蒙特卡羅樹搜索(MCTS)算法執(zhí)行基于模擬的搜索以改進(jìn)在線策略。在搜索過程中,模擬策略適用于探索最有希望的游戲策略。MCTS已被用于處理許多最新的程序問題,但MCTS的一個缺點(diǎn)是需要評估狀態(tài)值并存儲其結(jié)果,這在分支樹非常多的游戲場景中并不適用。
作者提出了一種替代性的基于模擬的搜索方法,即策略梯度搜索(PGS),該方法通過策略梯度更新在線調(diào)整神經(jīng)網(wǎng)絡(luò)模擬策略,避免了對搜索樹的需求。在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)最大測試時間性能的價(jià)值早已為人所知。最近的研究表明,在許多經(jīng)典的棋盤類游戲中,通過專家迭代算法將規(guī)劃方法納入強(qiáng)化學(xué)習(xí)智能體的訓(xùn)練,可以使用純RL方法實(shí)現(xiàn)最好的性能。
但是,MCTS構(gòu)建一個顯式搜索樹,每個節(jié)點(diǎn)會存儲其訪問數(shù)和估計(jì)值。所以在MCTS中需要多次訪問搜索樹中的節(jié)點(diǎn)。這種方法適用許多經(jīng)典的棋盤游戲,但在許多現(xiàn)實(shí)世界的問題中,分支樹都會非常大,這使得MCTS難以使用。大量的分支樹可能由非常大的動作空間或偶然節(jié)點(diǎn)引起。在動作空間很大時,可以使用先前策略來降低弱動作的影響,從而減少有效分支樹。隨機(jī)轉(zhuǎn)換更難以處理,因?yàn)橄惹暗牟呗圆荒苡糜跍p少偶然節(jié)點(diǎn)處的分支因子。
相比之下,蒙特卡羅搜索(MCS)算法沒有這樣的要求。MCTS使用每個節(jié)點(diǎn)中的值估計(jì)來調(diào)整模擬策略,而MCS算法在整個搜索過程中都有固定的模擬策略。但是,由于MCS在搜索過程中不能提高模擬質(zhì)量,因此它的效果會明顯弱于MCTS。
基礎(chǔ)理論:
1)Markov Decision Processes(MDP):馬爾可夫決策過程在每個時間間隔t中,代理觀察狀態(tài)并選擇要采取的動作。對于終止?fàn)顟B(tài),需要最大化階段性獎勵R。
2)Hex:Hex 是一個基于雙人的基于連接的游戲,在n×n六邊形網(wǎng)格上進(jìn)行。游戲雙方分別用黑色和白色棋子表示,雙方輪流在空的位置上放置自己的棋子。如果白棋從左到右連續(xù)成線則白棋贏,若黑色棋子從上到下連成線則黑棋贏,下圖是白棋贏的示意圖。
3)Monte Carlo Tree Search(MCTS):蒙特卡羅樹搜索是一種隨時可用的最佳樹搜索算法。它使用重復(fù)的游戲模擬來估計(jì)狀態(tài)值,并使用更優(yōu)的游戲策略進(jìn)一步擴(kuò)展搜索樹。當(dāng)所有分支都模擬完成后,采取reward值最高的action。
4)Monte Carlo Search(MCS):蒙特卡羅搜索是一種比MCTS更簡單的搜索算法。給定狀態(tài)和策略,通過迭代的模擬選擇評估值最高的策略。
5)Expert Iteration:搜索算法基于單個狀態(tài)s0的規(guī)劃模型動作,但不學(xué)習(xí)推廣到不同位置的信息。相比之下,深度神經(jīng)網(wǎng)絡(luò)能夠在狀態(tài)空間中推廣知識。專家迭代算法將基于搜索的規(guī)劃方法和深度學(xué)習(xí)進(jìn)行了結(jié)合,其中規(guī)劃算法作為專家,用于發(fā)現(xiàn)對當(dāng)前策略的改進(jìn)內(nèi)容。神經(jīng)網(wǎng)絡(luò)算法作為學(xué)員,其模仿專家的策略并計(jì)算值函數(shù)。
Policy Gradient Search
策略梯度搜索通過應(yīng)用無模型的強(qiáng)化學(xué)習(xí)算法來適應(yīng)蒙特卡羅搜索中的模擬過程。作者假設(shè)提供先驗(yàn)策略π和先驗(yàn)值函數(shù)V,并在完整MDP上訓(xùn)練。
該算法必須對它通過非表格函數(shù)逼近器學(xué)習(xí)的所有內(nèi)容進(jìn)行表示,否則它將遇到與MCTS相同的問題。MCTS已經(jīng)是一種自我對弈強(qiáng)化學(xué)習(xí)方法,但不能直接使其適應(yīng)函數(shù)逼近,因?yàn)閁CT公式依賴于基于訪問量的探索規(guī)則。
作者使用策略梯度強(qiáng)化學(xué)習(xí)方法來訓(xùn)練模擬策略。模擬策略由具有與全局策略網(wǎng)絡(luò)相同的體系結(jié)構(gòu)的神經(jīng)網(wǎng)絡(luò)表示。在每個游戲開始時,策略網(wǎng)絡(luò)的參數(shù)被設(shè)置為全局策略網(wǎng)絡(luò)的參數(shù)。
由于評估模擬策略代價(jià)很大,所以該算法不會模擬到終止?fàn)顟B(tài),而是使用截?cái)嗟拿商乜_算法模擬。選擇何時截?cái)嗄M并不簡單,最佳選擇策略可能取決于MDP本身。如果模擬太短,可能無法包含新的信息,或者沒有給出足夠長的時間范圍搜索。太長的模擬則會導(dǎo)致恨到的時間開銷。
對于Hex,作者使用與MCTS算法相同的策略:運(yùn)行每個模擬過程,直到模擬的動作序列是唯一的。一旦我們在t步之后達(dá)到模擬的終止?fàn)顟B(tài)sL,使用全局值網(wǎng)絡(luò)V估計(jì)該狀態(tài)的值,并使用該估計(jì)更新模擬策略參數(shù)θ,其中α是學(xué)習(xí)率,其值在-1和1之間,對于其他問題,可能需要非零基線。可以將這些更新視為微調(diào)當(dāng)前子游戲的全局策略。
因?yàn)樵诿看文M中都要訪問根節(jié)點(diǎn),與 MCS 一樣,可以使用基于單狀態(tài)的強(qiáng)化學(xué)習(xí)方法來選擇每個模擬的第一個動作。采用PUCT公式,選擇令下式的值的動作:
Parameter Freezing during Online Adaptation
在測試期間,在線搜索算法通常受在時間約束的情況下使用,因此,與標(biāo)準(zhǔn)RL問題相比,其使用數(shù)量級更少的模擬。還需要注意的是,要確保該算法在每個模擬步驟中不需要太多計(jì)算。當(dāng)在專家迭代中用于離線訓(xùn)練時,搜索方法的效率仍然至關(guān)重要。
Note on Batch Normalisation
神經(jīng)網(wǎng)絡(luò)使用批量標(biāo)準(zhǔn)化。在所有情況下,全局神經(jīng)網(wǎng)絡(luò)已經(jīng)在來自許多獨(dú)立采樣的Hex游戲的狀態(tài)數(shù)據(jù)集上進(jìn)行了訓(xùn)練。
實(shí)驗(yàn)
Policy Gradient Search as an Online Planner
作者在Hex游戲中評估PGS。Hex具有中等數(shù)量的分支因子和確定性轉(zhuǎn)換,這意味著MCTS在該領(lǐng)域中非常有效,這使作者能夠直接比較PGS與MCTS的強(qiáng)度。作者在原始神經(jīng)網(wǎng)絡(luò)和四個搜索算法MCS,MCTS,PGS和PGS-UF之間進(jìn)行了循環(huán)對弈,其中參數(shù)可變。為了克服Hex中第一個玩家具有的優(yōu)勢,每對智能體互相打了2*n*n場比賽。
每個智能體在每次移動使用800次搜索迭代,不會在移動之間思考。實(shí)驗(yàn)結(jié)果見下表。
如果策略搜索的能力已經(jīng)飽和,那么PGS的擴(kuò)展可能不如MCTS,但是并沒有發(fā)現(xiàn)在游戲中會出現(xiàn)這種情況。但是,在每次移動中進(jìn)行1600次迭代仍然是一個相當(dāng)短的搜索,這樣的情況可能會發(fā)生在較長時間的搜索過程中。
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)用更好或更差的專家時,智能體的差異更加復(fù)雜多變。
結(jié)論
作者提出了PGS算法,這是一種在線規(guī)劃的搜索算法,不需要顯式搜索樹。PGS是一種有效的規(guī)劃算法。實(shí)驗(yàn)結(jié)果證明,在9x9和13x13 的Hex游戲中,它的性能略微弱于MCTS,但與MCTS相比具有競爭力,同時其決策時間顯著性能優(yōu)于MCS。
在專家迭代算法的框架中使用PGS時,PGS在訓(xùn)練期間也很有效,該算法在不使用搜索樹的情況下,訓(xùn)練了第一個有競爭力的Hex代理tabula rasa。相比之下,該算法比類似的強(qiáng)化學(xué)習(xí)算法和使用MCTS專家的專家迭代算法性能要好。
實(shí)驗(yàn)結(jié)果顯示PGS-EXIT在專家迭代算法框架中性能明顯優(yōu)于MCS,并且還提供了第一個經(jīng)驗(yàn)數(shù)據(jù),表明MCTS-EXIT算法優(yōu)于傳統(tǒng)的策略迭代方法。
這項(xiàng)工作中提出的結(jié)果主要關(guān)注Hex的確定性和離散動作空間域。這使得模型的效果可以與MCTS直接比較,但PGS最激動人心的潛在應(yīng)用是MCTS不易使用的問題,例如隨機(jī)狀態(tài)轉(zhuǎn)換或連續(xù)動作空間的問題。
-
神經(jīng)網(wǎng)絡(luò)
+關(guān)注
關(guān)注
42文章
4726瀏覽量
100311 -
算法
+關(guān)注
關(guān)注
23文章
4576瀏覽量
92341 -
深度學(xué)習(xí)
+關(guān)注
關(guān)注
73文章
5437瀏覽量
120790
原文標(biāo)題:策略梯度搜索:不使用搜索樹的在線規(guī)劃和專家迭代 | 技術(shù)頭條
文章出處:【微信號:rgznai100,微信公眾號:rgznai100】歡迎添加關(guān)注!文章轉(zhuǎn)載請注明出處。
發(fā)布評論請先 登錄
相關(guān)推薦
評論