Reasoning and predicting POMDP planning complexity via covering numbers |
| |
| Authors: | Zongzhang?Zhang,Qiming?Fu,Xiaofang?Zhang,Quan?Liu author-information" > author-information__contact u-icon-before" > mailto:quanliu@suda.edu.cn" title=" quanliu@suda.edu.cn" itemprop=" email" data-track=" click" data-track-action=" Email author" data-track-label=" " >Email author |
| |
| Affiliation: | 1.School of Computer Science and Technology,Soochow University,Suzhou,China;2.Collaborative Innovation Center of Novel Software Technology and Industrialization,Nanjing,China;3.School of Electronic and Information Engineering,Suzhou University of Science and Technology,Suzhou,China;4.Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education,Jilin University,Changchun,China |
| |
| Abstract: | 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 1-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. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
