Abstract

Randomization tests (including permutation tests) are one of the most fundamental methods in
statistics, enabling a range of inferential tasks such as testing for (conditional) independence of random variables, constructing confidence intervals in semiparametric location models, and constructing (by inverting a permutation test) model-free prediction intervals via conformal inference. Randomization tests are intuitive, easy to implement, and exactly valid for any sample size, but their use is generally confined to independent and/or exchangeable data. Yet in many applications including clinical trials, online education, online advertising, and protein design, data is routinely collected adaptively, meaning that the aspects of the data under the data collector’s control (e.g., treatment assignments) are assigned at each time step via a (possibly randomized) algorithm that depends on all the data observed so far; such assignment algorithms include (contextual) bandit and reinforcement learning algorithms as well as adaptive experimental designs. In this paper we present a general framework for randomization testing on adaptively collected data (despite its non-exchangeability), encompassing (and in some cases improving) the few existing results on randomization testing and conformal inference for adaptively collected data, as well as many other important settings. The key to our framework is the ability to compute likelihood ratio-based weights involving known quantities based purely on the known adaptive assignment algorithm, as long as a certain proportionality condition is met. These weights can then be accounted for in our framework to conduct an exact randomization test, but in order for the test to be powerful, resamples need to be diverse yet have weights as close to equal as possible. Thus, we additionally present novel computationally tractable resampling algorithms for various popular adaptive assignment algorithms, data-generating environments, and types of inferential tasks. Finally, we demonstrate via a range of simulations our framework’s power (in the case of hypothesis testing) and narrow widths (in the case of confidence or prediction intervals produced by inverting randomization tests).