《强化学习数学原理》学习笔记7——从贝尔曼最优方程得到最优策略 - 教程

下面求解贝尔曼最优方程，从而得到最优状态价值$v^{\ast }$ 和最优策略 ${\pi }^{\ast }$。

一、求解最优状态价值$v^{\ast }$

若 $v^{\ast }$是贝尔曼最优方程的解，那么它满足：
$$v^{\ast }=\underset{\pi \in \Pi }{\max }(r_{\pi }+\gamma P_{\pi }{v}^{\ast })\text{\hspace{1em}(1)}$$
显然，$v^{\ast }$是一个不动点，源于$v^{\ast }=f(v^{\ast })$（这里 $f(v)={\max }_{\pi \in \Pi }(r_{\pi }+\gamma P_{\pi }v)$）。结合压缩映射定理，大家有以下结论。

存在性、唯一性与算法：对于贝尔曼最优方程$v=f(v)={\max }_{\pi \in \Pi }(r_{\pi }+\gamma P_{\pi }v)$，始终存在唯一的解$v^{\ast }$，可以通过迭代法求解：
$$v_{k+1}=f(v_k)=\underset{\pi \in \Pi }{\max }(r_{\pi }+\gamma P_{\pi }{v}_k),k=0,1,2,\dots \text{\hspace{1em}(2)}$$
对于任意初始给定的$v_0$，当 $k\to \infty$ 时，$v_k$会以指数速度快速收敛到$v^{\ast }$。

由于 $f(v)$是压缩映射，该定理的证明可直接由压缩映射定理得到。这个定理很核心，因为它回答了一些基本问题：

• $v^{\ast }$ 的存在性：贝尔曼最优方程的解始终存在。
• $v^{\ast }$ 的唯一性：贝尔曼最优方程的解$v^{\ast }$始终是唯一的。
• 求解 $v^{\ast }$ 的算法：$v^{\ast }$可以通过式（2）给出的迭代算法求解。此种迭代算法有一个特定的名称，叫做值迭代。

二、求解最优策略${\pi }^{\ast }$

一旦得到 $v^{\ast }$的值，我们可以通过求解下式轻松得到${\pi }^{\ast }$：
$${\pi }^{\ast }=\arg \underset{\pi \in \Pi }{\max }(r_{\pi }+\gamma P_{\pi }{v}^{\ast })\text{\hspace{1em}(3)}$$
将式（3）代入贝尔曼最优方程可得：
$$v^{\ast }=r_{{\pi }^{\ast }}+\gamma P_{{\pi }^{\ast }}{v}^{\ast }\text{\hspace{1em}(4)}$$
因此，$v^{\ast }=v_{{\pi }^{\ast }}$ 是 ${\pi }^{\ast }$的状态价值，且贝尔曼最优方程是一个特殊的贝尔曼方程，其对应的策略是${\pi }^{\ast }$。

此时，尽管我们可以求解$v^{\ast }$ 和 ${\pi }^{\ast }$，但仍不清楚这个解是否是最优的。下面的定理揭示了解的最优性。

$v^{\ast }$ 和 ${\pi }^{\ast }$ 的最优性：解 $v^{\ast }$是最优状态价值，${\pi }^{\ast }$是最优策略。即，对于任意策略$\pi$，有
$$v^{\ast }=v_{{\pi }^{\ast }}\ge v_{\pi }\text{\hspace{1em}(5)}$$
其中 $v_{\pi }$ 是 $\pi$的状态价值，$\ge$是按元素比较。上述定理的证明如下：

对于任意策略$\pi$，有
$$v_{\pi }=r_{\pi }+\gamma P_{\pi }{v}_{\pi }\text{\hspace{1em}(6)}$$
因为
$$v^{\ast }=\underset{\pi }{\max }(r_{\pi }+\gamma P_{\pi }{v}^{\ast })=r_{{\pi }^{\ast }}+\gamma P_{{\pi }^{\ast }}{v}^{\ast }\ge r_{\pi }+\gamma P_{\pi }{v}^{\ast }\text{\hspace{1em}(7)}$$
所以我们有
$$v^{\ast }-v_{\pi }\ge (r_{\pi }+\gamma P_{\pi }{v}^{\ast })-(r_{\pi }+\gamma P_{\pi }{v}_{\pi })=\gamma P_{\pi }(v^{\ast }-v_{\pi })\text{\hspace{1em}(8)}$$
重复应用上述不等式可得$v^{\ast }-v_{\pi }\ge \gamma P_{\pi }(v^{\ast }-v_{\pi })\ge {\gamma }^2{P}_{\pi }^2(v^{\ast }-v_{\pi })\ge \cdots \ge {\gamma }^n{P}_{\pi }^n(v^{\ast }-v_{\pi })$。由此可得
$$v^{\ast }-v_{\pi }\ge \underset{n\to \infty }{\lim }{\gamma }^n{P}_{\pi }^n(v^{\ast }-v_{\pi })=0\text{\hspace{1em}(9)}$$
因为就是最后一个等式成立$\gamma <1$，且 $P_{\pi }^n$是一个非负矩阵，其所有元素都小于或等于 1（因为$P_{\pi }^{n}1=1$）。因此，对于任意$\pi$，有 $v^{\ast }\ge v_{\pi }$。

接下来，我们更仔细地研究式（3）中的${\pi }^{\ast }$。具体来说，下面的定理表明，始终存在一个确定性的贪婪策略是最优的。

贪婪最优策略证明

贪婪最优策略：假设 $v^{\ast }$是贝尔曼最优方程的最优状态值解。对于任意$s\in \mathcal{S}$，确定性贪婪策略
$${\pi }^{\ast }(a|s)=\{\begin{array}{ll}1,& a=a^{\ast }(s)\\ 0,& a\ne a^{\ast }(s)\end{array}\text{\hspace{1em}(10)}$$
是求解贝尔曼最优方程的最优策略。这里，
$$a^{\ast }(s)=\arg \underset{a}{\max }{q}^{\ast }(a,s)\text{\hspace{1em}(11)}$$
其中
$$q^{\ast }(s,a)\triangleq \sum _{r\in \mathcal{R}}p(r|s,a)r+\gamma \sum _{s^{\prime }\in \mathcal{S}}p(s^{\prime }|s,a)v^{\ast }(s^{\prime })\text{\hspace{1em}(12)}$$
证明如下：
最优策略的矩阵 - 向量形式是${\pi }^{\ast }=\arg {\max }_{\pi }(r_{\pi }+\gamma P_{\pi }{v}^{\ast })$，其元素展开形式为
$${\pi }^{\ast }(s)=\arg \underset{\pi \in \Pi }{\max }\sum _{a\in \mathcal{A}}\pi (a|s)\underset{q^{\ast }(s,a)}{\underbrace{\left(\sum _{r\in \mathcal{R}}p(r|s,a)r+\gamma \sum _{s^{\prime }\in \mathcal{S}}p(s^{\prime }|s,a)v^{\ast }(s^{\prime })\right)}},s\in \mathcal{S}\text{\hspace{1em}(13)}$$
显然，如果 $\pi (s)$选择具有最大$q^{\ast }(s,a)$的动作，那么${\sum }_{a\in \mathcal{A}}\pi (a|s)q^{\ast }(s,a)$会被最大化。

式（10）中的策略被称为贪婪策略，缘于它选择具有最大$q^{\ast }(s,a)$的动作，它指出总是存在一个确定性的贪婪策略是最优的。最终，大家讨论${\pi }^{\ast }$的两个要紧性质：

• 最优策略的唯一性：尽管 $v^{\ast }$的值是唯一的，但与$v^{\ast }$对应的最优策略可能不唯一。
• 最优策略的随机性：最优策略许可是随机的或确定性的。然而，肯定始终存在一个确定性的最优策略。