0
| 本文作者： AI研習(xí)社-譯站 | 2021-01-07 11:21 |
譯者：AI研習(xí)社（季一帆）
雙語原文鏈接：MuZero Intuition
為慶祝Muzero論文在Nature上的發(fā)表，我特意寫了這篇文章對MuZero算法進(jìn)行詳細(xì)介紹，希望本人能讓你對該算法有一個(gè)直觀的了解。更多詳細(xì)信息請閱讀原文。
MuZero是令人振奮的一大步，該算法擺脫了對游戲規(guī)則或環(huán)境動(dòng)力學(xué)的知識(shí)依賴，可以自行學(xué)習(xí)環(huán)境模型并進(jìn)行規(guī)劃。即使如此，MuZero仍能夠?qū)崿F(xiàn)AlphaZero的全部功能——這顯示出其在許多實(shí)際問題的應(yīng)用可能性！
MuZero是一種機(jī)器學(xué)習(xí)算法，因此自然要先了解它是如何使用神經(jīng)網(wǎng)絡(luò)的。簡單來說，該算法使用了AlphaGo和AlphaZero的策略網(wǎng)絡(luò)和值網(wǎng)絡(luò)：
策略和值的直觀含義如下：
策略p(s,a)表示在狀態(tài)s時(shí)所有可能的動(dòng)作a分布，據(jù)此可以估計(jì)最優(yōu)的動(dòng)作。類比人類玩家，該策略相當(dāng)于快速瀏覽游戲時(shí)擬采取的可能動(dòng)作。
值v(s)估計(jì)在當(dāng)前狀態(tài)s下獲勝的可能性，即通過對所有的未來可能性進(jìn)行加權(quán)平均，確定當(dāng)前玩家的獲勝概率。
這兩個(gè)網(wǎng)絡(luò)任何一個(gè)都非常強(qiáng)大：只根據(jù)策略網(wǎng)絡(luò)，能夠輕易預(yù)測每一步的動(dòng)作，最終得到良好結(jié)果；只依賴值網(wǎng)絡(luò)，始終選擇值最高的動(dòng)作。但是，將這兩個(gè)估計(jì)結(jié)合起來可以得到更好的結(jié)果。
與AlphaGo和AlphaZero相似，MuZero也使用蒙特卡洛樹搜索方法（MCTS）匯總神經(jīng)網(wǎng)絡(luò)預(yù)測并選擇適合當(dāng)前環(huán)境的動(dòng)作。
MCTS是一種迭代的，最佳優(yōu)先的樹搜索過程。最佳優(yōu)先意味著搜索樹的擴(kuò)展依賴于搜索樹的值估計(jì)。與經(jīng)典方法（如廣度優(yōu)先或深度優(yōu)先）相比，最佳優(yōu)先搜索利用啟發(fā)式估計(jì)（如神經(jīng)網(wǎng)絡(luò)），這使其在很大的搜索空間中也可以找到有效的解決方案。
MCTS具有三個(gè)主要階段：模擬，擴(kuò)展和反向傳播。通過重復(fù)執(zhí)行這些階段，MCTS根據(jù)節(jié)點(diǎn)可能的動(dòng)作序列逐步構(gòu)建搜索樹。在該樹中，每個(gè)節(jié)點(diǎn)表示未來狀態(tài)，而節(jié)點(diǎn)間的邊緣表示從一個(gè)狀態(tài)到下一個(gè)狀態(tài)的動(dòng)作。
在深入研究之前，首先對該搜索樹及逆行介紹，包括MuZero做出的神經(jīng)網(wǎng)絡(luò)預(yù)測：
圓圈表示樹節(jié)點(diǎn)，對應(yīng)環(huán)境狀態(tài)；線表示從一個(gè)狀態(tài)到下一個(gè)狀態(tài)的動(dòng)作；根節(jié)點(diǎn)為當(dāng)前環(huán)境狀態(tài)，即圍棋面板狀態(tài)。后續(xù)章節(jié)我們會(huì)詳細(xì)介紹預(yù)測和動(dòng)力學(xué)函數(shù)。
模擬：從樹的根節(jié)點(diǎn)出發(fā)（圖頂部的淡藍(lán)色圓圈），即環(huán)境或游戲的當(dāng)前位置。在每個(gè)節(jié)點(diǎn)（狀態(tài)s），使用評分函數(shù)U(s,a)比較不同的動(dòng)作a，并選擇最優(yōu)動(dòng)作。MuZero中使用的評分函數(shù)是將先前的估計(jì)p(s,a)與v(s')的值結(jié)合起來，即
其中c是比例因子，隨著值估計(jì)準(zhǔn)確性的增加，減少先驗(yàn)的影響。
每選擇一個(gè)動(dòng)作，我們都會(huì)增加其相關(guān)的訪問計(jì)數(shù)n(s,a)，以用于UCB比例因子c以及之后的動(dòng)作選擇。
模擬沿著樹向下進(jìn)行，直到尚未擴(kuò)展的葉子。此時(shí)，應(yīng)用神經(jīng)網(wǎng)絡(luò)評估節(jié)點(diǎn)，并將評估結(jié)果（優(yōu)先級和值估計(jì)）存儲(chǔ)在節(jié)點(diǎn)中。
擴(kuò)展：一旦節(jié)點(diǎn)達(dá)到估計(jì)量值后，將其標(biāo)記為“擴(kuò)展”，意味著可以將子級添加到節(jié)點(diǎn)，以便進(jìn)行更深入的搜索。在MuZero中，擴(kuò)展閾值為1，即每個(gè)節(jié)點(diǎn)在首次評估后都會(huì)立即擴(kuò)展。在進(jìn)行更深入的搜索之前，較高的擴(kuò)展閾值可用于收集更可靠的統(tǒng)計(jì)信息。
反向傳播：最后，將神經(jīng)網(wǎng)絡(luò)的值估計(jì)傳播回搜索樹，每個(gè)節(jié)點(diǎn)都在其下保存所有值估計(jì)的連續(xù)均值，這使得UCB公式可以隨著時(shí)間的推移做出越來越準(zhǔn)確的決策，從而確保MCTS收斂到最優(yōu)動(dòng)作。
細(xì)心的讀者可能已經(jīng)注意到，上圖還包括r的預(yù)測。某一情況（如棋盤游戲）在完全結(jié)束后提供反饋（獲勝/失敗結(jié)果），這樣可以通過值估計(jì)進(jìn)行建模。但在另外一些情況下，會(huì)存在頻繁的反饋，即每次從一種狀態(tài)轉(zhuǎn)換到另一種狀態(tài)后，都會(huì)得到回報(bào)r。
只需對UCB公式進(jìn)行簡單修改，就可以通過神經(jīng)網(wǎng)絡(luò)預(yù)測直接對獎(jiǎng)勵(lì)進(jìn)行建模，并將其用于搜索。
其中，r(s,a)是指在狀態(tài)s時(shí)執(zhí)行動(dòng)作a后觀察到的獎(jiǎng)勵(lì)，而折扣因子γ是指對未來獎(jiǎng)勵(lì)的關(guān)注程度。
由于總體獎(jiǎng)勵(lì)可以時(shí)任意量級的，因此在將其與先驗(yàn)獎(jiǎng)勵(lì)組合之前，我們將獎(jiǎng)勵(lì)/值估計(jì)歸一化為區(qū)間[0,1]：
其中，q_min和q_max分別是整個(gè)搜索樹中觀察到的最小和最大r(s,a)+γ?v(s')估計(jì)。
過程生成
重復(fù)執(zhí)行以下過程可實(shí)現(xiàn)上述MCTS：
在當(dāng)前環(huán)境狀態(tài)下進(jìn)行搜索；
根據(jù)搜索的統(tǒng)計(jì)信息π_t選擇一個(gè)動(dòng)作a_(t+1);
根據(jù)該動(dòng)作更新環(huán)境，得到新的狀態(tài)s_(t+1)和獎(jiǎng)勵(lì)u(t+1)；
重復(fù)上述過程。
動(dòng)作的選擇可以是貪心的（選擇訪問次數(shù)最多的動(dòng)作），也可以是探索性的：通過一定的溫度t控制探索程度，并對與訪問次數(shù)n(s,a)成比例的動(dòng)作a進(jìn)行采樣：
當(dāng)t = 0時(shí)，等效貪婪采樣；當(dāng)t = inf時(shí)，等效均勻采樣。
現(xiàn)在，我們已經(jīng)學(xué)會(huì)了運(yùn)行MCTS來選擇動(dòng)作，并與環(huán)境互動(dòng)生成過程，接下來就可以訓(xùn)練MuZero模型了。
首先，從數(shù)據(jù)集中采樣一條軌跡和一個(gè)位置，然后根據(jù)該軌跡運(yùn)行MuZero模型：
可以看到，MuZero算法由以下三部分組成：
表示函數(shù)h將一組觀察值（棋盤）映射到神經(jīng)網(wǎng)絡(luò)的隱藏狀態(tài)s；
動(dòng)態(tài)函數(shù)g根據(jù)動(dòng)作a_(t + 1)將狀態(tài)s_t映射到下一個(gè)狀態(tài)s_(t + 1)，同時(shí)估算在此過程的回報(bào)r_t，這樣模型就能夠不斷向前擴(kuò)展；
預(yù)測函數(shù)f根據(jù)狀態(tài)s_t對策略p_t和值v_t進(jìn)行估計(jì)，應(yīng)用UCB公式并將其匯入MCTS過程。
根據(jù)軌跡選擇用于網(wǎng)絡(luò)輸入的觀測值和動(dòng)作。相應(yīng)地，策略、值和獎(jiǎng)勵(lì)的預(yù)測目標(biāo)是在生成存儲(chǔ)的軌跡。
從下圖可以看到過程生成（B）與訓(xùn)練（C）之間的一致性：
具體問言，MuZero估計(jì)量的訓(xùn)練損失為：
策略：MCTS訪問統(tǒng)計(jì)信息與預(yù)測函數(shù)的策略logit之間的交叉熵；
值：N個(gè)獎(jiǎng)勵(lì)的折扣和+搜索值/目標(biāo)網(wǎng)絡(luò)估計(jì)值與預(yù)測函數(shù)的值之間的交叉熵或均方誤差；
獎(jiǎng)勵(lì)：軌跡觀測獎(jiǎng)勵(lì)與動(dòng)態(tài)函數(shù)估計(jì)之間的交叉熵。
在了解了MuZero的核心思想后，接下來我們將介紹重分析技術(shù)，這將顯著提高模型對大量數(shù)據(jù)的搜索效率。
在一般訓(xùn)練過程中，通過與環(huán)境的相互作用，我們會(huì)生成許多軌跡，并將其存儲(chǔ)在重播緩沖區(qū)用于訓(xùn)練。那么，我們可以從該數(shù)據(jù)中獲得更多信息嗎？
很難。由于需要與環(huán)境交互，我們無法更改存儲(chǔ)數(shù)據(jù)的狀態(tài)、動(dòng)作或獎(jiǎng)勵(lì)。在《黑客帝國》中可能做到，但在現(xiàn)實(shí)世界中則不可能。
幸運(yùn)的是，我們并不需要這樣。只要使用更新的、改進(jìn)標(biāo)簽的現(xiàn)有輸入，就足以繼續(xù)學(xué)習(xí)?？紤]到MuZero模型和MCTS，我們做出如下改進(jìn)：
保持軌跡（觀測、動(dòng)作和獎(jiǎng)勵(lì)）不變，重新運(yùn)行MCTS，就可以生成新的搜索統(tǒng)計(jì)信息，從而提供策略和值預(yù)測的新目標(biāo)。
我們知道，在與環(huán)境直接交互過程中，使用改進(jìn)網(wǎng)絡(luò)進(jìn)行搜索會(huì)獲得更好的統(tǒng)計(jì)信息。與之相似，在已有軌跡上使用改進(jìn)網(wǎng)絡(luò)重新搜索也會(huì)獲得更好的統(tǒng)計(jì)信息，從而可以使用相同的軌跡數(shù)據(jù)重復(fù)改進(jìn)。
重分析適用于MuZero訓(xùn)練，一般訓(xùn)練循環(huán)如下：
設(shè)置兩組異步通信任務(wù)：
一個(gè)學(xué)習(xí)者接收最新軌跡，將最新軌跡保存在重播緩沖區(qū)，并根據(jù)這些軌跡進(jìn)行上述訓(xùn)練；
多個(gè)行動(dòng)者定期從學(xué)習(xí)者那里獲取最新的網(wǎng)絡(luò)檢查點(diǎn)，并使用MCTS中的網(wǎng)絡(luò)選擇動(dòng)作，與環(huán)境進(jìn)行交互生成軌跡。
為實(shí)現(xiàn)重分析，引入兩個(gè)新任務(wù)：
重分析緩沖區(qū)，用于接收參與者生成的所有軌跡并保留最新軌跡；
多個(gè)重分析行動(dòng)者從重分析緩沖區(qū)采樣存儲(chǔ)的軌跡，使用學(xué)習(xí)者的最新網(wǎng)絡(luò)檢查點(diǎn)重新運(yùn)行MCTS，并將生成的軌跡和更新的統(tǒng)計(jì)信息發(fā)送給學(xué)習(xí)者。
由于學(xué)習(xí)者無法區(qū)分新軌跡和重分析的軌跡，這使得新軌跡與重分析軌跡的比例更改變得簡單。
MuZero的命名基于AlphaZero，其中Zero表示是在沒有模仿人類數(shù)據(jù)的情況下進(jìn)行訓(xùn)練的，Mu取代Alpha表示使用學(xué)習(xí)模型進(jìn)行規(guī)劃。
更研究一些，Mu還有其他豐富的含義：
夢，日語中讀作mu，表示“夢”的意思， 就像MuZero通過學(xué)習(xí)的模型來想象未來狀況一樣；
希臘字母μ（發(fā)音為mu）也可以表示學(xué)習(xí)的模型；
無， 日語發(fā)音為mu，表示“無、沒有”，這強(qiáng)調(diào)從頭學(xué)習(xí)的概念：不僅無需模仿人類數(shù)據(jù)，甚至不需提供規(guī)則。
希望本文對MuZero的介紹對你有所啟發(fā)！
如果想了解更多細(xì)節(jié)，可以閱讀原文，還可以查看我在NeurIPS的poster以及在ICAPS上發(fā)表的關(guān)于MuZero的演講。
最后，分享給你一些其他研究人員的文章，博客和GitHub項(xiàng)目：
為簡單起見，在MuZero中僅使用單個(gè)網(wǎng)絡(luò)進(jìn)行預(yù)測。
根據(jù)Rémi Coulom在2006年發(fā)表的Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search，MCTS為解決圍棋問題提供可能。具體而言，MCTS中的“蒙特卡洛”指在圍棋比賽中的隨機(jī)模擬數(shù)，通過計(jì)算每次隨機(jī)移動(dòng)得獲勝概率從而選擇合適位置。
MuZero中使用的比例因子為∑bn(s,b)√1+n(s,a)?(c1+log(∑bn(s,b)+c2+1c2))，其中n(s,a)表示從狀態(tài)s到動(dòng)作a的訪問次數(shù)，常數(shù)c1和c2分別為1.25和19652，它們決定先驗(yàn)對于值估計(jì)得重要性。請注意，當(dāng)c2遠(yuǎn)大于n時(shí)，c2的確切值不再重要，對數(shù)項(xiàng)此時(shí)為0。在這種情況下，公式簡化為c1?∑bn(s,b)√1+n(s,a)c1。
就像AlphaGo之前的許多Go程序使用的隨機(jī)卷展，隨機(jī)評估函數(shù)有一定作用。但如果評估函數(shù)是確定性的（如標(biāo)準(zhǔn)神經(jīng)網(wǎng)絡(luò)），那么對同一節(jié)點(diǎn)多次評估沒什么意義。
在棋盤游戲中，折扣因子γ為1，TD步數(shù)趨于無限，因此，這僅適用于對蒙特卡洛獎(jiǎng)勵(lì)（游戲獲勝者）的預(yù)測。
在運(yùn)行MuZero時(shí)，無需單獨(dú)對行動(dòng)者進(jìn)行重分析：由于只有一組行動(dòng)者，在每次行動(dòng)之前決定是與環(huán)境交互生成新軌跡還是對存儲(chǔ)軌跡進(jìn)行重分析。
AI研習(xí)社是AI學(xué)術(shù)青年和AI開發(fā)者技術(shù)交流的在線社區(qū)。我們與高校、學(xué)術(shù)機(jī)構(gòu)和產(chǎn)業(yè)界合作，通過提供學(xué)習(xí)、實(shí)戰(zhàn)和求職服務(wù)，為AI學(xué)術(shù)青年和開發(fā)者的交流互助和職業(yè)發(fā)展打造一站式平臺(tái)，致力成為中國最大的科技創(chuàng)新人才聚集地。
如果，你也是位熱愛分享的AI愛好者。歡迎與譯站一起，學(xué)習(xí)新知，分享成長。
雷峰網(wǎng)版權(quán)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。
