mlsanityData to 7 Oct 2026

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

arXiv 2409.12882 ↗First posted 19 Sep 2024cs.CR cs.DC cs.LGcited by 3

Not on the map. Why?

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.

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

Builds on

27 of 47 references.

References · 27

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,592
  2. 2017Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environmentscited by 1,519
  3. 2017Counterfactual Multi-Agent Policy Gradientscited by 733
  4. 2018Byzantine-Robust Distributed Learning: Towards Optimal Statistical Ratescited by 698
  5. 2019Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithmscited by 555
  6. 2019Local Model Poisoning Attacks to Byzantine-Robust Federated Learningcited by 479
  7. 2020FLTrust: Byzantine-robust Federated Learning via Trust Bootstrappingcited by 330
  8. 2016Safe, Multi-Agent, Reinforcement Learning for Autonomous Drivingcited by 301
  9. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 225
  10. 2018Fully Decentralized Multi-Agent Reinforcement Learning with Networked Agentscited by 189
  11. 2019Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learningcited by 165
  12. 2020Learning from History for Byzantine Robust Optimizationcited by 137
15 more
  1. 2020Byzantine-Robust Learning on Heterogeneous Datasets via Bucketingcited by 125
  2. 2022On the Convergence Rates of Policy Gradient Methodscited by 115
  3. 2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 111
  4. 2018Generalized Byzantine-tolerant SGDcited by 94
  5. 2021Fault-Tolerant Federated Reinforcement Learning with Theoretical Guaranteecited by 52
  6. 2024Byzantine-Robust Decentralized Federated Learningcited by 47
  7. 2022AFLGuard: Byzantine-robust Asynchronous Federated Learningcited by 29
  8. 2021Sample and Communication-Efficient Decentralized Actor-Critic Algorithms with Finite-Time Analysiscited by 25
  9. 2022Reward Poisoning Attacks on Offline Multi-Agent Reinforcement Learningcited by 19
  10. 2019Finite-Time Performance of Distributed Temporal Difference Learning with Linear Function Approximationcited by 14
  11. 2022Byzantine-Robust Online and Offline Distributed Reinforcement Learningcited by 13
  12. 2015Byzantine Multi-Agent Optimization: Part Icited by 4
  13. 2024Sample and Communication Efficient Fully Decentralized MARL Policy Evaluation via a New Approach: Local TD updatecited by 3
  14. 2022Scalable and Sample Efficient Distributed Policy Gradient Algorithms in Multi-Agent Networked Systemscited by 2
  15. 2015Fault-Tolerant Multi-Agent Optimization: Part IIIcited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 1; 2026: 2.

3 papers.

  1. 2025Provably Robust Federated Reinforcement Learningcited by 8
  2. 2026BARD-MARL: Byzantine-Agent Detection for Learned Communication in Multi-Agent Reinforcement Learningcited by 0
  3. 2026Fully Byzantine-Resilient Multi-Agent Reinforcement Learningcited by 0