Optimal Attack and Defense for Reinforcement Learning
Jeremy McMahan Young Wu Xiaojin Zhu Qiaomin Xie
To ensure the usefulness of Reinforcement Learning (RL) in real systems, it
is crucial to ensure they are robust to noise and adversarial attacks. In
adversarial RL, an external attacker has the power to manipulate the victim
agent's interaction with the environment. We study the full class of online
manipulation attacks, which include (i) state attacks, (ii) observation attacks
(which are a generalization of perceived-state attacks), (iii) action attacks,
and (iv) reward attacks. We show the attacker's problem of designing a stealthy
attack that maximizes its own expected reward, which often corresponds to
minimizing the victim's value, is captured by a Markov Decision Process (MDP)
that we call a meta-MDP since it is not the true environment but a higher level
environment induced by the attacked interaction. We show that the attacker can
derive optimal attacks by planning in polynomial time or learning with
polynomial sample complexity using standard RL techniques. We argue that the
optimal defense policy for the victim can be computed as the solution to a
stochastic Stackelberg game, which can be further simplified into a
partially-observable turn-based stochastic game (POTBSG). Neither the attacker
nor the victim would benefit from deviating from their respective optimal
policies, thus such solutions are truly robust. Although the defense problem is
NP-hard, we show that optimal Markovian defenses can be computed (learned) in
polynomial time (sample complexity) in many scenarios.