# Best-of-K Bandits

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Mar 2016.

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

- [Exploiting Correlation to Achieve Faster Learning Rates in Low-Rank Preference Bandits](https://mlsanity.com/paper/2202.11795/) (2022)
- [Nearly Minimax Optimal Submodular Maximization with Bandit Feedback](https://mlsanity.com/paper/2310.18465/) (2023)
- [Finding Optimal Arms in Non-stochastic Combinatorial Bandits with Semi-bandit Feedback and Finite Budget](https://mlsanity.com/paper/2202.04487/) (2022)
- [Sum-max Submodular Bandits](https://mlsanity.com/paper/2311.05975/) (2023)
- [Combinatorial Bandits without Total Order for Arms](https://mlsanity.com/paper/2103.02741/) (2021)
- [On the Sublinear Regret of Continuous K-Max Bandits](https://mlsanity.com/paper/2502.13467/) (2025)
- [Oracle-Efficient Combinatorial Semi-Bandits](https://mlsanity.com/paper/2510.21431/) (2025)

## Abstract (arXiv)

This paper studies the Best-of-K Bandit game: At each time the player chooses a subset S among all N-choose-K possible options and observes reward max(X(i) : i in S) where X is a random vector drawn from a joint distribution. The objective is to identify the subset that achieves the highest expected reward with high probability using as few queries as possible. We present distribution-dependent lower bounds based on a particular construction which force a learner to consider all N-choose-K subsets, and match naive extensions of known upper bounds in the bandit setting obtained by treating each subset as a separate arm. Nevertheless, we present evidence that exhaustive search may be avoided for certain, favorable distributions because the influence of high-order order correlations may be dominated by lower order statistics. Finally, we present an algorithm and analysis for independent arms, which mitigates the surprising non-trivial information occlusion that occurs due to only observing the max in the subset. This may inform strategies for more general dependent measures, and we complement these result with independent-arm lower bounds.