史上最強 Atari 遊戲通關演算法：蒙特祖瑪獲分超過 200 萬！

【新智元導讀】

Atari 遊戲史上最強通關演算法來了——Go-Explore！蒙特祖瑪獲分超過 200 萬，平均得分超過 40 萬；Pitfall 平均超過 21000 分！

通關 Atari 遊戲的最強演算法來了！

在強化學習中，解決經典 Atari 遊戲《蒙特祖瑪的復仇》和《Pitfall》一直是個巨大的挑戰。

這些遊戲代表了一大類具有挑戰性的、現實世界中的問題，這些問題被稱為 “

硬探索問題（hard-exploration problems）

”，而智慧體必須透過獎勵（reward）來學習複雜的任務。

在採用最先進演算法的情況下，蒙特祖瑪的平均得分為 11347 分，最高得分為 17500 分，並在十次嘗試中能透過一個關卡。然而令人驚訝的是，儘管進行了大量的研究，到目前為止還沒有演算法在 Pitfall 上得到大於 0 的分數。

而一個新的演算法 Go-Explore，能夠在蒙特祖瑪中獲得超過

200 萬分

，平均得分超過

40 萬分

！Go-Explore 非常穩定地把整個遊戲都通關了，級別甚至能達到 159 級！

在 Pitfall 上，Go-Explore 的平均分超過了 21000 分，遠遠超過了人類的平均成績，並且在所有學習演算法上，首次得到超過 0 分的成績。要做到這一點，智慧體需要穿過 40 個房間，搖擺於水上的繩索，跳過鱷魚、陷阱以及滾動桶等。

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

Go-Explore 可以從人工領域知識（domain knowledge）中獲益，無需人類先行通關來演示

。領域知識是最小的，很容易從畫素中獲得，突出了 Go-Explore 利用最小先驗知識的能力。而即使沒有任何領域知識，Go-Explore 在蒙特祖瑪中得分也超過了 3。5 萬分，是目前最高水平的三倍多。

Go-Explore 與其他深度強化學習演算法有很大區別。它可以在許多重要的且具有挑戰性的問題上取得突破性進展，尤其是機器人技術。

“稀疏獎勵”和 “欺騙性” 是最具難度的挑戰

獎勵（reward）較少的問題是比較棘手的，因為隨機行動不可能產生獎勵，因此無法學習。《蒙特祖瑪的復仇》就是一種 “稀疏獎勵問題（sparse reward problem）”。

更具挑戰的是當獎勵具有欺騙性時，這意味著在短期內最大化獎勵會讓智慧體在獲得更高分數時出錯。Pitfall 就是具有欺騙性的，因為許多行為會導致較小的負面獎勵（比如攻擊敵人），因此大多數演算法學習到的結果就 “不動”。

許多具有挑戰性的現實問題也是既稀疏又具有欺騙性

。

普通的強化學習演算法通常無法從蒙特祖瑪的第一個房間（得分 400 或更低）中跳出，在 Pitfall 中得分為 0 或更低。為了解決這類挑戰，研究人員在智慧體到達新狀態（情境或地點）時，會給他們獎勵，這種探索通常被稱為內在動機（ intrinsic motivation，IM）。

儘管 IM 演算法是專門設計用來解決稀疏獎勵問題的，但它們在蒙特祖瑪和 Pitfall 表現依舊不佳：在蒙特祖瑪中，很少能透過第一關，在 Pitfall 中就完全是失敗的，得分為 0。

IM 演算法分離的例子。綠色區域表示內在獎勵，白色區域表示沒有內在獎勵的區域，紫色區域表示演算法目前正在探索的區域。

假設當前 IM 演算法的一個主要缺點是分離，演算法會忘記它們訪問過的 “有獎勵” 的區域，這意味著它們不會返回這些區域，來檢視它們是否會導致新的狀態。

比如，兩個迷宮之間有一個智慧體，首先它會隨機地向西開始探索左邊的迷宮，由於演算法在行為或引數中加入了隨機性，智慧體可能在探索完左邊 50% 的迷宮的時候，開始探索向東探索右邊的迷宮。右邊的迷宮探索完之後，智慧體可以說已然是 “遺忘” 了剛才探索左邊迷宮的事情了。

而更糟糕的是，左邊的迷宮已經有一部分是探索過的，換句話說，智慧體在左邊迷宮已經 “消費” 了一定的獎勵，當它再回頭探索相同的迷宮時，不會再有更多的獎勵了，這就嚴重的影響了學習的效果。

Go-Explore

Go-Explore 演算法概述

Go-Explore 將學習分為兩個步驟：探索和強化。

第一階段：探索

， 直到解決。Go-Explore 構建了一個有趣的不同遊戲狀態 （我們稱之為“單元格”） 和導致這些狀態的軌跡檔案，在問題解決之前會一直做如下的重複：

隨機選擇存檔中的單元格；

回到那個單元格；

從該單元格中探索（例如，隨機進行 n 個步驟）；

對於所有訪問的單元格（包括新的單元格），如果新的軌跡更好（例如更高的分數），則將其作為到達該單元格的軌跡進行交換。

第二階段：強化。

如果找到的解決方案對噪聲不夠魯棒（就像 Atari 軌跡那樣），就用模擬學習演算法將它們組合成一個深層神經網路。

單元格表示（Cell representation）

要在像 Atari 這樣的高維狀態空間中易於處理，Go-Explore 需要一個低維的單元表示來形成它的存檔。因此，單元格表示應該合併足夠相似而不值得單獨研究的狀態。重要的是，建立這樣的表示並不需要遊戲特定的領域知識。最簡單的單元格表示方式所得到的結果會非常好，即簡單地對當前遊戲框架進行下采樣。

下采樣單元格表示。 完全可觀察狀態（彩色影象）縮小為具有 8 個畫素強度的 11×8 灰度影象。

返回單元格（Returning to cells）

根據環境的限制，可以透過三種方式返回單元格（在進行探索之前）。按效率排序：

在可重置環境中，可以簡單地將環境狀態重置為單元格的狀態；

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

在隨機環境中，可以訓練目標條件策略（goal-conditioned policy ），學習返回到單元。

採用穩健的深度神經網路策略的結果

試圖從通關蒙特祖瑪的復仇第 1 級的軌跡中產生穩健的策略的努力都取得了成效。平均得分為 35410 分，

是之前最好成績的 11347 分的 3 倍多，略高於人類專家平均水平的 34900 分

！

無領域知識的 Go-Explore 與其他 RL 演算法在蒙特祖瑪的復仇中的比較。圖中的每一點都代表了蒙特祖瑪的復仇上測試的不同演算法。

新增領域知識

演算法如果能整合易於取得的領域知識，這是一項重要的能力。Go-Explore 提供了在 cell representation 中利用領域知識的機會。我們在蒙特祖瑪的復仇中測試了具有

領域知識

的 Go-Explore 版本，其中 cell 被定義為智慧體的 x-y 座標、當前房間、當前關卡和當前持有的金鑰數量的唯一組合。我們編寫了一些簡單的程式碼來直接從畫素中提取這些資訊。

使用這種改進的 state representation，Go-Explore 在 Phase 1 找到了 238 個房間，平均通關了超過 9 個關卡，並且與縮小的影象單元表示相比，模擬器步驟減少了一半。

Go-Explore 在 Phase 1 發現的房間數量

Robustified 的結果

對 Go-Explore 領域知識版本中發現的軌跡進行

Robustifying

，可以生成深度神經網路策略，可靠地解決了蒙特祖瑪的復仇的前 3 個關卡。因為在這個遊戲中，關卡 3 之外的所有關卡幾乎都是相同的 （如上所述），

Go-Explore 已經解決了整個遊戲

！

事實上，我們的 agent 超越了它們的初始軌跡，平均解決了 29 個關卡，平均得分達到 469209 分！這打破了針對蒙特祖瑪的復仇的傳統 RL 演算法和模仿學習演算法的最高水平，這兩種演算法都以人類演示的形式給出解決方案。令人難以置信的是，Go-Explore 的一些神經網路得分

超過 200 萬，達到 159 關

！為了充分了解這些 agent 能夠做到什麼程度，我們不得不增加了 OpenAI 的 Gym 允許 agent 玩遊戲的時間。Go-Explore 的最高分數遠遠超過了人類 1，219，200 分的世界紀錄，即使是最嚴格的 “超越人類表現” 的定義，它也達到了。

具有領域知識的 Go-Explore 與其他 RL 演算法在蒙特祖瑪的復仇遊戲中的比較。紅點表示以人類演示的形式給出解決方案的演算法。

即使加速了 4 倍，這個破紀錄的執行的完整影片也有 53 分鐘。並且，agent 還沒有死，只是達到了時間限制（時間已經大大增加）。

Pitfall 遊戲

Pitfall 也需要大量的探索，而且比蒙特祖瑪的復仇更難，因為它的

獎勵更稀疏

（只有 32 個正面的獎勵分散在 255 個房間中），而且許多操作產生的負面獎勵很小，這阻礙了 RL 演算法探索環境。到目前為止，我們所知的 RL 演算法還沒有在這個遊戲中得到哪怕是一個正面的獎勵 （在沒有給出人類演示的情況下）。

相比之下，Go-Explore 只需要最少的領域知識 （螢幕上的位置和房間號，都可以從畫素中獲取），就能夠到達所有 255 個房間，收集超過 60000 點。在沒有領域知識（即縮小的畫素表示）的情況下，Go-Explore 找到了 22 個房間，但沒有找到任何獎勵。我們認為縮小的畫素表示在 Pitfall 中表現不佳，因為遊戲包含許多具有相同畫素表示的不同狀態 （即遊戲中位置不同、但外觀相同的房間）。在沒有領域知識的情況下區分這些狀態可能需要考慮先前狀態的狀態表示，或者開發其他技術。

圖：Go-Explore 在 Pitfall 遊戲的探索階段找到的房間 （左） 和獲得的獎勵（右）

從探索階段收集的軌跡中，我們能夠可靠地對收集超過 21，000 點的軌跡進行強化，這大大超過了目前最優的水平和人類的平均表現。事實證明，較長的、得分較高的軌跡很難區分，這可能是因為視覺上難以區分的狀態可能需要不同的行為。

Go-Explore 生成的深度神經網路策略與其他 RL 演算法在 Pitfall 上的比較。

Pitfall遊戲超過21000分的AI

https：//www。zhihu。com/video/1052952903916036096

三個關鍵見解

Go-Explore 在硬探索問題上的表現非常出色，原因有三個：

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

2、先回到一個狀態，然後探索

3、先解決問題，然後進行強化 （如果需要的話）

這些原則在大多數 RL 演算法中都不存在，但是將它們編入其中會很有趣。正如上面所討論的，當前的 RL 演算法不會做第 1 點。第 2 點很重要，因為當前的 RL 演算法透過隨機擾動現行策略的引數或行為來探索新領域的環境，但當大幅打破或改變策略時，這種方法是無效的，因為不能在進一步探索之前先返回難以到達的狀態。

達到某種狀態所需的動作序列越長、越複雜、越精確，這個問題就越嚴重。Go-Explore 解決了這個問題，它首先返回到一個狀態，然後從那裡開始探索。這樣做可以進行深入的探索，從而找到問題的解決方案，然後對問題進行糾正，進而產生可靠的策略 （原則 3）。

值得注意的是，Go-Explore 的當前版本在探索過程中採取完全隨機的行動 （沒有任何神經網路！），甚至在對狀態空間進行非常簡單的離散化時，它也是有效的。儘管如此簡單的探索取得了成功，但它強烈地表明，記住和探索好的墊腳石是有效探索的關鍵，而且即使是在其他簡單的探索中這樣做，也比當代 deepRL 方法更有助於尋找新的狀態並表示這些狀態。透過將其與有效的、可學習的表示形式結合起來，並將當前的隨機探索替換為更智慧的探索策略，Go-Explore 可能會更加強大。我們正在研究這兩種途徑。

結論

總的來說，Go-Explore 是一個令人興奮的新演算法家族，用於解決難以探索的強化學習問題，即那些具有稀疏和 / 欺騙性獎勵的問題。它開闢了大量新的研究方向，包括不同的 cell representations，不同的探索方法，不同的 robustification 方法，如不同的模仿學習演算法等。

我們也很興奮地看到 Go-Explore 在哪些領域擅長，在什麼時候會失敗。它給我們的感覺就像一個充滿各種可能性的遊樂場，我們希望你能加入我們的行列一起來研究這個領域。

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

本文首發於微信公眾號：新智元，歡迎關注！