3.4-从贝尔曼最优公式中求解最优策略

有了前面的充分准备，下面我们来求解贝尔曼最优方程，从而得到最优状态值\(v^*\)和最优策略\(\pi^*\)。

\[v^* = f(v^*)=\max_{\pi \in \Pi} \left( r_{\pi} + \gamma P_{\pi} v^* \right). \]

显然，\(v^*\)是一个不动点，根据压缩映射定理有以下重要结论。

Note

定理3.3. (存在性、唯一性和算法)。贝尔曼最优方程\(v = f(v)= max_{\pi \in \Pi}(r_\pi + \gamma P_\pi v)\)始终存在唯一的解\(v^*\)，该解可以通过迭代算法求解：

\[v_{k+1} = f(v_k) = \max_{\pi \in \Pi} \left( r_{\pi} + \gamma P_{\pi} v_k \right), \quad k = 0, 1, 2, \dots.\]

对任意给定的\(v_0\)，当\(k\rightarrow\infty\)时，\(v_k\)以指数速度收敛到\(v^*\)。

因为\(f(v)\)是压缩映射，所以上面的定理可以直接由压缩映射定理得到。上面定理很重要，因为它能回答一系列重要的基本问题。

\(v^*\)的存在性: 贝尔曼最优方程的解总是存在的。
\(v^*\)的唯一性: 贝尔曼最优方程的解总是唯一的。
算法: 贝尔曼最优方程可以通过定理\(3.3\)中的迭代算法来求解。此迭代算法有一个特定的名称-值迭代 (value iteration)。该算法的具体实施步骤将在第4章中详细介绍，本章主要关注贝尔曼最优方程的基本性质。
求解最优策略\(\pi^*\): 一旦得到了\(v^*\)的值，就可以通过下式求解得到一个最优策略：

\[\pi^* = \arg \max_{\pi \in \Pi} \left( r_{\pi} + \gamma P_{\pi} v^* \right).\tag{3.6}\]

\(\pi^*\)的具体形式将在定理\(3.5\)中给出。将公式\((3.6)\)代入贝尔曼最优方程可得：

\[v^* = r_{\pi^*} + \gamma P_{\pi^*} v^*.\]

因此，\(v^*=v_{\pi^*}\)是\(\pi^*\)的状态值。从上式可以看出，贝尔曼最优方程是一个特殊的贝尔曼方程，其对应的策略是\(\pi^*\)。

虽然我们上面提到\(v^*\)是最优值、\(\pi^*\)是最优策略，但是仍然没有证明它们的最优性，只是说明了\(v^*\)和\(\pi^*\)是贝尔曼最优方程的解而已。下面的定理证明了贝尔曼最优方程的解的最优性。

Note

定理\(3.4\)(\(v^*\)和\(\pi^*\)的最优性),如果\(v^*\)和\(\pi^*\)是贝尔曼最优方程的解。那么\(v^*\)是最优状态值，\(\pi^*\)是最优策略，即对于任何策略\(\pi\)都有：

\[v^*=v_{\pi^*}\geq v_\pi,\]

其中\(v_\pi\)是策略\(\pi\)的状态值，\(\geq\)是逐元素比较。

上面这个定理非常重要，正因为贝尔曼最优方程的解具有最优性，所以才需要学习它，关于它的具体证明将在Box\(3.3\)中给出，感兴趣的读者可以阅读。

虽然上面反复提到了最优策略\(\pi^*\)，但是它是随机性策略还是确定性策略呢？下面定理回答了这个问题。

Note

定理3.5(贪婪最优策略). 假设\(v^*\)是贝尔曼最优方程的最优状态值解，那么下面的确定性贪婪策略是一个最优策略

\[\pi^*(a|s) = \begin{cases}1, & \text{if } a = a^*(s), \\0, & \text{if } a \neq a^*(s).\end{cases},s\in\mathcal{S},\tag{3.7}\]

其中

\[a^*(s) = \arg \max_a q^*(s, a).\]

且

\[q^*(s,a) = \sum_{r \in \mathcal{R}} p(r|s, a) r + \gamma \sum_{s' \in \mathcal{S}} p(s'|s, a) v^*(s').\]

定理\(3.5\)指出总是存在一个确定性的贪婪策略是最优的。式\((3.7)\)中的策略之所以被称为贪婪，是因为它选了具有最大\(q^*(s, a)\)的行动。

最后，我们讨论\(\pi^*\)的两个重要性质。

最优策略的唯一性：尽管\(v^*\)的值是唯一的，但与\(v^*\)对应的最优策略可能并不唯一。这一点可以通过反例验证。例如，图\(3.3\)中所示的两种策略都是最优的。

图\(3.3\)：展示最优策略可能不唯一的示例。这两个策略不同，但都是最优的。

评论