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

Fateme Jamshidi, Mohammad Shahverdikondori, Negar Kiyavash
Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, PMLR 337:2442-2460, 2026.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v337-jamshidi26a, title = {Graph-Dependent Regret Bounds in Multi-Armed Bandits with Interference}, author = {Jamshidi, Fateme and Shahverdikondori, Mohammad and Kiyavash, Negar}, booktitle = {Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence}, pages = {2442--2460}, year = {2026}, editor = {Perković, Emilija and Malinsky, Daniel}, volume = {337}, series = {Proceedings of Machine Learning Research}, month = {17--21 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v337/main/assets/jamshidi26a/jamshidi26a.pdf}, url = {https://proceedings.mlr.press/v337/jamshidi26a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Graph-Dependent Regret Bounds in Multi-Armed Bandits with Interference %A Fateme Jamshidi %A Mohammad Shahverdikondori %A Negar Kiyavash %B Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2026 %E Emilija Perković %E Daniel Malinsky %F pmlr-v337-jamshidi26a %I PMLR %P 2442--2460 %U https://proceedings.mlr.press/v337/jamshidi26a.html %V 337 %X 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.
APA
Jamshidi, F., Shahverdikondori, M. & Kiyavash, N.. (2026). Graph-Dependent Regret Bounds in Multi-Armed Bandits with Interference. Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 337:2442-2460 Available from https://proceedings.mlr.press/v337/jamshidi26a.html.

Related Material