六、随机近似与随机梯度下降

type

status

password

date

slug

summary

6.1 背景—动机

6.1.1 增量计算

接下来，我们通过研究均值估计问题来展示如何将非增量算法转换为增量算法。

考虑一个从有限集中取值的随机变量。我们的目标是估计。假设我们有一个独立同分布的样本序列。的期望值可以通过以下方式近似。

式（6.1）中的近似是蒙特卡洛估计的基本思想，如第 5 章所介绍。根据大数定律，我们知道当时，趋近于。

接下来我们展示有两种方法可以用来计算式（6.1）中的。第一种非增量方法是先收集所有样本，然后计算平均值。这种方法的缺点是，如果样本数量很大，我们可能需要等待很长时间才能收集到所有样本。第二种方法可以避免这个缺点，因为它以增量的方式计算平均值。具体来说，假设

/to

那么，可以用来表示。

因此，我们得到以下增量算法：

该算法可用于以增量方式计算均值。可以验证

式（6.2）的优点是每次收到一个样本时都可以立即计算平均值。这个平均值可以用来近似，进而近似。值得注意的是，由于样本不足，在开始时这个近似可能不准确。然而，有总比没有好。随着获得更多的样本，根据大数定律，估计的准确性可以逐渐提高。

💡

此外，也可以定义和。这样做不会有太大的区别。在这种情况下，相应的迭代算法是。

总结

从有限集中取值的随机变量。我们的目标是估计。假设我们有一个独立同分布的样本序列。的期望值可以通过以下方式近似。

💡

不断的迭代计算

6.1.2 扩展

此外，考虑一个具有更一般表达式的算法：

这个算法很重要，在本章中经常被使用。它与式（6.2）相同，只是系数被所取代。由于没有给出的表达式，我们无法像在式（6.3）中那样得到的显式表达式。然而，我们将在下一节中表明，如果满足一些宽松的条件，那么当时，。在第 7 章中，我们将看到时间差分算法具有类似（但更复杂）的表达式。

6.2 Robbins-Monro算法

随机近似是指一类用于解方程或优化问题的随机迭代算法[24]。与许多其他求根算法（如基于梯度的算法）相比，随机近似的强大之处在于它不需要目标函数的表达式或其导数。

求根与解方程的区别：根是使方程等于零的特定值。求根是解 表达式等于零 的方程

6.2.1 概述

Robbins-Monro（RM）算法是随机近似领域的开创性工作[24-27]。著名的随机梯度下降算法是 RM 算法的一种特殊形式，如第 6.4 节所示。接下来，我们介绍 RM 算法的详细内容。

问题描述

假设我们想要找到方程的根：

其中是未知变量，是一个函数。许多问题都可以表述为解上述方程的问题。例如，如果是一个待优化的目标函数，那么这个优化问题可以转化为求解。此外，像这样的方程，其中是一个常数，可以将作为一个新函数，从而将其转换为上述形式的方程。

如果的表达式或其导数已知，那么有许多数值算法可以使用。然而，我们面临的问题是函数的表达式未知。例如，该函数可能由一个人工神经网络表示，其结构和参数都是未知的。此外，我们只能获得的一个有噪声的观测值。

其中是观测误差，它可能是高斯分布的，也可能不是。总之，这是一个黑箱系统，其中只有输入和有噪声的输出是已知的（见图 6.2）。我们的目标是利用和来求解。

图 6.2: An illustration of the problem of solving from and .

求解方法

能够求解的Robbins-Monro（RM）算法如下。

其中是方程解的第次估计值，是第次有噪声的观测值，并且是一个正系数。可以看出，Robbins-Monro算法不需要关于函数的任何信息。它只需要输入和带有噪声的输出。

示例

为了说明Robbins-Monro算法，考虑一个例子，其中。真正的解是。现在，假设我们只能观察到输入和输出，其中是独立同分布的，服从均值为零、标准差为的标准正态分布。初始化为，系数是。的迭代过程如图 6.3 所示。即使观测值被噪声破坏，仍然可以收敛到真正的解。

💡

请注意，初始化很重要，只有参数被恰当的初始化，才能确保算法收敛。在接下来的小节中，我们将给出Robbins-Monro算法对于任何初始化都收敛的条件。

如果参数初始化不恰当，那么参数会崩掉

初始化为1：[3.633105682846248, -17.04307496742068, 1634.488171984292, -1091653230.7139578, 2.6018611044481768e+26, -2.9356283702652555e+78, 3.6141418029199846e+234, -inf, nan, nan, nan, nan, nan, nan, ...]

初始化为1.71：[1.89, 0.87, 2.27, 0.81, 1.72, 1.70, 1.92, 1.49, 1.68, 1.67, 1.69, 1.59, 1.50, 1.52, 1.62, 1.59, 1.66, 1.67, 1.673, 1.70, 1.70, 1.74, 1.83, 1.75, ...]

举例分析收敛性

为什么Robbins-Monro算法（公式6.5）能够找到的解呢？接下来我们用一个例子来说明这个思路，然后给出严格的收敛性分析。

考虑如图 6.4 所示的示例。在这个示例中，。的真正解是。我们应用Robbins-Monro算法，初始值且。为了更好地说明收敛的原因，我们简单地令，因此，。在这种情况下，Robbins-Monro算法为。由Robbins-Monro算法生成的如图 6.4 所示。可以看出，收敛到真正的解。这个简单的例子可以说明为什么 RM 算法会收敛。

当时，我们有。那么，。如果足够小，我们有。结果是，比更接近。

当时，我们有。那么，。如果足够小，我们有。结果是，比更接近。

💡

在任何一种情况下，都比更接近。因此，很直观地可以看出收敛于。

上面的例子很简单，因为假设观测误差为零。在存在随机观测误差的情况下分析收敛性并非易事。下面给出一个严格的收敛结果。

6.2.2 Robbins-Monro定理

💡

定理 6.1（Robbins-Monro theorem）。在（6.5）中的Robbins-Monro算法中，如果：

对于所有的，都有；表明是一个单调递增函数，且的梯度有上界。

且。，要求在时收敛到零；，要求不应该太快收敛到零。要求越来越小，但是要很长。

且，其中，那么几乎必然收敛到满足的解。

我们将这个定理的证明推迟到 6.3.3 节。这个定理依赖于几乎必然收敛的概念，该概念在附录 B 中介绍。

定理 6.1 中的三个条件解释如下。
在第一个条件中。表明是一个单调递增函数，且的梯度有上界。
表明是一个单调递增函数。
这个条件确保的解存在且唯一。如果是单调递减的，我们可以简单地将视为一个新的单调递增函数。
作为一个应用，我们可以将目标函数为的优化问题表述为一个解方程组的问题。在这种情况下，单调递增的条件（单调递增）表明是凸函数，这是优化问题中常用的假设。凸函数的导数是单调函数
💡
凸函数的导数是单调函数。但如果一个函数的导数是单调递增函数，那么这个函数不一定是凸函数
不等式表明的梯度有上界
不等式表明的梯度有上界，梯度不能越来越大。例如，满足这个条件，但不满足。
关于的第二个条件很有趣。我们经常在强化学习算法中看到这样的条件，稍后将详细分析。
条件意味着有上界。它要求在时收敛到零。
条件意味着是无穷大。它要求不应该太快收敛到零。
第三个条件比较宽松。它不要求观测误差是高斯分布的。一个重要的特殊情况是是一个独立同分布的随机序列，满足且，因为与独立，所以我们有且。
：表明随机误差在长期多次观测中的平均取值为零。这意味着误差在正负方向上的平均影响相互抵消，不存在系统性的偏差朝着某个特定方向。
：方差衡量了随机误差围绕其期望的波动程度。方差小于无穷大意味着误差的波动是有界的，不会无限制地剧烈变化。

系数

接下来我们更仔细地研究关于系数的第二个条件。为什么第二个条件对 RM 算法的收敛很重要呢？当我们稍后给出上述定理的严格证明时，这个问题自然可以得到回答。在这里，我们想提供一些有见地的直觉。

的重要性

首先，表明当时。为什么这个条件很重要呢？假设观测值总是有界的。由于

如果，那么，因此，这表明当时，和相互接近。否则，如果不收敛，那么当时，可能仍然会波动。

的重要性

其次，表明不应该太快收敛到零。为什么这个条件很重要呢？对，，……等式两边进行合并。

如果，那么也是有界的。设表示有限的上界，使得：

如果初始值离很远，以至于，那么根据（6.6），不可能有。这表明在这种情况下，随机映射（RM）算法无法找到真正的解。因此，要在给定任意初始值的情况下确保收敛，条件是必要的。

什么样的序列满足且？

其中被称为Euler-Mascheroni常数（或欧拉常数）[28]。由于当时，，所以我们有

事实上，在数论中，被称为调和数[29]。另一方面，有以下结论成立。

求的值被称为Basel问题[30]。

总之，序列满足定理 6.1 中的第二个条件。值得注意的是，稍作修改，比如或者（其中是有界的），也满足这个条件。

💡

在许多应用中，RM算法的通常被选为一个足够小的常数。尽管在这种情况下，由于而不是，所以第二个条件不再满足；但该算法在某种意义上仍然可以收敛[24，第 1.5 节]。此外，如图 6.3 所示例子中的不满足第一个条件，但如果参数初始化得当，RM 算法仍可以找到解。

6.2.3 均值估计的应用

接下来，我们应用Robbins-Monro定理来分析均值估计问题，该问题已在 6.1 节中进行了讨论。回想一下。

（6.4）中的是均值估计算法。当时，我们可以得到的解析表达式为。然而，当给定一般的值时，收敛性分析并非易事；我们可以证明在这种情况下的算法是一种特殊的 RM（Robbins-Monro）算法，因此其收敛性自然成立。

特别地，定义一个函数如下。

原始问题是获得的值。这个问题被表述为一个求解的问题。给定一个的值，我们可以获得的有噪声观测值是，其中是的一个样本。注意，可以写成

其中。

用于解决这个问题的Robbins-Monro算法是

这正是（6.4）中的算法。因此，根据定理 6.1，如果，且是独立同分布的，那么可以保证几乎必然收敛到。值得一提的是，这种收敛性质不依赖于关于分布的任何假设。

6.3 Dvoretzky’s收敛定理

到目前为止，RM 算法的收敛性尚未得到证明。为了证明这一点，我们接下来引入Dvoretzky’s基定理[31,32]，这是随机近似领域的一个经典理论。这个定理可用于分析 RM 算法以及许多强化学习算法的收敛性。

这一部分的数学性稍强。对随机算法的收敛性分析感兴趣的读者建议学习这一部分。否则，这一部分可以跳过。

💡

定理 6.2（Dvoretzky’s定理）：假设一个随机过程。

其中、、是随机序列。在此，对于所有的，都有，。那么，如果满足以下条件，依概率1(almost surely)收敛到零：

（a）uniformly almost surely地有，，且；（b）almost surely地有且；其中。

依概率收敛

6.3.1 Dvoretzky’s 定理证明

Dvoretzky’s定理的原始证明是在 1956 年给出的[31]。也有其他的证明方法。接下来我们给出一个基于quasimartingales的证明。借助quasimartingales的收敛结果，Dvoretzky’s的证明是直接的。关于quasimartingales的更多信息可以在附录 C 中找到。

Dvoretzky’s 收敛定理证明，假设
对上述等式两边取期望，可得
首先，由于包含在内，因此由确定，它可以从期望中提取出来（见引理 B.1 中的性质(e)）。其次，考虑和由确定的简单情况。例如，当和是的函数或确定性序列时，这种情况是有效的。那么，它们也可以从期望中提取出来。因此，（6.7）变为。
对于第一项，由于意味着几乎必然成立，所以存在一个有限的，使得对于所有，几乎必然成立。不失一般性，我们接下来只考虑的情况。那么，。对于第二项，我们有，如假设所示。第三项等于零，因为如假设所示。因此，式（6.8）变为。
最后一个不等式是由于这个条件。然后，根据附录 C 中的拟鞅收敛定理，我们得出几乎必然收敛。
右边第一项如假设那样是有界的。第二项也是有界的，因为收敛，所以是可和的。因此，左边的也是有界的。由于我们考虑的情况，所以有
因此，是有界的。由于，我们必然有几乎必然成立。

6.3.2 均值估计的应用

虽然均值估计算法已经使用Robbins-Monro定理（RM theorem）进行了分析，但接下来我们将展示其收敛性也可以通过Dvoretzky’s 定理直接证明。

证明：设。均值估计算法可以重写为。
令。那么，我们有。
由于是独立同分布的，所以我们有。因此，，并且如果的方差是有限的，那么是有界的。根据Dvoretzky’s定理，我们得出收敛到零，因此几乎必然收敛到。

6.3.3 对Robbins-Monro定理的应用。

现在我们准备使用Dvoretzky’s定理来证明Robbins-Monro定理。

Robbins-Monro定理的证明。RM 算法旨在找到的根。假设根为，使得。RM 算法是
然后，我们有
根据中值定理[7,8]，我们有，其中。令。上述方程变为
注意，如假设所示，是有界的，即。由于假设且，我们知道且。因此，Dvoretzky’s定理中的所有条件都得到满足，所以几乎必然收敛到零。
Robbins-Monro定理的证明展示了Dvoretzky’s定理的强大之处。
特别是，证明中的是一个依赖于的随机序列，而不是一个确定的序列。在这种情况下，Dvoretzky’s定理仍然适用。

6.3.4 Dvoretzky’s定理的扩展

接下来，我们将Dvoretzky’s定理扩展为一个更一般的定理，这个定理可以处理多个变量。这个由[32]提出的一般定理可以用于分析诸如 Q-learning 之类的随机迭代算法的收敛性。

💡

定理 6.3：考虑一个实数的有限集合。对于随机过程

如果对于满足以下条件，则对于每个，几乎必然收敛到零：

（a）对于，，，，并且几乎必然一致成立；

（b），其中；

（c），其中是一个常数。

这里，表示历史信息。符号指的是最大范数。

证明。作为一种扩展，这个定理可以基于Dvoretzky’s定理来证明。详细内容可以在[32]中找到，这里省略。

关于这个定理的一些评论如下。

我们首先阐明定理中的一些符号。变量可以被视为一个索引。在强化学习的背景下，它表示一个状态或一个状态-动作对。最大范数是在一个集合上定义的。它与向量的范数相似但不同。特别地，且。

这个定理比Dvoretzky’s定理更一般。首先，由于最大范数运算，它可以处理多变量的情况。这对于具有多个状态的强化学习问题很重要。其次，虽然Dvoretzky’s定理要求且，但这个定理只要求期望和方差由误差界定。

应当注意，对于所有，的收敛要求这些条件对每个都有效。因此，当应用这个定理来证明强化学习算法的收敛性时，我们需要证明这些条件对每个状态（或状态-动作对）都有效。

6.4 随机梯度下降

本节介绍随机梯度下降（Stochastic Gradient Descent，SGD）算法，该算法在机器学习领域中被广泛使用。我们将会看到，随机梯度下降是一种特殊的Robbins-Monro算法，而均值估计算法是一种特殊的随机梯度下降算法。

6.4.1 概述

考虑以下优化问题：

其中是待优化的参数，是一个随机变量。期望是相对于计算的。这里，和可以是标量也可以是向量。函数是一个标量。

求解（6.10）的一种直接方法是梯度下降。特别地，的梯度是。那么，梯度下降算法是：

在一些宽松的条件下，例如的凸性条件下，这种梯度下降算法可以找到最优解。关于梯度下降算法的预备知识可以在附录 D 中找到。

梯度下降算法需要这个期望值。一种获得期望值的方法是基于的概率分布。然而，在实际中这个分布通常是未知的。另一种方法是收集大量独立同分布的的样本，这样期望值就可以近似为：

那么，（6.11）就变成了：

（6.12）中的算法存在一个问题，即它在每次迭代中都需要所有的样本。在实际中，如果样本是一个一个收集的，那么每次收集到一个样本就更新会更有利。为此，我们可以使用以下算法：

其中是在时间步收集到的样本。这就是著名的随机梯度下降算法。这个算法被称为“随机的”，是因为它依赖于随机样本。

与（6.11）中的梯度下降算法相比，随机梯度下降用随机梯度代替了真实梯度。由于，这样的替换仍然能确保当时吗？答案是肯定的。接下来我们给出一个直观的解释，并将收敛性的严格证明推迟到 6.4.5 节。特别地，由于

式（6.13）中的随机梯度下降算法可以重写为：

因此，随机梯度下降算法与常规梯度下降算法相同，只是它有一个扰动项。由于是独立同分布的，所以。结果是

因此，扰动项具有零均值，这直观地表明它可能不会损害收敛性。随机梯度下降的收敛性的严格证明在 6.4.5 节给出。

6.4.2 应用于均值估计

接下来我们将随机梯度下降应用于分析均值估计问题，并表明式（6.4）中的均值估计算法是一种特殊的随机梯度下降算法。为此，我们将均值估计问题表述为一个优化问题：

其中，梯度为。通过求解可以验证最优解是。因此，这个优化问题等同于均值估计问题。

用于求解（6.14）的梯度下降算法是：

这个梯度下降算法不可用，因为右边的或者是未知的（实际上，这正是我们需要求解的东西）。

用于求解（6.14）的随机梯度下降算法是：

其中是在时间步获得的一个样本。值得注意的是，这个随机梯度下降算法与式（6.4）中的迭代均值估计算法是相同的。因此，式（6.4）是专门为解决均值估计问题而设计的随机梯度下降算法。

6.4.3 随机梯度下降的收敛模式

随机梯度下降算法的思想是用随机梯度代替真实梯度。然而，由于随机梯度是随机的，人们可能会问随机梯度下降的收敛速度是否缓慢慢、是否随机。幸运的是，一般情况下随机梯度下降可以有效地收敛。一个有趣的收敛模式是，当估计值远离最优解时，它的表现与常规梯度下降算法相似。只有当接近时，随机梯度下降的收敛才会表现出更多的随机性。下面给出对这种模式的分析和一个说明性的例子。

分析：随机梯度与真实梯度之间的相对误差为

为了简单起见，我们考虑和都是标量的情况。由于是最优解，所以。那么，相对误差可以重写为

其中最后一个等式是由于中值定理[7,8]，并且。

假设是严格凸函数，使得对于所有的，。那么，（6.15）中的分母变为

将上述不等式代入（6.15）可得。

示例：一个很好地展示上述分析的例子是均值估计问题。考虑（6.14）中的均值估计问题。当和都是标量时，我们有，因此。

因此，相对误差为：

这个结果进一步说明了在均值估计问题中，相对误差与之间的关系，与前面的分析一致。当较大时，相对误差较小，算法表现得像梯度下降算法，快速收敛；当接近时，相对误差可能较大，收敛表现出更多随机性。

仿真结果如图 6.5 所示。这里，表示平面中的一个随机位置。它的分布在以原点为中心的正方形区域内是均匀的，且。均值估计基于 100 个独立同分布的样本。尽管均值的初始猜测远离真实值，但可以看到随机梯度下降估计值迅速接近原点附近。当估计值接近原点时，收敛过程表现出一定的随机性。

6.4.4 随机梯度下降的一种确定性公式

式（6.13）中随机梯度下降（SGD）的公式涉及随机变量。人们经常会遇到一种不涉及任何随机变量的确定性的 SGD 公式。

特别地，考虑一组实数，其中不一定是任何随机变量的样本。要解决的优化问题是最小化平均值：

其中是一个参数化函数，是要优化的参数。解决这个问题的梯度下降算法是：

假设集合规模很大，并且我们每次只能获取一个数据。在这种情况下，以增量方式更新是有利的。

必须注意的是，这里的是在时间步获取到的数字，而不是集合中的第个元素。

公式（6.16）中的算法与随机梯度下降（SGD）非常相似，但其问题表述略有不同，因为它不涉及任何随机变量或期望值。于是，就产生了许多问题。例如，这个算法是随机梯度下降算法吗？我们应该如何使用有限数字集呢？我们是应该将这些数字按某种顺序排序然后逐个使用，还是应该从集合中随机抽取一个数字呢？

对上述问题的一个快速回答是，尽管上述公式中没有涉及随机变量，但我们可以通过引入一个随机变量将确定性公式转换为随机性公式。特别地，令为定义在集合上的随机变量。假设其概率分布是均匀的，使得。那么，确定性优化问题就变成了一个随机性问题：

6.4.4 BGD, SGD, and mini-batch GD

虽然随机梯度下降（SGD）在每次迭代中使用单个样本，但接下来我们将介绍小批量梯度下降（MBGD），它在每次迭代中使用更多的样本。当在每次迭代中使用所有样本时，该算法被称为批量梯度下降（BGD）。

具体来说，假设给定随机变量的一组随机样本，我们想要找到能使最小化的最优解。用于解决此问题的批量梯度下降（BGD）、随机梯度下降（SGD）和小批量梯度下降（MBGD）算法分别为：

在批量梯度下降（BGD）算法中，每次迭代都会用到所有样本。当很大时，接近真实梯度。在小批量梯度下降（MBGD）算法中，是在时刻得到的的一个子集。该集合的大小为。同时假定中的样本是独立同分布（i.i.d）的。在随机梯度下降（SGD）算法中，是在时刻从中随机采样得到的。

小批量梯度下降（MBGD）可被视为随机梯度下降（SGD）和批量梯度下降（BGD）之间的中间版本。与SGD相比，MBGD的随机性更小，因为它使用更多的样本，而不像SGD那样仅使用一个样本。与BGD相比，MBGD不需要在每次迭代中使用所有样本，这使其更具灵活性。如果，那么MBGD就变成了SGD。然而，如果，MBGD可能不会变成BGD。这是因为MBGD使用的是随机获取的个样本，而BGD使用的是全部个数字。这随机获取的个样本可能多次包含同一个数字，因此可能无法涵盖中的所有个数字。

一般来说，MBGD的收敛速度比SGD快。这是因为SGD使用来近似真实梯度，而MBGD使用，由于随机性被平均化，它更接近真实梯度。MBGD算法的收敛性可以用与SGD情况类似的方法证明。

用于说明上述分析的一个很好的例子是均值估计问题。具体来说，给定一些数字，我们的目标是计算均值。这个问题可以等价地表述为如下优化问题：

其最优解为。用于解决此问题的三个算法分别是：

其中。此外，如果，上述等式可以按如下方式求解：

上述等式的推导与（6.3）的推导类似，在此省略。可以看出，批量梯度下降（BGD）在每一步给出的估计值恰好是最优解。小批量梯度下降（MBGD）比随机梯度下降（SGD）更快地收敛到均值，因为已经是一个平均值。

图6.5给出了一个模拟示例，用于展示小批量梯度下降（MBGD）的收敛性。设。结果表明，不同小批量大小的所有MBGD算法都能收敛到均值。的情况收敛速度最快，而的随机梯度下降（SGD）最慢。这与上述分析一致。然而，SGD的收敛速度仍然很快，特别是当远离时。

6.4.5 随机梯度下降（SGD）的收敛性

随机梯度下降（SGD）收敛性的严格证明如下。

💡

定理6.4（SGD的收敛性）对于公式（6.13）中的随机梯度下降算法，如果满足以下条件，那么几乎必然收敛到的根。

且；

是独立同分布（i.i.d.）的。

下面对定理6.4中的三个条件进行讨论。

条件1是关于的凸性的。它要求的曲率上下有界。这里，是一个标量，也是标量。这个条件可以推广到向量情形。当是向量时，就是著名的海森（Hessian）矩阵。

条件2与均方根（RM）算法的条件类似。实际上，随机梯度下降算法是一种特殊的均方根算法（如框6.1中的证明所示）。在实际中，通常被选为一个足够小的常数。尽管在这种情况下不满足条件2，但该算法在某种意义上仍然能够收敛[24，1.5节]。

条件3是一个常见的要求。

证明

接下来我们将表明随机梯度下降（SGD）算法是一种特殊的均方根（RM）算法。然后，随机梯度下降算法的收敛性自然就可以从均方根定理得出。

随机梯度下降算法要解决的问题是最小化。这个问题可以转化为一个求根问题。即，求的根。令

然后，随机梯度下降（SGD）旨在找到的根。这正是均方根（RM）算法所解决的问题。我们能够测量的量是，其中是的一个样本。注意，可重写为

那么，用于求解的均方根（RM）算法为：

这与公式（6.13）中的随机梯度下降（SGD）算法相同。因此，随机梯度下降算法是一种特殊的均方根（RM）算法。接下来我们将表明定理6.1中的三个条件得到满足。然后，随机梯度下降（SGD）的收敛性自然可由定理6.1得出。

由于，由可推出。因此，定理6.1中的第一个条件得到满足。

定理6.1中的第二个条件与本定理中的第二个条件相同。

定理6.1中的第三个条件要求且。由于是独立同分布（i.i.d.）的，对于所有的，我们有。因此，

由于且与相互独立，等式右边的第一项变为。第二项变为，因为是的函数。因此

类似地，可以证明如果对于任意的，对于所有的都有，那么。

由于定理6.1中的三个条件均得到满足，随机梯度下降（SGD）算法的收敛性得证。

6.5 总结

本章没有引入新的强化学习算法，而是介绍了随机逼近的预备知识，如均方根（RM）算法和随机梯度下降（SGD）算法。与许多其他求根算法相比，均方根算法不需要目标函数或其导数的表达式。已经表明，随机梯度下降算法是一种特殊的均方根算法。此外，均值估计是本章通篇频繁讨论的一个重要问题。均值估计算法（6.4）是我们在本书中介绍的第一个随机迭代算法。我们表明它是一种特殊的随机梯度下降算法。我们将在第7章看到，时差学习算法有着类似的表达式。最后，“随机逼近”这个名称最早是由罗宾斯（Robbins）和蒙罗（Monro）在1951年使用的[25]。有关随机逼近的更多信息可在[24]中找到。

在给出这个定理的证明之前，我们首先澄清一些问题。

在 RM 算法中，系数序列是确定的。然而，Dvoretzky’s定理允许、是依赖于的随机变量。因此，在或是的函数的情况下，它更加有用。

在第一个条件中，表述为“uniformly almost surely”。这是因为和可能是随机变量，因此它们的极限的定义必须在随机意义下。在第二个条件中，也表述为“almost surely”。这是因为是一个随机变量序列而不是特定的值。因此，和是随机变量。在这种情况下，条件期望的定义是在“almost surely”意义下（附录 B）。

定理6.2的陈述与[32]略有不同，在于定理6.2在第一个条件中不要求。当时，特别是在极端情况下，即对所有的都有时，序列仍然可以收敛。