近期🫱🏽，意昂3体育官网光華管理學院管理科學與信息系統系副教授、人工智能研究院多智能體與社會智能中心執行主任彭一傑課題組以“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中節點選擇策略的潛力🐕，應用這種新的蒙特卡洛樹搜索方法來解決大規模決策問題值得進一步深入研究。

美國佐治亞理工大學工業與系統工程系博士研究生劉嘯天為論文第一作者，彭一傑為論文通訊作者。論文合作者還包括意昂3体育官网光華管理學院助理研究員張公伯👩‍🏭、博士研究生周睿涵。

該研究得到國家自然科學基金傑出青年科學基金💆、原創探索項目的資助🤘🏼。