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.
31,997 characters · 6 sections · 49 citation commands
Admissibility of Completely Randomized Trials: A Large-Deviation Approach
\affil{Stanford Graduate School of Business} \pdfoutput=1 \onehalfspacing
Randomized control trials (RCTs) \begingroup \footnote{A preliminary version of this work will appear as a one-page abstract at the 26th ACM Conference on Economics and Computation (EC'25). We are grateful for helpful conversations with Po-An Wang, Junpei Komiyama, Daniel Russo, Whitney Newey, and Pepe Montiel Olea. This work was partially funded by ONR grant N-00014-24-12091.} \addtocounter{footnote}{-1} \endgroup
are considered a gold-standard method for causal inference and data-driven decision making in many fields fisher1925design,imbens2015causal. The traditional approach to RCT designs involves pre-specifying the treatment assignment mechanism before any data is collected; for example, in completely randomized trials (CRTs), the actual treatment assignment is chosen uniformly at random from all possible assignments with the same marginal treatment fractions fisher1925design. Recently, however, there has been growing concern that in settings where an analyst wants to learn about multiple treatment arms and has the option to run an adaptive experiment, standard designs such as CRTs may be inefficient relative to adaptive designs that can use data collected early in the trial to better target their experimentation budget. Such considerations can arise, for example, in online marketing chapelle2011empirical, interface design qin2023adaptive, job-search assistance caria2024adaptive, or vaccine trials wu2022partial. It is by now clear that, in some application areas, adaptive trials can vastly outperform non-adaptive designs chapelle2011empirical. What's less clear, however, is whether successful deployment of adaptive experimental designs fundamentally relies on the use of problem-specific domain knowledge (in which case basic CRTs would remain attractive as a robust, domain-agnostic baseline method), or whether there exist adaptive designs that uniformly dominate CRTs qin2022open.
Here, we provide an affirmative answer to this question in the context of the well-known best-arm identification problem ABR-10.\footnote{A similar problem is explored in the simulation literature, known as ranking and selection problem glynn2004large, hong2021review.} The goal in best-arm identification is to deploy a treatment arm at the end of the experiment with high confidence that it is the best, or achieves low degradation in welfare. We show that---for this task and using a large-deviation error metric (described further in Definition (ref) below)---there exist simple adaptive designs that dominate standard CRTs on an instance-by-instance level whenever there are at least $K \geqslant 3$ treatment arms to choose from. This implies that standard CRTs are not admissible among potentially adaptive randomized experiments in a sense analogous to that of wald1949statistical. Our result provides an affirmative answer to the second open problem posed in qin2022open.
Our dominance results are achieved within a class of “batched arm elimination” (BAE) designs, presented in Section (ref). BAE designs sequentially discard the worst-performing arms from the experiment at pre-specified checkpoints. When there are only $K=2$ treatment arms, BAE designs reduce to standard CRTs. However, when $K \geqslant 3$ arms are available, we show that simple BAE designs can uniformly outperform CRTs. Here is an example of such BAE designs: given $T$ experimental units:
These dominance results are derived from an exact characterization of the large-deviation behavior of BAE designs, which is presented in Section (ref). In Section (ref), we demonstrate our proposed design on a semi-synthetic experiment calibrated to a randomized trial by karlan2007does.
We frame our analysis in terms of a standard i.i.d. sampling model for multi-armed experimentation lattimore2020bandit. An experimenter conducts an adaptive experiment to identify the best treatment arm among $K$ arms to deploy, following sequentially assigning these $K$ treatments to $T$ experimental units. The potential outcome of assigning treatment $i \in [K] \triangleq \{1,\ldots, K\}$ to experimental unit $t \in [T] \triangleq \{1,\ldots, T\}$ is a scalar random variable $Y_{t,i}$, where larger values indicate more desirable outcomes. We assume that for each treatment $i$, the potential outcomes $(Y_{t,i})_{t\in [T] }$ are drawn i.i.d. from a distribution $P(\cdot \mid \theta_i)$ with an unknown scalar parameter $\theta_i$. If these parameters were known, the experimenter would deploy an arm with the highest expected outcome, given by $ \max_{i\in[K]} \intop y \cdot P(\mathrm{d}y\mid \theta_i). $ Let $\bm{\theta} \triangleq (\theta_1, \dots, \theta_K)$ denote the vector of unknown parameters, which we refer to as the problem instance. Since these parameters are unknown, the experimenter interacts sequentially with experimental units to learn which treatment arm is best. For the $t$-th experimental unit, the experimenter selects a treatment arm $I_{t}\in [K]$ based on the history of previously assigned treatments and observed outcomes, denoted by $ H_{t-1}\triangleq \{I_1, Y_{1, I_1}, \ldots, I_{t-1}, Y_{{t-1},I_{t-1}}\}. $ Importantly, only the outcome of the chosen treatment, $Y_{t, I_{t}}$, is observed; outcomes of the unselected treatments remain unknown. The experimenter's goal is to identify and deploy the best treatment arm among $K$ arms with high confidence by the end of the experiment.
The experimenter needs to design a policy $\pi$, which is a (potentially randomized) decision rule that governs both the sequential allocation of treatment arms to $T$ experimental units and the final deployment of a treatment arm; specifically, it consists of:
Formally, the allocation rule is a function that maps the history of past allocations and outcomes, denoted by $H_{t-1}$, and the sample size $T$ to the treatment assignment $I_t$ for the $t$-th experimental unit. Additionally, after all $T$ units have been treated, the deployment rule maps the sample size $T$ and the full history $H_T$ to the final deployed arm $\hat{I}_T$. We denote the class of all such policies by $\Pi$.
The experimenter's objective is to minimize the post-experiment utilitarian regret of the arm deployed under policy $\pi$---also known as simple regret, as termed by ABR-10:
A number of authors have shown that, for analytic tractability, it is helpful to study adaptive experiments in an asymptotic regime where errors can be characterized using large-deviation methods chernoff1959sequential,glynn2004large,kaufmann2016complexity,russo2020simple. Here, we also leverage such asymptotics, under which different exploration policies can be usefully compared in terms of the efficiency exponent given below.
We refer to a policy as admissible if there exists no other policy that beats it on an instance-by-instance level (with strict inequality for some instance).
Throughout this paper, for simplicity, we will work under a setting where there is a unique best arm and all arms have Gaussian sampling distributions with the same variance. Under this setting, the efficiency exponent of completely randomized trials is well known. Our challenge will be to find a policy that achieves a higher efficiency exponent on an instance-by-instance level.
Pure exploration problems consist of an initial adaptive data collection phase followed by a deployment step. Many different problem formulations fall under this broad framework. In this paper, we consider a “fixed-budget” model where the experiment length is given, and we seek the best possible post-experiment guarantees ABR-10, wang2023best. Another classical model for pure exploration is the “fixed-confidence” model, where the target error rate is taken as given and we seek to guarantee this error rate with the shortest possible expected experiment length chernoff1959sequential, garivier2016optimal. Furthermore, one can use different metrics to quantify errors, including the utilitarian regret of the deployed arm kasy2021adaptive. Regardless of the problem formulation, exact finite-sample analyses for these questions present significant analytical challenges; consequently, most high-profile results in this area rely on asymptotics chernoff1959sequential, glynn2004large, kaufmann2016complexity, garivier2016optimal, russo2020simple, as do we.
Among pure exploration problems, arguably the fixed-confidence setting has the longest history, dating back to the classical work of chernoff1959sequential on the sequential design of experiments, and optimality under this model is well understood. In particular, garivier2016optimal demonstrate the existence of universally asymptotically optimal experimental designs under this model: There exist designs that guarantee error rate $\delta$ and whose expected stopping time as $\delta \rightarrow 0$ has the best possible dependence for every problem instance $\bm{\theta}$. qin2024optimizing introduce a unified model that bridges the fixed-confidence setting and the classical regret minimization framework of lai1985asymptotically, unifying results from both strands of the literature.
However, while the fixed-confidence problem seems a dual to the fixed-budget problem considered here, insights derived under the fixed-confidence model cannot be directly adapted to our setting qin2022open. Unlike in the fixed-confidence model, universally asymptotically optimal policies do not exist under the fixed-budget model in full generality: degenne2023existence show that no such policy exists for Bernoulli bandits with two arms or for Gaussian bandits with $K > e^{80/3}$ arms, and degenne2023existence further conjectures that no universally asymptotically optimal policy exists even when $K\geqslant 3$ arms. Thus, the problem of optimal experimental design under the fixed-budget model is fundamentally more complicated than that under the fixed-confidence model.
Given this context---and especially the non-existence of universally optimal designs in the fixed-budget setting---we fall back on a follow-up question: Are there policies that at least dominate CRTs in terms of their efficiency exponent, or, conversely, are CRTs large-deviation admissible? This question was recently highlighted as an open problem by qin2022open;\footnote{This is the second open problem posed by qin2022open; the first one was addressed by the results of ariu2021policychoicebestarm,degenne2023existence.} and, to the best of our knowledge, remained open until this paper.
We do note that, when there are only $K = 2$ arms, CRTs are difficult to outperform---unlike the case with $K\geqslant 3$ arms. For two-armed Gaussian bandits, kaufmann2016complexity prove that Neyman allocation, i.e., CRTs with samples allocated proportionally to arm variances, is universally asymptotically optimal (under an assumption that arm variances are known a-priori). Meanwhile, for two-armed Bernoulli bandits, although degenne2023existence show that no universally optimal policy exists, wang24c prove that CRTs remain large-deviation admissible in the sense of Definition (ref).
The class of adaptive algorithms we design to beat CRTs under the fixed-budget model is an adaption of the “successive rejects” algorithm of ABR-10, and falls under the general class of batched bandit algorithms perchet2016batched. One important question left open in this paper is the question of hypothesis testing using our proposed algorithms; for example, it would useful to provide $p$-values against the null hypothesis that the chosen arm was in fact sub-optimal. Recent advances in the literature on inference from adaptively collected data include hadad2019confidence, hirano2023asymptotic, luedtke2016statistical and zhang2020inference.
Recall that we seek to design an adaptive policy that can choose a good arm among $K$ options using $T$ datapoints. Batched arm elimination (BAE) initializes the candidate arm set as $[K]$ and divides the whole sample of $T$ experimental units into $K-1$ batches. For each batch, BAE experiments on the treatment arms in the candidate set in a round-robin manner, and discards at the end of the batch an arm from the candidate set with the lowest empirical mean.
More specifically, BAE takes as inputs the sample size $T$ and $K-1$ instance-agnostic batch weights $\beta_{K}, \beta_{K-1},\ldots, \beta_2$, where the sample size $\beta_n\cdot T$ corresponds to the batch with the candidate set of $n$ arms. BAE begins by experimenting on all arms in a round-robin fashion until $K$ arms have been allocated to a total of $\beta_K\cdot T$ experimental units, after which the arm with the lowest sample mean is eliminated. It then proceeds to experiment on the remaining $K-1$ arms using another $\beta_{K-1}\cdot T$ units. This process continues iteratively, reducing the number of arms in each batch by one, until only one arm remains.
We use the following notation throughout. Let $\Sigma_{K-1}$ be the $(K-2)$-dimensional simplex with $K-1$ entries. Given this, $(\beta_K, \beta_{K-1}, \ldots, \beta_2)\in\Sigma_{K-1}$. For $t\leqslant T$, the number of experimental units that receive treatment $i$ is denoted by $N_{t,i} \triangleq \sum_{\ell=1}^{t} \mathbb{1}(I_\ell =i)$. When it is positive, we define the empirical mean reward as
When $N_{t,i}=0$, we let $m_{t,i} = 0$. We give pseudocode for the BAE procedure in Algorithm (ref).
We note that BAE is a direct generalization of the “successive rejects” algorithm proposed by ABR-10. Successive rejects is BAE with the following batch weights: \[ \left(\beta_K, \beta_{K-1}, \ldots, \beta_3\right) = \left(1, \frac{1}{K},\ldots,\frac{1}{4}\right) \cdot \frac{1}{\overline{\ln}(K)} \quad\text{and}\quad\beta_2 = 1 - \sum_{n = 3}^K \beta_{n}. \] where $\overline{\ln}(K) = \frac{1}{2} + \sum_{i = 2}^K \frac{1}{i}$. ABR-10 did not investigate uniform-dominance results as we do here. Furthermore, the set of BAE procedures we show dominate uniform sampling in fact does not include the original successive rejects algorithm. It can be verified that uniform allocation outperforms successive rejects in instances where all suboptimal arms are identical. Additionally, we note that CRTs are a speical case of BAE designs with batch weights $(1,0,\ldots,0)\in\Sigma_{K-1}$. In other words, CRTs consists of a single batch that includes the entire sample size.
Our main result shows that there exist instance-agnostic batch weights such that BAE achieves a strictly higher efficiency exponent than uniform allocation for any problem instance.
In this section, we demonstrate the universal superiority BAE designs over CRTs in terms of the efficiency exponent, providing certain sufficient conditions are met. We begin by deriving an exact characterization of the large-deviation behavior of all BAE designs. Our characterization result extends the results of wang2023best, wang24c, which focused on bounded observations and aimed to minimize the probability of misidentifying the best arm, with an emphasis on the successive rejects algorithm ABR-10 and its two variants proposed in wang2023best. In contrast, we consider unbounded Gaussian observations and aim to minimize the utilitarian regret, studying all BAE designs with any batch weights $(\beta_K, \beta_{K-1}, \ldots, \beta_2)\in\Sigma_{K-1}$.
Recall that in BAE designs (Algorithm (ref)), we use $n\in\{K,\ldots,2\}$ to denote the number of remaining arms. Let $\mathcal{J}_{\bm{\theta},n}$ denote the collection of all sets with cardinality $n$ that includes the best arm $I^* = I^*(\bm{\theta})$:
which depends on $\bm{\theta}$ since it is defined based on its best arm $I^*$. Consider such a set $J\in \mathcal{J}_{\bm{\theta},n}$; we define the set of instances where $I^*$ is the worst-performing arm in this set:
Building on the previous definitions, we introduce a quantity that captures the minimal information required for the best arm $I^*$ to be eliminated at the end of a batch, starting with $n$ arms, by the remaining $n-1$ arms:
where $d(\lambda, \theta)$ is the Kullback–Leibler (KL) divergence between two distributions parameterized by $\lambda$ and $\theta$. For two Gaussian distributions with means $\lambda$ and $\theta$ and common variance $\sigma^2$, the KL divergence $d(\lambda, \theta) = \frac{1}{2\sigma^2}(\lambda - \theta)^2$.
In addition to the minimal information quantity $\Gamma_{\bm{\theta}, n}$, we compute the proportion (of the sample size $T$) allocated to the arm eliminated at the end of the batch, starting with $n$ arms:
where the first term arises from the fact that, in the first batch, the proportion $\beta_K$ (of the sample size $T$) is uniformly allocated across $K$ arms, and the remaining terms follow the same logic. These quantities introduced above characterize the efficiency exponent of the BAE designs, as established in Lemma (ref) below. The proof of Lemma (ref) is provided in Appendix (ref).
Our next task is to establish sufficient conditions for BAE designs being universally dominating the CRT. We derive the following lower bound on the information quantity $\Gamma_{\bm{\theta},n}$ in (ref), by analyzing different instance configurations respectively.
The proof of Lemma (ref) is provided in Section (ref). By integrating this lower bound on the minimal information $\Gamma_{\bm{\theta},n}$ into the efficiency exponent in Lemma (ref), we obtain the lower bound for efficiency exponent of BAE designs.
By comparing this lower bound for efficiency exponent of BAE designs with the efficiency exponent of CRTs in Proposition (ref), we immediately derive the sufficient conditions for BAE designs to universally outperforms CRTs, based on the batch weights of BAE designs.
Recall that $w_n$, defined in (ref), is the proportion (of the sample size $T$) allocated to the arm eliminated at the end of the batch starting with $n$ arms. As the number of remaining arms $n$ decreases, the proportion $w_n$ increases, while the multiplier $\frac{n-1}{n}$ decreases. The sufficient condition above requires that the proportions allocated to all arms, weighted by their respective multipliers, exceed half the proportion each arm would receive under uniform allocation or CRTs.
We present simple BAE designs consisting of only two batches, with batch weights satisfying the sufficient conditions in (ref).
karlan2007does report results on an experiment to test whether matching gifts increase charitable giving. Their experiment includes 4 arms: A control arm, and 3 treatment arms that offer 1:1, 2:1 and 3:1 matches to potential donors (a k:1 match promises that each \$1 given will be matched by a \$k gift from a different donor). The outcome we are interested in was the total amount given. This is a sparse and skewed outcome: Only 2% of prospective donors give anything (i.e., 98% of the outcomes are 0), and conditionally on donating the mean donation is \$44 with a standard deviation of \$42. The distribution of the data presents a marked departure of the Gaussianity assumption use in our formal results, and presents us with an opportunity to investigate practical robustness of our algorithm to distributions one might face in real-world applications.
The original experiment of karlan2007does had a sample size of $n = 50,083$. Here, we start by non-parametrically fitting the data-generating distribution. For each arm we separately tally the fraction of zero outcomes and fit the density of log donation amounts for non-zero donations via kernel density estimation; and combine these to obtain a zero-inflated and skewed density for the outcomes themselves. We then simulate data from this fitted distribution to compare the performance of the following two algorithms for different sample sizes $T$:
Throughout, we pick $T$ so that no rounding is required.
Results are shown in Figure (ref). We see that both experimental designs perform comparably with smaller sample sizes (in which case they both frequently make errors); however, as the sample size grows, the error of batched arm elimination decays faster than than of the non-adaptive design. Thus, at least in this design, batched arm elimination appears to give a “safe” improvement over non-adaptive experiments: We can benefit from adaptive in high-signal regimes without compromising performance in low-signal ones.