标题： 探索先，利用后：多臂老虎机问题中遗憾的真实形状 显示英文标题

标题： Explore First, Exploit Next: The True Shape of Regret in Bandit Problems

摘要： 我们重新审视多臂老虎机问题中的遗憾下界。 我们得到非渐近、与分布相关的界限，并提供仅基于Kullback-Leibler散度已知性质的简单证明。 这些界限特别表明，在初始阶段，遗憾几乎线性增长，而遗憾的对数增长仅在最终阶段成立。 证明技术抓住了所用信息论论证的本质，并去除了所有不必要的复杂性。 显示英文摘要

摘要： We revisit lower bounds on the regret in the case of multi-armed bandit problems. We obtain non-asymptotic, distribution-dependent bounds and provide straightforward proofs based only on well-known properties of Kullback-Leibler divergences. These bounds show in particular that in an initial phase the regret grows almost linearly, and that the well-known logarithmic growth of the regret only holds in a final phase. The proof techniques come to the essence of the information-theoretic arguments used and they are deprived of all unnecessary complications.