Organizations: City University of Hong Kong, Hong Kong SAR, China · The Chinese University of Hong Kong, Hong Kong SAR, China · Nanyang Technological University, Singapore
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.
Figures & tables
Attack Strategy
Timing
Bounded Rewards
Target Promotion
Allocation Analysis
Opt.
Jun et al. (2018)
online
✗
✗
✗
✗
Liu and Shroff (2019)
offline
✗
✓
✗
✓
Xu et al. (2021)
online
✓
✓
✗
✗
Zuo (2024)
online
✗
✗
✗
✓
Zeng et al. (2025)
online
✓
✗
✗
✗
Hosseini et al. (2026)
offline
✗
✗
✗
✗
Table 1: Comparison of bandit attack models and guarantees.
Figure 1: Attack Cost for UCB.
Figure 2: Target-arm Selection Ratio for UCB.
Figure 3: Near-Boundary Cost and Allocation for UCB.
Figure 4: Comparison with Xu et al. (2021) for UCB.
Appendix figures & tables5 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 5: Attack Cost for TS.
Figure 6: Target-arm Selection Ratio for TS.
Figure 7: Near-Boundary Cost and Allocation for TS.
Figure 8: Attack Cost for ϵ -greedy.
Figure 9: Target-arm Selection Ratio for ϵ -greedy.
We study bandit best-arm identification with arbitrary and potentially adversarial rewards. A simple random uniform learner obtains the optimal rate of error in the adversarial scenario. However, this type of strategy is suboptimal when the rewards are sampled stochastically. Therefore, we ask: Can we design a learner that performs optimally in both the stochastic and adversarial problems while not being aware of the nature of the rewards? First, we show that designing such a learner is impossible in general. In particular, to be robust to adversarial rewards, we can only guarantee optimal rates of error on a subset of the stochastic problems. We give a lower bound that characterizes the optimal rate in stochastic problems if the strategy is constrained to be robust to adversarial rewards. Finally, we design a simple parameter-free algorithm and show that its probability of error matches (up to log factors) the lower bound in stochastic problems, and it is also robust to adversarial ones.
Yasin Abbasi-Yadkori, Peter L. Bartlett, Victor Gabillon +2
Adobe Research, USA · University of California, Berkeley, USA · Queensland University of Technology - ACEMS, Australia +2
In multi-armed bandits, the most-explored arms are the most informative, while reward maximization typically pulls only the best arm. We study the tradeoff between identifying arm means accurately and accumulating reward, and present an algorithm with regret guarantees that interpolates between the two objectives. We provide both upper and lower bounds and validate empirically.
Akram Erraqabi, Alessandro Lazaric, Michal Valko +2
We study budget-constrained contextual bandits with adversarial contexts, where each action yields a random reward and incurs a random cost. We adopt the standard realizability assumption: conditioned on the observed context, rewards and costs are drawn independently from fixed distributions whose expectations belong to known function classes. We focus on the continuing setting, in which the algorithm operates over the entire horizon even after the budget for cumulative cost is exhausted. In this setting, the objective is to simultaneously control regret and the violation of the budget constraint. Building on the seminal SquareCB framework of Foster et al. [2018], we propose a simple and modular framework that leverages online regression oracles to reduce the constrained problem to a standard unconstrained contextual bandit problem with adaptively defined surrogate reward functions. In contrast to prior works, which focus on stochastic contexts, our reduction yields improved guarantees for more general adversarial contexts, together with an efficient algorithm with a compact and transparent analysis.
Dhruv Sarkar, Abhishek Sinha
Indian Institute of Technology Kharagpur, India · Tata Institute of Fundamental Research, Mumbai, India