  Good arm identification (GAI) is a pure-exploration bandit problem in which a
single learner outputs an arm as soon as it is identified as a good arm. A good
arm is defined as an arm with an expected reward greater than or equal to a
given threshold. This paper focuses on the GAI problem under a small threshold
gap, which refers to the distance between the expected rewards of arms and the
given threshold. We propose a new algorithm called lil'HDoC to significantly
improve the total sample complexity of the HDoC algorithm. We demonstrate that
the sample complexity of the first $\lambda$ output arm in lil'HDoC is bounded
by the original HDoC algorithm, except for one negligible term, when the
distance between the expected reward and threshold is small. Extensive
experiments confirm that our algorithm outperforms the state-of-the-art
algorithms in both synthetic and real-world datasets.
