Reproduce “DESPOT: Online POMDP Planning with Regularization” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Nan Ye, Adhiraj Somani, David Hsu, Wee Sun Lee
The DESPOT algorithm provides a scalable online planning solution for Partially Observable Markov Decision Processes (POMDPs) by using a sparse tree representation based on sampled scenarios and incorporating a regularization term to prevent overfitting. This approach enables near-optimal decision-making in real-time for large state and observation spaces, outperforming prior methods on various complex benchmarks, including domains with 10^56 states.
Key insights
- Representing POMDPs as Determinized Sparse Partially Observable Trees (DESPOT) using sampled scenarios drastically reduces computational complexity while maintaining essential information for planning.
- Introducing a regularization term in the objective function effectively mitigates overfitting in Monte Carlo sampling-based online POMDP planning, particularly in environments with large observation spaces, leading to more robust policies.
- An anytime heuristic search, combined with flexible initial bounds and default policies, enables DESPOT to provide near-optimal actions within real-time constraints for practical applications, even with millions of observations and extremely large state spaces.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.