# Practical Algorithms for Best-K Identification in Multi-Armed Bandits

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

## Key facts

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

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

- [SHAP@k:Efficient and Probably Approximately Correct (PAC) Identification of Top-k Features](https://mlsanity.com/paper/2307.04850/) (2023)
- [lil'HDoC: An Algorithm for Good Arm Identification under Small Threshold Gap](https://mlsanity.com/paper/2401.15879/) (2024)
- [TSEC: a framework for online experimentation under experimental constraints](https://mlsanity.com/paper/2101.06592/) (2021)
- [BoundaryMORPH: Budgeted Reranking via Active Set Selection for Diffuse Retrieval](https://mlsanity.com/paper/2609.27213/) (2026)

## Abstract (arXiv)

In the Best-K identification problem (Best-K-Arm), we are given N stochastic bandit arms with unknown reward distributions. Our goal is to identify the K arms with the largest means with high confidence, by drawing samples from the arms adaptively. This problem is motivated by various practical applications and has attracted considerable attention in the past decade. In this paper, we propose new practical algorithms for the Best-K-Arm problem, which have nearly optimal sample complexity bounds (matching the lower bound up to logarithmic factors) and outperform the state-of-the-art algorithms for the Best-K-Arm problem (even for K=1) in practice.