PAC Identification of Many Good Arms in Stochastic Multi-Armed Bandits
PAC Identification of Many Good Arms in Stochastic Multi-Armed Bandits
复制标题
PAC 识别随机多臂强盗中的许多好武器
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Shivaram Kalyanakrishnan
中科院分区：
文献类型：
--
作者：
A. Chaudhuri;Shivaram Kalyanakrishnan
我们考虑的问题，确定任何$k$的最好的$m$武器在$n$-武装随机多臂强盗。在PAC设置中，这个特定的问题概括了“最佳子集选择”和"从最佳m个臂中选择一个“的问题[arcsk 2017]。在众包和药物设计等应用中，确定单一的良好解决方案往往是不够的。此外，由于存在许多非常接近的解决方案，找到最佳子集可能很难。我们的推广识别出$k$武器的最佳$m$，其中$1 \leq k \leq m$，作为一个更有效的替代方案。我们提出了一个下界的最坏情况下的样本复杂性一般$k$，和一个完全顺序的PAC算法，\GLUCB，这是更简单的情况下，样本效率。此外，将我们的分析扩展到无限武装匪徒，我们提出了一种独立于$n$的PAC算法，该算法最多使用与下限相比的加性poly-log样本数从最佳$\rho$分数的武器中识别武器，从而改进了[arcsk 2017]和[Aziz+AKA：2018]。识别$k > 1$不同的武器从最好的$\rho$分数的问题并不总是定义良好的，对于这个问题的一个特殊的类，我们提出了下限和上限。最后，通过减少，我们建立了一个上限之间的关系，为“一出最好的$\rho$”问题的无限实例和“一出最好的$m$”问题的有限实例。我们猜想，这是更有效地解决“小”有限的情况下，使用后者制定，而不是通过前者。
We consider the problem of identifying any $k$ out of the best $m$ arms in an $n$-armed stochastic multi-armed bandit. Framed in the PAC setting, this particular problem generalises both the problem of `best subset selection' and that of selecting `one out of the best m' arms [arcsk 2017]. In applications such as crowd-sourcing and drug-designing, identifying a single good solution is often not sufficient. Moreover, finding the best subset might be hard due to the presence of many indistinguishably close solutions. Our generalisation of identifying exactly $k$ arms out of the best $m$, where $1 \leq k \leq m$, serves as a more effective alternative. We present a lower bound on the worst-case sample complexity for general $k$, and a fully sequential PAC algorithm, \GLUCB, which is more sample-efficient on easy instances. Also, extending our analysis to infinite-armed bandits, we present a PAC algorithm that is independent of $n$, which identifies an arm from the best $\rho$ fraction of arms using at most an additive poly-log number of samples than compared to the lower bound, thereby improving over [arcsk 2017] and [Aziz+AKA:2018]. The problem of identifying $k > 1$ distinct arms from the best $\rho$ fraction is not always well-defined; for a special class of this problem, we present lower and upper bounds. Finally, through a reduction, we establish a relation between upper bounds for the `one out of the best $\rho$' problem for infinite instances and the `one out of the best $m$' problem for finite instances. We conjecture that it is more efficient to solve `small' finite instances using the latter formulation, rather than going through the former.