Technical Summary: Practical Adversarial Attacks on Stochastic Bandits via Fake Data Injection

1. Problem Statement

Multi-armed bandit (MAB) algorithms are foundational to online decision-making systems, balancing exploration and exploitation in applications like personalized recommendation, online advertising, and clinical trials. While prior research has established that MAB algorithms are vulnerable to adversarial attacks, existing threat models rely on unrealistic assumptions that limit their relevance to real-world systems.

Specifically, prior works (e.g., Jun et al., 2018; Liu and Shroff, 2019; Zuo, 2024) predominantly adopt a feedback-perturbation model. In this model, the attacker observes the learner's chosen arm and its reward in every round, then arbitrarily modifies the reward before it is revealed to the learner. This model grants the attacker full control over the feedback channel at every timestep and assumes unbounded perturbation capabilities.

In practice, such capabilities are often infeasible. For instance, in a restaurant recommendation platform, an adversary cannot continuously overwrite genuine user ratings from thousands of real customers. Instead, realistic attacks involve creating fake accounts to inject fabricated reviews or synthetic interactions (e.g., click fraud). These attacks add fake data rather than altering existing data, are subject to system-level detection or resource limits, and must conform to valid feedback ranges (e.g., 1–5 star ratings).

This paper addresses the gap between theoretical attack models and practical constraints by proposing a new threat model: Fake Data Injection. The core challenge is to design attack strategies that can mislead a learner into selecting a specific suboptimal (target) arm in nearly all rounds while incurring only sublinear cost, under the constraints of:

1. No modification of genuine feedback: The attacker cannot overwrite real user data.
2. Bounded rewards: Injected fake rewards must lie within the valid feedback range $[r_l, r_u]$.
3. Temporal constraints: The attacker may be limited in the number of fake samples they can inject per round (batch size) or the frequency of injection.

2. Methodology and Core Concepts

2.1 The Fake Data Injection Threat Model

The authors formalize a setting where the attacker injects $N_F$ fake data samples $\{(a^F_s, r^F_s)\}$ into the learner's history. The learner treats these injected samples indistinguishably from legitimate interactions, updating empirical means, pull counts, and internal round counters accordingly.

• Attack Cost: Defined as $C_F(T) = \sum |r^F_s - \mu_{a^F_s}|$.
• Success Criterion: An attack is successful if it induces the learner to select the target arm in $T - o(T)$ rounds while ensuring $C_F(T) = o(T)$.

2.2 The Suppression Principle

The central technical insight is the Suppression Principle. Instead of continuously perturbing rewards, the attacker aims to inject enough bounded fake feedback to suppress the empirical estimate of a non-target arm below a stable lower benchmark of the target arm. Once a non-target arm is sufficiently suppressed, the learner's own exploration mechanism prevents it from being selected again for a significant duration.

The Exponential Suppression Lemma (for UCB)

For the Upper Confidence Bound (UCB) algorithm, the authors prove that if a non-target arm $i$ is pulled sufficiently ($N_i(t) \geq \log T/\delta_0^2$) and its empirical mean is driven below a specific lower bound $\hat{\ell}_K(t)$ of the target arm $K$, then arm $i$ will not be selected again until at least round $\exp(N_i(t)\delta_0^2)$ with high probability. This "exponential suppression" allows the attacker to achieve long-term manipulation with a single injection event per arm.

2.3 Attack Strategies

A. Simultaneous Injection (SI)

Designed for a setting where the attacker can inject data as needed without strict per-round limits.

• Mechanism: For each non-target arm $i$, the attacker waits until it has been pulled $\lceil \log T/\delta_0^2 \rceil$ times. The attacker then injects a batch of fake samples with the minimum valid reward $r_l$ to reduce the arm's empirical mean below the target arm's lower confidence bound.
• Result: This forces the UCB algorithm to select the target arm for $T - o(T)$ rounds with a cumulative cost of $\tilde{O}(K\sigma\sqrt{\log T})$, matching known lower bounds.

B. Periodic Bounded Injection (PBI)

Designed for realistic constraints where the attacker faces a batch size limit ($f$ samples per round) and must avoid triggering anomaly detection.

• Mechanism: Instead of a single large injection, the attacker distributes the required fake samples over time. Once a non-target arm reaches the pull threshold, the attacker calculates the total number of samples needed and a "cooldown" period $R_i$. The attacker injects batches of size $f$ periodically, separated by $R_i$ rounds, ensuring the arm remains suppressed between injections.
• Result: PBI achieves successful attacks with sublinear cost even under strict temporal and magnitude constraints, balancing stealthiness with efficacy.

C. General Suppression-Bounded Framework

The authors extend these findings beyond UCB to a class of algorithms termed Suppression-Bounded. An algorithm is suppression-bounded if, once a suboptimal arm is empirically dominated by the target arm, the algorithm pulls that arm only a bounded number of additional times.

• This framework applies to Thompson Sampling and $\epsilon$-greedy algorithms.
• The attack strategy involves injecting the minimum number of fake samples to satisfy a condition where the non-target arm's empirical mean stays below the target's benchmark, leveraging the algorithm's inherent bound on post-suppression pulls.

3. Key Contributions

1. New Threat Model: Introduction of Fake Data Injection, which reflects realistic constraints (bounded rewards, limited injection frequency, inability to overwrite genuine data) overlooked by prior feedback-perturbation models.
2. Suppression Principle: Formalization of a mechanism where bounded fake injections can permanently suppress non-target arms, turning the attack into a problem of establishing and maintaining suppression rather than continuous perturbation.
3. Algorithmic Strategies:
   • Simultaneous Injection (SI): An optimal strategy for UCB under minimal constraints.
   • Periodic Bounded Injection (PBI): A robust strategy for UCB under batch-size and temporal constraints.
   • General Framework: Extension of the suppression analysis to Thompson Sampling and $\epsilon$-greedy.
4. Theoretical Guarantees: Proof that these attacks can mislead learners into selecting a target arm in $T - o(T)$ rounds with sublinear attack cost ($o(T)$), even with bounded reward values.
5. Empirical Validation: Experiments on synthetic data and the MovieLens 25M dataset demonstrating that sparse, bounded fake data can significantly bias bandit learners in practice.

4. Experimental Results

The authors evaluated their strategies on:

• Synthetic Data: Gaussian reward distributions with $K=10$ arms.
• Real-World Data: MovieLens 25M dataset, simulating a recommendation system with 10 arms (movies) and user interactions.

Key Findings:

• Effectiveness: Both SI and PBI successfully forced UCB and Thompson Sampling learners to select the target arm in over 95% of rounds after an initial suppression phase.
• Cost Efficiency: PBI achieved performance comparable to SI but with lower attack costs in long-horizon scenarios by spreading injections over time.
• Comparison with Baselines: A heuristic baseline that injected samples randomly (proportional to remaining time) failed to converge the learner to the target arm, highlighting the critical importance of the injection schedule and the suppression principle.
• Robustness to Constraints: PBI demonstrated that even with strict limits on batch size ($f=5$ or $f=10$), the attack remains effective, whereas unbounded strategies (like Least Injection) incur the lowest theoretical cost but may be less practical in detection-heavy environments.

5. Significance and Limitations

Significance:
The paper bridges the gap between theoretical adversarial robustness and practical security in online learning. It demonstrates that the assumption of "unbounded, per-round reward manipulation" significantly overestimates the difficulty of attacking real-world systems. By showing that sparse, bounded, and temporally distributed fake data can subvert standard bandit algorithms, the work reveals a critical vulnerability in sequential decision-making systems used in high-stakes domains. The proposed Suppression Lemma provides a general tool for analyzing vulnerabilities in algorithms that rely on empirical means and exploration bonuses.

Limitations (as stated by the authors):

• Passive Learner: The analysis assumes a passive learner that processes all feedback without defense mechanisms (e.g., filtering or auditing).
• Stochastic Setting: The framework is currently limited to stochastic bandits; extending it to contextual bandits or reinforcement learning remains an open problem.
• Detection Risks: The current model does not explicitly capture the dynamic interaction between attackers and adaptive learners that employ anomaly detection or arm-level auditing.

The authors conclude that while their results expose a gap between classical robustness guarantees and practical security, future work must investigate defenses such as anomaly detection and the dynamic interplay between attackers and adaptive, defensive learners.