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

Reda Ouhamma, Odalric-Ambrym Maillard, Vianney Perchet

Introduction

In the realm of multi-armed bandits, the vast majority of research focuses on "regret minimization"—the process of finding the single best arm. However, many real-world applications, such as clinical trial screening or crowdsourcing quality control, require a different approach known as thresholding. In this setting, an algorithm is presented with $K$ different "arms" (distributions) and must answer a binary question for each: Is its mean $\mu_k$ greater than a specific threshold $\theta$?

The primary challenge is operating under a fixed budget. You have exactly $T$ total samples to distribute among the $K$ arms. Allocating too many samples to an "easy" arm (one whose mean is far from the threshold) wastes the budget. Conversely, spending too much on a "hard" arm (one very close to the threshold) might still result in an incorrect prediction due to noise. The ultimate goal is to minimize the expected weighted number of errors.

While previous algorithms like the Logarithmic-Sample Algorithm (LSA) were considered "optimal up to a constant," that constant was astronomically large (e.g., a factor of 16,000). This paper introduces a new family of algorithms that drastically tightens these theoretical performance guarantees and reveals surprising insights about adaptive versus non-adaptive strategies.

Methods: The Frank-Wolfe Inspiration

The authors propose a unified framework for index-based algorithms. At each step, the algorithm calculates an "index" for each arm based on its current samples and pulls the arm with the smallest index.

The core innovation of this paper is viewing the sample allocation problem through the lens of the Frank-Wolfe algorithm, a classic continuous optimization method. The process follows three main steps:

  1. Establish a theoretical upper bound on the probability of error.
  2. Treat the sample allocation as a continuous optimization problem.
  3. Calculate the gradient of this error bound to derive a sampling rule that iteratively moves toward the optimal allocation.

This approach yields the FWT (Frank-Wolfe for Thresholding) algorithm, which utilizes a specific index function: $$F(n, x; a) = \max\{x, 1\} - \log(\max\{x, 1\}) + \log(n/a)$$ where $n$ is the number of pulls, $x$ is a measure of information about the sign, and $a$ is the cost of an error on that arm.

Key Insights: The M-Shape Allocation and Beating the Oracle

To validate their theory, the authors tested FWT against existing algorithms (APT and LSA) and a theoretical Non-Adaptive Oracle (which knows the true means beforehand) using synthetic datasets like Gaussian bandits and Bernoulli-like toy problems.

The "M-Shape" Allocation

A fascinating observation from the study is how the non-adaptive oracle distributes its budget. Because it knows the underlying truth, it follows a distinctive "M-shaped" sampling strategy.

M-shaped sampling allocation strategy

As seen in the allocation curves, the oracle ignores arms that are "too hard" (too close to the threshold to be reliably identified within the budget) and "too easy" (already easily identifiable). Instead, it focuses its sampling effort entirely on the middle ground, creating an M-shaped distribution across the arms.

Beating the Oracle

In most bandit settings, an "oracle" that knows the true parameters represents the ultimate performance ceiling. Counter-intuitively, the authors demonstrate that adaptive algorithms can actually outperform the non-adaptive oracle in this fixed-budget thresholding setting.

Because an adaptive algorithm observes data as it arrives, it can capitalize on early luck. If an arm's sign becomes obvious early on due to favorable noise, the algorithm can immediately stop sampling it and reallocate that budget to harder arms. A fixed, non-adaptive oracle cannot adjust its strategy on the fly, giving adaptive methods a distinct empirical advantage.

Key Results

  • Theoretical Superiority: FWT is proven to be within a factor of 4 of the non-adaptive oracle's exponent. This is a massive leap forward; previous bounds for APT were off by a factor of 32, and LSA by over 16,000. The authors effectively improved the known constant for LSA by a factor of 4,005.
  • Empirical Performance: In simulations, FWT and LSA consistently outperformed the non-adaptive oracle. In scenarios where all arms were equally difficult (where the oracle defaults to uniform sampling), the adaptive algorithms proved significantly more efficient.
  • Unified Analysis: Beyond FWT, the paper provides a "master proof" that can be used to derive loss bounds for an entire class of index-based algorithms.

Limitations and Future Work

While the paper makes significant strides, several open challenges remain:

  • Separable Losses: The current analysis assumes the total loss is a linear, separable sum of individual arm losses. Future work could extend this framework to more complex, non-linear objective functions.
  • Closing the Gap: Although reducing the theoretical gap from 16,000 to a factor of 4 is a major achievement, a gap between adaptive bounds and the non-adaptive oracle still exists.
  • Theoretical Characterization of Adaptivity: The paper empirically demonstrates that adaptive algorithms beat the oracle and provides an intuitive explanation. However, a rigorous theoretical characterization of this "adaptivity bonus" in fixed-budget settings remains an exciting avenue for future research.

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 methodsempirically 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 Odalric-Ambrym Maillard 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