$\displaystyle=\max_{z\in\mathcal{Z}}\inf_{\lambda\in\neg_{\varepsilon}\tilde{z}}\|\mu-\lambda\|^{2}_{V_{N_{t}}}-\sqrt{8f(t)\beta(t,\delta)}-4f(t)\>.$

The second inequality is obtained by using (19) and the definition of
$\tilde{\lambda}$. The third is obtained by taking the
$\inf_{\lambda\in\neg_{\varepsilon}\tilde{z}}$, which is possible since
$\tilde{\lambda}\in\neg_{\varepsilon}\tilde{z}$. The equality uses that
$\tilde{z}\in z_{F}(\mu,N_{t})$. Therefore, we have shown that

$\displaystyle
2\beta(t,\delta)\geq\max_{z\in\mathcal{Z}}\inf_{\lambda\in\neg_{\varepsilon}z}\|\mu-\lambda\|^{2}_{V_{N_{t}}}-h_{\delta}(t)$

where
$h_{\delta}(t)=\sqrt{8f(t)\beta(t,\delta)}+4f(t)=\Theta\left(\ln(t)+\sqrt{\ln\left(\frac{1}{\delta}\right)}\right)$,
hence sub-linear function of both $t$ and $\ln\left(\frac{1}{\delta}\right)$.
∎

####  E.2.1 Computational Relaxations

Depending on $\mathcal{Z}$, computing an instantaneous furthest answer at each
time $t$ might be too costly. To reduce the computational cost, we propose two
different relaxations for any stopping-recommendation pair: the lazy version
and the sticky one. The main idea behind both of them is to avoid the
computation of a new recommendation rule at each time. Defining a grid of time
$\mathcal{T}\subseteq\mathbb{N}$, we stick to the previous candidate answer
when $t\notin\mathcal{T}$, i.e. $z_{t}=z_{t-1}$, else we compute a new one. To
satisfy the sole requirement on the recommendation rule (Lemma 3.1), a new
value has to be computed when $t\notin\mathcal{T}$ and
$z_{t-1}\notin\mathcal{Z}_{\varepsilon}(\mu_{t-1})$.

Both computational relaxations use the stopping criterion defined in (5).
While the sticky version evaluates it at each time $t>n_{0}$, the lazy version
only does it when the recommendation rule is updated ($t\in\mathcal{T}$). It
is important to notice that thanks to Lemma 3.1, the lazy and sticky
computational relaxations yield $(\varepsilon,\delta)$-PAC strategy regardless
of the sampling rule.

In the following, we consider an instantaneous furthest answer as
recommendation rule and a geometric-like grid of time $\mathcal{T}$. To ensure
asymptotic optimality of the algorithm, we need to have a strictly positive
and decreasing expansion parameter $(\gamma_{i})_{i\in\mathbb{N}^{\star}}$
such that $\gamma_{i}\rightarrow 0$. More formally, we use
$\mathcal{T}\buildrel\text{def}\over{=}\left\\{n_{0}+1\right\\}\cup\left\\{t_{i}\right\\}_{i\in\mathbb{N}}$
where $t_{0}>n_{0}$ denotes the end of the first phase and for all
$i\in\mathbb{N}^{\star}$, $t_{i}=\lceil(1+\gamma_{i})t_{i-1}\rceil$. Since
$\gamma_{i}$ is strictly positive, we have $t_{i}>t_{i-1}$ and $\mathcal{T}$
is an infinite set of times, hence Lemma 3.1 applies. Since the main
components of the proof are unchanged, we only state the noteworthy
modifications.

##### Lazy Update

When considering the lazy update, both the candidate answer and the stopping
criterion are computed only when $t\in\mathcal{T}$. Under $\mathcal{E}_{t}$,
if the algorithm doesn’t stop at time $t+1$, there exists $i\in\mathbb{N}$
such that $t\in\left\llbracket t_{i},t_{i+1}-1\right\rrbracket$ such that the
stopping criterion is not met at time $t_{i}+1$:

$\displaystyle
2\beta(t_{i},\delta)\geq\inf_{\lambda\in\neg_{\varepsilon}z_{t_{i}+1}}\|\mu_{t_{i}}-\lambda\|^{2}_{V_{N_{t_{i}}}}\geq\max_{z\in\mathcal{Z}}\inf_{\lambda\in\neg_{\varepsilon}z}\|\mu-\lambda\|^{2}_{V_{N_{t_{i}}}}-h_{\delta}(t_{i})$

where $h_{\delta}$ is defined in Lemma E.5 and the second inequality is
obtained as above since $\mathcal{E}_{t_{i}}\subseteq\mathcal{E}_{t}$ and
$z_{t_{i}+1}=z_{F}(\mu_{t_{i}},N_{t_{i}})$. Therefore, using the lazy update
with an instantaneous furthest answer as recommendation rule allow to satisfy
the condition (17) at time $t_{i}$.

Given a sampling rule satisfying the condition (18) at time $t_{i}$, the rest
of the proof is exactly the same as sketched in Appendix E.1 and proved in
Appendix E.3 with $t_{i}$ instead of $t$. Therefore, we will obtain

$\displaystyle H_{\mu}(t_{i},\delta)\geq t_{i}T_{\varepsilon}(\mu)^{-1}$

Since $t\in\left\llbracket t_{i},t_{i+1}-1\right\rrbracket$, we have
$H_{\mu}(t_{i},\delta)\leq H_{\mu}(t,\delta)$ and
$t_{i}\geq\frac{t_{i+1}-1}{1+\gamma_{i+1}}\geq\frac{t}{1+\gamma_{i+1}}$. This
yields

$\displaystyle\tilde{H}_{\mu}(t,\delta)\buildrel\text{def}\over{=}(1+\gamma_{i+1})H_{\mu}(t,\delta)\geq
tT_{\varepsilon}(\mu)^{-1}$

We remark that $t\rightarrow+\infty$ implies $i\rightarrow+\infty$, hence
$\gamma_{i+1}\rightarrow_{t\rightarrow+\infty}0$. Choosing $\gamma_{i}$
independently of $\delta$ and noting that
$\tilde{H}_{\mu}(t,\delta)=\ln\left(\frac{1}{\delta}\right)+\mathcal{O}\left(t^{1-\beta_{1}}+\ln\left(1/\delta\right)^{1-\beta_{2}}\right)$
since
$H_{\mu}(t,\delta)=\ln\left(\frac{1}{\delta}\right)+\mathcal{O}\left(t^{1-\beta_{1}}+\ln\left(1/\delta\right)^{1-\beta_{2}}\right)$,
we can conclude the proof. Combining the lazy update with a good sampling rule
and an instantaneous furthest answer as recommendation rule leads to
asymptotically optimal algorithms.

For an expansion parameter which is constant, the manipulation above shows
that the upper bound won’t match the lower bound by a constant multiplicative
factor $1+\gamma_{0}$. Therefore, the shrinking expansion parameter is crucial
to obtain asymptotic optimality.

##### Sticky Update

When considering the sticky update, the candidate answer is computed only when
$t\in\mathcal{T}$, while the stopping criterion is evaluated at each time $t$.
Since the GLRTs conducted with the lazy update are strictly included in the
ones conducted with the sticky update (with matching candidate answer), the
sticky approach is strictly better in terms of sample complexity than
considering the lazy one. Therefore, we have
$\tau_{\delta}^{\text{sticky}}\leq\tau_{\delta}^{\text{lazy}}$, hence
$\lim_{\delta\rightarrow
0}\frac{\operatorname*{\mathbb{E}}_{\mu}[\tau_{\delta}^{\text{sticky}}]}{\ln(1/\delta)}\leq\lim_{\delta\rightarrow
0}\frac{\operatorname*{\mathbb{E}}_{\mu}[\tau_{\delta}^{\text{lazy}}]}{\ln(1/\delta)}$.
Using the above result showing that lazy update leads to asymptotic optimal
algorithms, we conclude that sticky update also leads to asymptotic optimal
algorithms.

###  E.3 Sampling Rule

In this appendix, we show that the desired condition (18) on the sampling rule
holds when considering the sampling rule in L$\varepsilon$BAI (Appendix
E.3.2). Appendix E.3.1 details the two algorithmic requirements enforced in
L$\varepsilon$BAI.

####  E.3.1 Requirements

To conduct the analysis of the sampling rule used in L$\varepsilon$BAI, two
algorithmic requirements were needed to be enforced. However, as experiments
show in Appendix F.2, competitive empirical performance are obtained without
them.

##### Forced Exploration

To provide an upper bound on the number of times a good event doesn’t occur
(Lemma E.20), forced exploration has to be introduced by using
$w_{t}=\frac{1}{tK}\mathbf{1}_{K}+\left(1-\frac{1}{t}\right)w_{t}^{\mathcal{L}^{\mathcal{K}}}$.
Good events will be formally introduced below in (22). Since we are using
tracking and $\sum_{s=n_{0}+1}^{t}\frac{1}{s}=\Theta(\ln t)$, the forced
exploration only concerns a logarithmic number of steps.

##### Exact $\mathcal{Z}$-Oracle

Likewise, to provide an upper bound on the number of times a good event
doesn’t occur (Lemma E.20), the $\mathcal{Z}$-oracle has to satisfy
$\tilde{z}_{t}\in z_{F}(\mu_{t-1})$. Since this requirement is computationally
intractable, it doesn’t lead to a practical algorithm. In the experiments, we
use an instantaneous furthest answer $\tilde{z}_{t}=z_{t}\in
z_{F}(\mu_{t-1},N_{t-1})$ which has good empirical behavior. Since it was
already computed for the recommendation rule, no additional computation are
needed.

While the proof still eludes us, we believe that using an instantaneous
furthest answer would be also a theoretically valid choice for the
$\mathcal{Z}$-oracle. Intuitively an instantaneous furthest answer is a good
proxy for $z_{F}(\mu)$ because the empirical proportions will eventually
converge to $w_{F}(\mu)$. Using our current proof techniques, it is difficult
to show this result since the convergence properties and upper bound on the
expected sample complexity are highly intertwined. Borrowing the proofs
strategy of (Garivier & Kaufmann, 2016), it might be possible to show it with
purely asymptotic arguments. We leave this interesting question to future
work.

####  E.3.2 Proof of Desired Property

To highlight the structure of the proof, we prove separately two inequalities
satisfied by the sampling rule used in L$\varepsilon$BAI (Lemma E.6 and Lemma
E.7). This intermediate step involves the cumulative gain of the learner used
by the $\mathcal{K}$-player.

######  Lemma E.6.

Let $\mathcal{L}^{\mathcal{Z}}$ be the $\mathcal{Z}$-oracle such that
$\tilde{z}_{s}\in z_{F}(\mu_{s-1})$. Let $b>0$. For all $s\in\left\llbracket
n_{0},t-1\right\rrbracket$ and $a\in\mathcal{K}$, let $(c_{s}^{a})_{s\geq
n_{0},a\in\mathcal{K}}$ be defined by

$c_{s}^{a}\buildrel\text{def}\over{=}\min\left\\{f\left(s^{1+b}\right)\|a\|^{2}_{V_{N_{s}}^{-1}},4M^{2}L_{\mathcal{K}}^{2}\right\\}$
(20)

The optimistic gain $g_{s}(w)\buildrel\text{def}\over{=}(1-\frac{1}{s})\langle
w,U_{s}\rangle$ are defined such that: for all $a\in\mathcal{K}$ and
$s\in\left\llbracket n_{0}+1,t\right\rrbracket$,

$U_{s}^{a}\buildrel\text{def}\over{=}\left(\|\mu_{s-1}-\lambda_{s}\|_{aa^{\mathsf{\scriptscriptstyle
T}}}+\sqrt{c_{s-1}^{a}}\right)^{2}$ (21)

with
$\lambda_{s}\buildrel\text{def}\over{=}\operatorname*{arg\,min}_{\lambda\in\neg_{\varepsilon}\tilde{z}_{s}}\|\mu_{s-1}-\lambda\|^{2}_{V_{w_{s}}}$.
Then, under $\mathcal{E}_{t}$ if L$\varepsilon$BAI does not stop at time
$t+1$,

$\displaystyle\max_{z\in\mathcal{Z}}\inf_{\lambda\in\neg_{\varepsilon}z}\|\mu-\lambda\|^{2}_{V_{N_{t}}}\geq\sum_{s=n_{0}+1}^{t}g_{s}\left(w_{s}^{\mathcal{L}^{\mathcal{K}}}\right)-r_{1}(t)\>,$

where

$\displaystyle
r_{1}(t)=C_{1}+\left(N_{F}(t)+t^{\frac{1}{1+b}}\right)4KM^{2}L_{\mathcal{K}}^{2}+h^{\prime}(t)+h^{\prime\prime}(t)=\Theta\left(\ln(t)\sqrt{t}+\ln(t)^{2}t^{\frac{1}{1+b}}\right)$
with $\displaystyle
h^{\prime\prime}(t)=f\left(t^{1+b}\right)\left(K\ln(K)+2K\ln(t)\right)+4ML_{\mathcal{K}}\sqrt{f\left(t^{1+b}\right)}\left(K\ln(K)+\sqrt{8Kt}\right)$
and $\displaystyle
h^{\prime}(t)=4ML_{\mathcal{K}}\sqrt{\left(K\ln(K)+2K\ln(t)\right)f\left(t^{1+b}\right)t}+8M^{2}L_{\mathcal{K}}^{2}t^{\frac{1}{1+b}}\>.$

###### Proof.

Step 1. From $N_{t}$ to $W_{t}$. Let
$W_{t}\buildrel\text{def}\over{=}\sum_{s\in[t]}w_{s}$. Using Lemma E.15,

$\displaystyle\max_{z\in\mathcal{Z}}\inf_{\lambda\in\neg_{\varepsilon}z}\|\mu-\lambda\|^{2}_{V_{N_{t}}}$
$\displaystyle\geq\max_{z\in
z_{F}(\mu,W_{t})}\inf_{\lambda\in\neg_{\varepsilon}z}\|\mu-\lambda\|^{2}_{V_{N_{t}}}\>.$

Recall that for all $N\in\mathbb{R}_{+}^{K}$,
$\|\mu-\lambda\|^{2}_{V_{N}}=\sum_{a\in\mathcal{K}}N^{a}\|\mu-\lambda\|^{2}_{aa^{\mathsf{\scriptscriptstyle
T}}}$. Using Cauchy-Schwartz and the bounded assumption, we have:
$\|\mu-\lambda\|^{2}_{aa^{\mathsf{\scriptscriptstyle
T}}}=\langle\mu-\lambda,a\rangle^{2}\leq\|\mu-\lambda\|_{2}^{2}\|a\|^{2}_{2}\leq
4M^{2}L_{\mathcal{K}}^{2}$. For any $\lambda\in\mathcal{M}$, using Lemma E.9,

$\displaystyle\|\mu-\lambda\|^{2}_{V_{N_{t}}}$
$\displaystyle\geq\|\mu-\lambda\|^{2}_{V_{W_{t}}}-\ln(K)\sum_{a\in\mathcal{K}}\|\mu-\lambda\|^{2}_{aa^{\mathsf{\scriptscriptstyle
T}}}$ $\displaystyle\geq\|\mu-\lambda\|^{2}_{V_{W_{t}}}-C_{1}\>,$

where
$C_{1}\buildrel\text{def}\over{=}4\ln(K)KM^{2}L_{\mathcal{K}}^{2}=\Theta(1)$.

Let $\tilde{z}\in\operatorname*{arg\,max}_{z\in
z_{F}(\mu,W_{t})}\inf_{\lambda\in\neg_{\varepsilon}z}\|\mu-\lambda\|^{2}_{V_{N_{t}}}$
and
$\tilde{\lambda}\in\operatorname*{arg\,min}_{\lambda\in\neg_{\varepsilon}\tilde{z}}\|\mu-\lambda\|^{2}_{V_{N_{t}}}$.
Using the above yields

$\displaystyle\max_{z\in\mathcal{Z}}\inf_{\lambda\in\neg_{\varepsilon}z}\|\mu-\lambda\|^{2}_{V_{N_{t}}}$
$\displaystyle\geq\|\mu-\tilde{\lambda}\|^{2}_{V_{W_{t}}}-C_{1}$
$\displaystyle\geq\inf_{\lambda\in\neg_{\varepsilon}\tilde{z}}\|\mu-\lambda\|^{2}_{V_{W_{t}}}-C_{1}$
$\displaystyle=\max_{z\in\mathcal{Z}}\inf_{\lambda\in\neg_{\varepsilon}z}\|\mu-\lambda\|^{2}_{V_{W_{t}}}-C_{1}\>,$

where we used that $\tilde{\lambda}\in\neg_{\varepsilon}\tilde{z}$ and
$\tilde{z}\in z_{F}(\mu,W_{t})$.

##### Step 2. From $(\mu,z_{F}(\mu,W_{t}))$ to $(\mu_{s-1},\tilde{z}_{s})$.

Using the concavity of $\inf$ and
$\|\mu-\lambda\|^{2}_{V_{W_{t}}}=\sum_{s=n_{0}+1}^{t}\|\mu-\lambda\|^{2}_{V_{w_{s}}}$,
we obtain

$\displaystyle\max_{z\in\mathcal{Z}}\inf_{\lambda\in\neg_{\varepsilon}z}\|\mu-\lambda\|^{2}_{V_{W_{t}}}\geq\max_{z\in\mathcal{Z}}\sum_{s=n_{0}+1}^{t}\inf_{\lambda\in\neg_{\varepsilon}z}\|\mu-\lambda\|^{2}_{V_{w_{s}}}\>.$

Using the triangular inequality, for all $z\in\mathcal{Z}$ and
$s\in\left\llbracket n_{0}+1,t\right\rrbracket$

$\displaystyle\|\mu-\lambda\|^{2}_{V_{w_{s}}}$
$\displaystyle\geq(\|\mu_{s-1}-\lambda\|_{V_{w_{s}}}-\|\mu_{s-1}-\mu\|_{V_{w_{s}}})^{2}\geq\|\mu_{s-1}-\lambda\|^{2}_{V_{w_{s}}}-2\|\mu_{s-1}-\mu\|_{V_{w_{s}}}\|\mu_{s-1}-\lambda\|_{V_{w_{s}}}$

For
$\tilde{\lambda}^{z}_{s}\in\operatorname*{arg\,min}_{\lambda\in\neg_{\varepsilon}z}\|\mu-\lambda\|^{2}_{V_{w_{s}}}$,
we obtain

$\displaystyle\|\mu-\tilde{\lambda}^{z}_{s}\|^{2}_{V_{w_{s}}}$
$\displaystyle\geq\|\mu_{s-1}-\tilde{\lambda}^{z}_{s}\|^{2}_{V_{w_{s}}}-2\|\mu_{s-1}-\mu\|_{V_{w_{s}}}\|\mu_{s-1}-\tilde{\lambda}^{z}_{s}\|_{V_{w_{s}}}$
$\displaystyle\geq\inf_{\lambda\in\neg_{\varepsilon}z}\|\mu_{s-1}-\lambda\|^{2}_{V_{w_{s}}}-2\|\mu_{s-1}-\mu\|_{V_{w_{s}}}\|\mu_{s-1}-\tilde{\lambda}^{z}_{s}\|_{V_{w_{s}}}$
$\displaystyle\geq\inf_{\lambda\in\neg_{\varepsilon}z}\|\mu_{s-1}-\lambda\|^{2}_{V_{w_{s}}}-4ML_{\mathcal{K}}\|\mu_{s-1}-\mu\|_{V_{w_{s}}}$

The second to last inequality is obtained by taking the
$\inf_{\lambda\in\neg_{\varepsilon}z}$, which is possible since
$\tilde{\lambda}^{z}_{s}\in\neg_{\varepsilon}z$, and the last one by upper
bounding
$\|\mu_{s-1}-\tilde{\lambda}_{s}\|_{V_{w_{s}}}\leq\|\mu_{s-1}-\tilde{\lambda}_{s}\|_{2}\leq
2ML_{\mathcal{K}}$ (since $w_{s}\in\triangle_{K}$). Summing those inequalities
together, using Cauchy-Schwartz when $s\geq\left\lceil
t^{\frac{1}{1+b}}\right\rceil$ and the boundedness assumption when
$s<\left\lceil t^{\frac{1}{1+b}}\right\rceil$, we obtain: for all
$z\in\mathcal{Z}$

$\displaystyle\sum_{s=n_{0}+1}^{t}\inf_{\lambda\in\neg_{\varepsilon}z}\|\mu-\lambda\|^{2}_{V_{w_{s}}}$
$\displaystyle\geq\sum_{s=n_{0}+1}^{t}\inf_{\lambda\in\neg_{\varepsilon}z}\|\mu_{s-1}-\lambda\|^{2}_{V_{w_{s}}}-4ML_{\mathcal{K}}\sum_{s=n_{0}+1}^{t}\|\mu_{s-1}-\mu\|_{V_{w_{s}}}$
$\displaystyle\geq\sum_{s=n_{0}+1}^{t}\inf_{\lambda\in\neg_{\varepsilon}z}\|\mu_{s-1}-\lambda\|^{2}_{V_{w_{s}}}-4ML_{\mathcal{K}}\sqrt{t-\left\lceil
t^{\frac{1}{1+b}}\right\rceil+1}\sqrt{\sum_{s=\left\lceil
t^{\frac{1}{1+b}}\right\rceil}^{t}\|\mu_{s-1}-\mu\|^{2}_{V_{w_{s}}}}$
$\displaystyle\quad\quad-8M^{2}L_{\mathcal{K}}^{2}\left(\left\lceil
t^{\frac{1}{1+b}}\right\rceil-n_{0}-1\right)$
$\displaystyle\geq\sum_{s=n_{0}+1}^{t}\|\mu_{s-1}-\lambda_{s}\|^{2}_{V_{w_{s}}}-4ML_{\mathcal{K}}\sqrt{t}\sqrt{\sum_{s=\left\lceil
t^{\frac{1}{1+b}}\right\rceil}^{t}\|\mu_{s-1}-\mu\|^{2}_{V_{w_{s}}}}-8M^{2}L_{\mathcal{K}}^{2}t^{\frac{1}{1+b}}$

The second inequality is obtained by concavity of $x\mapsto\sqrt{x}$, and the
last one uses the definition of the best-response oracle in the sampling rule,
$\lambda_{s}\in\operatorname*{arg\,min}_{\lambda\in\neg_{\varepsilon}\tilde{z}_{s}}\|\mu_{s-1}-\lambda\|^{2}_{V_{w_{s}}}$.
Using Lemma E.25, we know that $\sum_{s=\left\lceil
t^{\frac{1}{1+b}}\right\rceil}^{t}\|\mu_{s-1}-\mu\|^{2}_{V_{w_{s}}}\leq
f\left(t^{1+b}\right)\left(K\ln(K)+2K\ln(t)\right)=\mathcal{O}(\ln(t)^{2})$.
Therefore, we obtain: for all $z\in\mathcal{Z}$

$\displaystyle\sum_{s=n_{0}+1}^{t}\inf_{\lambda\in\neg_{\varepsilon}z}\|\mu-\lambda\|^{2}_{V_{w_{s}}}$
$\displaystyle\geq\sum_{s=n_{0}+1}^{t}\inf_{\lambda\in\neg_{\varepsilon}z}\|\mu_{s-1}-\lambda\|^{2}_{V_{w_{s}}}-h^{\prime}(t)$

where
$h^{\prime}(t)\buildrel\text{def}\over{=}4ML_{\mathcal{K}}\sqrt{\left(K\ln(K)+2K\ln(t)\right)f\left(t^{1+b}\right)t}+8M^{2}L_{\mathcal{K}}^{2}t^{\frac{1}{1+b}}=\Theta\left(\ln(t)\sqrt{t}+t^{\frac{1}{1+b}}\right)$.
Taking the maximum on both sides for the above result and using Lemma E.21, we
obtain by chaining the above inequalities

$\displaystyle\max_{z\in\mathcal{Z}}\inf_{\lambda\in\neg_{\varepsilon}z}\|\mu-\lambda\|^{2}_{V_{N_{t}}}$
$\displaystyle\geq\max_{z\in\mathcal{Z}}\sum_{s=n_{0}+1}^{t}\inf_{\lambda\in\neg_{\varepsilon}z}\|\mu_{s-1}-\lambda\|^{2}_{V_{w_{s}}}-C_{1}-h^{\prime}(t)$
$\displaystyle\geq\sum_{s=n_{0}+1}^{t}\inf_{\lambda\in\neg_{\varepsilon}\tilde{z}_{s}}\|\mu_{s-1}-\lambda\|^{2}_{V_{w_{s}}}-\left(N_{F}(t)+t^{\frac{1}{1+b}}\right)4KM^{2}L_{\mathcal{K}}^{2}-C_{1}-h^{\prime}(t)$
$\displaystyle=\sum_{s=n_{0}+1}^{t}\|\mu_{s-1}-\lambda_{s}\|^{2}_{V_{w_{s}}}-\left(N_{F}(t)+t^{\frac{1}{1+b}}\right)4KM^{2}L_{\mathcal{K}}^{2}-C_{1}-h^{\prime}(t)\>,$

where $N_{F}(t)$ is defined in (24).

##### Step 3. From $\|\mu_{s-1}-\lambda_{s}\|^{2}_{V_{w_{s}}}$ to
$g_{s}\left(w_{s}^{\mathcal{L}^{\mathcal{K}}}\right)$.

Using Lemma E.17, we obtain: for all $s\in\left\llbracket
n_{0}+1,t\right\rrbracket$ and $a\in\mathcal{K}$,

$\displaystyle\|\mu_{s-1}-\lambda_{s}\|^{2}_{aa^{\mathsf{\scriptscriptstyle
T}}}\geq U_{s}^{a}-c_{s-1}^{a}-4ML_{\mathcal{K}}\sqrt{c_{s-1}^{a}}$

Summing those inequalities together, we obtain:

$\displaystyle\sum_{s=n_{0}+1}^{t}\sum_{a\in\mathcal{K}}w_{s}^{a}\|\mu_{s-1}-\lambda_{s}\|^{2}_{aa^{\mathsf{\scriptscriptstyle
T}}}$
$\displaystyle\geq\sum_{s=n_{0}+1}^{t}\sum_{a\in\mathcal{K}}w_{s}^{a}U_{s}^{a}-\sum_{s=n_{0}+1}^{t}\sum_{a\in\mathcal{K}}w_{s}^{a}c_{s-1}^{a}-4ML_{\mathcal{K}}\sum_{s=n_{0}+1}^{t}\sum_{a\in\mathcal{K}}w_{s}^{a}\sqrt{c_{s-1}^{a}}$
$\displaystyle\geq\sum_{s=n_{0}+1}^{t}\sum_{a\in\mathcal{K}}w_{s}^{a}U_{s}^{a}-f\left(t^{1+b}\right)\left(K\ln(K)+2K\ln(t)\right)-4ML_{\mathcal{K}}\sqrt{f\left(t^{1+b}\right)}\left(K\ln(K)+\sqrt{8Kt}\right)$
$\displaystyle\geq\sum_{s=n_{0}+1}^{t}\left(1-\frac{1}{s}\right)\langle
w_{s}^{\mathcal{L}^{\mathcal{K}}},U_{s}\rangle-f\left(t^{1+b}\right)\left(K\ln(K)+2K\ln(t)\right)$
$\displaystyle\quad\quad-4ML_{\mathcal{K}}\sqrt{f\left(t^{1+b}\right)}\left(K\ln(K)+\sqrt{8Kt}\right)$
$\displaystyle=\sum_{s=n_{0}+1}^{t}g_{s}\left(w_{s}^{\mathcal{L}^{\mathcal{K}}}\right)-f\left(t^{1+b}\right)\left(K\ln(K)+2K\ln(t)\right)-4ML_{\mathcal{K}}\sqrt{f\left(t^{1+b}\right)}\left(K\ln(K)+\sqrt{8Kt}\right)$

where the second inequality is obtained by using Lemma E.24 and the third
since the optimistic gains are positive and the weights are defined as
$w_{s}=\frac{1}{sK}\mathbf{1}_{K}+\left(1-\frac{1}{s}\right)w_{s}^{\mathcal{L}^{\mathcal{K}}}$
for all $s\in\left\llbracket n_{0}+1,t\right\rrbracket$. The last equality
uses the definition of the gain $g_{s}(w)=\left(1-\frac{1}{s}\right)\langle
w,U_{s}\rangle$. Therefore, since
$\|\mu_{s-1}-\lambda_{s}\|^{2}_{V_{w_{s}}}=\sum_{a\in\mathcal{K}}w_{s}^{a}\|\mu_{s-1}-\lambda_{s}\|^{2}_{aa^{\mathsf{\scriptscriptstyle
T}}}$, we obtain that:

$\displaystyle\max_{z\in\mathcal{Z}}\inf_{\lambda\in\neg_{\varepsilon}z}\|\mu-\lambda\|^{2}_{V_{N_{t}}}\geq\sum_{s=n_{0}+1}^{t}g_{s}\left(w_{s}^{\mathcal{L}^{\mathcal{K}}}\right)-C_{1}-\left(N_{F}(t)+t^{\frac{1}{1+b}}\right)4KM^{2}L_{\mathcal{K}}^{2}-h^{\prime}(t)-h^{\prime\prime}(t)$

where
$h^{\prime\prime}(t)=f\left(t^{1+b}\right)\left(K\ln(K)+2K\ln(t)\right)+4ML_{\mathcal{K}}\sqrt{f\left(t^{1+b}\right)}\left(K\ln(K)+\sqrt{8Kt}\right)=\Theta\left(\sqrt{t\ln(t)}\right)$.
∎

######  Lemma E.7.

Let $\mathcal{L}^{\mathcal{Z}}$ be the $\mathcal{Z}$-oracle such that
$\tilde{z}_{s}\in z_{F}(\mu_{s-1})$. Let $\mathcal{L}^{\mathcal{K}}$ be a
learner with regret
$R_{\mathcal{L}^{\mathcal{K}}}(t)=\mathcal{O}(t^{\alpha_{1}})$ with
$\alpha_{1}\in(0,1)$ and fed with optimistic gain
$g_{s}(w)=(1-\frac{1}{s})\langle w,U_{s}\rangle$ where
$(U_{s})_{s\in\left\llbracket n_{0}+1,t\right\rrbracket}$ defined in (21).
Then, under $\mathcal{E}_{t}$ if L$\varepsilon$BAI does not stop at time
$t+1$,

$\displaystyle\sum_{s=n_{0}+1}^{t}g_{s}\left(w_{s}^{\mathcal{L}^{\mathcal{K}}}\right)\geq
2tT_{\varepsilon}(\mu)^{-1}-r_{2}(t)$

where

$\displaystyle
r_{2}(t)=R_{\mathcal{L}^{\mathcal{K}}}(t)+h^{\prime\prime\prime}(t)=\mathcal{O}\left(\ln(t)^{2}t^{\frac{1}{1+b}}+t^{\max\\{\alpha_{1},\frac{1}{1+b},1-\frac{1}{1+b}\\}}\right)$
with $\displaystyle
h^{\prime\prime\prime}(t)=2\left(t^{\frac{1}{1+b}}+N_{F}(t)+t^{1-\frac{1}{1+b}}\right)T_{\varepsilon}(\mu)^{-1}$

###### Proof.

Step 4. No-regret property. Using the no-regret property of the chosen online
learner $\mathcal{L}^{\mathcal{K}}$ fed with gains $\left(g_{s}\right)_{s\geq
n_{0}+1}$ and playing $\left(w_{s}^{\mathcal{L}^{\mathcal{K}}}\right)_{s\geq
n_{0}+1}$, whose regret is denoted by
$R_{\mathcal{L}^{\mathcal{K}}}(t)=\mathcal{O}(t^{\alpha_{1}})$, we obtain
directly

$\displaystyle\sum_{s=n_{0}+1}^{t}g_{s}\left(w_{s}^{\mathcal{L}^{\mathcal{K}}}\right)\geq\max_{w\in\triangle_{K}}\sum_{s=n_{0}+1}^{t}g_{s}(w)-R_{\mathcal{L}^{\mathcal{K}}}(t)$

##### Step 5. From the optimal gain to $T_{\varepsilon}(\mu)^{-1}$.

Dropping the first positive terms and the ones for which the good event
$A_{s}\buildrel\text{def}\over{=}\left\\{\lambda_{s}\in\neg_{\varepsilon}z_{F}(\mu)\lor\mu_{s-1}\in\neg_{\varepsilon}z_{F}(\mu)\lor\tilde{z}_{s}=z_{F}(\mu)\right\\}$
doesn’t hold, i.e. $\left\llbracket n_{0}+1,\left\lceil
t^{\frac{1}{1+b}}\right\rceil-1\right\rrbracket\cup\left\\{s\in\left\llbracket\left\lceil
t^{\frac{1}{1+b}}\right\rceil,t\right\rrbracket:\neg A_{s}\right\\}$, and
using Lemma E.18, we obtain: for all $w\in\triangle_{K}$,

$\displaystyle\sum_{s=n_{0}+1}^{t}g_{s}(w)\geq\sum_{s=\left\lceil
t^{\frac{1}{1+b}}\right\rceil}^{t}\mathbf{1}_{(A_{s})}g_{s}(w)$
$\displaystyle\geq\left(1-t^{-\frac{1}{1+b}}\right)\sum_{s=\left\lceil
t^{\frac{1}{1+b}}\right\rceil}^{t}\mathbf{1}_{(A_{s})}\langle w,U_{s}\rangle$
$\displaystyle\geq\left(1-t^{-\frac{1}{1+b}}\right)\sum_{s=\left\lceil
t^{\frac{1}{1+b}}\right\rceil}^{t}\mathbf{1}_{(A_{s})}\inf_{\lambda\in\neg_{\varepsilon}z_{F}(\mu)}\|\mu-\lambda\|^{2}_{V_{w}}$
$\displaystyle\geq\left(1-t^{-\frac{1}{1+b}}\right)\left(t-t^{\frac{1}{1+b}}-N_{F}(t)\right)\inf_{\lambda\in\neg_{\varepsilon}z_{F}(\mu)}\|\mu-\lambda\|^{2}_{V_{w}}$

where $\left|\left\\{s\in\left\llbracket\left\lceil
t^{\frac{1}{1+b}}\right\rceil,t\right\rrbracket:\neg A_{s}\right\\}\right|\leq
N_{F}(t)$ since $\\{\tilde{z}_{s}=z_{F}(\mu)\\}\subseteq A_{s}$, where
$N_{F}(t)$ defined in (24) satisfies
$N_{F}(t)=\mathcal{O}\left(\ln(t)^{2}t^{\frac{1}{1+b}}\right)$ (Lemma E.20).
For the last inequality, we also used that $-\left\lceil
t^{\frac{1}{1+b}}\right\rceil+1\geq-t^{\frac{1}{1+b}}$. Taking the maximum
over $\triangle_{K}$, we obtain:

$\displaystyle\max_{w\in\triangle_{K}}\sum_{s=n_{0}+1}^{t}g_{s}(w)$
$\displaystyle\geq\left(1-t^{-\frac{1}{1+b}}\right)\left(t-t^{\frac{1}{1+b}}-N_{F}(t)\right)\max_{w\in\triangle_{K}}\inf_{\lambda\in\neg_{\varepsilon}z_{F}(\mu)}\|\mu-\lambda\|^{2}_{V_{w}}$
$\displaystyle=2\left(1-t^{-\frac{1}{1+b}}\right)\left(t-t^{\frac{1}{1+b}}-N_{F}(t)\right)T_{\varepsilon}(\mu)^{-1}$
$\displaystyle\geq
2\left(t-t^{\frac{1}{1+b}}-N_{F}(t)-t^{1-\frac{1}{1+b}}\right)T_{\varepsilon}(\mu)^{-1}$

where the equality is obtained by definition of $z_{F}(\mu)$. The last
inequality is obtained by dropping some positive terms. Putting everything
together, we obtain:

$\displaystyle\sum_{s=n_{0}+1}^{t}g_{s}\left(w_{s}^{\mathcal{L}^{\mathcal{K}}}\right)\geq
2tT_{\varepsilon}(\mu)^{-1}-R_{\mathcal{L}^{\mathcal{K}}}(t)-h^{\prime\prime\prime}(t)$

where
$h^{\prime\prime\prime}(t)=2\left(t^{\frac{1}{1+b}}+N_{F}(t)+t^{1-\frac{1}{1+b}}\right)T_{\varepsilon}(\mu)^{-1}=\mathcal{O}\left(\ln(t)^{2}t^{\frac{1}{1+b}}+t^{\max\\{\frac{1}{1+b},1-\frac{1}{1+b}\\}}\right)$.
∎

Chaining the two inequalities in Lemma E.6 and Lemma E.7, we obtain directly
Lemma E.8. Therefore, the sampling rule in L$\varepsilon$BAI satisfies the
desired condition (18) for $\beta_{2}=1$ and
$\beta_{1}=1-\max\left\\{\frac{1}{2},\frac{1}{1+b},1-\frac{1}{1+b},\alpha_{1}\right\\}$.

######  Lemma E.8.

Let $\mathcal{L}^{\mathcal{Z}}$ be the $\mathcal{Z}$-oracle such that
$\tilde{z}_{s}\in z_{F}(\mu_{s-1})$. Let $\mathcal{L}^{\mathcal{K}}$ be a
learner with regret
$R_{\mathcal{L}^{\mathcal{K}}}(t)=\mathcal{O}(t^{\alpha_{1}})$ with
$\alpha_{1}\in(0,1)$ fed with optimistic gain $g_{s}(w)=(1-\frac{1}{s})\langle
w,U_{s}\rangle$ where $(U_{s})_{s\in\left\llbracket
n_{0}+1,t\right\rrbracket}$ defined in (21). Then, under $\mathcal{E}_{t}$ if
the algorithms does not stop at time $t+1$,

$\displaystyle\max_{z\in\mathcal{Z}}\inf_{\lambda\in\neg_{\varepsilon}z}\|\mu-\lambda\|^{2}_{V_{N_{t}}}\geq
2tT_{\varepsilon}(\mu)^{-1}-r(t)$

where
$r(t)=r_{1}(t)+r_{2}(t)=\tilde{\mathcal{O}}\left(t^{\max\\{\frac{1}{2},\frac{1}{1+b},1-\frac{1}{1+b},\alpha_{1}\\}}\right)$.

###  E.4 Summarized Proof

Combining the lemmas obtained in Appendix E.1, E.2 and E.3, we obtain directly
Theorem 4.1. Therefore, our algorithm L$\varepsilon$BAI provides
asymptotically optimal algorithms if instantiated properly.

######  Theorem (Theorem 4.1).

Let $\mathcal{L}^{\mathcal{K}}$ be a learner with sub-linear regret and
$\mathcal{L}^{\mathcal{Z}}$ be the $\mathcal{Z}$-oracle such that
$\tilde{z}_{s}\in z_{F}(\mu_{s-1})$. Let the recommendation rule be an
instantaneous furthest answer $z_{t}\in z_{F}(\mu_{t-1},N_{t-1})$ and the
stopping rule given by (5), both being either evaluated at each time $t$ or
with the sticky or lazy update schedule as described in Appendix E.2.1. Let
the stopping threshold $\beta(t,\delta)$ as in (6) and the exploration bonus
$f(t)\buildrel\text{def}\over{=}2\beta\left(t,t^{1/\alpha}\right)$. Then,
L$\varepsilon$BAI yields an $(\varepsilon,\delta)$-PAC algorithm and, for all
$\mu\in\mathcal{M}$ such that $|z_{F}(\mu)|=1$,

$\displaystyle\limsup_{\delta\rightarrow
0}\frac{\operatorname*{\mathbb{E}}_{\mu}\left[\tau_{\delta}\right]}{\ln\left(\frac{1}{\delta}\right)}\leq
T_{\varepsilon}(\mu)\>.$

###### Proof.

First, let’s prove the result for the stopping-recommendation pair with an
update at each time $t$. Combining Lemma E.5 and Lemma E.8, we obtain:

$\displaystyle 2\beta(t,\delta)$
$\displaystyle\geq\max_{z\in\mathcal{Z}}\inf_{\lambda\in\neg_{\varepsilon}z}\|\mu-\lambda\|^{2}_{V_{N_{t}}}-h_{\delta}(t)$
$\displaystyle\geq 2tT_{\varepsilon}(\mu)^{-1}-r(t)-h_{\delta}(t)$

where
$h_{\delta}(t)=\sqrt{8f(t)\beta(t,\delta)}+4f(t)=\Theta\left(\ln(t)+\sqrt{\ln\left(\frac{1}{\delta}\right)}\right)$
and
$r(t)=r_{1}(t)+r_{2}(t)=\tilde{\mathcal{O}}\left(t^{\max\\{\frac{1}{2},\frac{1}{1+b},1-\frac{1}{1+b},\alpha_{1}\\}}\right)$.
Therefore, our identification strategy is sample-efficient, i.e. it verifies
(11) with

$\displaystyle H_{\mu}\left(t,\delta\right)\geq
tT_{\varepsilon}(\mu)^{-1}\quad\quad\text{where
}H_{\mu}\left(t,\delta\right)=\beta(t,\delta)+\frac{1}{2}\left(r(t)+h_{\delta}(t)\right)=\mathcal{O}\left(t^{1-\beta_{1}}+\ln(1/\delta)^{1-\beta_{2}}\right)$

where
$\beta_{1}=1-\max\left\\{\frac{1}{2},\frac{1}{1+b},1-\frac{1}{1+b},\alpha_{1}\right\\}\in(0,1]$
and $\beta_{2}=\frac{1}{2}\in(0,1]$.

Combining Lemma 3.1 and Lemma E.4, we obtain directly that our
L$\varepsilon$BAI yields a $(\varepsilon,\delta)$-PAC and asymptotically
optimal algorithm.

When considering the computational relaxations of the update schemes called
sticky or lazy, the proof is identical as explained in Appendix E.2.1 and the
fact that Lemma 3.1 can also be used. ∎

##### Values of Parameters

In the proof above, the condition (11) holds for
$\beta_{1}=1-\max\left\\{\frac{1}{2},\frac{1}{1+b},1-\frac{1}{1+b},\alpha_{1}\right\\}$
and $\beta_{2}=\frac{1}{2}$. For AdaHedge (De Rooij et al., 2014), Lemma E.14
shows that $\alpha_{1}=\frac{1}{2}$. An optimal choice of parameter suggests
that $\frac{1}{1+b}=1-\frac{1}{1+b}$. Therefore, we choose $b=1$. Higher $b$
would imply more conservative optimistic gains. Therefore, we have shown that
the condition (11) holds for $\beta_{1}=\beta_{2}=\frac{1}{2}$. As done in
Degenne et al. (2020a), we can choose $\alpha=3$ in the definition of the
exploration bonus $f(t)=2\beta\left(t,t^{1/\alpha}\right)$. The higher
$\alpha$, the higher the exploration bonus is.

###  E.5 Technical Arguments

In this appendix, we list and prove the technical arguments used in the core
of the proof of Theorem 4.1. For clarity, we distinguish between the lemmas
extracted from the literature (Appendix E.5.1), the key new lemmas (Appendix
E.5.2) and the technical ones allowing to upper bound the considered
cumulative sums (Appendix E.5.3).

####  E.5.1 Lemmas From the Literature

We recall the lemmas extracted from the literature, while omitting the proofs
for the sake of space. Lemma E.9 is a powerful result allowing to upper and
lower bound the difference between the empirical allocation over arms and the
cumulative sum of the played proportions when using tracking. Lemma E.10 and
Lemma E.11 are technical results on manipulation of inequalities and
cumulative sums. Lemma E.13 shows that $\mu\mapsto z_{F}(\mu)$ is upper
hemicontinuous on $\mathcal{M}$. Upper hemicontinuity is defined in Definition
E.12. Lemma E.14 gives an upper bound on the regret incurred by AdaHedge.

######  Lemma E.9 (Theorem 6 in Degenne et al. (2020b)).

The tracking procedure, which draws
$a_{t}\in\operatorname*{arg\,min}_{a\in\mathcal{K}}N_{t-1}^{a}-W_{t}^{a}$
where $W_{t}=W_{t-1}+w_{t}$, ensures that for all $t\in\mathbb{N}$, for all
$a\in\mathcal{K}$,

$\displaystyle-\sum_{j=2}^{K}\frac{1}{j}\leq N_{t}^{a}-W_{t}^{a}\leq 1$

In practice, we will use the following slightly coarser lower bound
$-\ln(K)\leq N_{t}^{a}-W_{t}^{a}$.

######  Lemma E.10 (Lemma 28 in Degenne et al. (2020a)).

For all $\alpha,y>0$, if for some $x\geq 0$, it holds that $y\geq
x-\alpha\sqrt{x}$, then $x\leq y+\alpha\sqrt{y}+\alpha^{2}$ .

######  Lemma E.11 (Lemma 8 in Degenne et al. (2019)).

For $t\geq t_{0}\geq 1$ and $(x_{s})_{s\in[t]}$ non-negative real numbers such
that $\sum_{s=1}^{t_{0}-1}x_{s}>0$,

$\displaystyle\sum_{s=t_{0}}^{t}\frac{x_{s}}{\sum_{r=1}^{s}x_{r}}\leq\ln\left(\sum_{s=1}^{t}x_{s}\right)-\ln\left(\sum_{s=1}^{t_{0}-1}x_{s}\right)$
$\displaystyle\sum_{s=t_{0}}^{t}\frac{x_{s}}{\sqrt{\sum_{r=1}^{s}x_{r}}}\leq
2\sqrt{\sum_{s=1}^{t}x_{s}}-2\sqrt{\sum_{s=1}^{t_{0}-1}x_{s}}$

######  Definition E.12 (Upper hemicontinuity).

For a set $B$, let $\mathbb{S}(B)=2^{B}\setminus\\{\emptyset\\}$ be the set of
all non-empty subsets of $B$. A set-valued function
$\Gamma:A\mapsto\mathbb{S}(B)$ is upper hemicontinuous at $a\in A$ if for any
open neighborhood $V$ of $\Gamma(a)$ there exists a neighborhood $U$ of $a$
such that for all $x\in U$, $\Gamma(x)$ is a subset of $V$.

######  Lemma E.13 (Theorem 4 in Degenne & Koolen (2019)).

The function $\mu\mapsto z_{F}(\mu)$ is upper hemicontinuous on
$\mathbb{R}^{d}$ with non-empty and compact values.

###### Proof.

Theorem 4 in Degenne & Koolen (2019) proves that the function $\mu\mapsto
z_{F}(\mu)$ is upper hemicontinuous on $\mathcal{M}$ with non-empty and
compact values. In their paper the function $\mu\mapsto z_{F}(\mu)$ was only
defined on $\mathcal{M}$. However, a careful analysis of their Appendix D
reveals that their result and proof apply without any change when $\mu\mapsto
z_{F}(\mu)$ is defined on $\mathbb{R}^{d}$. Since in our setting $z_{F}(\mu)$
is defined on $\mathbb{R}^{d}$, this concludes the proof. Note that while
$\mu\mapsto z_{F}(\mu)$ is defined on $\mathcal{M}$, the alternatives
$(\neg_{\varepsilon}z)_{z\in\mathcal{Z}}$ are all subsets of
$\overline{\mathcal{M}}$. ∎

######  Lemma E.14.

On the online learning problem with $K$ arms and gains
$g_{s}(w)=(1-\frac{1}{s})\langle w,U_{s}\rangle$ for $s\in\left\llbracket
n_{0}+1,t\right\rrbracket$, AdaHedge predicting
$\left(w_{s}^{\mathcal{L}^{\mathcal{K}}}\right)_{s\in\left\llbracket
n_{0}+1,t\right\rrbracket}$ has regret

$\displaystyle R_{\mathcal{L}^{\mathcal{K}}}(t)$
$\displaystyle=\max_{w\in\triangle_{K}}\sum_{s=n_{0}+1}^{t}g_{s}(w)-g_{s}\left(w_{s}^{\mathcal{L}^{\mathcal{K}}}\right)\leq\left(\sqrt{t\ln(K)}+\frac{4}{3}\ln(K)+2\right)\sigma=\mathcal{O}\left(\sqrt{t}\right)$

where $\sigma=\max_{s\in\left\llbracket
n_{0}+,t\right\rrbracket}(1-\frac{1}{s})\left(\max_{a\in\mathcal{K}}U_{s}^{a}-\min_{a\in\mathcal{K}}U_{s}^{a}\right)$.

###### Proof.

For scaled losses in $[0,1]$, Theorem 6 in De Rooij et al. (2014) yields that
AdaHedge’s cumulative regret $R_{t}$ satisfies: $R_{t}\leq
2\sqrt{V_{t}\ln(K)}+\frac{4}{3}\ln(K)+2$ where $V_{t}=\sum_{s\in[t]}v_{s}$
with
$v_{s}=\sum_{a\in\mathcal{K}}w_{s,a}^{\mathcal{L}^{\mathcal{K}}}(l_{s}^{a}-\langle
w_{s}^{\mathcal{L}^{\mathcal{K}}},l_{s}\rangle)^{2}$.

Rewriting our gains as losses, we have
$l_{s}^{a}=(1-\frac{1}{s})\frac{\max_{b\in\mathcal{K}}U_{s}^{b}-U_{s}^{a}}{b_{s}}$
where
$b_{s}=(1-\frac{1}{s})\left(\max_{a\in\mathcal{K}}U_{s}^{a}-\min_{a\in\mathcal{K}}U_{s}^{a}\right)$
is the scale of the loss at time $s$. We have $v_{s}\leq\|l_{s}-\langle
w_{s}^{\mathcal{L}^{\mathcal{K}}},l_{s}\rangle\|_{\infty}^{2}=(1-\frac{1}{s})^{2}\frac{\|\langle
w_{s}^{\mathcal{L}^{\mathcal{K}}},U_{s}\rangle-
U_{s}\|_{\infty}^{2}}{b_{s}^{2}}\leq\frac{b_{s}^{2}}{\sigma^{2}}$ where
$\sigma=\max_{s\in\left\llbracket n_{0}+,t\right\rrbracket}b_{s}$. The upper
bound on $R_{t}$ rewrites as: $R_{t}\leq\frac{1}{\sigma}\sqrt{\sum_{s\leq
t}b_{s}^{2}\ln(K)}+\frac{4}{3}\ln(K)+2$. Theorem 16 in De Rooij et al. (2014)
yields that $R_{\mathcal{L}^{\mathcal{K}}}(t)=\sigma R_{t}$. Therefore, we
conclude that:

$\displaystyle R_{\mathcal{L}^{\mathcal{K}}}(t)$
$\displaystyle\leq\sqrt{\sum_{s\in\left\llbracket
n_{0}+,t\right\rrbracket}b_{s}^{2}\ln(K)}+\left(\frac{4}{3}\ln(K)+2\right)\max_{s\in\left\llbracket
n_{0}+,t\right\rrbracket}b_{s}\leq\left(\sqrt{t\ln(K)}+\left(\frac{4}{3}\ln(K)+2\right)\right)\max_{s\in\left\llbracket
n_{0}+,t\right\rrbracket}b_{s}$

Using the definition of $U_{s}^{a}$ and Lemma E.17, we obtain:

$\displaystyle
b_{s}\leq\max_{a\in\mathcal{K}}U_{s}^{a}\leq\max_{a\in\mathcal{K}}\left(\|\mu_{s-1}-\lambda_{s}\|^{2}_{aa^{\mathsf{\scriptscriptstyle
T}}}+c_{s-1}^{a}+4ML_{\mathcal{K}}\sqrt{c_{s-1}^{a}}\right)\leq
16M^{2}L_{\mathcal{K}}^{2}$

where the last inequality is obtained by the boundedness assumption and the
definition of $c_{s}^{a}$. ∎

We also recall a trivial result obtained by comparison of sum and integrals:
for all $\alpha\in(0,1)$ and all $t\in\mathbb{N}^{\star}$,
$\sum_{s\in[t]}\frac{1}{s^{\alpha}}=\Theta(t^{1-\alpha})$.

####  E.5.2 Key Lemmas

The following lemmas are key arguments used throughout Appendix E. Lemma E.15
is a simple, yet powerful, result allowing to change the considered
alternatives. This subtlety arises only because we are considering multiple
correct answers.

######  Lemma E.15.

For all $w\in\mathbb{R}_{+}^{K}$, $\mu\in\mathcal{M}$ and
$\tilde{z}\in\mathcal{Z}$,

$\displaystyle\max_{z\in\mathcal{Z}}\inf_{\lambda\in\neg_{\varepsilon}z}\|\mu-\lambda\|^{2}_{V_{w}}\geq\inf_{\lambda\in\neg_{\varepsilon}\tilde{z}}\|\mu-\lambda\|^{2}_{V_{w}}\>.$

In particular, for all $(w,\tilde{w})\in(\mathbb{R}_{+}^{K})^{2}$ and
$(\mu,\tilde{\mu})\in\mathcal{M}^{2}$,

$\displaystyle\max_{z\in\mathcal{Z}}\inf_{\lambda\in\neg_{\varepsilon}z}\|\mu-\lambda\|^{2}_{V_{w}}\geq\max_{\tilde{z}\in
z_{F}(\tilde{\mu},\tilde{w})}\inf_{\lambda\in\neg_{\varepsilon}\tilde{z}}\|\mu-\lambda\|^{2}_{V_{w}}\>.$

###### Proof.

Case 1: $\tilde{z}\notin\mathcal{Z}_{\varepsilon}(\mu)$, hence
$\mu\in\neg_{\varepsilon}\tilde{z}$. Therefore
$\inf_{\lambda\in\neg_{\varepsilon}\tilde{z}}\|\mu-\lambda\|^{2}_{V_{w}}=0$.
Case 2: $\tilde{z}\in\mathcal{Z}_{\varepsilon}(\mu)$. The result is direct by
taking the maximum. ∎

Lemma E.16 shows that the slacks $(c_{s}^{a})_{s\in\left\llbracket\lceil
t^{\frac{1}{1+b}}\rceil,t-1\right\rrbracket,a\in\mathcal{K}}$ are an upper
bound of the unknown distance
$\|\mu-\mu_{s}\|^{2}_{aa^{\mathsf{\scriptscriptstyle T}}}$.

######  Lemma E.16.

Let $(c_{s}^{a})_{s\in\left\llbracket
n_{0},t-1\right\rrbracket,a\in\mathcal{K}}$ in (20). Under $\mathcal{E}_{t}$,
for all $(s,a)\in\left\llbracket\lceil
t^{\frac{1}{1+b}}\rceil,t-1\right\rrbracket\times\mathcal{K}$,
$\|\mu-\mu_{s}\|^{2}_{aa^{\mathsf{\scriptscriptstyle T}}}\leq c_{s}^{a}$.

###### Proof.

Since $(\mu,\mu_{s})\in\mathcal{M}^{2}$, the boundedness yields:
$\|\mu-\mu_{s}\|^{2}_{aa^{\mathsf{\scriptscriptstyle
T}}}=\langle\mu-\mu_{s},a\rangle^{2}\leq\|\mu-\mu_{s}\|_{2}^{2}\|a\|_{2}^{2}\leq
4M^{2}L_{\mathcal{K}}^{2}$.

By definition, under $\mathcal{E}_{t}$, for all $s\in[t]$, we have
$\|\mu_{s}-\mu\|^{2}_{V_{N_{s}}}\leq f(t)$. Since $x\mapsto f(x)$ is
increasing, for all $s\geq\lceil t^{\frac{1}{1+b}}\rceil$, we have $f(t)\leq
f\left(s^{1+b}\right)$. By initialization $V_{N_{s}}$ is positive definite,
using Cauchy-Schwartz yields:

$\displaystyle\langle\mu-\mu_{s},a\rangle^{2}\leq\|\mu_{s}-\mu\|^{2}_{V_{N_{s}}}\|a\|^{2}_{V_{N_{s}}^{-1}}\leq
f\left(s^{1+b}\right)\|a\|^{2}_{V_{N_{s}}^{-1}}$

Combining both upper bound and using the definition of
$(c_{s}^{a})_{s\in\left\llbracket n_{0},t-1\right\rrbracket,a\in\mathcal{K}}$
in (20) conclude the proof. ∎

Lemma E.17 shows useful upper and lower bounds on the optimistic gains
$(U_{s}^{a})_{s\in\left\llbracket n_{0}+1,t\right\rrbracket,a\in\mathcal{K}}$.

######  Lemma E.17.

Let $b>0$, $(c_{s-1}^{a})_{s\in\left\llbracket
n_{0}+1,t\right\rrbracket,a\in\mathcal{K}}$ and
$(U_{s}^{a})_{s\in\left\llbracket n_{0}+1,t\right\rrbracket,a\in\mathcal{K}}$
defined in (20-21). For all $s\in\left\llbracket n_{0}+1,t\right\rrbracket$,
for all $a\in\mathcal{K}$,

$\displaystyle\|\mu_{s-1}-\lambda_{s}\|^{2}_{aa^{\mathsf{\scriptscriptstyle
T}}}\leq
U_{s}^{a}\leq\|\mu_{s-1}-\lambda_{s}\|^{2}_{aa^{\mathsf{\scriptscriptstyle
T}}}+c_{s-1}^{a}+4ML_{\mathcal{K}}\sqrt{c_{s-1}^{a}}\>.$

For all $s\in\left\llbracket\left\lceil
t^{\frac{1}{1+b}}\right\rceil,t\right\rrbracket$, for all $a\in\mathcal{K}$,
$U_{s}^{a}\geq\|\mu_{s-1}-\mu\|^{2}_{aa^{\mathsf{\scriptscriptstyle T}}}$ and
$U_{s}^{a}\geq\|\mu-\lambda_{s}\|^{2}_{aa^{\mathsf{\scriptscriptstyle T}}}$.

###### Proof.

By definition of $U_{s}^{a}$ in (21) and using the boundedness to show
$\|\mu_{s-1}-\lambda_{s}\|_{aa^{\mathsf{\scriptscriptstyle T}}}\leq
2ML_{\mathcal{K}}$, we have: for all $s\in\left\llbracket
n_{0}+1,t\right\rrbracket$, for all $a\in\mathcal{K}$,

$\displaystyle U_{s}^{a}$
$\displaystyle=\|\mu_{s-1}-\lambda_{s}\|^{2}_{aa^{\mathsf{\scriptscriptstyle
T}}}+c_{s-1}^{a}+2\|\mu_{s-1}-\lambda_{s}\|_{aa^{\mathsf{\scriptscriptstyle
T}}}\sqrt{c_{s-1}^{a}}\geq\|\mu_{s-1}-\lambda_{s}\|^{2}_{aa^{\mathsf{\scriptscriptstyle
T}}}$ $\displaystyle U_{s}^{a}$
$\displaystyle\leq\|\mu_{s-1}-\lambda_{s}\|^{2}_{aa^{\mathsf{\scriptscriptstyle
T}}}+c_{s-1}^{a}+4ML_{\mathcal{K}}\sqrt{c_{s-1}^{a}}$

By definition of $U_{s}^{a}$ in (21), Lemma E.16 and triangular inequality, we
have: for all $s\in\left\llbracket\left\lceil
t^{\frac{1}{1+b}}\right\rceil,t\right\rrbracket$, for all $a\in\mathcal{K}$,

$\displaystyle U_{s}^{a}$
$\displaystyle=\left(\|\mu_{s-1}-\lambda_{s}\|_{aa^{\mathsf{\scriptscriptstyle
T}}}+\sqrt{c_{s-1}^{a}}\right)^{2}\geq\left(\|\mu_{s-1}-\lambda_{s}\|_{aa^{\mathsf{\scriptscriptstyle
T}}}+\|\mu_{s-1}-\mu\|_{aa^{\mathsf{\scriptscriptstyle
T}}}\right)^{2}\geq\|\mu-\lambda_{s}\|^{2}_{aa^{\mathsf{\scriptscriptstyle
T}}}$ $\displaystyle U_{s}^{a}$ $\displaystyle\geq
c_{s-1}^{a}\geq\|\mu_{s-1}-\mu\|^{2}_{aa^{\mathsf{\scriptscriptstyle T}}}$

∎

Lemma E.18 shows that under a good event $A_{s}$ the gain $\langle
w,U_{s}\rangle$ is an upper bound on the unknown
$\inf_{\lambda\in\neg_{\varepsilon}z_{F}(\mu)}\|\mu-\lambda\|^{2}_{V_{w}}$ for
all $w\in\triangle_{K}$. This good event essentially boils down to having as
candidate answer the unknown furthest answer $\tilde{z}_{s}=z_{F}(\mu)$.

######  Lemma E.18.

Let $b>0$ as in Lemma E.17. Let $(A_{s})_{s\in\left\llbracket\left\lceil
t^{\frac{1}{1+b}}\right\rceil,t\right\rrbracket}$ defined as: for all
$s\in\left\llbracket\left\lceil
t^{\frac{1}{1+b}}\right\rceil,t\right\rrbracket$,

$A_{s}\buildrel\text{def}\over{=}\left\\{\lambda_{s}\in\neg_{\varepsilon}z_{F}(\mu)\lor\mu_{s-1}\in\neg_{\varepsilon}z_{F}(\mu)\lor\tilde{z}_{s}=z_{F}(\mu)\right\\}$
(22)

Under $\mathcal{E}_{t}$, we have for all $w\in\triangle_{K}$ and
$s\in\left\llbracket\left\lceil
t^{\frac{1}{1+b}}\right\rceil,t\right\rrbracket$, under $A_{s}$ it holds that

$\displaystyle\langle
w,U_{s}\rangle\geq\inf_{\lambda\in\neg_{\varepsilon}z_{F}(\mu)}\|\mu-\lambda\|^{2}_{V_{w}}$

###### Proof.

Summing the lower bound of Lemma E.17 yields: for all
$s\in\left\llbracket\left\lceil
t^{\frac{1}{1+b}}\right\rceil,t\right\rrbracket$ and all $w\in\triangle_{K}$,
$\langle w,U_{s}\rangle\geq\|\mu-\lambda_{s}\|^{2}_{V_{w}}$ and $\langle
w,U_{s}\rangle\geq\|\mu-\mu_{s-1}\|^{2}_{V_{w}}$.

##### Case 1: $\lambda_{s}\in\neg_{\varepsilon}z_{F}(\mu)$.

Taking the infimum on the first inequality, we have: for all
$s\in\left\llbracket\left\lceil
t^{\frac{1}{1+b}}\right\rceil,t\right\rrbracket$ and all $w\in\triangle_{K}$,

$\langle
w,U_{s}\rangle\geq\inf_{\lambda\in\neg_{\varepsilon}z_{F}(\mu)}\|\mu-\lambda\|^{2}_{V_{w}}$

##### Case 2: $\mu_{s-1}\in\neg_{\varepsilon}z_{F}(\mu)$.

Taking the infimum on the second inequality, we obtain directly: for all
$w\in\triangle_{K}$ and $s\geq t^{\frac{1}{1+b}}$,

$\langle
w,U_{s}\rangle\geq\inf_{\lambda\in\neg_{\varepsilon}z_{F}(\mu)}\|\mu-\lambda\|^{2}_{V_{w}}$

##### Case 3: $\tilde{z}_{s}=z_{F}(\mu)$.

By definition $\lambda_{s}\in\neg_{\varepsilon}\tilde{z}_{s}$, hence
$\lambda_{s}\in\neg_{\varepsilon}z_{F}(\mu)$. Therefore, we can use the first
case. ∎

We introduce a strictly positive geometrical quantity $\Delta_{\min}^{2}$ (23)
in Lemma E.19. This result crucially uses that $\mathcal{Z}$ is finite and
$|z_{F}(\mu)|=1$ for the unknown parameter $\mu$. It means that we can’t be
arbitrarily close to $\mu$ while having a unique furthest answer which is
different from $z_{F}(\mu)$.

$\Delta_{\min}^{2}$ represents the distance of $\mu$ to the furthest
alternative to $z_{F}(\mu)$, denoted by $\neg_{F}z_{F}(\mu)$. The furthest
alternative is fundamentally different from the alternative
$\neg_{\varepsilon}z_{F}(\mu)$ (which is considered in the rest of the paper).
While the furthest alternative corresponds to an identification problem with a
unique correct answer, the alternative corresponds to an identification
problem with multiple correct answers. Therefore, we see that to achieve
asymptotic optimality in this multiple correct answer setting, we need to
solve the harder problem of exactly identifying the unique $z_{F}(\mu)$.

######  Lemma E.19.

Defining

$\Delta_{\min}^{2}\buildrel\text{def}\over{=}\inf_{\lambda\in\neg_{F}z_{F}(\mu)}\max_{a\in\mathcal{K}}\|\mu-\lambda\|_{aa^{\mathsf{\scriptscriptstyle
T}}}^{2}>0$ (23)

where
$\neg_{F}z_{F}(\mu)\buildrel\text{def}\over{=}\left\\{\lambda\in\mathbb{R}^{d}:z_{F}(\mu)\neq
z_{F}(\lambda)\right\\}$. Then, we have: $\Delta_{\min}^{2}>0$.

###### Proof.

By Lemma E.13, we know that $\lambda\mapsto z_{F}(\lambda)$ is upper
hemicontinuous on $\mathbb{R}^{d}$ with non-empty and compact values. Since
$\mathcal{Z}$ is finite and $z_{F}(\mu)$ is a singleton by assumption on
$\mu$, the upper hemicontinuity implies that there exists an open a
neighborhood $U$ of $\mu$ such that for all $\tilde{\mu}\in U$,
$z_{F}(\tilde{\mu})=z_{F}(\mu)$. This is obtained directly by using Definition
E.12 and taking an open neighborhood $V$ of $z_{F}(\mu)$ such that
$V\cap\mathcal{Z}=z_{F}(\mu)$, which exists since $|z_{F}(\mu)|=1$ and
$\mathcal{Z}$ finite. Noticing that
$U\subseteq(\neg_{F}z_{F}(\mu))^{\complement}$ and using that $U$ is an open
neighborhood of $\mu$, we can conclude that $\Delta_{\min}^{2}>0$. ∎

Lemma E.20 shows that the good event $\\{\tilde{z}_{s}=z_{F}(\mu)\\}\subseteq
A_{s}$ doesn’t happen only for a sub-linear number of times. A similar
argument was shown in Lemma 25 of Degenne et al. (2020a). This crucially uses
the fact that $\Delta_{\min}^{2}>0$.

######  Lemma E.20.

Let $\mathcal{L}^{\mathcal{Z}}$ be the $\mathcal{Z}$-oracle such that
$\tilde{z}_{s}\in z_{F}(\mu_{s-1})$. For all $s\in\left\llbracket\left\lceil
t^{\frac{1}{1+b}}\right\rceil,t\right\rrbracket$, let

$B_{s}\buildrel\text{def}\over{=}\\{\tilde{z}_{s}=z_{F}(\mu)\\}\quad\text{and}\quad
N_{F}(t)\buildrel\text{def}\over{=}\left|\left\\{s\in\left\llbracket\left\lceil
t^{\frac{1}{1+b}}\right\rceil,t\right\rrbracket:\neg B_{s}\right\\}\right|\>.$
(24)

Then, under $\mathcal{E}_{t}$,

$\displaystyle
N_{F}(t)\leq\frac{K}{\Delta_{\min}^{2}}t^{\frac{1}{1+b}}f\left(t^{1+b}\right)\left(K\ln(K)+2K\ln(t)\right)=\mathcal{O}\left(\ln(t)^{2}t^{\frac{1}{1+b}}\right)$

###### Proof.

Using Lemma E.25, under $\mathcal{E}_{t}$,

$\displaystyle
f\left(t^{1+b}\right)\left(K\ln(K)+2K\ln(t)\right)\geq\sum_{s=\left\lceil
t^{\frac{1}{1+b}}\right\rceil}^{t}\|\mu_{s-1}-\mu\|^{2}_{V_{w_{s}}}$
$\displaystyle\geq\sum_{s=\left\lceil
t^{\frac{1}{1+b}}\right\rceil}^{t}\mathbf{1}_{(\neg
B_{s})}\|\mu_{s-1}-\mu\|^{2}_{V_{w_{s}}}$
$\displaystyle\geq\sum_{s=\left\lceil
t^{\frac{1}{1+b}}\right\rceil}^{t}\mathbf{1}_{(\neg
B_{s})}\frac{1}{sK}\sum_{a\in\mathcal{K}}\|\mu_{s-1}-\mu\|^{2}_{aa^{\mathsf{\scriptscriptstyle
T}}}$

where the last inequality is obtained since
$w_{s}=\frac{1}{sK}\mathbf{1}_{K}+\left(1-\frac{1}{s}\right)w_{s}^{\mathcal{L}^{\mathcal{K}}}$
for all $s\in\left\llbracket n_{0}+1,t\right\rrbracket$.

Since $B_{s}=\\{\tilde{z}_{s}=z_{F}(\mu)\\}$ and $\tilde{z}_{s}\in
z_{F}(\mu_{s-1})$, we obtain:

$\displaystyle\neg B_{s}=\left\\{\tilde{z}_{s}\notin
z_{F}(\mu),\tilde{z}_{s}\in
z_{F}(\mu_{s-1})\right\\}\subseteq\left\\{z_{F}(\mu_{s-1})\neq
z_{F}(\mu)\right\\}$

where in the above $z_{F}(\mu)$ is viewed as the set containing one element.
Therefore, since $\mu_{s-1}\in\mathbb{R}^{d}$ and $z_{F}(\mu_{s-1})\neq
z_{F}(\mu)$, we have shown that $\mu_{s-1}\in\neg_{F}z_{F}(\mu)$. By the
definition of $\Delta_{\min}^{2}$ in (23), there exists $a_{s}\in\mathcal{K}$
such that $\|\mu_{s-1}-\mu\|^{2}_{a_{s}a_{s}^{\mathsf{\scriptscriptstyle
T}}}\geq\Delta_{\min}^{2}$. This yields
$\sum_{a\in\mathcal{K}}\|\mu_{s-1}-\mu\|^{2}_{aa^{\mathsf{\scriptscriptstyle
T}}}\geq\Delta_{\min}^{2}$. Therefore, we obtain:
$\frac{1}{s}\sum_{a\in\mathcal{K}}\|\mu_{s-1}-\mu\|^{2}_{aa^{\mathsf{\scriptscriptstyle
T}}}\geq\frac{\Delta_{\min}^{2}}{s}\geq\frac{\Delta_{\min}^{2}}{t^{\frac{1}{1+b}}}$
for all $s\in\left\llbracket\left\lceil
t^{\frac{1}{1+b}}\right\rceil,t\right\rrbracket$. Putting everything together,
we have shown that:

$\displaystyle
N_{F}(t)\leq\frac{K}{\Delta_{\min}^{2}}t^{\frac{1}{1+b}}f\left(t^{1+b}\right)\left(K\ln(K)+2K\ln(t)\right)$

∎

######  Lemma E.21.

Let $\mathcal{L}^{\mathcal{Z}}$ be the $\mathcal{Z}$-oracle such that
$\tilde{z}_{s}\in z_{F}(\mu_{s-1})$. Then, under $\mathcal{E}_{t}$,

$\min_{z\in\mathcal{Z}}\sum_{s=n_{0}+1}^{t}[f_{s}(\tilde{z}_{s})-f_{s}(z)]\leq\left(N_{F}(t)+t^{\frac{1}{1+b}}\right)4KM^{2}L_{\mathcal{K}}^{2}=\mathcal{O}\left(\ln(t)^{2}t^{\frac{1}{1+b}}\right)\>,$

where
$f_{s}(z)=\inf_{\lambda\in\neg_{\varepsilon}z}\|\mu_{s-1}-\lambda\|^{2}_{V_{w_{s}}}$.

###### Proof.

Let $B_{s}$ as in (24) for all $s\in\left\llbracket\left\lceil
t^{\frac{1}{1+b}}\right\rceil,t\right\rrbracket$. Since $f_{s}(z)\geq 0$, we
can drop the the first positive terms and the ones for which the good event
$B_{s}$ doesn’t hold, i.e. $\left\llbracket n_{0}+1,\left\lceil
t^{\frac{1}{1+b}}\right\rceil-1\right\rrbracket\cup\left\\{s\in\left\llbracket\left\lceil
t^{\frac{1}{1+b}}\right\rceil,t\right\rrbracket:\neg B_{s}\right\\}$, hence

$\displaystyle\min_{z\in\mathcal{Z}}\sum_{s=n_{0}+1}^{t}[f_{s}(\tilde{z}_{s})-f_{s}(z)]$
$\displaystyle\leq\min_{z\in\mathcal{Z}}\sum_{s\in\left\llbracket\left\lceil
t^{\frac{1}{1+b}}\right\rceil,t\right\rrbracket}\mathbf{1}_{(B_{s})}[f_{s}(\tilde{z}_{s})-f_{s}(z)]+\sum_{s\in\left\llbracket\left\lceil
t^{\frac{1}{1+b}}\right\rceil,t\right\rrbracket}\mathbf{1}_{(\neg
B_{s})}f_{s}(\tilde{z}_{s})+\sum_{s\in\left\llbracket n_{0}+1,\left\lceil
t^{\frac{1}{1+b}}\right\rceil-1\right\rrbracket}f_{s}(\tilde{z}_{s})$
$\displaystyle=\min_{z\in\mathcal{Z}}\sum_{s=n_{0}+1}^{t}\mathbf{1}_{(B_{s})}[f_{s}(z_{F}(\mu))-f_{s}(z)]+\sum_{s\in\left\llbracket\left\lceil
t^{\frac{1}{1+b}}\right\rceil,t\right\rrbracket}\mathbf{1}_{(\neg
B_{s})}f_{s}(\tilde{z}_{s})+\sum_{s\in\left\llbracket n_{0}+1,\left\lceil
t^{\frac{1}{1+b}}\right\rceil-1\right\rrbracket}f_{s}(\tilde{z}_{s})$
$\displaystyle\leq\sum_{s\in\left\llbracket\left\lceil
t^{\frac{1}{1+b}}\right\rceil,t\right\rrbracket}\mathbf{1}_{(\neg
B_{s})}f_{s}(\tilde{z}_{s})+\sum_{s\in\left\llbracket n_{0}+1,\left\lceil
t^{\frac{1}{1+b}}\right\rceil-1\right\rrbracket}f_{s}(\tilde{z}_{s})$

where we used that the best constant policy for $(f_{s})$ is by definition
better than the constant policy playing $z_{F}(\mu)$. By boundedness
assumption, we have $f_{s}(\tilde{z}_{s})\leq 4KM^{2}L_{\mathcal{K}}^{2}$ for
all $s$. Therefore, under $\mathcal{E}_{t}$,

$\displaystyle\min_{z\in\mathcal{Z}}\sum_{s=n_{0}+1}^{t}[f_{s}(\tilde{z}_{s})-f_{s}(z)]$
$\displaystyle\leq\left(N_{F}(t)+t^{\frac{1}{1+b}}\right)4KM^{2}L_{\mathcal{K}}^{2}=\mathcal{O}\left(\ln(t)^{2}t^{\frac{1}{1+b}}\right)\>.$

∎

####  E.5.3 Upper Bounding Cumulative Sums

Lemma E.22 is very similar to Lemma 9 in Degenne et al. (2019) and Lemma 15 in
Jourdan et al. (2021), the novelty lies in using Lemma E.9 to obtain tighter
upper bounds. It gives an upper bound on the cumulative sum of the reweighted
inverse of the empirical allocations.

######  Lemma E.22.

The tracking procedure, which draws
$a_{t}\in\operatorname*{arg\,min}_{a\in\mathcal{K}}N_{t-1}^{a}-W_{t}^{a}$
where $W_{t}=W_{t-1}+w_{t}$, ensures that for all $t\in\mathbb{N}$,

$\displaystyle\sum_{a\in\mathcal{K}}\sum_{s=n_{0}}^{t}\frac{w_{s}^{a}}{N_{s}^{a}}\leq
K\ln(K)+K\ln\left(t\right)\quad\quad\text{ and
}\quad\quad\sum_{a\in\mathcal{K}}\sum_{s=n_{0}+1}^{t}\frac{w_{s}^{a}}{N_{s-1}^{a}}\leq
K\ln(K)+2K\ln\left(t\right)$
$\displaystyle\sum_{a\in\mathcal{K}}\sum_{s=n_{0}}^{t}\frac{w_{s}^{a}}{\sqrt{N_{s}^{a}}}\leq
K\ln(K)+2\sqrt{Kt}\quad\quad\text{ and
}\quad\quad\sum_{a\in\mathcal{K}}\sum_{s=n_{0}+1}^{t}\frac{w_{s}^{a}}{N_{s-1}^{a}}\leq
K\ln(K)+2\sqrt{2Kt}$

###### Proof.

Let’s prove the first and the third inequality. Let $a\in\mathcal{K}$ and
$t_{0}^{a}$ be the first time such that:
$\sum_{s=1}^{t_{0}^{a}-1}w_{s}^{a}>\ln(K)-1$. Since $w_{t_{0}^{a}-1}^{a}\leq
1$, this yields $\sum_{s=1}^{t_{0}^{a}-1}w_{s}^{a}\leq\ln(K)$. Since
$N_{s}^{a}\geq 1$ for $s\geq n_{0}$, we obtain:

$\displaystyle\sum_{s=n_{0}}^{t}\frac{w_{s}^{a}}{N_{s}^{a}}=\sum_{s=n_{0}}^{t_{0}^{a}-1}\frac{w_{s}^{a}}{N_{s}^{a}}+\sum_{s=t_{0}^{a}}^{t}\frac{w_{s}^{a}}{N_{s}^{a}}\leq\sum_{s=n_{0}}^{t_{0}^{a}-1}w_{s}^{a}+\sum_{s=t_{0}^{a}}^{t}\frac{w_{s}^{a}}{N_{s}^{a}}\leq\ln(K)+\sum_{s=t_{0}^{a}}^{t}\frac{w_{s}^{a}}{N_{s}^{a}}$
$\displaystyle\sum_{s=n_{0}}^{t}\frac{w_{s}^{a}}{\sqrt{N_{s}^{a}}}=\sum_{s=n_{0}}^{t_{0}^{a}-1}\frac{w_{s}^{a}}{\sqrt{N_{s}^{a}}}+\sum_{s=t_{0}^{a}}^{t}\frac{w_{s}^{a}}{\sqrt{N_{s}^{a}}}\leq\sum_{s=n_{0}}^{t_{0}^{a}-1}w_{s}^{a}+\sum_{s=t_{0}^{a}}^{t}\frac{w_{s}^{a}}{\sqrt{N_{s}^{a}}}\leq\ln(K)+\sum_{s=t_{0}^{a}}^{t}\frac{w_{s}^{a}}{\sqrt{N_{s}^{a}}}$

Combining the Lemma E.9 and Lemma E.11 for $x_{s}=w_{s}^{a}$, we obtain:

$\displaystyle\sum_{s=t_{0}^{a}}^{t}\frac{w_{s}^{a}}{N_{s}^{a}}\leq\sum_{s=t_{0}^{a}}^{t}\frac{w_{s}^{a}}{\sum_{r=1}^{s}w_{r}^{a}-\ln(K)}\leq\ln\left(\sum_{s=1}^{t}w_{s}^{a}-\ln(K)\right)-\ln\left(\sum_{s=1}^{t_{0}^{a}-1}w_{s}^{a}-\ln(K)\right)$
$\displaystyle\sum_{s=t_{0}^{a}}^{t}\frac{w_{s}^{a}}{\sqrt{N_{s}^{a}}}\leq\sum_{s=t_{0}^{a}}^{t}\frac{w_{s}^{a}}{\sqrt{\sum_{r=1}^{s}w_{r}^{a}-\ln(K)}}\leq
2\sqrt{\sum_{s=1}^{t}w_{s}^{a}-\ln(K)}-2\sqrt{\sum_{s=1}^{t_{0}^{a}-1}w_{s}^{a}-\ln(K)}$

Since $\sum_{s=1}^{t_{0}^{a}-1}w_{s}^{a}>\ln(K)-1$, we have
$\ln\left(\sum_{s=1}^{t_{0}^{a}-1}w_{s}^{a}-\ln(K)\right)\geq 0$. Therefore,
we have shown:
$\sum_{s=t_{0}^{a}}^{t}\frac{w_{s}^{a}}{N_{s}^{a}}\leq\ln\left(\sum_{s=1}^{t}w_{s}^{a}\right)$
and $\sum_{s=t_{0}^{a}}^{t}\frac{w_{s}^{a}}{\sqrt{N_{s}^{a}}}\leq
2\sqrt{\sum_{s=1}^{t}w_{s}^{a}}$. By concavity of $x\mapsto\ln(x)$ (resp.
$x\mapsto\sqrt{x}$) and the fact that
$\sum_{s=1}^{t}\sum_{a\in\mathcal{K}}w_{s}^{a}=t$, we obtain:

$\displaystyle\sum_{a\in\mathcal{K}}\sum_{s=n_{0}}^{t}\frac{w_{s}^{a}}{N_{s}^{a}}\leq
K\ln(K)+K\ln\left(t\right)\quad\quad\text{ and
}\quad\quad\sum_{a\in\mathcal{K}}\sum_{s=n_{0}}^{t}\frac{w_{s}^{a}}{\sqrt{N_{s}^{a}}}\leq
K\ln(K)+2\sqrt{Kt}$

For all $s\geq n_{0}$, we have $N_{s-1}^{a}\geq 1$, hence
$N_{s-1}^{a}\geq\frac{1}{2}N_{s,a}$. Plugging this inequality in the sum
starting from $t_{0}^{a}$ yields:
$\sum_{a\in\mathcal{K}}\sum_{s=n_{0}+1}^{t}\frac{w_{s}^{a}}{N_{s-1}^{a}}\leq
K\ln(K)+2K\ln\left(t\right)$ and
$\sum_{a\in\mathcal{K}}\sum_{s=n_{0}}^{t}\frac{w_{s}^{a}}{\sqrt{N_{s-1}^{a}}}\leq
K\ln(K)+2\sqrt{2Kt}$. ∎

Lemma E.23 gives an upper bound on the norm of each arms once reweighted by
the inverse of the empirical allocation.

######  Lemma E.23.

For all $s\in\left\llbracket n_{0}+1,t\right\rrbracket$ and all
$a\in\mathcal{K}$, we have
$\|a\|^{2}_{V_{N_{s-1}}^{-1}}\leq\frac{1}{N_{s-1}^{a}}$.

###### Proof.

Recall that $\mathcal{K}$ is arbitrary and by initialization $N_{s-1}^{a}\geq
1$ for all $(s,a)\in\left\llbracket
n_{0}+1,t\right\rrbracket\times\mathcal{K}$. Let $a\in\mathcal{K}$. Let’s
rewrite $V_{N_{s-1}}=C_{s-1}^{a}+N_{s-1}^{a}aa^{\mathsf{\scriptscriptstyle
T}}$ where $C_{s-1}^{a}=\sum_{b\in\mathcal{K}:b\neq
a}N_{s-1}^{b}bb^{\mathsf{\scriptscriptstyle T}}$. If
$\mathcal{K}=\\{e_{a}\\}_{a\in[d]}$, we have directly that
$\|a\|^{2}_{V_{N}^{-1}}=\frac{1}{N^{a}}$. In the following, we consider the
more general case where $\mathcal{K}\neq\\{e_{a}\\}_{a\in[d]}$.

##### Case 1: $C_{s-1}^{a}$ is invertible.

Using the Sherman-Morrison formula, we obtain: for all $s\in\left\llbracket
n_{0}+1,t\right\rrbracket$ and all $a\in\mathcal{K}$

$\displaystyle
V_{N_{s-1}}^{-1}=(C_{s-1}^{a})^{-1}-N_{s-1}^{a}\frac{(C_{s-1}^{a})^{-1}aa^{\mathsf{\scriptscriptstyle
T}}(C_{s-1}^{a})^{-1}}{1+N_{s-1}^{a}a^{\mathsf{\scriptscriptstyle
T}}(C_{s-1}^{a})^{-1}a}$
$\displaystyle\|a\|^{2}_{V_{N_{s-1}}^{-1}}=a^{\mathsf{\scriptscriptstyle
T}}V_{N_{s-1}}^{-1}a=\frac{a^{\mathsf{\scriptscriptstyle
T}}(C_{s-1}^{a})^{-1}a}{1+N_{s-1}^{a}a^{\mathsf{\scriptscriptstyle
T}}(C_{s-1}^{a})^{-1}a}\leq\frac{1}{N_{s-1}^{a}}$

where for the last inequality, we used that $\frac{x}{1+xy}\leq\frac{1}{y}$
(since it is equivalent with $1+xy\geq xy$ which is true) for
$x=a^{\mathsf{\scriptscriptstyle T}}(C_{s-1}^{a})^{-1}a$ and $y=N_{s-1}^{a}$.

##### Case 2: $C_{s-1}^{a}$ is not invertible.

By initialization, we know that $V_{N_{s-1}}$ is invertible for all
$s\in\left\llbracket n_{0}+1,t\right\rrbracket$. Let
$u\in\text{Ker}(C_{s-1}^{a})\setminus\\{0_{d}\\}$. We have $N_{s-1}^{a}\langle
a,u\rangle a=V_{N_{s-1}}u\neq 0_{d}$ since $V_{N_{s-1}}$ is invertible and
$u\neq 0_{d}$. Given that $N_{s-1}^{a}>0$ (otherwise
$V_{N_{s-1}}=C_{s-1}^{a}$, hence contradiction with invertible), we obtain
that $\langle a,u\rangle>0$, hence $u\notin\text{Span}(a)^{\perp}$. By
dimension consideration, we obtain $\text{Span}(a)=\text{Ker}(C_{s-1}^{a})$.
This yields directly that $a$ is an eigenvector of $V_{N_{s-1}}$ with
eigenvalue $N_{s-1}^{a}\|a\|^{2}_{2}$. Therefore, $a$ is also an eigenvector
of $V_{N_{s-1}}^{-1}$ with eigenvalue $\frac{1}{N_{s-1}^{a}\|a\|^{2}_{2}}$ and
we can conclude: $a^{\mathsf{\scriptscriptstyle
T}}V_{N_{s-1}}^{-1}a=a^{\mathsf{\scriptscriptstyle
T}}\left(\frac{1}{N_{s-1}^{a}\|a\|^{2}_{2}}a\right)=\frac{1}{N_{s-1}^{a}}$. ∎

Lemma E.24 gives an upper bound on the cumulative sum of the reweighted slacks
involved in the optimistic reward.

######  Lemma E.24.

$\displaystyle\sum_{s=n_{0}+1}^{t}\sum_{a\in\mathcal{K}}w_{s}^{a}c_{s-1}^{a}$
$\displaystyle\leq f\left(t^{1+b}\right)\left(K\ln(K)+2K\ln(t)\right)$
$\displaystyle\sum_{s=n_{0}+1}^{t}\sum_{a\in\mathcal{K}}w_{s}^{a}\sqrt{c_{s-1}^{a}}$
$\displaystyle\leq\sqrt{f\left(t^{1+b}\right)}\left(K\ln(K)+\sqrt{8Kt}\right)$

###### Proof.

Using the definition of $c_{s}^{a}$ in (20), $f\left((s-1)^{1+b}\right)\leq
f\left(t^{1+b}\right)$ for all $s\leq t$, we obtain:

$\displaystyle\sum_{s=n_{0}+1}^{t}\sum_{a\in\mathcal{K}}w_{s}^{a}c_{s-1}^{a}\leq\sum_{s=n_{0}+1}^{t}\sum_{a\in\mathcal{K}}w_{s}^{a}f\left((s-1)^{1+b}\right)\|a\|^{2}_{V_{N_{s-1}}^{-1}}$
$\displaystyle\leq
f\left(t^{1+b}\right)\sum_{s=n_{0}+1}^{t}\sum_{a\in\mathcal{K}}w_{s}^{a}\|a\|^{2}_{V_{N_{s-1}}^{-1}}$
$\displaystyle\leq
f\left(t^{1+b}\right)\sum_{s=n_{0}+1}^{t}\sum_{a\in\mathcal{K}}\frac{w_{s}^{a}}{N_{s-1}^{a}}$
$\displaystyle\leq f\left(t^{1+b}\right)\left(K\ln(K)+2K\ln(t)\right)$

where the second to last inequality is obtained by Lemma E.23 and the last one
by Lemma E.22. Using the same arguments, we obtain:

$\displaystyle\sum_{s=n_{0}+1}^{t}\sum_{a\in\mathcal{K}}w_{s}^{a}\sqrt{c_{s-1}^{a}}\leq\sqrt{f\left(t^{1+b}\right)}\sum_{s=n_{0}+1}^{t}\sum_{a\in\mathcal{K}}w_{s}^{a}\|a\|_{V_{N_{s-1}}^{-1}}$
$\displaystyle\leq\sqrt{f\left(t^{1+b}\right)}\sum_{s=n_{0}+1}^{t}\sum_{a\in\mathcal{K}}\frac{w_{s}^{a}}{\sqrt{N_{s-1}^{a}}}$
$\displaystyle\leq\sqrt{f\left(t^{1+b}\right)}\left(K\ln(K)+\sqrt{8Kt}\right)$

∎

Lemma E.25 gives an upper bound on the cumulative sum of the reweighted KL
divergence between the true parameter and its MLE.

######  Lemma E.25.

Let $b>0$ as in (20). Under $\mathcal{E}_{t}$,

$\displaystyle\sum_{s=\left\lceil
t^{\frac{1}{1+b}}\right\rceil}^{t}\|\mu_{s-1}-\mu\|^{2}_{V_{w_{s}}}\leq
f\left(t^{1+b}\right)\left(K\ln(K)+2K\ln(t)\right)$

###### Proof.

Using Lemma E.16, we obtain:

$\displaystyle\sum_{s=\left\lceil
t^{\frac{1}{1+b}}\right\rceil}^{t}\|\mu_{s-1}-\mu\|^{2}_{V_{w_{s}}}=\sum_{s=\left\lceil
t^{\frac{1}{1+b}}\right\rceil}^{t}\sum_{a\in\mathcal{K}}w_{s}^{a}\|\mu_{s-1}-\mu\|^{2}_{aa^{\mathsf{\scriptscriptstyle
T}}}\leq\sum_{s=\left\lceil
t^{\frac{1}{1+b}}\right\rceil}^{t}\sum_{a\in\mathcal{K}}w_{s}^{a}c_{s-1}^{a}$
$\displaystyle\leq\sum_{s=n_{0}+1}^{t}\sum_{a\in\mathcal{K}}w_{s}^{a}c_{s-1}^{a}$
$\displaystyle\leq f\left(t^{1+b}\right)\left(K\ln(K)+2K\ln(t)\right)$

where the second inequality uses $w_{s}^{a}c_{s-1}^{a}\geq 0$ and the last
inequality is obtained by Lemma E.24. ∎

##  Appendix F Implementation Details and Additional Experiments

After presenting the implementations details in Appendix F.1, we display
supplementary experiments in Appendix F.2.

###  F.1 Implementation Details

##### Computational Cost of L$\varepsilon$BAI

When $\overline{\mathcal{M}}=\mathbb{R}^{d}$, the non-convex set of
alternatives can be rewritten as a union over $Z-1$ half-spaces, on which
there is a closed-form formula for the closest alternative of Lemma C.1.
Therefore, the stopping-recommendation pair has a computational cost in
$\mathcal{O}(Zd^{2}|\mathcal{Z}_{\varepsilon}(\mu_{t-1})|)$. For the heuristic
L$\varepsilon$BAI, i.e. $\tilde{z}_{t}=z_{t}$, the sampling rule has a
computational cost in $\mathcal{O}((K+Z)d^{2})$. Computing $z_{F}(\mu_{t-1})$
requires solving $|Z_{\varepsilon}(\mu_{t-1})|$ separate optimization
problems. Each one can be rewritten as an easier one-dimensional optimization
problem (Garivier & Kaufmann, 2016) which can be solved numerically by using
two nested binary searches. Our experiments testify of the feasibility of that
procedure.

##### Algorithm Implementations

We list below more clarifications on the exact implementation of each
individual algorithm.

  * •

The discretization of the simplex $\Delta_{2}$ and $\Delta_{4}$ (with $500$
and $10000$ vectors) is obtained by drawing uniformly vectors in the simplex,
in practice we used a Dirichlet distribution with parameters
$\frac{1}{2}\mathbf{1}_{2}$ and $\frac{1}{4}\mathbf{1}_{4}$.

  * •

The algorithms DKM, LinGame and L$\varepsilon$BAI are implemented without the
boundedness assumption. In practice, given
$(\mu,z,w,x)\in\mathcal{M}\times\mathcal{Z}_{\varepsilon}(\mu)\times\triangle_{K}\times\mathcal{Z}\setminus\\{z\\}$,
we used the closed-form formulas for the closest alternative
$\lambda_{0}(\mu,z,w,x)$ and $\lambda_{\varepsilon}(\mu,z,w,x)$ as detailed in
Appendix C.3.1.

  * •

We consider the greedy version of LinGapE, which does not have a theoretical
guarantee in the general case. We pull an arm with $z_{t}\in
z^{\star}(\mu_{t-1})$ and $x_{t}=\operatorname*{arg\,max}_{x\neq
z_{t}}\langle\mu_{t-1},x-z_{t}\rangle+\|x-z_{t}\|_{V^{-1}_{N_{t-1}}}\sqrt{2\beta(t-1,\delta)}$.

  * •

Likewise, we use the greedy version of $\mathcal{X}\mathcal{Y}$-Static in
order to avoid computing the optimal allocation at each step.

  * •

We set the hyper-parameter of $\mathcal{X}\mathcal{Y}$-Adaptive to $0.1$ as
done in Soare et al. (2014); Degenne et al. (2020a). It controls the length of
each phase.

##### Stopping Threshold

Instead of the stopping threshold (6) supported by the theory, we use as
heuristic
$\beta\left(t,\delta\right)=4\ln\left(\frac{4+\ln(t/2)}{\delta}\right)$, where
we take the main term and plug in $d$ instead of $K$. This is similar to what
we could obtain with a threshold tailored to linear bandits and featuring only
$d$. With this choice, the empirical error (number of runs such that
$\hat{z}\notin\mathcal{Z}_{\varepsilon}(\mu)$) is lower than the confidence
parameter $\delta$. Previous algorithms on BAI settings (Garivier & Kaufmann,
2016; Degenne et al., 2019, 2020a; Jourdan et al., 2021) were using
$\beta\left(t,\delta\right)=\ln\left(\frac{1+\ln(t)}{\delta}\right)$ as
heuristic for the stopping threshold. Interestingly, using this coarser
stopping threshold for $\varepsilon$-BAI leads to an empirical error which is
higher than $\delta$, violating the $(\varepsilon,\delta)$-PAC property.
Therefore, we need to be closer to the theoretically validated threshold.

An additional argument in favor of considering the same stopping rule for all
BAI algorithm can be seen in the choice of the stopping threshold itself. DKM
(Degenne et al., 2019) uses the concentration results in Garivier & Kaufmann
(2016), LinGame (Degenne et al., 2020a) the ones in (Lattimore & Szepesvári,
2020) and L$\varepsilon$BAI the ones in (Kaufmann & Koolen, 2021). Therefore,
a fair comparison of the sampling rule requires using the same
$\beta(t,\delta)$, as defined above.

##### Reproducibility

To assess our code and reproduce the experiments presented in this paper, you
need to unzip the provided code by running unzip code.zip. All the algorithms
and experiments are implemented in Julia 1.6.3 (but also run on Julia 1.1.1).
Plots were generated with the StatsPlots.jl package. Other dependencies are
listed in the Readme.md. The Readme.md file provides detailed julia
instructions to reproduce our experiments, as well as a script.sh to run them
all at once. The general structure of the code (and some functions) is taken
from the tidnabbil library.222This library was created by (Degenne et al.,
2019), see https://bitbucket.org/wmkoolen/tidnabbil. No license were available
on the repository, but we obtained the authorization from the authors.

###  F.2 Supplementary Experiments

Supplementary experiments for the multiplicative $\varepsilon$-optimality are
shown in Appendix F.2.1. The equivalent experiments for the additive
$\varepsilon$-optimality are displayed in Appendix F.2.2.

In the following, the hard/random instances that are considered are the same
as in Section 6. We consider the same choice of parameters:
$(\varepsilon,\delta)=(0.05,0.01)$, discretization of the simplex with $500$
(resp. $10000$) vectors when $K=2$ (resp. $K=4$), average (resp. standard
deviation) on $5000$ runs (resp. sub-samples of size $100$). Unless specified
otherwise, the recommendation rule and the $\mathcal{Z}$-oracle return an
instantaneous furthest answer, i.e. $z_{t}=\tilde{z}_{t}\in
z_{F}(\mu_{t-1},N_{t-1})$, and the stopping-recommendation pair is
updated/evaluated at each time $t$.

####  F.2.1 Multiplicative Optimality

Below, we present experiments on the multiplicative $\varepsilon$-optimality
that were conducted to highlight algorithmic choices.

Figure 5: Empirical stopping time of the modified BAI algorithms with
$z_{t}\in z_{F}(\mu_{t-1},N_{t-1})$ on the hard instance (star equals mean).
“-G” denotes when $z_{t}\in z^{\star}(\mu_{t-1})$.

##### Modified BAI

Figure 5 conveys the same message as Figure 2. For all modified BAI using (5),
considering an instantaneous furthest answer instead of a greedy answer leads
to lower empirical stopping time. Their ratio is $0.928$ on average (coherent
with Figure 1(b)). Note that the extension of LinGapE to the multiplicative
$\varepsilon$-optimality is not obtained directly as was done for the additive
setting, hence we didn’t displayed it.

Table 4: Empirical stopping time ($\pm$ $\sigma$) with their original stopping rule or with ours (5) on the hard instance ($\mathcal{K}=\mathcal{Z}$). The modified BAI algorithms use (5) with $z_{t}\in z_{F}(\mu_{t-1},N_{t-1})$. | LinGame | LinGapE |  $\mathcal{X}\mathcal{Y}$-Adaptive
---|---|---|---
Original |  $151473$ $(\pm 18082)$ |  $121716$ $(\pm 14771)$ |  $263806$ $(\pm 36896)$
Modified |  $423$ $(\pm 51)$ |  $414$ $(\pm 51)$ |  $399$ $(\pm 52)$

##### Original Stopping Rule

In Table 4, we displayed the difference between the empirical stopping time of
BAI algorithms using their original stopping rule and ours (5). Their stopping
time is $438$ times higher when using their original stopping rule which was
designed for an harder problem, i.e. identifying the unique best-answer which
is also an $\varepsilon$-optimal answer.

Table 5: Average number of pulls per arm and empirical stopping time ($\pm$ $\sigma$) on the hard instance ($\mathcal{K}=\mathcal{Z}$). The modified BAI algorithms use (5) with $z_{t}\in z_{F}(\mu_{t-1},N_{t-1})$. | $a_{1}$ | $a_{2}$ | $a_{3}$ | $a_{4}$ | Total
---|---|---|---|---|---
L$\varepsilon$BAI | $115$ | $247$ | $19$ | $3$ |  $384$ $(\pm 17)$
LinGame | $120$ | $239$ | $52$ | $12$ |  $423$ $(\pm 16)$
DKM | $174$ | $223$ | $173$ | $175$ |  $745$ $(\pm 29)$
LinGapE | $63$ | $349$ | $1$ | $1$ |  $414$ $(\pm 16)$
G-Static | $204$ | $227$ | $7$ | $19$ |  $458$ $(\pm 18)$
$\mathcal{X}\mathcal{Y}$-Static | $223$ | $224$ | $1$ | $1$ |  $449$ $(\pm 17)$
$\mathcal{X}\mathcal{Y}$-Adaptive | $82$ | $315$ | $1$ | $1$ |  $399$ $(\pm 18)$
Fixed | $96$ | $271$ | $1$ | $1$ |  $370$ $(\pm 16)$
Uniform | $214$ | $214$ | $214$ | $213$ |  $856$ $(\pm 33)$

##### Empirical Allocation

Table 5 details the empirical allocations of pulls. Uniform and DKM sample all
arms similarly. Therefore, they stop with almost twice as many samples as the
other algorithms whose empirical allocations are close to the oracle
allocation used in the fixed algorithm. As expected,
$\mathcal{X}\mathcal{Y}$-Adaptive outperforms $\mathcal{X}\mathcal{Y}$-Static
and G-Static. We see that L$\varepsilon$BAI slightly outperforms LinGapE and
$\mathcal{X}\mathcal{Y}$-Adaptive, performs better than LinGame and
$\mathcal{X}\mathcal{Y}$-Static and is on par with the “oracle” fixed
algorithm.

Figure 6: Empirical stopping time on the hard instance
($\mathcal{K}=\mathcal{Z}$) for (a) the lazy and sticky update, and different
implementations of (b) the lazy scheme and (c) the sticky scheme. “-S” denotes
the sticky scheme and “-L” the lazy one. The notations for implementations
are: “-C” for the constant one with $T_{0}=10$, “-G” for the geometric one
with $(T_{0},\gamma)=(10,0.2)$, “-D” for geometrically decreasing one with
$(T_{0},\gamma)=(10,0.2)$ and “-B” for the Bernoulli one with parameter
$p=0.1$.

##### Computational Relaxations

In Appendix E.2.1, we introduced the sticky and the lazy schemes. Instead of
updating the candidate answer and evaluating the stopping criterion at each
time $t$, the lazy scheme only does it on all time
$t\in\mathcal{T}\subseteq\mathbb{N}$. The sticky scheme evaluates the stopping
criterion at each time $t\geq n_{0}+1$, but update the candidate answer when
$t\in\mathcal{T}\subseteq\mathbb{N}$. With a good choice of $\mathcal{T}$,
using the sticky/lazy schemes with L$\varepsilon$BAI yield an asymptotically
optimal algorithm (Appendix E.2.1). To ensure that the strategy is
$(\varepsilon,\delta)$-PAC, it is sufficient to consider
$|\mathcal{T}|=+\infty$ (Lemma 3.1), property satisfied by all the
implementations below.

In Figure 6, we test several implementations of lazy/sticky schemes to assess
their impact on the empirical stopping time. They differ by how the infinite
grid of time $\mathcal{T}$ is defined. The constant implementation uses an
arithmetic grid of time with parameter $T_{0}>n_{0}$, i.e.
$\mathcal{T}=\left\\{n_{0}+1\right\\}\cup\left\\{iT_{0}\right\\}_{i\in\mathbb{N}^{\star}}$.
The geometric implementation uses a geometric grid of time with parameter
$T_{0}>n_{0}$ and $\gamma>0$, i.e.
$\mathcal{T}\buildrel\text{def}\over{=}\left\\{n_{0}+1\right\\}\cup\left\\{T_{i}\right\\}_{i\in\mathbb{N}}$
where $T_{i}=\lceil(1+\gamma)T_{i-1}\rceil$ for $i\in\mathbb{N}^{\star}$. The
geometrically decreasing implementation uses a grid of time with parameter
$T_{0}>n_{0}$ and $\gamma>0$, i.e.
$\mathcal{T}\buildrel\text{def}\over{=}\left\\{n_{0}+1\right\\}\cup\left\\{T_{i}\right\\}_{i\in\mathbb{N}}$
where $T_{i}=\lceil(1+\frac{\gamma}{\sqrt{i}})T_{i-1}\rceil$ for
$i\in\mathbb{N}^{\star}$. The Bernoulli implementation with parameter $p$ is
slightly different as it adds internal randomness, hence it is not a
deterministic strategy anymore. The idea is simple: draw
$X\sim\mathcal{B}(p)$, if $X=1$ we update the candidate answer, else we stick
to it. The geometrically decreasing implementation is the only implementation
ensuring that L$\varepsilon$BAI is an asymptotically optimal algorithm
(Appendix E.2.1).

In Figure 6(a), we see that the sticky relaxation allows to perform on par
with the algorithm updating the recommendation rule at each time $t$. However,
when considering the lazy relaxation, we pay the price of not evaluating the
stopping rule at each time $t$ by incurring a slightly higher empirical
stopping time. Therefore, depending on the constraints of the practitioner,
the sticky/lazy schemes allow to reduce the computational cost per time step
while keeping similar sample complexity.

In Figure 6(b), we observe that the empirical stopping time might be higher
depending on the implementation of the lazy scheme. Overall, algorithms using
a lazy scheme suffer from slightly worse sample complexity. This is the price
to pay to drastically reduce the computational cost.

In Figure 6(c), we see that the exact implementation of the sticky scheme has
few consequences as regards the empirical stopping time since they all perform
on par with the algorithm updating the recommendation rule at each time $t$.
Therefore, the sticky scheme is the computational relaxation to adopt when one
wishes to reduce the computational cost in a significant manner without
damaging the empirical performance.

Figure 7: Empirical stopping time on the hard instance
($\mathcal{K}=\mathcal{Z}$). “-D” denotes when the D-Tracking is used instead
of C-Tracking and “-NF” denotes the removal of forced exploration.

##### Tracking And Forced Exploration

The tracking procedure that we use throughout the paper is referred as
C-Tracking in the literature, since it tracks the cumulative sum of pulling
proportions over arms played by the agent, i.e.
$a_{t}\in\operatorname*{arg\,min}_{a\in\mathcal{K}}N_{t-1}^{a}-W_{t}^{a}$
where $W_{t}=\sum_{s=n_{0}+1}^{t}w_{s}$. Another commonly considered tracking
procedure is D-Tracking (Garivier & Kaufmann, 2016), in which the pulling
proportion over arms played by the agent at time $t$ is directly tracked, i.e.
$a_{t}\in\operatorname*{arg\,min}_{a\in\mathcal{K}}N_{t-1}^{a}-(t-n_{0})w_{t}^{a}$.
In Degenne & Koolen (2019), it is shown that D-Tracking might fail when
several correct answer exist. This explains why we only considered C-Tracking
in this paper. In Figure 7, we observe that considering D-Tracking instead of
C-Tracking leads to similar empirical stopping time.

As discussed in Appendix E.3.1, we need a logarithmic forced exploration to
conclude the proof, which was not needed by previous game-based approaches
Degenne et al. (2020a). In Figure 7, we see that removing the forced
exploration has almost no impact on the empirical stopping time.

####  F.2.2 Additive Optimality

When comparing the following plots and their equivalent in the main content of
the paper, we observe that the characteristic time and the empirical stopping
time in the additive $\varepsilon$-optimality is always smaller than for the
multiplicative one (all other parameters being identical). If there isn’t a
natural choice of $\varepsilon$-optimality, this fact might influence the
choice of the practitioner. Overall the messages conveyed by the following
plots are the same as the ones highlighted in the multiplicative
$\varepsilon$-optimality case, we report them for the sake of completeness.

Figure 8: Influence of $\varepsilon$ on (a) the proportion of draws where
$z_{F}(\mu)\notin z^{\star}(\mu)$, (b) the median (and first/third quartile)
of
$\frac{T_{\varepsilon}^{\operatorname*{add}}(\mu)}{T_{g,\varepsilon}^{\operatorname*{add}}(\mu)}$,
when $z_{F}(\mu)\notin z^{\star}(\mu)$.

##### Furthest Answer

The results observed in Figure 8 are similar to the ones in Figure 1, while
the discrepancy is less noteworthy. The proportion of draws where
$z_{F}(\mu)\notin z^{\star}(\mu)$ is not negligible, reaching on average
$10\%$. The impact on the characteristic time is visible with a ratio on
average at $0.95$, but it is very slim when considering $\varepsilon\leq
0.01$. Up to $\varepsilon\approx 0.25$ the proportion of draws where
$z_{F}(\mu)\notin z^{\star}(\mu)$ has a logarithmic increase with
$\varepsilon$. Therefore, when they are different, the furthest answer still
outperforms a greedy answer achieving
$T_{g,\varepsilon}^{\operatorname*{add}}(\mu)$. We note that this difference
is smaller in the additive $\varepsilon$-optimality than for the
multiplicative $\varepsilon$-optimality.

Table 6: Empirical stopping time ($\pm$ $\sigma$) with their original stopping rule or with ours (5) on the hard instance ($\mathcal{K}=\mathcal{Z}$). The modified BAI algorithms use (5) with $z_{t}\in z_{F}(\mu_{t-1},N_{t-1})$. | LinGame | LinGapE |  $\mathcal{X}\mathcal{Y}$-Adaptive
---|---|---|---
Original |  $151473$ $(\pm 18082)$ |  $121716$ $(\pm 14771)$ |  $263806$ $(\pm 36896)$
Modified |  $393$ $(\pm 49)$ |  $297$ $(\pm 39)$ |  $314$ $(\pm 38)$

##### Original Stopping Rule

In Table 6, the Original line is unchanged compared to Table 4 since BAI
algorithms consider $\varepsilon=0$, hence no multiplicative/additive notions
of $\varepsilon$-optimality. Similarly, their stopping time is $545$ times
higher when using their original stopping rule which was designed for an
harder problem, i.e. identifying the unique best-answer which is also an
$\varepsilon$-optimal answer.

Table 7: Empirical stopping time ($\pm$ $\sigma$) for different combinations of sampling rule and recommendation rule on the hard instance with $\mathcal{K}=\\{e_{1},e_{2}\\}$. | $z^{\star}(\mu_{t-1})$ | $z_{F}(\mu_{t-1})$ | $z_{F}(\mu_{t-1},N_{t-1})$
---|---|---|---
L$\varepsilon$BAI |  $350$ $(\pm 14)$ |  $318$ $(\pm 12)$ |  $318$ $(\pm 13)$
$\varepsilon$-TaS |  $323$ $(\pm 12)$ |  $298$ $(\pm 13)$ |  $298$ $(\pm 13)$
Fixed |  $324$ $(\pm 10)$ |  $300$ $(\pm 11)$ |  $300$ $(\pm 11)$
Uniform |  $477$ $(\pm 15)$ |  $434$ $(\pm 16)$ |  $434$ $(\pm 16)$

##### Choosing Answers

Table 7 conveys the same messages as Table 1. It shows that using greedy is
consistently worse than an (instantaneous) furthest answer, the ratio of their
stopping time is $0.917$ on average (coherent with Figure 8(b)) and that
instantaneous furthest answer and furthest answer have the same empirical
performance. While L$\varepsilon$BAI consistently outperform uniform sampling
($73\%$), it performs slightly worse than $\varepsilon$-TaS and the “oracle”
fixed algorithm (tracking the optimal allocation $w_{F}(\mu)$).

Table 8: Average number of pulls per arm and empirical stopping time ($\pm$ $\sigma$) on the hard instance ($\mathcal{K}=\mathcal{Z}$). The modified BAI algorithms use (5) with $z_{t}\in z_{F}(\mu_{t-1},N_{t-1})$. | $a_{1}$ | $a_{2}$ | $a_{3}$ | $a_{4}$ | Total
---|---|---|---|---|---
L$\varepsilon$BAI | $77$ | $228$ | $13$ | $3$ |  $321$ $(\pm 13)$
LinGame | $112$ | $221$ | $49$ | $11$ |  $393$ $(\pm 15)$
DKM | $169$ | $217$ | $168$ | $169$ |  $723$ $(\pm 27)$
LinGapE | $47$ | $248$ | $1$ | $1$ |  $297$ $(\pm 13)$
G-Static | $196$ | $217$ | $7$ | $18$ |  $438$ $(\pm 18)$
$\mathcal{X}\mathcal{Y}$-Static | $215$ | $217$ | $1$ | $1$ |  $434$ $(\pm 17)$
$\mathcal{X}\mathcal{Y}$-Adaptive | $76$ | $236$ | $1$ | $1$ |  $314$ $(\pm 12)$
Fixed | $48$ | $251$ | $1$ | $1$ |  $300$ $(\pm 11)$
Uniform | $211$ | $211$ | $211$ | $210$ |  $844$ $(\pm 33)$
Figure 9: Empirical stopping time on the hard instance
($\mathcal{K}=\mathcal{Z}$), the star represents the mean. The modified BAI
algorithms use (5) with $z_{t}\in z_{F}(\mu_{t-1},N_{t-1})$.

##### Modified BAI Algorithms and Empirical Allocation

The detailed empirical allocations presented in Table 8 bare similarity with
the results shown in Table 5. Likewise, Figure 9 shows similar results as
Figure 3. Uniform and DKM sample all arms equally. Their stopping time is
twice as high as the other algorithms whose empirical allocations are close to
the oracle allocation (fixed algorithm). $\mathcal{X}\mathcal{Y}$-Adaptive
outperforms $\mathcal{X}\mathcal{Y}$-Static and G-Static. We see that
L$\varepsilon$BAI slightly outperforms LinGapE and
$\mathcal{X}\mathcal{Y}$-Adaptive, performs better than LinGame and
$\mathcal{X}\mathcal{Y}$-Static and is on par with the “oracle” fixed
algorithm.

Figure 10: Empirical stopping time on random instances
($\mathcal{K}=\mathcal{Z}$) for $d\in\\{6,8,10,12\\}$ (from top left to bottom
right). The modified BAI algorithms use (5) with $z_{t}\in
z_{F}(\mu_{t-1},N_{t-1})$.

##### Random Instances In Higher Dimensions

For random instances and increasing dimension, Figure 10 reveals the same
trends as Figure 4. L$\varepsilon$BAI shows competitive empirical performance
with modified BAI algorithms. Even though it is outperformed by LinGapE,
L$\varepsilon$BAI is almost twice as fast as $\mathcal{X}\mathcal{Y}$-Adaptive
and appears to be slightly more robust than LinGame to increasing dimension.