比TD、MC、MCTS指數級快，性能超越A3C、DDQN等模型，這篇RL演算法論文在Reddit上火了

來自專欄機器之心100 人贊了文章

選自arxiv，作者：Jose A. Arjona-Medina、Michael Gillhofer、Michael Widrich、Thomas Unterthiner、Sepp Hochreiter，機器之心編譯。

在強化學習中，延遲獎勵的存在會嚴重影響性能，主要表現在隨著延遲步數的增加，對時間差分（TD）估計偏差的糾正時間的指數級增長，和蒙特卡洛（MC）估計方差的指數級增長。針對這一問題，來自奧地利約翰開普勒林茨大學 LIT AI Lab 的研究者提出了一種基於返回值分解的新方法 RUDDER。實驗表明，RUDDER 的速度是 TD、MC 以及 MC 樹搜索（MCTS）的指數級，並在特定 Atari 遊戲的訓練中很快超越 rainbow、A3C、DDQN 等多種著名強化學習模型的性能。

本文在 Reddit 上也引起了廣泛而熱烈的討論，網友表示，論文中長達 50 頁的附錄令人感到驚艷，這樣他們就不用絞盡腦汁去猜測作者們到底是怎麼完成實驗的。此外，雖然主要的實驗結果僅針對兩個簡單的遊戲，但其方法很有潛力，相當具備進一步探索的價值。

論文：RUDDER: Return Decomposition for Delayed Rewards

論文鏈接：https://arxiv.org/abs/1806.07857

摘要：我們提出了一種針對延遲獎勵的有限馬爾可夫決策過程（MDP）的新型強化學習方法。本研究證明了時間差分（TD）估計偏差的糾正速度僅在延遲步上出現指數級的減慢。此外，本研究還證明蒙特卡洛估計方差可以增加其他估計值的方差，使之在延遲步上出現指數級的增長。我們介紹了一種返回值分解方法（return decomposition method）RUDDER，該方法使用和原始 MDP 一樣的最佳策略創建了一個新的 MDP，但是其再分配獎勵的延遲已經大大降低。如果返回值分解方法是最佳策略，那麼新的 MDP 不會有延遲獎勵，TD 估計也不會出現偏差。在這種情況下，獎勵追蹤 Q 值，這樣未來的期望獎勵值就保持為零。我們通過實驗確認了關於 TD 估計偏差和 MC 估計方差的理論結果。在不同長度的獎勵延遲的任務中，我們展示了 RUDDER 的速度是 TD、MC 以及 MC 樹搜索（MCTS）的指數級。在延遲獎勵 Atari 遊戲 Venture 中，RUDDER 僅學習了一小段時間，其性能就優於 rainbow、A3C、DDQN、Distributional DQN、Dueling DDQN、Noisy DQN 和 Prioritized DDQN。RUDDER 在更少的學習時間內顯著提高了在延遲獎勵 Atari 遊戲 Bowling 上的當前最優性能。

引言

在強化學習中，為執行動作的接收獎勵分配信度值是中心任務之一 [107]。人們認識到長期信度值分配是強化學習中最大的挑戰之一 [91]。目前的強化學習方法在面對長期延遲的獎勵時速度會顯著降低 [84,86]。為了學習延遲獎勵，有三個階段需要考慮：（1）發現延遲獎勵；（2）追蹤延遲獎勵相關信息；（3）學習接收延遲獎勵並保存以備後用。近期成功的強化學習方法為以上三個階段中的一個或多個提供了解決方案。最著名的方法是 Deep Q-Network（DQN）[71, 72]，它結合了 Q-learning 和卷積神經網路用於視覺強化學習 [58]。

DQN 的成功歸因於經驗重放（experience replay）[64]，其保存了觀察到的狀態獎勵轉換過程，然後從中採樣。優先經驗重放 [93,50] 促進了對重放記憶的採樣。Ape-X DQN 的訓練中，不同的策略並行執行探索，並共享優先經驗重放記憶 [50]。DQN 被擴展為 double DQN（DDQN）[113,114]，其降低了過高估計的偏差，從而有助於探索。Noisy DQN [21] 通過策略網路中的一個隨機層進行探索（詳見 [40, 94]）。Distributional Q-learning [8] 可以從雜訊中獲益，因為有高方差的平均值更可能被選擇。對抗（dueling）網路架構 [117,118] 可以分別估計狀態值和動作優勢，從而可以幫助在未知狀態中的探索。策略梯度方法 [124] 也通過並行策略進行探索。A2C 通過 IMPALA 的並行 actor 和對 actor、學習器之間的策略滯後的修正得到改進。結合非同步梯度下降的 A3C [70] 和 Ape-X DPG [50] 也依賴並行策略。近端策略優化（PPO）通過代理目標和由截斷（clipping）或 Kullback-Leibler 懲罰 [96] 實現的置信域優化擴展了 A3C。

近期出現的方法希望能解決延遲獎勵帶來的學習問題。如果和獎勵相關的狀態和很多步之前遇到的狀態很相似，則價值函數的函數逼近或 critic [72,70] 可以填補時間間隔。例如，假設一個函數學習預測一個 episode 結束時的大獎勵值（如果其狀態具備特定的特徵）。該函數可以將該相關性泛化到 episode 的起點，並為處理相同特徵的狀態預測已經很高的獎勵值。多步時間差分（TD）學習 [105,107] 可以改善 DQN 和策略梯度 [39, 70]。AlphaGo 和 AlphaZero 使用蒙特卡洛樹搜索（MCTS）可以達到比人類職業選手更好的圍棋和國際象棋水平。MCTS 從一個時間點開始模擬博弈，直到博弈結束或到達一個評估點，因此 MCTS 能夠捕捉到長期延遲獎勵。近期，使用進化策略的世界模型很成功 [36]。這些前向方法在具備狀態轉換高分支因子的概率環境中並不可行。後向方法追溯已知的目標狀態 [18] 或高獎勵狀態 [30]。然而，我們必須一步一步地學習後向模型。

我們提出後向的學習過程，且這是基於前向模型構建的。前向模型預測返回值，而後向模型分析確認導致返回值的狀態和動作。我們使用長短期記憶網路（LSTM）來預測一個 episode 的返回值。LSTM 已經在強化學習中的優勢學習（advantage learning）[4] 和學習策略 [37,70,38] 中得到了應用。然而，通過「模型中的反向傳播」進行的敏感度分析 [75,87,88,5] 有嚴重的缺陷：局部極小值、不穩定性、世界模型中的梯度爆炸或消失問題、恰當的探索、動作僅通過敏感度進行分析而不是基於它們的貢獻（相關性）[40,94]。

由於敏感度分析極大地阻礙了學習，我們對反向分析使用了貢獻分析，例如貢獻傳播 [60]、貢獻方法 [81]、excitation 反向傳播 [127]、層級相關度傳播（LRP）[3]、泰勒分解 [3,73] 或集成梯度（IG）[103]。使用貢獻分析，預測的返回值可以沿著狀態-動作序列分解為貢獻。通過用實際返回值替代預測，我們得到了一個再分配獎勵，進而獲得一個新的 MDP，其最優策略和原始 MDP 相同。再分配獎勵和獎勵塑造（reward shaping）[76,122] 是很不同的，其將獎勵變為狀態的函數而不是動作的函數。獎勵塑造和「回溯建議」（look-back advice）[123] 都保持了原始獎勵，即仍然可能存在較長的延遲，從而導致學習過程指數級變慢。我們提出了 RUDDER，其通過返回值分解來執行獎勵重分配，從而克服 TD 和 MC 因為延遲獎勵而遇到的問題。RUDDER 可以極大地減少 MC 的方差，並極大程度地避免 TD 的指數級緩慢的偏差修正（對於最優的返回值分解，TD 甚至是無偏差的）。

圖 1：在 Grid World 上對不同 Q 值 estimator 的偏差和方差的實驗評估結果。左：高方差影響的狀態數量隨著延遲步數的增加呈現指數級的增長。右：不同延遲上將偏差減少 80% 的樣本數量。

圖 2：不同方法在不同延遲下學習達到 90% 返回獎勵的最佳策略的觀察狀態數（對數坐標）。我們對比了由 Q 學習實現的時序差分（TD）、蒙特卡洛（MC）、蒙特卡洛樹搜索（MCTS）和 RUDDER。左：Grid World 環境。右：Charge-Discharge 環境。RUDDER 和其他方法所需狀態的差距隨著延遲步數的增加呈現指數級增長。

表 1：RUDDER 和其他方法在學習 Atari 遊戲 Bowling 和 Venture 時的結果。在無操作指令開始條件下，各個方法在超過 200 個測試遊戲中的歸一化人類得分和原始得分：A3C 得分未報道，因為其在無操作指令開始條件下無法獲得。其他方法的得分來自於之前的研究 [8, 39]。我們選擇了僅基於 12M 幀訓練損失的 RUDDER 模型。

圖 3：RUDDER 學習 Atari 遊戲 Bowling 和 Venture 的延遲獎勵的速度比其他方法快。左圖是 Bowling 遊戲訓練過程中各個方法的歸一化人類得分，右圖是 Venture 遊戲訓練過程中各個方法的歸一化人類得分，其中學習曲線來自於之前的研究 [39, 50]。RUDDER 在 Bowling 遊戲上達到了新的當前最優性能。

圖 4：RUDDER 在具備較長延遲獎勵的兩個 Atari 遊戲中的返回值分解示意圖。左：在 Bowling 遊戲中，僅在一個 turn（包含多次滾動）後給予獎勵。RUDDER 識別引導球沿著正確方向擊中瓶子的動作。一旦球擊中瓶子，RUDDER 隨即檢測與擊中瓶子相關的延遲獎勵。圖中只展示了 100 幀，但是整個 turn 的長度超過 200 幀。在原始遊戲中，獎勵是在 turn 結束時才給予。右：在 Venture 遊戲中，只在收集到寶藏後才給予獎勵。RUDDER 通過獎勵再分配引導智能體（紅色）前往寶藏處（金色）。獎勵在進入有寶藏的房間時進行再分配。此外，隨著智能體離寶藏越來越近，再分配獎勵逐漸增加。為簡潔起見，圖中綠色曲線展示了在使用 lambda 之前的再分配獎勵。環境僅在收集寶藏結束時才給予獎勵（藍色）。

源代碼：https://github.com/ml-jku/baselines-rudder

視頻 demo：