# Finite-Time Convergence Rates of Decentralized Stochastic Approximation with Applications in Multi-Agent and Multi-Task Learning

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Oct 2020.

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

- [A Two-Time-Scale Stochastic Optimization Framework with Applications in Control and Reinforcement Learning](https://mlsanity.com/paper/2109.14756/) (2021)
- [Fast Two-Time-Scale Stochastic Gradient Method with Applications in Reinforcement Learning](https://mlsanity.com/paper/2405.09660/) (2024)
- [Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Sampling](https://mlsanity.com/paper/2402.11800/) (2024)
- [Does Worst-Performing Agent Lead the Pack? Analyzing Agent Dynamics in Unified Distributed SGD](https://mlsanity.com/paper/2409.17499/) (2024)
- [Achieving Tighter Finite-Time Rates for Heterogeneous Federated Stochastic Approximation under Markovian Sampling](https://mlsanity.com/paper/2504.11645/) (2025)
- [A primal-dual perspective for distributed TD-learning](https://mlsanity.com/paper/2310.00638/) (2023)
- [A finite time analysis of distributed Q-learning](https://mlsanity.com/paper/2405.14078/) (2024)
- [Natural Policy Gradient and Actor Critic Methods for Constrained Multi-Task Reinforcement Learning](https://mlsanity.com/paper/2405.02456/) (2024)
- [Core-Halo Decomposition: Decentralizing Large-Scale Fixed-Point Problems](https://mlsanity.com/paper/2605.08681/) (2026)
- [Variance-Reduced Q-Learning over Static and Time-Varying Networks](https://mlsanity.com/paper/2607.21876/) (2026)

## Abstract (arXiv)

We study a decentralized variant of stochastic approximation, a data-driven approach for finding the root of an operator under noisy measurements. A network of agents, each with its own operator and data observations, cooperatively find the fixed point of the aggregate operator over a decentralized communication graph. Our main contribution is to provide a finite-time analysis of this decentralized stochastic approximation method when the data observed at each agent are sampled from a Markov process; this lack of independence makes the iterates biased and (potentially) unbounded. Under fairly standard assumptions, we show that the convergence rate of the proposed method is essentially the same as if the samples were independent, differing only by a log factor that accounts for the mixing time of the Markov processes. The key idea in our analysis is to introduce a novel Razumikhin-Lyapunov function, motivated by the one used in analyzing the stability of delayed ordinary differential equations. We also discuss applications of the proposed method on a number of interesting learning problems in multi-agent systems.