Design-Based Bandits Under Network Interference: Trade-Off Between Regret and Statistical Inference

Haoxuan Li (Peking University) · Chuanhao Li (Shanghai AI Laboratory) · Zichen Wang (University of Illinois at Urbana-Champaign) · Haoyang Hong (Oregon State University) · Zhiheng Zhang (Shanghai University of Finance and Economics) · Huazheng Wang (lut)

adversarial mabnianytime-validasymptotic confidence sequencecomplex interdependencedesign-based mabniexp3-n-csinference accuracymulti-armed banditsnetwork interferencepareto frontier regret minimizationsub-optimal armstheoretical characterization trade-off

In multi-armed bandits with network interference (MABNI), the action taken by one node can influence the rewards of others, creating complex interdependence. While existing research on MABNI largely concentrates on minimizing regret, it often overlooks the crucial concern that an excessive emphasis on the optimal arm can undermine the inference accuracy for sub-optimal arms. 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 MABNI. 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) MABNI. We further introduce an anytime-valid asymptotic confidence sequence along with a corresponding algorithm, $\texttt{EXP3-N-CS}$, specifically designed to balance the trade-off between regret minimization and inference accuracy in this setting.