Online Security Learning in Cooperative Multi-Agent Systems under Hidden Byzantine Attacks
Ximing Sun, Yue Wang
cs.LG
Submitted: 2026-08-06
Updated: 2026-08-10
Comments: preprint; Work in progress
License: http://creativecommons.org/licenses/by/4.0/
The gist: We study online cooperative control of a multi-agent system under Byzantine attacks.
Terminology
Abstract
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 D K. Two indistinguishable horizon-one instances force (K) expected security regret while return regret is zero, showing that dependence on D K is unavoidable. Finally, we develop a stage-tied robust estimation-to-decisions learner and prove a regret bound of ! (H 2S sqrt AK)+ E[D K]. Our studies thus provide comprehensive theoretical and algorithmic foundations of reliable multi-agent systems under Byzantine attacks.
Sources
- Coordinated Multi-Agent Reinforcement Learning for Unmanned Aerial Vehicle Swarms in Autonomous Mobile Access Applications
- AutoGen: Enabling Next-Gen LLM Applications via Multi-Agent Conversation
- Adversarial Policies: Attacking Deep Reinforcement Learning
- The Statistical Complexity of Interactive Decision Making
- Regret Bounds for Robust Online Decision Making
- Wolfpack Adversarial Attack for Robust Multi-Agent Reinforcement Learning
- The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Model
- Corruption-Robust Offline Reinforcement Learning
- Online Learning for Uninformed Markov Games: Empirical Nash-Value Regret and Non-Stationarity Adaptation
- Adversarial Learning in Games with Bandit Feedback: Logarithmic Pure-Strategy Maximin Regret
Related papers
- Polynomial-Augmented Neural Networks (PANNs) with Weak Orthogonality Constraints for Enhanced Function and PDE Approximation
- AIRL-S: Unifying Reinforcement Learning and Search-Based Test-Time Scaling via Adversarial Inverse Reinforcement Learning
- Transformers as Bayesian In-Context Experimenters: Smoothness-Adaptive Efficient ATE Estimation
- Convergence issues in Relational Concept Analysis based on AOC-posets
- Beliefs Beyond Posteriors: The Predictive Cost of ELBO Binding
- Understanding Diffusion Models via Ratio-Based Function Approximation with SignReLU Networks