Adversarial Attacks on Adversarial Bandits
This work addresses security vulnerabilities in bandit-based systems, such as online recommendation, where attackers could hijack systems to promote desired products, representing a novel but incremental contribution to adversarial robustness.
The paper tackles the problem of security threats in adversarial multi-armed bandits by showing that an attacker can mislead any no-regret algorithm into selecting a suboptimal target arm in all but sublinear rounds with only sublinear cumulative attack cost, implying critical risks in real-world systems like online recommendation.
We study a security threat to adversarial multi-armed bandits, in which an attacker perturbs the loss or reward signal to control the behavior of the victim bandit player. We show that the attacker is able to mislead any no-regret adversarial bandit algorithm into selecting a suboptimal target arm in every but sublinear (T-o(T)) number of rounds, while incurring only sublinear (o(T)) cumulative attack cost. This result implies critical security concern in real-world bandit-based systems, e.g., in online recommendation, an attacker might be able to hijack the recommender system and promote a desired product. Our proposed attack algorithms require knowledge of only the regret rate, thus are agnostic to the concrete bandit algorithm employed by the victim player. We also derived a theoretical lower bound on the cumulative attack cost that any victim-agnostic attack algorithm must incur. The lower bound matches the upper bound achieved by our attack, which shows that our attack is asymptotically optimal.