# MaxGap Bandit: Adaptive Algorithms for Approximate Ranking

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Jun 2019.

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

- [Sequential Learning of the Pareto Front for Multi-objective Bandits](https://mlsanity.com/paper/2501.17513/) (2025)
- [Online Sign Identification: Minimization of the Number of Errors in Thresholding Bandits](https://mlsanity.com/paper/2110.09133/) (2021)
- [Exponentially Consistent Nonparametric Linkage-Based Clustering of Data Sequences](https://mlsanity.com/paper/2411.13922/) (2024)
- [Online Clustering of Data Sequences with Bandit Information](https://mlsanity.com/paper/2501.11421/) (2025)
- [Efficient Clustering in Stochastic Bandits](https://mlsanity.com/paper/2601.09162/) (2026)
- [Data Efficient Sample Selection for In-Context Learning](https://mlsanity.com/paper/2609.06670/) (2026)

## Abstract (arXiv)

This paper studies the problem of adaptively sampling from K distributions (arms) in order to identify the largest gap between any two adjacent means. We call this the MaxGap-bandit problem. This problem arises naturally in approximate ranking, noisy sorting, outlier detection, and top-arm identification in bandits. The key novelty of the MaxGap-bandit problem is that it aims to adaptively determine the natural partitioning of the distributions into a subset with larger means and a subset with smaller means, where the split is determined by the largest gap rather than a pre-specified rank or threshold. Estimating an arm's gap requires sampling its neighboring arms in addition to itself, and this dependence results in a novel hardness parameter that characterizes the sample complexity of the problem. We propose elimination and UCB-style algorithms and show that they are minimax optimal. Our experiments show that the UCB-style algorithms require 6-8x fewer samples than non-adaptive sampling to achieve the same error.