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

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

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

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

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

基礎理論：

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

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

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

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

5）Expert Iteration：搜索算法基于單個狀態s0的規劃模型動作，但不學習推廣到不同位置的信息。相比之下，深度神經網絡能夠在狀態空間中推廣知識。專家迭代算法將基于搜索的規劃方法和深度學習進行了結合，其中規劃算法作為專家，用于發現對當前策略的改進內容。神經網絡算法作為學員，其模仿專家的策略并計算值函數。

Policy Gradient Search

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

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

作者使用策略梯度強化學習方法來訓練模擬策略。模擬策略由具有與全局策略網絡相同的體系結構的神經網絡表示。在每個游戲開始時，策略網絡的參數被設置為全局策略網絡的參數。

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

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

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

Parameter Freezing during Online Adaptation

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

Note on Batch Normalisation

神經網絡使用批量標準化。在所有情況下，全局神經網絡已經在來自許多獨立采樣的Hex游戲的狀態數據集上進行了訓練。

實驗

Policy Gradient Search as an Online Planner

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

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

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

Policy Gradient Search Expert Iteration

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

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

結論

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

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

實驗結果顯示PGS-EXIT在專家迭代算法框架中性能明顯優于MCS，并且還提供了第一個經驗數據，表明MCTS-EXIT算法優于傳統的策略迭代方法。

這項工作中提出的結果主要關注Hex的確定性和離散動作空間域。這使得模型的效果可以與MCTS直接比較，但PGS最激動人心的潛在應用是MCTS不易使用的問題，例如隨機狀態轉換或連續動作空間的問題。