# Monte-Carlo Planning: Theoretically Fast Convergence Meets Practical Efficiency

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Sep 2013.

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

- [Generalised Policy Improvement with Geometric Policy Composition](https://mlsanity.com/paper/2206.08736/) (2022)
- [Monte Carlo Tree Search with Boltzmann Exploration](https://mlsanity.com/paper/2404.07732/) (2024)

## Abstract (arXiv)

Popular Monte-Carlo tree search (MCTS) algorithms for online planning, such as epsilon-greedy tree search and UCT, aim at rapidly identifying a reasonably good action, but provide rather poor worst-case guarantees on performance improvement over time. In contrast, a recently introduced MCTS algorithm BRUE guarantees exponential-rate improvement over time, yet it is not geared towards identifying reasonably good choices right at the go. We take a stand on the individual strengths of these two classes of algorithms, and show how they can be effectively connected. We then rationalize a principle of "selective tree expansion", and suggest a concrete implementation of this principle within MCTS. The resulting algorithm,s favorably compete with other MCTS algorithms under short planning times, while preserving the attractive convergence properties of BRUE.