DASA: Delay-Adaptive Multi-Agent Stochastic Approximation
Not on the map. Why?
Abstract (arXiv)
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 textttDASA, a Delay-Adaptive algorithm for multi-agent Stochastic Approximation. We provide a finite-time analysis of textttDASA assuming that the agents' stochastic observation processes are independent Markov chains. Significantly advancing existing results, textttDASA is the first algorithm whose convergence rate depends only on the mixing time τmix and on the average delay τavg while jointly achieving an N-fold convergence speedup under Markovian sampling. Our work is relevant for various SA applications, including multi-agent and distributed temporal difference (TD) learning, Q-learning and stochastic optimization with correlated data.
Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Builds on 12 of its 19 references that are in the map. First posted on arXiv 25 Mar 2024.
Builds on
12 of 19 references.
References · 12
- 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 229
- 2019Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learningcited by 166
- 2022Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learningcited by 79
- 2019Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learningcited by 67
- 2021Asynchronous Stochastic Optimization Robust to Arbitrary Delayscited by 32
- 2024Finite-Time Analysis of On-Policy Heterogeneous Federated Reinforcement Learningcited by 31
- 2023Federated Temporal Difference Learning with Linear Function Approximation under Environmental Heterogeneitycited by 27
- 2020Towards Understanding Asynchronous Advantage Actor-critic: Convergence and Linear Speedupcited by 25
- 2023Federated TD Learning over Finite-Rate Erasure Channels: Linear Speedup under Markovian Samplingcited by 15
- 2023Stability of Q-Learning Through Design and Optimismcited by 8
- 2024Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Samplingcited by 7
- 2023Min-Max Optimization under Delayscited by 1
Built on by
Citing papers per year: 2024: 2.
2 papers.
Similar, not cited
Close in wording, no citation either way
- 2025Achieving Tighter Finite-Time Rates for Heterogeneous Federated Stochastic Approximation under Markovian Sampling
- 2024Accelerated Multi-Time-Scale Stochastic Approximation: Optimal Complexity and Applications in Reinforcement Learning and Multi-Agent Games
- 2025Rainbow Delay Compensation: A Multi-Agent Reinforcement Learning Framework for Mitigating Delayed Observation
- 2024Stochastic Approximation with Unbounded Markovian Noise: A General-Purpose Theorem
- 2023Temporal Difference Learning with Compressed Updates: Error-Feedback meets Reinforcement Learning
- 2024Almost Sure Convergence Rates and Concentration of Stochastic Approximation and Reinforcement Learning with Markovian Noise
- 2024The ODE Method for Stochastic Approximation and Reinforcement Learning with Markovian Noise
- 2024Asymptotic and Finite Sample Analysis of Nonexpansive Stochastic Approximations with Markovian Noise