# Optimality Guarantees for Particle Belief Approximation of POMDPs

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 43 references that are in the map.
- First posted on arXiv 10 Oct 2022.

## Builds on (most cited first, 10 of 10)

- [DESPOT: Online POMDP Planning with Regularization](https://mlsanity.com/paper/1609.03250/) (2016)
- [Online algorithms for POMDPs with continuous state, action, and observation spaces](https://mlsanity.com/paper/1709.06196/) (2017)
- [Policy Optimization via Importance Sampling](https://mlsanity.com/paper/1809.06098/) (2018)
- [Online Planning Algorithms for POMDPs](https://mlsanity.com/paper/1401.3436/) (2014)
- [Bayesian Optimized Monte Carlo Planning](https://mlsanity.com/paper/2010.03597/) (2020)
- [An On-Line POMDP Solver for Continuous Observation Spaces](https://mlsanity.com/paper/2011.02076/) (2020)
- [Improving Automated Driving through POMDP Planning with Human Internal States](https://mlsanity.com/paper/2005.14549/) (2020)
- [Compositional Learning-based Planning for Vision POMDPs](https://mlsanity.com/paper/2112.09456/) (2021)
- [Sparse tree search optimality guarantees in POMDPs with continuous observation spaces](https://mlsanity.com/paper/1910.04332/) (2019)
- [When is Particle Filtering Efficient for Planning in Partially Observed Linear Dynamical Systems?](https://mlsanity.com/paper/2006.05975/) (2020)

## Built on by (most cited first, 20 of 20)

- [BetaZero: Belief-State Planning for Long-Horizon POMDPs using Learned Approximations](https://mlsanity.com/paper/2306.00249/) (2023)
- [Online POMDP Planning with Anytime Deterministic Optimality Guarantees](https://mlsanity.com/paper/2310.01791/) (2023)
- [Simplifying Complex Observation Models in Continuous POMDP Planning with Probabilistic Guarantees and Practice](https://mlsanity.com/paper/2311.07745/) (2023)
- [Previous Knowledge Utilization In Online Anytime Belief Space Planning](https://mlsanity.com/paper/2412.13128/) (2024)
- [Online Risk-Averse Planning in POMDPs Using Iterated CVaR Value Function](https://mlsanity.com/paper/2601.20554/) (2026)
- [Control Reinforcement Learning: Interpretable Token-Level Steering of LLMs via Sparse Autoencoder Features](https://mlsanity.com/paper/2602.10437/) (2026)
- [Data Association Aware POMDP Planning with Hypothesis Pruning Performance Guarantees](https://mlsanity.com/paper/2303.02139/) (2023)
- [Partially Observable Monte-Carlo Graph Search](https://mlsanity.com/paper/2507.20951/) (2025)
- [Online Robust Planning under Model Uncertainty: A Sample-Based Approach](https://mlsanity.com/paper/2509.10162/) (2025)
- [Active Measuring in Reinforcement Learning With Delayed Negative Effects](https://mlsanity.com/paper/2510.14315/) (2025)
- [SovereignPA-Bench: Evaluating User-Owned Personal Agents under Evolving Intent, Platform Mediation, and Consent Constraints](https://mlsanity.com/paper/2607.05363/) (2026)
- [Factored Online Planning in Many-Agent POMDPs](https://mlsanity.com/paper/2312.11434/) (2023)
- [Belief-State Query Policies for User-Aligned POMDPs](https://mlsanity.com/paper/2405.15907/) (2024)
- [Simplification of Risk Averse POMDPs with Performance Guarantees](https://mlsanity.com/paper/2406.03000/) (2024)
- [Anytime Probabilistically Constrained Provably Convergent Online Belief Space Planning](https://mlsanity.com/paper/2411.06711/) (2024)
- [Action-Gradient Monte Carlo Tree Search for Non-Parametric Continuous (PO)MDPs](https://mlsanity.com/paper/2503.12181/) (2025)
- [Why Goal-Conditioned Reinforcement Learning Works: Relation to Dual Control](https://mlsanity.com/paper/2512.06471/) (2025)
- [Finite-Time Analysis of MCTS in Continuous POMDP Planning](https://mlsanity.com/paper/2605.07703/) (2026)
- [Scalable Rao-Blackwellized Online Planning for High-Dimensional POMDPs](https://mlsanity.com/paper/2609.01351/) (2026)
- [Risk-Averse Online POMDP Planning via CVaR of the Immediate Cost with Performance Guarantees](https://mlsanity.com/paper/2609.35874/) (2026)

## Abstract (arXiv)

Partially observable Markov decision processes (POMDPs) provide a flexible representation for real-world decision and control problems. However, POMDPs are notoriously difficult to solve, especially when the state and observation spaces are continuous or hybrid, which is often the case for physical systems. While recent online sampling-based POMDP algorithms that plan with observation likelihood weighting have shown practical effectiveness, a general theory characterizing the approximation error of the particle filtering techniques that these algorithms use has not previously been proposed. Our main contribution is bounding the error between any POMDP and its corresponding finite sample particle belief MDP (PB-MDP) approximation. This fundamental bridge between PB-MDPs and POMDPs allows us to adapt any sampling-based MDP algorithm to a POMDP by solving the corresponding particle belief MDP, thereby extending the convergence guarantees of the MDP algorithm to the POMDP. Practically, this is implemented by using the particle filter belief transition model as the generative model for the MDP solver. While this requires access to the observation density model from the POMDP, it only increases the transition sampling complexity of the MDP solver by a factor of O(C), where C is the number of particles. Thus, when combined with sparse sampling MDP algorithms, this approach can yield algorithms for POMDPs that have no direct theoretical dependence on the size of the state and observation spaces. In addition to our theoretical contribution, we perform five numerical experiments on benchmark POMDPs to demonstrate that a simple MDP algorithm adapted using PB-MDP approximation, Sparse-PFT, achieves performance competitive with other leading continuous observation POMDP solvers.