Debiasing Samples from Online Learning Using Bootstrap
This addresses bias estimation issues for researchers and practitioners using adaptive policies in online learning, offering a practical solution without reliance on conditional propensity scores, though it is incremental as it builds on existing debiasing methods.
The paper tackles the problem of biased sample averages in online learning experiments by proposing a bootstrap-based procedure to debias samples without requiring reward distribution knowledge, applicable to any adaptive policy, and demonstrates effective bias reduction for popular multi-armed bandit algorithms like ETC, UCB, TS, and ε-greedy.
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.