Delayed Adversarial Attacks on Stochastic Multi-Armed Bandits

Abstract

We study adversarial attacks on stochastic bandits when, differently from previous works, the attack of the malicious attacker is delayed and starts after the learning process begins. In particular, we focus on strong attacks and capture the setting where the malicious attacker does not have information about the beginning of the learning process. Interestingly, the lack of such information can dramatically affect the effectiveness of the attack. We analyze this scenario in the case of the UCB algorithm facing an omniscient attacker, providing a more general framework to study adversarial attacks on stochastic bandit algorithms. We characterize the success and profitability of the attack depending on the round in which the attack starts. In particular, we derive an upper and a lower bound on the number of target arm pulls, showing that our bound is tight up to a sublinear factor. Moreover, we provide a condition that identifies when an attack can be successful. Finally, we empirically evaluate the tightness of our theoretical bounds on synthetic instances.