Research map / Bandits and online learning / Multi-armed bandits
Multi-Armed Bandits with Interference: Bridging Causal Inference and Adversarial Bandits
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.
Introduces multi-armed bandits with interference (MABI) under spatial decaying interference and proposes EXP3 with robust random clustered randomization and a Horvitz-Thompson implicit-exploration estimator, achieving optimal expected regret and a high-probability bound vanishing in market size N.
Problem
Cumulative reward maximization in online experiments where each unit's reward depends on all units' treatments (interference) and reward functions are adversarial, a setting not covered by prior work focused on final-output estimation.
Approach
Combines EXP3 with implicit exploration and a Horvitz-Thompson-IX estimator, and replaces uniform spatial clustering with a robust random partition that boosts exposure probability from p^4 to Omega(p), yielding a high-probability regret bound that vanishes as N grows, while switchback policies cannot achieve this.
Key results
- Switchback policy (EXP3-based) achieves eO(sqrt(kT)) expected regret, and a matching lower bound Omega(sqrt(kT)) holds for any MABI policy.
- The EXP3-HT-IX policy with robust random partition achieves optimal expected regret and a high-probability tail bound that vanishes as N grows (e.g., P(Reg > RegOPT + N^-c log(1/delta)) <= delta).
- For T=50 and tau=T^{2/3}, switchback tail probability ranges 2.7% to 0.01% while clustered randomization is astronomically small (e.g., 10^-14 to 10^-39 for N=T, c=1/2).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use an EXP3 switchback policy instead of a general MABI policy | MABI · General interference | expected regret: eO(√kT) | Helped |
| Use a clustered-randomization policy with the HT-IX estimator instead of a switchback policy | MABI · General interference | tail mass of regret as N grows: P (RegSB − RegOPT > τ) ≤ e−τ; P (RegCR − RegOPT > τ) ≤ e−Ncτ | Helped |
| Randomize cluster boundaries with the Robust Random Partition (RRP) | Clustered randomization · Spatial interference | exposure probability: from pO(1) to Ω(p) | Helped |
| Add an implicit-exploration parameter to the Horvitz-Thompson estimator | HT-IX estimator · MABI | estimator variance | Helped |
| Use switchback policies rather than clustered randomization | MABI · General interference | dependence of regret tail mass on N: P (RegSB − RegOPT > τ) ≤ e−τ; P (RegCR − RegOPT > τ) ≤ e−Ncτ | Hurt |
Surprising findings
- Expected regret cannot be improved by a large N: any policy suffers Omega(sqrt(kT)) expected regret on some MABI instance.
Experimental setup
Metrics: expected regret high-probability regret bound value at risk of regret
Baselines: switchback policy uniform clustered randomization (Leung 2022) EXP3
Builds on: EXP3 EXP3-IX Horvitz-Thompson estimator under spatial interference (Leung 2022) switchback experiments randomized graph cluster randomization (Ugander and Yin 2023)
Closest papers by meaning
- Mutli-Armed Bandits with Network Interference (NeurIPS 2024 · similarity 0.93)
- Design-Based Bandits Under Network Interference: Trade-Off Between Regret and Statistical Inference (NeurIPS 2025 · similarity 0.93)
- Linear Contextual Bandits With Interference (ICML 2025 · similarity 0.91)
- Learning to target with network interference (NeurIPS 2026 · similarity 0.90)
- Multi-Armed Bandits With Best-Action Queries (NeurIPS 2026 · similarity 0.88)
- Causal Bandits: The Pareto Optimal Frontier of Adaptivity, a Reduction to Linear Bandits, and Limitations around Unknown Marginals (ICML 2024 · similarity 0.88)
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.