Inference for Batched Bandits
  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.
