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

arXiv: https://arxiv.org/abs/1905.11397 · HTML: https://mlsanity.com/paper/1905.11397/

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 May 2019.

## Built on by (most cited first, 24 of 24)

- [Off-Policy Evaluation via Adaptive Weighting with Data from Contextual Bandits](https://mlsanity.com/paper/2106.02029/) (2021)
- [A Closer Look at the Worst-case Behavior of Multi-armed Bandit Algorithms](https://mlsanity.com/paper/2106.02126/) (2021)
- [Policy Learning with Adaptively Collected Data](https://mlsanity.com/paper/2105.02344/) (2021)
- [Near-optimal inference in adaptive linear regression](https://mlsanity.com/paper/2107.02266/) (2021)
- [Metalearning Linear Bandits by Prior Update](https://mlsanity.com/paper/2107.05320/) (2021)
- [Learning from an Exploring Demonstrator: Optimal Reward Estimation for Bandits](https://mlsanity.com/paper/2106.14866/) (2021)
- [A unified framework for bandit multiple testing](https://mlsanity.com/paper/2107.07322/) (2021)
- [Stable Thompson Sampling: Valid Inference via Variance Inflation](https://mlsanity.com/paper/2505.23260/) (2025)
- [Efficient Inference Without Trading-off Regret in Bandits: An Allocation Probability Test for Thompson Sampling](https://mlsanity.com/paper/2111.00137/) (2021)
- [Challenges in Statistical Analysis of Data Collected by a Bandit Algorithm: An Empirical Exploration in Applications to Adaptively Randomized Experiments](https://mlsanity.com/paper/2103.12198/) (2021)
- [Adaptive Linear Estimating Equations](https://mlsanity.com/paper/2307.07320/) (2023)
- [Doubly Robust Interval Estimation for Optimal Policy Evaluation in Online Learning](https://mlsanity.com/paper/2110.15501/) (2021)
- [Safe Data Collection for Offline and Online Policy Learning](https://mlsanity.com/paper/2111.04835/) (2021)
- [Adaptive Off-Policy Inference for M-Estimators Under Model Misspecification](https://mlsanity.com/paper/2509.14218/) (2025)
- [Debiasing Samples from Online Learning Using Bootstrap](https://mlsanity.com/paper/2108.00236/) (2021)
- [Adaptive Identification of Populations with Treatment Benefit in Clinical Trials: Machine Learning Challenges and Solutions](https://mlsanity.com/paper/2208.05844/) (2022)
- [Replicability is Asymptotically Free in Multi-armed Bandits](https://mlsanity.com/paper/2402.07391/) (2024)
- [A characterization of sample adaptivity in UCB data](https://mlsanity.com/paper/2503.04855/) (2025)
- [Avoiding the Price of Adaptivity: Inference in Linear Contextual Bandits via Stability](https://mlsanity.com/paper/2512.20368/) (2025)
- [Algorithms for Adaptive Experiments that Trade-off Statistical Analysis with Reward: Combining Uniform Random Assignment and Reward Maximization](https://mlsanity.com/paper/2112.08507/) (2021)
- [Some performance considerations when using multi-armed bandit algorithms in the presence of missing data](https://mlsanity.com/paper/2205.03820/) (2022)
- [Entropy Regularization for Population Estimation](https://mlsanity.com/paper/2208.11747/) (2022)
- [Offline Policy Evaluation for Reinforcement Learning with Adaptively Collected Data](https://mlsanity.com/paper/2306.14063/) (2023)
- [Near-Exponential Savings for Mean Estimation with Active Learning](https://mlsanity.com/paper/2511.05736/) (2025)

## Abstract (arXiv)

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 sampling of arms, adaptive stopping of the experiment, and adaptively 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.