Abstract
To ensure the usefulness of Reinforcement Learning (RL) in real systems, itis crucial to ensure they are robust to noise and adversarial attacks. Inadversarial RL, an external attacker has the power to manipulate the victimagent's interaction with the environment. We study the full class of onlinemanipulation 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 stealthyattack that maximizes its own expected reward, which often corresponds tominimizing 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 levelenvironment induced by the attacked interaction. We show that the attacker canderive optimal attacks by planning in polynomial time or learning withpolynomial sample complexity using standard RL techniques. We argue that theoptimal defense policy for the victim can be computed as the solution to astochastic Stackelberg game, which can be further simplified into apartially-observable turn-based stochastic game (POTBSG). Neither the attackernor the victim would benefit from deviating from their respective optimalpolicies, thus such solutions are truly robust. Although the defense problem isNP-hard, we show that optimal Markovian defenses can be computed (learned) inpolynomial time (sample complexity) in many scenarios.