Covering Number for Efficient Heuristic-based POMDP Planning

Zongzhang Zhang, David Hsu, Wee Sun Lee
Proceedings of the 31st International Conference on Machine Learning, PMLR 32(1):28-36, 2014.

Abstract

The difficulty of POMDP planning depends on the size of the search space involved. Heuristics are often used to reduce the search space size and improve computational efficiency; however, there are few theoretical bounds on their effectiveness. In this paper, we use the covering number to characterize the size of the search space reachable under heuristics and connect the complexity of POMDP planning to the effectiveness of heuristics. With insights from the theoretical analysis, we have developed a practical POMDP algorithm, Packing-Guided Value Iteration (PGVI). Empirically, PGVI is competitive with the state-of-the-art point-based POMDP algorithms on 65 small benchmark problems and outperforms them on 4 larger problems.

Cite this Paper

BibTeX
@InProceedings{pmlr-v32-zhanga14, title = {Covering Number for Efficient Heuristic-based POMDP Planning}, author = {Zhang, Zongzhang and Hsu, David and Lee, Wee Sun}, booktitle = {Proceedings of the 31st International Conference on Machine Learning}, pages = {28--36}, year = {2014}, editor = {Xing, Eric P. and Jebara, Tony}, volume = {32}, number = {1}, series = {Proceedings of Machine Learning Research}, address = {Bejing, China}, month = {22--24 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v32/zhanga14.pdf}, url = {https://proceedings.mlr.press/v32/zhanga14.html}, abstract = {The difficulty of POMDP planning depends on the size of the search space involved. Heuristics are often used to reduce the search space size and improve computational efficiency; however, there are few theoretical bounds on their effectiveness. In this paper, we use the covering number to characterize the size of the search space reachable under heuristics and connect the complexity of POMDP planning to the effectiveness of heuristics. With insights from the theoretical analysis, we have developed a practical POMDP algorithm, Packing-Guided Value Iteration (PGVI). Empirically, PGVI is competitive with the state-of-the-art point-based POMDP algorithms on 65 small benchmark problems and outperforms them on 4 larger problems.} }
Endnote
%0 Conference Paper %T Covering Number for Efficient Heuristic-based POMDP Planning %A Zongzhang Zhang %A David Hsu %A Wee Sun Lee %B Proceedings of the 31st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2014 %E Eric P. Xing %E Tony Jebara %F pmlr-v32-zhanga14 %I PMLR %P 28--36 %U https://proceedings.mlr.press/v32/zhanga14.html %V 32 %N 1 %X The difficulty of POMDP planning depends on the size of the search space involved. Heuristics are often used to reduce the search space size and improve computational efficiency; however, there are few theoretical bounds on their effectiveness. In this paper, we use the covering number to characterize the size of the search space reachable under heuristics and connect the complexity of POMDP planning to the effectiveness of heuristics. With insights from the theoretical analysis, we have developed a practical POMDP algorithm, Packing-Guided Value Iteration (PGVI). Empirically, PGVI is competitive with the state-of-the-art point-based POMDP algorithms on 65 small benchmark problems and outperforms them on 4 larger problems.
RIS
TY - CPAPER TI - Covering Number for Efficient Heuristic-based POMDP Planning AU - Zongzhang Zhang AU - David Hsu AU - Wee Sun Lee BT - Proceedings of the 31st International Conference on Machine Learning DA - 2014/01/27 ED - Eric P. Xing ED - Tony Jebara ID - pmlr-v32-zhanga14 PB - PMLR DP - Proceedings of Machine Learning Research VL - 32 IS - 1 SP - 28 EP - 36 L1 - http://proceedings.mlr.press/v32/zhanga14.pdf UR - https://proceedings.mlr.press/v32/zhanga14.html AB - The difficulty of POMDP planning depends on the size of the search space involved. Heuristics are often used to reduce the search space size and improve computational efficiency; however, there are few theoretical bounds on their effectiveness. In this paper, we use the covering number to characterize the size of the search space reachable under heuristics and connect the complexity of POMDP planning to the effectiveness of heuristics. With insights from the theoretical analysis, we have developed a practical POMDP algorithm, Packing-Guided Value Iteration (PGVI). Empirically, PGVI is competitive with the state-of-the-art point-based POMDP algorithms on 65 small benchmark problems and outperforms them on 4 larger problems. ER -
APA
Zhang, Z., Hsu, D. & Lee, W.S.. (2014). Covering Number for Efficient Heuristic-based POMDP Planning. Proceedings of the 31st International Conference on Machine Learning, in Proceedings of Machine Learning Research 32(1):28-36 Available from https://proceedings.mlr.press/v32/zhanga14.html.

Related Material