On the Computational Complexity of Stochastic Controller Optimization in POMDPs
Lists
Only you see this
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.
BibTeX
@article{vlassis2011computational,
author = {Nikos Vlassis and Michael L. Littman and David Barber},
title = {{On the Computational Complexity of Stochastic Controller Optimization in POMDPs}},
journal = {ACM Trans. Comput. Theory},
year = {2011},
doi = {10.1145/2382559.2382563},
}