The Complexity of Model Aggregation

We show that the problem of transforming a structured Markov decision process (MDP) into a Bounded Inir.jval MDP is coNPp p-hard. ITI particular, the test for ε-homogencity. a necessary part of verifying any proposed partition, is coNP^pp-complete. This indicates that., without, further assumptions on the sorts of partitioning allowed or the structure of the original proportional MDP, this is not likely to be a practical approach. We also analyze the complexity of finding the minimal-size partition, and of the k-block partition existence problem. Finally, we show that the test for homogeneity of an exact partition is complete for coNP^pp which is the same class as coNP^pp. All of this analysis applies equally well to the process of partitioning the state space via Structured Value Iteration.