Concentration and Mean-Square Bounds for Contractive Stochastic Approximation: A Unified Elementary Approach

技术摘要：收缩型随机逼近算法的集中性与均方界限

问题定义
本文研究了如下迭代形式的随机逼近（Stochastic Approximation, SA）算法的有限时间分析：
$$x_{k+1} = x_k + \beta_k (f(x_k) - x_k + M_{k+1})$$
其中 $x_k \in \mathbb{R}^d$ 是迭代值，$\beta_k$ 是步长，$f(\cdot)$ 是一个具有唯一不动点 $x^*$ 的映射，$M_{k+1}$ 是鞅差噪声序列。分析重点针对强化学习（RL）及其他应用中普遍存在的两个特定挑战：

1. 任意范数的收缩性： 映射 $f(\cdot)$ 对任意范数 $\|\cdot\|_c$（例如 Q-learning 中使用的 $\ell_\infty$ 范数）具有收缩性，而非仅限于欧几里得范数。由于平方范数在这些情况下是非光滑的，这使得推导李雅普诺夫漂移不等式变得复杂。
2. 乘性噪声： 噪声并非一致有界；相反，其条件二阶矩随迭代值的范数呈仿射缩放：$\mathbb{E}[\|M_{k+1}\|_c^2 \mid \mathcal{F}_k] \leq \sigma^2 (1 + \|x_k\|_c^2)$。因此，迭代值 $x_k$ 可能是无界的，这阻碍了直接应用要求几乎处处有界的标准鞅集中不等式。

方法论
作者提出了一种统一且基础的框架，避免了先前研究中使用的复杂机制，例如用于平滑非光滑范数的广义 Moreau 包络，或用于处理无界迭代的多阶段自助法（bootstrapping）。核心技术包括：

1. 平均噪声与辅助迭代：
   作者定义了一个平均噪声序列 $\xi_{k+1} = (1-\beta_k)\xi_k + \beta_k M_{k+1}$（其中 $\xi_0=0$）以及辅助迭代 $z_k = x_k - \xi_k$。这种变换允许将原始迭代重写为关于 $z_k$ 的形式：
   $$z_{k+1} = z_k + \beta_k (f(z_k) - z_k + \Delta_k)$$
   其中 $\Delta_k = f(x_k) - f(z_k)$。至关重要的是，这种构造直接产生了误差 $\|z_k - x^*\|_c^2$ 的单步李雅普诺夫漂移不等式，而无需平滑范数或构建包络。误差 $\|x_k - x^*\|_c$ 随后可以通过 $\|z_k - x^*\|_c + \|\xi_k\|_c$ 来界定。

2. 用于控制的归纳论证：
   由于噪声依赖于迭代值，因此在均方分析和集中性分析中必须分别对 $\|\xi_k\|_c$ 进行控制，这里使用了归纳法：

   • 均方界限： 使用直接归纳法证明迭代值在期望意义下是有界的（即 $\mathbb{E}[\|x_k\|_c^2]$ 是一致有界的）。这足以界定 $\mathbb{E}[\|\xi_k\|_c^2]$。
   • 集中性界限： 在一系列“良好”事件 $\{C_k\}$ 上采用概率归纳法，在这些事件中误差受到控制。证明通过计算第一个“良好”事件失效时的概率来分解坏事件并集。在所有先前事件均成立的事件上，迭代值（以及噪声）实际上是有界的，从而允许应用标准的 Azuma-Hoeffding 不等式于截断后的鞅差序列。

主要结果
在假设 $f(\cdot)$ 是收缩因子为 $\lambda < 1$ 的收缩映射且步长为 $\beta_k = \beta / (k+h)$ 的条件下，本文建立了两个主要定理。

1. 均方误差界限（定理 1）：
   在乘性噪声模型下，存在常数使得如果 $h$ 足够大，则：
   $$\mathbb{E}[\|x_k - x^*\|_c^2] \leq \frac{\mathfrak{c}_2}{k+h}$$
   对于 $\ell_\infty$ 范数，速率为 $O(\frac{\sigma^2 \log d}{(1-\lambda)^3 k})$，这与使用 Moreau 包络的 Chen 等人 [13] 的速率相匹配。

2. 极大集中性界限（定理 2）：
   本文推导了一个对所有 $k \geq 0$ 同时成立的高概率界限（极大界限）。对于每个置信水平 $\delta \in (0,1)$，如果步长参数 $h$ 随 $\delta$ 对数级变化（具体为 $h = \Omega(\log(1/\delta))$），则以至少 $1 - \frac{\pi^2}{3}\delta$ 的概率：
   $$\forall k \geq 0: \|x_k - x^*\|_c^2 \leq \frac{\mathfrak{c}_4 \log(d(k+1)/\delta)}{k+h}$$
   该界限具有亚高斯尾部（随 $\log(1/\delta)$ 缩放）。

意义与主张
作者声称其工作提供了乘性噪声模型下、针对潜在无界迭代的 SA 的首个亚高斯尾部的极大（全时）集中性界限。

• 统一性： 该方法利用基础技术（平均噪声和归纳法）统一了均方界限和集中性界限的分析，而非使用专门的机制如 Moreau 包络或复杂的自助法。
• 亚高斯尾部 vs 不可能性： 文中强调了先前研究（Chen 等人 [15]）中确定的权衡：对于乘性噪声，使用与置信水平 $\delta$ 无关的步长序列无法实现亚高斯尾部。通过允许初始步长（通过 $h$）轻微依赖于 $\delta$（即 $h \propto \log(1/\delta)$），作者恢复了亚高斯尾部。如果 $h$ 是固定的，该界限仅在经过一个瞬态期 $k_0 = \Omega(\log(1/\delta))$ 后才成立。
• 泛化性： 作者指出，噪声平均技术和概率归纳法可以推广到其他噪声模型（如重尾噪声）以及具有无界迭代的迭代算法（如 SSP Q-learning, RVI Q-learning）。

文章结论指出，尽管证明技术更为简单，但并未牺牲锐度，成功恢复了现有均方误差的速率，并改进了乘性噪声设置下的集中性界限的尾部行为。