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

Abstract

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.

References in corpus (4)

• Risk-Aversion in Multi-armed Bandits
• Stochastic simultaneous optimistic optimization
• Exploration vs Exploitation vs Safety: Risk-averse Multi-Armed Bandits
• Black-box optimization of noisy functions with unknown smoothness

Cited by in corpus (5)

• Sequential estimation of quantiles with applications to A/B-testing and best-arm identification
• Off-Policy Risk Assessment in Contextual Bandits
• Bias-Corrected Peaks-Over-Threshold Estimation of the CVaR
• Quantile Bandits for Best Arms Identification
• Risk-Averse Action Selection Using Extreme Value Theory Estimates of the CVaR