【强化学习系列】贝尔曼最优方程

接上一篇文章贝尔曼方程

定义

如果一个策略在所有状态下的状态价值都不低于其他任意策略在相同状态下的状态价值，即：对于所有的$s\in \mathcal{S}$，$v_{\pi }(s)\ge v_{{\pi }^{{}^{\prime }}}(s)$，那么这个策略$\pi$就是最优策略，最优策略可能不止一个，但统一记为${\pi }^{\ast }$。
定义最优价值函数：
$$v_{\ast }(s)\triangleq \underset{\pi }{\max }{v}_{\pi }(s)$$
$$q_{\ast }(s,a)\triangleq \underset{\pi }{\max }{q}_{\pi }(s,a)$$
而从最优策略的定义中也可以得出：
$$v_{\pi \ast }(s)\triangleq \underset{\pi }{\max }{v}_{\pi }(s)$$
$$q_{\pi \ast }(s,a)\triangleq \underset{\pi }{\max }{q}_{\pi }(s,a)$$
所以有：
$$v_{\pi \ast }(s)=v_{\ast }(s)=\underset{\pi }{\max }{v}_{\pi }(s)$$
$$q_{\ast }(s,a)=q_{\pi \ast }(s,a)=\underset{\pi }{\max }{q}_{\pi }(s,a)$$
解释一下$v_{\pi \ast }(s)和v_{\ast }(s)$的区别：
后者是从值函数的大小的角度做出的定义，与策略并没有太大关系，而前者则是在最优策略下的状态价值函数。
上面的结果说明：最优价值函数就是执行最优策略时的价值函数

推导

对于任何一个策略$\pi$都满足：
$$v_{\pi }(s)\le \underset{a}{\max }{q}_{\pi }(s,a)$$
这是因为
$$v_{\pi }(s)=\sum _{a\in \mathcal{A}}\pi (a|s)q_{\pi }(s,a)$$
状态价值函数是各个动作价值函数的加权平均，一定小于等于最大的动作价值。
对于最优策略${\pi }^{\ast }$，为了使状态价值函数达到最大，它在选择动作时一定是以概率1选择使动作价值最大的动作，而其他动作被选择的概率都是0，由于${\max }_a{q}_{\pi }(s,a)=q_{{\pi }^{\ast }}(s|a)$，结合上一个式子可以得到：
$$\begin{array}{c}{v}_{{\pi }^{\ast }}(s)=\underset{a}{\max }{q}_{{\pi }^{\ast }}(s,a)\end{array}$$
在上一篇文章中已经推出：
$$q_{\pi }(s,a)=\sum _{s^{\prime }\in S}\sum _{r\in R}p(s^{\prime },r|s,a)[r+\gamma v_{\pi }(s^{\prime })]$$
它对于最优策略${\pi }^{\ast }$也是成立的，所以有：
$$\begin{array}{c}{q}_{{\pi }^{\ast }}(s,a)=\sum _{s^{\prime }\in S}\sum _{r\in R}p(s^{\prime },r|s,a)[r+\gamma v_{{\pi }^{\ast }}(s^{\prime })]\end{array}$$
代入到公式（1）中可以得到：
$$v_{{\pi }^{\ast }}(s)=\underset{a}{\max }\sum _{s^{\prime }\in S}\sum _{r\in R}p(s^{\prime },r|s,a)[r+\gamma v_{{\pi }^{\ast }}(s^{\prime })]$$
上式就是贝尔曼最优方程。对于动作价值函数也可推导出类似的结果：
将公式(1)代入公式(2)中：
$$q_{{\pi }^{\ast }}(s,a)=\sum _{s^{\prime }\in S}\sum _{r\in R}p(s^{\prime },r|s,a)[r+\gamma \underset{a^{\prime }}{\max }{q}_{{\pi }^{\ast }}(s^{\prime },a^{\prime })]$$
当然这两个贝尔曼最优方程中$v_{{\pi }^{\ast }}$和$q_{{\pi }^{\ast }}$分别用$v_{\ast }$和$q_{\ast }$代替也是成立的，原因见定义。