the strategy by their values in Ext($\mathcal{P}$),

$$ \mathcal{I}_T = \sum_{t=1}^{T} \mathbb{E}_{\underline{\nu}}[\mathrm{KL}(\nu_{A_t}, \nu'_{A_t})] = \sum_{t=1}^{T} \mathbb{E}_{\underline{\nu}}\left[\sum_{a=1}^{K} p_{t,a} \mathrm{KL}(\nu_a, \nu'_a)\right] = \sum_{\underline{p} \in \mathrm{Ext}(\mathcal{P})} \mathbb{E}_{\underline{\nu}}[N_{\underline{p}}(T)] \sum_{a \in [K]} p_a \mathrm{KL}(\nu_a, \nu'_a). \quad (21) $$

Since alternative problems $\underline{\nu}' \in \mathrm{ALT}(\underline{\nu})$ are such that $\nu'_a = \nu_a$ when $p_a^*(\underline{\nu}) > 0$, we finally obtain

$$ \frac{\mathcal{I}_T}{\ln T} = \sum_{\underline{p} \in \mathrm{Ext}(\mathcal{P})} n_{T, \underline{p}} \sum_{\substack{a \in [K] \\ p_a^*(\underline{\nu})=0}} p_a \mathrm{KL}(\nu_a, \nu'_a) = \sum_{\substack{\underline{p} \in \mathrm{Ext}(\mathcal{P}) \\ \underline{p} \neq \underline{p}^*(\underline{\nu})}} n_{T, \underline{p}} \sum_{\substack{a \in [K] \\ p_a^*(\underline{\nu})=0}} p_a \mathrm{KL}(\nu_a, \nu'_a). \quad (22) $$

**Step 2: UFC entails that $\mathcal{I}_T$ is larger than $\ln T$ in the limit.** This step is a mere adaptation of the standard proof technique by Lai & Robbins (1985) and Garivier et al., 2019, with distributions in Ext($\mathcal{P}$) playing the role of arms in the mentioned references. More formally, the crucial observation is that the regret is expressed in (2) in terms of the number of plays of suboptimal distributions in Ext($\mathcal{P}$). Thus, that the strategy is UFC and that $\underline{p}^*(\underline{\nu})$ is, by definition of $\mathrm{ALT}(\underline{\nu})$, suboptimal for $\underline{\nu}'$ entail that, for all $\alpha > 0$,

$$ \forall \underline{p} \neq \underline{p}^*(\underline{\nu}), \quad \mathbb{E}_{\underline{\nu}}[N_{\underline{p}}(T)] = o(T^{\alpha}), \quad \text{as well as} \quad \mathbb{E}_{\underline{\nu}'}[N_{\underline{p}^*(\underline{\nu})}(T)] = o(T^{\alpha}). \quad (23) $$

In particular, for all $\varepsilon > 0$, there exists $T$ large enough so that $\mathbb{E}_{\underline{\nu}'}[N_{\underline{p}^*(\underline{\nu})}(T)] \le T^{\varepsilon}$. We denote by $\mathrm{kl}(p, q) = p \ln(p/q) + (1-p) \ln((1-p)/(1-q))$ the Kullback-Leibler divergence between two Bernoulli distributions with parameters $p$ and $q$. By the data-processing inequality for $[0, 1]$-valued random variables (see Section 2.1 in Garivier et al., 2019) and by the standard inequality $\mathrm{kl}(p, q) \ge p \ln(1/q) - \ln 2$, for all $\varepsilon > 0$, for all $T$ sufficiently large,

$$ \mathcal{I}_T = \mathrm{KL}(\mathbb{P}_{\underline{\nu},T}, \mathbb{P}_{\underline{\nu}',T}) \ge \mathrm{kl}\left(\mathbb{E}_{\underline{\nu}}\left[\frac{N_{\underline{p}^*(\underline{\nu})}(T)}{T}\right], \mathbb{E}_{\underline{\nu}'}\left[\frac{N_{\underline{p}^*(\underline{\nu})}(T)}{T}\right]\right) \ge \underbrace{\mathbb{E}_{\underline{\nu}}\left[\frac{N_{\underline{p}^*(\underline{\nu})}(T)}{T}\right]}_{\rightarrow 1} \ln\left(\frac{T}{\mathbb{E}_{\underline{\nu}'}[N_{\underline{p}^*(\underline{\nu})}(T)]}\right) - \ln 2, $$

where we substituted (23). Letting $T \to \infty$ then $\varepsilon \to 0$, we conclude to

$$ \liminf_{T \to \infty} \frac{\mathcal{I}_T}{\ln T} \ge \sup_{\varepsilon > 0} \liminf_{T \to \infty} \frac{\ln T^{1-\varepsilon}}{\ln T} = 1. \quad (24) $$

**Remark 1.** The specificity of the setting considered appears in these first two steps: we use the UFC property on Ext($\mathcal{P}$) but pure actions $A_t$ are eventually played, so that we could lower bound $\mathcal{I}_T/\ln T$ in (22) by

$$ \sum_{\underline{p} \in \mathrm{Ext}(\mathcal{P})} n_{T, \underline{p}} \sum_{\substack{a \in [K] \\ p_a^*(\underline{\nu})=0}} p_a \mathrm{KL}(\nu_a, \nu'_a) \ge \sum_{\underline{p} \in \mathrm{Ext}(\mathcal{P})} n_{T, \underline{p}} \mathrm{KL}\left(\sum_{a \in [K]} p_a \nu_a, \sum_{a \in [K]} p_a \nu'_a\right), $$

where the inequality holds by convexity of KL and the fact that $\nu'_a = \nu_a$ when $p_a^*(\underline{\nu}) > 0$. The right-hand side above corresponds to the measure of information gained when playing distributions $\underline{p}_t$ without observing the pure actions $A_t$.

**Step 3: Considering cluster points.** We combine (20), (22), and (24) as follows. Let $c$ be a cluster point of the sequence $R_T/\ln T$. If $c = +\infty$ is the only value, then $R_T/\ln T \to +\infty$ and the result is proved; otherwise, take a finite $c$. We denote by $(T_m)_{m \ge 1}$ an increasing sequence such that $R_{T_m}/\ln T_m \to c$. In view of the decomposition (20) and since $n_{T_m, \underline{p}} \ge 0$ and $\Delta(\underline{p}) > 0$ for all $\underline{p} \in \mathrm{Ext}(\mathcal{P})$ with $\underline{p} \neq \underline{p}^*(\underline{\nu})$, all these sequences $n_{T_m, \underline{p}}$ are bounded. Hence, we may extract a subsequence $(T_{m_k})_{k \ge 1}$ from $(T_m)$ such that all sequences $n_{T_{m_k}, \underline{p}}$ converge as $k \to \infty$, to limits denoted by $n_{\underline{p}}$. This only holds for $\underline{p} \in \mathrm{Ext}(\mathcal{P})$ with $\underline{p} \neq \underline{p}^*(\underline{\nu})$, but $c(\mathrm{Ext}(\mathcal{P}), \underline{\nu})$ is only defined based on such vectors.
These convergences yield first, by (20), that

$$ \liminf_{T \to \infty} \frac{R_T}{\ln T} \geq \sum_{\substack{p \in \mathrm{Ext}(\mathcal{P}) \\ \underline{p} \neq \underline{p}^*(\underline{\nu})}} \Delta_{\underline{p}} n_{\underline{p}}. $$

These convergences also entail, together with (22) and (24), and the definition of $\liminf$, that, for any $\underline{\nu}' \in \mathrm{ALT}(\underline{\nu})$,

$$ \sum_{\substack{\underline{p} \in \mathrm{Ext}(\mathcal{P}) \\ \underline{p} \neq \underline{p}^*(\underline{\nu})}} n_{\underline{p}} \sum_{\substack{a \in [K] \\ p_a^*(\underline{\nu}) = 0}} p_a \mathrm{KL}(\nu_a, \nu_a') \geq \liminf_{T \to +\infty} \sum_{\substack{\underline{p} \in \mathrm{Ext}(\mathcal{P}) \\ \underline{p} \neq \underline{p}^*(\underline{\nu})}} n_{T, \underline{p}} \sum_{\substack{a \in [K] \\ p_a^*(\underline{\nu}) = 0}} p_a \mathrm{KL}(\nu_a, \nu_a') \geq 1. $$

Put differently, the limits $n_{\underline{p}}$ defined above, where $\underline{p} \neq \underline{p}^*(\underline{\nu})$, satisfy the constraints in the defining infimum of $c(\mathrm{Ext}(\mathcal{P}), \underline{\nu})$. This concludes the proof.

### C Proof of Proposition 1

The proof builds on the proofs for upper bounds (Appendix A) and lower bounds (Appendix B).

We provide here some general considerations. The Bernoulli distributions are sub-Gaussian with parameter $\sigma^2 = 1/4$. The problem $\underline{\nu} = (\mathrm{Ber}(0), \mathrm{Ber}(1/2), \mathrm{Ber}(0))$ considered has expectations $\underline{\mu} = (0, 1/2, 0)$. The distributions $\underline{p}^{(1)} = (0, 1/2, 1/2)$ and $\underline{p}_{\delta}^{(2)} = (\delta, 0, 1 - \delta)$ obtain respective expected rewards

$$ \langle \underline{p}^{(1)}, \underline{\mu} \rangle = \frac{1}{4} > 0 = \langle \underline{p}_{\delta}^{(2)}, \underline{\mu} \rangle. $$

In particular, given that the polytope $\mathcal{P}_{\delta}$ considered is the segment between $\underline{p}^{(1)}$ and $\underline{p}_{\delta}^{(2)}$, the distribution $\underline{p}^{(1)}$ is the unique optimal distribution in $\mathcal{P}$.

#### C.1 Case $\delta > 1/4$: a $\ln T$ regret is suffered

The setting of Proposition 1 satisfies the assumptions of Lemmas 4 and 5, up to considering the reduction performed in Appendix B.2. It therefore suffices to show that $\mathrm{ALT}(\underline{\nu})$ is not empty.

Given that $\underline{p}^{(1)}$ puts a positive probability mass on arms 2 and 3, alternative problems in $\mathrm{ALT}(\underline{\nu})$ may differ from $\underline{\nu}$ only at arm 1. Given that $\mathrm{KL}(\mathrm{Ber}(0), \mathrm{Ber}(\mu_1)) < +\infty$ if and only if $\mu_1 \in [0, 1)$, we have

$$ \mathrm{ALT}(\underline{\nu}) = \{ \underline{\nu}' = (\mathrm{Ber}(\mu_1'), \mathrm{Ber}(1/2), \mathrm{Ber}(0)) : \mu_1' \in [0, 1) \text{ and } \underline{p}^{(1)} \notin \mathrm{Opt}(\underline{\nu}') \}. $$

Now, denoting by $\underline{\mu}'$ the expectations of $\underline{\nu}'$, and given that $\mathcal{P}_{\delta}$ is a segment, we have that the condition $\underline{p}^{(1)} \notin \mathrm{Opt}(\underline{\nu}')$ is equivalent to

$$ \langle \underline{p}^{(1)}, \underline{\mu}' \rangle = 1/4 < \delta \mu_1' = \langle \underline{p}^{(2)}, \underline{\mu}' \rangle, $$

which is equivalent to $\mu_1' > 1/(4\delta)$. Therefore,

$$ \mathrm{ALT}(\underline{\nu}) = \{ \underline{\nu}' = (\mathrm{Ber}(\mu_1'), \mathrm{Ber}(1/2), \mathrm{Ber}(0)) : 1/(4\delta) < \mu_1' < 1 \}. $$

$\mathrm{ALT}(\underline{\nu})$ is not empty if and only if $\delta > 1/4$, which concludes the proof.

#### C.2 Case $\delta < 1/4$: a bounded regret may be suffered

We use the Box-B algorithm with $u_0 = 1/2$ but make sure that the upper-confidence estimates of the expectations are always smaller than the known bound 1 on rewards, i.e., we replace Step 1 of Box B by

$$ V_a(t-1) = \min\{U_a(t-1), 1\}, \quad \underline{V}(t-1) = (V_1(t), \dots, V_K(t)), \quad \underline{p}_t \in \underset{\underline{p} \in \mathrm{Ext}(\mathcal{P})}{\operatorname{argmax}} \langle \underline{p}, \underline{V}(t-1) \rangle; $$

this is the crucial modification for this proof, see (26) for an explanation why it is handy. All other steps of the Box-B algorithm remain unchanged.
**Step 1: Preparation and adaptation of existing proofs.** We borrow several elements from the proof conducted in Appendix A. We consider the same favorable event $\mathcal{E}(t)$ as therein, but only one event in terms of number of pulls—namely, we are only interested in arm 3:

$$ \mathcal{E}(t) = \left\{ \text{For all } a \in [K], \quad |\mu_a - \hat{\mu}_a(t)| \le \sqrt{\frac{2 \ln t}{\max\{N_a(t), 1\}}} \right\} \quad \text{and} \quad \mathcal{G}(t) = \{N_3(t) \ge t/3\}. $$

Lemma 3 shows that $\mathbb{P}(\mathcal{E}(t)) \le 2Kt^{-3}$ for all $t \ge 2 > e^{1/8}$. Given that $p_{t,3} \ge \min\{p_3^{(1)}, p_{\delta,3}^{(2)}\} = 1/2$ by definition of $\mathcal{P}_\delta$ as a segment and the fact that $\delta < 1/4$, we apply the Hoeffding-Azuma bound (18) as follows: for all $t \ge 1$,

$$ \mathbb{P}(\mathcal{G}(t)) \le \mathbb{P}\left\{N_3(t) - \frac{t}{2} \le -\frac{t}{6}\right\} \le \mathbb{P}\left\{N_3(t) - \sum_{s=1}^{t} p_{s,3} \le -\frac{t}{6}\right\} \le e^{-t/18}. $$

Since $\delta < 1/4$, there exists a threshold $t_0 \ge 2$ such that

$$ \forall t \ge t_0, \quad \delta + 2\sqrt{\frac{6 \ln t}{t}} < \frac{1}{4}. $$

We show below that

$$ \forall t \ge t_0, \quad \text{on } \mathcal{E}(t) \cap \mathcal{G}(t), \quad \langle \underline{p}^{(1)}, \underline{V}(t) \rangle > \langle \underline{p}_{\delta}^{(2)}, \underline{V}(t) \rangle, \quad \text{thus,} \quad \underline{p}_{t+1} = \underline{p}^{(1)}. \quad (25) $$

We recall that $\underline{p}^{(1)}$ is the unique optimal distribution for $\underline{\nu}$ and that the gap of $\underline{p}_{\delta}^{(2)}$ equals $1/4$. The property (25) therefore leads to the following bounded regret bound: for all $T \ge t_0$,

$$ R_T = \frac{1}{4} \sum_{t=1}^{T} \mathbb{P}\{\underline{p}_t = \underline{p}_{\delta}^{(2)}\} \le \frac{t_0}{4} + \frac{1}{4} \sum_{t=t_0}^{+\infty} \mathbb{P}(\overline{\mathcal{E}(t)} \cup \overline{\mathcal{G}(t)}) \le \frac{t_0}{4} + \frac{1}{4} \sum_{t=t_0}^{+\infty} (2Kt^{-3} + e^{-t/18}) = \frac{t_0}{4} + \frac{K}{2} + 5. $$

**Step 2: Proving (25).** By definition, we have, $\langle \underline{p}^{(1)}, \underline{V}(t) \rangle \ge \langle \underline{p}^{(1)}, \underline{\nu} \rangle = 1/4$ on $\mathcal{E}(t)$, and

$$ \text{still on } \mathcal{E}(t), \quad \langle \underline{p}_{\delta}^{(2)}, \underline{V}(t) \rangle = \delta \underbrace{V_1(t)}_{\le 1} + \underbrace{(1-\delta) V_3(t)}_{\le 1} \le \delta + 2\sqrt{\frac{2 \ln t}{\max\{N_3(t), 1\}}}. \quad (26) $$

We crucially used here the boundedness of $V_1(t)$, which we upper bounded by 1. This is fortunate, as arm 1 is only played when the suboptimal distribution $\underline{p}_{\delta}^{(2)}$ is picked, so that $N_1(t)$ could be small and $\mathcal{E}(t)$ would not provide an efficient bound.

Therefore,

$$ \text{on } \mathcal{E}(t) \cap \mathcal{G}(t), \quad \langle \underline{p}^{(1)}, \underline{V}(t) \rangle \ge \frac{1}{4} \quad \text{and} \quad \langle \underline{p}_{\delta}^{(2)}, \underline{V}(t) \rangle \le \delta + 2\sqrt{\frac{6 \ln t}{t}}, $$

so that (25) follows by the definition of $t_0$.

## D Proof of Theorem 3

The proof strategy is similar to that of Theorem 1 with some differences we will highlight: we still work under the favorable event under which all the confidence bounds are correct, and all arms have been picked a linear number of times. Both these events hold with high probability since the probability of picking any arm is lower bounded by some positive constant at all rounds. In that case, the upper confidence vectors $\underline{U}(t)$ are a good estimators of the true mean payoff vector $\underline{\mu}$, and the distributions picked by diversity-preserving UCB get close to the optimal distribution(s). Crucially, we show in Lemma 7 that the differences between
the expected payoffs of the distributions selected by UCB and the optimal payoff depend quadratically on the differences between $\underline{U}(t)$ and $\mu$. This is a consequence of the curvature of the diversity-preserving set $\mathcal{P}_r$. Since the error in estimating $\mu$ by $\underline{U}(t)$ is of order $\sqrt{\ln t/t}$, we obtain per-round regrets of order $\ln t/t$, which sum up to $\ln^2 T$.

We start with two lemmas, providing first a closed-form expression of the optimal distribution (Lemma 6) and second, deducing a quadratic upper bound on the instantaneous regret (Lemma 7).

Denote by $V = \{\underline{\mu} \in \mathbb{R}^d | \mu_1 = \cdots = \mu_K\}$ the subset of expected-payoff vectors with identical components. All strategies get a null regret in bandit problems $\underline{v}$ with payoffs in $V$. We may therefore exclude this case in the rest of the proof. We denote by $\mathbf{1}$ the vector in $\mathbb{R}^K$ with components all equal to 1, and refer to the model of all distributions over $\mathbb{R}$ with a finite first moment as $\mathcal{D}_{\text{all}}$.

**Lemma 6.** Consider $\mathcal{P}_r$ with $r < r_{\text{lim}}$. For any bandit problem $\underline{v}$ in $\mathcal{D}_{\text{all}}$ with means $\underline{\mu} \in \mathbb{R}^K \setminus V$, the optimal distribution in $\mathcal{P}_r$ is unique, only depends on $\underline{\mu}$, and equals

$$ \underline{p}_{\star}(\underline{\mu}) = \frac{1}{K} \mathbf{1} + \frac{r}{\|\underline{\mu} - \mu_{\text{avg}} \mathbf{1}\|} (\underline{\mu} - \mu_{\text{avg}} \mathbf{1}), \quad \text{where} \quad \mu_{\text{avg}} = \frac{1}{K} \sum_{a \in [K]} \mu_a. $$

*Proof.* We denote already by $\underline{p}_{\star}(\underline{\mu})$ the vector defined above and prove that it is the only optimal vector; we do so via elementary arguments. For any $\underline{p}$ in $\mathcal{P}_r$, the difference between the expected payoffs of $\underline{p}$ and $\underline{p}_{\star}(\underline{\mu})$ equals

$$ \begin{aligned} \langle \underline{\mu}, \underline{p}_{\star}(\underline{\mu}) - \underline{p} \rangle &= \langle \underline{\mu}, \frac{1}{K} \mathbf{1} - \underline{p} \rangle + \frac{r}{\|\underline{\mu} - \mu_{\text{avg}} \mathbf{1}\|} \langle \underline{\mu}, \underline{\mu} - \mu_{\text{avg}} \mathbf{1} \rangle \\ &= \langle \underline{\mu} - \mu_{\text{avg}} \mathbf{1}, \frac{1}{K} \mathbf{1} - \underline{p} \rangle + \frac{r}{\|\underline{\mu} - \mu_{\text{avg}} \mathbf{1}\|} \langle \underline{\mu} - \mu_{\text{avg}} \mathbf{1}, \underline{\mu} - \mu_{\text{avg}} \mathbf{1} \rangle \\ &\geq \|\underline{\mu} - \mu_{\text{avg}} \mathbf{1}\| \left( r - \left\| \frac{1}{K} \mathbf{1} - \underline{p} \right\| \right) \geq 0, \end{aligned} \quad (27) $$

where we used, for the second equality, that both vectors $(1/K)\mathbf{1} - \underline{p}$ and $\underline{\mu} - \mu_{\text{avg}}\mathbf{1}$ are orthogonal to $\mathbf{1}$ (as their components sum up to 0), and where, for the final inequality, we applied the the Cauchy-Schwarz inequality:

$$ \langle \underline{\mu} - \mu_{\text{avg}} \mathbf{1}, \frac{1}{K} \mathbf{1} - \underline{p} \rangle \geq - \| \underline{\mu} - \mu_{\text{avg}} \mathbf{1} \| \cdot \| \frac{1}{K} \mathbf{1} - \underline{p} \|. $$

Now, the inequality (27) is an equality if and only if $\underline{\mu} - \mu_{\text{avg}}\mathbf{1}$ and $(1/K)\mathbf{1} - \underline{p}$ are colinear, that is, if there exists $\alpha \in \mathbb{R}$ such that

$$ \underline{p} = \frac{1}{K} \mathbf{1} + \frac{\alpha}{\|\underline{\mu} - \mu_{\text{avg}} \mathbf{1}\|} (\underline{\mu} - \mu_{\text{avg}} \mathbf{1}). $$

By definition of $\mathcal{P}_r$, such a $\underline{p}$ is in $\mathcal{P}_r$ if and only if $|\alpha| \le r$. Therefore, a final equality to 0 is achieved in (27) if and only if $\alpha = r$, i.e., if $\underline{p} = \underline{p}_{\star}(\underline{\mu})$. $\square$

The curvature of the diversity-preserving set $\mathcal{P}_r$ guarantees that the best distribution varies smoothly with the expected payoffs. This in turn implies that the per-round regret of the diversity-preserving UCB strategy depends quadratically on the difference between the upper confidence bound vector $\underline{U}$ and $\underline{\mu}$—at least when $\underline{U}$ is in a neighborhood of $\underline{\mu}$.

**Lemma 7.** Consider $\mathcal{P}_r$ with $r < r_{\text{lim}}$ and use the notation of Lemma 6. For any expected-payoff vector $\underline{\mu} \in \mathbb{R}^d \setminus V$, define the function

$$ \phi_{\underline{\mu}} : \underline{v} \in \mathbb{R}^K \setminus V \mapsto \langle \underline{\mu}, \underline{p}_{\star}(\underline{v}) \rangle. $$

There exist a constant $B_{\underline{\mu}}$ such that

$$ \forall \underline{v} \in \mathbb{R}^K \setminus V, \quad \phi_{\underline{\mu}}(\underline{\mu}) - \phi_{\underline{\mu}}(\underline{v}) \le B_{\underline{\mu}} \|\underline{\mu} - \underline{v}\|^2. $$
With this notation, if $\underline{p}_t$ is the distribution output by the diversity-preserving UCB strategy at round $t$, then the expected per-round regret $r_t$ suffered at time $t$ can be expressed as

$$r_t = \mathbb{E}[\langle \underline{\mu}, \underline{p}_t(\underline{\mu}) - \underline{p}_t \rangle] = \phi_{\underline{\mu}}(\underline{\mu}) - \mathbb{E}[\phi_{\underline{\mu}}(\underline{U}(t-1))]$$

*Proof.* By Lemma 6, $\phi_{\underline{\mu}}$ admits the closed-form expression

$$\phi_{\underline{\mu}}: \underline{v} \in \mathbb{R}^K \setminus V \mapsto \frac{1}{K} \langle \underline{\mu}, \mathbf{1} \rangle + \frac{r}{\|\underline{v} - \underline{v}_{\text{avg}} \mathbf{1}\|} \langle \underline{\mu}, \underline{v} - \underline{v}_{\text{avg}} \mathbf{1} \rangle,$$

showing that $\phi_{\underline{\mu}}$ is $\mathcal{C}^3$ at all points $\underline{v}$ such that $\underline{v} - \underline{v}_{\text{avg}} \mathbf{1} \neq 0$, i.e., over $\mathbb{R}^K \setminus V$. Moreover, by definition of $\underline{p}_t(\underline{\mu})$, the function $\phi_{\underline{\mu}}$ reaches its maximum at $\underline{\mu}$, therefore its differential at $\underline{\mu}$ is null and the Taylor expansion around $\underline{\mu}$ of $\phi_{\underline{\mu}}$ reads

$$\phi_{\underline{\mu}}(\underline{v}) = \phi_{\underline{\mu}}(\underline{\mu}) + \mathcal{O}(\|\underline{v} - \underline{\mu}\|^2).$$

Put differently, the function

$$\psi_{\underline{\mu}}: \underline{v} \in \mathbb{R}^K \setminus V \mapsto \frac{\phi_{\underline{\mu}}(\underline{v}) - \phi_{\underline{\mu}}(\underline{\mu})}{\|\underline{v} - \underline{\mu}\|^2}$$

is bounded in some $\varepsilon$-neighbourhood of $\underline{\mu}$. Outside of this neighborhood, the denominator $\|\underline{v} - \underline{\mu}\|$ is larger than $\varepsilon$ while the numerator is bounded by $2\max_{a \in [K]} \mu_a$. Therefore, $\psi_{\underline{\mu}}$ is bounded over the entire $\mathbb{R}^K \setminus V$. $\square$

We are now equipped to prove Theorem 3. The fact that the model $\mathcal{D}$ is composed of $\sigma^2$-sub-Gaussian distributions is used now. We adapt several arguments already reviewed in Appendix A and therefore provide a concise proof.

*Proof.* Consider the favorable events

$$\mathcal{E}(t) = \left\{ \forall a \in [K], \quad |\mu_a - \hat{\mu}_a(t)| \le \sqrt{\frac{8\sigma^2 \ln t}{\max\{N_a(t), 1\}}} \right\} \quad \text{and} \quad \mathcal{G}'(t) = \left\{ \forall a \in [K], \quad N_a(t) \ge \frac{t(r_{\text{lim}} - r)}{2} \right\}.$$

For any $t$, under $\mathcal{E}(t) \cap \mathcal{G}'(t)$, by Lemma 7,

$$\langle \underline{\mu}, \underline{p}_t(\underline{\mu}) - \underline{p}_t \rangle = \phi_{\underline{\mu}}(\underline{\mu}) - \phi_{\underline{\mu}}(\underline{U}(t-1)) \le B_{\underline{\mu}} \|\underline{\mu} - \underline{U}(t-1)\|^2 \le B_{\underline{\mu}} \sum_{a \in [K]} \frac{16\sigma^2 \ln t}{t(r_{\text{lim}} - r)} = \frac{16KB_{\underline{\mu}}\sigma^2 \ln t}{r_{\text{lim}} - r}.$$

Therefore, taking expectations above,

$$r_t = \mathbb{E}[\langle \underline{\mu}, \underline{p}_t(\underline{\mu}) - \underline{p}_t \rangle] \le \frac{16KB_{\underline{\mu}}\sigma^2 \ln t}{r_{\text{lim}} - r} + \max_{a \in [K]} \mu_a \left( \mathbb{P}(\overline{\mathcal{E}(t)}) + \mathbb{P}(\overline{\mathcal{G}'(t)}) \right). \quad (28)$$

We showed already in (11) in the proof of Theorem 1 that $\sum_{t=1}^{+\infty} \mathbb{P}(\overline{\mathcal{E}(t)}) < +\infty$.

Similarly, as in the argument following (17), introduce the martingales $M_{a,t}$, and note that by (5), we have

$$\sum_{t=1}^{T} \mathbb{P}[\overline{\mathcal{G}'}(t)] \le \sum_{t=1}^{T} \sum_{a \in [K]} \mathbb{P}\{M_{a,t} \le -\frac{t(r_{\text{lim}} - r)}{2}\}.$$

By the Azuma-Hoeffding inequality, the sum above is bounded, cf. (18). Sum (28) over $t$ to conclude. $\square$