Source-linked AI summary
An optimal algorithm for the Thresholding Bandit Problem
Andrea Locatelli, Maurilio Gutzeit, Alexandra Carpentier
TL;DR
The paper studies fixed-budget thresholding bandits, where the learner must identify arms above a threshold with a given precision. It introduces a parameter-free algorithm that adapts without knowing key problem parameters. The authors prove matching upper and lower bounds, establishing order-optimal fixed-budget performance for the TBP setting.
Problem
The paper addresses the unresolved fixed-budget problem of identifying threshold-exceeding arms with optimal error bounds without assuming additional problem information.
Method
The authors introduce a parameter-free strategy based on an original heuristic that does not require the horizon, complexity H, or sub-Gaussian constant R.
Results
The strategy reaches, up to constants, the optimal expected loss for TBP and closes the fixed-budget gap without requiring knowledge of H.
Takeaways & Limitations
The results provide an order-optimal fixed-budget strategy for TBP and extend the approach to active level-set detection, classification, and anomaly detection.
Takeaways & Limitations
The formal guarantees assume R-sub-Gaussian arm distributions and impose theorem-specific conditions such as bounds on K and T.
Abstract
from arXiv · showhide
We study a specific \textit{combinatorial pure exploration stochastic bandit problem} where the learner aims at finding the set of arms whose means are above a given threshold, up to a given precision, and \textit{for a fixed time horizon}. We propose a parameter-free algorithm based on an original heuristic, and prove that it is optimal for this problem by deriving matching upper and lower bounds. To the best of our knowledge, this is the first non-trivial pure exploration setting with \textit{fixed budget} for which optimal strategies are constructed.
1. Introduction
The paper studies Thresholding Bandits, where a learner identifies arms above a threshold under a fixed sampling budget. It addresses an open fixed-budget complexity gap by introducing a parameter-free strategy with matching upper and lower bounds.
- Problem setting: The Thresholding Bandit Problem asks learners to identify arms whose means exceed a threshold after a fixed number of samples.It is a combinatorial pure exploration stochastic bandit problem, with precision determining how arms near the threshold are treated.
- Relation to prior problems: Unlike TopM, which selects the M highest-mean arms, TBP selects every arm above a meaningful threshold such as an efficiency or correctness criterion.The paper argues that threshold-based selection is more relevant in applications where options must exceed a natural standard.
- Problem setting: The fixed-budget setting maximizes the probability of returning the correct set for a given budget, whereas fixed confidence minimizes samples for a target error probability.The paper emphasizes that results generally do not transfer between these settings without additional problem information.
- Research gap: Fixed-budget TBP lacked a known problem-dependent complexity H* governing the exponential error bound, despite related fixed-confidence results.For TBP, existing results left H* between 0 and a logarithmic-factor upper bound, with the lower bound known only for fixed confidence.
- Contribution: The paper introduces a parameter-free algorithm and proves that its fixed-budget TBP guarantees close the gap up to constants.The strategy does not require the complexity H or other problem parameters, while the paper's results include matching upper and lower bounds.
2. The Thresholding Bandit Problem
The Thresholding Bandit Problem asks a learner to identify arms whose means exceed a threshold after a fixed horizon, allowing precision around the threshold. The paper introduces parameter-free APT and shows matching fixed-budget bounds, establishing order optimality under sub-Gaussian assumptions.
- 2.1. Problem formulation: The problem is to identify, after T rounds, arms above or below threshold τ up to precision ϵ, while allowing mistakes within the 2ϵ band around τ.Arms above τ+ϵ should be accepted and arms below τ−ϵ rejected.
- 2.2. A lower bound: The paper gives a non-asymptotic lower bound showing that every algorithm incurs error at least exp(−3T/H −4 log(12(log(T) + 1)K)) on one of the constructed Gaussian problems.The lower bound remains valid even when the learner knows the arm gaps and distribution shape.
- 2.3. Algorithm APT and associated upper bound: APT is order optimal for fixed-budget thresholding when the horizon is sufficiently large, matching lower bounds up to constants and a logarithmic term that vanishes in the relevant regime.The result holds over problems with bounded complexity and sub-Gaussian constant.
- 2.3. Algorithm APT and associated upper bound: APT requires no knowledge of the horizon, complexity H, or sub-Gaussian constant R, while its upper bound holds for every R-sub-Gaussian problem.This parameter-free property contrasts with upper-confidence approaches that require problem-dependent information.
- 2.4. Discussion: Existing CSAR bounds contain a gap relative to the fixed-budget lower bound, whereas APT removes that gap through a parameter-free strategy.The paper attributes CSAR’s gap to its successive-reject structure with fixed, non-adaptive rejection phases.
3. Extensions of our results to related settings
The paper extends its thresholding approach to best-arm identification, cumulative reward maximization, active level-set detection, active classification, and active anomaly detection. These extensions rely on additional information or a simple transformation of observations.
- Active level set detection: A simple indicator transformation converts active level-set detection into a thresholding bandit problem, covering active classification and active anomaly detection.For each sample, the transformation records whether it exceeds a cutoff level, producing Bernoulli observations whose means are the relevant exceedance probabilities.
- Best arm identification and cumulative reward maximization: With known highest mean, best-arm identification achieves error probability of order exp(−cT/H), whereas without it the minimax simple regret has an extra log(K) factor.The stronger guarantee depends on providing the highest mean to the learner.
- Best arm identification and cumulative reward maximization: When the highest arm mean is known, APT simultaneously solves best-arm identification and cumulative reward maximization.The paper presents this as counterintuitive because these objectives ordinarily favor different exploration strategies.
- Experiments: Figure 1 compares average error across horizons on a logarithmic scale for six methods in three Bernoulli experiments.The experiments vary the arrangement of arm means around the threshold.
- TopM problem: With the relevant arm means available, the thresholding strategy extends to TopM identification and outperforms cited fixed-budget results.The construction returns the estimated threshold-exceeding set as the M optimal arms when the Mth and (M+1)th means are known.
4. Experiments
The experiments compare APT with uniform allocation, tuned and untuned UCB-type strategies, and CSAR across three Bernoulli configurations. APT is generally competitive with methods given extra problem information, while poor parameter choices substantially reduce accuracy.
- Experimental setup: The comparison includes state-of-the-art CSAR, uniform allocation, UCB-type adaptations, and APT across three Bernoulli experiments.The experiments use 5,000 simulated games with τ = 1/2, ϵ = 0.1, K = 10, and T = 500.
- Compared methods: Uniform allocation is optimal when all arms are equally difficult to classify, whereas UCB-type performance depends on choosing its exploration parameter appropriately.The experiments include parameter values that explore too little, optimally, or too much.
- Compared methods: CSAR is specialized here by classifying arms according to their distance from the threshold and rejecting the arm farthest from it at each phase.In this setting, CSAR behaves as a successive-reject-type strategy.
- Results: APT is only outperformed by methods given the problem complexity or an additional optimal parameter choice.Other parameter choices can perform as poorly as the naive uniform-allocation strategy.
- Results: The appendix reports effects consistent with the main experimental comparison.The paper states that the same parameter-sensitivity effects appear in further results.
A.1. Proof of Theorem 1
The lower-bound proof constructs Gaussian instances with identical threshold gaps and complexity, then uses concentration, change of measure, and a union of classification events. It shows that some instance forces error of order exp(−cT/H).
- Lower-bound construction: Any algorithm makes an error of order at least exp(−cT/H) on at least one constructed instance.The proof establishes the lower bound through Gaussian instances and a change-of-measure argument.
- Step 0: Setting and notations: The constructed problems share the same complexity H because flipping an arm across the threshold preserves each arm’s threshold gap.The proof uses Gaussian distributions with means ±∆i and variance 1, then defines product distributions differing in one arm.
- Step 2: A change of measure: A change of measure compares the event that an algorithm classifies an arm as above the threshold under paired product distributions.The comparison isolates the samples collected from the modified arm.
- Step 3: A union of events: Because the total number of pulls is T, some arm receives at most T/H∆2 pulls, yielding the bottleneck needed for the risk lower bound.The argument combines positive pull counts with the complexity definition.
A.2. Proof of Theorem 2
The upper-bound proof identifies a high-probability event on which APT accepts arms above τ + ϵ and rejects arms below τ − ϵ. On that event the loss is zero, and its complement has probability bounded exponentially in T/H.
- Step 4: Conclusion: The proof translates empirical gap inequalities into correct threshold decisions for arms outside the 2ϵ band.Arms inside the band may be mistaken without contributing to the loss under the stated objective.
- Step 1: Concentration of the empirical KL: The proof constructs the concentration event from sub-Gaussian martingale inequalities over arms and logarithmic peeling scales.There are fewer than (log(T) + 1)K combinations in the union bound.
- Steps 2–3: Pull allocation: APT’s pull allocation guarantees a sufficiently sampled arm, which supports lower bounds on the pulls received by the remaining arms.The proof uses initialization and the condition T ≥ 2K to establish the required allocation relation.
- Step 4: Conclusion: APT incurs zero loss on the concentration event because it accepts all arms above τ + ϵ and rejects all arms below τ − ϵ.The proof therefore reduces the expected loss to the probability that the concentration event fails.
- Step 1: Concentration of the empirical KL: The failure probability is bounded by 2(log(T) + 1)K exp(−T/(64R2H)).A union bound covers the arm and peeling-index combinations.
A.3. Proof of Theorem 3
The proof bounds how often sub-optimal arms are pulled on a favorable event, then shows the best arm is selected at the horizon.
- Step 3: Conclusion: Because the best arm is pulled more than T/2 times, the algorithm selects it at the end of the horizon.
- Step 1: A favorable event: A favorable event is constructed as an intersection of concentration events whose probability is lower-bounded using a sub-Gaussian martingale inequality and a union bound.
- Step 2: The wrong arm at the wrong time: Assuming a sub-optimal arm is pulled late, the proof compares lower and upper bounds at its last pull to derive the pull-count bound.
- Step 2: The wrong arm at the wrong time: The contradiction follows from combining the resulting condition with δ = 1/18, ruling out excessive late pulls of a sub-optimal arm.
A.4. Proof of Theorem 4
The proof uses concentration events to bound sub-optimal pulls and then derives expected pseudo-regret, recovering the classical UCB1 bound when δ = 1.
- Step 3: Conclusion: The expectation is upper-bounded by combining the favorable-event bound with the worst-case contribution from its complement.
- Step 1: A favorable event: Hoeffding’s inequality and a union bound control the probability that the concentration event fails across times and arms.
- Step 2: Bound on pulls of sub-optimal arms: On the favorable event, the algorithm’s decision rule yields a bound on the final pull count of each sub-optimal arm.
- Step 3: Conclusion: Setting δ = 1 recovers the classical bound of the UCB1 algorithm.
B. Further Experimental Results
The experiments evaluate Gaussian arms across three settings, displaying average error logarithmically as the horizon varies.
- Only the correctly tuned UCBE algorithm outperforms APT in the Gaussian simulations.
- Figure 2 plots average error for Experiments 1–3 on a logarithmic scale against the horizon.