技术摘要：重尾马尔可夫噪声下随机逼近的集中性

1. 问题陈述

本文针对随机逼近（SA）算法的有限样本集中性分析，重点关注误差 $\|x_k - x^*\|_c$ 的高概率界，其中 $x^*$ 是平均算子 $\bar{F}$ 的唯一不动点。该研究考虑如下形式的通用递归：
$$x_{k+1} = x_k + \alpha_k (F(x_k, S_k) + Z_k - x_k)$$
其中噪声由两个不同的分量组成：

1. 马尔可夫噪声：一个有限状态马尔可夫链 $\{S_k\}$，在算子估计中引入时间依赖性和偏差。
2. 加性鞅差噪声：序列 $\{Z_k\}$，在给定过去滤子条件下是无偏的。

本研究针对强化学习（RL）和大规模优化等应用中常见的两个主要场景：

• 通用步长：形式为 $\alpha_k = \alpha/(k+h)^z$ 的步长，其中 $z \in (0, 1]$。
• 重尾噪声：加性噪声 $Z_k$ 可能是无界的，服从次韦伯（sub-Weibull）或次帕累托（sub-Pareto）等分布，而非严格有界或次高斯分布。

核心挑战在于在这些综合条件下建立最大集中性界（即以概率 $1-\delta$ 成立的时间一致界），而先前的文献通常要求噪声有界、特定的步长（例如 $O(1/k)$）或独立性假设。

2. 方法论与技术

作者开发了新颖的证明技术，以克服三个具体挑战：通用步长、无界噪声以及马尔可夫依赖性。

2.1 处理通用步长与扩张算子

当步长衰减缓慢（$z < 1$）或随机算子以正概率扩张时，误差可能呈指数增长，使得依赖均匀界的标准“自举”（bootstrapping）技术失效。

• 投影辅助算法：作者引入了一种辅助 SA 算法，其中迭代点被投影到以 $x^*$ 为中心、半径为 $B$ 的球内。这确保了迭代点的一致有界性，防止误差指数增长。
• 重合论证：他们证明，如果半径 $B$ 选择得足够大（依赖于 $\delta$），则投影步骤以高概率处于非激活状态。因此，为有界辅助迭代点推导出的高概率界同样适用于原始无界迭代点。

2.2 处理无界加性噪声

对于无界且独立同分布的加性噪声情形，标准的矩生成函数（MGF）技术失效，因为误差的 MGF 可能不存在。

• 截断论证：作者通过在一个水平 $B$ 处截断加性噪声，定义了一个新的辅助序列。这创造了一个有界噪声环境，使得现有的集中性结果得以适用。
• 偏差校正：截断引入了偏差，将辅助算子的不动点从 $x^*$ 移至 $\tilde{x}$。作者利用平均算子 $\bar{F}$ 的收缩性质界定了这一偏差。他们表明，对于足够大的截断水平，$x^*$ 与 $\tilde{x}$ 之间的距离很小，且原始迭代点与辅助迭代点以高概率重合。

2.3 处理马尔可夫噪声

马尔可夫噪声在误差漂移中引入偏差，阻碍了为无偏鞅差噪声设计的标准李雅普诺夫函数的使用。

• 基于泊松方程的李雅普诺夫函数：分析利用与马尔可夫链相关的泊松方程的解 $V_x$ 来构建一种新颖的李雅普诺夫函数。该函数涉及误差平方的矩生成函数，以及源自 $V_x$ 的校正项。
• 上鞅构造：这种修正后的李雅普诺夫函数使作者能够为误差的 MGF 建立递归不等式，有效地补偿了马尔可夫偏差，从而能够推导出紧密的高概率界。

3. 主要贡献与结果

3.1 有界加性噪声下的通用 SA

本文建立了在通用步长 $\alpha_k = \alpha/(k+h)^z$ 下，具有有限状态马尔可夫噪声和有界加性噪声的 SA 的最大集中性界。误差的尾部行为取决于参数 $D = A_1 + A_3 - 1$，其中 $A_1$ 和 $A_3$ 分别与噪声和算子的 Lipschitz 常数相关。

• 情形 $D < 0$（几乎处处收缩）：
  • 对于 $z=1$，误差尾部为次高斯。
  • 对于 $z \in (0, 1)$，误差尾部为次韦伯。
• 情形 $D = 0$（几乎处处非扩张）：
  • 对于 $z=1$，误差尾部为次高斯。
  • 对于 $z \in (0, 1)$，误差尾部为次韦伯（具体而言，比任何帕累托分布轻，但比任何韦伯分布重）。
• 情形 $D > 0$（以正概率扩张）：
  • 对于 $z=1$，误差尾部为次韦伯。
  • 对于 $z \in (0, 1)$，误差尾部比任何韦伯分布重，但比任何帕累托分布轻（具体形式为 $\exp(\log(1/\delta)^{(1-z)/z})$）。

作者提供了不可能性结果（定理 2.3），表明在一般情况下不可能获得定性上更尖锐的界。具体而言，当 $D \ge 0$ 或 $z < 1$ 时，误差不可能被次高斯分布界定，且推导出的界与反例建立的下界相匹配。

3.2 无界加性噪声下的收缩 SA

对于步长 $\alpha_k = O(1/k)$ 的收缩算子（$D < 0$），作者放宽了对加性噪声有界的假设，允许任意无界分布（例如次韦伯、次帕累托）。

• 尾部行为：集中性界以噪声分布的尾部形式表达。
  • 如果噪声是参数为 $\theta$ 的次韦伯分布，则误差尾部是参数为 $2\theta + 1/2$ 的次韦伯分布（大致比噪声重 2 到 3 倍）。
  • 如果噪声是参数为 $\theta$ 的次帕累托分布，则误差尾部是参数为 $\theta/4$ 的次帕累托分布（要求 $\theta > 4$ 才能收敛）。
• 方法论：该结果是通过第 3.2 节描述的“黑盒截断论证”实现的，该方法将无界情形归约为有界情形，同时控制由截断引入的偏差。

3.3 应用与示例

通用结果被具体化为特定场景：

• 收缩 SA：恢复标准收缩 SA 算法的界。
• 平稳均值估计：推导马尔可夫链经验均值的霍夫丁（Hoeffding）型界。
• 线性 SA：将结果应用于具有赫尔维茨（Hurwitz）矩阵的线性系统。
• Polyak-Ruppert 平均：将他们的界与关于平均的最新结果相结合，表明虽然平均能改善渐近方差，但与未平均的迭代点相比，它可能导致估计误差具有更重的尾部，特别是在算子具有扩张性时。

4. 意义与主张

本文声称提供了首个同时处理以下条件的随机逼近算法的最大集中性界：

1. 有限状态马尔可夫噪声。
2. 通用步长（$O(1/k^z)$，其中 $z \in (0, 1]$）。
3. 潜在的无界重尾加性噪声。

作者强调，他们的结果是阶最优的（在多项式对数因子范围内），并且定性上是尖锐的，这由他们的不可能性定理所证明。他们指出，先前的文献仅限于有界噪声、特定步长（如 $O(1/k)$）或独立性假设，而这些假设在函数逼近等实际应用（如强化学习）中经常被违反。

方法论上的贡献在于结合了基于泊松方程的李雅普诺夫函数（用于处理马尔可夫偏差）和辅助耦合迭代点（通过投影和截断）以处理通用步长和无界噪声。该框架允许对广泛噪声体制和算子属性下的 SA 迭代点尾部行为进行统一分析。