基於模擬的搜索與蒙特卡羅樹搜索(MCTS)

• 2019 年 11 月 21 日
• 筆記

文章作者：劉建平Pinard 出品社區：DataFun 註：轉載請聯繫作者本人。

本文我們討論基於模型與不基於模型的強化學習方法：基於模擬的搜索(Simulation Based Search)。

本篇主要參考了UCL強化學習課程的第八講，第九講部分。

1. 基於模擬的搜索概述

什麼是基於模擬的搜索呢？當然主要是兩個點：一個是模擬，一個是搜索。模擬我們在上一篇也討論過，就是基於強化學習模型進行取樣，得到樣本數據。但是這是數據不是基於和環境交互獲得的真實數據，所以是「模擬」。對於搜索，則是為了利用模擬的樣本結果來幫我們計算到底應該採用什麼樣的動作，以實現我們的長期受益最大化。

那麼為什麼要進行基於模擬的搜索呢？在這之前我們先看看最簡單的前向搜索(forward search)。前向搜索演算法從當前我們考慮的狀態節點

開始考慮，怎麼考慮呢？對該狀態節點所有可能的動作進行擴展，建立一顆以

為根節點的搜索樹，這個搜索樹也是一個MDP，只是它是以當前狀態為根節點，而不是以起始狀態為根節點，所以也叫做sub-MDP。我們求解這個sub-MDP問題，然後得到

狀態最應該採用的動作

。前向搜索的sub-MDP如下圖：

前向搜索建立了一個sub-MDP來求解，這很精確，而且這在狀態動作數量都很少的時候沒有問題，但是只要稍微狀態動作數量多一點，每個狀態的選擇就都特別慢了，因此不太實用，此時基於模擬的搜索就是一種比較好的折衷。

2. 簡單蒙特卡羅搜索

首先我們看看基於模擬的搜索中比較簡單的一種方法：簡單蒙特卡羅搜索。

簡單蒙特卡羅搜索基於一個強化學習模型

和一個模擬策略

在此基礎上，對於當前我們要選擇動作的狀態

, 對每一個可能取樣的動作

,都進行

輪取樣，這樣每個動作

都會得到K組經歷完整的狀態序列(episode)。即：

現在對於每個

組合，我們可以基於蒙特卡羅法來計算其動作價值函數並選擇最優的動作了。

簡單蒙特卡羅搜索和起前向搜索比起來，對於狀態動作數量的處理能力上了一個數量級,可以處理中等規模的問題。但是假如我們的狀態動作數量達到非常大的量級，比如圍棋的級別,那麼簡單蒙特卡羅搜索也太慢了。同時，由於使用蒙特卡羅法計算其動作價值函數，模擬取樣得到的一些中間狀態和對應行為的價值就被忽略了，這部分數據能不能利用起來呢？

下面我們看看蒙特卡羅樹搜索(Monte-Carlo Tree Search，以下簡稱MCTS)怎麼優化這個問題的解決方案。

3. MCTS的原理

MCTS摒棄了簡單蒙特卡羅搜索裡面對當前狀態

每個動作都要進行K次模擬取樣的做法，而是總共對當前狀態

進行K次取樣，這樣取樣到的動作只是動作全集

中的一部分。這樣做大大降低了取樣的數量和取樣後的搜索計算。當然，代價是可能動作全集中的很多動作都沒有取樣到，可能錯失好的動作選擇，這是一個演算法設計上的折衷。

在MCTS中，基於一個強化學習模型

和一個模擬策略

，當前狀態

對應的完整的狀態序列(episode)是這樣的：

取樣完畢後，我們可以基於取樣的結果構建一顆MCTS的搜索樹，然後近似計算

和最大

對應的動作。

MCTS搜索的策略分為兩個階段：第一個是樹內策略(tree policy)：為當模擬取樣得到的狀態存在於當前的MCTS時使用的策略。樹內策略可以使

貪婪策略，隨著模擬的進行策略可以得到持續改善，還可以使用上限置信區間演算法UCT，這在棋類遊戲中很普遍；第二個是默認策略(default policy)：如果當前狀態不在MCTS內，使用默認策略來完成整個狀態序列的取樣，並把當前狀態納入到搜索樹中。默認策略可以使隨機策略或基於目標價值函數的策略。

這裡講到的是最經典的強化學習終MCTS的用戶，每一步都有延時獎勵，但是在棋類之類的零和問題中，中間狀態是沒有明確獎勵的，我們只有在棋下完後知道輸贏了才能對前面的動作進行狀態獎勵，對於這類問題我們的MCTS需要做一些結構上的細化。

4. 上限置信區間演算法UCT

在討論棋類遊戲的MCTS搜索之前，我們先熟悉下上限置信區間演算法(Upper Confidence Bound Applied to Trees, 以下簡稱UCT)。它是一種策略演算法，我們之前最常用的是

貪婪策略。但是在棋類問題中，UCT更常使用。

在棋類遊戲中，經常有這樣的問題，我們發現在某種棋的狀態下，有2個可選動作，第一個動作歷史棋局中是0勝1負，第二個動作歷史棋局中是8勝10負，那麼我們應該選擇哪個動作好呢？如果按

貪婪策略，則第二個動作非常容易被選擇到。但是其實雖然第一個動作勝利0%，但是很可能是因為這個動作的歷史棋局少，數據不夠導致的，很可能該動作也是一個不錯的動作。那麼我們如何在最優策略和探索度達到一個選擇平衡呢？

貪婪策略可以用，但是UCT是一個更不錯的選擇。

UCT首先計算每一個可選動作節點對應的分數，這個分數考慮了歷史最優策略和探索度嗎，一個常用的公式如下：

其中，

是

節點的勝利次數，

是i節點的模擬次數，

是所有模擬次數，c 是探索常數，理論值為

，可根據經驗調整，c 越大就越偏向於廣度搜索，c 越小就越偏向於深度搜索。最後我們選擇分數最高的動作節點。

比如對於下面的棋局，對於根節點來說，有3個選擇，第一個選擇7勝3負，第二個選擇5勝3負，第三個選擇0勝3負。

如果我們取c=10,則第一個節點的分數為：

第二個節點的分數為：

第三個節點的分數為：

可見，由於我們把探索率c設置的比較大，第三個節點是被UCT選中要執行的動作節點。當然如果我們把c設置的比較小的話，第一個或者第二個可能就變成最大的分數了。

5. 棋類遊戲MCTS搜索

在像中國象棋，圍棋這樣的零和問題中，一個動作只有在棋局結束才能拿到真正的獎勵，因此我們對MCTS的搜索步驟和樹結構上需要根據問題的不同做一些細化。

對於MCTS的樹結構，如果是最簡單的方法，只需要在節點上保存狀態對應的歷史勝負記錄。在每條邊上保存取樣的動作。這樣MCTS的搜索需要走4步，如下圖(圖來自維基百科)：

第一步是選擇(Selection):這一步會從根節點開始，每次都選一個「最值得搜索的子節點」，一般使用UCT選擇分數最高的節點，直到來到一個「存在未擴展的子節點」的節點，如圖中的 3/3 節點。之所以叫做「存在未擴展的子節點」，是因為這個局面存在未走過的後續著法，也就是MCTS中沒有後續的動作可以參考了。這時我們進入第二步。

第二步是擴展(Expansion)，在這個搜索到的存在未擴展的子節點，加上一個0/0的子節點，表示沒有歷史記錄參考。這時我們進入第三步。

第三步是模擬(simulation)，從上面這個沒有試過的著法開始，用一個簡單策略比如快速走子策略（Rollout policy）走到底，得到一個勝負結果。快速走子策略一般適合選擇走子很快可能不是很精確的策略。因為如果這個策略走得慢，結果雖然會更準確，但由於耗時多了，在單位時間內的模擬次數就少了，所以不一定會棋力更強，有可能會更弱。這也是為什麼我們一般只模擬一次，因為如果模擬多次，雖然更準確，但更慢。

第四步是回溯(backpropagation), 將我們最後得到的勝負結果回溯加到MCTS樹結構上。注意除了之前的MCTS樹要回溯外，新加入的節點也要加上一次勝負歷史記錄，如上圖最右邊所示。

以上就是MCTS搜索的整個過程。這4步一般是通用的，但是MCTS樹結構上保存的內容而一般根據要解決的問題和建模的複雜度而不同。

6. MCTS小結

MCTS通過取樣建立MCTS搜索樹，並基於4大步驟選擇，擴展，模擬和回溯來持續優化樹內的策略，進而可以幫助對狀態下的動作進行選擇，非常適合狀態數，動作數海量的強化學習問題。比如AlphaGo和AlphaGo Zero都重度使用了MCTS搜索，我們在下一篇討論AlphaGo Zero如何結合MCTS和神經網路來求解圍棋強化學習問題。

原文鏈接：

https://www.cnblogs.com/pinard/p/10470571.html