References of "Littman, Michael L."
     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: 105 (8 UL)
See detailOn the computational complexity of stochastic controller optimization in POMDPs
Vlassis, Nikos UL; Littman, Michael L.; Barber, David

E-print/Working paper (2011)

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 solvable to arbitrary accuracy in polynomial time via semidefinite or second-order cone programming. [less ▲]

Detailed reference viewed: 96 (0 UL)