A Contextual Bandit Bake-off
\nameAlberto Bietti \addrCenter for Data Science, New York University, New York, NY \nameAlekh Agarwal \addrMicrosoft Research, Redmond, WA \nameJohn Langford \addrMicrosoft Research, New York, NY Work done while AB was at Inria, partly during a visit to Microsoft Research NY, supported by the Microsoft Research-Inria Joint Center.
Abstract
Contextual bandit algorithms are essential for solving many real-world interactive machine learning problems. Despite multiple recent successes on statistically optimal and computationally efficient methods, the practical behavior of these algorithms is still poorly understood. We leverage the availability of large numbers of supervised learning datasets to empirically evaluate contextual bandit algorithms, focusing on practical methods that learn by relying on optimization oracles from supervised learning. We find that a recent method (Foster et al., 2018) using optimism under uncertainty works the best overall. A surprisingly close second is a simple greedy baseline that only explores implicitly through the diversity of contexts, followed by a variant of Online Cover (Agarwal et al., 2014) which tends to be more conservative but robust to problem specification by design. Along the way, we also evaluate various components of contextual bandit algorithm design such as loss estimators. Overall, this is a thorough study and review of contextual bandit methodology.
中文速览
在真实推荐、医疗等场景中，智能体每次只能观察到所选动作的反馈，如何在"探索新选项"和"利用已知信息"之间取得平衡，是情境赌博机（contextual bandit）算法的核心难题，但现有方法的实际表现一直缺乏系统性认识。研究者利用超过500个有监督学习数据集模拟赌博机反馈，对多种主流算法——包括RegCB、ε-greedy、Online Cover、Bootstrap Thompson采样以及纯贪心策略——进行了迄今最大规模的对比实验。结果发现，基于乐观估计的RegCB（Foster et al., 2018）总体表现最佳，令人意外的是，几乎不做主动探索的纯贪心基准紧随其后，甚至超过大多数精心设计的探索算法，而理论上更稳健的Online Cover虽然保守，但在各类数据集上表现相当稳定。这项研究为从业者提供了切实的算法选型建议，同时也揭示了理论与实践之间的明显落差，呼吁学界重新审视贪心策略的有效性，以及如何让探索算法在"容易"的问题上不再付出不必要的代价。
原文 arXiv:1802.04064;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1802.04064v5