強化學習： 貝爾曼方程與馬爾可夫決策過程
一、簡介
貝爾曼方程和馬爾可夫決策過程是強化學習非常重要的兩個概念，大部分強化學習算法都是圍繞這兩個概念進行操作。尤其是貝爾曼方程，對以後了解蒙特卡洛搜尋、時序差分算法以及深度強化學習算法都至關重要。這篇文章主要介紹貝爾曼方程。
常用的資料：
《Reinforcement Learning: An Introduction》 author: Richard S.Sutton and Andrew G.Barto
UCL Course: https://www.davidsilver.uk/teaching/
部落格園：https://www.cnblogs.com/pinard/
二、馬爾可夫決策過程
熟悉自然語言處理的同學一定對馬爾可夫（Markov）并不陌生，隐馬爾科夫模型，條件随機場中都有利用到馬爾可夫性質。馬爾可夫描述這樣一個随機過程：如果一個系統有 N N N個狀态 S 1 , S 2 , . . . , S N S_1,S_2,...,S_N S1,S2,...,SN，随着時間的推移，該系統從某一個狀态轉移到另一個狀态。如果用 q t q_t qt表示系統在時間 t t t的狀态變量，那麼 t t t時刻的狀态取值為 S j S_j Sj的機率取決于前 t − 1 t-1 t−1個時刻，該機率為：
p ( q t = S j ∣ q t − 1 = S i , q t − 2 = s k , . . . ) (1) \tag{1} p(q_t=S_j|q_{t-1}=S_i,q_{t-2}=s_k,...) p(qt=Sj∣qt−1=Si,qt−2=sk,...)(1)
意思很好了解，就是某一時刻狀态的取值，取決于前面所有時刻的狀态，畫圖表示為：
那麼這個模型猛一看并沒有什麼問題，我此時此刻的狀态是由前面所有時刻的狀态所決定的。但是它的緻命缺點則是，過于複雜。因為在計算某一個狀态的機率時，你需要利用前面所有的狀态值，那麼多的參數模型肯定複雜。是以馬爾可夫模型進行了兩個重要的簡化：1. 一階獨立性假設。任意一個時刻的狀态僅僅依賴于前一個時刻的狀态。這個很容易了解，用數學表示為：
p ( q t = S j ∣ q t − 1 = S i , q t − 2 = s k , . . . ) = p ( q t = S j ∣ q t − 1 = S i ) (2) p(q_t=S_j|q_{t-1}=S_i,q_{t-2}=s_k,...) = p(q_t=S_j|q_{t-1}=S_i)\tag{2} p(qt=Sj∣qt−1=Si,qt−2=sk,...)=p(qt=Sj∣qt−1=Si)(2)
畫圖表示為：
這樣一看，模型就簡化很多了，雖然可能會帶來模型上的誤差，但相比較于難以計算的複雜度，這點誤差還是可以接受的。2. 時間獨立性假設。可以設想這麼一個情況，如果時刻 j j j和時刻 j + 1 j+1 j+1的狀态是 a a a和 b b b，在 i i i和 i + 1 i+1 i+1時刻的狀态也分别是 a a a和 b b b，那麼時間獨立性可以表示為：
p 1 = p ( q j + 1 = b ∣ q j = a ) p 2 = p ( q i + 1 = b ∣ q i = a ) p 1 = p 2 (3) \begin{aligned} p_1&=p(q_{j+1}=b|q_j=a)\\ p_2&=p(q_{i+1}=b|q_i=a)\\\tag{3} p_1&=p_2 \end{aligned} p1p2p1=p(qj+1=b∣qj=a)=p(qi+1=b∣qi=a)=p2(3)
也就是隻要前一個時刻的狀态是 a a a，那麼後一個時刻的狀态是 b b b的機率是固定的，此機率和 a a a所在的時刻（ i i i或者 j j j）無關。那麼既然和時間是無關的，那麼由狀态 a a a轉移到狀态 b b b的機率就可以寫作：
p ( b ∣ a ) (4) p(b|a)\tag{4} p(b∣a)(4)
進而，我們得到馬爾可夫模型，一階獨立性假設和時間獨立性假設。
三、強化學習中的馬爾可夫決策過程
回想一下強化學習中的一個重要概念，機率轉化模型，也就是 p s s , a p^a_{ss^,} pss,a，代表的是，在狀态 s s s下，采取動作 a a a後，轉移到狀态 s , s^, s,的機率。此變量的定義其實已經暗含了馬爾科夫假設：狀态 s , s^, s,發生的機率僅僅和上一時刻的狀态 s s s相關。當然，還和動作 a a a相關，但這個動作 a a a可以看作是環境的輸入（想一想條件随機場）。是以，可以用數學表達為：
p s s , a = p ( s , ∣ s , a ) (5) p_{ss^,}^a=p(s^,|s,a)\tag{5} pss,a=p(s,∣s,a)(5)
這個假設極大的簡化了強化學習的狀态轉移矩陣。此外，除了馬爾可夫假設之外，還有一個比較重要的假設，就是對政策 π \pi π的假設，回想一下政策 π \pi π的定義，在狀态 s s s下，agent采取動作 a a a的機率，表達為機率形式：
π ( a ∣ s ) = p ( a ∣ s ) \begin{aligned} \pi(a|s)=p(a|s) \end{aligned} π(a∣s)=p(a∣s)
其實也隐含了一個假設，那就是agent的動作 a a a隻和狀态 s s s有關。
四、貝爾曼方程
如果要說強化學習中最重要的一個公式，那麼非貝爾曼方程莫屬了，本文将以圖表和公式的形式來解釋貝爾曼方程，争取能以一種接近人的思維去解釋貝爾曼方程。
首先引入一個變量，叫做動作價值函數， q π ( s , a ) q_{\pi}(s,a) qπ(s,a)，它的含義是在**狀态 s s s下，采取動作 a a a後所期望獲得的總回報。**對比一下價值函數 v π ( s ) v_\pi (s) vπ(s)的定義，狀态s下，期望獲得的總回報，顯然，二者的差別在于動作價值函數在狀态 s s s下多了一個動作 a a a的限制。言語無法解釋，直接上圖：
假設agent初始狀态為 A A A，在 t = 1 t=1 t=1時刻，采取了動作 a 11 a_{11} a11(其他可能的動作 a 12 , a 13 a_{12},a_{13} a12,a13)，那麼之後可能發生的狀态都如紅框中所示，而動作價值函數 q π ( s , a ) q_\pi(s,a) qπ(s,a)代表的就是紅框中所能獲得回報期望，也就是狀态 A A A到達所有紅框中葉子節點（終點）的回報期望值。從上節的定義中可知，價值函數 v π ( s ) v_\pi (s) vπ(s)代表從狀态 s s s到達所有葉子節點的總回報的期望，是以可以看出來，**動作價值函數隻是價值函數的一部分。**那麼怎麼由動作價值函數去獲得價值函數呢？看下圖：
如圖所示，我們可以把整個狀态樹可以分成三個分支，分别代表執行 a 11 a_{11} a11産生的動作價值函數 q π ( A , a 11 ) q_\pi(A,a_{11}) qπ(A,a11)，執行 a 12 a_{12} a12産生的動作價值函數 q π ( A , a 12 ) q_\pi(A,a_{12}) qπ(A,a12)，和執行 a 13 a_{13} a13産生的動作價值函數 q π ( A , a 13 ) q_\pi(A,a_{13}) qπ(A,a13)。而價值函數 v π ( A ) v_\pi(A) vπ(A)由于代表的是 A A A到達所有葉子節點的回報的期望，是以，将這三個分支相加不就是總的價值函數了嗎？由此可以得到下式
v π ( s ) = π ( a 11 ∣ A ) q π ( A , a 11 ) + π ( a 12 ∣ A ) q π ( A , a 12 ) + π ( a 13 ∣ A ) q π ( A , a 13 ) (6) v_\pi(s)=\pi(a_{11}|A) q_\pi(A,a_{11})+\pi(a_{12}|A)q_\pi(A,a_{12})+\pi(a_{13}|A)q_\pi(A,a_{13})\tag{6} vπ(s)=π(a11∣A)qπ(A,a11)+π(a12∣A)qπ(A,a12)+π(a13∣A)qπ(A,a13)(6)
注意由于是求期望，我們還要乘以各自分支發生的機率 π ( a ∣ s ) \pi(a|s) π(a∣s)。進而，我們得到了第一個重要的公式，也就是關關聯作價值函數和價值函數的等式：
v π ( s ) = ∑ a π ( a ∣ s ) q π ( s , a ) (7) v_\pi(s)=\sum_{a}\pi(a|s)q_\pi(s,a)\tag{7} vπ(s)=a∑π(a∣s)qπ(s,a)(7)
它代表的是，一個狀态的價值函數，由此狀态可能發生的動作價值函數構成，也就是一棵樹可以由若幹個分支構成，每一個分支是由一個動作産生，這個動作的機率由 π \pi π決定，此分支的動作價值函數記為 q π ( s , a ) q_\pi(s,a) qπ(s,a)。
-
貝爾曼方程
首先回想一下三個重要的等式,分别代表價值函數定義，動作價值函數定義，價值函數和動作價值函數的關系：
v π ( s ) = E π ( G t ∣ S t = s ) = E π ( R t + 1 + γ R t + 2 + γ 2 R t + 3 + . . . ∣ S t = s ) p π ( s , a ) = E π ( G t ∣ S t = s , A t = a ) = E π ( R t + 1 + γ R t + 2 + γ 2 R t + 3 + . . . ∣ S t = s , A t = a ) v π ( s ) = ∑ a π ( a ∣ s ) p π ( s , a ) (8) \begin{aligned} v_\pi(s)&=E_\pi(G_t|S_t=s)=E_\pi(R_{t+1}+\gamma R_{t+2}+\gamma^2R_{t+3}+...|S_t=s)\\\\ p_\pi(s,a)&=E_\pi(G_t|S_t=s,A_t=a)=E_\pi(R_{t+1}+\gamma R_{t+2}+\gamma^2R_{t+3}+...|S_t=s,A_t=a)\\\\\tag{8} v_\pi(s)&=\sum_a\pi(a|s)p_\pi(s,a) \end{aligned} vπ(s)pπ(s,a)vπ(s)=Eπ(Gt∣St=s)=Eπ(Rt+1+γRt+2+γ2Rt+3+...∣St=s)=Eπ(Gt∣St=s,At=a)=Eπ(Rt+1+γRt+2+γ2Rt+3+...∣St=s,At=a)=a∑π(a∣s)pπ(s,a)(8)
這三個公式非常重要，在後面的學習中會經常用到，是以一定要了解他們的含義，以及他們在狀态樹中代表着什麼。下面重點講解一下貝爾曼方程，首先是純數學推導：
v π ( s ) = E π ( R t + 1 + γ R t + 2 + γ 2 R t + 3 + . . . ∣ S t = s ) = E π ( R t + 1 + γ ( R t + 2 + γ R t + 3 + γ 2 R t + 4 + . . . ) ∣ S t = s ) = E π ( R t + 1 + γ G t + 1 ∣ S t = s ) = E π ( R t + 1 + γ v π ( S t + 1 ) ∣ S t = s ) (9) \begin{aligned} v_\pi(s)&=E_\pi(R_{t+1}+\gamma R_{t+2}+\gamma^2R_{t+3}+...|S_t=s)\\ &=E_\pi(R_{t+1}+\gamma(R_{t+2}+\gamma R_{t+3}+\gamma^2R_{t+4}+...)|S_t=s)\\\tag{9} &=E_\pi(R_{t+1}+\gamma G_{t+1}|S_t=s)\\ &=E_\pi(R_{t+1}+\gamma v_\pi(S_{t+1})|S_t=s) \end{aligned} vπ(s)=Eπ(Rt+1+γRt+2+γ2Rt+3+...∣St=s)=Eπ(Rt+1+γ(Rt+2+γRt+3+γ2Rt+4+...)∣St=s)=Eπ(Rt+1+γGt+1∣St=s)=Eπ(Rt+1+γvπ(St+1)∣St=s)(9)
遞推公式還是比較容易了解的，重點在于我們如何去了解這個公式。我們知道，狀态 s s s選擇一個動作後，會轉移到另一個狀态，其實貝爾曼方程描述的就是這樣一個過程：狀态 s s s的價值，可以由即時獎勵和後續狀态獲得。
如圖所示，狀态 s s s選擇一個動作後，可能會轉到某一個橘色狀态，如果我們知道了橘色狀态的價值（橘色節點代表的子樹所有葉子節點獎勵的總和的期望值），那麼我們就不需要知道計算到葉子節點了，因為橘色的狀态足以代表葉子節點。進而，貝爾曼方程實際上為我們提供了一個遞歸的方式求解問題：計算根節點的價值時，不需要周遊整棵樹，而隻需要利用根節點的子節點價值。這不是遞歸的典型特點嗎？一個大的問題（求解整棵樹的價值)可以由子問題去求解（子節點的價值)。同理，我們也可以得到動作價值函數的貝爾曼方程：
q π ( s , a ) = E π ( R t + 1 + γ Q ( S t + 1 , A t + 1 ) ∣ S t = s , A t = a ) (17) q_\pi(s,a)=E_\pi(R_{t+1}+\gamma Q(S_{t+1}, A_{t+1})|S_t=s, A_t=a)\tag{17} qπ(s,a)=Eπ(Rt+1+γQ(St+1,At+1)∣St=s,At=a)(17)
貝爾曼方程是我們後續動态規劃、時序差分算法的基礎，一定要了解其中的含義。
動作價值函數和價值函數的關系
上文我們提到，一個重要的等式可以揭示價值函數動作價值函數的關系：
v π ( s ) = ∑ a π ( a ∣ s ) q π ( s , a ) (11) v_\pi(s)=\sum_{a}\pi(a|s)q_\pi(s,a)\tag{11} vπ(s)=a∑π(a∣s)qπ(s,a)(11)
那麼，動作價值函數是否可以利用價值函數去獲得呢？上面說到，每一個動作價值函數其實代表樹的一個分支，如下圖紅框所示：
利用貝爾曼方程的思想，這一分支的價值可以由即時獎勵和橘色框狀态的價值之和構造，同樣是一個動态規劃的思想，是以我們有：
q π ( A , a 11 ) = R 1 + γ p A B a 11 v π ( B ) + γ p A C a 11 v π ( C ) (12) q_\pi(A,a_{11})=R_1+\gamma p_{AB}^{a_{11}}v_\pi(B) + \gamma p_{AC}^{a_{11}}v_\pi(C)\tag{12} qπ(A,a11)=R1+γpABa11vπ(B)+γpACa11vπ(C)(12)
當然，實際計算的過程，我們應該還要向上述一樣，考慮狀态轉移到其他狀态的機率，通用的公式則可以表示為：
q π ( s , a ) = R s a + ∑ s , p s s , a v π ( s , ) (13) q_\pi(s,a)=R_s^a+\sum_{s^,}p_{ss^,}^av_\pi(s^,)\tag{13} qπ(s,a)=Rsa+s,∑pss,avπ(s,)(13)
他代表的含義是：動作價值函數，可以由即時獎勵，以及後續狀态的價值，權重求和得到，放在樹中，其實就是一個動态規劃的思想。
那麼，既然價值函數可以由動作價值函數得到，動作價值函數也可以由價值函數得到，價值函數能不能通過價值函數得到呢？同理，動作價值函數能不能通過價值函數得到呢？答案當然是可以的：
v π ( s ) = ∑ a π ( a ∣ s ) ( R s a + γ ∑ s , p s s , a v π ( s , ) ) (14) v_\pi(s)=\sum_a\pi(a|s)(R_s^a+\gamma\sum_{s^,}p_{ss^,}^av_\pi(s^,))\tag{14} vπ(s)=a∑π(a∣s)(Rsa+γs,∑pss,avπ(s,))(14)
這個其實就是我們将公式(13)代入公式（11）得到的，但是我們不要死記硬背，我們需要去了解。同理，我們可以得到：
q π ( s , a ) = R s a + γ ∑ s , p s s , a ∑ a , π ( a , ∣ s , ) q π ( s , , a , ) (15) q_\pi(s,a)=R_s^a+\gamma\sum_{s^,}p_{ss^,}^a\sum_{a^,}\pi(a^,|s^,)q_\pi(s^,,a^,)\tag{15} qπ(s,a)=Rsa+γs,∑pss,aa,∑π(a,∣s,)qπ(s,,a,)(15)
是将（11）式代入（13）式得到的結果。
至此我們得到了幾個非常重要的公式：
價 值 函 數 定 義 ： v π ( s ) = E π ( G t ∣ S t = s ) = E π ( R t + 1 + γ R t + 2 + γ 2 R t + 3 + . . . ∣ S t = s ) 動 作 價 值 函 數 定 義 ： p π ( s , a ) = E π ( G t ∣ S t = s , A t = a ) = E π ( R t + 1 + γ R t + 2 + γ 2 R t + 3 + . . . ∣ S t = s , A t = a ) 價 值 函 數 貝 爾 曼 方 程 ： v π ( s ) = E π ( R t + 1 + γ v π ( S t + 1 ) ∣ S t = s ) 動 作 價 值 函 數 貝 爾 曼 方 程 ： q π ( s , a ) = E π ( R t + 1 + γ Q ( S t + 1 , A t + 1 ) ∣ S t = s , A t = a ) 動 作 價 值 函 數 到 價 值 函 數 ： v π ( s ) = ∑ a π ( a ∣ s ) p π ( s , a ) 價 值 函 數 到 動 作 價 值 函 數 ： q π ( s , a ) = R s a + ∑ s , p s s , a v π ( s , ) 價 值 函 數 到 價 值 函 數 ： v π ( s ) = ∑ a π ( a ∣ s ) ( R s a + γ ∑ s , p s s , a v π ( s , ) ) 動 作 價 值 函 數 到 動 作 價 值 函 數 ： q π ( s , a ) = R s a + γ ∑ s , p s s , a ∑ a , π ( a , ∣ s , ) q π ( s , , a , ) (16) \begin{aligned} 價值函數定義：v_\pi(s)&=E_\pi(G_t|S_t=s)=E_\pi(R_{t+1}+\gamma R_{t+2}+\gamma^2R_{t+3}+...|S_t=s)\\\\ 動作價值函數定義：p_\pi(s,a)&=E_\pi(G_t|S_t=s,A_t=a)=E_\pi(R_{t+1}+\gamma R_{t+2}+\gamma^2R_{t+3}+...|S_t=s,A_t=a)\\\\ 價值函數貝爾曼方程：v_\pi(s)&=E_\pi(R_{t+1}+\gamma v_\pi(S_{t+1})|S_t=s)\\\\ 動作價值函數貝爾曼方程：q_\pi(s,a)&=E_\pi(R_{t+1}+\gamma Q(S_{t+1}, A_{t+1})|S_t=s, A_t=a)\\\\\tag{16} 動作價值函數到價值函數：v_\pi(s)&=\sum_a\pi(a|s)p_\pi(s,a)\\\\ 價值函數到動作價值函數：q_\pi(s,a)&=R_s^a+\sum_{s^,}p_{ss^,}^av_\pi(s^,)\\\\ 價值函數到價值函數：v_\pi(s)&=\sum_a\pi(a|s)(R_s^a+\gamma\sum_{s^,}p_{ss^,}^av_\pi(s^,))\\\\ 動作價值函數到動作價值函數：q_\pi(s,a)&=R_s^a+\gamma\sum_{s^,}p_{ss^,}^a\sum_{a^,}\pi(a^,|s^,)q_\pi(s^,,a^,) \end{aligned} 價值函數定義：vπ(s)動作價值函數定義：pπ(s,a)價值函數貝爾曼方程：vπ(s)動作價值函數貝爾曼方程：qπ(s,a)動作價值函數到價值函數：vπ(s)價值函數到動作價值函數：qπ(s,a)價值函數到價值函數：vπ(s)動作價值函數到動作價值函數：qπ(s,a)=Eπ(Gt∣St=s)=Eπ(Rt+1+γRt+2+γ2Rt+3+...∣St=s)=Eπ(Gt∣St=s,At=a)=Eπ(Rt+1+γRt+2+γ2Rt+3+...∣St=s,At=a)=Eπ(Rt+1+γvπ(St+1)∣St=s)=Eπ(Rt+1+γQ(St+1,At+1)∣St=s,At=a)=a∑π(a∣s)pπ(s,a)=Rsa+s,∑pss,avπ(s,)=a∑π(a∣s)(Rsa+γs,∑pss,avπ(s,))=Rsa+γs,∑pss,aa,∑π(a,∣s,)qπ(s,,a,)(16)
這些公式，我們都可以找到他們的實體含義，都可以找到他們在狀态樹上的定義，我們一定要了解着去記憶，明白他們數學推導後的實體含義。