Point-Based POMDP Algorithms: Improved Analysis and Implementation
arXiv:1207.1412
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)
Cited by in corpus (14)
- Online Planning Algorithms for POMDPs
- DESPOT: Online POMDP Planning with Regularization
- Policy Iteration for Decentralized Control of Markov Decision Processes
- Efficient Planning under Uncertainty with Macro-actions
- Modelling Observation Correlations for Active Exploration and Robust Object Detection
- Non-Stationary Bandits with Habituation and Recovery Dynamics
- Pilot Beam Sequence Design for Channel Estimation in Millimeter-Wave MIMO Systems: A POMDP Framework
- Optimizing Sequential Medical Treatments with Auto-Encoding Heuristic Search in POMDPs
- Exploiting Causality for Selective Belief Filtering in Dynamic Bayesian Networks
- Near Optimality of Finite Memory Feedback Policies in Partially Observed Markov Decision Processes
- Adaptive Belief Discretization for POMDP Planning
- Finite Model Approximations for Partially Observed Markov Decision Processes with Discounted Cost
- Stochastic 2-D Motion Planning with a POMDP Framework
- Training Beam Sequence Design for Millimeter-Wave MIMO Systems: A POMDP Framework