Beyond the Best: Distribution Functional Estimation in Infinite-Armed Bandits

Yifei Wang, Tavor Z. Baharav, Yanjun Han, Jiantao Jiao, David TseNeurIPS 2022 · OpenReview

TL;DR

This paper moves beyond the traditional goal of finding the "best" arm in infinite-armed bandits to estimating broader properties of the reward distribution, such as the mean, median, or trimmed mean. The authors prove that while adaptive (online) sampling offers no advantage for estimating the mean, it significantly reduces sample complexity for the median and maximum, revealing a fascinating "thresholding phenomenon" in how noise affects statistical estimation.

The Infinite-Armed Bandit Setup

In the infinite-armed bandit setting, a learner has access to a virtually limitless pool of "arms." Each arm has an unknown average reward drawn from a master distribution $F$. To learn about an arm, the learner must sample it, which yields a noisy observation of its true average.

Hierarchical sampling process in infinite-armed bandits.

Historically, researchers have obsessed over Best-Arm Identification: finding the single arm with the highest average reward. However, in many real-world scenarios—like single-cell sequencing or large-scale product testing—we care about the "big picture." We might want to know the median affinity for a product, the mean reward across a population, or a trimmed mean that ignores outliers.

The core challenge is a resource allocation trade-off:

  1. How many unique arms ($n$) should you pull?
  2. How many times ($m$) should you sample each of those arms to beat down the noise?
  3. Does it help to be "online" (choosing which arm to pull next based on past results) versus "offline" (sampling everything uniformly)?

Algorithmic Approaches

The authors define a general class of indicator-based functionals—mathematical properties that depend on a specific range of the distribution (e.g., the top 1% for the maximum, or the middle 50% for a trimmed mean).

To estimate these functionals, they introduce two primary algorithmic frameworks:

  • Offline Meta-Algorithm: A "uniform" approach that picks a fixed number of arms and samples them all an equal number of times.
  • Online Meta-Algorithm: An elimination-based strategy. It starts with many arms and sequentially "throws away" arms that are statistically unlikely to fall within the target range (e.g., arms that are clearly far from the median).

To prove that their algorithms are optimal, the authors use Wasserstein distances ($W_2$ for offline and $W_\infty$ for online) to establish information-theoretic lower bounds. This quantifies exactly how much harder a problem becomes as the required accuracy ($\epsilon$) increases.

Key Insights: The Adaptivity Gap

One of the most striking findings of the paper is the adaptivity gap: the difference in efficiency between online and offline strategies.

  • No Gain for the Mean: Online sampling doesn't help for the mean. Because the mean is a global property, every arm provides equally useful information.
  • Massive Gains for the Median: For the median, being adaptive is a superpower. It allows the algorithm to focus resources only on arms near the "middle," quickly discarding the obvious high and low performers.

Furthermore, in median estimation, the authors discovered a curious thresholding phenomenon. The difficulty of distinguishing two distributions doesn't change smoothly with noise. Instead, there is a phase transition: once the noise level passes a certain threshold relative to the target accuracy, the distributions suddenly become much harder to tell apart.

Summary of Complexities

The authors successfully characterized the matching upper and lower bounds for several key functionals, clearly demonstrating where adaptive sampling shines.

Sample complexity bounds for offline vs. online estimation.

As shown in the results, estimating the median offline costs $\Theta(\epsilon^{-3})$ samples, but the online algorithm slashes this to $\tilde{\Theta}(\epsilon^{-2.5})$. Similar improvements are seen for the maximum and trimmed mean, whereas the mean remains bottlenecked at $\Theta(\epsilon^{-2})$ regardless of the strategy.

Limitations and Future Work

  • Indicator-Based Focus: The current work focuses on functionals defined by "hard" boundaries (indicator functions). Extending this to "smooth" weighting functions would be a natural next step.
  • Gaussian Assumption: The lower bounds and the thresholding phenomenon are derived assuming Gaussian noise. Exploring how these limits change with "heavy-tailed" noise could be valuable for finance or robust statistics.
  • Complex Functionals: The authors mention the Benjamini-Hochberg (BH) threshold used in multiple hypothesis testing as a prime candidate for future study using these infinite-armed bandit techniques.

Summary updated

Abstract

In the infinite-armed bandit problem, each arm's average reward is sampled from an unknown distribution, and each arm can be sampled further to obtain noisy estimates of the average reward of that arm. Prior work focuses on the best arm, i.e. estimating the maximum of the average reward distribution. We consider a general class of distribution functionals beyond the maximum and obtain optimal sample complexities in both offline and online settings. We show that online estimation, where the learner can sequentially choose whether to sample a new or existing arm, offers no advantage over the offline setting for estimating the mean functional, but significantly reduces the sample complexity for other functionals such as the median, maximum, and trimmed mean. We propose unified meta algorithms for the online and offline settings and derive matching lower bounds using different Wasserstein distances. For the special case of median estimation, we identify a curious thresholding phenomenon on the indistinguishability between Gaussian convolutions with respect to the noise level, which may be of independent interest.
BibTeX
@inproceedings{wang2022beyond,
  author = {Yifei Wang and Tavor Z. Baharav and Yanjun Han and Jiantao Jiao and David Tse},
  title = {{Beyond the Best: Distribution Functional Estimation in Infinite-Armed Bandits}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=LEffhGZw4a},
}

Loading related content...

Figure