On the optimal regret of collaborative personalized linear bandits

Bruce Huang, Ruida Zhou, Lin F. Yang, Suhas Diggavi
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:2440-2448, 2026.

Abstract

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 $\tilde{O}(d\sqrt{mn})$, $\tilde{O}(dm^{1-\gamma}\sqrt{n})$, $\tilde{O}(dm\sqrt{n})$ for the number of rounds $n$ in the range of $o \left( \frac{d}{m \sigma^2} \right)$, $\Theta \left( \frac{d}{m^{2\gamma} \sigma^2} \right)$ and $\omega \left( \frac{d}{\sigma^2}, \right)$ respectively, where $\sigma$ measures the level of heterogeneity, $m$ is the number of agents, and $\gamma\in[0, 1/2]$ is an absolute constant. In contrast, without collaboration achieves a regret bound $O(dm\sqrt{n})$ at best.

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-huang26a, title = { On the optimal regret of collaborative personalized linear bandits }, author = {Huang, Bruce and Zhou, Ruida and Yang, Lin F. and Diggavi, Suhas}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {2440--2448}, year = {2026}, editor = {Khan, Emtiyaz and Li, Yingzhen and Solin, Arno and Ramdas, Aaditya}, volume = {300}, series = {Proceedings of Machine Learning Research}, month = {02--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v300/main/assets/huang26a/huang26a.pdf}, url = {https://proceedings.mlr.press/v300/huang26a.html}, abstract = { 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 $\tilde{O}(d\sqrt{mn})$, $\tilde{O}(dm^{1-\gamma}\sqrt{n})$, $\tilde{O}(dm\sqrt{n})$ for the number of rounds $n$ in the range of $o \left( \frac{d}{m \sigma^2} \right)$, $\Theta \left( \frac{d}{m^{2\gamma} \sigma^2} \right)$ and $\omega \left( \frac{d}{\sigma^2}, \right)$ respectively, where $\sigma$ measures the level of heterogeneity, $m$ is the number of agents, and $\gamma\in[0, 1/2]$ is an absolute constant. In contrast, without collaboration achieves a regret bound $O(dm\sqrt{n})$ at best. } }
Endnote
%0 Conference Paper %T On the optimal regret of collaborative personalized linear bandits %A Bruce Huang %A Ruida Zhou %A Lin F. Yang %A Suhas Diggavi %B Proceedings of The 29th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2026 %E Emtiyaz Khan %E Yingzhen Li %E Arno Solin %E Aaditya Ramdas %F pmlr-v300-huang26a %I PMLR %P 2440--2448 %U https://proceedings.mlr.press/v300/huang26a.html %V 300 %X 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 $\tilde{O}(d\sqrt{mn})$, $\tilde{O}(dm^{1-\gamma}\sqrt{n})$, $\tilde{O}(dm\sqrt{n})$ for the number of rounds $n$ in the range of $o \left( \frac{d}{m \sigma^2} \right)$, $\Theta \left( \frac{d}{m^{2\gamma} \sigma^2} \right)$ and $\omega \left( \frac{d}{\sigma^2}, \right)$ respectively, where $\sigma$ measures the level of heterogeneity, $m$ is the number of agents, and $\gamma\in[0, 1/2]$ is an absolute constant. In contrast, without collaboration achieves a regret bound $O(dm\sqrt{n})$ at best.
APA
Huang, B., Zhou, R., Yang, L.F. & Diggavi, S.. (2026). On the optimal regret of collaborative personalized linear bandits . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:2440-2448 Available from https://proceedings.mlr.press/v300/huang26a.html.

Related Material