Nonparametric Kernel Clustering with Bandit Feedback
Abstract
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 \emph{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.
Related
- The Sample Complexity of Multiple Change Point Identification under Bandit Feedback
- PAC Learning with Bandit Feedback: Sharp Sample Complexity in the Realizable Setting
- Near-Optimal Regret Bounds for Monotone Stochastic Optimization under Semi-Bandit Feedback
- Variable-Length Feedback Coding With Universal Decoding and Bandit Channel Selection
- Asymptotically Valid Laplace Variational Inference for Bayesian Nonparametric Clustering of Marked Point Patterns
BibTeX
@misc{thuot2026nonparametric,
title = {{Nonparametric Kernel Clustering with Bandit Feedback}},
author = {Victor Thuot and Sebastian Vogt and Debarghya Ghoshdastidar and Nicolas Verzelen},
howpublished = {HAL},
year = {2026},
month = oct,
url = {https://hal.science/hal-05451062v2},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Nonparametric Kernel Clustering with Bandit Feedback
AU - Victor Thuot
AU - Sebastian Vogt
AU - Debarghya Ghoshdastidar
AU - Nicolas Verzelen
PY - 2026
DA - 2026/10/12
PB - HAL
UR - https://hal.science/hal-05451062v2
AB - 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 \emph{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.
ER -