ALGORITHMS FOR SINGULARLY PERTURBED LIMITING AVERAGE MARKOV CONTROL-PROBLEMS

We consider a singularly perturbed Markov decision process with the limiting average reward criterion. We assume that the underlying process is composed of n separate irreducible processes, and that the small perturbation is such that it "unites" these processes into a single irreducible process. We present two algorithms for the solution of the underlying "limit Markov control problem." The first of these is a linear program possessing the Wolfe-Dantzig structure inherited from the ergodic "nearly-decomposable" assumption in the model. The second is an aggregation-disaggregation policy improvement algorithm.