Point-Based POMDP Algorithms: Improved Analysis and Implementation

By Trey Smith, Reid G. Simmons. Conference on Uncertainty in Artificial Intelligence, 2005

436 citations recorded by the source corpus.

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.

Subfields: Computational Theory and Mathematics, Computer Networks and Communications, Numerical Analysis

View Paper: https://www.semanticscholar.org/paper/a66ad08e4a9d34f452a4f1a5d28a16a39c8c7f52

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

1. Brahim Chaib-draa
2. Lawrence Carin
3. Joelle Pineau
4. Susannah Young
5. Blaise Thomson
6. David Hsu
7. Stéphane Ross
8. Wee Sun Lee

In Computer Networks and Communications

1. Joelle Pineau
2. David Hsu
3. Wee Sun Lee
4. Brahim Chaib-draa
5. Lawrence Carin
6. Susannah Young
7. Blaise Thomson
8. Stéphane Ross

In Numerical Analysis

1. Brahim Chaib-draa
2. Lawrence Carin
3. Joelle Pineau
4. Susannah Young
5. Blaise Thomson
6. David Hsu
7. Stéphane Ross
8. Wee Sun Lee

Citations in the corpus

• Planning under Uncertainty for Robotic Tasks with Mixed Observability (2010, methodology): “For comparison, we also ran the original SARSOP algorithm (Kurniawati et al. 2008) on the same tasks modeled as standard POMDPs.”
• Multi-task Reinforcement Learning in Partially Observable Stochastic Environments (2009, background): “…1971 1978; Cheng 1988; Lovejoy 1991; Hansen 1997; Kaelbling et al. 1998; Poupart and Boutilier 2003; Pineau et al. 2003; Spaan and Vlassis 2005; Smith and Simmons 2005; Li et al. 2006ab) have been proposed, addressing problems of increasing complexity as the algorithms become progressively…”
• DESPOT: Online POMDP Planning with Regularization (2013, methodology): “Although offline planning algorithms have made major progress in recent years (Pineau et al., 2003; Spaan & Vlassis, 2005; Smith & Simmons, 2005; Kurniawati et al., 2008), they still face significant difficulty in scaling up to very large POMDPs, as they must plan for all beliefs and future…”
• Online Planning Algorithms for POMDPs (2008, methodology): “A heuristic similar to AEMS2 was also used by Smith and Simmons (2004) for their offline value iteration algorithm HSVI as a way to pick the next belief point at which to perform α-vector backups.”
• SARSOP: Efficient Point-Based POMDP Planning by Approximating Optimally Reachable Belief Spaces (2008, methodology): “in computing approximate solutions to large POMDPs [2, 5, 10, 16, 19, 20].”
• POMDP-Based Statistical Spoken Dialog Systems: A Review (2013, methodology): “Optimization by planning under uncertainty is attractive in that optimization methods are principled, and in some cases provide well-defined optimality bounds [17], [19].”
• Improved Memory-Bounded Dynamic Programming for Decentralized POMDPs (2007, neutral): “Successful error-bounding techniques for POMDPs have been introduced in [Pineau et al. , 2003] and [Smith and Simmons, 2005].”