Past exam of the mathematics course of the University of Cambridge / 2008 / ii / Paper 2 / 29I (Optimization and Control)

The average-cost Bellman equation isIf a constant $g$ and bounded relative cost function $\theta$ solve this equation and a stationary control attains the infimum in each state, that control is optimal and its long-run expected average cost is $g$. Indeed the Bellman inequality telescopes along any controlled trajectory; dividing by the number of steps removes the bounded endpoint terms and gives a lower bound $g$. The attaining policy makes the inequalities equalities. An unbounded $\theta$ requires the corresponding endpoint/transversality justification, which the question permits for this example.

To maximize occupation of zero, minimize $c(x,u)=-1_{\{x=0\}}$ and try $\theta (x)=\mu |x|$ with $\mu >0$. For $x>0$, the expected increment of $\theta$ is $\mu (2u-1)$, minimized at $u=\alpha$; for $x<0$, it is $\mu (1-2u)$, minimized at $u=1-\alpha$. At zero its expected next value is $\mu$, independent of $u$. Thus $g=\mu (2\alpha -1)$ away from zero and $g=-1+\mu$ at zero. Solving givesAn optimal control always biases a nonzero position towards zero: $u=\alpha$ on positive integers, $u=1-\alpha$ on negative integers, and any allowed $u$ at zero.

As an independent occupation check, fix the choice $u_0$ at zero. The stationary positive tail begins at ${\pi }_1={\pi }_0{u}_0/(1-\alpha )$ and has common ratio $\alpha /(1-\alpha )$; the negative tail begins at ${\pi }_{-1}={\pi }_0(1-u_0)/(1-\alpha )$ with the same ratio. Summing these geometric tails gives $1={\pi }_0[1+1/(1-2\alpha )]$, reproducing the boxed optimum. The chain has period two, but its time-averaged occupation still converges to this stationary proportion.