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

Sergey Samsonov, Eric Moulines, Qi-Man Shao, Zhuo-Song Zhang, Alexey Naumov
5/26/2024
stat.MLcs.LGmath.OC

No confident code implementation found for this paper.

Abstract

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.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. Any repos shown below are weak matches — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

Statistical inference for Linear Stochastic Approximation with Markovian Noise

90% match2025

Gaussian Approximation for Two-Timescale Linear Stochastic Approximation

88% match2025

Gaussian Approximation and Multiplier Bootstrap for Stochastic Gradient Descent

87% match2025

Statistical Inference for Temporal Difference Learning with Linear Function Approximation

86% match2024

High-Order Error Bounds for Markovian LSA with Richardson-Romberg Extrapolation

85% match2025

A General-Purpose Theorem for High-Probability Bounds of Stochastic Approximation with Polyak Averaging

83% match2025

Cite this paper

@article{samsonov2024gaussian,
  title  = {Gaussian Approximation and Multiplier Bootstrap for Polyak-Ruppert Averaged Linear Stochastic Approximation with Applications to TD Learning},
  author = {Sergey Samsonov and Eric Moulines and Qi-Man Shao and Zhuo-Song Zhang and Alexey Naumov},
  year   = {2024},
  eprint = {2405.16644},
  archivePrefix = {arXiv},
  doi    = {10.48550/arXiv.2405.16644},
  url    = {http://arxiv.org/abs/2405.16644v2},
  journal = {NEURIPS 2024 2024}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2405.16644.svg)](https://codeofpaper.com/paper/2405.16644)

Discussion