Achieving $ε^{-2}$ Sample Complexity for Single-Loop Actor-Critic under Minimal Assumptions
作者: Ishaq Hamza, Zaiwei Chen
分类: cs.LG, math.OC, stat.ML
发布日期: 2026-05-13
💡 一句话要点
单循环Actor-Critic算法在最小假设下实现ε⁻²样本复杂度
🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)
关键词: 强化学习 Actor-Critic 样本复杂度 单循环算法 Lyapunov漂移 策略迭代 离策略学习
📋 核心要点
- 现有Actor-Critic方法通常需要嵌套循环或对策略进行强假设才能达到ε⁻²样本复杂度，限制了其应用范围。
- 论文提出一种单循环Actor-Critic算法，通过耦合Lyapunov漂移框架，在最小假设下保证了ε⁻²样本复杂度。
- 该分析框架为Actor建立了几何收敛速率，为Critic建立了$\tilde{\mathcal{O}}(1/T)$收敛速率，并通过交叉支配属性结合。
📝 摘要（中文）
本文针对强化学习中的离策略Actor-Critic方法，建立了最后一次迭代的收敛速率。特别地，在单循环、单时间尺度实现以及广泛的策略更新类别（包括近似策略迭代和自然策略梯度方法）下，我们证明了在最小假设（即存在一个诱导不可约马尔可夫链的策略）下，找到ε-最优策略的首个$\tilde{\mathcal{O}}(ε^{-2})$样本复杂度保证。这与现有文献形成鲜明对比，现有文献仅通过嵌套循环更新和/或对策略的强算法依赖性假设（如均匀混合和均匀探索）才能实现$\tilde{\mathcal{O}}(ε^{-2})$样本复杂度。从技术上讲，为了解决单循环实现带来的耦合更新方程以及离策略学习引起的潜在无界迭代所带来的挑战，我们的分析基于耦合Lyapunov漂移框架。具体而言，我们为Actor建立了几何收敛速率，为Critic建立了$\tilde{\mathcal{O}}(1/T)$收敛速率，并通过交叉支配属性将两个Lyapunov漂移不等式结合起来。我们相信这种分析框架具有独立的意义，并且可能适用于其他具有无界性的耦合迭代算法。
🔬 方法详解
问题定义：论文旨在解决强化学习中离策略Actor-Critic算法的样本复杂度问题。现有方法，如需要嵌套循环更新或对策略进行强假设（如均匀混合和均匀探索）才能达到$\tilde{\mathcal{O}}(ε^{-2})$的样本复杂度，这限制了算法的适用性和效率。因此，如何在更宽松的假设下，实现高效的样本复杂度是本论文要解决的核心问题。
核心思路：论文的核心思路是设计一种单循环、单时间尺度的Actor-Critic算法，并利用耦合Lyapunov漂移框架来分析其收敛性。通过精心设计的Lyapunov函数，分别分析Actor和Critic的收敛速率，并利用交叉支配属性将二者联系起来，从而在最小假设下保证算法的样本复杂度。
技术框架：整体框架是一个单循环的Actor-Critic算法，包含Actor和Critic两个模块。Actor负责策略更新，Critic负责价值函数估计。算法采用单时间尺度更新，即Actor和Critic在同一个循环中同时更新。分析框架则基于耦合Lyapunov漂移，通过构建合适的Lyapunov函数，分析Actor和Critic的收敛性，并利用交叉支配属性将二者联系起来。
关键创新：最重要的技术创新在于使用耦合Lyapunov漂移框架来分析单循环Actor-Critic算法的收敛性。与现有方法不同，该方法不需要嵌套循环或对策略进行强假设，从而在更宽松的假设下保证了算法的样本复杂度。此外，交叉支配属性的引入，使得可以有效地分析Actor和Critic之间的相互影响。
关键设计：论文的关键设计包括：1) 单循环的Actor-Critic算法结构，简化了算法的实现；2) 精心设计的Lyapunov函数，能够有效地分析Actor和Critic的收敛性；3) 交叉支配属性，能够将Actor和Critic的收敛性联系起来，从而保证整体算法的收敛性。具体的参数设置和损失函数等技术细节在论文中进行了详细描述，但在此处无法完全展开。
📊 实验亮点
论文在最小假设下，证明了单循环Actor-Critic算法能够达到$\tilde{\mathcal{O}}(ε^{-2})$的样本复杂度，这是现有文献中首次在如此宽松的条件下实现该样本复杂度保证。该结果表明，通过精心设计的算法和分析框架，可以在保证算法性能的同时，降低对环境的假设。
🎯 应用场景
该研究成果可应用于各种需要高效策略学习的强化学习场景，例如机器人控制、游戏AI、推荐系统等。通过降低样本复杂度，可以减少训练时间和计算资源消耗，加速算法的部署和应用。此外，该研究提出的分析框架也为其他耦合迭代算法的收敛性分析提供了借鉴。
📄 摘要（原文）
In this paper, we establish last-iterate convergence rates for off-policy actor--critic methods in reinforcement learning. In particular, under a single-loop, single-timescale implementation and a broad class of policy updates, including approximate policy iteration and natural policy gradient methods, we prove the first $\tilde{\mathcal{O}}(ε^{-2})$ sample complexity guarantee for finding an $ε$-optimal policy under minimal assumptions, namely, the existence of a policy that induces an irreducible Markov chain. This stands in stark contrast to the existing literature, where an $\tilde{\mathcal{O}}(ε^{-2})$ sample complexity is achieved only through nested-loop updates and/or under strong, algorithm-dependent assumptions on the policies, such as uniform mixing and uniform exploration. Technically, to address the challenges posed by the coupled update equations arising from the single-loop implementation, as well as the potentially unbounded iterates induced by off-policy learning, our analysis is based on a coupled Lyapunov drift framework. Specifically, we establish a geometric convergence rate for the actor and an $\tilde{\mathcal{O}}(1/T)$ convergence rate for the critic, and combine the two Lyapunov drift inequalities through a cross-domination property. We believe this analytical framework is of independent interest and may be applicable to other coupled iterative algorithms with unbounded