Confidence Intervals for Policy Evaluation in Adaptive Experiments

1 Introduction

• Adaptive designs prioritize their objectives, such as identifying the best arm or maximizing welfare, and may collect little data about suboptimal treatments.Afterward, experimenters may need to answer questions the design did not target, while extreme undersampling or non-converging assignment probabilities complicate reuse of the data.Source: §1 · p. 1
• In the two-stage example, the adaptive sample mean for arm 1 is biased downward because reduced sampling leaves early negative fluctuations uncorrected.Arms with initial upward fluctuations receive more samples and regress toward their means, while downward fluctuations may not be corrected; this bias occurs even without selection effects.Source: §1 · pp. 2–3
• Inverse-probability weighting fixes the sample-mean bias but produces non-normal, heavier-tailed estimates as assignment probabilities approach zero.Increasing inverse-probability weights on later observations can exacerbate inference problems when an arm becomes unlikely to be assigned.Source: §1 · p. 3
• Estimators that rely on assignment probabilities converging to constants can be brittle when experiments end before convergence, so reliable inference must also cover non-convergent designs.The convergence rate can depend on unknown differences between treatment values, and limited experimental budgets may leave little data collected after convergence.Source: §1 · p. 3
• The proposed test statistic is asymptotically unbiased and normal even when assignment probabilities converge to zero or do not converge.The method targets frequentist confidence intervals for a pre-specified policy and can also supply normal estimates for adaptive-hypothesis testing procedures.Source: §1 · pp. 2–3

2.1 Unbiased scoring rules

• Unbiased scoring rules averaged with a deterministic 1/T normalization estimate arm values without bias, even when scores are correlated over time.The usual sample average with a random arm-specific denominator is not covered by this result; AIPW adds a mean-zero control variate that can reduce variance and reduces to IPW when its regression estimate is zero.Source: §2.1 · p. 5

2.2 Asymptotically normal test statistics

• Unweighted averages of unbiased scores can be heavy-tailed because their conditional variances depend on inverse propensities, and their variance may fail to converge even when propensities stay bounded below.With multiple optimal arms, uniform weights can leave runs dominated by different randomly selected arms, undermining variance convergence.Source: §2.2 · pp. 6, 8
• Adaptive weighting can yield consistent arm-value estimates and asymptotically normal studentized statistics when effective sampling, variance convergence, and moment conditions hold.Weights can offset rapidly decaying propensities, but cannot ensure consistent estimation if an arm is sampled only finitely often; inappropriate weights can also prevent variance convergence.Source: §2.2 · pp. 7–8

2.3 Constructing adaptive weights

• History-adapted stick-breaking weights make the variance-convergence sum deterministic, while allocation rates provide flexibility and must respect propensity-decay bounds.Theorem 3’s sufficient conditions constrain how quickly propensities may decay; in bandits, suboptimal arms must be sampled more often than rate-optimal algorithms imply, while sublinear regret remains possible.Source: §2.3 · pp. 8–9
• Constant and two-point allocation schemes satisfy the stated allocation-rate bounds, with the two-point heuristic averaging optimal-arm and decaying-propensity scenarios using Thompson-sampling posterior probabilities.The constant scheme ensures variance convergence but is not variance-optimal; the two-point scheme is designed as a practical alternative to a future-propensity-based heuristic.Source: §2.3 · pp. 9–10

3 Estimating Treatment Effects

• Adaptively weighting differences of AIPW scores yields asymptotically normal treatment-effect estimates and is a special case of a result for more general targets.The general result applies to targets with doubly robust estimators whose Riesz representer is a function of the treatment assignment mechanism.Source: §3 · pp. 10–11
• Under modified Theorem 2 conditions and extra assumption (21), subtracting adaptively weighted arm-value estimates gives a consistent treatment-effect estimate with an asymptotically standard normal studentized statistic.The two arm-specific studentized statistics are asymptotically jointly normal with identity covariance.Source: §3 · p. 11
• The experiments use the difference of arm-value estimates, which the authors found more powerful, presumably because separate arm weights provide more control over variance.Directly targeting the treatment-effect difference avoids an assumption like (21) and may be more robust to non-stationary potential-outcome distributions.Source: §3 · p. 11
• The general result also covers targets beyond arm values and treatment effects, including a continuous-dose policy estimand of how outcomes change under slightly larger doses.For this example, an unbiased scoring rule can be adaptively weighted to support inference about the estimand.Source: §3 · p. 11

4 Numerical Experiments

• The study compares sample-mean, AIPW, and adaptively weighted AIPW estimators for arm values and treatment effects, with normal-approximation intervals and time-uniform sample-mean confidence sequences.AIPW-based intervals use a plug-in reward mean and estimated variance; the time-uniform method follows Howard et al. (2021), and treatment-effect intervals combine arm intervals by the union bound.Source: §4 · p. 12
• Simulations use three arms with additive uniform noise, no-, low-, and high-signal arm values, and modified Thompson sampling with a lower bound on assignment probabilities.Treatment probabilities are adjusted to impose et(w) ≥ (1/K)t^-0.7.Source: §4 · p. 12
• Although unbiased, uniform-weight AIPW performs poorly in RMSE and interval width; undersampling raises its variance, and its studentized statistics are far from normal with no signal.In low- and high-signal settings, it fails to account for undersampling of the bad arm; in the no-signal case, its studentized statistics are far from normal.Source: §4 · p. 12
• Two-point allocation more aggressively downweights unlikely observations with large inverse propensity weights, controlling bad-arm variance; studentized statistics are approximately normal even with about 50 bad-arm observations.The reported roughly correct coverage applies to normal confidence intervals around adaptively weighted AIPW estimates.Source: §4 · p. 13
• Sample means are downwardly biased for undersampled arms, with larger bias in the low-signal case; normal-approximation intervals severely under-cover with little or no signal.The bias can be non-monotonic in signal strength; confidence sequences from Howard et al. (2021) are conservative but often wide.Source: §4 · p. 13
• Two-point adaptively weighted AIPW yields smaller RMSE and tighter intervals than constant allocation, while sample means often have lower MSE, especially with stronger signal.Normal intervals around two-point adaptively weighted AIPW have asymptotically nominal coverage at a pre-specified horizon; Howard et al. (2021) confidence sequences are often conservative and wider but remain valid over time and under arbitrary stopping. The AIPW method requires known propensity scores that decay slowly enough, while confidence sequences require outcome-distribution information but no assignment-process restrictions.Source: §4 · p. 13, Figure 2 · p. 14

5 Related literature

• Optimal-allocation literature targets optimal policies or finite-dimensional parameters, where undersampling treatments relevant to the estimand is itself suboptimal.Classical clinical-trial allocation strategies optimize criteria such as determining whether a treatment helps or harms relative to control; van der Laan (2008) generalizes optimal allocation to estimation or hypothesis testing for finite-dimensional parameters.Source: §5 · p. 14
• van der Laan and Lendle (2014) reduce to augmented inverse propensity weighting for arm-value estimation, with asymptotic normality requiring non-negligible assignment to the treatment of interest.Luedtke and van der Laan (2016) propose a stabilized variant that corresponds to the adaptively weighted estimator with constant allocation rates; its applicability to bandits is noted by Luedtke and van der Laan (2018), while Zhang et al. (2020) refine an analogous weighted-average estimator for batched adaptive designs.Source: §5 · pp. 14–16
• Deshpande et al. (2017) propose W-decorrelation for policy-value estimation in non-contextual and linear-contextual bandits, yielding consistent, asymptotically normal regression-coefficient estimates under strong serial correlation.For multi-armed bandits, the paper’s numerical evaluation finds W-decorrelation produces arm-value estimates with high variance.Source: §5 · p. 16

6 Discussion

• The paper provides sufficient conditions for inference on parameters not targeted by adaptive experiments and constructs averaging estimators with asymptotically normal, low-variance distributions.Its empirical applications show better mean squared error and coverage than existing alternatives.Source: §6 · p. 16
• A simpler estimator is essentially indistinguishable from the adaptively weighted estimator in numerical experiments and is appealing for evaluating a single arm.The paper focuses on estimator (6) because it supports formal study in a more general setting.Source: §6 · p. 16
• The discussion leaves open optimal confidence-interval width and generalization to contextual bandits, non-stationarity, and random stopping.The paper gives no optimality guarantees for interval width and calls for characterizing minimum worst-case expected width.Source: §6 · pp. 16–17

A Additional Figures

• The appendix adds further simulations on arm-value estimates, their distributions at T = 10^5, two-point allocation versus W-decorrelation, and allocation over time, plus an application in Section A.5.The reported simulations aggregate at least 10,000 runs with 95%-confidence-interval error bars.Source: A Additional Figures · p. 20

A.1 Behavior of arm value estimators over time

• For the good arm Q(3), all methods have negligible bias, small root mean-squared error, and roughly correct coverage for large T; difficulty estimating the bad arm explains much of the difficulty estimating Δ(3, 1).Figure 5 shows estimates of Q(3) across experiment lengths.Source: §A.1 · p. 20, Figure 5 · p. 21

A.2 Asymptotic normality of arm value estimators

• When there is no signal, neither unweighted AIPW nor the sample mean has an approximately normal distribution.Figures 8–10 show studentized-statistic distributions for adaptively weighted estimators under different weighting schemes, alongside the sample-mean deviation divided by its standard error.Source: §A.2 · p. 23, Figure 8 · p. 24, Figure 9 · p. 24

A.3 Comparison to W-decorrelation

• W-decorrelation attains correct coverage but requires more variance, typically yielding much higher mean squared error than the two-point allocation method.Figure 11 compares the adaptively weighted estimator with two-point allocation evaluation weights against W-decorrelation.Source: §A.3 · p. 25, Figure 11 · p. 26

A.4 λt path

• Under the two-point allocation scheme, λt decays over time, so earlier observations receive more weight.Figure 12 tracks (T − t)λt for good and bad arms across simulation designs; the passage’s description of the bottom-row behavior is incomplete.Source: §A.4 · p. 26, Figure 12 · p. 27

A.5 Introduction example, revisited.

• The example uses two identical arms with unit normal rewards, switching from equal allocation in the first half to 90% allocation to the leading arm in the second half.The leading arm is selected by its sample mean at T/2.Source: §A.5 · p. 27
• After studentization, the adaptively-weighted estimator is centered and approximately normal, while the sample mean and inverse-propensity weighted estimator lack normal asymptotic distributions.The deviations from normality are relatively small, but self-normalization alone is insufficient; the evaluation weights also play a role.Source: §A.5 · p. 27, Figure 13 · p. 28
• The adaptively-weighted estimator is more thin-tailed than the inverse-propensity weighted estimator and less biased than the sample average.Figure 13 aggregates 1,000,000 replications, with the top row showing estimates for T = 10^6.Source: §A.5 · p. 27, Figure 13 · p. 28

• The section proves more general versions of Theorems 2–4 from the main body.Source: B Limit theorems for adaptively… · p. 29

B.1 Setting

• The setting has iid real-valued potential outcomes, known history-dependent treatment assignment distributions, and a target that is a continuous linear functional of mean potential outcomes.The Riesz representer of the functional is used to define an unbiased scoring rule.Source: §B.1 · p. 29
• Under the theorem’s stated conditions, the adaptively weighted estimator is consistent for ψ(m), and its studentized statistic is asymptotically normal.The setup uses history-measurable nonnegative weights satisfying the specified sampling, variance-convergence, and moment conditions.Source: §B.1 · p. 30
• The variance-stabilizing weight recursion satisfies the stated sampling, variance-convergence, and Lyapunov conditions when the allocation-rate and other theorem conditions hold.The passage specifies λ_t < 1 for t < T and λ_T = 1.Source: §B.1 · p. 30
• Under the stated conditions, adaptively weighted score differences yield jointly normal studentized statistics and a consistent estimator of ψ1(m) − ψ2(m).The studentized statistic for the difference is asymptotically standard normal.Source: §B.1 · p. 31

B.2 Specializing general results

• For arm value ψ(m) = m(w), the Riesz representer is γ_t = I{· = w}/e_t(w), yielding the arm-value AIPW scoring rule.Theorem 2 gives sufficient conditions for consistency and asymptotic normality of the adaptively weighted estimator using this score.Source: §B.2 · pp. 31–32
• Theorem 3’s arm-value variance-stabilizing schemes specialize Theorem 6’s general weights, with the remaining general condition satisfied for any δ > 1.The specialization uses E_{t−1} = 1/e_t(w); the other conditions correspond to the arm-value conditions.Source: §B.2 · p. 32
• The direct treatment-effect score subtracts the two arm-value scores, is unbiased for m(w1) − m(w2), and is covered by Theorem 5 for consistency and asymptotic normality.Its Riesz representer is I{· = w1}/e_t(w1) − I{· = w2}/e_t(w2).Source: §B.2 · p. 32
• The alternative treatment-effect estimator assigns separate evaluation-weight sequences to the arm scores; Theorem 4 establishes its asymptotic normality as a special case of Theorem 7.Theorem 7’s conditions (38) and (40) simplify to Theorem 4’s conditions (21) and (22), while condition (39) always holds.Source: §B.2 · p. 32
• For the average derivative ψ(m) = ∫m′(w)f(w)dw, the Riesz representer is γ_t(w) = −f′(w)/f_t(w), assuming f(w) vanishes at ±∞.Source: §B.2 · p. 32

C.1 Proof of Theorem 5

• Theorem 5 establishes consistency of ψ̂_T and asymptotic normality of its studentized version by first proving a central limit theorem for an auxiliary martingale.The proof concludes by showing that the studentization remainder vanishes in probability.Source: §C.1 · pp. 33, 38, 39
• The conditional variance of the unbiased score is bounded below and above under the stated variance and uniform boundedness assumptions.These bounds support the Lyapunov and variance-convergence arguments.Source: §C.1 · pp. 34–35
• The Lyapunov condition for the auxiliary martingale follows by bounding score-difference moments by moments of γ_t and applying the theorem’s Lyapunov assumption.The normalized Lyapunov expression converges to zero in probability.Source: §C.1 · pp. 35–36
• Conditional variance convergence is shown by decomposing the variance sum into a dominant weighted term and a negligible remainder, yielding Z_T/EZ_T = 1 + o_p(1).The remainder is negligible because it is a weighted average of a bounded sequence converging almost surely to zero, with individually negligible weights.Source: §C.1 · pp. 36–37
• Studentization is justified by convergence of the auxiliary martingale’s quadratic variation to one and by showing the remaining terms vanish in probability.The proof uses consistency of ψ̂_T and variance and negligible-weight bounds to control those terms.Source: §C.1 · p. 39

Joint normality

• By the martingale CLT and Cramér–Wold, (ξ_T,1, ξ_T,2) converges to N(0, I), and the feasible studentized statistics share this limit.The limit is a jointly normal random vector with identity covariance.Source: §C.2 · pp. 40, 42, 43

Variance convergence

• Riesz-representation substitutions cancel leading covariance terms, while variance convergence and consistency-convergence for one arm make the remaining cross-term bounds negligible.The proof uses boundedness and shows the cross-term contribution vanishes in probability.Source: §C.2 · pp. 40–42

Lyapunov condition

• The Lyapunov condition follows because both terms in its bound converge to zero asymptotically.Source: §C.2 · p. 42

C.3 Proof of Theorem 6

• For variance convergence, recursion (35) and λ_T = 1 make the numerator in condition (29) constant; the denominator is the unconditional expectation of (93).Source: §C.3 · p. 44
• The Lyapunov condition holds when α < δ/(2+δ): the weights keep its denominator constant, and allocation-rate bounds make its numerator vanish.The bounding argument uses a uniformly bounded factor; for α < 1, its bound is 1/(1−α).Source: §C.3 · pp. 44–46
• The infinite-sampling condition is established for α < 1 by showing its numerator diverges in separate cases, T0 ≥ T/2 and T0 ≤ T/2.Source: §C.3 · pp. 46–47

C.4 Asymptotic normality of alternative estimators

• When appropriately studentized, bQh-avg is asymptotically normal under the same conditions as adaptively weighted estimator (6).The proof concludes by applying Slutsky’s theorem.Source: §C.4 · pp. 47, 49
• The studentized statistics are asymptotically equivalent because their numerators and variances are equivalent, with only the first variance term asymptotically non-negligible.The argument compares the alternative estimator with an adaptively weighted estimator using the oracle plug-in ˆmt(w) = Q(w).Source: §C.4 · pp. 47–49

C.5 Two-point allocation bounds

• The proof verifies that the two-point allocation parameter lies within Theorem 3’s stated bounds.It uses that the parameter is a convex combination of values for high-propensity and decaying-propensity scenarios.Source: §C.5 · p. 49

D.1 Modified thompson sampling

• Modified Thompson Sampling starts each arm with prior mean 0 and variance 1, updates a normal-prior, normal-likelihood posterior, and draws L samples per arm.The algorithm uses these draws to compute raw Thompson Sampling probabilities.Source: §D.1 · p. 50
• The algorithm floors assignment probabilities at xt%, shrinks the other arms’ probabilities to make the total one, then samples and stores probabilities, selected arms, and rewards.The adjusted Thompson Sampling probabilities are used for every period in the batch.Source: §D.1 · p. 50

D.2 Non-asymptotic confidence sequences

• Howard et al.’s empirical-Bernstein confidence sequence uses a Gamma-Exponential mixture boundary with c = 2 and a variance process based on summed empirical variances.The scaling parameter equals the outcome support width.Source: §D.2 · p. 50
• For 90% confidence intervals on an arm difference, the method combines two-sided 95% intervals for each arm using a union bound.For arms 1 and 3, the resulting interval is [ℓ3 −u1, u3 −ℓ1]. The bounds are optimized for the “bad” arm using its expected pull count, assuming known outcome variance and support.Source: §D.2 · p. 51