# On the Hardness of Decentralized Multi-Agent Policy Evaluation under Byzantine Attacks

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 47 references that are in the map.
- First posted on arXiv 19 Sep 2024.

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

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments](https://mlsanity.com/paper/1706.02275/) (2017)
- [Counterfactual Multi-Agent Policy Gradients](https://mlsanity.com/paper/1705.08926/) (2017)
- [Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates](https://mlsanity.com/paper/1803.01498/) (2018)
- [Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms](https://mlsanity.com/paper/1911.10635/) (2019)
- [Local Model Poisoning Attacks to Byzantine-Robust Federated Learning](https://mlsanity.com/paper/1911.11815/) (2019)
- [FLTrust: Byzantine-robust Federated Learning via Trust Bootstrapping](https://mlsanity.com/paper/2012.13995/) (2020)
- [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 from History for Byzantine Robust Optimization](https://mlsanity.com/paper/2012.10333/) (2020)
- [Byzantine-Robust Learning on Heterogeneous Datasets via Bucketing](https://mlsanity.com/paper/2006.09365/) (2020)
- [On the Convergence Rates of Policy Gradient Methods](https://mlsanity.com/paper/2201.07443/) (2022)
- [V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RL](https://mlsanity.com/paper/2110.14555/) (2021)
- [Generalized Byzantine-tolerant SGD](https://mlsanity.com/paper/1802.10116/) (2018)
- [Fault-Tolerant Federated Reinforcement Learning with Theoretical Guarantee](https://mlsanity.com/paper/2110.14074/) (2021)
- [Byzantine-Robust Decentralized Federated Learning](https://mlsanity.com/paper/2406.10416/) (2024)
- [AFLGuard: Byzantine-robust Asynchronous Federated Learning](https://mlsanity.com/paper/2212.06325/) (2022)
- [Sample and Communication-Efficient Decentralized Actor-Critic Algorithms with Finite-Time Analysis](https://mlsanity.com/paper/2109.03699/) (2021)
- [Reward Poisoning Attacks on Offline Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2206.01888/) (2022)
- [Finite-Time Performance of Distributed Temporal Difference Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.12530/) (2019)
- [Byzantine-Robust Online and Offline Distributed Reinforcement Learning](https://mlsanity.com/paper/2206.00165/) (2022)
- [Byzantine Multi-Agent Optimization: Part I](https://mlsanity.com/paper/1506.04681/) (2015)
- [Sample and Communication Efficient Fully Decentralized MARL Policy Evaluation via a New Approach: Local TD update](https://mlsanity.com/paper/2403.15935/) (2024)
- [Scalable and Sample Efficient Distributed Policy Gradient Algorithms in Multi-Agent Networked Systems](https://mlsanity.com/paper/2212.06357/) (2022)
- [Fault-Tolerant Multi-Agent Optimization: Part III](https://mlsanity.com/paper/1509.01864/) (2015)

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

- [Provably Robust Federated Reinforcement Learning](https://mlsanity.com/paper/2502.08123/) (2025)
- [BARD-MARL: Byzantine-Agent Detection for Learned Communication in Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2606.20701/) (2026)
- [Fully Byzantine-Resilient Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2609.25701/) (2026)

## Abstract (arXiv)

In this paper, we study a fully-decentralized multi-agent policy evaluation problem, which is an important sub-problem in cooperative multi-agent reinforcement learning, in the presence of up to f faulty agents. In particular, we focus on the so-called Byzantine faulty model with model poisoning setting. In general, policy evaluation is to evaluate the value function of any given policy. In cooperative multi-agent system, the system-wide rewards are usually modeled as the uniform average of rewards from all agents. We investigate the multi-agent policy evaluation problem in the presence of Byzantine agents, particularly in the setting of heterogeneous local rewards. Ideally, the goal of the agents is to evaluate the accumulated system-wide rewards, which are uniform average of rewards of the normal agents for a given policy. It means that all agents agree upon common values (the consensus part) and furthermore, the consensus values are the value functions (the convergence part). However, we prove that this goal is not achievable. Instead, we consider a relaxed version of the problem, where the goal of the agents is to evaluate accumulated system-wide reward, which is an appropriately weighted average reward of the normal agents. We further prove that there is no correct algorithm that can guarantee that the total number of positive weights exceeds |N|-f , where |N| is the number of normal agents. Towards the end, we propose a Byzantine-tolerant decentralized temporal difference algorithm that can guarantee asymptotic consensus under scalar function approximation. We then empirically test the effective of the proposed algorithm.