Introduction
In traditional statistical setups, researchers rely on fixed-sample experiments where data collection is independent of the results observed. In these "nonadaptive" settings, the sample mean is an unbiased estimator of the true population mean. However, modern machine learning and clinical trials increasingly utilize Multi-Armed Bandits (MAB) to optimize outcomes in real-time. These algorithms learn as they go, pulling arms that appear more promising to minimize regret or identify the best option quickly.
While efficient, this adaptivity introduces complex selection biases. Recent influential research suggested a "one-size-fits-all" rule: adaptively collected data always underestimates true performance, leading to negative bias. This paper challenges that conclusion, demonstrating that the reality is more nuanced. By decomposing the experimental process, the authors show that while certain adaptive behaviors cause negative bias, others—specifically those related to stopping and choosing—induce a positive bias.
The Three Sources of Adaptivity
To understand the direction of bias, the authors decouple the MAB process into three distinct components:
- Adaptive Sampling: The rule for choosing which arm to pull at each time step based on historical rewards.
- Adaptive Stopping: The rule for deciding when to terminate the experiment based on the accumulated data.
- Adaptive Choosing: The rule for selecting which specific arm’s mean to report or estimate once the experiment has concluded.
The authors define a property called "Optimism." An optimistic rule is monotonic: if an arm yields better observed data, an optimistic rule is more likely to sample that arm again, stop the experiment (if it looks like a clear winner), or choose that arm for the final report.
The Sign of the Bias
The central finding of the paper is a "sign flip" between these components.
Negative Bias from Sampling
When an experiment has a fixed duration (no adaptive stopping) and we look at the bias of all arms, optimistic sampling rules like Upper Confidence Bound (UCB) or Thompson Sampling consistently produce negative bias. Intuitively, if an arm's mean is currently overestimated due to random noise, an optimistic sampler will pull it more often. As more samples are collected, the law of large numbers pulls the estimate back toward the true mean. Conversely, if an arm is underestimated, the sampler stops pulling it, "freezing" the negative error.
Positive Bias from Stopping and Choosing
The narrative changes when we introduce adaptive stopping or choosing. If we stop an experiment because an arm looks particularly good, we are likely stopping at a "high point" of random noise, leading to an overestimation (positive bias). Similarly, if we run a trial and only report the mean of the "best" arm (adaptive choosing), we are selecting for the arm that most likely benefited from positive noise.
Theoretical Framework: Martingale Theory and Wald’s Identity
The authors utilize martingale theory and a generalization of Wald’s first identity to prove these signs. They provide a simplified expression for bias: it is proportional to the negative covariance between the sample mean and the number of times an arm was pulled. This framework allows them to analyze complex, path-dependent algorithms by imagining a "tabular perspective"—a counterfactual table of all possible rewards that might have been observed.
Key Results and the "Practitioner's Trap"
The paper mathematically proves that popular best-arm identification algorithms, such as lil’UCB, are "monotonically increasing strategies." This means they will almost always yield a positively biased estimate of the reported arm's mean.
For practitioners, this is a critical warning. If a company uses a bandit algorithm to test new website features and stops the test once a "winner" is identified, the reported performance of that winner is likely inflated. When that feature is rolled out to the entire user base, it will likely underperform compared to the trial results. This overestimation is a much riskier scenario than negative bias, as it leads to over-investment in sub-optimal strategies.
Conclusion
This research provides a unified framework for understanding bias in adaptive experiments. By showing that the net bias is a tug-of-war between negative sampling bias and positive stopping/choosing bias, the authors move beyond the "always negative" assumption. While the paper focuses on the sign of the bias, future work remains to precisely quantify the magnitude of this bias and extend the analysis to other statistical functionals like sample variance.
Summary updated