强化学习的数学基础 - Chapter 6

赵老师开源的 Github 仓库、赵老师的 B站 课程视频

背景来自 XHS 真理线_ 《世界在下沉 我们在相爱》

Overview

上一讲介绍了蒙特卡洛学习，下一讲将介绍时序差分（Temporal-Difference，TD）学习。本讲我们按下暂停键，做好知识准备。

为什么需要本讲？

• TD 算法的思路和表达式与此前研究的算法有很大不同。
• 许多初次接触 TD 算法的学生可能会疑惑：这些算法最初为何这样设计？它们为何有效？
• 存在知识鸿沟！

本讲内容：通过介绍基本的随机逼近（Stochastic Approximation，SA）算法，填补之前和后续讲座之间的知识鸿沟。下一讲将看到，时序差分算法是特殊的 SA 算法，因此理解这些算法会容易得多。

Outline

1. 动机示例
2. Robbins-Monro 算法
3. 随机梯度下降
4. BGD、MBGD 与 SGD 之间的比较

---

引入：估计均值

Lec 21

问题回顾

考虑一个随机变量 $X$，目标是估计 $\mathbb{E}[X]$。假设收集了一组 i.i.d. 样本 $\{x_i\}_{i=1}^N$，则：

$$\mathbb{E}[X] \approx \bar{x} := \frac{1}{N}\sum_{i=1}^N x_i$$

新问题：如何计算均值 $\bar{x}$？有两种方式：

1. 第一种方式：收集所有样本然后计算平均值。
   • 缺点：如果样本是逐个收集的，必须等到所有样本收集完毕才能计算
2. 第二种方式：以 增量迭代 的方式计算平均值，避免等待。

增量式均值估计

如果设

$$w_{k+1} = \frac{1}{k}\sum_{i=1}^k x_i, \quad k=1,2,\ldots$$

则有，

$$w_k = \frac{1}{k-1}\sum_{i=1}^{k-1} x_i, \quad k=2,3,\ldots$$

用 $w_k$ 和 $x_k$ 来表示 $w_{k+1}$，以构造迭代算法，

$$\begin{align*} w_{k+1} &= \frac{1}{k}\sum_{i=1}^k x_i = \frac{1}{k}\left(\sum_{i=1}^{k-1} x_i + x_k\right) \\ &= \frac{1}{k}((k-1)w_k + x_k) = w_k - \frac{1}{k}(w_k - x_k) \end{align*}$$

因此得到迭代算法：

$$\color{lightgreen}{w_{k+1} = w_k - \frac{1}{k}(w_k - x_k)}$$

• 一旦收到一个样本，就可以立即获得均值估计。
• 初始时由于样本不足，估计不准确（$w_k \neq \mathbb{E}[X]$），但总比没有好。随着更多样本的获得，估计会逐渐改进（$w_k \to \mathbb{E}[X]$ 当 $k \to \infty$）。

考虑更一般的算法：

$$w_{k+1} = w_k - \alpha_k(w_k - x_k)$$

其中，$1/k$ 被 $\alpha_k > 0$ 替代。

• 该算法是否仍收敛到 $\mathbb{E}[X]$？答案是肯定的，只要 $\{\alpha_k\}$ 满足某些条件。
• 该算法是特殊的 SA 算法，也是特殊的随机梯度下降算法。
• 下一讲将看到时序差分算法具有类似（但更复杂）的形式。

---

Robbins-Monro 算法

Lec 22 & 23

问题设置

随机逼近（Stochastic Approximation，SA）：泛指一类求解求根或优化问题的 随机迭代算法。

• SA 的强大之处在于：不需要知道目标函数的表达式或其导数。

Robbins-Monro（RM）算法：是随机逼近领域的开创性工作。著名的随机梯度下降算法是 RM 算法的特殊形式。

问题陈述：求方程 $g(w) = 0$ 的根，其中 $w \in \mathbb{R}$ 是待求解的变量，$g: \mathbb{R} \to \mathbb{R}$ 是一个函数。

许多问题最终可以转化为这个求根问题。例如，若 $J(w)$ 是要最小化的目标函数，则优化问题可以转化为 $g(w) = \nabla_w J(w) = 0$。

核心问题：如果不知道 $g$ 或其导数的表达式怎么办？

RM 算法

$$w_{k+1} = w_k - a_k \tilde{g}(w_k, \eta_k),\quad k=1,2,3,\ldots$$

其中：

• $w_k$ 是第 $k$ 次对根的估计
• $\tilde{g}(w_k, \eta_k) = g(w_k) + \eta_k$ 是第 $k$ 次带噪声的观测
• $a_k$ 是正系数

函数 $g(w)$ 是一个黑箱！该算法依赖数据：

• 输入序列：$\{w_k\}$
• 带噪声的输出序列：$\{\tilde{g}(w_k, \eta_k)\}$

哲学：没有模型，就需要数据！这里的模型指函数的表达式。

两个示例

示例1：手动求解 $g(w) = w - 10$。设 $w_1 = 20$，$a_k \equiv 0.5$，$\eta_k = 0$。

• $w_1 = 20 \implies g(w_1) = 10$
• $w_2 = w_1 - a_1 g(w_1) = 20 - 0.5 \times 10 = 15$
• $w_3 = w_2 - a_2 g(w_2) = 15 - 0.5 \times 5 = 12.5$
• $\ldots$
• $w_k \to 10$

示例2：求解 $g(w) = w^3 - 5$.

• 真实根为 $5^{1/3} \approx 1.71$。
• 我们只知道 $\tilde{g}(w) = g(w) + \eta$。
• 假设 $\eta_k$ 是独立同分布的，且服从均值为零、标准差为 $1$ 的标准正态分布。
• 初始猜测为 $w_1 = 0$，步长 $a_k$ 取为 $a_k = 1/k$。

$w_k$ 的演化过程如下图所示。可以看出，估计值 $w_k$ 能够收敛到真实根。

w 和 eta 的数值曲线

收敛性分析

一个直观的例子：

• $g(w) = \tanh(w-1)$
• $g(w) = 0$ 的真实根为 $w^* = 1$。
• 参数取：$w_1 = 3$，$a_k = 1/k$，$\eta_k \equiv 0$（为简化起见，无噪声）

在此情况下的 RM 算法为

$$w_{k+1} = w_k - a_k g(w_k)$$

因为当 $\eta_k = 0$ 时，$\tilde{g}(w_k, \eta_k) = g(w_k)$。

绘制出的结果

这里能保证 $w_{k+1}$ 比 $w_k$ 更接近 $w^*$ 的前提是，$a_k$ 需要足够小

• 当 $w_k > w^*$ 时，$g(w_k) > 0$，则 $w_{k+1} = w_k - a_k g(w_k) < w_k$，更接近 $w^*$。
• 当 $w_k < w^*$ 时，$g(w_k) < 0$，则 $w_{k+1} = w_k - a_k g(w_k) > w_k$，更接近 $w^*$。

Robbins-Monro 定理：在 RM 算法中，若满足以下条件：

1. $0 < c_1 \leq \nabla_w g(w) \leq c_2$ 对所有 $w$ 成立
2. $\sum_{k=1}^\infty a_k = \infty$ 且 $\sum_{k=1}^\infty a_k^2 < \infty$
3. $\mathbb{E}[\eta_k | \mathcal{H}_k] = 0$ 且 $\mathbb{E}[\eta_k^2 | \mathcal{H}_k] < \infty$

则 $w_k$ 以概率 1 收敛到满足 $g(w^*) = 0$ 的根 $w^*$。

条件解释：

1. $g$ 单调递增，保证根存在且唯一；梯度有上界。
2. $\sum a_k^2 < \infty$ 确保 $a_k \to 0$；$\sum a_k = \infty$ 确保 $a_k$ 不会收敛到零太快。
3. $\{\eta_k\}$ 满足零均值和有限方差。

满足条件的典型序列：$a_k = 1/k$，$\sum_{k=1}^\infty 1/k = \infty$，$\sum_{k=1}^\infty 1/k^2 = \pi^2/6 < \infty$

但在实际应用中，我们通常会选择一个非常小的正常数作为 $a_k$，因为令 $a_k = 1/k$ 会导致后面进来的数据影响越来越小，这不利于我们充分利用后续数据。

对第二个条件的详细分析

更仔细地考察第二个条件：

$$\sum_{k=1}^{\infty} a_k^2 < \infty, \quad \sum_{k=1}^{\infty} a_k = \infty$$

首先，$\sum_{k=1}^{\infty} a_k^2 < \infty$ 表明当 $k \to \infty$ 时，$a_k \to 0$。

由于

$$w_{k+1} - w_k = -a_k \tilde{g}(w_k, \eta_k),$$

1. 如果 $a_k \to 0$，那么 $a_k \tilde{g}(w_k, \eta_k) \to 0$，因此 $w_{k+1} - w_k \to 0$。
2. 如果 $w_k$ 最终收敛，我们需要 $w_{k+1} - w_k \to 0$ 这一事实。
3. 如果 $w_k \to w^*$，则 $g(w_k) \to 0$，且 $\tilde{g}(w_k, \eta_k)$ 由 $\eta_k$ 主导。

其次，$\sum_{k=1}^{\infty} a_k = \infty$ 表明 $a_k$ 不应过快地收敛到零。

结合 $w_2 = w_1 - a_1 \tilde{g}(w_1, \eta_1)$, $w_3 = w_2 - a_2 \tilde{g}(w_2, \eta_2)$, $\dots$, $w_{k+1} = w_k - a_k \tilde{g}(w_k, \eta_k)$ 可得

$$w_1 - w_{\infty} = \sum_{k=1}^{\infty} a_k \tilde{g}(w_k, \eta_k).$$

假设 $w_{\infty} = w^*$。如果 $\sum_{k=1}^{\infty} a_k < \infty$，那么 $\sum_{k=1}^{\infty} a_k \tilde{g}(w_k, \eta_k)$ 可能是有界的（此时，如果初始设置的 $w_1$ 不幸离 $w^*$ 较远，则上述等式将不成立）。

对均值估计的 RM 解释

均值估计算法 $w_{k+1} = w_k + \alpha_k(x_k - w_k)$ 可视为 RM 算法的特例：

1. 定义函数 $g(w) = w - \mathbb{E}[X]$，目标是求解 $g(w) = 0$
2. 可获得的观测为 $\tilde{g}(w, x) = w - x = (w - \mathbb{E}[X]) + (\mathbb{E}[X] - x) = g(w) + \eta$
3. RM 算法：$w_{k+1} = w_k - \alpha_k \tilde{g}(w_k, \eta_k) = w_k - \alpha_k(w_k - x_k)$，正是均值估计算法！

Dvoretzky 定理

Dvoretzky 定理：考虑随机过程 $w_{k+1} = (1 - \alpha_k)w_k + \beta_k \eta_k$. 若满足

1. $\sum \alpha_k = \infty$、$\sum \alpha_k^2 < \infty$、$\sum \beta_k^2 < \infty$
2. $\mathbb{E}[\eta_k|\mathcal{H}_k] = 0$、$\mathbb{E}[\eta_k^2|\mathcal{H}_k] \leq C$，

则 $w_k$ 以概率 1 收敛到零。

其中，$\mathcal{H}_k = \{w_k, w_{k-1}, \dots, \eta_{k-1}, \cdots, \alpha_{k-1}, \cdots,\beta_{k-1},\cdots \}$

该定理比 RM 定理更一般，可用于证明 RM 定理，也可直接分析均值估计问题，其扩展可用于分析 Q-learning 和 TD 学习算法。

---

SGD

Lec 24 & 25

随机梯度下降在机器学习和 RL 中广泛使用。SGD 是 RM 算法的特殊形式，而均值估计算法是 SGD 的特殊形式。

问题描述

求解优化问题：

$$\min_w J(w) = \mathbb{E}[f(w, X)]$$

其中 $w$ 是待优化参数，$X$ 是随机变量。

• 方法1：梯度下降（Gradient Descent，GD）

  $$w_{k+1} = w_k - \alpha_k \nabla_w \mathbb{E}[f(w_k, X)] = w_k - \alpha_k \mathbb{E}[\nabla_w f(w_k, X)]$$

  缺点：期望值难以获得。

• 方法2：批量梯度下降（Batch Gradient Descent，BGD）

  $$\mathbb{E}[\nabla_w f(w_k, X)] \approx \frac{1}{n}\sum_{i=1}^n \nabla_w f(w_k, x_i)$$

  $$w_{k+1} = w_k - \alpha_k \frac{1}{n} \sum_{i=1}^n \nabla_w f(w_k, x_i)$$

  缺点：每次迭代需要大量样本。

• 方法3：随机梯度下降（Stochastic Gradient Descent，SGD）

  $$w_{k+1} = w_k - \alpha_k \nabla_w f(w_k, x_k)$$

  • 与 GD 相比：用随机梯度 $\nabla_w f(w_k, x_k)$ 替代真实梯度 $\mathbb{E}[\nabla_w f(w_k, X)]$
  • 与 BGD 相比：取 $n = 1$

示例

我们考虑例子：

$$\min_w J(w) = \mathbb{E}[f(w, X)] = \mathbb{E}\left[\frac{1}{2}\|w - X\|^2\right],$$

其中

$$f(w, X) = \|w - X\|^2 / 2, \quad \nabla_w f(w, X) = w - X$$

可以推导出，其最优解 $w^* = \mathbb{E}[x]$ ！这是因为，

$$\begin{align*} \nabla_{w^*} \ J(w^*) = 0 &\implies \nabla_{w^*} \ \mathbb{E}[f(w^*, X)] = 0 \implies \mathbb{E}[\nabla_{w^*} \ f(w^*, X)] = 0 \\ & \implies \mathbb{E}[w^* - X] = 0 \implies w^* = \mathbb{E}[X] \end{align*}$$

• 求解上述问题的 GD 算法为，

  $$\begin{align*} w_{k+1} &= w_k - \alpha_k \nabla_w J(w_k) \\ &= w_k - \alpha_k \mathbb{E}[\nabla_w f(w_k, X)] \\ &= w_k - \alpha_k \mathbb{E}[w_k - X]. \end{align*}$$

• 求解上述问题的 SGD 算法为，

  $$w_{k+1} = w_k - \alpha_k \nabla_w f(w_k, x_k) = w_k - \alpha_k (w_k - x_k)$$

  • 它与我们之前介绍的均值估计算法相同。
  • 该均值估计算法是一种特殊的 SGD 算法。

SGD 的收敛性

$$\begin{align*} \text{GD：} &w_{k+1} = w_k - \alpha_k \mathbb{E}[\nabla_w f(w_k, X)] \\ \text{SGD：} &w_{k+1} = w_k - \alpha_k \nabla_w f(w_k, x_k) \end{align*}$$

$\nabla_w f(w_k, x_k)$ 可以被视为 $\mathbb{E}[\nabla_w f(w, X)]$ 的一个带噪声的测量：

$$\nabla_w f(w_k, x_k) = \mathbb{E}[\nabla_w f(w, X)] + \underbrace{\nabla_w f(w_k, x_k) - \mathbb{E}[\nabla_w f(w, X)]}_{\eta}.$$

由于 $\nabla_w f(w_k, x_k) \neq \mathbb{E}[\nabla_w f(w, X)]$，通过 SGD，当 $k \to \infty$ 时，$w_k$ 是否收敛到 $w^*$？

下面我们证明 SGD 是一种特殊的 RM 算法。那么，其收敛性自然随之而来。

SGD 的目标是极小化

$$J(w) = \mathbb{E}[f(w, X)]$$

该问题可以转化为一个求根问题：

$$\nabla_w J(w) = \mathbb{E}[\nabla_w f(w, X)] = 0$$

令

$$g(w) = \nabla_w J(w) = \mathbb{E}[\nabla_w f(w, X)].$$

那么，SGD 的目标就是求 $g(w) = 0$ 的根。

我们能够测量的是，

$$\begin{align*} \tilde{g}(w, \eta) &= \nabla_w f(w, x) \\ &= \underbrace{\mathbb{E}[\nabla_w f(w, X)]}_{g(w)} + \underbrace{\nabla_w f(w, x) - \mathbb{E}[\nabla_w f(w, X)]}_{\eta}. \end{align*}$$

那么，求解 $g(w) = 0$ 的 RM 算法为

$$w_{k+1} = w_k - a_k \tilde{g}(w_k, \eta_k) = w_k - a_k \nabla_w f(w_k, x_k).$$

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

SGD 的收敛性定理：SGD 算法若满足：

1. $0 < c_1 \leq \nabla_w^2 f(w, X) \leq c_2$
2. $\sum_{k=1}^\infty a_k = \infty$ 且 $\sum_{k=1}^\infty a_k^2 < \infty$
3. $\{x_k\}_{k=1}^\infty$ 是 i.i.d.

则 $w_k$ 以概率 1 收敛到 $\nabla_w \mathbb{E}[f(w, X)] = 0$ 的根。

SGD 的收敛模式

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

为了回答这个问题，我们考虑随机梯度与批量梯度之间的相对误差：

$$\delta_k \doteq \frac{|\nabla_w f(w_k, x_k) - \mathbb{E}[\nabla_w f(w_k, X)]|}{|\mathbb{E}[\nabla_w f(w_k, X)]|}.$$

由于 $\mathbb{E}[\nabla_w f(w^*, X)] = 0$，我们进一步有

$$\delta_k = \frac{|\nabla_w f(w_k, x_k) - \mathbb{E}[\nabla_w f(w_k, X)]|}{|\mathbb{E}[\nabla_w f(w_k, X)] - \mathbb{E}[\nabla_w f(w^*, X)]|} = \frac{|\nabla_w f(w_k, x_k) - \mathbb{E}[\nabla_w f(w_k, X)]|}{|\mathbb{E}[\nabla_w^2 f(\tilde{w}_k, X)(w_k - w^*)]|}.$$

其中，最后一个等式由中值定理得到，且 $\tilde{w}_k \in [w_k, w^*]$。

假设 $f$ 是严格凸的，使得

$$\nabla_w^2 f \geq c > 0, \quad \forall w, X$$

其中，$c$ 是一个正的下界。那么，$\delta_k$ 的分母变为

$$\begin{aligned} |\mathbb{E}[\nabla_w^2 f(\tilde{w}_k, X)(w_k - w^*)]| &= |\mathbb{E}[\nabla_w^2 f(\tilde{w}_k, X)](w_k - w^*)| \\ &= |\mathbb{E}[\nabla_w^2 f(\tilde{w}_k, X)]| |(w_k - w^*)| \geq c|w_k - w^*|. \end{aligned}$$

将上述不等式代入 $\delta_k$ 可得

$$\delta_k \leq \frac{|\nabla_w f(w_k, x_k) - \mathbb{E}[\nabla_w f(w_k, X)]|}{c|w_k - w^*|}.$$

注意到，

$$\delta_k \leq \frac{\overbrace{|\nabla_w f(w_k, x_k) - \mathbb{E}[\nabla_w f(w_k, X)]|}^{\text{随机梯度} \quad \text{真实梯度}}}{\underbrace{c|w_k - w^*|}_{\text{到最优解的距离}}}.$$

上述等式揭示了 SGD 一种有趣的收敛模式。

• 相对误差 $\delta_k$ 与 $|w_k - w^*|$ 成反比。
• 当 $|w_k - w^*|$ 较大时，$\delta_k$ 较小，SGD 表现得像 GD。
• 当 $w_k$ 接近 $w^*$ 时，相对误差可能较大，收敛在 $w^*$ 的邻域内表现出更多的随机性。

例子

$X \in \mathbb{R}^2$ 表示平面上的一个随机位置。其分布以原点为中心、边长为 20 的正方形区域内均匀分布。真实均值为 $\mathbb{E}[X] = 0$。均值估计基于 100 个独立同分布样本 $\{x_i\}_{i=1}^{100}$。

SGD 的计算结果

• 尽管均值的初始猜测远离真实值，SGD 估计仍能快速接近真实值的邻域。
• 当估计接近真实值时，它会表现出一定的随机性，但仍会逐渐逼近真实值。

SGD 的确定性形式

• 我们上面介绍的 SGD 形式涉及随机变量和期望。
• 在其他地方经常会遇到一种确定性的 SGD 形式，其中不涉及任何随机变量。

考虑如下优化问题：

$$\min_w \ J(w) = \frac{1}{n} \sum_{i=1}^{n} f(w, x_i),$$

• $f(w, x_i)$ 是一个参数化函数。
• $w$ 是待优化的参数。
• $\{x_i\}_{i=1}^{n}$ 是一组实数，其中 $x_i$ 不必是任何随机变量的样本。

求解该问题的 GD 算法为

$$w_{k+1} = w_k - \alpha_k \nabla_w J(w_k) = w_k - \alpha_k \frac{1}{n} \sum_{i=1}^{n} \nabla_w f(w_k, x_i).$$

假设该集合很大，我们每次只能获取一个数。在这种情况下，我们可以使用如下迭代算法：

$$w_{k+1} = w_k - \alpha_k \nabla_w f(w_k, x_k).$$

问题：

• 这个算法是 SGD 吗？它并不涉及任何随机变量或期望值。
• 我们应该如何使用这组有限的数 $\{x_i\}_{i=1}^{n}$？我们应该按某种顺序对这些数排序然后逐个使用？还是应该从集合中随机采样一个数？

Idea：我们可以手动引入一个随机变量，将确定性形式转化为 SGD 的随机形式。

特别地，假设 $X$ 是定义在集合 $\{x_i\}_{i=1}^{n}$ 上的一个随机变量。假设其概率分布是均匀的，即

$$p(X = x_i) = 1/n$$

那么，该确定性优化问题就变成了一个随机优化问题：

$$\min_w \ J(w) = \frac{1}{n} \sum_{i=1}^{n} f(w, x_i) = \mathbb{E}[f(w, X)].$$

• 上述等式中的最后一个等号是严格相等，而非近似。因此，该算法是 SGD。
• 如果 $x_k$ 是从 $\{x_i\}_{i=1}^{n}$ 中均匀且独立地采样得到的，则估计收敛。由于 $x_k$ 是随机采样的，它可能会重复取到 $\{x_i\}_{i=1}^{n}$ 中的同一个数。

---

BGD，MBGD 与 SGD

Lec 26

给定随机样本 $\{x_i\}_{i=1}^n$，目标是最小化 $J(w) = \mathbb{E}[f(w, X)]$：

• BGD：$w_{k+1} = w_k - \alpha_k \frac{1}{n}\sum_{i=1}^n \nabla_w f(w_k, x_i)$
• MBGD：$w_{k+1} = w_k - \alpha_k \frac{1}{m}\sum_{j \in I_k} \nabla_w f(w_k, x_j)$
• SGD：$w_{k+1} = w_k - \alpha_k \nabla_w f(w_k, x_k)$

比较：

• BGD 每次迭代使用所有样本，当 $n$ 大时接近真实梯度
• MBGD 的 $I_k$ 是大小为 $m$ 的子集，通过 $m$ 次 i.i.d. 采样获得
• SGD 在时刻 $k$ 从 $\{x_i\}$ 中随机采样 $x_k$

MBGD 与其他算法的关系：

• 相比 SGD，MBGD 随机性更小（使用更多样本）
• 相比 BGD，MBGD 不需要每次使用所有样本，更灵活高效
• 若 $m=1$，MBGD 变为 SGD
• 若 $m=n$，MBGD 并非严格意义上的 BGD（MBGD 可能多次使用同一值，而 BGD 每个数只用一次）

例子

给定一些数 $\{x_i\}_{i=1}^{n}$，我们的目标是计算均值 $\bar{x} = \sum_{i=1}^{n} x_i / n$。该问题可以等价地表述为如下优化问题：

$$\min_w \ J(w) = \frac{1}{2n} \sum_{i=1}^{n} \|w - x_i\|^2$$

求解该问题的三种算法分别为：

$$\begin{align*} w_{k+1} &= w_k - \alpha_k \frac{1}{n} \sum_{i=1}^{n} (w_k - x_i) = w_k - \alpha_k (w_k - \bar{x}), \qquad \text{(BGD)} \\ w_{k+1} &= w_k - \alpha_k \frac{1}{m} \sum_{j \in \mathcal{I}_k} (w_k - x_j) = w_k - \alpha_k \left(w_k - \bar{x}_k^{(m)}\right), \qquad \text{(MBGD)} \\ w_{k+1} &= w_k - \alpha_k (w_k - x_k), \qquad \text{(SGD)} \end{align*}$$

其中，$\bar{x}_k^{(m)} = \sum_{j \in \mathcal{I}_k} x_j / m$.

此外，如果 $\alpha_k = 1/k$，则上述方程可以求解为

$$\begin{align*} w_{k+1} &= \frac{1}{k} \sum_{j=1}^{k} \bar{x} = \bar{x}, \qquad \text{(BGD)} \\ w_{k+1} &= \frac{1}{k} \sum_{j=1}^{k} \bar{x}_j^{(m)}, \qquad \text{(MBGD)} \\ w_{k+1} &= \frac{1}{k} \sum_{j=1}^{k} x_j. \qquad \text{(SGD)} \end{align*}$$

MBGD 和 SGD 的计算结果

• BGD 在每一步的估计值恰好就是最优解 $w^* = \bar{x}$。
• MBGD 的估计值比 SGD 更快地逼近均值，因为 $\bar{x}_k^{(m)}$ 已经是一个平均值。

---

总结

• 均值估计：使用 $\{x_k\}$ 计算 $\mathbb{E}[X]$，

  $$w_{k+1} = w_k - \frac{1}{k}(w_k - x_k)$$

• RM 算法：使用 $\{\tilde{g}(w_k, \eta_k)\}$ 求解 $g(w) = 0$，

  $$w_{k+1} = w_k - a_k \tilde{g}(w_k, \eta_k)$$

• SGD 算法：使用 $\{\nabla_w f(w_k, x_k)\}$ 最小化 $J(w) = \mathbb{E}[f(w, X)]$，

  $$w_{k+1} = w_k - \alpha_k \nabla_w f(w_k, x_k)$$

这些结果非常有用：

• 下一章将看到时序差分学习算法可视为随机逼近算法，因此具有类似的表达式。
• 它们是可以应用于许多其他领域的重要优化技术。