Multi-Armed Bandits with Interference: Bridging Causal Inference and Adversarial Bandits

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. Cumulative performance, while equally important, is less well understood. To address this gap, we introduce the problem of Multi-armed Bandits with Interference (MABI), where the learner assigns an arm to each of N experimental units over T rounds. The reward of each unit depends on the treatments of all units, and this dependence decays in distance. The reward functions, chosen by an adversary, may vary arbitrarily over space and time. We first show that a switchback policy achieves an optimal expected regret of Õ( √ T ) against the best fixed-arm policy; however, the regret as a random variable suffers high variance. We propose a policy based on a novel clustered randomization scheme, whose regret (i) is optimal in expectation and (ii) admits a high-probability bound that vanishes in N .