An Experimental Design for Anytime-Valid Causal Inference on Multi-Armed
  Bandits
Biyonka Liang Iavor Bojinov
Typically, multi-armed bandit (MAB) experiments are analyzed at the end of
the study and thus require the analyst to specify a fixed sample size in
advance. However, in many online learning applications, it is advantageous to
continuously produce inference on the average treatment effect (ATE) between
arms as new data arrive and determine a data-driven stopping time for the
experiment. Existing work on continuous inference for adaptive experiments
assumes that the treatment assignment probabilities are bounded away from zero
and one, thus excluding nearly all standard bandit algorithms. In this work, we
develop the Mixture Adaptive Design (MAD), a new experimental design for
multi-armed bandits that enables continuous inference on the ATE with
guarantees on statistical validity and power for nearly any bandit algorithm.
On a high level, the MAD "mixes" a bandit algorithm of the user's choice with a
Bernoulli design through a tuning parameter $\delta_t$, where $\delta_t$ is a
deterministic sequence that controls the priority placed on the Bernoulli
design as the sample size grows. We show that for $\delta_t =
o\left(1/t^{1/4}\right)$, the MAD produces a confidence sequence that is
asymptotically valid and guaranteed to shrink around the true ATE. We
empirically show that the MAD improves the coverage and power of ATE inference
in MAB experiments without significant losses in finite-sample reward.