Reference : On the computational complexity of stochastic controller optimization in POMDPs
Scientific journals : Article
Engineering, computing & technology : Computer science
http://hdl.handle.net/10993/2786
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 [> >]
2012
ACM Transactions on Computation Theory
4
4
1-9
Yes (verified by ORBilu)
1942-3454
1942-3462
[en] Partially observable Markov decision process ; stochastic controller ; bilinear program ; computational complexity ; Motzkin-Straus theorem ; sum-of-square-roots problem ; matrix fractional program ; nonlinear optimization
[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 is convex and admits efficient global solutions.
Luxembourg Centre for Systems Biomedicine (LCSB): Machine Learning (Vlassis Group)
http://hdl.handle.net/10993/2786
10.1145/2382559.2382563
http://arxiv.org/pdf/1107.3090v2.pdf

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Open access
1107.3090v2.pdfarXiv versionAuthor postprint339.46 kBView/Open

Bookmark and Share SFX Query

All documents in ORBilu are protected by a user license.