# Debiasing Samples from Online Learning Using Bootstrap

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 57 references that are in the map.
- First posted on arXiv 31 Jul 2021.

## Builds on (most cited first, 22 of 22)

- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [Doubly Robust Off-policy Value Evaluation for Reinforcement Learning](https://mlsanity.com/paper/1511.03722/) (2015)
- [Recommendations as Treatments: Debiasing Learning and Evaluation](https://mlsanity.com/paper/1602.05352/) (2016)
- [More Robust Doubly Robust Off-policy Evaluation](https://mlsanity.com/paper/1802.03493/) (2018)
- [Multi-armed Bandit Models for the Optimal Design of Clinical Trials: Benefits and Challenges](https://mlsanity.com/paper/1507.08025/) (2015)
- [Confidence Intervals for Policy Evaluation in Adaptive Experiments](https://mlsanity.com/paper/1911.02768/) (2019)
- [Bootstrapped Thompson Sampling and Deep Exploration](https://mlsanity.com/paper/1507.00300/) (2015)
- [Accurate Inference for Adaptive Linear Models](https://mlsanity.com/paper/1712.06695/) (2017)
- [Why Adaptively Collected Data Have Negative Bias and How to Correct for It](https://mlsanity.com/paper/1708.01977/) (2017)
- [Bootstrapping Upper Confidence Bound](https://mlsanity.com/paper/1906.05247/) (2019)
- [Garbage In, Reward Out: Bootstrapping Exploration in Multi-Armed Bandits](https://mlsanity.com/paper/1811.05154/) (2018)
- [On Multi-Armed Bandit Designs for Dose-Finding Clinical Trials](https://mlsanity.com/paper/1903.07082/) (2019)
- [Statistical Bootstrapping for Uncertainty Estimation in Off-Policy Evaluation](https://mlsanity.com/paper/2007.13609/) (2020)
- [On the bias, risk and consistency of sample means in multi-armed bandits](https://mlsanity.com/paper/1902.00746/) (2019)
- [Are sample means in multi-armed bandits positively or negatively biased?](https://mlsanity.com/paper/1905.11397/) (2019)
- [Estimation Considerations in Contextual Bandits](https://mlsanity.com/paper/1711.07077/) (2017)
- [Mitigating Bias in Adaptive Data Gathering via Differential Privacy](https://mlsanity.com/paper/1806.02329/) (2018)
- [Thompson sampling with the online bootstrap](https://mlsanity.com/paper/1410.4009/) (2014)
- [A Survey of Online Experiment Design with the Stochastic Multi-Armed Bandit](https://mlsanity.com/paper/1510.00757/) (2015)
- [More Efficient Off-Policy Evaluation through Regularized Targeted Learning](https://mlsanity.com/paper/1912.06292/) (2019)
- [New Insights into Bootstrapping for Bandits](https://mlsanity.com/paper/1805.09793/) (2018)
- [Improving offline evaluation of contextual bandit algorithms via bootstrapping techniques](https://mlsanity.com/paper/1405.3536/) (2014)

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

- [Avoiding the Price of Adaptivity: Inference in Linear Contextual Bandits via Stability](https://mlsanity.com/paper/2512.20368/) (2025)
- [Design Experiments to Compare Multi-armed Bandit Algorithms](https://mlsanity.com/paper/2603.05919/) (2026)
- [Orthogonal Bootstrap: Efficient Simulation of Input Uncertainty](https://mlsanity.com/paper/2404.19145/) (2024)

## Abstract (arXiv)

It has been recently shown in the literature that the sample averages from online learning experiments are biased when used to estimate the mean reward. To correct the bias, off-policy evaluation methods, including importance sampling and doubly robust estimators, typically calculate the conditional propensity score, which is ill-defined for non-randomized policies such as UCB. This paper provides a procedure to debias the samples using bootstrap, which doesn't require the knowledge of the reward distribution and can be applied to any adaptive policies. Numerical experiments demonstrate the effective bias reduction for samples generated by popular multi-armed bandit algorithms such as Explore-Then-Commit (ETC), UCB, Thompson sampling (TS) and ε-greedy (EG). We analyze and provide theoretical justifications for the procedure under the ETC algorithm, including the asymptotic convergence of the bias decay rate in the real and bootstrap worlds.