# Sample and Communication Efficient Fully Decentralized MARL Policy Evaluation via a New Approach: Local TD update

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 35 references that are in the map.
- First posted on arXiv 23 Mar 2024.

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

- [Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments](https://mlsanity.com/paper/1706.02275/) (2017)
- [Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms](https://mlsanity.com/paper/1911.10635/) (2019)
- [Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent](https://mlsanity.com/paper/1705.09056/) (2017)
- [Safe, Multi-Agent, Reinforcement Learning for Autonomous Driving](https://mlsanity.com/paper/1610.03295/) (2016)
- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [Fully Decentralized Multi-Agent Reinforcement Learning with Networked Agents](https://mlsanity.com/paper/1802.08757/) (2018)
- [Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/1902.00923/) (2019)
- [Learning to Schedule Communication in Multi-agent Reinforcement Learning](https://mlsanity.com/paper/1902.01554/) (2019)
- [Scalable Multi-Agent Reinforcement Learning for Networked Systems with Average Reward](https://mlsanity.com/paper/2006.06626/) (2020)
- [Multi-Agent Reinforcement Learning via Double Averaging Primal-Dual Optimization](https://mlsanity.com/paper/1806.00877/) (2018)
- [Sample and Communication-Efficient Decentralized Actor-Critic Algorithms with Finite-Time Analysis](https://mlsanity.com/paper/2109.03699/) (2021)
- [Distributed Policy Evaluation Under Multiple Behavior Strategies](https://mlsanity.com/paper/1312.7606/) (2013)
- [A Communication-Efficient Multi-Agent Actor-Critic Algorithm for Distributed Reinforcement Learning](https://mlsanity.com/paper/1907.03053/) (2019)
- [Finite-Time Performance of Distributed Temporal Difference Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.12530/) (2019)
- [Communication-Efficient Policy Gradient Methods for Distributed Reinforcement Learning](https://mlsanity.com/paper/1812.03239/) (2018)
- [Primal-Dual Algorithm for Distributed Reinforcement Learning: Distributed GTD](https://mlsanity.com/paper/1803.08031/) (2018)

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

- [On the Hardness of Decentralized Multi-Agent Policy Evaluation under Byzantine Attacks](https://mlsanity.com/paper/2409.12882/) (2024)
- [Consensus-based Decentralized Multi-agent Reinforcement Learning for Random Access Network Optimization](https://mlsanity.com/paper/2508.07001/) (2025)
- [Finite-Time Global Optimality Convergence in Deep Neural Actor-Critic Methods for Decentralized Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2505.18433/) (2025)
- [Joint Trajectory, RIS, and Computation Offloading Optimization via Decentralized Model-Based PPO in Urban Multi-UAV Mobile Edge Computing](https://mlsanity.com/paper/2603.20238/) (2026)

## Abstract (arXiv)

In actor-critic framework for fully decentralized multi-agent reinforcement learning (MARL), one of the key components is the MARL policy evaluation (PE) problem, where a set of N agents work cooperatively to evaluate the value function of the global states for a given policy through communicating with their neighbors. In MARL-PE, a critical challenge is how to lower the sample and communication complexities, which are defined as the number of training samples and communication rounds needed to converge to some ε-stationary point. To lower communication complexity in MARL-PE, a "natural'' idea is to perform multiple local TD-update steps between each consecutive rounds of communication to reduce the communication frequency. However, the validity of the local TD-update approach remains unclear due to the potential "agent-drift'' phenomenon resulting from heterogeneous rewards across agents in general. This leads to an interesting open question: Can the local TD-update approach entail low sample and communication complexities? In this paper, we make the first attempt to answer this fundamental question. We focus on the setting of MARL-PE with average reward, which is motivated by many multi-agent network optimization problems. Our theoretical and experimental results confirm that allowing multiple local TD-update steps is indeed an effective approach in lowering the sample and communication complexities of MARL-PE compared to consensus-based MARL-PE algorithms. Specifically, the local TD-update steps between two consecutive communication rounds can be as large as O(1/ε1/2log(1/ε)) in order to converge to an ε-stationary point of MARL-PE. Moreover, we show theoretically that in order to reach the optimal sample complexity, the communication complexity of local TD-update approach is O(1/ε1/2log(1/ε)).