# Simplified Belief-Dependent Reward MCTS Planning with Guaranteed Tree Consistency

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 15 references that are in the map.
- First posted on arXiv 29 May 2021.

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

- [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)
- [Simplified decision making in the belief space using belief sparsification](https://mlsanity.com/paper/1909.00885/) (2019)
- [Multilevel Monte-Carlo for Solving POMDPs Online](https://mlsanity.com/paper/1907.09673/) (2019)
- [Online POMDP Planning via Simplification](https://mlsanity.com/paper/2105.05296/) (2021)
- [Probabilistic Loss and its Online Characterization for Simplified Decision Making Under Uncertainty](https://mlsanity.com/paper/2105.05789/) (2021)

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

- [Monte Carlo Planning with Large Language Model for Text-Based Game Agents](https://mlsanity.com/paper/2504.16855/) (2025)
- [Adaptive Information Belief Space Planning](https://mlsanity.com/paper/2201.05673/) (2022)
- [Nonmyopic Distilled Data Association Belief Space Planning Under Budget Constraints](https://mlsanity.com/paper/2207.08096/) (2022)
- [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)
- [Data Association Aware POMDP Planning with Hypothesis Pruning Performance Guarantees](https://mlsanity.com/paper/2303.02139/) (2023)

## Abstract (arXiv)

Partially Observable Markov Decision Processes (POMDPs) are notoriously hard to solve. Most advanced state-of-the-art online solvers leverage ideas of Monte Carlo Tree Search (MCTS). These solvers rapidly converge to the most promising branches of the belief tree, avoiding the suboptimal sections. Most of these algorithms are designed to utilize straightforward access to the state reward and assume the belief-dependent reward is nothing but expectation over the state reward. Thus, they are inapplicable to a more general and essential setting of belief-dependent rewards. One example of such reward is differential entropy approximated using a set of weighted particles of the belief. Such an information-theoretic reward introduces a significant computational burden. In this paper, we embed the paradigm of simplification into the MCTS algorithm. In particular, we present Simplified Information-Theoretic Particle Filter Tree (SITH-PFT), a novel variant to the MCTS algorithm that considers information-theoretic rewards but avoids the need to calculate them completely. We replace the costly calculation of information-theoretic rewards with adaptive upper and lower bounds. These bounds are easy to calculate and tightened only by the demand of our algorithm. Crucially, we guarantee precisely the same belief tree and solution that would be obtained by MCTS, which explicitly calculates the original information-theoretic rewards. Our approach is general; namely, any converging to the reward bounds can be easily plugged-in to achieve substantial speedup without any loss in performance.