彭一杰课题组提出一种解决大规模决策问题的高效蒙特卡洛树节点选择策略

　　

近期，北京大学光华管理学院管理科学与信息系统系副教授、人工智能研究院多智能体与社会智能中心执行主任彭一杰课题组以“An Efficient Node Selection Policy for Monte Carlo Tree Search with Neural Networks”为题的文章被运筹与管理科学领域高水平期刊Informs Journal of Computing接受。

近年来，智慧化运营管理、制造业及机器人控制等领域正面临着日益增多的大规模决策挑战。这些挑战的核心在于如何在庞大的动作空间中精确地识别出最优行动方案，这对于多数传统的基于规则的搜索方法而言，其计算复杂度往往极高。蒙特卡洛树搜索（Monte Carlo Tree Search，MCTS），作为一种融合了蒙特卡洛仿真的随机性与树搜索精确性的高效算法，能够有效处理复杂且大规模决策的问题，并在自动驾驶、计算机游戏及组合优化问题等多个领域展现出了其独特的优势与潜力。人工智能领域AlphaGo的成功引领了一种新趋势，即在MCTS中融入价值网络和策略网络，以进一步提升算法的性能。

图1. 蒙特卡洛树搜索

MCTS本质上是一个黑箱系统仿真优化问题。在经典的MCTS中，节点选择策略采用置信上界树（Upper Confidence Bounds applied to Trees，UCT）算法，该策略能够有效平衡节点选择中的探索与开发。然而，用于推导UCT算法的多臂老虎机问题与MCTS问题的框架存在差异，且该算法未能充分利用仿真抽样过程中获得的信息。本研究将蒙特卡洛树搜索中的节点选择问题建模为多阶段的排序与选择（Ranking and Selection，R&S）问题，该框架与蒙特卡洛树搜索问题更加契合。本研究将用于求解排序与选择问题的渐近最优仿真资源分配策略扩展为一种用于树搜索的节点选择策略。该策略通过平衡行动值与方差，能够高效地分配有限的仿真资源，以最大化正确选择最优行动的概率。进一步地，本研究将价值神经网络与策略神经网络融入所提出的节点选择策略中，分别为算法提供了先验信息与最优行动识别信息，从而进一步提升策略的表现。

图2. 在井字棋下的实验结果

图3. 在五子棋下的实验结果

图4. 在强化学习倒立摆环境中的实验结果

本文将所提出的算法应用于井字棋和五子棋计算机游戏中。数值结果表明，在不结合任何神经网络信息的情况下，与经典的UCT策略相比，该算法能够显著提升正确识别最优行动的概率；在结合神经网络信息后，该算法在游戏对弈中比AlphaGo Zero中使用的UCT策略具有更高的获胜率。此外，在OpenAI倒立摆环境测试中，该算法相比于MuZero中使用的UCT策略，在相同的迭代次数下能够获得更高的游戏得分。进一步地，本文通过数值测试分别验证了价值网络与策略网络在提升算法表现方面的效果。这项研究揭示了将动态仿真资源分配策略扩展为MCTS中节点选择策略的潜力，应用这种新的蒙特卡洛树搜索方法来解决大规模决策问题值得进一步深入研究。

美国佐治亚理工大学工业与系统工程系博士研究生刘啸天为论文第一作者，彭一杰为论文通讯作者。论文合作者还包括北京大学光华管理学院助理研究员张公伯、博士研究生周睿涵。

该研究得到国家自然科学基金杰出青年科学基金、原创探索项目的资助。