On the Computational Complexity of Stochastic Controller Optimization in POMDPs
Preprint
Abstract
We show that the problem of finding an optimal stochastic 'blind' controller in a Markov decision process is an NP-hard problem. The corresponding decision problem is NP-hard, in PSPACE, and SQRT-SUM-hard, hence placing it in NP would imply breakthroughs in long-standing open problems in computer science. Our result establishes that the more general problem of stochastic controller optimization in POMDPs is also NP-hard. Nonetheless, we outline a special case that is convex and admits efficient global solutions.Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- On the Complexity of Nash Equilibria and Other Fixed PointsSIAM Journal on Computing, 2010
- Markov decision processes under observability constraintsMathematical Methods of Operations Research, 2005
- Nonapproximability Results for Partially Observable Markov Decision ProcessesJournal of Artificial Intelligence Research, 2001
- Complexity of finite-horizon Markov decision process problemsJournal of the ACM, 2000
- The Computational Complexity of Probabilistic PlanningJournal of Artificial Intelligence Research, 1998
- Planning and acting in partially observable stochastic domainsArtificial Intelligence, 1998
- Jointly Constrained Biconvex ProgrammingMathematics of Operations Research, 1983
- Markov programming with policy constraintsEuropean Journal of Operational Research, 1979
- Markov Decisions on a Partitioned State SpaceIEEE Transactions on Systems, Man, and Cybernetics, 1971