給定預算下基于相對熵置信區間的蒙特卡洛樹搜索最優動作識別算法

劉郭慶 錢宇華 張亞宇 王婕婷

（山西大學大數據科學與產業研究院 太原 030006）

（計算智能與中文信息處理教育部重點實驗室（山西大學）太原 030006）

（山西大學計算機與信息技術學院 太原 030006）（guoqingl1001@163.com）

現有多數人工智能算法是通過自上而下的人為設計在有限的環境中實現特定機制或解決特定問題，不能很好地適應任務交叉復雜、場景未知多變的現實環境.針對這一困境，以“最大化獎勵，自適應學習”為原則的強化學習被視為一個有效途徑.強化學習[1-2]通過與環境交互得到反饋進行優化，無需提前標注數據和探索數據結構，因此能夠更加適應任務和需求多變的開放人工智能場景，被視為開放環境下最具前景的方法之一.然而現有的強化學習算法仍然面臨許多挑戰：1）泛化性不足，即強化學習算法對環境變化的健壯性和在部署過程中的適應性仍需加強；2）可解釋性不足，即對模型設計者和使用者而言，模型所學知識、模型內部邏輯等關鍵信息尚不明晰；3）指導性不足，即對任務場景的影響因素和的內在機理的研究較淺.為了應對這3個挑戰，亟需從理論角度對強化學習領域中的重要算法以及模型進行分析.

自Kocsis 和Szepesv′ari以及Coulom[3-4]提出蒙特卡洛樹搜索（Monte Carlo tree search , MCTS）后，MCTS作為一種典型的強化學習模型，其在樹結構表示的組合空間中通過啟發式搜索進行連續決策.后續工作通過引入領域知識或結合其他技術對特定問題進行處理，已經在化學合成[5]、組合優化[6]、規劃調度[7-8]和機器翻譯[9]等領域得到了成功的應用.其中最為矚目的進展是AlphaGo[10]首次擊敗了人類圍棋冠軍和其他圍棋程序，被認為是人工智能的里程碑式突破.隨后Alpha Zero[11]從白板狀態起步，實現了在國際象棋、圍棋和將棋3個領域超越人類專家和其他程序的水平，MuZero[12]在多個不相關任務上實現超越人類的水平，為創造通用人工智能甚至理解智能本身提供了可能性.

MCTS基于樹結構構建問題模型，其中節點表示狀態，邊表示從一個狀態到另一個狀態的動作.其面臨的主要問題是在當前狀態下，玩家如何在眾多可行動作中選擇出最優動作以確保獲勝.MCTS主要包含4個流程：選擇（從根節點開始，根據給定的搜索策略遞歸地選擇子節點，直至葉子節點停止）、擴展（對非終止節點的葉子節點創建一個或者更多的子節點）、模擬（對擴展的子節點通過蒙特卡洛方法進行模擬得到估計值，直至終止節點停止）和回溯（根據模擬結果更新擴展節點到根節點這一路徑上的節點估值）.重復進行這4個流程，當算法停止后選擇當前狀態下價值最高的邊對應的狀態作為輸出.然而在現實場景中，基于實際任務構建的樹結構往往具有巨大的搜索空間，但由于計算資源匱乏或者計算成本高等原因，完全充分地對樹結構進行搜索是難以實現的，因此在有限的預算下高效合理地分配計算資源從而獲得當前狀態下的最優動作是目前研究的一個重要思路.

由于2名玩家、完全信息、零和博弈是MCTS模型體系中一個基礎且重要的場景，因此，本文基于該場景對上述問題進行分析，在第2節中提出了抽象模型——極小極大采樣樹（minimax sampling tree, MST）模型并對樹模型中的相關概念定義了數學表示，給出了固定預算下最優動作識別問題的算法目標.在第3節中，構造了包含葉子節點勝率估計、第1層節點值估計、最優節點選擇3個部分的MST最優動作識別算法DLU （relative entropy confidence interval based pure exploration）.該算法首先基于相對熵構建了節點估值區間，以對葉子節點勝率進行更加準確地評估，進而從根本上提升算法的準確性；然后進行估值區間上傳；最后給出了最優節點選擇策略.在第4節中，基于DLU算法推導了輸出動作的誤差上界，從理論角度給出了算法誤差的相關影響因素.在第5節中，在人造樹模型和井字棋2種場景下對算法性能進行驗證分析.實驗結果表明，在固定預算設定下，所提出的基于相對熵置信區間的最優動作識別算法類在低預算時具有更好的性能表現，且模型越復雜識別難度越高時，該算法類的性能優勢越顯著.同時，在井字棋博弈場景下，將DLU算法與已知具有理論保證的最優算法進行比較，可以看出DLU算法能有效識別最優動作.同時，DLU算法具有快速選擇采樣節點的策略，從而降低時間消耗.

1 相關工作

高效的MCTS選擇策略的目的是在探索（未經過充分測試的行動）和利用（迄今為止確定的最佳行動）之間保持適當的平衡，已有很多學者對其進行了全面深入地研究，相關進展在文獻[13-14]中進行了詳細的分類和闡述.經典的MCTS策略包括基于樹結構上的上置信界（upper confidence bound applied to tree，UCT）算法[3,15]和湯姆森抽樣算法[16]等，它們通過非對稱的方式搜索博弈樹，使得有希望的走子路徑被更徹底地搜索以提高效率.然而具體的任務場景往往包含巨大的搜索空間和復雜的算法模型，基礎的或單一的樹搜索算法無法有效識別出最優動作，旨在解決這一問題的策略包括：限制可用行動的數量[17]、提前結束模擬階段[18]、構造信息集合[19]、結合領域知識[20]、建模對手行為[21]等.同時，將MCTS與進化學習[22-23]、聯邦學習[24]、遷移學習[25]等方法相結合實現優勢互補，進而增強收斂性、泛化性、遷移性和可解釋性等性能.雖然這些策略極大地提高了算法的效率和性能，但其中大部分策略僅通過實驗對比展現優勢，缺少理論保證和影響因素分析，導致算法缺少說服力.

將多臂賭博機（multi-armed bandit，MAB）算法引入到MCTS是促使其理論研究發展的關鍵一步，多臂賭博機的理論研究可為MCTS的分析提供有效參考.多臂賭博機[26]最初被提出用于管理臨床試驗，現在被常規應用于計算廣告、電子商務等廣泛任務中.多臂賭博機包含遺憾最小化[27]和最優搖臂識別 （best arm identification，BAI）[28]2個主要分支.文獻[29]通過引入KL散度得到搖臂的置信上界，從算法和理論2方面對遺憾最小化問題進行分析.最優搖臂識別算法要么在給定的置信度閾值下追求最少的試驗次數，要么在給定的試驗次數下追求識別最優搖臂的最小誤差[30-31]，固定預算下的MCTS最優動作識別問題與后者非常相似.

與BAI問題類似，MCTS最優動作識別問題的理論研究也可分為固定置信度和固定預算值2種設定.對于固定置信度的設定，文獻[32]將BAI方法引入到MCTS中，通過自底向上的方式對樹進行操作，并給出了返回具有可接受誤差的節點所需的采樣次數上界.文獻[33]提供了另外2種MCTS算法并得到了嚴格的概率近似正確分析和包含多個相關因素的樣本復雜度的高概率上界.對于固定預算的設定，文獻[34]假設隨機累計獎勵服從期望已知、均值未知的高斯分布，通過將排序選擇算法引入MCTS中提出了OCBA-MCTS算法，并得到了節點正確選擇的下界保證.然而，在獎勵樣本較少或整體方差較大時，文獻[33]給出的狀態動作值的后驗分布假設不能完全保證，造成理論保證不足.同時，OCBA-MCTS算法的正確選擇概率下界表明方差、間隔等相關因素與算法性能相關，其他相關因素仍需進一步探索.

2 極小極大采樣樹模型

本文對2名玩家、完全信息、零和博弈的蒙特卡洛樹搜索模型進行分析，為了有效地進行理論研究，引入了MCTS的抽象模型——MST模型，如圖1所示.該模型的大小由深度Depth和寬度Edge定義，即每個狀態下有Edge 個可行動作，樹結構有Depth個狀態層，最上層被定義為根節點層，最底層被定義為葉子節點層.根節點s0所在層數被定義為D(s0)=0，葉子節點f所在層數被定義為D(f)=Depth，葉子節點集合被定義為F.為了在樹狀結構中反映博弈過程，將玩家所在的偶數層節點定義為MAX節點，將對手所在的奇數層節點定義為MIN節點.

Fig.1 Flow chart of MST model圖1 極小極大采樣樹模型流程圖

MST模型包含3個流程：選擇、估計和回溯.在選擇流程中，MST通過給定策略選擇當前狀態下的最優動作并不斷下行，這與MCTS中的選擇流程一致.但MST將MCTS模型中的擴展流程和模擬流程合并為一個估計流程，即將擴展和模擬流程中通過隨機走子形成的子樹由一個服從伯努利分布的葉子節點f替代，其期望值pf為玩家在當前狀態的真實勝率.在實際探索過程中，葉子節點的期望值pf對玩家而言是未知的，因此玩家需要通過對葉子節點f的真實勝率進行估計.在回溯流程中將葉子節點估計值進行上傳，對該葉子節點的所有祖先節點的估值進行更新.由于MST依據葉子節點估值對所有非根節點進行估值，因此找到高效準確的葉子節點估值方法是最基礎和關鍵的一步.本文定義C(s)和P(s)分別表示節點s的子節點集合和1個父節點，從而可以得到樹結構中所有節點的期望值Vs： 如果節點s是葉子節點f，則Vf=pf；否則：

MST中的最優動作識別即識別出根節點s0下具有最大期望值的第1層節點：

在固定預算設定中，最優動作識別算法迭代N次后可返回第1層節點，算法旨在最小化識別誤差.

3 基于相對熵置信區間的最優動作識別算法

面向第2節中的MST模型，本節結合固定預算設定構造了MST最優動作識別算法DLU，其包含3個部分：葉子節點勝率估計、第1層節點值估計、最優節點選擇，其分別對應MST中估值、回溯和選擇3個流程，3個部分自下而上循環執行.首先在3.1節中，本文提出了基于相對熵的置信區間方法以估計葉子節點勝率.其次在3.2節中給出了區間上傳策略，依照該策略可以得到樹結構中所有非根節點的置信區間，從而對樹節點期望值進行估計.最后在3.3節中，本文給出了一種基于節點上下置信界的最優節點選擇策略，其包含選擇采樣節點和輸出推薦節點2部分.

3.1 葉子節點勝率估計

在DLU算法中，從第1節點中選擇出的最優節點是基于節點的估計值進行的，而第1層節點的估計值是通過以一定方式上傳葉子節點的估計值而得到，因此葉子節點估值的準確性對最優節點選擇是否正確和是否高效具有根本性的影響，更加準確的葉子節點估計策略將顯著提升算法性能.

為了對葉子節點f∈F的真實勝率V(f)=pf進行有效地估計，本文對葉子節點構造置信區間[35-36]：If(t)=[Lf(t),Uf(t)]，其中Uf(t)和Lf(t)分別是第t輪葉子節點勝率的置信上界和置信下界.在MST中設定葉子節點f∈F服從期望值為pf的伯努利分布β(pf)，通過對其進行采樣估值來表示MCTS中擴展階段和模擬階段形成的隨機走子過程.具體而言，在第t輪，算法選擇葉子節點ft并對其進行采樣得到樣本Xft～βft，進而計算葉子節點平均值并按照定義1得到置信區間Ift(t).

定義1.當算法第t次進行選擇流程并選擇葉子節點ft時，可基于相對熵得到其置信區間Ift(t)：

其中置信上界和置信下界分別為：

在式（5）中，Nft(t)表示葉子節點ft直至第t輪時被選擇的次數，p?ft(t)表示第t輪時葉子節點ft的平均值，α(Nft(t),λ)表示給定的探索函數，d(μ,μ′)為2個伯努利分布β和β′之間的相對熵，其中μ=E(β) 和μ′=E(β′)，即：

按照慣例，本文設定 0log0=0log0/0=0，及當x＞0時xlog(x/0)=+∞.對于任意的p?f(t)∈[0,1], 函數y-→d((t),y)在區間 [p?f(t),1]中是嚴格凸且單增.

3.2 第1層節點值估計

在得到葉子節點置信區間的基礎上，需要將其進行上傳以完成MST中的回溯流程.具體而言，由于MST由極小層和極大層交替組成，每次葉子節點ft的置信區間Ift(t)被更新后，依據式（6）將葉子節點的置信區間上傳[33]：

上傳過程直至第1層節點結束，從而完成ft每個祖先節點as∈AS的置信區間Ias(t)的更新，最終完成回溯流程.祖先節點集合AS定義為從根節點到達葉子節點ft時所有經過的節點.回溯流程完成后可以得到每個非根節點s包 含期望值V(s)的置信區間：Is(t)=[Ls(t),Us(t)].

在第t輪回溯流程中，第1層節點c∈C(s0)的置信區間Ic(t)為其期望值V(c)的估計范圍，能夠較為準確地表示當前狀態下玩家的勝率，更緊的置信區間能更好地為最優第1層節點選擇提供依據.

3.3 最優節點選擇

根據第t輪第1層節點c∈C(s0)的期望值估值區間Ic(t)，本文基于多臂賭博機方法給出了一種基于上下置信界（lower and upper confidence bounds, LUCB）[37]的最優節點選擇策略，其包含選擇采樣節點和輸出推薦節點2個部分，當t≤N時每次選擇一個第1層節點的代表葉子節點進行采樣，當t＞N時輸出推薦節點，該策略詳細流程為：

1）選擇采樣節點部分被劃分為確定備選節點和尋找代表葉子節點2個步驟.

①給出了以最高下界為準則的基于間隔的一致探索（unified gap-based exploration, UgapE）策略[38]，該策略基于置信界選擇備選節點，更緊的置信界能夠更加準確地刻畫節點值，從而在低采樣次數下更具優勢.UgapE策略對于每個第1層節點c∈C(s0)，計算指標并確定2個備選節點分別為：

②選擇lt和ut中具有較大置信區間的第1層節點置信區間越大表明該節點的不確定性更大，更需要探索.本文進一步定義第t輪每一個非葉節點s的 代表性子節點cs(t)為：

不斷向下尋找代表性子節點，最終可獲得第t輪每一個非根節點s的 代表性葉子節點rfs(t)為：

按照式（8）中的節點下傳方式，選擇Rt的代表葉子節點.

2）輸出推薦節點部分即當算法滿足N次采樣后算法終止并輸出推薦節點s?N.DLU算法架構如算法1所示.

算法1.DLU算法.

輸入：博弈樹結構T， 探索函數α(n,λ)，預算值N；

① fort=1,2,…,|F|

② 對每個葉子節點f∈F進行一次采樣，更新每個葉子節點的采樣次數Nf(t)并按照式（5）計算置信區間；

③ 按照式（6）更新每個非葉非根節點的置信區間Is(t)；

④ end for

⑤ fort≤N

⑥ 按照式（7）確定2個備選節點lt,ut；

⑦ 選擇具有較大置信區間的節點：

⑧ 選擇Rt的代表葉子節點rft；

⑨ 計算代表葉子節點rft的平均值p?rft(t)并更新置信區間Irft(t)；

⑩ 更新葉子節點的每個祖先節點as∈AS的置信區間Ias(t)；

?t=t+1；

? end for

4 誤差上界分析

第3節提出了DLU算法，該算法旨在給定預算時最小化識別誤差本節對最優動作的識別誤差上界進行推導.

首先，當設定d(μ,μ′)為2個期望值μ=E(β)和μ′=E(β′)的伯努利分布β和β′之間的相對熵時，基于Pinsker不等式可知這表明基于相對熵構造的葉子節點置信區間If(t)比基于霍夫丁不等式構造的置信區間IHf(t)=[LHf(t),UHf(t)]更緊，即If(t)?IHf(t)，其中：

進而可知當使用相對熵構造置信區間時，定理1成立.為了更清晰地進行證明，本文先給出了引理1.

引理1（引理5[33]）.令∈F If(t))成立，UGapE-MCTS算法使用探索函數：α(n,λ)=log(λ|F|)+3loglog(λ|F|)+1.5log(1+logn),λ≥1/max(0.1|F|,1)，

運行且在第t輪還未結束時，在第t+1輪選擇葉子節點f后可得：

其中Hf為葉子節點f的復雜度項，其中表示第1層節點中最優動作與次優動作之間期望值之差的平方，表示f的祖先節點s與其父節點P(s)之間的期望值之差的平方.基于其可以得到在第t輪葉子節點f的采樣次數Nf(t)與探索函數α（Nf(t),λ)的關系，H為所有葉子節點的復雜度項之和.

定理1.當DLU算法的采樣次數設定為N＞8H(W+2log(1+log(8HW)))，可以得到算法識別最優動作的誤差上界為：

其中，W=log(λ|F|)+3loglog(λ|F|).

證明：

文獻[33]中在固定置信度的設定下，UGapEMCTS算法運行直至滿足終止條件Uut(t)-Llt(t)＜η后停止采樣并且得到終止次數τ.對于DLU算法，本文假設η=0且在探索函數α(n;λ)=log(λ|F|)+3loglog(λ|F|)+1.5log(1+logn)，λ≥1/max(0.1|F|,1)下運行UGapEMCTS算法N次后，返回節點，進而分為2種情況進行分析：

1）對P(V(s0)≠V(s?N)|τ≤N)P(τ≤N)的上界進行分析.如果τ≤N，那么DLU算法在第τ輪滿足了終止條件Uuτ(τ)-Llτ(τ)＜η，并且輸出節點{1,2,…,N}也滿足了該條件.同時當假設和成立時，由式（6）進行置信區間上傳可得進而根據文獻[33]中引理2可知到V(s0)=V().因此，如果V(s0)≠V(s?N)，這意味著存在t∈[1,N]，εt不成立.即：

2）對P(τ＞N)進行上界分析，其表明算法在N次采樣后還未停止的概率.如果τ＞N，那么DLU算法的輸出節點其是在t∈{1,2,…,N}中具有最小指標Blt(t)的第1層節點.然后結合引理1可得：

其中可由引理1得到不等式（11）成立，是將UGapEMCTS算法在探索函數α(n;λ)中運行得到的.

基于引理1并結合DLU算法最終可得到結論：通過定理1可以得到，最優動作的識別誤差與探索函數和葉子集合的復雜度項有關，這表明固定預算下的DLU算法可通過改進這些影響因素以提升算法性能.

5 實驗分析

面向固定預算下的MCTS最優動作識別問題，為了最小化識別誤差，本文基于相對熵構造節點置信區間以評估節點值.為了驗證基于相對熵置信區間的算法優勢，本節在2種實驗場景下進行算法對比：人為構造的樹模型和真實博弈場景井字棋.在每一種實驗場景下，本文首先闡明了相關對比算法，然后給出了實驗參數設置，最后進行實驗分析.分析結果表明在人為構造的樹模型下，本文所提出的基于相對熵置信區間的算法類在低采樣次數下能顯著地提高識別準確度，從而節省計算資源.在井字棋場景下，本文提出的DLU算法可以有效地識別最優動作,減少時間復雜度.

5.1 構造樹模型場景

5.1.1 對比算法

首先，為了能夠證明基于相對熵置信區間的算法能夠從根本上提升算法性能，本文引入另一類備選節點計算策略：以最大均值為準則的EME策略[39]，該策略確定2個有希望的備選節點lt,ut的步驟為：

其次，本文在最優節點選擇部分中提出了均勻采樣（uniform sampling, RS）策略作為基準策略.與第3節使用的最優節點選擇策略LUCB每次只對1個節點進行采樣對比，均勻采樣策略是每輪對所有第1層節點進行采樣，詳細的算法流程為：

算法2.RS策略算法.

輸入：博弈樹結構T，探索函數α(n,λ)，預算值N；

輸出：第1層節點s?=lN.

① fort=1,2,...,|F|

② 對每個葉子節點f∈F進行一次采樣，更新每個葉子節點的采樣次數Nf(t)并計算置信區間If(t)；

③ 更新每個非葉非根節點的置信區間Is(t)；

④ end for

⑤ fort≤N

⑥ forc∈C(s0)

⑦ 選擇第1層節點c的代表葉子節點；

⑧ 計算代表葉子節點rfc的平均值(t)并更新置信區間Irfc(t)；

⑨ 更新代表葉子節點rfc的祖先節點as∈AS(rfc)的置信區間Ias(t)；

⑩t=t+1；

? end for

? end for

然后，本文引入文獻[33]中基于霍夫丁置信區間的2個算法，為了方便對比，將2個算法分別重命名為HLU算法和HLE算法.由于這2個算法只限定于LUCB策略，本文將這2個算法拓展至均勻采樣策略下，形成了HRU算法和HRE算法使用的探索函數為：

最后，本文將第4節DLU算法中的UgapE策略替換為EME策略，提出了DLE算法，同時將DLU算法和DLE算法中的LUCB策略替換為RS策略分別生成了DRU算法和DRE算法.8個算法的對應關系如表1所示.

Table 1 Setting of Experimental Algorithms表1 實驗算法設置

Table 2 Setting of Experimental Models表2 實驗模型設置

5.1.2 實驗模型

本文首先構造了3種樹類別、15種樹結構以驗證算法的性能表現.由于邊數Edge（表2中以E表示）和深度Depth（表2中以De表示，不包括根節點）是構成樹結構的2個元素，本文在其基礎上構造了邊數變化、深度變化、固定積數的3種樹類別.具體而言，對于邊數變化的樹類別，本文設定樹的深度為2，構造邊數分別為4，8，12，16，20的5種樹結構.對于深度變化的樹類別，本文設定樹的邊數為2，構造深度分別為2，4，6，8，10的5種樹結構.同時，固定邊數與深度之積S為24，得到(E,De)分別為（3，8），（4，6），（6，4），（8，3），（12，2）的5種樹結構.

在每一種樹結構下，進一步設置不同的節點間隔s_gap從而驗證算法在節點區分難度不同的樹模型的性能.節點間隔為2個同父結點取值的最小差值，設置取值為0.010或0.02，即

其中，V(s)表示節點s的 期望值，Ps表示節點s的父節點.

對于每一種樹模型，基于葉子節點和樹節點的個數給出不同倍數的采樣次數，具體的比例見實驗結果.設置參數λ=10.在每一種樹結構下對應生成2000個模型以進行樹搜索，最終對2000個模型上正確輸出最優動作的次數取平均值作為該結構在對應采樣倍數下的準確度：由于每個樹模型中葉節點的期望值p∈（0，1），因此在實驗過程中設定節點期望值的最大置信上界是1，最小置信下界是0.每個葉子節點的期望值在值空間中隨機選擇以保證模型的隨機性，設定多種架構和類別能夠更加全面地展現算法的性能優勢，凸顯算法對性能的影響.

5.1.3 實驗結果

圖2～7分別為3種樹類別中不同節點間隔s_gap和采樣倍數下的算法準確度，由于節點識別難度隨著節點間隔的減小而增加，因此在小節點間隔時給定更高的采樣倍數.8種算法在3種樹類別上性能表現都具有相同結論，即采用準確度作為評價標準時，基于相對熵置信區間的算法類都優于基于霍夫丁置信區間的算法類.

Fig.2 Accuracy of algorithms for edge-varing trees with node gap equals to 0.01圖2 節點間隔為0.01時邊數變化的樹類別的算法準確度

表3表示邊數變化的樹類別下的5種樹架構，可以發現隨著邊數的增加，總節點個數基本翻倍增加，因此給定的采樣倍數也逐步增加.圖2和圖3分別表示邊數變化的樹類別在節點間隔分別取0.01和0.02時8種算法的準確度，可以發現除了DRE算法和HRE算法，其他基于相對熵置信區間的算法都顯著優于對應的基于霍夫丁置信區間的算法.DRE算法和HRE算法準確度差距不顯著可能是因為當邊數增加時，第1層節點的取值逐漸接近，區分難度變大，需要更高的采樣倍數才能區分性能差異.同時由于均勻采樣策略對所有第1層節點使用相同的采樣次數，沒有在探索和利用之間進行均衡.然而，由于基于相對熵能構造更緊的置信區間從而更準確地對節點取值進行估計，因此DRE算法的準確度仍然高于HRE算法.同時HRU算法對采樣倍數變化非常敏感，在低采樣倍數下DRU算法具有明顯優勢，隨著采樣次數增加，HRU算法準確度有了極大的提升.

Table 3 Five Edge-varing Tree Structures表3 邊數變化的5種樹結構

Fig.3 Accuracy of algorithms for edge-varing trees with node gap equals to 0.02圖3 節點間隔為0.02時邊數變化的樹類別的算法準確度

表4為深度變化的樹類別下的5種樹結構，可以發現隨著深度的增加，葉子節點個數和總節點個數急劇增長，因此在深度較小的樹結構中增大采樣倍數，在深度較大時減小采樣倍數，從而將采樣次數保持在合理范圍內，以體現算法性能差距.圖4和圖5分別表示深度變化的樹類別在節點間隔分別取0.01和 0.02時8種算法的準確度，可以發現基于相對熵置信區間的算法類相較于基于霍夫丁置信區間的算法類具有斷層優勢，且隨著樹結構深度增加，優勢愈加明顯.這是因為深度增加時，置信區間上傳次數增加，更緊的置信區間能夠更加精準地對節點取值進行估計，減少上傳誤差.

Table 4 Five Depth-varing Tree Structures表4 深度變化的五種樹結構

Fig.4 Accuracy of algorithms for depth-varing trees with node gap equals to 0.01圖4 節點間隔為0.01時深度變化的樹類別的算法準確度

Fig.5 Accuracy of algorithms for depth-varing trees with node gap equals to 0.02圖5 節點間隔為0.02時深度變化的樹類別的算法準確度

表5設定固定積數的樹類別，以觀察在樹節點數量顯著不同的樹結構中算法性能的表現.圖6和圖7分別為固定積數的樹類別在節點間隔分別取0.01和0.02時8種算法的性能，可以發現在龐大的樹結構中，基于相對熵置信區間的算法類在采樣次數小幅度增加時其準確度會顯著增加，這表明本文所提的DLV算法類更適用于大規模樹結構，以實現節省計算資源的目的.

Table 5 Five Fixed Product Tree Structures表5 固定積數的5種樹結構

Fig.6 Accuracy of algorithms for fixed product trees with node gap equals to 0.01圖6 節點間隔為0.01時固定積數的樹類別的算法準確度

Fig.7 Accuracy of algorithms for fixed product trees with node gap equals to 0.02圖7 節點間隔為0.02時固定積數的樹類別的算法準確度

同時，通過比較基于RS策略和LUCB策略的算法類可以發現，LUCB策略整體而言具有更高的準確度.這是因為RS策略忽略節點之間的價值差異，對所有第1層節點進行等量采樣.而LUCB策略首先計算出2個高價值的備選節點，并對其中不確定性更大的節點進行采樣.LUCB策略作為一種啟發式方法，避免了對低價值節點進行過度采樣造成的資源浪費，在有限的預算內對更有價值的節點進行更充分地探索，因此能獲得更好的性能.

設定節點間隔為0.01，表6、表7和表8表示將15種樹模型上8種算法的實驗性能按照基于相對熵置信區間和基于霍夫丁置信區間進行分類的結果，可以發現本文所提出的構建相對熵置信區間以估計節點取值的方法能夠顯著提升算法性能.

Table 6 Accuracy Comparison of Two Classes of Algorithms for Edge-varing Trees with node gap equals to 0.01表6 節點間隔為0.01的邊數變化樹上的2類算法準確度對比

Table 8 Accuracy Comparison of Two Classes of Algorithms for Fixed Product Trees with node gap equals to 0.01表8 節點間隔為0.01的固定積數樹上的2類算法準確度對比

5.2 井字棋博弈場景

為了驗證DLU算法在實際博弈場景中具有良好的性能，本文引入OCBA-MCTS算法[34]，其完全契合固定預算下最優動作識別問題的最小化識別誤差的目標，是目前已知具有正確識別概率下界的最好算法，并在井字棋這一實際博弈場景中表現出優越的性能.

井字棋是一個2名玩家、完全信息、零和博弈游戲.棋盤為3×3大小，共有9個落子點，己方玩家（“O”）和對手玩家（“X”）輪流落子，見圖8.當在1行、1列或對角線上出現連續3個相同標記時，標記對應的一方獲勝.如果雙方都采取最佳行動，游戲將平局結束.本文考慮2種游戲設置： 圖9和圖10的左圖分別表明對手玩家已經在0號位置（設置1）和4號位置（設置2）標記了 “X”.圖9和圖10的右圖分別表明己方玩家在對應設置下的最優動作.由于棋盤的對稱性，因此在設置2中己方玩家的最優動作是0，2，6，8中的任意一個位置.如果算法運行結束后返回的動作與最佳位置匹配，則算法識別了一個正確的動作.OCBA-MCTS算法的參數設置與文獻[34]保持一致.DLU算法設置參數λ=10，算法重復5 000次觀察平均性能.在初次對所有葉子節點進行估值時，使用探索函數：α(n,λ)=log(λ)+1.5log(log(n)+1)，其后計算置信區間時使用探索函數:

Fig.8 Tic-tac-toe board圖8 井字棋棋盤

Fig.9 Tic-tac-toe game setup 1圖9 井字棋游戲設置1

Fig.10 Tic-tac-toe game setup 2圖10 井字棋游戲設置2

圖11和圖12分別為DLU算法和OCBA-MCTS算法在2種游戲設置下的實驗結果，2個算法性能相近，都能夠有效地識別最優節點.然而，OCBA-MCTS除了理論分析中的分布假設難以保證外，該算法在選擇流程中，需要計算當前節點下的每個子節點的新采樣分配，進而確定采樣節點，因此運行時間較為緩慢.當任務模型狀態空間越大，該算法的時間消耗將是一個不能忽視的問題.DLU算法使用的最優節點選擇策略相比更加簡潔，具有更低的時間復雜度.

Fig.11 Accuracy of algorithms under setup 1圖11 設置1下的算法準確度

Fig.12 Accuracy of algorithms under setup 2圖12 設置2下的算法準確度

6 結 論

為了解決固定預算下的MCTS最優動作識別問題，本文構造了極小極大采樣樹抽象模型MST并提出了基于相對熵置信區間的DLU算法，其包含與MST模型估值、回溯和選擇3個流程對應的3個部分：葉子節點勝率估計、第1層節點值估計、最優節點選擇.同時，本文給出了最優動作的識別誤差上界，并通過在30個樹模型上的實驗驗證了基于相對熵的算法類在準確性上具有顯著優勢.

在未來的工作中，將基于非平穩多臂賭博機對MCTS最優動作識別問題的采樣次數和誤差進行分析，從而更加還原MCTS流程，使得分析結果與實際算法更加匹配.同時，對強化學習的主要算法存在的隨機一致性[40-41]進行性能分析，以指導生成更具有泛化性、可解釋性的新方法，也是未來值得關注的研究方向.

作者貢獻聲明：劉郭慶提出了算法內容并撰寫論文；錢宇華指導并完善論文；張亞宇和王婕婷提出了修改意見并修改論文.