[2604.00179] Finite-Time Analysis of Projected Two-Time-Scale Stochastic Approximation

Electrical Engineering and Systems Science > Systems and Control arXiv:2604.00179 (eess) [Submitted on 31 Mar 2026] Title:Finite-Time Analysis of Projected Two-Time-Scale Stochastic Approximation Authors:Yitao Bai, Thinh T. Doan, Justin Romberg View a PDF of the paper titled Finite-Time Analysis of Projected Two-Time-Scale Stochastic Approximation, by Yitao Bai and 2 other authors View PDF HTML (experimental) Abstract:We study the finite-time convergence of projected linear two-time-scale stochastic approximation with constant step sizes and Polyak--Ruppert averaging. We establish an explicit mean-square error bound, decomposing it into two interpretable components, an approximation error determined by the constrained subspace and a statistical error decaying at a sublinear rate, with constants expressed through restricted stability margins and a coupling invertibility condition. These constants cleanly separate the effect of subspace choice (approximation errors) from the effect of the averaging horizon (statistical errors). We illustrate our theoretical results through a number of numerical experiments on both synthetic and reinforcement learning problems. Comments: Subjects: Systems and Control (eess.SY); Machine Learning (cs.LG) MSC classes: 62L20, 93E35 Cite as: arXiv:2604.00179 [eess.SY]   (or arXiv:2604.00179v1 [eess.SY] for this version)   https://doi.org/10.48550/arXiv.2604.00179 Focus to learn more arXiv-issued DOI via DataCite (pending registration) Submission h...