An Iterative Aggregation Procedure for Markov Decision Processes

An iterative aggregation procedure is described for solving large scale, finite state, finite action Markov decision processes (MDPs). At each iteration, an aggregate master problem and a sequence of smaller subproblems are solved. The weights used to form the aggregate master problem are based on the estimates from the previous iteration. Each subproblem is a finite state, finite action MDP with a reduced state space and unequal row sums. Global convergence of the algorithm is proven under very weak assumptions. The proof relates this technique to other iterative methods that have been sug-gested for general linear programs. OST REAL applications of Markov decision processes (MDPs) M give rise to very large problems; this is particularly true if the state is represented as a vector of dimension greater than two or three. The major limitation to solving large scale MDPs appears to be in-core storage, as computers are now capable of performing iterations of algo-rithms for MDPs quickly. However, a 7-dimensional state with only 5 grid points per dimension would have 78,125 states and a transition matrix for each policy that could not be stored in present-day computers. In this paper, an iterative aggregation procedure is described for solving large scale MDPs which relieves this storage burden considerably. The procedure to be described uses the linear programming (LP) formulation of a discounted MDP (d’Epenoux [1963]) and employs ideas for aggregation of LPs developed in Vakhutinskii and Dudkin [1973]