強化學習Q-Learning/DQN

本文是一篇學習筆記，主要參考李宏毅老師的強化學習課程。

目前主流的強化學習方法大致可以分為 policy-based 和 value-based 兩大類。之前我們介紹的 policy gradient 策略梯度，就是 policy-based 的方法。本文要介紹的 Q-learning 則是 value-based 方法。不同于 policy gradient 直接優化 policy，Q-learning 是要學習一個價值網絡，來估計策略的狀態價值或動作狀態價值，價值網絡并不直接決定接下來要采取的動作，我們需要基于價值網絡估計出的價值函數，制定新的 policy，并不斷優化 policy。

本文將介紹如何訓練模型來擬合價值函數，以及 Q-learning 如何基于價值網絡不斷優化 policy，最后介紹實際實現中常用的幾個技巧。

價值函數

價值函數是強化學習中的重要概念，也是 value-based 類方法的基礎。價值函數有關于狀態 $s$ 和關于狀態-動作對 $(s,a)$ 兩種。這里的價值是指從這個狀態 $s$ 或從這個狀態-動作對 $(s,a)$ 開始，一直按照某個特定的策略進行動作，直到結束，這期間的期望回報就稱為價值函數。

狀態價值函數，$V^{\pi }(s)$，是指在狀態 $s$，接下來按照特定的策略 $\pi$ 來進行動作，最終累積回報的期望，表示為：
$$V^{\pi }(s)={\mathbb{E}}_{\tau ～\pi }[R(\tau )|s_0=s]$$
其中 $\tau$ 是在狀態 $s$ 之后，根據策略 $\pi$ 進行動作得到的軌跡，$R(\tau )$ 即該軌跡得到的累積獎勵。

動作-狀態價值函數，$Q^{\pi }(s,a)$，是指在狀態 $s$，先強制采取動作 $a$（這個動作不一定符合當前策略 $\pi$，是人為采取的），接下來按照特定的策略 $\pi$ 來進行動作，最終累積回報的期望。表示為：
$$Q^{\pi }(s,a)={\mathbb{E}}_{\tau ～\pi }[R(\tau )|s_0=s,a_0=a]$$
從兩種價值函數的定義上不難發現，二者之間存在這樣的關系：
$$\begin{gathered} V^{\pi }(s)={\mathbb{E}}_{a～\pi }[Q^{\pi }(s,a)] \\ \text{\hspace{1em}(1)} \end{gathered}$$
即狀態價值函數 $V$ 是動作-價值函數 $Q$ 在策略 $\pi$ 下的期望。也可以更直接一點，帶進去，寫成：

$$\begin{gathered} V^{\pi }(s)=Q^{\pi }(s,\pi (s)) \\ \text{\hspace{1em}(2)} \end{gathered}$$
還是要強調一句，兩種價值函數描述的都是針對某個特定的策略 $\pi$ 的價值，對于不同的策略 $\pi$，同一個狀態 $s$ 的價值很可能是不同的。比如棋魂里的阿光，在剛學棋時可能駕馭不了高難度的棋招 “大飛”，此時策略（actor）“阿光” 對于 “大飛” 這個狀態的價值函數估計就比較低，當阿光棋力上漲，能夠駕馭這一招時，價值函數估計就比較高。即對于不同的 $\pi$，同樣狀態 $s$ 的價值是不同的，所以價值函數都是針對特定的策略 $\pi$ 來說的。
$$\begin{array}{rl}{V}^{\text{以前的阿光}}(大飛)& =\text{low}\\ V^{\text{現在更強的阿光}}(大飛)& =\text{high}\end{array}$$

從 Q-learning 的思路來進行強化學習建模，需要兩個步驟，首先是我們要如何訓練網絡來擬合價值函數 $V/Q$，然后是有了一個可靠的價值函數后，如何決定動作。我們接下來分別介紹這兩步。

訓練價值網絡估計價值函數

現在我們一般是用神經網絡來估計價值函數（DQN）了，我們需要價值網絡是一個回歸模型，輸入一個狀態（和動作），輸出一個標量分數。那么如何訓練這個神經網絡呢？有兩種方法，MC（Monte Carlo，蒙特卡洛） 和 TD（Temporal Difference，時序差分）。

MC 方法

MC 來訓練價值網絡的想法非常直覺，比如我們要估計 $V^{\pi }(s)$，它是策略 $\pi$ 在狀態 $s$ 之后的期望回報，那我們就讓 $\pi$ 把整個 episode 跑出來，記錄下最終的累積回報 $R(\tau )$，讓價值網絡回歸這個累積回報就行了。
$${\hat{V}}^{\pi }(s)\to R(\tau )$$
理想情況下是能遍歷所有可能的狀態，得到最終累積回報來給價值網絡學習，但這顯然不可能，因此就采樣 $N$ 輪來近似。

TD 方法

MC 方法非常直覺，但問題在于每次都至少要等到一整輪 episode 跑完，才能更新一次模型。在很多實際的強化學習任務（如圍棋、游戲等）中，跑完一整輪 episode 通常非常久，導致訓練效率不高。而 TD 的方法，在每次動作，有了 { s t , a t , r t , s t + 1 } \{s_t, a_t, r_t, s_{t+1}\} {st?,at?,rt?,st+1?} 這一組數據之后，就能進行一次更新。

具體來說，我們先改寫一下 $V^{\pi }(s_t)$：
$$V^{\pi }(s_t)=V^{\pi }(s_{t+1})+r_t$$
這個式子的意思很簡單：狀態 $s_t$ 的價值函數 $V^{\pi }(s_t)$ 等于當前立即得到的獎勵 $r_t$ 加上下一個狀態的價值函數 $V^{\pi }(s_{t+1})$。

這樣，在我們有了單步的一組數據之后，就可以將 $s_t,s_{t+1}$ 分別送入價值網絡，得到相鄰兩步的價值估計值 $V^{\pi }(s_t),V^{\pi }(s_{t+1})$，我們的訓練目標就是希望這兩個估計值的差值盡可能接近當前步的真實獎勵 $r_t$：
$${\hat{V}}^{\pi }(s_t)?{\hat{V}}^{\pi }(s_{t+1})\to r_t$$

對比 MC 和 TD

我們對比一下 MC 和 TD 彼此的優缺點。

首先，MC 需要一整輪的數據才能進行一次更新，而 TD 只需一步的數據即可進行更新，訓練效率更高。其次，MC 的目標值是 $R(\tau )$，取決于其后所有步的隨機采樣結果，方差會比較大，而 TD 的目標是單步采樣的數據 $r_t$，方差比較小。

但是，畢竟 TD 的目標中 ${\hat{V}}^{\pi }(s_{t+1})$ 也是價值網絡估計出來，因此 TD 不一定準。而 MC 的 $R(\tau )$ 都是實打實跟環境交互跑出來的，是真實的目標。

總之 MC 和 TD 看起來還是各有優劣，但是現在一般都是采用 TD 方法來訓練價值網絡。

更好地policy

現在我們已經可以使用 MC 或 TD 方法來訓練價值網絡，估計價值函數，但是價值網絡畢竟只是一個打分的模型，沒法直接選擇執行哪個動作，在實際中，有了價值函數之后，如何進行動作呢？也就是我們基于估計的價值函數，如何實現 policy 呢？以及我們如何能夠在價值網絡的引導下，不斷地優化 policy 呢？

Q-learning 整體的過程如下圖所示。最開始我們有一個初始的策略 $\pi$，我們讓它與環境互動，得到一系列經驗數據，然后在這些數據上采用 TD 或 MC 的方法，來學習出這個策略 $\pi$ 對應的價值函數 $Q^{\pi }(s,a)$。然后根據這個價值函數，得到一個 “更好的” 策略 ${\pi }^{\prime }$，隨后再用這個 ${\pi }^{\prime }$ 作為策略，繼續上述過程，循環往復，不斷地優化策略。這里所謂的 “更好”，指的是對于所有的狀態 $s$，都有 $V^{{\pi }^{\prime }}(s)\ge V^{\pi }(s)$。

現在的問題就是，如何根據價值函數，得到一定比現在更好的策略 ${\pi }^{\prime }$。實際上也非常簡單，就是根據學習到的關于策略 $\pi$ 的價值函數，取 argmax：
$${\pi }^{\prime }(s)=\arg \underset{a}{\max }{Q}^{\pi }(s,a)$$
直覺上很好理解，每一步我們都取能讓 $Q$ 值最大的動作，最終得到的累積回報，肯定比當前按策略 $\pi$ 要高。以下我們來簡單證明推導一下：取 ${\pi }^{\prime }(s)=\arg {\max }_a{Q}^{\pi }(s,a)$，可以使得對所有的狀態 $s$，都有 $V^{{\pi }^{\prime }}(s)\ge V^{\pi }(s)$。

首先我們寫出 $V$ 和 $Q$ 的關系（式 2），狀態價值函數 $V^{\pi }(s)$ 相當于狀態-動作價值函數 $Q^{\pi }(s,a)$ 取 $a=\pi (s)$，即在當前步也按照策略 $\pi$ 來選取動作執行。注意我們此時已知 $Q$ 函數了，所以我們是知道當前每個動作所得到的 $Q$ 值的，因此我們可以直接貪婪地選取一個讓 $Q$ 值最大的動作 $a$，這樣肯定是大于等于按照 $\pi$ 選取動作的。而這種按照 $\arg \max Q$ 來選取動作的策略，正是我們剛剛定義的策略 ${\pi }^{\prime }$ 。
$$V^{\pi }(s)=Q^{\pi }(s,\pi (s))\le \underset{a}{\max }(Q^{\pi }(s,a))=Q^{\pi }(s,{\pi }^{\prime }(s))$$
這是一步的差異。而如果我們每一步都采用 ${\pi }^{\prime }(s)=\arg {\max }_a{Q}^{\pi }(s,a)$ ，自然是更加優于 $\pi$，這最終能推導出 $V^{\pi }(s)\le V^{{\pi }^{\prime }}(s)$：
$$\begin{array}{rl}{V}^{\pi }(s)& \le Q^{\pi }(s,{\pi }^{\prime }(s))\\ & =\mathbb{E}\left[r_t+V^{\pi }(s_{t+1})|s_t=s,a_t={\pi }^{\prime }(s_t)\right]\\ & \le \mathbb{E}\left[r_t+Q^{\pi }(s_{t+1},{\pi }^{\prime }(s_{t+1}))|s_t=s,a_t={\pi }^{\prime }(s_t)\right]\\ & =\mathbb{E}\left[r_t+r_{t+1}+V^{\pi }(s_{t+2})|...\right]\\ & \le \mathbb{E}\left[r_t+r_{t+1}+Q^{\pi }(s_{t+2},{\pi }^{\prime }(s_{t+2}))|...\right]\\ & =...\le ...\\ & \le V^{{\pi }^{\prime }}(s)\end{array}$$
至此，我們就證明了只要選擇 ${\pi }^{\prime }(s)=\arg {\max }_a{Q}^{\pi }(s,a)$，就能保證對所有的狀態 $s$ 都有 $V^{{\pi }^{\prime }}(s)\ge V^{\pi }(s)$，也就是 ${\pi }^{\prime }$ 是一個比 $\pi$ 更好的策略。然后我根據上圖中的過程，不斷循環迭代，直至收斂得到一個最終的策略。

Q-learning 常用技巧

我們已經介紹了 Q-learning 的基本思想，接下來我們介紹幾個實際中一般都會用到的 tricks。

Target Network

上面提到，現在我們在訓練價值網絡時，一般會用 TD 方法，其訓練目標（以 Q 為例）為：
$$Q^{\pi }(s_t,a_t)\to r_t+Q^{\pi }(s_{t+1},a_{t+1})$$
會發現等式兩邊都有共享的、一直在更新的網絡 $Q^{\pi }$，因此網絡的擬合目標是在一直變的，雖然看起來上沒什么問題，但實際中這種情況下訓練通常會非常不穩定。Target Network 的技巧是我們將其中一個網絡（一般是圖中右下角那個）固定住，更新另一個網絡，這樣該網絡的擬合目標一直是固定的，比較易于訓練。在更新 $N$ 輪之后，同步一次固定網絡的參數。

Exploration

Exploitation v.s. Exploration 是強化學習中的一個重要課題，Exploitation 指利用已有的經驗獲取盡可能高的累積回報，Exploration 則是指訓練時不只關注短期的回報，而是也以一定概率采樣其他動作，盡量地探索是否有其他能贏得更高回報的可能選擇。

在之前介紹的 Policy Gradient 類算法中，策略網絡 ${\pi }_{\theta }$ 輸出的是一個動作空間的概率分布，每次執行的動作是從該分布中采樣得到，即使是概率相對較低的動作也有機會被采樣到，因此 Exploration 是已經被考慮在內的。

在剛剛介紹的 Q-learning 算法中，策略 $\pi$ 本身不是一個分布，而是對學習到的 Q 函數在各個動作中 argmax 得到，是一種 greedy 的策略，這就導致同一狀態下除了 Q 值最高的其他動作永遠不會被嘗試。假設初始化后，每個動作的默認 Q 值都是 0，那么最先被采樣到且獲得正 Q 值的動作就會一直被選中，而其它動作無法被探索到。因此，我們需要在 Q-learning 中引入一些機制來增強其 Exploration 能力。

Q-learning 中引入 Exploration 機制的思路其實很簡單，只要在訓練時，除了 argmax Q 之外，也給一定概率采樣到其他動作即可。一般常用的有兩種方法，一是 Epsilon Greedy，二是 Boltzmann Exploration。

Epsilon Greedy 是指選擇動作時大部分時候（$1??$）取 argmax Q 的動作，但是也有 $?$ 的概率不管 Q，直接隨機選取一個動作：
$$a=\{\begin{array}{ll}\arg {\max }_{a}Q(s,a),& \text{with?probability?}1??\\ \text{random},& \text{others}\end{array}$$
$?$ 是一個超參數，其值一般隨訓練過程衰減，因為我們在訓練前期更希望模型多多 Explore，后期則希望穩定的獲取高的回報分數。

Boltzmann Exploration 是指我們直接將各動作的 Q 值歸一化為一個分布，選取動作時從其中采樣
$$P(a|s)=\frac{\exp (Q(s,a))}{{\sum }_a\exp (s,a)}$$

這兩種方法都能使得 Q 值較低的動作也有一定概率選中，進行 Exploration。

Replay Buffer

在強化學習中，樣本效率也是一個很重要的問題，強化學習訓練過程的很大一部分耗時都花在策略 $\pi$ 與環境互動收集 rollout 數據上，真正的 GPU 計算梯度反傳更新模型其實是很快的。在 Q-learning 中，每個數據只會使用一次，這樣的樣本效率就不高。為了提高樣本的利用率，我們可以將策略 $\pi$ 與環境互動的經驗 $(s_t,a_t,r_t,s_{t+1})$ 保存到一個 Replay Buffer 中，每次訓練時從 Replay Buffer 中 sample 一個 batch 的數據用于訓練模型。Replay Buffer 技巧一來可以提高樣本的利用率，二來由于 Buffer 中所存的經驗樣本不一定來自于同一個 policy，因此也能提高每個 batch 內樣本的多樣性。

總結

本文我們先介紹了強化學習中的價值函數，然后介紹如何訓練價值網絡來擬合價值函數，以及 Q-learning/DQN 中如何不斷地優化 policy，最后介紹了 Q-learning 在實際實現中常用的幾個技巧。