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) . $$
We now use the expression of the uniform laws that follows $\kappa, \chi$ and Lemma B.17,

$$ 
\begin{aligned}
\mathbb{E}_{\pi, G'}[N_{a_1}^{\pi}(\tau)|\mathcal{Y}] &= \frac{1}{2^L \#S} \sum_{\kappa \in S} \sum_{\chi \in \{-1, 1\}^L} \mathbb{E}_{\pi, G'}[N_{a_1}^{\pi}(\tau)|\mathcal{Y}, \kappa, \chi] \\
&= \frac{1}{2^L \#S} \sum_{\kappa \in S} \sum_{\chi \in \{-1, 1\}^L} \mathbb{E}_{\pi', G'(\kappa, \chi)}[N_{\kappa^{-1}(a_1)}^{\pi'}(\tau)|\mathcal{Y}] .
\end{aligned}
$$

We construct $\kappa' \in S$ a permutation which switches the blocks of $a_1$ and $a_2$, while switching $a_1$ and $a_2$, take

$$ 
\begin{array}{ll}
\forall \epsilon \in \{-1, 1\}, \kappa'(G'_{l_1, \epsilon g_1}) = G'_{l_2, \epsilon g_2}; & \forall \epsilon \in \{-1, 1\}, \kappa'(G'_{l_2, \epsilon g_2}) = G'_{l_1, \epsilon g_1}; \\
\kappa'(a_1) = a_2, \kappa'(a_2) = a_1, \text{ and} & \forall c \in [N], \text{ if } l^*(c) \notin \{l_1, l_2\}, \kappa'(c) = c.
\end{array}
$$

The permutation $\kappa'$ exists because the groups of $G'$ have exactly the same size.

We also define $\chi' \in \{-1, 1\}^L$ with

$$ \chi'(l) = \chi(l) \text{ if } l \notin \{l_1, l_2\}, \quad \chi'(l_1) = (g_1 g_2) \chi(l_2), \quad \text{and} \quad \chi'(l_2) = (g_2 g_1) \chi(l_1). $$

Note that $\kappa' \in S$. When we consider $S$ is a group of permutation we see that $\kappa'S = S$. Moreover, as the law of $\chi(1), \dots, \chi(L)$ is exchangeable and symmetric with respect to 0, $\chi'$ and $\chi$ follow the same distribution.

It implies that we can use a change of variable in the sum,

$$ 
\begin{aligned}
\mathbb{E}_{\pi, G'}[N_{a_1}^{\pi}(\tau)|\mathcal{Y}] &= \frac{1}{2^L \#S} \sum_{\kappa \in S} \sum_{\chi \in \{-1, 1\}^L} \mathbb{E}_{\pi', G'(\kappa, \chi)}[N_{\kappa^{-1}(a_1)}^{\pi'}(\tau)|\mathcal{Y}] \\
&= \frac{1}{2^L \#S} \sum_{\kappa \in S} \sum_{\chi \in \{-1, 1\}^L} \mathbb{E}_{\pi', G'(\kappa'\kappa, \chi')}[N_{(\kappa'\kappa)^{-1}(a_1)}^{\pi'}(\tau)|\mathcal{Y}].
\end{aligned}
$$

Now, for any $\kappa \in S$, $(\kappa'\kappa)^{-1}(a_1) = \kappa^{-1}(\kappa')^{-1}(a_1) = \kappa^{-1}(a_2)$ because $\kappa'$ exchanges $a_1$ and $a_2$.

Then, fix $\chi$ and $\kappa$ and consider the partition $G'(\kappa'\kappa, \chi')$. We want to prove that, $G'(\kappa'\kappa, \chi') = G'(\kappa, \chi)$. By definition (Lemma B.17), we have to prove that $\forall b \in [N]$,

$$ g'(\kappa(b))\chi(\tilde{\kappa}(l^*(b))) = g'(\kappa'\kappa(b))\chi'(\tilde{\kappa}'\tilde{\kappa}(l^*(b))), \quad (23) $$

We prove eq. (23).

Take $\epsilon \in \{-1, 1\}$ and $b \in \kappa^{-1}(G'_{l_1, \epsilon g_1})$, by construction, $\tilde{\kappa}'$ is the transposition $(l_1 \ l_2)$, and we have

$$ \chi'(\tilde{\kappa}'\tilde{\kappa}(l^*(b))) = \chi'(\tilde{\kappa}'(l_1)) = \chi'((l_1 \ l_2)(l_1)) = \chi'(l_2) = (g_1 g_2)\chi(l_1). $$

Besides, we have $\chi(\tilde{\kappa}(l^*(b))) = \chi(l_1)$. Moreover, $\kappa(b) \in G'_{l_1, \epsilon g_1}$ and then $\kappa'(\kappa(b)) \in G'_{l_2, \epsilon g_2}$, i.e., $g'(\kappa'\kappa(b)) = \epsilon g_2$.

The equality in eq. (23) therefore holds for all $b$ in $\kappa^{-1}(G'_{l_1, \epsilon g_1})$,

$$ g'(\kappa(b))\chi(\tilde{\kappa}(l^*(b))) = \epsilon g_2(g_1 g_2)\chi(l_1) = \epsilon g_1\chi(l_1) = g'(\kappa(b))\chi(\tilde{\kappa}(l^*(b))). $$

The labels $l_1$ and $l_2$ play the symmetric role, so we also have the equality of eq. (23) for $b \in \kappa^{-1}(G'_{l_2, \epsilon g_2})$. Finally, if $l^*(\kappa(b)) \notin \{l_1, l_2\}$, then by construction of $\chi'$ and $\kappa'$, we have $\kappa'(\kappa(b)) = \kappa(b)$ and $\chi'(\kappa'\tilde{\kappa}(l^*(b))) = \chi'(\tilde{\kappa}(l^*(b))) = \chi(\tilde{\kappa}(l^*(b)))$.

eq. (23) being proved, we have finally,

$$ 
\begin{aligned}
\mathbb{E}_{\pi, G'}[N_{a_1}^{\pi}(\tau)|\mathcal{Y}] &= \frac{1}{2^L \#S} \sum_{\kappa \in S} \sum_{\chi \in \{-1, 1\}^L} \mathbb{E}_{\pi', G'(\kappa'\kappa, \chi')}[N_{(\kappa'\kappa)^{-1}(a_1)}^{\pi'}(\tau)|\mathcal{Y}] \\
&= \frac{1}{2^L \#S} \sum_{\kappa \in S} \sum_{\chi \in \{-1, 1\}^L} \mathbb{E}_{\pi', G'(\kappa, \chi)}[N_{\kappa^{-1}(a_2)}^{\pi'}(\tau)|\mathcal{Y}] \\
&= \mathbb{E}_{\pi, G'}[N_{a_2}^{\pi}(\tau)|\mathcal{Y}].
\end{aligned}
$$
We now use the expression of the uniform laws that follows $\kappa, \chi$ and Lemma B.17,

$$ 
\begin{aligned}
\mathbb{E}_{\pi, G'}[N_{a_1}^{\pi}(\tau)|\mathcal{Y}] &= \frac{1}{2^L \#S} \sum_{\kappa \in S} \sum_{\chi \in \{-1, 1\}^L} \mathbb{E}_{\pi, G'}[N_{a_1}^{\pi}(\tau)|\mathcal{Y}, \kappa, \chi] \\
&= \frac{1}{2^L \#S} \sum_{\kappa \in S} \sum_{\chi \in \{-1, 1\}^L} \mathbb{E}_{\pi', G'(\kappa, \chi)}[N_{\kappa^{-1}(a_1)}^{\pi'}(\tau)|\mathcal{Y}] .
\end{aligned}
$$

We construct $\kappa' \in S$ a permutation which switches the blocks of $a_1$ and $a_2$, while switching $a_1$ and $a_2$, take

$$ 
\begin{array}{ll}
\forall \epsilon \in \{-1, 1\}, \kappa'(G'_{l_1, \epsilon g_1}) = G'_{l_2, \epsilon g_2}; & \forall \epsilon \in \{-1, 1\}, \kappa'(G'_{l_2, \epsilon g_2}) = G'_{l_1, \epsilon g_1}; \\
\kappa'(a_1) = a_2, \kappa'(a_2) = a_1, \text{ and} & \forall c \in [N], \text{ if } l^*(c) \notin \{l_1, l_2\}, \kappa'(c) = c.
\end{array}
$$

The permutation $\kappa'$ exists because the groups of $G'$ have exactly the same size.

We also define $\chi' \in \{-1, 1\}^L$ with

$$ \chi'(l) = \chi(l) \text{ if } l \notin \{l_1, l_2\}, \quad \chi'(l_1) = (g_1 g_2) \chi(l_2), \quad \text{and} \quad \chi'(l_2) = (g_2 g_1) \chi(l_1). $$

Note that $\kappa' \in S$. When we consider $S$ is a group of permutation we see that $\kappa'S = S$. Moreover, as the law of $\chi(1), \dots, \chi(L)$ is exchangeable and symmetric with respect to 0, $\chi'$ and $\chi$ follow the same distribution.

It implies that we can use a change of variable in the sum,

$$ 
\begin{aligned}
\mathbb{E}_{\pi, G'}[N_{a_1}^{\pi}(\tau)|\mathcal{Y}] &= \frac{1}{2^L \#S} \sum_{\kappa \in S} \sum_{\chi \in \{-1, 1\}^L} \mathbb{E}_{\pi', G'(\kappa, \chi)}[N_{\kappa^{-1}(a_1)}^{\pi'}(\tau)|\mathcal{Y}] \\
&= \frac{1}{2^L \#S} \sum_{\kappa \in S} \sum_{\chi \in \{-1, 1\}^L} \mathbb{E}_{\pi', G'(\kappa'\kappa, \chi')}[N_{(\kappa'\kappa)^{-1}(a_1)}^{\pi'}(\tau)|\mathcal{Y}].
\end{aligned}
$$

Now, for any $\kappa \in S$, $(\kappa'\kappa)^{-1}(a_1) = \kappa^{-1}(\kappa')^{-1}(a_1) = \kappa^{-1}(a_2)$ because $\kappa'$ exchanges $a_1$ and $a_2$.

Then, fix $\chi$ and $\kappa$ and consider the partition $G'(\kappa'\kappa, \chi')$. We want to prove that, $G'(\kappa'\kappa, \chi') = G'(\kappa, \chi)$. By definition (Lemma B.17), we have to prove that $\forall b \in [N]$,

$$ g'(\kappa(b))\chi(\tilde{\kappa}(l^*(b))) = g'(\kappa'\kappa(b))\chi'(\tilde{\kappa}'\tilde{\kappa}(l^*(b))), \quad (23) $$

We prove eq. (23).

Take $\epsilon \in \{-1, 1\}$ and $b \in \kappa^{-1}(G'_{l_1, \epsilon g_1})$, by construction, $\tilde{\kappa}'$ is the transposition $(l_1 \ l_2)$, and we have

$$ \chi'(\tilde{\kappa}'\tilde{\kappa}(l^*(b))) = \chi'(\tilde{\kappa}'(l_1)) = \chi'((l_1 \ l_2)(l_1)) = \chi'(l_2) = (g_1 g_2)\chi(l_1). $$

Besides, we have $\chi(\tilde{\kappa}(l^*(b))) = \chi(l_1)$. Moreover, $\kappa(b) \in G'_{l_1, \epsilon g_1}$ and then $\kappa'(\kappa(b)) \in G'_{l_2, \epsilon g_2}$, i.e., $g'(\kappa'\kappa(b)) = \epsilon g_2$.

The equality in eq. (23) therefore holds for all $b$ in $\kappa^{-1}(G'_{l_1, \epsilon g_1})$,

$$ g'(\kappa(b))\chi(\tilde{\kappa}(l^*(b))) = \epsilon g_2(g_1 g_2)\chi(l_1) = \epsilon g_1\chi(l_1) = g'(\kappa(b))\chi(\tilde{\kappa}(l^*(b))). $$

The labels $l_1$ and $l_2$ play the symmetric role, so we also have the equality of eq. (23) for $b \in \kappa^{-1}(G'_{l_2, \epsilon g_2})$. Finally, if $l^*(\kappa(b)) \notin \{l_1, l_2\}$, then by construction of $\chi'$ and $\kappa'$, we have $\kappa'(\kappa(b)) = \kappa(b)$ and $\chi'(\kappa'\tilde{\kappa}(l^*(b))) = \chi'(\tilde{\kappa}(l^*(b))) = \chi(\tilde{\kappa}(l^*(b)))$.

eq. (23) being proved, we have finally,

$$ 
\begin{aligned}
\mathbb{E}_{\pi, G'}[N_{a_1}^{\pi}(\tau)|\mathcal{Y}] &= \frac{1}{2^L \#S} \sum_{\kappa \in S} \sum_{\chi \in \{-1, 1\}^L} \mathbb{E}_{\pi', G'(\kappa'\kappa, \chi')}[N_{(\kappa'\kappa)^{-1}(a_1)}^{\pi'}(\tau)|\mathcal{Y}] \\
&= \frac{1}{2^L \#S} \sum_{\kappa \in S} \sum_{\chi \in \{-1, 1\}^L} \mathbb{E}_{\pi', G'(\kappa, \chi)}[N_{\kappa^{-1}(a_2)}^{\pi'}(\tau)|\mathcal{Y}] \\
&= \mathbb{E}_{\pi, G'}[N_{a_2}^{\pi}(\tau)|\mathcal{Y}].
\end{aligned}
$$
This proves that $\mathbb{E}_{\pi, G'}[N_{a_1}^{\pi}(\tau)|Y]$ is independent of $a_1$ and equal to $\mathbb{E}_{\pi, G'}[\tau|Y]/N$. Now, using the same method as above with $\kappa' = (a b_a)$, we also deduce that $\mathbb{E}_{\pi, G^*_{(a)}}[\tau|Y] = \mathbb{E}_{\pi, G^*}[\tau|Y]$ does not depend on $a$.

This proves that $\pi$ is symmetric as defined in Definition B.6.

We have proved that $\pi$ is $\delta$-PAC and symmetric on $\mathcal{E}_{Sym}(G^*, \gamma)$. It remains to conclude for the proof of the lemma.

**Budget of $\pi$** By construction of the algorithm, we have

$$ \mathbb{E}_{\pi, G^*}[\tau^\pi|Y, \kappa, \chi] = \mathbb{E}_{\pi', G^*(\kappa, \chi)}[\tau^{\pi'}|Y] \le \sup_{\nu \in \mathcal{E}(\Delta, \theta, \sigma, N, K, d)} \mathbb{E}_{\pi', \nu}[\tau'] , $$

since, on the event $Y$, we have $\nu(G^*(\kappa, \chi), \bar{\mu}) \in \mathcal{E}(\Delta, \theta, \sigma, N, K, d)$. We now use the fact that $\pi$ is in $\Pi_{Sym}(\delta, \mathcal{E}_{Sym}(G^*, \gamma))$, so that

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

Finally, we prove Lemma B.7 by taking the inf over $\pi' \in \Pi(\delta, \mathcal{E}(\Delta, \theta, \sigma, N, K, d))$.

### B.4.3 Proofs from Appendix B.3

**Proof of lemma B.11.** Let $l \in [L]$ and define $Z = \|\bar{\mu}(l)\|^2/\rho^2$. We have $\bar{\mu}(l) \sim \mathcal{N}(0, \rho^2)$ with $\rho^2 = \Delta^2/d$, then $Z \sim \chi_2(d)$ is a chi-square distribution with $d$ degrees of freedom. We apply the Laurent-Massart inequality with $x = (3/8)^2d - \text{see E.2}$,

$$ \mathbb{P}\left(\|\bar{\mu}(l)\| < \frac{\Delta}{2}\right) = \mathbb{P}\left(Z - d < \frac{\Delta^2}{4\rho^2} - d\right) = \mathbb{P}\left(Z - d < -2\sqrt{d(3/8)^2d}\right) \le \exp(-(3/8)^2d) . $$

Then, we notice that $\beta = 4$ satisfies $(\beta - 1)^2/4 \ge 1 + 2(3/8)^2 + 2\sqrt{(3/8)^2}$, we have

$$ \begin{aligned} \mathbb{P}\left(\|\bar{\mu}(l)\| > (\beta - 1)\frac{\Delta}{2}\right) &= \mathbb{P}\left(Z - d > ((\beta - 1)^2/4 - 1)d\right) \\ &\le \mathbb{P}\left(Z - d > 2\sqrt{d(3/8)^2d} + 2(3/8)^2d\right) . \end{aligned} $$

Now, we use the other side of Laurent-Massart inequality with $x = (3/8)^2d$ to obtain

$$ \mathbb{P}\left(\|\bar{\mu}(l)\| > (\beta - 1)\frac{\Delta}{2}\right) \le \exp(-(3/8)^2d) . $$

We recall that we assumed that $d \ge (8/3)^2 \log(K/\delta)$, and so $\exp(-(3/8)^2d) \le \delta/K$. A union bound on $L = K/2$ ensures that lemma B.11 holds. $\square$

**Proof of Lemma B.15.** Let $a \in G_+^*$ be an arm labelled by $(l_a^*, 1)$ in $G^*$ and let $Y, Z \sim \mathbb{P}_{-1}$ - see Definition B.13. We fix an algorithm $\pi$ for the active clustering problem on $\mathcal{E}(G^*, \gamma_2)$. The algorithm $\pi$ is characterized by three families of measurable functions $(\pi_s, \tau_s, f_s)_{s \ge 1}$ where for all $s \ge 1$

* $A_s = \pi_s((A_1, X_1), \dots, (A_{s-1}, X_{s-1}); U_s)$

* $\tau = \min\{t \ge 1; \tau_s((A_1, X_1), \dots, (A_s, X_s); U_s) = 1\}$

* $\hat{g} = f_\tau((A_1, X_1), \dots, (A_\tau, X_\tau); U_\tau)$

Here, the sequence $(U_s)$ captures the fact that $\pi$ can use some external randomness to make decisions. We define $N_{s,a} = \sum_{u=1}^s 1_{\{A_u \in \{a, b_a\}\}}$ and $M_s = \sum_{u=1}^s 1_{\{A_u \in G_a^*\}}$. We consider the event $B_a$ on which the inequalities $N_{\tau,a} = N_a(\tau) + N_{b_a} \le t_a = t$ and $M_\tau \le M_{l_a^*}(\tau) \le T_a = T$ holds. Then, the data collected $(X_1, \dots, X_\tau)$ when $\pi$ interacts with $\nu(G_{(a)}^*, \bar{\mu})$ and $\bar{\mu} \sim \gamma^{\otimes L}$ can be constructed with $Y, Z, \epsilon, U$ using the following coupling.
This proves that $\mathbb{E}_{\pi,G'}[N_{a_1}^\pi(\tau)|\mathcal{Y}]$ is independent of $a_1$ and equal to $\mathbb{E}_{\pi,G'}[\tau|\mathcal{Y}]/N$. Now, using the same method as above with $\kappa' = (a b_a)$, we also deduce that $\mathbb{E}_{\pi,G^*_{(a)}}[\tau|\mathcal{Y}] = \mathbb{E}_{\pi,G^*}[\tau|\mathcal{Y}]$ does not depend on $a$.

This proves that $\pi$ is symmetric as defined in Definition B.6.

We have proved that $\pi$ is $\delta$-PAC and symmetric on $\mathcal{E}_{Sym}(G^*, \gamma)$. It remains to conclude for the proof of the lemma.

**Budget of $\pi$** By construction of the algorithm, we have

$$ \mathbb{E}_{\pi,G^*}[\tau^\pi|\mathcal{Y}, \kappa, \chi] = \mathbb{E}_{\pi',G^*(\kappa,\chi)}[\tau^{\pi'}|\mathcal{Y}] \le \sup_{\nu \in \mathcal{E}(\Delta,\theta,\sigma,N,K,d)} \mathbb{E}_{\pi',\nu}[\tau'] , $$

since, on the event $\mathcal{Y}$, we have $\nu(G^*(\kappa, \chi), \bar{\mu}) \in \mathcal{E}(\Delta, \theta, \sigma, N, K, d)$. We now use the fact that $\pi$ is in $\Pi_{Sym}(\delta, \mathcal{E}_{Sym}(G^*, \gamma))$, so that

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

Finally, we prove Lemma B.7 by taking the inf over $\pi' \in \Pi(\delta, \mathcal{E}(\Delta, \theta, \sigma, N, K, d))$.

### B.4.3 Proofs from Appendix B.3

**Proof of lemma B.11.** Let $l \in [L]$ and define $Z = \|\bar{\mu}(l)\|^2/\rho^2$. We have $\bar{\mu}(l) \sim \mathcal{N}(0, \rho^2)$ with $\rho^2 = \Delta^2/d$, then $Z \sim \chi_2(d)$ is a chi-square distribution with $d$ degrees of freedom. We apply the Laurent-Massart inequality with $x = (3/8)^2d - \text{see E.2}$,

$$ \mathbb{P}\left(\|\bar{\mu}(l)\| < \frac{\Delta}{2}\right) = \mathbb{P}\left(Z - d < \frac{\Delta^2}{4\rho^2} - d\right) = \mathbb{P}\left(Z - d < -2\sqrt{d(3/8)^2d}\right) \le \exp(-(3/8)^2d) . $$

Then, we notice that $\beta = 4$ satisfies $(\beta - 1)^2/4 \ge 1 + 2(3/8)^2 + 2\sqrt{(3/8)^2}$, we have

$$ \begin{aligned} \mathbb{P}\left(\|\bar{\mu}(l)\| > (\beta - 1)\frac{\Delta}{2}\right) &= \mathbb{P}\left(Z - d > ((\beta - 1)^2/4 - 1)d\right) \\ &\le \mathbb{P}\left(Z - d > 2\sqrt{d(3/8)^2d} + 2(3/8)^2d\right) . \end{aligned} $$

Now, we use the other side of Laurent-Massart inequality with $x = (3/8)^2d$ to obtain

$$ \mathbb{P}\left(\|\bar{\mu}(l)\| > (\beta - 1)\frac{\Delta}{2}\right) \le \exp(-(3/8)^2d) . $$

We recall that we assumed that $d \ge (8/3)^2 \log(K/\delta)$, and so $\exp(-(3/8)^2d) \le \delta/K$. A union bound on $L = K/2$ ensures that lemma B.11 holds. $\square$

**Proof of Lemma B.15.** Let $a \in G_+^*$ be an arm labelled by $(l_a^*, 1)$ in $G^*$ and let $Y, Z \sim \mathbb{P}_{-1}$ - see Definition B.13. We fix an algorithm $\pi$ for the active clustering problem on $\mathcal{E}(G^*, \gamma_2)$. The algorithm $\pi$ is characterized by three families of measurable functions $(\pi_s, \tau_s, f_s)_{s \ge 1}$ where for all $s \ge 1$

* $A_s = \pi_s((A_1, X_1), \dots, (A_{s-1}, X_{s-1}); U_s)$

* $\tau = \min\{t \ge 1; \tau_s((A_1, X_1), \dots, (A_s, X_s); U_s) = 1\}$

* $\hat{g} = f_\tau((A_1, X_1), \dots, (A_\tau, X_\tau); U_\tau)$

Here, the sequence $(U_s)$ captures the fact that $\pi$ can use some external randomness to make decisions. We define $N_{s,a} = \sum_{u=1}^s 1_{\{A_u \in \{a, b_a\}\}}$ and $M_s = \sum_{u=1}^s 1_{\{A_u \in G_+^*\}}$. We consider the event $B_a$ on which the inequalities $N_{\tau,a} = N_a(\tau) + N_{b_a} \le t_a = t$ and $M_\tau \le M_{l_a^*}(\tau) \le T_a = T$ holds. Then, the data collected $(X_1, \dots, X_\tau)$ when $\pi$ interacts with $\nu(G_{(a)}^*, \bar{\mu})$ and $\bar{\mu} \sim \gamma^{\otimes L}$ can be constructed with $Y, Z, \epsilon, U$ using the following coupling.
First, we create the observations from arms that belongs to a block different than the one of a, using the variables $(\epsilon_u)_{u \ge 1}$. We sample once and for all $(L-1)$ centers by defining for any $l \in [L] \setminus \{l_a^*\}$,

$$ \bar{\mu}(l) = \rho \epsilon_l, $$

we observe that $(\bar{\mu})_{l \ne l_a^*} \sim \gamma_2^{\otimes (L-1)}$.

Then, for any $s \ge 1$, if $A_s \in G_l^*$ with $l \ne l_a^*$, we can create $X_s$ with the expression

$$ X_s = C(l) + g\bar{\mu}(l) + \sigma\epsilon_{s+L}. $$

Now, for $s \ge 1$, when $A_s \in G_{l_a^*}$, we use $Y, Z$,

$$ \bullet \ X_s = C(l_a^*) + Y_{N_{s,a}} \text{ if } A_s = a $$

$$ \bullet \ X_s = C(l_a^*) - Y_{N_{s,a}} \text{ if } A_s = b_a $$

$$ \bullet \ X_s = C(l_a^*) + g_{A_s}^* Z_{M_s} \text{ if } A_s \in G_{l_a^*} \setminus \{a, b_a\} $$

We highlight that the law of $Y, Z$ is a marginal distribution that captures the fact that the data obtained from the block $G_{l_a^*}$ are obtained using the prior $\gamma$ for $\bar{\mu}(l_a^*)$.

From there, it is possible to give (explicitly) a function $f_a$ measurable with respect to $Y, Z, \epsilon, U$ such that $A_a \cap B_a = f(Y, Z, \epsilon, U)$ where the equality holds in law with respect to $\mathbb{P}_{\pi, G_{(a)}^*}$ (integrated with respect to $\bar{\mu}$). If we use the same measurable function $f_a$ with $X, Y \sim \mathbb{P}_1$, then $A_a \cap B_a = f(Y, Z, \epsilon, U)$ where the equality holds with respect to $\mathbb{P}_{\pi, G^*}$. $\square$

**Proof of Lemma B.16.** We recall that $\pi$ is a $\delta$-PAC algorithm for the problem of active clustering with an oracle. We recall that $A_a = \{\hat{G} \sim G_{(a)}^*\}$. By construction of the partitions $G_{(a)}^*$, these partitions are not equivalent (for the relation $\sim$). We highlight that this is due to the fact that all the groups contain more than two arms. The events $(A_a)_a$ are disjoints, and $\sqcup_{a \in G_+^*} (A_a \cap B_a) \subset \{\hat{G} \not\sim G^*\}$.

Now, we have directly

$$ \mathbb{P}_{\pi, G^*}(\cup_{a \in [N] \setminus S} A_a \cap B_a) \le \mathbb{P}_{\pi, G^*}(\hat{G} \not\sim G^*). $$

By definition, $\pi$ is $\delta$-PAC on $\mathcal{E}_{Sym}(G^*, \gamma_2)$, we have

$$ \begin{aligned} \mathbb{P}_{\pi, G^*}(\hat{G} \not\sim G^*) &= \mathbb{P}_{\pi, G^*}(\hat{G} \not\sim G^* | \mathcal{Y}) \mathbb{P}_{\gamma \otimes L}(\mathcal{Y}) + \mathbb{P}_{\pi, G^*}(\hat{G} \not\sim G^* | \mathcal{Y}^c) \mathbb{P}_{\gamma \otimes L}(\mathcal{Y}^c) \\ &\le \delta + \mathbb{P}_{\gamma \otimes L}(\mathcal{Y}^c) \le 2\delta \end{aligned} $$

For the second point of the lemma, we fix $a \in G_{+}^*$.

$$ \begin{aligned} \mathbb{P}_{\pi, G_{(a)}^*}((A_a \cap B_a)^c) &= \mathbb{P}_{\pi, G_{(a)}^*}(A_a^c \cup B_a^c | \mathcal{Y}) \mathbb{P}_{\gamma \otimes L}(\mathcal{Y}) + \mathbb{P}_{\pi}(A_a^c \cup B_a^c | \mathcal{Y}^c) \mathbb{P}_{\gamma \otimes L}(\mathcal{Y}^c) \\ &\le \mathbb{P}_{\pi, G_{(a)}^*}(A_a^c \cup B_a^c | \mathcal{Y}) + \mathbb{P}_{\gamma \otimes L}(\mathcal{Y}^c) \\ &\le \mathbb{P}_{\pi, G_{(a)}^*}(A_a^c | \mathcal{Y}) + \mathbb{P}_{\pi, G_{(a)}^*}(B_a^c | \mathcal{Y}) + \mathbb{P}_{\gamma \otimes L}(\mathcal{Y}^c). \end{aligned} $$

Now, $\pi$ is $\delta$-PAC which implies that

$$ \mathbb{P}_{\pi, G_{(a)}^*}(A_a^c | \mathcal{Y}) = \mathbb{P}_{\pi, G_{(a)}^*}(\hat{G} \not\sim G_{(a)}^* | \mathcal{Y}) \le \delta. $$

For the second term, we use Markov inequality with respect to the distribution $\mathbb{P}_{\pi, G_{(a)}^*}(\cdot | \mathcal{Y})$. We recall that $\pi$ satisfies a symmetry property and that $t = t_a = 3\mathbb{E}_{\pi, G_{(a)}^*}[N_a(\tau) + N_{b_a}(\tau)]|\mathcal{Y}|$ and $T = T_a = 3\mathbb{E}_{\pi, G_{(a)}^*}[M_{l_a^*}(\tau)]|\mathcal{Y}|$. We also recall that $B_a = \{N_a(\tau) + N_{b_a}(\tau) \le t_a\} \cap \{M_{l_a^*}(\tau) \le T_a\}$. We have with Markov inequality

$$ \mathbb{P}_{\pi, G_{(a)}^*}(B_a^c | \mathcal{Y}) \le \mathbb{P}_{\pi, G_{(a)}^*}(N_a(\tau) + N_{b_a}(\tau) > t_a | \mathcal{Y}) + \mathbb{P}_{\pi, G_{(a)}^*}(M_{l_a^*}(\tau) > T_a | \mathcal{Y}) \le \frac{1}{3} + \frac{1}{3} = \frac{2}{3}. $$

This concludes the proof of Lemma B.16. $\square$
First, we create the observations from arms that belongs to a block different than the one of a, using the variables $(\epsilon_u)_{u \ge 1}$. We sample once and for all $(L-1)$ centers by defining for any $l \in [L] \setminus \{l_a^*\}$,

$$ \bar{\mu}(l) = \rho \epsilon_l, $$

we observe that $(\bar{\mu})_{l \ne l_a^*} \sim \gamma_2^{\otimes (L-1)}$.

Then, for any $s \ge 1$, if $A_s \in G_l^*$ with $l \ne l_a^*$, we can create $X_s$ with the expression

$$ X_s = C(l) + g\bar{\mu}(l) + \sigma\epsilon_{s+L}. $$

Now, for $s \ge 1$, when $A_s \in G_{l_a^*}$, we use $Y, Z$,

$$ \bullet \ X_s = C(l_a^*) + Y_{N_{s,a}} \text{ if } A_s = a $$

$$ \bullet \ X_s = C(l_a^*) - Y_{N_{s,a}} \text{ if } A_s = b_a $$

$$ \bullet \ X_s = C(l_a^*) + g_{A_s}^* Z_{M_s} \text{ if } A_s \in G_{l_a^*} \setminus \{a, b_a\} $$

We highlight that the law of $Y, Z$ is a marginal distribution that captures the fact that the data obtained from the block $G_{l_a^*}$ are obtained using the prior $\gamma$ for $\bar{\mu}(l_a^*)$.

From there, it is possible to give (explicitly) a function $f_a$ measurable with respect to $Y, Z, \epsilon, U$ such that $A_a \cap B_a = f(Y, Z, \epsilon, U)$ where the equality holds in law with respect to $\mathbb{P}_{\pi, G_{(a)}^*}$ (integrated with respect to $\bar{\mu}$). If we use the same measurable function $f_a$ with $X, Y \sim \mathbb{P}_1$, then $A_a \cap B_a = f(Y, Z, \epsilon, U)$ where the equality holds with respect to $\mathbb{P}_{\pi, G^*}$. $\square$

**Proof of Lemma B.16.** We recall that $\pi$ is a $\delta$-PAC algorithm for the problem of active clustering with an oracle. We recall that $A_a = \{\hat{G} \sim G_{(a)}^*\}$. By construction of the partitions $G_{(a)}^*$, these partitions are not equivalent (for the relation $\sim$). We highlight that this is due to the fact that all the groups contain more than two arms. The events $(A_a)_a$ are disjoints, and $\sqcup_{a \in G_+^*} (A_a \cap B_a) \subset \{\hat{G} \not\sim G^*\}$.

Now, we have directly

$$ \mathbb{P}_{\pi, G^*}(\cup_{a \in [N] \setminus S} A_a \cap B_a) \le \mathbb{P}_{\pi, G^*}(\hat{G} \not\sim G^*). $$

By definition, $\pi$ is $\delta$-PAC on $\mathcal{E}_{Sym}(G^*, \gamma_2)$, we have

$$ \begin{aligned} \mathbb{P}_{\pi, G^*}(\hat{G} \not\sim G^*) &= \mathbb{P}_{\pi, G^*}(\hat{G} \not\sim G^* | \mathcal{Y}) \mathbb{P}_{\gamma \otimes L}(\mathcal{Y}) + \mathbb{P}_{\pi, G^*}(\hat{G} \not\sim G^* | \mathcal{Y}^c) \mathbb{P}_{\gamma \otimes L}(\mathcal{Y}^c) \\ &\le \delta + \mathbb{P}_{\gamma \otimes L}(\mathcal{Y}^c) \le 2\delta \end{aligned} $$

For the second point of the lemma, we fix $a \in G_+^*$.

$$ \begin{aligned} \mathbb{P}_{\pi, G_{(a)}^*}((A_a \cap B_a)^c) &= \mathbb{P}_{\pi, G_{(a)}^*}(A_a^c \cup B_a^c | \mathcal{Y}) \mathbb{P}_{\gamma \otimes L}(\mathcal{Y}) + \mathbb{P}_{\pi}(A_a^c \cup B_a^c | \mathcal{Y}^c) \mathbb{P}_{\gamma \otimes L}(\mathcal{Y}^c) \\ &\le \mathbb{P}_{\pi, G_{(a)}^*}(A_a^c \cup B_a^c | \mathcal{Y}) + \mathbb{P}_{\gamma \otimes L}(\mathcal{Y}^c) \\ &\le \mathbb{P}_{\pi, G_{(a)}^*}(A_a^c | \mathcal{Y}) + \mathbb{P}_{\pi, G_{(a)}^*}(B_a^c | \mathcal{Y}) + \mathbb{P}_{\gamma \otimes L}(\mathcal{Y}^c). \end{aligned} $$

Now, $\pi$ is $\delta$-PAC which implies that

$$ \mathbb{P}_{\pi, G_{(a)}^*}(A_a^c | \mathcal{Y}) = \mathbb{P}_{\pi, G_{(a)}^*}(\hat{G} \not\sim G_{(a)}^* | \mathcal{Y}) \le \delta. $$

For the second term, we use Markov inequality with respect to the distribution $\mathbb{P}_{\pi, G_{(a)}^*}(\cdot | \mathcal{Y})$. We recall that $\pi$ satisfies a symmetry property and that $t = t_a = 3\mathbb{E}_{\pi, G_{(a)}^*}[N_a(\tau) + N_{b_a}(\tau)]|\mathcal{Y}|$ and $T = T_a = 3\mathbb{E}_{\pi, G_{(a)}^*}[M_{l_a^*}(\tau)]|\mathcal{Y}|$. We also recall that $B_a = \{N_a(\tau) + N_{b_a}(\tau) \le t_a\} \cap \{M_{l_a^*}(\tau) \le T_a\}$. We have with Markov inequality

$$ \mathbb{P}_{\pi, G_{(a)}^*}(B_a^c | \mathcal{Y}) \le \mathbb{P}_{\pi, G_{(a)}^*}(N_a(\tau) + N_{b_a}(\tau) > t_a | \mathcal{Y}) + \mathbb{P}_{\pi, G_{(a)}^*}(M_{l_a^*}(\tau) > T_a | \mathcal{Y}) \le \frac{1}{3} + \frac{1}{3} = \frac{2}{3}. $$

This concludes the proof of Lemma B.16. $\square$
Proof of Lemma B.14. Let $g \in \{-1, 1\}$ and take $\mathbb{P}_g$ defined in Definition B.13 with the Gaussian prior. We have $\mu \sim \mathcal{N}(0, \rho^2 I_d)$ and conditionally on $\mu$,

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

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

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

First, $Y_1, \dots, Y_t, Z_1, \dots, Z_T$ have i.i.d coordinates and so has $\mu$. Then, it is enough to prove Lemma B.14 in dimension 1. The general case will be obtained by multiplying by $d$ the result for dimension 1. We assume then that $d=1$, and we want to prove that $\text{KL}(\mathbb{P}_{-g}, \mathbb{P}_g) = \frac{2tT\rho^4}{\sigma^4 + \sigma^2\rho^2(T+t)}$.

Now, we specify the distribution of the vector $Y, Z$. As $\mu$ follows a Gaussian distribution, the vector $(X, Y) = Y_1, \dots, X_t, Z_1, \dots, Z_T$ is a Gaussian vector.

With the law of total variance, we have $Y, Z \sim \mathcal{N}(0, \Sigma_g)$ where $\Sigma_g$ is the covariance (square) matrix of size $(T+t)$. The matrix $\Sigma_g$ is defined as follows:

$$ \Sigma_g = \sigma^2 I_{t+T} + \rho^2 \begin{pmatrix} J_{t,t} & gJ_{t,T} \\ gJ_{T,t} & J_{T,T} \end{pmatrix} =: \sigma^2 I_{(t+T)} + \rho^2 H_g, $$

where $I_{(t+T)}$ is the identity matrix of size $(T+t)$, and we define $J_{t,T}$ being the rectangle matrix of size $t \times T$ where all entries are equal to 1.

We observe that $H_g$ has a particular shape, in particular, $H_g^2 = (T+t)H_g$. As a consequence, it is easy to compute its inverse. We have:

$$ \Sigma_g^{-1} = \frac{1}{\sigma^2} I_{(t+T)} + \frac{1}{\tilde{\rho}^2} H_g ; $$

with $\tilde{\rho}^2 = -\frac{\sigma^2}{\tilde{\rho}^2}(\sigma^2 + \rho^2(t+T))$.

Now,

$$ \Sigma_g^{-1} \Sigma_{-g} - I_{(T+t)} = \left( \frac{1}{\sigma^2} I_{(T+t)} + \frac{1}{\tilde{\rho}^2} H_g \right) (\sigma^2 I_{(T+t)} + \rho^2 H_{-g}) - I_{(T+t)} = \frac{\rho^2}{\sigma^2} H_{-g} + \frac{\sigma^2}{\tilde{\rho}^2} H_g + \frac{\rho^2}{\tilde{\rho}^2} H_g H_{-g}, $$

where we compute

$$ H_g H_{-g} = (t-T) \begin{pmatrix} J_{t,t} & -gJ_{t,T} \\ gJ_{T,t} & -J_{T,T} \end{pmatrix}. $$

Finally, with the formula for the KL divergence between two multidimensional Gaussian distribution, we have

$$ \begin{aligned} \text{KL}(\mathbb{P}_{-g}, \mathbb{P}_g) &= \frac{1}{2} \left( \log \frac{|\Sigma_g|}{|\Sigma_{-g}|} + \text{Tr}(\Sigma_g^{-1} \Sigma_{-g} - I_{(T+t)}) + 0\Sigma_g^{-1} 0 \right) \\ &= \frac{1}{2} \left( \frac{\rho^2}{\sigma^2} \text{Tr}(H_{-g}) + \frac{\sigma^2}{\tilde{\rho}^2} \text{Tr}(H_g) + \frac{\rho^2}{\tilde{\rho}^2} \text{Tr}(H_g H_{-g}) \right) \\ &= \frac{1}{2} \left( \frac{\rho^2(t+T)}{\sigma^2} - \frac{\rho^2(T+t)}{\sigma^2 + \rho^2(T+t)} - \frac{\rho^4(T-t)^2}{\sigma^2(\sigma^2 + \rho^2(T+t))} \right) \\ &= \frac{1}{2} \left( \frac{\rho^4((t+T)^2 - (T-t)^2)}{\sigma^2(\sigma^2 + \rho^2(T+t))} \right) = \frac{2tT\rho^4}{\sigma^4 + \sigma^2\rho^2(T+t)} . \end{aligned} $$

This concludes the computation of $\text{KL}(\mathbb{P}_{-g}, \mathbb{P}_g)$. $\square$

## C Analysis of ACB

In this section, we establish that ACB 1 is $\delta$-PAC, and we control its budget thereby proving the part of Theorem 4.1 pertaining to ACB.
Proof of Lemma B.14. Let $g \in \{-1, 1\}$ and take $\mathbb{P}_g$ defined in Definition B.13 with the Gaussian prior. We have $\mu \sim \mathcal{N}(0, \rho^2 I_d)$ and conditionally on $\mu$,

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

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

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

First, $Y_1, \dots, Y_t, Z_1, \dots, Z_T$ have i.i.d coordinates and so has $\mu$. Then, it is enough to prove Lemma B.14 in dimension 1. The general case will be obtained by multiplying by $d$ the result for dimension 1. We assume then that $d=1$, and we want to prove that $\text{KL}(\mathbb{P}_{-g}, \mathbb{P}_g) = \frac{2tT\rho^4}{\sigma^4+\sigma^2\rho^2(T+t)}$.

Now, we specify the distribution of the vector $Y, Z$. As $\mu$ follows a Gaussian distribution, the vector $(X, Y) = Y_1, \dots, X_t, Z_1, \dots, Z_T$ is a Gaussian vector.

With the law of total variance, we have $Y, Z \sim \mathcal{N}(0, \Sigma_g)$ where $\Sigma_g$ is the covariance (square) matrix of size $(T+t)$. The matrix $\Sigma_g$ is defined as follows:

$$ \Sigma_g = \sigma^2 I_{t+T} + \rho^2 \begin{pmatrix} J_{t,t} & gJ_{t,T} \\ gJ_{T,t} & J_{T,T} \end{pmatrix} =: \sigma^2 I_{(t+T)} + \rho^2 H_g , $$

where $I_{(t+T)}$ is the identity matrix of size $(T+t)$, and we define $J_{t,T}$ being the rectangle matrix of size $t \times T$ where all entries are equal to 1.

We observe that $H_g$ has a particular shape, in particular, $H_g^2 = (T+t)H_g$. As a consequence, it is easy to compute its inverse. We have:

$$ \Sigma_g^{-1} = \frac{1}{\sigma^2} I_{(t+T)} + \frac{1}{\tilde{\rho}^2} H_g ; $$

with $\tilde{\rho}^2 = -\frac{\sigma^2}{\rho^2}(\sigma^2 + \rho^2(t+T))$.

Now,

$$ \Sigma_g^{-1} \Sigma_{-g} - I_{(T+t)} = \left( \frac{1}{\sigma^2} I_{(T+t)} + \frac{1}{\tilde{\rho}^2} H_g \right) (\sigma^2 I_{(T+t)} + \rho^2 H_{-g}) - I_{(T+t)} = \frac{\rho^2}{\sigma^2} H_{-g} + \frac{\sigma^2}{\tilde{\rho}^2} H_g + \frac{\rho^2}{\tilde{\rho}^2} H_g H_{-g} , $$

where we compute

$$ H_g H_{-g} = (t-T) \begin{pmatrix} J_{t,t} & -gJ_{t,T} \\ gJ_{T,t} & -J_{T,T} \end{pmatrix} . $$

Finally, with the formula for the KL divergence between two multidimensional Gaussian distribution, we have

$$ \begin{aligned} \text{KL}(\mathbb{P}_{-g}, \mathbb{P}_g) &= \frac{1}{2} \left( \log \frac{|\Sigma_g|}{|\Sigma_{-g}|} + \text{Tr}(\Sigma_g^{-1} \Sigma_{-g} - I_{(T+t)}) + 0 \Sigma_g^{-1} 0 \right) \\ &= \frac{1}{2} \left( \frac{\rho^2}{\sigma^2} \text{Tr}(H_{-g}) + \frac{\sigma^2}{\tilde{\rho}^2} \text{Tr}(H_g) + \frac{\rho^2}{\tilde{\rho}^2} \text{Tr}(H_g H_{-g}) \right) \\ &= \frac{1}{2} \left( \frac{\rho^2(t+T)}{\sigma^2} - \frac{\rho^2(T+t)}{\sigma^2 + \rho^2(T+t)} - \frac{\rho^4(T-t)^2}{\sigma^2(\sigma^2 + \rho^2(T+t))} \right) \\ &= \frac{1}{2} \left( \frac{\rho^4((t+T)^2 - (T-t)^2)}{\sigma^2(\sigma^2 + \rho^2(T+t))} \right) = \frac{2tT\rho^4}{\sigma^4 + \sigma^2\rho^2(T+t)} . \end{aligned} $$

This concludes the computation of $\text{KL}(\mathbb{P}_{-g}, \mathbb{P}_g)$. $\square$

## C Analysis of ACB

In this section, we establish that ACB 1 is $\delta$-PAC, and we control its budget thereby proving the part of Theorem 4.1 pertaining to ACB.
**Theorem C.1.** Let $\delta > 0$. Let $\Delta > 0$, $\theta > 0$ be the two parameters used in the design of ACB, such that $\mathcal{E}(\Delta, \theta, \sigma, N, K, d) \neq \emptyset$. The ACB algorithm (1) is $\delta$-PAC on $\mathcal{E}(\Delta, \theta, \sigma, N, K, d)$. Moreover, define $\tau_{ACB}$ for the budget of ACB($\delta$, $\Delta$, $\theta$). There exist two universal constants $c$ and $c'$ (with $c$ small), independent of all the parameters $\Delta$, $\theta$, $\sigma$, $N$, $K$, $d$ and such that for any environment $\nu$ in $\mathcal{E}(\Delta, \theta, \sigma, N, K, d)$, if we assume that $\frac{\log(K)}{\theta} \le N$, then $\mathbb{E}_{ACB,\nu}[\tau_{ACB}] \le cN + c'A$, and $\tau_{ACB} \le cN + c'(A + B)$ almost surely, where

$$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{\log(K/\delta)}{\theta} + \frac{\sigma^2}{\Delta^2} \frac{1}{\theta} \log\left(\frac{K}{\delta}\right) \left[ \sqrt{d} + \log\log\left(\frac{1}{\theta\delta}\right) \right].$$

In fact, Theorem C.1 is a straightforward consequence of the two following lemmas that separately consider the two sub-routines SRI and ADC.

**Lemma C.2 (Analysis of SRI).** Let $\delta > 0$ be fixed. Let $\Delta > 0$ and $1/K > \theta > 0$ and let $\hat{S} = SRI(\delta, \Delta, \theta)$ be the output of Algorithm SRI applied to an environment in $\mathcal{E}(\Delta, \theta, \sigma, N, K, d)$. Let $\tau_{SRI}$ be the number of samples used by the SRI routine to compute $\hat{S}$. With probability higher than $1 - \delta$, it holds that $\hat{S}$ contains exactly one arm by group.

Moreover, there exist two universal constant $c$ and $c'$ (independent of all the parameters) such that almost surely, we have

$$\tau_{SRI} \le c \frac{1}{\theta} \log \left( \frac{K}{\delta} \right) + c' \frac{\sigma^2}{\Delta^2} \frac{1}{\theta} \log \left( \frac{K}{\delta} \right) \left[ \log(K) + \sqrt{d} + \log \log \left( \frac{1}{\theta \delta} \right) \right]. \quad (24)$$

Also, the expected budget satisfies

$$\mathbb{E}_{\nu}[\tau_{SRI}] \le c \frac{\log(K)}{\theta} + c' \frac{\sigma^2}{\Delta^2} \left[ \frac{\log(K)}{\theta} \log\left(\frac{1}{\theta\delta}\right) + \frac{\log(K)}{\theta} + \sqrt{dK \frac{\log(K)}{\theta} \log\left(\frac{K}{\delta}\right)} \right]. \quad (25)$$

**Lemma C.3 (Analysis of ADC).** Let $\nu$ be an environment in $\mathcal{E}(\Delta, \theta, \sigma, N, K, d)$. Let $S$ be a set of $K$ arms containing exactly one arm belonging to each of the $K$ groups. Let $\hat{G} = ADC(\delta, \Delta, S)$ be the output of the ACD routine, and $\tau_{ADC}$ be the budget of ADC, i.e., the number of samples used to compute $\hat{G}$. First, with probability larger than $1 - \delta$, $\hat{G}$ is a perfect clustering, that is

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

Second, there exists a universal constant $c$ such that

$$\tau_{ADC} \le 2N + c \frac{\sigma^2}{\Delta^2} N \log \left( \frac{N}{\delta} \right) + c \frac{\sigma^2}{\Delta^2} \sqrt{dKN \log \left( \frac{N}{\delta} \right)}. \quad (26)$$

As a warm-up, we discuss the intuition behind the SRI routine in Appendix C.1. Then, we prove Lemma C.2 in Appendix C.2. The proofs of some technical lemmas are postponed to Appendix C.3. Finally, we establish Lemma C.3 in Appendix C.4.

## C.1 Discussion of the SRI routine

In this section, we fix $\Delta > 0$, and $\theta > 0$ the two parameters used in the design of the SRI routine. We also fix $\delta > 0$ and $\sigma > 0$. We consider then the algorithm $SRI = SRI(\delta, \Delta, \theta)$, where the parameters of the algorithm $U$, $(n_s)_s$, $n_{max}$ and $r$ are computed with $\sigma$, $\Delta$, $\theta$ and $\delta$, using the expressions from Remark C.4. We denote by $\mathbb{P}_{\nu}$ for the probability induced by $SRI(\delta, \Delta, \theta)$ and an environment $\nu$.

Let $\nu$ be an environment with a hidden partition $G^* = G_1^*, \dots, G_K^*$ and the centers of the groups $\mu(1), \dots, \mu(K)$, with $\sigma$-subGaussian noises Assumption 2.1. We associate to $G^*$ the labels $(k(a))_{a \in [N]}$ such that the mean of $a$ is $\mu_a = \mu(k(a))$ and $a \in G_{k(a)}^*$. We recall that $\Delta_*$ denotes
**Theorem C.1.** Let $\delta > 0$. Let $\Delta > 0$, $\theta > 0$ be the two parameters used in the design of ACB, such that $\mathcal{E}(\Delta, \theta, \sigma, N, K, d) \neq \emptyset$. The ACB algorithm (1) is $\delta$-PAC on $\mathcal{E}(\Delta, \theta, \sigma, N, K, d)$. Moreover, define $\tau_{ACB}$ for the budget of ACB($\delta$, $\Delta$, $\theta$). There exist two universal constants $c$ and $c'$ (with $c$ small), independent of all the parameters $\Delta$, $\theta$, $\sigma$, $N$, $K$, $d$ and such that for any environment $\nu$ in $\mathcal{E}(\Delta, \theta, \sigma, N, K, d)$, if we assume that $\frac{\log(K)}{\theta} \le N$, then $\mathbb{E}_{ACB,\nu}[\tau_{ACB}] \le cN + c'A$, and $\tau_{ACB} \le cN + c'(A + B)$ almost surely, where

$$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{\log(K/\delta)}{\theta} + \frac{\sigma^2}{\Delta^2} \frac{1}{\theta} \log\left(\frac{K}{\delta}\right) \left[ \sqrt{d} + \log\log\left(\frac{1}{\theta\delta}\right) \right].$$

In fact, Theorem C.1 is a straightforward consequence of the two following lemmas that separately consider the two sub-routines SRI and ADC.

**Lemma C.2 (Analysis of SRI).** Let $\delta > 0$ be fixed. Let $\Delta > 0$ and $1/K > \theta > 0$ and let $\hat{S} = SRI(\delta, \Delta, \theta)$ be the output of Algorithm SRI applied to an environment in $\mathcal{E}(\Delta, \theta, \sigma, N, K, d)$. Let $\tau_{SRI}$ be the number of samples used by the SRI routine to compute $\hat{S}$. With probability higher than $1 - \delta$, it holds that $\hat{S}$ contains exactly one arm by group.

Moreover, there exist two universal constant $c$ and $c'$ (independent of all the parameters) such that almost surely, we have

$$\tau_{SRI} \le c \frac{1}{\theta} \log \left( \frac{K}{\delta} \right) + c' \frac{\sigma^2}{\Delta^2} \frac{1}{\theta} \log \left( \frac{K}{\delta} \right) \left[ \log(K) + \sqrt{d} + \log \log \left( \frac{1}{\theta \delta} \right) \right]. \quad (24)$$

Also, the expected budget satisfies

$$\mathbb{E}_{\nu}[\tau_{SRI}] \le c \frac{\log(K)}{\theta} + c' \frac{\sigma^2}{\Delta^2} \left[ \frac{\log(K)}{\theta} \log\left(\frac{1}{\theta\delta}\right) + \frac{\log(K)}{\theta} + \sqrt{dK \frac{\log(K)}{\theta} \log\left(\frac{K}{\delta}\right)} \right]. \quad (25)$$

**Lemma C.3 (Analysis of ADC).** Let $\nu$ be an environment in $\mathcal{E}(\Delta, \theta, \sigma, N, K, d)$. Let $S$ be a set of $K$ arms containing exactly one arm belonging to each of the $K$ groups. Let $\hat{G} = ADC(\delta, \Delta, S)$ be the output of the ACD routine, and $\tau_{ADC}$ be the budget of ADC, i.e., the number of samples used to compute $\hat{G}$. First, with probability larger than $1 - \delta$, $\hat{G}$ is a perfect clustering, that is

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

Second, there exists a universal constant $c$ such that

$$\tau_{ADC} \le 2N + c \frac{\sigma^2}{\Delta^2} N \log \left( \frac{N}{\delta} \right) + c \frac{\sigma^2}{\Delta^2} \sqrt{dKN \log \left( \frac{N}{\delta} \right)}. \quad (26)$$

As a warm-up, we discuss the intuition behind the SRI routine in Appendix C.1. Then, we prove Lemma C.2 in Appendix C.2. The proofs of some technical lemmas are postponed to Appendix C.3. Finally, we establish Lemma C.3 in Appendix C.4.

## C.1 Discussion of the SRI routine

In this section, we fix $\Delta > 0$, and $\theta > 0$ the two parameters used in the design of the SRI routine. We also fix $\delta > 0$ and $\sigma > 0$. We consider then the algorithm $SRI = SRI(\delta, \Delta, \theta)$, where the parameters of the algorithm $U$, $(n_s)_s$, $n_{max}$ and $r$ are computed with $\sigma$, $\Delta$, $\theta$ and $\delta$, using the expressions from Remark C.4. We denote by $\mathbb{P}_{\nu}$ for the probability induced by $SRI(\delta, \Delta, \theta)$ and an environment $\nu$.

Let $\nu$ be an environment with a hidden partition $G^* = G_1^*, \dots, G_K^*$ and the centers of the groups $\mu(1), \dots, \mu(K)$, with $\sigma$-subGaussian noises Assumption 2.1. We associate to $G^*$ the labels $(k(a))_{a \in [N]}$ such that the mean of $a$ is $\mu_a = \mu(k(a))$ and $a \in G_{k(a)}^*$. We recall that $\Delta_*$ denotes
the minimal gap of $\nu$ and $\theta_*$ is the proportion of arms in the smallest group. We want to study how $SRI = SRI(\delta, \Delta, \theta)$ behaves when it interacts with the environment $\nu$. For now, $\nu$ denotes any environment in the hidden partition model, with subGaussian noises of parameters $\sigma$ – see Assumption 2.1 and Assumption 2.3. In this subsection, in particular, we do not assume anything about $\Delta_*$ and $\theta_*$, unless we specify the contrary.

### Step 1: explanation and notation.

In the algorithm, there are some parameters defined in (9)–(11) that we recall here.

*Remark C.4.* For any $s \ge 1$,

$$
\begin{align*}
U &= \left\lceil \frac{8}{\theta} \log \left( \frac{8K}{\delta} \right) \right\rceil , \\
r &= \left\lceil \log_2(\log(4U/\delta)) \right\rceil , \\
n_s &= \left[ c_1 \frac{\sigma^2}{\Delta^2} (2^s + \log(12K)) \right] \vee \left[ c_2 \frac{\sigma^2}{\Delta^2} \sqrt{d(2^s + \log(6))} \right] , \\
n_{\max} &= n_r \vee \left[ c_3 \frac{\sigma^2}{\Delta^2} \sqrt{d \log(2K)} \right] , \\
s_0 &= r \wedge \min\{s \ge 1; n_s \ge 2\} ,
\end{align*}
$$

where the universal constants $c_1, c_2, c_3$ are respectively defined by $c_1 = 32^2 \vee 8c_{HW}$, $c_2 = 16\sqrt{c_{HW}/2} \vee 32\sqrt{2}$, and $c_3 = 32\sqrt{2}$ where $c_{HW}$ is the constant of Hanson-Wright inequality –see Appendix E. Also, the maximum budget $T_{\max}$ (12) is defined as

$$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}},$$

and thereby only depends on $\theta$, $\Delta$, $K$, and $\delta$.

We refer as an epoch of the algorithm, the successive passage in the $u$ loop in the SRI routine. We introduce some notation, taking into account the dependency on $u$.

At the beginning of the $u$-th epoch, the arm $a_u$ is taken randomly and uniformly on the set $[N]$ of arms (independently of everything else). We denote by $S_u$ for the set of arms selected as representatives before the $u$-th epoch. Before the first epoch, we initialise $S_1 = \{a_0\}$. During the $u$-th epoch, the algorithm decides to add $a_u$ to $S_u$ or not by performing a sequence of tests – see Line 6 to 11 in SRI routine. If $a_u$ is added to $S_u$, it computes (Line 11) two empirical means $\hat{\mu}_{a_u}$ and $\hat{\mu}'_{a_u}$ using $2n_{\max}$ samples.

We say that

* the arm $a_u$ is bad if there exists $a \in S_u$ such that $\|\mu_{a_u} - \mu_a\| \le \Delta/4$;

* the arm $a_u$ is good if for any arm $a \in S_u$ then $\|\mu_{a_u} - \mu_a\| \ge \Delta$.

*Remark C.5.* If $\Delta \ge \Delta_*$, it is possible that some arms are neither good nor bad. Nonetheless, if $\Delta_* \ge \Delta$, then all arms from $\nu$ are good or bad. Moreover, in this case, the arm $a_u$ is bad if and only if $a_u$ is already represented in $S_u$.

We want to add $a_u$ to $S_u$ if $a_u$ is good, but we allow the algorithm to reject some good arms if it does not affect the budget (up to a numerical constant). Anyway, we want to reject every bad arm, and reject them as quickly as possible.

For $s \ge 1$, we define as $\phi_s^u$ for the output of REPRESENTEDTEST($a_u$, $(\hat{\mu}_b, \hat{\mu}'_b)_{b \in S_u}$, $\Delta$, $n_s$) computed during the $u$-th epoch and for the $s$-th step. We call it the test $(u, s)$. We further write,

$$\phi_s^u := \mathbb{1}\{\min_{a \in S_u} \langle \bar{\mu}_{u,s} - \hat{\mu}_a, \bar{\mu}'_{u,s} - \hat{\mu}'_a \rangle \le \frac{\Delta^2}{2}\},$$

where $\bar{\mu}_{u,s}$ and $\hat{\mu}'_{u,s}$ denotes the two empirical means of arm $a_u$ computed with $2n_s$ samples, when REPRESENTEDTEST($a_u$, $(\hat{\mu}_b, \hat{\mu}'_b)_{b \in S_u}$, $\Delta$, $n_s$) is called. Remark that these empirical means are only used for the test $(u, s)$.
the minimal gap of $\nu$ and $\theta_*$ is the proportion of arms in the smallest group. We want to study how $SRI = SRI(\delta, \Delta, \theta)$ behaves when it interacts with the environment $\nu$. For now, $\nu$ denotes any environment in the hidden partition model, with subGaussian noises of parameters $\sigma$ – see Assumption 2.1 and Assumption 2.3. In this subsection, in particular, we do not assume anything about $\Delta_*$ and $\theta_*$, unless we specify the contrary.

**Step 1: explanation and notation.**

In the algorithm, there are some parameters defined in (9)–(11) that we recall here.

Remark C.4. For any $s \ge 1$,

$$
\begin{align*}
U &= \left\lceil \frac{8}{\theta} \log \left( \frac{8K}{\delta} \right) \right\rceil , \\
r &= \left\lceil \log_2(\log(4U/\delta)) \right\rceil , \\
n_s &= \left[ c_1 \frac{\sigma^2}{\Delta^2} (2^s + \log(12K)) \right] \vee \left[ c_2 \frac{\sigma^2}{\Delta^2} \sqrt{d(2^s + \log(6))} \right] , \\
n_{\max} &= n_r \vee \left[ c_3 \frac{\sigma^2}{\Delta^2} \sqrt{d \log(2K)} \right] , \\
s_0 &= r \wedge \min\{s \ge 1; n_s \ge 2\} ,
\end{align*}
$$

where the universal constants $c_1, c_2, c_3$ are respectively defined by $c_1 = 32^2 \vee 8c_{HW}$, $c_2 = 16\sqrt{c_{HW}/2} \vee 32\sqrt{2}$, and $c_3 = 32\sqrt{2}$ where $c_{HW}$ is the constant of Hanson-Wright inequality –see Appendix E. Also, the maximum budget $T_{\max}$ (12) is defined as

$$
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}},
$$

and thereby only depends on $\theta$, $\Delta$, $K$, and $\delta$.

We refer as an epoch of the algorithm, the successive passage in the $u$ loop in the SRI routine. We introduce some notation, taking into account the dependency on $u$.

At the beginning of the $u$-th epoch, the arm $a_u$ is taken randomly and uniformly on the set $[N]$ of arms (independently of everything else). We denote by $S_u$ for the set of arms selected as representatives before the $u$-th epoch. Before the first epoch, we initialise $S_1 = \{a_0\}$. During the $u$-th epoch, the algorithm decides to add $a_u$ to $S_u$ or not by performing a sequence of tests – see Line 6 to 11 in SRI routine. If $a_u$ is added to $S_u$, it computes (Line 11) two empirical means $\hat{\mu}_{a_u}$ and $\hat{\mu}'_{a_u}$ using $2n_{\max}$ samples.

We say that

• the arm $a_u$ is bad if there exists $a \in S_u$ such that $\|\mu_{a_u} - \mu_a\| \le \Delta/4$;

• the arm $a_u$ is good if for any arm $a \in S_u$ then $\|\mu_{a_u} - \mu_a\| \ge \Delta$.

Remark C.5. If $\Delta \ge \Delta_*$, it is possible that some arms are neither good nor bad. Nonetheless, if $\Delta_* \ge \Delta$, then all arms from $\nu$ are good or bad. Moreover, in this case, the arm $a_u$ is bad if and only if $a_u$ is already represented in $S_u$.

We want to add $a_u$ to $S_u$ if $a_u$ is good, but we allow the algorithm to reject some good arms if it does not affect the budget (up to a numerical constant). Anyway, we want to reject every bad arm, and reject them as quickly as possible.

For $s \ge 1$, we define as $\phi_s^u$ for the output of REPRESENTEDTEST($a_u$, $(\hat{\mu}_b, \hat{\mu}'_b)_{b \in S_u}$, $\Delta$, $n_s$) computed during the $u$-th epoch and for the $s$-th step. We call it the test $(u, s)$. We further write,

$$
\phi_s^u := \mathbb{1}\{\min_{a \in S_u} (\bar{\mu}_{u,s} - \hat{\mu}_a, \bar{\mu}'_{u,s} - \hat{\mu}'_a) \le \frac{\Delta^2}{2}\},
$$

where $\bar{\mu}_{u,s}$ and $\hat{\mu}'_{u,s}$ denotes the two empirical means of arm $a_u$ computed with $2n_s$ samples, when $\text{REPRESENTEDTEST}(a_u, (\hat{\mu}_b, \hat{\mu}'_b)_{b \in S_u}, \Delta, n_s)$ is called. Remark that these empirical means are only used for the test $(u, s)$.
We start with some $s_0$ equal to $r \wedge \min\{s \ge 1; n_s \ge 2\}$ so that $n_s$ strictly increases at each iteration $s \to s+1$. If, at some test $s_0 \le s \le r$, it holds that $\phi_s^u = 1$, then $a_u$ is rejected and considered as a bad arm (Line 8). If $a_u$ is rejected, we denote by $\tau_u$ for the time of rejection of $a_u$, $\tau_u := \min\{s_0 \le s \le r; \phi_s^u = 1\}$. If for all $s = s_0, \dots, r$, $\phi_s^u$ is equal to zero (False) (condition in Line 9), then $a_u$ is added to $S_u$ (Line 10) and considered as a new representative. If $a_u$ is not rejected, $\tau_u = +\infty$ by convention. The empirical mean $\hat{\mu}_{a_u}$ (resp. $\hat{\mu}'_a$) denotes the estimator of $\mu_{a_u}$ computed once and for all when $a_u$ is added to $S_u$ (Line 11), and used in every test that follows.

**Remark C.6.** In REPRESENTEDTEST, the condition $\langle \bar{\mu}_{u,s} - \hat{\mu}_a, \bar{\mu}'_{u,s} - \hat{\mu}'_a \rangle \le \frac{\Delta^2}{2}$ is natural, because $\mathbb{E}_\nu[\langle \bar{\mu}_{u,s} - \hat{\mu}_a, \bar{\mu}'_{u,s} - \hat{\mu}'_a \rangle] = \|\mu_{a_u} - \mu_a\|^2$, which is equal to zero if $a$ and $a_u$ are in the same group, and is larger than $\Delta_*$ else. This is a benefit of sub-sampling.

## Step 2: Control the probability of rejecting a good arm or adding a bad arm to S

In order to use the subGaussian noise assumption– see assumption 2.1, we define $\epsilon_a = \frac{\sqrt{n_{\max}}}{\sigma}(\hat{\mu}_a - \mu_a)$ and $\epsilon_{u,s} = \frac{\sqrt{n_s}}{\sigma}(\bar{\mu}_{u,s} - \mu_{a_u})$ (and respectively $\epsilon'_{u,s}, \epsilon'_a$). We refer to corollary E.4 for concentration inequalities on these variables.

With this notation, we develop the statistic $\langle \bar{\mu}_{u,s} - \hat{\mu}_a, \bar{\mu}'_{u,s} - \hat{\mu}'_a \rangle$ as follows

$$ \langle \bar{\mu}_{u,s} - \hat{\mu}_a, \bar{\mu}'_{u,s} - \hat{\mu}'_a \rangle = \|\mu_{a_u} - \mu_a\|^2 + \frac{\sqrt{2}\sigma}{\sqrt{n_{\max}}} \left\langle \frac{\epsilon_a + \epsilon'_a}{\sqrt{2}}, \mu_a - \mu_{a_u} \right\rangle + \frac{\sigma^2}{n_{\max}} \langle \epsilon_a, \epsilon'_a \rangle \\ - \frac{\sigma^2}{\sqrt{n_{\max}n_s}} \langle \epsilon_{u,s}, \epsilon'_a \rangle - \frac{\sigma^2}{\sqrt{n_{\max}n_s}} \langle \epsilon'_{u,s}, \epsilon_a \rangle \\ + \frac{\sqrt{2}\sigma}{\sqrt{n_s}} \left\langle \frac{\epsilon_{u,s} + \epsilon'_{u,s}}{\sqrt{2}}, \mu_{a_u} - \mu_a \right\rangle + \frac{\sigma^2}{n_s} \langle \epsilon_{u,s}, \epsilon'_{u,s} \rangle . \quad (27) $$

We will use concentration inequalities in order to control all deviations of $\langle \bar{\mu}_{u,s} - \hat{\mu}_a, \bar{\mu}'_{u,s} - \hat{\mu}'_a \rangle$ around its mean $\|\mu_{a_u} - \mu_a\|^2$.

**Remark C.7.** In order to estimate the means of the representatives added to $S$, we compute once and for all $(\hat{\mu}_a, \hat{\mu}'_a)$ when arm $a$ is added to $S$ (Line 11) of the SRI routine. It implies that the test statistics $(\phi_s^u)_{s,u}$ are not independent. This is why we condition on the event $\mathcal{Y}$ defined below, which controls once and for all the deviation of the random variables $\epsilon_a$ and $\epsilon'_a$.

We define $\mathcal{Y}$ as the event:

$$ \mathcal{Y} = \left\{ \begin{array}{l} \forall a \in \hat{S}, \forall k \in [K] \setminus \{k(a)\}, \left| \left\langle \frac{\epsilon_a + \epsilon'_a}{\sqrt{2}}, \frac{\mu_a - \mu(k)}{\|\mu_a - \mu(k)\|} \right\rangle \right| \le \frac{1}{16} \sqrt{\frac{\Delta^2}{2\sigma^2}} \sqrt{n_{\max}} \\ \cap \left\{ \forall a \in \hat{S}, |\langle \epsilon_a, \epsilon'_a \rangle| \le \frac{\Delta^2}{16\sigma^2} n_{\max} \right\} \\ \cap \left\{ \forall a \in \hat{S}, \|\epsilon'_a\|^2 \vee \|\epsilon_a\|^2 - \mathbb{E}[\|\epsilon_a\|^2] \le c_{HW} \log(12K/\delta) \vee \sqrt{c_{HW} d \log(12K/\delta)} \right\} \end{array} \right\} \quad (28) $$

where $c_{HW}$ is the universal constant from Hanson-Wright inequality (Lemma E.3).

**Lemma C.8.** For any environment $\nu$, we have,

$$ \mathbb{P}_\nu(\mathcal{Y}) \ge 1 - \delta/4 . $$

We leave the proof of this technical lemma to Appendix C.3; it is a consequence of the concentration of subGaussian random variables, in particular Hanson-Wright inequality (lemma E.3 and corollary E.4).
We start with some $s_0$ equal to $r \wedge \min\{s \ge 1; n_s \ge 2\}$ so that $n_s$ strictly increases at each iteration $s \to s + 1$. If, at some test $s_0 \le s \le r$, it holds that $\phi_s^u = 1$, then $a_u$ is rejected and considered as a bad arm (Line 8). If $a_u$ is rejected, we denote by $\tau_u$ for the time of rejection of $a_u$, $\tau_u := \min\{s_0 \le s \le r; \phi_s^u = 1\}$. If for all $s = s_0, \dots, r$, $\phi_s^u$ is equal to zero (False) (condition in Line 9), then $a_u$ is added to $S_u$ (Line 10) and considered as a new representative. If $a_u$ is not rejected, $\tau_u = +\infty$ by convention. The empirical mean $\hat{\mu}_{a_u}$ (resp. $\hat{\mu}'_a$) denotes the estimator of $\mu_{a_u}$ computed once and for all when $a_u$ is added to $S_u$ (Line 11), and used in every test that follows.

**Remark C.6.** In REPRESENTEDTEST, the condition $\langle \bar{\mu}_{u,s} - \hat{\mu}_a, \bar{\mu}'_{u,s} - \hat{\mu}'_a \rangle \le \frac{\Delta^2}{2}$ is natural, because $\mathbb{E}_\nu[\langle \bar{\mu}_{u,s} - \hat{\mu}_a, \bar{\mu}'_{u,s} - \hat{\mu}'_a \rangle] = \|\mu_{a_u} - \mu_a\|^2$, which is equal to zero if $a$ and $a_u$ are in the same group, and is larger than $\Delta_*$ else. This is a benefit of sub-sampling.

## Step 2: Control the probability of rejecting a good arm or adding a bad arm to S

In order to use the subGaussian noise assumption– see assumption 2.1, we define $\epsilon_a = \frac{\sqrt{n_{\max}}}{\sigma}(\hat{\mu}_a - \mu_a)$ and $\epsilon_{u,s} = \frac{\sqrt{n_s}}{\sigma}(\bar{\mu}_{u,s} - \mu_{a_u})$ (and respectively $\epsilon'_{u,s}, \epsilon'_a$). We refer to corollary E.4 for concentration inequalities on these variables.

With this notation, we develop the statistic $\langle \bar{\mu}_{u,s} - \hat{\mu}_a, \bar{\mu}'_{u,s} - \hat{\mu}'_a \rangle$ as follows

$$ \langle \bar{\mu}_{u,s} - \hat{\mu}_a, \bar{\mu}'_{u,s} - \hat{\mu}'_a \rangle = \|\mu_{a_u} - \mu_a\|^2 + \frac{\sqrt{2}\sigma}{\sqrt{n_{\max}}} \left\langle \frac{\epsilon_a + \epsilon'_a}{\sqrt{2}}, \mu_a - \mu_{a_u} \right\rangle + \frac{\sigma^2}{n_{\max}} \langle \epsilon_a, \epsilon'_a \rangle \\ - \frac{\sigma^2}{\sqrt{n_{\max}n_s}} \langle \epsilon_{u,s}, \epsilon'_a \rangle - \frac{\sigma^2}{\sqrt{n_{\max}n_s}} \langle \epsilon'_{u,s}, \epsilon_a \rangle \\ + \frac{\sqrt{2}\sigma}{\sqrt{n_s}} \left\langle \frac{\epsilon_{u,s} + \epsilon'_{u,s}}{\sqrt{2}}, \mu_{a_u} - \mu_a \right\rangle + \frac{\sigma^2}{n_s} \langle \epsilon_{u,s}, \epsilon'_{u,s} \rangle . \quad (27) $$

We will use concentration inequalities in order to control all deviations of $\langle \bar{\mu}_{u,s} - \hat{\mu}_a, \bar{\mu}'_{u,s} - \hat{\mu}'_a \rangle$ around its mean $\|\mu_{a_u} - \mu_a\|^2$.

**Remark C.7.** In order to estimate the means of the representatives added to $S$, we compute once and for all $(\hat{\mu}_a, \hat{\mu}'_a)$ when arm $a$ is added to $S$ (Line 11) of the SRI routine. It implies that the test statistics $(\phi_s^u)_{s,u}$ are not independent. This is why we condition on the event $\mathcal{Y}$ defined below, which controls once and for all the deviation of the random variables $\epsilon_a$ and $\epsilon'_a$.

We define $\mathcal{Y}$ as the event:

$$ \mathcal{Y} = \left\{ \begin{array}{l} \forall a \in \hat{S}, \forall k \in [K] \setminus \{k(a)\}, \left| \left\langle \frac{\epsilon_a + \epsilon'_a}{\sqrt{2}}, \frac{\mu_a - \mu(k)}{\|\mu_a - \mu(k)\|} \right\rangle \right| \le \frac{1}{16} \sqrt{\frac{\Delta^2}{2\sigma^2}} \sqrt{n_{\max}} \\ \cap \left\{ \forall a \in \hat{S}, |\langle \epsilon_a, \epsilon'_a \rangle| \le \frac{1}{16} \frac{\Delta^2}{\sigma^2} n_{\max} \right\} \\ \cap \left\{ \forall a \in \hat{S}, \|\epsilon'_a\|^2 \vee \|\epsilon_a\|^2 - \mathbb{E}[\|\epsilon_a\|^2] \le c_{HW} \log(12K/\delta) \vee \sqrt{c_{HW} d \log(12K/\delta)} \right\} \end{array} \right\} \quad (28) $$

where $c_{HW}$ is the universal constant from Hanson-Wright inequality (Lemma E.3).

**Lemma C.8.** For any environment $\nu$, we have,

$$ \mathbb{P}_\nu(\mathcal{Y}) \ge 1 - \delta/4 . $$

We leave the proof of this technical lemma to Appendix C.3; it is a consequence of the concentration of subGaussian random variables, in particular Hanson-Wright inequality (lemma E.3 and corollary E.4).
We now give an auxiliary lemma that will be used in the rest of the proof as an elementary brick. For every test $(u, s)$, we define the event $\mathcal{Z}_{u,s}$ as

$$ \mathcal{Z}_{u,s} = \left\{ \exists k \in [K] \setminus \{k(a_u)\} ; \left| \left\langle \frac{\epsilon_{u,s} + \epsilon'_{u,s}}{\sqrt{2}}, \frac{\mu_{a_u} - \mu(k)}{\|\mu_{a_u} - \mu(k)\|} \right\rangle \right| \ge \frac{1}{16} \frac{\Delta^2}{\sigma^2} n_s \right\} \\ \cup \left\{ \left| \langle \epsilon_{u,s}, \epsilon'_{u,s} \rangle \right| \ge \frac{1}{16} \frac{\Delta^2}{\sigma^2} n_s \right\} \tag{29} \\ \cup \left\{ \exists a \in \hat{S} ; \left| \langle \epsilon_{u,s}, \rho'_a \rangle + \langle \epsilon'_{u,s}, \rho_a \rangle \right| \ge \frac{1}{4} \frac{\Delta^2}{\sigma^2} \sqrt{\frac{n_s n_{\max}}{4d + c_{HW} l \vee \sqrt{c_{HW} dl}}} \right\} , $$

with $l = \log(12K/\delta)$ and $c_{HW}$ is the constant from Lemma E.3.

**Lemma C.9.** The sequence of events $(\mathcal{Z}_{u,s})_{u \ge 1, s \ge s_0}$ satisfies four properties.

1. Conditionally on the random directions $(\rho_a, \rho'_a)_a := \left( \frac{\epsilon_a}{\|\epsilon_a\|}, \frac{\epsilon'_a}{\|\epsilon'_a\|} \right)_a$, with $a \in \hat{S}$ the events $\mathcal{Z}_{u,s}$ are independent (for all test $(u, s)$).

2. For all $u \ge 1$ and $\forall s_0 \le s \le r$, the inclusion $\mathcal{Y} \cap \{a_u \text{ is good and } \phi_s^u = 1\} \subset \mathcal{Z}_{u,s}$ holds.

3. For all $u \ge 1$ and $\forall s_0 \le s \le r$, the inclusion $\mathcal{Y} \cap \{a_u \text{ is bad and } \phi_s^u = 0\} \subset \mathcal{Z}_{u,s}$ also holds.

4. Finally, we have $\forall u \ge 1$ and $\forall s_0 \le s \le r$, $\mathbb{P}_\nu(\mathcal{Z}_{u,s}) \le \exp(-2^s)$.

These results are important to prove that the SRI routine actually rejects bad arms and add good arms to $\hat{S}$. We recall that $\phi_s^u = 1$ implies that the test $(u, s)$ would reject $a_u$.

*Sketch of proof.* The terminology bad and good was introduced in the previous paragraph. Let $u \ge 1$ and $s_0 \le s \le r$. The variables $(\epsilon_{u,s}, \epsilon'_{u,s})$ are mutually independent (for any test $(u, s)$), and the event $\mathcal{Z}_{u,s}$ is measurable with respect to $((\rho_a, \rho'_a)_{a \in \hat{S}}, \epsilon_{u,s}, \epsilon'_{u,s})$, the first point of Lemma C.9 is clear.

The construction of the event $\mathcal{Z}_{u,s}$ follows from the decomposition in eq. (27). We notice that if the event $\mathcal{Y}$ holds, the estimation of all centers $(\mu_a, \mu'_a)$ for $a$ in $\hat{S}$ are concentrated around the true centers. The points two and three follow from this observation. Moreover, the deviation of $\bar{\mu}_{u,s}$ around $\mu_{a_u}$ are subGaussian, the point 4 will follow from subGaussian concentration inequalities. We postpone the proof of this result to Appendix C.3. $\square$

Now, in the next lemma, we prove that $r$ is large enough to ensure that, within the procedure, every bad arm is rejected with large probability.

**Lemma C.10.** Recall that $r = \lceil \log_2(\log(4U/\delta)) \rceil$. If $\mathcal{Y}$ holds, then, with probability higher than $1 - \delta/4$, we do not add bad arms to $\hat{S}$, i.e.,

$$ \mathbb{P}_{\nu} \left( \{ \exists a, b \in \hat{S} , \| \mu_a - \mu_b \| \le \Delta/4 \} \cap \mathcal{Y} \right) \le \frac{\delta}{4} . $$

*Proof.* Within the procedure, the algorithm picks at most $U$ arms (without counting $a_0$) – see Line 4 in SRI routine. If there exists $a, b \in \hat{S}$ such that $\|\mu_a - \mu_b\| \le \Delta/4$, it means that there exists an epoch $1 \le u \le U$, where the last test statistic $\phi_r^u$ is equal to zero, although $a_u$ is bad. If the events $\mathcal{Y}$ holds, using the third point of Lemma C.9, the event $\mathcal{Z}_{u,r}$ holds.

In terms of probability, with a simple union bound, we have

$$ \begin{aligned} \mathbb{P}_{\nu} \left( \{ \exists a, b \in \hat{S} , \| \mu_a - \mu_b \| \le \Delta/4 \} \cap \mathcal{Y} \right) &\le \mathbb{P}_{\nu} ( \{ \exists 1 \le u \le U , a_u \text{ is bad} , \phi_r^u = 0 \} \cap \mathcal{Y} ) \\ &\le \sum_{u=1}^{U} \mathbb{P}_{\nu} ( \mathcal{Z}_{u,r} ) . \end{aligned} $$
We now give an auxiliary lemma that will be used in the rest of the proof as an elementary brick. For every test $(u, s)$, we define the event $\mathcal{Z}_{u,s}$ as

$$ \mathcal{Z}_{u,s} = \left\{ \exists k \in [K] \setminus \{k(a_u)\} ; \left| \left\langle \frac{\epsilon_{u,s} + \epsilon'_{u,s}}{\sqrt{2}}, \frac{\mu_{a_u} - \mu(k)}{\|\mu_{a_u} - \mu(k)\|} \right\rangle \right| \ge \frac{1}{16} \frac{\Delta^2}{\sigma^2} n_s \right\} \\ \cup \left\{ \left| \left\langle \epsilon_{u,s}, \epsilon'_{u,s} \right\rangle \right| \ge \frac{1}{16} \frac{\Delta^2}{\sigma^2} n_s \right\} \tag{29} \\ \cup \left\{ \exists a \in \hat{S} ; \left| \left\langle \epsilon_{u,s}, \rho'_a \right\rangle + \left| \left\langle \epsilon'_{u,s}, \rho_a \right\rangle \right| \right| \ge \frac{1}{4} \frac{\Delta^2}{\sigma^2} \sqrt{\frac{n_s n_{\max}}{4d + c_{HW} l \vee \sqrt{c_{HW} dl}}} \right\} , $$

with $l = \log(12K/\delta)$ and $c_{HW}$ is the constant from Lemma E.3.

**Lemma C.9.** The sequence of events $(\mathcal{Z}_{u,s})_{u \ge 1, s \ge s_0}$ satisfies four properties.

1. Conditionally on the random directions $(\rho_a, \rho'_a)_a := \left( \frac{\epsilon_a}{\|\epsilon_a\|}, \frac{\epsilon'_a}{\|\epsilon'_a\|} \right)_a$, with $a \in \hat{S}$ the events $\mathcal{Z}_{u,s}$ are independent (for all test $(u, s)$).

2. For all $u \ge 1$ and $\forall s_0 \le s \le r$, the inclusion $\mathcal{Y} \cap \{a_u \text{ is good and } \phi_s^u = 1\} \subset \mathcal{Z}_{u,s}$ holds.

3. For all $u \ge 1$ and $\forall s_0 \le s \le r$, the inclusion $\mathcal{Y} \cap \{a_u \text{ is bad and } \phi_s^u = 0\} \subset \mathcal{Z}_{u,s}$ also holds.

4. Finally, we have $\forall u \ge 1$ and $\forall s_0 \le s \le r$, $\mathbb{P}_\nu(\mathcal{Z}_{u,s}) \le \exp(-2^s)$.

These results are important to prove that the SRI routine actually rejects bad arms and add good arms to $\hat{S}$. We recall that $\phi_s^u = 1$ implies that the test $(u, s)$ would reject $a_u$.

**Sketch of proof.** The terminology bad and good was introduced in the previous paragraph. Let $u \ge 1$ and $s_0 \le s \le r$. The variables $(\epsilon_{u,s}, \epsilon'_{u,s})$ are mutually independent (for any test $(u, s)$), and the event $\mathcal{Z}_{u,s}$ is measurable with respect to $((\rho_a, \rho'_a)_{a \in \hat{S}}, \epsilon_{u,s}, \epsilon'_{u,s})$, the first point of Lemma C.9 is clear.

The construction of the event $\mathcal{Z}_{u,s}$ follows from the decomposition in eq. (27). We notice that if the event $\mathcal{Y}$ holds, the estimation of all centers $(\mu_a, \mu'_a)$ for $a$ in $\hat{S}$ are concentrated around the true centers. The points two and three follow from this observation. Moreover, the deviation of $\tilde{\mu}_{u,s}$ around $\mu_{a_u}$ are subGaussian, the point 4 will follow from subGaussian concentration inequalities. We postpone the proof of this result to Appendix C.3. $\square$

Now, in the next lemma, we prove that $r$ is large enough to ensure that, within the procedure, every bad arm is rejected with large probability.

**Lemma C.10.** Recall that $r = \lceil \log_2(\log(4U/\delta)) \rceil$. If $\mathcal{Y}$ holds, then, with probability higher than $1 - \delta/4$, we do not add bad arms to $\hat{S}$, i.e.,

$$ \mathbb{P}_{\nu} \left( \{ \exists a, b \in \hat{S} , \| \mu_a - \mu_b \| \le \Delta/4 \} \cap \mathcal{Y} \right) \le \frac{\delta}{4} . $$

**Proof.** Within the procedure, the algorithm picks at most $U$ arms (without counting $a_0$) – see Line 4 in SRI routine. If there exists $a, b \in \hat{S}$ such that $\|\mu_a - \mu_b\| \le \Delta/4$, it means that there exists an epoch $1 \le u \le U$, where the last test statistic $\phi_r^u$ is equal to zero, although $a_u$ is bad. If the events $\mathcal{Y}$ holds, using the third point of Lemma C.9, the event $\mathcal{Z}_{u,r}$ holds.

In terms of probability, with a simple union bound, we have

$$ \begin{aligned} \mathbb{P}_{\nu} \left( \{ \exists a, b \in \hat{S} , \| \mu_a - \mu_b \| \le \Delta/4 \} \cap \mathcal{Y} \right) &\le \mathbb{P}_{\nu} ( \{ \exists 1 \le u \le U , a_u \text{ is bad} , \phi_r^u = 0 \} \cap \mathcal{Y} ) \\ &\le \sum_{u=1}^{U} \mathbb{P}_{\nu} ( \mathcal{Z}_{u,r} ) . \end{aligned} $$
We recall that the probability of $\mathcal{Z}_{u,r}$ is smaller than $\exp(-2^r)$, and we conclude with the expression of $r$.

$$ \mathbb{P}_{\nu} \left( \left\{ \exists a, b \in \hat{S}, \|\mu_a - \mu_b\| \le \Delta/4 \right\} \cap \mathcal{Y} \right) \le U \exp(-2^r) \le \frac{\delta}{4}. \quad \square $$

## C.2 Proof of Lemma C.2

### Step 3: SRI is $\delta$-PAC

For all epochs $u \ge 1$ and $s_0 \le s \le r$, we denote $H_{s,u} := \sum_{v=1}^{u-1} \mathbb{1}_{\{s \le \tau_v \le r\}}$ as the number of arms that are rejected with a time of rejection larger than $s$ within the epochs $1, \dots, u-1$. We highlight that $H_{s_0,u}$ is the total number of arms rejected before epoch $u$.

Now, we define $M = \inf \{u \ge 1; |S_u| = K \text{ or } u > U \text{ or Budget } T_{\max} \}$ as the stopping time (i.e., the number of epochs) of SRI. It corresponds to the number of arms taken randomly from $[N]$, (namely $a_0, \dots, a_{M-1}$) to build the set $\hat{S}$. When $M$ is reached, SRI outputs $\hat{S} = S_M$, whether or not it contains $K$ arms.

We will prove that, with probability higher than $1 - \delta$, we have, on $\mathcal{E}(\Delta, \theta, \sigma, N, K, d)$, we will have $|S_M| = K$ and $S_M$ contains each representative of each cluster.

Now, assume that $\theta_* \ge \theta$ and $\Delta_* \ge \Delta$. We use Appendix C.1 to prove that the SRI routine outputs a set with exactly one arm by group when it interacts with the environment $\nu \in \mathcal{E}(\Delta, \theta, \sigma, N, K, d)$.

First, we define

$$ \mathcal{X} := \bigcap_{s=s_0+1}^{r} \{H_{s,M} < \frac{1}{2^{s-4}} U\}. \quad (30) $$

The definition (12) of $T_{\max}$ ensures that, on the event $\mathcal{X}$, the stopping condition of the SRI routine reduces to the condition $\{|S_u| = K\} \cup \{u > U\}$ and then $M = (U+1) \wedge \min\{u \ge 1; |S_u| = K\}$. It turns out that the event $\mathcal{X}$ has a large probability when it is intersected with $\mathcal{Y}$.

**Lemma C.11.** Let $1+s_0 \le s \le r$ and recall that $H_{s,M} = \#\{u \in [|1; M-1|], s \le \tau_u \le r\}$. It holds that

$$ \mathbb{P}_{\nu} \left( \{H_{s,M} \ge \frac{1}{2^{s-4}} U\} \cap \mathcal{Y} \right) \le \exp(-U/2) . \quad (31) $$

This implies that

$$ \mathbb{P}_{\nu}(\mathcal{Y} \cap \mathcal{X}^c) \le \frac{\delta}{8}. $$

**Proof of Lemma C.11.** We start with the first statement of Lemma C.11, take $s$ such that $s_0 < s \le r$.

If $s = 1, 2$ or $3$, the inequality is trivial because $H_{s,M} \le U$, we assume that $s > 3 \lor s_0$. Recall that $\nu \in \mathcal{E}(\Delta, \theta, \sigma, N, K, d)$, so that all arms are either good or bad. By definition of $\tau_u$, if $s \le \tau_u \le r$, it means that at some test $t \in [s, r]$, $\phi_t^u = 1$ but $\phi_t^u = 0$ for $t < s$. Moreover, each arm is either good or bad because $\Delta_* \ge \Delta$. The following inclusion holds then,

$$ \{s \le \tau_u \le r\} \cap \mathcal{Y} = \left( \{s \le \tau_u \le r\} \cap \{a_u \text{ is good}\} \cap \mathcal{Y} \right) \bigcap \left( \{s \le \tau_u \le r\} \cap \{a_u \text{ is bad}\} \cap \mathcal{Y} \right) \\ \subset \left( \cup_{s \le t \le r} \{\phi_t^u = 1\} \cap \{a_u \text{ is good}\} \cap \mathcal{Y} \right) \bigcap \left( \{\phi_{s-1}^u = 0\} \cap \{a_u \text{ is bad}\} \cap \mathcal{Y} \right). $$

We use the points 2 of Lemma C.9 to get the inclusion $\{\phi_t^u = 1\} \cap \{a_u \text{ is good}\} \cap \mathcal{Y} \subset \mathcal{Z}_{u,t}$ valid for any $t \in [s, r]$. Using the point 3 of the same lemma with $s-1 \ge s_0$, we have also $\{\phi_{s-1}^u = 0\} \cap \{a_u \text{ is bad}\} \cap \mathcal{Y} \subset \mathcal{Z}_{u,s-1}$. Then,

$$ \{s \le \tau_u \le r\} \cap \mathcal{Y} \subset \bigcup_{s-1 \le t \le r} \mathcal{Z}_{u,t}, \quad (32) $$
We recall that the probability of $\mathcal{Z}_{u,r}$ is smaller than $\exp(-2^r)$, and we conclude with the expression of $r$.

$$ \mathbb{P}_{\nu} \left( \left\{ \exists a, b \in \hat{S}, \|\mu_a - \mu_b\| \le \Delta/4 \right\} \cap \mathcal{Y} \right) \le U \exp(-2^r) \le \frac{\delta}{4}. \quad \square $$

## C.2 Proof of Lemma C.2

### Step 3: SRI is $\delta$-PAC

For all epochs $u \ge 1$ and $s_0 \le s \le r$, we denote $H_{s,u} := \sum_{v=1}^{u-1} \mathbb{1}_{\{s \le \tau_v \le r\}}$ as the number of arms that are rejected with a time of rejection larger than $s$ within the epochs $1, \dots, u-1$. We highlight that $H_{s_0,u}$ is the total number of arms rejected before epoch $u$.

Now, we define $M = \inf\{u \ge 1; |S_u| = K \text{ or } u > U \text{ or Budget } T_{\max}\}$ as the stopping time (i.e., the number of epochs) of SRI. It corresponds to the number of arms taken randomly from $[N]$, (namely $a_0, \dots, a_{M-1}$) to build the set $\hat{S}$. When $M$ is reached, SRI outputs $\hat{S} = S_M$, whether or not it contains $K$ arms.

We will prove that, with probability higher than $1 - \delta$, we have, on $\mathcal{E}(\Delta, \theta, \sigma, N, K, d)$, we will have $|S_M| = K$ and $S_M$ contains each representative of each cluster.

Now, assume that $\theta_* \ge \theta$ and $\Delta_* \ge \Delta$. We use Appendix C.1 to prove that the SRI routine outputs a set with exactly one arm by group when it interacts with the environment $\nu \in \mathcal{E}(\Delta, \theta, \sigma, N, K, d)$.

First, we define

$$ \mathcal{X} := \bigcap_{s=s_0+1}^{r} \{H_{s,M} < \frac{1}{2^{s-4}} U\} . \quad (30) $$

The definition (12) of $T_{\max}$ ensures that, on the event $\mathcal{X}$, the stopping condition of the SRI routine reduces to the condition $\{|S_u| = K\} \cup \{u > U\}$ and then $M = (U+1) \wedge \min\{u \ge 1; |S_u| = K\}$. It turns out that the event $\mathcal{X}$ has a large probability when it is intersected with $\mathcal{Y}$.

**Lemma C.11.** Let $1+s_0 \le s \le r$ and recall that $H_{s,M} = \#\{u \in [|1; M-1|], s \le \tau_u \le r\}$. It holds that

$$ \mathbb{P}_{\nu} \left( \{H_{s,M} \ge \frac{1}{2^{s-4}} U\} \cap \mathcal{Y} \right) \le \exp(-U/2) . \quad (31) $$

This implies that

$$ \mathbb{P}_{\nu}(\mathcal{Y} \cap \mathcal{X}^c) \le \frac{\delta}{8}. $$

**Proof of Lemma C.11.** We start with the first statement of Lemma C.11, take $s$ such that $s_0 < s \le r$.

If $s = 1, 2$ or $3$, the inequality is trivial because $H_{s,M} \le U$, we assume that $s > 3 \lor s_0$. Recall that $\nu \in \mathcal{E}(\Delta, \theta, \sigma, N, K, d)$, so that all arms are either good or bad. By definition of $\tau_u$, if $s \le \tau_u \le r$, it means that at some test $t \in [s, r]$, $\phi_t^u = 1$ but $\phi_t^u = 0$ for $t < s$. Moreover, each arm is either good or bad because $\Delta_* \ge \Delta$. The following inclusion holds then,

$$ \{s \le \tau_u \le r\} \cap \mathcal{Y} = (\{s \le \tau_u \le r\} \cap \{a_u \text{ is good}\} \cap \mathcal{Y}) \bigcup (\{s \le \tau_u \le r\} \cap \{a_u \text{ is bad}\} \cap \mathcal{Y}) \\ \subset (\cup_{s \le t \le r} \{\phi_t^u = 1\} \cap \{a_u \text{ is good}\} \cap \mathcal{Y}) \bigcup (\{\phi_{s-1}^u = 0\} \cap \{a_u \text{ is bad}\} \cap \mathcal{Y}) . $$

We use the points 2 of Lemma C.9 to get the inclusion $\{\phi_t^u = 1\} \cap \{a_u \text{ is good}\} \cap \mathcal{Y} \subset \mathcal{Z}_{u,t}$ valid for any $t \in [s, r]$. Using the point 3 of the same lemma with $s-1 \ge s_0$, we have also $\{\phi_{s-1}^u = 0\} \cap \{a_u \text{ is bad}\} \cap \mathcal{Y} \subset \mathcal{Z}_{u,s-1}$. Then,

$$ \{s \le \tau_u \le r\} \cap \mathcal{Y} \subset \bigcup_{s-1 \le t \le r} \mathcal{Z}_{u,t} , \quad (32) $$
and we recall that the events ($\bigcup_{s-1 \le t \le r} \mathcal{Z}_{u,t})_{u \ge 1}$ are independent according to Lemma C.9 (if we condition on the random directions $(\rho_a, \text{rho}'_a)_a$). Now, we use a union bound on $t$ and the bound $\mathbb{P}_\nu(\mathcal{Z}_{u,t}) \le \exp(-2^t)$ valid for any $t \in [s_0, r]$, and we have,

$$ \mathbb{P}_\nu \left( \bigcup_{s-1 \le t \le r} \mathcal{Z}_{u,t} \right) \le \exp(-2^{s-2}) . $$

From the inequality $H_{s,M} = \sum_{u=1}^{M-1} \mathbb{1}_{\{s \le \tau_u \le r\}} \le \sum_{u=1}^{U} \mathbb{1}_{\{s \le \tau_u \le r\}}$, we deduce that $H_{s,M} \mathbb{1}_Y$ is stochastically dominated by $\mathcal{B}(U, q_s)$ where $q_s := \exp(-2^{s-2})$.

We use Chernoff bound with $\alpha \ge \sqrt{q_s}$, we have

$$ \begin{aligned} \mathbb{P}_\nu (H_{s,M} \mathbb{1}_Y \ge (1+\alpha/q_s)q_s U) &\le \left[ \frac{e^{\alpha/q_s}}{(1+\alpha/q_s)^{1+\alpha/q_s}} \right]^{q_s U} \\ &= \exp\left[ \alpha U \left(1 - \log(1+\alpha/q_s)(1+q_s/\alpha)\right) \right] \\ &= (1+\alpha/q_s)^{-\alpha U/2} \exp\left[ \alpha U \left(1 - \log(1+\alpha/q_s)/2\right) - Uq_s \log(1+\alpha/q_s) \right]. \end{aligned} $$

As $\alpha \ge \sqrt{q_s}$ and $s \ge 4$, we have $\alpha/q_s \ge \frac{1}{\sqrt{q_s}} = \exp(2^{s-3}) \ge e^2 - 1$ and then $1 - \log(1+\alpha/q_s)/2 \le 0$. It follows that

$$ \begin{aligned} \mathbb{P}_\nu (H_{s,M} \mathbb{1}_Y \ge 2\alpha U) &\le (1+\alpha/q_s)^{-\alpha U/2} \\ &\le (1+1/\sqrt{q_s})^{-\alpha U/2} \\ &\le \exp\left(-\frac{\alpha U}{2} 2^{s-3}\right) = \exp(-\alpha U 2^{s-4}) . \end{aligned} $$

Finally, taking $\alpha = 1/2^{s-3} \ge \exp(-2^{s-3}) = \sqrt{q_s}$, we deduce the first result of Lemma C.11

$$ \mathbb{P}_\nu \left( \left\{ H_{s,M} \ge \frac{1}{2^{s-4}} U \right\} \cap \mathcal{Y} \right) \le \mathbb{P}_\nu \left( H_{s,M} \mathbb{1}_Y \ge \frac{1}{2^{s-4}} U \right) \le \exp(-U/2) . $$

Directly,

$$ \mathcal{Y} \cap \mathcal{X}^c = \bigcup_{s=1}^r \mathcal{Y} \cap \{H_{s,M} \ge \frac{1}{2^{s-4}} U\}, $$

then, we use the first part of the lemma and a union bound,

$$ \mathbb{P}(\mathcal{Y} \cap \mathcal{X}^c) \le r \exp(-U/2) \le \delta/8, $$

where we conclude with the expression of $U \ge \frac{8K}{\delta} \log(\frac{8r}{\delta}) \ge 2 \log(\frac{8r}{\delta})$. The last inequality follows from the expression of $r$.

□

Now, we study the probability of adding $K$ arms to $S$, before reaching the maximum number of epochs $U$.

**Lemma C.12.** Recall that $\hat{S}$ denotes the output of SRI, consider a group $G_k^*$, it holds that

$$ \mathbb{P}_{\nu}(\{\hat{S} \cap G_k^* = \emptyset\} \cap \{\forall a, b \in \hat{S}, \mu_a \neq \mu_b\} \cap \mathcal{Y} \cap \mathcal{X}) \le 2 \exp\left(-\frac{U\theta}{8}\right). $$

*Proof of Lemma C.12.* Let $k \in [K]$, we study the event $\{\hat{S} \cap G_k^* = \emptyset\}$, event where the group $G_k^*$ is not represented in $\hat{S}$ (the output of the SRI routine). We use here the assumption that the groups are nonempty. If $\hat{S}$ contains arms from different groups but no arm from the group $G_k^*$, it implies that $|\hat{S}| < K$ and then, if the event $\mathcal{X}$ also holds, the algorithm has passed every epochs from $u = 1$ to $U$,
and we recall that the events ($\bigcup_{s-1 \le t \le r} \mathcal{Z}_{u,t})_{u \ge 1}$ are independent according to Lemma C.9 (if we condition on the random directions $(\rho_a, \text{rho}'_a)_a$). Now, we use a union bound on $t$ and the bound $\mathbb{P}_\nu(\mathcal{Z}_{u,t}) \le \exp(-2^t)$ valid for any $t \in [s_0, r]$, and we have,

$$ \mathbb{P}_\nu \left( \bigcup_{s-1 \le t \le r} \mathcal{Z}_{u,t} \right) \le \exp(-2^{s-2}) . $$

From the inequality $H_{s,M} = \sum_{u=1}^{M-1} \mathbb{1}_{\{s \le \tau_u \le r\}} \le \sum_{u=1}^{U} \mathbb{1}_{\{s \le \tau_u \le r\}}$, we deduce that $H_{s,M} \mathbb{1}_Y$ is stochastically dominated by $\mathcal{B}(U, q_s)$ where $q_s := \exp(-2^{s-2})$.

We use Chernoff bound with $\alpha \ge \sqrt{q_s}$, we have

$$ \begin{aligned} \mathbb{P}_\nu (H_{s,M} \mathbb{1}_Y \ge (1 + \alpha/q_s) q_s U) &\le \left[ \frac{e^{\alpha/q_s}}{(1 + \alpha/q_s)^{1+\alpha/q_s}} \right]^{q_s U} \\ &= \exp \left[ \alpha U \left( 1 - \log(1 + \alpha/q_s)(1 + q_s/\alpha) \right) \right] \\ &= (1 + \alpha/q_s)^{-\alpha U/2} \exp \left[ \alpha U \left( 1 - \log(1 + \alpha/q_s)/2 \right) - U q_s \log(1 + \alpha/q_s) \right]. \end{aligned} $$

As $\alpha \ge \sqrt{q_s}$ and $s \ge 4$, we have $\alpha/q_s \ge \frac{1}{\sqrt{q_s}} = \exp(2^{s-3}) \ge e^2 - 1$ and then $1 - \log(1 + \alpha/q_s)/2 \le 0$.

It follows that

$$ \begin{aligned} \mathbb{P}_\nu (H_{s,M} \mathbb{1}_Y \ge 2\alpha U) &\le (1 + \alpha/q_s)^{-\alpha U/2} \\ &\le (1 + 1/\sqrt{q_s})^{-\alpha U/2} \\ &\le \exp \left( -\frac{\alpha U}{2} 2^{s-3} \right) = \exp(-\alpha U 2^{s-4}) . \end{aligned} $$

Finally, taking $\alpha = 1/2^{s-3} \ge \exp(-2^{s-3}) = \sqrt{q_s}$, we deduce the first result of Lemma C.11

$$ \mathbb{P}_\nu \left( \left\{ H_{s,M} \ge \frac{1}{2^{s-4}} U \right\} \cap \mathcal{Y} \right) \le \mathbb{P}_\nu \left( H_{s,M} \mathbb{1}_Y \ge \frac{1}{2^{s-4}} U \right) \le \exp(-U/2) . $$

Directly,

$$ \mathcal{Y} \cap \mathcal{X}^c = \bigcup_{s=1}^r \mathcal{Y} \cap \{H_{s,M} \ge \frac{1}{2^{s-4}} U\}, $$

then, we use the first part of the lemma and a union bound,

$$ \mathbb{P}(\mathcal{Y} \cap \mathcal{X}^c) \le r \exp(-U/2) \le \delta/8, $$

where we conclude with the expression of $U \ge \frac{8K}{\theta} \log(\frac{8r}{\delta}) \ge 2 \log(\frac{8r}{\delta})$. The last inequality follows from the expression of $r$.

□

Now, we study the probability of adding $K$ arms to $S$, before reaching the maximum number of epochs $U$.

**Lemma C.12.** Recall that $\hat{S}$ denotes the output of SRI, consider a group $G_k^*$, it holds that

$$ \mathbb{P}_\nu (\{\hat{S} \cap G_k^* = \emptyset\} \cap \{\forall a, b \in \hat{S}, \mu_a \ne \mu_b\} \cap \mathcal{Y} \cap \mathcal{X}) \le 2 \exp \left( -\frac{U\theta}{8} \right) . $$

*Proof of Lemma C.12.* Let $k \in [K]$, we study the event $\{\hat{S} \cap G_k^* = \emptyset\}$, event where the group $G_k^*$ is not represented in $\hat{S}$ (the output of the SRI routine). We use here the assumption that the groups are nonempty. If $\hat{S}$ contains arms from different groups but no arm from the group $G_k^*$, it implies that $|\hat{S}| < K$ and then, if the event $\mathcal{X}$ also holds, the algorithm has passed every epochs from $u = 1$ to $U$,
i.e., $M = U + 1$. In particular, the algorithm rejected every arm from $G_k^* \cap \{a_1, \dots, a_U\}$. We have the inclusion between events,

$$ \{\hat{S} \cap G_k^* = \emptyset\} \cap \{\forall a \neq b \in \hat{S}, \mu_a \neq \mu_b\} \cap \mathcal{X} \subset \bigcap_{u \in B_k} \{a_u \text{ rejected}\}, $$

where $B_k := G_k^* \cap \{a_1, \dots, a_U\}$ and denote $X_k := |B_k|$. As $\{a_1, \dots, a_U\}$ are i.i.d and uniform on $[N]$ then $X_k$ is binomial with parameters $U$ and $\theta_k = |G_k|/N \ge \theta_* \ge \theta$. Using Hoeffding's bound and taking $\alpha \in (0, 1)$ to be specified later, it holds that

$$ \mathbb{P}_{\nu}(X_k \le \theta U(1-\alpha)) \le \exp(-2\alpha^2 U\theta). \quad (33) $$

Then, as $\Delta_* \ge \Delta$, the arms in $G_k \cap \{a_1, \dots, a_U\}$ are good until one of them is added to $S$. In particular, if none are added to $S$, they are all good. We then have

$$ \{ |\hat{S}| \cap G_k^* = \emptyset \} \cap \{ \forall a \neq b \in \hat{S}, \mu_a \neq \mu_b \} \cap \mathcal{Y} \cap \mathcal{X} \subset \bigcap_{u \in B_k} \{ a_u \text{ good and rejected} \} \cap \mathcal{Y}. $$

If $a_u$ is rejected, it means that $\phi_s^u = 1$ for some $s_0 \le s \le r$, we then have the inclusion $\{a_u \text{ is good and rejected}\} \subset \bigcup_{s \ge s_0} \{a_u \text{ is good and } \phi_s^u = 1\}$. According to the second point of Lemma C.9, we have $\{a_u \text{ is good and rejected}\} \cap \mathcal{Y} \subset \bigcup_{s \ge s_0} \mathcal{Z}_{u,s}$. We denote $\mathcal{Z}_u = \bigcup_{s \ge s_0} \mathcal{Z}_{u,s}$.
In terms of probability, we have $\mathbb{P}_{\nu}(\cap_{u \in B_k} \{a_u \text{ rejected}\} \cap \mathcal{Y}) \le \mathbb{P}_{\nu}(\cap_{u \in B_k} \mathcal{Z}_u)$.

Then, we also have $\mathbb{P}_{\nu}(\mathcal{Z}_{u,s}) \le \exp(-2^s)$ for any $s \in [s_0, r]$, and with a union bound, $\mathbb{P}_{\nu}(\mathcal{Z}_u) \le 1/2$. Moreover, with the first point of Lemma C.9, we deduce that the events $(\mathcal{Z}_u)_u$ are independent (if we condition on $\rho_a, \rho'_a$).

If $X_k > \theta U(1 - \alpha)$ and using the independence of the events $(\mathcal{Z}_u)_u$, we have

$$ \mathbb{P}_{\nu} \left( \{X_k > \theta U(1-\alpha)\} \cap \left( \bigcap_{u \in B_k} \mathcal{Z}_u \right) \right) \le \left( \frac{1}{2} \right)^{\theta U(1-\alpha)}. $$

Finally, with eq. (33), we have

$$ \begin{aligned} & \mathbb{P}_{\nu}(\{\hat{S} \cap G_k^* = \emptyset\} \cap \{\forall a \neq b \in \hat{S}, \mu_a \neq \mu_b\} \cap \mathcal{Y} \cap \mathcal{X}) \\ & \le \mathbb{P}_{\nu} \left( \{X_k > \theta U(1-\alpha)\} \cap \left( \bigcap_{u \in B_k} \mathcal{Z}_u \right) \right) + \mathbb{P}_{\nu}(X_k \le \theta U(1-\alpha)) \\ & \le \exp(-\log(2)\theta U(1-\alpha)) + \exp(-2\alpha^2 U\theta) \\ & \le 2\exp(-U\theta/8). \end{aligned} $$

In the last line, we took $\alpha = 1/2$. $\square$

We now have all the tools that we need to prove that SRI($\delta$, $\Delta$, $\theta$) is $\delta$-PAC on $\mathcal{E}(\Delta, \theta, \sigma, N, K, d)$ for the representative identification problem, which means that with probability higher than $1 - \delta$, SRI outputs a set of $K$ representatives for environments that are $\mathcal{E}(\Delta, \theta, \sigma, N, K, d)$.

*Proof of the first statement of Lemma C.2.* recall that in this subsection, $\nu \in \mathcal{E}(\Delta, \theta, \sigma, N, K, d)$.

As a direct consequence of Lemma C.10, we know that with high probability, $\hat{S}$ does not contain two arms from the same group.

$$ \mathbb{P}_{\nu}(\{\exists a, b \in \hat{S}, \mu_a = \mu_b\} \cap \mathcal{Y}) \le \mathbb{P}_{\nu}(\{\exists a, b \in \hat{S}, \|\mu_a - \mu_b\| \le \Delta/4\} \cap \mathcal{Y}) \le \frac{\delta}{4}. $$

Now, with Lemma C.12, for all $k \in [K]$,

$$ \mathbb{P}_{\nu}(\{\hat{S} \cap G_k^* = \emptyset\} \cap \{\forall a \neq b \in \hat{S}, \mu_a \neq \mu_b\} \cap \mathcal{Y} \cap \mathcal{X}) \le 2 \exp(-U\theta/8). $$
i.e., $M = U + 1$. In particular, the algorithm rejected every arm from $G_k^* \cap \{a_1, \dots, a_U\}$. We have the inclusion between events,

$$ \{\hat{S} \cap G_k^* = \emptyset\} \cap \{\forall a \neq b \in \hat{S}, \mu_a \neq \mu_b\} \cap \mathcal{X} \subset \bigcap_{u \in B_k} \{a_u \text{ rejected}\}, $$

where $B_k := G_k^* \cap \{a_1, \dots, a_U\}$ and denote $X_k := |B_k|$. As $\{a_1, \dots, a_U\}$ are i.i.d and uniform on $[N]$ then $X_k$ is binomial with parameters $U$ and $\theta_k = |G_k|/N \ge \theta_* \ge \theta$. Using Hoeffding's bound and taking $\alpha \in (0, 1)$ to be specified later, it holds that

$$ \mathbb{P}_{\nu}(X_k \le \theta U(1-\alpha)) \le \exp(-2\alpha^2 U\theta). \quad (33) $$

Then, as $\Delta_* \ge \Delta$, the arms in $G_k \cap \{a_1, \dots, a_U\}$ are good until one of them is added to $S$. In particular, if none are added to $S$, they are all good. We then have

$$ \{ |\hat{S}| \cap G_k^* = \emptyset \} \cap \{ \forall a \neq b \in \hat{S}, \mu_a \neq \mu_b \} \cap \mathcal{Y} \cap \mathcal{X} \subset \bigcap_{u \in B_k} \{ a_u \text{ good and rejected} \} \cap \mathcal{Y}. $$

If $a_u$ is rejected, it means that $\phi_s^u = 1$ for some $s_0 \le s \le r$, we then have the inclusion $\{a_u \text{ is good and rejected}\} \subset \bigcup_{s \ge s_0} \{a_u \text{ is good and } \phi_s^u = 1\}$. According to the second point of Lemma C.9, we have $\{a_u \text{ is good and rejected}\} \cap \mathcal{Y} \subset \bigcup_{s \ge s_0} \mathcal{Z}_{u,s}$. We denote $\mathcal{Z}_u = \bigcup_{s \ge s_0} \mathcal{Z}_{u,s}$.
In terms of probability, we have $\mathbb{P}_{\nu}(\cap_{u \in B_k} \{a_u \text{ rejected}\} \cap \mathcal{Y}) \le \mathbb{P}_{\nu}(\cap_{u \in B_k} \mathcal{Z}_u)$.

Then, we also have $\mathbb{P}_{\nu}(\mathcal{Z}_{u,s}) \le \exp(-2^s)$ for any $s \in [s_0, r]$, and with a union bound, $\mathbb{P}_{\nu}(\mathcal{Z}_u) \le 1/2$. Moreover, with the first point of Lemma C.9, we deduce that the events $(\mathcal{Z}_u)_u$ are independent (if we condition on $\rho_a, \rho'_a$).

If $X_k > \theta U(1-\alpha)$ and using the independence of the events $(\mathcal{Z}_u)_u$, we have

$$ \mathbb{P}_{\nu} \left( \{X_k > \theta U(1-\alpha)\} \cap \left( \bigcap_{u \in B_k} \mathcal{Z}_u \right) \right) \le \left( \frac{1}{2} \right)^{\theta U(1-\alpha)}. $$

Finally, with eq. (33), we have

$$ \begin{aligned} & \mathbb{P}_{\nu}(\{\hat{S} \cap G_k^* = \emptyset\} \cap \{\forall a \neq b \in \hat{S}, \mu_a \neq \mu_b\} \cap \mathcal{Y} \cap \mathcal{X}) \\ & \le \mathbb{P}_{\nu} \left( \{X_k > \theta U(1-\alpha)\} \cap \left( \bigcap_{u \in B_k} \mathcal{Z}_u \right) \right) + \mathbb{P}_{\nu}(X_k \le \theta U(1-\alpha)) \\ & \le \exp(-\log(2)\theta U(1-\alpha)) + \exp(-2\alpha^2 U\theta) \\ & \le 2\exp(-U\theta/8). \end{aligned} $$

In the last line, we took $\alpha = 1/2$. $\square$

We now have all the tools that we need to prove that SRI($\delta$, $\Delta$, $\theta$) is $\delta$-PAC on $\mathcal{E}(\Delta, \theta, \sigma, N, K, d)$ for the representative identification problem, which means that with probability higher than $1 - \delta$, SRI outputs a set of $K$ representatives for environments that are $\mathcal{E}(\Delta, \theta, \sigma, N, K, d)$.

*Proof of the first statement of Lemma C.2.* recall that in this subsection, $\nu \in \mathcal{E}(\Delta, \theta, \sigma, N, K, d)$.

As a direct consequence of Lemma C.10, we know that with high probability, $\hat{S}$ does not contain two arms from the same group.

$$ \mathbb{P}_{\nu} \left( \{ \exists a, b \in \hat{S}, \mu_a = \mu_b \} \cap \mathcal{Y} \right) \le \mathbb{P}_{\nu} \left( \{ \exists a, b \in \hat{S}, \|\mu_a - \mu_b\| \le \Delta/4 \} \cap \mathcal{Y} \right) \le \frac{\delta}{4}. $$

Now, with Lemma C.12, for all $k \in [K]$,

$$ \mathbb{P}_{\nu} \left( \{ \hat{S} \cap G_k^* = \emptyset \} \cap \{ \forall a \neq b \in \hat{S}, \mu_a \neq \mu_b \} \cap \mathcal{Y} \cap \mathcal{X} \right) \le 2 \exp(-U\theta/8). $$
Now, we recall that $U \ge \frac{8}{\theta} \log(\frac{8K}{\delta})$ and then $\exp(-U\theta/8) \le \delta/8K$. If the set $\hat{S}$ contains strictly less than $K$ arms then at least one group is not represented. With a union bound on $k \in [K]$,

$$ \mathbb{P}_{\nu} (\{|\hat{S}| < K\} \cap \{\forall a \neq b \in \hat{S}, \mu_a \neq \mu_b\} \cap \mathcal{Y} \cap \mathcal{X}) \le 2K \exp(-U\theta/8) \le \delta/4 . $$

Finally, together with Lemmas C.8 and C.11, we conclude that

$$ \begin{aligned} \mathbb{P}_{\nu} (\forall k \in [K], \exists! a \in \hat{S}; \mu_a = \mu(k)) &\ge 1 - \mathbb{P}_{\nu}(\mathcal{Y}^c) - \mathbb{P}_{\nu}(\mathcal{Y} \cap \mathcal{X}^c) \\ &\quad - \mathbb{P}_{\nu}(|\hat{S}| < K) \cap \{\forall a \neq b \in \hat{S}, \mu_a \neq \mu_b\} \cap \mathcal{Y} \cap \mathcal{X}) \\ &\quad - \mathbb{P}_{\nu}(\{\exists a, b \in \hat{S}, \mu_a = \mu_b\} \cap \mathcal{Y}) \\ &\ge 1 - \delta. \end{aligned} $$

In summary, we have proved that SRI is $\delta$-PAC on $\mathcal{E}(\Delta, \theta, \sigma, N, K, d)$ for the Representatives identification problem. $\square$

### Step 4: upper bound on the budget $\tau_{SRI}$

We establish here the bounds on the budget $\tau_{SRI}$ of Lemma C.2.

**Explanation on $T_{max}$**

By definition (12) of $T_{max}$, we know that, almost surely, the total budget $\tau_{SRI}$ satisfies:

$$ \tau_{SRI} \le 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}}. \quad (34) $$

Although plugging the values of $n_{max}$, $n_s$, $U$, and $s_0$, will lead to (24), we start by gently describing the budget of SRI in order to give intuition on the definition of $T_{max}$.

To analyze the budget, we divide the budget in two parts, $\tau_{SRI} = \tau_{SRI}^a + \tau_{SRI}^r$, where $\tau_{SRI}^a$ is the number of samples used for arms that are added to $\hat{S}$ and $\tau_{SRI}^r$ is the number of samples used for arms that are rejected.

First, we study $\tau_{SRI}^a$. From the algorithm, the arms that are selected in $\hat{S}$ are arms that pass successfully all the tests, and after the tests, they are sampled again $2n_{max}$ times. In total, each arm in $\hat{S}$ is sampled $2n_{max} + \sum_{s=s_0}^{r} 2n_s$, the factor 2 comes from the fact that we compute two empirical means at each time. We have then

$$ \tau_{SRI}^a = 2|\hat{S}|n_{max} + (|\hat{S}| - 1) \sum_{s=s_0}^{r} 2n_s \le 2K \left( n_{max} + \sum_{s=s_0+1}^{r} n_s \right) + 2(|\hat{S}| - 1)n_{s_0}. \quad (35) $$

Now, consider the budget spent for arms that are ultimately rejected during the procedure. For $s_0 \le s \le r$, we defined previously $H_{s,M} = \sum_{u=1}^{M-1} 1_{\{s \le \tau_u \le r\}}$, as the number of arms rejected after at least $s$ tests in the procedure. The algorithm outputs $\hat{S}$ after $M-1$ epochs. In particular, $H_{s_0,M} = M - |\hat{S}|$. Besides, if the candidate $a_u$ is rejected, it is sampled $\sum_{s=s_0}^{\tau_u} 2n_s$ times. This leads us to the equality

$$ \tau_{SRI}^r = \sum_{u=1}^{M-1} \sum_{s=s_0}^{\tau_u} 2n_s 1_{\{a_u \text{ is rejected}\}} = \sum_{s=s_0}^{r} 2H_{s,M}n_s = 2(M - |\hat{S}|)n_{s_0} + 2 \sum_{s=s_0+1}^{r} H_{s,M}n_s. \quad (36) $$

This justifies the definition $T_{max}$ (12), as under the large probability event $\mathcal{X}$, $\tau_{SRI} \le T_{max}$ is directly implied by (35) and (36).

**Upper bound on $T_{max}$**

In order to upper bound $T_{max}$ (12), we need the following lemmas, whose proofs are postponed to Appendix C.3. These lemmas are direct consequences of the expressions of $n_s$, $n_{max}$, $U$ and $r$ from equations (9),(11).
Now, we recall that $U \ge \frac{8}{\theta} \log(\frac{8K}{\delta})$ and then $\exp(-U\theta/8) \le \delta/8K$. If the set $\hat{S}$ contains strictly less than $K$ arms then at least one group is not represented. With a union bound on $k \in [K]$,

$$ \mathbb{P}_{\nu} (\{|\hat{S}| < K\} \cap \{\forall a \neq b \in \hat{S}, \mu_a \neq \mu_b\} \cap \mathcal{Y} \cap \mathcal{X}) \le 2K \exp(-U\theta/8) \le \delta/4 . $$

Finally, together with Lemmas C.8 and C.11, we conclude that

$$ \begin{aligned} \mathbb{P}_{\nu} (\forall k \in [K], \exists! a \in \hat{S}; \mu_a = \mu(k)) &\ge 1 - \mathbb{P}_{\nu}(\mathcal{Y}^c) - \mathbb{P}_{\nu}(\mathcal{Y} \cap \mathcal{X}^c) \\ &\quad - \mathbb{P}_{\nu} (|\hat{S}| < K) \cap \{\forall a \neq b \in \hat{S}, \mu_a \neq \mu_b\} \cap \mathcal{Y} \cap \mathcal{X}) \\ &\quad - \mathbb{P}_{\nu} (\{\exists a, b \in \hat{S}, \mu_a = \mu_b\} \cap \mathcal{Y}) \\ &\ge 1 - \delta. \end{aligned} $$

In summary, we have proved that SRI is $\delta$-PAC on $\mathcal{E}(\Delta, \theta, \sigma, N, K, d)$ for the Representatives identification problem. $\square$

### Step 4: upper bound on the budget $\tau_{SRI}$

We establish here the bounds on the budget $\tau_{SRI}$ of Lemma C.2.

**Explanation on $T_{max}$**

By definition (12) of $T_{max}$, we know that, almost surely, the total budget $\tau_{SRI}$ satisfies:

$$ \tau_{SRI} \le 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}}. \quad (34) $$

Although plugging the values of $n_{max}$, $n_s$, $U$, and $s_0$, will lead to (24), we start by gently describing the budget of SRI in order to give intuition on the definition of $T_{max}$.

To analyze the budget, we divide the budget in two parts, $\tau_{SRI} = \tau_{SRI}^a + \tau_{SRI}^r$, where $\tau_{SRI}^a$ is the number of samples used for arms that are added to $\hat{S}$ and $\tau_{SRI}^r$ is the number of samples used for arms that are rejected.

First, we study $\tau_{SRI}^a$. From the algorithm, the arms that are selected in $\hat{S}$ are arms that pass successfully all the tests, and after the tests, they are sampled again $2n_{max}$ times. In total, each arm in $\hat{S}$ is sampled $2n_{max} + \sum_{s=s_0}^{r} 2n_s$, the factor 2 comes from the fact that we compute two empirical means at each time. We have then

$$ \tau_{SRI}^a = 2|\hat{S}|n_{max} + (|\hat{S}| - 1) \sum_{s=s_0}^{r} 2n_s \le 2K \left( n_{max} + \sum_{s=s_0+1}^{r} n_s \right) + 2(|\hat{S}| - 1)n_{s_0}. \quad (35) $$

Now, consider the budget spent for arms that are ultimately rejected during the procedure. For $s_0 \le s \le r$, we defined previously $H_{s,M} = \sum_{u=1}^{M-1} 1_{\{s \le \tau_u \le r\}}$, as the number of arms rejected after at least $s$ tests in the procedure. The algorithm outputs $\hat{S}$ after $M-1$ epochs. In particular, $H_{s_0,M} = M - |\hat{S}|$. Besides, if the candidate $a_u$ is rejected, it is sampled $\sum_{s=s_0}^{\tau_u} 2n_s$ times. This leads us to the equality

$$ \tau_{SRI}^r = \sum_{u=1}^{M-1} \sum_{s=s_0}^{\tau_u} 2n_s 1_{\{a_u \text{ is rejected}\}} = \sum_{s=s_0}^{r} 2H_{s,M}n_s = 2(M - |\hat{S}|)n_{s_0} + 2 \sum_{s=s_0+1}^{r} H_{s,M}n_s. \quad (36) $$

This justifies the definition $T_{max}$ (12), as under the large probability event $\mathcal{X}$, $\tau_{SRI} \le T_{max}$ is directly implied by (35) and (36).

**Upper bound on $T_{max}$**

In order to upper bound $T_{max}$ (12), we need the following lemmas, whose proofs are postponed to Appendix C.3. These lemmas are direct consequences of the expressions of $n_s$, $n_{max}$, $U$ and $r$ from equations (9),(11).
**Lemma C.13.** Using the explicit expression of $r$, $n_s$, $n_{max}$ and $s_0$ from Remark C.4, we have, up to a universal constant $c$, the inequality

$$ 
\begin{aligned}
K \left( n_{\max} + \sum_{s=s_0+1}^{r} n_s \right) &\le K + c \frac{\sigma^2}{\Delta^2} \left[ \frac{\log(K)}{\theta} \log(K/\delta) + \sqrt{dK \frac{\log(K)}{\theta} \log(K/\delta)} \right] \\
&\le K + c \frac{\sigma^2}{\Delta^2} \frac{1}{\theta} \log \left( \frac{K}{\delta} \right) \left[ \log(K) + \sqrt{d} \right] .
\end{aligned}
$$

**Lemma C.14.** Using the explicit expression of $r$, $U$, $n_s$ and $s_0$ from Remark C.4, we have

$$ U \sum_{s=s_0+1}^{r} \frac{n_s}{2^{s-4}} \le c \frac{\sigma^2}{\Delta^2} \frac{1}{\theta} \log \left( \frac{K}{\delta} \right) \left[ \log(K) + \sqrt{d} + \log \log \left( \frac{1}{\theta \delta} \right) \right], $$

where $c$ is a numerical constant.

Now, by combining (34) with Lemmas C.13 and C.14 and bounding $Un_{s_0}$ by $U + A$ where $A$ is the right side of Lemma C.14, we conclude that

$$ \tau_{SRI} \le T_{\max} \le 2(U + K) + c \frac{\sigma^2}{\Delta^2} \frac{1}{\theta} \log \left( \frac{K}{\delta} \right) \left[ \log(K) + \sqrt{d} + \log \log \left( \frac{1}{\theta \delta} \right) \right], \quad (37) $$

where $c$ is a numerical constant. We have proved (24).

**Upper bound on $\mathbb{E}[\tau_{SRI}]**

We now upper bound the expectation of $\tau_{SRI}$. For that purpose, we now assume that $\nu \in \mathcal{E}(\Delta, \theta, \sigma, N, K, d)$. We will prove (25).

With the same decomposition on the budget $\tau_{SRI} = \tau_{SRI}^a + \tau_{SRI}^r$, and by linearity of the expectation, we deduce from (35) and (36) that

$$ 
\begin{aligned}
\mathbb{E}_{\nu}[\tau_{SRI}] &= \mathbb{E}_{\nu}[\tau_{SRI} \mathbb{1}_{Y^c}] + \mathbb{E}_{\nu}[\tau_{SRI} \mathbb{1}_{Y}] \\
&\le T_{\max} \delta + 2n_{s_0} \mathbb{E}_{\nu}[(M-1)\mathbb{1}_{Y}] + \sum_{s=s_0+1}^{r} 2n_s \mathbb{E}_{\nu}[H_{s,M}\mathbb{1}_{Y}] \\
&\quad + 2\mathbb{E}_{\nu}[|\hat{S}|\mathbb{1}_{Y}] \left(n_{\max} + \sum_{s=s_0+1}^{r} n_s\right) \\
&\le T_{\max} \delta + 2K \left(n_{\max} + \sum_{s=s_0+1}^{r} n_s\right) + 2n_{s_0} \mathbb{E}_{\nu}[(M-1)\mathbb{1}_{Y}] + \sum_{s=s_0+1}^{r} 2n_s \mathbb{E}_{\nu}[H_{s,M}\mathbb{1}_{Y}] .
\end{aligned}
\quad (38) $$

Let us focus on the terms $\mathbb{E}_{\nu}[(M-1)\mathbb{1}_{Y}]$ and $\mathbb{E}_{\nu}[H_{s,M}\mathbb{1}_{Y}]$.

Recall that $H_{s,M} = \sum_{u=1}^{M-1} \mathbb{1}_{\{s \le \tau_u \le r\}}$. We also recall eq. (32), valid for $s > s_0$, and which is a consequence of Lemma C.9 and the fact that $\Delta_* \ge \Delta$,

$$ \{s \le \tau_u \le r\} \cap \mathcal{Y} \subset \bigcup_{s-1 \le t \le r} \mathcal{Z}_{u,t}. $$

We have then,

$$ \mathbb{E}_{\nu}[H_{s,M} \mathbb{1}_{Y}] = \mathbb{E}_{\nu} \left[ \sum_{u=1}^{M-1} \mathbb{1}_{\{s \le \tau_u \le r\} \cap Y} \right] \le \mathbb{E}_{\nu} \left[ \sum_{u=1}^{M-1} \mathbb{1}_{\{\cup_{s-1 \le t \le r} \mathcal{Z}_{u,t}\}} \right]. $$

We can use Wald's equation. Indeed, if we condition on the direction of the estimated centers $(\rho_a, \rho'_a)$, the random variables $\mathbb{1}_{\{\cup_{s-1 \le t \le r} \mathcal{Z}_{u,t}\}}$ are independent and identically distributed for $u = 1, \dots, U$. $\mathbb{P}_{\nu}(\cup_{s-1 \le t \le r} \mathcal{Z}_{u,t}) \le \exp(-2^{s-4})$ thanks to Lemma C.9. We observe that $M$ is a stopping time with respect to the filtration naturally associated to the sequence of epochs, and the sequence $(\cup_{s-1 \le t \le r} \mathcal{Z}_{u,t})_u$ is adapted to this filtration. With Wald's equation, we deduce that

$$ \mathbb{E}_{\nu}[H_{s,M} \mathbb{1}_{Y}] \le \mathbb{E}_{\nu}[(M-1) \mathbb{1}_{Y}] \exp(-2^{s-4}). \quad (39) $$
**Lemma C.13.** Using the explicit expression of $r$, $n_s$, $n_{max}$ and $s_0$ from Remark C.4, we have, up to a universal constant $c$, the inequality

$$ K \left( n_{\max} + \sum_{s=s_0+1}^{r} n_s \right) \le K + c \frac{\sigma^2}{\Delta^2} \left[ \frac{\log(K)}{\theta} \log(K/\delta) + \sqrt{dK \frac{\log(K)}{\theta} \log(K/\delta)} \right] \\ \le K + c \frac{\sigma^2}{\Delta^2} \frac{1}{\theta} \log \left( \frac{K}{\delta} \right) \left[ \log(K) + \sqrt{d} \right] . $$

**Lemma C.14.** Using the explicit expression of $r$, $U$, $n_s$ and $s_0$ from Remark C.4, we have

$$ U \sum_{s=s_0+1}^{r} \frac{n_s}{2^{s-4}} \le c \frac{\sigma^2}{\Delta^2} \frac{1}{\theta} \log \left( \frac{K}{\delta} \right) \left[ \log(K) + \sqrt{d} + \log \log \left( \frac{1}{\theta \delta} \right) \right], $$

where $c$ is a numerical constant.

Now, by combining (34) with Lemmas C.13 and C.14 and bounding $Un_{s_0}$ by $U + A$ where $A$ is the right side of Lemma C.14, we conclude that

$$ \tau_{SRI} \le T_{\max} \le 2(U + K) + c \frac{\sigma^2}{\Delta^2} \frac{1}{\theta} \log \left( \frac{K}{\delta} \right) \left[ \log(K) + \sqrt{d} + \log \log \left( \frac{1}{\theta \delta} \right) \right], \quad (37) $$

where $c$ is a numerical constant. We have proved (24).

**Upper bound on $\mathbb{E}[\tau_{SRI}]**

We now upper bound the expectation of $\tau_{SRI}$. For that purpose, we now assume that $\nu \in \mathcal{E}(\Delta, \theta, \sigma, N, K, d)$. We will prove (25).

With the same decomposition on the budget $\tau_{SRI} = \tau_{SRI}^a + \tau_{SRI}^r$, and by linearity of the expectation, we deduce from (35) and (36) that

$$ \begin{aligned} \mathbb{E}_{\nu}[\tau_{SRI}] &= \mathbb{E}_{\nu}[\tau_{SRI} \mathbb{1}_{Y^c}] + \mathbb{E}_{\nu}[\tau_{SRI} \mathbb{1}_{Y}] \\ &\le T_{\max} \delta + 2n_{s_0} \mathbb{E}_{\nu}[(M-1)\mathbb{1}_{Y}] + \sum_{s=s_0+1}^{r} 2n_s \mathbb{E}_{\nu}[H_{s,M} \mathbb{1}_{Y}] \\ &\quad + 2\mathbb{E}_{\nu}[|\hat{S}|\mathbb{1}_{Y}] \left(n_{\max} + \sum_{s=s_0+1}^{r} n_s\right) \\ &\le T_{\max} \delta + 2K \left(n_{\max} + \sum_{s=s_0+1}^{r} n_s\right) + 2n_{s_0} \mathbb{E}_{\nu}[(M-1)\mathbb{1}_{Y}] + \sum_{s=s_0+1}^{r} 2n_s \mathbb{E}_{\nu}[H_{s,M} \mathbb{1}_{Y}]. \end{aligned} \quad (38) $$

Let us focus on the terms $\mathbb{E}_{\nu}[(M-1)\mathbb{1}_{Y}]$ and $\mathbb{E}_{\nu}[H_{s,M} \mathbb{1}_{Y}]$.

Recall that $H_{s,M} = \sum_{u=1}^{M-1} \mathbb{1}_{\{s \le \tau_u \le r\}}$. We also recall eq. (32), valid for $s > s_0$, and which is a consequence of Lemma C.9 and the fact that $\Delta_* \ge \Delta$,

$$ \{s \le \tau_u \le r\} \cap \mathcal{Y} \subset \bigcup_{s-1 \le t \le r} \mathcal{Z}_{u,t}. $$

We have then,

$$ \mathbb{E}_{\nu}[H_{s,M} \mathbb{1}_{Y}] = \mathbb{E}_{\nu} \left[ \sum_{u=1}^{M-1} \mathbb{1}_{\{s \le \tau_u \le r\} \cap Y} \right] \le \mathbb{E}_{\nu} \left[ \sum_{u=1}^{M-1} \mathbb{1}_{\{\cup_{s-1 \le t \le r} \mathcal{Z}_{u,t}\}} \right]. $$

We can use Wald's equation. Indeed, if we condition on the direction of the estimated centers $(\rho_a, \rho'_a)$, the random variables $\mathbb{1}_{\{\cup_{s-1 \le t \le r} \mathcal{Z}_{u,t}\}}$ are independent and identically distributed for $u = 1, \dots, U$. $\mathbb{P}_{\nu}(\cup_{s-1 \le t \le r} \mathcal{Z}_{u,t}) \le \exp(-2^{s-4})$ thanks to Lemma C.9. We observe that $M$ is a stopping time with respect to the filtration naturally associated to the sequence of epochs, and the sequence $(\cup_{s-1 \le t \le r} \mathcal{Z}_{u,t})_u$ is adapted to this filtration. With Wald's equation, we deduce that

$$ \mathbb{E}_{\nu}[H_{s,M} \mathbb{1}_{Y}] \le \mathbb{E}_{\nu}[(M-1)\mathbb{1}_{Y}] \exp(-2^{s-4}). \quad (39) $$
Hence, we conclude that

$$ \sum_{s=s_0+1}^{r} 2n_s \mathbb{E}_{\nu} [H_{s,M} 1_{\{y\}}] \le \sum_{s=s_0+1}^{r} 2n_s \mathbb{E}_{\nu} [(M-1)1_y] \exp(-2^{s-4}) . \quad (40) $$

It remains to bound $\mathbb{E}_{\nu}[(M-1)1_y]$. We will bound stochastically $M-1$ by a sum of geometric random variables. We recall that $S_u$ is the state of the set of representatives at the beginning of the epoch $u$ and $\hat{S} = S_M$. We define for $k \in [K-1]$, $M_k = \sum_{u=1}^{M-1} 1_{\{|S_u|=k\}}$. The number $M_k$ is the number of epochs necessary to add the $(k+1)$-th arm to $S$. Once $|S_u| = K$, the algorithm stops, so that

$$ M-1 = \sum_{k=1}^{K-1} M_k . $$

Fix now $k \in [K-1]$. If $|\hat{S}| < k$, we have $M_k = 0$. We assume that $|\hat{S}| \ge k$, and we condition on $S^{(k)}$ and $\mathcal{Y}$, the set containing the $k$ first arms that were added to $\hat{S}$. Let $u$ such that $|S_u| = k$. Thanks to the second point of Lemma C.9, it holds that

$$ \{a_u \text{ is good}\} \cap \mathcal{Y} \cap (\cap_{s \in [s_0, r]} \mathcal{Z}_{u,s}^c) \subset \cap_{s \in [s_0, r]} \{\phi_s^u = 0\} = \{a_u \text{ is added to } S\}. $$

Then, the events $\{a_u \text{ is good}\}$, $\mathcal{Y}$ and $\cap_{s \in [r]} \mathcal{Z}_{u,s}^c$ are independent. Moreover, $\mathbb{P}_{\nu}(a_u \text{ is good}) \ge (K-k)\theta_* \ge (K-k)\theta$ because it remains at least $(K-k)$ groups not represented in $S^{(k)}$ and all these groups have a proportion larger than $\theta_*$. We also have thanks to Lemma C.8 and Lemma C.9, $\mathbb{P}_{\nu}(\mathcal{Y}) \ge 1 - \delta/4$ and $\mathbb{P}_{\nu}(\cap_{s \in [r]} \mathcal{Z}_{u,s}^c) \ge 1/2$.

Conditionally on $S_u = S^{(k)}$, and on the estimated centers of the representatives in $S^{(k)}$, the event $\{a_u \text{ is added to } S\}$ are independent and of probability larger than $(1 - \delta/4)(K-k)\theta/2$. Then, $M_k$ is stochastically dominated by a geometric random variable of parameter $(K-k)\theta/4$. Finally, $\mathbb{E}_{\nu}[M_k 1_y] \le \frac{4}{(K-k)\theta}$ and

$$ \mathbb{E}_{\nu}[(M-1)1_y] = \sum_{k=1}^{K-1} \mathbb{E}_{\nu}[M_k 1_y] \le \sum_{k=1}^{K-1} \frac{4}{(K-k)\theta} = \frac{4}{\theta} \sum_{k=1}^{K-1} \frac{1}{k} \le \frac{4}{\theta}(1 + \log(K)) . \quad (41) $$

Now, eq. (40) becomes

$$ \sum_{s=s_0+1}^{r} 2n_s \mathbb{E}_{\nu} [H_{s,M} 1_y] \le \sum_{s=s_0+1}^{r} 2n_s \left[ \frac{4}{\theta} (1 + \log(K)) \exp(-2^{s-4}) \right] . $$

We bound the previous expression, using the same computation as Lemma C.14, and we state the bound as a lemma proved later.

**Lemma C.15.** Using the explicit expression of $r$, $U$, $n_s$, $n_{max}$ and $s_0$ from Remark C.4, we have

$$ \sum_{s=s_0}^{r} n_s \left[ \frac{4}{\theta} \cdot \frac{1 + \log(K)}{\exp(2^{s-4})} \right] \le c \frac{\sigma^2 \log(K)}{\Delta^2} \frac{\log(K)}{\theta} \left[ \log(K) + \sqrt{d} \right], $$

where $c$ is a universal constant.

We come back to eq. (38), using eqs. (40) and (41), we have

$$ \mathbb{E}_{\nu}[\tau_{SRI}] \le T_{\max}\delta + 2K \left( n_{\max} + \sum_{s=s_0+1}^{r} n_s \right) \\ + \frac{8n_{s_0}}{\theta} (1 + \log(K)) + \sum_{s=s_0+1}^{r} 2n_s \left[ \frac{4}{\theta} (1 + \log(K)) \exp(-2^{s-4}) \right] . $$

Now, if we define $A' = \frac{\sigma^2}{\Delta^2} \left[ \frac{\log(K)}{\theta} \log(1/(\theta\delta)) + \frac{\log(K)}{\theta} \sqrt{d} + \sqrt{dK \frac{\log(K)}{\theta} \log(K/\delta)} \right]$, Lemma C.13 and Lemma C.15 implies that we can choose $c$ large enough (and universal) such that

$$ \sum_{s=s_0+1}^{r} 2n_s \left[ \frac{4}{\theta} (1 + \log(K)) \exp(-2^{s-4}) \right] + 2K \left( n_{\max} + \sum_{s=s_0+1}^{r} n_s \right) \le 2K + cA' . $$
Hence, we conclude that

$$ \sum_{s=s_0+1}^{r} 2n_s \mathbb{E}_{\nu} [H_{s,M} 1_{\{y\}}] \le \sum_{s=s_0+1}^{r} 2n_s \mathbb{E}_{\nu} [(M-1)1_y] \exp(-2^{s-4}) . \quad (40) $$

It remains to bound $\mathbb{E}_{\nu}[(M-1)1_y]$. We will bound stochastically $M-1$ by a sum of geometric random variables. We recall that $S_u$ is the state of the set of representatives at the beginning of the epoch $u$ and $\hat{S} = S_M$. We define for $k \in [K-1]$, $M_k = \sum_{u=1}^{M-1} 1_{\{|S_u|=k\}}$. The number $M_k$ is the number of epochs necessary to add the $(k+1)$-th arm to $S$. Once $|S_u| = K$, the algorithm stops, so that

$$ M-1 = \sum_{k=1}^{K-1} M_k . $$

Fix now $k \in [K-1]$. If $|\hat{S}| < k$, we have $M_k = 0$. We assume that $|\hat{S}| \ge k$, and we condition on $S^{(k)}$ and $\mathcal{Y}$, the set containing the $k$ first arms that were added to $\hat{S}$. Let $u$ such that $|S_u| = k$. Thanks to the second point of Lemma C.9, it holds that

$$ \{a_u \text{ is good}\} \cap \mathcal{Y} \cap (\cap_{s \in [s_0, r]} \mathcal{Z}_{u,s}^c) \subset \cap_{s \in [s_0, r]} \{\phi_s^u = 0\} = \{a_u \text{ is added to } S\} . $$

Then, the events $\{a_u \text{ is good}\}$, $\mathcal{Y}$ and $\cap_{s \in [r]} \mathcal{Z}_{u,s}^c$ are independent. Moreover, $\mathbb{P}_{\nu}(a_u \text{ is good}) \ge (K-k)\theta_* \ge (K-k)\theta$ because it remains at least $(K-k)$ groups not represented in $S^{(k)}$ and all these groups have a proportion larger than $\theta_*$. We also have thanks to Lemma C.8 and Lemma C.9, $\mathbb{P}_{\nu}(\mathcal{Y}) \ge 1 - \delta/4$ and $\mathbb{P}_{\nu}(\cap_{s \in [r]} \mathcal{Z}_{u,s}^c) \ge 1/2$.

Conditionally on $S_u = S^{(k)}$, and on the estimated centers of the representatives in $S^{(k)}$, the event $\{a_u \text{ is added to } S\}$ are independent and of probability larger than $(1 - \delta/4)(K-k)\theta/2$. Then, $M_k$ is stochastically dominated by a geometric random variable of parameter $(K-k)\theta/4$. Finally, $\mathbb{E}_{\nu}[M_k 1_y] \le \frac{4}{(K-k)\theta}$ and

$$ \mathbb{E}_{\nu}[(M-1)1_y] = \sum_{k=1}^{K-1} \mathbb{E}_{\nu}[M_k 1_y] \le \sum_{k=1}^{K-1} \frac{4}{(K-k)\theta} = \frac{4}{\theta} \sum_{k=1}^{K-1} \frac{1}{k} \le \frac{4}{\theta}(1+\log(K)) . \quad (41) $$

Now, eq. (40) becomes

$$ \sum_{s=s_0+1}^{r} 2n_s \mathbb{E}_{\nu} [H_{s,M} 1_y] \le \sum_{s=s_0+1}^{r} 2n_s \left[ \frac{4}{\theta} (1 + \log(K)) \exp(-2^{s-4}) \right] . $$

We bound the previous expression, using the same computation as Lemma C.14, and we state the bound as a lemma proved later.

**Lemma C.15.** Using the explicit expression of $r$, $U$, $n_s$, $n_{max}$ and $s_0$ from Remark C.4, we have

$$ \sum_{s=s_0}^{r} n_s \left[ \frac{4}{\theta} \cdot \frac{1 + \log(K)}{\exp(2^{s-4})} \right] \le c \frac{\sigma^2 \log(K)}{\Delta^2 \theta} \left[ \log(K) + \sqrt{d} \right], $$

where $c$ is a universal constant.

We come back to eq. (38), using eqs. (40) and (41), we have

$$ \mathbb{E}_{\nu}[\tau_{SRI}] \le T_{\max}\delta + 2K \left( n_{\max} + \sum_{s=s_0+1}^{r} n_s \right) \\ + \frac{8n_{s_0}}{\theta}(1 + \log(K)) + \sum_{s=s_0+1}^{r} 2n_s \left[ \frac{4}{\theta}(1 + \log(K)) \exp(-2^{s-4}) \right] . $$

Now, if we define $A' = \frac{\sigma^2}{\Delta^2} \left[ \frac{\log(K)}{\theta} \log(1/(\theta\delta)) + \frac{\log(K)}{\theta} \sqrt{d} + \sqrt{dK \frac{\log(K)}{\theta} \log(K/\delta)} \right]$, Lemma C.13 and Lemma C.15 implies that we can choose $c$ large enough (and universal) such that

$$ \sum_{s=s_0+1}^{r} 2n_s \left[ \frac{4}{\theta}(1 + \log(K)) \exp(-2^{s-4}) \right] + 2K \left( n_{\max} + \sum_{s=s_0+1}^{r} n_s \right) \le 2K + cA' . $$
By definition of $n_{s_0}$, we can also see that

$$ \frac{8n_{s_0}}{\theta}(1 + \log(K)) \le 16 \frac{\log(K)}{\theta} + cA' . $$

Finally, it follows from (37) and $\delta \log(1/\delta) \le 1$ that

$$ T_{\max} \delta \le c' \frac{\log(K)}{\theta} + cA' . $$

In summary, we have the desired bound in expectation,

$$ \mathbb{E}_{\nu}[\tau_{SRI}] \le c' \frac{\log(K)}{\theta} + c \frac{\sigma^2}{\Delta^2} \left[ \frac{\log(K)}{\theta} \log(1/(\theta\delta)) + \frac{\log(K)}{\theta} \sqrt{d} + \frac{\log^2(K)}{\theta} \right] . $$

### C.3 Proofs of technical lemmas

**Proof of Lemma C.8.** We want to prove that $\mathbb{P}_{\nu}(\mathcal{Y}^c) \le \delta/4$, where $\mathcal{Y}^c$ is equal to

$$ \mathcal{Y}^c = \left\{ \begin{array}{l} \exists a \in \hat{S}, \exists k \in [K] \setminus \{k(a)\}, \left| \left\langle \frac{\epsilon_a + \epsilon'_a}{\sqrt{2}}, \frac{\mu_a - \mu(k)}{\|\mu_a - \mu(k)\|} \right\rangle \right| > \frac{1}{16} \sqrt{\frac{\Delta^2}{2\sigma^2}} \sqrt{n_{\max}} \\ \cup \left\{ \exists a \in \hat{S}, |\langle \epsilon_a, \epsilon'_a \rangle| > \frac{1}{16} \frac{\Delta^2}{\sigma^2} n_{\max} \right\} \\ \cup \left\{ \exists a \in \hat{S}, \|\epsilon'_a\|^2 \vee \|\epsilon_a\|^2 - \mathbb{E}[\|\epsilon_a\|^2] > c_{HW} \log(12K/\delta) \vee \sqrt{c_{HW} d \log(12K/\delta)} \right\} . \end{array} \right. $$

From the definition of $n_s$ and $n_{\max}$ as given in (10), (11), it holds that $n_{\max} \ge n_r$, with

$$ n_s \ge 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))} . $$

With the definition of $r$ in (9), we have also $2^r \ge \log(4U/\delta)$ and $U \ge 8K \log(K/\delta)$. We prove that, for $c_1 = 32^2 \vee 8c_{HW}$ and $c_2 = 16\sqrt{c_{HW}/2} \vee c_3$, then $n_{\max}$ is large enough to ensure Lemma C.8 (the value of $c_3$ will be useful later).

We start with a union bound on $\hat{S} \times [K]$, where $|\hat{S}| \le K$. We have

$$ \mathbb{P}_{\nu} \left( \exists a \in \hat{S}, \exists k \in [K] \setminus \{k(a)\}, \left| \left\langle \frac{\epsilon_a + \epsilon'_a}{\sqrt{2}}, \frac{\mu_a - \mu(k)}{\|\mu_a - \mu(k)\|} \right\rangle \right| > \sqrt{\frac{n_{\max} \Delta^2}{2 \cdot 16^2 \sigma^2}} \right) \\ \le K^2 \mathbb{P}_{\nu} \left( \left| \left\langle \frac{\epsilon_a + \epsilon'_a}{\sqrt{2}}, \frac{\mu_a - \mu(k)}{\|\mu_a - \mu(k)\|} \right\rangle \right| > \sqrt{\frac{n_{\max} \Delta^2}{2 \cdot 16^2 \sigma^2}} \right) . $$

From the assumption on the noise (Assumption 2.1), it is easy to see that $\left\langle \frac{\epsilon_a + \epsilon'_a}{\sqrt{2}}, \frac{\mu_a - \mu(k)}{\|\mu_a - \mu(k)\|} \right\rangle$ is 1-subGaussian, proceeding as in the same proof of corollary E.4. With the standard concentration inequality lemma E.1 for subGaussian variables, we have

$$ \mathbb{P}_{\nu} \left( \left| \left\langle \frac{\epsilon_a + \epsilon'_a}{\sqrt{2}}, \frac{\mu_a - \mu(k)}{\|\mu_a - \mu(k)\|} \right\rangle \right| > \sqrt{\frac{n_{\max} \Delta^2}{2 \cdot 16^2 \sigma^2}} \right) \le 2 \exp \left( - \frac{n_{\max} \Delta^2}{(32\sigma)^2} \right) , $$

Now, $c_1 \ge 32^2$ and $2^r \ge \log(4K/\delta)$ so that $n_{\max} \ge c_1 \frac{\sigma^2}{\Delta^2}(2^r + \log(12K)) \ge 32^2 \frac{\sigma^2}{\Delta^2} \log(\frac{48K^2}{\delta})$. Finally, with the union bound above, we have

$$ \mathbb{P}_{\nu} \left( \exists a \in \hat{S}, \exists k \in [K] \setminus \{k(a)\}, \left| \left\langle \frac{\epsilon_a + \epsilon'_a}{\sqrt{2}}, \frac{\mu_a - \mu(k)}{\|\mu_a - \mu(k)\|} \right\rangle \right| > \sqrt{\frac{n_{\max} \Delta^2}{2 \cdot 16^2 \sigma^2}} \right) \le \frac{\delta}{24} . \quad (42) $$
By definition of $n_{s_0}$, we can also see that

$$ \frac{8n_{s_0}}{\theta}(1 + \log(K)) \le 16 \frac{\log(K)}{\theta} + cA' . $$

Finally, it follows from (37) and $\delta \log(1/\delta) \le 1$ that

$$ T_{\max} \delta \le c' \frac{\log(K)}{\theta} + cA' . $$

In summary, we have the desired bound in expectation,

$$ \mathbb{E}_{\nu}[\tau_{SRI}] \le c' \frac{\log(K)}{\theta} + c \frac{\sigma^2}{\Delta^2} \left[ \frac{\log(K)}{\theta} \log(1/(\theta\delta)) + \frac{\log(K)}{\theta} \sqrt{d} + \frac{\log^2(K)}{\theta} \right] . $$

### C.3 Proofs of technical lemmas

**Proof of Lemma C.8.** We want to prove that $\mathbb{P}_{\nu}(\mathcal{Y}^c) \le \delta/4$, where $\mathcal{Y}^c$ is equal to

$$ \mathcal{Y}^c = \left\{ \begin{array}{l} \exists a \in \hat{S}, \exists k \in [K] \setminus \{k(a)\}, \left| \left\langle \frac{\epsilon_a + \epsilon'_a}{\sqrt{2}}, \frac{\mu_a - \mu(k)}{\|\mu_a - \mu(k)\|} \right\rangle \right| > \frac{1}{16} \sqrt{\frac{\Delta^2}{2\sigma^2}} \sqrt{n_{\max}} \\ \cup \left\{ \exists a \in \hat{S}, |\langle \epsilon_a, \epsilon'_a \rangle| > \frac{1}{16} \frac{\Delta^2}{\sigma^2} n_{\max} \right\} \\ \cup \left\{ \exists a \in \hat{S}, \|\epsilon'_a\|^2 \lor \|\epsilon_a\|^2 - \mathbb{E}[\|\epsilon_a\|^2] > c_{HW} \log(12K/\delta) \lor \sqrt{c_{HW} d \log(12K/\delta)} \right\} . \end{array} \right. $$

From the definition of $n_s$ and $n_{\max}$ as given in (10), (11), it holds that $n_{\max} \ge n_r$, with

$$ n_s \ge 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))} . $$

With the definition of $r$ in (9), we have also $2^r \ge \log(4U/\delta)$ and $U \ge 8K \log(K/\delta)$. We prove that, for $c_1 = 32^2 \lor 8c_{HW}$ and $c_2 = 16\sqrt{c_{HW}/2} \lor c_3$, then $n_{\max}$ is large enough to ensure Lemma C.8 (the value of $c_3$ will be useful later).

We start with a union bound on $\hat{S} \times [K]$, where $|\hat{S}| \le K$. We have

$$ \mathbb{P}_{\nu} \left( \exists a \in \hat{S}, \exists k \in [K] \setminus \{k(a)\}, \left| \left\langle \frac{\epsilon_a + \epsilon'_a}{\sqrt{2}}, \frac{\mu_a - \mu(k)}{\|\mu_a - \mu(k)\|} \right\rangle \right| > \sqrt{\frac{n_{\max} \Delta^2}{2 \cdot 16^2 \sigma^2}} \right) \\ \le K^2 \mathbb{P}_{\nu} \left( \left| \left\langle \frac{\epsilon_a + \epsilon'_a}{\sqrt{2}}, \frac{\mu_a - \mu(k)}{\|\mu_a - \mu(k)\|} \right\rangle \right| > \sqrt{\frac{n_{\max} \Delta^2}{2 \cdot 16^2 \sigma^2}} \right) . $$

From the assumption on the noise (Assumption 2.1), it is easy to see that $\left\langle \frac{\epsilon_a + \epsilon'_a}{\sqrt{2}}, \frac{\mu_a - \mu(k)}{\|\mu_a - \mu(k)\|} \right\rangle$ is 1-subGaussian, proceeding as in the same proof of corollary E.4. With the standard concentration inequality lemma E.1 for subGaussian variables, we have

$$ \mathbb{P}_{\nu} \left( \left| \left\langle \frac{\epsilon_a + \epsilon'_a}{\sqrt{2}}, \frac{\mu_a - \mu(k)}{\|\mu_a - \mu(k)\|} \right\rangle \right| > \sqrt{\frac{n_{\max} \Delta^2}{2 \cdot 16^2 \sigma^2}} \right) \le 2 \exp \left( - \frac{n_{\max} \Delta^2}{(32\sigma)^2} \right) , $$

Now, $c_1 \ge 32^2$ and $2^r \ge \log(4K/\delta)$ so that $n_{\max} \ge c_1 \frac{\sigma^2}{\Delta^2}(2^r + \log(12K)) \ge 32^2 \frac{\sigma^2}{\Delta^2} \log(\frac{48K^2}{\delta})$. Finally, with the union bound above, we have

$$ \mathbb{P}_{\nu} \left( \exists a \in \hat{S}, \exists k \in [K] \setminus \{k(a)\}, \left| \left\langle \frac{\epsilon_a + \epsilon'_a}{\sqrt{2}}, \frac{\mu_a - \mu(k)}{\|\mu_a - \mu(k)\|} \right\rangle \right| > \sqrt{\frac{n_{\max} \Delta^2}{2 \cdot 16^2 \sigma^2}} \right) \le \frac{\delta}{24} . \quad (42) $$
Now, as proved in Corollary E.4, Hanson Wright inequality imply a bound for $\langle \epsilon_a, \epsilon'_a \rangle$ and then with the constant $c_{HW}$ from Lemma E.3, we have:

$$ \mathbb{P}_{\nu} \left( \exists a \in \hat{S}, \left| \langle \epsilon_a, \epsilon'_a \rangle \right| > \frac{\Delta^2 n_{\max}}{16\sigma^2} \right) \le 2K \exp \left( -\frac{2}{c_{HW}} \left( \frac{\Delta^2 n_{\max}}{16\sigma^2} \wedge \frac{\Delta^4 n_{\max}^2}{16^2 \sigma^4 d} \right) \right) \le \frac{\delta}{24}, \quad (43) $$

because the definition of $c_1$, $c_2$ and $r$, implies that

$$ n_{\max} \ge 8c_{HW} \frac{\sigma^2}{\Delta^2} \log \left( \frac{48K}{\delta} \right) \vee 16 \sqrt{\frac{c_{HW}}{2}} \frac{\sigma^2}{\Delta^2} \sqrt{d \log \left( \frac{48K}{\delta} \right)} . $$

Finally, a direct application of Hanson-Wright inequality (Lemma E.3) ensures that

$$ \begin{aligned} \mathbb{P}_{\nu} \left( \exists a \in \hat{S}, \|\epsilon'_a\|^2 \vee \|\epsilon_a\|^2 - \mathbb{E}[\|\epsilon_a\|^2] \ge c_{HW} \log(12K/\delta) \vee \sqrt{c_{HW} d \log(12K/\delta)} \right) \\ \le 2K \exp(-\log(12K/\delta)) \le \frac{\delta}{6}, \end{aligned} \quad (44) $$

This concludes the proof of Lemma C.8, using a union bound and inequalities (42) to (44). □

**Proof of Lemma C.9.** We recall that in this lemma, $\nu$ is an environment with minimal gap $\Delta_*$ and balancedness $\theta_*$, and $\nu$ is not necessary in $\mathcal{E}(\Delta, \theta, \sigma, N, K, d)$. Let $u \ge 1$ and $s \in [s_0, r]$.

The first point of the lemma is a direct consequence of the expression of $\mathcal{Z}_{u,s}$ and the mutual independence of the series of empirical means $(\bar{\mu}_{u,s}, \bar{\mu}'_{u,s})$.

**Second point of Lemma C.9**

We assume that $a_u$ is a good arm rejected by the test $(u, s)$, which by definition of the test statistic means that for all $a \in S_u$, then $|\mu_{a_u} - \mu_a| \ge \Delta$, while the test statistic $\phi_s^u$ is equal to 1. It implies that there exists $a \in S_u$ such that

$$ \langle \bar{\mu}_{u,s} - \hat{\mu}_a, \bar{\mu}'_{u,s} - \hat{\mu}'_a \rangle \le \frac{\Delta^2}{2} . $$

From the decomposition of 27, and conditionally on the event $\mathcal{Y}$ 28, we have:

$$ \begin{aligned} \frac{\Delta^2}{2} \ge & \|\mu_{a_u} - \mu_a\|^2 - \frac{\Delta}{16} \|\mu_{a_u} - \mu_a\| - \frac{\Delta^2}{16} \\ & - \frac{\sigma^2}{\sqrt{n_{\max} n_s}} \langle \epsilon_{u,s}, \rho'_a \rangle \|\epsilon'_a\| - \frac{\sigma^2}{\sqrt{n_{\max} n_s}} \langle \epsilon'_{u,s}, \rho_a \rangle \|\epsilon_a\| \end{aligned} \quad (45) $$

$$ + \frac{\sqrt{2}\sigma}{\sqrt{n_s}} \left\langle \frac{\epsilon_{u,s} + \epsilon'_{u,s}}{\sqrt{2}}, \mu_{a_u} - \mu_a \right\rangle + \frac{\sigma^2}{n_s} \langle \epsilon_{u,s}, \epsilon'_{u,s} \rangle . \quad (46) $$

We also have on $\mathcal{Y}$, $\|\epsilon_a\|^2 \le \mathbb{E}[\|\epsilon_a\|^2] + c_{HW} l \vee \sqrt{c_{HW} d l}$ with $l := \log(\frac{12K}{\sigma})$, $\mathbb{E}[\|\epsilon_a\|^2] \le 4d$ is a direct consequence of the subGaussian assumption – see Lemma 1.4 from [30]. We have

$$ (45) \ge - \frac{\sigma^2}{\sqrt{n_{\max} n_s}} \left[ |\langle \epsilon'_{u,s}, \rho_a \rangle| + |\langle \epsilon_{u,s}, \rho'_a \rangle| \right] \sqrt{4d + c_{HW} l \vee \sqrt{c_{HW} d l}} . $$

We also have directly,

$$ (46) \ge - \sqrt{\frac{2\sigma^2 \|\mu_{a_u} - \mu_a\|^2}{n_s}} \left| \left\langle \frac{\epsilon_{u,s} + \epsilon'_{u,s}}{\sqrt{2}}, \frac{\mu_{a_u} - \mu_a}{\|\mu_{a_u} - \mu_a\|} \right\rangle \right| - \frac{\sigma^2}{n_s} \left| \langle \epsilon_{u,s}, \epsilon'_{u,s} \rangle \right| . $$

We recall that $\Delta \le \|\mu_{a_u} - \mu_a\|$, because $a_u$ is a good arm. Hence, we have $\|\mu_{a_u} - \mu_a\|^2 - \frac{\Delta^2}{16} \|\mu_{a_u} - \mu_a\| - \frac{\Delta^2}{16} - \frac{\Delta^2}{2} \ge \frac{3}{8} \|\mu_{a_u} - \mu_a\|^2 \ge \frac{3}{8} \Delta^2$.
Now, as proved in Corollary E.4, Hanson Wright inequality imply a bound for $\langle \epsilon_a, \epsilon'_a \rangle$ and then with the constant $c_{HW}$ from Lemma E.3, we have:

$$ \mathbb{P}_{\nu} \left( \exists a \in \hat{S}, \left| \langle \epsilon_a, \epsilon'_a \rangle \right| > \frac{\Delta^2 n_{\max}}{16\sigma^2} \right) \le 2K \exp \left( -\frac{2}{c_{HW}} \left( \frac{\Delta^2 n_{\max}}{16\sigma^2} \wedge \frac{\Delta^4 n_{\max}^2}{16^2 \sigma^4 d} \right) \right) \le \frac{\delta}{24}, \quad (43) $$

because the definition of $c_1$, $c_2$ and $r$, implies that

$$ n_{\max} \ge 8c_{HW} \frac{\sigma^2}{\Delta^2} \log \left( \frac{48K}{\delta} \right) \vee 16 \sqrt{\frac{c_{HW}}{2}} \frac{\sigma^2}{\Delta^2} \sqrt{d \log \left( \frac{48K}{\delta} \right)} . $$

Finally, a direct application of Hanson-Wright inequality (Lemma E.3) ensures that

$$ \begin{aligned} & \mathbb{P}_{\nu} \left( \exists a \in \hat{S}, \|\epsilon'_a\|^2 \vee \|\epsilon_a\|^2 - \mathbb{E}[\|\epsilon_a\|^2] \ge c_{HW} \log(12K/\delta) \vee \sqrt{c_{HW} d \log(12K/\delta)} \right) \\ & \le 2K \exp(-\log(12K/\delta)) \le \frac{\delta}{6}, \end{aligned} \quad (44) $$

This concludes the proof of Lemma C.8, using a union bound and inequalities (42) to (44). $\square$

**Proof of Lemma C.9.** We recall that in this lemma, $\nu$ is an environment with minimal gap $\Delta_*$ and balancedness $\theta_*$, and $\nu$ is not necessary in $\mathcal{E}(\Delta, \theta, \sigma, N, K, d)$. Let $u \ge 1$ and $s \in [s_0, r]$.

The first point of the lemma is a direct consequence of the expression of $\mathcal{Z}_{u,s}$ and the mutual independence of the series of empirical means $(\bar{\mu}_{u,s}, \bar{\mu}'_{u,s})$.

**Second point of Lemma C.9**

We assume that $a_u$ is a good arm rejected by the test $(u, s)$, which by definition of the test statistic means that for all $a \in S_u$, then $|\mu_{a_u} - \mu_a| \ge \Delta$, while the test statistic $\phi_s^u$ is equal to 1. It implies that there exists $a \in S_u$ such that

$$ \langle \bar{\mu}_{u,s} - \hat{\mu}_a, \bar{\mu}'_{u,s} - \hat{\mu}'_a \rangle \le \frac{\Delta^2}{2} . $$

From the decomposition of 27, and conditionally on the event $\mathcal{Y}$ 28, we have:

$$ \begin{aligned} \frac{\Delta^2}{2} \ge & \|\mu_{a_u} - \mu_a\|^2 - \frac{\Delta}{16} \|\mu_{a_u} - \mu_a\| - \frac{\Delta^2}{16} \\ & - \frac{\sigma^2}{\sqrt{n_{\max} n_s}} \langle \epsilon_{u,s}, \rho'_a \rangle \|\epsilon'_a\| - \frac{\sigma^2}{\sqrt{n_{\max} n_s}} \langle \epsilon'_{u,s}, \rho_a \rangle \|\epsilon_a\| \end{aligned} \quad (45) $$

$$ + \frac{\sqrt{2}\sigma}{\sqrt{n_s}} \left\langle \frac{\epsilon_{u,s} + \epsilon'_{u,s}}{\sqrt{2}}, \mu_{a_u} - \mu_a \right\rangle + \frac{\sigma^2}{n_s} \langle \epsilon_{u,s}, \epsilon'_{u,s} \rangle . \quad (46) $$

We also have on $\mathcal{Y}$, $\|\epsilon_a\|^2 \le \mathbb{E}[\|\epsilon_a\|^2] + c_{HW} l \vee \sqrt{c_{HW} d l}$ with $l := \log(\frac{12K}{\sigma})$, $\mathbb{E}[\|\epsilon_a\|^2] \le 4d$ is a direct consequence of the subGaussian assumption – see Lemma 1.4 from [30]. We have

$$ (45) \ge -\frac{\sigma^2}{\sqrt{n_{\max} n_s}} \left[ |\langle \epsilon'_{u,s}, \rho_a \rangle| + |\langle \epsilon_{u,s}, \rho'_a \rangle| \right] \sqrt{4d + c_{HW} l \vee \sqrt{c_{HW} d l}} . $$

We also have directly,

$$ (46) \ge -\sqrt{\frac{2\sigma^2 \|\mu_{a_u} - \mu_a\|^2}{n_s}} \left| \left\langle \frac{\epsilon_{u,s} + \epsilon'_{u,s}}{\sqrt{2}}, \frac{\mu_{a_u} - \mu_a}{\|\mu_{a_u} - \mu_a\|} \right\rangle \right| - \frac{\sigma^2}{n_s} \left| \langle \epsilon_{u,s}, \epsilon'_{u,s} \rangle \right| . $$

We recall that $\Delta \le \|\mu_{a_u} - \mu_a\|$, because $a_u$ is a good arm. Hence, we have $\|\mu_{a_u} - \mu_a\|^2 - \frac{\Delta}{16} \|\mu_{a_u} - \mu_a\| - \frac{\Delta^2}{16} - \frac{\Delta^2}{2} \ge \frac{3}{8} \|\mu_{a_u} - \mu_a\|^2 \ge \frac{3}{8} \Delta^2$.
From there, we state that if $a_u$ is good and $\phi_s^u = 1$ then there exists $a \in \hat{S}$ such that at least one of the these three inequalities holds:

$$ \begin{aligned} & |\langle \epsilon_{u,s}, \rho'_a \rangle| + |\langle \epsilon'_{u,s}, \rho_a \rangle| \ge \frac{1}{4} \frac{\Delta^2}{\sigma^2} \sqrt{\frac{n_s n_{\max}}{4d + \sqrt{c_{HW} dl} \lor c_{HW} l}}, \\ & |\langle \epsilon_{u,s}, \epsilon'_{u,s} \rangle| \ge \frac{1}{16} \frac{\Delta^2}{\sigma^2} n_s, \\ & \left| \left\langle \frac{\epsilon_{u,s} + \epsilon'_{u,s}}{\sqrt{2}}, \frac{\mu_{a_u} - \mu_a}{\|\mu_{a_u} - \mu_a\|} \right\rangle \right| \ge \frac{1}{16} \frac{\Delta}{\sigma} \sqrt{\frac{n_s}{2}}. \end{aligned} $$

By definition, $\mathcal{Z}_{u,s}$ is the event where one of these three inequalities hold for some $a \in \hat{S}$, so the inclusion $\mathcal{Y} \cap \{a_u \text{ is good and } \phi_s^u = 1\} \subset \mathcal{Z}_{u,s}$ is proved.

### Third point of Lemma C.9

We now assume that $a_u$ is bad, but the s-th test accept $a_u$, i.e., $\phi_s^u = 0$. As $a_u$ is bad, there exists $a \in S_u$ such that $\|\mu_{a_u} - \mu_a\| \le \Delta/4$. As $\phi_s^u = 0$, for this specific arm $a$, we have: $\langle \bar{\mu}_{u,s} - \hat{\mu}_a, \bar{\mu}'_{u,s} - \hat{\mu}'_a \rangle > \frac{\Delta^2}{2}$.

Assume that $0 < \|\mu_{a_u} - \mu_a\| \le \Delta/4$, with the same computation as in the first case, we have

$$ \begin{aligned} \frac{\Delta^2}{2} &\le \|\mu_{a_u} - \mu_a\|^2 + \frac{\Delta}{16} \|\mu_{a_u} - \mu_a\| + \frac{\Delta^2}{16} \\ &\quad + \frac{\sigma^2}{\sqrt{n_{\max} n_s}} \sqrt{4d + c_{HW} l \lor \sqrt{c_{HW} dl}} (|\langle \epsilon_{u,s}, \rho'_a \rangle| + |\langle \epsilon'_{u,s}, \rho_a \rangle|) \\ &\quad + \sqrt{\frac{2\sigma^2 \|\mu_{a_u} - \mu_a\|^2}{n_s}} \left| \left\langle \frac{\epsilon_{u,s} + \epsilon'_{u,s}}{\sqrt{2}}, \frac{\mu_{a_u} - \mu_a}{\|\mu_{a_u} - \mu_a\|} \right\rangle \right| + \frac{\sigma^2}{n_s} |\langle \epsilon_{u,s}, \epsilon'_{u,s} \rangle| . \end{aligned} $$

In the last line, we upper bound $\|\mu_{a_u} - \mu_a\|$ by $\Delta/4$. Now, consider the constant terms, $\frac{\Delta^2}{2} - \|\mu_{a_u} - \mu_a\|^2 - \frac{\Delta}{16} \|\mu_{a_u} - \mu_a\| - \frac{\Delta^2}{16} \ge \frac{\Delta^2}{2} - \frac{\Delta^2}{16} - \frac{\Delta^2}{64} - \frac{\Delta^2}{16} \ge \Delta^2 (\frac{1}{4} + \frac{1}{16} + \frac{1}{4 \cdot 16})$. As above, we deduce that at least one of the three inequalities defining $\mathcal{Z}_{u,s}$ holds. If $\|\mu_{a_u} - \mu_a\| = 0$, there are simply fewer terms in the equality. This proves the inclusion $\mathcal{Y} \cap \{a_u \text{ is bad and } \phi_s^u = 0\} \subset \mathcal{Z}_{u,s}$.

### Probability of $\mathcal{Z}_{u,s}$

We prove now that the probability of $\mathcal{Z}_{u,s}$ decrease exponentially fast with $s$. Fix $s_0 \le s \le r$.

We recall the expression of $n_s$, and $n_{\max}$

$$ n_s \ge 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))}, $$

$$ \text{where } c_1 = 32^2 \lor 8c_{HW}, c_2 = 16\sqrt{c_{HW}/2} \lor 32\sqrt{2}, c_3 = 32\sqrt{2}, \text{ and } n_{\max} \ge n_r \lor c_3 \frac{\sigma^2}{\Delta^2} \sqrt{d \log(2K)}. $$

Let $k \in [K]$ such that $\mu_{a_u} \ne \mu(k)$, as a consequence of assumption 2.1, the one-dimensional variable $\left\langle \frac{\epsilon_{u,s} + \epsilon'_{u,s}}{\sqrt{2}}, \frac{\mu_{a_u} - \mu(k)}{\|\mu_{a_u} - \mu(k)\|} \right\rangle$ is 1-subGaussian. With standard concentration of subGaussian variables (Lemma E.1), we have

$$ \mathbb{P}_v \left( \left| \left\langle \frac{\epsilon_{u,s} + \epsilon'_{u,s}}{\sqrt{2}}, \frac{\mu_{a_u} - \mu(k)}{\|\mu_{a_u} - \mu(k)\|} \right\rangle \right| \ge \frac{1}{16} \frac{\Delta}{\sigma} \sqrt{\frac{n_s}{2}} \right) \le 2 \exp \left( - \frac{\Delta^2}{\sigma^2} \frac{n_s}{32^2} \right) \le \frac{1}{3K} \exp(-2^s), $$

$$ \text{because } n_s \ge 32^2 \frac{\sigma^2}{\Delta^2} (2^s + \log(6K)). $$

Now, with a union bound over $k \in [K]$, it holds that

$$ \mathbb{P} \left( \exists k \in [K] \setminus \{k(a_u)\} ; \left| \left\langle \frac{\epsilon_{u,s} + \epsilon'_{u,s}}{\sqrt{2}}, \frac{\mu_{a_u} - \mu(k)}{\|\mu_{a_u} - \mu(k)\|} \right\rangle \right| \ge \frac{1}{16} \frac{\Delta}{\sigma} \sqrt{\frac{n_s}{2}} \right) \le \frac{1}{3} \exp(-2^s), \quad (47) $$
From there, we state that if $a_u$ is good and $\phi_s^u = 1$ then there exists $a \in \hat{S}$ such that at least one of the these three inequalities holds:

$$ \begin{aligned} & |\langle \epsilon_{u,s}, \rho'_a \rangle| + |\langle \epsilon'_{u,s}, \rho_a \rangle| \ge \frac{1}{4} \frac{\Delta^2}{\sigma^2} \sqrt{\frac{n_s n_{\max}}{4d + \sqrt{c_{HW} dl} \lor c_{HW} l}}, \\ & |\langle \epsilon_{u,s}, \epsilon'_{u,s} \rangle| \ge \frac{1}{16} \frac{\Delta^2}{\sigma^2} n_s, \\ & \left| \left\langle \frac{\epsilon_{u,s} + \epsilon'_{u,s}}{\sqrt{2}}, \frac{\mu_{a_u} - \mu_a}{\|\mu_{a_u} - \mu_a\|} \right\rangle \right| \ge \frac{1}{16} \frac{\Delta}{\sigma} \sqrt{\frac{n_s}{2}}. \end{aligned} $$

By definition, $\mathcal{Z}_{u,s}$ is the event where one of these three inequalities hold for some $a \in \hat{S}$, so the inclusion $\mathcal{Y} \cap \{a_u \text{ is good and } \phi_s^u = 1\} \subset \mathcal{Z}_{u,s}$ is proved.

**Third point of Lemma C.9**

We now assume that $a_u$ is bad, but the s-th test accept $a_u$, i.e., $\phi_s^u = 0$. As $a_u$ is bad, there exists $a \in S_u$ such that $\|\mu_{a_u} - \mu_a\| \le \Delta/4$. As $\phi_s^u = 0$, for this specific arm $a$, we have: $\langle \bar{\mu}_{u,s} - \hat{\mu}_a, \bar{\mu}'_{u,s} - \hat{\mu}'_a \rangle > \frac{\Delta^2}{2}$.

Assume that $0 < \|\mu_{a_u} - \mu_a\| \le \Delta/4$, with the same computation as in the first case, we have

$$ \begin{aligned} \frac{\Delta^2}{2} &\le \|\mu_{a_u} - \mu_a\|^2 + \frac{\Delta}{16} \|\mu_{a_u} - \mu_a\| + \frac{\Delta^2}{16} \\ &\quad + \frac{\sigma^2}{\sqrt{n_{\max} n_s}} \sqrt{4d + c_{HW} l \lor \sqrt{c_{HW} dl}} (|\langle \epsilon_{u,s}, \rho'_a \rangle| + |\langle \epsilon'_{u,s}, \rho_a \rangle|) \\ &\quad + \sqrt{\frac{2\sigma^2 \|\mu_{a_u} - \mu_a\|^2}{n_s}} \left| \left\langle \frac{\epsilon_{u,s} + \epsilon'_{u,s}}{\sqrt{2}}, \frac{\mu_{a_u} - \mu_a}{\|\mu_{a_u} - \mu_a\|} \right\rangle \right| + \frac{\sigma^2}{n_s} |\langle \epsilon_{u,s}, \epsilon'_{u,s} \rangle|. \end{aligned} $$

In the last line, we upper bound $\|\mu_{a_u} - \mu_a\|$ by $\Delta/4$. Now, consider the constant terms, $\frac{\Delta^2}{2} - \|\mu_{a_u} - \mu_a\|^2 - \frac{\Delta}{16} \|\mu_{a_u} - \mu_a\| - \frac{\Delta^2}{16} \ge \frac{\Delta^2}{2} - \frac{\Delta^2}{16} - \frac{\Delta^2}{64} - \frac{\Delta^2}{16} \ge \Delta^2 (\frac{1}{4} + \frac{1}{16} + \frac{1}{4 \cdot 16})$. As above, we deduce that at least one of the three inequalities defining $\mathcal{Z}_{u,s}$ holds. If $\|\mu_{a_u} - \mu_a\| = 0$, there are simply fewer terms in the equality. This proves the inclusion $\mathcal{Y} \cap \{a_u \text{ is bad and } \phi_s^u = 0\} \subset \mathcal{Z}_{u,s}$.

**Probability of $\mathcal{Z}_{u,s}$**

We prove now that the probability of $\mathcal{Z}_{u,s}$ decrease exponentially fast with $s$. Fix $s_0 \le s \le r$.

We recall the expression of $n_s$, and $n_{\max}$

$$ n_s \ge 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))}, $$

where $c_1 = 32^2 \lor 8c_{HW}$, $c_2 = 16\sqrt{c_{HW}/2} \lor 32\sqrt{2}$, $c_3 = 32\sqrt{2}$, and $n_{\max} \ge n_r \lor c_3 \frac{\sigma^2}{\Delta^2} \sqrt{d \log(2K)}$.

Let $k \in [K]$ such that $\mu_{a_u} \ne \mu(k)$, as a consequence of assumption 2.1, the one-dimensional variable $\left\langle \frac{\epsilon_{u,s} + \epsilon'_{u,s}}{\sqrt{2}}, \frac{\mu_{a_u} - \mu(k)}{\|\mu_{a_u} - \mu(k)\|} \right\rangle$ is 1-subGaussian. With standard concentration of subGaussian variables (Lemma E.1), we have

$$ \mathbb{P}_{\nu} \left( \left| \left\langle \frac{\epsilon_{u,s} + \epsilon'_{u,s}}{\sqrt{2}}, \frac{\mu_{a_u} - \mu(k)}{\|\mu_{a_u} - \mu(k)\|} \right\rangle \right| \ge \frac{1}{16} \frac{\Delta}{\sigma} \sqrt{\frac{n_s}{2}} \right) \le 2 \exp \left( -\frac{\Delta^2}{\sigma^2} \frac{n_s}{32^2} \right) \le \frac{1}{3K} \exp(-2^s), $$

because $n_s \ge 32^2 \frac{\sigma^2}{\Delta^2}(2^s + \log(6K))$.

Now, with a union bound over $k \in [K]$, it holds that

$$ \mathbb{P} \left( \exists k \in [K] \setminus \{k(a_u)\} ; \left| \left\langle \frac{\epsilon_{u,s} + \epsilon'_{u,s}}{\sqrt{2}}, \frac{\mu_{a_u} - \mu(k)}{\|\mu_{a_u} - \mu(k)\|} \right\rangle \right| \ge \frac{1}{16} \frac{\Delta}{\sigma} \sqrt{\frac{n_s}{2}} \right) \le \frac{1}{3} \exp(-2^s), \quad (47) $$
Then, $\langle \epsilon_{u,s}, \epsilon'_{u,s} \rangle$ is the inner product of two independent vectors, for which the assumptions from Corollary E.4 holds. We use this corollary of Hanson-Wright inequality, and obtain

$$ \mathbb{P}_{\nu} \left( \left| \langle \epsilon_{u,s}, \epsilon'_{u,s} \rangle \right| \ge \frac{\Delta^2 n_s}{\sigma^2 16} \right) \le 2 \exp \left( -\frac{2}{c_{HW}} \left( \frac{\Delta^2 n_s}{\sigma^2 16} \wedge \frac{1}{d} \frac{\Delta^4}{\sigma^4} \frac{n_s^2}{16^2} \right) \right) \le \frac{1}{3} \exp(-2^s), \quad (48) $$

where the last inequality follows from the definition of $n_s$ (and $c_1, c_2$) where $n_s \ge 8c_{HW} \frac{\sigma^2}{\Delta^2}(2^s + \log(6)) \vee 16\sqrt{\frac{c_{HW}}{2}} \frac{\sigma^2}{\Delta^2} \sqrt{d(2^s + \log(6))}$.

Finally, we want to upper bound the probability that the cross term between $\epsilon_a$ and $\epsilon_{u,s}$ is too large. By conditioning with respect to the random variables $(\rho_a, \rho'_a)_a$, we consider these variables as constants. We start with a union bound and the inequality $a + b \le 2a \vee b$.

$$ \begin{aligned} & \mathbb{P}_{\nu} \left( \exists a \in \hat{S}; \left| \langle \epsilon_{u,s}, \rho'_{a} \rangle \right| + \left| \langle \epsilon'_{u,s}, \rho_a \rangle \right| \ge \frac{1}{4} \frac{\Delta^2}{\sigma^2} \sqrt{\frac{n_s n_{\max}}{4d + \sqrt{c_{HW} dl \vee c_{HW} l}}} \right) \\ & \le 2K \mathbb{P}_{\nu} \left( \left| \langle \epsilon_{u,s}, \rho \rangle \right| \ge \frac{1}{8} \frac{\Delta^2}{\sigma^2} \sqrt{\frac{n_s n_{\max}}{4d + \sqrt{c_{HW} dl \vee c_{HW} l}}} \right), \end{aligned} $$

with $\rho$ of norm 1. Then $\langle \epsilon_{u,s}, \rho \rangle$ is a 1-dimensional subGaussian random variable. We use therefore the concentration inequality in Lemma E.1, and we state that

$$ \begin{aligned} & \mathbb{P}_{\nu} \left( \exists a \in \hat{S}; \left| \langle \epsilon_{u,s}, \rho'_{a} \rangle \right| + \left| \langle \epsilon'_{u,s}, \rho_a \rangle \right| \ge \frac{1}{4} \frac{\Delta^2}{\sigma^2} \sqrt{\frac{n_s n_{\max}}{4d + \sqrt{c_{HW} dl \vee c_{HW} l}}} \right) \\ & \le 4K \exp \left( -\frac{1}{2 \cdot 8^2} \frac{\Delta^4}{\sigma^4} \frac{n_s n_{\max}}{4d + \sqrt{c_{HW} dl \vee c_{HW} l}} \right) \\ & \le 4K \exp \left( -\frac{1}{16^2} \frac{\Delta^4}{\sigma^4} \frac{n_s n_{\max}}{4d + \sqrt{c_{HW} dl \vee c_{HW} l}} \right), \end{aligned} $$

in the last line, we use again the inequality $a + b \le 2a \vee b$.

Now, we need to bound this last expression by $\frac{1}{3} \exp(-2^s)$ by using the definition of $n_s$ and $n_{\max}$ We recall that $l = \log(12K/\delta) \le 2^r$.

Now, with our choice for $c_1$ and $c_2$, it holds that $n_s \ge 32^2 \frac{\sigma^2}{\delta^2}(2^s + \log(12K))$ and $n_{\max} \ge c_{HW} l \vee \sqrt{c_{HW} dl}$, so that

$$ n_s n_{\max} \ge 16^2 \frac{\sigma^4}{\Delta^2} (\sqrt{c_{HW} dl \vee c_{HW} l})(2^s + \log(12K)). $$

We finally use the assumption that $c_2 \ge 32\sqrt{2}$ and $c_3 = 32\sqrt{2}$, so that $n_s \ge 16\sqrt{2} \frac{\sigma^2}{\Delta^2} \sqrt{(4d)(2^s + \log(6))}$, $n_{\max} \ge 16\sqrt{2} \frac{\sigma^2}{\Delta^2} \sqrt{4d\sqrt{2^s + \log(6)}}$ and $n_{\max} \ge 16\sqrt{2} \frac{\sigma^2}{\Delta^2} \sqrt{4d\log(2K)}$. Then, with the inequality $a \vee b \ge (a+b)/2$, we have

$$ n_s n_{\max} \ge 16^2 \frac{\sigma^4}{\Delta^2} (4d)(2^s + \log(12K)). $$

We combine these lower bound on $n_s n_{\max}$ to deduce that

$$ n_s n_{\max} \ge 16^2 \frac{\sigma^4}{\Delta^2} (4d \vee \sqrt{c_{HW} dl \vee c_{HW} l})(2^s + \log(12K)). $$

This allows us to conclude that

$$ \begin{aligned} & \mathbb{P}_{\nu} \left( \exists a \in \hat{S}; \left| \langle \epsilon_{u,s}, \rho'_{a} \rangle \right| + \left| \langle \epsilon'_{u,s}, \rho_a \rangle \right| \ge \frac{1}{4} \frac{\Delta^2}{\sigma^2} \sqrt{\frac{n_s n_{\max}}{4d + \sqrt{c_{HW} dl \vee c_{HW} l}}} \right) \\ & \le 4K \exp \left( -\frac{1}{16^2} \frac{\Delta^4}{\sigma^4} \frac{n_s n_{\max}}{4d + \sqrt{c_{HW} dl \vee c_{HW} l}} \right) \le \frac{1}{3} \exp(-2^s) . \end{aligned} \quad (49) $$

We finish the proof with a union bound, gathering the inequalities (47) to (49),

$$ \mathbb{P}_{\nu}(Z_{u,s}) \le \frac{1}{3} \exp(-2^s) + \frac{1}{3} \exp(-2^s) + \frac{1}{3} \exp(-2^s) = \exp(-2^s). $$

□
Then, $\langle \epsilon_{u,s}, \epsilon'_{u,s} \rangle$ is the inner product of two independent vectors, for which the assumptions from Corollary E.4 holds. We use this corollary of Hanson-Wright inequality, and obtain

$$ \mathbb{P}_{\nu} \left( \left| \langle \epsilon_{u,s}, \epsilon'_{u,s} \rangle \right| \ge \frac{\Delta^2 n_s}{\sigma^2 16} \right) \le 2 \exp \left( -\frac{2}{c_{HW}} \left( \frac{\Delta^2 n_s}{\sigma^2 16} \wedge \frac{1}{d} \frac{\Delta^4 n_s^2}{\sigma^4 16^2} \right) \right) \le \frac{1}{3} \exp(-2^s), \quad (48) $$

where the last inequality follows from the definition of $n_s$ (and $c_1, c_2$) where $n_s \ge 8c_{HW} \frac{\sigma^2}{\Delta^2}(2^s + \log(6)) \vee 16\sqrt{\frac{c_{HW}}{2}} \frac{\sigma^2}{\Delta^2} \sqrt{d(2^s + \log(6))}$.

Finally, we want to upper bound the probability that the cross term between $\epsilon_a$ and $\epsilon_{u,s}$ is too large. By conditioning with respect to the random variables $(\rho_a, \rho'_a)_a$, we consider these variables as constants. We start with a union bound and the inequality $a + b \le 2a \vee b$.

$$ \begin{aligned} & \mathbb{P}_{\nu} \left( \exists a \in \hat{S}; \left| \langle \epsilon_{u,s}, \rho'_{a} \rangle \right| + \left| \langle \epsilon'_{u,s}, \rho_a \rangle \right| \ge \frac{1}{4} \frac{\Delta^2}{\sigma^2} \sqrt{\frac{n_s n_{\max}}{4d + \sqrt{c_{HW} dl \vee c_{HW} l}}} \right) \\ & \le 2K \mathbb{P}_{\nu} \left( \left| \langle \epsilon_{u,s}, \rho \rangle \right| \ge \frac{1}{8} \frac{\Delta^2}{\sigma^2} \sqrt{\frac{n_s n_{\max}}{4d + \sqrt{c_{HW} dl \vee c_{HW} l}}} \right), \end{aligned} $$

with $\rho$ of norm 1. Then $\langle \epsilon_{u,s}, \rho \rangle$ is a 1-dimensional subGaussian random variable. We use therefore the concentration inequality in Lemma E.1, and we state that

$$ \begin{aligned} & \mathbb{P}_{\nu} \left( \exists a \in \hat{S}; \left| \langle \epsilon_{u,s}, \rho'_{a} \rangle \right| + \left| \langle \epsilon'_{u,s}, \rho_a \rangle \right| \ge \frac{1}{4} \frac{\Delta^2}{\sigma^2} \sqrt{\frac{n_s n_{\max}}{4d + \sqrt{c_{HW} dl \vee c_{HW} l}}} \right) \\ & \le 4K \exp \left( -\frac{1}{2 \cdot 8^2} \frac{\Delta^4}{\sigma^4} \frac{n_s n_{\max}}{4d + \sqrt{c_{HW} dl \vee c_{HW} l}} \right) \\ & \le 4K \exp \left( -\frac{1}{16^2} \frac{\Delta^4}{\sigma^4} \frac{n_s n_{\max}}{4d + \sqrt{c_{HW} dl \vee c_{HW} l}} \right), \end{aligned} $$

in the last line, we use again the inequality $a + b \le 2a \vee b$.

Now, we need to bound this last expression by $\frac{1}{3} \exp(-2^s)$ by using the definition of $n_s$ and $n_{\max}$ We recall that $l = \log(12K/\delta) \le 2^r$.

Now, with our choice for $c_1$ and $c_2$, it holds that $n_s \ge 32^2 \frac{\sigma^2}{\delta^2}(2^s + \log(12K))$ and $n_{\max} \ge c_{HW} l \vee \sqrt{c_{HW} dl}$, so that

$$ n_s n_{\max} \ge 16^2 \frac{\sigma^4}{\Delta^2} (\sqrt{c_{HW} dl \vee c_{HW} l})(2^s + \log(12K)). $$

We finally use the assumption that $c_2 \ge 32\sqrt{2}$ and $c_3 = 32\sqrt{2}$, so that $n_s \ge 16\sqrt{2} \frac{\sigma^2}{\Delta^2} \sqrt{(4d)(2^s + \log(6))}$, $n_{\max} \ge 16\sqrt{2} \frac{\sigma^2}{\Delta^2} \sqrt{4d\sqrt{2^s + \log(6)}}$ and $n_{\max} \ge 16\sqrt{2} \frac{\sigma^2}{\Delta^2} \sqrt{4d\log(2K)}$. Then, with the inequality $a \vee b \ge (a+b)/2$, we have

$$ n_s n_{\max} \ge 16^2 \frac{\sigma^4}{\Delta^2} (4d)(2^s + \log(12K)). $$

We combine these lower bound on $n_s n_{\max}$ to deduce that

$$ n_s n_{\max} \ge 16^2 \frac{\sigma^4}{\Delta^2} (4d \vee \sqrt{c_{HW} dl \vee c_{HW} l})(2^s + \log(12K)). $$

This allows us to conclude that

$$ \begin{aligned} & \mathbb{P}_{\nu} \left( \exists a \in \hat{S}; \left| \langle \epsilon_{u,s}, \rho'_{a} \rangle \right| + \left| \langle \epsilon'_{u,s}, \rho_a \rangle \right| \ge \frac{1}{4} \frac{\Delta^2}{\sigma^2} \sqrt{\frac{n_s n_{\max}}{4d + \sqrt{c_{HW} dl \vee c_{HW} l}}} \right) \\ & \le 4K \exp \left( -\frac{1}{16^2} \frac{\Delta^4}{\sigma^4} \frac{n_s n_{\max}}{4d + \sqrt{c_{HW} dl \vee c_{HW} l}} \right) \le \frac{1}{3} \exp(-2^s). \end{aligned} \quad (49) $$

We finish the proof with a union bound, gathering the inequalities (47) to (49),

$$ \mathbb{P}_{\nu}(Z_{u,s}) \le \frac{1}{3} \exp(-2^s) + \frac{1}{3} \exp(-2^s) + \frac{1}{3} \exp(-2^s) = \exp(-2^s). \quad \square $$
**Proof of Lemma C.13.** Throughout the proofs of Lemmas C.13 to C.15, c is a universal constant changing from one line to another. Also, we use that, by the definition of $s_0$ and $n_s$, it turns out, that if $s > s_0$ then

$$n_s \le 2c_1 \frac{\sigma^2}{\Delta^2} (2^s + \log(12K)) \vee 2c_2 \frac{\sigma^2}{\Delta^2} \sqrt{d(2^s + \log(6))} . \quad (50)$$

We now bound $K (\sum_{s=s_0+1}^r n_s + n_{\max})$. Relying on the expression of $n_s$ above, and the sums $\sum_{s=1}^r 2^s \le 2^{r+1}$ and $\sum_{s=1}^r \sqrt{2^s} \le \sqrt{2}^{r+1}(1+\sqrt{2})$, we deduce that

$$K \sum_{s=s_0+1}^{r} n_s \le 2c_1 \frac{\sigma^2}{\Delta^2} K(2^{r+1} + \log(12K)r) \vee 2c_2 \frac{\sigma^2}{\Delta^2} K \sqrt{d} (\sqrt{2^r}(2+\sqrt{2}) + \sqrt{\log(6)}r) .$$

Now, from the expression of $r$ and $U$, we have $2^r \le 2 \log(4U/\delta) \le c \log(1/(\theta\delta))$. It leads to the bound

$$K \sum_{s=s_0+1}^{r} n_s \le c \frac{\sigma^2}{\Delta^2} \left[ K \log(1/(\theta\delta)) + K \log(K) \log \log(1/(\theta\delta)) + K \sqrt{d \log(1/(\theta\delta))} \right] .$$

As $1/\theta \ge K$, we have $K \log(\frac{1}{\theta}) \le \frac{1}{\theta} \log(K)$, so that we can bound the term above by

$$K \sum_{s=s_0+1}^{r} n_s \le c \frac{\sigma^2}{\Delta^2} \left[ \frac{1}{\theta} \log(K/\delta) + \sqrt{dK \frac{1}{\theta} \log(K/\delta)} \right] .$$

We also compute $n_{\max}$, we have $Kn_{\max} \le K + c \frac{\sigma^2}{\Delta^2} [Kn_r + K \log(K) \sqrt{d}]$, where $Kn_r$ is upper bounded by the same bound as $K \sum_{s=s_0+1}^r n_s$.

Finally, it implies that

$$K \sum_{s=s_0+1}^{r} n_s + Kn_{\max} \le K + c \frac{\sigma^2}{\Delta^2} \left[ \frac{\log(K)}{\theta} \log(K/\delta) + \sqrt{dK \frac{\log(K)}{\theta} \log(K/\delta)} \right] .$$

The second inequality in Lemma C.13 is clear, and the lemma is proved. $\square$

**Proof of Lemma C.14.** With the bound on $n_s$ for $s > s_0$ from eq. (50), we simplify the terms in $2^s$ and obtain,

$$\begin{align*}
\sum_{s=s_0+1}^{r} \frac{U}{2^{s-4}} n_s &\le 2c_1 \frac{16U\sigma^2}{\Delta^2} \sum_{s=s_0+1}^{r} \left(1 + \frac{1}{2^s} \log(12K)\right) \vee 2c_2 \frac{16U\sigma^2}{\Delta^2} \sum_{s=s_0+1}^{r} \left(\frac{1}{\sqrt{2}^s} \sqrt{d} + \frac{1}{2^s} \sqrt{d} \sqrt{\log(6)}\right) \\
&\le 2c_1 \frac{16U\sigma^2}{\Delta^2} (r + 2 \log(12K)) \vee 2c_2 \frac{16U\sigma^2}{\Delta^2} ((2+\sqrt{2})\sqrt{d} + 2\sqrt{\log(6)}\sqrt{d}) \\
&\le c \frac{\sigma^2}{\Delta^2} U \left[ \log \log \left(\frac{1}{\theta\delta}\right) + \log(K) + \sqrt{d} \right],
\end{align*}$$

because $\sum_{s \ge 1} 1/2^s \le 2$ and $\sum_{s \ge 1} 1/\sqrt{2}^s = 2 + \sqrt{2}$. We also use in the last inequality that $\log(U/\delta) \le 2 \log(8/\theta\delta)$, so that $r \le \log(2 \log(8/\theta\delta)) \le c \log \log(1/\theta\delta)$.

From the previous bound, we conclude that

$$\sum_{s=s_0+1}^{r} \frac{U}{2^{s-4}} n_s \le c \frac{\sigma^2}{\Delta^2} U \left[ \log \log \left( \frac{1}{\theta\delta} \right) + \log(K) + \sqrt{d} \right] + c \frac{\sigma^2}{\Delta^2} \sqrt{d \log(K) K U} .$$

Moreover, we have by definition of $U$ (9), $U \ge K \log(K)$, and then $\frac{\sigma^2}{\Delta^2} \sqrt{d \log(K) K U} \le \frac{\sigma^2}{\Delta^2} U \sqrt{d}$.
**Proof of Lemma C.13.** Throughout the proofs of Lemmas C.13 to C.15, c is a universal constant changing from one line to another. Also, we use that, by the definition of $s_0$ and $n_s$, it turns out, that if $s > s_0$ then

$$n_s \le 2c_1 \frac{\sigma^2}{\Delta^2} (2^s + \log(12K)) \lor 2c_2 \frac{\sigma^2}{\Delta^2} \sqrt{d(2^s + \log(6))} . \quad (50)$$

We now bound $K(\sum_{s=s_0+1}^r n_s + n_{\max})$. Relying on the expression of $n_s$ above, and the sums $\sum_{s=1}^r 2^s \le 2^{r+1}$ and $\sum_{s=1}^r \sqrt{2^s} \le \sqrt{2}^{r+1}(1+\sqrt{2})$, we deduce that

$$K \sum_{s=s_0+1}^{r} n_s \le 2c_1 \frac{\sigma^2}{\Delta^2} K(2^{r+1} + \log(12K)r) \lor 2c_2 \frac{\sigma^2}{\Delta^2} K \sqrt{d} (\sqrt{2^r}(2+\sqrt{2}) + \sqrt{\log(6)}r) .$$

Now, from the expression of $r$ and $U$, we have $2^r \le 2 \log(4U/\delta) \le c \log(1/(\theta\delta))$. It leads to the bound

$$K \sum_{s=s_0+1}^{r} n_s \le c \frac{\sigma^2}{\Delta^2} \left[ K \log(1/(\theta\delta)) + K \log(K) \log \log(1/(\theta\delta)) + K \sqrt{d \log(1/(\theta\delta))} \right] .$$

As $1/\theta \ge K$, we have $K \log(1/\theta) \le \frac{1}{\theta} \log(K)$, so that we can bound the term above by

$$K \sum_{s=s_0+1}^{r} n_s \le c \frac{\sigma^2}{\Delta^2} \left[ \frac{1}{\theta} \log(K/\delta) + \sqrt{dK \frac{1}{\theta} \log(K/\delta)} \right] .$$

We also compute $n_{\max}$, we have $Kn_{\max} \le K + c \frac{\sigma^2}{\Delta^2} [Kn_r + K \log(K) \sqrt{d}]$, where $Kn_r$ is upper bounded by the same bound as $K \sum_{s=s_0+1}^r n_s$.

Finally, it implies that

$$K \sum_{s=s_0+1}^{r} n_s + Kn_{\max} \le K + c \frac{\sigma^2}{\Delta^2} \left[ \frac{\log(K)}{\theta} \log(K/\delta) + \sqrt{dK \frac{\log(K)}{\theta} \log(K/\delta)} \right] .$$

The second inequality in Lemma C.13 is clear, and the lemma is proved. $\square$

**Proof of Lemma C.14.** With the bound on $n_s$ for $s > s_0$ from eq. (50), we simplify the terms in $2^s$ and obtain,

$$\begin{aligned}
\sum_{s=s_0+1}^{r} \frac{U}{2^{s-4}} n_s &\le 2c_1 \frac{16U\sigma^2}{\Delta^2} \sum_{s=s_0+1}^{r} \left(1 + \frac{1}{2^s}\log(12K)\right) \lor 2c_2 \frac{16U\sigma^2}{\Delta^2} \sum_{s=s_0+1}^{r} \left(\frac{1}{\sqrt{2}^s}\sqrt{d} + \frac{1}{2^s}\sqrt{d}\sqrt{\log(6)}\right) \\
&\le 2c_1 \frac{16U\sigma^2}{\Delta^2} (r + 2\log(12K)) \lor 2c_2 \frac{16U\sigma^2}{\Delta^2} ((2+\sqrt{2})\sqrt{d} + 2\sqrt{\log(6)}\sqrt{d}) \\
&\le c \frac{\sigma^2}{\Delta^2} U \left[\log \log\left(\frac{1}{\theta\delta}\right) + \log(K) + \sqrt{d}\right],
\end{aligned}$$

because $\sum_{s \ge 1} 1/2^s \le 2$ and $\sum_{s \ge 1} 1/\sqrt{2}^s = 2 + \sqrt{2}$. We also use in the last inequality that $\log(U/\delta) \le 2 \log(8/\theta\delta)$, so that $r \le \log(2 \log(8/\theta\delta)) \le c \log \log(1/\theta\delta)$.

From the previous bound, we conclude that

$$\sum_{s=s_0+1}^{r} \frac{U}{2^{s-4}} n_s \le c \frac{\sigma^2}{\Delta^2} U \left[ \log \log \left( \frac{1}{\theta \delta} \right) + \log(K) + \sqrt{d} \right] + c \frac{\sigma^2}{\Delta^2} \sqrt{d \log(K) K U} .$$

Moreover, we have by definition of $U(9)$, $U \ge K \log(K)$, and then $\frac{\sigma^2}{\Delta^2} \sqrt{d \log(K) K U} \le \frac{\sigma^2}{\Delta^2} U \sqrt{d}$.
Finally, using the expression of $U(9)$, we have

$$ \sum_{s=s_0+1}^{r} \frac{U}{2^{s-4}} n_s \le c \frac{\sigma^2}{\Delta^2} \frac{1}{\theta} \log(K/\delta) \left[ \log(K) + \sqrt{d} + \log \log \left( \frac{1}{\theta\delta} \right) \right] . \quad \square $$

*Proof of Lemma C.15.* With the same computation as in Lemma C.14, we obtain

$$ \begin{aligned} \sum_{s=s_0+1}^{r} n_s \left[ \frac{4}{\theta}(1 + \log(K)) \exp(-2^{s-4}) \right] &\le c \frac{\sigma^2}{\Delta^2} \frac{\log(K)}{\theta} \left[ \log(K) + \sqrt{d} \right] + c \frac{\sigma^2}{\Delta^2} \sqrt{dK} \frac{\log(K)}{\theta} \log(K) \\ &\le c \frac{\sigma^2}{\Delta^2} \frac{\log(K)}{\theta} \left[ \log(K) + \sqrt{d} \right], \end{aligned} $$

where we use $K \le 1/\theta$ in the last inequality. $\square$

## C.4 Proof of Lemma C.3

In this section, we want to prove that the subroutine ADC outputs the exact partition with probability larger than $1 - \delta$, for environments in $\mathcal{E}(\Delta, \theta, \sigma, N, K, d)$. Let $\nu$ be an environment with a minimal gap smaller than $\Delta$, following Assumptions 2.1 and 2.3. We highlight that the algorithm ADC uses $\Delta$, $\sigma$, $N$, $K$ and $d$ as parameters but not $\theta$. Let $S = \{b_1, \dots, b_K\}$ be a set of $K$ arms containing one representative by group. The objective is to find the groups $G_1^*, \dots, G_K^*$ up to permutation. Without loss of generality, we fix the label of the groups so that $G_k^* = \{a \in [N], \mu_a = \mu_{b_k}\}$. We denote by $k(a)$ as the corresponding label of any arm $a$ ($a \in G_k^*$). With this convention, making an error of clustering is equivalent of making an error of labelling.

We denote $\hat{G}$ for the output of the ADC routine. The algorithm labels the arms in $S$ so that $b_k \in \hat{G}_k$ for $k \in [K]$ (see Line 8). Then, it labels each arm $a \in [N] \setminus S$ by $\hat{k}(a)$ defined (eq. (14)) by

$$ \hat{k}(a) \in \underset{j=1,\dots,K}{\operatorname{argmin}} \left\langle \hat{\mu}_a - \hat{\mu}(j), \hat{\mu}'_a - \hat{\mu}'(j) \right\rangle . $$

We have $\{\hat{G} \sim G^*\} = \{\exists a \in [N] \setminus S; \hat{k}(a) \neq k(a)\}$.

Consider $j \in [K]$ a group and $a \in [N]$ an arm. As explained in the introduction, the statistic $\hat{d}_{a,j}^2 := \langle \hat{\mu}_a - \hat{\mu}(j), \hat{\mu}'_a - \hat{\mu}'(j) \rangle$ is a natural non-biased estimator of $\|\mu_a - \mu(j)\|^2$ where $\mu(j) = \mu_{b_j}$ is the center of $G_j^*$. In the expression of $\hat{k}(a), \hat{\mu}(j)$ [resp. $\hat{\mu}'(j)$] is the empirical mean of representative $b_j$ computed with $J = \lfloor c_4 \frac{\sigma^2}{\Delta^2} L \rfloor \cup c_5 \frac{\sigma^2}{\Delta^2} \sqrt{dL \frac{N}{K}}$ samples –see Equation (13) and Line 7– and $L = \log(6NK/\delta)$. The random variable $\hat{\mu}_a$ [resp. $\hat{\mu}'_a$] is the empirical mean of the arm $a$ computed with $I = \lfloor c_4 \frac{\sigma^2}{\Delta^2} L \rfloor \cup c_5 \frac{\sigma^2}{\Delta^2} \sqrt{dL \frac{K}{N}}$ samples – see Line 10. We emphasise that in high dimension, $J \asymp NJ/K$ is much larger than $I$. We want to bound the probability of misclassification for a single arm in $[N] \setminus S$. Let $a \in [N] \setminus S$ such that $a$ belongs to the group $G_{k(a)}^*$. The misclassification probability for the arm $a$ using the classifier $\hat{k}(a)$ of eq. (14) is

$$ \begin{aligned} \mathbb{P}_{\nu}(\hat{k}(a) \neq k(a)) &= \mathbb{P}_{\nu}(\exists j = 1, \dots, K, j \neq k(a); \hat{d}_{a,j}^2 < \hat{d}_{a,k(a)}^2) \\ &\le \sum_{j \neq k(a)}^{K} \mathbb{P}_{\nu}(\hat{d}_{a,j}^2 < \hat{d}_{a,k(a)}^2) . \end{aligned} \quad (51) $$

We used here a first union bound over $j \in [1; K] \setminus k(a)$, and now, we upper bound each term on the sum.

**Lemma C.16.** For all $a \in [N] \setminus S$, and $j \in [K]$, if $\mu(j) \neq \mu_a$ then

$$ \mathbb{P}_{\nu} \left( \hat{d}_{a,j}^2 < \hat{d}_{a,k(a)}^2 \right) \le \frac{\delta}{(K-1)(N-K)} . $$
Finally, using the expression of $U(9)$, we have

$$ \sum_{s=s_0+1}^{r} \frac{U}{2^{s-4}} n_s \le c \frac{\sigma^2}{\Delta^2} \frac{1}{\theta} \log(K/\delta) \left[ \log(K) + \sqrt{d} + \log \log \left( \frac{1}{\theta\delta} \right) \right] . \quad \square $$

*Proof of Lemma C.15.* With the same computation as in Lemma C.14, we obtain

$$ \begin{aligned} \sum_{s=s_0+1}^{r} n_s \left[ \frac{4}{\theta}(1 + \log(K)) \exp(-2^{s-4}) \right] &\le c \frac{\sigma^2}{\Delta^2} \frac{\log(K)}{\theta} \left[ \log(K) + \sqrt{d} \right] + c \frac{\sigma^2}{\Delta^2} \sqrt{dK} \frac{\log(K)}{\theta} \log(K) \\ &\le c \frac{\sigma^2}{\Delta^2} \frac{\log(K)}{\theta} \left[ \log(K) + \sqrt{d} \right], \end{aligned} $$

where we use $K \le 1/\theta$ in the last inequality. $\square$

## C.4 Proof of Lemma C.3

In this section, we want to prove that the subroutine ADC outputs the exact partition with probability larger than $1 - \delta$, for environments in $\mathcal{E}(\Delta, \theta, \sigma, N, K, d)$. Let $\nu$ be an environment with a minimal gap smaller than $\Delta$, following Assumptions 2.1 and 2.3. We highlight that the algorithm ADC uses $\Delta$, $\sigma$, $N$, $K$ and $d$ as parameters but not $\theta$. Let $S = \{b_1, \dots, b_K\}$ be a set of $K$ arms containing one representative by group. The objective is to find the groups $G_1^*, \dots, G_K^*$ up to permutation. Without loss of generality, we fix the label of the groups so that $G_k^* = \{a \in [N], \mu_a = \mu_{b_k}\}$. We denote by $k(a)$ as the corresponding label of any arm $a$ ($a \in G_k^*$). With this convention, making an error of clustering is equivalent of making an error of labelling.

We denote $\hat{G}$ for the output of the ADC routine. The algorithm labels the arms in $S$ so that $b_k \in \hat{G}_k$ for $k \in [K]$ (see Line 8). Then, it labels each arm $a \in [N] \setminus S$ by $\hat{k}(a)$ defined (eq. (14)) by

$$ \hat{k}(a) \in \underset{j=1, \dots, K}{\operatorname{argmin}} \left\langle \hat{\mu}_a - \hat{\mu}(j), \hat{\mu}'_a - \hat{\mu}'(j) \right\rangle . $$

We have $\{\hat{G} \sim G^*\} = \{\exists a \in [N] \setminus S; \hat{k}(a) \neq k(a)\}$.

Consider $j \in [K]$ a group and $a \in [N]$ an arm. As explained in the introduction, the statistic $\hat{d}_{a,j}^2 := \langle \hat{\mu}_a - \hat{\mu}(j), \hat{\mu}'_a - \hat{\mu}'(j) \rangle$ is a natural non-biased estimator of $\|\mu_a - \mu(j)\|^2$ where $\mu(j) = \mu_{b_j}$ is the center of $G_j^*$. In the expression of $\hat{k}(a), \hat{\mu}(j)$ [resp. $\hat{\mu}'(j)$] is the empirical mean of representative $b_j$ computed with $J = \left[c_4 \frac{\sigma^2}{\Delta^2} L \lor c_5 \frac{\sigma^2}{\Delta^2} \sqrt{dL \frac{N}{K}}\right]$ samples –see Equation (13) and Line 7– and $L = \log(6NK/\delta)$. The random variable $\hat{\mu}_a$ [resp. $\hat{\mu}'_a$] is the empirical mean of the arm $a$ computed with $I = \left[c_4 \frac{\sigma^2}{\Delta^2} L \lor c_5 \frac{\sigma^2}{\Delta^2} \sqrt{dL \frac{K}{N}}\right]$ samples – see Line 10. We emphasise that in high dimension, $J \asymp NJ/K$ is much larger than $I$. We want to bound the probability of misclassification for a single arm in $[N] \setminus S$. Let $a \in [N] \setminus S$ such that $a$ belongs to the group $G_{k(a)}^*$. The misclassification probability for the arm $a$ using the classifier $\hat{k}(a)$ of eq. (14) is

$$ \begin{aligned} \mathbb{P}_{\nu}(\hat{k}(a) \neq k(a)) &= \mathbb{P}_{\nu}(\exists j = 1, \dots, K, j \neq k(a); \hat{d}_{a,j}^2 < \hat{d}_{a,k(a)}^2) \\ &\le \sum_{j \neq k(a)}^{K} \mathbb{P}_{\nu}(\hat{d}_{a,j}^2 < \hat{d}_{a,k(a)}^2) . \end{aligned} \quad (51) $$

We used here a first union bound over $j \in [1; K] \setminus k(a)$, and now, we upper bound each term on the sum.

**Lemma C.16.** For all $a \in [N] \setminus S$, and $j \in [K]$, if $\mu(j) \neq \mu_a$ then

$$ \mathbb{P}_{\nu} \left( \hat{d}_{a,j}^2 < \hat{d}_{a,k(a)}^2 \right) \le \frac{\delta}{(K-1)(N-K)} . $$
This lemma easily leads to the desired result (Lemma C.3) by a union bound on $a \in [N] \setminus S$. With eq. (51) and Lemma C.16, we have indeed

$$ \begin{aligned} \mathbb{P}_{\nu}(\hat{G} \not\sim G^*) &= \mathbb{P}_{\nu}(\exists a \in [N] \setminus [S] ; \hat{k}(a) \neq k(a)) \\ &\leq \sum_{a \in [N] \setminus S} \sum_{j \in [K] \setminus \{k(a)\}} \mathbb{P}_{\nu}(\hat{d}_{a,j}^2 < \hat{d}_{a,k(a)}^2) \leq \delta. \end{aligned} $$

Moreover, the budget $\tau_{ADC}$ used to compute ADC is deterministic and equal to $2(N - K)I + 2KJ$ with the notation of the algorithm which leads to the second part of the lemma directly.

We have indeed the (deterministic) bound on the budget of ADC

$$ \tau_{ADC} = 2(N - K)I + 2KJ \leq 2N + 2c_4 \frac{\sigma^2}{\Delta^2} NL \lor 4c_5 \frac{\sigma^2}{\Delta^2} \sqrt{dKNL}. $$

It remains now to prove the auxiliary lemma.

*Proof of Lemma C.16.* Without loss of generality, we assume that $\mu_a = \mu(1)$ and consider $j = 2$. We write

$$ \hat{\mu}_a = \mu_a + \frac{\sigma}{\sqrt{I}} \varepsilon_a = \mu(1) + \frac{\sigma}{\sqrt{I}} \varepsilon_a, $$

where $\varepsilon_a := \frac{\sqrt{I}}{\sigma}(\hat{\mu}_a - \mu_a)$. We define in the same way $\varepsilon(1) := \frac{\sqrt{I}}{\sigma}(\hat{\mu}(1) - \mu(1))$ and also $\varepsilon(2), \varepsilon'_a, \varepsilon'(1)$ and $\varepsilon'(2)$.

From direct computation, reorganising the terms, we write the event $\{\hat{d}_{a,2}^2 < \hat{d}_{a,1}^2\}$ as

$$ \begin{aligned} \langle \hat{\mu}_a - \hat{\mu}(2), \hat{\mu}'_a - \hat{\mu}'(2) \rangle < \langle \hat{\mu}_a - \hat{\mu}(1), \hat{\mu}'_a - \hat{\mu}'(1) \rangle &\Leftrightarrow \\ \frac{\sqrt{2}\sigma \|\mu(1) - \mu(2)\|}{\sqrt{I}} A + \frac{\sqrt{2}\sigma \|\mu(1) - \mu(2)\|}{\sqrt{J}} B + \frac{\sqrt{2}\sigma^2}{\sqrt{IJ}} (C + D) + \frac{\sigma^2}{J} (E + F) > \|\mu(1) - \mu(2)\|^2, \end{aligned} \quad (52) $$

where

$$ A := - \left\langle \frac{\mu(1) - \mu(2)}{\|\mu(1) - \mu(2)\|}, \frac{\varepsilon'_a + \varepsilon_a}{\sqrt{2}} \right\rangle; \quad C := - \left\langle \varepsilon_a, \frac{\varepsilon'(1) - \varepsilon'(2)}{\sqrt{2}} \right\rangle; \quad E := - \langle \varepsilon(2), \varepsilon'(2) \rangle; $$

$$ B := - \left\langle \frac{\mu(2) - \mu(1)}{\|\mu(2) - \mu(1)\|}, \frac{\varepsilon'(2) + \varepsilon(2)}{\sqrt{2}} \right\rangle; \quad D := - \left\langle \varepsilon'_a, \frac{\varepsilon(1) - \varepsilon(2)}{\sqrt{2}} \right\rangle; \quad F := - \langle \varepsilon'(1), \varepsilon(1) \rangle. $$

Let us control the variation of each of these terms.

First, by Assumption 2.1, as in the proofs of Appendix C.1 and C.2, A and B are subGaussian. With the concentration inequality (Lemma E.1) for subGaussian (real) variables, we have

$$ \mathbb{P}_{\nu}(A > \sqrt{2L}) \leq \exp(-L) \quad \text{and} \quad \mathbb{P}(B > \sqrt{2L}) \leq \exp(-L). $$

For the other terms, we use Hanson-Wright inequality (Corollary E.4) with $c_{HW}$ the universal constant from the lemma. The scalar products C, D, E and F verifies all the assumptions for Corollary E.4, and for instance,

$$ \mathbb{P}_{\nu} \left( C > \frac{c_{HW} L}{2} \lor \sqrt{c_{HW} \frac{dL}{2}} \right) \leq \exp(-L), $$

and we have the same bound for D,E and F.
This lemma easily leads to the desired result (Lemma C.3) by a union bound on $a \in [N] \setminus S$. With eq. (51) and Lemma C.16, we have indeed

$$ \begin{aligned} \mathbb{P}_{\nu}(\hat{G} \not\sim G^*) &= \mathbb{P}_{\nu}(\exists a \in [N] \setminus [S] ; \hat{k}(a) \neq k(a)) \\ &\leq \sum_{a \in [N] \setminus S} \sum_{j \in [K] \setminus \{k(a)\}} \mathbb{P}_{\nu}(\hat{d}_{a,j}^2 < \hat{d}_{a,k(a)}^2) \leq \delta. \end{aligned} $$

Moreover, the budget $\tau_{ADC}$ used to compute ADC is deterministic and equal to $2(N - K)I + 2KJ$ with the notation of the algorithm which leads to the second part of the lemma directly.

We have indeed the (deterministic) bound on the budget of ADC

$$ \tau_{ADC} = 2(N - K)I + 2KJ \leq 2N + 2c_4 \frac{\sigma^2}{\Delta^2} NL \lor 4c_5 \frac{\sigma^2}{\Delta^2} \sqrt{dKNL}. $$

It remains now to prove the auxiliary lemma.

*Proof of Lemma C.16.* Without loss of generality, we assume that $\mu_a = \mu(1)$ and consider $j = 2$. We write

$$ \hat{\mu}_a = \mu_a + \frac{\sigma}{\sqrt{I}} \varepsilon_a = \mu(1) + \frac{\sigma}{\sqrt{I}} \varepsilon_a, $$

where $\varepsilon_a := \frac{\sqrt{I}}{\sigma}(\hat{\mu}_a - \mu_a)$. We define in the same way $\varepsilon(1) := \frac{\sqrt{I}}{\sigma}(\hat{\mu}(1) - \mu(1))$ and also $\varepsilon(2), \varepsilon'_a, \varepsilon'(1)$ and $\varepsilon'(2)$.

From direct computation, reorganising the terms, we write the event $\{\hat{d}_{a,2}^2 < \hat{d}_{a,1}^2\}$ as

$$ \begin{aligned} \langle \hat{\mu}_a - \hat{\mu}(2), \hat{\mu}'_a - \hat{\mu}'(2) \rangle < \langle \hat{\mu}_a - \hat{\mu}(1), \hat{\mu}'_a - \hat{\mu}'(1) \rangle &\Leftrightarrow \\ \frac{\sqrt{2}\sigma \|\mu(1) - \mu(2)\|}{\sqrt{I}} A + \frac{\sqrt{2}\sigma \|\mu(1) - \mu(2)\|}{\sqrt{J}} B + \frac{\sqrt{2}\sigma^2}{\sqrt{IJ}} (C + D) + \frac{\sigma^2}{J} (E + F) > \|\mu(1) - \mu(2)\|^2, \end{aligned} \quad (52) $$

where

$$ A := - \left\langle \frac{\mu(1) - \mu(2)}{\|\mu(1) - \mu(2)\|}, \frac{\varepsilon'_a + \varepsilon_a}{\sqrt{2}} \right\rangle; \quad C := - \left\langle \varepsilon_a, \frac{\varepsilon'(1) - \varepsilon'(2)}{\sqrt{2}} \right\rangle; \quad E := - \langle \varepsilon(2), \varepsilon'(2) \rangle; $$

$$ B := - \left\langle \frac{\mu(2) - \mu(1)}{\|\mu(2) - \mu(1)\|}, \frac{\varepsilon'(2) + \varepsilon(2)}{\sqrt{2}} \right\rangle; \quad D := - \left\langle \varepsilon'_a, \frac{\varepsilon(1) - \varepsilon(2)}{\sqrt{2}} \right\rangle; \quad F := - \langle \varepsilon'(1), \varepsilon(1) \rangle. $$

Let us control the variation of each of these terms.

First, by Assumption 2.1, as in the proofs of Appendix C.1 and C.2, A and B are subGaussian. With the concentration inequality (Lemma E.1) for subGaussian (real) variables, we have

$$ \mathbb{P}_{\nu}(A > \sqrt{2L}) \leq \exp(-L) \quad \text{and} \quad \mathbb{P}(B > \sqrt{2L}) \leq \exp(-L). $$

For the other terms, we use Hanson-Wright inequality (Corollary E.4) with $c_{HW}$ the universal constant from the lemma. The scalar products C, D, E and F verifies all the assumptions for Corollary E.4, and for instance,

$$ \mathbb{P}_{\nu} \left( C > \frac{c_{HW} L}{2} \lor \sqrt{c_{HW} \frac{dL}{2}} \right) \leq \exp(-L), $$

and we have the same bound for D,E and F.
We recall the expression $L = \log(\frac{6NK}{\delta})$ defined after Equation (13), in particular, $\exp(-L) \le \frac{\delta}{6NK}$. With a union bound on these 6 errors, it holds that with probability larger than $1 - \delta/NK$ we have

$$ \frac{\sqrt{2\sigma}\|\mu(1) - \mu(2)\|}{\sqrt{I}} A + \frac{\sqrt{2\sigma}\|\mu(1) - \mu(2)\|}{\sqrt{J}} B + \frac{\sqrt{2}\sigma^2}{\sqrt{I,J}} (C + D) + \frac{\sigma^2}{J}(E + F) \\ \le \frac{\sqrt{2\sigma}\|\mu(1) - \mu(2)\|}{\sqrt{I}} \sqrt{2L} + \frac{\sqrt{2\sigma}\|\mu(1) - \mu(2)\|}{\sqrt{J}} \sqrt{2L} + \frac{2\sqrt{2}\sigma^2}{\sqrt{I,J}} \left( \frac{c_{HW}L}{2} \vee \sqrt{c_{HW}\frac{dL}{2}} \right) \\ + \frac{2\sigma^2}{J} \left( \frac{c_{HW}L}{2} \vee \sqrt{c_{HW}\frac{dL}{2}} \right). $$

The parameters $I,J$ are defined as

$$ I = \left\lceil \frac{\sigma^2}{\Delta^2} \left( c_4 L \vee c_5 \sqrt{\frac{K}{N}} dL \right) \right\rceil; \quad J = \left\lceil \frac{\sigma^2}{\Delta^2} \left( c_4 L \vee c_5 \sqrt{\frac{N}{K}} dL \right) \right\rceil, $$

with $c_4$ and $c_5$ two universal constants defined as $c_4 = 8^2 \vee 4\sqrt{2c_{HW}}$ and $c_5 = 8\sqrt{c_{HW}}$ with $c_{HW}$ the universal constant in Hanson-Wright inequality (Lemma E.3). Now, each term in the last sum is smaller than $\|\mu(1) - \mu(2)\|\Delta/4$, or $\Delta^2/4$. As $\nu \in \mathcal{E}(\Delta, \theta, \sigma, N, K, d)$, we have $\Delta_* \ge \Delta$ and $\|\mu(1) - \mu(2)\| \ge \Delta$. It implies that with probability larger than $1 - \delta/NK$, it holds that

$$ \frac{\sqrt{2}\sigma\|\mu(1) - \mu(2)\|}{\sqrt{I}} A + \frac{\sqrt{2}\sigma\|\mu(1) - \mu(2)\|}{\sqrt{J}} B + \frac{\sqrt{2}\sigma^2}{\sqrt{I,J}} (C + D) + \frac{\sigma^2}{J}(E + F) \le \|\mu(1) - \mu(2)\|^2. $$

From there, eq. (52) assures that

$$ \mathbb{P}_{\nu} \left( \left\langle \hat{\mu}_1 - \hat{\mu}(2), \hat{\mu}'_1 - \hat{\mu}'(2) \right\rangle < \left\langle \hat{\mu}_a - \hat{\mu}(k(a)), \hat{\mu}'_a - \hat{\mu}'(k(a)) \right\rangle \right) \le \frac{\delta}{KN}. \quad \square $$

## D Analysis of $ACB^*$

In this section, we prove the part of Theorem 4.1 pertaining to $ACB^*$. In fact, this result is a straightforward consequence of the following theorem

**Theorem D.1.** Let $\delta > 0$. For any environment $\nu$, $ACB^*$ Algorithm 2 is $\delta$-PAC. There exist positive numerical constants $c, c'$, and $c''$ such that the following holds.

$$ \mathbb{P}_{ACB^*, \nu} \left[ \tau_{ACB^*} \le cN + c' \frac{\sigma^2}{\Delta_*^2 \theta_*} L_* \log \left( \frac{L_* K}{\delta} \right) \left[ \log(K) + \sqrt{d} + \log \log(L_*) + \log \log(N/\delta) \right] \right. \\ \left. + c' \frac{L_*}{\theta_*} \log \left( \frac{L_* K}{\delta} \right) + c'' \frac{\sigma^2}{\Delta_*^2} \left[ N \log(N/\delta) + \sqrt{dNK \log(N/\delta)} \right] \right] \ge 1 - \delta, \quad (53) $$

where

$$ L_* := \left\lceil \log_2 \left( \frac{1}{\theta_* K} \left[ \left( \frac{\Delta_0^2}{\Delta_*^2} \vee 1 \right) \right] \right) \right\rceil. \quad (54) $$

We set the numerical constant $c_6$ in the definition (16) of $n'_p$ as

$$ c_6 = 2048 \vee 64c_{HW} \vee 92\sqrt{c_{HW}}, \quad (55) $$

where $c_{HW}$ is the constant arising in Hanson-Wright inequality –see Lemma E.3.

### D.1 Analysis of SRI for $\Delta \le 4\Delta_*$

We explained in Appendix C.1 how the algorithm $\hat{S} = \text{SRI}(\delta, \Delta, \theta)$ behaves for environments that are not in $\mathcal{E}(\Delta, \theta, \sigma, N, K, d)$. If $\Delta_* \ge \Delta$ then the identification of $K$ representatives goes well but, if $\Delta_* \gg \Delta$, the budget will be unnecessarily large. If $\Delta_* \le \Delta$, then the set of representative $\hat{S}$ may contain less than $K$ representative. The following lemma summarizes the properties of SRI.
We recall the expression $L = \log(\frac{6NK}{\delta})$ defined after Equation (13), in particular, $\exp(-L) \le \frac{\delta}{6NK}$. With a union bound on these 6 errors, it holds that with probability larger than $1 - \delta/NK$ we have

$$ \frac{\sqrt{2\sigma}\|\mu(1) - \mu(2)\|}{\sqrt{I}} A + \frac{\sqrt{2\sigma}\|\mu(1) - \mu(2)\|}{\sqrt{J}} B + \frac{\sqrt{2}\sigma^2}{\sqrt{I,J}} (C + D) + \frac{\sigma^2}{J}(E + F) \\ \le \frac{\sqrt{2\sigma}\|\mu(1) - \mu(2)\|}{\sqrt{I}} \sqrt{2L} + \frac{\sqrt{2\sigma}\|\mu(1) - \mu(2)\|}{\sqrt{J}} \sqrt{2L} + \frac{2\sqrt{2}\sigma^2}{\sqrt{I,J}} \left( \frac{c_{HW}L}{2} \vee \sqrt{c_{HW}\frac{dL}{2}} \right) \\ + \frac{2\sigma^2}{J} \left( \frac{c_{HW}L}{2} \vee \sqrt{c_{HW}\frac{dL}{2}} \right) . $$

The parameters $I,J$ are defined as

$$ I = \left\lceil \frac{\sigma^2}{\Delta^2} \left( c_4 L \vee c_5 \sqrt{\frac{K}{N}} dL \right) \right\rceil; \quad J = \left\lceil \frac{\sigma^2}{\Delta^2} \left( c_4 L \vee c_5 \sqrt{\frac{N}{K}} dL \right) \right\rceil, $$

with $c_4$ and $c_5$ two universal constants defined as $c_4 = 8^2 \vee 4\sqrt{2c_{HW}}$ and $c_5 = 8\sqrt{c_{HW}}$ with $c_{HW}$ the universal constant in Hanson-Wright inequality (Lemma E.3). Now, each term in the last sum is smaller than $\|\mu(1) - \mu(2)\|\Delta/4$, or $\Delta^2/4$. As $\nu \in \mathcal{E}(\Delta, \theta, \sigma, N, K, d)$, we have $\Delta_* \ge \Delta$ and $\|\mu(1) - \mu(2)\| \ge \Delta$. It implies that with probability larger than $1 - \delta/NK$, it holds that

$$ \frac{\sqrt{2}\sigma\|\mu(1) - \mu(2)\|}{\sqrt{I}} A + \frac{\sqrt{2}\sigma\|\mu(1) - \mu(2)\|}{\sqrt{J}} B + \frac{\sqrt{2}\sigma^2}{\sqrt{I,J}} (C + D) + \frac{\sigma^2}{J}(E + F) \le \|\mu(1) - \mu(2)\|^2. $$

From there, eq. (52) assures that

$$ \mathbb{P}_{\nu} \left( \left\langle \hat{\mu}_1 - \hat{\mu}(2), \hat{\mu}'_1 - \hat{\mu}'(2) \right\rangle < \left\langle \hat{\mu}_a - \hat{\mu}(k(a)), \hat{\mu}'_a - \hat{\mu}'(k(a)) \right\rangle \right) \le \frac{\delta}{KN}. \quad \square $$

## D Analysis of $ACB^*$

In this section, we prove the part of Theorem 4.1 pertaining to $ACB^*$. In fact, this result is a straightforward consequence of the following theorem

**Theorem D.1.** Let $\delta > 0$. For any environment $\nu$, $ACB^*$ Algorithm 2 is $\delta$-PAC. There exist positive numerical constants $c, c'$, and $c''$ such that the following holds.

$$ \mathbb{P}_{ACB^*, \nu} \left[ \tau_{ACB^*} \le cN + c' \frac{\sigma^2}{\Delta_*^2 \theta_*} L_* \log \left( \frac{L_* K}{\delta} \right) \left[ \log(K) + \sqrt{d} + \log \log(L_*) + \log \log(N/\delta) \right] \right. \\ \left. + c' \frac{L_*}{\theta_*} \log \left( \frac{L_* K}{\delta} \right) + c'' \frac{\sigma^2}{\Delta_*^2} \left[ N \log(N/\delta) + \sqrt{dNK \log(N/\delta)} \right] \right] \ge 1 - \delta, \quad (53) $$

where

$$ L_* := \left\lceil \log_2 \left( \frac{1}{\theta_* K} \left[ \left( \frac{\Delta_0^2}{\Delta_*^2} \vee 1 \right) \right] \right) \right\rceil. \quad (54) $$

We set the numerical constant $c_6$ in the definition (16) of $n'_p$ as

$$ c_6 = 2048 \vee 64c_{HW} \vee 92\sqrt{c_{HW}}, \quad (55) $$

where $c_{HW}$ is the constant arising in Hanson-Wright inequality –see Lemma E.3.

### D.1 Analysis of SRI for $\Delta \le 4\Delta_*$

We explained in Appendix C.1 how the algorithm $\hat{S} = \text{SRI}(\delta, \Delta, \theta)$ behaves for environments that are not in $\mathcal{E}(\Delta, \theta, \sigma, N, K, d)$. If $\Delta_* \ge \Delta$ then the identification of $K$ representatives goes well but, if $\Delta_* \gg \Delta$, the budget will be unnecessarily large. If $\Delta_* \le \Delta$, then the set of representative $\hat{S}$ may contain less than $K$ representative. The following lemma summarizes the properties of SRI.
**Lemma D.2.** Take $\nu$ an environment with a minimal gap $\Delta_*$ and a balancedness $\theta_*$. Consider $\hat{S} = SRI(\delta, \Delta, \theta)$ the output of the SRI routine, designed with $\Delta > 0$ and $\theta > 0$. With probability $P_{SRI,\nu}$ larger than $1 - \delta$, the following holds

* the set $\hat{S}$ does not contain two arms from the same cluster,

* if $\Delta_* \le \Delta/4$, then $\hat{S}$ contains strictly less than $K$ arms,

* if $\Delta_* \ge \Delta$ and $\theta_* \ge \theta$ then $\hat{S}$ contains exactly one arm by group.

*Proof.* The first point is a consequence of Lemma C.8 and Lemma C.10. The third point is exactly the result of Lemma C.2.

For the second point, recall that by definition, a candidate $a_u$ is bad if there exists an arm $a$ in the set $S$ such that $\|\mu_{a_u} - \mu_a\| \le \Delta/4$. In Lemma C.10, we prove that with probability larger than $1 - \delta$, no bad arms would be added to $S$. Moreover, if $\Delta_* \le \Delta/4$, then there exists at least one group whose arms are bad during all the procedure, and hence, the second point is also a consequence of Lemma C.8 and Lemma C.10. $\square$

## D.2 Proof of Theorem D.1

### D.2.1 ACB* is $\delta$-PAC

We consider separately two cases $\Delta_* \le \Delta_0$ and $\Delta_* > \Delta_0$. We first focus on the case where $\Delta_* \le \Delta_0$.

We remind the reader that the procedure ACB* consists on a sequence of calls for SRI, with different parameters, we remind these parameters as defined in (15), (16)

$$ \Delta_0^2 = \sigma^2[\log(K) + \sqrt{d} + \log \log(6N/\delta)], \quad \delta_l = \frac{\delta}{6(l+1)^3} \\ \theta_{p,l} = \frac{1}{K2^{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]. $$

For short, we write $SRI(p, l)$ for SRI routine with parameters $\delta_l$, $\Delta_p$, and $\theta_{p,l}$. For $l \ge 0$ and $p = 0, \dots, l$, we define $\mathcal{E}_{p,l}$ as the event of probability larger than $1 - \delta_l$ under $P_{SRI(p,l),\nu}$ defined in Lemma D.2. We write $\mathcal{E}$ for the intersection of these events.

From Lemma D.2, the event $\mathcal{E}_{p,l}$ has a probability larger than $1 - \delta_l$. With a union bound, and the definition of $\delta_l$ (15), we deduce that

$$ P(\mathcal{E}) = P\left(\bigcap_{p,l} \mathcal{E}_{p,l}\right) \ge 1 - \sum_{l \ge 1} \sum_{p=0}^{l} \delta_l = 1 - \sum_{l \ge 0} \frac{\delta}{6(l+1)^2} \ge 1 - \delta/3. $$

We write $(l', p')$ the first value of $(l, p)$ in Algorithm 2 such that $|S_{l,p}| = K$. On the event $\mathcal{E}$, we have that $\hat{S} = S_{l',p'}$ contains exactly one arm by cluster – see again Lemma D.2.

Even, if on the event $\mathcal{E}$, we know that $\Delta_* \ge \Delta_{p'}/4$ (see also Lemma D.2). This lower bound on $\Delta_*$ could be used to parameterize the ADC Algorithm 1, however, we prefer to estimate $\Delta_*$ directly in Algorithm 2 before applying the routine ADC. Recall that $n'_p = c_6 \frac{\sigma^2}{\Delta_p^2} (\log(3K^2/\delta) + \sqrt{d \log(3K^2/\delta)})$. We use $2Kn'_{p'}$ samples to estimate $\Delta_*$–see $\hat{\Delta}$ in Line 8 of Algorithm 2. Arguing as in the proof of Lemma C.8, we deduce from the definition (55) of $c_6$, that, on the intersection of the event $\mathcal{E}$ with an event of probability higher than $1 - \delta/3$, we have

$$ \frac{1}{4}\Delta_*^2 \le \frac{1}{2}\hat{\Delta}^2 \le \Delta_*^2 $$

Since, on this event, we have $2^{-1/2}\hat{\Delta} \le \Delta_*$, we are in position to apply Lemma C.3 to $ADC(\delta/3, 2^{-1/2}\hat{\Delta}, \hat{S})$. In summary, we have proved that ACB* is $\delta$-PAC.
**Lemma D.2.** Take $\nu$ an environment with a minimal gap $\Delta_*$ and a balancedness $\theta_*$. Consider $\hat{S} = SRI(\delta, \Delta, \theta)$ the output of the SRI routine, designed with $\Delta > 0$ and $\theta > 0$. With probability $P_{SRI,\nu}$ larger than $1 - \delta$, the following holds

* the set $\hat{S}$ does not contain two arms from the same cluster,

* if $\Delta_* \le \Delta/4$, then $\hat{S}$ contains strictly less than $K$ arms,

* if $\Delta_* \ge \Delta$ and $\theta_* \ge \theta$ then $\hat{S}$ contains exactly one arm by group.

*Proof.* The first point is a consequence of Lemma C.8 and Lemma C.10. The third point is exactly the result of Lemma C.2.

For the second point, recall that by definition, a candidate $a_u$ is bad if there exists an arm $a$ in the set $S$ such that $\|\mu_{a_u} - \mu_a\| \le \Delta/4$. In Lemma C.10, we prove that with probability larger than $1 - \delta$, no bad arms would be added to $S$. Moreover, if $\Delta_* \le \Delta/4$, then there exists at least one group whose arms are bad during all the procedure, and hence, the second point is also a consequence of Lemma C.8 and Lemma C.10. $\square$

## D.2 Proof of Theorem D.1

### D.2.1 ACB* is $\delta$-PAC

We consider separately two cases $\Delta_* \le \Delta_0$ and $\Delta_* > \Delta_0$. We first focus on the case where $\Delta_* \le \Delta_0$.

We remind the reader that the procedure ACB* consists on a sequence of calls for SRI, with different parameters, we remind these parameters as defined in (15), (16)

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

$$ \theta_{p,l} = \frac{1}{K2^{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]. $$

For short, we write $SRI(p, l)$ for SRI routine with parameters $\delta_l$, $\Delta_p$, and $\theta_{p,l}$. For $l \ge 0$ and $p = 0, \dots, l$, we define $\mathcal{E}_{p,l}$ as the event of probability larger than $1 - \delta_l$ under $P_{SRI(p,l),\nu}$ defined in Lemma D.2. We write $\mathcal{E}$ for the intersection of these events.

From Lemma D.2, the event $\mathcal{E}_{p,l}$ has a probability larger than $1 - \delta_l$. With a union bound, and the definition of $\delta_l$ (15), we deduce that

$$ P(\mathcal{E}) = P\left(\bigcap_{p,l} \mathcal{E}_{p,l}\right) \ge 1 - \sum_{l \ge 1} \sum_{p=0}^{l} \delta_l = 1 - \sum_{l \ge 0} \frac{\delta}{6(l+1)^2} \ge 1 - \delta/3. $$

We write $(l', p')$ the first value of $(l, p)$ in Algorithm 2 such that $|S_{l,p}| = K$. On the event $\mathcal{E}$, we have that $\hat{S} = S_{l',p'}$ contains exactly one arm by cluster – see again Lemma D.2.

Even, if on the event $\mathcal{E}$, we know that $\Delta_* \ge \Delta_{p'}/4$ (see also Lemma D.2). This lower bound on $\Delta_*$ could be used to parameterize the ADC Algorithm 1, however, we prefer to estimate $\Delta_*$ directly in Algorithm 2 before applying the routine ADC. Recall that $n'_p = c_6 \frac{\sigma^2}{\Delta_p^2} (\log(3K^2/\delta) + \sqrt{d \log(3K^2/\delta)})$. We use $2Kn'_{p'}$ samples to estimate $\Delta_*$–see $\hat{\Delta}$ in Line 8 of Algorithm 2. Arguing as in the proof of Lemma C.8, we deduce from the definition (55) of $c_6$, that, on the intersection of the event $\mathcal{E}$ with an event of probability higher than $1 - \delta/3$, we have

$$ \frac{1}{4}\Delta_*^2 \le \frac{1}{2}\hat{\Delta}^2 \le \Delta_*^2 $$

Since, on this event, we have $2^{-1/2}\hat{\Delta} \le \Delta_*$, we are in position to apply Lemma C.3 to ADC($\delta/3, 2^{-1/2}\hat{\Delta}, \hat{S}$). In summary, we have proved that ACB* is $\delta$-PAC.
### D.2.2 Control of the budget of ACB*

We now bound the budget of ACB* under the same event as in the previous subsection.

The key observation was proven page 22 of [17], taking $T_l = 2^l$, it holds that

$$ \{\theta \in (0, 1/K), \Delta \in (0, \Delta_0): \frac{\Delta_0^2}{K\theta\Delta^2} \le 2^l\} \subset \bigcup_{p=0}^{l-1} \{(\theta, \Delta): \theta \ge \theta_{p,l}, \Delta \ge \Delta_p\} . $$

In particular, if $2^l \ge \frac{\Delta_0^2}{K\theta_*\Delta_*^2}$, then, there exists $p \in [l-1]$ such that $\theta_{p,l} \le \theta_*$ and $\Delta_{p,l} \le \Delta_*$. From this result and from Lemma D.2, we get that, on the event $\mathcal{E}$, the stopping time $l'$ satisfies $l' \le L_* = \lfloor \log_2 \left( \frac{\Delta_0^2}{K\theta_*\Delta_*^2} \right) \rfloor$ –recall that $L_*$ is defined in (54).

We write $\tau_1$ at the total budget we have spent for computing $\hat{S}$. Recall that the budget of the routine SRI is almost surely bounded by $T_{\max}$ — see (12) — and we upper bounded $T_{\max}$ in (37). In order to emphasize the dependency of this budget on $(\delta, \Delta, \theta)$ we write $T_{\max}(\delta, \Delta, \theta)$ in the sequel.

By (37), on the event $\mathcal{E}$, we have

$$ \tau_1 \le \sum_{l=0}^{L_*} \sum_{p=0}^{l} T_{\max}(\delta_l, \Delta_p, \theta_{p,l} \lor 1/N) \\ \le \sum_{l=0}^{L_*} \sum_{p=0}^{l} 2 \left( \left\lfloor \frac{8}{\theta_{p,l}} \log \left( \frac{8K}{\delta_l} \right) \right\rfloor + K \right) + c' \frac{\sigma^2}{\Delta_p^2} \frac{1}{\theta_{p,l}} \log \left( \frac{K}{\delta_l} \right) \left[ \log(K) + \sqrt{d} + \log \log \left( \frac{N}{\delta_l} \right) \right] . $$

We observe that, in ACB* Line 4, we use SRI with $\theta_{p,l} \lor 1/N$ because any environment has necessary a balancedness larger than $1/N$. It allows us to bound the log log-term in eq. (37) by $\log(\log(N/\delta))$.

Now, by definition (16), $\theta_{p,l} = \frac{1}{K2^{l-p}}$ and $\Delta_p^2 = \frac{\Delta_0^2}{2p}$ so that $\frac{1}{\Delta_p^2} \frac{1}{\theta_{p,l}} = \frac{K2^l}{\Delta_0^2}$ and then

$$ \begin{aligned} \tau_1 &\le \sum_{l=0}^{L_*} \sum_{p=0}^{l} \left( 16K \cdot 2^p \log \left( \frac{8K}{\delta_l} \right) + 2(K+1) \right) \\ &\quad + \sum_{l=0}^{L_*} \sum_{p=0}^{l} c' \frac{\sigma^2}{\Delta_0^2} K 2^l \log \left( \frac{K}{\delta_l} \right) \left[ \log(K) + \sqrt{d} + \log \log \left( \frac{N}{\delta_{L_*}} \right) \right] \\ &\le 2(L_*+1)^2(K+1) + cK 2^{L_*} \log \left( \frac{8K}{\delta_{L_*}} \right) \\ &\quad + c' \frac{\sigma^2}{\Delta_0^2} K(L_*+1) 2^{L_*} \log \left( \frac{K}{\delta_{L_*}} \right) \left[ \log(K) + \sqrt{d} + \log \log \left( \frac{N}{\delta_{L_*}} \right) \right] . \end{aligned} $$

Now, $2^{L_*} \le 2 \frac{\Delta_0^2}{\theta_* K \Delta_*^2}$, so that

$$ \begin{aligned} \tau_1 &\le 2(L_*+1)^2(K+1) + c \frac{\Delta_0^2}{\theta_* \Delta_*^2} \log \left( 8 \frac{K(L_*+1)^3}{\delta} \right) \\ &\quad + c'(L_*+1) \frac{\sigma^2}{\theta_* \Delta_*^2} \log \left( \frac{6K(L_*+1)^3}{\delta} \right) \left[ \log(K) + \sqrt{d} + \log \log \left( \frac{6N(L_*+1)^3}{\delta} \right) \right] \\ &\le c L_*^2 K + c' L_* \frac{\sigma^2}{\theta_* \Delta_*^2} \log \left( \frac{KL_*}{\delta} \right) \left[ \log(K) + \sqrt{d} + \log \log \left( \frac{NL_*}{\delta} \right) \right] . \end{aligned} \quad (56) $$

In the last inequality, we used the expression of $\Delta_0^2$ (15) which implies that

$$ \frac{\Delta_0^2}{\theta_* \Delta_*^2} \log \left( 8 \frac{K(L_*+1)^3}{\delta} \right) \le c' \frac{\sigma^2}{\theta_* \Delta_*^2} \log \left( \frac{KL_*}{\delta} \right) \left[ \log(K) + \sqrt{d} + \log \log \left( \frac{N}{\delta} \right) \right] . $$
### D.2.2 Control of the budget of ACB*

We now bound the budget of ACB* under the same event as in the previous subsection.

The key observation was proven page 22 of [17], taking $T_l = 2^l$, it holds that

$$ \{\theta \in (0, 1/K), \Delta \in (0, \Delta_0): \frac{\Delta_0^2}{K\theta\Delta^2} \le 2^l\} \subset \bigcup_{p=0}^{l-1} \{(\theta, \Delta): \theta \ge \theta_{p,l}, \Delta \ge \Delta_p\} . $$

In particular, if $2^l \ge \frac{\Delta_0^2}{K\theta_*\Delta_*^2}$, then, there exists $p \in [l-1]$ such that $\theta_{p,l} \le \theta_*$ and $\Delta_{p,l} \le \Delta_*$. From this result and from Lemma D.2, we get that, on the event $\mathcal{E}$, the stopping time $l'$ satisfies $l' \le L_* = \lfloor \log_2 \left( \frac{\Delta_0^2}{K\theta_*\Delta_*^2} \right) \rfloor$ –recall that $L_*$ is defined in (54).

We write $\tau_1$ at the total budget we have spent for computing $\hat{S}$. Recall that the budget of the routine SRI is almost surely bounded by $T_{\max}$ — see (12) — and we upper bounded $T_{\max}$ in (37). In order to emphasize the dependency of this budget on $(\delta, \Delta, \theta)$ we write $T_{\max}(\delta, \Delta, \theta)$ in the sequel.

By (37), on the event $\mathcal{E}$, we have

$$ \tau_1 \le \sum_{l=0}^{L_*} \sum_{p=0}^{l} T_{\max}(\delta_l, \Delta_p, \theta_{p,l} \lor 1/N) \\ \le \sum_{l=0}^{L_*} \sum_{p=0}^{l} 2 \left( \left\lfloor \frac{8}{\theta_{p,l}} \log \left( \frac{8K}{\delta_l} \right) \right\rfloor + K \right) + c' \frac{\sigma^2}{\Delta_p^2} \frac{1}{\theta_{p,l}} \log \left( \frac{K}{\delta_l} \right) \left[ \log(K) + \sqrt{d} + \log \log \left( \frac{N}{\delta_l} \right) \right] . $$

We observe that, in ACB* Line 4, we use SRI with $\theta_{p,l} \lor 1/N$ because any environment has necessary a balancedness larger than $1/N$. It allows us to bound the log log-term in eq. (37) by $\log(\log(N/\delta))$.

Now, by definition (16), $\theta_{p,l} = \frac{1}{K2^{l-p}}$ and $\Delta_p^2 = \frac{\Delta_0^2}{2p}$ so that $\frac{1}{\Delta_p^2} \frac{1}{\theta_{p,l}} = \frac{K2^l}{\Delta_0^2}$ and then

$$ \begin{aligned} \tau_1 &\le \sum_{l=0}^{L_*} \sum_{p=0}^{l} \left( 16K \cdot 2^p \log \left( \frac{8K}{\delta_l} \right) + 2(K+1) \right) \\ &\quad + \sum_{l=0}^{L_*} \sum_{p=0}^{l} c' \frac{\sigma^2}{\Delta_0^2} K 2^l \log \left( \frac{K}{\delta_l} \right) \left[ \log(K) + \sqrt{d} + \log \log \left( \frac{N}{\delta_{L_*}} \right) \right] \\ &\le 2(L_*+1)^2(K+1) + cK 2^{L_*} \log \left( \frac{8K}{\delta_{L_*}} \right) \\ &\quad + c' \frac{\sigma^2}{\Delta_0^2} K(L_*+1) 2^{L_*} \log \left( \frac{K}{\delta_{L_*}} \right) \left[ \log(K) + \sqrt{d} + \log \log \left( \frac{N}{\delta_{L_*}} \right) \right] . \end{aligned} $$

Now, $2^{L_*} \le 2 \frac{\Delta_0^2}{\theta_* K \Delta_*^2}$, so that

$$ \begin{aligned} \tau_1 &\le 2(L_*+1)^2(K+1) + c \frac{\Delta_0^2}{\theta_* \Delta_*^2} \log \left( 8 \frac{K(L_*+1)^3}{\delta} \right) \\ &\quad + c'(L_*+1) \frac{\sigma^2}{\theta_* \Delta_*^2} \log \left( \frac{6K(L_*+1)^3}{\delta} \right) \left[ \log(K) + \sqrt{d} + \log \log \left( \frac{6N(L_*+1)^3}{\delta} \right) \right] \\ &\le c L_*^2 K + c' L_* \frac{\sigma^2}{\theta_* \Delta_*^2} \log \left( \frac{KL_*}{\delta} \right) \left[ \log(K) + \sqrt{d} + \log \log \left( \frac{NL_*}{\delta} \right) \right] . \end{aligned} \quad (56) $$

In the last inequality, we used the expression of $\Delta_0^2$ (15) which implies that

$$ \frac{\Delta_0^2}{\theta_* \Delta_*^2} \log \left( 8 \frac{K(L_*+1)^3}{\delta} \right) \le c' \frac{\sigma^2}{\theta_* \Delta_*^2} \log \left( \frac{KL_*}{\delta} \right) \left[ \log(K) + \sqrt{d} + \log \log \left( \frac{N}{\delta} \right) \right] . $$
Let us now consider the budget $\tau_2$ dedicated to the estimation of $\Delta_*$. Since $\Delta_{p'}^{-2} \le 2^{L_*} \Delta_0^{-2}$, we deduce that

$$ \tau_2 = 2Kn_{p'} \le 2K + c \frac{\sigma^2}{\theta_* \Delta_*^2} \left( \log(3K^2/\delta) + \sqrt{d \log(3K^2/\delta)} \right) . \quad (57) $$

Finally, as we are working under the event $\hat{\Delta}^2/\Delta_*^2 \in [1/2, 2]$, we deduce from Lemma C.3 that the budget $\tau_3$ incurred by ADC is smaller or equal to

$$ \tau_3 \le 2N + c \frac{\sigma^2}{\Delta_*^2} N \log \left( \frac{N}{\delta} \right) + c \frac{\sigma^2}{\Delta_*^2} \sqrt{dKN \log \left( \frac{N}{\delta} \right)} . \quad (58) $$

The total budget is obtained by summing the bounds (56), (57), and (58).

It remains to consider the case where $\Delta_* \ge \Delta_0$. In that case, under the events of the previous subsection, the first phase of the algorithm stops at the latest as $(l, p) = (L_*, 0)$, where $L_* = \lceil \log_2(1/(\theta_* K)) \rceil$. Arguing as above, we deduce that $\tau_1$ satisfies

$$ \tau_1 \le cKL_*^2 + c'L_* \frac{1}{\theta_*} \log \left( \frac{KL_*}{\delta} \right) . \quad (59) $$

Regarding the second step of the algorithm, we know that $p' \le L_*$ so that $\Delta_{p'}^{-2} \le 2^{L_*} \Delta_0^{-2} \le \frac{\Delta_0^{-2}}{\theta_* K}$. We deduce that

$$ \tau_2 \le 2K + c \frac{\log(3K^2/\delta) + \sqrt{d \log(3K^2/\delta)}}{\theta_* [\log(K) + \sqrt{d} + \log \log(6N/\delta)]} \le 2K + c'L_* \frac{1}{\theta_*} \log \left( \frac{KL_*}{\delta} \right) . \quad (60) $$

Finally, the budget $\tau_3$ is still given by (58). Gathering (59), (60), and (58) allows us to conclude.

## E Concentration inequalities

We now give a few concentration inequalities used in the paper.

First, a consequence of the definition of $\sigma$-subGaussian random variables given in Assumption 2.1 is the following,

**Lemma E.1.** Let $Y \in \mathbb{R}$ be subGaussian, then for all $x > 0$,

$$ \mathbb{P}(X > x) \le \exp(-\frac{x^2}{2}), \text{ and } \mathbb{P}(X < -x) \le \exp(-\frac{x^2}{2}) . $$

Here is Laurent and Massart inequality, page 1325 of [22].

**Lemma E.2 (Laurent & Massart).** Let $Z \sim \chi_d^2$ a chi-square distribution, where $d \ge 1$ is the degree of freedom, then for any $x > 0$,

$$ \mathbb{P}(Z \ge d + 2\sqrt{dx} + 2x) \le \exp(-x), \text{ and } \mathbb{P}(Z \le d - 2\sqrt{dx}) \le \exp(-x) . $$

We now give the Hanson-Wright inequality for the concentration of scalar products of subGaussian random variables – see [32] for the proof.

**Lemma E.3 (Hanson-Wright inequality).** Let $Y$ be a $d$-dimensional vector in $\mathbb{R}^d$ with independent, centered and 1-subGaussian components. Let $A$ be a $d \times d$ matrix. Then, there exists a constant $c_{HW}$ such that for any $x \ge 0$,

$$ \mathbb{P}(Y^T AY - \mathbb{E}[Y^T AY] > x) \le \exp \left( - \frac{1}{c_{HW}} \left( \frac{x^2}{\|A\|_F^2} \wedge \frac{x}{\|A\|_{op}} \right) \right), $$

where $\|A\|_{op}$ is the operator norm of $A$, $\|A\|_F$ is the Frobenius norm.

We use in this paper the following corollary,
Let us now consider the budget $\tau_2$ dedicated to the estimation of $\Delta_*$. Since $\Delta_{p'}^{-2} \le 2^{L_*} \Delta_0^{-2}$, we deduce that

$$ \tau_2 = 2Kn_{p'} \le 2K + c \frac{\sigma^2}{\theta_* \Delta_*^2} \left( \log(3K^2/\delta) + \sqrt{d \log(3K^2/\delta)} \right) . \quad (57) $$

Finally, as we are working under the event $\hat{\Delta}^2/\Delta_*^2 \in [1/2, 2]$, we deduce from Lemma C.3 that the budget $\tau_3$ incurred by ADC is smaller or equal to

$$ \tau_3 \le 2N + c \frac{\sigma^2}{\Delta_*^2} N \log \left( \frac{N}{\delta} \right) + c \frac{\sigma^2}{\Delta_*^2} \sqrt{dKN \log \left( \frac{N}{\delta} \right)} . \quad (58) $$

The total budget is obtained by summing the bounds (56), (57), and (58).

It remains to consider the case where $\Delta_* \ge \Delta_0$. In that case, under the events of the previous subsection, the first phase of the algorithm stops at the latest as $(l, p) = (L_*, 0)$, where $L_* = \lceil \log_2(1/(\theta_* K)) \rceil$. Arguing as above, we deduce that $\tau_1$ satisfies

$$ \tau_1 \le cKL_*^2 + c'L_* \frac{1}{\theta_*} \log \left( \frac{KL_*}{\delta} \right) . \quad (59) $$

Regarding the second step of the algorithm, we know that $p' \le L_*$ so that $\Delta_{p'}^{-2} \le 2^{L_*} \Delta_0^{-2} \le \frac{\Delta_0^{-2}}{\theta_* K}$. We deduce that

$$ \tau_2 \le 2K + c \frac{\log(3K^2/\delta) + \sqrt{d \log(3K^2/\delta)}}{\theta_* [\log(K) + \sqrt{d} + \log \log(6N/\delta)]} \le 2K + c' L_* \frac{1}{\theta_*} \log \left( \frac{KL_*}{\delta} \right) . \quad (60) $$

Finally, the budget $\tau_3$ is still given by (58). Gathering (59), (60), and (58) allows us to conclude.

## E Concentration inequalities

We now give a few concentration inequalities used in the paper.

First, a consequence of the definition of $\sigma$-subGaussian random variables given in Assumption 2.1 is the following,

**Lemma E.1.** Let $Y \in \mathbb{R}$ be subGaussian, then for all $x > 0$,

$$ \mathbb{P}(X > x) \le \exp(-\frac{x^2}{2}), \text{ and } \mathbb{P}(X < -x) \le \exp(-\frac{x^2}{2}) . $$

Here is Laurent and Massart inequality, page 1325 of [22].

**Lemma E.2 (Laurent & Massart).** Let $Z \sim \chi_d^2$ a chi-square distribution, where $d \ge 1$ is the degree of freedom, then for any $x > 0$,

$$ \mathbb{P}(Z \ge d + 2\sqrt{dx} + 2x) \le \exp(-x), \text{ and } \mathbb{P}(Z \le d - 2\sqrt{dx}) \le \exp(-x) . $$

We now give the Hanson-Wright inequality for the concentration of scalar products of subGaussian random variables – see [32] for the proof.

**Lemma E.3 (Hanson-Wright inequality).** Let $Y$ be a $d$-dimensional vector in $\mathbb{R}^d$ with independent, centered and 1-subGaussian components. Let $A$ be a $d \times d$ matrix. Then, there exists a constant $c_{HW}$ such that for any $x \ge 0$,

$$ \mathbb{P}(Y^T AY - \mathbb{E}[Y^T AY] > x) \le \exp \left( - \frac{1}{c_{HW}} \left( \frac{x^2}{\|A\|_F^2} \wedge \frac{x}{\|A\|_{op}} \right) \right), $$

where $\|A\|_{op}$ is the operator norm of $A$, $\|A\|_F$ is the Frobenius norm.

We use in this paper the following corollary,
**Corollary E.4.** Let $\nu_1$ and $\nu_2$ be two probability distribution, with respective expectations $\mu_1$ and $\mu_2$. We assume that there exists $\Sigma_1$ and $\Sigma_2$ two symmetric $d \times d$ matrices such that, for $a = 1, 2$, under $\nu_a$, $E = \Sigma_a^{-1/2}[X - \mu_a]$ is a vector with independent subGaussian random variables. Assume also that $\|\Sigma_1\|_{op} \le \sigma^2$ and $\|\Sigma_2\|_{op} \le \sigma^2$.

Let $m_1 \in \mathbb{N}^*$ and $m_2 \in \mathbb{N}^*$ be two integers. Consider $X_{1,1}, \dots, X_{1,n_1}$ be i.i.d variables distributed as $\nu_1$, and $X_{2,1}, \dots, X_{2,n_2}$ i.i.d variables distributed as $\nu_2$, independent of the observations of $a_2$.

If $\epsilon_1 := \frac{\sqrt{n_1}}{\sigma} \left( \frac{1}{n_1} \sum_{i=1}^{n_1} X_{1,i} - \mu_1 \right)$, and $\epsilon_2 := \frac{\sqrt{n_2}}{\sigma} \left( \frac{1}{n_2} \sum_{i=1}^{n_2} X_{2,i} - \mu_2 \right)$, then, for any $x \ge 1$,

$$ \mathbb{P}(\langle \epsilon_1, \epsilon_2 \rangle > x) \le \exp \left( -\frac{2}{c_{HW}} \left( \frac{x^2}{d} \vee x \right) \right). $$

Similarly, for any $x > 0$, we have

$$ \mathbb{P} \left( \langle \epsilon_1, \epsilon_2 \rangle > \frac{c_{HW}}{2} x \vee \sqrt{\frac{c_{HW}}{2}} dx \right) \le \exp(-x) . $$

**Proof.** Let $a = 1, 2$. We specify the rotation $\Sigma_a$ in the expression of $\epsilon_a$,

$$ \epsilon_a = \frac{\sqrt{n_a}}{\sigma} \left( \frac{1}{n_a} \sum_{i=1}^{n_a} X_{a,i} - \mu_a \right) = \frac{1}{\sigma} \Sigma_a^{1/2} \frac{1}{\sqrt{N}} \sum_{t=1}^{n_a} \Sigma_a^{-1/2} [X_{a,i} - \mu_a] . $$

Now, by assumption on the distribution $\nu_a$, for all $i \in [n_a]$, the vector $\Sigma_a^{-1/2}[X_{a,i} - \mu_a]$ has independent and subGaussian entries. By independence of the random variables $(X_{a,1}, \dots, X_{a,n_a})$, the vector $\frac{1}{\sqrt{N}} \sum_{t=1}^{n_a} \Sigma_a^{-1/2}[X_{a,i} - \mu_a]$ has independent entries. By independence and using the definition of subGaussian variables given in Assumption 2.1, $Y_a := \frac{1}{\sqrt{N}} \sum_{t=1}^{n_a} \Sigma_a^{-1/2}[X_{a,i} - \mu_a]$ is composed of independent and subGaussian entries. It holds then that:

$$ \langle \epsilon_1, \epsilon_2 \rangle = Y_1^T \frac{\Sigma_1^{1/2} \Sigma_2^{1/2}}{\sigma^2} Y_2 = \begin{bmatrix} Y_1 \\ Y_2 \end{bmatrix}^T S \begin{bmatrix} Y_1 \\ Y_2 \end{bmatrix}, $$

where the matrix $S := \frac{1}{2} \begin{bmatrix} 0 & \frac{\Sigma_1^{1/2} \Sigma_2^{1/2}}{\sigma^2} \\ \frac{\Sigma_1^{1/2} \Sigma_2^{1/2}}{\sigma^2} & 0 \end{bmatrix}$ is a $2d \times 2d$ matrix. We can then apply Lemma E.3, noticing that $\mathbb{E}[\langle \epsilon_1, \epsilon_2 \rangle] = 0$, $\|S\|_{op} = \|\Sigma_1^{1/2} \Sigma_2^{1/2} \frac{1}{\sigma^2} \|_{op}/2 \le 1/2$ and $\|S\|_F^2 \le d/2$. $\square$

<figure><img src="image_2.png" /></figure>
**Corollary E.4.** Let $\nu_1$ and $\nu_2$ be two probability distribution, with respective expectations $\mu_1$ and $\mu_2$. We assume that there exists $\Sigma_1$ and $\Sigma_2$ two symmetric $d \times d$ matrices such that, for $a = 1, 2$, under $\nu_a$, $E = \Sigma_a^{-1/2}[X - \mu_a]$ is a vector with independent subGaussian random variables. Assume also that $\|\Sigma_1\|_{op} \le \sigma^2$ and $\|\Sigma_2\|_{op} \le \sigma^2$.

Let $m_1 \in \mathbb{N}^*$ and $m_2 \in \mathbb{N}^*$ be two integers. Consider $X_{1,1}, \dots, X_{1,n_1}$ be i.i.d variables distributed as $\nu_1$, and $X_{2,1}, \dots, X_{2,n_2}$ i.i.d variables distributed as $\nu_2$, independent of the observations of $a_2$.

If $\epsilon_1 := \frac{\sqrt{n_1}}{\sigma} \left( \frac{1}{n_1} \sum_{i=1}^{n_1} X_{1,i} - \mu_1 \right)$, and $\epsilon_2 := \frac{\sqrt{n_2}}{\sigma} \left( \frac{1}{n_2} \sum_{i=1}^{n_2} X_{2,i} - \mu_2 \right)$, then, for any $x \ge 1$,

$$ \mathbb{P}(\langle \epsilon_1, \epsilon_2 \rangle > x) \le \exp\left(-\frac{2}{c_{HW}}\left(\frac{x^2}{d} \lor x\right)\right). $$

Similarly, for any $x > 0$, we have

$$ \mathbb{P} \left( \langle \epsilon_1, \epsilon_2 \rangle > \frac{c_{HW}}{2} x \lor \sqrt{\frac{c_{HW}}{2}} dx \right) \le \exp(-x) . $$

**Proof.** Let $a = 1, 2$. We specify the rotation $\Sigma_a$ in the expression of $\epsilon_a$,

$$ \epsilon_a = \frac{\sqrt{n_a}}{\sigma} \left( \frac{1}{n_a} \sum_{i=1}^{n_a} X_{a,i} - \mu_a \right) = \frac{1}{\sigma} \Sigma_a^{1/2} \frac{1}{\sqrt{N}} \sum_{t=1}^{n_a} \Sigma_a^{-1/2} [X_{a,t} - \mu_a] . $$

Now, by assumption on the distribution $\nu_a$, for all $i \in [n_a]$, the vector $\Sigma_a^{-1/2}[X_{a,i} - \mu_a]$ has independent and subGaussian entries. By independence of the random variables $(X_{a,1}, \dots, X_{a,n_a})$, the vector $\frac{1}{\sqrt{N}} \sum_{t=1}^{n_a} \Sigma_a^{-1/2}[X_{a,t} - \mu_a]$ has independent entries. By independence and using the definition of subGaussian variables given in Assumption 2.1, $Y_a := \frac{1}{\sqrt{N}} \sum_{t=1}^{n_a} \Sigma_a^{-1/2}[X_{a,t} - \mu_a]$ is composed of independent and subGaussian entries. It holds then that:

$$ \langle \epsilon_1, \epsilon_2 \rangle = Y_1^T \frac{\Sigma_1^{1/2} \Sigma_2^{1/2}}{\sigma^2} Y_2 = \begin{bmatrix} Y_1 \\ Y_2 \end{bmatrix}^T S \begin{bmatrix} Y_1 \\ Y_2 \end{bmatrix}, $$

where the matrix $S := \frac{1}{2} \begin{bmatrix} 0 & \frac{\Sigma_1^{1/2} \Sigma_2^{1/2}}{\sigma^2} \\ \frac{\Sigma_1^{1/2} \Sigma_2^{1/2}}{\sigma^2} & 0 \end{bmatrix}$ is a $2d \times 2d$ matrix. We can then apply Lemma E.3, noticing that $\mathbb{E}[\langle \epsilon_1, \epsilon_2 \rangle] = 0$, $\|S\|_{op} = \|\Sigma_1^{1/2} \Sigma_2^{1/2} \frac{1}{\sigma^2} \|_{op}/2 \le 1/2$ and $\|S\|_F^2 \le d/2$. $\square$

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