Past exam of the mathematics course of the University of Cambridge / 2010 / ii / Paper 3 / 28J / Solution

A control policy specifies each control as a nonanticipating measurable function of the observed history, possibly with additional randomization. It may depend on time and the entire past; a stationary Markov policy uses only the current state. We use the standard admissibility assumptions allowing measurable choices and concatenation of continuation policies.

The dynamic programming operator is monotone: $f\le g$ implies $\mathcal{L}f\le \mathcal{L}g$. Nonnegative costs give $F_1\ge F_0=0$, so induction gives $F_{t+1}\ge F_t$. Thus $F_t$ increases pointwise to an extended nonnegative limit $F_{\infty }$. Backward induction identifies $F_t$ with the infimum of expected costs for the first $t$ periods: condition on the first control and next state, then optimize the continuation. Every infinite-horizon policy has at least that finite-horizon cost, so

For the Bellman equation, any infinite-horizon policy, conditional on its first action and next state, has continuation cost at least $F(X_1)$. Its total cost is therefore at least $\mathcal{L}F(x)$; infimizing gives $F\ge \mathcal{L}F$. For the reverse inequality at a state with finite $\mathcal{L}F(x)$, choose a first action within $\epsilon /2$ of its infimum and concatenate continuation policies whose costs are within $\epsilon /(2\beta )$ of $F(y)$ at each next state $y$. This produces a policy of cost at most $\mathcal{L}F(x)+\epsilon$. Such continuations are needed only at states of finite value, which have probability one under an action with finite continuation expectation. Let $\epsilon \downarrow 0$. If $\mathcal{L}F(x)=\infty$, the first inequality already gives $F(x)=\infty$. Therefore

Let $\Phi =\mathcal{L}\Phi \ge 0$, and use the permitted selector $u_{\ast }$. Under the stationary policy $u_{\ast }(X_t)$, repeated conditional expectation givesIf $\Phi (x)$ is infinite the desired comparison is immediate; otherwise these nonnegative quantities have finite expectations and the displayed recursion is legitimate. Drop the terminal term and apply monotone convergence theorem as $T\to \infty$. The policy's infinite-horizon cost is at most $\Phi (x)$, soThus the value is the least nonnegative Bellman fixed point. The argument works also for $\beta =1$ because costs and the dropped terminal term are nonnegative; it makes no unwarranted contraction or finite-value assumption.