$\lambda>0$, we have $\mathbb{E}_{\bm{F}}[N_{i}]<+\infty$ for
$i\in\\{8,9,10\\}$. Since

$\mathbb{E}_{\bm{F}}[N_{7}]\leq\sum_{i\in\\{1,4,8,9,10\\}}\mathbb{E}_{\bm{F}}[N_{i}]<+\infty\>,$

this concludes the proof. ∎

####  D.1.3 TCI challenger

Conditioned on $\mathcal{F}_{n}$ and given a leader $B_{n+1}$, the
Transportation Cost Improved (TCI) challenger is defined as the arm with
smallest penalized transportation cost compared to the leader

$C_{n+1}^{\text{TCI}}\in\operatorname*{arg\,min}_{j\neq
B_{n+1}}\left\\{W_{n}(B_{n+1},j)+\log(N_{n,j})\right\\}\quad\text{,}\quad\widehat{C}_{n+1}^{\text{TCI}}\in\operatorname*{arg\,min}_{j\neq\widehat{B}_{n+1}}\left\\{W_{n}(\widehat{B}_{n+1},j)+\log(N_{n,j})\right\\}\>,$
(28)

and

$\mathbb{P}_{\mid
n}[C_{n+1}^{\text{TCI}}=j|B_{n+1}=i]=\frac{\mathds{1}\left(j\in\operatorname*{arg\,min}_{k\neq
i}\left\\{W_{n}(i,k)+\log(N_{n,k})\right\\}\right)}{|\operatorname*{arg\,min}_{k\neq
i}\left\\{W_{n}(i,k)+\log(N_{n,k})\right\\}|}$

The TCI challenger is inspired by IMED [20]. As we will see in Appendix I.2,
it is more stable than the TC challenger. In Appendix D.3, we explain
intuitively why. The analysis of the TCI challenger is very close to the one
of the TC challenger.

##### Property 3

With similar arguments as in Lemma 19, Lemma 21 shows that the Property 3 is
satisfied by $C_{n+1}^{\text{TCI}}$.

######  Lemma 21.

Let $B_{n+1}$ be a leader satisfying Property 2. Let
$(C_{n+1}^{\text{TCI}},\widehat{C}_{n+1}^{\text{TCI}})$ as in (28). Let
$U_{n}^{L}$ and $V_{n}^{L}$ as in (20) and
$\mathcal{J}_{n}^{\star}=\operatorname*{arg\,max}_{i\in\overline{V_{n}^{L}}}\mu_{i}$.
There exists $\tilde{L}_{6}$ with $\mathbb{E}_{\bm{F}}[\tilde{L}_{6}]<+\infty$
such that if $L\geq\tilde{L}_{6}$, for all $n$ such that
$U_{n}^{L}\neq\emptyset$, $\widehat{B}_{n+1}\notin V_{n}^{L}$ implies
$\widehat{C}_{n+1}^{\text{TCI}}\in
V_{n}^{L}\cup\left(\mathcal{J}_{n}^{\star}\setminus\left\\{\widehat{B}_{n+1}\right\\}\right)$.

###### Proof.

In the following, we consider $U_{n}^{L}\neq\emptyset$ (hence
$V_{n}^{L}\neq\emptyset$) and $\widehat{B}_{n+1}\in V_{n}^{L}$. Let $L_{0}$ be
defined as in Property 2. Then, for $L\geq L_{0}^{4/3}$, we have
$\widehat{B}_{n+1}\in\mathcal{J}_{n}^{\star}$. If
$\widehat{C}_{n+1}^{\text{TCI}}\in\mathcal{J}_{n}^{\star}\setminus\left\\{\widehat{B}_{n+1}\right\\}$,
we are done. Assume that
$\widehat{C}_{n+1}^{\text{TCI}}\notin\mathcal{J}_{n}^{\star}\setminus\left\\{\widehat{B}_{n+1}\right\\}$.

Let $(L_{4},D_{\bm{F}})$ and $(L_{5},D_{1})$ as in Lemmas 15 and 16. Then, for
all $L\geq\max\\{L_{0}^{4/3},L_{4}^{4/3},L_{5}^{2}\\}$,

$\displaystyle\widehat{B}_{n+1}\in\mathcal{J}_{n}^{\star}\>,$
$\displaystyle\forall(i,j)\in\mathcal{J}_{n}^{\star}\times\left(\overline{V_{n}^{L}}\setminus\mathcal{J}_{n}^{\star}\right),\quad$
$\displaystyle W_{n}(i,j)+\log(N_{n,j})\geq L^{3/4}D_{\bm{F}}+\frac{3}{4}\log
L\>,$ $\displaystyle\forall(i,j)\in\overline{U_{n}^{L}}\times U_{n}^{L},\quad$
$\displaystyle W_{n}(i,j)+\log(N_{n,j})\leq\sqrt{L}D_{1}+\frac{1}{2}\log L\>.$

There exists a deterministic $\tilde{L}_{7}$ such that for all
$L\geq\tilde{L}_{7}$,

$L^{3/4}D_{\bm{F}}+\frac{3}{4}>\sqrt{L}D_{1}+\frac{1}{2}\log L\>.$

Since
$\mathcal{J}_{n}^{\star}\subseteq\overline{V_{n}^{L}}\subseteq\overline{U_{n}^{L}}$,
for all
$L\geq\tilde{L}_{6}:=\max\\{L_{0}^{4/3},L_{4}^{4/3},L_{5}^{2},\tilde{L}_{7}\\}$
we have

$\forall(i,k,j)\in\mathcal{J}_{n}^{\star}\times
U_{n}^{L}\times\left(\overline{V_{n}^{L}}\setminus\mathcal{J}_{n}^{\star}\right),\quad
W_{n}(i,j)+\log(N_{n,j})>W_{n}(i,k)+\log(N_{n,k})\>.$

As $\widehat{B}_{n+1}\in\mathcal{J}_{n}^{\star}$ and
$\widehat{C}_{n+1}^{\text{TCI}}\notin\mathcal{J}_{n}^{\star}\setminus\left\\{\widehat{B}_{n+1}\right\\}$,
the definition
$\widehat{C}_{n+1}^{\text{TCI}}\in\operatorname*{arg\,max}_{j\neq\widehat{B}_{n+1}}\left\\{W_{n}(\widehat{B}_{n+1},j)+\log(N_{n,j})\right\\}$
yields that $\widehat{C}_{n+1}^{\text{TCI}}\in V_{n}^{L}$. Otherwise the above
strict inequality would wield a contradiction. Since

$\mathbb{E}_{\bm{F}}[\tilde{L}_{6}]\leq\tilde{L}_{7}+\mathbb{E}_{\bm{F}}[L_{0}^{4/3}]+\mathbb{E}_{\bm{F}}[L_{4}^{4/3}]+\mathbb{E}_{\bm{F}}[L_{5}^{2}]<+\infty\>,$

this concludes the proof. ∎

##### Property 6

With similar arguments as in Lemma 20, Lemma 22 shows that the Property 6 is
satisfied by $C_{n+1}^{\text{TCI}}$.

######  Lemma 22.

Assume Property 4 holds. Let $\varepsilon>0$. Let $B_{n+1}$ be a leader
satisfying Property 5 and $C_{n+1}^{\text{TCI}}$ as in (28). There exists
$\tilde{N}_{7}$ with $\mathbb{E}_{\bm{F}}[\tilde{N}_{7}]<+\infty$ such that
for all $n\geq\tilde{N}_{7}$ and all $i\neq i^{\star}(\bm{F})$,

$\frac{\Psi_{n,i}}{n}\geq
w_{i}^{\beta}+\varepsilon\quad\implies\quad\mathbb{P}_{\mid
n}[C_{n+1}^{\text{TCI}}=i\mid B_{n+1}=i^{\star}(\bm{F})]=0\>.$ (29)

###### Proof.

Let $\varepsilon>0$ and $i^{\star}=i^{\star}(\bm{F})$. Using the definition of
$C_{n+1}^{\text{TCI}}$ in (28), we have

$\displaystyle\mathbb{P}_{\mid n}[C_{n+1}^{\text{TCI}}=i\mid
B_{n+1}=i^{\star}]=0$ $\displaystyle\iff$
$\displaystyle\>i\notin\operatorname*{arg\,min}_{k\neq
i^{\star}}\left\\{W_{n}(i^{\star},k)+\log(N_{n,k})\right\\}$
$\displaystyle\iff$
$\displaystyle\frac{1}{n}\left(W_{n}(i^{\star},i)+\log(N_{n,i})-\min_{j\neq
i^{\star}}\left\\{W_{n}(i^{\star},j)+\log(N_{n,j})\right\\}\right)>0$
$\displaystyle\impliedby$
$\displaystyle\frac{1}{n}\left(W_{n}(i^{\star},i)-\min_{j\neq
i^{\star}}W_{n}(i^{\star},j)\right)>\frac{\log(nK)}{2n}\>,$

where we used that $N_{n,i}\geq\sqrt{\frac{n}{K}}$ and $N_{n,j}\leq n$.

Let $N_{7}$ as in Lemma 22. In the proof of Lemma 22, we showed that there
exists $C_{\bm{F}}>0$ such that for all $n\geq N_{7}$ and all $i\neq
i^{\star}$,

$\frac{\Psi_{n,i}}{n}\geq
w_{i}^{\beta}+\varepsilon\quad\implies\quad\frac{1}{n}\left(W_{n}(i^{\star},i)-\min_{j\neq
i^{\star}}W_{n}(i^{\star},j)\right)\geq C_{\bm{F}}\>.$

Since $\frac{\log(nK)}{2n}\to_{\infty}0$, there exists a deterministic $N_{8}$
such that for all $n\geq\tilde{N}_{8}$,

$\frac{\log(nK)}{2n}<C_{\bm{F}}\>.$

Therefore, for all $n\geq\tilde{N}_{7}:=\max\\{N_{8},N_{7}\\}$ and all $i\neq
i^{\star}$,

$\frac{\Psi_{n,i}}{n}\geq
w_{i}^{\beta}+\varepsilon\quad\implies\quad\mathbb{P}_{\mid
n}[C_{n+1}^{\text{TCI}}=i\mid B_{n+1}=i^{\star}]=0\>.$

Since
$\mathbb{E}_{\bm{F}}[\tilde{N}_{7}]=N_{8}+\mathbb{E}_{\bm{F}}[N_{7}]<+\infty$,
this concludes the proof. ∎

###  D.2 Randomized mechanisms

Conditioned on the history $\mathcal{F}_{n}$, randomized mechanisms for the
leader and the challenger depend on a sampler $\Pi_{n}$. In addition, ties
will be broken uniformly at random. In Appendix D.2.1, we introduce the
general properties that a good sampler should verify. Depending on whether we
are using the sampler for the leader or for the challenger different
properties are necessary. In Appendix D.2.2, we define the TS leader and shows
that it satisfies Properties 2 and 5. In Appendix D.2.3, we define the RS
challenger and proves that Properties 3 and 6 hold.

####  D.2.1 How to sample

As both TS leader and RS challenger rely on a sampler $\Pi_{n}$, it is crucial
for this sampler to be tailored to the considered set of distributions
$\mathcal{F}^{K}$. For bounded distributions, the sampler $\Pi_{n}$ under
scrutiny is the Dirichlet sampler introduced in Section 3, which produces for
each arm a random re-weighting of the current history of rewards, augmented
with $\\{0,B\\}$. Yet, aiming for a unified analysis of Top Two algorithms
relying on a sampler, we put forward some general properties that the sampler
should satisfy. Those properties are only expressed in terms of the Boundary
Crossing Probability (BCP) associated to each arm, i.e. the probabilities
$\mathbb{P}_{n}[\theta_{i}\geq u]$ and $\mathbb{P}_{n}[\theta_{i}\leq u]$
where $u$ is a fixed threshold. For all measurable sets $A_{\theta}$, we
denote by
$\mathbb{P}_{n}[A_{\theta}]:=\mathbb{P}_{\theta\sim\Pi_{n}}[A_{\theta}\mid\mathcal{F}_{n}]$.

##### From $\bm{a_{n+1,i}}$ to BCP

Let
$a_{n,i}:=\mathbb{P}_{n-1}[i\in\operatorname*{arg\,max}_{j\in[K]}\theta_{j}]$.
From the definition of the TS leader in (32) and the RS challenger in (33), it
becomes apparent that we should control the quantity $a_{n,i}$. We will need
both upper and lower bounds on $a_{n+1,i}$. To derive those, we can write

$\displaystyle\forall j\neq i,\quad a_{n+1,i}$
$\displaystyle\leq\mathbb{P}_{n}[\theta_{i}\geq\theta_{j}]\>,$ $\displaystyle
a_{n+1,i}$ $\displaystyle\leq 1-\max_{j\neq
i}\mathbb{P}_{n}[\theta_{j}\geq\theta_{i}]\>,$ $\displaystyle\forall
u\in(0,B),\quad a_{n+1,i}$
$\displaystyle\geq\mathbb{P}_{n}\left[\theta_{i}\geq u\right]\prod_{j\neq
i}\mathbb{P}_{n}\left[\theta_{j}\leq u\right]\>.$

The lower bound is already expressed using BCPs, however the upper bound
requires to control $\mathbb{P}_{n}[\theta_{i}\geq\theta_{j}]$. In Lemma 64
stated in Appendix G, we provide upper bounds on this probability featuring
only BCPs (for some well-chosen threshold).

As we will see, a sampler $\Pi_{n}$ is tailored to the considered set of
distributions when the upper and lower bounds on the BCP involve
$\mathcal{K}_{\inf}^{\pm}$. Those bounds will be referred to as tight, the
ones without $\mathcal{K}_{\inf}^{\pm}$ will be referred as coarse. To show
that the TS leader satisfies Properties 2 and 5, we need a tight upper bound
on the BCP. Proving Property 3 for the RS challenger requires a tight upper
bound and a coarse lower bound on the BCP. However, the proof of Property 6
for the RS challenger relies on a tight upper _and_ lower bound on the BCP.

In Appendix G, we prove the corresponding bounds on the BCP for the Dirichlet
sampler. These bounds use some ingredients from BPCs bounds obtained for
variants of Non-Parametric Thompson Sampling [36, 7] in the regret
minimization literature. Our new Lemma 64 is instrumental to bring those to
the best arm identification literature.

##### Coarse lower bound on $\bm{a_{n+1,i}}$

Recall that $F_{n,i}$ is the empirical cdf of arms $i$. To ensure that the
sampling stops, the sampler $\Pi_{n}$ should rely on modified cdfs instead of
simply using $\bm{F}_{n}$. Those probability measures are denoted by
$\tilde{F}_{n,i}$ and their means by $\tilde{\mu}_{n,i}$. For single-parameter
exponential family, this modification corresponds to the posterior update
based on the prior. For bounded distributions (and Bernoulli), this
modification amounts to adding $\\{0,B\\}$ to the support. This ensures that
$\tilde{\mu}_{n,i}\in(0,B)$, hence it is not a Dirac in $0$ or $B$.
Alternatively, we can view this step as mixing $F_{n,i}$ with the distribution
$G=\frac{1}{2}\left(\delta_{0}+\delta_{B}\right)$ which is in the interior of
the domain, i.e.

$\tilde{F}_{n,i}=\left(1-\frac{2}{n+2}\right)F_{n,i}+\frac{1}{n+2}\left(\delta_{0}+\delta_{B}\right)\>.$
(30)

The necessity of adding $B$ to the support was already known [8] to obtain a
lower bound on $\mathbb{P}_{n}[\theta_{i}\geq u]$. Since we also need to
control $\mathbb{P}_{n}[\theta_{i}\leq u]$, we should add $0$ in the support
(by symmetry).

In all generality, the considered modified cdfs should be close to the
empirical cdf, i.e.

$\forall
n\in\mathbb{N},\quad\max_{i\in[K]}\left\|\tilde{F}_{n,i}-F_{n,i}\right\|_{\infty}\leq
d_{0}(n)\;,$ (31)

where the function $d_{0}:\mathbb{N}^{*}\to\mathbb{N}^{*}$ satisfies
$d_{0}(n)=_{+\infty}o(n^{-\alpha})$ with $\alpha>0$. For bounded distributions
(and Bernoulli), $\bm{\tilde{F}}_{n}$ defined in (30) verifies Property (31)
for $d_{0}(n)=\frac{3}{n+2}$.

Property 9 states that the sampler $\Pi_{n}$ based on $\bm{\tilde{F}}_{n}$
yields an exponential lower bound on the BCP. It is coarse as it doesn’t
involve $\mathcal{K}_{\inf}^{\pm}$.

######  Property 9.

There exists functions $\kappa^{+},\kappa^{-}:(0,B)\to\mathbb{R}_{+}^{*}$ such
that for all $u\in(0,B)$, all $n\geq 1$ and all $i\in[K]$

$\displaystyle\mathbb{P}_{n}[\theta_{i}\geq u]\geq
e^{-c_{0}(N_{n,i})\kappa^{+}(u)}\qquad\text{and}\qquad\mathbb{P}_{n}[\theta_{i}\leq
u]\geq e^{-c_{0}(N_{n,i})\kappa^{-}(u)}\>.$

The function $c_{0}:\mathbb{N}^{*}\to\mathbb{N}^{*}$ is increasing with
$c_{0}(x)\sim_{+\infty}x$. Moreover, $\kappa^{-}(B)=\kappa^{+}(0)=0$ and
$\lim_{u\to B}\kappa^{+}(u)=\lim_{u\to 0}\kappa^{-}(u)=+\infty$.

Property 9 plays a role in the proof of sufficient exploration for the RS
challenger. For bounded distributions (and Bernoulli), Lemma 65 in Appendix G
shows that Property 9 holds with

$\displaystyle\kappa^{-}(u)=-\log\left(\frac{u}{B}\right)\quad\text{,}\quad\kappa^{+}(u)=-\log\left(1-\frac{u}{B}\right)\quad\text{,}\quad
c_{0}(n)=n+1\>.$

##### Tight upper bound on $\bm{a_{n+1,i}}$

Property 10 states that the sampler $\Pi_{n}$ based on $\bm{\tilde{F}}_{n}$
yields an exponential upper bound on the BCP. Importantly, this upper bound is
tailored to the considered family of distributions $\mathcal{F}$ as it
involves the $\mathcal{K}_{\inf}^{\pm}$ for the set of distributions
$\mathcal{F}$.

######  Property 10.

For all $u\in(0,B)$, all $n\geq 1$ and all $i\in[K]$,

$\displaystyle\mathbb{P}_{n}[\theta_{i}\geq u]\leq
e^{-c_{1}(N_{n,i})\mathcal{K}_{\inf}^{+}(\tilde{F}_{n,i},u)}\qquad\text{and}\qquad\mathbb{P}_{n}[\theta_{i}\leq
u]\leq e^{-c_{1}(N_{n,i})\mathcal{K}_{\inf}^{-}(\tilde{F}_{n,i},u)}\>,$

where $c_{1}:\mathbb{N}^{*}\to\mathbb{N}^{*}$ is an increasing function such
that $c_{1}(x)\sim_{+\infty}x$.

Property 10 plays an important role for the TS leader and the RS challenger,
both in the proof of sufficient exploration and convergence towards the
$\beta$-optimal allocation. For bounded distributions (and Bernoulli), Theorem
5 in Appendix G shows that Property 10 holds with $c_{1}(n)=n+2$.

Lemma 23 is a direct corollary of Property 10 by using Lemma 64. For bounded
distributions, it is exactly Corollary 2.

######  Lemma 23.

Let $\Pi_{n}$ satisfying Property 10. Then, for all $n\geq 1$ and all
$(i,j)\in[K]^{2}$

$\displaystyle\mathbb{P}_{n}[\theta_{j}\geq\theta_{i}]$ $\displaystyle\leq
f\left(\inf_{u\in[0,B]}\left\\{c_{1}(N_{n,i})\mathcal{K}_{\inf}^{-}(\tilde{F}_{n,i},u)+c_{1}(N_{n,j})\mathcal{K}_{\inf}^{+}(\tilde{F}_{n,j},u)\right\\}\right)\>,$

where $f:x\mapsto(1+x)e^{-x}$ is decreasing on $\mathbb{R}_{+}$ with values in
$(0,1]$.

###### Proof.

Using Property 10 and Lemma 64, we obtain for all $n\geq 1$ and all
$(i,j)\in[K]^{2}$

$\displaystyle\mathbb{P}_{n}[\theta_{j}\geq\theta_{i}]$ $\displaystyle\leq
f\left(c_{1}(N_{n,i})\mathcal{K}_{\inf}^{-}(\tilde{F}_{n,i},u_{i,j})+c_{1}(N_{n,j})\mathcal{K}_{\inf}^{+}(\tilde{F}_{n,j},u_{i,j})\right)$
$\displaystyle\leq
f\left(\inf_{u\in[0,B]}\left\\{c_{1}(N_{n,i})\mathcal{K}_{\inf}^{-}(\tilde{F}_{n,i},u)+c_{1}(N_{n,j})\mathcal{K}_{\inf}^{+}(\tilde{F}_{n,j},u)\right\\}\right)\>,$

where
$u_{i,j}=\operatorname*{arg\,max}_{c\in[0,B]}\mathbb{P}_{n}[\theta_{j}\geq
c]\mathbb{P}_{n}[\theta_{i}\leq c]$. When
$\tilde{\mu}_{n,i}\leq\tilde{\mu}_{n,j}$, this result is non informative as
$f(0)=1$. ∎

While the proof of Property 9 heavily relies on the transformed cdfs, Property
10 also holds for the empirical cdfs $\bm{F}_{n}$. There is no need to add
$\\{0,B\\}$ in the support for this property. We aim at presenting a unified
sampler $\Pi_{n}$, which could be used both for the TS leader and the RS
challenger. Therefore, we present all the results with the modified cdfs
$\bm{\tilde{F}}_{n}$ instead of differentiating between a sampler $\Pi_{n}$
for the TS leader and a sampler $\tilde{\Pi}_{n}$ for the RS challenger.

##### Tight lower bound on $\bm{a_{n+1,i}}$

Property 11 states that the sampler $\Pi_{n}$ based on $\bm{\tilde{F}}_{n}$
yields an exponential lower bound on
$\mathbb{P}_{n}[\theta_{i}\geq\theta_{i^{\star}}]$. Importantly, this lower
bound is tailored to the considered family of distributions $\mathcal{F}$ as
it involves the $\mathcal{K}_{\inf}^{\pm}$ for the set of distributions
$\mathcal{F}$.

######  Property 11.

Let $\varepsilon>0$ and $i^{\star}=i^{\star}(\bm{F})$. There exists $N_{8}$,
with $\mathbb{E}_{\bm{F}}[(N_{8})^{\alpha}]<+\infty$ for all $\alpha>0$, such
that for all $n$ with $\min_{i\in[K]}N_{n,i}\geq N_{8}$ and all $i\neq
i^{\star}$,

$\mathbb{P}_{n}\left[\theta_{i}\geq\theta_{i^{\star}}\right]\geq\frac{e^{-\varepsilon(N_{n,i^{\star}}+N_{n,i})}}{h_{\varepsilon}(N_{n,i^{\star}},N_{n,i})}\exp\left(-\inf_{x\in[0,B]}\left\\{N_{n,i^{\star}}\mathcal{K}_{\inf}^{-}(F_{i^{\star}},x)+N_{n,i}\mathcal{K}_{\inf}^{+}(F_{i},x)\right\\}\right)\>,$

where $h_{\varepsilon}:(\mathbb{N}^{\star})^{2}\to(0,+\infty)$ is an
increasing function of both arguments, such that
$h_{\varepsilon}(n,m)=_{+\infty}o\left(e^{(n+m)^{\alpha}}\right)$ where
$\alpha<1$.

For bounded distributions (and Bernoulli), Property 11 is a direct corollary
of Theorem 8 given in Appendix G. Let $\varepsilon>0$ and $\eta>0$ as in
Theorem 8. Using Lemma 14, there exists $N_{8}=Poly(W_{2})$ such that for all
$n$ such that $\min_{i\in[K]}N_{n,i}\geq N_{8}$, we have
$\max_{i\in[K]}\|F_{n,i}-F_{i}\|_{\infty}\leq\eta$. As
$\mathbb{E}_{\bm{F}}[e^{\lambda W_{2}}]<+\infty$ for all $\lambda>0$, we have
$\mathbb{E}_{\bm{F}}[(N_{8})^{\alpha}]<+\infty$ for all $\alpha>0$ since
$(N_{8})^{\alpha}=Poly(W_{2})$. Therefore, Property 11 holds for bounded
distributions with

$h_{\varepsilon}(n,m)=(nm)^{\frac{M_{\varepsilon}+1}{2}}C_{\varepsilon}\quad\text{and}\quad
C_{\varepsilon}=\frac{4(8\pi)^{M_{\varepsilon}-1}}{M_{\varepsilon}^{M_{\varepsilon}}}\>,$

where $h_{\varepsilon}$ satisfies the conditions from Property 11.

Using Lemma 64, Theorem 8 was shown thanks to tight lower bound on the BCP for
bounded distributions (Lemma 67). Given a family of distribution for which a
tight lower bound on the BCP exists, similar manipulations would yield a tight
lower bound on $\mathbb{P}_{n}[\theta_{i}\geq\theta_{j}]$, hence showing
Property 11. The proof of Theorem 8 heavily relies on the modified empirical
cdf featured in the tight BCP lower bound. Indeed, for bounded distributions
Lemma 67 follows from a discretization of the empirical cdf, which allows to
use results on multinomial distributions. Since the technicalities depend on
the considered distribution, we don’t provide a general proof of Property 11
given a tight lower bound on the BCP.

##### Rates for $\bm{a_{n+1,i}}$

Analyzing randomized mechanisms heavily relies on properties of $a_{n+1,i}$.
Lemma 24 shows that $a_{n+1,i}$ decreases exponentially with a linear rate for
the arms not having highest means.

######  Lemma 24.

Let $\Pi_{n}$ satisfying Property 10, and $c_{1}$ therein. Let $S_{n}^{L}$ and
$\mathcal{I}_{n}^{\star}$ as in (19). There exists $L_{7}$ with
$\mathbb{E}_{\bm{F}}[(L_{7})^{\alpha}]<+\infty$ for all $\alpha>0$ such that
if $L\geq L_{7}$, for all $n$ such that $S_{n}^{L}\neq\emptyset$,

$\forall i\in S_{n}^{L}\setminus\mathcal{I}_{n}^{\star},\quad a_{n+1,i}\leq
f(c_{1}(L)D_{\bm{F}})\>,$

where $f(x)=(1+x)e^{-x}$ and $D_{\bm{F}}>0$ is the problem dependent constant
from Lemma 15.

###### Proof.

Let $S_{n}^{L}$ and $\mathcal{I}_{n}^{\star}$ as in (19). Assume that
$S_{n}^{L}\neq\emptyset$. If $S_{n}^{L}\setminus\mathcal{I}_{n}^{\star}$ is
empty, then the statement is not informative. Assume
$S_{n}^{L}\setminus\mathcal{I}_{n}^{\star}$ is not empty. Let
$(i,j)\in\mathcal{I}_{n}^{\star}\times\left(S_{n}^{L}\setminus\mathcal{I}_{n}^{\star}\right)$.

Since $\Pi_{n}$ satisfies Property 10, using Lemma 23 yields

$\displaystyle a_{n+1,j}\leq\mathbb{P}_{n}[\theta_{j}\geq\theta_{i}]$
$\displaystyle\leq
f\left(\inf_{u\in[0,B]}\left\\{c_{1}(N_{n,i})\mathcal{K}_{\inf}^{-}(\tilde{F}_{n,i},u)+c_{1}(N_{n,j})\mathcal{K}_{\inf}^{+}(\tilde{F}_{n,j},u)\right\\}\right)$
$\displaystyle\leq
f\left(c_{1}(L)\inf_{u\in[0,B]}\left\\{\mathcal{K}_{\inf}^{-}(\tilde{F}_{n,i},u)+\mathcal{K}_{\inf}^{+}(\tilde{F}_{n,j},u)\right\\}\right)\>,$

where we used that $\\{i,j\\}\subset S_{n}^{L}$, $c_{1}$ increasing and $f$
decreasing.

Using Lemma 30, there exists $\alpha>0$ such that

$D_{\bm{F}}=\min_{(i,j):m(F_{i})>m(F_{j})}\inf_{\begin{subarray}{c}G_{i},G_{j}:\\\
\forall
k\in\\{i,j\\},\|G_{k}-F_{k}\|_{\infty}\leq\alpha\end{subarray}}\inf_{u\in[0,B]}\left\\{\mathcal{K}_{\inf}^{-}(G_{i},u)+\mathcal{K}_{\inf}^{+}(G_{j},u)\right\\}>0\>.$

Using Lemma 14 and (31), i.e.
$\max_{i\in[K]}\left\|\tilde{F}_{n,i}-F_{n,i}\right\|_{\infty}\leq d_{0}(n)$
where $d_{0}(n)=_{+\infty}o(n^{-\alpha})$, there exists $L_{7}=Poly(W_{2})$
such that for all $L\geq L_{7}$ and all $i\in S_{n}^{L}$,
$\left\|\tilde{F}_{n,i}-F_{i}\right\|_{\infty}\leq\alpha\>.$

Since $f$ is decreasing, further upper bounding yields directly that for all
$L\geq L_{7}$ and all $j\in S_{n}^{L}\setminus\mathcal{I}_{n}^{\star}$, we
have

$a_{n+1,j}\leq f\left(c_{1}(L)D_{\bm{F}}\right)\>.$

As $\mathbb{E}_{\bm{F}}[e^{\lambda W_{2}}]<+\infty$ for all $\lambda>0$, we
have $\mathbb{E}_{\bm{F}}[(L_{7})^{\alpha}]<+\infty$ for all $\alpha>0$ since
$(L_{7})^{\alpha}=Poly(W_{2})$. This concludes the proof. ∎

Lemma 25 gives a lower bound on $a_{n,i}$ for under-sampled arms.

######  Lemma 25.

Let $\Pi_{n}$ satisfying Properties 9 and 10. Let $S_{n}^{L}$ as in (19).
There exists $L_{8}$ with $\mathbb{E}_{\bm{F}}[(L_{8})^{\alpha}]<+\infty$ for
all $\alpha>0$ such that for all $L\geq L_{8}$ and all $n\in\mathbb{N}$,

$\forall i\in\overline{S_{n}^{L}},\quad
a_{n+1,i}\geq\frac{e^{-D_{0}c_{0}(L)}}{2^{K-1}}\>,$

where $c_{0}$ is defined in Property 9 and $D_{0}>0$ is a problem dependent
constant.

###### Proof.

Let $i\in\overline{S_{n}^{L}}$ and $u\in(0,B)$. As explained above, we have

$a_{n+1,i}\geq\mathbb{P}_{n}\left[\theta_{i}\geq u\right]\prod_{j\in
S_{n}^{L}}\mathbb{P}_{n}\left[\theta_{j}\leq
u\right]\prod_{j\in\overline{S_{n}^{L}}\setminus\\{i\\}}\mathbb{P}_{n}\left[\theta_{j}\leq
u\right]\>.$

For all $j\in S_{n}^{L}$, Property 10 yields

$\displaystyle\mathbb{P}_{n}\left[\theta_{j}\leq
u\right]=1-\mathbb{P}_{n}\left[\theta_{j}\geq u\right]\geq
1-e^{-c_{1}(N_{n,j})\mathcal{K}_{\inf}^{+}(\tilde{F}_{n,j},u)}\geq
1-e^{-c_{1}(L)\mathcal{K}_{\inf}^{+}(\tilde{F}_{n,j},u)}\>,$

where we used that $N_{n,j}\geq L$ for all $j\in S_{n}^{L}$ and $c_{1}$
increasing.

By Theorem 4, the function $F\mapsto\mathcal{K}_{\inf}^{+}(F,u)$ is continuous
on $\mathcal{F}$. Using Lemma 14 and (31), i.e.
$\max_{i\in[K]}\left\|\tilde{F}_{n,i}-F_{n,i}\right\|_{\infty}\leq d_{0}(n)$
where $d_{0}(n)=_{+\infty}o(n^{-\alpha})$, there exists $L_{9}=Poly(W_{2})$
such that for all $L\geq L_{9}$ and all $j\in S_{n}^{L}$,

$\mathcal{K}_{\inf}^{+}(\tilde{F}_{n,j},u)\geq\frac{1}{2}\mathcal{K}_{\inf}^{+}(F_{j},u)\geq\frac{1}{2}\min_{j\in[K]}\mathcal{K}_{\inf}^{+}(F_{j},u)\>.$

Since $\mu_{j}\in(0,B)$ for all $j\in[K]$, there exists $u\in(0,B)$ such that
$\min_{j\in[K]}\mathcal{K}_{\inf}^{+}(F_{j},u)>0$. Choosing such a $u$, there
exists a deterministic $L_{10}$ such that for all $L\geq
L_{8}:=\max\\{L_{9},L_{10}\\}$

$\forall j\in S_{n}^{L},\quad\mathbb{P}_{n}\left[\theta_{j}\leq
u\right]\geq\frac{1}{2}\>.$

For the under-sampled arms $j\in\overline{S_{n}^{L}}$, Property 9 yields that

$\displaystyle\forall j\in\overline{S_{n}^{L}}\setminus\\{i\\},\qquad$
$\displaystyle\mathbb{P}_{n}\left[\theta_{j}\leq u\right]\geq
e^{-c_{0}(N_{n,j})\kappa^{-}(u)}\geq e^{-c_{0}(L)\kappa^{-}(u)}\>,$
$\displaystyle\mathbb{P}_{n}\left[\theta_{i}\geq u\right]\geq
e^{-c_{0}(N_{n,i})\kappa^{+}(u)}\geq e^{-c_{0}(L)\kappa^{+}(u)}\>,$

where we used that $N_{n,i}<L$ for $j\in\overline{S_{n}^{L}}$, $c_{0}$
increasing and $\kappa^{-}$, $\kappa^{+}$ strictly positive.

Combining the above and further lower bounding, we have shown that for $L\geq
L_{8}$,

$\displaystyle\forall i\in\overline{S_{n}^{L}},\quad a_{n+1,i}$
$\displaystyle\geq\frac{e^{-D_{0}c_{0}(L)}}{2^{K-1}}\>,$

where $D_{0}=\kappa^{+}(u)+(K-1)\kappa^{-}(u)$. As
$\mathbb{E}_{\bm{F}}[e^{\lambda W_{2}}]<+\infty$ for all $\lambda>0$, we have
$\mathbb{E}_{\bm{F}}[(L_{9})^{\alpha}]<+\infty$ for all $\alpha>0$. Since
$\mathbb{E}_{\bm{F}}[(L_{8})^{\alpha}]\leq(L_{10})^{\alpha}+\mathbb{E}_{\bm{F}}[(L_{9})^{\alpha}]<+\infty$,
this concludes the proof. ∎

####  D.2.2 TS leader

Conditioned on $\mathcal{F}_{n}$, the internal randomness of the Thompson
Sampling (TS) leader is parameterized by a sampler $\Pi_{n}$, where
$a_{n+1,i}=\mathbb{P}_{n}[i\in\operatorname*{arg\,max}_{j\in[K]}\theta_{j}]$.
Given an observation $\theta\sim\Pi_{n}$, the TS leader is defined as an arm
with highest mean for $\theta$,

$B_{n+1}^{\text{TS}}\in\operatorname*{arg\,max}_{i\in[K]}\theta_{i}\quad\text{,}\quad\mathbb{P}_{\mid
n}[B_{n+1}^{\text{TS}}=i]=a_{n+1,i}\quad\text{and}\quad\widehat{B}_{n+1}^{\text{TS}}\in\operatorname*{arg\,max}_{i\in[K]}a_{n+1,i}\>,$
(32)

where $\widehat{B}_{n+1}^{\text{TS}}$ is defined as an arm with highest
$a_{n,i}$.

##### Property 2

Lemma 26 shows that Property 2 is satisfied by $B_{n+1}^{\text{TS}}$.

######  Lemma 26.

Let $\Pi_{n}$ satisfying Property 10. Let $S_{n}^{L}$ and
$\mathcal{I}_{n}^{\star}$ as in (19). There exists $\tilde{L}_{7}$ with
$\mathbb{E}_{\bm{F}}[(\tilde{L}_{7})^{\alpha}]<+\infty$ for all $\alpha>0$
such that if $L\geq\tilde{L}_{7}$, for all $n$ such that
$S_{n}^{L}\neq\emptyset$, $\widehat{B}_{n+1}^{\text{TS}}\in S_{n}^{L}$ implies
$\widehat{B}_{n+1}^{\text{TS}}\in\mathcal{I}_{n}^{\star}$.

###### Proof.

Let $S_{n}^{L}$ and $\mathcal{I}_{n}^{\star}$ as in (19). Assume that
$S_{n}^{L}\neq\emptyset$. If $S_{n}^{L}\setminus\mathcal{I}_{n}^{\star}$ is
empty, then the result is true. Assume
$S_{n}^{L}\setminus\mathcal{I}_{n}^{\star}$ is not empty. Let $j\in
S_{n}^{L}\setminus\mathcal{I}_{n}^{\star}$ and $L_{7}$ as in Lemma 24, hence

$a_{n+1,j}\leq f\left(c_{1}(L)D_{\bm{F}}\right)\>.$

As $c_{1}(x)\sim_{+\infty}x$ and $\lim_{+\infty}f(x)=0$, there exists a
deterministic $L_{8}$ such that for all $L\geq L_{8}$,

$f\left(c_{1}(L)D_{\bm{F}}\right)<\frac{1}{K}\>.$

Therefore, for all $L\geq\tilde{L}_{7}:=\max\\{L_{7},L_{8}\\}$ and all $j\in
S_{n}^{L}\setminus\mathcal{I}_{n}^{\star}$, we have $a_{n+1,j}<\frac{1}{K}$.

Assume that $\widehat{B}_{n+1}^{\text{TS}}\in S_{n}^{L}$. Suppose towards
contradiction that
$\widehat{B}_{n+1}^{\text{TS}}\notin\mathcal{I}_{n}^{\star}$. Then, the above
shows that $a_{n+1,\widehat{B}_{n+1}^{\text{TS}}}<\frac{1}{K}$. This is a
contradiction with
$\widehat{B}_{n+1}^{\text{TS}}\in\operatorname*{arg\,max}_{i\in[K]}a_{n+1,i}$,
hence $\widehat{B}_{n+1}^{\text{TS}}\in\mathcal{I}_{n}^{\star}$. Since
$\mathbb{E}_{\bm{F}}[(\tilde{L}_{7})^{\alpha}]\leq(L_{8})^{\alpha}+\mathbb{E}_{\bm{F}}[(L_{7})^{\alpha}]$,
this concludes the proof. ∎

##### Property 5

Lemma 27 shows that Property 5 is satisfied by $B_{n+1}^{\text{TS}}$. More
precisely, we show that after enough time, the probability for the leader to
not be the best arm is decreasing exponentially fast.

######  Lemma 27.

Assume Property 4 holds. Let $\Pi_{n}$ satisfying Property 10, and $c_{1}$
therein. There exists $N_{9}$ with $\mathbb{E}_{\bm{F}}[N_{9}]<+\infty$ such
that for all $n\geq N_{9}$,

$\mathbb{P}_{\mid n}[B_{n+1}^{\text{TS}}\neq
i^{\star}(\bm{F})]\leq(K-1)f\left(c_{1}\left(\sqrt{\frac{n}{K}}\right)D_{\bm{F}}\right)\>,$

where $f(x)=(1+x)e^{-x}$ and $D_{\bm{F}}>0$ is the problem dependent constant
from Lemma 15.

###### Proof.

Let $i^{\star}=i^{\star}(\bm{F})$. Let $N_{1}$ as in Property 4, then
$N_{n,i}\geq\sqrt{\frac{n}{K}}$ for all $n\geq N_{1}$. Let $L_{7}$ as in Lemma
24. For all $n\geq N_{9}=\max\\{N_{1},K(L_{7})^{2}\\}$, Lemma 26 and Property
4 yields that

$\forall i\neq i^{\star},\quad a_{n+1,i}\leq
f\left(c_{1}\left(\sqrt{\frac{n}{K}}\right)D_{\bm{F}}\right)\>.$

Using the definition of $B_{n+1}^{\text{TS}}$ in (32), we obtain

$\displaystyle\mathbb{P}_{\mid n}[B_{n+1}^{\text{TS}}\neq
i^{\star}]=\sum_{i\neq i^{\star}}\mathbb{P}_{\mid
n}[B_{n+1}^{\text{TS}}=i]\leq(K-1)\max_{i\neq
i^{\star}}a_{n+1,i}\leq(K-1)f\left(c_{1}\left(\sqrt{\frac{n}{K}}\right)D_{\bm{F}}\right)\>.$

Since
$\mathbb{E}_{\bm{F}}[N_{9}]\leq\mathbb{E}_{\bm{F}}[N_{1}]+K\mathbb{E}_{\bm{F}}[(L_{7})^{2}]<+\infty$,
this concludes the result. ∎

####  D.2.3 RS challenger

Conditioned on $\mathcal{F}_{n}$, the internal randomness of the Re-Sampling
(RS) challenger is parameterized by a sampler $\Pi_{n}$, where
$a_{n+1,i}:=\mathbb{P}_{n}[i\in\operatorname*{arg\,max}_{j\in[K]}\theta_{j}]$.
Given a leader $B_{n+1}$, the RS challenger is defined by repeatedly sampling
$\tilde{\theta}\sim\Pi_{n}$ until
$B_{n+1}\notin\operatorname*{arg\,max}_{i\in[K]}\tilde{\theta}_{i}$ and by
taking an arm with highest mean for this $\tilde{\theta}$

$C_{n+1}^{\text{RS}}\in\operatorname*{arg\,max}_{i\in[K]}\tilde{\theta}_{i}\not\owns
B_{n+1}\quad\text{and}\quad\widehat{C}_{n+1}^{\text{RS}}\in\operatorname*{arg\,max}_{j\neq\widehat{B}_{n+1}}a_{n+1,j}\>,$
(33)

where

$\displaystyle\mathbb{P}_{\mid
n}[C_{n+1}^{\text{RS}}=j|B_{n+1}=i]=\sum_{k=0}^{+\infty}a_{n+1,i}^{k}a_{n+1,j}=\frac{a_{n+1,j}}{1-a_{n+1,i}}\>.$

##### Property 3

We prove Property 3 for $C_{n+1}^{\text{RS}}$ in Lemma 28 by comparing the
rates with which $a_{n+1,i}$ decreases. The effective challenger
$\widehat{C}_{n+1}^{\text{RS}}$ is taken as an arm different from
$\widehat{B}_{n+1}$ which maximizes $a_{n+1,i}$. Therefore, it is sufficient
to show that the sampled enough arms have lower $a_{n+1,i}$ than the mildly
under-sampled ones. This will imply that $\widehat{C}_{n+1}^{\text{RS}}$ has
to be mildly under-sampled or be an arm with highest true mean among the
sampled enough arms.

######  Lemma 28.

Let $\Pi_{n}$ satisfying Properties 9 and 10. Let $B_{n+1}$ be a leader
satisfying Property 2. Given $(B_{n+1},\widehat{B}_{n+1})$, let
$(C_{n+1}^{\text{RS}},\widehat{C}_{n+1}^{\text{RS}})$ as in (33). Let
$U_{n}^{L}$ and $V_{n}^{L}$ as in (20) and
$\mathcal{J}_{n}^{\star}=\operatorname*{arg\,max}_{i\in\overline{V_{n}^{L}}}\mu_{i}$.
There exists $L_{9}$ with $\mathbb{E}_{\bm{F}}[L_{9}]<+\infty$ such that if
$L\geq L_{9}$, for all $n$ such that $U_{n}^{L}\neq\emptyset$,
$\widehat{B}_{n+1}\notin V_{n}^{L}$ implies $\widehat{C}_{n+1}^{\text{RS}}\in
V_{n}^{L}\cup\left(\mathcal{J}_{n}^{\star}\setminus\left\\{\widehat{B}_{n+1}\right\\}\right)$.

###### Proof.

Let
$\mathcal{J}_{n}^{\star}=\operatorname*{arg\,max}_{i\in\overline{V_{n}^{L}}}\mu_{i}$.
In the following, we consider $U_{n}^{L}\neq\emptyset$ (hence
$V_{n}^{L}\neq\emptyset$) and $\widehat{B}_{n+1}\in V_{n}^{L}$. Let $B_{n+1}$
be a leader satisfying Property 2, and $L_{0}$ defined therein. Then, for
$L\geq L_{0}^{4/3}$, we have $\widehat{B}_{n+1}\in\mathcal{J}_{n}^{\star}$. If
$\widehat{C}_{n+1}^{\text{RS}}\in\mathcal{J}_{n}^{\star}\setminus\left\\{\widehat{B}_{n+1}\right\\}$,
we are done. Assume that
$\widehat{C}_{n+1}^{\text{RS}}\notin\mathcal{J}_{n}^{\star}\setminus\left\\{\widehat{B}_{n+1}\right\\}$.

Since $\Pi_{n}$ satisfies Properties 9 and 10, let $L_{7}$ and $L_{8}$ as in
Lemmas 24 and 25. Then, for all
$L\geq\max\\{L_{0}^{4/3},L_{7}^{4/3},L_{8}^{2}\\}$,

$\displaystyle\widehat{B}_{n+1}\in\mathcal{J}_{n}^{\star}\>,$
$\displaystyle\forall
i\in\overline{V_{n}^{L}}\setminus\mathcal{J}_{n}^{\star},\quad$ $\displaystyle
a_{n+1,i}\leq f(c_{1}(L^{3/4})D_{\bm{F}})\>,$ $\displaystyle\forall j\in
U_{n}^{L},\quad$ $\displaystyle
a_{n+1,j}\geq\frac{e^{-D_{0}c_{0}(\sqrt{L})}}{2^{K-1}}\>.$

Since $f(x)=(1+x)e^{-x}$, $c_{0}(x)\sim_{+\infty}x$ and
$c_{1}(x)\sim_{+\infty}x$, there exists a deterministic $L_{10}$ such that for
all $L\geq L_{10}$,

$f(c_{1}(L^{3/4})D_{\bm{F}})<\frac{e^{-D_{0}c_{0}(\sqrt{L})}}{2^{K-1}}\>.$

Therefore, for all $L\geq
L_{9}:=\max\\{L_{0}^{4/3},L_{7}^{4/3},L_{8}^{2},L_{10}\\}$,

$\forall(j,i)\in
U_{n}^{L}\times\left(\overline{V_{n}^{L}}\setminus\mathcal{J}_{n}^{\star}\right),\quad
a_{n+1,j}>a_{n+1,i}\>.$

As $\widehat{B}_{n+1}\in\mathcal{J}_{n}^{\star}$ and
$\widehat{C}_{n+1}^{\text{RS}}\notin\mathcal{J}_{n}^{\star}\setminus\left\\{\widehat{B}_{n+1}\right\\}$,
the definition
$\widehat{C}_{n+1}^{\text{RS}}\in\operatorname*{arg\,max}_{j\neq\widehat{B}_{n+1}}a_{n+1,j}$
yields that $\widehat{C}_{n+1}^{\text{RS}}\in V_{n}^{L}$. Otherwise the above
strict inequality would wield a contradiction. Since

$\mathbb{E}_{\bm{F}}[L_{9}]\leq
L_{10}+\mathbb{E}_{\bm{F}}[(L_{0})^{4/3}]+\mathbb{E}_{\bm{F}}[(L_{7})^{4/3}]+\mathbb{E}_{\bm{F}}[(L_{8})^{2}]<+\infty\>,$

this concludes the proof. ∎

##### Property 6

Lemma 29 shows that Property 6 is satisfied by $C_{n+1}^{\text{RS}}$.

######  Lemma 29.

Assume Property 4 holds. Let $\Pi_{n}$ satisfying Properties 10 and 11. Let
$B_{n+1}$ be a leader satisfying Property 5. Let
$\varepsilon\in(0,\varepsilon_{0}]$ where $\varepsilon_{0}$ is a problem
dependent constant. Given $B_{n+1}$, let $C_{n+1}^{\text{RS}}$ as in (33).
There exists $N_{10}$ with $\mathbb{E}_{\bm{F}}[N_{10}]<+\infty$ such that for
all $n\geq N_{10}$ and all $i\neq i^{\star}(\bm{F})$,

$\frac{\Psi_{n,i}}{n}\geq
w_{i}^{\beta}+\varepsilon\quad\implies\quad\mathbb{P}_{\mid
n}[C_{n+1}^{\text{RS}}=i\mid B_{n+1}=i^{\star}(\bm{F})]\leq h(n)\>,$ (34)

where $h:\mathbb{N}^{\star}\to(0,+\infty)$ such that
$h(n)=_{+\infty}o(n^{-\alpha})$ with $\alpha>0$.

###### Proof.

Let $\varepsilon>0$ and $i^{\star}=i^{\star}(\bm{F})$. Let $N_{1}$ as in
Property 4, then $N_{n,i}\geq\sqrt{\frac{n}{K}}$ for all $n\geq N_{1}$. Since
$i^{\star}$ is unique, we have $\Delta:=\min_{j\neq
i^{\star}}|\mu_{i^{\star}}-\mu_{j}|>0$. For bounded distributions, $F\mapsto
m(F)$ is continuous on $\mathcal{F}$ for the weak convergence. Lemma 14 yields
that there exists $N_{11}=Poly(W_{2})$ such that for all
$n\geq\max\\{N_{1},N_{11}\\}$ and all $i\in[K]$, we have
$|\mu_{n,i}-\mu_{i}|\leq\frac{\Delta}{4}$. Therefore, for all
$n\geq\max\\{N_{1},N_{8}\\}$,
$\operatorname*{arg\,max}_{i\in[K]}\mu_{n,i}=\operatorname*{arg\,max}_{i\in[K]}\mu_{i}=i^{\star}$.

Let $\xi>0$. Since Property 4 holds and $B_{n+1}$ satisfies Property 5, we can
use the results from Lemma 11. Let $N_{4}$ defined in Lemma 11, we have
$\left|\frac{N_{n,i^{\star}}}{n}-\beta\right|\leq\xi$ for all
$n\geq\max\\{N_{1},N_{4}\\}$.

Using the definition of $C_{n+1}^{\text{RS}}$ in (33), we have

$\displaystyle\mathbb{P}_{\mid n}[C_{n+1}^{\text{RS}}=i\mid
B_{n+1}=i^{\star}]=\frac{a_{n+1,i}}{1-a_{n+1,i^{\star}}}\leq\frac{\mathbb{P}_{n}[\theta_{i}\geq\theta_{i^{\star}}]}{\max_{j\neq
i^{\star}}\mathbb{P}_{n}[\theta_{j}\geq\theta_{i^{\star}}]}\>,$

where we used that $\\{\theta_{j}>\theta_{i^{\star}}\\}\subseteq\bigcup_{j\neq
i^{\star}}\\{\theta_{j}>\theta_{i^{\star}}\\}=\\{i^{\star}\notin\operatorname*{arg\,max}_{j\in[K]}\theta_{j}\\}$.

Let $i\neq i^{\star}$ such that $\frac{\Psi_{n,i}}{n}\geq
w_{i}^{\beta}+\varepsilon$. Using Lemma 5, there exists $N_{12}=Poly(W_{1})$,
such that for all $n\geq\max\\{N_{1},N_{12}\\}$, we have
$\frac{N_{n,i}}{n}\geq w_{i}^{\beta}+\frac{\varepsilon}{2}$. Therefore, for
all $n\geq\max_{i\in\\{1,4,11,12\\}}N_{i}$,

Let $f(x)=(1+x)e^{-x}$. Since $\Pi_{n}$ satisfies Property 10, Lemma 23 yields

$\displaystyle\mathbb{P}_{n}[\theta_{i}\geq\theta_{i^{\star}}]\leq
f\left(n\inf_{u\in[0,B]}\left\\{\frac{c_{1}(N_{n,i^{\star}})}{n}\mathcal{K}_{\inf}^{-}(\tilde{F}_{n,i^{\star}},u)+\frac{c_{1}(N_{n,i})}{n}\mathcal{K}_{\inf}^{+}(\tilde{F}_{n,i},u)\right\\}\right)\>.$

Let $\tilde{\varepsilon}>0$. Since
$f(x)=_{+\infty}\mathcal{O}\left(e^{-(1-\tilde{\varepsilon})x}\right)$ and
$c_{1}(x)\sim_{+\infty}x$, there exists deterministic
$C_{\tilde{\varepsilon}}$ and $N_{13}$ such that for all
$n\geq\max_{i\in\\{1,4,11,12,13\\}}N_{i}$,

$\displaystyle\mathbb{P}_{n}[\theta_{i}\geq\theta_{i^{\star}}]$
$\displaystyle\leq
C_{\tilde{\varepsilon}}\exp\left(-n(1-\tilde{\varepsilon})\inf_{u\in[0,B]}\left\\{\frac{N_{n,i^{\star}}}{n}\mathcal{K}_{\inf}^{-}(\tilde{F}_{n,i^{\star}},u)+\frac{N_{n,i}}{n}\mathcal{K}_{\inf}^{+}(\tilde{F}_{n,i},u)\right\\}\right)$
$\displaystyle\leq
C_{\tilde{\varepsilon}}\exp\left(-n(1-\tilde{\varepsilon})\inf_{u\in[0,B]}\left\\{\frac{N_{n,i^{\star}}}{n}\mathcal{K}_{\inf}^{-}(\tilde{F}_{n,i^{\star}},u)+\left(w_{i}^{\beta}+\frac{\varepsilon}{2}\right)\mathcal{K}_{\inf}^{+}(\tilde{F}_{n,i},u)\right\\}\right)\>.$

Let $(h_{\varepsilon},N_{8})$ as in Property 11. Since $h_{\varepsilon}$ is
increasing in both its arguments, we have
$h_{\varepsilon}(N_{n,i^{\star}},N_{n,i})\leq h_{\varepsilon}(n,n)$ and
$N_{n,i^{\star}}+N_{n,i}\leq n$. Therefore, for all
$n\geq\max\\{KN_{8}^{2},\max_{i\in\\{1,4,11,12\\}}N_{i}\\}$,

$\displaystyle\max_{j\neq
i^{\star}}\mathbb{P}_{n}[\theta_{j}\geq\theta_{i^{\star}}]$
$\displaystyle\geq\frac{e^{-\varepsilon
n}}{h_{\varepsilon}(n,n)}\exp\left(-n\min_{j\neq
i^{\star}}\inf_{x\in[0,B]}\left\\{\frac{N_{n,i^{\star}}}{n}\mathcal{K}_{\inf}^{-}(F_{i^{\star}},x)+\frac{N_{n,j}}{n}\mathcal{K}_{\inf}^{+}(F_{j},x)\right\\}\right)$
$\displaystyle\geq\frac{e^{-\varepsilon
n}}{h_{\varepsilon}(n,n)}\exp\left(-n\sup_{w\in\triangle_{K}:w_{i^{\star}}=\frac{N_{n,i^{\star}}}{n}}\min_{j\neq
i^{\star}}\inf_{x\in[0,B]}\left\\{w_{i^{\star}}\mathcal{K}_{\inf}^{-}(F_{i^{\star}},x)+w_{j}\mathcal{K}_{\inf}^{+}(F_{j},x)\right\\}\right)\>,$

where we lower bounded by considering the best possible allocation such that
$w_{i^{\star}}=\frac{N_{n,i^{\star}}}{n}$. For
$(\bm{G},\tilde{\beta})\in\mathcal{F}^{2}\times[0,1]$, let

$\displaystyle H_{\tilde{\varepsilon}}(\bm{G},\tilde{\beta})$
$\displaystyle=(1-\tilde{\varepsilon})\inf_{u\in[0,B]}\left\\{\tilde{\beta}\mathcal{K}_{\inf}^{-}(G_{1},u)+\left(w_{i}^{\beta}+\frac{\varepsilon}{2}\right)\mathcal{K}_{\inf}^{+}(G_{2},u)\right\\}$
$\displaystyle\quad-\sup_{w\in\triangle_{K}:w_{i^{\star}}=\tilde{\beta}}\min_{j\neq
i^{\star}}\inf_{u\in[0,B]}\left\\{w_{i^{\star}}\mathcal{K}_{\inf}^{-}(F_{i^{\star}},u)+w_{j}\mathcal{K}_{\inf}^{+}(F_{j},u)\right\\}\>.$

Let
$\bm{\tilde{G}}_{n,i^{\star},i}=(\tilde{F}_{n,i^{\star}},\tilde{F}_{n,i})$.
Combining the upper and the lower bound, we obtain for all
$n\geq\max\\{KN_{8}^{2},\max_{i\in\\{1,4,11,12,13\\}}N_{i}\\}$,

$\displaystyle\mathbb{P}_{\mid n}[C_{n+1}^{\text{RS}}=i\mid
B_{n+1}=i^{\star}]$ $\displaystyle\leq
C_{\tilde{\varepsilon}}h_{\varepsilon}(n,n)e^{\varepsilon
n}\exp\left(-nH_{\tilde{\varepsilon}}\left(\bm{\tilde{G}}_{n,i^{\star},i},\frac{N_{n,i^{\star}}}{n}\right)\right)$
$\displaystyle\leq C_{\tilde{\varepsilon}}h_{\varepsilon}(n,n)e^{\varepsilon
n}\exp\left(-n\inf_{\tilde{\beta}:|\beta-\tilde{\beta}|\leq\xi}H_{\tilde{\varepsilon}}\left(\bm{\tilde{G}}_{n,i^{\star},i},\tilde{\beta}\right)\right)\>.$

Using Lemma 31, the functions $(\bm{G},\tilde{\beta})\mapsto
H_{\tilde{\varepsilon}}(\bm{G},\tilde{\beta})$ and
$\bm{G}\mapsto\inf_{\tilde{\beta}:|\beta-\tilde{\beta}|\leq\xi}H_{\tilde{\varepsilon}}(\bm{G},\tilde{\beta})$
are continuous. Let $\bm{G}_{i^{\star},i}=(F_{i^{\star}},F_{i})$. Therefore,
there exists $N_{14}=Poly(W_{1})$, $\xi_{0}>0$ and $\tilde{\varepsilon}_{0}>0$
such that for all $n\geq
N_{10}:=\max\\{KN_{8}^{2},\max_{i\in\\{1,4,11,12,13,14\\}}N_{i}\\}$, all
$\xi\in(0,\xi_{0}]$ and $\tilde{\varepsilon}\in(0,\tilde{\varepsilon}_{0}]$,
we have

$\displaystyle\inf_{\tilde{\beta}:|\beta-\tilde{\beta}|\leq\xi}H_{\tilde{\varepsilon}}\left(\bm{\tilde{G}}_{n,i^{\star},i},\tilde{\beta}\right)\geq\frac{1}{2}\inf_{\tilde{\beta}:|\beta-\tilde{\beta}|\leq\xi}H_{\tilde{\varepsilon}}(\bm{G}_{i^{\star},i},\tilde{\beta})\geq\frac{1}{4}H_{\tilde{\varepsilon}}(\bm{G}_{i^{\star},i},\beta)\geq\frac{1}{8}H_{0}(\bm{G}_{i^{\star},i},\beta)\>.$

In the following, we take such $\xi_{0}>0$ and $\tilde{\varepsilon}_{0}>0$ and
$\varepsilon\in(0,\varepsilon_{0}]$ where
$\varepsilon_{0}=\frac{1}{16}H_{0}(\bm{G}_{i^{\star},i},\beta)$ is a problem
dependent constant.

At the $\beta$-equilibrium all transportation costs are equal (Lemma 61).
Therefore, by definition of $w^{\beta}$,

$\displaystyle\sup_{w\in\triangle_{K}:w_{i^{\star}}=\beta}\min_{j\neq
i^{\star}}\inf_{u\in[0,B]}\left\\{w_{i^{\star}}\mathcal{K}_{\inf}^{-}(F_{i^{\star}},u)+w_{j}\mathcal{K}_{\inf}^{+}(F_{j},u)\right\\}$
$\displaystyle\qquad=\min_{j\neq
i^{\star}}\inf_{u\in[0,B]}\left\\{\beta\mathcal{K}_{\inf}^{-}(F_{i^{\star}},u)+w^{\beta}_{j}\mathcal{K}_{\inf}^{+}(F_{j},u)\right\\}$
$\displaystyle\qquad=\inf_{u\in[0,B]}\left\\{\beta\mathcal{K}_{\inf}^{-}(F_{i^{\star}},u)+w^{\beta}_{i}\mathcal{K}_{\inf}^{+}(F_{i},u)\right\\}$
$\displaystyle\qquad<\inf_{u\in[0,B]}\left\\{\beta\mathcal{K}_{\inf}^{-}(F_{i^{\star}},u)+\left(w^{\beta}_{i}+\frac{\varepsilon}{2}\right)\mathcal{K}_{\inf}^{+}(F_{i},u)\right\\}$

where the strict inequality is obtained because the transportation costs are
strictly increasing in their allocation arguments (Lemma 56). Therefore, we
have $H_{0}(\bm{G}_{i^{\star},i},\beta)>0$.

As $\mathbb{E}_{\bm{F}}[e^{\lambda W_{1}}]<+\infty$ and
$\mathbb{E}_{\bm{F}}[e^{\lambda W_{2}}]<+\infty$ for all $\lambda>0$, we have
$\mathbb{E}_{\bm{F}}[N_{i}]<+\infty$ for $i\in\\{11,12,14\\}$ and

$\mathbb{E}_{\bm{F}}[N_{10}]\leq
N_{13}+K\mathbb{E}_{\bm{F}}[(N_{8})^{2}]+\sum_{i\in\\{1,4,11,12,14\\}}\mathbb{E}_{\bm{F}}[N_{i}]<+\infty\>.$

Summarizing, we have shown that for all $\varepsilon\in(0,\varepsilon_{0}]$,
there exists $N_{10}$ with $\mathbb{E}_{\bm{F}}[N_{10}]<+\infty$ such that for
all $n\geq N_{10}$,

$\displaystyle\frac{\Psi_{n,i}}{n}\geq
w_{i}^{\beta}+\varepsilon\quad\implies\quad\mathbb{P}_{\mid
n}[C_{n+1}^{\text{RS}}=i\mid B_{n+1}=i^{\star}(\bm{F})]\leq h(n)\>,$

where

$\displaystyle
h(n):=C_{\tilde{\varepsilon}_{0}}h_{\varepsilon}(n,n)\exp\left(-\frac{n}{16}H_{0}(\bm{G}_{i^{\star},i},\beta)\right)\>.$

Since $H_{0}(\bm{G}_{i^{\star},i},\beta)>0$, $n\mapsto h_{\varepsilon}(n,n)$
is decreasing and
$h_{\varepsilon}(n,n)=_{+\infty}o\left(e^{(2n)^{\alpha}}\right)$ where
$\alpha<1$, we obtain that $h(n)=_{+\infty}o(n^{-\alpha})$ with $\alpha>0$. It
is obvious by definition that $h(n)\in(0,+\infty)$ for all
$n\in\mathbb{N}^{\star}$. ∎

###  D.3 Relaxing the distinct means assumption

In Appendix C, we highlighted that Assumption 2 ($\Delta_{\min}(\bm{F})>0$)
was only used to show sufficient exploration (see Appendix C.3). We also
remarked that the proofs in Appendices C.3 and C.4 work similarly when the
amount of exploration $\sqrt{\frac{n}{K}}$ in Lemma 7 and Property 4 is
replaced by $\left(\frac{n}{K}\right)^{\alpha}$ for some arbitrary
$\alpha\in(0,1)$. We conjecture that, besides $\beta$-EB-TC, all the Top Two
algorithms studied in this paper are also asymptotically $\beta$-optimal when
$\Delta_{\min}(\bm{F})=0$, as detailed below. Let
$\Delta_{\min}:=\Delta_{\min}(\bm{F})$.

##### Lack of robustness of $\beta$-EB-TC for $\Delta_{\min}=0$

For the EB-TC sampling rule, a simple explanation hints that it can
dramatically fail empirically, which is confirmed experimentally in Appendix
I.2. Let $\bm{F}$ be a bandit instance in which there are two arms with equal
mean that are closest to $\mu_{i^{\star}}$. At small time, it can happen that
the best arm is under-estimated (e.g. when under-sampled) and the two second-
best arms have higher empirical mean. In that case, is is very hard for
$\beta$-EB-TC to recover as it will mostly sample the two second-best arms
instead of the best arm. The EB leader will alternate between one of the two
second-best arms, depending on the collected samples. Then, given the EB
leader, the TC challenger will output the arm with smallest transportation
cost. When both second-best arms have higher empirical mean and the best arm
is under-estimated, the transportation cost will be smaller between the two
second-best arms. Therefore, the TC challenger will propose the second of the
two second-best arms. As neither the leader nor the challenger propose to
sample the true best arm, it is very hard for $\beta$-EB-TC to recover from
unlucky first draws.

The condition $\Delta_{\min}>0$ asymptotically prevents the above situation.
When $\mu_{i}>\mu_{j}$, the transportation cost between $(i,j)$ grows linearly
with $N_{n,i}+N_{n,j}$. Therefore, the transportation cost between the over-
sampled arms will become larger than between the current leader and the best
arm, even if it is under-estimated. This ensures that the challenger will
propose to sample the best arm, hence allowing the algorithm to eventually
recover from unlucky first draws. Based on our analysis, the number of samples
required by $\beta$-EB-TC to recover from unlucky first draws is a function of
$(D_{\bm{F}})^{-1}$, where $D_{\bm{F}}$ is a problem dependent constant
defined in (35). Extrapolating from results on Gaussian, it is intuitive to
expect that small $\Delta_{\min}$ yields small $D_{\bm{F}}$. Therefore, for
small $\Delta_{\min}$, $\beta$-EB-TC can need a large number of samples before
recovering from unlucky first draws. This undesirable behavior in moderate
confidence regime is hidden in the asymptotic analysis. Therefore, we expect
$\beta$-EB-TC to also suffer from large outliers in the moderate regime, even
when $\Delta_{\min}>0$.

##### On asymptotic $\beta$-optimality for $\Delta_{\min}=0$

Experiments reported in Appendix I.2.2 reveal that on some instance with
$\Delta_{\min}=0$, the other Top Two instances still have a good performance.
We conjecture that using either regularization in the TCI challenger or
randomization in the TS leader or RS challenger is adding the right amount of
exploration to avoid the undesirable behavior of $\beta$-EB-TC described
above, and ensure asymptotic $\beta$-optimality. More precisely, we conjecture
that this amount of exploration is actually logarithmic, and that logarithmic
exploration is sufficient to prove $\beta$-optimality (which is currently not
supported by our analysis).

In particular, for the TS leader it is known from the literature on regret
minimization that Thompson Sampling is selecting sub-optimal arms a
logarithmic amount of time (at least in expectation) [1]. As for the TCI
challenger, we observe that it is designed to avoid the situation described
above in which $\beta$-EB-TC fails when there are two equal second best arms.
When choosing the challenger, we penalize the highly over-sampled arms by
adding $\log(N_{n,j})$. While the transportation cost can be very small for
two highly sampled arms having similar means, the penalization makes sure that
the under-sampled best arm will be selected as the challenger. We conjecture
that the TCI challenger ensures an implicit logarithmic exploration.

##### On forced exploration

Another natural idea to prove asymptotic $\beta$-optimality when
$\Delta_{\min}=0$ is to add some small amount of forced exploration to the
algorithm. A round $n$, if there exists an arm $i$ such that
$N_{n,i}<{n}^{\alpha}$ (for some small value of $\alpha$), we draw this arm.
This will make Property 4 hold for an exploration level $(n/K)^{\alpha}$.
However, forced exploration can be wasteful as it is agnostic to
$\mathcal{F}_{n}$ and all under-sampled arms should not be drawn equally. Our
experiments confirm that it is actually not needed for most Top Two
algorithms.

Concurrently to our work, [33] introduces and studies the TT-SPRT algorithm
for general SPEF. In our terminology, it corresponds to the $\beta$-EB-TC
algorithm with an added forced exploration in $\sqrt{n/K}$. As expected,
adding forced exploration allows to obtain asymptotic $\beta$-optimality even
for instances where $\Delta_{\min}=0$. By adding forced exploration, their
result also holds for SPEF which are not sub-exponential distributions. In our
work, the sub-exponential assumption is made to control the concentration
towards the mean parameter. Controlling the concentration rate is of the
upmost importance to prove sufficient exploration. Therefore, while this fact
is not a direct consequence of our unified analysis, it is not surprising.

###  D.4 Technicalities

We present some technical results used in the above proofs. Those
technicalities are direct corollaries of properties on
$\mathcal{K}_{\inf}^{\pm}$ obtained in the Appendix F.

######  Lemma 30.

There exists $\alpha>0$ such that

$D_{\bm{F}}=\min_{(i,j):m(F_{i})>m(F_{j})}\inf_{\begin{subarray}{c}G_{i},G_{j}:\\\
\forall
k\in\\{i,j\\},\|G_{k}-F_{k}\|_{\infty}\leq\alpha\end{subarray}}\inf_{u\in[0,B]}\left\\{\mathcal{K}_{\inf}^{-}(G_{i},u)+\mathcal{K}_{\inf}^{+}(G_{j},u)\right\\}>0\>.$
(35)

###### Proof.

Using Lemma 54 for $w_{1}=w_{2}=1$, we have that

$\bm{F}\mapsto\inf_{u\in[0,B]}\left\\{\mathcal{K}_{\inf}^{-}(F_{i},u)+\mathcal{K}_{\inf}^{+}(F_{j},u)\right\\}$

is continuous on $\mathcal{F}^{K}$. Since it has strictly positive values when
$m(F_{i})>m(F_{j})$ (Lemma 55), there exists $\alpha$ such that

$\inf_{\begin{subarray}{c}G_{i},G_{j}:\\\ \forall
k\in\\{i,j\\},\|G_{k}-F_{k}\|_{\infty}\leq\alpha\end{subarray}}\inf_{u\in[0,B]}\left\\{\mathcal{K}_{\inf}^{-}(G_{i},u)+\mathcal{K}_{\inf}^{+}(G_{j},u)\right\\}>0\>.$

Further lower bounding by a finite number of strictly positive constants
yields the result. ∎

For all $i\in[K]$, we define the distributions for which $i$ is among the best
arm

$\mathcal{F}^{K}_{i}:=\left\\{\bm{F}\in\mathcal{F}^{K}\mid i\in
i^{\star}(\bm{F})\right\\}\>.$

######  Lemma 31.

Let $i^{\star}\in[K]$, $\bm{F}\in\mathcal{F}^{K}_{i^{\star}}$, $i\neq
i^{\star}$ and $\varphi\in[0,1]$. Define for $\beta\in[0,1]$,

$\displaystyle G_{i}(\bm{F},\beta)$
$\displaystyle=\inf_{u\in[0,B]}\left\\{\beta\mathcal{K}_{\inf}^{-}(F_{i^{\star}},u)+\varphi\mathcal{K}_{\inf}^{+}(F_{i},u)\right\\}$
$\displaystyle\quad-\sup_{w\in\triangle_{K}:w_{i^{\star}}=\beta}\min_{j\neq
i^{\star}}\inf_{u\in[0,B]}\left\\{w_{i^{\star}}\mathcal{K}_{\inf}^{-}(F_{i^{\star}},u)+w_{j}\mathcal{K}_{\inf}^{+}(F_{j},u)\right\\}\>.$

Then, $(\bm{F},\beta)\mapsto G_{i}(\bm{F},\beta)$ is continuous on
$\mathcal{F}^{K}\times[0,1]$. Moreover, the function
$\bm{F}\mapsto\inf_{\tilde{\beta}:|\beta-\tilde{\beta}|\leq\xi}G_{i}(\bm{F},\tilde{\beta})$
is continuous on $\mathcal{F}^{K}$.

Let $\bm{\nu}\in\mathcal{F}^{K}_{1}$, $\bm{F}\in\mathcal{F}^{2}$ such that
$m(F_{1})>m(F_{2})$, $\alpha>0$ and $\varphi\in[0,1]$. Define for
$\beta\in[0,1]$,

$\displaystyle H(\bm{F},\beta)$
$\displaystyle=\alpha\inf_{u\in[0,B]}\left\\{\beta\mathcal{K}_{\inf}^{-}(F_{1},u)+\varphi\mathcal{K}_{\inf}^{+}(F_{2},u)\right\\}$
$\displaystyle\quad-\sup_{w\in\triangle_{K}:w_{1}=\beta}\min_{i\neq
1}\inf_{u\in[0,B]}\left[w_{1}\mathcal{K}_{\inf}^{-}(\nu_{1},u)+w_{i}\mathcal{K}_{\inf}^{+}(\nu_{i},u)\right]\>.$

Then, $(\bm{F},\beta)\mapsto H(\bm{F},\beta)$ is continuous on
$\mathcal{F}^{2}\times[0,1]$. Moreover, the function
$\bm{F}\mapsto\inf_{\tilde{\beta}:|\beta-\tilde{\beta}|\leq\xi}H(\bm{F},\tilde{\beta})$
is continuous on $\mathcal{F}^{2}$.

###### Proof.

Since $\bigcup_{i\in[K]}\mathcal{F}^{K}_{i}=\mathcal{F}^{K}$, it is enough to
show the property for all $i\in[K]$. Let $i^{\star}\in[K]$ and $i\neq
i^{\star}$. In the proof of Lemma 58, we have obtained that

$\displaystyle(\bm{F},w)\mapsto\inf_{u\in[0,B]}\left\\{w_{i^{\star}}\mathcal{K}_{\inf}^{-}(F_{i^{\star}},u)+w_{i}\mathcal{K}_{\inf}^{+}(F_{i},u)\right\\}$
and $\displaystyle(\bm{F},w)\mapsto\min_{i\neq
i^{\star}}\inf_{u\in[0,B]}\left\\{w_{i^{\star}}\mathcal{K}_{\inf}^{-}(F_{i^{\star}},u)+w_{i}\mathcal{K}_{\inf}^{+}(F_{i},u)\right\\}$

are continuous on $\mathcal{F}^{K}_{i^{\star}}\times\triangle_{K}$.

Let $\Phi_{i^{\star}}:(\bm{F},\beta)\mapsto\\{w\in\triangle_{K}\mid
w_{i^{\star}}=\beta\\}$, it is compact valued and non-empty for all
$\beta\in[0,1]$. It is also continuous (both lower and upper hemicontinuous).
Using the continuity proven above, Berge’s theorem yields that

$(\bm{F},\beta)\mapsto\sup_{w\in\triangle_{K}:w_{1}=\beta}\min_{i\neq
1}\inf_{u\in[0,B]}\left[w_{1}\mathcal{K}_{\inf}^{-}(\nu_{1},u)+w_{i}\mathcal{K}_{\inf}^{+}(\nu_{i},u)\right]\>,$

is continuous on $\mathcal{F}^{K}_{i^{\star}}\times[0,1]$. Combining with the
above continuity results, we obtain that $(\bm{F},\beta)\mapsto
G_{i}(\bm{F},\beta)$ is continuous on $\mathcal{F}^{K}_{i^{\star}}\times[0,1]$
for all $i^{\star}\in[K]$, hence on $\mathcal{F}^{K}\times[0,1]$.

Let
$\Phi:\bm{F}\mapsto\left\\{\tilde{\beta}:|\beta-\tilde{\beta}|\leq\xi\right\\}$,
it is a continuous (constant), compact valued and non-empty correspondence.
Using the continuity proven above, Berge’s theorem yields that
$\bm{F}\mapsto\inf_{\tilde{\beta}:|\beta-\tilde{\beta}|\leq\xi}G_{i}(\bm{F},\tilde{\beta})$
is continuous on $\mathcal{F}^{K}$.

Using exactly the same arguments, we obtain that $(\bm{F},\beta)\mapsto
H(\bm{F},\beta)$ is continuous on $\mathcal{F}^{2}\times[0,1]$ and
$\bm{F}\mapsto\inf_{\tilde{\beta}:|\beta-\tilde{\beta}|\leq\xi}H(\bm{F},\tilde{\beta})$
is continuous on $\mathcal{F}^{2}$. ∎

##  Appendix E Concentration

In Appendix E.1, we leverage results on martingales [5] to prove
$\delta$-correctness of the threshold (4) from Lemma 2. In Appendix E.2, we
derive technical results needed in our analysis of Top Two algorithms based on
concentration for sub-Gaussian random variables.

###  E.1 Calibration for bounded distributions

After proving Lemma 32, we give a threshold for bounded distributions (Lemma
2). The concentration is obtained as a direct corollary of recent work on
martingales [5]. We apply their technical result to the case of bounded
distributions.

##### Calibration by concentration

Lemma 32 states that $\delta$-correct thresholds can be obtained by
concentration results.

######  Lemma 32.

If with probability $1-\delta$, for all $n\in\mathbb{N}$ and all $i\neq
i^{\star}(\bm{F})$,

$N_{n,i}\mathcal{K}_{\inf}^{-}(F_{n,i},\mu_{i})+N_{n,i^{\star}(\bm{F})}\mathcal{K}_{\inf}^{+}(F_{n,i^{\star}(\bm{F})},\mu_{i^{\star}(\bm{F})}))\leq
c(n,\delta)\>,$ (36)

then the stopping rule (2) using $c(n,\delta)$ is $\delta$-correct on
$\mathcal{F}^{K}$.

###### Proof.

Let $i^{\star}=i^{\star}(\bm{F})$ and
$\hat{\imath}_{n}=i^{\star}(\bm{F}_{n})$. The empirical transportation costs
in (1) can be rewritten as

$W_{n}(\hat{\imath}_{n},j)=\inf_{x\leq
y}\left[N_{n,\hat{\imath}_{n}}\mathcal{K}_{\inf}^{-}(F_{n,\hat{\imath}_{n}},x)+N_{n,j}\mathcal{K}_{\inf}^{+}(F_{n,j},y)\right]\>.$

Using $j=i^{\star}$, $x=\mu_{i}$ and $y=\mu_{i^{\star}}$, we obtain

$\displaystyle\mathbb{P}\left(\tau_{\delta}<+\infty,\hat{\imath}_{\tau_{\delta}}\neq
i^{\star}\right)$ $\displaystyle\leq\mathbb{P}\left(\exists
n\in\mathbb{N},\>\exists i\neq i^{\star},\>i=\hat{\imath}_{n},\>\min_{j\neq
i}W_{n}(i,j)>c(n,\delta)\right)$ $\displaystyle\leq\mathbb{P}\left(\exists
n\in\mathbb{N},\>\exists i\neq
i^{\star},\>N_{n,i}\mathcal{K}_{\inf}^{-}(F_{n,i},\mu_{i})+N_{n,i^{\star}}\mathcal{K}_{\inf}^{+}(F_{n,i^{\star}},\mu_{i^{\star}})>c(n,\delta)\right)\>.$

∎

##### Concentration of $\mathcal{K}_{\inf}$

The key technical result, which was extracted from [5], is reproduced in Lemma
33.

######  Lemma 33 (Lemma E.1 in [5]).

Let a compact and convex set $\Lambda\subseteq\mathbb{R}^{d}$, and $q$ be the
uniform distribution on $\Lambda$. Let $g_{t}:\Lambda\mapsto\mathbb{R}$ be any
series of exp-concave functions. Then,

$\displaystyle\max_{\bm{\lambda}\in\Lambda}\sum_{k=1}^{n}g_{k}(\bm{\lambda})\leq\log\mathbb{E}_{\bm{\lambda}\sim
q}\left[e^{\sum_{k=1}^{n}g_{t}(\bm{\lambda})}\right]+d\log(n+1)+1$

We are now ready to prove Lemma 2.

###### Proof.

For all $(n,i)\in\mathbb{N}\times[K]$, we denote by
$(X_{k,i})_{k\in[N_{n,i}]}$ the samples collected on arm $i$. Let
$i^{\star}=i^{\star}(\bm{F})$ and $i\in[K]\setminus\\{i^{\star}\\}$. Using
Theorem 3, we obtain

$\displaystyle
N_{n,i^{\star}}\mathcal{K}_{\inf}^{+}(F_{n,i^{\star}},\mu_{i^{\star}}))$
$\displaystyle=\max_{\lambda\in\left[0,\frac{1}{B-\mu_{i^{\star}}}\right]}\sum_{k\in[N_{n,i^{\star}}]}\log(1-\lambda(X_{k,i^{\star}}-\mu_{i^{\star}}))\>,$
$\displaystyle N_{n,i}\mathcal{K}_{\inf}^{-}(F_{n,i},\mu_{i}))$
$\displaystyle=\max_{\lambda\in\left[0,\frac{1}{\mu_{i}}\right]}\sum_{k\in[N_{n,i}]}\log(1+\lambda(X_{k,i}-\mu_{i}))\>.$

Let $q_{i}^{+}$ and $q_{i}^{-}$ be the uniform distributions over
$\left[0,\frac{1}{B-\mu_{i}}\right]$ and $\left[0,\frac{1}{\mu_{i}}\right]$,
which are compact and convex sets of $\mathbb{R}$. Define

$\displaystyle L_{n,i}$ $\displaystyle=\mathbb{E}_{\lambda\sim
q_{i}^{-}}\left[\prod_{k\in[N_{n,i}]}(1+\lambda(X_{k,i}-\mu_{i}))\mid
X_{1,i},\cdots,X_{N_{n,i},i}\right]\>,$ $\displaystyle U_{n,i}$
$\displaystyle=\mathbb{E}_{\lambda\sim
q_{i}^{+}}\left[\prod_{k\in[N_{n,i}]}(1-\lambda(X_{i,k}-\mu_{i}))\mid
X_{1,i},\cdots,X_{N_{n,i},i}\right]\>,$ $\displaystyle Y^{-}_{n,i}$
$\displaystyle=N_{n,i}\mathcal{K}_{\inf}^{-}(F_{n,i},\mu_{i})-\log(N_{n,i}+1)-1\>,$
$\displaystyle Y^{+}_{n,i}$
$\displaystyle=N_{n,i}\mathcal{K}_{\inf}^{+}(F_{n,i},\mu_{i})-\log(N_{n,i}+1)-1\>.$

With $d=1$, using Lemma 33 with the exp-concave functions
$g_{k,i}^{+}(\lambda)=\log(1-\lambda(X_{k,i}-\mu_{i}))$ for $k\in[N_{n,i}]$,
and $g_{k,i}^{-}(\lambda)=\log(1+\lambda(X_{k,i}-\mu_{i}))$ for
$k\in[N_{n,i}]$, yields

$\displaystyle e^{Y^{-}_{n,i}}\leq L_{n,i}\qquad\text{and}\qquad
e^{Y^{+}_{n,i}}\leq U_{n,i}\qquad\text{a.s.}$

Furthermore, it is easy to verify that for each arm $i\in[K]$, $L_{n,i}$ and
$U_{n,i}$ are non-negative martingales with unit initial value $L_{0,i}=1$ and
$U_{0,i}=1$ almost surely. The martingale property is shown directly by the
tower rule (conditioned on the arm sampled at time $n$) and
$\mathbb{E}\left[1\pm\lambda(X_{N_{n,i},i}-\mu_{i})\right]=1$. Furthermore,
they satisfy $\mathbb{E}[U_{n,i}]\leq 1$ and $\mathbb{E}[L_{n,i}]\leq 1$.
Thus, $U_{n,i^{\star}}L_{n,i}$ is a non-negative martingale with unit initial
value.

By concavity of $\log$ and using $\sum_{j\in\\{i,i^{\star}\\}}N_{n,j}\leq n$,
we have

$c(n,\delta)\geq\log\left(\frac{K-1}{\delta}\right)+2+\sum_{j\in\\{i,i^{\star}\\}}\log\left(N_{n,j}+1\right)\>.$

Taking a union bound over $i\neq i^{\star}$ and using Ville’s inequality, we
obtain

$\displaystyle\mathbb{P}\left(\exists t\in\mathbb{N},\>\exists i\neq
i^{\star},\>N_{n,i}\mathcal{K}_{\inf}^{-}(F_{n,i},\mu_{i})+N_{n,i^{\star}}\mathcal{K}_{\inf}^{+}(F_{n,i^{\star}},\mu_{i^{\star}})>c(n,\delta)\right)$
$\displaystyle\leq\sum_{i\neq i^{\star}}\mathbb{P}\left(\exists
t\in\mathbb{N},\>Y^{-}_{n,i}+Y^{+}_{n,i^{\star}}>\log\left(\frac{K-1}{\delta}\right)\right)$
$\displaystyle\leq\sum_{i\neq i^{\star}}\mathbb{P}\left(\exists
t\in\mathbb{N},\>U_{n,i^{\star}}L_{n,i}>\frac{K-1}{\delta}\right)\leq\delta\>.$

Combining the above concentration with Lemma 32 yields the result. ∎

###  E.2 Sub-Gaussian random variables

We want to exhibit a sub-Gaussian random variables which controls the
deviation of various random variables to their means. More precisely, we will
prove the existence of $W_{1}$ in Lemma 5 and $W_{2}$ in Lemma 14.

######  Definition 3.

A random variable $X$ is said to be sub-Gaussian with constant $c$ if for all
$x\geq 0$, $\mathbb{P}(X\geq x)\leq e^{-cx^{2}/2}$ and for all $x\leq 0$,
$\mathbb{P}(X\leq x)\leq e^{-cx^{2}/2}$.

We are interested in sub-Gaussian random variable mainly due to the following
property.

######  Lemma 34.

If $X$ is sub-Gaussian, then for all $\lambda\in\mathbb{R}$,
$\mathbb{E}[e^{\lambda X}]<\infty$.

The proof can be found in any textbook dealing with sub-Gaussian random
variables, e.g. [42]. We will furthermore use the following classical
properties:

  * •

If $X$ and $Y$ are sub-Gaussian and $\alpha\in\mathbb{R}$ then $X+Y$ is sub-
Gaussian and $\alpha X$ is sub-Gaussian.

  * •

Bounded random variables are sub-Gaussian.

  * •

If $X$ verifies that for all $x\geq x_{1}\geq 0$, $\mathbb{P}(X\geq x)\leq
a_{1}e^{-c_{1}x^{2}/2}$ and for all $x\leq x_{2}\leq 0$, $\mathbb{P}(X\leq
x)\leq a_{2}e^{-c_{2}x^{2}/2}$, then $X$ is sub-Gaussian.

  * •

The maximum (or minimum) of a finite number of sub-Gaussian random variables
is sub-Gaussian.

######  Lemma 35.

If $(X_{n})_{n\in\mathbb{N},n\geq 1}$ are sub-Gaussian random variables with
constants $(c_{n})$ such that $\inf_{n}c_{n}>0$, then
$\sup_{n}\frac{X_{n}}{\sqrt{n\log(e+n)/(1+n)}}$ is sub-Gaussian.

###### Proof.

For $x\geq\sqrt{\frac{8}{\inf_{n}c_{n}}}$,

$\displaystyle\mathbb{P}(\xi\geq x)$
$\displaystyle\leq\sum_{n=1}^{\infty}\mathbb{P}\left(X_{n}\geq
x\sqrt{\frac{n\log(e+n)}{n+1}}\right)$
$\displaystyle\leq\sum_{n=1}^{\infty}\exp\left(-(\inf_{n}c_{n})x^{2}{\frac{n\log(e+n)}{n+1}}\right)$
$\displaystyle\leq\sum_{n=1}^{\infty}\exp\left(-\left[2\log(e+n)+\frac{\inf_{n}c_{n}}{2}\frac{x^{2}n}{n+1}\right]\right)$
$\displaystyle\leq\sum_{n=1}^{\infty}\exp\left(-\left[2\log(e+n)+\frac{\inf_{n}c_{n}}{4}x^{2}\right]\right)$
$\displaystyle=\left[\sum_{n=1}^{\infty}\frac{1}{(e+n)^{2}}\right]e^{-\frac{\inf_{n}c_{n}}{4}x^{2}}\>,$

where we have used that $\frac{n}{n+1}\geq\tfrac{1}{2}$ and that
$\alpha\beta\geq\alpha+\beta$ for $\alpha,\beta\geq 2$. Now for the lower
tail, for $x\leq 0$,

$\displaystyle\mathbb{P}(\xi\leq x)\leq\mathbb{P}\left(X_{1}\leq
x\sqrt{\frac{\log(1+e)}{2}}\right)\leq\exp\left(-\frac{\log(1+e)}{2}c_{1}x^{2}/2\right)\>.$

∎

##### Application to our work

We will use the following two examples of sub-Gaussian variables. Lemma 36 is
a consequence of the Dvoretzky-Kiefer-Wolfowitz (DKW) inequality [31] while
Lemma 37 follows from Azuma’s inequality.

######  Lemma 36.

Let $(X_{n})_{n\geq 1}$ be i.i.d. random variables with cdf $F$ and let
$F_{n}$ be the empirical distribution function of $(X_{i})_{i\in[n]}$. Then
for all $n$, $\sqrt{n}\|F_{n}-F\|_{\infty}$ is sub-Gaussian with a constant
which does not depend on $n$.

######  Lemma 37.

Let $(X_{n})_{n\geq 1}$ be a martingale with mean 0 and $c$-sub-Gaussian
increments and $\mu_{n}=X_{n}/n$. Then for all $n$, $\sqrt{n}\mu_{n}$ is sub-
Gaussian with constant $c$.

Theses results permit to establish the concentration results that are used in
Appendix C and D.

######  Lemma (Lemma 5 and 14).

There exists sub-Gaussian random variables $W_{1}$ and $W_{2}$ such that for
all $(n,i)\in\mathbb{N}\times[K]$ with $n\geq K+1$ (such that all arms are
pulled at least once)

$\displaystyle|N_{n,i}-\Psi_{n,i}|\leq
W_{1}\sqrt{(n+1)\log(e+n)}\quad\text{a.s.}\>,$
$\displaystyle\left\|{F}_{n,i}-F_{i}\right\|_{\infty}\leq
W_{2}\sqrt{\frac{\log(e+N_{n,i})}{1+N_{n,i}}}\quad\text{a.s.}\>.$

In particular, $\mathbb{E}\left[e^{\lambda W_{i}}\right]<+\infty$ for all
$\lambda>0$ and $i\in\\{1,2\\}$.

###### Proof.

For the first inequality, we use that $N_{n,i}-\Psi_{n,i}$ is a martingale and
combine Lemma 37 with Lemma 35 to get that for all $i\in[K]$

$W_{1,i}:=\sup_{n\geq
1}\frac{|N_{n,i}-\Psi_{n,i}|/\sqrt{n}}{\sqrt{n\log(e+n)/(1+n)}}$

is sub-Gaussian. Therefore $W_{1}=\max_{i\in[K]}W_{1,i}$ is sub-Gaussian and
we have, for all $(n,i)$,

$|N_{n,i}-\Psi_{n,i}|\leq W_{1}{\sqrt{\frac{n^{2}}{n+1}\log(e+n)}}\leq
W_{1}\sqrt{(n+1)\log(e+n)}.$

For the second inequality, we define $W_{2,i}:=\sup_{n\geq
K+1}\left\|{F}_{n,i}-F_{i}\right\|_{\infty}\sqrt{\frac{1+N_{n,i}}{\log(e+N_{n,i})}}$.
Letting $\hat{F}_{n,i}$ be the empirical distribution fo the first $n$ samples
from arm $i$ (while $F_{n,i}$ is the empirical distribution of the samples
collected up to time $n$), one can rewrite

$W_{2,i}=\sup_{n\geq
1}\left\|\hat{F}_{n,i}-F_{i}\right\|_{\infty}\sqrt{\frac{1+n}{\log(e+n)}}=\sup_{n\geq
1}\frac{\sqrt{n}\left\|\hat{F}_{n,i}-F_{i}\right\|_{\infty}}{\sqrt{n\log(e+n)/(1+n)}}.$

Combining Lemma 36 with Lemma 35 yields that $W_{2,i}$ is sub-Gaussian for all
$i\in[K]$. Then $W_{2}=\max_{i\in[K]}W_{2,i}$ is sub-Gaussian and we have, for
all $(n,i)$,

$\left\|{F}_{n,i}-F_{i}\right\|_{\infty}\leq
W_{1}\sqrt{\frac{1+N_{n,i}}{\log(e+N_{n,i})}}.$

∎

##  Appendix F Kinf for bounded distributions

Here, $\mathcal{F}$ is the set of probability distributions with support in
the interval $[0,B]$. The goal of this section is to study the properties of
$\mathcal{K}_{\inf}^{+}$ and $\mathcal{K}_{\inf}^{-}$, which are functions
$\mathcal{F}\times[0,B]\to\mathbb{R}_{+}$ defined by

$\displaystyle\mathcal{K}_{\inf}^{+}(F,\mu)$
$\displaystyle=\inf\\{\mathrm{KL}(F,G)\mid
G\in\mathcal{F},\mathbb{E}_{G}[X]>\mu\\}\>,$
$\displaystyle\mathcal{K}_{\inf}^{-}(F,\mu)$
$\displaystyle=\inf\\{\mathrm{KL}(F,G)\mid
G\in\mathcal{F},\mathbb{E}_{G}[X]<\mu\\}\>.$

As a first step, we remark that for $\mu\in(0,B)$ we can rewrite the
$\mathcal{K}_{\inf}$ functions using non-strict inequalities, which will be
more convenient [18, 17]. We do so and will work in this section on

$\displaystyle\mathcal{K}_{\inf}^{+}(F,\mu)$
$\displaystyle=\inf\\{\mathrm{KL}(F,G)\mid
G\in\mathcal{F},\mathbb{E}_{G}[X]\geq\mu\\}\>,$
$\displaystyle\mathcal{K}_{\inf}^{-}(F,\mu)$
$\displaystyle=\inf\\{\mathrm{KL}(F,G)\mid
G\in\mathcal{F},\mathbb{E}_{G}[X]\leq\mu\\}\>.$

There is a strong link between these two definitions, which we will use to
transport results from one function to the other.

######  Lemma 38.

Let $F\in\mathcal{F}$, $\mu\in[0,B]$ and let $f:[0,B]\to[0,B]$ be defined by
$f(x)=B-x$. Let $F^{B-X}$ be the pushforward measure of $F$ through $f$. Then

$\displaystyle\mathcal{K}_{\inf}^{+}(F^{B-X},B-\mu)=\mathcal{K}_{\inf}^{-}(F,\mu)\quad\text{
and
}\quad\mathcal{K}_{\inf}^{-}(F^{B-X},B-\mu)=\mathcal{K}_{\inf}^{+}(F,\mu)\>.$

###### Proof.

The function $f$ is measurable, bijective and involutive. We have
$\mathrm{KL}(F,G)=\mathrm{KL}(F^{B-X},G^{B-X})$ for all $F,G\in\mathcal{F}$.

$\displaystyle\mathcal{K}_{\inf}^{+}(F^{B-X},B-\mu)$
$\displaystyle=\inf\\{\mathrm{KL}(F^{B-X},G)\mid
G\in\mathcal{F},\mathbb{E}_{G}[X]\geq B-\mu\\}$
$\displaystyle=\inf\\{\mathrm{KL}(F^{B-X},G)\mid
G\in\mathcal{F},\mathbb{E}_{G^{B-X}}[X]\leq\mu\\}$
$\displaystyle=\inf\\{\mathrm{KL}(F^{B-X},(G^{B-X})^{B-X})\mid
G\in\mathcal{F},\mathbb{E}_{G^{B-X}}[X]\leq\mu\\}$
$\displaystyle=\inf\\{\mathrm{KL}(F,G^{B-X})\mid
G\in\mathcal{F},\mathbb{E}_{G^{B-X}}[X]\leq\mu\\}$
$\displaystyle=\inf\\{\mathrm{KL}(F,G)\mid
G\in\mathcal{F},\mathbb{E}_{G}[X]\leq\mu\\}$
$\displaystyle=\mathcal{K}_{\inf}^{-}(F,\mu)\>.$

∎

Let $\mathcal{F}^{+}(\mu)=\\{G\in\mathcal{F}\mid\mathbb{E}_{G}[X]\geq\mu\\}$
and define $\mathcal{F}^{-}(\mu)$ similarly.

######  Lemma 39.

For all $\mu\in[0,B]$, $\mathcal{F}^{+}(\mu)$ is a nonempty compact convex set
(for the weak convergence of measures).

###### Proof.

It is nonempty since the Dirac distribution at $B$ belongs to the set.

The set $\mathcal{F}$ is compact, hence a sequence of distributions in
$\mathcal{F}^{+}(\mu)$ admits a convergent subsequence. Suppose then that we
have a convergent sequence $(F_{n})_{n\in\mathbb{N}}$, converging to $F$, and
let’s show that $F\in\mathcal{F}^{+}(\mu)$. We can rewrite
$\mathcal{F}^{+}(\mu)=\\{G\in\mathcal{F}\mid\mathbb{E}_{G}[\max\\{X,B\\}]\geq\mu\\}\>.$
This is useful since the function $x\mapsto\max\\{x,B\\}$ is bounded from
above and continuous. We can thus apply the Portmanteau theorem to write

$\displaystyle\mathbb{E}_{F}[\max\\{X,B\\}]\geq\limsup_{n}\mathbb{E}_{F_{n}}[\max\\{X,B\\}]\geq\mu\>.$

We conclude that $F\in\mathcal{F}^{+}(\mu)$, which is then compact.

To prove convexity, let $F,G\in\mathcal{F}^{+}(\mu)$ and let $\alpha\in[0,1]$:
$\alpha F+(1-\alpha)G\in\mathcal{F}$ and

$\displaystyle\mathbb{E}_{\alpha
F+(1-\alpha)G}[X]=\alpha\mathbb{E}_{F}[X]+(1-\alpha)\mathbb{E}_{G}[X]\geq\alpha\mu+(1-\alpha)\mu=\mu\>.$

∎

######  Lemma 40.

$\mu\mapsto\mathcal{F}^{+}(\mu)$ is an upper hemicontinuous correspondence.

###### Proof.

Since $\mathcal{F}^{+}$ is a compact-valued correspondence (Lemma 39), it
suffices to show that for all sequences $(\mu_{n})$ and $(Q_{n})$ with
$Q_{n}\in\mathcal{F}^{+}(\mu_{n})$, if $\mu_{n}\to\mu$ then there exists a
convergent subsequence of $(Q_{n})$, which converges to
$Q\in\mathcal{F}^{+}(\mu)$ [40, Proposition 9.8, p. 231]. The existence of a
convergent subsequence comes from the compactness of $\mathcal{F}$. The limit
$Q$ then belongs to $\mathcal{F}$ since $\mathcal{F}$ is closed. We need to
show that $Q$ belongs to $\\{G\mid\mathbb{E}_{G}[X]\geq\mu\\}$.

We can rewrite
$\mathcal{F}^{+}(\mu)=\\{G\in\mathcal{F}\mid\mathbb{E}_{G}[\max\\{X,B\\}]\geq\mu\\}$
and prove that $Q$ belongs to
$\\{G\mid\mathbb{E}_{G}[\max\\{X,B\\}]\geq\mu\\}$. This is useful since the
function $x\mapsto\max\\{x,B\\}$ is bounded from above and continuous. We can
thus apply the Portmanteau theorem to write

$\displaystyle\mathbb{E}_{Q}[\max\\{X,B\\}]\geq\limsup_{n}\mathbb{E}_{Q_{n}}[\max\\{X,B\\}]\geq\limsup_{n}\mu_{n}=\mu\>.$

We conclude that $Q\in\mathcal{F}^{+}(\mu)$. We have proved upper
hemicontinuity. ∎

######  Lemma 41.

The infimum in the definition of $\mathcal{K}_{\inf}^{+}$ is attained at a
distribution in $\mathcal{F}^{+}(\mu)$.

###### Proof.

$G\mapsto\mathrm{KL}(F,G)$ is lower semicontinuous wrt the topology of weak
convergence of measures and the set $\mathcal{F}^{+}(\mu)$ over which the
minimization is performed is compact, hence the functions attains its infimum
at a point in $\mathcal{F}^{+}(\mu)$. ∎

###  F.1 Duality

For $(\lambda,F,u)\in\mathbb{R}_{+}\times\mathcal{F}\times[0,B]$, let
$H^{+}(\lambda,F,u)=\mathbb{E}_{F}[\log(1-\lambda(X-u))]$, where we define
$\log(x)=-\infty$ for $x\leq 0$. Let
$H^{-}(\lambda,F,u)=\mathbb{E}_{F}[\log(1+\lambda(X-u))]$.

######  Theorem 3.

For all $F\in\mathcal{F}$ and $u\in[0,B]$,

$\displaystyle\mathcal{K}_{\inf}^{+}(F,u)$
$\displaystyle=\sup_{\lambda\in[0,(B-u)^{-1}]}H^{+}(\lambda,F,u)\>,$
$\displaystyle\mathcal{K}_{\inf}^{-}(F,u)$
$\displaystyle=\sup_{\lambda\in[0,u^{-1}]}H^{-}(\lambda,F,u)\>.$

###### Proof.

A proof of this statement for $\mathcal{K}_{\inf}^{+}$ can be found in any one
of [18, 17]. The result for $\mathcal{K}_{\inf}^{-}$ then follows from Lemma
38. ∎

######  Lemma 42 ([18], Lemma 14).

For all $(F,u)\in\mathcal{F}\times[0,B)$,
$\mathcal{K}_{\inf}^{+}(F,u)\leq-\log\left(1-\frac{u}{B}\right)$.

###### Proof.

Let $(F,u)\in\mathcal{F}\times[0,B)$. The proof relies on Theorem 3 and $X\geq
0$ for all $X\in\mathrm{supp}(F)$. Using that $\log$ is increasing on
$(0,+\infty)$ and $\mathbb{E}_{F}[1]=1$,

$\displaystyle\mathcal{K}_{\inf}^{+}(F,u)$
$\displaystyle=\sup_{\lambda\in[0,(B-u)^{-1}]}H^{+}(\lambda,F,u)\leq\sup_{\lambda\in[0,(B-u)^{-1}]}\log\left(1+\lambda
u\right)=-\log\left(1-\frac{u}{B}\right)\>.$

∎

###  F.2 Continuity and differentiability

######  Lemma 43.

The function $\lambda,F,u\mapsto H^{+}(\lambda,F,u)$ is upper semicontinuous
(jointly in all arguments) on $\mathbb{R}_{+}\times\mathcal{F}\times[0,B]$.

###### Proof.

Let $(\lambda_{n},F_{n},u_{n})\in\mathbb{R}_{+}\times\mathcal{F}\times[0,B]$
be a sequence converging to $(\lambda,F,u)$. We want to prove that

$\displaystyle\limsup\mathbb{E}_{F_{n}}[\log(1-\lambda_{n}(X-u_{n}))]\leq\mathbb{E}_{F}[\log(1-\lambda(X-u))]\>.$

By Skorokhod’s representation theorem, there exists real random variables
$(X_{n})_{n\in\mathbb{N}},X$ defined on a common probability space
$(\Omega,\mathcal{A},\mathbb{P})$ such that the law of $X_{n}$ is $F_{n}$ for
all $n\in\mathbb{N}$, the law of $X$ is $F$ and $(X_{n})$ converges to $X$
almost surely (hence also in probability).

The family $(X_{n})$ has compact support, hence it is uniformly integrable. By
Vitali’s theorem, since $X_{n}$ is uniformly integrable and converges in
probability, it also converges in $L^{1}$.

We get that $\lambda_{n}(X_{n}-u_{n})\xrightarrow{a.s.}\lambda(X-u)$ and
$\mathbb{E}[\lambda_{n}(X_{n}-u_{n})]\to\mathbb{E}[\lambda(X-u)]$. Now we want
to translate this into a statement about the log.

Since $-\lambda_{n}(X_{n}-u_{n})-\log(1-\lambda_{n}(X_{n}-u_{n}))\geq 0$, by
Fatou’s lemma,

$\displaystyle\mathbb{E}\left[-\lambda(X-u)\right]-\mathbb{E}\left[\limsup\log(1-\lambda_{n}(X_{n}-u_{n}))\right]$
$\displaystyle=\mathbb{E}\left[\liminf\left(-\lambda_{n}(X_{n}-u_{n})-\log(1-\lambda_{n}(X_{n}-u_{n}))\right)\right]$
$\displaystyle\leq\liminf\left(\mathbb{E}\left[-\lambda_{n}(X_{n}-u_{n})-\log(1-\lambda_{n}(X_{n}-u_{n}))\right]\right)$
$\displaystyle=\mathbb{E}\left[-\lambda(X-u)\right]-\limsup\mathbb{E}\left[\log(1-\lambda_{n}(X_{n}-u_{n}))\right]\>.$

Canceling the first term, we get the inequality we were after. ∎

######  Theorem 4.

The function $\mathcal{K}_{\inf}^{+}$ (resp. $\mathcal{K}_{\inf}^{-}$) is
continuous on $\mathcal{F}\times[0,B)$ (resp. $\mathcal{F}\times(0,B]$).

###### Proof.

We follow the proof method of [5] (which applied to a slightly different
setting).

We first prove lower semicontinuity. We want to apply Berge’s Maximum Theorem
[9, Theorem 2, p. 116] to the correspondence $C(F,u)=\mathcal{F}^{+}(u)$ and
the function $f((F,u),G)=-\mathrm{KL}(F,G)$. We will obtain the upper
semicontinuity of $f^{*}(F,u):=\inf\\{f((F,u),G)\mid G\in
C(F,u)\\}=-\inf\\{\mathrm{KL}(F,G)\mid G\in\mathcal{F}^{+}(u)\\}$, which gives
us the lower semicontinuity we are after. We need to show that

  * •

$F,u\mapsto C(F,u)=\mathcal{F}^{+}(u)$ is upper hemicontinuous: this is proved
in Lemma 40,

  * •

$F,u,G\mapsto f(F,u,G)=-\mathrm{KL}(F,G)$ is upper semicontinuous (jointly in
all arguments): this is true since $\mathrm{KL}$ is jointly lower
semicontinuous [34].

We have lower semicontinuity on $\mathcal{F}\times[0,B]$.

To prove upper semicontinuity, we first use duality (Theorem 3) to write
$\mathcal{K}_{\inf}^{+}(F,u)=\sup_{\lambda\in[0,(B-u)^{-1}]}H^{+}(\lambda,F,u)$.
Since we want to prove semicontinuity on $\mathcal{F}\times[0,B)$, we can take
any $\varepsilon>0$ and prove it on $\mathcal{F}\times[0,B-\varepsilon]$.

We want to apply Berge’s Maximum Theorem [9, Theorem 2, p. 116] to the
correspondence $C(F,u)=\mathcal{[}0,(B-u)^{-1}]$ and the function
$f((F,u),\lambda)=\mathbb{E}_{F}[\log(1-\lambda(X-u))]$. We will obtain the
upper semicontinuity of $f^{*}(F,u)=\sup\\{f((F,u),G)\mid G\in C(F,u)\\}$,
which is exactly what we are after. We need to show that

  * •

$F,u\mapsto C(F,u)=[0,(B-u)^{-1}]$ is upper hemicontinuous, nonempty and
compact,

  * •

$F,u,\lambda\mapsto f(F,u,\lambda)=\mathbb{E}_{F}[\log(1-\lambda(X-u))]$ is
upper semicontinuous (jointly in all arguments): this is true by Lemma 43.

For the first point, nonempty compact values are obvious for $u\leq
B-\varepsilon$. The upper hemicontinuity comes from the continuity of the
upper bound of the interval. ∎

######  Lemma 44.

$\lambda\mapsto H^{+}(\lambda,F,u)$ is strictly concave on $[0,(B-u)^{-1})$.

###### Proof.

For $\alpha\in(0,1)$, by strict concavity of the logarithm,

$\displaystyle H^{+}(\alpha\lambda+(1-\alpha)\eta,F,u)$
$\displaystyle=\mathbb{E}_{F}[\log(\alpha(1-\lambda(X-u))+(1-\alpha)(1-\eta(X-u)))]$
$\displaystyle>\mathbb{E}_{F}[\alpha\log(1-\lambda(X-u))+(1-\alpha)\log(1-\eta(X-u))]$
$\displaystyle=\alpha H^{+}(\lambda,F,u)+(1-\alpha)H^{+}(\eta,F,u)\>.$

The restriction to the interval $[0,(B-u)^{-1})$ guarantees that all
quantities appearing in logarithms above are finite. ∎

######  Lemma 45.

$(\lambda,u)\mapsto H^{+}(\lambda,F,u)$ is continuous on
$\\{(\lambda,u)\in\mathbb{R}_{+}\times[0,B]\mid\lambda<(B-u)^{-1}\\}$.

###### Proof.

We already have upper semicontinuity by Lemma 43. We only need lower
semicontinuity. That is, we need that for $\lambda_{n}\to\lambda$ and
$u_{n}\to u$ in that set, we have

$\displaystyle\liminf_{n}\mathbb{E}_{F}[\log(1-\lambda_{n}(X-u_{n}))]\geq\mathbb{E}_{F}[\log(1-\lambda(X-u))]\>.$

There exists $\varepsilon>0$ such that $\lambda\leq(B-u)^{-1}(1-\varepsilon)$.
Then for $n$ big enough, $\lambda_{n}\leq(B-u_{n})^{-1}(1-\varepsilon/2)$. For
all $n$ large enough, we get
$\log(1-\lambda_{n}(X-u_{n}))-\log(\varepsilon/2)\geq 0$. By Fatou’s lemma,

$\displaystyle\liminf_{n}\mathbb{E}_{F}[\log(1-\lambda_{n}(X-u_{n}))-\log(\varepsilon/2)]\geq\mathbb{E}_{F}[\log(1-\lambda(X-u))-\log(\varepsilon/2)]\>.$

We cancel the $\log(\varepsilon/2)$ term and get the lower semicontinuity. ∎

Let
$\lambda_{\star}^{+}(F,u)=\operatorname*{arg\,max}_{\lambda\in[0,(B-u)^{-1}]}\mathbb{E}_{F}[\log(1-\lambda(X-u))]=\operatorname*{arg\,max}_{\lambda\in[0,(B-u)^{-1}]}H^{+}(\lambda,F,u)$
and
$\lambda_{\star}^{-}(F,u)=\operatorname*{arg\,max}_{\lambda\in[0,u^{-1}]}H^{-}(\lambda,F,u)$.

######  Lemma 46.

$u\mapsto\lambda_{\star}^{+}(F,u)$ is continuous over the set
$\\{u\in[0,B)\mid\lambda_{\star}^{+}(F,u)<(B-u)^{-1}\\}$.

###### Proof.

We first show that for any $\varepsilon\in(0,B^{-1}]$, the function
$u\mapsto\operatorname*{arg\,max}_{\lambda\in[0,(B-u)^{-1}-\varepsilon]}H^{+}(\lambda,F,u)$
is continuous on $[0,B)$ and the argmax is unique. This is not exactly
continuity of $u\mapsto\lambda_{\star}^{+}(F,u)$ because of the
$[0,(B-u)^{-1}-\varepsilon]$ interval instead of $[0,(B-u)^{-1}]$.

We will apply Berge’s Maximum theorem [9, page 116]. For
$\varepsilon\in(0,B^{-1}]$, let

$\displaystyle\varphi(\lambda,u)$ $\displaystyle=H(\lambda,F,u)\>,$
$\displaystyle\Gamma(u)$ $\displaystyle=[0,(B-u)^{-1}-\varepsilon]\>,$
$\displaystyle M(u)$
$\displaystyle=\max\\{H(\lambda,u)\mid\lambda\in\Gamma(u)\\}\>,$
$\displaystyle\Phi(u)$
$\displaystyle=\operatorname*{arg\,max}\\{\varphi(\lambda,u)\mid\lambda\in\Gamma(u)\\}\>.$

We verify the hypotheses of the theorem for any $\varepsilon^{\prime}>0$ and
$u<B-\varepsilon^{\prime}$:

  * •

$H$ is continuous on
$\\{(\lambda,u)\in\mathbb{R}_{+}\times[0,B]\mid\lambda<(B-u)^{-1}\\}$, by
Lemma 45, which is a domain containing $\Gamma(u)\times\\{u\\}$ for all $u$.

  * •

$\Gamma$ is nonempty (since $(B-u)^{-1}-\varepsilon\geq 0$), compact-valued
(since $u\leq B-\varepsilon^{\prime}$) and continuous.

We obtain that $M$ is continuous on $[0,B)$ and that $\Phi$ is upper
hemicontinuous.

Now since $\varphi$ is a strictly concave function of $\lambda$ (by Lemma 44)
and $\Gamma$ is convex, we can argue as in [40, Theorem 9.17] to prove that
$\Phi$ is a single-valued upper hemicontinuous correspondence, hence a
continuous function.

Now that we have proved the continuity of the argmax restricted to the
interval $[0,(B-u)^{-1}-\varepsilon]$, let’s prove the continuity of
$u\mapsto\lambda_{\star}^{+}(F,u)$ over the set
$\\{u\in[0,B)\mid\lambda_{\star}^{+}(F,u)<(B-u)^{-1}\\}$.

let $u\in[0,B)$ such that $\lambda_{\star}^{+}(F,u)<(B-u)^{-1}$. Then there
exists $\varepsilon>0$ such that

$\displaystyle\lambda_{\star}^{+}(F,u)$
$\displaystyle=\operatorname*{arg\,max}_{\lambda\in[0,(B-u)^{-1}-\varepsilon]}H^{+}(\lambda,F,u)\>,$
$\displaystyle\text{and }\lambda_{\star}^{+}(F,u)$
$\displaystyle\leq(B-u)^{-1}-3\varepsilon\>.$

Remark that by concavity of $H$ in $\lambda$, for all $u$, if
$\operatorname*{arg\,max}_{\lambda\in[0,(B-u)^{-1}-\varepsilon]}H^{+}(\lambda,F,u)\neq(B-u)^{-1}-\varepsilon$
then
$\lambda_{\star}^{+}(F,u)=\operatorname*{arg\,max}_{\lambda\in[0,(B-u)^{-1}-\varepsilon]}H^{+}(\lambda,F,u)$.

For $v$ in some neighborhood of $u$, we have both
$(B-v)^{-1}-\varepsilon>(B-u)^{-1}-2\varepsilon$ and
$\operatorname*{arg\,max}_{\lambda\in[0,(B-v)^{-1}-\varepsilon]}H^{+}(\lambda,F,v)<(B-u)^{-1}-2\varepsilon$.
This means that for all $v$ in that neighborhood,
$\lambda_{\star}^{+}(F,v)=\operatorname*{arg\,max}_{\lambda\in[0,(B-v)^{-1}-\varepsilon]}H^{+}(\lambda,F,v)$.
The continuity of the $\varepsilon$ version then gives continuity of
$\lambda_{\star}^{+}$ at $u$. ∎

######  Lemma 47 (Theorem 6 in [18]).

For all $F\in\mathcal{F}$ and $u\in(m(F),B]$,
$u\mapsto\mathcal{K}_{\inf}^{+}(F,u)$ is differentiable and

$\frac{\partial\mathcal{K}_{\inf}^{+}(F,u)}{\partial
u}=\lambda_{\star}^{+}(F,u)\>.$ (37)

For all $F\in\mathcal{F}$ and $u\in[0,m(F))$,
$u\mapsto\mathcal{K}_{\inf}^{-}(F,u)$ is differentiable and

$\frac{\partial\mathcal{K}_{\inf}^{-}(F,u)}{\partial
u}=-\lambda_{\star}^{-}(F,u)\>.$ (38)

###  F.3 Convexity

######  Lemma 48.

The functions $\mathcal{K}_{\inf}^{+}$ and $\mathcal{K}_{\inf}^{-}$ are
jointly convex on $\mathcal{F}\times[0,B]$.

###### Proof.

We prove the result for $\mathcal{K}_{\inf}^{+}$, but the proof for
$\mathcal{K}_{\inf}^{-}$ is identical. Let $F_{1},F_{2}\in\mathcal{F}$,
$u_{1},u_{2}\in[0,B]$ and let $G_{1},G_{2}\in\mathcal{F}$ be distributions at
which the infimum is attained in $\mathcal{K}_{\inf}^{+}(F_{1},u_{1})$ and
$\mathcal{K}_{\inf}^{+}(F_{2},u_{2})$ respectively (which exist by Lemma 41).
For all $\alpha\in[0,1]$, $\alpha G_{1}+(1-\alpha)G_{2}$ has expectation
$\alpha u_{1}+(1-\alpha)u_{2}$. Hence for all $\alpha\in[0,1]$,

$\displaystyle\mathcal{K}_{\inf}^{+}(\alpha F_{1}+(1-\alpha)F_{2},\alpha
u_{1}+(1-\alpha)u_{2})$ $\displaystyle\leq\mathrm{KL}(\alpha
F_{1}+(1-\alpha)F_{2},\alpha G_{1}+(1-\alpha)G_{2})$
$\displaystyle\leq\alpha\mathrm{KL}(F_{1},G_{1})+(1-\alpha)\mathrm{KL}(F_{2},G_{2})$
$\displaystyle=\alpha\mathcal{K}_{\inf}^{+}(F_{1},u_{1})+(1-\alpha)\mathcal{K}_{\inf}^{+}(F_{2},u_{2})$

The first inequality follows from the definition of $\mathcal{K}_{\inf}^{+}$
as an infimum and the second inequality comes from the joint convexity of the
Kullback-Leibler divergence. We have proved joint convexity. ∎

######  Lemma 49 (Theorem 5 in [18]).

Let $F\in\mathcal{F}$ and
$u^{+}(F)=B-\frac{1}{\mathbb{E}_{F}\left[\frac{1}{B-X}\right]}\geq m(F)$. We
have

$\lambda_{\star}^{+}(F,u)=0\>\iff\>u\leq m(F)\>,$ (39)
$u\in(m(F),u^{+}(F)]\>\implies\>\mathbb{E}_{F}\left[\frac{1}{1-\lambda_{\star}^{+}(F,u)(X-u)}\right]=1\>,$
(40)

and

$\lambda_{\star}^{+}(F,u)=\frac{1}{B-u}\>\iff\>u\geq u^{+}(F)\>.$ (41)

###### Proof.

First, we have

$\lambda_{\star}^{+}(F,u)=0\>\iff\>u\leq m(F)\>.$

If $\lambda_{\star}^{+}(F,u)=0$, then
$\mathcal{K}_{\inf}^{+}(F,u)=H^{+}(0,F,u)=0$, hence $u\leq m(F)$. The other
direction is obtained in Theorem 5 in [18].

Let $u^{+}(F)=B-\frac{1}{\mathbb{E}_{F}\left[\frac{1}{B-X}\right]}$ and
$u^{-}(F)=\frac{1}{\mathbb{E}_{F}\left[\frac{1}{X}\right]}$. Then,

$\displaystyle
u\in(m(F),u^{+}(F)]\>\implies\>\mathbb{E}_{F}\left[\frac{1}{1-\lambda_{\star}^{+}(F,u)(X-u)}\right]=1\>,$

Moreover,

$\lambda_{\star}^{+}(F,u)=\frac{1}{B-u}\>\iff\>u\geq u^{+}(F)\>.$

If $u\geq u^{+}(F)$, then $\mathbb{E}_{F}\left[\frac{B-u}{B-X}\right]\leq 1$,
hence $\lambda_{\star}^{+}(F,u)=\frac{1}{B-u}$ by Theorem 5 in [18]. Assume
that there exists $u<u^{+}(F)$, such that
$\lambda_{\star}^{+}(F,u)=\frac{1}{B-u}$. Then, by equation (40), we obtain
that
$1=\mathbb{E}_{F}\left[\frac{1}{1-\frac{X-u}{B-u}}\right]=\mathbb{E}_{F}\left[\frac{B-u}{B-X}\right]$.
This condition can be rewritten as $u=u(F)$, hence contradicting $u<u^{+}(F)$.
Therefore, we have shown $\lambda_{\star}^{+}(F,u)=\frac{1}{B-u}$ implies that
$u\geq u^{+}(F)$. ∎

######  Lemma 50.

The function $u\mapsto\mathcal{K}_{\inf}^{+}(F,u)$ is strictly convex on
$(m(F),B]$. The function $u\mapsto\mathcal{K}_{\inf}^{-}(F,u)$ is strictly
convex on $[0,m(F))$.

###### Proof.

We prove the result for $\mathcal{K}_{\inf}^{+}$. The proof for
$\mathcal{K}_{\inf}^{-}$ is similar.

Using Lemma 47, $u\mapsto\mathcal{K}_{\inf}^{+}(F,u)$ is strictly convex for
$u>m(F)$ if and only if $\lambda_{\star}^{+}(F,u)$ is increasing for $u>m(F)$.

Using (39), $\lambda_{\star}^{+}(F,u)$ is null for $u\leq m(F)$. Therefore,
$u\mapsto\mathcal{K}_{\inf}^{\pm}(F,u)$ is not strictly convex on those
intervals.

Using (41), we obtain directly that $\lambda_{\star}^{+}(F,u)$ is increasing
for $u\geq u^{+}(F)$.

Suppose towards contradiction that $u\mapsto\lambda_{\star}^{+}(F,u)$ is not
increasing for $(m(F),u^{+}(F))$. Therefore, there exists an open
$\mathcal{O}\subseteq(m(F),u^{+}(F))$, such that
$u\mapsto\lambda_{\star}^{+}(F,u)$ is constant on $\mathcal{O}$, i.e. there
exists $c_{\mathcal{O}}\in\left[0,\frac{1}{B-\inf_{u\in\mathcal{O}}u}\right]$
such that $\lambda_{\star}^{+}(F,u)=c_{\mathcal{O}}$. Using (39-41), we know
that $c_{\mathcal{O}}\in\left(0,\frac{1}{B-\inf_{u\in\mathcal{O}}u}\right)$.
On $\mathcal{O}$, $u\mapsto\lambda_{\star}^{+}(F,u)$ is constant, hence it is
continuously differentiable with null derivative. Since
$\mathcal{O}\subseteq(m(F),u^{+}(F))$, (40) defines implicitly
$\lambda_{\star}^{+}(F,u)$ as satisfying

$\mathbb{E}_{F}\left[\frac{1}{1-\lambda_{\star}^{+}(F,u)(X-u)}\right]=1\>.$

Since $\mathcal{O}\subseteq(m(F),u^{+}(F))$, we have
$\lambda_{\star}^{+}(F,u)\in\left(0,\frac{1}{B-\inf_{u\in\mathcal{O}}u}\right)$.
Therefore, the function
$(u,x)\mapsto\frac{1}{1-\lambda_{\star}^{+}(F,u)(x-u)}$ is bounded on
$[0,B]\times\mathcal{O}$, hence integrable, and the function
$u\mapsto\frac{1}{1-\lambda_{\star}^{+}(F,u)(x-u)}$ is continuously
differentiable. Moreover, the function
$x\mapsto\frac{1}{\left(1-\lambda_{\star}^{+}(F,u)(x-u)\right)^{2}}$ is
strictly positive and bounded on $[0,B]$, hence integrable with strictly
positive integrable. Having checked all the conditions to interchange the
derivative with the expectation, differentiating the above yields

$\displaystyle
0=\mathbb{E}_{F}\left[-\frac{\lambda_{\star}^{+}(F,u)+(u-X)\frac{\partial\lambda_{\star}^{+}(F,u)}{\partial
u}}{\left(1-(X-u)\lambda_{\star}^{+}(F,u)\right)^{2}}\right]=-c_{\mathcal{O}}\mathbb{E}_{F}\left[\frac{1}{\left(1-(X-u)c_{\mathcal{O}}\right)^{2}}\right]<0\>,$

where the strict inequality is obtained since we show that $c_{\mathcal{O}}>0$
and
$\mathbb{E}_{F}\left[\frac{1}{\left(1-(X-u)c_{\mathcal{O}}\right)^{2}}\right]>0$.
This is a contradiction, hence such $\mathcal{O}\subset(m(F),u^{+}(F))$
doesn’t exist. Therefore, $u\mapsto\lambda_{\star}^{+}(F,u)$ is increasing on
$(m(F),u^{+}(F))$.

Since the convexity already gave that $u\mapsto\lambda_{\star}^{+}(F,u)$ is
increasing on $(m(F),B]$. The fact that $u\mapsto\lambda_{\star}^{+}(F,u)$ is
increasing on $(m(F),u^{+}(F))$ and on $[u^{+}(F),B]$, yields that
$u\mapsto\lambda_{\star}^{+}(F,u)$ is increasing on $(m(F),B]$. ∎

######  Lemma 51.

$u\mapsto\mathcal{K}_{\inf}^{+}(F,u)$ is equal to zero on $[0,m(F)]$ and
increasing on $(m(F),B]$.

###### Proof.

We already proved that $\mathcal{K}_{\inf}^{+}(F,u)$ is equal to zero on
$[0,m(F)]$. Since $\mathcal{K}_{\inf}^{+}(F,m(F))=0$, $\mathcal{K}_{\inf}^{+}$
is nonnegative and strictly convex for $u>m(F)$, then
$u\mapsto\mathcal{K}_{\inf}^{+}(F,u)$ is increasing on $(m(F),B]$. ∎

######  Lemma 52.

For all $F,G\in\mathcal{F}$ with means $m(F)\leq m(G)$ and for all
$w\in\mathbb{R}_{+}^{2}$.

  * •

If $\max\\{w_{1},w_{2}\\}>0$, then $\mu\mapsto
w_{1}\mathcal{K}_{\inf}^{+}(F,\mu)+w_{2}\mathcal{K}_{\inf}^{-}(G,\mu)$ is
strictly convex on $[m(F),m(G)]$.

  * •

If $\min\\{w_{1},w_{2}\\}>0$, then $\mu\mapsto
w_{1}\mathcal{K}_{\inf}^{+}(F,\mu)+w_{2}\mathcal{K}_{\inf}^{-}(G,\mu)$ is
strictly convex on $[0,B]$.

###### Proof.

For $\mu\leq m(F)$, the function is equal to
$w_{2}\mathcal{K}_{\inf}^{-}(G,\mu)$, which is strictly convex unless
$w_{2}=0$. For $\mu\geq m(G)$, the function is equal to
$w_{1}\mathcal{K}_{\inf}^{+}(F,\mu)$, which is strictly convex unless
$w_{1}=0$. In the interval $(m(F),m(G))$, it is the sum of two convex
functions, one of which is strictly convex. Furthermore, the function is
continuous at $m(F)$ and $m(G)$. ∎

####  F.3.1 More continuity, using convexity

######  Lemma 53.

Let $F,G\in\mathcal{F}$ with means $m(F)\leq m(G)$ in $(0,B)$ and
$w\in\mathbb{R}_{+}^{2}$. Then

$\displaystyle\inf_{\mu\in[0,B]}(w_{1}\mathcal{K}_{\inf}^{+}(F,\mu)+w_{2}\mathcal{K}_{\inf}^{-}(G,\mu))=\inf_{\mu\in[m(F),m(G)]}(w_{1}\mathcal{K}_{\inf}^{+}(F,\mu)+w_{2}\mathcal{K}_{\inf}^{-}(G,\mu))\>.$

###### Proof.

On $[0,m(F)]$, $\mathcal{K}_{\inf}^{+}(F,\mu)$ is constant equal to 0 and
$\mathcal{K}_{\inf}^{-}(G,\mu)$ is non-increasing, hence the minimum over that
interval is attained at $m(F)$. We argue similarly for the interval
$[m(G),B]$. ∎

######  Lemma 54.

Let $F,G\in\mathcal{F}$ with means in $(0,B)$ and $w\in\mathbb{R}_{+}^{2}$.
Then

  1. 1.

$(F,G,w)\mapsto\inf_{\mu\in[0,B]}(w_{1}\mathcal{K}_{\inf}^{+}(F,\mu)+w_{2}\mathcal{K}_{\inf}^{-}(G,\mu))$
is continuous on $\mathcal{F}\times\mathcal{F}\times\mathbb{R}_{+}^{2}$.

  2. 2.

If $\max\\{w_{1},w_{2}\\}>0$,
$\mu_{\star}(F,G,w)=\operatorname*{arg\,min}_{\mu\in[0,B]}(w_{1}\mathcal{K}_{\inf}^{+}(F,\mu)+w_{2}\mathcal{K}_{\inf}^{-}(G,\mu))$
is unique and continuous on
$\mathcal{F}\times\mathcal{F}\times\mathbb{R}_{+}^{2}$.

###### Proof.

We can restrict the inf to $[\mu_{F},\mu_{G}]$ by Lemma 53.

We will apply Berge’s Maximum theorem [9, page 116]. Let

$\displaystyle\varphi(\mu,F,G,w)$
$\displaystyle=-w_{1}\mathcal{K}_{\inf}^{+}(F,\mu)-w_{2}\mathcal{K}_{\inf}^{-}(G,\mu)\>,$
$\displaystyle\Gamma(F,G,w)$ $\displaystyle=[\mu_{F},\mu_{G}]\>,$
$\displaystyle M(F,G,w)$
$\displaystyle=\max\\{\varphi(\mu,F,G,w)\mid\mu\in\Gamma(F,G,w)\\}\>,$
$\displaystyle\Phi(F,G,w)$
$\displaystyle=\operatorname*{arg\,max}\\{\varphi(\mu,F,G,w)\mid\mu\in\Gamma(F,G,w)\\}\>.$

We verify the hypotheses of the theorem:

  * •

$\varphi$ is continuous on
$[\mu_{F},\mu_{G}]\times\mathcal{F}\times\mathcal{F}\times C$, by Theorem 4
since $\mu_{F},\mu_{G}\in(0,B)$.

  * •

$\Gamma$ is nonempty, compact-valued and continuous (since constant).

We obtain that $M$ is continuous on
$\mathcal{F}\times\mathcal{F}\times\mathbb{R}_{+}^{2}$ and that $\Phi$ is
upper hemicontinuous.

Now since $\varphi$ is a strictly concave function of $\mu$ (by Lemma 52) and
$\Gamma$ is convex, we can argue as in [40, Theorem 9.17] to prove that $\Phi$
is a single-valued upper hemicontinuous correspondence, hence a continuous
function. ∎

######  Lemma 55.

Let $F,G\in\mathcal{F}$ with means $m(F)<m(G)$ in $(0,B)$ and
$w\in\mathbb{R}_{+}^{2}$ such that $\min\\{w_{1},w_{2}\\}>0$. The value
$\mu_{\star}(F,G,w)=\operatorname*{arg\,min}_{\mu\in[0,B]}(w_{1}\mathcal{K}_{\inf}^{+}(F,\mu)+w_{2}\mathcal{K}_{\inf}^{-}(G,\mu))$
(unique by Lemma 54) belongs to the interval $(m(F),m(G))$ and is such that
both $\mathcal{K}_{\inf}$ are positive.

###### Proof.

We know by Lemma 53 that the minimum is attained inside $[m(F),m(G)]$. We only
need to exclude the boundaries.

The function $\mu\mapsto
w_{1}\mathcal{K}_{\inf}^{+}(F,\mu)+w_{2}\mathcal{K}_{\inf}^{-}(G,\mu)$ is
differentiable on $(m(F),m(G))$ with derivative
$w_{1}\lambda_{\star}^{+}(F,\mu)-w_{2}\lambda_{\star}^{-}(G,\mu)$. If we show
that this derivatives takes the value zero in the open interval, then we prove
the result.

For $\mu>m(F)$ in a neighborhood of $m(F)$, $\lambda_{\star}^{+}(F,\mu)$ tends
to 0 by continuity (Lemma 46) and
$\lambda_{\star}^{-}(G,\mu)>\lambda_{\star}^{-}(G,\frac{m(F)+m(G)}{2})>0$. We
get that close to $m(F)$, the derivative is negative. Similarly, we get that
the derivative is positive close to $m(G)$. We conclude that the infimum is
indeed attained inside the open interval. ∎

######  Lemma 56.

Let $F,G\in\mathcal{F}$ with means $m(F)<m(G)$ in $(0,B)$ and $w_{1}>0$. Then
$w_{2}\mapsto\min_{\mu\in[0,B]}(w_{1}\mathcal{K}_{\inf}^{+}(F,\mu)+w_{2}\mathcal{K}_{\inf}^{-}(G,\mu))$
is increasing on $\mathbb{R}_{+}$.

###### Proof.

Let $w_{2}^{\prime}>w_{2}\geq 0$. Then by Lemma 55, since $w_{2}^{\prime}>0$,
there exists $\mu^{\prime}\in[0,B]$ with
$\mathcal{K}_{\inf}^{-}(G,\mu^{\prime})>0$ such that
$\min_{\mu\in[0,B]}(w_{1}\mathcal{K}_{\inf}^{+}(F,\mu)+w_{2}^{\prime}\mathcal{K}_{\inf}^{-}(G,\mu))=w_{1}\mathcal{K}_{\inf}^{+}(F,\mu^{\prime})+w_{2}^{\prime}\mathcal{K}_{\inf}^{-}(G,\mu^{\prime})$.
Then we have

$\displaystyle\min_{\mu\in[0,B]}(w_{1}\mathcal{K}_{\inf}^{+}(F,\mu)+w_{2}^{\prime}\mathcal{K}_{\inf}^{-}(G,\mu))$
$\displaystyle=w_{1}\mathcal{K}_{\inf}^{+}(F,\mu^{\prime})+w_{2}^{\prime}\mathcal{K}_{\inf}^{-}(G,\mu^{\prime})$
$\displaystyle>w_{1}\mathcal{K}_{\inf}^{+}(F,\mu^{\prime})+w_{2}\mathcal{K}_{\inf}^{-}(G,\mu^{\prime})$
$\displaystyle\geq\min_{\mu\in[0,B]}(w_{1}\mathcal{K}_{\inf}^{+}(F,\mu)+w_{2}\mathcal{K}_{\inf}^{-}(G,\mu))\>.$

∎

######  Lemma 57.

Let $F,G,F_{1},\ldots,F_{K}\in\mathcal{F}$ with means in $(0,B)$.

The function
$w\mapsto\min_{\mu\in[0,B]}(w_{1}\mathcal{K}_{\inf}^{+}(F,\mu)+w_{2}\mathcal{K}_{\inf}^{-}(G,\mu))$
is concave on $\mathbb{R}_{+}^{2}$.

The function $w\mapsto\min_{j\neq
1}\min_{\mu\in[0,B]}(w_{1}\mathcal{K}_{\inf}^{-}(F_{1},\mu)+w_{j}\mathcal{K}_{\inf}^{+}(F_{j},\mu))$
is concave on $\mathbb{R}_{+}^{K}$.

###### Proof.

These functions are minimums of linear functions, hence concave. ∎

###  F.4 Properties of the characteristic time

Let $\bm{F}\in\mathcal{F}^{K}$ and $i^{\star}=i^{\star}(\bm{F})$, supposed
unique. Recall that

$\displaystyle T^{\star}(\bm{F})^{-1}$
$\displaystyle=\sup_{w\in\triangle_{K}}\min_{i\neq
i^{\star}}\inf_{u\in[0,B]}\left\\{w_{i^{\star}}\mathcal{K}_{\inf}^{-}(F_{i^{\star}},u)+w_{i}\mathcal{K}_{\inf}^{+}(F_{i},u)\right\\}\>,$
$\displaystyle w^{\star}(\bm{F})$
$\displaystyle=\operatorname*{arg\,max}_{w\in\triangle_{K}}\min_{i\neq
i^{\star}}\inf_{u\in[0,B]}\left\\{w_{i^{\star}}\mathcal{K}_{\inf}^{-}(F_{i^{\star}},u)+w_{i}\mathcal{K}_{\inf}^{+}(F_{i},u)\right\\}\>,$
$\displaystyle T_{\beta}^{\star}(\bm{F})^{-1}$
$\displaystyle=\sup_{\begin{subarray}{c}w\in\triangle_{K}\\\
w_{i^{\star}}=\beta\end{subarray}}\min_{i\neq
i^{\star}}\inf_{u\in[0,B]}\left\\{w_{i^{\star}}\mathcal{K}_{\inf}^{-}(F_{i^{\star}},u)+w_{i}\mathcal{K}_{\inf}^{+}(F_{i},u)\right\\}\>,$
$\displaystyle w_{\beta}^{\star}(\bm{F})$
$\displaystyle=\operatorname*{arg\,max}_{\begin{subarray}{c}w\in\triangle_{K}\\\
w_{i^{\star}}=\beta\end{subarray}}\min_{i\neq
i^{\star}}\inf_{u\in[0,B]}\left\\{w_{i^{\star}}\mathcal{K}_{\inf}^{-}(F_{i^{\star}},u)+w_{i}\mathcal{K}_{\inf}^{+}(F_{i},u)\right\\}\>.$

######  Lemma 58.

The functions ${T^{\star}}^{-1}$ and ${T^{\star}_{\beta}}^{-1}$ are continuous
on $\mathcal{F}^{K}$. The correspondences $w^{\star}$ and $w^{\star}_{\beta}$
are upper hemicontinuous on $\mathcal{F}^{K}$ with compact convex values.

###### Proof.

Let $\mathcal{F}^{K}_{i}=\left\\{\bm{F}\in\mathcal{F}^{K}\mid i\in
i^{\star}(\bm{F})\right\\}$. Since
$\bigcup_{i\in[K]}\mathcal{F}^{K}_{i}=\mathcal{F}^{K}$, it is enough to show
the property for all $\mathcal{F}^{K}_{i}$ for $i\in[K]$. Let
$i^{\star}\in[K]$.

First, the function $(w,\bm{F})\mapsto\min_{i\neq
i^{\star}}\inf_{u\in[0,B]}\left\\{w_{i^{\star}}\mathcal{K}_{\inf}^{-}(F_{i^{\star}},u)+w_{i}\mathcal{K}_{\inf}^{+}(F_{i^{\star}},u)\right\\}$
is continuous on $\triangle_{K}\times\mathcal{F}^{K}$ by Lemma 54 and the fact
that a minimum of continuous functions is continuous. It is concave in $w$ by
Lemma 57.

The correspondence $(w,\bm{F})\mapsto\triangle_{K}$ is nonempty compact-valued
and continuous (since constant). By Berge’s maximum theorem, we get that
$T^{\star}(\bm{F})^{-1}$ is continuous on $\mathcal{F}^{K}_{i^{\star}}$ and
that $w^{\star}(\bm{F})$ is upper hemicontinuous with compact values. By [40,
Theorem 9.17], the concavity of the function being maximized implies that
$w^{\star}(\bm{F})$ is convex-valued.

The correspondence
$(w,\bm{F})\mapsto\triangle_{K}\cap\\{w_{i^{\star}}=\beta\\}$ is nonempty
compact-valued and continuous (since constant). By Berge’s maximum theorem, we
get that $T_{\beta}^{\star}(\bm{F})^{-1}$ is continuous on
$\mathcal{F}^{K}_{i^{\star}}$ and that $w^{\star}_{\beta}(\bm{F})$ is upper
hemicontinuous with compact values. By [40, Theorem 9.17], the concavity of
the function being maximized implies that $w_{\beta}^{\star}(\bm{F})$ is
convex-valued. ∎

######  Lemma 59.

If $i^{\star}(\bm{F})$ is a singleton and $\beta\in(0,1)$, then
$T^{\star}(\bm{F})^{-1}>0$ and $T_{\beta}^{\star}(\bm{F})^{-1}>0$.

###### Proof.

$\displaystyle T^{\star}(\bm{F})^{-1}$
$\displaystyle=\sup_{w\in\triangle_{K}}\min_{i\neq
i^{\star}}\inf_{u\in[0,B]}\left\\{w_{i^{\star}}\mathcal{K}_{\inf}^{-}(F_{i^{\star}},u)+w_{i}\mathcal{K}_{\inf}^{+}(F_{i},u)\right\\}$
$\displaystyle\geq\min_{i\neq
i^{\star}}\inf_{u\in[0,B]}\left\\{\frac{1}{K}\mathcal{K}_{\inf}^{-}(F_{i^{\star}},u)+\frac{1}{K}\mathcal{K}_{\inf}^{+}(F_{i},u)\right\\}>0\>,$

since we proved that the inner infimum is positive for nonzero coefficients
and $\mu_{i}<\mu_{i^{\star}}$. The proof for $T_{\beta}^{\star}$ is similar. ∎

######  Lemma 60.

If $i^{\star}(\bm{F})$ is a singleton and $\beta\in(0,1)$, then for all
$i\in[K]$, $w^{\star}_{i}(\bm{F})>0$ and $w^{\star}_{\beta,i}(\bm{F})>0$.

###### Proof.

We proceed by contradiction. If $i^{\star}(\bm{F})$ is unique and there exists
$j$ with $w^{\star}_{j}(\bm{F})=0$, then we show $T^{\star}(\bm{F})^{-1}=0$,
which is absurd by Lemma 59. If $j=i^{\star}$ we have

$\displaystyle T^{\star}(\bm{F})^{-1}=\min_{i\neq
i^{\star}}\inf_{u\in[0,B]}w_{i}^{\star}\mathcal{K}_{\inf}^{+}(F_{i},u)\leq\min_{i\neq
i^{\star}}w_{i}^{\star}\mathcal{K}_{\inf}^{+}(F_{i},F_{i})=0\>.$

If $j\neq i^{\star}$,

$\displaystyle T^{\star}(\bm{F})^{-1}$ $\displaystyle=\min_{i\neq
i^{\star}}\inf_{u\in[0,B]}\left\\{w_{i^{\star}}^{\star}\mathcal{K}_{\inf}^{-}(F_{i^{\star}},u)+w_{i}^{\star}\mathcal{K}_{\inf}^{+}(F_{i},u)\right\\}$
$\displaystyle\leq\inf_{u\in[0,B]}\left\\{w_{i^{\star}}^{\star}\mathcal{K}_{\inf}^{-}(F_{i^{\star}},u)+w_{j}^{\star}\mathcal{K}_{\inf}^{+}(F_{j},u)\right\\}$
$\displaystyle=\inf_{u\in[0,B]}w_{i^{\star}}^{\star}\mathcal{K}_{\inf}^{-}(F_{i^{\star}},u)=0\>.$

A similar proof holds for $T_{\beta}^{\star}$. ∎

######  Lemma 61.

If $i^{\star}(\bm{F})$ is a singleton and $\beta\in(0,1)$, then

  * •

for all $i\neq i^{\star}(\bm{F})$,
$\inf_{u\in[0,B]}\left\\{w_{i^{\star}}^{\star}(\bm{F})\mathcal{K}_{\inf}^{-}(F_{i^{\star}},u)+w_{i}^{\star}(\bm{F})\mathcal{K}_{\inf}^{+}(F_{i},u)\right\\}=T^{\star}(\bm{F})^{-1}$
,

  * •

for all $i\neq i^{\star}(\bm{F})$,
$\inf_{u\in[0,B]}\left\\{\beta\mathcal{K}_{\inf}^{-}(F_{i^{\star}},u)+w_{\beta,i}^{\star}(\bm{F})\mathcal{K}_{\inf}^{+}(F_{i},u)\right\\}=T_{\beta}^{\star}(\bm{F})^{-1}$
,

  * •

$w^{\star}(\bm{F})$ and $w_{\beta}^{\star}(\bm{F})$ are singletons: the
optimal allocations are unique.

###### Proof.

At the optimal allocations, all $w_{i}$ are positive. Suppose w.l.o.g. that 1
is the best arm. By dividing by $w_{1}$ and defining

$G_{j}(x)=\inf_{u\in[0,B]}\left(\mathcal{K}_{\inf}^{-}(F_{i^{\star}},u)+x\mathcal{K}_{\inf}^{+}(F_{j},u)\right)\>,$

we obtain directly that

$\displaystyle
T^{\star}(\bm{F})^{-1}=\max_{w\in\triangle_{K},w_{1}>0}w_{1}\min_{j\neq
1}G_{j}\left(\frac{w_{j}}{w_{1}}\right)\>.$

Let $w^{\star}\in w^{\star}(\bm{F})$. Then, using the above result, we obtain

$\displaystyle
w^{\star}\in\operatorname*{arg\,max}_{w\in\triangle_{K}}w_{1}\min_{j\neq
1}G_{j}\left(\frac{w_{j}}{w_{1}}\right)$

Introducing $x_{j}^{\star}=\frac{w^{\star}_{j}}{w_{1}^{\star}}$ for all $j\neq
1$, using that $\sum_{j\in[K]}w_{j}^{\star}=1$, one has

$\displaystyle
w_{1}^{\star}=\frac{1}{1+\sum_{j=2}^{K}x_{j}^{\star}}\quad\text{ and, for
}j\geq 2,w^{\star}_{j}=\frac{x_{j}^{\star}}{1+\sum_{j=2}^{K}x_{j}^{\star}}\>.$

If $x^{\star}$ is unique, then so is $w^{\star}$.

Since it is optimal, $\\{x_{j}^{\star}\\}_{j=2}^{K}\in\mathbb{R}^{K-1}$
belongs to

$\operatorname*{arg\,max}_{\\{x_{j}\\}_{j=2}^{K}\in\mathbb{R}^{K-1}}\frac{\min_{j\neq
1}G_{j}\left(x_{j}\right)}{1+\sum_{j=2}^{K}x_{j}}$ (42)

Let’s show that all the $G_{j}\left(x_{j}^{\star}\right)$ have to be equal.
Let $\mathcal{O}=\left\\{i\in[K]\setminus\\{1\\}\mid
G_{i}\left(x_{i}^{\star}\right)=\min_{j\neq
1}G_{j}\left(x_{j}^{\star}\right)\right\\}$ and
$\mathcal{A}=[K]\setminus(\\{1\\}\cup\mathcal{O})$. Assume that
$\mathcal{A}\neq\emptyset$. For all $a\in\mathcal{A}$ and $b\in\mathcal{O}$,
one has $G_{j}\left(x_{j}^{\star}\right)>G_{i}\left(x_{i}^{\star}\right)$.
Using the continuity of the $G_{j}$ functions and the fact that they are
increasing (Lemma 56), there exists $\varepsilon>0$ such that

$\displaystyle\forall j\in\mathcal{A},i\in\mathcal{O},\quad
G_{j}\left(x_{j}^{\star}-\varepsilon/|\mathcal{A}|\right)>G_{i}\left(x_{i}^{\star}+\varepsilon/|\mathcal{O}|\right)>G_{i}\left(x_{i}^{\star}\right)\>.$

We introduce $\bar{x}_{j}=x_{j}^{\star}-\varepsilon/|\mathcal{A}|$ for all
$j\in\mathcal{A}$ and $\bar{x}_{i}=x_{i}^{\star}+\varepsilon/|\mathcal{O}|$
for all $i\in\mathcal{O}$, hence
$\sum_{j=2}^{K}\bar{x}_{j}=\sum_{j=2}^{K}x_{j}^{\star}$. There exists
$i\in\mathcal{O}$ such that $\min_{j\neq
1}G_{j}\left(\bar{x}_{j}\right)=G_{i}\left(x_{i}^{\star}+\varepsilon/|\mathcal{O}|\right)$,
hence

$\displaystyle\frac{\min_{j\neq
1}G_{j}\left(\bar{x}_{j}\right)}{1+\bar{x}_{2}+\ldots\bar{x}_{K}}=\frac{G_{i}\left(x_{i}^{\star}+\varepsilon/|\mathcal{O}|\right)}{1+x_{2}^{\star}+\cdots+x_{K}^{\star}}>\frac{G_{i}\left(x_{i}^{\star}\right)}{1+x_{2}^{\star}+\cdots+x_{K}^{\star}}=\frac{\min_{j\neq
1}G_{j}\left(x_{j}^{\star}\right)}{1+x_{2}^{\star}+\cdots+x_{K}^{\star}}\>.$

This is a contradiction with the fact that $x^{\star}$ belongs to (42).
Therefore, we have $\mathcal{A}=\emptyset$.

We have proved that there is a unique value by $y^{\star}\in\mathbb{R}_{+}$,
such that for all $j\neq 1$, $G_{j}\left(x_{j}^{\star}\right)=y^{\star}$. Now
since $G_{j}$ is increasing, this defines a unique value for $x_{j}^{\star}$,
equal to $G_{j}^{-1}(y^{\star})$.

For $y$ in the intersection of the ranges of all $G_{j}$, let
$x_{j}(y)=G_{j}^{-1}(y)$. $y^{\star}$ belongs to

$\operatorname*{arg\,max}_{y\in\left[0,\min_{j\neq
1}\lim_{+\infty}G_{j}(x)\right)}\frac{y}{1+\sum_{j\neq 1}x_{j}(y)}\>.$ (43)

For $\beta\in(0,1)$, the same results (and proof) hold for
$w_{\beta}^{\star}(\bm{F})$ by noting that

$\displaystyle
T^{\star}_{\beta}(\bm{F})^{-1}=\max_{w\in\triangle_{K}:w_{1}=\beta}\beta\min_{j\neq
1}G_{j}\left(\frac{w_{j}}{\beta}\right)\>.$

Let $w^{\beta}\in w_{\beta}^{\star}(\bm{F})$, since we have equality at the
equilibrium, we obtain for all $j\neq 1$,

$\displaystyle\beta
G_{j}\left(\frac{w^{\beta}_{j}}{\beta}\right)=T^{\star}_{\beta}(\bm{F})^{-1}\>,$

Using the inverse mapping $x_{j}$, we obtain for all $j\neq 1$,

$\displaystyle w^{\beta}_{j}=\beta
x_{j}\left(\frac{1}{T^{\star}_{\beta}(\bm{F})\beta}\right)\>.$

Therefore, we have shown that $w_{\beta}^{\star}(\bm{F})=\\{w^{\beta}\\}$,
where

$\displaystyle w^{\beta}_{i}=\begin{cases}\beta
x_{i}\left(\frac{1}{T^{\star}_{\beta}(\bm{F})\beta}\right)&\text{if }i\neq
i^{\star}\\\ \beta&\text{else}\end{cases}\>.$

∎

######  Lemma 62.

$T^{\star}_{1/2}(\bm{F})\leq 2T^{\star}(\bm{F})$ and with
$\beta^{\star}=w^{\star}_{i^{\star}}(\bm{F})$,

$\displaystyle\frac{T^{\star}(\bm{F})^{-1}}{T^{\star}_{\beta}(\bm{F})^{-1}}\leq\max\left\\{\frac{\beta^{\star}}{\beta},\frac{1-\beta^{\star}}{1-\beta}\right\\}\>.$

###### Proof.

Define for each non-negative vector $\bm{\psi}\in\mathbb{R}_{+}^{K}$,

$\displaystyle f(\bm{\psi}):=\min_{i\neq
i^{\star}(\bm{F})}\inf_{u\in[0,B]}\left\\{\psi_{i^{\star}}\mathcal{K}_{\inf}^{-}(F_{i^{\star}},u)+\psi_{i}\mathcal{K}_{\inf}^{+}(F_{i},u)\right\\}\>.$

$T^{\star}(\bm{F})^{-1}$ is the maximum of $f(\bm{\psi})$ over probability
vectors $\bm{\psi}$. Here, we instead define $f$ for all non-negative vectors,
and proceed by varying the total budget of measurement effort available
$\sum_{a\in[K]}\psi_{a}$. $f$ is non-decreasing in $\psi_{i}$ for all $i$. $f$
is homogeneous of degree $1$. That is $f(c\bm{\psi})=cf(\bm{\psi})$ for all
$c\geq 1$. For each $c_{1}$, $c_{2}>0$ define

$g\left(c_{1},c_{2}\right)=\max\left\\{f(\bm{\psi})\mid\bm{\psi}\in\mathbb{R}_{+}^{K},\>\psi_{i^{\star}(\bm{F})}=c_{1},\sum_{i\neq
i^{\star}(\bm{F})}\psi_{i}\leq c_{2},\right\\}$

The function $g$ inherits key properties of $f$; it is also non-decreasing and
homogeneous of degree 1 . We have

$\displaystyle T^{\star}_{\beta}(\bm{F})^{-1}$
$\displaystyle=\max\left\\{f(\bm{\psi})\mid\bm{\psi}\in\mathbb{R}_{+}^{K},\>\psi_{i^{\star}(\bm{F})}=\beta,\sum_{i\in[K]}\psi_{i}=1\right\\}$
$\displaystyle=\max\left\\{f(\bm{\psi})\mid\bm{\psi}\in\mathbb{R}_{+}^{K},\>\psi_{i^{\star}(\bm{F})}=\beta,\sum_{i\neq
i^{\star}(\bm{F})}\psi_{i}\leq 1-\beta\right\\}$
$\displaystyle=g(\beta,1-\beta)$

where the second equality uses that $f$ is non-decreasing. Similarly,
$T^{\star}(\bm{F})^{-1}=g\left(\beta^{\star},1-\beta^{\star}\right)$ where
$\beta^{\star}=w^{\star}_{i^{\star}(\bm{F})}(\bm{F})$. Setting

$r:=\max\left\\{\frac{\beta^{\star}}{\beta},\frac{1-\beta^{\star}}{1-\beta}\right\\}$

implies $r\beta\geq\beta^{\star}$ and $r(1-\beta)\geq 1-\beta^{\star}$.
Therefore

$rT^{\star}_{\beta}(\bm{F})^{-1}=rg(\beta,1-\beta)=g(r\beta,r(1-\beta))\geq
g\left(\beta^{\star},1-\beta^{\star}\right)=T^{\star}(\bm{F})^{-1}\>.$

Taking $\beta=\frac{1}{2}$, yields that $T^{\star}(\bm{F})^{-1}\leq
2\max\\{\beta^{\star},1-\beta^{\star}\\}T^{\star}_{1/2}(\bm{F})^{-1}\leq
2T^{\star}_{1/2}(\bm{F})^{-1}$. ∎

######  Lemma 63.

Let
$G_{i}(x)=\inf_{u\in[0,B]}\left(\mathcal{K}_{\inf}^{-}(F_{i^{\star}},u)+x\mathcal{K}_{\inf}^{+}(F_{i},u)\right)$
for $x\in[0,+\infty)$ and $i\neq i^{\star}$. Then,

$\lim_{x\to+\infty}G_{i}(x)=\mathcal{K}_{\inf}^{-}(F_{i^{\star}},m(F_{i}))\>.$

###### Proof.

Let
$u_{i}(x)\in\operatorname*{arg\,min}_{u\in[0,B]}\left(\mathcal{K}_{\inf}^{-}(F_{i^{\star}},u)+x\mathcal{K}_{\inf}^{+}(F_{i},u)\right)$.
It is easy to see that $G_{i}(0)=0$ and $u_{i}(0)=m(F_{1})$. Likewise, we have
$u_{i}(x)=_{+\infty}m(F_{i})+o(1)$ by considering $(w_{i^{\star}},w_{i})$
instead of $x_{i}=\frac{w_{i}}{w_{i^{\star}}}$. By continuity of
$u\mapsto\mathcal{K}_{\inf}^{-}(F_{i^{\star}},u)$ and using the definition of
$u_{i}(x)$

$\lim_{x\to+\infty}G_{i}(x)=\mathcal{K}_{\inf}^{-}(F_{i^{\star}},m(F_{i}))+\lim_{x\to+\infty}x\mathcal{K}_{\inf}^{+}(F_{i},u_{i}(x))\>.$

Using the deviations bounds on the $u\mapsto\mathcal{K}_{\inf}^{-}(F,u)$ (e.g.
Lemma 6 in [19]), we obtain that

$0<x\mathcal{K}_{\inf}^{-}(F_{i},u_{i}(x))\leq
x\frac{(m(F_{i})-u_{i}(x))^{2}}{2}\>.$

Therefore, a sufficient condition to obtain
$\lim_{x\to+\infty}x\mathcal{K}_{\inf}^{+}(F_{i},u_{i}(x))=0$ is to show that
$u_{i}(x)=_{+\infty}m(F_{i})+o\left(\frac{1}{\sqrt{x}}\right)$. The first
order condition of optimality on $u_{i}(x)$ can be expressed as

$\displaystyle x\frac{\partial\mathcal{K}_{\inf}^{+}(F_{i},u_{i}(x))}{\partial
u}=-\frac{\partial\mathcal{K}_{\inf}^{-}(F_{i^{\star}},u_{i}(x))}{\partial
u}\iff\quad$ $\displaystyle
x\lambda_{\star}^{+}(F_{i},u_{i}(x))=\lambda_{\star}^{-}(F_{i^{\star}},u_{i}(x))\>,$

where we used Lemma 47 for the equivalent formulation.

Using that $u\mapsto\lambda_{\star}^{-}(F,u)$ is decreasing for
$u<m(F_{i^{\star}})$ (Lemma 50 and Lemma 47) yields

$\displaystyle
x\lambda_{\star}^{+}(F_{i},u_{i}(x))=\lambda_{\star}^{-}(F_{i^{\star}},u_{i}(x))\leq\lambda_{\star}^{-}(F_{i^{\star}},m(F_{i}))\leq\frac{1}{m(F_{i})}\>.$

Using that $\lambda_{\star}^{+}(F_{i},u)\geq\frac{u-m(F_{i})}{u(B-u)}$ (Lemma
12 in [18]) and denoting $y(x)=u_{i}(x)-m(F_{i})=_{+\infty}o(1)$, we obtain

$\frac{1}{m(F_{i})}\geq
x\lambda_{\star}^{+}(F_{i},u_{i}(x))\geq\frac{xy(x)}{(m(F_{i})+y(x))(B-m(F_{i})-y(x))}\>.$

Suppose towards contradiction that $y(x)=\mathcal{O}(\frac{1}{x})$ doesn’t
hold, i.e. $\lim_{+\infty}xy(x)=+\infty$. Using that $y(x)=_{+\infty}o(1)$ and
taking the limit in the above inequality yields

$\frac{1}{m(F_{i})}\geq\frac{\lim_{+\infty}xy(x)}{m(F_{i})(B-m(F_{i}))}=+\infty\>,$

which is a direct contradiction. Therefore, we have shown that
$y(x)=\mathcal{O}(\frac{1}{x})$. We showed above that a sufficient condition
to conclude was $y(x)=_{+\infty}o\left(\frac{1}{\sqrt{x}}\right)$. Therefore,
we have obtained that
$\lim_{+\infty}x\mathcal{K}_{\inf}^{-}(F_{i},u_{i}(x))=0$, which concludes the
proof. ∎

##  Appendix G Boundary crossing probability bounds

In order to analyze the algorithms presented in this paper, we need to
quantify probabilities of the form $\mathbb{P}(\theta_{1}\geq\theta_{2})$ for
$\theta_{1}$ and $\theta_{2}$ two independent real random variables. We first
show how such bounds can be obtained by quantifying the individual deviations
$\mathbb{P}(\theta_{i}\geq u)$ and $\mathbb{P}(\theta_{i}\leq u)$ for all
$u\in\mathbb{R}$ (the so-called Boundary Crossing Probabilities). Then we
prove upper and lower bounds on those probabilities when $\theta_{1}$ and
$\theta_{2}$ are obtained from a Dirichlet sampler.

###  G.1 From one arm to two

As remarked in Appendix D.2.1, studying BAI randomized algorithms require to
control probability of the form $\mathbb{P}(\theta_{1}\geq\theta_{2})$ where
$\theta_{1}$ and $\theta_{2}$ are two independent real random variables.
Thanks to Lemma 64, it is possible to obtain those by using Boundary Crossing
Probability (BCP) bounds, which are extensively studied in the regret
minimization literature. Therefore, while it is based on simple calculations,
Lemma 64 is a powerful result of independent interest.

######  Lemma 64.

Let $\theta_{1}$ and $\theta_{2}$ be two independent real random variables
with cdf $F_{1}$ and $F_{2}$. Let
$x\in\operatorname*{arg\,max}_{u\in\mathbb{R}}\mathbb{P}(\theta_{2}\geq
u)\mathbb{P}(\theta_{1}\leq u)$. Then

$\displaystyle\mathbb{P}(\theta_{2}\geq x)\mathbb{P}(\theta_{1}\leq
x)\leq\mathbb{P}(\theta_{2}\geq\theta_{1})$ $\displaystyle\leq
g\big{(}\mathbb{P}(\theta_{2}\geq x)\mathbb{P}(\theta_{1}\leq x)\big{)}\>.$

where $g(u)=u(1-\log(u))$ for all $u\in[0,1]$.

###### Proof.

To ease the notation, we introduce the cdfs
$F_{1}(u)=\mathbb{P}(\theta_{1}\leq u)$ and
$F_{2}(u)=\mathbb{P}(\theta_{2}\leq u)$. We can suppose that there exists
$u\in\mathbb{R}$ with $(1-F_{2}(u))F_{1}(u)>0$. Otherwise the probability of
$\theta_{2}\geq\theta_{1}$ is 0, and both bounds are 0 as well. We start by
proving the upper bound.

$\displaystyle\mathbb{P}(\theta_{2}\geq\theta_{1})$
$\displaystyle=\int_{u}\int_{v}\mathds{1}\\{u\geq v\\}dF_{1}(v)dF_{2}(u)$
$\displaystyle=\int_{u\leq x}\int_{v\leq x}\mathds{1}\\{u\geq
v\\}dF_{1}(v)dF_{2}(u)+\int_{u\leq x}\int_{v>x}\mathds{1}\\{u\geq
v\\}dF_{1}(v)dF_{2}(u)$ $\displaystyle\quad+\int_{u>x}\int_{v\leq
x}\mathds{1}\\{u\geq
v\\}dF_{1}(v)dF_{2}(u)+\int_{u>x}\int_{v>x}\mathds{1}\\{u\geq
v\\}dF_{1}(v)dF_{2}(u)$

The second of those four integrals is equal to zero. We now bound integrals 1,
3, and 4.

_1._ For $x$ such that $F_{2}(x)<1$,

$\displaystyle\int_{u\leq x}\int_{v\leq x}\mathds{1}\\{u\geq
v\\}dF_{1}(v)dF_{2}(u)$ $\displaystyle=\int_{u\leq x}F_{1}(u)dF_{2}(u)$
$\displaystyle=\int_{u\leq
x}\frac{1}{1-F_{2}(u)}(1-F_{2}(u))F_{1}(u)dF_{2}(u)$
$\displaystyle\leq\left(\sup_{u\leq x}(1-F_{2}(u))F_{1}(u)\right)\int_{u\leq
x}\frac{1}{1-F_{2}(u)}dF_{2}(u)$ $\displaystyle=-\log(1-F_{2}(x))\sup_{u\leq
x}(1-F_{2}(u))F_{1}(u)\>.$

_3._

$\displaystyle\int_{u>x}\int_{v\leq x}\mathds{1}\\{u\geq
v\\}dF_{1}(v)dF_{2}(u)$ $\displaystyle=F_{1}(x)(1-F_{2}(x))\>.$

_4._ For $x$ such that $F_{1}(x)>0$,

$\displaystyle\int_{u>x}\int_{v>x}\mathds{1}\\{u\geq v\\}dF_{1}(v)dF_{2}(u)$
$\displaystyle=\int_{v>x}(1-F_{2}(v))dF_{1}(v)$
$\displaystyle=\int_{v>x}F_{1}(v)(1-F_{2}(v))\frac{1}{F_{1}(v)}dF_{1}(v)$
$\displaystyle\leq\left(\sup_{v>x}F_{1}(v)(1-F_{2}(v))\right)\int_{v>x}\frac{1}{F_{1}(v)}dF_{1}(v)$
$\displaystyle=-\log(F_{1}(x))\sup_{v>x}F_{1}(v)(1-F_{2}(v))\>.$

Putting things together:

$\displaystyle\mathbb{P}(\theta_{2}\geq\theta_{1})$
$\displaystyle\leq-\log(1-F_{2}(x))\sup_{u\leq
x}(1-F_{2}(u))F_{1}(u)+F_{1}(x)(1-F_{2}(x))$
$\displaystyle\quad-\log(F_{1}(x))\sup_{v>x}F_{1}(v)(1-F_{2}(v))\>.$

Taking for $x$ the argmax over $\mathbb{R}$ (which verifies $F_{1}(x)>0$ and
$F_{2}(x)<1$), we get

$\displaystyle\mathbb{P}(\theta_{2}\geq\theta_{1})$
$\displaystyle\leq(1-F_{2}(x))F_{1}(x)\left[1-\log((1-F_{2}(x))F_{1}(x))\right]$

We now prove the lower bound. For $x\in\mathbb{R}$, by independence of
$\theta_{1}$ and $\theta_{2}$,

$\displaystyle\mathbb{P}(\theta_{2}\geq\theta_{1})$
$\displaystyle\geq\mathbb{P}(\theta_{2}\geq
x\geq\theta_{1})=\mathbb{P}(\theta_{2}\geq x)\mathbb{P}(\theta_{1}\leq
x)=(1-F_{2}(x))F_{1}(x)\>.$

∎

###  G.2 Upper bounds

Theorem 5 gives a tight upper bound on the BCP.

######  Theorem 5.

Let $X=(X_{1},\ldots,X_{n})\in[0,B]^{n}$, let $\hat{F}_{n}$ be the
corresponding empirical distribution and let $\mu\in\mathbb{R}$. Then

$\displaystyle\mathbb{P}_{L\sim\mathrm{Dir}(1^{n})}(L^{\top}X\geq\mu)$
$\displaystyle\leq\exp\left(-n\mathcal{K}_{\inf}^{+}(\hat{F}_{n},\mu)\right)\>,$
$\displaystyle\mathbb{P}_{L\sim\mathrm{Dir}(1^{n})}(L^{\top}X\leq\mu)$
$\displaystyle\leq\exp\left(-n\mathcal{K}_{\inf}^{-}(\hat{F}_{n},\mu)\right)\>.$

###### Proof.

We first prove the bound involving $\mathcal{K}_{\inf}^{+}$. This proof is
extracted from the proof of Lemma 15 of [36].

Let $R_{1},\ldots,R_{n}$ be independent exponential random variables with
parameter 1.

$\displaystyle\mathbb{P}_{L\sim\mathrm{Dir}(1^{n})}(L^{\top}X\geq\mu)$
$\displaystyle=\mathbb{P}(\sum_{i=1}^{n}\frac{R_{i}}{\sum_{j}R_{j}}X_{i}\geq\mu)=\mathbb{P}(\sum_{i=1}^{n}R_{i}(X_{i}-\mu)\geq
0)\>.$

For $t\geq 0$, we can compose with exponentials and use Markov’s inequality to
obtain

$\displaystyle\mathbb{P}_{L\sim\mathrm{Dir}(1^{n})}(L^{\top}X\geq\mu)$
$\displaystyle=\mathbb{P}(\exp t\sum_{i=1}^{n}R_{i}(X_{i}-\mu)\geq
1)\leq\mathbb{E}e^{t\sum_{i=1}^{n}R_{i}(X_{i}-\mu)}\>.$

By independence, this last expression is equal to
$\prod_{i=1}^{n}\mathbb{E}e^{t(X_{i}-\mu)R_{i}}$ . By a simple computation
(See [36]) we get, for $t\in[0,\frac{1}{X_{i}-\mu})$ if $X_{i}\geq\mu$ and for
$t\geq 0$ otherwise,

$\displaystyle\mathbb{E}e^{t(X_{i}-\mu)R_{i}}=\frac{1}{1-t(X_{i}-\mu)}\>.$

We have proved that for all $t\in[0,\frac{1}{B-\mu})$,

$\displaystyle\mathbb{P}_{L\sim\mathrm{Dir}(1^{n})}(L^{\top}X\geq\mu)$
$\displaystyle\leq\exp\left(-n\frac{1}{n}\sum_{i=1}^{n}\log(1-t(X_{i}-\mu))\right)\>.$

This is then also true for $t$ minimizing the right-hand side.

It remains to show that
$\sup_{t\in[0,\frac{1}{B-\mu})}\frac{1}{n}\sum_{i=1}^{n}\log(1-t(X_{i}-\mu))=\mathcal{K}_{\inf}^{+}(\hat{F}_{n},\mu)$
.

From [18], Theorem 8, for any distribution $F$ with support in $[0,B]$,

$\displaystyle\mathcal{K}_{\inf}^{+}(F,\mu)$
$\displaystyle=\sup_{t\in[0,\frac{1}{B-\mu}]}\mathbb{E}_{X\sim
F}[\log(1-t(X-\mu))]\>.$

Applying this to $\hat{F}_{n}$ gives
$\mathcal{K}_{\inf}^{+}(\hat{F}_{n},\mu)=\sup_{t\in[0,\frac{1}{B-\mu}]}\frac{1}{n}\sum_{i=1}^{n}\log(1-t(X_{i}-\mu))$.
The only difference with our target is that the supremum is over the closed
interval and not the right-open interval, but either the sup is the same by
continuity if there is no $X_{i}$ equal to $B$, or the value at $1/(B-\mu)$ is
$-\infty$ and hence not equal to the sup.

We now prove the bound involving $\mathcal{K}_{\inf}^{-}$. Let
$\hat{F}_{n}^{B-X}$ be the empirical distribution corresponding to
$(B-X_{1},\ldots,B-X_{n})$.

$\displaystyle\mathbb{P}_{L\sim\mathrm{Dir}(1^{n})}(L^{\top}X\leq\mu)$
$\displaystyle=\mathbb{P}_{L\sim\mathrm{Dir}(1^{n})}(L^{\top}(B-X)\geq B-\mu)$
$\displaystyle\leq\exp\left(-n\mathcal{K}_{\inf}^{+}(\hat{F}_{n}^{B-X},B-\mu)\right)$
$\displaystyle=\exp\left(-n\mathcal{K}_{\inf}^{-}(\hat{F}_{n},\mu)\right)\>.$

The last equality follows from Lemma 38. ∎

######  Corollary 2.

Let $X=(X_{1},\ldots,X_{n})\in[0,B]^{n}$, and let
$Y=(Y_{1},\ldots,Y_{m})\in[0,B]^{m}$. let $\hat{F}_{n,X}$ be empirical
distribution corresponding to $X$ (and define $\hat{F}_{m,Y}$ similarly). Then

$\displaystyle\mathbb{P}_{L_{X}\sim\mathrm{Dir}(1^{n}),L_{Y}\sim\mathrm{Dir}(1^{m})}(L_{X}^{\top}X\geq
L_{Y}^{\top}Y)$ $\displaystyle\leq
f\left(-\inf_{\mu\in[0,B]}\left(n\mathcal{K}_{\inf}^{+}(\hat{F}_{n,X},\mu)+m\mathcal{K}_{\inf}^{-}(\hat{F}_{m,Y},\mu)\right)\right)\>.$

where $f(x)=(1+x)e^{-x}$.

###### Proof.

Combine the two bounds of Theorem 5 using Lemma 64. ∎

###  G.3 Lower bounds

Lemma 65 gives a first, coarse lower bound on the BCP under a Dirichlet
sampler. This result crucially relies on the fact that $\\{0,B\\}$ have been
added to the support.

######  Lemma 65.

Let $X=(B,0,X_{1}\ldots,X_{n})\in[0,B]^{n+2}$ and $u\in(0,B)$. Then,

$\displaystyle\mathbb{P}_{L\sim\mathrm{Dir}(1^{n+2})}[L^{\top}X\geq u]$
$\displaystyle\geq\left(1-\frac{u}{B}\right)^{n+1}\quad\text{and}\quad\mathbb{P}_{L\sim\mathrm{Dir}(1^{n+2})}[L^{\top}X\leq
u]\geq\left(\frac{u}{B}\right)^{n+1}\>.$

###### Proof.

We consider $\tilde{X}=(B,0,0\ldots,0)\in[0,B]^{n+2}$, use that the marginals
of Dirichlet are Beta distributions and the Beta-Binomial trick (e.g. [2]) to
obtain

$\displaystyle\mathbb{P}_{L\sim\mathrm{Dir}(1^{n+2})}[L^{\top}X\geq
u]\geq\mathbb{P}_{L\sim\mathrm{Dir}(1^{n+2})}[L^{\top}\tilde{X}\geq u]$
$\displaystyle=\mathbb{P}_{w\sim\mathrm{Beta}(1,n+1)}\left[w\geq\frac{u}{B}\right]$
$\displaystyle=\mathbb{P}_{k\sim\mathrm{Bin}\left(n+1,\frac{u}{B}\right)}[k\leq
0]$ $\displaystyle=\left(1-\frac{u}{B}\right)^{n+1}\>.$

Similarly, considering $\tilde{X}=(B,0,B\ldots,B)\in[0,B]^{n+2}$, we obtain

$\displaystyle\mathbb{P}_{L\sim\mathrm{Dir}(1^{n+2})}[L^{\top}X\leq
u]\geq\mathbb{P}_{L\sim\mathrm{Dir}(1^{n+2})}[L^{\top}\tilde{X}\leq u]$
$\displaystyle=\mathbb{P}_{w\sim\mathrm{Beta}(1,n+1)}\left[w\geq
1-\frac{u}{B}\right]$
$\displaystyle=\mathbb{P}_{k\sim\mathrm{Bin}\left(n+1,1-\frac{u}{B}\right)}[k\leq
0]$ $\displaystyle=\left(\frac{u}{B}\right)^{n+1}\>.$

∎

In the rest of this section, we derive a tighter lower bound on the BCP which
leads to a tight lower bound on the probability that one Dirichlet sample
exceeds another (Theorem 8). These result rely on a discretization argument
and on deriving lower bounds for multinomial distributions.

####  G.3.1 Multinomial distributions

Theorem 6 gives a tight lower bound on the BCP for multinomial distributions.

######  Theorem 6.

Let $X_{1},\ldots,X_{M}\in[0,B]$ with $X_{M}=B$ and let
$\beta\in\mathbb{N}^{M}$ with $\beta_{i}>0$ for all $i$. Define
$n=\sum_{i=1}^{M}\beta_{i}$. For all $\mu\in[0,B]$ and $q\in\triangle_{M}$
such that $q^{\top}X\geq\mu$,

$\displaystyle\mathbb{P}_{L\sim
Dir(\beta)}(L^{\top}X\geq\mu)\geq\frac{M^{M/2}}{2(8\pi)^{\frac{M-1}{2}}}\frac{1}{n^{\frac{M+1}{2}}}\exp\left(-n\mathrm{KL}_{\mathcal{M}}\left(\frac{\beta}{n},q\right)\right)\>.$

where $\mathrm{KL}_{\mathcal{M}}(p,q)$ is the Kullback-Leibler divergence
between multinomial distributions with probability vectors $p$ and $q$.

###### Proof.

The proof is strongly inspired by the works of [18] and [7] who use lower
bound on the BCP for analyzing regret minimization algorithms.

Let $\mathcal{S}_{q}=\\{p\in\triangle_{M}\mid\forall i\in[M-1],p_{i}\leq
q_{i}\\}$. For $p\in\mathcal{S}_{q}$, we necessarily have $p_{M}\geq q_{M}$
and $p^{\top}X\geq q^{\top}X\geq\mu$. From that inequality we get

$\displaystyle\mathbb{P}_{L\sim\mathrm{Dir}(\beta)}(L^{\top}X\geq\mu)\geq\mathbb{P}_{L\sim\mathrm{Dir}(\beta)}(L\in\mathcal{S}_{q})\>.$

We now quantify that probability, using the pdf of a Dirichlet distribution,

$\displaystyle\mathbb{P}_{L\sim\mathrm{Dir}(\beta)}(L\in\mathcal{S}_{q})$
$\displaystyle=\frac{\Gamma(n)}{\prod_{i=1}^{M}\Gamma(\beta_{i})}\int_{x\in\mathcal{S}_{q}}\prod_{i=1}^{M}x_{i}^{\beta_{i}-1}dx$
$\displaystyle\geq\frac{\Gamma(n)}{\prod_{i=1}^{M}\Gamma(\beta_{i})}q_{M}^{\beta_{M}-1}\prod_{j=1}^{M-1}\int_{x_{j}=0}^{q_{j}}x_{j}^{\beta_{j}-1}dx_{j}$
$\displaystyle=\frac{\Gamma(n)}{\prod_{i=1}^{M}\Gamma(\beta_{i})}q_{M}^{\beta_{M}-1}\prod_{j=1}^{M-1}\frac{q_{j}^{\beta_{j}}}{\beta_{j}}$
$\displaystyle=\frac{\Gamma(n)}{\prod_{i=1}^{M}\Gamma(\beta_{i})}\frac{\beta_{M}}{q_{M}}\prod_{j=1}^{M}\frac{q_{j}^{\beta_{j}}}{\beta_{j}}$
$\displaystyle\geq\frac{\Gamma(n)}{\prod_{i=1}^{M}\Gamma(\beta_{i})}\prod_{j=1}^{M}\frac{q_{j}^{\beta_{j}}}{\beta_{j}}\>.$

The last line uses that since $\beta_{M}\geq 1$ and $q_{M}\leq 1$,
$\beta_{M}/q_{M}\geq 1$. We transform that last expression to exhibit the
Kullback-Leibler divergence between multinomial distributions.

$\displaystyle\mathbb{P}_{L\sim\mathrm{Dir}(\beta)}(L\in\mathcal{S}_{q})$
$\displaystyle\geq\frac{\Gamma(n)}{\prod_{i=1}^{M}\Gamma(\beta_{i})}\prod_{j=1}^{M}\frac{q_{j}^{\beta_{j}}}{\beta_{j}}$
$\displaystyle=\frac{1}{n^{M}}\frac{\Gamma(n)}{\prod_{i=1}^{M}\Gamma(\beta_{i})}\prod_{j=1}^{M}\left(\frac{q_{j}}{\beta_{j}/n}\right)^{\beta_{j}}\prod_{j=1}^{M}\left(\frac{\beta_{j}}{n}\right)^{\beta_{j}-1}$
$\displaystyle=\frac{1}{n^{M}}\frac{\Gamma(n)}{\prod_{i=1}^{M}\Gamma(\beta_{i})}\prod_{j=1}^{M}\left(\frac{\beta_{j}}{n}\right)^{\beta_{j}-1}\exp\left(-n\mathrm{KL}(\frac{\beta}{n},q)\right)\>.$

We now simplify the factor in front of the exponential.

$\displaystyle\frac{1}{n^{M}}\frac{\Gamma(n)}{\prod_{i=1}^{M}\Gamma(\beta_{i})}\prod_{j=1}^{M}\left(\frac{\beta_{j}}{n}\right)^{\beta_{j}-1}=\frac{1}{n}\frac{n!}{\prod_{i=1}^{M}\beta_{i}!}\prod_{j=1}^{M}\left(\frac{\beta_{j}}{n}\right)^{\beta_{j}}$
$\displaystyle=\frac{1}{n}\frac{n!}{n^{n}}\prod_{j=1}^{M}\frac{\beta_{j}^{\beta_{j}}}{\beta_{j}!}\>.$

We use the following bound on the Stirling approximation of the factorial:
$\frac{n!}{\sqrt{2\pi n}(n/e)^{n}}\in[1,2]$ for all $n\geq 1$. A tighter
approximation is possible, but this one is sufficient for our purpose.

$\displaystyle\frac{1}{n}\frac{n!}{n^{n}}\prod_{j=1}^{M}\frac{\beta_{j}^{\beta_{j}}}{\beta_{j}!}\geq\frac{1}{n}\sqrt{2\pi
n}e^{n}\prod_{j=1}^{M}\frac{1}{2\sqrt{2\pi\beta_{j}}e^{\beta_{j}}}$
$\displaystyle=\frac{1}{n}\sqrt{2\pi
n}\prod_{j=1}^{M}\frac{1}{2\sqrt{2\pi\beta_{j}}}$
$\displaystyle\geq\frac{1}{n}\sqrt{2\pi n}\prod_{j=1}^{M}\frac{1}{2\sqrt{2\pi
n/M}}$
$\displaystyle=\frac{M^{M/2}}{2(8\pi)^{\frac{M-1}{2}}}\frac{1}{n^{\frac{M+1}{2}}}\>.$

∎

Lemma 66 links $\mathrm{KL}_{\mathcal{M}}$ with $\mathcal{K}_{\inf}^{\pm}$.

######  Lemma 66.

Let $F$ be a multinomial distribution supported on points
$X_{1},\ldots,X_{M}\in[0,B]$ and let $p\in\triangle_{M}$ be the corresponding
probability vector.

If there exists $i\in[M]$ with $X_{i}=B$ and $p_{i}>0$, then for all
$\mu\in[0,B]$,

$\displaystyle\mathcal{K}_{\inf}^{+}(F,\mu)=\inf_{q\in\triangle_{M}:q^{\top}X\geq\mu}\mathrm{KL}_{\mathcal{M}}(p,q)\>.$

If there exists $i\in[M]$ with $X_{i}=0$ and $p_{i}>0$, then for all
$\mu\in[0,B]$,

$\displaystyle\mathcal{K}_{\inf}^{-}(F,\mu)=\inf_{q\in\triangle_{M}:q^{\top}X\leq\mu}\mathrm{KL}_{\mathcal{M}}(p,q)\>.$

###### Proof.

As remarked in [18], the probability measure that realizes the infimum (which
exists by Lemma 41) in the $\mathcal{K}_{\inf}^{+}$ problem for distributions
with finite support has mass on the same points and on $B$. Under the
hypothesis that there exists $i\in[M]$ with $X_{i}=B$ and $p_{i}>0$, we get
that that infimum is also a multinomial with same support. Hence there exists
$q_{F}$ such that
$\mathcal{K}_{\inf}^{+}(F,\mu)=\mathrm{KL}_{\mathcal{M}}(p,q_{F})$ and we get
$\inf_{q\in\triangle_{M}:q^{\top}X\geq\mu}\mathrm{KL}_{\mathcal{M}}(p,q)\leq\mathcal{K}_{\inf}^{+}(F,\mu)$.
The reverse inequality comes from the definition of $\mathcal{K}_{\inf}^{+}$
as an infimum over all probability distributions (which is a larger set than
the multinomial distributions).

The proof for $\mathcal{K}_{\inf}^{-}$ is similar. ∎

######  Theorem 7.

Let $X_{1},\ldots,X_{M}\in[0,B]$ with $X_{M}=B$ and let
$\beta\in\mathbb{N}^{M}$ with $\beta_{M}>0$. Define
$n=\sum_{i=1}^{M}\beta_{i}$. Let $F_{n}$ be the multinomial distributions over
the $X_{i}$ with weights $\beta/n$. For all $\mu\in[0,B]$,

$\displaystyle\mathbb{P}_{L\sim\mathrm{Dir}(\beta)}(L^{\top}X\geq\mu)\geq\frac{M^{M/2}}{2(8\pi)^{\frac{M-1}{2}}}\frac{1}{n^{\frac{M+1}{2}}}\exp\left(-n\mathcal{K}_{\inf}^{+}(F_{n},\mu)\right)\>.$

###### Proof.

If $\beta_{i}>0$ for all $i\in[M]$, this is the result of a supremum over the
lower bounds of Theorem 6, to which we apply the equality of Lemma 66. Now if
there are some $i$ for which $\beta_{i}=0$, we have for some $M_{0}<M$,

$\displaystyle\mathbb{P}_{L\sim\mathrm{Dir}(\beta)}(L^{\top}X\geq\mu)\geq\frac{M_{0}^{M_{0}/2}}{2(8\pi)^{\frac{M_{0}-1}{2}}}\frac{1}{n^{\frac{M_{0}+1}{2}}}\exp\left(-n\mathcal{K}_{\inf}^{+}(F_{n},\mu)\right)\>.$

But since the leading factor is non-increasing in $M_{0}$, we recover the
result with $M$ instead of $M_{0}$. ∎

######  Corollary 3.

Let $X_{1},\ldots,X_{M}\in[0,B]$ with $X_{M}=0$ and let
$\beta\in\mathbb{N}^{M}$ with $\beta_{M}>0$. Define
$n=\sum_{i=1}^{M}\beta_{i}$. Let $F_{n}$ be the multinomial distributions over
the $X_{i}$ with weights $\beta/n$. For all $\mu\in[0,B]$,

$\displaystyle\mathbb{P}_{L\sim\mathrm{Dir}(\beta)}(L^{\top}X\leq\mu)\geq\frac{M^{M/2}}{2(8\pi)^{\frac{M-1}{2}}}\frac{1}{n^{\frac{M+1}{2}}}\exp\left(-n\mathcal{K}_{\inf}^{-}(F_{n},\mu)\right)\>.$

###### Proof.

Remark that
$\mathbb{P}_{L\sim\mathrm{Dir}(\beta)}(L^{\top}X\leq\mu)=\mathbb{P}_{L\sim\mathrm{Dir}(\beta)}(L^{\top}(B-X)\geq
B-\mu)$ and apply Theorem 7 and Lemma 38. ∎

####  G.3.2 Lower bound for bounded distributions

######  Lemma 67.

Let $X_{1},\ldots,X_{n}\in[0,B]$. Let $\theta=L^{\top}X$, where $L$ is a
Dirichlet random variables, with $L\sim\mathrm{Dir}(1,\ldots,1)$ ($n$ ones).
Let $Y_{1},\ldots,Y_{M}\in[0,B]$, among which are the values 0 and $B$. For
all $i$, let $X_{i}^{+}=\min\\{Y_{k}\mid k\in[M],Y_{k}\geq X_{i}\\}$. Let
$F_{n}^{+}$ be the empirical distribution corresponding to points $X_{i}^{+}$.

If $0\in\\{X_{1},\ldots,X_{n}\\}$, then for all $\mu\in[0,B]$,

$\displaystyle\mathbb{P}(\theta\leq\mu)$
$\displaystyle\geq\frac{M^{M/2}}{2(8\pi)^{\frac{M-1}{2}}}\frac{1}{n^{\frac{M+1}{2}}}\exp\left(-n\mathcal{K}_{\inf}^{-}(F_{n}^{+},\mu)\right)\>.$

If $B\in\\{X_{1},\ldots,X_{n}\\}$, then for all $\mu\in[0,B]$,

$\displaystyle\mathbb{P}(\theta\geq\mu)$
$\displaystyle\geq\frac{M^{M/2}}{2(8\pi)^{\frac{M-1}{2}}}\frac{1}{n^{\frac{M+1}{2}}}\exp\left(-n\mathcal{K}_{\inf}^{+}(F_{n}^{-},\mu)\right)\>.$

###### Proof.

We have $\theta=L^{\top}X\leq L^{\top}X^{+}$ and $\theta=L^{\top}X\geq
L^{\top}X^{-}$. Those scalar products can be written as scalar products of
Dirichlet random variables with $Y$. We now apply Theorem 7 and its corollary.
∎

For a probability distribution with cdf $F$ on $[0,B]$ and points
$0=x_{0}<x_{1}<\ldots<x_{M}<x_{M+1}=B$ we define two discretized distributions
with cdf given by, for $x\in[x_{m},x_{m+1})$,

$\displaystyle F^{-}(x)$ $\displaystyle=\lim_{y\to x_{m+1},y\leq
x_{m+1}}F(y)\>,$ $\displaystyle F^{+}(x)$ $\displaystyle=F(x_{m})\>.$

######  Lemma 68.

For all $\varepsilon>0$ and all probability distributions $F$ supported on
$[0,B]$, there exists a discretization over at most $2+\lfloor
1/\varepsilon\rfloor$ points (counting points $0$ and $B$) such that
$\|F^{-}-F\|_{\infty}\leq\varepsilon$ and
$\|F^{+}-F\|_{\infty}\leq\varepsilon$.

###### Proof.

Let $M=\lfloor 1/\varepsilon\rfloor$. For $m\in\\{0,\ldots,M\\}$, let
$x_{m}=\inf\\{x\in[0,B]\mid F(x)\geq m\varepsilon\\}$. Let $x_{M+1}=B$.

$\displaystyle\|F^{-}-F\|_{\infty}$ $\displaystyle\leq\max_{0\leq m\leq
M}|\lim_{y\to x_{m+1},y\leq x_{m+1}}F(y)-F(x_{m})|\mathds{1}\\{x_{m+1}\neq
x_{m}\\}$ $\displaystyle\leq\max_{0\leq m\leq
M}|(m+1)\varepsilon-m\varepsilon|\leq\varepsilon\>.$

The computation for $F^{+}$ is similar. ∎

######  Lemma 69.

For all $F,G\in\mathcal{P}(\mathbb{R})$ with support in $[0,B]$ and all finite
discretizations,

$\displaystyle\|F^{-}-G^{-}\|_{\infty}\leq\|F-G\|_{\infty}\>,$
$\displaystyle\|F^{+}-G^{+}\|_{\infty}\leq\|F-G\|_{\infty}\>.$

###### Proof.

For all $x\in[x_{m},x_{m+1})$, $F^{-}(x)=\lim_{y\to x_{m+1},y\leq
x_{m+1}}F(y)$.

$\displaystyle\|F^{-}-G^{-}\|_{\infty}$ $\displaystyle\leq\max_{0\leq m\leq
M}|\lim_{y\to x_{m+1},y\leq x_{m+1}}F(y)-\lim_{y\to x_{m+1},y\leq
x_{m+1}}G(y)|\leq\|F-G\|_{\infty}\>.$

∎

######  Lemma 70.

Let $F\in\mathcal{P}(\mathbb{R})$ with support in $[0,B]$. For all
$\varepsilon>0$, there exists a discretization of $[0,B]$ into $2+\lfloor
2/\varepsilon\rfloor$ points such that for all $G$ with
$\|G-F\|\leq\varepsilon/2$, we have $\|G^{-}-F\|_{\infty}\leq\varepsilon$ and
$\|G^{+}-F\|_{\infty}\leq\varepsilon$.

###### Proof.

Let $\varepsilon>0$. For a discretization of $F$ verifying the result of Lemma
68 for $\varepsilon/2$,

$\displaystyle\|G^{-}-F\|_{\infty}\leq\|G^{-}-F^{-}\|_{\infty}+\|F^{-}-F\|_{\infty}\leq\|G-F\|_{\infty}+\|F^{-}-F\|_{\infty}\leq\varepsilon\>.$

Same computation for $G^{+}$. ∎

Lemma 71 gives a tight lower bound on the BCP for bounded distributions.

######  Lemma 71.

Let $a>0$ and $b<B$. Let $F$ be a probability distribution with support in
$[0,B]$.

For points $X,\ldots,X_{n}\in[0,B]$. let $\theta=L^{\top}X$, where $L$ is a
Dirichlet random variable, with $L\sim\mathrm{Dir}(1,\ldots,1)$ ($n$ ones).
Let $F_{n}$ be the empirical distribution corresponding to points
$(X_{i})_{i\in[n]}$.

For all $\varepsilon>0$, there exists $\eta>0$ such that for all such
empirical distributions (and in particular for all $n$), if
$\|F_{n}-F\|_{\infty}\leq\eta$ then for all $u\in[a,b]$,

$\displaystyle\text{if }B\in\\{X_{1},\ldots,X_{n}\\}\text{ then
}\mathbb{P}(\theta\geq u)$
$\displaystyle\geq\frac{M^{M/2}}{2(8\pi)^{\frac{M-1}{2}}}\frac{1}{n^{\frac{M+1}{2}}}\exp\left(-n\mathcal{K}_{\inf}^{+}(F,\mu)-n\varepsilon\right)\>,$
$\displaystyle\text{if }0\in\\{X_{1},\ldots,X_{n}\\}\text{ then
}\mathbb{P}(\theta\leq u)$
$\displaystyle\geq\frac{M^{M/2}}{2(8\pi)^{\frac{M-1}{2}}}\frac{1}{n^{\frac{M+1}{2}}}\exp\left(-n\mathcal{K}_{\inf}^{-}(F,\mu)-n\varepsilon\right)\>.$

with $M=2+\lfloor 2/\eta\rfloor$.

###### Proof.

The function $(F,\mu)\mapsto\mathcal{K}_{\inf}^{-}(F,\mu)$ is continuous on
$\mathcal{D}\times(0,B)$ by Theorem 4. The function