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

	Document type :	E-prints/Working papers : Already available on another site
	Discipline(s) :	Engineering, computing & technology : Computer science
	To cite this reference:	http://hdl.handle.net/10993/3388

Title :	On the computational complexity of stochastic controller optimization in POMDPs
Language :	English
Author, co-author :	Vlassis, Nikos [University of Luxembourg > Luxembourg Centre for Systems Biomedicine (LCSB) > >]
	Littman, Michael L. []
	Barber, David []
Publication date :	2011
Peer reviewed :	No
Abstract :	[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 solvable to arbitrary accuracy in polynomial time via semidefinite or second-order cone programming.
Permalink :	http://hdl.handle.net/10993/3388
source URL :	http://arxiv.org/abs/1107.3090v1

There is no file associated with this reference.

All documents in ORBi^lu are protected by a user license.

 

University of Luxembourg Library |  Feedback |  Legal notices Site Map