# Nearly Instance Optimal Sample Complexity Bounds for Top-k Arm Selection

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

## Key facts

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

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

- [Revisiting Simple Regret: Fast Rates for Returning a Good Arm](https://mlsanity.com/paper/2210.16913/) (2022)
- [Near-Optimal Collaborative Learning in Bandits](https://mlsanity.com/paper/2206.00121/) (2022)
- [A/B/n Testing with Control in the Presence of Subpopulations](https://mlsanity.com/paper/2110.15573/) (2021)
- [Sequential Learning of the Pareto Front for Multi-objective Bandits](https://mlsanity.com/paper/2501.17513/) (2025)
- [Sample Efficient Demonstration Selection for In-Context Learning](https://mlsanity.com/paper/2506.08607/) (2025)
- [Dealing With Misspecification In Fixed-Confidence Linear Top-m Identification](https://mlsanity.com/paper/2111.01479/) (2021)
- [Top-m identification for linear bandits](https://mlsanity.com/paper/2103.10070/) (2021)
- [Non-Asymptotic Analysis of a UCB-based Top Two Algorithm](https://mlsanity.com/paper/2210.05431/) (2022)
- [Learning-augmented Maximum Independent Set](https://mlsanity.com/paper/2407.11364/) (2024)
- [Optimal Best-Arm Identification in Bandits with Access to Offline Data](https://mlsanity.com/paper/2306.09048/) (2023)
- [Asymptotic Instance-Optimal Algorithms for Interactive Decision Making](https://mlsanity.com/paper/2206.02326/) (2022)
- [Approximate Top-m Arm Identification with Heterogeneous Reward Variances](https://mlsanity.com/paper/2204.05245/) (2022)
- [Communication-Efficient Collaborative Best Arm Identification](https://mlsanity.com/paper/2208.09029/) (2022)
- [SHAP@k:Efficient and Probably Approximately Correct (PAC) Identification of Top-k Features](https://mlsanity.com/paper/2307.04850/) (2023)
- [The Best Arm Evades: Near-optimal Multi-pass Streaming Lower Bounds for Pure Exploration in Multi-armed Bandits](https://mlsanity.com/paper/2309.03145/) (2023)
- [Optimal Streaming Algorithms for Multi-Armed Bandits](https://mlsanity.com/paper/2410.17835/) (2024)
- [FraPPE: Fast and Efficient Preference-based Pure Exploration](https://mlsanity.com/paper/2508.16487/) (2025)
- [Optimal Arm Elimination Algorithms for Combinatorial Bandits](https://mlsanity.com/paper/2510.23992/) (2025)
- [Good Allocations from Bad Estimates](https://mlsanity.com/paper/2601.05597/) (2026)
- [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)
- [Top-k Feature Importance Ranking](https://mlsanity.com/paper/2509.15420/) (2025)
- [Efficient Learning for Selecting Top-m Context-Dependent Designs](https://mlsanity.com/paper/2305.04086/) (2023)
- [Optimal Regret Bounds for Collaborative Learning in Bandits](https://mlsanity.com/paper/2312.09674/) (2023)
- [Cost-Aware Optimal Pairwise Pure Exploration](https://mlsanity.com/paper/2503.07877/) (2025)
- [Representative Action Selection for Large Action Space Bandit Families](https://mlsanity.com/paper/2505.18269/) (2025)
- [The Price of Decentralization in Top-K Arm Identification](https://mlsanity.com/paper/2608.22120/) (2026)
- [Data Efficient Sample Selection for In-Context Learning](https://mlsanity.com/paper/2609.06670/) (2026)

## Abstract (arXiv)

In the Best-k-Arm problem, we are given n stochastic bandit arms, each associated with an unknown reward distribution. We are required to identify the k arms with the largest means by taking as few samples as possible. In this paper, we make progress towards a complete characterization of the instance-wise sample complexity bounds for the Best-k-Arm problem. On the lower bound side, we obtain a novel complexity term to measure the sample complexity that every Best-k-Arm instance requires. This is derived by an interesting and nontrivial reduction from the Best-1-Arm problem. We also provide an elimination-based algorithm that matches the instance-wise lower bound within doubly-logarithmic factors. The sample complexity of our algorithm strictly dominates the state-of-the-art for Best-k-Arm (module constant factors).