An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Bandits
An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Bandits
复制标题
DOI：
--
复制
发表时间：
2020-06
期刊：
影响因子：
--
通讯作者：
Julian Katz-Samuels;Lalit P. Jain;Zohar S. Karnin;Kevin G. Jamieson
中科院分区：
文献类型：
--
作者：
Julian Katz-Samuels;Lalit P. Jain;Zohar S. Karnin;Kevin G. Jamieson
本文提出了固定置信度和固定预算条件下纯探索线性盗贼问题的近似最优算法。利用经验过程至上理论的思想，我们给出了一个算法，它的样本复杂度随着实例的几何形状而变化，并且避免了对臂数量的显式并界。与以往基于最小化最坏情况方差(例如G-最优设计)进行抽样的方法不同，我们定义了基于基础臂集合的高斯宽度的实验设计目标。我们就这一目标提供了一个新的下限，强调了它在样本复杂性中的基础作用。我们的固定置信度算法的样本复杂度符合这个下界，此外，对于最短路径、匹配和拟阵等组合类，其计算效率也很高，其中ARM集的维度可以是指数大的。最后，我们提出了固定预算设置下的线性强盗的第一种算法。它的保证符合我们的对数因子的下限。
This paper proposes near-optimal algorithms for the pure-exploration linear bandit problem in the fixed confidence and fixed budget settings. Leveraging ideas from the theory of suprema of empirical processes, we provide an algorithm whose sample complexity scales with the geometry of the instance and avoids an explicit union bound over the number of arms. Unlike previous approaches which sample based on minimizing a worst-case variance (e.g. G-optimal design), we define an experimental design objective based on the Gaussian-width of the underlying arm set. We provide a novel lower bound in terms of this objective that highlights its fundamental role in the sample complexity. The sample complexity of our fixed confidence algorithm matches this lower bound, and in addition is computationally efficient for combinatorial classes, e.g. shortest-path, matchings and matroids, where the arm sets can be exponentially large in the dimension. Finally, we propose the first algorithm for linear bandits in the the fixed budget setting. Its guarantee matches our lower bound up to logarithmic factors.