# DASA: Delay-Adaptive Multi-Agent Stochastic Approximation

arXiv: https://arxiv.org/abs/2403.17247 · HTML: https://mlsanity.com/paper/2403.17247/

## 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 (most cited first, 12 of 12)

- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/1902.00923/) (2019)
- [Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning](https://mlsanity.com/paper/2206.08307/) (2022)
- [Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learning](https://mlsanity.com/paper/1905.11425/) (2019)
- [Asynchronous Stochastic Optimization Robust to Arbitrary Delays](https://mlsanity.com/paper/2106.11879/) (2021)
- [Finite-Time Analysis of On-Policy Heterogeneous Federated Reinforcement Learning](https://mlsanity.com/paper/2401.15273/) (2024)
- [Federated Temporal Difference Learning with Linear Function Approximation under Environmental Heterogeneity](https://mlsanity.com/paper/2302.02212/) (2023)
- [Towards Understanding Asynchronous Advantage Actor-critic: Convergence and Linear Speedup](https://mlsanity.com/paper/2012.15511/) (2020)
- [Federated TD Learning over Finite-Rate Erasure Channels: Linear Speedup under Markovian Sampling](https://mlsanity.com/paper/2305.08104/) (2023)
- [Stability of Q-Learning Through Design and Optimism](https://mlsanity.com/paper/2307.02632/) (2023)
- [Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Sampling](https://mlsanity.com/paper/2402.11800/) (2024)
- [Min-Max Optimization under Delays](https://mlsanity.com/paper/2307.06886/) (2023)

## Built on by (most cited first, 2 of 2)

- [Asynchronous Heterogeneous Linear Quadratic Regulator Design](https://mlsanity.com/paper/2404.09061/) (2024)
- [Faster Stochastic Optimization with Arbitrary Delays via Asynchronous Mini-Batching](https://mlsanity.com/paper/2408.07503/) (2024)

## 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.