mlsanityData to 7 Oct 2026

Rates of Convergence in the Central Limit Theorem for Markov Chains, with an Application to TD Learning

arXiv 2401.15719 ↗First posted 28 Jan 2024math.PR cs.LG cs.SYcited by 17

Not on the map. Why?

Abstract (arXiv)

We prove a non-asymptotic central limit theorem for vector-valued martingale differences using Stein's method, and use Poisson's equation to extend the result to functions of Markov Chains. We then show that these results can be applied to establish a non-asymptotic central limit theorem for Temporal Difference (TD) learning with averaging.

Key facts. Cited by 17 papers in the map (data through 7 Oct 2026). Builds on 20 of its 58 references that are in the map. First posted on arXiv 28 Jan 2024.

Builds on

20 of 58 references.

References · 20

  1. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 225
  2. 2019Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learningcited by 165
  3. 2017Bridging the Gap between Constant Step Size Stochastic Gradient Descent and Markov Chainscited by 84
  4. 2020Least Squares Regression with Markovian Data: Fundamental Limits and Algorithmscited by 56
  5. 2022Finite-time High-probability Bounds for Polyak-Ruppert Averaged Iterates of Linear Stochastic Approximationcited by 41
  6. 2019Finite-Time Performance Bounds and Adaptive Learning Rate Selection for Two Time-Scale Reinforcement Learningcited by 40
  7. 2020Nonlinear Two-Time-Scale Stochastic Approximation: Convergence and Finite-Time Performancecited by 35
  8. 2021Optimal and instance-dependent guarantees for Markovian linear stochastic approximationcited by 33
  9. 2019Normal Approximation for Stochastic Gradient Descent via Non-Asymptotic Rates of Martingale CLTcited by 30
  10. 2021The ODE Method for Asymptotic Statistics in Stochastic Approximation and Reinforcement Learningcited by 29
  11. 2021A Statistical Analysis of Polyak-Ruppert Averaged Q-learningcited by 29
  12. 2022Bias and Extrapolation in Markovian Linear Stochastic Approximation with Constant Stepsizescited by 28
8 more
  1. 2023Concentration of Contractive Stochastic Approximation: Additive and Multiplicative Noisecited by 26
  2. 2019Finite-Time Analysis and Restarting Scheme for Linear Two-Time-Scale Stochastic Approximationcited by 18
  3. 2023Online Statistical Inference for Nonlinear Stochastic Approximation with Markovian Datacited by 18
  4. 2019Characterizing the Exact Behaviors of Temporal Difference Learning Algorithms Using Markov Jump Linear System Theorycited by 17
  5. 2022Stochastic linear optimization never overfits with quadratically-bounded losses on general datacited by 16
  6. 2023Tight Finite Time Bounds of Two-Time-Scale Linear Stochastic Approximation with Markovian Noisecited by 14
  7. 2023Online covariance estimation for stochastic gradient descent under Markovian samplingcited by 7
  8. 2024Central Limit Theorem for Two-Timescale Stochastic Approximation with Markovian Noise: Theory and Applicationscited by 7

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 3; 2025: 8; 2026: 6.

17 papers.

Sort:

By area:

  1. 2024Gaussian Approximation and Multiplier Bootstrap for Polyak-Ruppert Averaged Linear Stochastic Approximation with Applications to TD Learningcited by 19
  2. 2024Revisiting Step-Size Assumptions in Stochastic Approximationcited by 10
  3. 2025Gaussian Approximation and Multiplier Bootstrap for Stochastic Gradient Descentcited by 8
  4. 2025Nonasymptotic CLT and Error Bounds for Linear Two-Time-Scale Stochastic Approximationcited by 6
  5. 2025Gaussian Approximation for Two-Timescale Linear Stochastic Approximationcited by 5
  6. 2025A General-Purpose Theorem for High-Probability Bounds of Stochastic Approximation with Polyak Averagingcited by 4
  7. 2025Central Limit Theorems for Asynchronous Averaged Q-Learningcited by 3
  8. 2024Does Worst-Performing Agent Lead the Pack? Analyzing Agent Dynamics in Unified Distributed SGDcited by 2
  9. 2025Improved Central Limit Theorem and Bootstrap Approximations for Linear Stochastic Approximationcited by 2
  10. 2026Finite-Sample Wasserstein Error Bounds and Concentration Inequalities for Nonlinear Stochastic Approximationcited by 2
  11. 2025Dimension-free Score Matching and Time Bootstrapping for Diffusion Modelscited by 1
  12. 2025On the Rate of Gaussian Approximation for Linear Regression Problemscited by 1
5 more
  1. 2026Gaussian Approximation for Asynchronous Q-learningcited by 1
  2. 2026Gaussian Approximation for Multivariate Martingale Sums from Uniformly Ergodic Markov Chainscited by 1
  3. 2026Stability and Sensitivity Analysis of Relative Temporal-Difference Learning: Extended Versioncited by 0
  4. 2026Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Driftcited by 0
  5. 2026A Diffusion Approximation for Temporal-Difference Learning with Linear Features under Markovian Noisecited by 0