# DESPOT: Online POMDP Planning with Regularization

arXiv: https://arxiv.org/abs/1609.03250 · HTML: https://mlsanity.com/paper/1609.03250/

## Key facts

- Cited by 106 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Sep 2016.

## Built on by (most cited first, 30 of 106)

- [Motion Planning for Autonomous Driving: The State of the Art and Future Perspectives](https://mlsanity.com/paper/2303.09824/) (2023)
- [Partially Observable Markov Decision Processes in Robotics: A Survey](https://mlsanity.com/paper/2209.10342/) (2022)
- [Deep Multiagent Reinforcement Learning: Challenges and Directions](https://mlsanity.com/paper/2106.15691/) (2021)
- [Learning in Observable POMDPs, without Computationally Intractable Oracles](https://mlsanity.com/paper/2206.03446/) (2022)
- [Planning in Observable POMDPs in Quasipolynomial Time](https://mlsanity.com/paper/2201.04735/) (2022)
- [Machine Learning for Autonomous Vehicle's Trajectory Prediction: A comprehensive survey, Challenges, and Future Research Directions](https://mlsanity.com/paper/2307.07527/) (2023)
- [Optimality Guarantees for Particle Belief Approximation of POMDPs](https://mlsanity.com/paper/2210.05015/) (2022)
- [Physical Interaction as Communication: Learning Robot Objectives Online from Human Corrections](https://mlsanity.com/paper/2107.02349/) (2021)
- [Equivariant Reinforcement Learning under Partial Observability](https://mlsanity.com/paper/2408.14336/) (2024)
- [What Truly Matters in Trajectory Prediction for Autonomous Driving?](https://mlsanity.com/paper/2306.15136/) (2023)
- [Partially Observable Task and Motion Planning with Uncertainty and Risk Awareness](https://mlsanity.com/paper/2403.10454/) (2024)
- [An Efficient, Generalized Bellman Update For Cooperative Inverse Reinforcement Learning](https://mlsanity.com/paper/1806.03820/) (2018)
- [Solving Common-Payoff Games with Approximate Policy Iteration](https://mlsanity.com/paper/2101.04237/) (2021)
- [Active Uncertainty Reduction for Safe and Efficient Interaction Planning: A Shielding-Aware Dual Control Approach](https://mlsanity.com/paper/2302.00171/) (2023)
- [Towards Optimal Correlational Object Search](https://mlsanity.com/paper/2110.09991/) (2021)
- [BetaZero: Belief-State Planning for Long-Horizon POMDPs using Learned Approximations](https://mlsanity.com/paper/2306.00249/) (2023)
- [Closing the Planning-Learning Loop with Application to Autonomous Driving](https://mlsanity.com/paper/2101.03834/) (2021)
- [CAR-DESPOT: Causally-Informed Online POMDP Planning for Robots in Confounded Environments](https://mlsanity.com/paper/2304.06848/) (2023)
- [Active Uncertainty Reduction for Human-Robot Interaction: An Implicit Dual Control Approach](https://mlsanity.com/paper/2202.07720/) (2022)
- [LEADER: Learning Attention over Driving Behaviors for Planning under Uncertainty](https://mlsanity.com/paper/2209.11422/) (2022)
- [Compositional Learning-based Planning for Vision POMDPs](https://mlsanity.com/paper/2112.09456/) (2021)
- [Safe POMDP Online Planning via Shielding](https://mlsanity.com/paper/2309.10216/) (2023)
- [SIDE: State Inference for Partially Observable Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2105.06228/) (2021)
- [Learning Logic Specifications for Soft Policy Guidance in POMCP](https://mlsanity.com/paper/2303.09172/) (2023)
- [Simplified Belief-Dependent Reward MCTS Planning with Guaranteed Tree Consistency](https://mlsanity.com/paper/2105.14239/) (2021)
- [Adaptive Information Belief Space Planning](https://mlsanity.com/paper/2201.05673/) (2022)
- [Efficient Algorithms for Planning with Participation Constraints](https://mlsanity.com/paper/2205.07767/) (2022)
- [Multiagent Reinforcement Learning for Autonomous Routing and Pickup Problem with Adaptation to Variable Demand](https://mlsanity.com/paper/2211.14983/) (2022)
- [Combining Tree-Search, Generative Models, and Nash Bargaining Concepts in Game-Theoretic Reinforcement Learning](https://mlsanity.com/paper/2302.00797/) (2023)
- [Adaptive Discretization using Voronoi Trees for Continuous POMDPs](https://mlsanity.com/paper/2302.10439/) (2023)

## Abstract (arXiv)

The partially observable Markov decision process (POMDP) provides a principled general framework for planning under uncertainty, but solving POMDPs optimally is computationally intractable, due to the "curse of dimensionality" and the "curse of history". To overcome these challenges, we introduce the Determinized Sparse Partially Observable Tree (DESPOT), a sparse approximation of the standard belief tree, for online planning under uncertainty. A DESPOT focuses online planning on a set of randomly sampled scenarios and compactly captures the "execution" of all policies under these scenarios. We show that the best policy obtained from a DESPOT is near-optimal, with a regret bound that depends on the representation size of the optimal policy. Leveraging this result, we give an anytime online planning algorithm, which searches a DESPOT for a policy that optimizes a regularized objective function. Regularization balances the estimated value of a policy under the sampled scenarios and the policy size, thus avoiding overfitting. The algorithm demonstrates strong experimental results, compared with some of the best online POMDP algorithms available. It has also been incorporated into an autonomous driving system for real-time vehicle control. The source code for the algorithm is available online.