# Exact Formulas for Finite-Time Estimation Errors of Decentralized Temporal Difference Learning with Linear Function Approximation

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 39 references that are in the map.
- First posted on arXiv 20 Apr 2022.

## Builds on (most cited first, 19 of 19)

- [Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms](https://mlsanity.com/paper/1911.10635/) (2019)
- [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)
- [Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints](https://mlsanity.com/paper/1408.3595/) (2014)
- [Two Time-scale Off-Policy TD Learning: Non-asymptotic Analysis over Markovian Samples](https://mlsanity.com/paper/1909.11907/) (2019)
- [Dissipativity Theory for Nesterov's Accelerated Method](https://mlsanity.com/paper/1706.04381/) (2017)
- [Analysis of Optimization Algorithms via Integral Quadratic Constraints: Nonstrongly Convex Problems](https://mlsanity.com/paper/1705.03615/) (2017)
- [Characterizing the Exact Behaviors of Temporal Difference Learning Algorithms Using Markov Jump Linear System Theory](https://mlsanity.com/paper/1906.06781/) (2019)
- [Finite-Time Performance of Distributed Temporal Difference Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.12530/) (2019)
- [A Unified Switching System Perspective and O.D.E. Analysis of Q-Learning Algorithms](https://mlsanity.com/paper/1912.02270/) (2019)
- [Analysis of Biased Stochastic Gradient Descent Using Sequential Semidefinite Programs](https://mlsanity.com/paper/1711.00987/) (2017)
- [Distributed Reinforcement Learning via Gossip](https://mlsanity.com/paper/1310.7610/) (2013)
- [Analysis and Design of First-Order Distributed Optimization Algorithms over Time-Varying Graphs](https://mlsanity.com/paper/1907.05448/) (2019)
- [A frequency-domain analysis of inexact gradient methods](https://mlsanity.com/paper/1912.13494/) (2019)
- [A Unified Analysis of Stochastic Optimization Methods Using Jump System Theory and Quadratic Constraints](https://mlsanity.com/paper/1706.08141/) (2017)
- [Robustness of accelerated first-order algorithms for strongly convex optimization problems](https://mlsanity.com/paper/1905.11011/) (2019)
- [Dissipativity Theory for Accelerating Stochastic Variance Reduction: A Unified Analysis of SVRG and Katyusha Using Semidefinite Programs](https://mlsanity.com/paper/1806.03677/) (2018)
- [Convex Programs and Lyapunov Functions for Reinforcement Learning: A Unified Perspective on the Analysis of Value-Based Methods](https://mlsanity.com/paper/2202.06922/) (2022)
- [A Control-Theoretic Approach to Analysis and Parameter Selection of Douglas-Rachford Splitting](https://mlsanity.com/paper/1903.11525/) (2019)

## Abstract (arXiv)

In this paper, we consider the policy evaluation problem in multi-agent reinforcement learning (MARL) and derive exact closed-form formulas for the finite-time mean-squared estimation errors of decentralized temporal difference (TD) learning with linear function approximation. Our analysis hinges upon the fact that the decentralized TD learning method can be viewed as a Markov jump linear system (MJLS). Then standard MJLS theory can be applied to quantify the mean and covariance matrix of the estimation error of the decentralized TD method at every time step. Various implications of our exact formulas on the algorithm performance are also discussed. An interesting finding is that under a necessary and sufficient stability condition, the mean-squared TD estimation error will converge to an exact limit at a specific exponential rate.