# A primal-dual perspective for distributed TD-learning

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 65 references that are in the map.
- First posted on arXiv 1 Oct 2023.

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

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [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)
- [EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization](https://mlsanity.com/paper/1404.6264/) (2014)
- [Distributed Stochastic Gradient Tracking Methods](https://mlsanity.com/paper/1805.11454/) (2018)
- [Distributed optimization over time-varying directed graphs](https://mlsanity.com/paper/1303.2289/) (2013)
- [Push-Pull Gradient Methods for Distributed Optimization in Networks](https://mlsanity.com/paper/1810.06653/) (2018)
- [Multi-Agent Reinforcement Learning via Double Averaging Primal-Dual Optimization](https://mlsanity.com/paper/1806.00877/) (2018)
- [Distributed Policy Evaluation Under Multiple Behavior Strategies](https://mlsanity.com/paper/1312.7606/) (2013)
- [Finite-Time Performance of Distributed Temporal Difference Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.12530/) (2019)
- [DSA: Decentralized Double Stochastic Averaging Gradient Algorithm](https://mlsanity.com/paper/1506.04216/) (2015)
- [Exact Diffusion for Distributed Optimization and Learning --- Part II: Convergence Analysis](https://mlsanity.com/paper/1702.05142/) (2017)
- [Multi-Agent Fully Decentralized Value Function Learning with Linear Convergence Rates](https://mlsanity.com/paper/1810.07792/) (2018)
- [On the Exponential Stability of Primal-Dual Gradient Dynamics](https://mlsanity.com/paper/1803.01825/) (2018)
- [Distributed convex optimization via continuous-time coordination algorithms with discrete-time communication](https://mlsanity.com/paper/1401.4432/) (2014)
- [A Multistep Lyapunov Approach for Finite-Time Analysis of Biased Stochastic Approximation](https://mlsanity.com/paper/1909.04299/) (2019)
- [Finite-Time Convergence Rates of Decentralized Stochastic Approximation with Applications in Multi-Agent and Multi-Task Learning](https://mlsanity.com/paper/2010.15088/) (2020)
- [Distributed Reinforcement Learning via Gossip](https://mlsanity.com/paper/1310.7610/) (2013)
- [Primal-Dual Algorithm for Distributed Reinforcement Learning: Distributed GTD](https://mlsanity.com/paper/1803.08031/) (2018)
- [New Versions of Gradient Temporal Difference Learning](https://mlsanity.com/paper/2109.04033/) (2021)
- [Passivity-Based Distributed Optimization with Communication Delays Using PI Consensus Algorithm](https://mlsanity.com/paper/1609.04666/) (2016)
- [Fast Multi-Agent Temporal-Difference Learning via Homotopy Stochastic Primal-Dual Optimization](https://mlsanity.com/paper/1908.02805/) (2019)
- [Dual Seminorms, Ergodic Coefficients and Semicontraction Theory](https://mlsanity.com/paper/2201.03103/) (2022)
- [Stability, Linear Convergence, and Robustness of the Wang-Elia Algorithm for Distributed Consensus Optimization](https://mlsanity.com/paper/2204.10030/) (2022)

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

- [A finite time analysis of distributed Q-learning](https://mlsanity.com/paper/2405.14078/) (2024)

## Abstract (arXiv)

The goal of this paper is to investigate distributed temporal difference (TD) learning for a networked multi-agent Markov decision process. The proposed approach is based on distributed optimization algorithms, which can be interpreted as primal-dual Ordinary differential equation (ODE) dynamics subject to null-space constraints. Based on the exponential convergence behavior of the primal-dual ODE dynamics subject to null-space constraints, we examine the behavior of the final iterate in various distributed TD-learning scenarios, considering both constant and diminishing step-sizes and incorporating both i.i.d. and Markovian observation models. Unlike existing methods, the proposed algorithm does not require the assumption that the underlying communication network structure is characterized by a doubly stochastic matrix.