《强化学习的数学原理》【学习笔记06】随机近似算法：在线学习的数学基础

《强化学习的数学原理》赵世钰 著 · 第 6 章

本章是全书的"数学工具箱"。第 5 章的蒙特卡罗方法用样本均值估计期望，但每次都从头算。能不能增量式更新？这需要随机近似理论。

一、从期望值估计说起

批量 vs 增量

批量更新（MC 方法的做法）：

$$\bar{x}_N = \frac{1}{N} \sum_{i=1}^{N} x_i$$

每来一个新样本，要重新算所有样本的均值。

增量更新：

$$\bar{x}_{N} = \bar{x}_{N-1} + \frac{1}{N}(x_N - \bar{x}_{N-1})$$

只保留上一次的均值，用新样本做小修正。这大大节省了内存。

这个递推公式怎么来的？ 纯代数推导：

$$\bar{x}_N = \frac{1}{N}\sum_{i=1}^N x_i = \frac{1}{N}\left(\sum_{i=1}^{N-1} x_i + x_N\right) = \frac{N-1}{N}\bar{x}_{N-1} + \frac{1}{N}x_N = \bar{x}_{N-1} + \frac{1}{N}(x_N - \bar{x}_{N-1})$$

二、罗宾斯-门罗算法（Robbins-Monro Algorithm）

一般形式

$$w_{t+1} = w_t - \alpha_t g(w_t, X_t)$$

其中 $g(w_t, X_t)$ 是一个随机量，$w_t$ 是要估计的参数，$\alpha_t$ 是步长。

收敛条件

步长序列 $\{\alpha_t\}$ 需要满足 Robbins-Monro 条件：

$$\sum_{t=0}^{\infty} \alpha_t = \infty, \quad \sum_{t=0}^{\infty} \alpha_t^2 < \infty$$

直觉理解：

• $\sum \alpha_t = \infty$：步长不能衰减太快，否则总更新量不够
• $\sum \alpha_t^2 < \infty$：步长不能衰减太慢，否则噪声累积不收敛

典型选择：$\alpha_t = \frac{c}{t}$ 或 $\alpha_t = \frac{c}{t + a}$。

为什么 $\alpha_t = \frac{1}{t}$ 满足条件？

• $\sum \frac{1}{t} = \infty$（调和级数发散）✓
• $\sum \frac{1}{t^2} < \infty$（p-级数收敛）✓

在期望值估计中的应用

设要估计 $\mathbb{E}[X]$，用 Robbins-Monro 算法：

$$w_{t+1} = w_t - \alpha_t (w_t - x_t) = (1 - \alpha_t) w_t + \alpha_t x_t$$

在 RM 条件下，$w_t \to \mathbb{E}[X]$。

三、Dvoretzky 定理

这是随机近似理论的最一般定理，Robbins-Monro 是它的特例。

定理形式

考虑迭代：

$$\Delta_{t+1} = (1 - \alpha_t)\Delta_t + \beta_t + \eta_t$$

如果：

1. $\alpha_t \geq 0$, $\sum \alpha_t = \infty$, $\sum \alpha_t^2 < \infty$
2. $\mathbb{E}[\beta_t | \mathcal{F}_t] = 0$, $\sum \mathbb{E}[\beta_t^2] < \infty$
3. $\mathbb{E}[\eta_t | \mathcal{F}_t] \leq 0$（漂移项非正）

则 $\Delta_t \to 0$（依概率收敛）。

直觉：$\alpha_t$ 控制衰减速度，$\beta_t$ 是零均值噪声，$\eta_t$ 是向零漂移的力。三者共同保证收敛。本书用这个定理统一证明了多种 RL 算法的收敛性。

四、随机梯度下降（SGD）

从梯度下降到随机梯度下降

梯度下降（GD）：

$$w_{t+1} = w_t - \alpha \nabla J(w_t)$$

需要计算全量数据的梯度，代价 $O(N)$。

随机梯度下降（SGD）：

$$w_{t+1} = w_t - \alpha_t \nabla J(w_t, x_t)$$

每次只用一个样本 $x_t$ 的梯度，代价 $O(1)$。

关键性质

$$\mathbb{E}[\nabla J(w_t, x_t)] = \nabla J(w_t)$$

即随机梯度的期望等于真实梯度。这使得 SGD 是 GD 的无偏随机近似。

在期望值估计中的应用

目标函数 $J(w) = \frac{1}{2}\mathbb{E}[(w - X)^2]$，梯度 $\nabla J = \mathbb{E}[w - X]$。

SGD 更新：

$$w_{t+1} = w_t - \alpha_t (w_t - x_t)$$

这与 Robbins-Monro 算法完全一致！说明 SGD 是 RM 的特例。

五、SGD 的收敛模式

三种收敛模式

小批量梯度下降

$$w_{t+1} = w_t - \alpha \frac{1}{m} \sum_{i=1}^{m} \nabla J(w_t, x_{t,i})$$

用 $m$ 个样本的平均梯度，方差更小，但每步代价 $O(m)$。

实践智慧：小批量是"方差-效率"的折中。$m = 1$ 是纯 SGD（高方差，低成本），$m = N$ 是 GD（零方差，高成本）。深度学习中通常选 $m = 32 \sim 256$。

六、为什么本章重要？

本章看似与强化学习无关，但实际上它是第 7 章（TD 方法）和第 8 章（值函数近似）的数学基础：

第 6 章（随机近似）
    ↓
第 7 章 TD 方法的收敛性证明
    ↓
第 8 章 值函数近似的优化算法
    ↓
第 9-10 章 策略梯度和 Actor-Critic 的优化

没有随机近似理论，就无法证明 TD(0) 收敛、无法分析 Q-learning 的稳定性。

七、总结