Parallel Online Clustering of Bandits via Hedonic Game

Xiaotong Cheng, Cheng Pan, Setareh Maghsudi
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:5485-5503, 2023.

Abstract

Contextual bandit algorithms appear in several applications, such as online advertisement and recommendation systems like personalized education or personalized medicine. Individually-tailored recommendations boost the performance of the underlying application; nevertheless, providing individual suggestions becomes costly and even implausible as the number of users grows. As such, to efficiently serve the demands of several users in modern applications, it is imperative to identify the underlying users’ clusters, i.e., the groups of users for which a single recommendation might be (near-)optimal. We propose CLUB-HG, a novel algorithm that integrates a game-theoretic approach into clustering inference. Our algorithm achieves Nash equilibrium at each inference step and discovers the underlying clusters. We also provide regret analysis within a standard linear stochastic noise setting. Finally, experiments on synthetic and real-world datasets show the superior performance of our proposed algorithm compared to the state-of-the-art algorithms.

Cite this Paper

BibTeX
@InProceedings{pmlr-v202-cheng23d, title = {Parallel Online Clustering of Bandits via Hedonic Game}, author = {Cheng, Xiaotong and Pan, Cheng and Maghsudi, Setareh}, booktitle = {Proceedings of the 40th International Conference on Machine Learning}, pages = {5485--5503}, year = {2023}, editor = {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan}, volume = {202}, series = {Proceedings of Machine Learning Research}, month = {23--29 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v202/cheng23d/cheng23d.pdf}, url = {https://proceedings.mlr.press/v202/cheng23d.html}, abstract = {Contextual bandit algorithms appear in several applications, such as online advertisement and recommendation systems like personalized education or personalized medicine. Individually-tailored recommendations boost the performance of the underlying application; nevertheless, providing individual suggestions becomes costly and even implausible as the number of users grows. As such, to efficiently serve the demands of several users in modern applications, it is imperative to identify the underlying users’ clusters, i.e., the groups of users for which a single recommendation might be (near-)optimal. We propose CLUB-HG, a novel algorithm that integrates a game-theoretic approach into clustering inference. Our algorithm achieves Nash equilibrium at each inference step and discovers the underlying clusters. We also provide regret analysis within a standard linear stochastic noise setting. Finally, experiments on synthetic and real-world datasets show the superior performance of our proposed algorithm compared to the state-of-the-art algorithms.} }
Endnote
%0 Conference Paper %T Parallel Online Clustering of Bandits via Hedonic Game %A Xiaotong Cheng %A Cheng Pan %A Setareh Maghsudi %B Proceedings of the 40th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2023 %E Andreas Krause %E Emma Brunskill %E Kyunghyun Cho %E Barbara Engelhardt %E Sivan Sabato %E Jonathan Scarlett %F pmlr-v202-cheng23d %I PMLR %P 5485--5503 %U https://proceedings.mlr.press/v202/cheng23d.html %V 202 %X Contextual bandit algorithms appear in several applications, such as online advertisement and recommendation systems like personalized education or personalized medicine. Individually-tailored recommendations boost the performance of the underlying application; nevertheless, providing individual suggestions becomes costly and even implausible as the number of users grows. As such, to efficiently serve the demands of several users in modern applications, it is imperative to identify the underlying users’ clusters, i.e., the groups of users for which a single recommendation might be (near-)optimal. We propose CLUB-HG, a novel algorithm that integrates a game-theoretic approach into clustering inference. Our algorithm achieves Nash equilibrium at each inference step and discovers the underlying clusters. We also provide regret analysis within a standard linear stochastic noise setting. Finally, experiments on synthetic and real-world datasets show the superior performance of our proposed algorithm compared to the state-of-the-art algorithms.
APA
Cheng, X., Pan, C. & Maghsudi, S.. (2023). Parallel Online Clustering of Bandits via Hedonic Game. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:5485-5503 Available from https://proceedings.mlr.press/v202/cheng23d.html.

Related Material