The Bias of Nonlinear Two-Time-scale Stochastic Approximation under Constant Step-Sizes
Two-timescale stochastic approximation (TTSA) is a fundamental tool for analyzing coupled iterative algorithms in reinforcement learning, optimization, and stochastic control. However, finite-time guarantees for nonlinear two-timescale schemes remain difficult to obtain, especially under constant step-sizes. In this paper, we study nonlinear TTSA with step-sizes $α\ggβ$. Under standard stability, regularity, and Markovian noise assumptions, we upper bound the mean-squared error and the bias of both iterates around their limiting equilibria. Our bounds scale as $O(α+β^2/α^2)$, which we prove to be tight when $β\leα^{3/2}$. The analysis separates the contributions of initial conditions, fas...
| Authors | Djamel Rassem Lamouri, Dorian Baudry, Nicolas Gast |
|---|---|
| Primary category | cs.LG |
| Published | 17 September 2026 |
| Last updated at source | 17 September 2026 |
Silytics shows public metadata from arXiv and links to the original. Information may be incomplete or out of date. Last refreshed 17 October 2026. Licenses and terms of the original apply to the work itself. Not financial, legal or professional advice.