Asymptotic linear programming and policy improvement for singularly perturbed Markov decision processes

In this paper we consider a singularly perturbed Markov decision process with finitely many states and actions and the limiting expected average reward criterion. We make no assumptions about the underlying ergodic structure. We present algorithms for the computation of a uniformly optimal deterministic control, that is, a control which is optimal for all values of the perturbation parameter that are sufficiently small. Our algorithms are based on Jeroslow's Asymptotic Linear Programming.