Beyond Global Clusters: Objective-Specific User Clustering for Multi-Objective Bandits

Clustering of bandits is a common approach to improving the sample efficiency of contextual bandits in recommendation: it adaptively groups users with similar preferences and pools their interaction data. Existing methods, however, group users under a single similarity structure for the whole reward, which fails in multi-objective recommendation, where users who agree on one objective may disagree on another. To fill in this gap, we propose Clustering of Multi-Objective Bandits (CMOB), a framework that maintains one user graph per objective and pools data only within objective-specific clusters, so that two users can share data for one objective while being separated for another. We instantiate the framework as COMOLB for linear rewards; since rewards are often not linear in the context, we further propose COMONB, which applies the same scheme to the gradient features of a neural network. Both algorithms separate two users for an objective only when a confidence test certifies that their preferences differ. Our proposed algorithms are proved to never separate users of the same cluster with high probability, to recover the objective-specific partitions after an identification time that depends on the horizon only logarithmically, and to attain a Pareto regret whose dominant term scales with the number of objective-specific clusters instead of the number of users. Experiments on synthetic instances show that our algorithms outperform existing clustering methods, and on semi-synthetic MovieLens data with objective-specific user clusters, our method nearly halves the regret of learning each user independently.