Covering Number for Efficient Heuristic-based POMDP Planning
Zongzhang Zhang, David Hsu, Wee Sun Lee · 2014
The difficulty of POMDP planning depends on the size of the search space involved. Heuris-tics are often used to reduce the search space size and improve computational efficiency; how-ever, there are few theoretical bounds on their effectiveness. In this paper, we use the cover-ing number to characterize the size of the search space reachable under heuristics and connect the complexity of POMDP planning to the effective-ness of heuristics. With insights from the the-oretical analysis, we have developed a practical POMDP algorithm, Packing-Guided Value Iter-ation (PGVI). Empirically, PGVI is competitive with the state-of-the-art point-based POMDP al-gorithms on 65 small benchmark problems and outperforms them on 4 larger problems. 1.