【强化学习入门笔记】1.5 贝尔曼最优公式

本系列为学习赵世钰老师的《强化学习的数学原理》所作的学习笔记.

课程视频网址：https://space.bilibili.com/2044042934

1.5.1 定义

1.5.1.1 Contraction mapping theorem (收缩映射定理)

• fixed point(不动点)

如果$x^{\ast }$满足下式, $x^{\ast }$称之为fixed point(不动点)

$$f\left(x^{\ast }\right)=x^{\ast }$$

• Contraction mapping (收缩映射)

如果一个函数满足下面不等式, 则称这个函数满足Contraction mapping

$$\begin{gathered} \Vert f\left(x_1\right)-f\left(x_2\right)\Vert \le \gamma \Vert x_1-x_2\Vert \\ \gamma \in (0,1) \end{gathered}$$

• Contraction mapping theorem (收缩映射定理)

如果函数$f(x)$满足Contraction mapping, 则有Contraction mapping theorem:

• 存在性: 一定存在fixed point, 使其满足$f\left(x^{\ast }\right)=x^{\ast }$
• 唯一性: fixed point $x^{\ast }$一定是唯一的
• 求解算法: $x^{\ast }$可以通过迭代计算得到, 并且迭代会指数收敛

1.5.1.2 贝尔曼最优公式

如果对于所有的状态$\mathcal{S}$, 策略${\pi }^{\ast }$的状态值大于等于其他任何一个策略的状态值, 那么${\pi }^{\ast }$称之为$\mathcal{S}$状态空间中的最优策略:

$$v_{{\pi }^{\ast }}(s)\ge v_{\pi }(s)\text{ for all }s\in \mathcal{S}$$

在贝尔曼公式的基础上, 求解使得状态值$v(s)$最大的策略$\pi (s)$就是贝尔曼最优公式:

$\begin{array}{rl}v(s)& =\underset{\pi (s)\in \Pi (s)}{\max }\sum _{a\in \mathcal{A}}\pi (a\mid s)\left(\sum _{r\in \mathcal{R}}p(r\mid s,a)r+\gamma \sum _{s^{\prime }\in \mathcal{S}}p\left(s^{\prime }\mid s,a\right)v\left(s^{\prime }\right)\right)\\ & =\underset{\pi (s)\in \Pi (s)}{\max }\sum _{a\in \mathcal{A}}\pi (a\mid s)q(s,a),\end{array}$

将贝尔曼最优公式写成矩阵形式:

$$v=\underset{\pi \in \Pi }{\max }\left(r_{\pi }+\gamma P_{\pi }v\right)$$

如果将右边的最优化问题, 定义为函数$f(x)$:

$$v=f(v)=\underset{\pi }{\max }\left(r_{\pi }+\gamma P_{\pi }v\right)$$

书中详细证明了函数符合Contraction mapping, 有兴趣可以看详细证明, 这里我们使用结论即可.

1.5.2 最优解及其特性

1.5.2.1 最优解

Contraction mapping theorem告诉我们:贝尔曼最优公式一定存在唯一解$v^{\ast }$, 并且可以用迭代的方式求解.

当我们有了最优解$v^{\ast }$之后, 就有它对应的最优策略${\pi }^{\ast }$:

$${\pi }^{\ast }=\arg \underset{\pi \in \Pi }{\max }\left(r_{\pi }+\gamma P_{\pi }{v}^{\ast }\right)$$

那么贝尔曼最优公式可以简写成:

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

我们可以发现, 这就是一个贝尔曼公式. 只不过他的参数是最优策略${\pi }^{\ast }$, 也就是说贝尔曼最优公式是贝尔曼公式在最优策略下的一个特殊形式.

$v^{\ast }=v_{{\pi }^{\ast }}\ge v_{\pi }$, 书中同样详细证明了为什么$v^{\ast }$和${\pi }^{\ast }$是最优的.

1.5.2.2 Greedy optimal policy(贪婪最优定理)

最优策略${\pi }^{\ast }$的Greedy optimal policy(贪婪最优定理), 对于任何 $s\in S$，贝尔曼最优公式的最优解唯一, 且是确定性贪婪策略:

$${\pi }^{\ast }(a\mid s)=\{\begin{array}{ll}1,& a=a^{\ast }(s),\\ 0,& a\ne a^{\ast }(s),\end{array}$$

之所以称之为贪婪, 是因为只有最优动作的概率是1, 其他动作概率都是0. 但是仍然有以下两个性质需要注意:

• ${\pi }^{\ast }$不唯一: 虽然最优解$v^{\ast }$的值是唯一的, 但是最优策略不唯一. 也就是说, 可能有多个策略的状态值都是最优.
• ${\pi }^{\ast }$可能是随机策略: 虽然Greedy optimal policy告诉我们, 一定存在一个确定性的策略${\pi }^{\ast }$; 但是因为${\pi }^{\ast }$不唯一, 其他的${\pi }^{\ast }$可能是随机策略.

这个例子可以说明上面的两个特性: 两个策略的状态值都是最优, 那么它们都是最优策略; 并且左边是确定策略, 右边是随机策略.

1.5.3 例子

我们重新回顾贝尔曼最优公式:

$$v(s)=\underset{\pi (s)\in \Pi (s)}{\max }\sum _{a\in \mathcal{A}}\pi (a\mid s)\left(\sum _{r\in \mathcal{R}}p(r\mid s,a)r+\gamma \sum _{s^{\prime }\in \mathcal{S}}p\left(s^{\prime }\mid s,a\right)v\left(s^{\prime }\right)\right),s\in \mathcal{S}.$$

• 求解目标: 状态值$v(s)$, 策略$\pi (s)$
• 参数$r,\gamma$: 通过改变奖励设计和折扣率, 可以改变最优解

1.5.3.1 $\gamma$的影响

举个例子说明参数的影响,在这样参数设置时:

• 抵达禁止格或边界的奖励是-1: $r_{\text{boundary }}=r_{\text{forbidden }}=-1$
• 抵达终点的奖励是1: $r_{\text{target }}=1$
• $\gamma =0.9$
• 其他行为奖励是0

它的最优策略和最优状态值如下图所示, 它会倾向于穿过禁止格, 抵达终点:

当我们把$\gamma =0.5$时, 最优策略则倾向于绕过禁止格, 抵达终点:

当我们把$\gamma =0$时, 最优策略则几乎放弃抵达终点, 倾向于脱离禁止格后原地不动, 因为它只考虑了眼前的即时动作奖励:

这几个例子说明了$\gamma$代表奖励设计的远视程度: $\gamma$越大说明越鼓励长远的收益; $\gamma$越小说明越鼓励眼前的收益;

不过需要说明的是, 只要$\gamma$不等于1, 远期收益都会逐渐衰减. 我们可以看return的公式:

$$G_t=R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+\dots$$

因为$0\le \gamma \le 1$, 越远期的奖励折扣率越小, 它自然的就会使得远期收益逐渐衰减.

1.5.3.2 $r$的影响

如果我们非常不希望策略进入禁止格, 那么我们可以将禁止格惩罚设置为-10或者是更小的值, 来惩罚对应的动作.

但是显而易见的是: 如果整体性的放大奖励, 比如将终点奖励也设置为10, 结果不会有任何变化.

推荐阅读

• 端到端理论与实战
• 动手学轨迹预测
• 动手学运动规划
• 动手学行为决策
• 强化学习入门笔记