Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Demystifying Online Clustering of Bandits: Enhanced Exploration Under Stochastic and Smoothed Adversarial Contexts
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes UniCLUB/PhaseUniCLUB and set-based UniSCLUB that add uniform exploration to clustering of bandits to remove restrictive context-diversity assumptions, plus a smoothed adversarial context setting with SACLUB/SASCLUB.
Problem
Online clustering of bandits relies on UCB-based cluster inference, which lacks exploration and needs strong context-diversity assumptions (i.i.d. contexts, bounded variance) that are impractical and hurt performance.
Approach
Add an explicit uniform-exploration phase (or phase-based doubling exploration) to CLUB/SCLUB-style graph clustering so the design matrices become well-conditioned, removing the variance assumption; and introduce a smoothed adversarial context setting where adversarial arm means are perturbed by truncated Gaussian noise so explicit exploration is unnecessary.
Key results
- UniCLUB regret bound O~(ud/(gamma^2 lambda_x) + d sqrt(mT)) improves the clustering-cost term of prior CLUB-type analyses by O~(u/lambda_x^2) when gamma is known.
- PhaseUniCLUB removes the known-gap requirement with regret O~(ud/(gamma^5 lambda_x^2)+ (ud/lambda_x)^{2/3} T^{1/3} + d sqrt(mT)).
- Experiments on synthetic and three real-world datasets show UniCLUB consistently beats CLUB and UniSCLUB beats SCLUB in cumulative regret, though the margin is modest.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add uniform exploration to CLUB | CLUB · Stochastic contexts; synthetic, MovieLens-25M, Last.fm, and Yelp | cumulative regret | Helped |
| Add uniform exploration to SCLUB | SCLUB · Stochastic contexts; synthetic, MovieLens-25M, Last.fm, and Yelp | cumulative regret | Helped |
| Use user clustering instead of a single shared or separate per-user preference vector | LinUCB-One and LinUCB-Ind · Stochastic contexts; synthetic, MovieLens-25M, Last.fm, and Yelp | cumulative regret | Helped |
| Add uniform exploration and assume known cluster gap | CLUB · Stochastic contexts | regret incurred by clustering (bound): $\widetilde{O}\ab(u\ab(\frac{d}{\gamma^2\lambda_x} + \frac{1}{\lambda_x^2}))$ -> $\widetilde{O}\ab(\frac{ud}{\gamma^2\la | Helped |
Surprising findings
- Modest advantage of UniCLUB/UniSCLUB over CLUB/SCLUB in experiments despite the theoretical improvement.
Limitations
- Known cluster gap gamma is required for the best UniCLUB bound; PhaseUniCLUB has worse dependence on gamma and lambda_x.
- Smoothed adversarial setting still requires Gaussian perturbation; a fully adversarial setting is left open.
- Regret bounds retain 1/lambda_x dependence with lambda_x = O(1/d) under bounded contexts.
Experimental setup
Datasets: MovieLens-25M Last.fm Yelp
Benchmarks: MovieLens-25M Last.fm Yelp synthetic
Metrics: cumulative regret
Baselines: LinUCB-One LinUCB-Ind CLUB SCLUB GOB.Lin GraphUCB
Builds on: CLUB SCLUB LinUCB
Closest papers by meaning
- Online Clustering of Dueling Bandits (ICML 2025 · similarity 0.94)
- Clustering Items through Bandit Feedback: Finding the Right Feature out of Many (ICML 2025 · similarity 0.88)
- Efficient Contextual Bandits with Uninformed Feedback Graphs (ICML 2024 · similarity 0.88)
- Leveraging Offline Data in Linear Latent Contextual Bandits (ICML 2025 · similarity 0.88)
- Variance-aware Regret Bounds for Stochastic Contextual Dueling Bandits (ICLR 2024 · similarity 0.87)
- Diffusion Models Meet Contextual Bandits (NeurIPS 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.