# Graph-Dependent Regret Bounds in Multi-Armed Bandits with Interference

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 58 references that are in the map.
- First posted on arXiv 10 Mar 2025.

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

- [Causal Bandits: Learning Good Interventions via Causal Inference](https://mlsanity.com/paper/1606.03203/) (2016)
- [Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Arms](https://mlsanity.com/paper/1407.8339/) (2014)
- [Nonstochastic Multi-Armed Bandits with Graph-Structured Feedback](https://mlsanity.com/paper/1409.8428/) (2014)
- [High-Dimensional Sparse Linear Bandits](https://mlsanity.com/paper/2011.04020/) (2020)
- [Improving Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms and Its Applications](https://mlsanity.com/paper/1703.01610/) (2017)
- [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)
- [Thompson Sampling for the MNL-Bandit](https://mlsanity.com/paper/1706.00977/) (2017)
- [Statistical Efficiency of Thompson Sampling for Combinatorial Semi-Bandits](https://mlsanity.com/paper/2006.06613/) (2020)
- [Multiple-Play Bandits in the Position-Based Model](https://mlsanity.com/paper/1606.02448/) (2016)
- [Causal Inference Under Interference And Network Uncertainty](https://mlsanity.com/paper/1907.00221/) (2019)
- [Multiple Randomization Designs: Estimation and Inference with Interference](https://mlsanity.com/paper/2112.13495/) (2021)
- [Estimating Total Treatment Effect in Randomized Experiments with Unknown Network Structure](https://mlsanity.com/paper/2205.12803/) (2022)
- [Tight Lower Bounds for Combinatorial Multi-Armed Bandits](https://mlsanity.com/paper/2002.05392/) (2020)
- [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)
- [Multi-Armed Bandits with Interference](https://mlsanity.com/paper/2402.01845/) (2024)
- [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)
- [Network Cluster-Robust Inference](https://mlsanity.com/paper/2103.01470/) (2021)
- [Pure Exploration Beyond Reward Feedback: The Role of Post-Action Context](https://mlsanity.com/paper/2502.03061/) (2025)
- [Confounded Budgeted Causal Bandits](https://mlsanity.com/paper/2401.07578/) (2024)
- [Leveraging heterogeneous spillover in maximizing contextual bandit rewards](https://mlsanity.com/paper/2310.10259/) (2023)
- [Learning Exposure Mapping Functions for Inferring Heterogeneous Peer Effects](https://mlsanity.com/paper/2503.01722/) (2025)

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

- [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)
- [Learning Peer Influence Probabilities with Linear Contextual Bandits](https://mlsanity.com/paper/2510.19119/) (2025)
- [Learning to target with network interference](https://mlsanity.com/paper/2605.27794/) (2026)
- [Graph Dimensionality Reduction for Contextual Bandits: Structure-Specific Regret Bounds under Approximate Smoothness and Noisy Eigenspaces](https://mlsanity.com/paper/2606.27917/) (2026)

## Abstract (arXiv)

We study multi-armed bandits under network interference, where each unit's reward depends on its own treatment and those of its neighbors in a given graph. This induces an exponentially large action space, making standard approaches computationally impractical. We propose a novel algorithm that uses the local graph structure to minimize regret. We derive a graph-dependent upper bound on cumulative regret that improves over prior work. Additionally, we provide the first lower bounds for bandits with arbitrary network interference, where each bound involves a distinct structural property of the graph. These bounds show that for both dense and sparse graphs, our algorithm is nearly optimal, with matching upper and lower bounds up to logarithmic factors. When the interference graph is unknown, a variant of our algorithm is Pareto optimal: no algorithm can uniformly outperform it across all instances. We complement our theoretical results with numerical experiments, showing that our approach outperforms the baseline methods.