Research map / Probabilistic and scientific modeling / Treatment effects
Online Experimental Design With Estimation-Regret Trade-off Under Network Interference
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.
Proposes MAB-N, an online experimental design framework under network interference using exposure mapping, proves a Pareto-optimal estimation-regret trade-off, and gives the UCB-TSN algorithm (plus EXP3-TSN for adversarial settings).
Problem
Online experiments under network interference must balance ATE estimation accuracy against cumulative regret, but standard bandit and causal methods assume independent units (SUTVA) and the joint arm space K^N is exponentially large.
Approach
Reduce the super-arm space via exposure mapping onto a small set of exposure arms organized by clusters, establish a minimax lower bound on the product of squared regret and ATE error, and show a two-stage UCB (uniform exploration then UCB) attains this Pareto frontier.
Key results
- UCB-TSN and Standard achieve the lowest cumulative regret in simulation, while Uniform has the highest regret.
- UCB-TSN and Uniform give lower and more compact ATE estimation errors than the Standard method, which has more outliers.
- Theory: ATE error times sqrt(regret) is lower bounded by Omega(sqrt(|U_E|)), and UCB-TSN matches it up to log factors (Otilde(sqrt(|U_E|))).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use UCB-TSN with uniform exposure-arm exploration in the first stage | UCB-TSN · MAB-N stochastic setting | ATE estimation error: \tilde{O}\big(\sqrt{{\vert \U_\bbE \vert}/{T_1}}\big) | Helped |
| Use UCB exploration in the second stage after T1 exploration rounds | UCB-TSN · MAB-N stochastic setting | regret: \tilde{O}\big(\sqrt{\vert \U_\bbE \vert T} + T_1\big) | Helped |
| Set T1 ≥ √(|U_E|T) | UCB-TSN · MAB-N stochastic setting | estimation-regret trade-off: \tilde{O}(\sqrt{\vert \U_\bbE \vert}) | Helped |
| Use exposure mapping to reduce the original super-arm space | MAB-N · Network interference | regret: O\big(|d_s|^C\big) | Helped |
| Use UCB-TSN rather than EXP3EG, with T1 = O(T^{1-α}) | Single-unit, no-interference setting · Single-unit, no-interference setting | regret: {\tilde{O}}\big(K + T_1\big) vs. \tilde{O}(K^5 + T^{1-\alpha}) | Helped |
| Use UCB-TSN with T1 = T^{1-α} ∨ |U_E| rather than EXP3EG | Single-unit, no-interference setting · Single-unit, no-interference setting | ATE estimation error: \tilde{O}(\sqrt{{K}/{T_1}}) vs. \Tilde{O}({K^2}{T^{-\frac{1-\alpha}{2}}} ) | Helped |
| Set T1 = 0, removing the uniform-exploration stage (ablation) | UCB-TSN · 101-unit network simulation | cumulative regret | No clear effect |
| Set T1 = 0, removing the uniform-exploration stage (ablation) | UCB-TSN · 101-unit network simulation | maximum ATE estimation error | Hurt |
| Set T1 = T, using uniform exploration throughout (ablation) | UCB-TSN · 101-unit network simulation | cumulative regret | Hurt |
| Set T1 = T, using uniform exploration throughout (ablation) | UCB-TSN · 101-unit network simulation | maximum ATE estimation error | Helped |
| Use UCB-TSN with T1 = √(|U_E|T) rather than Standard (ablation) | UCB-TSN · 101-unit network simulation | maximum ATE estimation error | Helped |
| Use EXP3-TSN for adversarial rewards | MAB-N adversarial setting · MAB-N adversarial setting | estimation-regret trade-off: \tilde{O}(\sqrt{\vert \U_\bbE \vert}) | Helped |
Limitations
- Experiments are limited to a single simulated network with Bernoulli rewards and 1000 repetitions; no real-data evaluation.
- Assumes a predefined, time-invariant sampling rule and an exposure mapping that is fixed in advance.
- Several results rely on the assumption that exposure arm space size is at least 2 and at most T; the paper notes the adversarial and N-dependence results are discussed only partially.
Experimental setup
Datasets: simulated Bernoulli-reward network with 101 units
Benchmarks: simulated 101-unit network experiments
Metrics: cumulative regret maximum ATE estimation error
Baselines: EXP3EG Standard UCB-TSN with T_1=0 Uniform exploration (T_1=T)
Builds on: exposure mapping UCB EXP3 switchback experiments
Closest papers by meaning
- Higher-Order Causal Message Passing for Experimentation with Complex Interference (NeurIPS 2024 · similarity 0.91)
- Independent-Set Design of Experiments for Estimating Treatment and Spillover Effects under Network Interference (ICLR 2024 · similarity 0.91)
- Doubly Robust Causal Effect Estimation under Networked Interference via Targeted Learning (ICML 2024 · similarity 0.89)
- Mutli-Armed Bandits with Network Interference (NeurIPS 2024 · similarity 0.88)
- Balancing Interference and Correlation in Spatial Experimental Designs: A Causal Graph Cut Approach (ICML 2025 · similarity 0.87)
- Learning to target with network interference (NeurIPS 2026 · similarity 0.87)
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.