Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/40978
Title: What makes some POMDP problems easy to approximate?
Authors: Hsu, D. 
Lee, W.S. 
Rong, N.
Issue Date: 2009
Source: Hsu, D.,Lee, W.S.,Rong, N. (2009). What makes some POMDP problems easy to approximate?. Advances in Neural Information Processing Systems 20 - Proceedings of the 2007 Conference. ScholarBank@NUS Repository.
Abstract: Point-based algorithms have been surprisingly successful in computing approximately optimal solutions for partially observable Markov decision processes (POMDPs) in high dimensional belief spaces. In this work, we seek to understand the belief-space properties that allow some POMDP problems to be approximated efficiently and thus help to explain the point-based algorithms' success often observed in the experiments. We show that an approximately optimal POMDP solution can be computed in time polynomial in the covering number of a reachable belief space, which is the subset of the belief space reachable from a given belief point. We also show that under the weaker condition of having a small covering number for an optimal reachable space, which is the subset of the belief space reachable under an optimal policy, computing an approximately optimal solution is NP-hard. However, given a suitable set of points that "cover" an optimal reachable space well, an approximate solution can be computed in polynomial time. The covering number highlights several interesting properties that reduce the complexity of POMDP planning in practice, e.g., fully observed state variables, beliefs with sparse support, smooth beliefs, and circulant state-transition matrices.
Source Title: Advances in Neural Information Processing Systems 20 - Proceedings of the 2007 Conference
URI: http://scholarbank.nus.edu.sg/handle/10635/40978
ISBN: 160560352X
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

59
checked on Dec 9, 2017

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.