单时标强化学习算法实现全局最优收敛，样本效率提升显著。
On the Convergence of Single-Timescale Actor-Critic
- 构建解析框架处理耦合递推，突破传统收敛分析瓶颈。
- 达到ε-最优策略的样本复杂度为O(ε⁻³)，优于现有O(ε⁻⁴)。
- 需以O(k⁻²ᐟ³)速率衰减步长，不同于常规优化中的O(k⁻¹ᐟ²)。
我们分析了有限状态空间下无限时域折扣马尔可夫决策过程（MDPs）中单时标演员-评论家（AC）算法的全局收敛性。为此，我们引入一个简洁的分析框架，用于处理算法中固有的复杂耦合递推关系。利用该框架，我们证明该算法在样本复杂度为O(ε⁻³)时收敛至ε-接近全局最优策略，显著优于现有O(ε⁻²)复杂度下获得ε-接近驻点策略的结果。而后者等价于使用梯度支配引理实现ε-接近全局最优策略所需的O(ε⁻⁴)复杂度。此外，我们表明，实现此改进要求演员与评论家的步长均以O(k⁻²ᐟ³)速率随迭代次数k衰减，这与非凸优化中常用的O(k⁻¹ᐟ²)速率不同。
原文摘要 · Abstract (English)
We analyze the global convergence of the single-timescale actor-critic (AC) algorithm for the infinite-horizon discounted Markov Decision Processes (MDPs) with finite state spaces. To this end, we introduce an elegant analytical framework for handling complex, coupled recursions inherent in the algorithm. Leveraging this framework, we establish that the algorithm converges to an $ε$-close \textbf{globally optimal} policy with a sample complexity of \( O(ε^{-3}) \). This significantly improves upon the existing complexity of $O(ε^{-2})$ to achieve $ε$-close \textbf{stationary policy}, which is equivalent to the complexity of $O(ε^{-4})$ to achieve $ε$-close \textbf{globally optimal} policy using gradient domination lemma. Furthermore, we demonstrate that to achieve this improvement, the step sizes for both the actor and critic must decay as \( O(k^{-\frac{2}{3}}) \) with iteration $k$, diverging from the conventional \( O(k^{-\frac{1}{2}}) \) rates commonly used in (non)convex optimization.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。