Algorithms for singularly perturbed limiting average Markov control problems

The authors consider a singularly perturbed Markov decision process (MDP) with the limiting average cost criterion. It is assumed 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. This structure corresponds to the Markov chains admitting strong and weak interactions. The authors introduce the formulation and some results given by T. R. Bielecki and J. A. Filar (1989) for the underlying control problem for the singularly perturbed MDP, the so-called limit Markov control problem (limit MCP). It is demonstrated here that the limit MCP can be solved by a suitably constructed linear program. An algorithm for solving the limit MCP based on the policy improvement method is constructed.