State aggregation in Markov decision processes
Zhiyuan Ren, Bruce H. Krogh · 2004
We study state aggregation for Markov decision processes (MDPs) with long-run average-cost optimality criterion in this paper. The aggregation is based on a definition of an (/spl epsiv//sub p/, /spl epsiv//sub f/)-lumpable partition of the state space, where the difference between the control effect of any control action on any two states belonging to the same subset in the partition is bounded by /spl epsiv//sub p/ for the state-transition effect and /spl epsiv//sub f/ for the cost effect. The states in the same partition subset are treated into one meta-state to obtain an aggregated Markov chain. We then construct an aggregated MDP with average cost on the aggregated Markov chain. We develop an algorithm to find the solution to this aggregated MDP problem and show its performance is within some o(/spl epsiv//sub p/, /spl epsiv//sub f/) neighborhood of the optimal solution to the original MDP problem. In real applications, the (/spl epsiv//sub p/, /spl epsiv//sub f/)-lumpable partition is usually obtained empirically. However, we also study the problem of looking for the coarsest (/spl epsiv//sub p/, /spl epsiv//sub f/)-lumpable partition, i.e., the partition with minimum number of subsets, given /spl epsiv//sub p/ and /spl epsiv//sub f/. We prove that this partitioning problem is in the time complexity class of P-hard, which is not easier than the original MDP problem in the class of P-complete.