贝尔曼最优公式是贝尔曼公式的一个特殊情况，是一个很重要的式子
两个概念：最优状态值（optimal state value）、最优策略（optimal policy）
一个工具：贝尔曼最优公式（BOE,bellman optimal equation）
1. 引子——抛砖引玉
上图中所示的例子我们已经很熟悉了，很容易理解。其中，绿色的箭头代表策略 $\pi$。
接下来，我们需要去做两件事情。
首先，我们需要求解贝尔曼最优公式得到 state value，进而得到 action value （在此基础上，我们在后面会进一步介绍一个很有意思的现象）
利用我们之前学到的贝尔曼公式，我们可以对图中的例子得到以下公式：
$$ 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) $$
令 $\gamma = 0.9$，我们代入上式计算可得：
$$ v_{\pi}(s_4)=v_{\pi}(s_3)=v_{\pi}(s_2)=10 $$
$$ v_{\pi}(s_1)=8 $$
接下来，我们单独考虑状态 $ s_1 $。$ s_1 $一共有五个动作，我们有下列式子：
$$ 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 $$
有了上面的分析后，我们可以提出一个很有意思的问题：如果我们的策略不太好，我们应该如何去优化策略呢？
答案是：我们可以依赖 action value 来优化策略。
比如说，我们在上图中有一个策略 ${\pi}(a|s_1)$：
$$ {\pi}(a|s_1)= \left \{ \begin{matrix} 1 \quad a=a_2 \\ 0 \quad a\neq a_2 \end{matrix}\right. $$
在这个策略下，我们已经计算出 action value 了：
$$ q_{\pi}(s_1,a_1)=6.2 $$
$$ q_{\pi}(s_1,a_2)=8 $$
$$ q_{\pi}(s_1,a_3)=9 $$
$$ q_{\pi}(s_1,a_4)=6.2 $$
$$ q_{\pi}(s_1,a_5)=7.2 $$
通过观察可以发现 $a_3$ 对应的 action value 是最大的，那么我们能否选择 $a_3$ 作为一个新的策略呢？我们可以先将新的策略表示成下面这个式子：
$$ {\pi}_{new} (a|s_1)= \left \{ \begin{matrix} 1 \quad a=a^* \\ 0 \quad a\neq a^* \end{matrix}\right. $$
在这个新策略下，智能体一定会选择动作 $a^*$ ，而 $a^*$ 就对应了当前状态下 action value 最大的那个 action。在我们上面的例子里，$a^*=argmax_a q_{\pi} (s_1,a)=a_3$。
所以，为什么我们选择 action value 最大的那个 action 就能得到一个比较好的策略呢？从直观上来说，就是因为这个 action value 本身就代表了动作 action 的价值，选择一个较大的 action value 便代表我们可以收获更多的 reward。但是在数学上其实并不是很容易理解，比如如果出现来全局最优与局部最优问题的时候就很难考虑。
事实上，从机器学习的角度上来看，只要我们一遍一遍反复迭代，最后一定能得到一个最优的策略。
这里我们可以先不考虑这些问题，等介绍完所有理论部分的内容后，你或许会有更深入的见解。
下面我们开始正式介绍贝尔曼最优公式的相关定义。
2. 最优策略optimal policy
刚才我们反复强调了 state value 的重要性，是因为它能够来衡量一个策略究竟是好还是不好。那么接下来，我们来正式地定义这种说法。
如果我有两个策略分别为 ${\pi}_1$ 和 ${\pi}_2$，那它们在每一个状态都有自己的 state value ，如果对于所有的状态 $s$ ，${\pi}_1$ 得到的 state value 都是大于 ${\pi}_2$ 得到的 state value ，我们就称 ${\pi}_1$ 是比 ${\pi}_2$ 要好的。进一步，我们就可以来定义 最优。
什么是最优呢？
如果一个策略 ${\pi}^*$ 对任意一个状态，其所得的 state value 都大于或等于其他所有的策略 $\pi$，我们便称这个 ${\pi}^*$ 是最优的。
其实，给出上述定义并不麻烦，最麻烦的事情是我们现在给出这个定义后，需要去回答一系列问题：
- 这个最优的策略是否存在？
- 这个最优的策略是唯一的吗？
- 这个最优的策略是不确定的还是确定的？
- 如何得到最优的策略？
为了回答上述这些问题，我们需要研究贝尔曼最优公式。
3. 贝尔曼最优公式 BOE
3.1 Introduction
我们首先给出贝尔曼最优公式的数学表达式：
$$ v(s)= \sum_{a}{\pi}(a|s)(\sum_r p(r|s,a)r + \gamma \sum_{s’}p(s’|s,a)v(s’)),\quad \forall s \in S $$
我们现在观察上面这个表达式，你会发现这个式子看起来很眼熟——它其实就是当策略 $\pi$ 给定的时候的贝尔曼公式。
这里我们做一个小改动——在策略 $\pi$ 前加上一个 max：
$$ v(s)= max_{\pi} \sum_{a}{\pi}(a|s)(\sum_r p(r|s,a)r + \gamma \sum_{s’}p(s’|s,a)v(s’)),\quad \forall s \in S $$
这个时候策略 $\pi$ 就不再是固定的了，因为其中嵌套了一个优化问题，我们需要先解决优化问题得到 $\pi$，然后再把这个 $\pi$ 代入到式子中去。
下面我们化简上面的贝尔曼最优公式：
$$ v(s)= max_{\pi} \sum_{a}{\pi}(a|s)(\sum_r p(r|s,a)r + \gamma \sum_{s’}p(s’|s,a)v(s’)),\quad \forall s \in S $$
$$ =max_{\pi} \sum_{a} {\pi}(a|s)q(s,a) \quad s\in S $$
其中，$p(r|s,a)$、$p(s’|s,a)$ 是已知的；$v(s)$、$v(s’)$ 是未知的，需要计算得出。
考虑：$\pi(s)$ 是否已知？
注意：对于贝尔曼公式来说，策略 $\pi$ 一定是给定的，而对贝尔曼最优公式来说，$\pi$ 没有给定，我们必须要去求解这个 $\pi$
下面我们给出贝尔曼最优公式的矩阵形式：
$$ v=max_{ \pi } (r_{\pi} + \gamma P_{\pi}v) $$
这里我们可能要考虑到很多问题：
- 如何求出这个公式的解？
- 这个公式的解是否存在？
- 这个公式的解是否唯一？
- 它和 optimal policy 之间有什么联系？
别担心，我们下面会一一解决这些问题。
3.2 基本性质分析
BOE (Elementwise form)：
$$v(s)= max_{\pi} \sum_{a}{\pi}(a|s)(\sum_r p(r|s,a)r + \gamma \sum_{s’}p(s’|s,a)v(s’)),\quad \forall s \in S$$
BOE (matrix-vector form)：
$$v=max_{\pi} (r_{\pi} + \gamma P_{\pi}v)$$
在矩阵形式的数学表达式中，$v$ 和策略 $\pi$ 均为未知量，相当于我们只有一个式子但需要求解两个未知量。那么我们如何求解这样的问题呢？
我们先来看一个例子：
考虑两个未知量 $x,a\in \R$，设它们满足：
$$x={max}_a(2x-1-a^2)$$
那么在这个式子中，只有当 $a=0$ 时，式子才能取得最大值。
而当 $a=0$ 的时候，上式就变成了：
$$x=2x-1$$
解得x=1。因此，$a=0$ 且 $x=1$ 是这个式子的解。
上面这个例子的思路其实可以放在我们求解贝尔曼最优公式的过程当中。
我们下面来看一看。
$$ v(s)= max_{\pi} \sum_{a}{\pi}(a|s)(\sum_r p(r|s,a)r + \gamma \sum_{s’}p(s’|s,a)v(s’)),\quad \forall s \in S $$
$$ =max_{\pi} \sum_{a} {\pi}(a|s)q(s,a) \quad s\in S $$
解决思路：先给 $v’(s)$ 一个初始值，然后解出策略 $\pi$。
这里我们先考虑一种简单的情况。
假设 $q_1, q_2, q_3 \in \R$ 是已知的，我们需要找到 $c_1^*, c_2^*, c_3^*$ 来解决下面这个式子：
$$ max_{c_1, c_2, c_3}c_1 q_1 + c_2 q_2 + c_3 q_3$$
其中 $c_1 + c_2 + c_3 = 1$ 且 $c_1, c_2, c_3 \ge 0$
我们现在假设 $q_3 \ge q_1, q_2$。 那么这时候，最优的解就是 $c_3^*=1$ 且 $c_1^*=c_2^*=0$。因为对任意 $c_1 + c_2 + c_3$，有
$$q_3=(c_1 + c_2 + c_3)q_3=c_1 q_3 + c_2 q_3 + c_3 q_3 \ge c_1 q_1 + c_2 q_2 + c_3 q_3$$
由此可知：当右侧 $q$ 值确定的时候，那么右侧最大值就等于最大的那个 $q$ 值
由上面这个例子，我们现在考虑 $\sum_a \pi (a|s)=1$，这时我们有：
$$ max_{\pi} \sum_a \pi (a|s)q(s,a) = max_{a\in A(s)} q(s,a) $$
其中，当
$$ {\pi}(a|s)= \left\{ \begin{matrix} 1 \quad a=a^* \\ 0 \quad a\neq a^* \end{matrix}\right. $$
时取得最优值，其中 $a^*=argmax_a q(s,a)$
到这里，我们已经介绍来如何去处理右边的 $max_\pi$ ，实际上我们可以把它写成一个函数 $f(v)$，如下所示：
$$ f(v)=max_{\pi}(r_{\pi}+\gamma P_{\pi}v)$$
然后，贝尔曼最优公式就可以写成
$$ v= f(v)$$
$$[f(v)]s = max{\pi} \sum _a {\pi} (a|s) q(s,a),\quad s \in S$$
那么接下来，我们该如何求解这个等式呢？
在我们求解这个式子之前，我们先介绍一个好东西：压缩映射定理。在后面我们会用到。
3.3 压缩映射定理
在介绍压缩映射定理之前，我们首先需要引入两个概念。
不动点
如果
$$f(x)=x$$
我们称 $x\in X$ 是 $f:X\rightarrow X$的不动点。
（即无论如何映射，x位置都不动）
压缩映射
如果
$$||f(x_1)-f(x_2)||\le \gamma ||x_1-x_2||$$
其中 $\gamma \in (0, 1)$那么我们称 $f$ 是一个压缩映射。
- $\gamma$ 必须小于1,从而保证 $\gamma^k \rightarrow 0$等条件
- 这里的 ||…|| 可以是任何向量的模
有了上面介绍的两个概念，我们就可以引出压缩映射定理了。
（ps：这个定理非常强大，大家除了在强化学习中会用到之外，其实在其他很多领域里，如果你要求解类似与 $x=f(x)$ 这样的一个式子的话，都能用得上。）
压缩映射定理
对于任意一个类似于 $x=f(x)$ 的等式，如果 $f$ 是一个压缩映射，那么有：
- 存在一个不动点 $x^*$ 满足 $f(x^*)=x^*$
- 这个不动点 $x^*$ 是唯一的
- 考虑序列 ${x_k}$，其中 $x_{k+1}=f(x_k)$。那么当 $k \rightarrow \infty$ 时有 $x_k \rightarrow x^*$。值得一提的是，这时候的收敛速度非常快快，呈指数收敛。
下面我们通过一个简单的例子来理解这个定理。
给出 $x=0.5x$ ，其中 $f(x)=0.5x$ 且 $x \in \R$。$x^*=0$ 是唯一的不动点。这个问题还可以用下式解决：
$$ x_{k+1}=0.5x_{k}$$
现在我们已经介绍了压缩映射定理，那么我们回到最初的问题：如何求解贝尔曼最优公式？这个时候我们就可以利用压缩映射定理来解决这个问题了。
我们令贝尔曼最优公式的表达式 $v=f(v)$，则有
$$v=f(v)=max_{\pi}(r_{\pi}+\gamma P_{\pi}v)$$
为了在这里用上压缩映射定理，我们首先需要证明 $f(v)$ 是一个压缩映射（证明过程略，感兴趣的可以自行查找资料）。
我们现在已知 $f$ 是一个压缩映射，那么贝尔曼最优公式就立刻可以用压缩映射定理求解出来。
这里我们有几个结论：
- 第一个就是我们知道贝尔曼最优公式它一定是存在一个解的，这个解用 $v^*$ 来表示。
- 这个解 $v^*$ 是唯一的。
- 这个解可以通过迭代算法来求解出来
3.4 贝尔曼最优公式解的最优性
假设 $v^*$ 是贝尔曼最优公式的解，它满足
$$ v^*=max_{\pi}(r_{\pi}+\gamma P_{\pi} v^*)$$
假设
$$ {\pi}^*=argmax_{\pi}(r_{\pi}+\gamma P_{\pi} v^*)$$
于是
$$ v^*=r_{\pi ^*} + \gamma P_{\pi ^*} v^*$$
因此，$\pi ^*$ 是一个策略且 $v^*=v_{\pi ^*}$ 是对应的状态价值。
那么这里的 $\pi ^*$ 长什么样子呢？如下所示：
对于任意 $s \in S$，那么已确定的贪心策略
$$ {\pi ^*}(a|s)= \left\{ \begin{matrix} 1 \quad a=a^*(s) \\ 0 \quad a\neq a^*(s)\end{matrix}\right. $$就是贝尔曼最优公式的最优策略。这里
$$a^*(s)=argmax_a q^*(a,s)$$
其中
$$q^*(s,a)=\sum_r p(r|s,a)r+\gamma \sum_{s’} p(s’|s,a)v^*(s’)$$