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

arXiv: https://arxiv.org/abs/2405.16644 · HTML: https://mlsanity.com/paper/2405.16644/

## Key facts

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

## Builds on (most cited first, 22 of 22)

- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Learning to Optimize Via Posterior Sampling](https://mlsanity.com/paper/1301.2609/) (2013)
- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)](https://mlsanity.com/paper/1306.2119/) (2013)
- [Statistical Inference for Model Parameters in Stochastic Gradient Descent](https://mlsanity.com/paper/1610.08637/) (2016)
- [On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration](https://mlsanity.com/paper/2004.04719/) (2020)
- [The promises and pitfalls of Stochastic Gradient Langevin Dynamics](https://mlsanity.com/paper/1811.10072/) (2018)
- [Finite-time High-probability Bounds for Polyak-Ruppert Averaged Iterates of Linear Stochastic Approximation](https://mlsanity.com/paper/2207.04475/) (2022)
- [Online Covariance Matrix Estimation in Stochastic Gradient Descent](https://mlsanity.com/paper/2002.03979/) (2020)
- [Bootstrapping Upper Confidence Bound](https://mlsanity.com/paper/1906.05247/) (2019)
- [Optimal and instance-dependent guarantees for Markovian linear stochastic approximation](https://mlsanity.com/paper/2112.12770/) (2021)
- [A Tale of Two-Timescale Reinforcement Learning with the Tightest Finite-Time Bound](https://mlsanity.com/paper/1911.09157/) (2019)
- [Normal Approximation for Stochastic Gradient Descent via Non-Asymptotic Rates of Martingale CLT](https://mlsanity.com/paper/1904.02130/) (2019)
- [Bias and Extrapolation in Markovian Linear Stochastic Approximation with Constant Stepsizes](https://mlsanity.com/paper/2210.00953/) (2022)
- [Tight High Probability Bounds for Linear Stochastic Approximation with Fixed Stepsize](https://mlsanity.com/paper/2106.01257/) (2021)
- [Online Bootstrap Inference For Policy Evaluation in Reinforcement Learning](https://mlsanity.com/paper/2108.03706/) (2021)
- [On the Stability of Random Matrix Product with Markovian Noise: Application to Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/2102.00185/) (2021)
- [Finite time analysis of temporal difference learning with linear function approximation: Tail averaging and regularisation](https://mlsanity.com/paper/2210.05918/) (2022)
- [Improved High-Probability Bounds for the Temporal Difference Learning Algorithm via Exponential Stability](https://mlsanity.com/paper/2310.14286/) (2023)
- [Rates of Convergence in the Central Limit Theorem for Markov Chains, with an Application to TD Learning](https://mlsanity.com/paper/2401.15719/) (2024)
- [Online Bootstrap Inference with Nonconvex Stochastic Gradient Descent Estimator](https://mlsanity.com/paper/2306.02205/) (2023)
- [Off-policy Learning with Eligibility Traces: A Survey](https://mlsanity.com/paper/1304.3999/) (2013)

## Built on by (most cited first, 19 of 19)

- [Gaussian Approximation and Multiplier Bootstrap for Stochastic Gradient Descent](https://mlsanity.com/paper/2502.06719/) (2025)
- [Nonasymptotic CLT and Error Bounds for Linear Two-Time-Scale Stochastic Approximation](https://mlsanity.com/paper/2502.09884/) (2025)
- [A Finite Sample Analysis of Distributional TD Learning with Linear Function Approximation](https://mlsanity.com/paper/2502.14172/) (2025)
- [Extensions of Robbins-Siegmund Theorem with Applications in Reinforcement Learning](https://mlsanity.com/paper/2509.26442/) (2025)
- [Online Covariance Estimation in Nonsmooth Stochastic Approximation](https://mlsanity.com/paper/2502.05305/) (2025)
- [Central Limit Theorems for Asynchronous Averaged Q-Learning](https://mlsanity.com/paper/2509.18964/) (2025)
- [Improved Central Limit Theorem and Bootstrap Approximations for Linear Stochastic Approximation](https://mlsanity.com/paper/2510.12375/) (2025)
- [Statistical Inference for Online Algorithms](https://mlsanity.com/paper/2505.17300/) (2025)
- [On the Rate of Gaussian Approximation for Linear Regression Problems](https://mlsanity.com/paper/2509.14039/) (2025)
- [Sharp Gaussian approximations for Decentralized Federated Learning](https://mlsanity.com/paper/2505.08125/) (2025)
- [Statistical Inference for Linear Functionals of Online Least-squares SGD when t gtrsim d1+δ](https://mlsanity.com/paper/2510.19734/) (2025)
- [Accelerated Distributional Temporal Difference Learning with Linear Function Approximation](https://mlsanity.com/paper/2511.12688/) (2025)
- [Gaussian Approximation for Asynchronous Q-learning](https://mlsanity.com/paper/2604.07323/) (2026)
- [Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Drift](https://mlsanity.com/paper/2605.07104/) (2026)
- [Gaussian Approximation in Wasserstein-p: Markovian Martingale Differences and Stochastic Approximation](https://mlsanity.com/paper/2609.09480/) (2026)
- [Sharp asymptotic theory for Q-learning with LDTZ learning rate and its generalization](https://mlsanity.com/paper/2604.04218/) (2026)
- [Online Covariance Estimation in Averaged SGD: Improved Batch-Mean Rates and Minimax Optimality via Trajectory Regression](https://mlsanity.com/paper/2604.10814/) (2026)
- [On Gaussian approximation for entropy-regularized Q-learning with function approximation](https://mlsanity.com/paper/2605.17678/) (2026)
- [Clipped or Unclipped? Finite-Sample Trade-offs for Averaged SGD under Heavy-Tailed Noise](https://mlsanity.com/paper/2609.32962/) (2026)

## 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.