Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
433,530 characters · 74 sections · 89 citation commands
Adaptive Neyman Allocation
\RUNAUTHOR
\RUNTITLE{Adaptive Neyman Allocation}
\TITLE{Adaptive Neyman Allocation}
\ARTICLEAUTHORS{ \AUTHOR{Jinglong Zhao}\AFF{Boston University, Questrom School of Business, Boston, MA, 02215, \EMAIL{[email removed]}} }
\ABSTRACT{ In the experimental design literature, Neyman allocation refers to the practice of allocating units into treated and control groups, potentially in unequal numbers proportional to their respective standard deviations, with the objective of minimizing the variance of the treatment effect estimator. This widely recognized approach increases statistical power in scenarios where the treated and control groups have different standard deviations, as is often the case in social experiments, clinical trials, marketing research, and online A/B testing. However, Neyman allocation cannot be implemented unless the standard deviations are known in advance. Fortunately, the multi-stage nature of the aforementioned applications allows the use of earlier stage observations to estimate the standard deviations, which further guide allocation decisions in later stages. In this paper, we introduce a competitive analysis framework to study this multi-stage experimental design problem. We propose a simple adaptive Neyman allocation algorithm, which almost matches the information-theoretic limit of conducting experiments. We provide theory for estimation and inference using data collected from our adaptive Neyman allocation algorithm. We demonstrate the effectiveness of our adaptive Neyman allocation algorithm using both online A/B testing data from a social media site and synthetic data. }
\HISTORY{\href{https://papers.ssrn.com/sol3/papers.cfm?abstract_id=4448249}{First draft: May 15, 2023.} This version: \today}
Why are randomized controlled experiments usually conducted with half treated and half control? One answer, dating back to neyman1934two, is that experimenters usually believe the treated and control groups to have the same level of variability. When the treated and control groups have different levels of variability, such as an intervention inducing heterogeneous responses or even polarization of the responses, the seminal work of neyman1934two recommends unequal allocation: the sizes of treated and control groups should be proportional to their respective standard deviations. This approach has later on been recognized as “Neyman allocation.”
Neyman allocation has many desirable properties. First, since it prescribes the sizes of the treated and control groups, it can be naturally combined with complete randomization cox2000theory, fisher1936design, imbens2015causal, wu2011experiments. Randomization then serves as the basis of validity for many randomized experiments cook2002experimental, deaton2018understanding. Second, it proves to minimize the variance of the widely used difference-in-means estimator, and increases the statistical power in scenarios where the the treated and control groups have different levels of variability neyman1934two. Consequently, it brings tremendous value to a wide range of applications whose treatment and control groups have different standard deviations, such as social experiments duflo2007using, karlan2008credit, mosleh2021shared, clinical trials berry2006bayesian, hu2003optimality, rosenberger2015randomization, marketing research rossi2003bayesian, sandor2001designing, and online A/B testing bakshy2014designing, deng2013improving, kohavi2017online. For example, at a social media site who compares two advertisement strategies, the standard deviation of the treated group is much smaller than that of the control group; see Figure (ref) for an illustration.
Albeit useful, a challenge in using Neyman allocation arises when the standard deviations of the treated and control groups are unknown in advance. Fortunately, the multi-stage nature of the aforementioned applications allows the use of earlier stage observations to estimate the standard deviations. If the earlier stage observations suggest a higher level of variability in one group, more experimental units will be allocated to the same group in the later stages, so that the confidence intervals of the average outcomes are roughly equal between the two groups. We refer to this approach as “adaptive Neyman allocation.”
In this paper, we study the optimal adaptive Neyman allocation problem.
To study this problem, we borrow the competitive analysis framework, a common optimization framework in the literature of decision making under uncertainty. This framework minimizes the worst case ratio between a proposed algorithm and an optimal algorithm endowed with clairvoyant information. This framework is scale-independent, ensuring that the ratio remains meaningful even on “hard instances” where both the proposed algorithm and the optimal algorithm perform poorly. To the best of our knowledge, we are the first to introduce the competitive analysis framework into experimental designs. In the single stage setup, an immediate implication of adopting this framework is that half-half allocations are optimal, without knowing the standard deviations of the treated and control groups, or any assumptions about these standard deviations. In the multi-stage setup, this framework allows for meaningful comparisons across different problem instances, even if the standard deviations of the treated and control groups are different. This is in contrast to the conventional minimax framework or the regret minimization framework, as the objective values in such frameworks will change under re-scaling of the standard deviations. To facilitate such comparisons, the minimax framework and the regret minimization framework need to assume the standard deviations being constants.
Another remarkable advantage of using the competitive analysis framework is that it facilitates a more precise examination of the second-order efficiency of experimental designs, which is different from the conventional emphasis on the first-order efficiency\footnote{First order efficiency in the context of experimental design is similar to semi-parametric efficiency in the context of observational study; see, e.g., hahn1998role, hirano2003efficient, robins1994estimation, robins1995semiparametric, scharfstein1999adjusting and textbooks ding2024first, imbens2015causal, wager2024causal.} such as in armstrong2022asymptotic and hahn2011adaptive. More specifically, when a total of $T$ experimental units are enrolled over $M \geq 2$ stages, the adaptive Neyman allocation algorithm in this paper achieves $1 + O\big(T^{-\frac{M-1}{M}}\big)$ competitiveness against a hindsight benchmark that knew the standard deviations in advance. In contrast, hahn2011adaptive show that when there are $M = 2$ stages and when the first stage pilot experiment involves approximately $T^\alpha$ units, any value of $\alpha < 1$ is first-order efficient. While two different parameterizations of $\alpha$ may both satisfy the first-order efficiency criterion, they can still lead to significantly different performances due to their second-order gap. A more precise examination of the second-order efficiency is useful in determining which parameterization of $\alpha$ is optimal.
Our work presents how to use the notion of second-order efficiency to choose the sample size for each stage in an adaptive Neyman allocation algorithm. In the $M = 2$ stage example above, the optimal sample size for the first stage pilot experiment should involve approximately $T^{\frac{1}{2}}$ units, i.e., $\alpha = \frac{1}{2}$. In general, in an $M$ stage experiment, the optimal sample size for the $m$-th stage should involve approximately $T^{\frac{m}{M}}$ units, leading to an exponentially increasing number of units in the later stages of the experiment. This exponentially increasing pattern may serve as a rule of thumb for practitioners who would like to conduct multi-stage experiments.
We also prove a novel information-theoretic $1 + O(T^{-1})$ competitive lower bound of conducting adaptive experiments. Recall that the competitive ratio of the aforementioned adaptive Neyman allocation algorithm is $1 + O\big(T^{-\frac{M-1}{M}}\big)$, which quickly approaches $1 + O(T^{-1})$ when the number of stages is large. Combining these two results, it shows that the adaptive Neyman allocation algorithm is second-order optimal when the number of stages is large. See Figure (ref) for an illustration. To the best of our knowledge, the best known result that studies the same question in the literature antos2010active, carpentier2011finite, grover2009active translates into a $1 + O\big(T^{-\frac{1}{2}}\big)$ ratio (see Section (ref) for details), and conjectures that this ratio is best possible. Our work negates this conjecture by improving this ratio.
Our work has two practical implications. First, conducting a two-stage or three-stage experiment can be sufficiently efficient as long as the sample size in each stage approximately follows an exponentially increasing pattern. Even though the two-stage or three-stage experiment is not optimal, having the ability to adaptively adjust the allocation of units based on insights from earlier stages can greatly improve efficiency. Second, if there is existing experimental data available, practitioners can use it as the first stage experiment to estimate the levels of variability from the treated and control groups, and guide the allocation of units in later stages.
This paper bridges four different fields of literature, listed alphabetically below. The subtle differences that distinguish these fields lie in the objective function and the underlying assumptions.
The paper is structured as follows. In Section (ref) we formally introduce adaptive Neyman allocation. In Section (ref) we introduce an optimization framework and show that the classical half-half allocation is optimal under this optimization framework. In Sections (ref) and (ref) we study the two-stage and multi-stage adaptive Neyman allocation problem, respectively. In Section (ref) we study estimation and inference using adaptively collected data. In Section (ref) we extend our high probability guarantees into in expectation guarantees. In Sections (ref) and (ref) we use online A/B testing data from a social media site and synthetic data to demonstrate the effectiveness of our adaptive Neyman allocation algorithm. In Section (ref) we conclude the paper and point out some limitations and future research directions. All mathematical details are deferred to the Online Appendix.
Consider the following problem. There is a discrete, finite time horizon of $T \in \mathbb{N}$ periods. The time horizon $T$ stands for the size of the experiment, and is known to the experimenter before the start of the horizon. At any time $t \in [T] := \{1,2,...,T\}$, one unit is involved in the experiment. We interchangeably use unit $t$ to stand for the unit that arrives at time $t$.
Let there be two versions of treatments. We use “treatment” and “control”, or $1$ and $0$, respectively, to stand for these two versions of treatments. Let $W_t \in \{0,1\}$ stand for the treatment assignment that unit $t$ receives. Following convention, we use $W_t$ for a random treatment assignment, and $w_t$ for one realization.
Following the potential outcomes framework and under the Stable Unit Treatment Value Assumption rubin1974estimating, holland1986statistics, imbens2015causal, each unit $t$ has a set of potential outcomes $Y_{t}(\cdot)$. Each observed outcome is related to its respective potential outcomes $Y_t = Y_t(w)$, if $W_t=w$. We assume the existence of a super-population abadie2020sampling, such that each unit's potential outcomes $(Y_t(1), Y_t(0))$ are independent and identically distributed (i.i.d.) replicas of a pair of representative random variables $(Y(1), Y(0))$. These random variables are drawn from a joint distribution of the super-population, i.e., $(Y(1), Y(0)) \sim \mathcal{F}$. We assume that $\mathcal{F}$ belongs to $\mathscr{P}$, the family of joint distributions where the first two moments exist. But we put no restrictions on the correlation between $Y(1)$ and $Y(0)$.
In this paper, we consider a multi-stage randomized experiment, which we refer to as “adaptive Neyman allocation.” The experiment is conducted in $M \in \mathbb{N}$ stages. In stage $m \in [M]$, the experimenter conducts a completely randomized experiment parameterized by $(T_m(1), T_m(0))$. The size of the stage-$m$ experiment is $T_m = T_m(1)+T_m(0)$, and the experimenter randomly chooses exactly $T_m(1)$ units to receive treatment, and exactly $T_m(0)$ units to receive control. After $M$ stages of experiments, the experimenter has assigned $T(1) = \sum_{m=1}^M T_m(1)$ units to receive treatment, and $T(0) = \sum_{m=1}^M T_m(0)$ units to receive control. See Table (ref) for a summary of notations.
Formally, a design of $M$-stage adaptive experiment is defined as $\pi = (\mathcal{T}_M, \phi_1, \phi_2, ..., \phi_T)$, where $\mathcal{T}_M = \{T_1, T_2, ..., T_M\}$ is a sequence of sample sizes in the $M$ stages, and $\phi_t$ is a decision rule that decides the treatment probability of unit $t$. Given $\mathcal{T}_M$, let $m(t) \in [M]$ be the index of the current stage that contains $t$. Let $\mathcal{H}(t) = \{(W_s, Y_s) \vert s \leq \sum_{l=1}^{m(t)-1} T_l\}$ be the history of unit $t$, that is, a collection of treatment assignments and observed outcomes up to the end of stage $m(t)-1$, where stage $0$ stands for an empty set. For each $t \in [T]$, $\phi_t: \mathcal{H}(t) \to [0,1]$ maps from the space of histories to the space of treatment probabilities, such that $\Pr(W_t = 1) = \phi_t(\mathcal{H}(t))$. Let $\Pi_M$ be the family of $M$-stage adaptive experiments. We have $\Pi_0 \subseteq \Pi_1 \subseteq ... \subseteq \Pi_T := \Pi$, where $\Pi_0$ stands for the family of non-adaptive experiments, and $\Pi$ stands for the family of fully adaptive experiments, or, simply, adaptive experiments.
The causal effect of interest is the average treatment effect of the super-population,
where the expectation is taken with respect to the joint distribution $\mathcal{F}$. After collecting data from the experiment, the experimenter uses the simple difference-in-means estimator to estimate the causal effect,
It is worth mentioning that $\widehat{\tau}$ may have two sources of randomness. The potential outcomes are random and the treatment assignments are also possibly random.
To evaluate the quality of the difference-in-means estimator, we consider the mean squared error of the estimator. When $T(1)$ and $T(0)$ are fixed, the difference-in-means estimator is unbiased and the mean squared error is equivalent to the variance of the estimator, which could be further expressed as follows,
where $\sigma(1), \sigma(0) > 0$ stand for the standard deviations of the two representative random variables $Y(1)$ and $Y(0)$, respectively. However, in an adaptive Neyman allocation algorithm, $T(1)$ and $T(0)$ are random in nature. The number of treated and control units are adaptively determined by the observed outcomes in the previous stages. Consequently, the mean squared error may not always have the same expression in (ref) as if $T(1)$ and $T(0)$ were fixed quantities.
In this paper, we re-define expression (ref) to be the proxy mean squared error,
The experimenter’s objective is then to minimize the proxy mean squared error as defined above. We will show in Theorem (ref) that, under appropriate allocation rules such as the adaptive Neyman allocation algorithms that we will introduce in this paper, the variance of estimator (ref) asymptotically converges to the proxy mean squared error (ref). So minimizing the proxy mean squared error (ref) can be interpreted as minimizing the variance of estimator (ref) when $T$ is large. See Section (ref) for more discussions.
One benefit of using the proxy mean squared error as our objective is that the proxy mean squared error only depends on $(T(1), T(0))$ the numbers of treated and control units in total. No matter how the experimenter adaptively chooses $(T_m(1), T_m(0))$ in each stage, the proxy mean squared error $V(T(1), T(0))$ is always well defined. The multi-stage experiment enables the experimenter to make better choices for $(T(1), T(0))$ by appropriately selecting $(T_m(1), T_m(0))$ at each stage. In the following section, we present an optimization framework for making such decisions.
If the experimenter was endowed with clairvoyant information about the standard deviations $\sigma(1)$ and $\sigma(0)$, the experimenter would allocate $(T(1), T(0))$ optimally in a single stage experiment to minimize $V(T(1), T(0))$. Note that we do not take expectation for $V(T(1), T(0))$ in a single stage experiment because $T(1)$ and $T(0)$ are fixed. The optimal solution can be explicitly calculated as,
and the optimal proxy mean squared error is given by the following expression,
This is what neyman1934two suggests, and has been recognized as the Neyman allocation. As the standard deviations were assumed given, the original work of Neyman allocation only focused on single stage experiments.
More often, the experimenter is not endowed with clairvoyant information about $\sigma(1)$ and $\sigma(0)$. To solve this decision making under uncertainty problem, we introduce the competitive analysis framework to experimental design. For any design $\pi \in \Pi$, let $(T^\pi(1), T^\pi(0))$ be the numbers of treated and control units assigned by policy $\pi$. The competitive analysis framework suggests to solve the following problem,
The optimal value to problem (ref) is often referred to as the competitive ratio borodin2005online, buchbinder2009design.
The above competitive analysis framework is similar to the minimax decision rule berger2013statistical, bickel2015mathematical, li1983minimaxity, wu1981robustness, which solves
as well as the minimax regret decision rule lai1985asymptotically, manski2004statistical, robbins1952some, stoye2009minimax, which solves
But the above two decision rules are not directly applicable in our work because both objective values scale with the magnitudes of the potential outcomes or the variances. Consequently, the active learning literature assumes that $\sigma(1)$ and $\sigma(0)$ are constants antos2010active, carpentier2011finite, grover2009active. Under this assumption, $V(T^*(1), T^*(0)) = \Theta(T^{-1})$. So any regret minimization result on the order of $O\big(T^{-1-\alpha}\big)$ corresponds to a competitive ratio result on the order of $1+O\big(T^{-\alpha}\big)$.
To illustrate the competitive analysis framework, consider the setup of the traditional single stage Neyman allocation, but with unknown standard deviations. In the single stage experiment, the policy $\pi$ only determines one single and fixed pair of $(T(1), T(0))$. We replace the policy $\pi$ with this pair of actions $(T(1), T(0))$ in (ref), and solve the new problem to optimal. This yields the following result, the proof of which is deferred to Section (ref) in the Online Appendix.
Theorem (ref) reproduces the classical result that the optimal design involves an equal number of treated and control units neyman1934two. But Theorem (ref) does not require any knowledge of the standard deviations of the treatment or control populations. More importantly, Theorem (ref) does not even require any assumption about the data generating process, such as the treatment or control populations having the same support (see, e.g., bojinov2023design, ni2023design), or the treatment effects being additive, which implies that the standard deviations are the same (see, e.g., xiong2019optimal), or permutation invariance (see, e.g., bai2023randomize, basse2023minimax, wu1981robustness).
In other experimental design literature, Theorem (ref) is often presented as an assumption and serves as the basis for designing optimal experiments bai2022optimality, candogan2021near, greevy2004optimal, harshaw2019balancing, lu2011optimal, rosenbaum1989optimal, xiong2019optimal, zhao2022pigeonhole. In contrast, by using the competitive analysis framework, Theorem (ref) establishes the credibility of such an assumption.
In the following sections, we will use this competitive analysis framework to study adaptive Neyman allocation. We will start with the two-stage adaptive Neyman allocation to introduce the basic estimation ideas and build some intuitions in Section (ref). We will then introduce the more general multi-stage adaptive Neyman allocation in Section (ref).
In this section, we focus on the $M=2$ case, which we refer to as the two-stage adaptive Neyman allocation. When there are two stages, the experimental data collected during the first stage reveals information about the magnitudes of $\sigma(1)$ and $\sigma(0)$, which can be used to guide the design of the second stage experiment.
Recall that $(T_1(1), T_1(0))$ stand for the numbers of treated and control units in the first stage, respectively, and that $T_1 = T_1(1) + T_1(0)$ stands for the total number of units in the first stage. We consider the following sample variance estimators at the end of the first stage,
After obtaining the sample variance estimators, it is natural to use such sample variance estimators to guide the Neyman allocation in the second stage. The allocation of treated and control units should roughly follow the ones suggested by (ref), but the estimated standard deviations from the first stage will be used instead of the true standard deviations, i.e.\footnote{When $\widehat{\sigma}(1) = \widehat{\sigma}(0) = 0$, we abuse the notation and denote $\frac{0}{0+0} = \frac{1}{2}$.},
Based on this natural intuition, we define the two-stage adaptive Neyman allocation in Algorithm (ref).
In words, the experiment consists of two stages. In the first stage, the experiment has a total size of $\sqrt{T}$, and assigns half units to treated and the other half to control. Then we calculate the sample variance estimators $\widehat{\sigma}^2_1(1)$ and $\widehat{\sigma}^2_1(0)$. If neither $\widehat{\sigma}_1(1)$ or $\widehat{\sigma}_1(0)$ is too small, the second stage experiment roughly mimics the Neyman allocation by using the estimated variances. If $\widehat{\sigma}_1(1)$ or $\widehat{\sigma}_1(0)$ is too small, the second stage experiment assigns all units to control or treated, respectively.
In essence, the two-stage adaptive Neyman allocation is similar to the design in hahn2011adaptive. But there are two differences. First and more importantly, we specify the optimal size for the first-stage experiment. Second, we use equation (ref) to guide the allocation of treated and control units for the entire horizon; whereas hahn2011adaptive uses equation (ref) to guide the allocation for the second stage.
We now present a formal analysis about the quality of the two-stage adaptive Neyman allocation. Recall that the sample variance estimators are unbiased, i.e., $\mathrm{E}[\widehat{\sigma}^2_1(1)] = \sigma^2(1)$ and $\mathrm{E}[\widehat{\sigma}^2_1(0)] = \sigma^2(0)$. To ensure that the distributions of the sample variance estimators are concentrated enough around the true variances $\sigma^2(1)$ and $\sigma^2(0)$, we make the following assumption.
Assumption (ref) asserts that the representative random variables $Y(1), Y(0)$ are sufficiently light-tailed, in the sense that their respective kurtosis values $\kappa(1), \kappa(0)$ exist. It is worth noting that the kurtosis values are always greater than $1$, i.e., $\kappa(1), \kappa(0) > 1$. For a Gaussian random variable $Z$, its kurtosis is equal to $3$, i.e., $\mathrm{E}\left[(Z - \mathrm{E} Z)^4\right] / \sigma^4(Z) = 3$. The kurtosis will be larger for distributions with heavier tails, and smaller for those with lighter tails. In other papers, instead of assuming Assumption (ref), either sub-Gaussianity or boundedness is often assumed lattimore2020bandit, slivkins2019introduction. Let $\mathscr{P}^{[\kappa]}$ be the family of joint distributions that satisfies Assumption (ref).
With the above assumption, we now show the quality of the two-stage adaptive Neyman allocation, as measured by the competitive ratio, in Theorem (ref).
Theorem (ref) presents a high probability bound. Using an assumption that enables us to show exponentially small probability, we will be able to show that a similar bound (up to some logarithm factors) holds in expectation. See Corollary (ref) in Section (ref).
Results that study the quality of adaptive allocation policies also frequently appear in the active learning literature antos2010active, carpentier2011finite, grover2009active, russac2021b. This literature adopts a minimax regret framework, which differs from the competitive analysis framework. The minimax regret framework focuses on the difference between the variance of any policy and the optimal variance, rather than the ratio between them. As the magnitudes of $\sigma(1)$ and $\sigma(0)$ directly impact the objective value, the minimax regret framework typically assumes $\sigma(1)$ and $\sigma(0)$ are constants and that they are on the same order. In contrast, this paper allows $\sigma(1)$ and $\sigma(0)$ to differ significantly, with one potentially much larger than the other. After translating into the framework of this paper, the best competitive ratio suggested by the literature is on the order of $1 + O(T^{-\frac{1}{2}})$, using much more complicated and fully adaptive experimental designs such as upper confidence bound approaches. In contrast, Theorem (ref) shows that a simple two-stage adaptive Neyman allocation can achieve the same competitive ratio, by adapting only once.
In Section (ref), we will show that conducting experiments in more than two stages can improve the competitive ratio, to an extent that almost matches the information-theoretic limit of conducting adaptive experiments.
To conclude this section, we sketch some unrigorous intuitions behind the proof of Theorem (ref) below, and defer the complete proof to Section (ref) in the Online Appendix.
\proof{Sketch proof of Theorem (ref).} Denote $\rho = \frac{\sigma(1)}{\sigma(0)}$. Without loss of generality assume $\rho \geq 1$. Suppose the length of the first stage is parameterized by $T^\alpha$ (we ignore $\beta$ in this unrigorous sketch proof). We aim to find the optimal length $T^\alpha$ of the first stage.
Case 1: $\rho > \frac{T - T^{\alpha}}{T^{\alpha}}$. Then with high probability, the first stage reveals this condition and Algorithm (ref) stops allocating units to the control group in the second stage. In this case, we will show that
Case $2$: $1 \leq \rho \leq \frac{T - T^{\alpha}}{T^{\alpha}}$. Then with high probability, the first stage reveals this condition and Algorithm (ref) mimics the Neyman allocation by using the estimated variances. In this case, the estimation errors of estimating $\sigma(1)$ and $\sigma(0)$ are on the order of $T^{-\frac{\alpha}{2}}$. So the estimation error of estimating $\rho$ is on the order of $T^{-\alpha}$. We will show that
Combining both cases, we set $\alpha-1 = -\alpha$ and obtain $\alpha = \frac{1}{2}$, which leads to competitive ratio $\frac{V(T(1), T(0))}{V(T^*(1), T^*(0))} \approx 1 + T^{-\frac{1}{2}}.$ \halmos \endproof
This section presents an extension of the two-stage adaptive Neyman allocation to multiple stages. We provide a formal analysis of the competitive ratio of the multi-stage adaptive Neyman allocation, and show that such a competitive ratio is nearly optimal.
The multi-stage adaptive Neyman allocation algorithm uses the following sample variance estimators at the end of each stage. Recall that $(T_m(1), T_m(0))$ stand for the numbers of treated and control units in stage $m$, respectively, and that $T_m = T_m(1) + T_m(0)$ stands for the total number of units in stage $m$. At the end of stage $m$, define the following sample variance estimators,
Using the above sample variance estimators (ref) and (ref), we could update the allocation of treated and control units following the Neyman allocation, i.e.,
We can update the above Neyman allocation as defined in (ref) using the estimated variances at the end of each stage $m$. Using (ref) we define the $M$-stage adaptive Neyman allocation. See Algorithm (ref) for Pseudo-codes.
The $M$-stage adaptive Neyman allocation generalizes the idea of two-stage adaptive Neyman allocation: we use the observations in the earlier stages to estimate the variances, and use the estimated variances to guide the allocation in the later stages. Initially, an equal number of treated and control units are allocated in the first stage. At the end of each stage, sample variances are estimated using (ref) and (ref), and the number of treated and control units is determined using the Neyman allocation formula, as shown in (ref).
There are three major cases that will happen. First, the estimated standard deviations $\widehat{\sigma}_m(1)$ and $\widehat{\sigma}_m(0)$ indicate that there is already an excessive allocation to either the treated or control group by the end of stage $m$. In this case, we immediately stop allocating units to that group in the subsequent stages. See Case 1 (Line (ref)) and Case 5 (Line (ref)) in Algorithm (ref). Intuitively, we are pruning the corner cases: once we have used a small number of stages to identify that the standard deviation $\sigma(1)$ or $\sigma(0)$ is very small, we stop allocating units to that group.
Second, the estimated standard deviations $\widehat{\sigma}_m(1)$ and $\widehat{\sigma}_m(0)$ indicate that we have not allocated too many units to both groups by the end of stage $m$, but an equal allocation in the next stage $(m+1)$ would result in an excessive allocation to either the treated or control group. In this case, we follow the Neyman allocation in the next stage $(m+1)$ only. We then stop allocating units to that treated or control group in the subsequent stages after the next stage. See Case 2 (Line (ref)) and Case 4 (Line (ref)) in Algorithm (ref). This is the non-trivial generalization from Algorithm (ref) in the two-stage adaptive Neyman allocation. Intuitively, we are pruning the corner cases as early as possible: now that we have identified that the standard deviation $\sigma(1)$ or $\sigma(0)$ is small enough, we do not spend an extra stage to allocate more units than necessary and convince ourselves that they are small. Instead, we follow the Neyman allocation in the next stage, and, without even updating the estimators $\widehat{\sigma}_{m+1}(1)$ and $\widehat{\sigma}_{m+1}(0)$, directly stop allocating future units to that group.
Third, the estimated standard deviations $\widehat{\sigma}_m(1)$ and $\widehat{\sigma}_m(0)$ indicate that even with an equal allocation in the next stage, we will not have allocated too many units to both groups. In this case, we keep an equal allocation in the next stage. See Case 3 (Line (ref)) in Algorithm (ref). Intuitively, we have not identified a significant difference between the standard deviation $\sigma(1)$ or $\sigma(0)$, so we keep a balanced exploration. After collecting data from the next stage, the above procedure is repeated.
Such a simple idea leads to an effective improvement over the two-stage adaptive Neyman allocation. We show the quality of the multi-stage adaptive Neyman allocation, as measured by the competitive ratio, in Theorem (ref) below.
Theorem (ref) presents a high probability bound. Using an assumption that enables us to show exponentially small probability, we will be able to show that a similar bound (up to some logarithm factors) holds in expectation. See Corollary (ref) in Section (ref). This result improves the best existing results in the literature antos2010active, carpentier2011finite, grover2009active, and negates the conjecture that the competitive ratio is lower bounded by $1 + \Omega(T^{-\frac{1}{2}})$. We sketch some unrigorous intuitions behind the proof of Theorem (ref) below. The proof borrows ideas from perchet2016batched. We defer the complete proof to Section (ref) in the Online Appendix.
\proof{Sketch proof of Theorem (ref).} Denote $\rho = \frac{\sigma(1)}{\sigma(0)}$. Without loss of generality assume $\rho \geq 1$. Suppose there are $(M-1)$ constants $0 \leq \alpha_1 \leq \alpha_2 \leq \ldots \leq \alpha_{M-1} \leq 1$, such that we can choose the lengths of the $M$ stages to be roughly in the following order: $[0,T^{\alpha_1}]$, $(T^{\alpha_1}, T^{\alpha_2}]$, ..., $(T^{\alpha_{M-1}}, T]$.
Case 1: $\rho > \frac{T - T^{\alpha_1}}{T^{\alpha_1}}$. Then with high probability, the first stage reveals this condition and the algorithm stops allocating units to the control group from the second stage. In this case, we will show that
Case $m$ $(2 \leq m \leq M-1)$: $\frac{T - T^{\alpha_{m}}}{T^{\alpha_{m}}} < \rho \leq \frac{T - T^{\alpha_{m-1}}}{T^{\alpha_{m-1}}}$. Then with high probability, this condition is not revealed until the end of the $(m-1)$-th stage. Once this condition is revealed, the algorithm allocates a few units to the control group in the $m$-th stage, and stops allocating units to the control group from the $(m+1)$-th stage. In this case, the estimation errors of estimating $\sigma(1)$ and $\sigma(0)$ are on the order of $T^{-\frac{\alpha_{m-1}}{2}}$. So the estimation error of estimating $\rho$ is on the order of $T^{-\alpha_{m-1}}$. We will show that
Case $M$: $1 \leq \rho \leq \frac{T - T^{\alpha_{M-1}}}{T^{\alpha_{M-1}}}$. Then with high probability, this condition is not revealed until the end of the $(M-1)$-th stage. In the last stage, the algorithm mimics Neyman allocation by using the estimated variances. In this case, the estimation errors of estimating $\sigma(1)$ and $\sigma(0)$ are on the order of $T^{-\frac{\alpha_{M-1}}{2}}$. So the estimation error of estimating $\rho$ is on the order of $T^{-\alpha_{M-1}}$. We will show that
Combining all cases, we solve
and obtain $\alpha_m = \frac{m}{M}$, which leads to a competitive ratio $\frac{V(T(1), T(0))}{V(T^*(1), T^*(0))} \approx 1 + T^{-\frac{M-1}{M}}.$ \halmos \endproof
Next, we present an information-theoretic limit of such experiments, as measured by the competitive ratio, in Theorem (ref) below.
We sketch some unrigorous intuitions behind the proof of Theorem (ref) as follows, and defer the complete information-theoretic proof of Theorem (ref) to Section (ref) in the Online Appendix.
\proof{Sketch proof of Theorem (ref).} To prove Theorem (ref), we construct two probability distributions $\nu$ and $\nu'$ that are challenging to distinguish. Intuitively, we know that $Y(0)$ and $Y(1)$ follow $\nu$ and $\nu'$, but it is challenging to distinguish which outcome corresponds to which distribution.
Now define $\varepsilon = \frac{1}{3T^{\frac{1}{2}}}.$ Both distributions have three discrete supports $\{-1,0,1\}$. The probability mass for distribution $\nu$ is given by
The probability mass for distribution $\nu'$ is given by
Then we bound the KL-divergences of these two probability distributions,
Intuitively, it is challenging to distinguish the above two probability distributions within $T$ rounds. This means that, any policy can not distinguish the above two probability distributions until the end of horizon. Since the two probability distributions are not distinguishable, the best policy in this situation has to follow the half-half allocation, which leads to a competitive ratio of $\frac{\mathrm{E}[V(T^\pi(1), T^\pi(0))]}{V(T^*(1), T^*(0))} \approx 1 + T^{-1}.$ \halmos \endproof
By comparing Theorems (ref) and (ref), we see that when the number of stages $M$ is large, the two results are close to each other. When there are $\log(T)$ many stages, the two results almost match with each other, suggesting that the multi-stage adaptive Neyman allocation is the optimal design of experiments, whose competitive ratio almost matches the information-theoretic limit of conducting adaptive experiments.
In this section, we establish estimation and inference results using data collected via our adaptive Neyman allocation algorithms. Generally speaking, analyzing data collected by adaptive experiments could be challenging. However, our proposed adaptive Neyman allocation algorithms enjoy the key property of adapting on the sample variance, not on the sample mean. This property makes estimation and inference easy. The estimation result in this section borrows ideas from xiong2019optimal, and the inference result in this section borrows ideas from chen2025characterization, khamaru2024inference.
We start with establishing an unbiased estimation result that holds in finite sample. Recall that the pair of potential outcomes $(Y(1), Y(0)) \sim \mathcal{F}$ is sampled from the joint distribution $\mathcal{F}$. We show that the difference-in-means estimator is unbiased, as long as distribution $\mathcal{F}$ satisfies Assumption (ref) below. Assumption (ref) borrows ideas from xiong2019optimal, who study a similar assumption and show unbiasedness of least squares estimators.
The symmetric distribution is satisfied by many families of distributions, such as the family of joint normal distributions. Intuitively, because the family of joint normal distributions is symmetric and has two parameters, adapting to the sample variance does not bias the mean estimation. On the other hand, Assumption (ref) does not hold for the family of Bernoulli distributions. The family of Bernoulli distributions is generally not symmetric and has only one single parameter, and adapting to the estimated variance biases the mean estimation. We provide a simplified toy example below to illustrate the intuitions.
We formalize the intuitions built in Example (ref) into the following theorem.
We prove Theorem (ref) in Section (ref) in the Online Appendix. It is worth noting that Theorem (ref) is a non-asymptotic result. This non-asymptotic nature is unique to our adaptive Neyman allocation algorithms, which adapts on the sample variance but not the sample mean. It is different from the traditional adaptive experiments literature, where the unbiasedness property usually requires the sample size $T$ to be large bowden2017unbiased, chen2025characterization, hadad2021confidence, hirano2023asymptotic, khamaru2024inference, melfi2000estimation, nie2018adaptively, offer2021adaptive, shin2019bias, shin2019sample, zhan2021off, zhan2023policy, zhang2020inference, zhang2021statistical. In what follows, we provide a standard asymptotic result that does not require Assumption (ref) but requires the sample size $T$ to be large.
Now we turn our attention to inference when the sample size $T$ is large. Making inference for adaptively collected data is an active literature. As long as some notion of “stability condition” holds, one can establish central limit theorems for the sample means chen2025characterization, khamaru2024inference, melfi2000estimation. We borrow this technique and provide a central limit theorem that allows us to construct confidence intervals under asymptotic normality.
We can use Theorem (ref) to construct confidence intervals using any consistent estimator of the true variance. It turns out that the sample variance estimators using all the data,
are consistent in estimating the true variances $\sigma^2(1)$ and $\sigma^2(0)$. This consistency result follows arguments similar to those in melfi2000estimation, shin2019bias, khamaru2024inference, and is a consequence of the law of large numbers.
Combining Theorem (ref) and Proposition (ref), we can construct the classical asymptotically valid $1-\alpha$ confidence interval as follows,
where $z_{1-\frac{\alpha}{2}}$ is the $1-\frac{\alpha}{2}$ quantile of the standard normal distribution.
We sketch the intuitions behind the proof of Theorem (ref) as follows, and defer the complete proof of Theorem (ref) to Section (ref) in the Online Appendix. The proof of Proposition (ref) is simple, and we defer the self-contained proof to Section (ref) in the Online Appendix.
\proof{Sketch proof of Theorem (ref).} The proof of Theorem (ref) relies on a standard martingale central limit theorem. To appropriately apply the martingale central limit theorem, we will identify the martingale sequence. Apparently, the following sequence of (re-centered) sample mean estimators
is not a martingale sequence, because the denominator $T(1)$ is a random variable. To overcome this issue, note that under our adaptive Neyman allocation algorithms, the denominator $T(1)$ converges to a deterministic quantity $T^*(1)$ in probability, that is, $T(1) \xrightarrow{p} T^*(1)$ as $T \to +\infty$. Consequently,
as $T \to +\infty$. We can now show that the sequence
is a martingale sequence, and establish a martingale central limit theorem. \halmos \endproof
In the above sketch proof, the condition that there exists a deterministic quantity $T^*(1)$ such that $T(1) \xrightarrow{p} T^*(1)$ is referred to as the stability condition in chen2025characterization, khamaru2024inference. This stability condition is naturally satisfied by our adaptive Neyman allocation algorithms.
First, Theorem (ref) is an asymptotic result that requires $T$ to be large, but does not require Assumption (ref). An immediate implication of Theorem (ref) is that the difference-in-means estimator is asymptotically unbiased. This is in contrast to Theorem (ref) which suggests that the difference-in-means estimator is unbiased in finite sample but requires Assumption (ref).
Second, recall from Section (ref) that the objective function of our adaptive Neyman allocation algorithms is the proxy mean squared error, which is not equal to the variance of the difference-in-means estimator (ref) because the data is adaptively collected. But Theorem (ref) implies that using this proxy is a reasonable idea. More specifically, Theorem (ref) implies that the difference-in-means estimator (ref) using adaptively collected data has an asymptotic variance of
which is exactly the same expression as the proxy mean squared error (ref).
The fact that the proxy mean squared error (ref) is not equal to the variance of estimator (ref) in finite sample has been well recognized in the literature across three different fields: the active learning literature where people directly use the proxy mean squared error as an objective function antos2010active, carpentier2011finite, grover2009active, the experimental design literature where people analyze adaptively collected data chen2025characterization, hahn2011adaptive, hirano2023asymptotic, khamaru2024inference, li2024double, nie2018adaptively, offer2021adaptive, shin2019bias, shin2019sample, zhang2020inference, zhang2021statistical, and the simulations literature where people discuss the bias in estimating confidence intervals ross2013simulation. Theorem (ref) aligns with the same message from hahn2011adaptive, li2024double that, under properly designed adaptive Neyman allocation algorithms, the variance of estimator (ref) converges to the proxy mean squared error asymptotically. We conduct simulations in Section (ref) to verify that the gap between these two quantities is small. However, the magnitude of the non-asymptotic gap between these two quantities remains unknown, which we discuss as a future research direction in Section (ref).
In the previous sections, we have seen that Theorems (ref) and (ref) provide high probability bounds for the competitive ratios of using adaptive Neyman allocation. But with low probability, the competitive ratios might be much larger. In this section, we show that similar bounds as in Theorems (ref) and (ref) still hold in expectation.
We will need a stronger assumption to show that the low probability events happen with exponentially small probability. But this stronger assumption is still weaker than the standard modeling assumptions that commonly appear in the active learning literature, where existing works assume that both the standard deviations and the supports are bounded antos2010active, carpentier2011finite, grover2009active.
Assumption (ref) asserts that the representative random variables $Y(1), Y(0)$ have bounded supports that depend on the variances. In contrast, the traditional literature sometimes assumes that the bounded support is between $[0,1]$, and that the variances are constants. To illustrate Assumption (ref), consider the following example. Consider a three-point distribution $Y$, such that with probability $1-2p$, $Y=0$; with probability $p$, $Y=1$; and with probability $p$, $Y=-1$. In this example, $\vert Y \vert \leq 1$ and $\sigma(Y) = \sqrt{2p}$. If $\lim_{T \to +\infty} p \to 0$, Assumption (ref) does not hold. On the other hand, if $p$ is a constant, Assumption (ref) holds. For example, if $p = \frac{1}{3}$, then Assumption (ref) holds with constant $C = \sqrt{\frac{3}{2}}$. Let $\mathscr{P}^{[C]}$ be the family of joint distributions that satisfies Assumption (ref).
Under Assumption (ref), we are able to show Corollary (ref) as an extension of Theorem (ref), and Corollary (ref) as an extension of Theorem (ref).
In this section, we conduct simulations using online A/B testing data from a social media site AB_testing_kaggle. We combine this online A/B testing data with a resampling process which generates the sequence of experiments. Following each trajectory of the generated sequence, we calculate the difference-in-means estimator as in (ref) under the adaptive Neyman allocation and the half-half allocation, respectively. By drawing different trajectories from the resampling process, we are able to compare the adaptive Neyman allocation and the half-half allocation. Overall, the simulation suggests a $\sim 10\%$ reduction in the variance. We describe the details below.
This social media site has conducted an online A/B test to compare two advertisement strategies, which they refer to as the average bidding strategy and the maximum bidding strategy. The true label of treatment and control is masked from the data. We only know that they refer to two different advertisement strategies: average bidding and maximum bidding. This social media site is interested in understanding which bidding strategy generates more conversion, that is, user clicks.
Unlike traditional user click data which documents the binary user click records from one single experiment, this data set documents a total of $80$ experiments, $40$ treated and $40$ control. Each experiment is stored in one row, which documents aggregate data of the number of impressions (one impression refers to one view of the advertisement) and the number of clicks. We normalize the number of clicks by the number of impressions, and use the number of clicks per million impressions as the unit of measurement. We denote the numbers of clicks from these two groups as $\mathcal{Y}(1)$ and $\mathcal{Y}(0)$, respectively. See Table (ref) for the summary statistics of these two groups.
Since the data does not show us the sequence of experiments, we use a resampling process to generate the sequence. In the resampling process, we consider $T = 1000$. For each $t \in [T]$, we generate the potential outcomes $Y_t(1)$ and $Y_t(0)$ by sampling from the two groups $\mathcal{Y}(1)$ and $\mathcal{Y}(0)$ with replacement. We refer to the data generated above as one trajectory, and following each trajectory we calculate the difference-in-means estimator (ref) under different experients. By drawing a total of $1,000,000$ different trajectories, we obtain the distributions of the same difference-in-means estimator and compare the performances across different experiments.
Since we generate the potential outcomes, we can calculate the average treatment effect of the super-population as $\tau = \mathrm{E}[Y(1) - Y(0)] = -19442$, where the expectation is taken over the resampling process.
We consider the following three designs of experiments.
For each design, we conduct the experiment and calculate the difference-in-means estimator $\widehat{\tau}$. We compare the variances of the estimators in Figure (ref) and compare the distributions of the estimators in Figure (ref). Note that, there are two sources of randomness in Figures (ref) and (ref). First, the resampling process draws random samples when generating the potential outcomes; second, the experiments are randomized experiments when determining the treatment assignments.
In Figure (ref), we simulate the variances of the estimator $\widehat{\tau}$. Figure (ref) shows a significant reduction in variance when increasing the number of stages from $M=1$ to $M=2$. However, the marginal benefit of increasing the number of stages from $M=2$ to $M=3$ is substantially smaller. Further increasing the number of stages beyond this point leads to negligible improvements or even a slight increase in variance. We recommend using a small value for $M$, such as $2$ or $3$, to have the best the numerical performance.
In Figure (ref), we simulate the distributions of $\widehat{\tau} - \tau$, the difference-in-means estimator subtracted by the average treatment effect of the super-population. The vertical dashed lines indicate the mean of each distribution, while the solid curves represent the respective kernel density estimates. As shown in Figure (ref), the three dashed lines are virtually indistinguishable at zero, suggesting that all three estimators are unbiased. Furthermore, the blue and green density curves almost coincide, and both of them are taller than the red density curve. They suggest that the two stage and three stage adaptive Neyman allocation algorithms have similar performances, and both of them outperform the half-half allocation benchmark.
Our simulations in Figures (ref) and (ref) suggest that, on this user click data from a social media site, adaptive Neyman allocation leads to a $\sim 10\%$ reduction in variance compared to half-half allocations. This will lead to faster business decisions as the experimenter would require less samples to draw the same causal conclusion.
In this section, we conduct extensive simulations using synthetic data. The main purposes of this section are two fold. First, we compare the performances of the adaptive Neyman allocation algorithms we propose in this paper with a series of benchmarks in the literature. Second, we numerically study the gap between the proxy mean squared error (ref) and the variance of estimator (ref) when the sample size is relatively small.
We change the values of $T$ from $\{100, 200, ..., 1000\}$. For each $t \in [T]$, we set the potential outcomes $Y_t(1)$ and $Y_t(0)$ to be independent normal $\mathcal{N}(1,\sigma^2(1))$ and $\mathcal{N}(0,1)$ random variables, respectively, where we set $\sigma(1) = 5$. We also study other values of $\sigma(1)$ in Section (ref).
We study the performances of eight algorithms that fall into the six types below. For each algorithm, we normalize the mean squared error by the theoretical value of the mean squared error under optimal allocation, which is derived in (ref). Such a normalization enables us to focus on the relative performance of the eight algorithms.
We first compare the performances of the above eight algorithms and report their mean squared errors in Figure (ref). As we see from Figure (ref), the normalized mean square error of the optimal Neyman allocation stays at $1$, suggesting that the simulation performance of the optimal Neyman allocation closely mimics the theoretical calculation of expression (ref). The normalized mean square error of half-half allocation, on the other hand, stays at the theoretical calculation of $\frac{2(\sigma^2(1)+\sigma^2(0))}{(\sigma(1)+\sigma(0))^2} \approx 1.44$, and does not change as $T$ changes. The two adaptive Neyman allocation algorithms as we proposed in Theorems (ref) and (ref) perform well, with the three-stage adaptive Neyman allocation algorithm slightly outperforming the two-stage one. The two sample-discarding variants of batched Neyman allocation algorithm perform worse than the adaptive Neyman allocation algorithms, because they do not fully utilize all the samples. The three-stage sample-discarding algorithm performs even worse, because it discards even more samples, on the order of $T^{\frac{2}{3}}$, than compared with the two-stage algorithm. The doubly adaptive biased coin design has the best performance. This is not surprising because this algorithm is fully adaptive, whereas the adaptive Neyman allocation algorithms run in batches. Finally, the upper confidence bound algorithm performs worse than the adaptive Neyman allocation algorithms. This is probably because elimination-based algorithms, which are the algorithmic ideas behind our adaptive Neyman allocation algorithms, outperform the upper confidence bound algorithm when the sub-optimal treatment is easy to identify, which is the case in our simulation when $\sigma(1)=5$. In Section (ref) in the Online Appendix, we will see that the upper confidence bound algorithm performs better when $\sigma(1)=1$.
We also report the proxy mean squared errors as defined in (ref) in Figure (ref). In this comparison, we omit the two curves of the sample-discarding algorithms because they are not defined for the proxy mean squared error. Among the remaining six algorithms, the proxy mean squared error serves as the objective function of both the adaptive Neyman allocation algorithms and the upper confidence bound algorithm. The performances of the six algorithms follow the same pattern as we have observed in Figure (ref).
In this simulation, we focus on the following three quantities: the proxy mean squared error $\mathrm{E}[V(T(1),T(0))]$ as in (ref), the variance of estimator (ref), $\mathrm{Var}(\widehat{\tau})$, and the mean squared error of estimator (ref), $\mathrm{E}\left[(\widehat{\tau} - \tau)^2\right]$. We conduct the simulation under two cases when $M=2$ and $M=3$.
We report the simulation results in Figure (ref). First, we compare the variance of estimator (ref), $\mathrm{Var}(\widehat{\tau})$, and the mean squared error of estimator (ref), $\mathrm{E}\left[(\widehat{\tau} - \tau)^2\right]$. They seem indistinguishable in this figure. This is partly because we generate the potential outcomes from normal distributions, which satisfies Assumption (ref). So the estimator (ref) is unbiased. Second, we compare the proxy mean squared error $\mathrm{E}[V(T(1),T(0))]$ with $\mathrm{Var}(\widehat{\tau})$ and $\mathrm{E}[(\widehat{\tau} - \tau)^2]$. The gap between the proxy mean squared error $\mathrm{E}[V(T(1),T(0))]$ and $\mathrm{Var}(\widehat{\tau})$ or $\mathrm{E}[(\widehat{\tau} - \tau)^2]$ seems to be small. Third, the proxy mean squared error $\mathrm{E}[V(T(1),T(0))]$ is relatively stable compared with $\mathrm{Var}(\widehat{\tau})$ or $\mathrm{E}[(\widehat{\tau} - \tau)^2]$.
In this paper, we present a competitive analysis framework to study the optimal multi-stage experimental design problem. We propose an adaptive Neyman allocation algorithm that is nearly optimal and almost matches the information-theoretic limit of conducting experiments. Our algorithm allows for efficient allocation of units into treated and control groups in multi-stage experiments, and can guide researchers towards the best allocation decisions when standard deviations are unknown in advance. Overall, our approach offers a solution for researchers seeking to optimize their experimental designs and increase statistical power, particularly in cases where the treated and control groups have different standard deviations, such as in social experiments, clinical trials, marketing research, and online A/B testing.
We conclude this paper with three potential limitations that should serve as cautionary notes for practitioners. First, while adaptive Neyman allocation as described in this paper is suitable for sequential experimental design with a limited sample size, it still requires a minimum amount of sample size on the scale of at least several hundreds, to have reasonable performance. In cases where a social experiment only involves a very small number of units, such as $\sim 30$ districts in a developing economy gibson2023redesigning, and especially when there is a constraint that limits the size of the treated group to be only $2$ or $3$, we do not recommend the usage of adaptive Neyman allocation, or any randomized experiment design method. Instead, we recommend conducting non-randomized experiments using similar ideas as the synthetic control method; see, e.g., abadie2021synthetic, doudchenko2021synthetic.
Second, we have used the proxy mean squared error as the primary objective, instead of using the variance of the estimator $\widehat{\tau}$. Since there is a gap between the proxy mean squared error and the variance, the confidence intervals derived based on the proxy mean squared error may suffer from undercoverage issues when the sample size is small. In the simulations literature asmussen2007stochastic, glasserman2004monte, ross2013simulation, this gap could be estimated if the outcomes are assumed to come from known parametric distribution families. Yet there is no general method that estimates such a gap, not even the magnitude of such a gap when the sample size is small. We leave this as a future research direction.
Third, we have shown both high probability guarantees (Theorems (ref) and (ref)) and in expectation guarantees (Corollaries (ref) and (ref)) in this paper. However, with a small probability, the estimation error can still be very large. This is usually referred to as the “tail risk” of an adaptive algorithm, which we do not discuss in this paper. We refer to fan2024fragility, kalvit2021closer for more details, and leave this as a future research direction.
\ACKNOWLEDGMENT{ The author would like to thank Alberto Abadie, Yilun Chen, Dean Eckles, Ivan Fernandez-Val, Christopher Harshaw, Susan Hunter, Ramesh Johari, Menglong Li, Tesary Lin, Tu Ni, Erol Pekoz, Pengyu Qian, Chao Qin, Philippe Rigollet, Daniel Russo, Nian Si, Stefan Wager, Chonghuan Wang, Yunzong Xu, Ruoxuan Xiong, Ruohan Zhan, and Zijie Zhou for their insightful comments that have greatly improved this paper. In particular, the literature review on small gap regime versus fixed gap regime drew from the wisdom of Daniel Russo. }
\ECSwitch
\ECHead{Online Appendix}
In this section, we discuss some unrigorous intuitions behind the design of Algorithm (ref). Intuitively, at the end of each stage, Algorithm (ref) considers three different cases: when the current allocation is significantly different from the estimated Neyman allocation, or when it is moderately different, or when it is not very different. A very natural idea is to directly extend Algorithm (ref) and consider only two cases: when the current allocation is significantly different from the estimated Neyman allocation, or when it is not very different. This direct extension will lead to Algorithm (ref) as follows.
However, Algorithm (ref) does not lead to the competitive ratio $\frac{V(T(1), T(0))}{V(T^*(1), T^*(0))} \approx 1 + T^{-\frac{M-1}{M}}$ as we were able to show in Theorem (ref).
To see this, consider the following example when $M=3$, Denote $\rho = \frac{\sigma(1)}{\sigma(0)}$. Consider the case when $\rho = \frac{T - T^{\frac{1}{3}}}{T^{\frac{1}{3}}} - \varepsilon$, where $\varepsilon > 0$ is a small number. So $\rho$ falls into the following case $\frac{T - T^{\frac{2}{3}}}{T^{\frac{2}{3}}} < \rho \leq \frac{T - T^{\frac{1}{3}}}{T^{\frac{1}{3}}}$. Then with high probability, we will stick with equal allocation in the first $2$ stages, and then in the last stage only allocate units into the treated group. This means that we will allocate a total of $T^{\frac{2}{3}}$ units into the control group, and $T - T^{\frac{2}{3}}$ units into the treated group.
In this case,
which is larger than the $1 + T^{-\frac{2}{3}}$ competitive ratio result that we were able to prove in Theorem (ref).
Through this counterexample, we see that Algorithm (ref), the direct extension of Algorithm (ref), does not yield a desirable competitive ratio. This is the reason why we need the many different cases as in Algorithm (ref). However, it is still unclear if there are other simpler algorithms that can yield the same competitive ratio as in Algorithm (ref).
In this section, we examine the number of treated and control units after we run Algorithms (ref) and (ref). We show that the number of treated and control units converge to the optimal allocation, although the rate that we provide below may not be optimal. This results are implications of Theorems (ref) and (ref).
We defer the proof of Corollary (ref) to Section (ref) and the proof of Corollary (ref) to Section (ref) in the Online Appendix.
We state Theorem 2 from brown1971martingale below without a proof.
We state Theorem 2.2 from gut2009stopped below without a proof. Note that, this result does not require that the sequence of random variables $\big\{Y_n, n \geq 1\big\}$ and the family of random variables $\big\{N(t), t \geq 0\big\}$ are independent.
It is well known that the sample variance can be expressed as a sum of squares.
\proof{Proof of Lemma (ref).} Taking first order derivative, we have
When $\rho < \frac{G_1}{G_2}$, $g'(\rho) < 0$ so $g(\rho)$ is decreasing; when $\rho > \frac{G_1}{G_2}$, $g'(\rho) > 0$ so $g(\rho)$ is increasing.
Using the above, we have that
\halmos \endproof
\proof{Proof of Lemma (ref).} Taking first order derivative, we have
When $\widehat{\rho} < \frac{\sigma(1)}{\sigma(0)}$, $h'(\widehat{\rho}) < 0$, so $h(\widehat{\rho})$ is decreasing in $\widehat{\rho}$; when $\widehat{\rho} > \frac{\sigma(1)}{\sigma(0)}$, $h'(\widehat{\rho}) > 0$, so $h(\widehat{\rho})$ is increasing in $\widehat{\rho}$.
Next, taking second order derivative, we have
So $h(\widehat{\rho})$ is a convex function.
Combing above, we know that $h(\widehat{\rho})$ is a convex function, increasing when $\widehat{\rho} > \frac{\sigma(1)}{\sigma(0)}$ and decreasing when $\widehat{\rho} < \frac{\sigma(1)}{\sigma(0)}$. When $\frac{\sigma(1)}{\sigma(0)}\sqrt{\frac{1-\zeta}{1+\zeta}} \leq \widehat{\rho} \leq \frac{\sigma(1)}{\sigma(0)}\sqrt{\frac{1+\zeta}{1-\zeta}}$, the maximum is taken on the boundaries, i.e.,
\halmos \endproof
\proof{Proof of Lemma (ref).} When $T \geq 16$, we have
On the other hand, when $T \geq 16$ and $\varepsilon \in \left(0, \frac{1}{8}\right)$, we have $T^{1-2\varepsilon} \geq 8 = \left( 2^{\frac{3}{4}} \right)^4$, which then suggests $2^{-\frac{1}{2}}T^{\frac{1}{4}-\frac{\varepsilon}{2}} \geq 2^{\frac{1}{4}} > 0$. So
Since $\frac{1+x}{1-x}$ is an increasing function on $x > 0$, we have
Combining (ref) and (ref) we finish the proof. \halmos \endproof
\proof{Proof of Lemma (ref).} When $0 \leq x \leq \frac{1}{2}$, we have $x + x^2 \leq 1$. Then, since $x \geq 0$, we have $1 \leq 1 + x - x^2 - x^3 = (1+x)^2 (1-x)$. Since $1-x > 0$, this leads to $0 < \frac{1}{1-x} \leq (1+x)^2$. Taking square root we have
Next we show that $\beta_m^{-1} T^{-\frac{m}{M} + \varepsilon} \leq \frac{1}{4}$. To see this, we use the definition of $\beta_m = 6 \cdot 15^{-\frac{m}{M}}$.
where the first inequality is because $T > 15$ and $-\frac{m}{M}+\varepsilon \leq 0$; the second inequality is because $0 < \varepsilon \leq \frac{1}{100}$. Replacing $x = 2 \beta_m^{-1} T^{-\frac{m}{M} + \varepsilon}$ into (ref) we finish the proof. \halmos \endproof
\proof{Proof of Lemma (ref).} First we focus on $\beta_m^{-1} T^{-\frac{m}{M} + \varepsilon}$. Using the definition of $\beta_m = 6 \cdot 15^{-\frac{m}{M}}$,
where the first inequality is because $T > 15$ and $-\frac{m}{M}+\varepsilon \leq 0$; the second inequality is because $0 < \varepsilon \leq \frac{1}{100}$.
Using (ref) as above, we have
Since $\frac{1-x}{1+x}$ is a decreasing function in $x$ when $0<x<1$,
Taking square root finishes the proof. \halmos \endproof
\proof{Proof of Lemma (ref).} Using the definition of $\beta_m = 6 \cdot 15^{-\frac{m}{M}}$,
where the inequality is due to $m < M$. Then we have
which finishes the proof. \halmos \endproof
\proof{Proof of Lemma (ref).} Using the definition of $\beta_1 = 6 \cdot 15^{-\frac{1}{M}}$,
Then, replacing $\frac{1}{2} \beta_1 T^{\frac{1}{M}}$ with $\frac{1}{4}T$ in the denominator, we have
\halmos \endproof
\proof{Proof of Lemma (ref).} From $\varepsilon < 1$, we have
Since $\varepsilon > 0$,
Then we have,
Taking square root we finish the proof. \halmos \endproof
\proof{Proof of Lemma (ref).} From $\varepsilon < \frac{1}{6}$, we have
Since $\varepsilon > 0$,
Then we have,
Since $1-\frac{27}{4}\varepsilon^2 - \frac{27}{4}\varepsilon^3 > 0$, moving it to the left hand side finishes the proof. \halmos \endproof
\proof{Proof of Lemma (ref).} To prove the first claim, note that $\frac{T}{\log{T}}$ is an increasing function, and that $T \geq 320^{\frac{5}{4}} C^5$, so we have
which finishes the proof. \halmos \endproof
\proof{Proof of Lemma (ref).} Note that $\frac{T}{\log{T}}$ is an increasing function, and that $T \geq (\frac{5000}{3})^{\frac{5}{4}} C^5$, so we have
which finishes the proof. \halmos \endproof
\proof{Proof of Lemma (ref).} To prove the first claim, we re-arrange terms from Lemma (ref) and obtain
To prove the second claim, note that from above, we have $T \geq 8 C^2 T^{\frac{1}{2}} (\log{T})^{\frac{1}{2}}$, so that
We also have $2 C T^{-\frac{1}{4}} (\log{T})^{\frac{1}{4}} \leq \frac{\sqrt{2}}{2}$, so that
which concludes the proof of the second claim.
To prove the third claim, note that when $0 \leq x \leq \frac{1}{2}$, we have $x + x^2 \leq 1$. Then, since $x \geq 0$, we have $1 \leq 1 + x - x^2 - x^3 = (1+x)^2 (1-x)$. Since $1-x > 0$, this leads to $0 < \frac{1}{1-x} \leq (1+x)^2$. Taking square root we have
Replacing $x = 4 C^2 T^{-\frac{1}{2}} (\log{T})^{\frac{1}{2}}$ we conclude the proof of the third claim. \halmos \endproof
\proof{Proof of Lemma (ref).} When $0 \leq x \leq \frac{1}{2}$, we have $x + x^2 \leq 1$. Then, since $x \geq 0$, we have $1 \leq 1 + x - x^2 - x^3 = (1+x)^2 (1-x)$. Since $1-x > 0$, this leads to $0 < \frac{1}{1-x} \leq (1+x)^2$. Taking square root we have
Using the definition of $\beta_m = \frac{400}{3} C^4 \log{T} \cdot (\frac{1000}{3} C^4 \log{T})^{-\frac{m}{M}}$,
where the first inequality is due to Lemma (ref) and $m \geq 1$.
Replacing $x = 48 C^4\beta_m^{-1}T^{-\frac{m}{M}}\log{T}$ finishes the proof. \halmos \endproof
\proof{Proof of Lemma (ref).} Using the definition of $\beta_m = \frac{400}{3} C^4 \log{T} \cdot (\frac{1000}{3} C^4 \log{T})^{-\frac{m}{M}}$,
where the first inequality is due to Lemma (ref) and $m \geq 1$.
Using (ref) as above, we have
Since $\frac{1-x}{1+x}$ is a decreasing function in $x$ when $0<x<1$,
Taking square root finishes the proof. \halmos \endproof
\proof{Proof of Lemma (ref).} Using the definition of $\beta_m = \frac{400}{3} C^4 \log{T} \cdot (\frac{1000}{3} C^4 \log{T})^{-\frac{m}{M}}$,
where the inequality is due to Lemma (ref) and $m < M$. Then we have
which finishes the proof. \halmos \endproof
\proof{Proof of Lemma (ref).} Using the definition of $\beta_1 = \frac{400}{3} C^4 \log{T} \cdot (\frac{1000}{3} C^4 \log{T})^{-\frac{1}{M}}$,
where the inequality is due to Lemma (ref). Then, replacing $\frac{1}{2} \beta_1 T^{\frac{1}{M}}$ with $\frac{1}{5}T$ in the denominator, we have
where the last inequality is re-arranging terms, and using the fact that $\frac{250}{3} < 96$. \halmos \endproof
\proof{Proof of Lemma (ref).} Note that we can re-write the sample variance estimator as
We now expand the variance of the sample variance estimator.
Note that, the first term after taking expectation is
The second term is
The third term is
Due to linearity of expectations and merging common terms,
Note that,
and
Putting the above two expressions into (ref) we have
which finishes the proof. \halmos \endproof
\proof{Proof of Lemma (ref).} We prove the first inequality, and the second follows similarly.
Due to Chebyshev inequality,
Note that,
Using Lemma (ref), the above can be expressed as
where the last two inequalities are due to $\sum_{l=1}^m T_l(1) \geq 3$. Putting this inequality back to (ref) we finish the proof. \halmos \endproof
\proof{Proof of Lemma (ref).} The proof is by applying the bounded difference inequality.
First, denote $N = \sum_{l=1}^m T_l(1)$ as a short-hand notion. Denote $\phi(Y_1, ..., Y_{N}) = \widehat{\sigma}^2_m(1)$ to emphasize the dependence on all the potential outcomes up to $N$. Conditional on $W_1, ..., W_{N}$, we distinguish between two cases. If $W_i = 0$, then
If $W_i = 1$, then
To start with (ref), we see that it is equal to
Next, focusing on (ref), we see that it is equal to
Combining both parts, we have
Note that for any $x,y,z \in [-V,V]$, we have
where the first inequality is because the function is monotone with respect to $z$; the last inequality is because both functions are monotone with respect to $x$ and $y$. Replacing $x = Y'_i$, $y = Y_i$, $z = \frac{1}{N-1} \sum_{\substack{t: W_{t} = 1 \\ t \ne i}} Y_{t}$, and $V = C \sigma(1)$ into the above inequality, we have
which finishes discussing the case of $W_i=1$.
Using the bounded difference inequality boucheron2013concentration, mcdiarmid1989method,
Similarly, we can show
which finishes the proof. \halmos \endproof
Lemma (ref) is very common knowledge. We provide a proof below for completeness.
\proof{Proof of Lemma (ref).} Denote $\bar{X} = \frac{1}{n} \sum_{i=1}^n X_i$.
\halmos
In the main paper, we did not provide proofs to (ref) and (ref) because they are very well-known. For completeness, we provide proofs to the derivation of expressions (ref) and (ref) here.
Consider the case when $T(1)$ and $T(0)$ are fixed. Note that there are two sources of randomness: the treatment assignments are random, and the potential outcomes are also random. Using the law of total variance,
We derive both terms separately. First,
Since the expression of $\mathrm{Var}\left(\widehat{\tau} \vert W_1, ..., W_T\right)$ only directly depends on $T(1)$ and $T(0)$ but not directly on $W_1, ..., W_T$,
Second,
Since the expression of $\mathrm{E}\left[\widehat{\tau} \vert W_1, ..., W_T\right]$ does not depend on $W_1, ..., W_T$,
Combining both parts,
Consider the following problem:
Consider the first order condition, which leads to
Simplifying terms this reduces to
And the optimal objective value is
\proof{Proof of Theorem (ref).} Since this is a single stage experiment, we use $V(T(1), T(0))$ instead of $\mathrm{E}[V(T(1), T(0))]$. Suppose the optimal solution is not $T(1) = T(0) = T/2$. Without loss of generality, assume the optimal solution is such that $T(1) > T(0) > 0$. Then for any $(T(1), T(0))$, the worst case $\sigma(1), \sigma(0)$ should solve the following problem,
Using (ref), the above expression can be re-written as
When $\sigma(0) \ne 0$, denote $\rho = \sigma(1) / \sigma(0) \in [0, +\infty)$. Further denote
Taking first order derivative,
So $g(\rho)$ is an increasing function when $\rho > T(1) / T(0)$, and an decreasing function when $\rho < T(1) / T(0)$. The maximum value of $g(\rho)$ is taken when either $\rho = 0$ or $\rho \to +\infty$. Denote $g(+\infty) = \lim_{\rho \to +\infty} g(\rho)$.
Putting the above back to (ref), we have, for any $(T(1), T(0))$ such that $T(1) > T(0) > 0$,
where the last inequality holds because $T(0) < T/2$. This suggests that, if $T(1) > T(0) > 0$, then
On the other hand, when $T(1) = T(0) = T/2$. For any $\sigma(1), \sigma(0)$,
This suggests that
Combining both cases, the optimal solution must be $T(1) = T(0) = T/2$.
To prove the second part of the Theorem, we focus on the inequality in (ref). The inequality holds when either $\sigma(1) = 0$ or $\sigma(0) = 0$. \halmos \endproof
\proof{Proof of Theorem (ref).} Without loss of generality, we assume $\sigma(1) \geq \sigma(0)$ throughout the proof. Our analysis of the two-stage adaptive Neyman allocation (Algorithm (ref)) will be based on the following two events.
Denote $\mathcal{E} = \mathcal{E}_1(1) \cap \mathcal{E}_1(0)$. Then $\Pr(\mathcal{E}) = \Pr(\mathcal{E}_1(1) \cap \mathcal{E}_1(0)) \geq 1 - \Pr(\overline{\mathcal{E}}_1(1)) - \Pr(\overline{\mathcal{E}}_1(0))$. We further have
where the inequality is due to Lemma (ref).
Conditional on the event $\mathcal{E}$, we have
Due to (ref) and (ref), and given that $\sigma(1), \sigma(0) > 0$, we have $\widehat{\sigma}^2_1(1), \widehat{\sigma}^2_1(0) > 0$. Denote $\rho = \frac{\sigma(1)}{\sigma(0)}$ and $\widehat{\rho} = \frac{\widehat{\sigma}_1(1)}{\widehat{\sigma}_1(0)}$.
Now we distinguish two cases, and discuss these two cases separately.
Note that, for case 2, we do not discuss $\rho = \frac{\sigma(1)}{\sigma(0)} < \frac{\frac{1}{2}T^{\frac{1}{2}}}{T - \frac{1}{2}T^{\frac{1}{2}}}$, because we assume that $\sigma(1) \geq \sigma(0)$. For each of the above two cases, we further discuss two sub-cases. The remaining of the proof is structured as enumerating all four cases. After enumerating all four sub-cases we finish the proof.
\noindentCase 1.1:
Since $\frac{\frac{1}{2}T^{\frac{1}{2}}}{T - \frac{1}{2}T^{\frac{1}{2}}} \leq \widehat{\rho} \leq \frac{T - \frac{1}{2}T^{\frac{1}{2}}}{\frac{1}{2}T^{\frac{1}{2}}}$, we have
Due to this, Algorithm (ref) goes to Line 3 instead of Line 5 or Line 7. The total numbers of treated and control units are given by (ref). We re-write (ref) again as follows,
With a little abuse of notation, we write $V(T(1), T(0)\vert \mathcal{E})$ to stand for $V(T(1), T(0))$, where we emphasize that this is a random quantity (as $T(1)$ and $T(0)$ are random) that is conditional on event $\mathcal{E}$. Putting $(T(1), T(0))$ into (ref), we have, for any $\sigma(1), \sigma(0)$,
Due to Lemma (ref), and using (ref) and (ref),
Note that
Note also that
where the inequality holds when $T^{\frac{1}{2} - \varepsilon} \geq 2$. This is because $T \geq 16$ and $\varepsilon \in (0,\frac{1}{8})$, so we have $T^{\frac{1}{2} - \varepsilon} \geq T^{\frac{1}{4}} \geq 2$.
Combining (ref) --- (ref), we have
\noindentCase 1.2:
If $\widehat{\rho} > \frac{T - \frac{1}{2}T^{\frac{1}{2}}}{\frac{1}{2}T^{\frac{1}{2}}}$, then
Due to this, Algorithm (ref) goes to Line 7. The total numbers of treated and control units are given by $(T(1), T(0)) = (T - \frac{1}{2}T^{\frac{1}{2}}, \frac{1}{2}T^{\frac{1}{2}})$.
Note that, conditional on event $\mathcal{E}$,
Putting $(T(1), T(0))$ into (ref), we have, for any $\sigma(1), \sigma(0)$,
where the inequality is due to Lemma (ref). Combining this with (ref) and (ref) we have again
If $\widehat{\rho} < \frac{\frac{1}{2}T^{\frac{1}{2}}}{T - \frac{1}{2}T^{\frac{1}{2}}}$, then Algorithm (ref) goes to Line 5.
and the same analysis follows similarly.
\noindentCase 2.1:
Since $\widehat{\rho} > \frac{T - \frac{1}{2}T^{\frac{1}{2}}}{\frac{1}{2}T^{\frac{1}{2}}}$, we have
Due to this, Algorithm (ref) goes to Line 7. The total numbers of treated and control units are given by $(T(1), T(0)) = (T - \frac{1}{2}T^{\frac{1}{2}}, \frac{1}{2}T^{\frac{1}{2}})$.
Putting $(T(1), T(0))$ into (ref), we have, for any $\sigma(1), \sigma(0)$,
Due to Lemma (ref), since $\rho = \frac{\sigma(1)}{\sigma(0)} > \frac{T - \frac{1}{2}T^{\frac{1}{2}}}{\frac{1}{2}T^{\frac{1}{2}}}$, we know that the expression in (ref) is increasing with respect to $\rho$. So we have
where the last inequality holds because $T \geq 1$.
\noindentCase 2.2:
Note that,
where the first inequality is due to (ref); the second inequality is due to $\rho > \frac{T - \frac{1}{2}T^{\frac{1}{2}}}{\frac{1}{2}T^{\frac{1}{2}}}$; the third inequality is due to (ref); the last inequality is due to Lemma (ref).
The above shows that, in this case (Case 2.2),
Since $\frac{\frac{1}{2}T^{\frac{1}{2}}}{T - \frac{1}{2}T^{\frac{1}{2}}} \leq \widehat{\rho} \leq \frac{T - \frac{1}{2}T^{\frac{1}{2}}}{\frac{1}{2}T^{\frac{1}{2}}}$, we have
Due to this, Algorithm (ref) goes to Line 3 instead of Line 5 or Line 7. The total numbers of treated and control units are given by (ref), which we write again as follows,
Similar to Case 1.1, combining (ref) --- (ref), we have
To conclude, in all four cases,
\halmos \endproof
\proof{Proof of Theorem (ref).} We first show Algorithm (ref) is feasible. To start, it is easy to see $1 < \beta_1 T^{\frac{1}{M}}$. Then for any $m \leq M-2$,
where the inequality is because $T>15$. Finally,
where the first inequality is because $M \geq 3$. Combining all above we know Algorithm (ref) is feasible, i.e., $1 < \beta_1 T^{\frac{1}{M}} < ... < \beta_{M-1} T^{\frac{M-1}{M}} < T$.
Then we analyze the performance of Algorithm (ref). Our analysis of Algorithm (ref) relies on a clean event analysis, which has been widely used in the online learning literature to prove upper bounds badanidiyuru2018bandits, lattimore2020bandit, slivkins2019introduction, and has been recently used in the stochastic control literature to prove lower bounds arlotto2019uniformly.
To proceed with the clean event analysis, suppose there are two length-$T$ arrays for the treated and the control, respectively, with each value being an independent and identically distributed copy of the representative random variables $Y(1)$ and $Y(0)$, respectively. When Algorithm (ref) suggests to conduct an $m$-th stage experiment parameterized by $(T_m(1), T_m(0))$, the observations from the $m$-th stage experiment are generated by reading the next $T_m(1)$ values from the treated array, and the next $T_m(0)$ values from the control array. See Figure (ref) for an illustration.
Even though Algorithm (ref) adaptively determines the number of treated and control units, it is always the first few values of of the two arrays that are read. For any $m \leq M-1$, let $\widehat{\psi}^2_m(1)$ and $\widehat{\psi}^2_{m}(0)$ be the sample variance estimators obtained from reading the first $\frac{\beta_m}{2}T^{\frac{m}{M}}$ values in the treated array and control array, respectively. Depending on the execution of Algorithm (ref), only a few of the sample variance estimators $\widehat{\sigma}^2_m(1)$ or $\widehat{\sigma}^2_m(0)$ are calculated. When one sample variance estimator $\widehat{\sigma}^2_m(1)$ or $\widehat{\sigma}^2_m(0)$ is calculated following Algorithm (ref), it is equivalent to reading the corresponding $\widehat{\psi}^2_m(1)$ or $\widehat{\psi}^2_m(0)$ from Table (ref).
Define the following events. For any $m \leq M-1$, define
Denote the intersect of all above events as $\mathcal{E}$, i.e.,
Then due to union bound,
We further have
where the inequality is due to Lemma (ref).
Conditional on the event $\mathcal{E}$, we have, for any $m \leq M-1$,
Since $\sigma(1), \sigma(0) > 0$, we can denote $\rho = \frac{\sigma(1)}{\sigma(0)}$. For any $m \leq M-1$, when $\widehat{\sigma}^2_m(1)$ and $\widehat{\sigma}^2_m(0)$ are calculated during Algorithm (ref), $\widehat{\sigma}^2_m(1) = \widehat{\psi}^2_m(1)$ and $\widehat{\sigma}^2_m(0) = \widehat{\psi}^2_m(0)$. Conditional on the event $\mathcal{E}$, due to (ref) and (ref), and given that $\sigma(1), \sigma(0) > 0$, we have $\widehat{\sigma}^2_m(1), \widehat{\sigma}^2_m(0) > 0$. Then we can denote $\widehat{\rho}_m = \frac{\widehat{\sigma}_m(1)}{\widehat{\sigma}_m(0)}$.
In the remaining of the analysis, we distinguish several cases and discuss these cases separately. Recall that $\widehat{\rho}_1 = \frac{\widehat{\sigma}_1(1)}{\widehat{\sigma}_1(0)}$. Without loss of generality, assume
\noindentCase 1:
Case 1.1:
In this case,
So Algorithm (ref) goes to Line (ref) in the $1$-st stage experiment. Then we have
With a little abuse of notation, we write $V(T(1), T(0)\vert \mathcal{E})$ to stand for $V(T(1), T(0))$, where we emphasize that this is a random quantity (as $T(1)$ and $T(0)$ are random) that is conditional on event $\mathcal{E}$. We can then express
Recall that $\rho = \frac{\sigma(1)}{\sigma(0)}$. We further distinguish two cases.
First, if $\rho < \frac{T - \frac{1}{2} \beta_1 T^{\frac{1}{M}}}{\frac{1}{2} \beta_1 T^{\frac{1}{M}}}$, then we write (ref) as
Note that,
So we have
where the first inequality is due to Lemma (ref) and (ref); the last inequality is due to Lemma (ref).
Note that, $\frac{\sigma(1) \sigma(0)}{(\sigma(1) + \sigma(0))^2} = \frac{\rho}{(\rho+1)^2}$ is a decreasing function when $\rho>1$. Note also that,
where the first inequality is due to (ref); the second inequality is due to Lemma (ref); the last inequality is due to Lemma (ref).
Then we have
Putting this into (ref) we have
where the last inequality is because $T > 15$ so $T^{-1+\varepsilon} = T^{-\frac{1}{M}} \cdot T^{-\frac{M-1}{M}+\varepsilon} < 15^{-\frac{1}{M}} \cdot T^{-\frac{M-1}{M}+\varepsilon}$.
Second, if $\rho \geq \frac{T - \frac{1}{2} \beta_1 T^{\frac{1}{M}}}{\frac{1}{2} \beta_1 T^{\frac{1}{M}}}$, then we write (ref) as
So we have
where the first inequality is due to Lemma (ref); the last inequality is due to Lemma (ref).
Combining $\rho < \frac{T - \frac{1}{2} \beta_1 T^{\frac{1}{M}}}{\frac{1}{2} \beta_1 T^{\frac{1}{M}}}$ and $\rho \geq \frac{T - \frac{1}{2} \beta_1 T^{\frac{1}{M}}}{\frac{1}{2} \beta_1 T^{\frac{1}{M}}}$ we have that in Case 1.1,
Case 1.2:
In this case,
So Algorithm (ref) goes to Line (ref) in the $1$-st stage experiment. Then we have
We can then express
Recall that, conditional on $\mathcal{E}$, (ref) and (ref) lead to
So we have
where the first inequality is due to Lemma (ref); the last inequality is due to Lemma (ref).
Note that, $\frac{\sigma(1) \sigma(0)}{(\sigma(1) + \sigma(0))^2} = \frac{\rho}{(\rho+1)^2}$ is a decreasing function when $\rho>1$. Note also that,
where the first inequality is due to (ref) and (ref); the second inequality is due to the condition of Case 1.2; the third inequality is due to Lemma (ref); the last inequality is due to Lemma (ref). Then we have
Putting this into (ref) we have that in Case 1.2,
\noindentCase 2:
Due to (ref) we know that $\widehat{\sigma}_1(1) \geq \widehat{\sigma}_1(0)$. In Case 2 we immediately have
So Algorithm (ref) goes to Line (ref) in the 1-st stage experiment. We further distinguish two cases.
\noindentCase 2.1:
In this case,
So Algorithm (ref) goes to Line (ref) in the $2$-nd stage experiment. Then we have
We can express
Note that,
where the first and the fourth inequalities are due to (ref) and (ref); the second and the third inequalities are due to the condition of Case 2.1; the last inequality is because $\beta_1 T^{\frac{1}{M}} < \beta_2 T^{\frac{2}{M}}$ so we have $2^{\frac{1}{2}} \beta_2^{-\frac{1}{2}} T^{-\frac{2}{2M}+\frac{\varepsilon}{2}} < 2^{\frac{1}{2}} \beta_1^{-\frac{1}{2}} T^{-\frac{1}{2M}+\frac{\varepsilon}{2}}$.
Then we have
where the first inequality is due to Lemma (ref); the last inequality is due to Lemma (ref).
Note that, $\frac{\sigma(1) \sigma(0)}{(\sigma(1) + \sigma(0))^2} = \frac{\rho}{(\rho+1)^2}$ is a decreasing function when $\rho>1$. Note also that,
where the first inequality is due to (ref); the second inequality is due to Lemma (ref); the last inequality is due to Lemma (ref).
Then we have
Putting this into (ref) we have that in Case 2.1,
\noindentCase 2.2:
In this case,
So Algorithm (ref) goes to Line (ref) in the $2$-nd stage experiment. Then we have
We can then express
Recall that, conditional on $\mathcal{E}$, (ref) and (ref) lead to
So we have
where the first inequality is due to Lemma (ref); the last inequality is due to Lemma (ref).
Note that, $\frac{\sigma(1) \sigma(0)}{(\sigma(1) + \sigma(0))^2} = \frac{\rho}{(\rho+1)^2}$ is a decreasing function when $\rho>1$. Note also that,
where the first inequality is due to (ref) and (ref); the second inequality is due to the condition of Case 2.2; the third inequality is due to Lemma (ref); the last inequality is due to Lemma (ref). Then we have
Putting this into (ref) we have that in Case 2.2,
\noindentCase $\bm{m}$ (when $m \leq M-2$):
Due to the condition of Case $m$, we immediately have
On the other hand, since
where the first and second inequalities are due to (ref) and (ref); the third inequality is due to (ref); the fourth inequality is due to Lemma (ref); the last inequality is due to Lemma (ref). Due to the above sequence of inequalities, we have $\frac{1}{\widehat{\rho}_{m-1}} \leq \frac{T - \frac{1}{2}\beta_m T^{\frac{m}{M}}}{\frac{1}{2}\beta_m T^{\frac{m}{M}}}$, which leads to
So Algorithm (ref) goes to Line (ref) in the (m-1)-th stage experiment. We further distinguish two cases.
\noindentCase $\bm{m}$.1: In addition to the conditions in Case $m$ above, we also have
Similar to the analysis in Case 2.1, we proceed with the following analysis. In Case $m$.1,
So Algorithm (ref) goes to Line (ref) in the $m$-th stage experiment. Then we have
We can express
Note that,
where the first and the fourth inequalities are due to (ref) and (ref); the second and the third inequalities are due to the condition of Case $m$.1; the last inequality is because $\beta_{m-1} T^{\frac{m-1}{M}} < \beta_m T^{\frac{m}{M}}$ so we have $2^{\frac{1}{2}} \beta_m^{-\frac{1}{2}} T^{-\frac{m}{2M}+\frac{\varepsilon}{2}} < 2^{\frac{1}{2}} \beta_{m-1}^{-\frac{1}{2}} T^{-\frac{m-1}{2M}+\frac{\varepsilon}{2}}$.
Then we have
where the first inequality is due to Lemma (ref); the last inequality is due to Lemma (ref).
Note that, $\frac{\sigma(1) \sigma(0)}{(\sigma(1) + \sigma(0))^2} = \frac{\rho}{(\rho+1)^2}$ is a decreasing function when $\rho>1$. Note also that,
where the first inequality is due to (ref); the second inequality is due to Lemma (ref); the last inequality is due to Lemma (ref).
Then we have
Putting this into (ref) we have that in Case $m$.1,
\noindentCase $\bm{m}$.2: In addition to the conditions in Case $m$ above, we also have
Similar to the analysis in Case 2.2, we proceed with the following analysis. In Case $m$.2,
So Algorithm (ref) goes to Line (ref) in the $m$-th stage experiment. Then we have
We can then express
Recall that, conditional on $\mathcal{E}$, (ref) and (ref) lead to
So we have
where the first inequality is due to Lemma (ref); the last inequality is due to Lemma (ref).
Note that, $\frac{\sigma(1) \sigma(0)}{(\sigma(1) + \sigma(0))^2} = \frac{\rho}{(\rho+1)^2}$ is a decreasing function when $\rho>1$. Note also that,
where the first inequality is due to (ref) and (ref); the second inequality is due to the condition of Case 2.2; the third inequality is due to Lemma (ref); the last inequality is due to Lemma (ref). Then we have
Putting this into (ref) we have that in Case $m$.2,
\noindentCase ($\bm{M-1}$):
Due to the condition of Case ($M-1$), we immediately have
On the other hand, since
where the first and second inequalities are due to (ref) and (ref); the third inequality is due to (ref); the fourth inequality is due to Lemma (ref); the last inequality is due to Lemma (ref). Due to the above sequence of inequalities, we have $\frac{1}{\widehat{\rho}_{M-2}} \leq \frac{T - \frac{1}{2}\beta_{M-1} T^{\frac{M-1}{M}}}{\frac{1}{2}\beta_{M-1} T^{\frac{M-1}{M}}}$, which leads to
So Algorithm (ref) goes to Line (ref) in the $(M-2)$-th stage experiment. Then Algorithm (ref) goes to Line (ref) in the last stage. We further distinguish two cases.
\noindentCase ($\bm{M-1}$).1: In addition to the conditions in Case $(M-1)$ above, we also have
Similar to the analysis in Case $m$.1, we proceed with the following analysis. In Case $(M-1)$.1,
So Algorithm (ref) goes to Line (ref) in the $(M-1)$-th stage experiment, and we have
We can express
Note that,
where the first and the fourth inequalities are due to (ref) and (ref); the second and the third inequalities are due to the conditions of Case $(M-1)$.1; the last inequality is because $\beta_{M-2} T^{\frac{M-2}{M}} < \beta_{M-1} T^{\frac{M-1}{M}}$ so we have $2^{\frac{1}{2}} \beta_{M-1}^{-\frac{1}{2}} T^{-\frac{M-1}{2M}+\frac{\varepsilon}{2}} < 2^{\frac{1}{2}} \beta_{M-2}^{-\frac{1}{2}} T^{-\frac{M-2}{2M}+\frac{\varepsilon}{2}}$.
Then we have
where the first inequality is due to Lemma (ref); the last inequality is due to Lemma (ref).
Note that, $\frac{\sigma(1) \sigma(0)}{(\sigma(1) + \sigma(0))^2} = \frac{\rho}{(\rho+1)^2}$ is a decreasing function when $\rho>1$. Note also that,
where the first inequality is due to (ref); the second inequality is due to Lemma (ref); the last inequality is due to Lemma (ref).
Then we have
Putting this into (ref) we have that in Case $(M-1)$.1,
\noindentCase ($\bm{M-1}$).2: In addition to the conditions in Case $(M-1)$ above, we also have
Due to the condition of Case ($M-1$).2, we immediately have
On the other hand, since
where the first and second inequalities are due to (ref) and (ref); the third inequality is due to (ref); the fourth inequality is due to Lemma (ref); the last inequality is due to Lemma (ref). Due to the above sequence of inequalities, we have $\frac{1}{\widehat{\rho}_{M-1}} \leq \frac{T - \frac{1}{2}\beta_{M-1} T^{\frac{M-1}{M}}}{\frac{1}{2}\beta_{M-1} T^{\frac{M-1}{M}}}$, which leads to
So Algorithm (ref) goes to Line (ref) in the $(M-1)$-th stage experiment. Then we have
We can then express
Recall that, conditional on $\mathcal{E}$, (ref) and (ref) lead to
So we have
where the first inequality is due to Lemma (ref); the second inequality is due to Lemma (ref); the last inequality is because $\frac{\sigma(1) \sigma(0)}{(\sigma(1) + \sigma(0))^2} \leq \frac{1}{4}$.
Finally, using the definition of $\beta_{M-1} = 6 \cdot 15^{-\frac{M-1}{M}}$,
So we have
To conclude, in all cases, we have shown that
\halmos \endproof
\proof{Proof of Theorem (ref).} Fix any adaptive design of experiment $\pi$. Let $T \geq 4$ and define
Let there be two discrete probability distributions $\nu$ and $\nu'$, defined as follows. Both distributions have three discrete supports $\{-1,0,1\}$. The probability mass for distribution $\nu$ is given by
The probability mass for distribution $\nu'$ is given by
Then we immediately have
Moreover, we upper bound the KL-divergences of these two probability distributions as follows.
where the first inequality is due to Lemma (ref); the second inequality is because for any $x>0$, $\log{(1+x)} \leq x$.
On the other hand, the KL-divergence calculated in the other way is upper bounded by.
where the first inequality is because first, for any $x>0$, $\log{(1+x)} \leq x$, and second, for any $0<x<1$, $\log{(1-x)} \leq -x$.
We will use these two probability distributions to construct two problem instances. Consider the first problem instance where $Y(1) \sim \nu', Y(0) \sim \nu$. Denote $\Pr_{\nu',\nu}$ as the probability distribution induced by this problem instance and by the design of experiment $\pi$, where we drop the dependence on $\pi$ as it is clear from the context. Denote $\mathrm{E}_{\nu',\nu}$ as the expectation taken under $\Pr_{\nu',\nu}$.
Similarly, consider the second problem instance where $Y(1) \sim \nu, Y(0) \sim \nu'$. Denote $\Pr_{\nu,\nu'}$ as the probability distribution induced by this problem instance and by the design of experiment $\pi$, where we drop the dependence on $\pi$. Denote $\mathrm{E}_{\nu,\nu'}$ as the expectation taken under $\Pr_{\nu,\nu'}$.
Now we focus on the first instance $(Y(1), Y(0)) \sim (\nu', \nu)$. Note that $\sigma^2(1) = \sigma^2(\nu') > \sigma^2(\nu) = \sigma^2(0)$. When $T^\pi(1) \leq \frac{T}{2}$, we have
Due to Lemma (ref),
On the other hand, when $T^\pi(1) > \frac{T}{2}$, the ratio is greater or equal to $1$, i.e.,
Putting the above two cases together we have
We further have
where the first inequality is due to Lemma (ref); the last inequality is due to $\varepsilon \leq \frac{1}{6}$. Putting the above inequality into (ref) we have
Next we focus on the second instance $(Y(1), Y(0)) \sim (\nu, \nu')$. Similar to the above analysis, we have
Combining (ref) and (ref) we have
where the second inequality is due to Bretagnolle-Huber inequality bretagnolle1979estimation, lattimore2020bandit.
Next we upper bound $D_{KL}\left( \mathrm{Pr}_{\nu',\nu}, \mathrm{Pr}_{\nu,\nu'} \right)$.
where the inequality is due to (ref) and (ref). Putting this into (ref) we have
where the equality is using $\varepsilon = \frac{1}{3T^{\frac{1}{2}}}$. Using the above inequality we have
\halmos \endproof
\proof{Proof of Theorem (ref).} Our proof proceeds by identifying the following sequence of realizations of the sample variances,
We denote the above event using $\mathcal{E}(a_1(1), ..., a_{M-1}(1), a_1(0), ..., a_{M-1}(0)) := \mathcal{E}(\bm{a})$.
Below we show that, for any $\bm{a} \in \mathbb{R}^{2(M-1)}$, and conditional on event $\mathcal{E}(\bm{a})$, the difference-in-means estimator as defined in (ref) is unbiased, that is,
Note that, conditional on $\mathcal{E}(\bm{a})$, our adaptive Neyman allocation algorithm (including both Algorithm (ref) and Algorithm (ref)) will uniquely determine the number of treated and control units assigned in each stage, which are $T_1(1), T_1(0), ..., T_M(1), T_M(1).$ In other words, conditional on $\mathcal{E}(\bm{a})$, we can think of $T_1(1), T_1(0), ..., T_M(1), T_M(1)$ as constants. Consequently, conditional on $\mathcal{E}(\bm{a})$, we can also think of $T(1) = \sum_{m=1}^M T_m(1)$ and $T(0) = \sum_{m=1}^M T_m(0)$ as constants.
Now we focus on the difference-in-means estimator.
where the first equality is counting by each stage; the second equality is because conditional on $\mathcal{E}(\bm{a})$, $T_1(1), T_1(0), ..., T_M(1), T_M(1)$ are all fixed, so that $\text{\usefont{U}{bbm}{m}{n}1}\{W_t=1\}$ only depends on the randomization and thus is independent of $Y_t$.
Next, we focus on $\mathrm{E}\big[ Y_t(1) \Big\vert \mathcal{E}(\bm{a}) \big]$. Because of Lemma (ref), the event $\widehat{\sigma}^2_m(1) = a_m(1)$ can be written as
Because of Assumption (ref) and because the potential outcomes $(Y_1(1), Y_1(0))$, $(Y_2(1), Y_2(0))$, ..., $(Y_T(1), Y_T(0))$ are mutually independent, the joint distribution of
and the joint distribution of
are identical. Replacing all the random variables $\big(Y_1(1), Y_2(1), ..., Y_T(1)\big)$ by the random variables $\big(2\mathrm{E}[Y(1)] - Y_1(1), 2\mathrm{E}[Y(1)] - Y_2(1), ..., 2\mathrm{E}[Y(1)] - Y_T(1)\big)$, the event $\widehat{\sigma}^2_m(1) = a_m(1)$ is written as
This above expression coincides with (ref).
Similarly, we can replace all the random variables $\big(Y_1(0), Y_2(0), ..., Y_T(0)\big)$ by the random variables $\big(2\mathrm{E}[Y(0)] - Y_1(0), 2\mathrm{E}[Y(0)] - Y_2(0), ..., 2\mathrm{E}[Y(0)] - Y_T(0)\big)$, and the event $\widehat{\sigma}^2_m(0) = a_m(0)$ has the same expression. Consequently,
which yields
Putting (ref) into (ref), we have
Similarly,
Combining both equalities we finish the proof. \halmos \endproof
As suggested in chen2025characterization, khamaru2024inference, as long as some notion of stability condition holds, one can establish central limit theorems for the sample means, despite that the data is collected in an adaptive fashion. In Section (ref), we state the stability condition of our adaptive Neyman allocation algorithms. Then in Section (ref), we use the martingale central limit theorem from brown1971martingale to prove Theorem (ref) by checking the Lindeberg condition.
To check the stability condition, we need to construct a pair of deterministic quantities $(T^*(1), T^*(0))$ to compare with the pair of random variables $(T(1), T(0))$.
When $M=2$, define $(T^*(1), T^*(0))$ as follows,
When $M \geq 3$, define $(T^*(1), T^*(0))$ as follows,
Using the above definitions, we define the stability condition of our adaptive Neyman allocation algorithms below.
Below we prove Lemma (ref) separately when $M=2$ and when $M \geq 3$ because the algorithms that we use are different.
\proof{Proof of Lemma (ref) when $M=2$.} We can explicitly verify that Condition (ref) in Lemma (ref) is satisfied. Below we prove Condition (ref).
Without loss of generality, we assume $\sigma(1) \geq \sigma(0)$ throughout the proof. Our analysis of the two-stage adaptive Neyman allocation (Algorithm (ref)) will be based on the following two events.
Denote $\mathcal{E} = \mathcal{E}_1(1) \cap \mathcal{E}_1(0)$. Then $\Pr(\mathcal{E}) = \Pr(\mathcal{E}_1(1) \cap \mathcal{E}_1(0)) \geq 1 - \Pr(\overline{\mathcal{E}}_1(1)) - \Pr(\overline{\mathcal{E}}_1(0))$. We further have
where the inequality is due to Lemma (ref).
Conditional on the event $\mathcal{E}$, we have
Due to (ref) and (ref), and given that $\sigma(1), \sigma(0) > 0$, we have $\widehat{\sigma}^2_1(1), \widehat{\sigma}^2_1(0) > 0$. Denote $\rho = \frac{\sigma(1)}{\sigma(0)}$ and $\widehat{\rho} = \frac{\widehat{\sigma}_1(1)}{\widehat{\sigma}_1(0)}$.
Now we distinguish two cases, and discuss these two cases separately.
Note that, for case 2, we do not discuss $\rho = \frac{\sigma(1)}{\sigma(0)} < \frac{\frac{1}{2}T^{\frac{1}{2}}}{T - \frac{1}{2}T^{\frac{1}{2}}}$, because we assume that $\sigma(1) \geq \sigma(0)$. For each of the above two cases, we further discuss two sub-cases. The remaining of the proof is structured as enumerating all four cases. After enumerating all four sub-cases we finish the proof.
\noindentCase 1.1:
Since $\frac{\frac{1}{2}T^{\frac{1}{2}}}{T - \frac{1}{2}T^{\frac{1}{2}}} \leq \widehat{\rho} \leq \frac{T - \frac{1}{2}T^{\frac{1}{2}}}{\frac{1}{2}T^{\frac{1}{2}}}$, we have
As a result, Algorithm (ref) goes to Line 3 instead of Line 5 or Line 7. The total numbers of treated and control units are given by (ref). We re-write (ref) again as follows,
On the other hand, since $\frac{\frac{1}{2}T^{\frac{1}{2}}}{T - \frac{1}{2}T^{\frac{1}{2}}} \leq \rho \leq \frac{T - \frac{1}{2}T^{\frac{1}{2}}}{\frac{1}{2}T^{\frac{1}{2}}}$, following (ref) we have
Conditional on event $\mathcal{E}$, we have
where the inequality is due to (ref) and (ref).
So conditional on event $\mathcal{E}$, we have $\left\vert \frac{T(1)}{T^*(1)} - 1 \right\vert \to 0$ as $T \to +\infty$. In addition, $1 - \Pr(\mathcal{E}) = \frac{\kappa(1) + \kappa(0)}{T^{\varepsilon}} \to 0$ as $T \to +\infty$. Combining these two, we have $\frac{T(1)}{T^*(1)} \xrightarrow{p} 1$ as $T \to +\infty$. Similarly, $\frac{T(0)}{T^*(0)} \xrightarrow{p} 1$ as $T \to +\infty$.
\noindentCase 1.2:
If $\widehat{\rho} > \frac{T - \frac{1}{2}T^{\frac{1}{2}}}{\frac{1}{2}T^{\frac{1}{2}}}$, then
Due to this, Algorithm (ref) goes to Line 7. The total numbers of treated and control units are given by
On the other hand, since $\frac{\frac{1}{2}T^{\frac{1}{2}}}{T - \frac{1}{2}T^{\frac{1}{2}}} \leq \rho \leq \frac{T - \frac{1}{2}T^{\frac{1}{2}}}{\frac{1}{2}T^{\frac{1}{2}}}$, following (ref) we have
Note that,
Conditional on event $\mathcal{E}$, we have
where the inequality is because $\big(1+\frac{1}{\rho}\big) \cdot \frac{T-\frac{1}{2}T^{\frac{1}{2}}}{T} - 1$ is decreasing in $\rho$ and equals $0$ when $\rho = \frac{T - \frac{1}{2}T^{\frac{1}{2}}}{\frac{1}{2}T^{\frac{1}{2}}}$.
So conditional on event $\mathcal{E}$, we have $\left\vert \frac{T(1)}{T^*(1)} - 1 \right\vert \to 0$ as $T \to +\infty$. In addition, $1 - \Pr(\mathcal{E}) = \frac{\kappa(1) + \kappa(0)}{T^{\varepsilon}} \to 0$ as $T \to +\infty$. Combining these two, we have $\frac{T(1)}{T^*(1)} \xrightarrow{p} 1$ as $T \to +\infty$.
Conditional on event $\mathcal{E}$, we have
where the inequality is because $\big(\rho + 1\big) \frac{1}{2T^{\frac{1}{2}}} - 1$ is increasing in $\rho$ and equals $0$ when $\rho = \frac{T - \frac{1}{2}T^{\frac{1}{2}}}{\frac{1}{2}T^{\frac{1}{2}}}$.
So conditional on event $\mathcal{E}$, we have $\left\vert \frac{T(0)}{T^*(0)} - 1 \right\vert \to 0$ as $T \to +\infty$. In addition, $1 - \Pr(\mathcal{E}) = \frac{\kappa(1) + \kappa(0)}{T^{\varepsilon}} \to 0$ as $T \to +\infty$. Combining these two, we have $\frac{T(0)}{T^*(0)} \xrightarrow{p} 1$ as $T \to +\infty$.
If $\widehat{\rho} < \frac{\frac{1}{2}T^{\frac{1}{2}}}{T - \frac{1}{2}T^{\frac{1}{2}}}$, then Algorithm (ref) goes to Line 5 and the same analysis follows similarly.
\noindentCase 2.1:
Since $\widehat{\rho} > \frac{T - \frac{1}{2}T^{\frac{1}{2}}}{\frac{1}{2}T^{\frac{1}{2}}}$, we have
As a result, Algorithm (ref) goes to Line 7. The total numbers of treated and control units are given by
On the other hand, since $\rho > \frac{T - \frac{1}{2}T^{\frac{1}{2}}}{\frac{1}{2}T^{\frac{1}{2}}}$, following (ref) we have
So conditional on event $\mathcal{E}$, we have $\frac{T(1)}{T^*(1)} = 1$. In addition, $1 - \Pr(\mathcal{E}) = \frac{\kappa(1) + \kappa(0)}{T^{\varepsilon}} \to 0$ as $T \to +\infty$. Combining these two, we have $\frac{T(1)}{T^*(1)} \xrightarrow{p} 1$ as $T \to +\infty$. Similarly, $\frac{T(0)}{T^*(0)} \xrightarrow{p} 1$ as $T \to +\infty$.
\noindentCase 2.2:
Note that,
where the first inequality is due to (ref); the second inequality is due to $\rho > \frac{T - \frac{1}{2}T^{\frac{1}{2}}}{\frac{1}{2}T^{\frac{1}{2}}}$; the third inequality is due to (ref); the last inequality is due to Lemma (ref).
The above shows that, in this case (Case 2.2),
Since $\frac{\frac{1}{2}T^{\frac{1}{2}}}{T - \frac{1}{2}T^{\frac{1}{2}}} \leq \widehat{\rho} \leq \frac{T - \frac{1}{2}T^{\frac{1}{2}}}{\frac{1}{2}T^{\frac{1}{2}}}$, we have
Due to this, Algorithm (ref) goes to Line 3 instead of Line 5 or Line 7. The total numbers of treated and control units are given by (ref), which we write again as follows,
On the other hand, since $\rho > \frac{T - \frac{1}{2}T^{\frac{1}{2}}}{\frac{1}{2}T^{\frac{1}{2}}}$, following (ref) we have
Note that,
Conditional on event $\mathcal{E}$, we have
where the inequality is because $\frac{\widehat{\rho}}{\widehat{\rho}+1} \frac{T}{T-\frac{1}{2}T^{\frac{1}{2}}} - 1$ is increasing in $\widehat{\rho}$ and equals $0$ when $\widehat{\rho} = \frac{T - \frac{1}{2}T^{\frac{1}{2}}}{\frac{1}{2}T^{\frac{1}{2}}}$.
So conditional on event $\mathcal{E}$, we have $\left\vert \frac{T(1)}{T^*(1)} - 1 \right\vert \to 0$ as $T \to +\infty$. In addition, $1 - \Pr(\mathcal{E}) = \frac{\kappa(1) + \kappa(0)}{T^{\varepsilon}} \to 0$ as $T \to +\infty$. Combining these two, we have $\frac{T(1)}{T^*(1)} \xrightarrow{p} 1$ as $T \to +\infty$.
Conditional on event $\mathcal{E}$, we have
where the first inequality is because $\frac{1}{\widehat{\rho}+1} \frac{T}{\frac{1}{2}T^{\frac{1}{2}}} - 1$ is decreasing in $\widehat{\rho}$ and equals $0$ when $\widehat{\rho} = \frac{T - \frac{1}{2}T^{\frac{1}{2}}}{\frac{1}{2}T^{\frac{1}{2}}}$.
So conditional on event $\mathcal{E}$, we have $\left\vert \frac{T(0)}{T^*(0)} - 1 \right\vert \to 0$ as $T \to +\infty$. In addition, $1 - \Pr(\mathcal{E}) = \frac{\kappa(1) + \kappa(0)}{T^{\varepsilon}} \to 0$ as $T \to +\infty$. Combining these two, we have $\frac{T(0)}{T^*(0)} \xrightarrow{p} 1$ as $T \to +\infty$.
To conclude, in all cases, as $T \to +\infty$,
This proves Condition (ref), and completes the proof of Lemma (ref) when $M=2$. \halmos \endproof
\proof{Proof of Lemma (ref) when $M \geq 3$.} We can explicitly verify that Condition (ref) in Lemma (ref) is satisfied. Below we prove Condition (ref).
We borrow the same clean event analysis as in the proof of Theorem (ref). To proceed with the clean event analysis, suppose there are two length-$T$ arrays for the treated and the control, respectively, with each value being an independent and identically distributed copy of the representative random variables $Y(1)$ and $Y(0)$, respectively. When Algorithm (ref) suggests to conduct an $m$-th stage experiment parameterized by $(T_m(1), T_m(0))$, the observations from the $m$-th stage experiment are generated by reading the next $T_m(1)$ values from the treated array, and the next $T_m(0)$ values from the control array.
Even though Algorithm (ref) adaptively determines the number of treated and control units, it is always the first few values of of the two arrays that are read. For any $m \leq M-1$, let $\widehat{\psi}^2_m(1)$ and $\widehat{\psi}^2_{m}(0)$ be the sample variance estimators obtained from reading the first $\frac{\beta_m}{2}T^{\frac{m}{M}}$ values in the treated array and control array, respectively. Depending on the execution of Algorithm (ref), only a few of the sample variance estimators $\widehat{\sigma}^2_m(1)$ or $\widehat{\sigma}^2_m(0)$ are calculated. When one sample variance estimator $\widehat{\sigma}^2_m(1)$ or $\widehat{\sigma}^2_m(0)$ is calculated following Algorithm (ref), it is equivalent to reading the corresponding $\widehat{\psi}^2_m(1)$ or $\widehat{\psi}^2_m(0)$ from the array.
Define the following events. For any $m \leq M-1$, define
Denote the intersect of all above events as $\mathcal{E}$, i.e.,
Then due to union bound,
We further have
where the inequality is due to Lemma (ref).
Conditional on the event $\mathcal{E}$, we have, for any $m \leq M-1$,
Since $\sigma(1), \sigma(0) > 0$, we can denote $\rho = \frac{\sigma(1)}{\sigma(0)}$. For any $m \leq M-1$, when $\widehat{\sigma}^2_m(1)$ and $\widehat{\sigma}^2_m(0)$ are calculated during Algorithm (ref), $\widehat{\sigma}^2_m(1) = \widehat{\psi}^2_m(1)$ and $\widehat{\sigma}^2_m(0) = \widehat{\psi}^2_m(0)$. Conditional on the event $\mathcal{E}$, due to (ref) and (ref), and given that $\sigma(1), \sigma(0) > 0$, we have $\widehat{\sigma}^2_m(1), \widehat{\sigma}^2_m(0) > 0$. Then we can denote $\widehat{\rho}_m = \frac{\widehat{\sigma}_m(1)}{\widehat{\sigma}_m(0)}$.
In the remaining of the analysis, we distinguish several cases and discuss these cases separately. Recall that $\widehat{\rho}_m = \frac{\widehat{\sigma}_m(1)}{\widehat{\sigma}_m(0)}$, and that $\rho = \frac{\sigma(1)}{\sigma(0)}$. Without loss of generality, assume
\noindentCase 1:
Case 1.1:
In this case,
So Algorithm (ref) goes to Line (ref) in the $1$-st stage experiment. Then we have
We further distinguish two cases.
First, $\rho < \frac{T - \frac{1}{2} \beta_1 T^{\frac{1}{M}}}{\frac{1}{2} \beta_1 T^{\frac{1}{M}}}$. Note that, conditional on $\mathcal{E}$,
Note also that,
where the first inequality is due to (ref); the second inequality is due to Lemma (ref); the last inequality is due to Lemma (ref).
As a result,
Conditional on event $\mathcal{E}$, we have
where the inequality is because $\big( \frac{1}{\rho}+1 \big) \frac{T-\frac{1}{2} \beta_1 T^{\frac{1}{M}}}{T} - 1$ is decreasing in $\rho$ and equals $0$ when $\rho = \frac{T - \frac{1}{2}\beta_1 T^{\frac{1}{M}}}{\frac{1}{2}\beta_1 T^{\frac{1}{M}}}$; and due to (ref) we have a lower bound for $\rho$.
So conditional on event $\mathcal{E}$, we have $\left\vert \frac{T(1)}{T^*(1)} - 1 \right\vert \to 0$ as $T \to +\infty$. In addition, $1 - \Pr(\mathcal{E}) = (M-1) \frac{\kappa(1) + \kappa(0)}{T^{\varepsilon}} \to 0$ as $T \to +\infty$. Combining these two, we have $\frac{T(1)}{T^*(1)} \xrightarrow{p} 1$ as $T \to +\infty$.
Conditional on event $\mathcal{E}$, we have
where the first inequality is because $\big( \rho+1 \big) \frac{\frac{1}{2} \beta_1 T^{\frac{1}{M}}}{T} - 1$ is increasing in $\rho$ and equals $0$ when $\rho = \frac{T - \frac{1}{2}\beta_1 T^{\frac{1}{M}}}{\frac{1}{2}\beta_1 T^{\frac{1}{M}}}$, the second inequality is because for any $\delta \in [0,1), 1- \delta \leq \sqrt{\frac{1-\delta}{1+\delta}}$.
So conditional on event $\mathcal{E}$, we have $\left\vert \frac{T(0)}{T^*(0)} - 1 \right\vert \to 0$ as $T \to +\infty$. In addition, $1 - \Pr(\mathcal{E}) = (M-1) \frac{\kappa(1) + \kappa(0)}{T^{\varepsilon}} \to 0$ as $T \to +\infty$. Combining these two, we have $\frac{T(0)}{T^*(0)} \xrightarrow{p} 1$ as $T \to +\infty$.
Second, if $\rho \geq \frac{T - \frac{1}{2} \beta_1 T^{\frac{1}{M}}}{\frac{1}{2} \beta_1 T^{\frac{1}{M}}}$, then we have
So conditional on event $\mathcal{E}$, we have $\frac{T(1)}{T^*(1)} = 1$. In addition, $1 - \Pr(\mathcal{E}) = (M-1) \frac{\kappa(1) + \kappa(0)}{T^{\varepsilon}} \to 0$ as $T \to +\infty$. Combining these two, we have $\frac{T(1)}{T^*(1)} \xrightarrow{p} 1$ as $T \to +\infty$. Similarly, $\frac{T(0)}{T^*(0)} \xrightarrow{p} 1$ as $T \to +\infty$.
Case 1.2:
In this case,
So Algorithm (ref) goes to Line (ref) in the $1$-st stage experiment. Then we have
We further distinguish two cases.
First, $\rho < \frac{T - \frac{1}{2} \beta_1 T^{\frac{1}{M}}}{\frac{1}{2} \beta_1 T^{\frac{1}{M}}}$. Note that, conditional on $\mathcal{E}$,
where the first inequality is due to (ref) and (ref); the second inequality is due to the condition of Case 1.2; the third inequality is due to Lemma (ref); the last inequality is due to Lemma (ref).
As a result,
Conditional on event $\mathcal{E}$, we have
where the inequality is due to (ref) and (ref).
So conditional on event $\mathcal{E}$, we have $\left\vert \frac{T(1)}{T^*(1)} - 1 \right\vert \to 0$ as $T \to +\infty$. In addition, $1 - \Pr(\mathcal{E}) = (M-1) \frac{\kappa(1) + \kappa(0)}{T^{\varepsilon}} \to 0$ as $T \to +\infty$. Combining these two, we have $\frac{T(1)}{T^*(1)} \xrightarrow{p} 1$ as $T \to +\infty$. Similarly, we have $\frac{T(0)}{T^*(0)} \xrightarrow{p} 1$ as $T \to +\infty$.
Second, if $\rho \geq \frac{T - \frac{1}{2} \beta_1 T^{\frac{1}{M}}}{\frac{1}{2} \beta_1 T^{\frac{1}{M}}}$, then we have
Note that, conditional on $\mathcal{E}$,
Conditional on event $\mathcal{E}$, we have
where the first inequality is because $\frac{\widehat{\rho}_1}{\widehat{\rho}_1+1} \frac{T}{T - \frac{1}{2} \beta_1 T^{\frac{1}{M}}} - 1$ is increasing in $\widehat{\rho}_1$ and equals $0$ when $\widehat{\rho}_1 = \frac{T - \frac{1}{2}\beta_1 T^{\frac{1}{M}}}{\frac{1}{2}\beta_1 T^{\frac{1}{M}}}$, the second inequality is because for any $\delta \in [0,1), 1- \delta \leq \sqrt{\frac{1-\delta}{1+\delta}}$ and we lower bound $\widehat{\rho}_1$ with $\frac{T - \frac{1}{2} \beta_1 T^{\frac{1}{M}}}{\frac{1}{2} \beta_1 T^{\frac{1}{M}}} ({1-2^{\frac{1}{2}} \beta_1^{-\frac{1}{2}} T^{-\frac{1}{2M} + \frac{\varepsilon}{2}}})$.
So conditional on event $\mathcal{E}$, we have $\left\vert \frac{T(1)}{T^*(1)} - 1 \right\vert \to 0$ as $T \to +\infty$. In addition, $1 - \Pr(\mathcal{E}) = (M-1) \frac{\kappa(1) + \kappa(0)}{T^{\varepsilon}} \to 0$ as $T \to +\infty$. Combining these two, we have $\frac{T(1)}{T^*(1)} \xrightarrow{p} 1$ as $T \to +\infty$.
Conditional on event $\mathcal{E}$, we have
where the first inequality is because $\frac{1}{\widehat{\rho}_1+1} \frac{T}{\frac{1}{2} \beta_1 T^{\frac{1}{M}}} - 1$ is decreasing in $\widehat{\rho}_1$ and equals $0$ when $\widehat{\rho}_1 = \frac{T - \frac{1}{2}\beta_1 T^{\frac{1}{M}}}{\frac{1}{2}\beta_1 T^{\frac{1}{M}}}$, the second inequality is because for any $\delta \in [0,1), 1- \delta \leq \sqrt{\frac{1-\delta}{1+\delta}}$ and we lower bound $\widehat{\rho}_1$ with $\frac{T - \frac{1}{2} \beta_1 T^{\frac{1}{M}}}{\frac{1}{2} \beta_1 T^{\frac{1}{M}}} ({1-2^{\frac{1}{2}} \beta_1^{-\frac{1}{2}} T^{-\frac{1}{2M} + \frac{\varepsilon}{2}}})$.
So conditional on event $\mathcal{E}$, we have $\left\vert \frac{T(0)}{T^*(0)} - 1 \right\vert \to 0$ as $T \to +\infty$. In addition, $1 - \Pr(\mathcal{E}) = (M-1) \frac{\kappa(1) + \kappa(0)}{T^{\varepsilon}} \to 0$ as $T \to +\infty$. Combining these two, we have $\frac{T(0)}{T^*(0)} \xrightarrow{p} 1$ as $T \to +\infty$.
\noindentCase 2:
Due to (ref) we know that $\widehat{\sigma}_1(1) \geq \widehat{\sigma}_1(0)$. In Case 2 we immediately have
So Algorithm (ref) goes to Line (ref) in the 1-st stage experiment. We further distinguish two cases.
\noindentCase 2.1:
In this case,
So Algorithm (ref) goes to Line (ref) in the $2$-nd stage experiment. Then we have
Note that, as $T \to +\infty$,
where the first inequality is due to (ref) and (ref); the second inequality is due to the condition of Case 2; the equality holds when $T \to +\infty$; the last inequality is because $\beta_1 T^{\frac{1}{M}} < \beta_2 T^{\frac{2}{M}}$.
Note also that,
where the first inequality is due to (ref) and (ref); the second inequality is due to the condition of Case 2.1; the third inequality is due to Lemma (ref); the last inequality is due to Lemma (ref).
As a result, as $T \to +\infty$, we have $\frac{\frac{1}{2} \beta_1 T^{\frac{1}{M}}}{T - \frac{1}{2} \beta_1 T^{\frac{1}{M}}} < \rho < \frac{T - \frac{1}{2} \beta_1 T^{\frac{1}{M}}}{\frac{1}{2} \beta_1 T^{\frac{1}{M}}}$, so
Conditional on event $\mathcal{E}$, we have
where the inequality is because $\big( \frac{1}{\rho}+1 \big) \frac{T-\frac{1}{2} \beta_2 T^{\frac{2}{M}}}{T} - 1$ is decreasing in $\rho$ and equals $0$ when $\rho = \frac{T - \frac{1}{2}\beta_2 T^{\frac{2}{M}}}{\frac{1}{2}\beta_2 T^{\frac{2}{M}}}$; and we lower bound $\rho$ by $\frac{T - \frac{1}{2} \beta_2 T^{\frac{2}{M}}}{\frac{1}{2} \beta_2 T^{\frac{2}{M}}} \cdot \sqrt{\frac{1-2^{\frac{1}{2}} \beta_2^{-\frac{1}{2}} T^{-\frac{2}{2M} + \frac{\varepsilon}{2}}}{1+2^{\frac{1}{2}} \beta_2^{-\frac{1}{2}} T^{-\frac{2}{2M} + \frac{\varepsilon}{2}}}}$.
So conditional on event $\mathcal{E}$, we have $\left\vert \frac{T(1)}{T^*(1)} - 1 \right\vert \to 0$ as $T \to +\infty$. In addition, $1 - \Pr(\mathcal{E}) = (M-1) \frac{\kappa(1) + \kappa(0)}{T^{\varepsilon}} \to 0$ as $T \to +\infty$. Combining these two, we have $\frac{T(1)}{T^*(1)} \xrightarrow{p} 1$ as $T \to +\infty$.
Conditional on event $\mathcal{E}$, we have
where the first inequality is because $\big( \rho+1 \big) \frac{\frac{1}{2} \beta_2 T^{\frac{2}{M}}}{T} - 1$ is increasing in $\rho$ and equals $0$ when $\rho = \frac{T - \frac{1}{2}\beta_2 T^{\frac{2}{M}}}{\frac{1}{2}\beta_2 T^{\frac{2}{M}}}$, the second inequality is because for any $\delta \in [0,1), 1- \delta \leq \sqrt{\frac{1-\delta}{1+\delta}}$.
So conditional on event $\mathcal{E}$, we have $\left\vert \frac{T(0)}{T^*(0)} - 1 \right\vert \to 0$ as $T \to +\infty$. In addition, $1 - \Pr(\mathcal{E}) = (M-1) \frac{\kappa(1) + \kappa(0)}{T^{\varepsilon}} \to 0$ as $T \to +\infty$. Combining these two, we have $\frac{T(0)}{T^*(0)} \xrightarrow{p} 1$ as $T \to +\infty$.
\noindentCase 2.2:
In this case,
So Algorithm (ref) goes to Line (ref) in the $2$-nd stage experiment. Then we have
Note that, as $T \to +\infty$,
where the first inequality is due to (ref) and (ref); the second inequality is due to the condition of Case 2.2; the last inequality is because $\beta_1 T^{\frac{1}{M}} < \beta_2 T^{\frac{2}{M}}$ and holds as $T \to +\infty$.
Note also that,
where the first inequality is due to (ref) and (ref); the second inequality is due to the condition of Case 2.2; the third inequality is due to Lemma (ref); the last inequality is due to Lemma (ref).
As a result, as $T \to +\infty$,
Conditional on event $\mathcal{E}$, we have
where the inequality is due to (ref) and (ref).
So conditional on event $\mathcal{E}$, we have $\left\vert \frac{T(1)}{T^*(1)} - 1 \right\vert \to 0$ as $T \to +\infty$. In addition, $1 - \Pr(\mathcal{E}) = (M-1) \frac{\kappa(1) + \kappa(0)}{T^{\varepsilon}} \to 0$ as $T \to +\infty$. Combining these two, we have $\frac{T(1)}{T^*(1)} \xrightarrow{p} 1$ as $T \to +\infty$. Similarly, we have $\frac{T(0)}{T^*(0)} \xrightarrow{p} 1$ as $T \to +\infty$.
\noindentCase $\bm{m}$ (when $m \leq M-2$):
Due to the condition of Case $m$, we immediately have
On the other hand, since
where the first and second inequalities are due to (ref) and (ref); the third inequality is due to (ref); the fourth inequality is due to Lemma (ref); the last inequality is due to Lemma (ref). Due to the above sequence of inequalities, we have $\frac{1}{\widehat{\rho}_{m-1}} \leq \frac{T - \frac{1}{2}\beta_m T^{\frac{m}{M}}}{\frac{1}{2}\beta_m T^{\frac{m}{M}}}$, which leads to
So Algorithm (ref) goes to Line (ref) in the (m-1)-th stage experiment. We further distinguish two cases.
\noindentCase $\bm{m}$.1: In addition to the conditions in Case $m$ above, we also have
Similar to the analysis in Case 2.1, we proceed with the following analysis. In Case $m$.1,
So Algorithm (ref) goes to Line (ref) in the $m$-th stage experiment. Then we have
Note that, as $T \to +\infty$,
where the first inequality is due to (ref) and (ref); the second inequality is due to the condition of Case m; the equality holds when $T \to +\infty$; the last inequality is because $\beta_1 T^{\frac{1}{M}} < \beta_m T^{\frac{m}{M}}$.
Note also that,
where the first inequality is due to (ref) and (ref); the second inequality is due to the condition of Case m.1; the third inequality is due to Lemma (ref); the last inequality is due to Lemma (ref).
As a result, as $T \to +\infty$, we have $\frac{\frac{1}{2} \beta_1 T^{\frac{1}{M}}}{T - \frac{1}{2} \beta_1 T^{\frac{1}{M}}} < \rho < \frac{T - \frac{1}{2} \beta_1 T^{\frac{1}{M}}}{\frac{1}{2} \beta_1 T^{\frac{1}{M}}}$, so
Conditional on event $\mathcal{E}$, we have
where the inequality is because $\big( \frac{1}{\rho}+1 \big) \frac{T-\frac{1}{2} \beta_m T^{\frac{m}{M}}}{T} - 1$ is decreasing in $\rho$ and equals $0$ when $\rho = \frac{T - \frac{1}{2}\beta_m T^{\frac{m}{M}}}{\frac{1}{2}\beta_m T^{\frac{m}{M}}}$; and we lower bound $\rho$ by $\frac{T - \frac{1}{2} \beta_m T^{\frac{m}{M}}}{\frac{1}{2} \beta_m T^{\frac{m}{M}}} \cdot \sqrt{\frac{1-2^{\frac{1}{2}} \beta_m^{-\frac{1}{2}} T^{-\frac{m}{2M} + \frac{\varepsilon}{2}}}{1+2^{\frac{1}{2}} \beta_m^{-\frac{1}{2}} T^{-\frac{m}{2M} + \frac{\varepsilon}{2}}}}$.
So conditional on event $\mathcal{E}$, we have $\left\vert \frac{T(1)}{T^*(1)} - 1 \right\vert \to 0$ as $T \to +\infty$. In addition, $1 - \Pr(\mathcal{E}) = (M-1) \frac{\kappa(1) + \kappa(0)}{T^{\varepsilon}} \to 0$ as $T \to +\infty$. Combining these two, we have $\frac{T(1)}{T^*(1)} \xrightarrow{p} 1$ as $T \to +\infty$.
Conditional on event $\mathcal{E}$, we have
where the first inequality is because $\big( \rho+1 \big) \frac{\frac{1}{2} \beta_m T^{\frac{m}{M}}}{T} - 1$ is increasing in $\rho$ and equals $0$ when $\rho = \frac{T - \frac{1}{2}\beta_m T^{\frac{m}{M}}}{\frac{1}{2}\beta_m T^{\frac{m}{M}}}$, the second inequality is because for any $\delta \in [0,1), 1- \delta \leq \sqrt{\frac{1-\delta}{1+\delta}}$.
So conditional on event $\mathcal{E}$, we have $\left\vert \frac{T(0)}{T^*(0)} - 1 \right\vert \to 0$ as $T \to +\infty$. In addition, $1 - \Pr(\mathcal{E}) = (M-1) \frac{\kappa(1) + \kappa(0)}{T^{\varepsilon}} \to 0$ as $T \to +\infty$. Combining these two, we have $\frac{T(0)}{T^*(0)} \xrightarrow{p} 1$ as $T \to +\infty$.
\noindentCase $\bm{m}$.2: In addition to the conditions in Case $m$ above, we also have
Similar to the analysis in Case 2.2, we proceed with the following analysis. In Case $m$.2,
So Algorithm (ref) goes to Line (ref) in the $m$-th stage experiment. Then we have
Note that, as $T \to +\infty$,
where the first inequality is due to (ref) and (ref); the second inequality is due to the condition of Case m.2; the last inequality is because $\beta_1 T^{\frac{1}{M}} < \beta_m T^{\frac{m}{M}}$ and holds as $T \to +\infty$.
Note also that,
where the first inequality is due to (ref) and (ref); the second inequality is due to the condition of Case m.2; the third inequality is due to Lemma (ref); the last inequality is due to Lemma (ref).
As a result, as $T \to +\infty$,
Conditional on event $\mathcal{E}$, we have
where the inequality is due to (ref) and (ref).
So conditional on event $\mathcal{E}$, we have $\left\vert \frac{T(1)}{T^*(1)} - 1 \right\vert \to 0$ as $T \to +\infty$. In addition, $1 - \Pr(\mathcal{E}) = (M-1) \frac{\kappa(1) + \kappa(0)}{T^{\varepsilon}} \to 0$ as $T \to +\infty$. Combining these two, we have $\frac{T(1)}{T^*(1)} \xrightarrow{p} 1$ as $T \to +\infty$. Similarly, we have $\frac{T(0)}{T^*(0)} \xrightarrow{p} 1$ as $T \to +\infty$.
\noindentCase ($\bm{M-1}$):
Due to the condition of Case ($M-1$), we immediately have
On the other hand, since
where the first and second inequalities are due to (ref) and (ref); the third inequality is due to (ref); the fourth inequality is due to Lemma (ref); the last inequality is due to Lemma (ref). Due to the above sequence of inequalities, we have $\frac{1}{\widehat{\rho}_{M-2}} \leq \frac{T - \frac{1}{2}\beta_{M-1} T^{\frac{M-1}{M}}}{\frac{1}{2}\beta_{M-1} T^{\frac{M-1}{M}}}$, which leads to
So Algorithm (ref) goes to Line (ref) in the $(M-2)$-th stage experiment. Then Algorithm (ref) goes to Line (ref) in the last stage. We further distinguish two cases.
\noindentCase ($\bm{M-1}$).1: In addition to the conditions in Case $(M-1)$ above, we also have
Similar to the analysis in Case $m$.1, we proceed with the following analysis. In Case $(M-1)$.1,
So Algorithm (ref) goes to Line (ref) in the $(M-1)$-th stage experiment, and we have
Note that, as $T \to +\infty$,
where the first inequality is due to (ref) and (ref); the second inequality is due to the condition of Case (M-1); the equality holds when $T \to +\infty$; the last inequality is because $\beta_1 T^{\frac{1}{M}} < \beta_{M-1} T^{\frac{M-1}{M}}$.
Note also that,
where the first inequality is due to (ref) and (ref); the second inequality is due to the condition of Case (M-1).1; the third inequality is due to Lemma (ref); the last inequality is due to Lemma (ref).
As a result, as $T \to +\infty$, we have $\frac{\frac{1}{2} \beta_1 T^{\frac{1}{M}}}{T - \frac{1}{2} \beta_1 T^{\frac{1}{M}}} < \rho < \frac{T - \frac{1}{2} \beta_1 T^{\frac{1}{M}}}{\frac{1}{2} \beta_1 T^{\frac{1}{M}}}$, so
Conditional on event $\mathcal{E}$, we have
where the inequality is because $\big( \frac{1}{\rho}+1 \big) \frac{T-\frac{1}{2} \beta_{M-1} T^{\frac{M-1}{M}}}{T} - 1$ is decreasing in $\rho$ and equals $0$ when $\rho = \frac{T - \frac{1}{2}\beta_{M-1} T^{\frac{M-1}{M}}}{\frac{1}{2}\beta_{M-1} T^{\frac{M-1}{M}}}$; and we lower bound $\rho$ by $\frac{T - \frac{1}{2} \beta_{M-1} T^{\frac{M-1}{M}}}{\frac{1}{2} \beta_{M-1} T^{\frac{M-1}{M}}} \cdot \sqrt{\frac{1-2^{\frac{1}{2}} \beta_{M-1}^{-\frac{1}{2}} T^{-\frac{M-1}{2M} + \frac{\varepsilon}{2}}}{1+2^{\frac{1}{2}} \beta_{M-1}^{-\frac{1}{2}} T^{-\frac{M-1}{2M} + \frac{\varepsilon}{2}}}}$.
So conditional on event $\mathcal{E}$, we have $\left\vert \frac{T(1)}{T^*(1)} - 1 \right\vert \to 0$ as $T \to +\infty$. In addition, $1 - \Pr(\mathcal{E}) = (M-1) \frac{\kappa(1) + \kappa(0)}{T^{\varepsilon}} \to 0$ as $T \to +\infty$. Combining these two, we have $\frac{T(1)}{T^*(1)} \xrightarrow{p} 1$ as $T \to +\infty$.
Conditional on event $\mathcal{E}$, we have
where the first inequality is because $\big( \rho+1 \big) \frac{\frac{1}{2} \beta_{M-1} T^{\frac{M-1}{M}}}{T} - 1$ is increasing in $\rho$ and equals $0$ when $\rho = \frac{T - \frac{1}{2}\beta_{M-1} T^{\frac{M-1}{M}}}{\frac{1}{2}\beta_{M-1} T^{\frac{M-1}{M}}}$, the second inequality is because for any $\delta \in [0,1), 1- \delta \leq \sqrt{\frac{1-\delta}{1+\delta}}$.
So conditional on event $\mathcal{E}$, we have $\left\vert \frac{T(0)}{T^*(0)} - 1 \right\vert \to 0$ as $T \to +\infty$. In addition, $1 - \Pr(\mathcal{E}) = (M-1) \frac{\kappa(1) + \kappa(0)}{T^{\varepsilon}} \to 0$ as $T \to +\infty$. Combining these two, we have $\frac{T(0)}{T^*(0)} \xrightarrow{p} 1$ as $T \to +\infty$.
\noindentCase ($\bm{M-1}$).2: In addition to the conditions in Case $(M-1)$ above, we also have
Due to the condition of Case ($M-1$).2, we immediately have
On the other hand, since
where the first and second inequalities are due to (ref) and (ref); the third inequality is due to (ref); the fourth inequality is due to Lemma (ref); the last inequality is due to Lemma (ref). Due to the above sequence of inequalities, we have $\frac{1}{\widehat{\rho}_{M-1}} \leq \frac{T - \frac{1}{2}\beta_{M-1} T^{\frac{M-1}{M}}}{\frac{1}{2}\beta_{M-1} T^{\frac{M-1}{M}}}$, which leads to
So Algorithm (ref) goes to Line (ref) in the $(M-1)$-th stage experiment. Then we have
Note that, as $T \to +\infty$,
where the first inequality is due to (ref) and (ref); the second inequality is due to the condition of Case 2.2; the last inequality is because $\beta_1 T^{\frac{1}{M}} < \beta_m T^{\frac{m}{M}}$ and holds as $T \to +\infty$.
Note also that,
where the first inequality is due to (ref) and (ref); the second inequality is due to (ref); the third inequality is due to Lemma (ref); the last inequality is due to Lemma (ref).
As a result, as $T \to +\infty$,
Conditional on event $\mathcal{E}$, we have
where the inequality is due to (ref) and (ref).
So conditional on event $\mathcal{E}$, we have $\left\vert \frac{T(1)}{T^*(1)} - 1 \right\vert \to 0$ as $T \to +\infty$. In addition, $1 - \Pr(\mathcal{E}) = (M-1) \frac{\kappa(1) + \kappa(0)}{T^{\varepsilon}} \to 0$ as $T \to +\infty$. Combining these two, we have $\frac{T(1)}{T^*(1)} \xrightarrow{p} 1$ as $T \to +\infty$. Similarly, we have $\frac{T(0)}{T^*(0)} \xrightarrow{p} 1$ as $T \to +\infty$.
To conclude, in all cases, we have shown that $\frac{T(1)}{T^*(1)} \xrightarrow{p} 1$ and $\frac{T(0)}{T^*(0)} \xrightarrow{p} 1$ as $T \to +\infty$. \halmos \endproof
\proof{Proof of Theorem (ref).} To use the martingale central limit theorem to prove Theorem (ref), we adopt the following “tape” view of each run of the adaptive Neyman allocation algorithm. For any fixed $T$, suppose there are two length-$T$ arrays for the treated and the control, respectively, with each value being an independent and identically distributed copy of the representative random variables $Y(1)$ and $Y(0)$, respectively. When Algorithm (ref) or Algorithm (ref) assigns treatment and control to unit $t$, it reads the corresponding $Y_t(1)$ or $Y_t(0)$ from one of the two arrays. See Table (ref) for an illustration.
We can also take a “sequential” view of the completely randomized design. For a completely randomized experiment involving $T_m = T_m(1)+T_m(0)$ units, with $T_m(1)$ and $T_m(0)$ units in the treatment and control groups, respectively, we conduct the sequential experiment as follows. The first unit is randomly assigned into the treatment group with probability $\frac{T_m(1)}{T_m}$ and control group with probability $\frac{T_m(0)}{T_m}$. When there are already $N(1) \leq T_m(1)$ and $N(0) \leq T_m(0)$ units in the treated and control groups, the next unit is randomly assigned into the treatment group with probability $\frac{T_m(1)-N(1)}{T_m-N(1)-N(0)}$ and control group with probability $\frac{T_m(0)-N(0)}{T_m-N(1)-N(0)}$.
We now define $\mathscr{F}_t = \sigma(W_1, Y_1(W_1), ..., W_t, Y_t(W_t))$ to be a filtration defined on the first $t$ treatment assignments and observed outcomes. Denote the following random variables
Note that $X_t(1)$ and $X_t(0)$ are not the sample means. On the denominator, $T^*(1)$ and $T^*(0)$ are deterministic quantities as defined in (ref) when $M=2$ or (ref) when $M \geq 3$.
We first show that $\{X_t(1)\}_{t=1,2,...}$ (and $\{X_t(0)\}_{t=1,2,...}$) is a martingale difference sequence. To see this, note that
where the second equality holds because $Y_t(1)$ is independent of the filtration $\mathscr{F}_{t-1}$.
Then, for any constants $\alpha(1), \alpha(0) > 0$, denote $X_t = \alpha(1) X_t(1) + \alpha(0) X_t(0)$. We see that $\mathrm{E}\big[X_t \big\vert \mathscr{F}_{t-1}\big] = 0$. So $\{X_t\}_{t=1,2,...}$ is a martingale difference sequence.
Now we check the first condition in Lemma (ref).
where the second equality is because $\text{\usefont{U}{bbm}{m}{n}1}\{W_t=1\} \text{\usefont{U}{bbm}{m}{n}1}\{W_t=0\} = 0$; the last equality is because $Y_t(1)$ and $Y_t(0)$ are independent of the filtration $\mathscr{F}_{t-1}$ so $\mathrm{E}\big[ \big(Y_t(1) - \mathrm{E}[Y(1)]\big)^2 \big\vert \mathscr{F}_{t-1} \big] = \sigma^2(1)$ and $\mathrm{E}\big[ \big(Y_t(0) - \mathrm{E}[Y(0)]\big)^2 \big\vert \mathscr{F}_{t-1} \big] = \sigma^2(0)$.
Using Lemma (ref), as $T \to +\infty$, we have
So this satisfies the first condition in Lemma (ref).
Now we check the second condition in Lemma (ref). Denote $\alpha = \sqrt{\alpha^2(1) + \alpha^2(0)}$. Note that, for any $\varepsilon > 0$ and any $t \in [T]$,
where the first inequality is because either $\vert X_t \vert \geq \varepsilon \alpha$, in which case $\text{\usefont{U}{bbm}{m}{n}1}\{ \vert X_t \vert \geq \varepsilon \alpha \} = 1 \leq \frac{\vert X_t \vert^2}{\varepsilon^2 \alpha^2}$, or $\vert X_t \vert < \varepsilon \alpha$, in which case $\text{\usefont{U}{bbm}{m}{n}1}\{ \vert X_t \vert \geq \varepsilon \alpha \} = 0 \leq \frac{\vert X_t \vert^2}{\varepsilon^2 \alpha^2}$. Note that,
where the first equality is because all the cross terms containing $\text{\usefont{U}{bbm}{m}{n}1}\{W_t=1\} \text{\usefont{U}{bbm}{m}{n}1}\{W_t=0\}$ are equal to $0$; the last equality is because $Y_t(1)$ and $Y_t(0)$ are independent of the filtration $\mathscr{F}_{t-1}$ so $\mathrm{E}\big[ \big(Y_t(1) - \mathrm{E}[Y(1)]\big)^4 \big\vert \mathscr{F}_{t-1} \big] = \sigma^4(1)$ and $\mathrm{E}\big[ \big(Y_t(0) - \mathrm{E}[Y(0)]\big)^4 \big\vert \mathscr{F}_{t-1} \big] = \sigma^4(0)$.
Using Lemma (ref), as $T \to +\infty$, we have
Due to (ref), as $T \to +\infty$, we have
So this satisfies the second condition in Lemma (ref).
Following Lemma (ref), we have that for any $\alpha(1), \alpha(0)$,
Now we would like to apply the Cramer-Wold Theorem to show a joint normal distribution. Let there be a two-dimensional multivariate normal distribution denoted as
where $\mathbb{I}_2 =
$ stands for the $2 \times 2$ identity matrix. For any $\alpha(1), \alpha(0)$, we know that
follows a normal distribution, which is the same distribution as (ref). Following the Cramer-Wold Theorem,
Finally, note that from Lemma (ref) we have
Following the Slutsky Theorem, we have
\halmos \endproof
\proof{Proof of Proposition (ref).} For any fixed $T$, suppose there are two length-$T$ arrays for the treated and the control, respectively, with each value being an independent and identically distributed copy of the representative random variables $Y(1)$ and $Y(0)$, respectively. When Algorithm (ref) or Algorithm (ref) assigns treatment or control to unit $t$, we read the next value from the treated or control array. Note that, we read the next value, instead of the $t$-th value, from the corresponding array. In other words, even though Algorithm (ref) or Algorithm (ref) adaptively determines the number of treated and control units, it is always the first few values of of the two arrays that are read. See Table (ref) for an illustration.
Note that the sample variance estimators can be expressed as
Now we focus on $\widehat{\sigma}^2(1)$. Define
Because $\mathrm{E}\big[Y(1)\big] < +\infty$ and $\mathrm{E}\big[Y^2(1)\big] < +\infty$, due to the strong law of large numbers, as $T \to +\infty$,
Then, following Lemma (ref), as $T \to +\infty$,
Since $Z_{1,T}$ (and $Z_{2,T}$) can be interpreted as taking the average of the first $T(1)$ random variables (and their squares), following Lemma (ref) and combining (ref) and (ref), we have that, as $T \to +\infty$,
So we have, as $T \to +\infty$,
Similarly, the other part $\widehat{\sigma}^2(0) \xrightarrow{p} \sigma^2(0)$ follows. \halmos \endproof
We first establish a high probability bound for the proof of Corollary (ref).
\proof{Proof of Lemma (ref).} Without loss of generality, we assume $\sigma(1) \geq \sigma(0)$ throughout the proof. We consider the following two events.
Denote $\mathcal{E} = \mathcal{E}_1(1) \cap \mathcal{E}_1(0)$. Then $\Pr(\mathcal{E}) = \Pr(\mathcal{E}_1(1) \cap \mathcal{E}_1(0)) \geq 1 - \Pr(\overline{\mathcal{E}}_1(1)) - \Pr(\overline{\mathcal{E}}_1(0))$. We further have
where the inequality is due to Lemma (ref); and the last equality is using $T_1(1) = T_1(0) = 4 C^2 T^{\frac{1}{2}} (\log{T})^{\frac{1}{2}}$
Conditional on the event $\mathcal{E}$, we have
Due to (ref) and (ref), and given that $\sigma(1), \sigma(0) > 0$, we have $\widehat{\sigma}^2_1(1), \widehat{\sigma}^2_1(0) > 0$. Denote $\rho = \frac{\sigma(1)}{\sigma(0)}$ and $\widehat{\rho} = \frac{\widehat{\sigma}_1(1)}{\widehat{\sigma}_1(0)}$.
Now we distinguish two cases, and discuss these two cases separately.
Note that, for case 2, we do not discuss $\rho = \frac{\sigma(1)}{\sigma(0)} < \frac{\frac{1}{2}\beta T^{\frac{1}{2}}}{T - \frac{1}{2}\beta T^{\frac{1}{2}}}$, because we assume that $\sigma(1) \geq \sigma(0)$. For each of the above two cases, we further discuss two sub-cases. The remaining of the proof is structured as enumerating all four cases. After enumerating all four sub-cases we finish the proof.
\noindentCase 1.1:
Since $\frac{\frac{1}{2}\beta T^{\frac{1}{2}}}{T - \frac{1}{2}\beta T^{\frac{1}{2}}} \leq \widehat{\rho} \leq \frac{T - \frac{1}{2}\beta T^{\frac{1}{2}}}{\frac{1}{2}\beta T^{\frac{1}{2}}}$, we have
Due to this, Algorithm (ref) goes to Line 3 instead of Line 5 or Line 7. The total numbers of treated and control units are given by (ref). We re-write (ref) again as follows,
Putting $(T(1), T(0))$ into (ref), we have, for any $\sigma(1), \sigma(0)$,
Due to Lemma (ref), and using (ref) and (ref),
Note that
Note also that
where the inequality is due to Lemma (ref)-(iii).
Combining (ref) --- (ref), we have
\noindentCase 1.2:
If $\widehat{\rho} > \frac{T - \frac{1}{2}\beta T^{\frac{1}{2}}}{\frac{1}{2}\beta T^{\frac{1}{2}}}$, then
Due to this, Algorithm (ref) goes to Line 7. The total numbers of treated and control units are given by $(T(1), T(0)) = (T - \frac{1}{2}\beta T^{\frac{1}{2}}, \frac{1}{2}\beta T^{\frac{1}{2}})$.
Note that,
Then we have, for any $\sigma(1), \sigma(0)$,
where the inequality is due to Lemma (ref). Combining this with (ref) and (ref) we have again
If $\widehat{\rho} < \frac{\frac{1}{2}\beta T^{\frac{1}{2}}}{T - \frac{1}{2}\beta T^{\frac{1}{2}}}$, then Algorithm (ref) goes to Line 5.
and the same analysis follows similarly.
\noindentCase 2.1:
Since $\widehat{\rho} > \frac{T - \frac{1}{2}\beta T^{\frac{1}{2}}}{\frac{1}{2}\beta T^{\frac{1}{2}}}$, we have
Due to this, Algorithm (ref) goes to Line 7. The total numbers of treated and control units are given by $(T(1), T(0)) = (T - \frac{1}{2}\beta T^{\frac{1}{2}}, \frac{1}{2}\beta T^{\frac{1}{2}})$.
Putting $(T(1), T(0))$ into (ref), we have, for any $\sigma(1), \sigma(0)$,
Due to Lemma (ref), since $\rho = \frac{\sigma(1)}{\sigma(0)} > \frac{T - \frac{1}{2}\beta T^{\frac{1}{2}}}{\frac{1}{2}\beta T^{\frac{1}{2}}}$, we know that the expression in (ref) is increasing with respect to $\rho$. So we have
where the last inequality holds because $T \geq 64 C^4 \log{T} > 16 C^4 \log{T}$.
\noindentCase 2.2:
Note that,
where the first inequality is due to (ref); the second inequality is due to $\rho > \frac{T - \frac{1}{2}\beta T^{\frac{1}{2}}}{\frac{1}{2}\beta T^{\frac{1}{2}}}$; the third inequality is due to (ref); the last inequality is due to Lemma (ref)-(ii).
The above shows that, in this case (Case 2.2),
Since $\frac{\frac{1}{2}\beta T^{\frac{1}{2}}}{T - \frac{1}{2}\beta T^{\frac{1}{2}}} \leq \widehat{\rho} \leq \frac{T - \frac{1}{2}\beta T^{\frac{1}{2}}}{\frac{1}{2}\beta T^{\frac{1}{2}}}$, we have
Due to this, Algorithm (ref) goes to Line 3 instead of Line 5 or Line 7. The total numbers of treated and control units are given by (ref), which we write again as follows,
Similar to Case 1.1, combining (ref) --- (ref), we have
To conclude, in all four cases,
\halmos \endproof
\proof{Proof of Corollary (ref).} We first show Algorithm (ref) is feasible under $\beta = 4 C^2 (\log{T})^{\frac{1}{2}}$. This is because
where the inequality is due to Lemma (ref).
Next, due to Lemma (ref), conditional on $\mathcal{E}$ that happens with probability at least $1 - \frac{4}{T^2}$,
On the other hand, on the low probability event $\overline{\mathcal{E}}$ that happens with probability at most $\frac{4}{T^2}$,
where the inequality is due to Lemma (ref).
So overall we have
where the first inequality is using the total law of probability, and upper bounding the two parts using (ref) and (ref); the second probability is upper bounding $1 - \frac{4}{T^2}$ by 1; the third inequality is because $T \geq 2$ and $C^4 \log{T} \geq 1$. \halmos \endproof
We first establish a high probability bound for the proof of Corollary (ref).
\proof{Proof of Lemma (ref).} We proceed with the similar clean event analysis as in Theorem (ref). Suppose there are two length-$T$ arrays for the treated and the control, respectively, with each value being an independent and identically distributed copy of the representative random variables $Y(1)$ and $Y(0)$, respectively. When Algorithm (ref) suggests to conduct an $m$-th stage experiment parameterized by $(T_m(1), T_m(0))$, the observations from the $m$-th stage experiment are generated by reading the next $T_m(1)$ values from the treated array, and the next $T_m(0)$ values from the control array.
Even though Algorithm (ref) adaptively determines the number of treated and control units, it is always the first few values of of the two arrays that are read. For any $m \leq M-1$, let $\widehat{\psi}^2_m(1)$ and $\widehat{\psi}^2_{m}(0)$ be the sample variance estimators obtained from reading the first $\frac{\beta_m}{2}T^{\frac{m}{M}}$ values in the treated array and control array, respectively. Depending on the execution of Algorithm (ref), only a few of the sample variance estimators $\widehat{\sigma}^2_m(1)$ or $\widehat{\sigma}^2_m(0)$ are calculated. When one sample variance estimator $\widehat{\sigma}^2_m(1)$ or $\widehat{\sigma}^2_m(0)$ is calculated following Algorithm (ref), it is equivalent to reading the corresponding $\widehat{\psi}^2_m(1)$ or $\widehat{\psi}^2_m(0)$ from the array.
Define the following events. For any $m \leq M-1$, define
Denote the intersect of all above events as $\mathcal{E}$, i.e.,
Then due to union bound,
We further have
where the first inequality is due to Lemma (ref).
Conditional on the event $\mathcal{E}$, we have, for any $m \leq M-1$,
Since $\sigma(1), \sigma(0) > 0$, we can denote $\rho = \frac{\sigma(1)}{\sigma(0)}$. For any $m \leq M-1$, when $\widehat{\sigma}^2_m(1)$ and $\widehat{\sigma}^2_m(0)$ are calculated during Algorithm (ref), $\widehat{\sigma}^2_m(1) = \widehat{\psi}^2_m(1)$ and $\widehat{\sigma}^2_m(0) = \widehat{\psi}^2_m(0)$. Conditional on the event $\mathcal{E}$, due to (ref) and (ref), and given that $\sigma(1), \sigma(0) > 0$, we have $\widehat{\sigma}^2_m(1), \widehat{\sigma}^2_m(0) > 0$. Then we can denote $\widehat{\rho}_m = \frac{\widehat{\sigma}_m(1)}{\widehat{\sigma}_m(0)}$.
In the remaining of the analysis, we distinguish several cases and discuss these cases separately. Recall that $\widehat{\rho}_1 = \frac{\widehat{\sigma}_1(1)}{\widehat{\sigma}_1(0)}$. Without loss of generality, assume
\noindentCase 1:
Case 1.1:
In this case,
So Algorithm (ref) goes to Line (ref) in the $1$-st stage experiment. Then we have
We can then express
Recall that $\rho = \frac{\sigma(1)}{\sigma(0)}$. We further distinguish two cases.
First, if $\rho < \frac{T - \frac{1}{2} \beta_1 T^{\frac{1}{M}}}{\frac{1}{2} \beta_1 T^{\frac{1}{M}}}$, then we write (ref) as
Note that,
So we have
where the first inequality is due to Lemma (ref) and (ref); the last inequality is due to Lemma (ref).
Note that, $\frac{\sigma(1) \sigma(0)}{(\sigma(1) + \sigma(0))^2} = \frac{\rho}{(\rho+1)^2}$ is a decreasing function when $\rho>1$. Note also that,
where the first inequality is due to (ref); the second inequality is due to Lemma (ref); the last inequality is due to Lemma (ref).
Then we have
Putting this into (ref) we have
where the last inequality is due to Lemma (ref).
Second, if $\rho \geq \frac{T - \frac{1}{2} \beta_1 T^{\frac{1}{M}}}{\frac{1}{2} \beta_1 T^{\frac{1}{M}}}$, then we write (ref) as
So we have
where the first inequality is due to Lemma (ref); the last inequality is due to Lemma (ref).
Combining $\rho < \frac{T - \frac{1}{2} \beta_1 T^{\frac{1}{M}}}{\frac{1}{2} \beta_1 T^{\frac{1}{M}}}$ and $\rho \geq \frac{T - \frac{1}{2} \beta_1 T^{\frac{1}{M}}}{\frac{1}{2} \beta_1 T^{\frac{1}{M}}}$, we have that in Case 1.1,
Case 1.2:
In this case,
So Algorithm (ref) goes to Line (ref) in the $1$-st stage experiment. Then we have
We can then express
Recall that, conditional on $\mathcal{E}$, (ref) and (ref) lead to
So we have
where the first inequality is due to Lemma (ref); the last inequality is due to Lemma (ref).
Note that, $\frac{\sigma(1) \sigma(0)}{(\sigma(1) + \sigma(0))^2} = \frac{\rho}{(\rho+1)^2}$ is a decreasing function when $\rho>1$. Note also that,
where the first inequality is due to (ref) and (ref); the second inequality is due to the condition of Case 1.2; the third inequality is due to Lemma (ref); the last inequality is due to Lemma (ref). Then we have
Putting this into (ref) we have that in Case 1.2,
\noindentCase 2:
Due to (ref) we know that $\widehat{\sigma}_1(1) \geq \widehat{\sigma}_1(0)$. In Case 2 we immediately have
So Algorithm (ref) goes to Line (ref) in the 1-st stage experiment. We further distinguish two cases.
\noindentCase 2.1:
In this case,
So Algorithm (ref) goes to Line (ref) in the $2$-nd stage experiment. Then we have
We can express
Note that,
where the first and the fourth inequalities are due to (ref) and (ref); the second and the third inequalities are due to the condition of Case 2.1; the last inequality is because $\beta_1 T^{\frac{1}{M}} < \beta_2 T^{\frac{2}{M}}$ so we have $48^{\frac{1}{2}} C^2 \beta_2^{-\frac{1}{2}} T^{-\frac{2}{2M}} (\log{T})^{\frac{1}{2}} < 48^{\frac{1}{2}} C^2 \beta_1^{-\frac{1}{2}} T^{-\frac{1}{2M}} (\log{T})^{\frac{1}{2}}$.
Then we have
where the first inequality is due to Lemma (ref); the last inequality is due to Lemma (ref).
Note that, $\frac{\sigma(1) \sigma(0)}{(\sigma(1) + \sigma(0))^2} = \frac{\rho}{(\rho+1)^2}$ is a decreasing function when $\rho>1$. Note also that,
where the first inequality is due to (ref); the second inequality is due to Lemma (ref); the last inequality is due to Lemma (ref).
Then we have
Putting this into (ref) we have that in Case 2.1,
\noindentCase 2.2:
In this case,
So Algorithm (ref) goes to Line (ref) in the $2$-nd stage experiment. Then we have
We can then express
Recall that, conditional on $\mathcal{E}$, (ref) and (ref) lead to
So we have
where the first inequality is due to Lemma (ref); the last inequality is due to Lemma (ref).
Note that, $\frac{\sigma(1) \sigma(0)}{(\sigma(1) + \sigma(0))^2} = \frac{\rho}{(\rho+1)^2}$ is a decreasing function when $\rho>1$. Note also that,
where the first inequality is due to (ref) and (ref); the second inequality is due to the condition of Case 2.2; the third inequality is due to Lemma (ref); the last inequality is due to Lemma (ref). Then we have
Putting this into (ref) we have that in Case 2.2,
\noindentCase $\bm{m}$ (when $m \leq M-2$):
Due to the condition of Case $m$, we immediately have
On the other hand, since
where the first and second inequalities are due to (ref) and (ref); the third inequality is due to (ref); the fourth inequality is due to Lemma (ref); the last inequality is due to Lemma (ref). Due to the above sequence of inequalities, we have $\frac{1}{\widehat{\rho}_{m-1}} \leq \frac{T - \frac{1}{2}\beta_m T^{\frac{m}{M}}}{\frac{1}{2}\beta_m T^{\frac{m}{M}}}$, which leads to
So Algorithm (ref) goes to Line (ref) in the (m-1)-th stage experiment. We further distinguish two cases.
\noindentCase $\bm{m}$.1: In addition to the conditions in Case $m$ above, we also have
Similar to the analysis in Case 2.1, we proceed with the following analysis. In Case $m$.1,
So Algorithm (ref) goes to Line (ref) in the $m$-th stage experiment. Then we have
We can express
Note that,
where the first and the fourth inequalities are due to (ref) and (ref); the second and the third inequalities are due to the condition of Case $m$.1; the last inequality is because $\beta_{m-1} T^{\frac{m-1}{M}} < \beta_m T^{\frac{m}{M}}$ so we have $48^{\frac{1}{2}} C^2 \beta_m^{-\frac{1}{2}} T^{-\frac{m}{2M}} (\log{T})^{\frac{1}{2}} < 48^{\frac{1}{2}} C^2 \beta_{m-1}^{-\frac{1}{2}} T^{-\frac{m-1}{2M}} (\log{T})^{\frac{1}{2}}$.
Then we have
where the first inequality is due to Lemma (ref); the last inequality is due to Lemma (ref).
Note that, $\frac{\sigma(1) \sigma(0)}{(\sigma(1) + \sigma(0))^2} = \frac{\rho}{(\rho+1)^2}$ is a decreasing function when $\rho>1$. Note also that,
where the first inequality is due to (ref); the second inequality is due to Lemma (ref); the last inequality is due to Lemma (ref).
Then we have
Putting this into (ref) we have that in Case $m$.1,
\noindentCase $\bm{m}$.2: In addition to the conditions in Case $m$ above, we also have
Similar to the analysis in Case 2.2, we proceed with the following analysis. In Case $m$.2,
So Algorithm (ref) goes to Line (ref) in the $m$-th stage experiment. Then we have
We can then express
Recall that, conditional on $\mathcal{E}$, (ref) and (ref) lead to
So we have
where the first inequality is due to Lemma (ref); the last inequality is due to Lemma (ref).
Note that, $\frac{\sigma(1) \sigma(0)}{(\sigma(1) + \sigma(0))^2} = \frac{\rho}{(\rho+1)^2}$ is a decreasing function when $\rho>1$. Note also that,
where the first inequality is due to (ref) and (ref); the second inequality is due to the condition of Case 2.2; the third inequality is due to Lemma (ref); the last inequality is due to Lemma (ref). Then we have
Putting this into (ref) we have that in Case $m$.2,
\noindentCase ($\bm{M-1}$):
Due to the condition of Case ($M-1$), we immediately have
On the other hand, since
where the first and second inequalities are due to (ref) and (ref); the third inequality is due to (ref); the fourth inequality is due to Lemma (ref); the last inequality is due to Lemma (ref). Due to the above sequence of inequalities, we have $\frac{1}{\widehat{\rho}_{M-2}} \leq \frac{T - \frac{1}{2}\beta_{M-1} T^{\frac{M-1}{M}}}{\frac{1}{2}\beta_{M-1} T^{\frac{M-1}{M}}}$, which leads to
So Algorithm (ref) goes to Line (ref) in the $(M-2)$-th stage experiment. Then Algorithm (ref) goes to Line (ref) in the last stage. We further distinguish two cases.
\noindentCase ($\bm{M-1}$).1: In addition to the conditions in Case $(M-1)$ above, we also have
Similar to the analysis in Case $m$.1, we proceed with the following analysis. In Case $(M-1)$.1,
So Algorithm (ref) goes to Line (ref) in the $(M-1)$-th stage experiment, and we have
We can express
Note that,
where the first and the fourth inequalities are due to \eqref{eqn:MStage:Ne