mlsanityData to 7 Oct 2026

Gaussian Approximation and Multiplier Bootstrap for Polyak-Ruppert Averaged Linear Stochastic Approximation with Applications to TD Learning

arXiv 2405.16644 ↗First posted 26 May 2024stat.ML cs.LG math.OCcited by 19

Not on the map. Why?

Abstract (arXiv)

In this paper, we obtain the Berry-Esseen bound for multivariate normal approximation for the Polyak-Ruppert averaged iterates of the linear stochastic approximation (LSA) algorithm with decreasing step size. Moreover, we prove the non-asymptotic validity of the confidence intervals for parameter estimation with LSA based on multiplier bootstrap. This procedure updates the LSA estimate together with a set of randomly perturbed LSA estimates upon the arrival of subsequent observations. We illustrate our findings in the setting of temporal difference learning with linear function approximation.

Key facts. Cited by 19 papers in the map (data through 7 Oct 2026). Builds on 22 of its 68 references that are in the map. First posted on arXiv 26 May 2024.

Builds on

22 of 68 references.

References · 22

  1. 2015An Introduction to Matrix Concentration Inequalitiescited by 391
  2. 2013Learning to Optimize Via Posterior Samplingcited by 253
  3. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 225
  4. 2013Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)cited by 110
  5. 2016Statistical Inference for Model Parameters in Stochastic Gradient Descentcited by 71
  6. 2020On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentrationcited by 65
  7. 2018The promises and pitfalls of Stochastic Gradient Langevin Dynamicscited by 56
  8. 2022Finite-time High-probability Bounds for Polyak-Ruppert Averaged Iterates of Linear Stochastic Approximationcited by 41
  9. 2020Online Covariance Matrix Estimation in Stochastic Gradient Descentcited by 37
  10. 2019Bootstrapping Upper Confidence Boundcited by 36
  11. 2021Optimal and instance-dependent guarantees for Markovian linear stochastic approximationcited by 33
  12. 2019A Tale of Two-Timescale Reinforcement Learning with the Tightest Finite-Time Boundcited by 31
10 more
  1. 2019Normal Approximation for Stochastic Gradient Descent via Non-Asymptotic Rates of Martingale CLTcited by 30
  2. 2022Bias and Extrapolation in Markovian Linear Stochastic Approximation with Constant Stepsizescited by 28
  3. 2021Tight High Probability Bounds for Linear Stochastic Approximation with Fixed Stepsizecited by 26
  4. 2021Online Bootstrap Inference For Policy Evaluation in Reinforcement Learningcited by 26
  5. 2022Finite time analysis of temporal difference learning with linear function approximation: Tail averaging and regularisationcited by 23
  6. 2021On the Stability of Random Matrix Product with Markovian Noise: Application to Linear Stochastic Approximation and TD Learningcited by 22
  7. 2023Improved High-Probability Bounds for the Temporal Difference Learning Algorithm via Exponential Stabilitycited by 20
  8. 2024Rates of Convergence in the Central Limit Theorem for Markov Chains, with an Application to TD Learningcited by 17
  9. 2013Off-policy Learning with Eligibility Traces: A Surveycited by 12
  10. 2023Online Bootstrap Inference with Nonconvex Stochastic Gradient Descent Estimatorcited by 12

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 12; 2026: 7.

19 papers.

Sort:

  1. 2025Gaussian Approximation and Multiplier Bootstrap for Stochastic Gradient Descentcited by 8
  2. 2025Nonasymptotic CLT and Error Bounds for Linear Two-Time-Scale Stochastic Approximationcited by 6
  3. 2025A Finite Sample Analysis of Distributional TD Learning with Linear Function Approximationcited by 5
  4. 2025Extensions of Robbins-Siegmund Theorem with Applications in Reinforcement Learningcited by 5
  5. 2025Online Covariance Estimation in Nonsmooth Stochastic Approximationcited by 4
  6. 2025Central Limit Theorems for Asynchronous Averaged Q-Learningcited by 3
  7. 2025Statistical Inference for Online Algorithmscited by 2
  8. 2025Improved Central Limit Theorem and Bootstrap Approximations for Linear Stochastic Approximationcited by 2
  9. 2025Sharp Gaussian approximations for Decentralized Federated Learningcited by 1
  10. 2025On the Rate of Gaussian Approximation for Linear Regression Problemscited by 1
  11. 2025Statistical Inference for Linear Functionals of Online Least-squares SGD when t gtrsim d1+δcited by 1
  12. 2026Gaussian Approximation for Asynchronous Q-learningcited by 1
7 more
  1. 2026Gaussian Approximation for Multivariate Martingale Sums from Uniformly Ergodic Markov Chainscited by 1
  2. 2025Accelerated Distributional Temporal Difference Learning with Linear Function Approximationcited by 0
  3. 2026Sharp asymptotic theory for Q-learning with LDTZ learning rate and its generalizationcited by 0
  4. 2026Online Covariance Estimation in Averaged SGD: Improved Batch-Mean Rates and Minimax Optimality via Trajectory Regressioncited by 0
  5. 2026Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Driftcited by 0
  6. 2026On Gaussian approximation for entropy-regularized Q-learning with function approximationcited by 0
  7. 2026Clipped or Unclipped? Finite-Sample Trade-offs for Averaged SGD under Heavy-Tailed Noisecited by 0