Design-Based Bandits Under Network Interference: Trade-Off Between Regret and Statistical Inference
Zichen Wang, Zhiheng Zhang, Haoyang Hong, Haoxuan Li, Chuanhao Li, Huazheng Wang
In multi-armed bandits with network interference (MAB-NI), the action taken by one node can influence the rewards of others, creating complex interdependence. While current research primarily focuses on minimizing regret in MAB-NI, it often neglects the critical issue that overly prioritizing the optimal arm can compromise the inference accuracy of the sub-optimal arm. Although initial efforts have been made to address this trade-off in single-unit scenarios, these challenges have become more pronounced in the context of MAB-NI. In this paper, we establish, for the first time, a theoretical Pareto frontier characterizing the trade-off between regret minimization and inference accuracy in adversarial (design-based) MAB-NI. We further introduce an anytime-valid asymptotic confidence sequence along with a corresponding algorithm, EXP3-N-CS, specifically designed to balance the trade-off between regret minimization and inference accuracy in this setting.