mlsanityData to 7 Oct 2026

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

arXiv 2502.09884 ↗First posted 14 Feb 2025cs.LG cs.AIcited by 6

Not on the map. Why?

Abstract (arXiv)

We consider linear two-time-scale stochastic approximation algorithms driven by martingale noise. Recent applications in machine learning motivate the need to understand finite-time error rates, but conventional stochastic approximation analyses focus on either asymptotic convergence in distribution or finite-time bounds that are far from optimal. Prior work on asymptotic central limit theorems (CLTs) suggests that two-time-scale algorithms may be able to achieve 1/√K error in expectation, with a constant given by the expected norm of the limiting Gaussian vector. However, the best known finite-time rates are much slower. We derive the first nonasymptotic Wasserstein-1 CLT for linear two-time-scale stochastic approximation with Polyak-Ruppert averaging driven by martingale difference noise. As a corollary, we show that the expected error achieved by Polyak-Ruppert averaging decays at rate 1/√K, which significantly improves on the rates of convergence in prior works.

Key facts. Cited by 6 papers in the map (data through 7 Oct 2026). Builds on 18 of its 37 references that are in the map. First posted on arXiv 14 Feb 2025.

Builds on

18 of 37 references.

References · 18

  1. 2019Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learningcited by 165
  2. 2020A Finite Time Analysis of Two Time-Scale Actor Critic Methodscited by 120
  3. 2019Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learningcited by 67
  4. 2020On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentrationcited by 65
  5. 2020Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noisecited by 52
  6. 2022Finite-time High-probability Bounds for Polyak-Ruppert Averaged Iterates of Linear Stochastic Approximationcited by 41
  7. 2019Finite-Time Performance Bounds and Adaptive Learning Rate Selection for Two Time-Scale Reinforcement Learningcited by 40
  8. 2019Two Time-scale Off-Policy TD Learning: Non-asymptotic Analysis over Markovian Samplescited by 31
  9. 2019Normal Approximation for Stochastic Gradient Descent via Non-Asymptotic Rates of Martingale CLTcited by 30
  10. 2024Gaussian Approximation and Multiplier Bootstrap for Polyak-Ruppert Averaged Linear Stochastic Approximation with Applications to TD Learningcited by 19
  11. 2022Regularized Gradient Descent Ascent for Two-Player Zero-Sum Markov Gamescited by 18
  12. 2024Rates of Convergence in the Central Limit Theorem for Markov Chains, with an Application to TD Learningcited by 17
6 more
  1. 2023Tight Finite Time Bounds of Two-Time-Scale Linear Stochastic Approximation with Markovian Noisecited by 14
  2. 2024Revisiting Step-Size Assumptions in Stochastic Approximationcited by 10
  3. 2024Fast Two-Time-Scale Stochastic Gradient Method with Applications in Reinforcement Learningcited by 8
  4. 2024Central Limit Theorem for Two-Timescale Stochastic Approximation with Markovian Noise: Theory and Applicationscited by 7
  5. 2024Fast Nonlinear Two-Time-Scale Stochastic Approximation: Achieving O(1/k) Finite-Sample Complexitycited by 7
  6. 2024Accelerated Multi-Time-Scale Stochastic Approximation: Optimal Complexity and Applications in Reinforcement Learning and Multi-Agent Gamescited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 3; 2026: 3.

6 papers.

  1. 2025Gaussian Approximation for Two-Timescale Linear Stochastic Approximationcited by 5
  2. 2025A General-Purpose Theorem for High-Probability Bounds of Stochastic Approximation with Polyak Averagingcited by 4
  3. 2025Central Limit Theorems for Asynchronous Averaged Q-Learningcited by 3
  4. 2026Finite-Sample Wasserstein Error Bounds and Concentration Inequalities for Nonlinear Stochastic Approximationcited by 2
  5. 2026Gaussian Approximation for Asynchronous Q-learningcited by 1
  6. 2026Finite-Time Analysis of Projected Two-Time-Scale Stochastic Approximationcited by 0