Experimental Design for Regret Minimization in Linear Bandits
Experimental Design for Regret Minimization in Linear Bandits
复制标题
DOI：
--
复制
发表时间：
2020-11
期刊：
影响因子：
--
通讯作者：
Andrew Wagenmaker;Julian Katz-Samuels;Kevin G. Jamieson
中科院分区：
文献类型：
--
作者：
Andrew Wagenmaker;Julian Katz-Samuels;Kevin G. Jamieson
本文提出了一种新的基于实验设计的算法来最小化在线随机线性和组合强盗的后悔。虽然现有文献倾向于关注基于乐观的算法——在许多情况下，这已被证明是次优的——但我们的方法通过平衡信息获取和奖励之间的权衡，仔细计划采取哪些行动，克服乐观主义的失败。此外，我们利用经验过程至上理论的工具来获得与动作集的高斯宽度成比例的遗憾保证，避免浪费的联合界。我们提供了最先进的有限时间后悔保证，并表明我们的算法可以应用于强盗和半强盗反馈制度。在组合半强盗设置中，我们证明了我们的算法计算效率高，并且只依赖于调用线性最大化oracle。此外，我们还表明，只要稍加修改，我们的算法就可以用于纯勘探，在半强盗环境下获得最先进的纯勘探保证。最后，据我们所知，我们提供了第一个在半强盗制度下乐观主义失败的例子，并表明在这种情况下我们的算法是成功的。
In this paper we propose a novel experimental design-based algorithm to minimize regret in online stochastic linear and combinatorial bandits. While existing literature tends to focus on optimism-based algorithms--which have been shown to be suboptimal in many cases--our approach carefully plans which action to take by balancing the tradeoff between information gain and reward, overcoming the failures of optimism. In addition, we leverage tools from the theory of suprema of empirical processes to obtain regret guarantees that scale with the Gaussian width of the action set, avoiding wasteful union bounds. We provide state-of-the-art finite time regret guarantees and show that our algorithm can be applied in both the bandit and semi-bandit feedback regime. In the combinatorial semi-bandit setting, we show that our algorithm is computationally efficient and relies only on calls to a linear maximization oracle. In addition, we show that with slight modification our algorithm can be used for pure exploration, obtaining state-of-the-art pure exploration guarantees in the semi-bandit setting. Finally, we provide, to the best of our knowledge, the first example where optimism fails in the semi-bandit regime, and show that in this setting our algorithm succeeds.