aiqbench analysis
This paper introduces \kabc, a nonparametric algorithm for clustering bandit arms using kernel mean embeddings to capture distributional differences beyond simple means. By operating in a reproducing kernel Hilbert space, the method provides rigorous theoretical guarantees and adapts to unknown variance ratios where traditional sub-Gaussian assumptions fail. The approach advances sequential decision-making frameworks by enabling robust partitioning of stochastic processes in realistic settings involving shape or higher-moment variations.
Nonparametric Kernel Clustering with Bandit Feedback
arXiv:2601.07535v2 Announce Type: replace-cross 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 $\delta$-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.
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 $\delta$-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.
Machine Learning (stat.ML); Machine Learning (cs.LG)
arXiv:2601.07535 [stat.ML]
(or arXiv:2601.07535v2 [stat.ML] for this version)
https://doi.org/10.48550/arXiv.2601.07535 Focus to learn more arXiv-issued DOI via DataCite
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 310 words
Related coverage
A General $\widetilde{\Omega}(\sqrt{T \gamma_T})$ Lower Bound for Kernel Bandits
arXiv · Oct 9, 2026
Scaling MoE reinforcement learning on Amazon EKS with EFA and DeepEP with 40% more throughput
AWS · Sep 25, 2026
On the Complexity of Preference-Based Bandits
arXiv · Oct 1, 2026
An Educational GEMM Ladder for Helios GPUs
AMD · Sep 14, 2026