On the Computational Complexity of Stochastic Controller Optimization in POMDPs

Nikos Vlassis, Michael L. Littman, David Barber

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 P…