提示：本章涉及一些定理等先验知识，故建议读者可以观看原视频，该篇不作任何的数学证明。

系列文章

1. 强化学习-基本概念
2. 强化学习-贝尔曼公式
3. 强化学习-贝尔曼最优公式

前沿

  本章核心：1️⃣ 核心概念：optimal state value 和 optimal policy；2️⃣ 基础工具：贝尔曼最优公式Bellman optimality equation, BOE。本文目的：熟悉概念、掌握贝尔曼最优公式的数学原理以及学会求解贝尔曼最优公式。

一、最优策略(optimal policy)

1.1 什么是optimal policy？

  最优策略(optimal policy)的定义如下：

  A policy ${\pi }^{\ast }$ is optimal if $v_{{\pi }^{\ast }}(s)\ge v_{\pi }(s)$ for all $s$ and for any other policy $\pi$.

 上述的意思是：如果对任意其他策略 $\pi$，对于所有状态 $s$ 都有 $v_{{\pi }^{\ast }}(s)\ge v_{\pi }(s)$，那么策略 ${\pi }^{\ast }$ 就是最优的。

由此产生的问题：

1. optimal policy是否存在？
 存在，依据是：contraction mapping Theorem

2. optimal policy是否唯一？

 唯一，依据是：contraction mapping Theorem

3. optimal policy是确定性的还是随机性的？

 确定性的

4. 如何得到optimal policy？

 选取状态中最大的action value 作为下一步的 action

二、贝尔曼最优公式(Bellman optimality equation, BOE)

2.1 贝尔曼最优公式

  通过字面意思便可知：贝尔曼最优公式是上一章节中贝尔曼公式的特殊情况，其数学表达式如下：

• elementwise form:
  $$\begin{array}{rl}{v}_{\pi }(s)& =\underset{\pi }{\max }\underset{a}{\Sigma }\pi (a|s)(\underset{r}{\Sigma }p(r|s,a)r+\gamma \underset{s^{\prime }}{\Sigma }p(s^{\prime }|s,a)v_{\pi }(s^{\prime })),{\forall }_s\in S\\ & =\underset{\pi }{\max }\Sigma \pi (a|s)q(s,a),{\forall }_s\in S\end{array}$$
• matrix-vector form:
  $$\begin{array}{r}v=\underset{\pi }{\max }(r_{\pi }+\gamma P_{\pi }v)\end{array}$$

2.2 如何求解贝尔曼最优公式？

2.2.1 求解贝尔曼最优公式前置知识

1. 如何从一个等式中求解2个未知量？(如何处理等式右边的 $ma{x}_{\pi }$)
   
     一个例子：$x=\underset{a}{\max }(2x-1-a^2)$，要想求解该等式，我们可以将得出上述等式的右侧可写为：$\underset{a}{\max }(2x-1-a^2)=\underset{a}{\max }(2x-1{)}^2$，随后可得当$a=0$时等式最大，因此，对于可求得原等式的值为：$a=0、x=1$。
   
     同理，：$v_{\pi }(s)=\underset{\pi }{\max }\Sigma \pi (a|s)q(s,a)$ 为了使右边等式取得最大值，只需要在当前的状态下选取最大的action value即可，对应策略$\pi$的表示如下：
   $$\pi =\{\begin{array}{r}1a=a^{\ast }\\ 0a\ne a^{\ast }\end{array}$$
     这里$a^{\ast }$表示在该状态下计算出来的最大的action value对应的动作，即 $a^{\ast }=argma{x}_{a}q(s|a)$。
   
2. Contraction mapping theorem
     1️⃣ fixed point： 如果对于一个函数映射关系$f:X\to X$ 有 $f(x)=x,(x\in X)$ ，则$x$是一个不动点；
     2️⃣ contraction mapping (or contraction function)： 如果函数$f$满足$\Vert f(x_1)-f(x_2)\Vert ⩽\gamma \Vert x_1-x_2\Vert ,\gamma \in (0,1)$，那么函数$f$是contraction mapping。
     3️⃣ contraction mapping的性质：
   • Existence： 存在不动点$x^{\ast }$，满足$f(x^{\ast })=x^{\ast }$；
   • Uniqueness： 不动点$x^{\ast }$是唯一的；
   • Algorithm： Consider a sequence { x k } \{x_k\} {xk​} where $x_{k+1}=f(x_k)$, then $x_k\to x^{\ast }$ as $k\to \infty$. Moreover, the convergence rate is exponentially fast.

2.2.2 求解贝尔曼最优公式

  BOE表达式：$v=ma{x}_{\pi }(r_{\pi }+\gamma P_{\pi }v)$，可改写为$f(v):=\underset{a}{\max }(r_{\pi }+\gamma P_{\pi }v)$，然后，贝尔曼最优公式变为：$v=f(v)$。因此，可以通过Contraction Mapping Theorem来求解贝尔曼最优公式，因为其满足该理论，即$f(v)$是一个contraction mapping【证明过程感兴趣的可以查阅该作者的书籍，这里不再进行证明】。

小结及参考资料

• 小结

贝尔曼最优公式的两种表达方式如下：

• elementwise form: $v_{\pi }(s)=\underset{\pi }{m}ax\underset{a}{\Sigma }\pi (a|s)(\underset{r}{\Sigma }p(r|s,a)r+\gamma \underset{s^{\prime }}{\Sigma }p(s^{\prime }|s,a)v_{\pi }(s^{\prime })),{\forall }_s\in S$
• matrix-vector form: $v=\underset{\pi }{\max }(r_{\pi }+\gamma P_{\pi }v)$

以上就是今天要讲的内容，本文仅仅对贝尔曼最优公式做了简单的梳理，强烈推荐大家去看原视频进行细节的理解。

• 参考资料
  1、贝尔曼公式视频讲解