Beating the adaptive bandit with high probability
Beating the adaptive bandit with high probability
复制标题
高概率击败自适应强盗
DOI：
10.1109/ita.2009.5044958
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
A. Rakhlin
中科院分区：
文献类型：
--
作者：
Jacob D. Abernethy;A. Rakhlin
给出了任意凸决策集上部分信息(BANDIT)问题的(√T)高概率保证的一种原则性证明方法。首先，我们从“局部”规范的角度证明了全信息问题的遗憾保证，将这两种方法统一起来，这两种规范都是关于熵和自协调势垒正则化的。给定一种算法，如黑匣子，我们可以使用抽样方案将一个盗贼问题转化为一个全信息问题。主要结果表明，当黑盒、抽样方案和缺失信息的估计满足一些相对容易检验的条件时，高概率(√T)界成立。该方法的核心是构造置信度区间的线性上界。作为主要结果的应用，我们给出了第一个已知的具有(√T)高概率界的球面的有效算法。我们还得到了n-单形的结果，改进了Auer等人[3]的O(√Nt Log(Nt))界，方法是用Ω(√T替换Log T项，并缩小与Log Nt的下界的差距)。虽然(√T)高概率界应该适用于一般决策集(通过我们的主要结果)，但线性上界的构造取决于集合的特定几何；我们相信球面例子已经展示了必要的成分。我们得到的对自适应对手的保证(不像[1]的预期结果)和算法是有效的，因为置信度的线性上界是可以计算的。
We provide a principled way of proving Õ(√T) high-probability guarantees for partial-information (bandit) problems over arbitrary convex decision sets. First, we prove a regret guarantee for the full-information problem in terms of “local” norms, both for entropy and self-concordant barrier regularization, unifying these methods. Given one of such algorithms as a black-box, we can convert a bandit problem into a full-information problem using a sampling scheme. The main result states that a high-probability Õ(√T) bound holds whenever the black-box, the sampling scheme, and the estimates of missing information satisfy a number of conditions, which are relatively easy to check. At the heart of the method is a construction of linear upper bounds on confidence intervals. As applications of the main result, we provide the first known efficient algorithm for the sphere with an Õ(√T) high-probability bound. We also derive the result for the n-simplex, improving the O(√nT log(nT)) bound of Auer et al [3] by replacing the log T term with log log T and closing the gap to the lower bound of Ω(√nT). While Õ(√T) high-probability bounds should hold for general decision sets through our main result, construction of linear upper bounds depends on the particular geometry of the set; we believe that the sphere example already exhibits the necessary ingredients. The guarantees we obtain hold for adaptive adversaries (unlike the in-expectation results of [1]) and the algorithms are efficient, given that the linear upper bounds on confidence can be computed.