Problem Dependent View on Structured Thresholding Bandit Problems

James Cheshire, Pierre Ménard, Alexandra Carpentier

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:

  1. Monotone TBPs (MTBP): The means of the arms are known to be strictly increasing ($\mu_1 \le \mu_2 \le \dots \le \mu_K$).
  2. 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.

Binary tree structure representing the search space for the PD-MTB algorithm

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.

Comparison of error rates across Unconstrained, Monotone, and Concave 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

Abstract

We investigate the \textit{problem dependent regime} in the stochastic \emph{Thresholding Bandit problem} (\tbp) under several \emph{shape constraints}. In the \tbp the objective of the learner is ...
BibTeX
@inproceedings{cheshire2021problem,
  author = {James Cheshire and Pierre Ménard and Alexandra Carpentier},
  title = {{Problem Dependent View on Structured Thresholding Bandit Problems}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=h54iI3XaxS},
}
Figure