# Active clustering with bandit feedback

Victor Thuot, Alexandra Carpentier, Christophe Giraud, Nicolas Verzelen

► To cite this version:

Victor Thuot, Alexandra Carpentier, Christophe Giraud, Nicolas Verzelen. Active clustering with bandit feedback. 2024. hal-04610780

HAL Id: hal-04610780

https://hal.science/hal-04610780

Preprint submitted on 14 Jun 2024

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 Attribution 4.0 International License
# Active clustering with bandit feedback

Thuot Victor

INRAE, Mistea, Institut Agro, Univ Montpellier, Montpellier, France.

email: victor.thuot@inrae.fr

Alexandra Carpentier

Institut für Mathematik, Universität Potsdam, Potsdam, Germany.

email: carpentier@uni-potsdam.de

Christophe Giraud

Université Paris-Saclay, Laboratoire de mathématiques d'Orsay, Orsay, France

email:christophe.giraud@universite-paris-saclay.fr

Nicolas Verzelen

INRAE, Mistea, Institut Agro, Univ Montpellier, Montpellier, France.

email: nicolas.verzelen@inrae.fr

## Abstract

We investigate the Active Clustering Problem (ACP). A learner interacts with an *N*-armed stochastic bandit with *d*-dimensional subGaussian feedback. There exists a hidden partition of the arms into *K* groups, such that arms within the same group, share the same mean vector. The learner's task is to uncover this hidden partition with the smallest budget - i.e., the least number of observation - and with a probability of error smaller than a prescribed constant $\delta$. In this paper, (i) we derive a non asymptotic lower bound for the budget, and (ii) we introduce the computationally efficient ACB algorithm, whose budget matches the lower bound in most regimes. We improve on the performance of a uniform sampling strategy. Importantly, contrary to the batch setting, we establish that there is no computation-information gap in the active setting.

## 1 Introduction

We consider a sequential and active clustering problem, the **Active Clustering Problem (ACP)**, introduced for instance in [36]. In this setting, there are *N* items, represented by a *d*-dimensional mean. At each time *t*, the learner chooses one of the items, and samples it - i.e., obtains a noisy evaluation of the *d*-dimensional mean that characterizes it - until termination of the sampling process at time $\tau$, which we call the budget, and which is chosen by the learner. We assume that the items are clustered into *K* unknown groups - and two items are in the same group if and only if their (unknown) means are the same. For a prescribed confidence level $\delta$, the aim of the learner is to recover perfectly this clustering, on an event of probability larger than $1 - \delta$, and with a final budget $\tau$ that is as small as possible. Clustering problems are ubiquitous in modern data analysis, and ACP arises e.g., in digital marketing, where accurate clustering of the customers is crucial for adapting recommendations to specific groups of customers, and where repeated feedback can be collected online. Since feedback collection is costly, the goal is to recover the clusters with a minimal number $\tau$ of feedback requests. See [36] for further motivations.
# Active clustering with bandit feedback

Thuot Victor

INRAE, Mistea, Institut Agro, Univ Montpellier, Montpellier, France.
email: victor.thuot@inrae.fr

Alexandra Carpentier

Institut für Mathematik, Universität Potsdam, Potsdam, Germany.
email: carpentier@uni-potsdam.de

Christophe Giraud

Université Paris-Saclay, Laboratoire de mathématiques d'Orsay, Orsay, France
email:christophe.giraud@universite-paris-saclay.fr

Nicolas Verzelen

INRAE, Mistea, Institut Agro, Univ Montpellier, Montpellier, France.
email: nicolas.verzelen@inrae.fr

## Abstract

We investigate the Active Clustering Problem (ACP). A learner interacts with an *N*-armed stochastic bandit with *d*-dimensional subGaussian feedback. There exists a hidden partition of the arms into *K* groups, such that arms within the same group, share the same mean vector. The learner's task is to uncover this hidden partition with the smallest budget - i.e., the least number of observation - and with a probability of error smaller than a prescribed constant *δ*. In this paper, (i) we derive a non asymptotic lower bound for the budget, and (ii) we introduce the computationally efficient ACB algorithm, whose budget matches the lower bound in most regimes. We improve on the performance of a uniform sampling strategy. Importantly, contrary to the batch setting, we establish that there is no computation-information gap in the active setting.

## 1 Introduction

We consider a sequential and active clustering problem, the **Active Clustering Problem (ACP)**, introduced for instance in [36]. In this setting, there are *N* items, represented by a *d*-dimensional mean. At each time *t*, the learner chooses one of the items, and samples it - i.e., obtains a noisy evaluation of the *d*-dimensional mean that characterizes it - until termination of the sampling process at time *τ*, which we call the budget, and which is chosen by the learner. We assume that the items are clustered into *K* unknown groups - and two items are in the same group if and only if their (unknown) means are the same. For a prescribed confidence level *δ*, the aim of the learner is to recover perfectly this clustering, on an event of probability larger than $1 - \delta$, and with a final budget *τ* that is as small as possible. Clustering problems are ubiquitous in modern data analysis, and ACP arises e.g., in digital marketing, where accurate clustering of the customers is crucial for adapting recommendations to specific groups of customers, and where repeated feedback can be collected online. Since feedback collection is costly, the goal is to recover the clusters with a minimal number *τ* of feedback requests. See [36] for further motivations.
In the low-dimensional setting, where $K$, $d$ are small, [36] proves that, when $\delta$ converges to 0, an asymptotic expected budget for perfectly recovering the groups is at most of the order

$$ \frac{\sigma^2}{\Delta_*^2} N \log(1/\delta), \qquad (1) $$

where $\Delta_*$ is the minimal Euclidean distance between the means, and $\sigma^2$ is the variance of the observations.

**High-dimensional setting.** We consider the high-dimensional setting, where $K$, $d$ can be large, possibly larger than $1/\delta$ or $N$ (for $d$). In the classical setting, where there is no repeated measurements on each item, clustering in high-dimension can be nearly impossible in practice. Indeed, in high-dimension, the best polynomial time algorithms require a very large separation of the means for successful clustering with no repeated measurements. This requirement has two origins. First, it is difficult to localize the means in high-dimension, making the clustering problem harder when $d$ becomes large compared to $N/K$. Second, a computation-information gap is conjectured (i) for clustering [23, 12] when $d$ is very large, and (ii) for estimation [10, 9] in some high-dimensional non-isotropic setting.

For instance, when there is no repeated measurement, for clustering a mixture of $N$ isotropic Gaussian with covariance $I_d$ and balanced size of the groups, in the high-dimensional setting where $d \ge N$ and $K \gg \log(N)$, low-degree polynomial algorithms require a separation at least $\Delta_*^2 \gtrsim \sigma^2 \sqrt{dK^2/N}$ (Theorem 1 in [12]), while a separation $\Delta_*^2 \gtrsim \sigma^2 \sqrt{dK \log(N)/N}$ is enough at the information level (Theorem 4 in [12]). This is a strong evidence of a computation-information gap for the problem of clustering isotropic Gaussian mixture in high dimension.

When repeated measurements are possible, let us consider the simple scheme where we sample $T$ times each item. This scheme corresponds to oracle-BOC sampling of [36], when the groups have similar sizes, and the clusters are equidistant. Sampling $T$ times each item is equivalent to shrinking the variance from $\sigma^2$ to $\sigma^2/T$, so, applying standard polynomial time algorithms [15] to the average values for each item, we can recover the clustering in polynomial time with confidence $\delta = 1/N$ when $T \gtrsim \frac{\sigma^2}{\Delta_*^2} \sqrt{dK^2/N}$. The total number of requests of this simple batch algorithm is then

$$ \tau = NT \gtrsim N + \frac{\sigma^2}{\Delta_*^2} \sqrt{dK^2 N}. \qquad (2) $$

This set of results raises two fundamental questions:

1. Can we improve upon the number of requests of the simple batch algorithm, by implementing a more careful sequential design strategy?

2. What is the minimal budget for perfect recovery in high-dimension, and is there a fundamental computation-information gap for clustering with repeated measurements?

**Contributions.** We provide an answer to these two fundamental questions.

1. First, we provide a polynomial-time algorithm that recovers exactly the clustering with probability higher than $1 - \delta$. In the balanced case (all groups have a similar size), it has an expected budget of order

$$ N + \frac{\sigma^2}{\Delta_*^2} \left[ N \log(N/\delta) + \sqrt{dKN \log(N/\delta)} \right], \qquad (3) $$

which outperforms the budget (2) required by the simple batch algorithm.

2. Second, we prove that the budget (3) is information-theoretical optimal, meaning that there is no computation-information gap for active clustering in high-dimension, contrary to the classical case with no repeated measurement.

Our results are non-asymptotic in $N$, $K$, $d$, and $\delta$, in order to account for high-dimensional phenomenon, and possible computational barriers –see the discussion for more details. Compared to the asymptotic minimal budget (1) obtained in [36] for $\delta \to 0$, an additional term pops up in the non-asymptotic minimal budget (3), which is dominant when $dK > N \log(N/\delta)$. Our algorithm is based on ideas related to sub-sampling, in order to localize in a more efficient way the mean of each group. The possibility of performing sub-sampling enables us to bypass combinatorial problems arising in clustering with no-repeated measurements. Our algorithm has a quasi-linear complexity, and is also order-optimal for all $\delta$, $N$, $K$, and $d$, for a broader family of problems defined below.

**Related literature in clustering.** The problem of clustering a mixture of subGaussian is a classical problem, which has lead to a large literature both in statistics and in machine learning [8, 35, 23,
In the low-dimensional setting, where $K$, $d$ are small, [36] proves that, when $\delta$ converges to 0, an asymptotic expected budget for perfectly recovering the groups is at most of the order

$$ \frac{\sigma^2}{\Delta_*^2} N \log(1/\delta), \qquad (1) $$

where $\Delta_*$ is the minimal Euclidean distance between the means, and $\sigma^2$ is the variance of the observations.

**High-dimensional setting.** We consider the high-dimensional setting, where $K$, $d$ can be large, possibly larger than $1/\delta$ or $N$ (for $d$). In the classical setting, where there is no repeated measurements on each item, clustering in high-dimension can be nearly impossible in practice. Indeed, in high-dimension, the best polynomial time algorithms require a very large separation of the means for successful clustering with no repeated measurements. This requirement has two origins. First, it is difficult to localize the means in high-dimension, making the clustering problem harder when $d$ becomes large compared to $N/K$. Second, a computation-information gap is conjectured (i) for clustering [23, 12] when $d$ is very large, and (ii) for estimation [10, 9] in some high-dimensional non-isotropic setting.

For instance, when there is no repeated measurement, for clustering a mixture of $N$ isotropic Gaussian with covariance $I_d$ and balanced size of the groups, in the high-dimensional setting where $d \ge N$ and $K \gg \log(N)$, low-degree polynomial algorithms require a separation at least $\Delta_*^2 \gtrsim \sigma^2 \sqrt{dK^2/N}$ (Theorem 1 in [12]), while a separation $\Delta_*^2 \gtrsim \sigma^2 \sqrt{dK \log(N)/N}$ is enough at the information level (Theorem 4 in [12]). This is a strong evidence of a computation-information gap for the problem of clustering isotropic Gaussian mixture in high dimension.

When repeated measurements are possible, let us consider the simple scheme where we sample $T$ times each item. This scheme corresponds to oracle-BOC sampling of [36], when the groups have similar sizes, and the clusters are equidistant. Sampling $T$ times each item is equivalent to shrinking the variance from $\sigma^2$ to $\sigma^2/T$, so, applying standard polynomial time algorithms [15] to the average values for each item, we can recover the clustering in polynomial time with confidence $\delta = 1/N$ when $T \gtrsim \frac{\sigma^2}{\Delta_*^2} \sqrt{dK^2/N}$. The total number of requests of this simple batch algorithm is then

$$ \tau = NT \gtrsim N + \frac{\sigma^2}{\Delta_*^2} \sqrt{dK^2 N}. \qquad (2) $$

This set of results raises two fundamental questions:

1. Can we improve upon the number of requests of the simple batch algorithm, by implementing a more careful sequential design strategy?

2. What is the minimal budget for perfect recovery in high-dimension, and is there a fundamental computation-information gap for clustering with repeated measurements?

**Contributions.** We provide an answer to these two fundamental questions.

1. First, we provide a polynomial-time algorithm that recovers exactly the clustering with probability higher than $1 - \delta$. In the balanced case (all groups have a similar size), it has an expected budget of order

$$ N + \frac{\sigma^2}{\Delta_*^2} \left[ N \log(N/\delta) + \sqrt{dKN \log(N/\delta)} \right], \qquad (3) $$

which outperforms the budget (2) required by the simple batch algorithm.

2. Second, we prove that the budget (3) is information-theoretical optimal, meaning that there is no computation-information gap for active clustering in high-dimension, contrary to the classical case with no repeated measurement.

Our results are non-asymptotic in $N$, $K$, $d$, and $\delta$, in order to account for high-dimensional phenomenon, and possible computational barriers –see the discussion for more details. Compared to the asymptotic minimal budget (1) obtained in [36] for $\delta \to 0$, an additional term pops up in the non-asymptotic minimal budget (3), which is dominant when $dK > N \log(N/\delta)$. Our algorithm is based on ideas related to sub-sampling, in order to localize in a more efficient way the mean of each group. The possibility of performing sub-sampling enables us to bypass combinatorial problems arising in clustering with no-repeated measurements. Our algorithm has a quasi-linear complexity, and is also order-optimal for all $\delta$, $N$, $K$, and $d$, for a broader family of problems defined below.

**Related literature in clustering.** The problem of clustering a mixture of subGaussian is a classical problem, which has lead to a large literature both in statistics and in machine learning [8, 35, 23,
26, 11, 29, 15, 13, 5, 21, 33, 31, 24, 9]. In low-dimension and for large values of N, state-of-the art polynomial-time procedures for recovering the groups have been introduced by [24], and are based on generalisation of higher moments methods – see also [11, 20]. In high-dimension, the best known conditions for exact reconstruction in polynomial-time are based on an SDP relaxation of K-means [28, 15]. For $K = 2$, a simple Lloyd algorithm achieves perfect recovery at the information level [27], thereby establishing the absence of computation-information gap for $K = 2$. For larger $K$, [23] conjectures a computation-information gap in high-dimension, and [12] exhibits a low-degree computational barrier for the clustering of a mixture of isotropic Gaussians, when $d \ge N$. Some computation-information gaps have also been shown for Statistical-Query algorithms for learning mixture of non-isotropic Gaussian, with unknown covariance, in moderately high-dimension –see[10] and [9]. In the sequel, we refer to clustering with no repeated measurements as batch clustering.

**Sequential literature related to ACP.** When turning to the sequential learning literature, the ACP belongs to the family of pure exploration problems in the sequential active learning framework. An iconic such problem is the best-arm identification problem – see [16] for a survey. In this stream of literature, the Thresholding Bandit Problem (TBP) is quite related – see [3, 4, 25]. This is a specific instance of our setting in dimension $d = 1$ and for two groups, i.e., $K = 2$. In this active binary classification problem, the learner aims at finding the arms that have a mean larger than a given threshold (here $d = 1$), and to divide them in $K = 2$ groups. Note that [18] propose a generalisation of these ideas to multiple groups, albeit still in dimension 1. The optimal asymptotic budget $\tau$ for perfect recovery in the TBP is $\Delta_*^{-2}N \log(1/\delta)$ when $\delta$ goes to 0, and there are no computational gaps, see [34] for state of the art results on TBP.

The ACP, first introduced in [36], can be seen as a generalisation of the TBP in dimension $d$. This generalisation is highly non-trivial: subtle phenomenons make clustering problems with $d \ge 2$ very different from clustering in dimension 1.

[36] provides an algorithm called BOC, which perfectly recovers the groups with probability higher than $1 - \delta$, and which has an expected budget at most of the order (1) in the asymptotic regime where $\delta$ goes to zero. Note that this rate is reminiscent of the TBP (where $d = 1, K = 2$). A closer look at the proofs in [36] exhibits an exponential dependence of second-order terms (in $\delta$) on $K, d$ so that BOC - or at least its current analysis - is effective only in the asymptotic regime, when $K, d$ are considered as being constants. In fact, since the oracle version of BOC samples equally all the arms when the clusters are balanced and equidistant, the BOC budget in this case is at least (2) in high-dimension [12], which is suboptimal. Our non-asymptotic analysis allows to recover the shape of the optimal budget in the so-called high-dimensional regimes where $d$ or $K$ are not considered as constants.

A somewhat related problem was studied in [37], in the Stochastic Block Model within the fixed-budget setting. To extract hidden structure, the interaction between pairs of nodes can be sampled several times, in an active manner. The setting is however quite distinct from our work, and is also focusing on the asymptotic regime where $\delta$ goes to 0. In the paper [1], the related problem of clustering items based on binary feedback is studied - but therein, the feedback corresponds to a single coordinate of a chosen vector. In our work, we observe the full $d$-dimensional vector at each time, so that the settings differ. Finally, it is worth mentioning that our problem should not be confused with that of online clustering, for example studied in [7].

**Outline.** We formally introduce the ACP in Section 2. An information-theoretical lower bound on the minimal budget for exact recovery is established in Section 3. We introduce and analyze our procedure ACB in Section 4. Numerical experiments are provided in Section 5. All the results are discussed in Section 6.

## 2 Setting and notation

**The sequential and active setting.** We consider a set of $N$ arms, indexed by $[N]$. Each arm $a \in [N]$ is associated to an unknown probability distribution $\nu_a$ on $\mathbb{R}^d$. At each time $t$, the learner chooses an arm $A_t \in [N]$ based on the past observations. Conditionally on the chosen arm $A_t$, she receives from the environment a random observation $X_t \in \mathbb{R}^d$, distributed as $\nu_{A_t}$.

For each arm $a \in [N]$, we write $\mu_a \in \mathbb{R}^d$ for the mean of the distribution $\nu_a$. Both in the context of multi-armed bandits, and in the context of clustering, it is common to assume that the distributions are subGaussian.
26, 11, 29, 15, 13, 5, 21, 33, 31, 24, 9]. In low-dimension and for large values of N, state-of-the-art polynomial-time procedures for recovering the groups have been introduced by [24], and are based on generalisation of higher moments methods – see also [11, 20]. In high-dimension, the best known conditions for exact reconstruction in polynomial-time are based on an SDP relaxation of K-means [28, 15]. For $K = 2$, a simple Lloyd algorithm achieves perfect recovery at the information level [27], thereby establishing the absence of computation-information gap for $K = 2$. For larger $K$, [23] conjectures a computation-information gap in high-dimension, and [12] exhibits a low-degree computational barrier for the clustering of a mixture of isotropic Gaussians, when $d \ge N$. Some computation-information gaps have also been shown for Statistical-Query algorithms for learning mixture of non-isotropic Gaussian, with unknown covariance, in moderately high-dimension –see[10] and [9]. In the sequel, we refer to clustering with no repeated measurements as batch clustering.

**Sequential literature related to ACP.** When turning to the sequential learning literature, the ACP belongs to the family of pure exploration problems in the sequential active learning framework. An iconic such problem is the best-arm identification problem – see [16] for a survey. In this stream of literature, the Thresholding Bandit Problem (TBP) is quite related – see [3, 4, 25]. This is a specific instance of our setting in dimension $d = 1$ and for two groups, i.e., $K = 2$. In this active binary classification problem, the learner aims at finding the arms that have a mean larger than a given threshold (here $d = 1$), and to divide them in $K = 2$ groups. Note that [18] propose a generalisation of these ideas to multiple groups, albeit still in dimension 1. The optimal asymptotic budget $\tau$ for perfect recovery in the TBP is $\Delta_*^{-2}N \log(1/\delta)$ when $\delta$ goes to 0, and there are no computational gaps, see [34] for state of the art results on TBP.

The ACP, first introduced in [36], can be seen as a generalisation of the TBP in dimension $d$. This generalisation is highly non-trivial: subtle phenomenons make clustering problems with $d \ge 2$ very different from clustering in dimension 1.

[36] provides an algorithm called BOC, which perfectly recovers the groups with probability higher than $1 - \delta$, and which has an expected budget at most of the order (1) in the asymptotic regime where $\delta$ goes to zero. Note that this rate is reminiscent of the TBP (where $d = 1, K = 2$). A closer look at the proofs in [36] exhibits an exponential dependence of second-order terms (in $\delta$) on $K, d$ so that BOC - or at least its current analysis - is effective only in the asymptotic regime, when $K, d$ are considered as being constants. In fact, since the oracle version of BOC samples equally all the arms when the clusters are balanced and equidistant, the BOC budget in this case is at least (2) in high-dimension [12], which is suboptimal. Our non-asymptotic analysis allows to recover the shape of the optimal budget in the so-called high-dimensional regimes where $d$ or $K$ are not considered as constants.

A somewhat related problem was studied in [37], in the Stochastic Block Model within the fixed-budget setting. To extract hidden structure, the interaction between pairs of nodes can be sampled several times, in an active manner. The setting is however quite distinct from our work, and is also focusing on the asymptotic regime where $\delta$ goes to 0. In the paper [1], the related problem of clustering items based on binary feedback is studied - but therein, the feedback corresponds to a single coordinate of a chosen vector. In our work, we observe the full $d$-dimensional vector at each time, so that the settings differ. Finally, it is worth mentioning that our problem should not be confused with that of online clustering, for example studied in [7].

**Outline.** We formally introduce the ACP in Section 2. An information-theoretical lower bound on the minimal budget for exact recovery is established in Section 3. We introduce and analyze our procedure ACB in Section 4. Numerical experiments are provided in Section 5. All the results are discussed in Section 6.

## 2 Setting and notation

**The sequential and active setting.** We consider a set of $N$ arms, indexed by $[N]$. Each arm $a \in [N]$ is associated to an unknown probability distribution $\nu_a$ on $\mathbb{R}^d$. At each time $t$, the learner chooses an arm $A_t \in [N]$ based on the past observations. Conditionally on the chosen arm $A_t$, she receives from the environment a random observation $X_t \in \mathbb{R}^d$, distributed as $\nu_{A_t}$.

For each arm $a \in [N]$, we write $\mu_a \in \mathbb{R}^d$ for the mean of the distribution $\nu_a$. Both in the context of multi-armed bandits, and in the context of clustering, it is common to assume that the distributions are subGaussian.
**Assumption 2.1** (σ-subGaussian arm observations). For any arm $a \in [N]$, we assume that there exists a symmetric $d \times d$ matrix $\Sigma_a$ such that, (i) $\max_{a \in [N]} ||\Sigma_a||_{op} \le \sigma^2$, where $||\cdot||_{op}$ is the operator norm; (ii) the coordinates $(E_i)$ of $E = \Sigma_a^{-1/2}[X - \mu_a]$ are independent and fulfills $E[\exp(tE_i)] \le \exp(t^2/2)$ for all $t \in \mathbb{R}$.

**Remark 2.2.** This assumption encompasses the emblematic settings where the data are Gaussian, and where the data are bounded. If the distributions $(\nu_a)$ are Gaussian, then Assumption 2.1 holds by e.g., choosing $\Sigma_a$'s to be the covariance matrices, and associate $\sigma$. If the distributions $(\nu_a)_a$ are such that the coordinates are independent and lie in $[0, 1]$, the collection $(\nu_a)$ is 1/4-subGaussian.

**The Active Clustering Problem.** As for the vanilla clustering problem, our objective is to partition the set of arms into groups of arms that share the same expectation $\mu_a$. For this purpose, we make the following modeling assumption.

**Assumption 2.3** (Hidden partition $G^*$ of the arms into $K$ groups). Consider $N \ge K \ge 1$. We assume that there exists a partition $G^* = \{G_1^*, \dots, G_K^*\}$ of $[N]$ into $K$ groups such that any two arms $a$ and $b$ are in the same group if and only if they share the same expectation $(\mu_a = \mu_b)$. For notation purpose, we introduce the vectors $\mu(1), \dots, \mu(K) \in \mathbb{R}^p$ such $\mu(k)$ corresponds to the common expectation in $G_k^*$. Henceforth, $\mu(k)$ is called the center of the group $G_k^*$.

In ACP, the goal of the learner is to uncover the true partition $G^*$ of the arms, while using as few samples as possible. The learner samples arms sequentially and, when reaching some stopping time $\tau$, she returns a partition $\hat{G}$ of $[N]$ into $K$ groups, which should ideally be equal to $G^*$. More precisely, let $\pi$ be an algorithm for the active clustering problem, also called the strategy of the learner. We write $(\mathcal{F}_t)_{t \ge 0}$ for the filtration $\mathcal{F}_t = \sigma(A_1, X_1, \dots, A_t, X_t)$. A strategy $\pi$ consists on three rules:

* A selection rule that chooses the next arm $A_t$ to sample, based on the previously sampled arms and observations; $A_t$ is $\mathcal{F}_t$-measurable.

* A stopping rule that controls when the learner stops sampling the arms, and which quantifies the budget of the strategy. This is modeled by a stopping time $\tau$ with respect to the filtration $(\mathcal{F}_t)_{t \ge 0}$.

* A recommendation rule. Once the stopping time $\tau$ is reached, the learner outputs an estimated partition of the arms $\hat{G}$. This partition is $\mathcal{F}_\tau$-measurable.

For an environment $\nu$ and an algorithm $\pi$, we write $\mathbb{P}_{\pi,\nu}$ for the probability induced by the interaction between the algorithm $\pi$ and the environment.

In this paper, we aim at exactly recovering the partition $G^*$ in the fixed confidence setting. While the partition $G^*$ is identifiable, the groups $(G_k^*)$ and the means $\mu(k)$ are identifiable only up to relabelling, i.e., up to a permutation of $[K]$. We denote by $G \sim G'$ two equivalent partitions of $[N]$, i.e., two partitions such that, for some permutation $\rho$ of $[K]$, $G_k = G_{\rho(k)}$ for all $k \in [K]$. For a fixed confidence level $\delta \in (0, 1)$, and a given set of environments $\mathcal{E}$, a strategy $\pi = \pi(\delta)$ fulfilling

$$ \mathbb{P}_{\pi, \nu}(\hat{G} \sim G^*) \ge 1 - \delta, \quad (4) $$

is said to be $\delta$-PAC (probably approximately correct) on $\mathcal{E}$. We write $\Pi(\delta, \mathcal{E})$ for the family of such $\delta$-PAC strategies for the ACP on $\mathcal{E}$. Our aim is to design a $\delta$-PAC algorithm, whose budget $\tau$ is as small as possible. For a family of environments $\mathcal{E}$, the optimal worst case (average) budget $T^*(\delta, \mathcal{E})$ is defined as

$$ T^*(\delta, \mathcal{E}) = \inf_{\pi \in \Pi(\delta, \mathcal{E})} \sup_{\nu \in \mathcal{E}} \mathbb{E}_{\pi, \nu}[\tau]. \quad (5) $$

In order to introduce relevant sets of environments $\mathcal{E}$, we introduce two quantities that characterize the difficulty of a clustering problem, let it be batch or active. First, we consider the minimal Euclidean distance between two distinct group centers

$$ \Delta_* = \Delta_*(\nu) = \min_{k \neq k'} ||\mu(k) - \mu(k')|| > 0. \quad (6) $$

Intuitively, the smaller $\Delta_*$, the more difficult it is to distinguish the groups and to recover the partition $G^*$. This quantity naturally appears in most clustering works in the batch setting [8, 35, 15]. Besides, we denote $\theta_*$ the balancedness of $G^*$, that is the proportion of arms in the smallest cluster

$$ \theta_* = \min_{k \in [K]} \frac{|G_k^*|}{N} \in \left[ \frac{1}{N}, \frac{1}{K} \right]. \quad (7) $$
**Assumption 2.1 (σ-subGaussian arm observations).** For any arm $a \in [N]$, we assume that there exists a symmetric $d \times d$ matrix $\Sigma_a$ such that, (i) $\max_{a \in [N]} ||\Sigma_a||_{op} \le \sigma^2$, where $||\cdot||_{op}$ is the operator norm; (ii) the coordinates $(E_i)$ of $E = \Sigma_a^{-1/2}[X - \mu_a]$ are independent and fulfills $E[\exp(tE_i)] \le \exp(t^2/2)$ for all $t \in \mathbb{R}$.

**Remark 2.2.** This assumption encompasses the emblematic settings where the data are Gaussian, and where the data are bounded. If the distributions $(\nu_a)$ are Gaussian, then Assumption 2.1 holds by e.g., choosing $\Sigma_a$'s to be the covariance matrices, and associate $\sigma$. If the distributions $(\nu_a)_a$ are such that the coordinates are independent and lie in $[0, 1]$, the collection $(\nu_a)$ is 1/4-subGaussian.

**The Active Clustering Problem.** As for the vanilla clustering problem, our objective is to partition the set of arms into groups of arms that share the same expectation $\mu_a$. For this purpose, we make the following modeling assumption.

**Assumption 2.3 (Hidden partition $G^*$ of the arms into $K$ groups).** Consider $N \ge K \ge 1$. We assume that there exists a partition $G^* = \{G_1^*, \dots, G_K^*\}$ of $[N]$ into $K$ groups such that any two arms $a$ and $b$ are in the same group if and only if they share the same expectation $(\mu_a = \mu_b)$. For notation purpose, we introduce the vectors $\mu(1), \dots, \mu(K) \in \mathbb{R}^p$ such $\mu(k)$ corresponds to the common expectation in $G_k^*$. Henceforth, $\mu(k)$ is called the center of the group $G_k^*$.

In ACP, the goal of the learner is to uncover the true partition $G^*$ of the arms, while using as few samples as possible. The learner samples arms sequentially and, when reaching some stopping time $\tau$, she returns a partition $\hat{G}$ of $[N]$ into $K$ groups, which should ideally be equal to $G^*$. More precisely, let $\pi$ be an algorithm for the active clustering problem, also called the strategy of the learner. We write $(\mathcal{F}_t)_{t \ge 0}$ for the filtration $\mathcal{F}_t = \sigma(A_1, X_1, \dots, A_t, X_t)$. A strategy $\pi$ consists on three rules:

* A selection rule that chooses the next arm $A_t$ to sample, based on the previously sampled arms and observations; $A_t$ is $\mathcal{F}_t$-measurable.

* A stopping rule that controls when the learner stops sampling the arms, and which quantifies the budget of the strategy. This is modeled by a stopping time $\tau$ with respect to the filtration $(\mathcal{F}_t)_{t \ge 0}$.

* A recommendation rule. Once the stopping time $\tau$ is reached, the learner outputs an estimated partition of the arms $\hat{G}$. This partition is $\mathcal{F}_\tau$-measurable.

For an environment $\nu$ and an algorithm $\pi$, we write $\mathbb{P}_{\pi,\nu}$ for the probability induced by the interaction between the algorithm $\pi$ and the environment.

In this paper, we aim at exactly recovering the partition $G^*$ in the fixed confidence setting. While the partition $G^*$ is identifiable, the groups $(G_k^*)$ and the means $\mu(k)$ are identifiable only up to relabelling, i.e., up to a permutation of $[K]$. We denote by $G \sim G'$ two equivalent partitions of $[N]$, i.e., two partitions such that, for some permutation $\rho$ of $[K]$, $G_k = G_{\rho(k)}$ for all $k \in [K]$. For a fixed confidence level $\delta \in (0, 1)$, and a given set of environments $\mathcal{E}$, a strategy $\pi = \pi(\delta)$ fulfilling

$$ \mathbb{P}_{\pi, \nu}(\hat{G} \sim G^*) \ge 1 - \delta, \quad (4) $$

is said to be $\delta$-PAC (probably approximately correct) on $\mathcal{E}$. We write $\Pi(\delta, \mathcal{E})$ for the family of such $\delta$-PAC strategies for the ACP on $\mathcal{E}$. Our aim is to design a $\delta$-PAC algorithm, whose budget $\tau$ is as small as possible. For a family of environments $\mathcal{E}$, the optimal worst case (average) budget $T^*(\delta, \mathcal{E})$ is defined as

$$ T^*(\delta, \mathcal{E}) = \inf_{\pi \in \Pi(\delta, \mathcal{E})} \sup_{\nu \in \mathcal{E}} \mathbb{E}_{\pi, \nu}[\tau]. \quad (5) $$

In order to introduce relevant sets of environments $\mathcal{E}$, we introduce two quantities that characterize the difficulty of a clustering problem, let it be batch or active. First, we consider the minimal Euclidean distance between two distinct group centers

$$ \Delta_* = \Delta_*(\nu) = \min_{k \neq k'} ||\mu(k) - \mu(k')|| > 0. \quad (6) $$

Intuitively, the smaller $\Delta_*$, the more difficult it is to distinguish the groups and to recover the partition $G^*$. This quantity naturally appears in most clustering works in the batch setting [8, 35, 15]. Besides, we denote $\theta_*$ the balancedness of $G^*$, that is the proportion of arms in the smallest cluster

$$ \theta_* = \min_{k \in [K]} \frac{|G_k^*|}{N} \in \left[ \frac{1}{N}, \frac{1}{K} \right]. \quad (7) $$
When $\theta_* = 1/K$, all the groups $G_k^*$ share the same size, and the partition is balanced.

Consider $\Delta > 0$, and $\theta > 0$, we define the set $\mathcal{E}(\Delta, \theta, \sigma, N, K, d)$ as the family of environments with $N$ arms, divided into $K$ groups as in Assumption 2.3, with a minimal gap $\Delta_*$ at least $\Delta$, a balancedness $\theta_*$ at least $\theta$, and with $d$-dimensional observations that are $\sigma$-subGaussian – see Assumption 2.1. Our main aim is to craft polynomial-time algorithms that attain the optimal worst case budget $T^*(\delta, \mathcal{E}(\Delta, \theta, \sigma, N, K, d))$, and to characterize this optimal worst-case budget.

### 3 Lower bound on the budget

We start by establishing a lower bound for the expected budget of any $\delta$-PAC algorithm over $\mathcal{E}(\Delta, \theta, \sigma, N, K, d)$.

**Theorem 3.1.** There exists a numerical constant $c > 0$, such that we have for any $\sigma > 0$, any $\Delta > 0$, any $d \ge 1$, any $\theta > 0$, any $\delta \in (0, 1/12)$, and any $N \ge 2K \ge 4$ such that $\mathcal{E}(\Delta, \theta, \sigma, N, K, d) \ne \emptyset$

$$T^*(\delta, \mathcal{E}(\Delta, \theta, \sigma, N, K, d)) \ge cN + c \frac{\sigma^2}{\Delta^2} \left[ N \log \left( \frac{N}{\delta} \right) + \sqrt{dKN \log \left( \frac{N}{\delta} \right)} \right]. \quad (8)$$

The lower bound in (8) involves three different terms. As in any pure exploration problem, the first term $N$ is necessary because, when $\tau \le N/2$, then the label of at least one arm has to be guessed randomly inducing a constant probability of error for the exact clustering. This term is only relevant for very large $\Delta$ and is not discussed further. The second term is the largest in the low-dimensional regime where $d \le N \log(N/\delta)/K$, whereas the third one is the largest in the high-dimensional regime where $d \ge N \log(N/\delta)/K$. This dichotomy between low-dimensional and high-dimensional clustering problems also occurs in the batch problem. Together with the results of the next section, we will establish that it is intrinsic here –see the discussion and the proof sketch for further details. Note that (8) does not depend on $\theta$: we establish (8) for environments where $\theta_*$ is close to $1/K$, that is for balanced partitions. In fact, the total budget of our procedures ACB and ACB* - see below - do not depend on $\theta_*$ except for extremely unbalanced partitions (very small $\theta_*$) so that the lower bound is tight even for mildly unbalanced partitions.

*Sketch of proof of Theorem 3.1.* The first two terms in the lower bound (8) – resp. $\frac{\sigma^2}{\Delta^2} N \log(\frac{N}{\delta})$ and $\frac{\sigma^2}{\Delta^2} \sqrt{dKN \log(\frac{N}{\delta})}$ – are proved separately in Lemmas B.1 and B.2. Regarding the first term, we first observe that it depends neither on $d$, nor on $K$, nor on $\theta$. For the sake of this sketch, we can therefore restrict ourselves to a one-dimensional ($d=1$) multi-armed bandit setting where each arm has $a \in [N]$ has either mean $\mu_a = 0$ or $\mu_a = \Delta$, so that $K=2$. For this simplified toy problem, recovering the partition $G^*$ is equivalent to a Thresholding Bandit Problem (TBP), where the goal is to find the set of arms whose mean is higher or equal to $\Delta$. By building upon some ideas introduced in [6], we establish the lower bound $\frac{\sigma^2}{\Delta^2} N \log(\frac{N}{\delta})$. Note that one may easily interpret this quantity using the fact that, for a specific arm, deciphering whether the mean of a specific arm is 0 or $\Delta$ with probability $1 - \delta/N$, one needs to sample it at least $\frac{\sigma^2}{\Delta^2} \log(\frac{N}{\delta})$ times.

The proof of the second term is both more challenging and more innovative. Again, for the purpose of this sketch, let us assume that $K=2$ and $\theta_* = 1/2$. We use a Bayesian approach by putting a Gaussian prior distribution on $\mu(1)$ with variance $d^{-1/2}\Delta I_d$ and by fixing $\mu(2) = -\mu(1)$ so that, with high probability, $\|\mu(2) - \mu(1)\| \ge \Delta$. Introducing this prior distribution on $\mathbb{R}^d$ is instrumental to recover the dependency of the budget on the dimension $d$ of the problem. First, we use the symmetry of the problem to show that the optimal budget is achieved by a strategy $\pi$ which, in expectation, samples all the arms uniformly. Then, we use a series of reduction by first noting that identifying the group of any node $a$ is, in some sense, at least as difficult, as the supervised problem where we would know the group of all the arms, except that of $a$. In turn, we show that tackling this active supervised problem with a uniform strategy $\pi$ is as difficult as tackling a batch supervised learning problem where each arm is sampled $\tau/N$ times. Finally, we craft an impossibility result for the latter problem. We emphasize that there is no computational restriction here, so that the lower bound for uniform sampling strategies is (8), and not the rate (2) which relates to polynomial-time algorithms [12]. $\square$

### 4 ACB and Upper bound on the budget

To introduce the main ideas underlying our active clustering algorithm, we first assume in the next subsection that $\Delta, \theta, \sigma, N, K$ and $d$ are known quantities, and we construct an algorithm, ACB, that
When $\theta_* = 1/K$, all the groups $G_k^*$ share the same size, and the partition is balanced.

Consider $\Delta > 0$, and $\theta > 0$, we define the set $\mathcal{E}(\Delta, \theta, \sigma, N, K, d)$ as the family of environments with $N$ arms, divided into $K$ groups as in Assumption 2.3, with a minimal gap $\Delta_*$ at least $\Delta$, a balancedness $\theta_*$ at least $\theta$, and with $d$-dimensional observations that are $\sigma$-subGaussian – see Assumption 2.1. Our main aim is to craft polynomial-time algorithms that attain the optimal worst case budget $T^*(\delta, \mathcal{E}(\Delta, \theta, \sigma, N, K, d))$, and to characterize this optimal worst-case budget.

### 3 Lower bound on the budget

We start by establishing a lower bound for the expected budget of any $\delta$-PAC algorithm over $\mathcal{E}(\Delta, \theta, \sigma, N, K, d)$.

**Theorem 3.1.** There exists a numerical constant $c > 0$, such that we have for any $\sigma > 0$, any $\Delta > 0$, any $d \ge 1$, any $\theta > 0$, any $\delta \in (0, 1/12)$, and any $N \ge 2K \ge 4$ such that $\mathcal{E}(\Delta, \theta, \sigma, N, K, d) \ne \emptyset$

$$T^*(\delta, \mathcal{E}(\Delta, \theta, \sigma, N, K, d)) \ge cN + c \frac{\sigma^2}{\Delta^2} \left[ N \log \left( \frac{N}{\delta} \right) + \sqrt{dKN \log \left( \frac{N}{\delta} \right)} \right]. \quad (8)$$

The lower bound in (8) involves three different terms. As in any pure exploration problem, the first term $N$ is necessary because, when $\tau \le N/2$, then the label of at least one arm has to be guessed randomly inducing a constant probability of error for the exact clustering. This term is only relevant for very large $\Delta$ and is not discussed further. The second term is the largest in the low-dimensional regime where $d \le N \log(N/\delta)/K$, whereas the third one is the largest in the high-dimensional regime where $d \ge N \log(N/\delta)/K$. This dichotomy between low-dimensional and high-dimensional clustering problems also occurs in the batch problem. Together with the results of the next section, we will establish that it is intrinsic here –see the discussion and the proof sketch for further details. Note that (8) does not depend on $\theta$: we establish (8) for environments where $\theta_*$ is close to $1/K$, that is for balanced partitions. In fact, the total budget of our procedures ACB and ACB* - see below - do not depend on $\theta_*$ except for extremely unbalanced partitions (very small $\theta_*$) so that the lower bound is tight even for mildly unbalanced partitions.

*Sketch of proof of Theorem 3.1.* The first two terms in the lower bound (8) – resp. $\frac{\sigma^2}{\Delta^2} N \log(\frac{N}{\delta})$ and $\frac{\sigma^2}{\Delta^2} \sqrt{dKN \log(\frac{N}{\delta})}$ – are proved separately in Lemmas B.1 and B.2. Regarding the first term, we first observe that it depends neither on $d$, nor on $K$, nor on $\theta$. For the sake of this sketch, we can therefore restrict ourselves to a one-dimensional ($d=1$) multi-armed bandit setting where each arm has $a \in [N]$ has either mean $\mu_a = 0$ or $\mu_a = \Delta$, so that $K=2$. For this simplified toy problem, recovering the partition $G^*$ is equivalent to a Thresholding Bandit Problem (TBP), where the goal is to find the set of arms whose mean is higher or equal to $\Delta$. By building upon some ideas introduced in [6], we establish the lower bound $\frac{\sigma^2}{\Delta^2} N \log(\frac{N}{\delta})$. Note that one may easily interpret this quantity using the fact that, for a specific arm, deciphering whether the mean of a specific arm is 0 or $\Delta$ with probability $1 - \delta/N$, one needs to sample it at least $\frac{\sigma^2}{\Delta^2} \log(\frac{N}{\delta})$ times.

The proof of the second term is both more challenging and more innovative. Again, for the purpose of this sketch, let us assume that $K=2$ and $\theta_* = 1/2$. We use a Bayesian approach by putting a Gaussian prior distribution on $\mu(1)$ with variance $d^{-1/2} \Delta I_d$ and by fixing $\mu(2) = -\mu(1)$ so that, with high probability, $\|\mu(2) - \mu(1)\| \ge \Delta$. Introducing this prior distribution on $\mathbb{R}^d$ is instrumental to recover the dependency of the budget on the dimension $d$ of the problem. First, we use the symmetry of the problem to show that the optimal budget is achieved by a strategy $\pi$ which, in expectation, samples all the arms uniformly. Then, we use a series of reduction by first noting that identifying the group of any node $a$ is, in some sense, at least as difficult, as the supervised problem where we would know the group of all the arms, except that of $a$. In turn, we show that tackling this active supervised problem with a uniform strategy $\pi$ is as difficult as tackling a batch supervised learning problem where each arm is sampled $\tau/N$ times. Finally, we craft an impossibility result for the latter problem. We emphasize that there is no computational restriction here, so that the lower bound for uniform sampling strategies is (8), and not the rate (2) which relates to polynomial-time algorithms [12]. $\square$

### 4 ACB and Upper bound on the budget

To introduce the main ideas underlying our active clustering algorithm, we first assume in the next subsection that $\Delta, \theta, \sigma, N, K$ and $d$ are known quantities, and we construct an algorithm, ACB, that
is $\delta$-PAC for environments such that $\Delta_* \le \Delta$ and $\theta_* \le \theta$. We introduce our main algorithm, ACB*, adaptive to $\Delta_*$ and $\theta_*$ in Subsection 4.2.

## 4.1 Warm-up: optimal active clustering with known $\Delta$, $\theta$

The main recipe of ACB is to first identify a set $\hat{S}$ of $K$ arms, which are representative of each group, and then, to classify all the arms based on a precise estimation of the means of the $K$ arms in $\hat{S}$. The ACB algorithm built then on two subroutines:

1. SRI (Sequential Representatives identification), which constructs a set $\hat{S}$ that contains, with high probability, exactly one arm for each group, called the representatives of each group. To construct $\hat{S}$, we use a sequential elimination technique, combined with high-dimensional two-sample tests.

2. ADC (Active Distance-based classification), which computes precise estimates of the means of the arms in $\hat{S}$, and classifies the remaining arms based on minimum estimated distance to the representatives.

**Estimating distances.** In order to detect whether two arms $a$ and $b$ are in the same group, a key ingredient for both SRI and ADC is to get a good estimation of the square distance $\|\mu_a - \mu_b\|^2$ between the means. Computing the empirical means $\hat{\mu}_a$ and $\hat{\mu}_b$ of collected samples of $a$ and $b$, we can estimate $\|\mu_a - \mu_b\|^2$ by $\|\hat{\mu}_a - \hat{\mu}_b\|^2$. Yet, this simple estimator suffers from an unknown bias depending on the noise covariance matrix. This issue can be circumvented in active sampling, by:

(i) computing independent empirical means $\hat{\mu}_a$, $\hat{\mu}'_a$, and $\hat{\mu}_b$, $\hat{\mu}'_b$ for the arms $a$ and $b$, based on repeated measurements,

(ii) estimating $\|\mu_a - \mu_b\|^2$ with the unbiased estimator $\hat{d}_{ab}^2 = \langle \hat{\mu}_a - \hat{\mu}_b, \hat{\mu}'_a - \hat{\mu}'_b \rangle$.

**SRI subroutine (Sequential Representative Identification).** The core idea underlying the SRI subroutine is to start from a set $S = \{a_0\}$ made of a single arm, chosen uniformly at random, and then to successively sample new arms $a$, and to add them to $S$, if they pass a sequence of tests ensuring that $a$ is not represented in $S$ with high-probability. The sequence of tests checks if $a$ is already represented in $S$, i.e., if $\min_{b \in S} \|\mu_a - \mu_b\|^2 = 0$, by multiplying the condition $\min_{b \in S} \hat{d}_{ab}^2 \le \Delta^2/2$, with a sequence of estimators $\hat{d}_{ab}^2$ based on increasing sample sizes, ensuring increasing confidence. It is based on the call of the REPRESENTEDTEST subroutine described below, where empirical_mean($a, n$) refers to the action of sampling $n$ times the $a$-th arm, and computing the empirical mean of the collected samples. This action is performed twice to compute $\hat{\mu}_a$ and $\hat{\mu}'_a$.

1. **function REPRESENTEDTEST(a, (\hat{\mu}_b, \hat{\mu}'_b)_{b \in S}, \Delta, n)**
   ▷ Test if a is represented in S

2. $\hat{\mu}_a, \hat{\mu}'_a \leftarrow \text{empirical\_mean}(a, n)$

3. **Return** IS TRUE $\{\min_{b \in S} \langle \hat{\mu}_a - \hat{\mu}_b, \hat{\mu}'_a - \hat{\mu}'_b \rangle \le \Delta^2/2\}$

More precisely, let us define

$$U := [8\theta^{-1} \log(8K/\delta)] ; \quad r := \lceil \log_2(\log(4U/\delta)) \rceil; \qquad (9)$$

$$n_s := \left[ c_1 \frac{\sigma^2}{\Delta^2} (2^s + \log(12K)) \vee c_2 \frac{\sigma^2}{\Delta^2} \sqrt{d(2^s + \log(6))} \right] ; \qquad (10)$$

$$s_0 := r \wedge \min\{s \ge 1; n_s \ge 2\} ; \quad n_{\max} := n_r \vee \left[ c_3 \frac{\sigma^2}{\Delta^2} \sqrt{d \log(2K)} \right] , \qquad (11)$$

$$T_{\max} = 2K \left( n_{\max} + \sum_{s=s_0+1}^{r} n_s \right) + 2Un_{s_0} + 2U \sum_{s=s_0+1}^{r} \frac{n_s}{2^{s-4}}, \qquad (12)$$

with $c_1, c_2, c_3 > 0$ numerical constants, explicitly provided in the proof of Lemma C.2. The SRI procedure successively samples candidate arms $a_u$ at random, and performs a sequence of REPRESENTEDTEST with (roughly) doubling sample size $n_s$ for $s = s_0, s_0 + 1, \dots$, until either a REPRESENTEDTEST returns TRUE, in which case the arm $a_u$ is rejected (Line 8); or all tests up to $s = r$ have answered FALSE, in which case the arm $a_u$ is added to $S$ (Line 10). The procedure SRI stops when $|S| = K$, or when a maximal budget has been spent ($T_{\max}$ is defined in (12)) and it returns $\hat{S} = S$. The minimal index $s_0$ ensures that the sample sizes $n_s$ are not smaller than 2.

The sequence of tests is designed in order to use few samples to reject arms already represented in $S$, while wrongly rejecting an unrepresented arm with probability less than $1/2$. Indeed, the choice of
is $\delta$-PAC for environments such that $\Delta_* \le \Delta$ and $\theta_* \le \theta$. We introduce our main algorithm, ACB*, adaptive to $\Delta_*$ and $\theta_*$ in Subsection 4.2.

## 4.1 Warm-up: optimal active clustering with known $\Delta$, $\theta$

The main recipe of ACB is to first identify a set $\hat{S}$ of $K$ arms, which are representative of each group, and then, to classify all the arms based on a precise estimation of the means of the $K$ arms in $\hat{S}$. The ACB algorithm built then on two subroutines:

1. SRI (Sequential Representatives identification), which constructs a set $\hat{S}$ that contains, with high probability, exactly one arm for each group, called the representatives of each group. To construct $\hat{S}$, we use a sequential elimination technique, combined with high-dimensional two-sample tests.

2. ADC (Active Distance-based classification), which computes precise estimates of the means of the arms in $\hat{S}$, and classifies the remaining arms based on minimum estimated distance to the representatives.

**Estimating distances.** In order to detect whether two arms $a$ and $b$ are in the same group, a key ingredient for both SRI and ADC is to get a good estimation of the square distance $\|\mu_a - \mu_b\|^2$ between the means. Computing the empirical means $\hat{\mu}_a$ and $\hat{\mu}_b$ of collected samples of $a$ and $b$, we can estimate $\|\mu_a - \mu_b\|^2$ by $\|\hat{\mu}_a - \hat{\mu}_b\|^2$. Yet, this simple estimator suffers from an unknown bias depending on the noise covariance matrix. This issue can be circumvented in active sampling, by:

(i) computing independent empirical means $\hat{\mu}_a, \hat{\mu}'_a$, and $\hat{\mu}_b, \hat{\mu}'_b$ for the arms $a$ and $b$, based on repeated measurements,

(ii) estimating $\|\mu_a - \mu_b\|^2$ with the unbiased estimator $\hat{d}_{ab}^2 = \langle \hat{\mu}_a - \hat{\mu}_b, \hat{\mu}'_a - \hat{\mu}'_b \rangle$.

**SRI subroutine (Sequential Representative Identification).** The core idea underlying the SRI subroutine is to start from a set $S = \{a_0\}$ made of a single arm, chosen uniformly at random, and then to successively sample new arms $a$, and to add them to $S$, if they pass a sequence of tests ensuring that $a$ is not represented in $S$ with high-probability. The sequence of tests checks if $a$ is already represented in $S$, i.e., if $\min_{b \in S} \|\mu_a - \mu_b\|^2 = 0$, by multiplying the condition $\min_{b \in S} \hat{d}_{ab}^2 \le \Delta^2/2$ with a sequence of estimators $\hat{d}_{ab}^2$ based on increasing sample sizes, ensuring increasing confidence. It is based on the call of the REPRESENTEDTEST subroutine described below, where empirical_mean($a, n$) refers to the action of sampling $n$ times the $a$-th arm, and computing the empirical mean of the collected samples. This action is performed twice to compute $\hat{\mu}_a$ and $\hat{\mu}'_a$.

1. **function REPRESENTEDTEST(a, (\hat{\mu}_b, \hat{\mu}'_b)_{b \in S}, \Delta, n)**
   ▷ Test if a is represented in S

2. $\hat{\mu}_a, \hat{\mu}'_a \leftarrow \text{empirical\_mean}(a, n)$

3. **Return** IS TRUE{$\min_{b \in S} \langle \hat{\mu}_a - \hat{\mu}_b, \hat{\mu}'_a - \hat{\mu}'_b \rangle \le \Delta^2/2$}

More precisely, let us define

$$U := [8\theta^{-1} \log(8K/\delta)] ; \quad r := \lceil \log_2(\log(4U/\delta)) \rceil; \qquad (9)$$

$$n_s := \left[ c_1 \frac{\sigma^2}{\Delta^2} (2^s + \log(12K)) \lor c_2 \frac{\sigma^2}{\Delta^2} \sqrt{d(2^s + \log(6))} \right] ; \qquad (10)$$

$$s_0 := r \land \min\{s \ge 1; n_s \ge 2\} ; \quad n_{\max} := n_r \lor \left[ c_3 \frac{\sigma^2}{\Delta^2} \sqrt{d \log(2K)} \right] , \qquad (11)$$

$$T_{\max} = 2K \left( n_{\max} + \sum_{s=s_0+1}^{r} n_s \right) + 2Un_{s_0} + 2U \sum_{s=s_0+1}^{r} \frac{n_s}{2^{s-4}}, \qquad (12)$$

with $c_1, c_2, c_3 > 0$ numerical constants, explicitly provided in the proof of Lemma C.2. The SRI procedure successively samples candidate arms $a_u$ at random, and performs a sequence of REPRESENTEDTEST with (roughly) doubling sample size $n_s$ for $s = s_0, s_0 + 1, \dots$, until either a REPRESENTEDTEST returns TRUE, in which case the arm $a_u$ is rejected (Line 8); or all tests up to $s = r$ have answered FALSE, in which case the arm $a_u$ is added to $S$ (Line 10). The procedure SRI stops when $|S| = K$, or when a maximal budget has been spent ($T_{\max}$ is defined in (12)) and it returns $\hat{S} = S$. The minimal index $s_0$ ensures that the sample sizes $n_s$ are not smaller than 2.

The sequence of tests is designed in order to use few samples to reject arms already represented in $S$, while wrongly rejecting an unrepresented arm with probability less than 1/2. Indeed, the choice of
1: **procedure** SRI(δ, Δ, θ) ▷ **Sequential Representative Identification**
2: Compute U, r, s₀, n_s, n_max, T_max according to (9)–(12) and sample a₀ ∈ [N]
3: Set S = {a₀}; and ̂μ_{a₀}, ̂μ'_{a₀} ← empirical_mean(a₀, n_max) ▷ **Initialisation**
4: **for** u = 1, ..., U **do**
5: Sample a_u ∈ [N].
6: **for** s = s₀, ..., r **do**
7: **if** REPRESENTEDTEST(a_u, (̂μ_b, ̂μ'_b)_{b∈S}, Δ, n_s) **then**
8: BREAK ▷ **reject** a_u
9: **if** s = r **then**
10: S ← S ∪ {a_u} ▷ **Add** a_u to S
11: ̂μ_{a_u}, ̂μ'_{a_u} ← empirical_mean(a_u, n_max) ▷ **Estimate** μ_{a_u}
12: **if** |S| = K or budget > T_max **then**
13: BREAK ▷ **Terminate** u loop
14: **Return** S ▷ **Return a representative** for each group

the sample sizes $n_s$ and $n_{max}$ ensures that the probability to take a wrong decision at the s-th step is smaller than $2^{-s-1}$. Hence, the probability that an arm already represented in $S$ is rightly rejected before step $s$ is at least $1 - 2^{-s}$, leading to a quick rejection with high-probability. In addition, the maximum sample size $n_r$ is chosen large enough, to ensure a vanishingly small probability of (wrongly) not rejecting such an arm. As for unrepresented arms, the probability to wrongly reject an arm $a_u$ not already represented in $S$ is smaller than $\sum_{s>1} 2^{-s-1} = 1/2$, so that, with probability at least $1 - \delta/4$, we need less than $U$ candidate arms to identify one representative of each group.

**ADC subroutine (Active Distance-based Classification).** Once a set $\hat{S} = \{b_1, \dots, b_K\}$ of representatives of each group has been successfully obtained with SRI, the mean of each group can be precisely estimated, and remaining arms can be classified based on distance estimation $\hat{d}_{ab}^2$ to these means. This classification is performed by the ADC subroutine.

Let us define

$$ J := \left[ c_4 \frac{\sigma^2}{\Delta^2} L \lor c_5 \frac{\sigma^2}{\Delta^2} \sqrt{\frac{dN}{K}} L \right] , \quad I := \left[ c_4 \frac{\sigma^2}{\Delta^2} L \lor c_5 \frac{\sigma^2}{\Delta^2} \sqrt{\frac{dK}{N}} L \right] , \quad (13) $$

with $L = \log(6NK/\delta)$, and $c_4, c_5$ two universal constants defined in the proof of Lemma C.3. Assume, without loss of generality, that $b_j \in G_j^*$ for all $j \in [K]$. Then, ADC first computes two precise estimations $\hat{\mu}(j), \hat{\mu}'(j)$ of the mean of arms in $G_j^*$ (Line 7), each based on $J$ samples of arm $b_j$. As these mean estimations are the references for the classification, the sample size $J$ is chosen large enough to ensure a small variance. Then, for each arm $a$, two mean estimations $\hat{\mu}_a, \hat{\mu}'_a$ are computed based on $I$ samples, and the arm $a$ is classified Line 10 according to the smallest estimated distance (14). The budget $I$ for individual mean estimation is much smaller than $J$ in high-dimension $d$, with $I = KJ/N$ for $d$ large. This budget ensures yet that the probability of misclassifying an arm is smaller than $\delta/N$.

1: **procedure** ADC(δ, Δ, S) ▷ **Active Distance-based Classification**
2: if $|S| \neq K$ **then**
3: return Null
4: **else**
5: Enumerate $S = \{b_1, \dots, b_K\}$, and compute $J, I$ according to (13)
6: **for** $j \in [K]$ **do**
7: $\hat{\mu}(j), \hat{\mu}'(j) \leftarrow \text{empirical\_mean}(b_j, J)$ ▷ **Estimate the mean of each group**
8: $\hat{G}_j \leftarrow \{b_j\}$
9: **for** $a \in [n] \setminus S$ **do**
10: $\hat{\mu}_a, \hat{\mu}'_a \leftarrow \text{empirical\_mean}(a, I)$ ▷ **Classify arm a**
11: Add $a$ to the group $\hat{G}_k$ such that $k \in \underset{j=1,...,K}{\operatorname{argmin}} \langle \hat{\mu}_a - \hat{\mu}(j), \hat{\mu}'_a - \hat{\mu}'(j) \rangle$ (14)
12: **return** $\{\hat{G}_1, \dots, \hat{G}_K\}$ ▷ **Return a clustering**
1: **procedure** SRI(δ, Δ, θ) ▷ **Sequential Representative Identification**
2: Compute U, r, s₀, n_s, n_max, T_max according to (9)–(12) and sample a₀ ∈ [N]
3: Set S = {a₀}; and ̂μ_{a₀}, ̂μ'_{a₀} ← empirical_mean(a₀, n_max) ▷ **Initialisation**
4: **for** u = 1, ..., U **do**
5: Sample a_u ∈ [N].
6: **for** s = s₀, ..., r **do**
7: **if** REPRESENTEDTEST(a_u, (̂μ_b, ̂μ'_b)_{b∈S}, Δ, n_s) **then**
8: BREAK ▷ **reject** a_u
9: **if** s = r **then**
10: S ← S ∪ {a_u} ▷ **Add** a_u to S
11: ̂μ_{a_u}, ̂μ'_{a_u} ← empirical_mean(a_u, n_max) ▷ **Estimate** μ_{a_u}
12: **if** |S| = K or budget > T_max **then**
13: BREAK ▷ **Terminate** u loop
14: **Return** S ▷ **Return a representative** for each group

the sample sizes $n_s$ and $n_{max}$ ensures that the probability to take a wrong decision at the s-th step is smaller than $2^{-s-1}$. Hence, the probability that an arm already represented in $S$ is rightly rejected before step $s$ is at least $1 - 2^{-s}$, leading to a quick rejection with high-probability. In addition, the maximum sample size $n_r$ is chosen large enough, to ensure a vanishingly small probability of (wrongly) not rejecting such an arm. As for unrepresented arms, the probability to wrongly reject an arm $a_u$ not already represented in $S$ is smaller than $\sum_{s>1} 2^{-s-1} = 1/2$, so that, with probability at least $1 - \delta/4$, we need less than $U$ candidate arms to identify one representative of each group.

**ADC subroutine (Active Distance-based Classification).** Once a set $\hat{S} = \{b_1, \dots, b_K\}$ of representatives of each group has been successfully obtained with SRI, the mean of each group can be precisely estimated, and remaining arms can be classified based on distance estimation $\hat{d}_{ab}^2$ to these means. This classification is performed by the ADC subroutine.

Let us define

$$ J := \left[ c_4 \frac{\sigma^2}{\Delta^2} L \lor c_5 \frac{\sigma^2}{\Delta^2} \sqrt{\frac{dN}{K}} L \right] , \quad I := \left[ c_4 \frac{\sigma^2}{\Delta^2} L \lor c_5 \frac{\sigma^2}{\Delta^2} \sqrt{\frac{dK}{N}} L \right] , \quad (13) $$

with $L = \log(6NK/\delta)$, and $c_4, c_5$ two universal constants defined in the proof of Lemma C.3. Assume, without loss of generality, that $b_j \in G_j^*$ for all $j \in [K]$. Then, ADC first computes two precise estimations $\hat{\mu}(j), \hat{\mu}'(j)$ of the mean of arms in $G_j^*$ (Line 7), each based on $J$ samples of arm $b_j$. As these mean estimations are the references for the classification, the sample size $J$ is chosen large enough to ensure a small variance. Then, for each arm $a$, two mean estimations $\hat{\mu}_a, \hat{\mu}'_a$ are computed based on $I$ samples, and the arm $a$ is classified Line 10 according to the smallest estimated distance (14). The budget $I$ for individual mean estimation is much smaller than $J$ in high-dimension $d$, with $I = KJ/N$ for $d$ large. This budget ensures yet that the probability of misclassifying an arm is smaller than $\delta/N$.

1: **procedure** ADC(δ, Δ, S) ▷ **Active Distance-based Classification**
2: **if** |S| ≠ K **then**
3: **return** Null
4: **else**
5: Enumerate S = {b₁, ..., b_K}, and compute J, I according to (13)
6: **for** j ∈ [K] **do**
7: ̂μ(j), ̂μ'(j) ← empirical_mean(b_j, J) ▷ **Estimate the mean** of each group
8: ̂G_j ← {b_j}
9: **for** a ∈ [n] \ S **do**
10: ̂μ_a, ̂μ'_a ← empirical_mean(a, I) ▷ **Classify** arm a
11: Add a to the group ̂G_k such that $k \in \underset{j=1,...,K}{\operatorname{argmin}} \langle \hat{\mu}_a - \hat{\mu}(j), \hat{\mu}'_a - \hat{\mu}'(j) \rangle$ (14)
12: **return** { ̂G₁, ..., ̂G_K} ▷ **Return a clustering**
**ACB algorithm.** Combining the SRI and ADC subroutines, we get a simple active clustering algorithm ACB for the case where $\Delta_*$ and $\theta_*$ are known – see Algorithm 1.

**Algorithm 1 ACB ($\theta_*$ and $\Delta_*$ known)**

1: **Input:** $\delta, \Delta, \theta$

2: $\hat{S} \leftarrow \text{SRI}(\delta/2, \Delta, \theta)$

3: **return** $\hat{G} = \text{ADC}(\delta/2, \Delta, \hat{S})$

**Algorithm 2 ACB\* ($\theta_*$ and $\Delta_*$ unknown)**
1: **Input:** $\delta$
2: **for** $l = 0, 1, \dots, \text{do}$
3: &nbsp;&nbsp;&nbsp;&nbsp;**for** $p = 0, \dots, l$ **do**
4: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Compute $S_{p,l} \leftarrow \text{SRI}(\delta_l, \Delta_p, \theta_{p,l} \lor \frac{1}{N})$
5: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $|S_{p,l}| = K$ **then**
6: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**for** $a \in S_{p,l}$ **do**
7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\bar{\mu}_a, \bar{\mu}'_a \leftarrow \text{empirical\_mean}(a, n'_p)$
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\hat{\Delta}^2 \leftarrow \inf_{a,b \in S_{p,l}} \langle \bar{\mu}_a - \bar{\mu}_b, \bar{\mu}'_a - \bar{\mu}'_b \rangle$
9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**return** $\hat{G} = \text{ADC}(\delta/3, 2^{-1/2}\hat{\Delta}, S_{p,l})$

## 4.2 Main algorithm ACB\*

When the parameters $\Delta_*$ and $\theta_*$ are unknown, we cannot rely on a single call to SRI and ADC as in the ACB algorithm. Multiscale calls to SRI are required, for different candidate levels $\Delta_p$ and $\theta_{p,l}$ for $\Delta_*$ and $\theta_*$. These levels, related sample sizes $n'_p$, and confidence levels $\delta_l$ are defined by

$$ \Delta_0^2 = \sigma^2[\log(K) + \sqrt{d} + \log \log(6N/\delta)], \quad \delta_l = \frac{\delta}{6(l+1)^3} \quad (15) $$

$$ \theta_{p,l} = \frac{1}{K^2 l^{-p}}, \quad \Delta_p = \Delta_0 \sqrt{\frac{1}{2^p}}, \quad n'_p = \left[ c_6 \frac{\sigma^2}{\Delta_p^2} \left( \log(3K^2/\delta) + \sqrt{d \log(3K^2/\delta)} \right) \right], \quad (16) $$

where $c_6$ is a numerical constant, whose value is given in (55).

The main recipe in ACB\*, is to scan decreasing candidate values $\Delta_p$ and $\theta_{p,l}$, until we find a scale where SRI returns a set $S_{p,l}$ of cardinality $K$, see Algorithm 2.

Below, we provide upper bounds on $T^*(\delta, \mathcal{E}(\Delta, \theta, \sigma, N, K, d))$ for both ACB and ACB\*. We write $\tau_{ACB}$ and $\tau_{ACB\*}$ for the budget of the non-adaptive procedure ACB($\delta, \Delta, \theta$), and of the adaptive one ACB\*($\delta$). Define the quantities

$$ A = \frac{\sigma^2}{\Delta^2} \left[ N \log(N/\delta) + \sqrt{dNK \log(N/\delta)} + \sqrt{d} \frac{\log(K)}{\theta} \right] $$

$$ B = \frac{1}{\theta} \log(K/\delta) + \frac{\sigma^2}{\Delta^2} \frac{1}{\theta} \log\left(\frac{K}{\delta}\right) \left[ \sqrt{d} + \log \log(N/\delta) \right]. $$

**Theorem 4.1.** Let $\delta > 0$. Let $\Delta > 0, \theta > 0$ be any two parameters such that $\mathcal{E}(\Delta, \theta, \sigma, N, K, d) \neq \emptyset$. Both the ACB (Algorithm 1) and its adaptive version ACB\* (Algorithm 2) are $\delta$-PAC on $\mathcal{E}(\Delta, \theta, \sigma, N, K, d)$. There exist numerical constants $c, c', c''$, independent of all the parameters $\Delta, \theta, \sigma, N, K, d$ such that the following holds. For any environment $\nu$ in $\mathcal{E}(\Delta, \theta, \sigma, N, K, d)$, such that $\theta \ge \log(K)/N$, we have

$$ \mathbb{E}_{ACB,\nu}[\tau_{ACB}] \le cN + c'A; \quad \tau_{ACB} \le cN + c'(A+B) \text{ a.s.} $$

$$ \mathbb{P}_{ACB^{*},\nu}[\tau_{ACB^{*}} \le cN + c''L \log^2(L)(A+B)] \ge 1 - \delta, $$

$$ \text{where } L := \log_2 \left( \frac{1}{\theta K} \left( \frac{\Delta_0^2}{\Delta^2} \lor 1 \right) \right). $$

# 5 Numerical experiments

In this section, we run experiments on synthetic data with standard Gaussian noise ($\sigma = 1$). We consider environments with equidistant centers (with $\Delta_* = 1$), and balanced groups ($\theta_* \approx 1/K$). We choose a high-dimensional setting with $N = 200, d = 1000$, and $K \in \{10, 15, 20, 25\}$. We compare ACB with oracle-BOC [36] - in our balanced setup it simply performs uniform sampling, see below.

Regarding ACB, we assume that $\Delta_*$ is known, and we implement the non-adaptive version of ACB with $\delta = 0.1$. In order to provide a tighter calibration of ACB, we slightly modify ACB
**ACB algorithm.** Combining the SRI and ADC subroutines, we get a simple active clustering algorithm ACB for the case where $\Delta_*$ and $\theta_*$ are known – see Algorithm 1.

**Algorithm 1 ACB ($\theta_*$ and $\Delta_*$ known)**

1: **Input:** $\delta, \Delta, \theta$

2: $\hat{S} \leftarrow \text{SRI}(\delta/2, \Delta, \theta)$

3: **return** $\hat{G} = \text{ADC}(\delta/2, \Delta, \hat{S})$

**Algorithm 2 ACB\* ($\theta_*$ and $\Delta_*$ unknown)**
1: **Input:** $\delta$
2: **for** $l = 0, 1, \dots, \text{do}$
3: &nbsp;&nbsp;&nbsp;&nbsp;**for** $p = 0, \dots, l$ **do**
4: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Compute $S_{p,l} \leftarrow \text{SRI}(\delta_l, \Delta_p, \theta_{p,l} \lor \frac{1}{N})$
5: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $|S_{p,l}| = K$ **then**
6: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**for** $a \in S_{p,l}$ **do**
7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\bar{\mu}_a, \bar{\mu}'_a \leftarrow \text{empirical\_mean}(a, n'_p)$
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$$\hat{\Delta}^2 \leftarrow \inf_{a,b \in S_{p,l}} \langle \bar{\mu}_a - \bar{\mu}_b, \bar{\mu}'_a - \bar{\mu}'_b \rangle$$
9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**return** $\hat{G} = \text{ADC}(\delta/3, 2^{-1/2}\hat{\Delta}, S_{p,l})$

## 4.2 Main algorithm ACB\*

When the parameters $\Delta_*$ and $\theta_*$ are unknown, we cannot rely on a single call to SRI and ADC as in the ACB algorithm. Multiscale calls to SRI are required, for different candidate levels $\Delta_p$ and $\theta_{p,l}$ for $\Delta_*$ and $\theta_*$. These levels, related sample sizes $n'_p$, and confidence levels $\delta_l$ are defined by

$$ \Delta_0^2 = \sigma^2[\log(K) + \sqrt{d} + \log \log(6N/\delta)], \quad \delta_l = \frac{\delta}{6(l+1)^3} \quad (15) $$

$$ \theta_{p,l} = \frac{1}{K^2 l^{-p}}, \quad \Delta_p = \Delta_0 \sqrt{\frac{1}{2^p}}, \quad n'_p = \left[ c_6 \frac{\sigma^2}{\Delta_p^2} \left( \log(3K^2/\delta) + \sqrt{d \log(3K^2/\delta)} \right) \right], \quad (16) $$

where $c_6$ is a numerical constant, whose value is given in (55).

The main recipe in ACB\*, is to scan decreasing candidate values $\Delta_p$ and $\theta_{p,l}$, until we find a scale where SRI returns a set $S_{p,l}$ of cardinality $K$, see Algorithm 2.

Below, we provide upper bounds on $T^*(\delta, \mathcal{E}(\Delta, \theta, \sigma, N, K, d))$ for both ACB and ACB\*. We write $\tau_{ACB}$ and $\tau_{ACB\*}$ for the budget of the non-adaptive procedure ACB($\delta, \Delta, \theta$), and of the adaptive one ACB\*($\delta$). Define the quantities

$$ A = \frac{\sigma^2}{\Delta^2} \left[ N \log(N/\delta) + \sqrt{dNK \log(N/\delta)} + \sqrt{d \frac{\log(K)}{\theta}} \right] $$

$$ B = \frac{1}{\theta} \log(K/\delta) + \frac{\sigma^2}{\Delta^2} \frac{1}{\theta} \log\left(\frac{K}{\delta}\right) \left[ \sqrt{d} + \log \log(N/\delta) \right]. $$

**Theorem 4.1.** Let $\delta > 0$. Let $\Delta > 0, \theta > 0$ be any two parameters such that $\mathcal{E}(\Delta, \theta, \sigma, N, K, d) \neq \emptyset$. Both the ACB (Algorithm 1) and its adaptive version ACB\* (Algorithm 2) are $\delta$-PAC on $\mathcal{E}(\Delta, \theta, \sigma, N, K, d)$. There exist numerical constants $c, c', c''$, independent of all the parameters $\Delta, \theta, \sigma, N, K, d$ such that the following holds. For any environment $\nu$ in $\mathcal{E}(\Delta, \theta, \sigma, N, K, d)$, such that $\theta \ge \log(K)/N$, we have

$$ \mathbb{E}_{ACB,\nu}[\tau_{ACB}] \le cN + c'A; \quad \tau_{ACB} \le cN + c'(A+B) \text{ a.s.} $$

$$ \mathbb{P}_{ACB^{*},\nu}[\tau_{ACB^{*}} \le cN + c''L \log^2(L)(A+B)] \ge 1 - \delta, $$

$$ \text{where } L := \log_2 \left( \frac{1}{\theta K} \left( \frac{\Delta_0^2}{\Delta^2} \lor 1 \right) \right). $$

# 5 Numerical experiments

In this section, we run experiments on synthetic data with standard Gaussian noise ($\sigma = 1$). We consider environments with equidistant centers (with $\Delta_* = 1$), and balanced groups ($\theta_* \approx 1/K$). We choose a high-dimensional setting with $N = 200, d = 1000$, and $K \in \{10, 15, 20, 25\}$. We compare ACB with oracle-BOC [36] - in our balanced setup it simply performs uniform sampling, see below.

Regarding ACB, we assume that $\Delta_*$ is known, and we implement the non-adaptive version of ACB with $\delta = 0.1$. In order to provide a tighter calibration of ACB, we slightly modify ACB
algorithm in order to specialize it to the Gaussian distribution –see Appendix A. As the setting is
perfectly symmetric (balanced clusters, equidistant means), the Oracle-BOC policy is equivalent to
the Uniform Sampling strategy, with Loyd initialised by maximin. We implement instead a kmeans++
initialisation, as it is known to outperform maximin [2].

<figure><img src="image_1.png" /><figcaption>Figure 1: Comparison of the necessary budget for ACB and oracle-BOC. We represent (orange curve) the (empirical) budget of ACB computed with 100 simulations, for $K = 10, 15, 20, 25$. The error bars are equal to twice the standard deviation. In blue, we provide the smallest budget for which oracle-BOC (initialised with kmeans++) makes less than 10% of error out of 100 experiments. As this budget is a numerical constant, there are no error bars.</figcaption></figure>

In Figure 1, we plot the estimated mean budget of ACB as a function of $K$, as well as the budget of oracle-BOC, with the budget chosen so that the procedure is exactly $\delta$-PAC with $\delta = 0.1$. This figure confirms our theoretical findings that, in a high-dimensional setting ($d \gg N/K$), ACB improves over oracle-BOC - which is here equivalent to a state of the art batch clustering algorithm - when the number $K$ of groups increases. Also, we have checked that ACB is $\delta$-PAC. Fixing $\delta = 0.1$, we observe no more than 1 error out of 100 experiments. We detail further the experimental setup (including compute resources) in Appendix A.

# 6 Discussion

**Optimality of ACB.** First, we discuss the budget of ACB, and we compare it to the information-theoretical lower bound of Theorem 3.1. To simplify the discussion, let us first consider the case where the partition $G^*$ is almost balanced, that is when $\theta$ is of the order of $1/K$, and assume that $\frac{\Delta^2}{\sigma^2} \lesssim \log(N/\delta)$. According to Theorem 4.1, the $\delta$-PAC algorithm ACB has an expected budget upper bounded by (3), as long as $K \le N/\log(N)$. In light of Theorem 3.1, we see that the expected budget is optimal with respect to all the quantities of the problem: the number of arms $N$, the minimum separation $\Delta$, the number of groups $K$, the probability $\delta$, and the subGaussian norm $\sigma$. The only restriction is that the number of groups $K$ is smaller than $N/\log(N)$, but it is really mild as non-supervised learning problems are mostly relevant for dimension reduction, that is when $K$ is really small compared to $N$. In fact, for larger $K \in [\frac{N}{\log(N)}, N/2]$, the expected budget $\mathbb{E}_{ACB,\nu}[\tau_{ACB}]$ is optimal, up to a possible $\sqrt{\log(N)}$ multiplicative term. Theorem 4.1 also states high probability controls of the budget $\tau_{ACB}$ and $\tau_{ACB}^*$ which again, are optimal (up to log terms for the latter), in most regimes.

When the true partition $G^*$ is extremely unbalanced, so that $\theta_* \le \frac{\log(K)}{\sqrt{\log(N/\delta)KN}}$, the bound $A$ on the expected budget may be larger than the lower bound of Theorem 3.1. We conjecture that the upper bound could be improved in this extreme case, but we leave this for future work.

**Further comparison with [36].** When $\delta$ goes to zero while $\sigma$, $\Delta$, $K$, and $d$ are fixed, the average budget of ACB in (3) is at most of the order of $\frac{\sigma^2}{\Delta^2}N \log(1/\delta)$, and is consistent with the BOC algorithm of [36]. Still, we mention that [36] manage to pinpoint the exact value of the asymptotic optimal budget, while our non-asymptotic bounds are only tight up to numerical constants. We however point out that this asymptotic expression hides dependencies on $K$, $d$, and $N$, which are not negligible unless $\delta$ is exponentially small with respect to $d$, $K$ - and in high dimension, such a high confidence regime is typically out of reach.

**Comparison to batch clustering.** We briefly come back to our fundamental questions on the comparison between the batch and active clustering problems. Contrary to the batch setting, we have established that the polynomial-time strategy ACB is information-theoretical optimal, thereby establishing the absence of computation-information gap. This is in contrast with the classical batch
algorithm in order to specialize it to the Gaussian distribution –see Appendix A. As the setting is
perfectly symmetric (balanced clusters, equidistant means), the Oracle-BOC policy is equivalent to
the Uniform Sampling strategy, with Loyd initialised by maximin. We implement instead a kmeans++
initialisation, as it is known to outperform maximin [2].

<figure><img src="image_2.png" /><figcaption>Figure 1: Comparison of the necessary budget for ACB and oracle-BOC. We represent (orange curve) the (empirical) budget of ACB computed with 100 simulations, for $K = 10, 15, 20, 25$. The error bars are equal to twice the standard deviation. In blue, we provide the smallest budget for which oracle-BOC (initialised with kmeans++) makes less than 10% of error out of 100 experiments. As this budget is a numerical constant, there are no error bars.</figcaption></figure>

In Figure 1, we plot the estimated mean budget of ACB as a function of $K$, as well as the budget of oracle-BOC, with the budget chosen so that the procedure is exactly $\delta$-PAC with $\delta = 0.1$. This figure confirms our theoretical findings that, in a high-dimensional setting ($d \gg N/K$), ACB improves over oracle-BOC - which is here equivalent to a state of the art batch clustering algorithm - when the number $K$ of groups increases. Also, we have checked that ACB is $\delta$-PAC. Fixing $\delta = 0.1$, we observe no more than 1 error out of 100 experiments. We detail further the experimental setup (including compute resources) in Appendix A.

# 6 Discussion

**Optimality of ACB.** First, we discuss the budget of ACB, and we compare it to the information-theoretical lower bound of Theorem 3.1. To simplify the discussion, let us first consider the case where the partition $G^*$ is almost balanced, that is when $\theta$ is of the order of $1/K$, and assume that $\frac{\Delta^2}{\sigma^2} \lesssim \log(N/\delta)$. According to Theorem 4.1, the $\delta$-PAC algorithm ACB has an expected budget upper bounded by (3), as long as $K \le N/\log(N)$. In light of Theorem 3.1, we see that the expected budget is optimal with respect to all the quantities of the problem: the number of arms $N$, the minimum separation $\Delta$, the number of groups $K$, the probability $\delta$, and the subGaussian norm $\sigma$. The only restriction is that the number of groups $K$ is smaller than $N/\log(N)$, but it is really mild as non-supervised learning problems are mostly relevant for dimension reduction, that is when $K$ is really small compared to $N$. In fact, for larger $K \in [\frac{N}{\log(N)}, N/2]$, the expected budget $\mathbb{E}_{ACB,\nu}[\tau_{ACB}]$ is optimal, up to a possible $\sqrt{\log(N)}$ multiplicative term. Theorem 4.1 also states high probability controls of the budget $\tau_{ACB}$ and $\tau_{ACB}^*$ which again, are optimal (up to log terms for the latter), in most regimes.

When the true partition $G^*$ is extremely unbalanced, so that $\theta_* \le \frac{\log(K)}{\sqrt{\log(N/\delta)KN}}$, the bound $A$ on the expected budget may be larger than the lower bound of Theorem 3.1. We conjecture that the upper bound could be improved in this extreme case, but we leave this for future work.

**Further comparison with [36].** When $\delta$ goes to zero while $\sigma$, $\Delta$, $K$, and $d$ are fixed, the average budget of ACB in (3) is at most of the order of $\frac{\sigma^2}{\Delta^2}N \log(1/\delta)$, and is consistent with the BOC algorithm of [36]. Still, we mention that [36] manage to pinpoint the exact value of the asymptotic optimal budget, while our non-asymptotic bounds are only tight up to numerical constants. We however point out that this asymptotic expression hides dependencies on $K$, $d$, and $N$, which are not negligible unless $\delta$ is exponentially small with respect to $d$, $K$ - and in high dimension, such a high confidence regime is typically out of reach.

**Comparison to batch clustering.** We briefly come back to our fundamental questions on the comparison between the batch and active clustering problems. Contrary to the batch setting, we have established that the polynomial-time strategy ACB is information-theoretical optimal, thereby establishing the absence of computation-information gap. This is in contrast with the classical batch
clustering problem, where strong evidence of a computation-information gap were proved in [12] in high dimension, when there are many groups. We therefore illustrate here that clustering is an unsupervised learning problem, where repeated active sampling breaks a computational barrier, which is interesting and opens perspectives for other unsupervised clustering problems where computation-information gap are conjectured.

**Conclusion and limitations.** In our paper, we characterized the non-asymptotic minimal budget for recovering the groups in a collection of environment $\mathcal{E}(\Delta, \theta, \sigma, N, K, d)$, where the minimum distance between the groups is higher or equal to $\Delta$, and all groups have a size larger than $\theta$. We also crafted a strategy adaptive to both $\theta_*$ and $\Delta_*$. Unlike in batch clustering, our results prove that there is no computation-information gap.

Our work still has limitations, and raises several open questions: First, it remains to explore how sequential and active learning can be leveraged for adapting to heterogeneous distances between groups and heterogeneous group sizes. This has been investigated in [36] in the asymptotic regime, but not in the non-asymptotic regime. Second, when $\sigma$ is unknown, building a sampling strategy that is adaptive to it, would require to estimate the subGaussian norm of the noise, while at the same time estimating the distances between the means. We leave this question for a future work. Finally, as in most of the clustering literature, we assumed that the number $K$ of groups was known to the learner. Investigating the problem of estimating or testing the number of groups in an active setting is also an interesting research direction.

# 7 Acknowledgements

The work of V. Thuot and N. Verzelen has been partially supported by grant ANR-21-CE23-0035 (ASCAI,ANR). The work of A. Carpentier has been partially supported by the DFG CRC 1294 'Data Assimilation', Project A03, by the DFG Forschungsgruppe FOR 5381 "Mathematical Statistics in the Information Age - Statistical Efficiency and Computational Tractability", Project TP 02, by the Agence Nationale de la Recherche (ANR) and the DFG on the French-German PRCI ANR ASCAI CA 1488/4-1 "Aktive und Batch-Segmentierung, Clustering und Seriation: Grundlagen der KI". The work of C. Giraud has been partially supported by grant ANR-19-CHIA-0021-01(BiSCottE, ANR) and ANR-21-CE23-0035 (ASCAI, ANR).

# References

[1] Kaito Ariu, Jungseul Ok, Alexandre Proutiere, and Seyoung Yun. Optimal clustering from noisy binary feedback. *Machine Learning*, 113(5):2733-2764, 2024.

[2] M Emre Celebi, Hassan A Kingravi, and Patricio A Vela. A comparative study of efficient initialization methods for the k-means clustering algorithm. *Expert systems with applications*, 40(1):200-210, 2013.

[3] Lijie Chen and Jian Li. On the optimal sample complexity for best arm identification. arXiv preprint arXiv:1511.03774, 2015.

[4] Shouyuan Chen, Tian Lin, Irwin King, Michael R Lyu, and Wei Chen. Combinatorial pure exploration of multi-armed bandits. *Advances in neural information processing systems*, 27, 2014.

[5] Xiaohui Chen and Yun Yang. Hanson-Wright inequality in Hilbert spaces with application to $K$-means clustering for non-Euclidean data. *Bernoulli*, 27(1):586-614, 2021.

[6] James Cheshire, Pierre Ménard, and Alexandra Carpentier. The influence of shape constraints on the thresholding bandit problem. In *Conference on Learning Theory*, pages 1228-1275. PMLR, 2020.

[7] Vincent Cohen-Addad, Benjamin Guedj, Varun Kanade, and Guy Rom. Online k-means clustering. In *International Conference on Artificial Intelligence and Statistics*, pages 1126-1134. PMLR, 2021.

[8] Sanjoy Dasgupta. Learning mixtures of gaussians. In *40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039)*, pages 634-644, 1999.

[9] Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas, and Nikos Zarifis. Sq lower bounds for learning mixtures of separated and bounded covariance gaussians. In *Gergely Neu and Lorenzo
clustering problem, where strong evidence of a computation-information gap were proved in [12] in high dimension, when there are many groups. We therefore illustrate here that clustering is an unsupervised learning problem, where repeated active sampling breaks a computational barrier, which is interesting and opens perspectives for other unsupervised clustering problems where computation-information gap are conjectured.

**Conclusion and limitations.** In our paper, we characterized the non-asymptotic minimal budget for recovering the groups in a collection of environment $\mathcal{E}(\Delta, \theta, \sigma, N, K, d)$, where the minimum distance between the groups is higher or equal to $\Delta$, and all groups have a size larger than $\theta$. We also crafted a strategy adaptive to both $\theta_*$ and $\Delta_*$. Unlike in batch clustering, our results prove that there is no computation-information gap.

Our work still has limitations, and raises several open questions: First, it remains to explore how sequential and active learning can be leveraged for adapting to heterogeneous distances between groups and heterogeneous group sizes. This has been investigated in [36] in the asymptotic regime, but not in the non-asymptotic regime. Second, when $\sigma$ is unknown, building a sampling strategy that is adaptive to it, would require to estimate the subGaussian norm of the noise, while at the same time estimating the distances between the means. We leave this question for a future work. Finally, as in most of the clustering literature, we assumed that the number $K$ of groups was known to the learner. Investigating the problem of estimating or testing the number of groups in an active setting is also an interesting research direction.

# 7 Acknowledgements

The work of V. Thuot and N. Verzelen has been partially supported by grant ANR-21-CE23-0035 (ASCAI,ANR). The work of A. Carpentier has been partially supported by the DFG CRC 1294 'Data Assimilation', Project A03, by the DFG Forschungsgruppe FOR 5381 "Mathematical Statistics in the Information Age - Statistical Efficiency and Computational Tractability", Project TP 02, by the Agence Nationale de la Recherche (ANR) and the DFG on the French-German PRCI ANR ASCAI CA 1488/4-1 "Aktive und Batch-Segmentierung, Clustering und Seriation: Grundlagen der KI". The work of C. Giraud has been partially supported by grant ANR-19-CHIA-0021-01(BiSCottE, ANR) and ANR-21-CE23-0035 (ASCAI, ANR).

# References

[1] Kaito Ariu, Jungseul Ok, Alexandre Proutiere, and Seyoung Yun. Optimal clustering from noisy binary feedback. Machine Learning, 113(5):2733-2764, 2024.

[2] M Emre Celebi, Hassan A Kingravi, and Patricio A Vela. A comparative study of efficient initialization methods for the k-means clustering algorithm. Expert systems with applications, 40(1):200-210, 2013.

[3] Lijie Chen and Jian Li. On the optimal sample complexity for best arm identification. arXiv preprint arXiv:1511.03774, 2015.

[4] Shouyuan Chen, Tian Lin, Irwin King, Michael R Lyu, and Wei Chen. Combinatorial pure exploration of multi-armed bandits. Advances in neural information processing systems, 27, 2014.

[5] Xiaohui Chen and Yun Yang. Hanson-Wright inequality in Hilbert spaces with application to $K$-means clustering for non-Euclidean data. Bernoulli, 27(1):586-614, 2021.

[6] James Cheshire, Pierre Ménard, and Alexandra Carpentier. The influence of shape constraints on the thresholding bandit problem. In Conference on Learning Theory, pages 1228-1275. PMLR, 2020.

[7] Vincent Cohen-Addad, Benjamin Guedj, Varun Kanade, and Guy Rom. Online k-means clustering. In International Conference on Artificial Intelligence and Statistics, pages 1126-1134. PMLR, 2021.

[8] Sanjoy Dasgupta. Learning mixtures of gaussians. In 40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039), pages 634-644, 1999.

[9] Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas, and Nikos Zarifis. Sq lower bounds for learning mixtures of separated and bounded covariance gaussians. In Gergely Neu and Lorenzo
Rosasco, editors, *Proceedings of Thirty Sixth Conference on Learning Theory*, volume 195 of *Proceedings of Machine Learning Research*, pages 2319–2349. PMLR, 12–15 Jul 2023.

[10] Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart. Statistical query lower bounds for robust estimation of high-dimensional gaussians and gaussian mixtures. In *2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)*, pages 73–84, 2017.

[11] Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart. List-decodable robust mean estimation and learning mixtures of spherical gaussians. In *Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing*, STOC 2018, page 1047–1060. Association for Computing Machinery, 2018.

[12] Bertrand Even, Christophe Giraud, and Nicolas Verzelen. Computation-information gap in high-dimensional clustering. In Aaron Roth Shipra Agrawal, editor, *Proceedings of Thirty Seventh Conference on Learning Theory*, Proceedings of Machine Learning Research. PMLR, 30 Jun – 3 Jul 2024.

[13] Yingjie Fei and Yudong Chen. Hidden integrality of sdp relaxations for sub-gaussian mixture models. In *Proceedings of the 31st Conference On Learning Theory*, volume 75 of *Proceedings of Machine Learning Research*, pages 1931–1965. PMLR, 2018.

[14] Sébastien Gerchinovitz, Pierre Ménard, and Gilles Stoltz. Fano's inequality for random variables. *Statistical Science*, 35(2):178–201, 2020.

[15] Christophe Giraud and Nicolas Verzelen. Partial recovery bounds for clustering with the relaxed $k$-means. *Mathematical Statistics and Learning*, 1(3):317–374, 2019.

[16] Kevin Jamieson and Robert Nowak. Best-arm identification algorithms for multi-armed bandits in the fixed confidence setting. In *2014 48th Annual Conference on Information Sciences and Systems (CISS)*, pages 1–6. IEEE, 2014.

[17] Kevin G Jamieson, Daniel Haas, and Benjamin Recht. The power of adaptivity in identifying statistical alternatives. *Advances in Neural Information Processing Systems*, 29, 2016.

[18] Sumeet Katariya, Lalit Jain, Nandana Sengupta, James Evans, and Robert Nowak. Adaptive sampling for coarse ranking. In *International Conference on Artificial Intelligence and Statistics*, pages 1839–1848. PMLR, 2018.

[19] Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier. On the complexity of best arm identification in multi-armed bandit models. *Journal of Machine Learning Research*, 17:1–42, 2016.

[20] Pravesh K. Kothari and Jacob Steinhardt. Better Agnostic Clustering Via Relaxed Tensor Norms. *CoRR*, abs/1711.07465, 2017.

[21] Jeongyeol Kwon and Constantine Caramanis. The em algorithm gives sample-optimality for learning mixtures of well-separated gaussians. In Jacob Abernethy and Shivani Agarwal, editors, *Proceedings of Thirty Third Conference on Learning Theory*, volume 125 of *Proceedings of Machine Learning Research*, pages 2425–2487. PMLR, 09–12 Jul 2020.

[22] Beatrice Laurent and Pascal Massart. Adaptive estimation of a quadratic functional by model selection. *Annals of Statistics*, pages 1302–1338, 2000.

[23] Thibault Lesieur, Caterina De Bacco, Jess Banks, Florent Krzakala, Cris Moore, and Lenka Zdeborová. Phase transitions and optimal algorithms in high-dimensional gaussian mixture clustering. In *2016 54th Annual Allerton Conference on Communication, Control, and Computing (Allerton)*, pages 601–608. IEEE, 2016.

[24] Allen Liu and Jerry Li. Clustering mixtures with almost optimal separation in polynomial time. In *Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing*, STOC 2022, page 1248–1261, New York, NY, USA, 2022. Association for Computing Machinery.

[25] Andrea Locatelli, Maurilio Gutzeit, and Alexandra Carpentier. An optimal algorithm for the thresholding bandit problem. In *International Conference on Machine Learning*, pages 1690–1698. PMLR, 2016.

[26] Yu Lu and Harrison H. Zhou. Statistical and Computational Guarantees of Lloyd's Algorithm and its Variants. *ArXiv e-prints*, December 2016.

[27] Mohamed Ndaoud. Sharp optimal recovery in the two component gaussian mixture model. *The Annals of Statistics*, 50(4):2096–2126, 2022.
Rosasco, editors, *Proceedings of Thirty Sixth Conference on Learning Theory*, volume 195 of *Proceedings of Machine Learning Research*, pages 2319–2349. PMLR, 12–15 Jul 2023.

[10] Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart. Statistical query lower bounds for robust estimation of high-dimensional gaussians and gaussian mixtures. In *2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)*, pages 73–84, 2017.

[11] Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart. List-decodable robust mean estimation and learning mixtures of spherical gaussians. In *Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing*, STOC 2018, page 1047–1060. Association for Computing Machinery, 2018.

[12] Bertrand Even, Christophe Giraud, and Nicolas Verzelen. Computation-information gap in high-dimensional clustering. In Aaron Roth Shipra Agrawal, editor, *Proceedings of Thirty Seventh Conference on Learning Theory*, Proceedings of Machine Learning Research. PMLR, 30 Jun – 3 Jul 2024.

[13] Yingjie Fei and Yudong Chen. Hidden integrality of sdp relaxations for sub-gaussian mixture models. In *Proceedings of the 31st Conference On Learning Theory*, volume 75 of *Proceedings of Machine Learning Research*, pages 1931–1965. PMLR, 2018.

[14] Sébastien Gerchinovitz, Pierre Ménard, and Gilles Stoltz. Fano's inequality for random variables. *Statistical Science*, 35(2):178–201, 2020.

[15] Christophe Giraud and Nicolas Verzelen. Partial recovery bounds for clustering with the relaxed $k$-means. *Mathematical Statistics and Learning*, 1(3):317–374, 2019.

[16] Kevin Jamieson and Robert Nowak. Best-arm identification algorithms for multi-armed bandits in the fixed confidence setting. In *2014 48th Annual Conference on Information Sciences and Systems (CISS)*, pages 1–6. IEEE, 2014.

[17] Kevin G Jamieson, Daniel Haas, and Benjamin Recht. The power of adaptivity in identifying statistical alternatives. *Advances in Neural Information Processing Systems*, 29, 2016.

[18] Sumeet Katariya, Lalit Jain, Nandana Sengupta, James Evans, and Robert Nowak. Adaptive sampling for coarse ranking. In *International Conference on Artificial Intelligence and Statistics*, pages 1839–1848. PMLR, 2018.

[19] Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier. On the complexity of best arm identification in multi-armed bandit models. *Journal of Machine Learning Research*, 17:1–42, 2016.

[20] Pravesh K. Kothari and Jacob Steinhardt. Better Agnostic Clustering Via Relaxed Tensor Norms. *CoRR*, abs/1711.07465, 2017.

[21] Jeongyeol Kwon and Constantine Caramanis. The em algorithm gives sample-optimality for learning mixtures of well-separated gaussians. In Jacob Abernethy and Shivani Agarwal, editors, *Proceedings of Thirty Third Conference on Learning Theory*, volume 125 of *Proceedings of Machine Learning Research*, pages 2425–2487. PMLR, 09–12 Jul 2020.

[22] Beatrice Laurent and Pascal Massart. Adaptive estimation of a quadratic functional by model selection. *Annals of Statistics*, pages 1302–1338, 2000.

[23] Thibault Lesieur, Caterina De Bacco, Jess Banks, Florent Krzakala, Cris Moore, and Lenka Zdeborová. Phase transitions and optimal algorithms in high-dimensional gaussian mixture clustering. In *2016 54th Annual Allerton Conference on Communication, Control, and Computing (Allerton)*, pages 601–608. IEEE, 2016.

[24] Allen Liu and Jerry Li. Clustering mixtures with almost optimal separation in polynomial time. In *Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing*, STOC 2022, page 1248–1261, New York, NY, USA, 2022. Association for Computing Machinery.

[25] Andrea Locatelli, Maurilio Gutzeit, and Alexandra Carpentier. An optimal algorithm for the thresholding bandit problem. In *International Conference on Machine Learning*, pages 1690–1698. PMLR, 2016.

[26] Yu Lu and Harrison H. Zhou. Statistical and Computational Guarantees of Lloyd's Algorithm and its Variants. *ArXiv e-prints*, December 2016.

[27] Mohamed Ndaoud. Sharp optimal recovery in the two component gaussian mixture model. *The Annals of Statistics*, 50(4):2096–2126, 2022.
[28] Jiming Peng and Yu Wei. Approximating K-means-type Clustering via Semidefinite Programming. SIAM J. on Optimization, 18(1):186–205, February 2007.

[29] Oded Regev and Aravindan Vijayaraghavan. On learning mixtures of well-separated gaussians. In Proceedings of 58th Annual IEEE Symposium on the Foundations of Computer Science, 2017.

[30] Philippe Rigollet and Jan-Christian Hütter. High-dimensional statistics. arXiv preprint arXiv:2310.19244, 2023.

[31] Elad Romanov, Tamir Bendory, and Or Ordentlich. On the role of channel capacity in learning gaussian mixture models. Proceedings of Machine Learning Research vol 178:1–50, 2022.

[32] Mark Rudelson and Roman Vershynin. Hanson-Wright inequality and sub-gaussian concentration. Electron. Commun. Probab, 18(82):1–9, 2013.

[33] Nimrod Segol and Boaz Nadler. Improved convergence guarantees for learning Gaussian mixture models by EM and gradient EM. Electronic Journal of Statistics, 15(2):4510–4544, 2021.

[34] Andrea Tirinzoni and Rémy Degenne. On elimination strategies for bandit fixed-confidence identification. Advances in Neural Information Processing Systems, 35:18586–18598, 2022.

[35] Santosh Vempala and Grant Wang. A spectral algorithm for learning mixture models. Journal of Computer and System Sciences, 68(4):841–860, 2004.

[36] Junwen Yang, Zixin Zhong, and Vincent YF Tan. Optimal clustering with bandit feedback. Journal of Machine Learning Research, 25:1–54, 2024.

[37] Se-Young Yun and Alexandre Proutière. Optimal sampling and clustering in the stochastic block model. Advances in Neural Information Processing Systems, 32, 2019.
[28] Jiming Peng and Yu Wei. Approximating K-means-type Clustering via Semidefinite Programming. SIAM J. on Optimization, 18(1):186–205, February 2007.

[29] Oded Regev and Aravindan Vijayaraghavan. On learning mixtures of well-separated gaussians. In Proceedings of 58th Annual IEEE Symposium on the Foundations of Computer Science, 2017.

[30] Philippe Rigollet and Jan-Christian Hütter. High-dimensional statistics. arXiv preprint arXiv:2310.19244, 2023.

[31] Elad Romanov, Tamir Bendory, and Or Ordentlich. On the role of channel capacity in learning gaussian mixture models. Proceedings of Machine Learning Research vol 178:1–50, 2022.

[32] Mark Rudelson and Roman Vershynin. Hanson-Wright inequality and sub-gaussian concentration. Electron. Commun. Probab, 18(82):1–9, 2013.

[33] Nimrod Segol and Boaz Nadler. Improved convergence guarantees for learning Gaussian mixture models by EM and gradient EM. Electronic Journal of Statistics, 15(2):4510–4544, 2021.

[34] Andrea Tirinzoni and Rémy Degenne. On elimination strategies for bandit fixed-confidence identification. Advances in Neural Information Processing Systems, 35:18586–18598, 2022.

[35] Santosh Vempala and Grant Wang. A spectral algorithm for learning mixture models. Journal of Computer and System Sciences, 68(4):841–860, 2004.

[36] Junwen Yang, Zixin Zhong, and Vincent YF Tan. Optimal clustering with bandit feedback. Journal of Machine Learning Research, 25:1–54, 2024.

[37] Se-Young Yun and Alexandre Proutière. Optimal sampling and clustering in the stochastic block model. Advances in Neural Information Processing Systems, 32, 2019.
# A Details on the numerical experiments

## Experimental setting

We consider artificial data, generated with standard Gaussian noise ($\sigma = 1$). We build environments with equidistant centers, and balanced groups. Precisely, we choose $\mu(k) = e_k/\sqrt{2}$, where $\{e_1, \dots, e_K\}$ are the K first vector of the canonical base of $\mathbb{R}^d$, so that the centers are equidistant, and $\Delta_* = 1$.

We choose a partition where each group has a size $\lfloor N/K \rfloor$ or $\lfloor N/K \rfloor + 1$, which makes the partition almost balanced, with $\theta_* = \frac{1}{N} \lfloor \frac{N}{K} \rfloor \sim \frac{1}{K}$.

Finally, we choose a large number of arms $N = 200$, and a relatively large dimension $d = 1000$. The number of clusters varies in $\{10, 15, 20, 25\}$, and the experiments provided in this paper were ran on these different environments.

## Variant of the procedure and parametrization of ACB

In the main paper, we introduced and calibrated ACB to allow for subGaussian noise. In particular, the quantities $n_s$, $n_{max}$, $I$ and $J$, defined in eqs. (9) to (11) and (13) were calibrated by inverting concentration inequalities, at the cost of non-optimal numerical constants.

In order to study numerically our procedure with sharper constants, we implement a variant of the algorithm whose tuning parameters are adjusted to the Gaussian setting. The test statistics and the classifier, so as the parameters are adjusted to specifically work with Gaussian distribution.

In SRI, we avoid dual sampling for computing $\hat{d}_{ab}$ in order to save a factor two in the budget. We modify the test statistic from line 3 in the function REPRESENTEDTEST used in SRI. We use $\text{IS. TRUE} \left\{ \min_{b \in S} \|\hat{\mu}_a - \bar{\mu}_b\|^2 \le \Delta^2/2 + d\sigma^2 \left( \frac{1}{n_s} + \frac{1}{n_{max}} \right) \right\}$, so that there is no need to compute $\hat{\mu}'_a$ in REPRESENTEDTEST, and neither $\bar{\mu}'_b$ in SRI. Observe that $\|\hat{\mu}_a - \bar{\mu}_b\|^2$ is an estimator of $\|\mu_a - \mu_b\|^2$ which is biased. As in the experiment, the variance is known, we debias it, using the shift $d\sigma^2 \left( \frac{1}{n_s} + \frac{1}{n_{max}} \right)$ in the statistics above.

In order to have a $\delta$-PAC algorithm, we take $n_{max} = 4\frac{\sigma^2}{\Delta^2}(x-d)$, where $x$ is the $1 - \delta/K$ quantile of a $\chi^2$ distribution. This quantile is obtained with the library spipy.stats. As we implement the non-adaptive version of the algorithm, we do not limit the number of candidates, and the budget of SRI in our implementation. The condition from Line 12 in SRI is indeed not used. Now, we choose $n_0, \dots, n_r$, by putting $n_s = \lceil 2^s n_0 \rceil$ for $s = 0, \dots, r$, for all $s$. We choose $n_0$ so that the budget spent on the rejected candidates should be close to the budget spent on the accepted representatives. We choose $n_0 = \lceil (K/U')n_{max} \rceil$ where $U' = (1/\theta) \log(1/\delta)$. Finally, $r$ is chosen such that $n_r = 2^r n_0$ is equal to $n_{max}$, up to a factor 2.

In the Active Distance-based Classification routine (ADC), we also modify the sampling size $I$ and $J$ (eq. (13)), and the classifier from (10). In the classification, we label each arm with $\arg\min_{j=1,...,K} \|\hat{\mu}_a - \hat{\mu}(j)\|$, which is a distance-based classifier as in eq. (14), but without dual sampling. By the analysis of the probability of error of this classifier, we choose

$$I = \left\lceil \frac{\sigma^2}{\Delta^2} \max(16\beta, 4\sqrt{2K/N\alpha}) \right\rceil, \quad J = \left\lceil \frac{\sigma^2}{\Delta^2} \max(16\beta, 4\sqrt{2N/K\alpha}) \right\rceil,$$

where $\beta$ is the $1 - \delta/(4K(N-K))$ quantile of a normal distribution (obtained with spipy.stats), and $\alpha$ is the $1 - \delta/(4K(N-K))$ quantile of a product of independent standard $N(0, I_d)$, that we had to compute empirically with Monte Carlo. With this choice of tuning parameters, one can prove that the corresponding variant of ACB is $\delta$-PAC for Gaussian data. The proof is analogous to the one in Section C. Our numerical experiments confirm that, with these tuning parameters, the modified procedure is still $\delta$-PAC.

## Experiments Compute Resource

We used for the experiments python/Anaconda/3-5.1.0 and the scikit-learn/1.02 package. The experiment were run in the cluster MESO@LR, working with CPUs of 4Gb. To give an idea on the computation cost, for $N, d, K = 200, 1000, 10$, each call for ACB takes approximately 5 minutes. In total, the curve for ACB from fig. 1 took around 9h30 for each value of $K$.
# A Details on the numerical experiments

## Experimental setting

We consider artificial data, generated with standard Gaussian noise ($\sigma = 1$). We build environments with equidistant centers, and balanced groups. Precisely, we choose $\mu(k) = e_k/\sqrt{2}$, where $\{e_1, \dots, e_K\}$ are the K first vector of the canonical base of $\mathbb{R}^d$, so that the centers are equidistant, and $\Delta_* = 1$.

We choose a partition where each group has a size $\lfloor N/K \rfloor$ or $\lfloor N/K \rfloor + 1$, which makes the partition almost balanced, with $\theta_* = \frac{1}{N} \lfloor \frac{N}{K} \rfloor \sim \frac{1}{K}$.

Finally, we choose a large number of arms $N = 200$, and a relatively large dimension $d = 1000$. The number of clusters varies in $\{10, 15, 20, 25\}$, and the experiments provided in this paper were ran on these different environments.

## Variant of the procedure and parametrization of ACB

In the main paper, we introduced and calibrated ACB to allow for subGaussian noise. In particular, the quantities $n_s$, $n_{max}$, $I$ and $J$, defined in eqs. (9) to (11) and (13) were calibrated by inverting concentration inequalities, at the cost of non-optimal numerical constants.

In order to study numerically our procedure with sharper constants, we implement a variant of the algorithm whose tuning parameters are adjusted to the Gaussian setting. The test statistics and the classifier, so as the parameters are adjusted to specifically work with Gaussian distribution.

In SRI, we avoid dual sampling for computing $\hat{d}_{ab}$ in order to save a factor two in the budget. We modify the test statistic from line 3 in the function REPRESENTEDTEST used in SRI. We use $\text{IS.TRUE} \left\{ \min_{b \in S} \|\hat{\mu}_a - \bar{\mu}_b\|^2 \le \Delta^2/2 + d\sigma^2 \left( \frac{1}{n_s} + \frac{1}{n_{max}} \right) \right\}$, so that there is no need to compute $\hat{\mu}'_a$ in REPRESENTEDTEST, and neither $\bar{\mu}'_b$ in SRI. Observe that $\|\hat{\mu}_a - \bar{\mu}_b\|^2$ is an estimator of $\|\mu_a - \mu_b\|^2$ which is biased. As in the experiment, the variance is known, we debias it, using the shift $d\sigma^2 \left( \frac{1}{n_s} + \frac{1}{n_{max}} \right)$ in the statistics above.

In order to have a $\delta$-PAC algorithm, we take $n_{max} = 4\frac{\sigma^2}{\Delta^2}(x-d)$, where $x$ is the $1 - \delta/K$ quantile of a $\chi^2$ distribution. This quantile is obtained with the library spipy.stats. As we implement the non-adaptive version of the algorithm, we do not limit the number of candidates, and the budget of SRI in our implementation. The condition from Line 12 in SRI is indeed not used. Now, we choose $n_0, \dots, n_r$, by putting $n_s = \lceil 2^s n_0 \rceil$ for $s = 0, \dots, r$, for all $s$. We choose $n_0$ so that the budget spent on the rejected candidates should be close to the budget spent on the accepted representatives. We choose $n_0 = \lceil (K/U')n_{max} \rceil$ where $U' = (1/\theta) \log(1/\delta)$. Finally, $r$ is chosen such that $n_r = 2^r n_0$ is equal to $n_{max}$, up to a factor 2.

In the Active Distance-based Classification routine (ADC), we also modify the sampling size $I$ and $J$ (eq. (13)), and the classifier from (10). In the classification, we label each arm with $\arg\min_{j=1,...,K} \|\hat{\mu}_a - \hat{\mu}(j)\|$, which is a distance-based classifier as in eq. (14), but without dual sampling. By the analysis of the probability of error of this classifier, we choose

$$I = \left\lceil \frac{\sigma^2}{\Delta^2} \max(16\beta, 4\sqrt{2K/N\alpha}) \right\rceil, \quad J = \left\lceil \frac{\sigma^2}{\Delta^2} \max(16\beta, 4\sqrt{2N/K\alpha}) \right\rceil,$$

where $\beta$ is the $1 - \delta/(4K(N-K))$ quantile of a normal distribution (obtained with spipy.stats), and $\alpha$ is the $1 - \delta/(4K(N-K))$ quantile of a product of independent standard $N(0, I_d)$, that we had to compute empirically with Monte Carlo. With this choice of tuning parameters, one can prove that the corresponding variant of ACB is $\delta$-PAC for Gaussian data. The proof is analogous to the one in Section C. Our numerical experiments confirm that, with these tuning parameters, the modified procedure is still $\delta$-PAC.

## Experiments Compute Resource

We used for the experiments python/Anaconda/3-5.1.0 and the scikit-learn/1.02 package. The experiment were run in the cluster MESO@LR, working with CPUs of 4Gb. To give an idea on the computation cost, for $N, d, K = 200, 1000, 10$, each call for ACB takes approximately 5 minutes. In total, the curve for ACB from fig. 1 took around 9h30 for each value of $K$.
# B Proof of the Lower Bound

## Sketch of the proof

Throughout Appendix B, we fix $\Delta > 0$, $\sigma$ and $d$. In this section, we bound the worst case budget for any $\delta$-PAC algorithm on the collection of environments $\mathcal{E}(\Delta, \theta, \sigma, N, K, d)$ –see Equation (5), and we prove Theorem 3.1.

We start in Appendix B.1 by reducing the active clustering problem to a binary classification problem. For that purpose, we construct a family of environments, for which, the problem of active clustering essentially reduces to $\lfloor K/2 \rfloor$ independent and identical sub-problems of binary classification. The environments that we construct are symmetrical, (in some sense defined in the proof) and we will explain in Lemma B.7 that we can find an optimal algorithm (as defined in Definition B.6) that samples (in expectation) the same number of time each arm. This construction jointly deals with the low-dimensional (Lemma B.1) and the high-dimensional (Lemma B.2) regimes. For the construction, we will need to assume that $N \ge 2K$, that $K$ is even, and that $K$ divides $N$, and we explain in Lemma B.4 how to reduce to this hypothesis.

We divide then the proof in two main lemmas, dealing with the low-dimensional and high-dimensional regimes. We recall that $T^* - \text{see (5)}$ – is the optimal worst case budget.

**Lemma B.1.** If $N \ge 2K$, $K$ is even, $K$ divides $N$, and $\theta = 1/K$, then for any $\delta \in (0, 1)$,

$$T^*(\delta, \mathcal{E}(\Delta, \theta, \sigma, N, K, d)) \ge \frac{\sigma^2}{\Delta^2} N \text{kl} \left( 1 - \delta, \frac{\delta}{N} \right),$$

where kl is the relative entropy defined as $kl: x, y \mapsto x \log(x/y) + (1-x) \log((1-x)/(1-\delta))$.

**Lemma B.2.** If $N \ge 2K$, $K$ is even, $K$ divides $N$, and $\theta = 1/K$, then for all $\delta \in (0, 1/6)$,

$$T^*(\delta, \mathcal{E}(\Delta, \theta, \sigma, N, K, d)) \ge \frac{\sigma^2}{\Delta^2} \sqrt{\frac{dKN}{72} \text{kl} \left( \frac{1}{3} - 2\delta, \frac{4\delta}{N} \right)}.$$

In Appendix B.2, we prove Lemma B.1, the dimension-free lower bound. It is enough for this term to assume that the centers of the groups are known, and we use an information-theoretic method with the KL-divergence, which is somewhat related to previous works for the thresholding bandit problem derived by [6].

In Appendix B.3, we prove Lemma B.2 in the high-dimensional regime. For this purpose, we will consider a Bayesian setting and assume a Gaussian prior on the centers of the groups. The KL-divergence is hard to compute for the probability induced by the interaction between an algorithm and a Bayesian bandit environment. To overcome this technical problem, we formalize the intuition that the problem of active clustering is in some sense “harder” than a problem of supervised learning where the player knows the labels of every arm except one arm that has to be classified. It will reduce the problem into a two-sample (batch) testing problem (see Definition B.13), and the conclusion will follow from some explicit computation and an impossibility result for this latter batch problem.

We postpone the proofs of some technical lemmas in Appendix B.4

*Remark B.3.* We explain quickly the term $cN$ in the lower bound from Theorem 3.1. Assume that, for any $\nu \in \mathcal{E}(\Delta, \theta, \sigma, N, K, d)$, it holds that $\mathbb{E}_{\pi, \sigma}[\tau] \le cN$ with $c < 1/2$. Then, for any environment $\nu$, there is a fixed probability that two arms from two different groups are not sampled at all during the procedure. The best to do for the learner is then to estimate randomly the groups of the arms, inducing a fixed probability of making at least one error in the clustering. We do not discuss further this term $cN$ in the lower bound in the remainder of the proof. Still, note that it is only relevant in an artificial regime where $\Delta$ is arbitrary large.

Now, we explain how Lemmas B.1 and B.2 and remark B.3 imply Theorem 3.1.

*Proof of Theorem 3.1.* Let $N, K$ such that $N \ge 2K$. Let $\theta > 0$ such that $\mathcal{E}(\Delta, \theta, \sigma, N, K, d) \ne \emptyset$.

We first reduce the problem into a problem where $K$ is even, $N$ is a multiple of $K$, and the groups have the same size $N/K$. With this technical condition fulfilled, we will be able to Lemmas B.1 and B.2. We define $N', K'$, and $\theta'$:

* if $K$ is even, $K' := K$ and $N' := K \lfloor N/K \rfloor$;
# B Proof of the Lower Bound

## Sketch of the proof

Throughout Appendix B, we fix $\Delta > 0$, $\sigma$ and $d$. In this section, we bound the worst case budget for any $\delta$-PAC algorithm on the collection of environments $\mathcal{E}(\Delta, \theta, \sigma, N, K, d)$ –see Equation (5), and we prove Theorem 3.1.

We start in Appendix B.1 by reducing the active clustering problem to a binary classification problem. For that purpose, we construct a family of environments, for which, the problem of active clustering essentially reduces to $\lfloor K/2 \rfloor$ independent and identical sub-problems of binary classification. The environments that we construct are symmetrical, (in some sense defined in the proof) and we will explain in Lemma B.7 that we can find an optimal algorithm (as defined in Definition B.6) that samples (in expectation) the same number of time each arm. This construction jointly deals with the low-dimensional (Lemma B.1) and the high-dimensional (Lemma B.2) regimes. For the construction, we will need to assume that $N \ge 2K$, that $K$ is even, and that $K$ divides $N$, and we explain in Lemma B.4 how to reduce to this hypothesis.

We divide then the proof in two main lemmas, dealing with the low-dimensional and high-dimensional regimes. We recall that $T^* - \text{see (5)}$ – is the optimal worst case budget.

**Lemma B.1.** If $N \ge 2K$, $K$ is even, $K$ divides $N$, and $\theta = 1/K$, then for any $\delta \in (0, 1)$,

$$T^*(\delta, \mathcal{E}(\Delta, \theta, \sigma, N, K, d)) \ge \frac{\sigma^2}{\Delta^2} N \text{kl} \left( 1 - \delta, \frac{\delta}{N} \right),$$

where kl is the relative entropy defined as $kl: x, y \mapsto x \log(x/y) + (1-x) \log((1-x)/(1-\delta))$.

**Lemma B.2.** If $N \ge 2K$, $K$ is even, $K$ divides $N$, and $\theta = 1/K$, then for all $\delta \in (0, 1/6)$,

$$T^*(\delta, \mathcal{E}(\Delta, \theta, \sigma, N, K, d)) \ge \frac{\sigma^2}{\Delta^2} \sqrt{\frac{dKN}{72} \text{kl} \left( \frac{1}{3} - 2\delta, \frac{4\delta}{N} \right)}.$$

In Appendix B.2, we prove Lemma B.1, the dimension-free lower bound. It is enough for this term to assume that the centers of the groups are known, and we use an information-theoretic method with the KL-divergence, which is somewhat related to previous works for the thresholding bandit problem derived by [6].

In Appendix B.3, we prove Lemma B.2 in the high-dimensional regime. For this purpose, we will consider a Bayesian setting and assume a Gaussian prior on the centers of the groups. The KL-divergence is hard to compute for the probability induced by the interaction between an algorithm and a Bayesian bandit environment. To overcome this technical problem, we formalize the intuition that the problem of active clustering is in some sense “harder” than a problem of supervised learning where the player knows the labels of every arm except one arm that has to be classified. It will reduce the problem into a two-sample (batch) testing problem (see Definition B.13), and the conclusion will follow from some explicit computation and an impossibility result for this latter batch problem.

We postpone the proofs of some technical lemmas in Appendix B.4

*Remark B.3.* We explain quickly the term $cN$ in the lower bound from Theorem 3.1. Assume that, for any $\nu \in \mathcal{E}(\Delta, \theta, \sigma, N, K, d)$, it holds that $\mathbb{E}_{\pi, \sigma}[\tau] \le cN$ with $c < 1/2$. Then, for any environment $\nu$, there is a fixed probability that two arms from two different groups are not sampled at all during the procedure. The best to do for the learner is then to estimate randomly the groups of the arms, inducing a fixed probability of making at least one error in the clustering. We do not discuss further this term $cN$ in the lower bound in the remainder of the proof. Still, note that it is only relevant in an artificial regime where $\Delta$ is arbitrary large.

Now, we explain how Lemmas B.1 and B.2 and remark B.3 imply Theorem 3.1.

*Proof of Theorem 3.1.* Let $N, K$ such that $N \ge 2K$. Let $\theta > 0$ such that $\mathcal{E}(\Delta, \theta, \sigma, N, K, d) \ne \emptyset$.

We first reduce the problem into a problem where $K$ is even, $N$ is a multiple of $K$, and the groups have the same size $N/K$. With this technical condition fulfilled, we will be able to Lemmas B.1 and B.2. We define $N', K'$, and $\theta'$:

* if $K$ is even, $K' := K$ and $N' := K \lfloor N/K \rfloor$;
• if $K$ is odd, $K' := K - 1$ and $N' = K' \lfloor \frac{N - \lfloor \theta N \rfloor}{K'} \rfloor$;

• in both cases, $\theta' := 1/K'$.

We now use the following natural reduction result, whose proof is in Appendix B.4.1.

**Lemma B.4.** The optimal worst case budget over $\mathcal{E}(\Delta, \theta, \sigma, N, K, d)$ is larger than the one over $\mathcal{E}(\Delta, \theta', \sigma, N', K', d)$,

$$T^*(\delta, \mathcal{E}(\Delta, \theta, \sigma, N, K, d)) \geq T^*(\delta, \mathcal{E}(\Delta, \theta', \sigma, N', K', d)).$$

It holds immediately that that $K'$ is even, and that $K'$ divides $N'$. Moreover, as $\mathcal{E}(\Delta, \theta, \sigma, N, K, d) \neq \emptyset$, then $\lfloor \theta N \rfloor \leq N/K$. This inequality and the assumption $N \geq 2K$, implies that $N' \geq 2K'$. We can then use Lemma B.1 and Lemma B.2 with $N'$ and $K'$ in order to bound $T^*(\delta, \mathcal{E}(\Delta, \theta', N', K', d))$.

We have for any $\delta \in (0, 1/6)$,

$$T^*(\delta, \mathcal{E}(\Delta, \theta', \sigma, N', K', d)) \geq \frac{\sigma^2}{\Delta^2} N' \mathrm{kl}\left(1 - \delta, \frac{\delta}{N'}\right) \vee \frac{\sigma^2}{\Delta^2} \sqrt{\frac{dK'N'}{72}} \mathrm{kl}\left(\frac{1}{3} - 2\delta, \frac{4\delta}{N'}\right).$$

We can also easily deduce from the expression of $N'$ that $N' \geq N/6$.

Finally, we study $\delta \mapsto \mathrm{kl}(1 - \delta, 2\delta/N')$ to obtain the bound valid for all $\delta \in (0, 1)$ and for all $N' \geq 1$,

$$\mathrm{kl}\left(1 - \delta, \frac{2\delta}{N'}\right) \geq \log\left(\frac{1}{\delta}\right) + \log(N')(1 - \delta) - 1.5.$$

In particular, we have the bound $\mathrm{kl}(1 - \delta, \frac{2\delta}{N'}) \geq \frac{1}{2}\log(N'/\delta)$ for $\delta \in (0, 1/4)$.

By studying the variation of $\delta \mapsto \mathrm{kl}(1/3 - 2\delta, 4\delta/N')$, we obtain the bound valid for all $\delta \in (0, 1/6)$ and for all $N'$,

$$\mathrm{kl}\left(\frac{1}{3} - 2\delta, \frac{4\delta}{N'}\right) \geq \frac{1}{3}\left[\log\left(\frac{1}{4\delta}\right) + \log(N')(1 - 6\delta)\right] - 0.7.$$

Combining all these inequalities and Remark B.3, we obtain Theorem 3.1. $\square$

## B.1 From active clustering to binary classification

### B.1.1 Construction of a family of environments

From now on, we assume that $K$ is even, and $N/K$ is an integer. In all the proof, we only consider perfectly balanced environments such that $\theta = 1/K$. We also assume that $N \geq 2K$. Define $L := \lfloor K/2 \rfloor$. In this subsection, we construct a family of environments defined with a prior on the centers of the groups.

We assume that the noises are Gaussian with covariance matrix $\sigma^2 I_d$. This fulfills the subGaussian noise hypothesis from Assumption 2.1. In this Gaussian model, an environment is characterized by the hidden partition $G^*$ and the (distinct) centers of the groups.

We use a Bayesian approach, and we define the $K = 2L$ centers of the groups, that we order as $\mu_{1,1}, \mu_{1,-1}, \dots, \mu_{L,1}, \mu_{L,-1}$. For all $l \in [L]$, we construct the centers $\mu_{l,1}$ and $\mu_{l,-1}$ as symmetrical with respect to some offset. More specifically, for all $(l, g) \in [L] \times \{-1, 1\}$, we define

$$\mu_{l,g} := g\bar{\mu}(l) + C(l), \qquad (17)$$

where

• for all $l \in [L]$, $C(l) \in \mathbb{R}^d$ is a fixed offset defined as $C(l) = \beta(l\Delta, 0, \dots, 0) \in \mathbb{R}^d$;

• $\beta > 1$ will be fixed later and is arbitrary large;

• $\bar{\mu} := \bar{\mu}(1), \dots, \bar{\mu}(L)$ are i.i.d and $\bar{\mu}(l) \sim \gamma$. The prior distribution $\gamma$ over $\mathbb{R}^d$ will be set differently if we consider the low or high-dimensional regime. We will specify later this prior.
* if $K$ is odd, $K' := K - 1$ and $N' = K' \lfloor \frac{N - \lfloor \theta N \rfloor}{K'} \rfloor$;

* in both cases, $\theta' := 1/K'$.

We now use the following natural reduction result, whose proof is in Appendix B.4.1.

**Lemma B.4.** The optimal worst case budget over $\mathcal{E}(\Delta, \theta, \sigma, N, K, d)$ is larger than the one over $\mathcal{E}(\Delta, \theta', \sigma, N', K', d)$,

$$T^*(\delta, \mathcal{E}(\Delta, \theta, \sigma, N, K, d)) \geq T^*(\delta, \mathcal{E}(\Delta, \theta', \sigma, N', K', d)).$$

It holds immediately that that $K'$ is even, and that $K'$ divides $N'$. Moreover, as $\mathcal{E}(\Delta, \theta, \sigma, N, K, d) \neq \emptyset$, then $\lfloor \theta N \rfloor \leq N/K$. This inequality and the assumption $N \geq 2K$, implies that $N' \geq 2K'$. We can then use Lemma B.1 and Lemma B.2 with $N'$ and $K'$ in order to bound $T^*(\delta, \mathcal{E}(\Delta, \theta', N', K', d))$.

We have for any $\delta \in (0, 1/6)$,

$$T^*(\delta, \mathcal{E}(\Delta, \theta', \sigma, N', K', d)) \geq \frac{\sigma^2}{\Delta^2} N' \mathrm{kl}\left(1 - \delta, \frac{\delta}{N'}\right) \vee \frac{\sigma^2}{\Delta^2} \sqrt{\frac{dK'N'}{72}} \mathrm{kl}\left(\frac{1}{3} - 2\delta, \frac{4\delta}{N'}\right).$$

We can also easily deduce from the expression of $N'$ that $N' \geq N/6$.

Finally, we study $\delta \mapsto \mathrm{kl}(1 - \delta, 2\delta/N')$ to obtain the bound valid for all $\delta \in (0, 1)$ and for all $N' \geq 1$,

$$\mathrm{kl}\left(1 - \delta, \frac{2\delta}{N'}\right) \geq \log\left(\frac{1}{\delta}\right) + \log(N')(1 - \delta) - 1.5.$$

In particular, we have the bound $\mathrm{kl}(1 - \delta, \frac{2\delta}{N'}) \geq \frac{1}{2}\log(N'/\delta)$ for $\delta \in (0, 1/4)$.

By studying the variation of $\delta \mapsto \mathrm{kl}(1/3 - 2\delta, 4\delta/N')$, we obtain the bound valid for all $\delta \in (0, 1/6)$ and for all $N'$,

$$\mathrm{kl}\left(\frac{1}{3} - 2\delta, \frac{4\delta}{N'}\right) \geq \frac{1}{3}\left[\log\left(\frac{1}{4\delta}\right) + \log(N')(1 - 6\delta)\right] - 0.7.$$

Combining all these inequalities and Remark B.3, we obtain Theorem 3.1. $\square$

# B.1 From active clustering to binary classification

## B.1.1 Construction of a family of environments

From now on, we assume that $K$ is even, and $N/K$ is an integer. In all the proof, we only consider perfectly balanced environments such that $\theta = 1/K$. We also assume that $N \geq 2K$. Define $L := \lfloor K/2 \rfloor$. In this subsection, we construct a family of environments defined with a prior on the centers of the groups.

We assume that the noises are Gaussian with covariance matrix $\sigma^2 I_d$. This fulfills the subGaussian noise hypothesis from Assumption 2.1. In this Gaussian model, an environment is characterized by the hidden partition $G^*$ and the (distinct) centers of the groups.

We use a Bayesian approach, and we define the $K = 2L$ centers of the groups, that we order as $\mu_{1,1}, \mu_{1,-1}, \dots, \mu_{L,1}, \mu_{L,-1}$. For all $l \in [L]$, we construct the centers $\mu_{l,1}$ and $\mu_{l,-1}$ as symmetrical with respect to some offset. More specifically, for all $(l, g) \in [L] \times \{-1, 1\}$, we define

$$\mu_{l,g} := g\bar{\mu}(l) + C(l), \qquad (17)$$

where

* for all $l \in [L]$, $C(l) \in \mathbb{R}^d$ is a fixed offset defined as $C(l) = \beta(l\Delta, 0, \dots, 0) \in \mathbb{R}^d$;

* $\beta > 1$ will be fixed later and is arbitrary large;

* $\bar{\mu} := \bar{\mu}(1), \dots, \bar{\mu}(L)$ are i.i.d and $\bar{\mu}(l) \sim \gamma$. The prior distribution $\gamma$ over $\mathbb{R}^d$ will be set differently if we consider the low or high-dimensional regime. We will specify later this prior.
Through the proof, we fix a partition $G^*$ of $[N]$ into $K$ groups. The partition $G^*$ is composed of $K = 2L$ nonempty groups $G^*_{1,1}, G^*_{1,-1}, \dots, G^*_{L,1}, G^*_{L,-1}$ associated to the means $\mu_{1,1}, \mu_{1,-1}, \dots, \mu_{L,1}, \mu_{L,-1}$. For each arm $a \in [N]$, we denote as $(l_a^*, g_a^*) \in [L] \times \{-1, 1\}$ for the labels such that $a \in G^*_{l_a^*, g_a^*}$ and $\mu_a = \mu_{l_a^*, g_a^*}$. Also, we will always restrict ourselves to balanced partitions $G^*$ so that each group $G^*_{l,g}$ has the same size $N/K$ and thus $\theta_* = 1/K$.

In summary, we have

$$[N] = \bigsqcup_{(l,g) \in [L] \times \{-1,1\}} G^*_{l,g},$$

where the groups $(G^*_{l,g})$ are nonempty and share the same size $N/K$.

We also define the so-called L "blocks". For $l \in [L]$, we define $G^*_l := \{a \in [N] ; l_a^* = l\} = G^*_{l,1} \sqcup G^*_{l,-1}$. For each arm $a \in [N]$, $l_a^*$ corresponds to the label of the pair of groups (block) $G^*_l$ that contains $a$. If $l_a^* = l$, then the arm $a$ belongs either to $G^*_{l,1}$ or $G^*_{l,-1}$ depending on the value of $g_a^* \in \{-1, 1\}$. We also denote as $G^+_+ := \{a \in [L]; g_a^* = +1\}$.

We now construct a set of partitions obtained from $G^*$ by switching two arms from the two different groups of the same block. Arbitrarily define a set $\{s(1), \dots, s(L)\}$ of arms such that for all $l \in [L]$, $s(l) \in G^*_{l,-1}$. For any arm $a \in [N]$, we write $b_a := s(l_a^*)$. For an arm $a$ in $G^+_+ = \{a \in [L]; g_a^* = +1\}$, we define $G^*_{(a)}$ as the partition equal to $G^*$ except that the arm $a$ is switched from $G^*_{l_a^*, 1}$ to $G^*_{l_a^*, -1}$, and the arm $b_a$ is switched from $G^*_{l_a^*, -1}$ to $G^*_{l_a^*, +1}$. This is a valid partition with $K$ nonempty and perfectly balanced groups. As we took $N \ge 2K$, it holds that, if any two distinct partition $G$ and $G'$ belong to $\{G^*\} \cup \{G^*_{(a)}\}_{a \in G^+_+}$, we have $G \not\sim G'$. As a consequence, any $\delta$-PAC algorithm distinguishes, with probability higher than $1 - \delta$, whether the environments are characterized by a partition $G^*$ or by some $(G^*_{a})_{a \in G^+_+}$.

For any partition $G'$ such that $[N] = \sqcup_{l,g} G'_{l,g}$, we denote as $\nu(G', \bar{\mu})$ for the environment constructed in this paragraph with the means $(\mu_{l,g})_{l,g} = (C(l) + g\bar{\mu}(l))$ and $\bar{\mu} \in \mathbb{R}^d$. We will use $\mathbb{P}_{\pi,G',\bar{\mu}}$ [resp. $\mathbb{E}_{\pi,G',\bar{\mu}}$] for the probability distribution [resp expectation] induced by the interaction between an algorithm $\pi$ and the environment $\nu(G', \bar{\mu})$ for a fixed realization of $\bar{\mu}$. We also denote as $\mathbb{P}_{\pi,G'} = \int_{\bar{\mu}} \mathbb{P}_{\pi,G',\bar{\mu}} d\gamma^{\otimes L}(\bar{\mu})$ [resp. $\mathbb{E}_{\pi,G'}$] as the integrated probability with respect to the prior $\gamma^{\otimes L}$ on $\bar{\mu}$ [resp expectation].

There is a technical detail that has to be handled with this Bayesian prior, if $\bar{\mu}_l$ is too small or too large, the environment $\nu(G', \bar{\mu})$ is not necessary in $\mathcal{E}(\Delta, \theta, \sigma, N, K, d)$. We define therefore $\mathcal{Y} := \bigcap_{l \in [L]} \{\Delta/2 \le \|\bar{\mu}(l)\| \le \Delta(\beta - 1)/2\}$. On $\mathcal{Y}$, the centers are distinct, the minimal gap is larger than $\Delta$, and the set of possible values for $(\bar{\mu}(l))_l$ are disjoint.

We denote $\mathcal{E}_{Ssym}(G^*, \gamma)$ as the Bayesian family of environments of the form $\nu(G', \bar{\mu})$, where $\bar{\mu} \sim \gamma^{\otimes L}$ and the partitions $G' \in \{G^*\} \cup \bigcup_{a \in G^+_+} \{G^*_{(a)}\}$.

We explain a bit more the construction.

**Remark B.5.** 1. The parameter $\beta$ will be arbitrary large so that it is very easy to decide if two arms belong to different blocks or not. In this case, it is intuitively easy to first separate the arms into $L$ blocks (that means to estimate $l_1^*, \dots, l_N^*$). Then the difficulty of the problem mostly lies in the $L$ sub-problems of binary classification, where each block has to be partition into two groups.

2. In the low-dimensional regime, we will take $\bar{\mu}(l) = (\Delta/2, 0, \dots, 0)$ ($\gamma$ is deterministic). It means that we will derive the lower bound from Lemma B.1 for fixed centers of the groups $\mu(1), \dots, \mu(K)$ which basically amounts to the simpler setting where the learner knows the centers in advance.

3. In the high-dimensional regime, we will use a Gaussian prior on $(\bar{\mu}(l))_{l \in [L]}$. With this prior, we will be able to quantify to what extent we have to estimate the unknown means $(\bar{\mu}(l))_{l \in [L]}$ to be able to group the arms.
Through the proof, we fix a partition $G^*$ of $[N]$ into $K$ groups. The partition $G^*$ is composed of $K = 2L$ nonempty groups $G^*_{1,1}, G^*_{1,-1}, \dots, G^*_{L,1}, G^*_{L,-1}$ associated to the means $\mu_{1,1}, \mu_{1,-1}, \dots, \mu_{L,1}, \mu_{L,-1}$. For each arm $a \in [N]$, we denote as $(l_a^*, g_a^*) \in [L] \times \{-1, 1\}$ for the labels such that $a \in G^*_{l_a^*, g_a^*}$ and $\mu_a = \mu_{l_a^*, g_a^*}$. Also, we will always restrict ourselves to balanced partitions $G^*$ so that each group $G^*_{l,g}$ has the same size $N/K$ and thus $\theta_* = 1/K$.

In summary, we have

$$[N] = \bigsqcup_{(l,g) \in [L] \times \{-1, 1\}} G^*_{l,g},$$

where the groups $(G^*_{l,g})$ are nonempty and share the same size $N/K$.

We also define the so-called L "blocks". For $l \in [L]$, we define $G^*_l := \{a \in [N] ; l_a^* = l\} = G^*_{l,1} \sqcup G^*_{l,-1}$. For each arm $a \in [N]$, $l_a^*$ corresponds to the label of the pair of groups (block) $G^*_l$ that contains $a$. If $l_a^* = l$, then the arm $a$ belongs either to $G^*_{l,1}$ or $G^*_{l,-1}$ depending on the value of $g_a^* \in \{-1, 1\}$. We also denote as $G^+_+ := \{a \in [L]; g_a^* = +1\}$.

We now construct a set of partitions obtained from $G^*$ by switching two arms from the two different groups of the same block. Arbitrarily define a set $\{s(1), \dots, s(L)\}$ of arms such that for all $l \in [L]$, $s(l) \in G^*_{l,-1}$. For any arm $a \in [N]$, we write $b_a := s(l_a^*)$. For an arm $a$ in $G^+_+ = \{a \in [L]; g_a^* = +1\}$, we define $G^*_{(a)}$ as the partition equal to $G^*$ except that the arm $a$ is switched from $G^*_{l_a^*, 1}$ to $G^*_{l_a^*, -1}$, and the arm $b_a$ is switched from $G^*_{l_a^*, -1}$ to $G^*_{l_a^*, +1}$. This is a valid partition with $K$ nonempty and perfectly balanced groups. As we took $N \ge 2K$, it holds that, if any two distinct partition $G$ and $G'$ belong to $\{G^*\} \cup \{G^*_{(a)}\}_{a \in G^+_+}$, we have $G \not\sim G'$. As a consequence, any $\delta$-PAC algorithm distinguishes, with probability higher than $1 - \delta$, whether the environments are characterized by a partition $G^*$ or by some $(G^*_{a})_{a \in G^+_+}$.

For any partition $G'$ such that $[N] = \sqcup_{l,g} G'_{l,g}$, we denote as $\nu(G', \bar{\mu})$ for the environment constructed in this paragraph with the means $(\mu_{l,g})_{l,g} = (C(l) + g\bar{\mu}(l))$ and $\bar{\mu} \in \mathbb{R}^d$. We will use $\mathbb{P}_{\pi,G',\bar{\mu}}$ [resp. $\mathbb{E}_{\pi,G',\bar{\mu}}$] for the probability distribution [resp expectation] induced by the interaction between an algorithm $\pi$ and the environment $\nu(G', \bar{\mu})$ for a fixed realization of $\bar{\mu}$. We also denote as $\mathbb{P}_{\pi,G'} = \int_{\bar{\mu}} \mathbb{P}_{\pi,G',\bar{\mu}} d\gamma^{\otimes L}(\bar{\mu})$ [resp. $\mathbb{E}_{\pi,G'}$] as the integrated probability with respect to the prior $\gamma^{\otimes L}$ on $\bar{\mu}$ [resp expectation].

There is a technical detail that has to be handled with this Bayesian prior, if $\bar{\mu}_l$ is too small or too large, the environment $\nu(G', \bar{\mu})$ is not necessary in $\mathcal{E}(\Delta, \theta, \sigma, N, K, d)$. We define therefore $\mathcal{Y} := \bigcap_{l \in [L]} \{\Delta/2 \le \|\bar{\mu}(l)\| \le \Delta(\beta - 1)/2\}$. On $\mathcal{Y}$, the centers are distinct, the minimal gap is larger than $\Delta$, and the set of possible values for $(\bar{\mu}(l))_l$ are disjoint.

We denote $\mathcal{E}_{Ssym}(G^*, \gamma)$ as the Bayesian family of environments of the form $\nu(G', \bar{\mu})$, where $\bar{\mu} \sim \gamma^{\otimes L}$ and the partitions $G' \in \{G^*\} \cup \bigcup_{a \in G^+_+} \{G^*_{(a)}\}$.

We explain a bit more the construction.

**Remark B.5.** 1. The parameter $\beta$ will be arbitrary large so that it is very easy to decide if two arms belong to different blocks or not. In this case, it is intuitively easy to first separate the arms into $L$ blocks (that means to estimate $l_1^*, \dots, l_N^*$). Then the difficulty of the problem mostly lies in the $L$ sub-problems of binary classification, where each block has to be partition into two groups.

2. In the low-dimensional regime, we will take $\bar{\mu}(l) = (\Delta/2, 0, \dots, 0)$ ($\gamma$ is deterministic). It means that we will derive the lower bound from Lemma B.1 for fixed centers of the groups $\mu(1), \dots, \mu(K)$ which basically amounts to the simpler setting where the learner knows the centers in advance.

3. In the high-dimensional regime, we will use a Gaussian prior on $(\bar{\mu}(l))_{l \in [L]}$. With this prior, we will be able to quantify to what extent we have to estimate the unknown means $(\bar{\mu}(l))_{l \in [L]}$ to be able to group the arms.
## B.1.2 Symmetrization

Now, we exploit the different symmetries of the environments of the shape $\nu(G', \bar{\mu})$, and the symmetries of the distribution of the centers when $\bar{\mu} \sim \gamma$, in order to restrict our study to algorithms that are $\delta$-PAC on $\mathcal{E}_{Sym}(G^*, \gamma)$ and that satisfies a symmetry property defined below.

**Definition B.6.** We say that $\pi$ is $\delta$-PAC on $\mathcal{E}_{Sym}(G^*, \gamma)$, if, conditionally on the event $\mathcal{Y}$, we have

$$ \mathbb{P}_{\pi, G'}(\hat{G} \sim G'|\mathcal{Y}) \geq 1 - \delta, $$

for any $G' \in \{G^*\} \cup \{G^*_{(a)}\}_{a \in G^*}$. We say that an algorithm $\pi$ is symmetric on $\mathcal{E}_{Sym}(G^*, \gamma)$, if for any $b \in [N]$ and $G' \in \{G^*\} \cup \{G^*_{(a)}\}_{a \in G^*}$, then

$$ \mathbb{E}_{\pi, G'}[N_b(\tau)|\mathcal{Y}] = \frac{1}{N} \mathbb{E}_{\pi, G'}[\tau|\mathcal{Y}] = \frac{1}{N} \mathbb{E}_{\pi, G^*}[\tau|\mathcal{Y}]. $$

We denote as $\Pi_{Sym}(\delta, \mathcal{E}_{Sym}(G^*, \gamma))$ for the family of symmetric and $\delta$-PAC algorithms on $\mathcal{E}_{Sym}(G^*, \gamma)$.

Finally, we define the optimal Bayesian budget for an algorithm in $\Pi_{Sym}(\delta, \mathcal{E}_{Sym}(G^*, \gamma))$ as

$$ T^*(\delta, \mathcal{E}_{Sym}(G^*, \gamma)) := \inf_{\pi \in \Pi_{Sym}} \mathbb{E}_{\pi, G^*}[\tau|\mathcal{Y}], $$

where the inf is taken over $\Pi_{Sym}(\delta, \mathcal{E}_{Sym}(G^*, \gamma))$, recalling that $\mathbb{E}_{\pi, G^*}$ is the integrated budget with respect to the prior $\gamma$.

The next lemma implies that we only need to lower bound the quantity $T^*_{Sym}(\delta, \mathcal{E}_{Sym}(G^*, \gamma))$.

**Lemma B.7.** If $K$ is even, $K$ divides $N$, $\theta = 1/K$, and $N \ge 2K$, it holds that

$$ T^*(\delta, \mathcal{E}(\Delta, \theta, \sigma, N, K, d)) \ge T^*_{Sym}(\delta, \mathcal{E}_{Sym}(G^*, \gamma)). $$

*Remark B.8.* We highlight that this construction essentially reduces the problem into $L$ sub-problems of active binary classification. On the family of environments $\mathcal{E}_{Sym}(G^*, \gamma)$, the offsets $C_1, \dots, C_L$ and the labels of the blocks $l_1^*, \dots, l_N^*$ are fixed and common to all the environments $\nu(G^*, \bar{\mu})$ and $\nu(G^*_{(a)}, \bar{\mu})$, it is equivalent to say that this is known by the learner. Then, the problem consists on estimating the partition into two groups $G_l^* = G_{l,1}^* \cup G_{l,-1}^*$ (up to switching of the two groups) for any of the $L$ blocks. If an algorithm is symmetric, it will have access in expectation to the same budget to solve each sub-problem.

The proof of this Lemma, technical but standard is provided in Appendix B.4.2. In the proof, we explain how to use the knowledge of the blocks $G_1^*, \dots, G_L^*$ and the offsets $C(1), \dots, C(l)$ in order to transform any algorithm into a symmetric algorithm – see Definition B.6. The rough idea is to permute the arms, and then to apply the algorithm to the permuted arms.

## B.2 First Lower bound : proof of Lemma B.1

In this section, we prove the Lower Bound from Lemma B.1. We highlight that the lower bound from Lemma B.1 does not depend on the dimension $d$. Thus, we will derive lower bound for fixed centers of the groups which basically amounts to the simpler setting where the learner knows them in advance.

We use the construction of Appendix B.1, and we choose the prior distribution $\gamma_1 := \delta_\mu$ to be a Dirac, i.e, $\bar{\mu}(l) = \mu$ for all $l$ and the centers are deterministic and fixed. We choose $\mu = (\Delta/2, 0, \dots, 0) \in \mathbb{R}^d$ and $\beta = 2$. The environment $\nu(G^*, \bar{\mu})$ is in $\mathcal{E}(\Delta, \theta, \sigma, N, K, d)$, so the event $\mathcal{Y}$ from Definition B.6 holds almost surely.

*Remark B.9.* The active clustering problem on $\mathcal{E}_{Sym}(G^*, \gamma)$ is highly connected to a specific instance of the Thresholding Bandit Problem (TBP), another pure exploration problem studied in [6]. In this problem, a player interacts with a multi-armed bandit environment with one-dimensional rewards, and she has to recover the set of arms with a mean larger or equal to a certain threshold (for us, this threshold is $\Delta$). The proof of Lemma B.1 is inspired by the proof of Theorem 1 in [6]. For the thresholding bandit problem, the authors derive a lower bound in the fixed budget setting. In this setting, the player has to minimize the simple regret (related to the probability of error), using a fixed budget. From their result, we could deduce a lower bound of the form $\frac{\sigma^2}{\Delta^2}(N-K) \log(\frac{N-K}{\delta})$. Here, we use a workaround to establish a slightly tighter lower bound of the form $\frac{\sigma^2}{\Delta^2}N \log(\frac{N}{\delta})$.
### B.1.2 Symmetrization

Now, we exploit the different symmetries of the environments of the shape $\nu(G', \bar{\mu})$, and the symmetries of the distribution of the centers when $\bar{\mu} \sim \gamma$, in order to restrict our study to algorithms that are $\delta$-PAC on $\mathcal{E}_{Sym}(G^*, \gamma)$ and that satisfies a symmetry property defined below.

**Definition B.6.** We say that $\pi$ is $\delta$-PAC on $\mathcal{E}_{Sym}(G^*, \gamma)$, if, conditionally on the event $\mathcal{Y}$, we have

$$ \mathbb{P}_{\pi, G'}(\hat{G} \sim G'|\mathcal{Y}) \ge 1 - \delta, $$

for any $G' \in \{G^*\} \cup \{G^*_{(a)}\}_{a \in G^*}$. We say that an algorithm $\pi$ is symmetric on $\mathcal{E}_{Sym}(G^*, \gamma)$, if for any $b \in [N]$ and $G' \in \{G^*\} \cup \{G^*_{(a)}\}_{a \in G^*}$, then

$$ \mathbb{E}_{\pi, G'}[N_b(\tau)|\mathcal{Y}] = \frac{1}{N} \mathbb{E}_{\pi, G'}[\tau|\mathcal{Y}] = \frac{1}{N} \mathbb{E}_{\pi, G^*}[\tau|\mathcal{Y}]. $$

We denote as $\Pi_{Sym}(\delta, \mathcal{E}_{Sym}(G^*, \gamma))$ for the family of symmetric and $\delta$-PAC algorithms on $\mathcal{E}_{Sym}(G^*, \gamma)$.

Finally, we define the optimal Bayesian budget for an algorithm in $\Pi_{Sym}(\delta, \mathcal{E}_{Sym}(G^*, \gamma))$ as

$$ T^*(\delta, \mathcal{E}_{Sym}(G^*, \gamma)) := \inf_{\pi \in \Pi_{Sym}} \mathbb{E}_{\pi, G^*}[\tau|\mathcal{Y}], $$

where the inf is taken over $\Pi_{Sym}(\delta, \mathcal{E}_{Sym}(G^*, \gamma))$, recalling that $\mathbb{E}_{\pi, G^*}$ is the integrated budget with respect to the prior $\gamma$.

The next lemma implies that we only need to lower bound the quantity $T^*_{Sym}(\delta, \mathcal{E}_{Sym}(G^*, \gamma))$.

**Lemma B.7.** If $K$ is even, $K$ divides $N$, $\theta = 1/K$, and $N \ge 2K$, it holds that

$$ T^*(\delta, \mathcal{E}(\Delta, \theta, \sigma, N, K, d)) \ge T^*_{Sym}(\delta, \mathcal{E}_{Sym}(G^*, \gamma)). $$

**Remark B.8.** We highlight that this construction essentially reduces the problem into $L$ sub-problems of active binary classification. On the family of environments $\mathcal{E}_{Sym}(G^*, \gamma)$, the offsets $C_1, \dots, C_L$ and the labels of the blocks $l_1^*, \dots, l_N^*$ are fixed and common to all the environments $\nu(G^*, \bar{\mu})$ and $\nu(G^*_{(a)}, \bar{\mu})$, it is equivalent to say that this is known by the learner. Then, the problem consists on estimating the partition into two groups $G_l^* = G_{l,1}^* \cup G_{l,-1}^*$ (up to switching of the two groups) for any of the $L$ blocks. If an algorithm is symmetric, it will have access in expectation to the same budget to solve each sub-problem.

The proof of this Lemma, technical but standard is provided in Appendix B.4.2. In the proof, we explain how to use the knowledge of the blocks $G_1^*, \dots, G_L^*$ and the offsets $C(1), \dots, C(l)$ in order to transform any algorithm into a symmetric algorithm – see Definition B.6. The rough idea is to permute the arms, and then to apply the algorithm to the permuted arms.

## B.2 First Lower bound : proof of Lemma B.1

In this section, we prove the Lower Bound from Lemma B.1. We highlight that the lower bound from Lemma B.1 does not depend on the dimension $d$. Thus, we will derive lower bound for fixed centers of the groups which basically amounts to the simpler setting where the learner knows them in advance.

We use the construction of Appendix B.1, and we choose the prior distribution $\gamma_1 := \delta_\mu$ to be a Dirac, i.e, $\bar{\mu}(l) = \mu$ for all $l$ and the centers are deterministic and fixed. We choose $\mu = (\Delta/2, 0, \dots, 0) \in \mathbb{R}^d$ and $\beta = 2$. The environment $\nu(G^*, \bar{\mu})$ is in $\mathcal{E}(\Delta, \theta, \sigma, N, K, d)$, so the event $\mathcal{Y}$ from Definition B.6 holds almost surely.

**Remark B.9.** The active clustering problem on $\mathcal{E}_{Sym}(G^*, \gamma)$ is highly connected to a specific instance of the Thresholding Bandit Problem (TBP), another pure exploration problem studied in [6]. In this problem, a player interacts with a multi-armed bandit environment with one-dimensional rewards, and she has to recover the set of arms with a mean larger or equal to a certain threshold (for us, this threshold is $\Delta$). The proof of Lemma B.1 is inspired by the proof of Theorem 1 in [6]. For the thresholding bandit problem, the authors derive a lower bound in the fixed budget setting. In this setting, the player has to minimize the simple regret (related to the probability of error), using a fixed budget. From their result, we could deduce a lower bound of the form $\frac{\sigma^2}{\Delta^2}(N-K) \log(\frac{N-K}{\delta})$. Here, we use a workaround to establish a slightly tighter lower bound of the form $\frac{\sigma^2}{\Delta^2}N \log(\frac{N}{\delta})$.
We consider $T_{Sym}^*(\delta, \mathcal{E}_{Sym}(G^*, \gamma_1)) = \inf_{\pi \in \Pi_{Sym}} \mathbb{E}_{\pi, G^*}[\tau]$ where the inf is taken over all symmetric and $\delta$-PAC algorithm on $\mathcal{E}_{Sym}(G^*, \gamma_1)$ -see Definition B.6.

**Lemma B.10.** If K is even, K divides N and $N \ge K$, then,

$$T_{Sym}^*(\delta, \mathcal{E}_{Sym}(G^*, \gamma_1)) \ge N \frac{\sigma^2}{\Delta^2} \mathrm{kl} \left( 1 - \delta, \frac{2\delta}{N} \right).$$

Then, Lemma B.1 simply follows from the reduction arguments of B.7 and lemma B.10 that we prove now.

*Proof of lemma B.10.* Let $\pi$ be a symmetric and $\delta$-PAC algorithm for the active clustering problem on $\mathcal{E}_{Sym}(G^*, \gamma_1)$. It outputs a partition $\hat{G}$ of $[N]$ such that for any $a \in G_+^*$,

$$\mathbb{P}_{\pi, G_{(a)}^*}(\hat{G} \sim G_{(a)}^*) \ge 1 - \delta, \text{ and}$$

$$\mathbb{P}_{\pi, G^*}(\hat{G} \sim G^*) \ge 1 - \delta.$$

The main tool that we use is a data-processing inequality– see e.g.[14]. We will use the KL-divergence which, in our setting, turns out to be explicitly computed. The difficulty of the proof is to recover the term $\log(N/\delta)$ in the lower bound of the budget. For that, we adapt the proof page 15 of [6] to the fixed confidence setting. The idea is that, instead of constructing one partition, different from $G^*$, we constructed a collection of $\{G_{(a)}^*\}_{a \in G_+^*}$, where any algorithm has to distinguish $G^*$ from any of these environments (up to relabelling).

First, we use lemma 1 from [19] which relies on the data-processing inequality and the decomposition of the KL-divergence in the multi-armed bandit model. It holds that, for any $a \in G_+^*$,

$$\mathrm{kl} \left( \mathbb{P}_{\pi, G_{(a)}^*}(\hat{G} \sim G_{(a)}^*), \mathbb{P}_{\pi, G^*}(\hat{G} \sim G_{(a)}^*) \right) \le \mathrm{KL} \left( \mathbb{P}_{\pi, G_{(a)}^*}, \mathbb{P}_{\pi, G^*} \right) \quad (18)$$

$$= \mathbb{E}_{\pi, G_{(a)}^*} [N_a(\tau) + N_{b_{l^*}(a)}(\tau)] \frac{\Delta^2}{2\sigma^2},$$

the last equality follows from the fact that the environments $\nu(G^*, \bar{\mu})$ and $\nu(G_{(a)}^*, \bar{\mu})$ only differ on arm a and $b_a$ and KL($\mathcal{N}(-\Delta/2, \sigma^2)$, $\mathcal{N}(\Delta/2, \sigma^2)$) = $\Delta^2/2\sigma^2$. We recall that for any $b \in [N]$, $N_b(\tau)$ is the number of times that the arm b is sampled.

Thanks to the joint convexity of the kl function, see Corollary 3 from [14], we have

$$\mathrm{kl} \left( \frac{1}{N/2} \sum_{a \in G_+^*} \mathbb{P}_{\pi, G_{(a)}^*}(\hat{G} \sim G_{(a)}^*), \frac{1}{N/2} \sum_{a \in G_+^*} \mathbb{P}_{\pi, G^*}(\hat{G} \sim G_{(a)}^*) \right) \quad (19)$$

$$\le \frac{1}{N/2} \sum_{a \in G_+^*} \mathrm{kl} \left( \mathbb{P}_{\pi, G_{(a)}^*}(\hat{G} \sim G_{(a)}^*), \mathbb{P}_{\pi, G^*}(\hat{G} \sim G_{(a)}^*) \right).$$

By construction, the partition $G^*$ and all the different partitions $(G_a^*)_{a \in G_+^*}$ belong to different equivalence classes with respect to the relation $\sim$. As $\pi$ is $\delta$-PAC – see Definition B.6, we deduce that

$$\forall a \in G_+^*, \mathbb{P}_{\pi, G_{(a)}^*}(\hat{G} \sim G_{(a)}^*) \ge 1 - \delta;$$

$$\sum_{a \in G_+^*} \mathbb{P}_{\pi, G^*}(\hat{G} \sim G_{(a)}^*) = \mathbb{P}_{\pi, G^*}(\bigcup_{a \in G_+^*} \{\hat{G} \sim G_{(a)}^*\}) \le \mathbb{P}_{\pi, G^*}(\hat{G} \not\sim G^*) \le \delta.$$

With the monotony properties of the kl function, we obtain

$$\mathrm{kl} \left( 1 - \delta, \frac{\delta}{N/2} \right) \le \mathrm{kl} \left( \frac{1}{N/2} \sum_{a \in G_+^*} \mathbb{P}_{\pi, G_{(a)}^*}(\hat{G} \sim G_{(a)}^*), \frac{1}{N/2} \sum_{a \in G_+^*} \mathbb{P}_{\pi, G^*}(\hat{G} \sim G_{(a)}^*) \right) . \quad (20)$$

Gathering Equations (18), (19) and (20), we obtain

$$\mathrm{kl} \left( 1 - \delta, \frac{2\delta}{N} \right) \le \frac{1}{N/2} \sum_{a \in G_+^*} \mathbb{E}_{\pi, G_{(a)}^*} [N_a(\tau) + N_{b_a}(\tau)] \frac{\Delta^2}{2\sigma^2} \quad (21)$$
We consider $T_{Sym}^*(\delta, \mathcal{E}_{Sym}(G^*, \gamma_1)) = \inf_{\pi \in \Pi_{Sym}} \mathbb{E}_{\pi, G^*}[\tau]$ where the inf is taken over all symmetric and $\delta$-PAC algorithm on $\mathcal{E}_{Sym}(G^*, \gamma_1)$ -see Definition B.6.

**Lemma B.10.** If K is even, K divides N and $N \ge K$, then,

$$T_{Sym}^*(\delta, \mathcal{E}_{Sym}(G^*, \gamma_1)) \ge N \frac{\sigma^2}{\Delta^2} \mathrm{kl}\left(1 - \delta, \frac{2\delta}{N}\right).$$

Then, Lemma B.1 simply follows from the reduction arguments of B.7 and lemma B.10 that we prove now.

*Proof of lemma B.10.* Let $\pi$ be a symmetric and $\delta$-PAC algorithm for the active clustering problem on $\mathcal{E}_{Sym}(G^*, \gamma_1)$. It outputs a partition $\hat{G}$ of $[N]$ such that for any $a \in G_+^*$,

$$\mathbb{P}_{\pi, G_{(a)}^*}(\hat{G} \sim G_{(a)}^*) \ge 1 - \delta, \text{ and}$$

$$\mathbb{P}_{\pi, G^*}(\hat{G} \sim G^*) \ge 1 - \delta.$$

The main tool that we use is a data-processing inequality– see e.g.[14]. We will use the KL-divergence which, in our setting, turns out to be explicitly computed. The difficulty of the proof is to recover the term $\log(N/\delta)$ in the lower bound of the budget. For that, we adapt the proof page 15 of [6] to the fixed confidence setting. The idea is that, instead of constructing one partition, different from $G^*$, we constructed a collection of $\{G_{(a)}^*\}_{a \in G_+^*}$, where any algorithm has to distinguish $G^*$ from any of these environments (up to relabelling).

First, we use lemma 1 from [19] which relies on the data-processing inequality and the decomposition of the KL-divergence in the multi-armed bandit model. It holds that, for any $a \in G_+^*$,

$$\mathrm{kl}\left(\mathbb{P}_{\pi, G_{(a)}^*}(\hat{G} \sim G_{(a)}^*), \mathbb{P}_{\pi, G^*}(\hat{G} \sim G_{(a)}^*)\right) \le \mathrm{KL}\left(\mathbb{P}_{\pi, G_{(a)}^*}, \mathbb{P}_{\pi, G^*}\right) \quad (18)$$

$$= \mathbb{E}_{\pi, G_{(a)}^*}[N_a(\tau) + N_{b_{l^*}(a)}(\tau)] \frac{\Delta^2}{2\sigma^2},$$

the last equality follows from the fact that the environments $\nu(G^*, \bar{\mu})$ and $\nu(G_{(a)}^*, \bar{\mu})$ only differ on arm $a$ and $b_a$ and KL($\mathcal{N}(-\Delta/2, \sigma^2)$, $\mathcal{N}(\Delta/2, \sigma^2)) = \Delta^2/2\sigma^2$. We recall that for any $b \in [N]$, $N_b(\tau)$ is the number of times that the arm $b$ is sampled.

Thanks to the joint convexity of the kl function, see Corollary 3 from [14], we have

$$\mathrm{kl}\left(\frac{1}{N/2} \sum_{a \in G_+^*} \mathbb{P}_{\pi, G_{(a)}^*}(\hat{G} \sim G_{(a)}^*), \frac{1}{N/2} \sum_{a \in G_+^*} \mathbb{P}_{\pi, G^*}(\hat{G} \sim G_{(a)}^*)\right) \quad (19)$$

$$\le \frac{1}{N/2} \sum_{a \in G_+^*} \mathrm{kl}\left(\mathbb{P}_{\pi, G_{(a)}^*}(\hat{G} \sim G_{(a)}^*), \mathbb{P}_{\pi, G^*}(\hat{G} \sim G_{(a)}^*)\right).$$

By construction, the partition $G^*$ and all the different partitions $(G_a^*)_{a \in G_+^*}$ belong to different equivalence classes with respect to the relation $\sim$. As $\pi$ is $\delta$-PAC – see Definition B.6, we deduce that

$$\forall a \in G_+^*, \mathbb{P}_{\pi, G_{(a)}^*}(\hat{G} \sim G_{(a)}^*) \ge 1 - \delta;$$

$$\sum_{a \in G_+^*} \mathbb{P}_{\pi, G^*}(\hat{G} \sim G_{(a)}^*) = \mathbb{P}_{\pi, G^*}(\bigcup_{a \in G_+^*} \{\hat{G} \sim G_{(a)}^*\}) \le \mathbb{P}_{\pi, G^*}(\hat{G} \not\sim G^*) \le \delta.$$

With the monotony properties of the kl function, we obtain

$$\mathrm{kl}\left(1 - \delta, \frac{\delta}{N/2}\right) \le \mathrm{kl}\left(\frac{1}{N/2} \sum_{a \in G_+^*} \mathbb{P}_{\pi, G_{(a)}^*}(\hat{G} \sim G_{(a)}^*), \frac{1}{N/2} \sum_{a \in G_+^*} \mathbb{P}_{\pi, G^*}(\hat{G} \sim G_{(a)}^*)\right) \quad (20)$$

Gathering Equations (18), (19) and (20), we obtain

$$\mathrm{kl}\left(1 - \delta, \frac{2\delta}{N}\right) \le \frac{1}{N/2} \sum_{a \in G_+^*} \mathbb{E}_{\pi, G_{(a)}^*}[N_a(\tau) + N_{b_a}(\tau)] \frac{\Delta^2}{2\sigma^2} \quad (21)$$
We recall that $\pi$ is symmetric. Hence, For any $a \in G_+^*$, we have

$$ \mathbb{E}_{\pi, G_{(a)}^*} [N_a(\tau) + N_{b_a}(\tau)] = \frac{2}{N} \mathbb{E}_{\pi, G_{(a)}^*} [\tau] = \frac{2}{N} \mathbb{E}_{\pi, G^*} [\tau] . $$

Finally, with eq. (21), we conclude that

$$ \mathbb{E}_{\pi, G^*} [\tau] \geq \frac{\sigma^2}{\Delta^2} N \operatorname{kl} \left( 1 - \delta, \frac{2\delta}{N} \right) . \qquad (22) $$

We take now the inf over all algorithms $\pi$, which are $\delta$-PAC and symmetric, this proves lemma B.10. $\square$

## B.3 Second Lower Bound: proof of Lemma B.2

In this section, we prove the lower bound from Lemma B.2. If $d \le (8/3)^2 \log(K/\delta)$, the lower bound from Lemma B.2 is smaller than the dimension-free lower bound from Lemma B.1, which is already proved. We may then assume that $d \ge (8/3)^2 \log(K/\delta)$. For the sake of the presentation, we postpone the proofs of some technical lemmas to the end of the next subsection.

### Step 1: introduction of the Gaussian prior

In this regime, we choose the prior distribution $\gamma$ to be Gaussian. Indeed, we introduce $\gamma_2 = \mathcal{N}(0, \rho^2 I_d)$ with $\rho^2 = \frac{\Delta^2}{d}$ and $\bar{\mu}(1), \dots, \bar{\mu}(L)$ are i.i.d of law $\mathcal{N}(0, \rho^2 I_d)$. Also, we choose $\beta = 4$. We consider the Bayesian family of environments constructed in Appendix B.1 $\mathcal{E}_{Sym}(G^*, \gamma_2)$.

Because of this Bayesian prior, we have some additional technical challenge in comparison to the low-dimensional case.

1. We can not use the decomposition of the KL-divergence for bandit in order to compute $KL(\mathbb{P}_{\pi, G_{(a)}^*}, \mathbb{P}_{\pi, G^*})$ because the integral over the prior $\gamma_1$ is inside the KL-divergence. Most of the work consists on upper bounding this divergence with a divergence that can be computed.

2. We can not compare the maximum budget over $\mathcal{E}(\Delta, \theta, \sigma, N, K, d)$ (i.e., $\sup_{\nu \in \mathcal{E}(\Delta)} \mathbb{E}_{\pi, \nu}[\tau])$ to the Bayesian budget $\mathbb{E}_{\pi, G^*}[\tau]$ because the minimal gap of $\nu(G^*, \bar{\mu})$ is not always larger than $\Delta$. This is why we condition on the event $\mathcal{Y} = \bigcap_{l \in [L]} \{\Delta/2 \le \|\bar{\mu}(l)\| \le \Delta(\beta - 1)/2\} \subset \{\nu(G^*, \bar{\mu}) \in \mathcal{E}(\Delta, \theta, \sigma, N, K, d)\}$.

We compute $\mathbb{P}_{\gamma^\otimes L}(\mathcal{Y}^c)$ for the Gaussian prior. This is the only time we will use the hypothesis $d \ge (8/3)^2 \log(K/\delta)$.

**Lemma B.11.** If we assume that $d \ge (8/3)^2 \log(K/\delta)$ and $\gamma_2 = \mathcal{N}(0, \rho^2)$, we have

$$ \mathbb{P}_{\gamma_2^{\otimes L}}(\mathcal{Y}) = \mathbb{P}_{\gamma_2^{\otimes L}} \left( \bigcap_{l \in [L]} \{\Delta/2 \le \|\bar{\mu}(l)\| \le 3\Delta/4\} \right) \ge 1 - \delta . $$

### Step 2: From active binary classification to (batch) two-sample testing

Let $\pi \in \Pi_{Sym}$ be a $\delta$-PAC and symmetric algorithm for the active clustering problem on $\mathcal{E}_{Sym}(G^*, \gamma_2)$ -see Definition B.6. We define $t = 6\mathbb{E}_{\pi, G^*}[\tau|\mathcal{Y}]/N$ and $T = 6\mathbb{E}_{\pi, G^*}[\tau|\mathcal{Y}]/K$.

We recall that, for any $a \in G_+^* = \{a; g_a^* = 1\}$, $G_{(a)}^*$ is obtained by switching one arm $a$ with another arm $b_a \in G_{l_a^*, -1}^*$. We recall that $N_a(\tau) := \sum_{l=1}^T \mathbb{1}_{\{A_s=a\}}$ is the number of times the arm $a$ is sampled. We also denote, $M_l(\tau) = \sum_{b:l_b^*=l} N_b(\tau)$ as the number of times the arms in the block $G_l^*$ are sampled. As $\pi$ is symmetric and as the blocks have the same size $2N/K$, we have, for any $a \in G_+^*$,

$$ t_a := 3\mathbb{E}_{\pi, G_{(a)}^*} [N_a(\tau) + N_{b_a}(\tau)|\mathcal{Y}] = t, \quad \text{and} \quad T_a := 3\mathbb{E}_{\pi, G_{(a)}^*} [M_{l_a^*}(\tau)|\mathcal{Y}] = T. $$
We recall that $\pi$ is symmetric. Hence, For any $a \in G_+^*$, we have

$$ \mathbb{E}_{\pi, G_{(a)}^*} [N_a(\tau) + N_{b_a}(\tau)] = \frac{2}{N} \mathbb{E}_{\pi, G_{(a)}^*} [\tau] = \frac{2}{N} \mathbb{E}_{\pi, G^*} [\tau] . $$

Finally, with eq. (21), we conclude that

$$ \mathbb{E}_{\pi, G^*} [\tau] \geq \frac{\sigma^2}{\Delta^2} N \operatorname{kl} \left( 1 - \delta, \frac{2\delta}{N} \right) . \qquad (22) $$

We take now the inf over all algorithms $\pi$, which are $\delta$-PAC and symmetric, this proves lemma B.10. $\square$

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

## B.3 Second Lower Bound: proof of Lemma B.2

In this section, we prove the lower bound from Lemma B.2. If $d \le (8/3)^2 \log(K/\delta)$, the lower bound from Lemma B.2 is smaller than the dimension-free lower bound from Lemma B.1, which is already proved. We may then assume that $d \ge (8/3)^2 \log(K/\delta)$. For the sake of the presentation, we postpone the proofs of some technical lemmas to the end of the next subsection.

### Step 1: introduction of the Gaussian prior

In this regime, we choose the prior distribution $\gamma$ to be Gaussian. Indeed, we introduce $\gamma_2 = \mathcal{N}(0, \rho^2 I_d)$ with $\rho^2 = \frac{\Delta^2}{d}$ and $\bar{\mu}(1), \dots, \bar{\mu}(L)$ are i.i.d of law $\mathcal{N}(0, \rho^2 I_d)$. Also, we choose $\beta = 4$. We consider the Bayesian family of environments constructed in Appendix B.1 $\mathcal{E}_{Sym}(G^*, \gamma_2)$.

Because of this Bayesian prior, we have some additional technical challenge in comparison to the low-dimensional case.

1. We can not use the decomposition of the KL-divergence for bandit in order to compute $KL(\mathbb{P}_{\pi, G_{(a)}^*}, \mathbb{P}_{\pi, G^*})$ because the integral over the prior $\gamma_1$ is inside the KL-divergence. Most of the work consists on upper bounding this divergence with a divergence that can be computed.

2. We can not compare the maximum budget over $\mathcal{E}(\Delta, \theta, \sigma, N, K, d)$ (i.e., $\sup_{\nu \in \mathcal{E}(\Delta)} \mathbb{E}_{\pi, \nu}[\tau])$ to the Bayesian budget $\mathbb{E}_{\pi, G^*}[\tau]$ because the minimal gap of $\nu(G^*, \bar{\mu})$ is not always larger than $\Delta$. This is why we condition on the event $\mathcal{Y} = \bigcap_{l \in [L]} \{\Delta/2 \le \|\bar{\mu}(l)\| \le \Delta(\beta - 1)/2\} \subset \{\nu(G^*, \bar{\mu}) \in \mathcal{E}(\Delta, \theta, \sigma, N, K, d)\}$.

We compute $\mathbb{P}_{\gamma^\otimes L}(\mathcal{Y}^c)$ for the Gaussian prior. This is the only time we will use the hypothesis $d \ge (8/3)^2 \log(K/\delta)$.

**Lemma B.11.** If we assume that $d \ge (8/3)^2 \log(K/\delta)$ and $\gamma_2 = \mathcal{N}(0, \rho^2)$, we have

$$ \mathbb{P}_{\gamma_2^{\otimes L}}(\mathcal{Y}) = \mathbb{P}_{\gamma_2^{\otimes L}} \left( \bigcap_{l \in [L]} \{ \Delta/2 \le \|\bar{\mu}(l)\| \le 3\Delta/4 \} \right) \ge 1 - \delta . $$

### Step 2: From active binary classification to (batch) two-sample testing

Let $\pi \in \Pi_{Sym}$ be a $\delta$-PAC and symmetric algorithm for the active clustering problem on $\mathcal{E}_{Sym}(G^*, \gamma_2)$ -see Definition B.6. We define $t = 6\mathbb{E}_{\pi, G^*}[\tau|\mathcal{Y}]/N$ and $T = 6\mathbb{E}_{\pi, G^*}[\tau|\mathcal{Y}]/K$.

We recall that, for any $a \in G_+^* = \{a; g_a^* = 1\}$, $G_{(a)}^*$ is obtained by switching one arm $a$ with another arm $b_a \in G_{l_a^*, -1}^*$. We recall that $N_a(\tau) := \sum_{l=1}^T 1_{\{A_s=a\}}$ is the number of times the arm $a$ is sampled. We also denote, $M_l(\tau) = \sum_{b:l_b^*=l} N_b(\tau)$ as the number of times the arms in the block $G_l^*$ are sampled. As $\pi$ is symmetric and as the blocks have the same size $2N/K$, we have, for any $a \in G_+^*$,

$$ t_a := 3\mathbb{E}_{\pi, G_{(a)}^*} [N_a(\tau) + N_{b_a}(\tau)|\mathcal{Y}] = t, \quad \text{and} \quad T_a := 3\mathbb{E}_{\pi, G_{(a)}^*} [M_{l_a^*}(\tau)|\mathcal{Y}] = T. $$
**Remark B.12.** We now give some heuristic in order to explain the rest of the proof. Imagine that, at time $\tau$, the learner receives an oracle that gives the labels of all the arms except the arm $a$, assume also that the learner knows that $a \in G_l^*$. As in a supervised classification setting, the player has to find the label $g_a$ of the unlabeled data sampled from $a$, using the labelled data available. It has access to $N_a(\tau)$ observations from $a$ distributed as $N(g_a\bar{\mu}(l), \sigma^2I_d)$, and $M_{l_a^*}(\tau) - N_a(\tau)$ labelled data distributed as $N(\bar{\mu}(l), \sigma^2I_d)$. It also has access to data from the other blocks, but those data are not useful to find $g_a$. Moreover, $N_a(\tau)$ is of the order of $E_{\pi,G^*}[\tau]/N$ and $M_{l_a^*}(\tau) - N_a(\tau)$ is of the order of $E_{\pi,G^*}[\tau]/L$. As a consequence, with this amount of data, a learner should be able to correctly recover the labels in this simplified setting.

With this heuristic in mind, we introduce the following (batch) two-sample testing problem.

**Definition B.13.** Let $t, T$ be two integers, we consider data $Y_1, \dots, Y_t, Z_1, \dots, Z_T$ and two symmetric hypotheses $H_1$ and $H_2$ such that, for $g \in \{-1, 1\}$, under $H_g$, the data follows the law $\mathbb{P}_g$ defined as follows:

* $\mu \sim \gamma$ and conditionally on $\mu$:

* $Y_1, \dots, Y_t, Z_1, \dots, Z_T$ are independent;

* $\forall r \in [t], Y_r \sim N(g\mu, \sigma^2I_d)$

* $\forall s \in [T], Z_r \sim N(\mu, \sigma^2I_d)$.

This problem is interesting because we can explicitly compute the KL-divergence.

**Lemma B.14.** Let $g \in \{-1, 1\}$ and $\mathbb{P}_g$ defined in Definition B.13. It holds that

$$ \mathrm{KL}(\mathbb{P}_{-g}, \mathbb{P}_g) = \mathrm{KL}(\mathbb{P}_g, \mathbb{P}_{-g}) = \frac{2tT\rho^4d}{\sigma^4 + \sigma^2\rho^2(t+T)} \le \frac{2tT\rho^4d}{\sigma^4} \wedge \frac{2\rho^2d}{\sigma^2} \frac{tT}{t+T}. $$

Now, we explain properly the ideas introduced in the previous remark. We define the event $B_a = \{N_a(\tau) + N_{b_a}(\tau) \le t\} \cap \{M_{l_a^*}(\tau) \le T\}$. Thanks to Markov inequality, the event $B_a$ has a probability higher than a constant and conditionally on $B_a$, the algorithm $\pi$ has access to strictly less information than in (batch) two-sample testing problem defined above with $t_a$ and $T_a$. We formalize this in the following coupling lemma.

**Lemma B.15.** Let $a \in G_+^*$ be an arm and fix $A_a$ an event. Consider the family of random variables $(Y_1, \dots, Y_t)$, $(Z_1, \dots, Z_T)$ that follows a distribution $\mathbb{P}_{-1}$ – see Definition B.13. Consider also an independent sequence $(\epsilon_s, U_s)_{s \ge 1}$ of random variables such that for all $s \ge 1$, $\epsilon_s \sim N(0, I_d)$ and $U_s \sim U([0, 1])$. Then, there exists a function $f_a$ that is measurable according to the random variables $Y, Z, \epsilon, U$ and such that $A_a \cap B_a = f_a(Y, Z, \epsilon, U)$, where the equality holds with respect to the probability distribution $\mathbb{P}_{\pi, G_{(a)}^*} = \int_{\bar{\mu}} \mathbb{P}_{\pi, G_{(a)}^*}, \bar{\mu} \mathrm{d}\gamma^{\otimes L}(\bar{\mu})$.

Similarly, if $(Y, Z) \sim \mathbb{P}_1$, with the same function $f_a$, $A_a \cap B_a = f_a(Y, Z, \epsilon, U)$, under the probability distribution $\mathbb{P}_{\pi, G^*}$.

In the previous lemma, we will consider $A_a := \{\hat{G} \sim G_{(a)}^*\}$ for $a \in G_+^*$. By construction of $G_{(a)}^*$ (because $N \ge 2K$), the events $A_a$ are disjoint. By using the fact that $\pi$ is $\delta$-PAC on $\mathcal{E}(\gamma, \Delta)$, we have the following property for $A_a$,

**Lemma B.16.** The family $(A_a \cap B_a)_{a \in G_+^*}$ is such that

1. $\sum_{a \in G_+^*} \mathbb{P}_{\pi, G^*}(A_a \cap B_a) \le \delta + \mathbb{P}_{\gamma^{\otimes L}}(Y^c) \le 2\delta$;

2. $\mathbb{P}_{\pi, G_{(a)}^*}(A_a \cap B_a) \ge 1/3 - \delta - \mathbb{P}_{\gamma^{\otimes L}}(Y^c) \ge 1/3 - 2\delta$.

We delay the technical proofs of Lemma B.15 and Lemma B.16. From there, we have all the tools that we need. We now use data-processing inequalities similar to the proof of Lemma B.1 to conclude.

### Step 3: Conclusion to the proof of Lemma B.2

We assume that $\delta \in (0, 1/6)$, so that $\mathrm{kl}(1/3 - 2\delta, \frac{2\delta}{N/2})$ is defined.
**Remark B.12.** We now give some heuristic in order to explain the rest of the proof. Imagine that, at time $\tau$, the learner receives an oracle that gives the labels of all the arms except the arm $a$, assume also that the learner knows that $a \in G_l^*$. As in a supervised classification setting, the player has to find the label $g_a$ of the unlabeled data sampled from $a$, using the labelled data available. It has access to $N_a(\tau)$ observations from $a$ distributed as $N(g_a\bar{\mu}(l), \sigma^2I_d)$, and $M_{l_a^*}(\tau) - N_a(\tau)$ labelled data distributed as $N(\bar{\mu}(l), \sigma^2I_d)$. It also has access to data from the other blocks, but those data are not useful to find $g_a$. Moreover, $N_a(\tau)$ is of the order of $E_{\pi,G^*}[\tau]/N$ and $M_{l_a^*}(\tau) - N_a(\tau)$ is of the order of $E_{\pi,G^*}[\tau]/L$. As a consequence, with this amount of data, a learner should be able to correctly recover the labels in this simplified setting.

With this heuristic in mind, we introduce the following (batch) two-sample testing problem.

**Definition B.13.** Let $t, T$ be two integers, we consider data $Y_1, \dots, Y_t, Z_1, \dots, Z_T$ and two symmetric hypotheses $H_1$ and $H_2$ such that, for $g \in \{-1, 1\}$, under $H_g$, the data follows the law $\mathbb{P}_g$ defined as follows:

* $\mu \sim \gamma$ and conditionally on $\mu$:

* $Y_1, \dots, Y_t, Z_1, \dots, Z_T$ are independent;

* $\forall r \in [t], Y_r \sim N(g\mu, \sigma^2I_d)$

* $\forall s \in [T], Z_r \sim N(\mu, \sigma^2I_d)$.

This problem is interesting because we can explicitly compute the KL-divergence.

**Lemma B.14.** Let $g \in \{-1, 1\}$ and $\mathbb{P}_g$ defined in Definition B.13. It holds that

$$ \mathrm{KL}(\mathbb{P}_{-g}, \mathbb{P}_g) = \mathrm{KL}(\mathbb{P}_g, \mathbb{P}_{-g}) = \frac{2tT\rho^4d}{\sigma^4 + \sigma^2\rho^2(t+T)} \le \frac{2tT\rho^4d}{\sigma^4} \wedge \frac{2\rho^2d}{\sigma^2} \frac{tT}{t+T}. $$

Now, we explain properly the ideas introduced in the previous remark. We define the event $B_a = \{N_a(\tau) + N_{b_a}(\tau) \le t\} \cap \{M_{l_a^*}(\tau) \le T\}$. Thanks to Markov inequality, the event $B_a$ has a probability higher than a constant and conditionally on $B_a$, the algorithm $\pi$ has access to strictly less information than in (batch) two-sample testing problem defined above with $t_a$ and $T_a$. We formalize this in the following coupling lemma.

**Lemma B.15.** Let $a \in G_+^*$ be an arm and fix $A_a$ an event. Consider the family of random variables $(Y_1, \dots, Y_t)$, $(Z_1, \dots, Z_T)$ that follows a distribution $\mathbb{P}_{-1}$ – see Definition B.13. Consider also an independent sequence $(\epsilon_s, U_s)_{s \ge 1}$ of random variables such that for all $s \ge 1$, $\epsilon_s \sim N(0, I_d)$ and $U_s \sim U([0, 1])$. Then, there exists a function $f_a$ that is measurable according to the random variables $Y, Z, \epsilon, U$ and such that $A_a \cap B_a = f_a(Y, Z, \epsilon, U)$, where the equality holds with respect to the probability distribution $\mathbb{P}_{\pi, G_{(a)}^*} = \int_{\bar{\mu}} \mathbb{P}_{\pi, G_{(a)}^*}, \bar{\mu} \mathrm{d}\gamma^{\otimes L}(\bar{\mu})$.

Similarly, if $(Y, Z) \sim \mathbb{P}_1$, with the same function $f_a$, $A_a \cap B_a = f_a(Y, Z, \epsilon, U)$, under the probability distribution $\mathbb{P}_{\pi, G^*}$.

In the previous lemma, we will consider $A_a := \{\hat{G} \sim G_{(a)}^*\}$ for $a \in G_+^*$. By construction of $G_{(a)}^*$ (because $N \ge 2K$), the events $A_a$ are disjoint. By using the fact that $\pi$ is $\delta$-PAC on $\mathcal{E}(\gamma, \Delta)$, we have the following property for $A_a$,

**Lemma B.16.** The family $(A_a \cap B_a)_{a \in G_+^*}$ is such that

1. $\sum_{a \in G_+^*} \mathbb{P}_{\pi, G^*}(A_a \cap B_a) \le \delta + \mathbb{P}_{\gamma^{\otimes L}}(Y^c) \le 2\delta$;

2. $\mathbb{P}_{\pi, G_{(a)}^*}(A_a \cap B_a) \ge 1/3 - \delta - \mathbb{P}_{\gamma^{\otimes L}}(Y^c) \ge 1/3 - 2\delta$.

We delay the technical proofs of Lemma B.15 and Lemma B.16. From there, we have all the tools that we need. We now use data-processing inequalities similar to the proof of Lemma B.1 to conclude.

### Step 3: Conclusion to the proof of Lemma B.2

We assume that $\delta \in (0, 1/6)$, so that $\mathrm{kl}(1/3 - 2\delta, \frac{2\delta}{N/2})$ is defined.
We use the first point of Lemma B.16. We notice that the events $(A_a)_a$ are disjoint by construction of $G_{(a)}^*$ and because we took at least two arms by groups ($N \ge 2K$), it holds that

$$ \sum_{a \in G_+^*} \mathbb{P}_{\pi, G^*}(A_a \cap B_a) = \mathbb{P}_{\pi, G^*}(\bigcup_{a \in G_+^*} A_a \cap B_a) \le 2\delta . $$

With the second point of Lemma B.16, for any $a \in G_+^*$, we have

$$ \mathbb{P}_{G_{(a)}^*}(A_a \cap B_a) \ge 1/3 - 2\delta \ge 0 . $$

We use the monotony properties of the kl function, it holds that

$$ \mathrm{kl} \left( 1/3 - 2\delta, \frac{2\delta}{N/2} \right) \le \mathrm{kl} \left( \frac{1}{N/2} \sum_{a \in G_+^*} \mathbb{P}_{\pi, G_{(a)}^*}(A_a \cap B_a), \frac{1}{N/2} \sum_{a \in G_+^*} \mathbb{P}_{G^*}(A_a \cap B_a) \right) . $$

Thanks to the joint convexity of the kl function, see corollary 3 in [14], we deduce that

$$ \mathrm{kl} \left( \frac{1}{N/2} \sum_{a \in G_+^*} \mathbb{P}_{\pi, G_{(a)}^*}(A_a \cap B_a), \frac{1}{N/2} \sum_{a \in G_+^*} \mathbb{P}_{\pi, G^*}(A_a \cap B_a) \right) \\ \le \frac{1}{N/2} \sum_{a \in G_+^*} \mathrm{kl} \left( \mathbb{P}_{\pi, G_{(a)}^*}(A_a \cap B_a), \mathbb{P}_{\pi, G^*}(A_a \cap B_a) \right) . $$

Now, we use the coupling lemma B.15,

$$ \mathbb{P}_{\pi, G_{(a)}^*}(A_a \cap B_a) = \mathbb{P}_1 \times \mathbb{P}_{\epsilon, U}(f_a(Y, Z, \epsilon, U)) $$

$$ \mathbb{P}_{\pi, G^*}(A_a \cap B_a) = \mathbb{P}_{-1} \times \mathbb{P}_{\epsilon, U}(f_a(Y, Z, \epsilon, U)) . $$

We use the data-processing inequality, see corollary 2 in [14], for all $a \in G_+^*$,

$$ \begin{aligned} \mathrm{kl} \left( \mathbb{P}_{\pi, G_{(a)}^*}(A_a \cap B_a), \mathbb{P}_{\pi, G^*}(A_a \cap B_a) \right) &= \mathrm{kl} \left( \mathbb{P}_1 \times \mathbb{P}_{\epsilon, U}(f_a(Y, Z, \epsilon, U)), \mathbb{P}_{-1} \times \mathbb{P}_{\epsilon, U}(f_a(Y, Z, \epsilon, U)) \right) \\ &\le \mathrm{KL} \left( \mathbb{P}_{-1} \otimes \mathbb{P}_{\epsilon, U}, \mathbb{P}_1 \otimes \mathbb{P}_{\epsilon, U} \right) \\ &= \mathrm{KL} \left( \mathbb{P}_{-1}, \mathbb{P}_1 \right) . \end{aligned} $$

Gathering the previous inequalities, we obtain

$$ \mathrm{kl} \left( \frac{1}{3} - 2\delta, \frac{4\delta}{N} \right) \le \frac{1}{N/2} \sum_{a \in G_{(a)}^*} \mathrm{KL}(\mathbb{P}_{-1}, \mathbb{P}_1) . $$

We recall that $\rho^2 = \Delta^2/d$. With the explicit computation from Lemma B.14, we have

$$ \frac{d\sigma^4}{2\Delta^4} \mathrm{kl} \left( \frac{1}{3} - 2\delta, \frac{4\delta}{N} \right) \le \frac{1}{N/2} \sum_{a \in G_+^*} tT = tT . $$

Finally, we have, using the definition of $t$ and $T$,

$$ \mathbb{E}_{\pi, G^*}[\tau|\mathcal{Y}]^2 \ge \frac{d\sigma^4 KN}{72\Delta^4} \mathrm{kl} \left( \frac{1}{3} - 2\delta, \frac{4\delta}{N} \right) . $$

As it is true for any $\pi \in \Pi_O$, take the inf in the last inequality over $\pi \in \Pi_O$ and use Lemma B.7 to get

$$ T^*(\delta, \mathcal{E}(\Delta, \theta, \sigma, N, K, d)) \ge \frac{\sigma^2}{\Delta^2} \sqrt{\frac{dKN}{72}} \mathrm{kl} \left( \frac{1}{3} - 2\delta, \frac{4\delta}{N} \right), $$

this is exactly the inequality of Lemma B.2.
We use the first point of Lemma B.16. We notice that the events $(A_a)_a$ are disjoint by construction of $G_{(a)}^*$ and because we took at least two arms by groups ($N \ge 2K$), it holds that

$$ \sum_{a \in G_+^*} \mathbb{P}_{\pi, G^*}(A_a \cap B_a) = \mathbb{P}_{\pi, G^*}(\bigcup_{a \in G_+^*} A_a \cap B_a) \le 2\delta . $$

With the second point of Lemma B.16, for any $a \in G_+^*$, we have

$$ \mathbb{P}_{G_{(a)}^*}(A_a \cap B_a) \ge 1/3 - 2\delta \ge 0 . $$

We use the monotony properties of the kl function, it holds that

$$ \mathrm{kl} \left( 1/3 - 2\delta, \frac{2\delta}{N/2} \right) \le \mathrm{kl} \left( \frac{1}{N/2} \sum_{a \in G_+^*} \mathbb{P}_{\pi, G_{(a)}^*}(A_a \cap B_a), \frac{1}{N/2} \sum_{a \in G_+^*} \mathbb{P}_{G^*}(A_a \cap B_a) \right) . $$

Thanks to the joint convexity of the kl function, see corollary 3 in [14], we deduce that

$$ \begin{aligned} & \mathrm{kl} \left( \frac{1}{N/2} \sum_{a \in G_+^*} \mathbb{P}_{\pi, G_{(a)}^*}(A_a \cap B_a), \frac{1}{N/2} \sum_{a \in G_+^*} \mathbb{P}_{\pi, G^*}(A_a \cap B_a) \right) \\ & \le \frac{1}{N/2} \sum_{a \in G_+^*} \mathrm{kl} \left( \mathbb{P}_{\pi, G_{(a)}^*}(A_a \cap B_a), \mathbb{P}_{\pi, G^*}(A_a \cap B_a) \right) . \end{aligned} $$

Now, we use the coupling lemma B.15,

$$ \mathbb{P}_{\pi, G_{(a)}^*}(A_a \cap B_a) = \mathbb{P}_1 \times \mathbb{P}_{\epsilon, U}(f_a(Y, Z, \epsilon, U)) $$

$$ \mathbb{P}_{\pi, G^*}(A_a \cap B_a) = \mathbb{P}_{-1} \times \mathbb{P}_{\epsilon, U}(f_a(Y, Z, \epsilon, U)) . $$

We use the data-processing inequality, see corollary 2 in [14], for all $a \in G_+^*$,

$$ \begin{aligned} \mathrm{kl} \left( \mathbb{P}_{\pi, G_{(a)}^*}(A_a \cap B_a), \mathbb{P}_{\pi, G^*}(A_a \cap B_a) \right) &= \mathrm{kl} \left( \mathbb{P}_1 \times \mathbb{P}_{\epsilon, U}(f_a(Y, Z, \epsilon, U)), \mathbb{P}_{-1} \times \mathbb{P}_{\epsilon, U}(f_a(Y, Z, \epsilon, U)) \right) \\ &\le \mathrm{KL} \left( \mathbb{P}_{-1} \otimes \mathbb{P}_{\epsilon, U}, \mathbb{P}_1 \otimes \mathbb{P}_{\epsilon, U} \right) \\ &= \mathrm{KL} \left( \mathbb{P}_{-1}, \mathbb{P}_1 \right) . \end{aligned} $$

Gathering the previous inequalities, we obtain

$$ \mathrm{kl} \left( \frac{1}{3} - 2\delta, \frac{4\delta}{N} \right) \le \frac{1}{N/2} \sum_{a \in G_{(a)}^*} \mathrm{KL}(\mathbb{P}_{-1}, \mathbb{P}_1) . $$

We recall that $\rho^2 = \Delta^2/d$. With the explicit computation from Lemma B.14, we have

$$ \frac{d\sigma^4}{2\Delta^4} \mathrm{kl} \left( \frac{1}{3} - 2\delta, \frac{4\delta}{N} \right) \le \frac{1}{N/2} \sum_{a \in G_+^*} tT = tT . $$

Finally, we have, using the definition of $t$ and $T$,

$$ \mathbb{E}_{\pi, G^*}[\tau|\mathcal{Y}]^2 \ge \frac{d\sigma^4 KN}{72\Delta^4} \mathrm{kl} \left( \frac{1}{3} - 2\delta, \frac{4\delta}{N} \right) . $$

As it is true for any $\pi \in \Pi_O$, take the inf in the last inequality over $\pi \in \Pi_O$ and use Lemma B.7 to get

$$ T^*(\delta, \mathcal{E}(\Delta, \theta, \sigma, N, K, d)) \ge \frac{\sigma^2}{\Delta^2} \sqrt{\frac{dKN}{72}} \mathrm{kl} \left( \frac{1}{3} - 2\delta, \frac{4\delta}{N} \right), $$

this is exactly the inequality of Lemma B.2.
## B.4 Proof of technical lemmas

### B.4.1 Proof of Lemma B.4

Let $N, K$ such that $N \ge 2K$. Let $\theta > 0$ such that $\mathcal{E}(\Delta, \theta, \sigma, N, K, d) \neq \emptyset$. We prove Lemma B.4 assuming that $K$ is odd, the other case is simpler and can be proved with the same construction up to minor details.

Recall the expressions introduced before Lemma B.4, $K' = K - 1$, $N' = K' \lfloor \frac{N - \lfloor \theta N \rfloor}{K'} \rfloor$ and $\theta' = 1/K'$.

Let $\pi$ being $\delta$-PAC on $\mathcal{E}(\Delta, \theta, \sigma, N, K, d)$, we will use $\pi$ to construct $\pi'$, an algorithm which is $\delta$-PAC on $\mathcal{E}(\Delta, \theta', \sigma, N', K', d)$.

Let $\nu' \in \mathcal{E}(\Delta, \theta', \sigma, N', K', d)$ be an environment with $K - 1$ perfectly balanced groups. We run the algorithm $\pi$ where we create the data $X_1, \dots, X_{\pi^\pi}$ with the following coupling.

* If $A_t^\pi \in [N']$, we sample $X_t$ with the arm $A_t^\pi$ from $\nu'$.

* If $A_t^\pi \in [N' + 1; N - \lfloor \theta N \rfloor]$, we sample $X_t$ with $a_1$, the first arm from $\nu'$.

* If $A_t^\pi \in [N - \lfloor \theta N \rfloor + 1, N]$, we create $X_t = c$ where $c$ is an arbitrary large constant.

Equivalently, we have created the environment $\nu$ where the $N'$ first arms are the arms of $\nu$; the $\lfloor \theta N \rfloor$ last arms are in an artificial group associated to a Dirac in $c$, and the remaining arms are in the same group as $a_1$. The environment $\nu$ has a hidden partition $G_1^*, \dots, G_K^*$ where $G_1^* = G_1' \cup [N' + 1; N - \lfloor \theta N \rfloor]$, $G_2^*, \dots, G_{K-1}^* = G_2', \dots, G_{K-1}'$, and $G_K^* = [N - \lfloor \theta N \rfloor + 1, N]$. By construction, this environment is in $\mathcal{E}(\Delta, \theta, \sigma, N, K, d)$. In particular, the balancedness is larger than $\theta$, and the minimal gap is larger than $\Delta$ if $c$ is large enough.

When $\pi$ reaches $\tau^\pi$, it outputs a partition of $[N]$, $\hat{G}_1^\pi, \dots, \hat{G}_K^\pi$, and we output $\hat{G}^\pi$ as the partition defined by the restriction to $[N']$ of the partition $\hat{G}^\pi$. This is what we call the algorithm $\pi'$.

As $\pi$ is $\delta$-PAC on $\mathcal{E}(\Delta, \theta, \sigma, N, K, d)$, it holds that, with a probability $P_{\pi,\nu}$ higher than $1 - \delta$, $\hat{G} \sim G^*$, and this implies that $\hat{G}^\pi' \sim G'$. Finally, we have $P_{\pi',\nu'}(\hat{G}^\pi' \sim G') \ge P_{\pi,\nu}(\hat{G}^\pi \sim G^*) \ge 1 - \delta$. This means that $\pi'$ is indeed $\delta$-PAC on $\mathcal{E}(\Delta, \theta', \sigma, N', K', d)$.

In terms of budget, we have $\tau^\pi' \le \tau^\pi$, because the data provided from the last group are artificially created by the algorithm. We deduce that

$$ \mathbb{E}_{\pi', \nu'}[\tau^{\pi'}] \le \mathbb{E}_{\pi, \nu}[\tau^{\pi}] \le \sup_{\nu \in \mathcal{E}(\Delta, \theta, \sigma, N, K, d)} \mathbb{E}_{\pi, \nu}[\tau]. $$

Then, we take the sup over $\nu' \in \mathcal{E}(\Delta, \theta', \sigma, N', K', d)$, and we have

$$ T^*(\delta, \mathcal{E}(\Delta, \theta', \sigma, N', K', d)) \le \sup_{\nu' \in \mathcal{E}(\Delta, \theta', \sigma, N', K', d)} \mathbb{E}_{\pi', \nu'}[\tau] \le \sup_{\nu \in \mathcal{E}(\Delta, \theta, \sigma, N, K, d)} \mathbb{E}_{\pi, \nu}[\tau]. $$

Finally, we consider the inf over $\pi$ $\delta$-PAC on $\mathcal{E}(\Delta, \theta, \sigma, N, K, d)$, which concludes the proof of Lemma B.4.

### B.4.2 Proof of Lemma B.7

Let $\pi'$ be a $\delta$-PAC algorithm on $\mathcal{E}(\Delta, \theta, \sigma, N, K, d)$.

We will use the algorithm $\pi'$ to construct an algorithm $\pi$, which is symmetric and $\delta$-PAC on the class $\mathcal{E}_{Sym}(G^*, \gamma)$ – see Definition B.6. We will use the symmetries in the structure of the environment $\nu(G', \bar{\mu})$ when $\bar{\mu}$ is distributed with the prior $\gamma^{\otimes L}$ as the main argument to prove that $\pi$ will have the wanted properties. To avoid confusion, we index $(A_s^{\pi'})_s, \tau^{\pi'}$ and $\hat{G}^{\pi'}$ for the algorithm $\pi'$ and without $'$ for the algorithm $\pi$. As explained in the previous remark, the algorithm $\pi$ just need to perform well (i.e., being $\delta$-PAC) on the family $\mathcal{E}_{Sym}(G^*, \gamma)$, so we can use the offsets and the labels $l_1^*, \dots, l_N^*$ to construct the algorithm $\pi$.

#### Construction of $\pi$

In this paragraph, we describe how we symmetrize a strategy $\pi'$ –see Algorithm 3. Let $G' \in$
## B.4 Proof of technical lemmas

### B.4.1 Proof of Lemma B.4

Let $N, K$ such that $N \ge 2K$. Let $\theta > 0$ such that $\mathcal{E}(\Delta, \theta, \sigma, N, K, d) \ne \emptyset$. We prove Lemma B.4 assuming that $K$ is odd, the other case is simpler and can be proved with the same construction up to minor details.

Recall the expressions introduced before Lemma B.4, $K' = K - 1$, $N' = K' \lfloor \frac{N - \lfloor \theta N \rfloor}{K'} \rfloor$ and $\theta' = 1/K'$.

Let $\pi$ being $\delta$-PAC on $\mathcal{E}(\Delta, \theta, \sigma, N, K, d)$, we will use $\pi$ to construct $\pi'$, an algorithm which is $\delta$-PAC on $\mathcal{E}(\Delta, \theta', \sigma, N', K', d)$.

Let $\nu' \in \mathcal{E}(\Delta, \theta', \sigma, N', K', d)$ be an environment with $K - 1$ perfectly balanced groups. We run the algorithm $\pi$ where we create the data $X_1, \dots, X_{\pi^\pi}$ with the following coupling.

* If $A_t^\pi \in [N']$, we sample $X_t$ with the arm $A_t^\pi$ from $\nu'$.

* If $A_t^\pi \in [N' + 1; N - \lfloor \theta N \rfloor]$, we sample $X_t$ with $a_1$, the first arm from $\nu'$.

* If $A_t^\pi \in [N - \lfloor \theta N \rfloor + 1, N]$, we create $X_t = c$ where $c$ is an arbitrary large constant.

Equivalently, we have created the environment $\nu$ where the $N'$ first arms are the arms of $\nu$; the $\lfloor \theta N \rfloor$ last arms are in an artificial group associated to a Dirac in $c$, and the remaining arms are in the same group as $a_1$. The environment $\nu$ has a hidden partition $G_1^*, \dots, G_K^*$ where $G_1^* = G_1' \cup [N' + 1; N - \lfloor \theta N \rfloor]$, $G_2^*, \dots, G_{K-1}^* = G_2', \dots, G_{K-1}'$, and $G_K^* = [N - \lfloor \theta N \rfloor + 1, N]$. By construction, this environment is in $\mathcal{E}(\Delta, \theta, \sigma, N, K, d)$. In particular, the balancedness is larger than $\theta$, and the minimal gap is larger than $\Delta$ if $c$ is large enough.

When $\pi$ reaches $\tau^\pi$, it outputs a partition of $[N]$, $\hat{G}_1^\pi, \dots, \hat{G}_K^\pi$, and we output $\hat{G}^\pi$ as the partition defined by the restriction to $[N']$ of the partition $\hat{G}^\pi$. This is what we call the algorithm $\pi'$.

As $\pi$ is $\delta$-PAC on $\mathcal{E}(\Delta, \theta, \sigma, N, K, d)$, it holds that, with a probability $P_{\pi,\nu}$ higher than $1 - \delta$, $\hat{G} \sim G^*$, and this implies that $\hat{G}^\pi' \sim G'$. Finally, we have $P_{\pi',\nu'}(\hat{G}^\pi' \sim G') \ge P_{\pi,\nu}(\hat{G}^\pi \sim G^*) \ge 1 - \delta$. This means that $\pi'$ is indeed $\delta$-PAC on $\mathcal{E}(\Delta, \theta', \sigma, N', K', d)$.

In terms of budget, we have $\tau^\pi' \le \tau^\pi$, because the data provided from the last group are artificially created by the algorithm. We deduce that

$$ \mathbb{E}_{\pi', \nu'}[\tau^\pi'] \le \mathbb{E}_{\pi, \nu}[\tau^\pi] \le \sup_{\nu \in \mathcal{E}(\Delta, \theta, \sigma, N, K, d)} \mathbb{E}_{\pi, \nu}[\tau]. $$

Then, we take the sup over $\nu' \in \mathcal{E}(\Delta, \theta', \sigma, N', K', d)$, and we have

$$ T^*(\delta, \mathcal{E}(\Delta, \theta', \sigma, N', K', d)) \le \sup_{\nu' \in \mathcal{E}(\Delta, \theta', \sigma, N', K', d)} \mathbb{E}_{\pi', \nu'}[\tau] \le \sup_{\nu \in \mathcal{E}(\Delta, \theta, \sigma, N, K, d)} \mathbb{E}_{\pi, \nu}[\tau]. $$

Finally, we consider the inf over $\pi$ $\delta$-PAC on $\mathcal{E}(\Delta, \theta, \sigma, N, K, d)$, which concludes the proof of Lemma B.4.

### B.4.2 Proof of Lemma B.7

Let $\pi'$ be a $\delta$-PAC algorithm on $\mathcal{E}(\Delta, \theta, \sigma, N, K, d)$.

We will use the algorithm $\pi'$ to construct an algorithm $\pi$, which is symmetric and $\delta$-PAC on the class $\mathcal{E}_{Sym}(G^*, \gamma)$ – see Definition B.6. We will use the symmetries in the structure of the environment $\nu(G', \bar{\mu})$ when $\bar{\mu}$ is distributed with the prior $\gamma^{\otimes L}$ as the main argument to prove that $\pi$ will have the wanted properties. To avoid confusion, we index $(A_s^{\pi'})_s, \tau^{\pi'}$ and $\hat{G}^{\pi'}$ for the algorithm $\pi'$ and without $'$ for the algorithm $\pi$. As explained in the previous remark, the algorithm $\pi$ just need to perform well (i.e., being $\delta$-PAC) on the family $\mathcal{E}_{Sym}(G^*, \gamma)$, so we can use the offsets and the labels $l_1^*, \dots, l_N^*$ to construct the algorithm $\pi$.

#### Construction of $\pi$

In this paragraph, we describe how we symmetrize a strategy $\pi'$ –see Algorithm 3. Let $G' \in$
$\{G^*\} \cup \{G_{(a)}^*\}_{a \in G_+^*}$ being a partition. In order to make the reading easier, we use the notation $l_a^* = l^*(a)$ for all $a \in [N]$. For any arm $a$, we denote as $g'(a) \in \{-1, 1\}$ as the label such that the mean of $a$ is $\mu_a = g'(a)\bar{\mu}(l^*(a)) + C(l^*(a))$, in the environment $\nu(G', \bar{\mu})$, for any $\bar{\mu} \in \mathbb{R}^d$.

We need to define the behavior of $\pi$ when facing the environment $\nu(G', \bar{\mu})$ for any $\bar{\mu}$.

Define $S$ as the set of permutations of $[N]$ that switch the blocks in $G^*$, that is to say if $\kappa \in S$ then for all $l \in [L], \exists l' \in [L]$, such that $\kappa(G_l^*) = G_{l'}^*$. For any $\kappa \in S$, $\kappa$ naturally induces a permutation of $[L]$ denoted as $\tilde{\kappa}$ such that for all $a \in [N], l^*(\kappa(a)) = \tilde{\kappa}(l^*(a))$.

First, the strategy $\pi$ uniformly samples a permutation $\kappa$ in $S$ and a vector $\chi \in \{-1, 1\}^L$. From a rough perspective, the strategy $\pi$ will then apply the strategy $\pi'$ by permuting the blocks using $\kappa$ and reversing the means of each block using $\chi$.

<caption>**Algorithm 3 Symmetrization of $\pi'$**</caption>

1: **Input:** $\nu(G', \bar{\mu})$ an environment in $\mathcal{E}_{Sym}(G^*, \gamma)$
2: **Output:** $\hat{G}^\pi$, partition of $[N]$
3: $t = 1$
4: Take $\kappa \sim \mathcal{U}(S)$
5: Take $\chi \sim \mathcal{U}(\{-1, 1\}^L)$
6: **while** $t \le \tau^\pi(A_1^{\pi'}, X_1^{\pi'}, \dots, A_{t-1}^{\pi'}, X_{t-1}^{\pi'})$ **do**
7: &nbsp;&nbsp;&nbsp;&nbsp;Choose an arm with $\pi'$ and get $A_t^\pi(A_1^{\pi'}, X_1^{\pi'}, \dots, A_{t-1}^{\pi'}, X_{t-1}^{\pi'}) \in [N]$.
8: &nbsp;&nbsp;&nbsp;&nbsp;Sample $X_t^\pi$ from $A_t^\pi := \kappa(A_t^\pi')$
9: &nbsp;&nbsp;&nbsp;&nbsp;Create the data $X_t^{\pi'} := \chi(\tilde{\kappa}(l^*(A_t^{\pi'}))) [X_t^\pi - C(\tilde{\kappa}(l^*(A_t^{\pi'})))] + C(l^*(A_t^{\pi'}))$
10: &nbsp;&nbsp;&nbsp;&nbsp;**t=t+1**
11: Compute $\hat{G}^\pi(A_1^{\pi'}, X_1^{\pi'}, \dots, A_\tau^{\pi'}, X_\tau^{\pi'}) := \hat{G}_1^{\pi'}, \dots, \hat{G}_K^{\pi'}$
12: **return** $\hat{G}_1^\pi, \dots, \hat{G}_K^\pi := \kappa(\hat{G}_1^{\pi'}), \dots, \kappa(\hat{G}_K^{\pi'})$

Within the procedure $\pi$, we run algorithm $\pi'$ with modified data $X_1^{\pi'}, \dots, X_\tau^{\pi'}$. At time $t$, the algorithm $\pi'$ chooses to sample the arm $A_t^{\pi'}$, where the decision is based on the data $(X_s^{\pi'}, A_s^{\pi'})_{s \le t-1}$. Instead of sampling the arm chosen by $\pi'$, the algorithm $\pi$ samples $X_t^\pi$ from the arm $A_t^\pi := \kappa(A_t^{\pi'})$ and sends the data $X_t^{\pi'}$ to $\pi'$, according to the formula

$$X_t^{\pi'} = \chi(\tilde{\kappa}(l^*(A_t^{\pi'}))) [X_t^\pi - C(\tilde{\kappa}(l^*(A_t^{\pi'})))] + C(l^*(A_t^{\pi'})),$$

where we recall that $C(l)$ is the offset associated to block $l$. When $\pi'$ decides to stop, $\pi$ also stops; i.e., $\tau^\pi(X_1^\pi, A_1^\pi, \dots, X_\tau^\pi, A_\tau^\pi) = \tau^\pi(X_1^{\pi'}, A_1^{\pi'}, \dots, X_\tau^{\pi'}, A_\tau^{\pi'})$. Then, $\pi'$ outputs a partition $\hat{G}^\pi = \hat{G}_1^{\pi'}, \dots, \hat{G}_K^{\pi'}$ based on the modified data, and $\pi$ outputs $\hat{G}_1^\pi, \dots, \hat{G}_K^\pi := \kappa(\hat{G}_1^{\pi'}), \dots, \kappa(\hat{G}_K^{\pi'})$.

**Lemma B.17.** Take $\kappa \in S$, and $\chi \in \{-1, 1\}^L$. For all $l \in [L]$, define $\bar{\mu}_\kappa(l) := \bar{\mu}(\tilde{\kappa}(l))$. As $\bar{\mu}$ is sampled according to $\gamma^{\otimes L}$, then $\bar{\mu}_\kappa$ follows the same prior $\gamma^{\otimes L}$. Define $G'(\kappa, \chi)$ as a partition of $[N]$ into $2L$ groups such that for all $(l, g) \in [L] \times \{-1; 1\}$, then

$$G'(\kappa, \chi)_{l,g} = \{a \in [N]; l^*(a) = l, \text{ and } g'(\kappa(a))\chi(\tilde{\kappa}(l^*(a))) = g\} = \kappa^{-1} \left( G'_{\tilde{\kappa}(l), g\chi(\tilde{\kappa}(l))} \right).$$

Conditionally on $\kappa, \chi, \bar{\mu}$, the modified data $X_s^{\tau'}$ are distributed according to the probability induced by the interaction between $\pi'$ and the environment $\nu(G'(\kappa, \chi), \bar{\mu}_\kappa)$, after integration on the prior $\gamma$, we have

$$\mathbb{P}_{\pi, G'(\cdot|\mathcal{Y}), \kappa, \chi} = \mathbb{P}_{\pi', G'(\kappa, \chi)(\cdot|\mathcal{Y})}.$$

**Remark B.18.** It is very important to note that, as $G'$ is a partition with $K = 2L$ groups of the same size, the partition $G'(\kappa, \chi)$ is also balanced.

**Proof of Lemma B.17.** Let $\bar{\mu} \in (\mathbb{R}^d)^L$ be a realization of the prior $\gamma^{\otimes L}$.

When $\pi'$ tries to sample the arm $a = A_t^{\pi'}$, we sample in fact $\kappa(a)$. Using the Gaussian assumption on the data, and the expression of the centers of the environment $\nu(G', \bar{\mu})$, it holds that

$$X_t^\pi = g'(\kappa(a))\bar{\mu}(l^*(\kappa(a))) + C(l^*(\kappa(a))) + \epsilon_s = g'(\kappa(a))\bar{\mu}(\tilde{\kappa}(l^*(a))) + C(\tilde{\kappa}(l^*(a))) + \epsilon_t,$$
$\{G^*\} \cup \{G_{(a)}^*\}_{a \in G_+^*}$ being a partition. In order to make the reading easier, we use the notation $l_a^* = l^*(a)$ for all $a \in [N]$. For any arm $a$, we denote as $g'(a) \in \{-1, 1\}$ as the label such that the mean of $a$ is $\mu_a = g'(a)\bar{\mu}(l^*(a)) + C(l^*(a))$, in the environment $\nu(G', \bar{\mu})$, for any $\bar{\mu} \in \mathbb{R}^d$.

We need to define the behavior of $\pi$ when facing the environment $\nu(G', \bar{\mu})$ for any $\bar{\mu}$.

Define $S$ as the set of permutations of $[N]$ that switch the blocks in $G^*$, that is to say if $\kappa \in S$ then for all $l \in [L], \exists l' \in [L]$, such that $\kappa(G_l^*) = G_{l'}^*$. For any $\kappa \in S$, $\kappa$ naturally induces a permutation of $[L]$ denoted as $\tilde{\kappa}$ such that for all $a \in [N], l^*(\kappa(a)) = \tilde{\kappa}(l^*(a))$.

First, the strategy $\pi$ uniformly samples a permutation $\kappa$ in $S$ and a vector $\chi \in \{-1, 1\}^L$. From a rough perspective, the strategy $\pi$ will then apply the strategy $\pi'$ by permuting the blocks using $\kappa$ and reversing the means of each block using $\chi$.

<caption>**Algorithm 3 Symmetrization of $\pi'$**</caption>

1: **Input:** $\nu(G', \bar{\mu})$ an environment in $\mathcal{E}_{Sym}(G^*, \gamma)$
2: **Output:** $\hat{G}^\pi$, partition of $[N]$
3: $t = 1$
4: Take $\kappa \sim \mathcal{U}(S)$
5: Take $\chi \sim \mathcal{U}(\{-1, 1\}^L)$
6: **while** $t \le \tau^\pi(A_1^{\pi'}, X_1^{\pi'}, \dots, A_{t-1}^{\pi'}, X_{t-1}^{\pi'})$ **do**
7: &nbsp;&nbsp;&nbsp;&nbsp;Choose an arm with $\pi'$ and get $A_t^\pi(A_1^{\pi'}, X_1^{\pi'}, \dots, A_{t-1}^{\pi'}, X_{t-1}^{\pi'}) \in [N]$.
8: &nbsp;&nbsp;&nbsp;&nbsp;Sample $X_t^\pi$ from $A_t^\pi := \kappa(A_t^\pi')$
9: &nbsp;&nbsp;&nbsp;&nbsp;Create the data $X_t^{\pi'} := \chi(\tilde{\kappa}(l^*(A_t^{\pi'}))) [X_t^\pi - C(\tilde{\kappa}(l^*(A_t^{\pi'})))] + C(l^*(A_t^{\pi'}))$
10: &nbsp;&nbsp;&nbsp;&nbsp;**t=t+1**
11: Compute $\hat{G}^\pi(A_1^{\pi'}, X_1^{\pi'}, \dots, A_\tau^{\pi'}, X_\tau^{\pi'}) := \hat{G}_1^{\pi'}, \dots, \hat{G}_K^{\pi'}$
12: **return** $\hat{G}_1^\pi, \dots, \hat{G}_K^\pi := \kappa(\hat{G}_1^{\pi'}), \dots, \kappa(\hat{G}_K^{\pi'})$

Within the procedure $\pi$, we run algorithm $\pi'$ with modified data $X_1^{\pi'}, \dots, X_\tau^{\pi'}$. At time $t$, the algorithm $\pi'$ chooses to sample the arm $A_t^{\pi'}$, where the decision is based on the data $(X_s^{\pi'}, A_s^{\pi'})_{s \le t-1}$. Instead of sampling the arm chosen by $\pi'$, the algorithm $\pi$ samples $X_t^\pi$ from the arm $A_t^\pi := \kappa(A_t^{\pi'})$ and sends the data $X_t^{\pi'}$ to $\pi'$, according to the formula

$$X_t^{\pi'} = \chi(\tilde{\kappa}(l^*(A_t^{\pi'}))) [X_t^\pi - C(\tilde{\kappa}(l^*(A_t^{\pi'})))] + C(l^*(A_t^{\pi'})),$$

where we recall that $C(l)$ is the offset associated to block $l$. When $\pi'$ decides to stop, $\pi$ also stops; i.e., $\tau^\pi(X_1^\pi, A_1^\pi, \dots, X_\tau^\pi, A_\tau^\pi) = \tau^\pi(X_1^{\pi'}, A_1^{\pi'}, \dots, X_\tau^{\pi'}, A_\tau^{\pi'})$. Then, $\pi'$ outputs a partition $\hat{G}^\pi = \hat{G}_1^{\pi'}, \dots, \hat{G}_K^{\pi'}$ based on the modified data, and $\pi$ outputs $\hat{G}_1^\pi, \dots, \hat{G}_K^\pi := \kappa(\hat{G}_1^{\pi'}), \dots, \kappa(\hat{G}_K^{\pi'})$.

**Lemma B.17.** Take $\kappa \in S$, and $\chi \in \{-1, 1\}^L$. For all $l \in [L]$, define $\bar{\mu}_\kappa(l) := \bar{\mu}(\tilde{\kappa}(l))$. As $\bar{\mu}$ is sampled according to $\gamma^{\otimes L}$, then $\bar{\mu}_\kappa$ follows the same prior $\gamma^{\otimes L}$. Define $G'(\kappa, \chi)$ as a partition of $[N]$ into $2L$ groups such that for all $(l, g) \in [L] \times \{-1; 1\}$, then

$$G'(\kappa, \chi)_{l,g} = \{a \in [N]; l^*(a) = l, \text{ and } g'(\kappa(a))\chi(\tilde{\kappa}(l^*(a))) = g\} = \kappa^{-1} \left( G'_{\tilde{\kappa}(l), g\chi(\tilde{\kappa}(l))} \right).$$

Conditionally on $\kappa, \chi, \bar{\mu}$, the modified data $X_s^{\tau'}$ are distributed according to the probability induced by the interaction between $\pi'$ and the environment $\nu(G'(\kappa, \chi), \bar{\mu}_\kappa)$, after integration on the prior $\gamma$, we have

$$\mathbb{P}_{\pi, G'}(\cdot | \mathcal{Y}, \kappa, \chi) = \mathbb{P}_{\pi', G'(\kappa, \chi)}(\cdot | \mathcal{Y}).$$

**Remark B.18.** It is very important to note that, as $G'$ is a partition with $K = 2L$ groups of the same size, the partition $G'(\kappa, \chi)$ is also balanced.

**Proof of Lemma B.17.** Let $\bar{\mu} \in (\mathbb{R}^d)^L$ be a realization of the prior $\gamma^{\otimes L}$.

When $\pi'$ tries to sample the arm $a = A_t^{\pi'}$, we sample in fact $\kappa(a)$. Using the Gaussian assumption on the data, and the expression of the centers of the environment $\nu(G', \bar{\mu})$, it holds that

$$X_t^\pi = g'(\kappa(a))\bar{\mu}(l^*(\kappa(a))) + C(l^*(\kappa(a))) + \epsilon_s = g'(\kappa(a))\bar{\mu}(\tilde{\kappa}(l^*(a))) + C(\tilde{\kappa}(l^*(a))) + \epsilon_t,$$
where $\epsilon_t \sim \mathcal{N}(0, \sigma^2 I_d)$. We used also in the second equality that $\kappa$ induces a permutation of the blocks, so that $l^*(\kappa(a)) = \tilde{\kappa}(l^*(a))$.

We now decompose $X_t^{\pi'}$, using the expression defined Line 9 of Algorithm 3. Assuming that $\tilde{\kappa}(l^*(a)) = m \in [L]$, we have

$$ 
\begin{aligned}
X_t^{\pi'} &= \chi(m)[X_t^{\pi} - C(m)] + C(l^*(a)) \\
&= \chi(m)[g'(\kappa(a))\bar{\mu}(m) + \epsilon_t] + C(l^*(a)) .
\end{aligned}
$$

We develop and reorganize the terms, and we use the expression $\bar{\mu}_{\kappa}(l) = \bar{\mu}(\tilde{\kappa}(l))$,

$$ 
\begin{aligned}
X_t^{\pi'} &= g'(\kappa(a))\chi(m)\bar{\mu}(m) + \chi(m)\epsilon_t + C(l^*(a)) \\
&= g'(\kappa(a))\chi(m)\bar{\mu}_{\kappa}(l^*(a)) + \chi(m)\epsilon_t + C(l^*(a)) .
\end{aligned}
$$

As $\epsilon_t$ is symmetric with respect to 0, then $\epsilon_t' := \chi(m)\epsilon_t$ is distributed as a normal distribution $\mathcal{N}(0, \sigma^2 I_d)$. Besides, the $(\epsilon_t)_t$ are independent. The arm $a$ appears to $\pi'$ to have a mean $C(l^*(a)) + \tilde{g}\bar{\mu}_{\kappa}(l^*(a))$, where $\tilde{g} = g'(\kappa(a))\chi(\tilde{\kappa}(l^*(a))) \in \{-1, 1\}$. It appears then that the data received by $\pi'$ are distributed as $\nu(G'(\kappa, \chi), \bar{\mu}_{\kappa})$, where, for all $(g, l) \in [L] \times \{-1, 1\}$,

$$ G'(\kappa, \chi)_{l,g} = \{a \in [N]; l^*(a) = l, \text{ and } g'(\kappa(a))\chi(\tilde{\kappa}(l)) = g\} , $$

which proves the first part of the lemma.

The second expression for $G'(\kappa, \chi)_{l,g}$ is now obtained using the fact that $\kappa$ permutes the blocks, so that $l^*(\kappa(a)) = \tilde{\kappa}(l)$ and also that $\chi(\tilde{\kappa}(l)) \in \{-1, 1\}$.

$$ 
\begin{aligned}
\{a \in [N]; l^*(a) = l, \text{ and } g'(\kappa(a))\chi(\tilde{\kappa}(l)) = g\} &= \{a \in [N]; l^*(\kappa(a)) = \tilde{\kappa}(l), \text{ and } g'(\kappa(a)) = g\chi(\tilde{\kappa}(l))\} \\
&= \kappa^{-1} \left( G'_{\tilde{\kappa}(l), g\chi(\tilde{\kappa}(l))} \right) .
\end{aligned}
$$

Finally, if $\bar{\mu} \sim \gamma^{\otimes L}$, by exchangeability of the law of $\gamma^{\otimes L}$, and as $\tilde{\kappa}$ is a permutation of $[L]$, the vector $(\bar{\mu}(\tilde{\kappa}(l)))_{l \in [L]}$ is distributed as $(\bar{\mu}(l))_{l \in [L]}$. We also highlight that the event $\mathcal{Y} = \bigcap_{l \in [L]} \{\Delta/2 \le \|\bar{\mu}(l)\| \le \Delta(\beta - 1)/2\} = \bigcap_{l \in [L]} \{\Delta/2 \le \|\bar{\mu}_{\kappa}(l)\| \le \Delta(\beta - 1)/2\}$ remains the same, so that we have the equality of the laws

$$ \mathbb{P}_{\pi, G'(\kappa, \chi)}(\cdot | \mathcal{Y}, \kappa, \chi) = \mathbb{P}_{\pi', G'(\kappa, \chi)}(\cdot | \mathcal{Y}) . \quad \square $$

### Correction of $\pi$

We now deduce that $\pi$ is $\delta$-PAC on $\mathcal{E}_{Sym}(G^*, \gamma)$ –see Definition B.6.

By construction of the algorithm, and with the definition of $G'(\kappa, \chi)$ given in Lemma B.17, we have conditionally on $\kappa, \chi$, and $\bar{\mu}$,

$$ \mathbb{P}_{\pi, G', \bar{\mu}}(\hat{G}^{\pi} \sim G'|\kappa, \chi) = \mathbb{P}_{\pi', G'(\kappa, \chi), \bar{\mu}_{\kappa}}(\hat{G}^{\pi'} \sim G'(\kappa, \chi)) . $$

If $\bar{\mu} \in \mathcal{Y}$, then we have also $\bar{\mu}_{\kappa} \in \mathcal{Y}$ and the environment $\nu(G'(\kappa, \chi), \bar{\mu}_{\kappa})$ is in $\mathcal{E}(\Delta, \theta, \sigma, N, K, d)$. We recall that $\pi$ is $\delta$-PAC on $\mathcal{E}(\Delta, \theta, \sigma, N, K, d)$, we then have

$$ \mathbb{P}_{\pi', G'(\kappa, \chi), \bar{\mu}_{\kappa}}(\hat{G}^{\pi'} \sim G'(\kappa, \chi)) 1_{\mathcal{Y}} \ge (1 - \delta) 1_{\mathcal{Y}} . $$

The conclusion then follow by integrating over the law of $\kappa, \chi$, and $\bar{\mu}$ to obtain $\mathbb{P}_{\pi, G'}(\hat{G}^{\pi} \sim G'|\mathcal{Y}) \ge 1 - \delta$, and $\pi$ is indeed $\delta$-PAC on $\mathcal{E}_{Sym}(G^*, \gamma)$.

### Symmetry of $\pi$

We want to prove that $\pi$ is symmetric as defined in Definition B.6. Take $a_1, a_2 \in [N]^2$ two arms and assume that $a_1 \in G'_{l_1, g_1}$ and $a_2 \in G'_{l_2, g_2}$.

First, we recall that $A_t^{\pi} = \kappa(A_t^{\pi'})$ so that,

$$ N_{a_1}^{\pi}(\tau) = \sum_{s=1}^{\tau} 1_{A_s^{\pi}=a_1} = \sum_{s=1}^{\tau} 1_{\kappa(A_s^{\pi'})=a_1} = N_{\kappa^{-1}(a_1)}^{\pi'}(\tau) . $$