Risk-Averse Multi-Armed Bandit Problems Under Mean-Variance Measure

The multi-armed bandit (MAB) problems have been studied mainly under the measure of expected total reward accrued over a horizon of length T . In this paper, we address the issue of risk in MAB problems and develop parallel results under the measure of mean-variance, a commonly adopted risk measure in economics and mathematical finance. We show that the model-specific regret and the model-independent regret in terms of the mean-variance of the reward process are lower bounded by Ω(logT) and Ω(T 2/3 ), respectively. We then show that variations of the UCB policy and the DSEE policy developed for the classic risk-neutral MAB achieve these lower bounds.