論文名稱：Playing Atari with Deep Reinforcement Learning
論文地址：http://www.cs.toronto.edu/~vmnih/docs/dqn.pdf

相關論文：Human-level control through deep reinforcement learning
論文地址：https://storage.googleapis.com/deepmind-data/assets/papers/DeepMindNature14236Paper.pdf

強化學習在自然語言處理的文本生成方向上有不少的應用，本篇博客主要涉及對強化學習原理的決議，
《Playing Atari with Deep Reinforcement Learning》是2013年DeepMind發表在NIPS上的論文，為深度強化學習的開山之作，主要講解了如何基于游戲資料幀（一幅幅游戲影像），使用深度強化學習在游戲上通關，《Human-level control through deep reinforcement learning》是對上一篇論文的改進，2015年發表于nature，

一、強化學習的基本原理

1.什么是強化學習

我們給出一堆紅蘋果和青蘋果的照片（每張照片中只有一個蘋果），通過影像識別能夠辨別圖片中蘋果的紅綠，因為我們事先已經對蘋果的照片進行了標注，比如紅蘋果標記為1，青蘋果標記為0，機器從我們事先標記的照片中學得資訊，再用于別的蘋果照片（監督學習），但是這樣存在一個問題，這些蘋果的初始標注是怎么來的，沒有初始標注如何學習標注同類物體的能力？我們人類在與環境不斷的互動，不斷的進行試錯才學習得到辨別物體的能力，強化學習能從無標注的某類物體中學習知識，并能由此采取利益最大化的決策，
強化學習與我們人類的學會走路方式相似，一開始跌跌撞撞，在摔倒這個疼的環境反饋下，我們走下一步會越來越好，作用機制如下圖所示，我們先觀察環境狀態(state)，然后采取行動(action)，獲得反饋（reward），通過上一步的行動，我們進入新環境，根據reward中學到的知識采取下一步動作，可以這么認為，強化學習就是智能體（agent）在與環境的互動程序中通過學習策略以達成回報最大化或實作特定目標的程序，

2.強化學習的要素

（1）環境狀態 S {\rm{S}} S， t t t時刻環境狀態為 S t {S_t} St?，
（2）個體(例子中是人，也可以是其它，通常稱為agent智能體）的動作A， t t t時刻采取的動作為 A t {A_t} At?，
（3）環境的獎勵的 R {\rm{R}} R， t t t時刻在環境狀態 S t {S_t} St?，采取 A t {A_t} At?動作,獲得的獎勵 R t + 1 {R_{{\rm{t + 1}}}} Rt+1?(某個動作采取后，下一時刻才能獲得回報），獎勵可為正獎勵和負獎勵（懲罰），
（4）個體的策略(policy)π，是個體采取動作的根據， π ( a ∣ s ) = P ( A t = a ∣ S t = s ) \pi (a|s) = P({A_t} = a|{S_t} = s) π(a∣s)=P(At?=a∣St?=s)表示在 t t t時刻狀態 S t {S_t} St?下，個體根據π策略采取動作 A t {A_t} At?的概率，一般最大概率動作就是我們采取的下一步動作，
（5）個體在策略π和狀態 S {\rm{S}} S時，采取行動后的價值（value），一般用 v π ( s ) {v_\pi }(s) vπ?(s)表示，雖然我們已經有了一個延時獎勵 R t + 1 {R_{{\rm{t + 1}}}} Rt+1?，但是很多情況下我們不能僅僅只看當前的回報，比如我們的目標是讓我們生活舒適，現在我們拿了一萬塊錢工資，前幾天大吃大喝會讓我們相當舒服，但后邊的日子就會相當難受，即我們不能僅僅考慮下一步的獎勵，還得考慮后續的獎勵， v π ( s ) {v_\pi }(s) vπ?(s)可用公式表示：

v π ( s ) = E π ( R t + 1 + γ R t + 2 + γ 2 R t + 3 + . . . ∣ S t = s ) = E π ( R t + 1 + γ v π ( S t + 1 ) ∣ S t = s ) {v_\pi }(s) = {E_\pi }({R_{t + 1}} + \gamma {R_{t + 2}} + \gamma 2{R_{t + 3}} + ...\mid {S_t} = s){\rm{ = }}{E_\pi }({R_{t + 1}} + \gamma {v_\pi }({S_{t + 1}})|{S_t} = s) vπ?(s)=Eπ?(Rt+1?+γRt+2?+γ2Rt+3?+...∣St?=s)=Eπ?(Rt+1?+γvπ?(St+1?)∣St?=s)

E π {E_\pi } Eπ?表示的是后n步的數學期望； γ \gamma γ是獎勵衰減因子，在[0,1]區間， γ \gamma γ=0為只考慮下一步的貪心演算法， γ \gamma γ=1后續n步和下一步的同等重要， γ \gamma γ一般取(0,1)，表示下一步的獎勵最重要，但是其他后續獎勵同樣不可忽略，
（6）動作價值函式 q π ( s , a ) {q_\pi }(s,a) qπ?(s,a)，表示在每個狀態s下采取動作a帶來的價值影響，計算公式如下：
q π ( s , a ) = E π ( G t ∣ S t = s , A t = a ) = E π ( R t + 1 + γ R t + 2 + γ R t + 3 + . . . ∣ S t = s , A t = a ) = E π ( R t + 1 + γ q π ( S t + 1 , A t + 1 ) ∣ S t = s , A t = a ) {q_\pi }(s,a) = {E_\pi }({G_t}|{S_t} = s,{A_t} = a) = {E_\pi }({R_{t + 1}} + \gamma {R_{t + 2}}{\rm{ + }}\gamma {R_{t + 3}}{\rm{ + }}...|{S_t} = s,{A_t} = a) = {E_\pi }({R_{t + 1}} + \gamma {{\rm{q}}_\pi }({S_{t + 1}},{A_{t + 1}})|{S_t} = s,{A_t} = a) qπ?(s,a)=Eπ?(Gt?∣St?=s,At?=a)=Eπ?(Rt+1?+γRt+2?+γRt+3?+...∣St?=s,At?=a)=Eπ?(Rt+1?+γqπ?(St+1?,At+1?)∣St?=s,At?=a)
（7）狀態轉換機，在狀態s下采取動作a,轉到下一個狀態s′的概率，表示為 P s s ′ a {\rm{P}}_{ss'}^a Pss′a?，
（8）探索率?，我們在行動時一般會采取最有利的，但是這樣也會導致一些陌生的行動方式沒有被我們考慮到，此時我們有一定的概率采取別的行動，該概率為?，一般來說，隨著時間推移?會越來越小，表示我們的行動已經逐漸利益最大化，采取別的行動對我們效益逐漸減小，

3.計算方法

實際中，強化學習的建模非常復雜，需要引入馬爾科夫程序，我們假設某個狀態s轉移到下一個狀態s’不與之前的狀態產生關系，即某一狀態僅與上一狀態有關（馬爾科夫性），
在狀態s下采取動作a，轉移到下一個狀態s’的概率計為 P s s ′ a {\rm{P}}_{ss'}^a Pss′a?，用公式表示為：
P s s ′ a = E ( S t + 1 = s ′ ∣ S t = s , A t = a ) {\rm{P}}_{ss'}^a = E({S_{t + 1}} = s'|{S_t} = s,{A_t} = a) Pss′a?=E(St+1?=s′∣St?=s,At?=a)
假設在狀態s時采取動作僅與當前狀態s有關（同樣是馬爾科夫性），公式表示為：
π ( a ∣ s ) = P ( A t = a ∣ S t = s ) \pi (a|s) = P({A_t} = a|{S_t} = s) π(a∣s)=P(At?=a∣St?=s)
根據動作價值函式 q π ( s , a ) {q_\pi }(s,a) qπ?(s,a)和狀態價值函式 v π ( s ) {v_\pi }(s) vπ?(s)的定義，容易得到他們之間的轉化關系公式：
v π ( s ) = ∑ a ∈ A π ( a ∣ s ) q π ( s , a ) {v_\pi }(s) = \sum\limits_{a \in A} {\pi (a|s){q_\pi }(s,a)} vπ?(s)=a∈A∑?π(a∣s)qπ?(s,a)
反過來，我們也容易得到狀態價值函式 v π ( s ) {v_\pi }(s) vπ?(s)表示動作價值函式 v π ( s ) {v_\pi }(s) vπ?(s):
q π ( s , a ) = R s a + γ ∑ s ′ ∈ S P s s ′ a v π ( s ′ ) {q_\pi }(s,a) = R_s^a + \gamma \sum\limits_{s\prime \in S} {P_{ss\prime }^a{v_\pi }(s\prime )} qπ?(s,a)=Rsa?+γs′∈S∑?Pss′a?vπ?(s′)
其實兩個公式可以用一句話概括：某一個狀態的價值可以用該狀態下所有動作的價值表述；某一個動作的價值可以用該狀態后續狀態的價值表達，
價值函式 v π ( s ) {v_\pi }(s) vπ?(s)公式的變體:
v π ( s ) = ∑ a ∈ A π ( a ∣ s ) ( R s a + γ ∑ s ′ ∈ S P s s ′ a v π ( s ′ ) ) {v_\pi }(s) = \sum\limits_{a \in A} {\pi (a|s)(R_s^a + \gamma \sum\limits_{s\prime \in S} {P_{ss\prime }^a{v_\pi }(s\prime )} )} vπ?(s)=a∈A∑?π(a∣s)(Rsa?+γs′∈S∑?Pss′a?vπ?(s′))
動作價值函式 v π ( s ) {v_\pi }(s) vπ?(s)的變體：
q π ( s , a ) = R s a + γ ∑ s ′ ∈ S P s s ′ a ∑ a ′ ∈ A π ( a ′ ∣ s ′ ) q π ( s ′ , a ′ ) {q_\pi }(s,a) = R_s^a + \gamma \sum\limits_{s\prime \in S} {P_{ss\prime }^a\sum\limits_{a' \in A} {\pi (a'|s'){q_\pi }(s',a')} } qπ?(s,a)=Rsa?+γs′∈S∑?Pss′a?a′∈A∑?π(a′∣s′)qπ?(s′,a′)

4.最優價值函式

強化學習的關鍵在于找到一個最優策略，讓智能體與環境的互動程序中獲得最大收益，我們記這個最優策略為 π ? {\pi ^*} π?，
尋找最優策略也就是找最優價值函式，我們記錄該函式為 v ? ( s ) {v_*}(s) v??(s)，計算方法如下：
v ? ( s ) = max ? π v π ( s ) {v_*}(s) = \mathop {\max }\limits_\pi {v_\pi }(s) v??(s)=πmax?vπ?(s)
同理可得最優策略函式:
q ? ( s , a ) = max ? π q π ( s , a ) {q_*}(s,a) = \mathop {\max }\limits_\pi {q_\pi }(s,a) q??(s,a)=πmax?qπ?(s,a)
最優策略，基于動作價值函式我們可以定義為：
π ? ( a ∣ s ) = { 0 e l s e 1 i f a = a r g m a x a ∈ A q ? ( s , a ) {\pi _ * }(a|s) = \left\{ {_{0{\rm{ }}{\kern 1pt} {\rm{else}}}^{1{\rm{ }}{\kern 1pt} if{\kern 1pt} {\rm{ }}a = \mathop {argmax}\limits_{a \in A} {\rm{ }}{\kern 1pt} q * (s,a)}} \right. π??(a∣s)={0else1ifa=a∈Aargmax?q?(s,a)?
利用狀態價值函式和動作價值函式之間的關系，可得最優狀態價值函式：
v ? ( s ) = m a x a q ? ( s , a ) {v_*}(s) = \mathop {max{\rm{ }}}\limits_a {q_*}(s,a) v??(s)=amax?q??(s,a)
反過來，最優動作價值函式為:
q ? ( s , a ) = R s a + γ ∑ s ′ ∈ s P s s ′ a v ? ( s ′ ) {q_*}(s,a) = R_s^a + \gamma \sum\limits_{s' \in s} {P_{ss'}^a{v_*}(s')} q??(s,a)=Rsa?+γs′∈s∑?Pss′a?v??(s′)
最優狀態價值函式 v ? {{v_*}} v??公式的變體:
v ? ( s ) = max ? a ( R s a + γ ∑ s ′ ∈ s P s s ′ a v ? ( s ′ ) ) {v_*}(s) = \mathop {\max }\limits_a (R_s^a + \gamma \sum\limits_{s' \in s} {P_{ss'}^a} {v_*}(s')) v??(s)=amax?(Rsa?+γs′∈s∑?Pss′a?v??(s′))
最優動作價值函式 q ? ( s , a ) {q_*}(s,a) q??(s,a)公式的變體：
q ? ( s , a ) = R s a + γ ∑ s ′ ∈ s P s s ′ a max ? a ′ q ? ( s ′ , a ′ ) {q_*}(s,a) = R_s^a + \gamma \sum\limits_{s' \in s} {P_{ss'}^a\mathop {\max }\limits_{a'} } {\rm{ }}{{\rm{q}}_*}(s',a') q??(s,a)=Rsa?+γs′∈s∑?Pss′a?a′max?q??(s′,a′)

5.應用舉例

狀態轉換圖如下，設定左上、左邊、中間和右邊的圓圈分別為v1、v2、v3、v4，正方形為m，現在的任務是求v2到m的R之和最大化的路徑，

為了方便，我們假設衰減因子 γ = 1 \gamma {\rm{ = 1}} γ=1, π ( a ∣ s ) = 0 . 5 \pi {\rm{(a|s) = 0}}{\rm{.5}} π(a∣s)=0.5，
基于公式 v π ( s ) = ∑ a ∈ A π ( a ∣ s ) ( R s a + γ ∑ s ′ ∈ S P s s ′ a v π ( s ′ ) ) {v_\pi }(s) = \sum\limits_{a \in A} {\pi (a|s)(R_s^a + \gamma \sum\limits_{s\prime \in S} {P_{ss\prime }^a{v_\pi }(s\prime )} )} vπ?(s)=a∈A∑?π(a∣s)(Rsa?+γs′∈S∑?Pss′a?vπ?(s′))，可以列出方程組：
v1位置：v1=0.5?(?1+v1)+0.5?(0+v2)
v2位置：v2=0.5?(?1+v1)+0.5?(?2+v3)
v3位置：v3=0.5?(0+0)+0.5?(?2+v4)
v4位置：v4=0.5?(10+0)+0.5?(1+0.2?v2+0.4?v3+0.4?v4)
解出這個方程組可以得到v1=?2.3,v2=?1.3,v3=2.7,v4=7.4, 即每個狀態的價值函式如下圖：

此時我們通過 v ? ( s ) {{v_*(s)}} v??(s)和 q ? ( s , a ) {q_*}(s,a) q??(s,a)價值公式(即每次都走最優路徑，然后更新v和q），不斷迭代可得到如下最終狀態圖，理想路徑為v2->v3->v4->m，

二、深度強化學習

1.價值函式的選擇

我們許多任務都通過深度學習來完成，比如影像識別和語音處理，但強化學習在之前適用于單一領域（特征手工提取）或低維資料，難以應用在高維資料領域(影像或語音等），
難以應用的一個重要原因是價值函式難以確定，我們往往只能手工設定，無法保證準確性，自然而然有了用神經網路去擬合價值函式的想法，而這也是DeepMind論文的重點，
用神經網路預測價值有三種常見方式，如下圖所示，第一種方式(左邊網路)，我們輸入當前狀態得到當前狀態的狀態價值；第二種方式(中間網路)，輸入狀態和動作，輸出動作價值；第三種方式(右邊網路)，輸入狀態，輸出每個可能動作的動作價值，

論文采用第三種方式，如下圖，我們輸入一張圖片，輸出所有可能動作的價值，其中箭頭表示向某個方向移動；紅色的點可以表示為射擊或跳躍，不同游戲組合狀態不一定相同，

2.價值函式引數的更新

一般而言，游戲角色存活越久其相對得分越高，以下圖游戲為例，飛機有向敵軍射擊和向某一邊移動兩種動作，我們飛機存活的越久，得分也相應越高，

那么相應得出一個想法結論，我們設計目標價值函式時，當下一狀態我們的飛機為毀滅狀態，設定價值回報較低，即可達到有效更新網路的目標，記當前狀態價值為 Q ( φ j , a j ; θ ) Q({\varphi _j},{a_j};\theta ) Q(φj?,aj?;θ)，采取最優策略后下一狀態價值為 Q ( φ j + 1 , a ′ ; θ ) Q({\varphi _{j + 1}},{a_{}}';\theta ) Q(φj+1?,a?′;θ)，則我們的目標價值計算方法如下圖所示( r j {r_j} rj?表示得分變化，比如我們多活一個狀態就加1分)，當我們飛機下一狀態被擊毀時，價值為 r j {r_j} rj?，此時價值最小，表示游戲結束，我們定義損失函式為 ( y j ? Q ( φ j , a j ; θ ) ) 2 {({y_j} - Q({\varphi _j},{\rm{ }}{a_j};\theta ))^2} (yj??Q(φj?,aj?;θ))2，通過與最小價值狀態的互動，網路可不斷收斂，

3.總體設計

解決了大問題，仍存在許多其它困難，
主要困難：

1. DL需要大量帶標簽的樣本進行監督學習；RL只有reward回傳值，而且伴隨著噪聲，延遲（過了幾十毫秒才回傳），稀疏（很多state的reward為0）等問題，
2. DL的樣本獨立；RL前后狀態相關，
3. DL目標分布固定；RL的分布一直變化，比如玩一個游戲，一個關卡和下一個關卡狀態分布不一致，所以我們通過一關訓練的網路，到下一關又要重新訓練，
4. 過往的研究表明，使用非線性網路表示值函式出現不穩定等問題，

解決辦法：

1. 深度強化學習使用reward來構造標簽，解決回報延遲問題(對應問題1)，
2. 通過經驗池的方法解決RL前后狀態相關和分布固定的問題(對應問題2和3)，我們把曾經放入訓練的資料，訓練后的結果和下一狀態資料投入經驗池，然后再從經驗池隨機取資料，也就是說我們不再像以前一樣一關關的訓練，而是不斷存放我們訓練過的片段，再隨機抽取，零碎的訓練，這部分和人類回憶機制相關聯，在2015年的nature論文中甚至介紹了該機制和大腦海馬體的相似之處，
3. 引入target-netword(對應問題4)，目標網路不再實時更新，而是每過一段時間將價值網路的引數復制給它，也就是說目標網路和價值網路架構完全一致，只是為了防止目標和價值關聯過于親密，而通過分隔賦值的方法，這也是2015的nature論文對2013的nips論文改進的一個地方，此處可以舉一個簡單的例子，有一個跳水運動員在進行訓練，裁判進行評分，跳水運動員根據裁判的評分改進自己的動作，但是一開始我們并沒有裁判，那該怎么辦呢？我們將跳水運動員的知識灌輸到一個和跳水運動員長得一模一樣的克隆體身上，讓他當裁判，一開始跳水運動員每次訓練完，教練評完分，跳水運動員就馬上將自己學到的知識傳給教練，這相當于每次運動員訓練完，教練馬上改指標，會出現一個人既當教練又當裁判的問題，這樣無法保證公平性，所以我們每隔一段時間再把運動員訓練完的感悟傳給教練，教練在這一段時間內評分標準不變，就可以保證公正性的問題了（后期強化學習的Actor-Critic也與之相似，但是Actor和Critic分開的更徹底），

主要困難解決后，引入具體演算法流程：
初始化replay memory D(記憶回放，也叫經驗池)，容量為N用于存盤訓練的樣本，
初始化行為價值網路函式Q的卷積神經網路，引數 θ \theta θ隨機初始化，
初始化target行為價值網路函式的卷積神經網路(簡寫為target-Q)，結構和Q相同，引數 θ ? {\theta _*} θ??初始等于Q的引數 θ \theta θ，
For episode=1,M do（總共訓練M個回合）
初始化狀態序列s1，并對其進行預處理得到4*84*84的視頻幀（處理程序簡寫為 φ 1 = φ ( s 1 ) {\varphi _1} = \varphi (s1) φ1?=φ(s1)，4代表輸入資料是最后四幀，84*84表示輸入圖片大小）
for t=1,T do（一次最多訓練T個時間片的資料，防止落入區域最優解）
以概率?（探索率）選擇一個一個隨機動作 a t {a_t} at?，否則選擇最優價值動作（此處?是衰減的，可以認為是模擬退火演算法的退火率，時間越長現有網路越好，落入區域最優解概率越小，探索其它區域的概率也應越小）
執行動作 a t {a_t} at?可以得到獎勵 r t {r_t} rt?以及新影像 x t + 1 {x_{t + 1}} xt+1?（比如我們讓飛機向上飛， x t + 1 {x_{t + 1}} xt+1?是飛行完后的游戲影像），游戲往前移動一幀，依然是4幀的影像，再次處理得到新的網路輸入，
把（ φ t {\varphi _t} φt?， a t {a_t} at?， r t {r_t} rt?， φ t + 1 {\varphi _{t + 1}} φt+1?）資料放入經驗池D，
從經驗池中隨機抽取小批次（ φ t {\varphi _t} φt?， a t {a_t} at?， r t {r_t} rt?， φ t + 1 {\varphi _{t + 1}} φt+1?）資料用于下一次訓練，
使用target-Q得到目標價值 y j {y_j} yj?，利用損失函式 ( y j ? Q ( φ j , a j ; θ ) ) 2 {({y_j} - Q({\varphi _j},{\rm{ }}{a_j};\theta ))^2} (yj??Q(φj?,aj?;θ))2計算loss，反向傳播訓練網路，
每迭代C次，將Q網路的引數復制給target-Q網路，
end
end
下圖是nips論文的演算法流程，nature對此進行了改進：

總結：論文構建一個全新智能體，構建深度學習Q和target-Q網路，能從高維資料中學習到知識，進行端到端的強化學習訓練，在2013的NIPS論文，作者將該方法應用于7款雅達利游戲，它在其中6個游戲上優于所有之前的方法，在3個游戲上超過了人類專家，2015的nature論文，作者將該方法用于49款游戲，它在43款游戲中表現出超于之前所有強化學習演算法，超過一半的游戲中智能體玩游戲的能力高于75%的人類，表現出RL強大的學習能力，