技术摘要：Robbins-Siegmund 定理的扩展及其在强化学习中的应用

1. 问题陈述

Robbins-Siegmund 定理是分析随机迭代算法收敛性的基础工具，尤其在随机逼近和强化学习（RL）领域。该定理确立了“几乎上鞅”（即带有噪声扰动的序列）在零阶项（即加性噪声项）可求和条件下的几乎必然收敛性。

然而，对于许多现代强化学习算法，特别是那些关联于非全局渐近稳定（GAS）常微分方程（ODE）的算法，存在一个显著的局限性。线性 SARSA 和线性 Q-learning 即属于此类。在这些设定下，由于学习率和算法结构的特性，分析中产生的零阶项通常仅是平方可和的（即 $\sum T_n^2 < \infty$），而非可求和的（即 $\sum T_n < \infty$）。

标准的 Robbins-Siegmund 定理在此情形下失效。正如作者所演示的，仅靠 Robbins-Monro 条件（要求 $\sum T_n = \infty$ 且 $\sum T_n^2 < \infty$）不足以保证收敛；若无额外约束，由于噪声中不受控制的“尖峰”，迭代序列可能几乎必然发散。因此，现有理论往往无法为这些算法提供收敛速率或集中界，仅能在强假设或特定策略设计下提供有界性结果。

2. 方法论

本文构建了一个理论框架，将 Robbins-Siegmund 定理扩展至处理零阶项平方可和但不可求和的情形。方法论分为三个阶段：

A. 渐近扩展

作者引入了一个关于随机过程增量的新颖且温和的假设，以控制序列的增长。具体而言，对于满足带有平方可和零阶项的递推关系的序列 $\{z_n\}$，他们施加了一个条件：增量 $|z_{n+1} - z_n|$ 被 $T_n(z_n + 1)$ 线性有界。

• 定理 3 与 4：在该增长条件及零阶项的平方可和性下，作者证明了序列几乎必然收敛至一个有界集（具体为一个球或区间），而非单一点。这解决了在病态示例中因尖峰导致无界增长的发散问题。

B. 非渐近扩展

基于渐近结果，本文推导了非渐近收敛速率和集中界。

• 定理 5：在假设学习率具有特定衰减速率的前提下，确立了收敛至有界集的几乎必然收敛速率。
• 定理 6 与推论 7：推导了具有指数尾部的高概率集中界及 $L_p$ 收敛速率。这些结果利用了受近期文献启发的归纳（自举）方法，允许获得对所有时间步同时成立的最大界。

C. 在随机逼近与强化学习中的应用

作者将这些扩展定理应用于具有非时齐马尔可夫噪声的随机逼近（SA）算法。

• 技术：他们采用了“骨架迭代”技术（来自 Qian 等人，2024），并结合了一种新颖的误差分解（来自 Liu 等人，2025）。这涉及分析一个迭代子序列，其中累积学习率满足 Robbins-Monro 条件。
• 偏差控制：一个关键的技术贡献是对由马尔可夫链的非时齐性引起的偏差项进行了严格控制。通过将证明按当前时间步与马尔可夫链混合时间之间的关系分解为不同情形，他们有效地界定了偏差项，从而使骨架技术首次适用于非时齐设定。

3. 主要贡献

1. Robbins-Siegmund 定理的扩展：本文提供了 Robbins-Siegmund 定理的首次扩展，将零阶项的可求和条件放宽为平方可和条件。这是通过引入关于增量的温和增长假设实现的，确保了收敛至有界集。
2. 收敛速率与界：作者推导了在此不可求和情形下，针对几乎上鞅的首个几乎必然收敛速率、高概率集中界（具有指数尾部）以及 $L_p$ 收敛速率。
3. 非时齐随机逼近分析：该框架成功处理了具有非时齐马尔可夫噪声的随机逼近，而在该设定下，此前 Robbins-Siegmund 定理的应用受到限制或需要更强的假设。
4. 线性 Q-learning 结果：将理论应用于具有线性函数近似和“驯化”Gibbs 行为策略（如 Meyn, 2024 所提出）的线性 Q-learning，本文确立了：
   • 首个收敛至有界集的几乎必然收敛速率。
   • 首个具有指数尾部的高概率集中界。
   • 首个 $L_p$ 收敛速率。
   • 这些结果无需算法调整（如目标网络）或对特征施加限制性假设，只要行为策略满足特定的稳定性条件即可成立。

4. 结果

本文提出了一套全面的理论保证：

• 收敛至集合：对于关联 ODE 非全局渐近稳定的算法，证明了迭代序列几乎必然收敛至一个有界集，而非单一点。
• 可量化的速率：收敛不仅仅是渐近的；本文提供了明确的速率（例如 $O(t^{-\zeta})$）以及偏离概率的界。
• 与先前工作的比较：
  • 不同于 Meyn (2024) 和 Liu 等人 (2025)（确立了几乎必然有界性或二阶矩的 $L_2$ 收敛速率），本工作确立了所有 $p \ge 2$ 的 $L_p$ 收敛速率以及收敛至集合的几乎必然收敛速率。
  • 不同于 Qian 等人 (2024) 和 Borkar 等人 (2025)（专注于全局渐近稳定 ODE，即收敛至单一点），本工作解决了非全局渐近稳定情形。
  • 线性 Q-learning 的结果代表了相对于先前稳定性分析的重大进步，提供了包括速率和集中性在内的收敛动力学的完整刻画。

5. 意义与主张

作者将此项工作定位为分析不符合经典全局渐近稳定框架的现代强化学习算法所必需的理论进展。

• 弥合差距：本文声称弥合了文献中的一个关键空白，即由于零阶项不可求和，标准 Robbins-Siegmund 定理无法适用的情形。
• 首创性：作者明确声称，在标准假设下（特别是驯化 Gibbs 策略），为具有线性函数近似的线性 Q-learning 提供了首个几乎必然收敛速率、高概率集中界和 $L_p$ 收敛速率。
• 谦逊：作者对其主张的范围持谦逊态度。他们承认，其结果依赖于特定的学习率调度（平方可和且递减），并未直接解决恒定步长情形或不可平方求和的学习率。他们还指出，虽然其框架适用于线性 SARSA，但为了简洁起见， presentation 聚焦于线性 Q-learning。此外，他们进一步澄清，其结果刻画的是收敛至有界集，这是在不施加强结构假设的情况下，针对非全局渐近稳定 ODE 所能达到的最佳结果，而非收敛至唯一不动点。

总之，本文提供了一套强大的理论工具，用于分析此前被认为在理论上难以处理的 regime 中随机迭代算法的稳定性与收敛性，特别是为线性 Q-learning 提供了首个细粒度的收敛刻画。