Research map / Bandits and online learning / Multi-armed bandits
Design-Based Bandits Under Network Interference: Trade-Off Between Regret and Statistical Inference
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.
Establishes a regret vs. ATE-estimation Pareto frontier for adversarial design-based bandits under network interference and proposes EXP3-N-CS, which combines EXP3 with an anytime-valid asymptotic confidence sequence and MAD exploration.
Problem
Adversarial multi-armed bandits with network interference face a trade-off: regret minimization can starve sub-optimal arms, hurting ATE estimation and continual inference; the trade-off is not characterized theoretically.
Approach
Extends the MAB-N exposure-mapping/clustering framework to the adversarial setting, proves a Pareto lower bound on sqrt(regret)×ATE error, and adds an IPW-based asymptotic confidence sequence plus a mixing exploration term (MAD, weight delta_t = t^{-alpha}) to EXP3 so that the regret-inference trade-off is tunable via alpha.
Key results
- Proves an Omega(sqrt(|U_E|)) lower bound on inf over estimators of max over instances of sqrt(regret)×ATE error, establishing the Pareto frontier.
- EXP3-N-CS achieves regret Õ(sqrt(|U_E|T)+T^{1-alpha}) and ATE error Õ(|U_E|^{1/2} T^{(alpha-1)/2}), matching the frontier for alpha in [0,1/2).
- In simulations on a 101-unit network with Bernoulli rewards, EXP3-N-CS with smaller alpha yields narrower CS and lower ATE error than Standard, while larger alpha yields lower regret comparable to Standard.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Uniform sampling instead of EXP3-N-CS | MAB-N simulation · 101-unit network simulation | cumulative regret | Hurt |
| Use EXP3-N-CS with larger α (0.4 or 0.49) instead of Uniform sampling | EXP3-N-CS · 101-unit network simulation | cumulative regret | Helped |
| Use Uniform sampling instead of Standard (δₜ = 0) | MAB-N simulation · 101-unit network simulation | confidence-sequence width | Helped |
| Use Standard (δₜ = 0) instead of Uniform sampling | MAB-N simulation · 101-unit network simulation | confidence-sequence width | Hurt |
| Decrease α in EXP3-N-CS (ablation) | EXP3-N-CS · 101-unit network simulation | confidence-sequence width | Mixed |
| Use EXP3-N-CS with smaller α instead of Standard (δₜ = 0) | MAB-N simulation · 101-unit network simulation | maximum ATE estimation error | Helped |
| Use Uniform sampling instead of Standard (δₜ = 0) | MAB-N simulation · 101-unit network simulation | maximum ATE estimation error | Helped |
| Set α to a smaller value in EXP3-N-CS (ablation) | EXP3-N-CS · 101-unit network simulation | maximum ATE estimation error | Helped |
Limitations
- Assumes linear growth of cumulative conditional variance (Omega(t)), stronger than prior work.
- Experiments are limited to simulated Bernoulli rewards on a single network topology.
- Lower bound proof is a sketch relying on constructed hard instances; asymptotic CS validity depends on regularity conditions.
Experimental setup
Metrics: cumulative regret confidence sequence width maximum ATE estimation error
Baselines: Standard (EXP3 without exploration mixing) Uniform sampling
Builds on: EXP3 MAB-N asymptotic confidence sequences exposure mapping
Closest papers by meaning
- Multi-Armed Bandits with Interference: Bridging Causal Inference and Adversarial Bandits (ICML 2025 · similarity 0.93)
- Mutli-Armed Bandits with Network Interference (NeurIPS 2024 · similarity 0.91)
- Linear Contextual Bandits With Interference (ICML 2025 · similarity 0.90)
- Learning to target with network interference (NeurIPS 2026 · similarity 0.89)
- Multi-Armed Bandits With Best-Action Queries (NeurIPS 2026 · similarity 0.88)
- Improved Best-of-Both-Worlds Regret for Bandits with Delayed Feedback (NeurIPS 2025 · 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.