Inference for Batched Bandits

Abstract

As bandit algorithms are increasingly utilized in scientific studies and industrial applications, there is an associated increasing need for reliable inference methods based on the resulting adaptively-collected data. In this work, we develop methods for inference on data collected in batches using a bandit algorithm. We first prove that the ordinary least squares estimator (OLS), which is asymptotically normal on independently sampled data, is not asymptotically normal on data collected using standard bandit algorithms when there is no unique optimal arm. This asymptotic non-normality result implies that the naive assumption that the OLS estimator is approximately normal can lead to Type-1 error inflation and confidence intervals with below-nominal coverage probabilities. Second, we introduce the Batched OLS estimator (BOLS) that we prove is (1) asymptotically normal on data collected from both multi-arm and contextual bandits and (2) robust to non-stationarity in the baseline reward.

References in corpus (11)

• A Contextual-Bandit Approach to Personalized News Article Recommendation
• A Reinforcement Learning System to Encourage Physical Activity in Diabetes Patients
• lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits
• Statistical inference for the mean outcome under a possibly non-unique optimal treatment strategy
• Sample Size Calculations for Micro-randomized Trials in mHealth
• Batched bandit problems
• Sequential Batch Learning in Finite-Action Linear Contextual Bandits
• Are sample means in multi-armed bandits positively or negatively biased?
• Why Adaptively Collected Data Have Negative Bias and How to Correct for It
• Mixture Martingales Revisited with Applications to Sequential Tests and Confidence Intervals
• Power Constrained Bandits

Cited by in corpus (8)

• A Closer Look at the Worst-case Behavior of Multi-armed Bandit Algorithms
• Deeply-Debiased Off-Policy Interval Estimation
• Weak Signal Asymptotics for Sequentially Randomized Experiments
• Off-Policy Evaluation of Bandit Algorithm from Dependent Samples under Batch Update Policy
• Optimal Off-Policy Evaluation from Multiple Logging Policies
• Challenges in Statistical Analysis of Data Collected by a Bandit Algorithm: An Empirical Exploration in Applications to Adaptively Randomized Experiments
• Doubly Robust Interval Estimation for Optimal Policy Evaluation in Online Learning
• Off-Policy Evaluation via Adaptive Weighting with Data from Contextual Bandits