# Online POMDP Planning with Anytime Deterministic Optimality Guarantees

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 16 references that are in the map.
- First posted on arXiv 3 Oct 2023.

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

- [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)
- [Optimality Guarantees for Particle Belief Approximation of POMDPs](https://mlsanity.com/paper/2210.05015/) (2022)
- [An On-Line POMDP Solver for Continuous Observation Spaces](https://mlsanity.com/paper/2011.02076/) (2020)
- [Sparse tree search optimality guarantees in POMDPs with continuous observation spaces](https://mlsanity.com/paper/1910.04332/) (2019)

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

- [SovereignPA-Bench: Evaluating User-Owned Personal Agents under Evolving Intent, Platform Mediation, and Consent Constraints](https://mlsanity.com/paper/2607.05363/) (2026)
- [Finite-Time Analysis of MCTS in Continuous POMDP Planning](https://mlsanity.com/paper/2605.07703/) (2026)
- [Scalable Robust MCTS with Anytime Deterministic Optimality Guarantees](https://mlsanity.com/paper/2610.15461/) (2026)

## Abstract (arXiv)

Decision-making under uncertainty is a critical aspect of many practical autonomous systems due to incomplete information. Partially Observable Markov Decision Processes (POMDPs) offer a mathematically principled framework for formulating decision-making problems under such conditions. However, finding an optimal solution for a POMDP is generally intractable. In recent years, there has been a significant progress of scaling approximate solvers from small to moderately sized problems, using online tree search solvers. Often, such approximate solvers are limited to probabilistic or asymptotic guarantees towards the optimal solution. In this paper, we derive a deterministic relationship for discrete POMDPs between an approximated and the optimal solution. We show that at any time, we can derive bounds that relate between the existing solution and the optimal one. We show that our derivations provide an avenue for a new set of algorithms and can be attached to existing algorithms that have a certain structure to provide them with deterministic guarantees with marginal computational overhead. In return, not only do we certify the solution quality, but we demonstrate that making a decision based on the deterministic guarantee may result in superior performance compared to the original algorithm without the deterministic certification.