Stochastic Approximation With Delayed Updates: Finite-time Rates Under Markovian Sampling

Abstract

Motivated by applications in large-scale and multi-agent reinforcement learning, we study the non-asymptotic performance of stochastic approximation (SA) schemes with delayed updates under Markovian sampling. While the effect of delays has been extensively studied for optimization, the manner in which they interact with the underlying Markov process to shape the finite-time performance of SA remains poorly understood. In this context, our first main contribution is to show that under time-varying bounded delays, the delayed SA update rule guarantees exponentially fast convergence of the *last iterate* to a ball around the SA operator's fixed point. Notably, our bound is *tight* in its dependence on both the maximum delay \(\tau_\{max\}\), and the mixing time \(\tau_\{mix\}\). To achieve this tight bound, we develop a novel inductive proof technique that, unlike various existing delayed-optimization analyses, relies on establishing uniform boundedness of the iterates. As such, our proof

Stats

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

Related papers

• Finite-sample Analysis Of Nonlinear Stochastic Approximation With Applications In Reinforcement Learning (2019)10.35
• Finite Time Analysis Of Linear Two-timescale Stochastic Approximation With Markovian Noise (2020)0.00
• Finite Sample Analysis Of Two-timescale Stochastic Approximation With Applications To Reinforcement Learning (2017)0.00
• DASA: Delay-adaptive Multi-agent Stochastic Approximation (2024)2.26
• Achieving Tighter Finite-time Rates For Heterogeneous Federated Stochastic Approximation Under Markovian Sampling (2025)0.00
• Non-asymptotic Analysis Of Biased Stochastic Approximation Scheme (2019)0.00
• Finite-sample Analysis Of Stochastic Approximation Using Smooth Convex Envelopes (2020)0.00
• On The Convergence Of Consensus Algorithms With Markovian Noise And Gradient Bias (2020)0.00