Stronger Neyman Regret Guarantees for Adaptive Experimental Design

We study the design of adaptive, sequential experiments for unbiased average treatment effect (ATE) estimation in the design-based potential outcomes setting. Our goal is to develop adaptive designs offering *sublinear Neyman regret*, meaning their efficiency must approach that of the hindsight-optimal nonadaptive design.Recent work [Dai et al, 2023] introduced ClipOGD, the first method achieving $\widetilde{O}(\sqrt{T})$ expected Neyman regret under mild conditions. In this work, we propose adaptive designs with substantially stronger Neyman regret guarantees. In particular, we modify ClipOGD to obtain anytime $\widetilde{O}(\log T)$ Neyman regret under natural boundedness assumptions. Further, in the setting where experimental units have pre-treatment covariates, we introduce and study a class of contextual ``multigroup'' Neyman regret guarantees: Given a set of possibly overlapping groups based on the covariates, the adaptive design outperforms each group's best non-adaptive designs. In particular, we develop a contextual adaptive design with $\widetilde{O}(\sqrt{T})$ anytime multigroup Neyman regret. We empirically validate the proposed designs through an array of experiments.

Consider a randomized control trial: you sequentially receive experimental units with corresponding pairs of outcomes (A/B) and you can only choose one outcome to see from each pair (as in A/B testing). A very important quantity to (unbiasedly) estimate is the average treatment effect (ATE), i.e. the average difference in rewards from A-outcomes and B-outcomes. How do you do that with estimation variance as small as possible? We first design an adaptive, sequential scheme for sampling A and B outcomes, such that it simultaneously beats every fixed design (e.g. "choose A always with probability 50%") up to a small difference that goes to 0 faster (in the number of experimental units T) than in prior work. Secondly, we design an even more adaptive sequential scheme that we call "multigroup", which takes into account the units' features to further reduce estimation variance: for instance, if units are humans, the features could be their demographics, and our scheme then beats the best fixed group-specific design on every demographic group!