[en] 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 a breakthrough in long-standing open problems in computer science. Our optimization 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 solvable to arbitrary accuracy in polynomial time via semidefinite or second-order cone programming.
Disciplines :
Sciences informatiques
Auteur, co-auteur :
VLASSIS, Nikos ; University of Luxembourg > Luxembourg Centre for Systems Biomedicine (LCSB)
Littman, Michael L.
Barber, David
Langue du document :
Anglais
Titre :
On the computational complexity of stochastic controller optimization in POMDPs
