On the Optimal Regret of Collaborative Personalized Linear Bandits

摘要

Stochastic linear bandits are a fundamental model for sequential decision making. 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. This paper investigates the optimal regret achievable in collaborative personalized linear bandits. We derive an information-theoretic lower bound showing how the number of agents, the number of rounds, and the degree of heterogeneity jointly affect regret. We propose a two-stage collaborative algorithm that achieves the optimal regret. We model 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 Õ(d√(mn)), Õ(dm^1-γ√(n)), Õ(dm√(n)) for the number of rounds n in the range of o ( d/m σ^2), Θ( d/m^2γσ^2) and ω( d/σ^2, ) respectively, where σ measures the level of heterogeneity, m is the number of agents, and γ∈[0, 1/2] is an absolute constant. In contrast, without collaboration achieves a regret bound O(dm√(n)) at best.