summaries: 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.  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.  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.  The 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.  The authors show that the proposed algorithm asymptotically achieves the optimal sample complexity as the error threshold $\delta \to 0$. The 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. 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. 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.  Main contributions include a lower bound which involves optimization over reals, and an algorithm which is asymptotically optimal in terms of expected sample complexity.
abstractText: 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, safetycritical 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 δ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 δ approaches 0). The algorithm requires solving a non-convex optimization problem in the space of probability measures, that requires delicate analysis. Enroute, we develop new non-asymptotic, anytime-valid, empirical-likelihood-based concentration inequalities for tail-risk measures.
authors.name: Shubhada Agrawal
authors.name: Wouter M. Koolen
authors.name: Sandeep Juneja
references.authors: S. Agrawal N. Goyal
references.title: Further optimal regret bounds for thompson sampling
references.venue: Artificial intelligence and statistics, pages 99–107. PMLR,
references.authors: S. Agrawal S. Juneja P. Glynn
references.title: Optimal δ-correct best-arm selection for heavy-tailed distributions
references.venue: Proceedings of the 31st International Conference on Algorithmic Learning Theory, volume 117 of Proceedings of Machine Learning Research, pages 61–110. PMLR, 08 Feb–11 Feb
references.authors: S. Agrawal S.K. Juneja W.M. Koolen
references.title: Regret minimization in heavy-tailed bandits
references.venue: Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 26–62. PMLR, 15–19 Aug
references.authors: E. Arıkan J. Fichtinger
references.title: The risk-averse newsvendor problem under spectral risk measures: A classification with extensions
references.venue: European Journal of Operational Research, 256(1):116–125,
references.authors: P. Artzner F. Delbaen J.-M. Eber D. Heath
references.title: Coherent measures of risk
references.venue: Mathematical finance, 9(3):203–228,
references.authors: J.-Y. Audibert S. Bubeck
references.title: Best arm identification in multi-armed bandits
references.venue: COLT-23th Conference on Learning Theory-2010, pages 13–p,
references.authors: P. Auer N. Cesa-Bianchi P. Fischer
references.title: Finite-time analysis of the multiarmed bandit problem
references.venue: Machine Learning, 47(2):235–256, May
references.authors: C. Berge
references.title: Topological Spaces: Including a Treatment of Multi-valued Functions, Vector Spaces, and Convexity
references.venue: Dover books on mathematics. Dover Publications,
references.authors: P. Billingsley
references.title: Convergence of Probability Measures
references.venue: Wiley Series in Probability and Statistics. Wiley,
references.authors: A. Blum A. Kalai
references.title: Universal portfolios with and without transaction costs
references.venue: Proceedings of the Tenth Annual Conference on Computational Learning Theory, pages 309–313. ACM,
references.authors: S. Boyd L. Vandenberghe
references.title: Convex optimization
references.venue: Cambridge university press,
references.authors: S. Bubeck N. Cesa-Bianchi
references.title: Regret analysis of stochastic and nonstochastic multi-armed bandit problems
references.venue: Foundations and Trends® in Machine Learning,
references.authors: S. Bubeck N. Cesa-Bianchi G. Lugosi
references.title: Bandits with heavy tails
references.venue: IEEE Transactions on Information Theory, 59(11):7711–7717,
references.authors: S. Bubeck R. Munos G. Stoltz
references.title: Pure exploration in finitely-armed and continuous-armed bandits
references.venue: Theor. Comput. Sci., 412(19):1832–1852,
references.authors: A.N. Burnetas M.N. Katehakis
references.title: Optimal adaptive policies for sequential allocation problems
references.venue: Advances in Applied Mathematics, 17(2):122 – 142,
references.authors: O. Cappé A. Garivier O.-A. Maillard R. Munos G. Stoltz
references.title: Kullback–Leibler upper confidence bounds for optimal sequential allocation
references.venue: The Annals of Statistics,
references.authors: H. Chernoff
references.title: Sequential design of experiments
references.venue: The Annals of Mathematical Statistics, 30(3):755–770,
references.authors: Y. David N. Shimkin
references.title: Pure exploration for max-quantile bandits
references.venue: Machine Learning and Knowledge Discovery in Databases, pages 556–571. Springer International Publishing,
references.authors: L. De Haan A. Ferreira
references.title: Extreme value theory: an introduction
references.venue: Springer Science & Business Media,
references.authors: V.H. de la Pena M.J. Klass T.L. Lai
references.title: Self-normalized processes: exponential inequalities, moment bounds and iterated logarithm laws
references.venue: Annals of probability,
references.authors: R. Degenne W.M. Koolen
references.title: Pure exploration with multiple correct answers
references.venue: Advances in Neural Information Processing Systems 32, pages 14591–14600,
references.authors: R. Degenne W.M. Koolen P. Ménard
references.title: Non-asymptotic pure exploration by solving games
references.venue: Advances in Neural Information Processing Systems 32, pages 14492–14501,
references.authors: A. Dembo O. Zeitouni
references.title: Large deviations techniques and applications
references.venue: corrected reprint of the second (1998) edition. stochastic modelling and applied probability, 38,
references.authors: E. Even-Dar M. Kearns J. Wortman
references.title: Risk-sensitive online learning
references.venue: J. L. Balcázar, P. M. Long, and F. Stephan, editors, Algorithmic Learning Theory, pages 199–213, Berlin, Heidelberg,
references.authors: E. Even-Dar S. Mannor Y. Mansour
references.title: Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems
references.venue: Journal of machine learning research, 7(Jun):1079–1105,
references.authors: V. Gabillon M. Ghavamzadeh A. Lazaric
references.title: Best arm identification: A unified approach to fixed budget and fixed confidence
references.venue: Advances in Neural Information Processing Systems, pages 3212–3220,
references.authors: A. Garivier E. Kaufmann
references.title: Optimal best arm identification with fixed confidence
references.venue: Conference on Learning Theory, pages 998–1027,
references.authors: P.W. Glynn A. Zeevi
references.title: Bounding stationary expectations of markov processes. In Markov processes and related topics: a Festschrift for Thomas G. Kurtz, pages 195–214
references.venue: Institute of Mathematical Statistics,
references.authors: E. Hazan A. Agarwal S. Kale
references.title: Logarithmic regret algorithms for online convex optimization
references.venue: Mach. Learn., 69(2-3):169–192,
references.authors: J. Honda A. Takemura
references.title: Non-asymptotic analysis of a new bandit algorithm for semibounded rewards
references.venue: The Journal of Machine Learning Research, 16(1):3721–3756,
references.authors: L.J. Hong Z. Hu G. Liu
references.title: Monte carlo methods for value-at-risk and conditional valueat-risk: a review
references.venue: ACM Transactions on Modeling and Computer Simulation (TOMACS), 24(4):1–37,
references.authors: S.R. Howard A. Ramdas
references.title: Sequential estimation of quantiles with applications to A/B-testing and best-arm identification
references.venue: arXiv preprint arXiv:1906.09712,
references.authors: K. Jamieson M. Malloy R. Nowak S. Bubeck
references.title: lil’UCB: An optimal exploration algorithm for multi-armed bandits
references.venue: Conference on Learning Theory, pages 423–439,
references.authors: S. Juneja S. Krishnasamy
references.title: Sample complexity of partition identification using multi-armed bandits
references.venue: Proceedings of the Thirty-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 1824–1852. PMLR, 25–28 Jun
references.authors: A. Kagrecha J. Nair K. Jagannathan
references.title: Distribution oblivious, risk-aware algorithms for multi-armed bandits with unbounded rewards
references.venue: Advances in Neural Information Processing Systems 32, pages 11272–11281. Curran Associates, Inc.,
references.authors: S. Kalyanakrishnan A. Tewari P. Auer P. Stone
references.title: PAC subset selection in stochastic multi-armed bandits
references.venue: ICML, volume 12, pages 655–662,
references.authors: E. Kaufmann O. Cappé A. Garivier
references.title: On the complexity of best-arm identification in multi-armed bandit models
references.venue: The Journal of Machine Learning Research, 17(1):1–42,
references.authors: E. Kaufmann W.M. Koolen
references.title: Mixture martingales revisited with applications to sequential tests and confidence intervals
references.venue: arXiv preprint arXiv:1811.11419,
references.authors: P.L.A K. Jagannathan R. Kolla
references.title: Concentration bounds for CVaR estimation: The cases of light-tailed and heavy-tailed distributions
references.venue: Proceedings of the 37th International Conference on Machine Learning,
references.authors: T. Lattimore C. Szepesvári
references.title: Bandit algorithms
references.venue: Cambridge University Press,
references.authors: D. Luenberger
references.title: Optimization by Vector Space Methods
references.venue: Series in Decision and Control. Wiley,
references.authors: O.-A. Maillard
references.title: Robust risk-averse stochastic multi-armed bandits
references.venue: S. Jain, R. Munos, F. Stephan, and T. Zeugmann, editors, Algorithmic Learning Theory, pages 218–233, Berlin, Heidelberg,
references.authors: S. Mannor J.N. Tsitsiklis
references.title: The sample complexity of exploration in the multi-armed bandit problem
references.venue: Journal of Machine Learning Research, 5(Jun):623–648,
references.authors: H. Markowitz
references.title: Portfolio selection
references.venue: The Journal of Finance, 7(1):77–91,
references.authors: E. Posner
references.title: Random coding strategies for minimum entropy
references.venue: IEEE Transactions on Information Theory, 21(4):388–391,
references.authors: R.T. Rockafellar
references.title: Coherent approaches to risk in optimization under uncertainty
references.venue: OR Tools and Applications: Glimpses of Future Technologies, pages 38–61. Informs,
references.authors: R.T. Rockafellar S. Uryasev
references.title: Conditional value-at-risk for general loss distributions
references.venue: Journal of banking & finance, 26(7):1443–1471,
references.authors: R.T. Rockafellar S. Uryasev
references.title: Optimization of conditional value-at-risk
references.venue: Journal of risk,
references.authors: A. Sani A. Lazaric R. Munos
references.title: Risk-aversion in multi-armed bandits
references.venue: F. Pereira, C. J. C. Burges, L. Bottou, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 25. Curran Associates, Inc.,
references.authors: S. Sarykalin G. Serraino S. Uryasev
references.title: Value-at-risk vs
references.venue: conditional value-at-risk in risk management and optimization. In State-of-the-art decision-making tools in the informationintensive age, pages 270–294. Informs,
references.authors: T. Sawik
references.title: Optimization of cost and service level in the presence of supply chain disruption risks: Single vs
references.venue: multiple sourcing. Computers amd Operations Research, 51:11 – 20,
references.authors: R.K. Sundaram
references.title: A First Course in Optimization Theory
references.venue: Cambridge University Press,
references.authors: W.R. Thompson
references.title: On the likelihood that one unknown probability exceeds another in view of the evidence of two samples
references.venue: Biometrika, 25(3/4):285–294,
references.authors: H. Victor
references.title: A general class of exponential inequalities for martingales and ratios
references.venue: Annals of probability,
references.authors: J. Ville
references.title: Etude critique de la notion de collectif
references.venue: Bull. Amer. Math. Soc, 45(11):824,
references.authors: M.K. Warmuth D. Kuzmin
references.title: Online variance minimization
references.venue: G. Lugosi and H. U. Simon, editors, Learning Theory, pages 514–528, Berlin, Heidelberg,
references.authors: D. Williams
references.title: Probability with martingales
references.venue: Cambridge university press,
references.authors: R.C. Williamson A.K. Menon
references.title: Fairness risk measures
references.venue: arXiv preprint arXiv:1901.08665,
references.authors: J.Y. Yu E. Nikolova
references.title: Sample complexity of risk-averse bandit-arm selection
references.venue: Twenty- Third International Joint Conference on Artificial Intelligence,
sections.heading: 1 Introduction
sections.text: Tail risk is a common term used to quantify losses occurring due to rare events, and has been an important topic in finance, insurance and other safety critical uncertain environments. [44] first formalized the problem of identifying optimal investment in financial assets as a multi-criteria 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-risk (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). Informally, for a probability measure η, VaR at level π ∈ (0, 1) is the πth quantile for η, i.e., the outcome below which there is exactly π mass. CVaR at level π is the conditional expectation of η, conditioned on values beyond the VaR at 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 [51], etc. Recently, coherent risk measures, especially CVaR, have also been used in connection with fairness in 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, 1, 7, 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 on average might result in adverse outcomes for some patients. In finance, one
  35th Conference on Neural Information Processing Systems (NeurIPS 2021).
  is typically interested in balancing the mean return with the risk of extreme losses. Risk sensitivity has been well studied in 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 a 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 or 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 δ-correct, i.e., identify the correct answer (arm with minimum VaR, CVaR or mean-CVaR) with probability at least 1− δ, for some pre-specified confidence level δ. While ensuring δ-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]). Variants of this problem have been widely studied in the literature, where the best-arm is the one with maximum mean (see, [43, 25, 6, 14, 26, 33, 27, 34]).
  A relaxation of the pure exploration setting described above is the ( , δ)-PAC setting, where the aim is to output an -optimal arm (for an appropriate notion of -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 in the ( , δ)-PAC setting. While [59] consider both VaR and CVaR as measures of risk, [18, 32] focus on the VaR-problem. Recently, [39] and [35] have studied the BAI MAB problem with CVaR and mean-CVaR objectives, respectively, in the closely related “fixed-budget” framework, in which the total number of samples the algorithm is allowed to take is fixed, and the aim of the algorithm is to minimize the error-probability.
sections.heading: 1.1 Outline of the approach and main assumption
sections.text: As a 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 its parameter. We show that both CVaR and VaR are monotonic functions of this parameter, as is the mean. Hence, finding the best-(CVaR/VaR/mean-CVaR) arm reduces to finding the arm with the minimum mean.
  Since risk-sensitive objectives are particularly important when there is a non-trivial probability of occurrence of extreme outcomes, it is important to consider arm-distributions beyond canonical SPEF, for which the above-mentioned equivalence breaks. We solve the VaR problem for arbitrary arm distributions.
  In contrast the CVaR problem is unlearnable in full generality: on the class of all arm distributions, any δ-correct algorithm requires an infinite number of samples in expectation to identify the best arm amongst any finite collection of arms (Remark 3.1). To avoid this, we impose a mild and standard raw (1 + )-moment restriction on the arm-distributions. Let P(<) denote the collection of all the probability distributions on the reals <, and let B and be positive constants. For risk measure CVaR and for the mean-CVaR objective, we restrict the class of allowed arm distributions to
  L = { η ∈ P(<) : Eη ( |X|1+ ) ≤ B } .
  We discuss the choice of parameters in Section 1.3 below. For each tail measure, we prove informationtheoretic lower bounds on the sample complexity of any δ-correct algorithm, and use these to develop a δ-correct algorithm whose sample complexity exactly matches the lower bound as δ → 0, 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 mean-CVaR setting in Appendix I. We also spell out the somewhat analogous analysis for the VaR setting towards the end (Section 4.2), with details deferred Appendix to H.
sections.heading: 1.2 Technical contributions
sections.text: 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 ideally 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 a 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 to our lower bounds, algorithms, confidence intervals etc.
  Information distance for CVaR problem: Given η1, η2 in P(<), let KL(η1, η2) denote the KLdivergence between them, i.e., KL(η1, η2) := ∫ log dη1dη2 (y)dη1(y). Furthermore, for the probability measure η let cπ(η) denote its CVaR at the given confidence level π ∈ (0, 1) (see Section 2 for the exact definition). Then, given η ∈ P(<) and x ∈ <, we define functionals KLUinf : P(<)×< −→ <+, and KLLinf : P(<)×< −→ <+, where <+ denotes the non-negative reals, as
  KLUinf(η, x) := min κ∈L: cπ(κ)≥x KL(η, κ) and KLLinf(η, x) := min κ∈L: cπ(κ)≤x KL(η, κ). (1)
  See [2, 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, KLUinf and KL L inf in (1) are not symmetric, and need to be studied separately. In particular, KLUinf is a convex optimization problem, while KL L inf is not. This is because cπ(·) is a concave function, whence, the CVaR constraint in the KLLinf problem in (1) renders the feasible region non-convex (see Section 2). CVaR can be expressed as the optimal value of a minimization problem. This helped in re-expressing KLLinf as minimization over 2 variables, fixing one of which resulted in convex optimization over the other (see Section 3).
  For proving δ-correctness, we develop a new concentration inequality for weighted sums of these functionals (Proposition 4.2). Dual representations of these suggest natural candidates for supermartingales, whose mixtures help us 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 KLUinf - and KL L inf -based 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, we 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 KLLinf and KL U inf 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(<) with the topology of weak convergence, or equivalently, with the Lévy metric (see Section 2 for definitions). Another nuance in our analysis is that the empirical distributions may not lie in L. This is handled by projecting these on to L under a 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 as 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 n of the algorithm (where n samples are 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 KLLinf and KLUinf replaced by the corresponding functionals with the VaR constraints instead, is asymptotically optimal for this problem in complete generality (Section 4.2). Here, KLUinf and KL L inf have closed form representations. However, they are no longer jointly-continuous in the Lévy metric, which introduces new technical challenges in the analysis of the algorithm.
sections.heading: 1.3 Regarding the choice of and B in our assumption
sections.text: 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, [31]). Input distributions in simulation are known and may often
  involve heavy tails. In some cases, by the use of Lyapunov-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 a 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 a particular tail index, say, (1 + ). For stock returns, extensive research suggests that (1 + ) ∈ [2, 5]. For daily exchange rates and income and wealth distributions we may have (1 + ) ∈ (1, 2]. Extreme value theory, under reasonable dependence structure amongst underlying securities, shows that a portfolio (a weighted sum) will also have the same tail index of (1 + ) (see, [19]). So the key approximation needed is in arriving at B. It is easy to arrive at distributions η and κ whose (1 + )th moments are arbitrarily far while the KL 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 a pragmatic view and approximate B by estimating the (1 + )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 are independent, even though these may only be approximately correct.
sections.heading: 2 Background
sections.text: For K ≥ 2, letM = LK denote the collection of all K-vectors of distributions, ν = (ν1, . . . , νK), such that for all i, νi belongs to L. Let µ ∈M be the given bandit problem, and π ∈ (0, 1) denote the fixed confidence level. For η ∈ P(<), let Fη(y) = η((−∞, y]) denote the CDF function for η, and let m(η) denote mean of measure η.
  VaR, CVaR: With the above notation, VaR at level π for the distribution η, denoted as xπ(η), equals min {z ∈ < : Fη(z) ≥ π} . Since Fη(·) is a non-decreasing and right-continuous function, the minimum in the expression of VaR is always attained. Define CVaR at level π, cπ(η), as
  cπ(η) = Fη(xπ(η))− π
  1− π xπ(η) +
  1
  1− π ∞∫ xπ(η) ydFη(y). 0 1 π
  xπ(η)0
  Fη(x)
  If η has a density in a neighbourhood around xπ , then cπ(η) = Eη (X|X ≥ xπ(η)) , i.e., 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− π 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− π), 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.
  cπ(η) = 1
  1− π ∫ p∈[π,1] xp(η)dp = min x0∈< { x0 + 1 1− π Eη ((X − x0)+) } (2)
  = max v∈M+(<)
  1
  1− π ∫ < ydv(y) s.t. ∀y, dv(y) ≤ dη(y) and ∫ < dv(y) = 1− π, (3)
  where (x)+ denotes max {0, x} and M+(<) denotes collection of all non-negative measures on <. From (2), since cπ(η) is a minimum of linear functions of η, it is a concave function of η. Thus, the KLUinf problem in (1) is a convex optimization problem, while the KL L inf problem is not, since the cπ(·) 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, it can be argued that xπ(ηθ) is a monotonically increasing function of θ when ηθ belongs to a canonical SPEF with parameter θ, as is the mean. The
  first formulation in 2 then gives that cπ(ηθ) is also monotonically increasing. Thus, the problem of identifying the best-(CVaR/VaR/mean-CVaR) arm is equivalent to identifying that with minimum mean. See Appendix A for details.
  However, the ranking in mean and in CVaR can be very different in general. To see this, fix π = 0.8, and consider a 3-armed bandit instance, ν, with ν1 = 0.8δ0 + 0.2δ1, ν2 = 0.8δ0 + 0.2δ0.5, and ν3 = 0.8δ−0.5 + 0.2δ2. Clearly, m(ν1) > m(ν2) > m(ν3), yet cπ(ν2) < cπ(ν1) < cπ(ν3).
  General case: For η in class L, the moment-constraint limits the minimum and maximum possible values of VaR and CVaR, as discussed in the following lemma (proof in Appendix B). Lemma 2.1. For η ∈ L, cπ(η) ∈ D and xπ(η) ∈ C, where
  D , [ −B 1 1+ , ( B
  1− π
  ) 1 1+ ] and C , [ − ( B
  π
  ) 1 1+
  ,
  ( B
  1− π
  ) 1 1+ ] .
  Topology of weak convergence and the Lévy metric: Let φ be a bounded and continuous function on <, δ > 0, and x ∈ <. Consider the topology on P(<), generated by the base sets of the form U(φ, x, δ) = { η ∈ P(<) : | ∫ < φ(y)dη(y)− x| < δ } . Weak convergence of a sequence κn to κ, denoted as κn D =⇒ κ, is convergence in this topology [see 23, Sec-
  tion D.2]. It is equivalent to convergence in the Lévy metric on P(<), (denoted by dL), defined next (see, [9, Theorem 6.8], [23, Theorem D.8]). For η, κ ∈ P(<), dL(η, κ) equals inf {δ > 0 : Fη(x− δ)− δ ≤ Fκ(x) ≤ Fη(x+ δ) + δ, ∀x ∈ <} . Additionally, the metric space (P(<), dL) is complete and separable.
sections.heading: 3 Lower bound
sections.text: We consider δ-correct algorithms for identifying the arm with minimum CVaR, acting on bandit problems inM. While ensuring δ-correctness, the aim is to minimize the sample complexity, i.e., expected number of samples generated by the algorithm before it terminates. As is well known, the δ-correctness property imposes a lower bound on the sample complexity of such algorithms.
  Let µ ∈M denote the given bandit problem. Henceforth, for ease of notation, we assume without loss of generality that the best-CVaR arm in µ is arm 1. Let ΣK denote the probability simplex in <K , Aj denote the collection of all bandit problems inM which have arm j as the best-CVaR arm, τδ be the stopping time for the δ-correct algorithm, Na(τ) denote the number of times arm a has been sampled by the algorithm, and for a set S, let So denote its interior. It is easy to deduce using standard arguments (see, e.g., [40, Theorem 33.5]) that for a δ-correct algorithm acting on µ ∈ A1,
  E (τδ) ≥ V (µ)-1 log 1
  4δ where V (µ) = sup t∈ΣK inf ν∈Ac1 K∑ a=1 ta KL(µa, νa), and Acj =M\Aj . (4)
  Lemma 3.1. For µ ∈ A1, the inner minimization problem in V (µ) equals
  min j 6=1 inf x≤y
  { t1 KL U inf(µ1, y) + tj KL L inf(µj , x) } ,
  and hence V (µ) = sup
  t∈ΣK min j 6=1 inf x≤y
  { t1 KL U inf(µ1, y) + tj KL L inf(µj , x) } . (5)
  Recall from (1) that the expressions in (4) and (5) above differ from those in the best-mean arm setting in that the functionals KLLinf and KL U inf here are defined instead with the CVaR constraints. Remark 3.1. Without any restriction on arm distributions for the CVaR-problem, for y ∈ < and η ∈ L, KLUinf(η, y) = 0. This is essentially because η 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 VaR-problem without such assumptions, i.e., arm distributions are allowed to be arbitrary probability measures in <. The lower bound for the VaR problem is as in (4), with KLLinf and KLUinf in the representation in (5) defined with VaR constraints, instead.
  A proof of Lemma 3.1 can be found in Appendix C.1. Let t∗ :M→ 2ΣK . In particular, for ν ∈M, let t∗(ν) denote the set of maximizers in the V (ν) optimization problem in (5). A key nuance of our algorithm and the related analysis is that the vector of empirical distributions may not belong to the classM. 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 t∗ (Section 4). For appropriate choices of the projection maps, the following lemmas guarantee that as the empirical distributions converge to the actual arm-distributions (in the weak topology), the t∗ computed by the algorithm converge to the optimal weights corresponding to µ. Lemma 3.2. L is a 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 L×Do, KLLinf and KLUinf are both jointly continuous functions of the arguments. Moreover, for fixed x, KLUinf(ν, x) is a convex function of ν.
  Definition (Upper hemicontinuity) A set-valued function Γ : S → T is upper hemicontinuous at s ∈ S if for any open neighbourhood V of Γ(s) there exists a neighbourhood U of s such that for all x ∈ U , Γ(x) is a subsest of V . Lemma 3.3. t∗ is an upper-hemicontinuous correspondence. For ν ∈Mo, t∗(ν) is a convex set.
  In Lemma 3.2, we restrict to the interior of D as KLUinf(·, B 1 1+ (1 − π) −1 1+ ) and KLLinf(·,−B 1 1+ ) 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.1). Lemma 3.3 and Theorem 4.1 (optimality and δ-correctness of the proposed algorithm) hold for distributions with CVaR in Do. For ease of notation, we restrict µ to lie in the interior ofM. 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-semicontinuity of the KL-projection functionals separately. These rely on various properties of the weak convergence of probability measures in L, the dual representations for KLLinf and KLUinf (see Theorem 3.4), properties of CVaR 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 t∗ is the set of maximizers of a 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, we now provide more tractable characterizations of the two KL-projection functionals, and in particular, of (5). We also discuss the statistical and computational implications of these alternative characterizations.
  For η ∈ P(<), let Supp(η) denote the collection of points in the support of measure η. For v ∈ Do, x0 ∈ C, λ ∈ <3, γ ∈ <2, and X ∈ <, set
  gU (X,λ, v) = 1 + λ1v − λ2(1− π) + λ3(|X|1+ −B)− (λ1X (1− π)-1 − λ2)+, and gL(X,γ, v, x0) = 1− γ1(v − x0 − (X − x0)+ (1− π)-1)− γ2(B − |X|1+ ). Furthermore, define Ŝ(v) = { λ1 ≥ 0, λ2 ∈ <, λ3 ≥ 0 : ∀x ∈ <, gU (x,λ, v) ≥ 0 } , andR2(x0, v)
  to be { γ1 ≥ 0, γ2 ≥ 0 : ∀y ∈ <, gL(y,γ, v, x0) ≥ 0 } . Notice that these are convex sets.
  As shown in Theorem 3.4 below, gU (y, ·, v) and gL(y, ·, v, x0) are related to the dual formulations of KLUinf and KL L inf , respectively, and the parameters λ and γ are the corresponding dual variables. The sets Ŝ andR2 correspond to the feasible values of these dual variables. Theorem 3.4. For η ∈ P(<) and v ∈ Do,
  (a) KLUinf(η, v) = max λ∈Ŝ(v) Eη ( log ( gU (X,λ, v) )) .
  The maximum in this expression is attained at a unique point λ∗ ∈ Ŝ(v). The unique probability measure κ∗ ∈ L that achieves infimum in the primal problem satisfies
  dκ∗
  dη (y) =
  1
  gU (y,λ∗, v) , for y ∈ Supp(η).
  Moreover, it has mass on at most 2 points outside Supp(η). Furthermore, for y′ ∈ {Supp(κ∗) \ Supp(η)}, gU (y′,λ∗, v) = 0.
  (b) KLLinf(η, v) = min
  x0∈[−(Bπ ) 1 1+ ,v]
  max γ∈R2(x0,v)
  Eη ( log ( gL(X,γ, v, x0) )) .
  For a fixed x0, the maximum in the inner problem is attained at a unique γ∗ inR2(x0, v). The unique probability measure κ∗ ∈ L achieving infimum in the primal problem satisfies
  dκ∗
  dη (y) =
  1
  gL(y,γ∗, v, x0) , for y ∈ Supp(η).
  Moreover, size of the set {Supp(κ∗) \ Supp(η)} is at most 1, and for y′ ∈ {Supp(κ∗) \ Supp(η)}, gL(y′γ∗, v, x0) = 0.
  These dual formulations help in reformulating the lower bound optimization problem in (5) as optimization over reals. A computationally more efficient approach for this is to consider the joint dual of the inner optimization problem in (5).
  For η1, η2 ∈ P(<), and non-negative weights α1, α2, let Z = inf
  x≤y
  { α1 KL U inf(η1, y) + α2 KL L inf(η2, x) } . (6)
  For y ∈ <, λ ∈ <2,ρ ∈ <2, and γ2 ∈ <, let hL(y,λ, γ, ρ, x0) = 1− λ1 + γ2(|y|1+ −B) + ρ1(x0 + (y − x0)+(1− π)-1),
  and hU (y,λ, γ, ρ) = 1 + λ1 + λ2(|y|1+ −B)− (ρ2 + (ρ1y − ρ2)+(1− π)-1). For x0 ∈ C, define the convex region Dx0 to be collection of λ1 ∈ <, ρ2 ∈ <, λ2 ≥ 0, γ2 ≥ 0, and ρ1 ≥ 0, such that for all y ∈ <, hL(y,λ, γ, ρ, x0) ≥ 0 and hU (y,λ, γ, ρ) ≥ 0. As we show next, these quantities are related to the dual formulation of (6). Proposition 3.5. For η1, η2 ∈ P(<) and weights α1, α2 ∈ [0, 1], Z equals
  min x0∈C max (λ,γ,ρ)∈Dx0
  α1Eη1 ( log ( hU (X,λ, γ, ρ) )) + α2Eη2 ( log ( hL(X,λ, γ, ρ, x0) )) − α1 logα1 − α2 logα2 + (α1 + α2) log (α1 + α2)− (α1 + α2) log 2.
  An application of above to the empirical distributions (ηa = µ̂a(t)) weighted by sample counts, i.e., αa = Na(t), for a ∈ {1, 2}, results in unweighted sums over the samples. Also observe that the representation in Proposition 3.5 is 1 dimension smaller compared to that obtained by using Theorem 3.4 in (6), and hence, is faster to optimize numerically.
  Recall that while KLUinf is a convex optimization problem, KL L inf is not (see Section 2). To handle this, we use the min formulation for CVaR in 2 to turn it into a one-dimensional family of linear constraints, which appears as the outer minx0 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 KLUinf , we use (3). Rest is the Lagrangian duality. Complete proofs for Theorem 3.4, and Proposition 3.5, are given in Appendix D.
  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 from Theorem 3.4 in (6) to construct mixtures of super-martingales 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 3.5 in our experiments to solve the inner optimization problem in (5). These will be made precise in Section 4.
  Computing a gradient for the objective of the maximisation problem (5), seen as a function of the sampling weights t, takes one Z evaluation per suboptimal arm. The inner maximisation over Dx0 is a constrained concave program, for which standard algorithms apply. The outer minx0 problem requires a 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 on the error probability (there is none). Numerical results are presented in Section 4.4.
sections.heading: 4 The algorithm
sections.text: Given a bandit problem µ ∈M, our algorithm is a specification of three things: a sampling rule, a stopping rule, and a recommendation rule.
  Sampling rule: At each iteration, the algorithm has access to the empirical distribution vector, µ̂(n). It first projects µ̂(n) to LK in the Kolmogorov metric, dK , using the projection map, Π, defined below. It then computes t∗ (Π (µ̂(n))) and allocates samples using the C-tracking rule of [27], which we state in Appendix E for completeness. The map Π = (Π̃, . . . , Π̃), where Π̃ : P(<)→ L, is given by
  Π̃(η) ∈ argminκ∈L dK(η, κ), where dK(η, κ) := supx∈< |Fη(x)− Fκ(x)| . We show in Appendix G that this projection has a simple form and can be computed easily.
  Stopping rule: We use a modification of the generalized likelihood ratio test (GLRT) (see, [17]) as our stopping criterion. At any time, the vector of empirical distributions, µ̂(n), suggests an arm with minimum CVaR (empirically best-CVaR arm), say arm i. This is our null hypothesis, which we test against all the alternatives. Formally, the log of the GLRT statistic, denoted by Si(n), is infν′∈Aci ∑K a=1 Na(n) KL(µ̂a(n), ν ′ a). This is exactly the scaled inner optimization problem in the expression of V (µ̂(n)) in (4), except that µ̂(n) may not belong toM (recall the Z statistic defined in (6)). Let Zi(n) equal mina6=i infx≤y { Ni(n) KL U inf(µ̂i(n), y) +Na(n) KL L inf(µ̂a(n), x) } . It equals Si(n) when µ̂(n) ∈M (Lemma 3.1). Our stopping rule corresponds to checking
  Zi(n) ≥ β(n, δ) where β(n, δ) = log ( (K − 1) δ-1 ) + 5 log(n+ 1) + 2. (7)
  Recommendation rule: After stopping, the algorithm outputs the arm with the minimum CVaR of the corresponding empirical distribution, i.e., if τ is the stopping time of the algorithm, then it outputs argmina cπ(µ̂a(τ)).
sections.heading: 4.1 Theoretical guarantees
sections.text: For a given confidence δ, let τδ denote the stopping time for the algorithm. The algorithm makes an error if at time τδ, there is an arm j 6= 1 such that cπ(µ̂j(τδ)) < cπ(µ̂1(τδ)). Let the error event be denoted by E . Theorem 4.1. For δ > 0 and µ ∈Mo, the proposed algorithm with β(t, δ) chosen as in (7), satisfies
  P (E) ≤ δ and lim sup δ→0 Eµ (τδ) log(1/δ) ≤ 1 V (µ) .
  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 in Appendix F.
  δ-correctness: Recall that the algorithm makes an error if at time τδ , the empirically best-CVaR arm is not arm 1. As in the best-mean arm case, it can be argued that this probability is at most
  K∑ i=2 P ( ∃n : Ni(n) KLUinf(µ̂i(n), cπ(µi)) +N1(n) KLLinf(µ̂1(n), cπ(µ1)) ≥ β ) . (8)
  See Appendix F for a proof of (8). The following proposition will be helpful in bounding each of the summands above. Setting j = 1, and x = log K−1δ in Proposition 4.2, along with β from (7), we get that each summand in (8) is at most δ/(K − 1), proving that the proposed algorithm is δ-correct. Proposition 4.2. For i ∈ [K], j ∈ [K], i 6= j, h(n) = 5 log(n+ 1) + 2, and x ≥ 0,
  P ( ∃n : Ni(n) KLUinf(µ̂i(n), cπ(µi)) +Nj(n) KLLinf(µ̂j(n), cπ(µj))− h(n) ≥ x ) ≤ e−x.
  A key step in proving Proposition 4.2 is constructing mixtures of super-martingales that dominate the exponentials of Ni(n) KLUinf(µ̂i(n), cπ(µi)) and Ni(n) KL L inf(µ̂i(n), cπ(µi)). From Theorem 3.4(a) and (2), it can be shown that for fixed dual-variables, the objective is a sum of logs of random variables with mean at-most 1. Hence, its exponential is a non-negative candidate super-martingale. Since we want to bound the maximum over the dual parameters, we construct a mixture of these candidates, over the dual-parameters, and show that it dominates the exponential of Ni(n) KLUinf(µ̂i(n), cπ(µi)).
  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 KL-projection functionals (Lemma 3.2). Our proof also differs from that in [2] in that we only have upper-hemicontinuity of the set of optimal sampling allocations (t∗) (Lemma 3.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 t∗. Our careful choice of the projection map aids in the proof of this result.
  Computational complexity: The computational cost of these KL-projection functionals, and hence, that of the oracle weights, is linear in the number of samples taken (see, [2, 16, 30]). As a result, the overall run-time is quadratic in τδ . We propose a modification in which we update the weights only at geometrically spaced times. This modification improves the computational-cost to almost linear in τδ , while its sample complexity is 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, [3] propose a similar yet different “doubling” trick in 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 K for details of the algorithm and proofs for its theoretical guarantees.
  Mean-CVaR problem: We now extend the methodology for the CVaR problem to the more general mean-CVaR problem. For a distribution η ∈ L (for example, a random loss in a financial investment), the metric associated with the “badness” of a distribution is α1m(η) + α2cπ(η), for α1 > 0 and α2 > 0, and the best-arm is the one with minimum value of this conic combination of mean and CVaR. For α1 = 0 this is the CVaR-problem, which we have studied in this work. For α2 = 0, this is the mean-problem, extensively studied in [2, 27].
  As in (1), we can define corresponding KL-projection functionals, with the CVaR constraints replaced with those on the modified metric. The above theory, with this updated KLLinf and KL U inf , gives the corresponding results for this setting. In particular, the lower bound on E (τδ) for δ-correct algorithms for mean-CVaR BAI is given by V (µ)-1 log 14δ , where V (µ) is defined in (5) with the updated KL U inf and KLLinf . Theorem 4.3 (Informal). For µ ∈ Mo, the proposed algorithm for CVaR, with KLUinf and KLLinf defined with mean-CVaR constraints instead, is δ-correct and asymptotically optimal.
  The proof of this theorem parallels that for CVaR above. We give the formal statement with proofdetails in Appendix I.
sections.heading: 4.2 The VaR problem
sections.text: 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 to be arbitrary probability measures on <. For a probability measure η, let Fη(y), denote its CDF evaluated at y and F−η (y) = limz↑y Fη(z) denote the left limit of the CDF. Moreover, for r, q ∈ (0, 1) let d2(r, q) denote the KL divergence between the Bernoulli random variables with mean r and q. For y ∈ <, let KLLinf(η, y) and KLUinf(η, y) be defined as in (1), with VaR constraints, instead. These simplify as follows. Lemma 4.4. KLLinf(η, y) = d2(min {Fη(y), π} , π) and KLUinf(η, y) = d2(max { F−η (y), π } , π).
  Unlike in the CVaR-problem, we show that KLLinf and KL U inf for the VaR problem are not jointly continuous functionals (see Remark H.2). The discontinuity occurs at y being the jump points of Fη in Lemma 4.4 above. However, we prove in Appendix H (Corollary H.3.1) that the set of optimal proportions, t∗, is still upper-hemicontinuous and convex.
  The algorithm for CVaR with KLUinf and KL L inf replaced by those in the lemma above, and setting
  β(t, δ) = 6 log ( 1 + log t
  2
  ) + log
  K − 1 δ + 8 log
  ( 1 + log
  K − 1 δ
  ) ,
  we get our algorithm for the VaR-problem. Theorem 4.5 (Informal). The proposed algorithm for the VaR-problem is δ-correct and asymptotically optimal.
  We refer the reader to Appendix H for a detailed discussion of the VaR-problem and proofs.
  4.3 Tight KLinf -based confidence intervals for CVaR
  We now present tight anytime-valid confidence interval for the CVaR of a distribution in L. Let η̂n denote the empirical distribution corresponding to n samples from η ∈ L. Our proposed upper (Un) and lower (Ln) confidence intervals for cπ(η) are of the form Un = max { x ∈ < : nKLUinf(η̂n, x) ≤ C } and Ln = min { x ∈ < : nKLLinf(η̂n, x) ≤ C } , for an appropriately chosen threshold C ≈ log δ-1 + 3 log n. Similar confidence intervals for the mean of heavytailed distributions were proposed in [3]. Let x̂π,n denote the πth quantile for η̂n. Recall that the popular truncation-based estimator for cπ(η) is given by ĉπ,n = n-1(1−π)-1 ∑ iXi1(x̂π,n ≤ Xi ≤ un), for appropriately chosen truncation levels, un (see, [39]). Observe that there are 2 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, xπ. In Appendix J, we show that even given the correct estimation of x̂π,n, confidence intervals for ĉπ,n perform poorly compared to those based on KLUinf and KL L inf , in some applications.
sections.heading: 4.4 Numerical Results
sections.text: 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 δ. Whether this is the case or not differs greatly between pure exploration setups: [27] see state-of-the-art numerical results in Bernoulli arms for Track-and-Stop with δ = 0.1, while [22] present a Minimum Threshold problem instance where the Track-and-Stop asymptotics have not kicked in yet at δ = 10−20. Our experiments confirm that our approach is indeed practical at moderate confidence δ.
  In our experiments we implement a version of Track-and-Stop including C-tracking and forced exploration and apply it to Fisher-Tippett (F (µ, σ, γ)), Pareto (P (µ, σ, γ)), and mixtures of FisherTippett arms (these heavy-tailed distributions arise in extreme value theory).
  Figure 1 shows the distribution of the stopping time as a function of δ in a synthetic three-arm task: arm 1 is a uniform mixture of F (−1, 0.5, 0.4) and F (−3, 0.5,−0.4), arm 2 is P (0, 0.2, 0.55) and arm 3 is F (−0.5, 1, 0.1) with respective CVaRs at quantile π = 0.6 being −0.1428, 0.974 and 1.547. We select = 0.7 and B = 4.5. This is a moderately hard problem of complexity V -1(µ) = 49.7. We conclude that even at moderate δ the average sample complexity closely matches the lower bound, especially after adjusting it for the lowerorder terms in the employed stopping threshold β(n, δ). This demonstrates that our asymptotic optimality is in fact indicative of the performance in practice.
  We do additional experiments to show the dependence of the algorithm’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 L 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 a conic combination of mean and CVaR. Our algorithms operate in non-parametric settings with possibly heavy-tailed 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.
  Acknowledgments and Disclosure of Funding
  We acknowledge the support of the Department of Atomic Energy, Government of India, to TIFR under project no. RTI4001.
title: Optimal Best-Arm Identification Methods for Tail-Risk Measures