An Iterative Aggregation Procedure for Markov Decision Processes

Abstract

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 suggested for general linear programs.