On the Computational Complexity of Stochastic Controller Optimization in POMDPs
Authors:
Open Access
- 1 November 2012
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computation Theory
- Vol. 4 (4) , 1-8
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 14 references indexed in Scilit:
- Expectation maximisation methods for solving (PO)MDPs and optimal control problems2011
- On the Complexity of Nash Equilibria and Other Fixed PointsSIAM Journal on Computing, 2010
- On the Complexity of Numerical AnalysisSIAM Journal on Computing, 2009
- Markov decision processes under observability constraintsMathematical Methods of Operations Research, 2005
- Complexity of finite-horizon Markov decision process problemsJournal of the ACM, 2000
- Planning and acting in partially observable stochastic domainsArtificial Intelligence, 1998
- The Complexity of Markov Decision ProcessesMathematics of Operations Research, 1987
- Jointly Constrained Biconvex ProgrammingMathematics of Operations Research, 1983
- Markov programming with policy constraintsEuropean Journal of Operational Research, 1979
- Maxima for Graphs and a New Proof of a Theorem of TuránCanadian Journal of Mathematics, 1965