Optimal and suboptimal stationary controls for Markov chains

The problem studied is that of controlling a Markov chain so as to minimize the long run expected cost per unit time. Three results are obtained. First, a necessary and sufficient condition for optimality is given. The second gives for any strategy
u
, an easily computable bound
B (u) \geq J(u)-J^{\ast}
, where J
^*
is the minimum cost. The third result consists of an algorithm which, starting with any strategy, successively generates alternative strategies so that the bound
B (u)
decreases monotonically to zero.