State aggregation in Markov decision processes

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 (ε_p, ε_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 ε_p for the state-transition effect and ε_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(ε_p, ε_f) neighborhood of the optimal solution to the original MDP problem. In real applications, the (ε_p, ε_f)-lumpable partition is usually obtained empirically. However, we also study the problem of looking for the coarsest (ε_p, ε_f)-lumpable partition, i.e., the partition with minimum number of subsets, given ε_p and ε_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.