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

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

## 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 (most cited first, 30 of 38)

- [AutoGen: Enabling Next-Gen LLM Applications via Multi-Agent Conversation](https://mlsanity.com/paper/2308.08155/) (2023)
- [CAMEL: Communicative Agents for "Mind" Exploration of Large Language Model Society](https://mlsanity.com/paper/2303.17760/) (2023)
- [The Statistical Complexity of Interactive Decision Making](https://mlsanity.com/paper/2112.13487/) (2021)
- [Adversarial Policies: Attacking Deep Reinforcement Learning](https://mlsanity.com/paper/1905.10615/) (2019)
- [Action Robust Reinforcement Learning and Applications in Continuous Control](https://mlsanity.com/paper/1901.09184/) (2019)
- [Learning from History for Byzantine Robust Optimization](https://mlsanity.com/paper/2012.10333/) (2020)
- [Online Robust Reinforcement Learning with Model Uncertainty](https://mlsanity.com/paper/2109.14523/) (2021)
- [Sample Complexity of Robust Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2112.01506/) (2021)
- [Corruption-robust exploration in episodic reinforcement learning](https://mlsanity.com/paper/1911.08689/) (2019)
- [The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2305.16589/) (2023)
- [Corruption-Robust Offline Reinforcement Learning](https://mlsanity.com/paper/2106.06630/) (2021)
- [On the Robustness of Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2003.03722/) (2020)
- [Corruption-Robust Offline Reinforcement Learning with General Function Approximation](https://mlsanity.com/paper/2310.14550/) (2023)
- [Byzantine-Robust Federated Learning with Optimal Statistical Rates and Privacy Guarantees](https://mlsanity.com/paper/2205.11765/) (2022)
- [Sample-Efficient Reinforcement Learning of Partially Observable Markov Games](https://mlsanity.com/paper/2206.01315/) (2022)
- [Cooperative Multi-Agent Deep Reinforcement Learning for Reliable Surveillance via Autonomous Multi-UAV Control](https://mlsanity.com/paper/2201.05843/) (2022)
- [Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithms](https://mlsanity.com/paper/2404.03578/) (2024)
- [Robust Multi-Agent Reinforcement Learning via Adversarial Regularization: Theoretical Foundation and Stable Algorithms](https://mlsanity.com/paper/2310.10810/) (2023)
- [Regret Minimization and Convergence to Equilibria in General-sum Markov Games](https://mlsanity.com/paper/2207.14211/) (2022)
- [Byzantine Robust Cooperative Multi-Agent Reinforcement Learning as a Bayesian Game](https://mlsanity.com/paper/2305.12872/) (2023)
- [Multi-Agent Reinforcement Learning for Connected and Automated Vehicles Control: Recent Advancements and Future Prospects](https://mlsanity.com/paper/2312.11084/) (2023)
- [Learning Markov Games with Adversarial Opponents: Efficient Algorithms and Fundamental Limits](https://mlsanity.com/paper/2203.06803/) (2022)
- [Attacking Cooperative Multi-Agent Reinforcement Learning by Adversarial Minority Influence](https://mlsanity.com/paper/2302.03322/) (2023)
- [A Finite-Sample Analysis of Payoff-Based Independent Learning in Zero-Sum Stochastic Games](https://mlsanity.com/paper/2303.03100/) (2023)
- [Robust multi-agent coordination via evolutionary generation of auxiliary adversarial attackers](https://mlsanity.com/paper/2305.05909/) (2023)
- [Byzantine-Robust Online and Offline Distributed Reinforcement Learning](https://mlsanity.com/paper/2206.00165/) (2022)
- [Fictitious Play in Markov Games with Single Controller](https://mlsanity.com/paper/2205.11389/) (2022)
- [Provably Robust Federated Reinforcement Learning](https://mlsanity.com/paper/2502.08123/) (2025)
- [Sample Complexity of Distributionally Robust Off-Dynamics Reinforcement Learning with Online Interaction](https://mlsanity.com/paper/2511.05396/) (2025)
- [Wolfpack Adversarial Attack for Robust Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2502.02844/) (2025)

## 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.