On the Computational Complexity of Stochastic Controller Optimization in POMDPs

We show that the problem of finding an optimal stochastic 'blind' controller\nin a Markov decision process is an NP-hard problem. The corresponding decision\nproblem is NP-hard, in PSPACE, and SQRT-SUM-hard, hence placing it in NP would\nimply breakthroughs in long-standing open problems in computer science. Our\nresult establishes that the more general problem of stochastic controller\noptimization in POMDPs is also NP-hard. Nonetheless, we outline a special case\nthat is convex and admits efficient global solutions.\n