DASA: Delay-adaptive Multi-agent Stochastic Approximation

Abstract

We consider a setting in which \(N\) agents aim to speedup a common Stochastic Approximation (SA) problem by acting in parallel and communicating with a central server. We assume that the up-link transmissions to the server are subject to asynchronous and potentially unbounded time-varying delays. To mitigate the effect of delays and stragglers while reaping the benefits of distributed computation, we propose \texttt\{DASA\}, a Delay-Adaptive algorithm for multi-agent Stochastic Approximation. We provide a finite-time analysis of \texttt\{DASA\} assuming that the agents' stochastic observation processes are independent Markov chains. Significantly advancing existing results, \texttt\{DASA\} is the first algorithm whose convergence rate depends only on the mixing time \(\tau_\{mix\}\) and on the average delay \(\tau_\{avg\}\) while jointly achieving an \(N\)-fold convergence speedup under Markovian sampling. Our work is relevant for various SA applications, including multi-agent and dis

Stats

• citations1
• S2 citations—
• github stars0
• HF likes0
• heat score2.26
• arxiv keyfabbro2024dasa

Related papers

• Stochastic Approximation With Delayed Updates: Finite-time Rates Under Markovian Sampling (2024)0.00
• Asynchronous Stochastic Approximations With Asymptotically Biased Errors And Deep Multi-agent Learning (2018)0.00
• Achieving Tighter Finite-time Rates For Heterogeneous Federated Stochastic Approximation Under Markovian Sampling (2025)0.00
• DSDF: An Approach To Handle Stochastic Agents In Collaborative Multi-agent Reinforcement Learning (2021)0.00
• Finite Sample Analysis Of Two-timescale Stochastic Approximation With Applications To Reinforcement Learning (2017)0.00
• Finite Time Analysis Of Linear Two-timescale Stochastic Approximation With Markovian Noise (2020)0.00
• On The Convergence Of Consensus Algorithms With Markovian Noise And Gradient Bias (2020)0.00
• Finite-sample Analysis Of Nonlinear Stochastic Approximation With Applications In Reinforcement Learning (2019)10.35