# Best arm identification in rare events

Anirban Bhattacharjee
School of Technology and Computer Science
Tata Institute of Fundamental Research
Mumbai, India
<EMAIL_ADDRESS>&Sushant Vijayan
School of Technology and Computer Science
Tata Institute of Fundamental Research
Mumbai, India
<EMAIL_ADDRESS>
&Sandeep K Juneja
School of Technology and Computer Science
Tata Institute of Fundamental Research
Mumbai, India
<EMAIL_ADDRESS>

###### Abstract

We consider the best arm identification problem in the stochastic multi-armed
bandit framework where each arm has a tiny probability of realizing large
rewards while with overwhelming probability the reward is zero. A key
application of this framework is in online advertising where click rates of
advertisements could be a fraction of a single percent and final conversion to
sales, while highly profitable, may again be a small fraction of the click
rates. Lately, algorithms for BAI problems have been developed that minimise
sample complexity while providing statistical guarantees on the correct arm
selection. As we observe, these algorithms can be computationally prohibitive.
We exploit the fact that the reward process for each arm is well approximated
by a Compound Poisson process to arrive at algorithms that are faster, with a
small increase in sample complexity. We analyze the problem in an asymptotic
regime as rarity of reward occurrence reduces to zero, and reward amounts
increase to infinity. This helps illustrate the benefits of the proposed
algorithm. It also sheds light on the underlying structure of the optimal BAI
algorithms in the rare event setting.

##  1 Introduction

Online advertising is ubiquitous in present times, and is used by e-commerce
platforms, mobile application developers, marketing professionals etc.
Typically, an online advertiser has to decide amongst various product
advertisements and choose the one with highest expected reward. Advertisers
typically have a period of experimentation where they sequentially show
competing advertisements to the users to arrive at advertisements that elicit
best response from each customer type (customers maybe clustered based on
available information).

A key feature of online advertising is that while each advertisement maybe
shown to a large number of customers, the click rates on advertisements are
usually small. Typically, these maybe of order one in a thousand
111https://cxl.com/guides/click-through-rate/benchmarks/, and a very small
percentage 222https://localiq.com/blog/search-advertising-benchmarks/. of the
users who click on an advertisement end up buying the product (known as the
conversion rate). The conversion and click rates can vary significantly
depending on the product category. For example, high-end products often have
higher click rates but much lower conversion rates compared to standard
products. Thus, a key characteristic of the problem is that rarer conversion
rates often have very high rewards.

We study the problem of identifying the best advertisement to show to a
customer type as a best arm identification (BAI) problem in the multi-armed
bandit framework. The rarity of the reward probabilities, and the fact
advertisements are shown to a large number of customers, may make the
computational effort of popular existing adaptive algorithms prohibitive. On
the other hand, these properties call for sensible aggregation based
algorithms. In this paper, we observe that the rewards from large number of
pulls from each arm can be well modelled as a Compound Poisson process,
significantly simplifying and speeding up the existing optimal algorithms.

To illustrate the proposed ideas clearly, we consider a simple stochastic BAI
problem where agent is given a set of $K$ unknown probability distributions
(arms) that can be sampled sequentially. The agent’s objective is to declare
the arm with the highest mean with a pre-specified confidence level
$1-\delta$, while minimizing the expected number of samples (sampling
complexity). In the literature, this is popularly known as the fixed-
confidence setting, and the algorithms that provide $1-\delta$ confidence
guarantees are referred to as $\delta$-correct.

Best arm identification problems are also popular in simulation community
where these are better known as ranking and selection problems (for example
see Goldsman, (1983); Chan and Lai, (2006)). Classical problem involves many
complex simulation models of practical systems such as supply chain design,
traffic network and so on, and the aim is to identify with high probability,
the system with the highest expected reward, using minimum computational
budget. In many systems, the performance measure of interest may correspond to
a rare event, e.g., a manufacturing plant shut down probability, or computer
system unavailability fraction. The algorithms that we propose here are also
applicable in optimal computational resource allocation in simulating such
systems.

Related literature: In the learning theory literature, Even-Dar et al., (2006)
were amongst the first to consider the fixed confidence BAI problem. They
proposed a successive elimination algorithm (see section F of supplementary
material). Upper Confidence Bound (UCB) based algorithms were proposed in Auer
et al., (2002); Jamieson et al., (2014), wherein the arm with highest
confidence index is sampled. These algorithms usually stop when the difference
between arm indices breaches a certain threshold (see Jamieson and Nowak,
(2014) for more details). Sample complexity of these algorithms was shown to
match the lower bound within a constant. Motivated by Bayesian approaches in
Russo, (2016), Jourdan et al., (2022) proposes top-two algorithms that propose
a challenger to the current empirical best arm and sample between the
challenger and the empirical best arm with a pre-defined probability $\beta$.
Although these algorithms are $\beta$-optimal 333see Jourdan et al., (2022)
for definition they are not known to be asymptotically optimal in the sense
defined in Garivier and Kaufmann, (2016). The sample complexity of these
algorithms is typically analyzed in an asymptotic regime where
$\delta\rightarrow 0$. Garivier and Kaufmann, (2016) and Kaufmann et al.,
(2016) derived a more general lower bound (as a maxmin formulation) on the
sample complexity. Based on this lower bound a Track-and-Stop algorithm (TS)
was proposed for arm distributions restricted to single parameter exponential
families (SPEF), and was shown to match the lower bound even to a constant (as
$\delta\to 0$).Agrawal et al., (2019, 2020) extended the TS algorithms to more
general distributions. The optimal TS algorithms in the literature, proceed
iteratively. At each iteration, the observed empirical parameters are plugged
into the lower bound max-min problem to arrive at prescriptive optimal sample
allocations to each arm, that then guide the sample allocations. As is known,
and as we observe, these algorithms are computationally prohibitive,
especially since in our rare advertising settings, the informative non-zero
reward samples (those instances where users buy products) are rare. This
motivates the paper’s goal to arrive at computationally efficient algorithms
that exploit the Compound Poisson structure of the arm reward process, with a
small increase in sample complexity.

Contributions: We develop a rarity framework where the reward success
probabilities are modelled as a function of $\gamma^{\alpha}$ for arm
dependent $\alpha>0$ and $\gamma$ is $>0$ and small. The rewards are modelled
to be of order $\gamma^{-\alpha}$ so that the expected rewards across arms are
comparable (otherwise, we a-priori know arms with small or large expected
rewards). We assume that arm specific upper bounds on rewards are available to
us. In this framework, we propose a computationally efficient $\delta$-correct
algorithm that is nearly asymptotically optimal for small $\gamma$. This
algorithm (Approximate Track and Stop) is based on existing track and stop
algorithms that are simplified through a Compound Poisson approximation to the
bandit reward process. The Poisson approximation can be seen to be tight as
$\gamma\rightarrow 0$ and we provide bounds on the deviations due to Poisson
approximation. Further, we give an asymptotically valid upper bound on the
sample complexity illustrating that the increase in sample complexity is
marginal compared to the computational benefit. The rarity structure helps us
shed further light on the optimal sample allocations across arms in our BAI
problem. We identify five different regimes depending on the rarity
differences between the arms. Finally, we compare experimentally with the TS
algorithm in Agrawal et al., (2020) for bounded random rewards. We find that
for realistic rare event probabilities and reward structure, our algorithm is
6-12 times faster than the TS algorithm with a small increase (1-13 %) in
sample complexity.

The rest of the paper is organized as follows: Section 2 formally introduces
the problem, rare event setting and provides some background material. Section
3 introduces the approximate problem, analyzes its deviations from the exact
problem and gives the optimal weight asymptotics, Section 4 outlines the
details of the Approximate Track and Stop (TS(A)) algorithm,
$\delta$-correctness, sample complexity guarantee and computational benefits
of the algorithm. Section 5 presents some experimental results and we conclude
in Section 6. The proofs of various results and further technical details are
furnished in the supplementary material.

##  2 Modelling Framework

Consider a $K$-armed bandit with each arm’s distribution denoted by $p_{i}$,
$i\in[K]$. We denote such a bandit instance by $p$. For any distribution
$\eta$, let $\mu(\eta)$ denote its mean and $\textrm{supp}(\eta)$ denote its
support. Further, let
$KL(\eta,\kappa)=\mathbb{E}_{\eta}\log\left(\frac{d\eta}{d\kappa}\right)$
denote the Kullback-Leibler divergence between two measures $\eta$ and
$\kappa$, where $E_{\eta}$ denotes the expectation operator under $\eta$. We
assume that $\textrm{supp}(p_{i})$ is finite for each $i$. Further, this set
may not be known to the agent. However, there is a lower bound 0 and an upper
bound $B_{i}$ for $\textrm{supp}(p_{i})$ and that is known to the agent. The
agent’s goal is to sequentially sample from these arms using a policy that at
any sequential step $t$, may depend upon all the generated data before time
$t$. The policy then stops at a random stopping time and declares an arm that
it considers to have the highest mean. A sampling strategy, a stopping rule
and a recommendation rule are together called a best arm bandit algorithm. A
best arm bandit algorithm that correctly recommends the arm with the highest
mean with probability at least $1-\delta$ (for a pre-specified
$\delta\in(0,1)$) is said to be $\delta$-correct.

This BAI problem has been well studied, and lower bounds on sample complexity
under $\delta$-correct algorithms have been developed along with algorithms
that match the lower bound asymptotically as $\delta\rightarrow 0$. Below, we
first state the lower bound in Theorem 2, and then briefly outline an
algorithm that asymptotically matches it. The lower bounds were developed by
Garivier and Kaufmann, (2016)) for single parameter exponential family of
distributions and were generalized to bounded and heavy-tailed distributions
by Agrawal et al., (2020). Let

$\mathcal{K}^{L,B}_{inf}(\eta,x)\coloneqq\min_{\begin{subarray}{c}\textrm{supp}(\kappa)\subseteq[0,B]\\\
\mu_{\kappa}\leq x\end{subarray}}KL(\eta,\kappa)$ (1)

$\mathcal{K}^{U,B}_{inf}(\eta,x)\coloneqq\min_{\begin{subarray}{c}\textrm{supp}(\kappa)\subseteq[0,B]\\\
\mu_{\kappa}\geq x\end{subarray}}KL(\eta,\kappa).$ (2)

Henceforth, we suppress the dependence on $B$ above to ease the presentation.
This should not cause confusion in the following discussion. For brevity,
we’ll denote $\mu_{p_{i}}$ by $\mu_{i}$ for each $i\in[K]$. As is customary in
the BAI literature, we assume that best arm is unique and without loss of
generality, $\mu_{1}>\mu_{i}$ for $i\in[K]\backslash\\{1\\}$.

  * Theorem5 in Agrawal et al., (2020).

For our bandit problem, any $\delta$-correct algorithm with stopping rule
$\tau_{\delta}$, satisfies

$\mathbb{E}[\tau_{\delta}]\geq\frac{1}{V^{*}(p)}\log\Big{(}\frac{1}{2.4\delta}\Big{)},$

where $V^{*}(p)$ equals

$\max_{w\in\Sigma_{K}}\min_{i\neq
1}\inf_{x\in[\mu_{i},\mu_{1}]}w_{1}\mathcal{K}^{L}_{inf}(p_{1},x)+w_{i}\mathcal{K}^{U}_{inf}(p_{i},x),$
(3)

$\Sigma_{K}$ being the $K$-dimensional probability simplex.

Optimal track and stop (TS) algorithms in the literature that match the lower
bound asymptotically as $\delta\rightarrow 0$ briefly involve the following
features (see, Garivier and Kaufmann, (2016), Agrawal et al., (2020), Agrawal
et al., (2021) for details and justification of such track and stop
algorithms. We also discuss existing algorithms further in Section F of
supplementary material.)

  1. 1.

Arms are sampled sequentially in batches. At stage $t$, each arm is sampled at
least order $\sqrt{t}$ times (this sub linear exploration ensures that no arm
is starved).

  2. 2.

Empirical distributions $\hat{p}_{t}$ are plugged into the lower bound that is
solved to determine the prescriptive proportions $\hat{w}_{t}$.

  3. 3.

The algorithm then samples to closely track these proportions.

  4. 4.

The algorithm stops when the log-likelihood ratio at stage $m$ exceeds a
threshold $\beta(m,\delta)$ (set close to $\log(1/\delta)$). At stage $m$, the
log likelihood ratio equals

$\displaystyle\underset{b\neq k^{*}}{\min}\underset{x\leq y}{\inf}$
$\displaystyle
N_{k^{*}}(m)\mathcal{K}_{inf}^{L}(\hat{p}_{k^{*}}(m),x)+N_{b}(m)\mathcal{K}_{inf}^{U}(\hat{p}_{b}(m),y),$

where $k^{*}$ denotes the arm with the largest sample mean, each $N_{a}(m)$
denotes the samples of arm $a$ amongst $m$ samples.

As is apparent, the above algorithm involves repeatedly solving the lower
bound problem, and this is computationally demanding, particularly when
nonzero rewards are rare and occur with very low probabilities.

###  2.1 The Rare Event Setting

We now specialize the BAI setting to illustrate our rare event framework where
the rewards from each arm take positive values with small probabilities.
Further, while the expected rewards across arms are of the same order, the
realized rewards and the associated probabilities may be substantially
different.

Concretely, suppose that $\gamma$ is a small positive value (say of order
$10^{-2}$ or lower) and corresponding to each arm distribution $p_{i}$, we
have a rarity index $\alpha_{i}>0$. The support of arm $i$ takes values
$a_{ij}\gamma^{-\alpha_{i}}$, each with probability
$p_{ij}\gamma^{\alpha_{i}}>0$ for $j\leq n_{i}<\infty$. Under each $p_{i}$,
the realized reward takes value zero with probability close to 1. To
summarize,

$\displaystyle\mathbb{P}_{X\sim
p_{i}}(X=a_{ij}\gamma^{-\alpha_{i}})=p_{ij}\gamma^{\alpha_{i}},\ j\in[n_{i}]$
$\displaystyle\mathbb{P}_{X\sim
p_{i}}(X=0)=1-\sum_{j}p_{ij}\gamma^{\alpha_{i}}.$

The arm means are given by $\mu_{i}=\sum_{j}a_{ij}p_{ij}$ and are independent
of $\gamma$. We further assume that an upper bound $B_{i}\gamma^{-\alpha_{i}}$
for each arm $i$ is known to the agent.

The above rarity framework brings out the benefits of the proposed
approximations cleanly for small $\gamma$ in our theoretical analysis.
However, in executing the associated algorithm, we don’t need to separately
know the values of $\gamma$ and each $\alpha_{i}$.

###  2.2 The Poisson Approximation of KL Divergence

We motivate in this section the approximate form of KL divergence that we
shall use. The following well-known result, shown in section A.5 of the
supplementary material for completeness, is used to motivate our
approximation.

  * Proposition1.

Let $\tau^{(1)}_{ij}$ denote the minimum number of samples of arm $i$ needed
to see the reward $a_{ij}\gamma^{-\alpha_{i}}$, i.e. the first arrival time of
the support point $j$. Similarly, let $\tau^{(k)}_{ij}$ be the $k$-th arrival
time of support point $j$,

Let $N_{ij}(t)$ be the number of times the reward $a_{ij}\gamma^{-\alpha_{i}}$
is returned by arm $i$ in $\lceil t\gamma^{-\alpha_{i}}\rceil$ trials
($t\in\mathbb{R}$). Then as $\gamma\to 0$,

    1. (a)

$\mathbb{P}(\tau^{(k)}_{ij}>t\gamma^{-\alpha_{i}})\to e^{-p_{ij}t}$,

    2. (b)

$N_{ij}(t)$ $\xrightarrow{D}$ $\mathrm{Poisson}$($p_{ij}t$).

Further for all support points, $\\{\mathrm{Poisson}(p_{ij}t)\\}_{j}$ is a
collection of mutually independent random variables.

This implies that in rare event setting, the distribution of the counting
process $N_{ij}(t)$ for each support point $a_{ij}\gamma^{-\alpha_{i}}$ is
well-approximated by a Poisson process. We now argue that when $\gamma$ is
small enough, the KL divergence between arm distributions $p_{i}$ and
$\tilde{p}_{i}$ of same rarity can be approximated by a sum of KL divergences
between independent $\mathrm{Poisson}$ variables.

Let $X_{1:m}$ and $\tilde{X}_{1:m}$ be two sets of i.i.d samples of size $m$
from $p_{i}$ and $\tilde{p}_{i}$ respectively. The corresponding measures are
the product measures $p_{i}^{\otimes m}$ and $\tilde{p}_{i}^{\otimes m}$
respectively. By the tensorization property of KL-divergence, we have that

$KL\big{(}p_{i}^{\otimes m},\tilde{p}_{i}^{\otimes
m}\big{)}=mKL(p_{i},\tilde{p}_{i})$ (4)

In the following discussion we set $m=\lceil t\gamma^{-\alpha_{i}}\rceil$.
Consider the vector-valued random variable $(N_{ij}(t))_{j\in[n_{i}]}$ and its
counterpart $(\tilde{N}_{ij}(t))_{j\in[n_{i}]}$ under $\tilde{p}_{i}$. Note
that they are functions of the samples $X_{1:\lceil
t\gamma^{-\alpha_{i}}\rceil},\tilde{X}_{1:\lceil
t\gamma^{-\alpha_{i}}\rceil}$. Since we can also reconstruct a permutation of
these samples from $({N}_{ij}(t))_{j}$,$(\tilde{N}_{ij}(t))_{j}$, we have that

$\displaystyle KL\big{(}p_{i}^{\otimes\lceil
t\gamma^{-\alpha_{i}}\rceil},\tilde{p}_{i}^{\otimes\lceil
t\gamma^{-\alpha_{i}}\rceil}\big{)}=KL\big{(}\nu((N_{ij}(t))_{j}),\nu((\tilde{N}_{ij}(t))_{j})\big{)}$

where $\nu(A)$ is the measure of a random variable $A$. Now, it can easily be
shown from Proposition 1 that

$\displaystyle KL\big{(}p_{i}^{\otimes\lceil
t\gamma^{-\alpha_{i}}\rceil},\tilde{p}_{i}^{\otimes\lceil
t\gamma^{-\alpha_{i}}\rceil}\big{)}$ $\displaystyle\approx$
$\displaystyle\sum_{j}KL(\textrm{Poisson}(p_{ij}t),\textrm{Poisson}(\tilde{p}_{ij}t))$
$\displaystyle=$ $\displaystyle
t\bigg{[}\sum_{j}p_{ij}\log\Big{(}\frac{p_{ij}}{\tilde{p}_{ij}}\Big{)}+(\tilde{p}_{ij}-p_{ij})\bigg{]}.$

for $\gamma$ small enough. Then, combining the approximation above with the
relation (4) gives

$KL(p_{i},\tilde{p}_{i})\approx\gamma^{\alpha_{i}}\bigg{[}\sum_{j}p_{ij}\log\Big{(}\frac{p_{ij}}{\tilde{p}_{ij}}\Big{)}+(\tilde{p}_{ij}-p_{ij})\bigg{]}.$
(5)

This approximation is used to motivate the approximate lower bound problem in
the next section.

##  3 Approximate Lower Bound Problem

For each $i$, if $B_{i}\notin\textrm{supp}(p_{i})$, let
$\tilde{n}_{i}=n_{i}+1$ and set $a_{i\tilde{n}_{i}}=B_{i}$, else
$\tilde{n}_{i}=n_{i}$. The Poisson approximation of the KL divergence (see
section 2.2) suggests that in lieu of equation (3), which is computationally
expensive to solve, one could consider the following approximate problem when
the rarity $\gamma$ is small (the summations over $j$ below correspond to
$j\in[\tilde{n}_{i}]$).

$\displaystyle V^{*}_{a}(p)\coloneqq\max_{w\in\Sigma_{K}}\min_{i\neq
1}\underset{\underset{\sum_{j}ua_{1j}\tilde{p}_{1j}}{\sum_{j}a_{ij}\tilde{p}_{ij}\geq}}{\inf}\bigg{\\{}w_{1}\gamma^{\alpha_{1}}\bigg{[}\sum_{j}p_{1j}\log\Big{(}\frac{p_{1j}}{\tilde{p}_{1j}}\Big{)}+(\tilde{p}_{1j}-p_{1j})\bigg{]}+w_{i}\gamma^{\alpha_{i}}\bigg{[}\sum_{j}p_{ij}\log\Big{(}\frac{p_{ij}}{\tilde{p}_{ij}}\Big{)}+(\tilde{p}_{ij}-p_{ij})\bigg{]}\bigg{\\}}.$
(6)

The minimization in 3 will now be replaced with the approximation in 5. Above,
instead of allowing $\tilde{p}_{i}$ to have the support
$[0,B_{i}\gamma^{-\alpha_{i}}]$, we limited its support to that of $p_{i}$
extended to allow point $B_{i}\gamma^{-\alpha_{i}}$. This is justified in
Sections A.1-A.2 of the supplementary material.

Let

$\mathcal{P}_{i}\coloneqq\underset{x\in[\mu_{i},\mu_{1}]}{\inf}w_{1}\mathcal{K}^{L}_{inf}(p_{1},x)+w_{i}\mathcal{K}^{U}_{inf}(p_{i},x)$
(7)

denote the inner minimisation problem in 3 and let

$\displaystyle\mathcal{P}_{i,a}\coloneqq\underset{\underset{\sum_{j}a_{1j}\tilde{p}_{1j}}{\sum_{j}a_{ij}\tilde{p}_{ij}\geq}}{\inf}w_{1}\gamma^{\alpha_{1}}\bigg{[}\sum_{j}p_{1j}\log\Big{(}\frac{p_{1j}}{\tilde{p}_{1j}}\Big{)}+(\tilde{p}_{1j}-p_{1j})\bigg{]}+w_{i}\gamma^{\alpha_{i}}\bigg{[}\sum_{j}p_{ij}\log\Big{(}\frac{p_{ij}}{\tilde{p}_{ij}}\Big{)}+(\tilde{p}_{ij}-p_{ij})\bigg{]}$
(8)

denote its approximation (above, we suppress the dependence on $w_{1}$ and
$w_{i}$ of $\mathcal{P}_{i}$ and $\mathcal{P}_{i,a}$).

By approximating a reformulated version of $\mathcal{P}_{i}$ that uses the
dual representations of $\mathcal{K}^{L}_{inf}$ and $\mathcal{K}^{U}_{inf}$
(following the approach used in Honda and Takemura, (2010); Agrawal et al.,
(2020)), we can show that

$\displaystyle\mathcal{P}_{i,a}=w_{1}\gamma^{\alpha_{1}}\big{[}\sum_{j}p_{1j}\log(1+C^{a}_{1i}a_{1j})-C^{a}_{1i}x^{*}_{i,a}\big{]}+w_{i}\gamma^{\alpha_{i}}\big{[}\sum_{j}p_{ij}\log(1-C^{a}_{i}a_{ij})+C^{a}_{i}x^{*}_{i,a}\big{]}.$
(9)

where the quantities $x^{*}_{i,a},C^{a}_{1i},C^{a}_{i}$ (the qualifier ’a’
reminds us these are for the approximate problem) are defined by the
relations:

$\displaystyle
C^{a}_{1i}w_{1}\gamma^{\alpha_{1}}=C^{a}_{i}w_{i}\gamma^{\alpha_{i}},$ (10)
$\displaystyle
x^{*}_{i,a}=\sum_{j}\frac{a_{1j}p_{1j}}{1+a_{1j}C^{a}_{1i}},\mbox{ and }$
$\displaystyle x^{*}_{i,a}=\sum_{j}\frac{a_{ij}p_{ij}}{1-a_{ij}C^{a}_{i}}.$

Section A.4 of the supplementary material provides the step-by-step
reformulation, as well as the results that have been used for it (Sections
A.1-A.3 and A.5). The advantage of our reformulation is that the quantities
$C^{a}_{1i}$ and $C^{a}_{i}$ have bounded well-defined limits and using (10),
we can eliminate the dependence on $x^{*}_{i}$ (whose behaviour is not as easy
to analyze when $\gamma\to 0$).

The discussion in Section 2.2 also suggests that
$\mathcal{P}_{i,a}\approx\mathcal{P}_{i}$ and hence, $V^{*}(p)\approx
V^{*}_{a}(p)$. This is shown in the following theorem:

  * Theorem1.

For each $i\in[K]$ and $w\in\Sigma_{K}$, $\mathcal{P}_{i}$,
$\mathcal{P}_{i,a}$ are $\mathcal{O}(\gamma^{\max(\alpha_{1},\alpha_{i})})$.
Furthermore, $\underset{\gamma\to
0}{\lim}\frac{\mathcal{P}_{i}}{\mathcal{P}_{i,a}}=1.$ In addition, there exist
constants $L_{1i}$ and $L_{i}$, independent of $w$, such that

$|\mathcal{P}_{i}-\mathcal{P}_{i,a}|\leq
L_{1i}w_{1}\gamma^{\min(2\alpha_{1},\alpha_{1}+\alpha_{i})}+L_{i}w_{i}\gamma^{\min(2\alpha_{i},\alpha_{i}+\alpha_{1})}.$

Furthermore,

$\displaystyle|V^{*}(p)-V^{*}_{a}(p)|\leq\underset{i\neq 1}{\max}\max\big{(}$
$\displaystyle
L_{1i}\gamma^{\min(2\alpha_{1},\alpha_{1}+\alpha_{i})},L_{i}\gamma^{\min(2\alpha_{i},\alpha_{i}+\alpha_{1})}\big{)}.$

The proof involves simplifying $\mathcal{P}_{i}$, $\mathcal{P}_{i,a}$ through
Taylor expansions for small $\gamma$. It is given in the Sections A.4 and B of
the supplementary material.

###  3.1 Solving the approximate lower bound

By definition we have that

$V^{*}_{a}(p)=\max_{w\in\Sigma_{K}}\min_{i\neq 1}\mathcal{P}_{i,a}.$

Further, we note that $\mathcal{P}_{i,a}$ is a concave function of $w$
(infimum of linear function of $w$). Maxmin problems with this specific
structure were studied in Glynn and Juneja, (2004) (the caveat being that in
our $\mathcal{K}_{inf}$ definitions in the underlying KL term, the first
argument is fixed while we optimize over the second argument, while in Glynn
and Juneja, (2004), these orders are reversed. However, all the steps carry
out identically). The optimal weights $w^{*}$ are characterized in the
following theorem:

  * Theorem1 in Glynn and Juneja, (2004).

The optimal $w^{*}$ of the maxmin problem 6 satisfies:

$\sum_{i=2}^{K}\frac{\partial\mathcal{P}_{i,a}(w^{*})}{\partial
w_{1}}\bigg{/}\frac{\partial\mathcal{P}_{i,a}(w^{*})}{\partial w_{i}}=1,$ (11)

and $\forall i\neq j$, $i,j\neq 1$,

$\mathcal{P}_{i,a}(w^{*})=\mathcal{P}_{j,a}(w^{*}).$ (12)

These conditions are also sufficient.

We can use the above theorem to find closed form expressions (in terms of
$w^{*}$) for $\mathcal{P}_{i,a}$ and
$\frac{\partial\mathcal{P}_{i,a}(w^{*})}{\partial w_{j}}$ using (9). As a
starting point, we identify certain monotonicities present in (10), (11) and
(12) to ease up the process of root-finding via bisection methods.

The equations defining $C^{a}_{1i}$ and $C^{a}_{i}$ imply that $C^{a}_{i}$ is
a decreasing function of $C^{a}_{1i}$. Mathematically, the implicit functions
$g_{i}(r)$, defined for all $i\neq 1$ as

$\sum_{j}\frac{a_{1j}p_{1j}}{1+g_{i}(r)a_{1j}}=\sum_{j}\frac{a_{ij}p_{ij}}{1-ra_{ij}}$

are decreasing in $r$. The domain of $g_{i}$ is chosen such that the RHS in
the above equation is positive and finite.
The optimality equation (12) implies at the optimal weight $w^{*}$, each
$C^{a}_{1i}$, $i>2$, is an increasing function of $C^{a}_{12}$. More formally,
the functions $\xi_{i}(s)$, $\forall i>2$, implicitly defined through the
equation:

$\displaystyle\sum_{j}p_{1j}\log(1+g_{i}(\xi_{i})a_{1j})+\frac{g_{i}(\xi_{i})}{\xi_{i}}\sum_{j}p_{ij}\log(1-\xi_{i}a_{ij})=\sum_{j}p_{1j}\log(1+g_{2}(s)a_{1j})+\frac{g_{2}(s)}{s}\sum_{j}p_{2j}\log(1-sa_{2j})$

are increasing in $s$. The domain of $\xi_{i}$ is such that the RHS is well-
defined. Finally, as a function of $C^{a}_{12}$, the LHS in the optimality
equation 11 is also increasing. Mathematically this means that the functions ,
$\forall i\neq 1$,

$\displaystyle
h_{i}(s)\coloneqq\bigg{(}\sum_{j}p_{1j}\log(1+\xi_{i}a_{1j})-\xi_{i}\Big{[}\sum_{j}\frac{a_{1j}p_{1j}}{1+a_{1j}\xi_{i}}\Big{]}\bigg{)}\bigg{(}\sum_{j}p_{ij}\log(1-g_{i}(\xi_{i})a_{ij})+g_{i}(\xi_{i})\sum_{j}\Big{[}\frac{a_{ij}p_{ij}}{1-a_{ij}g_{i}(\xi_{i})}\Big{]}\bigg{)}^{-1}$

are increasing in $s$. These monotonicities enable one to solve for optimal
weights in (6) through simple bisection methods. This is the source of
computational benefit of solving (6) vis-a-vis (3). In (3), one has to solve
either convex programs ($\mathcal{P}_{i}$) or a nonlinear system of four
equations to arrive at the solution (see Section C of supplementary material).

This enables us to study the behaviour of $w^{*}$ as $\gamma\to 0.$ We set up
some notation first.

  * Definition1.

Two positive valued functions of $\gamma$, $A(\gamma)$ and $B(\gamma)$, are
said to be asymptotically equivalent if $0<\underset{\gamma\to
0}{\liminf}\frac{A(\gamma)}{B(\gamma)}\leq\underset{\gamma\to
0}{\limsup}\frac{A(\gamma)}{B(\gamma)}<\infty$. We denote this by
$A(\gamma)=\Theta(B(\gamma))$.

Let $\alpha_{\max}={\max}_{i}\alpha_{i}$. The quantity
$\zeta\coloneqq\sum_{\underset{\alpha_{i}=\alpha_{max}}{i\neq
1,}}h_{i}(\xi_{i}(0))$ also plays a role in governing the asymptotic behaviour
of $w^{*}$.

Theorem (2) provides insight into the optimal weights in the lower bound
problem as $\gamma\rightarrow 0$. We discuss its conclusions further in the
nex subsection.

  * Theorem2.

The behaviour of $w^{*}$ as $\gamma\to 0$ is described by the following five
cases:

Case 1: The best arm is not the rarest, $\alpha_{max}\neq\alpha_{1}.$

$\displaystyle w^{*}_{1}=\Theta(\gamma^{\frac{\alpha_{max}-\alpha_{1}}{2}}),$
$\displaystyle w^{*}_{i}=\Theta(\gamma^{\alpha_{max}-\alpha_{i}})$
$\displaystyle\text{for all $i\neq 1$}.$

Case 2: The best arm is uniquely the rarest,
$\alpha_{1}=\alpha_{max}>\alpha_{i},i\neq 1.$

$\displaystyle w^{*}_{2}=\Theta(\gamma^{\frac{\alpha_{max}-\alpha_{2}}{2}}),$
$\displaystyle w^{*}_{i}=\Theta(\gamma^{\alpha_{max}-\alpha_{i}})$ for all
$i\neq 2.$

Case 3: The best and second best arm only are the rarest,
$\alpha_{1}=\alpha_{2}=\alpha_{max}>\alpha_{i},\ \forall i\neq 1,2.$

$w^{*}_{i}=\Theta(\gamma^{\alpha_{max}-\alpha_{i}}),\text{ for all $i.$}$

Case 4: The best arm is the rarest but not uniquely,
$\alpha_{1}=\alpha_{k}=\alpha_{max}\geq\alpha_{i},\ i\notin\\{1,2,k\\}$,
$\alpha_{max}>\alpha_{2}$ and $\zeta>1$.

$\displaystyle w^{*}_{2}=\Theta(\gamma^{\frac{\alpha_{max}-\alpha_{2}}{2}}),$
$\displaystyle w^{*}_{i}=\Theta(\gamma^{\alpha_{max}-\alpha_{i}})$ for all
$i\neq 2.$

Case 5: The best arm is the rarest but not uniquely,
$\alpha_{1}=\alpha_{k}=\alpha_{max}\geq\alpha_{i},\ i\notin\\{1,2,k\\}$,
$\alpha_{max}>\alpha_{2}$ and $\zeta\leq 1$.

$\displaystyle w^{*}_{1}=\Theta(\gamma^{\alpha_{max}-\alpha_{1}}),$
$\displaystyle w^{*}_{i}=\Theta(\gamma^{\alpha_{max}-\alpha_{i}})$ for all
$i\neq 1.$

Further, the asymptotic equivalence can be expressed by limits that are
functions of parameters of the bandit problem.

###### Proof.

See section C of supplementary material. ∎

The theorem gives us insight into the behavior of the optimal weights $w^{*}$
in equation (6). By the fact that $V^{*}(p)\approx V^{*}_{a}(p)$ (Theorem 1)
the optimal weights of actual maxmin problem also will show the same
asymptotic behaviour. It is easy to see that substituting these optimal
weights in $V^{*}(p)$ gives us an overall lower bound on the sample complexity
as a scalar multiple of $\gamma^{\alpha_{max}}$.

###  3.2 Discussion on Theorem 2

The following lemma will be useful in the subsequent discussion of Theorem 2.
Without loss of generality let arm 2 be the one with the second highest mean.
We further assume that $\mu_{2}>\mu_{i}$ for $i\geq 3$.

  * Lemma1.

In the maxmin problem (3), let $x^{*}_{i,e}(w^{*})$ denote the minimizer of
each $\mathcal{P}_{i}$ for the optimal weights $w^{*}$. Then, we have
$x^{*}_{i}(w^{*})\in[\mu_{2},\mu_{1}]\,\,\,\,\forall i$.

###### Proof.

We shall show this by contradiction. Suppose $x^{*}_{i,e}(w^{*})<\mu_{2}$.
Then, from the optimality conditions of $w^{*}$ (similar to (11), (12)) we
have, $\forall i\neq j$, $i,j\neq 1$:

$\displaystyle\underset{\mu^{\prime}_{i}\geq\mu^{\prime}_{1}}{\inf}w^{*}_{1}KL(\mu_{1},\mu^{\prime}_{1})+w^{*}_{i}KL(\mu_{i},\mu^{\prime}_{i})=\underset{\mu^{\prime}_{j}\geq\mu^{\prime}_{1}}{\inf}w^{*}_{1}KL(\mu_{1},\mu^{\prime}_{1})+w^{*}_{j}KL(\mu_{j},\mu^{\prime}_{j}).$

But we know that this minimization, for each $i\neq 1$, is attained uniquely
by a bandit instance $p^{\prime}$ where the rest of the arms, except 1 and
$i$, are the same as the original bandit instance in consideration, namely,
$p$. Both the arms $i$ and $1$ have means $x^{*}_{i,e}(w^{*})$ under
$p^{\prime}$. But the assumed hypothesis then implies that
$x^{*}_{i,e}(w^{*})=\mu^{\prime}_{1}<\mu^{\prime}_{2}=\mu_{2}$. That means
$p^{\prime}$ is also in the set $\\{\mu^{\prime}_{2}\geq\mu^{\prime}_{1}\\}$
and hence

$\displaystyle\underset{\mu^{\prime}_{i}\geq\mu^{\prime}_{1}}{\inf}w^{*}_{1}KL(\mu_{1},\mu^{\prime}_{1})+w^{*}_{i}KL(\mu_{i},\mu^{\prime}_{i})>\underset{\mu^{\prime}_{2}\geq\mu^{\prime}_{1}}{\inf}w^{*}_{1}KL(\mu_{1},\mu^{\prime}_{1})+w^{*}_{2}KL(\mu_{2},\mu^{\prime}_{2}).$

However, this contradicts the necessary optimality conditions for $w^{*}$.
Thus, $x^{*}_{i,e}(w^{*})\geq\mu_{2}$. ∎

A similar result can also be shown for the approximate problem (6) (see
Section D of supplementary material).

In the rare event setting, the non-zero samples from an arm are the
informative samples, but they are quite rare. Any algorithm needs to see non-
zero (informative) samples from at least some arms before it decides to stop.
By Lemma 1 we know that all arms, except possibly the best and second best
($i=1,2$), will show deviations in their sample mean under max-min optimality.
As the TS algorithm and our algorithm track these weights, it is to be
expected that the number of samples for arm $i(\neq 1,2)$ is only as high as
it takes to see an $\mathcal{O}(1)$ sample mean, but also sufficiently low as
to ensure that the probability of sample mean deviation is high. The optimal
weights $w^{*}_{i}\simeq\gamma^{\alpha_{max}-\alpha_{i}}$, $\forall i\neq
1,2$, have this feature. This gives the sample complexity for arm $i(\neq
1,2)$ as $\mathcal{O}(\gamma^{-\alpha_{i}})$ (since the overall sample
complexity is $\mathcal{O}(\gamma^{-\alpha_{\max}}$)). On average, each arm
thus sees only $\mathcal{O}(1)$ non-zero samples, with a deviation probability
$1-\mathcal{O}(\gamma^{\alpha_{i}}(\mu_{1}-\mu_{i})^{2})$ and $\mathcal{O}(1)$
sample mean.

##  4 Track and Stop Algorithm

Our algorithm builds upon the Track and Stop (TS) algorithm proposed in
Agrawal et al., (2019); Kaufmann et al., (2016). We call it Track and Stop
(A), to emphasize thatwe are solving an approximate problem. The algorithm
solves the approximate maxmin problem 6, and samples according to the weights
obtained. The calculation of the sampling weights happen in batches of size
$m$. Let $l$ denote the batch index. Within each batch we ensure that each arm
gets at least $\sqrt{lm}$ samples. This is done in the same manner as Agrawal
et al., (2019). At the end of $l$-th batch, TS(A) evaluates the maximum
likelihood ratio $Z_{k^{*}}(l)$ for the empirical best arm $k^{*}(l)$ and
decides whether to stop or not. The likelihood ratio is given by:

$\displaystyle Z_{k^{*}}(l)\coloneqq$ $\displaystyle\underset{b\neq
k^{*}}{\min}\underset{x\leq
y}{\inf}N_{k^{*}}(lm)\mathcal{K}_{inf}^{L}(\hat{p}_{k^{*}}(lm),x)+N_{b}(lm)\mathcal{K}_{inf}^{U}(\hat{p}_{b}(lm),y).$

$\hat{p}(t)$ refers to the empirical bandit instance after $t$ samples.
$N_{i}(t)$ denotes to number of pulls of arm $i$ after $t$ samples. TS(A)
stops when $Z_{k^{*}}(l)>\beta(lm,\delta)$, where $\beta(t,\delta)$ is a
stopping threshold defined as

$\beta(t,\delta)\coloneqq\log\bigg{(}\frac{K-1}{\delta}\bigg{)}+5\log(t+1)+2.$

Note that we are computing the maximum likelihood ratio by solving the
$\mathcal{K}_{inf}$ problems exactly, and not approximately. Although it is
relatively expensive to compute these quantities exactly, such computations
occur only once for each $l$. The number of samples $N_{i}(t)$ for each arm
$i$ is influenced by the optimal weights that are obtained as solution to the
approximate maxmin problem. The precise algorithmic details of TS(A) are given
below.

Algorithm 1 TS(A) algorithm

Generate $\lfloor\frac{m}{K}\rfloor$ samples for each arm.

$l\leftarrow 1$.

Compute the empirical bandit $\hat{p}=(\hat{p})_{i\in[K]}$.

$\hat{w}(\hat{p})\leftarrow\text{Compute weights according to
(\ref{approx_lower_bound_problem})}$.

$k^{*}\leftarrow\underset{i\in[K]}{\arg\max}\hskip
5.69046pt\mathbb{E}[\hat{p}_{i}]$.

Compute $Z_{k^{*}}(l)$, $\beta(lm,\delta)$.

while $Z_{k^{*}}(l)\geq\beta(lm,\delta)$ do

$s_{i}\leftarrow(\sqrt{(l+1)m}-N_{i}(lm))^{+}$.

if $m\geq\sum_{i}s_{i}$ then

Generate $s_{i}$ many samples for each arm $i$.

Generate $(m-\sum_{i}s_{i})^{+}$ i.i.d. samples from $\hat{w}(\hat{p})$. Let
$Count(i)$ be occurrence of $i$ in these samples.

Generate $Count(i)$ samples from each arm $i$.

else

$\hat{s}^{*}\leftarrow\underset{\hat{s},s_{i}\geq\hat{s}_{i}\geq
0}{\arg\min}\max_{i}(s_{i}-\hat{s}_{i})$.

Generate $\hat{s}^{*}_{i}$ samples from each arm $i$.

end if

$l\leftarrow l+1$

Update empirical bandit $\hat{p}.$

$k^{*}\leftarrow\underset{i\in[K]}{\arg\max}\hskip
5.69046pt\mathbb{E}[\hat{p}_{i}]$.

Update $Z_{k^{*}}(l)$, $\beta(lm,\delta)$.

$\hat{w}(\hat{p})\leftarrow\text{Compute weights according to
(\ref{approx_lower_bound_problem})}$.

end while

return $k^{*}$.

###  4.1 $\delta$-correctness and sample complexity of TS(A)

The following theorem guarantees the $\delta$-correctness and gives
asymtptotic sample complexity bound for TS(A):

  * Theorem3..

The TS(A) is a $\delta$-correct algorithm with the following asymptotic sample
complexity bound:

$\limsup_{\delta\to
0}\frac{\mathbb{E}[\tau_{\delta}]}{\log(1/\delta)}\leq\frac{1}{V_{TS(A)}(p)}$
(13)

where $V_{TS(A)}(p):=\underset{i\neq 1}{\min}\mathcal{P}_{i}(\hat{w}^{*}(p))$.
$\hat{w}^{*}(p))$ denotes the optimal weights for the approx lower bound
problem $V^{*}_{a}(p).$

See sections E and F in the supplementary material for a proof of Theorem 3.
Note that by definition we have $V^{*}(p)\leq V_{TS(A)}$ and hence we do
suffer some loss in sample complexity vis-a-vis the TS algorithm. However,
when $\gamma$ is small, the difference is negligible as
$w^{*}(p)\approx\hat{w}^{*}(p)$.

###  4.2 Computational Benefit of Poisson Approximation

The computational benefit of TS(A) vis-a-vis the exact algorithm, call it TS
(E), is in how the approximate and exact lower bound problems are solved.

Let us first examine the number of operations required in finding the exact
lower bound. In our implementation, we used Brent’s method for one-dimensional
optimization and the bisection method for root finding. To get a relative
error of $\epsilon$ in Brent’s method (see Chapter 4 in Brent, (2013)) we
require $\mathcal{O}\big{(}\log^{2}\big{(}\frac{1}{\epsilon}\big{)}\big{)}$
operations. The bisection method takes
$\mathcal{O}\big{(}\log\big{(}\frac{1}{\epsilon}\big{)}\big{)}$ for a relative
accuracy of $\epsilon$. Lemma 2 (see Section A of the supplementary material)
reduces the process of computing $\mathcal{K}_{inf}^{L}$ and
$\mathcal{K}_{inf}^{U}$ to a root-finding procedure, causing said computations
to take about $\mathcal{O}\big{(}\log\big{(}\frac{1}{\epsilon}\big{)}\big{)}$
operations. The inner optimization $\mathcal{P}_{i}$ is a convex optimization
that requires
$\mathcal{O}\big{(}\log^{2}\big{(}\frac{1}{\epsilon}\big{)}\big{)}$
operations. The outer optimization in (3) can be reduced to solving two sets
of simultaneous root finding procedures and hence would take
$\mathcal{O}\big{(}\log^{2}\big{(}\frac{1}{\epsilon}\big{)}\big{)}$. Thus, the
total number of operations to solve the exact lower bound (3) is
$\mathcal{O}\big{(}\log^{5}\big{(}\frac{1}{\epsilon}\big{)}\big{)}$.

In the approximate problem $C_{i},C_{1i}$’s are the unknown variables, whose
behaviour we analyze. Using $g_{i}$ (section 3.1) to write $C_{i}$ as a
function of $C_{1i}$ requires about
$\mathcal{O}\big{(}\log\big{(}\frac{1}{\epsilon}\big{)}\big{)}$ operations for
each such conversion using the bisection method. Then, each of the $C_{1i}$
$(i\neq 2)$, are written as function of $C_{12}$ through $\xi_{i}$. This again
requires about $\mathcal{O}\big{(}\log\big{(}\frac{1}{\epsilon}\big{)}\big{)}$
operations for each such conversion. Finally the solution of $C_{12}$ through
$h_{i}$ requires another factor of
$\mathcal{O}\big{(}\log\big{(}\frac{1}{\epsilon}\big{)}\big{)}$. This gives
the total required number of operations to be
$\mathcal{O}\big{(}\log^{3}\big{(}\frac{1}{\epsilon}\big{)}\big{)}$. Thus, we
are saving about
$\mathcal{O}\big{(}\log^{2}\big{(}\frac{1}{\epsilon}\big{)}\big{)}$ by solving
the approximate problem vis-a-vis the exact one.

##  5 Numerical Experiments

We compare the sample complexity and computational time between TS(A) and
Track & Stop TS(E) algorithm proposed in Agrawal et al., (2020). We make the
comparison across different arms, $\gamma$ and $\alpha$ structures at a
confidence level $\delta=0.01$. We run each algorithm for $100$ sample paths
and their average sample complexity and average computational time are
reported in the Table 1 below. The algorithm for both TS(E) and TS(A) proceeds
in batches of size $\gamma^{-\alpha_{\max}}$.

Experiment: ($\gamma$,$\alpha$) | Samples (m) | Runtime (s)
---|---|---
TS(E) | TS(A) | TS(E) | TS(A)
$\gamma=10^{-3}$, $\alpha=(1,1,1)$ | 0.93 | 0.98 | 619.7 | 51.91
$\gamma=10^{-2}$, $\alpha=(1,1.5,2)$ | 1.21 | 1.23 | 97.33 | 6.59
$\gamma=10^{-3}$, $\alpha=(1,1,1,1,1)$ | 2.03 | 2.22 | 1860.71 | 290.47
$\gamma=10^{-2}$, $\alpha=(2,1.5,2,2.5,1)$ | 14.93 | 16.87 | 152.28 | 23.64
Table 1: Comparison between the TS and TS(A) algorithms. Sample complexity is
reported in million (m) samples. The computational runtime is reported in
seconds (s).

The table shows for all experiments TS(A) takes slightly more samples
(1-13$\%$) to stop and recommend an arm compared to TS. The computational
savings of TS(A) is about $6-12$ times the TS algorithm. These simple
experiments underscore the trade-off between sample complexity and
computational time.

##  6 Conclusion

The paper proposes a rarity framework to study the fixed confidence BAI
problem relevant to online ad placement. In this framework the positive reward
probabilities are tiny while the corresponding rewards are quite large.
Consequently, the mean rewards are $\mathcal{O}(1)$.
We introduce a Poisson approximation to the standard lower bound problem and
use it to motivate an algorithm that is computationally faster than the
optimal TS algorithm at the cost of a small increase sample complexity. We
also use this approximation to derive asymptotic optimal weights which give
insight into the lower bound behaviour in the rare event setting. We observe
this trade-off between sample complexity and computational time in our
numerical experiments.

## References

  * Agrawal et al., (2019) Agrawal, S., Juneja, S., and Glynn, P. (2019).  Optimal $\delta$-correct best-arm selection for general distributions.  arXiv preprint arXiv:1908.09094.
  * Agrawal et al., (2020) Agrawal, S., Juneja, S., and Glynn, P. (2020).  Optimal $\delta$-correct best-arm selection for heavy-tailed distributions.  In Algorithmic Learning Theory, pages 61–110. PMLR.
  * Agrawal et al., (2021) Agrawal, S., Koolen, W. M., and Juneja, S. (2021).  Optimal best-arm identification methods for tail-risk measures.  Advances in Neural Information Processing Systems, 34:25578–25590.
  * Auer et al., (2002) Auer, P., Cesa-Bianchi, N., and Fischer, P. (2002).  Finite-time analysis of the multiarmed bandit problem.  Machine learning, 47(2):235–256.
  * Brent, (2013) Brent, R. P. (2013).  Algorithms for minimization without derivatives.  Courier Corporation.
  * Chan and Lai, (2006) Chan, H. P. and Lai, T. L. (2006).  Sequential generalized likelihood ratios and adaptive treatment allocation for optimal sequential selection.  Sequential Analysis, 25(2):179–201.
  * Even-Dar et al., (2006) Even-Dar, E., Mannor, S., Mansour, Y., and Mahadevan, S. (2006).  Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems.  Journal of machine learning research, 7(6).
  * Garivier and Kaufmann, (2016) Garivier, A. and Kaufmann, E. (2016).  Optimal best arm identification with fixed confidence.  In Conference on Learning Theory, pages 998–1027. PMLR.
  * Glynn and Juneja, (2004) Glynn, P. and Juneja, S. (2004).  A large deviations perspective on ordinal optimization.  In Proceedings of the 2004 Winter Simulation Conference, 2004., volume 1. IEEE.
  * Goldsman, (1983) Goldsman, D. (1983).  Ranking and selection in simulation.  Technical report, Institute of Electrical and Electronics Engineers (IEEE).
  * Honda and Takemura, (2010) Honda, J. and Takemura, A. (2010).  An asymptotically optimal bandit algorithm for bounded support models.  In COLT, pages 67–79. Citeseer.
  * Jamieson et al., (2014) Jamieson, K., Malloy, M., Nowak, R., and Bubeck, S. (2014).  lil’ucb: An optimal exploration algorithm for multi-armed bandits.  In Conference on Learning Theory, pages 423–439. PMLR.
  * Jamieson and Nowak, (2014) Jamieson, K. and Nowak, R. (2014).  Best-arm identification algorithms for multi-armed bandits in the fixed confidence setting.  In 2014 48th Annual Conference on Information Sciences and Systems (CISS), pages 1–6. IEEE.
  * Jourdan et al., (2022) Jourdan, M., Degenne, R., Baudry, D., de Heide, R., and Kaufmann, E. (2022).  Top two algorithms revisited.  arXiv preprint arXiv:2206.05979.
  * Kaufmann et al., (2016) Kaufmann, E., Cappé, O., and Garivier, A. (2016).  On the complexity of best-arm identification in multi-armed bandit models.  The Journal of Machine Learning Research, 17(1):1–42.
  * Russo, (2016) Russo, D. (2016).  Simple bayesian algorithms for best arm identification.  In Conference on Learning Theory, pages 1417–1418. PMLR.

##  Appendix A The $\mathcal{K}_{inf}$ problem and related reformulations

###  A.1 Dual form of $\mathcal{K}_{inf}$

The following well-known Lemma gives the dual representations of
$\mathcal{K}^{U}_{inf}(.,.)$ and $\mathcal{K}^{L}_{inf}(.,.)$. We follow the
approach used in Honda and Takemura, (2010); Agrawal et al., (2020).

  * Lemma2.

Consider any discrete distribution $\eta$ with a finite support
$\\{y_{j}\\}_{j\in[n]}$ and an upper bound $B$. We assume $y_{j}\geq 0,\forall
j$ and $0<x<B$.

a) The dual representation of $\mathcal{K}^{U}_{inf}(\eta,x)$ is

$\mathcal{K}^{U}_{inf}(\eta,x)=\max_{\lambda_{U}\in\big{[}0,\frac{1}{B-x}\big{]}}\sum_{j=0}^{n}\eta_{j}\log(1+\lambda_{U}(x-y_{j})).$

The optimal $\lambda^{*}_{U}$ in the dual maximization above is characterised
by:

$\begin{cases}\lambda^{*}_{U}=0,&\text{if $x<\mu_{\eta}$,}\\\
\lambda^{*}_{U}=\frac{1}{B-x},&\text{if $x>\mu_{\eta}$ and
$\sum_{j=0}^{n_{i}}\eta_{j}\big{(}\frac{B-x}{B-y_{j}}\big{)}<1$,}\\\
\sum_{j}\frac{y_{j}\eta_{j}}{1+\lambda^{*}_{U}(x-y_{j})}=x,&\text{If
$x>\mu_{\eta}$, and
$\sum_{j=0}^{n}\eta_{j}\big{(}\frac{B-x}{B-y_{j}}\big{)}\geq 1$.}\end{cases}$

The support of the primal optimizer $\kappa^{*}$ satisfies
$supp(\eta)\subseteq supp(\kappa^{*})\subseteq supp(\eta)\cup\\{B\\}$. The
constraint is tight at optimality:

$\mu_{\kappa^{*}}=x.$

Further for $y_{j}\in supp(\eta)$:

$\kappa^{*}(y_{j})=\frac{n_{j}}{1+\lambda^{*}_{U}(x-y_{j})}.$

b) The dual representation of $\mathcal{K}^{L}_{inf}(\eta,x)$ is

$\mathcal{K}^{L}_{inf}(\eta,x)=\max_{\lambda_{L}\in\big{[}0,\frac{1}{x}\big{]}}\sum_{j=0}^{n}\eta_{j}\log(1-\lambda_{L}(x-y_{j})).$

The optimal $\lambda^{*}_{L}$ in the dual maximization above is characterised
by:

$\begin{cases}\lambda^{*}_{L}=0,&\text{\hskip 28.45274ptif
$x\geq\mu_{\eta}$,}\\\
\sum_{j}\frac{(y_{j}-x)\eta_{j}}{1-\lambda^{*}_{L}(x-y_{j})}=0,&\text{\hskip
28.45274ptIf $x<\mu_{\eta}$.}\end{cases}$

The support of the primal optimizer $\kappa^{*}$ satisfies
$supp(\eta)=supp(\kappa^{*})$. The constraint is tight at optimality:

$\mu_{\kappa^{*}}=x.$

Further for $y_{j}\in supp(\eta)$:

$\kappa^{*}(y_{j})=\frac{n_{j}}{1-\lambda^{*}_{L}(x-y_{j})}.$

###### Proof.

See sections A.2 and A.3. ∎

###  A.2 Proof of Lemma 2a

Define the set $\mathcal{D}:=\\{0\\}\cup[b,B]$. Suppose a probability
distribution $\eta$ has finite support (say $\\{0,y_{1},...,y_{n}\\}$ for some
$n$) from $\mathcal{D}$. Let $\mathcal{M}^{+}(\mathcal{D})$ denote the set of
positive finite measures on $\mathcal{D}$. We want to find
$\mathcal{K}^{U}_{inf}(\eta,x)$, which is defined as

$\mathcal{K}^{U}_{inf}(\eta,x)=\min_{\begin{subarray}{c}\textrm{supp}(\kappa)\subseteq\mathcal{D}\\\
\mathbb{E}[\kappa]\geq x\end{subarray}}KL(\eta,\kappa).$

We shall develop a Lagrangian duality for the above quantity in the space
$\mathcal{M}^{+}(\mathcal{D})$. The Lagrangian with multiplier
$\lambda=(\lambda_{1},\lambda_{2})$ and
$\kappa\in\mathcal{M}^{+}(\mathcal{D})$ is:

$\mathcal{L}(\kappa,\lambda):=KL(\eta,\kappa)+\lambda_{1}(x-\int_{\mathcal{D}}yd\kappa(y))+\lambda_{2}(1-\int_{\mathcal{D}}d\kappa(y)).$

Then the dual objective becomes

$\mathcal{L}(\lambda):=\inf_{\kappa\in\mathcal{M}^{+}(\mathcal{D})}\mathcal{L}(\kappa,\lambda).$

Let us define two quantities useful in the analysis:

$h(y,\lambda):=-\lambda_{2}-\lambda_{1}y,$
$Z(\lambda):=\\{y\in\mathcal{D}:h(y,\lambda)=0\\}.$

We define the set

$\displaystyle\mathcal{R}_{2}$
$\displaystyle:=\\{\lambda\in\mathbb{R}^{2}:\lambda_{1}\geq
0,\lambda_{2}\in\mathbb{R},\lambda\neq
0,\inf_{y\in\mathcal{D}}h(y,\lambda)\geq 0\\}$
$\displaystyle=\\{\lambda\in\mathbb{R}^{2}:\lambda_{1}\geq
0,\lambda_{2}\in\mathbb{R},\lambda\neq 0,-\lambda_{2}\geq\lambda_{1}B\geq
0\\}.$

The lemma below shows that in maximising the dual objective
$\mathcal{L}(\lambda)$, it is enough to restrict ourselves to the set
$\mathcal{R}_{2}$.

  * LemmaA.1.a.

$\max_{\begin{subarray}{c}\lambda_{1}\geq 0,\\\
\lambda_{2}\in\mathbb{R}\end{subarray}}\mathcal{L}(\lambda)=\max_{\lambda\in\mathcal{R}_{2}}\mathcal{L}(\lambda)$

###### Proof.

Suppose $\lambda\notin\mathcal{R}_{2}$. Then, there is a $y_{0}\in\mathcal{D}$
such that $h(y_{0},\lambda)<0$. We know that for any $M>0$, we have a measure
$\kappa_{M}\in\mathcal{M}^{+}(\mathcal{D})$ such that

$\kappa_{M}(y_{0})=M,\ \frac{d\kappa_{M}}{d\eta}(y)=1,\forall
y\in\textrm{supp}(\eta)\backslash\\{y_{0}\\}$

So, we must have that
$\textrm{supp}(\kappa_{M})=\\{y_{0}\\}\cup\textrm{supp}(\eta)$.

$\displaystyle\mathcal{L}(\kappa_{M},\lambda)$
$\displaystyle=\int_{\mathcal{D}}\log\bigg{(}\frac{d\eta}{d\kappa_{M}}(y)\bigg{)}d\eta(y)+\int_{\mathcal{D}}h(y,\lambda)d\kappa_{M}(y)+\lambda_{1}x+\lambda_{2}$
$\displaystyle=\eta(y_{0})\log\bigg{(}\frac{\eta(y_{0})}{M}\bigg{)}+Mh(y_{0},\lambda)+\int_{\mathrm{supp}(\eta)}h(y,\lambda)d\kappa_{M}(y)+\lambda_{1}x+\lambda_{2}.$

Now as $M\to\infty$ the first two terms tend to $-\infty$ while the other
terms remain bounded and gives the result. ∎

The next lemma characterises the minimizer $\kappa^{*}$ in the dual objective
$\mathcal{L}(\lambda)$. The support of $\kappa^{*}$ is contained in
$\mathrm{supp}(\eta)\cup Z(\lambda)$ and its density wrt $\eta$ (wherever it
is well-defined) is $1/h(y,\lambda)$.

  * LemmaA.1.b.

For $\lambda\in\mathcal{R}_{2}$, $\kappa^{*}\in\mathcal{M}^{+}(\mathcal{D})$
that minimizes $\mathcal{L}(\kappa,\lambda)$ satisfies
$\mathrm{supp}(\eta)\subseteq\mathrm{\kappa^{*}}\subseteq\mathrm{supp}(\eta)\cup
Z(\lambda).$
Also, for $y\in\mathrm{supp}(\eta),h(y,\lambda)>0,$ and

$\frac{d\kappa^{*}}{d\eta}=\frac{1}{-\lambda_{1}-\lambda_{2}y}.$

###### Proof.

Given $\lambda\in\mathcal{R}_{2}$, the inner optimization problem is strictly
convex in $\kappa$. This means that a unique minimizer $\kappa^{*}$ must
exist. This $\kappa^{*}$ must satisfy for any arbitrary
$\kappa_{1},\kappa_{t}:=(1-t)\kappa^{*}+t\kappa_{1}$,
$\frac{\partial\mathcal{L}(\kappa_{t},\lambda)}{\partial t}\bigg{|}_{t=0}\geq
0$.
Let us define $\mathcal{L}(t):=\mathcal{L}(\kappa_{t},\lambda)$ which is

$\int_{\mathrm{supp}(\eta)}\log\bigg{(}\frac{d\eta}{d\kappa_{t}}(y)\bigg{)}d\eta(y)+\int_{\mathcal{D}}h(y,\lambda)d\kappa_{t}(y)+\lambda_{1}x+\lambda_{2}.$

Then,

$\frac{d\mathcal{L}(t)}{dt}=\int_{\mathrm{supp}(\eta)}\frac{d\eta}{d\kappa^{*}}(y)(d\kappa^{*}(y)-d\kappa_{1}(y))+\int_{\mathcal{D}}h(y,\lambda)(d\kappa_{1}(y)-d\kappa^{*}(y)).$

So,

$\frac{d\mathcal{L}(t)}{dt}\bigg{|}_{t=0}=-\int_{\mathcal{D}\backslash\mathrm{supp}(\eta)}h(y,\lambda)d\kappa^{*}(y))+\int_{\mathcal{D}\backslash\mathrm{supp}(\eta)}h(y,\lambda)(d\kappa_{1}(y)).$

Now, $\lambda\in\mathcal{R}^{2}$ guarantees that
$\mathcal{L}^{{}^{\prime}}(0)\geq 0$. This completes our proof. ∎

  * RemarkA.1.1.

If $y\in Z(\lambda)$, then $y$ can only be $-\frac{\lambda_{2}}{\lambda_{1}}$.
Therefore, we get that
$Z(\lambda)=\big{\\{}-\frac{\lambda_{2}}{\lambda_{1}}\big{\\}}$, if
$\lambda_{1}\geq 0,-\frac{\lambda_{2}}{\lambda_{1}}\in\mathcal{D}$ and
$Z(\lambda)=\emptyset$, otherwise.

It now remains to find
$\underset{\lambda\in\mathcal{R}_{2}}{\max}\mathcal{L}(\lambda)$ in order to
characterise the Lagrangian dual of $\mathcal{K}^{U}_{inf}(\eta,x)$.

If $Z(\lambda)=\Phi$, $\textrm{supp}(\kappa^{*})=\textrm{supp}(\eta)$. We can
then say from the characterization of $\kappa^{*}$ that

$\mathcal{K}_{inf}^{U}(\eta,x)=\max_{\lambda\in\mathcal{R}_{2}}\sum_{j=0}^{n}\eta_{j}\log(-\lambda_{2}-\lambda_{1}y_{j})$

The first order conditions tell us that
$\sum_{j}\frac{\eta_{j}}{\lambda_{2}-\lambda_{1}y_{j}}=1$ and
$\sum_{j}\frac{y_{j}\eta_{j}}{\lambda_{2}-\lambda_{1}y_{j}}=x$. Multiplying
the first equation by $-\lambda_{2}$ and the second by $-\lambda_{1}$ and then
adding the two would give us that $\lambda_{2}-\lambda_{1}x=1$. And
$\lambda_{2}\geq\lambda_{1}B\Rightarrow
1+\lambda_{1}x\geq\lambda_{1}B\Rightarrow\lambda_{1}\in\big{[}0,\frac{1}{B-x}\big{]}$.
We can therefore conclude that

$\mathcal{K}^{U}_{inf}(\eta,x)=\max_{\lambda_{1}\in\big{[}0,\frac{1}{B-x}\big{]}}\sum_{j=0}^{n}\eta_{j}\log(1+\lambda_{1}(x-y_{j}))$

If $Z(\lambda)\neq\Phi$, then $-\frac{\lambda_{2}}{\lambda_{1}}\leq B$. But
$\lambda\in\mathcal{R}_{2}$ implies that $-\frac{\lambda_{2}}{\lambda_{1}}\geq
B$. Hence, $-\frac{\lambda_{2}}{\lambda_{1}}=B$. Then, we can say that

$\mathcal{K}_{inf}^{U}(\eta,x)=\max_{\lambda_{1}\geq
0}\sum_{j=0}^{n}\eta_{j}\log(\lambda_{1}(B-y_{j})).$

Let $\lambda_{U}^{*}$ denote the maximizing $\lambda_{1}$, $\kappa^{*}(B)$
denote the mass that $\kappa^{*}$ puts at $B$. Then, we get from the first
order conditions that
$\sum_{j}\frac{\eta_{j}}{\lambda_{U}^{*}(B-y_{j})}+\kappa^{*}(B)=1$ and
$\sum_{j}\frac{y_{j}\eta_{j}}{\lambda_{U}^{*}(B-y_{j})}+B\kappa^{*}(B)=x$.
Multiplying the first equation by B and adding to the second gives us that
$B-x=\frac{1}{\lambda_{U}^{*}}\Rightarrow\lambda_{U}^{*}=\frac{1}{B-x}$.
Therefore, in this case,

$\mathcal{K}^{U}_{inf}(\eta,x)=\sum_{j=0}^{n}\eta_{j}\log\bigg{(}\frac{B-y_{j}}{B-x}\bigg{)}.$

Note that this can happen iff
$\sum_{j=0}^{n}\eta_{j}\log\bigg{(}\frac{B-x}{B-y_{j}}\bigg{)}\leq 1$.

Irrespective of whether or not $Z(\lambda)=\Phi$, we can say that

$\mathcal{K}^{U}_{inf}(\eta,x)=\max_{\lambda_{1}\in\big{[}0,\frac{1}{B-x}\big{]}}\sum_{j=0}^{n}\eta_{j}\log(1+\lambda_{1}(x-y_{j}))$

. Let us define
$p(\lambda_{1}):=\sum_{j=0}^{n}\eta_{j}\log(1+\lambda_{1}(x-y_{j}))$,
$\lambda_{1}\in\big{[}0,\frac{1}{B-x}\big{]}$. Then,
$p^{{}^{\prime}}(\lambda_{1})=\sum_{j=0}^{n}\frac{\eta_{j}(x-y_{j})}{1+\lambda_{1}(x-y_{j})}$
and
$p^{{}^{\prime\prime}}(\lambda_{1})=-\sum_{j=0}^{n}\frac{\eta_{j}(x-y_{j})^{2}}{(1+\lambda_{1}(x-y_{j}))^{2}}$.
The expression for $p^{{}^{\prime\prime}}$ leads us to conclude that $p$ is
always concave in $\lambda_{1}$ and hence, must have a unique maximizer.

If $x\leq\mathbb{E}_{\eta}$, note that
$p^{{}^{\prime}}(0)=x-\sum_{j=0}^{n}\eta_{j}y_{j}\leq 0$, i.e., $p$ decreases
in $\big{[}0,\frac{1}{B-x}\big{]}$. Hence, we must have
$\mathcal{K}^{U}_{inf}(\eta,x)=\max_{\lambda_{1}\in\big{[}0,\frac{1}{B-x}\big{]}}p(\lambda_{1})=p(0)=0$.
Since the maximizer is $\lambda_{U}^{*}=0$, we know from the definition of
$Z(\lambda)$ that $Z(\lambda)=\Phi$, and therefore,
$\textrm{supp}(\kappa^{*})=\textrm{supp}(\eta)$.

If $x>\mathbb{E}_{\eta}$, then we have that $p^{{}^{\prime}}(0)>0$, meaning
that $p$ is increasing at $\lambda_{1}=0$ and therefore, may take the maximum
value at either $\lambda_{U}^{*}=\frac{1}{B-x}$ or
$\lambda_{U}^{*}\in\big{(}0,\frac{1}{B-x}\big{)}$. Let us first compute
$p^{{}^{\prime}}\big{(}\frac{1}{B-x}\big{)}$.

$\displaystyle
p^{{}^{\prime}}\big{(}\frac{1}{B-x}\big{)}=\sum_{j=0}^{n}\eta_{j}\frac{(x-y_{j})(B-x)}{(B-y_{j})}$
$\displaystyle=$
$\displaystyle(B-x)\sum_{j=0}^{n}\frac{\eta_{j}x-\eta_{j}B+\eta_{j}B-\eta_{j}y_{j}}{B-y_{j}}$
$\displaystyle=$
$\displaystyle-(B-x)^{2}\sum_{j=0}^{n}\frac{\eta_{j}}{B-y_{j}}+(B-x)$
$\displaystyle=$
$\displaystyle(B-x)\bigg{[}1-\sum_{j=0}^{n}\eta_{j}\big{(}\frac{B-x}{B-y_{j}}\big{)}\bigg{]}$

If $p^{{}^{\prime}}\big{(}\frac{1}{B-x}\big{)}\leq 0$, then $p$ must reach its
maximum in $\big{(}0,\frac{1}{B-x}\big{)}$. This happens iff
$\sum_{j=0}^{n}\eta_{j}\big{(}\frac{B-x}{B-y_{j}}\big{)}\geq 1$.

If $p^{{}^{\prime}}\big{(}\frac{1}{B-x}\big{)}>0$, then $p$ must reach its
maximum at $\frac{1}{B-x}$. This happens iff
$\sum_{j=0}^{n}\eta_{j}\big{(}\frac{B-x}{B-y_{j}}\big{)}<1$.

  * RemarkA.1.2.

For the rare event setup, it is now easy to check that mass will be put at
$B_{i}\gamma^{-\alpha_{i}}$ in $\mathcal{K}^{U}_{inf}(p_{i},x)$ iff
$x>F_{0}(\gamma)$, where
$F_{0}(\gamma):=\frac{B_{i}}{\big{(}\sum_{j=1}^{n}\frac{a_{ij}p_{ij}}{B_{i}-a_{ij}}\big{)}^{-1}+\gamma^{\alpha_{i}}}$.

###  A.3 Proof of Lemma 2b

We want to find

$\mathcal{K}^{L}_{inf}(\eta,x)=\min_{\begin{subarray}{c}\textrm{supp}(\kappa)\subseteq\mathcal{D}\\\
\mathbb{E}[\kappa]\leq x\end{subarray}}KL(\eta,\kappa)$

Just as in section A.2, we shall develop a Lagrangian dual for
$\mathcal{K}^{L}_{inf}(\eta,x)$. The Lagrangian with multiplier
$\lambda=(\lambda_{1},\lambda_{2})$ is:

$\mathcal{L}(\kappa,\lambda):=KL(\eta,\kappa)-\lambda_{1}(x-\int_{\mathcal{D}}yd\kappa(y))-\lambda_{2}(1-\int_{\mathcal{D}}d\kappa(y))$

Similar to section A.2, define the quantities

$\mathcal{L}(\lambda):=\inf_{\kappa\in\mathcal{M}^{+}(\mathcal{D})}\mathcal{L}(\kappa,\lambda),$
$\displaystyle h(y,\lambda):=\lambda_{2}+\lambda_{1}y,$ $\displaystyle
Z(\lambda):=\\{y\in\mathcal{D}:h(y,\lambda)=0\\}$

and the set

$\displaystyle\mathcal{R}_{2}$
$\displaystyle:=\\{\lambda\in\mathbb{R}^{2}:\lambda_{1}\geq
0,\lambda_{2}\in\mathbb{R},\lambda\neq
0,\inf_{y\in\mathcal{D}}h(y,\lambda)\geq 0\\}$
$\displaystyle=\\{\lambda\in\mathbb{R}^{2}:\lambda_{1}\geq 0,\lambda_{2}\geq
0,\lambda\neq 0\\}.$

As in section A.2 we have the following lemmas:

  * LemmaA.2.a.

$\max_{\begin{subarray}{c}\lambda_{1}\geq 0,\\\
\lambda_{2}\in\mathbb{R}\end{subarray}}\mathcal{L}(\lambda)=\max_{\lambda\in\mathcal{R}_{2}}\mathcal{L}(\lambda)$

###### Proof.

Suppose $\lambda\notin\mathcal{R}_{2}$. Then, there is a $y_{0}\in\mathcal{D}$
such that $h(y_{0},\lambda)<0$. We know that for any $M>0$, we have a measure
$\kappa_{M}\in\mathcal{M}^{+}(\mathcal{D})$ such that

$\kappa_{M}(y_{0})=M,\ \frac{d\kappa_{M}}{d\eta}(y)=1,\forall
y\in\textrm{supp}(\eta)\backslash\\{y_{0}\\}$

So, we must have that
$\textrm{supp}(\kappa_{M})=\\{y_{0}\\}\cup\textrm{supp}(\eta)$.

$\displaystyle\mathcal{L}(\kappa,\lambda)$
$\displaystyle=\int_{\mathcal{D}}\log\bigg{(}\frac{d\eta}{d\kappa_{M}}(y)\bigg{)}d\eta(y)+\int_{\mathcal{D}}h(y,\lambda)d\kappa_{M}(y)-\lambda_{1}x-\lambda_{2}$
$\displaystyle=\eta(y_{0})\log\bigg{(}\frac{\eta(y_{0})}{M}\bigg{)}+Mh(y_{0},\lambda)+\int_{\mathrm{supp}(\eta)}h(y,\lambda)d\kappa_{M}(y)-\lambda_{1}x-\lambda_{2}$

Now as $M\to\infty$ the first two terms tend to $-\infty$ while the other
terms remain bounded and we obtain the desired result. ∎

  * LemmaA.2.b.

For $\lambda\in\mathcal{R}_{2}$, $\kappa^{*}\in\mathcal{M}^{+}(\mathcal{D})$
that minimizes $\mathcal{L}(\kappa,\lambda)$ satisfies
$\mathrm{supp}(\eta)\subseteq\mathrm{\kappa^{*}}\subseteq\mathrm{supp}(\eta)\cup
Z(\lambda).$
Also, for $y\in\mathrm{supp}(\eta),h(y,\lambda)>0,$ and

$\frac{d\kappa^{*}}{d\eta}=\frac{1}{\lambda_{1}+\lambda_{2}y}.$

###### Proof.

Given $\lambda\in\mathcal{R}_{2}$, the inner optimization problem is strictly
convex in $\kappa$. This means that a unique minimizer $\kappa^{*}$ must
exist. This $\kappa^{*}$ must satisfy for any arbitrary
$\kappa_{1},\kappa_{t}:=(1-t)\kappa^{*}+t\kappa_{1}$,
$\frac{\partial\mathcal{L}(\kappa_{t},\lambda)}{\partial t}\bigg{|}_{t=0}\geq
0$.
Let us define $\mathcal{L}(t):=\mathcal{L}(\kappa_{t},\lambda)$ which is

$\mathcal{L}(t)=\int_{\mathrm{supp}(\eta)}\log\bigg{(}\frac{d\eta}{d\kappa_{M}}(y)\bigg{)}d\eta(y)+\int_{\mathcal{D}}h(y,\lambda)d\kappa_{t}(y)-\lambda_{1}x-\lambda_{2}.$

Then,

$\frac{d\mathcal{L}(t)}{dt}=\int_{\mathrm{supp}(\eta)}\frac{d\eta}{d\kappa^{*}}(y)(d\kappa^{*}(y)-d\kappa_{1}(y))+\int_{\mathcal{D}}h(y,\lambda)(d\kappa_{1}(y)-d\kappa^{*}(y)).$

So,

$\frac{d\mathcal{L}(t)}{dt}\bigg{|}_{t=0}=-\int_{\mathcal{D}\backslash\mathrm{supp}(\eta)}h(y,\lambda)d\kappa^{*}(y))+\int_{\mathcal{D}\backslash\mathrm{supp}(\eta)}h(y,\lambda)(d\kappa_{1}(y)).$

Now, $\lambda\in\mathcal{R}^{2}$ guarantees that
$\mathcal{L}^{{}^{\prime}}(0)\geq 0$. This completes our proof. ∎

Note that if $y\in Z(\lambda)$ then $y=-\frac{\lambda_{2}}{\lambda_{1}}$ if
$-\frac{\lambda_{2}}{\lambda_{1}}\in\mathcal{D}.$ But because
$\lambda\in\mathcal{R}_{2}$ we have $-\frac{\lambda_{2}}{\lambda_{1}}<0$ and
hence $Z(\lambda)=\phi.$ This implies
$\mathrm{supp}(\kappa^{*})=\mathrm{supp}(\eta)$ with the mean and probability
conditions

$\displaystyle 1=\sum_{j}\frac{\eta_{j}}{(\lambda_{2}+\lambda_{1}y_{j})}$
$\displaystyle x=\sum_{j}\frac{y_{j}\eta_{j}}{(\lambda_{2}+\lambda_{1}y_{j})}$

These imply $1=\lambda_{2}+\lambda_{1}x$. As $\lambda_{2}\geq 0$, we have
$\lambda_{1}\leq\frac{1}{x}.$ Thus, denoting the optinal $\lambda_{1}$ by
$\lambda_{L}^{*}$, we get that

$\mathcal{K}^{L}_{inf}(\eta,x)=\sum\eta_{j}\log(1-\lambda_{L}^{*}(x-y_{j}))$

with $0\leq\lambda_{L}^{*}\leq 1/x$ and the mean equation

$x=\sum_{j}\frac{y_{j}\eta_{j}}{(1-\lambda_{L}^{*}(x-y_{j}))}.$

###  A.4 Reformulation of the lower bound

We can now use Lemma 2 to simplify $\mathcal{P}_{i}$ (see 7 of the main body)
in the rare event setting. We observe that the objective in $\mathcal{P}_{i}$
is a smooth and strictly convex function. The optimizer, $x^{*}_{i,e}$, is
therefore given by first-order stationarity conditions. Using the dual
representation, we can write this as

$w_{1}\lambda^{*}_{L_{1i}}(x^{*}_{i,e})-w_{i}\lambda^{*}_{U_{i}}(x^{*}_{i,e})=0$

where $\lambda^{*}_{U_{i}},\lambda^{*}_{L_{1i}}$ are as in Lemma 2 and are
functions of $x^{*}_{i,e}$. Now let us define quantities that are useful in
reformulating $\mathcal{P}$ to a form suitable for further analysis. Define

$\displaystyle K_{1i}:=1-x^{*}_{i,e}\lambda^{*}_{L_{1i}}(x^{*}_{i,e}),$
$\displaystyle C_{1i}:=\lambda^{*}_{L_{1i}}(x^{*}_{i,e})\gamma^{-\alpha_{1}},$
$\displaystyle K_{i}:=1+x^{*}_{i,e}\lambda^{*}_{U_{i}}(x^{*}_{i,e}),$
$\displaystyle C_{i}:=\lambda^{*}_{U_{i}}(x^{*}_{i,e})\gamma^{-\alpha_{i}}.$

These quantities will turn out to have bounded limits as $\gamma\to 0$. The
stationarity condition may now be rewritten as

$C_{1i}w_{1}\gamma^{\alpha_{1}}=C_{i}w_{i}\gamma^{\alpha_{i}}.$ (14)

In the rare event setup, the tightness of the constraint in Lemma 2 gives us
that

$\displaystyle x^{*}_{i,e}$
$\displaystyle=\sum_{j=1}^{n_{1}}\frac{a_{1j}p_{1j}}{K_{1i}+C_{1i}a_{1j}}=\sum_{j=1}^{n_{i}}\frac{a_{ij}p_{ij}}{K_{i}-C_{i}a_{ij}}+B_{i}\gamma^{-\alpha_{i}}\bigg{[}1-\sum_{j=1}^{n}\frac{p_{ij}}{K_{i}-C_{i}a_{ij}}\gamma^{\alpha_{i}}-\frac{1-\sum_{j=1}^{n}p_{ij}\gamma^{\alpha_{i}}}{K_{i}}\bigg{]}.$
(15)

Since the primal optimizer has the same support as the underlying distribution
in part (b) of Lemma 2, we must have

$\sum_{j=1}^{n}\frac{p_{1j}}{K_{1i}+C_{1i}a_{1j}}\gamma^{\alpha_{1}}+\frac{1-\sum_{j=1}^{n}p_{1j}\gamma^{\alpha_{1}}}{K_{1i}}=1.$
(16)

From their definitions and from the stationarity condition, we have the
following relationship between $K_{1i}$ and $K_{i}$:

$w_{1}(1-K_{1i})=w_{i}(K_{i}-1).$ (17)

Let
$\mathcal{P}_{i}=\underset{x\in[\mu_{i},\mu_{1}]}{\inf}\mathcal{K}_{i}(w_{1},w_{i},x)$
(see (7) from the main body). We know from the Envelope Theorem that

$\frac{d\mathcal{K}_{i}(w_{1},w_{i},x)}{dx}=-w_{1}\lambda_{L_{1i}^{*}}+w_{i}\lambda_{U_{i}^{*}}.$

The first order stationarity condition
$\frac{d\mathcal{K}_{i}(w_{1},w_{i},x)}{dx}=0$ implies that
$w_{1}\lambda_{L_{1i}^{*}}=w_{i}\lambda_{U_{i}^{*}}\
=\phi_{i},(\textrm{say})$. Let us define
$x^{*}_{i}:=\arg\min_{x\in[\mu_{i},\mu_{1}]}\mathcal{K}_{i}(w_{1},w_{i},x)$.
It is easy to infer from our derivations of the $\mathcal{K}_{inf}^{L}$ and
$\mathcal{K}_{inf}^{U}$ expressions that

$\displaystyle\mathcal{K}_{inf}^{L}(p_{1},x^{*}_{i})=KL(p_{1},\tilde{p}_{1}^{(i)})$
(18)
$\displaystyle\mathcal{K}_{inf}^{U}(p_{i},x^{*}_{i})=KL(p_{i},\tilde{p}_{i})$

where

$\displaystyle\tilde{p}_{1j}^{(i)}=\frac{p_{1j}}{1-\lambda_{L_{1i}^{*}}(x^{*}_{i}-a_{1j}\gamma^{-\alpha_{1}})}=\frac{p_{1j}}{\big{(}1-\frac{\phi_{i}}{w_{1}}x^{*}_{i})+\frac{\phi_{i}a_{1j}}{w_{1}\gamma^{\alpha_{1}}}}$
(19)
$\displaystyle\tilde{p}_{ij}=\frac{p_{ij}}{1+\lambda_{U_{i}^{*}}(x^{*}_{i}-a_{ij}\gamma^{-\alpha_{i}})}=\frac{p_{ij}}{\big{(}1+\frac{\phi_{i}}{w_{i}}x^{*}_{i})-\frac{\phi_{i}a_{ij}}{w_{i}\gamma^{\alpha_{i}}}}$

We note that
$\mathbb{E}_{\tilde{p}_{1}^{(i)}}=\mathbb{E}_{\tilde{p}_{i}}=x^{*}_{i}$.

We can now express $K_{1i}=1-\frac{\phi_{i}}{w_{1}}x^{*}_{i}-i$,
$K_{i}=1+\frac{\phi_{i}}{w_{i}}x^{*}_{i}$,
$C_{1i}=\frac{\phi_{i}}{w_{1}\gamma^{\alpha_{1}}}$,
$C_{i}=\frac{\phi_{i}}{w_{i}\gamma^{\alpha_{i}}}$. The following obvious
equations will be helpful.

$\displaystyle
K_{1i}=\frac{1-\sum_{j=1}^{n}p_{1j}\gamma^{\alpha_{1}}}{1-\sum_{j=1}^{n}\tilde{p}_{1j}^{(i)}\gamma^{\alpha_{1}}}$
$\displaystyle
K_{i}=\frac{1-\sum_{j=1}^{n}p_{ij}\gamma^{\alpha_{i}}}{1-\sum_{j=1}^{n}\tilde{p}_{ij}\gamma^{\alpha_{i}}}$
$\displaystyle w_{1}(1-K_{1i})=w_{i}(K_{i}-1)=\phi_{i}x^{*}_{i}$

We also claim that

$\displaystyle 1-\sum_{j=1}^{n}p_{1j}\gamma^{\alpha_{1}}\leq K_{1i}\leq 1,$
(20) $\displaystyle 1\leq
K_{i}\leq\bigg{[}\frac{1}{1-\frac{\gamma^{\alpha_{1}}\mu_{1}}{\max_{j}a_{ij}(1-\sum_{j=1}^{n}p_{1j}\gamma^{\alpha_{1}})}}\bigg{]}.$

For the proof of the first claim, we see that
$K_{1i}=1-\lambda_{L_{1i}^{*}}x\leq 1$ because
$0\leq\lambda_{L_{1i}^{*}}\leq\frac{1}{x}\Rightarrow
0\leq\lambda_{L_{1i}^{*}}x\leq 1$. The lower bound on $K_{1i}$ is trivial.

For the proof of the second claim, we see that
$K_{i}=1+\frac{\phi_{i}}{w_{i}}x^{*}\geq 1$. We also have that
$w_{i}(K_{i}-1)=\phi_{i}x^{*}\leq\frac{\phi_{i}x^{*}}{K_{1i}}\leq\frac{\phi_{i}x^{*}_{i}}{1-\sum_{j=1}^{n}p_{1j}\gamma^{\alpha_{1}}}$.
This implies that
$K_{i}-1\leq\frac{\phi_{i}}{w_{i}\gamma^{\alpha_{i}}}.\frac{\gamma^{\alpha_{i}\mu_{1}}}{1-\sum_{j=1}^{n}p_{1j}\gamma^{\alpha_{1}}}\leq\frac{K_{i}}{max_{j}a_{ij}}.\frac{\gamma^{\alpha_{i}\mu_{1}}}{1-\sum_{j=1}^{n}p_{1j}\gamma^{\alpha_{1}}}$.
As the final step, we can conclude from the above chain of inequalities that
$K_{i}\bigg{(}1-\frac{1}{max_{j}a_{ij}}.\frac{\gamma^{\alpha_{i}\mu_{1}}}{1-\sum_{j=1}^{n}p_{1j}\gamma^{\alpha_{1}}}\bigg{)}\leq
1$

These bounds tell us that $K_{1i},K_{i}\to 1$ as $\gamma\to 0$. Now, we can
write $\mathcal{P}_{i}$ in terms of $K_{1i},K_{i},C_{1i},C_{i}$ as

$\displaystyle\mathcal{P}_{i}=$ $\displaystyle
w_{1}\gamma^{\alpha_{1}}\bigg{[}\sum_{j}p_{1j}\log(K_{1i}+C_{1i}a_{1j})+\frac{(1-\sum_{j=1}^{n}p_{1j}\gamma^{\alpha_{1}})}{\gamma^{\alpha_{1}}}\log(K_{1i})\bigg{]}$
(21) $\displaystyle+$ $\displaystyle
w_{i}\gamma^{\alpha_{i}}\bigg{[}\sum_{j}p_{ij}\log(K_{i}-C_{i}a_{ij})+\frac{(1-\sum_{j=1}^{n}p_{ij}\gamma^{\alpha_{i}})}{\gamma^{\alpha_{i}}}\log(K_{i})\bigg{]}.$

The advantage of re-writing $\mathcal{P}_{i}$ in terms of
$K_{1i},K_{i},C_{1i},C_{i}$ is that these quantities have bounded well-defined
limits and using equations (14),(15),(16),(17), we can eliminate the
dependence on $x^{*}_{i}$ (whose behaviour is not as easy to analyze when
$\gamma\to 0$). The bounds on $K_{1i}\textrm{ and }K_{i}$ will also help us to
define the approximate version $\mathcal{P}_{i,a}$ of $\mathcal{P}_{i}$ (see 9
of main body).

###  A.5 Proof of Proposition 1

Consider i.i.d. draws of the $i$th arm. Define

$\displaystyle\tau_{ij}^{(1)}\coloneqq\textrm{the first time
}a_{ij}\gamma^{-\alpha_{i}}\textrm{ is seen in arm }i.$
$\displaystyle\tau_{ij}^{(k)}\coloneqq\textrm{the }k\textrm{th inter-arrival
time of }a_{ij}\gamma^{-\alpha_{i}}\textrm{ in arm }i.$

Then, we have that

$\mathbb{P}(\tau_{ij}^{(1)}>n)=(1-\gamma^{\alpha_{i}}p_{ij})^{n}$

Clearly, the $k$th inter-arrival time is independent of all the previous
inter-arrival times. Hence

$\mathbb{P}(\tau_{ij}^{(k)}>n_{k})=(1-\gamma^{\alpha_{i}}p_{ij})^{n_{k}}$

Now setting $n_{k}=t\gamma^{-\alpha_{i}}$ and taking the limit $\gamma\to 0$
we have

$\displaystyle\lim_{\gamma\to
0}\mathbb{P}(\tau_{ij}^{(k)}>t\gamma^{-\alpha_{i}})$
$\displaystyle=\lim_{\gamma\to
0}(1-\gamma^{\alpha_{i}}p_{ij})^{t\gamma^{-\alpha_{i}}}$
$\displaystyle=e^{p_{ij}t}$

Now as the inter-arrival times are asymptotically independent exponentially
distributed, it follows by the standard argument that $N_{ij}(t)$ is
asymptotically distributed as Poisson$(p_{ij}t)$. Note that the same argument
could have been repeated while assuming two or more support points as a set.
We would then get that the count process for the set are asymptotically
distributed as sum of the individual Poisson distributions. From computing the
Poisson mgf this implies asymptotic independence of these Poisson variables.
We omit the arguments as they are standard.

##  Appendix B Proof of Theorem 1

In this section alone, we add the superscript $e$ to $C_{i},C_{1i}$ to prevent
any confusion, since exact and approximate versions are used simultaneously.
Let $C_{1i}^{e},C_{i}^{e},x^{*}_{i,e}$ denote solutions inner minimization
problem $\mathcal{P}_{i}(w)$, and $C_{1i}^{a},C_{i}^{a},x^{*}_{i,a}$ denote
solutions to the approximate inner minimization problem
$\mathcal{P}_{i,a}(w)$. We have already established bounds on $K_{1i}$ and
$K_{i}$ in A.4. It is straightforward to see from equation 15 of the
supplementary material and equations 10 of the main body, that $0\leq
C_{1i}^{e},C_{1i}^{a}\leq\frac{\sum_{j}p_{1j}}{\mu_{i}}$, $0\leq
C_{i}^{e}\leq\frac{K_{i}}{B_{i}},C_{i}^{a}\leq\frac{1}{B_{i}}.$ Using these
bounds, one can easily use the definitions of $mathcal{P}_{i}$,
$\mathcal{P}_{i,a}$ to conclude that $\mathcal{P}_{i}$,
$\mathcal{P}_{i,a}=\mathcal{O}(\min(w_{1}\gamma^{\alpha_{1}},w_{i}\gamma^{\alpha_{i}}))$.
$\underset{\gamma\to 0}{\lim}\frac{\mathcal{P}_{i}}{\mathcal{P}_{i,a}}=1.$
becomes an immediate conclusion.

To establish the bound on $|\mathcal{P}_{i}-\mathcal{P}_{i,a}|$, we’ll follow
three broad steps: showing that the solutions to $\mathcal{P}_{i}$ also
approximately solve $\mathcal{P}_{i,a}$; showing that solutions to
$\mathcal{P}_{i}$ and solutions to $\mathcal{P}_{i,a}$ are close; using the
Lipschitz property of $\tilde{\mathcal{K}}_{inf}^{L}$ and
$\tilde{\mathcal{K}}_{inf}^{U}$ along with the triangle inequality to connect
the bounds derived in the earlier steps and arrive at the proof.
$\tilde{\mathcal{K}}_{inf}^{L}$ and $\tilde{\mathcal{K}}_{inf}^{U}$ are
defined as follows:

$\displaystyle\tilde{\mathcal{K}}_{inf}^{L}(z)=\gamma^{\alpha_{1}}\bigg{(}\sum_{j}p_{1j}\log(1+za_{1j})-z\sum_{j}\frac{a_{1j}p_{1j}}{1-za_{1j}}\bigg{)}$
$\displaystyle\tilde{\mathcal{K}}_{inf}^{U}(m,z)=\gamma^{\alpha_{i}}\bigg{(}\sum_{j}p_{ij}\log(1-za_{ij})+zm\bigg{)}$

Step 1: Solutions to exact problem approximately solve approximate problem

Bounds on $K_{1i}$ (see 20) imply that given any $\epsilon>0$, we have
$\gamma$ small enough that $K_{1i}\geq 1-\epsilon$. Then

$\log\bigg{(}\frac{1-\epsilon+C_{1i}^{e}a_{1j}}{1+C_{1i}^{e}a_{1j}}\bigg{)}\leq\log\bigg{(}\frac{K_{1i}+C_{1i}^{e}a_{1j}}{1+C_{1i}^{e}a_{1j}}\bigg{)}\leq
0.$

By Mean Value Theorem (MVT), we have that

$\log\Big{(}\frac{1-\epsilon+C_{1i}^{e}a_{1j}}{1+C_{1i}^{e}a_{1j}}\Big{)}\geq-\frac{\epsilon}{1-\epsilon}$

and hence,

$-\frac{\epsilon}{1-\epsilon}\leq\log(K_{1i}+C_{1i}^{e}a_{1j})-\log(1+C_{1i}^{e}a_{1j})\leq
0.$

Thus, for small enough $\gamma$,
$\log(1+C_{1i}^{e}a_{1j})\approx\log(K_{1i}+C_{1i}^{e}a_{1j})$.

Using the fact that $K_{1i}=1-C_{1i}^{e}x^{*}_{i,e}\gamma^{\alpha_{1}}$, we
get

$(1-\gamma^{\alpha_{1}}\sum_{j}p_{1j})\frac{\log(K_{1i})}{\gamma^{\alpha_{1}}}\leq-(1-\epsilon)C_{1i}^{e}x^{*}_{i,e}$

when $\gamma^{\alpha_{1}}\sum_{j}p_{ij}\leq\epsilon.$ Similarly, we have

$(1-\gamma^{\alpha_{1}}\sum_{j}p_{1j})\frac{\log(K_{1i})}{\gamma^{\alpha_{1}}}\geq\frac{-C_{1i}^{e}x^{*}_{i,e}}{1-C_{1i}^{e}x^{*}_{i,e}\gamma^{\alpha_{1}}}=-C_{1i}^{e}x^{*}_{i,e}+\frac{-(C_{1i}^{e}x^{*}_{i,e})^{2}\gamma^{\alpha_{1}}}{1-C_{1i}^{e}x^{*}_{i,e}\gamma^{\alpha_{1}}}$

Thus, for $\gamma$ small enough, we have
$(1-\gamma^{\alpha_{1}}\sum_{j}p_{1j})\frac{\log(K_{1i})}{\gamma^{\alpha_{1}}}\approx-
C_{1i}^{e}x^{*}_{i,e}$. In $\mathcal{K}^{L}_{inf}$ (from Lemma 2b),
$\tilde{p}$ has no probability mass on the upper bound $B_{i}$ and hence

$x^{*}_{i,e}=\sum_{j}\frac{a_{1j}p_{1j}}{1-C_{1i}^{e}a_{1j}}.$

This gives us

$|\tilde{\mathcal{K}}_{inf}^{L}(C_{1i}^{e})-\mathcal{K}_{inf}^{L}(K_{1i},C_{1i}^{e})|\leq
2\gamma^{2\alpha_{1}}\frac{(\sum_{j}p_{1j})^{2}}{1-\sum_{j}p_{1j}\gamma^{\alpha_{1}}}$

Bounds on $K_{i}$, imply that for any $\epsilon>0$, we can choose $\gamma$
(again independently of $w$) so that $K_{i}\leq 1+\epsilon.$ Then,

$0\leq\log(K_{i}+C_{i}^{e}a_{ij})-\log(1+C_{i}^{e}a_{ij})\leq\log\bigg{(}\frac{1+\epsilon+C_{i}^{e}a_{ij}}{1+C_{i}^{e}a_{ij}}\bigg{)}.$

Now, from MVT we have

$\log(1+\epsilon+C_{i}^{e}a_{ij})-\log(1+C_{i}^{e}a_{ij})\leq\frac{\epsilon}{1+C_{i}^{e}a_{ij}}\leq\epsilon.$

Thus, $\log(K_{i}+C_{i}^{e}a_{ij})\approx\log(1+C_{i}^{e}a_{ij})$ when
$\gamma$ is small. From $K_{i}=1+C_{i}^{e}x^{*}_{i,e}\gamma^{\alpha_{i}}$, we
have

$(1-\epsilon)\frac{C_{i}^{e}x^{*}_{i,e}}{1+C_{i}^{e}x^{*}_{i,e}\gamma^{\alpha_{i}}}\leq(1-\gamma^{\alpha_{i}}\sum_{j}p_{ij})\frac{\log(K_{i})}{\gamma^{\alpha_{i}}}\leq
C_{i}^{e}x^{*}_{i,e}$

when $\gamma^{\alpha_{i}}\leq\epsilon.$ Thus when $\gamma$ small,
$(1-\gamma^{\alpha_{i}}\sum_{j}p_{ij})\frac{\log(K_{i})}{\gamma^{\alpha_{i}}}\approx
C_{i}^{e}x^{*}_{i,e}$.

We thus have the following bound:

$|\mathcal{K}_{inf}^{U}(K_{i},C_{i}^{e})-\tilde{\mathcal{K}}_{inf}^{U}(x^{*}_{i,e},C_{i}^{(e)})|\leq\frac{\frac{\mu_{1}}{\underset{j}{\max}a_{ij}}\gamma^{2\alpha_{i}}}{1-\frac{\mu_{1}}{\underset{j}{\max}a_{ij}}\gamma^{\alpha_{i}}}\bigg{(}\sum_{j}p_{ij}+\frac{\mu_{1}}{\underset{j}{\max}a_{ij}}\bigg{)}$

It may be noted that the bound does not depend on $w$, which give uniform
bounds independent of $w$.

Step 2: Solutions to exact problem are close to solutions of approximate
problem

So far, we have shown that the $C_{1i}^{e},C_{i}^{e}$ and $x^{*}_{i,e}$ that
solve the exact problem are also good solutions for the approximate problem.
However, the solution to our new approximate problem will be
$C_{1i}^{a},C_{i}^{a}$ and $x^{*}_{i,a}$. We’ll now show that this set of
solutions to the approximate problem indeed approaches the set of solutions to
the actual problem at the rate of
$\gamma^{\min(2\alpha_{i},\alpha_{i}+\alpha_{1})}$ as $\gamma\to 0$.

We have that

$\displaystyle
x^{*}_{i,e}=\sum_{j=1}^{n}\frac{a_{1j}p_{1j}}{1-C_{1i}^{e}x^{*}_{i,e}\gamma^{\alpha_{1}}+C_{1i}^{e}a_{1j}},$
$\displaystyle
x^{*}_{i,a}=\sum_{j=1}^{n}\frac{a_{1j}p_{1j}}{1+C_{1i}^{a}a_{1j}},$

Note that the above two statements imply that $C_{1i}^{e}$ and $C_{1i}^{a}$
are bounded above by $\frac{\sum_{j}p_{1j}}{\mu_{i}}$. We collect the
following established results:

$\displaystyle\frac{C_{1i}^{e}}{C_{i}^{e}}=\frac{C_{1i}^{a}}{C_{i}^{a}}=\frac{w_{i}\gamma^{\alpha_{i}}}{w_{1}\gamma^{\alpha_{1}}},$
$\displaystyle x^{*}_{i,e}>F_{0}(\gamma)\Rightarrow
C_{i}^{e}=\frac{1}{B_{i}-x^{*}_{i,e}\gamma^{\alpha_{i}}},$ $\displaystyle
x^{*}_{i,a}>F_{0}(0)\Rightarrow C_{i}^{a}=\frac{1}{B_{i}},$ $\displaystyle
x^{*}_{i,e}\leq F_{0}(\gamma)\Rightarrow
x^{*}_{i,e}=\sum_{j=1}^{n}\frac{a_{ij}p_{ij}}{1+C_{i}^{e}x^{*}_{i,e}\gamma^{\alpha_{i}}-C_{i}^{e}a_{1j}}$
$\displaystyle x^{*}_{i,a}\leq F_{0}(0)\Rightarrow
x^{*}_{i,a}=\sum_{j=1}^{n}\frac{a_{ij}p_{ij}}{1-C_{i}^{e}a_{1j}}$

where $F_{0}(\gamma)$ is defined in RemarkA.1.2. In what follows, we shall let
$b_{i}=\underset{j}{\min}a_{ij}$. We shall now establish that, for all $w$,
the solution to the exact and approximate inner optimisations are close when
$\gamma$ is small. We break the analysis into the following four cases.

Case 1. $x^{*}_{i,e}\leq F_{0}(\gamma),x^{*}_{i,a}\leq F_{0}(0)$.

We have that

$\displaystyle x^{*}_{i,e}-x^{*}_{i,a}=$
$\displaystyle\sum_{j=1}^{n}\frac{a_{1j}p_{1j}(1-K_{1i}+a_{1j}(C_{1i}^{a}-C_{1i}^{e}))}{(1+C_{1i}^{a}a_{1j})(K_{1i}+C_{1i}^{e}a_{1j})}$
$\displaystyle=$
$\displaystyle\sum_{j=1}^{n}\frac{a_{ij}p_{ij}(1-K_{i}-a_{ij}(C_{i}^{a}-C_{1i}^{e}))}{(1-C_{i}^{a}a_{ij})(K_{i}-C_{i}^{(e)}a_{1j})}$

Splitting terms from the numerator and using
$\frac{C_{1i}^{e}}{C_{i}^{e}}=\frac{C_{1i}^{a}}{C_{i}^{a}}=\frac{w_{i}\gamma^{\alpha_{i}}}{w_{1}\gamma^{\alpha_{1}}}$,
we get the following:

$A(1-K_{1i})+B(1-K_{i})=\tilde{A}(C_{1i}^{e}-C_{1i}^{a})+\tilde{B}\frac{w_{1}\gamma^{\alpha_{1}}}{w_{i}\gamma^{\alpha_{i}}}(C_{1i}^{e}-C_{1i}^{a})$

where

$\displaystyle
A:=\sum_{j=1}^{n}\frac{a_{1j}p_{1j}}{(1+C_{1i}^{a}a_{1j})(K_{1i}+C_{1i}^{e}a_{1j})}$
$\displaystyle\tilde{A}:=\sum_{j=1}^{n}\frac{a_{1j}^{2}p_{1j}}{(1+C_{1i}^{a}a_{1j})(K_{1i}+C_{1i}^{e}a_{1j})}\geq
b_{1}A$ $\displaystyle
B:=\sum_{j=1}^{n}\frac{a_{ij}p_{ij}}{(1-C_{i}^{a}a_{ij})(K_{i}-C_{i}^{(e)}a_{1j})}$
$\displaystyle\tilde{B}:=\sum_{j=1}^{n}\frac{a_{ij^{2}}p_{ij}}{(1-C_{i}^{a}a_{ij})(K_{i}-C_{i}^{(e)}a_{1j})}\geq
b_{i}B$

Therefore,

$\displaystyle
C_{1i}^{e}-C_{1i}^{a}=\gamma^{\alpha_{i}}\frac{Aw_{i}(1-K_{1i})+Bw_{i}(K_{i}-1)}{\tilde{A}w_{i}\gamma^{\alpha_{i}}+\tilde{B}w_{1}\gamma^{\alpha_{1}}}$

Using equation (17), we can write that

$\displaystyle
C_{1i}^{e}-C_{1i}^{a}=\bigg{(}\frac{Aw_{i}+Bw_{1}}{\tilde{A}w_{i}\gamma^{\alpha_{i}}+\tilde{B}w_{1}\gamma^{\alpha_{1}}}\bigg{)}\gamma^{\alpha_{i}}(1-K_{1i}).$

Following this, we can use the lower bounds on $\tilde{A}$, $\tilde{B}$ and
$K_{1i}$ to conclude that

$\displaystyle|C_{1i}^{e}-C_{1i}^{a}|\leq\bigg{(}\frac{\sum_{j}p_{1j}}{\min(b_{1},b_{i})}\bigg{)}\gamma^{\min(\alpha_{1},\alpha_{i})}.$

This also tells us that

$\displaystyle|x^{*}_{i,e}-x^{*}_{i,a}|\leq\mu_{1}\bigg{(}\sum_{j=1}^{n}p_{1j}\gamma^{\alpha_{1}}+\frac{B_{1}\sum_{j}p_{1j}}{b_{1}\land
b_{i}}\gamma^{\alpha_{1}\land\alpha_{i}}\bigg{)}.$

And using a similar computation, we can also prove that

$\displaystyle|C_{i}^{e}-C_{i}^{a}|\leq\frac{\mu_{1}\gamma^{\min{\alpha_{1},\alpha_{i}}}}{min(b_{1},b_{i})(b_{i}-\mu_{1}\gamma^{\alpha_{i}})}.$

Case 2. $x^{*}_{i,e}\geq F_{0}(\gamma),x^{*}_{i,a}\geq F_{0}(0)$.

In this case, we can say that

$\displaystyle|C_{i}^{(e)}-C_{i}^{a}|=\frac{x^{*}_{i,e}}{B_{i}(B_{i}-x^{*}_{i,e}\gamma^{\alpha_{i}})}\gamma^{\alpha_{i}}$

We also have that

$\displaystyle
x^{*}_{i,e}=\sum_{j=1}^{n}\frac{a_{1j}p_{1j}}{1+\frac{w_{i}\gamma^{\alpha_{i}}}{w_{1}\gamma^{\alpha_{1}}}C_{i}^{(e)}(a_{1j}-x^{*}_{i,e}\gamma^{\alpha_{1}})}$
$\displaystyle
x^{*}_{i,a}=\sum_{j=1}^{n}\frac{a_{1j}p_{1j}}{1+\frac{w_{i}\gamma^{\alpha_{I}}}{w_{1}\gamma^{\alpha_{1}}}C_{i}^{a}a_{1j}}.$

Subtracting the two gives us that

$\displaystyle|x^{*}_{i,e}-x^{*}_{i,a}|\leq\sum_{j=1}^{n}\frac{a_{1j}p_{1j}\mu_{i}}{a_{1j}-\mu_{1}\gamma^{\alpha_{i}}}\gamma^{\alpha_{1}}+\sum_{j=1}^{n}\frac{a_{1j}^{2}p_{1j}\mu_{i}}{B_{i}(a_{1j}-\mu_{1}\gamma^{\alpha_{i}})}\gamma^{\alpha_{i}}.$

The above relation, along with the relation between $|C_{1i}^{e}-C_{1i}^{a}|$
and $|x^{*}_{i,e}-x^{*}_{i,a}|$ as outlined under Case I, may be used to prove
that

$\displaystyle|C_{1i}^{e}-C_{1i}^{a}|\leq
D_{i}\gamma^{\min(\alpha_{1},\alpha_{i})}$

where $D_{i}$ is constant depending on arm $p_{i}$.

Case 3. $F_{0}(\gamma)\leq x^{*}_{i,e},x^{*}_{i,a}\leq F_{0}(0)$.

A direct conclusion here would be

$\displaystyle|x^{*}_{i,e}-x^{*}_{i,a}|\leq|F_{0}(0)-F_{0}(\gamma)|\leq\frac{B_{i}}{{1+\gamma^{\alpha_{i}}\sum_{j}\frac{a_{ij}p_{ij}}{B_{i}-a_{ij}}}}\big{(}\sum_{j=1}^{n}\frac{a_{ij}p_{ij}}{B_{i}-a_{ij}}\big{)}^{2}\gamma^{\alpha_{i}}$

We have that

$\displaystyle
x^{*}_{i,e}-x^{*}_{i,a}=\sum_{j=1}^{n}\frac{a_{1j}p_{1j}(1-K_{1i}+a_{1j}(C_{1i}^{a}-C_{1i}^{e}))}{(1+C_{1i}^{a}a_{1j})(K_{1i}+C_{1i}^{e}a_{1j})}$

whence we can conclude that

$\displaystyle|C_{1i}^{e}-C_{1i}^{a}|\leq\frac{(|x^{*}_{i,e}-x^{*}_{i,a}|+C^{(e)}x^{*}_{i,e}\sum_{j=1}^{n}a_{1j}p_{1j}\gamma^{\alpha_{1}})}{\frac{b_{1}\mu_{i}}{1+B_{1}C^{(a)}}}$
$\displaystyle\Rightarrow$ $\displaystyle|C_{1i}^{e}-C_{1i}^{a}|\leq
D_{i}\gamma^{\min(\alpha_{1},\alpha_{i})}$

where $D_{i}$ is again a constant depending on arm $p_{i}$. Lastly, we can
show that

$\displaystyle|C_{i}^{e}-\frac{1}{B_{i}}|\leq\frac{(1-b_{i}/B_{i})}{b_{i}\mu_{i}}B_{i}\bigg{(}\sum_{j}\frac{a_{ij}p_{ij}}{B_{i}-a_{ij}}\bigg{)}^{2}\gamma^{\alpha_{i}}$
$\displaystyle|C_{i}^{a}-\frac{1}{B_{i}}|\leq\frac{\mu_{1}}{B_{i}(B_{i}-\mu_{1}\gamma^{\alpha_{i}})}.\gamma^{\alpha_{i}}$

to conclude that

$\displaystyle|C_{i}^{e}-C_{i}^{a}|\leq\frac{(1-b_{i}/B_{i})}{b_{i}\mu_{i}}B_{i}\bigg{(}\sum_{j}\frac{a_{ij}p_{ij}}{B_{i}-a_{ij}}\bigg{)}^{2}\gamma^{\alpha_{i}}+\frac{\mu_{1}}{B_{i}(B_{i}-\mu_{1}\gamma^{\alpha_{i}})}.\gamma^{\alpha_{i}}$

Case 4. $x^{*}_{i,e}\leq F_{0}(\gamma)<F_{0}(0)\leq x^{*}_{i,a}$.

We first show that $1/B_{i}<C_{i}^{e}$. Suppose this is false. Then,
$C_{i}^{a}=1/B_{i}\geq C_{i}^{e}$. From equation (14) for fixed $w_{1},w_{i}$
and $\gamma$, we have:

$\displaystyle C_{1i}^{a}\geq C_{1i}^{e}\Rightarrow
x^{*}_{i,e}>\sum_{j}\frac{a_{1j}p_{1j}}{1+C_{1i}^{e}a_{1j}}$
$\displaystyle>\sum_{j}\frac{a_{1j}p_{1j}}{1+C_{1i}^{a}a_{1j}}=x^{*}_{i,a}$

But this contradicts the hypothesis of this case. Hence we must have have:

$\frac{1}{B_{i}}<C_{i}^{e}<\frac{1}{B_{i}-x^{*}_{i,e}\gamma^{\alpha_{i}}}$

As $C_{i}^{a}=\frac{1}{B_{i}}$, from above we have

$1<\frac{C_{i}^{e}}{C_{i}^{a}}=\frac{C_{1i}^{e}}{C_{1i}^{a}}\leq
1+\frac{x^{*}_{i,e}\gamma^{\alpha_{i}}}{B_{i}-x^{*}_{i,e}\gamma^{\alpha_{i}}}$

And we can conclude that

$\displaystyle|C_{i}^{a}-C_{1i}^{a}|\leq\frac{\mu_{1}}{B_{i}-\mu_{1}\gamma^{\alpha_{1}}}\gamma^{\alpha_{i}}$
$\displaystyle|C_{1i}^{a}-C_{1i}^{e}|\leq\frac{(\sum_{j}p_{1j})\mu_{1}}{\mu_{i}(B_{i}-\mu_{1}\gamma^{\alpha_{i}})}\gamma^{\alpha_{i}}$
$\displaystyle|x^{*}_{i,a}-x^{*}_{i,e}|\leq\frac{\mu_{i}^{2}B_{i}^{2}}{B_{i}-\mu_{i}}\gamma^{\min\\{\alpha_{1},\alpha_{i}\\}}$

This completes the analysis of the four cases and shows that
$C_{1i}^{a},C_{i}^{a},x^{*}_{i,a}$ are close to
$C_{1i}^{e},C_{i}^{e},x^{*}_{i,e}$ when $\gamma$ is small.

Step 3: Connecting solutions to exact problem and solutions to approximate
problem

We concluded in Step 1 that

$|\tilde{\mathcal{K}}_{inf}^{L}(C_{1i}^{e})-\mathcal{K}_{inf}^{L}(K_{1i},C_{1i}^{e})|\leq
2\gamma^{2\alpha_{1}}\frac{(\sum_{j}p_{1j})^{2}}{1-\sum_{j}p_{1j}\gamma^{\alpha_{1}}}$

and in Step 2 that $|C_{1i}^{e}-C_{1i}^{a}|$ is related to
$|x^{*}_{i,e}-x^{*}_{i,a}|$ by the equation

$|C_{1i}^{e}-C_{1i}^{a}|\leq\frac{|x^{*}_{i,e}-x^{*}_{i,a}|+\sum_{j}a_{1j}p_{1j}C_{1i}^{e}x^{*}_{i,e}\gamma^{\alpha_{1}}}{\sum_{j}\frac{a_{1j}^{2}p_{1j}}{(1+C_{1i}^{a}a_{1j})(1+C_{1i}^{e}(a_{1j}-x^{*}_{i,e}\gamma^{\alpha_{1}}))}}\leq\frac{|x^{*}_{i,e}-x^{*}_{i,a}|+\mu_{1}\sum_{j}p_{1j}\gamma^{\alpha_{1}}}{\mu_{2}\Big{(}\frac{b_{1}}{1+B_{1}\sum_{j}p_{1j}/\mu_{2}}\Big{)}}$

We have:

$\frac{d}{dz}\tilde{\mathcal{K}}_{inf}^{L}(z)=\gamma^{\alpha_{i}}\bigg{(}\sum_{j}\frac{a_{1j}p_{1j}}{1+za_{1j}}-\sum_{j}\frac{a_{1j}p_{1j}}{1-za_{1j}}-z\sum_{j}\frac{a_{1j}^{2}p_{1j}}{1-za_{1j}}\bigg{)}$

Now, the derivative of $\tilde{\mathcal{K}}_{inf}^{L}$ can easily be bounded
above by $\mu_{1}\gamma^{\alpha_{1}}$. This leads us to the following
conclusion.

$|\tilde{\mathcal{K}}_{inf}^{L}(C_{1i}^{e})-\tilde{\mathcal{K}}_{inf}^{L}(C_{1i}^{a})|\leq\frac{\mu_{1}^{2}B_{1}}{\mu_{i}b_{1}}\Bigg{[}\frac{\frac{\mu_{1}^{3}}{\mu_{i}b_{1}}\gamma^{\alpha_{1}}+\mu_{1}^{2}(1+\frac{B_{1}\lor
B_{i}}{b_{1}\land
b_{i}})\frac{1}{(b_{i}-\mu_{1}\gamma^{\alpha_{i}})}\gamma^{\alpha_{1}\land\alpha_{i}}}{\mu_{i}\Big{(}\frac{b_{i}}{1+\frac{\mu_{1}B_{1}}{\mu_{i}b_{1}}}\Big{)}}\Bigg{]}\gamma^{\alpha_{1}}=\mathcal{O}(\gamma^{(2\alpha_{1})\land(\alpha_{1}+\alpha_{i})})$

where we have used the inequalities
$C^{e}_{1i},C^{a}_{1i}\leq\frac{\sum_{j}p_{1j}}{\mu_{i}}$ and
$b_{1}\sum_{j}p_{1j}\leq\mu_{1}$.

We thus have,

$\begin{split}|\mathcal{K}_{inf}^{L}(K_{1i},C_{1i}^{e})-\tilde{\mathcal{K}}_{inf}^{L}(C_{1i}^{a})|\leq|\mathcal{K}_{inf}^{L}(K_{1i},C_{1i}^{e})-\tilde{\mathcal{K}}_{inf}^{L}(C_{1i}^{e})|+|\tilde{\mathcal{K}}_{inf}^{L}(C_{1i}^{e})-\tilde{\mathcal{K}}_{inf}^{L}(C_{1i}^{a})|\leq
L_{1i}\gamma^{(2\alpha_{1})\land(\alpha_{1}+\alpha_{i})}\end{split}$

where $L_{1i}$ is a computable constant, and
$L_{1i}\gamma^{(2\alpha_{1})\land(\alpha_{1}+\alpha_{i})}$ can be computed by
adding the bounds on
$|\mathcal{K}_{inf}^{L}(K_{1i},C_{1i}^{e})-\tilde{\mathcal{K}}_{inf}^{L}(C_{1i}^{e})|$
and
$|\tilde{\mathcal{K}}_{inf}^{L}(C_{1i}^{e})-\tilde{\mathcal{K}}_{inf}^{L}(C_{1i}^{a})|$.

Similarly from Step 1 we have:

$\displaystyle|\mathcal{K}_{inf}^{U}(K_{i},C_{i}^{e})-\tilde{\mathcal{K}}_{inf}^{U}(x^{*}_{i,e},C_{i}^{e})|\leq\frac{\frac{\mu_{1}}{\underset{j}{\max}a_{ij}}\gamma^{2\alpha_{i}}}{1-\frac{\mu_{1}}{\underset{j}{\max}a_{ij}}\gamma^{\alpha_{i}}}\bigg{(}\sum_{j}p_{ij}+\frac{\mu_{1}}{\underset{j}{\max}a_{ij}}\bigg{)}$

To upper bound
$|\mathcal{K}_{inf}^{U}(K_{i},C_{i}^{e})-\tilde{\mathcal{K}}_{inf}^{U}(x^{*}_{i,a},C_{i}^{a})|$,
we can follow a procedure similar to how
$|\mathcal{K}_{inf}^{L}(K_{1i},C_{1i}^{e})-\tilde{\mathcal{K}}_{inf}^{L}(C_{1i}^{a})|$
was bounded. We first use the triangle inequality to make the following split.

$\displaystyle|\mathcal{K}_{inf}^{U}(K_{i},C_{i}^{e})-\tilde{\mathcal{K}}_{inf}^{U}(x^{*}_{i,a},C_{i}^{a})|$
$\displaystyle\leq|\mathcal{K}_{inf}^{U}(K_{i},C_{i}^{e})-\tilde{\mathcal{K}}_{inf}^{U}(x^{*}_{i,e},C_{i}^{e})|+|\tilde{\mathcal{K}}_{inf}^{U}(x^{*}_{i,e},C_{i}^{e})-\tilde{\mathcal{K}}_{inf}^{U}(x^{*}_{i,e},C_{i}^{a})|$
$\displaystyle+|\tilde{\mathcal{K}}_{inf}^{U}(x^{*}_{i,e},C_{i}^{a})-\tilde{\mathcal{K}}_{inf}^{U}(x^{*}_{i,a},C_{i}^{a})|$

In the right hand side of the above inequality, the bound to the first summand
was already obtained. The second and third summands can be bounded above by
showing that $\tilde{\mathcal{K}}_{inf}^{U}$ is Lipschitz in both its
arguments, the Lipschitz constants being computable ones. Thus, we have

$\displaystyle|\tilde{\mathcal{K}}_{inf}^{U}(x^{*}_{i,e},C_{i}^{e})-\tilde{\mathcal{K}}_{inf}^{U}(x^{*}_{i,e},C_{i}^{a})|$
$\displaystyle\leq\gamma^{\alpha_{i}}(\mu_{1}-\mu_{i})|C_{i}^{e}-C_{i}^{a}|$
$\displaystyle\leq\frac{\mu_{1}(\mu_{1}-\mu_{2})}{(b_{1}\land
b_{i})(b_{i}-\mu_{1}\gamma^{\alpha_{i}})}\gamma^{(\alpha_{1}+\alpha_{i})\land(2\alpha_{i})}$
$\displaystyle+\frac{(B_{i}-b_{i})(\mu_{1}-\mu_{2})}{b_{i}\mu_{i}}\bigg{(}\sum_{j=1}^{n}\frac{a_{1j}p_{1j}}{B_{i}-a_{ij}}\bigg{)}^{2}\gamma^{2\alpha_{i}}..$

The bound in the first step was derived by bounding the partial derivative wrt
$z$ of $\tilde{\mathcal{K}}_{inf}^{U}(m,z)$. Similarly bounding the partial
derivative wrt $m$ gives

$\displaystyle|\tilde{\mathcal{K}}_{inf}^{U}(x^{*}_{i,e},C_{i}^{a})-\tilde{\mathcal{K}}_{inf}^{U}(x^{*}_{i,a},C_{i}^{a})|\leq\gamma^{\alpha_{i}}\frac{|x^{*}_{i,e}-x^{*}_{i,a}|}{b_{i}}$

$|x^{*}_{i,e}-x^{*}_{i,a}|$ is bounded above by the maximum of the upper
bounds derived in the four cases of Step 2. We can therefore conclude that,

$|\mathcal{K}_{inf}^{U}(K_{i},C_{i}^{e})-\tilde{\mathcal{K}}_{inf}^{U}(x^{*}_{i,a},C_{i}^{a})|\leq
L_{i}\gamma^{(\alpha_{1}+\alpha_{i})\land(2\alpha_{i})}$

where $L_{i}$ can be computed as described above. The upper bounds on
$|\mathcal{K}_{inf}^{L}(K_{1i},C_{1i}^{e})-\tilde{\mathcal{K}}_{inf}^{L}(C_{1i}^{a})|$
and
$|\mathcal{K}_{inf}^{U}(K_{i},C_{i}^{e})-\tilde{\mathcal{K}}_{inf}^{U}(x^{*}_{i,a},C_{i}^{a})|$
give us the proof of Theorem 3. The upper bound on $|V^{*}(p)-V^{*}_{a}(p)|$
can be inferred immediately.

##  Appendix C Proof of Theorem 2

The proof goes through the following steps: first we analyse the behavior of
equation (12) and derive some constraints it imposes on the asymptotic
behavior of $C_{1i}^{a},C_{i}^{a}$; utilising this, we then analyse the
behaviour of equation (11) and finally get the five asymptotic regimes noted
in the Theorem.
Step 1: Constraint imposed by equation (12) in the asymptotic behaviours of
$C_{1i}^{a},C_{i}^{a}$.
We first observe that $C_{1i}^{a}\to 0,C_{i}^{a}\to 0$ as $\gamma\to 0$ cannot
happen for any $i\in[K]\backslash\\{1\\}$, because then equation 10 would
imply that
$\mu_{1}=\sum_{j=1}^{n}a_{1j}p_{1j}=\sum_{j=1}^{n}a_{ij}p_{ij}=\mu_{i}$.

Equation (12) from the main body can be re-written (using envelope theorem) as

$\displaystyle
w_{1}\gamma^{\alpha_{1}}\bigg{(}\sum_{j}p_{1j}\log(1+C_{1i}^{a}a_{1j})-C_{1i}^{a}x^{*}_{i,a}\bigg{)}+w_{i}\gamma^{\alpha_{i}}\bigg{(}\sum_{j}p_{ij}\log(1-C_{i}^{a}a_{ij})+C_{i}^{a}x^{*}_{i,a}\bigg{)}$
$\displaystyle=$ $\displaystyle
w_{1}\gamma^{\alpha_{1}}\bigg{(}\sum_{j}p_{1j}\log(1+C_{1k}^{a}a_{1j})+C_{1i}^{a}x^{*}_{k,a}\bigg{)}+w_{k}\gamma^{\alpha_{i}}\bigg{(}\sum_{j}p_{kj}\log(1-C_{i}^{a}a_{kj})-C_{i}^{a}x^{*}_{k,a}\bigg{)}$

for all $i\neq k$, $i,k\neq 1$. Using equation
$w_{1}C_{1i}^{a}\gamma^{\alpha_{1}}=w_{i}C_{i}^{a}\gamma^{\alpha_{i}}$, we can
simplify this equation to

$\frac{\sum_{j}p_{1j}\log(1+C_{1i}^{a}a_{1j})+\frac{C_{1i}^{a}}{C_{i}^{a}}\sum_{j}p_{ij}\log(1-C_{i}^{a}a_{ij})}{\sum_{j}p_{1j}\log(1+C_{1k}^{a}a_{1j})+\frac{C_{1k}^{a}}{C_{k}^{a}}\sum_{j}p_{kj}\log(1-C_{k}^{a}a_{kj})}=1$
(22)

for all $i\neq k$. We also re-write (10) from the main body as

$\sum_{j}\frac{a_{1j}p_{1j}}{1+C_{1i}^{a}a_{1j}}=\sum_{j}\frac{a_{ij}p_{ij}}{1-C_{i}^{a}a_{ij}}.$
(23)

Now, we analyze the asymptotic behavior of equation (22) as $\gamma\to 0$ on a
case-by-case basis.

Case 1: $C_{1i}^{a}\to A_{1}^{a}(>0),C_{i}\to 0;C_{1k}^{a}\to
A_{1k}^{a}(>0),C_{k}^{a}\to 0.$

Taking the limit in equation (22) we get

$\displaystyle 1=$ $\displaystyle\lim_{\gamma\to
0}\frac{\sum_{j}p_{1j}\log(1+C_{1i}^{a}a_{1j})+\frac{C_{1i}^{a}}{C_{i}^{a}}\sum_{j}p_{ij}\log(1-C_{i}^{a}a_{ij})}{\sum_{j}p_{1j}\log(1+C_{1k}^{a}a_{1j})+\frac{C_{1k}^{a}}{C_{k}^{a}}\sum_{j}p_{kj}\log(1-C_{k}^{a}a_{kj})}$
$\displaystyle=$
$\displaystyle\frac{\sum_{j}p_{1j}\log(1+A_{1i}^{a}a_{1j})-A_{1i}^{a}\sum_{j}a_{ij}p_{ij}}{\sum_{j}p_{1j}\log(1+A_{1k}^{a}a_{1j})-A_{1k}^{a}\sum_{j}a_{kj}p_{kj}}$

Taking $\gamma\to 0$ in (15), we have that

$\displaystyle\sum_{j}\frac{a_{1j}p_{1j}}{1+A_{1i}a_{1j}}=\sum_{j}a_{ij}p_{ij}$
$\displaystyle\sum_{j}\frac{a_{1j}p_{1j}}{1+A_{1k}a_{1j}}=\sum_{j}a_{kj}p_{kj}$

Hence,

$\frac{\sum_{j}f_{j}(A_{1i})}{\sum_{j}f_{j}(A_{1k})}=1$

where $f_{j}(x):=p_{1j}[\log(1+a_{1j}x)-\frac{xa_{1j}}{1+xa_{1j}}]$. It is
easy to check that $f$ is a monotonically increasing function, and therefore
the above equation must imply $A_{1i}=A_{1k}$. But this also means that
$\mu_{i}=\mu_{k}$, which is against our assumption of all means being
distinct.

Case 2: $C_{1i}^{a}\to A_{1i}(>0),C_{i}^{a}\to 0,C_{1k}^{a}\to 0,C_{k}^{a}\to
A_{k}(>0)$

As in Case 1 we take the asymptotic limit on 22 to get

$\displaystyle 1=$ $\displaystyle\lim_{\gamma\to
0}\frac{\sum_{j}p_{1j}\log(1+C_{1i}^{a}a_{1j})+\frac{C_{1i}^{a}}{C_{i}^{a}}\sum_{j}p_{ij}\log(1-C_{i}^{a}a_{ij})}{\sum_{j}p_{1j}\log(1+C_{1k}^{a}a_{1j})+\frac{C_{1k}^{a}}{C_{k}^{a}}\sum_{j}p_{kj}\log(1-C_{k}^{a}a_{kj})}$
$\displaystyle=$ $\displaystyle\lim_{\gamma\to
0}\frac{\sum_{j}p_{1j}\log(1+A_{1i}^{a}a_{1j})-A_{1i}^{a}\sum_{j}a_{ij}p_{ij}}{\sum_{j}p_{1j}\log(1+C_{1k}^{a}a_{1j})-\frac{C_{1k}^{a}}{A_{k}}\sum_{j}p_{kj}\log(1-A_{k}^{a}a_{kj})}$

which is impossible, because the denominator of the right hand side approaches
$0$ as $\gamma\to 0$.

Case 3: $C_{1i}^{a}\to A_{1i}(>0),C_{i}^{a}\to A_{i}(>0),C_{1k}^{a}\to
0,C_{k}^{a}\to A_{k}(>0)$

We have that

$\displaystyle 1=$ $\displaystyle\lim_{\gamma\to
0}\frac{\sum_{j}p_{1j}\log(1+C_{1i}^{a}a_{1j})+\frac{C_{1i}^{a}}{C_{i}^{a}}\sum_{j}p_{ij}\log(1-C_{i}^{a}a_{ij})}{\sum_{j}p_{1j}\log(1+C_{1k}^{a}a_{1j})+\frac{C_{1k}^{a}}{C_{k}^{a}}\sum_{j}p_{kj}\log(1-C_{k}^{a}a_{kj})}$
$\displaystyle=$ $\displaystyle\lim_{\gamma\to
0}\frac{\sum_{j}p_{1j}\log(1+A_{1i}^{a}a_{1j})+\frac{A_{1i}^{a}}{A_{i}^{a}}\sum_{j}p_{ij}\log(1-A_{i}^{a}a_{ij})}{\sum_{j}p_{1j}\log(1+C_{1k}^{a}a_{1j})-\frac{C_{1k}^{a}}{A_{k}}\sum_{j}p_{kj}\log(1-A_{k}^{a}a_{kj})}$

which is impossible, because the denominator of the left hand side approaches
$0$ as $\gamma\to 0$. That only leaves us with only the following three
possibilities.

Case 4: $C_{1i}^{a}\to A_{1i}(\neq 0),C_{i}^{a}\to A_{i}(\neq 0),C_{1k}^{a}\to
A_{1k}(\neq 0),C_{k}^{a}\to A_{k}(\neq 0)$

From 22, we know

$\lim_{\gamma\to
0}\frac{\sum_{j}p_{1j}\log(1+C_{1i}^{a}a_{1j})+\frac{w_{i}\gamma^{\alpha_{i}}}{w_{1}\gamma^{\alpha_{1}}}\sum_{j}p_{ij}\log(1-C_{i}^{a}a_{ij})}{\sum_{j}{p_{1j}\log(1+C_{1k}^{a}a_{1j})+\frac{w_{k}\gamma^{\alpha_{k}}}{w_{1}\gamma^{\alpha_{1}}}\sum_{j}p_{kj}\log(1-C_{k}^{a}a_{kj})}}$

which cannot be ruled out as an impossibility.

Case 5: $C_{1i}^{a}\to 0,C_{i}{a}\to A_{i}(\neq 0),C_{1k}^{a}\to
0,C_{k}^{a}\to A_{k}(\neq 0)$

Using
$C_{1i}^{a}w_{1}\gamma^{\alpha_{1}}=C_{i}^{a}w_{i}\gamma^{\alpha_{i}}=\lambda_{i}\
\forall i\neq 1$ on 22 gives us that

$\displaystyle\lim_{\gamma\to
0}\frac{C_{1i}^{a}}{C_{1k}^{a}}\frac{\sum_{j}p_{1j}\frac{\log(1+C_{1i}^{a}a_{1j})}{C_{1i}^{a}}+\sum_{j}p_{ij}\frac{\log(1-C_{i}{a}a_{ij})}{C_{i}^{a}}}{\sum_{j}p_{1j}\frac{\log(1+C_{1k}^{a}a_{1j})}{C_{1k}^{a}}+\sum_{j}p_{kj}\frac{\log(1-C_{k}^{a}a_{kj})}{C_{k}^{a}}}$
$\displaystyle=$ $\displaystyle\lim_{\gamma\to
0}\frac{C_{1i}^{a}}{C_{1k}^{a}}\bigg{(}\frac{\sum_{j}a_{1j}p_{1j}+\sum_{j}\frac{p_{i}j}{A_{i}}\log(1-A_{i}a_{ij})}{\sum_{j}a_{1j}p_{1j}+\sum_{j}\frac{p_{kj}}{A_{k}}\log(1-A_{k}a_{kj})}\bigg{)}=1$
$\displaystyle\Rightarrow$ $\displaystyle\lim_{\gamma\to
0}\frac{C_{1i}^{a}}{C_{1k}^{a}}=\frac{\sum_{j}a_{1j}p_{1j}+\sum_{j}\frac{p_{kj}}{A_{k}}\log(1-A_{k}a_{kj})}{\sum_{j}a_{1j}p_{1j}+\frac{p_{ij}}{A_{i}}\log(1-A_{i}a_{ij})}$
$\displaystyle\Rightarrow$ $\displaystyle\lim_{\gamma\to
0}\frac{C_{i}^{a}w_{i}\gamma^{\alpha_{i}}}{C_{k}^{a}w_{k}\gamma^{\alpha_{k}}}=\bigg{(}\frac{\sum_{j}a_{1j}p_{1j}+\sum_{j}\frac{p_{kj}}{A_{k}}\log(1-A_{k}a_{kj})}{\sum_{j}a_{1j}p_{1j}+\sum_{j}\frac{p_{ij}}{A_{i}}\log(1-A_{i}a_{ij})}\bigg{)}$

Case 6: $C_{1i}^{a}\to A_{1i}(\neq 0),C_{i}^{a}\to 0,C_{1k}^{a}\to A_{1k}(\neq
0),C_{k}^{a}\to A_{k}(\neq 0)$

Using
$C_{1i}^{a}w_{1}\gamma^{\alpha_{1}}=C_{i}^{a}w_{i}\gamma^{\alpha_{i}}=\lambda_{i}\
\forall i\neq 1$ on 22 gives us that

$\displaystyle\lim_{\gamma\to
0}\frac{C_{1i}^{a}}{C_{1k}^{a}}\frac{\sum_{j}p_{1j}\frac{\log(1+C_{1i}^{a}a_{1j})}{C_{1s}^{a}}+\sum_{j}p_{ij}\frac{\log(1-C_{i}^{a}a_{ij})}{C_{i}^{a}}}{\sum_{j}p_{1j}\frac{\log(1+C_{1k}^{a}a_{1j})}{C_{1k}^{a}}+\sum_{j}p_{kj}\frac{\log(1-C_{k}^{a}a_{kj})}{C_{k}^{a}}}$
$\displaystyle=$
$\displaystyle\frac{\sum_{j}p_{1j}\log(1+A_{1i}a_{1j})-A_{1i}\mu_{i}}{\sum_{j}p_{1j}\log(1+A_{1k}a_{1j})+\frac{A_{1k}}{A_{k}}\sum_{j}p_{kj}\log(1-A_{k}a_{kj})}=1$

Step 2: Analysis of equation 11 of the main body.

The Envelope Theorem guarantees that equation 11 of the main body can be
rewritten as

$\sum_{i=2}^{K}\frac{KL(p_{1},\tilde{p}_{1}^{(i)})}{KL(p_{i},\tilde{p}_{i})}=\sum_{i=2}^{K}\frac{\gamma^{\alpha_{1}}(\sum_{j}p_{1j}\log(1+C_{1i}^{a}a_{1j})-C_{1i}^{a}\sum_{j}a_{1j}\tilde{p}_{1j}^{(i)})}{\gamma^{\alpha_{i}}(\sum_{j}p_{ij}\log(1-C_{i}^{a}a_{ij})+C_{i}^{a}\sum_{j}a_{ij}\tilde{p}_{ij})}=1$
(24)

because $\frac{\partial\mathcal{P}_{i,a}(w^{*})}{\partial
w_{1}}=KL(p_{1},\tilde{p}_{1}^{i})$ and
$\frac{\partial\mathcal{P}_{i,a}(w^{*})}{\partial
w_{i}}=KL(p_{i},\tilde{p}_{i})$. We shall use this form of equation 11 to
derive expressions for $w_{i},\ i\in[K]\backslash\\{1\\}$ under the following
cases:

Case 1: $\alpha_{1}\neq\alpha_{max},$
Case 2: $\alpha_{1}=\alpha_{max}>\alpha_{i},\ \forall i\neq 1,$
Case 3: $\alpha_{1}=\alpha_{2}=\alpha_{max}>\alpha_{i},\ \forall i\neq 1,2,$
Case 4: $\alpha_{1}=\alpha_{k}=\alpha_{max}\geq\alpha_{i},\
i\notin\\{1,2,k\\}$, $\alpha_{max}>\alpha_{2}$ and $\zeta>1$
Case 5: $\alpha_{1}=\alpha_{k}=\alpha_{max}\geq\alpha_{i},\
i\notin\\{1,2,k\\}$, $\alpha_{max}>\alpha_{2}$ and $\zeta\leq 1$

where $\alpha_{max}:=\max_{i}\alpha_{i}$. We shall first show that Case 1 is
equivalent to $C_{1i}^{a}\to 0,C_{i}^{a}\to A_{i}(\neq 0)\forall i\neq 1$

For the “if" direction, let us assume that $\alpha_{1}\geq\alpha_{i}$ for all
$i\in[K]\backslash\\{1\\}$. In the limit as $\gamma\to 0$, we then get that

$\sum_{i=2}^{K}\frac{KL(p_{1},\tilde{p}_{1}^{(i)})}{KL(p_{i},\tilde{p}_{i})}=\sum_{i=2}^{K}\frac{\gamma^{\alpha_{1}}(\sum_{j}p_{1j}\log(1+C_{1i}^{a}a_{1j})-C_{1i}^{a}\sum_{j}a_{1j}\tilde{p}_{1j}^{(i)})}{\gamma^{\alpha_{i}}(\sum_{j}p_{ij}\log(1-C_{i}^{a}a_{ij})+C_{i}^{a}\sum_{j}a_{ij}\tilde{p}_{ij})}=1\Rightarrow
0=1$

which is an absurdity.

For the “only if" direction, let us suppose that for some
$k\in[K]\backslash\\{1\\}$, $\alpha_{1}<\alpha_{k}$. If $C_{k}^{a}\to 0$, from
our analysis in Step 1, we can conclude that $C_{1k}^{a}\to A_{1k}(\neq 0)$.
Therefore,

$\gamma^{\alpha_{1}-\alpha_{k}}\frac{(\sum_{j}p_{1j}\log(1+C_{1k}^{a}a_{1j})-C_{1k}^{a}\sum_{j}a_{1j}\tilde{p}_{1j}^{(k)})}{(\sum_{j}p_{kj}\log(1-C_{k}^{a}a_{kj})+C_{k}^{a}\sum_{j}a_{kj}\tilde{p}_{kj})}\to\infty\
\textrm{as}\ \gamma\to 0$

contradicting
$\sum_{i=2}^{K}\frac{\gamma^{\alpha_{1}}(\sum_{j}p_{1j}\log(1+C_{1i}^{a}a_{1j})-C_{1i}^{a}\sum_{j}a_{1j}\tilde{p}_{1j}^{(i)})}{\gamma^{\alpha_{i}}(\sum_{j}p_{ij}\log(1+C_{i}^{a}a_{ij})+C_{i}^{a}\sum_{j}a_{ij}\tilde{p}_{ij})}=1$.

From our analysis in Step 1, we can conclude that $C_{k}^{a}\to A_{k}(\neq 0)$
implies that $C_{1k}^{a}\to 0$ and consequently, $C_{1i}^{a}\to 0,C_{i}^{a}\to
A_{i}(\neq 0)\ \forall i\neq 1$.

Let $\alpha_{max}=\alpha_{k}$. Since $C_{1i}^{a}\to 0,C_{i}^{a}\to A_{i}(\neq
0)\ \forall i\neq 1$, we can use Taylor series expansions to write

$\displaystyle\lim_{\gamma\to
0}\sum_{i=2}^{K}\frac{\gamma^{\alpha_{1}}(\sum_{j}p_{1j}\log(1+C_{1i}^{a}a_{1j})-C_{1i}^{a}\sum_{j}a_{1j}\tilde{p}_{1j}^{(i)})}{\gamma^{\alpha_{i}}(\sum_{j}p_{ij}\log(1+C_{i}^{a}a_{ij})+C_{i}^{a}\sum_{j}a_{ij}\tilde{p}_{ij})}=1$
$\displaystyle\Rightarrow$ $\displaystyle\lim_{\gamma\to
0}\sum_{i=2}^{K}\frac{\frac{(C^{a}_{1i})^{2}\sum_{j}a_{1j}^{2}p_{1j}}{2}\gamma^{\alpha_{1}-\alpha_{i}}}{(\sum_{j}p_{ij}\log(1+C_{i}^{a}a_{ij})+C_{i}^{a}\sum_{j}a_{ij}\tilde{p}_{ij})}=1$

We know that
$C_{1i}^{a}=C_{i}^{a}\frac{w_{i}\gamma^{\alpha_{i}}}{w_{1}\gamma^{\alpha_{1}}}$.
This substitution will give us

$\displaystyle\lim_{\gamma\to
0}\sum_{i=2}^{K}\frac{\frac{(C^{a}_{i})^{2}\sum_{j}a_{1j}^{2}p_{1j}}{2}}{(\sum_{j}p_{ij}\log(1+C_{i}^{a}a_{ij})+C_{i}^{a}\sum_{j}a_{ij}\tilde{p}_{ij})}\bigg{(}\frac{w_{i}}{w_{1}}\bigg{)}^{2}\gamma^{\alpha_{i}-\alpha_{1}}=1$
$\displaystyle\Rightarrow$ $\displaystyle\sum_{i=2}^{K}\lim_{\gamma\to
0}M_{i}\bigg{(}\frac{w_{i}}{w_{1}}\bigg{)}^{2}\gamma^{\alpha_{i}-\alpha_{1}}=1;\textrm{where
}M_{i}:=\frac{\frac{(C^{a}_{i})^{2}\sum_{j}a_{1j}^{2}p_{1j}}{2}}{(\sum_{j}p_{ij}\log(1+C_{i}^{a}a_{ij})+C_{i}^{a}\sum_{j}a_{ij}\tilde{p}_{ij})}$

If $\alpha_{i}<\alpha_{1}$, then $\gamma^{\alpha_{i}-\alpha_{1}}$ must go to
$\infty$ as $\gamma\to 0$. But $M_{i}$ being bounded and
$M_{i}\big{(}\frac{w_{i}}{w_{1}}\big{)}^{2}\gamma^{\alpha_{i}-\alpha_{1}}\leq
1$ implies that
$\frac{w_{i}}{w_{1}}\leq\frac{1}{M_{i}}\gamma^{\frac{\alpha_{1}-\alpha_{i}}{2}}$.
Therefore,
$M_{i}\big{(}\frac{w_{i}}{w_{1}}\big{)}^{2}\gamma^{\alpha_{i}-\alpha_{1}}=M_{i}(\frac{C_{1i}^{a}}{C_{i}^{a}})(\frac{w_{i}}{w_{1}})\to
0$ as $\gamma\to 0$.

If $\alpha_{1}<\alpha_{i}<\alpha_{max}$, let us suppose
$M_{i}\big{(}\frac{w_{i}}{w_{1}}\big{)}^{2}\gamma^{\alpha_{i}-\alpha_{1}}=M_{i}.\frac{C_{k}^{a}}{C_{i}^{a}}.\frac{w_{k}\gamma^{\alpha_{k}}}{w_{i}\gamma^{\alpha_{i}}}.\frac{w_{i}}{w_{1}}\to
L_{i}\neq 0$ as $\gamma\to 0$. Let us choose an $\epsilon>0$ such that
$L_{i}-\epsilon>0$. Then for sufficiently small $\gamma$, we get
$w_{k}\gamma^{\alpha_{k}}>(L_{i}-\epsilon)\frac{w_{1}\gamma^{\alpha_{1}}}{w_{i}}$.
But due to
$M_{k}\big{(}\frac{w_{i}}{w_{1}}\big{)}^{2}\gamma^{\alpha_{k}-\alpha_{1}}\leq
1$, we must have
$(L_{i}-\epsilon)^{2}\frac{M_{k}}{w_{i}^{2}}\gamma^{\alpha_{1}-\alpha_{k}}<M_{k}\big{(}\frac{w_{i}}{w_{1}}\big{)}^{2}\gamma^{\alpha_{k}-\alpha_{1}}\leq
1$. This implies that
$w_{i}>(L_{i}-\epsilon)\sqrt{M_{k}}\gamma^{\frac{\alpha_{1}-\alpha_{k}}{2}}$.
But we cannot have $w_{i}\to\infty$ as $\gamma\to 0$.

We are thus forced to conclude that only those values of $i$ for which
$\alpha_{i}=\alpha_{max}$ will contribute positively to the sum
$\sum_{i=2}^{K}\lim_{\gamma\to
0}M_{i}\big{(}\frac{w_{i}}{w_{1}}\big{)}^{2}\gamma^{\alpha_{i}-\alpha_{1}}$.

For $i$ such that $\alpha_{i}=\alpha_{max}$, as $\gamma\to 0$, let
$M_{i}\big{(}\frac{w_{i}}{w_{1}}\big{)}^{2}\gamma^{\alpha_{i}-\alpha_{1}}\to
L_{i}\neq 0$. Therefore, in the limit,
$w_{1}=\sqrt{\frac{M_{i}}{L_{i}}}\gamma^{\frac{\alpha_{max}-\alpha_{1}}{2}}w_{i}$.
This also gives us that as $\gamma\to 0$, for all $s,t$ such that
$\alpha_{s}=\alpha_{t}=\alpha_{max}$,
$\frac{w_{s}}{w_{t}}=\sqrt{\frac{M_{t}L_{s}}{M_{s}L_{t}}}=\sqrt{\frac{L_{s}}{L_{t}}}\sqrt{\frac{\sum_{j}p_{sj}\log(1+A_{s}a_{sj})+A_{s}\sum_{j}a_{sj}\tilde{p}_{sj}}{\sum_{j}p_{tj}\log(1+A_{t}a_{tj})+A_{t}\sum_{j}a_{tj}\tilde{p}_{tj}}}$.

To approximately solve our maxmin problem, we do the following:

Let us fix a $k$ with $\alpha_{k}=\alpha_{max}$ and set $w_{k}=1$. Then,
$w_{1}=\sqrt{\frac{M_{k}}{L_{k}}}\gamma^{\frac{\alpha_{max}-\alpha_{1}}{2}}$.
For the other $i$ such that $\alpha_{i}<\alpha_{max}$, using
$C_{i}^{a}w_{i}\gamma^{\alpha_{i}}=\frac{\sum_{j}a_{1j}p_{1j}+\sum_{j}\frac{p_{k}j}{A_{k}}\log(1-A_{k}a_{kj})}{\sum_{j}a_{1j}p_{1j}+\sum_{j}\frac{p_{i}j}{A_{i}}\log(1-A_{i}a_{ij})}C_{k}^{a}w_{k}\gamma^{\alpha_{k}}$,
we get that
$w_{i}=\frac{A_{k}\sum_{j}a_{1j}p_{1j}+\sum_{j}{p_{kj}}\log(1-A_{k}a_{kj})}{A_{i}\sum_{j}a_{1j}p_{1j}+\sum_{j}{p_{ij}}\log(1-A_{i}a_{ij})}\gamma^{\alpha_{k}-\alpha_{i}}$.
Note that $A_{i}$ may be obtained by solving
$\mu_{1}=\sum_{j}\frac{a_{ij}p_{ij}}{1-A_{i}a_{ij}}$. For any other $s$ with
$\alpha_{s}=\alpha_{max}$, we have
$w_{s}=\sqrt{\frac{L_{s}}{L_{k}}}\sqrt{\frac{\sum_{j}p_{sj}\log(1+A_{s}a_{sj})+A_{s}\sum_{j}a_{sj}\tilde{p}_{sj}}{\sum_{j}p_{kj}\log(1+A_{k}a_{kj})+A_{k}\sum_{j}a_{kj}\tilde{p}_{kj}}}$.
We use this to evaluate $L_{k}$ for each “rarest arm" and finally normalize
the weights obtained to lie within [0,1].

Special case: If there is a unique $k$ with $\alpha_{k}=\alpha_{max}$, then
our analysis tells us that $L_{k}=1$. Our approximate solution then becomes
the normalized form of
$w_{1}=\sqrt{M_{k}}\gamma^{\frac{\alpha_{max}-\alpha_{1}}{2}}$,
$w_{i}=\frac{A_{k}\sum_{j}a_{1j}p_{1j}+\sum_{j}{p_{kj}}\log(1-A_{k}a_{kj})}{A_{i}\sum_{j}a_{1j}p_{1j}+\sum_{j}{p_{ij}}\log(1-A_{i}a_{ij})}\gamma^{\alpha_{k}-\alpha_{i}}$
for $i\neq k,1$, and $w_{k}=1$.

Before starting on rest of the cases, we’ll introduce some additional notation
that will be of importance. Let us revisit the following function introduced
in section 3.1.

$g_{i}(x)=\bigg{\\{}y:\sum_{j}\frac{a_{1j}p_{1j}}{1+ya_{1j}}=\sum_{j}\frac{a_{ij}p_{ij}}{1-xa_{ij}}\bigg{\\}}$

Clearly, $g_{i}$ is decreasing in $x$, and $g_{k}(A_{k})=A_{1k}$. We now
define $f_{i}(x)$ as

$f_{i}(x):=\sum_{j}p_{1j}\log(1+g_{i}(x)a_{1j})+\frac{g_{i}(x)}{x}\sum_{j}p_{ij}\log(1-xa_{ij})$
$f_{i}(0):=\lim_{x\to 0^{+}}f_{i}(x)$

$f_{i}$ can also be shown to be decreasing in $x$ and increasing in
$g_{i}(x)$. Further, we define $h_{i}$ as follows.

$h_{i}(x):=\frac{\sum_{j}p_{1j}\log(1+g_{i}(x)a_{1j})-g_{i}(x)\sum_{j}a_{1j}\tilde{p}_{1j}^{(i)}}{\sum_{j}p_{ij}\log(1-xa_{ij})+xa_{ij}\tilde{p}_{ij}}$

It can be showed that $h_{i}$ is a decreasing function of $x$.

We can now turn our attention to Case 2.

Since $\alpha_{1}=\alpha_{max}$ uniquely, in the sum

$\sum_{i=2}^{K}\lim_{\gamma\to
0}\frac{\gamma^{\alpha_{1}}(\sum_{j}p_{1j}\log(1+C_{1i}^{a}a_{1j})-C_{1i}^{a}\sum_{j}a_{1j}\tilde{p}_{1j}^{(i)})}{\gamma^{\alpha_{i}}(\sum_{j}p_{ij}\log(1-C_{i}^{a}a_{ij})+C_{i}^{a}\sum_{j}a_{ij}\tilde{p}_{ij})}=1,$

if we do not have $C_{k}^{a}\to 0$ as $\gamma\to 0$ for some $k$, then the sum
on the left becomes equal to 0, which would be a contradiction. We also note
that there will be exactly one arm $k$ where $C_{k}^{a}\to 0$ as $\gamma\to
0$. Let us separately examine this $k^{\textrm{th}}$ summand.

$\lim_{\gamma\to
0}\frac{(\sum_{j}p_{1j}\log(1+C_{1k}^{a}a_{1j})-C_{1k}^{a}\sum_{j}a_{1j}\tilde{p}_{1j}^{(i)})}{(\sum_{j}p_{kj}\log(1-C_{k}^{a}a_{kj})+C_{k}^{a}\sum_{j}a_{kj}\tilde{p}_{kj})}\gamma^{\alpha_{1}-\alpha_{k}}=\lim_{\gamma\to
0}\frac{2(\sum_{j}p_{1j}\log(1+C_{1k}^{a}a_{1j})-C_{1k}^{a}\sum_{j}a_{1}\tilde{p}_{1j}^{(k)})}{(C^{a}_{k})^{2}\sum_{j}a_{kj}^{2}p_{kj}}\gamma^{\alpha_{1}-\alpha_{k}}$

Since this term needs to be equal to 1, we must have

$\lim_{\gamma\to
0}\frac{(C^{a}_{k})^{2}}{\gamma^{\alpha_{k}-\alpha_{1}}}=\lim_{\gamma\to
0}\frac{(C^{a}_{1k})^{2}w_{k}^{2}\gamma^{\alpha_{k}-\alpha_{1}}}{w_{1}^{2}}=\frac{\sum_{j}a_{kj}^{2}p_{kj}}{2(\sum_{j}p_{1j}\log(1+A_{1k}a_{1j})-A_{1k}\sum_{j}a_{1j}\tilde{p}_{1j}^{(k)})}$

This suggests the following form for $w_{k}$.

$w_{k}=\frac{1}{A_{1k}}\sqrt{\frac{\sum_{j}a_{kj}^{2}p_{kj}}{2(\sum_{j}p_{1j}\log(1+A_{1k}a_{1j})-A_{1k}\sum_{j}a_{1j}\tilde{p}_{1j}^{(k)})}}w_{1}\gamma^{\frac{\alpha_{1}-\alpha_{k}}{2}}(=:M_{k}w_{1}\gamma^{\frac{\alpha_{1}-\alpha_{k}}{2}})$

We shall now establish that $k=2$.

It can be understood that $g_{i}(x)$ is the factor by which the mean of arm 1
is reduced to $\frac{a_{ij}p_{i}}{1-xa_{i}}$. Hence, we conclude that
$g_{2}(0)<...<g_{K}(0)$, implying that $f_{2}(0)<...<f_{K}(0)$.

Observe that (8) can be expressed as (as $A_{k}=0$)

$f_{i}(A_{i})=f_{k}(A_{k})=f_{k}(0)$

If $k>2$, we have $f_{2}(A_{2})<f_{2}(0)<f_{k}(0)$, giving us a contradiction.
Hence, $k=2$.

Since for every other arm $i$, $C_{1i}^{a}\to A_{1i}(\neq 0)$ and
$C_{i}^{a}\to A_{i}(\neq 0)$ as $\gamma\to 0$,

$w_{i}=\frac{A_{1i}}{A_{i}}w_{1}\gamma^{\alpha_{1}-\alpha_{i}}$

where $A_{1i}$ and $A_{i}$ can be obtained by finding the unique solution to

$\frac{\sum_{j}p_{1j}\log(1+A_{12}a_{1j})-A_{12}\sum_{j}a_{2j}p_{2j}}{\sum_{j}p_{1j}\log(1+A_{1i}a_{1j})+\frac{A_{1i}}{A_{i}}\sum_{j}p_{ij}\log(1-A_{i}a_{ij})}=1$

and

$\sum_{j}\frac{a_{1j}p_{1j}}{1+A_{1i}a_{1j}}=\sum_{j}\frac{a_{ij}p_{ij}}{1-A_{i}a_{ij}}$

the latter equality following from the limit form of the mean equation. We can
then use the same normalization technique as in case 1 to find the optimal
weights.

For Case 3, if $C^{a}_{12}\to A_{12}(\neq 0),C_{2}^{a}\to 0$ as $\gamma\to 0$,
we have

$\lim_{\gamma\to
0}\frac{(\sum_{j}p_{1j}\log(1+C^{a}_{12}a_{1j})-C^{a}_{12}\sum_{j}a_{1j}\tilde{p}_{1j}^{(i)})}{(\sum_{j}p_{2j}\log(1-C_{2}^{a}a_{2j})+C_{2}^{a}\sum_{j}a_{2j}\tilde{p}_{2j})}\gamma^{\alpha_{1}-\alpha_{2}}=\lim_{\gamma\to
0}\frac{2(\sum_{j}p_{1j}\log(1+C^{a}_{12}a_{1j})-C^{a}_{12}\sum_{j}a_{1j}\tilde{p}_{1j}^{(2)})}{(C^{a}_{2})^{2}\sum_{j}a_{2j}^{2}p_{2}}=\infty$

which is impossible, thereby guaranteeing $C^{a}_{12}\to A_{12}(\neq
0),C_{2}^{a}\to A_{2}(\neq 0)$ as $\gamma\to 0$, and
$w_{2}=\frac{A_{12}}{A_{2}}w_{1}$. This will enable us to find $w_{2}$ as
described under case 2.

As already argued in case 2, $C_{2}^{a}\to A_{2}(\neq 0)$ as $\gamma\to 0$
means that $C_{i}^{a}\to A_{i}(\neq 0)$ as $\gamma\to 0$ for all $i\neq 2$.
Therefore, we must have

$\lim_{\gamma\to
0}\frac{\sum_{j}p_{1j}\log(1+C^{a}_{12}a_{1j})-C^{a}_{12}\sum_{j}a_{1j}\tilde{p}_{1j}^{(i)}}{\sum_{j}p_{2j}\log(1-C_{2}^{a}a_{2j})+C_{2}^{a}\sum_{j}a_{2j}\tilde{p}_{2j}}=1$

where $A_{1i}$ and $A_{i}$ can be related by

$\frac{\sum_{j}p_{1j}\log(1+A_{12}a_{1j})+\frac{A_{12}}{A_{2}}\sum_{j}p_{2j}\log(1-A_{2}a_{2j})}{\sum_{j}p_{1j}\log(1+A_{1i}a_{1j})+\frac{A_{1i}}{A_{i}}\sum_{j}p_{ij}\log(1-A_{i}a_{ij})}=1$
(25)

and using the mean equation,

$\displaystyle\sum_{j}\frac{a_{1j}p_{1j}}{1+A_{1i}a_{1j}}=\sum_{j}\frac{a_{ij}p_{ij}}{1-A_{i}a_{ij}}\
\forall i$

Let us denote these by $A_{2}(A_{12})$ and $A_{i}(A_{1i})$. Substituting them
in 25 and using the defintions of $f_{i}$, we have
$f_{2}(A_{12})=f_{i}(A_{1i})$.

Each of these $f_{i}$’s is increasing in $A_{1i}$. Thus we have
$A_{1i}=f_{i}^{-1}\circ(f_{2}(A_{12}))$.

Using this, we can solve for $A_{12}$ from equation 11. We observe that each
summand in 11 is an increasing function of $A_{1i}$ and hence $A_{12}$. So a
simple efficient scheme to find the solution is to first guess an $A_{12}$ and
then use a simple bisection method to numerically get $A_{1i}$’s for this
guess. The mean equations can be used to get the $A_{i}$’s. Finally, we check
if 11 is satisfied (upto tolerance). If LHS of 11 is greater than 1, then we
halve our initial guess, and double the guess if lesser than 1. And repeat the
earlier procedure till error tolerance is breached.

It only remains to consider Cases 4 and 5. We have already argued under case 3
that $C_{j}^{a}\to A_{j}(\neq 0)\ \textrm{as}\ \gamma\to 0$ whenever
$\alpha_{j}=\alpha_{max}$. Corresponding to any such $A_{j}$, we can write all
other $A_{i}$’s in terms of $A_{j}$. Let us define $\xi_{ij}(x)$ as follows.

$\xi_{ij}(x):=\bigg{\\{}y:\frac{p_{1j}\log(1+g_{i}(y)a_{1})+p_{i}\frac{g_{i}(y)}{y}\log(1-ya_{i})}{p_{1j}\log(1+g_{j}(x)a_{1})+p_{j}\frac{g_{j}(x)}{x}\log(1-ya_{i})}=1\bigg{\\}}$

Let us now define $\zeta$ as

$\zeta:=\sum_{\begin{subarray}{c}\\{k:k\neq 1,\\\
\alpha_{k}=\alpha_{max}\\}\end{subarray}}h_{k}(\xi_{k2}(0)).$

Equation 11 can now be re-written after taking the limit $\gamma\to 0$ as

$\sum_{\begin{subarray}{c}\\{k:k\neq 1,\\\
\alpha_{k}=\alpha_{max}\\}\end{subarray}}h_{k}(A_{k})+\lim_{\gamma\to
0}(\gamma^{\alpha_{1}-\alpha_{2}}h_{2}(C_{2}^{a}))=1$

The issue now is to determine if $C_{2}^{a}\to 0$ as $\gamma\to 0$. We have
observed earlier that $h_{i}(A_{i})$ is a decreasing function of $A_{i}$ and
the bijective map $\xi_{i2}$ implies $h_{i}(A_{i})$ is also a decreasing
function of $A_{2}$. Thus, we have

$\zeta\geq\sum_{\begin{subarray}{c}\\{k:k\neq 1,\\\
\alpha_{k}=\alpha_{max}\\}\end{subarray}}h_{k}(A_{k}).$

If $\zeta>1$, then equation 11 can be satisfied only when $C_{2}^{a}\to A_{2}\
(>0).$ Because otherwise, the first term itself would contribute more than 1
and we’d have a contradiction. Similarly, when $\zeta\leq 1$, we must
necessarily have $C_{2}^{a}\to 0.$

In the case when $\zeta>1$, the $A_{i},A_{1i}$’s are determined exactly as in
3. If $\zeta\leq 1$ then $A_{i},A_{1i}$’s are determined exactly as in Case 2.
This completes our proof.

##  Appendix D The meeting point of the means in the approximate problem

Equation (12) in the main body and the Mean Value Theorem together give us the
following chain of equalities/inequalities.

$\displaystyle\sum_{j=1}^{n}p_{1j}\log(1+C_{1s}a_{1j})-C_{1s}\tilde{\mu}_{s}$
$\displaystyle\leq$
$\displaystyle\sum_{j=1}^{n}p_{1j}\log(1+C_{1s}a_{1j})-C_{1s}\sum_{j=1}^{n}\frac{a_{sj}p_{sj}}{1-C_{s}a_{sj}}$
$\displaystyle\leq$
$\displaystyle\sum_{j=1}^{n}p_{1j}\log(1+C_{1s}a_{1j})+\frac{C_{1s}}{C_{s}}\sum_{j=1}^{n}p_{sj}\log(1-C_{s}a_{sj})$
$\displaystyle=$
$\displaystyle\sum_{j=1}^{n}p_{1j}\log(1+C_{1t}a_{1j})+\frac{C_{1t}}{C_{t}}\sum_{j=1}^{n}p_{tj}\log(1-C_{t}a_{tj})$
$\displaystyle\leq$
$\displaystyle\sum_{j=1}^{n}p_{1j}\log(1+C_{1t}a_{1j})-C_{1t}\mu_{t}$

Regrouping terms among the first and last quantities of the above chain gives
us that

$\frac{C_{1t}}{C_{1s}}\mu_{t}\leq\frac{1}{C_{1s}}\sum_{j=1}^{n}p_{1j}\log\bigg{(}\frac{1+C_{1t}a_{1j}}{1+C_{1s}a_{1j}}\bigg{)}+\tilde{\mu}_{s}$

Note that
$\log\big{(}\frac{1+C_{1t}a_{1j}}{1+C_{1s}a_{1j}}\big{)}=\log\big{(}1+\frac{(C_{1t}-C_{1s})a_{1j}}{1+C_{1s}a_{1j}}\big{)}\leq(C_{1t}-C_{1s})\tilde{\mu}_{s}$,
and hence,
$\frac{C_{1t}}{C_{1s}}\mu_{t}\leq\frac{C_{1t}}{C_{1s}}\tilde{\mu}_{s}$, i.e.,
$\mu_{t}\leq\tilde{\mu}_{s}$.

We conclude from the above analysis that $\forall s,t\neq 2$,
$\tilde{\mu}_{s}\geq\mu_{t}\Rightarrow\forall s\neq 2$,
$\tilde{\mu}_{s}\geq\mu_{2}$.

##  Appendix E Proof of $\delta$-Correctness of TS(A).

Let the set of all possible bandit hypotheses be $\mathcal{H}$. We have
$\mathcal{H}=\cup_{i}\mathcal{H}_{i}$, where $\mathcal{H}_{i}$ denotes all
bandit instances with arm $i$ having the highest mean. Let
$\hat{i}(\tau_{\delta})$ denote the recommendation of TS(A) at the stopping
time. The error probability for a bandit instance $p$ with arm 1 having the
highest mean is given by:

$\displaystyle\mathbb{P}_{p}(\tau_{\delta}<\infty,\hat{i}(\tau_{\delta})\neq
1)$ $\displaystyle\leq\mathbb{P}_{p}(\exists t\in\mathbb{N}:\hat{i}(t)\neq
1,Z_{\hat{i}(t)}(t)>\beta(t,\delta))$ $\displaystyle=\mathbb{P}_{p}(\exists
t\in\mathbb{N}:\exists i\neq 1A(\hat{p})\subseteq\mathcal{H}_{i})$

where
$A(\hat{p}):=\\{p^{\prime}\in\mathcal{H}|\underset{b\neq\hat{i}(t)}{\min}N_{\hat{i}(t)}(t)\mathcal{K}_{inf}^{L}(\hat{p}_{\hat{i}(t)}(t),\mu_{\hat{i}(t)}^{\prime})+N_{b}(t)\mathcal{K}_{inf}^{U}(\hat{p}_{b}(t),\mu_{b}^{\prime})\leq\beta(t,\delta)\\}$.
This implies:

$\displaystyle\mathbb{P}_{p}(\tau_{\delta}<\infty,\hat{i}(\tau_{\delta})\neq
1)$ $\displaystyle\leq\mathbb{P}_{p}(\exists t\in\mathbb{N}:p\notin
A(\hat{p}))$ (26) $\displaystyle=\mathbb{P}_{p}(\exists
t\in\mathbb{N}:\underset{b\neq\hat{i}(t)}{min}N_{\hat{i}(t)}(t)\mathcal{K}_{inf}^{L}(\hat{p}_{\hat{i}(t)}(t),\mu_{\hat{i}(t)})+N_{b}(t)\mathcal{K}_{inf}^{U}(\hat{p}_{b}(t),\mu_{b})\geq\beta(t,\delta))$
$\displaystyle\leq\sum_{b\neq 1}\mathbb{P}_{p}(\exists
t\in\mathbb{N}:N_{\hat{i}(t)}(t)\mathcal{K}_{inf}^{L}(\hat{p}_{\hat{i}(t)}(t),\mu_{\hat{i}(t)})+N_{b}(t)\mathcal{K}_{inf}^{U}(\hat{p}_{b}(t),\mu_{b})\geq\beta(t,\delta))$

Now a concentration inequality for the above quantity was shown in Agrawal et
al., (2021).

  * Proposition4.2 in Agrawal et al., (2021).

$\mathbb{P}\bigg{(}\exists
n\in\mathbb{N}:N_{i}(n)\mathcal{K}_{inf}^{U}(\hat{p}_{i}(t),\mu_{i})+\mathcal{K}_{inf}^{L}(\hat{p}_{j}(t),\mu_{j})\geq
x+5\log(n+1)+2\bigg{)}\leq e^{-x}.$

Substituting this in (26) finishes the proof.

##  Appendix F Sample complexity guarantee for TS(A).

We follow closely the section C.6.2 in Agrawal et al., (2020). Let
$\hat{w}^{*}(p)$ denote the optimal weights obtained as solutions to the
approximate problem described at the beginning of section 3.1 in the main
paper. Lemma 14 in Agrawal et al., (2020) then tells us that TS(A) ensures
that for all arms $i\in[K]$,
$\frac{N_{i}(lm)}{lm}\overset{a.s.}{\to}\hat{w}^{*}(p)$ as $l\to\infty$.
Recall from section 4 of the main paper that $l$ is the batch index and $m$ is
the batch size.

Define the following set

$\mathcal{I}_{\epsilon}(p):=B_{\zeta}(p_{1})\times...\times B_{\zeta}(p_{K})$

where

$B_{\zeta}(p_{i}):=\\{\tilde{p}_{i}:d_{W}(p_{i},\tilde{p}_{i})\leq\zeta,|\tilde{\mu}_{i}-\mu_{i}|\leq\zeta\\}.$

Here, $d_{W}$ is the Wasserstein-1 metric on probability measures and
$\tilde{\mu}_{i}$ is the mean of $\tilde{p}_{i}$.
Whenever the empirical bandit $\hat{p}(lm)\in\mathcal{I}_{\epsilon}(p)$, arm1
becomes empirically best. For $\epsilon>0$, choose
$\zeta:=\zeta(\epsilon)(<\frac{\mu_{1}-\mu_{2}}{4})$ such that

$\underset{i\in[K]}{\max}|\hat{w}^{*}_{i}(p^{\prime})-\hat{w}_{i}^{*}(p)|\leq\epsilon$

for all $p^{\prime}\in\mathcal{I}_{\epsilon}(p)$. For $T\in\mathbb{N}$, $T\geq
m$, define $\ell_{0}(T):=\max\\{1,\frac{T^{1/4}}{m}\\}$,
$\ell_{1}(T):=\max\\{1,\frac{T^{3/4}}{m}\\}$ and
$\ell_{2}(T):=\lfloor\frac{T}{m}\rfloor$. Define the following set

$\mathcal{G}_{T}(\epsilon):=\bigcap^{\ell_{2}(T)}_{l=\ell_{0}(T)}\\{\hat{p}(lm)\in\mathcal{I}_{\epsilon}(p)\\}\bigcap^{\ell_{2}(T)}_{l=\ell_{1}(T)}\bigg{\\{}\underset{i\in[K]}{\max}\bigg{|}\frac{N_{i}(lm)}{lm}-\hat{w}_{i}^{*}(p)\bigg{|}\leq\epsilon\bigg{\\}}$

Define the quantities:

$\displaystyle\tilde{g}(p,w)$ $\displaystyle:=\underset{b\neq
1}{\min}\mathcal{P}_{b}(w)$ $\displaystyle\tilde{C}_{\epsilon}(p)$
$\displaystyle:=\underset{\underset{\\{w^{{}^{\prime}}:||w^{{}^{\prime}}-\hat{w}^{*}(p)||\leq\epsilon\\}}{p^{{}^{\prime}}\in\mathcal{I}_{\epsilon}(p)}}{inf}\tilde{g}(p^{{}^{\prime}},w^{{}^{\prime}}).$

where $\mathcal{P}_{b}$ was defined in equation 7 of the main paper. Now the
stopping rule (see section 4 in the main paper) is given by:

$Z_{k^{*}}(l)>\beta(lm,\delta)$

where

$\displaystyle Z_{k^{*}}(l):=$ $\displaystyle\underset{b\neq
k^{*}}{\min}\underset{x\leq
y}{\inf}N_{k^{*}}(lm)\mathcal{K}_{inf}^{L}(\hat{p}_{k^{*}}(lm),x)$
$\displaystyle+N_{b}(lm)\mathcal{K}_{inf}^{U}(\hat{p}_{b}(lm),y).$

where $k^{*}$ is the empirical best arm and $\beta(t,\delta)$ is the stopping
threshold defined as

$\beta(t,\delta):=\log\bigg{(}\frac{K-1}{\delta}\bigg{)}+5\log(t+1)+2.$

Note that in $\mathcal{G}_{T}(\epsilon)$ we have
$Z_{k^{*}}(l)>lm\times\tilde{C}_{\epsilon}(p)$. Hence, in
$\mathcal{G}_{T}(\epsilon)$,

$\displaystyle\min\\{\tau_{\delta},T\\}$ $\displaystyle\leq
m.l_{1}(T)+m\sum_{l=l_{1}(T)+1}^{l_{2}(T)}\mathbb{I}\\{lm<\tau_{\delta}\\}$
$\displaystyle\leq
m.l_{1}(T)+m\sum_{l=l_{1}(T)+1}^{l_{2}(T)}\mathbb{I}\\{Z_{k^{*}}(l)<\beta(lm,\delta)\\}$
$\displaystyle=m.l_{1}(T)+m\sum_{l=l_{1}(T)+1}^{l_{2}(T)}\mathbb{I}\bigg{\\{}l<\frac{\beta(lm,\delta)}{m\tilde{C}_{\epsilon}(p)}\bigg{\\}}$
$\displaystyle=m.l_{1}(T)+\frac{\beta(T,\delta)}{\tilde{C}_{\epsilon}(p)}$

Define
$T_{0}(\delta,\epsilon):=\inf\bigg{\\{}t:m.l_{1}(T)+\frac{\beta(t,\delta)}{\tilde{C}_{\epsilon}(p)}\leq
t\bigg{\\}}$.
On $\mathcal{G}_{T}(\epsilon)$, for $T\geq\max\\{m,T_{0}(\delta,\epsilon)\\}$,
$\min\\{\tau_{\delta},T\\}\leq T$, meaning that for such $T$,
$\tau_{\delta}\leq T$. Hence, choosing
$T_{1}(\delta,\epsilon):=\max\\{m,T_{0}(\delta,\epsilon)+1$, we get that
$\mathcal{G}_{T_{1}(\delta,\epsilon)}(\epsilon)\subseteq\\{\tau_{\delta}\leq
T_{1}(\delta,\epsilon)\\}$. Then,
$\min\\{\tau_{\delta},T_{1}(\delta,\epsilon)\\}\leq
T_{1}(\delta,\epsilon)\Rightarrow\tau_{\delta}\leq T_{1}(\delta,\epsilon)$.
This allows us to conclude that

$\displaystyle\mathbb{E}(\tau_{\delta})$
$\displaystyle=\sum_{t=1}^{\infty}\mathbb{P}(\tau_{\delta}\geq t)$
$\displaystyle=\sum_{t=1}^{T_{1}(\delta,\epsilon)}\mathbb{P}(\tau_{\delta}\geq
t)+\sum_{t=T_{1}(\delta,\epsilon)+1}^{\infty}\mathbb{P}(\tau_{\delta}\geq t)$
$\displaystyle\leq
T_{0}(\delta,\epsilon)+m+\sum_{t=m+1}^{\infty}\mathbb{P}(\mathcal{G}_{T}^{C}(\epsilon))$

Now in the same manner as in Agrawal et al., (2020) we can show that
$\frac{T_{0}(\delta,\epsilon)}{\log(1/\delta)}\to\frac{1}{\tilde{C}_{\epsilon}(p)}$
as $\delta\to 0$. We invoke Lemma 32 in Agrawal et al., (2020) to observe that
$\frac{\sum_{t=m+1}^{\infty}\mathbb{P}(\mathcal{G}_{T}^{C}(\epsilon))}{\log(1/\delta)}\to
0$. Thus we have for small enough $\epsilon>0$

$\limsup_{\delta\to
0}\frac{\mathbb{E}(\tau_{\delta})}{\log(1/\delta)}\leq\frac{1}{\tilde{C}_{\epsilon}(p)}$

But we observe that by continuity in $\epsilon$, when $\epsilon\to 0$

$\tilde{C}_{\epsilon}(p)\to\underset{b\neq
1}{\min}\mathcal{P}_{b}(\hat{w}^{*}).$

Note by definition $\underset{b\neq 1}{\min}\mathcal{P}_{b}(\hat{w}^{*})\leq
V^{*}(p)$. This inequality shows that TS(A) suffers an increase in sample
complexity but this is expected to be small when $\gamma$ is close to zero
since then $\hat{w}^{*}(p)\approx w^{*}(p).$

##  Appendix G Algorithms in Literature

The following algorithm as per Even-Dar, Mannor & Mansour (2006) provides a
simplistic approach towards solving our problem, despite being highly
expensive in terms of sampling complexity.

Algorithm 2 Succesive elimination ($\delta$)

Set $t=1,S=[K]$.

For all $i\in[K]$, set the empirical means $\hat{\mu}_{i}^{t}=0$.

while |S|>1 do

Sample every arm once, update $\hat{\mu}_{i}^{t}$.

Define $\hat{\mu}_{max}^{t}:=\underset{i\in S}{\max}\hat{\mu}_{i}^{t}$,
$\xi_{t}:=\sqrt{\frac{\log(4Kt^{2}/\delta)}{t}}$.

For all $i\in S$ such that $\hat{\mu}_{max}^{t}-\hat{\mu}_{i}^{t}\geq
2\xi_{t}$, set $S=S\backslash{i}$.

$t=t+1$

end while

Declare the surviving arm as the best arm.

The successive elimination algorithm performs poorly in the rare event setting
because a less rare arm which does not have the largest mean becomes likely to
survive the elimination and be declared the winner. This is because the less
rare arm is likely to produce a nonzero sample, thereby raising its empirical
mean, while the more rare arms are yet to turn out any non-zero samples.

Agrawal et al., (2019) describes the following algorithm to meet the lower
bound on sampling complexity.

Algorithm 3 Track and Stop

Generate $\lfloor\frac{m}{k}\rfloor$ samples for each arm.

Set $l=1$. $lm$ denotes the number of samples.

Compute the empirical bandit $\hat{\mu}=(\hat{\mu})_{\\{a\in[K]}$.

Compute the approximate weights $\hat{w}(\hat{\mu})$.

Let $k^{*}=\underset{a\in[K]}{\arg\max}\mathbb{E}[\hat{\mu}_{a}]$.

Compute ${Z}(k^{*},l,\hat{\mu})$, $\beta(lm,\delta)$.

while $l\leq 2$ or ${Z}(k^{*},l,\hat{\mu})\geq\beta(lm,\delta)$ do

Compute $s_{a}=(\sqrt{(l+1)m}-N_{a}(lm))^{+}$.

if $m\geq\sum_{a}s_{a}$ then

Generate $s_{a}$ many samples for each arm $a$.

Generate $(m-\sum_{a}s_{a})^{+}$ independent samples from
$\hat{w}(\hat{\mu})$. Let $Count(a)$ be occurrence of $a$ in these samples.

Generate $Count(a)$ samples from each arm $a$.

else

Solve the load balancing problem $\text{minimize
}\max_{a}(s_{a}-\hat{s}_{a})$, where $s_{a}\geq\hat{s}_{a}\geq 0$.

Generate $\hat{s}_{a}$ samples from each arm $a$.

end if

$l=l+1$

Update empirical bandit $\hat{\mu}$ with new samples.

Update ${Z}(k^{*},l,\hat{\mu})$, $\beta(lm,\delta)$ and $\hat{w}(\hat{\mu})$ .

end while

Declare $k^{*}$ arm as the best arm.