References of "ACM Transactions on Computation Theory"
     in
Bookmark and Share    
Full Text
Peer Reviewed
See detailOn the computational complexity of stochastic controller optimization in POMDPs
Vlassis, Nikos UL; Littman, Michael L.; Barber, David

in ACM Transactions on Computation Theory (2012), 4(4), 1-9

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 ... [more ▼]

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. [less ▲]

Detailed reference viewed: 58 (8 UL)