Finite-Time Analysis of Projected Two-Time-Scale Stochastic Approximation

Yitao Bai; Thinh T. Doan; Justin Romberg

eess.SYMar 31, 2026

Finite-Time Analysis of Projected Two-Time-Scale Stochastic Approximation

Authors: Yitao Bai, Thinh T. Doan, Justin Romberg

Organizations: Department of Aerospace Engineering, University of Texas at Austin · Department of Electrical and Computer Engineering, Georgia Tech

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.

Figures & tables

Fig. 1: Error decomposition of projected TTSA.

Panel of Figure 3 — Fig. 3: Performance of GTD under different $\Phi$ .

Polyak-Ruppert Averaging

See all 8 papers

Finite-Time Concentration and Convergence Rates for Projected Two-Time-Scale Stochastic Approximation with Markov Noise
Sep 28, 2026Rahul Singh, Vivek S. Borkar, Eric MoulinesLast-Iterate Convergence Stochastic Approximation
Laboratoire de Recherche de l’EPITA, Paris, France · Indian Institute of Technology Bombay · Mohamed bin Zayed University of Artificial Intelligence, Abu Dhabi, United Arab Emirates
Nonasymptotic CLT and Error Bounds for Linear Two-Time-Scale Stochastic Approximation
Feb 14, 2025Seo Taek Kong, Sihan Zeng, Thinh T. Doan +1Stochastic Approximation Two-Timescale Stochastic Approximation
Coordinated Science Laboratory, Department of Electrical and Computer Engineering, University of Illinois Urbana-Champaign, Urbana, IL 61801 USA · JP Morgan AI Research, Palo Alto, CA 94304 USA · Aerospace Engineering and Engineering Mechanics Department at University of Texas, Austin, Austin, TX 78712 USA
The Bias of Nonlinear Two-Time-scale Stochastic Approximation under Constant Step-Sizes
Sep 17, 2026Djamel Rassem Lamouri, Dorian Baudry, Nicolas GastStochastic Approximation Two-Timescale Stochastic Approximation
Univ. Grenoble Alpes, CNRS, Inria Grenoble INP, LIG, 38000 Grenoble France

Sep 28, 2026J/K move · Enter open · S save

Finite-Time Concentration and Convergence Rates for Projected Two-Time-Scale Stochastic Approximation with Markov Noise

Rahul Singh, Vivek S. Borkar, Eric Moulines

Laboratoire de Recherche de l’EPITA, Paris, France · Indian Institute of Technology Bombay · Mohamed bin Zayed University of Artificial Intelligence, Abu Dhabi, United Arab Emirates

Last-Iterate Convergence Stochastic Approximation Constrained RL Two-Timescale Stochastic Approximation

Open paper AskPDF arXiv

We study finite-time concentration and convergence rates for projected two-time-scale stochastic approximation driven by a controlled Markov chain. The averaged fast map is contractive, while the slow iterate is projected onto a compact convex polyhedron. The associated projected ordinary differential equation may have a discontinuous vector field at the boundary, preventing a direct application of standard analyses based on Lipschitz vector fields. Using the Skorokhod map, we establish explicit high-probability bounds for tracking the moving fast equilibrium and the projected slow dynamics. These bounds separate martingale fluctuations, Markov-noise residuals, and the bias due to time-scale separation. A Lipschitz Lyapunov function satisfying a uniform decrease condition over fixed time intervals yields almost-sure convergence, with explicit last-iterate rates when the decrease admits a power lower bound. Under uniform Lyapunov contraction, polynomial step sizes yield joint fast-tracking and slow Lyapunov-error exponents arbitrarily close to

1/3

. Under the additional assumption that the reduced slow update map is a Euclidean contraction, logarithmically separated step sizes improve the joint rate to

O(n^{-1/2}\log n)

almost surely, including for boundary equilibria. The same rate holds under a distinct geometric condition involving a strictly attracting face of a box and a fast equilibrium that is constant on that face. An actor-critic application achieves an almost-sure value-gap rate of

O(n^{-1}\log n)

relative to the optimum within the constrained policy class. Further applications include projected TD(0) and projected stochastic gradient descent. We also extend the analysis to projection of the fast recursion under Euclidean contractivity.

Abstract

Polyak-Ruppert Averaging

Explore similar work

Finite-Time Concentration and Convergence Rates for Projected Two-Time-Scale Stochastic Approximation with Markov Noise

Nonasymptotic CLT and Error Bounds for Linear Two-Time-Scale Stochastic Approximation

The Bias of Nonlinear Two-Time-scale Stochastic Approximation under Constant Step-Sizes