# lil'HDoC: An Algorithm for Good Arm Identification under Small Threshold Gap

arXiv: https://arxiv.org/abs/2401.15879 · HTML: https://mlsanity.com/paper/2401.15879/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 14 references that are in the map.
- First posted on arXiv 29 Jan 2024.

## Builds on (most cited first, 7 of 7)

- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits](https://mlsanity.com/paper/1312.7308/) (2013)
- [An optimal algorithm for the Thresholding Bandit Problem](https://mlsanity.com/paper/1605.08671/) (2016)
- [Good Arm Identification via Bandit Feedback](https://mlsanity.com/paper/1710.06360/) (2017)
- [Differential Good Arm Identification](https://mlsanity.com/paper/2303.07154/) (2023)
- [Fast online inference for nonlinear contextual bandit based on Generative Adversarial Network](https://mlsanity.com/paper/2202.08867/) (2022)
- [Practical Algorithms for Best-K Identification in Multi-Armed Bandits](https://mlsanity.com/paper/1705.06894/) (2017)

## Built on by (most cited first, 5 of 5)

- [Uncertainty Profiles for LLMs: Uncertainty Source Decomposition and Adaptive Model-Metric Selection](https://mlsanity.com/paper/2505.07309/) (2025)
- [LinearAPT: An Adaptive Algorithm for the Fixed-Budget Thresholding Linear Bandit Problem](https://mlsanity.com/paper/2403.06230/) (2024)
- [Multi-Metric Adaptive Experimental Design Under a Fixed Budget with Validation](https://mlsanity.com/paper/2506.03062/) (2025)
- [Near Optimal Non-asymptotic Sample Complexity of 1-Identification](https://mlsanity.com/paper/2506.06978/) (2025)
- [Multimodal Chip Physical Design Engineer Assistant](https://mlsanity.com/paper/2510.15872/) (2025)

## Abstract (arXiv)

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 λ 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.