Debiasing Samples from Online Learning Using Bootstrap

Abstract

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 $\epsilon$-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.

References in corpus (16)

• Unbiased Offline Evaluation of Contextual-bandit-based News Article Recommendation Algorithms
• Recommendations as Treatments: Debiasing Learning and Evaluation
• Counterfactual Risk Minimization: Learning from Logged Bandit Feedback
• Bootstrapped Thompson Sampling and Deep Exploration
• A Survey of Online Experiment Design with the Stochastic Multi-Armed Bandit
• Thompson sampling with the online bootstrap
• On Multi-Armed Bandit Designs for Dose-Finding Clinical Trials
• Are sample means in multi-armed bandits positively or negatively biased?
• Bootstrapping Upper Confidence Bound
• Why Adaptively Collected Data Have Negative Bias and How to Correct for It
• A Practical Method for Solving Contextual Bandit Problems Using Decision Trees
• On the bias, risk and consistency of sample means in multi-armed bandits
• More Efficient Off-Policy Evaluation through Regularized Targeted Learning
• Improving offline evaluation of contextual bandit algorithms via bootstrapping techniques
• Statistical Bootstrapping for Uncertainty Estimation in Off-Policy Evaluation
• New Insights into Bootstrapping for Bandits