Thompson Sampling Algorithms for Mean-Variance Bandits (2020-02-01T00:00:00.000000Z)

TL;DR

Thompson Sampling-style algorithms for mean-variance MAB and comprehensive regret analyses for Gaussian and Bernoulli bandits with fewer assumptions are developed and shown to significantly outperform existing LCB-based algorithms for all risk tolerances.

Abstract

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 {\em 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.

Authors

Qiuyu Zhu

1 papers

V. Tan

1 papers

Thompson Sampling Algorithms for Mean-Variance Bandits

TL;DR

Abstract

Authors

References25 items

Bandit Algorithms

Risk-aware Multi-armed Bandits Using Conditional Value-at-Risk

Index-Based Policy for Risk-Averse Multi-Armed Bandit

A General Approach to Multi-Armed Bandits Under Risk Criteria

Pure Exploration for Max-Quantile Bandits

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

Bounds on Tail Probabilities in Exponential families

Mean-variance and value at risk in multi-armed bandit problems

Exploration vs Exploitation vs Safety: Risk-Aware Multi-Armed Bandits

Robust Risk-Averse Stochastic Multi-armed Bandits

Bandits With Heavy Tail

Deviations of Stochastic Bandit Regret

Multi-armed bandit problems with heavy-tailed reward distributions

Exploration-exploitation tradeoff using variance estimates in multi-armed bandits

Risk-Sensitive Online Learning

Handbook of Mathematical Functions With Formulas, Graphs and Mathematical Tables (National Bureau of Standards Applied Mathematics Series No. 55)

ON THE LIKELIHOOD THAT ONE UNKNOWN PROBABILITY EXCEEDS ANOTHER IN VIEW OF THE EVIDENCE OF TWO SAMPLES

Portfolio Selection

PAC Bandits with Risk Constraints

Pure Exploration of Multi-Armed Bandits with Heavy-Tailed Payoffs

Information Theory - Coding Theorems for Discrete Memoryless Systems, Second Edition

The economic nature of the firm: From Risk, Uncertainty, and Profit

MUTUAL FUND PERFORMANCE*

25th Annual Conference on Learning Theory Analysis of Thompson Sampling for the Multi-armed Bandit Problem

Author manuscript, published in "NIPS- Twenty-Sixth Annual Conference on Neural Information Processing Systems (2012)" Risk–Aversion in Multi–armed Bandits

Field of Study

Journal Information

Name

Volume

Venue Information

Name

Type

URL

Alternate Names