$\\{X_{t}\\}_{t\in\mathbb{N}_{0}}$ and a scalar $x\in\mathbb{R}$, we say
$X_{t}\xrightarrow{\mathbb{M}}x$ if

$\text{for all }\epsilon>0\,\text{there exists }\,T\in\mathbb{M}\,\text{ such
that for all }t\geq T,\,\,|X_{t}-x|\leq\epsilon.$

We say $X_{t}\xrightarrow{\mathbb{M}}\infty$ if

$\text{for all }c>0\,\text{there exists }\,T\in\mathbb{M}\,\text{ such that
for all }t\geq T,\,\,X_{t}\geq c,$

and similarly, we say $X_{t}\xrightarrow{\mathbb{M}}-\infty$ if
$-X_{t}\xrightarrow{\mathbb{M}}\infty$.
For a sequence of random vectors $\\{\bm{X}_{t}\\}_{t\in\mathbb{N}_{0}}$
taking values in $\mathbb{R}^{d}$ and a vector $\bm{x}\in\mathbb{R}^{d}$ where
$\bm{X}_{t}\triangleq(X_{t,1},\ldots,X_{t,d})$ and
$\bm{x}=(x_{1},\ldots,x_{d})$, we say
$\bm{X}_{t}\xrightarrow{\mathbb{M}}\bm{x}$ if
$X_{t,i}\xrightarrow{\mathbb{M}}x_{i}$ for all $i\in[d]$.

Qin and Russo (2022) also introduces a number of properties of the class
$\mathbb{M}$ (Definition 2) and strong convergence (Definition 3).

######  Lemma 2 (Lemma 1 in Qin and Russo (2022): Closedness of $\mathbb{M}$).

Let $X$ and $Y$ be non-negative random variables in $\mathbb{M}$.

  1. 1.

$aX+bY\in\mathbb{M}$ for any scalars $a,b\in\mathbb{R}$.

  2. 2.

$XY\in\mathbb{M}$.

  3. 3.

$\max\\{X,Y\\}\in\mathbb{M}$.

  4. 4.

$X^{q}\in\mathbb{M}$ for any $q\geq 0$.

  5. 5.

If $g:\mathbb{R}\to\mathbb{R}$ satisfies $\sup_{x\in-[c,c]}|g(x)|<\infty$ for
all $c\geq 0$ and $|g(x)|=O(|x|^{q})$ as $|x|\to\infty$ for some $q\geq 0$,
then $g(X)\in\mathbb{M}$.

  6. 6.

If $g:\mathbb{R}\to\mathbb{R}$ is continuous and $|g(x)|=O(|x|^{q})$ as
$|x|\to\infty$ for some $q\geq 0$, then $g(X)\in\mathbb{M}$.

As mentioned in Qin and Russo (2022), many of the above properties can be
extended to any finite collection of random variables in $\mathbb{M}$. A
notable one is that if $X_{i}\in\mathbb{M}$ for each $i\in[d]$ then

$X_{1}+\cdots+X_{d}\in\mathbb{M}\quad\text{and}\quad\max\\{X_{1},\ldots,X_{d}\\}\in\mathbb{M}.$

Qin and Russo (2022) also shows an equivalence between pointwise convergence
and convergence in the maximum norm and a continuous mapping theorem under
strong convergence (Definition 3).

######  Lemma 3 (Lemma 2 in Qin and Russo (2022)).

For a sequence of random vectors $\\{X_{n}\\}_{n\in\mathbb{N}}$ taking values
in $\mathbb{R}^{d}$ and a vector $x\in\mathbb{R}^{d}$, if
$X_{n}\xrightarrow{\mathbb{M}}x$, then
$\|X_{n}-x\|_{\infty}\xrightarrow{\mathbb{M}}0$. Equivalently, if
$X_{n,i}\xrightarrow{\mathbb{M}}x_{i}$ for all $i\in[d]$, then for all
$\epsilon>0$, there exists $N\in\mathbb{M}$ such that $n\geq N$ implies
$|X_{n,i}-x_{i}|\leq\epsilon$ for all $i\in[d]$.

######  Lemma 4 (Lemma 3 in Qin and Russo (2022): Continuous Mapping).

For any $x$ taking values in a normed vector space and any random sequence
$\\{X_{n}\\}_{n\in\mathbb{N}}$:

  1. 1.

If $g$ is continuous at $x$, then $X_{n}\xrightarrow{\mathbb{M}}x$ implies
$g(X_{n})\xrightarrow{\mathbb{M}}g(x)$.

  2. 2.

If the range of function $g$ belongs to $\mathbb{R}$ and $g(y)\to\infty$ as
$y\to\infty$, then $X_{n}\xrightarrow{\mathbb{M}}\infty$ implies
$g(X_{n})\xrightarrow{\mathbb{M}}\infty$.

#####  B.1.3 Maximal inequalities

Following Qin et al. (2017); Shang et al. (2020), we introduce the following
path-dependent random variable to control the impact of observation noises:

$W_{1}=\sup_{(t,i)\in\mathbb{N}_{0}\times[K]}\sqrt{\frac{N_{t,i}+1}{\log(N_{t,i}+e)}}\frac{|\theta_{t,i}-\theta_{i}|}{\sigma}.$
(34)

In addition, to control the impact of algorithmic randomness, we introduce the
other path-dependent random variable:

$W_{2}=\sup_{(t,i)\in\mathbb{N}_{0}\times[K]}\frac{|N_{t,i}-\Psi_{t,i}|}{\sqrt{(t+1)\log(t+e^{2})}}.$
(35)

The next lemma ensures that these maximal deviations have light tails.

######  Lemma 5 (Lemma 6 of Qin et al. (2017) and Lemma 4 of Shang et al.
(2020)).

For any $\lambda>0$,

$\mathbb{E}[e^{\lambda W_{1}}]<\infty\quad\text{and}\quad\mathbb{E}[e^{\lambda
W_{2}}]<\infty.$

The definition of $W_{2}$ in Equation (35) and Lemma 5 imply the following
corollary.

######  Corollary 2.

There exists $T\in\mathbb{M}$ such that for any $t\geq T$,

$|N_{t,i}-\Psi_{t,i}|\leq W_{2}t^{0.6},\quad\forall i\in[K].$

We remark that the exponent $0.6$ is not essential in the sense that it can be
any constant in $(0.5,1)$. This implies

$p_{t,i}-w_{t,i}\xrightarrow{\mathbb{M}}0,\quad\forall i\in[K].$

####  B.2 Proof outline

###### Stopping rule and $\delta$-correct guarantee.

When $k=1$, our Chernoff stopping rule specializes to the one used in Garivier
and Kaufmann (2016) for BAI. The $\delta$-correct guarantee is provided in
Garivier and Kaufmann (2016, Proposition 12).

######  Proposition 9 (Proposition 12 in Garivier and Kaufmann (2016)).

Consider the best-arm identification problem. Let $\delta\in(0,1)$ and
$\alpha>1$. There exists a constant $C=C(\alpha,K)$ given in the proof of
Garivier and Kaufmann (2016, Proposition 12) such that for any sampling rule,
using the Chernoff stopping rule (4) with threshold
$\gamma(t,\delta)=\log\left(Ct^{\alpha}/\delta\right)$ and the decision rule
$\widehat{\mathcal{I}}_{\tau_{\delta}}=\mathcal{I}(\bm{\theta}_{\tau_{\delta}})$
ensures that for any $\bm{\theta}\in\Theta$,
$\mathbb{P}_{\bm{\theta}}(\tau_{\delta}<\infty,\widehat{\mathcal{I}}_{\tau_{\delta}}\neq\mathcal{I}(\bm{\theta}))\leq\delta$.

###### Sufficient conditions for optimality in fixed-confidence setting.

Theorem 1 shows a sufficient condition of sampling rules that ensures the
optimality in fixed-confidence setting. It is easier to study the following
alternative but equivalent sufficient conditions to prove optimality of
sampling rules.

######  Proposition 10 (Alternative sufficient conditions).

The following conditions are equivalent:

  1. 1.

$\bm{p}_{t}\xrightarrow{\mathbb{M}}\bm{p}^{*}$;

  2. 2.

$\frac{p_{t,j}}{p_{t,I^{*}}}\xrightarrow{\mathbb{M}}\frac{p_{j}^{*}}{p_{I^{*}}^{*}}$
for any $j\neq I^{*}$;

  3. 3.

$\bm{w}_{t}\xrightarrow{\mathbb{M}}\bm{p}^{*}$; and

  4. 4.

$\frac{w_{t,j}}{w_{t,I^{*}}}\xrightarrow{\mathbb{M}}\frac{p_{j}^{*}}{p_{I^{*}}^{*}}$
for any $j\neq I^{*}$.

###### Proof.

By Corollary 2, conditions 1 and 3 are equivalent.

Now we are going to show conditions 1 and 2 are equivalent. By Lemma 2,
condition 1 implies condition 2. On the other hand, applying Lemma 2 to
condition 3 gives

$\frac{1-p_{t,I^{*}}}{p_{t,I^{*}}}=\sum_{j\neq
I^{*}}\frac{p_{t,j}}{p_{t,I^{*}}}\xrightarrow{\mathbb{M}}\sum_{j\neq
I^{*}}\frac{p^{*}_{j}}{p^{*}_{I^{*}}}=\frac{1-p^{*}_{I^{*}}}{p^{*}_{I^{*}}},$

Using Lemma 2 again yields $p_{t,I^{*}}\xrightarrow{\mathbb{M}}p^{*}_{I^{*}},$
and then condition 2 gives $p_{t,j}\xrightarrow{\mathbb{M}}p_{j}^{*}$ for any
$j\neq I^{*}$ Hence, condition 2 implies condition 1, and thus they are
equivalent. Similarly, conditions 2 and 4 are equivalent. This completes the
proof. ∎

To prove our Theorem 2, we are going to show that TTTS with IDS satisfies the
last sufficient condition in Proposition 10:

######  Proposition 11.

Under TTTS with IDS,

$\frac{w_{t,j}}{w_{t,I^{*}}}\xrightarrow{\mathbb{M}}\frac{p_{j}^{*}}{p_{I^{*}}^{*}},\quad\forall
j\neq I^{*}.$

The rest of this appendix is devoted to proving Proposition 11.

####  B.3 Empirical overall balance under TTTS with IDS

Previous papers (Qin et al., 2017; Shang et al., 2020; Jourdan et al., 2022)
establishes $\beta$-optimality by proving either
$w_{t,I^{*}}\xrightarrow{\mathbb{M}}\beta$ or
$p_{t,I^{*}}\xrightarrow{\mathbb{M}}\beta$ where $\beta$ is a fixed tuning
parameter taken as an input to the algorithms, while the optimal $\beta^{*}=$
(i.e., $p^{*}_{I^{*}}$) is unknown a priori. In our information-directed
selection rule, at each time step, $h_{t}$ is adaptive to the top-two
candidates, so novel proof techniques are required. In this subsection, we
first show that the “empirical” version of overall balance (10) holds.

######  Proposition 12.

Under TTTS with IDS,

$w_{t,I^{*}}^{2}-\sum_{j\neq
I^{*}}w_{t,j}^{2}\xrightarrow{\mathbb{M}}0\quad\text{and}\quad
p_{t,I^{*}}^{2}-\sum_{j\neq I^{*}}p_{t,j}^{2}\xrightarrow{\mathbb{M}}0.$

To prove this proposition, we need the following supporting result.

######  Lemma 6.

Under TTTS with IDS, for any $t\in\mathbb{N}_{0}$,

$\alpha_{t,I^{*}}\left(\sum_{\ell\neq
I^{*}}\frac{\alpha_{t,\ell}}{1-\alpha_{t,I^{*}}}\frac{p_{t,\ell}}{p_{t,I^{*}}+p_{t,\ell}}\right)\leq\psi_{t,I^{*}}\leq\alpha_{t,I^{*}}\left(\sum_{\ell\neq
I^{*}}\frac{\alpha_{t,\ell}}{1-\alpha_{t,I^{*}}}\frac{p_{t,\ell}}{p_{t,I^{*}}+p_{t,\ell}}\right)+(1-\alpha_{t,I^{*}}),$

and for any $j\neq I^{*}$,

$\alpha_{t,I^{*}}\frac{\alpha_{t,j}}{1-\alpha_{t,I^{*}}}\frac{p_{t,I^{*}}}{p_{t,I^{*}}+p_{t,j}}\leq\psi_{t,j}\leq\alpha_{t,I^{*}}\frac{\alpha_{t,j}}{1-\alpha_{t,I^{*}}}\frac{p_{t,I^{*}}}{p_{t,I^{*}}+p_{t,j}}+(1-\alpha_{t,I^{*}}).$

###### Proof.

Fix $t\in\mathbb{N}_{0}$. For a fixed $j\in[K]$ and any $\ell\neq j$, TTTS
obtains the top-two candidates

$\left(I_{t}^{(1)},I_{t}^{(2)}\right)=\begin{cases}(j,\ell),&\text{with
probability }\alpha_{t,j}\frac{\alpha_{t,\ell}}{1-\alpha_{t,j}},\\\
(\ell,j),&\text{with probability
}\alpha_{t,\ell}\frac{\alpha_{t,j}}{1-\alpha_{t,\ell}},\end{cases}$

and when TTTS is applied with IDS,

$\displaystyle\psi_{t,j}=\alpha_{t,j}\left(\sum_{\ell\neq
j}\frac{\alpha_{t,\ell}}{1-\alpha_{t,j}}\frac{p_{t,\ell}}{p_{t,j}+p_{t,\ell}}\right)+\sum_{\ell\neq
j}\alpha_{t,\ell}\frac{\alpha_{t,j}}{1-\alpha_{t,\ell}}\frac{p_{t,\ell}}{p_{t,j}+p_{t,\ell}}.$

For $j=I^{*}$, we have

$\displaystyle\psi_{t,I^{*}}$
$\displaystyle=\alpha_{t,I^{*}}\left(\sum_{\ell\neq
I^{*}}\frac{\alpha_{t,\ell}}{1-\alpha_{t,I^{*}}}\frac{p_{t,\ell}}{p_{t,I^{*}}+p_{t,\ell}}\right)+\sum_{\ell\neq
I^{*}}\alpha_{t,\ell}\frac{\alpha_{t,I^{*}}}{1-\alpha_{t,\ell}}\frac{p_{t,\ell}}{p_{t,I^{*}}+p_{t,\ell}},$

so

$\displaystyle\psi_{t,I^{*}}$
$\displaystyle\geq\alpha_{t,I^{*}}\left(\sum_{\ell\neq
I^{*}}\frac{\alpha_{t,\ell}}{1-\alpha_{t,I^{*}}}\frac{p_{t,\ell}}{p_{t,I^{*}}+p_{t,\ell}}\right)$

and

$\displaystyle\psi_{t,I^{*}}$
$\displaystyle\leq\alpha_{t,I^{*}}\left(\sum_{\ell\neq
I^{*}}\frac{\alpha_{t,\ell}}{1-\alpha_{t,I^{*}}}\frac{p_{t,\ell}}{p_{t,I^{*}}+p_{t,\ell}}\right)+\sum_{\ell\neq
I^{*}}\alpha_{t,\ell}$ $\displaystyle=\alpha_{t,I^{*}}\left(\sum_{\ell\neq
I^{*}}\frac{\alpha_{t,\ell}}{1-\alpha_{t,I^{*}}}\frac{p_{t,\ell}}{p_{t,I^{*}}+p_{t,\ell}}\right)+(1-\alpha_{t,I^{*}}),$

where the inequality uses that for any $\ell\neq I^{*}$,
$\frac{\alpha_{t,I^{*}}}{1-\alpha_{t,\ell}}\frac{p_{t,\ell}}{p_{t,I^{*}}+p_{t,\ell}}\leq\frac{\alpha_{t,I^{*}}}{1-\alpha_{t,\ell}}=\frac{\alpha_{t,I^{*}}}{\sum_{\ell^{\prime}\neq\ell}\alpha_{t,\ell^{\prime}}}\leq
1$.

For $j\neq I^{*}$, we have

$\displaystyle\psi_{t,j}$ $\displaystyle=\sum_{\ell\neq
j}\alpha_{t,\ell}\frac{\alpha_{t,j}}{1-\alpha_{t,\ell}}\frac{p_{t,\ell}}{p_{t,j}+p_{t,\ell}}+\alpha_{t,j}\left(\sum_{\ell\neq
j}\frac{\alpha_{t,\ell}}{1-\alpha_{t,j}}\frac{p_{t,\ell}}{p_{t,j}+p_{t,\ell}}\right)$
$\displaystyle=\alpha_{t,I^{*}}\frac{\alpha_{t,j}}{1-\alpha_{t,I^{*}}}\frac{p_{t,I^{*}}}{p_{t,j}+p_{t,I^{*}}}+\sum_{\ell\neq
j,I^{*}}\alpha_{t,\ell}\frac{\alpha_{t,j}}{1-\alpha_{t,\ell}}\frac{p_{t,\ell}}{p_{t,\ell}+p_{t,j}}+\alpha_{t,j}\left(\sum_{\ell\neq
j}\frac{\alpha_{t,\ell}}{1-\alpha_{t,j}}\frac{p_{t,\ell}}{p_{t,j}+p_{t,\ell}}\right),$

so

$\displaystyle\psi_{t,j}$
$\displaystyle\geq\alpha_{t,I^{*}}\frac{\alpha_{t,j}}{1-\alpha_{t,I^{*}}}\frac{p_{t,I^{*}}}{p_{t,j}+p_{t,I^{*}}}$

and

$\displaystyle\psi_{t,j}$
$\displaystyle\leq\alpha_{t,I^{*}}\frac{\alpha_{t,j}}{1-\alpha_{t,I^{*}}}\frac{p_{t,I^{*}}}{p_{t,j}+p_{t,I^{*}}}+\left(\sum_{\ell\neq
j,I^{*}}\alpha_{t,\ell}\right)+\alpha_{t,j}$
$\displaystyle=\alpha_{t,I^{*}}\frac{\alpha_{t,j}}{1-\alpha_{t,I^{*}}}\frac{p_{t,I^{*}}}{p_{t,j}+p_{t,I^{*}}}+(1-\alpha_{t,I^{*}}),$

where the inequality uses that

  1. 1.

for any $\ell\neq j,I^{*}$,
$\frac{\alpha_{t,j}}{1-\alpha_{t,\ell}}\frac{p_{t,\ell}}{p_{t,\ell}+p_{t,j}}\leq\frac{\alpha_{t,j}}{1-\alpha_{t,\ell}}=\frac{\alpha_{t,j}}{\sum_{\ell^{\prime}\neq\ell}\alpha_{t,\ell^{\prime}}}\leq
1$; and

  2. 2.

$\sum_{\ell\neq
j}\frac{\alpha_{t,\ell}}{1-\alpha_{t,j}}\frac{p_{t,\ell}}{p_{t,j}+p_{t,\ell}}\leq\sum_{\ell\neq
j}\frac{\alpha_{t,\ell}}{1-\alpha_{t,j}}=1$.

This completes the proof. ∎

Now we are ready to complete the proof of Proposition 12.

###### Proof of Proposition 12.

By Corollary 2, it suffices to only show

$w_{t,I^{*}}^{2}-\sum_{j\neq I^{*}}w_{t,j}^{2}\xrightarrow{\mathbb{M}}0.$

For any $t\in\mathbb{N}_{0}$, we let

$G_{t}\triangleq{\Psi_{t,I^{*}}^{2}}-\sum_{j\neq I^{*}}{\Psi_{t,j}^{2}},$

and we are going to show $\frac{G_{t}}{t^{2}}\xrightarrow{\mathbb{M}}0$.

We argue that it suffices to show that there exists $T\in\mathbb{M}$ such that
for any $t\geq T$,

$|G_{t+1}-G_{t}|\leq 2W_{2}t^{0.6}+2.$ (36)

The reason is that given (36), for any $t\geq T$

$\displaystyle|G_{t}|=\left|G_{T}+\sum_{\ell=T}^{t-1}(G_{\ell+1}-G_{\ell})\right|$
$\displaystyle\leq\left|G_{T}\right|+\sum_{\ell=T}^{t-1}|G_{\ell+1}-G_{\ell}|$
$\displaystyle\leq\left|G_{T}\right|+\sum_{\ell=T}^{t-1}\left(2W_{2}\ell^{0.6}+2\right)$
$\displaystyle\leq\left|G_{T}\right|+2(t-T)+2W_{2}\int_{T+1}^{t+1}x^{0.6}\mathrm{d}x$
$\displaystyle=\left|G_{T}\right|+2(t-T)+\frac{2W_{2}}{1.6}\left[(t+1)^{1.6}-(T+1)^{1.6}\right]$
$\displaystyle\leq
T^{2}+2(t-T)+\frac{2W_{2}}{1.6}\left[(t+1)^{1.6}-(T+1)^{1.6}\right],$

where in the last inequality, $\left|G_{T}\right|\leq T^{2}$ holds since
$G_{T}\geq-\sum_{j\neq I^{*}}\Psi_{T,j}^{2}\geq-\left(\sum_{j\neq
I^{*}}\Psi_{T,j}\right)^{2}\geq-T^{2},$ and $G_{T}\leq\Psi_{T,I^{*}}^{2}\leq
T^{2}.$ This gives $\frac{|G_{t}|}{t^{2}}\xrightarrow{\mathbb{M}}0.$

Now we are going to prove the sufficient condition (36). We can calculate

$\displaystyle G_{t+1}-G_{t}$
$\displaystyle=\left[\left(\Psi_{t,I^{*}}+\psi_{t,I^{*}}\right)^{2}-\Psi_{t,I^{*}}^{2}\right]-\sum_{j\neq
I^{*}}\left[\left(\Psi_{t,j}+\psi_{t,j}\right)^{2}-\Psi_{t,j}^{2}\right]$
$\displaystyle=2\left(\psi_{t,I^{*}}\Psi_{t,I^{*}}-\sum_{j\neq
I^{*}}\psi_{t,j}\Psi_{t,j}\right)+\left(\psi_{t,I^{*}}^{2}-\sum_{j\neq
I^{*}}\psi_{t,j}^{2}\right).$

Then by Lemma 6, we have

$\displaystyle G_{t+1}-G_{t}$ $\displaystyle\geq$ $\displaystyle
2\left[\alpha_{t,I^{*}}\sum_{j\neq
I^{*}}\frac{\alpha_{t,j}}{1-\alpha_{t,I^{*}}}\frac{p_{t,j}\Psi_{t,I^{*}}}{p_{t,I^{*}}+p_{t,j}}-\alpha_{t,I^{*}}\sum_{j\neq
I^{*}}\frac{\alpha_{t,j}}{1-\alpha_{t,I^{*}}}\frac{p_{t,I^{*}}\Psi_{t,j}}{p_{t,I^{*}}+p_{t,j}}-(1-\alpha_{t,I^{*}})\sum_{j\neq
I^{*}}\Psi_{t,j}\right]-1$ $\displaystyle\geq$ $\displaystyle
2\alpha_{t,I^{*}}\sum_{j\neq
I^{*}}\frac{\alpha_{t,j}}{1-\alpha_{t,I^{*}}}\frac{p_{t,j}\Psi_{t,I^{*}}-p_{t,I^{*}}\Psi_{t,j}}{p_{t,I^{*}}+p_{t,j}}-2(1-\alpha_{t,I^{*}})t-1,$

where the last inequality uses $\sum_{j\neq I^{*}}\Psi_{t,j}\leq t$, and

$\displaystyle G_{t+1}-G_{t}$ $\displaystyle\leq$ $\displaystyle
2\left[\alpha_{t,I^{*}}\sum_{j\neq
I^{*}}\frac{\alpha_{t,j}}{1-\alpha_{t,I^{*}}}\frac{p_{t,j}\Psi_{t,I^{*}}}{p_{t,I^{*}}+p_{t,j}}+(1-\alpha_{t,I^{*}})\Psi_{t,I^{*}}-\alpha_{t,I^{*}}\sum_{j\neq
I^{*}}\frac{\alpha_{t,j}}{1-\alpha_{t,I^{*}}}\frac{p_{t,I^{*}}\Psi_{t,j}}{p_{t,I^{*}}+p_{t,j}}\right]+1$
$\displaystyle\leq$ $\displaystyle 2\alpha_{t,I^{*}}\left(\sum_{j\neq
I^{*}}\frac{\alpha_{t,j}}{1-\alpha_{t,I^{*}}}\frac{p_{t,j}\Psi_{t,I^{*}}-p_{t,I^{*}}\Psi_{t,j}}{p_{t,I^{*}}+p_{t,j}}\right)+2(1-\alpha_{t,I^{*}})t+1,$

where the last inequality uses $\Psi_{t,I^{*}}\leq t$. Hence,

$\displaystyle|G_{t+1}-G_{t}|$ $\displaystyle\leq 2\alpha_{t,I^{*}}\sum_{j\neq
I^{*}}\frac{\alpha_{t,j}}{1-\alpha_{t,I^{*}}}\left|\frac{p_{t,j}\Psi_{t,I^{*}}-p_{t,I^{*}}\Psi_{t,j}}{p_{t,I^{*}}+p_{t,j}}\right|+2(1-\alpha_{t,I^{*}})t+1.$

By Lemma 10, there exists $T_{1}\in\mathbb{M}$ such that for any $t\geq
T_{1}$, $(1-\alpha_{t,I^{*}})t\leq 1/2$, and thus

$\displaystyle|G_{t+1}-G_{t}|$ $\displaystyle\leq 2\alpha_{t,I^{*}}\sum_{j\neq
I^{*}}\frac{\alpha_{t,j}}{1-\alpha_{t,I^{*}}}\max_{j\neq
I^{*}}\left|\frac{p_{t,j}\Psi_{t,I^{*}}-p_{t,I^{*}}\Psi_{t,j}}{p_{t,I^{*}}+p_{t,j}}\right|+2$
$\displaystyle\leq 2\max_{j\neq
I^{*}}\left|\frac{p_{t,j}\Psi_{t,I^{*}}-p_{t,I^{*}}\Psi_{t,j}}{p_{t,I^{*}}+p_{t,j}}\right|+2$
$\displaystyle=2\max_{j\neq
I^{*}}\left|\frac{N_{t,j}\Psi_{t,I^{*}}-N_{t,I^{*}}\Psi_{t,j}}{N_{t,I^{*}}+N_{t,j}}\right|+2,$

where the last inequality applies $\alpha_{t,I^{*}}\leq 1$ and $\sum_{j\neq
I^{*}}\frac{\alpha_{t,j}}{1-\alpha_{t,I^{*}}}=1$. By Corollary 2, there exists
$T_{2}\in\mathbb{M}$ such that for any $t\geq T_{2}$ and $i\in[K]$,
$|N_{t,i}-\Psi_{t,i}|\leq W_{2}t^{0.6}$, and thus for $j\neq I^{*}$

$\displaystyle\left|\frac{N_{t,j}\Psi_{t,I^{*}}-N_{t,I^{*}}\Psi_{t,j}}{N_{t,I^{*}}+N_{t,j}}\right|\leq\left|\frac{N_{t,j}\left(N_{t,I^{*}}+W_{2}t^{0.6}\right)-N_{t,I^{*}}\left(N_{t,j}-W_{2}t^{0.6}\right)}{N_{t,I^{*}}+N_{t,j}}\right|\leq
W_{2}t^{0.6}.$

Hence, for $t\geq T\triangleq\max\\{T_{1},T_{2}\\}$, $|G_{t+1}-G_{t}|\leq
2W_{2}t^{0.6}+2$. Note that $T\in\mathbb{M}$ by Lemma 2. This completes the
proof of the sufficient condition (36). ∎

#####  B.3.1 Implication of empirical overall balance

Here we present some results that are implied by empirical overall balance
(Proposition 12) and needed for proving the sufficient condition for
optimality in fixed-confidence setting (Proposition 11). The first one shows
that when $t$ is large enough, two measures of average effort are bounded away
from 0 and 1.

######  Lemma 7.

Let $b_{1}\triangleq\frac{1}{\sqrt{32(K-1)}}$ and
$b_{2}\triangleq\frac{3}{4}$. Under TTTS with IDS, there exists a random time
$T\in\mathbb{M}$ such that for any $t\geq T$,

$b_{1}\leq w_{t,I^{*}}\leq b_{2}\quad\text{and}\quad b_{1}\leq p_{t,I^{*}}\leq
b_{2}.$

Since $w_{t,I^{*}}$ and $p_{t,I^{*}}$ are bounded away from 0 when $t$ is
large enough, we obtain the following corollary by dividing the equations in
Proposition 12 by $w_{t,I^{*}}$ and $p_{t,I^{*}}$, respectively,

######  Corollary 3.

Under TTTS with IDS,

$\sum_{j\neq
I^{*}}\frac{w_{t,j}^{2}}{w_{t,I^{*}}^{2}}\xrightarrow{\mathbb{M}}1\quad\text{and}\quad\sum_{j\neq
I^{*}}\frac{p_{t,j}^{2}}{p_{t,I^{*}}^{2}}\xrightarrow{\mathbb{M}}1.$

###### Proof of Lemma 7.

We only show the upper and lower bounds for $w_{t,I^{*}}$ since proving those
for $p_{t,I^{*}}$ is the same.

By Proposition 12, there exists $T_{1}\in\mathbb{M}$ such that for any $t\geq
T_{1}$,

$w_{t,I^{*}}^{2}-\sum_{j\neq I^{*}}w_{t,j}^{2}\leq\frac{1}{2}.$

This implies

$\frac{1}{2}\geq w_{t,I^{*}}^{2}-\left(\sum_{j\neq
I^{*}}w_{t,j}\right)^{2}=w_{t,I^{*}}^{2}-\left(1-w_{t,I^{*}}\right)^{2}=2w_{t,I^{*}}-1,$

which gives $w_{t,I^{*}}\leq b_{2}\triangleq\frac{3}{4}$.

Using Proposition 12 again, there exists $T_{2}\in\mathbb{M}$ such that for
any $t\geq T_{2}$,

$w_{t,I^{*}}^{2}-\sum_{j\neq I^{*}}w_{t,j}^{2}\geq-\frac{1}{32(K-1)}.$

By Cauchy-Schwarz inequality,

$\displaystyle w_{t,I^{*}}^{2}$
$\displaystyle\geq-\frac{1}{32(K-1)}+\frac{\left(\sum_{j\neq
I^{*}}w_{t,j}\right)^{2}}{K-1}$
$\displaystyle=-\frac{1}{32(K-1)}+\frac{\left(1-w_{t,I^{*}}\right)^{2}}{K-1}$
$\displaystyle\geq-\frac{1}{32(K-1)}+\frac{1}{16(K-1)}=\frac{1}{32(K-1)},$

where the last inequality uses $w_{t,I^{*}}\leq b_{2}=\frac{3}{4}$. This gives
$w_{t,I^{*}}\geq b_{1}\triangleq\frac{1}{\sqrt{32(K-1)}}$. Taking
$T\triangleq\max\\{T_{1},T_{2}\\}$ completes the proof since $T\in\mathbb{M}$
by Lemma 2. ∎

####  B.4 Sufficient exploration under TTTS with IDS

In this subsection, we show that applied with information-directed selection,
TTTS sufficiently explores all arms:

######  Proposition 13.

Under TTTS with IDS, there exists $T\in\mathbb{M}$ such that for any $t\geq
T$,

$\min_{i\in[K]}N_{t,i}\geq\sqrt{t/K}.$

The previous analyses in Qin et al. (2017); Shang et al. (2020); Jourdan et
al. (2022) only work for any sequence of tuning parameters
$\\{h_{t}\\}_{t\in\mathbb{N}_{0}}$ that is _uniformly strictly bounded_ ,
i.e., there exists $h_{\min}>0$ such that with probability one,

$\inf_{t\in\mathbb{N}_{0}}\min\\{h_{t},1-h_{t}\\}\geq h_{\min}.$

Our IDS is adaptive to the algorithmic randomness in TTTS in the sense that it
depends on the algorithmic randomness in picking top-two candidates, so it
does not enjoy the property above. We need some novel analysis to prove the
sufficient exploration of TTTS with IDS.

Following Shang et al. (2020) of analyzing TTTS, we define the following
auxiliary arms, the two “most promising arms”:

$J_{t}^{(1)}\in\operatorname*{argmax}_{i\in[K]}\alpha_{t,i}\quad\text{and}\quad
J_{t}^{(2)}\in\operatorname*{argmax}_{i\neq J_{t}^{(1)}}\alpha_{t,i}.$ (37)

We further define the one that is less sampled as:

$J_{t}\triangleq\operatorname*{argmin}_{i\in\left\\{J_{t}^{(1)},J_{t}^{(2)}\right\\}}N_{t,i}=\operatorname*{argmin}_{i\in\left\\{J_{t}^{(1)},J_{t}^{(2)}\right\\}}p_{t,i}.$

Note that the identity of $J_{t}$ can change over time. Next we show that IDS
allocates a decent amount of effort to $J_{t}$.

######  Lemma 8.

Under TTTS with IDS, for any $t\in\mathbb{N}_{0}$,

$\psi_{t,J_{t}}\geq\frac{1}{2K(K-1)}.$

###### Proof.

Fix $t\in\mathbb{N}_{0}$. We have

$\left(I_{t}^{(1)},I_{t}^{(2)}\right)=\left(J_{t}^{(1)},J_{t}^{(2)}\right)\quad\text{with
probability}\quad\alpha_{t,J_{t}^{(1)}}\frac{\alpha_{t,J_{t}^{(2)}}}{1-\alpha_{t,J_{t}^{(1)}}}\geq\frac{1}{K(K-1)},$

where the inequality follows from the definition of $J_{t}^{(1)}$ and
$J_{t}^{(2)}$. Note that

$h_{J_{t}^{(1)},J_{t}^{(2)}}(\bm{p}_{t};\bm{\theta}_{t})=\frac{p_{t,J_{t}^{(2)}}}{p_{t,J_{t}^{(1)}}+p_{t,J_{t}^{(2)}}}.$

If
$J_{t}=\operatorname*{argmin}_{i\in\left\\{J_{t}^{(1)},J_{t}^{(2)}\right\\}}p_{t,i}=J_{t}^{(1)}$,

$\psi_{t,J_{t}}\geq\frac{1}{K(K-1)}\frac{p_{t,J_{t}^{(2)}}}{p_{t,J_{t}^{(1)}}+p_{t,J_{t}^{(2)}}}\geq\frac{1}{2K(K-1)}.$

Otherwise,
$J_{t}=\operatorname*{argmin}_{i\in\left\\{J_{t}^{(1)},J_{t}^{(2)}\right\\}}p_{t,i}=J_{t}^{(2)}$
and

$\psi_{t,J_{t}}\geq\frac{1}{K(K-1)}\frac{p_{t,J_{t}^{(1)}}}{p_{t,J_{t}^{(1)}}+p_{t,J_{t}^{(2)}}}\geq\frac{1}{2K(K-1)}.$

This completes the proof. ∎

Following Qin et al. (2017); Shang et al. (2020), we define an insufficiently
sampled set for any $t\in\mathbb{N}_{0}$ and $s\geq 0$,:

$U_{t}^{s}\triangleq\\{i\in[K]\,:\,N_{t,i}<s^{1/2}\\}.$

Proposition 13 can be rephrased as that there exists $T\in\mathbb{M}$ such
that for all $t\geq T$, $U_{t}^{t/K}$ is empty.

Lemma 11 in Shang et al. (2020) shows a nice property of TTTS: if TTTS with a
selection or tuning rule allocates a decent amount of effort to $J_{\ell}$ at
any time $\ell$, the insufficiently sampled set $U_{t}^{s}$ is empty when $t$
is large enough.

######  Lemma 9 (Lemmas 9 and 11 in Shang et al. (2020)).

Under TTTS with any selection rule (e.g., IDS) such that

$\exists\psi_{\min}>0\quad\forall
t\in\mathbb{N}_{0}\quad\psi_{t,J_{t}}\geq\psi_{\min},$

there exists $S\in\mathbb{M}$ such that for any $s\geq S$, $U^{s}_{\lfloor
Ks\rfloor}=\emptyset$.

We remark that, while the original result focuses on $\beta$-tuning, the same
proof applies to any selection rule that satisfies the condition.

Now we can complete the proof of Proposition 13.

###### Proof of Proposition 13.

By Lemma 8, IDS satisfies the condition in Lemma 9. Take the corresponding $S$
in Lemma 9 for IDS, and let $T\triangleq KS$. For any $t\geq T$, we let
$s=t/K\geq S$, and then by Lemma 9, we have $U^{s}_{\lfloor
Ks\rfloor}=U_{t}^{t/K}$ is empty. ∎

#####  B.4.1 Implication of sufficient exploration

Here we present some results that are implied by sufficient exploration
(Proposition 13) and needed for proving the sufficient condition for
optimality in fixed-confidence setting (Proposition 11). With sufficient
exploration, the posterior means strongly converge to the unknown true means,
and the probability of any sub-optimal arm being the best decays
exponentially.

######  Lemma 10 (Lemmas 6 and 12 in Shang et al. (2020)).

Under TTTS with any selection rule that ensures sufficient exploration (e.g.,
IDS), i.e.,

$\exists\tilde{T}\in\mathbb{M}\quad\forall
t\geq\tilde{T}\quad\min_{i\in[K]}N_{t,i}\geq\sqrt{t/K},$

the following properties hold:

  1. 1.

$\bm{\theta}_{t}\xrightarrow{\mathbb{M}}\bm{\theta}$; and

  2. 2.

there exists $T\in\mathbb{M}$ such that for any $t\geq T$ and $j\neq I^{*}$,

$\alpha_{t,j}\leq\exp\left(-ct^{1/2}\right),\quad\text{where}\quad
c\triangleq\frac{\Delta_{\min}^{2}}{16\sigma^{2}K^{1/2}}.$

We remark that, while the original result focuses on $\beta$-tuning, the same
proof applies to any selection rule that ensures sufficient exploration.

####  B.5 Strong convergence to optimal proportions: completing the proof of
Proposition 11

In this subsection, we are going to complete the proof of Proposition 11, the
sufficient condition for optimality for fixed-confidence setting, which
requires a sequence of results.

######  Lemma 11.

Under TTTS with IDS, for any arm $j\neq I^{*}$,

$\frac{C_{t,I^{*},j}}{p_{t,I^{*}}\cdot
f_{j}\left(\frac{p_{t,j}}{p_{t,I^{*}}}\right)}\xrightarrow{\mathbb{M}}1,\quad\text{where}\quad
f_{j}(x)\triangleq\frac{\left(\theta_{I^{*}}-\theta_{j}\right)^{2}}{2\sigma^{2}\left(1+\frac{1}{x}\right)}\quad\text{and}\quad
C_{t,I^{*},j}=\frac{\left(\theta_{t,I^{*}}-\theta_{t,j}\right)^{2}}{2\sigma^{2}\left(\frac{1}{p_{t,I^{*}}}+\frac{1}{p_{t,j}}\right)}.$

###### Proof.

Fix $j\neq I^{*}$. We have

$p_{t,I^{*}}f_{j}\left(\frac{p_{t,j}}{p_{t,I^{*}}}\right)=p_{t,I^{*}}\frac{\left(\theta_{I^{*}}-\theta_{j}\right)^{2}}{2\sigma^{2}\left(1+\frac{p_{t,I^{*}}}{p_{t,j}}\right)}=\frac{\left(\theta_{I^{*}}-\theta_{j}\right)^{2}}{2\sigma^{2}\left(\frac{1}{p_{t,I^{*}}}+\frac{1}{p_{t,j}}\right)}.$

By Proposition 13, TTTS with IDS ensures sufficient exploration, and thus by
Lemma 10, $\bm{\theta}_{t}\xrightarrow{\mathbb{M}}\bm{\theta}$. Then applying
the continuous mapping theorem (Lemma 4), we have

$\frac{C_{t,I^{*},j}}{p_{t,I^{*}}\cdot
f_{j}\left(\frac{p_{t,j}}{p_{t,I^{*}}}\right)}\xrightarrow{\mathbb{M}}1.$

This completes the proof. ∎

######  Lemma 12.

Under TTTS with IDS, for any $\epsilon>0$, there exists a deterministic
constant $c_{\epsilon}>0$ and a random time $T_{\epsilon}\in\mathbb{M}$ such
that for any $t\geq T_{\epsilon}$ and $j\neq I^{*}$,

$\frac{w_{t,j}}{w_{t,I^{*}}}>\frac{p_{j}^{*}+\epsilon}{p_{I^{*}}^{*}}\quad\implies\quad\psi_{t,j}\leq\exp\left(-c_{\epsilon}t\right)+(K-1)\exp\left(-ct^{1/2}\right),$

where $c$ is defined in Lemma 10.

###### Proof.

Fix $\epsilon>0$. It suffices to show that for any $j\neq I^{*}$, there exist
a deterministic constant $c^{(j)}_{\epsilon}>0$ and a random time
$T^{(j)}_{\epsilon}\in\mathbb{M}$ such that for any $t\geq
T^{(j)}_{\epsilon}$,

$\frac{w_{t,j}}{w_{t,I^{*}}}>\frac{p_{j}^{*}+\epsilon}{p_{I^{*}}^{*}}\quad\implies\quad\psi_{t,j}\leq\exp\left(-c_{\epsilon}^{(j)}t\right)+(K-1)\exp\left(-ct^{1/2}\right),$

since this completes the proof by taking $T_{\epsilon}\triangleq\max_{j\neq
I^{*}}T^{(j)}_{\epsilon}$ and $c_{\epsilon}\triangleq\min_{j\neq
I^{*}}c^{(j)}_{\epsilon}$.

From now on, we fix $j\neq I^{*}$. By Corollary 2, there exists
$T_{\epsilon,1}^{(j)}\in\mathbb{M}$ such that for any $t\geq
T_{\epsilon,1}^{(j)}$,

$\frac{w_{t,j}}{w_{t,I^{*}}}=\frac{\Psi_{t,j}}{\Psi_{t,I^{*}}}>\frac{p_{j}^{*}+\epsilon}{p_{I^{*}}^{*}}\quad\implies\quad\frac{p_{t,j}}{p_{t,I^{*}}}=\frac{N_{t,j}}{N_{t,I^{*}}}>\frac{p_{j}^{*}+\epsilon/2}{p_{I^{*}}^{*}}.$

Then by Corollary 3, there exists $T_{\epsilon,2}^{(j)}\in\mathbb{M}$ such
that for any $t\geq T_{\epsilon,2}^{(j)}$,

$\frac{p_{t,j}}{p_{t,I^{*}}}>\frac{p_{j}^{*}+\epsilon/2}{p_{I^{*}}^{*}}\quad\implies\quad\exists
A_{t}\neq
I^{*}\,\,:\,\,\frac{p_{t,A_{t}}}{p_{t,I^{*}}}\leq\frac{p_{A_{t}}^{*}}{p_{I^{*}}^{*}}.$

From now on, we consider
$t\geq\max\left\\{T_{\epsilon,1}^{(j)},T_{\epsilon,2}^{(j)}\right\\}$ and we
have

$\frac{w_{t,j}}{w_{t,I^{*}}}=\frac{\Psi_{t,j}}{\Psi_{t,I^{*}}}>\frac{p_{j}^{*}+\epsilon}{p_{I^{*}}^{*}}\quad\implies\quad\frac{p_{t,j}}{p_{t,I^{*}}}=\frac{N_{t,j}}{N_{t,I^{*}}}>\frac{p_{j}^{*}+\epsilon/2}{p_{I^{*}}^{*}}\quad\text{and}\quad\exists
A_{t}\neq
I^{*}\,\,:\,\,\frac{p_{t,A_{t}}}{p_{t,I^{*}}}\leq\frac{p_{A_{t}}^{*}}{p_{I^{*}}^{*}}.$
(38)

By Lemmas 6 and 10,

$\displaystyle\psi_{t,j}\leq\alpha_{t,I^{*}}\frac{\alpha_{t,j}}{1-\alpha_{t,I^{*}}}\frac{p_{t,I^{*}}}{p_{t,I^{*}}+p_{t,j}}+(1-\alpha_{t,I^{*}})\leq\frac{\alpha_{t,j}}{1-\alpha_{t,I^{*}}}+(K-1)\exp\left(-ct^{1/2}\right).$

We can upper bound the numerator $\alpha_{t,j}$ as follows,

$\displaystyle\alpha_{t,j}\leq\mathbb{P}_{t}\left(\tilde{\theta}_{j}\geq\tilde{\theta}_{I^{*}}\right)$
$\displaystyle=\mathbb{P}\left(\frac{\tilde{\theta}_{I^{*}}-\tilde{\theta}_{j}-(\theta_{t,I^{*}}-\theta_{t,j})}{\sigma\sqrt{1/N_{t,I^{*}}+1/N_{t,j}}}\leq\frac{-(\theta_{t,I^{*}}-\theta_{t,j})}{\sigma\sqrt{1/N_{t,I^{*}}+1/N_{t,j}}}\right)$
$\displaystyle=\Phi\left(-\sqrt{2tC_{t,I^{*},j}}\right),$

where
$\tilde{\bm{\theta}}=\left(\tilde{\theta}_{1},\ldots,\tilde{\theta}_{K}\right)$
is a sample drawn from the posterior distribution $\Pi_{t}$ and $\Phi(\cdot)$
is Gaussian cumulative distribution function. Similarly, we can lower bound
the denominator $1-\alpha_{t,I^{*}}$ as follows,

$1-\alpha_{t,I^{*}}=\mathbb{P}_{t}\left(\exists a\neq
I^{*}\,:\,\tilde{\theta}_{a}\geq\tilde{\theta}_{I^{*}}\right)\geq\mathbb{P}_{t}\left(\tilde{\theta}_{A_{t}}\geq\tilde{\theta}_{I^{*}}\right)=\Phi\left(-\sqrt{2tC_{t,I^{*},A_{t}}}\right).$

Hence,

$\psi_{t,j}\leq\frac{\Phi\left(-\sqrt{2tC_{t,I^{*},j}}\right)}{\Phi\left(-\sqrt{2tC_{t,I^{*},A_{t}}}\right)}+(K-1)\exp\left(-ct^{1/2}\right).$

The remaining task is to show that there exist a deterministic constant
$c^{(j)}_{\epsilon}>0$ and a random time $T^{(j)}_{\epsilon,3}\in\mathbb{M}$
such that for any $t\geq T^{(j)}_{\epsilon,3}$,

$\frac{\Phi\left(-\sqrt{2tC_{t,I^{*},j}}\right)}{\Phi\left(-\sqrt{2tC_{t,I^{*},A_{t}}}\right)}\leq\exp\left(-c_{\epsilon}^{(j)}t\right).$
(39)

By Lemma 11, for any $\delta>0$,

$\displaystyle\frac{\Phi\left(-\sqrt{2tC_{t,I^{*},j}}\right)}{\Phi\left(-\sqrt{2tC_{t,I^{*},A_{t}}}\right)}$
$\displaystyle\leq\frac{\Phi\left(-\sqrt{2tp_{t,I^{*}}f_{j}\left(\frac{p_{t,j}}{p_{t,I^{*}}}\right)(1-\delta)}\right)}{\Phi\left(-\sqrt{2tp_{t,I^{*}}f_{A_{t}}\left(\frac{p_{t,A_{t}}}{p_{t,I^{*}}}\right)(1+\delta)}\right)}$
$\displaystyle\leq\frac{\Phi\left(-\sqrt{2tp_{t,I^{*}}f_{j}\left(\frac{p^{*}_{j}+\epsilon/2}{p^{*}_{I^{*}}}\right)(1-\delta)}\right)}{\Phi\left(-\sqrt{2tp_{t,I^{*}}f_{A_{t}}\left(\frac{p^{*}_{A_{t}}}{p^{*}_{I^{*}}}\right)(1+\delta)}\right)}$
$\displaystyle=\frac{\Phi\left(-\sqrt{2tp_{t,I^{*}}f_{j}\left(\frac{p^{*}_{j}+\epsilon/2}{p^{*}_{I^{*}}}\right)(1-\delta)}\right)}{\Phi\left(-\sqrt{2tp_{t,I^{*}}f_{j}\left(\frac{p^{*}_{j}}{p^{*}_{I^{*}}}\right)(1+\delta)}\right)},$

where the second inequality follows from (38) the monotonicity of $f_{j}$ and
$f_{A_{t}}$ and the final equality uses the information balance (32).

We can pick a sufficiently small $\delta$ as a function of $\epsilon$ such
that

$c_{1}\triangleq
f_{j}\left(\frac{p^{*}_{j}+\epsilon/2}{p^{*}_{I^{*}}}\right)(1-\delta)>f_{j}\left(\frac{p^{*}_{j}}{p^{*}_{I^{*}}}\right)(1+\delta)\triangleq
c_{2}.$

Then (39) follows from Gaussian tail upper and lower bounds (or
$\frac{1}{t}\log\Phi\left(-\sqrt{t}x\right)\to-x^{2}/2$ as $t\to\infty$) and
that $p_{t,I^{*}}$ is bounded away from 0 and 1 when $t$ is large (Lemma 7).
This completes the proof. ∎

######  Lemma 13.

Under TTTS with IDS, for any $\epsilon>0$, there exists
$T_{\epsilon}\in\mathbb{M}$ such that for any $t\geq T_{\epsilon}$,

$\frac{w_{t,j}}{w_{t,I^{*}}}\leq\frac{p_{j}^{*}+\epsilon}{p_{I^{*}}^{*}},\quad\forall
j\neq I^{*}.$

###### Proof.

Fix $\epsilon>0$ and $j\neq I^{*}$. By Lemma 12, there exists
$\tilde{T}_{\epsilon}\in\mathbb{M}$ such that for any
$t\geq\tilde{T}_{\epsilon}$ and $j\neq I^{*}$,

$\frac{w_{t,j}}{w_{t,I^{*}}}>\frac{p_{j}^{*}+\epsilon/2}{p_{I^{*}}^{*}}\quad\implies\quad\psi_{t,j}\leq\exp\left(-c_{\epsilon}t\right)+(K-1)\exp\left(-ct^{1/2}\right).$

Define

$\kappa_{\epsilon}\triangleq\sum_{\ell=0}^{\infty}\left[\exp\left(-c_{\epsilon}\ell\right)+(K-1)\exp\left(-c\ell^{1/2}\right)\right]<\infty.$

From now on, we consider $t\geq\tilde{T}_{\epsilon}$. We need to consider two
cases, and we provide an upper bound on $\frac{w_{t,j}}{w_{t,I^{*}}}$ for each
case.

  1. 1.

The first case supposes that

$\forall\ell\in\left\\{\tilde{T}_{\epsilon},\tilde{T}_{\epsilon}+1,\ldots,t-1\right\\}:\quad\frac{w_{\ell,j}}{w_{\ell,I^{*}}}\geq\frac{p_{j}^{*}+\epsilon/2}{p^{*}_{I^{*}}}.$

We have

$\displaystyle\Psi_{t,j}$
$\displaystyle=\Psi_{\tilde{T}_{\epsilon},j}+\sum_{\ell=\tilde{T}_{\epsilon}}^{t-1}\psi_{\ell,j}$
$\displaystyle=\Psi_{\tilde{T}_{\epsilon},j}+\sum_{\ell=\tilde{T}_{\epsilon}}^{t-1}\psi_{\ell,j}\mathbf{1}\left(\frac{w_{\ell,j}}{w_{\ell,I^{*}}}\geq\frac{p_{j}^{*}+\epsilon/2}{p^{*}_{I^{*}}}\right)$
$\displaystyle\leq\Psi_{\tilde{T}_{\epsilon},j}+\sum_{\ell=\tilde{T}_{\epsilon}}^{t-1}\left[\exp\left(-c_{\epsilon}\ell\right)+(K-1)\exp\left(-c\ell^{1/2}\right)\right]$
$\displaystyle\leq\Psi_{\tilde{T}_{\epsilon},j}+\kappa_{\epsilon}.$

Take $T\in\mathbb{M}$ in Lemma 7, so for any $t\geq T$, $\Psi_{t,I^{*}}\geq
b_{1}t$, and thus

$\frac{w_{t,j}}{w_{t,I^{*}}}=\frac{\Psi_{t,j}}{\Psi_{t,I^{*}}}\leq\frac{\Psi_{\tilde{T}_{\epsilon},j}+\kappa_{\epsilon}}{\Psi_{t,I^{*}}}\leq\frac{\tilde{T}_{\epsilon}+\kappa_{\epsilon}}{b_{1}t}.$
(40)

  2. 2.

The alternative case supposes that

$\exists\ell\in\left\\{\tilde{T}_{\epsilon},\tilde{T}_{\epsilon}+1,\ldots,t-1\right\\}:\quad\frac{w_{\ell,j}}{w_{\ell,I^{*}}}<\frac{p_{j}^{*}+\epsilon/2}{p^{*}_{I^{*}}}.$

We define

$L_{t}\triangleq\max\left\\{\ell\in\left\\{\tilde{T}_{\epsilon},\tilde{T}_{\epsilon}+1,\ldots,t-1\right\\}\,:\,\frac{w_{\ell,j}}{w_{\ell,I^{*}}}<\frac{p_{j}^{*}+\epsilon/2}{p^{*}_{I^{*}}}\right\\}.$

We have

$\displaystyle\Psi_{t,j}$
$\displaystyle=\Psi_{L_{t},j}+\psi_{L_{t},j}+\sum_{\ell=L_{t}+1}^{t-1}\psi_{\ell,j}$
$\displaystyle=\Psi_{L_{t},j}+\psi_{L_{t},j}+\sum_{\ell=L_{t}+1}^{t-1}\psi_{\ell,j}\mathbf{1}\left(\frac{w_{\ell,j}}{w_{\ell,I^{*}}}\geq\frac{p_{j}^{*}+\epsilon/2}{p^{*}_{I^{*}}}\right)$
$\displaystyle\leq\frac{p_{j}^{*}+\epsilon/2}{p^{*}_{I^{*}}}\Psi_{L_{t},I^{*}}+1+\sum_{\ell=L_{t}+1}^{t-1}\left[\exp\left(-c_{\epsilon}\ell\right)+(K-1)\exp\left(-c\ell^{1/2}\right)\right]$
$\displaystyle\leq\frac{p_{j}^{*}+\epsilon/2}{p^{*}_{I^{*}}}\Psi_{L_{t},I^{*}}+\left(\kappa_{\epsilon}+1\right),$

where the first inequality uses
$\frac{\Psi_{L_{t},j}}{\Psi_{L_{t},I^{*}}}=\frac{w_{L_{t},j}}{w_{L_{t},I^{*}}}<\frac{p_{j}^{*}+\epsilon/2}{p^{*}_{I^{*}}}$.
Then by Lemma 7, for any $t\geq T$,

$\frac{w_{t,j}}{w_{t,I^{*}}}\leq\frac{p_{j}^{*}+\epsilon/2}{p^{*}_{I^{*}}}\frac{\Psi_{L_{t},I^{*}}}{\Psi_{t,I^{*}}}+\frac{1+\kappa_{\epsilon}}{\Psi_{t,I^{*}}}\leq\frac{p_{j}^{*}+\epsilon/2}{p^{*}_{I^{*}}}+\frac{1+\kappa_{\epsilon}}{b_{1}t}.$
(41)

Putting (40) and (41) together, we find that for any $t\geq T_{1}$,

$\frac{w_{t,j}}{w_{t,I^{*}}}=\frac{\Psi_{t,j}}{\Psi_{t,I^{*}}}\leq\max\left\\{\frac{\tilde{T}_{\epsilon}+\kappa_{\epsilon}}{b_{1}t}\,,\,\frac{p_{j}^{*}+\epsilon/2}{p^{*}_{I^{*}}}+\frac{\kappa_{\epsilon}+1}{b_{1}t}\right\\}\leq\frac{p_{j}^{*}+\epsilon/2}{p^{*}_{I^{*}}}+\frac{\tilde{T}_{\epsilon}+2\kappa_{\epsilon}+1}{t}.$

Then we have

$t\geq\frac{2\left(\tilde{T}_{\epsilon}+2\kappa_{\epsilon}+1\right)}{\epsilon}\quad\implies\quad\frac{w_{t,j}}{w_{t,I^{*}}}\leq\frac{p_{j}^{*}+\epsilon}{p^{*}_{I^{*}}}.$

Taking
$T_{\epsilon}\triangleq\max\left\\{\tilde{T}_{\epsilon},T,\frac{2\left(\tilde{T}_{\epsilon}+2\kappa_{\epsilon}+1\right)}{\epsilon}\right\\}$
completes the proof since Lemma 2 implies $T_{\epsilon}\in\mathbb{M}$. ∎

Now we are ready to complete the proof of Proposition 11.

###### Proof of Proposition 11.

Corollary 3 and Lemma 13 give Proposition 11. ∎

###  Appendix C Proof of Proposition 7

Define $\Delta_{\min}\triangleq\min_{i\in[K]}|\theta_{i}-\mathfrak{T}|$ and
$\Delta_{\max}\triangleq\max_{i\in[K]}|\theta_{i}-\mathfrak{T}|$.

####  C.1 Sufficient exploration

######  Proposition 14.

There exists $T\in\mathbb{M}$ such that for any $t\geq T$,

$\min_{i\in[K]}N_{t,i}\geq\sqrt{t/K}.$

Following Qin et al. (2017); Shang et al. (2020), we define the following sets
for any $t\in\mathbb{N}_{0}$ and $s\geq 0$,:

$U_{t}^{s}\triangleq\\{i\in[K]\,:\,N_{t,i}<s^{1/2}\\}$

and

$V_{t}^{s}\triangleq\\{i\in[K]\,:\,N_{t,i}<s^{3/4}\\}.$

We let $\overline{U_{t}^{s}}=[K]\setminus U_{t}^{s}$ and
$\overline{V_{t}^{s}}=[K]\setminus V_{t}^{s}$.

######  Lemma 14.

There exists $S\in\mathbb{M}$ such that for any $s\geq S$, if $U_{t}^{s}$ is
nonempty, then $I_{t}\in V_{t}^{s}$.

###### Proof.

By Lemma 5, there exists $S_{1}\in\mathbb{M}$ such that for any $s\geq S_{1}$
and any $t\in\mathbb{N}_{0}$, if $i\in\overline{V_{t}^{s}}$, then
$|\theta_{t,i}-\mathfrak{T}|\geq\Delta_{\min}/2$. On the other hand, if $j\in
U_{t}^{s}$, then by the definition of $W_{1}$,
$|\theta_{t,j}-\mathfrak{T}|\leq\Delta_{\max}+\sigma W_{1}$. Hence, there
exists $S_{2}\in\mathbb{M}$ such that for $s\geq S_{1}$,
$p_{t,j}d(\theta_{t,j},\mathfrak{T})<p_{t,i}d(\theta_{t,i},\mathfrak{T})$,
which implies $I_{t}\notin\overline{V_{t}^{s}}$, i.e., $I_{t}\in V_{t}^{s}$. ∎

The proof of Proposition 14 follows from the above lemma and a variant of
Lemma 9.

####  C.2 Strong convergence to optimal proportions

For notational convenience, let $w_{t,i}\triangleq\frac{\Psi_{t,i}}{t}$ for
any $(t,i)\in\mathbb{N}_{0}\times[K]$. Now we define the over-sampled sets as
follows: for any $t\in\mathbb{N}_{0}$ and $\epsilon>0$,

$O_{t,\epsilon}\triangleq\left\\{j\in[K]\,:\,w_{t,i}>p_{i}^{*}+\epsilon\right\\}.$

######  Lemma 15.

For any arm $i\in[K]$,

$\frac{C_{t,i}}{D_{t,i}}\xrightarrow{\mathbb{M}}1\quad\text{where}\quad
D_{t,i}\triangleq
p_{t,i}d(\theta_{i},\mathfrak{T})=\frac{p_{t,i}\left(\theta_{i}-\mathfrak{T}\right)^{2}}{2\sigma^{2}}.$

######  Lemma 16.

For any $\epsilon>0$, there exists a random time $T_{\epsilon}\in\mathbb{M}$
such that for any $t\geq T_{\epsilon}$ and $i\in[K]$,

$i\in O_{t,\epsilon}\quad\implies\quad\psi_{t,i}=0.$

###### Proof.

There exists $T_{1}\in\mathbb{M}$ such that for any $t\geq T_{1}$ and
$i\in[K]$,

$i\in O_{t,\epsilon}\quad\implies\quad
p_{t,i}>p_{i}^{*}+\epsilon/2\quad\text{and}\quad\exists J_{t}\neq
I^{*}\,\,\text{s.t.}\,\,p_{t,J_{t}}\geq p_{J_{t}}.$
$\displaystyle\frac{C_{t,i}}{C_{t,J_{t}}}$
$\displaystyle=\frac{p_{t,i}\left(\theta_{t,i}-\mathfrak{T}\right)^{2}}{p_{t,J_{t}}\left(\theta_{t,J_{t}}-\mathfrak{T}\right)^{2}}$
$\displaystyle\geq\frac{p_{t,i}\left(\theta_{i}-\mathfrak{T}\right)^{2}(1-\delta)}{p_{t,J_{t}}\left(\theta_{J_{t}}-\mathfrak{T}\right)^{2}(1+\delta)}$
$\displaystyle\geq\frac{\left(p_{i}+\frac{\epsilon}{2}\right)\left(\theta_{i}-\mathfrak{T}\right)^{2}(1-\delta)}{p_{J_{t}}^{*}\left(\theta_{J_{t}}-\mathfrak{T}\right)^{2}(1+\delta)}$
$\displaystyle>1,$

where the first inequality uses the above lemma and picks a sufficient small
$\delta$ as a function of $\epsilon$ such that the last inequality holds. ∎

######  Lemma 17.

For any $\epsilon>0$, there exists $T_{\epsilon}\in\mathbb{M}$ such that for
any $t\geq T_{\epsilon}$,

$\forall i\in[K],\quad i\notin O_{t,\epsilon}\quad\text{i.e.}\quad w_{t,i}\leq
p_{i}^{*}+\epsilon.$

###### Proof.

Since $K$ is finite, it suffices to consider a fixed $i\in[K]$. There exists
$\tilde{T}_{\epsilon}\in\mathbb{M}$ such that for any
$t\geq\tilde{T}_{\epsilon}$,

$i\in O_{t,\epsilon}\quad\implies\quad\psi_{t,i}=0.$

We need to consider two cases.

  1. 1.

$\exists\ell\in\left\\{\tilde{T}_{\epsilon},\tilde{T}_{\epsilon}+1,\ldots,t-1\right\\},w_{\ell,i}\leq
p_{i}^{*}+\epsilon$.

Define

$L_{t}\triangleq\max\left\\{\ell\in\left\\{\tilde{T}_{\epsilon},\tilde{T}_{\epsilon}+1,\ldots,t-1\right\\}\,:\,w_{\ell,i}\leq
p_{i}^{*}+\epsilon\right\\}.$

Then

$\displaystyle
w_{t,i}=\frac{\Psi_{t,i}}{t}=\frac{\Psi_{L_{t},i}}{t}\leq\frac{\Psi_{L_{t},i}}{L_{t}}=w_{L_{t},i}\leq
p_{i}^{*}+\epsilon.$

  2. 2.

$\forall\ell\in\left\\{\tilde{T}_{\epsilon},\tilde{T}_{\epsilon}+1,\ldots,t-1\right\\},w_{\ell,i}>p_{i}^{*}+\epsilon/2$.

We have

$\displaystyle
w_{t,i}=\frac{\Psi_{t,i}}{t}=\frac{\Psi_{\tilde{T}_{\epsilon},i}}{t}.$

Letting
$T_{\epsilon,i}\triangleq\max\left\\{\tilde{T}_{\epsilon},\frac{\Psi_{\tilde{T}_{\epsilon},i}}{p_{i}^{*}+\epsilon}\right\\}$
completes the proof. ∎

###  Appendix D Proof of Theorem 3

###### Proof.

Note that the optimal allocation problem (3) is equivalent to

$\displaystyle\Gamma^{*}=\max_{\phi,\bm{p}}$ $\displaystyle\hskip 10.0pt\phi$
(42a) $\displaystyle\mathrm{s.t.}$ $\displaystyle\hskip
10.0pt\sum_{i\in[K]}p_{i}-1=0,$ (42b) $\displaystyle\hskip 10.0ptp_{i}\geq
0,\quad\forall i\in[K],$ (42c) $\displaystyle\hskip 10.0pt\phi-
C_{x}(\bm{p})\leq 0,\quad\forall x\in\mathcal{X}.$ (42d)

The corresponding Lagrangian is given by

$\mathcal{L}(\phi,\bm{p},\lambda,\bm{\mu})=\phi-\lambda\left(\sum_{i\in[K]}p_{i}-1\right)-\sum_{x\in\mathcal{X}}\mu_{x}(\phi-
C_{x}(\bm{p}))+\sum_{i\in[K]}\iota_{i}p_{i}.$ (43)

Slater’s condition holds since $\bm{p}=\bm{1}/K$ and $\phi=0$ is a feasible
solution such that all inequality constraints hold strictly, where $\bm{1}$ is
a vector of $1$’s. Hence, the KKT conditions are necessary and sufficient for
global optimality, which are then given by

$\displaystyle-1+\sum_{x\in\mathcal{X}}\mu_{x}=0,$ (44a)
$\displaystyle\lambda-\sum_{x\in\mathcal{X}}\mu_{x}\frac{\partial
C_{x}(\bm{p})}{\partial p_{i}}-\iota_{i}=0,\quad\forall i\in[K],$ (44b)
$\displaystyle\sum_{i\in[K]}p_{i}-1=0,\quad p_{i}\geq 0,\quad\forall i\in[K],$
(44c) $\displaystyle\phi-C_{x}(\bm{p})\leq 0,\quad\forall x\in\mathcal{X},$
(44d) $\displaystyle\mu_{x}\geq 0,\quad\forall
x\in\mathcal{X},\quad\iota_{i}\geq 0\quad\forall i\in[K],$ (44e)
$\displaystyle\sum_{x\in\mathcal{X}}\mu_{x}(\phi-
C_{x}(\bm{p}))=0,\quad\sum_{i\in[K]}\iota_{i}p_{i}=0.$ (44f)

We first show that the KKT conditions (44) implies (27). To this end, we
reformulate the stationarity condition (44b), leaving the feasibility and
complementary slackness conditions unchanged. Define the selection functions
$h^{x}_{i}$ as in (26), which we repeat here for convenience:

$h^{x}_{i}\triangleq
h^{x}_{i}(\bm{\theta},\bm{p})=\frac{p_{i}d(\theta_{i},\vartheta^{x}_{i})}{C_{x}(\bm{p})},\quad\forall(x,i)\in\mathcal{X}\times[K].$
(45)

Now, we can rewrite the KKT conditions by eliminating the dual variables
$\lambda$ and $\iota$.

$\displaystyle\lambda-\sum_{x\in\mathcal{X}}\mu_{x}\frac{\partial
C_{x}(\bm{p})}{\partial p_{i}}-\iota_{i}=0,\quad\forall i\in[K],$
$\displaystyle\text{C-S for $\bm{\mu}$}\quad\Rightarrow\quad$
$\displaystyle\frac{\lambda}{\phi}-\sum_{x\in\mathcal{X}}\mu_{x}\frac{\frac{\partial
C_{x}(\bm{p})}{\partial
p_{i}}}{C_{x}(\bm{p})}-\frac{\iota_{i}}{\phi}=0,\quad\forall i\in[K],$ (46)
$\displaystyle\text{Multiply }p_{i}\text{ and use C-S for
$\bm{\iota}$}\quad\Rightarrow\quad$
$\displaystyle\frac{\lambda}{\phi}p_{i}-\sum_{x\in\mathcal{X}}\mu_{x}\frac{p_{i}\frac{\partial
C_{x}(\bm{p})}{\partial p_{i}}}{C_{x}(\bm{p})}=0,\quad\forall i\in[K],$ (47)
$\displaystyle\Rightarrow\quad$
$\displaystyle\frac{\lambda}{\phi}p_{i}-\sum_{x\in\mathcal{X}}\mu_{x}h^{x}_{i}=0,\quad\forall
i\in[K],$ $\displaystyle\text{Sum over }i\quad\Rightarrow\quad$
$\displaystyle\frac{\lambda}{\phi}-\sum_{x\in\mathcal{X}}\mu_{x}\sum_{i\in[K]}h^{x}_{i}=0,\quad\forall
i\in[K],$ $\displaystyle\text{Primal and dual
feasibility}\quad\Rightarrow\quad$
$\displaystyle\frac{\lambda}{\phi}=1,\quad\forall i\in[K].$

Substituting $\lambda=\phi$ into (47) yields the desired result. Note that
(47) is equivalent to (46) if and only if $\bm{p}^{*}$ is strictly positive.

Next, we show that (27) implies the KKT conditions in (44) when the optimal
solution is strictly positive. First, when $\bm{p}^{*}$ is strictly positive,
we have $\bm{\iota}=\bm{0}$. We have that (44a), (44d), (44e), and (44f) hold
automatically. Let $\lambda=\phi$, we have (44b) using (47), (44f) and
$\bm{\iota}=\bm{0}$. Finally, (44c) is obtained by summing (27a) over all
$i\in[K]$ and noting that $\bm{\mu}\in\mathcal{S}_{|\mathcal{X}|}$. This
completes the proof. ∎

###  Appendix E Best-$k$-arm identification

We now consider a natural extension of best-arm identification, where we aim
to find the exact set of $k$ best-arms

$\mathcal{I}({\bm{\theta}})\triangleq\operatorname*{argmax}_{\mathcal{A}\subseteq[K],|\mathcal{A}|=k}\left\\{\sum_{i\in\mathcal{A}}\theta_{i}\right\\},$

where $k<K$ is a fixed integer. We refer to arms in $\mathcal{I}(\bm{\theta})$
as the top arms and arms in
$\mathcal{I}^{c}(\bm{\theta})=[K]\backslash\mathcal{I}(\bm{\theta})$ as the
bottom arms.

For the fixed-confidence best-$k$-arm identification problem with $k>1$, we
are facing a more complex exploration task, where each pair of arms
$(i,j)\in\mathcal{X}(\bm{\theta})=\mathcal{I}(\bm{\theta})\times\mathcal{I}^{c}(\bm{\theta})$
need to be compared. Indeed, the alternative set can be decomposed as

$\mathrm{Alt}(\bm{\theta})=\bigcup_{(i,j)\in\mathcal{I}(\bm{\theta})\times\mathcal{I}^{c}(\bm{\theta})}\mathrm{Alt}_{i,j},\quad\hbox{where}\quad\mathrm{Alt}_{i,j}\triangleq\left\\{\bm{\vartheta}:\vartheta_{j}>\vartheta_{i}\right\\}.$

For each culprit $(i,j)\in\mathcal{X}(\bm{\theta})$, the function $C_{i,j}$ is
given by

$\displaystyle C_{i,j}(\bm{p})$
$\displaystyle\triangleq\inf_{\bm{\vartheta}\in\mathrm{Alt}_{i,j}}\sum_{i}p_{i}d(\theta_{i},\vartheta_{i})$
$\displaystyle=\inf_{\vartheta_{j}>\vartheta_{i}}\left\\{p_{i}d(\theta_{i},\vartheta_{i})+p_{j}d(\theta_{j},\vartheta_{j})\right\\}$
$\displaystyle=\inf_{\tilde{\theta}}\left\\{p_{i}d(\theta_{i},\tilde{\theta})+p_{j}d(\theta_{j},\tilde{\theta})\right\\}$
$\displaystyle=p_{i}d(\theta_{i},\bar{\theta}_{i,j})+p_{j}d(\theta_{j},\bar{\theta}_{i,j}),\quad\hbox{where}\quad\bar{\theta}_{i,j}\triangleq\frac{p_{i}\theta_{i}+p_{j}\theta_{j}}{p_{i}+p_{j}}.$
(48)

In the second line, we set $\vartheta_{k}=\theta_{k}$ for all $k\neq i,j$; the
third line follows from the monotonicity of KL divergence; and the last
equality follows from explicitly solving the one-dimensional convex
optimization analytically. The optimal allocation problem (3) is then given by

$\Gamma^{*}_{\bm{\theta}}=\max_{\bm{p}\in\mathcal{S}_{K}}\min_{(i,j)\in\mathcal{I}\times\mathcal{I}^{c}}C_{i,j}(\bm{p}).$
(49)

We present several properties of the optimal solution to (49). These
properties generalize those for BAI in Garivier and Kaufmann (2016). We
postpone the proof to Appendix E.4. To the best of our knowledge, we provide
the first uniqueness result for best-$k$-arm identification problem. We
collect the proof in Appendix E.4.

######  Proposition 15 (Properties of the optimal solution).

The optimal solution $\bm{p}^{*}$ to (49) satisfies the following properties

  1. 1.

Uniqueness: $\bm{p}^{*}$ is unique.

  2. 2.

Positivity: $\bm{p}^{*}>\bm{0}$.

  3. 3.

Monotonicity: for all $i,i^{\prime}\in\mathcal{I}$ we have
$\theta_{i}\geq\theta_{i^{\prime}}\implies p^{*}_{i}\leq p^{*}_{i^{\prime}}$;
and for all $j,j^{\prime}\in\mathcal{I}^{c}$ we have
$\theta_{j}\geq\theta_{j^{\prime}}\implies p^{*}_{j}\geq p^{*}_{j^{\prime}}$.

We now revisit two of the most prominent approaches in solving BAI problems
with fixed-confidence optimality and demonstrate the challenges in
generalizing them for the best-$k$-arm identification problem. We subsequently
present our ACC algorithm and briefly discuss how these challenges are
addressed.

####  E.1 Optimality conditions that are dependent only on the allocation
vector.

As stated in Proposition 3, the BAI problem admits a simple optimality
condition that depends only on the allocation vector $\bm{p}$. Given the
simplicity and popularity of the conditions in Proposition 3, it may be
intriguing to consider a direct generalization of these conditions for $k>1$
and to hope that they remain sufficient, as studied in Gao and Chen (2015,
Theorem 2) and Zhang et al. (2023, Theorem 3). Unfortunately, these
conditions, albeit necessary, fail to remain sufficient.

We first summarize the conditions that generalize Proposition 3. For ease of
presentation, we show results for Gaussian bandits.

######  Proposition 16.

For Gaussian bandits, the following conditions are necessary for the
optimality of $\bm{p}^{*}$ for (49):

  1. 1.

Information balance:

$\Gamma_{\bm{\theta}}^{*}=\min_{j^{\prime}\in\mathcal{I}^{c}}C_{i,j^{\prime}}(\bm{p}^{*})\quad\forall
i\in\mathcal{I}\quad\text{and}\quad\Gamma_{\bm{\theta}}^{*}=\min_{i^{\prime}\in\mathcal{I}}C_{i^{\prime},j}(\bm{p}^{*})\quad\forall
j\in\mathcal{I}^{c}.$ (50)

  2. 2.

Overall balance:

$\sum_{i\in\mathcal{I}}(p^{*}_{i})^{2}=\sum_{j\in\mathcal{I}^{c}}(p^{*}_{j})^{2}.$
(51)

The information balance suggests that the optimal allocation should balance
the statistical evidence gathered to distinguish any top arm $i$ from its
corresponding most confusing bottom arm(s)

$j_{i}\in\operatorname*{argmin}_{j^{\prime}\in\mathcal{I}^{c}}C_{i,j^{\prime}}(\bm{p}^{*}),$

and similarly, any bottom arm from its corresponding most confusing top
arm(s). However, it is a priori unclear which pairs of $(i,j)$ are the most
confusing under the optimal allocation.

Indeed, these simplistic balancing conditions fail to be sufficient when
$k>1$. We present a counterexample using Gaussian bandits in Example 5. This
example implies that the crude information balance in Proposition 16 cannot
guarantee optimality, even when combined with the correct overall balance.

######  Example 5 (Failure of sufficiency).

We point out that conditions in Proposition 16 do not guarantee the uniqueness
of the solution nor the optimality. We present a counterexample in a Gaussian
bandit with $(k,K)=(2,4)$. Consider Gaussian rewards with mean
$\bm{\theta}=(1,0.7,0,-0.5)$ and variance $\sigma^{2}=1/4$. The solution
$\bm{p}_{1}\approx(0.0482,0.459,0.4603,0.0325)$ satisfies Proposition 16 with
an objective value of $\Gamma_{\bm{\theta}}(\bm{p}_{1})\approx 0.0873$. For
$\bm{p}_{1}$, we have
$C_{1,3}(\bm{p}_{1})=C_{1,4}(\bm{p}_{1})=C_{2,4}(\bm{p}_{1})<C_{2,3}(\bm{p}_{1})$.
However, the optimal solution is
$\bm{p}^{*}\approx(0.1277,0.3894,0.4016,0.0813)$ with an optimal value of
$\Gamma^{*}_{\bm{\theta}}\approx 0.1938>\Gamma_{\bm{\theta}}(\bm{p}_{1})$. For
$\bm{p}^{*}$, we have
$C_{1,3}(\bm{p}^{*})=C_{2,4}(\bm{p}^{*})=C_{2,3}(\bm{p}^{*})<C_{1,4}(\bm{p}^{*})$.
$\hfill\square$

Our analysis shows that to obtain a sufficient condition (that is based only
on the allocation vector $\bm{p}$ as did in the literature), the overall
balance condition needs to be decomposed into finer balance conditions among
subgroups of arms; see Appendix E for a detailed discussion. This result
indicates that algorithms that rely only on overall balance are highly likely
to be suboptimal.

Unfortunately, the optimal decomposition of subgroups of arms relies on the
true $\bm{\theta}$, which is unavailable a priori. Due to the _combinatorial_
number of possibilities, we caution that these conditions are too complicated
to yield any meaningful algorithm.

####  E.2 Adaptive adjustment of the tuning parameter in top-two algorithms.

An alternative approach to designing an optimal algorithm for best-$k$-arm
identification is to adaptively update the tuning parameter $\beta$ used in
top-two algorithms, e.g., Russo (2020). For BAI, this is relatively
straightforward: (i) the optimal tuning parameter $\beta^{*}$ equals the
optimal allocation to the best arm, which can be solved using standard
bisection search as in Garivier and Kaufmann (2016); and (ii) the optimal
solution is uniquely determined by the information balance (50) and
$p_{I^{*}}=\beta^{*}$.

However, such an approach does not work for the best-$k$-arm problem. The
first complication is that $\beta^{*}$ is now interpreted as the total
allocation to the set of best-$k$-arm. This is because, assuming sufficient
exploration, the top set $\mathcal{I}$ is accurately estimated; then precisely
one candidate will be selected from each of $\mathcal{I}$ and
$\mathcal{I}^{c}$. Hence, $\beta^{*}$ is asymptotically the total allocation
to the top set $\mathcal{I}$. Consequently, solving the optimal allocation no
longer reduces to a one-dimensional optimization problem. Most importantly,
(50) and $\sum_{i\in\mathcal{I}}p_{i}=\beta^{*}$ do not guarantee the
uniqueness of the solution.

######  Example 6 (The failure of $\beta$-tuning).

We present a counterexample showing that
$\sum_{i\in\mathcal{I}}p_{i}=\beta^{*}$ and (50) do not guarantee the
uniqueness of the solution. Consider Gaussian bandits with mean rewards
$\bm{\theta}=(0.51,0.5,0,-0.01,-0.092)$, variance $\sigma^{2}=1/4$ and $k=2$.
The optimal allocation is

$\bm{p}^{*}\approx(0.21851674,0.23713642,0.21851674,0.20260818,0.12322192).$

Consider an alternative feasible solution

$\bm{p}^{\prime}\approx(0.21843623,0.23721697,0.21859726,0.20254937,0.12320016)$

such that
$p^{\prime}_{1}+p^{\prime}_{2}=p_{1}^{*}+p_{2}^{*}\triangleq\beta^{*}$. The
solution $\bm{p}^{\prime}$ is suboptimal because
$\Gamma_{\bm{\theta}}(\bm{p}^{\prime})=0.056836198<0.0568362041=\Gamma^{*}_{\bm{\theta}}.$
$\hfill\square$

####  E.3 The ACC algorithm

With $\mathcal{X}=\mathcal{I}\times\mathcal{I}^{c}$ and $C_{i,j}$ in (48),
Algorithm 5 can be immediately implemented. We remark that the ACC algorithm
significantly differs from the two previous approaches. In particular, we use
the dual variables to encode the detailed information balance. It is then
achieved by tracking the complementary-slackness conditions. With the detailed
information balance conditions, the IDS that adapts to the leading culprit can
encourage the stationarity condition to hold. We showcase the convergence of
ACC with a numerical example for the Gaussian bandits considered in Example 6.

######  Example 7 (Example 6 continued).

To demonstrate the failure of $\beta^{*}$-tuning, we consider a simplified
case where the algorithms have access to the true $\bm{\theta}$ (i.e., assume
that the estimation subroutine always returns the true $\bm{\theta}$), and
focus on whether sample allocation $\bm{p}_{t}$ converges to the optimal
$\bm{p}^{*}$. We report in Figure 1 reports the gap between the sample path of
$\Gamma_{\bm{\theta}}(\bm{p}_{t})$ and the optimal $\Gamma^{*}_{\bm{\theta}}$,
averaged across $100$ replications, where $\bm{p}_{t}$ is the sample
allocation under either ACC or an $\beta^{*}$-tuning version of ACC, i.e., in
step 5 of ACC we sample arm $i_{t}$ with probability
$\beta^{*}=p_{1}^{*}+p_{2}^{*}$ and arm $j_{t}=1-\beta^{*}$, where
$(i_{t},j_{t})=x_{t}$. It shows that the ACC algorithm with $\beta^{*}$-tuning
converges to the solution $\bm{p}^{\prime}$, which is sub-optimal, whereas the
ACC algorithm with IDS converges to the optimal solution $\bm{p}^{*}$.
$\hfill\square$

Figure 1: Consider the Gaussian bandits in Example 6. We plot the gap between
the sample path of $\Gamma_{\bm{\theta}}(\bm{p}_{t})$ and the optimal
$\Gamma^{*}_{\bm{\theta}}$, averaged across 100 replications for ACC with
$\beta^{*}$-tuning and ACC with IDS. For demonstration, we let the algorithm
access $\bm{\theta}$, i.e., we replace empirical/sampled mean vectors with the
true $\bm{\theta}$. Surprisingly, it fails to achieve the optimal
$\Gamma_{\bm{\theta}}^{*}$. However, ACC with IDS converges to $\bm{p}^{*}$.

In this section, we present detailed study of the optimal allocation problem
(6). In particular, we characterize the optimality conditions in terms of the
allocation vector $\bm{p}$ without the presence of the dual variable
$\bm{\mu}$. This type of conditions is frequently analyzed for BAI, see
Garivier and Kaufmann (2016); Chen et al. (2000); Glynn and Juneja (2004);
Chen and Ryzhov (2023). Conditions based only on $\bm{p}$ are attractive
because they directly yield intuitive and effective algorithms.

####  E.4 Proof of Proposition 15: properties of the optimal solution

###### Uniqueness.

By Lemma 20, $C_{i,j}(\cdot)$ is a concave function. Hence the optimal
allocation problem (6) is a concave programming. Consequently, the optimal set
is convex, see Boyd and Vandenberghe (2004, Chapter 2).

We prove by contradiction. Suppose there exist two optimal solutions
$\bm{p}^{\prime}\neq\bm{p}^{\prime\prime}$, then

$\bm{p}(\varepsilon)=(1-\varepsilon)\bm{p}^{\prime}+\varepsilon\bm{p}^{\prime\prime}$

is also an optimal solution for any $\varepsilon\in(0,1)$. To facilitate
discussion, we define the index set where $\bm{p}^{\prime}$ differs from
$\bm{p}^{\prime\prime}$

$\mathcal{D}=\\{i\in[K]:p_{i}^{\prime}\neq
p_{i}^{\prime\prime}\\}\neq\varnothing.$

Now, consider the optimal solution $\bm{p}^{\prime}$. By the information
balance (50), there exist a set
$\mathcal{B}\subset\mathcal{I}\times\mathcal{I}^{c}$ such that

$C_{i,j}(\bm{p}^{\prime})=\Gamma_{\bm{\theta}}(\bm{p}^{\prime}),\quad\forall(i,j)\in\mathcal{B},\quad\text{and}\quad
C_{i^{\prime},j^{\prime}}(\bm{p}^{\prime})>\Gamma_{\bm{\theta}}(\bm{p}^{\prime}),\quad\forall(i^{\prime},j^{\prime})\notin\mathcal{B}.$

For any collection $\mathcal{C}$ of $(i,j)$ pairs, we define

$\mathcal{C}_{\cap\mathcal{D}}\triangleq\\{(i,j)\in\mathcal{C}:\\{i,j\\}\cap\mathcal{D}\neq\varnothing\\}.$

  1. 1.

For any $(i,j)\in(\mathcal{B}\backslash\mathcal{B}_{\cap\mathcal{D}})$, we
have

$C_{i,j}(\bm{p}(\varepsilon))=C_{i,j}(\bm{p}^{\prime})=\Gamma_{\bm{\theta}}(\bm{p}^{\prime}).$
(52)

  2. 2.

Next, consider any $(i,j)\in\mathcal{B}^{c}$. Since
$|\mathcal{B}^{c}|<\infty$, we can define

$\Delta^{\Gamma_{\bm{\theta}}(\bm{p}^{\prime})}_{\text{min}}\triangleq\min_{(i,j)\notin\mathcal{B}}C_{i,j}(\bm{p}^{\prime})-\Gamma_{\bm{\theta}}(\bm{p}^{\prime})>0.$

By the continuity of $C_{i,j}(\cdot)$, there exists a sufficiently small
$\varepsilon$ such that

$\min_{(i,j)\notin\mathcal{B}}C_{i,j}(\bm{p}(\varepsilon))-\Gamma_{\bm{\theta}}(\bm{p}^{\prime})>\Delta^{\Gamma_{\bm{\theta}}(\bm{p}^{\prime})}_{\text{min}}/2>0,$

then

$\min_{(i,j)\notin\mathcal{B}}C_{i,j}(\bm{p}(\varepsilon))>\Gamma_{\bm{\theta}}(\bm{p}^{\prime})=\Gamma_{\bm{\theta}}(\bm{p}(\varepsilon)),$
(53)

where the last equality follows from the fact that both $\bm{p}^{\prime}$ and
$\bm{p}(\varepsilon)$ are optimal solutions.

  3. 3.

Finally, consider any $(i,j)\in\mathcal{B}_{\cap\mathcal{D}}$. Invoking Lemma
21, we conclude that $\varepsilon$ can be selected such that

$C_{i,j}(\bm{p}(\varepsilon))\neq
C_{i,j}(\bm{p}^{\prime}),\quad\forall(i,j)\in\mathcal{B}_{\cap\mathcal{D}}.$
(54)

We have the following contradictions.

  1. 1.

Suppose that there exists some $(i_{1},j_{1})\in\mathcal{B}_{\cap\mathcal{D}}$
such that

$C_{i_{1},j_{1}}(\bm{p}(\varepsilon))<C_{i_{1},j_{1}}(\bm{p}^{\prime})=\Gamma_{\bm{\theta}}(\bm{p}^{\prime}).$

Then

$\Gamma_{\bm{\theta}}(\bm{p}(\varepsilon))\leq
C_{i_{1},j_{1}}(\bm{p}(\varepsilon))<\Gamma_{\bm{\theta}}(\bm{p}^{\prime}).$

This contradicts with the fact that $\bm{p}(\varepsilon)$ is an optimal
solution.

  2. 2.

Suppose that for all $(i,j)\in\mathcal{B}_{\cap\mathcal{D}}$, we have

$C_{i_{1},j_{1}}(\bm{p}(\varepsilon))>C_{i_{1},j_{1}}(\bm{p}^{\prime})=\Gamma_{\bm{\theta}}(\bm{p}^{\prime}).$

Recall that $\mathcal{D}\neq\varnothing$, then there exist $i\in\mathcal{D}$
or $j\in\mathcal{D}$. Suppose
$i_{2}\in\mathcal{I}\cap\mathcal{D}\neq\varnothing$. Combining (52),(53) and
(54), we have

$\min_{j\in\mathcal{I}^{c}}C_{i_{2},j}(\bm{p}(\varepsilon))>\Gamma_{\bm{\theta}}(\bm{p}^{\prime}).$

Invoking the information balance in Proposition 16 we conclude that

$\Gamma_{\bm{\theta}}(\bm{p}(\varepsilon))>\Gamma_{\bm{\theta}}(\bm{p}^{\prime}).$

This contradicts with the fact that $\bm{p}^{\prime}$ is an optimal solution.
Suppose $j_{2}\in\mathcal{I}^{c}\cap\mathcal{D}\neq\varnothing$, the proof
follows similarly.

In summary, we have uniqueness of the optimal solution to (6). ∎

###### Positivity.

Consider any fixed $i\in\mathcal{I}$ and any feasible solution $\bm{p}$. If
$p_{i}=0$ for some $i\in\mathcal{I}$, then
$C_{i,j}(\bm{p})=p_{i}d(\theta_{i},\bar{\theta}_{i,j})+p_{j}d\left(\theta_{j},\frac{p_{i}\theta_{i}+p_{j}\theta_{j}}{p_{i}+p_{j}}\right)=0$
holds for all $j\in\mathcal{I}^{c}$. Similarly, if $p_{j}=0$ for some
$j\in\mathcal{I}^{c}$, then $C_{i,j}=0$ holds for all $i\in\mathcal{I}$.
However, there exists $\bm{p}=(1/K,1/K,\dots,1/K)$ such that
$C_{i,j}=\frac{1}{K}d\left(\theta_{i},\frac{\theta_{i}+\theta_{j}}{2}\right)+\frac{1}{K}d\left(\theta_{j},\frac{\theta_{i}+\theta_{j}}{2}\right)>0$
holds for all $i\in\mathcal{I}$ and $j\in\mathcal{I}^{c}$. Thus, the optimal
solution cannot have $p_{i}=0$ for any $i\in[K]$. ∎

###### Monotonicity.

For the ease of exposition, we introduce the following function

$g_{i,j}(x)=d\left(\theta_{i},\frac{\theta_{i}+x\theta_{j}}{1+x}\right)+xd\left(\theta_{j},\frac{\theta_{i}+x\theta_{j}}{1+x}\right),\quad
i\in\mathcal{I},j\in\mathcal{I}^{c}.$

Then $C_{i,j}(\bm{p})$ can be written as

$C_{i,j}(\bm{p})=p_{i}g_{i,j}\left(\frac{p_{j}}{p_{i}}\right).$

At the optimal solution $\bm{p}^{*}$, consider any $j$,
$j^{\prime}\in\mathcal{I}^{c}$ such that $\theta_{j^{\prime}}\geq\theta_{j}$.
Proposition 16 implies that there exist a $i\in\mathcal{I}$ such that

$C_{i,j}(\bm{p}^{*})=\Gamma^{*}_{\bm{\theta}}\leq
C_{i,j^{\prime}}(\bm{p}^{*}).$

Note that we must have $p^{*}_{i}>0$, the inequality above implies that

$g_{i,j}\left(\frac{p^{*}_{j}}{p^{*}_{i}}\right)\leq
g_{i,j^{\prime}}\left(\frac{p^{*}_{j^{\prime}}}{p^{*}_{i}}\right).$ (55)

By Lemma 22, for any $i,j$ and $j^{\prime}$ such that
$\theta_{i}>\theta_{j^{\prime}}\geq\theta_{j}$, we have

$g_{i,j}(x)\geq g_{i,j^{\prime}}(x)\quad\text{for all }x.$ (56)

Plugging $x=\frac{p^{*}_{j}}{p^{*}_{i}}$ into (56), we have,

$g_{i,j}\left(\frac{p^{*}_{j}}{p^{*}_{i}}\right)\geq
g_{i,j^{\prime}}\left(\frac{p^{*}_{j}}{p^{*}_{i}}\right).$ (57)

Combining (55), (57) and $g_{i,j^{\prime}}(x)>0$, we conclude that
$p_{j^{\prime}}^{*}\geq p_{j}^{*}$. This shows the monotonicity of
$\bm{p}^{*}$ within the bottom arms $\mathcal{I}^{c}$.

For the top arms $\mathcal{I}$, we introduce

$g_{j,i}(x)=d\left(\theta_{j},\frac{\theta_{j}+x\theta_{i}}{1+x}\right)+xd\left(\theta_{i},\frac{\theta_{j}+x\theta_{i}}{1+x}\right).$

Then $C_{i,j}$ can be written as

$C_{i,j}(\bm{p})=p_{j}g_{j,i}\left(\frac{p_{i}}{p_{j}}\right).$

From the proof of Lemma 22 (See (67) and replace $\theta_{i}$ with
$\theta_{j}$ in $h$), we have

$g_{j,i}^{\prime}(x)=d\left(\theta_{i},\frac{\theta_{j}+x\theta_{i}}{1+x}\right)>0$

and, for any $\theta_{i}\geq\theta_{i^{\prime}}>\theta_{j}$, we have

$g_{j,i}(x)\geq g_{j,i^{\prime}}(x)\quad\text{for all }x.$ (58)

The rest of the proof mirrors the proof of the monotonicity within the bottom
arms. At the optimal solution $\bm{p}^{*}$, consider any $i$,
$i^{\prime}\in\mathcal{I}$ such that $\theta_{i}\geq\theta_{i^{\prime}}$.
Proposition 16 also implies that there exists a $j\in\mathcal{I}^{c}$ such
that

$C_{i,j}(\bm{p}^{*})=\Gamma^{*}_{\bm{\theta}}\leq
C_{i^{\prime},j}(\bm{p}^{*}).$

Note that we must have $p^{*}_{j}>0$, the inequality above implies that

$g_{j,i}\left(\frac{p^{*}_{i}}{p^{*}_{j}}\right)\leq
g_{j,i^{\prime}}\left(\frac{p^{*}_{i^{\prime}}}{p^{*}_{j}}\right).$ (59)

Plugging $x=\frac{p^{*}_{i}}{p^{*}_{j}}$ into (58), we have,

$g_{j,i}\left(\frac{p^{*}_{i}}{p^{*}_{j}}\right)\geq
g_{j,i^{\prime}}\left(\frac{p^{*}_{i}}{p^{*}_{j}}\right).$ (60)

Combining (59), (60) and $g_{j,i^{\prime}}(x)>0$, we conclude that
$p_{i^{\prime}}^{*}\geq p_{i}^{*}$. This shows the monotonicity of
$\bm{p}^{*}$ within the top arms $\mathcal{I}$. The proof is complete. ∎

###  Appendix F Examples of algorithms for pure-exploration problems

In this section, we collect examples of pure exploration problems that
satisfies the assumptions in Section 4.1. For each pure exploration, we
explicitly derive the following components:

  1. 1.

Correct answer $\mathcal{I}(\bm{\theta})$.

  2. 2.

The alternative set $\mathrm{Alt}(\bm{\theta})$, the culprit set
$\mathcal{X}(\bm{\theta})$, and the decomposition of
$\mathrm{Alt}(\bm{\theta})$ that satisfies Assumption 1.

  3. 3.

The unique solution $\bm{\vartheta}^{x}$ in Lemma 1.

  4. 4.

The function $C_{x}(\bm{p})$.

  5. 5.

The partial derivative of $C_{x}(\bm{p})$, from which the selection function
$h_{i}^{x}(\bm{p})$ can be derived.

With explicit formula for these components, Algorithm 5 and Algorithm 6 can be
implemented.

####  F.1 BAI in unstructured bandits

  1. 1.

Correct answer: $I^{*}=\operatorname*{argmax}_{i}\\{\theta_{i}\\}$.

  2. 2.

$\mathrm{Alt}(\bm{\theta})=\cup_{j\in\mathcal{X}}\mathrm{Alt}_{j}$ with
$\mathcal{X}=[K]\backslash\\{I^{*}\\}$ and
$\mathrm{Alt}_{j}=\\{\bm{\theta}:\theta_{j}>\theta_{I^{*}}\\}$.

  3. 3.

$\bm{\vartheta}^{j}$ is given by
$\vartheta^{j}_{I^{*}}=\vartheta^{j}_{j}=\frac{p_{I^{*}}\theta_{I^{*}}+p_{j}\theta_{j}}{p_{I^{*}}+p_{j}}$
and $\vartheta^{j}_{k}=\theta_{k}$ for all $j\in\mathcal{X}$ and $k\neq
I^{*},j$.

  4. 4.

$C_{j}(\bm{p})=p_{I^{*}}d(\theta_{I^{*}},\vartheta^{j}_{I^{*}})+p_{j}d(\theta_{j},\vartheta^{j}_{j})$
for all $j\in\mathcal{X}$.

  5. 5.

$\frac{\partial C_{j}}{\partial p_{i}}=d(\theta_{i},\vartheta^{j}_{i})$ for
all $j\in\mathcal{X}$, most of them are zero, except for $i=I^{*}$ or $j$.

####  F.2 Best-$k$-arm identification in unstructured bandits

  1. 1.

Correct answer: best-$k$-arm set
$\mathcal{I}(\bm{\theta})=\operatorname*{argmax}_{\mathcal{A}\subseteq[K],|\mathcal{A}|=k}\left\\{\sum_{i\in\mathcal{A}}\theta_{i}\right\\}$.

  2. 2.

$\mathrm{Alt}(\bm{\theta})=\cup_{(i,j)\in\mathcal{X}}\mathrm{Alt}_{i,j}$ with
$\mathcal{X}=\mathcal{I}\times\mathcal{I}^{c}$ and
$\mathrm{Alt}_{i,j}=\\{\bm{\theta}:\theta_{j}>\theta_{i}\\}$.

  3. 3.

$\bm{\vartheta}^{(i,j)}$ is given by
$\vartheta^{(i,j)}_{i}=\vartheta^{(i,j)}_{j}=\frac{p_{i}\theta_{i}+p_{j}\theta_{j}}{p_{i}+p_{j}}$
and $\vartheta^{(i,j)}_{k}=\theta_{k}$ for all $(i,j)\in\mathcal{X}$ and
$k\neq i,j$.

  4. 4.

$C_{(i,j)}(\bm{p})=p_{i}d(\theta_{i},\vartheta^{(i,j)}_{i})+p_{j}d(\theta_{j},\vartheta^{(i,j)}_{j})$
for all $(i,j)\in\mathcal{X}$.

  5. 5.

$\frac{\partial C_{(i,j)}}{\partial
p_{k}}=d(\theta_{k},\vartheta^{(i,j)}_{k})$ for all $(i,j)\in\mathcal{X}$,
most of them are zero, except for $k=i$ or $j$.

####  F.3 BAI in linear bandits

Consider a set of $K$ arms. Each arm $i$ has a feature vector $\bm{a}_{i}$
attached and has Gaussian reward with mean
$\mu_{i}=\langle\bm{\theta},\bm{a}_{i}\rangle$, where $\bm{\theta}$ is an
unknown parameter. The goal is to select the arm with the highest mean reward.
See, for example, Zhou and Ryzhov (2023).

  1. 1.

Correct answer: $I^{*}=\operatorname*{argmax}_{i\in[K]}\mu_{i}$, where
$\mu_{i}=\langle\bm{\theta},\bm{a}_{i}\rangle$.

  2. 2.

$\mathrm{Alt}(\bm{\theta})=\cup_{j\in\mathcal{X}}\\{\bm{\theta}:\langle\bm{\theta},\bm{a}_{j}-\bm{a}_{I^{*}}\rangle>0\\}$
with $\mathcal{X}=[K]\backslash\\{I^{*}\\}$.

  3. 3.

$\bm{\vartheta}=\\{\bm{\vartheta}^{j}:j\in\mathcal{X}\\}$ is given in Wang et
al. (2021, (27))

$\bm{\vartheta}^{j}=\bm{\theta}+\left(\frac{\langle\bm{\theta},\bm{a}_{I^{*}}-\bm{a}_{j}\rangle}{\|\bm{a}_{I^{*}}-\bm{a}_{j}\|^{2}_{V_{\bm{p}}^{-1}}}V_{\bm{p}}^{-1}\right)(\bm{a}_{j}-\bm{a}_{I^{*}}),$

where $V_{\bm{p}}$ denotes $\sum_{k=1}^{K}p_{k}\bm{a}_{k}\bm{a}_{k}^{\top}$.
This can be derived by Lagrangian multiplier method.

  4. 4.

$C_{j}(\bm{p})=\sum_{i\in[K]}p_{i}d(\mu_{i},\varrho^{j}_{i})$ for all
$j\in\mathcal{X}$, where
$\varrho^{j}_{i}=\langle\bm{\vartheta}^{j},\bm{a}_{i}\rangle.$

  5. 5.

$\frac{\partial C_{j}}{\partial p_{i}}=d(\mu_{i},\varrho^{j}_{i})$ for all
$j\in\mathcal{X}$. Note that this partial derivative vanishes if and only if
$\mu_{i}=\varrho^{j}_{i}$. This happens if (but not only if)
$\bm{\theta}\perp(\bm{a}_{I^{*}}-\bm{a}_{j})$, indicating that sampling arm
$j$ will not provide information about arm $I^{*}$.

In the literature, the linear BAI problem complexity is usually written as

$\Gamma^{*}=\max_{\bm{p}\in\mathcal{S}_{k}}\min_{j\in\mathcal{X}}\frac{\langle\bm{\theta},\bm{a}_{I^{*}}-\bm{a}_{j}\rangle^{2}}{2\|\bm{a}_{I^{*}}-\bm{a}_{j}\|^{2}_{V_{\bm{p}}^{-1}}},$

which indicates that

$C_{j}(\bm{p})=\frac{\langle\bm{\theta},\bm{a}_{I^{*}}-\bm{a}_{j}\rangle^{2}}{2\|\bm{a}_{I^{*}}-\bm{a}_{j}\|^{2}_{V_{\bm{p}}^{-1}}}.$

To see this, we note that

$\displaystyle C_{j}(\bm{p})$
$\displaystyle=\frac{1}{2}\sum_{k=1}^{K}p_{k}\left(\bm{a}_{k}^{\top}\bm{\vartheta}^{j}-\bm{a}_{k}^{\top}\bm{\theta}\right)^{2}$
$\displaystyle=\frac{1}{2}\sum_{k=1}^{K}p_{k}\frac{1}{\|\bm{a}_{I^{*}}-\bm{a}_{j}\|^{4}_{V_{\bm{p}}^{-1}}}\left(\bm{a}_{k}^{\top}\bm{\theta}^{\top}(\bm{a}_{I^{*}}-\bm{a}_{j})V_{\bm{p}}^{-1}(\bm{a}_{j}-\bm{a}_{I^{*}})\right)^{2}$
$\displaystyle=\frac{\langle\bm{\theta},\bm{a}_{I^{*}}-\bm{a}_{j}\rangle^{2}}{2\|\bm{a}_{I^{*}}-\bm{a}_{j}\|^{4}_{V_{\bm{p}}^{-1}}}(\bm{a}_{j}-\bm{a}_{I^{*}})^{\top}\left(V_{\bm{p}}^{-1}\right)^{\top}\left(\sum_{k=1}^{K}p_{k}\bm{a}_{k}\bm{a}_{k}^{\top}\right)V_{\bm{p}}^{-1}(\bm{a}_{j}-\bm{a}_{I^{*}})$
$\displaystyle=\frac{\langle\bm{\theta},\bm{a}_{I^{*}}-\bm{a}_{j}\rangle^{2}}{2\|\bm{a}_{I^{*}}-\bm{a}_{j}\|^{4}_{V_{\bm{p}}^{-1}}}{\|\bm{a}_{I^{*}}-\bm{a}_{j}\|^{2}_{V_{\bm{p}}^{-1}}}=\frac{\langle\bm{\theta},\bm{a}_{I^{*}}-\bm{a}_{j}\rangle^{2}}{2\|\bm{a}_{I^{*}}-\bm{a}_{j}\|^{2}_{V_{\bm{p}}^{-1}}}.$

To derive the partial derivatives, we note that

$\displaystyle C_{j}(\bm{p})$
$\displaystyle=\inf_{\bm{v}\in\mathrm{Alt}_{j}}\sum_{k=1}^{K}\bm{p}_{k}d\left(\mu_{k},\bm{v}^{\top}\bm{a}_{k}\right)=\sum_{k=1}^{K}p_{k}d(\mu_{k},\langle\bm{\vartheta}^{j},\bm{a}_{k}\rangle)$

Taking the partial derivative, we have

$\frac{\partial C_{j}}{\partial
p_{i}}=d(\mu_{i},\langle\bm{\vartheta}^{j},\bm{a}_{i}\rangle)+\sum_{k=1}^{K}p_{k}\left\langle\frac{\partial
d(\mu_{k},\langle\bm{\vartheta}^{j},\bm{a}_{k}\rangle)}{\partial\vartheta^{j}},\frac{\partial\vartheta^{j}}{\partial
p_{i}}\right\rangle=d(\mu_{i},\langle\bm{\vartheta}^{j},\bm{a}_{i}\rangle),$

where the summation term vanishes due to the fact that $\bm{\vartheta}^{j}$
minimizes
$\sum_{k=1}^{K}\bm{p}_{k}d\left(\mu_{k},\bm{v}^{\top}\bm{a}_{k}\right)$ in the
interior of $\mathrm{Alt}_{j}$.

####  F.4 Best-$k$-arm identification in linear bandits

Consider a set of $K$ arms. Each arm $i$ has a feature vector $\bm{a}_{i}$
attached and has Gaussian reward with mean
$\mu_{i}=\langle\bm{\theta},\bm{a}_{i}\rangle$, where $\bm{\theta}$ is an
unknown parameter. The goal is to select the set of $k$ arms with the highest
mean rewards.

  1. 1.

Correct answer: best-$k$-arm set
$\mathcal{I}(\bm{\theta})=\operatorname*{argmax}_{\mathcal{A}\subseteq[K],|\mathcal{A}|=k}\left\\{\sum_{i\in\mathcal{A}}\mu_{i}\right\\}$,
where $\mu_{i}=\langle\bm{\theta},\bm{a}_{i}\rangle$.

  2. 2.

$\mathrm{Alt}(\bm{\theta})=\cup_{(i,j)\in\mathcal{X}}\mathrm{Alt}_{i,j}$,
where $\mathcal{X}=\mathcal{I}\times\mathcal{I}^{c}$ and
$\mathrm{Alt}_{i,j}=\\{\bm{\theta}:\langle\bm{\theta},\bm{a}_{j}-\bm{a}_{i}\rangle>0\\}$.

  3. 3.

$\bm{\vartheta}=\\{\bm{\vartheta}^{(i,j)}:(i,j)\in\mathcal{X}\\}$:

$\bm{\vartheta}^{(i,j)}=\bm{\theta}+\left(\frac{\langle\bm{\theta},\bm{a}_{i}-\bm{a}_{j}\rangle}{\|\bm{a}_{i}-\bm{a}_{j}\|^{2}_{V_{\bm{p}}^{-1}}}V_{\bm{p}}^{-1}\right)(\bm{a}_{j}-\bm{a}_{i}),$

where $V_{\bm{p}}=\sum_{i\in[K]}p_{i}\bm{a}_{i}\bm{a}_{i}^{\top}.$

  4. 4.

$C_{(i,j)}=\sum_{i\in[K]}p_{i}d(\mu_{i},\varrho^{(i,j)}_{i})$ for all
$(i,j)\in\mathcal{X}$, where
$\varrho^{(i,j)}_{i}=\langle\bm{\vartheta}^{(i,j)},\bm{a}_{i}\rangle$.

  5. 5.

$\frac{\partial C_{(i,j)}}{\partial p_{i}}=d(\mu_{i},\varrho^{(i,j)}_{i})$ for
all $(i,j)\in\mathcal{X}$. Note that this partial derivative vanishes if and
only if $\mu_{i}=\varrho^{{(i,j)}}_{i}$. This happens if (but not only if)
$\bm{\theta}\perp\bm{a}_{i}-\bm{a}_{j}$.

####  F.5 Threshold unstructured bandits

Consider a set of $K$ arms. Each arm $i$ has Gaussian reward with mean
$\theta_{i}$. A threshold $S\in\mathbb{R}$ is given. The goal is to select the
set of arms whose mean rewards are above a given threshold $\mathfrak{T}$.

  1. 1.

Correct answer:
$\mathcal{I}(\bm{\theta})=\\{k\in[K]:\theta_{k}>\mathfrak{T}\\}$.

  2. 2.

$\mathrm{Alt}(\bm{\theta})=\cup_{j\in\mathcal{X}}\mathrm{Alt}_{j}$ where
$\mathcal{X}=[K]$ and
$\mathrm{Alt}_{j}=\\{\bm{\theta}^{\prime}:(S-\theta^{\prime}_{j})(S-\theta_{j})<0\\}$.

  3. 3.

$\bm{\vartheta}^{j}$ is given by $\vartheta^{j}_{j}=\mathfrak{T}$ and
$\vartheta^{j}_{k}=\theta_{k}$ for all $j\in\mathcal{X}$ and $k\neq j$.

  4. 4.

$C_{j}(\bm{p})=\sum_{i\in[K]}p_{i}d(\theta_{i},\vartheta^{j}_{i})=p_{j}d(\theta_{i},\mathfrak{T})$.

  5. 5.

$\frac{\partial C_{j}}{\partial p_{i}}=d(\theta_{i},\vartheta^{j}_{i})$ for
all $j\in\mathcal{X}$, most of them are zero, except for $i=j$.

####  F.6 Threshold linear bandits

Consider a set of $K$ arms. Each arm $i$ is attached a feature vector
$\bm{a}_{i}$ and has Gaussian reward with mean
$\mu_{i}=\langle\bm{\theta},\bm{a}_{i}\rangle$. A threshold
$\mathfrak{T}\in\mathbb{R}$ is given. The goal is to select the set of arms
whose mean rewards are above a given threshold.

  1. 1.

Correct answer:
$I^{*}_{S}=\\{k\in[K]:\langle\bm{\theta},\bm{a}_{k}\rangle>\mathfrak{T}\\}$.

  2. 2.

$\mathrm{Alt}(\bm{\theta})=\cup_{j\in\mathcal{X}}\mathrm{Alt}_{j}$, where
$\mathcal{X}=[K]$ and
$\mathrm{Alt}_{j}=\\{\bm{\theta}^{\prime}:(\mathfrak{T}-\langle\bm{\theta}^{\prime},\bm{a}_{j}\rangle)(\mathfrak{T}-\langle\bm{\theta},\bm{a}_{j}\rangle)<0\\}$.

  3. 3.

$\bm{\vartheta}=\\{\bm{\vartheta}^{j}:j\in\mathcal{X}\\}$ is given by

$\bm{\vartheta}^{j}=\bm{\theta}+\left(\frac{|\mathfrak{T}-\langle\bm{\theta},\bm{a}_{j}\rangle|}{\|\bm{a}_{j}\|^{2}_{V_{\bm{p}}^{-1}}}V_{\bm{p}}^{-1}\right)\bm{a}_{j},$

where $V_{\bm{p}}=\sum_{k=1}^{K}p_{k}\bm{a}_{k}\bm{a}_{k}^{\top}$.

  4. 4.

$C_{j}(\bm{p})=\sum_{i\in[K]}p_{i}d(\mu_{i},\varrho_{i}^{j})$ for all
$j\in\mathcal{X}$, where
$\varrho_{i}^{j}=\langle\bm{\vartheta}^{j},\bm{a}_{i}\rangle$.

  5. 5.

$\frac{\partial C_{j}}{\partial p_{i}}=d(\mu_{i},\varrho^{j}_{i})$ for all
$j\in\mathcal{X}$.

####  F.7 Threshold bandit (selecting one arm closest to a threshold)

Consider a set of $K$ arms. Each arm $i$ has Gaussian reward with mean
$\theta_{i}$. A threshold $\mathfrak{T}\in\mathbb{R}$ is given. The goal is to
select the arm whose mean reward is the closest to the threshold
$\mathfrak{T}$.

  1. 1.

Correct answer:
$\mathcal{I}(\bm{\theta})=I^{*}=\operatorname*{argmin}_{i\in[K]}|\theta_{i}-\mathfrak{T}|$.

  2. 2.

$\mathrm{Alt}(\bm{\theta})=\cup_{j\in\mathcal{X}}\mathrm{Alt}_{j}$, where
$\mathcal{X}=[K]\backslash{I^{*}}$ and
$\mathrm{Alt}_{j}=\\{\bm{\theta}:|\theta_{j}-\mathfrak{T}|<|\theta_{I^{*}}-\mathfrak{T}|\\}$.

  3. 3.

$\bm{\vartheta}=\\{\bm{\vartheta}^{j}:j\in\mathcal{X}\\}$ and

$\bm{\vartheta}^{j}\in\operatorname*{argmin}_{\bm{\theta}^{\prime}\in\\{\bm{\theta}:|\theta_{j}-\mathfrak{T}|<|\theta_{I^{*}}-\mathfrak{T}|\\}}\sum_{k=1}^{K}p_{k}d(\theta_{k},\theta^{\prime}_{k}).$

To solve this minimization problem in closed form, we note that

$\displaystyle\min_{\bm{\theta}^{\prime}\in\\{\bm{\theta}:|\theta_{j}-\mathfrak{T}|<|\theta_{I^{*}}-\mathfrak{T}|\\}}\sum_{k=1}^{K}p_{k}d(\theta_{k},\theta^{\prime}_{k})=\min_{|\theta^{\prime}_{j}-\mathfrak{T}|<|\theta^{\prime}_{I^{*}}-\mathfrak{T}|}p_{I^{*}}d(\theta_{I^{*}},\theta^{\prime}_{I^{*}})+p_{j}d(\theta_{j},\theta^{\prime}_{j}).$

That is to say $\vartheta^{j}_{k}=0$ for $k\neq I^{*},j$. Moreover, at the
minimum,
$|\vartheta^{j}_{j}-\mathfrak{T}|=|\vartheta^{j}_{I^{*}}-\mathfrak{T}|$ holds.
Let $x=\theta^{\prime}_{j}-\mathfrak{T}$. Then the minimization problem
reduces to

$\displaystyle\min_{|\theta^{\prime}_{j}-\mathfrak{T}|<|\theta^{\prime}_{I^{*}}-\mathfrak{T}|}p_{I^{*}}d(\theta_{I^{*}},\theta^{\prime}_{I^{*}})+p_{j}d(\theta_{j},\theta^{\prime}_{j})$
$\displaystyle=\min\left\\{\min_{x}p_{I^{*}}d(\theta_{I^{*}},\mathfrak{T}+x)+p_{j}d(\theta_{j},\mathfrak{T}+x),\min_{x}p_{I^{*}}d(\theta_{I^{*}},\mathfrak{T}-x)+p_{j}d(\theta_{j},\mathfrak{T}+x)\right\\}$
$\displaystyle=\min\Bigg{\\{}p_{I^{*}}d\left(\theta_{I^{*}},\frac{p_{I^{*}}\theta_{I^{*}}+p_{j}\theta_{j}}{p_{I^{*}}+p_{j}}\right)+p_{j}d\left(\theta_{j},\frac{p_{I^{*}}\theta_{I^{*}}+p_{j}\theta_{j}}{p_{I^{*}}+p_{j}}\right),$
$\displaystyle\hskip
40.0ptp_{I^{*}}d\left(\theta_{I^{*}},\frac{\theta_{I^{*}}p_{I^{*}}-\theta_{j}p_{j}+2p_{j}\mathfrak{T}}{p_{I^{*}}+p_{j}}\right)+p_{j}d\left(\theta_{j},\frac{-\theta_{I^{*}}p_{I^{*}}+\theta_{j}p_{j}+2p_{I^{*}}\mathfrak{T}}{p_{I^{*}}+p_{j}}\right)\Bigg{\\}}$
$\displaystyle=\min\left\\{\frac{p_{I^{*}}p_{j}}{p_{I^{*}}+p_{j}}\frac{(\theta_{I^{*}}-\theta_{j})^{2}}{2},\frac{p_{I^{*}}p_{j}}{p_{I^{*}}+p_{j}}\frac{(2\mathfrak{T}-\theta_{I^{*}}-\theta_{j})^{2}}{2}\right\\}$

This implies that, if
$(\theta_{I^{*}}-\theta_{j})^{2}>(2\mathfrak{T}-\theta_{I^{*}}-\theta_{j})^{2}$,
then

$\vartheta^{j}_{I^{*}}=\frac{\theta_{I^{*}}p_{I^{*}}-\theta_{j}p_{j}+2p_{j}\mathfrak{T}}{p_{I^{*}}+p_{j}},\quad\vartheta^{j}_{j}=\frac{-\theta_{I^{*}}p_{I^{*}}+\theta_{j}p_{j}+2p_{I^{*}}\mathfrak{T}}{p_{I^{*}}+p_{j}};$

if
$(\theta_{I^{*}}-\theta_{j})^{2}<(2\mathfrak{T}-\theta_{I^{*}}-\theta_{j})^{2}$,
then

$\vartheta^{j}_{I^{*}}=\vartheta^{j}_{j}=\frac{p_{I^{*}}\theta_{I^{*}}+p_{j}\theta_{j}}{p_{I^{*}}+p_{j}}.$

  4. 4.

$C_{j}(\bm{p})=\sum_{i\in[K]}p_{i}d(\theta_{i},\vartheta^{j}_{i})$ for all
$j\in\mathcal{X}$.

  5. 5.

$\frac{\partial C_{j}}{\partial p_{i}}=d(\theta_{i},\vartheta^{j}_{i})$ for
all $j\in\mathcal{X}$, most of them are zero, except for $i=I^{*}$ and $j$.

####  F.8 All-$\varepsilon$-best

Find all arms with mean larger than $\max_{i}\theta_{i}-\varepsilon$, i.e.,
the set $\mathcal{I}_{\varepsilon}(\bm{\theta})$. See Mason et al. (2020).

  1. 1.

Correct answer:
$\mathcal{I}(\bm{\theta})=\\{i:\theta_{i}\geq\max_{i}\theta_{i}-\varepsilon\\}$.

  2. 2.

$\mathrm{Alt}(\bm{\theta})=\cup_{(i,j)\in\mathcal{X}}\mathrm{Alt}_{i,j}$,
where $\mathcal{X}=\\{(i,j):i\in\mathcal{I},j\neq i\\}$ and
$\mathrm{Alt}_{i,j}=\\{\bm{\theta}^{\prime}:\theta_{j}-\varepsilon>\theta_{i}\\}$.
To interpret, if there exists a $j\neq i$ with
$\theta_{j}-\theta_{i}>\epsilon$, then $i$ must not be in the
$\varepsilon$-best set.

  3. 3.

$C_{i,j}=p_{i}d(\theta_{i},\bar{\theta}_{i,j,\varepsilon}-\varepsilon)+p_{j}d(\theta_{j},\bar{\theta}_{i,j,\varepsilon}),$
where
$\bar{\theta}_{i,j,\varepsilon}=\frac{p_{i}(\theta_{i}+\varepsilon)+p_{j}\theta_{j}}{p_{i}+p_{j}}$.

  4. 4.

The partial derivatives can be derived accordingly.

###  Appendix G Approximate TTTS algorithms and existing algorithms in the
literature

####  G.1 TS-KKT and TS-PPS algorithms

Despite its simplicity, the TTTS algorithm could be computationally
inefficient when the posterior concentrates due to the resampling step. Hence,
we implement two approximate versions of TTTS called TS-PPS (with PPS
referring to Posterior Probability Sampling) and TS-KKT($\rho$) (which takes
$\rho$ as a hyperparameter).

Here we follow and extend the naming convention in Jourdan et al. (2022) for
best-$k$-arm identification. For an algorithm with name
(top_set)-(candidates), (top_set) is a sub-routine calculating the estimated
top-set and (candidates) is a sub-routine proposing the top-two candidates.

Algorithm 9 TS-PPS sub-routine

1:Posterior distribution $\Pi_{t}$.

2:Sample $\tilde{\bm{\theta}}\sim\Pi_{t}$ and define
$\mathcal{I}_{t}=\mathcal{I}(\tilde{\bm{\theta}})$

3:Sample and return
$\left(I_{t}^{(1)},I_{t}^{(2)}\right)=(i,j)\in\mathcal{I}_{t}\times\mathcal{I}_{t}^{c}$
with probability proportional to
$\mathbb{P}_{\tilde{\bm{\theta}}\sim\Pi_{t}}\left(\tilde{\theta}_{j}>\tilde{\theta}_{i}\right)$.

Algorithm 10 TS-KKT($\rho$) sub-routine

1:Posterior distribution $\Pi_{t}$, mean estimator $\bm{\theta}_{t}$, and
hyperparameter $\rho$.

2:Sample $\tilde{\bm{\theta}}\sim\Pi_{t}$ and define
$\mathcal{I}_{t}=\mathcal{I}(\tilde{\bm{\theta}})$

3:Return
$\left(I_{t}^{(1)},I_{t}^{(2)}\right)\in\arg\min_{(i,j)\in\mathcal{I}_{t}\times\mathcal{I}_{t}^{c}}\left(C_{t,i,j}-\frac{\rho}{t}\log(1/N_{t,i}+1/N_{t,j})\right)$.

These two algorithms are closely related to TTTS. Essentially they recover the
complementary-slackness conditions in the asymptotic sense. Given any
$i\in\mathcal{I}_{t}$, for TTTS to sample a different arm
$j\in\mathcal{I}_{t}^{c}$ into $\mathcal{I}_{t}^{\prime}$, we need
$\tilde{\theta}_{j}>\tilde{\theta}_{i}$, which occurs with probability
$\mathbb{P}_{\tilde{\bm{\theta}}\sim\Pi_{t}}\left(\tilde{\theta}_{j}>\tilde{\theta}_{i}\right)$.
This is the motivation behind TS-PPS. We note that
$\mathbb{P}_{\tilde{\bm{\theta}}\sim\Pi_{t}}\left(\tilde{\theta}_{j}>\tilde{\theta}_{i}\right)$
is asymptotically equivalent to $\exp(-tC_{t,i,j})$ by Russo (2020,
Proposition 5). As $t\to\infty$, this becomes a hard minimum in (15a). TS-PPS
samples the top-two candidates proportional to posterior probabilities,
naturally encouraging exploration. The TS-KKT($\rho$) algorithm includes an
additional term to encourage measuring under-sampled pairs of candidates to
reduce the persistent effect of rare events at early stages. The design of
proposing the top-two candidates in TS-KKT($\rho$) is inspired by the
challenger used in TTEI (Qin et al., 2017), and shares a similar spirit with
the Transportation Cost Improved (TCI) challenger proposed in Jourdan et al.
(2022).

####  G.2 Fixed-confidence algorithms

###### KL-LUCB (Kaufmann and Kalyanakrishnan, 2013).

At each round $t$, the algorithm computes the upper confidence bound
$U_{i}(t)$ and lower confidence bound $L_{i}(t)$ of the mean reward for each
arm $i$:

$\displaystyle U_{i}(t)$
$\displaystyle=\max\\{q\in[\theta_{t,i},\infty):T_{t,i}d(\theta_{t,i},q)\leq\beta_{t,\delta}\\},$
(61) $\displaystyle L_{i}(t)$
$\displaystyle=\min\\{q\in(-\infty,\theta_{t,i}]:T_{t,i}d(\theta_{t,i},q)\leq\beta_{t,\delta}\\},$

where $\beta_{t,\delta}$ is the exploration rate we specify to be
$\log\left((\log t+1)/\delta\right)$. Then it samples two critical arms
$u_{t}$ and $l_{t}$:

$u_{t}=\operatorname*{argmax}_{i\notin\widehat{\mathcal{I}}_{t}}U_{i}(t)\quad\text{and}\quad
l_{t}=\operatorname*{argmin}_{i\in\widehat{\mathcal{I}}_{t}}L_{i}(t),$

The algorithm stops when $U_{u_{t}}(t)>L_{l_{t}}(t)$.

###### UGapE (Gabillon et al., 2012).

At each round $t$, the algorithm first compute the same $U_{i}(t)$ and
$L_{i}(t)$ as (61). Then it computes the gap index
$B_{i}(t)=\max_{i^{\prime}\neq i}^{k}U_{i^{\prime}}(t)-L_{i}(t)$ for each arm
$i$, where $\max^{k}$ denotes the operator returning the $k$-th largest value.
Based on $B_{i}(t)$, it evaluates a set of $k$ arms:
$J(t)=\\{j:\operatorname*{argmin}^{j}B_{j}(t)\\}$. From $J(t)$, it computes
two critical arms $u_{t}$ and $l_{t}$:

$u_{t}=\operatorname*{argmax}_{i\notin J_{t}}U_{i}(t)\quad\text{and}\quad
l_{t}=\operatorname*{argmin}_{i\in J_{t}}L_{i}(t),$

and samples one with larger $\beta_{t,\cdot}$. The algorithm stops when
$\max_{i\in J(t)}B_{i}(t)>0$.

######  $m$-LinGapE (Réda et al., 2021a).

At each round $t$, the algorithm first compute the same $U_{i}(t)$ and
$L_{i}(t)$ as (61). Then it computes the gap index
$B_{i,j}(t)=U_{i}(t)-L_{j}(t)$ for each arm $i$. It choose $J(t)$ as the set
of $k$ arms with largest empirical means. From $J(t)$, it computes two
critical arms $u_{t}$ and $l_{t}$:

$u_{t}=\operatorname*{argmax}_{j\in J_{t}}\max_{i\notin
J_{t}}B_{i,j}(t)\quad\text{and}\quad l_{t}=\operatorname*{argmax}_{i\notin
J_{t}}B_{i,u_{t}}(t),$

and samples one which would reduce the variance of the empirical mean
difference between them. (This is so-called "greedy selection rule" in Réda et
al. (2021a).) The algorithm stops when

$B_{l_{t},u_{t}}(t)>0.$

We remark that, in Réda et al. (2021a), the authors introduce a meta algorithm
called “Gap-Index-Focused" Algorithm (GIFA), which includes KL-LUCB, UGapE and
$m$-LinGapE in its framework. Refer to Algorithm 1 and Table 1 in Réda et al.
(2021a).

###### MisLid (Réda et al., 2021b).

The algorithm is designed from the lower bound maximin problem and achieves
the asymptotic optimality. It maintains a learner over the probability simplex
of number of arms. At each round $t$, it computes a gain function and updates
the learner. Then it perform tracking-rule to sample an arm. We adopt AdaHedge
as the learner and use empirical gain function $g_{t}$ as

$\operatorname*{argmin}_{\bm{\lambda}\in\text{Alt}(\bm{\mu}^{t})}\sum_{i=1}^{K}\bm{p}^{t}_{i}(\bm{\mu}^{t}_{i}-\bm{\lambda})^{2}$

where $\bm{p}^{t}$ is probability distribution returned by AdaHedge,
$\bm{\mu}_{t}$ is the empirical mean estimate and $\text{Alt}(\bm{\mu}^{t})$
defines the set of bandit model returning the top-$k$ arm set different from
$(\bm{\mu}^{t})$. As suggested by Réda et al. (2021b), the empirical gain
function reduced the sample complexity practically compared with the
optimistic gain function suggested by theory. For the tracking rule, we adopt
C-Tracking in our experiments. For the stopping rule, we adopt the same
General Likelihood Ratio Test statistic with threshold
$\log\left((\log(t)+1)/\delta\right)$.

###### FWS (Wang et al., 2021).

The algorithm track the lower bound maximin problem. At each round $t$, it
performs forced exploration or Frank-Wolfe update. Due to the non-smoothness
of objective function, it construct an $r_{t}$-sub-differential subspaces and
then solve a zero-sum game. Note $r_{t}$ is a tuning parameter. We choose
$r_{t}=t^{-0.9}/K$ as suggested in Wang et al. (2021). For the stopping rule,
we adopt the same General Likelihood Ratio Test statistic with threshold
$\log\left((\log(t)+1)/\delta\right)$.

###### Lazy-Mirror-Ascent (Ménard, 2019).

The algorithm treats the lower bound problem as

$\max_{\bm{w}}F(\bm{w}).$

It uses a sampling rule based on an online lazy mirror ascent. At each round
$t$, it tracks the allocation weights $\bm{w}(t)$ and updates it by

$\tilde{\bm{w}}(t+1)=\operatorname*{argmax}_{\bm{w}}\eta_{t+1}\sum_{s=K}^{t}\bm{w}\cdot\nabla
F(\tilde{\bm{w}}(s);\bm{\mu}(s))-\text{kl}(\bm{w},\bm{\pi});$
${\bm{w}}(t+1)=(1-\gamma_{t})\tilde{\bm{w}}(t+1)+\gamma_{t}\bm{\pi},$

where $\bm{\mu}(s)$ is the empirical mean estimates and $\bm{\pi}$ is the
uniform distribution. There exists two tuning parameter $\eta_{t}$ and
$\gamma_{t}$. Based on the code released by Wouter M. Koolen
(https://bitbucket.org/wmkoolen/tidnabbil/src/master/) and the suggestion in
Ménard (2019), we choose $\eta_{t}={\sqrt{\log K/t}}/{F^{*}}$ and
$\gamma_{t}=1/(4\sqrt{t})$. Wouter M. Koolen comments that, although setting
$F^{*}$ relies on the knowledge of true arm means, it is critical for the
performance. In appendix of Wang et al. (2021), the authors also comment that
this method is very sensitive to the learning rate $\eta_{t}$, the current
choice is only for experimental comparison and cannot be used in real-world
scenarios.

####  G.3 Fixed-budget algorithms

In the fixed-budget setting, some fixed-confidence algorithms can be adjusted
for use. Meanwhile, another branch of algorithms following the Optimal
Computing Budget Allocation (OCBA) framework is popular in the simulation
optimization community. We review some of them below.

###### UGapE (Gabillon et al., 2012).

The UGapE provide a variant running in the fixed-budget setting. At each round
$t$, the algorithm also identifies the arm with largest gap index
$B_{i}(t)=\max_{i^{\prime}\neq i}^{k}U_{i^{\prime}}(t)-L_{i}(t)$. In the
fixed-budget setting, $U_{i}(t)$ and $L_{i}(t)$ are defined by

$U_{i}(t)=\theta_{t,i}+\sqrt{\frac{a\times\texttt{budget}}{4HN_{t,i}}},\quad
L_{i}(t)=\theta_{t,i}-\sqrt{\frac{a\times\texttt{budget}}{4HN_{t,i}}}.$ (62)

A tuning parameter $a$ for exploration is needed. Furthermore, the algorithm
needs to estimate the sample complexity $H$ of the problem, which is defined
by $H=\left(\sum_{i=1}^{K}\frac{1}{\Delta_{i}}\right)$ where the gap
$\Delta_{i}$ for each arm is defined as

$\Delta_{i}=\begin{cases}\theta_{i}-\theta_{k+1}\hskip 10.0pt\text{if $i\leq
k$,}\\\ \theta_{k}-\theta_{i}\hskip 20.0pt\text{if $i>k$.}\end{cases}$

In our implementation, we give advantage to UGapE by hand-selecting the best
problem-dependent tuning parameter and pass-through the true sample complexity
$H$, both of which are unknown beforehand.

###### SAR (Bubeck et al., 2013).

The SAR maintains an active set $\mathcal{A}$ and a selected set
$\mathcal{S}$, which are initialized to be $\mathcal{A}=[K]$ and
$\mathcal{S}=\emptyset$ . The time horizon (budget) $T$ is divided into $K-1$
phases. At the beginning, the algorithm computes the following quantities:

$\overline{\log}(K)=\frac{1}{2}+\sum_{i=2}^{K}\frac{1}{i},\ n_{0}=0,\
\text{and}\
n_{p}=\left\lceil{\frac{1}{\overline{\log}(K)}\frac{T-K}{K+1-p}}\right\rceil\text{
for $p$ in $1,\cdots,K-1$}.$

At each phase $p$, the algorithm samples each active arm $i\in\mathcal{A}$ for
$n_{p}-n_{p-1}$ times. Sort the arms in $\mathcal{A}$ in descending order, say
$\theta_{t,1}\geq\theta_{t,2}\geq\cdots$. Define the following empirical gap

$\widehat{\Delta}_{i}=\begin{cases}\theta_{t,i}-\theta_{t,k-|S|+1}\hskip
10.0pt\text{if $i\leq k-|\mathcal{S}|$,}\\\
\theta_{t,k-|S|}-\theta_{t,i}\hskip 20.0pt\text{if
$i>k-|\mathcal{S}|$.}\end{cases}$

Let $i_{p}=\operatorname*{argmax}\widehat{\Delta}_{i}$ and
$\mathcal{A}=\mathcal{A}\backslash\\{i_{p}\\}$. If
$\theta_{t,i_{p}}>\theta_{t,k-|\mathcal{S}|+1}$, then
$\mathcal{S}=\mathcal{S}\cup\\{i_{p}\\}$.

###### OCBAss (Gao and Chen, 2015).

For the Gaussian bandits with equal known variance, OCBAss can be described as
follows. At the beginning, the algorithm samples each arm for $\Delta_{0}$
times. Then at time $t$, for all $i\in{\mathcal{I}}_{t}$ and
$j\notin{\mathcal{I}}_{t}$, the algorithm compute $C_{i,j}$ defined as
follows:

$C_{i,j}=\frac{N_{t,i}}{t}d\left(\theta_{t,i},\frac{N_{t,i}\theta_{t,i}+N_{t,j}\theta_{t,j}}{N_{t,i}+N_{t,j}}\right)+\frac{N_{t,j}}{t}d\left(\theta_{t,j},\frac{N_{t,i}\theta_{t,i}+N_{t,j}\theta_{t,j}}{N_{t,i}+N_{t,j}}\right).$
(63)

Then it identifies the $(i_{t},j_{t})$-pair that minimizes $C_{i,j}$ as
candidate arms. If
$\sum_{i\in{\mathcal{I}}_{t}}N_{t,i}^{2}<\sum_{j\notin{\mathcal{I}}_{t}}N_{t,j}^{2}$,
then sample $i_{t}$ for $n$ times. Otherwise, sample $j_{t}$ for $n$ times. In
the experiment, we choose the parameter $\Delta_{0}=n=10$ suggested by Gao and
Chen (2015).

At first glance, the OCBAss algorithm appears very similar to the TS-KKT(0)
algorithm, as they both identify the $(i,j)$-pair that minimizes $C_{i,j}$ as
candidate arms. However, there is a key difference between them: when choosing
from the $(i,j)$-pair, OCBAss balances the sum-of-squared allocation from the
entire bipartite graph, while TS-KKT tries to balance the sum-of-squared
allocation in each and every connected subgraph. Despite this difference,
OCBAss still demonstrates impressive empirical performance and is optimal at
least for a large problem instance. It is also worth noting that OCBAss
discovered this sum-of-squared allocation structure some time ago, earlier
than the BAI paper (Garivier and Kaufmann, 2016).

###### OCBASS (Gao and Chen, 2016).

At the beginning, the algorithm samples each arm for $\Delta_{0}$ times. Then
at time $t$, the algorithm compute $C_{i,j}$ defined by (63). Then it
identifies the $(i_{t},j_{t})$-pair that minimizes $C_{i,j}$ as candidate
arms. Choose $i_{t}$ or $j_{t}$ arbitrarily and sample it for $n$ times. In
the experiment, we choose the parameter $\Delta_{0}=n=10$ suggested by Gao and
Chen (2016).

The OCBASS algorithm is very similar to the OCBA-ss algorithm. In particular,
they both identify the $(i,j)$-pair that minimizes $C_{i,j}$ as candidate
arms. In each iteration of the algorithm, there will be multiple arms that
achieves the minimum value of $C_{i,j}$. However, the important step of
balancing sum-of-squared allocation is missing, which implies that OCBASS
cannot be optimal.

###  Appendix H Miscellaneous results and proofs

####  H.1 Facts about the exponential family

We restrict our attention to reward distribution following an one-dimensional
natural exponential family. In particular, a natural exponential family has
identity natural statistic in canonical form, i.e.,

$p(y|\eta)=b(y)\exp\\{\eta
y-A(\eta)\\},\quad\eta\in\mathcal{T}=\left\\{\eta:\int b(y)e^{\eta
y}\mathrm{d}y<\infty\right\\}$ (64)

where $\eta$ is the natural parameter and $A(\eta)$ is assumed to be twice
differentiable. The distribution is called non-singular if
$\text{Var}_{\eta}(Y_{t,i})>0$ for all $\eta\in\mathcal{T}^{o}$, where
$\mathcal{T}^{o}$ denotes the interior of the parameter space $\mathcal{T}$.
Denote by $\theta$ the mean reward $\theta(\eta)=\int yp(y|\eta)dy$. By the
properties of the exponential family, we have, for any
$\eta\in\mathcal{T}^{o}$,

$\theta(\eta)=\mathbb{E}_{\eta}[Y_{t,i}]=A^{\prime}(\eta),\quad\text{and}\quad
A^{\prime\prime}(\eta)=\text{Var}_{\eta}(Y_{t,i})>0.$

We immediately have the following lemma.

######  Lemma 18.

At any $\eta\in\mathcal{T}^{o}$, $\theta(\eta)$ is strictly increasing and
$A(\eta)$ is strictly convex.

Lemma 18 implies that $\theta(\cdot)$ is a one-to-one mapping. Consequently,
we can use $\theta$ to denote the distribution $p(\cdot|\eta)$ for
convenience. Let $\theta_{1}$ and $\theta_{2}$ be the mean reward of the
distribution $p(\cdot|\eta_{1})$ and $p(\cdot|\eta_{2})$. Denote by
$d(\theta_{1},\theta_{2})$ the Kullback–Leibler (KL) divergence from
$p(\cdot|\eta_{1})$ to $p(\cdot|\eta_{2})$. We have convenient closed-form
expressions of $d(\cdot,\cdot)$ and its partial derivative.

######  Lemma 19.

The partial derivatives of the KL divergense of a one-dimensional natural
exponential family satisfies

$d(\theta_{1},\theta_{2})=A(\eta_{2})-A(\eta_{1})-\theta_{1}(\eta_{2}-\eta_{1}),$
(65) $\frac{\partial
d(\theta_{1},\theta_{2})}{\partial\theta_{1}}=\eta_{1}-\eta_{2},\quad\frac{\partial
d(\theta_{1},\theta_{2})}{\partial\theta_{2}}=(\theta_{2}-\theta_{1})\frac{\mathrm{d}\eta(\theta_{2})}{\mathrm{d}\theta_{2}}.$
(66)

####  H.2 Properties of $C_{i,j}(\cdot)$

In this section, we provide useful properties of the functions $C_{j}$ for BAI
and the functions $C_{i,j}$ for best-$k$-arm identification.

First note that $C_{j}$ for BAI is equivalent to $C_{I^{*},j}$ for
best-$k$-arm identification, where $I^{*}$ is the best arm. To avoid
repetition, we consider only the functions $C_{i,j}$ for best-$k$-arm
identification.

######  Lemma 20.

For any $(i,j)\in\mathcal{I}\times\mathcal{I}^{c}$, $C_{i,j}(\bm{p})$ is
concave in $\bm{p}$, strictly increasing in $p_{i}$ and $p_{j}$, and

$\frac{\partial C_{i,j}(\bm{p})}{\partial
p_{i}}=d(\theta_{i},\bar{\theta}_{i,j})\quad\text{and}\quad\frac{\partial
C_{i,j}(\bm{p})}{\partial p_{j}}=d(\theta_{j},\bar{\theta}_{i,j})$

where
$\bar{\theta}_{i,j}=\bar{\theta}_{i,j}(\bm{p})=\frac{p_{i}\theta_{i}+p_{j}\theta_{j}}{p_{i}+p_{j}}.$

###### Proof.

To see the concavity of $C_{i,j}(\bm{p})$, note that
$C_{i,j}(\bm{p})=\inf_{\tilde{\theta}}\left\\{p_{i}d(\theta_{i},\tilde{\theta})+p_{j}d(\theta_{j},\tilde{\theta})\right\\}$,
which is the minimum over a family of linear functions in $\bm{p}$. This
directly implies that $C_{i,j}(\bm{p})$ is concave in $\bm{p}$; see Boyd and
Vandenberghe (2004, Chapter 3.2)).

By Lemma 19 and the definition of $C_{i,j}$ in (48), the partial derivatives
are derived as follows

$\displaystyle\frac{\partial C_{i,j}(\bm{p})}{\partial p_{i}}$
$\displaystyle=d(\theta_{i},\bar{\theta}_{i,j})+p_{i}\frac{\partial
d(\theta_{i},\bar{\theta})}{\partial p_{i}}+p_{j}\frac{\partial
d(\theta_{j},\bar{\theta})}{\partial p_{i}}$
$\displaystyle=d(\theta_{i},\bar{\theta}_{i,j})+\frac{\partial\bar{\theta}}{\partial
p_{i}}\cdot\left[p_{i}\frac{\partial
d(\theta_{i},\bar{\theta})}{\partial\bar{\theta}}+p_{j}\frac{\partial
d(\theta_{j},\bar{\theta})}{\partial\bar{\theta}}\right]$
$\displaystyle=d(\theta_{i},\bar{\theta}_{i,j}).$

The last equality comes from the first-order optimality condition for solving
the convex optimization problem in the third line of (48). The calculation of
$\frac{\partial C_{i,j}(\bm{p})}{\partial p_{j}}$ follows similarly. ∎

######  Lemma 21.

For any $(i,j)\in\mathcal{I}\times\mathcal{I}^{c}$, the contour of
$C_{i,j}(\cdot)$ as a bivariate function of $(p_{i},p_{j})$ does not contain
any line segment.

###### Proof.

To prove the result, we need to basic facts.

  1. 1.

We first give the Hessian matrix of $C_{i,j}(\bm{p})$ as follows

$H_{i,j}=\begin{bmatrix}\frac{\partial^{2}C_{i,j}(\bm{p})}{\partial^{2}p_{i}}&\frac{\partial^{2}C_{i,j}(\bm{p})}{\partial
p_{i}\partial p_{j}}\\\ \frac{\partial^{2}C_{i,j}(\bm{p})}{\partial
p_{j}\partial
p_{i}}&\frac{\partial^{2}C_{i,j}(\bm{p})}{\partial^{2}p_{j}}\end{bmatrix}=\frac{(\theta_{i}-\theta_{j})^{2}}{(p_{i}+p_{j})^{3}}\frac{\mathrm{d}\eta(\bar{\theta}_{i,j})}{\mathrm{d}\theta}\begin{bmatrix}-p_{j}^{2}&p_{i}p_{j}\\\
p_{i}p_{j}&-p_{i}^{2}\end{bmatrix},$

where $\eta$ is the natural parameter of the exponential family. By Lemma 18,
$\frac{\mathrm{d}\eta(\bar{\theta})}{\mathrm{d}\theta}$ is strictly positive.
Note that $H_{i,j}$ has an eigenvalue $0$. The other eigenvalue can be
calculated correspondingly,

$\lambda_{\min}(H_{i,j})=-\frac{p_{i}^{2}+p_{j}^{2}}{(p_{i}+p_{j})^{3}}\frac{\mathrm{d}\eta(\bar{\theta}_{i,j})}{\mathrm{d}\theta}(\theta_{i}-\theta_{j})^{2}.$

Note that $\lambda_{\min}(H_{i,j})<0$ whenever $p_{i}$ or $p_{j}$ is greater
than $0$.

  2. 2.

Recall that $C_{i,j}$ satisfies the partial differential equation in (7),
which has a general solution in the form of

$C_{i,j}(\bm{p})=p_{i}g_{i,j}\left(\frac{p_{j}}{p_{i}}\right),$

where $g_{i,j}(\cdot)$ is any differentiable function. This implies that the
graph of $C_{i,j}(\bm{p})$ is the boundary of a cone. The graph of a function
$f(x)$ is defined as $G(f)=\\{(x,f(x)):x\in D\\}$, where $D$ is the domain of
$f(x)$. In particular, for any point on the surface, the line segment
connecting the point and the origin belongs to the graph of $C_{i,j}(\bm{p})$.

We prove the result by contradiction. Suppose that there exist a line segment
in the contour of $C_{i,j}(p_{i},p_{j})$. Then the triangle specified by the
two end points of the line segment and the origin belongs to the graph of
$C_{i,j}$. This implies that at any point in the interior of this triangle,
$C_{i,j}$ has a Hessian of $\bm{0}$. This contradicts with the fact that the
Hessian of $C_{i,j}$ at any point $(p_{i},p_{j})$ such that $p_{i}$ or $p_{j}$
is greater than $0$ is semi-negative definite, with a eigenvalue strictly
smaller than $0$. ∎

######  Lemma 22.

For any $(i,j)\in\mathcal{I}\times\mathcal{I}^{c}$, $C_{i,j}(\bm{p})$ can be
written as

$C_{i,j}(\bm{p})=p_{i}g_{i,j}\left(\frac{p_{j}}{p_{i}}\right),$

where

$g_{i,j}(x)=d\left(\theta_{i},\frac{\theta_{i}+x\theta_{j}}{1+x}\right)+xd\left(\theta_{j},\frac{\theta_{i}+x\theta_{j}}{1+x}\right).$

Furthermore, we have

$g^{\prime}_{i,j}(x)=d\left(\theta_{j},\frac{\theta_{i}+x\theta_{j}}{1+x}\right)>0.$

Moreover, for any $i,j$ and $j^{\prime}$ such that
$\theta_{i}>\theta_{j^{\prime}}\geq\theta_{j}$, we have

$g_{i,j}(x)\geq g_{i,j^{\prime}}(x)\quad\text{for all }x.$

###### Proof.

We start by identifying that

$C_{i,j}(p_{i},p_{j})=p_{i}g_{i,j}\left(\frac{p_{j}}{p_{i}}\right).$

Fix $p_{i}$ and let $x=\frac{p_{j}}{p_{i}}$,

$\frac{\partial C_{i,j}}{\partial
p_{j}}=p_{i}g_{i,j}^{\prime}(x)\frac{\partial x}{\partial
p_{j}}=g_{i,j}^{\prime}(x).$

By Lemma 20, we have

$\frac{\partial C_{i,j}}{\partial
p_{j}}=d\left(\theta_{j},\frac{p_{i}\theta_{i}+p_{j}\theta_{j}}{p_{i}+p_{j}}\right)=d\left(\theta_{j},\frac{\theta_{i}+x\theta_{j}}{1+x}\right).$

Hence,

$g_{i,j}^{\prime}(x)=d\left(\theta_{j},\frac{\theta_{i}+x\theta_{j}}{1+x}\right)>0.$

To this end, we fix $\theta_{i}$ and $x$ and define

$h(\alpha)=d\left(\theta_{i},\frac{\theta_{i}+x\alpha}{1+x}\right)+xd\left(\alpha,\frac{\theta_{i}+x\alpha}{1+x}\right).$

It follows that $h(\theta_{j})=g_{i,j}(x)$. To complete the proof, we need to
show that, for any $\theta_{i}>\theta_{j^{\prime}}\geq\theta_{j}$,
$g_{i,j}(x)\geq g_{i,j^{\prime}}(x)$. It suffices to verify that
$h^{\prime}(\alpha)<0$ when $\theta_{i}>\alpha$. To see this, let

$m=\frac{\theta_{i}+x\alpha}{1+x}.$

We recall the partial derivative of $d(\cdot,\cdot)$ in (66) and calculate
$h^{\prime}(\alpha)$ as follows.

$\displaystyle h^{\prime}(\alpha)$ $\displaystyle=\frac{\partial
d(\theta_{i},m)}{\partial m}\frac{x}{1+x}+x\left[\frac{\partial
d(\alpha,m)}{\partial\alpha}+\frac{\partial d(\alpha,m)}{\partial
m}\frac{x}{1+x}\right]$
$\displaystyle=(m-\theta_{i})\frac{\mathrm{d}\eta}{\mathrm{d}m}\frac{x}{1+x}+x\left[\eta(\alpha)-\eta(m)+(m-\alpha)\frac{\mathrm{d}\eta}{\mathrm{d}m}\frac{x}{1+x}\right]$
$\displaystyle=x(\eta(\alpha)-\eta(m))+((m-\theta_{i})+x(m-\alpha))\frac{\mathrm{d}\eta}{\mathrm{d}m}\frac{x}{1+x}$
$\displaystyle=x(\eta(\alpha)-\eta(m)).$

Noticing that $\eta^{\prime}(\theta)=1/\theta^{\prime}(\eta)>0$ and
$m-\alpha=(\theta_{i}-\alpha)/(1+x)$, we have

$h^{\prime}(\alpha)\begin{cases}<0,\quad\text{if }\theta_{i}>\alpha,\\\
>0,\quad\text{if }\theta_{i}<\alpha.\end{cases}$ (67)

This completes the proof. ∎

####  H.3 Proof of Lemma 1

###### Proof.

When the reward distribution follows a single-parameter exponential family,
the KL divergence $d(m,m^{\prime})$ is continuous in $(m,m^{\prime})$ and
strictly convex in $m^{\prime}$. A direct application of Wang et al. (2021,
Theorem 4 and Lemma 7) leads to a unique $\vartheta$ that achieves the infimum
in (19), and the differentiability and concavity of $C_{x}$.

We say that a function $f$ is homogeneous of degree one if it satisfies
$f(s\bm{p})=sf(\bm{p})$ for any $s\geq 0$. Then, the fact that $C_{x}(\bm{p})$
is homogeneous of degree one follows directly from its definition in (19). The
PDE characterization follows Euler’s theorem for homogeneous functions, for
example, in (Apostol, 1969, p. 287). ∎

####  H.4 Proof of Corollary 1

Assuming strictly positiveness of $\bm{\ }p^{*}$, recall from (44b) that

$\lambda-\sum_{x\in\mathcal{X}}\mu_{x}\frac{\partial C_{x}(\bm{p})}{\partial
p_{i}}=0,\quad\forall i\in[K],$

where we used the fact that $\iota_{i}=0$ due to complementary slackness. By
the definition of

$\mathcal{X}_{i}\triangleq\\{x\in\mathcal{X}:i\in\mathfrak{C}_{x}\\},$

we have

$\displaystyle\lambda-\sum_{x\in\mathcal{X}_{i}}\mu_{x}\frac{\partial
C_{x}(\bm{p})}{\partial p_{i}}=0,\quad\forall i\in[K].$ (68)

Notice that $\lambda=\phi=\Gamma^{*}_{\bm{\theta}}>0$ from the proof of
Theorem 3 and that $\frac{\partial C_{x}(\bm{p})}{\partial p_{i}}>0$, there
must exist a $x_{0}\in\mathcal{X}_{i}$ such that $\mu_{x}>0$. The
complementary-slackness condition then implies that
$C_{x_{0}}(\bm{p}^{*})=\phi=\Gamma^{*}_{\bm{\theta}}$. Consequently,

$\Gamma_{\bm{\theta}}^{*}=\min_{x\in\mathcal{X}_{i}}C_{x}(\bm{p}^{*}),\quad\hbox{for
all }i\in[K].$