Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Clustering Items through Bandit Feedback: Finding the Right Feature out of Many
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 BanditClustering, a fixed-confidence adaptive algorithm that clusters n items into two groups by sampling single item-feature entries, using sequential halving to find a discriminative feature, and proves matching instance-dependent upper and lower bounds in key regimes.
Problem
Clustering n items with d-dimensional feature vectors into two unknown groups using noisy bandit feedback where each step observes only one item-feature entry, with the goal of minimizing the sampling budget for exact recovery with probability 1-delta.
Approach
Two-step adaptive procedure: first find an item from the other group via a sequential-halving-based search over item-feature entries (CandidateRow), then find a highly discriminative feature with the same subroutine and classify all items using only that feature (ClusterByCandidates), so budget adapts to the sparsity and magnitude of the gap vector.
Key results
- BanditClustering's budget scales with d/(theta*||Delta||^2) plus a term min_s (d/s + n)(1/Delta_(s)^2+1), up to log factors, and beats uniform sampling plus KMeans in sparse regimes in simulations (n=20, d=1000).
- In the two-valued gap case, the upper bound matches the lower bound up to polylog factors in d, n, theta and log(1/delta).
- In Experiment 2 with d=10n, the required budget grows linearly in n, whereas uniform sampling would fail.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use adaptive BanditClustering instead of uniform sampling | Clustering items from bandit feedback · Experiment 1 (n=20, d=1000; sparse regimes) | observation budget | Helped |
| increase the sparsity of the gap vector | BanditClustering · Experiment 1 (n=20, d=1000; sparse regimes) | observation budget | Mixed |
| use adaptive BanditClustering instead of uniform sampling | Clustering items from bandit feedback · Experiment 2 (d=10n; fixed sparsity) | observation budget | Helped |
Surprising findings
- Uniform sampling clustering fails as n and d grow jointly with fixed sparsity, since some items are almost surely observed only on null features.
Limitations
- Only two groups (K=2) considered; extension to K>2 is left open.
- Assumes homogeneous groups with identical feature vectors within a group.
- Algorithm is conservative, requiring large delta in experiments to show differences; lower bound is tight only in some regimes (two-valued gap).
Experimental setup
Metrics: total sampling budget error rate of clustering
Baselines: KMeans with uniform sampling
Builds on: Sequential Halving Bracketing Sequential Halving adaptive sensing for signal detection
Closest papers by meaning
- Optimal Clustering with Bandit Feedback (NeurIPS 2024 · similarity 0.90)
- Demystifying Online Clustering of Bandits: Enhanced Exploration Under Stochastic and Smoothed Adversarial Contexts (ICLR 2025 · similarity 0.88)
- From Contextual Combinatorial Semi-Bandits to Bandit List Classification: Improved Sample Complexity with Sparse Rewards (NeurIPS 2025 · similarity 0.88)
- Query-Efficient Correlation Clustering with Noisy Oracle (NeurIPS 2024 · similarity 0.87)
- Online Clustering of Dueling Bandits (ICML 2025 · similarity 0.87)
- New Classes of the Greedy-Applicable Arm Feature Distributions in the Sparse Linear Bandit Problem (AAAI 2024 · similarity 0.86)
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.