**Step 3.** Let $v \in \mathbb{N}$. If one of the two following conditions are true, then for all $t$ such that $T_i(t-1) \ge v$, we have $\Delta_i \ge 2B_i(T_i(t-1), t)$ (i.e. Equation (28) is false).

Condition 1: if $\tilde{\Delta}_{i,\varepsilon} > 12 \frac{\sigma_i^2}{\beta_i} (\sqrt{2} + 2 \frac{\beta_i}{\sigma_i} \bar{\varepsilon})^2$ and $v \le \log(n) \frac{96\beta_i}{9\tilde{\Delta}_{i,\varepsilon}}$.

Condition 2: if $\tilde{\Delta}_{i,\varepsilon} \le 12 \frac{\sigma_i^2}{\beta_i} (\sqrt{2} + 2 \frac{\beta_i}{\sigma_i} \bar{\varepsilon})^2$ and $v \le \frac{50}{9\tilde{\Delta}_{i,\varepsilon}^2} (\sigma_i\sqrt{2} + 2\beta_i\bar{\varepsilon})^2 \log(n)$.

**PROOF:** We search for the smallest value $v \ge s_{lim}(t)$ such that $\Delta_i$ verifies

$$ \Delta_i \ge 2B_i(v,t) = 2 \frac{\sigma_i \sqrt{\frac{2 \log(t^2)}{v}} + \beta_i \frac{\log(t^2)}{3v} + 2\bar{\varepsilon}\beta_i \sqrt{\frac{\log(t^2)}{v}} + 2\beta_i\varepsilon}{\left(p - \sqrt{\frac{\log(t^2)}{2v}} - \varepsilon\right)} + 2b_i. $$

First, we simplify the expression, having that $v \ge s_{lim}(t)$, we have

$$ \frac{\log(t^2)}{2v} \le \frac{128(p - 5\varepsilon)^2}{98(1 + 9/7)^2} \le \frac{(p - \varepsilon)^2}{4}, $$

hence we simplify to

$$ \Delta_i \ge \frac{4}{(p - \varepsilon)} \left( \sigma_i \sqrt{\frac{2 \log(t^2)}{v}} + \beta_i \frac{\log(t^2)}{3v} + 2\beta_i \bar{\varepsilon} \sqrt{\frac{\log(t^2)}{v}} + 2\beta_i \varepsilon \right) + 2b_i $$

let us denote $\tilde{\Delta}_{i,\varepsilon} = (\Delta_i - 2b_i)(p - \varepsilon) - 8\beta_i\varepsilon$, we are searching for $v$ such that

$$ \beta_i \frac{\log(t^2)}{3v} + \sqrt{\frac{\log(t^2)}{v}} (\sigma_i \sqrt{2} + 2\beta_i \bar{\varepsilon}) - \frac{\tilde{\Delta}_{i,\varepsilon}}{4} \le 0 $$

This is a second order polynomial in $\sqrt{\log(t^2)/v}$.

If $\tilde{\Delta}_{i,\varepsilon} > 0$, then the smallest $v > 0$ is

$$ \sqrt{\frac{\log(t^2)}{v}} = \frac{3}{2\beta_i} \left( - (\sigma_i \sqrt{2} + 2\bar{\varepsilon}\beta_i) + \sqrt{\left(\sigma_i \sqrt{2} + 2\beta_i\bar{\varepsilon}\right)^2 + \frac{\tilde{\Delta}_{i,\varepsilon}\beta_i}{3}} \right). $$

**First setting:** if $\tilde{\Delta}_{i,\varepsilon} > 12 \frac{\sigma_i^2}{\beta_i} (\sqrt{2} + 2 \frac{\beta_i}{\sigma_i} \bar{\varepsilon})^2$,

In that case, we have

$$ \sqrt{\frac{\log(t^2)}{v}} \ge \frac{3}{2\beta_i} \left( - (\sigma_i \sqrt{2} + 2\beta_i \bar{\varepsilon}) + \sqrt{\frac{\beta_i \tilde{\Delta}_{i,\varepsilon}}{3}} \right) \ge \frac{3}{2\beta_i} \sqrt{\frac{\beta_i \tilde{\Delta}_{i,\varepsilon}}{12}} = \sqrt{\frac{9 \tilde{\Delta}_{i,\varepsilon}}{48 \beta_i}} $$

Hence, $v \le \log(t) \frac{96\beta_i}{9\tilde{\Delta}_{i,\varepsilon}}$.

**Second setting:** if $\tilde{\Delta}_{i,\varepsilon} \le 12 \frac{\sigma_i^2}{\beta_i} (\sqrt{2} + 2 \frac{\beta_i}{\sigma_i} \bar{\varepsilon})^2$, then we use Lemma 9, using that

$$ \frac{\tilde{\Delta}_{i,\varepsilon}\beta_i}{3(\sigma_i\sqrt{2} + 2\beta_i\bar{\varepsilon})^2} \le 4 $$

and the fact that $\frac{\sqrt{1+4-1}}{4} \ge \frac{3}{10}$, we get,

$$ \sqrt{\frac{\log(t^2)}{v}} \ge \frac{3\tilde{\Delta}_{i,\varepsilon}}{5(\sigma_i\sqrt{2} + 2\beta_i\bar{\varepsilon})} $$
**Step 3.** Let $v \in \mathbb{N}$. If one of the two following conditions are true, then for all $t$ such that $T_i(t-1) \ge v$, we have $\Delta_i \ge 2B_i(T_i(t-1), t)$ (i.e. Equation (28) is false).

Condition 1: if $\tilde{\Delta}_{i,\varepsilon} > 12 \frac{\sigma_i^2}{\beta_i} (\sqrt{2} + 2 \frac{\beta_i}{\sigma_i} \bar{\varepsilon})^2$ and $v \le \log(n) \frac{96\beta_i}{9\tilde{\Delta}_{i,\varepsilon}}$.

Condition 2: if $\tilde{\Delta}_{i,\varepsilon} \le 12 \frac{\sigma_i^2}{\beta_i} (\sqrt{2} + 2 \frac{\beta_i}{\sigma_i} \bar{\varepsilon})^2$ and $v \le \frac{50}{9\tilde{\Delta}_{i,\varepsilon}^2} (\sigma_i \sqrt{2} + 2\beta_i \bar{\varepsilon})^2 \log(n)$.

**PROOF:** We search for the smallest value $v \ge s_{lim}(t)$ such that $\Delta_i$ verifies

$$ \Delta_i \ge 2B_i(v,t) = 2 \frac{\sigma_i \sqrt{\frac{2 \log(t^2)}{v}} + \beta_i \frac{\log(t^2)}{3v} + 2\bar{\varepsilon}\beta_i \sqrt{\frac{\log(t^2)}{v}} + 2\beta_i\varepsilon}{\left(p - \sqrt{\frac{\log(t^2)}{2v}} - \varepsilon\right)} + 2b_i. $$

First, we simplify the expression, having that $v \ge s_{lim}(t)$, we have

$$ \frac{\log(t^2)}{2v} \le \frac{128(p - 5\varepsilon)^2}{98(1 + 9/7)^2} \le \frac{(p - \varepsilon)^2}{4}, $$

hence we simplify to

$$ \Delta_i \ge \frac{4}{(p - \varepsilon)} \left( \sigma_i \sqrt{\frac{2 \log(t^2)}{v}} + \beta_i \frac{\log(t^2)}{3v} + 2\beta_i \bar{\varepsilon} \sqrt{\frac{\log(t^2)}{v}} + 2\beta_i \varepsilon \right) + 2b_i $$

let us denote $\tilde{\Delta}_{i,\varepsilon} = (\Delta_i - 2b_i)(p - \varepsilon) - 8\beta_i\varepsilon$, we are searching for $v$ such that

$$ \beta_i \frac{\log(t^2)}{3v} + \sqrt{\frac{\log(t^2)}{v}} (\sigma_i \sqrt{2} + 2\beta_i \bar{\varepsilon}) - \frac{\tilde{\Delta}_{i,\varepsilon}}{4} \le 0 $$

This is a second order polynomial in $\sqrt{\log(t^2)/v}$.

If $\tilde{\Delta}_{i,\varepsilon} > 0$, then the smallest $v > 0$ is

$$ \sqrt{\frac{\log(t^2)}{v}} = \frac{3}{2\beta_i} \left( - (\sigma_i \sqrt{2} + 2\bar{\varepsilon}\beta_i) + \sqrt{\left(\sigma_i \sqrt{2} + 2\beta_i\bar{\varepsilon}\right)^2 + \frac{\tilde{\Delta}_{i,\varepsilon}\beta_i}{3}} \right). $$

**First setting:** if $\tilde{\Delta}_{i,\varepsilon} > 12 \frac{\sigma_i^2}{\beta_i} (\sqrt{2} + 2 \frac{\beta_i}{\sigma_i} \bar{\varepsilon})^2$,

In that case, we have

$$ \sqrt{\frac{\log(t^2)}{v}} \ge \frac{3}{2\beta_i} \left( - (\sigma_i \sqrt{2} + 2\beta_i \bar{\varepsilon}) + \sqrt{\frac{\beta_i \tilde{\Delta}_{i,\varepsilon}}{3}} \right) \ge \frac{3}{2\beta_i} \sqrt{\frac{\beta_i \tilde{\Delta}_{i,\varepsilon}}{12}} = \sqrt{\frac{9 \tilde{\Delta}_{i,\varepsilon}}{48 \beta_i}} $$

Hence, $v \le \log(t) \frac{96\beta_i}{9\tilde{\Delta}_{i,\varepsilon}}$.

**Second setting:** if $\tilde{\Delta}_{i,\varepsilon} \le 12 \frac{\sigma_i^2}{\beta_i} (\sqrt{2} + 2 \frac{\beta_i}{\sigma_i} \bar{\varepsilon})^2$, then we use Lemma 9, using that

$$ \frac{\tilde{\Delta}_{i,\varepsilon}\beta_i}{3(\sigma_i\sqrt{2} + 2\beta_i\bar{\varepsilon})^2} \le 4 $$

and the fact that $\frac{\sqrt{1+4-1}}{4} \ge \frac{3}{10}$, we get,

$$ \sqrt{\frac{\log(t^2)}{v}} \ge \frac{3\tilde{\Delta}_{i,\varepsilon}}{5(\sigma_i\sqrt{2} + 2\beta_i\bar{\varepsilon})} $$
Hence,

$$v \le \frac{50}{9\tilde{\Delta}_{i,\varepsilon}^2} \left(\sigma_i\sqrt{2} + 2\beta_i\bar{\varepsilon}\right)^2 \log(t).$$

**Step 4.** Using All the previous steps, we prove the theorem. PROOF: We have

$$\begin{aligned}
\mathbb{E}[T_i(t)] &= \mathbb{E}\left[\sum_{t=1}^{t} \mathbf{1}\{A_t = i\}\right] \\
&\le \left[\max(v, s_{lim}(t))\right] + \mathbb{E}\left[\sum_{t=\max(v, s_{lim}(t)) + 1}^{t} \mathbf{1}\{A_t = i \text{ and (28) is false}\}\right] \\
&\le \left[\max(v, s_{lim}(t))\right] + \mathbb{E}\left[\sum_{t=\max(v, s_{lim}(t)) + 1}^{t} \mathbf{1}\{(26) \text{ or (27) or (29) is true}\}\right] \\
&= \left[\max(v, s_{lim}(t))\right] + \sum_{t=\min(v, s_{lim}(t)) + 1}^{t} \mathbb{P}\{(26) \text{ or (27) is true}\} \\
&\le \left[\max(v, s_{lim}(t))\right] + 2 \sum_{t=\min(v, s_{lim}(t)) + 1}^{t} \frac{5}{t}
\end{aligned}$$

using the harmonic series bound by $\log(t) + 1$, we have

$$\mathbb{E}[T_i(t)] \le \max(v, s_{lim}(t)) + 10(\log(t) + 1)$$

Then, we replace the value of $v$,

**First setting:** $\tilde{\Delta}_{i,\varepsilon} > 12 \frac{\sigma_i^2}{\beta_i} (\sqrt{2} + 2 \frac{\beta_i}{\sigma_i} \bar{\varepsilon})^2$

$$\mathbb{E}[T_i(t)] \le \log(t) \max\left(\frac{96\beta_i}{9\tilde{\Delta}_{i,\varepsilon}}, \frac{4}{(p-5\varepsilon)^2}\left(1 + 2\sqrt{2}\left(\bar{\varepsilon} \vee \frac{9}{14\sqrt{2}}\right)\right)^2\right) + 10(\log(t) + 1)$$

**Second setting:** if $\tilde{\Delta}_{i,\varepsilon} \le 12 \frac{\sigma_i^2}{\beta_i} (\sqrt{2} + 2 \frac{\beta_i}{\sigma_i} \bar{\varepsilon})^2$, then

$$\mathbb{E}[T_i(t)] \le \log(n) \max\left(\frac{50}{9\tilde{\Delta}_{i,\varepsilon}^2} \left(\sigma_i\sqrt{2} + 2\beta_i\bar{\varepsilon}\right)^2, \frac{4}{(p-5\varepsilon)^2} \left(1 + 2\sqrt{2}\left(\bar{\varepsilon} \vee \frac{9}{14\sqrt{2}}\right)\right)^2\right) + 10(\log(t) + 1).$$

This concludes the proof of Theorem 3.
Hence,

$$v \le \frac{50}{9\tilde{\Delta}_{i,\varepsilon}^2} \left( \sigma_i \sqrt{2} + 2\beta_i \bar{\varepsilon} \right)^2 \log(t).$$

**Step 4.** Using All the previous steps, we prove the theorem. PROOF: We have

$$ \begin{aligned} \mathbb{E}[T_i(t)] &= \mathbb{E} \left[ \sum_{t=1}^{t} \mathbf{1}\{A_t = i\} \right] \\ &\le \left[ \max(v, s_{lim}(t)) \right] + \mathbb{E} \left[ \sum_{t=\max(v,s_{lim}(t)) + 1}^{t} \mathbf{1}\{A_t = i \text{ and (28) is false}\} \right] \\ &\le \left[ \max(v, s_{lim}(t)) \right] + \mathbb{E} \left[ \sum_{t=\max(v,s_{lim}(t)) + 1}^{t} \mathbf{1}\{(26) \text{ or (27) or (29) is true}\} \right] \\ &= \left[ \max(v, s_{lim}(t)) \right] + \sum_{t=\min(v,s_{lim}(t)) + 1}^{t} \mathbb{P}((26) \text{ or (27) is true}) \\ &\le \left[ \max(v, s_{lim}(t)) \right] + 2 \sum_{t=\min(v,s_{lim}(t)) + 1}^{t} \frac{5}{t} \end{aligned} $$

using the harmonic series bound by $\log(t) + 1$, we have

$$\mathbb{E}[T_i(t)] \le \max(v, s_{lim}(t)) + 10(\log(t) + 1)$$

Then, we replace the value of $v$,

**First setting:** $\tilde{\Delta}_{i,\varepsilon} > 12 \frac{\sigma_i^2}{\beta_i} (\sqrt{2} + 2 \frac{\beta_i}{\sigma_i} \bar{\varepsilon})^2$

$$\mathbb{E}[T_i(t)] \le \log(t) \max \left( \frac{96\beta_i}{9\tilde{\Delta}_{i,\varepsilon}}, \frac{4}{(p-5\varepsilon)^2} \left( 1 + 2\sqrt{2} \left( \bar{\varepsilon} \vee \frac{9}{14\sqrt{2}} \right) \right)^2 \right) + 10(\log(t) + 1)$$

**Second setting:** if $\tilde{\Delta}_{i,\varepsilon} \le 12 \frac{\sigma_i^2}{\beta_i} (\sqrt{2} + 2 \frac{\beta_i}{\sigma_i} \bar{\varepsilon})^2$, then

$$\mathbb{E}[T_i(t)] \le \log(n) \max \left( \frac{50}{9\tilde{\Delta}_{i,\varepsilon}^2} \left( \sigma_i \sqrt{2} + 2\beta_i \bar{\varepsilon} \right)^2, \frac{4}{(p-5\varepsilon)^2} \left( 1 + 2\sqrt{2} \left( \bar{\varepsilon} \vee \frac{9}{14\sqrt{2}} \right) \right)^2 \right) + 10(\log(t) + 1).$$

This concludes the proof of Theorem 3.
# B Proof of Technical Lemmas and Corollaries

## B.1 Preliminary lemmas

### B.1.1 Proof of Lemma 1: Regret Decomposition

From Equation (Corrupted regret), we have

$$R_n = \sum_{a=1}^{k} \sum_{t=1}^{n} \mathbb{E} \left[ \left( \max_a \mathbb{E}_{P_a}[X'] - X_t' \right) \mathbf{1}\{A_t = a\} \right]$$

Then, we condition on $A_t$

$$\begin{aligned}
\mathbb{E} \left[ \left( \max_a \mathbb{E}_{P_a}[X'] - X_t' \right) \mathbf{1}\{A_t = a\} \mid A_t \right] &= \mathbf{1}\{A_t = a\} \mathbb{E} \left[ \max_a \mathbb{E}_{P_a}[X'] - X_t' \mid A_t \right] \\
&= \mathbf{1}\{A_t = a\} \left( \max_a \mathbb{E}_{P_a}[X'] - \mu_{A_t} \right) \\
&= \mathbf{1}\{A_t = a\} \left( \max_a \mathbb{E}_{P_a}[X'] - \mu_a \right) = \mathbf{1}\{A_t = a\} \Delta_a
\end{aligned}$$

and this stays true whatever the policy, because the policy at time $t$ use knowledge up to time $t-1$, hence its decision does not depend on $X_t$. Hence, we have

$$R_n(\pi) = \sum_{a=1}^{k} \Delta_a \mathbb{E}_{\pi(\cdot|X_1^n, A_1^n)} [T_a(n)]$$

where $T_a(n)$ is with respect to the randomness of $\pi$, which is to say that we compute $\mathbb{E}[T_i(n)]$ in the corrupted setting and not in the uncorrupted one.

$$R_n = \sum_{a=1}^{k} \Delta_a \mathbb{E}_{\nu_e} [T_a(n)].$$

### B.1.2 Proof of Lemma 3: KL for Student's Distribution

First, we compute the $\chi^2$ divergence between the two laws $f_a$ and $f_0$. We have, for any $a \ge 0$

$$\begin{aligned}
d_{\chi^2}(f_a, f_0) &= \int \frac{(f_a(x) - f_0(x))^2}{f_0(x)} dx \\
&= \frac{\Gamma\left(\frac{d+1}{2}\right)}{\Gamma\left(\frac{d}{2}\right) \sqrt{d\pi}} \int_{\mathbb{R}} \left( \frac{1}{\left(1 + \frac{(x-a)^2}{d}\right)^{\frac{d+1}{2}}} - \frac{1}{\left(1 + \frac{x^2}{d}\right)^{\frac{d+1}{2}}} \right)^2 \left(1 + \frac{x^2}{d}\right)^{\frac{d+1}{2}} dx \\
&= \frac{\Gamma\left(\frac{d+1}{2}\right)}{\Gamma\left(\frac{d}{2}\right) \sqrt{d\pi}} \int_{\mathbb{R}} \frac{\left(\left(1 + \frac{(x-a)^2}{d}\right)^{\frac{d+1}{2}} - \left(1 + \frac{x^2}{d}\right)^{\frac{d+1}{2}}\right)^2}{\left(1 + \frac{(x-a)^2}{d}\right)^{d+1} \left(1 + \frac{x^2}{d}\right)^{\frac{d+1}{2}}} dx \\
&= \frac{\Gamma\left(\frac{d+1}{2}\right)}{\Gamma\left(\frac{d}{2}\right) \sqrt{d\pi}} \left( \int_{\mathbb{R}} \frac{dx}{\left(1 + \frac{x^2}{d}\right)^{\frac{d+1}{2}}} - 2 \int_{\mathbb{R}} \frac{dx}{\left(1 + \frac{(x-a)^2}{d}\right)^{\frac{d+1}{2}}} + \int_{\mathbb{R}} \frac{\left(1 + \frac{x^2}{d}\right)^{\frac{d+1}{2}}}{\left(1 + \frac{(x-a)^2}{d}\right)^{d+1}} dx \right).
\end{aligned}$$

The first two terms are respectively equal to 1 and -2 using the fact that the student distribution integrate to 1. Then, we do the change of variable $y = x - a$ in the last integral to get

$$d_{\chi^2}(f_a, f_0) = \frac{\Gamma\left(\frac{d+1}{2}\right)}{\Gamma\left(\frac{d}{2}\right) \sqrt{d\pi}} \int_{\mathbb{R}} \frac{\left(1 + \frac{(y+a)^2}{d}\right)^{\frac{d+1}{2}}}{\left(1 + \frac{y^2}{d}\right)^{d+1}} dy - 1.$$

this is a polynomial of degree $d$ in the variable $a$. We have the following Lemma proven in Section B.3.4.
# B Proof of Technical Lemmas and Corollaries

## B.1 Preliminary lemmas

### B.1.1 Proof of Lemma 1: Regret Decomposition

From Equation (Corrupted regret), we have

$$R_n = \sum_{a=1}^{k} \sum_{t=1}^{n} \mathbb{E} \left[ \left( \max_a \mathbb{E}_{P_a}[X'] - X'_t \right) \mathbf{1}\{A_t = a\} \right]$$

Then, we condition on $A_t$

$$\begin{aligned}
\mathbb{E} \left[ \left( \max_a \mathbb{E}_{P_a}[X'] - X'_t \right) \mathbf{1}\{A_t = a\} \mid A_t \right] &= \mathbf{1}\{A_t = a\} \mathbb{E} \left[ \max_a \mathbb{E}_{P_a}[X'] - X'_t \mid A_t \right] \\
&= \mathbf{1}\{A_t = a\} \left( \max_a \mathbb{E}_{P_a}[X'] - \mu_{A_t} \right) \\
&= \mathbf{1}\{A_t = a\} \left( \max_a \mathbb{E}_{P_a}[X'] - \mu_a \right) = \mathbf{1}\{A_t = a\} \Delta_a
\end{aligned}$$

and this stays true whatever the policy, because the policy at time $t$ use knowledge up to time $t-1$, hence its decision does not depend on $X_t$. Hence, we have

$$R_n(\pi) = \sum_{a=1}^{k} \Delta_a \mathbb{E}_{\pi(\cdot|X_1^n, A_1^n)} [T_a(n)]$$

where $T_a(n)$ is with respect to the randomness of $\pi$, which is to say that we compute $\mathbb{E}[T_i(n)]$ in the corrupted setting and not in the uncorrupted one.

$$R_n = \sum_{a=1}^{k} \Delta_a \mathbb{E}_{\nu_e} [T_a(n)].$$

### B.1.2 Proof of Lemma 3: KL for Student's Distribution

First, we compute the $\chi^2$ divergence between the two laws $f_a$ and $f_0$. We have, for any $a \ge 0$

$$\begin{aligned}
d_{\chi^2}(f_a, f_0) &= \int \frac{(f_a(x) - f_0(x))^2}{f_0(x)} dx \\
&= \frac{\Gamma\left(\frac{d+1}{2}\right)}{\Gamma\left(\frac{d}{2}\right) \sqrt{d\pi}} \int_{\mathbb{R}} \left( \frac{1}{\left(1 + \frac{(x-a)^2}{d}\right)^{\frac{d+1}{2}}} - \frac{1}{\left(1 + \frac{x^2}{d}\right)^{\frac{d+1}{2}}} \right)^2 \left(1 + \frac{x^2}{d}\right)^{\frac{d+1}{2}} dx \\
&= \frac{\Gamma\left(\frac{d+1}{2}\right)}{\Gamma\left(\frac{d}{2}\right) \sqrt{d\pi}} \int_{\mathbb{R}} \frac{\left(\left(1 + \frac{(x-a)^2}{d}\right)^{\frac{d+1}{2}} - \left(1 + \frac{x^2}{d}\right)^{\frac{d+1}{2}}\right)^2}{\left(1 + \frac{(x-a)^2}{d}\right)^{d+1} \left(1 + \frac{x^2}{d}\right)^{\frac{d+1}{2}}} dx \\
&= \frac{\Gamma\left(\frac{d+1}{2}\right)}{\Gamma\left(\frac{d}{2}\right) \sqrt{d\pi}} \left( \int_{\mathbb{R}} \frac{dx}{\left(1 + \frac{x^2}{d}\right)^{\frac{d+1}{2}}} - 2 \int_{\mathbb{R}} \frac{dx}{\left(1 + \frac{(x-a)^2}{d}\right)^{\frac{d+1}{2}}} + \int_{\mathbb{R}} \frac{\left(1 + \frac{x^2}{d}\right)^{\frac{d+1}{2}}}{\left(1 + \frac{(x-a)^2}{d}\right)^{d+1}} dx \right).
\end{aligned}$$

The first two terms are respectively equal to 1 and -2 using the fact that the student distribution integrate to 1. Then, we do the change of variable $y = x - a$ in the last integral to get

$$d_{\chi^2}(f_a, f_0) = \frac{\Gamma\left(\frac{d+1}{2}\right)}{\Gamma\left(\frac{d}{2}\right) \sqrt{d\pi}} \int_{\mathbb{R}} \frac{\left(1 + \frac{(y+a)^2}{d}\right)^{\frac{d+1}{2}}}{\left(1 + \frac{y^2}{d}\right)^{d+1}} dy - 1.$$

this is a polynomial of degree $d$ in the variable $a$. We have the following Lemma proven in Section B.3.4.
**Lemma 10** For $a \ge 0$ and $d \ge 0$, we have the following algebraic inequality.

$$ \int_{\mathbb{R}} \frac{\left(1 + \frac{(y+a)^2}{d}\right)^{\frac{d+1}{2}}}{\left(1 + \frac{y^2}{d}\right)^{d+1}} dy \le \frac{a^2}{2\sqrt{d}}(d+1)^2 \left(2 + \frac{a}{\sqrt{d}}\right)^{d-1} + \int_{\mathbb{R}} \frac{(1+y^2/d)^{\frac{d+1}{2}}}{\left(1 + \frac{y^2}{d}\right)^{d+1}} dy. $$

Using this lemma, and because we recognize up to a constant the integral of the student distribution on $\mathbb{R}$ in the right-hand side, we have

$$ \begin{aligned} d_{\chi^2}(f_a, f_0) &= \frac{\Gamma\left(\frac{d+1}{2}\right)}{\Gamma\left(\frac{d}{2}\right)\sqrt{d\pi}} \left( \frac{a^2}{2\sqrt{d}}(d+1)^2 \left(2 + \frac{a}{\sqrt{d}}\right)^{d-1} + \int_{\mathbb{R}} \frac{(1+y^2/d)^{\frac{d+1}{2}}}{\left(1 + \frac{y^2}{d}\right)^{d+1}} dy \right) - 1 \\ &\le \frac{\Gamma\left(\frac{d+1}{2}\right)}{\Gamma\left(\frac{d}{2}\right)\sqrt{d\pi}} \frac{a^2}{2\sqrt{d}}(d+1)^2 \left(2 + \frac{a}{\sqrt{d}}\right)^{d-1} \end{aligned} $$

then, use that for any $d \ge 1$, $\Gamma(\frac{d+1}{2}) \le \Gamma(\frac{d}{2})\sqrt{d/2}$ from Wendel (1948), hence

$$ d_{\chi^2}(f_a, f_0) \le \frac{a^2(d+1)^2}{2\sqrt{2d\pi}} \left(2 + \frac{a}{\sqrt{d}}\right)^{d-1} \le \frac{a^2(d+1)^2}{5\sqrt{d}} \left(2 + \frac{a}{\sqrt{d}}\right)^{d-1}, $$

using $2\sqrt{2\pi} \ge 5$. Then, we use the link between KL divergence and $\chi^2$ divergence to get the result.

$$ \begin{aligned} D_{\text{KL}}(f_a, f_0) &\le \log(1 + d_{\chi^2}(f_a, f_0)) \\ &\le \log \left( 1 + \frac{a^2(d+1)^2}{5\sqrt{d}} \left(2 + \frac{a}{\sqrt{d}}\right)^{d-1} \right) \end{aligned} \quad (30) $$

Then, we have,

$$ \log \left( 1 + \frac{a^2(d+1)^2}{5\sqrt{d}} \left( 2 + \frac{a}{\sqrt{d}} \right)^{d-1} \right) \le \begin{cases} \log \left( 1 + 3^{d-1} \frac{(d+1)^2}{5\sqrt{d}} a^2 \right) & \text{if } a < 1 \\ \log \left( 1 + \frac{(d+1)^2}{5\sqrt{d}} a^{d+1} \left( \frac{(d+1)^2}{\sqrt{d}} + \frac{1}{\sqrt{d}} \right)^{d-1} \right) & \text{if } a \ge 1 \end{cases} $$

hence, using that $1 \le 3^{d-1} \frac{(d+1)^2}{d} a^{d+1}$

$$ \log \left( 1 + \frac{a^2(d+1)^2}{d} \left( 2 + \frac{a}{\sqrt{d}} \right)^{d-1} \right) \le \begin{cases} 3^{d-1} \frac{(d+1)^2}{5\sqrt{d}} a^2 & \text{if } a < 1 \\ (d+1) \log(a) + \log \left( 3^d \frac{(d+1)^2}{5\sqrt{d}} \right) & \text{if } a \ge 1. \end{cases} $$

Inject this in Equation (30) to get the result.

### B.1.3 Proof of Lemma 4: KL for Corrupted Bernoulli Distribution

Let $\alpha \in (0, 1/2)$ and denote $\delta_x$ the Dirac distribution in $x$. Define

$$ P_0 = (1 - \alpha)\delta_0 + \alpha\delta_1, $$

$$ P_1 = \alpha\delta_0 + (1 - \alpha)\delta_1, $$

$$ Q_0 = (1 - \varepsilon)(1 - \alpha)\delta_0 + (1 - (1 - \varepsilon)(1 - \alpha))\delta_1, $$

$$ Q_1 = (1 - (1 - \varepsilon)(1 - \alpha))\delta_0 + (1 - \varepsilon)(1 - \alpha)\delta_1. $$

One can check that $Q_0 = (1 - \varepsilon)P_0 + \varepsilon\delta_1$ and $Q_1 = (1 - \varepsilon)P_1 + \varepsilon\delta_0$ and hence $Q_0$ and $Q_1$ are in the $\varepsilon$-corrupted neighborhood of respectively $P_0$ and $P_1$.
**Lemma 10** For $a \ge 0$ and $d \ge 0$, we have the following algebraic inequality.

$$ \int_{\mathbb{R}} \frac{\left(1 + \frac{(y+a)^2}{d}\right)^{\frac{d+1}{2}}}{\left(1 + \frac{y^2}{d}\right)^{d+1}} dy \le \frac{a^2}{2\sqrt{d}}(d+1)^2 \left(2 + \frac{a}{\sqrt{d}}\right)^{d-1} + \int_{\mathbb{R}} \frac{(1+y^2/d)^{\frac{d+1}{2}}}{\left(1 + \frac{y^2}{d}\right)^{d+1}} dy. $$

Using this lemma, and because we recognize up to a constant the integral of the student distribution on $\mathbb{R}$ in the right-hand side, we have

$$ d_{\chi^2}(f_a, f_0) = \frac{\Gamma\left(\frac{d+1}{2}\right)}{\Gamma\left(\frac{d}{2}\right) \sqrt{d\pi}} \left( \frac{a^2}{2\sqrt{d}}(d+1)^2 \left(2 + \frac{a}{\sqrt{d}}\right)^{d-1} + \int_{\mathbb{R}} \frac{(1+y^2/d)^{\frac{d+1}{2}}}{\left(1 + \frac{y^2}{d}\right)^{d+1}} dy \right) - 1 \\ \le \frac{\Gamma\left(\frac{d+1}{2}\right)}{\Gamma\left(\frac{d}{2}\right) \sqrt{d\pi}} \frac{a^2}{2\sqrt{d}}(d+1)^2 \left(2 + \frac{a}{\sqrt{d}}\right)^{d-1} $$

then, use that for any $d \ge 1$, $\Gamma(\frac{d+1}{2}) \le \Gamma(\frac{d}{2})\sqrt{d/2}$ from Wendel (1948), hence

$$ d_{\chi^2}(f_a, f_0) \le \frac{a^2(d+1)^2}{2\sqrt{2d\pi}} \left(2 + \frac{a}{\sqrt{d}}\right)^{d-1} \le \frac{a^2(d+1)^2}{5\sqrt{d}} \left(2 + \frac{a}{\sqrt{d}}\right)^{d-1}, $$

using $2\sqrt{2\pi} \ge 5$. Then, we use the link between KL divergence and $\chi^2$ divergence to get the result.

$$ D_{\text{KL}}(f_a, f_0) \le \log(1 + d_{\chi^2}(f_a, f_0)) \\ \le \log \left( 1 + \frac{a^2(d+1)^2}{5\sqrt{d}} \left(2 + \frac{a}{\sqrt{d}}\right)^{d-1} \right) \quad (30) $$

Then, we have,

$$ \log \left( 1 + \frac{a^2(d+1)^2}{5\sqrt{d}} \left( 2 + \frac{a}{\sqrt{d}} \right)^{d-1} \right) \le \begin{cases} \log \left( 1 + 3^{d-1} \frac{(d+1)^2}{5\sqrt{d}} a^2 \right) & \text{if } a < 1 \\ \log \left( 1 + \frac{(d+1)^2}{5\sqrt{d}} a^{d+1} \left( \frac{(d+1)^2}{\sqrt{d}} + \frac{1}{\sqrt{d}} \right)^{d-1} \right) & \text{if } a \ge 1 \end{cases} $$

hence, using that $1 \le 3^{d-1} \frac{(d+1)^2}{d} a^{d+1}$

$$ \log \left( 1 + \frac{a^2(d+1)^2}{d} \left( 2 + \frac{a}{\sqrt{d}} \right)^{d-1} \right) \le \begin{cases} 3^{d-1} \frac{(d+1)^2}{5\sqrt{d}} a^2 & \text{if } a < 1 \\ (d+1) \log(a) + \log \left( 3^d \frac{(d+1)^2}{5\sqrt{d}} \right) & \text{if } a \ge 1. \end{cases} $$

Inject this in Equation (30) to get the result.

### B.1.3 Proof of Lemma 4: KL for Corrupted Bernoulli Distribution

Let $\alpha \in (0, 1/2)$ and denote $\delta_x$ the Dirac distribution in $x$. Define

$$ \begin{aligned} P_0 &= (1 - \alpha)\delta_0 + \alpha\delta_1, \\ P_1 &= \alpha\delta_0 + (1 - \alpha)\delta_1, \\ Q_0 &= (1 - \varepsilon)(1 - \alpha)\delta_0 + (1 - (1 - \varepsilon)(1 - \alpha))\delta_1, \\ Q_1 &= (1 - (1 - \varepsilon)(1 - \alpha))\delta_0 + (1 - \varepsilon)(1 - \alpha)\delta_1. \end{aligned} $$

One can check that $Q_0 = (1 - \varepsilon)P_0 + \varepsilon\delta_1$ and $Q_1 = (1 - \varepsilon)P_1 + \varepsilon\delta_0$ and hence $Q_0$ and $Q_1$ are in the $\varepsilon$-corrupted neighborhood of respectively $P_0$ and $P_1$.
We have

$$
\begin{align*}
D_{\mathrm{KL}}(Q_0, Q_1) &= \sum_{k \in \{0, c\}} \mathbb{P}_{Q_0}(X=k) \log \left( \frac{\mathbb{P}_{Q_0}(X=k)}{\mathbb{P}_{Q_1}(X=k)} \right) \\
&= (1-\varepsilon)(1-\alpha) \log \left( \frac{(1-\varepsilon)(1-\alpha)}{1-(1-\varepsilon)(1-\alpha)} \right) + (1-(1-\varepsilon)(1-\alpha)) \log \left( \frac{1-(1-\varepsilon)(1-\alpha)}{(1-\varepsilon)(1-\alpha)} \right) \\
&= ((1-\varepsilon)(1-\alpha) - (1-(1-\varepsilon)(1-\alpha))) \log \left( \frac{(1-\varepsilon)(1-\alpha)}{1-(1-\varepsilon)(1-\alpha)} \right) \\
&= (1-2\varepsilon-2\alpha+2\varepsilon\alpha) \log \left( 1 + \frac{1-2\varepsilon-2\alpha+2\varepsilon\alpha}{\varepsilon+\alpha-\varepsilon\alpha} \right)
\end{align*}
$$

Then, note that $\Delta = \mathbb{E}_{P_1}[X] - \mathbb{E}_{P_0}[X] = (1-2\alpha)$ and $\sigma^2 = \mathrm{Var}_{P_0}(X) = \mathrm{Var}_{P_1}(X) = \alpha(1-\alpha)$. Hence, with $\alpha = \frac{1}{2}(1-\Delta)$.

$$D_{\mathrm{KL}}(Q_0, Q_1) = (1 - 2\varepsilon - (1 - \Delta)(1 - \varepsilon)) \log \left( 1 + \frac{1 - 2\varepsilon - (1 - \Delta)(1 - \varepsilon)}{\varepsilon + \frac{1}{2}(1 - \Delta)(1 - \varepsilon)} \right) \quad (31)$$

$$= (\Delta(1 - \varepsilon) - \varepsilon) \log \left( 1 + \frac{\Delta(1 - \varepsilon) - \varepsilon}{\frac{1}{2}(1 + \varepsilon) - \frac{1}{2}\Delta(1 - \varepsilon)} \right) \quad (32)$$

**Uniform bound:** if $\varepsilon > 0$, we have

$$D_{\mathrm{KL}}(Q_0, Q_1) \le (1 - 2\varepsilon) \log \left( 1 + \frac{1 - 2\varepsilon}{\varepsilon} \right).$$

**High distinguishibility regime:** in the setting $2\sigma > \Delta$, we have the bound

$$
\begin{align*}
D_{\mathrm{KL}}(Q_0, Q_1) &\le \left( \frac{\Delta}{2\sigma} (1 - \varepsilon) - \varepsilon \right) \log \left( 1 + 2 \frac{\frac{\Delta}{2\sigma}(1 - \varepsilon) - \varepsilon}{1 - \left( \frac{\Delta}{2\sigma}(1 - \varepsilon) - \varepsilon \right)} \right) \\
&= \left( \frac{\Delta(1 - \varepsilon) - 2\sigma\varepsilon}{2\sigma} \right) \log \left( 1 + 2 \frac{\Delta(1 - \varepsilon) - 2\sigma\varepsilon}{2\sigma - \left( \Delta(1 - \varepsilon) - 2\sigma\varepsilon \right)} \right)
\end{align*}
$$

**Low distinguishibility regime:** if $\Delta \le 2\sigma \frac{\varepsilon}{\sqrt{1-2\varepsilon}}$. Then there exists $\varepsilon' \le \varepsilon$ such that $\Delta = 2\sigma \frac{\varepsilon'}{\sqrt{1-2\varepsilon'}}$ and then, from Equation (31), there exists $Q'_0, Q'_1$ which are $\varepsilon'$-corrupted versions of $P_0$ and $P_1$ such that $KL(Q'_0, Q'_1) = 0$
We have

$$
\begin{align*}
D_{\mathrm{KL}}(Q_0, Q_1) &= \sum_{k \in \{0, c\}} \mathbb{P}_{Q_0}(X=k) \log \left( \frac{\mathbb{P}_{Q_0}(X=k)}{\mathbb{P}_{Q_1}(X=k)} \right) \\
&= (1-\varepsilon)(1-\alpha) \log \left( \frac{(1-\varepsilon)(1-\alpha)}{1-(1-\varepsilon)(1-\alpha)} \right) + (1-(1-\varepsilon)(1-\alpha)) \log \left( \frac{1-(1-\varepsilon)(1-\alpha)}{(1-\varepsilon)(1-\alpha)} \right) \\
&= ((1-\varepsilon)(1-\alpha) - (1-(1-\varepsilon)(1-\alpha))) \log \left( \frac{(1-\varepsilon)(1-\alpha)}{1-(1-\varepsilon)(1-\alpha)} \right) \\
&= (1-2\varepsilon-2\alpha+2\varepsilon\alpha) \log \left( 1 + \frac{1-2\varepsilon-2\alpha+2\varepsilon\alpha}{\varepsilon+\alpha-\varepsilon\alpha} \right)
\end{align*}
$$

Then, note that $\Delta = \mathbb{E}_{P_1}[X] - \mathbb{E}_{P_0}[X] = (1-2\alpha)$ and $\sigma^2 = \mathrm{Var}_{P_0}(X) = \mathrm{Var}_{P_1}(X) = \alpha(1-\alpha)$. Hence, with $\alpha = \frac{1}{2}(1-\Delta)$.

$$
D_{\mathrm{KL}}(Q_0, Q_1) = (1 - 2\varepsilon - (1 - \Delta)(1 - \varepsilon)) \log \left( 1 + \frac{1 - 2\varepsilon - (1 - \Delta)(1 - \varepsilon)}{\varepsilon + \frac{1}{2}(1 - \Delta)(1 - \varepsilon)} \right) \quad (31)
$$

$$
= (\Delta(1 - \varepsilon) - \varepsilon) \log \left( 1 + \frac{\Delta(1 - \varepsilon) - \varepsilon}{\frac{1}{2}(1 + \varepsilon) - \frac{1}{2}\Delta(1 - \varepsilon)} \right) \quad (32)
$$

**Uniform bound:** if $\varepsilon > 0$, we have

$$
D_{\mathrm{KL}}(Q_0, Q_1) \leq (1 - 2\varepsilon) \log \left( 1 + \frac{1 - 2\varepsilon}{\varepsilon} \right).
$$

**High distinguishibility regime:** in the setting $2\sigma > \Delta$, we have the bound

$$
\begin{align*}
D_{\mathrm{KL}}(Q_0, Q_1) &\le \left( \frac{\Delta}{2\sigma} (1-\varepsilon) - \varepsilon \right) \log \left( 1 + 2 \frac{\frac{\Delta}{2\sigma}(1-\varepsilon) - \varepsilon}{1 - \left( \frac{\Delta}{2\sigma}(1-\varepsilon) - \varepsilon \right)} \right) \\
&= \left( \frac{\Delta(1-\varepsilon) - 2\sigma\varepsilon}{2\sigma} \right) \log \left( 1 + 2 \frac{\Delta(1-\varepsilon) - 2\sigma\varepsilon}{2\sigma - (\Delta(1-\varepsilon) - 2\sigma\varepsilon)} \right)
\end{align*}
$$

**Low distinguishibility regime:** if $\Delta \le 2\sigma \frac{\varepsilon}{\sqrt{1-2\varepsilon}}$. Then there exists $\varepsilon' \le \varepsilon$ such that $\Delta = 2\sigma \frac{\varepsilon'}{\sqrt{1-2\varepsilon'}}$ and then, from Equation (31), there exists $Q'_0, Q'_1$ which are $\varepsilon'$-corrupted versions of $P_0$ and $P_1$ such that $KL(Q'_0, Q'_1) = 0$
## B.2 Lemmas for Regret upper bound

### B.2.1 Proof of Corollary 1: Simplified Upper Bound of HuberUCB

Replacing $\beta_i$ by $4\sigma_i$, we have

* If $\tilde{\Delta}_{i,\varepsilon} > 6\sigma_i(1 + 4\sqrt{2\varepsilon})^2$, then

$$ \mathbb{E}[T_i(n)] \le \log(n) \max \left( \frac{128\sigma_i}{3\tilde{\Delta}_{i,\varepsilon}}, \frac{4}{(p-5\varepsilon)^2} \left( 1 + 2\sqrt{2} \left( \bar{\varepsilon} \vee \frac{9}{14\sqrt{2}} \right) \right)^2 \right) + 10(\log(n) + 1) $$

* If $\tilde{\Delta}_{i,\varepsilon} > 6\sigma_i(1 + 4\sqrt{2\varepsilon})^2$, then

$$ \mathbb{E}[T_i(n)] \le \log(n) \max \left( \frac{50\sigma_i^2}{9\tilde{\Delta}_{i,\varepsilon}^2} (\sqrt{2} + 8\bar{\varepsilon})^2, \frac{4}{(p-5\varepsilon)^2} \left( 1 + 2\sqrt{2} \left( \bar{\varepsilon} \vee \frac{9}{14\sqrt{2}} \right) \right)^2 \right) + 10(\log(n) + 1). $$

Then, we use that

$$ \begin{aligned} \left( 1 + 2\sqrt{2} \left( \bar{\varepsilon} \vee \frac{9}{14\sqrt{2}} \right) \right)^2 &\le 2 \left( 1 + \left( 2\sqrt{2} \left( \bar{\varepsilon} \vee \frac{9}{14\sqrt{2}} \right) \right)^2 \right) \\ &= 2 + 8 \left( \bar{\varepsilon}^2 \vee \frac{81}{392} \right) \le 8\bar{\varepsilon}^2 + 2 + \frac{648}{392} \le 8\bar{\varepsilon}^2 + 4 \end{aligned} $$

and that $p - 5\varepsilon \ge 1/4$, to get

* If $\tilde{\Delta}_{i,\varepsilon} > 6\sigma_i(1 + 4\sqrt{2\varepsilon})^2$, then

$$ \begin{aligned} \mathbb{E}[T_i(n)] &\le \log(n) \max \left( \frac{128\sigma_i}{3\tilde{\Delta}_{i,\varepsilon}}, 512\bar{\varepsilon}^2 + 256 \right) + 10(\log(n) + 1) \\ &= \frac{128}{3} \log(n) \max \left( \frac{\sigma_i}{\tilde{\Delta}_{i,\varepsilon}}, 12\bar{\varepsilon}^2 + 6 \right) + 10(\log(n) + 1) \\ &\le 43 \log(n) \max \left( \frac{\sigma_i}{\tilde{\Delta}_{i,\varepsilon}}, 12\bar{\varepsilon}^2 + 6 \right) + 10(\log(n) + 1) \end{aligned} $$

* If $\tilde{\Delta}_{i,\varepsilon} > 6\sigma_i(1 + 4\sqrt{2\varepsilon})^2$, then

$$ \begin{aligned} \mathbb{E}[T_i(n)] &\le \log(n) \max \left( \frac{50\sigma_i^2}{9\tilde{\Delta}_{i,\varepsilon}^2} (\sqrt{2} + 8\bar{\varepsilon})^2, 512\bar{\varepsilon}^2 + 256 \right) + 10(\log(n) + 1) \\ &\le \log(n) \max \left( \frac{100\sigma_i^2}{9\tilde{\Delta}_{i,\varepsilon}^2} (2 + 64\bar{\varepsilon}^2), 512\bar{\varepsilon}^2 + 256 \right) + 10(\log(n) + 1) \\ &\le 23 \log(n) \max \left( \frac{\sigma_i^2}{\tilde{\Delta}_{i,\varepsilon}^2} (1 + 32\bar{\varepsilon}^2), 24\bar{\varepsilon}^2 + 12 \right) + 10(\log(n) + 1) \end{aligned} $$

### B.2.2 Proof of Lemma 6: Regret Upper bound for SeqHuberUCB

In this section we virtually copy the proof of the regret for HuberUCB done in Section A.4 with modified constants and using the crude bound $P_2(s) \ge s/2$ whenever necessary.
## B.2 Lemmas for Regret upper bound

### B.2.1 Proof of Corollary 1: Simplified Upper Bound of HuberUCB

Replacing $\beta_i$ by $4\sigma_i$, we have

* If $\tilde{\Delta}_{i,\varepsilon} > 6\sigma_i(1 + 4\sqrt{2\varepsilon})^2$, then

$$ \mathbb{E}[T_i(n)] \le \log(n) \max \left( \frac{128\sigma_i}{3\tilde{\Delta}_{i,\varepsilon}}, \frac{4}{(p-5\varepsilon)^2} \left( 1 + 2\sqrt{2} \left( \bar{\varepsilon} \vee \frac{9}{14\sqrt{2}} \right) \right)^2 \right) + 10(\log(n) + 1) $$

* If $\tilde{\Delta}_{i,\varepsilon} > 6\sigma_i(1 + 4\sqrt{2\varepsilon})^2$, then

$$ \mathbb{E}[T_i(n)] \le \log(n) \max \left( \frac{50\sigma_i^2}{9\tilde{\Delta}_{i,\varepsilon}^2} (\sqrt{2} + 8\bar{\varepsilon})^2, \frac{4}{(p-5\varepsilon)^2} \left( 1 + 2\sqrt{2} \left( \bar{\varepsilon} \vee \frac{9}{14\sqrt{2}} \right) \right)^2 \right) + 10(\log(n) + 1). $$

Then, we use that

$$ \begin{aligned} \left( 1 + 2\sqrt{2} \left( \bar{\varepsilon} \vee \frac{9}{14\sqrt{2}} \right) \right)^2 &\le 2 \left( 1 + \left( 2\sqrt{2} \left( \bar{\varepsilon} \vee \frac{9}{14\sqrt{2}} \right) \right)^2 \right) \\ &= 2 + 8 \left( \bar{\varepsilon}^2 \vee \frac{81}{392} \right) \le 8\bar{\varepsilon}^2 + 2 + \frac{648}{392} \le 8\bar{\varepsilon}^2 + 4 \end{aligned} $$

and that $p - 5\varepsilon \ge 1/4$, to get

* If $\tilde{\Delta}_{i,\varepsilon} > 6\sigma_i(1 + 4\sqrt{2\varepsilon})^2$, then

$$ \begin{aligned} \mathbb{E}[T_i(n)] &\le \log(n) \max \left( \frac{128\sigma_i}{3\tilde{\Delta}_{i,\varepsilon}}, 512\bar{\varepsilon}^2 + 256 \right) + 10(\log(n) + 1) \\ &= \frac{128}{3} \log(n) \max \left( \frac{\sigma_i}{\tilde{\Delta}_{i,\varepsilon}}, 12\bar{\varepsilon}^2 + 6 \right) + 10(\log(n) + 1) \\ &\le 43 \log(n) \max \left( \frac{\sigma_i}{\tilde{\Delta}_{i,\varepsilon}}, 12\bar{\varepsilon}^2 + 6 \right) + 10(\log(n) + 1) \end{aligned} $$

* If $\tilde{\Delta}_{i,\varepsilon} > 6\sigma_i(1 + 4\sqrt{2\varepsilon})^2$, then

$$ \begin{aligned} \mathbb{E}[T_i(n)] &\le \log(n) \max \left( \frac{50\sigma_i^2}{9\tilde{\Delta}_{i,\varepsilon}^2} (\sqrt{2} + 8\bar{\varepsilon})^2, 512\bar{\varepsilon}^2 + 256 \right) + 10(\log(n) + 1) \\ &\le \log(n) \max \left( \frac{100\sigma_i^2}{9\tilde{\Delta}_{i,\varepsilon}^2} (2 + 64\bar{\varepsilon}^2), 512\bar{\varepsilon}^2 + 256 \right) + 10(\log(n) + 1) \\ &\le 23 \log(n) \max \left( \frac{\sigma_i^2}{\tilde{\Delta}_{i,\varepsilon}^2} (1 + 32\bar{\varepsilon}^2), 24\bar{\varepsilon}^2 + 12 \right) + 10(\log(n) + 1) \end{aligned} $$

### B.2.2 Proof of Lemma 6: Regret Upper bound for SeqHuberUCB

In this section we virtually copy the proof of the regret for HuberUCB done in Section A.4 with modified constants and using the crude bound $P_2(s) \ge s/2$ whenever necessary.
If $A_t = i$ then at least one of the following four inequalities is true:

$$ \widehat{\text{SeqHub}}_{1,T_1(t-1)} + B_1(T_1(t-1),t) \leq \mu_1 \qquad (33) $$

or

$$ \widehat{\text{SeqHub}}_{i,T_i(t-1)} \geq \mu_i + B_i(T_i(t-1),t) \qquad (34) $$

or

$$ \Delta_i < 2B_i(T_i(t-1),t) \qquad (35) $$

or

$$ P_2(T_1(t-1)) < s_{lim}(t) = \frac{98 \log(t)}{128 (p - 5\epsilon)^2} \left( 1 + 2\sqrt{2} \left( \bar{\epsilon} \vee \frac{9}{14\sqrt{2}} \right) \right)^2 \qquad (36) $$

Indeed, if $P_2(T_i(t-1)) < s_{lim}(t)$, then $B_i(T_i(t-1),t) = \infty$ and Inequality (35) is true. On the other hand, if $P_2(T_i(t-1)) \geq s_{lim}(t)$, then we have $B_i(T_i(t-1),t)$ is finite and all four inequalities are false, then,

$$ \begin{aligned} \widehat{\text{SeqHub}}_{1,T_1(t-1)} + B_1(T_1(t-1),t) &> \mu_1 \\ &= \mu_i + \Delta_i \\ &\geq \mu_i + 2B_i(T_i(t-1),n) \\ &\geq \mu_i + 2B_i(T_i(t-1),t) \\ &\geq \widehat{\text{SeqHub}}_{i,T_i(t-1)} + B_i(T_i(t-1),t) \end{aligned} $$

which implies that $A_t \neq i$.

**Step 1.** We have that $\mathbb{P}((33)$ is true) $\leq 14/t$.

PROOF:

Then, we have that,

$$ \begin{aligned} \mathbb{P}(\widehat{\text{SeqHub}}_{1,T_1(t-1)} + B_1(T_1(t-1),t) \leq \mu_1) &\leq \sum_{s=1}^{t} \mathbb{P}(\widehat{\text{SeqHub}}_{1,s} + B_1(s,t) \leq \mu_1) \\ &= \sum_{s=[s_{\text{lim}}(t)]}^{t} \mathbb{P}(\widehat{\text{SeqHub}}_{1,s} - \mu_1 \leq -B_1(s,t)) \end{aligned} $$

Then, use Theorem 4, we get

$$ \begin{aligned} \mathbb{P}(\widehat{\text{SeqHub}}_{1,T_1(t-1)} + B_1(T_1(t-1),t) \leq \mu_1) &\leq \sum_{s=[s_{\text{lim}}(t)]}^{t} 14e^{-\log(t^2)} \\ &\leq \sum_{s=[s_{\text{lim}}(t)]}^{t} \frac{14}{t^2} \leq \frac{14}{t}. \end{aligned} $$

**Step 2.** Similarly, for arm $i$, we have

$$ \mathbb{P}(\widehat{\text{SeqHub}}_{i,T_i(t-1)} \geq \mu_i + B_i(T_i(t-1),t)) \leq \frac{14}{t} $$

PROOF: We have,

$$ \begin{aligned} \mathbb{P}(\widehat{\text{SeqHub}}_{i,T_i(t-1)} \geq \mu_i + B_i(T_i(t-1),t)) &\leq \sum_{s=[s_{\text{lim}}(t)]}^{t} \mathbb{P}(\widehat{\text{SeqHub}}_{i,s} - \mu_i \geq B_i(s,t)) \\ &\leq \sum_{s=[s_{\text{lim}}(t)]}^{t} 14e^{-\log(t^2)} \leq \frac{14}{t}. \end{aligned} $$
If $A_t = i$ then at least one of the following four inequalities is true:

$$ \widehat{\text{SeqHub}}_{1,T_1(t-1)} + B_1(T_1(t-1),t) \leq \mu_1 \qquad (33) $$

or

$$ \widehat{\text{SeqHub}}_{i,T_i(t-1)} \geq \mu_i + B_i(T_i(t-1),t) \qquad (34) $$

or

$$ \Delta_i < 2B_i(T_i(t-1),t) \qquad (35) $$

or

$$ P_2(T_1(t-1)) < s_{lim}(t) = \frac{98 \log(t)}{128 (p - 5\epsilon)^2} \left( 1 + 2\sqrt{2} \left( \bar{\epsilon} \vee \frac{9}{14\sqrt{2}} \right) \right)^2 \qquad (36) $$

Indeed, if $P_2(T_i(t-1)) < s_{lim}(t)$, then $B_i(T_i(t-1),t) = \infty$ and Inequality (35) is true. On the other hand, if $P_2(T_i(t-1)) \geq s_{lim}(t)$, then we have $B_i(T_i(t-1),t)$ is finite and all four inequalities are false, then,

$$ \begin{aligned} \widehat{\text{SeqHub}}_{1,T_1(t-1)} + B_1(T_1(t-1),t) &> \mu_1 \\ &= \mu_i + \Delta_i \\ &\geq \mu_i + 2B_i(T_i(t-1),n) \\ &\geq \mu_i + 2B_i(T_i(t-1),t) \\ &\geq \widehat{\text{SeqHub}}_{i,T_i(t-1)} + B_i(T_i(t-1),t) \end{aligned} $$

which implies that $A_t \neq i$.

**Step 1.** We have that $\mathbb{P}((33)$ is true) $\leq 14/t$.

PROOF:

Then, we have that,

$$ \begin{aligned} \mathbb{P}(\widehat{\text{SeqHub}}_{1,T_1(t-1)} + B_1(T_1(t-1),t) \leq \mu_1) &\leq \sum_{s=1}^{t} \mathbb{P}(\widehat{\text{SeqHub}}_{1,s} + B_1(s,t) \leq \mu_1) \\ &= \sum_{s=[s_{\text{lim}}(t)]}^{t} \mathbb{P}(\widehat{\text{SeqHub}}_{1,s} - \mu_1 \leq -B_1(s,t)) \end{aligned} $$

Then, use Theorem 4, we get

$$ \begin{aligned} \mathbb{P}(\widehat{\text{SeqHub}}_{1,T_1(t-1)} + B_1(T_1(t-1),t) \leq \mu_1) &\leq \sum_{s=[s_{\text{lim}}(t)]}^{t} 14e^{-\log(t^2)} \\ &\leq \sum_{s=[s_{\text{lim}}(t)]}^{t} \frac{14}{t^2} \leq \frac{14}{t}. \end{aligned} $$

**Step 2.** Similarly, for arm $i$, we have

$$ \mathbb{P}(\widehat{\text{SeqHub}}_{i,T_i(t-1)} \geq \mu_i + B_i(T_i(t-1),t)) \leq \frac{14}{t} $$

PROOF: We have,

$$ \begin{aligned} \mathbb{P}(\widehat{\text{SeqHub}}_{i,T_i(t-1)} \geq \mu_i + B_i(T_i(t-1),t)) &\leq \sum_{s=[s_{\text{lim}}(t)]}^{t} \mathbb{P}(\widehat{\text{SeqHub}}_{i,s} - \mu_i \geq B_i(s,t)) \\ &\leq \sum_{s=[s_{\text{lim}}(t)]}^{t} 14e^{-\log(t^2)} \leq \frac{14}{t}. \end{aligned} $$
**Step 3.** Let $v \in \mathbb{N}$. If one of the two following conditions are true, then for all $t$ such that $P_2(T_i(t-1)) \ge v$, we have $\Delta_i \ge 2B_i(T_i(t-1), t)$ (i.e. Equation (35) is false).

Condition 1: if $\tilde{\Delta}_{i,\varepsilon} > 12 \frac{\sigma_i^2}{\beta_i} (\sqrt{2} + 2 \frac{\beta_i}{\sigma_i} \bar{\varepsilon})^2$ and $v \le \log(t) \frac{96\beta_i}{9\tilde{\Delta}_{i,\varepsilon}}$.

Condition 2: if $\tilde{\Delta}_{i,\varepsilon} \le 12 \frac{\sigma_i^2}{\beta_i} (\sqrt{2} + 2 \frac{\beta_i}{\sigma_i} \bar{\varepsilon})^2$ and $v \le \frac{50}{9\tilde{\Delta}_{i,\varepsilon}^2} (\sigma_i \sqrt{2} + 2\beta_i \bar{\varepsilon})^2 \log(t)$.

**PROOF:** We search for the smallest value $v \ge s_{lim}(t)$ such that $\Delta_i$ verifies

$$ \Delta_i \ge 2B_i(v,t) = 2r_v(1/t^2) + 2 \left( \frac{1}{p - \sqrt{\frac{\log(t^2)}{2v} - \varepsilon}} - 1 \right) r_{P_2(v)}(1/t^2) + 2b_i. $$

First, we simplify the expression, having that $v \ge s_{lim}(t)$, we have

$$ \frac{\log(t^2)}{2v} \le \frac{128(p - 5\varepsilon)^2}{98(1 + 9/7)^2} \le \frac{(p - \varepsilon)^2}{4}, $$

hence $r_v(1/t^2) \le \frac{2}{(p-\varepsilon)} \left( \sigma_i \sqrt{\frac{2\log(t^2)}{v}} \right)$ and we simplify the condition to

$$ \begin{aligned} \Delta_i &\ge \frac{4}{(p-\varepsilon)} \left( \sigma_i \sqrt{\frac{2\log(t^2)}{v}} + \beta_i \frac{\log(t^2)}{3v} + 2\beta_i \bar{\varepsilon} \sqrt{\frac{\log(t^2)}{v}} + 2\beta_i \varepsilon \right) \\ &\quad + \frac{4}{p-\varepsilon} \left( \sigma_i \sqrt{\frac{2\log(t^2)}{P_2(v)}} + \beta_i \frac{\log(t^2)}{3P_2(v)} + 2\beta_i \bar{\varepsilon} \sqrt{\frac{\log(t^2)}{P_2(v)}} + 2\beta_i \varepsilon \right) + 2b_i \\ &\ge \frac{12}{(p-\varepsilon)} \left( \sigma_i \sqrt{\frac{2\log(t^2)}{v}} + \beta_i \frac{\log(t^2)}{3v} + 2\beta_i \bar{\varepsilon} \sqrt{\frac{\log(t^2)}{v}} + 2\beta_i \varepsilon \right) + 2b_i \end{aligned} $$

where we used that $P_2(v) \ge v/2$.

Let us denote $\tilde{\Delta}_{i,\varepsilon} = (\Delta_i - 2b_i)(p - \varepsilon) - 24\beta_i\varepsilon$, we are searching for $v$ such that

$$ \beta_i \frac{\log(t^2)}{3v} + \sqrt{\frac{\log(t^2)}{v}} \left( \sigma_i \sqrt{2} + 2\beta_i \bar{\varepsilon} \right) - \frac{\tilde{\Delta}_{i,\varepsilon}}{12} \le 0 $$

This is a second order polynomial in $\sqrt{\log(t^2)/v}$.

If $\tilde{\Delta}_{i,\varepsilon} > 0$, then the smallest $v > 0$ is

$$ \sqrt{\frac{\log(t^2)}{v}} = \frac{3}{2\beta_i} \left( - \left( \sigma_i \sqrt{2} + 2\bar{\varepsilon}\beta_i \right) + \sqrt{\left( \sigma_i \sqrt{2} + 2\beta_i\bar{\varepsilon} \right)^2 + \frac{\tilde{\Delta}_{i,\varepsilon}\beta_i}{9}} \right). $$

**First setting:** if $\tilde{\Delta}_{i,\varepsilon} > 36 \frac{\sigma_i^2}{\beta_i} (\sqrt{2} + 2 \frac{\beta_i}{\sigma_i} \bar{\varepsilon})^2$,

In that case, we have

$$ \sqrt{\frac{\log(t^2)}{v}} \ge \frac{3}{2\beta_i} \left( - \left( \sigma_i \sqrt{2} + 2\beta_i \bar{\varepsilon} \right) + \sqrt{\frac{\beta_i \tilde{\Delta}_{i,\varepsilon}}{9}} \right) \ge \frac{3}{2\beta_i} \sqrt{\frac{\beta_i \tilde{\Delta}_{i,\varepsilon}}{36}} = \sqrt{\frac{\tilde{\Delta}_{i,\varepsilon}}{16\beta_i}} $$

Hence, $v \le \log(t) \frac{32\beta_i}{\tilde{\Delta}_{i,\varepsilon}}$.
**Step 3.** Let $v \in \mathbb{N}$. If one of the two following conditions are true, then for all $t$ such that $P_2(T_i(t-1)) \ge v$, we have $\Delta_i \ge 2B_i(T_i(t-1), t)$ (i.e. Equation (35) is false).

Condition 1: if $\tilde{\Delta}_{i,\varepsilon} > 12 \frac{\sigma_i^2}{\beta_i} (\sqrt{2} + 2 \frac{\beta_i}{\sigma_i} \bar{\varepsilon})^2$ and $v \le \log(t) \frac{96\beta_i}{9\tilde{\Delta}_{i,\varepsilon}}$.

Condition 2: if $\tilde{\Delta}_{i,\varepsilon} \le 12 \frac{\sigma_i^2}{\beta_i} (\sqrt{2} + 2 \frac{\beta_i}{\sigma_i} \bar{\varepsilon})^2$ and $v \le \frac{50}{9\tilde{\Delta}_{i,\varepsilon}^2} (\sigma_i \sqrt{2} + 2\beta_i \bar{\varepsilon})^2 \log(t)$.

**PROOF:** We search for the smallest value $v \ge s_{lim}(t)$ such that $\Delta_i$ verifies

$$ \Delta_i \ge 2B_i(v,t) = 2r_v(1/t^2) + 2 \left( \frac{1}{p - \sqrt{\frac{\log(t^2)}{2v} - \varepsilon}} - 1 \right) r_{P_2(v)}(1/t^2) + 2b_i. $$

First, we simplify the expression, having that $v \ge s_{lim}(t)$, we have

$$ \frac{\log(t^2)}{2v} \le \frac{128(p - 5\varepsilon)^2}{98(1 + 9/7)^2} \le \frac{(p - \varepsilon)^2}{4}, $$

hence $r_v(1/t^2) \le \frac{2}{(p-\varepsilon)} \left( \sigma_i \sqrt{\frac{2\log(t^2)}{v}} \right)$ and we simplify the condition to

$$ \begin{aligned} \Delta_i &\ge \frac{4}{(p-\varepsilon)} \left( \sigma_i \sqrt{\frac{2\log(t^2)}{v}} + \beta_i \frac{\log(t^2)}{3v} + 2\beta_i \bar{\varepsilon} \sqrt{\frac{\log(t^2)}{v}} + 2\beta_i \varepsilon \right) \\ &\quad + \frac{4}{p-\varepsilon} \left( \sigma_i \sqrt{\frac{2\log(t^2)}{P_2(v)}} + \beta_i \frac{\log(t^2)}{3P_2(v)} + 2\beta_i \bar{\varepsilon} \sqrt{\frac{\log(t^2)}{P_2(v)}} + 2\beta_i \varepsilon \right) + 2b_i \\ &\ge \frac{12}{(p-\varepsilon)} \left( \sigma_i \sqrt{\frac{2\log(t^2)}{v}} + \beta_i \frac{\log(t^2)}{3v} + 2\beta_i \bar{\varepsilon} \sqrt{\frac{\log(t^2)}{v}} + 2\beta_i \varepsilon \right) + 2b_i \end{aligned} $$

where we used that $P_2(v) \ge v/2$.

Let us denote $\tilde{\Delta}_{i,\varepsilon} = (\Delta_i - 2b_i)(p - \varepsilon) - 24\beta_i\varepsilon$, we are searching for $v$ such that

$$ \beta_i \frac{\log(t^2)}{3v} + \sqrt{\frac{\log(t^2)}{v}} \left( \sigma_i \sqrt{2} + 2\beta_i \bar{\varepsilon} \right) - \frac{\tilde{\Delta}_{i,\varepsilon}}{12} \le 0 $$

This is a second order polynomial in $\sqrt{\log(t^2)/v}$.

If $\tilde{\Delta}_{i,\varepsilon} > 0$, then the smallest $v > 0$ is

$$ \sqrt{\frac{\log(t^2)}{v}} = \frac{3}{2\beta_i} \left( - \left( \sigma_i \sqrt{2} + 2\bar{\varepsilon}\beta_i \right) + \sqrt{\left( \sigma_i \sqrt{2} + 2\beta_i\bar{\varepsilon} \right)^2 + \frac{\tilde{\Delta}_{i,\varepsilon}\beta_i}{9}} \right). $$

**First setting:** if $\tilde{\Delta}_{i,\varepsilon} > 36 \frac{\sigma_i^2}{\beta_i} (\sqrt{2} + 2 \frac{\beta_i}{\sigma_i} \bar{\varepsilon})^2$,

In that case, we have

$$ \sqrt{\frac{\log(t^2)}{v}} \ge \frac{3}{2\beta_i} \left( - \left( \sigma_i \sqrt{2} + 2\beta_i \bar{\varepsilon} \right) + \sqrt{\frac{\beta_i \tilde{\Delta}_{i,\varepsilon}}{9}} \right) \ge \frac{3}{2\beta_i} \sqrt{\frac{\beta_i \tilde{\Delta}_{i,\varepsilon}}{36}} = \sqrt{\frac{\tilde{\Delta}_{i,\varepsilon}}{16\beta_i}} $$

Hence, $v \le \log(t) \frac{32\beta_i}{\tilde{\Delta}_{i,\varepsilon}}$.
**Second setting:** if $\tilde{\Delta}_{i,\varepsilon} \le 36 \frac{\sigma_i^2}{\beta_i} (\sqrt{2} + 2 \frac{\beta_i}{\sigma_i} \bar{\varepsilon})^2$, then we use Lemma 9, using that

$$ \frac{\tilde{\Delta}_{i,\varepsilon}\beta_i}{9(\sigma_i\sqrt{2} + 2\beta_i\bar{\varepsilon})^2} \le 4 $$

and the fact that $\frac{\sqrt{1+4-1}}{4} \ge \frac{3}{10}$, we get,

$$ \sqrt{\frac{\log(t^2)}{v}} \ge \frac{\tilde{\Delta}_{i,\varepsilon}}{20(\sigma_i\sqrt{2} + 2\beta_i\bar{\varepsilon})} $$

Hence,

$$ v \le \frac{40}{\tilde{\Delta}_{i,\varepsilon}^2} (\sigma_i\sqrt{2} + 2\beta_i\bar{\varepsilon})^2 \log(t). $$

**Step 4.** Using All the previous steps, we prove the theorem.

**PROOF:** We have

$$ \begin{aligned} \mathbb{E}[T_i(t)] &= \mathbb{E} \left[ \sum_{t=1}^{t} \mathbf{1}\{A_t = i\} \right] \\ &\le \left[ \max(v, 2s_{lim}(t)) \right] + \mathbb{E} \left[ \sum_{t=\left[\max(v, 2s_{lim}(t))\right]+1}^{t} \mathbf{1}\{A_t = i \text{ and (35) is false}\} \right] \\ &\le \left[ \max(v, 2s_{lim}(t)) \right] + \mathbb{E} \left[ \sum_{t=\left[\max(v, 2s_{lim}(t))\right]+1}^{t} \mathbf{1}\{(33) \text{ or (34) or (36) is true}\} \right] \\ &= \left[ \max(v, 2s_{lim}(t)) \right] + \sum_{t=\left[\min(v, 2s_{lim}(t))\right]+1}^{t} \mathbb{P}\left((33) \text{ or (34) is true}\right) \\ &\le \left[ \max(v, 2s_{lim}(t)) \right] + 2 \sum_{t=\left[\min(v, 2s_{lim}(t))\right]+1}^{t} \frac{14}{t} \end{aligned} $$

using the harmonic series bound by $\log(t) + 1$, we have

$$ \mathbb{E}[T_i(t)] \le \max(v, 2s_{lim}(t)) + 28(\log(t) + 1) $$

Then, we replace the value of $v$,

**First setting:** $\tilde{\Delta}_{i,\varepsilon} > 36 \frac{\sigma_i^2}{\beta_i} (\sqrt{2} + 2 \frac{\beta_i}{\sigma_i} \bar{\varepsilon})^2$

$$ \mathbb{E}[T_i(t)] \le \log(t) \max \left( \frac{32\beta_i}{\tilde{\Delta}_{i,\varepsilon}}, \frac{8}{(p-5\varepsilon)^2} \left( 1 + 2\sqrt{2} \left( \bar{\varepsilon} \vee \frac{9}{14\sqrt{2}} \right) \right)^2 \right) + 28(\log(t) + 1) $$

**Second setting:** if $\tilde{\Delta}_{i,\varepsilon} \le 36 \frac{\sigma_i^2}{\beta_i} (\sqrt{2} + 2 \frac{\beta_i}{\sigma_i} \bar{\varepsilon})^2$, then

$$ \mathbb{E}[T_i(t)] \le \log(n) \max \left( \frac{40}{\tilde{\Delta}_{i,\varepsilon}^2} (\sigma_i\sqrt{2} + 2\beta_i\bar{\varepsilon})^2, \frac{8}{(p-5\varepsilon)^2} \left( 1 + 2\sqrt{2} \left( \bar{\varepsilon} \vee \frac{9}{14\sqrt{2}} \right) \right)^2 \right) + 28(\log(t) + 1). $$

Finish the proof of the Theorem using the given values for the constants $\beta_i, \varepsilon, p$.
**Second setting:** if $\tilde{\Delta}_{i,\varepsilon} \le 36 \frac{\sigma_i^2}{\beta_i} (\sqrt{2} + 2 \frac{\beta_i}{\sigma_i} \bar{\varepsilon})^2$, then we use Lemma 9, using that

$$ \frac{\tilde{\Delta}_{i,\varepsilon}\beta_i}{9(\sigma_i\sqrt{2} + 2\beta_i\bar{\varepsilon})^2} \le 4 $$

and the fact that $\frac{\sqrt{1+4-1}}{4} \ge \frac{3}{10}$, we get,

$$ \sqrt{\frac{\log(t^2)}{v}} \ge \frac{\tilde{\Delta}_{i,\varepsilon}}{20(\sigma_i\sqrt{2} + 2\beta_i\bar{\varepsilon})} $$

Hence,

$$ v \le \frac{40}{\tilde{\Delta}_{i,\varepsilon}^2} (\sigma_i\sqrt{2} + 2\beta_i\bar{\varepsilon})^2 \log(t). $$

**Step 4.** Using All the previous steps, we prove the theorem.

**PROOF:** We have

$$ \begin{aligned} \mathbb{E}[T_i(t)] &= \mathbb{E} \left[ \sum_{t=1}^{t} \mathbf{1}\{A_t = i\} \right] \\ &\le \left[ \max(v, 2s_{lim}(t)) \right] + \mathbb{E} \left[ \sum_{t=\left[\max(v, 2s_{lim}(t))\right]+1}^{t} \mathbf{1}\{A_t = i \text{ and (35) is false}\} \right] \\ &\le \left[ \max(v, 2s_{lim}(t)) \right] + \mathbb{E} \left[ \sum_{t=\left[\max(v, 2s_{lim}(t))\right]+1}^{t} \mathbf{1}\{(33) \text{ or (34) or (36) is true}\} \right] \\ &= \left[ \max(v, 2s_{lim}(t)) \right] + \sum_{t=\left[\min(v, 2s_{lim}(t))\right]+1}^{t} \mathbb{P}\left((33) \text{ or (34) is true}\right) \\ &\le \left[ \max(v, 2s_{lim}(t)) \right] + 2 \sum_{t=\left[\min(v, 2s_{lim}(t))\right]+1}^{t} \frac{14}{t} \end{aligned} $$

using the harmonic series bound by $\log(t) + 1$, we have

$$ \mathbb{E}[T_i(t)] \le \max(v, 2s_{lim}(t)) + 28(\log(t) + 1) $$

Then, we replace the value of $v$,

**First setting:** $\tilde{\Delta}_{i,\varepsilon} > 36 \frac{\sigma_i^2}{\beta_i} (\sqrt{2} + 2 \frac{\beta_i}{\sigma_i} \bar{\varepsilon})^2$

$$ \mathbb{E}[T_i(t)] \le \log(t) \max \left( \frac{32\beta_i}{\tilde{\Delta}_{i,\varepsilon}}, \frac{8}{(p-5\varepsilon)^2} \left( 1 + 2\sqrt{2} \left( \bar{\varepsilon} \vee \frac{9}{14\sqrt{2}} \right) \right)^2 \right) + 28(\log(t) + 1) $$

**Second setting:** if $\tilde{\Delta}_{i,\varepsilon} \le 36 \frac{\sigma_i^2}{\beta_i} (\sqrt{2} + 2 \frac{\beta_i}{\sigma_i} \bar{\varepsilon})^2$, then

$$ \mathbb{E}[T_i(t)] \le \log(n) \max \left( \frac{40}{\tilde{\Delta}_{i,\varepsilon}^2} (\sigma_i\sqrt{2} + 2\beta_i\bar{\varepsilon})^2, \frac{8}{(p-5\varepsilon)^2} \left( 1 + 2\sqrt{2} \left( \bar{\varepsilon} \vee \frac{9}{14\sqrt{2}} \right) \right)^2 \right) + 28(\log(t) + 1). $$

Finish the proof of the Theorem using the given values for the constants $\beta_i, \varepsilon, p$.
## B.3 Lemmas for concentration of robust estimators

### B.3.1 Proof of Lemma 7: Controlling Variance of Influence of Huber's Estimator

Let $\rho_\beta$ be Huber's loss function, with $\psi_\beta = \rho'_\beta$. We have that for any $x > 0$, $\psi_\beta(x)^2 \le 2\rho_\beta(x)$. Hence,

$$ \mathrm{Var}(\psi_\beta(Y - \mathrm{Hub}_\beta(P))) = \mathbb{E}[\psi_\beta(Y - \mathrm{Hub}_\beta(P))^2] \le 2\mathbb{E}[\rho_\beta(Y - \mathrm{Hub}_\beta(P))] $$

Then, use that by definition of $\mathrm{Hub}_\beta(P)$, $\mathrm{Hub}_\beta(P)$ is a minimizer of $\theta \mapsto \mathbb{E}[\rho_\beta(Y - \theta)]$, hence,

$$ \mathrm{Var}(\psi_\beta(Y - \mathrm{Hub}_\beta(P))) \le 2\mathbb{E}[\rho_\beta(Y - \mathbb{E}[Y])] $$

and finally, use that $\rho_\beta(x) \le x^2/2$ to conclude.

### B.3.2 Proof of Lemma 8: Concentrating Huber's Estimator by Concentrating the Influence

For all $n \in \mathbb{N}^*$, $\lambda > 0$, let

$$ f_n(\lambda) = \frac{\mathrm{sign}(\Delta_n)}{n} \sum_{i=1}^{n} \psi_\beta(X_i - \mathrm{Hub}_\beta(P) - \lambda \mathrm{sign}(\Delta_n)) $$

where $\Delta_n = \mathrm{Hub}_\beta(P) - \mathrm{Hub}_\beta(X_1^n)$.

**Step 1.** For any $\lambda > 0$, $\mathbb{P}(|\Delta_n| \ge \lambda) \le \mathbb{P}(f_n(\lambda) \ge 0)$.

**PROOF:** For all $y \in \mathbb{R}$, let $J_n(y) = \frac{1}{n} \sum_{i=1}^n \rho_\beta(X_i - y)$ we have,

$$ J_n''(y) = \frac{1}{n} \sum_{i=1}^{n} \psi_{\beta}'(X_i - y). $$

In particular, having $f_n(\lambda) = -\mathrm{sign}(\Delta_n)J'(\mathrm{Hub}_\beta(P) + \lambda \mathrm{sign}(\Delta_n))$ if we take the derivative of $f_n$ with respect to $\lambda$, we have the following equation

$$ \begin{aligned} \frac{\partial}{\partial \lambda} f_n(\lambda) &= -\mathrm{sign}(\Delta_n)^2 J_n''(\mathrm{Hub}_\beta(P) + \lambda \mathrm{sign}(\Delta_n)) \\ &\le -\frac{1}{n} \sum_{i=1}^{n} \psi_\beta'(X_i - \mathrm{Hub}_\beta(P) - \lambda \mathrm{sign}(\Delta_n)). \end{aligned} \quad (37) $$

Then, because $\psi'_\beta$ is non-negative, the function $\lambda \mapsto f_n(\lambda)$ is non-increasing. Hence, for all $n \in \mathbb{N}^*$ and $\lambda > 0$,

$$ |\Delta_n| \ge \lambda \Rightarrow f_n(|\Delta_n|) = 0 \le f_n(\lambda), $$

Hence,

$$ \mathbb{P}(|\Delta_n| \ge \lambda) \le \mathbb{P}(f_n(\lambda) \ge 0). \quad (38) $$

**Step 2.** For all $\lambda > 0$,

$$ f_n(\lambda) \le f_n(0) - \lambda \inf_{t \in [0, \lambda]} |f_n'(t)|. $$

**PROOF:** We apply Taylor's inequality to the function $f_n$. As $f_n$ is non-increasing (because its derivative is non-positive, see Equation (37)), we get

$$ f_n(\lambda) \le f_n(0) - \lambda \inf_{t \in [0, \lambda]} |f_n'(t)|. $$
## B.3 Lemmas for concentration of robust estimators

### B.3.1 Proof of Lemma 7: Controlling Variance of Influence of Huber's Estimator

Let $\rho_\beta$ be Huber's loss function, with $\psi_\beta = \rho'_\beta$. We have that for any $x > 0$, $\psi_\beta(x)^2 \le 2\rho_\beta(x)$. Hence,

$$ \mathrm{Var}(\psi_{\beta}(Y - \mathrm{Hub}_{\beta}(P))) = \mathbb{E}[\psi_{\beta}(Y - \mathrm{Hub}_{\beta}(P))^2] \le 2\mathbb{E}[\rho_{\beta}(Y - \mathrm{Hub}_{\beta}(P))] $$

Then, use that by definition of $\mathrm{Hub}_\beta(P)$, $\mathrm{Hub}_\beta(P)$ is a minimizer of $\theta \mapsto \mathbb{E}[\rho_\beta(Y - \theta)]$, hence,

$$ \mathrm{Var}(\psi_{\beta}(Y - \mathrm{Hub}_{\beta}(P))) \le 2\mathbb{E}[\rho_{\beta}(Y - \mathbb{E}[Y])] $$

and finally, use that $\rho_\beta(x) \le x^2/2$ to conclude.

### B.3.2 Proof of Lemma 8: Concentrating Huber's Estimator by Concentrating the Influence

For all $n \in \mathbb{N}^*$, $\lambda > 0$, let

$$ f_n(\lambda) = \frac{\mathrm{sign}(\Delta_n)}{n} \sum_{i=1}^{n} \psi_\beta(X_i - \mathrm{Hub}_\beta(P) - \lambda \mathrm{sign}(\Delta_n)) $$

where $\Delta_n = \mathrm{Hub}_\beta(P) - \mathrm{Hub}_\beta(X_1^n)$.

**Step 1.** For any $\lambda > 0$, $\mathbb{P}(|\Delta_n| \ge \lambda) \le \mathbb{P}(f_n(\lambda) \ge 0)$.

PROOF: For all $y \in \mathbb{R}$, let $J_n(y) = \frac{1}{n} \sum_{i=1}^n \rho_\beta(X_i - y)$ we have,

$$ J_n''(y) = \frac{1}{n} \sum_{i=1}^{n} \psi_{\beta}'(X_i - y). $$

In particular, having $f_n(\lambda) = -\mathrm{sign}(\Delta_n)J'(\mathrm{Hub}_\beta(P) + \lambda \mathrm{sign}(\Delta_n))$ if we take the derivative of $f_n$ with respect to $\lambda$, we have the following equation

$$ \begin{aligned} \frac{\partial}{\partial \lambda} f_n(\lambda) &= -\mathrm{sign}(\Delta_n)^2 J_n''(\mathrm{Hub}_\beta(P) + \lambda \mathrm{sign}(\Delta_n)) \\ &\le -\frac{1}{n} \sum_{i=1}^{n} \psi_\beta'(X_i - \mathrm{Hub}_\beta(P) - \lambda \mathrm{sign}(\Delta_n)). \end{aligned} \quad (37) $$

Then, because $\psi'_\beta$ is non-negative, the function $\lambda \mapsto f_n(\lambda)$ is non-increasing. Hence, for all $n \in \mathbb{N}^*$ and $\lambda > 0$,

$$ |\Delta_n| \ge \lambda \Rightarrow f_n(|\Delta_n|) = 0 \le f_n(\lambda), $$

Hence,

$$ \mathbb{P}(|\Delta_n| \ge \lambda) \le \mathbb{P}(f_n(\lambda) \ge 0). \quad (38) $$

**Step 2.** For all $\lambda > 0$,

$$ f_n(\lambda) \le f_n(0) - \lambda \inf_{t \in [0, \lambda]} |f_n'(t)|. $$

PROOF: We apply Taylor's inequality to the function $f_n$. As $f_n$ is non-increasing (because its derivative is non-positive, see Equation (37)), we get

$$ f_n(\lambda) \le f_n(0) - \lambda \inf_{t \in [0, \lambda]} |f_n'(t)|. $$
**Step 3.** Let $m_n = \mathbb{E}[\inf_{t \in [0, \lambda]} \frac{1}{n} \sum_{i=1}^{n} \psi'_{\beta}(X'_{i} - \text{Hub}_{\beta}(P) - t)]$. With probability larger than $1 - 2e^{-2n\eta^2}$,

$$ \inf_{t \in [0, \lambda]} |f'_{n}(t)| \geq m_n - 2\eta - \varepsilon, $$

PROOF: Write that $X_i = (1 - W_i)Y_i + W_iZ_i$ where $W_1, \dots, W_n$ are i.i.d Bernoulli random variable with mean $\varepsilon$, $Y_1, \dots, Y_n$ are i.i.d $\sim P$ and $Z_1, \dots, Z_n$ are i.i.d with law $H$.

From equation (37),

$$ |f'_{n}(t)| \geq \frac{1}{n} \sum_{i=1}^{n} \psi'_{\beta}(X_{i} - \text{Hub}_{\beta}(P) - t \text{sign}(\Delta)) \\ \geq \frac{1}{n} \sum_{i=1}^{n} \mathbf{1}\{W_{i} = 0\} \psi'_{\beta}(Y_{i} - \text{Hub}_{\beta}(P) - t \text{sign}(\Delta)) \tag{39} $$

$$ + \frac{1}{n} \sum_{i=1}^{n} \mathbf{1}\{W_i = 1\} \psi'_{\beta}(Z_i - \text{Hub}_{\beta}(P) - t \text{sign}(\Delta)) \tag{40} $$

$$ \geq \frac{1}{n} \sum_{i=1}^{n} \psi'_{\beta}(Y_i - \text{Hub}_{\beta}(P) - t \text{sign}(\Delta)) \tag{41} $$

$$ + \frac{1}{n} \sum_{i=1}^{n} \mathbf{1}\{W_i = 1\} (\psi'_{\beta}(Z_i - \text{Hub}_{\beta}(P) - t \text{sign}(\Delta)) - \psi'_{\beta}(W_i - \text{Hub}_{\beta}(P) - t \text{sign}(\Delta))) \tag{42} $$

Hence, because $\psi'_{\beta} \in [0, 1]$, we have

$$ |f'_{n}(t)| \geq \frac{1}{n} \sum_{i=1}^{n} \psi'_{\beta}(Y_{i} - \text{Hub}_{\beta}(P) - t \text{sign}(\Delta)) - \frac{1}{n} \sum_{i=1}^{n} \mathbf{1}\{W_{i} = 1\} \tag{43} $$

The right-hand side depends on the infimum of the mean of $n$ i.i.d random variables in $[0, 1]$. Hence, the function

$$ Z(X_1^n) \mapsto \sup_{t \in [0, \lambda]} \sum_{i=1}^{n} \psi'_{\beta}(X'_{i} - \text{Hub}_{\beta}(P) - t) $$

satisfies, by sub-linearity of the supremum operator and triangular inequality, the bounded difference property, with differences bounded by 1. Hence, by Hoeffding's inequality, we get with probability larger than $1 - e^{-2n\eta^2}$,

$$ \inf_{t \in [0, \lambda]} |f'_{n}(t)| \geq \mathbb{E} \left[ \inf_{t \in [0, \lambda]} \frac{1}{n} \sum_{i=1}^{n} \psi'_{\beta}(X'_{i} - \text{Hub}_{\beta}(P) - t) \right] - \eta - \frac{1}{n} \sum_{i=1}^{n} \mathbf{1}\{W_{i} = 1\} $$

and using Hoeffding's inequality to control $\frac{1}{n} \sum_{i=1}^{n} \mathbf{1}\{W_i = 1\}$, we have with probability larger than $1 - 2e^{-2\eta^2/n}$,

$$ \inf_{t \in [0, \lambda]} |f'_{n}(t)| \geq \mathbb{E} \left[ \inf_{t \in [0, \lambda]} \frac{1}{n} \sum_{i=1}^{n} \psi'_{\beta}(X'_{i} - \text{Hub}_{\beta}(P) - t) \right] - 2\eta - \varepsilon $$

**Step 4.** For $\lambda \in (0, \beta/2)$,

$$ \mathbb{P} ( |\Delta_n| \geq \lambda) \leq \mathbb{P} \left( \left| \frac{1}{n} \sum_{i=1}^{n} \psi_{\beta}(X_i - \text{Hub}_{\beta}(P)) \right| \geq \lambda (m_n - \eta - \varepsilon) \right) + 2e^{-2n\eta^2}. $$
**Step 3.** Let $m_n = \mathbb{E}[\inf_{t \in [0, \lambda]} \frac{1}{n} \sum_{i=1}^{n} \psi'_{\beta}(X'_{i} - \text{Hub}_{\beta}(P) - t)]$. With probability larger than $1 - 2e^{-2n\eta^2}$,

$$ \inf_{t \in [0, \lambda]} |f'_{n}(t)| \geq m_n - 2\eta - \varepsilon, $$

PROOF: Write that $X_i = (1 - W_i)Y_i + W_iZ_i$ where $W_1, \dots, W_n$ are i.i.d Bernoulli random variable with mean $\varepsilon$, $Y_1, \dots, Y_n$ are i.i.d $\sim P$ and $Z_1, \dots, Z_n$ are i.i.d with law $H$.

From equation (37),

$$ |f'_{n}(t)| \geq \frac{1}{n} \sum_{i=1}^{n} \psi'_{\beta}(X_{i} - \text{Hub}_{\beta}(P) - t \text{sign}(\Delta)) \geq \frac{1}{n} \sum_{i=1}^{n} \mathbf{1}\{W_{i} = 0\} \psi'_{\beta}(Y_{i} - \text{Hub}_{\beta}(P) - t \text{sign}(\Delta)) \quad (39) $$

$$ + \frac{1}{n} \sum_{i=1}^{n} \mathbf{1}\{W_i = 1\} \psi'_{\beta}(Z_i - \text{Hub}_{\beta}(P) - t \text{sign}(\Delta)) \quad (40) $$

$$ \geq \frac{1}{n} \sum_{i=1}^{n} \psi'_{\beta}(Y_i - \text{Hub}_{\beta}(P) - t \text{sign}(\Delta)) \quad (41) $$

$$ + \frac{1}{n} \sum_{i=1}^{n} \mathbf{1}\{W_i = 1\} (\psi'_{\beta}(Z_i - \text{Hub}_{\beta}(P) - t \text{sign}(\Delta)) - \psi'_{\beta}(W_i - \text{Hub}_{\beta}(P) - t \text{sign}(\Delta))) \quad (42) $$

Hence, because $\psi'_{\beta} \in [0, 1]$, we have

$$ |f'_{n}(t)| \geq \frac{1}{n} \sum_{i=1}^{n} \psi'_{\beta}(Y_{i} - \text{Hub}_{\beta}(P) - t \text{sign}(\Delta)) - \frac{1}{n} \sum_{i=1}^{n} \mathbf{1}\{W_{i} = 1\} \quad (43) $$

The right-hand side depends on the infimum of the mean of $n$ i.i.d random variables in $[0, 1]$. Hence, the function

$$ Z(X_1^n) \mapsto \sup_{t \in [0, \lambda]} \sum_{i=1}^{n} \psi'_{\beta}(X'_{i} - \text{Hub}_{\beta}(P) - t) $$

satisfies, by sub-linearity of the supremum operator and triangular inequality, the bounded difference property, with differences bounded by 1. Hence, by Hoeffding's inequality, we get with probability larger than $1 - e^{-2n\eta^2}$,

$$ \inf_{t \in [0, \lambda]} |f'_{n}(t)| \geq \mathbb{E} \left[ \inf_{t \in [0, \lambda]} \frac{1}{n} \sum_{i=1}^{n} \psi'_{\beta}(X'_{i} - \text{Hub}_{\beta}(P) - t) \right] - \eta - \frac{1}{n} \sum_{i=1}^{n} \mathbf{1}\{W_{i} = 1\} $$

and using Hoeffding's inequality to control $\frac{1}{n} \sum_{i=1}^{n} \mathbf{1}\{W_i = 1\}$, we have with probability larger than $1 - 2e^{-2\eta^2/n}$,

$$ \inf_{t \in [0, \lambda]} |f'_{n}(t)| \geq \mathbb{E} \left[ \inf_{t \in [0, \lambda]} \frac{1}{n} \sum_{i=1}^{n} \psi'_{\beta}(X'_{i} - \text{Hub}_{\beta}(P) - t) \right] - 2\eta - \varepsilon $$

**Step 4.** For $\lambda \in (0, \beta/2)$,

$$ \mathbb{P} ( |\Delta_n| \geq \lambda) \leq \mathbb{P} \left( \left| \frac{1}{n} \sum_{i=1}^{n} \psi_{\beta}(X_i - \text{Hub}_{\beta}(P)) \right| \geq \lambda (m_n - \eta - \varepsilon) \right) + 2e^{-2n\eta^2}. $$
PROOF: For any $\lambda > 0$, we have

$$ \mathbb{P}(|\Delta_n| \ge \lambda) \le \mathbb{P}(f_n(\lambda) \ge 0) \qquad \text{(from Step 1)} $$

$$ \le 1 - \mathbb{P} \left( f_n(0) - \lambda \inf_{t \in [0, \lambda]} |f'_n(t)| \le 0 \right) \qquad \text{(from Step 2)} $$

$$ \le 1 - \mathbb{P}(f_n(0) \le \lambda(m_n - 2\eta - \varepsilon)) + 2e^{-2n\eta^2} \qquad \text{(from Step 3)} $$

$$ = \mathbb{P}\left(\left|\frac{1}{n}\sum_{i=1}^{n}\psi_{\beta}(X_i - \text{Hub}_{\beta}(P))\right| \ge \lambda(m_n - \eta - \varepsilon)\right) + 2e^{-2n\eta^2}. \qquad (44) $$

**Step 5.** We prove that $m_n \ge p$, and hence

$$ \mathbb{P}(|\Delta_n| \ge \lambda) \le \mathbb{P}\left(\left|\frac{1}{n}\sum_{i=1}^{n}\psi_{\beta}(X_i - \text{Hub}(P))\right| \ge \lambda(p - \eta - \varepsilon)\right) + 2e^{-2n\eta^2} $$

PROOF: For all $\lambda \le \beta/2$,

$$ \begin{aligned} \mathbb{E}\left[\inf_{t \in [0, \lambda]} \frac{1}{n} \sum_{i=1}^{n} \psi_{\beta}'(X_i' - \text{Hub}_{\beta}(P) - t)\right] &= \mathbb{E}\left[\inf_{t \in [0, \lambda]} \frac{1}{n} \sum_{i=1}^{n} \mathbf{1}\{|X_i' - \text{Hub}_{\beta}(P) - t| \le \beta\}\right] \\ &\ge \mathbb{E}\left[\frac{1}{n} \sum_{i=1}^{n} \mathbf{1}\{|X_i' - \text{Hub}_{\beta}(P)| \le \beta - \lambda\}\right] \\ &\ge \mathbb{E}\left[\frac{1}{n} \sum_{i=1}^{n} \mathbf{1}\{|X_i' - \text{Hub}_{\beta}(P)| \le \beta/2\}\right] = p \end{aligned} $$

Then, we plug the bound on $m_n$ found in the previous step in equation (44), we get for any $\eta > 0$ and $\lambda \in (0, \beta/2]$,

$$ \mathbb{P}(|\Delta_n| \ge \lambda) \le \mathbb{P}\left(\left|\frac{1}{n}\sum_{i=1}^{n}\psi_{\beta}(X_i - \text{Hub}_{\beta}(P))\right| \ge \lambda(p - \eta - \varepsilon)\right) + 2e^{-2n\eta^2} $$

### B.3.3 Proof of Lemma 9: Algebra tool for bounding polynomial roots

The solutions of the second order polynomial indicate that $x$ must verify

$$ x \ge \frac{-b + \sqrt{b^2 + 4ac}}{2a} \ge \frac{b}{2a} \left(-1 + \sqrt{1 + \frac{4ac}{b^2}}\right). $$

Then, use that the function $x \mapsto \sqrt{x+1}$ is concave and hence the graph of $x \mapsto \sqrt{x+1}$ is above its chords and we have for any $x \in [0, d]$, $\sqrt{1+x} \ge 1 + x^{\sqrt{d+1}-1}$. Hence,

$$ x \ge \frac{b}{2a} \left( \frac{4ac(\sqrt{d+1}-1)}{db^2} \right) = \frac{2c(\sqrt{d+1}-1)}{db}. $$
PROOF: For any $\lambda > 0$, we have

$$ \mathbb{P}(|\Delta_n| \ge \lambda) \le \mathbb{P}(f_n(\lambda) \ge 0) \qquad \text{(from Step 1)} $$

$$ \le 1 - \mathbb{P} \left( f_n(0) - \lambda \inf_{t \in [0, \lambda]} |f'_n(t)| \le 0 \right) \qquad \text{(from Step 2)} $$

$$ \le 1 - \mathbb{P} (f_n(0) \le \lambda (m_n - 2\eta - \varepsilon)) + 2e^{-2n\eta^2} \qquad \text{(from Step 3)} $$

$$ = \mathbb{P} \left( \left| \frac{1}{n} \sum_{i=1}^{n} \psi_{\beta}(X_i - \text{Hub}_{\beta}(P)) \right| \ge \lambda (m_n - \eta - \varepsilon) \right) + 2e^{-2n\eta^2}. \qquad (44) $$

**Step 5.** We prove that $m_n \ge p$, and hence

$$ \mathbb{P}(|\Delta_n| \ge \lambda) \le \mathbb{P} \left( \left| \frac{1}{n} \sum_{i=1}^{n} \psi_{\beta}(X_i - \text{Hub}(P)) \right| \ge \lambda (p - \eta - \varepsilon) \right) + 2e^{-2n\eta^2} $$

PROOF: For all $\lambda \le \beta/2$,

$$ \begin{aligned} \mathbb{E} \left[ \inf_{t \in [0, \lambda]} \frac{1}{n} \sum_{i=1}^{n} \psi_{\beta}'(X_i' - \text{Hub}_{\beta}(P) - t) \right] &= \mathbb{E} \left[ \inf_{t \in [0, \lambda]} \frac{1}{n} \sum_{i=1}^{n} \mathbf{1}\{|X_i' - \text{Hub}_{\beta}(P) - t| \le \beta\} \right] \\ &\ge \mathbb{E} \left[ \frac{1}{n} \sum_{i=1}^{n} \mathbf{1}\{|X_i' - \text{Hub}_{\beta}(P)| \le \beta - \lambda\} \right] \\ &\ge \mathbb{E} \left[ \frac{1}{n} \sum_{i=1}^{n} \mathbf{1}\{|X_i' - \text{Hub}_{\beta}(P)| \le \beta/2\} \right] = p \end{aligned} $$

Then, we plug the bound on $m_n$ found in the previous step in equation (44), we get for any $\eta > 0$ and $\lambda \in (0, \beta/2]$,

$$ \mathbb{P}(|\Delta_n| \ge \lambda) \le \mathbb{P} \left( \left| \frac{1}{n} \sum_{i=1}^{n} \psi_{\beta}(X_i - \text{Hub}_{\beta}(P)) \right| \ge \lambda (p - \eta - \varepsilon) \right) + 2e^{-2n\eta^2} $$

### B.3.3 Proof of Lemma 9: Algebra tool for bounding polynomial roots

The solutions of the second order polynomial indicate that $x$ must verify

$$ x \ge \frac{-b + \sqrt{b^2 + 4ac}}{2a} \ge \frac{b}{2a} \left( -1 + \sqrt{1 + \frac{4ac}{b^2}} \right). $$

Then, use that the function $x \mapsto \sqrt{x+1}$ is concave and hence the graph of $x \mapsto \sqrt{x+1}$ is above its chords and we have for any $x \in [0, d]$, $\sqrt{1+x} \ge 1+x^{\sqrt{d+1}-1}$. Hence,

$$ x \ge \frac{b}{2a} \left( \frac{4ac(\sqrt{d+1}-1)}{db^2} \right) = \frac{2c(\sqrt{d+1}-1)}{db}. $$
### B.3.4 Proof of Lemma 10: Algebra on Student's distribution

We have,

$$ 
\begin{aligned}
\int_{\mathbb{R}} \frac{\left(1 + \frac{(y+a)^2}{d}\right)^{\frac{d+1}{2}}}{\left(1 + \frac{y^2}{d}\right)^{d+1}} dy &= \int_{\mathbb{R}} \sum_{l=0}^{\frac{d+1}{2}} \binom{\frac{d+1}{2}}{l} \frac{(y+a)^{2l}}{d^l \left(1 + \frac{y^2}{d}\right)^{d+1}} dy \\
&= \int_{\mathbb{R}} \sum_{l=0}^{\frac{d+1}{2}} \sum_{j=0}^{2l} \binom{\frac{d+1}{2}}{l} \binom{2l}{j} \frac{y^j a^{2l-j}}{d^l \left(1 + \frac{y^2}{d}\right)^{d+1}} dy \\
&= \sum_{l=0}^{\frac{d+1}{2}} \sum_{j=0}^{2l} \binom{\frac{d+1}{2}}{l} \binom{2l}{j} \int_{\mathbb{R}} \frac{y^j a^{2l-j}}{d^l \left(1 + \frac{y^2}{d}\right)^{d+1}} dy
\end{aligned}
$$

Remark that the integral is 0 if $j$ is odd. Hence,

$$ \int_{\mathbb{R}} \frac{\left(1 + \frac{(y+a)^2}{d}\right)^{\frac{d+1}{2}}}{\left(1 + \frac{y^2}{d}\right)^{d+1}} dy = \sum_{l=0}^{\frac{d+1}{2}} \sum_{j=1}^{l} \binom{\frac{d+1}{2}}{l} \binom{2l}{2j} \frac{a^{2l-2j}}{d^l} \int_{\mathbb{R}} \frac{y^{2j}}{\left(1 + \frac{y^2}{d}\right)^{d+1}} dy $$

Then, we compute the integrals. By change of variable $u = y/d$, we have

$$ \int_{\mathbb{R}} \frac{y^{2j}}{\left(1 + \frac{y^2}{d}\right)^{d+1}} dy = d^{j+1/2} \int_{\mathbb{R}} \frac{u^{2j}}{(1 + u^2)^{d+1}} du \le 2d^{j+1/2} $$

and for $l = j$,

$$ \sum_{l=0}^{\frac{d+1}{2}} \binom{\frac{d+1}{2}}{l} \frac{1}{d^l} \int_{\mathbb{R}} \frac{y^{2l}}{\left(1 + \frac{y^2}{d}\right)^{d+1}} dy = \int_{\mathbb{R}} \frac{(1 + y^2/d)^{\frac{d+1}{2}}}{\left(1 + \frac{y^2}{d}\right)^{d+1}} dy $$

Hence,

$$ 
\begin{aligned}
\int_{\mathbb{R}} \frac{\left(1 + \frac{(y+a)^2}{d}\right)^{\frac{d+1}{2}}}{\left(1 + \frac{y^2}{d}\right)^{d+1}} dy &\le 2 \sum_{l=1}^{\frac{d+1}{2}} \sum_{j=0}^{l-1} \binom{\frac{d+1}{2}}{l} \binom{2l}{2j} \frac{a^{2l-2j}}{d^l} d^{j+1/2} + \int_{\mathbb{R}} \frac{(1 + y^2/d)^{\frac{d+1}{2}}}{\left(1 + \frac{y^2}{d}\right)^{d+1}} dy \\
&= 2 \sum_{l=1}^{\frac{d+1}{2}} a^{2l} \sum_{j=0}^{l-1} \binom{\frac{d+1}{2}}{l} \binom{2l}{2j} \frac{a^{-2j}}{d^l} d^{j+1/2} + \int_{\mathbb{R}} \frac{(1 + y^2/d)^{\frac{d+1}{2}}}{\left(1 + \frac{y^2}{d}\right)^{d+1}} dy \\
&\le 2 \sum_{l=1}^{\frac{d+1}{2}} a^{2l} \sum_{j=0}^{l-1} \binom{\frac{d+1}{2}}{l} \binom{2l}{2j} \frac{a^{-2j}}{d^l} d^{j+1/2} + \int_{\mathbb{R}} \frac{(1 + y^2/d)^{\frac{d+1}{2}}}{\left(1 + \frac{y^2}{d}\right)^{d+1}} dy
\end{aligned}
\quad (45) $$
$$ 
\quad (46) $$

And,

$$ 
\begin{aligned}
\sum_{l=1}^{\frac{d+1}{2}} a^{2l} \sum_{j=0}^{l-1} \binom{\frac{d+1}{2}}{l} \binom{2l}{2j} \frac{a^{-2j}}{d^l} d^{j+1/2} &= \sqrt{d} \sum_{l=1}^{\frac{d+1}{2}} \sum_{j=0}^{l-1} \binom{\frac{d+1}{2}}{l} \binom{2l}{2j} a^{2(l-j)} d^{j-l} \\
&\le \sqrt{d} \sum_{l=1}^{\frac{d+1}{2}} \sum_{j=0}^{l-1} \binom{\frac{d+1}{2}}{l} \binom{2(l-1)}{2j} l^2 \left(\frac{a^2}{d}\right)^{l-j}.
\end{aligned}
$$
### B.3.4 Proof of Lemma 10: Algebra on Student's distribution

We have,

$$ 
\begin{aligned}
\int_{\mathbb{R}} \frac{\left(1 + \frac{(y+a)^2}{d}\right)^{\frac{d+1}{2}}}{\left(1 + \frac{y^2}{d}\right)^{d+1}} dy &= \int_{\mathbb{R}} \sum_{l=0}^{\frac{d+1}{2}} \binom{\frac{d+1}{2}}{l} \frac{(y+a)^{2l}}{d^l \left(1 + \frac{y^2}{d}\right)^{d+1}} dy \\
&= \int_{\mathbb{R}} \sum_{l=0}^{\frac{d+1}{2}} \sum_{j=0}^{2l} \binom{\frac{d+1}{2}}{l} \binom{2l}{j} \frac{y^j a^{2l-j}}{d^l \left(1 + \frac{y^2}{d}\right)^{d+1}} dy \\
&= \sum_{l=0}^{\frac{d+1}{2}} \sum_{j=0}^{2l} \binom{\frac{d+1}{2}}{l} \binom{2l}{j} \int_{\mathbb{R}} \frac{y^j a^{2l-j}}{d^l \left(1 + \frac{y^2}{d}\right)^{d+1}} dy
\end{aligned}
$$

Remark that the integral is 0 if j is odd. Hence,

$$ \int_{\mathbb{R}} \frac{\left(1 + \frac{(y+a)^2}{d}\right)^{\frac{d+1}{2}}}{\left(1 + \frac{y^2}{d}\right)^{d+1}} dy = \sum_{l=0}^{\frac{d+1}{2}} \sum_{j=1}^{l} \binom{\frac{d+1}{2}}{l} \binom{2l}{2j} \frac{a^{2l-2j}}{d^l} \int_{\mathbb{R}} \frac{y^{2j}}{\left(1 + \frac{y^2}{d}\right)^{d+1}} dy $$

Then, we compute the integrals. By change of variable $u = y/d$, we have

$$ \int_{\mathbb{R}} \frac{y^{2j}}{\left(1 + \frac{y^2}{d}\right)^{d+1}} dy = d^{j+1/2} \int_{\mathbb{R}} \frac{u^{2j}}{(1 + u^2)^{d+1}} du \le 2d^{j+1/2} $$

and for $l = j$,

$$ \sum_{l=0}^{\frac{d+1}{2}} \binom{\frac{d+1}{2}}{l} \frac{1}{d^l} \int_{\mathbb{R}} \frac{y^{2l}}{\left(1 + \frac{y^2}{d}\right)^{d+1}} dy = \int_{\mathbb{R}} \frac{(1 + y^2/d)^{\frac{d+1}{2}}}{\left(1 + \frac{y^2}{d}\right)^{d+1}} dy $$

Hence,

$$ 
\begin{aligned}
\int_{\mathbb{R}} \frac{\left(1 + \frac{(y+a)^2}{d}\right)^{\frac{d+1}{2}}}{\left(1 + \frac{y^2}{d}\right)^{d+1}} dy &\le 2 \sum_{l=1}^{\frac{d+1}{2}} \sum_{j=0}^{l-1} \binom{\frac{d+1}{2}}{l} \binom{2l}{2j} \frac{a^{2l-2j}}{d^l} d^{j+1/2} + \int_{\mathbb{R}} \frac{(1 + y^2/d)^{\frac{d+1}{2}}}{\left(1 + \frac{y^2}{d}\right)^{d+1}} dy \\
&= 2 \sum_{l=1}^{\frac{d+1}{2}} a^{2l} \sum_{j=0}^{l-1} \binom{\frac{d+1}{2}}{l} \binom{2l}{2j} \frac{a^{-2j}}{d^l} d^{j+1/2} + \int_{\mathbb{R}} \frac{(1 + y^2/d)^{\frac{d+1}{2}}}{\left(1 + \frac{y^2}{d}\right)^{d+1}} dy \\
&\le 2 \sum_{l=1}^{\frac{d+1}{2}} a^{2l} \sum_{j=0}^{l-1} \binom{\frac{d+1}{2}}{l} \binom{2l}{2j} \frac{a^{-2j}}{d^l} d^{j+1/2} + \int_{\mathbb{R}} \frac{(1 + y^2/d)^{\frac{d+1}{2}}}{\left(1 + \frac{y^2}{d}\right)^{d+1}} dy
\end{aligned}
\quad (45) $$
$$ 
\quad (46) $$

And,

$$ 
\begin{aligned}
\sum_{l=1}^{\frac{d+1}{2}} a^{2l} \sum_{j=0}^{l-1} \binom{\frac{d+1}{2}}{l} \binom{2l}{2j} \frac{a^{-2j}}{d^l} d^{j+1/2} &= \sqrt{d} \sum_{l=1}^{\frac{d+1}{2}} \sum_{j=0}^{l-1} \binom{\frac{d+1}{2}}{l} \binom{2l}{2j} a^{2(l-j)} d^{j-l} \\
&\le \sqrt{d} \sum_{l=1}^{\frac{d+1}{2}} \sum_{j=0}^{l-1} \binom{\frac{d+1}{2}}{l} \binom{2(l-1)}{2j} l^2 \left(\frac{a^2}{d}\right)^{l-j}.
\end{aligned}
$$
Using that $\binom{2l}{2j} = \binom{2(l-1)}{2j} \frac{2l(2l-1)}{(2l-2j)(2l-2j-1)} \le \binom{2(l-1)}{2j}l^2$.
Then, completing the binomial sum so that

$$ \sum_{j=0}^{l-1} \binom{2(l-1)}{2j} \left(\frac{a^2}{d}\right)^{-j} \le \sum_{j=0}^{2(l-1)} \binom{2(l-1)}{2j} \left(\frac{a^2}{d}\right)^{-j} = \left(1 + \frac{\sqrt{d}}{a}\right)^{2(l-1)}, $$

we have,

$$ \begin{aligned} \sum_{l=1}^{\frac{d+1}{2}} a^{2l} \sum_{j=0}^{l-1} \binom{\frac{d+1}{2}}{l} \binom{2l}{2j} \frac{a^{-2j}}{d^l} d^{j+1/2} &\le \frac{1}{2}(d+1)\sqrt{d} \sum_{l=1}^{\frac{d+1}{2}} \binom{\frac{d+1}{2}}{l} \left(\frac{a^2}{d}\right)^l l \left(1 + \frac{\sqrt{d}}{a}\right)^{2(l-1)} \\ &= \frac{a^2}{2d}(d+1)\sqrt{d} \sum_{l=1}^{\frac{d+1}{2}} \binom{\frac{d+1}{2}}{l} l \left(\frac{a}{\sqrt{d}} + 1\right)^{2(l-1)} \\ &= \frac{a^2}{2d}(d+1)\sqrt{d} \sum_{l=0}^{\frac{d-1}{2}} \binom{\frac{d-1}{2}}{l} \frac{(d+1)(l+1)}{2(l+1)} \left(\frac{a}{\sqrt{d}} + 1\right)^{2l} \\ &\le \frac{a^2}{4\sqrt{d}}(d+1)^2 \left(2 + \frac{a}{\sqrt{d}}\right)^{d-1} \end{aligned} $$

Then, inject this in Equation (45) to get

$$ \int_{\mathbb{R}} \frac{\left(1 + \frac{(y+a)^2}{d}\right)^{\frac{d+1}{2}}}{\left(1 + \frac{y^2}{d}\right)^{d+1}} dy \le \frac{a^2}{2\sqrt{d}}(d+1)^2 \left(2 + \frac{a}{\sqrt{d}}\right)^{d-1} + \int_{\mathbb{R}} \frac{(1 + y^2/d)^{\frac{d+1}{2}}}{\left(1 + \frac{y^2}{d}\right)^{d+1}} dy. $$
Using that $\binom{2l}{2j} = \binom{2(l-1)}{2j} \frac{2l(2l-1)}{(2l-2j)(2l-2j-1)} \le \binom{2(l-1)}{2j}l^2$.

Then, completing the binomial sum so that

$$ \sum_{j=0}^{l-1} \binom{2(l-1)}{2j} \left(\frac{a^2}{d}\right)^{-j} \le \sum_{j=0}^{2(l-1)} \binom{2(l-1)}{2j} \left(\frac{a^2}{d}\right)^{-j} = \left(1 + \frac{\sqrt{d}}{a}\right)^{2(l-1)}, $$

we have,

$$ \begin{aligned} \sum_{l=1}^{\frac{d+1}{2}} a^{2l} \sum_{j=0}^{l-1} \binom{\frac{d+1}{2}}{l} \binom{2l}{2j} \frac{a^{-2j}}{d^l} d^{j+1/2} &\le \frac{1}{2}(d+1)\sqrt{d} \sum_{l=1}^{\frac{d+1}{2}} \binom{\frac{d+1}{2}}{l} \left(\frac{a^2}{d}\right)^l l \left(1 + \frac{\sqrt{d}}{a}\right)^{2(l-1)} \\ &= \frac{a^2}{2d}(d+1)\sqrt{d} \sum_{l=1}^{\frac{d+1}{2}} \binom{\frac{d+1}{2}}{l} l \left(\frac{a}{\sqrt{d}} + 1\right)^{2(l-1)} \\ &= \frac{a^2}{2d}(d+1)\sqrt{d} \sum_{l=0}^{\frac{d-1}{2}} \binom{\frac{d-1}{2}}{l} \frac{(d+1)(l+1)}{2(l+1)} \left(\frac{a}{\sqrt{d}} + 1\right)^{2l} \\ &\le \frac{a^2}{4\sqrt{d}}(d+1)^2 \left(2 + \frac{a}{\sqrt{d}}\right)^{d-1} \end{aligned} $$

Then, inject this in Equation (45) to get

$$ \int_{\mathbb{R}} \frac{\left(1 + \frac{(y+a)^2}{d}\right)^{\frac{d+1}{2}}}{\left(1 + \frac{y^2}{d}\right)^{d+1}} dy \le \frac{a^2}{2\sqrt{d}}(d+1)^2 \left(2 + \frac{a}{\sqrt{d}}\right)^{d-1} + \int_{\mathbb{R}} \frac{(1 + y^2/d)^{\frac{d+1}{2}}}{\left(1 + \frac{y^2}{d}\right)^{d+1}} dy. $$
# C Additional experimental results

## C.1 Sensitivity to $\beta$ and $\varepsilon$

In this section, we illustrate the impact of the choice of $\beta$ and $\varepsilon$ on the estimation.

**Choice of $\beta$ (Figure 5(b)):** The choice of $\beta$ is a trade-off between the bias (distance $|\text{Hub}_{\beta}(P) - \mathbb{E}[X]|$ which decreases as $\beta$ goes to infinity) and robustness (when $\beta$ goes to 0, $\text{Hub}_{\beta}(P)$ goes to the median). To illustrate this trade-off we use the Weibull distribution for which can be very asymmetric. We use a 3-armed bandit problem with shape parameters (2, 2, 0.75) and scale parameters (0.5, 0.7, 0.8) which implies that the means are approximately (0.44, 0.62, 0.95). These distributions are very asymmetric, hence the bias $|\text{Hub}_{\beta}(P) - \mathbb{E}[X]|$ is high and in fact even though arm 3 has the optimal mean, arm 2 will have the optimal median, the medians are given by (0.41, 0.58, 0.49). In this experiment we don't use any corruption as we don't want to complicate the interpretation. As expected by the theory, we get that $\beta_i$ should not be too small or too large but it should be around $4\sigma_i$.

**Choice of $\varepsilon$ (Figure 5(a)):** To illustrate the dependency in $\varepsilon$, we also use the Weibull distribution to show the dependency in $\varepsilon$ with the same parameters as in the previous Weibull example, except that we choose $\beta_i = 5\sigma_i$ which is around the optimum found in the previous experiment and we corrupt with 2% of outliers (this is the true $\varepsilon$ while we will make the $\varepsilon$ used in the definition of the algorithm vary). The outliers are constructed as in Section 7. The effect of the parameter $\varepsilon$ is difficult to assess because $\varepsilon$ has an impact on the length of force exploration that we impose at the beginning of our algorithm (the $s_{lim}$).

<figure><img src="image_5.png" /><figcaption>Figure 4: Cumulative regret plots for different values of the parameters $\varepsilon$ and $\beta$ on a Weibull dataset.</figcaption></figure>

## C.2 Corrupted bandits with adversarial algorithms

To illustrate the performances of classical algorithms on corrupted bandits problems, we redo the experiments from Section 7 with algorithms from the adversarial literature (Exp3 and FTRL with log-barrier). We also include Thompson sampling in the case of Bernoulli inlier distributions. The results are rendered in Figure 5. These results show that adversarial algorithms like EXP3 and FTRL, and also Thompson Sampling are very inefficient when the corruption is important as in the case of the Pareto experiments with $\varepsilon = 0.03$ and $\varepsilon = 0.05$.
# C Additional experimental results

## C.1 Sensitivity to $\beta$ and $\varepsilon$

In this section, we illustrate the impact of the choice of $\beta$ and $\varepsilon$ on the estimation.

**Choice of $\beta$ (Figure 5(b)):** The choice of $\beta$ is a trade-off between the bias (distance $|\text{Hub}_{\beta}(P) - \mathbb{E}[X]|$ which decreases as $\beta$ goes to infinity) and robustness (when $\beta$ goes to 0, $\text{Hub}_{\beta}(P)$ goes to the median). To illustrate this trade-off we use the Weibull distribution for which can be very asymmetric. We use a 3-armed bandit problem with shape parameters (2, 2, 0.75) and scale parameters (0.5, 0.7, 0.8) which implies that the means are approximately (0.44, 0.62, 0.95). These distributions are very asymmetric, hence the bias $|\text{Hub}_{\beta}(P) - \mathbb{E}[X]|$ is high and in fact even though arm 3 has the optimal mean, arm 2 will have the optimal median, the medians are given by (0.41, 0.58, 0.49). In this experiment we don't use any corruption as we don't want to complicate the interpretation. As expected by the theory, we get that $\beta_i$ should not be too small or too large but it should be around $4\sigma_i$.

**Choice of $\varepsilon$ (Figure 5(a)):** To illustrate the dependency in $\varepsilon$, we also use the Weibull distribution to show the dependency in $\varepsilon$ with the same parameters as in the previous Weibull example, except that we choose $\beta_i = 5\sigma_i$ which is around the optimum found in the previous experiment and we corrupt with 2% of outliers (this is the true $\varepsilon$ while we will make the $\varepsilon$ used in the definition of the algorithm vary). The outliers are constructed as in Section 7. The effect of the parameter $\varepsilon$ is difficult to assess because $\varepsilon$ has an impact on the length of force exploration that we impose at the beginning of our algorithm (the $s_{lim}$).

<figure><img src="image_7.png" /><figcaption>Figure 4: Cumulative regret plots for different values of the parameters $\varepsilon$ and $\beta$ on a Weibull dataset.</figcaption></figure>

## C.2 Corrupted bandits with adversarial algorithms

To illustrate the performances of classical algorithms on corrupted bandits problems, we redo the experiments from Section 7 with algorithms from the adversarial literature (Exp3 and FTRL with log-barrier). We also include Thompson sampling in the case of Bernoulli inlier distributions. The results are rendered in Figure 5. These results show that adversarial algorithms like EXP3 and FTRL, and also Thompson Sampling are very inefficient when the corruption is important as in the case of the Pareto experiments with $\varepsilon = 0.03$ and $\varepsilon = 0.05$.
<figure><img src="image_6.png" /><figcaption>Figure 5: Cumulative regret plot of the algorithms on a corrupted Bernoulli (above), Student's (middle) and Pareto (below) reward distributions with various corruption levels $\epsilon$. Lower corrupted regret indicates better performance for an algorithm.</figcaption></figure>
<figure><img src="image_8.png" /><figcaption>Figure 5: Cumulative regret plot of the algorithms on a corrupted Bernoulli (above), Student's (middle) and Pareto (below) reward distributions with various corruption levels $\epsilon$. Lower corrupted regret indicates better performance for an algorithm.</figcaption></figure>