Fully Byzantine-Resilient Distributed Multi-Agent Q-Learning
This addresses a critical security issue in multi-agent systems for applications like autonomous vehicles or robotics, offering a fully resilient solution with proven optimal convergence.
The paper tackles the problem of Byzantine-resilient distributed multi-agent reinforcement learning, where agents must learn optimal policies despite compromised communication networks, and shows that their proposed algorithm ensures almost sure convergence to optimal value functions, unlike prior methods that fail under such attacks.
We study Byzantine-resilient distributed multi-agent reinforcement learning (MARL), where agents must 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 optimal solution. As a result, 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 prior methods fail under Byzantine edge attacks.