Optimal Thompson Sampling strategies for support-aware CVaR bandits
  In this paper we study a multi-arm bandit problem in which the quality of
each arm is measured by the Conditional Value at Risk (CVaR) at some level
alpha of the reward distribution. While existing works in this setting mainly
focus on Upper Confidence Bound algorithms, we introduce a new Thompson
Sampling approach for CVaR bandits on bounded rewards that is flexible enough
to solve a variety of problems grounded on physical resources. Building on a
recent work by Riou & Honda (2020), we introduce B-CVTS for continuous bounded
rewards and M-CVTS for multinomial distributions. On the theoretical side, we
provide a non-trivial extension of their analysis that enables to theoretically
bound their CVaR regret minimization performance. Strikingly, our results show
that these strategies are the first to provably achieve asymptotic optimality
in CVaR bandits, matching the corresponding asymptotic lower bounds for this
setting. Further, we illustrate empirically the benefit of Thompson Sampling
approaches both in a realistic environment simulating a use-case in agriculture
and on various synthetic examples.
