# Adaptive Discretization using Voronoi Trees for Continuous POMDPs

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 43 references that are in the map.
- First posted on arXiv 21 Feb 2023.

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

- [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)
- [Partially Observable Markov Decision Processes (POMDPs) and Robotics](https://mlsanity.com/paper/2107.07599/) (2021)
- [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)
- [Zooming for Efficient Model-Free Reinforcement Learning in Metric Spaces](https://mlsanity.com/paper/2003.04069/) (2020)
- [Adaptive Discretization using Voronoi Trees for Continuous-Action POMDPs](https://mlsanity.com/paper/2209.05733/) (2022)

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

- [Efficient Monte Carlo Tree Search via On-the-Fly State-Conditioned Action Abstraction](https://mlsanity.com/paper/2406.00614/) (2024)
- [AUPO -- Abstracted Until Proven Otherwise: A Reward Distribution Based Abstraction Algorithm](https://mlsanity.com/paper/2510.23214/) (2025)
- [Investigating Intra-Abstraction Policies For Non-exact Abstraction Algorithms](https://mlsanity.com/paper/2510.24297/) (2025)
- [Action-Gradient Monte Carlo Tree Search for Non-Parametric Continuous (PO)MDPs](https://mlsanity.com/paper/2503.12181/) (2025)
- [Discovering State Equivalences in UCT Search Trees By Action Pruning](https://mlsanity.com/paper/2510.26346/) (2025)
- [Finite-Time Analysis of MCTS in Continuous POMDP Planning](https://mlsanity.com/paper/2605.07703/) (2026)

## Abstract (arXiv)

Solving continuous Partially Observable Markov Decision Processes (POMDPs) is challenging, particularly for high-dimensional continuous action spaces. To alleviate this difficulty, we propose a new sampling-based online POMDP solver, called Adaptive Discretization using Voronoi Trees (ADVT). It uses Monte Carlo Tree Search in combination with an adaptive discretization of the action space as well as optimistic optimization to efficiently sample high-dimensional continuous action spaces and compute the best action to perform. Specifically, we adaptively discretize the action space for each sampled belief using a hierarchical partition called Voronoi tree, which is a Binary Space Partitioning that implicitly maintains the partition of a cell as the Voronoi diagram of two points sampled from the cell. ADVT uses the estimated diameters of the cells to form an upper-confidence bound on the action value function within the cell, guiding the Monte Carlo Tree Search expansion and further discretization of the action space. This enables ADVT to better exploit local information with respect to the action value function, allowing faster identification of the most promising regions in the action space, compared to existing solvers. Voronoi trees keep the cost of partitioning and estimating the diameter of each cell low, even in high-dimensional spaces where many sampled points are required to cover the space well. ADVT additionally handles continuous observation spaces, by adopting an observation progressive widening strategy, along with a weighted particle representation of beliefs. Experimental results indicate that ADVT scales substantially better to high-dimensional continuous action spaces, compared to state-of-the-art methods.