Please use this identifier to cite or link to this item:
|Title:||What makes some POMDP problems easy to approximate?||Authors:||Hsu, D.
|Issue Date:||2009||Citation:||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.
checked on May 17, 2019
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.