跳转至

3.3-贝尔曼最优公式

Note

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

为了分析和求解最优策略，下面将介绍贝尔曼最优公式 (Bellman optimality equation, BOE)。首先直接给出其表达式，然后详细分析它的性质。

对于每个\(s\in\mathcal{S}\)，贝尔曼最优方程的表达式为：

\[\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}\]

其中，

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

这里\(v(s),v(s^\prime)\)是待求解的未知变量，\(\pi(s)\)表示状态\(s\)的策略，而\(\Pi(s)\)是状态\(s\)所有可能策略的集合。

贝尔曼最优方程是一个优雅且强大的工具，它能清晰地解释许多基础且重要的问题。然而要理解这个方程可能并非易事。例如，这个方程有两个未知变量：一类是值\(v(s)\)，另一类是策略\(\pi(a|s)\)。如何从一个方程中同时求解两类未知量呢？此外，下面这些问题也需要回答：

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

此外，贝尔曼最优方程与贝尔曼最优方程是什么关系？为什么说它是一个特殊的贝尔曼方程？这些问题都是很重要的。如果我们能够回答这些问题，我们就能清楚地理解最优状态值和最优策略。

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)\]

贝尔曼最优方程的右侧嵌套了一个优化问题，初学者可能会对此感到迷惑。我们通过以下的例子来解释其求解思路。

Note

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

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

这个方程可以通过两步求解。第一步是求解方程右边的优化问题\(\max_{y\in\mathbb{R}}(2x-1-y^{2})\)。具体来说，不管\(x\)的值是什么，在\(y=0\)时\((2x − 1 − y^2)\)达到最大值，此时\(\max_y(2x-1-y^2)=2x-1\)。第二步是求解\(x\)，当\(y = 0\)时，此时方程变为\(x = 2x − 1\)，此时很容易求解出\(x = 1\)。因此，\(y = 0\)和\(x = 1\)是该方程的解。

明白了上面这个例子，我们再来看贝尔曼最优方程：式\((3.1)\)可以简写为：

\[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给定\(q_1,q_2,q_3\in\mathbb{R}\)，我们希望找到\(c_1，c_2，c_3\)的最优值，从而求解下面的优化问题：

\[\max_{c_1,c_2,c_3}\sum_{i=1}^3 c_iq_i=\max_{c_1,c_2,c_3}(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.1)就变成了\(v(s)=\max_{a\in\mathcal{A}(s)}q(s,a)\)。

3.3.2 矩阵-向量形式

方程\((3.1)\)是对任意状态都成立的，将所有这些方程联立起来，就可以得到一个简洁的矩阵-向量形式，该形式在本章中将被广泛的应用，对于分析贝尔曼最优方程将发挥重要作用。

具体来说，假设有\(n\)个状态\(\{s_1,s_2,\ldots,s_n\}\)。类似于第2章推导贝尔曼方程的矩阵-向量形式，我们可以得到贝尔曼最优方程的矩阵-向量形式为：

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

其中\(v\in R^{n}\)是待求解的未知量。上式中的\(max_\pi\)以逐元素的方式执行的。例如，对于一个向量\([*,*]\)，其中的元素我们用"\(*\)"表示，那么\(\max_\pi[*,*]=[\max_\pi *,\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)\)表示为：

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

然后，贝尔曼最优方程\((3.2)\)可以更简洁地表示：

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

在本节的剩余部分，我们将展示如何求解这个方程\((3.3)\)。

3.3.3 压缩映射定理

为了分析\(v=f(v)\)，我们接下来介绍压缩映射定理6。压缩映射定理是分析非线性方程的强大工具。它也被称为不动点定理。建议读者仔细学习该定理，因为它是分析贝尔曼最优方程的关键工具。

考虑一个函数\(f(x)\)，其中\(x\in \mathbb{R}^d\)且\(f:\mathbb{R}^d \rightarrow \mathbb{R}^d\)。如果一个点\(x^*\)满足：

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

那么称之为不动点 (fixed point)。之所以被称为“不动点”，是因为\(x^*\)的映射还是其自身。

如果存在\(\gamma \in(0，1)\)，使得：

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

对于任意\(x_1,x_2\in\mathbb{R}^d\)都成立，那么函数\(f\)被称为压缩映射 (contraction mapping)。上面不等式中的\(\|·\|\)表示向量或矩阵的范数。

下面我们给出三个例子来解释不动点和压缩映射。

Note

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

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

    首先，很容易验证\(x = 0\)是一个不动点，因为\(0 = 0.5 · 0\)。其次，\(f(x)=0.5x\)是一个压缩映射，因为对任何\(\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\)。其次，\(f(x)=Ax\)是一个压缩映射,因为\(\|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\)。且收敛过程有指数收敛速度。

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

下面的例子展示了如何使用压缩映射定理给出的迭代算法来求解方程。

Note

例子3.4. 再次考虑前面提到的三个简单例子：\(x = 0.5x，x = Ax，x = 0.5 \sin x\)。前面我们已经知道\(x^* = 0\)是一个不动点。并且方程右边的函数都是压缩映射。现在根据压缩映射定理，我们知道这个不动点\(x^* = 0\)是唯一的解，因为这三个方程很简单，所以可以用很多方式求解得到\(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\)可以是任意值。例如，考虑算法\(x_{k+1}=0.5x_k\)，如果初始值是\(x_0=10\)，那么可得\(x_1=5,x_2=2.5,x_3=1.25,x_4=0.625,...\)。可以看到，\(x_k\)会逐渐接近真实解\(x^*=0\)。

3.3.4 方程右侧函数的压缩性质

下面我们将证明贝尔曼最优方程\((3.3)\)中右侧函数\(f(v)\)是一个压缩映射。之后就可以利用前一小节介绍的压缩映射定理来分析该方程。

Note

定理3.2. (\(f(v)\)的压缩性质)。贝尔曼最优方程公式\(3.3\)右侧的函数\(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\)中给出。这个定理很重要，因为我们可以使用压缩映射定理来分析贝尔曼最优方程。

评论