Optimal Conditional Inference in Adaptive Experiments

Optimal Conditional Inference in Adaptive Experiments

\def\spacingset#1{ {#1}} \spacingset{0}

\onehalfspacing

{\it Keywords:} Conditional inference, sufficient statistic, bandit, selective inference, uniform inference

\onehalfspacing

Introduction

Consider a batched bandit experiment zhang2020inference,hirano2023asymptotic, where, at each batch $t = 1, 2,\ldots, T_0$, an experimenter either continues or ends the experiment. If they continue the experiment, $n_t$ units are independently sampled and independently randomized among $K$ different arms. The probability that a unit is assigned to arm $k$ in batch $t$ is denoted by $\Pi_ {tk}$, usually decided by bandit algorithms based on the history of outcomes. We let $\Pi_{t} =\diag(\Pi_{t1},\ldots, \Pi_{tK})$ collect the assignment probabilities in batch $t$. Observations assigned to arm $k$ have mean outcome $\mu_k$, collected in $\mu = [\mu_1,\ldots,\mu_K]'$, and variance $\sigma_k^2$, collected in $\Sigma = \diag (\sigma_1^2,\ldots, \sigma_K^2)$. Once the experiment ends, either at an experimenter-selected stopping time ($T<T_0$) or upon reaching the last batch ($T=T_0$), we are interested in statistical inference on some linear combination of the arm means, $\eta'\mu$, where $\eta$ may depend on the data.

The iterative nature of the experiment provides multiple opportunities for adaptive, data-driven decision-making. First, treatment assignments may be selected using bandit algorithms, which set $\Pi_ {t}$ using the results in batches $1,\ldots,t-1$. For instance, the experimenter might assign more units to arms which have produced good outcomes in the past, as in Thompson sampling. Second, the experimenter may choose whether to continue the experiment---and thus the observed number of batches $T$---based on how the results unfold. For instance, the experimenter might stop the experiment early if the results are either highly promising or overly discouraging. Third, the results of the experiment may also inform what objects the experimenter targets for inference, and hence the target parameter $\eta'\mu$. For instance, the experimenter might be interested in inference on average outcomes under an arm that performed especially well in the experiment.

Each of these forms of adaptivity presents challenges for inference. zhang2020inference and hadad2021confidence highlight that standard inference procedures that ignore the adaptive choice of $\Pi_ {t}$ can lead to invalid inference (e.g. under-coverage for confidence sets) in adaptive experiments, and propose alternative procedures which are valid in large samples provided $\eta$ and $T$ are fixed in advance. Similarly, the large and growing literature on anytime-valid inference is motivated by the long-standing observation that adaptively chosen stopping times $T$ can lead to arbitrarily poor performance for conventional inference procedures, and proposes alternatives which guarantee performance in settings where $\eta$ is fixed (see ramdasetal2023anytime for a recent review). Finally the large literatures on post-selection and selective inference Berk2013, FST15,andrews2019inference highlight that the data-driven choice of a target parameter can invalidate standard inference procedures, and proposes valid alternatives focused primarily on static settings or, equivalently, settings where $\Pi_ {t}$ and $T$ are fixed in advance.

In the batched setting we consider, there is a simple procedure available which ensures valid inference for many different rules for choosing $(T,\Pi_{1:T},\eta)=(T,\Pi_1,\ldots,\Pi_T,\eta),$ where we collectively shorthand these rules as “the experimental design.” So long as the experimental design depends only on data observed up to period $T-1$---requiring, for instance, that decisions to stop the experiment be made one period in advance, inference based on only the last batch of the experiment is guaranteed to be valid.

This “last-batch-only” approach is in one sense quite restrictive, since it discards information from all but the last batch of the experiment. At the same time, last-batch-only inference is quite flexible in that it requires no knowledge of how $ (T,\Pi_{1:T},\eta)$ are chosen, other than that $(T,\eta)$ must be chosen one batch in advance. Consequently, this approach can accommodate a variety of experimental designs, including ones where decisions are made adaptively by human decision-makers whose preferences and decision rules are not fully understood.

This paper examines the extent to which it is possible to improve last-batch-only inference while continuing to allow a very flexible class of experimental designs. We cast this problem as searching for optimal inference procedures that are valid conditionally on the experimental design $(T, \Pi_{1:T}, \eta)$. Since the last-batch-only procedure is a conditionally valid one, the optimal conditional inference procedure must weakly dominate it. One can think of focusing on conditional inference as looking for “safe free lunches” that inherit the flexibility of last-batch-only. Of course, conditionally valid intervals are able to accommodate many adaptive choices at the price of being somewhat longer than unconditionally valid ones zhang2020inference.

We start with a simple negative result. If there are no restrictions on how the design $ (T,\Pi_{1:T},\eta)$ is chosen, it is impossible to improve upon last-batch-only inference. This motivates searching for natural restrictions on the experimental design that allows for confidence sets that nontrivially use the first $T-1$ batches.

Many algorithms for selecting $(T,\Pi_{1:T},\eta)$ depend only on the contrasts between different arms, and are unaffected if we increase the average outcome for all arms by a fixed amount. This is the case, for instance, whenever the experimenter's decisions depend only on the difference in outcomes relative to a fixed treatment arm. We term experimental designs with this property “location-invariant.”

Our core result is that, in the class of location-invariant experiments, a sufficient statistic for $\mu$ is given by the mean outcomes in the last batch, together with a scalar $L$ summarizing information from earlier batches. Intuitively, $L$ represents information that is orthogonal to all pairwise arm differences over the first $T-1$ batches---and thus survives the conditioning. Conditional on these pairwise differences, the distribution of the sufficient statistic is (asymptotically) multivariate Gaussian. Thus, inference for $\eta'\mu$ based on these statistics is (asymptotically) a simple generalized least squares problem, and is optimal among the class of procedures which are conditionally valid given all pairwise differences between batch-arm means in the first $T-1$ batches. In particular, our approach dominates inference based on the last batch alone.

Two aspects of this result are worth commenting on. First, we derive it under the assumption that batch-arm means are exactly normally distributed (though results in (ref) extend to cases where batch-arm means are linear exponential family). This is a restrictive when viewed as an exact description of the data-generating process. Instead, we view it as an asymptotic description for large parts of applied practice, because (i) any batched bandit experiment is asymptotically equivalent---in the Le Cam--Hajek sense with large batch sizes---to our Gaussian model hirano2023asymptotic, and (ii) many adaptive experiments are batched in practice, due to implementation and cost concerns.\footnote{See, for instance, zhang2020inference and references therein, “We focus on the batched setting because it closely reflects many of the problem settings where bandit algorithms are applied. For example, in many mobile health and online education problems multiple users use apps / take courses simultaneously, so a batch corresponds to the number of unique users the bandit algorithm acts on at once. The batched setting is even common in online recommendations and advertising because it is impractical to update the bandit after every action if many users visit the site simultaneously.” } Thus, so long as one considers a batched bandit experiment with large batch sizes, our finite-sample optimality results for Gaussian data translate to---and should be viewed as---asymptotic optimality results for non-Gaussian data. Moreover, the optimal procedure in the Gaussian limit experiment suggests a feasible procedure applicable to data without distributional assumptions. Indeed, we show that these feasible confidence intervals have uniformly correct asymptotic coverage over a large class of non-Gaussian data generating processes.\footnote{These asymptotic results were already present in Appendix C of the first draft of this paper (September, 2023, arXiv:2309.12162v1). Independently, later work on bandit-experiment asymptotics niu2025assumption employs closely related proof techniques, showing asymptotics for a wider class of statistics. See (ref) for additional discussion. }

Second, because we allow all designs that satisfy location-invariance, our optimal inference procedure conditions on all batch-arm mean differences. In some cases, however, the information contained in $ (T,\Pi_{1:T},\eta)$ may be much coarser than all batch-arm mean differences (though not in all cases: we show that if $(T, \Pi_{1:T}, \eta)$ is generated by Thompson sampling, conditional validity given the design requires conditioning on all batch-arm mean differences). When the information contained in $ (T,\Pi_{1:T},\eta)$ is known to be coarser, we may exploit this knowledge to derive more powerful conditional inference procedures. To illustrate, we consider settings where the rules used to determine $(T,\Pi_ {1:T},\eta)$ are fully known and can be expressed in terms of a finite number of linear-in-data inequalities (that is, settings where these $ (T,\Pi_{1:T},\eta)$ depend on the experimental results only through a collection of polyhedral events). This holds, for instance, when $\Pi_{1:T}$ is constructed using an $\varepsilon$-greedy algorithm and $\eta$ selects the best-performing arm. In such settings, we characterize optimal median-unbiased estimators and equal-tailed confidence intervals conditional on $(T,\Pi_ {1:T},\eta)$ in the limit experiment. These confidence intervals are closely related to those in selective inference FST15.

These results have implications for a wide range of empirical contexts. Adaptive experiments are used in a variety of academic and commercial settings SBF17,Rafferty_Ying_Williams_2019,CGKQST22,bibaut2024demistifying. Moreover, recent theoretical results by HZZBGY20 show that batched experiments with a surprisingly small number of batches can achieve the same rate guarantees as fully adaptive experiments, in which the assignment probabilities may be different for each observation, further motivating our focus on batched experiments.

A potentially less obvious application of our results is to experiments with an initial pilot stage.\footnote{We thank 0{[anonymous] }bringing this connection to our attention.} For the purposes of our analysis the pilot stage can be treated as the first batch, and the main experiment as the second. If the choice of assignment probabilities and target parameters depend only on treatment-control contrasts at the pilot stage, one can apply our results on inference for location-invariant experimental designs and obtain more precise inference than is possible using the main experiment alone. Crucially, these results apply even when we do not have an exact formula for how the design of the main experiment depends on the pilot, for instance because design decisions were made on an ad-hoc basis after observing the results from the pilot.

(ref) formally introduces the problem we consider in the context of the normal model, and proves the optimality of last-batch-only inference absent further restrictions on $(T,\Pi_{1:T},\eta)$. (ref) introduces the class of location-invariant experiments and derives the sufficient statistic for $\mu$ in this class. (ref) shows that feasible analogs of the resulting inference procedures are uniformly asymptotically valid over a large class of data generating processes. (ref) considers optimal conditional inference when $ (T,\Pi_{1:T},\eta)$ depends on the data only through a collection of polyhedral events. Finally (ref) provides simulation evidence on the performance of our procedures. Proofs and additional results are provided in the appendix.

Problem setup

Let $n_t$ denote the total number of observations in batch $t$, $n = \sum_{t=1}^T n_t$ the total number of observations, and $c_t = n_t / n$ the fraction of observations assigned in batch $t.$ We write $X_{tk}$ for the sample average outcome among those units assigned to arm $k$ in batch $t$ and $X_t$ for the vector of these means, $X_t = [X_ {t1},\ldots, X_{tK}]'$. We assume that the assignment probabilities $\Pi_{t}$ depend on the data only through $X_{1:t-1}=(X_1,\ldots,X_{t-1}).$

Since $X_t$ is a vector of sample means, when batch sizes are large, the central limit theorem implies that $X_t$ is approximately Gaussian conditional on $\Pi_t,X_{1:t-1}$, with $X_{tk} \mid \Pi_t,X_{1:t-1} \sim \Norm (\mu_k,\frac{\sigma_k^2}{n_t\Pi_{tk}}).$ For $V_t$ the diagonal matrix with $k$\th diagonal element $\frac{\sigma_k^2}{c_t\Pi_{tk}}$ we thus have that, approximately, \[ X_{t} \mid \Pi_t,X_{1:t-1} \sim \Norm\pr{\mu, \frac{1}{n} V_t}, \addtocounter{equation}{1}\tag{\theequation} \label{eq:gaussian} \] Since $\Sigma$ is consistently estimable, in (ref) we treat it (and thus $V_t$) as known.

Exact Gaussianity (ref) is a strong assumption. Our results on general conditional inference (ref) extends to exponential family models ((ref)), though within exponential families we view Gaussian as likely the leading case. More importantly, we view the model (ref) as reflecting a focus on asymptotic approximation for batched bandits, rather than as a substantive parametric restriction. Indeed, the known-variance Gaussian model corresponds to the limit experiment for the batched bandit experiment under mild conditions hirano2023asymptotic. Since the statistical properties of any procedure in batched bandits can be matched asymptotically with a procedure under (ref), we derive optimal procedures under (ref). Thus, results under the Gaussian model characterizes {asymptotic} results for any batched bandit experiment, in the Le Cam--Hajek sense.

To demonstrate that these procedures are indeed asymptotically valid, (ref) verifies that the finite-sample analogue of our procedure converges to its counterpart under (ref), uniformly over a large class of (not necessarily Gaussian) data-generating processes. For analytical convenience, outside of (ref), we maintain that $\Pi_ {tk} > 0$ almost surely for all $t \in [T], k\in [K]$.

Inference problem

Suppose that we observe data from batches $1,\ldots,T$ of the Gaussian experiment (ref), where the stopping decision is based on information available at $T-1$ (i.e. $\one(T\le t)$ is measurable with respect to $X_{1:t-1}$). We are interested in inference on $\eta'\mu,$ where the target parameter is again measurable with respect to the information available at $T-1$, $\eta=\eta(X_ {1:T-1},T).$

Since we require that stopping decisions and target parameters are determined by $X_{1:T-1}$, inference based only on the last batch is valid: The $z$-statistic confidence interval $\eta'X_T\pm z_{1-\frac{\alpha}{2}} \sigma_{\eta}$ (where $z_{1-\frac{\alpha}{2}} = \Phi^{-1}(1-\frac{\alpha}{2})$ and $\sigma_{\eta}^2 = \frac{1}{n}\eta'V_T\eta$) has correct conditional coverage \[ \P\left(\eta'\mu\in \bk {\eta'X_T\pm z_{1-\frac{\alpha}{2}} \sigma_{\eta}} \mid T,\Pi_ {1:T},\eta\right)=1-\alpha. \] Moreover, $\eta'X_T$ is unbiased for $\eta'\mu$ even conditional on $T,$ $\Pi_{1:T}$, and $\eta$: $\E[\eta'X_T \mid T,\Pi_{1:T},\eta]=\eta'\mu.$

Can we construct a confidence set $C_{\eta}$ that improves on last-batch-only inference while maintaining the same flexibility? Specifically, if we would like confidence sets $C_\eta(\alpha)$ that maintain validity conditional on the experimental design (stopping time, assignment probability, and target parameter) \[ \P\pr{ \eta'\mu \in C_{\eta}(\alpha) \mid T,\Pi_{1:T},\eta } \ge 1-\alpha \text{ almost surely}, \quad \alpha \in (0,1). \addtocounter{equation}{1}\tag{\theequation} \label{eq:conditional_requirement} \] Can we do better than last-batch-only? The answer turns out to be no, if $\eta$ can be an arbitrary function $\eta(\cdot)$ of the history $X_{1:T-1}$.

(ref) shows that if $\eta(\cdot)$ is entirely unrestricted, then any confidence set which is conditionally valid in the sense of (ref) must also be valid conditional on $X_{1:T-1}.$ In fact, requiring conditional coverage given $\eta$ is already sufficient to obtain this conclusion. This effectively means we cannot use information from the first $T-1$ batches of data, so it is impossible to improve on the power of last-batch-only inference without losing some degree of robustness. In other words, for the first $T-1$ batches to provide useful information, we must be able to restrict the design.

To be sure, (ref) is stronger than some coverage requirements targeted in the literature, which do not condition on $ (T, \Pi_ {1:T}, \eta)$ zhang2020inference,hadad2021confidence. Correspondingly, imposing (ref) will tend to yield longer confidence sets. On the other hand, relative to the anytime-valid literature, we require weaker coverage (specifically, a weaker form of time-uniformity), and consequently tend to deliver tighter confidence intervals.\footnote{For example, the width of $(1-\alpha)$-asymptotic confidence sequences in waudby2024time scales as $\sqrt{\log (\sqrt{n}/\alpha) \frac{1}{n} }$ (Theorem 2.2), whereas our confidence sets scale as the usual $1/\sqrt{n}$.}

Whether imposing (ref) is appealing depends on whether one views conditional coverage as important. In settings where $\eta$ is adaptively chosen, fithian2014optimal advocate conditioning on $\eta$ on the grounds that that “The answer must be valid, given that the question was asked.” More broadly for confidence sets that are unconditionally, but not conditionally, valid, there necessarily exist values of $(T, \Pi_{1:T}, \eta)$ at which the confidence set under-covers some true parameter.\footnote{See (ref) for an example with zhang2020inference.} Thus, if we wish to avoid the situation where a reader could reasonably disbelieve our coverage claim after learning $(T, \Pi_{1:T}, \eta),$ we should focus on conditional coverage. On the other hand, if we are unconcerned with this possibility we are free to consider the (strictly larger) class of unconditionally valid procedures.

This tradeoff between a more robust form of Type I error control and power is an important but delicate question present in many contexts in statistics. Without taking a stand on on the “correct” form of error control in general, our motivation for focusing on (ref) stems from a desire to search for “safe free lunches” over the simple and intuitive procedure last-batch-only. Since last-batch-only satisfies (ref), optimal procedures satisfying (ref) by definition improves on last-batch-only.

To make progress in light of (ref), we consider two sets of restrictions on the design. First, we observe that many bandit algorithms are location-invariant. That is, they have the property that $\Pi_t(X_{1:t-1})$ is invariant to adding a constant $h \in \R$ to every batch-arm mean $X_{sk}$. If the adaptive choices of inferential target and stopping time are similarly location-invariant, as is often the case, then we can condition on less information, and construct procedures that dominate using solely the last batch. Such a procedure does not require knowledge of the precise allocation algorithm nor of $\eta(\cdot)$ and $T$, beyond location-invariance.

Second, if the experimental design depends solely on a lower-dimensional but known set of statistics, then we can also design optimal conditional inference procedures conditioning on these statistics. We show that such procedures are particularly tractable for a large class of discrete assignment algorithms that we call polyhedral algorithms. Since these procedures require less stringent conditioning, they are more powerful than conditional inference procedures that only use location-invariance.

Conditional inference for location-invariant algorithms

This section focuses on location-invariant designs. We show that there is a simple conditional procedure that assumes only location-invariance and improves upon last-batch-only inference. To state these results, we first formally define what we mean by location-invariance.

For concreteness, let us first introduce two leading location-invariant assignment algorithms. Let \[ W_t = \pr{\sum_{s=1}^t V_s^{-1}}^{-1} \sum_{s=1}^t V_s^{-1} X_s \] be the inverse-variance weighted batch-arm means, and let \[ \Omega_t = \frac{1}{n}\pr{\sum_{s=1}^t V_s^{-1}}^{-1} = \frac{\Sigma}{n} \pr{\sum_{s=1}^t c_s \Pi_s}^{-1} \addtocounter{equation}{1}\tag{\theequation} \label{eq:w_omega} \] be the posterior variance of $\mu \mid W_t$ under a flat prior for $\mu$.

Location-invariance implies that for each $t\in\{1,...,T_0\}$, the design $(\one(T\le t),\Pi_{1:t},\eta)$ is measurable with respect to batch-arm differences against $X_{1K}$: \[ \Delta X_{1:t-1} \equiv \br{X_{sk} - X_{1K} : s=1,\ldots, t-1; k = 1,\ldots, K-1}. \] Consider the following statistic, which represents some information from the first $T-1$ batches “left over” from conditioning on $(T,\Delta X_{1:T-1})$: \[ L = \sum_{t=1}^{T-1} \sum_{k=1}^K c_t \frac{ \Pi_{tk}}{\sigma_k^2} X_{tk}. \] Since $c_t n \Pi_{tk}$ is the number of units assigned to arm $k$ in batch $t$, the coefficient $c_t \frac{ \Pi_{tk}}{\sigma_k^2}$ is then the proportional to the inverse variance of $X_{tk}$. Thus we may view $L$ as the precision-weighted sum of all batch-arm means in the first $T-1$ batches. This particular weighted sum turns out to be orthogonal to random variables measurable with respect to $\Delta X_{1:t-1}$.\footnote {It is illustrative to note that for $Z \sim \Norm(0, \diag(\sigma_1^2, \sigma_2^2)),$ the precision-weighted sum $Z_1/\sigma_1^2 + Z_2/\sigma_2^2$ is independent of the difference $Z_1 - Z_2$.}

It turns out that $L$ is the only information left over from conditioning, in the sense that $(L, X_T)$ is sufficient for $\mu$ with respect to the conditional distribution of the data.

Therefore, we can base inference for $\mu$ on (ref). Optimal inference in (ref) is also optimal conditional inference given the finer information set $\Delta X_{1:T-1}$. The minimal sufficient statistic for $\mu$ under (ref) is the weighted least-squares coefficient

Optimal conditional inference for $\eta'\mu$ is thus simply based on the Gaussian statistic $\eta' S^\star$. For instance, the optimal uniformly most accurate unbiased conditional confidence interval for $\tau$ is the z-statistic interval centered at $\eta' S^\star$. (ref) shows that the finite sample analogue of $\eta'S^\star$ has asymptotic behavior analogous to (ref) and produces confidence intervals that cover the random parameter $\tau = \eta'\mu$ conditional on $(T,\Pi_{1:T},\eta)$.

Gain relative to last-batch inference

(ref) shows that under location-invariance there is one usable piece of information beyond the last batch, namely the statistic $L$. It is therefore interesting to understand to what extent this additional information helps us with inference on $\mu$.

Let $r^{(c)} = V_T \lambda$. Note that $r^{(c)}$ collects the ratio of cumulative sample size and last period sample size for each arm: $r^{(c)}_k = \frac{\sum_{t=1}^{T-1} n_t\Pi_ {tk}}{n_T \Pi_{Tk}}.$ Similarly, let $r^{(t)} = r^{(c)} + 1$ collect the ratio of total sample size to last period sample size for each arm. Let $q = \sum_{t=1}^{T-1} n_t \Pi_{t}1_K$ collect the cumulative sample size. Then we have that \[ \var(S_k^\star \mid \Delta X_{1:T-1}, T) = \underbrace{\frac{V_T}{n}}_{\var(X_T \mid \Pi_T)} \pr{I - \frac{q \Sigma^{-1} (r^{(c)})'}{q' \Sigma^{-1} r^{(t)}}}. \] Thus, the reduction in variance relative to using solely the last batch depends on the alignment of $\eta$ to the matrix $\frac{q \Sigma^{-1} (r^{(c)})'}{q' \Sigma^{-1} r^{(t)}}$, which collects information about variance-weighted relative sample sizes. The relative improvement is greatest when $\eta$ is proportional to $\lambda$, since then $L$ provides the greatest amount of information.

Conditioning on $\Delta X_{1:T-1}$ in Thompson sampling

We have so far studied inference conditional on all of the differences $\Delta X_ {1:T-1}$, since $(L, X_T)$ is sufficient with respect to $X_{1:T} \mid (T, \Delta X_ {1:T-1})$. While this allows for any location-invariant experimental design, one might wonder if this conditioning is excessive. If we had more restrictions on how $(T,\Pi_ {1:T},\eta)$ were generated and our only goal were to ensure conditional coverage (ref), perhaps it would suffice to condition on a coarser set of statistics, which could lead to higher power. (ref) explores this possibility.

Here, we show instead that conditioning on $\Delta X_{1:T-1}$ is sometimes necessary for conditional coverage (ref), even when the rules generating $(T,\Pi_{1:T},\eta)$ are perfectly known. Specifically, we show in the case of Thompson sampling ((ref)), for fixed $T$ and $\eta$, efficient conditional inference given $\Delta X_{1:T-1}$ is also efficient given $\Pi_{1:T}$. This is because $\Pi_{1:T}$ in Thompson sampling contains rich information about $\Delta X_{1:T-1}$.

(ref) shows that $(L, X_T)$ is sufficient for $\mu$ with respect to the distribution $X_{1:T} \mid (\Pi_{2:T}, T)$. Thus, optimal inference based on $(L, X_T)$ is optimal for $\eta'\mu$. The proof relies on inversion results from the econometrics of discrete choice hotz1993conditional,norets2013surjectivity in order to show that $\Pi_{1:T}$ reveals sufficiently rich information on $\Delta X_{1:t-1}$.

Uniform asymptotics for location-invariant algorithms

Our focus on the Gaussian model is motivated by the fact that it serves as an approximation to asymptotic results for any batched bandit setting, without distributional assumptions. To more formally connect the two, this section shows that the finite-sample analogue of the inference procedure following (ref) is uniformly asymptotically valid over a large class of data distributions and experimental designs.

To state these results, we first introduce the non-Gaussian version of our setting. Fix a sequence $(n, n_1,\ldots, n_{T_0})$ indexed by $n$ such that $n_t / n \to c_t \in (0,1)$ and $\sum_t n_t = n$. Let $\mathcal I_t \subset [n]$ collect the indicies of the $n_t$ individuals in batch $t$. Prior to each batch, assignment probabilities $\Pi_ {tn} = \diag(\Pi_{t1n},\ldots, \Pi_{tKn})$ are determined by the assignment algorithm, as a function of past data. In batch $t$, the $n_t$ participants are assigned to one of $K$ arms. The indicator for individual $i$'s assignment is $D_i = [D_{i1},\ldots, D_ {iK}]'$, which follows a categorical distribution with probabilities $\Pi_{tn}$ and are independent across $i$. Let $N_{tn} = [N_{t1n},\ldots, N_{tKn}]' = \sum_ {i \in \mathcal I_t} D_i$. Let $\hat\Pi_{tkn} = N_{tkn} / n_t $ be the realized frequency of samples to arm $k$ in batch $t$. Let $\hat\Pi_{tn} = \diag(\hat\Pi_{t1n},\ldots, \hat\Pi_{tKn}).$

Let $X_i^{\text{obs}} = \sum_k D_{ik} X_i(k)$ be the outcome observed for $i$---equal to the potential outcome at the assigned treatment---and let \[ X_{tkn} = \frac{1}{N_{tkn} \vee 1} \sum_{i \in \mathcal I_t} D_{ik} X_i^{\text{obs}} \] be the batch-arm empirical mean. The definition for $X_ {tkn}$ builds in the convention that an empty mean is zero. Let \[ \hat \sigma_{tkn}^2 = \frac{\sum_{s=1}^t \sum_ {i\in \mathcal I_s} D_{ik} (X_i^\text{obs} -W_{t, k, n})^2}{\sum_{s=1}^t N_{skn}} \addtocounter{equation}{1}\tag{\theequation} \label{eq:def_sigma2} \] be an estimate of the arm variance using data up until batch $t$. Let $\hat \sigma_{kn}^2 = \hat \sigma_{Tkn}^2$, $\hat\Sigma_{tn} = \diag(\hat\sigma_{t1n}^2, \ldots, \hat\sigma_ {tKn}^2)$ and $\hat\Sigma_n = \diag(\hat \sigma_{1n}^2,\ldots, \hat\sigma_{Kn}^2)$.

Let the realized stopping time be $T_n$ and suppose the experimenter wishes to conduct inference for a possibly data-dependent parameter $\tau_n = \eta_n'\mu$. We let \[ \lambda_n = \sqrt{n} \sum_{t=1}^{T_n-1} \frac{n_t \hat \Pi_{tkn}}{n \hat\sigma^2_{kn}} \quad L_n = \sqrt{n} \sum_{t=1}^{T_n-1} \sum_{k=1}^K \frac{n_t \hat \Pi_{tkn}}{n \hat\sigma^2_ {kn}} X_{tkn} \] be scaled analogues of $\lambda$ and $L$. Finally, let \[ S_n^\star = \pr{\frac{\lambda_n \lambda'_n }{\sqrt{n} \lambda'_n1} + \frac{n_{T_n}}{n} \hat\Sigma^{-1}_n \hat \Pi_{T_n,n} }^+ \pr{\frac{\lambda_n}{\lambda_n'1} \frac{L_n}{\sqrt{n}} + \frac{n_{T_n}}{n} \hat\Sigma^ {-1}_n \hat\Pi_ {T_nn} X_{T_nn}}\addtocounter{equation}{1}\tag{\theequation} \label{eq:real_wls_coef} \] be an analogue of (ref).\footnote{Here, to conform with our asymptotic results and to accommodate $\Pi_{tk} \approx 0$, we study the following parametrization of (ref) \[ \colvecb{2}{L}{\sqrt{n_t} \Pi_T X_T} \mid \Pi_{2:T} \sim \Norm\pr{ \colvecb{2}{\lambda'\mu}{\sqrt{n_t}\Pi_t \mu},

} \] which we again treat as a weighted least-squares problem for $\mu$. (ref) follows from applying the Sherman--Morrison identity in the case that $\Pi_T > 0$. } The estimator for $\tau_n$ is $\hat\tau_n = \eta_n' S_n^\star$, with estimated asymptotic standard error \[\hat\sigma^2_{\tau,n} = \eta_n' \pr{\frac{\lambda_n \lambda'_n / \sqrt{n}}{\lambda'_n1} + \frac{n_{T_n}}{n} \hat\Sigma^{-1}_n \hat \Pi_{T_n, n} }^+ \eta_n. \]

Our main asymptotic result is that, uniformly over a class $\mathcal P$ in the sense of andrews2011generic, $ \sqrt{n} \hat\sigma^{-1}_{\tau,n} (\eta_n'S_n^\star - \tau_n) \dto Z $ where $Z$ is conditionally standard Gaussian given (the limiting analogues of) $(T_n, \Pi_{1:T_n}, \eta_n)$. Thus, $(1-\alpha)$ two-sided confidence intervals $ \mathrm{CS}_{n}(\alpha) \equiv \eta_n'S_n^\star \pm \Phi^{-1}(1-\alpha/2) \cdot \hat\sigma^2_{\tau,n} $ have exact asymptotic conditional size for the parameters $\tau_n$:\footnote{For expositional clarity, the main text (ref) presents the conditional coverage as conditioning on $T$ and $\eta$. (ref) in the appendix additionally shows conditional coverage given $\Pi_{1:T}$.} \[ \limsup_{n\to\infty}\sup_{P \in \mathcal P} \, \abs[\big]{P\pr{ \tau_n \in \mathrm{CS}_{n}(\alpha) \mid T_n = T, \eta_n = \eta } - \alpha} P(T_n = T, \eta_n = \eta) = 0. \addtocounter{equation}{1}\tag{\theequation} \label{eq:uniform_inference} \]

Such a statement is predicated on assumptions about the class $\mathcal P$, the assignment algorithm for generating $\Pi_{1:T_0,n}$, $T_n$, and $\eta_n(\cdot)$. We assume that members of $\mathcal P$ have second moments bounded away from $0$ and $\infty$ and uniformly bounded fourth moments.

This section restricts to $T_n, \eta_n, \Pi_{t+1, n}$ that depend on $X_{1:T_0}$ only through the cumulative mean vector\footnote{Our proof in (ref) considers weaker conditions.} \[ W_{tkn} = \sum_{s=1}^{t} \frac{n_s \hat \Pi_{skn}}{\sum_{r=1}^{t} n_r \hat\Pi_{rkn}} X_{skn}. \] Note that this covers the Thompson sampling and $\varepsilon$-greedy examples discussed above. Let

be the analogues of $W_t, \Omega_t$ in (ref). We assume that $ \one(T_n > t+1) = \Xi_{t+1}\pr{ \sqrt{n} W_{tn}, \Omega_{tn} } $ for some known function $\Xi_{t}.$ Likewise, we assume that the assignment probability is generated through some function $\kappa_t$: \[ \Pi_{t+1,n} = \kappa_{t+1,n}\pr{X_{1:t,n}, \hat\Pi_{1:t,n}, \hat\Sigma_{tn}, n_{1:t}} = \kappa_ {t+1} \pr{ \sqrt{n} W_{tn}, \Omega_{tn} }. \addtocounter{equation}{1}\tag{\theequation} \label{eq:simplied_mechanism} \] We assume that both $\Xi_{tn}$ and $\kappa_{t+1, n}$ are location-invariant in $W$. Moreover, we require these functions to be suitably continuous, so that they converge weakly when their arguments converge weakly. All of the following assumptions are relative to some $\epsilon > 0$. (ref) describes some concrete algorithms that satisfy the following assumptions.

We remark on the continuity requirement (ref)(2). Quantities in the adaptive experiment depend on $\sqrt{n} W_{tn}$ and $\Omega_{tn}$. We expect that $\sqrt {n}W_{tn} - \sqrt{n}\mu$ converges in distribution to some continuous distribution, and $\Omega_{tn}$ converges in probability to some matrix $\Omega$. We would like to impose enough regularity so that $g(\sqrt{n} W_{tn}, \Omega_{tn})$ converges to a suitable limit. By location invariance, letting $\bar \mu = \max_k \mu_k$, we can replace $\sqrt{n}W_{tn}$ with $\sqrt{n}W_{tn} - \sqrt{n} \bar\mu = ( \sqrt{n} \mu - \sqrt{n}\bar\mu) + \sqrt{n}(W_{tn} - \mu)$. Given a suitable sequence of data-generating processes $P_n$ with $\mu = \mu(P_n)$, (sub)sequences of $\sqrt{n}W_{tn} - \sqrt{n} \bar\mu$ have entries that either tend to a continuously distributed random variable (for coordinates where $\sqrt{n} (\mu_k-\bar\mu) = O(1)$) or diverge to $-\infty$. Thus, the continuity of $g$ needs to accommodate entries diverging to $-\infty$ as well. On the other hand, the requirement that the limit exists for almost every $w_j$ allows $g$ to be discontinuous on measure-zero sets, and accommodates examples such as $ \varepsilon$-greedy.

The expression (ref) means that the assignment probability algorithm $\kappa_ {t+1}$ takes the form of a contingency plan. If the experiment continues, then the next-batch probabilities are prescribed by $\kappa_{t+1, (0)}$. Otherwise, they are prescribed by $\kappa_{t+1, (1)}$. By convention, we say that $\kappa_{t+1} = \Pi_1$ when the experiment has already stopped.

For the pseudoinverse $\pr{\frac{\lambda_n \lambda'_n }{\sqrt{n} \lambda'_n1} + \frac{n_T}{n} \hat\Sigma^{-1}_n \hat \Pi_{Tn} }^+$ to converge weakly when its arguments do, we additionally require that the rank of $\frac{\lambda_n \lambda'_n }{\sqrt{n} \lambda'_n1} + \frac{n_T}{n} \hat\Sigma^{-1}_n \hat \Pi_{Tn}$ is well-behaved. A sufficient condition is to assume that the range of the assignment probabilities of the last batch excludes $ (0, \epsilon)$. This can be implemented by pruning away small probabilities and set them to zero, and redistributing the excess mass. Doing so ensures that the arm-level sample sizes in batch $T$ either diverges to infinity or is eventually zero.

Lastly, we consider a simple form of $\eta_n$. We assume that $\eta_n$ takes finitely many values, but they can be chosen with respect to some rich information.

(ref) are stronger than necessary. We state weaker conditions as (ref), and verify that the weaker conditions are implications of the stronger ones. Under these assumptions, we formally justify (ref). The following is a corollary of a more general result (ref) in the appendix.

Notably, the asymptotics does not require truncation of $\Pi_{2:T-1,n}$ and instead solely requires a pruning step for $\Pi_{Tn}$, unlike existing work zhang2020inference,niu2025assumption. This is because the statistic (ref) can be written in terms of the scaled means $Y_t \propto \hat\Pi_{tn} (X_ {tn} - \mu)$ instead of $X_ {tkn}.$ The statistics $Y_{tkn}$ admit a central limit theorem uniformly over $\Pi_{tkn} \in [0,1]$.

General conditional inference

If we have additional knowledge of the allocation algorithm as well as the inferential target and stopping time, then we can design optimal conditional inference procedures that condition on less information and are hence more powerful.

Let us first introduce a general recipe for constructing optimal conditional procedures by analyzing the likelihood of the observed data. Suppose we wish to condition on growing information sets $\mathcal F_{T-1} (X_ {1:T-1})$ such that the experimental design $(\one(T\le t), \Pi_{1:t}, \eta(X_1,\ldots, X_t; t))$ is measurable with respect to $\mathcal F_{t-1}$. The law of the observed data, for a given stopping time $T'$, is an exponential family:

where $h(\cdot)$ does not depend on $\mu$. Thus, a sufficient statistic for $\mu$ with respect to the law of $\pr{X_{1:T} \mid T, \mathcal F_{T-1}}$ is \[ S = n \sum_{t=1}^{T} V_t^{-1} X_{t}. \] For any $\tau = \eta'\mu$, where without loss of generality $\norm{\eta} = 1$, given an orthogonal matrix $Q$ whose first row is $\eta$ we can further partition \[S'\mu = S'Q'Q\mu = (\eta'S) (\eta'\mu) + (\eta_\perp S)'(\eta_\perp\mu) \equiv U\tau + U_\perp'\tau_\perp.\]

By the results in section 5.5 of pfanzagl2011parametric, optimal inferences for $\tau$, conditional on $\mathcal F_{T-1}$,\footnote{adusumilli2023optimal studies Neyman--Pearson-style testing with the likelihood (ref).} are based on the distribution of $U \mid U_\perp, \mathcal F_{T-1}$, which depends solely on $\tau$ and is stochastically increasing in $\tau$. For instance, the optimal $\alpha$-quantile unbiased estimator for $\tau$, based on observations $(u, u_\perp, \mathcal F_{T-1}(X_{1:T-1})),$ can be computed by $\hat\tau_\alpha$ such that \[ \P_{\hat\tau_\alpha}\pr{U \le u \mid U_\perp=u_\perp, \mathcal F_{T-1}(X_{1:T-1})} = \alpha. \] The optimal $(1-\alpha)$ equal-tailed confidence interval for $\tau$ is $[\hat\tau_{\alpha/2}, \hat\tau_{1-\alpha/2}]$. Indeed, this general recipe based on the likelihood can also be used to show that the optimal conditional inference procedure in Thompson sampling corresponds to the procedure based on (ref).

If choices of inferential target and stopping time can be expressed in terms of linear inequalities in $X_ {1:T-1}$, then the above recipe is particularly tractable. Like our results in (ref), the optimal conditional procedures dominate using only the last batch.

Conditional inference for polyhedral algorithms

We consider a class of algorithms such that the support of $\mathcal F_ {T-1} \equiv (\Pi_{2:T}, T, \eta)$ is finite. For every $(\pi, t_0, h)$ in its support, there exist a conformable matrix $A(\mathcal F_{T-1})$ and vector $b(\mathcal F_{T-1})$ such that for all $\mu$,

As an example, suppose $T, \eta$ are fixed, but at each batch $t$, the assignment algorithm $\epsilon$-greedy ((ref)) favors the arm $k$ with the highest cumulative arm mean $W_{(t-1),k}$. Each realization of $\pi_{2:T}$ then corresponds to a sequence of $\epsilon$-greedy winners $(k_1,\ldots, k_{T-1})$. Thus, up to a measure-zero event of ties, the sequence of winners $(k_1,\ldots, k_{T-1})$ is equivalent to the inequalities \[ \br{W_{t,k_t} \ge W_{t, \ell} : t = 1,\ldots, T-1; \ell = 1,\ldots, K}. \] Since $W_{t, \ell}$ is linear in $X_{1},\ldots, X_t$, we may represent these inequalities as the polyhedron $A(\mathcal F_{T-1}) \bX_{1:T} \le b(\mathcal F_{T-1})$.

Following our conditional inference strategy, optimal inference for $\tau = \eta'\mu$ depends on the distribution \[ (U \mid U_\perp, \mathcal F_{T-1}) \sim (U \mid U_\perp, A(\mathcal F_{T-1}) \bX_{1:T} \le b(\mathcal F_{T-1})) \] where $U = \eta'S$, $U_\perp = \eta_\perp S$, and $S_k = \sum_{t=1}^T \frac{n_t \Pi_{tk}} {\sigma_k^2} X_{tk}$. The following theorem makes explicit this distribution, and, in particular, its dependence on $\mu$ only through $\tau$.

At any realization of the data $X_{1:T}$, the constraints and parameters \[(m(\mathcal F_ {T-1}) , M(\mathcal F_{T-1}), c, G_\perp \bV G_\perp')\] are functions of known quantities. The law $(Z_1 \mid M(\mathcal F_ {T-1}) Z \le m(\mathcal F_{T-1}) )$ depends only on the parameter of interest $\tau$.

For testing the point null hypothesis $H_0: \tau = \tau_0$, we can draw from the corresponding distribution $(Z_1 \mid M(\mathcal F_ {T-1}) Z \le m (\mathcal F_{T-1}) )$ induced by the null value $\tau_0$. The observed statistic is $z_1 = U/c$. Valid tests are then constructed by comparing $z_1$ to its distribution under the null. A level-$(1-\alpha)$ equal-tailed test, for instance, rejects $H_0$ when $z_1$ falls in the lower $\alpha/2$ or the upper $\alpha/2$ quantiles of the distribution $(Z_1 \mid M(\mathcal F_ {T-1}) Z \le m (\mathcal F_{T-1}) )$ under $\tau_0$.

In terms of computation, we can efficiently draw from $(Z \mid M(\mathcal F_{T-1}) Z \le m(\mathcal F_{T-1}) )$ via Gibbs sampling taylor2016restrictedmvn,\footnote{We thank 0{[anonymous] }for this suggestion.} since the conditional distribution of each coordinate of $Z$ is a truncated Gaussian. Confidence intervals can be constructed by inverting tests of $H_0 : \tau = \tau_0$ for a range of $\tau_0$. Computation of confidence intervals does not require drawing the distribution of $Z$ for every candidate value of $\tau_0$. Note that, since the likelihood ratio between two candidate values $(\tau_1, \tau_0)$ is known, \[ \frac{p_{\tau_1}(z_1 \mid M(\mathcal F_{T-1}) Z \le m(\mathcal F_{T-1}) )}{p_{\tau_0}(z_1 \mid M(\mathcal F_{T-1}) Z \le m(\mathcal F_{T-1}) )} = \exp\pr{ c(\tau_1 - \tau_0) z_1 }, \] samples from $p_{\tau_0}$ can be reweighted to obtain estimators for quantities under $p_ {\tau_1}$. As a result, inference based on (ref) is computationally efficient, at least for moderately-sized $(T,K)$.

Simulation evidence

We consider two simulated experiments. Both experiments have $T = 4, K = 3, \mu = [0,0,0]'$, $n_1 = n_2 = n_3 = n_4 = 200$. To demonstrate asymptotic validity of our inference procedures, we take the individual outcomes to be i.i.d. Rademacher random variables and we plug in estimated versions of $\Sigma$ in the following empirical exercises. We consider a Thompson sampling experiment and an $\varepsilon$-greedy experiment.\footnote{The Thompson sampling algorithm prunes the last-batch assignment probabilities at $0.01$ (See (ref)), which is needed for our asymptotic results in (ref). The $\varepsilon$-greedy algorithm chooses $\varepsilon = 0.1$. }

For Thompson sampling, (ref) displays coverage and length of different confidence intervals. In (ref),

Among these procedures, ZJM and Anytime-valid are not designed to control Type I error for adaptive targets. The confidence intervals are truncated to the parameter space $[-1,1]$.

We compare the procedures over two setups, fixed target and adaptive target. In terms of rejection rates, the conditional procedures control size for both setups, and ZJM does not control size for the adaptive setup ((ref) plots the distribution of $t$-statistics in the adaptive setup). Anytime-valid inference waudby2024estimating appears to underreject for both regimes.

In terms of length, the improvement in median length from using the leftover information is about 10% for this particular setup of the experiment, relative to only using the last batch, whereas the ZJM interval is 40--50% shorter than only using the last batch. This confirms that the improvement that the additional statistic $L$ provides relative to last-batch-only is mild but non-trivial (a 10% improvement in length is comparable to a 20% increase in sample size). On average, we do sacrifice confidence interval length to maintain conditional validity, relative to the unconditionally valid procedure ZJM. On the other hand, since our results are asymptotic and leverage the batch structure, they generally yield shorter intervals than finite-sample inference results from the anytime-valid inference literature.

Similarly, we additionally compare the behavior of the Polyhedral inference procedure ((ref)) for an $\varepsilon$-greedy experiment in (ref). For inference on a fixed target, all procedures achieve their nominal size. The Polyhedral procedure generates 40% shorter confidence intervals (measured in terms of median length) than Last-only, which is more than double the improvement of Leftover. For inference on the adaptive target, we again see that the conditional procedures maintain nominal size (at the cost of greater length), whereas ZJM does not.

Lastly, we plot conditional behavior of these procedures in (ref), where we condition on the number of times the inference target, arm 3, is the $\varepsilon$-greedy winner. We find that the conditional procedures indeed control conditional size, whereas ZJM over-rejects when arm 3 (for whose mean we perform inference) wins most and least often, and compensates for the over-rejection by under-rejecting on other sequences of $\varepsilon$-greedy winners.

Conclusion

This paper investigates inference conditional on the experimental design in batched adaptive experiments, and explores the potential of improving upon inference procedures that only use the last batch. For location-invariant experimental designs, we find there is a scalar statistic, beyond the last-batch result, which is left over after conditioning. Using this additional statistic provides a free lunch improvement for statistical inference, relative to using the last batch alone. For polyhedral experimental designs, we characterize optimal conditional inference procedures and demonstrate their computational tractability.