Provably Efficient Black-Box Action Poisoning Attacks Against
  Reinforcement Learning
  Due to the broad range of applications of reinforcement learning (RL),
understanding the effects of adversarial attacks against RL model is essential
for the safe applications of this model. Prior theoretical works on adversarial
attacks against RL mainly focus on either observation poisoning attacks or
environment poisoning attacks. In this paper, we introduce a new class of
attacks named action poisoning attacks, where an adversary can change the
action signal selected by the agent. Compared with existing attack models, the
attacker's ability in the proposed action poisoning attack model is more
restricted, which brings some design challenges. We study the action poisoning
attack in both white-box and black-box settings. We introduce an adaptive
attack scheme called LCB-H, which works for most RL agents in the black-box
setting. We prove that the LCB-H attack can force any efficient RL agent, whose
dynamic regret scales sublinearly with the total number of steps taken, to
choose actions according to a policy selected by the attacker very frequently,
with only sublinear cost. In addition, we apply LCB-H attack against a popular
model-free RL algorithm: UCB-H. We show that, even in the black-box setting, by
spending only logarithm cost, the proposed LCB-H attack scheme can force the
UCB-H agent to choose actions according to the policy selected by the attacker
very frequently.
