The Complexity of Model Aggregation

Judy Goldsmith and Robert H. Sloan

We show that the problem of transforming a structured Markov decision process (MDP) into a Bounded Interval MDP is coNPPP-hard. In particular, the test for e -homogeneity, a necessary part of verifying any proposed partition, is coNPPP-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 ofan exact partition is complete for coNPC- P, which is the same class as coNPPP. All of this analysis applies equally well to the process of partitioning the state space via Structured Value Iteration.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.