# Optimal Best-Arm Identification Methods for Tail-Risk Measures

arXiv: https://arxiv.org/abs/2008.07606 · HTML: https://mlsanity.com/paper/2008.07606/

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Aug 2020.

## Built on by (most cited first, 18 of 18)

- [Top Two Algorithms Revisited](https://mlsanity.com/paper/2206.05979/) (2022)
- [Regret Minimization in Heavy-Tailed Bandits](https://mlsanity.com/paper/2102.03734/) (2021)
- [Sequential Learning of the Pareto Front for Multi-objective Bandits](https://mlsanity.com/paper/2501.17513/) (2025)
- [A Unifying Theory of Thompson Sampling for Continuous Risk-Averse Bandits](https://mlsanity.com/paper/2108.11345/) (2021)
- [A General Framework for Clustering and Distribution Matching with Bandit Feedback](https://mlsanity.com/paper/2409.05072/) (2024)
- [On Stopping Times of Power-one Sequential Tests: Tight Lower and Upper Bounds](https://mlsanity.com/paper/2504.19952/) (2025)
- [From Optimality to Robustness: Dirichlet Sampling Strategies in Stochastic Bandits](https://mlsanity.com/paper/2111.09724/) (2021)
- [Stopping Rules for Stochastic Gradient Descent via Anytime-Valid Confidence Sequences](https://mlsanity.com/paper/2512.13123/) (2025)
- [Eventually LIL Regret: Almost Sure lnln T Regret for a sub-Gaussian Mixture on Unbounded Data](https://mlsanity.com/paper/2512.12325/) (2025)
- [Asymptotically Optimal Sequential Testing with Markovian Data](https://mlsanity.com/paper/2602.17587/) (2026)
- [Multi-Armed Sequential Hypothesis Testing by Betting](https://mlsanity.com/paper/2603.17925/) (2026)
- [Regret Tail Characterization of Optimal Bandit Algorithms with Generic Rewards](https://mlsanity.com/paper/2604.14876/) (2026)
- [Towards an efficient and risk aware strategy for guiding farmers in identifying best crop management](https://mlsanity.com/paper/2210.04537/) (2022)
- [Best arm identification in rare events](https://mlsanity.com/paper/2303.07627/) (2023)
- [EVaR-Optimal Arm Identification in Bandits](https://mlsanity.com/paper/2510.04728/) (2025)
- [UCB for Large-Scale Pure Exploration: Beyond Sub-Gaussianity](https://mlsanity.com/paper/2511.22273/) (2025)
- [Cover meets Robbins while Betting on Bounded Data: ln n Regret and Almost Sure lnln n Regret](https://mlsanity.com/paper/2604.20172/) (2026)
- [Certify the Decision, Not Every Score: Exact Top-k Selection from Few Evaluations](https://mlsanity.com/paper/2610.14996/) (2026)

## Abstract (arXiv)

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 δ-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. En-route, we develop new non-asymptotic empirical likelihood-based concentration inequalities for tail-risk measures which are tighter than those for popular truncation-based empirical estimators.