【强化学习的数学原理-赵世钰】课程笔记（六）随机近似与随机梯度下降

原文发布于 CSDN：https://blog.csdn.net/m0_49683806/article/details/139443499

参考引用

【强化学习的数学原理-赵世钰】课程笔记（六）随机近似与随机梯度下降

一.内容概述

背景：

• 本次课学习随机近似理论（Stochastic Approximation）和随机梯度下降（Stochastic Gradient Descent）。因为下节课我们要介绍 Temporal-Difference learning，这是一个无模型的强化学习算法，下节课与上节课介绍的有一个知识的鸿沟，比较难理解。实际上，Temporal-Difference learning 是 Stochastic Approximation 的一个特殊情况。因此，这节课先介绍背景知识
• 在上一讲中，我们介绍了蒙特卡洛学习法（Monte-Carlo learning）。
• 在下一讲中，我们将介绍时差（TD）学习（temporal-difference (TD) learning）。
• 在本讲座中，我们将按下暂停键，以便做好更充分的准备。

为什么？

• TD算法（temporal-difference (TD) learning）的思想和表达方式与我们目前学习的算法截然不同。
• 第一次看到 TD 算法时，都会疑惑为什么当初要设计这些算法，为什么它们能有效地工作。

在本次课中：

• 我们将通过介绍基本的随机逼近（SA）算法，填补上一讲和下一讲之间的知识空白。通过介绍基本的随机近似（SA）算法（basic stochastic approximation (SA) algorithms），我们将填补上一讲和下一讲之间的知识空白。
• 我们将在下一讲中看到，时差算法是一种特殊的 SA 算法（temporal-difference algorithms are special SA algorithms）。因此，理解这些算法会容易得多。

本节课内容：

• 1.激励性实例（Motivating examples）：首先介绍 mean estimation，也就是估计一个随机变量的 expectation，因为我们想用这个例子说明什么是 non-incremental（非增量式），什么是 incremental（增量式）。实际上要估计 $\mathbb{E}[X]$ 有两种方法：non-incremental 方法就是比如有一万个采样，要等所有采样都采到了再一次性求平均，得到 $\mathbb{E}[X]$ 的一个近似；incremental 的思想是开始的时候对他有一个估计，这个估计可能不准但是没关系，我得到一个采样我就用这个采样来更新我的估计，得到一个采样就更新一次，慢慢的估计会越来越准确，这就是增量式的思想，它的好处是不需要等全部样本全部集齐，在收集样本的过程中就可以有一些估计尽管不太准确，但可以使用，会越来越准确。
• 2.Robbins-Monro 算法（RM 算法）：是随机近似理论（Stochastic Approximation）中非常经典的一个算法，求解 $g(w) = 0$ 这样一个方程，求解 $w$ 使得这个方程成立。不需要知道 $g(w)$ 长什么样子，它的表达式，它的梯度导数全都不需要就可以被求出来。
• 3.随机梯度下降（Stochastic Gradient Descent）：是 RM 算法的一个特殊情况
• 4.batch gradient descent，mini-batch gradient descent 和 stochastic gradient descent（批量梯度下降，微型批量梯度下降和随机梯度下降）（BGD，MBGD 和 SGD）
• 5.总结

二.激励性实例（Motivating examples）

这部分介绍一个 mean estimation 的算法，如何通过迭代的方式去求一个期望（expectation）

重温上节课学过的平均值估计问题（Revisit the mean estimation problem）

• 考虑一个随机变量 $X$
• 我们的目标是估计它的期望 $\mathbb{E}[X]$
• 假设我们收集了一些独立同分布的采样
• 对采样求平均值，认为是 $\mathbb{E}[X]$ 的近似
• 上面这种近似方法就是蒙特卡罗估计的基本思想。
• 当有足够多的数据的时候，采样的平均值会逐渐收敛到它真实的期望 $\mathbb{E}[X]$

为什么我们如此在意平均值估计问题（mean estimation problem）？

强化学习（RL）中的许多量，如动作值和梯度（action values and gradients），都被定义为期望值，都需要用数据去估计。

新问题： 如何计算平均值 $\bar{x}$？
$$\mathbb{E}[x]\approx \bar{x}: = \frac{1}{N}\sum^{N}_{i = 1}x_i$$
有两种方法：

第一种方法： 很简单，就是收集所有样本，然后计算平均值。

• 这种方法的缺点是，如果要在一段时间内逐个（one by one）收集样本，我们就必须等到所有样本都收集完毕。我们必须等到所有样本都收集完毕再求平均。

第二种方法： 可以避免这一缺点，因为它是以递增（增量式的）（incremental）和迭代（iterative）的方式计算平均值的。基本思路就是来几个就先计算几个，这样效率更高。

下面详细介绍第二种方法

关于该算法的说明：

• 这种算法的优势在于它是渐进式的。一旦收到样本，就可以立即获得平均值估计值。然后，平均估算值就可以立即用于其他目的。在第 $k$ 步的时候，我不需要把前面所有的 $x_i$ 全部加起来再求平均，只需要通过上式一步的计算就可以得到一个新的平均数
• 这个算法代表一种增量式的计算思想：在最开始的时候因为数据量比较小，$w_k$ 难以非常精确的逼近 $\mathbb{E}[X]$，即由于样本不足，平均值估计在开始时并不准确（即 $w_k \neq \mathbb{E}[X]$。不过，有总比没有好，总比一直等到最后才能有一个数来得到一个平均数要强。在这个过程中 $w_k$ 就算不精确，也可以用到其它任务中。随着样本的增多，数据越来越大，$w_k$ 也会越来越精确的逼近 $\mathbb{E}[X]$，估计值会逐渐提高（即当 $k \rightarrow \infty$ 时，$w_k \rightarrow \mathbb{E}[X]$）。

此外，这个算法也可以进一步推广：

还可以考虑一种表达式更一般的算法：

• 这种算法还能收敛到平均值 $\mathbb{E}[X]$ 吗？ 我们之后将证明，如果 {αk} 满足一些温和的条件（satisfy some mild conditions），答案是可以的。
• 我们还将证明，这种算法是一种特殊的 SA 算法（Stochastic Approximation algorithm），也是一种特殊的随机梯度下降算法（stochastic gradient descent algorithm）。
• 在下一讲中，我们将看到时差算法(the temporal-difference algorithms)有类似（但更复杂）的表达式。

三.Robbins-Monro 算法（RM 算法）：

是随机近似理论（Stochastic Approximation）中非常经典的一个算法

1.算法描述

随机近似（Stochastic approximation，SA）究竟是什么：

• SA 指的是 解决寻根（方程求解）或优化问题 的一大类随机迭代算法。SA refers to a broad class of stochastic iterative algorithms solving root finding or optimization problems.（随机算法就是里面会涉及到对随机变量的采样）
• 与许多其他寻根（方程求解）算法（如基于梯度的方法gradient-based methods，梯度下降或梯度上升）相比，SA 的强大之处在于它不需要知道目标函数的表达式或其导数或者梯度的表达式。

Robbins-Monro (RM) 算法:

• 这是随机逼近领域（in the field of stochastic approximation）的一项开创性工作。
• 著名的随机梯度下降算法（stochastic gradient descent algorithm）是 RM 算法的一种特殊形式。
• 它可以用来分析开头介绍的均值估计（mean estimation）算法。我们前面介绍的 mean estimation 算法也是一种特殊的 RM 算法。

问题陈述： 假设我们想找出方程的根
$$g(w) = 0$$
其中 $w \in R$ 是待解变量，$g:\mathbb{R}\rightarrow \mathbb{R}$ 是一个函数。$w$ 和 $g$ 全都是标量

• 这个问题看似很简单，但是很有用，因为它广泛的存在。许多问题最终都可以转化为这个寻根问题，比如优化问题：例如，假设 $J(w)$ 是一个需要最小化的目标函数，需要优化 $J(w)$ 那么方法就是求解下面的这个方程，就是 $J(w)$ 的梯度等于 0，这个梯度等于 0 是 $J(w)$ 达到最大或最小的一个必要条件，并不是充分条件，但我们可以找到一个局部的极值。或者当 $J(w)$ 只有一个极值的时候，这个就变成一个充分必要条件。
• 总之，优化问题可以写成 $g(w) = 0$ 的形式，这时候 $g(w)$ 指的就是梯度

$$g(w) = \triangledown _{w}J(w) = 0$$

• 请注意，$g(w) = c$ 这样的方程（c 为常数），也可以通过将 $g(w)-c$ 改写为一个新函数而转换为上式 $g(w)-c = 0$。

如何求解 g(w) = 0 的根？

有两种情况：

• 基于模型： 如果已知 $g$ 或者其导数的表达式，有很多数值算法可以解决这个问题。
• 无模型： 如果函数 $g$ 的表达式未知呢？
  • 例如，函数由人工神经元网络表示。可以通过神经网络求解，$y = g(w)$，这个神经网络的输入是 $w$，输出是 $y$，神经网络里面其实就是 $g(w)$。常见的全连接神经网络其实就是做一个函数的近似，神经网络中我是不知道表达式的，现在问题就是输入什么样的 $w$ 能得到一个 0 的输出？

求解 $g(w) = 0$ 这样的问题（求这个方程的根）可以用 RM 算法来求解，下面正式介绍 RM 算法：

目标是求解 $g(w) = 0$，假设最优解是 $w^*$

RM算法是个迭代式的算法，对 $w^*$ 第 $k$ 次的估计是 $w_k$