Two advances for online clustering of bandits - a contextual multi-armed bandit setting that groups users with similar preferences into clusters to share statistical information and learn faster. First, keeping the i.i.d.-context assumption, the algorithms UniCLUB and PhaseUniCLUB add enhanced exploration so unknown user clusters are identified more quickly, achieving regret bounds comparable to prior UCB-based methods while requiring substantially weaker context-diversity assumptions - resolving a long-standing open problem. Second, using the smoothed-analysis framework, a more practical setting removes the i.i.d.-context requirement entirely and improves existing algorithms. Both techniques apply to graph-based and set-based clustering-of-bandits frameworks.
In the contextual multi-armed bandit problem a learner repeatedly serves users, choosing an arm (e.g. a recommendation) from each user's context and observing a reward, aiming to minimize regret. 'On…