Almost Sure Convergence Rates And Concentration Of Stochastic Approximation And Reinforcement Learning With Markovian Noise

Abstract

This paper establishes the first almost sure convergence rate and the first maximal concentration bound with exponential tails for general contractive stochastic approximation algorithms with Markovian noise. As a corollary, we also obtain convergence rates in \(L^p\). Key to our successes is a novel discretization of the mean ODE of stochastic approximation algorithms using intervals with diminishing (instead of constant) length. As applications, we provide the first almost sure convergence rate for \(Q\)-learning with Markovian samples without count-based learning rates. We also provide the first concentration bound for off-policy temporal difference learning with Markovian samples.

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyqian2024almost

Related papers

• Concentration Of Contractive Stochastic Approximation And Reinforcement Learning (2021)0.00
• The ODE Method For Stochastic Approximation And Reinforcement Learning With Markovian Noise (2024)0.00
• Finite-sample Analysis Of Nonlinear Stochastic Approximation With Applications In Reinforcement Learning (2019)10.35
• On The Convergence Of Consensus Algorithms With Markovian Noise And Gradient Bias (2020)0.00
• On The Stability Of Random Matrix Product With Markovian Noise: Application To Linear Stochastic Approximation And TD Learning (2021)0.00
• Uncertainty Quantification For Markov Chain Induced Martingales With Application To Temporal Difference Learning (2025)0.00
• Non-asymptotic Convergence Of Adam-type Reinforcement Learning Algorithms Under Markovian Sampling (2020)0.00
• Simple And Optimal Methods For Stochastic Variational Inequalities, II: Markovian Noise And Policy Evaluation In Reinforcement Learning (2020)8.60