Optimal Best-Arm Identification Methods for Tail-Risk Measures

• URL: http://arxiv.org/abs/2008.07606v3
• Date: Tue, 22 Jun 2021 00:58:34 GMT
• Title: Optimal Best-Arm Identification Methods for Tail-Risk Measures
• Authors: Shubhada Agrawal, Wouter M. Koolen, Sandeep Juneja
• Abstract summary: Conditional value-at-risk (CVaR) and value-at-risk (VaR) are popular tail-risk measures in finance and insurance industries. We identify the smallest CVaR, VaR, or sum of CVaR and mean from amongst finitely that has smallest CVaR, VaR, or sum of CVaR and mean.
• Score: 9.128264779870538
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 empirical likelihood-based concentration inequalities for tail-risk measures which are tighter than those for popular truncation-based empirical estimators.

Related papers

• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  We present sred, a truly adaptive algorithm that can reject arms in it any round based on the observed empirical gaps between the rewards of various arms. In particular, we present sred, a truly adaptive algorithm that can reject arms in it any round based on the observed empirical gaps between the rewards of various arms.
  arXiv  Detail & Related papers  (2023-12-19T13:17:43Z)
• Risk Estimation in a Markov Cost Process: Lower and Upper Bounds [3.1484174280822845]
  We tackle the problem of estimating risk measures of the infinite-horizon discounted cost within a Markov cost process. The risk measures we study include variance, Value-at-Risk (VaR), and Conditional Value-at-Risk (CVaR)
  arXiv  Detail & Related papers  (2023-10-17T16:35:39Z)
• Risk-aware linear bandits with convex loss [0.0]
  We propose an optimistic UCB algorithm to learn optimal risk-aware actions, with regret guarantees similar to those of generalized linear bandits. This approach requires solving a convex problem at each round of the algorithm, which we can relax by allowing only approximated solution obtained by online gradient descent.
  arXiv  Detail & Related papers  (2022-09-15T09:09:53Z)
• Tailoring to the Tails: Risk Measures for Fine-Grained Tail Sensitivity [10.482805367361818]
  Expected risk rearrangement (ERM) is at the core of machine learning systems. We propose a general approach to construct risk measures which exhibit a desired tail sensitivity.
  arXiv  Detail & Related papers  (2022-08-05T09:51:18Z)
• Probable Domain Generalization via Quantile Risk Minimization [90.15831047587302]
  Domain generalization seeks predictors which perform well on unseen test distributions. We propose a new probabilistic framework for DG where the goal is to learn predictors that perform well with high probability.
  arXiv  Detail & Related papers  (2022-07-20T14:41:09Z)
• Risk-Constrained Thompson Sampling for CVaR Bandits [82.47796318548306]
  We consider a popular risk measure in quantitative finance known as the Conditional Value at Risk (CVaR) We explore the performance of a Thompson Sampling-based algorithm CVaR-TS under this risk measure.
  arXiv  Detail & Related papers  (2020-11-16T15:53:22Z)
• Large-Scale Methods for Distributionally Robust Optimization [53.98643772533416]
  We prove that our algorithms require a number of evaluations gradient independent of training set size and number of parameters. Experiments on MNIST and ImageNet confirm the theoretical scaling of our algorithms, which are 9--36 times more efficient than full-batch methods.
  arXiv  Detail & Related papers  (2020-10-12T17:41:44Z)
• Statistically Robust, Risk-Averse Best Arm Identification in Multi-Armed Bandits [4.760079434948198]
  We show that specialized algorithms that exploit such parametric information are prone to inconsistent learning performance when the parameter is misspecified. Our key contributions are: (i) We establish fundamental performance limits of statistically robust MAB algorithms under the fixed-budget pure exploration setting, and (ii) We propose two classes of algorithms that are twofoldly near-optimal.
  arXiv  Detail & Related papers  (2020-08-28T13:43:12Z)
• Sharp Statistical Guarantees for Adversarially Robust Gaussian Classification [54.22421582955454]
  We provide the first result of the optimal minimax guarantees for the excess risk for adversarially robust classification. Results are stated in terms of the Adversarial Signal-to-Noise Ratio (AdvSNR), which generalizes a similar notion for standard linear classification to the adversarial setting.
  arXiv  Detail & Related papers  (2020-06-29T21:06:52Z)
• Constrained regret minimization for multi-criterion multi-armed bandits [5.349852254138086]
  We study the problem of regret minimization over a given time horizon, subject to a risk constraint. We propose a Risk-Constrained Lower Confidence Bound algorithm that guarantees logarithmic regret. We prove lower bounds on the performance of any risk-constrained regret minimization algorithm.
  arXiv  Detail & Related papers  (2020-06-17T04:23:18Z)
• Thompson Sampling Algorithms for Mean-Variance Bandits [97.43678751629189]
  We develop Thompson Sampling-style algorithms for mean-variance MAB. We also provide comprehensive regret analyses for Gaussian and Bernoulli bandits. Our algorithms significantly outperform existing LCB-based algorithms for all risk tolerances.
  arXiv  Detail & Related papers  (2020-02-01T15:33:50Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.