基于三元多臂賭博機(jī)的樹(shù)結(jié)構(gòu)最優(yōu)動(dòng)作識(shí)別

劉郭慶 王婕婷 胡治國(guó) 錢(qián)宇華

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

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

中圖分類號(hào)：?TP181

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

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

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

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

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

本文的主要工作如下：

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

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

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

1 相關(guān)工作

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

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

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

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

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

2 三元多臂賭博機(jī)的最優(yōu)臂確認(rèn)

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

2.1 基于三元分布的多臂賭博機(jī)

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

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

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

（1）

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

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

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

1）反饋值的獲取。

當(dāng)算法運(yùn)行至第t輪并按照選臂策略從臂集A中選擇采樣臂At后，再根據(jù)At的分布概率 μ At=（μAt1， μAt2， μAt3）進(jìn)行采樣并得到一個(gè)三元反饋值 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）的狄利克雷分布，即對(duì)于每個(gè)臂a∈{1，2，…，K}，在第t輪時(shí)其先驗(yàn)分布為：

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

（3）

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

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

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)貝葉斯估計(jì)的后驗(yàn)分布可以視為參數(shù)為 θ Att= θ??? ·?? Att+ R t的狄利克雷分布，用B函數(shù)將它標(biāo)準(zhǔn)化就得到本文算法的后驗(yàn)分布為：

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

（5）

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

3）采樣臂的選擇。

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

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

（6）

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

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

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

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）

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

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

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

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

程序前

1）

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

2）

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

3）

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

4）

進(jìn)行隨機(jī)采樣： ???at=D（ θ at-1）

5）

End For

6）

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

7）

對(duì)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）計(jì)算得到每個(gè)臂的分布概率近似值

12）

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

程序后

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

3 三元極大極小采樣樹(shù)最優(yōu)動(dòng)作識(shí)別

3.1 基于三元分布的極大極小采樣樹(shù)

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

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

TMST最優(yōu)動(dòng)作識(shí)別算法的目標(biāo)是在有限的輪數(shù)T內(nèi)，識(shí)別出玩家A在可行動(dòng)作集合中的最優(yōu)動(dòng)作i*。因?yàn)榱愫筒┺倪^(guò)程中玩家A和B為競(jìng)爭(zhēng)關(guān)系，因此，算法不能簡(jiǎn)單地從所有的葉子節(jié)點(diǎn)中選擇最有優(yōu)勢(shì)的節(jié)點(diǎn)

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

（9）

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

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

（10）

其中對(duì)于每一個(gè)動(dòng)作組i：

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

（11）

3.2 TMST最優(yōu)動(dòng)作識(shí)別算法

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

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

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

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

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

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

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

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

輸出? 算法確認(rèn)的最優(yōu)動(dòng)作 。

程序前

1）

對(duì)臂集P={（i， j）：1≤i≤K，1≤j≤Ji}中的每一個(gè)臂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）

進(jìn)行隨機(jī)采樣： ??i， jt～D（ θ i， jt-1）

6）

End for

7）

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

8）

End for

9）

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

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

10）

對(duì)搖臂Pt=（It， JIt，t）進(jìn)行采樣并得到反饋值： ???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）

得到每個(gè)搖臂分布概率的近似值：

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)動(dòng)作：

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

其中對(duì)于每一個(gè)動(dòng)作i：

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

程序后

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

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

4 實(shí)驗(yàn)與結(jié)果分析

4.1 度量標(biāo)準(zhǔn)

本文提出的TBBA、TTBA算法的目標(biāo)都是識(shí)別一個(gè)集合中最優(yōu)對(duì)象，因此，本文將準(zhǔn)確率作為算法的性能評(píng)估指標(biāo)，其定義為：

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

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

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

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

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

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

4.2 TBBA算法實(shí)驗(yàn)結(jié)果

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

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

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

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

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

4.3 TBBA_tree、TTBA算法實(shí)驗(yàn)結(jié)果

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

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

進(jìn)行兩組實(shí)驗(yàn)來(lái)驗(yàn)證本文提出的極大極小采樣樹(shù)最優(yōu)動(dòng)作識(shí)別算法（TTBA）的可行性和高效性。

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

本文設(shè)置了五

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

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

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

分區(qū)

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

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

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

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

5 結(jié)語(yǔ)

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

參考文獻(xiàn)

[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]?高陽(yáng)， 陳世福， 陸鑫. 強(qiáng)化學(xué)習(xí)研究綜述[J]. 自動(dòng)化學(xué)報(bào)， 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]?李寧， 高陽(yáng)， 陸鑫，等.一種基于強(qiáng)化學(xué)習(xí)的學(xué)習(xí)Agent[J]. 計(jì)算機(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團(tuán)隊(duì)的強(qiáng)化學(xué)習(xí)模型與應(yīng)用研究[J].計(jì)算機(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.）