# Optimal Clustering with Bandit Feedback

arXiv: https://arxiv.org/abs/2202.04294 · HTML: https://mlsanity.com/paper/2202.04294/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 67 references that are in the map.
- First posted on arXiv 9 Feb 2022.

## Builds on (most cited first, 17 of 17)

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [Online Clustering of Bandits](https://mlsanity.com/paper/1401.8257/) (2014)
- [Best-Arm Identification in Linear Bandits](https://mlsanity.com/paper/1409.6110/) (2014)
- [Mixture Martingales Revisited with Applications to Sequential Tests and Confidence Intervals](https://mlsanity.com/paper/1811.11419/) (2018)
- [Optimal Best-arm Identification in Linear Bandits](https://mlsanity.com/paper/2006.16073/) (2020)
- [The End of Optimism? An Asymptotic Analysis of Finite-Armed Linear Bandits](https://mlsanity.com/paper/1610.04491/) (2016)
- [Optimal Exploitation of Clustering and History Information in Multi-Armed Bandit](https://mlsanity.com/paper/1906.03979/) (2019)
- [Online k-means Clustering](https://mlsanity.com/paper/1909.06861/) (2019)
- [An Algorithm for Online K-Means Clustering](https://mlsanity.com/paper/1412.5721/) (2014)
- [Multi-Armed Bandits with Dependent Arms](https://mlsanity.com/paper/2010.09478/) (2020)
- [Dealing With Misspecification In Fixed-Confidence Linear Top-m Identification](https://mlsanity.com/paper/2111.01479/) (2021)
- [Max-Min Grouped Bandits](https://mlsanity.com/paper/2111.08862/) (2021)
- [Thompson Sampling for Bandits with Clustered Arms](https://mlsanity.com/paper/2109.01656/) (2021)
- [Best Arm Identification for Cascading Bandits in the Fixed Confidence Setting](https://mlsanity.com/paper/2001.08655/) (2020)
- [Detecting an Odd Restless Markov Arm with a Trembling Hand](https://mlsanity.com/paper/2005.06255/) (2020)

## Built on by (most cited first, 15 of 15)

- [Federated Best Arm Identification with Heterogeneous Clients](https://mlsanity.com/paper/2210.07780/) (2022)
- [Active clustering with bandit feedback](https://mlsanity.com/paper/2406.11485/) (2024)
- [A General Framework for Clustering and Distribution Matching with Bandit Feedback](https://mlsanity.com/paper/2409.05072/) (2024)
- [Graph Feedback Bandits on Similar Arms: With and Without Graph Structures](https://mlsanity.com/paper/2501.14314/) (2025)
- [Graph Feedback Bandits with Similar Arms](https://mlsanity.com/paper/2405.11171/) (2024)
- [Exponentially Consistent Nonparametric Linkage-Based Clustering of Data Sequences](https://mlsanity.com/paper/2411.13922/) (2024)
- [Clustering Items through Bandit Feedback: Finding the Right Feature out of Many](https://mlsanity.com/paper/2503.11209/) (2025)
- [Online Clustering of Data Sequences with Bandit Information](https://mlsanity.com/paper/2501.11421/) (2025)
- [Fixed-Confidence Multiple Change Point Identification under Bandit Feedback](https://mlsanity.com/paper/2507.08994/) (2025)
- [Near Optimal Best Arm Identification for Clustered Bandits](https://mlsanity.com/paper/2505.10147/) (2025)
- [A Distribution Testing Approach to Clustering Distributions](https://mlsanity.com/paper/2512.08376/) (2025)
- [Nonparametric Kernel Clustering with Bandit Feedback](https://mlsanity.com/paper/2601.07535/) (2026)
- [Efficient Clustering in Stochastic Bandits](https://mlsanity.com/paper/2601.09162/) (2026)
- [Fast Online Learning with Gaussian Prior-Driven Hierarchical Unimodal Thompson Sampling](https://mlsanity.com/paper/2602.15972/) (2026)
- [The Sample Complexity of Multiple Change Point Identification under Bandit Feedback](https://mlsanity.com/paper/2605.13252/) (2026)

## Abstract (arXiv)

This paper considers the problem of online clustering with bandit feedback. A set of arms (or items) can be partitioned into various groups that are unknown. Within each group, the observations associated to each of the arms follow the same distribution with the same mean vector. At each time step, the agent queries or pulls an arm and obtains an independent observation from the distribution it is associated to. Subsequent pulls depend on previous ones as well as the previously obtained samples. The agent's task is to uncover the underlying partition of the arms with the least number of arm pulls and with a probability of error not exceeding a prescribed constant δ. The problem proposed finds numerous applications from clustering of variants of viruses to online market segmentation. We present an instance-dependent information-theoretic lower bound on the expected sample complexity for this task, and design a computationally efficient and asymptotically optimal algorithm, namely Bandit Online Clustering (BOC). The algorithm includes a novel stopping rule for adaptive sequential testing that circumvents the need to exactly solve any NP-hard weighted clustering problem as its subroutines. We show through extensive simulations on synthetic and real-world datasets that BOC's performance matches the lower bound asymptotically, and significantly outperforms a non-adaptive baseline algorithm.