# Finite-Time Analysis of MCTS in Continuous POMDP Planning

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 16 references that are in the map.
- First posted on arXiv 8 May 2026.

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

- [Monte Carlo Tree Search: A Review of Recent Modifications and Applications](https://mlsanity.com/paper/2103.04931/) (2021)
- [Partially Observable Markov Decision Processes in Robotics: A Survey](https://mlsanity.com/paper/2209.10342/) (2022)
- [Online algorithms for POMDPs with continuous state, action, and observation spaces](https://mlsanity.com/paper/1709.06196/) (2017)
- [Partially Observable Markov Decision Processes (POMDPs) and Robotics](https://mlsanity.com/paper/2107.07599/) (2021)
- [Optimality Guarantees for Particle Belief Approximation of POMDPs](https://mlsanity.com/paper/2210.05015/) (2022)
- [A Unified Perspective on Value Backup and Exploration in Monte-Carlo Tree Search](https://mlsanity.com/paper/2202.07071/) (2022)
- [Adaptive Discretization using Voronoi Trees for Continuous POMDPs](https://mlsanity.com/paper/2302.10439/) (2023)
- [Online POMDP Planning with Anytime Deterministic Optimality Guarantees](https://mlsanity.com/paper/2310.01791/) (2023)
- [On the Convergence Rate of MCTS for the Optimal Value Estimation in Markov Decision Processes](https://mlsanity.com/paper/2402.07063/) (2024)

## Abstract (arXiv)

This paper presents a finite-time analysis for Monte Carlo Tree Search (MCTS) in Partially Observable Markov Decision Processes (POMDPs), with probabilistic concentration bounds in both discrete and continuous observation spaces. While MCTS-style solvers such as POMCP achieve empirical success in many applications, rigorous finite-time guarantees remain an open problem due to the nonstationarity and the interdependencies induced by heuristic action selection (e.g., UCB). In the discrete setting, we address these challenges by extending the polynomial exploration bonus to UCB in POMDP setting, yielding polynomial concentration bounds for the empirical value estimation at the root node. For continuous observation spaces, we introduce an abstract partitioning framework and propose a finite-time bound on partitioning loss. Under mild conditions, we prove highprobability bound on value estimates in POMDPs with continuous observation space. Specifically, we propose Voro-POMCPOW, a variant of POMCPOW with f inite-time guarantees that adaptively partitions the continuous observation space using Voronoi cells. This approach maintains a finite branching factor while preserving the original observation generator. Empirical validation demonstrates that the proposed Voro-POMCPOW shows competitive performance while providing theoretical guarantees. Although our analysis focuses on continuous POMDPs, the techniques developed herein are also applicable to continuous MDPs, closing another gap on the MDP side.