# Multi-Armed Bandits with Interference

arXiv: https://arxiv.org/abs/2402.01845 · HTML: https://mlsanity.com/paper/2402.01845/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 60 references that are in the map.
- First posted on arXiv 2 Feb 2024.

## Builds on (most cited first, 20 of 20)

- [Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms](https://mlsanity.com/paper/1911.10635/) (2019)
- [Explore no more: Improved high-probability regret bounds for non-stochastic bandits](https://mlsanity.com/paper/1506.03271/) (2015)
- [Identification and estimation of treatment and interference effects in observational studies on networks](https://mlsanity.com/paper/1609.06245/) (2016)
- [Graph cluster randomization: network exposure to multiple universes](https://mlsanity.com/paper/1305.6979/) (2013)
- [Design and analysis of experiments in networks: Reducing bias from interference](https://mlsanity.com/paper/1404.7530/) (2014)
- [Combinatorial Cascading Bandits](https://mlsanity.com/paper/1507.04208/) (2015)
- [Experimental Design in Two-Sided Platforms: An Analysis of Bias](https://mlsanity.com/paper/2002.05670/) (2020)
- [Optimal Regret Analysis of Thompson Sampling in Stochastic Multi-armed Bandit Problem with Multiple Plays](https://mlsanity.com/paper/1506.00779/) (2015)
- [Design and Analysis of Switchback Experiments](https://mlsanity.com/paper/2009.00148/) (2020)
- [Thompson Sampling for the MNL-Bandit](https://mlsanity.com/paper/1706.00977/) (2017)
- [Multiple-Play Bandits in the Position-Based Model](https://mlsanity.com/paper/1606.02448/) (2016)
- [Markovian Interference in Experiments](https://mlsanity.com/paper/2206.02371/) (2022)
- [Switchback Experiments under Geometric Mixing](https://mlsanity.com/paper/2209.00197/) (2022)
- [Randomized Graph Cluster Randomization](https://mlsanity.com/paper/2009.02297/) (2020)
- [Causal Network Motifs: Identifying Heterogeneous Spillover Effects in A/B Tests](https://mlsanity.com/paper/2010.09911/) (2020)
- [Adversarial Combinatorial Bandits with General Non-linear Reward Functions](https://mlsanity.com/paper/2101.01301/) (2021)
- [Rate-Optimal Cluster-Randomized Designs for Spatial Interference](https://mlsanity.com/paper/2111.04219/) (2021)
- [Average Direct and Indirect Causal Effects under Interference](https://mlsanity.com/paper/2104.03802/) (2021)
- [Network Cluster-Robust Inference](https://mlsanity.com/paper/2103.01470/) (2021)
- [Clustered Switchback Designs for Experimentation Under Spatio-temporal Interference](https://mlsanity.com/paper/2312.15574/) (2023)

## Built on by (most cited first, 10 of 10)

- [Online Experimental Design With Estimation-Regret Trade-off Under Network Interference](https://mlsanity.com/paper/2412.03727/) (2024)
- [Multi-Armed Bandits with Network Interference](https://mlsanity.com/paper/2405.18621/) (2024)
- [Linear Contextual Bandits with Interference](https://mlsanity.com/paper/2409.15682/) (2024)
- [Unraveling the Interplay between Carryover Effects and Reward Autocorrelations in Switchback Experiments](https://mlsanity.com/paper/2403.17285/) (2024)
- [Graph-Dependent Regret Bounds in Multi-Armed Bandits with Interference](https://mlsanity.com/paper/2503.07555/) (2025)
- [Balancing Interference and Correlation in Spatial Experimental Designs: A Causal Graph Cut Approach](https://mlsanity.com/paper/2505.20130/) (2025)
- [Scalable Policy Maximization Under Network Interference](https://mlsanity.com/paper/2505.18118/) (2025)
- [Graph Learning Is Suboptimal in Causal Bandits](https://mlsanity.com/paper/2510.16811/) (2025)
- [Design-Based Bandits Under Network Interference: Trade-Off Between Regret and Statistical Inference](https://mlsanity.com/paper/2510.07646/) (2025)
- [Learning to target with network interference](https://mlsanity.com/paper/2605.27794/) (2026)

## Abstract (arXiv)

Experimentation with interference poses a significant challenge in contemporary online platforms. Prior research on experimentation with interference has concentrated on the final output of a policy. The cumulative performance, while equally crucial, is less well understood. To address this gap, we introduce the problem of em Multi-armed Bandits with Interference (MABI), where the learner assigns an arm to each of N experimental units over a time horizon of T rounds. The reward of each unit in each round depends on the treatments of em all units, where the influence of a unit decays in the spatial distance between units. Furthermore, we employ a general setup wherein the reward functions are chosen by an adversary and may vary arbitrarily across rounds and units. We first show that switchback policies achieve an optimal em expected regret tilde O(√ T) against the best fixed-arm policy. Nonetheless, the regret (as a random variable) for any switchback policy suffers a high variance, as it does not account for N. We propose a cluster randomization policy whose regret (i) is optimal in em expectation and (ii) admits a high probability bound that vanishes in N.