The Bias of Nonlinear Two-Time-scale Stochastic Approximation under Constant Step-Sizes
Abstract
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 α≫β. 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 β≤α3/2. The analysis separates the contributions of initial conditions, fast-timescale tracking error, Markovian dependence, and timescale coupling, thereby clarifying the origin of the β2/α2 term. Our results reveal qualitative differences from the linear TTSA setting previously studied, showing that nonlinear dynamics introduce additional finite-time effects that are absent in the linear case.
Related
- Moment-Accurate Gaussian Mixtures for Constant-Step Stochastic Approximation
- Weak Convergence Rates for Partial-Sum Processes of Nonlinear Stochastic Approximation
- Finite-Time Concentration and Convergence Rates for Projected Two-Time-Scale Stochastic Approximation with Markov Noise
- Normal approximation, moderate and large deviations for the elephant random walk with stops and random step sizes
- Normal approximation and self-normalized moderate deviations for the minimal random walk with random step sizes
BibTeX
@misc{lamouri2026bias,
title = {{The Bias of Nonlinear Two-Time-scale Stochastic Approximation under Constant Step-Sizes}},
author = {Djamel Rassem Lamouri and Dorian Baudry and Nicolas Gast},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.20409},
eprint = {2609.20409},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.20409},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - The Bias of Nonlinear Two-Time-scale Stochastic Approximation under Constant Step-Sizes
AU - Djamel Rassem Lamouri
AU - Dorian Baudry
AU - Nicolas Gast
PY - 2026
DA - 2026/09/17
PB - arXiv
DO - 10.48550/arxiv.2609.20409
UR - https://arxiv.org/abs/2609.20409
AB - 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 α≫β. 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 β≤α^3/2. The analysis separates the contributions of initial conditions, fast-timescale tracking error, Markovian dependence, and timescale coupling, thereby clarifying the origin of the β^2/α^2 term. Our results reveal qualitative differences from the linear TTSA setting previously studied, showing that nonlinear dynamics introduce additional finite-time effects that are absent in the linear case.
ER -