Research map / Bandits and online learning / Multi-armed bandits
Mutli-Armed Bandits with 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.
Studies multi-armed bandits with sparse network interference where each unit's reward depends on at most s neighbors' treatments; uses Fourier analysis to get a sparse linear representation and proposes explore-then-commit algorithms (OLS when the network is known, Lasso when unknown) plus a sequential elimination variant.
Problem
Regret minimization for adaptive treatment assignment to N units with A actions each under cross-unit interference, where naive MAB approaches scale with A^N actions and prior work compares to only the best constant policy.
Approach
Use discrete Fourier analysis on the Boolean encoding of actions to show sparse network interference makes each unit's reward a sparse linear function of Fourier characters (at most A^s nonzero coefficients), enabling per-unit regression-based explore-then-commit with regret compared to the optimal joint action.
Key results
- Known-interference explore-then-commit achieves regret O~((A^s T)^{2/3}); sequential elimination achieves O~(sqrt(N A^s T)).
- Unknown-interference Lasso variant achieves regret O~(N^{1/3} (A^s T)^{2/3}), with the T^{2/3} dependence argued to be unimprovable.
- In simulations with N up to 10 and A=2, the proposed Network MAB methods outperform UCB and scale mildly with N rather than exponentially.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Network MAB (Known) instead of UCB | Network MAB (Known) · Simulations, cumulative regret | regret | Helped |
| Use Network MAB (Unknown) instead of UCB | Network MAB (Unknown) · Simulations, cumulative regret | regret | Helped |
| Provide the interference graph to the algorithm | Network MAB · Simulations, regret scaling with N | regret | Helped |
| Use known-interference OLS rather than unknown-interference Lasso | Network MAB · Simulations, regret scaling with T | exploration duration | Helped |
Surprising findings
- Comparing to the optimal joint action rather than the best constant policy makes the problem combinatorially harder, yet regret remains sublinear with polynomial dependence on N.
Limitations
- T^{2/3} regret rate in the explore-then-commit algorithms is not optimal in T; the sqrt(T) algorithm pays sqrt(N).
- Experiments are small-scale simulations (N up to 10) and require horizons on the order of A^N.
- Comparison to prior grid-based interference work is not empirical because no public implementation was available.
Experimental setup
Benchmarks: simulated sparse network interference environments
Metrics: cumulative regret
Baselines: UCB
Builds on: sparse linear bandits explore-then-commit sequential elimination (Even-Dar et al.) UCB
Closest papers by meaning
- Multi-Armed Bandits with Interference: Bridging Causal Inference and Adversarial Bandits (ICML 2025 · similarity 0.93)
- Learning to target with network interference (NeurIPS 2026 · similarity 0.92)
- Design-Based Bandits Under Network Interference: Trade-Off Between Regret and Statistical Inference (NeurIPS 2025 · similarity 0.91)
- Linear Contextual Bandits With Interference (ICML 2025 · similarity 0.91)
- Improved Regret and Contextual Linear Extension for Pandora's Box and Prophet Inequality (NeurIPS 2025 · 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.