# Online Clustering of Data Sequences with Bandit Information

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 51 references that are in the map.
- First posted on arXiv 20 Jan 2025.

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

- [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)
- [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)
- [An optimal algorithm for the Thresholding Bandit Problem](https://mlsanity.com/paper/1605.08671/) (2016)
- [Minimax Optimal Fixed-Budget Best Arm Identification in Linear Bandits](https://mlsanity.com/paper/2105.13017/) (2021)
- [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)
- [Sequential Change Detection for Learning in Piecewise Stationary Bandit Environments](https://mlsanity.com/paper/2501.10974/) (2025)
- [Consensus-ADMM for General Quadratically Constrained Quadratic Programming](https://mlsanity.com/paper/1601.02335/) (2016)
- [K-medoids Clustering of Data Sequences with Composite Distributions](https://mlsanity.com/paper/1807.11620/) (2018)
- [Exponentially Consistent Nonparametric Linkage-Based Clustering of Data Sequences](https://mlsanity.com/paper/2411.13922/) (2024)
- [Exponentially Consistent Outlier Hypothesis Testing for Continuous Sequences](https://mlsanity.com/paper/2405.01161/) (2024)

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

- [Nonparametric Kernel Clustering with Bandit Feedback](https://mlsanity.com/paper/2601.07535/) (2026)

## Abstract (arXiv)

We study the problem of online clustering of data sequences in the multi-armed bandit (MAB) framework under the fixed-confidence setting. There are M arms, each providing i.i.d. samples from a parametric distribution whose parameters are unknown. The M arms form K clusters based on the distance between the true parameters. In the MAB setting, one arm can be sampled at each time. The objective is to estimate the clusters of the arms using as few samples as possible from the arms, subject to an upper bound on the error probability. Our setting allows for: arms within a cluster to have non-identical distributions, vector parameter arms, vector observations, and K ≤ M clusters. We propose and analyze the Average Tracking Bandit Online Clustering (ATBOC) algorithm. ATBOC is asymptotically order-optimal for multivariate Gaussian arms, with expected sample complexity grows at most twice as fast as the lower bound as δ rightarrow 0, and this guarantee extends to multivariate sub-Gaussian arms. For single-parameter exponential family arms, ATBOC is asymptotically optimal, matching the lower bound. We also propose a computationally more efficient alternatives Lower and Upper Confidence Bound based Bandit Online Clustering Algorithm (LUCBBOC), and Bandit Online Clustering-Elimination (BOC-ELIM). We derive the computational complexity of the proposed algorithms and compare their per-sample runtime through simulations. LUCBBOC and BOC-ELIM require lower per-sample runtime than ATBOC while achieving comparable performance. All the proposed algorithms are δ-Probably correct, i.e., the error probability of cluster estimate at the stopping time is atmost δ. We validate the asymptotic optimality guarantees through simulations, and present the comparison of our proposed algorithms with other related work through simulations on both synthetic and real-world datasets.