Past exam of the mathematics course of the University of Cambridge / 2005 / ii / Paper 2 / 29I / Solution

A time-homogeneous Markov decision process specifies a state space, admissible actions at each state, an action-dependent transition kernel and one-step reward, with neither kernel nor reward depending on time. A policy chooses actions using the observed history. The positive programming case has nonnegative rewards and maximizes expected undiscounted total reward, allowing infinite values; its finite-horizon values increase to the infinite-horizon supremum under the appropriate approximation argument.

Here let ${\tau }_B$ be the absorption time of the underlying simple random walk at $0,N$. Every admissible stopping time $T$ is at most ${\tau }_B$. The reward is bounded by $R_{\max }={\max }_{j}r(j)$, and $E_i{\tau }_B=i(N-i)$, as follows by solving $h_i=1+(h_{i-1}+h_{i+1})/2$ with zero endpoint values. In particular absorption is almost surely finite. Truncating any policy at $T\wedge n$ changes its reward expectation by at most $2R_{\max }{P}_i({\tau }_B>n)\le 2R_{\max }i(N-i)/n$. Since the truncated policy is allowed in the $n$-step problem,This proves $V_n\to V$, even uniformly on the finite state space.

The finite-horizon recursion starts with $V_0=r$, fixes the endpoint rewards and hasTaking limits shows $V\ge r$ and $2V(i)\ge V(i-1)+V(i+1)$, so $V$ is discretely concave. If $W$ is any concave function majorizing $r$, induction in this same recursion gives $V_n\le W$, and hence $V\le W$. Therefore $V$ is the smallest concave majorant of the rewards. At a point where $V(i)>r(i)$ the recursion forces equality with the neighboring average; the value graph is linear through each consecutive continuation region.

An optimal policy stops upon first entering the contact set $\{i:V(i)=r(i)\}$ and continues elsewhere. Before stopping the neighboring-average equality makes $V$ of the walk a bounded martingale; the stopping time is bounded by ${\tau }_B$. Applying the bounded stopping identity by first truncating the time and then passing to the limit proves the expected terminal reward equals $V(i)$.

Distinct rewards do not guarantee uniqueness. With $N=2$ and $r(0)=0,r(1)=1,r(2)=2$, the reward function is already linear and $V=r$. From state one, stopping gives one, while continuing to the next step also gives expected reward $(0+2)/2=1$. Both policies are optimal. Thus the claimed uniqueness is false even when all rewards are distinct.