Timezone: »
The multi-armed bandit (MAB) problem is a classical learning task that exemplifies the exploration-exploitation tradeoff. However, standard formulations do not take into account risk. In online decision making systems, risk is a primary concern. In this regard, the mean-variance risk measure is one of the most common objective functions. Existing algorithms for mean-variance optimization in the context of MAB problems have unrealistic assumptions on the reward distributions. We develop Thompson Sampling-style algorithms for mean-variance MAB and provide comprehensive regret analyses for Gaussian and Bernoulli bandits with fewer assumptions. Our algorithms achieve the best known regret bounds for mean-variance MABs and also attain the information-theoretic bounds in some parameter regimes. Empirical simulations show that our algorithms significantly outperform existing LCB-based algorithms for all risk tolerances.
Author Information
Qiuyu Zhu (National University of Singapore)
Vincent Tan (National University of Singapore)
More from the Same Authors
-
2021 Poster: SGA: A Robust Algorithm for Partial Recovery of Tree-Structured Graphical Models with Noisy Samples »
Anshoo Tandon · Aldric Han · Vincent Tan -
2021 Poster: CIFS: Improving Adversarial Robustness of CNNs via Channel-wise Importance-based Feature Selection »
Hanshu YAN · Jingfeng Zhang · Gang Niu · Jiashi Feng · Vincent Tan · Masashi Sugiyama -
2021 Spotlight: CIFS: Improving Adversarial Robustness of CNNs via Channel-wise Importance-based Feature Selection »
Hanshu YAN · Jingfeng Zhang · Gang Niu · Jiashi Feng · Vincent Tan · Masashi Sugiyama -
2021 Spotlight: SGA: A Robust Algorithm for Partial Recovery of Tree-Structured Graphical Models with Noisy Samples »
Anshoo Tandon · Aldric Han · Vincent Tan -
2021 Poster: Probabilistic Sequential Shrinking: A Best Arm Identification Algorithm for Stochastic Bandits with Corruptions »
Zixin Zhong · Wang Chi Cheung · Vincent Tan -
2021 Spotlight: Probabilistic Sequential Shrinking: A Best Arm Identification Algorithm for Stochastic Bandits with Corruptions »
Zixin Zhong · Wang Chi Cheung · Vincent Tan -
2020 Poster: Best Arm Identification for Cascading Bandits in the Fixed Confidence Setting »
Zixin Zhong · Wang Chi Cheung · Vincent Tan