# Finite-Time Performance of Distributed Temporal Difference Learning with Linear Function Approximation

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Jul 2019.

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

- [The Blessing of Heterogeneity in Federated Q-Learning: Linear Speedup and Beyond](https://mlsanity.com/paper/2305.10697/) (2023)
- [The Sample-Communication Complexity Trade-off in Federated Q-Learning](https://mlsanity.com/paper/2408.16981/) (2024)
- [Compressed Federated Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2404.10635/) (2024)
- [Sample and Communication Efficient Fully Decentralized MARL Policy Evaluation via a New Approach: Local TD update](https://mlsanity.com/paper/2403.15935/) (2024)
- [Gap-Dependent Bounds for Federated Q-learning](https://mlsanity.com/paper/2502.02859/) (2025)
- [On the Hardness of Decentralized Multi-Agent Policy Evaluation under Byzantine Attacks](https://mlsanity.com/paper/2409.12882/) (2024)
- [Multi-agent Natural Actor-critic Reinforcement Learning Algorithms](https://mlsanity.com/paper/2109.01654/) (2021)
- [Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learning](https://mlsanity.com/paper/2506.04626/) (2025)
- [A Law of Iterated Logarithm for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2110.15092/) (2021)
- [Finite-Time Error Bounds for Distributed Linear Stochastic Approximation](https://mlsanity.com/paper/2111.12665/) (2021)
- [Federated Reinforcement Learning at the Edge](https://mlsanity.com/paper/2112.05908/) (2021)
- [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)
- [Exact Formulas for Finite-Time Estimation Errors of Decentralized Temporal Difference Learning with Linear Function Approximation](https://mlsanity.com/paper/2204.09801/) (2022)
- [Distributed TD Tracking with Linear Function Approximation over Directed Communication Networks](https://mlsanity.com/paper/2605.04466/) (2026)

## Abstract (arXiv)

We study the policy evaluation problem in multi-agent reinforcement learning, modeled by a Markov decision process. In this problem, the agents operate in a common environment under a fixed control policy, working together to discover the value (global discounted accumulative reward) associated with each environmental state. Over a series of time steps, the agents act, get rewarded, update their local estimate of the value function, then communicate with their neighbors. The local update at each agent can be interpreted as a distributed variant of the popular temporal difference learning methods sf TD (λ). Our main contribution is to provide a finite-analysis on the performance of this distributed sf TD(λ) algorithm for both constant and time-varying step sizes. The key idea in our analysis is to use the geometric mixing time τ of the underlying Markov chain, that is, although the "noise" in our algorithm is Markovian, its dependence is very weak at samples spaced out at every τ. We provide an explicit upper bound on the convergence rate of the proposed method as a function of the network topology, the discount factor, the constant λ, and the mixing time τ. Our results also provide a mathematical explanation for observations that have appeared previously in the literature about the choice of λ. Our upper bound illustrates the trade-off between approximation accuracy and convergence speed implicit in the choice of λ. When λ=1, the solution will correspond to the best possible approximation of the value function, while choosing λ = 0 leads to faster convergence when the noise in the algorithm has large variance.