Adaptive Exploration in Linear Contextual Bandit
Adaptive Exploration in Linear Contextual Bandit
复制标题
线性上下文强盗中的自适应探索
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Csaba Szepesvari
中科院分区：
文献类型：
--
作者：
Botao Hao;Tor Lattimore;Csaba Szepesvari
上下文老虎机是许多顺序决策任务的基本模型。最流行的理论上合理的方法是基于乐观原则。虽然这些算法是实用的，但众所周知，它们是渐近的次优算法（Lattimore 和 Szepesvari，2017）。另一方面，针对该问题的现有渐近最优算法并未以最优方式利用线性结构，并且会受到低阶项的影响，而这些项在所有实际有趣的情况下都占主导地位。我们开始通过设计一种渐近最优且具有良好有限时间经验性能的算法来弥补这一差距。同时，我们还联系了有关无探索方法何时有效的最新文献。事实上，如果上下文的分布表现良好，那么我们的算法主要是贪婪的，并且享受次对数遗憾。此外，我们的方法是自适应的，因为它会自动检测好的情况。数值结果表明，相对于几个基线，我们的方法显着减少了遗憾。
Contextual bandits serve as a fundamental model for many sequential decision making tasks. The most popular theoretically justified approaches are based on the optimism principle. While these algorithms can be practical, they are known to be suboptimal asymptotically (Lattimore and Szepesvari, 2017). On the other hand, existing asymptotically optimal algorithms for this problem do not exploit the linear structure in an optimal way and suffer from lower-order terms that dominate the regret in all practically interesting regimes. We start to bridge the gap by designing an algorithm that is asymptotically optimal and has good finite-time empirical performance. At the same time, we make connections to the recent literature on when exploration-free methods are effective. Indeed, if the distribution of contexts is well behaved, then our algorithm acts mostly greedily and enjoys sub-logarithmic regret. Furthermore, our approach is adaptive in the sense that it automatically detects the nice case. Numerical results demonstrate significant regret reductions by our method relative to several baselines.