劉郭慶 王婕婷 胡治國 錢宇華

摘 要：蒙特卡羅樹搜索（MCTS）在棋類博弈問題中展現(xiàn)出卓越的性能，但目前多數(shù)研究僅考慮勝負兩種反饋從而假設(shè)博弈結(jié)果服從伯努利分布，然而這種設(shè)定忽略了常出現(xiàn)的平局結(jié)果，導致不能準確地評估盤面狀態(tài)甚至錯失最優(yōu)動作。針對這個問題，首先構(gòu)建了基于三元分布的多臂賭博機（TMAB）模型并提出了最優(yōu)臂確認算法TBBA;然后，將TBBA算法應(yīng)用到三元極大極小采樣樹（TMST）中，提出了簡單迭代TBBA算法的TBBA_tree算法和通過將樹結(jié)構(gòu)轉(zhuǎn)化成TMAB的 三元極大極小采樣樹 TMST最優(yōu)動作識別（TTBA）算法。在實驗部分，建立了兩個精度不同的搖臂空間并在其基礎(chǔ)上構(gòu)造了多個具有對比性的TMAB和TMST。實驗結(jié)果表明，相比均勻采樣算法，TBBA算法準確率保持穩(wěn)步上升且部分能達到100%，TBBA算法準確率基本保持在80%以上且具有良好的泛化性和穩(wěn)定性，不會出現(xiàn)異常值和波動區(qū)間。

關(guān)鍵詞：蒙特卡羅樹搜索;三元多臂賭博機;最優(yōu)臂確認;序列決策;純探索

中圖分類號：?TP181

文獻標志碼：A

Best action identification of tree structure based on ternary multi-arm bandit

LIU Guoqing1，2，3， WANG Jieting1，2，3， HU Zhiguo1，2，3， QIAN Yuhua1，2，3*

1.Research Institute of Big Data Science and Industry， Shanxi University， Taiyuan Shanxi 030006， China ;

2.Key Laboratory of Computational Intelligence and Chinese Information Processing of Ministry of Education （Shanxi University）， Taiyuan Shanxi 030006， China ;

3.School of Computer and Information Technology， Shanxi University， Taiyuan Shanxi 030006， China

Abstract：?Monte Carlo Tree Search （MCTS） shows excellent performance in chess game problem. Most existing studies only consider the success and failure feedbacks and assum that the results follow the Bernoulli distribution. However， this setting ignores the usual result of draw， causing inaccurate assessment of the disk status and missing of optimal action. In order to solve this problem， Ternary Multi-Arm Bandit （TMAB） model was constructed and Best Arm identification of TMAB （TBBA） algorithm was proposed. Then， TBBA algorithm was applied to Ternary Minimax Sampling Tree （TMST）. Finally， TBBA_tree algorithm based on the simple iteration of TBBA and Best Action identification of TMST （TTBA） algorithm based on transforming the tree structure into TMAB were proposed. In the experiments， two arm spaces with different precision were established， and several comparative TMABs and TMSTs were constructed based on the two arm spaces. Experimental results show that compared to the accuracy of uniform sampling algorithm， the accuracy of TBBA algorithm keeps rising steadily and can reach 100% partially， and the accuracy of TBBA algorithm is basically more than 80% with good generalization and stability and without outliers or fluctuation ranges.

The best action identification methods of Monte carlo tree search （MCTS） showed excellent performance in chess game problem. Most existing studies only considered the successful and failing feedback， which means that results follow Bernoulli distribution. However， this setting ignored the usual result of draw， which led to inaccurate assessment of disk configuration and even made wrong choice. In order to solve this problem， ternary multi-arm bandit （TMAB） is constructed and TBBA algorithm is proposed， which used for identifying best arm. TBBA algorithm then applyied to the ternary minimax sampling tree （TMST）. TBBA_tree algorithm is proposed by iteratively using TBBA algorithm. TTBA algorithm is presented through transforming the tree structure into special TMAB for the purpose of best action identification. In the experimental part， two arm spaces are established， several comparative TMABs and TMSTs are constructed. Experimental results showed that， compared to the uniform sampling algorithm， the accuracy of TBBA algorithm keeps rising steadily and can reach 100% in part. The accuracy of the TTBA algorithm is basically maintained more than 80%. Good generalization， stability also showed in TTBA algorithm.

Key words：?Monte Carlo Tree Search （MCTS）; Ternary Multi-Arm Bandit （TMAB）; Best Arm Identification （BAI）; sequential decision-making; pure exploration

0 引言

AlphaGo、AlphaZero算法[1-3]的出現(xiàn)對人工智能領(lǐng)域產(chǎn)生了巨大的影響，算法面向兩名玩家、完全信息、零和博弈的最優(yōu)動作識別問題，并在圍棋、將棋和象棋領(lǐng)域取得了從白板狀態(tài)起步戰(zhàn)勝人類專業(yè)棋手的卓越成績。現(xiàn)有研究將最優(yōu)動作識別視為一個樹搜索問題，樹結(jié)構(gòu)的每一個節(jié)點表示博弈過程的每一個信息完全已知的盤面，節(jié)點的出邊表示當前盤面下的可行動作集合。樹搜索旨在尋找當前節(jié)點下的最優(yōu)出邊。大多數(shù)博弈形成的樹結(jié)構(gòu)擁有極大的搜索空間，即使帶有巧妙修剪過程的算法想要對樹結(jié)構(gòu)進行窮盡搜索也是完全不可能的。因此，將有限的計算資源進行合理高效的分配是當前工作的研究重點。

在AlphaGo及其后續(xù)算法中使用的蒙特卡羅樹搜索（Monte Carlo Tree Search， MCTS）模型結(jié)合了樹搜索的精確性和隨機采樣的一般性，從而能有效地提高算法性能，節(jié)省計算資源?；贛CTS模型的算法創(chuàng)新和理論研究都取得了極大的突破。其中，Garivier等[4]提出了一個基礎(chǔ)樹搜索結(jié)構(gòu)，它針對兩名棋手的兩輪零和完全信息博弈過程，并與極大極小樹搜索結(jié)構(gòu)有著很高的相似性。在基礎(chǔ)樹搜索結(jié)構(gòu)中，因為棋手雙方為零和博弈關(guān)系，因此己方必須在考慮對手對立作用的基礎(chǔ)上選擇可行動作集中的最優(yōu)動作。在已有研究中，算法假設(shè)博弈僅有輸贏兩種結(jié)果，然而在現(xiàn)實場景中，類似圍棋、象棋的博弈游戲常常包含第三種結(jié)果：平局。當博弈游戲的盤面較小或者博弈雙方的水平基本相當時有很大的概率出現(xiàn)平局結(jié)果，并且考慮平局結(jié)果有助于棋手更準確地估計博弈結(jié)果，有益于分析本身和對手的行為。因此本文在基礎(chǔ)樹搜索結(jié)構(gòu)之上假設(shè)每個葉子節(jié)點服從一個三元分布，并構(gòu)建了基于三元分布的兩層極大極小采樣樹（Ternary Minimax Sampling Tree， TMST），它能夠模擬博弈過程中出現(xiàn)的成功、平局、失敗三種結(jié)果。本文還提出了三元極大極小采樣樹最優(yōu)動作識別（Best Action identification of TMST， TTBA）算法，從而更準確地評估每個盤面的狀態(tài)，選擇最優(yōu)的可行動作。

三元多臂賭博機（Ternary Multi-Arm Bandit， TMAB）的最優(yōu)臂確認算法是一種解決極大極小采樣樹最優(yōu)動作識別問題的有效算法，本文通過將樹結(jié)構(gòu)的每一對動作視為一個搖臂構(gòu)建了特殊的多臂賭博機（Multi-Arm Bandit， MAB）模型。MAB是描述連續(xù)決策問題中探索與利用權(quán)衡關(guān)系的重要模型。探索 利用窘境可以描述為：對于多個獎賞未知的搖臂，為了在有限次數(shù)的連續(xù)選擇后使累積反饋獎賞最大化，每一次選擇時都面臨著是堅持目前已知的最好對象，還是探索可能的更優(yōu)對象的問題。近年來，MAB在網(wǎng)頁搜索、廣告推薦、多路通信、大數(shù)據(jù)等方面受到廣泛關(guān)注。

MAB中的最優(yōu)臂確認問題與累積獎賞最大化問題相比較而言，前者表示了一個純探索過程，即在有限次數(shù)的選擇過程中，智能體不關(guān)注累計獎賞值，僅識別候選臂集合中具有最優(yōu)目標的搖臂。目前基于純探索的最優(yōu)臂識別（Best Arm Identification， BAI）問題得到了廣泛的關(guān)注與深入的研究。BAI問題包括兩個主要研究方向：1）在設(shè)定置信度的前提下最小化采樣次數(shù);2）設(shè)定實驗輪數(shù)，旨在使得誤差概率最小化。部分現(xiàn)有算法將每一個獎賞未知的搖臂視為一個參數(shù)未知的伯努利分布，但是獎賞也常常包含一種無偏向的反饋情況。如在路徑規(guī)劃問題中，為了簡化人為設(shè)定獎賞值的工作量，除遇到障礙物或者接近目標等重要方向選擇外，其他選擇通常設(shè)定其獎賞為零。在游戲場景中，只有充分地估計玩家的輸贏及平局的概率，才能挑選出最合適的對手或隊友從而贏得游戲。因此，為了更加準確地模擬搖臂服從的分布，從而更高效地識別目標，本文設(shè)反饋結(jié)果包含三個類別：失敗、平局和成功，并稱此模型為三元多臂賭博機（TMAB）。

本文基于貝葉斯思想并利用共軛先驗的屬性解決TMAB最優(yōu)臂確認問題，并提出了TMAB最優(yōu)臂確認 （Best Arm identification of TMAB， TBBA）算法。本文提出的TBBA算法根據(jù)每個搖臂后驗分布的采樣值選擇一個最具優(yōu)勢的搖臂作為采樣臂并對其進行采樣，這一方法利用了貝葉斯估計在選取當前最優(yōu)臂的同時還能探索搖臂未知空間的優(yōu)勢。在貝葉斯推斷中，如果后驗分布與先驗分布屬于同類分布，則先驗分布與后驗分布被稱為共軛分布，而先驗分布被稱為似然函數(shù)的共軛先驗。TBBA算法利用狄利克雷分布和多項分布的共軛屬性并基于共軛先驗形成的先驗鏈，實現(xiàn)算法運行過程中的相關(guān)參數(shù)更新。

本文的主要工作如下：

1）引入了無偏向反饋值概念，提出了一個基于貝葉斯思想和共軛分布先驗鏈的TBBA算法，能夠?qū)Ρ疚臉?gòu)建的TMAB的最優(yōu)臂進行有效確認;

2）將 TBBA算法應(yīng)用到本文提出的極大極小采樣樹結(jié)構(gòu)中，解決了兩名玩家的兩輪零和完全信息博弈下的最優(yōu)動作識別問題;

3）建立了兩個臂空間并在其基礎(chǔ)上構(gòu)造了多個具有對比性的三元多臂賭博機、三元極大極小采樣樹結(jié)構(gòu)，驗證了本文所提出的TBBA、TTBA算法能夠有效地識別集合中的最優(yōu)對象。

1 相關(guān)工作

多臂賭博機在多個領(lǐng)域中發(fā)揮著重要的作用，MCTS及相關(guān)模型在不同的背景下也都有著廣泛的應(yīng)用和重要的研究意義。接下來，本文將介紹部分多臂賭博機和貝葉斯推理的工作以及MCTS的相關(guān)研究。

1993年，Thompson[5]以臨床實驗問題為背景提出了多臂賭博機模型。在關(guān)于累積獎賞最大化的研究中，文獻[6]介紹了兩個極端的案例：獨立同分布的獎賞和對抗性的獎賞，并給出了簡潔的遺憾分析。算法還描述了有限動作的基本設(shè)定和賭博機模型一些重要的變體和擴展。同時，多臂賭博機的最優(yōu)臂確認問題也取得了顯著的成果。在設(shè)定置信度并使得采樣次數(shù)最小化的研究方向中，已有文獻提出了一致采樣消除法、上下置信界法并就采樣次數(shù)的上下界進行了深入的研究[7-13]。在設(shè)定實驗輪數(shù)并使得誤差概率最小化的前提下，現(xiàn)有研究在最優(yōu)臂個數(shù)、策略思想、理論分析、應(yīng)用領(lǐng)域等方面展開了研究。在關(guān)于最優(yōu)臂個數(shù)研究中，文獻[14]提出了單個最優(yōu)臂確認的連續(xù)消除算法，隨后文獻[15]中提出了基于連續(xù)接受和拒絕思想的多個最優(yōu)臂確認算法。

文獻[16]針對連續(xù)消除算法提出了一個統(tǒng)一框架，并將設(shè)定的輪數(shù)根據(jù)一個與每輪存在臂集相關(guān)的非線性函數(shù)進行劃分。在理論分析方面，通過引入Kullback-Leibler散度，文獻[17]在原基礎(chǔ)算法之上得到了更緊的上界，文獻[18]中給出了更有效的下界。在文獻[19]中，算法框架表明上述固定置信度和固定輪數(shù)的設(shè)定可以共用一個算法框架進行最優(yōu)臂確認并給出了證明。

在策略思想方面，因為基于貝葉斯思想的湯普森采樣通常被視為一個解決探索 利用平衡問題的啟發(fā)式方法，因此它常被應(yīng)用于多臂賭博機的研究中并展現(xiàn)出易實現(xiàn)性和優(yōu)異性能[20]。為了能夠保證更好的定向探索，文獻[21]引入了樂觀貝葉斯抽樣（Optimistic Bayesian Sampling， OBS）算法，使得選取動作的概率與該動作值的不確定性成正比增加。在特殊的單輪多次采樣多臂賭博機模型中，文獻[22]也給出了多輪湯普森采樣（Multiple-Play Thompson Sampling， MP-TS）算法并討論了該算法的遺憾分析。

MCTS在包括棋類博弈的多個領(lǐng)域中展現(xiàn)了巨大的優(yōu)勢。文獻[23]概述了其核心算法的推導過程，介紹了一些已經(jīng)提出的變化和增強的結(jié)構(gòu)，并總結(jié)了MCTS方法應(yīng)用至關(guān)鍵游戲和非游戲領(lǐng)域的結(jié)果。文獻[24]解釋了MCTS的主要算法如何提高計算機圍棋的技術(shù)水平。針對一次對弈的簡化MCTS模型，文獻[25]提出了基于伯努利分布的兩種策略并討論了這兩種算法的樣本復雜度和一個下界分析。在不限層數(shù)、基于伯努利分布的簡化MCTS模型中，文獻[25-26]提出了最優(yōu)動作確認的算法及理論分析。

2 三元多臂賭博機的最優(yōu)臂確認

本文通過貝葉斯思想對基于三元分布的多臂賭博機進行最優(yōu)臂確認，提出了多臂賭博機最優(yōu)臂確認（Best Arm Identification of Multi-Arm Bandit， MAB_BAI）問題的一般算法框架，描述了如何運用貝葉斯思想和共軛分布的先驗鏈進行三元MAB_BAI的反饋值獲取、采樣臂選擇、參數(shù)更新和算法最優(yōu)臂輸出。

2.1 基于三元分布的多臂賭博機

多臂賭博機是由K個搖臂組成的系統(tǒng)（如圖1），臂集A中的每個搖臂a∈{1，2，…，K}服從一個參數(shù)未知的概率分布?，F(xiàn)有研究多將臂分布建模為伯努利分布，本文為了更準確地模擬反饋結(jié)果將臂分布建模為三元分布，從而建立了三元多臂賭博機模型。其中，每一個搖臂a都服從一個三元分布，即每個臂擁有不同的三元概率值：? μ a=（μam）m∈{1，2，3}=（μa1，μa2，μa3），如表1所示，μa1、 μa2、 μa3分別代表臂a取值-1、0、1的概率或失敗、平局、成功的概率，并且μa1+μa2+μa3=1。

在三元多臂賭博機中，本文將失敗概率值最小的臂作為最優(yōu)臂，若出現(xiàn)多個臂失敗概率最小時，本文將平局概率最小的臂作為最優(yōu)臂。即：

a*=arg min m=2 min m=1 （μam）; a∈{1，2，…，K}

（1）

在現(xiàn)有研究中，算法將具有最大期望值的臂作為最優(yōu)臂。本文沒有使用這種衡量指標，因為當出現(xiàn)如表2的兩個搖臂時，若按照本文最優(yōu)臂定義，臂2為最優(yōu)臂;如果將期望值作為評判標準時，臂1是最優(yōu)臂，然而臂1的失敗概率更大，更容易陷入最差的結(jié)果中。

2.2 三元多臂賭博機的最優(yōu)臂確認算法

本文考慮固定實驗輪數(shù)下的多臂賭博機最優(yōu)臂確認問題，基于此問題的算法框架通常包含如下過程：第t輪時，算法依據(jù)選臂策略從臂集A中選擇一個采樣臂At，然后對臂At按照概率值為 μ At的分布進行采樣并得到一個反饋值 R t。算法再依據(jù) R t對與其相關(guān)的臂進行更新，更新內(nèi)容包括分布參數(shù)、采樣次數(shù)或算法定義的相關(guān)變量。隨著實驗次數(shù)的增加，算法可以逐漸得到每個臂接近分布概率真實值 μ a的估計值?? a。當算法運行至第t+1輪時，算法終止并返回具有最優(yōu)概率估計值?? 的臂作為多臂賭博機的算法最優(yōu)臂 。上述過程主要包括四個研究點：選擇采樣臂、獲取反饋值、更新相關(guān)參數(shù)和輸出算法最優(yōu)臂。以下是它們在三元多臂賭博機中的具體實現(xiàn)。

1）反饋值的獲取。

當算法運行至第t輪并按照選臂策略從臂集A中選擇采樣臂At后，再根據(jù)At的分布概率 μ At=（μAt1， μAt2， μAt3）進行采樣并得到一個三元反饋值 R t=[r1，r2，r3]，其中ri∈{0，1}，∑ 3 i=1 ri=1?；诖?，本文算法將反饋值 R t=[r1，r2，r3]的概率記為：

P（ R t | ?μ At）=∏ 3 i=1 （μAti）ri

（2）

2）相關(guān)參數(shù)的更新。

首先，本文算法定義分布概率 μ a=（μa1，μa2，μa3）服從參數(shù)為 θ??? ·?? a=（θ ??·?? a1，θ ??·?? a2，θ ??·?? a3）的狄利克雷分布，即對于每個臂a∈{1，2，…，K}，在第t輪時其先驗分布為：

D（ θ??? ·?? at）= 1 B（ θ??? ·?? at）? ∏ 3 i=1 （μai） ??at，i-1

（3）

其中，B函數(shù)是一個標準化函數(shù)，目的是使狄利克雷分布的概率密度積分等于1。

然后，算法將對臂采樣后得到的反饋值視為貝葉斯估計中的似然函數(shù)，并與先驗分布D（ θ??? ·?? Att）結(jié)合求出如下后驗概率：

p （ θ Att | ?R t）= p（ R t | ?θ??? ·?? Att）p（ θ??? ·?? Att） p（ R t） ∝p（ R t | ?θ??? ·?? Att）p（ θ??? ·?? Att）=

∏ 3 i=1 （μAti）ri×∏ 3 i=1 （μAti） ??Att，i-1=

∏ 3 i=1 （μAti）ri+?? Att，i-1

（4）

算法發(fā)現(xiàn)貝葉斯估計的后驗分布可以視為參數(shù)為 θ Att= θ??? ·?? Att+ R t的狄利克雷分布，用B函數(shù)將它標準化就得到本文算法的后驗分布為：

D（ θ Att）= 1 B（ θ Att） ∏ 3 i=1 （μAti） θ Att，i-1

（5）

上述過程中，后驗分布與該先驗分布為共軛分布，則基于共軛先驗可以形成一個先驗鏈：當前輪每個臂的后驗分布可以作為下一輪的先驗分布，即D（ θ??? ·?? at+1）=D（ θ at）。算法不斷迭代使得基于分布參數(shù)的分布概率評估更加準確。在此迭代過程中：當算法運行到第t+1輪時，基于每個臂在第t輪的后驗概率D（ θ at）挑選出采樣臂At+1后，對其進行采樣并獲得反饋值 R t+1;然后利用反饋值對D（ θ At+1t）的參數(shù)進行更新。根據(jù)前文可知 θ At+1t+1= θ At+1t+ R t，即參數(shù)更新只需要把反饋值 R t+1為1的第i個分量在采樣臂參數(shù) θ At+1t的對應(yīng)分量加1就能得到第t+1輪的后驗分布D（ θ At+1t+1），非采樣臂的其他搖臂直接將第t輪的后驗分布作為第t+1輪的后驗分布。之后，算法可以繼續(xù)重復上述參數(shù)更新過程直至算法運行結(jié)束。

3）采樣臂的選擇。

在算法運行到第t+1輪時，算法依據(jù)每個臂在第t輪的后驗分布D（ θ at）進行隨機采樣并得到K個采樣值 θ ′at+1，然后從K個采樣值中選擇出最具優(yōu)勢的臂：

At+1=arg min m=2 min m=1 （ θ ′at+1，m）

（6）

作為算法在第t+1輪的采樣臂。通過對后驗狄利克雷分布隨機采樣而選取的采樣臂綜合了搖臂的最優(yōu)性和可探索性，在利用了搖臂現(xiàn)有信息的同時也對搖臂的不確定性進行了探索。

4）算法最優(yōu)臂的獲取。

當算法運行結(jié)束后，每個臂都服從參數(shù)為 θ aT的狄利克雷分布D（ θ aT）。通過狄利克雷分布的性質(zhì)：? μ a=?? θ a1? θ a1+ θ a2+ θ a3 ，? θ a2? θ a1+ θ a2+ θ a3 ，? θ a3? θ a1+ θ a2+ θ a3? ，算法可以得到每個搖臂的分布概率估計值：

a=

θ aT，1? θ aT，1+ θ aT，2+ θ aT，3 ，? θ aT，2? θ aT，1+ θ aT，2+ θ aT，3 ，? θ aT，3? θ aT，1+ θ aT，2+ θ aT，3

（7）

并在此基礎(chǔ)上獲得算法最優(yōu)臂：

=arg min m=2 min m=1 （ am）

（8）

綜上所述，三元多臂賭博機最優(yōu)臂確認問題的具體流程如下：

算法1? 三元多臂賭博機的最優(yōu)臂確認（TBBA）算法。

輸入? 多臂賭博機臂集A，各臂分布概率 μ a，輪數(shù)T;

輸出? 算法最優(yōu)臂。

程序前

1）

對每個臂設(shè)定參數(shù)初始值： θ a0=（1，1，1）

2）

Fo r t={1，2，…，T} do：

3）

Fo r a∈{1，2，…，K} do：

4）

進行隨機采樣： ???at=D（ θ at-1）

5）

End For

6）

選擇采樣臂： At=arg min m=2 min m=1 （?? at，m）

7）

對At根據(jù)分布概率 μ At=（μAt1，μAt2，μAt3）采樣并得到反饋值：? R t=[r1，r2，r3]

8）

If? rm=1

then θAtt，m=θAtt，m+1，m∈{1，2，3}

9）

End If

10）

End For

11）

利用式（7）計算得到每個臂的分布概率近似值

12）

利用式（1）計算得到算法最優(yōu)臂

程序后

算法運行之初，本文假設(shè)每個臂的先驗分布是參數(shù)為 θ??? ·?? a1=（1，1，1）的狄利克雷分布D（ θ??? ·?? a1），為了便于組織算法流程框架，將其記為D（ θ a0）。接著重復偽代碼中的流程直至第T輪時算法運行結(jié)束。本文通過每個臂在第T輪的后驗分布D（ θ aT）得到算法最優(yōu)臂并輸出。

3 三元極大極小采樣樹最優(yōu)動作識別

3.1 基于三元分布的極大極小采樣樹

以AlphaZero的模型框架——蒙特卡羅樹搜索為背景，Kaufmann等[26]將一個兩名玩家的兩輪零和完全信息博弈過程進行簡化并建立了一個樹搜索結(jié)構(gòu)，本文在此基礎(chǔ)上重新建立葉子節(jié)點服從的分布，并定義新的樹搜索結(jié)構(gòu)為極大極小采樣樹如圖2所示。它與常見的三層極大極小樹搜索結(jié)構(gòu)相比，相似之處包括：1）根節(jié)點為極大節(jié)點;2）第一層節(jié)點為極小節(jié)點，極大節(jié)點與極小節(jié)點交替出現(xiàn);3）葉子節(jié)點為根節(jié)點的獎賞信息。不同之處在于：極大極小樹中葉子節(jié)點表示已知固定的獎賞值，而極大極小采樣樹的每一個葉子節(jié)點是一個參數(shù)未知的三元分布。

極大極小采樣樹結(jié)構(gòu)設(shè)定玩家A為根節(jié)點并且有K個可行動作，具有競爭關(guān)系的玩家B作為第一層節(jié)點（競爭關(guān)系指玩家A選擇具有最大優(yōu)勢的動作，玩家B選擇使A優(yōu)勢最小的動作）。對于玩家A的每一個可行動作組i∈{1，2，…，K}，玩家B有j∈{1，2，…， Ji}個可行動作。樹結(jié)構(gòu)的葉子節(jié)點是玩家A博弈結(jié)果的概率分布，本文假設(shè)第i組中第j個葉子節(jié)點服從概率值為 μ ij=（μijm）m∈{1，2，3}=（μij1，μij2，μij3）的三元分布vij，其中，μij1、 μij2、 μij3分別表示玩家A獲得反饋值-1、0、1的概率，也可將其視為失敗、平局、勝利的概率。

TMST最優(yōu)動作識別算法的目標是在有限的輪數(shù)T內(nèi)，識別出玩家A在可行動作集合中的最優(yōu)動作i*。因為零和博弈過程中玩家A和B為競爭關(guān)系，因此，算法不能簡單地從所有的葉子節(jié)點中選擇最有優(yōu)勢的節(jié)點

i′j′=arg min m=2 min m=1 （μijm）; ??????i∈{1，2，…，K}且j∈{1，2，…， Ji}

（9）

后將i′作為玩家A的最優(yōu)動作。玩家A的最優(yōu)動作應(yīng)該是在玩家B刻意降低玩家A博弈優(yōu)勢的情況下，A能得到的最優(yōu)葉子節(jié)點i*j*中的動作，其定義為：

i*=arg min m=2 min m=1 （μij*im）; i∈{1，2，…，K}

（10）

其中對于每一個動作組i：

j*i=arg max m=2 max m=1 （μijm）; j∈{1，2，…， Ji}

（11）

3.2 TMST最優(yōu)動作識別算法

根據(jù)上文極大極小采樣樹最優(yōu)動作i*的定義，樹結(jié)構(gòu)可以被視為兩層三元多臂賭博機組成的系統(tǒng)?；诖擞^點本文提出了基于三元極大極小采樣樹的TBBA算法（TBBA algorithm based on TMST， TBBA_tree），其主要思想是：先后在下層、上層使用TBBA算法，從而找到玩家A的算法最優(yōu)動作i?? ^?? 。算法的具體過程如下：1）劃分樹結(jié)構(gòu)上下層的實驗輪數(shù)。2）在下層中，玩家B在每一個動作組i∈{1，2，…，K}的Ji個動作中選擇使玩家A的優(yōu)勢最小的動作j*i，這個部分可以視為一個目標與上文相反的三元多臂賭博機模型，此模型的最優(yōu)臂是玩家A博弈結(jié)果最差的臂。樹結(jié)構(gòu)下層共有K個多臂賭博機，因此，算法得到K個最差臂。

3）在上層中，玩家A在這K個最差臂中選擇最具優(yōu)勢的臂，此時，多臂賭博機模型與上文所述一致并且將這個部分視為第K+1個多臂賭博機。

4）將第K+1個多臂賭博機返回的搖臂作為樹結(jié)構(gòu)中玩家A的最優(yōu)動作i*，算法過程如圖3所示， 首先在每組內(nèi)通過TBBA_tree算法找到最差臂j*1， j*2，…， j*K（分別標記為1，2，…，K），然后根據(jù)K個最差臂選擇出整體最優(yōu)臂j*K（深灰色），即玩家A的最優(yōu)動作為K。

在TBBA_tree算法實驗過程中可能存在以下問題：1）由于樹結(jié)構(gòu)被分成兩層多臂賭博機，因此實驗開始之前需要人為設(shè)定上下層各多臂賭博機的實驗輪數(shù)，這將造成一定的人力開銷;2）在多數(shù)情況下，相同的樹結(jié)構(gòu)、不同的實驗輪數(shù)分配方式會產(chǎn)生不同的實驗結(jié)果，因此，實驗結(jié)果會存在很大的標準差，使得結(jié)果丟失評判價值;3）當實驗輪數(shù)全部分配給下層時，極有可能造成實驗結(jié)果中存在離群點。圖4表示TBBA_tree算法在一個給定的樹結(jié)構(gòu)中出現(xiàn)上述2）、3）兩個問題。

為了解決上述問題，本文基于文獻[4]提出的方法將樹結(jié)構(gòu)整體視為一種特殊的三元多臂賭博機。這個特殊的多臂賭博機一共包含 =∑ K i=1 Ji個臂，每個臂p∈ 由一對動作對表示（如圖5灰色部分所示），即：p=（i， j）。多臂賭博機的臂集為：P={（i， j）：1≤i≤K，1≤j≤Ji}。每個臂p服從參數(shù)為 μ p=（μpm）m∈{1，2，3}=（μp1，μp2，μp3）的三元分布νp。根據(jù)上述設(shè)定，極大極小采樣樹的最優(yōu)動作確認問題轉(zhuǎn)換成從包含 個臂的三元多臂賭博機中選擇一個臂子集，臂子集中所有的臂都是第i組內(nèi)玩家B的可行動作，且i符合玩家A最優(yōu)動作的定義。

本文基于特殊三元多臂賭博機模型和TBBA算法提出了一個新的極大極小采樣樹的最優(yōu)動作識別算法——TTBA。 算法具體過程如下：

算法2? 三元極大極小采樣樹的最優(yōu)動作識別（TTBA）。

輸入? 采樣樹結(jié)構(gòu)Tree，各葉子節(jié)點的概率值 μ i， j，輪數(shù)T;

輸出? 算法確認的最優(yōu)動作 。

程序前

1）

對臂集P={（i， j）：1≤i≤K，1≤j≤Ji}中的每一個臂p設(shè)定參數(shù)初始值： θ i， j0=（1，1，1）

2）

Fo r t=1，2，…，T do：

3）

Fo r i=1，2，…，K do

4）

Fo r j=1，2，…， Ji do

5）

進行隨機采樣： ??i， jt～D（ θ i， jt-1）

6）

End for

7）

返回組內(nèi)最差動作：Ji，t=arg max m=2 max m=1 （ i， jt，m）

8）

End for

9）

返回組間最優(yōu)動作：

It=arg min m=2 min m=1 （ i， Ji，tt，m）

10）

對搖臂Pt=（It， JIt，t）進行采樣并得到反饋值： ???R t=[r1，r2，r3]

11）

If? rm=1 then ?θ Ptt，m= θ Ptt，m+1，m∈{1，2，3}

12）

End if

13）

End for

14）

得到每個搖臂分布概率的近似值：

p= ??θ pT，1? θ pT，1+ θ pT，2+ θ pT，3 ，? θ pT，2? θ pT，1+ θ pT，2+ θ pT，3 ，? θ pT，3? θ pT，1+ θ pT，2+ θ pT，3

15）

得到算法最優(yōu)動作：

i?? ^?? =arg min m=2 min m=1 （ i，? im），i∈{1，2，…，K}

其中對于每一個動作i：

i=arg max m=2 max m=1 （ i， jm）， j∈{1，2，…， Ji}

程序后

與TBBA算法相同，本文假設(shè)每個臂的先驗分布是參數(shù)為 θ??? ·?? i， j1=（1，1，1）的狄利克雷分布D（ θ i， j0）。接著重復偽代碼中的流程，直到達到輪數(shù)T+1輸出算法最優(yōu)臂。算法過程如圖5所示，將每一個的葉子節(jié)點視為一個搖臂，此時共有 =∑ K i=1 Ji個搖臂。根據(jù)TTBA算法從 個搖臂中選擇出玩家A最優(yōu)動作組內(nèi)的葉子節(jié)點2.2（深灰色），即玩家A的最優(yōu)動作為2。淺灰色圖形表示一個動作對可視為一個三元多臂賭博機。

與TBBA_tree算法相比，TTBA算法既避免了出現(xiàn)由于人為劃分實驗輪數(shù)而導致的離群點和明顯波動的實驗結(jié)果，又表現(xiàn)出優(yōu)異的性能。圖6表示TTBA算法的實驗結(jié)果，TTBA算法和TBBA_tree算法使用的樹結(jié)構(gòu)相同。

4 實驗與結(jié)果分析

4.1 度量標準

本文提出的TBBA、TTBA算法的目標都是識別一個集合中最優(yōu)對象，因此，本文將準確率作為算法的性能評估指標，其定義為：

ACCURACY=P（ =a*）= 1 R ∑ R r=1 1 r=a*

其中： 表示算法輸出的對象，a*表示真實最優(yōu)對象， r表示第r次運行結(jié)束時算法輸出的對象，R表示算法運行的次數(shù)。與此同時，在三元多臂賭博機的測試中，為了更加清晰地觀察算法的性能，本文定義了算法的得分：

GRADE=? 1 R ∑ R r=1 （g（a*）-g（ r））=

1 R? R×g（a*）-∑ R r=1 g（ r）

其中：g（a*）、g（ r）分別表示真實最優(yōu)對象的分數(shù)和算法在第r次運行結(jié)束時返回的對象 r的分數(shù)。

文獻[11，25-26]等已經(jīng)對多臂賭博機最優(yōu)臂確認問題以及極大極小采樣樹最優(yōu)動作識別問題展開了深入的研究，并提出了有效的算法。在實驗部分驗證算法性能時，先設(shè)定模型中的參數(shù)值，即每個搖臂或每個葉子節(jié)點的分布概率值;然后在給定的模型上運行算法，從而驗證算法的性能。本文為了驗證TBBA和TTBA算法的高效性、穩(wěn)定性，建立了兩個精度不同的臂空間：第一個臂空間設(shè)定每個臂服從概率值為 μ =（μ1，μ2，μ3）的三元分布，其中（μm）m∈{1，2，3}∈（0.1，0.2，…，0.9），并且μ1+μ2+μ3=1;第二個臂空間設(shè)定每個臂服從的三元分布概率值（μm）m∈{1，2，3}∈（0，0.05，…，1.0），并且μ1+μ2+μ3=1。然后在此基礎(chǔ)上構(gòu)建了多個參數(shù)給定的、具有比較性的三元多臂賭博機及三元極大極小采樣樹模型。其中，模型結(jié)構(gòu)多樣，覆蓋范圍廣泛，并且搖臂和葉子節(jié)點的分布概率值在臂空間中隨機選擇保證了模型的隨機性。本文設(shè)定不同精度的臂空間也有助于在較低的實驗輪數(shù)內(nèi)展現(xiàn)算法的性能，更能突顯模型結(jié)構(gòu)對算法的影響。

4.2 TBBA算法實驗結(jié)果

本節(jié)實驗以游戲過程中玩家選擇隊友為例。每個候選玩家的實力都由其贏局、輸局、平局的概率表示，玩家的目標是選擇出最具優(yōu)勢的候選玩家。本文根據(jù)問題性質(zhì)將每個候選玩家視為一個服從三元分布的搖臂，將此問題建模成一個三元多臂賭博機，算法旨在確認出模型中的最優(yōu)臂。每個候選玩家的分布概率取值具有隨機性，因此，本文算法隨機從臂空間中選擇每個搖臂的分布概率值，這樣可以保證實驗結(jié)果的普適性。為了驗證基于三元分布的多臂賭博機最優(yōu)臂確認（TBBA）算法在三元多臂賭博機（TMAB）模型中的性能，本文將TBBA算法與均勻采樣（Uniform sampling， U）算法進行比較，并設(shè)置了兩組對比實驗。 實驗結(jié)果中，方塊線表示TBBA算法，三角線表示U算法。

第一組實驗驗證TBBA算法在臂數(shù)相同、識別難度不同的三元多臂賭博機中的有效性。本文依據(jù)第二個臂空間建立了如表3所示的3個TMAB模型，其中每一個模型包含5個臂，按照搖臂的序號依次設(shè)置分數(shù)為5、4、3、2、1。不同模型臂間的識別難度逐漸增大。本文分別在三個模型上運行了TBBA算法和均勻采樣算法，實驗結(jié)果如圖7所示，其中（a）表示算法的準確率，（b）表示算法運行結(jié)束后的得分。在模型1中，由于各臂分布概率值差距較大，因此算法在很少的輪數(shù)內(nèi)通過估計各臂分布的失敗概率就能確認出最優(yōu)臂： =arg min m=1 ?μam。圖7第一列展現(xiàn)出在搖臂容易區(qū)分的模型中TBBA算法比U算法的性能稍有優(yōu)勢，并且大約在400輪后兩個算法性能都趨于穩(wěn)定并能完全確認最優(yōu)臂。模型2縮小了臂分布之間的間隔，模型中搖臂分辨難度被提高，圖7第二列表明TBBA算法性能優(yōu)良、提升速度更快。在模型3中，搖臂之間僅在平局概率有細微的差別。均勻采樣算法的準確率在20%波動，得分約為300，這表明策略幾乎無效，算法隨機返回最優(yōu)臂;而TBBA算法仍表現(xiàn)出良好的性能，算法的精確度隨輪數(shù)增加呈現(xiàn)出穩(wěn)定的增長趨勢。實驗結(jié)果表明：TBBA算法在不同分辨難度的TMAB中都具有良好的性能，尤其對于臂分布非常相似、確認難度很高的模型，TBBA算法的優(yōu)勢更加顯著。

第二組實驗驗證TBBA算法在不同搖臂個數(shù)的三元多臂賭博機中的有效性，實驗結(jié)果如圖8所示。

圖8（a）表示TBBA算法在基于臂空間一隨機生成的分別包含5、10、20、30個搖臂的TMAB上的實驗結(jié)果。在相同的實驗輪數(shù)下，隨著臂數(shù)的增加，算法的準確度有所下降。但是在相同臂數(shù)中，TBBA算法隨著輪數(shù)的增加，性能逐步提升。當模型包含5、10個臂時，TBBA算法隨著實驗輪數(shù)的增加性能得到快速提升，并能保證穩(wěn)定性。在20、30個臂的TMAB中，均勻采樣方法喪失作用，但TBBA算法保持穩(wěn)步高速提升的性能，在3000輪時，算法的準確率超過80%。圖（b）表示TBBA算法在基于臂空間二中隨機生成包含50、100、150、200個臂的TMAB上的實驗結(jié)果。TBBA算法的性能隨著輪數(shù)的增加保持上升的趨勢。當臂數(shù)較小、輪數(shù)很少時，TBBA算法就具有很高的準確度;在臂數(shù)較大時，TBBA算法在短時間內(nèi)性能能得到快速提升。

實驗結(jié)果表明：TBBA算法在臂數(shù)不同的TMAB中，性能能保持穩(wěn)定上升;搖臂的個數(shù)越多時，TBBA算法的性能提升速度越快，越具有優(yōu)勢。

4.3 TBBA_tree、TTBA算法實驗結(jié)果

本節(jié)實驗以棋類博弈問題中棋手挑選出當前盤面下最具優(yōu)勢的動作為例。將每個己方和對方的可行動作對視為一個搖臂，每個搖臂的評估結(jié)果（勝、負、平）視為一個三元分布，并構(gòu)建了極大極小采樣樹模型。算法旨在識別根節(jié)點下的最

優(yōu)動作。同樣，葉子節(jié)點的分布概率值從臂空間中隨機選擇。

進行兩組實驗來驗證本文提出的極大極小采樣樹最優(yōu)動作識別算法（TTBA）的可行性和高效性。

第一組實驗驗證TTBA算法在樹結(jié)構(gòu)相同、上層下層確認難度組合不同的極大極小采樣樹中的性能。

本文設(shè)置了五

個3×3的兩層極大極小采樣樹結(jié)構(gòu)，它們的上下層確認難度

組合分別設(shè)定為：A表示上難下難，B表示上難下易，C表示

上易下難，D表示上易下易。最后，還構(gòu)造了一個基于臂空間

分區(qū)

一的隨機生成臂分布的E結(jié)構(gòu)。在A、B結(jié)構(gòu)中，TTBA算法、TBB_tree算法隨著輪數(shù)的增加準確率逐漸上升，TTBA算法的準確率基本在TBBA_tree算法準確率區(qū)間的中值之上;并且，由于TBBA_tree算法在不同上下層輪數(shù)分配下得到不同的準確率，這造成實驗結(jié)果有較大的標準差甚至還存在多個離群點。在C、D結(jié)構(gòu)中，TTBA算法與TBBA_tree算法、U算法的性能都基本達到了100%準確率。在E結(jié)構(gòu)中，由于樹結(jié)構(gòu)為3×3，每個節(jié)點下的動作集很小，因此上下層的三元多臂賭博機比較容易分辨。如圖9所示，TTBA算法有最高的準確率且不會出現(xiàn)波動區(qū)間和異常值，其標準差為0。U算法和TTBA_tree算法在不同采樣次數(shù)下的標準差如表4所示， 可以發(fā)現(xiàn)U算法相比TBBA_tree算法具有較大的標準差，即準確度波動更大。實驗結(jié)果表明：在不同確認難度組合的樹結(jié)構(gòu)中，TTBA算法具有最優(yōu)異的準確度性能，并且不會出現(xiàn)因上下層輪數(shù)劃分而產(chǎn)生的異常值和波動區(qū)間。

第二組實驗驗證TTBA算法在不同結(jié)構(gòu)的極大極小采樣樹中的性能，樹結(jié)構(gòu)中臂分布基于臂空間一隨機生成。本文首先設(shè)置了四種X×Y型樹結(jié)構(gòu)：A表示3×3、B表示10×3、C表示5×7、D表示3×10。X×Y表示根節(jié)點下有X個可行動作，每個第一層節(jié)點下有Y個可行動作。隨著輪數(shù)的增加，TBBA_tree算法、TTBA算法在每個結(jié)構(gòu)中整體保持著準確率上升的趨勢，當輪數(shù)值較大時算法的準確率稍有下降。TTBA算法在A、B結(jié)構(gòu)中的準確率基本能保持在TBBA_Ttree算法結(jié)果區(qū)間的上界浮動，與區(qū)間中值較為接近。在C、D結(jié)構(gòu)中，TTBA算法的準確率基本能超越TBBA_Ttree算法結(jié)果區(qū)間的上界，并且其中多個實驗結(jié)果表明TTBA算法的性能優(yōu)勢非常顯著。TBBA_tree算法在C、D結(jié)構(gòu)中實驗結(jié)果的波動區(qū)間很大，對于算法性能喪失表示性，而TTBA算法依然保持優(yōu)異的性能。

隨后，還給出了兩個特殊的樹結(jié)構(gòu)E：（18，3，9）和F：（2，4，6，6，12）（定義見3.1節(jié)的說明）。在E、F結(jié)構(gòu)中，TTBA算法同樣具有良好的性能，在不同的實驗輪數(shù)下，準確率基本超過80%。如表5所示是U算法和TBBA_tree算法在不同采樣次數(shù)下的標準差，可以看出U算法的標準差明顯大于TBBA_tree算法，而TTBA算法在不同采樣次數(shù)下的準確度都是一個數(shù)值，因此其標準差為0。

實驗結(jié)果表明：TTBA算法在不同結(jié)構(gòu)的極大極小采樣樹中都能保持穩(wěn)定優(yōu)異的性能，當樹結(jié)構(gòu)更加復雜時，TTBA算法的性能優(yōu)勢更加明顯。

5 結(jié)語

本文構(gòu)建了基于三元分布的多臂賭博機和極大極小采樣樹模型，并提出了一個基于貝葉斯思想和先驗鏈的三元多臂賭博機最優(yōu)臂確認算法TBBA;并進一步將TBBA算法應(yīng)用到極大極小采樣樹結(jié)構(gòu)中，給出了兩輪零和博弈問題下的最優(yōu) 動作識別算法TTBA。在實驗部分，本文建立了兩個精度不同的臂空間，并在其基礎(chǔ)上構(gòu)造了多個具有對比性的三元多臂賭博機、三元極大極小采樣樹結(jié)構(gòu)，驗證了本文所提出的TBBA、TTBA算法能夠有效地識別集合中的最優(yōu)對象。在未來的工作中，將基于本文的研究結(jié)果對不限深度、非滿樹的三元樹結(jié)構(gòu)進行研究，對其最優(yōu)動作識別問題的算法和理論分析進行探索，使得算法更加適用于兩名玩家完全信息零和博弈問題，并進一步探索強化學習問題[27-29]中的多名玩家非完全信息博弈問題。

參考文獻

[1]??SILVER D， HUANG A， MADDISON C J， et al. Mastering the? game of go with deep neural networks and tree search [J]. Nature， 2016， 529（7587）： 484-489.

[2]?SILVER D， SCHRITTWIESER J， SIMONYAN K， et al. Mastering the game of go without human knowledge [J]. Nature， 2017， 550（7676）： 354-359.

[3]?SILVER D， HUBERT T， SCHRITTWIESER J， et al. A general reinforcement learning algorithm that masters chess， shogi， and go through self-play[J]. Science， 2018， 362（6419）： 1140-1144.

[4]??GARIVIER A， KAUFMANN E， KOOLEN W M. Maximin action? identification： a new bandit framework for games [C]// Proceedings of the 29th Annual Conference on Learning Theory. [S.l.]： PMLR， 2016， 49： 1028-1050.?https：//arxiv.org/abs/1602.04676， 15 Feb 2016

[5]?THOMPSON W R. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples [J]. Biometrika， 1933， 25（3/4）： 285-294.

[6]?BUBECK S， CESA-BIANCHI N. Regret analysis of stochastic and nonstochastic multi-armed bandit problems [J]. Foundations & Trends in Machine Learning， 2012， 5（1）：1-112.

[7]?ROBBINS H. Some aspects of the sequential design of experiments [J]. Bulletin of the American Mathematical Society， 1952， 58（5）： 527-535

[8]?KALYANAKRISHNAN S， STONE P. Efficient selection of multiple bandit arms： theory and practice [C]// Proceedings of the 27th International Conference on Machine Learning. Cambridge， MA： MIT Press， 2010： 511-518.

[9]?EVEN-DAR E， MANNOR S， MANSOUR Y， et al. Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems [J]. Journal of Machine Learning Research， 2006， 7： 1079-1105.

[10]?KALYANAKRISHNAN S， TEWARI A， AUER P， et al. PAC subset selection in stochastic multi-armed bandits [C]// Proceedings of the 29th International Conference on Machine Learning. Cambridge， MA： MIT Press， 2012： 655-662.

[11]?KAUFMANN E， CAPPé O， GARIVIER A， et al. On the complexity of best-arm identification in multi-armed bandit models [J]. Journal of Machine Learning Research， 2016， 17（1）： 1-42.

[12]?MANNOR S， TSITSIKLIS J N. The sample complexity of exploration in the multi-armed bandit problem [J]. Journal of Machine Learning Research， 2004， 5： 623-648.

[13]?GARIVIER A， KAUFMANN E. Optimal best arm identification with fixed confidence [C]// Proceedings of the 29th Annual Conference on Learning Theory. [S.l.]： PMLR， 2016， 49： 998-1027.[C/OL]// Proceedings of the 29th Annul Conference on Learning Theory， 2016 [2018-11-13]. https：//arxiv.org/pdf/1602.04589.pdf.

[14]?AUDIBERT J-Y， BUBECK S， MUNOS R. Best arm identification in multi-armed bandits [C]// Proceedings of the 23rd Conference on Learning Theory. [S.l.]： PMLR， 2010： 41-53.

[15]?BUBECK S， WANG T， VISWANATHAN N. Multiple identifications in multi-armed bandits [C]// Proceedings of the 30th International Conference on Machine Learning. [S.l.]： PMLR， 2013， 28（1）： 258-265.

[16]??SHAHRAMPOUR S， NOSHAD M， TAROKH V. On sequential? elimination algorithms for best-arm identification in multi-armed bandits [J]. IEEE Transactions on Signal Processing， 2017， 65（16）： 4281-4292.

[17]?KAUFMANN E， KALYANAKRISHNAN S. Information complexity in bandit subset selection [C]// Proceedings of the 26th Conference on Learning Theory. [S.l.]： PMLR， 2013， 30： 228-251.

[18]?CARPENTIER A， LOCATELLI A. Tight （lower） bounds for the fixed budget best arm identification bandit problem [C]// Proceedings of the 29th Annual Conference on Learning Theory. [S.l.]： PMLR， 2016， 49： 590-604.

[19]??GABILLON V， GHAVAMZADEH M， LAZARIC A. Best arm? identification： a unified approach to fixed budget and fixed confidence [C]// Proceedings of the 25th International Conference on Neural Information Processing Systems. Cambridge， MA： MIT Press， 2012： 3212-3220.

[20]?CHAPELLE O， LI L. An empirical evaluation of Thompson sampling [C]// Proceedings of the 24th International Conference on Neural Information Processing Systems. New York： Curran Associates Inc， 2011： 2249-2257.

[21]?MAY B C， KORDA N， LEE A， et al. Optimistic Bayesian sampling in contextual-bandit problems [J]. Journal of Machine Learning Research， 2012， 13（1）：2069-2106.

[22]?KOMIYAMA J， HONDA J， NAKAGAWA H， et al. Optimal regret analysis of thompson sampling in stochastic multi-armed bandit problem with multiple plays[C]// Proceedings of the 32nd International Conference on Machine Learning. [S.l.]： PMLR， 2015： 1152-1161.

[23]?BROWNE C B， POWLEY E， WHITEHOUSE D， et al. A survey of monte carlo tree search methods [J]. IEEE Transactions on Computational Intelligence & AI in Games， 2012， 4（1）：1-43.

[24]?GELLY S， KOCSIS L， SCHOENAUER M， et al. The grand challenge of computer Go： monte carlo tree search and extensions [J]. Communications of the ACM， 2012， 55（3）：106-113.

[25]??TERAOKA K， HATANO K， TAKIMOTO E. Efficient sampling? method for Monte Carlo tree search problem[J]. IEICE Transactions on Information & Systems， 2014， E97-D（3）：392-398.

[26]?KAUFMANN E， KOOLEN W M. Monte-Carlo tree search by best arm identification[J]. arXiv E-print， 2017： arXiv：1706.02986.?Neural Information Processing Systems， 2017，30： 4897-4906. ?https：//arxiv.org/pdf/1706.02986.pdf

[27]?高陽， 陳世福， 陸鑫. 強化學習研究綜述[J]. 自動化學報， 2004， 30（1）：86-100. （GAO Y， CHEN S F， LU X. Research on reinforcement learning technology：a review [J]. Acta Automatica Sinica， 2004， 30（1）： 86-100.）

[28]?李寧， 高陽， 陸鑫，等.一種基于強化學習的學習Agent[J]. 計算機研究與發(fā)展， 2001， 38（9）：1051-1056. （LI N， GAO Y， LU X， et al. A learning agent based on reinforcement learning [J]. Journal of Computer Research and Development， 2001， 38（9）：1051-1056.）

[29]?蔡慶生， 張波. 一種基于Agent團隊的強化學習模型與應(yīng)用研究[J].計算機研究與發(fā)展， 2000， 37（9）：1087-1093. （CAI Q S， ZHANG B. An agent team based reinforcement learning model and its application [J]. Journal of Computer Research and Development， 2000， 37（9）： 1087-1093.）