  As reinforcement learning (RL) has achieved great success and been even
adopted in safety-critical domains such as autonomous vehicles, a range of
empirical studies have been conducted to improve its robustness against
adversarial attacks. However, how to certify its robustness with theoretical
guarantees still remains challenging. In this paper, we present the first
unified framework CROP (Certifying Robust Policies for RL) to provide
robustness certification on both action and reward levels. In particular, we
propose two robustness certification criteria: robustness of per-state actions
and lower bound of cumulative rewards. We then develop a local smoothing
algorithm for policies derived from Q-functions to guarantee the robustness of
actions taken along the trajectory; we also develop a global smoothing
algorithm for certifying the lower bound of a finite-horizon cumulative reward,
as well as a novel local smoothing algorithm to perform adaptive search in
order to obtain tighter reward certification. Empirically, we apply CROP to
evaluate several existing empirically robust RL algorithms, including
adversarial training and different robust regularization, in four environments
(two representative Atari games, Highway, and CartPole). Furthermore, by
evaluating these algorithms against adversarial attacks, we demonstrate that
our certification are often tight. All experiment results are available at
website https://crop-leaderboard.github.io.
