# Fast Multi-Agent Temporal-Difference Learning via Homotopy Stochastic Primal-Dual Optimization

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Aug 2019.

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

- [New Versions of Gradient Temporal Difference Learning](https://mlsanity.com/paper/2109.04033/) (2021)
- [A primal-dual perspective for distributed TD-learning](https://mlsanity.com/paper/2310.00638/) (2023)
- [Continuous-Time Distributed Dynamic Programming for Networked Multi-Agent Markov Decision Processes](https://mlsanity.com/paper/2307.16706/) (2023)

## Abstract (arXiv)

We study the policy evaluation problem in multi-agent reinforcement learning where a group of agents, with jointly observed states and private local actions and rewards, collaborate to learn the value function of a given policy via local computation and communication over a connected undirected network. This problem arises in various large-scale multi-agent systems, including power grids, intelligent transportation systems, wireless sensor networks, and multi-agent robotics. When the dimension of state-action space is large, the temporal-difference learning with linear function approximation is widely used. In this paper, we develop a new distributed temporal-difference learning algorithm and quantify its finite-time performance. Our algorithm combines a distributed stochastic primal-dual method with a homotopy-based approach to adaptively adjust the learning rate in order to minimize the mean-square projected Bellman error by taking fresh online samples from a causal on-policy trajectory. We explicitly take into account the Markovian nature of sampling and improve the best-known finite-time error bound from O(1/√T) to~O(1/T), where T is the total number of iterations.