一種替代性的基于模擬的搜索方法，即策略梯度搜索

蒙特卡羅樹搜索（MCTS）算法執(zhí)行基于模擬的搜索以改進(jìn)在線策略。在搜索過程中，模擬策略適用于探索最有希望的游戲策略。MCTS已被用于處理許多最新的程序問題，但MCTS的一個(gè)缺點(diǎn)是需要評(píng)估狀態(tài)值并存儲(chǔ)其結(jié)果，這在分支樹非常多的游戲場(chǎng)景中并不適用。

作者提出了一種替代性的基于模擬的搜索方法，即策略梯度搜索（PGS），該方法通過策略梯度更新在線調(diào)整神經(jīng)網(wǎng)絡(luò)模擬策略，避免了對(duì)搜索樹的需求。在Hex中，PGS實(shí)現(xiàn)了與MCTS相當(dāng)?shù)男阅?，并且使用專家迭代算法（Expert Iteration）和 PGS訓(xùn)練的模型擊敗了MoHex 2.0，這是目前最強(qiáng)的開源Hex代理。

蒙特卡羅樹搜索（MCTS）在Go和Hex等游戲中實(shí)現(xiàn)最大測(cè)試時(shí)間性能的價(jià)值早已為人所知。最近的研究表明，在許多經(jīng)典的棋盤類游戲中，通過專家迭代算法將規(guī)劃方法納入強(qiáng)化學(xué)習(xí)智能體的訓(xùn)練，可以使用純RL方法實(shí)現(xiàn)最好的性能。

但是，MCTS構(gòu)建一個(gè)顯式搜索樹，每個(gè)節(jié)點(diǎn)會(huì)存儲(chǔ)其訪問數(shù)和估計(jì)值。所以在MCTS中需要多次訪問搜索樹中的節(jié)點(diǎn)。這種方法適用許多經(jīng)典的棋盤游戲，但在許多現(xiàn)實(shí)世界的問題中，分支樹都會(huì)非常大，這使得MCTS難以使用。大量的分支樹可能由非常大的動(dòng)作空間或偶然節(jié)點(diǎn)引起。在動(dòng)作空間很大時(shí)，可以使用先前策略來(lái)降低弱動(dòng)作的影響，從而減少有效分支樹。隨機(jī)轉(zhuǎn)換更難以處理，因?yàn)橄惹暗牟呗圆荒苡糜跍p少偶然節(jié)點(diǎn)處的分支因子。

相比之下，蒙特卡羅搜索（MCS）算法沒有這樣的要求。MCTS使用每個(gè)節(jié)點(diǎn)中的值估計(jì)來(lái)調(diào)整模擬策略，而MCS算法在整個(gè)搜索過程中都有固定的模擬策略。但是，由于MCS在搜索過程中不能提高模擬質(zhì)量，因此它的效果會(huì)明顯弱于MCTS。

基礎(chǔ)理論：

1）Markov Decision Processes（MDP）：馬爾可夫決策過程在每個(gè)時(shí)間間隔t中，代理觀察狀態(tài)并選擇要采取的動(dòng)作。對(duì)于終止?fàn)顟B(tài)，需要最大化階段性獎(jiǎng)勵(lì)R。

2）Hex：Hex 是一個(gè)基于雙人的基于連接的游戲，在n×n六邊形網(wǎng)格上進(jìn)行。游戲雙方分別用黑色和白色棋子表示，雙方輪流在空的位置上放置自己的棋子。如果白棋從左到右連續(xù)成線則白棋贏，若黑色棋子從上到下連成線則黑棋贏，下圖是白棋贏的示意圖。

3）Monte Carlo Tree Search（MCTS）：蒙特卡羅樹搜索是一種隨時(shí)可用的最佳樹搜索算法。它使用重復(fù)的游戲模擬來(lái)估計(jì)狀態(tài)值，并使用更優(yōu)的游戲策略進(jìn)一步擴(kuò)展搜索樹。當(dāng)所有分支都模擬完成后，采取reward值最高的action。

4）Monte Carlo Search（MCS）：蒙特卡羅搜索是一種比MCTS更簡(jiǎn)單的搜索算法。給定狀態(tài)和策略，通過迭代的模擬選擇評(píng)估值最高的策略。

5）Expert Iteration：搜索算法基于單個(gè)狀態(tài)s0的規(guī)劃模型動(dòng)作，但不學(xué)習(xí)推廣到不同位置的信息。相比之下，深度神經(jīng)網(wǎng)絡(luò)能夠在狀態(tài)空間中推廣知識(shí)。專家迭代算法將基于搜索的規(guī)劃方法和深度學(xué)習(xí)進(jìn)行了結(jié)合，其中規(guī)劃算法作為專家，用于發(fā)現(xiàn)對(duì)當(dāng)前策略的改進(jìn)內(nèi)容。神經(jīng)網(wǎng)絡(luò)算法作為學(xué)員，其模仿專家的策略并計(jì)算值函數(shù)。

Policy Gradient Search

策略梯度搜索通過應(yīng)用無(wú)模型的強(qiáng)化學(xué)習(xí)算法來(lái)適應(yīng)蒙特卡羅搜索中的模擬過程。作者假設(shè)提供先驗(yàn)策略π和先驗(yàn)值函數(shù)V，并在完整MDP上訓(xùn)練。

該算法必須對(duì)它通過非表格函數(shù)逼近器學(xué)習(xí)的所有內(nèi)容進(jìn)行表示，否則它將遇到與MCTS相同的問題。MCTS已經(jīng)是一種自我對(duì)弈強(qiáng)化學(xué)習(xí)方法，但不能直接使其適應(yīng)函數(shù)逼近，因?yàn)閁CT公式依賴于基于訪問量的探索規(guī)則。

作者使用策略梯度強(qiáng)化學(xué)習(xí)方法來(lái)訓(xùn)練模擬策略。模擬策略由具有與全局策略網(wǎng)絡(luò)相同的體系結(jié)構(gòu)的神經(jīng)網(wǎng)絡(luò)表示。在每個(gè)游戲開始時(shí)，策略網(wǎng)絡(luò)的參數(shù)被設(shè)置為全局策略網(wǎng)絡(luò)的參數(shù)。

由于評(píng)估模擬策略代價(jià)很大，所以該算法不會(huì)模擬到終止?fàn)顟B(tài)，而是使用截?cái)嗟拿商乜_算法模擬。選擇何時(shí)截?cái)嗄M并不簡(jiǎn)單，最佳選擇策略可能取決于MDP本身。如果模擬太短，可能無(wú)法包含新的信息，或者沒有給出足夠長(zhǎng)的時(shí)間范圍搜索。太長(zhǎng)的模擬則會(huì)導(dǎo)致恨到的時(shí)間開銷。

對(duì)于Hex，作者使用與MCTS算法相同的策略：運(yùn)行每個(gè)模擬過程，直到模擬的動(dòng)作序列是唯一的。一旦我們?cè)趖步之后達(dá)到模擬的終止?fàn)顟B(tài)sL，使用全局值網(wǎng)絡(luò)V估計(jì)該狀態(tài)的值，并使用該估計(jì)更新模擬策略參數(shù)θ，其中α是學(xué)習(xí)率，其值在-1和1之間，對(duì)于其他問題，可能需要非零基線。可以將這些更新視為微調(diào)當(dāng)前子游戲的全局策略。

因?yàn)樵诿看文M中都要訪問根節(jié)點(diǎn)，與 MCS 一樣，可以使用基于單狀態(tài)的強(qiáng)化學(xué)習(xí)方法來(lái)選擇每個(gè)模擬的第一個(gè)動(dòng)作。采用PUCT公式，選擇令下式的值的動(dòng)作：

Parameter Freezing during Online Adaptation

在測(cè)試期間，在線搜索算法通常受在時(shí)間約束的情況下使用，因此，與標(biāo)準(zhǔn)RL問題相比，其使用數(shù)量級(jí)更少的模擬。還需要注意的是，要確保該算法在每個(gè)模擬步驟中不需要太多計(jì)算。當(dāng)在專家迭代中用于離線訓(xùn)練時(shí)，搜索方法的效率仍然至關(guān)重要。

Note on Batch Normalisation

神經(jīng)網(wǎng)絡(luò)使用批量標(biāo)準(zhǔn)化。在所有情況下，全局神經(jīng)網(wǎng)絡(luò)已經(jīng)在來(lái)自許多獨(dú)立采樣的Hex游戲的狀態(tài)數(shù)據(jù)集上進(jìn)行了訓(xùn)練。

實(shí)驗(yàn)

Policy Gradient Search as an Online Planner

作者在Hex游戲中評(píng)估PGS。Hex具有中等數(shù)量的分支因子和確定性轉(zhuǎn)換，這意味著MCTS在該領(lǐng)域中非常有效，這使作者能夠直接比較PGS與MCTS的強(qiáng)度。作者在原始神經(jīng)網(wǎng)絡(luò)和四個(gè)搜索算法MCS，MCTS，PGS和PGS-UF之間進(jìn)行了循環(huán)對(duì)弈，其中參數(shù)可變。為了克服Hex中第一個(gè)玩家具有的優(yōu)勢(shì)，每對(duì)智能體互相打了2*n*n場(chǎng)比賽。

每個(gè)智能體在每次移動(dòng)使用800次搜索迭代，不會(huì)在移動(dòng)之間思考。實(shí)驗(yàn)結(jié)果見下表。

如果策略搜索的能力已經(jīng)飽和，那么PGS的擴(kuò)展可能不如MCTS，但是并沒有發(fā)現(xiàn)在游戲中會(huì)出現(xiàn)這種情況。但是，在每次移動(dòng)中進(jìn)行1600次迭代仍然是一個(gè)相當(dāng)短的搜索，這樣的情況可能會(huì)發(fā)生在較長(zhǎng)時(shí)間的搜索過程中。

Policy Gradient Search Expert Iteration

作者使用PGS作為專家迭代算法中的專家進(jìn)行實(shí)驗(yàn)，并與MCS和MCTS進(jìn)行比較。

結(jié)果表明，PGS的性能優(yōu)于MCS，但不如MCTS。在訓(xùn)練過程中，在反復(fù)應(yīng)用更好或更差的專家時(shí)，智能體的差異更加復(fù)雜多變。

結(jié)論

作者提出了PGS算法，這是一種在線規(guī)劃的搜索算法，不需要顯式搜索樹。PGS是一種有效的規(guī)劃算法。實(shí)驗(yàn)結(jié)果證明，在9x9和13x13 的Hex游戲中，它的性能略微弱于MCTS，但與MCTS相比具有競(jìng)爭(zhēng)力，同時(shí)其決策時(shí)間顯著性能優(yōu)于MCS。

在專家迭代算法的框架中使用PGS時(shí)，PGS在訓(xùn)練期間也很有效，該算法在不使用搜索樹的情況下，訓(xùn)練了第一個(gè)有競(jìng)爭(zhēng)力的Hex代理tabula rasa。相比之下，該算法比類似的強(qiáng)化學(xué)習(xí)算法和使用MCTS專家的專家迭代算法性能要好。

實(shí)驗(yàn)結(jié)果顯示PGS-EXIT在專家迭代算法框架中性能明顯優(yōu)于MCS，并且還提供了第一個(gè)經(jīng)驗(yàn)數(shù)據(jù)，表明MCTS-EXIT算法優(yōu)于傳統(tǒng)的策略迭代方法。

這項(xiàng)工作中提出的結(jié)果主要關(guān)注Hex的確定性和離散動(dòng)作空間域。這使得模型的效果可以與MCTS直接比較，但PGS最激動(dòng)人心的潛在應(yīng)用是MCTS不易使用的問題，例如隨機(jī)狀態(tài)轉(zhuǎn)換或連續(xù)動(dòng)作空間的問題。