Risk-Constrained Thompson Sampling for CVaR Bandits

Abstract

The multi-armed bandit (MAB) problem is a ubiquitous decision-making problem that exemplifies the exploration-exploitation tradeoff. Standard formulations exclude risk in decision making. Risk notably complicates the basic reward-maximising objective, in part because there is no universally agreed definition of it. In this paper, 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. We provide comprehensive comparisons between our regret bounds with state-of-the-art L/UCB-based algorithms in comparable settings and demonstrate their clear improvement in performance. We also include numerical simulations to empirically verify that CVaR-TS outperforms other L/UCB-based algorithms.

arXiv comment7 pages main paper with 11 pages supplementary material

References in corpus (7)

• Analysis of Thompson Sampling for the multi-armed bandit problem
• Risk-Aversion in Multi-armed Bandits
• Risk-Averse Multi-Armed Bandit Problems under Mean-Variance Measure
• Exploration vs Exploitation vs Safety: Risk-averse Multi-Armed Bandits
• Statistical Learning with Conditional Value at Risk
• Learning Bounds for Risk-sensitive Learning
• Bounds on Tail Probabilities in Exponential families

Cited by in corpus (3)

• Off-Policy Risk Assessment in Contextual Bandits
• Risk averse non-stationary multi-armed bandits
• Thompson Sampling for Gaussian Entropic Risk Bandits