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.
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.
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