On uniformly nearly-optimal Markov strategies

In this paper the following result is proved. In any total reward countable state Markov decision process a Markov strategy IT exists which is uniformly nearly-optimal in the following sense: v(i,π,) ≥ v*(i) − ε − εu*(i) for any initial state i. Here v* denotes the value function of the process and u* denotes the value of the process if all negative rewards are neglected