Reference : On the computational complexity of stochastic controller optimization in POMDPs |
E-prints/Working papers : Already available on another site | |||
Engineering, computing & technology : Computer science | |||
http://hdl.handle.net/10993/3388 | |||
On the computational complexity of stochastic controller optimization in POMDPs | |
English | |
Vlassis, Nikos ![]() | |
Littman, Michael L. [] | |
Barber, David [] | |
2011 | |
No | |
[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. | |
http://hdl.handle.net/10993/3388 | |
http://arxiv.org/abs/1107.3090v1 |
There is no file associated with this reference.
All documents in ORBilu are protected by a user license.