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.
63,022 characters · 16 sections · 21 citation commands
Benefits and Costs of Adaptive Sampling
{\bf Keywords: }Adaptive Experimental Design, Multi-armed Bandits, Statistical Efficiency, Inference-regret Tradeoff, Adaptive Neyman Allocation
Adaptive experimental design uses information collected during an experiment to guide future assignment decisions, fueling online experimentation to become central in decision-making across a wide range of operational settings, including recommendation systems, digital advertising, and clinical decision-making, where organizations repeatedly run experiments to improve products and treatments (bojinov2025experimentation, netflix2022experimentation). At the same time, these experiments are rarely governed by a single objective. A practitioner may care both about experiment efficiency and about performance during the experiment itself, since assigning customers or patients to inferior alternatives can lower revenue, engagement, or increase avoidable medical cost while learning (wilson2025rar, netflix2025returnaware).
Despite this relevance, adaptive experimentation is still often viewed as impractical in industry for inference. Consider a data scientist evaluating which recommendation system performs best for a streaming platform. If the primary objective is accurate estimation of treatment effects, then the natural statistical goal is to minimize the mean squared error (MSE) of the estimators. In principle, adaptive assignment can use online observations to allocate more samples where they are most informative. In practice, however, data scientists often worry that changing assignment probabilities over time will complicate inference or introduce bias if analyzed naively. Furthermore, it is well known that adapting comes at a cost of increased variance. As a result, many experiments continue to rely on uniform sampling, even though such designs may use samples inefficiently and lengthen experiments unnecessarily.
To address these problems, we study the value of adaptive experimentation relative to non-adaptive designs under two objectives. We begin with the pure inference setting, where the goal is to improve statistical efficiency as measured by MSE. In this setting, we show that even simple data-driven adaptive sampling can outperform uniform sampling once the pilot learning phase is sufficiently informative. We then turn to a joint inference--regret setting, which captures the concern that experiments are often run in environments where continued assignment to suboptimal treatments carries real online cost. In this second setting, we propose two adaptive sampling rules, SARP and NARP, that balance statistical accuracy with online performance, commonly formalized as regret in the multi-armed bandit literature. SARP provides a simple rate-based exploration template that can be combined with standard regret-minimizing algorithms, while NARP further calibrates the exploration level using plug-in estimates of the instance's variance and gap structure. These procedures are not intended to replace optimized problem-specific bandit algorithms (ErraqabiLVBL17, simchi-levi_multi-armed_2025); rather, they provide a practical and interpretable policy family that exposes the inference--regret tradeoff directly while still attaining the asymptotic rate benchmark.
Taken together, our results show that adaptive designs can be justified on both statistical and operational grounds: they can improve inference relative to uniform designs, and can be extended to settings where learning must be balanced against performance during the experiment. We begin in Section (ref) by formulating the problem and introducing the necessary notation. We then present our theoretical results for the inference objective and the joint inference--regret objective separately in Sections (ref) and (ref). Next, in Section (ref), we provide numerical simulations illustrating the effectiveness of our findings and methods. Finally, we conclude in Section (ref).
\paragraph{Adaptive Experiment Design}
Our work sits within the growing literature that studies adaptive experiment design through the multi-arm bandit (MAB) lens. This perspective appears in both clinical and digital operation settings (berry2006bayesian, scott2010modern), and has been developed in settings where assignments are updated sequentially using accrued data rather than fixed in advance (Chernoff1992, https://doi.org/10.3982/ECTA17527). A separate line of work studies how to perform valid statistical inference under adaptive assignment despite the dependence between samples and assignment probabilities (doi:10.1073/pnas.2014602118, zhang2021statistical, dimakopoulou2021online, doi:10.1287/mnsc.2023.4921). Our paper adopts this general viewpoint of experimentation as a sequential decision problem, but focuses on simple adaptive rules whose statistical and operational performance can be compared directly to non-adaptive benchmarks. Furthermore, our paper does not focus solely on regret minimization or on validity of inference under adaptive assignment. Instead, we specifically study whether adaptive sampling for inference, rather than regret minimization, can be more statistically efficient than non-adaptive uniform policies.
\paragraph{Statistical Efficiency}
A second closely related literature studies experimental design from the perspective of statistical efficiency. The interest in improving efficiency through design goes back at least to https://doi.org/10.1111/j.2397-2335.1934.tb04184.x, which proposed the statistically optimal Neyman allocation, and has been extensively developed in later work (semipar_effic, https://doi.org/10.1111/1468-0262.00442, 10.1214/12-AOS1008, 10.1093/jrsssb/qkad072). Several recent papers focus specifically on adaptive designs that seek to approach Neyman-optimal allocation as the sample size increases, including zhao2023adaptiveneymanallocation, dai2023clip, li2024optimal, kato2025efficientadaptiveexperimentaldesign. Our pure-inference investigation differs in emphasis from this line. We do not focus on the asymptotic MSE optimality of a particular adaptive rule. Instead, building on the two-stage adaptive procedure in zhao2023adaptiveneymanallocation, we ask when an adaptive design, using only a modest pilot phase, already outperforms the non-adaptive uniform benchmark.
\paragraph{Learning-Focused Bandits}
Our pure-inference objective is also closely related to the learning-focused bandit literature, including active learning, mean estimation, and pure exploration (audibert:hal-00654404, ANTOS20102712, 10.1007/978-3-642-24412-4_17, meanest). These works study how adaptive sampling can improve learning quality when the objective is estimation or identification rather than cumulative reward maximization. This is therefore closer in spirit to our inference setting than classical regret-minimizing MAB. At the same time, our contribution differs in two ways. First, we are interested in explicit overperformance relative to a natural non-adaptive benchmark, namely uniform sampling, rather than primarily in regret guarantee or sample complexity. Second, we later extend the analysis beyond inference alone to account for the opportunity cost of suboptimal assignments during the experiment.
\paragraph{Inference and Regret-Focused Bandits}
Our second contribution, which jointly considers experiment efficiency and regret minimization, is closely aligned with ErraqabiLVBL17. Their work studies a related reward--error tradeoff through a proxy-MSE objective, and their algorithm can be viewed as repeatedly solving a one-step version of the oracle allocation problem in Section (ref): at each period, the next arm is selected by optimizing the current marginal reward--error tradeoff. Our goal is not to establish dominance over such procedures; rather, we aim to derive simpler and more interpretable adaptive rules that attain the oracle asymptotic rate benchmark while remaining easy to analyze and deploy. The recent work simchi-levi_multi-armed_2025 also studies this multi-objective problem, proposes corresponding algorithms, and characterizes a Pareto tradeoff between regret minimization and inference efficiency. Relative to these works, our emphasis is on adaptive sampling rules that are intuitive to practitioners and expose the exploration--exploitation structure explicitly. Additionally, our objectives are different from those proposed in the aforementioned papers, as detailed in Section (ref).
We study a stochastic $K$-armed bandit with horizon $N$. Each arm $i \in [K] := \{1,\dots,K\}$ is associated with an unknown reward distribution $\nu_i$, with arm-specific mean $\mu_i$ and variance $\sigma_i^2 > 0$. At each round $t \ge 1$, the learner selects an arm $I_t \in [K]$ and observes a reward $X_t \sim \nu_{I_t}$. The sampling rule may depend on the past history $\mathcal{H}_{t-1} := (I_1,X_1,\dots,I_{t-1},X_{t-1})$, and is therefore allowed to be adaptive. For each arm $i$, define $T_{i,t} := \sum_{s=1}^t \operatorname{\mathbbm{1}}\{I_s = i\}$, and write $T_i := T_{i,N}$ for the total number of samples collected from arm $i$ by the end of the horizon.
The primary statistical target is learning or doing inference on the vector of arm means $(\mu_1,\dots,\mu_K)$, and the sampling policy $\pi$ determines how the total budget $N$ is distributed across arms through the random sample counts $(T_1,\dots,T_K)$ satisfying $\sum_{i=1}^K T_i = N$. A sampling policy $\pi$ should be understood as a decision rule: at each round $t$, it maps the available history $\mathcal{H}_{t-1}$ to a distribution over arms. We write
for the conditional probability induced by policy $\pi$ of selecting arm $i$ at round $t$. Thus, $\pi$ denotes the policy as a whole, whereas $p_{t,i}^\pi$ denotes the particular assignment probability generated by that policy at a given time and history. We will also write $p_{t,i}$ generically and suppress the dependence on the underlying policy when only the conditional assignment probability matters.
This distinction between $\pi$ and $p^{\pi}$ may not seem necessary for simple non-adaptive designs. For example, under uniform sampling $\pi^{\rm uni}$, the policy and its induced probabilities are effectively indistinguishable, since $p_{t,i}^{\pi^{\mathrm{uni}}} = 1/K$ for all $t \in [N]$ and $i \in [K]$. In contrast, under a sequential policy, the rule $\pi$ may depend on the observed data, and the realized probabilities $p_{t,i}^\pi$ therefore change over time with the history. Keeping these two objects separate is useful in later analysis, especially when the sampling rule is history-dependent and the resulting estimators or risk bounds depend explicitly on the conditional assignment probabilities.
The formulation above specifies the common stochastic bandit model used throughout the paper. The additional ingredients needed to evaluate the problem at hand---including the estimator, sampling policy, and objective functional---depend on the design problem under consideration and will be introduced separately. We first study inference as the objective in Section (ref), where the focus is estimation of the arm means under adaptive data collection. We then turn to the joint inference--regret setting in Section (ref), which augments the inference objective with a regret-based criterion and introduces the notation needed for optimality gaps and online loss.
In this section, we study the design of an efficient experiment for estimating the arm means. For any policy $\pi$, given armwise estimators $\hat\mu_1, \dots, \hat\mu_K$, we define the armwise mean squared error by
and our goal is to solve
That is, we seek to understand how the choice of sampling policy, for a given estimator, shapes the total mean squared error (MSE) across arms. Our main interest is whether an adaptive sampling rule can improve upon uniform sampling in finite sample, which serves as the natural non-adaptive baseline. As a reminder, this problem differs from the standard regret-minimizing bandit setting. It is well known that adaptive policies $\pi$ can achieve substantially better regret than non-adaptive exploration rules. However, far less attention has been paid to whether a similar advantage persists when the objective is statistical inference. The works that do study this question typically focus on optimal bandit design rather than directly on inference efficiency relative to non-adaptive baselines ANTOS20102712, 10.1007/978-3-642-24412-4_17. We therefore begin with an oracle benchmark that isolates the underlying allocation problem in a static setting and clarifies the efficiency target that a data-driven adaptive design should aim to approximate.
Consider an oracle benchmark in which the arm variances $\sigma_1^2,\dots,\sigma_K^2$ are known a priori by the experimenter and we estimate $\mu_i$ by the sample mean $\hat\mu_j^{\mathrm{sam}}$. In this case, as noted in ANTOS20102712, there is no value in adopting adaptive sampling as adaptive sampling usually aims to learn $\hat\sigma$ over time. Therefore, when observations are independent and arm $i$ receives $T_i$ samples under an oracle static case, $\mathbb{E}\bigl[(\hat\mu_i^{\mathrm{sam}}-\mu_i)^2\bigr] = \frac{\sigma_i^2}{T_i}.$ Hence the total sum of MSE reduces to the static allocation problem
The optimizer to (ref) is the classical Neyman allocation, which we denote as $\pi^{\mathrm{Ney}}$ and assigns samples in proportion to the arm standard deviations, i.e. $T_i = \tfrac{\sigma_i}{\sum_{i}^K \sigma_i} N$, and leads to the total sum of MSE to be
However, when the arm variances are unknown, the oracle allocation is no longer directly available and the variances must be learned. As mentioned above, many practitioners in this case turn directly toward uniform sampling $\pi^{\mathrm{uni}}$, i.e. $p_{t,i}^{\pi^{\mathrm{uni}}} = 1/K$ for all $t \in [N]$ and $i \in [K]$, which is equivalent to setting $T_j = \tfrac{N}{K}$ in a completely randomized trial. By simple algebra, the total sum of MSE under uniform sampling is
By Cauchy-Schwarz inequality we can show (ref) $\le$ (ref), which is expected since we emphasized on the optimality of (ref). Nonetheless, the gap between these two benchmarks highlights the main question of this section:
This naturally raises the possibility of adaptive sampling, where early observations are used to guide the remaining budget toward a more efficient allocation. As mentioned in the related literature, there have been works that show that asymptotically adaptive policies can be designed to approach Neyman Allocation (dai2023clip, zhao2023adaptiveneymanallocation). However, to the best of our knowledge, no works exist that show when adaptive scheme can achieve better performance over uniform sampling in finite-samples.
Before presenting our main results, there are two distinct technical issues in moving from the oracle benchmark to a data-driven adaptive design. The first concerns the sampling policy itself. When the arm variances are unknown, the Neyman allocation must be learned from the data, which naturally suggests sequential adaptation. However, under a fully adaptive policy, the resulting allocation process is difficult to analyze tractably in finite samples. To keep the MSE calculation tractable, we therefore restrict attention to a two-stage design: a pilot stage, with $N_1$ units, is first used to estimate arm-specific quantities, and the remaining budget $N_2 := N - N_1$ is then allocated according to a plug-in Neyman allocation that is fixed after the pilot stage. This is termed Adaptive Neyman Allocation by zhao2023adaptiveneymanallocation. We view this approach conservative to the fully adaptive approach. In other words, if a single adaptive update can already improve over uniform sampling, then more fully adaptive variants may plausibly yield further gains.
Formally, we estimate the Neyman allocation after the pilot stage via \[ \hat p_i^{\mathrm{Ney}} := \frac{\hat\sigma_i}{\sum_{j=1}^K \hat\sigma_j}, \qquad i\in[K], \] where $\hat\sigma_i$ is the typical sample standard deviation estimator using $N_1$ samples. The resulting two-stage adaptive Neyman policy, denoted as $\pi^{\mathrm{AN}}$, is defined by \[ p^{\pi^\mathrm{AN}}_{t,i} =
\]
The second issue concerns how the estimator will change under adaptive design. In the oracle benchmark, the sample mean leads directly to the variance-driven Neyman objective. Under adaptive allocation, however, the clean static risk expression in (ref) no longer holds in adaptive sampling, and different estimators induce different expression of MSE. A natural first candidate is the Horvitz--Thompson estimator, defined as \[ \hat\mu_i^{\mathrm{HT}} := \frac{1}{N}\sum_{t=1}^N \frac{\operatorname{\mathbbm{1}}\{I_t = i\}X_t}{p_{t,i}}, \quad i \in [K], \] which accounts for the unequal assignment probabilities induced by the second-stage allocation. However, by Lemma (ref) in the Appendix, the MSE for HT estimator depends on the second moments $\mu_i^2+\sigma_i^2$, which does not align with the Neyman benchmark in (ref). For this reason, we instead use a stylized pilot-centered inverse-propensity-weighted (PCIPW) estimator,
where the pilot mean is \[ \hat\mu_i^{\mathrm{pilot}} := \frac{1}{n_1}\sum_{t=1}^{N_1}\operatorname{\mathbbm{1}}\{I_t = i\}X_t, \quad n_1 := N_1/K. \]
We outline the two-stage adaptive Neyman Allocation formally in Algorithm (ref). Before stating the main theoretical result, we give an intermediary Lemma (ref) (proved in Appendix (ref)) that details the components that make up the MSE of such an adaptive policy.
The decomposition shed light to where adaptive allocation can help, and where it can introduce additional cost. The second term is the adaptive variance: after the pilot stage, the PCIPW correction has variance proportional to $\sigma_i^2/p_{t,i}$, so assigning larger probability to high-variance arms moves the design toward the Neyman benchmark in (ref). The third term is an interaction penalty between pilot mean error and inverse-propensity reweighting; it is small when $\hat\mu_i^{\mathrm{pilot}}$ is accurate, but can be amplified when the estimated allocation assigns a small probability to arm $i$. Thus, the finite-sample comparison with uniform sampling depends on whether the variance reduction from plug-in Neyman allocation dominates the pilot-estimation and reweighting cost. We will directly quantify this tradeoff in Theorem (ref).
To clarify the intuition, we assume each arm $i$'s reward distribution $\nu_i$ to be Normally distributed with mean $\mu_i$ and variance $\sigma_i^2$. This assumption is mainly used to keep the comparison transparent: under normality, the pilot mean and pilot variance are independent. The mechanism behind the result, however, is not specific to Gaussian rewards. For general $i.i.d.$ outcomes with suitable moment conditions, the pilot mean and variance estimators satisfy the usual asymptotic normal approximations, so an analogous comparison can be obtained with an additional approximation slack term. Summing up, under Algorithm (ref), Lemma (ref)'s decomposition can be simplified to be:
Since $\hat p_i^{\rm Ney}$ consists of $\{\hat \sigma_j\}_{j=1}^k$, we can replace it by a combination of $F-$distribution and the population variance. We can, therefore, make a direct comparison of population parameters and hence derive a sufficient condition for Two-stage Adaptive Neyman Allocation to outperform Uniform Sampling. We are now ready to show our main theorem.
The full proof of Theorem (ref) is in Section (ref). Now, the left hand side term is a bit opaque in the current form, and by adopting Jensen's inequality on the $F-$distribution term $\beta_\nu$, we can derive the following corollary, which is operationally more intuitive.
Corollary (ref) gives a clear intuition for when adaptive Neyman allocation can improve upon uniform sampling. The pilot size $N_1$ measures how much information is collected before the second-stage allocation is chosen, capturing the strength of the learning phase. The terms $V$ and $S^2-V$ summarize the variance structure across arms, and measure how heterogeneous the arm variances are. When all arms have similar variances, the right-hand side is close to its smallest possible value, making the inequality harder to satisfy for a fixed pilot size. Indeed, when variances are similar, there is little reason to allocate them differently, so adaptive Neyman allocation has little advantage over uniform sampling. By contrast, when the variances differ substantially across arms, there is more to gain from reallocating effort toward the high-variance arms, and the sufficient condition becomes easier to satisfy; in that case the right-hand side becomes larger, so the same left-hand side is more likely to fall below it.
We remind readers that our aim is not to propose an asymptotic optimal algorithm. Rather, we show that even a simple data-driven adaptive procedure can outperform uniform sampling. Consequently, this result provides guidance to experimenters: for sufficiently large pilot size $N_1$, an adaptive policy can improve upon the uniform baseline even for inference.
So far, our focus has been purely inferential. In many experiments, however, estimation accuracy is not the only objective. While the experiment is running, the experimenter may also care about online performance, namely, about avoiding too many pulls of clearly suboptimal arms. This naturally leads to a joint inference--regret problem. For simplicity, in this section, we will use the sample mean estimator for the inference objective. Changing the sample mean to other estimators is unlikely to affect this section's main asymptotic rate result, since the main asymptotic result is governed by the sampling frequencies rather than by the particular bias-corrected form of the estimator.
To formalize this problem, Let $i^\star \in \arg\max_{i \in [K]} \mu_i$ denote an optimal arm, and for each arm $i$ define the suboptimality gap $\Delta_i := \mu_{i^\star} - \mu_i$. Throughout this section, we will assume for simplicity that the optimal arm is unique, so that \(\Delta_i > 0\) for all \(i \neq i^\star\). The cumulative and average regret up to horizon $N$ is defined as \[ R_N := \sum_{i=1}^K \Delta_i T_i, \quad \bar R_N := \frac{1}{N} \sum_{i=1}^K \Delta_i T_i \] which measures the performance loss induced by allocating samples to suboptimal arms. This is the usual pseudo-regret formulation in stochastic bandits: rather than comparing realized rewards pathwise through the random observations $X_t$, it compares the expected reward of the chosen arm to that of an optimal arm through the population means $\mu_i$. This makes the criterion depend on the sampling design itself, rather than on additional outcome noise, and is therefore the natural quantity to combine with an inference objective.
We now measure performance through a single objective that balances statistical accuracy and online performance. Fix a weight \(\lambda \in (0,1)\) that determines the two objectives relative importance. For the inferential term, we use \(\sqrt{\mathrm{MSE}}\), which is the Root MSE (RMSE), rather than MSE itself, since the regret term grows linearly whereas MSE is quadratic in the estimation error. This puts the two terms on a more comparable scale. Our objective $\mathcal J_N$, therefore, is
Equivalently, writing out the mean squared error term explicitly, we have
Our goal in this section is to understand \[ \min_{\pi} \mathcal J_N(\pi) \] for different policies $\pi$.
We start with the oracle fixed-allocation problem. Let $\mathcal S_K := \Bigl\{p\in\mathbb R_+^K : \sum_{i=1}^K p_i = 1\Bigr\}$ denote the simplex of allocation vectors. For \(p=(p_1,\dots,p_K)\in\mathcal S_K\), we interpret \(p_i\) as the target fraction of the horizon assigned to arm \(i\), so that \(T_i = N p_i\).
Under such a static allocation, the joint objective (ref) becomes
The first term is the oracle RMSE under fixed counts, while the second is the average regret induced by allocating a fraction \(p_i\) of the horizon to arm \(i\). The next lemma characterizes the optimizer of (ref), serving as a benchmark throughout the rest of the section.
The proof for Lemma (ref) is shown in Section (ref). Lemma (ref) gives the best benchmark one could hope for: even with full knowledge of the instance, the optimal joint tradeoff decays only at rate \(N^{-1/3}\). This rate therefore becomes the natural target for any adaptive procedure. The structure of the oracle solution is also intuitive. Since regret pushes mass toward the best arm, while inference requires each arm to be sampled, the optimizer places almost all of its mass on the best arm, but still allocates a vanishing fraction of order \(N^{-1/3}\), equivalently $N^{2/3}$ pulls, to each suboptimal arm. This is the amount needed to keep the inferential term from becoming too large.
The oracle benchmark above is informative but not implementable, since it depends on the unknown variances and arm gaps. We now ask a more practical question:
The answer is yes, and our proposed policy is surprisingly simple and practical. The key idea is to separate the two roles played by the policy. To guarantee inference, we must keep exploring all arms with a certain rate. To control regret, we would otherwise rely on a standard regret-minimizing bandit algorithm. This suggests a very simple mixture: at round \(t\), explore with probability of order \(t^{-1/3}\), and exploit otherwise. To keep our result as general as possible, we allow our policy to mix with most adaptive algorithms. However, we do still need regular conditions, which we state now, on the adaptive algorithm to achieve the optimal rate:
This is a standard minimax-type regret guarantee, satisfied by many familiar bandit algorithms, including UCB or Thompson Sampling (LAI19854,pmlr-v23-agrawal12, lattimore2020bandit). The advantage of Definition (ref) is that the theorem below does not depend on the fine details of the exploitation rule; any algorithm with a bound of the form (ref) can be plugged in. We are now ready to state the main result of this subsection, introducing the Static Allocation Rate Policy in Algorithm (ref) and its main theorem guarantee.
The theorem is deliberately general. It does not claim that the exploration distribution \(p^0\) is itself ideal for inference; rather, it shows that one can attain the optimal asymptotic order without estimating the oracle allocation online. This makes the result easy to interpret: a gradually vanishing amount of forced exploration is enough to guarantee inferential efficiency, while the exploitation algorithm takes care of the regret minimization.
Theorem (ref) is useful as a conceptual benchmark: it shows that the oracle rate is attainable by a very simple and broadly applicable adaptive strategy. At the same time, the theorem is intentionally coarse. The exploration distribution \(p^0\) is fixed in advance, and the result only guarantees the correct asymptotic order. It does not attempt to improve upon constants, i.e., finite-sample performance, nor does it adapt to the instance structure learned during the experiment.
On the other hand, the oracle benchmark in Lemma (ref) suggests that the best allocation should not explore all arms under an arbitrary fixed probability. Rather, it should tilt its inferential effort toward high-variance arms while still favoring high-mean arms to control regret. This motivates a more structured policy that interpolates between two natural extremes:
Hence we propose a policy that refines the simple SARP construction by explicitly balancing a regret-driven policy and an inference-driven policy within a smaller, more interpretable policy class. Before stating the algorithm, it is helpful to build intuition from an oracle interpolation between two extreme allocations: the rooted-Neyman allocation \(p^{\rm rN}\), which optimizes statistical efficiency, and the oracle best-arm vector \(e_{i^\star}\), which places all mass on the optimal arm. For \(x\in[0,1]\), define \[ p^{(x)} := (1-x)e_{i^\star} + x p^{\rm rN}, \quad p_i^{\rm rN} := \frac{\sigma_i^{2/3}}{\sum_j^k \sigma_j^{2/3}}. \] Along this path, the parameter \(x\) controls only the amount of exploration, while the exploration shape is fixed by \(p^{\rm rN}\). From the oracle MSE calculation in Section (ref), we can do similar calculation to show the rooted-Neyman rule allocates mass proportionally to \(\sigma_i^{2/3}\) for RMSE optimization.
We now examine how the joint objective (ref) behaves along this one-dimensional path. For every suboptimal arm \(i\neq i^\star\), we have \(p_i^{(x)}=x p_i^{\rm rN}\), so the regret contribution is linear in \(x\): \[ (1-\lambda)\sum_{i=1}^K p_i^{(x)}\Delta_i = (1-\lambda)x\sum_{i\neq i^\star}\Delta_i p_i^{\rm rN} = (1-\lambda)Lx, \quad L:=\sum_{i\neq i^\star}\Delta_i p_i^{\rm rN}. \] At the same time, the dominant suboptimal-arm RMSE contribution is of order \[ \frac{\lambda}{\sqrt N}\sum_{i\neq i^\star}\frac{\sigma_i}{\sqrt{x p_i^{\rm rN}}} = \frac{\lambda M}{\sqrt N}x^{-1/2}, \quad M:=\sum_{i\neq i^\star}\sigma_i (p_i^{\rm rN})^{-1/2}. \] Thus, after fixing the rooted-Neyman exploration profile, the remaining one-dimensional tradeoff is roughly \[ \frac{\lambda M}{\sqrt N}x^{-1/2} + (1-\lambda)Lx. \] Optimizing this expression yields an exploration level of order \[ x_N^\star \asymp \Bigl(\frac{\lambda M}{(1-\lambda)L}\Bigr)^{2/3}N^{-1/3}. \] This directly motivates the exploration rule used in the algorithm: we replace the unknown oracle quantities \(M\) and \(L\) by their plug-in estimates \(\hat M_{t-1}\) and \(\hat L_{t-1}\), and uses the same \(t^{-1/3}\) scaling online. We are now ready to present Neyman-Adaptive Rate Policy (NARP) in Algorithm (ref), together with its theoretical guarantee in Theorem (ref).
Although Theorem (ref) establishes the same \(N^{-1/3}\) rate as SARP, the plug-in quantities \(\hat M_{t-1}\) and \(\hat L_{t-1}\) are the online analogues of the two oracle coefficients that govern the interpolation between inference-driven and regret-driven allocation. Thus, NARP should be viewed as a practical and interpretable refinement of SARP rather than as a claim of global optimality among all adaptive bandit procedures (ErraqabiLVBL17, simchi-levi_multi-armed_2025). Comparing Algorithm (ref) and Algorithm (ref), the key distinction is that both use an exploration rate of the correct order \(t^{-1/3}\), but SARP leaves the leading constant unspecified, taking the form \(c_x t^{-1/3}\), whereas NARP adaptively calibrates this constant from the data. In addition, SARP permits any fixed exploration distribution \(p^0\), while NARP uses a plug-in rooted-Neyman allocation, which targets the lower-RMSE side of the inference--regret tradeoff by assigning exploratory pulls according to the estimated variance structure. This finer oracle-calibrated behavior is not captured by the rate theorem, but it is the mechanism behind the finite-sample improvements observed in Section (ref).
Now we provide simulations that validate our theoretical finding in Section (ref) and (ref).
We start with a theorem-guided analysis. Before turning to Monte Carlo simulations, we use Theorem (ref) to compute the minimum pilot size \(N_1^{\min}\) required for Algorithm (ref) to have lower total MSE than uniform sampling under different variance configurations. We also report \[ \text{Oracle Gain} := 100 \times \left(\frac{KV/N - S^2/N}{KV/N}\right) = 100\times\left(1 - \frac{S^2}{KV}\right), \] which measures the relative reduction in total MSE achieved by oracle Neyman allocation compared with uniform allocation, as derived in (ref) and (ref). This quantity is not the realized gain from adaptive sampling; rather, it summarizes the amount of variance heterogeneity and the maximum efficiency improvement. By contrast, \(N_1^{\min}\) is the theorem-implied pilot threshold above which the two-stage adaptive design is guaranteed to improve upon uniform sampling. Table (ref) reports these calculations and identifies the regimes in which adaptive allocation is expected to be more beneficial.
The table illustrates two distinct forces behind the benefit of adaptive allocation. First, the Oracle Gain is larger when the arm variances are more heterogeneous, because this is precisely the setting in which Neyman allocation differs most from uniform allocation. In the nearly-homogeneous variance case, Neyman and uniform allocation are close to equivalent, so there is little allocation advantage to learn, which is reflected in the configuration \(K=4\) and \(\boldsymbol\sigma=[3,3,3,4]\). Second, the adaptive procedure can realize this advantage only after the pilot stage estimates the variance structure accurately enough. Thus, \(N_1^{\min}\) should be interpreted as the required learning-phase size: when the variances are similar, the oracle gain is small and more pilot samples may be needed before adaptation is guaranteed to outperform uniform sampling.
We now turn to a simulation study, using \(2000\) Monte Carlo replications throughout this section. We begin by examining Algorithm (ref) under varying pilot sizes \(N_1\). The goal is to confirm the effect of the length of the pilot phase on total MSE of the resulting two-stage adaptive Neyman procedure. As in Section (ref), we compare against uniform sampling and oracle Neyman as the main benchmarks. They are not included as columns in the tables since, for a fixed total budget \(N\), their total MSE does not depend on the pilot size \(N_1\).
We report results for two configurations that vary the heterogeneity of the variances $\sigma$. The overall pattern is consistent across both: as the pilot size \(N_1\) increases, the two-stage adaptive Neyman procedure improves steadily, reflecting the fact that a longer pilot phase yields more accurate variance estimates and therefore a better plug-in Neyman allocation in stage two.
This effect is most visible in Table (ref), which corresponds to the stronger heteroskedastic \(K=4\) setting. There, the adaptive procedure begins to outperform uniform once \(N_1\) reaches 12, and quickly moves closer to the oracle benchmark. This is exactly the regime in which adaptive allocation has the most to gain, since the variance profile is highly uneven across arms.
Table (ref) shows the same phenomenon in the more \(K=10\) setting, but in a moderate form. For small \(N_1\), the adaptive procedure underperforms uniform sampling because the pilot estimates are still too noisy. As \(N_1\) grows, however, the total MSE decreases steadily, and the method begins to outperform uniform sampling around \(N_1=80\), in line with the threshold prediction from Table (ref).
Overall, these experiments reinforce the theoretical message of this subsection: adaptive allocation is not automatically beneficial when the pilot phase is too short or when the underlying variance is homogeneous, but it becomes effective once the pilot budget is large enough to recover the underlying variance structure with reasonable accuracy.
We now turn to a simulation study of Algorithms (ref) and (ref). We compare their empirical behavior against two baselines: uniform sampling and the ForcingBalance algorithm of ErraqabiLVBL17. The latter benchmark is derived for a different objective: ErraqabiLVBL17 uses a proxy inference term associated with the static-allocation problem and introduces a \(\sqrt{N}\) scaling in the tradeoff, whereas our performance metric is based on summed armwise RMSE and average regret. We therefore remove the $\sqrt N$ scaling in ForcingBalance and compare accordingly. Throughout this section, we use 1{,}000 Monte Carlo replications and fix \(\lambda=0.5\). For implementation, SARP uses \(c_x=1\) and a uniform exploration distribution \(p_0\), NARP uses \(m_0=2\) and \(\alpha=1\); in both SARP and NARP, the exploitation component is Gaussian Thompson Sampling.
Table (ref) highlights the main qualitative distinction between SARP and NARP. NARP achieves substantially better inferential performance than SARP, as reflected in its much smaller summed RMSE, but this comes at the price of higher regret. This is consistent with the intended role of NARP: it preserves a more nuanced exploratory allocation in order to improve estimation accuracy. By contrast, SARP uses a simpler exploration schedule and therefore tilts more strongly toward exploitation at this finite horizon, leading to lower regret but substantially worse inference.
In this instance, ForcingBalance achieves the best joint objective among the non-oracle policies. We view it as an important benchmark, but not as a direct head-to-head comparison under identical objectives. ForcingBalance is tailored to solving a per-round inference--regret optimization problem over a broad policy class, while our policies deliberately use a more restricted interpolation form. Formally, we consider a more practical scenario where a practitioner has already picked an exploration policy for inference, e.g., adaptive Neyman allocation or a base $\pi_0$, and a desirable regret-minimizing bandit algorithm, e.g., Thompson sampling. We restrict our adaptive policies to policies that specifically linearly interpolates between two such policies, where our flexibility is not in a specifically chosen explore or exploit policy but how to interpolate, with the right rate, any two given policies. This restriction leads to a closed-form exploration rule, separates the inference-aware exploration component from the underlying regret-minimizing algorithm, and makes the resulting procedure easier to implement in practice. In particular, the same construction can be paired with standard regret-minimization algorithms without redesigning the full allocation rule around a specialized objective.
Figure (ref) plots the combined objective as we increase total budget \(N\) from $500$ to $10,000$. Two features are worth emphasizing. First, both SARP and NARP exhibit the same qualitative decay pattern as the oracle benchmark, consistent with the \(N^{-1/3}\) scaling provided in Theorem (ref) and (ref). Second, NARP remains uniformly below SARP in the combined objective over this range of horizons, indicating that the plug-in adaptation of the exploration level yields improvement over the simpler fixed-rate exploration schedule under this configuration.
The decomposition in Figure (ref) reveals the core mechanism behind our two policies. SARP places more weight on exploitation and therefore controls regret more aggressively, while NARP preserves a more informative allocation and obtains substantially better inferential accuracy. To illustrate this more carefully, we present two panels in Figure (ref) that show how the inference--regret mechanism changes for two additional configurations. Panel (b) considers a 10-arm regime with substantial variance heterogeneity and weak separation among the top arms. In this setting, aggressive exploitation can sharply worsen the inferential component, so the gain from moving beyond SARP is visible. Panel (a) considers a 6-arm regime, where the best arm is easier to identify and the variance profile is less extreme. Here, the inferential penalty from exploitation is smaller, so SARP's lower-regret behavior becomes more valuable and its joint objective can come close to both the oracle benchmark. Together, the two panels illustrate that SARP can perform well when estimation is relatively easy, while NARP becomes more useful when variance heterogeneity and small top-arm gaps make inference harder.
These comparisons suggest the following interpretation. When the best arm is relatively easy to identify, the simpler and more exploitation-oriented structure of SARP can be adequate, since the inferential cost of exploration remains limited. As the problem becomes harder---because the top-arm gap shrinks, the variance profile becomes more uneven, or both---the benefit of NARP becomes more visible.
Overall, these simulations show that SARP and NARP provide a transparent and tunable policy family whose behavior is theoretically grounded and easy to interpret. SARP offers a lighter, more exploitation-oriented rule, while NARP uses the estimated variance and gap structure to protect inferential precision. In this sense, our contribution is to identify a practically interpretable frontier of adaptive designs when both inference and regret need to be taken into account.
In summary, this paper studies adaptive experimentation through two complementary lenses: statistical efficiency and online performance. We show that in the pure-inference setting, adaptive allocation can improve upon uniform sampling in finite samples once the pilot phase is informative enough. We then show that in the joint inference--regret setting, simple adaptive policies can attain the natural oracle rate while expressing different operating points on the same tradeoff frontier. The resulting message is not that one adaptive rule uniformly dominates all others, but that the value of adaptivity depends on the structure of the instance and on the experimenter's objective. By making this dependence explicit, our framework helps clarify when adaptive sampling is beneficial, when it is worth paying for additional exploration, and how that choice can be encoded in a policy that remains interpretable and practically deployable.
The authors thank Jinglong Zhao and Chonghuan Wang for helpful discussions.