Introduction
In standard multi-armed bandit problems, the objective is typically to sample different options (arms) to maximize a cumulative reward. However, the Thresholding Bandit Problem (TBP) presents a different challenge: given a fixed budget of $T$ samples, the learner must classify every arm as having a mean either above or below a known threshold $ au$.
Historically, research has focused on the "unstructured" case—where arms have no relationship to one another—or the "problem-independent" (worst-case) scenarios. This paper pivots to explore the problem-dependent regime for structured TBPs, specifically focusing on cases where the means of the arms follow specific shape constraints, such as monotonicity or concavity.
The authors reveal a surprising "blessing of structure": in the problem-dependent regime, these structured problems become essentially as easy as a one-armed bandit problem. As the sampling budget grows, the error rate becomes completely independent of the total number of arms ($K$).
The Challenge of Structured TBPs
The paper investigates two primary structural constraints:
- Monotone TBPs (MTBP): The means of the arms are known to be strictly increasing ($\mu_1 \le \mu_2 \le \dots \le \mu_K$).
- Concave TBPs (CTBP): The sequence of means follows a concave shape, rising to a peak and then falling.
The core challenge is determining how these inherent shapes influence the probability of making a mistake (misclassifying at least one arm) and designing algorithms that exploit this structure to outperform standard unstructured bounds.
Methods: Exploiting Structure
To tackle these structured environments, the authors introduce two parameter-free algorithms designed for the fixed-budget setting. Neither algorithm requires prior knowledge of specific gaps between means ($\Delta_i$) or the sub-Gaussian constant ($\sigma^2$).
PD-MTB (Problem Dependent Monotone Thresholding Bandit)
For monotone structures, the problem can be conceptualized as finding the "crossover" point where the means cross the threshold. PD-MTB treats this as a noisy binary search.
Because standard binary search is highly fragile to noisy evaluations, PD-MTB instead performs a random walk on a binary tree. If the sampled means suggest the threshold is in a certain direction, the algorithm moves down that path. If it detects a statistical inconsistency or "anomaly," it backtracks to a parent node, allowing it to probabilistically "undo" mistakes.
PD-CTB (Problem Dependent Concave Thresholding Bandit)
To handle concave structures, the authors propose PD-CTB, which utilizes a subroutine called Grad-Explore. Because a concave function rises and then falls, Grad-Explore uses estimated gradients to locate the "peak" area above the threshold. Once an arm above the threshold is identified, the concave problem effectively splits into two monotone sub-problems (one increasing sequence, one decreasing sequence). These sub-problems are then solved using the PD-MTB algorithm.
Key Insights and Results
The "One-Armed Bandit" Phenomenon
The most striking finding of the paper is that structure collapses complexity. In an unstructured TBP, the difficulty is determined by the sum of all inverse gaps ($H = \sum \Delta_i^{-2}$).
However, for both monotone and concave structures, the algorithm only needs to find the crossover points. The optimal error probability becomes proportional to $\exp(-T \Delta_{min}^2 / \sigma^2)$, where $\Delta_{min}$ is the smallest gap between any arm's mean and the threshold. Remarkably, the number of arms $K$ disappears entirely from the exponential rate. With a sufficient budget, classifying 1,000 ordered arms is fundamentally no harder than classifying a single arm.
Matching Bounds
The authors provide matching upper and lower bounds (up to universal constants) for the probability of error across different problem types.
As shown in the table above, while the problem-independent (worst-case) rates for monotone and concave problems differ ($\sqrt{\log K / T}$ vs $\sqrt{\log \log K / T}$), this paper proves that in the problem-dependent regime, they converge to the exact same fundamental limit: $\exp(-T \bar{\Delta}_{\min}^2)$.
Limitations and Future Work
While the theoretical results are strong, the authors note a few limitations:
- Large Budget Assumption: The "blessing of structure" (where $K$ drops out of the error rate) only takes effect when the budget $T$ is sufficiently large (specifically $T > \text{poly}(\log K) / \Delta_{min}^2$). For very small budgets, the total number of arms still impacts performance.
- Shape Constraints: The current study is limited to monotonicity and concavity. Future research could explore other shape constraints, such as unimodality or $s$-concavity.
- Fixed Budget vs. Fixed Confidence: This paper focuses exclusively on the fixed budget setting. Translating these structural advantages to the fixed confidence setting—where the goal is to minimize the number of samples required for a given error tolerance—remains an open area for future exploration.
Summary updated