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

Speaker | Nikos Vlassis |
---|---|

Affiliation | Luxembourg Centre for Systems Biomedicine, University of Luxembourg |

Date | Thursday, 23 Feb 2012 |

Time | 13:00 - 14:00 |

Location | 1.02, Malet Place Engineering Building |

Event series | CSML Joint Seminar Series |

Description |
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 |