From a Value Function to a Dynamic Programming Principle
A value function records the best expected cost from each time and state. The dynamic programming principle (DPP) expresses that same optimization in two stages: choose a control up to an intermediate time, then account for the best continuation from the state reached at that time. The conditioning step is delicate. A continuation chosen to be nearly optimal from a deterministic state cannot automatically be treated as nearly optimal conditional on an event involving the past. We will make the admissible controls and the concatenation argument precise enough to avoid that gap.
Work on a filtered probability space \((\Omega,\mathcal{F},(\mathcal{F}_t)_{t\geq0},\mathbb{P})\) carrying a one-dimensional Brownian motion \(B_t\). For definiteness, take the canonical Wiener space with its completed Brownian filtration. Fix a finite horizon \(T\), a nonempty compact control set \(U\), and an initial time \(t\in[0,T]\). An admissible control on \([t,T]\) is a \(U\)-valued progressively measurable process for the Brownian filtration. The controller has no additional random information at time \(t\). In particular, a continuation control chosen at a deterministic state can be chosen as a function of the Brownian increments after its starting time, without using the path before that time.
For an admissible control \(\alpha\), the controlled state satisfies \(dX_r=b(r,X_r,\alpha_r)\,dr+\sigma(r,X_r,\alpha_r)\,dB_r\), with \(X_t=x\). The Ito integrand \(r\mapsto\sigma(r,X_r,\alpha_r)\) is progressively measurable and belongs to \(\mathcal{L}^2\) on each finite interval; this follows below from the bounded-coefficient assumption. The drift \(b\) and diffusion coefficient \(\sigma\) are bounded, measurable in time and control, and globally Lipschitz in the state uniformly in time and control. The running cost \(l\) and terminal cost \(g\) are bounded, measurable, and globally Lipschitz in the state uniformly in time and control. These assumptions ensure a unique strong solution for every admissible control and finite expected cost. Strong means the solution is constructed on the given space using the specified Brownian motion; the result below does not assert weak uniqueness or pathwise uniqueness beyond the standard strong well-posedness for these Lipschitz coefficients.
All costs are integrable because \(l\) and \(g\) are bounded. The DPP will be proved for every deterministic intermediate time \(s\in[t,T]\), including \(s=t\) and \(s=T\).
A Stability Bound Used in the Proof
The concatenation argument will approximate a random state by finitely many deterministic states. To control the approximation error, we first record how costs change when the initial state changes but the control is held fixed.
Proof. Drive the solutions \(X^x\) and \(X^y\) with the same Brownian motion and the same control, and put \(D_r=X_r^x-X_r^y\). If \(L\) is a common Lipschitz constant for \(b\) and \(\sigma\), their integral equations, Cauchy–Schwarz, and the Ito isometry give, for \(r\in[t,T]\), \[ \mathbb{E}|D_r|^2 \leq 3|x-y|^2+3L^2(r-t)\int_t^r\mathbb{E}|D_q|^2\,dq +3L^2\int_t^r\mathbb{E}|D_q|^2\,dq. \] Since \(r-t\leq T-t\), the last two terms are at most \(3L^2(T-t+1)\int_t^r\mathbb{E}|D_q|^2\,dq\). Gronwall's inequality therefore yields \(\mathbb{E}|D_r|^2\leq C_1|x-y|^2\) for a finite \(C_1\) depending only on \(L,T\). In particular, Cauchy–Schwarz gives \(\mathbb{E}|D_r|\leq\sqrt{C_1}|x-y|\). If \(L_l,L_g\) are the state Lipschitz constants of the costs, then \[ |J(t,x;\alpha)-J(t,y;\alpha)| \leq L_l\int_t^T\mathbb{E}|D_r|\,dr+L_g\mathbb{E}|D_T| \leq (L_l(T-t)+L_g)\sqrt{C_1}|x-y|. \] This bound is uniform in \(\alpha\). Taking infima preserves a common Lipschitz bound: \(J(t,x;\alpha)\leq J(t,y;\alpha)+C|x-y|\) for every \(\alpha\), so \(V(t,x)\leq V(t,y)+C|x-y|\); exchanging \(x\) and \(y\) gives the reverse inequality. \(\square\)
Bounded coefficients also give \(\mathbb{E}|X_s|^2<\infty\): write the integral equation for \(X_s\), bound the drift integral by Cauchy–Schwarz, and the diffusion integral by the Ito isometry. Thus the random intermediate state can be truncated to a large bounded interval with a tail probability tending to zero.
The Dynamic Programming Principle
Proof. First consider any admissible control \(\alpha\) on \([t,T]\). Conditional on the Brownian path up to \(s\), the continuation control from \(s\) onward is, for almost every realized past, an admissible control driven by the future Brownian increments. Those increments are independent of \(\mathcal{F}_s\). More precisely, on canonical Wiener space, conditioning on the path up to \(s\) gives a regular conditional distribution under which the shifted future path is Brownian; the section of a progressively measurable control is progressively measurable for almost every past. The conditional expected continuation cost is therefore the cost of an admissible control starting from the realized state \(X_s\), and is at least \(V(s,X_s)\). Taking conditional expectations and then expectations gives \[ J(t,x;\alpha)\geq \mathbb{E}\left[\int_t^s l(r,X_r,\alpha_r)\,dr+V(s,X_s)\right]. \] The quantities are integrable because the costs are bounded and \(V\) is bounded by \((T-s)\|l\|_\infty+\|g\|_\infty\). Taking the infimum over full-horizon controls shows that \(V(t,x)\) is at least the right-hand side of the theorem: any full-horizon control restricts to an admissible control on \([t,s]\), so its two-stage cost is no smaller than that infimum.
For the reverse inequality, fix any admissible control \(\alpha\) on \([t,s]\), and let \(Y=X_s\) under this control. Fix \(R>0\) and a mesh size \(\delta>0\). Partition \([-R,R]\) into finitely many disjoint intervals \(A_i\) of length at most \(\delta\), assigning each shared endpoint to exactly one interval (for example, use intervals closed on the left and open on the right, with the last interval closed at \(R\)). Choose a representative \(y_i\in A_i\) for each nonempty interval. For each \(i\), by the definition of infimum choose a deterministic-state admissible continuation \(\beta_i\), using only Brownian increments after \(s\), with \(J(s,y_i;\beta_i)\leq V(s,y_i)+\varepsilon\). There are only finitely many such choices.
After time \(s\), use \(\beta_i\) on the event \(\{Y\in A_i\}\). On \(\{|Y|>R\}\), use any fixed admissible continuation \(\beta_0\). This is an admissible concatenated control: the event selecting the continuation is \(\mathcal{F}_s\)-measurable, each continuation uses future increments only, and the finite selection is progressively measurable. Conditional on \(\mathcal{F}_s\), independence of future increments means that on \(\{Y\in A_i\}\) the continuation cost is \(J(s,Y;\beta_i)\), defined by starting the same future-increment control at the now-known state \(Y\). The stability bound and the choice of \(\beta_i\) give, on that event, \[ J(s,Y;\beta_i)\leq J(s,y_i;\beta_i)+C|Y-y_i| \leq V(s,Y)+\varepsilon+2C\delta. \] Here the second \(C\delta\) uses the Lipschitz bound for \(V\), and \(|Y-y_i|\leq\delta\). Crucially, \(\beta_i\) was selected independently of the pre-\(s\) information; the comparison uses its deterministic-state cost and then the uniform state-stability bound, not an unsupported conditional near-optimality claim.
Let \(M=\|l\|_\infty(T-s)+\|g\|_\infty\). Both any continuation cost and \(V(s,\cdot)\) have absolute value at most \(M\). Thus on \(\{|Y|>R\}\) the continuation cost of \(\beta_0\) exceeds \(V(s,Y)\) by at most \(2M\). The constructed full control consequently has cost at most \[ \mathbb{E}\left[\int_t^s l(r,X_r,\alpha_r)\,dr+V(s,Y)\right] +\varepsilon+2C\delta+2M\,\mathbb{P}(|Y|>R). \] Since \(\mathbb{E}|Y|^2<\infty\), Markov's inequality gives \(\mathbb{P}(|Y|>R)\leq\mathbb{E}|Y|^2/R^2\), which tends to zero as \(R\) tends to infinity. Let \(R\) tend to infinity, then \(\delta\) and \(\varepsilon\) tend to zero. It follows that \(V(t,x)\) is at most the displayed two-stage expected cost for this arbitrary \(\alpha\). Taking the infimum over \(\alpha\) proves the reverse inequality. If \(s=t\), both sides equal \(V(t,x)\) directly; if \(s=T\), the continuation value is \(V(T,X_T)=g(X_T)\), so the identity follows directly from the definition. \(\square\)
Worked Examples and Checks
Worked Example: Brownian Motion with a Squared Terminal Cost
Let there be no effective control, let \(dX_r=dB_r\), and let the terminal cost be \(g(x)=x^2\), with no running cost. Starting from \(x\) at time \(t\), compute the value and verify the DPP at an arbitrary \(s\in[t,T]\).
The solution is \(X_T=x+(B_T-B_t)\). The increment has mean \(0\) and variance \(T-t\), so \[ V(t,x)=\mathbb{E}[X_T^2]=x^2+T-t. \] At time \(s\), \(X_s=x+(B_s-B_t)\), hence \(\mathbb{E}[X_s^2]=x^2+s-t\). The DPP right-hand side is \[ \mathbb{E}[V(s,X_s)] =\mathbb{E}[X_s^2+T-s] =x^2+s-t+T-s =x^2+T-t. \] This agrees with the direct value.
Check: If \(s=t\), the expression is \(x^2+T-t\); if \(s=T\), it is \(\mathbb{E}[X_T^2]=x^2+T-t\). Both endpoint choices agree with the direct calculation.
Worked Example: A Bounded-Rate Deterministic Control
Consider \(dX_r=u_r\,dr\), \(u_r\in[-1,1]\), with terminal cost \(g(x)=x^2\) and zero running cost. Compute \(V(t,x)\) and check the DPP for \(t=0\), \(s=1\), \(T=2\), and \(x=3\).
Over a horizon of length \(h=T-t\), every terminal state lies in \([x-h,x+h]\), because \(\left|\int_t^T u_r\,dr\right|\leq h\). Every point of this interval is attainable by a constant control \(u\in[-1,1]\). The point in the interval closest to zero has absolute value \((|x|-h)_+=\max\{|x|-h,0\}\). Since the terminal cost is the square, this proves \(V(t,x)=(|x|-(T-t))_+^2\).
For the specified values, \(V(0,3)=(3-2)^2=1\). At time \(s=1\), any admissible control gives \(Y=X_1\in[2,4]\), since \(\int_0^1u_r\,dr\in[-1,1]\). The remaining value is \(V(1,Y)=(|Y|-1)_+^2\). On \([2,4]\), this is \((Y-1)^2\), whose minimum is \(1\) at \(Y=2\). Choosing \(u_r=-1\) on \([0,1]\) reaches \(Y=2\), so the DPP infimum is exactly \(1\).
Check: Continuing with \(u_r=-1\) on \([1,2]\) reaches \(X_2=1\), with terminal cost \(1\). The two-stage value and the directly attained full-horizon cost agree.
Worked Example: A Control That Only Adds Running Cost
Let \(dX_r=dB_r\), let \(U=\{0,1\}\), and set \(l(r,x,u)=u\), \(g(x)=0\). Find the value and verify the DPP at \(t=0\), \(s=1\), \(T=3\).
The state does not depend on \(u\), and the running cost is nonnegative. The control \(u_r=0\) at every time attains total cost \(0\); no control can have negative cost. Therefore \(V(t,x)=0\) for every \(t,x\). For any control on \([0,1]\), the DPP expression is \(\mathbb{E}[\int_0^1u_r\,dr+V(1,X_1)]=\mathbb{E}\int_0^1u_r\,dr\geq0\). Choosing \(u=0\) on this interval makes it zero, so the infimum is \(0=V(0,x)\).
Check: The continuation \(u=0\) on \([1,3]\) has cost \(0\) from every realized \(X_1\). This confirms directly that the intermediate value is the correct continuation cost.
What the DPP Does—and Does Not—Say
The DPP is an exact identity for expected costs under the stated Markov and admissibility structure. Its proof uses two different arguments: conditioning shows that no continuation can improve on the value at the reached state, while concatenation shows that near-optimal continuations can be used to approach that value. The latter requires care about information. In the proof, a finite collection of continuations is selected at deterministic representative states, independently of the pre-intermediate history; the random state is handled by a stability estimate and truncation.
A common mistake is to choose an arbitrary continuation \(\beta\) with \(J(s,y;\beta)\leq V(s,y)+\varepsilon\), then assert that its conditional cost on an event involving the past is bounded by the same deterministic-state cost. That conclusion does not follow: if \(\beta\) itself depends on the past, its unconditional expectation can average over past histories not present on the event. The correction is not to silently condition that inequality. Use continuations independent of the past, as above, or establish a suitable conditional near-optimality result with the required measurable-selection argument.
Under additional regularity, the DPP can be examined over a short time interval to derive a partial differential equation for the value function. The DPP itself is the optimization identity; it does not by itself assert differentiability of \(V\), nor does it supply a classical solution to such an equation.
Check Your Understanding
Use the assumptions and proof above to answer the following questions.
- Why does conditioning on \(\mathcal{F}_s\) make the shifted future Brownian increments suitable for evaluating continuation costs?
- In the upper-bound proof, why is it useful that each selected \(\beta_i\) depends only on future increments and not on the pre-\(s\) path?
- Which estimate controls the error from replacing \(Y\in A_i\) by its representative \(y_i\), and where does the second state-distance term arise?
- For the Brownian terminal-cost example, compute the DPP expression at \(x=0\), \(t=1\), \(s=2\), \(T=4\).
- In the deterministic-control example, what is the reachable interval at time \(s\), and why does minimizing the continuation value over it give the DPP infimum?