技术摘要：不耐烦的 Bandit：在无延迟的情况下优化长期目标

1. 问题定义

本文解决了大规模推荐系统中一个关键的挑战：如何在优化长期用户满意度（例如 60 天内的持续参与度）的同时，缓解观察此类奖励时存在的严重延迟问题。在标准的多元 Bandit（MAB）设置中，算法假设反馈是即时的。然而，在像 Spotify 这样的现实平台中，真实的奖励（长期参与度）通常要在显著延迟之后（例如 $d_{max} = 60$ 天）才能被观察到。

等待完整的奖励实现后再更新策略会导致“冷启动”问题，即新内容无法得到有效评估，且学习速率极其缓慢。相反，优化短期代理指标（例如即时点击）往往与长期目标不一致。

作者将其形式化为一个具有渐进式反馈（Progressive Feedback）的 Bandit 问题。与标准的延迟反馈（即在延迟结束前无法获得任何信息）不同，渐进式反馈认为，长期的结果可以通过一系列中间的、相关的结果（例如每日收听活动）随时间推移而变得越来越可预测。核心挑战在于如何利用这些中间信号，在观测到最终长期奖励之前进行有效学习，同时不依赖于“短期信号是完美代理指标”这一假设。

2. 方法论

2.1 模型：具有渐进式反馈的 Bandit

作者定义了一个如下设置：

• 动作（Actions）： 在每个时间步 $t$，向一批用户 $U_t$ 推荐一组有限的项目集合 $\mathcal{A}$。
• 结果（Outcomes）： 为用户 $u$ 选择项目 $a$ 会生成一个结果向量 $Y_u = (Y_u^{(1)}, \dots, Y_u^{(J)})$，代表在 $J$ 天内逐步揭示的参与度指标。
• 奖励（Reward）： 真实奖励 $R(Y_u)$ 是已知轨迹的函数（例如 60 天内的总参与度）。
• 假设：
  • 可交换性（Exchangeability）： 接收相同项目的用户在给定项目特征的条件下，其潜在结果是可交换的。
  • 高斯过程（Gaussian Process）： 潜在结果遵循多元高斯分布。潜在参数 $\theta_a$ 代表项目的真实质量，观测到的结果是 $\theta_a$ 的带噪声实现。
  • 线性奖励（Linear Reward）： 奖励函数 $R(\cdot)$ 是仿射的，确保期望奖励为高斯分布。

2.2 算法：不耐烦的汤普森采样（Impatient Thompson Sampling）

提出的解决方案将汤普森采样（Thompson Sampling）与（经验）贝叶斯滤波器相结合。

1. 先验学习： 利用历史数据，系统拟合关于潜在项目质量参数 $\theta_a$ 的先验分布（具体为以项目特征 $z$ 为条件的均值 $\mu_{1,z}$ 和协方差 $\Sigma_{1,z}$）。这是通过第二类极大似然估计（经验贝叶斯）完成的。
2. 后验更新： 随着中间结果 $Y_u^{(j)}$ 的揭示，算法使用高斯滤波器更新 $\theta_a$ 的后验分布。这使得系统即使在最终奖励尚未观测到时，也能对项目的长期价值保持概率性的信念。
3. 决策制定： 在每一步，算法从当前每个项目的后验分布中采样一个候选 $\theta'_a$，并选择使期望奖励 $R(\theta'_a)$ 最大化的项目。

为了进行理论分析，文中引入了一个“低方差”版本的算法，通过对采样概率进行舍入以确保精确的批次大小，尽管实验结果显示标准版本表现相似。

2.3 理论框架：渐进式反馈的价值（VoPF）

论文引入了一个信息论指标——渐进式反馈的价值（Value of Progressive Feedback, VoPF），用以量化中间信号的效用。

• 定义： VoPF 是在给定延迟结果的情况下，真实长期奖励与渐进式（截断）结果之间的条件互信息。
• 意义： 它衡量了通过观察中间信号可以消除多少关于长期奖励的不确定性。
• 遗憾界（Regret Bound）： 作者推导出了该算法的一个遗憾界，该界与 $\exp(-\text{VoPF})$ 成比例。
  • 如果 VoPF 为零（中间信号不具信息量），则该界回归到标准的延迟奖励遗憾界。
  • 如果 VoPF 较高（信号具有高度预测性），则遗憾值显著降低，实际上允许算法像延迟较短的情况一样进行学习。

3. 核心贡献

1. 形式化了渐进式反馈： 论文区分了“渐进式反馈”（增量揭示、具有预测性的信号）与标准的“延迟反馈”或“完美代理指标”。它为推荐系统背景下的这一现象提供了严谨的模型。
2. 新颖算法： 提出了结合汤普森采样与高斯滤波器的“不耐烦 Bandit”算法，以处理相关的、渐进揭示的结果。
3. 理论保证： 通过由 VoPF 指标控制的新颖遗憾界，证明了只要中间信号具有信息量，该算法即使在长期奖励完全观测之前，也能在早期批次中实现低遗憾。
4. 实证验证：
   • 合成实验： 证明了该算法的表现随信号信息量水平的变化，在定性上符合理论预测。
   • 半合成实验： 使用 Spotify 的播客数据，该算法在累积遗憾方面显著优于基准模型（仅延迟反馈和短期代理指标），尤其是在冷启动场景下。
   • A/B 测试： 在 Spotify 进行的大规模部署中，涉及数亿用户。

4. 结果

4.1 合成与半合成实验

• 减少遗憾： 在合成环境中，不耐烦 Bandit 算法相比于忽略中间反馈的标准汤普森采样算法，显著降低了累积遗憾。这种提升与 VoPF 直接相关。
• 冷启动： 在使用 Spotify 播客数据的半合成实验中，与延迟奖励基准相比，该算法在最初 60 天（延迟期）内积累的遗憾要少得多。
• 先验的重要性： 实验表明，使用基于历史数据拟合的学得先验至关重要；使用无信息先验会导致性能与延迟奖励基准相当。
• 非平稳性： 在可用项目集频繁变化（模拟持续内容发布）的设置中，渐进式反馈算法保持了低遗憾，而延迟算法则无法快速适应。

4.2 A/B 测试结果 (Spotify)

该方法在 Spotify 移动应用的“你可能喜欢的节目”栏目中进行了测试，用于对播客推荐进行排序。

• 处理组 vs. 控制组： 处理组策略利用渐进式反馈来估计新节目的“粘性”（长期参与度），而控制组策略则依赖于延迟奖励（等待 60 天获取数据）。
• 对新内容的影响： 对于最近发布的节目，处理组策略将发现率提高了近 30%，并将每曝光次的 60 天活跃天数提高了 50% 以上（对比控制组）。
• 整体影响： 在所有节目中，处理组实现了 60 天活跃天数 7% 的增长 以及 每曝光次 60 天分钟数 >10% 的增长。
• 权衡： 这些长期收益伴随着短期发现率（即时点击）略微下降（具有统计学显著性），这证实了算法成功地将重心从短期代理指标转向了长期价值。
• 部署： 基于这些结果，该方法被推广到为数亿用户提供个性化播客推荐的流程中。

5. 重要性与主张

论文声称其主要贡献在于解决了推荐系统中学习速度与长期对齐之间的权衡。通过形式化“渐进式反馈”，作者证明了只要中间信号具有预测性，就可以在不等待完整奖励周期的情况下优化长期目标。

作者强调，其方法与现有的代理结果（surrogate outcome）文献不同，原因在于：

1. 它不假设中间结果是完美的代理指标。
2. 它处理大量连续、顺序揭示的中间信号（例如 >50 个每日指标），而非单一的二元结果。
3. 它通过贝叶斯滤波显式地建模了随时间推移的不确定性减少。

这项工作验证了利用渐进式反馈可以为工业级大规模系统带来实质性改进，特别是解决了由于缺乏历史长期数据而导致的新内容冷启动问题。作者指出，算法的成功依赖于能够从历史数据中学习准确先验的能力，这是通过经验贝叶斯拟合来解决的一个实际需求。