Covering Number: Analyses for Approximate Continuous-state POMDP Planning (Extended Abstract)

To date, many theoretical results on discrete POMDPs have not yet been extended to continuous-state POMDPs, due to the infinite dimensionality of the belief space in a continuousstate case. In this paper, we define a distance in the n-metric space with respect to a partitioning representation of the continuous-state space, and formalize the size of the search space reachable under inadmissible heuristics via the covering number concept. Together with existing proof techniques in discrete POMDPs, we use the covering number to analyze the computational complexity of approximate planning for some types of continuous-state POMDPs.