Robbins–Monro 随机逼近

两项步长和控制两种累积效应。$\sum {\eta }_t=\mathrm{\infty }$ 保留足够长的有效行程，让初始偏差有机会被消除。$\sum {\eta }_t^2<\mathrm{\infty }$ 则限制条件无偏噪声经平方距离累加的总量。证明中的 $W_t$ 把未来尚未花掉的噪声预算提前记入，得到平均意义下不再增加的量。

这也解释了“轨迹最终稳定”与“有限预算足够好”是两件事。几乎必然收敛说明每条典型路径最终接近根，却没有单凭式(2)给出一个统一、可用的有限停止轮数。需要预算保证时，应继续计算递推常数或使用特定模型的误差公式。

递推均值就是最简单的带噪求根 ​

设 $Y_1,Y_2,\dots$ IID，均值 $\theta$、方差 ${\sigma }^2<\mathrm{\infty }$。求根 $h(x)=x-\theta$，查询器返回 $H_{t+1}=x_t-Y_{t+1}$。取 ${\eta }_t=1/(t+1)$，则

首步系数把 $x_0$ 消掉，归纳得到 $x_T=T^{-1}\sum _{j=1}^T{Y}_j$，故 $E{x}_T=\theta$、$E(x_T-\theta {)}^2={\sigma }^2/T$。大数律理路强大数定律Law of large numbers · Strong law of large numbers · SLLN独立同分布且可积时，样本均值沿几乎每条无限样本路径收敛到共同期望。在这个特例中也给几乎必然收敛。观察 $(3,-1,2,0)$ 时，四个迭代依次为 $3,1,4/3,1$；最后结果正是样本均值。

每轮读取一个新观测，累计 $T$ 次oracle调用；标量更新和存储为 $O(T)$ 与 $O(1)$。若目标是二次损失 $f(x)=(x-\theta {)}^2/2$，其期望目标差为 ${\sigma }^2/(2T)$。如果再把这些已经是累积均值的 $x_t$ 平均一次，早期样本会获得较大权重，详见迭代平均理路Polyak–Ruppert 迭代平均Polyak–Ruppert averaging · Ruppert–Polyak averaging · 迭代平均平均带噪递推的相关迭代，在线性模型中证明根号样本量极限，精算常步长平均，并展示不合适的步长与非线性偏差。中的精确反例。

一般求根不必来自某个目标的梯度 ​

取

有 $⟨Ax,x⟩=\Vert x{\Vert }^2$、$\Vert Ax{\Vert }^2=2\Vert x{\Vert }^2$，故 $\mu =1,L=\sqrt{2}$，根为0。$A$ 不对称，因此它不是任何二次可微标量函数的梯度矩阵；递推仍可求这个根。无噪声、步长 $1/2$ 的前两步从 $(1,0)$ 到 $(1/2,-1/2)$，再到 $(0,-1/2)$，方向旋转但距离缩小。

这个特定矩阵与步长恰好给出纯旋转关系隐式步理路单调算子与极大单调性Monotone operator · Maximal monotone operator · 极大单调算子用图上的内积不等式统一凸次微分与旋转关系，并以极大性保证稳定隐式步对每个输入都有唯一解。中也出现的两点轨迹，但本页操作是对 $I+J$ 的显式更新，收敛依据是强单调性；旧页分析的是对 $J$ 的隐式平衡。

在有条件无偏有限方差噪声时，换成满足式(2)的步长即可使用上面的收敛证明。这个例子说明随机逼近拥有独立于最小化的求根接口。反过来，若 $h=\mathrm{\nabla }f$，强凸性理路强凸性Strong convexity · Strongly convex function函数在一阶凸下界之外还保留统一二次增长量的曲率性质。给出所需强单调性，再加梯度Lipschitz便成为SGD理路随机梯度下降Stochastic gradient descent · SGD · 随机梯度法在已知历史下用无偏随机梯度更新，推导凸目标期望界与二次噪声底，并按真实梯度查询比较批量和停止保证。的一组充分条件。

三个条件分别怎样失败 ​

只保留“小步长”，可能走不够远。对无噪声 $h(x)=x$，令 ${\eta }_t=1/(t+2{)}^2$。由于

有 $x_T\to x_0/2$，一般不是根。这里平方和有限，但步长总和也有限。

只保留无限行程，也可能永远被噪声推动。对 $h(x)=x$、独立公平 ${\xi }_t=\pm 1$，常步长1给 $x_{t+1}=-{\xi }_{t+1}$，轨迹不会收敛到0。此时 $\sum {\eta }_t^2=\mathrm{\infty }$。这个例子证明所列条件不能随意删去；它没有声称每一个不平方可和的步长都必然失败。

方向不稳定时，两项步长和都满足也无济于事。取 $h(x)=-x$、无噪声和 ${\eta }_t=1/(t+1)$，则 $x_T=(T+1)x_0$。这里根存在唯一，但强单调的方向相反。若噪声有固定非零条件均值 $\beta$，求解的也会变成 $h(x)+\beta =0$，而不是原方程。

输出与误差证书 ​

有限运行应指定总调用数，输出 $x_T$ 和状态；向量更新需 $O(Td)$ 算术及 $O(d)$ 工作空间，oracle的内部成本另计。单次 $\Vert H_{t+1}\Vert$ 很小可能只是噪声抵消，不是根残差证书。如果有独立的精确 $h(x_T)$，强单调性和Cauchy–Schwarz给

只有带噪残差时，则应先给其条件置信半径再换算，验证查询也属于预算。

TD(0)理路TD(0) 算法TD(0) · One-step TD prediction · 零资格迹时序差分算法对固定策略的每次状态转移执行一步表格自举更新，以在线随机近似策略价值。与其他序贯算法也出现这类步长条件，但异步状态访问、Markov数据及投影结构各有额外责任，不能仅因更新外形相似就自动套本页的全空间强单调定理。读实际算法时，先写清它在平均后逼近哪个方程，再检查噪声条件和稳定性，会比只检查 $\sum {\eta }_t$ 更可靠。