Design-based theory for causal inference from adaptive experiments

1. Problem Statement

Adaptive experimental designs (e.g., multi-armed bandits, covariate-adaptive randomization, sequential rerandomization) dynamically update treatment assignment probabilities based on accumulated data. While widely used in business, medicine, and policy, existing causal inference theories for these designs face significant limitations:

• Superpopulation Assumption: Most current literature assumes units are independent and identically distributed (i.i.d.) from a superpopulation. This assumption fails when the distribution of units evolves over time (non-exchangeable units), leading to biased estimates.
• Conservative Variance Estimation: Finite-population inference (design-based) is often more conservative than superpopulation inference. Existing methods struggle to provide sharp variance estimates, especially when using complex "black-box" outcome models (e.g., machine learning).
• Non-converging Probabilities: Many adaptive designs (like $\epsilon$-greedy bandits) do not have treatment probabilities that converge to a constant, complicating asymptotic analysis.
• Nonadaptive Analysis Limitations: Standard covariate adjustment methods for nonadaptive experiments often require strong assumptions (e.g., correct model specification or cross-fitting with Bonferroni corrections) to ensure valid inference when using flexible machine learning models.

2. Methodology and Framework

The authors propose a finite-population, design-based framework where potential outcomes and covariates are treated as fixed, and randomness arises solely from the treatment assignment mechanism.

A. Estimators

The paper focuses on two primary estimators for the finite-population average treatment effect (or linear combinations thereof, $\tau_C$):

1. Inverse-Propensity-Weighted (IPW):
   $$\hat{Y}_{ipw}(z) = \frac{1}{T} \sum_{t=1}^T \frac{\mathbb{I}(Z_t=z)}{e_t(z)} Y_t$$
   where $e_t(z)$ is the propensity score (probability of treatment $z$ at time $t$ given history $H_t$).
2. Augmented IPW (AIPW):
   $$\hat{Y}_{aipw}(z) = \frac{1}{T} \sum_{t=1}^T \left[ \frac{\mathbb{I}(Z_t=z)}{e_t(z)} Y_t + \left(1 - \frac{\mathbb{I}(Z_t=z)}{e_t(z)}\right) \hat{m}_t(z) \right]$$
   where $\hat{m}_t(z)$ is an adaptive estimator of the potential outcome $Y_t(z)$ constructed using only information in $H_t$ (the history up to time $t$). This allows for the integration of black-box machine learning models.

B. Theoretical Tools

• Martingale Structure: The authors leverage the fact that the estimation errors form a martingale difference sequence with respect to the filtration of the history $H_t$. This allows the application of the Martingale Central Limit Theorem (CLT).
• Variance Estimation:
  • They derive a standard sample covariance estimator ($\hat{V}_{aipw}$) which is generally conservative (upward biased) in finite populations.
  • They propose a sharp covariance estimator ($\tilde{V}_{aipw}$) that subtracts the sample covariance of the residuals ($Y_t - \hat{m}_t$). This estimator becomes sharp (unbiased) when the residuals are additive across units, significantly reducing conservativeness.

C. Extensions

• Block Adaptive Designs: The theory is extended to settings where units arrive in blocks (groups), and randomization occurs within blocks based on previous block history (e.g., sequential rerandomization).
• Nonadaptive Designs: The authors propose treating nonadaptive designs as if they were adaptive by constructing the outcome model $\hat{m}_t(z)$ sequentially. This induces a martingale structure that validates the use of black-box estimators without the need for cross-fitting or strong stability assumptions.

3. Key Contributions

1. Finite-Population Design-Based Theory

The paper establishes the first rigorous design-based theory for adaptive experiments that accommodates:

• Non-exchangeable units: Units can have evolving distributions over time.
• Non-converging and vanishing probabilities: The theory holds even if $e_t(z)$ does not converge to a constant or vanishes at specific rates (e.g., $t^{-1/2+\delta}$).
• Black-box outcome models: Valid inference is guaranteed for AIPW estimators even when $\hat{m}_t(z)$ is a complex, non-converging machine learning model, provided it satisfies specific martingale conditions.

2. Sharp Variance Estimation

The authors introduce a new covariance estimator for the AIPW estimator that leverages adaptive regression residuals.

• Result: The estimator is generally conservative but becomes sharp (i.e., the variance estimate equals the true variance) when the residuals from the adaptive regression of potential outcomes on covariates are additive across units. This addresses the inherent conservativeness of finite-population inference.

3. Adaptive Covariate Adjustment for Nonadaptive Designs

A methodological contribution is the proposal to analyze standard nonadaptive experiments using the adaptive AIPW framework.

• Benefit: By constructing the outcome model sequentially (using only past data), the method induces a martingale structure. This allows for valid inference with flexible black-box models (like Random Forests) that would otherwise require strong assumptions or cross-fitting with Bonferroni corrections in standard nonadaptive analysis.

4. Unification of Adaptive Designs

The framework unifies the theoretical treatment of diverse designs, including:

• Multi-armed bandits (contextual and non-contextual).
• Covariate-adaptive randomization (e.g., biased coin, minimization).
• Sequential rerandomization (filling a gap in existing literature where inference for sequential rerandomization was previously lacking).

4. Key Results and Theoretical Guarantees

• Unbiasedness: Both IPW and AIPW estimators are unbiased for the finite-population average treatment effect under general adaptive randomization.
• Asymptotic Normality: Under regularity conditions (variance convergence and Lindeberg conditions), the estimators satisfy a Central Limit Theorem:
  $$\sqrt{T}(\hat{\tau}_{aipw} - \tau_C) \xrightarrow{d} N(0, \Sigma)$$
  where the asymptotic variance depends on the conditional variance of the residuals.
• Validity of Confidence Intervals: The proposed Wald-type confidence intervals (based on the sharp variance estimator) achieve the nominal coverage rate asymptotically.
• Conditions for Validity: The theory provides specific sufficient conditions for the decay of variance in propensity scores and outcome models, accommodating both vanishing and non-converging probabilities.

5. Simulation and Empirical Evidence

The paper validates the theory through simulations:

• Adaptive Covariate Adjustment: In nonadaptive settings, the proposed adaptive AIPW method with black-box models (Random Forests) achieved valid coverage (approx. 95%) and shorter confidence intervals compared to standard methods. In contrast, standard nonadaptive adjustment with Random Forests led to severe undercoverage (68.7%) due to violation of independence assumptions.
• Sequential Rerandomization: The method was applied to sequential rerandomization, demonstrating a 70.6% reduction in RMSE and a 71.3% reduction in confidence interval length compared to completely randomized designs, while maintaining valid coverage.
• Vanishing Probabilities: Simulations confirmed that inference remains valid when treatment probabilities vanish at rates $t^{-1/2+\delta}$ ($\delta \ge 0$), but fails if the rate is too aggressive ($\delta < 0$), aligning with theoretical bounds.

6. Significance

This paper represents a major advancement in causal inference by:

1. Bridging the Gap: It connects the fields of adaptive experimental design (often associated with online learning and bandits) and finite-population causal inference (the gold standard for randomized trials).
2. Enabling Machine Learning: It provides a rigorous theoretical justification for using complex, data-driven outcome models (black boxes) in adaptive experiments without relying on the often unrealistic i.i.d. superpopulation assumption.
3. Improving Efficiency: By introducing sharp variance estimators and adaptive adjustment for nonadaptive designs, it offers practical tools to reduce the width of confidence intervals and improve the precision of causal estimates in real-world settings where units are not exchangeable.
4. Generalizability: The framework is broad enough to cover a wide spectrum of modern experimental designs, making it a foundational reference for researchers and practitioners in statistics, economics, and computer science.