贝尔曼最优公式

作用：用于找到最优的 Policy

最优 Policy

如果存在一个 Policy ${\pi }^{\ast }$，st 对于 $\forall s$ 以及 $\forall \pi$，都有 $v_{{\pi }^{\ast }}(s)\ge v_{\pi }(s)$，则称为是最优 Policy

因此最优的 Policy 要保证每一个 state 上的 state value，都优于任一其他的 Policy 在该位置的 state value （Note：State Value 的定义是从当前 state 出发，一条无限长 （实践中足够长就可以）的 trajectory 的总期望得分，且 $$v_{\pi }(s)=E[R_{t+1}|S_t=s]+\gamma \sum _{s^{\prime }}{v}_{\pi }(s^{\prime })P(S_{t+1}=s^{\prime }|S_t=s)$$，即当前 state 的 state value 取决于比它短一格的 trajectory 的总期望，其思路有点类似于 CRF 中使用的 Viterbi 算法，找的是全局最优，而不是局部最优）。现在有以下几个问题：

1. 这样的 ${\pi }^{\ast }$ 是否存在
2. 这样的 ${\pi }^{\ast }$ 是否唯一
3. 这样的 ${\pi }^{\ast }$ 是确定的还是有随机性

求解贝尔曼最优公式

首先回忆第一节当中的贝尔曼公式，一般形式：
$$\begin{array}{r}{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 })],\forall s\end{array}$$

matrix-form：
$$v_{\pi }=r_{\pi }+\gamma P_{\pi }{v}_{\pi }$$ 或
$$v_{\pi }=(I-\gamma P_{\pi }{)}^{-1}{r}_{\pi }$$
其中 $r_{\pi }(s_i)={\sum }_a\pi (a|s_i){\sum }_{r}P(r|s_i,a)r=E[R_{t+1}|S_t=s_i]$, $P_{\pi }(s_i)={\sum }_{s_j}{P}_{\pi }(s_j|s_i)$

找最优的 ${\pi }^{\ast }$ 等价于找到最大的 State Value，即:
$$v_{{\pi }^{\ast }}=\max ((I-\gamma P_{\pi }{)}^{-1}{r}_{\pi })，\forall s,\forall \pi \in \Pi$$
上式等价于：
$$v_{{\pi }^{\ast }}=\max (r_{\pi }+\gamma P_{\pi }{v}_{{\pi }^{\ast }})，\forall s,\forall \pi \in \Pi$$
后面我们将 $v_{{\pi }^{\ast }}$ 简记为 $v^{\ast }$，记 $$f(v)=\underset{\pi }{\max }(r_{\pi }+\gamma P_{\pi }v)$$
那么 $v^{\ast }$ 即满足 $$v^{\ast }=f(v^{\ast })$$ 的点。

求解最大 State Value $v^{\ast }$

求解上述 $$v^{\ast }=f(v^{\ast })$$ 需要引入 压缩映射定理：

设 $(X,d)$ 是一个完备度量空间，$T:X\to X$ 是一个压缩映射，即存在一个常数 $0\le k<1$，使得对于所有的 $x,y\in X$，有：
$$d(T(x),T(y))\le k\cdot d(x,y)$$
那么 $T$ 在 $X$ 中有 唯一 的不动点 $x^{\ast }$，即 $T(x^{\ast })=x^{\ast }$。并且，对于任意初始点 $x_0\in X$，迭代序列 { x n } \{ x_n \} {xn​} 定义为：
$$x_{n+1}=T(x_n)$$
将收敛于不动点 $x^{\ast }$，即：
$$\underset{n\to \infty }{\lim }{x}_n=x^{\ast }$$

因此只要能证明存在一个度量函数 $d$，使得对于所以 $v_1,v_2$ 满足： $$d(f(v_1),f(v_2))\le k\cdot d(v_1,v_2)$$
就可以证明：

1. 最大 State Value $v^{\ast }$ 存在且唯一
2. 最大 State Value $v^{\ast }$ 可以由 $v_{k+1}=f(v_k)$ 迭代求解

根据 $v^{\ast }$ 求解最佳 Policy ${\pi }^{\ast }$

由于 $$v_{\pi }(s)=\sum _a\pi (a|s)q_{\pi }(s,a)$$
其中 $q_{\pi }(s,a)$ 是 从 state s 出发，且 take action a 的期望return，那么一定存在一个 $a^{\ast }$，使得：
$$a^{\ast }(s)=\underset{a\in A}{\mathrm{argmax}}{q}^{\ast }(s,a)$$
又由于 ${\sum }_a\pi (a|s)=1$，因此使得 ${\sum }_a\pi (a|s)q_{\pi }(s,a)$ 取得最大值的 ${\pi }^{\ast }$ 应该形如：
$${\pi }^{\ast }(a|s)=\{\begin{array}{l}1,a=a^{\ast }(s)\\ 0,a\ne a^{\ast }(s)\end{array}$$
上述最佳 Policy ${\pi }^{\ast }$ 是确定形式的，也称为“贪婪”的。根据上式，需要求解该 ${\pi }^{\ast }$ 只需求解 $a^{\ast }(s)，\forall s$，而 $a^{\ast }(s)={\mathrm{argmax}}_{a\in A}{q}^{\ast }(s,a)$ ，所以只需要解得所有的 $q^{\ast }(s,a)$，根据 第一节 的内容：
$$q^{\ast }(s,a)=\sum _{r}P(r|s,a)r+\gamma \sum _{s^{\prime }}P(s^{\prime }|s,a)v^{\ast }(s^{\prime })$$

这里 $v^{\ast }$ 可以由 $v_{k+1}=f(v_k)$ 迭代求解，而 $P(r|s,a),P(s^{\prime }|s,a)$ 在前面这些章节中都认为是已知的（后面章节会讨论未知的情形）。因此 $q^{\ast }(s,a)$ 也可以求解。由此我们完成了对最佳 Policy ${\pi }^{\ast }$ 的求解。

Note: 最大 State Value $v^{\ast }$ 具有唯一性，但是达到这样的 $v^{\ast }$ 的 Policy ${\pi }^{\ast }$ 可能并不是唯一的，例如：

上述两个不同的 Policy， 它们的 state value 完全相同，因为在出现 diff 的部分路径上，reward总和相同

一些证明过程

为了说明 $f(v)={\max }_{\pi }(r_{\pi }+\gamma P_{\pi }v)$ 是压缩映射，只需要证明：

对任意 $v_1,v_2$，有：
$$||f(v_1)-f(v_2)|{|}_{\infty }\le \gamma ||v_1-v_2|{|}_{\infty }$$
其中 $||\cdot |{|}_{\infty }$ 是 maximum 范数

---

---

一些影响 ${\pi }^{\ast }$ 的因素

如何让 ${\pi }^{\ast }$ 不 “绕弯路”

以下为一个简单 grid-word 的两种 Policy，显然前者优于后者，因为后者走了 “冤枉路”，本可以直接到 target state 的，却绕了弯路：

但与直观相违背的是，对于从白格子走到白格子的 action，其 reward 并不需要设为负数，而可以直接设为 0，用 discount rate $\gamma$ 来对绕弯路的行为做惩罚：
$$\begin{array}{rl}{\text{return}}_1& =1+\gamma 1+{\gamma }^{2}1+...=\frac{1}{1-\gamma }\\ {\text{return}}_2& =0+\gamma 0+{\gamma }^{2}1+{\gamma }^{3}1+...=\frac{{\gamma }^2}{1-\gamma }\end{array}$$
所以 ${\text{return}}_2$ 一定小于 ${\text{return}}_1$，且 $\gamma$ 越小，差距越大。一个直观的理解是：“绕弯路” 虽然不会直接产生惩罚，但是它延后了取得奖励（即到达 target state）的时间，而时间越晚，discount rate $\gamma$ 对奖励的“打折”越大，因此好的 Policy 会倾向于更快得拿到奖励

$\gamma$ 的影响

$\gamma$ 的作用除了刚刚讨论的，在 第一节 中，我们也说过，由于：
$$\begin{array}{rl}\text{discount return}& =R_0+\gamma R_1+{\gamma }^2{R}_2+...\end{array}$$
因此，当$\gamma$更趋于0时，return更受早期的action影响，而当$\gamma$更趋于1时，return更受后期的action的影响。可以看一些例子得到更直观的理解：

• $\gamma =0.9$ 时，Policy 会更受后期的action的影响，因此在接近 target state 时，为了尽快的到达，会不惜进入 forbidden state
  

• $\gamma =0.5$ 时，Policy 受后期的action的影响没那么大了，相反当下立即进入 forbidden state 得到的惩罚权重更大了，因此它可能会为了避免进入 forbidden state 而绕弯路

• $\gamma =0$ 时，Policy 会变得极端 “短时”，因为后面步骤得分的权重归零了，所以在任何 state 中，它都只倾向于走当前步所有可操作的 action 中 reward 最高的，并且不再考虑未来是否能走到 target value

reward 的影响

这里有一个也是比较直观的结论：

如果所有的 reward 都做一个线性变换：$$r^{\prime }=ar+b，a>0$$
那么根据新的 reward 找到的 ${\pi }^{\prime \ast }$ 跟原来的 ${\pi }^{\ast }$ 相同

Proof：一个直观的理解是，由于
$${\pi }^{\ast }(a|s)=\{\begin{array}{l}1,a=a^{\ast }(s)\\ 0,a\ne a^{\ast }(s)\end{array}$$
那么只要 $a^{\ast }(s)$ 不变，${\pi }^{\ast }$ 就不变。而：
$$a^{\ast }(s)=\underset{a\in A}{\mathrm{argmax}}{q}^{\ast }(s,a)$$
因此，只要这个变化不改变 reward 的 相对大小，就不会改变 $a^{\ast }(s)$。上述线性变化显然符合这个要求。

---

值迭代与策略迭代

值迭代

值迭代基本是上面过程的一个总结：

1. 初始化一个 $v_0$
2. 迭代过程为：$$已知v_k\to 求解q_k(s,a)\to {\pi }_{k+1}(a|s)=\{\begin{array}{l}1,a=a^{\ast }(s)\\ 0,a\ne a^{\ast }(s)\end{array}\to v_{k+1}=\underset{a}{\max }{q}_k(s,a)$$
   其中 $$q_k(s,a)=\sum _{r}P(r|s,a)r+\gamma \sum _{s^{\prime }}P(s^{\prime }|s,a)v_k(s^{\prime })$$
3. 当 $||v_{k+1}-v_k||<ϵ$ 时，停止迭代

---

下面看一个具体的例子加深理解，对于如下 grid-word:

1. 初始化 $v_0$ 为全零向量： $$v_0(s_1)=v_0(s_2)=v_0(s_3)=v_0(s_4)=0$$
2. 根据 $q(s,a)$ 的计算式：
   
   $q_0(s,a)$ 为：
   
   因此 ${\pi }_1$ 为：
   $${\pi }_1(a_5|s_1)=1,{\pi }_1(a_3|s_2)=1,{\pi }_1(a_2|s_3)=1,{\pi }_1(a_5|s_4)=1$$

\qquad Note, 这里 ${\pi }_1(a_5|s_1)=1$ 或者 ${\pi }_1(a_3|s_1)=1$ 均可，随机取一个。$v_1$ 的值也随即可得：
$$v_1(s_1)=0,v_1(s_2)=1,v_1(s_3)=1,v_1(s_4)=1$$
${\pi }_1$对应的 grid-word 图为：
\qquad
\qquad 显然这还不是最优解，$s_1$ 的 policy 还有优化空间

3. 根据上述 $v_1$ 可以求 $q_1(s,a)$：
   
   因此 ${\pi }_2$ 为：
   $${\pi }_1(a_3|s_1)=1,{\pi }_1(a_3|s_2)=1,{\pi }_1(a_2|s_3)=1,{\pi }_1(a_5|s_4)=1$$
   $v_2$ 为：
   $$v_2(s_1)=\gamma ,v_2(s_2)=1+\gamma ,v_2(s_3)=1+\gamma ,v_2(s_4)=1+\gamma$$
   此时图为：
   \qquad
   达到最优 Policy。

---

策略迭代

与值迭代不同，策略迭代是先从初始化策略 ${\pi }_0$ 开始的，迭代过程：

$$已知{\pi }_k\to (v_{{\pi }_k}^{(0)}\to v_{{\pi }_k}^{(1)}\to ...\to v_{{\pi }_k}^{(\infty )}=v_{{\pi }_k})\to 求解q_{{\pi }_k}(s,a)\to {\pi }_{k+1}=\{\begin{array}{l}1,a=a^{\ast }(s)\\ 0,a\ne a^{\ast }(s)\end{array}\to ...$$
上面跟值迭代相比最主要的不同是 $(v_{{\pi }_k}^{(0)}\to v_{{\pi }_k}^{(1)}\to ...\to v_{{\pi }_k}^{(\infty )}=v_{{\pi }_k})$，将其展开：
$$\begin{array}{rl}{v}_{{\pi }_k}^{(1)}& =r_{{\pi }_k}+\gamma P_{{\pi }_k}{v}_{{\pi }_k}^{(0)}\\ v_{{\pi }_k}^{(2)}& =r_{{\pi }_k}+\gamma P_{{\pi }_k}{v}_{{\pi }_k}^{(1)}\\ & \dots \\ v_{{\pi }_k}^{(\infty )}& =r_{{\pi }_k}+\gamma P_{{\pi }_k}{v}_{{\pi }_k}^{(\infty )}\end{array}$$

那么首先一个问题是，由于 $v$ 不再是通过 $v_{k+1}={\max }_{\pi }(r_{\pi }+\gamma P_{\pi }{v}_k)$ 来求解了，那么上述策略迭代的有效性要如何保证呢？ 保证上述迭代策略的有效性可以分成两个部分：

1. ${\pi }_{k+1}$ 是否总是比 ${\pi }_k$ 更好
2. 上述迭代能否收敛

---

要证明 ${\pi }_{k+1}$ 是否总是比 ${\pi }_k$ 更好，只需要证明 $v_{{\pi }_{k+1}}\ge v_{{\pi }_k}$ 总成立

Proof: 由于
$$\begin{array}{rl}{v}_{{\pi }_k}& =r_{{\pi }_k}+\gamma P_{{\pi }_k}{v}_{{\pi }_k}\\ v_{{\pi }_{k+1}}& =r_{{\pi }_{k+1}}+\gamma P_{{\pi }_{k+1}}{v}_{{\pi }_{k+1}}\end{array}$$
由于 ${\pi }_{k+1}={\mathrm{argmax}}_{\pi }(r_{{\pi }_k}+\gamma P_{{\pi }_k}{v}_{{\pi }_k})$ 其中 $v_{{\pi }_k}$ 是固定值， (该式总成立，因为 ${\pi }_{k+1}=\{\begin{array}{l}1,a=a^{\ast }(s)\\ 0,a\ne a^{\ast }(s)\end{array}$ 即为该式的贪婪解)
因此 $$r_{{\pi }_{k+1}}+\gamma P_{{\pi }_{k+1}}{v}_{{\pi }_k}\ge r_{{\pi }_k}+\gamma P_{{\pi }_k}{v}_{{\pi }_k}=v_{{\pi }_k}$$
$$\Rightarrow v_{{\pi }_{k+1}}-v_{{\pi }_k}\ge (r_{{\pi }_{k+1}}+\gamma P_{{\pi }_{k+1}}{v}_{{\pi }_{k+1}})-(r_{{\pi }_{k+1}}+\gamma P_{{\pi }_{k+1}}{v}_{{\pi }_k})\ge \gamma P_{{\pi }_{k+1}}(v_{{\pi }_{k+1}}-v_{{\pi }_k})$$

$$\Rightarrow v_{{\pi }_{k+1}}-v_{{\pi }_k}\ge \gamma P_{{\pi }_{k+1}}(v_{{\pi }_{k+1}}-v_{{\pi }_k})\ge {\gamma }^2{P}_{{\pi }_{k+1}}^2(v_{{\pi }_{k+1}}-v_{{\pi }_k})\ge ...\ge \underset{n\to \infty }{\lim }{\gamma }^n{P}_{{\pi }_{k+1}}^n(v_{{\pi }_{k+1}}-v_{{\pi }_k})$$
其中 $0<\gamma <1$，因此 ${\lim }_{n\to \infty }{\gamma }^n=0$；而 $P_{{\pi }_{k+1}}$ 是随机矩阵，所以 $P_{{\pi }_{k+1}}^n$ 不会发散。所以 $v_{{\pi }_{k+1}}-v_{{\pi }_k}\ge 0$。

---

收敛性的证明要依赖我们上面由 压缩映射定理 得到的结论：
$$v_{k+1}=f(v_k)=\underset{\pi }{\max }(r_{\pi }+\gamma P_{\pi }{v}_k)\to v^{\ast }$$
由于 $v^{\ast }=\max ((I-\gamma P_{\pi }{)}^{-1}{r}_{\pi })，\forall s,\forall \pi \in \Pi$，因此 $v_{{\pi }_k}\le v^{\ast },\forall k$ 一定成立。那么我们只需要证明存在上述由 $v_{k+1}=f(v_k)$ 推导的 { v k } \{v_k\} {vk​}，使得满足： $$v_k\le v_{{\pi }_k},\forall k$$
由于 $$v_k\le v_{{\pi }_k}\le v^{\ast }，而\underset{k\to \infty }{\lim }{v}_k=v^{\ast }$$
因此可以证明 $$\underset{k\to \infty }{\lim }{v}_{{\pi }_k}=v^{\ast }$$

---

Proof： 由于 $v_0$ 是任意初始化的，所以对任意 ${\pi }_0$ 总可以找到 $v_0$ 使得 $$v_{{\pi }_0}\ge v_0$$
由归纳法，只需要证明当 $v_{{\pi }_k}\ge v_k$ 时，$v_{{\pi }_{k+1}}\ge v_{k+1}$ 成立。

$$\begin{array}{rl}{v}_{{\pi }_{k+1}}-v_{k+1}& =(r_{{\pi }_{k+1}}+\gamma P_{{\pi }_{k+1}}{v}_{{\pi }_{k+1}})-\underset{\pi }{\max }(r_{\pi }+\gamma P_{\pi }{v}_k)\\ & \ge (r_{{\pi }_{k+1}}+\gamma P_{{\pi }_{k+1}}{v}_{{\pi }_{k+1}})-\underset{\pi }{\max }(r_{\pi }+\gamma P_{\pi }{v}_k)(\text{由上述结论}{v}_{{\pi }_{k+1}}\ge v_k)\\ & =(r_{{\pi }_{k+1}}+\gamma P_{{\pi }_{k+1}}{v}_{{\pi }_{k+1}})-(r_{{\pi }_k}+\gamma P_{{\pi }_k}{v}_k)(\text{由于 }{\pi }_k=\arg \underset{\pi }{\max }(r_{\pi }+\gamma P_{\pi }{v}_k))\\ & \ge (r_{{\pi }_k}+\gamma P_{{\pi }_k}{v}_k)-(r_{{\pi }_k}+\gamma P_{{\pi }_k}{v}_k)(\text{由于 }{\pi }_{k+1}=\arg \underset{\pi }{\max }(r_{\pi }+\gamma P_{\pi }{v}_{{\pi }_k}))\\ & =\gamma P_{{\pi }_k}(v_{{\pi }_k}-v_k)\ge 0\end{array}$$
证毕。

---

值迭代和策略迭代的具体差别

以下是值迭代和策略迭代的对比图：

可以看到，当 $v_0$ 选取得当，两种策略的 ${\pi }_1$ 是相同的，但是从 ${\pi }_2$ 开始就不一定了，这是因为，计算 $v_{{\pi }_1}$ 过程实际是：

即 值迭代的 $v_1$ 其实就是策略迭代中的 $v_{{\pi }_1}^{(1)}$，所以就大的 iteration 而言，一般策略迭代会在 $k$ 更小的时候收敛：

当然这不意味着策略迭代的整体计算量更小，因为它每个大的 iteration 里面，会比值迭代计算更多轮的 Value State 。

这里当介于两者之间时，称为 截断策略迭代。

---

一个小例子

这个小例子有一点比较有意思：可以看出 Policy 的优化往往是现从靠近 target value 的地方开始的，这个其实也很好理解，根据贝尔曼公式：$$\begin{array}{rl}\Rightarrow v_{\pi }(s)& =E[G_t|S_t=s]\\ & =E[R_{t+1}+\gamma G_{t+1}|S_t=s]\\ & =E[R_{t+1}|S_t=s]+\gamma E[G_{t+1}|S_t=s]\end{array}$$
其中 $E[G_{t+1}|S_t=s]$ 就是后面路径的 state value，因此要优化当前位置的 state value，一定是先优化后面的 state 的 state value，再逐渐优化远离 target value 的 state。

---

Reference:
1.强化学习的数学原理