AGGREGATION OF THE POLICY ITERATION METHOD FOR NEARLY COMPLETELY DECOMPOSABLE MARKOV-CHAINS

This paper studies a steady-state optimal control problem for nearly completely decomposable Markov chains. In order to apply the policy iteration method of Howard, a high-dimensional ill-conditioned system of algebraic equations must be solved in the value determination step. Although algorithms exist for aggregation of the steady-state probability distribution problem, they only provide methods for computing the cost but not the dual variables. Using a singular perturbation approach, an aggregation method for the value determination equation is developed. The aggregation method is developed in three steps. First, a class of similarity transformations that transform the system into a singularly perturbed form is developed. Second, an aggregation method to compute the steady-state probability distribution is derived. Third, this aggregation method is appled to the value determination step of Howard's method.