We consider the thresholding bandit problem, whose goal is to find arms of
mean rewards above a given threshold $\theta$, with a fixed budget of $T$
trials. We introduce LSA, a new, simple and anytime algorithm that aims to
minimize the aggregate regret (or the expected number of mis-classified arms).
We prove that our algorithm is instance-wise asymptotically optimal. We also
provide comprehensive empirical results to demonstrate the algorithm's superior
performance over existing algorithms under a variety of different scenarios.

本文提出了 LSA 算法，用于解决阈值赌博机问题，证明了该算法在实例方面渐近最优，通过多种不同情况下的实证结果证明其优于现有算法的表现。

阈值型赌博机带有最优聚合遗憾

Thresholding Bandit with Optimal Aggregate Regret

We study the problem of selecting $K$ arms with the highest expected rewards
in a stochastic $n$-armed bandit game. This problem has a wide range of
applications, e.g., A/B testing, crowdsourcing, simulation optimization. Our
goal is to develop a PAC algorithm, which, with probability at least
$1-\delta$, identifies a set of $K$ arms with the aggregate regret at most
$\epsilon$. The notion of aggregate regret for multiple-arm identification was
first introduced in \cite{Zhou:14} , which is defined as the difference of the
averaged expected rewards between the selected set of arms and the best $K$
arms. In contrast to \cite{Zhou:14} that only provides instance-independent
sample complexity, we introduce a new hardness parameter for characterizing the
difficulty of any given instance. We further develop two algorithms and
establish the corresponding sample complexity in terms of this hardness
parameter. The derived sample complexity can be significantly smaller than
state-of-the-art results for a large class of instances and matches the
instance-independent lower bound upto a $\log(\epsilon^{-1})$ factor in the
worst case. We also prove a lower bound result showing that the extra
$\log(\epsilon^{-1})$ is necessary for instance-dependent algorithms using the
introduced hardness parameter.

研究了如何在随机赌博机游戏中选择期望回报最高的 K 个赌臂问题，提出了一种基于概率近似正确算法，并引入了难度参数来量化问题难度。通过研究两种算法的采样复杂度，得出了更优的上界，并证明了该上界在某些情况下是紧的。同时得出了引入难度参数的实例相关算法需要额外的对数因子作为代价的下界。