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.

介绍了一类广泛的随机赌博问题，其中将臂与相应的奖励映射的函数具有一些已知的结构特性。推导了这些问题的渐近特定情况下的遗憾下界，并且开发了OSSB算法，其遗憾匹配了这个基本极限。通过数值实验展示了OSSB的效率，并且证明OSSB优于包括汤普森取样在内的现有算法。

结构化随机赌臂问题中的最小探索