1. 论文基本信息

1.1. 标题

Bandits with Ranking Feedback (带排名反馈的多臂老虎机)

1.2. 作者

Davide Maran, Francesco Bacchiocchi, Francesco Emanuele Stradi, Matteo Castiglioni, Nicola Gatti, Marcello Restelli

• 机构: Politecnico di Milano (米兰理工大学)

1.3. 发表期刊/会议

NeurIPS 2024 (Neural Information Processing Systems)

• 影响力: 机器学习与人工智能领域的顶级会议，享有极高的学术声誉。

1.4. 发表年份

2024

1.5. 摘要

本文提出了一种名为“带排名反馈的老虎机”的新型多臂老虎机（Multi-Armed Bandits, MAB）变体。与传统老虎机提供数值奖励不同，该变体向学习者提供基于历史拉动情况的臂的排名，而不量化具体的性能差异。这种反馈适用于无法精确测量数值奖励（如金钱、概率）的场景，例如涉及人类偏好的匹配问题。 论文研究了在随机 (Stochastic) 和 对抗 (Adversarial) 环境下的无遗憾算法设计问题。

• 随机环境: 证明了在实例相关（Instance-dependent）情况下，不可能实现对数级的遗憾界（Logarithmic Regret），这与传统老虎机不同。作者提出了两种算法：
  • DREE: 实现了超对数（Superlogarithmic）遗憾，匹配了下界。
  • R-LPE: 在实例无关（Instance-independent）情况下保证了 $\tilde{\mathcal{O}}(\sqrt{T})$ 的遗憾。
  • 权衡: 证明了没有任何算法能同时在实例相关和实例无关两种情况下达到最优。
• 对抗环境: 证明了不可能实现次线性（Sublinear）遗憾，即遗憾会随时间线性增长。

1.6. 原文链接

https://proceedings.neurips.cc/paper_files/paper/2024/file/936ce22b767cf1a1496083e4725d3b21-Paper-Conference.pdf

---

2. 整体概括

2.1. 研究背景与动机

• 核心问题: 在经典的多臂老虎机（MAB）问题中，学习者每次拉动手臂（Arm）都会收到一个具体的数值奖励（例如 0.8 或 $100）。然而，在许多现实场景中，这种精确的数值反馈是不可得的。
• 重要性与挑战:
  • 人类反馈: 例如在约会匹配或推荐系统中，用户可能无法给出一个具体的“喜爱度分数”，但可以很容易地对展示的选项进行排名（例如“我更喜欢 A 而不是 B”）。
  • 隐私与安全: 在某些在线广告竞价中，出于隐私保护，平台可能只透露排位而不透露具体的点击率或收入数值。
  • 理论空白: 现有的理论高度依赖数值奖励来估计均值和置信区间（如 UCB 算法）。如果剥离了数值，仅保留排名信息，我们还能有效地学习吗？这种信息的缺失对学习效率（遗憾界）有多大影响？
• 创新点: 本文首次形式化定义了“基于历史平均奖励排名的反馈”这一模型，并深入探究了数值奖励在老虎机理论中的必要性。

2.2. 核心贡献与主要发现

1. 模型定义: 提出了 Bandits with Ranking Feedback 模型。关键区别在于，反馈不是瞬时的胜负（如 Dueling Bandits），而是基于历史经验均值的全局排名。
2. 随机环境下的下界: 证明了在这种反馈下，不可能像标准 MAB 那样获得 $O(\log T)$ 的遗憾界。这意味着排名反馈比数值反馈包含的信息量显著更少。
3. 算法设计:
   • 提出了 DREE 算法，通过超对数探索策略，达到了理论最优的实例相关遗憾界。
   • 提出了 R-LPE 算法，利用“对数网格”和“过滤条件”，在实例无关情况下打破了 $O(T^{2/3})$ 的屏障，达到了 $\tilde{\mathcal{O}}(\sqrt{T})$（针对高斯奖励）。
4. 不可能性结果:

   • 证明了算法无法“既要又要”：不可能同时拥有最优的实例相关遗憾和实例无关遗憾。

   • 证明了在对抗环境下，如果奖励是恶意设定的，学习者甚至无法获得次线性遗憾（即无法学到任何东西）。

     ---

3. 预备知识与相关工作

3.1. 基础概念

为了理解本文，初学者需要掌握以下概念：

• 多臂老虎机 (Multi-Armed Bandits, MAB): 一个序贯决策模型。你有 $K$ 个手臂，每次拉动一个，获得一个奖励。目标是最大化累积奖励（或最小化遗憾）。
• 遗憾 (Regret, $R_T$): 衡量算法性能的核心指标。定义为“最佳动作的期望总奖励”减去“算法实际获得的期望总奖励”。
  • 次线性遗憾 (Sublinear Regret): 如果 $\lim_{T \to \infty} R_T / T = 0$，说明算法平均来看收敛到了最优策略。
• 实例相关 vs. 实例无关 (Instance-dependent vs. Independent):
  • 实例相关界: 遗憾界依赖于具体问题的参数（如最优臂和次优臂的奖励差 $\Delta$）。通常形式为 $O(\frac{1}{\Delta} \log T)$。差距越大，越容易区分，遗憾越小（但系数大）。
  • 实例无关界: 遗憾界不依赖具体 $\Delta$，只依赖时间 $T$ 和臂数 $n$。通常形式为 $O(\sqrt{nT})$。这是最坏情况下的保证。
• 经验均值 (Empirical Mean): 某个臂在过去被拉动的所有次中获得的奖励平均值。

3.2. 前人工作

• 偏好学习 (Preference Learning): 研究如何从排序或比较中学习。本文属于这一范畴，特别是从“完全排名”中学习。

• 对决老虎机 (Dueling Bandits):

  • 区别分析: 这是一个非常容易混淆的概念。在 Dueling Bandits 中，学习者在每一轮选择两个臂，并观察它们当次的胜负（即 $r_t(i) > r_t(j)$）。
  • 本文模型: 学习者观察的是基于至今为止所有拉动计算出的经验均值的排名。换句话说，反馈是累积性的，而不是瞬时的。这使得本文的模型更偏向于利用长期统计信息，而非单次比较的噪声。

• 探索-利用困境 (Explore-then-Commit, EC): 一种基础策略，先纯探索一段时间，然后一直选最好的。本文将 EC 算法作为基线（Baseline）进行比较。

  ---

4. 方法论

4.1. 方法原理

本文的核心挑战在于：没有数值奖励，我们无法计算置信区间（Confidence Bounds）。 在标准 UCB 算法中，我们知道“均值大约是 0.5 $\pm$ 0.1”。但在排名反馈中，我们只知道“臂 A 的均值 > 臂 B 的均值”。我们不知道大多少。

• 直觉: 如果臂 A 的真实均值只比臂 B 大一点点（Gap $\Delta$ 很小），那么即使拉动很多次，它们的经验均值排名也可能频繁交替。如果 $\Delta$ 很大，排名会很快稳定。
• 理论障碍: 作者利用随机游走 (Random Walk) 理论证明，仅凭排名变化，很难快速区分两个均值非常接近的臂，因此需要比标准 MAB 更多的探索。

4.2. 核心方法详解

4.2.1. 问题设定与反馈机制

在每一轮 $t$，学习者选择一个臂 $i_t$。 环境根据该臂的分布 $\nu_{i_t}$ 生成奖励 $r_t(i_t)$，但学习者看不到这个数值。 学习者看到的是所有臂的经验均值的排名。经验均值定义为： $$\hat { r } _ { t } ( i ) : = \frac { \sum _ { j \in \mathcal { W } _ { t } ( i ) } r _ { j } ( i ) } { Z _ { i } ( t ) }$$ 其中 $\mathcal { W } _ { t } ( i )$ 是臂 $i$ 被拉动的时间步集合，Z _ { i } ( t ) 是被拉动的次数。 学习者观察到的排名 $\mathcal { R } _ { t }$ 满足：如果 $\hat { r } _ { t } ( i ) \geq \hat { r } _ { t } ( j )$，则 $i$ 在排名中优于 $j$。

4.2.2. 算法 1: DREE (Dynamical Ranking Exploration-Exploitation)

该算法旨在解决实例相关（Instance-dependent）的遗憾最小化问题。

步骤解析:

1. 初始化: 前 $n$ 轮，每个臂各拉一次。
2. 探索函数定义: 定义一个超对数函数 f(t)，例如 $f(t) = \log(t)^{1+\delta}$，其中 $\delta > 0$。这个函数决定了探索的频率。注意，这比标准的 $\log(t)$ 探索要多，这是为了弥补数值信息的缺失。
3. 循环决策 (For $t = n+1$ to $T$):
   • 强制探索: 检查是否存在任何臂 $i$，其被拉动的次数 $Z_i(t-1)$ 小于 f(t)。
   • 执行: 如果有这样的臂，拉动它（如果有多个，任选一个）。
   • 利用 (Exploitation): 如果所有臂都已被拉动至少 f(t) 次，则拉动当前排名第一（即经验均值最高）的那个臂 $\mathcal { R } _ { t - 1 , 1 }$。
   • 更新: 观察新的排名反馈 $\mathcal { R } _ { t }$。

理论保证: 定理 2 指出，DREE 算法的遗憾上界为： $$R _ { T } \leq ( 1 + f ( T ) ) \sum _ { i = 1 } ^ { n } \Delta _ { i } + \log ( T ) \sum _ { i = 1 } ^ { n } C ( f , \Delta _ { i } )$$ 其中 $\Delta_i$ 是次优臂 $i$ 与最优臂的差距。这个界限主要由 f(T) 主导，因此遗憾是超对数的（Superlogarithmic），这与作者证明的下界相匹配。

4.2.3. 算法 2: R-LPE (Ranking Logarithmic Phased Elimination)

该算法旨在解决实例无关（Instance-independent）的遗憾最小化问题，特别是针对高斯奖励。它采用了一种基于“淘汰”的策略。

核心组件:

1. 对数网格 (Loggrid, $\mathcal{L}$): 算法并不在每一步都做决策，而是在特定的时间点（检查点）进行评估。这些时间点构成一个集合 $\mathcal{L}$，其密度随时间呈对数增长。 $$L G ( a , b , T ) : = \left\{ \lfloor T ^ { \lambda _ { j } b + ( 1 - \lambda _ { j } ) a } \rfloor : \lambda _ { j } = \frac { j } { \lfloor \log ( T ) \rfloor } , \forall j = 0 , \ldots , \lfloor \log ( T ) \rfloor \right\}$$ 这个定义看似复杂，其核心思想是创建一个时间序列，使得我们在 $T^{1/2}$ 到 $T$ 之间有对数数量级的检查点。

2. 活跃集 (Active Set, $S$): 初始包含所有臂。随着时间推移，表现差的臂会被剔除。

3. 过滤条件 (Filtering Condition): 这是算法的灵魂。

   • 定义公平时间步 (fair timestep): 指所有活跃臂被拉动次数相同的时间点。
   • 在公平时间步，如果臂 $i$ 在过去所有的公平时间步中，排名高于臂 $j$ 的次数超过了某个阈值 $\zeta$，则认为 $i$ 显著优于 $j$。
   • 具体操作: 当所有活跃臂的拉动次数达到 Loggrid 中的某个值时，执行淘汰逻辑：保留那些在历史排名中表现足够好的臂，剔除其他的。

算法流程:

1. 初始化活跃集 $S = [n]$，初始化 Loggrid $\mathcal{L}$。
2. 在每一轮 $t$：
   • 选择 $S$ 中被拉动次数最少的臂 $i_t$（以保持拉动次数平衡）。
   • 更新拉动次数 $Z_{i_t}$，观察排名 $\mathcal{R}_t$。
   • 检查淘汰: 如果所有活跃臂的最小拉动次数达到了 $\mathcal{L}$ 中的下一个检查点：
     • 计算阈值参数 $\alpha$。
     • 根据过滤条件更新 $S$，移除那些在历史排名比较中输得太多的臂。

理论保证: 定理 4 证明了在高斯噪声假设下，R-LPE 的遗憾上界为： $$R _ { T } \leq 6 2 n ^ { 4 } \log ( T ) ^ { 2 } T ^ { 1 / 2 }$$ 忽略对数项和常数项，这达到了 $\tilde{\mathcal{O}}(\sqrt{T})$ 的遗憾界，打破了简单探索策略（Explore-Then-Commit）的 $O(T^{2/3})$ 瓶颈。证明过程极具技术性，涉及将随机游走离散化为布朗运动来分析。

---

5. 实验设置

5.1. 数据集

• 类型: 合成数据集 (Synthetic Data)。
• 生成方式: 奖励从单位方差（$\sigma^2=1$）的高斯分布中采样。
• 规模: 时间视界（Time Horizon）$T = 2 \cdot 10^5$。
• 实验环境: 模拟了四种不同的奖励配置（Instances），涵盖了臂的数量 $n$ 从 4 到 8 不等，以及最小差距 $\Delta_{\min}$ 从小 (0.03) 到大 (0.5) 的不同情况。

5.2. 评估指标

• 累积遗憾 (Cumulative Regret):
  • 概念定义: 衡量算法在 $T$ 时间内，因为没有一直选择最优臂而损失的总奖励。
  • 数学公式: $$R _ { T } ( \pi ) = \mathbb { E } \left[ \sum _ { t = 1 } ^ { T } r _ { t } ( i ^ { * } ) - r _ { t } ( i _ { t } ) \right]$$
  • 符号解释:
    • $\mathbb { E }$: 期望值。
    • $T$: 总时间步数。
    • $r _ { t } ( i ^ { * } )$: 最优臂 $i^*$ 在 $t$ 时刻的奖励。
    • r _ { t } ( i _ { t } ): 算法选择的臂 $i_t$ 在 $t$ 时刻的奖励。

5.3. 对比基线

• Explore-Then-Commit (EC):

  • 原理: 在前 $m \cdot n$ 轮均匀拉动每个臂（纯探索），之后一直拉动经验均值最高的臂（纯利用）。

  • 代表性: 这是处理无法获取置信区间（如排名反馈）场景的最简单、最直观的基线算法。理论上它能达到 $O(T^{2/3})$ 的遗憾。

    ---

6. 实验结果与分析

6.1. 核心结果分析

实验结果清晰地展示了两种算法在不同场景下的优势。

1. 小差距场景 (Small Gaps, $\Delta_{\min} = 0.03$):

   • 现象: 如下图 (Figure 1 & 2) 所示，当最优臂和次优臂非常接近时，DREE 算法表现不佳，其遗憾呈线性增长趋势。
   • 原因: DREE 的遗憾界依赖于 $1/\Delta$，当 $\Delta$ 很小时，常数项爆炸，且超对数探索 f(t) 导致即使在后期也进行大量探索。
   • R-LPE 的优势: 相比之下，R-LPE (紫色线) 表现出显著更低的遗憾，且曲线斜率随时间降低（次线性）。这验证了其 $\sqrt{T}$ 的实例无关界在困难问题上的鲁棒性。

2. 大差距场景 (Large Gaps, $\Delta_{\min} \ge 0.25$):

   • 现象: 如下图 (Figure 3 & 4) 所示，当差距较大时，DREE (橙/绿线) 迅速收敛，表现优于 R-LPE 和 EC。

   • 参数影响: 对于 DREE，参数 $\delta$ 越小（即 f(t) 越接近 $\log t$），表现越好。$\delta=1.0$ 的版本在简单任务中几乎是瞬间锁定最优臂。

     以下是原文 Figure 1 的结果（描述）：

Figure 1: 在 $\Delta_{\min} = 0.03$ 且所有 Gap 都很小的实例中。EC (蓝色) 遗憾较高。DREE (不同 $\delta$) 遗憾呈现线性上升，表现最差。R-LPE (紫色) 遗憾最低，显著优于其他算法，证明了其在困难实例下的有效性。

以下是原文 Figure 3 的结果（描述）：

Figure 3: 在 $\Delta_{\min} = 0.5$ 的简单实例中。R-LPE (紫色) 和 EC (蓝色) 表现尚可。但 DREE ($\delta=1.0$, 橙色) 表现极其出色，遗憾值极低且平稳，证明在容易区分的场景下，基于排名的贪婪策略配合适度探索是非常高效的。

6.2. 总结表 (Summary of Performance)

---

7. 总结与思考

7.1. 结论总结

这篇论文对“带排名反馈的老虎机”问题进行了开创性的理论研究。

1. 理论突破: 揭示了数值奖励的缺失使得问题本质上变得更难——我们失去了实现 $O(\log T)$ 遗憾的能力。
2. 算法贡献: 提出了两套互补的算法：DREE 适用于“简单”问题（大 Gap），R-LPE 适用于“困难”问题（小 Gap），分别在实例相关和实例无关的设定下达到了理论最优或接近最优的界。
3. 不可能性: 证明了在对抗性环境中，仅靠排名反馈无法学习（遗憾是线性的），这凸显了该反馈机制的脆弱性。

7.2. 局限性与未来工作

• R-LPE 的高斯假设: R-LPE 的理论分析强烈依赖于高斯噪声假设（利用布朗运动性质）。对于其他分布（如伯努利分布），虽然直觉上可能有效，但缺乏理论保证。这是论文明确指出的一个局限。
• 对数网格的复杂性: R-LPE 算法实现和分析都相对复杂，特别是过滤条件的计算。
• 对 $n$ 的依赖: R-LPE 的遗憾界中包含 $n^4$，这意味着当臂的数量很大时，算法性能可能会显著下降。

7.3. 个人启发与批判

• 信息的价值: 这篇论文通过反证法精彩地展示了“数值 magnitude”在学习中的价值。失去数值不仅仅是失去精度，而是改变了收敛速度的阶数（从 $\log T$ 到超 $\log T$ 或 $\sqrt{T}$）。
• 排名的定义: 本文定义的排名是基于“经验均值”的。这在实际系统中可能需要存储所有历史数据，计算成本较高。相比之下，Dueling Bandits 的瞬时比较反馈可能更“轻量级”，但本文模型利用了更多历史信息，理论上更稳定。
• 应用场景思考: 在设计涉及人类反馈的系统（如 RLHF）时，如果只收集排名数据，我们必须意识到模型收敛速度的理论上限会降低。这提示我们或许可以尝试混合反馈机制（大部分排名 + 少量数值打分）来打破这一限制。