面向推荐系统的 Bandit 方法

中文精读

原文约 3,154 词 · 14 节

1. 站点导航菜单（原文第 1 节）

   • 原文开头是一个导航菜单，列出五个指向站点其他页面的链接。
   • 五个栏目依次为：Start Here（从这里开始）、Writing（写作）、Speaking（演讲）、Prototyping（原型开发）、About（关于）。

2. ε-greedy、UCB 与 Thompson Sampling（原文第 3 节）

   • 先统一定义：action/arm 是推荐候选；reward 是单次试验中的用户互动（如点击、购买）；value 是某 arm 在多次试验中的估计长期回报；policy 是根据已学 value 选择动作的算法/智能体。
   • ε-greedy 是经典 bandit 算法：每次试验以概率 ε 随机选动作，以 1-ε 贪婪选价值最高的动作；ε 越大探索越多，越小利用越多。
   • ε-greedy 的缺点是可能探索超过必要程度（可通过随时间降低 ε 缓解），且不指导该探索哪些物品，默认对所有物品均匀随机探索。
   • Upper Confidence Bound（UCB）考虑 arm 的不确定性，选择潜力最大的 arm；不确定性用置信界（confidence bounds）建模，潜力由上置信界代表，故常被称为“面对不确定性时的乐观主义”。
   • 图中 Qt(a) 是 arm a 在时间步 t 的估计价值，Nt(a) 是被选次数，c 是置信参数（默认 1）；绿臂被选频繁、置信界窄，红臂被选少、置信界宽，因此即使绿臂估计价值更高，红臂的 UCB 更高而被选中，随着红臂被选增多其 UCB 会降到绿臂之下。
   • Thompson Sampling 用历史回报构建概率分布并以采样选动作；回报为二元时用 Beta 分布，参数 α、β 的均值为 α/(α+β)，可理解为成功数/(成功数+失败数)；对每个 arm 的 Beta 分布采样，选采样值最高者。

3. ε-greedy、UCB 与 Thompson Sampling（原文第 3 节）（续）

   • 数据越多 α、β 越大，Beta 分布越窄，对 arm 价值的估计越确定；分布越窄，采样值越靠近均值，从而减少探索、增加利用。

4. 推荐系统中 bandits 的工业实例（原文第 4 节）

   • ε-greedy 例：Spotify 的 recplanations（为音乐推荐生成解释）因实现简单、支持倾向性打分（propensity scoring）而采用 ε-greedy；为限制探索对体验的负面影响，先用类似 YouTube 论文候选生成阶段的 embedding 模型预选 100 个最相关物品作为探索范围。
   • Schibsted 的多臂老虎机排序器（multi-armed bandit ranker）对多个子推荐器的候选重排，每次输入额外加入 5% 随机物品，以防训练陷入局部最优。
   • UCB 经典例：Yahoo 新闻推荐的 LinUCB，用岭回归（ridge regression）线性估计 arm 特征上的回报，UCB 由预测回报加上岭回归标准差得到；混合版还使用所有 arm 共享的特征（如新闻类别），实验显示共享特征可跨多篇文章学习并利用 CTR 信息。
   • 阿里巴巴的 LinUCB 物品推荐引入用户浏览模型（user browsing model）加入位置权重，以缓解对用户互动影响很大的位置偏差（尤其在移动端）；奖励更新同时考虑 arm 特征与浏览概率，同样用岭回归和标准差计算 UCB。
   • Thompson Sampling 例：Doordash 的菜系推荐用 Beta(α=该菜系订单数, β=其他菜系订单数) 建模用户偏好；在探索页选择菜系过滤器时，对每个菜系采样并按降序排序取前几名展示。
   • Yahoo 的广告与新闻推荐 bandit 学习带正则的逻辑回归预测 CTR，模型权重后验用高斯分布表示，每次试验各权重从高斯后验独立抽取后再预测回报。

5. 推荐系统中 bandits 的工业实例（原文第 4 节）（续）

   • Amazon 的多变量 bandit 优化页面布局同样从独立高斯分布表示并采样权重；因布局组合使决策空间过大，用贪婪爬山法近似 argmax 而非穷举，并加入随机重启以缓解次优解。
   • Twitter 广告推荐用深度学习建模不确定性，比较了 bootstrapping 与 dropout：前者需划分/存储数据掩码、训练多个网络并多次前向，成本高，故改用共享底层、各数据子集走不同头的多头网络；后者用不同 dropout 单元多次前向预测价值，相当于从后验采样。
   • 最终架构把 dropout 层放在倒数第二层：后验采样时底层只算一次，再并行多次通过 dropout 层；dropout 层为每条数据提供掩码，无需显式划分数据集，也充当多头网络的头。

6. 工业应用 bandits 的经验教训（原文第 5 节）

   • 其一，UCB 与 Thompson Sampling 优于 ε-greedy：ε-greedy 默认无引导、均匀随机选动作；UCB 与 Thompson Sampling 由置信界与概率分布引导，且随尝试增多而收窄，能更聪明地探索不确定性高的 arm，因此后悔值更低。
   • 其二，反馈延迟时 Thompson Sampling 优于 UCB：现实中因资源与运行时限制，用户—物品互动常不能即时处理。
   • 延迟情况下，UCB 确定性选臂，在新反馈纳入前会一直选同一动作；Thompson Sampling 从后验随机采样，即使奖励未更新也会在动作间随机化，Yahoo 与 Deezer 都观察到这带来更广探索和更好结果。
   • Yahoo 模拟了 10、30、60 分钟的更新延迟：Thompson Sampling 在各延迟下都有竞争力；UCB 在 10 分钟短延迟时优于 Thompson Sampling，但延迟增至 30 和 60 分钟时表现更差。
   • 总体说明随机化策略对延迟更稳健，因它们在奖励未更新时仍持续探索。
   • 其三，bandit 的初始化方式有影响：Deezer 发现悲观初始化优于朴素初始化；Thompson Sampling 中朴素初始化为先验 Beta(1,1)，悲观初始化为先验 Beta(1,99)，UCB 也采用类似的朴素与悲观初始化。

7. 工业应用 bandits 的经验教训（原文第 5 节）（续）

   • Deezer 认为悲观初始化更好，是因为其先验概率更低，更贴近真实世界的回报。

8. 探索新物品的两种方案（原文第 6 节）

   • 讨论探索的少数论文采用两类做法：在有限用户上做大规模探索，或在所有用户上做小规模探索。
   • 前者：Yahoo 用探索桶（exploration bucket），随机把用户选入桶中，桶内用户被均匀随机地分发新闻文章；Twitter 的随机广告策略把 1% 的生产流量用于随机投放。
   • 后者：Netflix 在所有用户上测试新封面图，其说法是探索带来的后悔值通常很小，并由庞大用户基数分摊，每位成员只用一小部分目录帮提供反馈；Schibsted 也在 bandit 排序器的每次输入中加入 5% 随机物品。

9. 应对维度灾难（原文第 7 节）

   • 可用性别、年龄段、位置、行为等特征表示用户，但以这些特征为条件的 bandit 面临维度灾难（curse of dimensionality）：维度越多，每个维度组合可分到的数据越少。
   • Yahoo 在 LinUCB 学习策略前先用 PCA 降维：原有 1.2k 用户特征（人口统计、地理位置、行为）和 83 个文章特征（基于 URL 类别与编辑类别）。
   • Yahoo 把用户特征投影到文章特征上，再将用户聚为五组、使组内偏好相似，从而把 1.2k 用户特征降为 5 个；文章特征也以类似方式降维。
   • Deezer 比较了用聚类表示用户的半个性化与用用户特征的全个性化：半个性化用 k-means 按历史行为把用户聚为 100 组，得到音乐口味相似的群体，并为每个聚类单独训练 bandit。
   • 全个性化用 97 维向量概括用户对流派、心情、国家等的偏好，向量来自用户—歌曲互动矩阵分解，再在这些特征上训练 contextual bandit。
   • 结果是半个性化优于全个性化：按用户聚类训练的 bandit 各自收到更多反馈，因而学得更有效、更快排出播放列表。

10. 热启动 bandits 以改善用户体验（原文第 8 节）

    • 为保证 bandit 从第一次交互起就能提供良好体验，通常用以往记录的用户互动来热启动（warm-start）。
    • Doordash 用更高层级的区域数据热启动菜系 bandit：对每个菜系在区域、子区域、用户等多个层级学策略；顶层 bandit 初始化为 Beta(1,1)。
    • 每往下一层，用该层级该菜系的平均订单数加到 α、其他菜系的平均订单数加到 β；最后用户层再用用户自身订单数据更新 α、β。
    • 这样新用户的菜系 bandit 会先用更高层面的市场数据热启动，随后每次下单再用个人偏好更新。
    • 另一种方式是用随机策略收集的数据热启动用户偏好：Yahoo 先用随机数据学用户级 CTR 估计，再将其加到无上下文 CTR 估计中，发现热启动的 bandit 胜过无上下文 bandit。
    • 作为随机数据的替代，有论文提出通过对生产策略记录的数据做重要性加权（importance weighting）来热启动，权重需知生产策略（各动作概率）；该文用经验估计得到生产策略：统计每个广告在每页出现的次数，再用该估计对记录事件加权。

11. 热启动 bandits 以改善用户体验（原文第 8 节）（续）

    • 贪婪策略收集的数据也有助于热启动：Twitter 用贪婪策略数据热启动 bandit，并发现热启动更多轮（500 对比 100）在测试集上指标更好。

12. 用离策略评估评价 bandits（原文第 9 节）

    • 多个 bandit 实现（如 Netflix、Yahoo）引用 Li 等人的回放法（replay method）做离策略评估（off-policy evaluation）。
    • 回放法假设：单个事件独立同分布，且记录策略对每个 arm 均匀随机选择；文中指出后一假设可放宽为任意随机化策略，不限于均匀随机（原作者的理​​解是需要随机以保证足够支撑）。
    • 评估时输入待评新策略与记录的策略事件：若新策略所选动作与记录策略一致，该事件被加入历史并更新回报；否则丢弃事件、不更新回报。
    • 逆倾向打分（Inverse Propensity Scoring）的反事实评估是另一种替代方案。
    • Twitter 论文比较了两种指标：标准测试集上的 PR-AUC，以及相对随机策略的 CTR 提升；两者之间存在权衡。
    • 贪婪策略 PR-AUC 好但 CTR 相对差；UCB、Thompson Sampling 等 bandit 策略 PR-AUC 较差但 CTR 超过贪婪策略。

13. 用离策略评估评价 bandits（原文第 9 节）（续）

    • 这说明在有偏记录数据上用常规指标评价良好的监督学习，可能在实际关心的指标（如 CTR、转化）上表现并不好。

14. 结语与参考文献（原文第 9 节末与第 10 节）

    • 作者指出本文比平均篇幅长得多，并希望读者认为 bandits 是推荐系统的可行替代方案。
    • 其核心在于建模不确定性并刻意探索，因此在数据少、对用户—物品偏好确定性低时有效。
    • 作者在结尾询问读者是否知道其他基于 bandit 的推荐系统工业实现，并邀请在评论区分享。
    • 参考文献列出 13 项。
    • 包括 Netflix 封面图个性化、Doordash 个性化菜系过滤器、Yahoo 上下文 bandit 新闻推荐、从记录隐含探索数据学习、Spotify 可解释推荐个性化、音乐流媒体多目标 bandit 优化、音乐 App 轮播个性化、移动推荐上下文浏览 bandit、实时多变量优化高效 bandit、深度贝叶斯 bandit、在线实验中的深度神经网络市场推荐器、Thompson Sampli…
    • 以及上下文 bandit 新闻推荐的离线无偏评估。