RL 学习笔记 #5 随机近似与随机梯度下降

在上一节中，我们介绍了首个无模型的强化学习算法 ——蒙特卡洛学习（MC Learning）。在进一步讨论其他无模型算法之前，需要了解一个重要的理论背景：随机近似理论（Stochastic Approximation）。

随机近似 | Stochastic Approximation

在强化学习中，许多算法需要估计某个随机过程的期望值。例如，给定一个随机变量 \(X_1, X_2, \dots, X_n\)，我们希望估计其均值 \(\mu = \mathbb{E}[X]\)。一个简单的估计方法是均值估计： \[ \hat{\mu}_n = \frac{1}{n} \sum_{i=1}^n X_i \] 但是在实践中，等待足够多的数据点进行计算往往非常耗时。为了高效地更新估计值，我们引入增量式更新（Incremental Update）的思想，即通过不断使用新数据来逐步逼近 \(\mu\)。这样的更新方式不需要等待所有数据点收集完毕，适用于实时更新。

具体而言，假设： \[ \theta_{n+1}=\frac{1}{n} \sum_{i=1}^n x_i, \quad n=1,2, \ldots \]

进而有：

\[ \theta_n=\frac{1}{n-1} \sum_{i=1}^{n-1} x_i, \quad n=2,3, \ldots \]

于是，\(\theta_{n+1}\) 可以用 \(\theta_n\) 表示出来：

\[ \begin{aligned} \theta_{n+1}=\frac{1}{n} \sum_{i=1}^n x_i & =\frac{1}{n}\left(\sum_{i=1}^{n-1} x_i+x_n\right) \\ & =\frac{1}{n}\left((n-1) \theta_n+x_n\right)=\theta_n-\frac{1}{n}\left(\theta_n-x_n\right) \end{aligned} \] 这个递归公式表明，\(\theta_{n+1}\) 只依赖于当前的估计值 \(\theta_n\) 和新样本 \(x_n\)，每一步的更新只需少量的计算资源，从而可以在实时环境中进行增量更新。

随机近似理论扩展了这一思想，通过一般化的递归更新公式处理更复杂的估计问题： \[ \theta_{n+1} = \theta_n - \alpha_n h(\theta_n, X_{n+1}) \] 其中：

• \(\theta_n\) 是当前估计值，\(\theta_{n+1}\) 是下一步的估计；
• \(\alpha_n\) 是步长（学习率），控制每次更新的幅度；
• \(h(\theta_n, X_{n+1})\) 是一个与当前估计值 \(\theta_n\) 和新样本 \(X_{n+1}\) 相关的函数，通常代表误差。

这一理论为强化学习中许多算法（如值函数估计）提供了理论支撑。

Robbins-Monro 算法

在随机近似理论中，最经典的方法之一就是 Robbins-Monro 算法，它常用于估计期望或者求解方程的根，且通常用于具有噪声的场景。

案例 1：解方程

例如，在神经网络中，我们的目标是最小化损失函数 \(J(\theta)\)，此时优化问题可以转化为求 \(\nabla_\theta J(\theta)=0\) 的解。但由于模型的复杂性，我们无法直接求出其梯度的表达式，这个时候通常会用 RM 算法来逼近目标。

考虑求解目标方程 \(g(\theta)=0\) 的根，此时具体的更新公式是： \[ \theta_{n+1} = \theta_n - a_n \tilde{g}(\theta_n, \eta_n) \] 其中：

• \(\theta_n\) 是第 \(n\) 次的估计值，算法的目标是通过对观测值 $ (_n, _n)$ 的递归更新，逐步逼近方程 $g() = 0 $ 的根；
• \(\tilde{g}(\theta_n, \eta_n) = g(\theta_n) + \eta_n\) 是带噪声的观测值，\(\eta_n\) 是噪声项，表示某个函数 \(g(\theta_n)\) 的值由于噪声的存在，最终呈现为一个带有误差的随机变量；
• \(a_n\) 是步长参数，控制每次更新的幅度，需要满足一定条件来确保收敛性（后述）。

案例 2：求期望

又例如，在求解期望 \(\mu = \mathbb{E}[X]\) 时，RM 算法通过以下更新规则逐步逼近： \[ \hat{\mu}_{n+1} = \hat{\mu}_n-a_n (\hat{\mu}_n - X_{n+1}) \] 其中：

• \(\hat{\mu}_n\) 是当前的期望估计值，算法的目标是通过不断更新 \(\hat{\mu}_n\) 来逼近真实的期望值 \(\mu = \mathbb{E}[X]\)；
• \(X_{n+1}\) 是观测到的随机变量样本值，带有观测噪声 \(\eta_n\)，这里也可以理解为 \(\tilde{g}(\mu_n, \eta_n)\)；
• \(a_n\) 是步长参数，需要满足 \(\alpha_n > 0\) 且 \(\sum_n \alpha_n = \infty\) 和 \(\sum_n \alpha_n^2 < \infty\)，以确保收敛性。

在强化学习中，RM 算法可以应用于状态值函数或动作值函数的估计。例如，使用蒙特卡洛方法估计状态值函数时，可以通过以下更新规则来逼近目标值： \[ v(s) := v(s) - \alpha \left[ v(s) - G_t \right] \] 其中，\(G_t\) 是从状态 \(s\) 出发到终止状态的累计回报，也是和下一节要介绍的时序差分方法的主要区别。

收敛性分析

收敛性分析是 RM 算法的核心问题之一。我们希望确保在有限的步骤内，更新的估计值能够收敛到目标值。为了保证收敛性，通常需要满足以下几个条件：

1. 步长条件：步长 \(\alpha_n\) 必须满足两个条件：
   • \(\sum_n \alpha_n^2 < \infty\)，意味着 \(a_n\) 最终会收敛到 \(0\)，防止步长过大导致震荡和不收敛。
   • \(\sum_n \alpha_n = \infty\)，意味着 \(a_n\) 最终收敛到 \(0\) 的速度不能太快，确保随着迭代次数增加，算法能够不断更新。
   • 常见的一个设置是：\(a_n=\frac{1}{n}\)，通过数论可以证明满足上述条件。实际使用中我们会在一定步骤后固定 \(a_n\) 为一个小数，防止后续新增数据点失去作用。
2. 梯度存在性和有界性：对所有的 \(\theta\)，有 \(0 < c_1 \leq \nabla_\theta g(\theta) \leq c_2\)。
   • 要求 \(g(\theta)\) 曲线的导数是正数，即 \(g(\theta)\) 递增，从而解 \(\theta^*\) 存在且唯一。而梯度有界则避免了算法的发散。
   • 联系前面提及的 \(\nabla_\theta J(\theta)=0\)，可以发现这里其实是对 \(J(\theta)\) 的二阶导 Hessian 矩阵提出的要求。Hessian 矩阵为正对应了 \(J(\theta)\) 的凸函数性质（Convexity）。
3. 无偏可控误差：误差需要满足 $= 0 $ 且 \(\mathbb{E}\left[\eta_n^2 \mid \mathcal{H}_n\right] < \infty\)，\(\mathcal{H}_n\) 表示历史信息。
   • 如果误差序列 \(\{\eta_n\}\) 是独立同分布的（iid），这就自然满足了上述两个条件：由于独立性，\(\eta_n\) 不依赖于历史信息 \(\mathcal{H}_n\)，因此 \(\mathbb{E}[\eta_n \mid \mathcal{H}_n] = \mathbb{E}[\eta_n] = 0\)。如果采样的分布具有有限的二阶矩（即有限的方差），那么 \(\mathbb{E}[\eta_n^2 \mid \mathcal{H}_n] = \mathbb{E}[\eta_n^2] < \infty\) 也成立。
   • 并且 \(\eta_n\) 不要求是高斯噪音——虽然正态噪声是最常见的一种情况，但它不是唯一可能的分布。

根据这些条件，可以证明 Robbins-Monro 算法在适当的步长设置下会收敛于一个不动点，即目标值。

随机梯度下降 | SGD

在强化学习和深度学习中，随机梯度下降（Stochastic Gradient Descent，SGD） 是一种广泛使用的优化方法，它基于随机近似理论（实际上是 RM 算法的一个特殊情况），可以有效地逼近函数的最优解。

SGD 要解决的典型优化问题是： \[ \min_\theta J(\theta)=\mathbb{E}_X[f(\theta,X)] \]

其中：

• \(X\) 是随机变量，其概率分布已知但不可直接计算；
• \(f(\theta, X)\) 是给定参数 \(\theta\) 时的目标函数值。

由于直接计算 \(\mathbb{E}[f(\theta, X)]\) 通常不可行，我们需要借助样本进行近似。常见的三种方法如下：

1. 梯度下降（Gradient Descent，GD）

   • 梯度下降是一种经典的优化方法，基于目标函数的梯度更新参数： \[ \theta_{n+1} = \theta_n - \alpha_n \nabla_\theta \mathbb{E}[f(\theta_n, X)] = \theta_n - \alpha_n \mathbb{E}[\nabla_\theta f(\theta_n, X)] \]

   • 其中：\(\alpha_n\) 是步长（学习率），\(\nabla_\theta \mathbb{E}[f(\theta_n, X)]\) 是目标函数 \(J(\theta)\) 的梯度。

   • 缺点：没有模型，精确的期望值难以获得——只能用数据去估计。

2. 批量梯度下降（Batch Gradient Descent，BGD）

   • 为解决期望计算的难题，引入有限样本近似。通过采样 \(n\) 个数据点 \({x_1, x_2, \dots, x_n}\)，我们将期望用样本均值代替：

   \[ \mathbb{E}[\nabla_\theta f(\theta_n, X)] \approx \frac{1}{n} \sum_{i=1}^n \nabla_\theta f(\theta_n, x_i) \]

   • 更新公式变为：

   \[ \theta_{n+1} = \theta_n - \alpha_n \frac{1}{n} \sum_{i=1}^n \nabla_\theta f(\theta_n, x_i) \]

   • 缺点：每次迭代需要对 \(n\) 个数据点计算梯度，计算代价仍然过高，尤其在数据量大时难以适用。

3. 随机梯度下降（Stochastic Gradient Descent，SGD）

   • 随机梯度下降则通过仅用一个样本来近似梯度： \[ \theta_{n+1} = \theta_n - \alpha_n \nabla_\theta f(\theta_n, x_i) \]

   • 这里的 \(x_i\) 是从分布中随机采样的单个样本，此时计算开销显著降低。

   • 可以看出，SGD 实际上是 BGD 在 \(n = 1\) 时的特例，且与之前提到的增量式更新方法密切相关。

收敛性分析

在 SGD 中，我们用一个随机梯度（stochastic gradient）代替了真实梯度（true gradient），这种随机性引入了更新误差。具体地，将随机梯度分解为两个部分： \[ \nabla_\theta f\left(\theta_n, x_n\right)=\mathbb{E}\left[\nabla_\theta f(\theta, X)\right]+\underbrace{\nabla_\theta f\left(\theta_n, x_n\right)-\mathbb{E}\left[\nabla_\theta f(\theta, X)\right]}_\eta . \] 其中：

• \(\mathbb{E}[\nabla_\theta f(\theta, X)]\) 是真实梯度；
• \(\eta_n\) 是噪声项，反映了随机梯度的偏差。

那么是否当 \(n \rightarrow \infty\) 时有 \(\theta_n \rightarrow \theta^*\)？通过分析 SGD 可以发现，它实际上是一个特殊的 Robbins-Monro 算法。证明的思路如下：

1. 目标优化问题可以转化为梯度方程 \(g(\theta) = 0\) 的求解问题；
2. 虽然我们没法计算出 \(\mathbb{E}[\nabla_\theta f(\theta_n, X)]\)，但可以测量出 \(\nabla_\theta f(\theta_n, x_n)\)，也就是带噪音的 \(\tilde{g}(\theta_n, \eta_n)\)。

最终可以得到： \[ \theta_{n+1} = \theta_n - a_n \tilde{g}(\theta_n, \eta_n)= \theta_n - a_n \nabla_\theta f\left(\theta_n, x_n\right) \]

因此 SGD 的更新公式与 RM 算法完全一致，因此 SGD 的收敛性可以通过 RM 的分析条件加以修改得到：

• 步长参数：\(\sum_n \alpha_n = \infty\) 且 \(\sum_n \alpha_n^2 < \infty\)。
• 目标函数的严格凸性：\(0 < c_1 \leq \nabla^2_\theta f(\theta, X)\leq c_2\)。
• 独立同分布：\(\{x_k\}^{\infty}_{k=1}\) 是 iid. 的。

随机性与收敛性

我们讨论 SGD 的收敛性时，关注的核心问题是：随机梯度的引入是否会显著影响收敛路径和速度？ 换句话说，随机性是否会导致 \(\theta_k\) 在收敛过程中绕了远路？

为了评估随机性对收敛路径的影响，我们引入相对误差（relative error） 的概念，即： \[ \delta_n \doteq \frac{\left|\nabla_\theta f\left(\theta_n, x_n\right)-\mathbb{E}\left[\nabla_\theta f\left(\theta_n, X\right)\right]\right|}{\left|\mathbb{E}\left[\nabla_\theta f\left(\theta_n, X\right)\right]\right|} \] 由于 \(\mathbb{E}\left[\nabla_\theta f\left(\theta^*, X\right)\right]=0\)，得到： \[ \delta_n=\frac{\left|\nabla_\theta f\left(\theta_n, x_n\right)-\mathbb{E}\left[\nabla_\theta f\left(\theta_n, X\right)\right]\right|}{\left|\mathbb{E}\left[\nabla_\theta f\left(\theta_n, X\right)\right]-\mathbb{E}\left[\nabla_\theta f\left(\theta^*, X\right)\right]\right|}=\frac{\left|\nabla_\theta f\left(\theta_n, x_n\right)-\mathbb{E}\left[\nabla_\theta f\left(\theta_n, X\right)\right]\right|}{\left|\mathbb{E}\left[\nabla_\theta^2 f\left(\tilde{\theta}_n, X\right)\left(\theta_n-\theta^*\right)\right]\right|} \] 这里分母的变形引入了中值定理。当我们假设 \(f\) 是严格凸的，则有： \[ \nabla_\theta^2 f \ge c >0 \] 对分母再次变形可得： \[ \begin{aligned} \left|\mathbb{E}\left[\nabla_\theta^2 f\left(\tilde{\theta}_n, X\right)\left(\theta_n-\theta^*\right)\right]\right| & =\left|\mathbb{E}\left[\nabla_\theta^2 f\left(\tilde{\theta}_n, X\right)\right]\left(\theta_n-\theta^*\right)\right| \\ & =\left|\mathbb{E}\left[\nabla_\theta^2 f\left(\tilde{\theta}_n, X\right)\right]\right|\left|\left(\theta_n-\theta^*\right)\right| \geq c\left|\theta_n-\theta^*\right| \end{aligned} \] 代回原式可得： \[ \delta_n \leq \frac{|\overbrace{\nabla_\theta f\left(\theta_n, x_n\right)}^{\text {stochastic gradient }}-\overbrace{\mathbb{E}\left[\nabla_\theta f\left(\theta_n, X\right)\right]}^{\text {true gradient }}|}{\underbrace{c\left|\theta_n-\theta^*\right|}_{\text {distance to the optimal solution }}} \] 其中：

• 分子是随机梯度和真实梯度的绝对误差；
• 分母是当前估计和目标解的距离，显然：当 \(\theta_n\) 与 \(\theta^*\) 距离比较远的时候，SGD 呈现出来的行为跟 GD 差不多，因为相对误差较小；当距离较近的时候，才会出现比较大的随机性。

BGD vs. MBGD vs. SGD

当我们获取了一组随机数据 \(\left\{x_i\right\}_{i=1}^n\) 后，其实有以下三种用法：

• BGD（Batch Gradient Descent）：每次迭代都使用整个数据集计算梯度，计算开销大，但收敛稳定。 \[ \theta_{n+1}=\theta_n-\alpha_n \frac{1}{n} \sum_{i=1}^n \nabla_\theta f\left(\theta_n, x_i\right) \]

• MBGD（Mini-Batch Gradient Descent）：每次使用数据集的一个小批次计算梯度，权衡了计算效率和收敛稳定性。 \[ \theta_{n+1}=\theta_n-\alpha_n \frac{1}{m} \sum_{j \in \mathcal{I}_n} \nabla_\theta f\left(\theta_n, x_j\right) \]

• SGD（Stochastic Gradient Descent）：每次使用一个样本计算梯度，计算开销最小，但收敛较慢，波动较大。 \[ \theta_{n+1}=\theta_n-\alpha_n \nabla_\theta f\left(\theta_n, x_n\right) \]

在实践中，MBGD 结合了 BGD 和 SGD 的优点，成为最常用的梯度下降变种。