主动选择上下文可显著降低推荐系统的误差，尤其在数据分布不均时效果更明显。
Active Context Selection Improves Simple Regret in Contextual Bandits
- 通过主动选择要采样的上下文，优化样本分配策略
- 相比随机采样，误差率降低至原水平的 $\Theta(k^{1/4})$
- 适用于需要高效利用数据的个性化推荐场景
研究有限上下文空间下的上下文多臂赌博机问题，学习者需为每个上下文推荐最优动作，并按上下文加权简单遗憾进行评估。在最坏情况下的奖励分布下，仍保持对上下文分布向量 $p$ 的实例相关性。类似于实验设计中可控制采样子群体的情形，我们允许学习者主动选择采样上下文。对于已知 $p$，我们刻画了紧致的遗憾率：被动采样（随机揭示上下文）的遗憾为 $\sqrt{n/T \lVert p \rVert_{1/2}}$，而主动采样采用 $q_j \propto p_j^{2/3}$ 分配时，达到紧致率 $\sqrt{n/T} \lVert p \rVert_{2/3}$。该改进最大可达 $\Theta(k^{1/4})$，其中 $k$ 为上下文数量。进一步扩展到预算受限的主动采样，刻画了对应的紧致率，并识别出何时有限主动预算即可恢复完全主动速率。当 $p$ 未知时，提出探索-探索-再承诺（EETC）算法，能最优平衡上下文分布估计与切换至主动分配的时间，使大时间跨度下遗憾率匹配已知 $p$ 时的主动速率，仅差常数因子。合成与真实数据实验验证了理论结果。
原文摘要 · Abstract (English)
We study the contextual multi-armed bandit problem with a finite context space (a.k.a. subpopulations), where the learner recommends a best action for each context and is evaluated by context-weighted simple regret. Our guarantees are worst-case over the reward distributions, while remaining instance-dependent with respect to the context distribution vector $p$. Akin to experimental design problems where the population of interest is fixed but the sampled subpopulation can be controlled, we allow the learner to actively choose which context to sample from. For a known $p$, we characterize tight regret rates: passive sampling where contexts are randomly revealed achieves regret of order $\sqrt{n/T \, \lVert p \rVert_{1/2}}$, whereas active sampling with allocation $q_j \propto p_j^{2/3}$ achieves the tight rate $\sqrt{n/T} \, \lVert p \rVert_{2/3}$. The resulting improvement can be as large as $Θ(k^{1/4})$, where $k$ is the number of contexts. We further extend the analysis to budgeted active sampling, characterize the corresponding tight rate, and identify when a limited active budget suffices to recover the fully active rate. When $p$ is unknown, we propose the Explore-Explore-Then-Commit (EETC) algorithm, which optimally balances estimating the context distribution and the time to switch to active allocation, such that for large horizons, it matches the known-$p$ active rate up to constants. Experiments on synthetic and real-world data support our theoretical findings.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。