Active Context Selection Improves Simple Regret in Contextual Bandits

技术摘要：主动上下文选择改善上下文多臂老虎机中的简单遗憾

问题表述
本文研究了有限上下文空间内的上下文多臂老虎机问题，其中上下文代表不同的子群体（例如人口统计群体）。学习目标由上下文加权简单遗憾定义：在固定的实验预算 $T$ 之后，学习者必须为每个子群体推荐一个最佳处理方案。性能指标是最佳处理方案与推荐处理方案之间期望差距的加权和，权重为 $k$ 个子群体上的人口分布向量 $p$。

本研究区分了两种采样机制：

1. 被动采样：上下文根据固定分布 $p$ 随机揭示，学习者仅选择处理方案。
2. 主动采样：学习者可以在每一轮主动选择子群体（上下文）和处理方案。

分析假设奖励分布处于最坏情况设定，但在上下文分布 $p$ 方面是实例依赖的。本文聚焦于“数据丰富”机制，即时间视界 $T$ 显著大于处理方案数量 $n$、上下文数量 $k$ 以及最小上下文概率的倒数。

方法论与理论框架

• 已知 $p$ 的最优分配：
  当子群体分布 $p$ 已知时，作者刻画了实验预算的最优分配。他们证明，对于最坏情况下的简单遗憾标准，无历史策略（即上下文选择仅取决于 $p$ 而不依赖于观测历史）足以达到极小极大速率。

  • 被动速率：在被动采样下，遗憾规模为 $\Theta(\sqrt{\frac{n}{T}} \|p\|_{1/2})$。
  • 主动速率：在主动采样下，最优策略以与 $p_j^{2/3}$ 成正比的概率将样本分配给子群体 $j$。这实现了 $\Theta(\sqrt{\frac{n}{T}} \|p\|_{2/3})$ 的遗憾速率。
  • 差距：主动采样相对于被动采样的改进因子由比率 $R(p) = \|p\|_{1/2} / \|p\|_{2/3}$ 刻画。作者表明，对于高度非均匀的分布，该差距可高达 $\Theta(k^{1/4})$。最优的主动分配将采样概率向比 $p$ 更均匀的分布转移，从而增加对较小子群体的探索。

• 预算干预：
  本文将分析扩展到主动采样成本高昂的场景，允许学习者仅在 $\alpha$ 比例的轮次中选择子群体。作者构建了一个约束优化问题，以在满足分配 $q$ 必须满足 $q_j \geq (1-\alpha)p_j$ 的约束下最小化遗憾。他们推导出了最优分配的阈值结构：如果预算不足以改善那些 $p_j$ 较大的子群体，它们可能保持其被动分配，而其他子群体则被提升至接近 $p_j^{2/3}$ 的比例。他们确定了恢复完全主动最优速率所需的最小预算 $\alpha_{\min}(p)$。

• 未知 $p$（EETC 算法）：
  当 $p$ 未知时，完全主动策略不能简单地采用 $p^{2/3}$ 规则。作者提出了**探索 - 探索 - 然后承诺（EETC）**算法，该算法平衡了三个阶段：

  1. 初始被动探索：学习者被动行动以估计 $p$。
  2. 持续被动采样：学习者继续被动采样，直到剩余预算足以基于当前估计实施最优主动分配。
  3. 承诺：学习者切换到主动采样，利用估计的分布分配剩余轮次。
     理论分析表明，对于较大的时间视界，EETC 实现了与已知 $p$ 的最优完全主动策略相同的简单遗憾速率（相差常数因子）。

关键结果与实验

• 理论保证：本文建立了已知和未知 $p$ 情况下的紧确遗憾速率。它证明了主动上下文选择严格优于被动采样，且改进幅度取决于上下文分布的异质性。
• 合成实验：合成数据上的实验证实，随着子群体数量 $k$ 的增加，被动策略与主动策略之间的遗憾差距扩大，这与理论上的 $\Theta(k^{1/4})$ 界限一致。EETC 算法显示出与神谕（已知 $p$）主动策略的性能高度吻合。
• 真实世界数据（MovieLens）：作者在 MovieLens 1M 数据集上评估了他们的方法，将电影推荐视为处理方案，将人口统计群体视为子群体。结果表明，被动策略产生的遗憾最高。已知 $p$ 的主动策略和 EETC 均显著优于被动基线，且随着时间视界的增加，EETC 的性能趋近于神谕主动策略。

意义与主张
本文声称量化了在实验设计和策略学习中主动选择子群体的具体价值。其主要贡献在于证明主动子群体选择总是优于被动采样，且当人口分布偏斜时，增益尤为显著。

作者强调，他们的工作弥合了标准上下文老虎机（其中上下文是环境性的）与实验设计（其中实验者控制样本）之间的鸿沟。通过刻画最优分配规则（$q_j \propto p_j^{2/3}$）并提供一种适应未知分布且不牺牲渐近最优性的算法（EETC），本文为异质群体中的高效资源分配提供了严谨的框架。该研究表明，在可行进行针对性招募或受控采样的场景中，忽视选择上下文的能力会导致次优的处理方案推荐。