# Online Planning Algorithms for POMDPs

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

## Key facts

- Cited by 45 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jan 2014.

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

- [A Survey of Uncertainty in Deep Neural Networks](https://mlsanity.com/paper/2107.03342/) (2021)
- [Partially Observable Markov Decision Processes in Robotics: A Survey](https://mlsanity.com/paper/2209.10342/) (2022)
- [Efficient Sampling-Based Maximum Entropy Inverse Reinforcement Learning with Application to Autonomous Driving](https://mlsanity.com/paper/2006.13704/) (2020)
- [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)
- [Learning Belief Representations for Imitation Learning in POMDPs](https://mlsanity.com/paper/1906.09510/) (2019)
- [Optimality Guarantees for Particle Belief Approximation of POMDPs](https://mlsanity.com/paper/2210.05015/) (2022)
- [A Survey on Active Feature Acquisition Strategies](https://mlsanity.com/paper/2502.11067/) (2025)
- [Solving Common-Payoff Games with Approximate Policy Iteration](https://mlsanity.com/paper/2101.04237/) (2021)
- [Self-Adaptive Driving in Nonstationary Environments through Conjectural Online Lookahead Adaptation](https://mlsanity.com/paper/2210.03209/) (2022)
- [Learned Belief Search: Efficiently Improving Policies in Partially Observable Settings](https://mlsanity.com/paper/2106.09086/) (2021)
- [Provable Representation with Efficient Planning for Partial Observable Reinforcement Learning](https://mlsanity.com/paper/2311.12244/) (2023)
- [Continuous Relaxation of Symbolic Planner for One-Shot Imitation Learning](https://mlsanity.com/paper/1908.06769/) (2019)
- [Safe POMDP Online Planning via Shielding](https://mlsanity.com/paper/2309.10216/) (2023)
- [Online Planning for Constrained POMDPs with Continuous Spaces through Dual Ascent](https://mlsanity.com/paper/2212.12154/) (2022)
- [A Mathematical Characterization of Minimally Sufficient Robot Brains](https://mlsanity.com/paper/2308.09041/) (2023)
- [Weathering Ongoing Uncertainty: Learning and Planning in a Time-Varying Partially Observable Environment](https://mlsanity.com/paper/2312.03263/) (2023)
- [Sequential Monte Carlo for Policy Optimization in Continuous POMDPs](https://mlsanity.com/paper/2505.16732/) (2025)
- [Human-Centric Resource Allocation for the Metaverse With Multiaccess Edge Computing](https://mlsanity.com/paper/2312.15313/) (2023)
- [To Distill or Decide? Understanding the Algorithmic Trade-off in Partially Observable Reinforcement Learning](https://mlsanity.com/paper/2510.03207/) (2025)
- [Stochastic Optimization for Vaccine and Testing Kit Allocation for the COVID-19 Pandemic](https://mlsanity.com/paper/2101.01204/) (2021)
- [Active Inference Tree Search in Large POMDPs](https://mlsanity.com/paper/2103.13860/) (2021)
- [A Bayesian Approach to Identifying Representational Errors](https://mlsanity.com/paper/2103.15171/) (2021)
- [Rollout Heuristics for Online Stochastic Contingent Planning](https://mlsanity.com/paper/2310.02345/) (2023)
- [Towards Cost Sensitive Decision Making](https://mlsanity.com/paper/2410.03892/) (2024)
- [Deep Belief Markov Models for POMDP Inference](https://mlsanity.com/paper/2503.13438/) (2025)
- [Observation Adaptation via Annealed Importance Resampling for Partially Observable Markov Decision Processes](https://mlsanity.com/paper/2503.19302/) (2025)
- [Compositional shield synthesis for safe reinforcement learning in partial observability](https://mlsanity.com/paper/2509.12085/) (2025)
- [Uncertainty Maximization in Partially Observable Domains: A Cognitive Perspective](https://mlsanity.com/paper/2102.11232/) (2021)
- [Who's in Charge? Roles and Responsibilities of Decision-Making Components in Conversational Robots](https://mlsanity.com/paper/2303.08470/) (2023)

## Abstract (arXiv)

Partially Observable Markov Decision Processes (POMDPs) provide a rich framework for sequential decision-making under uncertainty in stochastic domains. However, solving a POMDP is often intractable except for small problems due to their complexity. Here, we focus on online approaches that alleviate the computational complexity by computing good local policies at each decision step during the execution. Online algorithms generally consist of a lookahead search to find the best action to execute at each time step in an environment. Our objectives here are to survey the various existing online POMDP methods, analyze their properties and discuss their advantages and disadvantages; and to thoroughly evaluate these online approaches in different environments under various metrics (return, error bound reduction, lower bound improvement). Our experimental results indicate that state-of-the-art online heuristic search methods can handle large POMDP domains efficiently.