# Scale-Adaptive Balancing of Exploration and Exploitation in Classical Planning

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 67 references that are in the map.
- First posted on arXiv 16 May 2023.

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

- [Simple Bayesian Algorithms for Best Arm Identification](https://mlsanity.com/paper/1602.08448/) (2016)
- [Learning Domain-Independent Planning Heuristics with Hypergraph Networks](https://mlsanity.com/paper/1911.13101/) (2019)
- [Generalized Planning With Deep Reinforcement Learning](https://mlsanity.com/paper/2005.02305/) (2020)
- [Action Schema Networks: Generalised Policies with Deep Learning](https://mlsanity.com/paper/1709.04271/) (2017)
- [Bandit Algorithms for Tree Search](https://mlsanity.com/paper/1408.2028/) (2014)
- [Learning to Rank for Synthesizing Planning Heuristics](https://mlsanity.com/paper/1608.01302/) (2016)
- [Reinforcement Learning for Classical Planning: Viewing Heuristics as Dense Reward Generators](https://mlsanity.com/paper/2109.14830/) (2021)

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

- [Extreme Value Monte Carlo Tree Search for Classical Planning](https://mlsanity.com/paper/2405.18248/) (2024)
- [Bilevel MCTS for Amortized O(1) Node Selection in Classical Planning](https://mlsanity.com/paper/2508.08385/) (2025)
- [Handling Infinite Domain Parameters in Planning Through Best-First Search with Delayed Partial Expansions](https://mlsanity.com/paper/2509.03953/) (2025)
- [Variance-Aware Prior-Based Tree Policies for Monte Carlo Tree Search](https://mlsanity.com/paper/2512.21648/) (2025)

## Abstract (arXiv)

Balancing exploration and exploitation has been an important problem in both game tree search and automated planning. However, while the problem has been extensively analyzed within the Multi-Armed Bandit (MAB) literature, the planning community has had limited success when attempting to apply those results. We show that a more detailed theoretical understanding of MAB literature helps improve existing planning algorithms that are based on Monte Carlo Tree Search (MCTS) / Trial Based Heuristic Tree Search (THTS). In particular, THTS uses UCB1 MAB algorithms in an ad hoc manner, as UCB1's theoretical requirement of fixed bounded support reward distributions is not satisfied within heuristic search for classical planning. The core issue lies in UCB1's lack of adaptations to the different scales of the rewards. We propose GreedyUCT-Normal, a MCTS/THTS algorithm with UCB1-Normal bandit for agile classical planning, which handles distributions with different scales by taking the reward variance into consideration, and resulted in an improved algorithmic performance (more plans found with less node expansions) that outperforms Greedy Best First Search and existing MCTS/THTS-based algorithms (GreedyUCT,GreedyUCT*).