# X-Armed Bandits: Optimizing Quantiles, CVaR and Other Risks

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Apr 2019.

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

- [Off-Policy Risk Assessment in Contextual Bandits](https://mlsanity.com/paper/2104.08977/) (2021)
- [Supervised Learning with General Risk Functionals](https://mlsanity.com/paper/2206.13648/) (2022)
- [Bias-Corrected Peaks-Over-Threshold Estimation of the CVaR](https://mlsanity.com/paper/2103.05059/) (2021)
- [A sampling criterion for constrained Bayesian optimization with uncertainties](https://mlsanity.com/paper/2103.05706/) (2021)
- [Distribution-Free Model-Agnostic Regression Calibration via Nonparametric Methods](https://mlsanity.com/paper/2305.12283/) (2023)
- [Conditionally Risk-Averse Contextual Bandits](https://mlsanity.com/paper/2210.13573/) (2022)
- [A Risk-Averse Framework for Non-Stationary Stochastic Multi-Armed Bandits](https://mlsanity.com/paper/2310.19821/) (2023)

## Abstract (arXiv)

We propose and analyze StoROO, an algorithm for risk optimization on stochastic black-box functions derived from StoOO. Motivated by risk-averse decision making fields like agriculture, medicine, biology or finance, we do not focus on the mean payoff but on generic functionals of the return distribution. We provide a generic regret analysis of StoROO and illustrate its applicability with two examples: the optimization of quantiles and CVaR. Inspired by the bandit literature and black-box mean optimizers, StoROO relies on the possibility to construct confidence intervals for the targeted functional based on random-size samples. We detail their construction in the case of quantiles, providing tight bounds based on Kullback-Leibler divergence. We finally present numerical experiments that show a dramatic impact of tight bounds for the optimization of quantiles and CVaR.