Research map / Learning theory and algorithms / Sample complexity
Asymptotically Optimal and Computationally Efficient Average Treatment Effect Estimation in A/B testing
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Derives an asymptotic lower bound on expected sample size for adaptive A/B tests producing a CI for the ATE with (ϵ,δ)-coverage, and proposes two asymptotically optimal policies (P1 plug-in, P2 Neyman-style computationally efficient).
Problem
Estimating a confidence interval of the average treatment effect in an A/B test with width at most ε and miscoverage at most δ while minimizing expected sample size, with adaptive treatment assignment.
Approach
Lower bound via a non-convex max-min optimization over alternative environments with a stability condition; a plug-in D-tracking policy P1 attains it, and P2 tracks the small-ε limit of the optimal allocation, which equals the Neyman allocation proportional to outcome standard deviations, avoiding the per-step optimization.
Key results
- Policy P2 requires roughly 50% fewer expected samples than the uniform RCT policy PRCT in the exponential example (e.g., 3.74e4 vs 7.85e4 at delta=10%).
- For Bernoulli outcomes with mu_A=0.98, mu_B=0.5, eps=0.2, delta=0.01, P2 needs 2672 expected samples vs 4034 for Clip-OGD and 4573 for the Neyman benchmark of Dai et al. (2024).
- In the small-epsilon limit, the optimal allocation to treatment A is w(mu_A,mu_B)=sigma_A/(sigma_A+sigma_B), and l*(eps)/eps^2 tends to a closed-form constant (Theorem 5.3).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use P2's adaptive assignment instead of uniform randomized assignment | A/B testing · Exponential outcomes (μA=10, μB=0.1), ϵ=0.5, δ=10% | expected sample size: 7.85 × 10^4 -> 3.74 × 10^4 | Helped |
| use P2's adaptive assignment instead of uniform randomized assignment | A/B testing · Exponential outcomes (μA=10, μB=0.1), ϵ=0.5, δ=5% | expected sample size: 8.62 × 10^4 -> 4.14 × 10^4 | Helped |
| use P2's adaptive assignment instead of uniform randomized assignment | A/B testing · Exponential outcomes (μA=10, μB=0.1), ϵ=0.5, δ=1% | expected sample size: 1.02 × 10^5 -> 4.98 × 10^4 | Helped |
| use P2's adaptive assignment instead of Clip-OGD sampling | A/B testing · Bernoulli outcomes (μA=0.98, μB=0.5), ϵ=0.2, δ=0.01 | expected sample size: 4034 -> 2672 | Helped |
| use P2's adaptive assignment instead of the fixed Neyman benchmark assignment | A/B testing · Bernoulli outcomes (μA=0.98, μB=0.5), ϵ=0.2, δ=0.01 | expected sample size: 4573 -> 2672 | Helped |
Surprising findings
- The asymptotically optimal allocation does not depend on eps for Gaussian outcomes and is nearly insensitive to eps in general, so a simple Neyman-style rule performs statistically indistinguishably from the computationally heavy plug-in policy P1.
Limitations
- Assumes outcome distributions in single-parameter exponential family or bounded support; general distributions not covered.
- Non-contextual setting only; extension to contextual assignment left to future work.
- Assumption 4.5 (joint quasi-concavity) verified analytically only for Gaussians and numerically for others.
Experimental setup
Metrics: expected sample size E[tau_delta] lower bound on E[tau_delta]
Baselines: uniform randomized assignment (RCT / PRCT) Clip-OGD (Dai et al., 2024) Neyman benchmark (Dai et al., 2024)
Builds on: Garivier & Kaufmann D-tracking Neyman allocation best arm identification Kaufmann information-theoretic lower bound
Closest papers by meaning
- Optimistic Algorithms for Adaptive Estimation of the Average Treatment Effect (ICML 2025 · similarity 0.88)
- Active Adaptive Experimental Design for Treatment Effect Estimation with Covariate Choice (ICML 2024 · similarity 0.88)
- Efficient Adaptive Experimentation with Noncompliance (NeurIPS 2025 · similarity 0.88)
- Strategic A/B testing via Maximum Probability-driven Two-armed Bandit (ICML 2025 · similarity 0.86)
- Constructing Confidence Intervals for Average Treatment Effects from Multiple Datasets (ICLR 2025 · similarity 0.85)
- Adaptive Data-Borrowing for Improving Treatment Effect Estimation using External Controls (NeurIPS 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.