# Bilevel MCTS for Amortized O(1) Node Selection in Classical Planning

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 2 of its 32 references that are in the map.
- First posted on arXiv 11 Aug 2025.

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

- [Approximate Novelty Search](https://mlsanity.com/paper/2105.07691/) (2021)
- [Scale-Adaptive Balancing of Exploration and Exploitation in Classical Planning](https://mlsanity.com/paper/2305.09840/) (2023)

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

- [When LLM Meets Tree Search: A Systematic View of Inference as Search in Large Language Models](https://mlsanity.com/paper/2608.30395/) (2026)

## Abstract (arXiv)

We study an efficient implementation of Multi-Armed Bandit (MAB)-based Monte-Carlo Tree Search (MCTS) for classical planning. One weakness of MCTS is that it spends a significant time deciding which node to expand next. While selecting a node from an OPEN list with N nodes has O(1) runtime complexity with traditional array-based priority-queues for dense integer keys, the tree-based OPEN list used by MCTS requires O(log N), which roughly corresponds to the search depth d. In classical planning, d is arbitrarily large (e.g., 2k-1 in k-disk Tower-of-Hanoi) and the runtime for node selection is significant, unlike in game tree search, where the cost is negligible compared to the node evaluation (rollouts) because d is inherently limited by the game (e.g., d≤ 361 in Go). To improve this bottleneck, we propose a bilevel modification to MCTS that runs a best-first search from each selected leaf node with an expansion budget proportional to d, which achieves amortized O(1) runtime for node selection, equivalent to the traditional queue-based OPEN list. In addition, we introduce Tree Collapsing, an enhancement that reduces action selection steps and further improves the performance.