  As reinforcement learning (RL) has achieved near human-level performance in a
variety of tasks, its robustness has raised great attention. While a vast body
of research has explored test-time (evasion) attacks in RL and corresponding
defenses, its robustness against training-time (poisoning) attacks remains
largely unanswered. In this work, we focus on certifying the robustness of
offline RL in the presence of poisoning attacks, where a subset of training
trajectories could be arbitrarily manipulated. We propose the first
certification framework, COPA, to certify the number of poisoning trajectories
that can be tolerated regarding different certification criteria. Given the
complex structure of RL, we propose two certification criteria: per-state
action stability and cumulative reward bound. To further improve the
certification, we propose new partition and aggregation protocols to train
robust policies. We further prove that some of the proposed certification
methods are theoretically tight and some are NP-Complete problems. We leverage
COPA to certify three RL environments trained with different algorithms and
conclude: (1) The proposed robust aggregation protocols such as temporal
aggregation can significantly improve the certifications; (2) Our certification
for both per-state action stability and cumulative reward bound are efficient
and tight; (3) The certification for different training algorithms and
environments are different, implying their intrinsic robustness properties. All
experimental results are available at https://copa-leaderboard.github.io.
