# Extreme Value Monte Carlo Tree Search for Classical Planning

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 4 of its 59 references that are in the map.
- First posted on arXiv 28 May 2024.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

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

- [On Using Admissible Bounds for Learning Forward Search Heuristics](https://mlsanity.com/paper/2308.11905/) (2023)
- [An Asymptotically Optimal Policy for Uniform Bandits of Unknown Support](https://mlsanity.com/paper/1505.01918/) (2015)
- [Scale-Adaptive Balancing of Exploration and Exploitation in Classical Planning](https://mlsanity.com/paper/2305.09840/) (2023)
- [Materials Discovery using Max K-Armed Bandit](https://mlsanity.com/paper/2212.08225/) (2022)

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

- [Variance-Aware Prior-Based Tree Policies for Monte Carlo Tree Search](https://mlsanity.com/paper/2512.21648/) (2025)

## Abstract (arXiv)

Despite being successful in board games and reinforcement learning (RL), Monte Carlo Tree Search (MCTS) combined with Multi Armed Bandits (MABs) has seen limited success in domain-independent classical planning until recently. Previous work (Wissow and Asai 2024) showed that UCB1, designed for bounded rewards, does not perform well as applied to cost-to-go estimates in classical planning, which are unbounded in R, and showed improved performance using a Gaussian reward MAB instead. This paper further sharpens our understanding of ideal bandits for planning tasks. Existing work has two issues: first, Gaussian MABs under-specify the support of cost-to-go estimates as (-∞,∞), which we can narrow down. Second, Full Bellman backup (Schulte and Keller 2014), which backpropagates sample max/min, lacks theoretical justification. We use Peaks-Over-Threashold Extreme Value Theory to resolve both issues at once, and propose a new bandit algorithm (UCB1-Uniform). We formally prove its regret bound and empirically demonstrate its performance in classical planning.