  The study of provable adversarial robustness for deep neural networks (DNNs)
has mainly focused on static supervised learning tasks such as image
classification. However, DNNs have been used extensively in real-world adaptive
tasks such as reinforcement learning (RL), making such systems vulnerable to
adversarial attacks as well. Prior works in provable robustness in RL seek to
certify the behaviour of the victim policy at every time-step against a
non-adaptive adversary using methods developed for the static setting. But in
the real world, an RL adversary can infer the defense strategy used by the
victim agent by observing the states, actions, etc., from previous time-steps
and adapt itself to produce stronger attacks in future steps. We present an
efficient procedure, designed specifically to defend against an adaptive RL
adversary, that can directly certify the total reward without requiring the
policy to be robust at each time-step. Our main theoretical contribution is to
prove an adaptive version of the Neyman-Pearson Lemma -- a key lemma for
smoothing-based certificates -- where the adversarial perturbation at a
particular time can be a stochastic function of current and previous
observations and states as well as previous actions. Building on this result,
we propose policy smoothing where the agent adds a Gaussian noise to its
observation at each time-step before passing it through the policy function.
Our robustness certificates guarantee that the final total reward obtained by
policy smoothing remains above a certain threshold, even though the actions at
intermediate time-steps may change under the attack. Our experiments on various
environments like Cartpole, Pong, Freeway and Mountain Car show that our method
can yield meaningful robustness guarantees in practice.
