[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-3462
Publisher :
Association for Computing Machinery (ACM), United States - New York
