(The Odoni Bound) Let k’ be the optimal stationary policy for a Markov decision problem and let g’ and π’ be the corresponding gain and steady-state probability respectively. Let v * i (n, u) be the...

(The Odoni Bound) Let k’ be the optimal stationary policy for a Markov decision problem and let g’ and π’ be the corresponding gain and steady-state probability respectively. Let v^*
_i
(n, u) be the optimal dynamic expected reward for starting in state i at stage n with final reward vector u.