Timezone: »

 
Poster
Optimal Best-Arm Identification Methods for Tail-Risk Measures
Shubhada Agrawal · Wouter Koolen · Sandeep Juneja

Tue Dec 07 08:30 AM -- 10:00 AM (PST) @
in Poster Session 1 »
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, anytime-valid, empirical-likelihood-based concentration inequalities for tail-risk measures.
Keywords: Optimization · Reinforcement Learning and Planning · Bandits

Author Information

Shubhada Agrawal (TIFR Mumbai)
Wouter Koolen (Centrum Wiskunde & Informatica, Amsterdam)
Sandeep Juneja (Tata Institute of Fundamental Research)

More from the Same Authors