Article (Scientific journals)
On the computational complexity of stochastic controller optimization in POMDPs
VLASSIS, Nikos; Littman, Michael L.; Barber, David
2012In ACM Transactions on Computation Theory, 4 (4), p. 1-9
Peer Reviewed verified by ORBi
 

Files


Full Text
1107.3090v2.pdf
Author postprint (347.6 kB)
arXiv version
Download

All documents in ORBilu are protected by a user license.

Send to



Details



Keywords :
Partially observable Markov decision process; stochastic controller; bilinear program; computational complexity; Motzkin-Straus theorem; sum-of-square-roots problem; matrix fractional program; nonlinear optimization
Abstract :
[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.
Research center :
Luxembourg Centre for Systems Biomedicine (LCSB): Machine Learning (Vlassis Group)
Disciplines :
Computer science
Identifiers :
UNILU:UL-ARTICLE-2011-697
Author, co-author :
VLASSIS, Nikos ;  University of Luxembourg > Luxembourg Centre for Systems Biomedicine (LCSB)
Littman, Michael L.
Barber, David
External co-authors :
yes
Language :
English
Title :
On the computational complexity of stochastic controller optimization in POMDPs
Publication date :
2012
Journal title :
ACM Transactions on Computation Theory
ISSN :
1942-3454
eISSN :
1942-3462
Publisher :
Association for Computing Machinery (ACM), United States - New York
Volume :
4
Issue :
4
Pages :
1-9
Peer reviewed :
Peer Reviewed verified by ORBi
Available on ORBilu :
since 24 June 2013

Statistics


Number of views
56 (10 by Unilu)
Number of downloads
96 (1 by Unilu)

Scopus citations®
 
61
Scopus citations®
without self-citations
59
OpenCitations
 
11
OpenAlex citations
 
66

Bibliography


Similar publications



Contact ORBilu