# Good Arm Identification via Bandit Feedback

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

## Key facts

- Cited by 30 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Oct 2017.

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

- [Online certification of preference-based fairness for personalized recommender systems](https://mlsanity.com/paper/2104.14527/) (2021)
- [Pure Exploration in Kernel and Neural Bandits](https://mlsanity.com/paper/2106.12034/) (2021)
- [Lenient Regret and Good-Action Identification in Gaussian Process Bandits](https://mlsanity.com/paper/2102.05793/) (2021)
- [Interactively Learning Preference Constraints in Linear Bandits](https://mlsanity.com/paper/2206.05255/) (2022)
- [Peeking with PEAK: Sequential, Nonparametric Composite Hypothesis Tests for Means of Multiple Data Streams](https://mlsanity.com/paper/2402.06122/) (2024)
- [Differential Good Arm Identification](https://mlsanity.com/paper/2303.07154/) (2023)
- [Query-Efficient Correlation Clustering with Noisy Oracle](https://mlsanity.com/paper/2402.01400/) (2024)
- [An Anytime Algorithm for Good Arm Identification](https://mlsanity.com/paper/2310.10359/) (2023)
- [lil'HDoC: An Algorithm for Good Arm Identification under Small Threshold Gap](https://mlsanity.com/paper/2401.15879/) (2024)
- [Reward Maximization for Pure Exploration: Minimax Optimal Good Arm Identification for Nonparametric Multi-Armed Bandits](https://mlsanity.com/paper/2410.15564/) (2024)
- [Online Sign Identification: Minimization of the Number of Errors in Thresholding Bandits](https://mlsanity.com/paper/2110.09133/) (2021)
- [Testing the Feasibility of Linear Programs with Bandit Feedback](https://mlsanity.com/paper/2406.15648/) (2024)
- [Adaptive Identification of Populations with Treatment Benefit in Clinical Trials: Machine Learning Challenges and Solutions](https://mlsanity.com/paper/2208.05844/) (2022)
- [Adaptive Experiment Design with Synthetic Controls](https://mlsanity.com/paper/2401.17205/) (2024)
- [Near Optimal Pure Exploration in Logistic Bandits](https://mlsanity.com/paper/2410.20640/) (2024)
- [Policy Testing in Markov Decision Processes](https://mlsanity.com/paper/2505.15342/) (2025)
- [Multi-thresholding Good Arm Identification with Bandit Feedback](https://mlsanity.com/paper/2503.10386/) (2025)
- [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)
- [Constrained Best Arm Identification with Tests for Feasibility](https://mlsanity.com/paper/2511.09808/) (2025)
- [Gaussian Process Classification Bandits](https://mlsanity.com/paper/2212.13157/) (2022)
- [An Asymptotically Optimal Algorithm for the Convex Hull Membership Problem](https://mlsanity.com/paper/2302.02033/) (2023)
- [Optimal Thresholding Linear Bandit](https://mlsanity.com/paper/2402.09467/) (2024)
- [Fixed Confidence Best Arm Identification in the Bayesian Setting](https://mlsanity.com/paper/2402.10429/) (2024)
- [Batch Entanglement Detection in Parameterized Qubit States using Classical Bandit Algorithms](https://mlsanity.com/paper/2406.19738/) (2024)
- [An Efficient Algorithm for Thresholding Monte Carlo Tree Search](https://mlsanity.com/paper/2601.22600/) (2026)
- [Pure Exploration for a Good Policy in Reinforcement Learning with Bandit Feedback](https://mlsanity.com/paper/2605.23182/) (2026)
- [Test-Time Scaling via Budgeted Multi-Attribute Verification](https://mlsanity.com/paper/2609.34322/) (2026)
- [Bandits with Multiple Optimal Arms: Minimax Regret and Non-Adaptivity](https://mlsanity.com/paper/2609.38659/) (2026)
- [DataCupid: Stable Matching Repair for Training Data Acquisition with Delayed Feedback](https://mlsanity.com/paper/2610.12960/) (2026)

## Abstract (arXiv)

We consider a novel stochastic multi-armed bandit problem called em good arm identification (GAI), where a good arm is defined as an arm with expected reward greater than or equal to a given threshold. GAI is a pure-exploration problem that a single agent repeats a process of outputting an arm as soon as it is identified as a good one before confirming the other arms are actually not good. The objective of GAI is to minimize the number of samples for each process. We find that GAI faces a new kind of dilemma, the em exploration-exploitation dilemma of confidence, which is different difficulty from the best arm identification. As a result, an efficient design of algorithms for GAI is quite different from that for the best arm identification. We derive a lower bound on the sample complexity of GAI that is tight up to the logarithmic factor O(log frac1δ) for acceptance error rate δ. We also develop an algorithm whose sample complexity almost matches the lower bound. We also confirm experimentally that our proposed algorithm outperforms naive algorithms in synthetic settings based on a conventional bandit problem and clinical trial researches for rheumatoid arthritis.