# The Second Type of Uncertainty in Monte Carlo Tree Search

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 May 2020.

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

- [Investigating Scale Independent UCT Exploration Factor Strategies](https://mlsanity.com/paper/2510.21275/) (2025)
- [Amplifying Exploration in Monte-Carlo Tree Search by Focusing on the Unknown](https://mlsanity.com/paper/2402.08511/) (2024)

## Abstract (arXiv)

Monte Carlo Tree Search (MCTS) efficiently balances exploration and exploitation in tree search based on count-derived uncertainty. However, these local visit counts ignore a second type of uncertainty induced by the size of the subtree below an action. We first show how, due to the lack of this second uncertainty type, MCTS may completely fail in well-known sparse exploration problems, known from the reinforcement learning community. We then introduce a new algorithm, which estimates the size of the subtree below an action, and leverages this information in the UCB formula to better direct exploration. Subsequently, we generalize these ideas by showing that loops, i.e., the repeated occurrence of (approximately) the same state in the same trace, are actually a special case of subtree depth variation. Testing on a variety of tasks shows that our algorithms increase sample efficiency, especially when the planning budget per timestep is small.