Improved Algorithm on Online Clustering of Bandits
This work addresses the online clustering of bandits problem for recommendation systems or personalization, but it appears incremental as it generalizes an existing setting with a refined algorithm.
The paper tackles the problem of online clustering of bandits with non-uniform user frequency distributions, proposing a more efficient algorithm using simple set structures. The result includes a regret bound independent of minimal user frequency and experimental advantages on synthetic and real datasets.
We generalize the setting of online clustering of bandits by allowing non-uniform distribution over user frequencies. A more efficient algorithm is proposed with simple set structures to represent clusters. We prove a regret bound for the new algorithm which is free of the minimal frequency over users. The experiments on both synthetic and real datasets consistently show the advantage of the new algorithm over existing methods.