Optimal Best-Arm Identification Methods for Tail-Risk Measures
Authors: Shubhada Agrawal
Wouter M Koolen
Sandeep Kumar Juneja
Venue: NeurIPS 2021 Poster (2021)
Keywords: Multi-armed bandits
pure exploration
CVaR
VaR
tail-risk
heavy-tailed distributions
best-arm identification

Abstract: Conditional value-at-risk (CVaR) and value-at-risk (VaR) are popular tail-risk measures in finance and insurance industries as well as in highly reliable, safety-critical uncertain environments where often the underlying probability distributions are heavy-tailed. We use the multi-armed bandit best-arm identification framework and consider the problem of identifying the arm from amongst finitely many that has the smallest CVaR, VaR, or weighted sum of CVaR and mean. The latter captures the risk-return trade-off common in finance. Our main contribution is an optimal $\delta$-correct algorithm that acts on general arms, including heavy-tailed distributions, and matches the lower bound on the expected number of samples needed, asymptotically (as $ \delta$ approaches $0$). The algorithm requires solving a non-convex optimization problem in the space of probability measures, that requires delicate analysis. En-route, we develop new non-asymptotic, anytime-valid, empirical-likelihood-based concentration inequalities for tail-risk measures. 

Optimal Best-Arm Identification Methods for Tail-Risk Measures
Shubhada Agrawal TIFR, Mumbai, India shubhadaiitd@@maal.. com
Wouter M. Koolen CWI, Amsterdam wmkoolen@cwi.nn
Sandeep Juneja TIFR, Mumbai, India j juneja@tifr rrss in
Abstract
Conditional value-at-risk (CVaR) and value-at-risk (VaR) are popular tail-risk measures in finance and insurance industries as well as in highly reliable, safety- critical uncertain environments where often the underlying probability distributions are heavy-tailed. We use the multi-armed bandit best-arm identification framework and consider the problem of identifying the arm from amongst finitely many that has the smallest CVaR, VaR, or weighted sum of CVaR and mean. The latter captures the risk-retun trade-off common in finance. Our main contribution is an optimal 8- correct algorithm that acts on general arms, including heavy-tailed -tiled distributions, and matches the lower bound on the expected number of samples needed, asymptotically (as approaches 0). The algorithm requires solving non-convex optimization problem in the space of probability measures, that requires delicate analysis. En- route, we develop new non-asymptotic, anytime-valid, concentration inequalities for tail-risk measures.
Introduction
Tail risk is a common term used to quantify losses occurring due to rare events, and has been important topic in finance, insurance and other safety critical uncertain environments. [44] first formalized the problem of identifying optimal investment in financial assets optimization problem of maximizing the average return, while minimizing the risk (measured via variance). Since then, several other risk measures have been considered. Lately, risk-measures based on tails of the distribution, like the conditional value-at-rist. (CVaR) and value-at-risk (VaR), have gained popularity in financial regulations and risk management (see, [48 47). where the underlying probability distributions are mostly heavy tailed (i.e. having infinite moment generating function for all 0 0). Informally, for probability measure 7/. VaR level (0, 1) the th quantile for n, i..., the outcome below which there is exactly æ mass. CVaR at level и is the conditional expectation of y,, conditioned
multi-criteria
values beyond the VaR level æ. See Section 2 for precise definitions, and (50 46 for applications of these risk measures in finance and optimization. As opposed to VaR, CVaR is a coherent risk-measure, and is a preferable metric (see. (5] for precise definition and properties of coherence). Outside finance, these tail-risk measures are being used to control risk in operations management, for example, in inventory management [4, supply chain management [5I], etc. Recently, coherent risk measures, especially CVaR, have also been used in connection with fairness machine learning [58).
The importance of these risk measures in the sequential decision making set-up has well been acknowledged (see, 49) 42). Typically in the stochastic multi-armed bandit (MAB) literature, the quality of an arm is measured using its mean. Tight asymptotic and finite time guarantees exist for
different MAB problems with performance measured by the mean (see, (27 36 16 13
I 53)).
Also, see [12 for a survey of the variants of stochastic MAB problems. However, maximizing the average reward is not always the primary desirable objective. In clinical trials, for example, the treatment that is good average might result in adverse outcomes for some patients. In finance, one
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

is typically interested in balancing the mean return with the risk of extreme losses. Risk sensitivity has been well studied the online learning setting, where in each round, the player sees reward from every arm (see, [24 56 ). However, there is very limited work which incorporates these risk-measures into the MAB framework.
In this paper, we provide systematic approach for identifying the distribution (or arm) from a given finite set of distributions (or arms) with minimum tail-risk (as measured by CVaR VaR, or by a conic combination of mean and CVaR, which we will henceforth refer to as the "mean-CVaR" objective). Adopting the best-arm identification (BAI) framework of the stochastic MAB problem. we consider algorithms that generate samples from the given arms, and are 8- d-correct, i.e., identify the correct answer (arm with minimum VaR. CVaR mean- mean-CVaR) with probability at least 1 8, for some pre-specified confidence level 8. While ensuring 6-correctness, the aim is to minimize the number of samples needed by the algorithm before its termination. This is the typical fixed-confidence setting of the BAI MAB problem (see, [37 2 2). Variants of this problem have been widely studied in the literature, where the best-arm is the one with maximum mean (see,
25
26
A relaxation of the pure exploration setting described above is the d) setting, where the aim is to output an e-optimal arm (for an appropriate notion of e-optimality,, with probability at least
1- ô, while minimizing the number of samples generated. [59] 18] 32 consider the pure exploration
problem of identifying the arm with minimum risk the (c. PAC setting. While [59 consider both VaR and CVaR as measures of risk. [18 32] focus on the VaR-problem. Recently, [39] and
B5 have studied the BAI MAB problem with CVaR and eVaR objectives, respectively, in the closely related fixeedbudget" framework, in which the total number of samples the algorithm is
allowed take is fixed, and the aim of the algorithm is minimize the grror-rrobability
1.1 Outline of the approach and main assumption
As warm-up, we first solve our minimum tail risk identification problems in the simple commonplace setting of arm-distributions belonging to a canonical single parameter exponential family (SPEF) of distributions. Each distribution in this family is uniquely identified with parameter. We show that both CVaR and VaR are monotonic functions of this parameter, as is the mean. Hence, finding the best-(CVaR Saeaa/////mean/CW//
arm reduces to finding the arm with the minimum mean.
Since lesk-sensitvee objectives are particularly important when there a non-trivial probability of occurrence of extreme outcomes, it is important consider din-iisrributions beyond canonical SPEF, for which the above-mentioned equivalence breaks. We solve the VaR problem for arbitrary arm distributions.
In contrast the CVaR problem unlearnable full generality: on the class of all arm distributions, any d-correct algorithm requires infinite number of samples in expectation to identify the best arm amongst any finite collection of arms (Remark 3.I.. To avoid this, we impose a mild and standard raw (1 + -moment restriction on the arm-distriiutions. Let P(R) denote the collection of all the probability distributions on the reals R, and let and be positive constants. For risk measure CVaR and for the mean-CVaR objective, we restrict the class of allowed arm distributions to
C= c=(n EE P(R)) E, (1X) S B)
We discuss the choice of parameters in Section below. For each tail measure, we prove information- theoretic lower bounds the sample complexity of any d-correct algorithm, and use these develop a 8-correct algorithm whose sample complexity exactly matches the lower bound as 8 + O, for CVaR, mean-CVaR, and VaR problems. The mean-CVaR problem is conceptually and technically similar to the CVaR problem. Hence, for simplicity of presentation, we primarily focus on the CVaR setting in the main text and give details of the -VRR setting in Appendix II We also spell out the somewhat analogous analysis for the VaR setting towards the end (Section with details deferred Appendix to H
1.2 Technical contributions
As is well known in the BAI MAB literature, the lower bound problem takes the underlying arm distributions as inputs and solves for optimal weights that determine the proportion of samples that should idcally be allocated to each arm. The proposed algorithm uses a plugin strategy that at each

---

sequential stage, modulo mild forced exploration. uses the generated empirical distributions as proxy for the true distributions and arrives at weights that guide the sequential sampling strategy.
In order to highlight the technical challenges arising in our non-parametric case, we will need to introduce two functionals next that are central lower bounds, algorithms, confidence intervals etc.
Information distance for CVaR problem: Given 71, 7/2 in P(R). let KL(1; 722) denote the KL- dm
divergence between them, i.e., (T, := log ang (y)dm (y). Furthermore, for the probability measure 7) let (1) denote its CVaR the given confidence level π E (0. 1) (see Section 2 for the exact definition). Then, given 1/ E ((R) and x E R, we define functionals KL, P(R)x and KT
Rt.
P(R) x R Rt, where R- denotes the non-negative reals, as
KL (L, (1,
min
(I, and
(n, min NEC: or (x)
KL(n, R:).
(1)
KEC: (K)22
See 22 30 15 for related quantities. These projection functionals appear in the lower bound (Section 3). and are central to our plugin algorithm.
Unlike their analogues in the mean case, KT 'inf and KT in 1 are not symmetric, and need to be studied separately. In particular, KL is convex optimization problem, while KL is not. This is because (=(-) concave function, whence, the CVaR constraint in the KL problem in [ renders the feasible region non-convex (see Section 2. CVaR can be expressed as the optimal value of a minimization problem. This helped re-expressing KI as minimization over variables. fixing one of which resulted in convex optimization over the other (see Section 33.
For proving 5-correctness, we develop new concentration inequality for weighted sums of these functionals (Proposition (4.)). Dual representations of these suggest natural candidates for super- martingales, whose mixtures help in proving the concentration result. Similar inequalities were developed in [38] 20 54 in different settings, See [40] Chapter 20] for an overview of the method of mixtures. We also propose KL and KL KL,,, tight anytime-valid confidence intervals for CVaR for heavy-tailed distributions, and show that classical confidence intervals derived using popular truncation-based estimators can be recovered using our method, with only a minor overhead (see
Section 4.3).
Since distributions in L are not characterized by parameters, work in the space of probability measures instead of in the Euclidean space. A key and non-trivial requirement for the proof of asymptotic optimality of the algorithm is the joint continuity of in and KT in a well-chosen metric, which should generate a topology that is sufficiently fine to ensure this continuity, but coarse to ensure fast convergence of the empirical distributions to the true-arm distributions. We endow P(R) with the topology of weak convergence, or equivalently, with the Lévy metric (see Section for definitions). Another nuance in our analysis is that the empirical distributions may not lie in Z. This is handled by projecting these on to L under suitable metric.
Our proposed algorithm is a plugin strategy that involves solving the lower bound problem using the empirical distributions as a proxy for the actual arm distributions. This can be computationally demanding especially the underlying samples in the empirical distribution become large. To ease the numerical burden we propose modifications that require solving the lower bound only order log(n) many times till stage of the algorithm (where samples generated). This modification substantially reduces the computation burden. We show that it is optimal up to a constant (Appendix K.
VaR problem: Our algorithm for CVaR, with KL and KL iin replaced by the corresponding functionals with the VaR constraints instead, is asymptotically optimal for this problem in complete generality (Section 4.2). Here, KL in and KL have closed form representations. However, they are no longer -ontticco in the Lévy metric, which introduces new technical challenges in the analysis of the algorithm.
1.3 Regarding the choice of and in our assumption
Firstly, BAI problems are important in simulation where the best model may need to be identified amongst many intricate models in terms of a performance measure such as CVaR or VaR, using minimal computational effort (see, B1). Input distributions in simulation are known and may often
3

---

involve heavy tails. In some cases, by the use of syapunov-function based techniques, bounds on moments of output random variables, B, can be determined. (see. e.g.. [28] and references therein). Secondly, consider rewards (returns) from a number of hedge funds. Each time some amount of money is invested into a fund, a random return may be revealed from that fund but not from others. To assume that these returns come from class of parametric distributions or have known bounded support can be a substantially inaccurate simplification. Typically, from historical analysis, it is known that the distribution of securities have particular tail index, say, (1 + +e). For stock returns, extensive research suggests that (1 + e) E 5]. For daily exchange rates and income and wealth distributions we may have (1 + <) E (1, Extreme value theory, under reasonable dependence structure amongst underlying securities, shows that portfolio (a weighted sum) will also have the same tail index of (1 + e) (see, [9). So the key approximation needed is in arriving at B. It is easy to arrive at distributions 7) and i. whose (1 + <)th moments are arbitrarily far while the KI. distance between them is arbitrarily close to zero. This makes it difficult to infer B from a given sample of data without further restriction on the two distributions. One may take pragmatic view and approximate by estimating the (1 + e)th moment from observed samples and padding it up with a reasonably large factor. A further set of distributional assumptions would be needed to justify the above procedure to arrive at B. Again, verifying those assumptions will entail similar problems. In practice, one may live with the above approximation even though in rare settings it may be inaccurate and lead to sub-optimal allocations in our algorithm. One accepts this risk as one often accepts the assumption that the distributions of the random samples from each arm are time stationary or independent, even though these may only be approximately correct.
2 Background
For K > 2, let M LK denote the collection of all K-vectors of distributions, v (11,-...3 ......... vR), such that for all i, vÚ belongs to L. Let Ja E M be the given bandit problem, and π E (0, 1) denote the fixed confidence level. For 7 E P(3)). let (v) = n1(_00, v)) denote the CDF function for n,. and let mn) denote mean of measure v).
VaR, CVaR: With the above notation, VaR at level for the distribution 7) denoted x (1)) equals min f2 E R: (x) 2 T}- Since (-) is a nen-decraaiing and right-continuous function, the minimum in the expression of VaR is always attained. Define CVaR at level π, Cx (x))).
(n) (x))
1
I (n)
+
(d).
1 1-
π 2,, (n)
2
If 17 has density in a neighbourhood around Zg, then cx (n) = E., (X| > In (n)) i... it measures the average loss conditioned on the event that losses are larger than the VaR.
In the figure above, the total shaded area (green and blue regions, together) divided by 1 - x denotes the CVaR of the measure whose CDF function is displayed in red. To see this, observe that the first term in the expression above, scaled by (1 T), equals the blue region. The integral in the second term when simplified using integration by parts can be seen to equal the green region. There are alternative formulations of CVaR, which we state without proofs.
(p(n)dp = min { + #oER
1 _
E. ((X ((xxxo)+1 mm)++
(n) = 1
{To
(2)
pE(S,1]
1
ydo(v) s.t. Vy, du(w)= S dr(y) and / du(ly)= n, (3)
max (R) π
where (x) denotes max (0, ) and M M+(R) denotes collection of all non-negative measures on R.
From since c, (n) is a minimum of linear functions of 17, it is a concave function of 1). Thus, the KLU problem in (1) is convex optimization problem, while the KLJ; problem is not, since the (-)-) constraint makes the feasible region non-convex. See, [50 for a comprehensive tutorial on the two tail-risk measures, and their properties.
Parametric case: Using the definition of VaR, can be argued that xy (16) is a monotonically increasing function of 0 when ne belongs to a canonical SPEF with parameter 8, as is the mean. The

---

first formulation in 2 then gives that (x identifying the best- CWaa//aa//maan-CCCC mean. See Appendix A for details.
) is also monotonically increasing. Thus, the problem of arm is equivalent to identifying that with minimum
However, the ranking in mean and in CVaR can be very different in general. To this, fix 0.8, and consider a 3-armed bandit instance, v, with = 0.86p + 0.261, 12 = 0.860 + 0.200.5. and 13 0.5 0.5 + 0.282. Clearly, m(r1) > m((2) m(r3). yet c₂ (12) < c, (v1) < G (v3).
General case: For v in class L, the moment-constrain limits the minimum and maximum possible values of VaR and CVaR, discussed in the following lemma (proof in Appendix B)
Lemma 2.1. For E L, Ca(T)) E DD and I (T) E C, where
4.
ihe
B
and a c
B
i+f
B
B
1
Topology of weak convergence and the Lévy metrie: Let ø be a bounded and continuous function R, 8 > 0, and base sets of the form U(0,2,0) 8) = E Is o(y)dn(v) æ| < 53 Weak convergence
R. Consider the topology on P(R), generated by the
of sequence Kn. to K, denoted as Kn. 2 K, convergence in this topology [see 23 Sec-
the Lévy metric on P(R), (denoted by dz), de- fined next (see, [ Theorem 6.8]. 23 Theorem D88.. For K. E P(R)), dr (1, x)) equals inf {ō > 0 F2 8) 8 H (x(x) S F2 6, Vo E R} Additionally, the metric space (P(R), dz) is complete and separable.
tion D.2]. It equivalent to convergence
3 Lower bound
We consider 8-correct algorithms for identifying the arm with minimum CVaR, acting on bandit problems in M. While ensuring 5-correctness, the aim is to minimize the sample complexity, i.e., expected number of samples generated by the algorithm before terminates. As is well known, the 5-correctness property imposes a lower bound on the sample complexity of such algorithms.
Let ya .M denote the given bandit problem. Henceforth, for ease of notation, assume without loss of generality that the hest-CVaR arm in J is arm 1. Let Σx denote the probability simplex in RK .Ay denote the collection of all bandit problems in M which have arm j as the best-CVaR arm, Ts be the stopping time for the d-correct algorithm, (T) denote the number of times arm a has been sampled by the algorithm, and for a S. let S denote its interior. easy to deduce using standard arguments (see, e.g., 440 Theorem 33.5)) that for a 8-correct algorithm acting on μ E A1,
K
E (T8) 2 V(H)* log 48
where V(n)= = sup inf LEER YEAR
Σ to KL va), and Aÿ = =M Ay. (4)
Lemma 3.1. For μ AI, the inner minimization problem in (nn) equals
min inf {ti KLL (11, v) + tú ( 341 asy
and hence
sup min inf KL (M1, + KI (mr V(n)
(5)
teSx
f#l
2$y
Recall from (1) that the expressions in 4 and (5) above differ from those in the best-mean arm setting in that the functionals L and KI
KL
U
here are defined instead with the CVaR constraints.
'inf
Remark 3.1. Without any restriction on arm distributions for the CVaRR-problem, for y R and C. KLU (n. y) = O. This is essentially because 1) can be perturbed in KL only slightly by shifting an arbitrarily small mass from the lower tail to the extreme right, so that the CVaR constraint is satisfied. Thus, without any restrictions, V(μ) = 0 (see. (2 Lemma 1, Theorem 3] for similar results in selecting the arm with the largest mean setting). However, we later solve the VaRR-problem without such assumptions, i.e., arm distributions are allowed to be arbitrary probability measures in R. The lower bound for the VaR problem as in with KT, iut and KT, KT_Y
inn in the representation in
(5) defined with VaR constraints, instead.
5

---

A proof of Lemma 3.1 can be found in Appendix C.1 Let t" . - x In particular, for v E M. let t" (v) denote the set of maximizers in the (2) optimization problem in ( A key nuance of our algorithm and the related analysis is that the vector of empirical distributions may not belong to the class M. The algorithm first projects the empirical distribution to class L, then solves for the optimal t* in 5 for the projected distributions, and samples the arms in proportion to the computed to (Sectionn)) 4). For appropriate choices of the projection maps, the following lemmas guarantee that as the empirical distributions converge to the actual arm rrm-distributions (in the weak topology), the t* computed by the algorithm converge to the optimal weights corresponding to J..
Lemma 3.2. C is compact set in the topology of weak convergence and the (Skorokhod transforms of) its members form a uniformly integrable collection of random variables. When restricted to C D KL and kL are both jointly continuous functions of the arguments. Moreover, for fixed KL, int ar) is convex function of v.
Definition (Upper hemicontinuity)
set-valued function I' S I' is upper hemicontinuous at s E S if for any open neighbourhood V of l(ss) there exists a neighbourhood U of s such that for all E U, (x) ) a subsest of V.
Lemma 3.3. t" is an upper-hemicootinuuus correspondence, For v E M,, (v) is a convex set.
In Lemma 3.2. we restrict to the interior of D as KL mf Br - x) and KL (: -Brit) are not continuous (see, Remark C.2). In Lemma 3.3 we only need to eliminate distributions with these extreme CVaRs (there are only two such distributions. See, Remark C.I). Lemma 3.3 and Theorem 4.1 (optimality and ō-correctness of the proposed algorithm) hold for distributions with CVaR in Dr. For ease of notation, we restrict j lie in the interior of M.
The proofs of the above two lemmas are technically challenging and involve nuanced analysis. Detailed steps are given in Appendix C.2 and C.3
We first prove joint lower- and upper-semicontinuit
of the KL-projection functionals separately. These rely on various properties of the weak convergence of probability measures in L, the dual representations for KL mg and KI (see Theorem 3.4). properties of C'aRR for probability measures in L. and the classical Berge's theorem (see, 52 for continuity of the optimal value and the set of optimizers for a parametric optimization problem.
We then use these to prove the continuity in Lemma 3.3) Convexity follows since 1* is the set of maximizers of concave function over a convex, compact set.
Understanding the lower bound: Our proposed algorithm requires repeated evaluations of the lower bound in 4 at its estimates of μ. To facilitate this, now provide more tractable characterizations of the two KL-projection functionalss, and in particular, of (5). We also discuss the statistical and computational implications of these alternative characterizations.
For 1) E (R)), let Supp(1) denote the collection of points in the support of measure 1). For V E D Io E C, E R2 7 R², and X E R, set
/ ( X, u)
A1 A2 x) >s(1X B) (A1X (1 x)¹ x2)+
and
g' u, v, 2o) = 1 - xo -(x -20)+ (1 (1- m) (2 - 11|1+
Furthermore, define 5(v) = {\ 2 0, E R, 2 0 Vr E R, n (x, A,,, 2 0} and R2 ( v) to be (n 2 72 2 V. E R.
v, 2 0}. Notice that these are convex sets.
As shown in Theorem beloww 9 (y. v) and g² 20) are related to the dual formulations of KI. and kT.,, respectively, and the parameters X and y are the corresponding dual variables.
The sets S and R₂ correspond to the feasible values these dual variables. Theorem 3.4. For 17 E P(R) and Do.
(a)
KT (1. (1) v) max F, (log ( (x,A,)))
XES(v)
The maximum in this expression is attained at a unique point X* S(v). The unique probability measure K* E L that achieves infimum in the primal problem satisfies
drs dn (y) = 9d (y,>a,0)
for y E Supp(n).

---

Moreover, it has mass on at most 2 points outside Supp(n). {Supp(x*) Supp(n)), g" (v/ .,,)
Furthermore, for y E
(b)
KL (1,
min
max (TO.))
Ey (log 7,,
TFc
For a fixed To. the maximum in the inner problem is attained at unique Y in R2 u). The unique probability measure '²* E L achieving infimum in the primal problem satisfies
dx²
(v) g gy 7" v,
for y E Supp(n)-
dn
Moreover, size of the set (Supp(x*) Supp(n)} {Supp(k*) {upp(n)), g (v'n" xo) =0
most 1, and for y
These dual formulations help in reformulating the lower bound optimization problem in ( as optimization over reals. computationally more efficient approach for this to consider the joint dual of the inner optimization problem in (5).
For 71, 722 E P(R). and non-negative weights 01, az2 let
2 = inf zSy
{ {an K + 02 (1
(6)
For y R, X 82 , R2 and 72 R, let
1t 7, mn) = A + 72 |/|
1+e
B) + pi + (y xo)+ (1 - -T)
and
2 de
B) (p2 + (plv p2) (1
For xo E C. define the convex region Dzn to be collection of R, P2 R, 112 2 0, 72 2 0, and
Pi 2 O, such that for all R, (,,,, X, Y, P, xo) > 0 and hd (y. X, 7, 2 0. As we show next.
these quantities are related to the dual formulation of (6)
Proposition 3.5. For m. 722 E P(R) and weights on, 02 E 00, 1}. Z equals
min
max (ArT-))EDED
a1 anEnn (log (h" (X, 7,)) az (log (h' X, 7, P, xo))) a log a₁ 022 log 0r2 (01 + 02) log (a) + a2) (a1 + a22) log 2.
20EC
An application of above the empirical distributions (1/- (t)) weighted by sample counts, i.e., a, = (t), for a E [1,2]. results in unweighted sums over the samples. Also observe that the representation in Proposition 3.5 dimension smaller compared to that obtained by using Theorem
3.4 in (6). and hence, is faster to optimize numerically.
Recall that while KL is convex optimization problem, KL is not (see Section 2 To handle this, we use the min formulation for CVaR in 2 to turn it into one-dimensional family of lincar constraints, which appears the outer ming, in the expression in (b) in Theorem 3.4 and Proposition 3.5 above, with the range constraint from Lemma 2.1 This renders the remanining problem as a convex optimization problem. To simplify the CVaR constraint in KL
(3). Rest is the Lagrangian duality. Complete proofs for Theorem [.44 and Proposition 3.5 are given in Appendix [
The equality in Proposition 3.5 and the dual formulations in Theorem 3.4 are important statistically and computationally. First, our stopping rule will threshold the Z statistics to determine when to safely stop. So we need to bound the deviations of Z. For this, we will use the dual formulations that dominate the deviations of Z. Second, our sampling rule will sample according to the optimal proportions evaluated for the empirical distribution vector, (t)., in (5) For this, we use Proposition (35 in our experiments to solve the inner optimization problem in These will be made precise in Section 4
from Theorem 3.4 in (6) to construct mixtures of
Computing a gradient for the objective of the maximisation problem (5). seen function of the sampling weights t. takes one Z evaluation per suboptimal arm. The inner maximisation over Dz,, a constrained concave program, for which standard algorithms apply. The outer minz, problem requires different approach, as it is not even quasiconvex. Empirically it does become quasiconvex after seeing enough samples, so we employ a heuristic bisection search for which we measure the impact the error probability (there is none). Numerical results presented in Section 4.4
7

---

The algorithm
Given a bandit problem μ E M, our algorithm is specification of three things: a sampling rule, stopping rule, and a recommendation rule.
Sampling rule: At each iteration, the algorithm has access the empirical distribution vector, ji(n). first projects ((n) to C in the Kolmogorov metric, dx. using the projection map. II, defined below. It then computes t* (II (ā(n))) and allocates samples using the C-tracking rule of [27], which
state in Appendix B for completeness. The map IT (T, ....... IT), where IT: P(R) C. is given by
(1) E argmin dx dx(1, 6), where dx (7,, x) == suPZER
Fx())
We show in Appendix G that this projection has simple form and can be computed easily.
Stopping rule: We use a modification of the generalized likelihood ratio test (GLRT) (see, our stopping criterion. At any time, the vector of empirical distributions, fi(n), suggests with minimum CVaR. (empirically best-CVaak arm), say arm i. This is our null hypothesis, which test against all the alternatives. Formally, the log of the GLRT statistic, denoted by (n),, is inf Ea= N₂ (n) (L( (n), v/)) This is exactly the scaled inner optimization problem the expression of (i((n) in (4). except that (i(n) may not belong to M (recall the Z statistic defined in (6). Let (z) equal min inf 2z
(N.(n) (A: y) + N₂ (n) KL (Aa (n), x)}- equals (n)n) when ji(n) E .M (Lemma 3.1g Our stopping rule corresponds to checking
(n) 2 ((n
where ((n, 6) log ((K 1) 8) + 5 log(n 1) 1)++2 +2
Recommendation rule: After stopping, the algorithm outputs the arm with the minimum CVaR of the corresponding empirical distribution, i.e., if T is the stopping time of the algorithm, then it outputs argmin, Ca (T)..
4.1 Theoretical guarantees
For a given confidence 8, let Ta denote the stopping time for the algorithm. The algorithm makes an error if time Tg. there is an arm such that cx (āg((T)) < ( Let the error event be denoted by E. Theorem 4.1. For and js M the proposed algorithm with B(t, 8) chosen as in 77. satisfies
Eg (Ta)
P (E) 5 and
limssu 8-0
log(1/5)
V(n)
We first sketch the proof for the ô-correctness part of the theorem. Proof ideas for sample complexity are presented later in this section. The detailed proof for Theorem 4.1 can be found Appendix [F
8 ō-correctness: Recall that the algorithm makes error if at time Ts. the empirically best-CVaR arm not arm As in the best-mean arm case, it can be argued that this probability is at most
k Σ P(n: N((n) (iam))
(n) KL (pn (n), (mo)) 2 B)
See Appendix for a proof of S The following proposition will be helpful in bounding each of the summands above. Setting j I, and log K
_ in Proposition 4.2 along with 3 from (7p. we get that each summand in 88 is at most 8/(K 1). proving that the proposed algorithm is 8-correct.
Proposition 4.2. For E [K].j [K], + j, h(()) = 5 log(n + 1) + 2, and x 2 O, (3n: (n) (p.)
+ (n) KLi (n), e, (x,)) h(m) 2 x) SE
key step in proving Proposition 4.2 constructing mixtures of super-martingales that dominate the exponentials of (n) KL ( (n). (44)) and (2)n) KLL (f)(n), cr (4t)). From Theorem 3.4 a) and ( can be shown that for fixed variabais,, the objective a sum logs of random variables with mean at-most 1. Hence, its exponential is non-negative candidate super-marting super-martingale. Since we want to bound the maximum over the dual parameters, we construct mixture of these candidates, over the dual-pprre parametrrs,,,, and show that it dominates the exponential of (r(r)) KL, (p.(n), en (p:)).

---

Sample complexity: Our sample complexity proof follows that of [27] for a parametric family. However, we work with a more general non-parametric class, in which we establish continuity of the KT.pprjecctoon functionals (Lemma 3.2) Our proof also differs from that in 2 in that we only have upper-hemicontinityy of the set of optimal sampling allocations (t*) (Lemma (.3). A nuance in our analysis is that the empirical distribution may not belong to the class L. in which case we project the empirical distribution onto that class, and the sampling rule uses this projected distribution to compute 6*, Our careful choice of the projection map aids in the proof of this result.
The computational cost of these KI-projection functionals, and hence, that of the oracle weights, is linear in the number of samples taken (see, 2 16 30)). As result, the overall run- unntimmein is quadratic in TG. We propose modification in which we update the weights only at geometrically spaced times. This modification improves the computational
Computational complexity:
to almost linear in T8, while its sample complexity optimal up to a multiplicative constant depending on the choice of geometrical-spacing factor, thus providing a controlled trade-off between the two costs. Recently, propose a similar yet different "'oubling" trick the regret-minimization setting. However, our approach differs from theirs in that our update-times for weights are not random. We refer the reader to Appendix for details of the algorithm and proofs for its theoretical guarantees.
K
Mean-CVaR problem: We now extend the methodology for the CVaR problem to the more general mean-CVaR problem. For a distribution 17. E L (for example, a random loss a financial investment), the metric associated with the "badness" of a distribution is a: (n) + aggCn (17), for a1 > 0 and Q2 > 0, and the best-arm is the one with minimum value of this conic combination of mean and CVaR. For 01 O this is the CVaR-problem, which we have studied in this work. For 02 0, this is the mean-problem, extensively studied in 27
As in D.. we can define corresponding KL-projection funcciooals,, with the CVaR constraints replaced with those on the modified metrie. The above theory, with this updated KL and KL gives the corresponding results for this setting. In particular, the lower bound on IE (Tx) for d-correct algorithms for mean-CVan CVaR BAI given by V (n)² log 1. where V (n) is defined in (5) with the updated KLu, and KT
Theorem 4.3 (Informal). For μ M the proposed algorithm for CVaR, with KL and KL defined with mean-CVat constraints instead, is 6-correct and asymptotically optimal.
The proof of this theorem parallels that for CVaR above. We give the formal statement with proof- details in Appendix !
4.2 The VaR problem
In this section we present the main ideas for an analogous approach for the optimum VaR-problem Here, we will not impose any conditions (viz. membership in L) on the arm-distributions. as the VaR lower bound is defined without it, i.e., arm distributions are allowed be arbitrary probability measures on R. For a probability measure n,, let (v), denote its CDF evaluated at y and F,, (v) lim.to (2) denote the left limit of the CDF. Moreover, for r. E (0. 1) let de(r, q) denote the KL divergence between the Bernoulli random variables with mean r and q. For y E R, let K v) and KL (1. y) be defined as in ( with VaR constraints, instead. These simplify as follows.
Lemma 4.4. L (7, v) d2 (min (F,(z), m) x) and KL (n) 8) dz(max (F, (y), x) .).
Unlike in the problem, we show that KL and KL for the VaR problem are not jointly continuous functionals (see Remark H.2p. The discontinuity occurs at y being the jump points of F,, in Lemma above. However, we prove in Appendix [ (Corollary H.3.1) that the set of optimal proportions, l", is still upper-hermicontinuuss and convex.
The algorithm for CVaR with KL and KL replaced by those in the lemma above, and setting
t + log 5 + 8log 8(t, 8) 6 log 1 + log
K -
K -
[ + log
2
8
we get our algorithm for the VaR-problem. Theorem 4.5 (Informal). The proposed algorithm for the VaR VaR-problem is 8-correct and asymptotically optimal.
We refer the reader to Appendix H for a detailed discussion of the VaR-problem and proofs.

---

4.3 Tight -aase confidence intervals for CVaR
We now present tight mytime-valid confidence interval for the CVaR of a distribution in Let fin denote the empirical distribution corresponding to samples from 'i E L. Our proposed upper (Un) and lower (In) confidence intervals for 67 are of the form Un = max {a E R : (fm, .) - C and Ln = min { R n fa x) - C} for an appro- priately chosen threshold C' = log 8-1 + 3lg n. Similar confidence intervals for the mean of heavy- tailed distributions were proposed in [3. Let 2 denote the nhhh quantile for in. Recall that the pop- ular suncation-based estimator for en (17) is given by & =
E; X,1(@x,n S X, S un). for appropriately chosen truncation levels, Un (see, (3).. Observe that there are sources of error in this estimator, first, the estimation of the quantile, and second, the estimation of the tail-expectation. On the other hand, our confidence intervals do not rely on estimation of the true quantile, Zx. In Appendix ! we show that even given the correct estimation of R confidence intervals for ट,, perform poorly compared to those based on KL inf and KL in some applications.
4.4 Numerical Results
This is only a brief teaser section on the experiments, which are detailed in Appendix L We are interested in the question whether the asymptotic sample complexity result of Theorem 4.1 is representative at reasonable confidence levels 8. Whether this the case or not differs greatly between pure exploration setups: [27 see state-of-the-art numerical results in Bernoulli arms for Track-and- ank-Stop with 0.1, while (22) present a Minimum Threshold problem instance where the Track-and-Ster asymptotics have not kicked in yet at 10-20, 20, Our experiments confirm that our approach is indeed practical at moderate confidence 8.
In our experiments we implement version of Track-and-Stop including C-tracking and forced exploration and apply Fisher-Tippa Tippett (F(H, a, ?)), Pareto (P(p, a, 7)), and mixtures of Fisher- Tippett arms (these heavy-tailed distributions arise in extreme value theory).
Figure D shows the distribution of the stopping time as function of 8 in a synthetic three-arm task: arm 1 is a uniform mixture of F(-1,0.5, 0.5, 0.4) and F(-3, 0.5, -0.4), arm 2 is P(O, 0.2, 0.55) and arm 3 is F(-0.5, 1, 0.1) with respective CVaRs at quantile π = 0.6 being- -..1428,
5
0.01
0.03
0,001
0,0001
fraction of ruurs
0oc2
0.974 and 1.547. We select = 0.7
and B = 4.5. This is moderately hard problem of complexity (n) 49.7. We conclude that even at mod- crate the average sample complcxity closely matches the lower bound, espe- cially after adjusting it for the lower- order terms in the employed stopping threshold i(n, 5). This demonstrates that our asymptotic optimality is in fact indicative of the performance in prac- tice.
0001
0003
300 1000 1500
Figure 1: Histogram of stopping times among 1000 runs 3 arms, as function of confidence 8. Vertical bars (solid) indicate the lower bound (4), and (dashed) version adjusted our stopping threshold 7 i.c., the n that solves n = [r, V) (p))
We do additional experiments to show the dependence of the algorithm's 's performance on the number of arms and the input parameter B. We see that the average stopping time of our algorithm increases linearly in the number of arms. Moreover, the sample complexity is sensitive to B, indicating the importance of correctly estimating it. We refer to Appendix D for details of these experiments.
Conclusion: We developed asymptotically optimal algorithms that identify the arm with the minimum risk, measured in terms of CVaR, VaR, or conic combination of mean and CVaR. Our algorithms operate in naramerrer settings with possibly heavy-tailes distributions. Although similar plug-and-play algorithms have been developed in simpler settings, our algorithms for tail-risk measures require more nuanced analysis. The techniques developed may be generalizable to a much broader class of problems.
10

---

Acknowledgments and Disclosure of Funding
We acknowledge the support of the Department of Atomic Energy, Government of India, to TIFR under project no. RT14001.
References
[1] S. Agrawal and N. Goyal. Further optimal regret bounds for thompson sampling. In Artificial intelligence and statistics, pages 99-107. PMLR, 2013.
[2] S. Agrawal, S. Juneja, and P. Glynn. Optimal 6-correct best-arm selection for heavy-tailed distributions. Proceedings of the 31st International Conference on Algorithmic Learning Theory, volume 117 of Proceedings of Machine Learning Research, pages 61-110. PMLR, 08 Feb- Feb 2020.
[3] S. Agrawal, S. K. Juneja, and W. M. Koolen. Regret minimization in heavy-tailed bandits. In Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 26-62. PMLR, 15-19 Aug 2021.
[4] E. Arıkan and J. Fichtinger. The risk-averse newsvendor problem under spectral risk measures: A classification with extensions. European Journal of Operational Research, 256(1):116-125 2017.
[5] P. Artzner, F. Delbaen, J.-M. Eber, and D. Heath, Coherent measures of risk. Mathematical finance, 9(3):203-222 1999.
[6] J.-Y. Audibert and S. Bubeck. Best arm identification in multi-armed bandits. In COLT-23th Conference on Learning Theory-2010, pages 13-p p. 2010.
[7] P. Auer, N. Cesa-Bianchi, and P. Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47(2):33--256, May 2002.
[8] C. Berge. Topological Spaces: Including a Treatment of Multi-valuee Functions, Vector Spaces, and Convexity. Dover books mathematics. Dover Publications, 1997.
[9] Billingsley, Convergence of Probability Measures. Wiley Series in Probability and Statistics. Wiley, 2013.
[10] A. Blum and A. Kalai, Universal portfolios with and without transaction costs. Proceedings of the Tenth Annual Conference Computational Learning Theory, pages 309-313. ACM, 1997.
[11] S. Boyd and L. Vandenberghe. Convex optimization. Cambridge university press, 2004.
[12] Bubeck. N. Cesa-Bianchi, et al. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends in Machine Learning, 5(1):1-122, 2012.
[13] Bubeck, N. Cesa-Bianchi, and G. Lugosi. Bandits with heavy tails. IEEE Transactions on Information Theory, 197117,77117771, 2013.
[14] S. Bubeck, R. Munos, and G. Stoltz. Pure exploration in finitely-armed and continuous-armed bandits. Theor. Comput. Sci., 1822119):83221188 2011.
[15] A. N. Burnetas and M. N. Katehakis. Optimal adaptive policies for sequential allocation problems. Advances in Applied Mathematics, 17(2):122 - 142, 1996.
[16] O. Cappé, A. Garivier, O.-A. Maillard, R. Munos, G. Stoltz, et al. Kullback-Leible upper confidence bounds for optimal sequential allocation. The Annals of Statistics, 1165),111-1151, 2013.
[17] H. Chernoff. Sequential design of experiments. The Annals of Mathematical Statistics, 30(3):755-770, 1959.

---

[18] Y. David and N. Shimkin. Pure exploration for max-qu mua--uuatile bandits. In Machine Learning and Knowledge Discovery Databases, pages 556-571- 066-571.20 Springer International Publishing, 2016.
[19] L. De Haan and A. Ferreira. Extreme value theory: an introduction. Springer Science & Business Media, 2007.
[20] V. H. de la Pena, M. J. Klass, and T. L. Lai. Self-normalized processes: exponential inequalities, moment bounds and iterated logarithm laws. Annals of probability, pages 1902-1933, 2004.
[21] R. Degenne and W. M. Koolen. Pure exploration with multiple correct answers. In Advances in Neural Information Processing Systems 32, pages 14591-14600, 2019.
[22] R. Degenne, M. Koolen, and P. Ménard. aon-asymptotie pure exploration by solving games. In Advances in Neural Information Processing Systems 32, pages 14492-14500) 2019.
[23] A. Dembo and O. Zeitouni. Large deviations techniques and applications. corrected reprint of the second (1998) edition. stochastic modelling and applied probability, 38, 2010.
[24] H. Even-Dar, M. Kearns, and J. Wortman. Risk-sensitive online learning. In J. L.. Balcázar, P. M. Long, and F. Stephan, editors, Algorithmic Learning Theory, pages 199-213, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg.
[25] E. Even-Dar S. Mannor, and Y. Mansour. Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. Journal of machine learning research, 7(Jun):009- 1109, 2006.
[26] V. Gabillon, M. Ghavamzadeh, and A. Lazaric. Best arm identification: A unified approach to fixed budget and fixed confidence. In Advances in Neural Information Processing Systems, pages 3212-3220, 2012.
[27] A. Garivier and E. Kaufmann. Optimal best arm identification with fixed confidence. In Conference on Learning Theorry pages 998-1027, 2016.
[28] W. Glynn, A. Zeevi, et al. Bounding stationary expectations of markov processes. Markov processes and related topics: Festschrift for Thomas G. Kurtz, pages 195-214, Institute of Mathematical Statistics, 2008
[29] E. Hazan, A. Agarwal, and S. Kale. Logarithmic regret algorithms for online convex optimiza- tion. Mach. Learn., (9(2-3):169-19)) 2007.
[30] J. Honda and A. Takemura. Non-asymptotic analysis of a new bandit algorithm for semi- bounded rewards. The Journal of Machine Learning Research, 16(1):3721-3756, 2015.
[31] I. J. Hong, Z. Hu, and Liu. Monte carlo methods for value-at-risk and conditional value- at-risk: review. ACM Transactions Modeling and Computer Simulation (TOMACS), 24(4):1-37, 2014.
[32] S. R. Howard and A. Ramdas. Sequential estimation of quantiles with applications to A/B-testing and best-arm identification. arXiv preprint arXiv:/906.09712. 2019.
[33] K. Jamieson, M. Malloy, R. Nowak, and S. Bubeck. UII An optimal exploration algorithm for multi-armed bandits. In Conference on Learning Theory, pages 423-439, 2014.
[34] S. Juneja and S. Krishnasamy. Sample complexity of partition identification using multi-armed bandits. In Proceedings of the Chirty-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 1824-1852 PMLR, 25-28 Jun 2019.
[35] A. Kagrecha, J. Nair, and K. Jagannathan. Distribution oblivious, risk awar algorithms for multi-armed bandits with unbounded rewards. In Advances in Neural Information Processing Systems 32, pages 1 11272-11281. Curran Associates, Inc., 2019.
[36] S. Kalyanakrishnan, A. Tewari, P. Auer, and P. Stone. PAC subset selection in stochastic multi-armed bandits. In ICML, volume 12, pages 655-662 2012.
12

---

[37] E. Kaufmann, O. Cappé, and A. Garivier. On the complexity of best-arm identification in bandit models. The Journal of Machine Learning Research, 17(1):1 2016.
[38] E. Kaufmann and W. M. Koolen. Mixture martingales revisited with applications to sequential tests and confidence intervals. arXiv preprint 1.1iv::811.1111 1419, 2018.
[39] L.A., K. Jagannathan, and R. Kolla. Concentration bounds for CVaR estimation: The cases of light-tailed and heavy-tailed distributions. In H. D. III and A. Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 5577-5586. PMLR, 13-18 Jul 2020.
[40] Lattimore and C. Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[41] D. Luenberger. Optimization by Vector Space Methods. Series in Decision and Control. Wiley,
1969.
[42] O.-A. Maillard. Robust risk-averse stochastic multi-armed bandits. In S. Jain, R. Munos, F. Stephan, and T. Zeugmann, editors, Algorithmic Learning Theory, pages 218-233, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg.
[43] S. Mannor and J. N. Tsitsiklis. The sample complexity of exploration in the multi-armet bandit problem. Journal of Machine Learning Research, 5(Jun):623-648, 2004.
[44] H. Markowitz. Portfolio selection. The Journal of Finance, 7(1):77-91, 1952.
[45] E. Posner. Random coding strategies for minimum entropy. IEEE Transactions on Information Theory, 2184)338--311 1975.
[46] R. T. Rockafellar. Coherent approaches to risk in optimization under uncertainty. In OR Tools and Applications: Glimpses of Future Technologies, pages 38 28. Informs, 2007.
[47] R. T. Rockafellar and S. Uryasev. Conditional value-at-risk for general loss distributions. Journal of banking & finance, 26(7):1443-1477 2002.
[48] R. T. Rockafellar, S. Uryasev, et al. Optimization of conditional value-at-risk. Journal of risk, 1-21-42,77 2000.
[49] A. Sani, A. Lazaric, and R. Munos. Risk-aversion in multi-armes bandits. In F. Pereira, J. Burges, L. Bottou, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 25. Curran Associates, Inc., 2012.
[50] S. Sarykalin, G. Serraino, and S. Uryasev. Value-at-risk vs. conditional value-at-risk in risk management and optimization. In State-of-the-art decision-making tools in the information- intensive age, pages 770-294, Informs, 2008
[51] T. Sawik. Optimization of cost and service level in the presence of supply chain disruption risks: Single multiple sourcing. Computers amd Operations Research, 51:11 2200 2014.
[52] R. K. Sundaram. A First Course in Optimization Theory. Cambridge University Press, 1996.
[53] W. R. Thompson. On the likelihood that one unknown probability exceeds another view of the evidence of two samples. Biometrika, 25(3/4):285-29 294, 1933.
[54] H. Victor et al. A general class of exponential inequalities for martingales and ratios. Annals of probability, 27(1):537-564 1999.
[55] J. Ville. Etude critique de la notion de collectif. Bull. Amer. Math. Soc, 45(11):824, 1939.
[56] M. Warmuth and D. Kuzmin. Online variance minimization. In Lugosi and U. Simon, editors, Learning Theory, pages 514-528, Berlin, Heidelberg. 2006. Springer Berlin Heidelberg.
[57] D. Williams. Probability with martingales. Cambridge university press, 1991.
[58] R. Williamson and A. K. Menon. Fairness risk measures. arXiv preprint arXiv: 1051::9901.0660 2019.
[59] Y. Yu and E. Nikolova. Sample complexity of risk-averse bandit-arm selection. In Twenty- Third International Joint Conference on Artificial Intelligence, 2013.
13


Reviews:
[{"review_id": "v6tqkymSM2K", "reviewer": "Reviewer_rZt1", "summary": "The paper considers best CVaR arm identification in a fixed confidence setting. They can also deal with conic combinations of mean and CVaR, as well as VaR based criteria.\n\nMain contributions include a lower bound which involves optimization over reals, and an algorithm which is asymptotically optimal in terms of expected sample complexity.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper considers the CVaR optimisation problem in a multi-armed bandit setting. Similar works exist in the context of mean [2] and for fixed budget best CVaR arm[39]. However, the CVaR optimisation problem over the distribution space L^K involves more intricate analysis. This paper carries out an involved analysis for obtaining the explicit KL characterisation of the lower bound. The authors also propose an algorithm that meets the lower bound asymptotically as the confidence δ goes to zero. Numerical results indicate that the average sample complexity matches the lower bound well at moderate values of δ.\n\nOverall, the paper studies a problem which has been studied a lot in the recent years, but proposes a sophisticated analysis technique which is worth recording and could be reusable for other settings.\n\nCould similar techniques be used for other convex risk measures? For example, utility based shortfall?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No major societal impact", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "saOzEWMVCc", "reviewer": "Reviewer_Gtxo", "summary": "This paper addresses the multi-armed bandit best arm identification problem which aims to identify the arm with the minimum tail risk measured by VaR, CVaR, or a weighted sum of CVaR and the mean. It proposes an optimal $\\delta$-correct algorithm that works with a mild restriction on the arm distributions for CVaR and works with any arm distributions for VaR. In particular, the paper develops a lower bound for the problem and shows that the proposed optimal $\\delta$-correct algorithm has the sample complexity that matches the lower bound asymptotically (as $\\delta \\rightarrow 0$). Additionally, the paper also suggests a solution to control the trade-off between the time computational complexity and the sample complexity, which is useful in practical applications.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper makes an important contribution to the multi-armed bandit best arm identification problem by considering 3 risk measures: VaR, CVaR, and a weighted sum of CVaR and the mean (mean-CVaR), all of which are well-motivated in the introduction. The proposed optimal $\\delta$-correct algorithm is capable of handling a large class of arm distributions (with only mild assumption when the risk measure is CVaR and mean-CVaR). Moreover, its sample complexity exactly matches the lower bound as $\\delta \\rightarrow 0$. I think it is a good paper, so I tend towards acceptance. There are only several minor questions as follows:\n1. What are the advantages/disadvantages between existing solutions in the ($\\epsilon$,$\\delta$)-PAC setting and the proposed optimal $\\delta$-correct algorithm in this paper, e.g., how large $\\epsilon$ should be such that existing PAC solutions are more favourable than the proposed algorithm in terms of sample complexity/computational complexity?\n2. When the arm distributions are parametric but not from canonical SPEF, what are the implications when we apply the proposed algorithm (which is designed for non-parametric arm distributions)? For example, the knowledge of the parametric arm distribution may not be fully utilized.\n3. I think that paper will be easier to read for people without much background if references and some brief explanations are included. For example, including a brief explanation of the intuition behind $KL_{\\inf}^{U}$ and $KL_{\\inf}^{L}$ in equation (1); references in lines 189-190 and 413-414; more details in lines 278-280; the derivation of equation (4) (or mentioning the specific chapter in the book [40]); the derivation of the GLRT in line 294. \n4. Why are there only heavy-tailed arm distributions in the experiments? Maybe the experiments with light-tailed arm distributions should also be demonstrated.\n5. The experiments in figure 3 in Appendix K contain arm distributions whose CVaR values are quite far apart (-0.1428 vs. 2.4439), so I suspect it is easy for the algorithm to identify the best arm with a small sample complexity in this case. Thus, the linear relationship between the empirical sample complexity and the number of arms will be more persuasive if we consider similar arm distributions as those in Figure 2 where the sample complexity is roughly 200 for $\\delta = 0.1$ and only $3$ arms (compared with figure 3 where the sample complexity is only around 150 for $\\delta = 0.05$ and $20$ arms).\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "24"}, "extra_text": {}}, {"review_id": "a6QQlSAU_ay", "reviewer": "Reviewer_w1AF", "summary": "The paper studies the problem of identifying the arm with the minimum CVaR, VaR, or a conic combination of the mean and CVaR. It provides an \\delta-correct algorithm that operates on possibly heavy-tailed arm distributions and matches the asymptotic lower bound on the expected number of samples needed as delta approaches 0. The paper also provides a result of separate interests, i.e., an anytime-valid confidence interval for CVaR estimation, which is tighter than truncation-based intervals (under certain conditions). Finally, the empirical studies show that the asymptotic sample complexity result of the proposed algorithm is indicative of its performance in practice. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The authors have provided a clear exposition of the motivation and the theoretical results of the work. In particular, the KL_inf-based anytime-valid confidence intervals for CVaR are (to the best of my knowledge) very novel. In addition, the empirical results show that the asymptotic optimality of the proposed algorithm is indicative of the performance of the algorithm in practice. \n\n- In general, the paper will benefit from more detailed discussions on interpreting some of the defined quantities (especially the ones defined in L235-239 for the dual formulation and the ones defined in L252-256). In their current forms, the readers are hard to gain intuitions on them. \n- Could the authors comment on differences between this paper and \"Statistically Robust, Risk-Averse Best Arm Identification in Multi-Armed Bandits\" (https://arxiv.org/pdf/2008.13629.pdf)? \n- Empirically, what is the performance of the algorithm for identifying the best arm under VaR? \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, the authors have adequately discussed the limitations and societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 hours"}, "extra_text": {}}, {"review_id": "Z4W6fO8nX0X", "reviewer": "Reviewer_1ikr", "summary": "The paper studies the problem of identifying the arm with smallesst CVaR and VaR. The lower bound for the specific structured best-arm identification problem is studied. The paper also proposed an algorithm that achieves asymptotic optimality in sample size. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper provides asymptotically matching upper and lower bounds for the best-arm identification methods for CVaR and VaR etc. I appreciate the efforts the authors have made for organizing all the content. However, the presentation and clarity of the paper are the major obstacles for understanding the whole paper, along with some technical incorrectness and ambiguity. I'm listing all my concerns as below:\n\n1. Although it might be trivial, it's indeed unclear to me how standard arguments in best arm identification lead to Equation (4) and (8). First, it is better to indicate where the equations come from in the standard references. For example, (4) seems to come from a direct result of Theorem 33.5 in [1]. However, even with the results there, it is unclear why the results of best arm identification can be directly applied to a different problem of identifying the arm with smallest CVaR and VaR. It would be better if the authors can make the proof of (4) and (8) explicit.\n\n2. Furthermore, Equation (4) and (8) make me even confused since they're suggesting that the problem of identifying the arm with smallest CVaR is exactly the same as the original best-arm identification problem in both upper and lower bounds. And the follow-up analysis (Lemma 3.1) is mostly simplification that does not depend on the structure of CVaR. If (4) and (8) turns our to be a simple application of the known result, it would be better if the authors can be clear on their own technical contributions.\n\n3. With the above point said, I believe one of the most important contribution of this paper is a statistically and (maybe) computationally efficient algorithm. However, the proof in Appendix F appears to be wrong. In particular, the authors only show that $G_z$ has its $(1+\\epsilon)$ moment bounded. However, the authors fail to show that among all the distributions that has moment bound, the way $G_z$ moves the mass is the optimal way such that $d_K(F, G_z)$ is minimized. Indeed, this is definitely wrong: the authors suggest that one shall move the mass on the left and right tail equally to point 0. However, in a highly asymmetric distribution, it would incur a much smaller distance if we only move one side of the mass that has a really long tail. The authors also didn't discuss whether the step of stopping rule is computationally efficient or not. \n\n4. There are many ambiguities in the paper that is not rigorously defined, which makes it hard to understand the paper. My suggestions for improving the presentation of the paper are listed as below:\n\n(a). In Section 4 when you describe the algorithm, it is better to write it in a formal algorithmic environment and be explicit on all the procedures. It is unclear to me how 'any reasonable tracking rule' are applied, how 'empirically-minimal CVaR arm' are selected. These might appear trivial but are not rigorously defined. One shall replace the languages there with equations. \n\n(b). Similar issues also happen in other places, e.g. the notation $\\mathcal{\\epsilon}$ in line 301, the notation $\\mathcal{L}$ in line 285 (although it is defined as the set of moment bounded distributions in introduction, later it is also used to refer to any set of distributions in line 150 and 199 etc.), and the notion of $\\delta$-correctness in the paper. \n\n\n\n[1] Lattimore, Tor, and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.\n\n\n**Update based on author responses:\n\nThe authors resolved the questions I had and the proof of Lemma F.1 looks good to me after the clarification. I have adjusted the score accordingly.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "91eACLQ6eV", "reviewer": "Reviewer_sUiJ", "summary": "The authors study the problem of multi armed bandits with the goal of identifying the arm with smallest (i) CVaR (ii) VaR or (iii) conic combination of CVaR and mean. This problem has applications in finance and clinical trials and captures a notion of risk sensitivity towards undesirable outcomes. The authors show that in the parametric case where the arm reward distributions follow a canonical SPEF, the problem reduces to best arm identification.\n\nThe authors study the VaR problem without any assumptions on the distributions, and study the CVaR problem assuming that distributions satisfy bounded $(1+\\epsilon)$ moments. The proposed algorithm projects the empirical distribution to the considered family of distributions and considers an exploratory transform that guides the arm sampling distribution. At each time the empirical reward distribution suggests an arm with empirical minimum CVaR - this is the null hypothesis which is tested against all alternatives using GLRT. The algorithm upon satisfying the termination condition outputs the arms with the empirical minimum CVaR.\n\nThe authors show that the proposed algorithm asymptotically achieves the optimal sample complexity as the error threshold $\\delta \\to 0$.\nThe results are supported by numerical simulations demonstrating good performance on instances with Bernoulli arms. The performance of the algorithm hinges on the asymptotic convergence of the track-and-stop exploration protocol which is often fast even when the error parameter delta is moderate.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall the paper is well written and discusses prior work in sufficient detail, to the best of my knowledge. The considered notion of CVaR and VaR minimization have been studied in prior work, but the optimal rates have not been established for any regime of error tolerance, $\\delta$ until this paper. I think this paper presents an important stepping stone towards exactly characterizing the minimax rates in best arm identification problems beyond the standard notion of mean. The algorithm presented in the paper is new and its proof uses novel analytical tools, which are of independent value.\n- The only suggestion I can provide in terms of the writing of the paper is: it might help to define the CVaR and VaR problems informally in the introduction instead of referring the reader to Section 2. The contents of the introduction would be more interpretable that way.\n- In financial settings, I can imagine more than best arm identification (which may take exponentially long in K if the gap is small), regret minimization with stochastic / adversarially chosen rewards is also of interest. Does the analysis here provide any intuition as to what to expect for the regret minimization setting as $T\\to\\infty$?\n- Are there instances where the best arm and the arm with minimum CVaR are very different from each other? This would provide more justification for proposing algorithms specific for CVaR minimization and mean-CVaR minimization.\n- Is there any intuition about the tightness of the algorithm in the non-asymptotic regime? It might help to include a discussion in the body of the paper as to the challenges of extending to the case when delta does not $\\to 0$.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, I believe the authors have sufficiently addressed such concerns", "review_text": "", "extra_scores": {"ethical_concerns": "None to the best of my knowledge", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the multi-armed bandit problem with the goal of identifying the arm with the smallest CVaR/VaR/conic combination of CVaR and the mean. It is a significant question with applications in various domains. This paper proposes an algorithm that projects the empirical distribution to the considered family of distributions and considers an exploratory transform that guides the arm sampling distribution. It shows that the algorithm asymptotically achieves the optimal sample complexity. I agree with the reviewers that this paper has made interesting technical contributions and I am happy to recommend acceptance. 
Decision: Accept (Poster)