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

arXiv:2401.15719 · math.PR, cs.LG, cs.SY, eess.SY, math.OC · Submitted 2024-01-28 · Read on arXiv

math.PR, cs.LG, cs.SY, eess.SY, math.OC

Submitted: 2024-01-28

Updated: 2026-08-29

Terminology

• Wasserstein Distance — 8× in this paper · explained in 4 episodes
• Reinforcement Learning — 7× in this paper · explained in 4 episodes
• Temporal Difference — 5× in this paper
• Lyapunov function — 2× in this paper · explained in 2 episodes
• Q-learning — 2× in this paper · explained in 3 episodes
• Adaptive Algorithm — 1× in this paper · explained in 1 episode
• Non-asymptotic Analysis — 1× in this paper · explained in 2 episodes
• Robustness — 1× in this paper · explained in 5 episodes
• Sample Complexity — 1× in this paper · explained in 15 episodes
• Spectral Gap — 1× in this paper · explained in 5 episodes

Sources

• The ODE Method for Asymptotic Statistics in Stochastic Approximation and Reinforcement Learning
• A short survey of Stein's method
• Concentration of Contractive Stochastic Approximation: Additive and Multiplicative Noise
• Finite-time High-probability Bounds for Polyak-Ruppert Averaged Iterates of Linear Stochastic Approximation
• Regularity of solutions of the Stein equation and rates in the multivariate central limit theorem
• Tight Finite Time Bounds of Two-Time-Scale Linear Stochastic Approximation with Markovian Noise
• Central Limit Theorem for Two-Timescale Stochastic Approximation with Markovian Noise: Theory and Applications
• Online Statistical Inference for Nonlinear Stochastic Approximation with Markovian Data
• Optimal and instance-dependent guarantees for Markovian linear stochastic approximation
• Online covariance estimation for stochastic gradient descent under Markovian sampling

Related papers

• Sharp Deviations Bounds for Dirichlet Weighted Sums with Application to analysis of Bayesian algorithms
• Local Anticoncentration for Gaussian Boson Sampling via Conditional Wishart Geometry
• Beyond the Semicircle: Free Diffusion Models with Prescribed Equilibria
• A New Bound on the Cumulant Generating Function of Dirichlet Processes
• The Site Frequency Spectrum in an Exponentially Growing Population with Selection
• Statistical inference for a multiscale stochastic model of enzyme kinetics via propagation of chaos