PPO算法-chapter6-随机近似理论和随机梯度下降

Bohao Zhao2025-09-192025-09-20

[chapter-6]-随机近似理论和随机梯度下降

[PPO算法]-随机近似和随机梯度下降

前言

重新审视均值估计问题：

考虑一个随机变量。
假设我们收集了一组独立同分布样本。
我们的目标是估计。
的期望可以通过以下方式近似

这种近似是蒙特卡洛估计的基本思想。
我们知道当。

为什么我们如此关心均值估计？

强化学习中的许多量如动作值和梯度都是定义为期望值！

新问题：如何计算均值？

我们有两种方法。

第一种方法是收集所有样本然后计算平均值。
- 这种方法的缺点是，如果样本是逐个收集的，我们必须等待所有样本收集完毕。
第二种方法可以避免这种缺点，因为它以增量和迭代的方式计算平均值。

特别地，假设

因此

那么可以用表示为

因此，我们得到以下迭代算法：

验证：我们可以使用

来递增计算均值：

关于该算法的说明：

该算法的优势是增量的。一旦收到样本，即可立即获得均值估计。然后，均值估计可以立即用于其他目的。
由于样本不足，开始时均值估计不准确（即）。然而，总比没有好。随着更多样本获得，估计可以逐渐改进（即当）。

RM算法

随机近似（SA）：

SA 指的是解决根查找或优化问题的广泛随机迭代算法。
与许多其他基于梯度量的根查找算法相比，SA 的强大之处在于不需要知道目标函数的表达式或其导数。

罗宾斯-蒙罗（RM）算法：

是随机近似领域的开创性工作。
著名的随机梯度下降算法是 RM 算法的特例。
可用于分析最初介绍的均值估计算法。

问题描述

问题陈述：假设我们希望找到方程的根

其中是要解的变量，是一个函数。

许多问题最终可以转换为这个根查找问题。例如，假设是要最小化的目标函数。那么，优化问题可以转换为

注意，方程也可以通过重写为新函数转换为上述方程。

如何计算 的根？

有模型：如果的表达式已知，有许多数值算法可以解决此问题。
无模型：如果的表达式未知怎么办？例如，函数由人工神经网络表示。

罗宾斯-蒙罗（RM）算法可以解决此问题的算法如下：

其中

是根的第估计
是第次噪声观察
为什么有噪声？例如，考虑的随机采样。
是正系数。

该算法依赖于数据而非模型：

输入序列：
输出序列（噪声）：

没有模型，我们需要数据！

函数被视为黑盒。
这里的模型指的是函数的表达式。

定理（罗宾斯-蒙罗定理-RM定理）

在罗宾斯-蒙罗算法中，如果

对所有；

和；

和；

其中，则以概率 1（w.p. p.1）收敛到满足的根。

解释三个条件：

条件1：对所有
- 应单调递增，确保的根存在且唯一
- 梯度量有界
- 此条件不严格。考虑。此条件要求凸。
条件 2：和
- 确保收敛到 0。
- 确保不收敛过快。
条件 3：和
- 特例：是满足和的独立同分布序列。不必高斯。

应用

回顾

是开始时介绍的均值估计算法。

如果，则。
如果不是，收敛性未分析。

接下来，我们展示此算法是 RM 算法的特例。然后，其收敛性自然跟随。

考虑一个函数：

我们的目标是求解。如果可以，那么我们可以获得。

均值估计（即，找到）被公式化为根查找问题（即，求解）。
问题：我们是否知道的表达式？

我们可以得到的观察是

因为我们只能获得的样本。注意

求解的 RM 算法是

即均值估计算法。收敛性自然跟随。

定理（多尔特斯基定理）

考虑随机过程

其中是随机序列。

这里对所有。那么以概率 1收敛到 0 如果满足以下条件：

几乎必然成立；

和几乎必然成立；

其中。

比 RM 定理更一般的结果。

可用于证明 RM 定理

可用于分析均值估计问题。

扩展可用于分析 Q-学习和 TD 学习算法。

SGD算法

接下来，我们介绍随机梯度下降（SGD）算法：

SGD 在机器学习和强化学习中广泛使用。
SGD 是 RM 算法的特例。
均值估计算法是 SGD 算法的特例。

问题设置：假设我们希望解决以下优化问题：

是要优化的参数。
是随机变量。期望关于。
和可以是标量或向量。函数是标量。

方法1-梯度下降（GD）

缺点：计算期望需要的分布。

方法2-批梯度下降（BGD）

因此

$缺点：每次迭代需要每个许多样本。

方法3-随机梯度下降（SGD）

与梯度下降方法相比：
- 用随机梯度替换。
与批度下降方法相比：
- 令。

我们接下来考虑一个例子：

其中

$￥$

练习：

练习 1：证明最优解是。
练习 2：写出解决此问题的 GD 算法。
练习 3：写出解决此问题的 SGD 算法。

我们接下来考虑一个例子：

其中

练习 1 的解答：最优解必须满足

即

因此，我们将均值估计问题（即，寻找）作为一个优化问题（即，优化）。

练习 2 的解答：解决上述问题的 GD 算法是

练习 3 的解答：解决上述问题的SGD算法是

这与我们之前介绍的均值估计算法相同。

因此，均值估计算法是一种特殊的SGD算法。

‍

收敛性分析

SGD 的思想：

其中真实梯度被随机梯度替代。

问题：由于

是否随着通过 SGD 收敛？

观察：随机梯度是对真实梯度的噪声测量：

其中是噪声。

我们能够测量的是

然后，解决的 RM 算法是

这正是 SGD 算法。
因此，SGD 是一种特殊的 RM 算法。

定理（SGD 的收敛性）

在 SGD 算法中，如果

；

且；

是独立同分布的；

那么以概率 1 收敛到的根。

问题：由于随机梯度是随机的，因此近似是不准确的，SGD 的收敛是慢的还是随机的？

解答：我们通过考虑随机梯度和批量梯度之间的相对误差来回答这个问题：

可以证明

证明

由于，我们有

其中最后一个等式是由于均值定理和。假设是严格凸的，使得

对于所有的，其中是一个正的常数。

然后，的分母变为

将上述不等式代入得到

上述方程表明了 SGD 的一个有趣的收敛模式。

上界与成反比。
- 当较大时，相对误差较小，SGD 的表现类似于 GD。
- 当较小时，相对误差可能较大（上界可能不紧）。然后，SGD 在的邻域内表现出更多的随机性。

假设我们希望在给定一组随机样本的情况下最小化。

解决这个问题的 BGD、SGD、MBGD 算法分别是：

在 BGD 算法中，每次迭代都使用所有样本。当较大时，接近真实梯度。
在 MBGD 算法中，是的一个子集，大小为。集合是通过次独立同分布采样获得的。
在 SGD 算法中，是在时刻从中随机采样的。

比较 MBGD 与 BGD 和 SGD：

与 SGD 相比，MBGD 的随机性较小，因为它使用的样本比 SGD 多。
与 BGD 相比，MBGD 不需要在每次迭代中使用所有样本，使其更加灵活和高效。
如果，MBGD 变为 SGD。
如果，MBGD 并不严格成为 BGD，因为 MBGD 使用随机抽取的个样本，而 BGD 使用所有个样本。特别是，MBGD 可能会多次使用中的某个值，而 BGD 每个值只使用一次。相当于一个是箱子内拿球放回和全部拿球