Exploring k out of Top ρ Fraction of Arms in Stochastic Bandits
Exploring k out of Top ρ Fraction of Arms in Stochastic Bandits
复制标题
DOI：
--
复制
发表时间：
2018-10
期刊：
影响因子：
--
通讯作者：
Wenbo Ren;Jia Liu;N. Shroff
中科院分区：
文献类型：
--
作者：
Wenbo Ren;Jia Liu;N. Shroff
本文研究了在一个有限或无限集合中，在可能近似正确的(PAC)容差下，从武器的前$\rho$分数(例如，前5\%)中识别任何$k$不同的武器的问题。我们考虑了两种情况：(I)当顶级武器的预期回报的门槛已知时，以及(Ii)当它未知的时候。我们证明了四种变量(有限或无限臂，以及已知或未知阈值)的下界，并给出了每种下界的算法。其中两个算法被证明是样本复杂度最优的(直到恒定因子)，另外两个算法是直到对数因子的最优。与专注于从$n$臂中寻找(PAC)最佳$k$臂的“$k$-探索”算法相比，本文的结果提供了高达$\rho n/k$的缩减。我们还在数字上展示了对最先进水平的改进。
This paper studies the problem of identifying any $k$ distinct arms among the top $\rho$ fraction (e.g., top 5\%) of arms from a finite or infinite set with a probably approximately correct (PAC) tolerance $\epsilon$. We consider two cases: (i) when the threshold of the top arms' expected rewards is known and (ii) when it is unknown. We prove lower bounds for the four variants (finite or infinite arms, and known or unknown threshold), and propose algorithms for each. Two of these algorithms are shown to be sample complexity optimal (up to constant factors) and the other two are optimal up to a log factor. Results in this paper provide up to $\rho n/k$ reductions compared with the "$k$-exploration" algorithms that focus on finding the (PAC) best $k$ arms out of $n$ arms. We also numerically show improvements over the state-of-the-art.