Data Poisoning to Fake a Nash Equilibrium in Markov Games
This work addresses security vulnerabilities in offline MARL, which is necessary for developing more robust algorithms, though it is incremental as it builds on existing concepts like reward polytopes.
The authors characterized offline data poisoning attacks in Multi-Agent Reinforcement Learning (MARL) for two-player zero-sum Markov games, proposing the unique Nash set to determine when attacks succeed and developing an efficient linear program to compute optimal attacks.
We characterize offline data poisoning attacks on Multi-Agent Reinforcement Learning (MARL), where an attacker may change a data set in an attempt to install a (potentially fictitious) unique Markov-perfect Nash equilibrium for a two-player zero-sum Markov game. We propose the unique Nash set, namely the set of games, specified by their Q functions, with a specific joint policy being the unique Nash equilibrium. The unique Nash set is central to poisoning attacks because the attack is successful if and only if data poisoning pushes all plausible games inside the set. The unique Nash set generalizes the reward polytope commonly used in inverse reinforcement learning to MARL. For zero-sum Markov games, both the inverse Nash set and the set of plausible games induced by data are polytopes in the Q function space. We exhibit a linear program to efficiently compute the optimal poisoning attack. Our work sheds light on the structure of data poisoning attacks on offline MARL, a necessary step before one can design more robust MARL algorithms.