Are sample means in multi-armed bandits positively or negatively biased?

Jaehyeok Shin, Aaditya Ramdas, Alessandro Rinaldo

TL;DR

This paper provides a unified framework to understand the sign of bias in sample mean estimates within multi-armed bandit (MAB) problems. It decouples the effects of adaptive sampling, stopping, and arm selection, revealing that optimistic sampling leads to negative bias, while optimistic stopping and choosing lead to positive bias. This work offers a more nuanced understanding than previous research, which often focused solely on adaptive sampling.

What Problem Does This Paper Address?

In statistics, the sample mean is typically an unbiased estimator of the true mean. However, this property breaks down in adaptive settings, such as multi-armed bandits (MAB). In MAB, decisions about which arm to sample next, when to stop the experiment, and which arm to ultimately focus on are all based on previously observed data. This adaptivity introduces "selection bias," making the sample mean an unreliable estimator of the true mean. While some prior work identified negative bias due to adaptive sampling, it was unclear how other adaptive strategies, like stopping or choosing, affected this bias, and whether they could even reverse it. This paper aims to provide a comprehensive understanding of the sign of this bias by analyzing the interplay of these three adaptive components.

Methods

The authors introduce a general MAB framework and define "optimism" as a natural monotonic behavior of sampling, stopping, and choosing rules. They then derive theoretical results that precisely characterize the sign of the bias induced by each of these adaptive strategies, independently and in combination. Their core theoretical contribution is Theorem 7, which establishes that:

  • Optimistic sampling induces a negative bias.
  • Optimistic stopping induces a positive bias.
  • Optimistic choosing induces a positive bias.

The analysis is agnostic to the specific goal of the MAB experiment (e.g., minimizing regret or identifying the best arm). They also provide a key lemma (Lemma 6) that generalizes Wald's first identity to the MAB setting, which is crucial for their proofs. The paper uses martingale arguments and a tabular MAB representation for its theoretical derivations.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and uses simulated data for experimental validation.

Key Insights and Ideas

  • Decoupling Bias Sources: The paper's main contribution is disentangling the bias introduced by adaptive sampling, stopping, and choosing. This is crucial because these components can have opposing effects on the overall bias.
  • Optimism as a Unifying Concept: By defining "optimism" as a monotonic behavior, the authors create a general framework applicable to a wide range of MAB algorithms.
  • Conflicting Biases: The finding that optimistic sampling leads to negative bias while optimistic stopping/choosing leads to positive bias is a key insight. This explains why the net bias in complex MAB algorithms can be either positive or negative.
  • Challenging Prior Assumptions: The work directly contrasts with prior research that might have suggested a universally negative bias in adaptive data collection, highlighting that this is only true under specific conditions (e.g., fixed stopping time and fixed arm).
  • Practical Implications: Understanding these biases is critical for practitioners who rely on MAB for decision-making, as it can lead to over- or under-estimation of arm performance, impacting deployment and resource allocation.

Key Results

  • Theorem 7: Formally proves that optimistic sampling induces negative bias, while optimistic stopping and choosing induce positive bias.
  • Corollary 8: Demonstrates that the lil'UCB algorithm, a popular best-arm identification algorithm, is a monotonically increasing strategy and thus its chosen stopped sample mean is always positively biased.
  • Simulations: The paper includes simulations that empirically confirm the theoretical predictions for various scenarios, including UCB, Thompson sampling, greedy algorithms, sequential likelihood ratio tests, and the lil'UCB algorithm. These simulations show clear evidence of negative bias from optimistic sampling and positive bias from optimistic stopping/choosing.

Limitations and Future Work

  • Magnitude of Bias: While the paper characterizes the sign of the bias, it acknowledges that characterizing its magnitude is a harder problem, though they mention recent progress on this front.
  • Generalization to Other Functionals: The authors suggest extending their results to other functionals of the data, such as sample variance.
  • Other Bandit Algorithms: Further work could extend their findings to a broader class of bandit algorithms beyond those explicitly analyzed.
  • Hard Open Problems: The paper poses natural but difficult open problems related to these extensions.

Summary updated

Abstract

It is well known that in stochastic multi-armed bandits (MAB), the sample mean of an arm is typically not an unbiased estimator of its true mean. In this paper, we decouple three different sources of this selection bias: adaptive \emph{sampling} of arms, adaptive \emph{stopping} of the experiment, and adaptively \emph{choosing} which arm to study. Through a new notion called ``optimism'' that captures certain natural monotonic behaviors of algorithms, we provide a clean and unified analysis of how optimistic rules affect the sign of the bias. The main takeaway message is that optimistic sampling induces a negative bias, but optimistic stopping and optimistic choosing both induce a positive bias. These results are derived in a general stochastic MAB setup that is entirely agnostic to the final aim of the experiment (regret minimization or best-arm identification or anything else). We provide examples of optimistic rules of each type, demonstrate that simulations confirm our theoretical predictions, and pose some natural but hard open problems.
BibTeX
@inproceedings{shin2019are,
  author = {Jaehyeok Shin and Aaditya Ramdas and Alessandro Rinaldo},
  title = {{Are sample means in multi-armed bandits positively or negatively biased?}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
}
Figure