# Nonparametric Kernel Clustering with Bandit Feedback

Victor Thuot, Sebastian Vogt, Debarghya Ghoshdastidar, Nicolas Verzelen

► To cite this version:

Victor Thuot, Sebastian Vogt, Debarghya Ghoshdastidar, Nicolas Verzelen. Nonparametric Kernel Clustering with Bandit Feedback. 2026. hal-05451062

HAL Id: hal-05451062

https://hal.science/hal-05451062v1

Preprint submitted on 9 Jan 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
Nonparametric Kernel Clustering with Bandit Feedback

Victor Thuot *¹ Sebastian Vogt *² Debarghya Ghoshdastidar² Nicolas Verzelen¹

Abstract

Clustering with bandit feedback refers to the problem of partitioning a set of items, where the clustering algorithm can sequentially query the items to receive noisy observations. The problem is formally posed as the task of partitioning the arms of an *N*-armed stochastic bandit according to their underlying distributions, grouping two arms together if and only if they share the same distribution, using samples collected sequentially and adaptively. This setting has gained attention in recent years due to its applicability in recommendation systems and crowdsourcing. Existing works on clustering with bandit feedback rely on a strong assumption that the underlying distributions are sub-Gaussian. As a consequence, the existing methods mainly cover settings with linearly-separable clusters, which has little practical relevance.

We introduce a framework of “nonparametric clustering with bandit feedback”, where the underlying arm distributions are not constrained to any parametric, and hence, it is applicable for active clustering of real-world datasets. We adopt a kernel-based approach, which allows us to reformulate the nonparametric problem as the task of clustering the arms according to their kernel mean embeddings in a reproducing kernel Hilbert space (RKHS). Building on this formulation, we introduce the KABC algorithm with theoretical correctness guarantees and analyze its sampling budget. We introduce a notion of signal-to-noise ratio for this problem that depends on the maximum mean discrepancy (MMD) between the arm distributions and on their variance in the RKHS. Our algorithm is adaptive to this unknown quantity: it does not require it as an input yet achieves instance-dependent guarantees.

# 1. Introduction

We consider a non-parametric instance of the so-called clustering with bandit feedback problem introduced in (Yang et al., 2024) and (Thuot et al., 2024). In this pure exploration problem, the goal is to partition a set of unknown distributions, from which we can collect samples, and to provide guarantees on the partition returned by the learner. This problem captures various contemporary settings where data are collected sequentially and in an adaptive manner. In digital marketing, online platforms repeatedly interact with users and must quickly discover specific groups of customers (market segment)s so as to personalize recommendations while limiting costly feedback collection. Beyond customer segmentation, our non-parametric, kernel-based formulation is well suited to modern high-dimensional or complex data for which parametric assumptions are often untenable, for example when clustering noisy biological or medical signals in adaptive trials. See (Yang et al., 2024) for further applications, e.g., in medical trials.

**Clustering with bandit feedback.** We adopt the stochastic multi-armed bandit model (see, e.g., Bubeck et al., 2012; Lattimore & Szepesvári, 2020), in which a learner interacts sequentially with an unknown environment with $N \in \mathbb{N}$ arms.

Each arm $i$ is associated with an unknown distribution $\nu_i$ supported on a space $\mathcal{X}$. At each time step, the algorithm chooses an arm and observes a data sampled from its associated distribution. The algorithm interacts with the environment until a (random) stopping time $\tau$– which it chooses. We consider the active clustering problem as in (Yang et al., 2024; Thuot et al., 2024), we assume that there exists an underlying partition of the arms into $K$ groups such that two arms are in the same group if and only if they are associated with the same distribution. The learner’s objective is to exactly recover

<footnote>*Equal contribution¹INRAE, Mistea, Institut Agro, Univ Montpellier, Montpellier, France ²Technical University of Munich, Munich, Germany. Correspondence to: Victor Thuot <victor.thuot@inrae.fr>.</footnote>
this partition with probability of error at most a prescribed $\delta$, in which case the algorithm is said to be $\delta$-PAC. Since data collection is costly, the goal is to design $\delta$-PAC algorithms, that make as few observations as possible.

**Non-parametric formulation.** In Yang et al. (2024) and Thuot et al. (2024), the authors restrict the possible arm distributions to sub-Gaussian distributions and cluster the arms according to their means in the original $d$-dimensional space $\mathbb{R}^d$. Our work aims to develop algorithms in the setting where no strong assumptions are imposed on the arm distributions, turning the problem into a *non-parametric* one.

Rather than working directly in the original space $\mathcal{X}$, we map distributions into a reproducing kernel Hilbert space (RKHS) $\mathcal{H}$ and represent each arm $i$ through its kernel mean embedding (KME) in that space. Our kernel-based formulation allows us to drop assumptions in the original space: we only assume that the kernel $g$ is bounded, characteristic and translation invariant. Importantly, the characteristic property of $g$ implies that the non-parametric problem of clustering the arms according to their distributions is equivalent, in the RKHS, to clustering the arms according to their KMEs, which allows us to leverage kernel methods. Recently, the maximum mean discrepancy (MMD) have been extensively used for comparing and testing distributions in RKHS – see e.g. (Gretton et al., 2012; Muandet et al., 2017), we similarly use the MMD in our method.

**Contributions.** We introduce *Kernel Active Bandit Clustering* (KABC, Algorithm 2), a new sequential and adaptive algorithm for clustering with bandit feedback. First, KABC is $\delta$-PAC: it outputs the correct partition of the arms with error probability at most $\delta$. Second, it leverages state-of-the-art concentration inequalities for empirical KMEs (Wolfer & Alquier, 2025) to adapt simultaneously to the unknown MMD between groups and to the unknown RKHS variances (see (3)).

Our main theoretical contribution is Theorem 3.1, which provides a non-asymptotic, high-probability upper bound budget of KABC and identifies a variance-aware signal-to-noise ratio governing the difficulty of the problem. At a high level, KABC is an adaptive algorithm that, at each iteration, runs variance-aware kernel two-sample tests based on empirical MMD and empirical variances for all pairs of arms, and increases the sampling budget until all tests can reliably decide whether two arms belong to the same group or not.

**Related work on clustering with bandit feedback problems.** The clustering with bandit feedback problem (CBP) has attracted increasing attention in recent years (Yang et al., 2024; Thuot et al., 2024; Chandran et al., 2025; Yavas et al., 2025; Graf et al., 2025). The problem was first formalized by Yang et al. (2024), who consider a parametric setting where arms are partitioned according to their $d$-dimensional means and the arm distributions are Gaussian. They introduce the BOC algorithm, a $\delta$-PAC procedure based on the Track-and-Stop method of Garivier & Kaufmann (2016), and establish that an expected budget is asymptotically optimal in the regime $\delta \to 0$. In turn, Thuot et al. (2024) study the same parametric CBP and provide a non-asymptotic characterization of the optimal complexity, combining tools from bandit pure exploration with high-dimensional hypothesis testing. A variant of the problem is considered by (Chandran et al., 2025), where the target partition is defined as the single-linkage clustering of the arm means. Yavas et al. (2025) study a family of distribution-matching problems, that encompasses the CBP under the assumption that the arm distributions lies on a finite alphabet. In a different direction, (Graf et al., 2025) study a similar clustering problem, but the learner is only able to sample partial information on each arm. All these works rely on strong parametric or distributional assumptions (e.g., Gaussian or sub-Gaussian arms, finite alphabets). In contrast, we consider here the active clustering problem in a genuinely non-parametric setting by working in an RKHS and clustering arms according to their kernel mean embeddings, under mild assumptions on the kernel rather than on the original distributions.

**Related work on kernel methods.** Recent advances in kernel methods have shown that kernel mean embeddings (KMEs) into RKHSs provide a powerful and versatile framework for statistical learning on distributions (Smola et al., 2007; Muandet et al., 2017). This framework has led to a wide range of applications, including kernel two-sample tests (Gretton et al., 2007a, 2012), independence testing (Gretton et al., 2007b), and many other distributional inference tasks; see Muandet et al. (2017); Berlinet & Thomas-Agnan (2011) for comprehensive reviews. From a more geometric point of view, Sriperumbudur et al. (2011) and Sriperumbudur et al. (2010) study when RKHS embeddings induce metrics on probability measures and characterize universality and characteristic kernels.

Within this framework, kernel two-sample tests compare empirical KMEs of two samples using the maximum mean discrepancy (MMD) as a test statistic, yielding nonparametric tests that avoid explicit density estimation. (Tolstikhin et al., 2017) study the minimax estimation of KMEs via their empirical counterparts and show that, for bounded kernels, the
optimal rate depends only on kernel properties and not on the underlying distributions. (Tolstikhin et al., 2016) extend this perspective to the minimax estimation of the MMD. More recently, (Wolfer & Alquier, 2025) derived state-of-the-art, variance-aware concentration bounds for the MMD between true and empirical KMEs. In particular, for distribution with small variance in the RKHS, the bounds from (Wolfer & Alquier, 2025) achieves better rates. Our analysis builds directly on these variance-aware KME and MMD concentration inequalities.

**Related work on Kernel clustering.** Another related line of work is the fruitful development of kernel methods for clustering. Kernel-based methods such as kernel k-means (Dhillon et al., 2004) and kernel spectral clustering (Ng et al., 2001) are widely used in practice, especially when cluster geometry is complex. More recently, (Vankadara et al., 2021) established separability conditions under which kernel-based clustering can recover the underlying true partition under non-parametric mixture models. In particular, their analysis highlights that these conditions can be expressed in terms of MMD between components. In a complementary line, kernel K-means has also been proposed for clustering distributional data by applying K-means directly to KMEs in RKHS and using MMD as the distance between probability measures (Bafillo et al., 2025). These works focus on batch clustering from a fixed sample. In contrast, we address an active, bandit-style setting where the learner adaptively decides which distributions (arms) to sample in order to recover the clustering.

**Outline** Section 2 introduces the problem setting and notation. Section 3 presents the KABC algorithm and our main upper bound on its sampling complexity.

Section 4 concludes with further comments and perspectives. The proof of our main theoretical contribution can be found in Appendix A.

## 2. Setting and notation

**Kernel and RKHS.** Let $\mathcal{X}$ be a separable topological space. Let $g: \mathcal{X} \times \mathcal{X} \to \mathbb{R}$ be a continuous, positive definite kernel on $\mathcal{X}$. The kernel $g$ induces a reproducing kernel Hilbert space (RKHS) $(\mathcal{H}, \langle \cdot, \cdot \rangle)$ and a feature map $\phi: \mathcal{X} \to \mathcal{H}$ such that

$$ \forall x, y \in \mathcal{X}: \quad g(x, y) = \langle \phi(x), \phi(y) \rangle . \qquad (1) $$

We assume that $g$ is bounded, in the sense that $\sup_{x \in \mathcal{X}} g(x, x) < +\infty$. We define the supremum and range of $g$ as

$$ \bar{g} := \sup_{x,y \in \mathcal{X}} g(x, y), \qquad \tilde{g} := \sup_{x,y \in \mathcal{X}} g(x, y) - \inf_{x,y \in \mathcal{X}} g(x, y). $$

For a distribution $\nu$ on $\mathcal{X}$, its kernel mean embedding (KME) is defined as $\mu_\nu := \mathbb{E}_{X \sim \nu} [\phi(X)] \in \mathcal{H}$, where $\mu_\nu$ is a Bochner integral ((Berlinet & Thomas-Agnan, 2011)). A kernel $g$ is called characteristic if the KME map $\mu: \nu \mapsto \mu_\nu$ is injective. Finally, $g$ is translation invariant if there exists a function $\Psi: \mathcal{X} \to \mathbb{R}$ such that $\forall x, x' \in \mathcal{X}: g(x, x') = \Psi(x - x')$ (Wolfer & Alquier, 2025).

For more background on RKHSs and kernel mean embeddings, see, e.g., (Gretton et al., 2012), (Muandet et al., 2017), or (Berlinet & Thomas-Agnan, 2011).

**Model and unknown partition.** We consider an $N$-armed stochastic bandit problem with $N \ge 2$ arms, indexed by $[N] = \{1, \dots, N\}$, where arm $i$ is associated with an unknown distribution $\nu_i$ on $\mathcal{X}$. The environment is $\nu = \{\nu_1, \dots, \nu_N\}$. For any $i \in [N]$, we denote as

$$ \mu_i := \mathbb{E}_{X \sim \nu_i} [\phi(X)] \in \mathcal{H}. \qquad (2) $$

We assume that there exists a partition $C^*$ of $[N]$ such that two arms belong to the same group if and only if they share the same kernel mean embedding (KME), and we denote by $K$ the number of groups in $C^*$. For any partition $C$ of $[N]$, we write $C(i)$ for the cluster containing $i$. We say that $C$ is correct if it groups together and only together arms with the same KME:

$$ \forall i \neq j \in [N]: \quad \mu_i = \mu_j \iff C(i) = C(j). $$

As usual in clustering problems, the true partition $C^*$ is only defined up to permutation of the groups. When the kernel is characteristic, it corresponds exactly to the problem of clustering the arms according to their underlying distributions.
**Sequential strategies and δ-PAC objective.** We work in an adaptive, sequential setting, where an algorithm interacts with the bandit environment–i.e., collects samples–in order to recover the clustering (up to permutation of the groups).

A strategy collects data sequentially from the environment in the following way: at each time $t \ge 1$, it selects an arm $A_t \in [N]$ and observes $X_t \sim \nu_{A_t}$. Let $\mathcal{F}_t = \sigma(A_1, X_1, \dots, A_t, X_t)$ denote the information available at time $t$. A strategy is specified by:

1. a selection rule choosing the next arm $A_t$ based on the passed $\mathcal{F}_{t-1}$;

2. a stopping time $\tau$ with respect to $(\mathcal{F}_t)$ deciding when to stop;

3. a recommendation rule that outputs a clustering $C_\tau$ based on $\mathcal{F}_\tau$.

Given a confidence level $\delta \in (0, 1]$ and a class of environments $\mathcal{E}$, we call a strategy $\delta$-PAC for this problem if

$$ \forall \nu \in \mathcal{E}: \quad \mathbb{P}(C_\tau \text{ is correct}) \ge 1 - \delta. $$

Our goal is to design $\delta$-PAC algorithms whose sampling complexity (the sampling budget) is as small as possible. We consider for the problem the class of problems with exactly $K$ nonempty groups, where the number of groups $K$ is known by the learner.

We characterize this complexity in terms of three main factors: the confidence parameter $\delta$, the kernel $g$, and the environment $\nu$. On the kernel side, we will use the bound $\bar{g}$; on the environment side we consider distribution-dependent quantities in the RKHS. In particular, we measure separation between arms via the maximum mean discrepancy $\|\mu_i - \mu_j\|$. Then, following (Wolfer & Alquier, 2025), we define the RKHS variance of arm $i$ as

$$ \mathcal{V}_i^* := \mathbb{E}_{X \sim \nu_i} [\|\phi(X) - \mu_i\|^2], \qquad (3) $$

which we interpret as a noise level.

Having specified the model, and the $\delta$-PAC objective, we now turn to the design of our algorithm.

### 3. Algorithm

We introduce KABC (Kernel Active Bandit Clustering), an adaptive algorithm that recovers the $K$ true clusters defined by equality of kernel mean embeddings (KME). The algorithm does not require any knowledge of the gaps between clusters or of the variances in the RKHS. The pseudo-code is given in Algorithm 2.

**Kernel two-sample testing for clustering.** At a high level, KABC reduces clustering to deciding, for every pair of arms, whether they share the same KME or not. This is exactly the setting of kernel two-sample testing, which we now recall and adapt to our bandit scenario. In particular, we follow the work of (Wolfer & Alquier, 2025), and we use a variance-aware bound on empirical KME.

Consider two arms $i, j \in [N]$. The null hypothesis $H_0^{i,j}: \mu_i = \mu_j$ (same KME) is tested against $H_1^{i,j}: \mu_i \neq \mu_j$. Given two arms $i$ and $j$ and a per-arm budget $n \ge 1$, we draw i.i.d. samples $(X_1^i, \dots, X_n^i) \sim \nu_i$ and $(X_1^j, \dots, X_n^j) \sim \nu_j$ and form the empirical KMEs

$$ \hat{\mu}_i := \frac{1}{n} \sum_{t=1}^{n} g(X_t^i, \cdot), \quad \hat{\mu}_j := \frac{1}{n} \sum_{t=1}^{n} g(X_t^j, \cdot). $$

By the reproducing property, the squared empirical distance between $\hat{\mu}_i$ and $\hat{\mu}_j$ is computed using only the kernel:

$$ \|\hat{\mu}_j - \hat{\mu}_i\|^2 = \frac{1}{n^2} \sum_{s,t=1}^{n} (g(X_s^i, X_t^i) - 2g(X_s^i, X_t^j) + g(X_s^j, X_t^j)). \qquad (4) $$

As in kernel two-sample testing, we interpret $\|\hat{\mu}_j - \hat{\mu}_i\|$ as an empirical maximum mean discrepancy (MMD) between the distributions of arms $i$ and $j$, and use it as a test statistic for the hypothesis $H_0^{i,j}: \mu_i = \mu_j$ versus $H_1^{i,j}: \mu_i \neq \mu_j$.
Under $H_0^{i,j}$, $\|\hat{\mu}_j - \hat{\mu}_i\| \to 0$; under $H_1^{i,j}$, $\|\hat{\mu}_j - \hat{\mu}_i\| \to \|\mu_i - \mu_j\|_{\mathcal{H}} > 0$. We reject $H_0^{i,j}$ (declare arms $i, j$ in different clusters) if $\|\hat{\mu}_j - \hat{\mu}_i\| > B^{i,j}(n, \delta')$, where $B^{i,j}(n, \delta')$ is a threshold derived from non-asymptotic concentration bounds. The comparison $\|\hat{\mu}_i - \hat{\mu}_j\| \le B^{i,j}(n, \delta')$ serves as a proxy to decide whether $(i, j)$ belong to the same group or not.

Standard MMD tests use kernel-uniform bounds $B^{i,j} \asymp \sqrt{g \log(1/\delta)/n}$ (Tolstikhin et al., 2017). We instead leverage empirical RKHS variance estimators:

$$ \hat{\mathcal{V}}_i := \frac{1}{n-1} \sum_{t=1}^{n} \left( g(X_t^i, X_t^i) - \frac{1}{n} \sum_{s=1}^{n} g(X_t^i, X_s^i) \right). \qquad (5) $$

We use then as threshold

$$ \mathcal{B}^{i,j}(n, \delta') = \left(\sqrt{\hat{\mathcal{V}}_i} + \sqrt{\hat{\mathcal{V}}_j}\right) \sqrt{2 \frac{\log \frac{8(N^2-N)}{\delta'}}{n}} + \frac{32}{3} \sqrt{\tilde{g}} \frac{\log \frac{8(N^2-N)}{\delta'}}{n} . \qquad (6) $$

Indeed, Lemma A.3 from (Wolfer & Alquier, 2025) – see also Appendix A- ensures that

$$ \mathbb{P}[\|\mu_i - \mu_j\| - \|\hat{\mu}_j - \hat{\mu}_i\| \le \mathcal{B}^{i,j}(n, \delta')] \ge 1 - \frac{\delta'}{N^2 - N}. $$

**Graph-based clustering.** To transform these pairwise kernel two-sample tests into a clustering procedure, we introduce a graph-based subroutine that we call CLUSTER($n, \delta'$) that takes as input a fixed per-arm sampling budget $n$ and a confidence parameter $\delta' \in (0, 1]$. The subroutine CLUSTER($n, \delta'$) simultaneous performs two-sample testing across all $N(N-1)/2$ pairs via a graph-based construction (Algorithm 1). For any $\{i, j\}$, the edge $\{i, j\}$ is added to $G = (V, E)$ whenever $H_0^{i,j}$ is not rejected, that is $\|\hat{\mu}_j - \hat{\mu}_i\| \le \mathcal{B}^{i,j}$. The connected components of $G$ form the clustering $C$.

The type I error (false splits within clusters) will be controlled by construction: arms with identical KME remain connected with high probability. Type II errors (false merges across clusters) are controlled by the MMD concentration when $n$ is large enough. Thus, CLUSTER either returns the true partition or fewer than $K$ clusters.

**Active choice of the Adaptive procedure** The minimal $n$ ensuring reliable two-sample testing across all pairs depends on unknown gaps $\|\mu_i - \mu_j\|$ and variances $V_i^*$. Hence, our main procedure KABC (Algorithm 2) applies the so-called "doubling trick". At iteration $k \ge 1$, define the per-arm sampling budget as

$$ n_k = \left\lceil 2^k \log\left(\frac{8(N^2 - N)}{\delta_k}\right) \right\rceil, \quad \delta_k = \frac{\delta}{4k^2}. $$

The algorithm calls the subroutine CLUSTER($n_k, \delta_k$) until $|C_k| = K$, then outputs $C_k$. Observe that the true number of clusters $K$ is known by the learner, and is only used in the stopping condition. The quadratic decay of the confidence $\delta_k$ ensures $\sum_k \delta_k \le \delta$.

We establish in Theorem 3.1 that KABC is $\delta$-PAC, terminates almost surely, and that its sampling complexity $\tau$ satisfies

$$ \tau \lesssim \frac{N}{s_*^2} \log\left(\frac{N}{\delta}\right), $$

where $s_*^2$ defined in (7) is interpreted as a signal-to-noise ratio.

**Theorem 3.1 (KABC($\delta$, $K$) is $\delta$-PAC).** Let $g$ be a continuous, positive definite, characteristic, translation invariant, bounded kernel, and let $\delta \in (0, 1]$. Define the (variance-aware) signal-to-noise ratio

$$ s_*^2(\nu) := \min_{\substack{i \neq j \in [N] \\ \mu_i \neq \mu_j}} \left( \frac{\|\mu_i - \mu_j\|^2}{V_i^* \vee V_j^*} \wedge \frac{2\|\mu_i - \mu_j\|}{\sqrt{g}} \right). \qquad (7) $$

Then:

1. Algorithm 2, KABC($\delta$, $K$), is $\delta$-PAC, i.e., it outputs the true clustering with probability at least $1 - \delta$;
<caption>**Algorithm 1 CLUSTER(n, δ') Clustering with fixed budget N × n**</caption>

1: sample ← SAMPLE(n) // Sample each arm n times
2: (||μ̂<sub>j</sub> - μ̂<sub>i</sub>||)ᵢ≠ⱼ∈[N], (μ̂<sub>i</sub>)ᵢ∈[N] ← COMPUTESTATISTICS(sample) // See (4)(5)
3: (B<sup>i,j</sup>(n, δ'))ᵢ≠ⱼ∈[N] ← COMPUTETHRESHOLD(n, δ') // See (6)
4: V ← [N]
5: E ← ∅
6: **for** i ≠ j ∈ [N] **do**
7: &nbsp;&nbsp;&nbsp;&nbsp;**if** ||μ̂<sub>j</sub> - μ̂<sub>i</sub>|| ≤ B<sup>i,j</sup>(n, δ') **then**
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;E ← E ∪ {{i, j}} // Do not reject H<sub>0</sub><sup>i,j</sup>; connect i and j
9: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
10: **end for**
11: G ← (V, E)
12: **return** GETCONNECTEDCOMPONENTS(G)

<caption>**Algorithm 2 KABC(δ, K)** Kernel Active Bandit Clustering</caption>

1: **for** k = 1, 2, ... **do**
2: &nbsp;&nbsp;&nbsp;&nbsp;δ_k ← δ / (4k^2) // Per-iteration error
3: &nbsp;&nbsp;&nbsp;&nbsp;n_k ← ⌊ 2^k log (8(N^2 - N) / δ_k) ⌋ // Per-arm sampling budget
4: &nbsp;&nbsp;&nbsp;&nbsp;C_k ← CLUSTER(n_k, δ_k)
5: &nbsp;&nbsp;&nbsp;&nbsp;**if** |C_k| = K **then**
6: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**return** C_k // Stop when K clusters are identified
7: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
8: **end for**

2. with probability at least 1 − δ, the total budget τ of KABC(δ, K) satisfies

$$
\tau \le 8N \cdot \left( \frac{128}{s_*^2} \lor 1 \right) \cdot \left( \log \left( \frac{32(N^2 - N)k_*^2}{\delta} \right) \right), \quad (8)
$$

where $k_* = \lceil \log_2 \left( \frac{128}{s_*^2} \right) \rceil$ is a logarithmic term independent of $\delta$.

The proof is postponed to Appendix A.

In Theorem 3.1, Algorithm 2 is shown to be δ-PAC while adapting to the instance-specific quantity s*. We now comment
on the sampling budget from Equation (8).

First, note that N appears as an overall multiplicative factor in the budget. This is because every call to CLUSTER (Algorithm 1) allocates samples uniformly across arms, so each arm is queried the same number of times. Such a linear dependence in N is unavoidable when the inter-cluster separations are all of the same order.

In total, each arm receives $\tau/N$ samples, which scales as $s_*^{-2} \log(N/\delta)$. The quantity $s_*^{-2}$ plays the role of a signal-to-noise ratio, matching the sample complexity needed to perform a nonparametric two-sample test based on the MMD with state-of-the-art procedures such as (Wolfer & Alquier, 2025). The minimum in the definition of $s_*$ reflects that, for every pair of arms $i, j$, one must test the hypotheses $\mu_i = \mu_j$ versus $\mu_i \neq \mu_j$ with error probability at most $\delta/(N^2 - N)$, so that a union bound guarantees an exact clustering overall.

The term $s_*^{-2}$ also appears inside the logarithm through an additive contribution of order $c \frac{N}{s_*^2} \log \log(s_*^{-2})$, reflecting the cost of adapting to the unknown value of $s_*$.

Although the linear kernel is unbounded, consider the special case of Gaussian distribution with a linear kernel, where $k(x, y) = \langle x, y \rangle$, and $\nu_i = \mathcal{N}(\mu_i, \sigma_i^2 I_d)$ on $\mathbb{R}^d$. To recover the bounded-kernel assumption, restrict to truncated Gaussians
supported on a compact subset of $\mathcal{B}(0, \sqrt{g})$. In this setting, our upper bound on the sampling budget scales as

$$ \max_{\mu_i \neq \mu_j} \left( \frac{\sigma_i^2 \vee \sigma_j^2}{\|\mu_i - \mu_j\|_2^2} \vee \frac{\sqrt{g}}{\|\mu_i - \mu_j\|_2} \right) \times N \log(N/\delta). $$

The bound from (Thuot et al., 2024), scales with

$$ \max_{\mu_i \neq \mu_j} \frac{\sigma_i^2 \vee \sigma_j^2}{\|\mu_i - \mu_j\|_2^2} \times \left( N \log(N/\delta) \vee \sqrt{dKN \log(N/\delta)} \right), $$

and is optimal, known to be optimal, at least in the canonical regime where the clusters have comparable sizes. When $\|\mu_i - \mu_j\| \le \sigma_j^2/\sqrt{g}$ and the dimension dd is moderate, our bound is therefore analogous to this optimal Gaussian linear-kernel rate.

## 4. Discussion

**Benefit of variance-aware bounds.** In this manuscript, we relied on the variance-aware bounds of (Wolfer & Alquier, 2025). As an alternative, we could have used sub-Gaussian type bounds –see Proposition A.1 in (Tolstikhin et al., 2017). For that purpose, we would only need to replace that threshold $\mathcal{B}^{i,j}(n, \delta')$ in Algorithm 1 by $\sqrt{g/n}(\sqrt{\log(8(N^2 - N)/\delta)} + 2)$. The modified algorithm would still be $\delta$-PAC, but its budget $\tau$ would now be bounded by $N\bar{g}[\min_{i \neq j} \|\mu_i - \mu_j\|]^{-2} \log(N/\delta)$. Since $\mathcal{V}_i^* \le \bar{g}$ for every arm $i$, the variance-aware bounds of (Wolfer & Alquier, 2025) are never worse and can substantially improve the budget whenever $\mathcal{V}_i^* \ll \bar{g}$.

**Unknown number of clusters.** In this manuscript, we assume that the number of clusters is known to the learner, and our algorithm is adaptive to the unknown quantity $s_*$, which plays the role of a signal-to-noise ratio for the problem. The number of clusters is only used in the stopping condition of the procedure. If a lower bound $s_* \ge s_0$ is available, then, even without knowing $K$, a single call CLUSTER($n_0$, $\delta$) to Algorithm 1 with a per-arm sampling budget $n_0 \asymp s_0^{-2} \log(N/\delta)$ yields a correct partition with high probability $1 - \delta$. Observe that, when neither $K$ nor $s_*$ is known, the problem is ill-posed, since no algorithm can, in finite time, distinguish two arms that are arbitrarily close in MMD from two arms belonging to the same cluster.

**Computational complexity.** The computational complexity of KABC is of the order $\log(N) [N^2 + N/s_*^2]$. We could slightly reduce it to $\log(N) [Nk + N/s_*^2]$ by evaluating the quantities $1\{\|\hat{\mu}_j - \hat{\mu}_i\| \le \mathcal{B}^{ij}\}$ in a sequential fashion as done e.g. in (Thuot et al., 2024). In this manuscript, we rather described Algorithm KABC for the sake of clarity.

**Adaptivity** The algorithm is adaptive to the unknown quantity $s_*$. Leveraging classical techniques from bandit theory, it achieves a guarantee that scales as $s_*^{-2}$, without any prior knowledge of the environment, except for the number of clusters. One can also define a non-adaptive variant, which takes $s_*$ as an input parameter. More precisely, consider the subroutine CLUSTER (Algorithm 1) with confidence parameter $\delta$ and per-arm sampling budget $n_* = 128 s_*^{-2} \log(8(N^2 - N)/\delta)$. Then Lemma A.1 guarantees that the output of CLUSTER($n_*$, $\delta$) is correct with probability at least $1 - \delta$. The total budget of this non-adaptive procedure is therefore $c N s_*^{-2} \log(8(N^2 - N)/\delta)$. To the best of our knowledge, and using the MMD-based two-sample tests of (Wolfer & Alquier, 2025), this is the state-of-the-art sampling budget that ensures correct clustering of all arms with global error probability at most $\delta$. Finally, note that the price of adaptivity is only an additional doubly logarithmic term $c N \log \log(s_*^{-2})$, which is negligible compared to the leading term, for instance if $\delta$ is small.

## Acknowledgment

This work is partly supported by the German Research Foundation (DFG) and by the ANR through the DFG-ANR PRCI "ASCAI" (GH 257/3-1; ANR-21-CE23-0035)

## References

Bafllo, A., Berrendero, J. R., and Sánchez-Signorini, M. Kernel k-means clustering of distributional data. arXiv preprint arXiv:2509.18037, 2025.
Berlinet, A. and Thomas-Agnan, C. *Reproducing kernel Hilbert spaces in probability and statistics*. Springer Science & Business Media, 2011.

Bubeck, S., Cesa-Bianchi, N., et al. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. *Foundations and Trends® in Machine Learning*, 5(1):1–122, 2012.

Chandran, G. D., Reddy, K. S., and Bhashyam, S. Online clustering with bandit information. In *2025 IEEE International Symposium on Information Theory (ISIT)*, pp. 1–6. IEEE, 2025.

Dhillon, I. S., Guan, Y., and Kulis, B. Kernel k-means: spectral clustering and normalized cuts. In *Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining*, pp. 551–556, 2004.

Garivier, A. and Kaufmann, E. Optimal best arm identification with fixed confidence. In *Conference on Learning Theory*, pp. 998–1027. PMLR, 2016.

Graf, M., Thuot, V., and Verzelen, N. Clustering items through bandit feedback: Finding the right feature out of many. *arXiv preprint arXiv:2503.11209*, 2025.

Gretton, A., Borgwardt, K. M., Rasch, M., Schölkopf, B., and Smola, A. J. A kernel approach to comparing distributions. In *Proceedings of the national conference on artificial intelligence*, volume 22, pp. 1637. AAAI Press, 2007a.

Gretton, A., Fukumizu, K., Teo, C., Song, L., Schölkopf, B., and Smola, A. A kernel statistical test of independence. In *Advances in neural information processing systems*, volume 20, 2007b.

Gretton, A., Borgwardt, K. M., Rasch, M. J., Schölkopf, B., and Smola, A. A kernel two-sample test. *Journal of Machine Learning Research*, 13(1):723–773, 2012.

Lattimore, T. and Szepesvári, C. *Bandit Algorithms*. Cambridge University Press, 2020.

Muandet, K., Fukumizu, K., Sriperumbudur, B., Schölkopf, B., et al. Kernel mean embedding of distributions: A review and beyond. *Foundations and Trends® in Machine Learning*, 10(1-2):1–141, 2017.

Ng, A., Jordan, M., and Weiss, Y. On spectral clustering: Analysis and an algorithm. *Advances in neural information processing systems*, 14, 2001.

Smola, A., Gretton, A., Song, L., and Schölkopf, B. A hilbert space embedding for distributions. In *International conference on algorithmic learning theory*, pp. 13–31. Springer, 2007.

Sriperumbudur, B. K., Gretton, A., Fukumizu, K., Schölkopf, B., and Lanckriet, G. R. Hilbert space embeddings and metrics on probability measures. *The Journal of Machine Learning Research*, 11:1517–1561, 2010.

Sriperumbudur, B. K., Fukumizu, K., and Lanckriet, G. R. G. Universality, characteristic kernels and rkhs embedding of measures. *J. Mach. Learn. Res.*, 12(null):2389–2410, July 2011. ISSN 1532-4435.

Thuot, V., Carpentier, A., Giraud, C., and Verzelen, N. Active clustering with bandit feedback. *CoRR*, 2024.

Tolstikhin, I., Sriperumbudur, B. K., and Muandet, K. Minimax estimation of kernel mean embeddings. *Journal of Machine Learning Research*, 18(86):1–47, 2017.

Tolstikhin, I. O., Sriperumbudur, B. K., and Schölkopf, B. Minimax estimation of maximum mean discrepancy with radial kernels. In *Advances in Neural Information Processing Systems*, volume 29, 2016.

Vankadara, L. C., Bordt, S., von Luxburg, U., and Ghoshdastidar, D. Recovery guarantees for kernel-based clustering under non-parametric mixture models. In *International Conference on Artificial Intelligence and Statistics*, pp. 3817–3825. PMLR, 2021.

Wolfer, G. and Alquier, P. Variance-aware estimation of kernel mean embedding. *Journal of Machine Learning Research*, 26(57):1–48, 2025.

Yang, J., Zhong, Z., and Tan, V. Y. Optimal clustering with bandit feedback. *Journal of Machine Learning Research*, 25 (186):1–54, 2024.

Yavas, R. C., Huang, Y., Tan, V. Y. F., and Scarlett, J. A general framework for clustering and distribution matching with bandit feedback. *IEEE Transactions on Information Theory*, 71(3):2116–2139, 2025. doi: 10.1109/TIT.2025.3528655.
A. Proofs of Theorem 3.1

In this appendix, we prove the correctness of KABC (Algorithm 2) and derive a high-probability upper bound on its budget.

A.1. Proof of Theorem 3.1

Recall from Section 3 that KABC repeatedly calls the subroutine CLUSTER($n_k$, $\delta_k$) with increasing per-arm budgets $n_k$ and decreasing confidence levels $\delta_k$. At iteration $k$, CLUSTER constructs a graph by performing variance-aware kernel two-sample tests between all pairs of arms and returns the connected components as a clustering $C_k$. For any arm $i \in [N]$, let $C_k(i)$ denote the unique cluster in $C_k$ containing $i$.

The analysis of KABC therefore reduces to understanding, for each fixed $k$, how CLUSTER behaves in terms of type I and type II errors under the thresholds $B^{i,j}(n_k, \delta_k)$ introduced in Equation 6.

Intuitively, we need that CLUSTER($n_k$, $\delta_k$) either returns fewer than $K$ clusters or identifies the correct $K$ clusters. The condition $\|\hat{\mu}_i - \hat{\mu}_j\| \le B^{i,j}(n_k, \delta_k)$ ensures that arms $i$ and $j$ with $\mu_i = \mu_j$ are clustered together with high probability. Moreover, there exists an iteration $k$ such that arms with $\mu_i \neq \mu_j$ are separated (i.e., $\|\hat{\mu}_i - \hat{\mu}_j\| > B^{i,j}(n_k, \delta_k)$) with high probability, yielding exactly $K$ clusters. These key properties of CLUSTER are formalized in Lemma A.1, whose proof—relying solely on concentration inequalities from Appendix A.3—is deferred to Appendix A.2.

**Lemma A.1.** For a fixed iteration $k \ge 1$, consider the clustering $C_k$ returned by CLUSTER($n_k$, $\delta_k$), and let $C_k(i)$ denote the cluster containing arm $i$.

Define the event type I error event $\mathcal{E}_{1,k}$ under which arms with identical KMEs are assigned to different clusters in $C_k$:

$$ \mathcal{E}_{1,k} = \bigcup_{\substack{i \neq j \in [N] \\ \mu_i = \mu_j}} \{C_k(i) \neq C_k(j)\} . \qquad (9) $$

Then,

$$ \forall k \ge 1, \mathbb{P}(\mathcal{E}_{1,k}) \le \delta_k . $$

Define the type II error event $\mathcal{E}_{2,k}$ under which arms with distinct KMEs are assigned to the same cluster in $C_k$:

$$ \mathcal{E}_{2,k} = \bigcup_{\substack{i \neq j \in [N] \\ \mu_i \neq \mu_j}} \{C_k(i) = C_k(j)\} . \qquad (10) $$

Let $s_* = s_*(\nu)$ be given by

$$ s_*^2(\nu) := \min_{\substack{i \neq j \in [N] \\ \mu_i \neq \mu_j}} \frac{\|\mu_i - \mu_j\|^2}{\mathcal{V}_i^*} \wedge \frac{2\|\mu_i - \mu_j\|}{\sqrt{g}} . \qquad (11) $$

For any iteration $\forall k \ge 1$, such that $n_k \ge 128 \frac{1}{s_*^2} \log(\frac{8(N^2 - N)}{\delta_k})$, then

$$ \mathbb{P}(\mathcal{E}_{2,k}) \le \delta_k . $$

**Proof of Theorem 3.1.** Let $\delta \in (0, 1]$ and assume the environment $\nu$ has $N$ arms forming exactly $K$ groups with distinct KMEs. We proceed in three parts: (i) correctness (outputting the true partition with probability at least $1 - \delta$), (ii) almost-sure termination, and (iii) a high-probability bound on the sampling complexity.

(i) **Correctness of KABC($\delta, K$)** Consider the call of KABC($\delta, K$) on the environment $\nu$. Let $C$ be the clustering returned by KABC($\delta, K$), obtained from CLUSTER($n_k$, $\delta_k$) at the stopping iteration $k \ge 1$. Observe that $k < +\infty$ happens almost surely (as we prove in (ii)), and the clustering $C$ contains exactly $K$ groups. On the event $\mathcal{E}_{1,k}^c$ (Equation 9), all arms with identical KMEs are clustered together. Since, by definition of the model in Section 2, the true partition $C^*$ is exactly the partition into equivalence classes of the relation $\mu_i = \mu_j$ and has cardinality $K$, any clustering with no type I error and exactly $K$ nonempty clusters must coincide with $C^*$ (up to permutation of the labels). Since the stopping iteration $k$ is unknown, we proceed with a union bound
$$
\begin{align*}
\mathbb{P}(\{C \text{ is incorrect}\}) &= \mathbb{P}(\{\exists k \ge 1 : C_k \text{ is incorrect and } |C_k| = K\}) \\
&\le \sum_{k=1}^{\infty} \mathbb{P}(\mathcal{E}_{1,k}) \\
&\le \sum_{k=1}^{\infty} \delta_k \le \delta,
\end{align*}
$$

where the final bound uses $\sum_{k=1}^{\infty} 1/k^2 = \pi^2/6$ and $\delta_k = \delta/(4k^2)$.

(ii) **Almost-sure termination of KABC($\delta, K$)** On $\mathcal{E}_{1,k}^c \cap \mathcal{E}_{2,k}^c$, we have that $C_k$ clusters the arms exactly according to their KMEs, and $C_k$ equals the true partition. In particular $|C_k| = K$, and the algorithm terminates. In other words, once $n_k$ is large enough, the graph built by CLUSTER exactly matches the true equivalence relation $\mu_i = \mu_j$, and KABC stops at that iteration.

Then,

$$
\mathbb{P}(KABC(\delta, K) \text{ never terminates}) \le \inf_{k \to \infty} \mathbb{P}(\mathcal{E}_{1,k} \cup \mathcal{E}_{2,k}) .
$$

Moreover, for $k$ large enough, it holds that $n_k \ge 128s_*^{-2} \log (8(N^2 - N)/\delta_k)$, Lemma A.1 then implies that for $k$ large enough, $\mathbb{P}(\mathcal{E}_{1,k} \cup \mathcal{E}_{2,k}) \le \delta_k$, and $\lim_{k \to \infty} \mathbb{P}(\mathcal{E}_{1,k} \cup \mathcal{E}_{2,k}) = 0$. Finally,

$$
\mathbb{P}(KABC(\delta, K) \text{ never terminates}) \le \inf_{k \to \infty} \mathbb{P}(\mathcal{E}_{1,k} \cup \mathcal{E}_{2,k}) = 0,
$$

and the algorithm terminates almost surely.

(iii) **Budget of KABC($\delta, K$)** Denote

$$
k_* = \left\lceil \log_2 \left( \frac{128}{s_*^2} \right) \right\rceil \vee 1, \qquad (12)
$$

so that $n_k \ge 128s_*^{-2} \log (8(N^2 - N)/\delta_k)$ for all $k \ge k_*$.

On $\mathcal{E}_{1,k_*}^c \cap \mathcal{E}_{2,k_*}^c$, the algorithm terminates at or before iteration $k_*$.
The per-iteration budget is $\tau_k = N \cdot n_k$, so the total budget $\tau$ satisfies

$$
\mathbb{P} \left( \tau \le \sum_{k=1}^{k_*} \tau_k \right) \ge \mathbb{P} \left( \mathcal{E}_{1,k_*}^c \cap \mathcal{E}_{2,k_*}^c \right) \ge 1 - \delta_{k_*} \ge 1 - \delta.
$$

Now,

$$
\begin{align*}
\sum_{k=1}^{k_*} \tau_k = N \sum_{k=1}^{k_*} n_k &= N \sum_{k=1}^{k_*} \left\lceil 2^k \log \frac{8(N^2 - N)}{\delta_k} \right\rceil \\
&\le 2 \sum_{k=1}^{k_*} 2^k \cdot \log \left( \frac{8(N^2 - N)}{\delta_{k_*}} \right) \\
&\le 4N \cdot 2^{k_*} \cdot \log \left( \frac{8(N^2 - N)}{\delta_{k_*}} \right) \\
&\le 8N \cdot \left( \frac{128}{s_*^2} \vee 1 \right) \cdot \left( \log \left( \frac{32(N^2 - N)k_*^2}{\delta} \right) \right)
\end{align*}
$$

□
## A.2. Proof of Lemma A.1

*Proof.* We fix any iteration $k$, for which we call CLUSTER($n_k$, $\delta_k$). Recall that the algorithm CLUSTER constructs an undirected graph $G_k = ([N], E_k)$, whose vertices are the arms $[N]$, and whose set of edges is $E_k = \{\{i, j\} : \|\hat{\mu}_i - \hat{\mu}_j\| \le B^{i,j}(n_k, \delta_k)\}$. Then, the clustering $C_k$ is defined as the connected components of $G_k$.

### Type-I error: splitting arms with identical KME.

We consider the event $\mathcal{E}_{1,k}$ (Equation (9)), under which $C_k$ assigns two arms with the same KME to different clusters. If $C_k(i) \neq C_k(j)$, then $E_k$ cannot contain the edge $\{i, j\}$, because otherwise they would be in the same connected component, and thus in the same cluster. By definition of $E_k$, if $(i, j) \notin E_k$, that means that the comparison of $\|\hat{\mu}_j - \hat{\mu}_i\|$ to the decision boundary yielded false. It follows by construction that

$$ \mathcal{E}_{1,k} \subset \bigcup_{\substack{i \neq j \in [N] \\ \mu_i = \mu_j}} \{\|\hat{\mu}_j - \hat{\mu}_i\| > B^{i,j}(n_k, \delta_k)\}, $$

where

$$ B^{i,j}(n_k, \delta_k) = \left( \sqrt{\hat{V}_i} + \sqrt{\hat{V}_j} \right) \sqrt{2 \frac{\log \frac{8(N^2 - N)}{\delta_k}}{n_k}} + \frac{32}{3} \sqrt{\hat{g}} \frac{\log \frac{8(N^2 - N)}{\delta_k}}{n_k}. $$

Now, we bound the probability $\mathbb{P}(\mathcal{E}_{1,k})$, with a union bound, together with the concentration inequality from Theorem A.3 with $\delta' = \frac{\delta_k}{N^2 - N}$,

$$ \begin{aligned} \mathbb{P}(\mathcal{E}_{1,k}) &\le \sum_{\substack{i \neq j \in [N] \\ \mu_i = \mu_j}} \mathbb{P}(\|\hat{\mu}_i - \hat{\mu}_j\| > B^{i,j}(n_k, \delta_k)) \\ &\le \sum_{\substack{i \neq j \in [N] \\ \mu_i = \mu_j}} \frac{\delta_k}{N^2 - N} \le \delta_k. \end{aligned} $$

### Type-II error: merging arms with different KMEs.

We now consider the event $\mathcal{E}_{2,k}$ (Equation 10, under which $C_k$ assigns two arms with different KMEs to the same cluster. For simplicity, we note

$$ \delta_{N,k} = \frac{\delta_k}{(N^2 - N)} = \frac{\delta}{4 \cdot (N^2 - N) \cdot k^2} $$

Assume that $\mu_i \neq \mu_j$, while $C_k(i) = C_k(j)$. By construction of $C_k$, the condition $C_k(i) = C_k(j)$ implies that there exists a path in the graph $G_k = ([N], E_k)$ between $i$ and $j$. Since there is a path between two arms with different means, somewhere on that path must be an edge connecting two arms with different means. Thus, it holds that

$$ \mathcal{E}_{2,k} \subset \bigcup_{\substack{i,j \in [N] \\ \mu_i \neq \mu_j}} \{\|\hat{\mu}_j - \hat{\mu}_i\| \le B^{i,j}(n_k, \delta_k)\}. \quad (13) $$

Let $i, j \in [N]$ be two arms such that $\mu_i \neq \mu_j$. Now we need to control the probability of the event $A_{i,j} := \{\|\hat{\mu}_j - \hat{\mu}_i\| \le B^{i,j}(n_k, \delta_k)\}$.

Theorem A.4 provides us that with probability at least $1 - \frac{\delta_{N,k}}{2}$

$$ \|\hat{\mu}_j - \hat{\mu}_i\| \ge \|\mu_j - \mu_i\| - \left(\sqrt{\hat{V}_i^*} + \sqrt{\hat{V}_j^*}\right) \sqrt{2 \frac{\log \frac{8}{\delta_{N,k}}}{n_k}} - \frac{8}{3} \sqrt{\hat{g}} \frac{\log \frac{8}{\delta_{N,k}}}{n_k}. $$

It remains to prove that the assumption $n_k$ ensures that (with high probability), the lower bound above from Theorem A.4 will be larger than the threshold $B^{i,j}(n_k, \delta_k)$ used for our classification.
Since $\mathcal{B}^{i,j}(n_k, \delta_k)$ contains the empirical variance, we first need to bound the empirical variance by the true variance. We define the event

$$B_i := \left\{ \sqrt{\hat{\mathcal{V}}_i} \le \sqrt{\mathcal{V}_i^*} + 2\sqrt{\frac{2\tilde{g}\log \frac{4}{\delta_{N,k}}}{n_k}} \right\},$$

whose probability is controlled by Theorem A.5 as

$$\mathbb{P}(B_i^c) \le \frac{\delta_{N,k}}{8}. \qquad (14)$$

With a union bound on Equation 13, we have that

$$\begin{aligned}
\mathbb{P}(\mathcal{E}_{2,k}) &\le \sum_{\substack{i,j \in [N] \\ \mu_i \ne \mu_j}} \mathbb{P}(A_{i,j}) \\
&\le \sum_{\substack{i,j \in [N] \\ \mu_i \ne \mu_j}} (\mathbb{P}(A_{i,j} \cap B_i \cap B_j) + \mathbb{P}(B_i^c) + \mathbb{P}(B_j^c)) \\
&\le \sum_{\substack{i,j \in [N] \\ \mu_i \ne \mu_j}} \left( \mathbb{P}(A_{i,j} \cap B_i \cap B_j) + \frac{\delta_{N,k}}{4} \right),
\end{aligned} \qquad (15)$$

where the final inequality follows from Equation (14). Then, it remains to bound the probability of the events $A_{i,j} \cap B_i \cap B_j$. Under $A_{i,j} \cap B_i \cap B_j$, it holds that:

$$\begin{aligned}
\|\hat{\mu}_j - \hat{\mu}_i\| &\le \left(\sqrt{\hat{\mathcal{V}}_i} + \sqrt{\hat{\mathcal{V}}_j}\right) \sqrt{2\frac{\log \frac{8}{\delta_{N,k}}}{n_k}} + \frac{32}{3}\sqrt{\tilde{g}}\frac{\log \frac{8}{\delta_{N,k}}}{n_k} \\
&\le \left(\sqrt{\mathcal{V}_i^*} + \sqrt{\mathcal{V}_j^*} + 4\sqrt{\frac{2\tilde{g}\log \frac{8}{\delta_{N,k}}}{n_k}}\right) \sqrt{2\frac{\log \frac{8}{\delta_{N,k}}}{n_k}} + \frac{32}{3}\sqrt{\tilde{g}}\frac{\log \frac{8}{\delta_{N,k}}}{n_k} \\
&= \left(\sqrt{\mathcal{V}_i^*} + \sqrt{\mathcal{V}_j^*}\right) \sqrt{2\frac{\log \frac{8}{\delta_{N,k}}}{n_k}} + \frac{56}{3}\sqrt{\tilde{g}}\frac{\log \frac{8}{\delta_{N,k}}}{n_k}
\end{aligned} \qquad (16)$$

Now, assume that

$$n_k \ge \max_{\substack{i \ne j \in [N] \\ \mu_i \ne \mu_j}} \max \left\{ 128 \frac{\mathcal{V}_i^*}{\|\mu_i - \mu_j\|^2}, \frac{112\sqrt{\tilde{g}} + 16\sqrt{\tilde{g}}}{3\|\mu_i - \mu_j\|^2} \right\} \log \frac{8}{\delta_{N,k}}$$

In particular, as $\tilde{g} \le 2\tilde{g}$, this will hold if $n_k \ge 128 \frac{1}{s_*^2} \log \frac{8}{\delta_{N,k}}$.

Now, we derive from direct computation that

$$\begin{aligned}
& \left(\sqrt{\mathcal{V}_i^*} + \sqrt{\mathcal{V}_j^*}\right) \sqrt{2\frac{\log \frac{8}{\delta_{N,k}}}{n_k}} + \frac{56}{3}\sqrt{\tilde{g}}\frac{\log \frac{8}{\delta_{N,k}}}{n_k} \\
&\le \|\mu_j - \mu_i\| - \left(\sqrt{\mathcal{V}_i^*} + \sqrt{\mathcal{V}_j^*}\right) \sqrt{2\frac{\log \frac{8}{\delta_{N,k}}}{n_k}} - \frac{8}{3}\sqrt{\tilde{g}}\frac{\log \frac{8}{\delta_{N,k}}}{n_k}
\end{aligned} \qquad (17)$$
Finally, we gather Equations (16), and (17) to control $\mathbb{P}(A_{i,j} \cap B_i \cap B_j)$,

$$ 
\begin{aligned}
& \mathbb{P}(A_{i,j} \cap B_i \cap B_j) \\
\le & \mathbb{P}\left(\|\hat{\mu}_j - \hat{\mu}_i\| \le \left(\sqrt{\mathcal{V}_i^*} + \sqrt{\mathcal{V}_j^*}\right) \sqrt{2\frac{\log \frac{8}{\delta_{N,k}}}{n_k}} + \frac{56}{3}\sqrt{\tilde{g}}\frac{\log \frac{8}{\delta_{N,k}}}{n_k}\right) \\
\le & \mathbb{P}\left(\|\hat{\mu}_j - \hat{\mu}_i\| \le \|\mu_j - \mu_i\| - \left(\sqrt{\mathcal{V}_i^*} + \sqrt{\mathcal{V}_j^*}\right) \sqrt{2\frac{\log \frac{8}{\delta_{N,k}}}{n_k}} - \frac{8}{3}\sqrt{\tilde{g}}\frac{\log \frac{8}{\delta_{N,k}}}{n_k}\right) \\
\le & \frac{\delta_{N,k}}{2},
\end{aligned}
$$

where the last inequality results from Theorem A.4 applied with $\delta' = \frac{\delta_{N,k}}{2}$.

Finally, we come back to our previous bound on $\mathbb{P}(\mathcal{E}_{2,k})$ in Equation 15, to conclude that

$$ 
\begin{aligned}
\mathbb{P}(\mathcal{E}_{2,k}) & \le \sum_{\substack{i,j \in [N] \\ \mu_i \ne \mu_j}} \left( \mathbb{P}(A_{i,j} \cap B_i \cap B_j) + \frac{2\delta_{N,k}}{8} \right) \\
& \le \sum_{\substack{i,j \in [N] \\ \mu_i \ne \mu_j}} \left( \frac{\delta_{N,k}}{2} + \frac{\delta_{N,k}}{4} \right) \\
& \le \delta_k,
\end{aligned}
$$

where the final inequality follows from the definition of $\delta_{N,k} = \frac{\delta_k}{(N^2-N)}$ □

### A.3. Concentration inequalities

The design of the algorithm relies mostly on concentration inequalities for empirical KME, and empirical variances. For completeness, we recall in this subsection several inequalities whose proofs can be found in (Wolfer & Alquier, 2025).

**Lemma A.2 (Variance-aware empirical bound (Wolfer & Alquier, 2025)).** Let $g$ be a continuous, positive definite, characteristic, translation invariant, bounded kernel. Assume arm $i \in [N]$ was sampled $n \in \mathbb{N}$ times to calculate the empirical KME $\hat{\mu}_i$ and the empirical variance $\hat{V}_i$. Then it holds that

$$ \forall \delta' \in (0, 1]: \mathbb{P} \left( \left\{ \|\mu_i - \hat{\mu}_i\| \le \sqrt{2\hat{V}_i \frac{\log \frac{4}{\delta'}}{n}} + \frac{16}{3}\sqrt{\tilde{g}}\frac{\log \frac{4}{\delta'}}{n} \right\} \right) \ge 1 - \delta'. $$

For our application, we will prefer the following inequality, which follows directly from Theorem A.2, by application of the triangle inequality.

**Lemma A.3 (Variance-aware empirical bound for the distance of two arms).** Under the same assumptions as Theorem A.2

$$ \forall \delta' \in (0, 1]: \mathbb{P} (\|\hat{\mu}_j - \hat{\mu}_i\| - \|\mu_j - \mu_i\| \le \mathcal{B}) \ge 1 - \delta', $$

for

$$ \mathcal{B} := \left(\sqrt{\hat{V}_i} + \sqrt{\hat{V}_j}\right) \sqrt{2\frac{\log \frac{8}{\delta'}}{n}} + \frac{32}{3}\sqrt{\tilde{g}}\frac{\log \frac{8}{\delta'}}{n}. $$

**Lemma A.4.** Let $g$ be a continuous, positive definite and bounded kernel with supremum $\bar{g}$. Assume arms $i \in [N]$ was sampled $n$ times to calculate the empirical KME $\hat{\mu}_i$. Then it holds that for all $\delta \in (0, 1]$

$$ \mathbb{P}\left(\left|\|\hat{\mu}_j - \hat{\mu}_i\| - \|\mu_j - \mu_i\|\right| \le \mathcal{B}_*\right) \ge 1 - \delta, $$
for

$$ \mathcal{B}_* := (\sqrt{\mathcal{V}_i^*} + \sqrt{\mathcal{V}_j^*}) \sqrt{2\frac{\log \frac{4}{\delta}}{n}} + \frac{8}{3}\sqrt{\bar{g}}\frac{\log \frac{4}{\delta}}{n}. $$

**Lemma A.5** (Bound for empirical Variance (Wolfer & Alquier, 2025)). Let g be a continuous, positive definite, characteristic, translation invariant, bounded kernel. Assume arm $i \in [N]$ was sampled $n \in \mathbb{N}$ times to calculate the empirical variance $\hat{V}_i$. Let $b \in \{-1, 1\}$ Then it holds that

$$ \forall \delta \in (0, 1]: \mathbb{P} \left( b \left[ \sqrt{\hat{V}_i} - \sqrt{\mathcal{V}_i^*} \right] \le 2\sqrt{\frac{2\tilde{g}\log \frac{1}{\delta}}{n}} \right) \ge 1 - \delta. $$