# Selective Sampling for Online Best-arm Identification

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 26 references that are in the map.
- First posted on arXiv 28 Oct 2021.

## Builds on (most cited first, 9 of 9)

- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Mean estimation and regression under heavy-tailed distributions--a survey](https://mlsanity.com/paper/1906.04280/) (2019)
- [Best-Arm Identification in Linear Bandits](https://mlsanity.com/paper/1409.6110/) (2014)
- [Sequential Experimental Design for Transductive Linear Bandits](https://mlsanity.com/paper/1906.08399/) (2019)
- [High-Dimensional Experimental Design and Kernel Bandits](https://mlsanity.com/paper/2105.05806/) (2021)
- [Efficient and Parsimonious Agnostic Active Learning](https://mlsanity.com/paper/1506.08669/) (2015)
- [Improved Algorithms for Agnostic Pool-based Active Classification](https://mlsanity.com/paper/2105.06499/) (2021)
- [Competitive Online Algorithms for Resource Allocation over the Positive Semidefinite Cone](https://mlsanity.com/paper/1802.01312/) (2018)

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

- [Active learning for data streams: a survey](https://mlsanity.com/paper/2302.08893/) (2023)
- [Active Learning with Safety Constraints](https://mlsanity.com/paper/2206.11183/) (2022)
- [Fast Rates in Pool-Based Batch Active Learning](https://mlsanity.com/paper/2202.05448/) (2022)
- [Data Representativity for Machine Learning and AI Systems](https://mlsanity.com/paper/2203.04706/) (2022)
- [Fair Active Learning in Low-Data Regimes](https://mlsanity.com/paper/2312.08559/) (2023)
- [On The Complexity of Best-Arm Identification in Non-Stationary Linear Bandits](https://mlsanity.com/paper/2603.10346/) (2026)

## Abstract (arXiv)

This work considers the problem of selective-sampling for best-arm identification. Given a set of potential options Zsubsetℝd, a learner aims to compute with probability greater than 1-δ, argmaxz∈ Z ztopθast where θast is unknown. At each time step, a potential measurement xt∈ Xsubsetℝd is drawn IID and the learner can either choose to take the measurement, in which case they observe a noisy measurement of xtopθast, or to abstain from taking the measurement and wait for a potentially more informative point to arrive in the stream. Hence the learner faces a fundamental trade-off between the number of labeled samples they take and when they have collected enough evidence to declare the best arm and stop sampling. The main results of this work precisely characterize this trade-off between labeled samples and stopping time and provide an algorithm that nearly-optimally achieves the minimal label complexity given a desired stopping time. In addition, we show that the optimal decision rule has a simple geometric form based on deciding whether a point is in an ellipse or not. Finally, our framework is general enough to capture binary classification improving upon previous works.