当前位置：首页 > article >正文

强化学习数学原理(二)——贝尔曼公式

article 2025/1/30 13:21:30

一、Examples

1.1 为什么需要return？

三个情况在s1的情况是不同的，其他相同。从s1出发，哪种策略是最好的，哪个最差的，直观感受肯定知道，第一种最好。那么我们就用数学公式来表达，就是return，用return就知道哪个策略最好

对于策略1，我们可以得到：

$\begin{aligned}return_1&\begin{aligned}&=0+\gamma1+\gamma^{2}1+\ldots,\end{aligned}\\&=\gamma(1+\gamma+\gamma^2+\ldots),\\&=\frac{\gamma}{1-\gamma}.\end{aligned}$

对于策略2，我们可以得到：

$\begin{aligned}return_2&=-1+\gamma1+\gamma^{2}1+\ldots,\\&=-1+\gamma(1+\gamma+\gamma^2+\ldots),\\&=-1+\frac{\gamma}{1-\gamma}.\end{aligned}$

对于策略3，我们可以得到：

$\begin{aligned}return_3&=0.5\left(-1+\frac{\gamma}{1-\gamma}\right)+0.5\left(\frac{\gamma}{1-\gamma}\right),\\&=-0.5+\frac{\gamma}{1-\gamma}.\end{aligned}$

这个return3并不是传统的return，因为正常的return只有一个返回值，但是这个相当于是一个均值，所以这个就是 state value.上面的计算结果也反应了不同策略的好坏。

在上面的分析中，我们可以得到，一条路径的评估，其实是起始位置和其他路径评估之和，这种返回依赖于其他路径，称为 Boostrapping

$\underbrace{\begin{bmatrix}v_1\\v_2\\v_3\\v_4\end{bmatrix}}_{\mathbf{v}}=\begin{bmatrix}r_1\\r_2\\r_3\\r_4\end{bmatrix}+\begin{bmatrix}\gamma v_2\\\gamma v_3\\\gamma v_4\\\gamma v_1\end{bmatrix}=\underbrace{\begin{bmatrix}r_1\\r_2\\r_3\\r_4\end{bmatrix}}_{\mathbf{r}}+\underbrace{\gamma\begin{bmatrix}0&1&0&0\\0&0&1&0\\0&0&0&1\\1&0&0&0\end{bmatrix}}_{\mathbf{P}}\underbrace{\begin{bmatrix}v_1\\v_2\\v_3\\v_4\end{bmatrix}}_{\mathbf{v}}$

上面的式子也可以写作一个更简化的式子：

$\mathbf{v}=\mathbf{r}+\gamma\mathbf{P}\mathbf{v}$

这个公式就是简单的贝尔曼公式，一个状态的value，依赖其他状态。

二、State value 状态值贝尔曼方程

$S_t\xrightarrow{A_t}R_{t+1},S_{t+1}$

当前状态·St，采取At，得到下一个动作奖励 Rt+1，跳到下一个状态St+1.state value就是Gt的期望值。这个函数是一个关于s的函数，那么不同的出发点，得到的值不同。同时不同的策略，得到的也会不同。并且他所得到的return也不同。

有几个比较常见的例子，比如我在St的状态需要采取什么样的行动，就是由决策来决定的

$\pi(A_t=a|S_t=s)$

我在St，我要采取At的行动，得到怎么样的reward，这是由奖励概率来决定的

$p(R_{t+1}=r|S_t=s,A_t=a)$

我在St，我要采取At的行动，跳到一个什么样的状态，是由状态转移概率来决定的

$p(S_{t+1}=s^{\prime}|S_t=s,A_t=a)$

对于一个trajectory，我们可以求他的discounted return (第一章),求取他的价值为

$G_t=R_{t+1}+\gamma R_{t+2}+\gamma^2R_{t+3}+\ldots$

其中，衰减率为0~1之间，每一个Rt都是一个随机变量，得到的Gt自然也是随机变量。

有了上面的概念，我们就可以来定义State value，我们知道Gt是对一个策略的discounted return，State value就是Gt的期待值 expectation,也可以称作mean

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

用Vpi(s) 来替代state value，如上面的公式，它基于当前的一个状态s，这样的条件下来求Gt的expectation，他是关于s的一个函数，并且是一个策略的函数不同的策略，得到的轨迹和return自然也不相同。state value和return不同的地方是，他是多种策略求取到的一个均值，如果只有一种策略，那他和return就会是相同的。

三、贝尔曼公式

首先考虑一个trajectory

$S_t\xrightarrow{A_t}R_{t+1},S_{t+1}\xrightarrow{A_{t+1}}R_{t+2},S_{t+2}\xrightarrow{A_{t+2}}R_{t+3},\ldots$

其return就可以计算得到

$\begin{aligned}G_{t}&=R_{t+1}+\gamma R_{t+2}+\gamma^{2}R_{t+3}+\ldots,\\&=R_{t+1}+\gamma(R_{t+2}+\gamma R_{t+3}+\ldots)\\&=R_{t+1}+\gamma G_{t+1},\end{aligned}$

这个trajectory，我们可以得到返回值 Gt。第一个值，是采取行动后能立即获得当前行动的Reward，与下一时刻出发，得到的 trajectory 和 discount rate。那么我们就将他分为两个部分，一部分是immediate reward，和future reward。实际上这个符号可以分开，就得到了两个期待值。

$\begin{aligned}v_{\pi}(s)&\begin{aligned}=\mathbb{E}[G_t|S_t=s]\end{aligned}\\&=\mathbb{E}[R_{t+1}+\gamma G_{t+1}|S_t=s]\\&=\mathbb{E}[R_{t+1}|S_t=s]+\gamma\mathbb{E}[G_{t+1}|S_t=s]\end{aligned}$

这样的话我们就对两个分别进行计算，左边 $\mathbb{E}[R_{t+1}|S_t=s]$

首先我在状态s会有多个action可以采用，所以实际上应该是多个action进行求和，在s的情况下采取a的概率为pi，同时我们也可以根据当前s与采取a的情况计算Reward，其应该是在s情况下，采取a行动，获得奖励r的概率，再乘上r本身，且有多个a，所以我们得到的reward也会是对应多个的，得到

$\sum_a\pi(a|s)\sum_rp(r|s,a)r$

第二项，是从s出发，得到下一时刻的return的mean，个人感觉，这块可以理解为，当你从s出发后，除开上面算的立刻获得的值，在新的状态St+1，你还能得到的discount return

$\mathbb{E}[G_{t+1}|S_t=s]$

从当前S出发，到达下一状态S`，可以获得其概率，因为会有多个S`，所以也是需要进行求和

$\sum_{s^{\prime}}\mathbb{E}[G_{t+1}|S_t=s,S_{t+1}=s^{\prime}]p(s^{\prime}|s)$

从第一章的马尔可夫性质，或者单纯从理解上来说，既然我们已经跳到了s`的状态，那么当前状态s就是一个非必要条件了，既然我们已经知道下一步我会到达 b，且要计算在b地区后面获得的state value，那么就不需要知道到达b前的状态了。所以上面的式子可以改写成

$\sum\mathbb{E}[G_{t+1}|S_{t+1}=s^{\prime}]p(s^{\prime}|s)$

由State value公式的定义，我们又可以将左边那块进行改写，由公式我们就知道，其为在s`下获得的state value，那么将式子进一步优化为

$\sum_{s^{\prime}}v_\pi(s^{\prime})p(s^{\prime}|s)$

对于右边的部分，从s到s`的概率，就相当于在s状态下，采取行动a跳到s`，这里就包含了在s状态下采取行动a的概率pi，同时可以将式子的条件进行补充

$\sum_{s^{\prime}}v_\pi(s^{\prime})\sum_ap(s^{\prime}|s,a)\pi(a|s)$

现在对上面的式子进行整合，就可以得到贝尔曼公式的表达式

$\sum_a\pi(a|s)\left[\sum_rp(r|s,a)r+\gamma\sum_{s^{\prime}}p(s^{\prime}|s,a)v_\pi(s^{\prime})\right],\quad\forall s\in\mathcal{S}.$

贝尔曼公式描述了不同状态state value之间的关系，左侧是s的state value，右侧是s`的state value，在上面的公式里面，我们是有确定值的。

通过一个例子来说明

上面的图里有两个方向可以走，针对每一个状态的state value，我们就可以写出每个状态的state value

$\begin{aligned}&v_{\pi}(s_{1})=0.5[0+\gamma v_{\pi}(s_{3})]+0.5[-1+\gamma v_{\pi}(s_{2})]\\&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}).\end{aligned}$

这个式子可从第四个式子入手进行化简，先求出s4，之后代入其他式子中得到

$\begin{aligned}&v_{\pi}(s_{4})=\frac{1}{1-\gamma},\quad v_{\pi}(s_{3})=\frac{1}{1-\gamma},\quad v_{\pi}(s_{2})=\frac{1}{1-\gamma}\\&v_{\pi}(s_{1})=0.5[0+\gamma v_\pi(s_3)]+0.5[-1+\gamma v_\pi(s_2)],\\&=-0.5+\frac{\gamma}{1-\gamma}.\end{aligned}$

四、贝尔曼公式的向量与矩阵形式

$v_\pi(s)=\sum_a\pi(a|s)\left[\sum_rp(r|s,a)r+\gamma\sum_{s^{\prime}}p(s^{\prime}|s,a)v_\pi(s^{\prime})\right]$

当从上面的公式来说，因为未知量比较多，要求出来几乎是不可能的，但是这个式子对所有的s都成立，所有的公式放到一起，就可以得到 matrix-vector form

我们把上面的式子放一起，在对式子进行一个计算得到

$v_{\pi}(s)=r_{\pi}(s)+\gamma\sum_{s^{^{\prime}}}p_{\pi}(s^{\prime}|s)v_{\pi}(s^{\prime})$

其中 $r_\pi(s)\triangleq\sum_a\pi(a|s)\sum_rp(r|s,a)r,\quad p_\pi(s^{\prime}|s)\triangleq\sum_a\pi(a|s)p(s^{\prime}|s,a)$

我们把所有的状态都写在一起，左侧认为是在s状态下采取行动a获得的奖励，右侧是在衰减系数的情况下，从Si跳到下一状态Sj的概率乘上下一状态的state value

$v_\pi=r_\pi+\gamma P_\pi v_\pi$

Vpi是每个状态的state value所组合成的向量，rpi是每个状态获得的奖励，Ppi是一个状态转移概率矩阵

$\left.\left[\begin{array}{c}v_\pi(s_1)\\v_\pi(s_2)\\v_\pi(s_3)\\v_\pi(s_4)\end{array}\right.\right]=\underbrace{\begin{bmatrix}r_\pi(s_1)\\r_\pi(s_2)\\r_\pi(s_3)\\r_\pi(s_4)\end{bmatrix}}_{r_\pi}+\gamma\underbrace{\begin{bmatrix}p_\pi(s_1|s_1)&p_\pi(s_2|s_1)&p_\pi(s_3|s_1)&p_\pi(s_4|s_1)\\p_\pi(s_1|s_2)&p_\pi(s_2|s_2)&p_\pi(s_3|s_2)&p_\pi(s_4|s_2)\\p_\pi(s_1|s_3)&p_\pi(s_2|s_3)&p_\pi(s_3|s_3)&p_\pi(s_4|s_3)\\p_\pi(s_1|s_4)&p_\pi(s_2|s_4)&p_\pi(s_3|s_4)&p_\pi(s_4|s_4)\end{bmatrix}}_{P_\pi}\underbrace{\begin{bmatrix}v_\pi(s_1)\\v_\pi(s_2)\\v_\pi(s_3)\\v_\pi(s_4)\end{bmatrix}}_{v_\pi}.$

P就是从当前状态跳到另一个状态的概率，同样引入一个例子

$\begin{bmatrix}v_\pi(s_1)\\v_\pi(s_2)\\v_\pi(s_3)\\v_\pi(s_4)\end{bmatrix}=\begin{bmatrix}0.5(0)+0.5(-1)\\1\\1\\1\end{bmatrix}+\gamma\begin{bmatrix}0&0.5&0.5&0\\0&0&0&1\\0&0&0&1\\0&0&0&1\end{bmatrix}\begin{bmatrix}v_\pi(s_1)\\v_\pi(s_2)\\v_\pi(s_3)\\v_\pi(s_4)\end{bmatrix}$

给定一个policy,我们去计算他的state values,通过这个算出的值来对策略进行一个评价，实际过程中，我们比较常用迭代的方法来写

$v_{k+1}=r_\pi+\gamma P_\pi v_k$

通过这样的迭代方式，就可以得到v0 v1 v2一直到vk这样的一个序列

四、Action Value

从当前的状态s出发，采取行动a，所得到的mean，他是用来衡量本次行动的价值，state是衡量当前位置的价值

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

从数学公式上，我们可以看出，action比state value多采取了一个行动，我理解为，在状态s下每个行动概率获得价值的总和，就是state value

$\underbrace{\mathbb{E}[G_t|S_t=s]}_{v_\pi(s)}=\sum_a\underbrace{\mathbb{E}[G_t|S_t=s,A_t=a]}_{q_\pi(s,a)}\pi(a|s)$

因此 $v_\pi(s)=\sum_a\pi(a|s)q_\pi(s,a)$ ，结合上面的贝尔曼公式

$\sum_a\pi(a|s)\left[\sum_rp(r|s,a)r+\gamma\sum_{s^{\prime}}p(s^{\prime}|s,a)v_\pi(s^{\prime})\right]$

q(s,a)可以直接等同于后面那一大串，这个等式我们就可以知道，如果知道了所有状态的state value，就可以算出来每个状态的action value，a 和 s如果知道了其中一个的全部，就可以得到另一个了。同样的以一个例子入手

上面的例子告诉我们，s1的时候往右边走，所得到的action value为reward+yVpi(Si)，和上面的矩阵也很相似，就是采取行动后的reward，+行动后所处状态的state value

$q_\pi(s_1,a_2)=-1+\gamma v_\pi(s_2)$

五、改进策略

同样以一个例子代入

对每个状态代入贝尔曼公式可以得到

$\begin{gathered}v_{\pi}(s_{1})=-1+\gamma v_{\pi}(s_{2}),\\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}).\end{gathered}$

假设衰减系数为0.9，我们代入就可以求出每个状态的state value，举个例子 s4 = 1+0.9s4,得s4 = 10，代入s2 s3，得s2 = s3 = 10,代入s2，得到s1 = 8，有了所有得state value就可以求解action value，一共有5个action，上下左右原地，边界为-1，s2为-1，其余为0，那么可以得到

$\begin{gathered}q_\pi(s_1,a_1)=-1+\gamma v_{\pi}(s_{1})=6.2,\\q_\pi(s_1,a_2)=-1+\gamma v_\pi(s_2)=8,\\q_\pi(s_1,a_3)=0+\gamma v_\pi(s_3)=9,\\q_\pi(s_1,a_4)=-1+\gamma v_\pi(s_1)=6.2,\\q_\pi(s_1,a_5)=0+\gamma v_\pi(s_1)=7.2.\end{gathered}$

上面得action可以采取多种行动，但是我们就可以选择其中最好得一个，再上面得选择就可以选择a3得概率为1，而其他概率为0

$\left.\pi_{\mathsf{new}}(a|s_1)=\left\{\begin{array}{cc}1&a=a^*\\\\0&a\neq a^*\end{array}\right.\right.$

选择最好的action value，直观上你就可以得到最多的reward，通过一遍遍的迭代，一定可以得到最优的策略

六、最优公式

我们来定义这样两个策略，对于所有状态 pi1的state value都是大于pi2的，那么pi1就是比篇

好的

$v_{\pi_1}(s)\geq v_{\pi_2}(s)\quad\text{for all }s\in\mathcal{S}$

如果pi*在任意状态都比其余策略pi好，这就是最优策略，那么这个策略其实就是在贝尔曼公式的前提下选择最优的策略，对于所有s状态

$v(s)=\max_{\pi}\sum_{a}\pi(a|s)\left(\sum_{r}p(r|s,a)r+\gamma\sum_{s^{\prime}}p(s^{\prime}|s,a)v(s^{\prime})\right)$

这个时候pi就不再是给定的了，之前我们的pi，都是在给出的情况下，拥有了指定策略下的概率，奖励，现在求最优的情况我们就要进行迭代，进一步，我们将后面那一大串换成q

$\max_\pi\sum_a\pi(a|s)q(s,a)\quad s\in\mathcal{S}$

上面的式子，我们已知的是probability,行动的概率，行动的奖励，衰减系数，要求解的是v值，一个贝尔曼公式一定是依赖于一个给定的pi，但是上面说了，最优公式是没有给定的，那么我们就需要去求解这样一个pi，我们前面还有矩阵形式的公式

$v=\max_\pi(r_\pi+\gamma P_\pi v)$

说白了，他们的区别就是选择这样一个pi，在右侧都有一个最优问题，这里有一个式子，但是有 v 和 pi两个未知量要求，书上给出，我们就需要先给右侧的v一个初始值，这样q(s,a)他就是一个已知的，那么需要做的就是确定 pi(s,a)，实际上，每次行动都会有多个a，其实就是上面所提到的，把所有概率放到值最大的一个上面(缩放)

$\max_\pi\sum_a\pi(a|s)q(s,a)=\max_{a\in\mathcal{A}(s)}q(s,a)$

我们可以把右边的maxpi写成一个函数

$f(v):=\max_\pi(r_\pi+\gamma P_\pi v)$

求解max pi的方法就是固定一个初始值v，就可以求解出一个pi，在里面，v是一个向量，代表着每个状态s的state value，每个值大小为

$[f(v)]_s=\max_\pi\sum_a\pi(a|s)q(s,a),\quad s\in\mathcal{S}$

求解之前，这里引入了一个概念——不动点 Fixed point，假设，在集合X上，有一个点x，有一个函数能够满足 f(x)=x【与y = x相交的点】，那x就是不动点、

第二个概念 Contraction mapping

$\|f(x_1)-f(x_2)\|\leq\gamma\|x_1-x_2\|$

二范数，每个元素的平方和再开根，相当于求两个点之间的欧式距离，两个点差的norm，小于两个点本身的norm，相当于f(x1)与f(x2)映射后的距离比先前的小，衰减系数取值在 0~1之间，fixed point x*是唯一的，通过迭代的方法就可以计算出来(逼近)

$\begin{aligned}x_{k+1}=f(x_k)\end{aligned}$

贝尔曼公式是满足contraction mapping的，那么就可以用这种迭代方式来推出来

$v_{k+1}=f(v_k)=\max_\pi(r_\pi+\gamma P_\pi v_k)$

最后vk就会收敛到v*，假设v*就是贝尔曼公式的最优解

$v^*=\max_\pi(r_\pi+\gamma P_\pi v^*)$

pi*是对于v*的一个最优策略，也就是固定v*，可以求解除一个pi

$\pi^*=\arg\max_\pi(r_\pi+\gamma P_\pi v^*)$

就可以最后化简成一个式子，这个式子本质就是一个贝尔曼公式(矩阵形式)，他一定是对应一个策略，v*就是pi*所对应的state value，pi*就是会选择最大的a*

$v^*=r_{\pi^*}+\gamma P_{\pi^*}v^*$

贝尔曼最优公式，需要我们求取的，就是最优的策略pi，最优的state value

贝尔曼最优公式，需要我们求取的，就是最优的策略pi，最优的state value。需要注意，optimal state value是唯一的，而对应的 optimai policy可能不是唯一的，我们从公式上来理解，首先贝尔曼最优方程，我们一直说他是通过递归的方式来定义的，表示给定状态下通过最优策略可以获得的回报

$V^*(s)=\max_\pi\mathbb{E}\left[R(s,a)+\gamma\sum_{s^{\prime}}P(s^{\prime}|s,a)V^*(s^{\prime})\right]$

最后算出的V*(s),是当前算出的最优价值，由于状态转移概率P和奖励R是固定的，这就是一个关于 V 的函数，那么他的解一定只有一个，

但是最优策略是在每个状态下选择的动作。以网格世界来说，state value就是你在这个网格内采取最正确的行动能获得最大的值，但是显然，在状态s内，会出现采取多个动作a1，a2获得相同回报的情况，那么这些动作都是最优的。这种情况下就可以有多个策略，每个策略在状态s下的动作不同，但是都能实现最优状态。按照我的理解来看，state value就是网格本身，policy是网格的行动，一个网格自然只能有一个最大值，但是一个网格内可有多种行动来达到最大值。

举个最简单的例子，假设状态s1，在这网格s1内有两个动作a1,a2，采取行动后都跳转到s2，获得的V(s1)相同都是10，那么最优状态V(s1)是唯一的，但是可选a1 a2 a1a2随机选择三种策略。比如一、Examples中的例子，如果s2的奖励也为1，那么向右移动和向下就是一样的

查看全文

http://www.kler.cn/a/520885.html