[强化学习的数学原理—赵世钰老师]学习笔记02-贝尔曼方程

本人为强化学习小白，为了在后续科研的过程中能够较好的结合强化学习来做相关研究，特意买了西湖大学赵世钰老师撰写的《强化学习数学原理》中文版这本书，并结合赵老师的讲解视频来学习和更深刻的理解强化学习相关概念，知识和算法技术等。学习笔记是记录自己在看书和视频过程当中的一些自己的想法，通过基于书籍、视频和自己的话讲清楚相关理论知识和算法技术。希望能帮助到同样在学习强化学习的同学和同行等。

本文章为西湖大学赵世钰老师《强化学习数学原理》中文版第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\cdots$，计算对应折扣回报为
  $$\begin{array}{rl}{\mathrm{return}}_1& =0+\gamma 1+{\gamma }^{2}1+\cdots \\ & =\gamma (1+\gamma +{\gamma }^2+\cdots )\\ & =\frac{\gamma }{1-\gamma }\end{array}\text{\hspace{1em}(1)}$$
• 中间策略，轨迹为$s_1\to s_2\to s_4\to s_4\cdots$，计算对应折扣回报为
  $$\begin{array}{rl}{\mathrm{return}}_2& =-1+\gamma 1+{\gamma }^{2}1+\cdots \\ & =-1+\gamma (1+\gamma +{\gamma }^2+\cdots )\\ & =-1+\frac{\gamma }{1-\gamma }\end{array}\text{\hspace{1em}(2)}$$
• 右侧策略，得到两条轨迹，分别为$s_1\to s_2\to s_4\to s_4\cdots$ 和$s_1\to s_3\to s_4\to s_4\cdots$。两条轨迹各有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+\cdots \\ v_2& =r_2+\gamma r_3+{\gamma }^2{r}_4+{\gamma }^3{r}_1+\cdots \\ v_3& =r_3+\gamma r_4+{\gamma }^2{r}_1+{\gamma }^3{r}_2+\cdots \\ v_4& =r_4+\gamma r_1+{\gamma }^2{r}_2+{\gamma }^3{r}_3+\cdots \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+\cdots )=r_1+\gamma v_2\\ v_2& =r_2+\gamma (r_3+\gamma r_4+{\gamma }^2{r}_1+\cdots )=r_2+\gamma v_3\\ v_3& =r_3+\gamma (r_4+\gamma r_1+{\gamma }^2{r}_2+\cdots )=r_3+\gamma v_4\\ v_4& =r_4+\gamma (r_1+\gamma r_2+{\gamma }^2{r}_3+\cdots )=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\doteq 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)\doteq \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 基于动作值的贝尔曼方程