Attack methods boost target choices in bandit learning with low cost

Beyond Reward Suppression: Near-Optimal Offline Attacks on Warm-Start Bandits with Bounded Rewards

Machine LearningArtificial Intelligence

Summary

Bandit learning algorithms decide what choices to make based on rewards they receive, but sometimes attackers try to trick them to pick certain options more often. The paper studies attacks done before the algorithm starts, by adding fake past data to guide the learning. The researchers found that attacking by promoting the target choice, not just hurting others, is important and efficient in some cases. They created attacks that balance promoting the target and suppressing others, working for several common learning strategies. Their tests on real and fake data show these attacks can effectively mislead bandit algorithms at a small cost.

What this means in practice

Authors

Qirun Zeng, Manhin Poon, Xiangxiang Dai, Qixin Zhang, Jinhang Zuo

Abstract

Adversarial attacks on bandits aim to mislead a learner toward a target arm while keeping the attack cost small. Existing attacks typically achieve this by suppressing non-target arms. In practice, however, manipulation such as fake reviews often directly promotes the target item. We study this gap through bounded offline attacks on warm-start bandits, where an attacker can inject only valid action-reward pairs into the warm-start history before deployment. We show that target promotion is not merely a heuristic: when the target arm lies near the lower reward boundary, any order-optimal-cost attack against UCB that makes it selected in nearly all online rounds must allocate a nonvanishing fraction of its cost to the target arm. We then design an attack that achieves the optimal sublinear cost and characterize its allocation between target promotion and non-target suppression. We further extend the attack to Thompson Sampling, $ε$-greedy, and a broader class of bandit algorithms. Experiments on real-world and synthetic data validate the effectiveness of our attacks.