Research map / Learning theory and algorithms / Sample complexity
Gaussian Approximation and Multiplier Bootstrap for Polyak-Ruppert Averaged Linear Stochastic Approximation with Applications to TD Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Derives a Berry-Esseen bound for Polyak-Ruppert averaged linear stochastic approximation (LSA) and a non-asymptotically valid multiplier bootstrap for confidence intervals, illustrated on TD learning.
Problem
Normal approximation rate (Berry-Esseen) for Polyak-Ruppert averaged LSA iterates and non-asymptotic validity of bootstrap confidence sets for LSA parameter estimates, which prior concentration-based and asymptotic methods did not provide.
Approach
Applies a randomized multivariate concentration/Gaussian approximation method for nonlinear statistics to the PR-averaged LSA error, and extends the online multiplier bootstrap (randomly perturbed LSA iterates updated alongside the main iterate) with an explicit error bound in the bootstrap world.
Key results
- Berry-Esseen bound for PR-averaged LSA with step size c0/k^gamma gives convex-distance rate n^{-1/4} at gamma=1/2 (aggressive step size c0/sqrt(k)).
- Multiplier bootstrap confidence sets for LSA are non-asymptotically valid with coverage error of order n^{-1/4} (with probability at least 1-6/n).
- Numerical TD experiments on Garnet MDP show the sup distance Delta_n is smallest for gamma=1/2 and consistent with n^{-1/4} decay.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the step-size schedule αₖ = c₀/√k instead of other tested powers (ablation) | Polyak-Ruppert averaged LSA for TD learning · TD learning on Garnet problem | normal-approximation error Δₙ: n^{-1/4} | Helped |
| Use the step-size power γ = 0.65 or γ = 0.7 instead of γ = 1/2 (ablation) | Polyak-Ruppert averaged LSA for TD learning · TD learning on Garnet problem | normal-approximation error Δₙ | Hurt |
Surprising findings
- The optimal normal-approximation rate is achieved with the aggressive step size gamma=1/2, rather than the step size commonly recommended for PR averaging.
Limitations
- Analysis assumes i.i.d. samples; extension to Markovian noise is left open.
- Requires almost-surely bounded noise and matrix norms (strong assumption), with relaxation only conjectured.
- Bootstrap bound requires additional sample-size conditions (e.g., lambda_min lower bound scaling with log n) and bounds depend on problem constants; last-iterate Berry-Esseen only sketched.
Experimental setup
Datasets: synthetic Garnet MDP (Ns=10, 2 actions, branching factor 3)
Benchmarks: Garnet MDP policy evaluation with TD learning
Metrics: Kolmogorov-type distance Delta_n between normal approximatio empirical scaling exponent of Delta_n
Baselines: Stein-method normal approximation for SA Markovian LSA Wasserstein normal approximation
Builds on: Polyak-Ruppert averaging multiplier bootstrap randomized multivariate concentration inequality for nonlinear statistics
Closest papers by meaning
- Statistical inference for Linear Stochastic Approximation with Markovian Noise (NeurIPS 2025 · similarity 0.90)
- A General-Purpose Theorem for High-Probability Bounds of Stochastic Approximation with Polyak Averaging (NeurIPS 2025 · similarity 0.86)
- Effectiveness of Constant Stepsize in Markovian LSA and Statistical Inference (AAAI 2024 · similarity 0.83)
- Almost Sure Convergence of Linear Temporal Difference Learning with Arbitrary Features (NeurIPS 2026 · similarity 0.82)
- Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson–Romberg Extrapolation (ICLR 2025 · similarity 0.82)
- Generalization Analysis of Stochastic Weight Averaging with General Sampling (ICML 2024 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.