Optimal Cost Constrained Adversarial Attacks for Multiple Agent Systems

Since many security-related applications use multi-agent reinforcement learning as their underlying algorithms, the study on the adversarial attacks against mutli-agent reinforcement learning systems receives a lot of attention. Finding optimal adversarial attack strategies is an important topic in adversarial attacks on reinforcement learning and the Markov decision process. Previous studies usually assume one all-knowing coordinator (attacker) for whom attacking different recipient (victim) agents incurs uniform costs. However, in important real-world applications, instead of coming from one limitless central attacker, the attacks often need to be performed by distributed attack agents. We formulate the new problem of performing optimal adversarial agent-to-agent attacks using distributed attack agents, in which we impose distinct cost constraints on each different attacker-victim pair. We propose a novel method integrating within-time-step static attack-resource allocation optimization and between-time-step dynamic programming to achieve the optimal adversarial attack in a multi-agent system. Our numerical results show that the proposed attacks can significantly reduce the rewards received by the attacked agents.