强化学习的数学原理课程总览

贝尔曼公式（Bellman Equation）

• 一个核心的概念：状态值（state value）
• 一个基础工具：the Bellman equation

一个示例

**为什么return是重要的？**首先我们根据一个轨迹（trajectory）获得rewards的（discounted）sum。如下所示：

根据上图所示，有两个问题：

• 问题1：从s1点出发，哪种policy是“best”？，哪一个是“worst”？
  直观上看，第一个是最优的，第二个是最差的，这是因为第二个经过了forbidden area。

• 问题2：是否可以用数学公式描述这样一种直观感觉？
  可以，使用return来评估policies。

基于策略1（左边图），从s1开始，the discounted return计算如下：
$$retur{n}_1=0+\gamma 1+{\gamma }^{2}1+...=\gamma (1+\gamma +{\gamma }^2+...)=\frac{\gamma }{1-\gamma }$$
基于策略2（中间图），从s1开始，the discounted return是：
$$retur{n}_2=-1+\gamma 1+{\gamma }^{2}1+...=-1+\gamma (1+\gamma +{\gamma }^2+...)=-1+\frac{\gamma }{1-\gamma }$$
策略3是随机性的，基于第三个策略（右边图），从s1出发，discounted return是：
$$retur{n}_3=0.5(-1+\frac{\gamma }{1-\gamma })+0.5(\frac{\gamma }{1-\gamma })=-0.5+\frac{\gamma }{1-\gamma }$$

基于上面的计算可知，从s1出发，$retur{n}_1>retur{n}_3>retur{n}_2$。因此从结果上看，这是符合之前的直觉的。所以，通过计算return可以评估一个policy的优劣。

那么如何计算return？刚才是用return的定义，现在用一个更好的方法来计算它。以如下图为例：

• 方法1：由定义计算，令$v_i$表示从$s_i(i=1,2,3,4)$出发得到的return
  
• 方法2：先看下面式子
  
  从上面式子中可以得出结论：return依赖于其他状态，这个思想称为Boostrapping。

如何求解这些等式？我们可以将上面的公式写成一个矩阵向量的形式：

可以写为：
$$\mathrm{v}=\mathrm{r}+\gamma \mathrm{Pv}$$
这个公式就是一个贝尔曼公式（Bellman equation）（对于这样一个具体的确定性问题）：

• 尽管简单，但是它证明一个关键思想：一个状态的值依赖于其他状态的值
• 一个矩阵-向量形式可以更加清晰地知道如何求解状态值。

状态值

首先，定义几个概念。考虑这样一个单步（single-step）的过程：

其中:

• $t,t+1$：离散时间
• $S_t$：在时刻$t$的状态
• $A_t$：在状态$S_t$采取的动作
• $R_{t+1}$：采取动作$A_t$之后得到的奖励
• $S_{t+1}$：采取动作$A_t$之后转移到的状态

注意：$S_t,A_t,R_{t+1}$都是随机变量（random variables）。

根据下面的概率分布决定后续的步骤：

在某一时刻，我们假设我们知道这个模型，即概率分布。

将上面的单步过程推广到一个多步的trajectory上，可以得到：

则discounted return计算如下：
$$G_t=R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+......$$

• $\gamma \in [0,1)$是一个折扣率
• $G_t$是一个随机变量，因为$R_{t+1}，R_{t+2}，...$是随机变量。

定义state value: $G_t$被的期望（或者称为期望值或均值）被定义为state-value function或者简单地称为state value：
$$v_{\pi }(s)=\mathbb{E}[G_t|S_t=s]$$
注意：

• 它是一个关于s的函数。从不同的s出发，得到的期望也是不同的
• 它是基于策略$\pi$的，对于不同的策略，state value也可能不同
• 它表示一个状态的“价值”。如果state value比较大，那么这个策略比较好。

问题：return和state value之间有什么关联？
答：state value是从一个state出发得到的所有可能的return的平均值。如果所有——$\pi (a|s)，p(r|s,a),p(s^{\prime }|s,a)$——是确定行的，则state value与return是相同的。

示例：下面三个图分别对应三个策略：${\pi }_1,{\pi }_2,{\pi }_3$

计算从$s_1$开始得到的returns:

贝尔曼公式：推导过程

用一句话来说，贝尔曼公式用于描述所有不同状态值之间的关系。
考虑一个随机的trajectory：

return $G_t$可以被写为：

然后，根据state value的定义，用数学形式化：

这样就可到了两个部分。然后我们分别计算这两个部分：
首先，计算第一项$\mathbb{E}[R_{t+1}|S_t=s]$：
$$\mathbb{E}[R_{t+1}|S_t=s]=\sum _a\pi (a|s)\mathbb{E}[R_{t+1}|S_t=s,A_t=a]=\sum _a\pi (a|s)\sum _{r}p(r|s,a)r$$
注意：这是得到的一个immediate rewards的均值。
再看第二项$\mathbb{E}[G_{t+1}|S_t=s]$：

注意：

• 第二项是future reward的均值
• $\mathbb{E}[G_{t+1}|S_t=s,S_{t+1}=s^{\prime }]=\mathrm{E}[G_{t+1}|S_{t+1}=s^{\prime }]$是由于Markov的无记忆功能，即不需要计算状态s的值。

现在，我们有如下公式：

注意：

• 上面的公式成为Bellman equation， 其描述了不同状态的state-value functions之间的关系；
• 它包含两个部分：the immediate reward term 和the future reward term，即当前奖励和未来奖励
• 它是一个等式的集合：所有的state都有这样一个类似的等式。
• $v_{\pi }(s)$和$v_{\pi }(s^{\prime })$是需要被计算的state value，计算方法就是Bootstrapping。
• $\pi (a|s)$是一个给定的策略policy，求解这个等式就被称为策略评估（policy evaluation）
• $p(r|s,a)$和$p(s^{\prime }|s,a)$表示动态模型（dynamic model），分为两种情况，即知道和不知道

根据上面网格，再次将Bellman公式根据最终的一般形式写出来：
$$v_{\pi }(s)=\sum _a\pi (a|s)[\sum _{r}p(r|s,a)r+\gamma \sum _{s^{\prime }}p(s^{\prime }|s,a)v_{\pi }(s^{\prime })]$$
这里非常简单，因为策略是确定性的。
首先，考虑$s_1$的state value：

这时候将上述公式的结果提交到贝尔曼公式里边，得到：
$$v_{\pi }(s_1)=0+\gamma v_{\pi }(s_3)$$
类似地，我们有如下公式：
$$v_{\pi }(s_1)=0+\gamma v_{\pi }(s_3)$$$$v_{\pi }(s_2)=1+\gamma v_{\pi }(s_4)$$$$v_{\pi }(s_3)=1+\gamma v_{\pi }(s_4)$$$$v_{\pi }(s_4)=1+\gamma v_{\pi }(s_4)$$
求解上面等式，通过从最后一个到第一个，逐步求解，得到：
$$v_{\pi }(s_4)=\frac{1}{1-\gamma }$$$$v_{\pi }(s_3)=\frac{1}{1-\gamma }$$$$v_{\pi }(s_2)=\frac{1}{1-\gamma }$$$$v_{\pi }(s_1)=\frac{\gamma }{1-\gamma }$$
假设$\gamma =0.9$，带入上面等式中，得到：
$$v_{\pi }(s_4)=10$$$$v_{\pi }(s_3)=10$$$$v_{\pi }(s_2)=10$$$$v_{\pi }(s_1)=9$$
当我们计算完成state value之后呢？需要计算action value和改善policy。

练习如下示例：

给出一般化的贝尔曼公式：
$$v_{\pi }(s)=\sum _a\pi (a|s)[\sum _{r}p(r|s,a)r+\gamma \sum _{s^{\prime }}p(s^{\prime }|s,a)v_{\pi }(s^{\prime })]$$
现在，对于每个state，写出对应的贝尔曼等式，根据上面的贝尔曼公式求解state value，最后比较不同的policy。
对于第一个问题，每个状态的贝尔曼等式如下：

从后往前计算每个state value，有：

然后，将$\gamma =0.9$带入上面式子中，得到：

比较不同的策略，这个策略是比较差的，没有之前的策略好。

贝尔曼公式：矩阵-向量形式（Matrix-vector form）

首先考虑如何求解Bellman公式，

一种unknown依赖于另一种unknown。上面的elementwise form对于每个state $s\in S$都是适用的，这意味着将有$|S|$个类似的公式，如果将这些公式放在一块，将得到一个线性方程组，将它们写为matrix-vector form，这种矩阵-向量形式是优雅而重要（elegant and important）。

Bellman公式的Matrix-vector形式求解如下：

假设states可以索引为$s_i(i=1,...,n)$。对于状态$s_i$，Bellman公式是：

将所有states的这样等式放在一起，用矩阵向量的形式写为：
$$v_{\pi }=r_{\pi }+\gamma P_{\pi }{v}_{\pi }$$
其中：

示例如下，假设有4个状态，上面公式可以写为：

进一步地，以网格为例：

可以写为如下形式：

再看一个随机性的网格示例，如下：

有如下结果：

贝尔曼公式：求解状态值

为什么要求解state values？

• 给定一个策略policy，找到对应的state values的过程被称为policy evaluation。这是一个强化学习的基础问题，即找出更好的策略。
• 这对于理解如何求解Bellman公式很重要

如下是Bellman公式的matrix-vector form：$$v_{\pi }=r_{\pi }+\gamma P_{\pi }{v}_{\pi }$$
其解析表达式（closed-form solution）是$$v_{\pi }=(I-\gamma P_{\pi }{)}^{-1}{r}_{\pi }$$，实际上，我们仍然需要使用数值工具计算矩阵的逆。
因此，在实际中，我们使用迭代算法去求解（iterative solution）：$$v_{k+1}=r_{\pi }+\gamma P_{\pi }{v}_k$$，这样的算法将得到一个序列{v0,v1,v2,...}\{v_0,v_1,v_2,...\}{v0​,v1​,v2​,...}，如下：

当k趋近于无穷的时候，则$v_k$就趋近于$v_{\pi }$。证明如下：

示例：$r_{boundary}=r_{forbidden}=-1,r_{target}=+1,\gamma =0.9$，下面是两个”bad“策略和状态值。the state value不如好的policies。

动作值（Action value）

state value和action value的区别：

• State value： 智能体starting from a state得到的平均return
• Action value：智能体starting from a state并taking an action得到的平均return

通过action value，可以得到哪个action是更好的。

Action value的定义：$$q_{\pi }(s,a)=\mathbb{E}[G_t|S_t=s,A_t=a]$$，其中$q_{\pi }(s,a)$是state-action pair $(s,a)$的函数，$q_{\pi }(s,a)$依赖于$\pi$。
于是，基于条件期望的性质，可以有：

因此，可以将上面式子写为：
$$v_{\pi }(s)=\sum _a\pi (a|s)q_{\pi }(s,a)$$
回顾之前的state value公式：

可以得到action-value函数如下：

示例：

针对$s_1$写出action value：$$q_{\pi }(s_1,a_2)=-1+\gamma v_{\pi }(s_2)$$
除了采取a2动作之外，还可以采取a1, a3, a4动作，那么它们的action value是多少呢？

总的来说

• Action value是非常重要的，因为我们关注哪一种action会被采用；
• 我们可以首先计算所有的state value，然后计算action value；
• can also directly calculate the action values with or without models.

总结

关键概念：

• State value： $v_{\pi }(s)=\mathbb{E}[G_t|S_t=s]$

• Action value: $q_{\pi }(s,a)=\mathbb{E}[G_t|S_t=s,A_t=a]$

• 贝尔曼公式（elementwise form）：
  

• 贝尔曼公式（matrix-vector form）：$$v_{\pi }=r_{\pi }+\gamma P_{\pi }{v}_{\pi }$$

• 如何求解贝尔曼公式：解析法（closed-form solution），迭代法（iterative solution）

参考资料

[1] 《强化学习的数学原理》赵世钰教授 西湖大学工学院
[2] 《动手学强化学习》 俞勇著