Research map / Bandits and online learning / Online convex optimization and games
Optimal Clustering with Bandit Feedback
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.
Derives an instance-dependent lower bound for online clustering with bandit feedback and proposes BOC, a computationally efficient algorithm (D-tracking sampling, K-means-Maximin, new stopping statistic) that is asymptotically optimal as delta→0.
Problem
Online clustering of arms with bandit (noisy Gaussian) feedback: uncover the unknown partition of arms into clusters with minimal expected arm pulls at fixed error probability delta, without solving NP-hard weighted K-means exactly.
Approach
Reduces the hardness-parameter optimization to a finite convex minimax problem via a Hamming-distance-1 lemma, and uses a new stopping statistic Z(t) built on K-means-Maximin estimates instead of the intractable GLR, yielding asymptotic optimality with a D-Tracking sampling rule.
Key results
- On Iris (delta=1e-1 to 1e-10), BOC needs about 886 to 1120 pulls vs 1176 to 1447 for Uniform.
- On Yeast, BOC needs about 14430 to 14977 pulls vs 19536 to 20767 for Uniform across the same delta range.
- On synthetic instances, BOC's curve slope matches the lower bound D* as log(1/delta) grows, while Uniform's slope is larger.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use adaptive BOC sampling instead of round-robin Uniform sampling | Online clustering · Iris dataset, δ=10^-1 to 10^-10 | sample complexity: 886.1 ± 55.9 vs 1176.4 ± 69.2 (δ=10^-1); 1120.2 ± 48.2 vs 1447.0 ± 73.3 (δ=10^-10) | Helped |
| use adaptive BOC sampling instead of round-robin Uniform sampling | Online clustering · Yeast dataset, δ=10^-1 to 10^-10 | sample complexity: 14430.5 ± 371.3 vs 19536.0 ± 530.4 (δ=10^-1); 14977.1 ± 445.0 vs 20766.8 ± 107.1 (δ=10^-10) | Helped |
| replace the theoretical threshold β(δ,t) with heuristic threshold β̃(δ,t) | BOC · Synthetic dataset | sample complexity | Helped |
| approximate the oracle sampling rule online with BOC rather than use the oracle rule | Online clustering · Synthetic dataset | sample complexity | No clear effect |
| use BOC sampling instead of Uniform sampling | Online clustering · Synthetic dataset | sample complexity | Helped |
Surprising findings
- The natural GLR stopping rule is computationally intractable, and a Hamming-distance-1 reduction that works for true means fails for empirical estimates (counterexample given).
Limitations
- Asymptotic optimality holds only as delta tends to zero; gap to lower bound at moderate delta.
- Heuristic threshold used in experiments lacks theoretical guarantees.
- Restricted to Gaussian noise with identity covariance and distinct cluster centers.
Experimental setup
Datasets: Iris Yeast MNIST synthetic Gaussian instances
Benchmarks: Iris Yeast MNIST synthetic instances
Metrics: expected sample complexity standard deviation over 256 trials slope vs lower bound
Baselines: Uniform Oracle
Builds on: D-Tracking GLR stopping rule K-means++ odd arm identification
Closest papers by meaning
- Clustering Items through Bandit Feedback: Finding the Right Feature out of Many (ICML 2025 · similarity 0.90)
- Online Clustering of Bandits with Misspecified User Models (NeurIPS 2023 · similarity 0.86)
- Demystifying Online Clustering of Bandits: Enhanced Exploration Under Stochastic and Smoothed Adversarial Contexts (ICLR 2025 · similarity 0.85)
- Query-Efficient Correlation Clustering with Noisy Oracle (NeurIPS 2024 · similarity 0.84)
- Online Clustering of Dueling Bandits (ICML 2025 · similarity 0.83)
- From Contextual Combinatorial Semi-Bandits to Bandit List Classification: Improved Sample Complexity with Sparse Rewards (NeurIPS 2025 · similarity 0.82)
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.