Atari游戲史上最強(qiáng)通關(guān)算法來了——Go-Explore！蒙特祖瑪獲分超過200萬，平均得分超過40萬；Pitfall平均超過21000分！

通關(guān)Atari游戲的最強(qiáng)算法來了！

在強(qiáng)化學(xué)習(xí)中，解決經(jīng)典Atari游戲《蒙特祖瑪?shù)膹?fù)仇》和《Pitfall》一直是個(gè)巨大的挑戰(zhàn)。

這些游戲代表了一大類具有挑戰(zhàn)性的、現(xiàn)實(shí)世界中的問題，這些問題被稱為“硬探索問題（hard-exploration problems）”，而智能體必須通過獎(jiǎng)勵(lì)（reward）來學(xué)習(xí)復(fù)雜的任務(wù)。

在采用最先進(jìn)算法的情況下，蒙特祖瑪?shù)钠骄梅譃?1347分，最高得分為17500分，并在十次嘗試中能通過一個(gè)關(guān)卡。然而令人驚訝的是，盡管進(jìn)行了大量的研究，到目前為止還沒有算法在Pitfall上得到大于0的分?jǐn)?shù)。

而一個(gè)新的算法Go-Explore，能夠在蒙特祖瑪中獲得超過200萬分，平均得分超過40萬分！Go-Explore非常穩(wěn)定地把整個(gè)游戲都通關(guān)了，級(jí)別甚至能達(dá)到159級(jí)！

在Pitfall上，Go-Explore的平均分超過了21000分，遠(yuǎn)遠(yuǎn)超過了人類的平均成績，并且在所有學(xué)習(xí)算法上，首次得到超過0分的成績。要做到這一點(diǎn)，智能體需要穿過40個(gè)房間，搖擺于水上的繩索，跳過鱷魚、陷阱以及滾動(dòng)桶等。

總而言之，Go-Explore使得蒙特祖瑪和Pitfall在技術(shù)水平上都得到了大幅度的提高。它無需涉及“人類的演示”，并且在結(jié)果和性能上完敗目前最先進(jìn)的算法。

Go-Explore可以從人工領(lǐng)域知識(shí)（domain knowledge）中獲益，無需人類先行通關(guān)來演示。領(lǐng)域知識(shí)是最小的，很容易從像素中獲得，突出了Go-Explore利用最小先驗(yàn)知識(shí)的能力。而即使沒有任何領(lǐng)域知識(shí)，Go-Explore在蒙特祖瑪中得分也超過了3.5萬分，是目前最高水平的三倍多。

Go-Explore與其他深度強(qiáng)化學(xué)習(xí)算法有很大區(qū)別。它可以在許多重要的且具有挑戰(zhàn)性的問題上取得突破性進(jìn)展，尤其是機(jī)器人技術(shù)。

“稀疏獎(jiǎng)勵(lì)”和“欺騙性”是最具難度的挑戰(zhàn)

獎(jiǎng)勵(lì)（reward）較少的問題是比較棘手的，因?yàn)殡S機(jī)行動(dòng)不可能產(chǎn)生獎(jiǎng)勵(lì)，因此無法學(xué)習(xí)。《蒙特祖瑪?shù)膹?fù)仇》就是一種“稀疏獎(jiǎng)勵(lì)問題（sparse reward problem）”。

更具挑戰(zhàn)的是當(dāng)獎(jiǎng)勵(lì)具有欺騙性時(shí)，這意味著在短期內(nèi)最大化獎(jiǎng)勵(lì)會(huì)讓智能體在獲得更高分?jǐn)?shù)時(shí)出錯(cuò)。Pitfall就是具有欺騙性的，因?yàn)樵S多行為會(huì)導(dǎo)致較小的負(fù)面獎(jiǎng)勵(lì)（比如攻擊敵人），因此大多數(shù)算法學(xué)習(xí)到的結(jié)果就“不動(dòng)”。

許多具有挑戰(zhàn)性的現(xiàn)實(shí)問題也是既稀疏又具有欺騙性。

普通的強(qiáng)化學(xué)習(xí)算法通常無法從蒙特祖瑪?shù)牡谝粋€(gè)房間（得分400或更低）中跳出，在Pitfall中得分為0或更低。為了解決這類挑戰(zhàn)，研究人員在智能體到達(dá)新狀態(tài)（情境或地點(diǎn)）時(shí)，會(huì)給他們獎(jiǎng)勵(lì)，這種探索通常被稱為內(nèi)在動(dòng)機(jī)（intrinsic motivation，IM）。

盡管IM算法是專門設(shè)計(jì)用來解決稀疏獎(jiǎng)勵(lì)問題的，但它們?cè)诿商刈娆敽蚉itfall表現(xiàn)依舊不佳：在蒙特祖瑪中，很少能通過第一關(guān)，在Pitfall中就完全是失敗的，得分為0。

IM算法分離的例子。綠色區(qū)域表示內(nèi)在獎(jiǎng)勵(lì)，白色區(qū)域表示沒有內(nèi)在獎(jiǎng)勵(lì)的區(qū)域，紫色區(qū)域表示算法目前正在探索的區(qū)域。

假設(shè)當(dāng)前IM算法的一個(gè)主要缺點(diǎn)是分離，算法會(huì)忘記它們?cè)L問過的“有獎(jiǎng)勵(lì)”的區(qū)域，這意味著它們不會(huì)返回這些區(qū)域，來查看它們是否會(huì)導(dǎo)致新的狀態(tài)。

比如，兩個(gè)迷宮之間有一個(gè)智能體，首先它會(huì)隨機(jī)地向西開始探索左邊的迷宮，由于算法在行為或參數(shù)中加入了隨機(jī)性，智能體可能在探索完左邊50%的迷宮的時(shí)候，開始探索向東探索右邊的迷宮。右邊的迷宮探索完之后，智能體可以說已然是“遺忘”了剛才探索左邊迷宮的事情了。

而更糟糕的是，左邊的迷宮已經(jīng)有一部分是探索過的，換句話說，智能體在左邊迷宮已經(jīng)“消費(fèi)”了一定的獎(jiǎng)勵(lì)，當(dāng)它再回頭探索相同的迷宮時(shí)，不會(huì)再有更多的獎(jiǎng)勵(lì)了，這就嚴(yán)重的影響了學(xué)習(xí)的效果。

Go-Explore

Go-Explore算法概述

Go-Explore將學(xué)習(xí)分為兩個(gè)步驟：探索和強(qiáng)化。

第一階段：探索,直到解決。Go-Explore構(gòu)建了一個(gè)有趣的不同游戲狀態(tài)(我們稱之為“單元格”)和導(dǎo)致這些狀態(tài)的軌跡檔案，在問題解決之前會(huì)一直做如下的重復(fù)：

隨機(jī)選擇存檔中的單元格；

回到那個(gè)單元格；

從該單元格中探索（例如，隨機(jī)進(jìn)行n個(gè)步驟）；

對(duì)于所有訪問的單元格（包括新的單元格），如果新的軌跡更好（例如更高的分?jǐn)?shù)），則將其作為到達(dá)該單元格的軌跡進(jìn)行交換。

第二階段：強(qiáng)化。如果找到的解決方案對(duì)噪聲不夠魯棒（就像Atari軌跡那樣），就用模擬學(xué)習(xí)算法將它們組合成一個(gè)深層神經(jīng)網(wǎng)絡(luò)。

單元格表示（Cell representation）

要在像Atari這樣的高維狀態(tài)空間中易于處理，Go-Explore需要一個(gè)低維的單元表示來形成它的存檔。因此，單元格表示應(yīng)該合并足夠相似而不值得單獨(dú)研究的狀態(tài)。重要的是，創(chuàng)建這樣的表示并不需要游戲特定的領(lǐng)域知識(shí)。最簡單的單元格表示方式所得到的結(jié)果會(huì)非常好，即簡單地對(duì)當(dāng)前游戲框架進(jìn)行下采樣。

下采樣單元格表示。 完全可觀察狀態(tài)（彩色圖像）縮小為具有8個(gè)像素強(qiáng)度的11×8灰度圖像。

返回單元格（Returning to cells）

根據(jù)環(huán)境的限制，可以通過三種方式返回單元格（在進(jìn)行探索之前）。按效率排序:

在可重置環(huán)境中，可以簡單地將環(huán)境狀態(tài)重置為單元格的狀態(tài)；

在確定性環(huán)境中，可以將軌跡重放到單元格；

在隨機(jī)環(huán)境中，可以訓(xùn)練目標(biāo)條件策略（goal-conditioned policy），學(xué)習(xí)返回到單元。

采用穩(wěn)健的深度神經(jīng)網(wǎng)絡(luò)策略的結(jié)果

試圖從通關(guān)蒙特祖瑪?shù)膹?fù)仇第1級(jí)的軌跡中產(chǎn)生穩(wěn)健的策略的努力都取得了成效。平均得分為35410分，是之前最好成績的11347分的3倍多，略高于人類專家平均水平的34900分！

無領(lǐng)域知識(shí)的Go-Explore與其他RL算法在蒙特祖瑪?shù)膹?fù)仇中的比較。圖中的每一點(diǎn)都代表了蒙特祖瑪?shù)膹?fù)仇上測試的不同算法。

添加領(lǐng)域知識(shí)

算法如果能集成易于取得的領(lǐng)域知識(shí)，這是一項(xiàng)重要的能力。Go-Explore提供了在cell representation中利用領(lǐng)域知識(shí)的機(jī)會(huì)。我們?cè)诿商刈娆數(shù)膹?fù)仇中測試了具有領(lǐng)域知識(shí)的Go-Explore版本，其中cell被定義為智能體的x-y坐標(biāo)、當(dāng)前房間、當(dāng)前關(guān)卡和當(dāng)前持有的密鑰數(shù)量的唯一組合。我們編寫了一些簡單的代碼來直接從像素中提取這些信息。

使用這種改進(jìn)的state representation，Go-Explore在Phase 1找到了238個(gè)房間，平均通關(guān)了超過9個(gè)關(guān)卡，并且與縮小的圖像單元表示相比，模擬器步驟減少了一半。

Go-Explore在Phase 1發(fā)現(xiàn)的房間數(shù)量

Robustified的結(jié)果

對(duì)Go-Explore領(lǐng)域知識(shí)版本中發(fā)現(xiàn)的軌跡進(jìn)行Robustifying，可以生成深度神經(jīng)網(wǎng)絡(luò)策略，可靠地解決了蒙特祖瑪?shù)膹?fù)仇的前3個(gè)關(guān)卡。因?yàn)樵谶@個(gè)游戲中，關(guān)卡3之外的所有關(guān)卡幾乎都是相同的(如上所述)，Go-Explore已經(jīng)解決了整個(gè)游戲！

事實(shí)上，我們的agent超越了它們的初始軌跡，平均解決了29個(gè)關(guān)卡，平均得分達(dá)到469209分！這打破了針對(duì)蒙特祖瑪?shù)膹?fù)仇的傳統(tǒng)RL算法和模仿學(xué)習(xí)算法的最高水平，這兩種算法都以人類演示的形式給出解決方案。令人難以置信的是，Go-Explore的一些神經(jīng)網(wǎng)絡(luò)得分超過200萬，達(dá)到159關(guān)！為了充分了解這些agent能夠做到什么程度，我們不得不增加了OpenAI的Gym允許agent玩游戲的時(shí)間。Go-Explore的最高分?jǐn)?shù)遠(yuǎn)遠(yuǎn)超過了人類1,219,200分的世界紀(jì)錄，即使是最嚴(yán)格的“超越人類表現(xiàn)”的定義，它也達(dá)到了。

具有領(lǐng)域知識(shí)的Go-Explore與其他RL算法在蒙特祖瑪?shù)膹?fù)仇游戲中的比較。紅點(diǎn)表示以人類演示的形式給出解決方案的算法。

即使加速了4倍，這個(gè)破紀(jì)錄的運(yùn)行的完整視頻也有53分鐘。并且，agent還沒有死，只是達(dá)到了時(shí)間限制（時(shí)間已經(jīng)大大增加）。

Pitfall游戲

Pitfall也需要大量的探索，而且比蒙特祖瑪?shù)膹?fù)仇更難，因?yàn)樗莫?jiǎng)勵(lì)更稀疏(只有32個(gè)正面的獎(jiǎng)勵(lì)分散在255個(gè)房間中)，而且許多操作產(chǎn)生的負(fù)面獎(jiǎng)勵(lì)很小，這阻礙了RL算法探索環(huán)境。到目前為止，我們所知的RL算法還沒有在這個(gè)游戲中得到哪怕是一個(gè)正面的獎(jiǎng)勵(lì)(在沒有給出人類演示的情況下)。

相比之下，Go-Explore只需要最少的領(lǐng)域知識(shí)(屏幕上的位置和房間號(hào)，都可以從像素中獲取)，就能夠到達(dá)所有255個(gè)房間，收集超過60000點(diǎn)。在沒有領(lǐng)域知識(shí)（即縮小的像素表示）的情況下，Go-Explore找到了22個(gè)房間，但沒有找到任何獎(jiǎng)勵(lì)。我們認(rèn)為縮小的像素表示在Pitfall中表現(xiàn)不佳，因?yàn)橛螒虬S多具有相同像素表示的不同狀態(tài)(即游戲中位置不同、但外觀相同的房間)。在沒有領(lǐng)域知識(shí)的情況下區(qū)分這些狀態(tài)可能需要考慮先前狀態(tài)的狀態(tài)表示，或者開發(fā)其他技術(shù)。

圖：Go-Explore在Pitfall游戲的探索階段找到的房間(左)和獲得的獎(jiǎng)勵(lì)(右)

從探索階段收集的軌跡中，我們能夠可靠地對(duì)收集超過21,000點(diǎn)的軌跡進(jìn)行強(qiáng)化，這大大超過了目前最優(yōu)的水平和人類的平均表現(xiàn)。事實(shí)證明，較長的、得分較高的軌跡很難區(qū)分，這可能是因?yàn)橐曈X上難以區(qū)分的狀態(tài)可能需要不同的行為。

Go-Explore生成的深度神經(jīng)網(wǎng)絡(luò)策略與其他RL算法在Pitfall上的比較。

Pitfall游戲中得分超過21000分的AI

三個(gè)關(guān)鍵見解

Go-Explore在硬探索問題上的表現(xiàn)非常出色，原因有三個(gè):

1、記住探索過程中好的情況（墊腳石）

2、先回到一個(gè)狀態(tài)，然后探索

3、先解決問題，然后進(jìn)行強(qiáng)化(如果需要的話)

這些原則在大多數(shù)RL算法中都不存在，但是將它們編入其中會(huì)很有趣。正如上面所討論的，當(dāng)前的RL算法不會(huì)做第1點(diǎn)。第2點(diǎn)很重要，因?yàn)楫?dāng)前的RL算法通過隨機(jī)擾動(dòng)現(xiàn)行策略的參數(shù)或行為來探索新領(lǐng)域的環(huán)境，但當(dāng)大幅打破或改變策略時(shí)，這種方法是無效的，因?yàn)椴荒茉谶M(jìn)一步探索之前先返回難以到達(dá)的狀態(tài)。

達(dá)到某種狀態(tài)所需的動(dòng)作序列越長、越復(fù)雜、越精確，這個(gè)問題就越嚴(yán)重。Go-Explore解決了這個(gè)問題，它首先返回到一個(gè)狀態(tài)，然后從那里開始探索。這樣做可以進(jìn)行深入的探索，從而找到問題的解決方案，然后對(duì)問題進(jìn)行糾正，進(jìn)而產(chǎn)生可靠的策略(原則3)。

值得注意的是，Go-Explore的當(dāng)前版本在探索過程中采取完全隨機(jī)的行動(dòng)(沒有任何神經(jīng)網(wǎng)絡(luò)!)，甚至在對(duì)狀態(tài)空間進(jìn)行非常簡單的離散化時(shí)，它也是有效的。盡管如此簡單的探索取得了成功，但它強(qiáng)烈地表明，記住和探索好的墊腳石是有效探索的關(guān)鍵，而且即使是在其他簡單的探索中這樣做，也比當(dāng)代deepRL方法更有助于尋找新的狀態(tài)并表示這些狀態(tài)。通過將其與有效的、可學(xué)習(xí)的表示形式結(jié)合起來，并將當(dāng)前的隨機(jī)探索替換為更智能的探索策略，Go-Explore可能會(huì)更加強(qiáng)大。我們正在研究這兩種途徑。

結(jié)論

總的來說，Go-Explore是一個(gè)令人興奮的新算法家族，用于解決難以探索的強(qiáng)化學(xué)習(xí)問題，即那些具有稀疏和/欺騙性獎(jiǎng)勵(lì)的問題。它開辟了大量新的研究方向，包括不同的cell representations，不同的探索方法，不同的robustification方法，如不同的模仿學(xué)習(xí)算法等。

我們也很興奮地看到Go-Explore在哪些領(lǐng)域擅長，在什么時(shí)候會(huì)失敗。它給我們的感覺就像一個(gè)充滿各種可能性的游樂場，我們希望你能加入我們的行列一起來研究這個(gè)領(lǐng)域。

我們將很快提供Go-Explore的源代碼和完整論文。