實踐非同步DQN

強化學習作為一種普適的近似規劃演算法在各個領域都有廣泛用途，和深度學習的結合更是發揮出讓人想像不到的能力。本文就基於值(valued based)的深度Q學習進行進階介紹和實踐。

1. Q學習基礎

強化學習是由獎勵信號驅動的學習方式，智能體通過不斷的和環境交互試錯來調整自身，從而達到期望獎勵最大的目標。強化學習的基礎理論是馬爾可夫過程(MDP)和貝爾曼(Bellman)方程。強化學習理論成熟，博大精深。而Q學習是強化學習中被廣泛應用一種。其優勢在於是無模型(Model Free)和離線學習(off-policy)，即不需要對模型本身建模，且學習和執行策略可以不是一個過程。這對於許多試錯成本比較大的環境如機器人、自動飛行器等有重大的意義。 Q學習也可以看做從離線的數據源中學習並將學習到的知識遷移到實際環境中來。Q學習是基於值估計的(value based)，也就是說通過索引或者估計每個狀態-動作值Q(s,a)，這樣在做實際策略時可以選擇使得Q值最大的動作。當使用表格法進行索引的時候，Q學習理論收斂。基於MDP和值函數的強化學習有以下基本公式：

上式又被稱為貝爾曼方程。其中值函數V表示某個狀態s有多好，而動作值函數Q表示在狀態s下的某個動作有多好，「有多好」不是當前看起來好，而是考慮到長期回報。帶星號的部分表示最優化。轉移概率P又被稱為對模型的建模，通常大多數環境是一個黑盒子，而智能體往往只能部分觀察環境，比如電玩遊戲(atari game)中，智能體只能觀察到視頻的每一幀，而其內部的狀態集則是不可見的。在交易市場中往往包含了其他交易的人/智能體，但是我們只能看見交易數據本身，無法對其他所有潛在智能體進行建模。由於上式是一個期望，故可以用採樣來進行估計，同時使用指數滑動平均進行平滑處理，這樣就省去了對環境建模：

上式可以看成一步向前的時序差分學習(Temporal-Difference Learning)。即在每個狀態s下採取一個動作a, 得到一個獎勵r, 同時轉移到下一個狀態s』。這時根據Q表以及s』估計這個狀態下最佳動作導致的Q值。 在實際中一步向前估計可能會導致較大的偏差(bias)，但是擁有較小的方差(Variance)。可以使用n步向前的方式用額外的計算量改善偏差。這一點在A3C中也有用到。更多強化學習理論知識可以參考Sutton的教程，目前已經有最新版在線閱讀。[1]

2. DQN：Deep Q-Network

在大部分應用中，對(1)式使用查表方法是不可行的，這是因為其狀態甚至動作空間幾乎是無限的，同時查表法對於未探索的狀態毫無辦法，哪怕是這個狀態（比如圖像）和已緩存的狀態有多麼相似。故需要一種方法來對狀態值V(s)以及狀態動作值Q(s,a)進行函數逼近。DeepMind提出了基於深度學習的強化學習框架：DQN[2]以及一系列的改進。考慮到神經網路可以近似任意函數以及CNN本質是對於層次化數據的特徵提取，DQN+CNN能勝具有層次結構的狀態數據的學習。對於離散的動作集，DQN將數據直接輸入，通過多層神經網路後直接輸出各動作的Q值。其核心仍然是Bellman方程：

上式左邊是網路輸出，右邊可以看成一個已知的更新目標(target)，注意到這也是一步向前的TD目標。這可以看成有監督學習中的標記值，所以只需要最小化目標值和網路輸出Q值之間的誤差即可，這樣目標函數可以用MSE或者Huber loss，那麼權重的梯度更新可以寫成：

和純粹的有監督學習演算法不同的是，上面的目標值target是不斷變化的，可以稱之為「半梯度更新」 。仔細觀察上式，目標和估計值使用了同一套參數 ，而且參數隨著梯度下降過程中每次目標值都使用上一次更新的參數，這樣會間接導致目標值依賴於之前的數據，給原本假設是獨同分布的數據帶來關聯性。另一方面，一步向前的TD值存在較大的偏差，訓練中不斷的修改本應是相對固定的值，只會使得訓練更加不穩定。鑒於此DeepMind提出使用TD目標網路(Target Network)，其結構和原DQN一樣，參數記為 ，原理很簡單，計算目標值時總是使用目標網路，這個網路是相對凍結的，而每隔一段時間將原網路的參數 拷貝給 即可。於是目標函數就可以改寫成：

在DDPG[3]的論文中使用了用指數滑動平均的方法逐漸更新目標網路：

實現DQN中最重要的還有經驗回放(Experience Replay)。經驗回放借鑒了生物學中的海馬體。通常在智能體的一次經歷中，從初始到結束的所有狀態有著明顯的關聯關係，那麼沿著這條軌跡進行數據採樣並依次送給DQN訓練，這違背了數據獨同分布的原則。解決方案是在互動的過程中將經驗(s,a,r,s』)存起來，在訓練的時候從中進行均勻隨機採樣。由於Q學習是off-policy的，儘管在記憶中的經驗是從不同階段的策略（參數）中得到，Q學習依然可以從中學習。很容易看出來，經驗回放最大的問題在於內存消耗。在atari遊戲的訓練中存儲了一百萬個經驗，而每個經驗的狀態又是由4張圖片堆疊而成，這將消耗數十G的內存。同時上面說到Q學習是離線學習，往往需要大量的探索來保證其收斂性。常見的探索的方式有ε-greedy, softmax，UCB等等。

3. Double DQN

在實際的訓練過程中，存在著各種誤差，比如環境雜訊，估計偏差以及各種非穩定因素。仔細觀察上面的Q學習更新式子可以發現都帶有max操作，而在決策的過程通常使用貪婪策略 。這將會帶來過估計(Overestimate)的問題。試想在某一次更新過程中過估計了一個Q(s,a)，那麼這個經歷會用於更新權重並可能在接下來帶來更多的過估計。最終這個過估計量如果是非均勻的，那麼會影響到最後決策，因為對於貪婪選擇來說，10.001的Q值也要比10來的好。DoubleDQN[4]就是用於解決這個問題，其思路是通過將動作選擇（max操作）和動作估計Q(s』,a』)解耦。原始的DQN的TD估計可以寫成：

也就是先選擇一個具有最大Q值的動作a』, 然後再用這個動作的Q值進行更新。前面說到用目標網路來延遲獲取目標值，將其用於上式就得到了Double Q-learning的TD值：

上式中還是使用目標網路 Q』來進行目標值估計。但是使用最新的網路Q（現實網路）來選擇動作。如果現實網路Q對某個動作高估進而選擇了，但是目標網路Q』不一定是高估這個動作的；反之如果Q』高估某個動作，但是Q不一定會選擇，除非Q和Q』同時高估某個狀態-動作對。這大幅度降低了原本DQN高估狀態動作值的幾率。

4. Dueling DQN

DuelingDQN[5]是用優勢函數(Advantage)的方法，將DQN進行結構上的改進，但是輸出不變。優勢函數的定義如下：

由值函數V的定義 可以看出V是狀態s下所有動作值函數的期望，反應了該狀態下能採取的所有的動作能獲取的長期回報的平均。從這個角度來值函數是全局的，動作值函數是局部的，所以優勢函數反映了某個狀態-動作值函數相對這個狀態的「優勢」，即比平均來說要好多少。換言之優勢函數衡量了某狀態下每個動作的重要程度。DuelingDQN就是同時在網路中學習狀態函數V(s)以及優勢函數A(s,a)，結構如下：

如圖上面一部分是傳統的DQN，即通過一系列特徵提取器最後用全連接輸出各個Q(s,a)。下面一部分是DuelingDQN，在特徵層後被分為兩個支路，上面一支用於學習標量V(s)，下面一支用於學習向量A(s,a)，最後兩者加起來即得到了Q(s,a)。

很多環境的狀態比如Atari遊戲的某些圖像是對動作不敏感的。也就是說不管採取任何動作都對環境影響不大。試想在直道行駛的賽車並且周圍都沒有對手，那麼學習這個狀態下的狀態動作值其實是不足以用來做策略的，換言之此種狀態的特定動作策略都不如隨機選擇一個的好，但這一點DQN無法做到。此外Q學習通常使用ε-greedy等方法保證足夠的探索，對於較大的動作空間來說，幾乎很難保證每個動作都被嘗試到。仔細觀察在原DQN中其實每次只更新了某一個特定動作，改進後的Dueling結構每次都在同時更新值函數V。所以對於一些沒有嘗試過的動作使用值函數來進行估計要比DQN用參數直接輸出猜測的好，這在一定程度上改善了原始DQN過度依賴於ε-greedy探索的情況。針對這個Dueling DQN的論文在atari 57 games上做了大量實驗，通過在原來的簡單動作集上加入30個no-actions的動作(什麼都不做)，這相當於大幅度減少了有效動作被探索到的幾率，實驗證明對於此種情況Dueling的結構完勝原始DQN，同時效率更高。

當然在上面的結構中為了避免兩個支路直接學習到V(s)=0或者A(s,a)=0的情況，需要做一些額外處理：

上式加入約束後迫使網路總是朝著最優的 進行學習。論文指出此處使用平均值將更加穩定：

現在優勢函數只需要追蹤平均變化即可。採用以上架構的DuelingDQN更加具有魯棒性，在一定程度上改善了DQN和DDQN的數值敏感的問題。

實現Dueling結構比較簡單，比如用keras的實現如下：

x = feature_map # 前面是特徵層 advantage = Dense(self.nb_actions, activation=linear, name=advantage)(x)v = Dense(1, activation=linear, name=v)(x)#output_q = Add()([advantage, v], name=output_q) 最原始的實現#實現1 使得學習到a*#output_q = Lambda(lambda z: z[0] + z[1] - K.max(z[0], axis=-1, keepdims=True), name=output_q)([advantage, v])#實現2 使得學習的a比優勢函數的期望要好，因為有的情況a*是多個甚至很難探索到的。output_q = Lambda(lambda z: z[0] + z[1] - K.max(z[0], axis=-1, keepdims=True), name=output_q)([advantage, v])#Q和輸入動作的one_hot編碼內積，得到對應動作的Q值。q_hat = Dot(axes=-1, normalize=False)([input_action, output_q])model = Model(inputs=[input_img, input_action], outputs=q_hat)

值得一提的是TD(0)可以看成優勢函數的無偏估計，該特性被用在Advantage Actor-Critic方法中以簡化結構。(將會在下一篇文章中詳細介紹該方法)。

5. 非同步DQN

2016年DeepMind提出了非同步強化學習框架[6]，包含了非同步Q學習/n步前向Q學習，非同步SARSA以及著名的A3C。這一類非同步方法的核心是非同步梯度更新。通過並行化的進程，每個進程擁有一個單獨的環境實例，智能體在每個進程內單獨交互使用本地模型累積梯度，本地模型不定時的從共享模型拷貝參數，交互結束後提交梯度給共享的全局模型進行更新。這就像火影忍者裡面的「影分身之術」，每個分身學習到的經驗最後累積給本體。其架構如下：

這裡的參數模型不一定是一台實體server，也可以是一個進程，故又分為Scale Up和Scale Out的區別，後者適用於大規並行強化學習，比如google的Gorila。非同步框架同時對on-policy的方法如Sarsa和Actor-Critic以及off-policy的方法如Q學習都適用。對於非同步DQN來說還可以省去經驗回放的開銷，因為並行的進程使用獨立的環境，各個進程使用的參數拷貝也不盡然完全相同，這近似的可以看成每個智能體在用不同的策略在和環境交互，這樣不同的進程累計的梯度可以看成是沒有關聯的。用並行的技術不僅解耦了數據關聯，同時也大大縮短了訓練時間。

6. 實現解析

由於涉及到模型共享參數和多進程操作，我使用pytorch來實現所有功能。詳細代碼請移步這裡。由上圖的整體結構， 主模型的參數是共享內存的。在每個子進程內使用不同的環境、不同的隨機數種子以及一個本地模型。

6.1 模型構建

模型本身非常簡單代碼如下：

def __init__(self, state_space, nb_action, dueling=True): super(QModel, self).__init__() self.state_space = state_space self.nb_action = nb_action self.dense1 = nn.Linear(state_space, 64) self.dense2 = nn.Linear(64, 32) if dueling: self.dense_advantage = nn.Linear(32, nb_action) self.dense_v = nn.Linear(32, 1) self.dense_q = nn.Linear(32, nb_action)

這裡僅僅使用了簡單的MLP。當然在更大的環境中一般使用CNN作為特徵提取器。在forward裡面實現了DuelingDQN：

def forward(self, state, action): x = F.relu(self.dense1(state)) x = F.relu(self.dense2(x)) if self.dueling: self.advantage_q = (self.dense_advantage(x)).view(-1, self.nb_action) self.v = (self.dense_v(x)).view(-1, 1) q_val = self.advantage_q + self.v - self.advantage_q.mean(dim=1, keepdim=True) else: q_val = self.dense_q(x) self.q_values = q_val q_hat = q_val.mul(action).sum(-1, keepdim=True) return q_hat

為了觀察V和advantage我將它們單獨保存下來。這裡對advantage使用mean和max即可實現上述兩種Dueling結構。自動求導機制會保證反向傳播時這裡也一起被計算了。

6.2 模型參數共享

在主進程中有DQN需要的目標網路以及主更新網路，使用share_memory函數可以方便的將模型參數設置為在進程間共享。同時pytorch提供了和python自帶庫具有相同介面的torch.multiprocessing類，利用process類可以創建多進程。在創建的子進程中用一個本地模型用於累積梯度。其中Q學習的關鍵代碼如下：

q_pred = target_model(next_state, max_action)y_target = reward + gamma * dw * q_pred.detach()model_output = model(state, action_one_hot)loss = crit(model_output, y_target)loss.backward() #積累梯度state = next_statewith lock: moving_copy_to_target(shared_model, target_model, tau=0.95)

上面代碼實現了Double DQN的邏輯。利用backword的特性只要不把模型參數的梯度清空，在這一次經歷裡面會一直累積梯度。在實踐上最後加入梯度裁剪會更好。在這次經歷結束後，將本地累計的梯度拷貝給主模型然後更新：

nn.utils.clip_grad_norm(model.parameters(), 10.)with lock: optimizer.zero_grad() copy_shared_grads(model, shared_model, counter) optimizer.step()

6.3 共享RMSprop

優化器(optimizer)對主模型進行參數更新，簡單情況下每個進程內單獨使用SGD即可。但是在強化學習中RMSprop被廣泛使用。所以有必要實現一個在非同步環境下能使用的RMSprop。RMSprop的原理是用滑動平均累積梯度變化的二階動量使得各個參數能自適應梯度變化學習率。所以只需要找到pytorch中RMSprop的具體實現，將二階動量部分改成共享內存，更新演算法不變。故在此不贅述。

7. 總結

以上簡單總結了DQN實現過程中的一些技巧，對非同步強化學習框架進行了實踐。當然無法介紹完全，比如優先經驗回放[7]、NoisyNet[8]和n步向前的DQN等等。將這些林林總總的技巧集大成起來就得到了葫蘆金剛，哦不Rainbow[9]，感興趣的朋友可以移步看這個實現。

引用：

1. Richard Sutton: Reinforcement Learning: An Introduction.
2. Volodymyr Mnih et al, 2015: Human-level control through deep reinforcement learning
3. Timothy P. Lillicrap et al, 2015: Continuous control with deep reinforcement learning
4. H van Hasselt et al, 2015: Deep Reinforcement Learning with Double Q-learning
5. Ziyu Wang et al, 2016: Dueling Network Architectures for Deep Reinforcement Learning
6. Volodymyr Mnih et al, 2016: Asynchronous Methods for Deep Reinforcement Learning
7. Tom Schaul et al, 2015: Prioritized Experience Replay
8. Meire Fortunato et al, 2017: Noisy Networks for Exploration
9. Matteo Hessel et al, 2017: Rainbow: Combining Improvements in Deep Reinforcement Learning

推薦閱讀：