Technical Summary: DARTS – Targeting Prognostic Covariates in Budget-Constrained Sequential Experiments

1. Problem Formulation

The paper addresses a critical limitation in the design of Randomized Controlled Trials (RCTs): the assumption that high-quality, high-dimensional pretreatment covariates are known and available at no cost. In practice, acquiring such data is often costly due to medical diagnostics, survey fatigue, or computational overhead. This creates a trade-off between covariate-adaptive precision (which reduces treatment effect variance) and a strict measurement budget.

Furthermore, the efficacy of covariate-adaptive methods (like rerandomization) diminishes when the number of prognostic factors is large relative to the sample size, making simultaneous balance across all dimensions mathematically improbable. While existing literature provides frameworks for balancing known prognostic sets, many settings involve unknown prognostic factors. The authors propose a sequential setting where data arrives in batches (e.g., continuous enrollment), allowing the experimenter to iteratively learn which variables are most prognostic while adhering to a global budget $B$ across $T$ batches.

2. Methodology: DARTS

The authors introduce Dynamic Adaptive Rerandomization via Thompson Sampling (DARTS), a framework that treats covariate acquisition as a sequential optimization problem embedded within a valid causal inference design. The method operates in three interconnected layers:

A. The Acquisition Layer (Combinatorial Semi-Bandit)

The selection of covariates is framed as a Budgeted Combinatorial Multi-Armed Bandit (CBwK) problem with knapsack constraints.

• Arms: Each candidate covariate $j \in [p]$ is an arm with an unknown prognostic importance $\theta^*_j$ and a measurement cost $c_j$.
• Objective: Maximize the total expected "reward" (prognostic value) subject to the global budget $B$.
• Algorithm: The authors adapt Thompson Sampling to this setting (CBwK-LP-TS).
  • They maintain independent Beta posteriors for the reward probabilities of each covariate.
  • At each round $t$, they sample from these posteriors and solve a linear programming (LP) relaxation of the integer selection problem to choose a subset of covariates $S_t$ that maximizes the "bang-per-buck" ratio (sampled reward divided by effective cost).
  • Shadow Prices: To enforce the budget constraint, the algorithm uses multiplicative weight updates on shadow prices (dual variables) associated with the budget and individual arm constraints. This prevents early exhaustion of the budget on noisy, high-cost arms.
• Reward Proxy: Since true prognostic importance is unknown, the reward is estimated using fractional rewards derived from LASSO regression coefficients on control units only ($r_j(t) = |\hat{\lambda}_j| / \max |\hat{\lambda}_k|$). This avoids treatment effect contamination and leverages sparsity in high-dimensional settings.

B. The Design Layer (Rerandomization)

Once the subset $S_t$ is selected for batch $t$:

1. The selected covariates are measured for all $n$ units in the batch.
2. Rerandomization: The algorithm generates $K$ candidate treatment assignments and selects the one minimizing the Mahalanobis distance between treatment and control groups based on $S_t$.
3. Mirror Symmetry: To preserve exact marginal balance, the final assignment is chosen by a fair coin flip between the optimal assignment $z^*$ and its complement $1-z^*$.

C. The Estimation Layer

1. Within-Batch Estimation: The Average Treatment Effect (ATE) for batch $t$ is estimated using Lin-adjusted OLS (regression adjustment) on the selected covariates, with HC2 heteroskedasticity-robust variance estimates.
2. Cumulative Estimation: Batch estimates are combined using a precision-weighted inverse-variance meta-analysis. The cumulative estimator $\hat{\mu}_t$ is updated sequentially, weighting each batch by its estimated precision ($1/\hat{v}_t$).

3. Key Theoretical Contributions

The paper establishes three primary theoretical results:

1. Design-Based Unbiasedness (Theorem 1): The authors prove that adaptive covariate selection based on past batches does not bias the batch-level difference-in-means estimator. Because the covariate set $S_t$ is determined by the $\sigma$-field of previous batches ($F_{t-1}$) and is fixed before the current batch's randomization, the conditional expectation of the estimator remains the true ATE $\tau$.
2. Asymptotic Validity (Theorem 2): The cumulative inverse-variance weighted estimator achieves at least nominal asymptotic coverage. Under regularity conditions (including that no single batch dominates the variance and that rerandomization does not inflate variance), the estimator converges to a normal distribution with conservative coverage.
3. Regret Bounds (Theorems 3 & 4):
   • Upper Bound: They derive a Bayes risk bound for the acquisition layer (CBwK-LP-TS) that scales as $O(\sqrt{p \log(pT) \cdot \min(KT, B/c_{min})})$.
   • Lower Bound: They establish a minimax lower bound for the combinatorial semi-bandit problem that matches the upper bound up to logarithmic factors, demonstrating the near-optimality of the learning rate.
   • Fractional Rewards: They extend the theory to the practical fractional reward scheme, showing that the algorithm retains sublinear Bayes risk if the pseudo-posterior approximation error is small.

4. Empirical Results

The authors evaluate DARTS through extensive simulations across various Data Generating Processes (DGPs), including linear models and the nonlinear, correlated Liang DGP.

• Learning Capability: DARTS successfully concentrates the budget on true prognostic covariates. In tractable settings (e.g., $p=100, n=1000$), the posterior inclusion probabilities for signal covariates are significantly higher than for noise covariates.
• Precision Gains: DARTS systematically reduces the standard error of the ATE estimator compared to:
  • DiM: Complete randomization without adjustment.
  • Random: Rerandomization with a randomly selected subset of covariates (no learning).
  • ARMM/MADCovar: Existing adaptive randomization methods that use pre-selected covariate sets.
  • In several scenarios, DARTS achieves a relative efficiency (RE) of up to 3.56 over DiM, significantly closing the gap to the "Oracle" design (which knows the true prognostic set a priori).
• Robustness: The method degrades gracefully to a completely randomized baseline when the learning problem is intractable (e.g., very high dimensionality relative to the budget and horizon) but never substantially harms precision compared to random baselines.
• Validity: Empirical coverage rates remain at or near the nominal 95% level, confirming the theoretical validity guarantees.

5. Significance and Claims

The paper claims that DARTS represents a new problem formulation: adaptive covariate acquisition as part of sequential RCT design under a measurement budget.

Its primary significance lies in bridging the gap between causal inference and sequential decision-making (bandits):

• It demonstrates that one can learn which covariates to measure in real-time without compromising the design-based validity of the causal inference.
• It provides a rigorous theoretical framework (decoupling selection from randomization) that ensures the cumulative estimator remains unbiased and asymptotically valid despite the adaptive nature of the design.
• It offers a practical solution for settings where prognostic factors are unknown and data acquisition is costly, systematically closing the efficiency gap to oracle designs while maintaining strict inferential validity.

The authors note limitations, including the reliance on an independent arm assumption (though LASSO mitigates correlation issues) and the current restriction to fixed-horizon inference (sequential peeking invalidates coverage). They suggest future work could address correlated arms and anytime-valid inference.