Abstract
In reward-poisoning attacks against reinforcement learning (RL), an attackercan perturb the environment reward $r_t$ into $r_t+\delta_t$ at each step, withthe goal of forcing the RL agent to learn a nefarious policy. We categorizesuch attacks by the infinity-norm constraint on $\delta_t$: We provide a lowerthreshold below which reward-poisoning attack is infeasible and RL is certifiedto be safe; we provide a corresponding upper threshold above which the attackis feasible. Feasible attacks can be further categorized as non-adaptive where$\delta_t$ depends only on $(s_t,a_t, s_{t+1})$, or adaptive where $\delta_t$depends further on the RL agent's learning process at time $t$. Non-adaptiveattacks have been the focus of prior works. However, we show that under mildconditions, adaptive attacks can achieve the nefarious policy in stepspolynomial in state-space size $|S|$, whereas non-adaptive attacks requireexponential steps. We provide a constructive proof that a Fast Adaptive Attackstrategy achieves the polynomial rate. Finally, we show that empirically anattacker can find effective reward-poisoning attacks using state-of-the-artdeep RL techniques.