On Faking a Nash Equilibrium
Young Wu Jeremy McMahan Xiaojin Zhu Qiaomin Xie
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. 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 it.
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.