用统一框架分析随机算法的有限时间收敛性，对强化学习很实用。
Non-Asymptotic Convergence of Stochastic Iterative Algorithms: A Lyapunov Framework
- 基于广义Moreau包络构造通用的李雅普诺夫函数。
- 给出均方收敛保证，适用于SGD、Q-learning等算法。
- 覆盖马尔可夫噪声等复杂场景，适合做理论研究者参考。
我们综述了基于李雅普诺夫函数的技巧，用于分析随机迭代算法（即随机逼近算法）在有限时间内的性能，这类算法用于求解固定点方程 $\bar{F}(x)=x$，其中算子 $\bar{F}(\cdot)$ 只能通过带有噪声的查询获得。首先聚焦于标准情形：$\bar{F}(\cdot)$ 相对于某种范数是压缩的，且噪声为独立同分布；说明广义Moreau包络可作为与范数无关的通用李雅普诺夫函数。接着展示该框架如何导出均方收敛保证，并应用于随机梯度下降、线性随机逼近及基于值的强化学习算法（如Q-learning和时序差分学习）。最后讨论扩展至马尔可夫噪声、半范数压缩算子、耗散算子以及高概率界的情形，并总结未解决问题。目标是为随机逼近及其在强化学习中的应用提供一个统一且自洽的有限时间分析路线图。
原文摘要 · Abstract (English)
We survey Lyapunov-based techniques for the finite-time analysis of stochastic iterative algorithms, also known as stochastic approximation (SA) algorithms, for solving fixed-point equations $\bar{F}(x)=x$, where the operator $\bar{F}(\cdot)$ can only be accessed through a noisy oracle. We first focus on the standard setting in which $\bar{F}(\cdot)$ is contractive with respect to some norm and the noise is i.i.d., and explain how generalized Moreau envelopes serve as universal Lyapunov functions, regardless of the underlying norm. We then show how this framework yields mean-square convergence guarantees and applies to stochastic gradient descent, linear SA, and value-based reinforcement learning algorithms such as Q-learning and temporal-difference learning. Finally, we discuss extensions to Markovian noise, seminorm-contractive operators, dissipative operators, and high-probability bounds, and conclude with open problems. The goal is to present a unified and self-contained roadmap for the finite-time analysis of SA and its applications, especially in reinforcement learning.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。