The Complexity of Model Aggregation

摘要

We show that the problem of transforming a structured Markov decision process (MDP) into a Bounded Interval MDP is coNP~(PP)-hard. In particular, the test for ε-homogeneity, 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 propositional 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~(C=P), 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.