超越奖励压制：有界奖励热启动 Bandit 的近最优离线攻击

有界奖励下，只能在部署前注入合法样本时，使目标臂在几乎所有在线轮被选中的成本最优攻击，是否必须把不可忽略的成本直接花在目标臂上。

• 场景：推荐与在线广告常用 warm-start 多臂赌博机，以历史交互初始化。作者认为，部署前注入的虚假反馈会偏置初始估计，且之后反馈全为真实时该偏差仍可能留下。
• 现有不足：既有攻击多在在线阶段压低非目标臂，成本常按奖励改动幅度计。作者认为这与直接抬高目标物品的做法不一致。
• 核心问题：抬高目标臂会同时优于所有竞争臂，但会被真实在线反馈稀释；压低单个竞争臂只影响该臂，且有界奖励限制每个注入样本能改变的经验均值。
• 本文做法：成本定义为部署前注入的合法动作–奖励对条数。对 UCB 给出上下界，作者称近边界时二者匹配到首阶，并刻画目标提升与非目标压制的分配；再推广到 Thompson Sampling、ϵ-greedy 与 suppression-bounded 算法。
• 威胁模型：
  • 目标：使目标臂 K 被选中。零容忍 ξ=0 要求每一在线轮都选 K。(ξ, δ)-success 要求非目标在线拉动之和不超过 ξ 的概率至少 1-δ，且 C(n)=o(T)。
  • 知识：观察干净离线日志 D_cl，已知策略 Π、终止时刻 T 与合法区间 [r_min, r_max]。
  • 能力：只在部署前注入；奖励须落在该区间，离散反馈还须属于合法字母表。上线后不能改动作、观测奖励或历史。
  • 受害系统：先用离线日志初始化、再在线交互的随机多臂赌博机。奖励为 [r_min, r_max] 上的 σ^2-次高斯，σ^2 对学习者已知。主构造针对 UCB。

按第 1.2 节的两条线组织：设计攻击，以及设计抗攻击的鲁棒算法。

在线与离线攻击

• Jun et al. [2018]：给出可把 UCB 与 ϵ-greedy 导向目标臂的次线性成本攻击。Table 1 将其标为在线、奖励无界、无目标提升、无分配分析、成本最优性一列为否。
• Liu and Shroff [2019]：给出不需知道学习者算法的自适应攻击，并把离线奖励投毒写成若干算法上的凸优化。Table 1 的离线一行标为有目标提升、有成本最优性，但奖励无界、无分配分析；其在线变体因不满足表中任一列而被省略。
• Zuo [2024]：对 UCB 与 TS 给出带匹配下界的近最优攻击。Table 1 标为在线、奖励无界、无目标提升、无分配分析，成本最优性一列为是。

受限干预与离线扰动

• Xu et al. [2021]：在预定在线阶段做无观测攻击。第 4.1 节比较其 UCB 攻击：近边界的规定成本为 Θ(K log T/Δ_K^2)；Δ_K=O(√(K log T/T)) 时不再次线性；Δ_K=0 时未定义。
• Zeng et al. [2025]：有界虚假数据注入，并限制注入时机与频率；提出 suppression-bounded 类。Table 1 标为在线、有界、无目标提升、无分配分析、无成本最优性。本文沿用其虚假数据注入模型，改为离线到在线。
• Hosseini et al. [2026]：在训练离线赌博机之前扰动奖励模型，之后没有在线交互。Table 1 标为离线、奖励无界、无目标提升、无分配分析、无成本最优性。

其他设定与鲁棒算法

• 上下文与排序等攻击：Garcelon et al. [2020]、Wang et al. [2022]、Ma and Zhou [2023]、Zuo et al. [2023] 研究上下文、线性、对抗与 learning-to-rank 赌博机上的攻击。
• 鲁棒赌博机：Lykouris et al. [2018] 与 Gupta et al. [2019] 给出依赖腐败水平的遗憾界；Kapoor et al. [2019]、Bogunovic et al. [2021]、He et al. [2022a] 等用稳健估计或置信加权回归控制被污染观测。作者认为这些威胁模型通常弱于攻击文献，因为对手在污染反馈之前不能观察学习者的动作。高斯过程、Lipschitz 与组合赌博机上的鲁棒性分别见 Bogunovic et al. [2022]、Kang et al. [2023]、Xu and Li [2021]。

基线与数据

• 数值对照为 Clipped Suppression，以及 UCB 上的 Xu et al. [2021]。UCB 与 TS 用 MovieLens-25M；ϵ-greedy 附录用合成 Bernoulli 奖励。

作者称既有工作分别研究离线投毒、有界攻击或成本最优性，但没有刻画攻击力度应如何在各臂之间分配；本文将有界离线注入与直接提升目标臂合在一起，并称首阶成本最优的攻击必须在目标臂上投入不可忽略的成本（Table 1）。

整体是一次部署前的有界注入：Algorithm 1 选定注入计划后，把伪造动作–奖励对拼到干净日志末尾。

设定与成本

K 个臂，奖励支撑在 [r_min, r_max] 且为 σ^2-次高斯，σ^2 对学习者已知。学习者持有干净日志 D_cl，再从 T_0+1 交互到 T。攻击者只在部署前拼接伪造样本。成本是注入条数 C(n)\triangleq\sum_{i=1}^{K}n_i，即伪造动作–奖励对的个数。总日志长度变为 T_0^{cl}+C(n)，在线长度 H=T-T_0 随注入变短。目标臂记为 K。

(ξ, δ)-success 要求非目标在线拉动之和不超过 ξ 的概率至少 1-δ，且成本为 o(T)。Algorithm 1 先选满足该式的 (n, y)，再拼接伪造日志；每条奖励必须落在 [r_min, r_max]，离散反馈还须属于合法字母表。

对 UCB 的零容忍构造

主分析取 ξ=0。UCB 指数为经验均值加 3σ 乘 log t/N_i(t) 的平方根；零次观测的臂指数为无穷。思路是拉大目标与非目标的差距，并压小非目标探索项，使 u_K(t) 在每个在线轮都高于 u_i(t)。

设每个臂的干净次数至少为 1，R=r_max-r_min。对 δ∈(0, 1/2)，用半径 β_δ 把 μ_K 定为 r_min 与干净目标均值减两倍半径的较大者，ε=μ_K-r_min。阈值 z 取 r_min 加上两项的较大者：z_T^-r_min，以及 min{ε, R/2}。z_T^ 等于 r_min 加上 (18Rσ^2(K-1)log T/T) 的立方根。

目标注入条数是 T(z-μ_K)_+/(r_max-z) 加 1 后向上取整；非目标条数由干净偏移 B_i、宽度 d(z) 与 log T 解出，见式 (3)。伪造奖励为非目标 r_min、目标 r_max。

Assumption 4.1 令 R、σ 与各臂干净次数均为 Θ(1)，故干净日志长度为 Θ(K)=o(T)。此时任何 o(T) 成本都使 H=T(1-o(1))。

成本界与 2:1 分配

S_T 定义为 T^{2/3}(K log T)^{1/3}。Theorem 4.2：足够大的 T 上，该构造以至少 1-δ 的概率使非目标在线拉动为 0，成本为 O(K log T/(ε∨(S_T/T))^2)。Theorem 4.3：任意 (0, δ)-成功的有界离线 UCB 攻击，以至少 1-δ-1/T 的概率满足成本 Ω(K log T/(Δ_K∨(S_T/T))^2)，其中 Δ_K=μ_K-r_min。

作者把 Δ_K=o(S_T/T) 称为近边界。此体制下把两类首阶成本之和最小化，得到 \Lambda_T\triangleq 3\left(\frac{9\sigma^{2}(K-1)T^{2}\log T}{4R^{2}}\right)^{1/3}，作者将其作为近边界的首阶成本基准，且 Λ_T=Θ(S_T)。Corollary 4.4：Δ_K=o(Λ_T/T) 时，构造成本不超过 (1+o(1))Λ_T；任意零容忍成功攻击以至少 1-δ-1/T 的概率不低于 (1-o(1))Λ_T。

Lemma 4.5：ε=o(Λ_T/T) 时，构造的 n_K=(2/3+o(1))Λ_T。若 Δ_K 同样为 o(Λ_T/T)，则容忍度为 o(Λ_T)、总成本不超过 (1+o(1))Λ_T 的成功攻击，以至少 1-δ-1/T 的概率也必须取这一份额。作者称这是 2:1：目标提升的首阶成本随抬高量线性增长，UCB 的 N_i 负二分之一次方探索项使竞争臂注入合计随抬高量的平方反比下降。ξ=O(Λ_T) 且有确定性 O(Λ_T) 成本帽时，Lemma A.2 仍要求 n_K/C(n)=Ω(1)。

推广到其他算法

Definition 4.7 沿用 Zeng et al. [2025]：若某臂在 t 之后经验均值始终不是最大，则其到 T 的额外拉动以至少 1-δ 的概率不超过确定性上界 B_i^A。Theorem 4.8 把目标均值抬过 r_min+ρ，并把非目标均值压到该阈值或以下；非目标注入还要盖住至多 B_i^A 次、奖励可高至 r_max 的在线观测。在 Assumption 4.1 且非目标上界之和为 o(T) 时，可选 ρ 使成本为 O(K+√(T A_T))=o(T)，并以至少 1-2δ 的概率使在线目标比例为 1-o(1)。作者称 UCB、TS、ϵ-greedy 都属于该类。

附录另给专用构造。TS 每轮从 N(μ̂_i, 1/N_i) 采样并选最大者，条数由式 (6)(7) 的阈值证书确定，成功事件的概率下界为 1-2δ。ϵ-greedy 的理论假设整份离线日志都由攻击者生成，因而干净次数为 0；探索由确定性日程规定，非目标拉动用上界 B 控制，不能单靠增加观测把探索消掉。

实验设置

• 学习者：UCB（第 5 节）、Thompson Sampling（附录 B.2）、ϵ-greedy（附录 C.2）。没有单独的评审模型；是否选中目标臂由拉动次数直接计。
• MovieLens-25M：评分至少为 4 映为 1，其余映为 0。每部电影是一个 Bernoulli 臂，均值取其经验正评分率；干净奖励与在线奖励独立、有放回抽样。目标为 Glitter（ID 4775），μ_K=11/669，是最小的正均值；竞争臂为其余被评分最多的电影。N_i^{cl}=5，σ=0.5，δ=0.05。TS 重复这一设置。
• 扫描：Figure 1–2 在 K=10 时改变 T，在 T=10^6 时改变 K。Figure 3 图例含 K=5、10、15、20、25，横轴 Horizon T 的刻度到 10×10^6。
• 基线：Clipped Suppression。对 UCB，作者称它在非目标臂被拉动时干预，成本为 T-N_K。对 ϵ-greedy，它把每个非目标在线奖励设为 0 并按轮计成本，没有离线日志，且从目标臂开始每臂先拉一次。UCB 另与 Xu et al. [2021] 比较（Figure 4）。
• ϵ-greedy 环境：合成 Bernoulli；非目标均值在 [0.2, 0.8] 上等距，目标均值为 r_T^{eg}/log T 且大于 0；ε_s=min{1, K/s}，δ=0.05。每个配置 50 次独立运行，阴影为一个样本标准差；贪心平局按臂下标打破。
• 指标：攻击成本、N_K^{on}/H、含 warm-start 的 N_K/T、归一化成本 C/Λ_T 或 C/Λ_T^{ts}、目标份额 n_K/C。论文写了 UCB 与 TS 的 every repeat，但未给出重复次数。

主结果

表格较宽，可左右滑动

结果	条件	成本	概率	出处
UCB 构造	Assumption 4.1，δ∈(0,1/2)，T 足够大	O(K log T/(ε∨(S_T/T))^2)	≥1-δ，非目标在线拉动为 0	Theorem 4.2
UCB 任意成功攻击	同上，(0,δ)-success	Ω(K log T/(Δ_K∨(S_T/T))^2)	≥1-δ-1/T	Theorem 4.3
UCB 近边界	Δ_K=o(Λ_T/T)	构造 ≤(1+o(1))Λ_T；攻击 ≥(1-o(1))Λ_T	下界事件 ≥1-δ-1/T	Corollary 4.4
UCB 分配	ε 或 Δ_K 为 o(Λ_T/T)；必要性还要求 ξ=o(Λ_T) 且 C(n)≤(1+o(1))Λ_T	n_K=(2/3+o(1))Λ_T	必要性事件 ≥1-δ-1/T	Lemma 4.5
TS 构造	Δ_K=o(S_T/T)，Assumption 4.1	≤(1+o(1))Λ_T^{ts}；E_δ 下 n_K=(2/3+o(1))Λ_T^{ts}	≥1-2δ，非目标在线拉动为 0	Theorem B.2
ϵ-greedy 构造	离线日志全由攻击者构造，R=Θ(1)，sum ε_s+K log(K/δ)=o(T)	(2+o(1))√(T(K-1)B)	≥1-δ，非目标在线拉动 ≤(K-1)B	Theorem C.2

• 作者称近边界体制下 UCB 上下界的首阶常数对齐，因此该构造达到渐近最优的首阶成本。
• 作者称 ε=Ω(Δ_K) 时间隙相关的速率匹配；ε=Ω(1) 时上下界同为 Θ(K log T)，与 Zeng et al. [2025] 的成本阶一致。
• 作者称同一套目标提升加非目标压制可用于 suppression-bounded 类，而 UCB、TS、ϵ-greedy 都在该类中。

MovieLens 上的 UCB

• 作者称本文成本低于 Clipped Suppression；T 增大时成本增长与 Theorem 4.2 的次线性上界相符，而基线成本为 T-N_K，随 T 增长更快，差距也随 K 增大。Figure 1 的纵轴为 Attack Cost，横轴分别为 Horizon T 与 Number of Arms K。
• 作者报告：在所有测试的 T 与 K 上，每次重复都有 N_K^{on}/H=1，即部署后每一在线轮都选目标臂；并称含 warm-start 的 N_K/T 接近 1。Figure 2 同时画出 N_K/T、N_K^{on}/H 与 Clipped Suppression 的 N_K/T。
• 作者称即使 T=10^6，Clipped Suppression 仍使学习者在将近一半的轮次选择非目标臂，且目标臂选择比例随 K 进一步下降。

近边界份额与 Xu et al. [2021]

• Figure 3(a) 纵轴为 C/Λ_T，刻度从 1 到 1.1。作者称每个固定 K 下，归一化成本随 T 增大靠近 1，与 Corollary 4.4 一致。Figure 3(b) 标出 2/3 与 1/3；作者称 K=10 时 n_K/C(n) 靠近 2/3，与 Lemma 4.5 一致。
• Figure 4 横轴为 Δ_K/(S_T/T)。作者称该比值小于 1 时本文仍保持次线性成本，并以高概率使部署后每一在线轮都选目标臂。Xu et al. [2021] 的成本按 O(K log T/Δ_K^2) 在 Δ_K 靠近 0 时变大；Δ_K=0 或该成本至少为 T 时其点被省略，且在最难的近边界设置里其目标臂选择比例低于 1。第 4.1 节还称：Δ_K=O(S_T/T) 时其成本为 Ω(S_T)，Δ_K=O(√(K log T/T)) 时不再次线性，Δ_K=0 时未定义，而本文构造仍覆盖该边界。

TS 与 ϵ-greedy

• 附录 B.2 重复第 5 节的对照与近边界实验，并在取整前数值最小化式 (6)(7) 的连续总条数。作者称本文每次重复都只有目标臂的在线拉动；成本低于 Clipped Suppression，除臂数最小的设置外——该处基线成本更低，但仍拉动非目标臂。
• Figure 7 纵轴 C/Λ_T^{ts} 的刻度从 1 到 1.3，并标出 2/3 与 1/3。作者称归一化成本靠近 1，目标臂份额靠近 2/3、非目标合计靠近 1/3；每次重复的非目标在线拉动为 0。
• 附录 C.2：作者称本文的平均成本更低、平均目标臂选择比例更高。全部贪心决策都选了目标臂；其余非目标拉动是探索性的，且低于理论界。

其他消融与分析

• Theorem 4.2 的证明分两支：ε 不超过 z_T^*-r_min 时，目标与非目标合计均为 O(S_T)；ε 更大时 n_K=1，每个非目标为 O(log T/ε^2)。
• Lemma A.2：Δ_K=o(Λ_T/T)、ξ=O(Λ_T)、确定性成本上界为 O(Λ_T) 时，n_K=Ω(Λ_T) 且 n_K/C(n)=Ω(1)，概率至少 1-δ-1/T。
• 对 ε_s=min{1, cK/s}、固定 c>0 且 K log T=o(T)，ϵ-greedy 成本为 O(√(T K log T))，ξ(T)=O(K log T)（附录 C.1）。
• 附录 E：UCB 与 TS 的非目标合计随阈值高度的平方反比下降，平衡后目标臂占 2/3；ϵ-greedy 的探索由日程规定，非目标合计随高度的反比下降，平衡后目标臂占 1/2。
• Theorem 4.8：非目标 B_i^A 之和为 o(T) 时，成本为 O(K+√(T A_T))=o(T)，N_K^{on}/H=1-o(1) 的概率至少 1-2δ。

作者指出的局限与后续方向

• 信任全部离线数据：分析假设学习者不加鉴别地信任所有离线数据。作者提出的后续方向是：折扣、过滤或审计离线观测能否减轻有利于目标臂的注入，以及这类防御如何在干净 warm start 的收益与对被污染初始化的鲁棒性之间权衡（第 6 节）。
• 干净日志较小：成本与分配结果假设干净离线日志较小。更多干净观测使经验均值更难移动，也降低探索不确定性，可能同时改变最优攻击成本及其分配。作者称，刻画这两种效应如何依赖干净观测的规模及其在各臂上的分布，是后续方向（第 6 节）。

实验覆盖范围

• 理论对象包括 UCB 的上下界与分配（第 4.1 节、Corollary 4.4、Lemma 4.5）、TS 与 ϵ-greedy 的附录构造，以及 suppression-bounded 类的通用攻击（Theorem 4.8）。作者称 UCB、TS、ϵ-greedy 都属于该类。
• UCB 与 TS 的数值实验使用 MovieLens-25M，目标臂为 Glitter（ID 4775），N_i^{cl}=5，σ=0.5，δ=0.05；Figure 1–2 在 K=10 时变 T、在 T=10^6 时变 K。
• UCB 的对照包括 Clipped Suppression 与 Xu et al. [2021]（Figure 4，横轴 Δ_K/(S_T/T)）。TS 重复了 Clipped Suppression 对照与近边界份额实验（附录 B.2）。
• ϵ-greedy 使用合成 Bernoulli 奖励，非目标均值在 [0.2, 0.8] 上等距，ε_s=min{1, K/s}，每个配置 50 次独立运行（附录 C.2）。其理论构造假设整份离线日志由攻击者生成。
• 论文未报告 UCB 与 TS 数值实验的重复次数。

有界离线攻击把 warm-start 随机赌博机在部署前的历史当作注入面，成本按合法样本条数而不是奖励改动幅度计。

要处理的约束是：奖励必须落在合法区间，上线后不能再改动作、奖励或历史。作者认为直接抬高目标并不只是启发式；目标均值贴近下界时，使 UCB 在几乎所有在线轮选中目标、且达到首阶最优成本的攻击，必须把不可忽略的成本花在目标臂上。

构造对目标臂写入奖励上界、对竞争臂写入下界，使目标 UCB 指数盖过全部在线轮。近边界 Δ_K=o(Λ_T/T) 下，Corollary 4.4 给出构造成本不超过 (1+o(1))Λ_T，并称任意零容忍成功攻击以至少 1-δ-1/T 的概率不低于 (1-o(1))Λ_T；Λ_T 与 S_T=T^{2/3}(K log T)^{1/3} 同阶。Lemma 4.5 把目标臂份额定为 2/3+o(1)。TS 在 Theorem B.2 中有同类成本上界，且在事件 E_δ 下份额同样为 2/3+o(1)。ϵ-greedy 在离线日志全由攻击者构造时，成本为 (2+o(1))√(T(K-1)B)；附录 E 将其目标臂份额配成 1/2。

MovieLens-25M 上，Glitter 的 μ_K=11/669。作者报告 UCB 每次重复的 N_K^{on}/H=1，并称成本低于 Clipped Suppression，K=10 时目标份额靠近 2/3。TS 除臂数最小的设置外成本也更低。作者的结论是：容忍度与确定性成本帽均为 O(S_T) 时，目标臂必须拿到不可忽略的注入份额；若学习者折扣、过滤或审计离线数据，或干净日志变大，成本与分配都可能改变。