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

An average-reward optimal policy maximizes the limiting expected reward per epoch, ${\mathrm{liminf}}_{n\to \infty }{n}^{-1}\mathbb{E}{\sum }_{t=1}^n{r}_t$, from each initial state. Here the state is the score modulo three. Under the coin policy the state moves to itself or its successor with probability one half. Its unique stationary distribution is uniform, so the reward for reaching state zero has average $g=1/3$ per toss.

The reward vector for that policy is $(1/2,0,1/2)$. Solving its Poisson equations $g+h_i=r_i+\frac{1}{2}{h}_i+\frac{1}{2}{h}_{i+1}$, with cyclic indices and $h_0=0$, gives $h=(0,-1/3,1/3)$. Telescoping the equations gives $F_s(i)=s/3+h_i-{\mathbb{E}}_{i}h(X_s)$. The chain is irreducible and aperiodic, so its last expectation converges to its stationary mean, independent of the starting state. ThereforeFor policy improvement, a die gives a uniform next residue, so its reward-plus-old-bias value is $1/3+(h_0+h_1+h_2)/3=1/3$. Coin values are $g+h_i=(1/3,0,2/3)$. Switch to the die at residue one and retain the coin at the others. The new stationary distribution is $(4/9,1/3,2/9)$ and its average reward is $4/9$, strictly better.

This improved policy is already optimal. Its bias is $h=(0,-1/9,1/9)$ and $g=4/9$. Die values are again $1/3$, whereas coin values are $(4/9,0,5/9)$. They satisfy the average-reward Bellman equation $g+h_i={\max }_a\{r_i(a)+{\mathbb{E}}_{a}h(X_{t+1})\}$. Summing the Bellman inequalities under any policy bounds its expected total reward by $ng$ plus a bounded bias difference; the proposed policy achieves equality. Hence