Seminar: On the computational complexity of stochastic controller optimization in POMDPs

SpeakerNikos Vlassis
AffiliationLuxembourg Centre for Systems Biomedicine, University of Luxembourg
DateThursday, 23 Feb 2012
Time13:00 - 14:00
Location1.02, Malet Place Engineering Building
Event seriesCSML Joint Seminar Series

In response to the computational intractability of searching for optimal policies in partially observable Markov decision processes (POMDPs), many researchers have turned to finite-state controllers as a more tractable alternative. We provide here a computational characterization of exactly solving problems in the class of stochastic controllers. In particular we show that the problem of finding an optimal stochastic `blind' controller 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 breakthroughs 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 in polynomial time.

iCalendar csml_id_13.ics