Saving Stochastic Bandits from Poisoning Attacks via Limited Data Verification. (arXiv:2102.07711v2 [cs.LG] UPDATED)

We study bandit algorithms under data poisoning attacks in a bounded reward
setting. We consider a strong attacker model in which the attacker can observe
both the selected actions and their corresponding rewards and can contaminate
the rewards with additive noise. We show that any bandit algorithm with regret
$O(\log T)$ can be forced to suffer a regret $\Omega(T)$ with an expected
amount of contamination $O(\log T)$. This amount of contamination is also
necessary, as we prove that there exists …

attacks data lg poisoning