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

3.4 从BOE中求解最优策略¶

通过上一节的准备，我们已经准备好求解BOE以获得最优状态值\(v^*\)和最优策略\(\pi^*\)。

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

显然，\(v^*\)是一个不动点，因为\(v^*=f(v^*)\)。然后，压缩映射定理给出了以下结果。

Note

定理3.3. (存在性、唯一性和算法)。对于BOE，\(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\)的情况下，\(v_k\)的值随着\(k\rightarrow \infty\)以指数速度收敛到\(v^*\)。

这个定理的证明直接从压缩映射定理得出，因为\(f(v)\)是压缩映射。这个定理很重要，因为它回答了一些基本问题。

\(v^*\)的存在性: BOE的解总是存在的。
\(v^*\)的唯一性: 解\(v^*\)总是唯一的。
求解\(v^*\)的算法: 可以通过定理\(3.3\)建议的迭代算法来求解\(v^*\)的值。这种迭代算法有一个特定的名称，称为值迭代(value iteration)。第四章将详细介绍其实现。在本章中，我们主要关注BOE的基本性质。

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

定理\(3.5\)中给出了\(\pi^*\)的值。将公式\(3.6\)代入BOE，

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

因此，\(v^*=v_{\pi^*}\)是\(\pi^*\)的状态值，BOE是一个特殊的贝尔曼公式，其对应的策略是\(\pi^*\)。

此时，虽然我们可以求解\(v^*\)和\(\pi^*\)，但仍不清楚该解是否为最优解。而下面的定理揭示了解的最优性。

Note

定理\(3.4\)(\(v^*\)和\(\pi^*\)的最优性),解\(v^*\)是最优状态值，\(\pi^*\)是最优策略。也就是说，对于任何策略\(\pi\)，有

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

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

现在，我们清楚了为什么必须研究BOE：它的解对应于最优状态值和最优策略。上述定理的证明在下面的方框中给出。

接下来，我们来仔细地研究\((3.6)\)中的\(\pi^*\)。特别是，以下定理表明，总存在一种确定性的Greedy策略，它是最优的。

Note

定理3.5(Greedy最优策略). 对于任意状态\(s\in \mathcal{S}\)，确定性Greedy策略

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

是解决BOE问题的最优策略。在此，

\[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.7)\)中的策略是Greedy的，因为它寻求具有最大\(q^*(s, a)\)的动作。最后，我们讨论\(\pi^*\)的两个重要性质。

最优策略的唯一性：尽管\(v^*\)的值是唯一的，但与\(v^*\)对应的最优策略却可能不唯一。这一点可以通过反例很容易地验证。例如，图\(3.3\)中所示的两种策略都是最优的。
最优策略的随机性：如图\(3.3\)所示，最优策略可以是随机的，也可以是确定的。然而，根据定理\(3.5\)，可以确定的是，总是存在一个确定性的最优策略。

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