首次在非线性双时间尺度随机逼近中实现1/k的收敛速率。
$O(1/k)$ Finite-Time Bound for Non-Linear Two-Time-Scale Stochastic Approximation
- 通过平均噪声序列重构迭代，结合归纳法证明期望有界。
- 在真实时间尺度分离下，误差率从O(1/k^{2/3})提升至O(1/k^a)（a<1）。
- 适用于强化学习与优化中的梯度下降-上升等算法。
双时间尺度随机逼近（SA）是一种具有耦合迭代的算法，在强化学习、优化和博弈控制中广泛应用。本文针对带有压缩映射的非线性双时间尺度迭代，推导出均方误差界。当两个步长均为Θ(1/k)时，即通常称为单时间尺度但多耦合序列的情形，我们首次在无需额外光滑性假设下获得O(1/k)的收敛速率。在真正的时间尺度分离设置下，此前最优界为O(1/k^{2/3})，我们将其改进为任意a<1的O(1/k^a)，逼近最优的O(1/k)。分析关键在于将原始迭代重写为方差快速衰减的平均噪声序列，并采用归纳法证明迭代序列在期望上是有界的。结果适用于Polyak平均，以及来自强化学习和优化的算法，包括梯度下降-上升和双时间尺度拉格朗日优化。
原文摘要 · Abstract (English)
Two-time-scale stochastic approximation (SA) is an algorithm with coupled iterations which has found broad applications in reinforcement learning, optimization and game control. In this work, we derive mean squared error bounds for non-linear two-time-scale iterations with contractive mappings. In the setting where both stepsizes are order $Θ(1/k)$, commonly referred to as single time-scale SA with multiple coupled sequences, we obtain the first $O(1/k)$ rate without imposing additional smoothness assumptions. In the setting with true time-scale separation, the previous best bound was $O(1/k^{2/3})$. We improve this to $O(1/k^a)$ for any $a<1$ approaching the optimal $O(1/k)$ rate. The key step in our analysis involves rewriting the original iteration in terms of an averaged noise sequence whose variance decays sufficiently fast. Additionally, we use an induction-based approach to show that the iterates are bounded in expectation. Our results apply to Polyak averaging, as well as to algorithms from reinforcement learning, and optimization, including gradient descent-ascent and two-time-scale Lagrangian optimization.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。