# Efficient Clustering in Stochastic Bandits

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 27 references that are in the map.
- First posted on arXiv 14 Jan 2026.

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

- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Optimal Best-arm Identification in Linear Bandits](https://mlsanity.com/paper/2006.16073/) (2020)
- [Gradient Ascent for Active Exploration in Bandit Problems](https://mlsanity.com/paper/1905.08165/) (2019)
- [Optimal Clustering with Bandit Feedback](https://mlsanity.com/paper/2202.04294/) (2022)
- [An Algorithm for Online K-Means Clustering](https://mlsanity.com/paper/1412.5721/) (2014)
- [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)
- [MaxGap Bandit: Adaptive Algorithms for Approximate Ranking](https://mlsanity.com/paper/1906.00547/) (2019)
- [Sequential Controlled Sensing for Composite Multihypothesis Testing](https://mlsanity.com/paper/1910.12697/) (2019)
- [K-medoids Clustering of Data Sequences with Composite Distributions](https://mlsanity.com/paper/1807.11620/) (2018)
- [Best Arm Identification in Stochastic Bandits: Beyond β-optimality](https://mlsanity.com/paper/2301.03785/) (2023)
- [Exponentially Consistent Nonparametric Linkage-Based Clustering of Data Sequences](https://mlsanity.com/paper/2411.13922/) (2024)

## Abstract (arXiv)

We study the Bandit Clustering (BC) problem under the fixed confidence setting, where the objective is to group a collection of data sequences (arms) into clusters through sequential sampling from adaptively selected arms at each time step while ensuring a fixed error probability at the stopping time. We consider a setting where arms in a cluster may have different distributions. Unlike existing results in this setting, which assume Gaussian-distributed arms, we study a broader class of vector-parametric distributions that satisfy mild regularity conditions. Existing asymptotically optimal BC algorithms require solving an optimization problem as part of their sampling rule at each step, which is computationally costly. We propose an Efficient Bandit Clustering algorithm (EBC), which, instead of solving the full optimization problem, takes a single step toward the optimal value at each time step, making it computationally efficient while remaining asymptotically optimal. We also propose a heuristic variant of EBC, called EBC-H, which further simplifies the sampling rule, with arm selection based on quantities computed as part of the stopping rule. We highlight the computational efficiency of EBC and EBC-H by comparing their per-sample run time with that of existing algorithms. The asymptotic optimality of EBC is supported through simulations on the synthetic datasets. Through simulations on both synthetic and real-world datasets, we show the performance gain of EBC and EBC-H over existing approaches.