Abstract: We investigate experimental design for randomized controlled trials (RCTs) with both equal and unequal treatment-control assignment probabilities. Our work makes progress on the connection between the distributional discrepancy minimization (DDM) problem introduced by Harshaw et al. (2024) and the design of RCTs. We make two main contributions: First, we prove that approximating the optimal solution of the DDM problem within a certain constant error is NP-hard. Second, we introduce a new Multiplicative Weights Update (MWU) algorithm for the DDM problem, which improves the Gram-Schmidt walk algorithm used by Harshaw et al. (2024) when assignment probabilities are unequal. Building on the framework of Harshaw et al. (2024) and our MWU algorithm, we then develop the MWU design, which reduces the worst-case mean squared error in estimating the average treatment effect. Finally, we present a comprehensive simulation study comparing our design with commonly used designs.
Introduction: The Challenge of Unequal Assignment
Randomized Controlled Trials (RCTs) are widely considered the gold standard for causal inference. While many experiments aim for a 50/50 split between treatment and control groups, practical constraints—such as high treatment costs, ethical considerations, or varying response rates—often necessitate unequal assignment probabilities. Ensuring that these "lopsided" groups remain balanced across observed covariates is critical for obtaining unbiased estimates of the Average Treatment Effect (ATE).
Recent advancements in Distributional Discrepancy Minimization (DDM) have provided a robust framework for balancing covariates while remaining resilient to unobserved factors. However, existing state-of-the-art methods, such as the Gram-Schmidt Walk (GSW), are optimized for equal assignment. This research addresses this gap by establishing the theoretical limits of DDM and introducing a superior algorithmic approach for general assignment probabilities.
Theoretical Limits: NP-Hardness of DDM
A primary contribution of this work is the formal proof that approximating the optimal solution for the DDM problem within a specific constant error is NP-hard. This theoretical result establishes that a perfect, universally efficient algorithm for covariate balancing is unlikely to exist. Consequently, the research focuses on developing sophisticated heuristics that provide high-quality approximations in polynomial time.
The Multiplicative Weights Update (MWU) Design
To overcome the limitations of the GSW algorithm in unequal assignment scenarios, we propose a design based on the Matrix Multiplicative Weights Update (MWU) framework. Unlike previous "walk-based" approaches, the MWU design frames the discrepancy problem as a minimax game against an adversary attempting to maximize estimation error.
The algorithm maintains a dynamic weight matrix that identifies the most imbalanced covariate directions. It utilizes a specialized MWU Oracle—a martingale-based random walk—to iteratively update assignments. As shown in the figure above, the algorithm categorizes constraints (rows) and tracks the state of assignment variables ("alive" vs. "not alive") to ensure the final design minimizes the worst-case Mean Squared Error (MSE) while strictly adhering to the target assignment probabilities.
Empirical Evaluation
The MWU design was rigorously tested against synthetic benchmarks and the classic LaLonde dataset, which evaluates job training programs using a mix of binary and numeric covariates (e.g., age, education, earnings).
Key Findings:
- Superior Accuracy: In linear outcome models, the MWU design achieved significantly lower MSE than competing methods. The best alternative designs often exhibited MSEs at least 2.61 times higher than the MWU approach.
- Robustness to Non-linearity: Even when the relationship between covariates and outcomes was non-linear (quadratic or cubic), the MWU design remained competitive with specialized methods like Rerandomization.
- Efficiency in Lopsided Trials: The MWU design successfully captures the robustness of simple Bernoulli trials while providing the precision of advanced balancing algorithms, particularly when assignment probabilities are highly unequal (e.g., 10/90 splits).
Conclusion and Future Directions
The MWU design represents a significant step forward in experimental design for general assignment probabilities. By bridging the gap between theoretical hardness and practical algorithmic implementation, it provides researchers with a more accurate tool for complex RCTs. While the current framework excels under linearity assumptions, future work may explore the integration of kernel methods to further enhance performance in highly non-linear environments. Additionally, optimizing the algorithm's computational intensity remains a priority for scaling to massive real-time A/B testing scenarios.
Summary updated