# Risk-Constrained Thompson Sampling for Gaussian CVaR Bandits

Joel Q. L. Chang  Qiuyu Zhu  Vincent Y. F. Tan

###### Abstract

The multi-armed bandit (MAB) problem is a ubiquitous decision-making problem
that exemplifies the exploration-exploitation tradeoff. Standard formulations
exclude risk in decision making. Risk notably complicates the basic reward-
maximising objective, in part because there is no universally agreed
definition of it. In this paper, we consider a popular risk measure in
quantitative finance known as the Conditional Value at Risk (CVaR). We explore
the performance of a Thompson Sampling-based algorithm CVaR-TS under this risk
measure. We provide comprehensive comparisons between our regret bounds with
state-of-the-art L/UCB-based algorithms in comparable settings and demonstrate
their clear improvement in performance. We show that the regret bounds of
CVaR-TS approach instance-dependent lower bounds for the same problem in some
parameter regimes. We also perform numerical simulations to empirically verify
that CVaR-TS significantly outperforms other L/UCB-based algorithms in terms
of regret and also in flagging an infeasible instance as feasible and vice
versa.

Multi-armed bandits

##  1 Introduction

The multi-armed bandit (MAB) problem analyses sequential decision making,
where the learner has access to partial feedback. This problem is applicable
to a variety of real-world applications, such as clinical trials, online
advertisement, network routing, and resource allocation. In the well-known
stochastic MAB setting, a player chooses among $K$ arms, each characterised by
an independent reward distribution. During each period, the player plays one
arm and observes a random reward from that arm, incorporates the information
in choosing the next arm to select. The player repeats the process for a
horizon containing $n$ periods. In each period, the player faces a dilemma
whether to explore the potential value of other arms or to exploit the arm
that the player believes offers the highest estimated reward.

In each of the above-mentioned applications, risk is not taken into account.
In this regard, the MAB problem should be explored in a more sophisticated
setting, where the player wants to maximise one’s reward while minimising
one’s risk incurred, subject to a “maximum risk” condition. This paper
proposes the first Thompson sampling-based learning algorithm which minimises
the _Conditional Value at Risk (CVaR)_ risk measure (Rockafellar & Uryasev,
2000), also known as the _expected shortfall (ES)_.

###  1.1 Related Work

Various analyses of MABs involving risk measures have been undertaken. Sani et
al. (2012) considered the _mean-variance_ as their risk measure. Each arm $i$
was distributed according to a Gaussian with mean $\mu_{i}\in[0,1]$ and
variance $\sigma_{i}^{2}\in[0,1]$. The authors provided an LCB-based algorithm
with accompanying regret analyses. Galichet et al. (2013) proposed the Multi-
Armed Risk-Aware Bandit (MaRaB) algorithm with the objective of minimising the
number of pulls of risky arms, using CVaR as their risk measure. Vakili & Zhao
(2016) showed that the instance-dependent and instance-independent regrets in
terms of the mean-variance of the reward process over a horizon $n$ are lower
bounded by $\Omega(\log n)$ and $\Omega(n^{2/3})$ respectively. Sun et al.
(2017) considered contextual bandits with risk constraints, and developed a
meta algorithm utilizing the online mirror descent algorithm which achieves
near-optimal regret in terms of minimizing the total cost. Huo & Fu (2017)
studied applications of risk-aware MAB into portfolio selection, achieving a
balance between risk and return. Khajonchotpanya et al. (2020) similarly used
CVaR as their risk measure and proposed the CVaR-UCB algorithm, which chooses
the arm with the highest gap with respect to the arm with the highest CVaR.
Note that the authors associated the highest CVaR to the highest reward, while
our paper considers the highest CVaR to result in the highest loss. Thus, the
discussions in Khajonchotpanya et al. (2020) apply analogously.

The paper closest to our work is that by Kagrecha et al. (2020a), who regard a
large CVaR as corresponding to a large loss incurred by the user. They
proposed and analysed RC-LCB and considered the scenario where users have a
predetermined risk tolerance level $\tau$. Any arm whose CVaR exceeds $\tau$
is deemed infeasible. This motivates the authors to define three different
regrets, each corresponding to the number of times the non-optimal arms of
different classes (e.g., feasible/infeasible) were pulled. This problem
formulation also includes that of Khajonchotpanya et al. (2020) in the
“infeasible instance” case. Having drawn inspiration from Kagrecha et al.
(2020a) in terms of the problem setup, in Section 2, we provide definitions of
these classes of arms later which were originally defined in their paper. Zhu
& Tan (2020) provided a Thompson sampling-based algorithm for the scenario in
Sani et al. (2012), where the arm distributions are Gaussian or Bernoulli. Our
paper seeks to explore the efficacy of Thompson sampling in the problem
setting proposed by Kagrecha et al. (2020a) and to demonstrate, theoretically
and empirically, the improvement of Thompson sampling over confidence bound-
based approaches. Finally, we note the independent and contemporaneous work by
Baudry et al. (2020) on designing and analyzing Thompson sampling-based
algorithms $\alpha$-NPTS for bounded rewards and $\alpha$-Multinomial-TS for
discrete multinomial distributions; we consider a different class of reward
distributions (Gaussian whose support is unbounded) here and also three
different regret criteria (Definition 3).

###  1.2 Contributions

  * •

CVaR-TS Algorithm: We design CVaR-TS, an algorithm that is similar to the
structure of RC-LCB in Kagrecha et al. (2020a) but using Thompson sampling
(Thompson, 1933; Agrawal & Goyal, 2012) as explored for mean-variance bandits
in Zhu & Tan (2020).

  * •

Comprehensive regret analyses: We provide theoretical analyses of the
algorithms and show that in a variety of parameter regimes, the bounds on
three types of regrets outperform those of Kagrecha et al. (2020a), Bhat &
L.A. (2019), Khajonchotpanya et al. (2020) and Tamkin et al. (2019). In the
risk-neutral setting, they coincide with existing bounds under other risk
measures, such as the mean-variance (Zhu & Tan, 2020). We argue that our
analytical techniques apply more broadly to other risk measures such as the
entropic risk. Finally, we judiciously particularize the instance-dependent
lower bounds derived by Kagrecha et al. (2020a) to Gaussian CVaR MABs and show
that CVaR-TS meets these lower bounds in some regimes.

  * •

Numerical simulations: We provide an extensive set of simulations to
demonstrate that under certain regimes, our algorithm based on Thompson
sampling (Thompson, 1933) consistently outperforms RC-LCB (Kagrecha et al.,
2020a) and MaRaB (Galichet et al., 2013). Furthermore, in Kagrecha et al.
(2020a), due to the nature of the constants that were not explicitly defined,
numerical simulations could not be implemented. By estimating the constants
that they used based on explicit concentration bounds in L.A. et al. (2020)
and Fournier & Guillin (2015), we implemented RC-LCB and demonstrated
significant improvements in performance using Thompson sampling. Finally, we
show empirically that the empirical probability of CVaR-TS declaring that an
instance that is infeasible is flagged as feasible and vice versa is lower
than competing methods.

This paper is structured as follows. We introduce the formulation of CVaR MAB
in Section 2. In Section 3, we present CVaR-TS and demonstrate that it is a
Thompson sampling analogue of Kagrecha et al. (2020a) and Khajonchotpanya et
al. (2020). In Section 4 and 5, we state upper bounds on the regret and
outline their proofs respectively. In Section 6, we provide numerical
simulations to validate the regret bounds. We conclude our discussions in
Section 7, suggesting avenues for future research. We defer detailed proofs of
the theorems to the supplementary material.

##  2 Problem formulation

In this section we define the CVaR MAB problem. Throughout the paper, denote
$[m]=\left\\{{1,\dots,m}\right\\}$ for any $m\in\mathbb{N}$ and
${(x)}^{+}=\max\left\\{{0,x}\right\\}$ for $x\in\mathbb{R}$.

######  Definition 1.

For any random variable $X$, given a confidence level $\alpha\in[0,1)$, we
define the Value at Risk (VaR) and Conditional Value at Risk (CVaR) metrics of
$X$ by

$\displaystyle v_{\alpha}(X)$
$\displaystyle={\inf\left\\{{v\in\mathbb{R}:\mathbb{P}(X\leq
v)\geq\alpha}\right\\}},\ \text{and}$ (1) $\displaystyle c_{\alpha}(X)$
$\displaystyle={v_{\alpha}(X)+\frac{1}{1-\alpha}\mathbb{E}\big{[}{(X-v_{\alpha}(X))}^{+}}\big{]}.$
(2)

As explained by Kagrecha et al. (2020a), $v_{\alpha}(X)$ is the worst case
loss corresponding to a confidence level $\alpha$, which is usually taken to
be in the set $[0.90,1)$ (Rockafellar & Uryasev, 2000), where $X$ is the loss
associated with a portfolio. Working with a continuous cumulative distribution
function (CDF) $F_{X}(\cdot)$ of $X$ that is strictly increasing over its
support, direct computations give $c_{\alpha}(X)=\mathbb{E}[X|X\geq
v_{\alpha}(X)]$, and thus $c_{\alpha}(X)$ can be interpreted as the expected
loss given that the loss exceeds $v_{\alpha}(X)$. We remark that CVaR is
usually preferred to VaR as a risk measure since it is coherent (Artzner et
al., 1999) and satisfies more mathematically useful properties for analysis.
In our paper, we will be working with Gaussian random variables
$X\sim\mathcal{N}(\mu,\sigma^{2})$ whose CDF satisfies the continuity and
strict monotonicity assumptions of $F_{X}(\cdot)$. Letting $\Phi$ denote the
CDF of $Z\sim\mathcal{N}(0,1)$, direct computations using (1) and (2) yield

$\displaystyle c_{\alpha}(Z)$
$\displaystyle={\frac{1}{(1-\alpha)\sqrt{2\pi}}\exp\Big{(}-\frac{1}{2}\left({\Phi^{-1}(\alpha)}\right)^{2}}\Big{)},$
(3) $\displaystyle c_{\alpha}(X)$
$\displaystyle={\mu\Big{(}\frac{\alpha}{1-\alpha}\Big{)}+\sigma
c_{\alpha}(Z)}.$ (4)

In the rest of the paper, we denote $c_{\alpha}^{*}=c_{\alpha}(Z)$.
Intuitively, by (3), as $\alpha\to 1^{-}$, we have $c_{\alpha}^{*}\to+\infty$,
i.e., the CVaR of the standard Gaussian arm increases without bound, and the
arm gets riskier as the user demands higher confidence. However, since
$(\sigma c_{\alpha}^{*})/\big{(}\mu\cdot{\frac{\alpha}{1-\alpha}}\big{)}\to 0$
as $\alpha\to 1^{-}$, we have that $\frac{\alpha}{1-\alpha}\to+\infty$ faster
than $c_{\alpha}^{*}$. Thus, for $\alpha$ sufficiently close to $1^{-}$,
$c_{\alpha}(X)\approx\mu\big{(}\frac{\alpha}{1-\alpha}\big{)}$ and the problem
reduces to a standard (risk-neutral, cost minimization or reward maximization)
$K$-armed MAB problem.

Consider a $K$-armed MAB $\nu=({\nu(i)})_{i\in[K]}$ and a player with a known
risk threshold $\tau>0$ that represents her risk appetite. The CVaR MAB
problem is played over a horizon of length $n$. Roughly speaking, our goal is
to choose the arm with the lowest average loss, subject to an upper bound on
the risk (measured by the CVaR) associated with the arm. For any arm $i$, the
loss associated with arm $i$ has distribution $\nu(i)$ and $X(i)$ denotes a
random variable with distribution $\nu(i)$. Furthermore, $\mu(i)=\mu_{i}$
denotes the mean of $X(i)$, and $c_{\alpha}(i)$ denotes the CVaR of $X(i)$, as
defined in (4). Similar to Kagrecha et al. (2020a), we define feasible and
infeasible instances as follows.

######  Definition 2 (Kagrecha et al. (2020a)).

An _instance_ of the risk-constrained MAB problem is defined by $(\nu,\tau)$.
We denote the set of feasible arms (whose CVaR $\leq\tau$) as
$\mathcal{K}_{\tau}=\left\\{{i\in[K]:c_{\alpha}(i)\leq\tau}\right\\}$. The
instance $(\nu,\tau)$ is said to be _feasible_ (resp.  _infeasible_) if
$\mathcal{K}_{\tau}\neq\emptyset$ (resp. $\mathcal{K}_{\tau}=\emptyset$).

In a feasible instance, an arm $i$ is _optimal_ if $c_{\alpha}(i)\leq\tau$ and
$\mu_{i}=\min_{j\in\mathcal{K}_{\tau}}\mu_{j}$. Suppose arm $1$ is optimal and
$\mathrm{arg\ min}_{i\in\mathcal{K}_{\tau}}\mu_{i}=\left\\{{1}\right\\}$ for
simplicity. Define the set ${\cal
M}:=\left\\{{i\in{[K]}\backslash{\left\\{{1}\right\\}}:\mu_{i}>\mu_{1}}\right\\}$.
Arm $i$ is said to be

$\begin{cases}\text{\emph{a suboptimal arm}}&\text{if $i\in{\cal
M}\cap\mathcal{K}_{\tau}$,}\\\ \text{\emph{an infeasible arm}}&\text{if
$i\in\mathcal{K}_{\tau}^{c}$,}\\\ \text{\emph{a deceiver arm}}&\text{if
$i\in{\cal M}^{c}\cap\mathcal{K}_{\tau}^{c}$.}\end{cases}$

For a suboptimal arm $i$, we define the _suboptimality gap_ as
$\Delta(i)=\mu_{i}-\mu_{1}>0$. For an infeasible arm $i$, we define the
_infeasibility gap_ as $\Delta_{\tau}(i,\alpha)=c_{\alpha}(i)-\tau>0$.

In an infeasible instance, without loss of generality, set arm $1$ as an
_optimal_ arm, that is, $c_{\alpha}(1)=\min_{i\in[K]}c_{\alpha}(i)$. For
simplicity we suppose $\mathrm{arg\
min}_{i\in[K]}c_{\alpha}(i)=\left\\{{1}\right\\}$. We define the _risk gap_
for an arm $i$ that is not optimal by
$\Delta_{r}(i,\alpha)=c_{\alpha}(i)-c_{\alpha}(1)>0$. We remark that it is in
this infeasible instance that the risk gap is defined naturally by
Khajonchotpanya et al. (2020). With the three gaps defined, we can now define
three regrets in different settings.

######  Definition 3.

Let $T_{i,n}$ denote the number of times arm $i$ was pulled in the first $n$
rounds.

  1. 1.

For a feasible instance, let

$\mathcal{K}^{*}=\left\\{{i\in[K]:c_{\alpha}(i)\leq\tau\ \text{and}\
\mu_{i}=\min_{j\in\mathcal{K}_{\tau}}\mu_{j}}\right\\}$

denote the set of optimal arms (and without loss of generality suppose
$1\in\mathcal{K}^{*}$). The _suboptimality regret_ of policy $\pi$ over $n$
rounds is

$\mathcal{R}_{n}^{\mathsf{sub}}(\pi)=\sum_{i\in{\mathcal{K}_{\tau}}\backslash{\mathcal{K}^{*}}}\mathbb{E}[T_{i,n}]\Delta(i),$
(5)

and the _infeasibility regret_ of policy $\pi$ over $n$ rounds is

$\mathcal{R}_{n}^{\mathsf{inf}}(\pi)=\sum_{i\in\mathcal{K}_{\tau}^{c}}\mathbb{E}[T_{i,n}]\Delta_{\tau}(i,\alpha).$
(6)

  2. 2.

For an infeasible instance, let

$\mathcal{K}^{*}=\left\\{{i\in[K]:c_{\alpha}(i)=\min_{j\in[K]}c_{\alpha}(j)}\right\\}$

denote the set of optimal arms (and without loss of generality suppose
$1\in\mathcal{K}^{*}$). The _risk regret_ of policy $\pi$ over $n$ rounds is

$\mathcal{R}_{n}^{\mathsf{risk}}(\pi)=\sum_{i\in{[K]}\backslash{\mathcal{K}^{*}}}\mathbb{E}[T_{i,n}]\Delta_{\mathrm{r}}(i,\alpha).$
(7)

In the following, we design and analyse CVaR-TS which aims to simultaneously
minimize the three regrets in (5), (6), and (7). To assess the optimality of
CVaR-TS, we define the notion of consistency in this risk-constrained setting.

######  Definition 4.

A policy $\pi$ is suboptimality-consistent if
$\mathcal{R}_{n}^{\mathsf{sub}}(\pi)=o(n^{a})$ for any $a>0$. Similarly, $\pi$
is infeasibility-consistent (resp. risk-consistent) if
$\mathcal{R}_{n}^{\mathsf{inf}}(\pi)=o(n^{a})$ (resp.
$\mathcal{R}_{n}^{\mathsf{risk}}(\pi)=o(n^{a})$) for any $a>0$.

##  3 The CVaR-TS Algorithm

In this section, we introduce the CVaR Thompson Sampling (CVaR-TS) algorithm
for Gaussian bandits with bounded variances, i.e., $\nu\in{\cal E}_{\cal
N}^{K}(\sigma_{\max}^{2})$ where

$\displaystyle{\cal E}_{\cal N}^{K}(\sigma_{\max}^{2})$
$\displaystyle=\big{\\{}\nu=(\nu_{1},\dots,\nu_{K}):$
$\displaystyle\qquad\nu_{i}\sim{\cal
N}(\mu_{i},\sigma_{i}^{2}),\sigma_{i}^{2}\leq\sigma_{\max}^{2},\forall\,i\in[K]\big{\\}}$

for some $\sigma_{\max}^{2}>1$. Instead of choosing the arm based on the
optimism in the face of uncertainty principle as in Kagrecha et al. (2020a),
the algorithm samples from the posteriors of each arm, then chooses the arm
according to a multi-criterion procedure.

As is well known, a crucial step of Thompson sampling algorithms is the
updating of parameters based on Bayes rule. Denote the mean and precision of
the Gaussian by $\mu$ and $\phi$ respectively. If
$(\mu,\phi)\sim\mathrm{Normal}\text{-}\mathrm{Gamma}(\mu,T,\alpha,\beta)$,
then $\phi\sim\mathrm{Gamma}(\alpha,\beta)$, and
$\mu|\phi\sim\mathcal{N}(\mu,1/(\phi T))$. Since the Normal-Gamma distribution
is the conjugate prior for the Gaussian with unknown mean and variance, we use
Algorithm 1 to update $(\mu,\phi)$.

Algorithm 1
$\mathrm{Update}(\hat{\mu}_{i,t-1},T_{i,t-1},\alpha_{i,t-1},\beta_{i,t-1})$

1: Input: Prior parameters $(\hat{\mu}_{i,t-1}$, $T_{i,t-1}$,
$\alpha_{i,t-1}$, $\beta_{i,t-1})$ and new sample $X_{i,t}$

2: Update the mean:
$\hat{\mu}_{i,t}=\frac{T_{i,t-1}}{T_{i,t-1}+1}\hat{\mu}_{i,t-1}+\frac{1}{T_{i,t-1}+1}X_{i,t}$

3: Update the number of samples, the shape parameter, and the rate parameter:
$T_{i,t}=T_{i,t-1}+1$, $\alpha_{i,t}=\alpha_{i,t-1}+\frac{1}{2}$,
$\beta_{i,t}=\beta_{i,t-1}+\frac{T_{i,t-1}}{T_{i,t-1}+1}\cdot\frac{{(X_{i,t}-\hat{\mu}_{i,t-1})}^{2}}{2}$

We present a Thompson sampling-based algorithm to solve the CVaR Gaussian MAB
problem. The player chooses a prior over the set of feasible bandits
parameters for both the mean and precision. In each round $t$, for each arm
$i$, the player samples a pair of parameters $(\theta_{it},\kappa_{it})$ from
the posterior distribution of arm $i$, then forms the set

$\hat{\mathcal{K}}_{t}:=\left\\{{k\in[K]:\hat{c}_{\alpha}(k,t)=\theta_{kt}\Big{(}\frac{\alpha}{1-\alpha}\Big{)}\\!+\\!\frac{1}{\sqrt{\kappa_{kt}}}c_{\alpha}^{*}\\!\leq\\!\tau}\right\\}.$

If $\hat{\mathcal{K}}_{t}$ is nonempty, i.e., it is plausible that there are
some feasible arms available, choose arm $j$ if
$\theta_{jt}=\min_{k\in\hat{\mathcal{K}}_{t}}\theta_{kt}$. Otherwise, choose
arm $j$ if $j=\mathrm{arg\ min}_{k\in[k]}\hat{c}_{\alpha}(k,t)$; that is,
choose the least infeasible arm available. At the end of the algorithm, we
also set a FeasibilityFlag that checks if the instance is feasible. Kagrecha
et al. (2020a) provided bounds on the probability of incorrect flagging by any
consistent algorithm, and we have empirically compared the errors induced by
both algorithms in Section 6. We find that for a moderate horizon $n\approx
1000$, CVaR-TS does not perform worse than RC-LCB in this aspect; yet regret-
wise, CVaR-TS often performs much better. We provide an explanation for this
phenomenon in Section 6.

Algorithm 2 CVaR Thompson Sampling (CVaR-TS)

1: Input: Threshold $\tau$, constant $\alpha$, $\hat{\mu}_{i,0}=0$,
$T_{i,0}=0$, $\alpha_{i,0}=\frac{1}{2}$, $\beta_{i,0}=\frac{1}{2}$

2: for $t=1,2,\ldots,K$ do

3: Play arm $t$ and update $\hat{\mu}_{t,t}=X_{t,t}$

4: $\mathrm{Update}(\hat{\mu}_{t,t-1},T_{t,t-1},\alpha_{t,t-1},\beta_{t,t-1})$

5: end for

6: for $t=K+1,K+2,...$ do

7: Sample $\kappa_{i,t}$ from $\mathrm{Gamma}(\alpha_{i,t-1},\beta_{i,t-1})$

8: Sample $\theta_{i,t}$ from $\mathcal{N}(\hat{\mu}_{i,t-1},1/T_{i,t-1})$

9: Set
$\hat{c}_{\alpha}(i,t)=\theta_{i,t}\big{(}\frac{\alpha}{1-\alpha}\big{)}+\frac{1}{{\sqrt{\kappa_{i,t}}}}c_{\alpha}^{*}$

10: Set
$\hat{\mathcal{K}}_{t}=\left\\{k:\hat{c}_{\alpha}(k,t)\leq\tau\right\\}$

11: if $\hat{\mathcal{K}}_{t}\neq\emptyset$ then

12: Play arm $i(t)=\mathrm{arg\ min}_{k\in\hat{\mathcal{K}}_{t}}\theta_{i,t}$
and observe loss $X_{i(t),t}\sim\nu(i(t))$

13:
$\mathrm{Update}(\hat{\mu}_{i(t),t-1},T_{i(t),t-1},\alpha_{i(t),t-1},\beta_{i(t),t-1})$

14: else

15: Play arm $i(t)=\mathrm{arg\
min}_{k\in\hat{\mathcal{K}}_{t}}\hat{c}_{\alpha}(k,t)$ and observe loss
$X_{i(t),t}\sim\nu(i(t))$

16:
$\mathrm{Update}(\hat{\mu}_{i(t),t-1},T_{i(t),t-1},\alpha_{i(t),t-1},\beta_{i(t),t-1})$

17: end if

18: end for

19: if $\hat{\mathcal{K}}_{t}\neq\emptyset$ then

20: Set FeasibilityFlag = true

21: else

22: Set FeasibilityFlag = false

23: end if

##  4 Regret Bounds of CVaR-TS and Lower Bounds

We present our regret bounds in the following theorems. We then compare our
bounds to those of other competing algorithms. Most comparisons of results are
with respect to Theorem 1, since a natural definition of regret induced by the
CVaR risk measure is considered in Khajonchotpanya et al. (2020), Tamkin et
al. (2019), Xi et al. (2020), and Soma & Yoshida (2020). We also compare these
bounds to instance-dependent lower bounds (Kagrecha et al., 2020a, Theorem 4)
that we particularize to Gaussian bandits.

######  Theorem 1.

Fix $\xi\in(0,1)$, $\alpha\in(1/2,1)$. In an infeasible instance, the
asymptotic expected risk regret of CVaR-TS for CVaR Gaussian bandits satisfies

$\displaystyle\limsup_{n\to\infty}\frac{\mathcal{R}_{n}^{\mathsf{risk}}(\text{CVaR-
TS})}{\log
n}\leq\sum_{i\in{[K]}\backslash{\mathcal{K}^{*}}}C_{\alpha,\xi}^{i}\Delta_{\mathrm{r}}(i,\alpha),$

where
$C_{\alpha,\xi}^{i}=\max\big{\\{}A_{\alpha,\xi}^{i},B_{\alpha,\xi}^{i}\big{\\}}$,

$\displaystyle A_{\alpha,\xi}^{i}$
$\displaystyle=\frac{2\alpha^{2}}{\xi^{2}{(1-\alpha)}^{2}\Delta_{r}^{2}(i,\alpha)},$
(8) $\displaystyle B_{\alpha,\xi}^{i}$
$\displaystyle=\frac{1}{h\left({\frac{\sigma_{i}^{2}{(c_{\alpha}^{*})}^{2}}{{\left({\sigma_{i}c_{\alpha}^{*}-(1-\xi)\Delta_{\mathrm{r}}(i,\alpha)}\right)}^{2}}}\right)},\quad\mbox{and}$
(9) $\displaystyle h(x)$ $\displaystyle=\textstyle\frac{{1}}{{2}}(x-1-\log
x).$

Furthermore, choosing

$\xi_{\alpha}=1-\frac{\sigma_{i}c_{\alpha}^{*}}{\Delta_{\mathrm{r}}(i,\alpha)}\left({1-\frac{1}{\sqrt{h_{+}^{-1}(1/A_{\alpha,1}^{i})}}}\right),$
(10)

where $h_{+}^{-1}(y)=\max\left\\{{x:h(x)=y}\right\\}\geq 1$, yields
$B_{\alpha,\xi_{\alpha}}^{i}\leq A_{\alpha,\xi_{\alpha}}^{i}$ and
$\xi_{\alpha}\to 1^{-}$ as $\alpha\to 1^{-}$.

######  Remark 1.

The final part of the theorem claims that the upper bound is characterised by
$A_{\alpha,\xi_{\alpha}}^{i}$. By continuity, we obtain the regret bound
involving $A_{\alpha,1}^{i}$ as defined in (8) with $\xi_{\alpha}\to 1^{-}$
given by (10). We remark that this asymptotic regret bound is tighter than
several existing results under certain regimes, as summarised in Table 1,
which lists the upper bounds on the expected number of pulls
$\mathbb{E}[T_{i,n}]$ of a non-optimal arm $i$ over a horizon $n$ by various
policies $\pi$.

Paper |  Expected number of pulls $\mathbb{E}[T_{i,n}]$ | Conditions
---|---|---
(1) | $\frac{16\log(Cn)}{\beta^{2}\Delta_{r}^{2}(i,\alpha)}+K(1+\frac{\pi^{2}}{3})$ | $\alpha^{2}\leq 8$
(2) | $\frac{2\gamma\log n}{\beta^{2}\Delta_{r}^{2}(i,\alpha)}+\frac{\gamma}{2}\left({\frac{1}{\gamma-2}+\frac{3}{\gamma-20\beta}}\right)$ | $\alpha^{2}\leq\gamma$
(3) | $\frac{4U^{2}\log(\sqrt{2}n)}{\beta^{2}\Delta_{r}^{2}(i,\alpha)}+3$ | $\alpha^{2}\leq 2U^{2}$
(4) | $\frac{4\log(2D_{\sigma}n^{2})}{\beta^{2}\Delta_{r}^{2}(i,\alpha)d_{\sigma}}+K+2$ | $\alpha^{2}\leq\frac{4}{d_{\sigma}}$
Table 1:  Comparison of the expected regret of CVaR-TS to those of existing
CVaR MAB algorithms: (1) CVaR-LCB by Bhat & L.A. (2019, Theorem 1), (2) CVaR-
UCB-1 by Khajonchotpanya et al. (2020, Lemma 4), (3) CVaR-UCB-2 by Tamkin et
al. (2019), (4) RC-LCB by Kagrecha et al. (2020a, Theorem 2). We abbreviate
$1-\alpha$ by $\beta$. The second column corresponds the expected number of
pulls of a non-optimal arm $i$ over horizon $n$, which suffices to provide
comparisons on the expected regret bounds. The last column states conditions
under which CVaR-TS performs better than the algorithm in comparison. See
Remark 3 for details.

######  Remark 2.

For any arm $i$, $\lim_{\alpha\to
1^{-}}(1-\alpha)\Delta_{r}(i,\alpha)=\mu_{i}-\mu_{1}$, and the upper bound
simplifies to ${2}/{{(\mu_{i}-\mu_{1})}^{2}}$. This agrees with our intuition
because as $\alpha\to 1^{-}$,
$c_{\alpha}(i)=\mu_{i}\big{(}\frac{\alpha}{1-\alpha}\big{)}+\sigma_{i}c_{\alpha}^{*}$
is dominated by $\mu_{i}\big{(}\frac{\alpha}{1-\alpha}\big{)}$, implying that
we are in the risk-neutral setting. Thus, the results are analogous to those
derived for mean-variance bandits (Zhu & Tan, 2020) for the risk-neutral
setting when $\rho\to+\infty$ (recall the mean-variance of arm $i$ is
$\mathrm{MV}_{i}=\rho\mu_{i}-\sigma_{i}^{2}$).

######  Remark 3.

From Table 1, we see that CVaR-TS outperforms existing state-of-the-art CVaR
MAB algorithms on Gaussian bandits under certain regimes.

  1. 1.

We see that CVaR-TS outperforms CVaR-LCB (Bhat & L.A., 2019) unconditionally
since $\alpha\in(0,1)$ in Definition 1, and hence $\alpha^{2}<1\leq 8$
trivially. Replacing $8$ in Remark 3.1 with $2\leq\gamma$, where $\gamma$ is
the UCB parameter in (Khajonchotpanya et al., 2020) (denoted as $\alpha$
therein), yields the conclusion that CVaR-TS outperforms CVaR-UCB-1
unconditionally.

  2. 2.

Our regret bound for CVaR-TS is tighter than that of CVaR-UCB-2 in Tamkin et
al. (2019) when $\alpha^{2}\leq 2U^{2}$, where $U>0$ is any upper bound on the
supports of the distributions of the $K$ bandits. Notice that we do not need
to assume that the arm distributions are bounded (since our arm distributions
are Gaussian), which is different from Tamkin et al. (2019) (and also the
contemporaneous work of Baudry et al. (2020)).

  3. 3.

Our regret bound for CVaR-TS is tighter than that of RC-LCB when
$\alpha^{2}\leq{4}/{d_{\sigma}}$, where $\sigma$ is the fixed sub-Gaussianity
parameter of the bandits. We remark that Kagrecha et al. (2020a, Lemma 1)
included the implicit constants $D_{\sigma}$ and $d_{\sigma}$ in their
algorithm design due to an LCB-style concentration bound derived from Bhat &
L.A. (2019, Corollary 1), which in turn was derived from a concentration of
measure result involving the Wasserstein distance in Fournier & Guillin
(2015). Note that $d_{\sigma}$ is non-trivial to compute as it is implicitly
stated, so we estimate it to be ${1}/(8\sigma^{2})$ based on an explicit
concentration bound for $d_{\sigma}$ in L.A. et al. (2020, Theorem 3.1). With
this choice, CVaR-TS outperforms RC-LCB when the sub-Gaussianity parameter of
the $K$ bandits $\sigma$ satisfies $\sigma^{2}\geq{\alpha^{2}}/{32}$.

######  Theorem 2.

Fix $\xi\in(0,1)$, $\alpha\in(1/2,1)$. In a feasible instance, the asymptotic
expected infeasibility regret of CVaR-TS for CVaR Gaussian bandits satisfies

$\displaystyle\limsup_{n\to\infty}\frac{\mathcal{R}_{n}^{\mathsf{inf}}(\text{CVaR-
TS})}{\log
n}\leq\sum_{i\in\mathcal{K}_{\tau}^{c}}F_{\alpha,\xi}^{i}\Delta_{\tau}(i,\alpha),$

where
$F_{\alpha,\xi}^{i}=\max\big{\\{}D_{\alpha,\xi}^{i},E_{\alpha,\xi}^{i}\big{\\}}$,

$\displaystyle D_{\alpha,\xi}^{i}$
$\displaystyle=\frac{2\alpha^{2}}{\xi^{2}{(1-\alpha)}^{2}\Delta_{\tau}^{2}(i,\alpha)},\quad\mbox{and}$
(11) $\displaystyle E_{\alpha,\xi}^{i}$
$\displaystyle=\frac{1}{h\left({\frac{\sigma_{i}^{2}{(c_{\alpha}^{*})}^{2}}{{\left({\sigma_{i}c_{\alpha}^{*}-(1-\xi)\Delta_{\tau}(i,\alpha)}\right)}^{2}}}\right)}.$

Furthermore, choosing

$\xi_{\alpha}=1-\frac{\sigma_{i}c_{\alpha}^{*}}{\Delta_{\tau}(i,\alpha)}\left({1-\frac{1}{\sqrt{h_{+}^{-1}(1/D_{\alpha,1}^{i})}}}\right)$
(12)

yields $E_{\alpha,\xi_{\alpha}}^{i}\leq D_{\alpha,\xi_{\alpha}}^{i}$ and
$\xi_{\alpha}\to 1^{-}$ as $\alpha\to 1^{-}$.

######  Remark 4.

As with Theorem 1, the final part of the theorem says that the upper bound is
characterised by $D_{\alpha,\xi_{\alpha}}^{i}$. By continuity, we obtain the
regret bound of $D_{\alpha,1}^{i}$ as defined in (11) with $\xi_{\alpha}\to
1^{-}$ given by (12). This is expected, since
$(c_{\alpha}(1),\Delta_{\mathrm{r}}(i,\alpha))$ can be replaced by
$(\tau,\Delta_{\tau}(i,\alpha))$ analogously for infeasible arms in the
infeasible case, and the computations can be similarly reused. Likewise, this
regret bound is tighter than RC-LCB (Kagrecha et al. (2020a, Theorem 2),
$\mathbb{E}[T_{i,n}]\leq{4\log(2D_{\sigma}n^{2})}/{(\beta^{2}\Delta_{\tau}^{2}(i,\alpha)d_{\sigma})}$)
provided that $d_{\sigma}\leq 4$.

######  Theorem 3.

In a feasible instance, the asymptotic expected suboptimality regret of CVaR-
TS for CVaR Gaussian bandits satisfies

$\displaystyle\limsup_{n\to\infty}\frac{\mathcal{R}_{n}^{\mathsf{sub}}(\text{CVaR-
TS})}{\log
n}\leq\sum_{i\in{\mathcal{K}_{\tau}}\backslash{\mathcal{K}^{*}}}\frac{2}{\Delta(i)}.$
(13)

######  Remark 5.

This is expected, since the problem reduces to a standard MAB. Our empirical
simulations in Section 6 corroborate this result. Additionally, our regret
bound is tighter than RC-LCB (in which
$\mathbb{E}[T_{i,n}]\leq{(16\sigma^{2}\log n)}/{\Delta^{2}(i)}$) under the
condition that $\sigma^{2}\geq{1}/{8}$ (where $\sigma$ is the largest sub-
Gaussianity parameter of the arms).

######  Remark 6.

For an infeasible and suboptimal arm $i$ in a feasible instance, the expected
number of pulls us upper bounded by ${2}/{\Delta^{2}(i)}$ and
$D_{\alpha,\xi}^{i}$, and thus can be written as

$\limsup_{n\to\infty}\frac{\mathbb{E}[T_{i,n}]}{\log
n}\leq\min\left\\{{\frac{2}{\Delta^{2}(i)},D_{\alpha,\xi}^{i}}\right\\}.$

This agrees with the regret analysis of RC-LCB if we take $\alpha\to 1^{-}$
and choose $\xi_{\alpha}\to 1^{-}$ according to (12).

######  Theorem 4 (Lower Bounds).

Fix a risk threshold $\tau\in\mathbb{R}$, $\xi\in(0,1)$ and $\alpha\in(1/2,1)$
Recall the definitions of $A_{\alpha,\xi}^{i}$ and $D_{\alpha,\xi}^{i}$ in (8)
and (11) respectively.

  1. 1.

In an infeasible instance $(\nu,\tau)$, where $\nu\in{\cal E}_{\cal
N}^{K}(\sigma_{\max}^{2})$, for any risk-consistent policy $\pi$,

$\liminf_{n\to\infty}\frac{\mathcal{R}_{n}^{\mathsf{risk}}(\pi)}{\log
n}\geq\sum_{i\in{[K]}\backslash{\mathcal{K}^{*}}}\xi^{2}\sigma_{i}^{2}A_{\alpha,\xi}^{i}\Delta_{\mathrm{r}}(i,\alpha).$

  2. 2.

In a feasible instance $(\nu,\tau)$, where $\nu\in{\cal E}_{\cal
N}^{K}(\sigma_{\max}^{2})$, for any infeasibility-consistent policy $\pi$,

$\liminf_{n\to\infty}\frac{\mathcal{R}_{n}^{\mathsf{inf}}(\pi)}{\log
n}\geq\sum_{i\in\mathcal{K}_{\tau}^{c}}\xi^{2}\sigma_{i}^{2}D_{\alpha,\xi}^{i}\Delta_{\tau}(i).$

Also, for any suboptimality-consistent policy $\pi$,

$\liminf_{n\to\infty}\frac{\mathcal{R}_{n}^{\mathsf{sub}}(\pi)}{\log
n}\geq\sum_{i\in{\mathcal{K}_{\tau}}\backslash{\mathcal{K}^{*}}}\frac{2}{\Delta(i)}.$

######  Remark 7.

We see that the asymptotic lower bound for the suboptimality regret matches
its asymptotic upper bound in Theorem 3. Furthermore, if the standard
deviations of the Gaussian arms satisfy
$1\leq\sigma_{1}\leq\sigma_{i}\leq\sigma_{\max}$ for all $i\in[K]$ and
$\alpha\to 1^{-}$, together with the appropriate choices of $\xi_{\alpha}$ in
(10) and (12), we see that the asymptotic lower bounds in Parts 1 and 2 of
Theorem 4 match their respective asymptotic upper bounds in Theorems 1 and 2.
Thus, CVaR-TS is asymptotically optimal in the risk regret (Theorem 1) and
infeasiblity regret (Theorem 2) if
$1\leq\sigma_{1}\leq\sigma_{i}\leq\sigma_{\max}$. CVaR-TS is asymptotically
optimal in the suboptimality regret (Theorem 3) unconditionally.

The main idea in the proof of Theorem 4 is to particularize the instance-
dependent lower bounds in Kagrecha et al. (2020a, Theorem 4) for Gaussian CVaR
MABs. For Part 1, the vanilla lower bound is stated in terms of the KL-
divergence between the distribution of arm $i$ infimized over the distribution
of an alternative arm whose Gaussian CVaR is less than $c_{\alpha}^{*}$. We
judiciously choose the distribution of the alternative arm $\nu^{\prime}(i)$
to be ${\cal
N}\left({\mu_{i}-\frac{1}{\xi}{\sqrt{2/A_{\alpha,\xi}^{i}}}-\varepsilon,\sigma_{i}^{2}}\right)$
for each $\varepsilon>0$, which then yields the almost-optimal lower bound in
view of Remark 7.

##  5 Proof Outline of Theorem 1 and Extensions

We outline the proof of Theorem 1, since it is the most involved. Theorem 2
follows by a straightforward substitution and Theorem 3 is analogous to the
proof of Thompson sampling for standard MAB. Denote the sample CVaR (the
Thompson sample) as
$\hat{c}_{\alpha}(i,t)=\theta_{i,t}\Big{(}\frac{\alpha}{1-\alpha}\Big{)}+\frac{1}{\sqrt{\kappa_{i,t}}}c_{\alpha}^{*}$.
Fix $\varepsilon>0$ and define
$E_{i}(t):=\left\\{{\hat{c}_{\alpha}(i,t)>c_{\alpha}(1)+\varepsilon}\right\\}$
the event that the Thompson sample mean of arm $i$ is $\varepsilon$-riskier
than a certain threshold or, more precisely, $\varepsilon$-higher than the
optimal arm (which has the lowest CVaR, quantifying the expected loss).
Intuitively, event $E_{i}(t)$ is highly likely to occur when the algorithm has
explored sufficiently. However, the algorithm does not choose arm $i$ when
$E_{i}^{c}(t)$ occurs with small probability under Thompson sampling. We can
split $\mathbb{E}[T_{i,n}]$ into two parts as follows.

######  Lemma 1 (Lattimore & Szepesvári (2020)).

Let
$\mathbb{P}_{t}(\,\cdot\,)=\mathbb{P}(\,\cdot\,|A_{1},X_{1},\dots,A_{t-1},X_{t-1})$
be the probability measure conditioned on the history up to time $t-1$ and
$G_{is}=\mathbb{P}_{t}(E_{i}^{c}(t)|T_{i,t}=s)$, where $E_{i}(t)$ is any
specified event for arm $i$ at time $t$. Denote
$\Lambda_{1}=\mathbb{E}\big{[}\sum_{s=0}^{n-1}\big{\\{}\frac{1}{G_{1s}}-1\big{\\}}\big{]}$
and $\Lambda_{2}=\sum_{s=0}^{n-1}\mathbb{P}\left({G_{is}>\frac{1}{n}}\right)$.
Then $\mathbb{E}[T_{i,n}]\leq\Lambda_{1}+\Lambda_{2}+1$.

It remains to upper bound $\Lambda_{1}$ and $\Lambda_{2}$. The techniques used
to upper-bound $\Lambda_{1}$ resemble those in Zhu & Tan (2020), and are
relegated to the supplementary material. To upper bound $\Lambda_{2}$, we
split the event $E_{i}^{c}(t)=\left\\{{\hat{c}_{\alpha}(i,t)\leq
c_{\alpha}(1)+\varepsilon}\right\\}$ into

$\displaystyle\Psi_{1}(\xi)$
$\displaystyle=\left\\{{\left({\theta_{i,t}\\!-\\!\mu_{i}}\right)\left({\textstyle\frac{{\alpha}}{{1\\!-\\!\alpha}}}\right)\\!\leq\\!-\xi(\Delta_{\mathrm{r}}(i,\alpha)\\!-\\!\varepsilon)}\right\\},$
$\displaystyle\Psi_{2}(\xi)$
$\displaystyle=\left\\{{\left({\textstyle\frac{{1}}{{\sqrt{\kappa_{i,t}}}}-\sigma_{i}}\right)c_{\alpha}^{*}\leq(-1+\xi)(\Delta_{\mathrm{r}}(i,\alpha)-\varepsilon)}\right\\}.$

That is, $E_{i}^{c}(t)\subseteq\Psi_{1}(\xi)\cup\Psi_{2}(\xi)$. We then use
the union bound which yields
$\mathbb{P}(E_{i}^{c}(t))\leq\mathbb{P}(\Psi_{1}(\xi))+\mathbb{P}(\Psi_{2}(\xi))$
and concentration bounds to upper bound $\mathbb{P}(\Psi_{1}(\xi))$ and
$\mathbb{P}(\Psi_{2}(\xi))$. A good choice of the free parameter $\xi$ allows
us to allocate “weights” to the bounds on $\mathbb{P}(\Psi_{1}(\xi))$ and
$\mathbb{P}(\Psi_{2}(\xi))$ which then yields $A_{\alpha,\xi}^{i}$ and
$B_{\alpha,\xi}^{i}$ (in (8) and (9)) without incurring further residual
terms.

#### Extensions and Improvements to Existing Works

The Thompson sample of the Gaussian CVaR is of the form
$af(\theta)+bg(1/\kappa)$, where $\theta$ and $\kappa$ follow a Gaussian and
Gamma distribution respectively, $f(x)=x,g(x)=\sqrt{x}$ are bijective on their
natural domains and have inverses $f^{-1},g^{-1}$ respectively, and
$a=\alpha/(1-\alpha),b=c_{\alpha}^{*}$ depend on $\alpha$. By splitting the
Thompson sample $\hat{c}_{\alpha}(i,t)$ into two parts as described in the
previous paragraph, and using $f^{-1}$ and $g^{-1}$, we reduced the problem to
upper bounding probabilities of the form $\mathbb{P}(\theta\leq\cdot)$ and
$\mathbb{P}(\kappa\geq\cdot)$ and concentration bounds can then be readily
applied. This hints that for general risk measures on Gaussian bandits with
Thompson samples of the form $af(\theta)+bg(1/\kappa)$, a similar strategy can
be used to establish tight regret bounds. For example, the entropic risk (Lee
et al., 2020; Howard & Matheson., 1972) with parameter $\gamma$ of a Gaussian
random variable $X\sim{\cal N}(\mu,\sigma^{2})$ is
$\frac{1}{\gamma}\log\mathbb{E}[\exp(-\gamma X)]=-\mu+(\gamma/2)\sigma^{2}$
with a corresponding Thompson sample $-\theta+(\gamma/2)(1/\kappa)$, where
$(f(x),g(x),a,b)=(x,x,-1,\gamma/2)$, and our techniques are also immediately
amenable to the entropic risk. Similarly, the mean-variance risk measure (Lee
et al., 2020; Zhu & Tan, 2020) with parameter $\rho$ of $X\sim{\cal
N}(\mu,\sigma^{2})$ is $\rho\mu-\sigma^{2}$, with a corresponding Thompson
sample $\rho\theta-1/\kappa$, where $(f(x),g(x),a,b)=(x,x,\rho,-1)$. In fact,
using our techniques and, in particular arguments, similar to Lemmas 6 and 8,
we can immediately strengthen the regret bound of MVTS in Zhu & Tan (2020,
Theorem 3) from being dependent on $O((\mu_{i}-\mu_{1})^{-2})$ to
$O((\mathrm{MV}_{i}-\mathrm{MV}_{1})^{-2})$. If instead $f$ and $g$ take very
different forms, establishing regret bounds might be more challenging and
require new analytical techniques.

##  6 Numerical Simulations

Figure 1: Risk regrets averaged over $100$ runs of instances whose arms follow
Gaussian distributions with means and variances according to
$(\mu,\sigma_{>}^{2})$ and $(\mu,\sigma_{\approx}^{2})$ respectively. The
error bars indicate $\pm 1$ standard deviations over the $100$ runs.

Figure 2: Infeasibility regrets averaged over $100$ runs of instances whose
arms follow Gaussian distributions with means and variances according to
$(\mu,\sigma_{>}^{2})$ and $(\mu,\sigma_{\approx}^{2})$ respectively.

Figure 3: Suboptimality regrets averaged over $100$ runs of instances whose
arms follow Gaussian distributions with means and variances according to
$(\mu,\sigma_{>}^{2})$ and $(\mu,\sigma_{\approx}^{2})$ respectively.

We verify the theory developed using numerical simulations. Set parameters
$(N,\alpha,\tau,K,n)=(100,0.95,4.6,15,1000)$. We present regret that is
averaged over $N$ statistically independent runs of horizon $n$. For the
$K=15$ arms, we set their means as per the experiments in Sani et al. (2012)
and Zhu & Tan (2020), namely, $\mu=(0.1$, $0.2$, $0.23$, $0.27$, $0.32$,
$0.32$, $0.34$, $0.41$, $0.43$, $0.54$, $0.55$, $0.56$, $0.67$, $0.71$,
$0.79$).

By L.A. et al. (2020, Theorem 3.1) and Kagrecha et al. (2020a, Lemma 1), we
have $(D_{\sigma},d_{\sigma})=(3,{1}/{(8\sigma^{2})})$ where we set
$\varepsilon<2\delta$ therein for simplicity. Under this regime, the regret
bounds for CVaR-TS are tighter than those of RC-LCB when the sub-Gaussianity
paramater $\sigma$ satisfies $\sigma^{2}\geq{1}/{32}=0.03125$. Thus, when
investigating Gaussian bandits with variances significantly larger than (resp.
close to) ${1}/{32}$, we set the variances of the arms according to
$\sigma_{>}^{2}$ (resp. $\sigma_{\approx}^{2}$), where $\sigma_{>}^{2}=$
$(0.045$, $0.144$, $0.248$, $0.339$, $0.243$, $0.172$, $0.039$, $0.144$,
$0.244$, $0.353$, $0.244$, $0.146$, $0.056$, $0.149$, $0.285)$ (resp.
$\sigma_{\approx}^{2}=(0.0321$, $0.0332$, $0.0355$, $0.0464$, $0.0375$,
$0.0486$, $0.0397$, $0.0398$, $0.0387$, $0.0378$, $0.0567$, $0.0456$,
$0.0345$, $0.0334$, $0.0323)$). In this setup, the first $2$ arms are
feasible, and arm $1$ is optimal. We additionally set $\tau=2$ to investigate
an infeasible instance. We run MaRaB (Galichet et al., 2013), RC-LCB (Kagrecha
et al., 2020a) and CVaR-TS.

Our results are shown in Figures 1–3. Each pair of figures compares the risk,
infeasibility and suboptimality regrets (cf. Definition 3) under the regime
with variances $\sigma_{>}^{2}$ and $\sigma_{\approx}^{2}$. We see a much
superior performance by CVaR-TS for instances with $\sigma^{2}\gg{1}/{32}$,
corroborating the theoretical conclusion of our regret analyses (summarized in
Table 1). When $\sigma^{2}\approx 1/32$, CVaR-TS still outperforms RC-LCB but
not by much. Compared to MaRaB, CVaR-TS also performs better, sometimes
significantly, in terms all the regrets and variances $\sigma_{>}^{2}$ and
$\sigma_{\approx}^{2}$. The Python code is included in the supplementary
material.

Setup | RC-LCB | CVaR-TS | MaRaB
---|---|---|---
$\sigma_{>}^{2}$ | $0.00$ | $0.00$ | $0.00$
$\sigma_{\approx}^{2}$ | $0.00$ | $0.00$ | $0.00$
Table 2:  Comparison of the proportions of wrong flags $r/N$, i.e., flagging a feasible instance as infeasible. All algorithms perform well in the feasible instance where $\tau=4.6$. Setup | RC-LCB | CVaR-TS | MaRaB
---|---|---|---
$\sigma_{>}^{2}$ | $1.00$ | $0.02$ | $0.99$
$\sigma_{\approx}^{2}$ | $1.00$ | $0.03$ | $1.00$
Table 3:  Comparison of $r/N$ of flagging an infeasible instance as feasible.
When $\tau=2$, to have $r/N\approx 0$, we need $n\geq 312,678$ for RC-LCB. We
omit this due to computational limitations.

Another consideration is the flagging of instances as feasible when in fact
they are infeasible and vice versa (Lines 19–23 of Algorithm 2). This was
analyzed by (Kagrecha et al., 2020a). In Tables 2 and 3, we tabulate $r/N$
where $N=100$ is the total number of statistically independent runs and $r$ is
the number of times that the various algorithms CVaR-TS (Algorithm 2), MaRaB
(Galichet et al., 2013), and RC-LCB (Kagrecha et al., 2020a) declare the flag
incorrectly. Table 2 compares the proportions of flagging a feasible instance
as infeasible while Table 3 compares the proportions of flagging an infeasible
instance as feasible. We see from Table 2 that all algorithms perform well in
this particular respect. However, from Table 3, the situation is clearly in
favor of CVaR-TS. This is partly because the parameters for the confidence
bounds in RC-LCB and MaRaB are too conservative in favor of declaring
feasibility. Furthermore, for RC-LCB, one requires a lower bound on the
horizon $n$ for the performance guarantee to hold (see Subsection A.6 which
contains the proof of Theorem 2 of Kagrecha et al. (2020a)) and for the
particular examples we experimented with, the lower bound was prohibitively
large. Indeed, for RC-LCB, we must have
$\hat{c}_{\alpha}(i)-c_{\alpha}(i)>\tau-
c_{\alpha}(i)+\frac{1}{1-\alpha}\sqrt{(\log(2D_{\sigma}n^{2}))/(nd_{\sigma})}$
(and $\tau-c_{\alpha}(i)<0$) which translates to the horizon $n\geq 312,678$.
In contrast, CVaR-TS is parameter-free for attaining a far lower rate of
incorrect flagging and outperforms RC-LCB and MaRaB in terms of ensuring that
the error rate for declaring an infeasible instances as feasible and vice
versa are both small.

##  7 Conclusion

This paper applies Thompson sampling (Thompson, 1933) to provide a solution
for CVaR MAB problems (Galichet et al., 2013; Kagrecha et al., 2020b;
Khajonchotpanya et al., 2020) which were largely approached from the L/UCB
perspectives previously. The regret bounds are notable improvements over those
obtained by the state-of-the-art L/UCB techniques, when the bandits are
Gaussians satisfying certain assumptions. We show that the bounds also
coincide with instance-dependent lower bounds when $\alpha\to 1^{-}$. We
corroborated the theoretical results through simulations and verified that
under the conditions predicted by the theorems, the gains over previous
approaches are significant.

Noting the similarity of the mean-variance of a Gaussian arm when
$\rho\to+\infty$ and the CVaR of the same arm when $\alpha\to 1^{-}$, we
believe there is a unifying theory of risk measures for Gaussian MABs; see
Cassel et al. (2018), Lee et al. (2020), and Xi et al. (2020). Furthermore,
most papers consider sub-Gaussian bandits, while we focus on Gaussian
distributions. This is perhaps why we obtain better regret bounds in some
regimes. Further work includes analysing Thompson sampling of Gaussian MABs
under general risk measures and exploring the performance of Thompson sampling
for CVaR sub-Gaussian bandits.

## References

  * Abramowitz & Stegun (1970) Abramowitz, M. and Stegun, I. A.  _Handbook of mathematical functions with formulas, graphs, and mathematical tables_ , volume 55.  US Government printing office, 1970.
  * Agrawal & Goyal (2012) Agrawal, S. and Goyal, N.  Analysis of Thompson sampling for the multi-armed bandit problem.  In _Conference on Learning Theory_ , pp. 39–1, 2012.
  * Artzner et al. (1999) Artzner, P., Delbaen, F., Eber, J.-M., and Heath, D.  Coherent measures of risk.  _Mathematical Finance_ , 9(3):203–228, 1999.
  * Baudry et al. (2020) Baudry, D., Gautron, R., Kaufmann, E., and Maillard, O.-A.  Thompson sampling for CVaR bandits.  _arXiv preprint arXiv:2012.05754_ , 2020.
  * Bhat & L.A. (2019) Bhat, S. P. and L.A., P.  Concentration of risk measures: A Wasserstein distance approach.  In _Advances in Neural Information Processing Systems_ , pp. 11762–11771, 2019.
  * Cassel et al. (2018) Cassel, A., Mannor, S., and Zeevi, A.  A general approach to multi-armed bandits under risk criteria.  In _Proceedings of the 31st Conference On Learning Theory_ , pp. 1295–1306, 2018.
  * Fournier & Guillin (2015) Fournier, N. and Guillin, A.  On the rate of convergence in Wasserstein distance of the empirical measure.  _Probability Theory and Related Fields_ , 162(3-4):707–738, 2015.
  * Galichet et al. (2013) Galichet, N., Sebag, M., and Teytaud, O.  Exploration vs exploitation vs safety: Risk-aware multi-armed bandits.  In _Asian Conference on Machine Learning_ , pp. 245–260, 2013.
  * Harremoës (2016) Harremoës, P.  Bounds on tail probabilities for negative binomial distributions.  _Kybernetika_ , 52(6):943–966, 2016.
  * Howard & Matheson. (1972) Howard, R. A. and Matheson., J. E.  Risk-sensitive Markov decision processes.  _Management Science_ , 18(7):356–369, 1972.
  * Huo & Fu (2017) Huo, X. and Fu, F.  Risk-aware multi-armed bandit problem with application to portfolio selection.  _Royal Society Open Science_ , 4(11):171377, 2017\.
  * Kagrecha et al. (2020a) Kagrecha, A., Nair, J., and Jagannathan, K.  Constrained regret minimization for multi-criterion multi-armed bandits.  _arXiv preprint arXiv:2006.09649_ , 2020a.
  * Kagrecha et al. (2020b) Kagrecha, A., Nair, J., and Jagannathan, K.  Statistically robust, risk-averse best arm identification in multi-armed bandits.  _arXiv preprint arXiv:2008.13629_ , 2020b.
  * Khajonchotpanya et al. (2020) Khajonchotpanya, N., Yilin, X., and Rujeerapaiboon, N.  A revised approach for risk-averse multi-armed bandits under cvar criterion.  _ScholarBank NUS_ , 2020.
  * L.A. et al. (2020) L.A., P., Jagannathan, K., and Kolla, R. K.  Concentration bounds for CVaR estimation: The cases of light-tailed and heavy-tailed distributions.  In _International Conference on Machine Learning_ , pp. 3657–3666, 2020.
  * Lattimore & Szepesvári (2020) Lattimore, T. and Szepesvári, C.  _Bandit algorithms_.  Cambridge University Press, 2020.
  * Laurent & Massart (2000) Laurent, B. and Massart, P.  Adaptive estimation of a quadratic functional by model selection.  _Annals of Statistics_ , pp. 1302–1338, 2000.
  * Lee et al. (2020) Lee, J., Park, S., and Shin, J.  Learning bounds for risk-sensitive learning.  In _Advances in Neural Information Processing Systems_ , 2020.
  * Rockafellar & Uryasev (2000) Rockafellar, R. T. and Uryasev, S.  Optimization of conditional value-at-risk.  _Journal of Risk_ , 2(3):21–41, 2000.
  * Sani et al. (2012) Sani, A., Lazaric, A., and Munos, R.  Risk-aversion in multi-armed bandits.  In _Advances in Neural Information Processing Systems_ , pp. 3275–3283, 2012.
  * Soma & Yoshida (2020) Soma, T. and Yoshida, Y.  Statistical learning with conditional value at risk.  _arXiv preprint arXiv:2002.05826_ , 2020.
  * Sun et al. (2017) Sun, W., Dey, D., and Kapoor, A.  Risk-aversion in multi-armed bandits.  In _International Conference on Machine Learning_ , pp. 3280–3288, 2017.
  * Tamkin et al. (2019) Tamkin, A., Keramati, R., Dann, C., and Brunskill, E.  Distributionally-aware exploration for CVaR bandits.  In _Neural Information Processing Systems 2019 Workshop on Safety and Robustness in Decision Making_ , 2019.
  * Thompson (1933) Thompson, W. R.  On the likelihood that one unknown probability exceeds another in view of the evidence of two samples.  _Biometrika_ , 25(3/4):285–294, 1933.
  * Vakili & Zhao (2016) Vakili, S. and Zhao, Q.  Risk-averse multi-armed bandit problems under mean-variance measure.  _IEEE Journal of Selected Topics in Signal Processing_ , 10(6):1093–1111, 2016.
  * Xi et al. (2020) Xi, G., Tao, C., and Zhou, Y.  Near-optimal MNL bandits under risk criteria.  _arXiv preprint arXiv:2009.12511_ , 2020.
  * Zhu & Tan (2020) Zhu, Q. and Tan, V. Y.  Thompson sampling algorithms for mean-variance bandits.  In _International Conference on Machine Learning_ , pp. 2645–2654, 2020.

Supplementary Material

##  Appendix A Proof of Theorem 1

###### Proof of Theorem 1.

Denote the sample CVaR at $\alpha$ by
$\hat{c}_{\alpha}(i,t)=\theta_{i,t}\left({\frac{\alpha}{1-\alpha}}\right)+\frac{1}{\sqrt{\kappa_{i,t}}}c_{\alpha}^{*}$
(see (4)). Fix $\varepsilon>0$, and define

$E_{i}(t):=\left\\{{\hat{c}_{\alpha}(i,t)>c_{\alpha}(1)+\varepsilon}\right\\},$

the event that the Thompson sample CVaR of arm $i$ is $\varepsilon$-higher
than the optimal arm (which has the lowest CVaR). Intuitively, event
$E_{i}(t)$ is highly likely to occur when the algorithm has explored
sufficiently. However, the algorithm does not choose arm $i$ when
$E_{i}^{c}(t)$, an event with small probability under Thompson sampling,
occurs. By Lemma 1, and the linearity of expectation, we can divide
$\mathbb{E}[T_{i,n}]$ into two parts as

$\mathbb{E}[T_{i,n}]\leq\sum_{s=0}^{n-1}\mathbb{E}\left[{\frac{1}{G_{1s}}-1}\right]+\sum_{s=0}^{n-1}\mathbb{P}\left({G_{is}>\frac{1}{n}}\right)+1.$
(14)

By Lemmas 3 and 8 in the following, we have

$\displaystyle\sum_{s=1}^{n}\mathbb{E}\left[{\frac{1}{G_{1s}}-1}\right]$
$\displaystyle\leq\frac{C_{1}}{\varepsilon^{3}}+\frac{C_{2}}{\varepsilon^{2}}+\frac{C_{3}}{\varepsilon}+C_{4},\
\text{and}$
$\displaystyle\sum_{s=1}^{n}\mathbb{P}_{t}\left({G_{is}>\frac{1}{n}}\right)$
$\displaystyle\leq
1+\max\left\\{{\frac{2\alpha^{2}\log(2n)}{\xi^{2}{(1-\alpha)}^{2}\left({\Delta_{\mathrm{r}}(i,\alpha)-\varepsilon}\right)^{2}},\frac{\log(2n)}{h\left({\frac{\sigma_{i}^{2}{(c_{\alpha}^{*})}^{2}}{\left({\sigma_{i}c_{\alpha}^{*}-(1-\xi)\left({\Delta_{\mathrm{r}}(i,\alpha)-\varepsilon}\right)}\right)^{2}}}\right)}}\right\\}+\frac{C_{5}}{\varepsilon^{4}}+\frac{C_{6}}{\varepsilon^{2}}.$

Plugging the two displays into (14), we have

$\mathbb{E}[T_{i,n}]\leq
1+\max\left\\{{\frac{2\alpha^{2}\log(2n)}{\xi^{2}{(1-\alpha)}^{2}\left({\Delta_{\mathrm{r}}(i,\alpha)-\varepsilon}\right)^{2}},\frac{\log(2n)}{h\left({\frac{\sigma_{i}^{2}{(c_{\alpha}^{*})}^{2}}{\left({\sigma_{i}(c_{\alpha}^{*})-(1-\xi)\left({\Delta_{\mathrm{r}}(i,\alpha)-\varepsilon}\right)}\right)^{2}}}\right)}}\right\\}+\frac{C_{1}^{\prime}}{\varepsilon^{4}}+\frac{C_{2}^{\prime}}{\varepsilon^{3}}+\frac{C_{3}^{\prime}}{\varepsilon^{2}}+\frac{C_{4}^{\prime}}{\varepsilon}+C_{5}^{\prime},$
(15)

where
$C_{1}^{\prime},C_{2}^{\prime},C_{3}^{\prime},C_{4}^{\prime},C_{5}^{\prime}$
are constants. Setting $\varepsilon={(\log n)}^{-\frac{1}{8}}$ into (15), we
get

$\displaystyle\limsup_{n\to\infty}\frac{\mathcal{R}_{n}^{\mathsf{risk}}(\text{CVaR-
TS})}{\log n}$
$\displaystyle\leq\sum_{i\in{[K]}\backslash{\mathcal{K}^{*}}}\left({\max\left\\{{\frac{2\alpha^{2}}{\xi^{2}{(1-\alpha)}^{2}\Delta_{r}^{2}(i)},\frac{1}{h\left({\frac{\sigma_{i}^{2}{(c_{\alpha}^{*})}^{2}}{{\left({\sigma_{i}c_{\alpha}^{*}-(1-\xi)\left({\Delta_{\mathrm{r}}(i,\alpha)}\right)}\right)}^{2}}}\right)}}\right\\}}\right)\Delta_{\mathrm{r}}(i,\alpha)$
$\displaystyle=\sum_{i\in{[K]}\backslash{\mathcal{K}^{*}}}\max\left\\{{A_{\alpha,\xi}^{i},B_{\alpha,\xi}^{i}}\right\\}\Delta_{\mathrm{r}}(i,\alpha)=\sum_{i\in{[K]}\backslash{\mathcal{K}^{*}}}C_{\alpha,\xi}^{i}\Delta_{\mathrm{r}}(i,\alpha).$

∎

######  Lemma 2.

We can lower bound

$\mathbb{P}_{t}\left({E_{1}^{c}(t)\mid
T_{1,t}=s,\hat{\mu}_{1,s}=\mu,\hat{\sigma}_{1,s}=\sigma}\right)=\mathbb{P}_{t}\left({\hat{c}_{\alpha}(1,t)\leq
c_{\alpha}(1)+\varepsilon\mid
T_{1,t}=s,\hat{\mu}_{1,s}=\mu,\hat{\sigma}_{1,s}=\sigma}\right)$

by

$\displaystyle\mathbb{P}_{t}\left({\hat{c}_{\alpha}(1,t)\leq
c_{\alpha}(1)+\varepsilon\mid
T_{1,t}=s,\hat{\mu}_{1,s}=\mu,\hat{\sigma}_{1,s}=\sigma}\right)$
$\displaystyle\geq\begin{cases}\mathbb{P}_{t}\left({{\theta}_{1,t}-\mu_{1}\leq\frac{(1-\alpha)\varepsilon}{2\alpha}}\right)\cdot\mathbb{P}_{t}\left({\frac{1}{\sqrt{\kappa_{1,t}}}-\sigma_{1}\leq\frac{\varepsilon}{2c_{\alpha}^{*}}}\right)&\text{if
}\mu\geq\mu_{1},\sigma\geq\sigma_{1},\\\
\frac{1}{2}\mathbb{P}_{t}\left({\frac{1}{\sqrt{\kappa_{1,t}}}-\sigma_{1}\leq\frac{\varepsilon}{2c_{\alpha}^{*}}}\right)&\text{if
}\mu<\mu_{1},\sigma\geq\sigma_{1},\\\
\frac{1}{2}\mathbb{P}_{t}\left({{\theta}_{1,t}-\mu_{1}\leq\frac{(1-\alpha)\varepsilon}{2\alpha}}\right)&\text{if
}\mu\geq\mu_{1},\sigma<\sigma_{1},\\\ \frac{1}{4}&\text{if
}\mu<\mu_{1},\sigma<\sigma_{1}.\end{cases}$ (16)

###### Proof of Lemma 2.

Given $T_{1,t}=s,\hat{\mu}_{1,s}=\mu,\hat{\sigma}_{1,s}=\sigma$, a direct
calculation gives us,

$\displaystyle\mathbb{P}_{t}\left({\hat{c}_{\alpha}(1,t)\leq
c_{\alpha}(1)+\varepsilon\mid
T_{1,t}=s,\hat{\mu}_{1,s}=\mu,\hat{\sigma}_{1,s}=\sigma}\right)$
$\displaystyle=\mathbb{P}_{t}\left({({\theta}_{1,t}-\mu_{1})\left({\frac{\alpha}{1-\alpha}}\right)+\left({\frac{1}{\sqrt{\kappa_{1,t}}}-\sigma_{1}}\right)c_{\alpha}^{*}\leq\varepsilon}\right)$
$\displaystyle\geq\mathbb{P}_{t}\left({{\theta}_{1,t}-\mu_{1}\leq\frac{(1-\alpha)\varepsilon}{2\alpha}}\right)\cdot\mathbb{P}_{t}\left({\frac{1}{\sqrt{\kappa_{1,t}}}-\sigma_{1}\leq\frac{\varepsilon}{2c_{\alpha}^{*}}}\right).$

If $\mu<\mu_{1}$, then

$\mathbb{P}_{t}\left({\theta_{1,t}-\mu_{1}\leq\frac{(1-\alpha)\varepsilon}{2\alpha}}\right)=\mathbb{P}_{t}\left({\theta_{1,t}-\mu\leq\mu_{1}-\mu+\frac{(1-\alpha)\varepsilon}{2\alpha}}\right)\geq\frac{1}{2}$

by the properties of the median of the Gaussian distribution.

If $\sigma<\sigma_{1}$, then

$\mathbb{P}_{t}\left({\frac{1}{\sqrt{\kappa_{1,t}}}-\sigma_{1}\leq\frac{\varepsilon}{2c_{\alpha}^{*}}}\right)=\mathbb{P}_{t}\left({\frac{1}{\kappa_{1,t}}-\sigma_{1}^{2}\leq\left({\frac{\varepsilon}{2c_{\alpha}^{*}}+2\sigma_{1}}\right)\frac{\varepsilon}{2c_{\alpha}^{*}}}\right)\geq\frac{1}{2}$

by the properties of the median of the Gamma distribution. ∎

######  Lemma 3 (Upper bounding the first term of (14)).

We have

$\sum_{s=1}^{n}\mathbb{E}\left[{\frac{1}{G_{1s}}-1}\right]\leq\frac{C_{1}}{\varepsilon^{3}}+\frac{C_{2}}{\varepsilon^{2}}+\frac{C_{3}}{\varepsilon}+C_{4},$

where $C_{1},C_{2},C_{3},C_{4}$ are constants.

###### Proof of Lemma 3.

We now attempt to bound $\mathbb{E}\left[{\frac{1}{G_{1s}}-1}\right]$ by
conditioning on the various values of $\hat{\mu}_{i,s}$ and
$\hat{\sigma}_{i,s}$. Firstly, we define the conditional version of $G_{1s}$
by

$\widetilde{G}_{1s}=G_{1s}|_{\hat{\mu}_{1,s}=\mu,\hat{\sigma}_{1,s}=\beta}=\mathbb{P}_{t}\left({\hat{c}_{\alpha}(1,t)\leq
c_{\alpha}(1)+\varepsilon\mid
T_{i,t}=s,\hat{\mu}_{1,s}=\mu,\hat{\sigma}_{1,s}=\beta}\right),$

which is the $\mathrm{LHS}$ of (16). Define
$c_{1}=\frac{1}{\sqrt{2\pi\sigma_{1}^{2}}}$,
$c_{2}=\frac{1}{2^{\frac{s-3}{2}}\Gamma(\frac{s-1}{2})\sigma_{1}^{s-1}}$, and
$\omega=s\sqrt{2}\sigma_{1}$. For clarity, we partition the parameter space
$(\beta,\mu)\in[0,\infty)\times(-\infty,\infty)=A\cup B\cup C\cup D,$ where

$A=[0,\omega)\times[\mu_{1}+\textstyle\frac{{(1-\alpha)\varepsilon}}{{2\alpha}},\infty),\;\;B=[0,\omega)\times(-\infty,\textstyle\frac{{(1-\alpha)\varepsilon}}{{2\alpha}}],\;\;C=[\omega,\infty)\times[\textstyle\frac{{(1-\alpha)\varepsilon}}{{2\alpha}},\infty),\;\;D=[\omega,\infty)\times(-\infty,\textstyle\frac{{(1-\alpha)\varepsilon}}{{2\alpha}}].$

We can then partition $\mathbb{E}\left[{\frac{1}{G_{1s}}-1}\right]$ into four
parts:

$\displaystyle\mathbb{E}\left[{\frac{1}{G_{1s}}-1}\right]$
$\displaystyle=c_{1}c_{2}\int_{0}^{\infty}{\int_{-\infty}^{\infty}{\frac{1-\widetilde{G}_{1s}}{\widetilde{G}_{1s}}\exp\left({-\frac{s{(\mu-\mu_{1})}^{2}}{2\sigma_{1}^{2}}}\right)\beta^{s-2}e^{-\frac{\beta^{2}}{2\sigma_{1}^{2}}}}\
\mathrm{d}{\mu}}\ \mathrm{d}{\beta}$
$\displaystyle=c_{1}c_{2}\left({\int_{A}+\int_{B}+\int_{C}+\int_{D}}\right)\frac{1-\widetilde{G}_{1s}}{\widetilde{G}_{1s}}\exp\left({-\frac{s{(\mu-\mu_{1})}^{2}}{2\sigma_{1}^{2}}}\right)\beta^{s-2}e^{-\frac{\beta^{2}}{2\sigma_{1}^{2}}}\mathrm{d}\mu\mathrm{d}\beta.$

For Part $B$, using the fourth case in Lemma 2,

$\frac{1-\widetilde{G}_{1s}}{\widetilde{G}_{1s}}\leq 4(1-\widetilde{G}_{1s}).$

It follows that

$\displaystyle
c_{1}c_{2}\int_{B}\frac{1-\widetilde{G}_{1s}}{\widetilde{G}_{1s}}\exp\left({-\frac{s{(\mu-\mu_{1})}^{2}}{2\sigma_{1}^{2}}}\right)\beta^{s-2}e^{-\frac{\beta^{2}}{2\sigma_{1}^{2}}}\,\mathrm{d}\mu\,\mathrm{d}\beta$
$\displaystyle\leq
4c_{1}c_{2}\int_{B}(1-\widetilde{G}_{1s})\exp\left({-\frac{s{(\mu-\mu_{1})}^{2}}{2\sigma_{1}^{2}}}\right)\beta^{s-2}e^{-\frac{\beta^{2}}{2\sigma_{1}^{2}}}\,\mathrm{d}\mu\,\mathrm{d}\beta$
$\displaystyle\leq
4c_{1}c_{2}\int_{B}\left({\mathbb{P}_{t}\left({\theta_{1,t}-\mu_{1}\geq\frac{(1-\alpha)\varepsilon}{2\alpha}\Big{|}\hat{\mu}_{1,s}=\mu}\right)+\mathbb{P}\left({\frac{1}{\sqrt{\kappa_{1,t}}}-\sigma_{1}\geq\frac{\varepsilon}{2c_{\alpha}^{*}}\Big{|}\hat{\sigma}_{1,s}=\beta}\right)}\right)$
$\displaystyle\phantom{--}\cdot\exp\left({-\frac{s{(\mu-\mu_{1})}^{2}}{2\sigma_{1}^{2}}}\right)\beta^{s-2}e^{-\frac{\beta^{2}}{2\sigma_{1}^{2}}}\,\mathrm{d}\mu\,\mathrm{d}\beta$
$\displaystyle\leq
4c_{1}\int_{-\infty}^{\mu_{1}+\frac{(1-\alpha)\varepsilon}{2\alpha}}\mathbb{P}_{t}\left({\theta_{1,t}-\mu_{1}\geq\frac{(1-\alpha)\varepsilon}{2\alpha}\Big{|}\hat{\mu}_{1,s}=\mu}\right)\exp\left({-\frac{s{(\mu-\mu_{1})}^{2}}{2\sigma_{1}^{2}}}\right)\
\mathrm{d}\mu$
$\displaystyle\phantom{--}+4c_{2}\int_{0}^{\omega}\mathbb{P}\left({\frac{1}{\sqrt{\kappa_{1,t}}}-\sigma_{1}\geq\frac{\varepsilon}{2c_{\alpha}^{*}}\Big{|}\hat{\sigma}_{1,s}=\beta}\right)\beta^{s-2}e^{-\frac{\beta^{2}}{2\sigma_{1}^{2}}}\
\mathrm{d}\beta$ $\displaystyle\leq
4c_{1}\int_{-\infty}^{\mu_{1}+\frac{(1-\alpha)\varepsilon}{2\alpha}}\exp\left({-\frac{s}{2}{\left({\mu_{1}-\mu+\frac{(1-\alpha)\varepsilon}{2\alpha}}\right)}^{2}}\right)\exp\left({-\frac{s{(\mu-\mu_{1})}^{2}}{2\sigma_{1}^{2}}}\right)\
\mathrm{d}\mu$
$\displaystyle\phantom{--}+4c_{2}\int_{0}^{\omega}\mathbb{P}\left({\kappa_{1,t}\leq\frac{1}{{\left({\frac{\varepsilon}{2c_{\alpha}^{*}}+\sigma_{1}}\right)}^{2}}\Big{|}\hat{\sigma}_{1,s}=\beta}\right)\beta^{s-2}e^{-\frac{\beta^{2}}{2\sigma_{1}^{2}}}\
\mathrm{d}\beta$ (17) $\displaystyle\leq
4c_{1}\int_{-\infty}^{\mu_{1}+\frac{(1-\alpha)\varepsilon}{2\alpha}}\exp\left({-\frac{s}{2}{\left({\mu_{1}-\mu+\frac{(1-\alpha)\varepsilon}{2\alpha}}\right)}^{2}}\right)\exp\left({-\frac{s{(\mu-\mu_{1})}^{2}}{2\sigma_{1}^{2}}}\right)\
\mathrm{d}\mu$
$\displaystyle\phantom{--}+4c_{2}\int_{0}^{\omega}\exp\left({-\frac{\left({\beta^{2}-s\left({\frac{\varepsilon}{2c_{\alpha}^{*}}+\sigma_{1}}\right)^{2}}\right)^{2}}{4s\left({\frac{\varepsilon}{2c_{\alpha}^{*}}+\sigma_{1}}\right)^{4}}}\right)\beta^{s-2}e^{-\frac{\beta^{2}}{2\sigma_{1}^{2}}}\
\mathrm{d}\beta$ (18) $\displaystyle\leq
4\exp\left({-\frac{s{(1-\alpha)}^{2}\varepsilon^{2}}{16\alpha^{2}}}\right)+4\exp\left({-\frac{s\varepsilon^{2}}{16{(c_{\alpha}^{*})}^{2}}}\right).$

where (17) and (18) respectively follow from applying standard tail upper
bounds on the Gaussian and Gamma distributions.

For Part $A$, using the third case in the above lemma,

$\frac{1-\widetilde{G}_{1s}}{\widetilde{G}_{1s}}\leq\frac{2}{\mathbb{P}_{t}\left({\theta_{1,t}-\mu_{1}\leq\frac{(1-\alpha)\varepsilon}{2\alpha}|\hat{\mu}_{1,s}=\mu}\right)}.$

Then

$\displaystyle
c_{1}c_{2}\int_{A}\frac{1-\widetilde{G}_{1s}}{\widetilde{G}_{1s}}\exp\left({-\frac{s{(\mu-\mu_{1})}^{2}}{2\sigma_{1}^{2}}}\right)\beta^{s-2}e^{-\frac{\beta^{2}}{2\sigma_{1}^{2}}}\,\mathrm{d}\mu\,\mathrm{d}\beta$
$\displaystyle\leq
2c_{1}c_{2}\int_{A}\frac{1}{\mathbb{P}_{t}\left({\theta_{1,t}-\mu_{1}\leq\frac{(1-\alpha)\varepsilon}{2\alpha}|\hat{\mu}_{1,s}=\mu}\right)}\exp\left({-\frac{s{(\mu-\mu_{1})}^{2}}{2\sigma_{1}^{2}}}\right)\beta^{s-2}e^{-\frac{\beta^{2}}{2\sigma_{1}^{2}}}\,\mathrm{d}\mu\,\mathrm{d}\beta$
$\displaystyle\leq
2c_{1}\int_{\mu_{1}+\frac{(1-\alpha)\varepsilon}{2\alpha}}^{\infty}\frac{1}{\mathbb{P}_{t}\left({\theta_{1,t}-\mu_{1}\leq\frac{(1-\alpha)\varepsilon}{2\alpha}|\hat{\mu}_{1,s}=\mu}\right)}\exp\left({-\frac{s{(\mu-\mu_{1})}^{2}}{2\sigma_{1}^{2}}}\right)\mathrm{d}\mu\cdot
c_{2}\int_{0}^{\omega}\beta^{s-2}e^{-\frac{\beta^{2}}{2\sigma_{1}^{2}}}\,\mathrm{d}\beta$
$\displaystyle\leq\frac{2c_{1}\sqrt{2}}{\sqrt{\pi}}\int_{\mu_{1}+\frac{(1-\alpha)\varepsilon}{2\alpha}}^{\infty}\left({\sqrt{s}\left({\mu-\mu_{1}-\frac{(1-\alpha)\varepsilon}{2\alpha}}\right)+\sqrt{s{\left({\mu-\mu_{1}-\frac{(1-\alpha)\varepsilon}{2\alpha}}\right)}^{2}+4}}\right)$
$\displaystyle\phantom{--}\cdot\exp\left({\frac{s{\left({\mu-\mu_{1}-\frac{(1-\alpha)\varepsilon}{2\alpha}}\right)}^{2}}{2}}\right)\cdot\exp\left({-\frac{s{(\mu-\mu_{1})}^{2}}{2\sigma_{1}^{2}}}\right)\,\mathrm{d}\mu$
(19)
$\displaystyle\leq\frac{2c_{1}\sqrt{2}}{\sqrt{\pi}}\int_{0}^{\infty}\left({\sqrt{s}z+\sqrt{sz^{2}+4}}\right)\exp\left({\frac{sz^{2}}{2}}\right)\cdot\exp\left({-\frac{s\left({z+\frac{(1-\alpha)\varepsilon}{2\alpha}}\right)^{2}}{2}}\right)\,\mathrm{d}z$
$\displaystyle\leq\frac{2c_{1}\sqrt{2}}{\sqrt{\pi}}\exp\left({-\frac{s\left({\frac{(1-\alpha)\varepsilon}{2\alpha}}\right)^{2}}{2}}\right)\int_{0}^{\infty}3\left({\sqrt{s}z}\right)\cdot\exp\left({-sz\varepsilon}\right)\mathrm{d}z\leq\frac{6}{\pi\varepsilon^{2}s\sqrt{s}}\exp\left({-\frac{s{(1-\alpha)}^{2}\varepsilon^{2}}{8\alpha^{2}}}\right),$

where (19) follows from Lemma 4, which we state below.

######  Lemma 4 (Abramowitz & Stegun (1970)).

For $X\sim\mathcal{N}(\mu,1/s)$,

$\mathbb{P}(X\leq\mu-x)=\mathbb{P}(X\geq\mu+x)\geq\sqrt{\frac{2}{\pi}}\cdot\frac{\exp\left({-\frac{sx^{2}}{2}}\right)}{\sqrt{s}x+\sqrt{sx^{2}+4}}.$

For Part $D$, using the second case in Lemma 2,

$\frac{1-\widetilde{G}_{1s}}{\widetilde{G}_{1s}}\leq\frac{2}{\mathbb{P}_{t}\left({\frac{1}{\sqrt{\kappa_{1,t}}}-\sigma_{1}\leq\frac{\varepsilon}{2c_{\alpha}^{*}}\big{|}\hat{\sigma}_{1,s}=\beta}\right)}.$

Then

$\displaystyle
c_{1}c_{2}\int_{D}\frac{1-\widetilde{G}_{1s}}{\widetilde{G}_{1s}}\exp\left({-\frac{s{(\mu-\mu_{1})}^{2}}{2\sigma_{1}^{2}}}\right)\beta^{s-2}e^{-\frac{\beta^{2}}{2\sigma_{1}^{2}}}\,\mathrm{d}\mu\,\mathrm{d}\beta$
$\displaystyle\leq
2c_{1}c_{2}\int_{D}\frac{1}{\mathbb{P}_{t}\left({\frac{1}{\sqrt{\kappa_{1,t}}}-\sigma_{1}\leq\frac{\varepsilon}{2c_{\alpha}^{*}}\big{|}\hat{\sigma}_{1,s}=\beta}\right)}\exp\left({-\frac{s{(\mu-\mu_{1})}^{2}}{2\sigma_{1}^{2}}}\right)\beta^{s-2}e^{-\frac{\beta^{2}}{2\sigma_{1}^{2}}}\,\mathrm{d}\mu\,\mathrm{d}\beta$
$\displaystyle\leq
c_{1}\int_{-\infty}^{\mu_{1}}\exp\left({-\frac{s{(\mu-\mu_{1})}^{2}}{2\sigma_{1}^{2}}}\right)\mathrm{d}\mu\cdot
2c_{2}\int_{\omega}^{\infty}\frac{1}{\mathbb{P}_{t}\left({\frac{1}{\sqrt{\kappa_{1,t}}}-\sigma_{1}\leq\frac{\varepsilon}{2c_{\alpha}^{*}}\big{|}\hat{\sigma}_{1,s}=\beta}\right)}\beta^{s-2}e^{-\frac{\beta^{2}}{2\sigma_{1}^{2}}}\,\mathrm{d}\beta$
$\displaystyle\leq
2c_{2}\int_{\omega}^{\infty}\frac{1}{\mathbb{P}_{t}\left({\frac{1}{\sqrt{\kappa_{1,t}}}-\sigma_{1}\leq\frac{\varepsilon}{2c_{\alpha}^{*}}\big{|}\hat{\sigma}_{1,s}=\beta}\right)}\beta^{s-2}e^{-\frac{\beta^{2}}{2\sigma_{1}^{2}}}\,\mathrm{d}\beta$
$\displaystyle\leq
2c_{2}\Gamma\left({\frac{s}{2}}\right)\int_{\omega}^{\infty}\exp\left({\frac{\beta^{2}}{{(\frac{\varepsilon}{2c_{\alpha}^{*}}+\sigma_{1})}^{2}}-\frac{\beta^{2}}{2\sigma_{1}^{2}}}\right)\beta^{s-2}\left({1+\frac{\beta^{2}}{{(\frac{\varepsilon}{2c_{\alpha}^{*}}+\sigma_{1})}^{2}}}\right)^{-\left({\frac{s}{2}-1}\right)}\,\mathrm{d}\beta$
(20) $\displaystyle\leq
2c_{2}\Gamma\left({\frac{s}{2}}\right)\cdot\left({\frac{\varepsilon}{2c_{\alpha}^{*}}+\sigma_{1}}\right)^{s-1}\int_{\frac{\sqrt{2}\sigma_{1}s}{\frac{\varepsilon}{2c_{\alpha}^{*}}+\sigma_{1}}}^{\infty}\exp\left({y^{2}-\frac{y^{2}\left({\frac{\varepsilon}{2c_{\alpha}^{*}}+\sigma_{1}}\right)^{2}}{2\sigma_{1}^{2}}}\right)y^{s-2}\left({1+y^{2}}\right)^{-\left({\frac{s}{2}-1}\right)}\,\mathrm{d}y$
$\displaystyle\leq
2c_{2}\Gamma\left({\frac{s}{2}}\right)\cdot\left({\frac{\varepsilon}{2c_{\alpha}^{*}}+\sigma_{1}}\right)^{s-1}\int_{s}^{\infty}y\exp\left({-\frac{2\sigma_{1}^{2}-\left({\frac{\varepsilon}{2c_{\alpha}^{*}}+\sigma_{1}}\right)^{2}}{\sigma_{1}^{2}}y^{2}}\right)\,\mathrm{d}y$
$\displaystyle\leq\frac{\sigma_{1}^{2}c_{2}\Gamma\left({\frac{s}{2}}\right)\cdot\left({\frac{\varepsilon}{2c_{\alpha}^{*}}+\sigma_{1}}\right)^{s-1}}{2\sigma_{1}^{2}-\left({\frac{\varepsilon}{2c_{\alpha}^{*}}+\sigma_{1}}\right)^{2}}\exp\left({-\frac{2\sigma_{1}^{2}-\left({\frac{\varepsilon}{2c_{\alpha}^{*}}+\sigma_{1}}\right)^{2}}{\sigma_{1}^{2}}s^{2}}\right).$

where (20) follows from Lemma 5, which we state below.

######  Lemma 5 (Zhu & Tan (2020, Lemma S-1)).

If $X\sim\mathrm{Gamma}(\alpha,\beta)$ with $\alpha\geq 1$ and rate $\beta>0$,
we have the lower bound on the complementary CDF

$\mathbb{P}(X\geq x)\geq\frac{1}{\Gamma(\alpha)}\exp(-\beta x){(1+\beta
x)}^{\alpha-1}.$

For Part $C$, using the first case in Lemma 2,

$\frac{1-\widetilde{G}_{1s}}{\widetilde{G}_{1s}}\leq\frac{1}{\mathbb{P}_{t}\left({{\theta}_{1,t}-\mu_{1}\leq\varepsilon|\hat{\mu}_{1,s}=\mu}\right)\cdot\mathbb{P}_{t}\left({\frac{1}{\sqrt{\kappa_{1,t}}}-\sigma_{1}\leq\varepsilon|\hat{\sigma}_{1,s}=\beta}\right)}.$

Reusing the integrations in Parts $A$ and $D$,

$\displaystyle
c_{1}c_{2}\int_{D}\frac{1-\widetilde{G}_{1s}}{\widetilde{G}_{1s}}\exp\left({-\frac{s{(\mu-\mu_{1})}^{2}}{2\sigma_{1}^{2}}}\right)\beta^{s-2}e^{-\frac{\beta^{2}}{2\sigma_{1}^{2}}}\,\mathrm{d}\mu\,\mathrm{d}\beta$
$\displaystyle\leq
c_{1}c_{2}\int_{D}\frac{1}{\mathbb{P}_{t}\left({{\theta}_{1,t}-\mu_{1}\leq\frac{(1-\alpha)\varepsilon}{2\alpha}\big{|}\hat{\mu}_{1,s}=\mu}\right)\cdot\mathbb{P}_{t}\left({\frac{1}{\sqrt{\kappa_{1,t}}}-\sigma_{1}\leq\frac{\varepsilon}{2c_{\alpha}^{*}}\big{|}\hat{\sigma}_{1,s}=\beta}\right)}$
$\displaystyle\phantom{---}\cdot\exp\left({-\frac{s{(\mu-\mu_{1})}^{2}}{2\sigma_{1}^{2}}}\right)\beta^{s-2}e^{-\frac{\beta^{2}}{2\sigma_{1}^{2}}}\,\mathrm{d}\mu\,\mathrm{d}\beta$
$\displaystyle\leq\frac{1}{4}\cdot
2c_{1}\int_{\mu_{1}+\frac{(1-\alpha)\varepsilon}{2\alpha}}^{\infty}\frac{1}{\mathbb{P}_{t}(\theta_{1,t}-\mu_{1}\leq\frac{(1-\alpha)\varepsilon}{2\alpha}\big{|}\hat{\mu}_{1,s}=\mu)}\exp\left({-\frac{s{(\mu-\mu_{1})}^{2}}{2\sigma_{1}^{2}}}\right)\,\mathrm{d}\mu$
$\displaystyle\phantom{---}\cdot
2c_{2}\int_{\omega}^{\infty}\frac{1}{\mathbb{P}_{t}(\frac{1}{\sqrt{\kappa_{1,t}}}-\sigma_{1}\leq\frac{\varepsilon}{2c_{\alpha}^{*}}\big{|}\hat{\sigma}_{1,s}=\beta)}\beta^{s-2}e^{-\frac{\beta^{2}}{2\sigma_{1}^{2}}}\,\mathrm{d}\beta$
$\displaystyle\leq\frac{3}{\pi\varepsilon^{2}s\sqrt{s}}\exp\left({-\frac{s{(1-\alpha)}^{2}\varepsilon^{2}}{8\alpha^{2}}}\right)\cdot\frac{\sigma_{1}^{2}c_{2}\Gamma\left({\frac{s}{2}}\right)\cdot\left({\frac{\varepsilon}{2c_{\alpha}^{*}}+\sigma_{1}}\right)^{s-1}}{2\sigma_{1}^{2}-\left({\frac{\varepsilon}{2c_{\alpha}^{*}}+\sigma_{1}}\right)^{2}}\exp\left({-\frac{2\sigma_{1}^{2}-\left({\frac{\varepsilon}{2c_{\alpha}^{*}}+\sigma_{1}}\right)^{2}}{\sigma_{1}^{2}}s^{2}}\right).$

Combining these four parts, we can upper bound
$\mathbb{E}\left[{\frac{1}{G_{1s}}-1}\right]$ by

$\displaystyle\mathbb{E}\left[{\frac{1}{G_{1s}}-1}\right]$
$\displaystyle=4\exp\left({-\frac{s{(1-\alpha)}^{2}\varepsilon^{2}}{16\alpha^{2}}}\right)+4\exp\left({-\frac{s\varepsilon^{2}}{16{(c_{\alpha}^{*})}^{2}}}\right)+\frac{6}{\pi\varepsilon^{2}s\sqrt{s}}\exp\left({-\frac{s{(1-\alpha)}^{2}\varepsilon^{2}}{8\alpha^{2}}}\right)$
$\displaystyle\phantom{---}+\frac{2\sigma_{1}\left({\frac{\varepsilon}{2c_{\alpha}^{*}}+\sigma_{1}}\right)^{s-1}}{\frac{\varepsilon}{2c_{\alpha}^{*}}}\exp\left({-\frac{\frac{\varepsilon}{2c_{\alpha}^{*}}(\frac{\varepsilon}{2c_{\alpha}^{*}}+2\sigma_{1})}{\sigma_{1}^{2}}s^{2}}\right)$
$\displaystyle\phantom{---}+\frac{3}{\pi\varepsilon^{2}s\sqrt{s}}\exp\left({-\frac{s{(1-\alpha)}^{2}\varepsilon^{2}}{8\alpha^{2}}}\right)\cdot\frac{\sigma_{1}^{2}c_{2}\Gamma\left({\frac{s}{2}}\right)\cdot\left({\frac{\varepsilon}{2c_{\alpha}^{*}}+\sigma_{1}}\right)^{s-1}}{2\sigma_{1}^{2}-\left({\frac{\varepsilon}{2c_{\alpha}^{*}}+\sigma_{1}}\right)^{2}}\exp\left({-\frac{2\sigma_{1}^{2}-\left({\frac{\varepsilon}{2c_{\alpha}^{*}}+\sigma_{1}}\right)^{2}}{\sigma_{1}^{2}}s^{2}}\right).$

Summing over $s$, we have

$\displaystyle\sum_{s=1}^{n}\mathbb{E}\left[{\frac{1}{G_{1s}}-1}\right]\leq\frac{C_{1}}{\varepsilon^{3}}+\frac{C_{2}}{\varepsilon^{2}}+\frac{C_{3}}{\varepsilon}+C_{4}.$

∎

######  Lemma 6.

For $\xi\in(0,1)$, we have

$\displaystyle\mathbb{P}_{t}\left({\hat{c}_{\alpha}(i,t)\leq
c_{\alpha}(1)+\varepsilon\mid
T_{i,s}=s,\hat{\mu}_{i,s}=\mu,\hat{\sigma}_{i,s}=\sigma}\right)$
$\displaystyle\leq\exp\left({-\frac{s}{2}\left({\mu-\mu_{i}+\frac{\xi(\Delta_{\mathrm{r}}(i,\alpha)-\varepsilon)(1-\alpha)}{\alpha}}\right)^{2}}\right)+\exp\left({-sh\left({\frac{\sigma^{2}{(c_{\alpha}^{*})}^{2}}{\left({\sigma_{i}c_{\alpha}^{*}-(1-\xi)\left({\Delta_{\mathrm{r}}(i,\alpha)-\varepsilon}\right)}\right)^{2}}}\right)}\right),$

where $h(x)=\frac{1}{2}(x-1-\log x)$.

###### Proof of Lemma 6.

Given $T_{i,t}=s,\hat{\mu}_{i,s}=\mu,\hat{\sigma}_{i,s}=\sigma$, a direct
calculation gives us,

$\displaystyle\mathbb{P}_{t}\left({\hat{c}_{\alpha}(i,t)\leq
c_{\alpha}(1)+\varepsilon\mid
T_{i,t}=s,\hat{\mu}_{i,s}=\mu,\hat{\sigma}_{i,s}=\sigma}\right)$
$\displaystyle=\mathbb{P}_{t}\left({{\theta}_{i,t}\left({\frac{\alpha}{1-\alpha}}\right)+\frac{1}{\sqrt{\kappa_{i,t}}}c_{\alpha}^{*}\leq
c_{\alpha}(1)+\varepsilon}\right)$
$\displaystyle=\mathbb{P}_{t}\left({({\theta}_{i,t}-\mu_{i})\left({\frac{\alpha}{1-\alpha}}\right)+\left({\frac{1}{\sqrt{\kappa_{i,t}}}-\sigma_{i}}\right)c_{\alpha}^{*}\leq-\Delta_{\mathrm{r}}(i,\alpha)+\varepsilon}\right)$
$\displaystyle=\mathbb{P}_{t}\left({({\theta}_{i,t}-\mu_{i})\left({\frac{\alpha}{1-\alpha}}\right)+\left({\frac{1}{\sqrt{\kappa_{i,t}}}-\sigma_{i}}\right)c_{\alpha}^{*}\leq\left({-\xi+(-1+\xi)}\right)\left({\Delta_{\mathrm{r}}(i,\alpha)-\varepsilon}\right)}\right)$
$\displaystyle\leq\mathbb{P}_{t}\left({{\theta}_{i,t}-\mu\leq-\left({\mu-\mu_{i}+\frac{\xi(\Delta_{\mathrm{r}}(i,\alpha)-\varepsilon)(1-\alpha)}{\alpha}}\right)}\right)+\mathbb{P}_{t}\left({\frac{1}{\sqrt{\kappa_{i,t}}}-\sigma_{i}\leq-\frac{(1-\xi)\left({\Delta_{\mathrm{r}}(i,\alpha)-\varepsilon}\right)}{c_{\alpha}^{*}}}\right)$
$\displaystyle\leq\exp\left({-\frac{s}{2}\left({\mu-\mu_{i}+\frac{\xi(\Delta_{\mathrm{r}}(i,\alpha)-\varepsilon)(1-\alpha)}{\alpha}}\right)^{2}}\right)+\mathbb{P}_{t}\left({\kappa_{i,t}\geq\frac{{(c_{\alpha}^{*})}^{2}}{\left({\sigma_{i}c_{\alpha}^{*}-(1-\xi)\left({\Delta_{\mathrm{r}}(i,\alpha)-\varepsilon}\right)}\right)^{2}}}\right)$
$\displaystyle\leq\exp\left({-\frac{s}{2}\left({\mu-\mu_{i}+\frac{\xi(\Delta_{\mathrm{r}}(i,\alpha)-\varepsilon)(1-\alpha)}{\alpha}}\right)^{2}}\right)+\exp\left({-sh\left({\frac{\sigma^{2}{(c_{\alpha}^{*})}^{2}}{\left({\sigma_{i}c_{\alpha}^{*}-(1-\xi)\left({\Delta_{\mathrm{r}}(i,\alpha)-\varepsilon}\right)}\right)^{2}}}\right)}\right),$
(21)

where (21) follows from Lemma 7, which we state below.

######  Lemma 7 (Harremoës (2016)).

For a Gamma r.v. $X\sim\mathrm{Gamma}(\alpha,\beta)$ with shape $\alpha\geq 2$
and rate $\beta>0$, we have

$\mathbb{P}(X\geq x)\leq\exp\left({-2\alpha h\left({\frac{\beta
x}{\alpha}}\right)}\right),\ x>\frac{\alpha}{\beta},$

where $h(x)=\frac{1}{2}(x-1-\log x)$.

∎

######  Lemma 8 (Upper bounding the second term of (14)).

We have

$\displaystyle\sum_{s=1}^{n}\mathbb{P}_{t}\left({G_{is}>\frac{1}{n}}\right)$
$\displaystyle\leq
1+\max\left\\{{\frac{2\alpha^{2}\log(2n)}{\xi^{2}{(1-\alpha)}^{2}\left({\Delta_{\mathrm{r}}(i,\alpha)-\varepsilon}\right)^{2}},\frac{\log(2n)}{h\left({\frac{\sigma_{i}^{2}{(c_{\alpha}^{*})}^{2}}{\left({\sigma_{i}c_{\alpha}^{*}-(1-\xi)\left({\Delta_{\mathrm{r}}(i,\alpha)-\varepsilon}\right)}\right)^{2}}}\right)}}\right\\}+\frac{C_{5}}{\varepsilon^{4}}+\frac{C_{6}}{\varepsilon^{2}},$
(22)

where $C_{5},C_{6}$ are constants.

###### Proof of Lemma 8.

From Lemma 6 we have the inclusions

$\displaystyle\left\\{{\hat{\mu}_{i,s}-\sqrt{\frac{2\log(2n)}{s}}\geq\mu_{i}-\frac{\xi(\Delta_{\mathrm{r}}(i,\alpha)-\varepsilon)(1-\alpha)}{\alpha}}\right\\}$
$\displaystyle\subseteq\left\\{{\exp\left({-\frac{s}{2}\left({\mu-\mu_{i}-\frac{\xi(\Delta_{\mathrm{r}}(i,\alpha)-\varepsilon)(1-\alpha)}{\alpha}}\right)^{2}}\right)\leq\frac{1}{2n}}\right\\}$

and

$\displaystyle\left\\{{\frac{\hat{\sigma}_{i,s}^{2}{(c_{\alpha}^{*})}^{2}}{\left({\sigma_{i}c_{\alpha}^{*}-(1-\xi)\left({\Delta_{\mathrm{r}}(i,\alpha)-\varepsilon}\right)}\right)^{2}}\geq
h_{+}^{-1}\left({\frac{\log(2n)}{s}}\right)}\right\\}$
$\displaystyle\cup\left\\{{\frac{\hat{\sigma}_{i,s}^{2}{(c_{\alpha}^{*})}^{2}}{\left({\sigma_{i}c_{\alpha}^{*}-(1-\xi)\left({\Delta_{\mathrm{r}}(i,\alpha)-\varepsilon}\right)}\right)^{2}}\leq
h_{-}^{-1}\left({\frac{\log(2n)}{s}}\right)}\right\\}$
$\displaystyle\subseteq\left\\{{\exp\left({-sh\left({\frac{\sigma^{2}{(c_{\alpha}^{*})}^{2}}{\left({\sigma_{i}c_{\alpha}^{*}-(1-\xi)\left({\Delta_{\mathrm{r}}(i,\alpha)-\varepsilon}\right)}\right)^{2}}}\right)}\right)\leq\frac{1}{2n}}\right\\}$

where $h_{+}^{-1}(y)=\max\left\\{{x:h(x)=y}\right\\}$ and
$h_{-}^{-1}(y)=\min\left\\{{x:h(x)=y}\right\\}$. Hence, for

$s\geq
u=\max\left\\{{\frac{2\alpha^{2}\log(2n)}{\xi^{2}{(1-\alpha)}^{2}{(\Delta_{\mathrm{r}}(i,\alpha)-\varepsilon)}^{2}},\frac{\log(2n)}{h\left({\frac{\sigma_{i}^{2}{(c_{\alpha}^{*})}^{2}}{\left({\sigma_{i}c_{\alpha}^{*}-(1-\xi)\left({\Delta_{\mathrm{r}}(i,\alpha)-\varepsilon}\right)}\right)^{2}}}\right)}}\right\\},$

we have

$\displaystyle\mathbb{P}_{t}\left({G_{is}>\frac{1}{n}}\right)$
$\displaystyle\leq\mathbb{P}_{t}\left({\hat{\mu}_{i,s}-\sqrt{\frac{2\log(2n)}{s}}\leq\mu_{i}-\frac{\xi(\Delta_{\mathrm{r}}(i,\alpha)-\varepsilon)(1-\alpha)}{\alpha}}\right)$
$\displaystyle\phantom{--}+\mathbb{P}_{t}\left({h_{-}^{-1}\left({\frac{\log(2n)}{s}}\right)\leq\frac{\hat{\sigma}_{i,s}^{2}{(c_{\alpha}^{*})}^{2}}{\left({\sigma_{i}c_{\alpha}^{*}-(1-\xi)\left({\Delta_{\mathrm{r}}(i,\alpha)-\varepsilon}\right)}\right)^{2}}\leq
h_{+}^{-1}\left({\frac{\log(2n)}{s}}\right)}\right)$
$\displaystyle\leq\mathbb{P}_{t}\left({\hat{\mu}_{i,s}-\mu_{i}\leq\sqrt{\frac{2\log(2n)}{s}}-\frac{\xi(\Delta_{\mathrm{r}}(i,\alpha)-\varepsilon)(1-\alpha)}{\alpha}}\right)$
$\displaystyle\phantom{--}+\mathbb{P}_{t}\left({\hat{\sigma}_{i,s}^{2}\leq\frac{\left({\sigma_{i}c_{\alpha}^{*}-(1-\xi)\left({\Delta_{\mathrm{r}}(i,\alpha)-\varepsilon}\right)}\right)^{2}}{{(c_{\alpha}^{*})}^{2}}h_{+}^{-1}\left({\frac{\log(2n)}{s}}\right)}\right)$
$\displaystyle\leq\exp\left({-\frac{s\left({\frac{\xi(\Delta_{\mathrm{r}}(i,\alpha)-\varepsilon)(1-\alpha)}{\alpha}-\sqrt{\frac{2\log(2n)}{s}}}\right)^{2}}{2\sigma_{i}^{2}}}\right)$
$\displaystyle\phantom{--}+\exp\left({-(s-1)\frac{\left({\sigma_{i}^{2}-\frac{\left({\sigma_{i}c_{\alpha}^{*}-(1-\xi)\left({\Delta_{\mathrm{r}}(i,\alpha)-\varepsilon}\right)}\right)^{2}}{{(c_{\alpha}^{*})}^{2}}h_{+}^{-1}\left({\frac{\log(2n)}{s}}\right)}\right)^{2}}{4\sigma_{i}^{4}}}\right)$
(23)
$\displaystyle\leq\exp\left({-\frac{s\varepsilon^{2}}{\sigma_{i}^{2}}}\right)+\exp\left({-(s-1)\frac{\varepsilon^{4}}{\sigma_{i}^{2}}}\right),$

where (23) follows from Lemma 9, which we state below. Summing over $s$,

$\displaystyle\sum_{s=1}^{n}\mathbb{P}_{t}\left({G_{is}>\frac{1}{n}}\right)$
$\displaystyle\leq u+\sum_{s=\lceil
u\rceil}^{n}\left[{\exp\left({-\frac{s\varepsilon^{2}}{\sigma_{i}^{2}}}\right)+\exp\left({-(s-1)\frac{\varepsilon^{4}}{\sigma_{1}^{2}}}\right)}\right]$
$\displaystyle\leq
1+\max\left\\{{\frac{2\alpha^{2}\log(2n)}{\xi^{2}{(1-\alpha)}^{2}\left({\Delta_{\mathrm{r}}(i,\alpha)-\varepsilon}\right)^{2}},\frac{\log(2n)}{h\left({\frac{\sigma_{i}^{2}{(c_{\alpha}^{*})}^{2}}{\left({\sigma_{i}c^{*}-(1-\xi)\left({\Delta_{\mathrm{r}}(i,\alpha)-\varepsilon}\right)}\right)^{2}}}\right)}}\right\\}+\frac{C_{5}}{\varepsilon^{4}}+\frac{C_{6}}{\varepsilon^{2}}.$

######  Lemma 9 (Laurent & Massart (2000)).

For any $X\sim\chi_{s-1}^{2}$, $\displaystyle\mathbb{P}(X\leq
x)\leq\exp\left({-\frac{{(s-1-x)}^{2}}{4(s-1)}}\right).$

Setting

$\xi_{\alpha}=1-\frac{\sigma_{i}c_{\alpha}^{*}}{\Delta_{\mathrm{r}}(i,\alpha)}\left({1-\frac{1}{\sqrt{h_{+}^{-1}(1/A_{\alpha,1}^{i})}}}\right),$

we observe that
$\omega_{i,\alpha}:=\sigma_{i}\left({1-\frac{1}{\sqrt{h_{+}^{-1}(1/A_{\alpha,1}^{i})}}}\right)\to\sigma_{i}\left({1-\frac{1}{\sqrt{h_{+}^{-1}({(\mu_{i}-\mu_{1})}^{2}/2)}}}\right)=:\Omega_{i}$
since $A_{\alpha,1}\to\frac{2}{{(\mu_{i}-\mu_{1})}^{2}}$, and hence,

$\xi_{\alpha}=1-\frac{\omega_{i,\alpha}c_{\alpha}^{*}}{\Delta_{\mathrm{r}}(i,\alpha)}=1-\frac{\omega_{i,\alpha}c_{\alpha}^{*}(1-\alpha)}{(\mu_{i}-\mu_{1})\alpha+\sigma_{i}c_{\alpha}^{*}(1-\alpha)}\to
1-\frac{\Omega_{i}\cdot 0}{\mu_{i}-\mu_{1}}=1$

as $\alpha\to 1^{-}$. Furthermore, we have

$\displaystyle B_{\alpha,\xi_{\alpha}}^{i}$
$\displaystyle=\frac{1}{h\left({\frac{\sigma_{i}^{2}{(c_{\alpha}^{*})}^{2}}{{\left({\sigma_{i}c_{\alpha}^{*}-(1-\xi_{\alpha})\Delta_{\mathrm{r}}(i,\alpha)}\right)}^{2}}}\right)}=\frac{1}{h\left({\frac{\sigma_{i}^{2}{(c_{\alpha}^{*})}^{2}}{{\left({\sigma_{i}c_{\alpha}^{*}-\omega
c_{\alpha}^{*}}\right)}^{2}}}\right)}=\frac{1}{h\left({\frac{\sigma_{i}^{2}}{{\left({\sigma_{i}-\omega}\right)}^{2}}}\right)}$
$\displaystyle=\frac{1}{h\left({\frac{\sigma_{i}^{2}}{\sigma_{i}^{2}/h_{+}^{-1}(1/A_{\alpha,1}^{i})}}\right)}=\frac{1}{h\left({h_{+}^{-1}(1/A_{\alpha,1}^{i})}\right)}=\frac{1}{1/A_{\alpha,1}^{i}}=A_{\alpha,1}^{i}\leq
A_{\alpha,\xi_{\alpha}}^{i}.$

∎

##  Appendix B Proof of Theorem 2

The proof of Theorem 2 is similar to that of Theorem 1.

###### Proof of Theorem 2.

Fix $\varepsilon>0$, and define

$E_{i}(t):=\left\\{{\hat{c}_{\alpha}(i,t)>\tau+\varepsilon}\right\\},$

By Lemma 1, and the linearity of expectation, we can split
$\mathbb{E}[T_{i,n}]$ into two parts as follows

$\mathbb{E}[T_{i,n}]\leq\sum_{s=0}^{n-1}\mathbb{E}\left[{\frac{1}{G_{1s}}-1}\right]+\sum_{s=0}^{n-1}\mathbb{P}\left({G_{is}>\frac{1}{n}}\right)+1.$
(24)

By Lemmas 10 and 11, we have

$\displaystyle\sum_{s=1}^{n}\mathbb{E}\left[{\frac{1}{G_{1s}}-1}\right]$
$\displaystyle\leq\frac{C_{7}}{\varepsilon^{2}}+C_{8},\ \text{and}$
$\displaystyle\sum_{s=1}^{n}\mathbb{P}_{t}\left({G_{is}>\frac{1}{n}}\right)$
$\displaystyle\leq
1+\max\left\\{{\frac{2\alpha^{2}\log(2n)}{\xi^{2}{(1-\alpha)}^{2}\left({{\Delta_{\tau}(i,\alpha)-\varepsilon}}\right)^{2}},\frac{\log(2n)}{h\left({\frac{\sigma_{i}^{2}{(c_{\alpha}^{*})}^{2}}{{\left({\sigma_{i}c_{\alpha}^{*}-(1-\xi)(\Delta_{\tau}(i,\alpha)-\varepsilon)}\right)}^{2}}}\right)}}\right\\}+\frac{C_{9}}{\varepsilon^{4}}+\frac{C_{10}}{\varepsilon^{2}}.$

Plugging the two displays into (24), we have

$\mathbb{E}[T_{i,n}]\leq
1+\max\left\\{{\frac{2\alpha^{2}\log(2n)}{\xi^{2}{(1-\alpha)}^{2}\left({{\Delta_{\tau}(i,\alpha)-\varepsilon}}\right)^{2}},\frac{\log(2n)}{h\left({\frac{\sigma_{i}^{2}{(c_{\alpha}^{*})}^{2}}{{\left({\sigma_{i}c_{\alpha}^{*}-(1-\xi)(\Delta_{\tau}(i,\alpha)-\varepsilon)}\right)}^{2}}}\right)}}\right\\}+\frac{C_{6}^{\prime}}{\varepsilon^{4}}+\frac{C_{7}^{\prime}}{\varepsilon^{2}}+C_{8}^{\prime},$
(25)

where $C_{6}^{\prime},C_{7}^{\prime},C_{8}^{\prime}$ are constants. Setting
$\varepsilon={(\log n)}^{-\frac{1}{8}}$ into (25), we get

$\displaystyle\limsup_{n\to\infty}\frac{\mathcal{R}_{n}^{\mathsf{inf}}(\text{CVaR-
TS})}{\log n}$
$\displaystyle\leq\sum_{i\in\mathcal{K}_{\tau}^{c}}\left({\max\left\\{{\frac{2\alpha^{2}}{\xi^{2}{(1-\alpha)}^{2}\Delta_{\tau}^{2}(i)},\frac{1}{h\left({\frac{\sigma_{i}^{2}{(c_{\alpha}^{*})}^{2}}{{\left({\sigma_{i}c_{\alpha}^{*}-(1-\xi)(\Delta_{\tau}(i,\alpha))}\right)}^{2}}}\right)}}\right\\}}\right)\Delta_{\tau}(i,\alpha)$
$\displaystyle=\sum_{i\in\mathcal{K}_{\tau}^{c}}\max\left\\{{D_{\alpha,\xi}^{i},E_{\alpha,\xi}^{i}}\right\\}\Delta_{\tau}(i,\alpha)=\sum_{i\in{[K]}\backslash{\mathcal{K}^{*}}}F_{\alpha,\xi}^{i}\Delta_{\tau}(i,\alpha).$

∎

######  Lemma 10 (Upper bounding the first term of (24)).

We have

$\sum_{s=1}^{n}\mathbb{E}\left[{\frac{1}{G_{1s}}-1}\right]\leq\frac{C_{7}}{\varepsilon^{2}}+C_{8},$

where $C_{7},C_{8}$ are constants.

###### Proof of Lemma 10.

We note that $i$ is either a deceiver arm or a non-deceiver arm.

  1. ()

Suppose $i$ is a deceiver arm. Then

$E_{i}(t)=\left\\{{\hat{c}_{\alpha}(i,t)>\tau+\varepsilon}\right\\}\cap\left\\{{\hat{\mu}_{i,t}\leq\mu_{1}-\varepsilon}\right\\}\Rightarrow
E_{i}^{c}(t)\supseteq\left\\{{\hat{\mu}_{i,t}>\mu_{1}-\varepsilon}\right\\}.$

This allows us to establish lower bound

$\mathbb{P}_{t}(E_{1}^{c}(t)|T_{1,t}=s,\hat{\mu}_{1,s}=\mu,\hat{\sigma}_{1,s}=\sigma)\geq\begin{cases}\frac{1}{2}&\text{if
$\mu\geq\mu_{1}$}\\\ \mathbb{P}_{t}(\theta_{1,t}>\mu_{1}-\varepsilon)&\text{if
$\mu<\mu_{1}$.}\end{cases}$ (26)

Define the conditional version of $G_{1s}$ by

$\widetilde{G}_{1s}=G_{1s}|_{\hat{\mu}_{1,s},\hat{\sigma}_{1,s}=\beta}=\mathbb{P}_{t}(\hat{\mu}_{1,t}>\mu_{1}-\varepsilon\
\text{or}\
\hat{c}_{\alpha}(1,t)\leq\tau+\varepsilon\mid\hat{\mu}_{1,s},\hat{\sigma}_{1,s}=\beta).$

Define $c_{1}=\frac{1}{\sqrt{2\pi\sigma_{1}^{2}}}$ and
$c_{2}=\frac{1}{2^{\frac{s}{2}}\Gamma(s/2)\sigma_{1}^{s}}$. We partition the
parameter space

$(\beta,\mu)\in[0,\infty)\times(-\infty,\infty)=A^{\prime}\cup B^{\prime}$

where $A^{\prime}=[0,\infty)\times[\mu_{1},\infty)$ and
$B^{\prime}=[0,\infty)\times(-\infty,\mu_{1}]$. We can then partition
$\mathbb{E}\left[{\frac{1}{G_{1s}}-1}\right]$ into two parts:

$\displaystyle\mathbb{E}\left[{\frac{1}{G_{1s}}-1}\right]$
$\displaystyle=c_{1}c_{2}\int_{0}^{\infty}{\int_{-\infty}^{\infty}{\frac{1-\widetilde{G}_{1s}}{\widetilde{G}_{1s}}\exp\left({-\frac{{(\mu-\mu_{1})}^{2}}{2\sigma_{1}^{2}}}\right)\beta^{s-1}e^{-\frac{\beta^{2}}{2\sigma^{2}}}}\
\mathrm{d}{\mu}}\ \mathrm{d}{\beta}$
$\displaystyle=c_{1}c_{2}\left({\int_{A^{\prime}}+\int_{B^{\prime}}}\right)\frac{1-\widetilde{G}_{1s}}{\widetilde{G}_{1s}}\exp\left({-\frac{{(\mu-\mu_{1})}^{2}}{2\sigma_{1}^{2}}}\right)\beta^{s-1}e^{-\frac{\beta^{2}}{2\sigma^{2}}}\
\mathrm{d}\mu\ \mathrm{d}\beta.$

For Part $A^{\prime}$, using the first case in (26),

$\frac{1-\widetilde{G}_{1s}}{\widetilde{G}_{1s}}\leq 2(1-\widetilde{G}_{1s}).$

Thus,

$\displaystyle
c_{1}c_{2}\int_{A^{\prime}}\frac{1-\widetilde{G}_{1s}}{\widetilde{G}_{1s}}\exp\left({-\frac{s{(\mu-\mu_{1})}^{2}}{2\sigma_{1}^{2}}}\right)\beta^{s-1}e^{-\frac{\beta^{2}}{2\sigma^{2}}}\mathrm{d}\mu\mathrm{d}\beta$
$\displaystyle\leq
2c_{1}c_{2}\int_{A^{\prime}}(1-\widetilde{G}_{1s})\exp\left({-\frac{s{(\mu-\mu_{1})}^{2}}{2\sigma_{1}^{2}}}\right)\beta^{s-1}e^{-\frac{\beta^{2}}{2\sigma^{2}}}\mathrm{d}\mu\mathrm{d}\beta$
$\displaystyle\leq
2c_{1}c_{2}\int_{A^{\prime}}\mathbb{P}_{t}\left({\theta_{1,t}\leq\mu_{1}-\varepsilon}\right)\mathbb{P}_{t}\left({\hat{c}_{\alpha}(1,t)>\tau+\varepsilon}\right)\exp\left({-\frac{s{(\mu-\mu_{1})}^{2}}{2\sigma_{1}^{2}}}\right)\beta^{s-1}e^{-\frac{\beta^{2}}{2\sigma^{2}}}\mathrm{d}\mu\mathrm{d}\beta$
$\displaystyle\leq
2c_{1}\int_{\mu_{1}}^{\infty}{\exp\left({-\frac{s}{2}{(\mu-\mu_{1}+\varepsilon)}^{2}}\right)\exp\left({-\frac{s{(\mu-\mu_{1})}^{2}}{2\sigma_{1}^{2}}}\right)}\
\mathrm{d}{\mu}\cdot
c_{2}\int_{0}^{\infty}{\beta^{s-1}e^{-\frac{\beta^{2}}{2\sigma^{2}}}}\
\mathrm{d}{\beta}$ (27) $\displaystyle\leq
2\exp\left({-\frac{s\varepsilon^{2}}{4}}\right),$

where (27) follows from using tail bounds on the Gaussian distribution.

For Part $B^{\prime}$, using the second case (26),

$\frac{1-\widetilde{G}_{1s}}{\widetilde{G}_{1s}}\leq\frac{1}{\mathbb{P}_{t}(\theta_{1,t}>\mu_{1}-\varepsilon|\hat{\mu}_{1,s}=\mu)}.$

Then, reusing a calculation in Zhu & Tan (2020),

$\displaystyle
c_{1}c_{2}\int_{B^{\prime}}\frac{1-\widetilde{G}_{1s}}{\widetilde{G}_{1s}}\exp\left({-\frac{s{(\mu-\mu_{1})}^{2}}{2\sigma_{1}^{2}}}\right)\beta^{s-1}e^{-\frac{\beta^{2}}{2\sigma^{2}}}\,\mathrm{d}\mu\,\mathrm{d}\beta$
$\displaystyle\leq
c_{1}c_{2}\int_{B^{\prime}}\frac{1}{\mathbb{P}_{t}(\theta_{1,t}>\mu_{1}-\varepsilon|\hat{\mu}_{1,s}=\mu)}\exp\left({-\frac{s{(\mu-\mu_{1})}^{2}}{2\sigma_{1}^{2}}}\right)\beta^{s-1}e^{-\frac{\beta^{2}}{2\sigma^{2}}}\,\mathrm{d}\mu\,\mathrm{d}\beta$
$\displaystyle\leq
c_{1}\int_{-\infty}^{\mu_{1}-\varepsilon}{\frac{1}{\mathbb{P}_{t}(\theta_{1,t}>\mu_{1}-\varepsilon|\hat{\mu}_{1,s}=\mu)}\exp\left({-\frac{s{(\mu-\mu_{1})}^{2}}{2\sigma_{1}^{2}}}\right)}\,\mathrm{d}{\mu}\cdot
c_{2}\int_{0}^{\infty}{\beta^{s-1}e^{-\frac{\beta^{2}}{2\sigma^{2}}}}\,\mathrm{d}{\beta}$
$\displaystyle\leq\frac{\sqrt{2}}{\sqrt{\pi}}\cdot\frac{3}{\sqrt{2\pi}\varepsilon^{2}s\sqrt{s}}\cdot\exp\left({-\frac{s\varepsilon^{2}}{2}}\right)=\frac{3}{\pi\varepsilon^{2}s\sqrt{s}}\exp\left({-\frac{s\varepsilon^{2}}{2}}\right).$

Combining both parts, we can upper bound
$\mathbb{E}\left[{\frac{1}{G_{1s}}-1}\right]$ by

$\mathbb{E}\left[{\frac{1}{G_{1s}}-1}\right]\leq
2\exp\left({-\frac{s\varepsilon^{2}}{4}}\right)+\frac{3}{\pi\varepsilon^{2}s\sqrt{s}}\exp\left({-\frac{s\varepsilon^{2}}{2}}\right).$

Summing over $s$, we have

$\sum_{s=1}^{n}\mathbb{E}\left[{\frac{1}{G_{1s}}-1}\right]\leq\frac{C_{7}^{(a)}}{\varepsilon^{2}}+C_{8}^{(a)}.$

  2. ()

Suppose $i$ is a non-deceiver arm. Then

$E_{i}(t)=\left\\{{\hat{c}_{\alpha}(i,t)>\tau+\varepsilon}\right\\}\cap\left\\{{\hat{\mu}_{i,t}\geq\mu_{1}+\varepsilon}\right\\}\Rightarrow
E_{i}^{c}(t)\supseteq\left\\{{\hat{\mu}_{i,t}<\mu_{1}+\varepsilon}\right\\}.$

This allows us to establish lower bound

$\mathbb{P}_{t}(E_{1}^{c}(t)|T_{1,t}=s,\hat{\mu}_{1,s}=\mu,\hat{\sigma}_{1,s}=\sigma)\geq\begin{cases}\frac{1}{2}&\text{if
$\mu<\mu_{1}$}\\\ \mathbb{P}_{t}(\theta_{1,t}<\mu_{1}+\varepsilon)&\text{if
$\mu\geq\mu_{1}$.}\end{cases}$ (28)

Define the conditional version of $G_{1s}$ by

$\widetilde{G}_{1s}=G_{1s}|_{\hat{\mu}_{1,s},\hat{\sigma}_{1,s}=\beta}=\mathbb{P}_{t}(\hat{\mu}_{1,t}\leq\mu_{1}+\varepsilon\
\text{or}\
\hat{c}_{\alpha}(1,t)>\tau-\varepsilon\mid\hat{\mu}_{1,s},\hat{\sigma}_{1,s}=\beta).$

Define $c_{1}=\frac{1}{\sqrt{2\pi\sigma_{1}^{2}}}$ and
$c_{2}=\frac{1}{2^{\frac{s}{2}}\Gamma(s/2)\sigma_{1}^{s}}$. We partition the
parameter space

$(\beta,\mu)\in[0,\infty)\times(-\infty,\infty)=A^{\prime\prime}\cup
B^{\prime\prime}$

where $A^{\prime\prime}=[0,\infty)\times[\mu_{1},\infty)$ and
$B^{\prime\prime}=[0,\infty)\times(-\infty,\mu_{1}]$. We can then partition
$\mathbb{E}\left[{\frac{1}{G_{1s}}-1}\right]$ into two parts:

$\displaystyle\mathbb{E}\left[{\frac{1}{G_{1s}}-1}\right]$
$\displaystyle=c_{1}c_{2}\int_{0}^{\infty}{\int_{-\infty}^{\infty}{\frac{1-\widetilde{G}_{1s}}{\widetilde{G}_{1s}}\exp\left({-\frac{{(\mu-\mu_{1})}^{2}}{2\sigma_{1}^{2}}}\right)\beta^{s-1}e^{-\frac{\beta^{2}}{2\sigma^{2}}}}\
\mathrm{d}{\mu}}\ \mathrm{d}{\beta}$
$\displaystyle=c_{1}c_{2}\left({\int_{A^{\prime\prime}}+\int_{B^{\prime\prime}}}\right)\frac{1-\widetilde{G}_{1s}}{\widetilde{G}_{1s}}\exp\left({-\frac{{(\mu-\mu_{1})}^{2}}{2\sigma_{1}^{2}}}\right)\beta^{s-1}e^{-\frac{\beta^{2}}{2\sigma^{2}}}\
\mathrm{d}\mu\ \mathrm{d}\beta.$

For Part $B^{\prime\prime}$, using the first case in (28),

$\frac{1-\widetilde{G}_{1s}}{\widetilde{G}_{1s}}\leq 2(1-\widetilde{G}_{1s}).$

Thus,

$\displaystyle
c_{1}c_{2}\int_{B^{\prime\prime}}\frac{1-\widetilde{G}_{1s}}{\widetilde{G}_{1s}}\exp\left({-\frac{s{(\mu-\mu_{1})}^{2}}{2\sigma_{1}^{2}}}\right)\beta^{s-1}e^{-\frac{\beta^{2}}{2\sigma^{2}}}\,\mathrm{d}\mu\,\mathrm{d}\beta$
$\displaystyle\leq
2c_{1}c_{2}\int_{B^{\prime\prime}}(1-\widetilde{G}_{1s})\exp\left({-\frac{s{(\mu-\mu_{1})}^{2}}{2\sigma_{1}^{2}}}\right)\beta^{s-1}e^{-\frac{\beta^{2}}{2\sigma^{2}}}\,\mathrm{d}\mu\,\mathrm{d}\beta$
$\displaystyle\leq
2c_{1}c_{2}\int_{B^{\prime\prime}}\mathbb{P}_{t}\left({\theta_{1,t}\geq\mu_{1}+\varepsilon}\right)\mathbb{P}_{t}\left({\hat{c}_{\alpha}(1,t)\leq\tau-\varepsilon}\right)\exp\left({-\frac{s{(\mu-\mu_{1})}^{2}}{2\sigma_{1}^{2}}}\right)\beta^{s-1}e^{-\frac{\beta^{2}}{2\sigma^{2}}}\,\mathrm{d}\mu\,\mathrm{d}\beta$
$\displaystyle\leq
2c_{1}\int_{-\infty}^{\mu_{1}}\mathbb{P}_{t}\left({\theta_{1,t}\geq\mu_{1}+\varepsilon}\right)\mathrm{d}\mu\cdot\int_{0}^{\infty}c_{2}\exp\left({-\frac{s{(\mu-\mu_{1})}^{2}}{2\sigma_{1}^{2}}}\right)\beta^{s-1}e^{-\frac{\beta^{2}}{2\sigma^{2}}}\,\mathrm{d}\beta$
$\displaystyle\leq 2\exp\left({-\frac{s\varepsilon^{2}}{4}}\right).$

For Part $A^{\prime\prime}$, using the second case in (28),

$\frac{1-\widetilde{G}_{1s}}{\widetilde{G}_{1s}}\leq\frac{1}{\mathbb{P}_{t}(\theta_{1,t}<\mu_{1}+\varepsilon|\hat{\mu}_{1,s}=\mu)}.$

By reusing a calculation from Part $A$ of the proof of Lemma 3,

$\displaystyle
c_{1}c_{2}\int_{A^{\prime\prime}}\frac{1-\widetilde{G}_{1s}}{\widetilde{G}_{1s}}\exp\left({-\frac{s{(\mu-\mu_{1})}^{2}}{2\sigma_{1}^{2}}}\right)\beta^{s-1}e^{-\frac{\beta^{2}}{2\sigma^{2}}}\,\mathrm{d}\mu\,\mathrm{d}\beta$
$\displaystyle\leq
c_{1}c_{2}\int_{A^{\prime\prime}}\frac{1}{\mathbb{P}_{t}(\theta_{1,t}-\mu_{1}\leq\varepsilon|\hat{\mu}_{1,s}=\mu)}\exp\left({-\frac{s{(\mu-\mu_{1})}^{2}}{2\sigma_{1}^{2}}}\right)\beta^{s-1}e^{-\frac{\beta^{2}}{2\sigma^{2}}}\,\mathrm{d}\mu\,\mathrm{d}\beta$
$\displaystyle\leq
c_{1}\int_{\mu_{1}+\varepsilon}^{\infty}\frac{1}{\mathbb{P}_{t}(\theta_{1,t}-\mu_{1}\leq\varepsilon|\hat{\mu}_{1,s}=\mu)}\exp\left({-\frac{s{(\mu-\mu_{1})}^{2}}{2\sigma_{1}^{2}}}\right)\,\mathrm{d}\mu\cdot
c_{2}\int_{0}^{\infty}\beta^{s-1}e^{-\frac{\beta^{2}}{2\sigma^{2}}}\,\mathrm{d}\beta$
$\displaystyle\leq\frac{3}{\pi\varepsilon^{2}s\sqrt{s}}\exp\left({-\frac{s\varepsilon^{2}}{2}}\right).$

Combining both parts, we can upper bound
$\mathbb{E}\left[{\frac{1}{G_{1s}}-1}\right]$ by

$\mathbb{E}\left[{\frac{1}{G_{1s}}-1}\right]\leq
2\exp\left({-\frac{s\varepsilon^{2}}{4}}\right)+\frac{3}{\pi\varepsilon^{2}s\sqrt{s}}\exp\left({-\frac{s\varepsilon^{2}}{2}}\right).$

Summing over $s$, we have

$\sum_{s=1}^{n}\mathbb{E}\left[{\frac{1}{G_{1s}}-1}\right]\leq\frac{C_{7}^{(b)}}{\varepsilon^{2}}+C_{8}^{(b)}.$

Setting $C_{7}=\max\left\\{{C_{7}^{(a)},C_{7}^{(b)}}\right\\}$ and
$C_{8}=\max\left\\{{C_{8}^{(a)},C_{8}^{(b)}}\right\\}$, we get

$\sum_{s=1}^{n}\mathbb{E}\left[{\frac{1}{G_{1s}}-1}\right]\leq\frac{C_{7}}{\varepsilon^{2}}+C_{8}.$

∎

######  Lemma 11 (Upper bounding the second term of (24)).

For $\xi\in(0,1)$,

$\displaystyle\mathbb{P}(E_{i}^{c}(t)|T_{i,t}=s,\hat{\mu}_{i,t}=\mu,\hat{\sigma}_{i,t}=\sigma)$
$\displaystyle\leq\exp\left({-\frac{s}{2}\left({\mu-\mu_{i}+\frac{\xi(1-\alpha)(\Delta_{\tau}(i,\alpha)-\varepsilon)}{\alpha}}\right)^{2}}\right)+\exp\left({-sh\left({\frac{\sigma^{2}{(c_{\alpha}^{*})}^{2}}{{\left({\sigma_{i}c_{\alpha}^{*}-(1-\xi)(\Delta_{\tau}(i,\alpha)-\varepsilon)}\right)}^{2}}}\right)}\right).$

Furthermore,

$\sum_{s=1}^{n}\mathbb{P}_{t}\left({G_{is}>\frac{1}{n}}\right)\leq
1+\max\left\\{{\frac{2\alpha^{2}\log(2n)}{\xi^{2}{(1-\alpha)}^{2}\left({{\Delta_{\tau}(i,\alpha)-\varepsilon}}\right)^{2}},\frac{\log(2n)}{h\left({\frac{\sigma_{i}^{2}{(c_{\alpha}^{*})}^{2}}{{\left({\sigma_{i}c_{\alpha}^{*}-(1-\xi)(\Delta_{\tau}(i,\alpha)-\varepsilon)}\right)}^{2}}}\right)}}\right\\}+\frac{C_{9}}{\varepsilon^{4}}+\frac{C_{10}}{\varepsilon^{2}},$

where $C_{9},C_{10}$ are constants.

###### Proof of Lemma 11.

The result follows immediately from Lemma 8 by replacing
$(c_{\alpha}(1),\Delta_{\mathrm{r}}(i,\alpha))$ with
$(\tau,\Delta_{\tau}(i,\alpha))$. Choose

$\xi_{\alpha}=1-\frac{\sigma_{i}c_{\alpha}^{*}}{\Delta_{\tau}(i,\alpha)}\left({1-\frac{1}{\sqrt{h_{+}^{-1}(1/D_{\alpha,1}^{i})}}}\right)$

and repeat the argument in Theorem 1 by replacing
$(c_{\alpha}(1),\Delta_{\mathrm{r}}(i,\alpha))$ with
$(\tau,\Delta_{\tau}(i,\alpha))$ to get the desired result. ∎

##  Appendix C Proof of Theorem 3

The proof of Theorem 3 follows the same strategy and is even more
straightforward. Nevertheless, we include it here for completeness.

###### Proof of Theorem 3:.

For any arm $i\in{\mathcal{K}_{\tau}}\backslash{\mathcal{K}^{*}}$, define the
good event by

$E_{i}(t)=\left\\{{\hat{\mu}_{i,t}>\mu_{1}+\varepsilon}\right\\}.$

We first observe that

$E_{i}^{c}(t)=\left\\{{\hat{\mu}_{i,t}\leq\mu_{1}+\varepsilon}\right\\}.$

By Lemma 1, and the linearity of expectation, we can divide
$\mathbb{E}[T_{i,n}]$ into two parts as

$\mathbb{E}[T_{i,n}]\leq\sum_{s=0}^{n-1}\mathbb{E}\left[{\frac{1}{G_{1s}}-1}\right]+\sum_{s=0}^{n-1}\mathbb{P}\left({G_{is}>\frac{1}{n}}\right)+1.$
(29)

By the computations in part () ‣ B of the proof of Lemma 10, we have

$\sum_{s=1}^{n}\mathbb{E}\left[{\frac{1}{G_{1s}}-1}\right]\leq\frac{C_{11}}{\varepsilon^{2}}+C_{12}.$
(30)

By a Gaussian concentration bound,

$\mathbb{P}_{t}(E_{i}^{c}(t))=\mathbb{P}_{t}\left({\theta_{i,t}-\mu\leq-(\mu-\mu_{1}-\varepsilon)}\right)\leq\exp\left({-\frac{s}{2}\left({\mu-\mu_{1}-\varepsilon}\right)^{2}}\right).$

By similar computations as in Zhu & Tan (2020),

$\sum_{s=1}^{n}\mathbb{P}_{t}\left({G_{is}>\frac{1}{n}}\right)\leq
1+\frac{2\log(n)}{{(\mu_{i}-\mu_{1}-\varepsilon)}^{2}}+\frac{C_{13}}{\varepsilon^{4}}+\frac{C_{14}}{\varepsilon^{2}}.$
(31)

Plugging (30) and (31) into (29), we have the expected number of pulls on arm
$i$ up to round $n$ given by

$\mathbb{E}[T_{i,n}]\leq\frac{2\log(n)}{{(\mu_{i}-\mu_{1}-\varepsilon)}^{2}}+\frac{C_{9}^{\prime}}{\varepsilon^{4}}+\frac{C_{10}^{\prime}}{\varepsilon^{2}}+C_{11}^{\prime}.$

Setting $\varepsilon={(\log n)}^{-\frac{1}{8}}$, we get the following result
for the suboptimality regret:

$\limsup_{n\to\infty}\frac{\mathcal{R}_{n}^{\mathsf{sub}}(\text{CVaR-
TS})}{\log
n}\leq\sum_{i\in{\mathcal{K}_{\tau}}\backslash{\mathcal{K}^{*}}}\frac{2}{{(\mu_{i}-\mu_{1})}^{2}}\Delta(i).$

∎

##  Appendix D Proof of Theorem 4

###### Proof of Theorem 4:.

Let $\pi$ be any (risk-, infeasibility-, or suboptimality-)consistent
algorithm. We will prove the theorem in two parts, when the instances are
infeasible and feasible respectively.

  1. 1.

Fix the threshold level $\tau\in\mathbb{R}$. For any arm $i$ with distribution
$\nu(i)\sim{\cal N}(\mu_{i},\sigma_{i}^{2})$ in a given infeasible instance
$(\nu,\tau)$, define ${\cal S}_{i}=\left\\{{\nu^{\prime}(i)\in{\cal E}_{\cal
N}^{K}:c_{\alpha}(\nu^{\prime}(i))<c_{\alpha}(1)}\right\\}$ and

$\displaystyle\eta(i,\alpha)$ $\displaystyle=\inf_{\nu^{\prime}(i)\in{\cal
S}_{i}}\left\\{{\mathrm{KL}(\nu(i),\nu^{\prime}(i))}\right\\}=\inf_{\nu^{\prime}(i)\in{\cal
S}_{i}}\left\\{{\log\frac{\sigma_{i}^{\prime}}{\sigma_{i}}+\frac{\sigma_{i}^{2}+{(\mu_{i}-\mu_{i}^{\prime})}^{2}}{2{(\sigma_{i}^{\prime})}^{2}}-\frac{1}{2}}\right\\},$

where $\nu^{\prime}(i)\sim{\cal
N}(\mu_{i}^{\prime},{(\sigma_{i}^{\prime})}^{2})$ and the KL-divergence of two
Gaussians is well-known. By Theorem 4 in Kagrecha et al. (2020a), the expected
number of pulls of a non-optimal arm $i$ is characterised by

$\liminf_{n\to\infty}\frac{\mathbb{E}[T_{i,n}]}{\log
n}\geq\frac{1}{\eta(i,\alpha)}.$

Fix $\varepsilon>0$ and consider the arm $\nu^{\prime}(i)$ with distribution
${\cal
N}\left({\mu_{i}-\frac{\sqrt{2}}{\xi\sqrt{A_{\alpha,\xi}^{i}}}-\varepsilon,\sigma_{i}^{2}}\right)$.
Then a direct computation gives

$\displaystyle c_{\alpha}(\nu^{\prime}(i))-c_{\alpha}(1)$
$\displaystyle=\left({\mu_{i}-\frac{\sqrt{2}}{\xi\sqrt{A_{\alpha,\xi}^{i}}}-\varepsilon}\right)\left({\frac{\alpha}{1-\alpha}}\right)+\sigma_{i}c_{\alpha}^{*}-\mu_{1}\left({\frac{\alpha}{1-\alpha}}\right)-\sigma_{1}c_{\alpha}^{*}$
$\displaystyle=\mu_{i}\left({\frac{\alpha}{1-\alpha}}\right)-\Delta_{\mathrm{r}}(i,\alpha)-\mu_{1}\left({\frac{\alpha}{1-\alpha}}\right)+(\sigma_{i}-\sigma_{1})c_{\alpha}^{*}-\varepsilon\left({\frac{\alpha}{1-\alpha}}\right)$
$\displaystyle=-\Delta_{\mathrm{r}}(i,\alpha)+\Delta_{\mathrm{r}}(i,\alpha)-\varepsilon\left({\frac{\alpha}{1-\alpha}}\right)$
$\displaystyle=-\varepsilon\left({\frac{\alpha}{1-\alpha}}\right)$
$\displaystyle<0.$

Thus, $c_{\alpha}(\nu^{\prime}(i))<c_{\alpha}(1)$ and $\nu^{\prime}(i)\in{\cal
S}_{i}$. Furthermore,

$\displaystyle\mathrm{KL}(\nu(i),\nu^{\prime}(i))$
$\displaystyle={\log\frac{\sigma_{i}}{\sigma_{i}}+\frac{\sigma_{i}^{2}+\left({\mu_{i}-\left({\mu_{i}-\frac{\sqrt{2}}{\xi\sqrt{A_{\alpha,\xi}^{i}}}-\varepsilon}\right)}\right)^{2}}{2\sigma_{i}^{2}}-\frac{1}{2}}=\frac{1}{\xi^{2}\sigma_{i}^{2}A_{\alpha,\xi}^{i}}-\frac{\varepsilon}{2\sigma_{i}^{2}}\left({\frac{2\sqrt{2}}{\xi\sqrt{A_{\alpha,\xi}^{i}}}-\varepsilon}\right).$

By the definition of $\eta$,

$\eta(i,\alpha)\leq\lim_{\varepsilon\to
0^{+}}\left[{\frac{1}{\xi^{2}\sigma_{i}^{2}A_{\alpha,\xi}^{i}}-\frac{\varepsilon}{2\sigma_{i}^{2}}\left({\frac{2\sqrt{2}}{\xi\sqrt{A_{\alpha,\xi}^{i}}}-\varepsilon}\right)}\right]=\frac{1}{\xi^{2}\sigma_{i}^{2}A_{\alpha,\xi}^{i}}\quad\Longrightarrow\quad\frac{1}{\eta(i,\alpha)}\geq\xi^{2}\sigma_{i}^{2}A_{\alpha,\xi}^{i}.$

Hence,

$\liminf_{n\to\infty}\frac{\mathcal{R}_{n}^{\mathsf{risk}}(\pi)}{\log
n}=\sum_{i\in{[K]}\backslash{\mathcal{K}^{*}}}\left({\liminf_{n\to\infty}\frac{\mathbb{E}[T_{i,n}]}{\log
n}}\right)\Delta_{\mathrm{r}}(i,\alpha)\geq\sum_{i\in{[K]}\backslash{\mathcal{K}^{*}}}\xi^{2}\sigma_{i}^{2}A_{\alpha,\xi}^{i}\Delta_{\mathrm{r}}(i,\alpha).$

  2. 2.

Fix the threshold level $\tau\in\mathbb{R}$. For any arm $i$ with distribution
$\nu(i)\sim{\cal N}(\mu_{i},\sigma_{i}^{2})$ in a given feasible instance
$(\nu,\tau)$, define ${\cal V}_{i}=\left\\{{\nu^{\prime}(i)\in{\cal E}_{\cal
N}^{K}:\mu(\nu^{\prime}(i))<\mu_{1}\ \text{and}\
c_{\alpha}(\nu^{\prime}(i))\leq\tau}\right\\}$ and

$\displaystyle\eta(i,\alpha)$ $\displaystyle=\inf_{\nu^{\prime}(i)\in{\cal
V}_{i}}\left\\{{\mathrm{KL}(\nu(i),\nu^{\prime}(i))}\right\\}=\inf_{\nu^{\prime}(i)\in{\cal
V}_{i}}\left\\{{\log\frac{\sigma_{i}^{\prime}}{\sigma_{i}}+\frac{\sigma_{i}^{2}+{(\mu_{i}-\mu_{i}^{\prime})}^{2}}{2{(\sigma_{i}^{\prime})}^{2}}-\frac{1}{2}}\right\\},$

where $\nu^{\prime}(i)\sim{\cal
N}(\mu_{i}^{\prime},{(\sigma_{i}^{\prime})}^{2})$ and the KL-divergence of two
Gaussians is well-known. By Theorem 4 in Kagrecha et al. (2020a), the expected
number of pulls of a non-optimal arm $i$ is characterised by

$\liminf_{n\to\infty}\frac{\mathbb{E}[T_{i,n}]}{\log
n}\geq\frac{1}{\eta(i,\alpha)}.$

Suppose arm $i$ is infeasible. Fix $\varepsilon>0$, and consider the arm
$\nu^{\prime}(i)$ with distribution ${\cal
N}\left({\mu_{i}-\frac{\sqrt{2}}{\xi\sqrt{D_{\alpha,\xi}^{i}}}-\varepsilon,\sigma_{i}^{2}}\right)$.
Then $\mu(\nu^{\prime}(i))<\mu_{1}$ trivially, and a direct computation gives

$\displaystyle c_{\alpha}(\nu^{\prime}(i))-\tau$
$\displaystyle=\left({\mu_{i}-\frac{\sqrt{2}}{\xi\sqrt{D_{\alpha,\xi}^{i}}}-\varepsilon}\right)\left({\frac{\alpha}{1-\alpha}}\right)+\sigma_{i}c_{\alpha}^{*}-\tau$
$\displaystyle=\mu_{i}\left({\frac{\alpha}{1-\alpha}}\right)-\Delta_{\tau}(i)+\sigma_{i}c_{\alpha}^{*}-\tau-\varepsilon\left({\frac{\alpha}{1-\alpha}}\right)$
$\displaystyle=\mu_{i}\left({\frac{\alpha}{1-\alpha}}\right)-c_{\alpha}(i)+\sigma_{i}c_{\alpha}^{*}-\varepsilon\left({\frac{\alpha}{1-\alpha}}\right)$
$\displaystyle=-\varepsilon\left({\frac{\alpha}{1-\alpha}}\right)<0.$

Thus, $c_{\alpha}(\nu^{\prime}(i))<\tau$ and $\nu^{\prime}(i)\in{\cal V}_{i}$.
By similar computations as in Part 1,

$\displaystyle\mathrm{KL}(\nu(i),\nu^{\prime}(i))$
$\displaystyle={\log\frac{\sigma_{i}}{\sigma_{i}}+\frac{\sigma_{i}^{2}+\left({\mu_{i}-\left({\mu_{i}-\frac{\sqrt{2}}{\xi\sqrt{D_{\alpha,\xi}^{i}}}-\varepsilon}\right)}\right)^{2}}{2\sigma_{i}^{2}}-\frac{1}{2}}=\frac{1}{\xi^{2}\sigma_{i}^{2}D_{\alpha,\xi}^{i}}-\frac{\varepsilon}{2\sigma_{i}^{2}}\left({\frac{2\sqrt{2}}{\xi\sqrt{A_{\alpha,\xi}^{i}}}-\varepsilon}\right).$

By the definition of $\eta$,

$\eta(i,\alpha)\leq\lim_{\varepsilon\to
0^{+}}\left[{\frac{1}{\xi^{2}\sigma_{i}^{2}D_{\alpha,\xi}^{i}}-\frac{\varepsilon}{2\sigma_{i}^{2}}\left({\frac{2\sqrt{2}}{\xi\sqrt{A_{\alpha,\xi}^{i}}}-\varepsilon}\right)}\right]=\frac{1}{\xi^{2}\sigma_{i}^{2}D_{\alpha,\xi}^{i}}\quad\Longrightarrow\quad\frac{1}{\eta(i,\alpha)}\geq\xi^{2}\sigma_{i}^{2}D_{\alpha,\xi}^{i}.$

Hence,

$\liminf_{n\to\infty}\frac{\mathcal{R}_{n}^{\mathsf{inf}}(\pi)}{\log
n}=\sum_{i\in\mathcal{K}_{\tau}^{*}}\left({\liminf_{n\to\infty}\frac{\mathbb{E}[T_{i,n}]}{\log
n}}\right)\Delta_{\tau}(i)\geq\sum_{i\in\mathcal{K}_{\tau}^{c}}\xi^{2}\sigma_{i}^{2}D_{\alpha,\xi}^{i}\Delta_{\tau}(i).$

Now, suppose arm $i$ is feasible but suboptimal. Fix $\varepsilon>0$ and
consider the arm $\nu^{\prime}(i)$ with distribution ${\cal
N}(\mu_{i}-\sigma_{i}\Delta(i)-\varepsilon,\sigma_{i}^{2})$. Then a direct
computation gives

$\displaystyle c_{\alpha}(\nu^{\prime}(i))-\tau$
$\displaystyle=(\mu_{i}-\sigma_{i}\Delta(i)-\varepsilon)\left({\frac{\alpha}{1-\alpha}}\right)+\sigma_{i}c_{\alpha}^{*}-\tau$
$\displaystyle=\mu_{i}\left({\frac{\alpha}{1-\alpha}}\right)-\tau-\sigma_{i}\Delta(i)\left({\frac{\alpha}{1-\alpha}}\right)+\sigma_{i}c_{\alpha}^{*}-\varepsilon\left({\frac{\alpha}{1-\alpha}}\right)$
$\displaystyle=c_{\alpha}(i)-\tau-\sigma_{i}\Delta(i)\left({\frac{\alpha}{1-\alpha}}\right)-\varepsilon\left({\frac{\alpha}{1-\alpha}}\right)<0.$

Thus, $c_{\alpha}(\nu^{\prime}(i))<\tau$ and $\nu^{\prime}(i)\in{\cal V}_{i}$.
By similar computations as in the previous parts,

$\displaystyle\mathrm{KL}(\nu(i),\nu^{\prime}(i))$
$\displaystyle={\log\frac{\sigma_{i}}{\sigma_{i}}+\frac{\sigma_{i}^{2}+\left({\mu_{i}-\left({\mu_{i}-\sigma_{i}\Delta(i)-\varepsilon}\right)}\right)^{2}}{2\sigma_{i}^{2}}-\frac{1}{2}}$
$\displaystyle=\frac{\sigma_{i}^{2}\Delta^{2}(i)}{2\sigma_{i}^{2}}-\frac{\varepsilon}{2\sigma_{i}^{2}}\left({2\sigma_{i}\Delta(i)-\varepsilon}\right)$
$\displaystyle=\frac{\Delta^{2}(i)}{2}-\frac{\varepsilon}{2\sigma_{i}^{2}}\left({2\sigma_{i}\Delta(i)-\varepsilon}\right).$

By the definition of $\eta$,

$\eta(i,\alpha)\leq\lim_{\varepsilon\to
0^{+}}\left[{\frac{\Delta^{2}(i)}{2}-\frac{\varepsilon}{2\sigma_{i}^{2}}\left({2\sigma_{i}\Delta(i)-\varepsilon}\right)}\right]=\frac{\Delta^{2}(i)}{2}\quad\Longrightarrow\quad\frac{1}{\eta(i,\alpha)}\geq\frac{2}{\Delta^{2}(i)}.$

Hence,

$\liminf_{n\to\infty}\frac{\mathcal{R}_{n}^{\mathsf{sub}}(\pi)}{\log
n}=\sum_{i\in{\mathcal{K}_{\tau}}\backslash{\mathcal{K}^{*}}}\left({\liminf_{n\to\infty}\frac{\mathbb{E}[T_{i,n}]}{\log
n}}\right)\Delta(i)\geq\sum_{i\in{\mathcal{K}_{\tau}}\backslash{\mathcal{K}^{*}}}\frac{2}{\Delta(i)}.$

∎