Sigmoid-FTRL: Design-Based Adaptive Neyman Allocation for AIPW Estimators

We consider the problem of Adaptive Neyman Allocation for the class of AIPW estimators in a design-based setting, where potential outcomes and covariates are deterministic. As each subject arrives, an adaptive procedure must select both a treatment assignment probability and a pair of linear predictors to be used in the AIPW estimator. Our goal is to construct an adaptive procedure that minimizes the Neyman Regret, which is the difference between the variance of the adaptive procedure and an oracle variance which uses the optimal non-adaptive choice of assignment probabilities and linear predictors. While previous work has drawn insightful connections between Neyman Regret and online convex optimization for the Horvitz--Thompson estimator, one of the central challenges for the AIPW estimator is that the underlying optimization is non-convex. In this paper, we propose Sigmoid-FTRL, an adaptive experimental design which addresses the non-convexity via simultaneous minimization of two convex regrets. We prove that under standard regularity conditions, the Neyman Regret of Sigmoid-FTRL converges at a T-1/2 R rate, where T is the number of subjects in the experiment and R is the maximum norm of covariate vectors. Moreover, we show that no adaptive design can improve upon the T-1/2 R rate under our regularity conditions, establishing the minimax rate of Neyman Regret. Finally, we establish a central limit theorem and a consistently conservative variance estimator which facilitate the construction of asymptotically valid Wald-type confidence intervals.