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

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 nodes has runtime complexity with traditional array-based priority-queues for dense integer keys, the tree-based OPEN list used by MCTS requires , which roughly corresponds to the search depth . In classical planning, is arbitrarily large (e.g., in -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 is inherently limited by the game (e.g., 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 , which achieves amortized 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.