強化學習——從Q-Learning到DQN到底發生了什麼？

05-10

1 學習目標

1. 複習Q-Learning；

2. 理解什麼是值函數近似（Function Approximation）；

3. 理解什麼是DQN，弄清它和Q-Learning的區別是什麼。

2 用Q-Learning解決經典迷宮問題

現有一個5房間的房子，如圖1所示，房間與房間之間通過門連接，編號0到4,5號是房子外邊，即我們的終點。我們將agent隨機放在任一房間內，每打開一個房門返回一個reward。圖2為房間之間的抽象關係圖，箭頭表示agent可以從該房間轉移到與之相連的房間，箭頭上的數字代表reward值。

圖1 房子原型圖

圖2 抽象關係圖

根據此關係，可以得到reward矩陣為

Q-Learning是一種off-policy TD方法，偽代碼如圖所示

Q-Learning偽代碼

我們首先會初始化一個Q表，用於記錄狀態-動作對的值，每個episode中的每一步都會根據下列公式更新一次Q表

$Qleft( S_t,A_t ight) gets Qleft( S_t,A_t ight) +alpha left[ R_{t+1}+gamma underset{a}{max}Qleft( S_{t+1},a ight) -Qleft( S_t,A_t ight) ight]$

這裡的迷宮問題，每一次episode的結束指的是到達終點狀態5。為了簡單起見，這裡將學習率 $alpha$ 設為1，更新公式變為

$Qleft( S_t,A_t ight) gets R_{t+1}+gamma underset{a}{max}Qleft( S_{t+1},a ight)$

另外，將衰減係數 $gamma$ 設為0.8。Q表初始化為一個5×5的全0矩陣。下面這個小視頻展示了一個episode中一步的更新過程，每次這樣更新，最終Q表會收斂到一個矩陣。

https://www.zhihu.com/video/970368234306883584

最終Q表收斂為

因此，也可以得到最優路徑如下紅色箭頭所示

Python代碼：

import numpy as npGAMMA = 0.8Q = np.zeros((6,6))R=np.asarray([[-1,-1,-1,-1,0,-1], [-1,-1,-1,0,-1,100], [-1,-1,-1,0,-1,-1], [-1,0, 0, -1,0,-1], [0,-1,-1,0,-1,100], [-1,0,-1,-1,0,100]])def getMaxQ(state): return max(Q[state, :])def QLearning(state): curAction = None for action in range(6): if(R[state][action] == -1): Q[state, action]=0 else: curAction = action Q[state,action]=R[state][action]+GAMMA * getMaxQ(curAction)count=0while count<1000: for i in range(6): QLearning(i) count+=1print(Q/5)

Q-Learning方法很好的解決了這個迷宮問題，但是這終究只是一個小問題（狀態空間和動作空間都很小），實際情況下，大部分問題都是有巨大的狀態空間或者動作空間，想建立一個Q表，內存是絕對不允許的，而且數據量和時間開銷也是個問題。

3 值函數近似與DQN

值函數近似（Function Approximation）的方法就是為了解決狀態空間過大，也稱為「維度災難」的問題。通過用函數而不是Q表來表示 $Qleft( s,a ight)$ ，這個函數可以是線性的也可以使非線性的。

$hat{v}left( s,oldsymbol{w} ight) approx v_{pi}left( s ight) or hat{q}left( s,a,oldsymbol{w} ight) approx q_{pi}left( s,a ight)$

其中 $oldsymbol{w}$ 稱為「權重」。那怎麼把這個權重求出來，即擬合出這樣一個合適的函數呢？這裡就要結合機器學習演算法里的一些有監督學習演算法，對輸入的狀態提取特徵作為輸入，通過MC/TD計算出值函數作為輸出，然後對函數參數 $oldsymbol{w}$ 進行訓練，直到收斂。這裡主要說的是回歸演算法，比如線性回歸、決策樹、神經網路等。

這裡，就可以引入DQN（Deep Q-Network）了，實際上它就是Q-Learning和神經網路的結合，將Q-Learning的Q表變成了Q-Network。

好，現在關鍵問題來了。這麼去訓練這個網路呢？換句話說，怎麼去確定網路參數 $oldsymbol{w}$ 呢？第一，我們需要一個Loss Function；第二，我們需要足夠的訓練樣本。

訓練樣本好說，通過 $varepsilon -greedy$ 策略去生成就好。回憶一下Q-Learning，我們更新Q表是利用每步的reward和當前Q表來迭代的。那麼我們可以用這個計算出來的Q值作為監督學習的「標籤」來設計Loss Function，我們採用如下形式，即近似值和真實值的均方差

$Jleft( oldsymbol{w} ight) =mathbb{E}_{oldsymbol{pi }}left[ left( q_{pi}left( s,a ight) -hat{q}left( s,a,oldsymbol{w} ight) ight) ^2 ight]$

採用隨機梯度下降法（SGD）來迭代求解，得到我們想要的 $oldsymbol{w}$ ，具體公式和過程還請看參考資料，這裡不展開了，其實就是求導啦。值得一提的是，上述公式中的 $q_{pi}left( s,a ight)$ 根據不同方法算出來，其形式不一樣，比如利用MC，則為 $G_t$ （回報）；利用TD(0)，則為 $R_{t+1}+gamma hat{q}left( s_{t+1},a_{t+1},oldsymbol{w} ight)$ ；Q-Learning呢，就是 $R_{t+1}+gamma max hat{q}left( s_{t+1},a_{t+1},oldsymbol{w} ight)$ 。

在David Silver的課里，他根據每次更新所參與樣本量的不同把更新方法分為增量法（Incremental Methods）和批處理法（Batch Methods）。前者是來一個數據就更新一次，後者是先攢一堆樣本，再從中採樣一部分拿來更新Q網路，稱之為「經驗回放」，實際上DeepMind提出的DQN就是採用了經驗回放的方法。為什麼要採用經驗回放的方法？因為對神經網路進行訓練時，假設樣本是獨立同分布的。而通過強化學習採集到的數據之間存在著關聯性，利用這些數據進行順序訓練，神經網路當然不穩定。經驗回放可以打破數據間的關聯。

最後附上DQN的偽代碼

DQN偽代碼

學到這裡，其實可以做一個階段性總結了，強化學習演算法的基本框架可以用下圖概括

強化學習框架

本專欄文章介紹了這個圖裡的大部分內容，但最重要、應用最為廣泛的policy-based方法還沒有介紹，這也是後面要著重去學習的。

參考

[1]Reinforcement Learning: An Introduction - Chapter 9: On-policy Prediction with Approximation

[2]Reinforcement Learning: An Introduction - Chapter 10: On-policy Control with Approximation

[3]David Silvers RL Course Lecture 6 - Value Function Approximation (video, slides)

[4]DQN從入門到放棄5 深度解讀DQN演算法

[5]一條鹹魚的強化學習之路6之值函數近似（Value Function Approximation）和DQN