【强化学习的数学原理】第03课-贝尔曼最优公式-笔记

学习资料：bilibili 西湖大学赵世钰老师的【强化学习的数学原理】课程。链接：强化学习的数学原理 西湖大学 赵世钰

一、例子：如何改进策略？

下图是一个grid world的例子。要求：写出该例的贝尔曼方程、计算每个状态的state value、计算状态s1的action value。

因为该例非常简单，所以无需套贝尔曼方程的公式，直接根据“即时奖励”+“未来奖励”的思路就可以写出贝尔曼方程。贝尔曼方程如下：

假设 $\gamma =0.9$， 联立方程组解方程，就可以解出每个状态的state value。结果为：

已知state value后，又可以计算出action value。这里的action value怎么算呢？因为例子比较简单，我们可以不套公式，而直接使用“即时奖励”+“未来奖励”的思路来计算。以下图中第三行 $q_{\pi }(s_1,a_3)$ 为例，在状态 $s_1$ 选择动作 $a_3$ （向下走），所获得的即时奖励是0，未来奖励是 $\gamma v_{\pi }(s_3)$。

到此，我们算出了状态s1的action value。对状态s1的策略进一步观察，可以发现，当前这个策略“s1-s2-s4”其实是不太好的，因为经过了forbidden area s2。 那么该如何改进这个策略呢？
策略的改进依赖于action value！
当前的策略为如下图所示。也就是说，a=a2 （往右走）的概率是1，往其他方向走的概率是0。

不过，根据我们刚刚算出来的action value。我们发现， $q_{\pi }(s_1,a_3)=9$ 是最大的，所以我们能不能把a3作为一个新的策略？答案是肯定的，因为action value越高，代表选择这个动作后可能获得的reward越大。从grid world中也可以看出，如果把s1的策略改成a3（向下走），不会遇到forbidden area，且可以顺利到达target area，确实是一个更好的策略。
所以，我们希望通过action value来改进策略。

二、最优策略和公式推导

1. 最优策略 ${\pi }^{\ast }$
state value 可以被用来衡量一个policy是好还是坏。如果现在有两个策略 ${\pi }_1$ 和 ${\pi }_2$，对于所有的状态 $s$， ${\pi }_1$ 的state value都大于 ${\pi }_2$ 的state value，那么就可以认为策略 ${\pi }_1$ 是好于策略 ${\pi }_2$ 的。

相似地，可以定义最优策略 ${\pi }^{\ast }$。如果对于一个策略 ${\pi }^{\ast }$，对于任意一个状态 $s$，策略 ${\pi }^{\ast }$ 带来的state value都要高于其他所有策略带来的state value，那么策略 ${\pi }^{\ast }$ 就可以被称作是最优策略。

2. 贝尔曼最优公式（Bellman optimality equation, BOE）

贝尔曼最优公式的定义如上图所示。与贝尔曼公式有一些小小的差异，贝尔曼最优公式前面多了一个 $max$ 符号。也就是说，需要找到一个策略 $\pi (s)$ ，使得状态 $s$ 的state value最大。公式中，转移概率 $p(r|s,a)$、$p(s^{\prime }|s,a)$，奖励 $r$，折扣因子 $\gamma$，都是已知的。策略 $\pi (s)$、状态值函数 $v(s)$ 和 $v(s^{\prime })$ 是未知的。

下图是贝尔曼最优公式定义的matrix-vector form。

3. 贝尔曼最优公式右边的最大化问题
如何求出一个策略 $\pi (s)$ ，使得贝尔曼公式右边的值最大化呢？

上面已经提到，贝尔曼最优公式中，策略 $\pi (s)$、状态值函数 $v(s)$ 和 $v(s^{\prime })$ 是未知的。假设把 $v(s)$ 和 $v(s^{\prime })$ 看成是一个变量，那么在贝尔曼最优公式中，有两个未知量： $v(s)$ 和 $\pi (s)$。一个方程式求解两个变量，看似有些困难。不过先别急，先看下面这个简单的例子。

对于下面这个式子，我们希望确定a、x的值，使得等式右边的值最大化。先来看a，因为 $-a^2$ 始终小于等于0，所以若想求最大值，a的值只能为0。将 a=0 代入式子后，等式就变成了 $x=2x-1$，从而可以求出x的值。因此，答案为a=0，x=1。这个思路可以被用在贝尔曼最优公式的求解中。

来看下式。我们希望从下式中求解出最优策略 $\pi$ 。一般来说，会给 $v(s^{\prime })$ 赋一个初始值，那么此时 $q(s,a)$ 就是已知的。此时需要找出一个 $\pi (a|s)$ ，使得等式右边的值最大。

但是，对于一个状态s来说，有许多的动作a可供选择。以grid world为例，一个状态s就有5种动作可以选择（上、下、左、右、不动），$q(s,a_1)$、$q(s,a_2)$、$q(s,a_3)$、$q(s,a_4)$、$q(s,a_5)$。假设在这5种选择里，$q(s,a_2)$ 的值是最大的，那么如果想求$max$，需要把 $\pi (a_2|s)$ 的值设置为1， $\pi (a_1|s)$ 、 $\pi (a_3|s)$ 、 $\pi (a_4|s)$ 、 $\pi (a_5|s)$ 的值都设置为0即可。

其数学上的表示如下图所示。意思是把$q(s,a_i)$最大的那个动作对应的概率 $\pi (a_i|s)$ 设置为1，其余动作的概率设置为0，这样就能使得等式右边的值最大化。

三、公式求解以及最优性

1. rewrite as $v=f(v)$
BOE等式右边的部分可以写成关于 $v$ 的一个函数 $f(v)$ ，因为固定 $v$ 了之后，就可以求出一个最优的 $\pi$。然后，贝尔曼最优方程就变成了 $v=f(v)$。所以，我们只要求出v，就能解出贝尔曼最优方程。

那么，该如何求解贝尔曼最优方程呢？在学习求解之前，还需要补充一些概念。

2. Contraction mapping theorem
(1) fixed point：不动点。如果在一个集合X中有一个x，有一个映射f，如果满足f(x)=x，那么x被称作一个不动点。简单来说就是，点x经过映射f后，又回到了它自己。

（2）contraction mapping：contraction mapping的直观理解就是，$x_1$映射为$f(x_1)$，$x_2$映射为$f(x_2)$，$f(x_1)$、$f(x_2)$之间的距离比$x_1$、$x_2$之间的距离要小。正好对应了“contracion（收缩）”的意思。

以下是两个帮助理解的例子。从例子 $x=f(x)=0.5x$ 中可以看出，x=0是一个fixed point，f(x)=0.5x是一个contraction mapping。将上例推广到 $x=f(x)=Ax$ ，仍然可以得到，x=0是一个fixed point，f(x)=Ax是一个contraction mapping。

contraction mapping theorem：
existence：只要f是一个contraction mapping，那么就一定存在一个fixed point。
uniqueness：fixed point是唯一的。
algorithm：fixed point是可以求解的，用一个迭代式的算法求解。从$x_0$开始，算 $x_1=f(x_0)$ ， $x_2=f(x_1)$ ，$x_3=f(x_2)$ ……可以证明，当k趋近于无穷时，$x_k$趋向于$x^{\ast }$。

（3）BOE：solution
下面将介绍如何求解贝尔曼最优公式。首先需要证明 $f(v)$ 是一个contraction mapping（证明过程略）。

如果$f(v)$ 是一个contraction mapping，那么其fixed point就可以用一种迭代式的算法求解出来。现在知道了贝尔曼最优公式BOE是一个contraction mapping，那么BOE就可以用contraction mapping求解出来。具体来说，我们可以求出fixed point $v^{\ast }$，使得 $v^{\ast }=f(v^{\ast })$ 。

把求解出的 $v^{\ast }$ 代入到贝尔曼最优公式中，可以得到下图中的第1个式子。假设 ${\pi }^{\ast }$ 为 $v^{\ast }$ 对应的最优策略（下图中的第2个式子），那么就可以把下图第1个式子中的 $max$ 给去掉了，得到下图中的第3个式子。

那么，我们所求出的这个 $v^{\ast }$ 和 $${\pi }^{\ast }$ ，是最优的state value和最优的策略吗？经证明是的。具体证明过程可以看赵老师的书。

四、最优策略的有趣性质

哪些因素影响了最优策略？从下图BOE公式中可以看出，转移概率p、奖励r、折扣因子$\gamma$，均对最优策略有影响。下面，我们将改变奖励r、折扣因子$\gamma$，看看它们的变化对最优策略有什么影响。

下图是一个grid world的例子。下图（左）展示了最优策略，可以发现，最优策略冒险经过forbidden area到达最后的target area。这是因为，它认为长远来看，冒险经过forbidden area带来的奖励，比绕一大圈到达target area带来的奖励要更高。

但是，把$\gamma$从0.9改到0.5之后，最优策略发生了改变。它不再倾向于冒险进入forbidden area了，而是选择绕一大圈，到达target area。这是因为$\gamma$，整体策略变得更加短视，不再注重长远利益了。

把$\gamma$降为0之后，策略又发生了改变。此时策略变得极为短视，仅仅根据即时奖励做出动作（action）决策。

把forbidden area的punishment加重之后，发现策略仍然倾向于绕着forbidden area走。

下面这个例子是对奖励r做出改变。把所有的奖励r变成ar+b，最优策略会改变吗？（下图中的取值是a=1,b=1）。答案是不会改变。因为影响策略的是不同奖励之间的相对差异，而不是奖励的绝对差异。

下面这个例子讨论的是，图（a）的策略要好于图（b）的策略。图（b）的策略仅仅比图（a）的策略多绕了几个格子，在寻找最优策略时，是如何规避这种无意义的绕路（meaningless detour）的呢？

答案是用discount rate $\gamma$ 来控制。假设有两条路径a、b，它们的起点、终点相同，但是路径b比路径a多兜了几圈。那么在计算return时，因为 $\gamma$ 的存在，路径b比路径a的return更小，因此b的动作价值函数（action value）更低，这个动作就不倾向于被选择为最优策略。

很多初学者认为，在设计奖励的时候，应该每走一步给一个惩罚（例如在下图中，从一个白色格子跳到另一个白色格子，给予其一个惩罚r=-1），使得程序不要在白色格子里反复横跳，能找一个最短路径跳到target area。但这种做法是不必要的，因为discount rate $\gamma$ 本身的性质就能够自然地找到一个到达target area的最短路径。

五、本节课summary