Threshold Bandits, With and Without Censored Feedback

Jacob D. Abernethy, Kareem Amin, Ruihao ZhuNeurIPS 2016 · OpenReview

Introduction

In the classical Multi-Armed Bandit (MAB) problem, a learner pulls an arm and receives a stochastic reward, aiming to maximize cumulative reward over time by balancing exploration and exploitation. However, many real-world scenarios do not offer continuous rewards; instead, they operate on a "pass/fail" condition dictated by a specific threshold.

Consider a logistics problem like FedEx routing: a package must arrive by a specific deadline (the threshold). If the travel time (the random sample) is less than the deadline, the delivery is successful. Crucially, the "best" route might change depending on whether the deadline is tight or loose.

This paper introduces the Threshold Bandit, a variant of the MAB problem where rewards are binary and depend on whether a hidden sample $X$ meets a known threshold $c$. The authors explore how to navigate this environment under two distinct feedback conditions: uncensored and censored feedback.

The Core Challenge: Censored vs. Uncensored Feedback

The difficulty of a Threshold Bandit problem hinges entirely on what information the learner receives after pulling an arm:

  1. Uncensored Feedback: The learner always observes the actual value of the sample $X$ after pulling the arm, regardless of whether it met the threshold.
  2. Censored Feedback: The learner only observes $X$ if it fails to meet the threshold (known as right-censoring). If the sample succeeds, the learner only knows that it passed, but not by how much.

Methodology: Adapting UCB for Thresholds

To tackle these settings, the authors introduce three main methodological advances, moving beyond traditional Upper Confidence Bound (UCB) analysis:

  • A Potential Function Perspective on UCB: The authors provide a novel proof for the standard UCB algorithm using a "potential function" that tracks the accumulation of uncertainty. This technique proves far more flexible for the complex, distribution-based estimation required in threshold bandits.
  • DKWUCB (Dvoretzky-Kiefer-Wolfowitz UCB): Designed for the uncensored case, this algorithm uses the DKW inequality to estimate the entire survival function (the probability that a sample exceeds a value) of each arm. This allows the learner to dynamically pick the best arm for any given threshold $c^t$.
  • KMUCB (Kaplan-Meier UCB): For the censored case, the authors adapt the Kaplan-Meier estimator—a staple of survival analysis—into a bandit framework. Because censoring obscures data and makes learning harder, KMUCB employs an "arm elimination" strategy within epochs to prune sub-optimal choices.

Key Insights and Theoretical Results

As a theoretical paper, the evaluation focuses on mathematical proofs demonstrating the upper and lower bounds of "regret"—the difference between the learner's performance and the optimal strategy.

Uncensored Bandits: Uniform Convergence

In the uncensored case, the DKW inequality ensures that the empirical distribution converges to the true distribution uniformly across all possible thresholds. Surprisingly, this means the threshold bandit is essentially no harder than the standard MAB, despite having a much larger "policy space" where the optimal arm can change every round.

  • Result: The DKWUCB algorithm achieves a regret bound of $O(\sum_{i=2}^K \frac{\log T}{\min_{j \in M} \Delta_i(j)})$. This matches the logarithmic growth of standard UCB, proving that threshold complexity doesn't slow down learning if feedback is fully visible.

Censored Bandits: The Order of Information Matters

In the censored setting, the sequence in which thresholds $c^t$ are presented dictates the learning rate.

  • Adversarial Order: If thresholds are presented from smallest to largest, the learner gains very little information about high-threshold performance from low-threshold trials. The authors prove a lower bound showing that no algorithm can do better than a regret scaling linearly with $m$ (the number of unique thresholds).
  • Optimistic Order: If thresholds go from largest to smallest, information flows efficiently. A sample that passes a high threshold is mathematically guaranteed to pass a lower one.
  • Cyclic Permutations: If thresholds arrive in a repeating cycle (1, 2, ..., m, 1, 2, ...), it represents a middle ground. The KMUCB algorithm achieves a regret bound that scales with $\log m \cdot \log T$. This proves that efficient learning is possible with censored data, provided the environment isn't actively hiding information through an adversarial sequence.

Limitations and Future Directions

While the paper establishes foundational bounds for Threshold Bandits, it notes several limitations:

  • Rigid Assumptions on Order: The analysis for the censored case relies on specific threshold sequences (like cyclic permutations). The authors note they could not prove the same bounds for a "uniformly random" sequence of thresholds, which would be a more natural assumption for many real-world applications.
  • Tightness of Bounds: The KMUCB regret bound could likely be sharpened, particularly by improving the constants and the relationship between the numerator and denominator in the regret formula.
  • Practical Implementation: The paper does not address the computational overhead of maintaining empirical distributions or Kaplan-Meier estimators in high-throughput, real-time systems. Future empirical work is needed to bridge this theoretical framework with production environments.

Summary updated

Abstract

We consider the \emph{Threshold Bandit} setting, a variant of the classical multi-armed bandit problem in which the reward on each round depends on a piece of side information known as a \emph{threshold value}. The learner selects one of $K$ actions (arms), this action generates a random sample from a fixed distribution, and the action then receives a unit payoff in the event that this sample exceeds the threshold value. We consider two versions of this problem, the \emph{uncensored} and \emph{censored} case, that determine whether the sample is always observed or only when the threshold is not met. Using new tools to understand the popular UCB algorithm, we show that the uncensored case is essentially no more difficult than the classical multi-armed bandit setting. Finally we show that the censored case exhibits more challenges, but we give guarantees in the event that the sequence of threshold values is generated optimistically.
BibTeX
@inproceedings{abernethy2016threshold,
  author = {Jacob D. Abernethy and Kareem Amin and Ruihao Zhu},
  title = {{Threshold Bandits, With and Without Censored Feedback}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2016},
  url = {https://openreview.net/forum?id=3wvzoRZfBtj},
}
Figure