Stronger Neyman Regret Guarantees for Adaptive Experimental Design
Authors: Georgy Noarov
Riccardo Fogliato
Martin Andres Bertran
Aaron Roth
Venue: ICML 2025 spotlightposter (2025)
Keywords: ATE
treatment effect
adaptive experimental design
efficient causal inference
Neyman
regret
Primary area: general_machine_learning->causality
TL;DR: Novel adaptive designs for efficient contextual/noncontextual finite-population estimation of ATE

Abstract: 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.

Stronger Neyman Regret Guarantees for Adaptive Experimental Design
Georgy Noarov Riccardo Fogliato 2 Martin Bertran 2
Aaron Roth
Abstract
have low variance.
We study the design of adaptive, sequential experi- ments 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 ((VT) expected Neyman regret under mild conditions. In this work, we propose adap- tive designs with substantially stronger Neyman regret guarantees. In particular, we modify Cli- pOGD to obtain anytime Ó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 any set of possibly overlapping groups based on the covariates, the adaptive de- sign outperforms each group's best non- -daapive designs. In particular, we develop contextual adaptive design with Ö(VT) anytime multigroup Neyman regret. We empirically validate the pro- posed designs through an array of experiments.
In many cases, RCTs are sequentially: Experimental units arrive one by one, and each unit is assigned to treat- ment or control adaptively, based on previous outcomes or auxiliary information. The data-driven nature and flexibil- ity of these experiments suggest that such adaptive trials can achieve substantial efficiency gains over standard fixed designs, as shown in domains ranging from political sci- ence (Offer-Weston) et al., 2021; Blackwell al., 2022) to medicine (Chow & Chang, 2008; Villar et al., 2015; FDA, 2019). However, so far adaptive experiments have re- ceived limited attention (Hu & Rosenberger, 2006) and have been rarely used in practice due to concerns that adaptiv- ity could invalidate standard statistical guarantees (van der Laan, 2008). Indeed, classic solutions for improving es- timator efficiency in the batch setting, such as Neyman allocation (Neyman, 1992), can be nontrivial to extend to the sequential setting.
Recently, a growing body of work (Hahn et al., 2011; Kato et al., 2020; Li & Owen, 2024; Dai al., 2023; Cook et al., 2023) has made progress on this front by introducing multi- stage adaptive designs that estimate the ATE via inverse- probability weighting (IPW)-type estimators with adaptively adjusted propensity scores. I Our work contributes to this literature by developing novel adaptive sequential designs for IPW-based ATE estimation with efficiency guarantees. Crucially, our methods -unlike most existing work- are de- veloped within the finite- potile-pppultiion setting (Wager, 2024), where the ATE is defined deterministic function of the observed population rather than superpopulation parame- ter. This distinction ensures robustness to treatment effect heterogeneity and temporal data drift, challenges that can undermine conventional superpopulation-basel designs.
1. Introduction
Randomized control trials (RCTs) play central role in variety of settings where causal effects need to be accurately measured, spanning healthcare and epidemiology, policy- making, the social sciences, econometrics, e-commerce, and beyond. In the classic potential outcomes framework (Ney- man, 1923; Rubin, 1974). a central estimand the average treatment effect (ATE) - the average individual causal effect across experimental units. To obtain precise estimates of the ATE, we generally seek estimators that are unbiased and
Our Contributions We focus on the design of adaptive RCTs to estimate the ATE as efficiently as the best-in- hindsight IPW design from some benchmark class, up to
Departmeent of Computer and Information Science, University of Pennsylvania. *Amazon Web Services. Correspondence to: Georgy Noarov <gnoarov@ @ scas.upenn.edu>.
Georgy Noarov conducted part of this work as an intern at Amazon Web Services.
'In parallel, studies that fall into the multi-armed bandits literature have developed adaptive designs for finding reward- maximizing treatments (arms) policies, which is a distinct, and conflicting, objective than estimation efficiency (Zhang et al., 2020; 2021; Hadad al., 2021; Xu et al., 2016; 2024).
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Stronger Neyman Regret Guarantees for Adaptive Experimental Design
error terms. Specifically, we aim minimize the Neyman regrer (Kato et al., 2020; Dai et al., 2023) measure comparing the variance of our adaptive estimator to that of the ceriance-minimizinn nonadaptive Bernoulli trial where units are treated with some fixed probability. Currently, to our knowledge Dai et al. (2023)'s ClipOGD method is the only adaptive design achieving sublinear Neyman regret in the popullaooplltion setting. This method guarantees O(VT) expected regret for any T-unit trial under moment- bounded potential outcomes. However, two important ques- tions arise:
experimental units corresponding to the groups in G. Criti- cally, we also allow for overlapping groups, i.e., units can simultaneously belong to multiple groups. A key challenge here is to balance the treatment probabilities in a way that balances the efficiency of the ATEs estimates across groups. Our proposed design leverages a variation of the "sleeping experts" approach (Blum & Lykouris, 2020; Acharya et al., 2024) used in the online learning literature (Lee et al., 2022: Deng et al., 2024), that deals with the limited feedback and the fact that the observed objective values do not live in an a-priori bounded range. The method achieves O(vT) multigroup Neyman regret. We also empirically validate its performance.
I. Can we develop designs with better regret rates? Dai al. (2023) conjectured that OVTT) is the minimax Neyman rate.
Our multigroup guarantees can be interpreted through the lens of group ATE (GATE) estimation (Chernozhukov et al., 2017; Semenova & Chernozhukov, 2021; Zimmert & Lech- ner, 2019). GATE occupies middle ground between ATE, which measures the average effect over the entire sequence, and CATE (conditional ATE), which measures the ATE conditionally on each covariate vector, Existing works on GATE, however, are mainly focused on learning data-driven disjoint groups improve overall ATE estimation. In con- trast, our objective is to simultaneously ensure efficient GATE inference for any family of arbitrarily overlapping groups. This is related in motivation (though distinct in technique) to the recent work of (Kern et al., 2024) who use "multicccuray"" to make CATE inference robust to certain kinds of distribution shift.
II. Can develop context-aware designs that use pre- treatment covariates to improve efficiency?
In this work, we answer both these questions affirmatively:
Contribution I: Exponentially Improved Noncontextual Neyman Regret Bound. We show that, under natural strengthening of Dai et al. (2023)'s assumptions on the outcomes, we can modify ClipOGD to attain an anytime- valid Neyman regret bound of Olog T). To achieve this speedup, we leverage the strong convexity of the Neyman objective under our stricter lower-bounding assumption on the outcomes, which as we show leads near-logarithmic regret via techniques introduced by (Hazan et al., 2007). Moreover, it can be shown that even under the weaker out- come lower bound assumption of Dai et al. (2023), our adaptive design can be tweaked to have the asymptotic ef- ficiency of (1 + c) V + Ö log for any e <> 0, where V* denotes the optimal nonadaptive design variance; the interpretation is that any (1 + e) -multiplicaaiie approxima- tion to the optimal variance can be attained at this fast rate. We validate the greater efficiency of our proposed design against that of ClipOGD through suite of experiments on synthetic and real-world data.
We expect that such multigroup efficiency guarantees can be broadly useful, and hope future work will study multigroup adaptive designs beyond the sequential finite-population setting that we focus on in this paper.
For an additional discussion of related work, including rele- vant independent work in the superpopulation setting, please see Appendix A.
Organization In Section 2, we introduce our general set- ting and objectives. In Section 3, we focus on the (vanilla) non-contextual setting, and present and analyze our adaptive design ClipOGDSC which achieves logarithii Ney- man regret. We prove the main regret bound in Theorem 3.2 and demonstrate further guarantees on the adaptive design.
Contribution II: Adaptive Designs with Contextual Ney- man Regret Guarantees. We next develop a novel adap- tive design MGATE (Multi-Group ATE) that leverages pre- treatment covariates to improve efficiency relative to the non-contextual setting. In a nutshell, given an arbitrary predefined finite collection G C 2 of contextual groups defined by the covariates (e.g.. demographics), we propose a no tains sublinear regret simultaneously on all subsequences of
In Section 4, we introduce the notion of multigroup Ney- man regret, and present our multigroup adaptive design MGATE (Algorithm 2), which achieves Õ(vT) multigroup Neyman regret as shown in Theorem 4.2. Furthermore, in Appendix D we provide general multigroup design (Algo- rithm 7) that significantly generalizes MGATE. In Section 5, we compare the empirical performance of our adaptive de- signs to the Dai et al. (2023) ClipOGD design on an array of weal-world and synthetic sequential experimental design tasks.
adaptive design that ob-
PIn fact, a lower bounding construction in the very recent work of Li et al. (2024) shows that the best possible Neyman regret is (1) even in the more relaxed superpopulation setting and so our method achieves best-of-both-worrdss guarantee, up to logarithmic factors.
2

---

Stronger Neyman Regret Guarantees for Adaptive Experimental Design
2. Preliminaries
A classical estimator of the ATE is the adaptive IPW esti- mator (Horvitz & Thompson, 1952), which employs inverse probability weighting, We define it next.
Setting We work in the design-based, sequential variant of the potential outcomes setting (Neyman, 1923; Rubin, 1974; Imbens& & Rubin, 2015). A finite number of experimental units in the population arrive one by one at rounds t N+- Each unit has two associated fixed potential outcomes, only one of which can be observed: treatment outcome (1) E IR and control outcome yr (0) E I.
Definition 2.2 (Adaptive IPW Estimator). The adaptive IPW estimator of the ATE Tr is:
Σ पr T Y
1
Z
1- Ze
Pt 1 Pt
In the basic setting, the observed outcome is the only infor- mation the experimenter receives about the units. richer setting is one where before choosing treatment control for unit f, the Experimenter is given access to pre-treatment covariate Ft E X, where X' is feature space of arbitrary nature (e.g. X' may be a finite-dimensional vector space). In this paper, we will study both settings: the noncontextual setting in Section and the contextual one in Section 4.
This estimator is unbiased, meaning that for any outcomes (v)( ze. (1)))= and any adaptive design (p:) with all Pt E (0, 1), we have E[+r] = Tr. Thus, no matter what adaptive design Experimenter employs, the induced adap- tive IPW estimator will always be unbiased. However, the estimator's 's variance will vary based on the design, making some designs more efficient than others.
Adaptive Design In randomized controlled trial (RCT), the experimenter (randomly) decides whether to apply treat- ment or control to each unit, and observes the corresponding outcome but not the counterfactual. These randomized de- cisions for all units constitute the experimental design. We study adaptive experimental designs, described as follows.
Objective: Minimize Variance of ATE Estimator Our main goal will be to construct adaptive designs that asymp- totically approach the variance of the best-in- hindsight ex- perimental design in some benchmark class. A basic class of designs is that of nonadaptive designs, parameterized by the choice of fixed propensity p E (0, 1). Formally, we measure the Neyman regrer (Kato et al., 2020; Dai et al., 2023) of any proposed adaptive design the (time-rescaled) differ- ence between its IPW estimator variance and the variance of same estimator under the most efficient nonadaptive design.
T-round Adaptive Design Protocol
Potential outcomes (11 yr (0)))e);)) are gener- ated upfront (but not shown to Experimenter). Then, sequentially for each unit t = I..
To define Neyman regret, note (see Proposition 2.2 of Dai et al. (2023)) that Varlfr] = Σt_ E [J((p:) /T2 - KATE. where (p) == ye (1)2/p+ ye (0) p) is the variance of the propensity-p IPW estimator unit t, and kATE Et= (1) - yo (0)) is design-independent term. We are now ready to provide the formal definition.
1. (Contextual setting only) Experimenter ob- serves pre-treatment covariate 2; X.
2. Experimenter sets treatment probability ps.
3. Experimenter flips bias-p, coin to obtain real- ized treatment decision: Z: ~ Bernoulli(p.).
Definition 2.3 (Neyman Regret (Kato et al., 2020; Dai et al., 2023)). The Neyman regret of adaptive design (pt) on a potential outcomes sequence (1v:1)) ya (0)) is:3
4. Experimenter observes outcome Y. (Z)).).
By contrast, the standard nonadaptive (Bernoulli) trial fixes upfront the same treatment probability pt = p for all units t, and uses it throughout the experiment without any adjust- ments.
Reg Var, max ().)))
Σ f(led) - f(7))
Thus the variance of the IPW estimator for design (pr (T differs from that of the best nonadaptive design by exactly RegVar, Vary/T², justifying the Neyman regret definition.
Our estimand of interest is the average treatment effect (ATE), which corresponds to the difference between the average outcomes of treatment and control units in the pop- ulation. We provide the formal definition below.
Our goal will be to develop adaptive designs with sublinear expected Neyman regret: E Varyl = o(T), or equiv- alently with vanishing average expected Neyman regret: E [Reg = o(1). We call any design that satisfies this a no-regret design.
Definition 2.1 (ATE). The average treatment effect for po- tential outcomes (1), ve (0)) is:
Me. (1) (0).
>ar'" stands for variance, as Neyman regret captures the rescaled estimator variance associated with the design.
3

---

Stronger Neyman Regret Guarantees for Adaptive Experimental Design
3. Efficient Non-Contextual ATE Estimation
ClipOGD" has Ö(vT) Neyman regret under moment as- sumption on the outcomes: 0 < c c (7 Σ Et= Vi (t)3)1/2 and ( >i (i()9))//// S C for i E {0,1} and some c S C. However, the learning rate of ClipOGD has sev- eral drawbacks. First, it is too conservative, precluding improvement in Neyman regret beyond Ö(VT). Second, it is horizon-dependdnt, making it necessary to know (or commit to) T upfront. Finally, it is constant rather than decreasing, the design probabilities will jump around (rather than gradually converge) during any given run of ClipOGDD
We now present our first contribution: An adaptive de- sign that achieves T) Neyman regret under natural assumptions on the outcomes. We begin by discussing the Ö O(yTT)-Neyma regret design ClipOGD of Dai et al. (2023), and then modifying it to better exploit the strongly convex structure of the Neyman objective. Next, we discuss further guarantees on our method's performance.
3.1. Adaptive Design with Logarithmic Neyman Regret
Meta-Design: ClipOGD The first Lnite-population de- sign that achieves sublinear Neyman regret, ClipOGD, was introduced by Dai et al. (2023). Leveraging the fact that the per-round Neyman objectives [p) are convex in p, it per- forms modified version of online gradient descent (OGD) on ft to adaptively modify the treatment probabilities Pt-
ClipOGDSC; Our Ö(log T) Regret Design We now present an adaptive design called ClipOGD that addresses these issues: It uses the learning rate f) ~ 1/t that, under Assumption 3.1, (1) achieves an exponentially improved Neyman regret bound, (2) is anytime, i.e., does not require advance knowledge of the time horizon T,, and (3) its propen- sities converge in L2 to the hindsight-best propensity. Our Neyman regret bound relies on stricter assumption than the one made by Dai et al. (2023)'s, which we detail below.
The complicating factor is that the gradients of Ss diverge when p is close to 0 or I: standard OGD analyses typically require explicit or implicit bounds on the gradients of the objective (Hazan et al., 2016), so vanilla projected OGD on the entire interval [0, 1] will not work without modification. ClipOGD solves this problem by clipping the OGD iterates {pi HeN, to be within a nested family {[6,, 1 be]e of subintervals of (0, 1), which gradually expand to cover the whole interval in the infinite time limit (i.e., lim & = 0). The expansion is needed to handle cases when pf- is close to the boundary. In view of this, we let 6, = -//h(t) for all t E N+, where h : N+ - Roo is some strictly increasing function with limy-rso h(t)= = co. We call & the clipping rate, h the clipping function, and refer to any adaptive de- sign (Pt) that satisfies 1/h(t) S Pt S 1 -1-18 11-1/h(t) for all t as h-clipped. Algorithm 1 gives the pseudocode for ClipOGD. Here, [Is(r) denotes the projection of & onto interval S C 1).
Assumption 3.1 (Bounds on Potential Outcomes). There exist positive constants c, C such that outcomes {Bv()), b(1)))221 satisfy for all time horizons T:
(lx (1)( SC
121
f21
c mim (vc(0)² + y (1))))
121
T T Σ (1))
1/2
min (0.1)
Next, let haw be the inverse function of h, defined via the identity hinv o h h hinv Id. Our main result the following Neyman regret bound in terms of T. h. and hav-
Algorithm 1 ClipOGD (Dai et al., 2023)
Theorem 3.2 (Stronger Neyman Regret Bound). Suppose Assumption 3. is satisfied with C, the corresponding constants. Let h : N+ + R>o be strictly increasing. Let ClipOGDSC be the adaptive design that instantiates Algo- rithm 1 with learning rate T)- = 1/(2c²t) and clipping rate 5, = 1/h(().. Then, ClipOGD attains the following anytime-valid Neyman regret bound:
Initialize po <- 0.5 and g0 f 0
for units f = 2,,.... do
Set step size n7 and clipping rate 5, E (0, 0.5) Set treatment probability Ps +- II (pt-1 - 7/e 1)-
Set treatment decision Z ~ (errouull((p))
Observe outcome Y, < -) (Z))
Set gradient estimate: 9: t Y?
Zg
+
(1-p)3
1-2
E (((())) (ogTT))))) (1+C/c))²)
pc
end for
(1)
Since h can be chosen to grow arbitrarily slowly, we can get: E[RegVar,] Ö(log
ClipOGDo: A Õ(VT) Regret Design In their paper, Dai et al. (2023) analyzed and provided guarantees for a specific instantiation of ClipOGD, where 7, = /1/T and 5, = 0.5. 1/1 where a = 55 log T for all = 1,....... T. For clarity, we call this design ClipOGD Their main result proves that
The proof is contained in Appendix B. It exploits the strong convexity of the Neyman objectives fa enabled by Assump- tion 3.1 (hence the 'SC' in ClipOGDSC), ), by applying
4

---

Stronger Neyman Regret Guarantees for Adaptive Experimental Design
the techniques for analyzing strongly convex gradient de- scent (Hazan et al., 2007; Rakhlin et al., 2012).
superpopulation: (ue(O),ye ye())) D for all 2 and any fixed distribution DD Then, ClipOGDSC guarantees that E [(PT )²} + 0 at the rate (log TT),, and thus in particular that pr + p" in probability.
Compared to the analysis in Dai et al. (2023), we make explicit the dependence of the regret of ClipOGD on the clipping rate. Note that the choice of is flexible in the sense that any h((t) = o(t022-) for any & > O will result in a regret bound that is sublinear in T. From a practical standpoint, however, picking may be nontrivial affair, as a slower-growing h will have a faster-growing inverse mapping hinv. While the hinv den-ddepndent term in the regret bound is constant in T,, it can still be large in the constants of the problem. Intuitively, if C/c is large, the optimal propensity pt may be near the boundary and convergence may be slow. We hope future work will further explore the "well-conditioning" properties of Neyman regret.
Proof. In the superpopulation setting, any adaptive design will have nonnegative Neyman regret: f((p) = f(p) = E (1y(1) + Elu(0))1/(1 - p) has the same optimum D¹ (1 + (O)) [((v)(1)))) -1 for all units 4, so E B(ReVVrr
-(x")))()))))))))))))))))))))))) E (f(P)) - f(v")) 2 0.
3.3. Valid CIs for the Adaptive IPW Estimator
We now turn to the issue of endowing the IPW estimator fy induced by our adaptive design with asymptotically valid confidence intervals (CIs). In general, the existence and construction of valid CIs for fy delicately depends on the choice of the design. However, we will now see that a construction of Dai et al. (2023) lends conservative CIs to all h-clipped adaptive designs with vanishing regret.
3.2. Convergence of Adaptive Treatment Probabilities
We now investigate the trajectory of treatment probabilities (Pr)t21 produced by ClipOGDSC, Ideally, these propensities would converge to the optimal probabilities (pi)r )r21 T grows large. By tweaking the arguments used in establishing our Neyman regret bounds of Theorem 3.2, we can obtain convergence in squared means (and hence in probability). The next claims formalize this result. In particular, we first establish a quantitative bound on the L2 convergence of our propensities the benchmark ones. (See Appendix B for the derivation.)
To formalize this result, we make standard assump- tion: that the outcome sequences are not perfectly anti- correlated. To state it, define "empirical second raw mo- ments" of the two outcome populations as: Sr(1)² ==
+ Σ Ei (i)) for i E {0, 1}.
Assumption 3.6 (Correlation of Outcome Populations (Dai et al., 2023)). For a constant cp > and all T 2 1, the running correlation pr of the sequences {(v (0), y1 (1)))21 satisfies:
Lemma 3.3 (Lz-Deviation from Benchmark Design). The deviation of the design probabilities of ClipOGDSC from the best nonadaptive design probabilities is boundddd for all T as:
PT 2 -1+ Cp. where pr = +V We (1)) ST(1)ST(0)
(PT p+) s -
[E|RegVaryy T
+
(A(T))) T
2og logT
Theorem 3.7 (CIs for Clipped Adaptive Designs). Suppose the potential outcomes satisfy Assumption 3.1 and Assump- tion 3.6. Consider any h-clipped adaptive design (pt)t21 with vanishing Neyman regret: lim RegVar, = 0. Let be a conservative upper bound on the
This implies the following Lz-convergence result, subject to an assumption on the Neyman regret of ClipOGDSC which asks for it to not consistently outperform the optimal non- adaptive design.
T 4 hindsight hest nonadaptive variance. Then, letting (Z, )221 be the treatment decisions, the estimator of Dai et al. (2023) given by:
VB =
Corollary 3.4 Slg-Convergence to Benchmark Design). As- sume ClipOGDSC has asymptoticully nonnegutive Neyman g g(RegVarry 2 0. Then, its propensities (pe)121 will converge to the benchmark nonadaptive propen- sities (T2) in squared means: E [PT p]] -> 0 as T -+00 0C.
regret: lim inf
VB+ T
(1))
Ze Pe
(
7
(v)) 2 1 Pt.
T
converges to VB in probability at rate O, (Vh(T)/T).
In the special case of sequences of potential outcomes that are (i.i.d.) samples from superpopulation, the regret non- negativity holds automatically, implying that our adaptive design will necessarily converge to the best nonadaptive design without further assumptions.
Consequently, VB can be used to construct asymptotically valid Chebyshev-type confidence intervals for the adaptive IPW estimator ंr under any adaptive design satisfying the above conditions. Specifically, for any confidence level a E (0, 1]:
Corollary 3.5 (Convergence in the Superpopulation Set- ting). Suppose that the outcomes are drawn i.i.d. from a
lim inf Pr Tr E T-000
ta 1/2 / VB
2 2 a.
5

---

Stronger Neyman Regret Guarantees for Adaptive Experimental Design
The proof for Theorem 3.7 is outlined in Appendix C.
(VVT) multigroup Neyman regret bound.
4. Efficient Multigroup ATE Estimation
Algorithm 2 AAMGATE: Multigroup Adaptive Design
Receive clipping function h N+ - R>
The Contextual Setting Section 3 covers non-contextual adaptive designs that only observe outcomes. A contextual adaptive design, however, also observes pre-treatment co- variates 24 X' at the start of each round, which can help predict potential outcomes (O), (1)). We can leverage this extra information to improve treatment assignments and outcome estimation.
Receive number of groups d = [
Set group counts 710 f 0
Initialize P1 f
0.5 1st // At round t,
Pt
(pi.O)EES will contain group propensities Initialize w/ + 1s, Lo + 0%, 00000 + 0 //
Parameters used to update group we weights
A Multigroup Formulation We frame the contextual set- ting in a multigroup way. Before the experiment, we have a finite set of context-defined groups 9 = {G1, .2.... each G S X, where X is the feature space. Any covariate vector 3t can belong none, one, or more groups. The group definition is dependent on the specifies of the task, e.g., in medical application the features Fy could represent a patient's 's health history.
for f 2, do
Receive covariate vector 2, E X, determine the set of active groups G, {G: 2t E G. G E g}
Cast G, as indicator vector as E 10, (aL. =
1 - Ge G.).). Set group counts: n4 + 14-1 + at
// Set Normalize group weights: Wt,eff (ariy))
inactive group weights to 0
Set effective treatment probability: Pt.f + // Aggregate group
Our objective in a multigroup setting, informally, is to de- sign an adaptive scheme that offers ATE estimation effi- ciency guarantees (such as Neyman regret guarantees) not only average over the entire sequence of units but also each subsequence that results from conditioning units be- longing to a group G, simultaneously for all groups G E G.
(Weeeff, PP)
propensities
Set treatment decision: Z, Bernoull((p,.tt)
Receive realized outcome: Y; + (((2))
for active groups G E 9i do
/* Update group propensities using ClipOGD -type
4.1. A New Metric: Multigroup Neyman Regret
update +/
Set estimated Neyman gradient as:
We introduce multigroup Neyman regret strengthening of (vanilla) Neyman regret. Specifically, given any contex- tual group collection G. G-multigroup Neyman regret is the maximum Neyman regret that an adaptive design achieves over any group G in the collection. We formalize next.
Fe.G Y?
___ T-Pt,et
Ze + [1 p1-
1-7
Pt.etl
Pia
Update P1+1, 16,,0,1-6,,01
II
(Dt,G 11 I1,c),
where 11 + 20 and 8G,6 + [(m.a)
/ Get losses used to update group weights +/
Definition 4.1 (G-Multigroup Neyman Regret), Given any group collection g 2*, the group-conditional Neyman regret of an adaptive design A on any group G E is defined as:
Set estimated Neyman loss as: 1 )
2. t.o t Y?? Pt.tft
2. 1-2e
Pi 1-PLO
end for for inactive groups G E G, do
Ver, (A;G)
T Σ
Set P1+1. + Pt,G and 4. + 0// Inactive groups are not updated end for
[s. E G (felet) 1(6p'1)
E max (())))
/+ Update group weights: Higher cumulative group losses + larger weights */
The G-multigroup Neyman regret of A is then defined as its maximum group-conditional Neyman regret over all groups
Ge G:
Set surrogate loss: 4 +- a 2 (b4 w(.at)
Set L, + L--1 + E, and qi + 9t-1 ||e,112
Reg (AgVarMG max Reg (egVarr(4:G)) GEg
Update group weights: w/y +- max { 00" vn L
end for
4.2. Achieving Ö(VT) Multigroup Neyman Regret
We now present in Algorithm 2 an adaptive design which we call MGATE (for Multi-Group ATE) and achieves the
Additional Notation: We use ④ to denote elementwise
6

---

Stronger Neyman Regret Guarantees for Adaptive Experimental Design
vector multiplication, and let 14, 0 be d-dimensional all- ones and all-zeros vectors. Also note that the update of w/+1 takes elementwise maximum of the vectors, and assumes that 0/0 0 to account for the corner case qt = 0.
give advice to the meta-algorithm. At a high level, obtain multigroup Neyman regret, would thus like to use sleep- ing experts algorithm aggregate propensities suggested by [g] = d copies of ClipOGD SC that are respectively active on all groups G E G: the aggregated design would then per- form comparably to each copy of ClipOGDSC on its group G. Then, since that copy of ClipOGDSC will have no regret on group G, neither will the aggregated design.
Given a collection 9 of d groups, in each round MGATE reads off the currently active groups G. S G. i.e., those groups that contain Te (G e zt). and then proceeds to determine the new treatment probabil- ity by aggregating the "best-guess" probabilities for all active groups G E Gr determined based on the past per- formance of those groups. To do so, MGATE maintains group weights V',,c and group-specific propensities Pt,G- It comes up with a single effective treatment probability: Pt.eff ~ -Eee, w/,ct WP,. in each round by reweighing the group specific propensities of the active groups. This ef- fective treatment probability should simultaneously satisfy the interests of all active groups. The treatment decision Z, is then generated according to et,eff- After the outcome is revealed, MGATE updates all group weights, as well as the propensities of groups that were active.
Algorithm Description:
Challenges and Solutions Past work on sleeping experts does not fully address the combination of difficulties present in our setting: (1) stochastic (realized outcome) feedback rather than full-information (both outcomes) feedback; (2) the need to perform clipping of the iterates (propensities) to explicitly restrict them from approaching the feasible set's boundary too fast; and (3) the fact that the gradient feedback magnitude grows unboundedly as T - oc, even with clipping.
While there are limited number of "sleeping bandits" algo- rithms in the literature (e.g., see Nguyen & Mehta (2024)) that address the stochastic feedback, they don't naturally extend to cover both of the latter two issues. Therefore, we design from scratch new sleeping experts algorithm tailored to all of these challenges. It employs scale-free updates of the group weights w so as to control the loss and gradient feedback magnitudes; we achieve this by deploying an instance of the seminal scale-free SOLO FTRL algorithm of Orabona & Pál (2018) and endowing it with sleeping ex- perts regret guarantees via a recent reduction of Orabona (2024). To clip the effective probability magnitudes, our algorithm aggregates over the suggested per-group probabil- ities via convex combinations rather than via sampling from their mixture. Finally, ensure that the per-group propen- sity updates remain valid under stochastic gradient feedback and despite the aggregator using different propensity than the suggested per-group one, MGATE uses a combination of unbiased first-order (ūr,c) and zeroth-order (Z,,a) per-group feedback estimators, which depend on both Pt.fff and Pt,G-
We can show that MGATE achieves the following multi- group Neyman regret guarantee. We note that MGATE is anytime valid, meaning that just like our noncontextual de- sign ClipOGDSC, it does not require advance knowledge of the time horizon T.
Theorem 4.2 (Guarantees for Algorithm 2). Fix any context space X and finite group family & C 2² Suppose" Assump- tion 3.1 holds with lower bound constant с > O. Then, for any clipping function h, the expected multigroup regret of Algorithm 2 will be bounded as:
RogVan
VT). .VT)
4.3. Technical Overview
The full analysis of Algorithm 2 is contained in Appendix D. It builds on several tools recently developed in the online learning literature, which are formally introduced in Ap- pendix D.I, and we briefly survey them here. The central tool is the sleeping experts algorithmic framework (Blum & Lykouris, 2020), which has recently been shown to be able to combine the wisdom of multiple sub-learners (or experts) into a meta-algorithm with performance on par with each of the nub-learners The key difference from typical online aggregation schemes is that each sub-learner is allowed to be inactive (asleep) on some rounds, on which it does not
A Generalized Meta-Design Our analysis in Appendix D generalizes beyond MGATE (Algorithm 2). Indeed, our approach more generally allows the use of any scale-free sleeping experts algorithm to update group weights, and any ClipOGD-style (see Appendix D.3) no-regret adaptive designs to update the groupwise treatment probabilities. Thus, we more generally provide a meta-design that reduces multigroup designs to a broad class of non-contextual, no- regret designs. This generalized meta- meta-design is given as Algorithm 7 in Appendix D.4, and Theorem D.6 contains its regret bound, of which Theorem 4.2 above is corollary.
'By replacing the ClipOGD&C propensity updates in MGATE with ClipOGD'-sty -style updates, we can straightforwardly obtain multigroup design which only relies on the assumptions of Dai al. (2023) while keeping Ö(vT) multigroup Neyman regret. This follows from the generality of our multigroup meta-design presented in Appendix D, which can use a wide variety "ClipOGD- style" updates while still obtaining Õ(VT) multigroup regret.
7

---

Stronger Neyman Regret Guarantees for Adaptive Experimental Design
Treatment probability
0 =.11
0 =1
=10
0.75
0.75
0.75
0.50
0.50
0.50
0.25
0.25
0.25
1000
3000
10000
30000
1000
3000
10000
30000
1000
3000
10000
30000
Neyman regrett
a =0.1
=1
=10
10.0
10.0
300
3.0
100
1.0
0.1
0.3
1000
3000
10000
30000
1000
3000
10000
30000
1000
3000
10000
30000
Round
Method
CLIPOGD
CLIPOGD
Figure 1. Treatment probabilities and Neyman regret of ClipOGD on Gaussian data for different noise (r) levels. As increases, ClipOGD converges more slowly. Its regret remains high, and the treatment probabilities not settle within observed horizon (T' = 50,000). The black line in the treatment probabilities indicates the Neyman optimal probability.
5. Experimental Results
control paths. We then measure the Neyman regret by aver- aging the regret across these probabilities obtained at each time step.
We first present the results for the non-contextual setting and then turn to the analysis of the performance for the contextual algorithm. Our code is available at the following link: http:///iihub.ooo/mmmaaaa http://wwww...ooo/oooooooo////aa
Hyperparameter Choices Throughout the experiments, the following hyperparameters. For method, set т) = 2/t and & = 1//h(t). where the clipping function is htt) exp (log(t (t + 24) For ClipOGD", we follow
5.1. Non-Contextual Experiments
Tasks We compare our method ClipOGIDCC with ClipOGD" (Dai et al., 2023) on multiple tasks. Below, we show two key datasets (one synthetic and one real- world) used in our experiments, with full details in Ap- pendix E. The first is a synthetic dataset is generated as
Dai al. (2023) with constant learning rate T/c 1/vT and clipping rate = - 2.5.--1//5lo""
We analyze three synthetic data settings where we vary as 1. As increases, the ratio C/c also grows, so by Equation (1), we expect slower conver- gence of our algorithm. We set T 50,000. Figure I shows the Neyman regret across these settings, matching our theoretical expectations: when ClipOGDSSc drops to 0 quickly, but for larger a, the regret remains high and converges later. The regret of ClipOGD" instead keeps increasing with time. Nonetheless, in line with Corollary 3.4. Figure I also shows that our method's adaptively chosen propensities ultimately converge to the Neyman optimal probability all three cases. By contrast, the propensities of ClipOGD only converge when 10, which happens to match the initial probability of 0.5. Next, turn examine the results the microfinance data. Figure 2 illustrates the treatment probabilities and Neyman regret for both algorithms. On average, each design as- signs probabilities near the Neyman probability. However, those of ClipOGD exhibit higher variance compared to ClipOGDSC This translates into greater Neyman regret in
Results
follows: (i) iid ((s; 2²) for L ...... T and 0, with A4 = 1 and μ41 2. We vary a, R__ showcase where method succeeds and where it struggles. The second dataset comes from Egypt's largest microfinance organization (Groh & McKenzie, 2016), covering 2,961 clients. Here, the treatment is a new insurance product, and the outcome how much individuals invest in machinery. Following Dai et al. (2023), we fill missing values with Gaussian noise and resample each unit five times to increase the population size. We also present experiments on the ASOS Digital Experiments Dataset (Liu et al., 2021), and on
0.1. the regret of
tasks for large language models, in- cluding BigBench (Srivastava et al., 2023), in the Appendix.
Experimental Setup In our simulation, each unit is ran- domly assigned to treatment or control using the treatment probability from our method or ClipOGD We repeat this process 10,000 times, generating many different treatment-
8

---

Stronger Neyman Regret Guarantees for Adaptive Experimental Design
6. Conclusion
CI POOD
In this paper, we have studied adaptive designs for unbiased ATE estimation with pottlee-pptationn guarantees. We intro- duced a modification of the ClipOGD algorithm that prov- ably yields vanishing Neyman regret, achieving anytime- Neyman regret, improving upon previous Õ(VT) guarantees. We also extend our framework incor- porate contextual information by introducing multigroup formulation. Our proposed multigroup adaptive design en- sures ((V)) regret for each predefined group, enabling efficiency improvements for subgroup ATE estimation. Ex- perimental results corroborate these findings.
Ci sosp!
12x
Round
Figure 2. Treatment probabilities and Neyman regret of Cli- POGD on microfinance data for I' = 15,000 rounds.
valid Olog T))
Noyman noggus
6.22
0.52
6.22
0.03
0.033
0.21
0.20
0.032
Overall, these results suggest that adaptive experimentation can achieve strong unite-population efficiency guarantees, offering practical advantages for wide range of applica- tions. Future work could explore extensions to other experi- mental designs and further reductions in regret rates.
15000
5000
5000
3000
1a0
Mechod
MGNTE
CUPOOU
CUPOSO
Figure 3. Group-conditional Neyman regret of ClipOGD and MGATE microfinance data. MGATE produces the lowest G-multigroup Neyman regret as desired, and in this case dominates the non-contextual ClipOGD variants for each group, including the noncontextual group Go = =X
Acknowledgements
The authors thank Vanessa Murdock for the support through- out this project, and Lorenzo Masoero, Blake Mason, and James McQueen for useful feedback.
later rounds, which never converges to O. The probabilities assigned by our method, instead, converge to the Neyman probability, yielding vanishing average Neyman regret.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
5.2. Contextual Experiments
Here we present our contextual results using Algorithm 2 over the previously-desctin
datasets. To standardize the contextual groups in each experiment, we design simple, synthetic post-hoc groups by scoring each sample vx(1)=+e) (the optimal Neyman sam- pling probability for the single sample). Our groups are computed by checking whether sample belongs to some predetermined quantile of the score function Go =, G1 = [[ [[='(ss S ]] G2 = F=)() We note that these groups overlapping and informative since G2 is guaranteed have lower equal optimal sampling probability than G2.
References
Acharya, K., Arunachaleswaran, E. R., Kannan, S., Roth, A., and Ziani, J. Oracle efficient algorithms for group- wise regret. In The Twelfth International Conference on Learning Representations, 2024.
as s, = (1 (.)²
Blackwell, M., Pashley, N. E., and Valentino, D. Batch adaptive designs to improve efficiency in social science experiments, 2022.
Blum, A. and Lykouris, T. Advancing subgroup fairness via sleeping experts. In Innovations in Theoretical Computer Science Conference (ITCS), volume 11, 2020.
We stress that these groups are included for illustrative purposes and rely on information that would be unobserv- able in a real ATE experiment, but nonetheless showcase the potential for high-quality contextual information for multi-group ATE, Figure shows the Neyman regret for ClipOGD ClipOGDSC, and MGATE on the microfinance dataset on each group; our MGATE method achieves the lowest group-conditional regret out of all the methods, ef- fectively minimizing the G-multigroup Neyman regret, and thereby validating our theoretical results. Additional con- textual experiments are provided in the Appendix.
Chernozhukov, V., Demirer, M., Duflo, E., and Fernández- Val, I. Fisher-schultz lecture: Generic machine learning inference on heterogenous treatment effects in random- ized experiments, with an application to immunization in india. arXiv preprint arXiv: arXiv: 1712.0482, 2017.
Chow, S.-C. and Chang, M. Adaptive design methods in clinical trials a review. Orphanet journal rare diseases, 3:1-13, 2008

---

Stronger Neyman Regret Guarantees for Adaptive Experimental Design
Conneau, A., Rinott, R., Lample, G., Schwenk, H., Stoy- anov, V., Williams, A., and Bowman, S. R. Xnli: Eval- uating cross-lingual sentence representations. In 2018 Conference on Empirical Methods in Natural Language Processing, EMNLP 2018, pp. 2475-2485. Association for Computational Linguistics, 2018.
Hazan, E. al. Introduction online convex optimization. Foundations and Trends@ in Optimization, 2(3-4):157-
325, 2016.
Hoffmann, J., Borgeaud, S., Mensch, A., Buchatskaya, E., Cai, T., Rutherford, E., Casas, D. d. L., Hendricks, L. A..
Welbl, J., Clark, A., et al. Training compute-optimal large language models. Advances in Neural Information Processing Systems, 2022.
Cook, T., Mishler, A., and Ramdas, A. Semiparametric efficient inference in adaptive experiments. In NeurlPS 2023 Workshop Adaptive Experimental Design and Active Learning in the Real World, 2023.
Horvitz, D. G. and Thompson, D. J. A generalization of sam- pling without replacement from finite universe. Journal of the American statistical Association, 47(260)::63-685, 1952.
Dai, J., Gradu, P., and Harshaw, C. Clip-ogd: An experimen- tal design for adaptive neyman allocation sequential experiments. Advances in Neural Information Processing Systems, 36:32235-32266 2023.
Hu, F. and Rosenberger, W. F. The theory of response- adaptive randomization in clinical trials. John Wiley Sons, 2006.
Deng, S., Liu, J., and Hsu, J. Group-wise wise oracle-efficient algorithms for online multi-group learning. Advances in Neural Information Processing Systems, 37:39462- 39500, 2024.
Imbens, G. W. and Rubin, D. B. Causal inference in statis- tics, social, and biomedical sciences. Cambridge univer- sity press, 2015.
FDA. Adaptive designs for clinical trials of drugs and bio- logies: Guidance for industry. Technical Report, Center for Drug Evaluation and Reseurch (CDER), Center for Biologics Evaluation and Research (CBER), 2019.
Jiang, A. Q.. Sablayrolles, A., Mensch, A., Bamford, C., Chaplot, D. S., Casas, d. L., Bressand, F., Lengyel, G., Lample, G., Saulnier, L.., al. Mistral 7b, arXiv preprint arXiv:2310.06825 2023.
Fogliato, R., Patil, P., Akpinar, N.-J., and Monfort, M. Precise model benchmarking with only a few observa- tions. In Proceedings of the 2024 Conference Em- pirical Methods in Natural Language Processing, pp. 2024.
Kato, M., Ishihara, T., Honda, J., and Narita, Y. Efficient adaptive experimental design for average treatment effect estimation. arXiv preprint arXiv:2002.05300, 2020.
Kern, C., Kim, M. P., and Zhou, A. Multi-accurate cate is robust unknown covariate shifts. Transactions Machine Learning Research: TMLR, pp. 1-59, 2024.
Groh, M. and McKenzie, D. Macroinsurance for microen- terprises: A randomized experiment in post-revolution egypt. Journal of Development Economics, 118:13-25, 2016.
Lee, D., Noarov, G., Pai, M., and Roth, A. Online minimax multiobjective optimization: Multicalibeating and other applications. Advances in Neural Information Processing Systems, 35:29051 -29663, 2022.
Hadad, V., Hirshberg, D. A., Zhan, R., Wager, S., and Athey, S. Confidence intervals for policy evaluation in adaptive experiments. Proceedings of the national academy of sciences, 210155)c20146021 18, 2021.
Li, H. H. and Owen, A. B. Double machine learning and design in batch adaptive experiments. Journal of Causal Inference, 12(1):2033068, 2024.
Hahn, J., Hirano, K., and Karlan, D. Adaptive experimental design using the propensity score. Journal of Business &
Economic Statistics, 29(1):96-100) 2011.
Li, J., Simchi-Levi, D., and Zhao, Y. Optimal adaptive experimental design for estimating treatment effect. arXiv preprint arXiv:2410.05552 2024.
Harshaw, C., Sävje, F., Spielman, D. A., and and, 7. Balancing covariates in randomized experiments with the gram- schmidt walk design. Journal of the Ameri-
can Statistical Association, (19(54)):9334-2999 doi: 10. 200.0080006221449922222222222220 20244449922222222 doi doi/org/10, 1080 0161445112244 2et.e2211122222..2....2 2222372.
2024.
Liu, C., Cardoso, Å., Couturier, P., and McCoy, E. J. Datasets for online controlled experiments. NeurIPS 2021 Datasets and Benchmarks Track, 2021.
URL https:/
Hazan, E., Agarwal, A., and Kale, S. Logarithmic regret al-
Neopane, O.,, Ramdas, A., and Singh, A. Logarithmic ney-
gorithms for online convex optimization. Machine Learn- ing, 6992):169-192, 2007.
man regret for adaptive estimation of the average treat- ment effect. arXiv preprint arXiv:24/ 1...24411114111... 2024.
10

---

Stronger Neyman Regret Guarantees for Adaptive Experimental Design
Neopane, O., Ramdas, A., and Singh, A. Optimistic algo- rithms for adaptive estimation of the average treatment effect. arXiv preprint arXiv:2502.0466
Semenova, V. and Cheroozhuoov V. Debiased machine learning of conditional average treatment effects and other causal functions. The Econometrics Journal, 24(2):264- 289, 2021.
2025.
Neyman, J. Sur les applications de la théorie des probabilités aux experiences agricoles: Essai des principes. Rocıniki Nauk Rolniczych, 10(1):1-51, 1923.
Solomon, H. and Zacks, S. Optimal design of sampling from finite populations: A critical review and indication of new research areas. Journal of the American Statistical Association, 65(330):653-677, 1970.
Neyman, J. On the two different aspects of the representative method: the method of stratified sampling and the method of purposive selection. In Breakthroughs in statistics: Methodology and distribution, pp. 123-150. Springer, 1992.
Srivastava, A., Rastogi A., Rao, A., Shoeb, A. A., Abid, A., Fisch, A., Brown, A. R., Santoro, A., Gupta, A., Garriga- Alonso, A., et al. Beyond the imitation game: Quantifying and extrapolating the capabilities of language models. Transactions on machine learning research, 2023.
Nguyen, Q. M. and Mehta, N. Near-optimal per-action regret bounds for sleeping bandits. In International Con- ference on Artificial Intelligence and Statistics, pp. 2827- 2835. PMLR, 2024.
Team, G., Riviere M., Pathak, S., Sessa, P. G., Hardin, C., Bhupatiraju, S., Hussenot, L.., Mesnard, T., Shahri- ari, B., Ramé, A., et al. Gemma 2: Improving open language models a practical size. arXiv preprint arXiv:2408.001 2024.
M., Coppock, A., and Green, D. P. Adaptive experimental design: Prospects and applications in politi- cal science. American Journal of Political Science, 65(4): 826-844, 2021.
van der Laan, M. J. The construction and analysis of adap- tive group sequential designs. U.C. Berkeley Division of Biostatistics Working Paper Series, 2008.
Orabona, Black-box reductions: Sleeping experts. URL: http://paaanneeerrree.mmm2244222 box-- reductions-slepiiggeexxrsss 2024. Accessed 2024-10- 20.
Villar, S. S., Bowden, J., and Wason, J. Multi-armed bandit models for the optimal design of clinical trials: benefits and challenges. Statistical science: a review journal of the Institute of Mathematical Statistics, 30(2):199, 2015.
Orabona, F. and Pál, D. Scale-free online learning. Theoret- ical Computer Science, 716:50-69, 2018.
Wager, S. Causal inference: A statistical learning approach, 2024.
Pal, A., Umapathi, L. K., and Sankarasubbu, M. Medmeqa: large-scale multi-subject multi-choice dataset for medi- cal domain question answering. In Conference health, inference, and learning, pp. 248-260. PMLR, 2022.
Wald, A. Sequential tests of statistical hypotheses. In Breakthroughs in statistics: Foundations and basic theory,
pp. 256-298. Springer, 1992.
Ponti, E. M., Glavaš, G., Majewska, O., Liu, Q., Vulié, I., and Korhonen, A. Xcopa: A multilingual dataset for causal commonsense reasoning. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 2362-2376, 2020.
Xu, Y.. Trippa, L.,, Müller, P., and Ji, Y. Subgroup- based adaptive (suba) designs for multi-arm biomarker trials. Statistics in Biosciences, 8:159-180, 2016
Xu, Z Zhang, K. W., and Murphy, S. A. The fallacy of minimizing local regret in the sequential task setting. arXiv preprint arXiv:2403. 10946, 2024.
Rakhlin, A., Shamir, O., and Sridharan, K. Making gradient descent optimal for strongly convex stochastic optimiza- tion. In Proceedings of the 29th International Conference on Machine Learning, pp. 1571-1578, 2012.
Zellers, R., Holtzman, A., Bisk, Y., Farhadi, A., and Choi, Y. Hellaswag: Can a machine really finish your sentence? In Proceedings of the 57th Annual Meeting of the Asso- ciation for Computational Linguistics, pp. 4791 4800,, 2019.
Rao, A. and Zhang, P. On distributional discrepancy for experimental design with general assignment probabili- ties. In The 28th International Conference on Artificial Intelligence and Statistics, 2024.
Zhang, K., Janson, I.., and Murphy, S. Inference for batched bandits. Advances in Neural Information Processing Systems, 33:9818 8 8-8829, 2020.
Robbins, H. Some aspects of the sequential design of exper- iments. 1952.
Zhang, K., Janson, L., and Murphy, S. Statistical infer- ence with m-estimators on adaptively collected data. Ad- vances in Neural Information Processing Systems, 34: 7460-7471, 2021.
Rubin, D. B. Estimating causal effects of treatments in randomized and nonrandomized studies. Journal of edu- cational Psychology, 66(5))688, 1974.

---

Stronger Neyman Regret Guarantees for Adaptive Experimental Design
Zimmert, M. and Lechner, M. Nonparametrri estimation of causal heterogeneity under high-dimensional confound-
ing, arXiv preprint arXiv:1908.08777 2019.
12

---

Stronger Neyman Regret Guarantees for Adaptive Experimental Design
Organization
The Appendix is organized as follows.
Appendix A contains a discussion of further related work.
Appendix contains proofs of noncontextual method's convergence.
Appendix discusses confidence interval guarantees for adaptive IPW estimators induced by our design.
Appendix D presents the general multigroup adaptive design framework and proves its efficiency guarantees.
Appendix E describes additional empirical results.
A. Additional Related Work
Some early work on adaptive designs The efficient adaptive design problem considered in this work (and in (Dai et al., 2023) and other prior works) has its roots in problems studied, or mentioned, in the classical works of Neyman, Wald, and Robbins. The seminal work of Wald (1992) is 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.
As described in (Dai et al., 2023), it was Robbins (1952) who explicitly posed the open problem of constructing efficient adaptive sampling schemes, though he stopped short of formally reasoning about precise benchmarks such Neyman regret that such designs must optimize; and while within the subsequent decades, adaptive designs have gained traction e.g. in the survey sampling context Solomon & Zacks (1970), but yet again they did not explicitly optimize for efficiency metrics like the ones we study.
Improved Neyman Regret in the Superpopulation Setting Independently and concurrently to our work, complementary progress has been made on the problem of (noncontextual) adaptive ATE estimation with low Neyman regret. Neopane et al. (2024) modify ClipOGD to obtain logarithmic Neyman regret guarantees in the substantially more benign superpopulation regime. Neopane et al. (2025), in an environment in which outcomes are generated from some joint distribution with time-stationary means and variances, design Neyman regret minimization algorithm based on UCB-like optimistic policy tracking approach, with both theoretical guarantees and strong empirical performance.
Covariate Balancing In relation our multigroup setting, it is interesting to discuss recent progress on what is known as covariate balancing techniques. For instance, studies such as Harshaw et al. (2024), Rao & Zhang (2024). which are conducted in the non-adaptive setting, share with our work the objective of optimizing the estimation variance and offer a principled way to exploit covariates to do so, by assuming the mapping between covariates and outcomes is linear (and trading off robustness and covariate balance). Thus, a potential future work direction can involve porting the covariate balancing insights over to the adaptive setting, possibly leading to a new perspective on group-aware optimal-variang adaptive designs that could complement our multigroup approach.
B. Mon-Contextual Setting: Proof of Theorem 3.2 and of Lemma 3.3
B.1. Neyman Regret Analysis for ClipOGDSC, Proof of Theorem 3.2
We establish Theorem 3.2 via a sequence of claims.
Claim 1 (Optimal Probability Bounds; Lemma C.2 of Dai et al. (2023)). The optimal fixed probability pf. for any time horizon T satisfies, under Assumption 3.1, the following inequality, defining the constant A = 1 C/c 2:
1 SpI
1
<
A
A'
Claim 2 (How Quickly Optimal Probability Enters Admissible Region). Under Assumption 3.1, let A = 1 + C/c 2 2. Then, for any time horizon T, the optimal probability pž will satisfy:
t t2 = pr E 15.,1 6c), where 1" := :=hinv (A).
13

---

Stronger Neyman Regret Guarantees for Adaptive Experimental Design
Proof. With 1 in hand, have that as soon as d, S 1/A, the optimal probability p7. (for any T) is guaranteed be in the admissible interval [6,, 1 - 5t]. This is equivalent to requiring h(t) 2 A, which by definition of hivv and by the strictly increasing nature of h is equivalent to 2 (A).
Claim 3 (Gradient Raw Moment Bounds). Under Assumption 3.1, for every t 2 we have the following bounds in expectation wrt. the design's randomness:
E[|sa|] & 2041(122 BLAi S (C))(1)²
Proof. The bounds follow as shown in Lemma C.5 of Dai et al. (2023), by just expanding out the first and second raw absolute moment of the gradient estimator defined above; we will get E gell ~ 6, 2 (1)) + ye (0))),, and E[g²! ~ (g, + y. (0)*), ) so the statement follows from our Assumption 3.1, or from Dai al. (2023)'s s assumption on the boundedness of the second and fourth moments of the two populations.
Claim (Strong Convexity of Objective). For any round - 1, and for any p.p' E (0, 1), the objective function will satisfy:
(( - f((') S (p) (p - p') (p)=2')²
Proof. To show this, it suffices to establish -stonng convexity of f((p) y.(1)² P
+ 2e(1)
I-p and we will do so by verifying
that (p) 2 2c² for all p E (0, 1). Indeed, note that f" = 2 (0)2
D² + (1)
N (0) + (c(1)² 2 2c² since
(1 (1-p)3
p E (0, () and by definition of e Assumption 3.1.
Claim 5, For any 2 1, any setting of T) > 0, 6, = 1/t(t), and for any point p" E EPi we have in expectation over the randomness of the design:
1 d²)
(lf((p)) - fe(p")]
B[(p: - --- E[(p++ - -p*) + -
277
21T
+2 st] (m-11) hh(t) +(CN(t)²)
Proof. By Claim 4 applied to p = Pt and p' = pp, we have f((p)) - f1() S fp() (pc pp) - -p( -2 Now, can bound the first term on the right-hand side as follows.
First, start with the inequality: IP++1-p"' pp' < Ip:- 7hSt -p"1 + +6, 1pp & 1- which follows by Lemma C.I in Dai
et al. (2023). By Claim 2, we have that 1(p" & [6,, - 51] = 0 for all 2 t", implying that 1pp" & [6,, 1 - 6d]l s 1 I t*). Thus, we have |p++1 - p²1 S lp:- "Me.t - p" + 5. 1[ S )*) Squaring this inequality, we arrive, after rearranging terms and using the triangle inequality,
(p++1-p')) pp)²² s (pr p-) n6 2p. pp) + 4 1lt [t ""].00 m 86 (1
l9el 7t 2
Rearranging terms once again, get:
2p p²) S (pt- p²)² + n - (pi+1 p²)² + +4. 4. 111 m de (1
19el
n7
2
Dividing this by 11 > 0, we get:
1 ((pr -0'2 ( (p(41 - p²)²) no? + 4- 1[t [t] 6,
1 +
(p: p²) S 7h
1h
Noting that Eig. (p.) by definition of 9t, well as using the bounds the expected gradient moments from Claim 3, we can take the expectation of the last inequality to obtain:
( 1
Ellg [Fc]
(p) x²) m
((p+ p²)² - El(p-11 - 1=)3( + + 1E
+4 1le 11s) 8
.8.
716
14

---

Stronger Neyman Regret Guarantees for Adaptive Experimental Design
+ -(00)--)0(---))111))) h0) + 4 11- de ( +
1/t
7
Returning to the strong convexity-induced inequality above, we thus have:
f((p)) - s+(p") - (pt) (p: - - - p²)²
1
- 2tk
((p: - pp)²² - E[(pt+1 - p0) (=))) + -Ch((t)
(1 +C2n(0P) [pt p²)²
2 . 1st s 19.60 56
1/1
1 è (pr -²"²²
1
El(eett p" p1) + m C²1(1)
277t
2nt
(++01())))
2 1st s 1-1
5z
1)t
Now, taking expectation again, now with respect to the randomness up through Fe, we obtain the statement of this claim.
Claim 6 (Convergence Bound). For any time horizon T, and any p" E {1t 122, we have:
T
Σ E(fe(p)) - fe(e')
C
(log(T +1) + 20 (1 [+ 9 hav (1+
- - ()) + 2
(han (1+ +1)
+ 20²
Proof. Summing the inequality in Claim from t T, we obtain via telescoping sums:
T
[lfe(Pe) - f(('')
T
T
T (Ch(t))
<
1
- c²
El(pe- -P")2-
Σ
[p(+1 - p0
E
Σ 1=1
m
2m7
2n
t=1
1=1
( (m-11
1
+
2
1lt S 11..
+ (Ch(t))2
17: h(t))
1=1
T
T E((ee1 - =p")]- Σ
<
1
②
El(pr -p')--
Σ
ne (Ch(t))s
217
27
+2
+ (Ch(t)))
h(t)
(=1
5
1
?²
E[(pi -p")²|- Σ
El p2)
21/1
21kt
t=1
T
t"
5 + (Ch(T))
T1. + 2t" (Ch(t")) +2 Σ
h((1)
t=1
t=1
1
1
?
Ei(P - -p*)²-
B((p++1 - 2
2m11
21/T+1
T
T B((pi- -D*)² [ (+}+((C(TT)) Σ
2)
nh + 21" (Ch(())² +2 2
2tfr
21p-11
T/e
h(()
2
2m1
15

---

Stronger Neyman Regret Guarantees for Adaptive Experimental Design
S -T 1)) E)((rr -p") (Ch(T)) 20²
(log(T+)++1) + (C) 4c t
h(t)*
Finally, recalling the definition of t" (A) hiv (1 C/c) and substituting it in, obtain the desired claim.
Finally, with the result of Claim 6 in hand, observe that (1) the term -T thus be ignored, (2) the second term on the right hand side is asymptotically (((h(T))² log 7", and (3) the third and fourth terms on the right hand side are constant with respect to T and only a function of the constants C, of the problem. This gives the desired result.
- p²)²] ] is nonpositive and can
B.2. Convergence of Treatment Probabilities of ClipOGD Proof of Lemma 3.3
We will make use of Claim 6 from the previous subsection. Simply rearranging the terms, we obtain the following bound for the deterministic setting:
2T + 11 ()P+1 -7)
Σ
Blf((p.) - f((PT)] 2
+ (1)
t=1
where the (1)) term hides terms in the bound that do not depend on T. Dividing through by c². (T 1) and reindexing for convenience, we obtain the desired result:
(
E Regr) +
(h(T))² log
E((PT - - -
T
C. Confidence Interval Guarantees: Proof Sketch for Theorem 3.7
Remark C.1 (Chebyshev vs. Wald Confidence Intervals). As Dai et al. (2023) point out, it appears that ClipOGD may lead to an asymptotically normal distribution of the IPW estimator. If this were true, that would allow us to get Wald-type confidence intervals for the IPW estimator based on the variance estimator VB, which would be narrower than Chebyshev-type ones. Through some simulations, we observed that asymptotically, the z-score of the IPW estimator induced by our adaptive scheme appears to satisfy asymptotic normality. However, below we only prove the validity of Chebyshev-type confidence intervals, and leave Wald-type CIs to be explored in future work.
We will convince ourselves that the techniques employed in Dai et al. (2023) for proving the validity of this variance estimator apply to a broad class of udaptive sampling schemes. Dai et al. (2023) state this result for their particular adaptive design but mention that it may apply to other learning rate and clipping rate settings. And indeed, we find that while their approach does depend on the adaptive design having sufficiently slowly decaying clipping rate and vanishing Neyman regret, is oblivious to hyperparameters such as the learning rate. Moreover, we find that the condition of having asymptotically nonnegative Neyman regret, which Dai al. (2023) impose on the design, is also not necessary to ensure that the variance estimator VB is conservatively valid.
For easier tracking of the relevant quantities, recall the notation: ST(1) = V E (e)2 for E (0,1). Following
(Dai al., 2023), we define the quantities (1) (1)) = (0)) as well as the quantities Ar 5 yr (1)) 2 (7 + E, (1)) T-pt that estimate them in unbiased way. Recalling that the variance of the optimal nonadaptive design (i.e., the variance of the IPW estimator that uses p7. as its fixed sampling probability on all rounds t 1...?.))
2 - (1 + ()ST(1) < VB = T Ar(1)Ar(0),
4
we can see that VB + V Ar(1) simply aims to approximate the upper bound VB on the optimal fixed-roobbiliig sampling scheme's 's variance. And given that our design has a no-regret guarantee with respect to this benchmark, VB thus also asymptotically approximates the upper bound on our (and any other such) design's 's induced IPW estimator variance Vz. This is the blueprint the proof, and we will now briefly revisit the technical steps in Dai et al. (2023) that make this blueprint argument work.
16

---

Stronger Neyman Regret Guarantees for Adaptive Experimental Design
First, Proposition D.1 of Dai et al. (2023) proves that
C
AT(1)AT(0)) S T
which by tracking the proof can be seen to not depend on the sampling scheme.
Second, by generalizing the result and steps of Proposition D.2 of Dai al. (2023), we can bound the variance of the (normalized version of the) estimator VB as:
Var (1 (1)Ar & C C
T + C (((T))) 20 ((T)
T I
T
Thus. applying Chebyshev's inequality to this variance bound and using the preceding in-expectation bound, we conclude that AT( + (1))Ar(()) in probability the rate ()(
Now, in the proof of Theorem 5.1 of Dai et al. (2023), applied to this in-probability convergence result to give the implication that V Ar(1) - (AT(1)Ar(0) at the same asymptotic rate (T())) Indeed, since the target random variable Ar (1) is bounded below by o² by Assumption 3.1, the square root transformation will be Lipschitz on the relevant range (i.e., away from zero).
observe that Continuous Mapping Theorem can be
Finally, to establish the validity of the Chebyshev-type confidence intervals given above, it suffices to look at the z-score statistic Ç = -r- and the estimated z-score statistic Ç' Ir-fr and establish that stochastically dominates Ç².
Var(Fr)
Towards this, note as in Dai et al. (2023) that:
Var(fr) VB
T VB T VB
s'=c.
First, since the estimator ir is induced by a no-regret adaptive design and since VB is upper bound on the vari- ance of the best fixed SRS scheme (which serves the benchmark of the design's regret performance), we have that 1. Second, from what we just obtained, T VB T VB probability, which in view of VB VB
lim sup Ver(fr)
T-V converges to in probability. By Slutsky's theorem, this proves the desired stochastic domination and thus implies that the proposed confidence interval construction is asymptotically (conservatively) valid.
being lower-bounded by a constant by Assumption 3.1 implies by the Continuous Mapping Theorem that V
TAVB
D. Multigroup Adaptive Design: Proofs and Details
D.1. OLO Primitives
Our multigroup design will rely on sequence of reductions, derived with the help of some online learning machinery: a recent reduction of Orabona (2024) and scale-free algorithms by Orabona & Pál (2018). First, we spell out the algorithmic primitives that we will require.
Definition D.1 (OLO algorithm: OLO regret). An OLO (online linear optimization) algorithm A over domain C Rd where d 2 the dimension of the problem, sequentially receives vectors & E IRdd 1,,, 1,2,...... Each & is interpreted as the "gradient", the "loss", that A suffers round t.
Each round, before seeing l, algorithm A outputs iterate o, V function of past history. The algorithm's 's regret at any time 7' is defined as the total loss incurred by its iterates minus the total loss of the hest-in-hindsight admissible solution:
(A) max (egr(A:)), where (e:r(A: E (l,, o) for v E DEV
Definition D.2 (Sleeping Experts algorithm; SE regret), A sleeping experts (SE) algorithm A over domain V C Rd, where 2 is the number of "sleeping experts", sequentially receives vectors a, E {0, 1]a and & E Rd at rounds = 1,2,.... The vector a, has the interpretation that oz, E [0, (for each E [d] denotes whether expert i "active" (1) or "inactive"
17

---

Stronger Neyman Regret Guarantees for Adaptive Experimental Design
(0) in round I. The vector & has the interpretation that at any round for all active experts (i.e., dt,5 1), expert i's loss frei while for all inactive experts the loss coordinate f is (arbitrarily) equal to O.
Each round, after seeing 4, but before seeing 4 (i.e., after seeing which experts are active but before seeing their losses), the algorithm outputs distribution E Ad as a function of past history, such that U = 0 for all inactive experts (i.e., for all i such that az,; = 0). In words, at each round the algorithm is required to output a distribution ey over the currently active experts only.
The algorithm's Sleeping Experts regret at any time T is defined as the upper bound, over all experts i E [d]. on its performance relative expert over those rounds t on which was active:
T
(egSE)((A)) == max iEId
Σ
ags (14,, v1) l1,s)
We will make use of a scale-free OLO algorithm (Orabona & Pál. 2018) to design base algorithm for our multigroup regret algorithm. The property of any such algorithm is that its regret bound does not require the norms of the gradients& & to be bounded in [0. 1] for some norm (like standard OLO methods typically require).
Scale-Free OLO
Fact (Theorem of (Orabona & Pál, 2018)). Fix any norm ||-I| and its dual norm ||-II.- Then, Algorithm 3 called SOLO FTRL achieves, for any convex closed set V C IR, the following regret bound to any point
V that scales with the
magnitude of the losses/gradients:
T
|1 + 3.5 3.55min min { {VT - 1, diam(V) max ||
(SOLO FTRL; v) & (R(u) + 2.75)
(E[?]
where dVam(V) = sup, vV [|u - V2ll. and where SOLO FTRL is parameterized by an arbitrary nonnegative continuous L-strongly-convex regularizer R: R.
Algorithm 3 Asoro: SOLO FTRL (Orabona & Pál, 2018)
Receive domain V C d base regularizer R(w), and norm |1-11- Initialize Lo + 0d +- O. for t = 2, do Compute new weights wy +- arg min ((L,-1, + Re [. where Re(w)- = v R(w).
weV
Receive loss vector l2. Set L LL-1 + lz. Set qt +- 9:-1 + 11
end for
D.2. Designing a Scale-Free Sleeping Experts Algorithm
Now, let us instantiate the above Fact appropriately. First, set the norm for the regret bound to be the 2-norm: ||-11 I|- 21 Second, set the regularizer to be R(v) ||0| for V. which is 1-convex with respect the 2-norm. Third, set the domain of the algorithm to be the non-negative orthant: V R We then arrive at the following guarantee.
Corollary D.3 (of Fact 1). With the nonnegative orthant V = RS domain and the squared L2-norm regularizer, SOLO FTRL achieves the following scale-free regret bound for all u V:
Regr(SOLO (SOLO FTRL; < (1e111 + +.25) max |lell2 VT.
Reg,
[E[T]
The instantiation of SOLO FTRL for these specific choices given in Algorithm 4.
We note that the update for we in Algorithm 4 is the solution to the original argmax problem in Algorithm 3, with the nonnegative orthant as domain and the rescaled ng-morm as regularizer.
18

---

Stronger Neyman Regret Guarantees for Adaptive Experimental Design
Algorithm 4 Asoro: Instantiation for scale-free sleeping experts
1: Initialize Ly 0 90 0.
2: for 1,2, do
3: Set weights + max { (0"
vi--I 1 (coordinate-wise maximum).
4: Receive loss vector & E R2
20
5: Set Lt + LL-1 +c.
6: Set qc + 9--1 + ||6s 1|
7: end for
Scale-Free Sleeping Experts Now, we will turn this just obtained scale-free OLO regret guarantee into a scale-free sleeping experts regret guarantee. We will utilize recent black-box reduction mechanism of Orabona (2024), which proceeds as follows.
Fact 2 (Sleeping Experts to OLO Reduction (Orabona, 2024)). Consider a sleeping experts setting with d experts. Define any base OLO algorithm A with nonnegative orthant = I2 as the domain. Then Algorithm which we refer to as AOLO-SE, constructs sequence U1 ...... of distributions over active experts that attains the following sleeping experts regret bound:
(
RegSEy(AoLo--E)
max Regr DESB(R.)
i0)
Here, (B(R)) as the collection of the d standard basis (unit) vectors of Rd; and the vectors {fr defined in Algorithm 5, are surrogate loss vectors. Note that these surrogate losses satisfy | I 2 lleell relative to the original losses {Ce
Algorithm AOLo-SE: Sleeping Experts to OLO Reduction (Orabona, 2024)
Initialize any base OLO algorithm A with nonnegative orthant V Fd domain. for t 1, do
Get unscaled prediction wa R2o from A.
Receive indicator vector deseribing which experts are active: 0, E (0, 1]d as for i [d].
Construct distribution U2 Ad as: Ut (a),0))
Receive loss vector & E IRd.
Construct surrogate loss vector E, as Ee, = oc, - (l), for i E [d], and send it to A.
end for
To obtain sleeping experts regret bounds scaling with the norm of the losses, we can implement this reduction with the scale-free Algorithm 4 its base. Formally, we have the following statement.
Theorem D.4 (Scale-Free Sleeping Experts Algorithm). Consider sleeping experts setting with d experts. Initialize Algorithum 5 using Algorithm 4 (an instance of SOLO FTRL with settings described in Corollary D.3) as its base OLO subroutine. Call the resulting sleeping experts algorithm Asoro SE, with the pseudocode given in Algorithm 6. Then, SOLO SE obtains the following sleeping experts regret bound on any sequence of losses {le Heeme
RegSEy (Asoros se ((lohetr)) S 15 max [1 VdT.
tE(T]
D.3. First-Order Neyman Regret Minimization
We now formalize (and generalize) how the ClipOGD design operates. This formalization will define the scope of noncontextual adaptive designs that can be used to estimate group propensities for all groups in our multigroup design.
Definition D.5 (First-order Neyman Regret Minimization). Recall the Neyman objectives: fe(p) yx(1)²
(0) for
1-p
E (0, 1), t 2 1, where (1() 3e (0)) are the potential outcomes.
first-order Neyman regret minimization algorithm AATE follows the following protocol for sequential ATE estimation: At each round 1, 1,2,.... ANTE decides on treatment probability Pt. (1/h(t), 1/h(t)), where h N. - Ryo is
19

---

Stronger Neyman Regret Guarantees for Adaptive Experimental Design
Algorithm 6 Asono SEt Sleeping Experts Algorithm
1: Initialize AsoLo, an instance of Algorithm 4.
2: for = 1,2.... do
3: Receive unscaled weights w2 12 from Asoro-
4: Receive indicator vector describing which experts are active: as E 13. ae,swh. for E [d].
5: Set rescaled weights v4 E Ad as: Vt,3 Tar.wr)
6: Receive loss vector 4, R..
7: Set surrogate loss vector l, as le, al, 21) for [d].
8: Send & to Asoro.
9: end for
strictly increasing clipping function. After that, AATE receives feedbbcc Jt from the environment, which is random variable that satisfies the following properties: (1) It is adapted to the natural filtration {Fehe21 of the process, i.c., the distribution of ge determined by all prior history up to and including determining pri (2) an unbiased estimator of (P:), in that B [] f((p)) (.)
(0)
+ (1-pa)2-
PC
It is easy to observe that Algorithm I conforms to Definition D.5. Algorithm I is written as requiring direct access to the selected outcome Y, but this outcome is only used to compute the unbiased gradient estimator (pt).
D.4. Multigroup-Adaptiee Design via Sleeping Experts
We are now ready to present a context-aware algorithm for online ATE estimation. It uses scale-free sleeping experts as derived above, as well first-order Neyman regret minimization algorithms as base learners. The following theorem states its most general guarantees (as well as the specific instantiation that gives MGATE). The proof is presented in the next subsection.
Theorem D.6 (Guarantees for Algorithm 7). Consider any first-order Neyman regret minimization algorithm AxTR and any scale-free sleeping experts algorithm Agg. Fix any context space and any finite group family G C 2 If the base learners for all G G are copies of AATE, Algorithm 7's expected multigroup regret will be bounded for all G as:
E (RegVarry G)] < E [RegSE, (Asa)) +
Moreover, Algorithmm 7 anytime, it does not require advance knowledge of the time horizon T.
Instantiate Algorithm 7 using h-clipped ClipOGDSC the base ATE algorithm, for some strictly increasing h, and use AsoLo (Algorithm 6) as the scale-free SE algorithm. Then, we obtain the MGATE design (Algorithm 2) that simultaneously offers the following guarantees for all G E eg:
E
= 0 - (V(IT-((M(T)) vT)
(M((T))
D.5. Proof of Theorem D.6
First, note that with the Neyman objective defined, as always, via fe(p) x=(1)² v.(0)² group G G:
for p E (0, 1), we have for any 1-p
RegVar, = Σ [xa E Gl (fe(pr,ea) - f((PT,)))
(E
Σ 1/r E ft
Σ
wi. pr, (P,
f
G'EG.
<
1|r G
Σ
wio So (pr.r)) s(lr,
Gres
20

---

Stronger Neyman Regret Guarantees for Adaptive Experimental Design
Algorithm 7 General Multigroup Adaptive Design
Input: First-order Neyman regret minimization algorithm AATE.
Input: Scale-free Sleeping Experts algorithm ASE.
Input: Feature space X, group family C 2*
Initialize [g] copies of AATE: for I. ., do
Get context 2, X. let 9t = {G E 9: E G}.
for active groups G E Ge do
Get group-specific advice Pt, from AATE(G).
end for
Get weights (we,a)Ges, of active groups from ASE.
Set treatment probability: Pt,fft Eceg, WaG Pt,G-
Set treatment decision: Ze ~ (ernoull(((r.ttt)
Observe realized outcome: Y + (Z)). for active groups G E Gr do
Set estimated loss of AxTE(G) as: &,, Y?
2,
+ 1-2,
( 21 1-2,
Peintt
I-Pe
PL.
1-pi.c
Set estimated gradient of AATE(G) as: J1,G t Y??
1/ + I-Pt,
1-22
(- (-Zz
+ 1-7
Priet
Pic
[I-PA,)
Send estimated gradient IG. back to AATE(G).
end for
Send estimated losses flE, back ASE.
end for
Σ Im E
Σ wi Se ( fi(P,,))
G'ESi
Sleeping Experts Regret Aggregation
1|, E G) (f(l..
Term ATE Noyman regret on Group G
Here, Pr.c: denotes the best-in-hindsipe static treatment allocation probability on the set of rounds up round T that correspond to group G. The inequality holds by convexity of the objective St-
What we just did is partition the multigroup regret expression into two terms. The expectation of the second term is bounded by the expected regret of the group croup-specific ATE Neyman regret minimization algorithm: E. Termm 2] < E [RegVar, The first term will be bounded by the sleeping experts regret of the aggregation algorithm.
To continue the analysis, we first collect the properties of the estimated outcomes, losses, and gradients. Namely, we have for any round and for any group G E Gr:
e " (2:31-1
Pr,eff
(w((1)) Pt,
(1 Pt,eft)
(1-Pe,eff a-fff (-11))1..Pp)) ft(Pr,o);
(0)(
|āll
maxxes. K
maxces, max
Pt,e [1 (1-P),ot):( (1-M.)) - SC
(1))
(0))
E
[ -PPteetf) (1 Pr.ett (I-Ptc)) Pt.eff (ve(1))
(v)(
P.ott f((r,));
E
{2, ||
(1 Pr.eff)
(0) (I-PL,et) (1 = + Pt,ff
Pr. < 2(2)())2;
(u.11))
E
2
[2r)1-1 [--
= (1-Pheett
Pr.ttt)
(1-ph.ot) (P)t
(1n(01)2
2
+ Pt.off
(mn(1))2
< 2
21

---

Stronger Neyman Regret Guarantees for Adaptive Experimental Design
The last calculation holds owing to the fact that at any round I, the aggregated probability Pr,eft is convex combination of the probabilities Pt,G for all G G.. Indeed that implies
min (Pr,otr, (1 Pt,ett]] }} 2 min (pr.o, (1- 2 1/h(t),
GE9.
(t,tft, et.)tt)) s h(t). leading to the bound max eft 1/ (1 -
By the first of these properties, we can bound the expectation of Term 1 as follows:
T
E Termm 1] = E
Σ 12.
EG]
Σ
wa, . Se (pt,or) - Se ((o.c))
G'Eat
Wr, E [1.0 {2r 1 - tno (2-111)
Σ 1|r, E G]
Σ
E
G'Est
E
[1 E G E
Σ 11o E1,00 - t,, [z+)1-11
L
(W) Ee) E | 1111 =]
= E
[/r E G]. E
T
G] E R (wr. Ei) - to [z, []
1 [xe E
1=1
ts0)
=E
Σ 1 Gl
(wir
S E (r
Thus, in combination with the above we indeed have:
E [RegVarMG < E (AsE))((AsE)] E [RegVarr(AATT)).
We now going to instantiate this regret bound with the following concrete choices. ASE will be instantiated as the scale-free sleeping experts Algorithm 6. For each copy of the first-order ATE Neyman regret minimization method, we will use the modification of ClipOGD SC which uses, instead of its originally specified gradient estimator 9t, the gradient estimator 5. specified in our multigroup Algorithm 7.
Our specific choice of ASE thus leads, by Theorem D.4 with our above bound on
?
plugged in, to the following bound:
20
E (AsE) < 15 max (E[T]
|oe VeT S 150² Vigl (H(
Now we update the regret bound of ClipOGD to use Jt instcad of ge at each round t. From the analysis of Claim 5 and Claim 6 in the proof of Theorem 3.2, we can distill the following inequality holding for any unbiased gradient estimators he and for the optimal p":
T
T
E Regg (RggVar,(AATE)) = Σ E(f((n)) - f((p)) S
Σ M EGG F 1--1
2
h(t) + EE
[=1
So it suffices to bound the first and second absolute raw moment of 9: in terms of the overlap function h in order to obtain concrete regret bounds. From the facts established above, we have at any time horizon T of the multigroup algorithm: E. | [ 2C**(t)*)(T), and E [r, [2 2CCh(t))(TT). Plugging this in and recalling
the learning rate setting 17, 2. we obtain:
E[eegVary (AATT)) < (Ch(T))
(log(T + +1) + + 26 C)((()(TT) + 422 Σ t
20
1=1 T((1)
22

---

Stronger Neyman Regret Guarantees for Adaptive Experimental Design
(Ch(T))' (Tog(T +1) + 1) + +22 (1 (1+ 9 2c
)) Ninw (1+ h(T) 20² (Mime (1+
-) + ))²
+1)+11
((h(T))) Tog
Thus, asymptotically in T this modification of ClipOGD obtains the same rate. The only difference is non-asymptotic; we now acquire an additional term that depends T in a low-order way: 2C (1 + C1/C/c hin (1 + C/c) A(T), which formerly had additional factor of (1 + C/c) instead of h(T). Even though this term is lower-order in T, but nonetheless it merits mention, as here (T) coexists with the inverse clipping rate mapping, hivv, being evaluated at "critical point" 1 + C/c. Since the inverse mapping /inv will grow fast when h grows slowly, this term can practically speaking become influential in the regret bound if the problem is not well-conditioned (if C/c is very large). Thus, in practice this term may merit a tradeoff in choosing h to not be too slowly-growing.
To conclude the proof, note by collecting the above two bounds that:
E [RegVarMGr(449)
< E. [RegSE,, + E [RegVar,(AAre))
S 150 Vlgi (N(T)) ((h(T)) log T)
$ 0 ( - vT)
E. Additional Experimental Results
In this section, we present experiments on additional real-world dataset. We list them below along with their descriptions. We then turn to the description of the results.
E.1. Task and Dataset Descriptions
Large Language Model Benchmarking We test our methods on (a subset of) large language model (LLM) benchmarking data that was examined by Fogliato et al. (2024), and includes BigBench (Srivastava et al., 2023), MedMCQA (Pal et al., 2022), XCOPA (Ponti al., 2020), HellaSwag (Zellers et al., 2019), MMLU (Hoffmann al., 2022), and XNLI (Conneau et al., 2018). Multiple LLMs are compared on these datasets, with each model producing vector of logits for each data point. These logits are turned into probability vectors. Since each task is supervised, we know the correct answers. We select two (control)-and build two parallel outcome sequences using the model accuracies. More specifically, for each data point, the model's chosen answer is the class with the highest predicted probability, and we define accuracy as if this chosen class matches the correct answer and otherwise.
(Jiang et al., 2023) (treatment) and Google Gemma-2b (Team et al., 2024)
ASOS Digital Dataset We use the sequential experiments dataset from Liu et al. (2021), gathered by ASOS.com between 2019 and 2020. It has 24,153 rows from 78 online controlled experiments. Each row represents a group of users who arrived during a certain time span and shows the average treatment and control outcomes for those users. Across all experiments, there are 99 different treatments and one control. The dataset tracks 4 consistent metrics; each row focuses on one of these metrics. This structure naturally creates 4 subsets of rows (each with about 6,000 rows). We treat each subset as separate dataset and feed each of these 4 pairs of treatment and control outcome sequences into ClipOGD and ClipOGD This setup keeps outcome definitions consistent within each subset, while mixing different experiments and thus providing varied environment for evaluating sequential ATE estimation methods.
E.2. Experimental Results
1. LLM BENCHMARKING
Figure 4 shows the experimental results across these six tasks (BigBench-MC, HellaSwag, MedMCQA, MMLU, XCOPA, XNLI). The top row shows that the treatment probabilities of ClipOGD" (orange) fluctuate more, while the treatment probabilities of ClipOGDSC (blue) settle closer to a stable value. Although our algorithm's 's assigned probabilities may initially jump around more because of the more aggressive clipping rate, they also stabilize more quickly. The second row shows the variances and tells a similar story: the variance ClipOGD is smaller and decreases faster compared to that of ClipOGD As seen in the bottom row, the Neyman regret of ClipOGD stays away from zero, whereas the regret
23

---

Stronger Neyman Regret Guarantees for Adaptive Experimental Design
of ClipOGD*c shrinks toward or remains lower throughout. This pattern suggests that ClipOGD converges the Neyman-optimal probabilities with less fluctuation and lower regret than ClipOGD
Treatnent probebiity
Bigliench-MCC
HellaSwag
NedMCOA
MMLU
XCDMA
0.60
0.00
0:60
0.60
0.60
0.50-
0.50-
0.50
9.45
0.40
0.20
0.20
1e103
14:
Ten05
1c:03
36-05
16:04
10
Ie:03
3e/03
1s:03
3e103
1o:04
5e
52-02 1e103
3e108a 03
1e 10 103LD 10
BigBench-WEE
HolbSwaq
NodMC.OA
MMLU
XCOPA
XWLI
0.92
Variance
0.60
0.90
0.60
0.88
0.72
0.00
0.55
0.63
0.86
0.50
1e403
Ie-04
Ie405
Ie-03
3e-03
1e+06
402
1e403
Je+03
1e-03 JeH03 1e-04
5e-02 1e403
Je Je+09e-00
1e-00 1e
DigUeenc--MCC
HelloSwag
0.0
0:15
0.05
0.05
0.06
0.06
004
0.10
0.04
0.04
Neyman
0.02
0.02
0.00
0.00
10403
1c-04
1c+03
3:403
16404
5e102 16+00
3c403
16+03 30+03 1s:04
Se-02 1er03
36-03e+03
1E-032e-011e-00HH
Round
Method
CUPGGS
CLeDG6
Figure 4. Treatment probabilities, variance of the ATE, and Neyman regret of ClipOGD on LLM benchmarking data. The solid black line the treatment probabilities indicates the Neyman optimal probability. Additionally, we show the per-group Neyman regret of MGATE and ClipOGD the contextual experiments.
24

---

Stronger Neyman Regret Guarantees for Adaptive Experimental Design
ds: BIgBench-MC
ds: Bigh
de: BigBench-MCC
ds: Hello
ds: He HellsS
group:
group:
group: 2
group:
group:
0.20
0.15
0.15
0.09
0.06
0.10
1.0
0.03
0.05
0.5
0.5
0.00
0.00
0.00
1e403
1e404 10405
1er03
1e404 1e405
1e403
18404 1e-05
1e403 3e403 1e:04
1e:03 3e403 1e404
ds: HelllHlllSSs wag
ds: MedMCQA
ds: MedMC QA
ds: MedM C.O.A
ds: MMLU
group:
group:
group: 1
group:
group: 0
0.05
0.04
0.04
1.0
0.03
0.02
0.03
0.03
0.02
0.02
0.5
0.01
0.01
Neyman regret
18:03
3e-03
10404
Se 40+
3eH00 +03
5e+02 1e+03
3e-05e#03
5e 1e403
3e+CSe +03
0.00
1e 1033e3303 104043e
ds: MMLU
ds: MMLU
ds: XCOPA
ds: XCOPA
ds: XCO
group:
group:
group: 0
group:
group: 2
1.5
0.03
1.0
1.0
1.0
0.01
0.01
0.5
0.5
0.00
0.00
10-03
30-03 1e+04
10:03 40+03 1o-04
16-03
3eH03 18/04
Se-022e403
3e-088--03
5e-021e+03
30-03a+033
ds: XI
ds: XNLI
ds: XNL
group:
group:
group: 2
0.100
0.100
0.15
0.075
0.075
0.10
0.050
0.050
0.05
0.025
0.025
0.000
1e403
1e+04
1e+05
1e-03e--0te+-0--000 Round
Method
MGATE
C
CLIPOGD
Figure 5. Group-conditional Neyman regret of ClipOGD and MGATE the LLM Benchmarking data.
25

---

Stronger Neyman Regret Guarantees for Adaptive Experimental Design
E.2.2. ASOS DIGITAL DATASET
Figure 6 shows the Neyman regret this dataset. Across all four metrics, ClipOGD (blue) steadily reduces Neyman regret, whereas ClipOGD (orange) remains higher grows time. Although the regret levels vary by metric, ClipOGD consistently converges closer to the Neyman-optimal probabilities shown by the shrinking regret.
Metri 41
Metric #2
Metric 43
Metric MN
Neyman regret
0.100
3000
0.0015
0.075
2500
0.0010
0.050
2000
0.0005
1500
5e-02
1e+03
3e+03
Se-03
5e+02
1e+03
3e403 Se+03
Se-422
1e-03
3e+03 Se+03
5e+02
1e403
3e+03 5e+03
Round
Method
CLIPOGD"
CLIPOGD
Figure 6. Neyman regret of ClipOGD the ASOS Digital Dataset.
Additionally, we show the per-group Neyman regret MGATE and ClipOGD the contextual experiments. Here we observe that MGATE and ClipOGD attain close to optimal Neyman regret guarantees all groups
26

---

Stronger Neyman Regret Guarantees for Adaptive Experimental Design
group:
group: 1
group:
0.006
metric:
0.004
0.002
0.10
metric:
Neyman regret
0.05
0.00
6
metri:
3000
metric:
2500
2000
1500
5e+02
1e+03
3e+03 5e +03 5e+02
1e+03
3e+03
5e+02
1e+03
3e+03
Round
Method
MGATE
CLIPOGD
CLIPOGD
Figure 7. Group-conditional Neyman regret of ClipOGD and AMGATE on the ASOS Digital Dataset.
27


Reviews:
[{"review_id": "BCAOLSw6Tm", "reviewer": "Reviewer_Wd4Y", "summary": "This paper explores efficient ATE estimation in adaptive experimental designs. The authors focus on Neyman regret, which quantifies the variance difference between the inverse-propensity-weighted (IPW) estimator under the proposed adaptive design and the best fixed design in hindsight. Prior work (e.g., Dai et al., 2023) established a sublinear $O(\\sqrt{T})$ bound on Neyman regret. This paper strengthens that result, achieving an $O(\\log T)$ bound under slightly stronger assumptions. The analysis is further extended to contextual (multigroup) settings, introducing a method that ensures $O(\\sqrt{T})$ regret across multiple overlapping subpopulations. The approach is validated both theoretically and empirically.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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. \n\nThe 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.", "claims_and_evidence": "1. **$O(\\log T)$ Neyman regret in the noncontextual setting**  \n   While previous work (Dai et al., 2023) established an $O(\\sqrt{T})$ regret bound using the ClipOGD method, this paper demonstrates that, under stronger boundedness assumptions on potential outcomes, the regret can be improved to $O(\\log T)$.\n\n2. **Multigroup (contextual) extension**  \n   The paper introduces MGATE, an adaptive design that leverages pre-treatment covariates to form groups (which may overlap) and jointly optimizes assignment probabilities for each group. The resulting multigroup Neyman regret guarantees a sublinear $O(\\sqrt{T})$ bound for all predefined groups simultaneously.\n\n3. **Theoretical analysis and empirical validation**  \n   The paper presents a rigorous theoretical analysis, establishing regret bounds for both noncontextual and contextual settings. Additionally, it provides extensive empirical validation using synthetic and real-world datasets, demonstrating that the proposed methods consistently outperform or match existing approaches in terms of regret reduction.", "methods_and_evaluation_criteria": "1. The overall approach builds on ClipOGD (online gradient descent with clipping) and **sleeping-experts algorithms**. The incorporation of sleeping-experts algorithms is particularly interesting and innovative.", "theoretical_claims": "1. I was personally surprised that the authors achieved a regret bound of $O(\\log T)$ instead of $O(\\sqrt{T})$. The authors clearly explain and rigorously prove their results.  \n2. The extension to multigroup settings enhances the method's applicability across various contexts.", "experimental_designs_or_analyses": "The paper presents a wide range of experiments and confirm the soundness of their proposed method. While I believe this paper primarily focuses on theoretical contributions and methodological advancements rather than experimental results, the effort put into these experiments is highly commendable.", "relation_to_broader_scientific_literature": "This study will have an impact on various fields, including economics and epidemiology.", "essential_references_not_discussed": "- I found the following potentially relevant paper recently uploaded on arXiv. It might be helpful to briefly discuss this work in your paper.\n\nNeopane et al. (2025). *Optimistic Algorithms for Adaptive Estimation of the Average Treatment Effect.", "other_strengths_and_weaknesses": "None.", "other_comments_or_suggestions": "- The notation in expressions like $\\sum_{t=1}^{T} y_t(1) - y_t(0)$ might be clearer with parentheses. For example, in Definition 2.1, you could write: $\\sum_{t=1}^{T}(y_t(1) - y_t(0))$ to emphasize that the subtraction is within the summation.\n- Li and Owen is cited as \"Harrison H Li and Art B Owen. Double machine learning and design in batch adaptive experiments. arXiv preprint arXiv:2309.15297, 2023.\" It is now accepted in Journal of Causal Inference.", "questions_for_authors": "None.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gwPUPxDsQi", "reviewer": "Reviewer_zBJq", "summary": "This work studies the design of adaptive, sequential experiments for ATE estimation in the design-based potential outcomes setting. The authors develop adaptive designs without/with covariates to achieve sublinear Neyman regret.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive assessment of our paper, in terms of both its contributions and writing, and for the interesting questions! \nTo address your points in the Strengths and Weaknesses section:\n1. 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.\n\n2. 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.\n\n3. 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.\n\n4. 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.\n\n5. Please find bias, variance and CI plots at: https://imgur.com/1P9sqbZ", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "I have checked the proof of the main theorems (3.7 and 4.2) which look correct to me.", "experimental_designs_or_analyses": "Yes the experimental designs are valid.", "relation_to_broader_scientific_literature": "The work contributes to sequential randomization with neyman regret guarantees.", "essential_references_not_discussed": "Not aware of any.", "other_strengths_and_weaknesses": "Strength: very clear writing. And the methods are good technical contributions to the literature. \nWeakness: \n1. Choice of estimator: the authors use IPW; however, in general Hajek version of IPW is much more robust choice in practice. Is the theory also work generally for Hajek estimator?\n2. The vanishing propensity score problem in adaptive experiments is actually studied in the literature. In particular, see Hadad 2019: https://www.pnas.org/doi/10.1073/pnas.2014602118. Is the learning rates here related to some weighting methods introduced in this paper?\n3. CI for Clipped Adaptive Design: Also check the Hadad paper - might have some connections. \n4. Multi-group extension: has the sense of best subgroup identification + best arm identification. Why are the pretreatment covariates not directly used to enhance efficiency?\n5. For simulation, can you also report the bias, variance and CI for the estimators with comparison between Dai approach and the proposed method?", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Tq2JjAn9ZI", "reviewer": "Reviewer_CD6v", "summary": "The authors make two main contributions in this paper: Firstly, in the non-contextual adaptive experimental design case, using stronger assumptions on potential outcome bounds, they change the learning rate and clipping schedules in Dai's ClipOGD algorithm to obtain stronger $O(log T)$ Neyman regret guarantees compared to Dai's $O(\\sqrt T)$ Neyman regret guarantees.\nSecondly, in the contextual adaptive experimental design case, using a variation of the \"sleeping experts\" algorithm, christened the MGATE algorithm, they leverage pre-experiment covariates for balancing treatment probabilities to obtain $O(\\sqrt T)$ multi-group Neyman regret, a new metric that they themselves define in this paper.\nBoth algorithms are any-time valid and do not require knowledge of the time horizon $T$.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive assessment of our paper and for the interesting questions. \n\nThe 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.\n\nNext, 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.\n\nNext, 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. \n\nThat 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.\n\nSo 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.", "claims_and_evidence": "Theorem 3.2 on non-contextual Neyman regret guarantees, for Algorithm 1, and Theorem 4.2 on multi-group Neyman regret guarantees, for Algorithm 2, appear to be the main theoretical results in this paper, although additional results such as Theorem 3.7 on confidence intervals for Algorithm 1, are also provided.\n\nThe authors also provide experimental evidence using one synthetic dataset and one real-world micro-finance dataset in the main body of the paper, to demonstrate the efficacy of algorithms 1 and 2.", "methods_and_evaluation_criteria": "The proposed methods and / or evaluation criteria appear to be sound for the problem at hand, as discussed under \"Claims And Evidence\" above and \"Theoretical Claims\" / \"Experimental Designs Or Analyses\" below.", "theoretical_claims": "The theoretical claims in Theorems 3.2 and 4.2 appear to be valid, although I didn't check the proofs in detail.", "experimental_designs_or_analyses": "Figures 1 (on the synthetic dataset) and 2 (on the microfinance dataset) clearly demonstrate the superiority of the proposed $ClipOGD^{SC}$ algorithm w.r.t. Dai's $ClipOGD^0$ algorithm, in terms of minimizing non-contextual Neyman regret.\nIn addition, Fig 3 demonstrates that Algorithm 2 (MGATE) is superior to $ClipOGD^{SC}$ (Algorithm 1) and Dai's $ClipOGD^0$ algorithm, in terms of minimizing group-conditional Neyman regret.\n\nI didn't check the experimental results on additional datasets presented in the supplementary material.", "relation_to_broader_scientific_literature": "References such as \"Balancing covariates in randomized experiments with the Gram–schmidt Walk design\" by Harshaw et al., and \"On Distributional Discrepancy for Experimental Design with General Assignment Probabilities\" by Rao and Zhang, on non-adaptive designs, use pre-treatment covariates to minimize the variance of the ATE. These references go beyond the group-based contextual setting considered by the authors in Algorithm 2, and may allow it to be further generalized for arbitrary pre-treatment covariate contextual settings. \n\nIn view of those known results, given the first contribution, the second contribution in this paper didn't surprise me. If space permits, the authors may wish to cite the above two references on non-adaptive designs.", "essential_references_not_discussed": "I couldn't think of any missed essential references.", "other_strengths_and_weaknesses": "Minor weakness:\nPrior to presenting Algorithm 1, the authors define the strictly increasing function $h$ using the natural number domain.\nHowever, in Theorem 3.2., the same function $h$ uses the non-negative real number domain.", "other_comments_or_suggestions": "Does the suggestion regarding generalization to arbitrary (non-necessarily group-based) pre-treatment covariate contextual settings under \"Relation To Broader Scientific Literature\" seem worthwhile to the authors ?", "questions_for_authors": "The author's mention Neyman's classical work on batch design, but do not make any attempt to relate their work to Wald's classical work on sequential hypothesis testing or design. Are connections with Wald's work already discussed in other cited references ?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hUZeCxisW3", "reviewer": "Reviewer_j79P", "summary": "Based on a stronger assumption, this paper improves the vanilla Neyman regret upper bound from Dai et al., 2023 by modifying the parameters of an existing algorithm. Additionally, the paper considers a contextual multi-group Neyman regret upper bound, for which the authors propose a corresponding algorithm and prove that it achieves a $\\mathcal{O}(\\sqrt{T})$ regret.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive assessment of our paper!\n\nWe 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). \n\nLower 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):\n\nOf 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. \n\nHowever, 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.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Yes", "experimental_designs_or_analyses": "Yes", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strengths: \n1. The paper is well structured. The introduction clearly outlines the motivation of the paper and its main theoretical contributions (i.e., improved vanilla Neyman regret upper bound and new contextual Neyman regret upper bound). Additionally, every symbol in the paper is well-defined.\n2. The paper makes multiple theoretical contributions. In addition to studying the upper bound of Neyman regret, it also investigates valid confidence intervals and the convergence rate of the best policy. \n3. The paper provides a thorough discussion of related work, especially regarding the technical foundations of its main theorem. The authors cite a series of relevant papers and present a clear outline of their proof.\n4. The experimental results are comprehensive.\n\nWeaknesses:\n1. The paper does not seem to mention the lower bound for contextual Neyman regret. As a result, it is unclear whether the contextual Neyman regret of the proposed algorithm is optimal.\n2. Regarding the vanilla Neyman regret, the proposed method in this paper only modifies the learning rate, which may not have high technical novelty.", "other_comments_or_suggestions": "Building upon Dai et al., 2023, this paper explores various settings and makes substantial theoretical contributions. I am inclined to accept it.\n## update after rebuttal: The authors have addressed my concerns, so I recommend acceptance.", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "N/A"}}]

Author rebuttal:

Meta-review: The goal of this study is to propose an algorithm that achieves sublinear regret for the problem of ATE estimation in sequential experiments. The paper constructs an algorithm that improves upon the existing upper bound of $O(\sqrt{T})$ regret to a logarithmic order $ \widetilde{O}(\log T)$. It also extends the framework to settings with multiple groups and contextual information.

The paper is comprehensive and well-written, with clear and substantive claims. The extensions and experimental support are appropriately included, and the discussion is well-balanced without any significant gaps or redundancies. Reviewers raised questions about the relationship to existing methods, but no critical technical concerns were raised. The authors responded appropriately to the questions, and the reviewers reacted positively to their replies.
Decision: Accept (spotlight poster)