Atari 遊戲得分提升兩個數量級：Uber AI 的新強化學習演算法 Go-Explore

摘要： 雷鋒網 (公眾號：雷鋒網) AI 科技評論按：近期，Uber AI 研究院提出了一種新的強化學習演算法 Go-Explore ，它的目標是克服當前熱門的好奇心（內在獎勵）大類方法尚未克服的遺忘和重複探索問題。他們也在極具挑戰的 Atari 遊戲「蒙特祖瑪的復仇」和「Pitfall」中實驗了演...

雷鋒網 (公眾號：雷鋒網) AI 科技評論按：近期，Uber AI 研究院提出了一種新的強化學習演算法 Go-Explore ，它的目標是克服當前熱門的好奇心（內在獎勵）大類方法尚未克服的遺忘和重複探索問題。他們也在極具挑戰的 Atari 遊戲「蒙特祖瑪的復仇」和「Pitfall」中實驗了演算法，取得了好幾個數量級的表現提升。雷鋒網 AI 科技評論介紹如下。

在強化學習（RL）中，解決 Atari 經典遊戲「蒙特祖瑪的復仇」和「Pitfall」是一項巨大的挑戰。這些遊戲代表了一類具有普遍挑戰性的現實問題——「硬探索問題」，即智慧體必須通過非常稀疏或有欺騙性的反饋來學習複雜任務。

之前最先進的演算法玩蒙特祖瑪的平均分為 11,347，最高分為 17,500，並且在十次闖關後通過了第一關。令人驚訝的是，儘管進行了大量的研究工作，但到目前為止對於 Pitfall，還沒有演算法能獲得大於 0 的分數。

Atari 遊戲得分的新突破

今天介紹的 Go-Explore，是一個新的演算法型別，它能夠在蒙特祖瑪上得分超過 2 百萬分，平均得分超過 400萬分！Go-Explore 可以很穩定的通關整個遊戲，其實這個遊戲只有前三關不一樣，後續關卡都是前三關的衍生（每個關卡僅在時間的長短和螢幕顯示的分數上有所不同而已）。Go-Explore 甚至可以達到159級！

在 Pitfall 中，Go-Explore的平均得分超過 21,000，遠超人類的平均表現，並且首次在已有演算法上實現零得分的突破。為此，它要穿過 40 個房間，完成水上繩索跳躍、跳過鱷魚、陷阱門、移動桶、爬梯子和躲避其他危險物。

總而言之，Go-Explore 演算法分別將蒙特祖瑪的復仇和 Pitfall 的得分現狀提升了兩個數量級和 21,000 分。再者它無需「人工演示」，並且在效能上完勝目前所有涉及「人工演示」的最先進的演算法。

Go-Explore 可以從人工領域知識中受益，無需人工通關遊戲作為演示。領域知識很小，很容易從畫素中獲得，這突出了 Go-Explore 利用最小先驗知識的深刻能力。然而，即使沒有任何領域知識，Go-Explore 在蒙特祖瑪中的得分也超過了 3.5 萬分，遠超現有技術三倍之多。

Go-Explore 與其他深度強化學習演算法完全不同。Uber 研究院認為它可以在各種重要的，具有挑戰性的問題中取得快速進展，特別是機器人技術方面。因此他們也希望它能夠幫助 Uber 和其他團隊更多地利用人工智慧的優勢。

探索的挑戰

獎勵稀疏的問題很難解決，因為隨機行為無法產生獎勵，因此無法學習。蒙特祖瑪就是這樣一個獎勵稀疏的問題。獎勵具有欺騙性時就更棘手，這意味著在短期內最大化獎勵可能會使智慧體在總分上表現不佳。Pitfall 中的獎勵則具有欺騙性，許多行為會導致小的負面獎勵（比如擊中敵人），因此大多數演算法都選擇智慧體不移動，因此永遠無法收集到其他獎勵。許多具有挑戰性的現實問題的獎勵都是稀疏和有欺騙性的。

普通的 RL 演算法通常無法離開蒙特祖瑪的第一個房間（得分為400或更低）並且在 Pitfall 上得分為 0 或更低。為了嘗試解決這些挑戰，研究人員為智慧體增加了探索獎勵，通常稱為內在動機（intrinsic motivation，IM），鼓勵他們到達新狀態（情境或地點）。儘管 IM 演算法專門用於解決稀疏獎勵問題，但他們在蒙特祖瑪和Pitfall的任務中仍表現不佳，在蒙特祖瑪中表現最好的也鮮有能過第一關的，在Pitfall中更是以0分完敗。

Uber AI 的研究人員們猜測當前 IM 演算法的一個主要弱點是分離，即演算法忘記了他們訪問過的「有獎勵」的區域，這意味著他們返回這些區域的時候不會再有新的獎勵。舉個例子，想象智慧體處在兩個迷宮入口之間。它先從左邊的迷宮開始隨機搜尋，由於 IM 演算法有要求智慧體隨機的嘗試新行為以找到更多的內在獎勵的機制，在搜尋完左邊迷宮的 50 %時，智慧體會在任意時刻開始對右邊迷宮的搜尋，但由於深度學習自身的災難性遺忘問題，在完成右邊的搜尋後智慧體並不記得在左邊迷宮中探索的事情；更糟糕的是，左邊迷宮的一部分已經被探索過，所以幾乎沒有可獲得的內在獎勵，這就嚴重影響了智慧體的學習過程。Uber AI 的研究人員們將這種狀況稱為：演算法從提供內在動機的狀態範圍分離開了。因此，當已經探索了當前智慧體訪問過的區域時，探索可能會停滯。 如果智慧體能夠返回到先前發現的有獎勵的探索區域，就可以解決這個探索停滯問題。

內在動機（IM）演算法中的分離示例。 綠色區域表示內在獎勵，白色表示沒有內在獎勵的區域，紫色區域表示演算法當前正在探索的位置。

GO-explore

Go-Explore演算法的高度概括

而 Uber AI 提出的新演算法 Go-Explore 將學習分為兩個步驟：探索和強化。

階段1：探索到解決為止 。 Go-Explore 構建了一個有趣的不同遊戲狀態（稱之為「單元格」）和導致狀態軌跡的存檔，如下所示：

重複到解決為止：

• 根據概率選擇存檔中的單元格（可選擇有可能有獎勵的單元格，例如更新的單元格）

• 回到那個單元格

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

• 對於所有訪問的單元格（包括新單元格），如果新的軌跡更好（例如更高的分數），則更新單元格軌跡。

通過在存檔中明確記錄狀態的軌跡，Go-Explore 能夠記住並返回到「有獎勵」的區域進行探索（這不同於內在動機的訓練策略）。此外，通過探索單元格前先返回單元格的操作，特別是對於那些距離遠的、難以到達的單元格，Go-Explore 避免過度探索容易達到的狀態（例如在起點附近），而是專注於擴充套件其知識領域。最後，因為 Go-Explore 嘗試訪問所有可達狀態，所以它不太容易受到欺騙性獎勵的影響。熟悉質量多樣性演算法的人可以理解這些想法。下文將繼續討論 Go-Explore 如何表示一種新型的質量多樣性演算法。

階段2：強化（如有必要） 。如果找到的解決方案對噪聲的魯棒性較差，可以使用模擬學習演算法將它們置於深度神經網路中。

單元格表示

為了能夠駕馭 Atari 遊戲這樣的高維狀態空間，Go-Explore 需要一個較低維度的單元格表示來進行存檔。因此，單元格表示應該將十分相似且無需單獨探索的狀態進行合併（但不混合意義上有差別的狀態）。重要的是，建立這樣的表示不需要遊戲特定的領域知識。經研究發現，最樸素的單元格表示可能非常有效：只需對當前遊戲框架進行下采樣。

返回單元格

根據環境的限制，可以通過以下三種方式實現探索之前先返回單元格的操作。為了提高效率：

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

• 在確定性環境中，可以重現到細胞的軌跡

• 在隨機環境中，人們可以訓練一個學習可靠返回到單元格的目標條件策略

雖然大多數有趣的問題都是隨機的，但 Go-Explore 背後的一個核心思想是我們可以先解決問題，之後再想辦法使解決方案更加具有魯棒性（如有必要）。特別是，我們通常認為確定性會阻礙產生更具魯棒性、更高效能的智慧體，但 Go-Explore 觀點與之相反，當我們瞭解到模擬器是確定的和可重置的（通過儲存和還原模擬器狀態）事實後，確定性可能還有助於產生更高效能的智慧體，然後可以隨機建立一個更強大的策略（包括新增領域隨機化）。此觀察結果與機器人任務尤為相關，在策略遷移到實際任務之前，需要在模擬器中完成相關訓練。

Atari 遊戲是可重置的，因此出於效率原因，Uber AI 的研究人員們通過載入遊戲狀態返回到先前訪問過的單元格。在蒙特祖瑪的復仇中，這種優化使他們能夠比「回顧軌跡方法」快 45 倍地通關第一級。然而，Go-Explore 不需要訪問模擬器，訪問模擬器只是為了讓它變得更快。

在這項工作中，當智慧體返回一個經隨機行為探索的單元格後（很可能重複以前的行為）。儘管在強化中常常會用到神經網路，但這種探索不需要神經網路或其他控制器，並且後續實驗中所有的探索都不使用。完全隨機的探索工作非常好的突出了僅返回目標單元格的驚人能力。

探索階段的結果

通過下采樣影象單元格表示，在蒙特祖瑪遊戲中， Go-Explore 僅用了先前技術的 65% 的時間就通關了第一關（其中包含24個不必要探索的房間），平均到達房間 37 個，而先前的技術水平平均只探索了22個房間。

Go-Explore在沒有領域知識(通過縮小畫素表示)的探索階段發現的房間數量

魯棒化

Uber AI 當前版本的 Go-Explore 利用確定性來更快地找到解決方案（高效能軌跡）。這樣的軌跡是脆弱的：不能泛化到其他差異場景中，包括那些通過使 Atari 遊戲有點隨機的經典方式所創造的狀態，即迫使智慧體在開始遊戲之前隨機 30 多次什麼都不做。

Go-Explore 通過模仿學習解決了這個脆弱性問題，模仿學習是一種可以從演示中學習魯棒無模型策略的演算法。通常這樣的演算法需要人工演示，但是 Go-Explore 的第1階段可以自動生成這樣的演示（其中一部分比人工演示效果更好）。

任何可靠的模仿學習演算法都可行。起初 Uber AI 的研究人員們選擇了 Salimans 和 Chen 的「後向演算法」，因為它是開源的，並且在提供人工演示時可以解決蒙特祖瑪的問題。

他們還發現從單一演示中學習有點不可靠。然而，因為 Go-Explore 可以產生大量的演示，他們為了同時學習多個演示而改進了後向演算法（在這種情況下學習 4 個演示，以及後面的領域知識實驗中 10 個）。他們還在初始條件中添加了一個隨機數的無操作（不執行任何命令），以使策略對此類隨機性具有魯棒性。

結果具有強大的深度神經網路策略

所有試圖從蒙特祖瑪第一關通關軌跡中學習的魯棒策略都有效。平均得分為 35,410 分，是之前技術水平均分 11,347 分的 3 倍以上，並略高於人類專家的均分 34,900 分！

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

新增領域知識

演算法能將易得的領域知識整合的能力是很重要的。Go-Explore 支援利用單元格表示中的領域知識。Uber AI 的研究人員們在蒙特祖瑪上測試了具有領域知識的 Go-Explore 版本，其中單元格被定義為智慧體的 x-y 位置、當前房間、當前關卡和當前持有的金鑰數量的唯一組合。他們編寫了簡單的程式碼來直接從畫素中提取這些資訊。

通過這種改進的狀態表示，在 Go-Explore 的第 1 階段，智慧體就驚人地發現了 238 個房間，平均通過 9 個關卡，並且在模擬器中，相比與縮圖的單元格表示，Go-Explore 智慧體僅用了一半步驟就完成了該任務。

僅使用由畫素匯出的領域知識的單元格表示， Go-Explore 第1階段發現的房間數量，

強化的結果

利用有領域知識的 Go-Explore 版本找到的軌跡的而產生的深度神經網路策略，可以穩定的通過蒙特祖瑪的前三個關卡（並且對隨機數量的初始無操作具有魯棒性）。因為在這個遊戲中，3 級以上的所有關卡幾乎相同（如上所述），Go-Explore 已經通關了整個遊戲！

事實上，Uber AI 的智慧體大致已經超過了他們的初始軌跡，平均通過 19 關並獲得了 469,209 的分數！這就已經突破了蒙特祖瑪的最好成績，無論是相對於傳統的 RL 演算法還是以人工演示形式提供解決方案的模仿學習演算法。令人難以置信的是，一些 Go-Explore 的神經網路得到了 200 多萬分、159級！為了充分了解這些智慧體可以做到什麼程度，Uber AI 增加了 OpenAI 的 Gym 允許智慧體玩遊戲的時間。 Go-Explore 的最高分數遠高於人類世界紀錄 1,219,200，可以說達到了嚴格意義上的「超越人類表現」。

結合領域知識的GO-EXPLORE與其他RL演算法的比較。紅點表示以人工演示的形式給出的解決方案的演算法

這個破紀錄的完整視訊在加速 4 倍後仍然有 53 分鐘長。智慧體不會死亡，只是達到了最大時間限制（儘管時間已經大大增加）。

Pitfall 遊戲

Pitfall 也需要大量的探索，並且比蒙特祖瑪更難，因為它的獎勵更稀疏（只有 32 個積極獎勵分散在 255 個房間中），許多行動產生小的負面獎勵，阻止 RL 演算法探索環境。目前為止，所有已知的 RL 演算法在這個遊戲中甚至沒有收到任何一個積極獎勵（沒有給人工演示的情況下）。

相比之下，Go-Explore 在具有最小領域知識的情況下，即我們從畫素中獲得的螢幕上的位置和房間號，其能夠訪問所有 255 個房間並在演算法的探索階段收集超過 60,000 個點。沒有領域知識（即在縮小的畫素表示）的情況下，Go-Explore 找到了 22 個房間，但沒有找到任何獎勵。Uber AI 的研究人員們認為縮小的畫素表示在Pitfall上的表現不佳，因為遊戲包含許多具有相同畫素表示的不同狀態（即遊戲中位置不同但外觀相同的房間）。在沒有領域知識的情況下區分這些狀態可能需要考慮先前狀態的狀態表示，或者開發其他技術。

在Go-Explore 在Pitfall遊戲中探索階段發現的房間(左)和獲得的獎勵(右)。

從探索階段收集的軌跡中，Uber AI 能夠可靠地收集超過 21,000 點的軌跡進行強化，這大大超過現有技術水平和人類平均表現。 更長、更高得分的軌跡強化起來很困難，可能是因為視覺上無法區分的狀態可能需要採取不同的行為。 他們相信可以通過進一步研究智慧體消除狀態歧義的技術來解決這個問題。

三大關鍵原則

Uber AI 認為 Go-Explore 之所以在「硬探索問題」上表現非常出色是源於三個關鍵原則：

• 記住探索過程中好的「基礎步驟」（目前為止訪問到的不同的有趣場景）

• 先返回到一個場景，然後再探索

• 先解決問題，然後進行魯棒化（如有必要）

大多數 RL 演算法中都沒有應用這些思想，但如果把這些思想嵌入到以往 RL 演算法中，那將會是一件有意思的事情。如上所述，目前的 RL 演算法不會考慮第一點。第二點很重要，因為當前的 RL 演算法採用隨機擾動引數或隨機動作的探索策略是希望能夠探索到環境內的新區域，這些區域可能會因為一些策略上的改變而使得智慧體表現的非常差，如在進行進一步區域探索之前不能先返回到難以到達的場景中。這個問題會隨著到達狀態的必要動作序列更長、更復雜、要求更為精確變得越來越嚴重。Go-Explore 通過首先返回狀態然後從那裡開始探索來解決這個問題。這樣做可以保證找到問題解決方案後的深入探索，然後在此基礎上魯棒化以產生更可靠的策略（原則3）。

從存檔的軌跡中儲存和探索的想法來自質量多樣性（QD）演算法型別（如 MAP-elites 和本地比賽的新穎搜尋），Go-Explore 是基於 MAP-Elites 的增強 QD 演算法。然而，之前的 QD 演算法側重於通過隨機擾當前存檔策略來探索行為空間，而不是通過重新探索來明確探索狀態空間。從狀態空間的確切位置開始，之前的探索就停止了。實際上，Go-Explore 提供了比其他 QD 方法更有控制的狀態空間探索，確保探測範圍通過狀態空間累積，因為每個新的探索軌跡都離開了前一個探測軌跡的終點。

值得注意的是，當前版本的 Go-Explore 通過在探索時採取完全隨機的行為（沒有任何神經網路！）來工作，並且即使應用在狀態空間的簡單離散化上也很有效。儘管搜尋如此簡單，但它的成功有力地表明瞭記住和探索良好的軌跡是有效探索的關鍵，並且進行簡單探索比深層RL方法更有助於尋找新狀態並完成狀態表示。如果將其與有效的，經過學習的表示相結合，並用更智慧的探索策略取代當前的隨機探索，Go-Explore 可以更加強大。這也是我們正在追求的兩種途徑。

Go-Explore 還演示瞭解決探索和處理環境隨機性的問題是可以通過以下兩個階段分別完成的，即先在確定性環境中進行探索然後強化相關解決方案。依賴於訪問確定性環境最初可能看起來像是 Go-Explore 的缺點。但是，Uber AI 認為確定性環境可用於許多流行的 RL 領域，包括計算機遊戲，機器人模擬器，甚至學術世界模型。一旦找到一種或多種魯棒性較弱的解決方案後，就可以在模擬中生成穩健的解決方案。如果最終目標是應用於現實中的策略（例如，機器人技術），則可以使用許多可用技術中的任何一種將強健策略從模擬器中轉移到現實世界。此外，Uber AI 計劃證明用目標條件策略替代載入確定性狀態的可能性，該策略從一開始就學習處理隨機環境。這樣的演算法仍然可以從 Go-Explore 的三個關鍵原則中受益。

有些人可能持反對意見，雖然這種方法已經在採集原始畫素進行 Atari 的高維域中證明有效，但它無法擴充套件到真實的高維域，如現實世界的模擬器中。Uber AI 則相信這種方法在真實高維域也可以工作，但它必須將不同的有趣狀態（例如，世界的學習，壓縮表示）的更智慧的單元格表示與智慧探索策略（不是隨機策略）相結合。有趣的是，狀態合併的越多（將更多的狀態對映到同一個單元格表示），就越需要進行智慧探索以到達這些本質上不同的單元格。另外，從任意給定單元格中學習智慧探索需要有效地重用探索必備技能（如遊走）。

相關工作

Go-Explore 讓人想起早期分離探索和開發的工作。然而，Go-Explore 進一步分解了探索的三個要素：積累基礎步驟、返回有獎勵的基礎步驟，並從中尋找額外的基礎步驟（即上面的原理＃1和＃2）。通過為每個元素插入非常簡單的演算法，Go-Explore 實現了令人印象深刻的結果，這顯示了分解的價值。如上所述，與 QD 演算法相比，所有當前 RL 演算法的另一個不同之處在於 Go-Explore 不會通過擾亂新狀態的策略來嘗試探索新的高效能的狀態，而是首先返回到一個確定的狀態，然後從中探索。

Go-Explore 首先找到一個解決方案然後圍繞它進行優化的思路在「引導策略搜尋」（ ofollow,noindex">https://arxiv.org/pdf/1504.00702.pdf ）中已有先例。然而，這種方法需要一種無欺騙性、非稀疏、可微分的損失函式來尋找解決方案，這意味著它不能直接應用於如 某些 Atari 遊戲許多現實世界的問題一樣，獎勵是離散的、稀疏的、具有欺騙性的問題。此外，引導式策略搜尋需要有可微分的全域性模型或學習一組區域性模型，這些區域性模型易於處理，需要在訓練期間觀察系統的完整狀態。

結論

總體而言，Go-Explore 是一個用於解決硬探索的強化學習問題（即具有稀疏和/或欺騙性獎勵的問題）的令人興奮的新演算法型別。 它開闢了大量新的研究方向，包括測試不同的存檔，選擇返回單元格的不同方法，不同的單元格表示，不同的探索方法，以及不同的模擬方法，如不同的模仿學習演算法。 Uber AI 也很高興看到 Go-Explore 的優勢與不足， 這像是一個探索可能性的新樂園，也希望更多研究人員能和他們一起進行該領域的研究。

Uber AI 正在撰寫這篇論文，預計很快就會正式發表。介紹部落格原地址為 https://eng.uber.com/go-explore/ ，文末也對部落格釋出後來自其它研究人員們的疑問給出了迴應。感興趣的讀者可以繼續關注。

雷鋒網 AI 科技評論編譯。

雷鋒網原創文章，未經授權禁止轉載。詳情見 轉載須知 。