# Monte Carlo Tree Search in the Presence of Transition Uncertainty

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 27 references that are in the map.
- First posted on arXiv 18 Dec 2023.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [When to Trust Your Model: Model-Based Policy Optimization](https://mlsanity.com/paper/1906.08253/) (2019)
- [Sample-Efficient Reinforcement Learning with Stochastic Ensemble Value Expansion](https://mlsanity.com/paper/1807.01675/) (2018)
- [Safe Reinforcement Learning with Model Uncertainty Estimates](https://mlsanity.com/paper/1810.08700/) (2018)
- [Self-Correcting Models for Model-Based Reinforcement Learning](https://mlsanity.com/paper/1612.06018/) (2016)
- [Learning to Combat Compounding-Error in Model-Based Reinforcement Learning](https://mlsanity.com/paper/1912.11206/) (2019)
- [Bidirectional Model-based Policy Optimization](https://mlsanity.com/paper/2007.01995/) (2020)
- [Mitigating Value Hallucination in Dyna Planning via Multistep Predecessor Models](https://mlsanity.com/paper/2006.04363/) (2020)
- [CMAX++ : Leveraging Experience in Planning and Execution using Inaccurate Models](https://mlsanity.com/paper/2009.09942/) (2020)
- [HEX and Neurodynamic Programming](https://mlsanity.com/paper/2008.06359/) (2020)

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

- [Online Robust Planning under Model Uncertainty: A Sample-Based Approach](https://mlsanity.com/paper/2509.10162/) (2025)
- [DyRo-MCTS: A Robust Monte Carlo Tree Search Approach to Dynamic Job Shop Scheduling](https://mlsanity.com/paper/2509.21902/) (2025)
- [UC-Search: Risk-Aware Test-Time Search for Delayed Constrained Time-Series Control](https://mlsanity.com/paper/2606.25274/) (2026)
- [Scalable Robust MCTS with Anytime Deterministic Optimality Guarantees](https://mlsanity.com/paper/2610.15461/) (2026)

## Abstract (arXiv)

Monte Carlo Tree Search (MCTS) is an immensely popular search-based framework used for decision making. It is traditionally applied to domains where a perfect simulation model of the environment is available. We study and improve MCTS in the context where the environment model is given but imperfect. We show that the discrepancy between the model and the actual environment can lead to significant performance degradation with standard MCTS. We therefore develop Uncertainty Adapted MCTS (UA-MCTS), a more robust algorithm within the MCTS framework. We estimate the transition uncertainty in the given model, and direct the search towards more certain transitions in the state space. We modify all four MCTS phases to improve the search behavior by considering these estimates. We prove, in the corrupted bandit case, that adding uncertainty information to adapt UCB leads to tighter regret bound than standard UCB. Empirically, we evaluate UA-MCTS and its individual components on the deterministic domains from the MinAtar test suite. Our results demonstrate that UA-MCTS strongly improves MCTS in the presence of model transition errors.