Minimal Exploration in Structured Stochastic Bandits
Minimal Exploration in Structured Stochastic Bandits
复制标题
结构化随机老虎机的最小探索
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
A. Proutière
中科院分区：
文献类型：
--
作者：
Richard Combes;Stefan Magureanu;A. Proutière
本文介绍并解决了广泛的随机匪徒问题，其中将手臂映射到相应的奖励表现出一些已知的结构特性。我们的框架涵盖了大多数现有的结构（例如线性，Lipschitz，单峰，组合，决斗等）。我们得出了针对这些问题的渐近实例特定后悔的下限，并开发了OSSB，这是一种遗憾与此基本限制相匹配的算法。 OSSB并不基于“面对不确定性的乐观”或汤普森采样的经典原则，而是旨在匹配在遗憾下界的推导中，次优臂的最小探索速率。在线性匪徒问题的情况下，我们使用数值实验说明了OSSB的效率，并表明OSSB的表现优于现有算法，包括汤普森采样。
This paper introduces and addresses a wide class of stochastic bandit problems where the function mapping the arm to the corresponding reward exhibits some known structural properties. Most existing structures (e.g. linear, Lipschitz, unimodal, combinatorial, dueling, ...) are covered by our framework. We derive an asymptotic instance-specific regret lower bound for these problems, and develop OSSB, an algorithm whose regret matches this fundamental limit. OSSB is not based on the classical principle of "optimism in the face of uncertainty" or on Thompson sampling, and rather aims at matching the minimal exploration rates of sub-optimal arms as characterized in the derivation of the regret lower bound. We illustrate the efficiency of OSSB using numerical experiments in the case of the linear bandit problem and show that OSSB outperforms existing algorithms, including Thompson sampling.