Efficient Adversarial Attacks on High-dimensional Offline Bandits

AI summary

Overview

Research area: Adversarial machine learning and multi-armed bandit theory, specifically attacks on offline bandit evaluation of generative models.

Technical level: Advanced. The paper combines convex optimization, random matrix theory, high-dimensional concentration inequalities, and Neural Tangent Kernel (NTK) approximations, and assumes familiarity with UCB-style bandit algorithms.

Scope: A theoretical and empirical study of a new threat model in which an attacker perturbs the weights of an offline reward model—not the data—before bandit training, thereby hijacking which arm the bandit selects.

What This Paper Is About

Offline bandit algorithms are increasingly used to evaluate machine learning models, including generative image models and large language models, by reusing a fixed logged dataset instead of running costly online trials. These systems rely on a reward model whose weights are often publicly released on platforms such as Hugging Face. The paper asks whether an adversary who can only perturb those public reward weights—while having access to the logged data but not the ability to modify samples or interfere with training—can reliably steer the bandit away from the truly optimal arm, and whether such attacks get easier as input dimensionality grows.

Key Contributions

1. A new threat model for offline bandits. The adversary exploits logged offline data and perturbs the reward model before training, rather than poisoning rewards or samples during the bandit interaction. The paper states that no prior research has considered attacks on the reward model before training.

2. Theoretical foundations. The authors show the attack reduces to a targeted optimization problem, prove a feasibility guarantee (Theorem 3.3) when the dimension exceeds the number of constraints, and prove that the required perturbation norm shrinks with dimension (Theorem 3.4).

3. Computationally efficient attack heuristics. The Full Trajectory, Trajectory-Free, and Online Score-Aware (OSA) attacks reduce the constraint count from O(TK) to O(T) and, in practice, to as small as O(log T), while preserving near-100% success.

4. Real-world validation and a partial defense. Attacks are demonstrated on two Hugging Face image reward models used for generative model assessment (aesthetic quality and compositional alignment), plus a data-shuffling defense that partially mitigates the attack.

Main Findings

• All attack variants reached 100% attack success rate (ASR) on UCB in the synthetic setting. The OSA method substantially reduced the time needed to generate perturbations.

• Naive random perturbations fail. With no perturbation, ASR was approximately 25%, and increasing the ℓ2 norm of random noise perturbation left ASR nearly constant across a wide range of magnitudes.

• Higher dimensionality makes attacks cheaper. Both the ℓ2 and ℓ∞ norms of the perturbation decreased rapidly as input dimensionality increased (experimental settings: T = 100, K = 3, ASR = 100%). In the low-dimensional regime the OSA solution showed a small gap relative to the Optimal solution, and this gap diminished as dimensionality grew.

• Feasibility guarantee. If the data-generating distributions are non-singular (minimum eigenvalue of the covariance matrix greater than zero) and d > (T−K)(K−1), then with probability 1 all optimization problems for the full-trajectory, trajectory-free, and OSA attacks are feasible (Theorem 3.3).

• Perturbation norm shrinks as Õ(d⁻¹/²). For product measures with identity covariance and d ≥ KT, the ℓ2 norm of the full-trajectory attack is bounded by O(sqrt(T³ log T · log d / (Kd))) with probability at least 1 − 2d⁻¹ (Theorem 3.4).

• Real-world attacks on Hugging Face reward models. Using five generative models—Stable Diffusion 3 (SD3), Stable Diffusion 1.4, Kandinsky 3, Openjourney, and Stable Diffusion XL—with 30 random prompts from GenAI-Bench and seeds ranging from 1 to 100, if a random prompt is selected and the attack performed, there is approximately an 80% probability that ASR falls between 90–100%.

• Attacks generalize beyond UCB. The method achieved 100% ASR on ETC and ε-greedy as well.

• Non-linear reward width matters. For a single-hidden-layer reward model, ASR reached 100% once the number of neurons exceeded 750 (with T = 100), consistent with the NTK prediction that linear approximation becomes more accurate as width grows.

• Robust bandits are also vulnerable. Against Fast–Slow with a corruption parameter of 0.5, the attack succeeded 100% of the time with perturbation norm around 0.3 (K ∈ {3,5}, T = 1000, d = 1000). Against the ε-contamination algorithm with ε = 0.15, ASR was 100% with ℓ2 norm approximately 0.2 (T ∈ {100, 1000}, K ∈ {3,5}, d = 1000, α = 0.1, σ = 1, α-trimmed strategy).

• A partial defense works. Randomly shuffling a portion of the logged data before running the bandit significantly reduced attack effectiveness; shuffling only T/2 of the logged data was sufficient to substantially mitigate the attack.

Methodology in Plain English

The bandit setting consists of K arms, each with its own distribution over d-dimensional inputs, and a reward function r(·) applied to samples drawn from the chosen arm. The adversary can perturb the reward parameters: adding δ to w in the linear case, or adding δ to θ in the neural network case, where θ has D parameters given by d·W₁ + W₁·W₂ + ⋯ + W_{L−1}·W_L + W_L.

The attacker's goal is formulated as minimizing the squared ℓ2 norm of δ subject to constraints ensuring the UCB score of a chosen arm exceeds that of competitors. Three attack designs are considered:

• Full Trajectory Attack: forces the bandit onto a fully predetermined target trajectory, requiring (T−K)(K−1) constraints.
• Trajectory-Free Attack: only prevents the optimal arm from being pulled at specified time steps, requiring T−K constraints (a factor of K−1 reduction).
• Online Score-Aware (OSA) Attack: iterates over time steps, adding a constraint only when the optimal arm actually has the highest UCB score, taking the runner-up arm as the target. This replaces one large quadratic program (QP) with a series of small ones.

For a linear reward model, all three designs reduce to a convex QP with d variables and |I| constraints, solvable in roughly Õ(|I|³ + d|I|²) operations. For neural networks, the UCB score is non-linear in δ, but NTK theory says that for sufficiently wide networks with random initialization the network behaves approximately linearly in its parameters, NN_{θ+δ}(X) = NN_θ(X) + ∇_θ NN_θ(X)ᵀδ + O(W_max⁻¹), reducing the attack to a QP with D variables (Corollary 3.2).

The theoretical results use linear-algebraic arguments, anti-concentration properties of non-degenerate distributions, high-dimensional concentration inequalities, and random matrix theory. Empirically, the authors test on synthetic data varying K and d, then on real image generation data using Image Reward (compositional alignment) and the Aesthetic Model (LAION-AI) as reward models, keeping most weights frozen except for a small subset used in the attack.

Why This Matters

Impact on research. The paper reframes bandit evaluation security: the vulnerability lies not in the data but in publicly shared reward model weights. It introduces a threat model that is arguably more realistic than reward-poisoning attacks, because the adversary does not need to be present during training, and it shows that the attack strength increases with dimensionality—the opposite of many intuitive robustness expectations.

Real-world applications:

• Generative model leaderboards and benchmarks that rank diffusion models by aesthetics or prompt alignment using reward models.
• LLM evaluation pipelines that use bandit algorithms to identify top-performing candidates without exhaustive pairwise comparisons.
• Offline A/B testing and recommendation systems where logged data and open reward models drive selection decisions.
• Hyperparameter and metric tuning on reused logged datasets, where a manipulated reward model could silently bias which configuration is chosen.

Industry relevance. Because reward models are routinely distributed with public weights (e.g., CLIP, BLIP, VQA models, Image Reward, LAION aesthetic predictor), any organization that reuses logged data and an open reward model to rank or select models inherits this attack surface. The paper's data-shuffling defense offers a cheap partial mitigation, but the authors state that a complete defense remains open.

Future Directions

• Develop a complete defense. The shuffling defense only partially mitigates the attack under certain conditions; the authors explicitly state that a complete defense remains open.

• Extend the theory to broader distribution classes. The paper conjectures that a more general ℓ2-norm result could be established for near-product measures, which cover a broader class of distributions, but leaves this beyond the present scope.

• Analyze OSA theoretically. A full theoretical analysis of the Online Score-Aware attack is stated to be beyond the scope of the paper; the authors only empirically observe its O(log T)-like constraint count.

• Close the loop on the proposed "on–off heuristic." The conclusion mentions an efficient on–off heuristic for scenarios where the attacker only aims to prevent optimal arm selection; a fuller treatment and evaluation of this heuristic is a natural follow-up.

Target Audience

Researchers and practitioners in adversarial machine learning, bandit theory, and generative model evaluation. It will be most valuable to those designing or auditing evaluation pipelines that use offline logged data with public reward model weights, and to theoreticians interested in high-dimensional robustness guarantees. A reader needs comfort with convex optimization, UCB-style algorithms, and NTK-based linearization arguments to follow the theoretical sections.

Authors’ abstract

Bandit algorithms have recently emerged as a powerful tool for evaluating machine learning models, including generative image models and large language models, by efficiently identifying top-performing candidates without exhaustive comparisons. These methods typically rely on a reward model, often distributed with public weights on platforms such as Hugging Face, to provide feedback to the bandit. While online evaluation is expensive and requires repeated trials, offline evaluation with logged data has become an attractive alternative. However, the adversarial robustness of offline bandit evaluation remains largely unexplored, particularly when an attacker perturbs the reward model (rather than the training data) prior to bandit training. In this work, we fill this gap by investigating, both theoretically and empirically, the vulnerability of offline bandit training to adversarial manipulations of the reward model. We introduce a novel threat model in which an attacker exploits offline data in high-dimensional settings to hijack the bandit's behavior. Starting with linear reward functions and extending to nonlinear models such as ReLU neural networks, we study attacks on two Hugging Face evaluators used for generative model assessment: one measuring aesthetic quality and the other assessing compositional alignment. Our results show that even small, imperceptible perturbations to the reward model's weights can drastically alter the bandit's behavior. From a theoretical perspective, we prove a striking high-dimensional effect: as input dimensionality increases, the perturbation norm required for a successful attack decreases, making modern applications such as image evaluation especially vulnerable. Extensive experiments confirm that naive random perturbations are ineffective, whereas carefully targeted perturbations achieve near-perfect attack success rates ...