# A General Framework for Clustering and Distribution Matching with Bandit Feedback

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 37 references that are in the map.
- First posted on arXiv 8 Sep 2024.

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

- [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)
- [Non-Asymptotic Pure Exploration by Solving Games](https://mlsanity.com/paper/1906.10431/) (2019)
- [Optimal Best-Arm Identification Methods for Tail-Risk Measures](https://mlsanity.com/paper/2008.07606/) (2020)
- [Optimal Clustering with Bandit Feedback](https://mlsanity.com/paper/2202.04294/) (2022)
- [A Non-asymptotic Approach to Best-Arm Identification for Gaussian Bandits](https://mlsanity.com/paper/2105.12978/) (2021)
- [Active clustering with bandit feedback](https://mlsanity.com/paper/2406.11485/) (2024)
- [Adaptive Sampling for Coarse Ranking](https://mlsanity.com/paper/1802.07176/) (2018)
- [Optimal Clustering with Noisy Queries via Multi-Armed Bandit](https://mlsanity.com/paper/2207.05376/) (2022)
- [Representative Arm Identification: A fixed confidence approach to identify cluster representatives](https://mlsanity.com/paper/2408.14195/) (2024)
- [Large and Small Deviations for Statistical Sequence Matching](https://mlsanity.com/paper/2407.02816/) (2024)

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

- [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)

## Abstract (arXiv)

We develop a general framework for clustering and distribution matching problems with bandit feedback. We consider a K-armed bandit model where some subset of K arms is partitioned into M groups. Within each group, the random variable associated to each arm follows the same distribution on a finite alphabet. At each time step, the decision maker pulls an arm and observes its outcome from the random variable associated to that arm. Subsequent arm pulls depend on the history of arm pulls and their outcomes. The decision maker has no knowledge of the distributions of the arms or the underlying partitions. The task is to devise an online algorithm to learn the underlying partition of arms with the least number of arm pulls on average and with an error probability not exceeding a pre-determined value~δ. Several existing problems fall under our general framework, including finding M pairs of arms, odd arm identification, and N-ary clustering of K arms belong to our general framework. We derive a non-asymptotic lower bound on the average number of arm pulls for any online algorithm with an error probability not exceeding δ. Furthermore, we develop a computationally-efficient online algorithm based on the Track-and-Stop method and Frank--Wolfe algorithm, and show that the average number of arm pulls of our algorithm asymptotically matches that of the lower bound. Our refined analysis also uncovers a novel bound on the speed at which the average number of arm pulls of our algorithm converges to the fundamental limit as δ vanishes.