正在學習RL—1，記錄總結自己的學習過程，并在原文基礎上增加一點自己的了解，防止自己以後忘記。
求解強化學習問題可以了解為如何最大化個體在與環境互動過程中獲得的累積獎勵。環境 的動力學特征确定了個體在互動時的狀态序列和即時獎勵，環境的狀态是建構環境動力學特征 所需要的所有資訊。當環境狀态是完全可觀測時，個體可以通過建構馬爾科夫決策過程來描述整個強化學習問題。有時候環境狀态并不是完全可觀測的，此時個體可以結合自身對于環境的曆史 觀測資料來建構一個近似的完全可觀測環境的描述。從這個角度來說，幾乎所有的強化學習問題 都可以被認為或可以被轉化為馬爾科夫決策過程。正确了解馬爾科夫決策過程中的一些概念和 關系對于正确了解強化學習問題非常重要。
在一個時序過程中，如果 \(t + 1\) 時刻的狀态僅取決于 \(t\) 時刻的狀态 \(S_{t}\) 而與 \(t\) 時刻之前的任何狀态都無關時，則認為 \(t\) 時刻的狀态 \(S_t\) 具有馬爾科夫性 (Markov property)。若過程中的每一 個狀态都具有馬爾科夫性，則這個過程具備馬爾科夫性。具備了馬爾科夫性的随機過程稱為馬爾科夫過程 (Markov process)，又稱馬爾科夫鍊 (Markov chain)。馬爾科夫過程中的每一個狀态 \(S_t\) 記錄了過程曆史上所有相關的資訊，而且一旦 St 确定了，那麼曆史狀态資訊 S1 ...St−1 對于确 定 St+1 均不再重要，可有可無。
描述一個馬爾科夫過程的核心是狀态轉移機率矩陣：
\[P_{ss'=P\left[ S_{t+1}=s'|S_t=s \right]}\ \ \ \ \ \ \ \left( 2.1 \right)
\]
公式 (2.1) 中的狀态轉移機率矩陣定義了從任意一個狀态 \(s\) 到其所有後繼狀态 \(s’\) 的狀态轉移機率：
\[P=from\overset{to}{\left| \begin{matrix}
P_{11}& .& .& .& P_{1n}\\
.& & & & \\
P_{n1}& .& .& .& Pnn\\
\end{matrix} \right|}\ \ \ \ \ \ \ \ \ \ \left( 2.2 \right)
其中，矩陣 \(P\) 中每一行的資料表示從某一個狀态到所有 n 個狀态的轉移機率值。每一行的 這些值加起來的和應該為 1。例如第一行，\(P_{11}\).....\(P_{1n}\) 即從1号結點到 \(1\).......\(n\) 号結點的狀态轉移機率。其中，如果\(1\).......\(n\)存在一些結點不為\(1\)号結點的next結點，即對應的轉移機率為零
通常使用一個元組 \(⟨S,P⟩\) 來描述馬爾科夫過程，其中 \(S\) 是有限數量的狀态集，\(P\) 是狀态轉移機率矩陣
圖 2.1 描述了一個假想的學生學習一門課程的馬爾科夫過程。在這個随機過程中，學生需要 順利完成三節課并且通過最終的考試來完成這門課程的學習。當學生處在第一節課中時，會有 50% 的幾率拿起手機浏覽社交軟體資訊，另有 50% 的幾率完成該節課的學習進入第二節課。一 旦學生在第一節課中浏覽手機社交軟體資訊，則有 90% 的可能性繼續沉迷于浏覽，而僅有 10% 的幾率放下手機重新聽講第一節課。學生處在第二節課的時有 80% 的幾率聽完第二節課順利進 入到第三節課的學習中，也有 20% 的幾率因課程内容枯燥或難度較大而休息或者退出。學生在 學習第三節課内容後，有 60% 的幾率通過考試繼而 100% 的進入休息狀态，也有 40% 的幾率因 為過于興奮而出去娛樂泡吧，随後可能因為忘掉了不少學到的東西而分别以 20%,40% 和 50% 的 機率需要重新傳回第一、二、三節課中學習。
上圖中，我們使用内有文字的空心圓圈來描述學生可能所處的某一個狀态。這些狀态有：第 一節課（C1）、第二節課（C2）、第三節課（C3）、泡吧中（Pub）、通過考試（Pass）、浏覽手機 （FB）、以及休息退出（Sleep）共 7 個狀态，其中最後一個狀态是終止狀态，意味着學生一旦進 入該狀态則永久保持在該狀态，或者說該狀态的下一個狀态将 100% 還是該狀态。連接配接狀态的箭頭表示狀态轉移過程，箭頭附近的數字表明着發生箭頭所示方向狀态轉移的機率。
從符合馬爾科夫過程給定的狀态轉移機率矩陣生成一個狀态序列的過程稱為采樣（sample）。 采樣将得到一系列的狀态轉換過程，本書我們稱為狀态序列 (episode)。當狀态序列的最後一個狀态是終止狀态時，該狀态序列稱為完整的狀态序列 (complete episode)。本文中所指的狀态序列大多數指的都是完整的狀态序列。sample 對應着從 圖2.1 到 4個狀态序列 的過程。
馬爾科夫過程隻涉及到狀态之間的轉移機率，并未觸及強化學習問題中伴随着狀态轉換的獎勵回報。如果把獎勵考慮進馬爾科夫過程，則成為馬爾科夫獎勵過程（Markov reward process, MRP）。它是由 \(⟨S,P,R,γ⟩\) 構成的一個元組，其中：
\(S\) 是一個有限狀态集 \(P\) 是集合中狀态轉移機率矩陣：\(P_{ss'=P\left[ S_{t+1}=s'|S_t=s \right]}\) R 是一個獎勵函數：$R_s=E\left[ R_{t+1}|S_t=s \right] $ γ 是一個衰減因子：$γ ∈ [0,1] $
圖 2.2 在圖 2.1 的基礎上在每一個狀态旁增加了一個獎勵值，表明到達該狀态後（或離開該狀态時）學生可以獲得的獎勵，如此構成了一個學生馬爾科夫獎勵過程。
學生到達每一個狀态能獲得多少獎勵不是學生自己能決定的，而是由充當環境的授課老師或教務部門來确定，從強化學習的角度來說，獎勵值由環境動力學确定。
在該學生馬爾科夫獎勵 過程中，授課老師的主要目的是希望學生能夠盡早的通過考試，因而給了“考試通過”這個狀态 以正的較高的獎勵（+10），而對于過程中的其它狀态多數給的是負獎勵。雖然設定狀态“泡吧 中”的獎勵為 +1，但由于狀态“泡吧中”随後的三個可能狀态獲得的獎勵都低于 −1，因而可以認為授課教師并不十分贊在完成“第三節課”後出去泡吧。從學生的角度來說，學生的目标是在學習一門課程的過程中獲得盡可能多的累積獎勵，對于這個例子來說，也就是盡早的到達“考試 通過”這個狀态進而進入“睡覺休息”這個終止狀态，完成一個完整的狀态序列。在強化學習中， 我們給這個累計獎勵一個新的名稱“收獲”。
收獲（return）是一個馬爾科夫獎勵過程中從某一個狀态\(S_t\) 開始采樣直到終止狀态時所有獎勵的有衰減的之和。數學表達式如下：
\[G_t=R_{t+1}+\gamma R_{t+2}+...=\sum_{k=0}^{\infty}{\gamma ^kR_{t+k+1}}\ \ \ \ \ \ \ \ \left( 2.3 \right)
收獲有時也被翻譯為回報。從式 (2.3) 中可以看出，收獲是對應于狀态序列中的某一時刻的狀态，并計算從該狀态開始直至結束還能獲得的累積獎勵。在一個狀态序列中，不同時刻的狀态一般對應着不同的收獲。從該式中我們還可以看出，收獲并不是後續狀态的獎勵的直接相加，而 是引入了一個取值範圍在 \([0,1]\) 間的衰減系數 γ。引入該系數使得後續某一狀态對目前狀态收獲的貢獻要小于其獎勵。這樣設計從數學上可以避免在計算收獲時因陷入循環而無法求解，從現實 考慮也反映了遠期獎勵對于目前狀态具有一定的不确定性，需要折扣計算。當 γ 取 0 時，表明 某狀态下的收獲就是目前狀态獲得的獎勵，不考慮後續狀态，這屬于“短視”行為，當 γ 取 1 時， 表明将考慮所有的後續狀态，屬于有“長遠眼光”的行為。求解實際問題時，模型建構者可根據 實際問題的特點來設定 γ 值。這個式子需要注意的是，它是從\(R_{t+1}\)開始，可以了解為，從狀态 \(t\) 出發後，環境會給它完成這個狀态相應的獎勵即\(R_{t+1}\)。
下文給出了學生馬爾科夫過程中四個狀态序列的開始狀态“第一節課”的收獲值的計算，選 取 S1 =“第一節課”，γ = 0.5。
可以認為，收獲間接給狀态序列中的每一個狀态設定了一個資料标簽，反映了某狀态的重要 程度。由于收獲的計算是基于一個狀态序列的，從某狀态開始，根據狀态轉移機率矩陣的定義， 可能會采樣生成多個不同的狀态序列，而依據不同的狀态序列得到的同一個狀态的收獲值一般不會相同。如何評價從不同狀态序列計算得到的某個狀态的收獲呢？此外，一個狀态還可能存在 于一個狀态序列的多個位置，可以參考學生馬爾科夫過程的第四個狀态序列中的狀态“第一節 課”，此時在一個狀态序列下同一個狀态可能會有不同的收獲，如何了解這些不同收獲的意義呢？ 不難看出收獲對于描述一個狀态的重要性還存在許多不友善的地方，為了準确描述一個狀态的 重要性，我們引入狀态的“價值”這個概念。
價值（value） 是馬爾科夫獎勵過程中狀态收獲的期望。ta 數學表達式為：
\[v\left( s \right) =E\left[ G_t|S_t=s \right] \ \ \ \ \ \ \ \left( 2.4 \right)
從式 (2.4) 可以看出，一個狀态的價值是該狀态的收獲的期望，也就是說從該狀态開始依據 狀态轉移機率矩陣采樣生成一系列的狀态序列，對每一個狀态序列計算該狀态的收獲，然後對該 狀态的所有收獲計算平均值得到一個平均收獲。當采樣生成的狀态序列越多，計算得到的平均收獲就越接近該狀态的價值，因而價值可以準确地反映某一狀态的重要程度。
如果存在一個函數，給定一個狀态能得到該狀态對應的價值，那麼該函數就被稱為價值函數 （value function）。價值函數建立了從狀态到價值的映射。
從狀态的價值的定義可以看出，得到每一個狀态的價值，進而得到狀态的價值函數對于求解強化學習問題是非常重要的。但通過計算收獲的平均值來求解狀态的價值不是一個可取的辦法， 因為一個馬爾科夫過程針對一個狀态可能可以産生無窮多個不同的狀态序列。
我們對價值函數中的收獲按照其定義進行展開：
\[v\left( s \right) =E\left[ G_t|S_t=s \right]
\[\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =E\left[ R_{t+1}+\gamma R_{t+2}+\gamma ^2R_{t+3}+...|S_t=s \right]
\[\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =E\left[ R_{t+1}+\gamma \left( R_{t+2}+\gamma R_{t+3}+... \right) |S_t=s \right]
\[\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =E\left[ R_{t+1}+\gamma G_{t+1}|S_t=s \right]
\[\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =R_{t+1}+E\left[ \gamma G_{t+1}|S_t=s \right]
\[\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =R_{t+1}+E\left[ \gamma E\left[ G_{t+1} \right] |S_t=s \right] \ \ \ \ \ \text{期望的性質：}E\left[ E\left[ x \right] \right] =E\left[ x \right]
\[\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =R_{t+1}+E\left[ \gamma v\left( S_{t+1} \right) |S_t=s \right] \ \ \ \ \text{根據}\left( 2.4 \right) \text{式}
\[\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =E\left[ R_{t+1}+\gamma v\left( S_{t+1} \right) |S_t=s \right]
最終得到：
\[v\left( s \right) =E\left[ R_{t+1}+\gamma v\left( S_{t+1} \right) |S_t=s \right]\ \ \ \ \ \ \ \ \ \ \ \ \ (2.5)
上式中，根據馬爾科夫獎勵過程的定義，\(S_{t+1}\)的期望就是其自身，因為每次離開同一個狀态得到的獎勵都是一個固定的值。而下一時刻狀态價值的期望，可以根據下一時刻狀态的機率分布得到。如果用 \(s′\) 表示 \(s\) 狀态下一時刻任一可能的狀态：
那麼上述方程可以寫成：
\[v\left( s \right) =R_s+\gamma \sum_{s’\epsilon S}^{}{P_{ss’}v\left( s’ \right)}\ \ \ \ \ \left( 2.6 \right)
上式稱為馬爾科夫獎勵過程中的貝爾曼方程（Bellman equation），它提示一個狀态的價值 由該狀态的獎勵以及後續狀态價值按機率分布求和按一定的衰減比例聯合組成。 其中，\(R_{s}\)與（2.5）式中 \(R_{t+1}\)一緻，而 \(\sum_{s’\epsilon S}^{}{P_{ss’}v\left( s’ \right)}\) 與 \(E\left[ v\left( S_{t+1} \right) \right]\) 一緻，即是對期望公式的展開。
圖 2.3 根據獎勵值和衰減系數的設定給出了學生馬爾科夫獎勵過程中各狀态的價值，并對狀 态“第三節課”的價值進行了驗證演算。讀者可以根據上述方程對其它狀态的價值進行驗證。
上述 Bellman 方程可以寫成如下矩陣的形式：
\[v=R+\gamma Pv\ \ \ \ \ \ \left( 2.7 \right)
它表示：
\[\left[ \begin{array}{c}
v\left( 1 \right)\\
.\\
v\left( n \right)\\
\end{array} \right] =\left[ \begin{array}{c}
R_1\\
R_n\\
\end{array} \right] +\gamma \left[ \begin{matrix}
P_{11}& .& .& P_{1n}\\
.& & & .\\
P_{n1}& .& .& P_{nn}\\
\end{matrix} \right] \left[ \begin{array}{c}
\end{array} \right] \ \ \ \ \ \ \ \ \ \left( 2.8 \right)
理論上，該方程可以直接求解：
\[v=R+\gamma Pv
\[\left( 1-\gamma P \right) v=R
\[v=\left( 1-\gamma P \right) ^{-1}R
計算這類問題的時間複雜度是 O(n3)，其中 n 是狀态的數量。這意味着，對于學生馬爾科夫 獎勵過程這類狀态數比較少的小規模問題，直接求解是可行的，但如果問題涉及到的狀态數量增 多，這種解法就不現實了。本書的後續章節會陸續介紹其它行之有效的求解方法。
在強化學習問題中，如果個體知道了每一個狀态的價值，就可以通過比較後續狀态價值的大 小而得到自身努力的方向是那些擁有較高價值的狀态，這樣一步步朝着擁有最高價值的狀态進 行轉換。但是從第一章的内容我們知道，個體需要采取一定的行為才能實作狀态的轉換，而狀态 轉換又與環境動力學有關。很多時候個體期望自己的行為能夠到達下一個價值較高的狀态，但是 它并不一定能順利實作。這個時候個體更需要考慮在某一個狀态下采取從所有可能的行為方案 中選擇哪個行為更有價值。要解釋這個問題，需要引入馬爾科夫決策過程、行為、政策等概念。
馬爾科夫獎勵過程并不能直接用來指導解決強化學習問題，因為它不涉及到個體行為的選 擇，是以有必要引入馬爾科夫決策過程。馬爾科夫決策過程（Markov decision process, MDP）是 由 \(⟨S,A,P,R,γ⟩\) 構成的一個元組，其中：
\(S\) 是一個有限狀态集 \(A\) 是一個有限行為集 \(P\) 是集合中基于行為的狀态轉移機率矩陣：$P_{ss’}^{a}=P\left[ S_{t+1}=s’|S_t=s,A_t=a \right] $ R 是基于狀态和行為的獎勵函數：$R_{s}^{a}=E\left[ R_{t+1}|S_t=s,A_t=a \right] $ \(γ\) 是一個衰減因子：$γ ∈ [0,1] $
圖 2.4 給出了學生馬爾科夫決策過程的狀态轉化圖。圖中依然用空心圓圈表示狀态，增加一 類黑色實心圓圈表示個體的行為。根據馬爾科夫決策過程的定義，獎勵和狀态轉移機率均與行為 直接相關，同一個狀态下采取不同的行為得到的獎勵是不一樣的。此圖還把 Pass 和 Sleep 狀态 合并成一個終止狀态；另外當個體在狀态“第三節課”後選擇”泡吧”這個動作時，将被環境按照動力學特征配置設定到另外三個狀态。請注意，學生馬爾科夫決策過程示例雖然與之前的學生馬爾 科夫獎勵過程示例有許多相同的狀态，但兩者還是有很大的差别，建議讀者将這兩個示例完全區 分開來了解。
馬爾科夫決策過程由于引入了行為，使得狀态轉移矩陣和獎勵函數與之前的馬爾科夫獎勵 過程有明顯的差别。在馬爾科夫決策過程中，個體有根據自身對目前狀态的認識從行為集中選擇 一個行為的權利，而個體在選擇某一個行為後其後續狀态則由環境的動力學決定。
個體在給定狀态下從行為集中選擇一個行為的依據則稱為政策 (policy)，用字母 \(π\) 表示。政策 \(π\) 是某一狀态下基于行為集合的一個機率分布：
\[\pi \left( a|s \right) =P\left[ A_t=a|S_t=s \right] \ \ \ \ \ \left( 2.9 \right)
在馬爾科夫決策過程中，政策僅通過依靠目前狀态就可以産生一個個體的行為，可以說政策僅與目前狀态相關，而與曆史狀态無關。對于不同的狀态，個體依據同一個政策也可能産生不同 的行為；對于同一個狀态，個體依據相同的政策也可能産生不同的行為。政策描述的是個體的行為産生的機制，是不随狀态變化而變化的，被認為是靜态的。
随機政策是一個很常用的政策，當個體使用随機政策時，個體在某一狀态下選擇的行為并不 确定。借助随機政策，個體可以在同一狀态下嘗試不同的行為。
當給定一個馬爾科夫決策過程：\(M = ⟨S,A,P,R,γ⟩\) 和一個政策 \(π\)，那麼狀态序列 \(S_1,S_2,...\) 是一個符合馬爾科夫過程 \(⟨S,P_π⟩\) 的采樣。類似的，聯合狀态和獎勵的序列 $S_1,R_2,S_2,R_3,... $是一個符合馬爾科夫獎勵過程 \(⟨S,P_π,R_π,γ⟩\) 的采樣，并且在這個獎勵過程中滿足下面兩個方程：
\[P_{s,s'}^{\pi}=\sum_{a\in A}^{}{\pi \left( a|s \right) P_{ss'}^{a}}\ \ \ \ \ \ \ \ \ \
\[R_{s}^{\pi}=\sum_{a\in A}^{}{\pi \left( a|s \right) R_{s}^{a}}\ \ \ \ \ \left( 2.10 \right)
上述公式展現了馬爾科夫決策過程中一個政策對應了一個馬爾科夫過程和一個馬爾科夫獎 勵過程。不難了解，同一個馬爾科夫決策過程，不同的政策會産生不同的馬爾科夫（獎勵）過程， 進而會有不同的狀态價值函數。是以在馬爾科夫決策過程中，有必要擴充先前定義的價值函數。 [ 首先對于馬爾科夫決策過程，從一個狀态出發，然後標明某個行為，而後采取該行為後，環境會給你相應的獎勵，最後會到達某一狀态（狀态 —> 行為 —> 狀态 是可以多對多對多的）。譬如圖2.4中，我可以選擇泡吧或學習行為，當我選擇泡吧這個行為後，有相應的獎勵，同時也會進入不同的狀态。對于第一個式子，即是對采取不同行為并進入不同狀态的機率總和，是以等同于在計算馬爾科夫過程或獎勵的狀态轉移函數，這是因為在馬爾科夫過程或獎勵中，它們沒有行動的概念。對于第二個式子，即是采取不同行為可獲得不同獎勵的總和（期望）]
定義：價值函數 \(v_π(s)\) 是在馬爾科夫決策過程下基于政策 π 的狀态價值函數，表示從狀态 \(s\) 開始，遵循目前政策 \(π\) 時所獲得的收獲的期望：
\[v_{\pi}\left( s \right) =E\left[ G_t|S_t=s \right] \ \ \ \ \ \ \left( 2.11 \right)
同樣，由于引入了行為，為了描述同一狀态下采取不同行為的價值，我們定義一個基于政策 \(π\) 的行為價值函數 \(q_π(s,a)\)，表示在遵循政策 \(π\) 時，對目前狀态 \(s\) 執行某一具體行為 \(a\) 所能的到 的收獲的期望:
\[q_{\pi}\left( s,a \right) =E\left[ G_t|S_t=s,A_t=a \right] \ \ \ \ \ \ \left( 2.12 \right)
行為價值（函數）絕大多數都是與某一狀态相關的，是以準确的說應該是狀态行為對價值 (函數)。為了簡潔，統一使用行為價值（函數）來表示狀态行為對價值（函數），而狀态價值 （函數）或價值（函數）多用于表示單純基于狀态的價值（函數）。
定義了基于政策 \(π\) 的狀态價值函數和行為價值函數後，依據貝爾曼方程，我們可以得到如 下兩個貝爾曼期望方程：
\[v_{\pi}\left( s \right) =E\left[ R_{t+1}+\gamma v_{\pi}\left( S_{t+1} \right) |S_t=s \right] \ \ \ \ \ \ \ \left( 2.13 \right)
\[q_{\pi}\left( s,a \right) =E\left[ R_{t+1}+\gamma q_{\pi}\left( S_{t+1},A_{t+1} \right) |S_t=s,A_t=a \right] \ \ \ \ \ \ \ \ \left( 2.14 \right)
由于行為是連接配接馬爾科夫決策過程中狀态轉換的橋梁，一個行為的價值與狀态的價值關系 緊密。具體表現為一個狀态的價值可以用該狀态下所有行為價值來表達：
\[v_{\pi}\left( s \right) =\sum_{a\in A}^{}{\pi \left( a|s \right) q_{\pi}\left( s,a \right)}\ \ \ \ \ \left( 2.15 \right)
類似的，一個行為的價值可以用該行為所能到達的後續狀态的價值來表達：
\[q_{\pi}\left( s,a \right) =R_{s}^{a}+\gamma \sum_{s'\in S}^{}{P_{ss'}^{a}v_{\pi}\left( s' \right)}\ \ \ \ \ \ \ \left( 2.16 \right)
如果把上二式組合起來，可以得到下面的結果：
\[v_{\pi}\left( s \right) =\sum_{a\in A}^{}{\pi \left( a|s \right) \left( R_{s}^{a}+\gamma \sum_{s'\in S}^{}{P_{ss'}^{a}v_{\pi}\left( s' \right)} \right)}\,\,\,\,\,\,\,\,\,\,\left( 2.17 \right)
或：
\[q_{\pi}\left( s,a \right) =R_{s}^{a}+\gamma \sum_{s'\in S}^{}{P_{ss'}^{a}}\sum_{a\in A}^{}{\pi \left( a'|s' \right) q_{\pi}\left( s',a' \right)}\ \ \ \ \ \ \ \ \left( 2.18 \right)
圖 2.5 給出了一個給定政策下學生馬爾科夫決策過程的價值函數。每一個狀态下都有且僅有2 個實質可發生的行為，我們的政策是兩種行為以均等 (各 0.5) 的機率被選擇執行，同時衰減因 子 \(γ = 1\)。圖中狀态“第三節課”在該政策下的價值為 7.4，可以由公式 (2.17) 計算得出。
給定政策 \(π\) 下的 MDP 問題可以通過其衍生的 MRP 和 P 來求解。不同的政策可以得到不 同的價值函數，這些價值函數之間的差别有什麼意義？是否存在一個基于某一政策的價值函數， 在該政策下每一個狀态的價值都比其它政策下該狀态的價值高？如果存在如何找到這樣的價值 函數？這樣的價值函數對應的政策又是什麼政策？為了回答這些問題，我們需要引入最優政策、 最優價值函數等概念。
解決強化學習問題意味着要尋找一個最優的政策讓個體在與環境互動過程中獲得始終比其 它政策都要多的收獲，這個最優政策用 \(\pi ^*\) 表示。一旦找到這個最優政策 \(\pi ^*\)，那麼就意味着該強 化學習問題得到了解決。尋找最優政策是一件比較困難的事情，但是可以通過比較兩個不同政策 的優劣來确定一個較好的政策。
定義：最優狀态價值函數（optimal value function）是所有政策下産生的衆多狀态價值函數 中的最大者
\[v_*=\underset{\pi}{\max}v_{\pi}\left( s \right) \ \ \ \ \ \ \ \ \left( 2.19 \right)
定義：最優行為價值函數（optimal action-value function）是所有政策下産生的衆多行為價值函數中的最大者：
\[q_*\left( s,a \right) =\underset{\pi}{\max}q_{\pi}\left( s,a \right) \ \ \ \ \ \ \left( 2.20 \right)
定義：政策 \(π\) 優于 \(π′(π ⩾ π′)\)，如果對于有限狀态集裡的任意一個狀态 \(s\)，不等式：\(v_π(s) ⩾ v_{π′}(s)\) 成立。
存在如下的結論：對于任何馬爾科夫決策過程，存在一個最優政策 \(π_∗\) 優于或至少不差于所有其它政策。一個馬爾科夫決策過程可能存在不止一個最優政策，但最優政策下的狀态價值函數均等同于最優狀态價值函數：\(v_{π_∗}(s) = v_∗(s)\)；最優政策下的行為價值函數均等同于最優行為價值 函數：\(q_{π_∗}(s,a) = q_∗(s,a)\)。
最優政策可以通過最大化最優行為價值函數 \(q_∗(s,a)\) 來獲得：
該式表示，在最優行為價值函數已知時，在某一狀态 \(s\) 下，對于行為集裡的每一個行為 \(a\) 将 對應一個最優行為價值 \(q_∗(s,a)\)，最優政策 \(π_∗(a|s)\) 将給予所有最優行為價值中的最大值對應的行為以 100% 的機率，而其它行為被選擇的機率則為 0，也就是說最優政策在面對每一個狀态時将 總是選擇能夠帶來最大最優行為價值的行為。這同時意味着，一旦得到 \(q_∗(s,a)\)，最優政策也就找到了。是以求解強化學習問題就轉變為了求解最優行為價值函數問題。
拿學生馬爾科夫決策過程來說，圖 2.6 用粗虛箭頭指出了最優政策，同時也對應了某個狀态 下的最優行為價值。
在學生馬爾科夫決策過程例子中，各狀态以及相應行為對應的最優價值可以通過回溯法遞推計算得到。其中，狀态 \(s\) 的最優價值可以由下面的貝爾曼最優方程得到：
\[v_*\left( s \right) =\underset{a}{\max}q_*\left( s,a \right) \ \ \ \left( 2.22 \right)
公式 (2.22) 表示：一個狀态的最優價值是該狀态下所有行為對應的最優行為價值的最大值。 這不難了解，對于圖 2.6 學生示例中的狀态“第三節課”，可以選擇的行為有“學習”和“泡吧” 兩個，其對應的最優行為價值分别為 10 和 9.4，是以狀态“第三節課”的最優價值就是兩者中最 大的 10。
由于一個行為的獎勵和後續狀态并不由個體決定，而是由環境決定，是以在狀态 \(s\) 時選擇行為 \(a\) 的最優行為價值将不能使用最大化某一可能的後續狀态的價值來計算。它由下面的貝爾曼最優方程得到：
公式 (2.23) 表示：一個行為的最優價值由兩部分組成，一部分是執行該行為後環境給予的确定的即時獎勵，另一部分則由所有後續可能狀态的最優狀态價值按發生機率求和乘以衰減系 數得到（環境決定的）。
同樣在學生示例中，考慮學生在“第三節課”時選擇行為“泡吧”的最優行為價值時，先計入 學生采取該行為後得到的即時獎勵 +1，學生選擇了該行為後，并不确定下一個狀态是什麼，環 境根據一定的機率确定學生的後續狀态是“第一節課”、“第二節課”還是“第三節課”。此時要 計算“泡吧”的行為價值勢必不能取這三個狀态的最大值，而隻能取期望值了，也就是按照進入 各種可能狀态的機率來估計總的最優價值，具體表現為 6∗0.2 + 8∗0.4 + 10∗0.4 = 8.4，考慮到 衰減系數 \(γ = 1\) 以及即時獎勵為 +1，是以在第三節課後采取泡吧行為的最優行為價值 9.4。
可以看出，某狀态的最優價值等同于該狀态下所有的行為價值中最大者，某一行為的最優行 為價值可以由該行為可能進入的所有後續狀态的最優狀态價值來計算得到。如果把二者聯系起 來，那麼一個狀态的最優價值就可以通過其後續可能狀态的最優價值計算得到：
類似的，最優行為價值函數也可以由後續的最優行為價值函數來計算得到：
貝爾曼最優方程不是線性方程，無法直接求解，通常采用疊代法來求解，具體有價值疊代、 政策疊代、Q 學習、Sarsa 學習等多種疊代方法，後續幾章将陸續介紹。
https://zhuanlan.zhihu.com/reinforce
從平凡到超凡，隻有一萬個小時的距離！