跳转至

3.3-贝尔曼最优公式

3.3 贝尔曼最优公式

Note

这一节公式非常多，建议读者仔细阅读

用于分析最优策略和最优状态值的工具是贝尔曼最优公式(BOE)。通过求解该公式，可以获得最优策略和最优状态值。接下来我们给出了BOE的表达式，并对其进行了详细分析。

对于每个\(s\in\mathcal{S}\)，BOE的元素级表达式为

\[\begin{aligned} v(s) &= \max_{\pi \in \Pi(\mathcal{S})} \sum_{a \in A} \pi(a|s) \left( \sum_{r \in \mathcal{R}} p(r|s, a) r + \gamma \sum_{s' \in S} p(s'|s, a) v(s') \right) \\ &= \max_{\pi \in \Pi(\mathcal{S})} \sum_{a \in A} \pi(a|s) q(s, a), \end{aligned}\tag{3.1}\]

其中\(v(s),v(s^\prime)\)是待求解的未知变量，

\[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').\]

这里,\(π(s)\)表示状态\(s\)的策略，而\(\Pi(s)\)是\(s\)的所有可能策略的集合。

BOE是分析最优策略的一个优雅而强大的工具。然而，要理解这个方程可能并非易事。例如，这个方程有两个未知变量\(v(s)\)和\(\pi(a|s)\)的情况。对于初学者来说，如何从一个方程中解出两个未知变量可能会令人困惑。BOE实际上是一个特殊的贝尔曼公式。但由于其表达式与贝尔曼公式的表达式有很大的不同，因此要认识到这一点并不容易。我们还需要回答关于贝尔曼最优方程的以下基本问题。

  • 存在性：这个方程是否有解？
  • 唯一性：解是否唯一？
  • 算法：如何求解这个方程？
  • 最优性：解与最优策略有何关系？

一旦我们能够回答这些问题，我们就能清楚地理解最优状态值和最优策略。

3.3.1 方程右侧的优化问题

Note

贝尔曼最优公式的元素级表达式

\[v(s)=\max_{\pi}\sum_{a}\pi(a|s)\left(\sum_{r}p(r|s,a)r+\gamma\sum_{s^{\prime}}p(s^{\prime}|s,a)v(s^{\prime})\right),\quad\forall s\in\mathcal{S}\]

贝尔曼最优公式的矩阵向量形式

\[v=\max_\pi(r_\pi+\gamma P_\pi v)\]

接下来，我们将阐明如何解决公式\((3.1)\)中BOE右侧的优化问题。初看之下，初学者可能会对在一个方程中如何求解两个未知变量\(v(s)\)和\(π(a|s)\)感到困惑。实际上，这两个未知变量可以逐一求解。下面的例子说明了这个结论。

Note

例子3.1 考虑两个未知变量\(x,y\in\mathbb{R}\)，满足

\[x=\max_{y\in\mathbb{R}}(2x-1-y^{2}).\]

第一步是求解方程右边的\(y\)。不管\(x\)的值如何，我们总是有\(max_y(2x − 1 − y^2)= 2x − 1\)，其中当\(y = 0\)时达到最大值。第二步是解\(x\)。当\(y = 0\)时，方程变为\(x = 2x − 1\)，因此\(x = 1\)。因此，\(y = 0\)和\(x = 1\)是方程的解。

我们现在转向BOE右侧的优化问题。式\((3.1)\)中的BOE可以简明地写为：

\[v(s)=\max_{\pi(s)\in\Pi(s)}\sum_{a\in A}\pi(a|s)q(s,a),\quad s\in\mathcal{S}.\]

受例\(3.1\)的启发，我们可以首先在右侧求解最优\(\pi\)。如何求解呢?下面的例子展示了它的基本思想。

Note

例子3.2(如何来求解\(\max_\pi\sum_a \pi(a|s)q(s,a)\)) 给定\(q_1,q_2,q_3\in\mathbb{R}\)，我们希望找到\(c_1，c_2，c_3\)的最优值以最大化

\[\sum_{i=1}^3c_iq_i=c_1q_1+c_2q_2+c_3q_3,\]

在这里\(c_1+c_2+c_3=1\)，并且\(c_1,c_2,c_3\geq0\)

不失一般性，假设\(q3 \geq q1，q2\)。那么，最优解是\(c_3^*=1\)和\(c_1^* = c_2^* = 0\)。这是因为

\[q_3=(c_1+c_2+c_3)q_3=c_1q_3+c_2q_3+c_3q_3\geq c_1q_1+c_2q_2+c_3q_3\]

对于任意\(c_1,c_2,c_3\)

受上述例子的启发，因为\(\sum_a\pi(a|s)=1\)，我们有

\[\begin{aligned}\sum_{a\in\mathcal{A}}\pi(a|s)q(s,a)\leq\sum_{a\in\mathcal{A}}\pi(a|s)\max_{a\in\mathcal{A}}q(s,a)=\max_{a\in\mathcal{A}}q(s,a),\end{aligned}\]

当等式成立时有

\[\pi(a|s)=\left\{\begin{array}{ll}1,&a=a^*,\\0,&a\neq a^*.\end{array}\right.\]

这里，\(a^*=\text{arg max}_a q(s,a)\)。简而言之，最优策略\(\pi(s)\)是选择具有最大\(q(s,a)\)值的动作的策略。

3.3.2 BOE的矩阵向量形式

BOE是指为所有状态定义的一组方程。如果我们把这些方程联合起来，就可以得到一个简明的矩阵向量形式，这将在本章中得到广泛的应用。BOE的矩阵向量形式为：

\[v=\max_{\pi\in\Pi}(r_\pi+\gamma P_\pi v),\tag{3.2}\]

其中\(v\in R^{|S|}\)并且\(max_\pi\)以逐元素方式执行。\(r_\pi\)和\(P_\pi\)的结构与标准贝尔曼公式的矩阵向量形式相同：

\[[r_\pi]_s=\sum_{a\in\mathcal{A}}\pi(a|s)\sum_{r\in\mathcal{R}}p(r|s,a)r,\quad[P_\pi]_{s,s^{\prime}}=p(s^{\prime}|s)=\sum_{a\in\mathcal{A}}\pi(a|s)p(s^{\prime}|s,a).\]

由于\(\pi\)的最佳值由\(v\)决定，公式\((3.2)\)的右边是\(v\)的函数，表示为

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

那么，BOE可以用简洁的形式表示为：

\[v=f(v).\tag{3.3}\]

在本节的剩余部分，我们将展示如何求解这个非线性方程。

3.3.3 压缩映射定理

由于BOE可以表示为一个非线性方程\(v=f(v)\)，我们接下来引入压缩映射定理[6]来分析它，压缩映射定理是分析一般非线性方程的有力工具。它也被称为不动点定理。已经知道这个定理的读者可以跳过这一部分。否则，建议读者熟悉这个定理，因为它是分析BOE的关键。

考虑一个函数\(f(x)\)，其中\(x\in \mathbb{R}^d\)且\(f:\mathbb{R}^d \rightarrow \mathbb{R}^d\)。一个点\(x^*\)被称为不动点，如果有

\[f(x^*)=x^*\]

对上述方程的解释是，\(x\)的映射是它本身。这就是为什么\(x\)被称为“不动”的原因。函数\(f\)是压缩映射(或压缩函数)，如果存在\(\gamma \in(0，1)\)，使得

\[\|f(x_1)-f(x_2)\|\leq\gamma\|x_1-x_2\|\]

对于任意\(x_1,x_2\in\mathbb{R}^d\)。在这本书中，\(\|·\|\)表示向量或矩阵范数。

Note

例子3.3. 我们给出了三个例子来证明不动点和压缩映射.

  1. \(x=f(x)=0.5x,x\in\mathbb{R}\)

    很容易证明\(x = 0\)是一个不动点，因为\(0 = 0.5 · 0\)。此外，\(f(x)=x\)是一个压缩映射，因为对任何\(\gamma\in [0.5，1)\)，有\(\|0.5x_1-0.5x_2\|=0.5\|x_1-x_2\|\leq\gamma\|x_1-x_2\|\)。

  2. \(x = f(x)= Ax\)，其中\(x \in \mathbb{R}^n，A\in \mathbb{R}^{n\times n}\)且\(\|A\|\leq\gamma\leq1\).

    很容易证明\(x = 0\)是一个不动点，因为\(0 = A0\)。此外，它也是一个压缩映射,有\(\|Ax_1-Ax_2\|=\|A(x_1-x_2)\|\leq\|A\|\|x_1-x_2\|\leq\gamma\|x_1-x_2\|.\)。因此，\(f(x)=Ax\)是一个压缩映射。

  3. \(x = f(x) = 0.5 \sin x, \quad x \in \mathbb{R}\).

    很容易证明\(x=0\)是一个不动点，因为\(0=0.5\sin 0\)。此外，此外，从中值定理[7，8]可以得出：

    \[\left| \frac{0.5 \sin x_1 - 0.5 \sin x_2}{x_1 - x_2} \right| = |0.5 \cos x_3| \leq 0.5, \quad x_3 \in [x_1, x_2].\]

    因此在这里有\(|0.5 \sin x_1 - 0.5 \sin x_2| \leq 0.5 |x_1 - x_2|\)因此\(f(x) = 0.5 \sin x\)是一个压缩映射。

不动点和压缩性质之间的关系由以下定理展示。

Note

定理3.1(压缩映射定理)。对于任何形式为\(x = f(x)\)的方程，其中\(x\)和\(f(x)\)是真实的向量，如果\(f\)是压缩映射，则以下性质成立。

  • 存在性：存在一个不动点\(x^*\)满足\(f(x^*)= x^*\)。

  • 唯一性：不动点\(x^*\)是唯一的。

  • 算法：考虑迭代过程

\[x_{k+1}=f(x_k)\]

在这里\(k=0,1,2,\cdots\)，然后，对于任何初始值\(x_0\)，有\(x_k \rightarrow x^*, k \rightarrow \infty\)。此外，收敛速度呈指数级速度。

压缩映射定理不仅可以判断一个非线性方程的解是否存在，而且可以给出一个求解该方程的数值算法。该定理的证明在方框\(3.1\)中给出。

下面的例子演示了如何使用压缩映射定理建议的迭代算法计算某些方程的不动点。

Note

例子3.4. 让我们再看看上面的例子：\(x = 0.5x，x = Ax，x = 0.5 \sin x\)。虽然已经证明了这三个方程的右边都是压缩映射，但从压缩映射定理可以得出，它们每个都有一个唯一的不动点，可以很容易地验证为\(x = 0\)。此外，三个方程的不动点可以通过以下算法迭代求解：

\[\begin{aligned}&x_{k+1}=0.5x_{k},\\&x_{k+1}=Ax_{k},\\&x_{k+1}=0.5\sin x_{k},\end{aligned}\]

给定任何初始猜测值\(x_0\)。

3.3.4 BOE右侧函数的压缩性质

接下来我们将证明\((3.3)\)中BOE中的\(f(v)\)是一个压缩映射。因此，可以应用前一小节中介绍的压缩映射定理。

Note

定理3.2. (\(f(v)\)的压缩性质)。公式\(3.3\)中BOE右边的函数\(f(v)\)是一个压缩映射。特别地，对任意的\(v_1,v_2\in \mathbb{R}^{|\mathcal{S}|}\)，有：

\[\|f(v_1)-f(v_2)\|_\infty\leq\gamma\|v_1-v_2\|_\infty,\]

在这里\(\gamma\in(0,1)\)是折现率，\(\|·\|\)是最大范数，其是向量的元素的最大绝对值。

该定理的证明在方框\(3.2\)中给出。这个定理很重要，因为我们可以使用压缩映射定理来分析BOE。

Question