Efficient Adversarial Attacks on High-Dimensional Offline Bandits

离线评测中，只改奖励模型、不改日志，能否让 bandit 选错最优臂。

• 场景：作者称 bandit 已用于推荐、临床试验、动态定价，以及扩散模型、GAN 与 LLM 评测。在线评测贵，实践改用固定日志比较 UCB、ETC、ε-greedy 或调超参。作者认为同一日志既可能被对抗操纵，也可能因反复调奖励指标而过拟合。
• 现有不足：作者称既有训练期攻击通常改奖励值或样本（附录 A），尚未研究训练前只改奖励模型。作者称高维下即使弱攻击者也可成功。
• 观察：作者称维度升高后，成功攻击所需扰动范数下降，图像评测因此更暴露。直观上，每臂观测远少于 d 时高维均值估计不稳，线性或过参数网络有足够自由度误导选臂。
• 提出：作者称提出新的威胁模型，对线性奖励和 ReLU 网络给出全轨迹、无轨迹与 OSA 攻击，并在两个 Hugging Face 图像评测器上检验；另给出打乱部分日志的防御。
• 威胁模型：
  • 目标：高概率使 bandit 找不到并利用最优臂 i∗；更强时强制预定轨迹。‖δ‖2 尽量小，例如最优臂被拉次数低于 T′<T。
  • 知识：可读离线日志 D1 到 DK；奖励函数在训练前已知并可被改。
  • 能力：不能改样本，不能干预训练，也不能进入运行 bandit 的环境（Section 4.8、附录 I）。线性将 w 改为 w+δ，网络将 θ 改为 θ+δ。
  • 受害系统：K 臂、输入维 d、时域 T 的随机 MAB，样本来自 Pi，奖励为 r(X)。正文以 UCB 为主，并延伸到 ETC 与 ε-greedy。

Appendix A and the introduction divide related work into supervised attacks, bandit evaluation, and bandit poisoning; the authors explicitly state the difference from this paper only for reward poisoning.

Adversarial attacks on supervised models

• Classic adversarial examples: Szegedy et al. (2014), Moosavi-Dezfooli et al. (2017), Cicalese et al. (2020), Cohen et al. (2019), Dasgupta et al. (2019). The authors state that adversarial attacks on supervised models have been widely studied, while bandit vulnerability has received less discussion.
• Reward models for evaluation: Singh & Zheng (2023), Cho et al. (2024), Hu et al. (2023), Hosseini et al. (2025). The authors list them as reward models that can be combined with bandit evaluators, without comparing each paper here.

Using bandits for model evaluation

• Generative models and LLMs: Rezaei et al. (2025), Hu et al. (2024a; 2024b; 2025) use bandits for online selection and evaluation. The introduction also cites public-weight evaluators such as CLIP, BLIP, and VQA.
• Tuning on the same log: The authors cite Rezaei et al. (2025), Hu et al. (2024b), Saito & Nomura (2024), noting that in practice metrics are repeatedly measured or hyperparameters tuned on the same log.

Poisoning bandits

• Reward poisoning: Jun et al. (2018), Liu & Shroff (2019), Liu & Lai (2020), as well as Niss & Tewari (2020), Lykouris et al. (2018), Gupta et al. (2019), Hajiesmaili et al. (2020). Modifying the rewards the agent receives during interaction biases learning toward a specific arm.
• Linear contextual bandits: Ma et al. (2018), Garcelon et al. (2020) modify the rewards of chosen actions; Garcelon et al. (2020) can also modify only the context. The authors state these works show sensitivity to reward and context manipulation.
• Difference from this paper: The authors state that this paper does not directly attack rewards, but attacks the reward model itself, corresponding to the use of bandits as an evaluation metric.

Baselines and data

• Baselines: random noise (Section 4.6); robust algorithms Fast–Slow (Lykouris et al., 2018) and ε-contamination (Niss & Tewari, 2020). Section 4.2 also compares OSA with the Optimal solution from quadratic programming.
• Data: synthetic logs; 30 random prompts from GenAI-Bench, seeds 1 to 100. Reward models are Image Reward and Aesthetic Model.

The authors position this paper as offline, pre-training, modifying only the reward model, and emphasize that high dimensionality makes the required perturbation smaller.

作者把劫持选臂写成对扰动 δ 的约束优化。线性奖励与足够宽的网络都收成凸二次规划；作者称随机扰动不够，必须解有目标的优化。

问题设定

• 环境：K 臂随机 MAB。臂 i 的分布 Pi 在 R^d 上，拉臂得到 X，奖励为 r(X)，时域为 T。日志 Di 有 ni 个独立样本，且 T 轮内每次拉臂都看到新样本。
• 两类奖励：线性为 w 与 X 的内积；网络为前馈 NN_θ，激活 σ，参数维 D。作者关注 d 很大，或最大隐层宽很大。最优臂 i∗ 的期望奖励严格最大。
• UCB：前 K 步每臂拉一次。之后选 UCB 分数最大的臂：经验平均奖励加上探索项，探索项为 2 log t 除以该臂次数后开方（式 1）。分数记为 Λt(i;δ)。

三类攻击

• 全轨迹：对所有 t>K 和所有非目标臂，要求预定臂 Ãt 的 UCB 分数严格更大。约束数为 (T−K)(K−1)。线性时约束对 δ 是线性的。
• 无轨迹：只要求在指定时间集合上不拉 i∗，不规定拉哪条臂。实验里辅助序列用 round-robin。若覆盖 K+1 到 T，约束数为 T−K；作者称约束数按 K−1 倍减少。
• OSA：按时间扫描。若当前 δ 还没让 i∗ 的 UCB 最高就跳过；否则加入“亚军臂分数高于 i∗”并重解。作者称每步约束通常很少，因而不是一次解很大的规划。附录 K 给出三类伪代码。

二次规划与宽网络

• 线性：Theorem 3.1 把三类攻击写成最小化 ‖δ‖2 的平方，约束为 δ 与 T_{i,t} 的内积大于 R_{i,t}。T_{i,t} 与 R_{i,t} 只由日志和原权重决定，指标集 I 由攻击类型决定。核心形式是 δ^∗=argmin|δ|₂²，且 δ^⊤T_i,t>R_i,t。
• 规模：全轨迹 |I|=O(TK)，无轨迹 |I|=O(T)。作者称实验里 OSA 的 |I| 可小到 O(log T)（Figure 7）。求解代价约为 |I| 的三次加上 d 乘 |I| 的二次，并带对数因子。
• 宽网络：作者引用 NTK，称随机初始化且足够宽时，输出对参数近似仿射，余项随最大宽度衰减，从而得到变量数为 D 的同类二次规划（Corollary 3.2）。真实大模型上，作者冻结大部分权重，只动一小部分；论文未写该子集的规模。

可行性与范数界

• 可行：若各 Pi 的协方差最小特征值大于 0，且 d>(T−K)(K−1)，则三类问题以概率 1 可行（Theorem 3.3）。摘要把全轨迹可行写成 d≥KT 并归于 Theorem 3.3；正文里 d≥KT 出现在 Theorem 3.4 的前提中。
• 范数：在乘积测度、协方差为单位阵，以及各臂均值与 w 的范数为 1、最优臂与 w 对齐、其余臂与 w 正交的记号下，若 d≥KT，全轨迹攻击的 ‖δ∗‖2 不超过 O(√(T^3 log T·log d/(Kd)))，概率至少 1−2d^{−1}（Theorem 3.4）。作者称这些范数假设只为简化记号，不改变算法。作者还称更一般的 near-product 测度留待以后。

Experimental Setup

• Algorithms: main experiment uses UCB. Also tested ETC (exploration rounds m=5), ε-greedy (initial ε=0.1, decays over time, floor 0.01), Fast–Slow (corruption parameter 0.5), and ε-contamination (ε=0.15, α=0.1, σ=1, α-trimmed).
• Reward models: synthetic linear model; single hidden layer ReLU, Adam, MSE, 80/20 split, 100 epochs, batch 1024, learning rate 10^{−3}, supervision is inner product of sample and optimal arm mean (Appendix E). Real models are Image Reward and Aesthetic Model, most weights frozen. Appendix F additionally uses random initialization, network with only one hidden layer trainable.
• Data and arms: synthetic experiments vary K and d or maximum hidden layer width. Real experiments have five arms: Stable Diffusion 3, Stable Diffusion 1.4, Kandinsky 3, Openjourney, Stable Diffusion XL; GenAI-Bench samples 30 prompts, seeds 1 to 100 produce logs.
• Metrics and criteria: ASR, perturbation ℓ2 and ℓ∞, attack time. Paper doesn't give formal definition of ASR, nor report repetitions, confidence intervals, or LLM evaluation. Success reported by whether bandit trajectory is hijacked.

Main Results

Swipe horizontally to read the table

Setting	Attack	ASR	Perturbation ℓ2	Source
Synthetic, UCB, linear and nonlinear	OSA, Trajectory-Free, Full Trajectory	100%	not reported	Figure 1
T=100, ε-greedy and ETC	this paper's attack	100%	not reported	Table 1
Fast–Slow, corruption=0.5, K∈{3,5}, T=1000, d=1000	change weights before training	100%	≈ 0.3	Figure 5, main text
ε-contamination, main text ε=0.15	change weights before training	100%	approximately 0.2	main text; Figure 6 also gives grid
Image Reward and Aesthetic, OSA	real logs	probability of falling in 90–100% about 80%	not reported	Section 4.3, Figure 3

• Authors state OSA construction time is shorter on log axis; Figure 1 caption doesn't give seconds. In Table 1, linear rows mostly 00:00, nonlinear ε-greedy 00:12 to 00:22, ETC 00:03 to 00:09.
• Authors interpret results on two robust algorithms as: these algorithms assume adversary changes realized rewards during interaction, while this paper changes weights before training and has no access to runtime environment. Figure 6 grid is T∈{100,1000}, K∈{3,5}, d=1000, α=0.1, σ=1; main text doesn't report norms per cell.
• Figure 3 caption writes two configurations without explaining content. In one Aesthetic trajectory in Appendix J, UCB continuously selects SD3 without attack, after OSA selects Openjourney. Appendix F states ASR distribution for randomly initialized networks is similar to Figure 3, without giving percentages.

Dimensions and Defenses

• Dimensions: Figure 2 left setting is T=100, K=3, ASR=100%. Authors state ℓ2 and ℓ∞ decrease with input dimension; at low dimension OSA has small gap relative to Optimal, gap shrinks as dimension increases. Norm and gap values per dimension not written. Appendix H uses PCA to project to three dimensions (T=100, D=1000, K=3 or 4); authors state perturbation is not simple reversal of w. Scatter positions not visible in transcript.
• Defenses: shuffle a segment of log before execution. Figure 2 right shuffles before T/2; Figure 8 additionally tests T/4 and 3T/4. Authors state larger shuffle fraction makes attack harder to succeed. ASR values after shuffling not reported.
• Random noise and width: Figure 4 right, without perturbation ASR about 25%; increasing random ℓ2, authors state ASR remains near that level. Figure 4 left, T=100, hidden width above 750 makes ASR reach 100%. Authors state linear approximation doesn't hold when width insufficient; ASR below 750 not listed in main text.

Other Ablations and Analysis

• OSA constraint count: T from 10 to 100,000, K=3 and K=5, authors state grows as O(log T) (Figure 7).
• ETC's m=5; ε-greedy initial 0.1, floor 0.01 (Appendix D).
• Synthetic network: 100 epochs, batch 1024, learning rate 10^{−3}, train/validation 80%/20% (Appendix E).
• Real large models only change small subset of weights; size of subset not reported (Section 4.3).
• Negative result: random noise cannot replace targeted attack (Section 4.6); authors state defenses only partially mitigate.

Limitations and future directions noted by the authors

The paper has no separate Limitations section. What is explicitly written as incomplete or out of scope includes:

• Full defense: The authors state that the proposed defense only partially mitigates under certain conditions, and a full defense remains open, listed as a future direction (Defense paragraph in the introduction).
• OSA theory: The authors state that a full theoretical analysis of OSA is beyond the scope of this paper (Section 3).
• Distribution class: The authors conjecture that more general norm results may hold on near-product measures, but this is beyond the scope of this paper (Section 3.2).

Experimental coverage

• Algorithms include UCB, ETC, ε-greedy, Fast–Slow, and ε-contamination (Sections 4.1, 4.4, 4.8).
• Reward models include linear, single-hidden-layer ReLU, Image Reward, Aesthetic Model, and randomly initialized networks in Appendix F.
• Real logs come from five generative models, 30 prompts from GenAI-Bench, seeds 1 to 100 (Section 4.3).
• Defense experiments shuffle T/4, T/2, and 3T/4 of the log (Figure 2, Figure 8).
• The paper does not report the number of ASR repetitions, the ASR values after shuffling, the size of the subset of parameters modified in the real models, or the perturbation norms on each input dimension.

作者研究离线 bandit 在奖励模型被事先改权重时，还会不会选出最优臂。

• 问题：生成模型评测常把公开权重的奖励模型接到 UCB 等算法上，用固定日志代替反复在线采样。作者关心攻击者只改权重、不改样本、不插手训练时，能否劫持选臂。
• 方法：把指定轨迹或避开最优臂写成 UCB 分数约束，对线性奖励解最小 ℓ2 扰动的二次规划；足够宽的网络用 NTK 收成同类规划。OSA 只在最优臂即将领先时加入亚军约束。作者给出高维下的可行性，以及全轨迹扰动范数随维度下降的界。摘要把 d≥KT 归于 Theorem 3.3；正文 Theorem 3.3 写的是 d>(T−K)(K−1)，d≥KT 出现在 Theorem 3.4。
• 结果：合成数据上，UCB 的三种攻击以及 T=100 的 ε-greedy 与 ETC，ASR 为 100%（Figure 1、Table 1）。Fast–Slow 在 K∈{3,5}、T=1000、d=1000 上 ASR 为 100%，ℓ2 为 ≈ 0.3（Figure 5）。ε=0.15 的 ε-contamination 上，正文写 ASR 为 100%、ℓ2 约为 0.2。无定向扰动时 ASR 约 25%（Figure 4）。作者称随机 prompt 下，Image Reward 与 Aesthetic Model 有约 80% 概率使 ASR 落在 90–100%。
• 结论：作者认为公开奖励权重会使离线评测暴露于这类攻击，输入维越高所需扰动越小；打乱部分日志只能部分缓解，完整防御仍开放。