# No Compromise in Solution Quality: Speeding Up Belief-dependent Continuous POMDPs via Adaptive Multilevel Simplification

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

## Key facts

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

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

- [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)
- [An On-Line POMDP Solver for Continuous Observation Spaces](https://mlsanity.com/paper/2011.02076/) (2020)
- [Simplified decision making in the belief space using belief sparsification](https://mlsanity.com/paper/1909.00885/) (2019)
- [iX-BSP: Incremental Belief Space Planning](https://mlsanity.com/paper/2102.09539/) (2021)
- [Nonmyopic Distilled Data Association Belief Space Planning Under Budget Constraints](https://mlsanity.com/paper/2207.08096/) (2022)
- [General Purpose Incremental Covariance Update and Efficient Belief Space Planning via Factor-Graph Propagation Action Tree](https://mlsanity.com/paper/1906.02249/) (2019)
- [Simplified Continuous High Dimensional Belief Space Planning with Adaptive Probabilistic Belief-dependent Constraints](https://mlsanity.com/paper/2302.06697/) (2023)
- [Risk Aware Adaptive Belief-dependent Probabilistically Constrained Continuous POMDP Planning](https://mlsanity.com/paper/2209.02679/) (2022)

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

- [Previous Knowledge Utilization In Online Anytime Belief Space Planning](https://mlsanity.com/paper/2412.13128/) (2024)

## Abstract (arXiv)

Continuous POMDPs with general belief-dependent rewards are notoriously difficult to solve online. In this paper, we present a complete provable theory of adaptive multilevel simplification for the setting of a given externally constructed belief tree and MCTS that constructs the belief tree on the fly using an exploration technique. Our theory allows to accelerate POMDP planning with belief-dependent rewards without any sacrifice in the quality of the obtained solution. We rigorously prove each theoretical claim in the proposed unified theory. Using the general theoretical results, we present three algorithms to accelerate continuous POMDP online planning with belief-dependent rewards. Our two algorithms, SITH-BSP and LAZY-SITH-BSP, can be utilized on top of any method that constructs a belief tree externally. The third algorithm, SITH-PFT, is an anytime MCTS method that permits to plug-in any exploration technique. All our methods are guaranteed to return exactly the same optimal action as their unsimplified equivalents. We replace the costly computation of information-theoretic rewards with novel adaptive upper and lower bounds which we derive in this paper, and are of independent interest. We show that they are easy to calculate and can be tightened by the demand of our algorithms. Our approach is general; namely, any bounds that monotonically converge to the reward can be utilized to achieve significant speedup without any loss in performance. Our theory and algorithms support the challenging setting of continuous states, actions, and observations. The beliefs can be parametric or general and represented by weighted particles. We demonstrate in simulation a significant speedup in planning compared to baseline approaches with guaranteed identical performance.