# Nonparametric Kernel Clustering with Bandit Feedback

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

## Key facts

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

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

- [Kernel Mean Embedding of Distributions: A Review and Beyond](https://mlsanity.com/paper/1605.09522/) (2016)
- [Optimal Clustering with Bandit Feedback](https://mlsanity.com/paper/2202.04294/) (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)
- [Recovery Guarantees for Kernel-based Clustering under Non-parametric Mixture Models](https://mlsanity.com/paper/2110.09476/) (2021)
- [Variance-Aware Estimation of Kernel Mean Embedding](https://mlsanity.com/paper/2210.06672/) (2022)
- [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)
- [Kernel K-means clustering of distributional data](https://mlsanity.com/paper/2509.18037/) (2025)

## Abstract (arXiv)

Clustering with bandit feedback refers to the problem of partitioning the arms of an N-armed stochastic bandit according to their underlying distributions, based on noisy observations collected sequentially and adaptively. This setting has attracted growing interest for its applicability in recommendation systems, crowdsourcing, and adaptive trials. Existing works rely on the strong assumption that arm distributions are sub-Gaussian, which can only distinguish arms whose distributions differ in mean - missing realistic settings where distributional differences lie in shape or higher moments. % We introduce a framework of nonparametric clustering with bandit feedback, free of any parametric assumptions regarding the arm distributions. We adopt a kernel-based approach and reformulate the problem as clustering arms according to their kernel mean embeddings in a reproducing kernel Hilbert space (RKHS). Building on this formulation, we introduce the kabc algorithm, prove that it is δ-PAC, and derive a non-asymptotic high-probability upper bound on its sampling complexity. The bound is governed by a variance-aware signal-to-noise ratio defined as the minimum over pairs of arms in distinct clusters of the ratio between their squared MMD and their RKHS variance. kabc achieves instance-dependent guarantees while being adaptive to this unknown ratio. We validate our approach empirically on synthetic and real-world datasets, demonstrating that kabc succeeds in distributional clustering settings where mean-based methods fail.