Aggregation and optimal control of nearly completely decomposable Markov chains

A study is made of the aggregation of nearly completely decomposable Markov chains. Three results are obtained. First, a similarity transformation that transforms the system into a singularly perturbed form is given. Second, an aggregation method for computing the exact steady-state probability distribution, as well as its O(∈^k) approximations, is derived. Third, a policy improvement algorithm based on the above aggregation method is developed for computing the optimal control that minimizes the average cost per stage over infinite horizon