提出双层MCTS，实现经典规划中节点选择的均摊常数时间
Bilevel MCTS for Amortized O(1) Node Selection in Classical Planning
- 设计双层结构，在每轮选择后进行预算控制的局部最佳优先搜索
- 节点选择时间从O(log N)降为均摊O(1)，适用于深度无界的经典规划问题
- 适合大规模状态空间下的经典规划任务，如汉诺塔等复杂路径搜索
我们研究了基于多臂老虎机（MAB）的蒙特卡洛树搜索（MCTS）在经典规划中的高效实现。传统MCTS在选择下一个扩展节点时耗时显著，因其使用基于树的OPEN列表，时间复杂度为O(log N)，约等于搜索深度d。而在经典规划中，深度d可任意大（如k盘汉诺塔中d=2^k−1），该开销不可忽视；相比之下，博弈树搜索中深度受游戏限制（如围棋中d≤361），节点选择成本可忽略。为此，我们提出一种双层MCTS改进方法：从每个选中的叶节点出发，执行预算与深度成比例的局部最佳优先搜索，实现节点选择的均摊O(1)复杂度，等效于传统队列式OPEN列表。此外，引入树压缩技术，减少动作选择步骤，进一步提升性能。
原文摘要 · Abstract (English)
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., $2^k-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\leq 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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。