拓展了随机逼近理论中的罗宾斯-西格蒙德定理，解决强化学习中收敛性分析的瓶颈问题。
Extensions of Robbins-Siegmund Theorem with Applications in Reinforcement Learning
- 引入新假设与平方可和条件，放宽原定理对零阶项的要求
- 首次获得线性函数逼近下Q-learning的几乎必然收敛速率与高概率集中界
- 适用于非可求和零阶项的强化学习算法分析，尤其适合复杂环境下的稳定学习
罗宾斯-西格蒙德定理是分析随机逼近与强化学习中随机迭代算法的核心工具，但其原始形式要求零阶项可求和，在许多重要强化学习场景中无法满足。本文提出扩展该定理，允许零阶项仅平方可和，通过引入关于增量的新温和假设，实现过程几乎必然收敛至有界集。进一步给出了几乎必然收敛速率、高概率集中界以及 $L^p$ 收敛速率。将这些结果应用于随机逼近与强化学习，首次为使用线性函数逼近的 Q-learning 提供了几乎必然收敛速率、高概率集中界与 $L^p$ 收敛速率。
原文摘要 · Abstract (English)
The Robbins-Siegmund theorem establishes the convergence of stochastic processes that are almost supermartingales and is one of the most commonly used approaches for analyzing stochastic iterative algorithms in stochastic approximation and reinforcement learning (RL). However, its original form has a significant limitation as it requires the zero-order term to be summable. In many important RL applications, this summable condition, however, cannot be met. This limitation motivates us to extend the Robbins-Siegmund theorem for almost supermartingales where the zero-order term is not summable, but only square-summable. In particular, we introduce a novel and mild assumption on the increments of the stochastic processes. This together with the square-summable condition enables an almost sure convergence to a bounded set. Additionally, we further provide almost sure convergence rates, high probability concentration bounds, and $L^p$ convergence rates. We then apply the new results to stochastic approximation and RL. Notably, we obtain the first almost sure convergence rate, the first high probability concentration bound, and the first $L^p$ convergence rate for $Q$-learning with linear function approximation.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。