從強化學習到深度強化學習（下）

05-03

強化學習的基礎知識可參考：

kevinbauer：從強化學習到深度強化學習（上）?

zhuanlan.zhihu.com

從離散空間到連續空間

在之前提到的強化學習任務中，都是有限的MDP框架，即動作空間及狀態空間的個數都是有限個。然而，現實生活中的很多問題動作空間與狀態空間並非離散的，而是連續的。那麼如何用強化學習的理論基礎去解決問題呢？主要有兩種思路：離散化處理、函數逼近。

離散化處理：

指的是把連續空間用區域o化的方式劃分成有限的個數。具體的處理手法有Tile coding及Coarse coding。

函數逼近：

指的是把輸入與輸出看作是經過某個函數的映射，然後用梯度更新的方法找到這個函數。具體的處理手法有線性函數逼近、核函數逼近、以及非線性函數逼近。

深度強化學習常用的演算法思路有以下三種：深度Q學習、策略梯度、行動者與評論者方法。以下逐一總結這三種思路的特點。

深度Q學習

對於傳統的強化學習，我們的解題思路是通過計算最優值函數（包括狀態值函數 $v_*$ 以及動作值函數 $q_*$ ），從而求得最優策略 $pi_*$ 。而狀態值函數可以看作是狀態 $s$ 到某實數的映射： $s ightarrow v_{pi} ightarrow v_{pi}(s) in mathbb{R}$ 。而在連續空間的問題時，狀態 $s$ 一般以向量 $mathbb{x}(s)$ 表示，因此可以看作是狀態向量 $mathbb{x}(s)$ 到某實數的映射： $mathbb{x}(s) ightarrow v_{pi} ightarrow v_{pi}(s, w) in mathbb{R}$ 。

於是我們就有了目標函數 $[v_{pi}(s,w) - hat v_{pi}(s,w)]^2$ ，然後就可以通過梯度下降演算法做函數逼近， $Delta w = alpha(v_{pi}(s) - hat v(s,w)) riangledown _w hat v(s,w)$ 。

同時，對於動作值函數，也有 $Delta w = alpha (q_{pi}(s, a) - hat q(s,a,w)) igtriangledown _w hat q(s,a,w)$ 。

然而，問題是此時我們並不知道 $v_{pi}$ 與 $q_{pi}$ 的函數真值是多少。於是，需要用兩種方法去估算函數真值：蒙特卡羅方法與時間差分方法。

蒙特卡羅方法：

我們從前面的經驗可知，基於值函數（ $v_{pi}$ 或 $q_{pi}$ ）的方法，解題的思路都是 $( v_{pi} ightarrow ) q_{pi} ightarrow pi$ ，而 $v_{pi}$ 或 $q_{pi}$ 的更新公式為：

$V(S_t) leftarrow V(S_t) + alpha (G_t - V(S_t)))$
$Q(S_t, A_t) leftarrow Q(S_t, A_t) + alpha (G_t - Q(S_t, A_t)))$

在更新公式中可以看到每次的更新的效果為：

$Delta V = alpha(G_t - V(S_t))$
$Delta Q = alpha(G_t - Q(S_t, A_t))$

值函數的迭代過程，本質上就是一個不精確的（誤差很大）的值函數，逐漸更新收斂形成精確的值函數的過程。假如把這過程理解為梯度下降，我們便可以把 $G_t$ 看作是值函數 $v_{pi}(S_t)$ 與 $q_{pi}(S_t)$ 的真值，於是有：

$Delta w = alpha (G_t - hat v(S_t, w))igtriangledown _w hat v(S_t, w)$
$Delta w = alpha (G_t - hat q(S_t,A_t, w))igtriangledown _w hat q(S_t, A_t, w)$

有了以上轉換，便可以通過Tensorflow等運算框架去計算梯度，從而求得值函數的真值。寫成偽代碼如下圖：

資料來源：Udacity深度學習課程

代碼說明：

以上偽代碼使用的背景是針對階段性任務，並且使用的 $G_t$ 是全訪問（every visit，MC演算法專用定義）

時間差分方法：

對於時間差分方法，我們有值函數：

$V(S_t) leftarrow V(S_t) + alpha(R_{t+1} + gamma V(S_{t+1}) - V(S_t))$
$Q(S_t, A_t) leftarrow Q(S_t, A_t) + alpha (R_{t+1} + gamma Q(S_{t+1},A_{t+1}) - Q(S_t, A_t))$

與MC方法同理，TD方法的梯度更新公式可以寫成：

$Delta w = alpha (R_{t+1} + gamma hat v(S_{t+1},w) - hat v(S_t,w))igtriangledown _w hat v(S_t,w)$
$Delta w = alpha (R_{t+1} + gamma hat q(S_{t+1},A_{t+1}, w) - hat q(S_t,A_t, w))igtriangledown _w hat q(S_t, A_t, w)$

於是，寫成偽代碼如下圖：

資料來源：Udacity深度學習課程

代碼說明：

該代碼是針對階段性任務。若要針對連續任務，只需修改循環條件；
Sarsa演算法屬於同步策略（on-policy），即更新值函數與行動用的是同一套策略；
該演算法適合在線學習，能夠快速收斂；
但該演算法的更新值函數與行動之間的關聯過於緊密，導致可能無法得到更優的策略

針對Sarsa的不足，Q-learning是另一種選擇，偽代碼如下圖：

資料來源：Udacity深度學習課程

代碼說明：

Q-learning與Sarsa演算法最大的不同，在於更新值函數時的策略與行動策略可能不同；
Q-learning屬於非同步策略（off-policy），即更新值函數的策略與行動策略不同；
該演算法適合離線學習，因為值函數的更新會延遲反應在行動策略的改變上；
該演算法不單能學習環境反饋，還能學習人為經驗；
更適合批量學習（batch learning）

以上提到的演算法，僅僅解決了深度學習中梯度更新的問題。除了梯度更新，如何讓智能體實現通用學習？Deep Q Network，又稱DQN。

DQN指的是模型結構是DNN，CNN，RNN等常見的神經網路模型，而梯度更新則是上述提及深度Q-learning的 $Delta w = alpha (R_{t+1} + gamma max_a hat q(S_{t+1},a, w) - hat q(S_t,A_t, w))igtriangledown _w hat q(S_t, A_t, w)$ ，並以此進行函數逼近。

DQN的訓練過程需要大量的訓練數據，即便這樣，由於狀態輸入向量與動作輸出向量之間的緊密聯繫，導致無法保證函數能夠收斂成為最優值函數，從而也導致策略不穩定或者效果不佳。為了解決這個問題，需要用到以下兩種處理手法來優化訓練過程。

經驗回放

以動作值函數為例，我們知道梯度更新公式為 $Delta w = alpha (R_{t+1} + gamma max_a hat q(S_{t+1},a, w) - hat q(S_t,A_t, w))igtriangledown _w hat q(S_t, A_t, w)$ ，因此對於每次更新計算，都需要用到一組經驗元組 $<S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1}>$ 。在有限MDP問題中，我們更新值函數時，每組經驗元組會且只會使用一次；而（在無限MDP）我們使用DQN時，我們可以使用一個暫存區，把一定數量的經驗元組暫存起來，然後能暫存區積累一定數量的經驗元組時，再從暫存區隨機抽取經驗元組進行訓練。這樣做有兩個好處：一是通過隨機抽取經驗元組，人為地切斷了元組之間的前後關聯關係，這樣可以使函數避免落入局部最優；二是使一組經驗元組可能會被使用多次，使得函數能更好地收斂。

通過經驗回放處理，相當於把一個強化學習問題轉化成一個監督學習問題。

固定Q目標

在梯度更新公式 $Delta w = alpha (R_{t+1} + gamma max_a hat q(S_{t+1},a, w) - hat q(S_t,A_t, w))igtriangledown _w hat q(S_t, A_t, w)$ 中， $R_{t+1} + gamma max_a hat q(S_{t+1},a, w)$ 實際上是梯度更新的目標值（TD target）。然而，權值 $w$ 是一個變化量，從而導致目標值隨之改變。這就好比坐在驢背手持蘿蔔來教驢直線走路，如下圖：

資料來源：Udacity深度學習課程

由於驢在移動的過程中會同時移動蘿蔔的位置，因此這樣是無法教會驢走直線的。正確的做法是，人站在地上固定不動，讓驢靠近時，人再往後退使驢可以繼續走，如下圖：

資料來源：Udacity深度學習課程

同理，梯度更新時，目標值的權值應該用一個固定權值代替，使權值更新若干次後，再用最新的權值替換一次固定權值，如此類推。

深度Q學習的具體演算法

以上關於深度Q學習已經作了足夠的鋪墊，以下來看看偽代碼：

資料來源：Udacity深度學習課程

代碼說明：

數組D用於暫存經驗元組，容量為N個；
以隨機數初始化動作值函數的權值 $w$ ；
並以 $w$ 初始化固定權值 $w^-$ ；
設置M代訓練循環；
對於每一代都要重新初始化起始狀態向量；
對於每一代的每個時間步，主要做兩件事：生成經驗元組與訓練；
生成的經驗元組存於數組D；
從數組D獲取隨機批量的經驗，先計算TD目標值，再進行梯度更新計算；
每隔C步就更新一次固定權值 $w^-$ 。

深度Q學習的優化思路

$diamond$ 雙DQN（Double DQN）

從DQN的梯度更新公式 $Delta w = alpha (R_{t+1} + gamma max_a hat q(S_{t+1},a, w) - hat q(S_t,A_t, w))igtriangledown _w hat q(S_t, A_t, w)$ 可知，其中的 $max_a hat q(S_{t+1},a, w) = hat q(S_{t+1}, argmax_a hat q(S_{t+1},a,w), w)$ 。由於在訓練的初始階段， $hat q$ 函數的值並不準確，我們並不應該太過盲目地信任這些值，並以此作為行動依據。那麼怎麼才能使策略更可靠呢？

其中一個被驗證的方法是雙DQN（論文《Deep Reinforcement Learning with Double Q-learning》）。大概的思路如下圖：

資料來源：Udacity深度學習課程

對於公式中的兩個權值 $w$ ，使用不同的權值。這樣就相當於使用了兩個DQN，一個用於生成策略，另一個用於評估策略。如果使用之前提到的固定Q目標的方法與雙DQN方法結合的話，固定權值 $w^-$ 就可以作為評估器使用。

$diamond$ 優先經驗回放

前面提到經驗回放，我們會在經驗暫存區隨機取樣進行批量訓練。然而，有些經驗比較「寶貴」出現的概率不高，但「信息量」很大，如果能進行多次訓練，能有效提升DQN的性能。那麼如何定義哪些經驗元組更「寶貴」呢？

答案是TD error，如下圖：

資料來源：Udacity深度學習課程

TD誤差越大，代表實際與預測的差距越大，因此「信息量」越大，模型能從中學到的規律就越多。因此，在保存經驗元組時，可以用優先隊列進行保存，以TD誤差的絕對值作為優先順序。在經驗抽樣時，不再以均勻分布來抽取，而按照優先順序的分值分配概率。

以上的處理經過證明，能減少值函數所需的批次更新數量（論文《Prioritized Experience Replay》）。

在上述處理的基礎上，還能進行幾處優化：

資料來源：Udacity深度學習課程

如果一個經驗元組的TD誤差很小甚至為零，那麼它在抽樣時被抽中的概率就幾乎為零，但這並不代表這個經驗就不值得學習，也許只是因為模型在之前所經歷的經驗樣本有限，使估值比較接近真實值而已；因此在原來TD誤差的基礎上加上一個常量e作為優先順序得分，從而讓這些經驗元組也有可能被選中。
另一個問題是，如果優先順序得分較高的經驗總是會大概率地被不斷回放，這可能會導致模型過擬合於這部分經驗子集；為了避免這個問題，對經驗的優先順序得分加上一個指數 $a$ ，這就相當於降低了 $p_i$ 的概率，因為當 $a=0$ 時，相當於以均勻的概率選擇經驗元組，而當 $a = 1$ 時就以優先順序得分作為概率計算。
當我們使用優先順序得分抽樣時，我們需要微調更新規則，加上權重係數。具體原因可參考論文。

$diamond$ 對抗網路架構（Dueling Networks）

資料來源：Udacity深度學習課程

對抗網路與原始DQN的主要區別在於全連接層從一個變為兩個，具體參考論文《Dueling Network Architectures for Deep Reinforcement Learning》。

深度Q學習是一種基於值函數的方法（value-based method），即根據狀態值或動作值函數來獲得最優策略。而有另一種方法，直接求最優策略而無需基於值函數（policy-based method），這就是策略梯度。

策略梯度（policy gradient）

既然已經有了基於值函數的方法，為何還需要有直接求最優策略的方法呢？

$diamond$ 因為更簡單：

最優策略 $pi_*$ 本質上是一個策略函數。

對於確定性策略而言，策略函數實際上是 $s ightarrow a$ 的映射；
對於隨機性策略而言，策略函數實際上是 $s ightarrow mathbb P[a|s]$ 概率分布的映射；

直接求策略函數的好處是可以減少對大量無關數據的儲存。

$diamond$ 因為能生成最優的隨機策略：

基於值函數的方法，無法生成真正的隨機策略，如下圖：

資料來源：Udacity深度學習課程

智能體的目標是要拿到香蕉。辣椒代表懲罰。智能體能感知當前狀態下周圍的環境，當智能體位於中間時，由於三邊無牆，向下移動是最優策略；當智能體位於兩邊時，當左邊有牆則向右移動為最優，而當右邊有牆則向左移動為最優。但當智能體位於陰影區域時，兩塊陰影區域的狀態完全一樣，如下圖：

資料來源：Udacity深度學習課程

如果根據值函數求最優策略，會形成要麼全部向左，要麼全部向右的策略，這樣會導致智能體陷入死循環。即便使用 $epsilon$ 係數來增加策略的隨機性，也需要很長的時間才能讓智能體「摸索」到出路，這樣的模型效率相當低；如果增大 $epsilon$ 係數，則會嚴重影響模型性能。因此，最優的策略是在陰影區域使用隨機策略，如下圖：

資料來源：Udacity深度學習課程

基於值函數的方法傾向於學習確定性策略或者近似確定性策略，而基於策略的方法能學習期望的隨機性策略。

$diamond$ 因為對於連續的動作空間，基於值函數的方法並不適用：

我們知道在基於值函數的方法中，最優策略是用 $argmax$ 函數求出，這僅僅適用於離散的動作空間；要在連續的動作空間中找最大值並不容易，尤其是當動作空間不是一維而是多維。因此，需要使用策略梯度方法。

那麼究竟如何求得策略函數呢？

策略函數逼近法：

（未完待續）

行動者與評論者方法

參考資料：

Udacity深度學習進階課程P5，課程優惠碼：6E1CAAC8
《Reinforcement Learning: An Introduction》，Richard S. Sutton and Andrew G. Barto
《蒙特卡洛方法到底有什麼用 - CSDN博客》
Monte Carlo method, en.wikipedia.org