改进蒙特卡洛树搜索,用方差信息提升探索效率。
Variance-Aware Prior-Based Tree Policies for Monte Carlo Tree Search
- 从优化理论出发,推导出带先验的新型搜索策略
- 在多个任务上超越经典PUCT,且不增加计算开销
- 适合研究强化学习规划与高效搜索的开发者
蒙特卡洛树搜索(MCTS)通过结合规划与学习,在长程推理任务中发挥关键作用,如AlphaZero系列算法。其核心是基于上限置信区间(UCT)的搜索策略,而引入先验项的PUCT策略显著提升了探索效率。尽管存在比UCB1理论更优的变体,但将其扩展至带先验的UCT仍具挑战性,因PUCT为经验推导而非源于基础原理。近期工作将MCTS重新解释为正则化策略优化(RPO)问题,为此我们提出逆向RPO(Inverse-RPO),一种系统化方法,可从一类无先验的UCB中导出带先验的UCT。我们将该方法应用于方差感知的UCB-V,得到两种新策略,能融合方差估计进行搜索。实验表明,这些方差感知的先验-UCT在多个基准测试中优于PUCT,且无需额外计算成本。我们还扩展了mctx库以支持方差感知的UCT,代码改动极小,旨在推动基于原则的先验-UCT研究。代码:github.com/Max-We/inverse-rpo。
原文摘要 · Abstract (English)
Monte Carlo Tree Search (MCTS) has profoundly influenced reinforcement learning (RL) by integrating planning and learning in tasks requiring long-horizon reasoning, exemplified by the AlphaZero family of algorithms. Central to MCTS is the search strategy, governed by a tree policy based on an upper confidence bound (UCB) applied to trees (UCT). A key factor in the success of AlphaZero is the introduction of a prior term in the UCB1-based tree policy PUCT, which improves exploration efficiency and thus accelerates training. While many alternative UCBs with stronger theoretical guarantees than UCB1 exist, extending them to prior-based UCTs has been challenging, since PUCT was derived empirically rather than from first principles. Recent work retrospectively justified PUCT by framing MCTS as a regularized policy optimization (RPO) problem. Building on this perspective, we introduce Inverse-RPO, a general methodology that systematically derives prior-based UCTs from a broad class of prior-free UCBs. Applying this method to the variance-aware UCB-V, we obtain two new prior-based tree policies that incorporate variance estimates into the search. Experiments indicate that these variance-aware prior-based UCTs outperform PUCT across multiple benchmarks without incurring additional computational cost. We also provide an extension of the mctx library supporting variance-aware UCTs, showing that the required code changes are minimal and intended to facilitate further research on principled prior-based UCTs. Code: github.com/Max-We/inverse-rpo.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。