mlsanityData to 14 Oct 2026

Online Security Learning in Cooperative Multi-Agent Systems under Hidden Byzantine Attacks

arXiv 2608.06520 ↗First posted 6 Aug 2026cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

We study online cooperative control of a multi-agent system under Byzantine attacks. Namely, an unknown, fixed subset of agents are Byzantine comprised and can stealthily overwrite its own coordinates of the team's planned joint action after observing that plan. The learner observes planned actions, public rewards, and public states, but neither the overwrite nor the executed joint action. Our objective is security: to optimize the team performance against the worst overwrites and achieve the optimal security value. We first show that the attacker's information determines the geometry. An attacker that observes the planned action induces an exact (s,a)-rectangular robust Markov decision process (MDP) whose rows are convex hulls of overwrite-induced public-outcome laws, whereas a blind attacker induces an s-rectangular model. We then identify the information-theoretic limit of security learning, showing that the security regret decomposes exactly into return regret against the response generating the data and a cumulative response gap DK. Two indistinguishable horizon-one instances force Omega(K) expected security regret while return regret is zero, showing that dependence on DK is unavoidable. Finally, we develop a stage-tied robust estimation-to-decisions learner and prove a regret bound of widetildemathcal O!left(H2S√AKright)+mathbb E[DK]. Our studies thus provide comprehensive theoretical and algorithmic foundations of reliable multi-agent systems under Byzantine attacks.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 38 of its 55 references that are in the map. First posted on arXiv 6 Aug 2026.

Builds on

38 of 55 references.

References · 38

  1. 2023AutoGen: Enabling Next-Gen LLM Applications via Multi-Agent Conversationcited by 1,988
  2. 2023CAMEL: Communicative Agents for "Mind" Exploration of Large Language Model Societycited by 1,395
  3. 2021The Statistical Complexity of Interactive Decision Makingcited by 218
  4. 2019Adversarial Policies: Attacking Deep Reinforcement Learningcited by 214
  5. 2019Action Robust Reinforcement Learning and Applications in Continuous Controlcited by 174
  6. 2020Learning from History for Byzantine Robust Optimizationcited by 137
  7. 2021Online Robust Reinforcement Learning with Model Uncertaintycited by 96
  8. 2021Sample Complexity of Robust Reinforcement Learning with a Generative Modelcited by 83
  9. 2019Corruption-robust exploration in episodic reinforcement learningcited by 72
  10. 2023The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Modelcited by 52
  11. 2021Corruption-Robust Offline Reinforcement Learningcited by 51
  12. 2020On the Robustness of Cooperative Multi-Agent Reinforcement Learningcited by 39
26 more
  1. 2023Corruption-Robust Offline Reinforcement Learning with General Function Approximationcited by 31
  2. 2022Byzantine-Robust Federated Learning with Optimal Statistical Rates and Privacy Guaranteescited by 30
  3. 2022Sample-Efficient Reinforcement Learning of Partially Observable Markov Gamescited by 27
  4. 2022Cooperative Multi-Agent Deep Reinforcement Learning for Reliable Surveillance via Autonomous Multi-UAV Controlcited by 26
  5. 2024Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithmscited by 26
  6. 2023Robust Multi-Agent Reinforcement Learning via Adversarial Regularization: Theoretical Foundation and Stable Algorithmscited by 25
  7. 2022Regret Minimization and Convergence to Equilibria in General-sum Markov Gamescited by 24
  8. 2023Byzantine Robust Cooperative Multi-Agent Reinforcement Learning as a Bayesian Gamecited by 18
  9. 2023Multi-Agent Reinforcement Learning for Connected and Automated Vehicles Control: Recent Advancements and Future Prospectscited by 18
  10. 2022Learning Markov Games with Adversarial Opponents: Efficient Algorithms and Fundamental Limitscited by 17
  11. 2023Attacking Cooperative Multi-Agent Reinforcement Learning by Adversarial Minority Influencecited by 17
  12. 2023A Finite-Sample Analysis of Payoff-Based Independent Learning in Zero-Sum Stochastic Gamescited by 15
  13. 2023Robust multi-agent coordination via evolutionary generation of auxiliary adversarial attackerscited by 15
  14. 2022Byzantine-Robust Online and Offline Distributed Reinforcement Learningcited by 13
  15. 2022Fictitious Play in Markov Games with Single Controllercited by 10
  16. 2025Provably Robust Federated Reinforcement Learningcited by 8
  17. 2025Sample Complexity of Distributionally Robust Off-Dynamics Reinforcement Learning with Online Interactioncited by 7
  18. 2025Wolfpack Adversarial Attack for Robust Multi-Agent Reinforcement Learningcited by 6
  19. 2024Roping in Uncertainty: Robustness and Regularization in Markov Gamescited by 5
  20. 2025Regret Bounds for Robust Online Decision Makingcited by 5
  21. 2026Adversarial Learning in Games with Bandit Feedback: Logarithmic Pure-Strategy Maximin Regretcited by 4
  22. 2024Learning in Markov Games with Adaptive Adversaries: Policy Regret, Fundamental Barriers, and Efficient Algorithmscited by 3
  23. 2022Coordinated Multi-Agent Reinforcement Learning for Unmanned Aerial Vehicle Swarms in Autonomous Mobile Access Applicationscited by 2
  24. 2023Learning in Zero-Sum Markov Games: Relaxing Strong Reachability and Mixing Time Assumptionscited by 2
  25. 2025Empirical Study on Robustness and Resilience in Cooperative Multi-Agent Reinforcement Learningcited by 1
  26. 2026Online Learning for Uninformed Markov Games: Empirical Nash-Value Regret and Non-Stationarity Adaptationcited by 1

Built on by

Not cited yet.