三、最优状态价值与贝尔曼最优性方程

type

status

password

date

slug

summary

如何改进策略

考虑图 3.2 中所示的策略。在这里，橙色和蓝色单元格分别代表禁止区域和目标区域。这里的策略不好，因为它在状态选择了；如果策略在处选择，那么该策略可以得到改进。我们如何改进给定的策略以获得更好的策略呢？答案在于状态价值和动作价值。

💡

强化学习算法的基本思，选择具有最大动作价值的动作，从而获得更好的策略。

首先，我们计算给定策略的状态价值

设

计算状态的动作价值

注意，动作具有最大的动作价值。因此，我们可以更新策略，在处选择。

最优状态价值和最优策略

最优定义

最优策略和最优状态价值：这个定义是基于状态价值的。具体来说，考虑两个给定的策略和。如果对于任何状态，的状态价值都大于或等于的状态价值，那么就说比更好。因此，最优策略 就是，在所有的状态下，均优于其他所有的策略。最优策略对应的状态价值就是最优状态价值。

💡

上述定义表明，与所有其他策略相比，最优策略在每个状态下都具有最大的状态价值。

存在性：最优策略一定存在

唯一性：最优策略是唯一的

随机性：最优策略是确定的

算法：通过贝尔曼最优方程获得最优策略和最优状态价值？

贝尔曼最优方程

贝尔曼最优方程是与最优策略以及最优状态价值相对应的贝尔曼方程。当的时候

其中即为贝尔曼最优方程。接下来，将对贝尔曼最优方程进行详细的阐述。在其中，所代表的含义是：选取策略，以使得达到最大值。而在这种情况下，。并且，意味着同样也取得了最大值，此时。

Elementwise形式

对于每个，贝尔曼最优方程的表达式为

表示状态的一个策略，而是状态的所有可能策略的集合；其中，且。上述意味着当Policy取某一个最优化值时，State Value 可以取到最大值。

💡

通过调整策略获得每一个状态的最大状态价值。

矩阵形式

求解贝尔曼最优方程

💡

本质上是迭代计算贝尔曼最优方程

定理 3.3 保证了当时，和分别收敛于最优状态价值和最优策略。证明过程

通过求解贝尔曼最优方程中的和，即可得到最优策略和最优状态价值。

对于任意，当前的估计值是。

对于任意，计算

计算贪心策略，对于，有

更新状态价值

示例

随机初始化：

计算动作价值函数，并更新策略与状态价值。

贝尔曼最优方程求解

收缩映射定理(Contraction mapping theorem)

收缩函数：如果存在使得函数满足，其中；那么函数就是一个收缩函数。

就是一个压缩函数。因为，

性质：对于任意符合格式的方程，如果是收缩映射，那么：

存在性：存在一个不动点满足；
唯一性：这个不动点是唯一的；
算法：迭代式算法，最终可以收敛到不动点处；

总之，最优策略是选择具有最大动作价值的策略。

收缩映射定理的收敛证明（证明可以迭代到不动点）

先验知识：

柯西序列：一个序列，如果对于任意小的，存在一个整数，使得对于所有的，都有，那么这个序列被称为柯西序列。直观的解释是，存在一个有限整数，使得之后的所有元素都彼此足够接近。柯西序列很重要，因为可以保证一个柯西序列收敛到一个极限。它的收敛性质将被用于证明压缩映射定理。

💡

请注意，对于所有的，我们必须有。如果我们仅仅有，那么不足以声称这个序列是一个柯西序列。例如，对于，有，但显然，是发散的。

证明：接下来我们证明是一个柯西序列，因此它是收敛的。

首先，由于是一个压缩映射，我们有

同样，我们有，……，。因此，我们有

由于，我们知道对于任意的，，当时，呈指数级快速收敛于零。值得注意的是，的收敛并不足以表明序列收敛。因此，我们需要进一步考虑对于任意的。特别地。

因此，对于任何，我们总能找到，使得对于所有，都有。所以，这个序列是柯西序列，因此收敛到一个极限点，记为。

证明极限是一个不动点

由于，我们知道以指数速度快速收敛到零。因此，在极限情况下我们有。

证明这个不动点是唯一的

假设存在另一个不动点满足，那么

由于，当且仅当时，这个不等式成立。因此，。

证明以指数速度快速收敛到

回想一下，如在（3.4）中所证明的，。由于可以任意大，我们有。

上式中，由于，当时，误差以指数速度快速收敛到零。

贝尔曼最优方程是收缩映射

接下来我们证明（3.3）中的 BOE（Budgeted Online Ensemble）中的是一个收缩映射。因此，上一小节中介绍的压缩映射定理可以被应用。

💡

定理 3.2（的压缩性质）。在（3.5）中的是一个收缩映射。特别地，对于任意的，有以下结论成立。

其中是折扣率，是最大范数，即向量元素的最大绝对值。

证明

考虑任意两个向量，并且假设以及。那么

其中是逐元素比较。结果是

类似地，可以证明。因此。

定义

其中、和都是逐元素运算符。根据定义，。一方面，很容易看出。

这意味着。

由此可得。

其中是最大范数。

另一方面，假设是的第个元素，并且和分别是和的第行。那么

由于是一个所有元素均为非负的向量，并且元素之和等于一，所以可得。

类似地，我们有。因此，，所以。

将这个不等式代入（3.5）可得。

这就完成了对函数的压缩性质的证明。

求解贝尔曼方程原理

求解：如果是BOE的一个解，那么它满足。

显然，是一个不动点，因为。然后，收缩映射定理给出了以下结果。

💡

定理 3.3（存在性、唯一性和算法）。对于BOE方程，总是存在唯一解，它可以通过迭代求解。

对于任意初始猜测值，当时，的值以指数速度收敛于。

这个定理的证明直接源于压缩映射定理，因为是一个压缩映射。这个定理很重要，因为它回答了一些基本问题。

的存在性：最优贝尔曼方程（BOE）的解总是存在的。
：最优贝尔曼方程的解唯一性。
求解的算法：的值可以通过定理3.3提出的迭代算法来求解。这种迭代算法有一个特定的名称叫做值迭代。它的实现将在第4章中详细介绍。在本章中，我们主要关注最优贝尔曼方程的基本性质。

迭代计算

因为系统模型参数、都是已知的，(reward)、 (discount rate)都给定常数；是常数；在此情形下，也是已知的中间值。因此，我们能够通过求解以实现对表达式的最大化。

求解：一旦得到了的值，我们就可以通过求解轻松获得。

的值将在定理 3.5 中给出。将（3.6）代入 BOE 可得。

因此，是策略的状态价值，而贝尔曼最优方程是一个特殊的贝尔曼方程，其对应的策略是。在这一点上，虽然我们可以求解和，但仍不清楚该解是否是最优的。下面的定理揭示了该解的最优性。

是最优状态价值

💡

定理3.4（和的最优性）。解是最优状态价值，是一个最优策略。也就是说，对于任何策略，都有：

其中是策略的状态价值，是逐元素比较。

现在，我们必须研究贝尔曼最优方程的原因很清楚了：它的解对应着最优状态价值和最优策略。上述定理的证明在下面的方框中给出。

定理 3.4 证明

对于任何策略，都有以下情况成立。

因为

所以

反复应用上述不等式可得：。由此可得

最后一个等式成立是因为，并且是一个非负矩阵，其所有元素都小于或等于 1（因为）。因此，对于任何，。

策略不一定最优

💡

定理 3.5（贪心最优策略）。对于任意的状态，确定性贪心策略。

是解决BOE问题的一种最优策略。

定理 3.5 证明

虽然最优策略的矩阵向量形式是，但其按元素形式是

很明显，如果策略选择具有最大的动作，那么就会被最大化。

式（3.7）中的策略被称为贪心策略，因为它寻求具有最大的动作。最后，我们讨论的两个重要性质。

最优策略的唯一性：尽管的值是唯一的，但对应于的最优策略可能不是唯一的。这可以很容易地通过反例来验证。例如，图 3.3 中所示的两种策略都是最优的。

最优策略的随机性：最优策略可以是随机的也可以是确定性的，如图 3.3 所示。然而，根据定理 3.5，可以确定总是存在一个确定性的最优策略。

最优策略的影响因素

通过BOE的公式(3.4)可以发现最优状态价最优策略由以下参数决定：

即时奖励

折扣率

系统模型。

附录

参考：【强化学习】强化学习数学基础：贝尔曼最优公式_贝尔曼公式-CSDN博客