2012/07/11 by Zhengzhu Feng, Feng, Zhengzhu, Shlomo Zilberstein +1
Computer Science · #AI-based Problem Solving and Planning #Artificial Intelligence (cs.AI) #Bayesian Modeling and Causal Inference #FOS: Computer and information sciences #Machine Learning and Algorithms #cs.AI
paper · pdf · doi:10.48550/arxiv.1207.4116
Appears in Proceedings of the Twentieth Conference on Uncertainty in Artificial Intelligence (UAI2004)
arxiv created 2012/07/11 · openalex publication_date 2012/07/11 · arxiv updated 2012/07/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present a major improvement to the incremental pruning algorithm for solving partially observable Markov decision processes. Our technique targets the cross-sum step of the dynamic programming (DP) update, a key source of complexity in POMDP algorithms. Instead of reasoning about the whole belief space when pruning the cross-sums, our algorithm divides the belief space into smaller regions and performs independent pruning in each region. We evaluate the benefits of the new technique both analytically and experimentally, and show that it produces very significant performance gains. The results contribute to the scalability of POMDP algorithms to domains that cannot be handled by the best existing techniques.