Stronger Neyman Regret Guarantees for Adaptive Experimental Design

We thank the reviewer for the positive assessment of our paper!

We would like to comment/expand on the point about the lower bounds for the contextual multigroup design: The primary goal of our manuscript on that front is to introduce the multigroup approach to the sequential ATE estimation literature, and to obtain the first sublinear multigroup regret bound. We would like to highlight that even the O(sqrt(T)) multigroup bound that we obtain is substantially non-trivial — due among other things to the unbounded gradients of the loss functions, which with more naive approaches (e.g. by adding noise to smooth them out) could lead to super-sqrt(T) regret bounds (as well as the other technical challenges discussed in Section 4.3).

Lower bounds in multigroup settings are to our knowledge unresolved in the online learning community, and as such present a difficult challenge even beyond sequential ATE estimation, so we therefore consider it fair to leave this challenge to follow-up work. We, however, conjecture that the O(sqrt(T)) multigroup regret that we obtained is in fact a tight minimax rate over all families of groups, and give the following brief discussion below (which we would be happy to include in some form in the revision of our paper if you'd like):

Of course, any lower bound from the non-contextual setting also serves as a lower bound for the multigroup setting (as each group sequence separately must obey such a lower bound). In the non-contextual setting, we were able to match the very recently and independently obtained (Li et al (2024), arXiv preprint arXiv:2410.05552) lower bound of Omega(log T) by leveraging the specific structure (strong convexity) of our objective.

However, as the multigroup algorithm generally requires balancing the competing interests of multiple arbitrary groups at once, the O(log(T)) bound would appear to be too optimistic in this setting. Intuitively, note the following bottleneck that would need to be eliminated to go beyond O(sqrt(T)) rates: while the group-specific sub-learners in the method can obtain O(log(T)) regret on their own groups (by exploiting the strongly convex structure), the regret term that comes from aggregating over the sub-learners has O(sqrt(T)) magnitude, thus introducing “overhead” that makes the overall multigroup regret bound O(sqrt(T)) despite the better performance of each group’s algorithm individually.

We thank the reviewer for the positive assessment of our paper, in terms of both its contributions and writing, and for the interesting questions! To address your points in the Strengths and Weaknesses section:

1. Adapting our theory to the Hajek estimator could indeed be a potential follow-up direction. However, such an adaptation would pose significant technical challenges: its variance, which Neyman regret would aim to track, is nonconvex in the propensity weights due to the normalization involved. As such, our online convex optimization-based machinery is not directly applicable there and would likely require substantial modifications and/or relaxed objectives to obtain Neyman regret results similar to ours. At the same time, if one is not committed to using specifically the Hajek estimator, and is generally interested in double robustness or just in further reducing variance compared to the IPW estimator that we study, we believe our methods could be applied to the augmented IPW estimator with significantly less anticipated modifications, as augmented IPW estimators preserve the nature of the optimization problem with respect to the propensity weights.

2. In terms of comparing our propensity weight clipping approach to the methods of Hadad et al: We explicitly enforce gradually loosening clippings on our treatment probabilities using a monotonic clipping function (while preserving the form of the adaptive IPW estimator), while Hadad et al, somewhat agnostically to the algorithm that produces the propensity weights, re-weigh the estimator by external weights that partially cancel out the propensity weight blowup. These methods, even though both aim at resolving the challenge of vanishing propensities, thus appear quite distinct in nature.

3. The Hadad et al paper, whose reweighting strategies accomplish asymptotic normality under some mild assumptions, indeed might serve as a potential lead for designing CLT-based CIs for our methods, as you point out. And in general, since the CI construction presented in Theorem 3.7 is quite conservative and doesn't leverage our much faster Neyman regret rates, improving it is a challenging but important avenue of future work. That being said, the Hadad et al results are restricted to the superpopulation (i.i.d.) setting and appear technically nontrivial to rigorously extend to the finite population setting. Of course, the intuitive / black-box nature of their proposed reweightings could still allow practitioners to use the Hadad et al approach as a heuristic add-on to our adaptive designs.

4. For the multigroup extension, please note that our method does not aim to identify the best subgroup: instead, it takes as input a given family of groups and optimizes the variance on each of them simultaneously. This makes the multigroup setting different from other existing sequential frameworks for ATE estimation that we are aware of. Within this setting, pretreatment covariates are in fact quite directly used to enhance efficiency: our groups are defined by covariates, and as such our multigroup algorithm takes advantage of any present group-specific homogeneity in the data (for the simplest example, just consider e.g. a finite covariate space X, and define a group for each x \in X; then the multigroup design will compete with the best propensity weight for every covariate). Also, note that for a complementary direct use of covariates, our framework can take advantage of estimating treatment and control outcomes via a model f(x), augmenting the IPW estimators we study into AIPW; however, our focus in this paper is on optimizing the propensities while staying agnostic to the IPW/AIPW distinction.

5. Please find bias, variance and CI plots at: https://imgur.com/1P9sqbZ

We thank the reviewer for the positive assessment of our paper and for the interesting questions.

The classical work by Wald is indeed the historical underpinning of much of the research in sequential experimental design, particularly on the hypothesis testing side. Our work shares the broad motivation of increasing statistical efficiency through adaptivity, though we do not explicitly deal with some of the notions that Wald focused on such as early stopping. To trace an early mention of the more specific problem of adaptive Neyman allocation in sequential design that we consider in our paper, the work of H. Robbins “Some aspects of the sequential design of experiments” (1952) (which came out shortly after Wald’s seminal treatise) mentions it as an important open problem. These references are mentioned in passing e.g. in [DGH’23]; we will add them to our paper along with brief discussion.

Next, in terms of the definition for h, thank you for pointing out the notational discrepancy. Our arguments in fact don’t require h to be integer-valued, so we revert to the continuous range in the revision.

Next, thank you for sharing the references on covariate balancing / distributional discrepancy based experimental designs. While these are conducted in the non-adaptive setting, they share the objective of optimizing the estimation variance, which we pursue in our work. They also offer a principled way to exploit covariates, by assuming the mapping between covariates and outcomes is linear (and trading off robustness and covariate balance). We will cite and discuss these in the final manuscript.

That being said — based on our reading of these references — there appear to be some important differences between the covariate balancing setting and our multigroup setting, making our contextual setting qualitatively different. (i) Our designs adaptively vary the treatment assignment probabilities to match the performance of the best treatment probability in hindsight. The covariate balancing papers focus on fixing the marginal treatment probabilities (0.5 in the former paper, arbitrary q in the latter) and then obtaining the best treatment assignment vector optimizing the estimation variance (more specifically, the balance-robustness tradeoff). (ii) The covariate balancing work is intimately connected to ridge regression. By contrast, our multigroup design doesn’t assume anything about the nature of the mapping from covariates to features. Instead of balancing covariates over all linear models, it optimizes efficiency for all groups simultaneously, more in the spirit of a “multiobjective” problem with respect to the groups.

So in this way, the two settings, while both are covariate-based and target optimal estimation variance, appear to be quite distinct without one implying the other. But we agree with the reviewer that the covariate balancing approach is worthwhile and potentially fruitful to investigate in the Neyman regret setting that we study — e.g. for obtaining Neyman regret bounds in the spirit of linear bandits.

We thank the reviewer for the careful reading and positive assessment of our paper! We will implement the bullet points in Other Comments and Suggestions.

The suggested paper of Neopane et al (2025) is an independent and concurrent work to ours. We are happy to cite and briefly discuss it. Its setting is closely related to that of our paper, but with the substantial difference that they assume a much milder environment in which outcomes/rewards are generated from some joint distribution with time-stationary means and variances (in contrast to our finite-population setting which makes no such assumptions) — and this milder setting crucially enables them to design an algorithm based on UCB-like optimistic policy tracking approach.