Reasoning and predicting POMDP planning complexity via covering numbers

详细信息    查看全文

• 作者：Zongzhang Zhang ; Qiming Fu ; Xiaofang Zhang ; Quan Liu
• 刊名：Frontiers of Computer Science in China
• 出版年：2016
• 出版时间：August 2016
• 年：2016
• 卷：10
• 期：4
• 页码：726-740
• 全文大小：573 KB
• 刊物类别：Computer Science
• 刊物主题：Computer Science, general
  Chinese Library of Science
  
• 出版者：Higher Education Press, co-published with Springer-Verlag GmbH
• ISSN：1673-7466
• 卷排序：10

文摘

Partially observable Markov decision processes (POMDPs) provide a rich mathematical framework for planning tasks in partially observable stochastic environments. The notion of the covering number, a metric of capturing the search space size of a POMDP planning problem, has been proposed as a complexity measure of approximate POMDP planning. Existing theoretical results are based on POMDPs with finite and discrete state spaces and measured in the l₁-metric space. When considering heuristics, they are assumed to be always admissible. This paper extends the theoretical results on the covering numbers of different search spaces, including the newly defined space reachable under inadmissible heuristics, to the l_n-metric spaces. We provide a simple but scalable algorithm for estimating covering numbers. Experimentally, we provide estimated covering numbers of the search spaces reachable by following different policies on several benchmark problems, and analyze their abilities to predict the runtime of POMDP planning algorithms.KeywordsPOMDP planningcomplexity theorycovering numbersearch space