Heterogeneous Multi-Agent Contextual Bandits under Bounded Misspecification

Misspecification is known to degrade the performance of contextual bandit algorithms, yet its impact has received little attention in the multi-agent setting. Motivated by this gap, we formulate the setting of arm-heterogeneous multi-agent linear contextual bandits under misspecification—a practically motivated model where each agent has access to only a subset of the global arm catalog. To minimize the joint regret of all agents without prior knowledge of the misspecification level, we propose HM-UCB, a collaborative algorithm that updates its parameter estimates via size-weighted pooling of agent observations. We first establish a high-probability regret upper bound of $\tilde{O}(R\sqrt{dNT\log (KN)}+\epsilon \sqrt{d}NT)$ for HM-UCB. Next, by using geometric packing and information-theoretic techniques, we derive a generic regret lower bound in our model, which along with the upper bound of HM-UCB, establishing the near-optimality of HM-UCB in some practical regimes. To demonstrate the scalability of our framework, we instantiate HM-UCB under two practical protocols—Naive and N-Selection. For each, we design customized algorithms and establish corresponding theoretical guarantees. Empirical evaluations corroborate our theoretical findings, underscoring the strong practical performance of HM-UCB and substantiating the tightness of our regret bounds.