EN KR JP CN RU IN
ICML

对组合多臂老虎机（CMAB）的对抗性攻击

Authors Rishab Balasubramanian, Jiawei Li, Prasad Tadepalli, Huazheng Wang, Qingyun Wu, Haoyu Zhao ; Proceedings of the 41st International Conference on Machine Learning, PMLR 235:2505-2526
ISOM Posted 2026-03-19 18:48 UTC
Read Time 26M
Open PDF Open MICCAI page

背景与学术渊源

起源与学术渊源

本文所研究的“对抗性攻击组合多臂老虎机（CMAB）”问题，源于两个重要研究领域的汇聚：多臂老虎机（MAB）和机器学习中的对抗性鲁棒性研究。多臂老虎机（MAB）的基本框架，最初由Auer（2002）探索，模拟了序列决策过程，其中智能体必须在探索新选项和利用已知有利选项之间进行战略性平衡，以最大化一段时间内的累积奖励。该框架已被广泛研究并应用于各种领域。

组合多臂老虎机（CMAB）作为MAB的一个更广义的版本，因其广泛的现实世界应用，如在线广告、推荐系统和影响力最大化（Liu & Zhao, 2012; Kveton et al., 2015），而获得了显著的关注。在CMAB中，智能体的决策涉及在每一轮中选择一组基础臂（称为“超级臂”），而不是单个臂。这种组合性质使得探索-利用的权衡变得复杂得多，主要是因为可能的超级臂数量会随着基础臂数量呈指数级增长。

这个特定问题的精确起源——即重新定义和重新评估CMAB的“可攻击性”概念——源于近期发现MAB算法及其变种容易受到对抗性攻击，特别是“奖励投毒攻击”（Jun et al., 2018; Liu & Shroff, 2019）。在这种攻击中，攻击者观察被拉动的臂及其奖励反馈，然后微妙地修改此反馈，以误导学习算法指向一个有利于攻击者利益的特定目标臂。虽然可攻击性的概念先前已应用于标准的MAB设置（Wang et al., 2022），但直接将其定义扩展到CMAB被证明是存在问题的。先前方法的根本局限在于，将MAB的可攻击性定义直接应用于CMAB会产生一个成本上限，该上限在时间范围 $T$ 上是次线性的，但在基础臂数量 $m$ 上是指数级的。这种对 $m$ 的指数依赖性在实际场景中是极不可取的，常常导致结果空洞，攻击成本甚至可能超过总时间范围 $T$。这种不足凸显了原始可攻击性概念的不足，从而需要为CMAB提供一个新的、更合适定义，而本文正是致力于此。

直观的领域术语

  • 多臂老虎机（MAB）： 想象你在赌场里面对一排老虎机，每台老虎机都有一个未知的平均赔率。你的目标是在多次游玩中最大化总赢利。在每一轮中，你选择一台机器，拉动它的拉杆，并获得奖励。你必须学习哪些机器是好的（利用），同时还要尝试其他机器以发现可能更好的机器（探索）。
  • 组合多臂老虎机（CMAB）： 这类似于MAB场景，但与每轮只选择一台老虎机不同，你选择一组或组合老虎机同时进行游戏。例如，你可能决定同时玩机器2、5和8。这个问题要困难得多，因为可能的机器组合远远多于单个机器。
  • 超级臂： 在CMAB的语境中，“超级臂”是指你在给定回合中选择玩的一组或组合的个体老虎机。它代表了你当轮的完整行动。
  • 基础臂： 这些是构成组合的个体、基础老虎机。如果你选择了一个由机器2、5和8组成的超级臂，那么2、5和8就是构成你所选超级臂的个体“基础臂”。
  • 奖励投毒攻击： 这描述了一种情况，即恶意方秘密地改变你从老虎机收到的奖励信息。他们的目标是通过使特定、通常利润较低的组合（他们的“目标超级臂”）的赔率看起来比实际更好，或者使真正好的组合看起来更差，来欺骗你的决策过程，使其反复选择该组合。

符号表

符号 描述
$m$ 基础臂的总数。
$\mathcal{S}$ 所有可能的超级臂（基础臂的组合）的集合。
$S \in \mathcal{S}$ 一个特定的超级臂。
$T$ 老虎机问题的总时间范围（回合数）。
$\mu = (\mu_1, \ldots, \mu_m)$ 所有 $m$ 个基础臂的真实平均奖励向量。
$r_S(\mu)$ 在真实平均奖励向量 $\mu$ 下，超级臂 $S$ 的期望奖励。
$O_S$ 选择超级臂 $S$ 时可能被概率触发的基础臂集合。
$\mu \odot O_S$ $\mu$ 与表示 $O_S$ 的二元向量的元素乘积，有效地将未在 $O_S$ 中的基础臂的平均奖励归零。
$\Delta_S$ 超级臂 $S$ 的“间隙”，量化其可攻击性（定义 3.5）。
$M$ 攻击者希望老虎机算法拉动的目标超级臂集合。
$\Delta_M$ 目标集 $M$ 的整体“间隙”，定义为 $\max_{S \in M} \Delta_S$。
$C(T)$ 攻击者在时间范围 $T$ 内产生的总攻击成本。
$o(T)$ 一个增长慢于 $T$ 的函数，即 $\lim_{T \to \infty} o(T)/T = 0$。
$p^*$ 与触发基础臂的最小概率相关的参数（定义 3.1）。
$K$ 与问题相关的参数，通常与超级臂的数量或遗憾界限有关。
$\gamma, \gamma'$ 与遗憾和攻击成本的次线性增长相关的正常数。
$\hat{\mu}_i^{(t)}$ 第 $t$ 回合基础臂 $i$ 的经验平均奖励估计。
UCB 上置信界，由老虎机算法用于探索-利用。

问题定义与约束

核心问题表述与困境

本文研究了组合多臂老虎机（CMAB）在对抗性攻击下的脆弱性理解中的一个关键差距。

输入/当前状态：
起点是一个标准的CMAB问题，其中一个学习智能体在时间范围 $T$ 内依次选择由“基础臂”组成的“超级臂”。在每一轮中，智能体观察反馈（触发的基础臂的结果）并获得奖励，目标是最大化累积奖励。当前的研究承认，多臂老虎机（MAB）及其变种容易受到“奖励投毒攻击”。在这种攻击中，攻击者观察智能体的行动和反馈，然后微妙地修改观察到的奖励。攻击者的目标是通过使一个特定的“目标臂”（符合攻击者利益的臂）的赔率看起来更好，或使真正好的组合看起来更差，来误导老虎机算法，使其在几乎所有回合（$T - o(T)$ 次）中持续拉动该目标臂，同时在时间范围 $T$ 内产生次线性攻击成本 $o(T)$。

期望输出/目标状态：
本文的主要目标是建立一个“能够捕捉CMAB脆弱性和鲁棒性的良好概念”，该概念具有实际意义。这个新定义，称为“多项式可攻击性”，旨在精确定义CMAB实例何时可以被高效攻击。在此改进定义下，成功的攻击不仅必须实现其目标（在 $T - o(T)$ 回合内误导智能体拉动目标臂），而且攻击成本必须是次线性于时间范围 $T$ 并且，至关重要的是，是多项式于基础臂数量 $m$ 和其他相关问题因素（例如，$1/p^*$，$K$）。

缺失环节/数学鸿沟：
精确的缺失环节是CMAB的鲁棒且实用的“可攻击性”定义。直接从更简单的MAB设置借用的先前定义，对于CMAB来说是不够的。这是因为CMAB的组合性质意味着可能的“超级臂”数量可能随着基础臂数量 $m$ 成指数级增长。应用旧定义将意味着攻击成本将随着 $m$ 指数级增长，使其在实践中“不可取”且“空洞”，因为这种成本很容易超过总时间范围 $T$。本文通过引入“多项式可攻击性”来弥合这一鸿沟，该定义明确将攻击成本限制为关于 $m$ 的多项式，从而使可攻击性的概念对于CMAB来说是相关且实用的。在数学上，这涉及到从一般的 $C(T) = o(T)$ 成本转移到更具体的 $C(T) = O(\text{poly}(m, 1/p^*, K) \cdot T^{1-\gamma'})$，其中 $\gamma' > 0$，而 $m$ 是基础臂的数量，$p^*$ 与触发概率有关，$K$ 是一个特定于问题的参数。本文还定义了每个超级臂 $S$ 的“间隙” $\Delta_S$（定义 3.5），它量化了其期望奖励与任何其他超级臂的最大期望奖励之间的差异，作为可攻击性的关键数学指标。

困境：
困扰先前研究人员的核心困境是CMAB的组合复杂性与攻击成本的实际性之间的权衡。虽然直接扩展MAB攻击概念很诱人，但这样做会导致关于基础臂数量 $m$ 的指数级成本，使得任何“成功”的攻击定义在现实场景中毫无意义。本文强调了一个令人惊讶且痛苦的权衡：CMAB实例的可攻击性不仅是内在属性，而且“还取决于老虎机实例是已知还是未知于攻击者”。这意味着，在白盒设置（环境参数已知）中有效的攻击策略，在黑盒设置（参数未知）中可能会完全失败，使得通用攻击策略难以捉摸，并且该问题在实践中“极其困难”。

约束与失败模式

高效且有意义地攻击CMAB实例的问题受到几个严峻的现实壁垒的约束：

  1. 超级臂的组合爆炸： 最显著的约束是可能的“超级臂”的数量，这可能随着基础臂数量 $m$ 指数级增长。这种组合复杂性意味着任何需要探索或操纵所有超级臂的攻击策略都将产生指数级成本，违反了多项式可攻击性的实际要求。这使得直接应用MAB攻击策略不切实际，并导致“空洞的结果”。
  2. 攻击者对环境的了解： 一个关键的约束是攻击者对CMAB实例底层参数的访问权限，例如奖励分布（$\mu$）和基础臂的输出分布。
    • 已知环境（白盒）： 如果攻击者完全了解这些参数，他们可以设计高度针对性和高效的攻击。
    • 未知环境（黑盒）： 在更现实的黑盒设置中，攻击者缺乏这种先验知识。这迫使攻击者进行探索以估计参数，这本身就会产生成本，并可能使攻击变得更加困难甚至不可能。本文通过一个“困难示例”（定理 4.1）展示了这一点，其中一个实例在环境已知时是多项式可攻击的，但在环境未知时是多项式不可攻击的。这凸显了一个主要的实际障碍。
  3. 攻击成本预算： 攻击者在严格的预算约束下运作：攻击成本必须是时间范围 $T$ 的次线性，并且在新定义下，是基础臂数量 $m$ 和其他因素的多项式。超出此预算即构成失败模式，因为攻击将不被认为是“高效”或“成功”的。
  4. 半老虎机反馈： CMAB中的学习智能体接收“半老虎机反馈”，这意味着它只能观察到所选超级臂触发的基础臂的输出，而不是所有基础臂。这种部分可观测性限制了可供攻击者使用信息，使得准确估计奖励或有效操纵奖励更加困难，尤其是在未知环境中。
  5. 算法鲁棒性与遗憾界限： 攻击必须成功对抗旨在最小化遗憾的学习算法（如CUCB），通常具有 $O(\text{poly}(m, 1/p^*, K) \cdot T^{1-\gamma})$ 的理论遗憾界限。攻击者需要克服算法固有的学习和探索机制，而不会产生过高的成本。
  6. 预言机限制： CMAB问题通常依赖于计算预言机（例如，用于查找最优超级臂）。如果这些预言机是近似的而非精确的（例如，$(\alpha, \beta)$-近似预言机），则可能给攻击者带来额外的复杂性，因为算法的行为可能偏离精确预言机产生的行为，从而可能影响攻击效果。

为什么选择这种方法

选择的必然性

作者选择为组合多臂老虎机（CMAB）定义“多项式可攻击性”，这不仅仅是一个选项，而是一个必然，源于将传统可攻击性概念应用于这一复杂领域所固有的局限性。作者意识到标准多臂老虎机（MAB）的最新（SOTA）方法不足以满足需求的那一刻，在引言中得到了清晰的阐述。他们指出，“将MAB的可攻击性概念直接应用于CMAB是诱人的……然而，这会导致在 $T$ 上是次线性成本，但在基础臂 $m$ 上是指数级成本。” 这种对 $m$（基础臂数量）的指数依赖性被明确称为“不可取”，并且可能超过时间范围 $T$，从而使结果“空洞”（第1页）。

这一关键观察表明，CMAB固有的组合爆炸，其中超级臂的数量可能随着 $m$ 指数级增长，从根本上打破了先前MAB可攻击性定义的假设。需要一种能够在实际计算限制内提供有意义保证的解决方案。因此，提出的多项式可攻击性定义，要求攻击成本不仅是时间范围 $T$ 的次线性，而且是基础臂数量 $m$ 和其他因素的多项式，成为提供可处理且相关的CMAB对抗性攻击分析框架的唯一可行解决方案。

比较优势

这种方法在质量上的优越性直接源于其能够解决CMAB的组合复杂性这一挑战，而这是先前MAB可攻击性的黄金标准未能克服的。除了简单的性能指标外，结构上的优势在于将一个棘手的指数成本问题转化为一个可处理的多项式问题。

具体而言，MAB的“原始可攻击性概念”，当应用于CMAB时，导致了“在 $m$ 上的指数成本”（第1页）。这意味着随着基础臂数量的增加，攻击成本将迅速变得天文数字，使得任何理论保证在实践中都毫无意义。新的“多项式可攻击性”定义（定义 3.1）通过要求攻击成本被 $m$、$1/p^*$ 和 $K$（其中 $p^*$ 与触发概率有关，$K$ 是来自遗憾界限的一个因子）的多项式函数所界定，从根本上改变了这一点。这是一个质的飞跃，因为它允许对高维CMAB设置中的可攻击性进行有意义的分析，其中超级臂的数量是指数级的。

此外，本文提供了一个多项式可攻击性的充要条件（定理 3.6），基于“间隙” $\Delta_M$（定义 3.5）。这种理论表征提供了对某些CMAB实例为何可攻击或不可攻击的深刻结构洞察，而不仅仅是衡量攻击表现如何。它提供了一个清晰的内在鲁棒性边界，这比仅在特定实例上提供经验性能的方法具有显著的定性优势。该方法有效地将内存复杂度从隐式的 $O(2^m)$（由于指数级超级臂）降低到对 $m$ 的多项式依赖，使得问题可分析。

与约束的对齐

所选定的“多项式可攻击性”定义方法与CMAB问题的核心约束完美对齐，特别是其组合性质带来的挑战。如问题定义中所强调的，主要约束是CMAB中可能的超级臂数量可能“随着 $m$ 指数级增长”（第1页）。直接应用不考虑这种指数增长的MAB可攻击性定义，会导致“空洞的结果”，因为攻击成本也会随着 $m$ 指数级增长。

问题严峻要求与解决方案独特属性之间的“联姻”体现在定义 3.1 中。该定义明确规定，成功攻击的成本必须是基础臂数量 $m$（以及其他因素，如 $1/p^*$ 和 $K$）的多项式，并且是时间范围 $T$ 的次线性。这确保了即使对于大型CMAB实例，可攻击性的概念也保持有意义且实用。

此外，本文侧重于“奖励投毒攻击”（第 2.2 节），其中攻击者修改观察到的奖励。提出的攻击算法（算法 1）和可攻击性条件（定理 3.6）专门针对此威胁模型，确保解决方案符合定义的对抗性能力和限制。该方法还考虑了CMAB的“半老虎机反馈”性质，即只观察到触发基础臂的输出，并将此反馈结构整合到攻击策略中。

替代方案的拒绝

本文清楚地阐述了拒绝或修改现有方法的理由，主要侧重于直接应用传统的MAB可攻击性定义。其不足的核心论点是，当应用于CMAB时，它们会导致“在 $m$ 上的指数成本”（第1页）。这不是一个小的性能问题，而是一个根本性的缺陷，使得结果在实践中“不可取”且“空洞”。CMAB的组合性质，具有指数级大的超级臂数量，意味着成本随着基础臂数量指数级增长的攻击成本根本不可行或无意义。因此，作者不得不引入一个新定义，要求 $m$ 上的多项式成本。

此外，本文隐含地拒绝了其他相关工作，认为它们不直接适用或不足以满足其特定的问题表述：

  1. 现有的MAB可攻击性定义： 如上所述，由于在 $m$ 上的指数成本，这些被认为是不够的。
  2. 对强化学习（RL）的对抗性攻击： 虽然相关，但本文指出“现有工作均未分析给定实例的可攻击性”（第2页，第1.2节）。这表明，虽然RL攻击是一个广泛的领域，但它们并未提供本文为CMAB寻求的实例级可攻击性表征。
  3. 抗腐败老虎机： 这条替代性工作研究了对投毒攻击的鲁棒性，被提及但隐含地拒绝作为直接解决方案，因为它通常考虑“较弱的威胁模型”（第2页，第1.2节）。例如，一些模型假设一个无意识的攻击者或限制腐败仅增加输出。相比之下，本文的威胁模型允许攻击者增加或减少输出，使得问题比抗腐败老虎机算法通常处理的问题更通用、更具挑战性。这种更广泛的对抗性能力需要更鲁棒的攻击性框架。
Figure 3. An unattackable shortest path from s to t in the Flickr dataset. Optimal path: (s, a, b, e, t). Target path: (s, a, v, c, d, t). The cost on (b, c, d, t) is larger than the number of edges on (b, e, t), and the attacker cannot fool the algorithm to play the target path

数学与逻辑机制

主方程

本文中定义组合多臂老虎机（CMAB）实例可攻击性的绝对核心方程是定义 3.5 中的超级臂 $S$ 的“间隙”定义。这个间隙量化了CMAB实例对奖励投毒攻击的内在脆弱性或鲁棒性。

$$ \Delta_S := r_S(\mu) - \max_{S' \neq S} r_{S'}(\mu \odot O_S) $$

对于一组目标超级臂 $M$，整体间隙定义为 $\Delta_M = \max_{S \in M} \Delta_S$。定理 3.6 随后确立，如果 $\Delta_M > 0$，则CMAB实例是多项式可攻击的，如果 $\Delta_M < 0$，则它是多项式不可攻击的。

按项解剖

让我们逐项剖析主方程，以理解其数学定义、物理/逻辑作用以及其运算符背后的原理。

  • $\Delta_S$：

    • 数学定义： 这是一个标量值，表示特定目标超级臂 $S$ 的期望奖励与任何其他超级臂 $S'$ 的最大期望奖励之间的差异，当在修改后的平均奖励向量下进行评估时。
    • 物理/逻辑作用： 它充当特定目标超级臂 $S$ 的“脆弱性指标”。正的 $\Delta_S$ 意味着目标超级臂 $S$ 本质上比任何替代臂 $S'$ 更优，前提是这些替代臂仅在 $S$ 本身可观察到的基础臂上进行评估。这表明攻击者可能存在误导老虎机算法指向 $S$ 的途径。如果 $\Delta_S$ 为负，则表示即使在此特定评估下，$S$ 也不是最佳选择，使其更难攻击。
    • 为何使用减法和最大值： 减法用于量化 $S$ 相对于其最佳替代品的“优势”。$\max$ 运算符在特定评估上下文中识别 $S$ 的最强竞争对手，确保间隙真正反映了最难克服的替代品。

  • $r_S(\mu)$：

    • 数学定义： 这表示选择超级臂 $S$ 的期望奖励，其中 $\mu$ 是所有基础臂的真实平均奖励向量。
    • 物理/逻辑作用： 这是超级臂 $S$ 的真实、未被篡改的期望性能。它代表了如果没有攻击者，老虎机算法理想情况下应该达到的目标。
    • 为何采用此形式： 这是在老虎机问题中表示行动（超级臂）期望效用的标准方法，取决于底层真实奖励分布。

  • $\mu$：

    • 数学定义： 这是一个 $m$ 维向量 $(\mu_1, \mu_2, \ldots, \mu_m)$，其中 $\mu_i = E_{X \sim D}[X_i^{(t)}]$ 是基础臂 $i$ 的真实平均奖励。
    • 物理/逻辑作用： 该向量代表了CMAB环境中所有基础臂的真实、底层奖励分布。这是老虎机算法试图估计的地面真相，也是攻击者试图操纵的对象。

  • $\max_{S' \neq S}$：

    • 数学定义： 此运算符查找所有不等于目标超级臂 $S$ 的超级臂 $S'$ 的期望奖励中的最大值。
    • 物理/逻辑作用： 这识别了目标超级臂 $S$ 的“最佳替代品”，从攻击者操纵策略的角度来看。攻击者的目标是使 $S$ 比所有其他选项都更有吸引力，因此他们必须考虑最强的竞争对手。

  • $S'$：

    • 数学定义： 表示动作空间 $\mathcal{S}$ 中与目标超级臂 $S$ 不同的任何超级臂。
    • 物理/逻辑作用： 这些是老虎机算法可能选择的替代行动，而不是目标超级臂 $S$。攻击者的目标是使这些替代品显得不那么有吸引力。

  • $\mu \odot O_S$：

    • 数学定义： 这是真实平均奖励向量 $\mu$ 与二元向量 $O_S$ 之间的元素乘积（Hadamard乘积）。向量 $O_S$ 对于可以被超级臂 $S$ 概率触发的基础臂（即 $i \in O_S$）的条目为 $1$，否则为 $0$。
    • 物理/逻辑作用： 这个修改后的平均向量代表了一种假设情况，其中未被目标超级臂 $S$ 可观察到的基础臂的奖励被有效地“归零”或忽略。这很关键，因为攻击者的攻击策略（算法 1）通常涉及将非目标基础臂的观察奖励设置为 0。通过在 $\mu \odot O_S$ 下评估 $S'$，本文模拟了攻击者对替代超级臂的操纵效果。它问道：“如果我们只考虑 $S$ 可以‘看到’的基础臂，那么其他超级臂 $S'$ 的表现如何？”
    • 为何使用元素乘积： 与 $O_S$ 的元素乘积有效地过滤了 $\mu$ 向量，仅保留了 $O_S$ 的基础臂的平均奖励。这在数学上捕捉了关注与目标超级臂 $S$ 相关的基础臂子集的概念。

分步流程

让我们追踪如何使用间隙定义来确定CMAB实例的可攻击性，使其感觉像装配线一样：

  1. 实例特征化输入： 一个特定的CMAB实例被输入系统。该实例由其基础臂 $[m]$、超级臂 $\mathcal{S}$ 的动作空间、环境的触发分布 $D$、概率触发函数 $D_{trig}$ 和奖励函数 $R$ 定义。至关重要的是，假设所有基础臂的真实平均奖励向量 $\mu$ 在此初始评估中是已知的。

  2. 目标集识别： 攻击者指定一组目标超级臂 $M$，他们希望老虎机算法拉动。

  3. 单个超级臂评估（对于每个 $S \in M$）： 对于目标集 $M$ 中的每个超级臂 $S$：

    • 真实奖励计算： 基于真实平均奖励 $\mu$，计算该超级臂 $S$ 的期望奖励 $r_S(\mu)$。这是其基线性能。
    • 可观察基础臂识别： 确定集合 $O_S$。这是当选择超级臂 $S$ 时可能被概率触发的基础臂的集合。可以将其视为 $S$ 的“视野”或其可以直接影响的资源。
    • 修改环境模拟： 构建一个假设环境，其中不在 $O_S$ 中的基础臂的真实平均奖励被有效地设置为零。这创建了修改后的平均奖励向量 $\mu \odot O_S$。这模拟了攻击者压制不相关基础臂奖励的策略。
    • 竞争者评估： 对于其他超级臂 $S' \neq S$（即，当前未被视为目标臂的任何超级臂），使用此修改后的平均奖励向量计算其期望奖励 $r_{S'}(\mu \odot O_S)$。此步骤评估了在仅考虑 $S$ 所见的基础臂的情况下，竞争对手的表现如何，或者攻击者是否操纵了其他臂。
    • 最强竞争者识别： 确定所有这些已评估竞争对手的期望奖励中的最大值，$\max_{S' \neq S} r_{S'}(\mu \odot O_S)$。这是 $S$ 必须克服的最高障碍。
    • 间隙计算： 通过从 $S$ 的真实奖励中减去最强竞争对手的奖励（在修改后的环境下）来计算单个间隙 $\Delta_S$。然后存储此值。

  4. 整体可攻击性确定： 在计算完所有 $S \in M$ 的 $\Delta_S$ 后，找到这些单个间隙的最大值，$\Delta_M = \max_{S \in M} \Delta_S$。

  5. 可攻击性输出：

    • 如果 $\Delta_M > 0$，则CMAB实例被声明为“多项式可攻击的”。这意味着至少有一个目标超级臂 $S$ 具有足够大的优势，即使在竞争对手在攻击者操纵下进行评估时也是如此。
    • 如果 $\Delta_M < 0$，则CMAB实例被声明为“多项式不可攻击的”。这意味着在攻击者提出的操纵下，没有目标超级臂 $M$ 具有明显的优势，使得成功攻击困难或不可能。

优化动态

本文的“数学与逻辑机制”不涉及间隙本身的传统学习或优化过程，因为 $\Delta_S$ 是CMAB实例和目标集的静态属性。相反，动态围绕着攻击者的固定策略（算法 1）如何利用老虎机算法的学习动态来实现其目标，以及间隙 $\Delta_M$ 如何作为成功预测因子。

  1. 攻击者目标： 攻击者的“优化”是迫使老虎机算法在时间范围 $T$ 内，在 $T - o(T)$ 回合中拉动目标超级臂 $S \in M$，同时产生次线性攻击成本 $o(T)$。这是一个目标驱动的操纵，而不是迭代参数更新。

  2. 老虎机算法的学习（例如，CUCB）： 受害者老虎机算法（例如，CUCB）通过迭代估计基础臂的期望奖励并构建超级臂的置信上界（UCBs）来运行。在每一轮 $t$：

    • 它观察拉动的超级臂 $S^{(t)}$ 和触发基础臂的输出 $X^{(t)}$。
    • 它更新基础臂平均奖励的经验估计值（$\hat{\mu}_i^{(t)}$）及其置信区间。
    • 它使用这些估计值计算所有超级臂的UCBs。
    • 然后选择具有最高UCB的超级臂进行下一轮。此过程旨在通过平衡探索（尝试不确定的臂）和利用（拉动高估计奖励的臂）来最小化遗憾。

  3. 攻击者操纵（算法 1）： 攻击者干预此学习循环。当老虎机算法拉动超级臂 $S^{(t)}$ 并观察到输出 $X^{(t)}$ 时，攻击者修改这些输出为 $\tilde{X}^{(t)}$。具体来说，对于任何被触发但不属于目标超级臂 $S$ 的可观察集 $O_S$ 的基础臂 $i$（即，$i \in \mathcal{T}^{(t)} \setminus O_S$），攻击者将其观察到的奖励设置为 $\tilde{X}_i^{(t)} = 0$。其他输出保持不变。

  4. 对老虎机UCB的影响： 这种操纵直接影响老虎机的学习：

    • 通过持续将非 $O_S$ 基础臂的奖励设置为 0，攻击者系统性地压低了这些基础臂的经验平均奖励估计值（$\hat{\mu}_i^{(t)}$）。
    • 这反过来又降低了任何严重依赖这些“归零”基础臂的超级臂的UCBs。
    • 然而，目标超级臂 $S$ 是根据其真实期望奖励 $r_S(\mu)$（或其UCB，攻击者希望保持其高位）来评估的。

  5. 收敛到目标臂： 如果间隙 $\Delta_M > 0$，则表示至少有一个目标超级臂 $S$ 的真实期望奖励 $r_S(\mu)$ 足够高于任何替代臂 $S'$（当这些替代臂在攻击者的操纵下进行评估时，即 $\mu \odot O_S$）。这个正间隙表明，老虎机算法的“损失景观”可以被攻击者有效地塑造。攻击者通过压低非 $O_S$ 臂的奖励的策略将导致非目标超级臂的UCBs低于目标超级臂的UCB。随着时间的推移，老虎机算法的迭代更新将收敛到持续选择目标集 $M$ 中的目标超级臂，因为由于操纵的反馈，其UCB将显得更优。当老虎机的UCBs足够倾斜时，攻击就“成功”了。

  6. 不可攻击性（$\Delta_M < 0$）： 如果 $\Delta_M < 0$，则意味着即使在攻击者最有利的操纵下（将非 $O_S$ 臂归零），也没有目标超级臂 $S \in M$ 比所有其他替代臂都更优。在这种情况下，老虎机算法的UCBs不会收敛到持续偏向目标臂，因为某些非目标臂将始终具有更高（或相当）的UCB，使得实例本质上对这种攻击具有鲁棒性。攻击者操纵奖励的努力将是徒劳的，或者需要指数级成本，违反了多项式可攻击性的定义。老虎机算法的自然探索和利用将阻止其被持续误导。

结果、局限性与结论

实验设计与基线

实验验证经过精心设计，以严格测试关于各种组合多臂老虎机（CMAB）实例多项式可攻击性的理论主张。研究人员采用了多方面的方法，利用真实世界数据集和一系列CMAB应用，每个应用都有特定的目标配置和基线算法。

对于概率最大覆盖（PMC）、在线最小生成树（MST）和在线最短路径问题，使用了Flickr数据集（McAuley & Leskovec, 2012）。对一个子图进行了降采样，保留了最大的弱连通分量，得到了1,892个节点和7,052条有向边，以及它们固有的边激活权重。对于级联老虎机，利用了包含9,000部电影的MovieLens小型数据集（Harper & Konstan, 2015），实验中随机采样了5,000部电影。使用d-rank SVD近似将电影评分映射到用户点击概率。所有实验至少重复10次以确保统计鲁棒性，并报告了平均结果和方差。

“受害者”（基线模型）是标准的CMAB学习算法。对于PMC，使用了带有贪婪预言机的CUCB算法。考虑了两种攻击目标：一个“固定目标”，由具有递减平均出边权重的节点组成；以及一个“随机目标”，即平均出边权重大于0.5的K个随机采样节点。

对于在线MST问题，将Flickr数据集转换为无向图，平均概率作为期望边成本。攻击采用了算法1的修改版本，其中目标被改为通过将修改后的基础臂输出 $X_T = 1$ 来最小化成本。基线是标准的CUCB算法。目标包括一个“固定目标”（第二优最小生成树）和一个“随机目标”（具有随机边权重的最小生成树）。

在在线最短路径问题中，针对CUCB评估了两种不同的目标类型：“不可攻击目标”（一条精心构造的路径，目标路径上的成本本质上高于最优路径，使得误导算法变得困难）和“随机目标”（在随机采样源和目标节点之间的一条最短路径，具有随机边权重）。这种设置对于展示本质上对攻击具有鲁棒性的实例至关重要。

对于级联老虎机，研究将攻击与CascadeKL-UCB、CascadeUCB1和CascadeUCB-V算法进行了对比。目标超级臂是从平均点击概率超过0.1的基础臂子集中选取的。

此外，关于在线影响力最大化（IM）的实验，详见附录A.2，由于该问题是NP-hard的，使用了（α, β）近似预言机（IMM预言机）。攻击策略涉及一种启发式方法，将目标节点及其在一定距离 $l$ 内的节点组成的“扩展目标集” $S_{ex}$ 之外的边观察到的实现修改为0。这些实验至少重复了5次。这种全面的实验设计，涵盖了不同的CMAB应用和目标配置，使得对理论可攻击性条件的实证验证得以彻底进行。

证据证明的内容

实验证据为本文关于CMAB可攻击性的核心数学主张提供了令人信服且明确的验证，特别是定理 3.6 和推论 3.8 中概述的条件。

对于概率最大覆盖（PMC），如图 2(a) 和 2(b) 所示，攻击成功地迫使CUCB算法随时间线性拉动目标臂，而总攻击成本呈亚线性增长。这种亚线性成本，尽管节点和边数量庞大，但显然是基础臂数量的多项式，直接验证了定理 3.9，该定理指出当 $\Delta_M > 0$ 时，PMC是多项式可攻击的。目标臂拉动次数随亚线性成本的线性增加是攻击机制有效误导CUCB基线的明确证据。对随机目标的攻击表现出更高的方差，暗示了此类场景的内在不可预测性。

同样，对于在线最小生成树（MST）问题（图 2(c) 和 2(d)），总攻击成本保持亚线性，目标臂被线性拉动。这一结果与推论 3.8 完全一致，该推论认为在线MST问题总是可攻击的，因为它们的间隙 $\Delta_M \ge 0$。在针对CUCB基线的实验中，持续的亚线性成本和线性目标臂拉动为该领域可攻击性的理论预测提供了强有力的实证支持。

在线最短路径实验（图 2(e) 和 2(f)）提供了对可攻击和不可攻击实例的至关重要的演示。对于“随机目标”，攻击实现了亚线性成本和线性目标臂拉动，类似于PMC和MST。然而，对于“不可攻击目标”（精心构造的路径，旨在具有鲁棒性），总成本呈线性增长，并且至关重要的是，目标臂拉动几乎保持不变。这种鲜明的对比明确证明了本质上不可攻击的CMAB实例的存在，验证了基于 $\Delta_M$ 条件区分可攻击和不可攻击场景的理论。在这种情况下，CUCB算法并未被欺骗，为可攻击性的极限提供了硬性证据。

在级联老虎机（图 2(g) 和 2(h)）中，攻击成功地诱导了目标臂的线性播放，同时在CascadeKL-UCB、CascadeUCB1和CascadeUCB-V上产生了亚线性攻击成本。这一结果进一步加强了推论 3.8，证实了级联老虎机是多项式可攻击的。在不同基线算法中，目标臂播放次数的持续线性增加和极低的成本，为攻击的有效性提供了可靠的证据。

在线影响力最大化（IM）结果（图 4(a) 和 4(b)）呈现了一个更细致的图景。虽然攻击成本有所下降，但目标节点的播放百分比保持在0，没有明显的选择目标节点增加的趋势。这一结果并未证伪可攻击性，而是凸显了攻击在线IM的难度，并强调了本文关于具有非精确（α-近似）预言机的CMAB实例的可攻击性需要逐实例分析的说法。这表明当前的攻击启发式方法不足以应对IM，但并未排除其内在的可攻击性，从而促使进一步研究。

总而言之，实验通过展示对于 $\Delta_M > 0$ 的实例（PMC、MST、级联老虎机），攻击算法成功地误导了各种基于CUCB的基线，并以亚线性成本和线性目标臂拉动，无情地证明了数学主张。相反，对于 $\Delta_M < 0$ 的实例（某些最短路径配置），攻击失败，导致线性成本和恒定的目标臂拉动，从而提供了攻击性（或不可攻击性）核心机制在现实中起作用的明确、无可辩驳的证据。

局限性与未来方向

尽管本文提出了CMAB可攻击性的开创性表征，但它也公开承认了几项局限性，并提出了令人兴奋的未来研究方向。

一个显著的局限性是，提出的攻击算法（算法 1）在攻击成本方面可能不是最优的。当前的研究结果建立了可攻击性的充分性，但并未保证最低可能成本。一个关键的未来方向是开发更复杂的攻击算法，以实现更低的攻击成本。这还需要建立CMAB实例的攻击成本的理论下界，这是一个有趣且具有挑战性的领域。

另一个关键的讨论领域围绕着已知和未知老虎机环境之间的区别。本文揭示了一个令人惊讶的事实：对于同一个CMAB实例，多项式可攻击性可能因攻击者是否预先了解环境参数（例如，奖励分布）而异。构造的“困难示例”（定理 4.1）展示了一个实例，该实例在已知环境中是多项式可攻击的，但在环境未知时是不可攻击的。这表明，对于黑盒设置中的任何CMAB实例，可能不存在通用的攻击策略。未来的工作应侧重于表征未知环境中CMAB实例的鲁棒性保证，特别是对于间隙 $\Delta_M$ 可以为正或负的最短路径等问题。开发一个通用框架将这些不可攻击的CMAB问题简化为这些困难示例将非常有价值。

此外，当前的可攻击性表征严格限于奖励投毒攻击。作者明确指出，他们的研究结果不能直接推广到其他可能更强大的威胁模型，例如环境投毒攻击（攻击者可以直接改变环境的奖励函数）或动作投毒攻击。未来的研究应将分析扩展到这些替代威胁模型，以提供对CMAB脆弱性的更全面理解。这需要研究不同类型的对抗性扰动如何影响可攻击性条件和成本。

最后，本文的结论强调需要进一步研究概率触发臂对可攻击性的影响。这种基础臂以概率方式触发的机制，为CMAB增加了另一层复杂性。理解其对可攻击性的影响，特别是在具有不同扩散模型的在线影响力最大化等应用中，可能会带来新的见解和更鲁棒的算法。在线影响力最大化（其中攻击策略不明显成功）的初步结果，尤其是在处理近似预言机时，凸显了这一特定研究方向的重要性。

这些前瞻性的讨论，从优化攻击成本到探索不同的威胁模型和环境知识，为旨在开发更鲁棒的CMAB算法并更好地理解其在实际应用中的安全影响的研究人员提供了丰富的议程。

与其他领域的同构性

结构骨架

其核心在于，本文提出了一种机制，通过识别预期结果中的关键“间隙”并随后通过奖励修改加以利用，来量化序列决策系统对目标操纵的脆弱性。

远亲

识别和利用“间隙”来误导决策智能体的基本逻辑，在远离组合多臂老虎机的领域中产生了共鸣。

  1. 目标领域：金融市场操纵检测

    • 联系： 在金融市场中，复杂的算法和人类交易者不断根据观察到的价格信号和市场数据做出序列投资决策。一个长期存在的问题是检测和防止市场操纵，其中攻击者（例如，大型机构交易者）可能会“投毒”市场信号（例如，通过对敲交易、虚假报价或传播虚假谣言），以误导其他市场参与者以人为的价格买卖特定资产。这与本文的问题相呼应：攻击者修改“奖励”（感知资产价值或回报），以迫使“学习智能体”（投资者/算法）为了攻击者的利益而拉动“目标臂”（投资于特定资产）。本文的“间隙”（$\Delta_S$）可以直接转化为衡量操纵者需要多大程度地扭曲资产的感知价值，才能使其比其真实的潜在价值更具吸引力，相对于其他资产。

  2. 目标领域：网络安全（入侵检测/防御系统）

    • 联系： 入侵检测系统（IDS）和入侵防御系统（IPS）在连续的序列决策循环中运行，监控网络流量和系统事件，以识别和响应威胁。网络安全中的攻击者旨在“投毒”观察到的数据（例如，通过注入看起来无害的流量、混淆恶意负载或生成误报）来误导IDS/IPS。目标是规避检测，或迫使系统采取“目标行动”，从而使攻击者受益，例如忽略真实威胁或阻止合法用户。这与CMAB攻击类似，其中攻击者操纵观察到的“奖励”（系统日志、网络数据包）来将“学习智能体”（IDS/IPS）引导至期望的、通常有害的结果。“可攻击性”条件可以反映系统检测逻辑对抗某些数据投毒策略的内在鲁棒性。

如果情况

想象一位金融研究员，也许是监管机构的量化分析师，明天“窃取”了本文的精确方程。具体来说，他们将定义 3.5 中的“间隙”定义 $\Delta_S := r_S(\mu) - \max_{S' \neq S} r_{S'}(\mu \odot O_S)$ 应用于此。

在这个激进的“如果情况”场景中，$r_S(\mu)$ 将代表股票 $S$ 的真实、基本预期回报（可能源自深入的、未被操纵的金融模型），而 $O_S$ 将是该股票可观察到的市场信号集。术语 $\mu \odot O_S$ 将表示基于这些可观察的、可能被操纵的信号的感知预期回报。“间隙” $\Delta_S$ 将量化股票的真实内在价值与其最具吸引力的感知替代品之间的差异。

这将带来一项突破，即主动市场可操纵性指数。与被动调查可疑交易模式不同，监管机构可以使用此指数来识别本质上易受操纵的股票或整个市场板块。如果一只股票持续显示小的正 $\Delta_S$（意味着其真实价值仅比其他选项略好，使其“可攻击”且奖励操纵成本很低），它将被标记。这将允许主动部署有针对性的监控、更严格的交易规则，甚至对这些资产实施临时熔断机制，从而在操纵发生之前就加以阻止。这从根本上改变了市场诚信的维护方式，将范式从法证分析转移到预测性脆弱性评估。

结构通用库

本文为表征序列决策系统中的可攻击性和鲁棒性提出的优雅框架，根植于量化“间隙”的概念，体现了控制战略互动和信息不对称的基本数学结构如何超越特定领域，提供通用的视角来理解各种科学和工程挑战中的脆弱性和弹性。