# Finite-Time Analysis of Asynchronous Multi-Agent TD Learning

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Jul 2024.

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

- [Almost Sure Convergence of Linear Temporal Difference Learning with Arbitrary Features](https://mlsanity.com/paper/2409.12135/) (2024)
- [Finite Sample Analysis of Linear Temporal Difference Learning with Arbitrary Features](https://mlsanity.com/paper/2505.21391/) (2025)
- [Corruption-Tolerant Asynchronous Q-Learning with Near-Optimal Rates](https://mlsanity.com/paper/2509.08933/) (2025)

## Abstract (arXiv)

Recent research endeavours have theoretically shown the beneficial effect of cooperation in multi-agent reinforcement learning (MARL). In a setting involving N agents, this beneficial effect usually comes in the form of an N-fold linear convergence speedup, i.e., a reduction - proportional to N - in the number of iterations required to reach a certain convergence precision. In this paper, we show for the first time that this speedup property also holds for a MARL framework subject to asynchronous delays in the local agents' updates. In particular, we consider a policy evaluation problem in which multiple agents cooperate to evaluate a common policy by communicating with a central aggregator. In this setting, we study the finite-time convergence of textttAsyncMATD, an asynchronous multi-agent temporal difference (TD) learning algorithm in which agents' local TD update directions are subject to asynchronous bounded delays. Our main contribution is providing a finite-time analysis of textttAsyncMATD, for which we establish a linear convergence speedup while highlighting the effect of time-varying asynchronous delays on the resulting convergence rate.