On the computational complexity of stochastic controller optimization in POMDPs

Nikos Vlassis, Michael L. Littman, David Barber

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},
}
Figure