本人為強化學習小白，為了在后續科研的過程中能夠較好的結合強化學習來做相關研究，特意買了西湖大學趙世鈺老師撰寫的《強化學習數學原理》中文版這本書，并結合趙老師的講解視頻來學習和更深刻的理解強化學習相關概念，知識和算法技術等。學習筆記是記錄自己在看書和視頻過程當中的一些自己的想法，通過基于書籍、視頻和自己的話講清楚相關理論知識和算法技術。希望能幫助到同樣在學習強化學習的同學和同行等。

本文章為西湖大學趙世鈺老師《強化學習數學原理》中文版第2章 貝爾曼方程的學習筆記，在書中內容的基礎上增加了自己的一些理解內容和相關補充內容。

2.1 啟發示例1：為什么回報很重要？

核心概念： 狀態值，作為一個評價策略好壞的指標
核心工具： 貝爾曼方程，描述了所有狀態值之間的關系。
通過求解貝爾曼方程，得到狀態值，進而可以評價一個策略的好壞。

回顧： 回報可以評價一個策略的好壞。
通過如圖2.1所示三個在狀態$s_1$策略不同，其他狀態策略相同的例子來說明回報的重要性，并分析三個不同策略的好壞。

圖2.1 同一狀態不同策略的三個例子

直接觀察結果：

• 左側策略，從狀態$s_1$出發不會進入禁止區域，回報最大，策略最好。
• 中間策略，從狀態$s_1$出發一定會進入禁止區域，回報最小，策略最壞。
• 右側策略，從狀態$s_1$出發有0.5的概率進入禁止區域，回報一般，策略不好也不壞。

數學計算結果：

• 左側策略，軌跡為$s_1\to s_3\to s_4\to s_4?$，計算對應折扣回報為
  $$\begin{array}{rl}{\mathrm{return}}_1& =0+\gamma 1+{\gamma }^{2}1+?\\ & =\gamma (1+\gamma +{\gamma }^2+?)\\ & =\frac{\gamma }{1?\gamma }\end{array}\text{\hspace{1em}(1)}$$
• 中間策略，軌跡為$s_1\to s_2\to s_4\to s_4?$，計算對應折扣回報為
  $$\begin{array}{rl}{\mathrm{return}}_2& =?1+\gamma 1+{\gamma }^{2}1+?\\ & =?1+\gamma (1+\gamma +{\gamma }^2+?)\\ & =?1+\frac{\gamma }{1?\gamma }\end{array}\text{\hspace{1em}(2)}$$
• 右側策略，得到兩條軌跡，分別為$s_1\to s_2\to s_4\to s_4?$ 和$s_1\to s_3\to s_4\to s_4?$。兩條軌跡各有0.5概率發生，其對應的折扣回報分別為${\mathrm{return}}_1$和${\mathrm{return}}_2$，則平均回報計算為
  $$\begin{array}{rl}{\mathrm{return}}_3& =0.5(\frac{\gamma }{1?\gamma })+0.5(?1+\frac{\gamma }{1?\gamma })\\ & =?0.5+\frac{\gamma }{1?\gamma }\end{array}\text{\hspace{1em}(3)}$$
  結論：根據式（1），（2）和（3）的計算結果可知
  $$\begin{array}{r}{\mathrm{return}}_1>{\mathrm{return}}_3>{\mathrm{return}}_2\end{array}\text{\hspace{1em}(4)}$$
  數學計算折扣回報得到的結果和直接觀察得到的結果是一致的。

注：例子得出的結論：回報可以評價一個策略的好壞。但是需要注意的是，回報的定義針對的是一條軌跡，但是${\mathrm{return}}_3$為兩條軌跡折扣回報的平均值，這其實就是后續要介紹的狀態值。

2.2 啟發示例2：如何計算回報？

• 定義法：回報定義為沿軌跡收集的所有獎勵的折扣總和。如圖2.2所示，忽略禁止區域和目標區域，給出一個簡單的例子來計算回報。
  

圖2.2 如何計算回報示例

定義$v_i$為從狀態$s_i$出發得到的回報，$i=1,2,3,4$，則對應狀態出發得到的折扣回報為
$$\begin{array}{rl}{v}_1& =r_1+\gamma r_2+{\gamma }^2{r}_3+{\gamma }^3{r}_4+?\\ v_2& =r_2+\gamma r_3+{\gamma }^2{r}_4+{\gamma }^3{r}_1+?\\ v_3& =r_3+\gamma r_4+{\gamma }^2{r}_1+{\gamma }^3{r}_2+?\\ v_4& =r_4+\gamma r_1+{\gamma }^2{r}_2+{\gamma }^3{r}_3+?\end{array}\text{\hspace{1em}(5)}$$

• 自舉法（bootstrapping）：觀察式（5）中針對每個狀態出發獲得回報的計算結果，可以改寫為
  $$\begin{array}{rl}{v}_1& =r_1+\gamma (r_2+\gamma r_3+{\gamma }^2{r}_4+?)=r_1+\gamma v_2\\ v_2& =r_2+\gamma (r_3+\gamma r_4+{\gamma }^2{r}_1+?)=r_2+\gamma v_3\\ v_3& =r_3+\gamma (r_4+\gamma r_1+{\gamma }^2{r}_2+?)=r_3+\gamma v_4\\ v_4& =r_4+\gamma (r_1+\gamma r_2+{\gamma }^2{r}_3+?)=r_4+\gamma v_1\end{array}\text{\hspace{1em}(6)}$$式（6）的矩陣-向量形式的線性方程為
  $$\begin{array}{r}\underset{v\in {\mathbb{R}}^4}{\underbrace{\left[\begin{array}{c}{v}_1\\ v_2\\ v_3\\ v_4\end{array}\right]}}=\left[\begin{array}{c}{r}_1\\ r_2\\ r_3\\ r_4\end{array}\right]+\left[\begin{array}{c}\gamma v_2\\ \gamma v_3\\ \gamma v_4\\ \gamma v_5\end{array}\right]=\underset{r\in {\mathbb{R}}^4}{\underbrace{\left[\begin{array}{c}{r}_1\\ r_2\\ r_3\\ r_4\end{array}\right]}}+\underset{P\in {\mathbb{R}}^{4\times 4}}{\underbrace{\left[\begin{array}{cccc}0& 1& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& 1\\ 1& 0& 0& 0\end{array}\right]}}\underset{v\in {\mathbb{R}}^4}{\underbrace{\left[\begin{array}{c}{v}_1\\ v_2\\ v_3\\ v_4\end{array}\right]}}\end{array}\text{\hspace{1em}(7)}$$式（7）的簡化形式為
  $$v=r+Pv$$總結：由式（5）可知，從不同狀態出發的回報值式彼此依賴的，即，$v_1$依賴于$v_2$，$v_2$依賴于$v_3$，$v_3$依賴于$v_4$，$v_4$又依賴于$v_1$。這也反映了自舉的思想，即，$v_1$，$v_2$，$v_3$，$v_4$，可以從其自身$v_2$，$v_3$，$v_4$，$v_1$得到。
  從數學的角度，由式（6）給出的矩陣-向量形式的線性方程為可以很好的理解自舉。同時通過線性代數的知識可以很容易得到方程的解為
  $$v=(I?\gamma P{)}^{?1}r$$這里，$I\in {\mathbb{R}}^{4\times 4}$為單位矩陣，且$(I?\gamma P)$一定是可逆的，這在后續的學習中將會被證明。、

注：方程（6）即為圖2所示例子對應的貝爾曼方程，方程（7）即為這個貝爾曼方程的矩陣-向量形式。
貝爾曼方程的核心思想：從一個狀態出發獲得的回報依賴于從其他狀態出發時獲得的回報。

2.3 狀態值

注：嚴格定義下，回報只能用來評價一個確定策略的好壞，對于一般化的隨機情況（從一個狀態出發得到不同策略和回報的可能性），用回報來評價這種策略的好壞是不適用的。這時候就要引入狀態值的概念。

首先給出一個一般化的過程，即，在任意時刻（$t=0,1,2,\dots$）智能體處于任意狀態$S_t$按照某一策略$\pi$執行動作$A_t$，并下一時刻轉移到狀態$S_{t+1}$且獲得即時獎勵$R_{t+1}$的過程
$$S_t{\to }^{A_t}{S}_{t+1},R_{t+1}\text{\hspace{1em}(8)}$$其中，$S_t,S_{t+1}\in \mathcal{S}$，$A_t\in \mathcal{A}({\mathcal{S}}_t)$，$R_{t+1}\in \mathcal{R}(S_t,A_t)$。

注：$S_t$，$S_{t+1}$，$A_t$和$R_{t+1}$都為隨機變量（random variables）。

由式（8）可以得到從$t$時刻開始的一條包含一系列“狀態-動作-獎勵”的軌跡
$$S_t{\to }^{A_t}{S}_{t+1},R_{t+1}{\to }^{A_{t+1}}{S}_{t+2},R_{t+2}{\to }^{A_{t+2}}{S}_{t+3},R_{t+3},\dots$$
沿著軌跡計算得到的折扣回報為
$$G_t?R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+\dots ,\gamma \in (0,1)$$

$G_t$由$R_{t+1}$,$R_{t+2}$,$\dots$這些隨機變量的組合得到，同樣也為隨機變量。

計算隨機變量$G_t$的數學期望（expectation/expected value）為
$$v_{\pi }(s)?\mathbb{E}[G_t|S_t=s]$$
這里$v_{\pi }(s)$被定義為狀態值函數（state-value function），又簡稱為狀態值或狀態價值（state value）。

注：關于狀態值的說明。

• 狀態值$v_{\pi }(s)$的值依賴于狀態$s$，不同狀態下的狀態值一般是不同的。狀態值的本質是求隨機變量$G_t$在條件$S_t=s$下的條件期望。
• 狀態值$v_{\pi }(s)$的值依賴于策略$\pi$，不同策略下的狀態值一般是不同的。不同的策略會產生不同的軌跡，進而影響狀態值。
• 狀態值$v_{\pi }(s)$的值不依賴于時間$t$。所考慮的系統模型是平穩的，不會隨時間變化。

“狀態值”和“回報”的關系如圖2.3所示

圖2.3 “狀態值”和“回報”關系圖

總結：狀態值所描述的情況比回報描述的情況更一般化，可以處理不確定性和隨機性的情況。

狀態值可以更一般化的來評價策略，能產生更高狀態值的策略更好。

2.4 貝爾曼方程

貝爾曼方程（Bellman equation）描述了所有狀態值之間的關系。

貝爾曼方程的推導過程如下：

1. 改寫$G_t$。
   $$\begin{array}{rl}{G}_t& =R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+\dots \\ & =R_{t+1}+\gamma (R_{t+2}+\gamma R_{t+3}+\dots )\\ & =R_{t+1}+\gamma G_{t+1}\end{array}$$
2. 基于步驟1中建立的$G_t$和$G_{t+1}$之間的關系，狀態值$v_{\pi }(s)$可以改寫為
   $$\begin{array}{rl}{v}_{\pi }(s)& =\mathbb{E}[G_t|S_t=s]\\ & =\mathbb{E}[R_{t+1}+\gamma G_{t+1}|S_t=s]\\ & =\mathbb{E}[R_{t+1}|S_t=s]+\mathbb{E}[\gamma G_{t+1}|S_t=s]\end{array}\text{\hspace{1em}(9)}$$
3. 分析式（9）中的兩個數學期望項

• 即時獎勵期望值$\mathbb{E}[R_{t+1}|S_t=s]$

這一項可以通過全期望（total expectation） 的性質來進行改寫，首先給出改寫結果，然后給出具體的推導過程
$$\begin{array}{rl}\mathbb{E}[R_{t+1}|S_t=s]& =\sum _{a\in \mathcal{A}}\pi (a|s)\mathbb{E}[R_{t+1}|S_t=s,A_t=a]\\ & =\sum _{a\in \mathcal{A}}\pi (a|s)\sum _{r\in \mathcal{R}}p(r|s,a)r\end{array}\text{\hspace{1em}(10)}$$

式（10）的推導過程如下：

首先基于鏈式規則（chain rule） 和條件概率公式可以得到
$$\begin{array}{rl}p(a,b)& =p(a|b)p(b)\\ p(a,b,c)& =p(a|b,c)p(b,c)\\ & =p(a|b,c)p(b|c)p(c)\end{array}$$
由于$p(a,b,c)=p(a,b|c)p(c)$，所以$$p(a,b,c)/p(c)=p(a,b|c)=p(a|b,c)p(b|c)$$
然后可以進一步推導出以下關系
$$p(x|a)=\sum _{b}p(x,b|a)=\sum _{b}p(x|b,a)p(b|a)$$
其次給出期望（expectation） 和條件期望（conditional expectation） 的定義，并基于此推導出全期望公式（formula of total expectation）。
（1）期望（expectation）：隨機變量$X$取值$x$的概率為$p(x)$，$X$的期望值定義為$$\mathbb{E}[X]=\sum _{x}xp(x)$$
（2）條件期望（conditional expectation）：
$$\mathbb{E}[X|A=a]=\sum _{x}xp(x|a)$$
（3）全期望公式（formula of total expectation）：
$$\mathbb{E}[X]=\sum _a\mathbb{E}[X|A=a]p(a)$$
全期望公式的證明如下：$$\begin{array}{rl}\sum _a\mathbb{E}[X|A=a]p(a)& =\sum _a\sum _{x}xp(x|a)p(a)\to 由條件期望定義得到\\ & =\sum _x[\sum _{a}p(x|a)p(a)]x\\ & =\sum _{x}p(x)x\to 由全概率公式定義得到\\ & =\mathbb{E}[X]\to 由期望值定義得到\end{array}$$
然后，給出條件期望的另一種數學表示形式
$$\mathbb{E}[X|A=a]=\sum _b\mathbb{E}[X|A=a,B=b]p(b|a)$$
證明如下：$$\begin{array}{rl}\sum _b\mathbb{E}[X|A=a,B=b]p(b|a)& =\sum _b[\sum _{x}xp(x|a,b)]p(b|a)\to 由條件期望定義得到\\ & =\sum _b\sum _x[p(x|a,b)p(b|a)x\\ & =\sum _x[\sum _{b}p(x|a,b)p(b|a)]x\\ & =\sum _x\sum _{b}p(x,b|a)x\to 由鏈式規則的推廣得到\\ & =\sum _{x}p(x|a)x\\ & =\mathbb{E}[X|A=a]\to 由期望值定義得到\end{array}$$
因此，利用上述等式，我們可以得到即時獎勵期望值$\mathbb{E}[R_{t+1}|S_t=s]$的改寫結果式（10），即$$\begin{array}{rl}\mathbb{E}[R_{t+1}|S_t=s]& =\sum _{a\in \mathcal{A}}\pi (a|s)\mathbb{E}[R_{t+1}|S_t=s,A_t=a]\\ & =\sum _{a\in \mathcal{A}}\pi (a|s)\sum _{r\in \mathcal{R}}p(r|s,a)r\end{array}$$推導結束。

• 未來獎勵期望值$\mathbb{E}[G_{t+1}|S_t=s]$

這一項可以基于馬爾可夫性質改寫為如下形式
$$\begin{array}{rl}\mathbb{E}[G_{t+1}|S_t=s]& =\sum _{s^{\prime }\in \mathcal{S}}\mathbb{E}[G_{t+1}|S_t=s,S_{t+1}=s^{\prime }|p(s^{\prime }|s)]\\ & =\sum _{s^{\prime }\in \mathcal{S}}\mathbb{E}[G_{t+1}|S_{t+1}=s^{\prime }|p(s^{\prime }|s)]\to 由馬爾可夫性質得到\\ & =\sum _{s^{\prime }\in \mathcal{S}}{v}_{\pi }(s^{\prime })p(s^{\prime }|s)\\ & =\sum _{s^{\prime }\in \mathcal{S}}{v}_{\pi }(s^{\prime })\sum _{a\in \mathcal{A}}p(s^{\prime }|s,a)\pi (a|s)\to 由鏈式規則的推廣得到\end{array}\text{\hspace{1em}(11)}$$

馬爾可夫性質：$\mathbb{E}[G_{t+1}|S_t=s,S_{t+1}=s^{\prime }]=\mathbb{E}[G_{t+1}|S_t=s]$，即未來的獎勵僅依賴于當前狀態，與先前的狀態無關，即無記憶性。

將式（10）和式（11）帶入式（9），即可得到貝爾曼方程
$$\begin{array}{rl}{v}_{\pi }(s)& =\mathbb{E}[R_{t+1}|S_t=s]+\gamma \mathbb{E}[G_{t+1}|S_t=s]\\ & =\sum _{a\in \mathcal{A}}\pi (a|s)\sum _{r\in \mathcal{R}}p(r|s,a)r+\gamma \sum _{s^{\prime }\in \mathcal{S}}{v}_{\pi }(s^{\prime })\sum _{a\in \mathcal{A}}p(s^{\prime }|s,a)\pi (a|s)\\ & =\sum _{a\in \mathcal{A}}\pi (a|s)[\sum _{r\in \mathcal{R}}p(r|s,a)r+\gamma \sum _{s^{\prime }\in \mathcal{S}}p(s^{\prime }|s,a)v_{\pi }(s^{\prime })],s\in \mathcal{S}\end{array}\text{\hspace{1em}(12)}$$

貝爾曼方程的解釋說明：

• $v_{\pi }(s)$和$v_{\pi }(s^{\prime })$都是需要計算的狀態值，是未知量。
• $\pi (a|s)$是一個給定的策略，是已知量。
• $p(r|s,a)$和$p(s^{\prime }|s,a)$代表系統模型，可以是已知的也可以是未知的。

貝爾曼方程的常見等價形式：

• 等價形式1的表達式如下所示
  $$v_{\pi }(s)=\sum _{a\in \mathcal{A}}\pi (a|s)\sum _{s^{\prime }\in \mathcal{S}}\sum _{r\in \mathcal{R}}p(s^{\prime },r|s,a)[r+\gamma v_{\pi }(s^{\prime })]$$

推導過程如下
首先給出兩個與狀態$s$，$s^{\prime }$，動作$a$和獎勵$r$有關的全概率公式 $$\begin{array}{rl}p(s^{\prime }|s,a)& =\sum _{r\in \mathcal{R}}p(s^{\prime },r|s,a)\\ p(r|,s,a)& =\sum _{s^{\prime }\in \mathcal{S}}p(s^{\prime },r|s,a)\end{array}$$將上述兩個全概率公式代入（12），可以得到$$\begin{array}{rl}{v}_{\pi }(s)& =\sum _{a\in \mathcal{A}}\pi (a|s)[\sum _{r\in \mathcal{R}}p(r|s,a)r+\sum _{s^{\prime }\in \mathcal{S}}p(s^{\prime }|s,a)v_{\pi }(s^{\prime })]\\ & =\sum _{a\in \mathcal{A}}\pi (a|s)[\sum _{s^{\prime }\in \mathcal{S}}\sum _{r\in \mathcal{R}}p(s^{\prime },r|s,a)r+\sum _{s^{\prime }\in \mathcal{S}}\sum _{r\in \mathcal{R}}p(s^{\prime },r|s,a)v_{\pi }(s^{\prime })]\\ & =\sum _{a\in \mathcal{A}}\pi (a|s)\sum _{s^{\prime }\in \mathcal{S}}\sum _{r\in \mathcal{R}}p(s^{\prime },r|s,a)[r+\gamma v_{\pi }(s^{\prime })]\end{array}$$推導結束。

• 等價形式2為貝爾曼期望方程（bellman expectation equation）：
  $$v_{\pi }(s)=\mathbb{E}[R_{t+1}+\gamma v_{\pi }(S_{t+1})|S_t=s],s\in \mathcal{S}$$

推導過程如下
由式（11）可知
$$\begin{array}{rl}\mathbb{E}[G_{t+1}|S_t=s]& =\sum _{s^{\prime }\in \mathcal{S}}{v}_{\pi }(s^{\prime })\sum _{a\in \mathcal{A}}p(s^{\prime }|s,a)\pi (a|s)\\ & =\mathbb{E}[v_{\pi }(S_{t+1})|S_t=s]\end{array}$$ 將上述等式帶入式（9）即可得到貝爾曼期望方程。

• 等價形式3的表達式如下所示
  $$v_{\pi }(s)=\sum _{a\in \mathcal{A}}\pi (a|s)\sum _{s^{\prime }\in \mathcal{S}}p(s^{\prime }|s,a)[r(s^{\prime })+\gamma v_{\pi }(s^{\prime })]$$

推導過程如下
在一些特殊問題中，獎勵$r$可能僅依賴于下一個狀態$s^{\prime }$，這時候獎勵可以表示為$r(s^{\prime })$。這時候以下等式成立
$$\begin{array}{rl}p(r(s^{\prime })|s,a)& =p(s^{\prime }|s,a)\\ \sum _{r\in \mathcal{R}}p(r|s,a)r& =\sum _{s^{\prime }\in \mathcal{S}}p(r(s^{\prime })|s,a)r(s^{\prime })\end{array}$$將上述等式帶入式（12）可得到等價形式3。

2.5 示例

2.6 矩陣-向量形式

2.7 求解狀態值

2.7.1 方法1：解析解

2.7.2 方法2：數值解

2.7.3 示例

2.8 動作值

2.8.1 示例

2.8.2 基于動作值的貝爾曼方程