强化学习学习笔记（六）随机近似理论与随机梯度下降方法
动机
回顾一下期望的定义，为什么我们要计算期望？是为了取平均。
为什么要计算期望？因为强化学习的本质就是求期望，求状态下能够获得的回报的期望、动作获得的未来回报的期望
求期望有两种方式：
①全量求期望，收集所有的样本然后求平均
②增量的方式求期望。
增量的方式求期望，如图所示，是可以通过推导，得到wk + 1和wk之间的关系的。通过迭代最下面的式子可以实现来一个新增数据得一个期望
这也是td
difference的基础，迭代式的求平均数。
我们不一定取1/k,而是取一个自适应的参数ak，在满足某些条件的情况下，可以证明，这个迭代的式子也是可以收敛在E[X]的。
这个就是随机梯度下降的方法。 核心的迭代式子就是 wk + 1 = wk − ag(wk, ηk)
这里n是噪音项。
RM算法
首先引入Robbins-Monro 算法（RM算法），RM算法是一种经典的随机近似算法，用于解决寻根问题或优化问题，尤其在目标函数未知或无法直接计算导数的情况下表现出色。它是随机梯度下降（SGD）等现代优化算法的理论基础。
我们要求一个问题，是求一个函数的最小值，来优化损失函数J(w)。我们很容易想到对这个损失函数进行求导数，并且令这个导数为0，从而得到这个导数的解。但是很多时候，我们并不知道这个导数长什么样子，只知道大概的形状。那么我们的问题就转换成：给定一个随机的观测噪声的函数g，求g(w)=0，从而得到原问题的导数的零点。原函数的最优值就在这些零点中间。
RM算法是用迭代的方式去求g(w)=0的一个方法，也就是
g这个函数的根，这里g的原始值不知道，只知道它是带噪声的观测。这里噪声就是ηk。
这种迭代的方式蕴含着哲学思想：没有模型就得有数据，没有数据就得有模型
RM算法的迭代的方法计算可以如图得到，每一次迭代，wk + 1都是比wk更靠近w*的，哪怕是wk＜w*的情况。 而rm算法需要满足三个条件：
第一个条件是：g（w）的梯度必须是正数，而且必须有上界。
这个条件看着很严格，但是是求解原问题必不可少的。
因为比如说我们要求 minJ（w），
如果我们已知g（w）是j（w）的导数，上述问题就转化成求g（w）＝ ▽ j（w）＝0
所以g（w）的导数就是j的二阶导。二阶导要有零点，它的何塞矩阵必须全是正数。
第二个条件是ak必须趋于0，随着k趋于无穷。但是ak趋于0又不能趋于的太快，因此又要求∑ak发散。
如果∑ak不发散，而w*距离w1很远，在这种情况下，可能迭代到中间的某几步，就停止了。无法从w1迭代到w*
ak＝1/k的时候是符合上述条件的一个解。证明就是那个p级数的证明。 但是实际问题里，不会取ak＝1/k，而是取一个很小的常数。从而让后面进来的数据也能使用到
RM算法可以用于平均值问题估计的证明，因为估计问题满足上面的性质。
随机梯度下降算法
随机梯度下降（Stochastic Gradient Descent, SGD）是一种高效的优化算法，通过迭代更新模型参数来最小化损失函数。与批量梯度下降（BGD）相比，SGD每次只使用一个或少量样本计算梯度，从而显著降低计算成本，并在大规模数据集上表现优异。
sgd算法在机器学习领域经常用，在强化领域也经常用。 sgd是一种特别的rm算法 平均值估计算法是一种特殊的sgd算法。
现在假设我们要求一个优化问题：
minj（w）＝E[f(w, x)]
这里表示对参数w进行优化，目标是让J（w）的损失函数最小化，最小化这个损失函数等价于最小化在给定随机变量X的环境下，通过参数w、f（w，x）来估计期望，调整w来优化估计期望的准确度。
w是待优化变量；X是随机变量，它的期望由多个数据x决定
优化目标函数J 是f的期望 x是随机分布， 现在要找到最优w，使得目标函数最小
有三种方法去求解这个期望：
第一种是gd 梯度下降，目标函数按照梯度的方式下降，这种方式要求明确知道梯度。而期望值是难以获得的。
第二种方法对应的是没有模型的情况下，采用类似蒙特卡洛的方式从一批数据中近似获取他的均值。
第三种就是要介绍的SGD方法，其中是将其中的真实梯度替换成了随机梯度。而真实的梯度不一定能够求得，所以这里替换成随机梯度，里面有个随机的采样变量xk。
和bgd算法的区别：就是令n＝1
SGD算法的收敛性和案例：
现在我们举一个例子，优化一个目标，这个目标是求随机变量x和w之间的距离最小。 首先，有一个小问题，我们需要证明w的最优解是EX，证明的如红笔所示。
然后，我们比较GD算法和SGD算法的差别
GD算法：首先要知道优化目标的梯度，然后把梯度写出来。
SGD算法：直接把Ex替换成梯度，也就是wk − xk。
这个公式的形式，和之前给出的平均值估计问题类似，就是有一组数，用增量的方式求平均值，是一样的，这也就是说，平均值估计算法是一种特殊的sgd算法。在那个算法里 ak＝1/k，或者其他的值。
也就是说，求平均值问题可以描述成优化问题，描述成最小化期望问题 这俩是殊途同归的。
SGD算法的收敛性证明（为什么SGD算法是有效的）
sgd就是用一个采样的值去替代了整个的梯度的期望E，这个梯度的期望可以认为是真实梯度。这个采样的值是梯度真值的近似。
为什么sgd可以收敛呢？可以用前面讲的rm算法来证明。sgd是优化问题 ，他最终的目标是求损失函数J（w）最小，这个最小可以转化成求根问题。也就是梯度(g(w))为0的时候去求g(w)的根。
他的形式就相当于g在有扰动的情况下，去求解这个算法。这和sgd是一样的。
由于SGDa是特别的RM算法，它的收敛性服从下面的结论（看图）。 第一个条件是f是凸函数，且上下界是向量 第二个是收敛性 第三个是采样是独立同分布。
最后一个问题：有时候在SGD算法里面没有看到随机变量，而是一组数，他写成了和SGD类似的形式，这里面没有随机变量X，也没有期望，就是取平均，这时候还是SGD吗
答案是是的，我们可以定义一个随机变量X，让其中取每个数的概率是1/n，这样，我们就有了随机变量，求平均的问题也转化成了求期望问题。 只是在运行SGD的时候，我们要一批次随机采样数据，这些数据样本可以重复利用。
BGD MBGD 和SGD的区别
bgd是用全部的样本来做梯度下降，
mbgd是从中间抽取一个小的子集，进行梯度下降
sgd是每次只取一个样本，进行梯度下降。
相对来说，mbgd和bgd它的方差更小，随机性更小。
如果m＝1 mbgd就是sgd
如果m＝n mbgd 只采取其中的n个样本，但是bgd使用所有样本。这时候这两者还不一样。
举例：求w和x的距离最小值。也就是估计x的均值。
bgd是用所有样本，mbgd是采样一批，sgd是就采一个
小结：
这一章介绍了
①用增量的方式求平均的方法
②经典的rm算法：求g（w）＝0的根，但是不知道g（w）的表达式，只知道每输入一个w能输出一个结果，可能是带误差的，这时候怎么求解
③从rm算法衍生的sgd算法：求随机变量的期望，用每次取一个数的方式。
