《强化学习的数学原理》(2024春)_西湖大学赵世钰 Ch6 随机近似 和 随机梯度下降 【non-incremental —＞ incremental 增量】_赵世钰老师书籍

PPT 截取必要信息。 课程网站做习题。总体 MOOC 过一遍

• 1、视频 1 + 学堂在线 习题
• 2、视频 2，过 电子书 是否遗漏， 【下载：本章 PDF GitHub页面链接】
• 3、MOOC 习题过一遍
• 跳过的部分

学堂在线 课程页面链接
中国大学MOOC 课程页面链接
B 站 视频链接

PPT和书籍下载网址： 【GitHub链接】

---

Stochastic Approximation：随机近似
Stochastic Gradient Descent：随机梯度下降

第 7 章 的 Temporal-Difference Learning 是 Stochastic Approximation 的一个特殊情况。

随机梯度下降 是 RM 算法的特例
4、Batch Gradient Descent、Mini-batch Gradient Descent、Stochastic Gradient Descent。

蒙特卡洛估计 的基本思想： $当N\to \infty ，\bar{x}\to \mathbb{E}[X]$

强化学习中的 状态值 和 动作值等 均定义为 均值。

计算 $\bar{x}$ 的两种方式：
1、收集所有样本，然后计算平均值。

• 如果样本数量很大，我们可能需要等待很长时间才能收集到所有的样本。

2、增量和迭代的方式计算平均值。

计算 $\bar{x}$ 的迭代 增量式 方法：
前 k 个 样本的均值：$w_{k+1}=\frac{1}{k}\sum _{i=1}^k{x}_i，k=1,2,...$
前 k - 1 个 样本的均值：$w_k=\frac{1}{k-1}\sum _{i=1}^{k-1}{x}_i，k=2,3$
w k + 1 = 1 k ∑ i = 1 k x i = 1 k ( ∑ i = 1 k − 1 x i + x k ) = 1 k ( ( k − 1 ) w k + x k ) = w k − 1 k ( w k − x k )

$$\begin{align*}w_{k+1} &= \frac{1}{k}\sum_{i=1}^kx_i\\ &=\frac{1}{k}(\sum_{i=1}^{k-1}x_i+x_k)\\ &=\frac{1}{k}((k-1)w_k+x_k)\\ &=w_k-\frac{1}{k}(w_k-x_k)\end{align*}$$ wk+1​​=k1​i=1∑k​xi​=k1​(i=1∑k−1​xi​+xk​)=k1​((k−1)wk​+xk​)=wk​−k1​(wk​−xk​)​

优点：一旦接收到样本，可以立即得到均值估计。

由于样本不足，最初的近似可能不准确。
随着样本量的增加，可以根据大数定律逐步提高估计精度。

$w_{k+1}=w_k-{\alpha }_k(w_k-x_k)$
特殊的 随机近似算法， 特殊的随机梯度下降算法。

6.2 Robbins-Monro (RM) 算法

Stochastic approximation (SA)：随机近似
SA 是指解决 寻根 或 优化问题的一大类随机迭代算法。
相比于其它寻根算法，SA 的强大之处在于它不需要知道 目标函数的表达式及其导数。

Robbins-Monro (RM) 算法：
stochastic gradient descent 算法 是 RM 算法的特殊形式。

可用于 分析 均值估计算法。

问题：找方程的根。
$$g(w)=0$$
$w\in \mathbb{R}$ 待解变量
$g$：$\mathbb{R}\to \mathbb{R}$ 方程
——————
假设 最小优化问题的目标函数为 $J(w)$
该优化问题可转成 $g(w)={▽}_{w}J(w)=0$

如何计算 $g(w)=0$ 的根？
情形 1 ： $g$ 的表达式或它的导数已知，数值算法。
情形 2 ： $g$ 的表达式未知 ——> 神经网络 表示函数

通过 RM 算法 求解 以下问题：
$$w_{k+1}=w_k-a_k\tilde{g}(w_k,{\eta }_k),k=1,2,3,...$$

• $w_k$： 根的第 $k$ 次估计值。
• 第 $k$ 次带误差的观测值： $\tilde{g}(w_k,{\eta }_k)=g(w_k)+{\eta }_k$
• 正 系数 $a_k$

函数 $g(w)$ 是黑盒， 算法依赖数据。

• 输入序列： { w k } \{w_k\} {wk​}
• 有误差的输出序列： { g ~ ( w k , η k ) } \{\widetilde{g}(w_k,\eta_k)\} {g ​(wk​,ηk​)}

无模型 ——> 提供 数据 亦可求解

---

6.2.1 RM 算法的 收敛性质

为什么 RM 算法 可以 找到 $g(w)=0$ 的根 ？

示例：直观说明 RM 算法 为什么收敛

求解 $g(w)=\tanh (w-1)=0$ 的根。
g(w) 的根 $w^{\ast }=1$
为了简化，不考虑 误差。 RM 算法求解该问题的过程如下：

参数： $w_1=3,a_k=1/k,{\eta }_k\equiv 0$
$$w_{k+1}=w_k-a_{k}g(w_k)$$
仿真结果： $w_k$ 收敛到根 $w^{\ast }=1$
  ~  
本次迭代 $w_{k+1}$ 比上一次迭代 $w_k$更接近真值 $w^{\ast }$。
1、当 $w_k>w^{\ast }$，有 $g(w_k)>0$ 【即 $w_k>1$ 时， $g(w_k)=\tanh (w_k-1)>0$】
$w_{k+1}=w_k-a_{k}g(w_k)<w_k$。【减掉正的】。$w_{k+1}$ 比 $w_k$更接近真值 $w^{\ast }$。
  ~  

  ~  
2、当 $w_k<w^{\ast }$，根据方程有 $g(w_k)<0$,
$w_{k+1}=w_k-a_{k}g(w_k)>w_k$。【加 正的】。$w_{k+1}$ 比 $w_k$更接近真值 $w^{\ast }$。
  ~  

$\equiv$$\equiv$

给 一个 $w$，观察输出 $y$， 若是 大于 0， 就小一些，若是 小于 0 ，就大一些。
那变化多少？ ——> RM 算法： $-a_{k}g(w_k)$

Robbins-Monro 定理：
如果以下 3 个条件满足， 则 $w_k$ 以概率 1 收敛到 $w^{\ast }$。其中 根 $w^{\ast }$ 满足 $g(w^{\ast })=0$
1）对所有 $w$， $0<c_1\le {▽}_{w}g(w)\le c_2$; 【要求 梯度 有界】
2）$\sum _{k=1}^{\infty }{a}_k=\infty$, 且 $\sum _{k=1}^{\infty }{a}_k^2<\infty$; 【对 正系数 $a_k$ 的要求：最终收敛到 0 (后面)， 同时不要太快收敛到 0 (前面)】
3）$\mathbb{E}[{\eta }_k|{\mathcal{H}}_k]=0$ 且 $\mathbb{E}[{\eta }_k^2|{\mathcal{H}}_k]<\infty$ 其中 H k = { w k , w k − 1 , . . . } \mathcal H_k=\{w_k,w_{k-1},...\} Hk​={wk​,wk−1​,...}。【对 测量误差 ${\eta }_k$ 的要求】。

with probability 1 (w.p.1)
————————
对 每个条件的进一步说明：
1）对所有 $w$， $0<c_1\le {▽}_{w}g(w)\le c_2$;

• $g$ 是单调递增的，保证了 $g(w)=0$ 的根存在且唯一。【导数为正】
• 梯度有上界。

2）$\sum _{k=1}^{\infty }{a}_k=\infty$ 且 $\sum _{k=1}^{\infty }{a}_k^2<\infty$;

• 前面的条件 保证 $a_k$ 不会太快收敛于 0。
• 后面的条件 保证 $a_k$在 $k\to \infty$ 时收敛到 0。

3）$\mathbb{E}[{\eta }_k|{\mathcal{H}}_k]=0$ 且 $\mathbb{E}[{\eta }_k^2|{\mathcal{H}}_k]<\infty$

• 一个特殊而又常见的情况是 { η k } \{η_k\} {ηk​}是一个满足 $\mathbb{E}[{\eta }_k]=0$ 和 $\mathbb{E}[{\eta }_k^2]<\infty$ 的 iid 【独立同分布】随机序列。观测误差 ${\eta }_k$ 不要求为高斯。

————————
针对 条件 2 进一步讨论：

为什么 条件 $\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)$

当 $a_k\to 0$，右边 $\to 0$。则左边 $w_{k+1}-w_k\to 0$ 【$w_{k+1}$ 和 $w_k$互相靠近】。这样 $w_k$ 才可能 最终收敛。否则 $w_k$ 在 $k\to \infty$ 时仍可能 波动。

2_1 为什么 条件 $\sum _{k=1}^{\infty }{a}_k=\infty$ 重要？
即为什么 需要 $a_k$ 不要 太快收敛到 0?

w 2 = w 1 − a 1 g ~ ( w 1 − η 1 ) w 3 = w 2 − a 2 g ~ ( w 2 − η 2 ) . . . w k + 1 = w k − a k g ~ ( w k − η k )

$$\begin{aligned}w_2&=w_1-a_1\widetilde g(w_1-\eta_1)\\ w_3&=w_2-a_2\widetilde g(w_2-\eta_2)\\ &...\\ w_{k+1} &=w_k-a_k\widetilde g(w_k-\eta_k)\end{aligned}$$ w2​w3​wk+1​​=w1​−a1​g ​(w1​−η1​)=w2​−a2​g ​(w2​−η2​)...=wk​−ak​g ​(wk​−ηk​)​

累加，得到
$w_{\infty }-w_1=\sum _{k=1}^{\infty }{a}_k\tilde{g}(w_k,{\eta }_k)$

如果 $\sum _{k=1}^{\infty }{a}_k<\infty$ ，等式右侧可能是 有界的。
此时有
$|w_{\infty }-w_1|=|\sum _{k=1}^{\infty }{a}_k\tilde{g}(w_k,{\eta }_k)|\le b$

若希望最终收敛，$w_{\infty }=w^{\ast }$，有 $|w^{\ast }-w_1|\le b$

考虑 初步猜测的 $w_1$ 离 $w^{\ast }$ 比较远， 满足 $|w^{\ast }-w_1|>b$。矛盾，意味着 这种情况下不收敛。

因此，需要 $\sum _{k=1}^{\infty }{a}_k=\infty$ ， 用于保证 选择的 $w_1$ 不管离 $w^{\ast }$ 多远， 最后都能收敛。

————————
什么样的 $a_k$ 满足上面的条件 2 呢？
即 $\sum _{k=1}^{\infty }{a}_k^2<\infty$ 且 $\sum _{k=1}^{\infty }{a}_k=\infty$;

• 最终收敛到 0， 同时不要太快收敛到 0 。

$a_k=\frac{1}{k}$
$\underset{n\to \infty }{\lim }(\sum _{k=1}^n\frac{1}{k}-\ln n)=\kappa$。【欧拉常数：Euler-Mascheroni constant、Euler’s constant。 $\kappa \approx 0.577$】
$\sum _{k=1}^{\infty }\frac{1}{k^2}=\frac{{\pi }^2}{6}<\infty$ 【Basel problem】

$\kappa$$\kappa$

如果不满足这三个条件，算法可能无法工作。

• 例如，$g(w)=w^3-5$ 不满足梯度有界性的第一个条件。如果初始猜测是好的，算法可以收敛(局部)。否则，它会发散。

在许多强化学习算法中，$a_k$ 通常被选为一个足够小的常数。在这种情况下，虽然不满足第二个条件，但算法仍然可以有效地工作。

• 虽然 $a_k=\frac{1}{k}$ 时满足条件，但当 $k$ 比较大时， 后面获取的数据 起到的作用将非常小。实际不这样设置。因为仍希望后续获取的数据能发挥作用 ——> 选为 一个 足够小的常数。

——————

6.2.2 将 RM 算法 应用到 均值估计

均值估计算法： $w_{k+1}=w_k+{\alpha }_k(x_k-w_k)$

以下 证明 该均值估计算法 是 RM 算法的特例。

???
考虑 方程 $g(w)\dot{=}w-\mathbb{E}[X]$
目标是 求解 $g(w)=0$
包含误差的观测值 $\tilde{g}(w,\eta )=w-x=(w-\mathbb{E}[X])+(\mathbb{E}[X]-x)\dot{=}g(w)+\eta$
求解 $g(x)=0$ 的 RM算法为：
$w_{k+1}=w_k-{\alpha }_k\tilde{g}(w_k,{\eta }_k)=w_k-{\alpha }_k(w_k-x_k)$
???

————————————

— [选学] Dvoretzkys 收敛定理

考虑 随机过程 $w_{k+1}=(1-{\alpha }_k)w_k+{\beta }_k{\eta }_k$。
其中 { α k } k = 1 ∞ \{\alpha_k\}_{k=1}^\infty {αk​}k=1∞​, { β k } k = 1 ∞ \{\beta_k\}_{k=1}^\infty {βk​}k=1∞​, { η k } k = 1 ∞ \{\eta_k\}_{k=1}^\infty {ηk​}k=1∞​ 为 随机序列。
对所有的 $k$, ${\alpha }_k\ge 0,{\beta }_k\ge 0$。
若是满足 以下两个条件，则 $w_k$ 以概率 1 收敛到 0 。
1) $\sum _{k=1}^{\infty }{\alpha }_k=\infty ,\sum _{k=1}^{\infty }{\alpha }_k^2<\infty ;\sum _{k=1}^{\infty }{\beta }_k^2<\infty 。$w.p.1;
2) $\mathbb{E}[{\eta }_k|{\mathcal{H}}_k]=0,\mathbb{E}[{\eta }_k^2|{\mathcal{H}}_k]\le C$w.p.1; 其中 H k = { w k , w k − 1 , . . . , η k − 1 , . . . , α k − 1 , . . . , β k − 1 , . . . } \mathcal H_k=\{w_k,w_{k-1}, ...,\eta_{k-1},...,\alpha_{k-1},...,\beta_{k-1},...\} Hk​={wk​,wk−1​,...,ηk−1​,...,αk−1​,...,βk−1​,...}

一个比 RM 定理更一般的结果。可用来证明RM 定理
可分析均值估计问题
它的扩展可以用来分析 Q 学习和 TD 学习算法。

6.4 随机梯度下降 (Stochastic gradient descent, SGD)

P3
均值估计算法： 通过迭代方法求解 期望值。

SGD 是 RM 算法的特殊情况，
均值估计算法 是 SGD 的特殊情况。

$均值估计\in SGD,SGD\in RM$

问题： 找 使得函数值最小 的 $w$ ： $\underset{w}{\min }J(w)=\mathbb{E}[f(w,X)]$
待优化参数： $w$
随机变量 $X$，期望 是关于 $X$ 的。

3 种求解方法
最小化
方法一： 梯度下降 (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)]$

• 不足： 关于 $X$ 的期望值 难以 获得
    ~  

方法二：批量梯度下降 (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)$
批次里迭代 求解 期望值。 外面的迭代 求解 $w$

• 不足： 每个 $w_k$ 的一次迭代需要很多样本
    ~  

方法三： 随机梯度下降 (stochastic gradient descent ，SGD)
$w_{k+1}=w_k-{\alpha }_k{\nabla }_{w}f(w_k,x_k)$

• 和 梯度下降 GD 相比， 真实 梯度 $\mathbb{E}[{\nabla }_{w}f(w_k,X)]$ ——> 随机梯度 ${\nabla }_{w}f(w_k,x_k)$
• 和 批次梯度下降 BGD 相比： n = 1

——————

6.4.1 将 SGD 应用到 均值估计

问题：
$\underset{w}{\min }J(w)=\mathbb{E}[f(w,X)]=\mathbb{E}[\frac{1}{2}||w-X|{|}^2]$
$f(w,X)=\frac{1}{2}||w-X|{|}^2$
${\nabla }_{w}f(w,X)=w-X$
可以通过求解 ${\nabla }_{w}J(w)=0$，获得最优解 $w^{\ast }=\mathbb{E}[X]$。
因此，这个优化问题等价于均值估计问题。
————
1、最优解 $w^{\ast }=\mathbb{E}[X]$

  ~  
2、用 梯度下降GD 算法 求解该问题
w k + 1 = w k − α k ∇ w J ( w k ) = w k − α k E [ ∇ w f ( w k , X ) ] = w k − α k E [ w k − X ]

$$\begin{aligned}w_{k+1} &= w_k-\alpha_k\nabla_wJ(w_k)\\ &=w_k-\alpha_k\mathbb E[\nabla_wf(w_k, X)]\\ &=w_k-\alpha_k\mathbb E[w_k-X]\end{aligned}$$ wk+1​​=wk​−αk​∇w​J(wk​)=wk​−αk​E[∇w​f(wk​,X)]=wk​−αk​E[wk​−X]​

• 这种梯度下降算法不适用，因为右边的 $\mathbb{E}[w_k-X]$ 或 $\mathbb{E}[X]$ 是未知的(事实上，这是我们需要求解的)。

3、用 SGD 算法 求解该问题
$w_{k+1}=w_k-{\alpha }_k{\nabla }_{w}f(w_k,x_k)=w_k-{\alpha }_k(w_k-x_k)$
————
和之前的 均值估计 算法相同。 均值估计 算法 $\in SGD$

6.4.2 SGD 的收敛性 分析

SGD 算法的思想是用随机梯度代替真实梯度。然而，由于随机梯度是随机的，有人可能会问 SGD 的收敛速度是慢的还是随机的。幸运的是，SGD 通常可以有效地收敛。
一个有趣的收敛模式是，当估计 $w_k$ 远离最优解 $w^{\ast }$ 时，它的行为类似于常规梯度下降算法。
只有当 $w_k$ 接近 $w^{\ast }$ 时，SGD 的收敛才表现出更大的随机性。

待分析的问题：
GD： $w_{k+1}=w_k-{\alpha }_k\mathbb{E}[{\nabla }_{w}f(w_k,X)]$

SGD： $w_{k+1}=w_k-{\alpha }_k{\nabla }_{w}f(w_k,x_k)$

${\nabla }_{w}f(w_k,x_k)$ 可视为 $\mathbb{E}[{\nabla }_{w}f(w_k,X)]$ 的 包含误差的测量值。

${\nabla }_{w}f(w_k,x_k)=\mathbb{E}[{\nabla }_{w}f(w_k,X)]+\underset{\eta }{\underbrace{{\nabla }_{w}f(w_k,x_k)-\mathbb{E}[{\nabla }_{w}f(w_k,X)]}}$
由于 ${\nabla }_{w}f(w_k,x_k)\ne \mathbb{E}[{\nabla }_{w}f(w_k,X)]$, SGD 算法 是否满足 当 $k\to \infty$ 时， $w_k\to w^{\ast }$

——————
以下 证明 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$ 的根。

测量值 $\tilde{g}(w,\eta )={\nabla }_{w}f(w,x)=\underset{g(w)}{\underbrace{\mathbb{E}[{\nabla }_{w}f(w,X)]}}+\underset{\eta }{\underbrace{{\nabla }_{w}f(w,x)-\mathbb{E}[{\nabla }_{w}f(w,X)]}}$

求解 $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 是一种特殊的 RM 算法。

• 证明 6.4.5 SGD 的收敛性

-——————
part 6 SGD 的一些特性

SGD 是 把 GD 中 的 真实梯度 用 随机梯度 替换，会不会 造成 SGD 的收敛的随机性比较大呢？

1、当 $w_k$ 离 $w^{\ast }$ 比较远时， 下降过程 和 普通梯度下降 类似； 比较近时下降过程 随机。

分析过程：

考虑 随机梯度 和 批次梯度的 相对误差：

$${\Delta }_k\dot{=}\frac{|{\nabla }_{w}f(w_k,x_k)-\mathbb{E}[{\nabla }_{w}f(w_k,X)]|}{|\mathbb{E}[{\nabla }_{w}f(w_k,X)]|}$$

$\nabla$$\nabla$

由于 $\mathbb{E}[{\nabla }_{w}f(w^{\ast },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^{\ast },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^{\ast })]|}$$

最后一个 等号 运用了 中值定理, 其中 ${\tilde{w}}_k\in [w_k,w^{\ast }]$

假设 $f$ 是严格凸的。 即对于 所有的 $w,X$， 均满足 ${\nabla }_w^{2}f\ge c>0$, 其中 $c$ 为正。

则 上式的分母

∣ E [ ∇ w 2 f ( w ~ k , X ) ( w k − w ∗ ) ] ∣ = ∣ E [ ∇ w 2 f ( w ~ k , X ) ] ( w k − w ∗ ) ∣ = ∣ E [ ∇ w 2 f ( w ~ k , X ) ] ∣ ⋅ ∣ ( w k − w ∗ ) ∣ ≥ c ∣ w k − w ∗ ∣

$$\begin{aligned}|\mathbb E[\nabla^2_wf(\widetilde w_k,X)(w_k -w^*)]| &= |\mathbb E[\nabla^2_wf(\widetilde w_k,X)](w_k -w^*)|\\ &= |\mathbb E[\nabla^2_wf(\widetilde w_k,X)]|·|(w_k -w^*)|\\ &\geq c|w_k-w^*|\end{aligned}$$ ∣E[∇w2​f(w k​,X)(wk​−w∗)]∣​=∣E[∇w2​f(w k​,X)](wk​−w∗)∣=∣E[∇w2​f(w k​,X)]∣⋅∣(wk​−w∗)∣≥c∣wk​−w∗∣​

$${\Delta }_k\le \frac{|\stackrel{随机梯度}{\overbrace{{\nabla }_{w}f(w_k,x_k)}}-\stackrel{真实梯度}{\overbrace{\mathbb{E}[{\nabla }_{w}f(w_k,X)]}}|}{c\underset{w_k到最优解w^{\ast }的距离}{\underbrace{|w_k-w^{\ast }|}}}$$

相对误差 ${\Delta }_k$ 和 $|w_k-w^{\ast }|$ 成反比

当 $|w_k-w^{\ast }|$ 较大时，${\Delta }_k$ 较小，SGD 表现与 GD 相似。
当 $w_k$ 接近 $w^{\ast }$ 时，相对误差 ${\Delta }_k$ 可能较大， $w^{\ast }$ 附近的收敛表现出更大的随机性。

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

MBGD(Mini-Batch Gradient Descent, MBGD)：小批量梯度下降

虽然 平均值的初始估计值 离真实值很远，但 SGD 估计值可以快速接近真实值的邻域。
当估计值接近真实值时，它表现出一定的随机性，但仍逐渐接近真实值。

————

6.4.3 SGD 的确定性公式

待优化问题：【不包含 任何随机变量， 如 $X$】
$\underset{w}{\min }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\}_{i=1}^{n} {xi​}i=1n​

——————
求解该问题的 梯度下降算法：
$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 \{x_i\}_{i=1}^{n} {xi​}i=1n​？我们应该把这些数字按一定的顺序排序，然后一个一个地使用吗？或者我们应该从集合中随机抽取一个数字?

回答：
引入 一个 随机变量 $X$， 使得
$p(X=x_i)=\frac{1}{n}$

确定性 优化问题 ——> 随机

$\underset{w}{\min }J(w)=\frac{1}{n}\sum _{i=1}^{n}f(w,x_i)=\mathbb{E}[f(w,X)]$

随机抽取 $x_i$， 抽取可能重复。

6.4.4 BGD, MBGD, SGD

P4

已知 $X$ 的随机样本集 { x i } i = 1 n \{x_i\}_{i=1}^{n} {xi​}i=1n​， 最小化 $J(w)=\mathbb{E}[f(w,X)]$
BGD 算法【批次 梯度下降】： 每次迭代 用完所有 的样本。

• 当 $n$ 很大时， 批次梯度 $\frac{1}{n}\sum _{i=1}^n{\nabla }_{w}f(w_k,x_i)$ 接近 真实梯度 $\mathbb{E}[{\nabla }_{w}f(w_k,X)]$
• $w_{k+1}=w_k-{\alpha }_k\frac{1}{n}\sum _{i=1}^n{\nabla }_{w}f(w_k,x_i)$
    ~  

MBGD 算法【小批次 梯度下降】： 大小为 $m$ 的 ${\mathcal{I}}_k$ 为 { x i } i = 1 n \{x_i\}_{i=1}^{n} {xi​}i=1n​ 的子集。

• $w_{k+1}=w_k-{\alpha }_k\frac{1}{m}\sum _{j\in {\mathcal{I}}_k}{\nabla }_{w}f(w_k,x_j)$
• m 越大， 收敛越快
    ~  

SGD 算法 【随机 梯度下降】：$x_k$ 在时间 $k$ 从 { x i } i = 1 n \{x_i\}_{i=1}^{n} {xi​}i=1n​ 随机抽取。

• $w_{k+1}=w_k-{\alpha }_k{\nabla }_{w}f(w_k,x_k)$

与 SGD 相比，MBGD 的随机性更小，因为它使用了更多的样本，而不是 SGD 中的一个样本。
与 BGD 相比，MBGD 不需要在每次迭代中使用所有的样本，使其更加灵活和高效。
m = 1 时，MBGD 变为 SGD。
如果 m = n，严格来说 MBGD 不成为 BGD，因为 MBGD 使用随机获取的 n 个样本，而 BGD 使用所有 n 个样本。特别是，MBGD 可能多次使用 { x i } i = 1 n \{x_i\}_{i=1}^{n} {xi​}i=1n​ 中的值，而 BGD 只使用每个样本一次。

均值问题 估计：

6.4.5 SGD 的收敛性

条件 (a) 是关于 $f$ 的凸性的，它要求 $f$ 的曲率上下有界。当 $w$ 是向量时，${\nabla }_w^{2}f(w,X)$ 是著名的 Hessian 矩阵。

证明 SGD 算法是一种特殊的 RM 算法。

SGD：求解 使得 $J(w)=\mathbb{E}[f(w,X)]$ 最小 的 $w$

这个问题 可以转成 寻根问题 ${\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$ 的根， 这正是 RM 算法 可求解的问题。

设测量值 $\tilde{g}={\nabla }_{w}f(w,x)$， 其中 $x$ 是 $X$ 的样本。

g ~ ( w , η ) = ∇ w f ( w , x ) = E [ ∇ w f ( w , X ) ] + ∇ w f ( w , x ) − E [ ∇ w f ( w , X ) ] ⏟ η ( w , x )

$$\begin{aligned}\widetilde g(w, \eta)&=\nabla_wf(w,x)\\ &={\mathbb E}[\nabla_wf(w, X)]+\underbrace{\nabla_wf(w,x)-{\mathbb E}[\nabla_wf(w, X)]}_{\eta(w,x)}\end{aligned}$$ g ​(w,η)​=∇w​f(w,x)=E[∇w​f(w,X)]+η(w,x) ∇w​f(w,x)−E[∇w​f(w,X)]​​​

求解 $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 算法是一种特殊的 RM 算法。

证明 满足 定理 6.1 的 3 个条件： 即 RM 算法收敛需要满足的 3 个条件

1、定理 6.4 满足： $c_1\le {\nabla }_w^{2}f(w,X)\le c_2$

而 ${\nabla }_{w}g(w)={\nabla }_w\mathbb{E}[{\nabla }_{w}f(w,X)]=\mathbb{E}[{\nabla }_w^{2}f(w,X)]$
则 $c_1\le {\nabla }_{w}g(w)\le c_2$， 满足 定理 6.1

2、条件相同
3、定理 6.4 要求 { x k } \{x_k\} {xk​} 是独立同分布的，有 ${\mathbb{E}}_{x_k}[{\nabla }_{w}f(w,x_k)]=\mathbb{E}[{\nabla }_{w}f(w,X)]$

$\mathbb{E}[{\eta }_k|{\mathcal{H}}_k]=\mathbb{E}[{\nabla }_{w}f(w_k,x_k)-\mathbb{E}[{\nabla }_{w}f(w,X)]|{\mathcal{H}}_k]$

因为 H k = { w k , w k − 1 , ⋯   } {\mathcal H}_k=\{w_k,w_{k-1},\cdots\} Hk​={wk​,wk−1​,⋯} 且 $x_k$ 与 ${\mathcal{H}}_k$ 无关。

$\mathbb{E}[{\eta }_k|{\mathcal{H}}_k]={\mathbb{E}}_{x_k}[{\nabla }_{w}f(w_k,x_k)]-\mathbb{E}[{\nabla }_{w}f(w,X)]=0$

类似地， 可证 给定任意 $x$， 对所有 $w$，若是 $|{\nabla }_{w}f(w,x)|<\infty$，则 $\mathbb{E}[{\eta }_k^2|{\mathcal{H}}_k]<\infty$。

• ？？？

————————

小结：

时间差分学习算法 可以被视为 随机近似算法

————————————————
6.6
stochastic approximation 随机近似是指解决寻根或优化问题的一大类随机迭代算法。

时序差分学习算法类似于均值估计的随机近似算法。

——————
习题

以下内容待完善

▢ 6.3 Dvoretzkys 收敛定理 【选学】

用于证明 RM 算法 的收敛性

在 RM 算法中，系数序列 { α k } \{\alpha_k\} {αk​} 是确定的。然而，Dvoretzky 定理允许 { α k } \{\alpha_k\} {αk​}， { β k } \{β_k\} {βk​} 是依赖于 ${\mathcal{H}}_k$ 的随机变量。因此，当 ${\alpha }_k$ 或 ${\beta }_k$ 是 $△k$ 的函数时，它更有用。

考虑随机过程： ${\Delta }_{k+1}=(1-{\alpha }_k){\Delta }_k+{\beta }_k{\eta }_k$

H k = { w k , w k − 1 , ⋯   , η k − 1 , ⋯   , α k − 1 , ⋯   , β k − 1 , ⋯   } \mathcal H_k=\{w_k,w_{k-1},\cdots,\eta_{k-1},\cdots,\alpha_{k-1},\cdots,\beta_{k-1},\cdots\} Hk​={wk​,wk−1​,⋯,ηk−1​,⋯,αk−1​,⋯,βk−1​,⋯}

证明：

令 $h_k={\Delta }_k^2$

h k + 1 − h k = Δ k + 1 2 − Δ k 2 = ( Δ k + 1 − Δ k ) ( Δ k + 1 + Δ k ) = ( ( 1 − α k ) Δ k + β k η k − Δ k ) ( ( 1 − α k ) Δ k + β k η k + Δ k ) = ( − α k Δ k + β k η k ) [ ( 2 − α k ) Δ k + β k η k ] = − α k ( 2 − α k ) Δ k 2 + β k 2 η k 2 + 2 ( 1 − α k ) β k η k Δ k

$$\begin{aligned} h_{k+1}-h_k&=\Delta_{k+1}^2-\Delta_k^2\\ &=(\Delta_{k+1}-\Delta_k)(\Delta_{k+1}+\Delta_k)\\ &=((1-\alpha_k)\Delta_k+\beta_k\eta_k-\Delta_k)((1-\alpha_k)\Delta_k+\beta_k\eta_k+\Delta_k)\\ &=(-\alpha_k\Delta_k+\beta_k\eta_k)[(2-\alpha_k)\Delta_k+\beta_k\eta_k]\\ &=-\alpha_k(2-\alpha_k)\Delta_k^2+\beta_k^2\eta_k^2+2(1-\alpha_k)\beta_k\eta_k\Delta_k\end{aligned}$$ hk+1​−hk​​=Δk+12​−Δk2​=(Δk+1​−Δk​)(Δk+1​+Δk​)=((1−αk​)Δk​+βk​ηk​−Δk​)((1−αk​)Δk​+βk​ηk​+Δk​)=(−αk​Δk​+βk​ηk​)[(2−αk​)Δk​+βk​ηk​]=−αk​(2−αk​)Δk2​+βk2​ηk2​+2(1−αk​)βk​ηk​Δk​​

等式两边取期望

$\mathbb{E}[h_{k+1}-h_k|{\mathcal{H}}_k]=\mathbb{E}[-{\alpha }_k(2-{\alpha }_k){\Delta }_k^2|{\mathcal{H}}_k]+\mathbb{E}[{\beta }_k^2{\eta }_k^2|{\mathcal{H}}_k]+\mathbb{E}[2(1-{\alpha }_k){\beta }_k{\eta }_k{\Delta }_k|{\mathcal{H}}_k]$

考虑 ${\alpha }_k$ 和 ${\beta }_k$ 由 ${\mathcal{H}}_k$ 确定的 简单情况：

$\mathbb{E}[h_{k+1}-h_k|{\mathcal{H}}_k]=-{\alpha }_k(2-{\alpha }_k){\Delta }_k^2+{\beta }_k^2\mathbb{E}[{\eta }_k^2|{\mathcal{H}}_k]+2(1-{\alpha }_k){\beta }_k{\Delta }_k\mathbb{E}[{\eta }_k|{\mathcal{H}}_k]$

$\mathbb{E}[h_{k+1}-h_k|{\mathcal{H}}_k]=-{\alpha }_k(2-{\alpha }_k){\Delta }_k^2+{\beta }_k^2\mathbb{E}[{\eta }_k^2|{\mathcal{H}}_k]\le {\beta }_k^{2}C$

$\sum _{k=1}^{\infty }\mathbb{E}[h_{k+1}-h_k|{\mathcal{H}}_k]\le \sum _{k=1}^{\infty }{\beta }_k^{2}C<\infty$

接下来 确认 ${\Delta }_k$ 的收敛值

$\sum _{k=1}^{\infty }{\alpha }_k(2-{\alpha }_k){\Delta }_k^2=\sum _{k=1}^{\infty }{\beta }_k^2\mathbb{E}[{\eta }_k^2|{\mathcal{H}}_k]-\mathbb{E}[h_{k+1}-h_k|{\mathcal{H}}_k]$

先说明等号两边均有界

由于 $\sum _{k=1}^{\infty }{\alpha }_k=\infty$， 则 ${\Delta }_k\to 0$

6.3.2 应用到 均值估计

设 $w^{\ast }=\mathbb{E}[X]$

均值估计算法 $w_{k+1}=w_k+{\alpha }_k(x_k-w_k)$ 可以重写为

$w_{k+1}-w^{\ast }=w_k-w^{\ast }+{\alpha }_k(x_k-w^{\ast }+w^{\ast }-w_k)$

令 $\Delta =w-w^{\ast }$

Δ k + 1 = Δ k + α k ( x k − w ∗ − Δ k ) = ( 1 − α k ) Δ k + α k ( x k − w ∗ ) ⏟ η k

$$\begin{aligned}\Delta_{k+1}&=\Delta_k+\alpha_k(x_k-w^*-\Delta_k)\\ &=(1-\alpha_k)\Delta_k+\alpha_k\underbrace{(x_k-w^*)}_{\eta_k}\end{aligned}$$ Δk+1​​=Δk​+αk​(xk​−w∗−Δk​)=(1−αk​)Δk​+αk​ηk​ (xk​−w∗)​​​

因为 { k } \{k\} {k} 是 i.i.d，我们有 $\mathbb{E}[x_k|{\mathcal{H}}_k]=\mathbb{E}[x_k]=w^{\ast }$。
因此，当 $x_k$ 的方差有限时，
$\mathbb{E}[{\eta }_k|{\mathcal{H}}_k]=\mathbb{E}[x_k-w^{\ast }|{\mathcal{H}}_k]=0$
$\mathbb{E}[{\eta }_k^2|{\mathcal{H}}_k]=\mathbb{E}[x_k^2|{\mathcal{H}}_k]-(w^{\ast }{)}^2=\mathbb{E}[x_k^2]-(w^{\ast }{)}^2=0$ 是有界的。
根据 Dvoretzky 定理，我们得出 ${△}_k$ 收敛于零，因此 $w_k$ 几乎肯定地收敛到 $w^{\ast }=\mathbb{E}[X]$。

6.3.3 应用到 Robbins-Monro 定理

通过 Dvoretzky 定理 证明 RM 定理

RM 算法的目标是 找 $g(w)=0$ 的根。

假设 这个根是 $w^{\ast }$， $g(w^{\ast })=0$

RM 算法：
w k + 1 = w k − a k g ~ ( w k , η k ) = w k − a k [ g ( w k ) + η k ]

$$\begin{aligned}w_{k+1}&=w_k-a_k\widetilde g(w_k,\eta_k)\\ &=w_k-a_k[g(w_k)+\eta_k]\end{aligned}$$ wk+1​​=wk​−ak​g ​(wk​,ηk​)=wk​−ak​[g(wk​)+ηk​]​

w k + 1 − w ∗ = w k − w ∗ − a k [ g ( w k ) − g ( w ∗ ) + η k ]

$$\begin{aligned}w_{k+1}-w^*&=w_k-w^*-a_k[g(w_k)-g(w^*)+\eta_k]\end{aligned}$$ wk+1​−w∗​=wk​−w∗−ak​[g(wk​)−g(w∗)+ηk​]​

$g(w_k)-g(w^{\ast })={\nabla }_{w}g(w_k^{\prime })(w_k-w^{\ast })$， 其中 $w_k^{\prime }\in [w_k,w^{\ast }]$

令 ${\Delta }_k\doteq w_k-w^{\ast }$

Δ k + 1 = Δ k − a k [ ∇ w g ( w k ′ ) ( w k − w ∗ ) + η k ] = Δ k − a ∇ w g ( w k ′ ) Δ k + a k ( − η k ) = [ 1 − a k ∇ w g ( w k ′ ) ⏟ α k ] Δ k + a k ( − η k )

$$\begin{aligned}\Delta_{k+1}&=\Delta_k-a_k[\nabla_wg(w^\prime_k)(w_k-w^*)+\eta_k] \\ &=\Delta_k-a\nabla_wg(w^\prime_k)\Delta_k+a_k(-\eta_k)\\ &=[1-\underbrace{a_k\nabla_wg(w^\prime_k)}_{\alpha_k}]\Delta_k+a_k(-\eta_k)\end{aligned}$$ Δk+1​​=Δk​−ak​[∇w​g(wk′​)(wk​−w∗)+ηk​]=Δk​−a∇w​g(wk′​)Δk​+ak​(−ηk​)=[1−αk​ ak​∇w​g(wk′​)​​]Δk​+ak​(−ηk​)​

由于假设 $0<c_1\le {\nabla }_{w}g(w)\le c_2$，${\nabla }_{w}g(w)$ 有界。

由于假设 ${\sum }_{k=1}^{\infty }{a}_k=\infty ，{\sum }_{k=1}^{\infty }{a}_k^2<\infty$，可知 ${\sum }_{k=1}^{\infty }{\alpha }_k=\infty ，{\sum }_{k=1}^{\infty }{\alpha }_k^2<\infty$。

满足 Dvoretzky 定理中的所有条件，因此 ${\Delta }_k$ 几乎肯定收敛于零。

当 ${\alpha }_k$ 是依赖于 $w_k$ 的随机序列，而不是确定性序列，Dvoretzky 定理仍然适用。

6.3.4

将 Dvoretzky 定理扩展为一个可以处理多个变量的更一般的定理。这个一般定理可以用来分析 Q-learning 等随机迭代算法的收敛性。

• P122 - P123

$$\begin{aligned} \end{aligned}$$ ​