# Monte Carlo Tree Search with Boltzmann Exploration

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 37 references that are in the map.
- First posted on arXiv 11 Apr 2024.

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

- [Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor](https://mlsanity.com/paper/1801.01290/) (2018)
- [Reinforcement Learning with Deep Energy-Based Policies](https://mlsanity.com/paper/1702.08165/) (2017)
- [Bridging the Gap Between Value and Policy Based Reinforcement Learning](https://mlsanity.com/paper/1702.08892/) (2017)
- [Accelerating Self-Play Learning in Go](https://mlsanity.com/paper/1902.10565/) (2019)
- [Bandit Algorithms for Tree Search](https://mlsanity.com/paper/1408.2028/) (2014)
- [Credal Networks under Maximum Entropy](https://mlsanity.com/paper/1301.3873/) (2013)
- [Convex Regularization in Monte-Carlo Tree Search](https://mlsanity.com/paper/2007.00391/) (2020)
- [Planning and Learning Using Adaptive Entropy Tree Search](https://mlsanity.com/paper/2102.06808/) (2021)
- [Monte-Carlo Planning: Theoretically Fast Convergence Meets Practical Efficiency](https://mlsanity.com/paper/1309.6828/) (2013)

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

- [SE-Agent: Self-Evolution Trajectory Optimization in Multi-Step Reasoning with LLM-Based Agents](https://mlsanity.com/paper/2508.02085/) (2025)
- [Diffusion Tree Sampling: Scalable inference-time alignment of diffusion models](https://mlsanity.com/paper/2506.20701/) (2025)
- [MALinZero: Efficient Low-Dimensional Search for Mastering Complex Multi-Agent Planning](https://mlsanity.com/paper/2511.06142/) (2025)
- [Generative Actor Critic](https://mlsanity.com/paper/2512.21527/) (2025)
- [Exploration by Random Reward Perturbation](https://mlsanity.com/paper/2506.08737/) (2025)
- [Power Mean Estimation in Stochastic Continuous Monte Carlo Tree Search](https://mlsanity.com/paper/2609.06489/) (2026)
- [Improved Monte Carlo Planning via Causal Disentanglement for Structurally-Decomposed Markov Decision Processes](https://mlsanity.com/paper/2406.16151/) (2024)
- [Doubly Robust Monte Carlo Tree Search](https://mlsanity.com/paper/2502.01672/) (2025)
- [Neural Architecture Search by Learning a Hierarchical Search Space](https://mlsanity.com/paper/2503.21061/) (2025)
- [Online Navigation Planning for Long-term Autonomous Operation of Underwater Gliders](https://mlsanity.com/paper/2602.19315/) (2026)
- [Boltzmann-based Exploration for Robust Decentralized Multi-Agent Planning (Extended Version)](https://mlsanity.com/paper/2603.02154/) (2026)
- [Variance Driven Exploration: A Provable and Efficient Methodology for Pure Exploration in Highly Stochastic Environments](https://mlsanity.com/paper/2608.21995/) (2026)

## Abstract (arXiv)

Monte-Carlo Tree Search (MCTS) methods, such as Upper Confidence Bound applied to Trees (UCT), are instrumental to automated planning techniques. However, UCT can be slow to explore an optimal action when it initially appears inferior to other actions. Maximum ENtropy Tree-Search (MENTS) incorporates the maximum entropy principle into an MCTS approach, utilising Boltzmann policies to sample actions, naturally encouraging more exploration. In this paper, we highlight a major limitation of MENTS: optimal actions for the maximum entropy objective do not necessarily correspond to optimal actions for the original objective. We introduce two algorithms, Boltzmann Tree Search (BTS) and Decaying ENtropy Tree-Search (DENTS), that address these limitations and preserve the benefits of Boltzmann policies, such as allowing actions to be sampled faster by using the Alias method. Our empirical analysis shows that our algorithms show consistent high performance across several benchmark domains, including the game of Go.