PAC Identification of a Bandit Arm Relative to a Reward Quantile

Arghya Roy Chaudhuri, Shivaram KalyanakrishnanAAAI 2017 · DOI

Introduction

In the standard multi-armed bandit (MAB) problem, the goal is typically to identify the single best arm. However, in modern applications like drug discovery or hyperparameter optimization, the number of potential arms ($n$) can be massive or even infinite. In such regimes, finding the absolute optimum is often computationally and statistically prohibitive. This paper, originally presented at AAAI 2017, proposes a shift in perspective: instead of seeking the absolute best, we aim to identify an arm that is "good enough" relative to a reward quantile.

Problem Formulation

The authors introduce a new Probably Approximately Correct (PAC) framework for identifying an $(\epsilon, m)$-optimal arm. Formally, given $n$ arms with mean rewards $\mu_1, \dots, \mu_n$, let $\mu_{[m]}$ denote the $m$-th largest mean. The goal is to find an arm $a$ such that $\mu_a \ge \mu_{[m]} - \epsilon$ with probability at least $1 - \delta$.

Two primary settings are explored:

  1. Quantile-Finite (Q-F): Identifying an $(\epsilon, m)$-optimal arm from a finite set of $n$ arms.
  2. Quantile-Probability (Q-P): Identifying an arm in the top $\rho$ quantile of an underlying probability distribution of arms, which is particularly relevant for infinite-armed settings where $\rho = m/n$.

Proposed Algorithms

The paper introduces three key algorithms to address these settings:

  • $\mathcal{P}_1$: A two-stage approach for infinite arms. It first samples a random subset of arms (size determined by $\rho$) and then applies the Median-Elimination algorithm to find the best arm within that subset.
  • $\mathcal{F}_2$: A fully sequential, gap-adaptive algorithm for the finite case. It extends the Lower Upper Confidence Bound (LUCB) approach by maintaining confidence intervals and partitioning arms into a leader, a set of contenders, and others. It focuses sampling on "contentious" arms until the leader's lower bound is sufficiently separated from the upper bounds of arms outside the top $m$.
  • $\mathcal{P}_2$: A memory-efficient sequential algorithm designed for infinite arms. It processes arms in batches of size $M$, balancing sample complexity with hardware memory constraints.

Experimental Evaluation

The algorithms were evaluated on synthetic bandit instances with Bernoulli rewards, designed to represent different difficulty levels:

  • $\mathcal{I}_1$: A single clear winner among identical sub-optimal arms.
  • $\mathcal{I}_2$: Arms with linearly spaced mean rewards.
  • $\mathcal{I}_3$: Two distinct clusters of "good" and "bad" arms.
Comparison of total pulls across different bandit instances (I1, I2, I3).

As shown in the figure above, the sequential algorithm $\mathcal{F}_2$ consistently outperforms standard LUCB and uniform sampling across various reward distributions. Its gap-adaptive nature allows it to stop sampling clearly inferior arms early, leading to significant efficiency gains.

Scaling with Large Arm Sets

A core contribution of this work is decoupling sample complexity from the total number of arms $n$. By targeting a quantile $\rho$, the complexity becomes a function of $1/\rho$ rather than $n$.

Sample complexity scaling of F2 and P2 as the number of arms increases.

Empirical results demonstrate that while traditional methods scale poorly, the quantile-based approach remains efficient even as $n$ reaches 3,000. Furthermore, for the $\mathcal{P}_2$ algorithm, increasing the batch size (memory) significantly reduces the total number of pulls required to meet the PAC guarantee.

Conclusion

By redefining the objective of MAB exploration from absolute optimality to quantile-based optimality, this work provides a practical framework for high-dimensional and infinite-armed problems. The proposed algorithms are near-optimal in theory and demonstrate superior empirical performance, particularly in their ability to adapt to specific instance gaps and scale to large arm spaces.

Summary updated

BibTeX
@inproceedings{chaudhuri2017pac,
  author = {Arghya Roy Chaudhuri and Shivaram Kalyanakrishnan},
  title = {{PAC Identification of a Bandit Arm Relative to a Reward Quantile}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.1609/aaai.v31i1.10802},
}
Figure