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

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

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

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

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

基礎(chǔ)理論：

1）Markov Decision Processes（MDP）：馬爾可夫決策過程在每個時間間隔t中，代理觀察狀態(tài)并選擇要采取的動作。對于終止狀態(tài)，需要最大化階段性獎勵R。

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

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

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

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

Policy Gradient Search

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

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

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

由于評估模擬策略代價很大，所以該算法不會模擬到終止狀態(tài)，而是使用截斷的蒙特卡羅算法模擬。選擇何時截斷模擬并不簡單，最佳選擇策略可能取決于MDP本身。如果模擬太短，可能無法包含新的信息，或者沒有給出足夠長的時間范圍搜索。太長的模擬則會導致恨到的時間開銷。

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

因為在每次模擬中都要訪問根節(jié)點，與 MCS 一樣，可以使用基于單狀態(tài)的強化學習方法來選擇每個模擬的第一個動作。采用PUCT公式，選擇令下式的值的動作：

Parameter Freezing during Online Adaptation

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

Note on Batch Normalisation

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

實驗

Policy Gradient Search as an Online Planner

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

每個智能體在每次移動使用800次搜索迭代，不會在移動之間思考。實驗結(jié)果見下表。

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

Policy Gradient Search Expert Iteration

作者使用PGS作為專家迭代算法中的專家進行實驗，并與MCS和MCTS進行比較。

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

結(jié)論

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

在專家迭代算法的框架中使用PGS時，PGS在訓練期間也很有效，該算法在不使用搜索樹的情況下，訓練了第一個有競爭力的Hex代理tabula rasa。相比之下，該算法比類似的強化學習算法和使用MCTS專家的專家迭代算法性能要好。

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

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