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 mailto [University of Luxembourg > Luxembourg Centre for Systems Biomedicine (LCSB) > >]
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.

Bookmark and Share SFX Query

All documents in ORBilu are protected by a user license.