Point-Based POMDP Algorithms: Improved Analysis and Implementation

Abstract

Existing complexity bounds for point-based POMDP value iteration algorithms focus either on the curse of dimensionality or the curse of history. We derive a new bound that relies on both and uses the concept of discounted reachability; our conclusions may help guide future algorithm design. We also discuss recent improvements to our (point-based) heuristic search value iteration algorithm. Our new implementation calculates tighter initial bounds, avoids solving linear programs, and makes more effective use of sparsity.

Appears in Proceedings of the Twenty-First Conference on Uncertainty in Artificial Intelligence (UAI2005)

References in corpus (3)

• Value-Function Approximations for Partially Observable Markov Decision Processes
• Incremental Pruning: A Simple, Fast, Exact Method for Partially Observable Markov Decision Processes
• Speeding Up the Convergence of Value Iteration in Partially Observable Markov Decision Processes

Cited by in corpus (1)

• Training Beam Sequence Design for Millimeter-Wave MIMO Systems: A POMDP Framework