# Online Sign Identification: Minimization of the Number of Errors in Thresholding Bandits

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 50 references that are in the map.
- First posted on arXiv 18 Oct 2021.

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

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Bandits with concave rewards and convex knapsacks](https://mlsanity.com/paper/1402.5758/) (2014)
- [Pure Exploration with Multiple Correct Answers](https://mlsanity.com/paper/1902.03475/) (2019)
- [Non-Asymptotic Pure Exploration by Solving Games](https://mlsanity.com/paper/1906.10431/) (2019)
- [An optimal algorithm for the Thresholding Bandit Problem](https://mlsanity.com/paper/1605.08671/) (2016)
- [The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime](https://mlsanity.com/paper/1702.05186/) (2017)
- [Good Arm Identification via Bandit Feedback](https://mlsanity.com/paper/1710.06360/) (2017)
- [Thresholding Bandit for Dose-ranging: The Impact of Monotonicity](https://mlsanity.com/paper/1711.04454/) (2017)
- [Sequential Test for the Lowest Mean: From Thompson to Murphy Sampling](https://mlsanity.com/paper/1806.00973/) (2018)
- [Thresholding Bandits with Augmented UCB](https://mlsanity.com/paper/1704.02281/) (2017)
- [An adaptive stochastic optimization algorithm for resource allocation](https://mlsanity.com/paper/1902.04376/) (2019)
- [The Influence of Shape Constraints on the Thresholding Bandit Problem](https://mlsanity.com/paper/2006.10006/) (2020)
- [Approachability in unknown games: Online learning meets multi-objective optimization](https://mlsanity.com/paper/1402.2043/) (2014)
- [A New Perspective on Pool-Based Active Classification and False-Discovery Control](https://mlsanity.com/paper/2008.06555/) (2020)
- [Fast Rates for Bandit Optimization with Upper-Confidence Frank-Wolfe](https://mlsanity.com/paper/1702.06917/) (2017)
- [A Bandit Approach to Multiple Testing with False Discovery Control](https://mlsanity.com/paper/1809.02235/) (2018)
- [Asynchronous Parallel Empirical Variance Guided Algorithms for the Thresholding Bandit Problem](https://mlsanity.com/paper/1704.04567/) (2017)
- [Thresholding Bandit with Optimal Aggregate Regret](https://mlsanity.com/paper/1905.11046/) (2019)
- [MaxGap Bandit: Adaptive Algorithms for Approximate Ranking](https://mlsanity.com/paper/1906.00547/) (2019)
- [Regularized Contextual Bandits](https://mlsanity.com/paper/1810.05065/) (2018)
- [Robust Outlier Arm Identification](https://mlsanity.com/paper/2009.09988/) (2020)
- [Statistical Decision Making for Optimal Budget Allocation in Crowd Labeling](https://mlsanity.com/paper/1403.3080/) (2014)

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

- [On the Existence of a Complexity in Fixed Budget Bandit Identification](https://mlsanity.com/paper/2303.09468/) (2023)
- [On Elimination Strategies for Bandit Fixed-Confidence Identification](https://mlsanity.com/paper/2205.10936/) (2022)
- [Multi-Metric Adaptive Experimental Design Under a Fixed Budget with Validation](https://mlsanity.com/paper/2506.03062/) (2025)

## Abstract (arXiv)

In the fixed budget thresholding bandit problem, an algorithm sequentially allocates a budgeted number of samples to different distributions. It then predicts whether the mean of each distribution is larger or lower than a given threshold. We introduce a large family of algorithms (containing most existing relevant ones), inspired by the Frank-Wolfe algorithm, and provide a thorough yet generic analysis of their performance. This allowed us to construct new explicit algorithms, for a broad class of problems, whose losses are within a small constant factor of the non-adaptive oracle ones. Quite interestingly, we observed that adaptive methods empirically greatly out-perform non-adaptive oracles, an uncommon behavior in standard online learning settings, such as regret minimization. We explain this surprising phenomenon on an insightful toy problem.