On the optimal regret of collaborative personalized linear bandits

Stochastic linear bandits are a fundamental model for sequential decision making, where an agent selects a vector-valued action and receives a noisy reward with expected value given by an unknown linear function. Although well studied in the single-agent setting, many real-world scenarios involve multiple agents solving heterogeneous bandit problems, each with a different unknown parameter. Applying single agent algorithms independently ignores cross-agent similarity and learning opportunities. This paper investigates the optimal regret achievable in collaborative personalized linear bandits. We provide an information-theoretic lower bound that characterizes how the number of agents, the interaction rounds, and the degree of heterogeneity jointly affect regret. We then propose a new two-stage collaborative algorithm that achieves the optimal regret. Our analysis models heterogeneity via a hierarchical Bayesian framework and introduces a novel information-theoretic technique for bounding regret. Our results offer a complete characterization of when and how collaboration helps with a optimal regret bound tildeO(d√mn), tildeO(dm1-γ√n), tildeO(dm√n) for the number of rounds n in the range of (0, fracdm σ2), [fracdm2γ σ2, fracdσ2] and (fracdσ2, ∞) respectively, where σ measures the level of heterogeneity, m is the number of agents, and γ∈[0, 1/2] is an absolute constant. In contrast, agents without collaboration achieve a regret bound O(dm√n) at best.