Dueling Network Architectures for Deep Reinforcement Learning
ICML 2016 Best Paper
摘要：本文的貢獻點主要是在 DQN 網絡結構上，将卷積神經網絡提出的特征，分為兩路走，即：the state value function 和 the state-dependent action advantage function.
這個設計的主要特色在于 generalize learning across actions without imposing any change to the underlying reinforcement learning algorithm.
本文的結果表明，這種設計結構可以當出現許多相似值的 actions 的時候，得到更好的 政策評估（policy evaluation）。
引言：文章首先開始講解了最近的關于 Deep Learning 網絡結構上的快速發展，列舉了一些成功的案例。并且提到了現有的 DRL 方面的發展，主要依賴于設計新的 RL 算法，而不是新的網絡結果。本文則從網絡結構方面入手，提出一種新的結構和現有的 RL 算法更好的結合在一起。
傳統單流程的 Q-network 與 新提出的 dueling Q-network 的示意圖如下：
可以看出，本文提出的 dueling network 将後續的輸出分為了兩個分支，來分别預測 state-value 和 the advantages for each actions ; 綠色的輸出子產品執行 下面提到的公式（9），來組合這兩個輸出。兩個網絡結構都是輸出每一個 action 的 Q-values 。
直覺上看，the dueling architecture 可以學習到哪一個狀态是有價值的 （which states are (or are not) valuable），而不必學習每一個 action 對每一個 state 的影響。這個對于那些 actions 不影響環境的狀态下特别有效。為了說明這一點，我們可以考慮圖2 所展示的顯著性圖。
這個圖展示了兩個不同時間步驟的 the value and advantage saliency maps。在一個時間步驟上，the value network steam 注意到 the road，特别是 the horizon，因為這個地方出現了新的車輛。他也注意到 score。 the advantage stream 另一方面不關心視覺輸入，因為當沒有車輛出現時，你可以随意的選擇 action，而對環境幾乎沒有影響。但是第二個圖可以看出，the advantage stram 關注到一輛車的出現，使得做出的選擇十分相關。
在實驗當中，我們發現這個 dueling architecture 能夠更快的做出正确的反應，選擇出合适的 action，當政策評價備援或者相似的 actions 被添加到學習過程中。
Background ：
作者剛開始介紹了一些基本的 RL 方面的知識，此處簡答的回顧下，具體可以參考相關 RL 教材。
state-action pair (s, a) 的 value 定義 以及 the state s 的 value 定義為：
接下來的 state-action value function (簡稱 Q function) 可以通過 dynamic programming 動态的計算如下：
我們定義最優的 $Q^*(s, a)$。在決定性的政策 $a = arg max Q^*(s, a')$，其服從 $V^*(s) = max_a Q^*(s, a)$。在這裡，最優 Q function 也滿足 Bellman equation:
我們定義另一個重要的變量， the advantage function, relating the value and Q function :
注意到，$E_{a~\pi(s)} [A^{\pi}(s, a)]$ 。直覺的來講，the value function V 評價了在特定狀态 s 下狀态有多好 （measures the how good it is to be in a particular state s）。The Q function, 然而，衡量了在這個狀态下選擇特定 action 的價值（value）。The advantage function 從 Q function 中減去了 狀态的值，得到了每一個 action 重要性的相對衡量。
Deep Q-network ：
在接下來的章節中，所涉及物體的 value function 都是高次元的。為了估計他們，我們利用一個 Deep Q-network: $Q(s, a; \theta)$，參數為 $\theta$ 。為了預測這個網絡，我們優化下面的第 i 次疊代損失函數序列：
其中 $\theta^-$ 代表一個固定的，單獨的 target network 的參數。我們可以嘗試去利用标準的 Q-learning 算法來線上的學習網絡 $Q(s, a; \theta)$ 的參數。然而，這個預測（estimator）執行起來卻表現的很差勁（performs poorly in pracitce）。Nature 2015 Human level control 那個文章中的一個關鍵的建立點是：
freeze the parameters of the target network for a fixed number of iterations while updating the online network by gradient descent.
（在用梯度下降的進行網絡更新的時候，固定一定次數的網絡，儲存為 target network）。
這一改進，極大的改善了該算法的穩定性。特定的梯度更新為：
這個方法之是以被稱為： model free 因為 states and rewards are produced by the environment.
off-policy 因為 這些狀态和獎賞 are obtained with a behavior policy different from the online policy that is being learned.
另一個關鍵的成功之處是： experience replay 。在學習的過程當中，the agent 積累了一個資料集 $D_t = {e_1, e_2, .., e_t}$ , 其中，每一個記錄 $e_t = (s_t, a_t, r_t, s_{t+1})$稱為一個 episode 。 當訓練 Q-network 的時候，并非僅僅使用目前的 experience 來進行學習，而是随機的從這個資料集上采樣出一個 mini-batch 的資料進行更新：
是以 這個序列的損失為：
經驗回放 增強了資料的有效性，主要是使得資料服從了監督學習所要求的 獨立同分布的前提。
上面一個小節主要講了 Nature 2015 Human level control via deep reinforcement learning 的主要内容。
Double Deep Q-networks:
本文中我們采用改善的 Double DQN learning algorithm。在 Q-learning 和 DQN 中，the max operator uses the same values to both select and evaluate an action.
這個就會導緻 value estimates 的過估計問題 （over estimation），為了改善這個問題，DDQN 采用下面的這個目标：
DDQN 和 DQN 是一樣的，不同之處在于 目标被替換掉了，僞代碼見下面。
Prioritized Replay :
優先級回放的一個關鍵點在于： increase the replay probability of experience tuples that have a high expected learning progress (as measured via the proxy of absolutely TD-error)。
這使得學習速度上有了較大的提升，在最後的政策品質上也有較好的改善。
The Dueling Network Architecture：
作者提到說，本文新的結構的關鍵的 motivation 在于：對于許多狀态，根本沒有必要進行預測每一個 actions choice 的 value 。
将兩個子產品的 fc layers 組合以輸出一個 Q estimates 需要非常巧妙的設計。
從 advantage $ Q^{\pi}(s, a) = V^{\pi}(s) + A^{\pi}(s, a)} $ 和 state-value V(s) 的表達式可以看出，advantage A 的期望值是為 0 的。
此外，對于一個決定性的政策，$a^* = arg max Q(s, a')$，服從 $Q(s, a^*) = V(s)$，是以 也可以推斷出 $A(s, a^*) = 0$.
是以，我們就考慮圖1中所展示的 dueling network：我們輸出一個 fc layer，輸出一個 scalar V， 另一路 輸出一個 |A|維的向量。
利用 advantage 的定義，我們可以嘗試去建構 the aggregating module 如下：
注意到，這個表達式适用于所有的 (s, a) instances, 也就是說，為了以矩陣形式表達公式7，我們需要複制 |A|次 這個變量 scalar V 。
但是，我們需要注意的是，$Q(s, a; \theta, \alpha, \beta)$ 僅僅是 true Q-fuction 的一個參數化估計。
此外，如果我們得出結論：V 是 state-value function 的較好的估計；或者是 A 提供了 advantage function 的一個合理的估計，都是錯誤的！
公式 7 是 unidentifiable （無法辨識的） in the scese that given Q we can not recover V and A uniquely.
（公式 7 是無法辨識的，從某種意義上說，給定 Q，我們無法唯一的恢複出 V 和 A）。
是以 我們對 V 加一個常數，對應的 從 A 中減掉同樣的常數。這個固定的撤銷操作會得到相同的 Q value。當這個公式被直接應用時，缺乏 identifiablity 的問題就會在實際問題上被放大。
為了解決 可識别性的問題，我們強迫 advantage function estimator 在選擇的 action 上具有 zero advantage。也就是說，我們讓網絡的最後一個子產品執行下面的這個映射（mapping）：
現在，對于 $ a* = arg max Q(s, a'; \theta, \alpha, \beta) = arg max A(s, a'; \theta, \alpha) $, 我們得到：
$Q(s, a*; \theta, \alpha, \beta) = V（s; \theta, \beta）$
是以， the stream V 提供了 value function 的估計， 另一路提供了 the advantage function 的一個估計。
另一個子產品用 an average 代替 the max operator：
另一方面，這就失去了 V 和 A 原本的意思，因為他們現在偏離目标 一個常數，但是從另一個角度來講，他又增強了優化的穩定性。
有了公式 9，the advantage 僅僅需要和 mean 變得一樣快就行了，而不需要彌補公式 8 中最優 actions advantage 的任何改變 （instead of having to compense any change to the optimal action's advantage in equation (8)）。我們也對公式 8 做了一個 softmax version的實驗，發現實驗結果和公式 9 得到的類似，但是明顯 公式 9 就非常簡潔。是以，本文中所有的結果都是基于公式 9 進行的。
雖然公式 9 減去了均值，幫助增強了可識别性。但是并沒有改變 A values 的相對排序，是以儲存了任何公式 7 的性質。當執行的時候，從 advantage streams 就足夠可以做出決定。
至此，本文的算法部分，就講解完畢了，接下來就是實驗部分，這裡 就不講了，感興趣的可以參考原文。
總結：從表面上來看，貌似了解了這個過程，但是實際上，閉上眼睛想一想這整個流程，我們還是會發現有一些問題，尚未了解清楚，例如：
1. 将 Q值 分解為 V + A 這種形式，再組合在一起，到底有什麼優勢？ 這樣訓練下來，為什麼 agent 會得到更多的資訊？是什麼使得 agent 變得聰明了，做出了更好的選擇？？？
---- My Answer：
第一點，相對于傳統的 single stream 的流程來說，本文的設計使得收斂速度更快。由文章的實驗可知，當 action 的選擇是 5個時，兩個結構的訓練結果相當；但是當 action 的選擇增加時，dueling network 的優勢就展現出來了。因為 the stream $V(s; \theta, \beta)$ 學習到了許多類似 action 的共享的一個 general 的 value。這個就比較有新引力了，因為很多控制問題，都存在這個問題。
第二點：就像文章的 convolution 部分講的那樣，dueling 結構的主要優勢在于：its ability to learn the state-value function efficiently. 在這個結構中，每次更新 Q value 的時候，都會随着更新 V --- 與此對應的是，single-stream architecture 僅僅更新其中的一個 action 對應的 value，其他 action 對應的 value 保持不變。這種更加頻繁的更新 value stream 的做法配置設定了更多的資源給 V，是以可以更好的估計 state values，而對于 temporal-difference-based methods 像 Q-learning 需要準确的 state value。這種現象主要展現在：當 action 的個數增加的時候，dueling architecture 比 single-stream 的算法更有效。
第三點：the difference between Q-values for a given state are often very small relative to the magnitude of Q.
(相對于 Q 值的量級來說，Q 值之間的差異顯得非常小，而不明顯，如： Q1 = 501, Q2 = 500) 。
文章中也給出了一個例子，即：在用 DDQN 算法訓練完畢 Seaquest 後，平均 action gap 大約是 0.04，而 the average state value 之間卻是 15. 不同尺寸的差異會導緻在更新的時候帶來 noise，而影響 action 的 reordering，這使得貪婪政策的更新非常頻繁。本文提出的算法則對這種 noise 是魯棒的。
Reference ：
Torch 官網上提供的關于 dueling DDQN 的一個部落格：
http://torch.ch/blog/2016/04/30/dueling_dqn.html
Dueling 網絡結構上比 DQN 改動的代碼部分：
不知道大家還有什麼疑問 ？？？
歡迎積極留言。。。一起讨論。。。 謝謝 。。。