Polynomial-Time Algorithms for Multiple-Arm Identification with Full-Bandit Feedback
Polynomial-Time Algorithms for Multiple-Arm Identification with Full-Bandit Feedback
复制标题
DOI：
10.1162/neco_a_01299
复制
发表时间：
2019-02
影响因子：
2.9
通讯作者：
Yuko Kuroki;Liyuan Xu;Atsushi Miyauchi;J. Honda;Masashi Sugiyama
中科院分区：
文献类型：
--
作者：
Yuko Kuroki;Liyuan Xu;Atsushi Miyauchi;J. Honda;Masashi Sugiyama
我们研究了随机多臂识别问题，其中一个智能体从给定的n个臂中按顺序搜索k个臂的一个子集(也称为超臂)，并试图识别出最佳超臂。到目前为止，大多数工作都考虑了半强盗设置，在这种情况下，代理人可以观察到每一只拉出的手臂的奖励，或者假设每只手臂都可以在每一轮中被询问。然而，在现实世界的应用中，观察单个武器的奖励是代价高昂的，有时甚至是不可能的。在这项研究中，我们处理的是全强盗设置，在这种情况下，每次拉动只给出一个超级手臂的总和的嘈杂观察。虽然我们的问题可以看作是线性强盗中最佳手臂识别的一个例子，但是基于线性强盗的朴素方法在计算上是不可行的，因为超臂的数量K是指数的。为了解决这个问题，我们首先设计了一个多项式时间近似算法来求解一个由置信度椭球最大值引起的0-1二次规划问题。基于我们的近似算法，我们提出了一种计算时间为O(LogK)的Banddit算法，从而获得了与线性Banddit算法相比的指数加速比。我们给出了一个样本复杂度上界，它仍然是最坏情况下最优的。最后，我们在超过1010个超级臂的大规模数据集上进行了实验，证明了我们的算法在计算时间和样本复杂度方面的优越性。
We study the problem of stochastic multiple-arm identification, where an agent sequentially explores a size-k subset of arms (also known as a super arm) from given n arms and tries to identify the best super arm. Most work so far has considered the semi-bandit setting, where the agent can observe the reward of each pulled arm or assumed each arm can be queried at each round. However, in real-world applications, it is costly or sometimes impossible to observe a reward of individual arms. In this study, we tackle the full-bandit setting, where only a noisy observation of the total sum of a super arm is given at each pull. Although our problem can be regarded as an instance of the best arm identification in linear bandits, a naive approach based on linear bandits is computationally infeasible since the number of super arms K is exponential. To cope with this problem, we first design a polynomial-time approximation algorithm for a 0-1 quadratic programming problem arising in confidence ellipsoid maximization. Based on our approximation algorithm, we propose a bandit algorithm whose computation time is O(log K), thereby achieving an exponential speedup over linear bandit algorithms. We provide a sample complexity upper bound that is still worst-case optimal. Finally, we conduct experiments on large-scale data sets with more than 1010 super arms, demonstrating the superiority of our algorithms in terms of both the computation time and the sample complexity.