Online Clustering of Bandits without Feature Diversity

Online clustering of bandits shares information across heterogeneous users by pooling observations within groups of users whose similarity is inferred from observed rewards. Existing methods typically group users when their preference vectors have the same values in all coordinates. To accumulate enough information to infer such groups, these methods rely on either distributional assumptions on feature generation or access to an action set spanning the entire $d$-dimensional feature space; neither requirement is guaranteed to hold in practice. To dispense with such requirements, we group users when their expected rewards are the same for every available action, even if their preference vectors are different. We propose `TRIBE`, which explores a basis of the space spanned by the available actions, groups users through a novel and computationally efficient statistical test, and selects actions using the observations pooled within each inferred group. Over $T$ rounds, our algorithm achieves a regret bound with the leading term $\tilde{\mathcal{O}}(d\sqrt{CT})$, where $C$ is the number of clusters, matching the rate attainable when the cluster structure is known a priori. Numerical experiments on synthetic and real-world datasets support our theoretical findings and confirm that `TRIBE` outperforms the baselines.