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

Reda Ouhamma, Rémy Degenne, Pierre Gaillard, Vianney Perchet

Abstract

In the multi-armed bandit literature, the focus is typically on regret minimization. However, many real-world scenarios require identifying the characteristics of distributions rather than maximizing rewards. This paper investigates the fixed-budget thresholding bandit problem, where the goal is to correctly classify the means of $K$ distributions as being above or below a specific threshold. We introduce the Frank-Wolfe for Thresholding (FWT) algorithm, an index-based method that optimizes an upper bound on expected errors. Our work provides significantly tighter theoretical bounds for existing algorithms and demonstrates a surprising "adaptivity bonus," where adaptive strategies outperform non-adaptive oracles by exploiting stochastic noise.

Introduction

Consider a crowdsourcing platform manager tasked with identifying positive versus negative contributors among $K$ workers within a fixed budget of $T$ tasks. This scenario exemplifies the fixed-budget thresholding bandit problem. Unlike standard bandits, the objective is to identify the "sign" (relative to a threshold) of every arm. The primary challenge lies in balancing resources between "easy" arms (far from the threshold) and "hard" arms (near the threshold). If resources are misallocated, the system risks making errors on easily identifiable arms or failing to resolve ambiguous ones.

Methodology: The FWT Algorithm

We propose a new class of index-based algorithms, headlined by Frank-Wolfe for Thresholding (FWT). FWT is inspired by the Frank-Wolfe optimization method, designed to minimize a mathematical upper bound of the total expected errors. At each step, the algorithm pulls the arm with the lowest index value, calculated using a function that balances the number of pulls ($n$) with the current estimated gap from the threshold ($x$):

$$F(n, x; a) = \max\{x, 1\} - \log(\max\{x, 1\}) + \log(n/a)$$

A key contribution of this work is a generic analysis framework that applies to a family of algorithms, including LSA and APT. This refinement improved the theoretical error bound for the LSA algorithm by a factor of 4005, bridging the gap between empirical performance and theoretical guarantees.

The M-Shape Strategy and Adaptivity

Theoretical analysis reveals that the optimal non-adaptive strategy follows an "M-shape." It prioritizes arms with intermediate distances from the threshold, as very close arms are statistically impossible to resolve perfectly with a fixed budget, and very distant arms are easily classified with minimal samples.

Comparison of sampling strategies across different mean values (mu), showing the characteristic M-shape of the optimal non-adaptive strategy.

A significant finding is the adaptivity bonus. While a non-adaptive oracle determines its sampling strategy upfront, adaptive algorithms like FWT can adjust based on observed samples. If an adaptive algorithm receives "lucky" samples that clarify an arm's sign early, it can reallocate that arm's remaining budget to more ambiguous cases. This allows adaptive methods to paradoxically outperform the "optimal" non-adaptive oracle.

Key Results

Empirical evaluations using synthetic datasets (Linear, Quadratic, and Constant gaps) confirm the superiority of adaptive methods. FWT and LSA consistently reach near-zero error rates faster than the non-adaptive oracle benchmark.

Upper-bound on expected errors over time, showing adaptive algorithms FWT and LSA outperforming the non-adaptive oracle.

Furthermore, FWT demonstrates "anytime" performance, maintaining high efficiency even if the budget $T$ is truncated unexpectedly. Theoretically, FWT's expected error is proven to be within a factor of 4 in the exponent of the best possible non-adaptive strategy.

Conclusion and Future Work

This research advances the understanding of thresholding bandits by providing tighter bounds and demonstrating the power of adaptivity. Future work will explore non-separable loss functions (e.g., minimizing the probability of exceeding a specific error count) and more complex cost functions, such as sum-of-gaps losses. Additionally, quantifying the exact theoretical "adaptivity gap" remains an open challenge for the field.

Summary updated

Abstract

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.
BibTeX
@inproceedings{ouhamma2021online,
  author = {Reda Ouhamma and Rémy Degenne and Pierre Gaillard and Vianney Perchet},
  title = {{Online Sign Identification: Minimization of the Number of Errors in Thresholding Bandits}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=rVvGyWMHWP},
}
Figure