We study Byzantine-resilient distributed multi-agent reinforcement learning (MARL), where agents collaboratively learn optimal value functions over a compromised communication network. Existing resilient MARL approaches typically guarantee almost sure convergence only to near-optimal value functions, or require restrictive assumptions to ensure convergence to the optimal solution. Thus, agents may fail to learn the optimal policies under these methods. To address this, we propose a novel distributed Q-learning algorithm, under which all agents' value functions converge almost surely to the optimal value functions despite Byzantine edge attacks. The key idea is a redundancy-based filtering mechanism that leverages two-hop neighbor information to validate incoming messages, while preserving bidirectional information flow. We then introduce a new topological condition for the convergence of our algorithm, present a systematic method to construct such networks, and prove that this condition can be verified in polynomial time. We validate our results through simulations, showing that our method converges to the optimal solutions, whereas other methods fail under Byzantine edge attacks.
Figures & tables
Fig. 1: Visualizations of (a) graph G(t)=(V,E(t)) and (b) its 5 -2-hop graph G5(2)(t)=(V,E5(2)(t)) at time t . The edge (i,j)∈E5(2)(t) , since ∣Bi(t)∩Nj(t)∣≥5 .
Fig. 2: (a) (1,0) -redundant graph and (b) its 1-2-hop graph.
Fig. 3: Performance comparison of our algorithm against the optimal Q-values from the Oracle [ 6 ] (no attack) and the Baseline [ 22 , 24 ] under a 1 -total Byzantine edge attack.
x=1
x=2
x=3
x=4
x=5
x=6
Oracle
(1,2)
(2,3)
(4,7)
(1,4)
(1,5)
(3,4)
Baseline
(2,9)
(2,3)
(4,7)
(1,6)
(2,9)
(1,9)
Ours
(1,2)
(2,3)
(4,7)
(1,4)
(1,5)
(3,4)
TABLE I: Learned policies from each algorithm across states.
We study distributed Byzantine-resilient actor-critic multi-agent reinforcement learning (AC-MARL), where agents collectively learn policies through local interactions. Existing methods guarantee convergence of the agents' parameters only to a neighborhood of the attack-free limit points, resulting in degraded performance. We propose Fully Resilient AC-MARL (FRAC-MARL), a decentralized method in which each agent leverages redundancy in two-hop messages to identify reliable messages. Under linear parameterizations of the value and team-reward functions and Byzantine edge attacks, where adversarial behavior is confined to the communication layer, we prove that agents' parameters converge almost surely to the same limit points as in the attack-free case over time-varying communication graphs. We introduce a novel topological condition for the convergence of our method, present a systematic method to construct such networks, and prove that this condition can be verified in polynomial time. Finally, we demonstrate our method on cooperative multi-robot formation control tasks.
Haejoon Lee, Dimitra Panagou
Robotics Department, University of Michigan, Ann Arbor, MI, USA
Learned communication improves coordination in cooperative multi-agent reinforcement learning, but it also creates a trust problem: a trained policy may route information through agents that have become faulty or adversarial. This paper studies Byzantine-agent detection for learned-communication MARL in adaptive traffic signal control. We propose BARD-MARL, a post-hoc diagnostic layer on top of BayesG, which is used as an attributed communication substrate rather than as a contribution of this paper. BARD-MARL combines two agent-level evidence streams: policy-graph features extracted from state-action trajectories and Bayesian trust statistics computed from BayesG latent mask probabilities. Across fixed-action, observation-flip, random-noise, and coordinated attacks in SUMO traffic grids, the results show that these signals are complementary rather than universally dominant. On a 25-agent grid, BARD-MARL reaches 0.843 AUC-ROC under a 10% observation-flip attack, while policy-graph-only detection reaches 0.917 AUC-ROC under a 10% coordinated attack. On a 100-agent grid, the unified BARD-MARL variant reaches 0.982 AUC-ROC for both 10% fixed-action and 10% coordinated attacks. The study shows that learned communication policies expose useful diagnostic evidence, but credible resilience claims require attack-specific ablations and explicit separation between coordination, detection, and mitigation.
Almond Kiruthu Murimi
Carnegie Mellon University Department of Electrical and Computer Engineering Pittsburgh, Pennsylvania, United States
We investigate a decentralized reinforcement learning problem involving multiple agents that interact with the same Markov Decision Process (MDP). The agents can exchange information over a network to collectively learn the optimal state-action value function. For this setting, we introduce a novel epoch-based distributed Q-learning algorithm called VRDQ, where within each epoch, agents locally estimate the Bellman optimality operator and diffuse information using a consensus-based protocol. For both static and time-varying networks, we establish high-probability finite-time convergence rates for VRDQ that enjoy linear speedups from collaboration. Crucially, we prove that such speedups in sample-complexity require only O~(1) communication, substantially improving upon the communication costs in prior work.
Sreejeet Maity, Feng Zhu, Aritra Mitra +1
Department of Electrical and Computer Engineering, North Carolina State University · Department of Electrical and Computer Engineering, University of California San Diego, San Diego, USA