CLIP-OGD: An Experimental Design for Adaptive Neyman Allocation in Sequential Experiments
Authors: Jessica Dai
Paula Gradu
Christopher Harshaw
Venue: NeurIPS 2023 spotlight (2023)
Keywords: causal inference
randomized experiments
online optimization
TL;DR: By adaptively setting probability of treatment assignment based on observed outcomes, we can achieve provably increased precision of effect estimators.

Abstract: From clinical development of cancer therapies to investigations into partisan bias, adaptive sequential designs have become increasingly popular method for causal inference, as they offer the possibility of improved precision over their non-adaptive counterparts. However, even in simple settings (e.g. two treatments) the extent to which adaptive designs can improve precision is not sufficiently well understood. In this work, we study the problem of Adaptive Neyman Allocation in a design-based potential outcomes framework, where the experimenter seeks to construct an adaptive design which is nearly as efficient as the optimal (but infeasible) non-adaptive Neyman design, which has access to all potential outcomes. Motivated by connections to online optimization, we propose Neyman Ratio and Neyman Regret as two (equivalent) performance measures of adaptive designs for this problem. We present Clip-OGD, an adaptive design which achieves $\widetilde{\mathcal{O}}(\sqrt{T})$ expected Neyman regret and thereby recovers the optimal Neyman variance in large samples. Finally, we construct a conservative variance estimator which facilitates the development of asymptotically valid confidence intervals. To complement our theoretical results, we conduct simulations using data from a microeconomic experiment.

CLIP-OGD: An Experimental Design for Adaptive Neyman Allocation in Sequential Experiments
Jessica Dai UC Berkeley jessicaddai@berkeeeeyy.. edu
Paula Gradu UC Berkeley pgradu@berkeley.cem edu
Christopher Harshaw* MIT charshaw@mit... edu
Abstract
From clinical development of cancer therapies to investigations into partisan bias, adaptive sequential designs have become increasingly popular method for causal inference, as they offer the possibility of improved precision over their non-adaptive counterparts. However, even in simple settings (e.g. two treatments) the extent which adaptive designs can improve precision is not sufficiently well understood. In this work, we study the problem of Adaptive Neyman Allocation in a design- based potential outcomes framework. where the experimenter seeks to construct an adaptive design which nearly as efficient as the optimal (but infeasible) non- adaptive Neyman design, which has access to all potential outcomes. Motivated by connections to online optimization, we propose Neyman Ratio and Neyman Regret as two (equivalent) performance measures of adaptive designs for this problem. We present CLIP-OGD adaptive design which achieves Ö (T) expected Neyman regret and thereby recovers the optimal Neyman variance in large samples. Finally, construct conservative variance estimator which facilitates the development of asymptotically valid confidence intervals. To complement our theoretical results, conduct simulations using data from microeconomic experiment.
Introduction
From medicine and public health to economics and public policy, randomized control trials used in a variety of disciplines to investigate causal effects. Typically, treatment assigned in a non- adaptive manner, where assignments determined before any outcomes observed. A sequential experimental approach, which adaptively assigns treatment based on previously observed outcomes, offers the possibility of more precise high powered estimates of relevant causal effects. Adaptive experiments are run to develop clinical therapies for breast cancer [Barker et al., 2009], evaluate incentives reduce partisan bias "Offer-Westort al., 2021], and evaluate customer acquisition via online advertising [Schwartz et al., 201 7]. to name a few.
In this paper, study the problem of Adaptive Neyman Allocation, which we informally define as follows. An optimal non-adaptive experimental design which minimizes variance of an estimator will depend the unknown potential outcomes, rendering it infeasible run. However, adaptively choosing treatment assignments in a sequential manner based on observed outcomes, we can hope to guarantee that the variance of the estimator under the adaptive design converges the optimal non-adaptive variance. The problem of Adaptive Neyman Allocation is to construct such an adaptive design which guarantees the variance converges the (infeasible) optimal non-adaptive design.
* *Coreespondigg author
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

An experimental design which sufficiently addresses the Adaptive Neyman Allocation problem offers the advantage of higher statistical power, relative to broad class of fixed experimental designs. Practically speaking, this means that either smaller confidence intervals are obtained for given number of experimental units, or that fewer units are required achieve confidence intervals of a given length. In practice, this means that investigating causal effects can be cheaper- in terms of time, money, and other valuable resources- experimental designs have been proposed for this purpose [Hahn et al., 201 1, Blackwell et al., 2022], none have provided formal guarantees that the optimal non-adaptive variance can be achieved and the effectiveness of such designs has recently been called into question Cai and Rafi [2022].
adaptive experiments are run. Although several
The main contributions of this work are follows:
1. Neyman Ratio and Regret: We propose two (equivalent) performance measures of ex- perimental designs for the problem of Adaptive Neyman Allocation: Neyman Ratio and Neyman Regret. We show that guarantees on the rates of these performance measures directly translate to guarantees on the convergence of variance to the Neyman variance.
2. CLIP-OGD: We propose the adaptive design CLIP-OGD, a variant of online stochastic projected gradient descent for which the Neyman regret is (VVT). This guarantees that the variance of the sequential effect estimator approaches the Neyman variance.
3. Confidence Intervals: By constructing a conservative variance estimator, we provide confidence intervals which guarantee asymptotic coverage of the average treatment effect.
In Section 7, we support these theoretical results with simulations using data from a microeconomic experiment. Our results rely on viewing the Adaptive Neyman Allocation problem through the lens of online convex optimization. However, as discussed in Section 4.2, due to the subtleties arising in the problem, we do not know of an existing online algorithm which directly obtains these results.
1.1 Related Work
We work within the potential outcomes framework for causal inference Neyman [1923], Rubin [1980]. Imbens and Rubin [2015]. The idea of optimal treatment allocation dates back to Neyman [1934]. where he demonstrates that sampling from treatments proportional to the within-treatment outcome variance will minimize the variance of standard estimators. Unfortunately, this type of design is not practically feasible when little is known about the statistics of outcomes from each treatment. Robbins [1952] highlights adaptive sampling as one of the more pressing open statistical problems at the time. In Chapter 5, Solomon and Zacks [1970] presents a survey of adaptive designs for survey sampling, but from Bayesian perspective. More recently, Hahn et al. [201 I] proposed a two stage design in a super-population setting, where data is uniformly collected from both arms in the first stage, statistics of the treatment arm are estimated, and a fixed probability derived from estimated statistics is used in the second stage. They derive the limiting distribution of the effect estimator under the two-stage design, which has a variance that is similar to, but asymptotically bounded away from the optimal Neyman variance. In design- based setting, Blackwell et al. [2022] propose similar two-stage approach and, through simulations, provide practical guidance on how to choose the length of the first stage. Although both of these works motivated by achieving the Neyman variance, neither formally show that this is possible under the two-stage design.
While the goal in this paper is to increase the precision of treatment effect estimates, a variety of response-adaptive designs have been developed for various objectives, including reducing mean total sample size [Hayre and Turnbull, 1981] and reduction of harm reduction in null hypothesis testing [Rosenberger et al., 2001]. Eisele [1994] proposes the Doubly Adaptive Coin Based Design, which is meta-algorithmm for targeting various allocation proportions when outcomes drawn i.i.d. from an exponential family. Hu and Rosenberger [2003] critiques many papponse-adaptiie designs as being "mypoic strategies" which have "adverse effects power", providing an asymptotic framework by which to judge adaptive design when the outcomes are i.i.d. and binary. This asymptotic evaluation framework was extended to continuous outcomes by Zhang and Rosenberger [2006]. An additional line of work has developed adaptive Bayesian methods for subgroup identification [Xu et al., 2014].
Causal inference under adaptively collected data has seen variety of recent developments which are adjacent to, but distinct from, the problem of Adaptive Neyman Allocation. One line of research has been to construct estimators via re-weighting which ensure consistency and normality when data

---

is collected via bandit algorithmss [Hadad et al., 2021, Zhang et al., 2020, 2021]. A second line of research has been to provide inferential methods which are valid under data-dependent stopping times (Wald, 1945, Howard et al., 2021, Ham et al., 2022]. Finally, Offer- Westort et al. [2021] propose an adaptive experimental design for improved selective inference, when only the effect of the best performing treatment is to be inferred.
2 Preliminaries
The sequential experiment takes place over T rounds, where we assume that T is fixed and known to the experimenter. At each iteration i E [7]. new experimental unit (e.g. clinical participant), enters into the experiment, so that there are T units in total. In an abuse of notation, we identify units with their respective round E [T]. The experimenter assigns (random) treatment Z₁ E {0, (e.g. drug or placebo) to the experimental unit. The unit has two real-valued potential outcomes (1)1,, 3/ (0) which are unknown to the experimenter and represent the unit's measured response to the treatment assignments (e.g. measured heart rate). The term "potential" is used here because while only one treatment is assigned and thus only one outcome is observed, both outcomes have the potential to be observed. At the end of the round, the experimenter sees the observed outcome Y 1[2 (1) 1 Oly,
2.1 Potential Outcomes Framework
In this paper, we adopt design-based framework where the sequence of potential outcomes (1). (0)] is deterministic and the only source of randomness is treatment assignment it- self. In particular, we place no assumption on the homogeneity of the outcomes: they are not necessarily related to each other in any systematic way. Although the potential outcomes are deter- ministic, we introduce finite population analogues of various statistics. Define the finite population second moments S(1) and S(0) and correlation of the treatment and control outcomes p to be
1 T T
and p= + E 34 (1)
5(1)
1 Σ (1)2 S(0)² T
Σ )o())²
S(1)S(0)
Observe that the correlation between treatment and control outcomes is bounded p E [-1,1]. Although we refer to p the correlation, it also known as the cosine similarity and is generally not equal to the Pearson correlation coefficient. We remark that although the potential outcomes (1(1) and (0) are deterministic, the observed outcome Y, is random, as it depends treatment assignment. The natural filtration according to these rounds is denoted as Fi... so that Fs captures all randomness before the sampling of Zt, i.e. the treatments assigned and outcomes observed in previous rounds.
random
In this sequential setting, the mechanism for random treatment assignment can incorporate observed outcomes from previous experimental rounds. This treatment mechanism, referred as the experi- menial design, is selected by and thus known to the experimenter. Formally, the experimental design is a sequence of functions {II, { with signature 11, (f0, RR)-1 - [0, 1] such that treatment is assigned as Pr(Z, 1 Fi) 11, YI.... Z,-1, Y--1). We denote Pt = Pr( Z. 1 Fi) as the (random) probability of treatment assignment at iteration f, given previously observed treatment assignments and outcomes.
The causal estimand of interest is the average treatment effect, defined as
T Σ vz (0) T = T
The average treatment effect captures the average counterfactual contrast between a unit's outcomes under the two treatment assignments. For example, this could be the average contrast of a clinical participant's 's heart rate under the drug or placebo. Individual treatment effects are defined as T. = (1) y (0), but they cannot be estimated without strong additional assumptions, only one outcome is observed.
A standard estimator of the average treatment effect is the Horvitz-Thompson estimator, which weights observed outcome by the probability of their observation [Narain, 1951, Horvitz and Thomp- son, 1952]. For adaptive designs, the standard Morvitz-Thompsee estimator is infeasible because
3

---

the marginal probability of treatment assignment Pr(Z, 1) depends on the unknown potential outcomes, For this reason, we investigate the adaptive Sorvitz-Thompsoo estimator, which uses the random (observed) treatment probabilities used at each iteration.
1
T Y
1L.
1] Pt
1[2 P -4--0) 0
T
where we recall that Pt = (Z,, yi,... 0e-1,Y-111 the treatment probability under the ex- perimental design given the observed data. When treatment assignments are non-adaptive and independent, then the adaptive Horvizz-Thompson Thompson estimator. Such adaptively weighted estimators have been proposed previously in the literature, e.g. [Bowden and Trippa, 2015, Hadad et al., 2021]. Below, we provide positivity conditions under which the adaptive estimator is unbiased, and derive its variance.
Thompson estimator the equivalent to the standard Horvitz-
Proposition 2.1. min Pt, 1 - P.) > 0 almost surely for all t E [T] then the adaptive Horvitz-
Thompson estimator is unbiased: E[f] =T.
Proposition 2.2. The variance of the adaptive Morvitz-Thomppe estimator is
T
T
T Var (f) = Σ
9o(1)
p.1 P.
vn()))
1) P
2.2 Asymptotic Framework and Assumptions
Following the convention of design-based inference, we analyze statistical methods within an asymp- totic framework [see e.g., Freedman, 2008, Lin, 2013, Sävje et al., 2021]. This provides a formal basis for reasoning about the performance of statistical methods as the sample size increases, giving meaning to conventional notions such as consistency and limiting distribution. Formally speaking. the which
asymptotic sequence of potential outcomes is a triangular array { (1), (0)) yields a sequence of estimands {Tr 7 and, together with an appropriately specified sequence of experimental design, sequence of estimators ( Analysis which applies to fixed T is said to be finite-sample (e.g. [F[rr] TT) whereas analysis which applies to the entire sequence is said to
be asymptotic (e.g. TT ीr F. 0). Although we use an asymptotic framework, we emphasize that the majority of our results are derived from finite-sample analysis and are merely interpreted through the lens of the asymptotic framework. We drop the subscript T for notational clarity.
The main regularity conditions we place the sequence of potential outcomes is below.
Assumption 1. There exist constants 0 < c C with < such that for all T in the sequence:
1. Bounded Moments: c ( DT (1))))) & E 1/4 & (0,1)
2. Bounded Correlation: p > c).
The upper moment bound in Assumption 1 stipulates that the potential outcomes cannot grow too large with the sample size, while the lower moment bound is type of non-degeneracy condition that prevents increasingly large fraction of the outcomes going to zero. These assumptions analogous to finite fourth moment and positive second moment assumptions in an i.i.d. setting. The bounded correlation assumption stipulates that the treatment and control outcomes are not exactly negatively correlated. In this paper, we do not assume that these constants C' and are known to the experimenter; however, if the experimenter can correctly specify such bounds (perhaps knowing priori the scaling of the outcomes) then some of the constant factors in our analysis can be improved. We emphasize here that Assumption places no assumption on the order in which units arrive in the experiment. In this sense, Assumption allows for arbitrary "non-stations "pon-stationarity" or "drift" in the potential outcomes over the experimental rounds. In the next section, these regularity assumptions will ensure that the Neyman variance converges to zero at the parametric rate.
3 Neyman Design: The Infeasible Non-Adaptive Ideal
The problem of Adaptive Neyman Allocation is to construct an adaptive experimental design that achieves nearly the same variance as an optimal non-adaptive experimental design, chosen with

---

knowledge of all potential outcomes. The optimal non non-adaptive design, referred to as the Neyman Design, is infeasible implement because depends on all potential outcomes, which are unknown to the experimenter at the design stage. The goal is that an adaptive experimental design- can select treatment assignment based on observed outcomes- can gather enough information to perform as well as the infeasible Neyman design.
In order define the optimal non-adaptive design, we begin by defining the class of Bernoulli designs. Informally, the class of Bernoulli designs consists of non-adaptive designs where each unit receives treatment Zj = 1 with probability p. independently of past treatment assignments and observations. Formally, this class is parameterized by a non-adaptive sampling probability e [0, such that for all [7], the treatment policy II, is constant function whose value is p. Using Proposition 2.2. we can derive the variance of the Bernoulli design with parameter E [0, 1] to be
1 V -oV==5(17 ((1))()))))) +(())) 1- (1-p -1) 2p5(1)
From the above. we can see that in order to minimize the variance of the Morvitz-Thompsee estimator under the Bernoulli design, we should set the sampling probability p so as balance the square of the second moments of treatment and control outcomes. The Neyman Design is the Bernoulli design which minimizes the variance of the Horvitz-Thompson estimator. The corresponding optimal probability p" and variance VN are referred to as the Neyman probability and Neyman variance, respectively. The following proposition derives these quantities in terms of the potential outcomes.
Proposition 3.1. The Neyman variance is T Vy 2(1 ()))())(()), which is achieved by the Neyman probability p* = (1 S(0)/S(1))
In order to quantify the reduction in variance achieved by the Neyman design, define the relative Neyman efficiency with respect to p E [0, 1J to be V./V,. Intuitively, this ratio is scale-free measure which eaptures the percent reduction variance of the sequential Horvitz-Thompee estimator under the Neyman design. Formally, the equation for the relative Neyman efficiency is given below:
VN 2(1 + p)
S(1) (1 (1-p) 5(0)
S(0)
P (1
+p - p)
5(1)
Consider the setting where outcomes are uncorrelated, and treatment outcomes are larger than control outcomes, e.g. - 0, S(1) 4- S()). In this case, the Neyman design is able achieve less than half the variance of the uniform Bernoulli design (with 1/2): we can plug in to 3 to see that in this setting, we have VV 0.47. The improvement is larger if the experimenter makes erroneous assumptions about the relative magnitudes of the treatment and control outcomes and attempts to set p accordingly: for example. if the experimenter had set p 1/4, incorrectly believing that S(1) & S(0). then the Neyman allocation results in a sixfold improvement in variance. Blackwell et al. [2022] derives qualitatively similar analysis of Neyman efficiency for stratified designs.
While the relative Neyman efficiency is helpful determining the variance reduction afforded by the (infeasible) optimal Bernoulli design, does address the main question: which adaptive experimental designs can guarantee similar variance reduction? In the next section, we propose performance metric which better addresses this question.
4 Adaptive Neyman Allocation: An Online Optimization Approach
4.1 Neyman Ratio and Neyman Regret: New Performance Measures
Let V be the variance of the adaptive experimental design. We introduce our first performance measure of a sequential experimental design for Adaptive Neyman Allocation.
Definition 1. The Neyman ratio of a sequential experimental design is Ky = (V VN)/VN.
The subscript T in Kr in included the reflect dependence of the number of rounds T. The Neyman ratio is motivated by the following relationship between the adaptive variance and the optimal Neyman variance:
V = (W2) (V) Vv = (1 (1+)T) VN
(1)
5

---

Equation (1) shows that the adaptive design can recover the Neyman variance if and only if the Neyman ratio KT can be made arbitrarily small. For this reason, we propose the Neyman ratio as a performance measure of sequential experimental design.
A natural question then becomes: how small can the Neyman ratio Kr be made the number of rounds I" increases? To answer this question, we view the problem of minimizing the Neyman ratio through the lens of online optimization. To this end, we must re-express the variance of the sequential experimental design. For each round & E [T], define the cost function ft : [0, 1J R as f((p) (1) (0)2/(1- ((1-/(11))))))p))) -p). Observe that by Proposition 2.2, the variance is given by T Var(f) = = E f((P)]. This reformulation of variance does not allow us to minimize variance directly, for the usual reason that the outcomes, and thus the cost functions ft, are not fully observed. On the other hand, our goal is only to show that the variance of the adaptive design is comparable the Neyman variance.
Definition 2. The Neyman regret of sequential experimental design is
T Σ sP)) pE
RT Σ ((PP))
min
Recall that P: is the random treatment probability at round t. The Neyman regret compares the accumulated costs fT()) incurred by the adaptive design to the accumulated costs incurred by the optimal Bernoulli design which has access to all potential outcomes. The Neyman regret is random because the sequence Pi.... Pr is random. The following theorem connects the expected Neyman regret to the Neyman ratio.
Theorem 4.1. Under Assumption 1, the Neyman ratio is within a constant factor of the 1/T expected Neyman regret: Ki O B[Rr]).
Theorem 4.1 demonstrates that the Neyman ratio can be made small by minimizing the expected Neyman regret in an online fashion. In particular, any sublinear bound on the expected Neyman regret ensures that the Neyman ratio goes to zero so that, in large samples, the adaptive design achieves the variance reduction of the optimal Neyman design. Any adaptive design which aims to achieve Neyman variance must, to some extent, minimize expected Neyman regret.
Fortunately, online optimization is a well-studied area with rich source of techniques from which we may draw inspiration. However, to the best of our knowledge, existing regret minimization algorithms are not well-suited to minimizing the Neyman regret. For example, the multi-arm bandit literature typically defines regret in terms of a finite number of actions that can be taken [Lattimore and Szepesvári, 2020] while Adaptive Neyman Allocation consists of a continuum of actions as Pt E [0, 1]. This means that algorithms like UCB [Auer et al., 2002a] and EXP3 [Auer et al., 2002b] are not appropriate for Adaptive Neyman Allocation. Our cost objectives fe and action space [o, 1] are both convex, so the problem of Adaptive Neyman Allocation is an instance of Online Convex Optimization (OCO) [Hazan, 2016). Even so, the problem of minimizing Neyman regret is not immediately amenable to existing algorithms, which typically requires assumptions on the cost functions such as bounded gradients or known Lipschitz parameters. In this setting, the cost functions have gradients which blow up at the boundary and Lipschitz parameters cannot be guaranteed as they rely on the unknown heterogeneous potential outcomes. For these reasons, we must design a new algorithm specifically tailored to Adaptive Neyman Allocation.
4.2 CLIP-OGD: A Variant of Online Stochastic Projected Gradient Descent
We present CLIP-OGD, which aims to minimize the Neyman regret and thus recover the Neyman variance in large samples. The algorithm is based on the online stochastic projected gradient descent principle, but with a twist: the projection set continuously grows over the rounds. At each round t, a new treatment probability P. is chosen by updating the previous sampling probability P:-1 in the negative (estimated) gradient direction of the previous cost, and then projecting to an interval [6, 1- 6.]. Initially, this projection interval contains only the point 1/2 and it grows the rounds increase, allowing for larger amounts of exploitation in later rounds.
The gradient estimator G2 is obtained in the following way: the gradient of fa at P is given as w()))
('(P.)
Only one outcome is observed, so we used the adaptive Horvitz-
P/
(1-P) P.)

---

Thompson principle using the conditional probability Pt to unbiasedly estimate the outcomes. CLIP- OGD is formally presented below as Algorithm 1, where the projection operator defined as Pa(x)) max min(ar, c)
Algorithm 1: C1.I--GD
Input: Step size and decay parameter Initialize Po + 1/2 and Go
for 1o.==...T7 do
Set projection parameter o, (1/2) 1/j
Compute new treatment probability Pt Po, (P-11 77 GG)
Sample treatment assignment Z, as 1 with probability P: and 0 with probability 1 - Pt
Observe outcome Y; 1 (1) + 1[2 (0))
Construct gradient estimator G: Y?
=1 112
P. [1-M]
end
Unlike the two-stage design of [Hahn et al., 2011, Blackwell et al., 2022], CLIP-OGD does not feature explicit explore-exploit stages, but rather performs both of these simultaneously. The trade-off implicitly controlled through parameters yj and a: smaller values of v) limit the amount of that sampling probabilities update and, likewise, larger values of prevent extreme probabilities in earlier stages. Because the gradient of the cost functions are inversely proportional to the treatment probabilities, limiting the extremeness of the treatment probabilities in this way ensures that the gradient estimates do not increase at a fast rate. By appropriately setting input parameters, CLIP-OGD achieves Õ(VT) expected Neyman regret, where the Ó(-) notation hides sub- sob--olynomial factors.
Theorem 4.2. Under Assumption I the parameter values 1/T and a / log()) ensure the expected Neyman regret of CLIP-GGD is asymptotically bounded: TR. [ & Ö(VT).
Theorem 4.2 answers, in the affirmative, that it is possible to construct an adaptive experimental design whose variance recovers that of the Neyman variance, in large samples. Note that the amount of exploration (as given by the parameters and a) should be increasing with I' in order to recover these regret bounds. In Appendix C, we show that CLIP-OGD somewhat robust to different values of the decay parameter, i.e. for any value a > 5, the expected regret will be sublinear. We also show that if the experimenter presumes to have correctly specified bounds C' and e appearing in Assumption 1, then the step size can be modified to improve the constant factors in the Neyman regret bound, which may lead to improved performance in moderate sample sizes. We conjecture that the minimax rate for expected Neyman regret O( O(VT), but proving this is beyond the scope of the current paper-we only remark that we do not know it to immediately follow from any existing regret lower bounds for OCO.
Inference in Large Samples
The proposed CLIP-OGD was constructed to ensure that the variance of the adaptive Horvitz- Thompson estimator quickly approaches the Neyman variance. this section, we provide confidence intervals for the average treatment effect which also enjoy reduced width compared to non-adaptive counterparts.
A necessary condition for variance estimation is that the variance itself cannot be going to zero too quickly. In design-based inference, is common to directly posit a so-called "non-superefffiiint" assumption that Var(f) = 9(1/7) [Aronow and Samii, 2017, Leung, 2022, Harshaw et al., 2022]. The non-superefficiency assumption may be seen as an additional regularity assumption the outcomes, e.g. preventing yı (1) (0) = 0 for all E [T]. In this work, a similar lower bound on the rate of the adaptive variance is obtained through a different, perhaps more transparent, assumption on the expected Neyman regret.
Assumption 2. The outcome sequence is not overly-fit to CLIP-OGD: - E[Rr] = o(T).
While we have shown that [[RT] Ö(VT), the Neyman regret could in principle be negative if the adaptive design achieves variance which is strictly smaller than the best Bernoulli design. While this
7

---

seems unlikely to happen for "typical" outcomes, it is not impossible. Assumption 2 rules out these edge-case settings. We suspect that Assumption would not be necessary an i.i.d. setting, but proving this seems beyond the scope of the current paper. As shown in the appendix, Assumptions 1 and imply that the adaptive variance achieves the parametric rate: Var(f) (117T).
5.1 Variance Estimation
In this section, we provide a variance estimator and show its stability in large samples. Rather than estimating the adaptive variance (which has no simple closed form), our approach is to estimate the Neyman variance directly. For an adaptive design achieving sublinear expected Neyman regret, these two quantities asymptotically equivalent. In this way, variance estimator may be appropriate not only for CLIP-OGD, but for any adaptive design achieving sublinear expected Neyman regret.
Recall that the Neyman variance is given by T VN 2(1 S) where is the outcome correlation, S₁ is the second moment of treatment outcomes and So the second moment of control outcomes. Unfortunately, the outcome correlation term is generally not estimable without strong assumptions in a design-based framework. Indeed, the difficulty is that terms like y (1(1) (0) are unobservable due to the fundamental problem of causal inference [Imbens and Rubin, 2015]. A common solution to the problem is to opt for a conservative estimate of the variance, which will ensure validity of resulting confidence intervals.
We propose estimating the following upper bound on the variance: T VB 4SoS,. This upper bound on the Neyman variance is tight (i.e. VB Vx) when outcome correlation satisfies 1. For example, this occurs when all individual treatment effects are zero, i.c. yr (1) (0) for all E [T]. Conversely, the upper bound will become looser for smaller values of the outcome correlation. In this sense, our bound resembles both the Neyman bound and the Aronow-Sami bound [Neyman, 1923, Aronow and Samii, 2013]. It may be possible to use the recent insights of Harshaw al. [2021] in order to construct variance bounds which are tight in other scenarios, but that is beyond the scope of the current paper. Our variance estimator is defined
1]
T
1 2
0]
VB +
yt
Σ
y6 Pt
Pt
1 1
which is essentially a plug-in Horvitz- Tryritz-Thoopoon estimator for the second moments. Theorem 5.1 shows the error of the normalized variance estimator converges parametric rate. Theorem 5.1. Under Assumptions and 2, and the parameters stated in Theorem 4.2, the ervor of the normalized variance estimator under CLIP-OGD is T VB T VB = (/-
5.2 Confidence Intervals
The variance estimator may be used to construct confidence intervals for the average treatment effect. This offers experimenters standard uncertainty quantification techniques when running CLIP-OGD. The following corollary shows that the resulting Chebyshev-type intervals are asymptotically valid.
Corollary 5.1. Under Assumptions I and 2, and parameters stated Theorem 4.2, Chebyshev-rype intervals are asymptotically valid: for all a 1]. lim inf Pr(r a VB) > --a
While these confidence intervals asymptotically valid under our regularity assumptions, they may be overly conservative in general. In particular, they will over cover when the Chebyshev tail bound is loose. We conjecture that the adaptive Horvitz-Thompson estimator under CLIP-OGD satisfies a Central Limit Theorem, which would imply asymptotic validity of the narrower Wald-type intervals where a 1/2 scaling is replaced with the corresponding normal quantile, 4b --1(1 (1-1000 a/2)). As discussed in Section 7, the adaptive estimator appears approximately normal in simulations. Until this formally shown, we recommend experimenters exhibit caution when using Wald-type confidence intervals for the adaptive Horvitz-Thompson estimator under CLIP-OGD.
6 Considering Alternative Designs
SisploreThhen-Come Two-stage adaptive designs have been proposed for the purpose of variance reduction [Hahn et al., 2011, Blackwell et al., 2022]. Due to its similarities algorithms in the bandits

---

literature, we call these types of designs Explore- Then-e Then-Commi Commit (ETC) [Lattimore and Szepesvári, 2020]. a high level, an Explore- ssplore-then--oee Mihee-Commii design runs the Bernoulli design with p = 1/2 for To & T iterations, uses the collected data to estimate p² by f and then runs the Bernoulli design with p = f for the remaining Ti than CLIP-OGD. and may be reasonable to apply in more restricted settings where changing the treatment probabilities is difficult or costly. However, we provide the following negative result which shows that they can suffer linear Neyman regret.
To iterations. These ETC designs are conceptually simpler
Proposition 6.1. For all explore phase lengths To satisfying To = (((T)) for some e > O, there exist class of potential outcomes sequences satisfying Assumption such that the Neyman regret under Explore-then- then--ommintttttttee is linear: RT = (T'(
The specifie class of potential outcomes referenced in Propposition 6.1 is constructed explicitly in Appendix E. 1. ETC designs suffer larger variance when the estimated 6 may be far from the true optimal probability p". In design-based setting, this happens when the units in the explore phase are not representative of the entire sequence. Formulating conditions under which Explore-then-Commee designs achieve low Neyman regret is beyond the scope of this paper, but the proof of Proposition 6. shows that additional regularity conditions on the order of the units will be required.
Multi Arm Bandit Algorithms Multi Arm Bandit (MAB) algorithms are often used for adaptive decision making settings, from online advertising to product development. The goal of MAB algorithms is to minimize the outcome regret, which measures the contrast between the overall value obtained from the actions relative to the value of the best action. The outcome regret is conventionally defined as R.g = ma Σ Dr (k) - Ei= Y, In certain contexts, minimizing outcome regret may be a more desirable goal than estimating a treatment effect to high precision. However, the following proposition illustrates that these two objectives are generally incompatible.
Proposition 6.2. Let A be an adaptive treatment algorithm achieving sublinear outcome regret, i.e. there exists q E 10,1) such that E. & O((T)) for all outcome sequences satisfying Assumption 1. Then, there exists a class of outcome sequences satisfying Assumption I on which A suffers super-linear Neyman regret, i.e. E[RT] > 22T2299)
Proposition 6.2 demonstrates that the outcome regret and the Neyman regret cannot generally be simultaneously minimized. In particular, sublinear outcome regret implies that the variance of the estimator must converge slower than the ((/TT) parametric rate. This result contributes to growing body of work which highlights trade-offss between various possible objectives in sequential decision making [Burtini et al., 2015]. It is beyond the scope of the current paper to determine how such trade-offs ought to be resolved, though Appendix F discusses ethical considerations.
7 Numerical Simulations
We evaluate the performance of CLIP-OGD and Explore-then-Commit (ETC) for the purpose of Adaptive Neyman Allocation on the field experiment of Groh and McKenzie [2016), which investigates the effect of macro-insurance on micro- micro-enterprises in post-revolution Egypt". The experimental units are 2,961 clients of Egypt's largest microfinance organization and the treatment was a novel insurance product. Several outcomes were recorded including whether the clients took on loans, introduced new product or service, and the amount invested in machinery or equipment following treatment. To allocate treatment, Groh and McKenzie [2016] use non-adaptive matched pair experimental design. Our goal here is not to provide a new analysis of this study, but rather to construct plausible experimental setting under which to evaluate adaptive experimental designs.
In our simulations, we focus on the numerical outcome "invested in machinery or equipment". The experimental data contains only observed outcomes, so we must impute the missing potential outcomes order to simulate the experiment. We impute outcomes using the model y (1) (0) =
T + Yt. where = 90, 000 and ..... ... 7r ~ .N( o²) are independent with o = 5, 000. This randomness is invoked only to impute potential outcomes. i.c. not re-sampled during each run of the experiment. In order to increase the sample size, we create larger population by repeating this processes times, which yields total of 14, 445 units after those with missing entries are removed. Units are shuffled to appear in an arbitrary order and outcomes are normalized to be in the range (0, 1].
A repository for reproducing simulations is: https: : /tt::://gttttt www.////ww//.ae.////c

---

Normalized Variance Var(f))
Norraliizdd Variance T- Var(f)
0.40
0.30
Bemoulli Neyman
Bemoulli
0.85
0.85
Neyman
0.80
ETC
0.80
ETC
0.75
ClipOGD
0.75
ClipOGD
0.70
0.70
0.45
0.55
0.00
0.60
0.55
0.55
5
2500
5000
7500
13000
12500
15000
17500
2300
5050
7500
10000
12500
15:00
17506
Number of Rounds (T)
Number of Rounds (T)
(a) Original dataset
(b) First 100 units have flipped potential outcomes
Figure Normalized Variance of Adaptive Estimator under Experimental Designs
Figure presents two plots illustrating how the variance of the adaptive HT estimator varies with different designs. The x axis contains the number of rounds T and the y axis contains the normalized variance T Var(f) under the designs. For each value of T, we take the population to be the first T units in the sequence. CLIP-OGD with To / so that the exploration phase grows with T. The variance under CLIP-OGD and ETC is estimated empirically from 50,000 runs of the experiment, while the variance under the Bernoulli and Neyman designs is computed exactly.
with the parameters recommended in Theorem 4.2 and ETC
In Figure 1a, we observe that CLIP-OGD requires about T 4, 000 samples achieve variance equal to Bernoulli, but eventually converges to the Neyman variance. As discussed in Section 4.2, may possible to improve the convergence rate by incorporating knowledge of the outcome moments in the design parameters, On the other hand, ETC remains comparable with Bernoulli even for small values of T, but remains far away from the Neyman design for large samples. Figure 1b, similar simulation is run, except that the potential outcomes of the first 100 units are swapped, so that the first units have negative individual treatment effects. While this produces little effect on the performance of CLIP-OGI it substantially worsens the performance of ETC, which relies the early outcomes to estimate an optimal treatment probability. particular, ETC performs worse than Bernoulli under this minor modification- in large samples-cormooorttin corroborating Proposition 6.1.
In the appendix, we evaluate the proposed confidence intervals, showing that CLIP-OGD enjoys intervals of reduced width. We show that normal based intervals cover at the nominal level and provide further evidence that the estimator asymptotically normal under CLIP-OGD, We run additional simulations investigate the sensitivity of the step size, and to demonstrate that additional baselines which were not designed for Neyman allocation indeed perform poorly.
8 Conclusion
In this paper, we have proposed the Neyman ratio and Neyman regret as a performance measure of experimental designs for the Adaptive Neyman Allocation problem. To this end, we proposed CLIP-OGD which achieves Ö(VT) expected Neyman regret under mild regularity conditions on the outcomes. This formally establishes-for the first time-the existence of adaptive experimental designs under which the variance of the effect estimator quickly approaches Finally, we have provided variance estimator which provides experimenters with uncertainty quantification methods when using CLIP-OGD. The main drawback bbck of our analysis is that it is most relevant for moderate and large sample sizes; in particular, our work does not properly address whether adaptive designs are always beneficial small samples.
Neyman variance.
There are several research directions which can improve relevance of this methodology to practice. First, establishing conditions under which a central limit theorem holds for CLIP-OGD will yield smaller and thus more desirable Wald-type confidence intervals. Second, investigations into batched treatment allocations and delayed observations of outcomes would allow practitioners more flexibility in their designs. Finally, investigating variants of Adaptive Neyman Allocation in the presence of interference [Aronow and Samii, 2017, Harshaw al., 2022] would allow for more realistic inference in complex settings, e.g. social network experiments and marketplace experiments.
10

---

Acknowledgments and Disclosure of Funding
We thank P.M. Aronow, Molly Offer- Westort, Alexander Rakhlin, Benjamin Recht, Fredrik Sävje, and Daniel Spielman for insightful discussions which helped shaped this work. Part of this work was done while Christopher Harshaw was visiting the Simons Institute for the Theory of Computing. Christopher Harshaw gratefully acknowledges support from Foundations of Data Science Institute (FODSI) NSF grant DMS2023505.
References
P.M. Aronow and Cyrus Samii. Conservative variance estimation for sampling designs with zero pairwise inclusion probabilities. Survey Methodology. 39(1):231 2013.
P.M. Aronow and Cyrus Samii. Estimating average causal effects under general interference. Annals of Applied Statistiss, 11(4:1912--1477, 2017.
Peter Auer, Nicolò Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47(2-3):235-256, may 2002a. ISSN 0885-6125, doi: 10.1023/A: 1013689704352.
Peter Auer, Nicolò Cesa-Bianche Yoav Freund, and Robert E. Schapire. The nonstochas- tic multiarmed bandit problem. SIAM Journal Computing, 32(():48-17) 77, 2002b. doi:
101137770097597019875.
AD Barker, CC Sigman, GJ Kelloff, NM Hylton, DA Berry, and LJ Esserman. I-spy 2: An adaptive breast cancer trial design in the setting of neoadjuvant chemotherapy. Clinical Pharmacology & Therapeutics, 86( (6(1))97-100, 2009,
doi: 10.1038/clpt.2009
Matthew Blackwell, Nicole E. Pashley and Dominic Valentino. Batch adaptive designs improve efficiency in social science experiments. Working paper, Harvard University, 2022. URL https: //www www.mmattbbackkwellll http:///w.......te///////////pte
adapttiieeaaiiieeeeeeeee pdf.
Jack Bowden and Lorenzo Trippa. Unbiased estimation for response adaptive clinical trials. Statistical methods in medical research, 26, 08 2015.
Giuseppe Burtini, Jason Loeppky, and Ramon Lawrence, A survey of online experiment design with the stochastic multi-armed bandit. arXiv preprint arXiv:1510.00757, 2015.
Yong Cai and Ahnaf Rafi. On the performance of the neyman allocation with small pilots. arXiv:2206.04643, 2022.
Jeffrey R. Fisele. The doubly adaptive biased coin design for sequential clinical trials. Journal of Statistical Planning and Inference, 38(2):249-261 261,, 1994. ISSN 0378-3758.
National Commission for the Protection of Human Subjects of Biomedical and Behavioral Research. Ethical principles and guidelines for the commission for the protection of human subjects of biomedical and behavioral research. Technical report, US Department of Health, Education, and Welfare, 1978.
The Belmont Report:
David A. Freedman. On regression adjustments to experimental data. Advances in Applied Mathe- matics, 40:180-193, 2008. doi: 10. 10.6616/j.aam. 2006. 12.003.
Matthew Groh and David McKenzie. Macroinsurance for microenterprises: A randomized experiment in post-revolution Egypt. Journal of Development Economies, 118:13 118:13-25, 2016. doi: 10.1016/j.
jdeveco.2015.08.00
Vitor Hadad, David A. Hirshberg, Ruohan Zhan, Stefan Wager, and Susan Athey. Confidence intervals for policy evaluation in adaptive experiments. PNAS, 118(15), 2021. doi: 10. 10.1073/pnas. 2014602118.
Jinyong Hahn, Keisuke Hirano, and Dean Karlan. Adaptive experimental design using the propensity score. Journal of Business & Economic Statistics, 29(1)966108, 2011.

---

Dae Woong Ham, lavor Bojinov, Michael Lindon, and Martin Tingley. Design- based confidence sequences for anytime-valid causal inference. arXiv:2210.08639, 2022.
Christopher Harshaw, Joel A. Middleton, and Fredrik Sävje. Optimized variance estimation under interference and complex experimental designs. 1rXiv:2112.017000 2021.
Christopher Harshaw, Fredrik Sävje, and Yitan Wang. A design-based riesz representation framework for randomized experiments. arXiv:2210.08698, 2022.
Lakhbir S. Hayre and Bruce W. Turnbull. Estimation of the odds ratio the two-armed bandit problem. Biometrika, 68(3):661-668 1981.
Elad Hazan. Introduction to online convex optimization. Foundations and Trends@ in Optimization, 2(3 (3-4):157-325, 2016. ISSN 2167-3888.
D. G. Horvitz and D. Thompson. A generalization sampling without replacement from finite universe. Journal of the American Statistical Association, (7(26)):633-685 1952. doi:
10.1080/01621450 110000162149.1110. 1952. 10483444
Steven R. Howard, Aaditya Ramdas, Jon McAuliffe, and Jasjeet Sekhon. Time-uniform, non- parametric, nonasymptotic confidence sequences. The Annals of Statistics, 49(2):1055 1080, 2021.
Feifang Hu and William F. Rosenberger. Optimality, variability, power: Evaluating response- adaptive randomization procedures for treatment comparisons. Journal of the American Statistical Association, 98(463):671-678 2003.
Guido W Imbens and Donald B Rubin. Causal inference in statistics, social, and biomedical sciences. Cambridge University Press, 2015.
Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University Press, 2020.
Michael P. Leung. Causal inference under approximate neighborhood interference. Econometrica. 90(1):267-29) 293, 2022.
Winston Lin. Agnostic notes regression adjustments to experimental data: Reexamining Freed- man's critique. Annals of Applied Statistics, 7(1):295-318, 2013.
R. Narain. On sampling without replacement with varying probabilities. Journal of the Indian Society of Agricultural Statistics, 3:169- 175, 1951.
Jerzy Neyman. On the application of probability theory to agricultural experiments. Essay on principles. Section Statistical Science, 5(4):465 1923. Reprinted 1990.
Jerzy Neyman. On the two different aspects of the representative method: The method of stratified sampling and the method of purposive selection. Journal of the Royal Statistical Society, 97(4): 358-625, 1934. ISSN 09528385.
Molly Offer- Westort, Alexander Coppock, and Donald Green. Adaptive experimental design: Prospects and applications in political science. American Journal of Political Science, 65(4): 826-844, 2021.
Herbert Robbins. Some aspects of the sequential design of experiments. Bulletin of the American Mathematical Society, 58(5):527 535, 1952.
W Rosenberger, N Stallard, Anastasia Ivanova, C Harper, and M Ricks. Optimal adaptive designs for binary response trials. Biometrics, 57:909-13, 10 2001.
Donald B. Rubin. Comment: Randomization analysis of experimental data. Journal of the American Statistical Association, 75(371):591, 1980.
Fredrik Sävje, M. Aronow, and Michael G. Hudgens. Average treatment effects in the presence of unknown interference. Annals of Statistics, 49(2):673-701, 2021.
12

---

Eric M. Schwartz, Eric T. Bradlow, and Peter S. Fader. Customer acquisition via display advertising using multi-armed bandit experiments. Marketing Science, 36(4):500-522, 2017.
H. Solomon and S. Zacks. Optimal design of sampling from finite populations: critical review and indication of new research areas. Journal of the American Statistical Association, 65(330): 633-677, 1970.
A. Wald. Sequential Tests of Statistical Hypotheses. The Annals of Mathematical Statistics, 16(2): 117-186, 1945.
Yanxun Xu, Lorenzo Trippa, Peter Müller, and Yuan Ji. Subgroup-based adaptive (suba) designs for multi-arm biomarker trials. Statistics in Biosciences, 8, 02 2014.
Kelly Zhang, Lucas Janson, and Susan Murphy, Inference for batched bandits. In Advances in Neural Information Processing Systems, volume 33, pages 0818-9829. Curran Associates, Inc., 2020.
Kelly Zhang, Lucas Janson, and Susan Murphy. Statistical inference with m-estimators on adaptively collected data. In Advances in Neural Information Processing Systems, volume 34, pages 7460= 7471. Curran Associates, Inc., 2021.
Lanju Zhang and William F. Rosenberger. Response-adaptive randomization for clinical trials with continuous outcomes. Biometrics, 62(2):562-569, 2006.
13

---

Appendix
Table of Contents
Additional Simulation Results
15
A.1 Confidence Intervals
15
A.2 Sensitivity to Step Size
15
A.3 Alternative Designs
16
General Analysis of Adaptive Neyman Allocation
17
B.1 Analysis of Adaptive Horvitz-Thompson Estimator (Propositions 2.1 and 2.2)
................................
17
B.2 Derivation of the Neyman Design (Proposition 3.1)
18
B.3 Equivalence of Neyman Ratio and Neyman Regret (Theorem 4.1)
19
Analysis of Neyman Regret for CLIP-OGD
19
C.1 Proof of Theorem 4.2
19
C.2 Selecting Parameters When Moment Bounds are Known
24
Analysis for Inference in Large Samples
25
D.I Conservative Variance Estimator (Theorem 5.1)
................................
25
D.2 Valid Confidence Intervals (Corollary 5.1)
30
Analysis of Alternative Designs
30
Analysis Explore-then- Cohmmt (Proposition 6.1)
30
E.2 Analysis Designs Outcome Regret (Proposition 6.2)
F Ethical Considerations
34
14

---

A Additional Simulation Results
In this section, we present additional simulation results on the Groh and McKenzie [2016] data. We refer to Section 7 for a review of the experimental set-up. this section, we focus on the full dataset where 14, 445. Simulations were run on 2019 MacBook Pro with 2.4 GHz Quad-Core Intel Core i5 and 16 GB LPDDR3 RAM.
A.1 Confidence Intervals
Chebyshev Width
Chebyshev Coverage
Normal Width
Normal Coverage
Bernoulli (p 1/2)
0.0541
100%
0.0237
95.21%
CLIP-OGD
0.0507
99.99%
0.0222
95.22%
Table 1: 95% Confidence Intervals for Bernoulli and CLIP-OGD
Table presents the Chebyshev-based and Normal-based intervals for the Bernuulii design (p 1/2) and CLIP-OGD We see that while Chebyshev over-covers, the normal-based confidence intervals cover at the nominal level with reduced width for both designs. The relative Neyman efficiency on this dataset is somewhat close to 1, so that the reduction of the width of the confidence intervals afforded by CLIP-GG is present, though modest. The coverage of the normal-based confidence intervals provides further evidence supporting conjecture that the adaptive Horvitz-Thompsie estimator is asymptotically normal under CLIP-OGI
3500
3000
2500
Counts
2000
1500
1000
500
0
-4
-2
Studentized Adaptive HT Values
Figure 2: Histogram of Studentized Adaptive Horvitz-Thompson estimator under CLIP-OGD (T 14, 445)
Figure plots the histogram of the studentized adaptive Horvitz-Thompson estimator under CLIP-OGD. By studentized, we mean that the histogram is plotting the draws the random variable
2
V Var(f))
We estimate the standard deviation empirically from 50,000 runs of the experiment. The estimator said to be
asymptotically normal if 7 - (O, 1). Figure provides evidence that asymptotic normality is likely to hold in this setting. Formally establishing asymptotic normality is beyond the scope of the current paper as it would involve very different analytic techniques than those used to establish sublinear Neyman regret.
A.2 Sensitivity to Step Size
In this section, explore through simulations how the performance of CLIP-OGD depends the step size.
15

---

Normalized Variance T. Var(i)
Bernoulli
1.0
Neyman
ClipOGD
0.9
Clip-OGD (0.25)
Clip-OGD (0.5)
0.8
Clip-OGD (2.0)
0.7
Clip-OGD (4.0)
0.6
0
2500
5000
7500
10000
12500
15000
17500
Number of Rounds (T)
Figure 3: Comparing Step Sizes:
In Figure 3, we re-create Figure 1a in the main paper but we have added instances of CLIP-OGD with different step sizes the forms 7 = c/v'T for e E (0.25, 0.5, 1.0, 2.0, 4.0). We find that smaller step sizes improve convergence rates, effectively removing the "overhead of adaptivity" in this example. However, because the randomized experiment can only be run once, experimenters will typically not be able to try many step sizes. While it remains an open question about how to select step size which best mitigates the "overhead of adaptivity", our recommendation of 1/vT still maintains good convergence properties.
A.3 Alternative Designs
In this section, we conduct additional experiments to compare the results CLIP-OGD to alternative experimental designs which are not made for Neyman allocation. Indeed, we find that the alternative designs incur high variance, relative to CLIP-OGD and the Neyman variance.
Bernoulli
Bernoull
Neyman
0.025
Neyman
Variance Var(ft
Variance Var(z)
ETC
ETC
0.020
DBCD
DBCD
ClipOGD
0.015
ClipOGD
0.010
0.000
5000
7500
10000
12500
15000
17500
10000 Number of Rounds (7)
15000
Number of Rounds (T)
DBCD only
(b) DBCD EXP3
Figure 4: Comparison of (Unnormalized) Variances:
In Figure 4, we plot the variance of the adaptive designs on an unnormalized scale. We include "Doubly Biased Coin Design" proposed by Eisele [1994] as DBCD in Fig 4a and both DBCD and EXP3 in Fig 4b. We find that both DBCD and EXP3 suffer from higher variance. This because they are not designed for Adaptive Neyman Allocation as defined this paper: DBCD targets different allocation rule and EXP3 minimizes outcome regret so that essentially only one arm is pulled. Both of these algorithms the sampling probabilities P; get too close to the boundary of [0, 1]. resulting in excessively large variance.
16

---

B General Analysis of Adaptive Neyman Allocation
In this section, we provide general analysis relevant for the problem of Adaptive Neyman Allocation. In Section B.1, we analyze the adaptive Horvizz-Thompson estimator. In Section B.2, we derive the optimal non-adaptive Neyman design terms of the potential outcomes. In Section B.3, we show the equivalence of Neyman ratio and expected Neyman regret. For completeness, all propositions re-appear in the appendix.
B.1 Analysis of Adaptive Horvite-Thompson Estimator (Propositions 2.1 and 2.2)
Throughout these proofs, we break up the adaptive Horvizz-Thompson estimator into the sum of individual estimators. For each e [T'. define
== = Y, 11 1] 1[2 = =0] Pt
1 - Pt
so that the sequential Horvitz- treatment effect is the average of individual treatment effects, i.e. (1/T) Ei=
Horvitz-Thompsor Thompson estimator is equal to f = (1/T) Σ Fr. This mirrors how the average
We begin by proving Proposition 2.1, which establishes the unbiasedness of the adaptive Horvitz- -hrriion estimator, subject to positivity condition.
Proposition 2.1. If min Pt. 1 - PP} > 0 almost surely for all e [T] then the adaptive Corvitz-Thompson estimator is unbiased: R[+] T.
Proof. Observe that by linearity of expectation, we can break the expectation of the adaptive Horvitz-Thompson estimator as
T T Σ Blid
[lf]
Thus, it suffices to show that the individual effect estimators are unbiased: [e condition holds, then we have that the conditional expectation may be computed as
т₁. Observe that if the positivity
11: = 1]
1[: = 0 F
E F.1 = Y
Pt
1 1 P-
(b((1)
(1- Pt) ( y/1 (0((0)
P.
Pt
P.
= (1) - (0)
Tt
The result follows by iterated expectation, E[ = E
Fill
0
Next, we prove Proposition 2.2, which derives the variance of the adaptive Horvitz-Thompson estimator. Proposition 2.2. The variance of the adaptive
estimator is
1
T Var(f)
T (1)
E
vi((0)
P.
1 P
1-
T
Proof. We begin by decomposing the variance of the adaptive Horvitz-Thompson estimator
T Σ
Var(f) Var
-
Σ
Cov fx)
T2
1=1==1
We now aim to compute each of these individual covariance terms. Before continuing, observe that, by construction,
the individual effect estimators are conditionally unbiased E[ F.] = Tt. It follows by iterated expectation that the individual effect estimators are unbiased (unconditionalll)), i.c. E ft] = Tę. Suppose that > t. In this case, the covariance between the individual estimators equal zero as,
Cov(fr, F.)
E[ B[A [[
= Bl Blf FJll - TTT
To Bl TET.
17

---

T,7 TTe
Now let us compute the variance of an individual effect estimator. Observe that the variance may be decomposed as Var(fi) = B[+?] - B[
Because the individual estimator is unbiased, have that E[+,] T². Let analyze the first term.
E
E
E
Fi]]
(iterated expectation)
1[
1[ 0]
E
E
Y?
Fr
Pf
Pt)
1
E
(1)²
+ ye(0)²
Pt
1- P
1
= (1)2 E
+ (0)
P
P.
Thus, this establishes that the variance of an individual estimator is equal to
Var(f:) = (c(1))
EE
+ (0)
P.
P
Combining terms, we have that the variance of the adaptive Horvitz. Corvit--Thompson estimator is
T
T Var(f)
Cov(fz, f.)
T
T
Var(ft)
T
(c(1)²
+ (0)
T
P.
Pr
T
B.2 Derivation the Neyman Design (Proposition 3.1)
In this section, we prove Proposition 3.1 which derives the (infeasible) non-adaptive Neyman design in terms of the Neyman probability y* and corresponding Neyman variance Vx. We also show that, under Assumption the Neyman variance achieves the parametric rate.
Proposition 3.1. The Neyman variance is T Vy 2(1 + ())()))(()), which is achieved by the Neyman probability pa (1 5(0)/5(1))
Proof. Using Proposition 2.2, we have that the variance of the (non-adaptive) Bernoulli design with probability p (0, 1) is equal
T T. - $(1) + ((0)2 1 11-p
-) 1
2p5(1))((0)
Thus, the optimal Neyman design obtained by the px which minimizes the above. The first order condition stipulates that
T 1/ p-px | = 0 -S(1)
+ +(()) -
(10))(11)))) )1-
0p
which solved by p* (1+ S(0)/S(1)) -1 Substituting this pd back into the variance yields the Neyman variance:
T. Vy, 5(1)² (1 1) +(0)) 1 p* -1) 2pS(1)S(())
p*
=(()) 5(0)
+ S 5(1) S(0) 2pS(())S(0)
5(1)
2(1 + S))S()
Next, show that under Assumption 1, the Neyman variance achieves the parametric rate.
18

---

Proposition B.1. Under Assumption 1, the Neyman variance achieves the parametric rate: VN = ((1/T).
Proof. Proposition 3.1, derives the Neyman variance: T VVV = 2[1 2(1+))
We begin by showing that the Neyman variance is asymptotically bounded from below. Moreover, Assumption stipulates that there exists a constant > 0 which lower bounds the second moments as S > с and S(0) > and the correlation as (1 + p) c. Thus, the normalized Neyman variance is bounded below T VN 2 2ca.
Next, we show that the Neyman variance asymptotically bounded from above at the same rate. Assumption stipulates that there exists constant C > 0 which upper bounds the second moments as S(1) & C and S(0) & C.
The correlation is bounded between p E I-1, 1] so that (1 + p) & These bounds together yield that the normalized
Neyman variance is bounded above as T VN < 4C².
Together, these bounds establish that, under Assumption we have that VN = ((/T))
B.3 Equivalence of Neyman Ratio and Neyman Regret (Theorem 4.1)
In this section, we prove Theorem 4.1, which demonstrates the equivalence between the Neyman Ratio and the expected Neyman regret.
Theorem 4.1. Under Assumption the Neyman ratio is within a constant factor of the 1/T--scaled expected Neyman regret: KT ( RT).
Proof. Recall that the Neyman ratio is defined as
V-
T V
T
VN
KT
VN
T
VN
where the second equality follows by multiplying the numerator and the denominator by T. Observe that by Proposi- tion 2.2, the numerator is given by
1 T
T.
T V~
=
T
Σ
(1)
E
P. + (0) E
1 P.
1
min
+ v=(0))=
p..
T
1/
1-
=
f((PP))
min
=
1
Σ
T
fe(x*)
p =
T
[-1
T Σ s((p*)
+
E
Se(P.)
min p*e
1
E[Rr]
E
T
Proposition B.1 shows that under Assumption 1, T Vi = (1) so that the denominator asymptotically constant. Thus, we have that O [[Rr)).
C Analysis of Neyman Regret for CLIP-OGD
In this section, we will prove Theorem 4.2, which establish that CLIP-OGD achieves O OlvTlogT)) expected Neyman regret under our assumptions on the potential outcomes. While the main paper used capital letters Ps and G, to signify that the treatment probability and gradient estimator were random variables, we use lower case letters and in the appendix for the purposes of more aesthetically appealing proofs. Throughout the analysis, we define A, [ōc, 8c] and a = 1 + C/c for notational convenience.
C.1 Proof of Theorem 4.2
The first lemma bound on the distance of treatment probability P to the optimal pa in terms of the previous treatment probability, gradient estimate, and whether the projection interval contains the optimal p*.
19

---

Lemma C.1. For each iteration t E [T].
Pt+1 p=1 & (p: - 79)) p*1 5,1 $ A.]
Proof. pf E Ar, then the statement holds by Pythagorean theorem. Otherwise, note that the most that the projection operation onto AS can move a point is exactly 6z. Therefore, the distance between Ps, (Pr 7g9e) and p" is at most o larger than that between Pt- 799 and p*.
Next, we show that Assumption 1 implies that the optimal Neyman probability lies within an interval bounded away from zero.
Lemma C.2. Under Assumption p* 1 1 d. where a 1 C/c> 2.
Proof. As shown previously, the optimal Neyman probability is equal to
Σ - (0)2
p*
1+
- (1)2
Recall that Assumption places the following moment conditions on the potential outcomes:
T
((11)))
1/2
< and c
T Σ
T
2(1)))
1/2
EC.
This bounds pa by
(1+ < pt & (1+ (
The result follows by using the definition of 1 + C/c to deduce that (1/a) (1 + c/c)-1 and (1 1/a) (1 + c/C)-1
The next lemma guarantees that after a fixed number of iterations, the projection interval will contain the Neyman optimal p*.
Lemma C.3. We have that p² E for all > (a/2)a.
Proof. Lemma C.2 guarantees that p* [1/a, 1 - 1/a], where 1 c/c. Thus, p* E A, if & & 1/a. Using the definition of 6, and rearranging terms, we have that
8, $ 1/a (1/2)-110 1/a <> L> (a/2)
The next lemma bounds the expected difference between the cost objective fa evaluated at and the cost objective fz evaluated at the Neyman optimal probability p*. Lemma C.4. For each iteration i e [T]. we have the bound
2R (ilm)) - se(p*)] &
R
(p) 2T)
-E[ 1ali--p"y -*)
+ B[ + 41 1
a 2
de
+
5e E
[0:])
|0.1
7
2
Proof.
Fix an iteration t [T]. By Lemma C.I, and using the triangle inequality, we have that
(pt+1 - 2 < (Kpp n991) + $ A.1)
((pr ngt)) p²)² 5,1 A 2p (gt1) 1- 10,111[p" $ A.l
((p: p² ngg1)* 1pp A.] 63 + 25. 1(p. --) 1991)
((p: - p*) ng:) 28, 1 1p Dc] 6e + lpt p²1 71.91
Because Pt [8,, 8,7. we have that 1pt - pa1 b, so that
& ((p: - p** - ng)) 26, 4.) + ri9el)
20

---

(pr -x*)2 + n² 2ngdli - -p") + 4n 11x² & Arl -h
+
"7
Rearranging terms yields that
PP - -P*) & (Do p²1 (pe+1 (pt+1-p*)) -2*)
+ +r" + 4n 11p² $ A
6
- (9.
+
7)
2
Dividing both sides by the step size 27 yields
9t (pt p²) &
2n | (p=- - p²)² (pt+1- - pp)0|+
" o2 + 21 $ A.]
de
+
6t
ggl]
2
77
2
Using convexity of fa, adding and subtracting terms, and using the above, have that fe(pt) Se(1*) & (Vse(Pt), p²>
(convexity)
= (gt, Pt p²) + <V f((p)) - 9t.Pr - -p">
(adding, subtracting)
< 2n
- -p*)² (Pt p² p²)²= (pt+1-p*)+
7 9 + 21[p" (
8 1lil)
(above)
2
+ (Vi{(p)) Pt --) p*)
By construction, we have that the gradient estimator is unbiased conditioned on Dz, i.c. E[g D.] V.t(P.). Thus, by iterated expectation have that the gradient estimator is unbiased, i.e.
[+ - 9.] = B[E[VS+(px) - -9t D:]] = 0
Thus, taking expectations of both sides and applying Lemma C.3 yields
E fp() fc(p*)
E (pt -p0}²
E (pe+1 - p+)²
+ 1 +
4.
11p*
$ Ail
6
+
8e E
(1111)) 1)
2
8
d E [ssl)
R (pr - p 18)2
-aap11---pp - F of
<
+
The following lemma derives bounds on the first and second (raw) moments the gradient estimator at each iteration. Lemma C.5. For each t [T], the gradient estimates have bounded first and second moments:
E
g
25/5/a
(He(1)² v.)
2// (c)))
Proof. We begin by handling the ge expectation is most
term.
By definition of gradient estimator, we have that the conditional
(2a(1)2 3
(0)2 pz)
El
Di]
Pt
+ (1-p))
p.) (
pt
(1)
(0)
+ (1 p5)
By definition of the algorithm, we have that pt E 18,, 1 - 5.] at iteration t. Thus, we may invoke the bound:
< 6, (1)² + vo(1)*)
= [11/2) 1/07-5 (u((1)*+u(11))
= 25/5/a (1)² (1)1
and the desired bound [[g]] follows from applying the law of iterated expectation.
21

---

The bound on the |g. term follows in a similar way. By definition of the gradient estimator, we have that the conditional expectation is at most
(0) (r)1 (o(
(e)3)
Blggel D.] Pt.
+1 (p))
Pi
(1-pa)3
pi (1 - pc)
8,2 (v.(1)) + v1())
[(1/2)t-1/a1) (vi(1)²+ vi(1)²)
2//2//0 (Ie (1)) (1))))++111)))))))
and the desired bound on E[[g.] ] follows from applying the law of iterated expectation.
The following proposition bounds the expected Neyman regret for general settings of the projection parameter a.
Proposition C.1. Suppose Assumption holds. Then, for any choice of projection parameter or > 2 (possibly depending on T) and for the step size V Thisaa a finite-saamp bound on the expected Neyman regret incurred by CLIP-OGD
is
B [RT] &
eoT114/aa + 22 2+a/2 2ea/2 VeaT.
Proof. By Lemma C.4, we have that the regret is at most
T
2
RT =
2E
f((pt) - f(((*)
T
T +
E
(p: ---)²
B
- -pt+11
B[g2]
Σ
T'
[ (2) 9
8c (h + T ((11)))
Using a telescoping argument, have that the first term is bounded by
E (pt - pp pp)] -B (P --)p
< 1
-
B
Using Lemma C.5 and Assumption the sum in the second term may be bounded as
T
T
22,5/0 23/ (vn(1)) (x())))
(Lemma C.5)
T
T
< 2575/a
Σ
(n(11)
Σ (0))
< 3// (20"T)
(Assumption 1)
1
Next, we deal with the third term by breaking it up into two more terms. Define 1 broken into two terms:
[(a/2)a]. The third term can be
Σ E
c dz
4
Σ 8
+
5 EE [gg]]]
7
-=1
1=1
The first of these two terms can be bounded in the following way. Using that a > 2 we have that
6
(1/2)-11/a 1/a
22

---

(1/2) 1+ +
Σ
1//
2-2
p
(1/2)
1/0 do
-==1
(1/2)
1+ a-
((t" - 11 -1)
(t* 1)(1-1/a)
< (a/2)a(1-1/a)
(a/2)a=11
The second term can be bounded using Lemma C.5 as follows:
#
Σ
8 [[9:1]
(1/2)t
1//22/2/a (1/2)t-//n228
(v) +1)22+++(0000 (x)))))
(Lemma C.5)
2a (vx(1) + (e))))
*
< 2(
Σ
1/2
1/2
(())))
E (0)+) 1/2
where the last inequality follows from Bauchy-Schware By extending the sum involving the outcomes all units, we obtain an upper bound on which we can apply the bounded moment assumption:
2/ 1/2
12
1/2 (,(1)))))
(
T
()()))) 1/2
*
< 2
Σ
22/a) 1/2
1
(Assumption 1)
What remains this step is to bound the first term above. By replacing each of the in the sum with t", we obtain the following upper bound:
2((t 1) 1/2
2(C*1))/2
(1+a/2) 1/2
02
2
Using the above work, have that the overall regret is bounded
a (a-1)
(1+a/2)
2 Rr <
+ C2 +
(
+ 22
T1/2
2
2
(1 + 4 1
(a-
+ 7,20
C/T11 23 a (1ta/2)
71/2
Next, we separate the constant a from the projection parameter a. To this end, we use the inequality y" & cl v. for all y IR and > 0, to obtain
(
(a-1) )0))
e c1o022
= c and
a (1+a/2) (
10/2 = = _2ta/2_0??
where we have used that a > 2. Substituting these back into the above, we have that the regret bound is Substituting this quantities into the above, we have that the regret bound is
RE & ( 20 + 1/2 + 220
23

---

23 20 + + 2 2
By setting V 71+3/0 to minimize the bound above, we have that the expected Neyman regret is bounded as = e28 2 + 2 C6 eaT1+5/a + 22 2+0/2 VerT
V
where have used that and the result follows by dividing both sides by 2.
Proposition C.I demonstrates that many different values of a will guarantee sublinear expected Neyman regret. For example, setting to be a constant satisfying 5 will ensure sublinear expected Neyman regret. However, by mning a according to the analysis above, we can achieve (( log(()) expected Neyman regret, as demonstrated by Theorem 4.2.
Theorem 4.2*. Under Assumption I the parameter values rj = VIT and a = /5log(T) ensure the expected
Neyman regrei of CLIP-OGD is bounded as
B[R]] & (2 + - 22 VT expl explx (5log(T)
which implies that B[RT] & Õ(VT).
Proof. Observe that for / log), we have that the step size posited in Proposition C.I (i.e. 1= V T1+3/0 is
equal to v V/T. Thus, by rearranging terms and using the result Proposition C.I, we have that expected Neyman regret is bounded as
B < (22 2 eaT1+5/a + 2
20022 T V VenT5 + 24 VT Vc
122
The difficulty now to find which setting of a will make this bound smallest. Observe that the real tension is in the first term and we can re-write the relevant part of this term as
+ (5/a) Teaaa = exp((x + l/g( | = (5/a))
1/2
(o/a) log(T)) 1/2
To minimize this term, we select = (Tlog(T) which results in
VearT5 = exp( (log)))))(T))
Likewise, this choice of a results in vea & e =x==eppvv (log(T)). Putting this together yields the desired finite sample regret bound:
B[Rr] & (22ea/2 + c* + 22 VT exp( v 5log(T))
The result follows by observing that the terms inside the parenthesis are constant by Assumption I and the function exp( /5 log()) subpolynomial.
C.2 Selecting Parameters When Moment Bounds are Known
We briefly remark on how to select the step size parameter when the experimenter can correctly specify the constants C used in the Assumption The proof of Proposition C.1 shows that for general parameters, the Neyman regret may be bounded as
2//21/22 & 2/2 + n C'T114/// +2
E
[
17
To optimize the step size with respect to these constants, one would choose a v (og((T) and
(1(10)))
7
2v202
VT
where we have used that + C/c. When these moment bounds are correctly specified, this choice of step size will likely yield improved convergence rates, as our bound on the Neyman regret will have factor of C2 rather than CA.
24

---

D Analysis for Inference in Large Samples
In this section, we provide the necessary statistical tools for constructing asymptotically valid confidence intervals. This can be done in two main steps. First, in Section D.1 we construct conservative variance estimator which show is consistent in probability. Then, in Section D.2, we show that the resulting Chebyshev- intervals are asymptotically valid.
While the main paper used capital letters P: and G, to signify that the treatment probability and gradient estimator were random variables, we use lower case letters pt and St in the appendix for the purposes of more aesthetically appealing proofs. Throughout the analysis, we use the parameter settings are recommended the main paper. However, we suspect that many of our results will go through for the class of parameters 1)
VI/T and a v log(T) which
T-43 and a which appear in Proposition C.I.
The following lemma shows that under Assumptions 1 and 2, the variance of the adaptive Horvitz-Thompson estimator under CLIP-OGD achieves the parametric rate.
Lemma D.1. Assumptions I and 2, the variance of the adaptive Horvita-Thompson estimator under CLIP-OGD achieves the parametric rate: Var(f) = (1/T).
Proof. Theorem 4.1 shows that under Assumption I, they Neyman ratio order equivalent to the 1/T--called expected Neyman regret, i.e. (((1 (1) E[Rr)). Theorem 4.2 shows that under these assumptions, CLIP-OGD achieves sublinear expected Neyman regret E o(T)) which implies that lim sup KrT & Likewise. Assumption 2 states that the negative expected Neyman regret is sublinear, - [[ = o(T), which implies that lim inf or ? 0. Thus, we have that the Neyman ratio converges to zero, c.g. lim KT
By recalling the definition of the Neyman ratio, we have that
VN
T V.V T
= lim KT T-
lim T-
=
lim T-
VN
T V/
Proposition B.1 demonstrates that T V/N = (1). Together with the above, this implies that T V = =(1).
The following lemma shows that under the recommended parameter settings, the (random) treatment probabilities are bounded away from zero and one.
Lemma D.2. When a / log(()) we have that for all iterations E [T]. the inverse of projection parameter is bounded:
8, 2cxp( (og((//))( =())
Proof.
uniform upper bound on the inverse of the projection parameters
(1/2)T-1/a 1/a 2T 2exp( 1 log(TT) -2expyy log(T"/5))
1
8, δT
To complete the proof, observe that the function h(T)) exple / Iog(T") is subpolynomial, so that we can write it as (().
D.1 Conservative Variance Estimator (Theorem 5.1)
In this section, we prove Theorem 5.1 which establishes that the normalized variance estimator is converges in probability to the normalized variance upper bound at (T(T21)2) rate. Before continuing, let us review the relevant quantities. Recall that the Neyman variance and the corresponding upper bound are given by
T VN 2(1 ()) and T. VB 45(1)S(0)
where the second moments 1(1 and S(0) are defined
T De (0)²
S(1)² = Σ (1)2 and S(0)²
7
25

---

Our variance estimator is defined as
T Σ yc 1[2 and A(0)
T T Σ yr (0)
1[ 1 Pt
T' VB - A(1) A()) where A(1) = T
The random variables A(1) and A(0) are unbiased estimates of S(1)² and S(0)² which are based on the Horvitz- Thompson principle. However, the fact that the estimators A(1) and A(0) are not independent and the square root is introduced means that the variance estimator VB is not an unbiased estimator for the variance bound VB. Even so, we will show that the variance estimator is consistent for the variance bound. For aesthetic considerations, define A(1) S(1)² and A(0) S(0) so that A(1) is an estimator for A(1) and A(0) an estimator for A(0).
Our general approach will follow in two steps. First, by bounding its bias and variance, we will show that A(1) A(0) A(1) converges (p(T-1/3) Next, by appealing to quantitative Continuous Mapping Theorem, will argue that the error V A(1) A(O) A(D) converges at the same rate, By definition, this is exactly the error of the normalized variance estimator to the normalized variance bound, i.e. T VB T VB.
Before continuing, let us define new auxiliary random variables. For each / E [T]. we define the variables and da
1[2
1] and q:
1 1/ 0]
Pt Below are basic facts about these auxiliary random variables. Lemma D.3. The auxiliary random variables satisfy the following properties:
1 Pt
1. B[rag=] 1[t s}.
2. Bir DJ] < 2/4 and Elgi Del & J.-
The covariance Cov(riqs,T14p behave in the following ways:
Cov(req; regk) = 0
ift = 8 or ift and l + k and (1, {L. Ø
Cov(regs; requ) 0
Cov(riqu, reqh) = -1
if t * and + and ( = k: or s = i
1
Cov(rege, < 6,
if and + k and t and # k:
1
(ov(rege,reuu) < 0,4
if * and + k and t & and
Teq()) < 0,6,
if # and E + k and t = and k
Proof. First, we show that E[r:g,] 1[t # s]. Let t, [T]] and suppose that t * Without loss of generality, suppose that > 8. Then by using iterated expectation, we have that
[ = Elg. Wrr DJ] = E[g.] =
Otherwise, if t = 8, then rege [1[2 = 1)/p:) (1[2, = 01/(1 (p)) = 0 so that E[ra4]] = 0.
Next, show that Elr² D.J < + and E[ D.J J. Observe that EEL?? D.J Pt (1/pī) = 1/p, & 1/6,, where the inequality follows by definition of Algorithm 1. A similar argument shows that E[q] D.] & 1/8,.
Finally, we establish the covariance terms one by one. We do this in order of the cases that they were presented in.
Case 1 (t s) (f (f=Aa ke): If then r,q, is almost surely zero, as argued above. Likewise, if f then rege is almost surely zero. In either of these cases, we have that Cov(raq., Teqs) = 0.
Case 2 (L * 8) and (E + k) and {4, 5) n [e,k] Ø: Note that in this case, all the indices I, 8, L, and A are distinct.
Without loss of generality, suppose that t < < < k. A repeated use of the iterated expectation yields that
[[regere4a] = E[r:gare [gg, D.]] = B[rag.r]] = T req. B[rr Dz]] = K[r.gs] = =...
Because all terms of distinct, we have that E [[r = and E6 [ ] = 1. Thus, the covariance is equal to
Cov(rige, Tzqr) B[rag,, Tequl [[[ [[[eq]] =
26

---

Case 3 [t * s) and (e # k) and (t = k or s = E): Suppose that = k. In this case, observe that 7291: is zero almost surely. Thus, El = O. On the other hand, and * lo so that E[r.q,] E[r:q:] This means that Cov(re9s, rega) Elrig.reqs] B[rag=] B[rega] The same argument shows that s = L yields the same result.
1.
Case 4 (1 s) and (e oe k) and / é and t k): We begin by computing the expectation of the product of these four terms. In this case, we have that so that
Blregreaal = q.ri
By assumption, the indices I, 8, and k are all distinct. Our approach will be obtain upper bound the expectation of the project of these three terms by iterated expectation. In particular, the inequality we will use is that E[r? D.] & 1/6.. Suppose for now that k In this case, we use iterated expectation to get
Blregaragd] = E Tz Elr+ D:Jl E 8, Blg.gn]
= Elg. Elgs D&Jl
Elg.1
8z
In the above, have assumes that < k < f, but the same iterated expectation technique be applied regardless of the ordering of these indices, because they are unique. Thus, in this case, B[reqoreqd] & 1/8g. Because t * and * k, we have that [[[rq [[[rgu]] = This means that
1
Cov(req., Tequ) = B[riggregdl - B[raq.] B[reqd <
- 8,
Case 5 (t s) and (e * k) and & * é and s k): We begin by computing the expectation of the product of these four terms. In this case, we have that = lo so that
B[rigree B[r.re-]]
By assumption, the indices l, and are all distinct. Using similar argument the previous case, we can iterated expectation together with the bound B[q D&1 < 1/82 to obtain that Bfregereqs < 1/52. Because # and { * k we have that [r] Esrequ]= This means that
1 8,
Cov(rige, = B[regsres]] [Brea.] E[regd]
&
Case 6 (t # s) and ke) and and s k): Suppose without loss of generality that t s. this case, we can bound the product of the expectation of these four terms using iterated expectation and the proven inequalities:
B[regreed B[r E
D.1l
E[qal
8.
5,5,
Because t s, we have that E[riqe] E[re, g 1. Thus, the covariance is bounded by
Cov(rig,
E[ re E[reg.] EFregk] < 8,6,
First, show that that the difference between the expected value of A(1)A(0) and the target A(1).(0)) is decreasing at a linear rate in T.
Proposition D.1. The absolute bias of the estimated crossing term A(1)A(0) to its target value A(1)A(0) al most
C*
E A(1)A())) - -()))sss
T
Proof. Using Lemma D.3, we can calculate the expectation of the product A(1)A(0) as
( (0))
E
A(1))((())
(x(1)
T
Σ
De (c(1)²
r=
T2
27

---

I T
(0))
1
Σ
T
(1) (0)
T
T
7
1
Σ
(1))))
G
Σ
T
ys y=())))
1
Σ
T
ye (.))
7
A(1)
1 T
Σ
De (1) (0)²
We complete the proof by using Cauchy-Schwand and Assumption I, to bound the absolute bias as
E A(0) - A(1)A(0))
(1 v0)
T
( (1))))) 1/2
)
Σ yo (1)))
T
T
1/4
(7 Σ v.(0)9) 1/4 1/472
ye (c(1)*)
T
Ct
< T
Next, show that the variance of A(1) is going zero at sufficiently fast rate. Proposition D.2. The variance of A(1) is bounded as
Var Var(A(1) A(O))(()) & 4e L.Vlog(T'>>))))) S
40 (C$52v/og((r4)
((7)
1
T
T2
Proof. We begin by decomposing the variance of A(1)A(0) into covariances of products of the auxiliary random variables rt and fs- To this end, observe that
T
T
Var ((((A())())) Var
Σ
Σ
ye
T
T
T
T
T
1
Σ
(1'') Cov(reg,, regk)
T
Next, we will use the result of Lemma D.3 to handle the individual covariance terms. In particular, the first six types of terms, as described Lemma D.3. The first three types of terms are at most O, so we may discard them from the sum, as they contribute positive value. The last three terms have upper bounds, which we use here to obtain the following upper bound:
Σ
(1))))(
un 1)
De
1=1
(T](
Term Ti
T
Σ
Σ
i (n (1))v(1))) 5,
7
[=1 BE (T) (Vtt,))
Term T2
T
Σ
ve(1) ())
7
6,0-
Term
Our goal will now be to bound each of these terms individually.
28

---

Terms 1 and 2: Terms and 2 are similar and will be handled in the same way. Let's begin with Term 1. Observe that by Lyapunov's inequality, the moment assumptions, and Lemma D.2, we have that
Me (I()))) [ (0)))))
Ti ÔT T
2e 2eVooRTTu))
T )((1)))
T (0))))
(Lemma D.2)
T
2e DeVloRt (oR(TTi
T
31(1)4)
1/4
1 -
(0)3
1/22
T
T
T
De 2eVlog(ru:)
(1))
1/4
1 7
Σ
r
y/
(0)+)
1/4
(Lyapunov's inequality)
T
2e AoVlogTTii
(Assumption 1)
T
A similar argument shows that T2 & log(T(/3) / Term 3: The third term may be upper bounded using Lemma D.2 and the moment assumptions. Namely,
T3
(1))
y/ (0)+)
T (2eV (eVV 2
T
Me ma(11*)) ( Σ (0)+)
Σ
(Lemma D.2)
T2
& (C
(Assumption 1)
T
Taken together, this shows that
Var(A(1)A(O)) 4ev BeVlug(Tisiss
Ö 0(7)
T2
This establishes the following corollary, which shows that the error A(1 A(0) A(1)A(0) is going to zero at a near-parametric rate, which follows from by Chebyshev's inequality from Propositions D.1 and D.2.
Corollary D.1. The following error goes to zero: A(1)A(0) A(1) = Ö (1-
Using the results derived above, we are ready to prove Theorem 5.1, which we restate here for convenience.
Theorem 5.1. Under Assumptions and 2, and the parameters stated in Theorem 4.2, the error of the normalized variance estimator under CLIP-OGD T VB T VB (T
Proof of Theorem 5.1. Recall that the variance estimator and the variance bound are equal to T. VB = 45(1)5(0) =
4v A(1)A(0)) and T VB = 4v A(1) so that the error is given by
T. VB T VB 4 VA(I)A(O) - A(1)A(0)
Corollary D.I states that the error A(1)AA() A(1)AA(0) is on the order of (T By Assumption 1, we have that A(1)A(0)) = / S(D)SS(0)2 22 Observe that the square root function g(x) = v is Lipschitz on the interval (c2, co). Thus, by a rate-preserving Continuous Mapping Theorem, we have that the error of the normalized variance
estimator is on the same order i.c. T', VB - T VB (A(I)A(0) V A(1)A(0) Ö 1/2).
29

---

D.2 Valid Confidence Intervals (Corollary 5.1)
We now prove the asymptotic validity of the associated Chebyshev-type intervals. This proof is standard the design-based literature, but we present it here for completeness.
Corollary 5.1. Under Assumptions and 2, and parameters stated in Theorem 4.2, Chebyshev-rype intervals are attaaiii 1/2
asymptotically valid: for all a (0, 1J, lim -x Pr(T E f a
VB) > 1-a
Proof. Define the random variables
and Z' z'= T --
Z VVr(ff)
v VB
Observe that they are related in the following way:
(V Var(f)
VB
(V
Var(f)
T VB
Z'
Z
VB
VVr(ff)
VB
VB
VB
T VB
By definition, we have that lim supy Var(f)/VB & 1. Recall that by Proposition B.I, T VB > T V/- = 2(1) so that by Theorem 5.1 and Continuous Mapping Theorem, we have that have that Z' is asymptotically stochastically dominated by Z. Now we are ready compute the coverage probability.
T-VB
I. 1. Thus, by Slutsky's theorem we T-VB
lim inf Pr f VB
lim inf Pr
$ aa-2/ 1/2
T-
VB
lim imminfPr Pr T-2
& a 112
lim Pr
x a 112
1/2
T-
where the last line followed from Chebyshev's inequality and the fact that Var ()) 1.
E Analysis of Alternative Designs
In this section, we provide analysis on the efficacy of existing adaptive experimental designs for the problem of Adaptive Neyman Allocation. To this end, we show two negative results. In Section E. we show that the two-stage design of [Hahn et al., 2011, Blackwell et al., 2022] (i.e. Explore-then-Comeee the design-based framework for a large class of potential outcome sequences. In Section E.2, we show that mutli-arm bandit algorithms which achieve sublinear expected outcome regret will incur super- linear expected Neyman regret, providing further evidence that these two goals are incompatible.
can suffer linear expected Neyman Regret in
E.1 Analysis of Cestoorettee-CComee (Proposition 6.1)
In this setting, we show that Explore-then-Conee designs can sometimes suffer linear Neyman regret, and therefore not recover the Neyman variance in large samples. We formally introduce our definition of Explore-then-Commi designs below. Let * be defined as
Io 26 D Mz (1)2
Me (0)²
-1
PT.
1
which the optimal Neyman probability when considering only the sample up to To.
Our definition of ETC encompasses many possible ways of estimating the optimal treatment probability. The only requirement is that the estimation method will converge to pT, at the rate 1/- We consider pt, rather than the true Neyman probability ya because the observed data is informative only of the outcomes in the exploration phase Tp- Many natural estimators will fall into this class, including Horvitz-Thompson style estimators similar to those used the construction of our variance estimator.
30

---

Algorithm 2: EXPLORE-TIEN-COMMIT
Exloration phase size To // Explore Phase
Input:
for 1 = 1...7 To do
Sample treatment assignment Ze as 1 with probability 1/2 and 0 with probability 1/2 Observe outcome Y, 1[ = (1): 1[ (0)
end
Construct an estimator PTb from observed data (Z1, Y1. Zro Yr,) satisfying PT. P1t = Op(TT
// Exploit Phase
for To 1..... do
Sample treatment assignment Z: as 1 with probability pT, and 0 with probability
PTo
Observe outcome Y, 1[ (1) 1[ 0]
end
Before continuing, we provide few more definitions. as well as the correlation in the exploration phase
We define the second moments of treatment and control outcomes
To
Ta 1
1 E. Ve (0)
STU (1)) = Σ (1)
1
and PT. = To (T) = T Σ (0)
(1)(1) (0)
We are now ready to state the formal version of Proposition 6.1.
Proposition 6.1º. Suppose that To = (2(TT) for some e > and further suppose that the outcome sequence satisfies the following properties for constants C' O and è' d>> 0:
The second moments S(1), S(O), ST, (1), and ST, (0) are contained in the interval [c, C7.
The correlations bounded away from -I, i.e. PTo: > -1
The second moments satisfy the following:
S(0) STo
5(1)
STa (1) ST,
S(1)
+ S(0)
3 d
5(1) ST,
5(0)
Then, the Neyman Regret of Explore-then Explore-then-Commii is at least linear in probability, Rr lT)
The first two conditions essentially extensions of Assumption 1 to the exploration phase. This ensures that the probability pt, (which is estimated in the Explore-then-Comee Commii design) does not approach or 1. The third condition is what really makes papllor-then--ooeeee
fail to achieve sublinear Neyman regret. This condition states that the ratio of the second moments in the exploration phase is different than in the larger sequence. For example, if S(1) = S(0) = but S1, (0)/S2, (1) 2 then the condition would hold. In this case, should not expect Explore- Explore-then--ee Chen-Commit to achieve the Neyman variance because the exploration phase does not contain sufficient information about the optimal Neyman probability. We now prove the proposition.
Proof. Let p* arg min pe(o.11 E fe(p) be the Neyman probability. We begin by a-rraanggng terms in the Neyman regret:
Rr= Σ fe(pe) Σ fi(e²)
(def of Neyman regret)
1=1
fe(me) s1(x*) +
Σ -e(p")
-
(splitting terms by phases)
t To+1
To
T
Σ
f((1/2) f((=")
Σ
f((tt)) f((x")
(def of ETC)
1=T++1
To
T
Σ ((1/2) (.
+
[(PT)) S1(x*)
(adding + subtracting)
31

---

To Σ - -((P)) + (PP))) fe(p")
T
Where the inequality follows by the optimality of P7, on the exploration phase. By adding and subtracting the ft( to the second sum, obtain the following decomposition
To
Σ f((1))) - SilPT
F((TT - S.(1
SAPI.) - fz((*)
Term
Term 2
Term
We handle each of the terms separately in the remainder of the proof.
Term 1: By the assumptions on the second moments and correlation of outcomes the exploration phase, we have that Pro is bounded away from O and 1 by constant. Furthermore, the cost functions ft are Lipschitz on the interval
[y, 1 >] for any fixed y. Thus, we may apply the quantitative Continuous Mapping Theorem to bound the absolute value of Term as follows:
To
To
fl(Pt.)
f((Pt.) ) =
(P( - fe(e%)) )
(triangle inequality)
OTO 1/2
(estimator property + CMT)
= OT 1/2
= 02
= ?2
where the final inequality follows from the fact that To < T.
Term 2: A similar argument may be applied to the second term. Again, we may apply the continuous mapping theorem as before to obtain
-
<
f.(pt.)
(triangle inequality)
<
117 1/2)
(estimator property + CMTT
= Op(T 1/9
OP(T. (2112
- -p(T
where we have used the assumption that To = -T=
Term 3: We now handle the third term. Let Vo be the variance of adaptive Soavitz-Thompson estimator under the Bernoulli design when using the treatment probability pf. By construction of the cost functions, we have that they are related to the variance follows:
Σ fe(et.)) ) f((x*)
=T
T. Vo - T. VN
2 -1} + S(0)
11) - S(1)2
-13 + S(0)2 (1-
( 1- p= -11p=-13)) 11)
11)
T.
p* [-]-1--
P16
1 - PTo
T.
S(1)2
PT p* -1)) S(0)
1 pTo
1 - p.
32

---

S(O) 5(1
(0) ST. (1)
S(1) 5(0)
Sr, (1) STo (0)
=T.
S(1)
S(0)
where the last equality follows by definition of the probabilities. By Assumption, we have that this bracketed term is constant so that the third term is linear in T.
Putting these together, we have that the Neyman regret is lower bounded as
Rr > S(TT) Op(T" -0
(p(T = =2p(T)
E.2 Analysis of Designs for Outcome Regret (Proposition 6.2)
In this section, we prove Proposition 6.2, which establishes that outcome regret and Neyman regret cannot be simultane- ously minimized in general. We restate a more formal version of the proposition here. In order for a simpler proof, we make restrictions that the units have constant treatment effect and that each of the individual outcomes more strictly bounded. We conjecture that the trade-off between Neyman and outcome regret will hold under weaker conditions.
Proposition 6.2a. Let A be an adaptive treatment algorithm achieving sublinear outcome regret, i.e. there exists E (0, 1) such that [[ & O(T9) for all outcome sequences satisfying Assumption I. Consider an outcome sequence satisfying Assumption with constants c and the additional conditions:
maxTgtET (0) C
all te (1() (0) and T > d' for constant d' > 0.
Then, A suffers super-linear Neyman regret on this outcome sequence: B[RT] Q(T2-9).
To begin, we re-express the outcome regret in terms of the expected treatment probabilities played by algorithm A. Observe that the expected outcome regret may be written as
Proof.
E R
Routcomme
E
max 1e((,1)
(k))
Σ
Yi
(def of regret)
1=1
t=1
Σ (1)
E
[(r]]
(T 0)
Σ (1)
Σ LE (1) = 11 (,))) =]]
Σ
(1)
Σ (e(1) B[pr] (0) (1 Elpr))
Σ (B)(1) (0) (1- (1-E(p.))
Σ (1 E(p.])
where the last equality follow as (1) (0) = r for all E [T] by assumption. Because the outcome sequence satisfies Assumption I, the expected outcome regret is at most Regitoooe & 3. T9 for some constant B. By the above, this implies that the expectation of the sum of probabilities 1 - pr must be small,
T (1 Elpl) T
Next, we show that A must incur large cost with respect to the functions f. in the definition of Neyman regret. To do this. we will use weighted version of the AM-HM inequality which states that for 2 ... ET >> and w1 ... Wn 2e 0, we have that
Σ
T
WoFt
W4
Y
T
1=1
W/
FF
33

---

The usual AM-HM inequality is recovered when 1/T.
We now bound the expected Neyman loss, observing that
T
T
(1]
(0)
E
f((p))
(def of ft)
Pt
- Pt
(0)
(non-negativity)
Pr.
(0) E
(linearity of EE-))
Pt.
(o(
(Jensen's inequality)
E p.l
E (0)
(weighted AM-HM)
1- (0) 1B[1 -
7 ΣT (0)2
EIET D4 (0)
EE [ Pr.
1-1
5(0)²
1
T
max1 TIET ye (0)
E Pt
T
T T
C
3
T2-9
C2
where the last two inequalities follow from moment bounds in Assumption together with the assumptions on the outcome sequence stated in the Theorem.
Next, we show that the optimal Neyman design incurs a much smaller cost. In particular,
min pc (0.
Σ fp(p) &
fe(12)
yr(1)2
(=)
Σ
1/2
1/2
1 T
2T
T (1)²
Σ (0)2
T
(T + S(0)3)
< 2C
Together, these facts establish that the Neyman regret for A is lower bounded as
I
èd
E ERR E Σ
f(lp)) min Σ f(l)) pE[U,1]
40TT> - 2(T2-9)
C²B
F Ethical Considerations
There are at least two objectives when constructing adaptive treatment allocation.
Minimizing Cumulative Regret: give the "best" treatment to as many people as possible.
Minimizing Variance of the Effect Estimate: estimate the effect of the treatment as high precision as possible.
34

---

As we show in Proposition 6.2, these two objective are fundamentally incompatible: an adaptive design which aims to estimate the effect high precision must assign treatment which has worse outcomes. Likewise, a design which seeks to maximize the utility of assigned treatments will not be able to reliably estimate causal effects to high precision. Which one of these is more ethically desirable depends on the purpose and the context of the experiment. For guidance on this ethical question, we turn to The Belmont Report.
In 1979, the National Commission for the Protection of Human Subjects of Biomedical and Behavioral Research released the "Belmont Report", which has been one of the foundational texts for ethical guidance in research conducted with human subjects [for the Protection of Human Subjects of Biomedical and Research, 1978]. One of the three basic ethical principles laid out in the report is "benevolence" which is understood as an the obligation the researcher has for the research to improve the general well-being of society, including those people in the experiment. The report writes:
The Hippocratic maxim 'do no harm' has long been fundamental principle of medical ethics. Claude Bernard extended to the realm of research, saying that one should not injure one person regardless of the benefits that might come others. However, even avoiding harm requires learning what is harmful; and, in the process of obtaining this information, persons may be exposed to risk of harm. Further, the Hippocratic Oath requires physicians to benefit their patients 'according to their best judgment.' Learning what will in fact benefit may require exposing persons to risk. The problem posed by these imperatives is to decide when it is justifiable to seek certain benefits despite the risks involved, and when the benefits should be foregone because the risks.
From this perspective, it may be ethically advisable researcher to learn the effect while subjecting fewer human subjects to the experimental treatments. other words, a variance minimizing design allows researchers learn what is harmful and what is beneficial while subjecting fewer human subjects to possible harm. An adaptive treatment plan which minimizes cumulative regret will ensure that minimal harm is done to subjects in the experiment, but will offer less certainty about the extent of the benefit harm of the treatments. Such an approach will lead to less informative generalizable knowledge of treatment effects, possibly defeating the goal of the research study.
variance minimizing adaptive design because it allows the
That being said, is not our goal to suggest that one adaptive allocation plan is most ethical in all circumstances. Indeed, these ethical questions have systematic answers which are generally applicable. It is the burden of the researchers to carefully "decide when it is justifiable to seek certain benefits despite the risks involved, and when the benefits should be foregone because of the risks." Our goal in this work is merely to provide improved statistical methodology which affords the researchers more choices when addressing these ethical questions.
35


Reviews:
[{"review_id": "OmEeOf0GAh", "reviewer": "Reviewer_xwuB", "summary": "The paper proposes a new adaptative Neyman allocation for experimental design. The proposed adaptative design gets close to the optimal non-adaptative strategy without suffering from the same infeasibilities. ", "questions": "1) I would like to see some discussion about the medical applications vs a more broader motivation.", "limitations": "Limitations are adequately addressed.\n\n", "rating": 5, "confidence": 1, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1) The writing and structure of the paper are OK.\n2) The topic is very relevant, and the paper proposes adaptative variance with formal guarantees ensuring feasibility is interesting.", "weaknesses": "1) The paper is not easy to follow for the non-expert, both concerning the notations used and the derivations.\n2) It seems that the motivation for this work could be broader. It is unclear to the reviewer why the authors focused on medical applications.\n3) The method is only applied to a single microeconomic example. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer 1 (xwuB)\n\nThank you for your careful reading of our submission.\nWe are glad to hear that you find the topic relevant and the formal guarantees interesting.\nBelow, we respond to the specific critiques raised in your review.\n\n## Broader Movtivations\n\n> It seems that the motivation for this work could be broader. It is unclear to the reviewer why the authors focused on medical applications...I would like to see some discussion about the medical applications vs a more broader motivation.\n\nAlthough clinical trials are a relevant application, we agree that the statistical methods in this paper apply more broadly to a variety of domains.\nSome motivating examples of randomized experiments in other disciplines include:\n\n- **International Development Economics**: International Development Economics (IDE) is concerned with determining which interventions (typically by NGOs or state governments) increase economic outcomes in developing nations. In the past 15 years, the introduction of randomized experiments (as opposed to relying solely on economic theory) has been a major development is figuring out \"what works\" (see, e.g. Banerjee et al 2015, Duflo 2012). In fact, Esther Duflo, Abhijit Banerjee, and Michael Kremer won the 2019 Nobel Prize in Economics for their foundational role in this line of work. IDE experiments with short-term outcomes can be implemented in a sequential manner.\n- **Email Marketing**: Nearly all companies that operate online use email marketing campaigns (see, e.g. Ellis-Chadwick & Doherty 2012). A common type of experiment is to test which personalization strategy will improve a certain outcome, e.g. a customer clicking a link. More generally, experiments like this are frequently run at tech companies to guide product development. These experiments typically have very quick response times and so can be made to run sequentially.\n- **Quantitative Political Sciences**: There has been a recent revolution in political science to incorporate more principled causal inference methods. A seminal work in this area is Gerber & Green (2000), which invesitgates the effects of canvassing on voter turn-out. More recently, Offer-Westort et al 2021 run a sequential experiment to test various interventions for reducing partisan bias.\n\nOur work shows that in settings where sequentially running the experiment is possible, fewer people are needed in the experiment to detect an effect, thereby saving money and resources.\n\nIn order to address your comment, we will update the introduction to better highlight these applications beyond medical trials, thereby broadening the motivation for this work.\n\n- Banerjee, Abhijit, Esther Duflo, Rachel Glennerster, and Cynthia Kinnan. 2015. \"The Miracle of Microfinance? Evidence from a Randomized Evaluation.\" American Economic Journal: Applied Economics, 7(1): 22-53.\n- Esther Duflo. “Women’s Empowerment and Economic Development”, Journal of Economic Literature, Vol. 50, No. 4: 1051-79, December 2012.\n- Ellis-Chadwick, Fiona and Doherty, Neil F. (2012). Web advertising: the role of email marketing. Journal of\nBusiness Research, 65(6) pp. 843–848.\n- Gerber, Alan S., and Donald P. Green. “The Effects of Canvassing, Telephone Calls, and Direct Mail on Voter Turnout: A Field Experiment.” The American Political Science Review, vol. 94, no. 3, 2000, pp. 653–63.\n- Molly Offer-Westort, Alexander Coppock, and Donald P. Green. \"Adaptive experimental design: Prospects and applications in political science.\" American Journal of Political Science, 65(4): 826–844, 2021. doi: 10.1111/ajps.12597.\n\n## Readability and Derivations\n\n> The paper is not easy to follow for the non-expert, both concerning the notations used and the derivations.\n\nOther reviewers (2JiC, etbf, wYBx) asked for further interpretation of Assumptions 1 and 2, as well as additional discussion into the derivation of the main algorithm, Clip-OGD.\nPlease see our responses to their reviews for more details on how we addressed these points.\nWe hope that these additional discussions on assumptions and derivations improve readability for a general audience.\n\nWe agree that the notation used in design-based causal inference can be sometimes cumbersome, especially relative to general statistics or machine learning.\nWe strive to make our paper as readable to as wide of an audience as possible, but we find value in sticking to conventional notation."}, {"review_id": "F3GFFUDWAo", "reviewer": "Reviewer_NsFr", "summary": "This paper studies the problem of “Adaptive Neyman Allocation”, which involves designing an efficient, adaptive experimental design. Neyman allocation is an infeasible experimental design which would be optimal (minimum variance) if the planner knew all the exact potential outcomes under different treatments. However, this is infeasible, and so the goal considered in the paper is to build an adaptive experimental design which is nearly as efficient (in terms of variance) as the infeasible non-adaptive Neyman allocation asymptotically.\nTo measure the performance, the first contribution of the paper is to propose new measures of regret (and regret ratio) similar to the notion of regret in bandits/statistical learning. Second, the paper proposes an adaptive design based on the idea of adaptive gradience descent to adjust the treatment probabilities to minimize regret. The paper shows that the regret in this approach scales as O(sqrt(T)). Finally the paper constructs confidence intervals which guarantee asymptotic coverage of the average treatment effect.  \n", "questions": "– In section 4.1 why isn’t the variance of adaptive experimental design, V also a function of t?\n\n– There seem to be a few other approaches that study adaptive randomziation in clinical trials. For example: Zhang, Lanju, and William F. Rosenberger. \"Response‐adaptive randomization for clinical trials with continuous outcomes.\" Biometrics 62.2 (2006): 562-569. \nHow does the proposed approach compare against existing methods?\n\n– Ethical concern: Please see additional question under Limitations section.\n", "limitations": "Could there be fairness/social welfare concerns stemming from such optimal designs? Perhaps the allocation algorithm may assign a higher probability to a less effective or detrimental treatment simply because the variance in its outcomes is higher. As a result, in the quest for minimized variance, could the negative treatment be administered more often than advisable/necessary?\n", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "– Novelty: The paper claims to be the first to introduce the notion of Neyman regret in the context of adaptive experimental designs. I am not fully aware of the related literature, but this seems to be an interesting contribution to analyze from this perspective. \n\n– Well-written: The paper is well organized overall and the concepts are introduced and explained crisply.  \n\n– Theory: The paper presents results well-grounded in theory.\n\n", "weaknesses": "1. Related Work: The related work section mainly talks about  Neyman allocation and about casual inference under adaptively collected data. However, it seems there is also a large body of work that studies adaptive experimentation/ adaptive design for randomized trials. All of these references seem to be missing (please see few examples below and references therein)? It would be good to distinguish this paper from this body of related work. \n\n-- Eggenberger, Florian, and George Pólya. \"Über die statistik verketteter vorgänge.\" ZAMM‐Journal of Applied Mathematics and Mechanics/Zeitschrift für Angewandte Mathematik und Mechanik 3, no. 4 (1923): 279-289\n\n-- Xu, Yanxun, Lorenzo Trippa, Peter Müller, and Yuan Ji. \"Subgroup-based adaptive (SUBA) designs for multi-arm biomarker trials.\" Statistics in Biosciences 8 (2016): 159-180.\n\n-- Eisele, Jeffrey R. \"The doubly adaptive biased coin design for sequential clinical trials.\" Journal of Statistical Planning and Inference 38, no. 2 (1994): 249-261.\n\n-- Hu, Feifang, and William F. Rosenberger. \"Optimality, variability, power: evaluating response-adaptive randomization procedures for treatment comparisons.\" Journal of the American Statistical Association 98, no. 463 (2003): 671-678.\n\n2. Unsurprising: To me it is a little unsurprising/ unimpressive that the approach can achieve the optimal data efficiency as T tend to infinity (after a really large number of samples). The authors also seem to acknowledge this in part in the final section of the paper. \n\n3. Empirical Evaluation: It may be useful to add more interesting baselines if available in comparison of the regret \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer 2 (NsFr)\n\nWe thank you for your thoughtful review of our paper and we are glad to hear that you found our exposition crisp and the results well-grounded in theory.\nWe are grateful for the comments, questions, and concerns raised in your review: they have highlighted weak points in our paper, which we have worked to address.\nAs a result, we believe the paper has been greatly strengthened.\n\nWe are limited for space in our rebuttal, but happy to expand upon any points in the discussion period.\nWe hope you find that many of these have been addressed.\n\n## W1: Related Work\n\n> The related work section mainly talks about Neyman allocation and about casual inference under adaptively collected data. However, it seems there is also a large body of work that studies adaptive experimentation/ adaptive design for randomized trials. All of these references seem to be missing (please see few examples below and references therein)? It would be good to distinguish this paper from this body of related work.\n\nWe thank you for providing us with additional references so that we can better contextualize our results within a broader literature.\nWe have read these papers (some of them familiar, some of them not) as well certain references therein and prepared a (longer) appropriate survey which better distinguishes our paper from this body of work.\nTo address this point raised in your review, we will include these papers into our literature review and better differentiate our work from the papers you raised.\n\nOur problem setting is distinct from this literature in two ways.\nThe first distinction is the goal of the adaptive design.\nIn the references above, there are a variety of goals from reducing sample size, to minimizing \"harm\", to identifying relevant subgroups.\nIn contrast, our work focuses on the goal of minimizing the variance of the sequential Horvitz--Thompson estimator.\nThe second distinction is the inferential frameworks.\nWhile the references you listed make strong independence and parametric assumptions (which simplify their problems), we take a design-based perspective, requirigin neither i.i.d. nor parametric assumptions on the outcomes.\n\n## W2: Unsurprising\n\n> To me it is a little unsurprising/ unimpressive that the approach can achieve the optimal data efficiency as T tend to infinity (after a really large number of samples). The authors also seem to acknowledge this in part in the final section of the paper.\n\nWe respectfully disagree; the state of prior work suggests that the main results presented in the paper are surprising and relevant to the design-based inference community.\nThe most closely related work of (Hahn et al 2011) and (Blackwell et al 2022) for the same problem of Adaptive Neyman Allocation was not able to establish that the optimal Neyman variance was recovered in large samples -- in fact, we show in Proposition 6.1 that the adaptive designs presented in those papers *provably cannot* obtain the Neyman variance in large samples.\nExperimental results (Fig 1b) corroborate this theoretical analysis.\nOur main results are the first to provably achieve this goal of Adaptive Neyman Allocation.\nOne of the insights of our work (which may be surprising to the design-based causal inference community) is that sophisticated algorithmic techniques seem to be required to achieve optimal Neyman variance, as the problem is equivalent to an adversarial online convex optimization problem.\n\n## W3: Empirical Evaluation\n\n> It may be useful to add more interesting baselines if available in comparison of the regret.\n\nWe have included two additional baselines.\nPlease see \"Global Response\" for details.\n\n## Q1: Variance Derivation\n\n> In section 4.1 why isn’t the variance of adaptive experimental design, V also a function of t?\n\nWe believe there is a slight misunderstanding here -- you are absolutely correct that the variance of the adaptive experimental design $V$ will be a function of $T$.\nWe write $V = (1 + \\kappa_T ) \\cdot V_N$, where $\\kappa_T$ is the Neyman ratio and $V_N$ is the optimal Neyman variance.\nBoth of these quantities depend on $T$.\nWe are happy to further clarify if this is unclear.\n\n## Q2: Comparison to Existing Method\n\n> There seem to be a few other approaches that study adaptive randomziation in clinical trials...How does the proposed approach compare against existing methods?\n\nThank you for this additional reference.\nThe recommended adaptive design in this paper is the Doubly Biased Coin Design (DBCD), which we have included in simulations (see \"Global Response\").\n\n## Q3: Ethical Concerns\n\n> Could there be fairness/social welfare concerns stemming from such optimal designs? Perhaps the allocation algorithm may assign a higher probability to a less effective or detrimental treatment simply because the variance in its outcomes is higher. As a result, in the quest for minimized variance, could the negative treatment be administered more often than advisable/necessary?\n\nGreat question!\nWe have written an additional section for the appendix that addresses your point, which we are happy to share in the discussion phase.\n\nThe highly influential 1979 \"Bellman Report\" writes that \"even avoiding harm requires learning what is harmful...Learning what will in fact benefit may require exposing persons to risk\".\nFrom this perspective, it may be ethically advisable to use a variance minimizing adaptive design because it allows the researcher to learn the effect while subjecting fewer human subjects to the experimental treatments.\nOn the other hand, an adaptive treatment plan which minimizes cumulative regret will ensure that minimial harm is done to subjects in the experiment, but will offer less certainty about the extent of the benefit or harm of the treatments.\nSuch an approach will lead to less informative generalizable knowledge of treatment effects, possibly defeating the goal of the research study and being, as a result, more unethical."}, {"review_id": "HHcXw5fL4O", "reviewer": "Reviewer_2JiC", "summary": "The work considers adaptive experimental design for sequential experiments. To do so, a new regret-like measure, called Neyman regret is defined that compares the ratio of the variance under the chosen experiment design with respect to the variance under the optimal experiment design. Drawing connections to online convex optimization literature, an algorithm is developed that provides $\\tilde O(\\sqrt(T))$ Neyman regret. In contrast, it is also established that two-stage explore then commit or multi-arm bandit setups may not result in (super)linear Neyman regret. Additionally, asymptotically valid confidence intervals using the adaptively collected data are provided.", "questions": "A.  For the gradient term in the algorithm, it might be beneficial to elaborate on that, i.e., from variance eqn to eqn for estimating that variance and taking the derivative to get the cubic terms.\n\nB. I see the need for the projection term in the algorithm, but it is not clear how to actually set it in practice. \n\nC. I am curious if the authors can elaborate on the choice of the utility for gradient estimation. Instead of minimizing the utility with just the new sample, why not do a Follow-the-leader style algorithm to minimize the utility over all the samples seen so far? Maybe even FTRL, with a regularizer that prevents the distribution from shifting too far from Bernoulli(0.5) could replace the projection step?\n\nD. I think the discussion around non-superefficient variance is important and I while I see the need of it, I do not quite understand it properly. Having more discussion about that could be beneficial.\n\nE. What is the practical relevance of the experiment setup for Fig 1(b)?", "limitations": "F. To understand the sensitivity of the projection hyper-parameter, can ablations for it be provided in Fig 1?", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "S1. An important topic of sequential experimental design, particularly setting up the framework from the point of regret minimization.\n\nS2. The core idea is well-presented \n\nS3. Comparison of Neyman regret with alternative designs is also valuable.", "weaknesses": "W1. Numerical simulations that analyzed more aspects of the algorithm could have made the paper stronger.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer 3 (2JiC)\n\nWe thank you for your careful review of our paper and we are happy to hear that you believe the core idea to be well-presented and find the comparison to alternative designs valuable.\nWe are grateful for the questions and concerns you raised in your review, which have strengthened the paper.\nWe respond to your questions and concerns below.\n\n## Weakness W1: Stronger Simulations\n\n> W1. Numerical simulations that analyzed more aspects of the algorithm could have made the paper stronger.\n\nThank you for encouraging us to increase the strength of our simulations.\nWe have added additional baselines and stability analyses.\nPlease see \"Global Response\" for details.\n\n## Question A: Gradient Term\n\n> A. For the gradient term in the algorithm, it might be beneficial to elaborate on that, i.e., from variance eqn to eqn for estimating that variance and taking the derivative to get the cubic terms.\n\nThank you for highighting this weakness in our exposition.\nWe will address this by adding a few sentences describing the derivation of the gradient estimator after Algorithm 1.\n\n## Question B: Projection Term\n\n> B. I see the need for the projection term in the algorithm, but it is not clear how to actually set it in practice.\n\nIn Clip-OGD, we set the projection parameter according to a decaying rate, $\\delta_t = (1/2) \\cdot t^{-1/\\alpha}$, where $\\alpha$ is a decay parameter chosen by the experimenter.\nAlthough $\\alpha$ could be arbitrarily chosen, our regret analysis in the proof of Theorem 4.2 demonstrates that choosing $\\alpha = \\sqrt{5 \\log(T)}$ minimizes our derived upper bound on the expected Neyman regret.\nIn this sense, we recommend that experimenters choose $\\alpha = \\sqrt{5 \\log(T)}$ in practice.\nNote that the experimental data is only collected once so that it is not possible to choose $\\alpha$ using cross-validation or a similar statistical method.\n\n## Question C: Gradient Estimation\n\n> C. I am curious if the authors can elaborate on the choice of the utility for gradient estimation. Instead of minimizing the utility with just the new sample, why not do a Follow-the-leader style algorithm to minimize the utility over all the samples seen so far? Maybe even FTRL, with a regularizer that prevents the distribution from shifting too far from Bernoulli(0.5) could replace the projection step?\n\nThis is a great question!\nWe tried an approach like this, but had difficulty analyzing its properties.\n\nOn one hand, you need to allow the algorithm to be able to select $p_t$ arbitrarily close to $0$ or $1$ as $T$ grows, which means that penalizing the distance from Bernoulli(0.5) is challenging to implement correctly.\nOn the other hand, an approach that does not explicitly constrain $P_t$ to be in the open interval $(0,1)$ might have the propery that the $P_t = 1$ or $P_t = 0$  at some round with non-zero probability, which would introduce bias in the Horvitz--Thompson estimator.\n\nAn interesting open question is to achieve sublinear expected Neyman regret *without* using a projection step.\nWe conjecture that this could shave off the sub-polynomial factor from our bounds on the expected Neyman regret and achieve a clean $\\mathcal{O}(\\sqrt{T})$.\n\n## Question D: Assumption 2\n\n> D. I think the discussion around non-superefficient variance is important and I while I see the need of it, I do not quite understand it properly. Having more discussion about that could be beneficial.\n\nThank you for your comment, which highlights the need for additional discussion following Assumption 2.\nDue to space considerations, we removed such a discussion.\nHowever, we are more than happy to add a brief discussion which addresses these points back in the main body.\nPlease see \"Global Response\" for an interpretation of Assumption 2.\n\n## Question E: Fig 1(b)\n\n> E. What is the practical relevance of the experiment setup for Fig 1(b)?\n\nThank you for raising this question, which highlights a weakness in our exposition.\nWe will update Section 7 with a brief discussion on the practical relevance of the experimental setup for Fig 1(b).\nHere is a longer discussion below:\n\nPractically speaking, Fig 1(b) represents a possible scenario where the first 100 people in the micro-economic experiment actually invest *less money* in machinery or equipment if they receive the macro-insurance intervention, while the remaining 14,435 people will invest *more money* given the macro-insurance.\nThis sort of scenario is not unreasonable -- perhaps the first 100 people recruited into the trial were systematically different from the rest, i.e. from a well-connected part of the entrepreneurial community.\n\nExplore-then-Commit (ETC) experimental designs -- which are the predominant existing method proposed by (Hahn et al 2011) and (Blackwell et al 2022) -- heavily rely on the first units arriving being representative of later units.\nThe simulation results in Fig 1(b) demonstrates that these methods can actually increase the variance, while Clip-OGD does not suffer from these issues."}, {"review_id": "pwTqpj4KLy", "reviewer": "Reviewer_etbf", "summary": "The authors study adaptive allocation of samples into control and treatment groups in an experiment. They (i) define new performance measures for such allocations, namely Neyman ratio and Neyman regret, (ii) introduce a new algorithm called Clip-OGD that achieves optimal Neyman regret, and (iii) provide asymptotically correct confidence intervals for experiments run with Clip-OGD.", "questions": "1) In the paragraph starting from line 226, Neyman regret is discussed from the perspective of multi-armed bandits. I understand how explore-exploit algorithms like UCB are not suitable for minimizing the Neyman regret; the purpose of adaptive Neyman allocation seems to be purely exploratory. Then, how does it relate to existing pure-exploration bandits?\n\n2) Assumption 2 is not intuitive and is not explained well enough. What does \"ruling out settings where the outcomes were chosen with knowledge of Clip-OGD\" mean exactly? I understand the formulation assumes $y_0(t)$ and $y_1(t)$ are deterministic, but just to understand Assumption 2, what would its equivalent have been under a super-population assumption (i.e. if $Y_0(t)$ and $Y_1(t)$ were to be random and i.i.d.)?\n\n3) Confidence intervals provided in Section 5 seem to be only asymptotically correct. Does this mean that no finite-sample guarantees are possible regarding the error rate of these intervals? This would limit the use of Clip-OGD in settings where strict error control is required (such as clinical trials).\n\n4) Why do the experiments not include a multi-armed bandit baseline although they are mentioned as an alternative design in Section 6?\n\n5) What does \"informal\" mean in Proposition 6.1? If it does not have a formal proof, maybe it should be stated as a remark rather than a proposition.", "limitations": "Yes, the authors adequately addressed the limitations of their work.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Presentation-wise, this is an extremely well-written paper. In particular,\n\n(i) The metrics that are proposed, Neyman ratio and Neyman regret, are well motivated. It is convincing why minimizing the Neyman ratio is desirable and how minimizing Neyman regret is a surrogate for that objective.\n\n(ii) Clip-OGD is a simple and intuitive algorithm. Notably, it does not have hyper-parameters that require tuning (although they could potentially be tuned). This is a major strength for an online algorithm where cross-validation using an offline dataset would not be possible.", "weaknesses": "There are only minor weaknesses (please see my questions below).\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer 4 (etbf)\n\nWe thank you for your careful reading of our paper and we are happy to hear that you find the paper well-written and its results well motivated.\nYour comments in this review have been very helpful, as they have identified a few weak points in the paper which we have addressed.\n\n## Question 1: Relation to Pure Exploration Bandits\n\n> In the paragraph starting from line 226, Neyman regret is discussed from the perspective of multi-armed bandits. I understand how explore-exploit algorithms like UCB are not suitable for minimizing the Neyman regret; the purpose of adaptive Neyman allocation seems to be purely exploratory. Then, how does it relate to existing pure-exploration bandits?\n\nGreat question! Although there are many objectives for pure exploration bandits (e.g. simple regret, best arm identification), they are all concerned with selecting or identifying the best arm.\nIn contrast, the objective in causal inference is to estimate the difference between the means of the two arms, to high precision.\nWe are not only interested in *which arm* is the better arm, but rather we are interested in estimating *how much better* is the better arm.\nThis is the average treatment effect.\n\nIn Proposition 6.2, we showed that a bandit algorithm which minimizes cumulative regret will necessarily incur a large variance of the effect estimator, by orders of magnitude.\nThis shows that cumulative regret and Neyman regret are generally incompatible.\nWe have not investigated whether a similar incompatibility result holds for pure exploration bandits objectives such as simple regret and best arm identification, but we conjecture that the answer is \"yes\".\n\n## Question 2: Assumption 2\n\n> Assumption 2 is not intuitive and is not explained well enough. What does \"ruling out settings where the outcomes were chosen with knowledge of Clip-OGD\" mean exactly? I understand the formulation assumes $y_0(t)$ and $y_1(t)$ are deterministic, but just to understand Assumption 2, what would its equivalent have been under a super-population assumption (i.e. if and were to be random and i.i.d.)?\n\nThank you for your comment, which highlights the need for additional discussion following Assumption 2.\nDue to space considerations, we removed such a discussion.\nHowever, we are more than happy to add a brief discussion which addresses these points back in the main body.\nPlease see a longer answer to your question in the \"Global Response\".\n\n## Question 3: Confidence Intervals\n\n> Confidence intervals provided in Section 5 seem to be only asymptotically correct. Does this mean that no finite-sample guarantees are possible regarding the error rate of these intervals? This would limit the use of Clip-OGD in settings where strict error control is required (such as clinical trials).\n\nYes, you are correct that we do not establish any finite sample guarantees for these confidence intervals.\nWe agree that confidence intervals with finite sample guarantees would be more desirable in practice, provided that they would not increase dramatically in width.\n\nHowever, we remark that asymptotic coverage guarantees are the standard in causal inference (space is limited in this rebuttal, but we are happy to provide additional citations during discussion period).\nIn fact, randomized clinical trials today typically use exactly these types of confidence intervals, which only guarantee coverage asymptotically.\nThis is referred to in practice as a \"large sample approximation\".\nIn this sense, our results are in-line with the literature.\nMoreover, over additional simulation results in the appendix show that the intervals cover at the nominal level.\n\n## Question 4 -- MAB in Experiments\n\n> Why do the experiments not include a multi-armed bandit baseline although they are mentioned as an alternative design in Section 6?\n\nThanks you for raising this point, which encouraged us to update our simulations and strengthened the paper.\nPlease see \"Global Response\" for our discussion on the results of a MAB baseline and additional new simulation results.\nInitially, we did not include a MAB baseline because Proposition 6.2 shows that any adaptive design guarantees a cumulative regret of $\\mathcal{O}(\\sqrt{T})$ must incur a variance of $\\Omega(1 / \\sqrt{T})$, orders of magnitude larger than even naive Bernoulli.\nSimulations are consistent with this claim.\n\n## Question 5: Proposition 6.1\n\n> What does \"informal\" mean in Proposition 6.1? If it does not have a formal proof, maybe it should be stated as a remark rather than a proposition.\n\nWe recognize that \"informal\" was a confusing term to use in Proposition 6.1.\nInitially, the term \"informal\" was used here because the class of potential outcomes referenced by Proposition 6.1 is directly constructed in the appendix.\nMoreover, Proposition 6.1 is restated in the appendix with respect to this class.\nThat being said, there is nothing \"informal\" about Proposition 6.1 from the point of mathematical rigor.\n\nTo address this comment, we have removed the word \"informal\" and replaced the sentence after Proposition 6.1 with the following: \"The specific class of potential outcomes referenced in Propposition 6.1 is constructed in Appendix E.1\".\n"}, {"review_id": "nak8Biv1dK", "reviewer": "Reviewer_wYBx", "summary": "This paper studies adaptive Neymann allocation and proposed an algorithm that achieves expected Neymann regret $\\tilde{O}(\\sqrt{T})$. I am not an expert in sequential experiment design so my ability is limited to assess the impact/relevance of this paper. Yet, I do consider myself well-versed in the potential-outcomes framework.", "questions": "1. I understand the authors may wish to provide sufficient background, but it is a bit hard to tell what are existing (and well-known) results and what are new results (except starting from page 6 when the authors introduce the algorithm).\n2. I felt Assumption 1 is a bit tricky to decipher: what is the motivation to have the same constant $c$? What are the scenarios where this assumption may break?\n3. Have you considered combining CLIP-OGD with an outcome model to get a doubly-robust estimator?\n4. Can you add more simulations?", "limitations": "Not applicable", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- I found the writing and analyses appear to be rigorous and precise.\n- The proposed algorithm achieves the Neymann variance in the synthetic experiment.", "weaknesses": "See \"Questions\" for more details.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer 5 (wYBx)\n\nWe thank you for your thoughtful reading of our paper.\nWe are happy to hear that you found the writing and analysis to be rigorous and precise.\nMoreover, your comments have helped us improve the paper in places where there were ambiguities or confusion.\n\nWe respond to the questions raised in your review below.\n\n## Question 1 - Existing and New Results\n\n> I understand the authors may wish to provide sufficient background, but it is a bit hard to tell what are existing (and well-known) results and what are new results (except starting from page 6 when the authors introduce the algorithm).\n\nThank you for highlighting this lack of clarity in our writing.\nLet us summarize the separation between existing work and our main contributions here.\n\n- **Existing Work**: The main existing results which are similar in spirit to ours are the works of (Hahn et al 2011) and (Blackwell et al 2022) which propose and formally analyze experimental designs for Adaptive Neyman Allocation. Neither of these works are able to show that the optimal Neyman variance is achieved, even in large samples.\n\nIn this paper, our main contributions are:\n\n- (Section 4.1): The introduction of performance measures which ensure that the optimal Neyman variance is achieved in large samples.\n- (Section 4.2): A new adaptive experimental design which ensures bounds on the Neyman regret, thereby ensuring that the optimal Neyman variance is achieved.\n- (Section 5): Methods for valid confidence intervals using this experimental design.\n\nThere are two additional minor contributions are contained in Section 6:\n\n- Proposition 6.1 shows that the \"explore-then-commit\" style designs proposed by existing work (Hahn et al 2011) and (Blackwell et al 2022) **can not attain optimal Neyman variance** in a design-based framework without very strong homogeneity assumptions.\n- Proposition 6.2 shows that MAB algorithms which minimize outcome regret are incompatible with achieving optimal Neyman variance. In fact, the variance of MAB algorithms will have convergence rates **larger by orders of magnitude**.\n\nThe background in Section 2 contains the formulation of design-based inference as well as basic facts about the adaptive Horvitz--Thompson estimator.\nThese basic facts have been established in i.i.d. settings but perhaps not design-based settings, although this does not count as a contribution by any means and we do not mean for it to be interpreted as such.\nWe will add a citation to the i.i.d. literature to make this clear.\n\nIn order to address your question, we will revise the introduction, related work, and preliminaries sections to clarify these points.\n\n## Question 2 -- Assumption 1\n\n> I felt Assumption 1 is a bit tricky to decipher: what is the motivation to have the same constant $c$\n? What are the scenarios where this assumption may break?\n\nWe appreciate your comment here, which highlights that Assumption 1 would benefit from a longer discussion which more carefully interprets its scope conditions.\nTo address your comment, we will include in the paper a discussion similar to the one below (although more streamlined):\n\nAs stated briefly at the end of Section 2, the purpose of Assumption 1 is to ensure that the optimal Neyman variance is bounded away from zero.\nMore precisely, the Assumption guarantees that $V_N = \\Omega (1 / T)$ or on a normalized scale, $T \\cdot V_N = \\Omega(1)$.\nThis is important because without this assumption, it is impossible to construct a sequential experimental design that can achieve a comparable variance.\n\nTo illustrate this, consider the following example where Assumption 1 does not hold: for all units $i \\in [n]$, consider the outcomes\n\n$$\ny_t(1) = 1 \n\\quad \\text{and} \\quad\ny_t(0) = -1 \n\\enspace.\n$$\n\nHere, $\\rho = -1$ so that the outcomes are perfectly negatively correlated and thus Assumption 1 does not hold.\nNote that the average treatment effect is $\\tau = 2$.\nThe optimal Neyman design is to set $p^* = 1/2$.\nIn this case, the Horvitz--Thompson estimator is $\\hat{\\tau} = 2$ with probability 1 and thus the Neyman variance is zero, i.e. $V_N = 0$.\nThus, any sequential design which can select treatment probability $P_t \\neq 1/2$ at some time $t$ will have a positive variance, and thus unbounded Neyman ratio.\n\nThe construction above requires a somewhat pathological set of outcomes -- even a slight perturbation of the outcomes is enough to prevent such pathologies.\n We remark that Assumption 1 (or similar assumptions) are typically required for efficiently estimating variance and constructing confidence intervals.\nFor these reasons, experimenters are typically comfortable making assumptions like Assumption 1, which rule out pathological edge cases.\n\nThe fact that the same constant $c$ is used in both parts of the assumption is arbitrary: it can be replaced by two separate constants $c_1$ and $c_2$ and our analysis goes through by taking $c = \\min \\{ c_1, c_2 \\}$.\n\n## Question 3 --  Doubly Robust Estimation\n\n> Have you considered combining CLIP-OGD with an outcome model to get a doubly-robust estimator?\n\nThis is an excellent question!\nWe have not considered such extensions, but they sound very interesting.\nWe are not aware of doubly robust estimation in an adaptive design.\nA promising direction for future work!\n\n## Question 4 -- More Simulations\n\n> Can you add more simulations?\n\nThank you for encouraging us to increase the strength of our simulations.\nPlease see \"Global Response\" for our discussion on the results of a MAB baseline and additional new simulation results."}]

Author rebuttal:
# Global Response

We thank the five reviewers for their careful reading of our paper.
We are happy to see that that the reviews were overall positive.
Moreover, we are very grateful for the critiques and questions from reviewers that revealed certain weaknesses in our submission.
We believe that the paper has been greatly strengthed as a result of this feedback.

We respond to each reviewer individually, but we list the main themes of the revisions here:

- **Simulations**: More simulations have been added, including a comparison to EXP3 and Doubly Biased Coin Design (DBCD) and an investigation into the stability of Clip-OGD relative to the step size.
- **Interpretation of Results**: We add additional discussions interpreting the assumptions and elaborating on the derivation of the algorithm.
- **Literature Review**: The literature review has been expanded and there are more careful comparisons to related prior work.
- **Ethical Considerations**: We have drafted a new section in the appendix that discusses ethical considerations grounded in The Bellmont Report.

We elaborate on some of these points below.

## Simulations

We thank the reviewers for encouraging us to strengthen our simluation results.
We have added two additional baselines for our simulations: EXP3 algorithm for outcome regret minimization and the Doubly Biased Coin Design (DBCD), as described in Section 6 of Eisele (1994).
See Figure 2 in the attached pdf for their performance.
We find that they suffer from variance which is orders of magnitude larger than what is achieved by Clip-OGD and ETC.
This is perhaps unsurprising because these adaptive allocation mechanisms are designed for different purposes.
The problem of (variance minimizing) Adaptive Neyman Allocation is relatively understudied so that we are unaware of additional meaningful baselines other than ETC.
We are happy to include these additional comparisons in the revised paper.

In addition, we have tested the stability of Clip-OGD to the step size, which can be found in Figure 1 of the attached pdf.
We tried various step sizes of the form $\eta = c / \sqrt{T}$ for $c \in \{ 0.25, 0.5, 1.0, 2.0, 4.0 \}$.
The original Clip-OGD was only run with $c = 1$.
We find that smaller step sizes improve convergence rates, effectively removing the "overhead of adaptivity" in this example.
However, because the randomized experiment can only be run once, experimenters will typically not be able to try many step sizes.
While it remains an open question about how to select a step size which best mitigates the "overhead of adaptivity", our recommendation of $\eta = 1 / \sqrt{T}$ still maintains good convergence properties.

## Interpretation: Assumption 2

Several reviewers asked for additional interpretation behind Assumption 2, which we provide below.

The Neyman regret is a quantity who expectation compares the variance of an adaptive design to the optimal Bernoulli design.
We show that when using Clip-OGD, we can bound the expected Neyman regret by $\mathbb{E}[\mathcal{R}_T] \leq \tilde{\mathcal{O}}(\sqrt{T})$.
However, the expected Neyman regret could be *negative* if the adaptive design achieves variance which is strictly smaller than the best Bernoulli design.
This seems unlikely to happen for "typical" outcomes, but it is not impossible.
In fact, an adversary could construct outcomes on which the optimal Bernoulli design achieves a variance like $V_N = \Omega(1/T)$, while *Clip-OGD specifically* will achieve a variance with a better rate, i.e. $V = \mathcal{O}(1/T^2)$.
In this case, $\mathbb{E}[\mathcal{R}_T] \approx - T$.
Note that this does not contradict the original regret bound that $\mathbb{E}[\mathcal{R}_T] \leq \tilde{\mathcal{O}}(\sqrt{T})$.
Such an adversary would have to have detailed knowledge of the adaptive design and so this construction of outcomes seems like a pathological edge case.
It is exactly this pathological edge case that Assumption 2 rules out.

Assumption 2 is very likely to hold automatically in an i.i.d. setting precisely because the potential outcomes are drawn by a distribution independently of treatment assignment.
In particular, the potential outcomes cannot be chosen by an adversary with knowledge of the experimental design.
We suspect that Assumption 2 would not be necessary in an i.i.d. setting, but proving this seems beyond the scope of the current paper.

Meta-review: Under the potential outcomes model, the authors wish to estimate the average treatment effect of T trials (1/T) sum_{t=1}^T y_t(1) - y_t(0), where at each time t only y_t(Z_t) for Z_t=0 or Z_t=1 can be observed. By sampling Z_t ~ Bernoulli(p) one can obtain a consistent estimate as long as p in (0,1). While the most natural choice is p=1/2, some other value may have smaller variance based on the specific (a priori unknown) outcomes. If p* is this optimal mixing proportion, this paper considers an online setting where trials arrive sequentially t=1,2,… and the algorithm must decide some p_t in (0,1) to make the assignment. The objective is to compete with the optimal proportion p* in hindsight. While this problem definition is very simple and exceedingly natural, I myself (as well as the reviewers) are unaware of prior art that directly address this problem. Standard pure-exploration bandit algorithms, like most adaptive clinical trials, assume trials are IID and use adaptivity to maximize power. What is interesting is that this work drops this IID assumption. While I agree with some reviewers that it is not so surprising that one can compete with the best static allocation in hindsight, it is not at all obvious how one might achieve it. And moreover, there is great value in new problem statements that provide a new perspective on an old problem setting. The reviewers raised a number of questions and concerns, but nothing that was not appropriately addressed by the authors or warranted second-guessing.
Decision: Accept (spotlight)