A Survey of Risk-Aware Multi-Armed Bandits

1 Introduction

The multi-armed bandit (MAB) problem studies the problem of online learning with partial feedback that exemplifies the exploration-exploitation tradeoff. This problem has a long history dating back to Thompson [1933] and finds a wide variety of applications from clinical trials to financial portfolio optimization. In the stochastic MAB problem, a player chooses or pulls one among several arms, each defined by a certain reward distribution. The player wishes to maximize his reward or find the best arm in the face of the uncertain environment the distributions are a priori unknown. There are two general sub-problems in the MAB literature, namely, regret minimization and best-arm identification (also called pure exploration). In the former, in which the explorationexploitation trade-off manifests, the player wants to maximize his reward over a fixed time period. In the latter, the player simply wants to learn which arm is the best in either the quickest time possible with a given probability of success (the fixed-confidence setting) or he wants to do so with the highest probability of success given a fixed playing horizon

(the fixed budget setting). In most of the MAB literature (see Lattimore and Szepesvari [2020] for an up-to-date survey), the metric of interest is defined simply as the mean of the reward distribution associated with the arm pulled.

However, in real-world applications, the mean does not satisfactorily capture the merits of certain actions. In such applications, risk plays an important role, and a risk-aware performance measure is often preferred over the average reward. For example, if we have an important face-to-face meeting downtown, we might want to choose a route that has a slightly higher expected travel time, but whose variance is small. Some risk measures include the mean-variance [Markowitz, 1952], the conditional value-at-risk [Artzner et al., 1999; Rockafellar and Uryasev, 2000], spectral risk measures [Acerbi, 2002], and cumulative prospect theory [Tversky and Kahneman, 1992]. This short survey aims to consolidate these various risk measures and to comment on their concentration properties. These properties are then used to describe the latest algorithmic developments for risk-aware bandits in regret minimization as well as best arm identification settings.

2 Preliminaries

For forming estimators of risk measures, we require the empirical distribution function (EDF), which we define below.

Definition 1. Given i.i.d. samples {Xi}ni=1 from the distribution F of a random variable (r.v.) X, the EDF is

To establish concentration bounds for risk measures, one requires an assumption that bounds the tail of the distribution. In this article, we consider sub-Gaussian distributions.

Definition 2. A r.v. X is sub-Gaussian with parameter σ2 if its cumulant generating function

See Theorem 2.1 of Wainwright [2019] for equivalent characterizations. A sub-Gaussian r.v. X satisfies the following bound for any ϵ > 0:

For unifying risk measures, we require the notion of the Wasserstein distance, which is defined below.

Definition 3. The Wasserstein distance between two cumulative distribution functions (CDFs) F1 and F2 on R is

where Γ(F1, F2) is the set of couplings of F1 and F2.

The Wasserstein distance between two CDFs. F1 and F2 of two r.v.s X and Y , respectively, may be alternatively written as follows:

where the supremum is over all functions f : R→R that are 1-Lipschitz.

3 Estimation and Concentration of Risk Measures

3.1 Mean-Variance

We present a measure that effectively balances between expected reward and variability. Although there are a large number of models that resolve the tension between return and risk-such as the Sharpe ratio [Sharpe, 1966] and the Knightian uncertainty [Knight, 1921], we commence our discussion on one of the most popular measures, namely the meanvariance proposed by Markowitz [1952].

Definition 4. The mean-variance of a r.v. X with mean µ and variance σ2 and risk tolerance γ is MV = γµ - σ2 .

We can recover two extreme cases by considering the extremal values of the risk tolerance γ. When γ → ∞, maximizing MV simply reduces to maximizing the mean, turning the mean-variance MAB problem into a standard reward maximizing problem. When γ = 0, the mean-variance MAB problem reduces to a variance-minimization problem. When one only has access to samples, one can estimate the meanvariance by using plug-in estimates for the mean and variance. Concentration results for the mean-variance can be found in Zhu and Tan [2020] and Sani et al. [2012].

3.2 Lipschitz-Continuous RiskMeasures

In Cassel et al. [2018], the authors consider general risk measures that satisfy a Lipschitz requirement under some norm in the space of distributions. Prashanth and Bhat [2020] use the notion of Wasserstein distance as the underlying norm in defining a continuous class of risk measures as given below.

Definition 5. Let (L,W1) denote the metric space of distributions. A risk measure ρ(·) is Lipschitz-continuous on (L,W) if there exists L > 0 such that, for any two distributions (CDFs) F, G ∈ L, the following holds:

Using the EDF Fn computed from n i.i.d. samples, we estimate the risk measure ρ(F) satisfying (1) as follows: ρn := ρ(Fn).

Theorem 1. Let X be a sub-Gaussian r.v. with parameter σ2 . Suppose ρ : L → R is a Lipschitz risk measure with parameter L. Then, for every ϵ satisfying 256√2σ √n < ϵL < 256√2σ √n +16σ√2e, we have

where e is Euler's number.

Conditional Value-at-Risk [Rockafellar and Uryasev, 2000], and the spectral risk measure [Acerbi, 2002] are two popular risk measures that are Lipschitz continuous. We describe these risk measures below. For other examples of risk measures satisfying (1), the reader is referred to Cassel et al. [2018] and Prashanth and Bhat [2020].

3.3 Conditional Value-at-Risk (CVaR)

Definition 6. Let (y)+ := max(y, 0). The CVaR at level α ∈ (0, 1) for a r.v. X is defined by

It is well known [Rockafellar and Uryasev, 2000] that the infimum in the definition of CVaR above is achieved for ξ = VaRα(X), where VaRα(X) = inf{ξ : P (X ≤ ξ) ≥ α} is the Value-at-Risk (VaR) of X at confidence level α. In financial applications, one prefers CVaR over VaR, since CVaR is coherent, while VaR is not [Artzner et al., 1999]. CVaR also admits the following equivalent representation:

The following lemma shows that CVaR is a Lipschitz risk measure in the sense of Definition 5.

Lemma 1. Suppose X and Y are r.v.s with CDFs FX and FY , respectively, and α ∈ (0, 1). Then

Let X1, . . . ,Xn denote i.i.d. samples drawn from the distribution of X. CVaRα(X) can be estimated as follows:

Let Y denote a r.v. with distribution Fn. Then, it can be shown that

where ˆ vn,α = inf{x ∈ R : Fn(x) ≥ α}.

A concentration bound for CVaR estimation under a subGaussianity assumption follows as a corollary to Theorem 1. Other works on CVaR estimation can be found in Brown [2007], Wang and Gao [2010], Kolla et al. [2019], Thomas and Learned-Miller [2019], Kagrecha et al. [2019], and Prashanth et al. [2020].

3.4 Spectral RiskMeasures (SRMs)

Given a risk spectrum φ : [0, 1] → [0,∞), the SRM Mφ associated with φ is defined by Acerbi [2002]

Mφ is a coherent risk measure if the risk spectrum is increasing and integrates to 1. Further, Mφ generalizes CVaR, since setting φ(β) = (1 - α)-1 I {β ≥ α} leads to Mφ = CVaRα(X).

The result below shows that an SRM is a Lipschitz risk measure if the risk spectrum φ is bounded.

Lemma 2. Suppose φ(u) ≤ K for all u ∈ [0, 1], and let X and Y be r.v.s with CDFs FX and FY , respectively. Then

Specializing the estimator ρn = ρ(Fn) for SRM leads to the following estimator:

Using Lemma 2 and Theorem 1, a concentration bound for SRM estimation can be derived in a straightforward manner.

Since CVaR and spectral risk measures are weighted averages of the underlying distribution quantiles, a natural alternative to a Wasserstein distance-based approach is to employ concentration results for quantiles; cf. Prashanth et al. [2020] and Pandey et al. [2021]. While such an approach can provide bounds with better constants, the resulting bounds also involve distribution-dependent quantities. In this survey, we have chosen the Wasserstein distance-based approach since it provides a unified bound for an abstract risk measure that is Lipschitz, and one can easily specialize this bound to handle CVaR, SRM and other risk measures. Secondly, a template confidence-bound type bandit algorithm can be arrived at using the unified concentration bound in Theorem 1.

3.5 RiskMeasures based on Cumulative Prospect Theory (CPT)

We present a risk measure based on CPT, and this risk measure does not satisfy the Lipschitz condition in Definition 5. The CPT-value of an r.v. X is defined as [Prashanth et al., 2016]

where u+, u- : R → R+ are the utility functions that are assumed to be continuous, with u+(x) = 0 when x ≤ 0 and increasing otherwise, and with u-(x) = 0 when x ≥ 0 and decreasing otherwise, w+,w- : [0, 1] → [0, 1] are weight functions assumed to be continuous, non-decreasing and satisfy w+(0) = w-(0) = 0 and w+(1) = w-(1) = 1.

Given a set of i.i.d. samples {Xi}ni=1 , we form the EDFs F + n (x) and F - n (x) of the r.v.s u+(X) and u-(X), respectively, Using these EDFs, we estimate CPT-value as follows:

The integrals above can be computed using the order statistics; see Jie et al. [2018].

We now present a concentration result for CPT-value estimation assuming bounded support for the underlying distribution; see Prashanth et al. [2016] and Jie et al. [2018] for the proof.

(A1) The weight functions w± are H¨older continuous with common order α and constant H, i.e.,

(A2) The utility functions u+, u- : R → R+ are bounded above by M.

Proposition 1. Under (A1) and (A2), for all ϵ > 0,

For the sub-Gaussian case, one can use a truncated CPTvalue estimator, and establish an exponentially decaying tail bound; see Bhat and Prashanth [2019] for details.

4 Regret Minimization

A bandit instance ν is a collection of K distributions (ν1, ν2, . . . , νK). Each distribution νi has mean µi ∈ R and without loss of generality, one may assume that µ1 ≥ µ2 ≥ . . . ≥ µK. The agent interacts with the bandit environment at each time by pulling an arm At ∈ {1, . . . , K} and observing a reward Xt,At drawn from νAt . The decision of which arm to pull depends on the previous arm pulls as well as rewards Ht-1 = (A1, X1,A1 , . . . At-1, Xt-1,At-1 ). Over a fixed time period (or horizon) of length n, the agent desires to maximize his/her total reward ∑nt=1 Xt,At by designing an appropriate policy π = {πt}nt=1 where πt is σ(Ht-1)-measurable. An equivalent measure is the regret

which is to be minimized over π. However, this measure pays no attention to risk, which is the central theme of this survey. More generally, the agent would like to minimize the ρ-regret

where ρ(ν) is an appropriate risk measure. Let ∆i = ρ(νi∗ )- ρ(νi) be the gap between the risk of the best arm i∗ and that of the i-th arm.

4.1 Confidence Bound-Based Algorithms

We present a straightforward adaptation Risk-LCB of the well-known UCB algorithm [Auer et al., 2002] to handle an objective based on abstract risk measures ρ. The algorithm caters to Lipschitz risk measures (see Definition 5) and arms' distributions that are sub-Gaussian. Here, note that we are minimizing the risk measure instead of maximizing the reward.

To obtain the confidence widths, we first rewrite the concentration bound in Theorem 1 as follows: For any δ ∈ [exp(-2m), 1], with probability ≥ 1 - δ,

where ρm = ρ(Fm) is an m-sample estimate of the risk measure ρ(X). For the classic bandit setup with a expected value objective, the finite sample analysis provided by [Auer et al., 2002] chose to set δ = t-4 for obtaining a sub-linear regret guarantee. This choice also satisfies the constraint on δ specified in the high confidence guarantee on ρm above. Under this choice of δ, in any round t of Risk-LCB and for any arm k ∈ {1, . . . ,K}, we have

where

In the above, ρi,Ti(t-1) is the estimate of the risk measure for arm i computed using ρn = ρ(Fn) from Ti(t - 1) samples.

The Risk-LCB algorithm would play all arms once in the initialization phase, and in rounds t ≥ K +1, play an arm At according to the following rule:

Theorem 2. Consider a K-armed stochastic bandit problem with a Lipschitz risk measure ρ and the arms' distributions are sub-Gaussian with parameter σ2 . Then, the expected regret Rρn of Risk-LCB satisfies the following bound:

This bound mimics that of risk-neutral UCB except that the ∆i's depend on ρ.

The regret bound derived in Theorem 2 is not applicable for CPT, as it is not a Lipschitz risk measure. However, one can derive a confidence bound-based algorithm with CPT as the risk measure using the result in Proposition 1 for the case of arms' distributions with bounded support, see Gopalan et al. [2017]. The regret bound is of the order O(∑i:∆i>0 log n ∆2/α-1 i ), where α is the H¨older exponent (see (A1) above). This bound cannot be improved in terms of dependence on the gaps and horizon n; see Theorem 3 in Gopalan et al. [2017] for details. For an extension of confidence bound-based algorithms to handle sub-Gaussian arms' distributions, see Prashanth and Bhat [2020].

4.2 Thompson Sampling

Another popular class of algorithms for regret minimization is Thompson sampling [Thompson, 1933; Agrawal and Goyal, 2012; Kaufmann et al., 2012; Russo et al., 2018]. Here, one starts with a prior over the set of bandit environments. In each round, as observations are obtained, the prior is updated to a posterior. The agent then samples an environment from the posterior and chooses the action that is optimal for the sampled environment.

The first attempt at using Thompson sampling for riskaverse bandits was by Zhu and Tan [2020] in which the authors applied Thompson sampling to mean-variance bandits for Gaussian and Bernoulli arms. This work is the Thompson sampling analogue of the UCB-based ones for the meanvariance by Sani et al. [2012] and Vakili and Zhao [2015]. For the Gaussian case, Sani et al. [2020] considered sampling the precision (inverse variance) of the Gaussian τi,t of arm i at time t from a Gamma distribution with parameters αi,t and βi,t. Subsequently, the mean of the Gaussian θi,t is sampled from a Gaussian whose mean is set to be the empirical mean and whose variance is the inverse of the number of times arm i has been played. The Gamma and Gaussian are chosen as they are conjugate to the precision and mean of the Gaussian respectively. This algorithm, termed MVTS (for mean-variance Thompson sampling), has expected regret satisfying

where Γi,j := µi -µj is the gap between the means of arms i and j, Γ2i :=maxj=1,...,K(µi -µi)2 , ∆i :=MVi∗ -MVi is the gap between the mean-variance of arm i and the arm with the best MV i∗ , and h(x) := 12 (x - 1 - logx). This bound was shown to be order-optimal in the sense of meeting a problem-dependent information-theoretic lower bound as γ tends to either 0 or diverges to ∞.

Baudry et al. [2021] considered an MAB problem in which the quality of an arm is measured by the CVaR of the reward distribution. They proposed B-CVTS and M-CVTS for continuous bounded and multinominal rewards respectively. Leveraging analysis by [Riou and Honda, 2020], the authors bounded the regret performances of both algorithms and show that they are asymptotically optimal. This is desirable as it improves on Zhu and Tan [2020], albeit for different risk measures, since the level α does not have to tend to its extremal values to be asymptotically optimal. Generalizations of and guarantees for Thompson sampling algorithms for other risk measures are discussed in Chang and Tan [2021].

5 Pure Exploration

We now review existing work on risk-aware pure exploration in MABs. Risk-aware pure exploration problems typically involve finding the best arm (or the best few arms), where the merit of an arm is defined to accommodate a risk measure or a constraint. Pure exploration problems have been studied in two settings, namely, fixed budget and fixed confidence.

5.1 Fixed Budget Algorithms

In the fixed budget setting, the objective is to find the arm (or the best few arms) using a fixed number of arm plays, so as to minimize the probability of misidentification. To be more precise, let n be the fixed "budget", i.e., the total number of arm plays allowed. In the notation of the previous section, let ρ(νk) be the risk measure of interest associated with arm k, and let k∗ be the optimal arm (often assumed to be unique for simplicity). A given arm selection policy π = {πt}nt=1 samples the arms as before, and at the end of the budget, identifies the arm kπ n to be the optimal arm. The merit of the arm selection algorithm is captured by the probability of misidentifying the best arm, which is simply P (kπ n ̸= k∗ ) .

The recent paper by Zhang and Ong [2021] considers pure exploration in a fixed budget setting, where the risk measure is the VaR or quantile at a particular level. Specifically, given a quantile level α, the objective is to identify a set of m arms with the highest VaRα values within a fixed budget n. The authors obtain the empirical VaR estimate using the order statistic X(⌊n(1-α)⌋) as explained in Section 3.3. They then derive exponential concentration bounds for the VaRα estimate under the assumptions that the underlying r.v.s have an increasing hazard rate, and a continuously differential probability density function. A similar VaR concentration result is derived in Prop. 2 of Kolla et al. [2019] under milder assumptions-nevertheless, VaR concentration results necessarily involve constants that depend on the slope of the distribution in the neighbourhood of the α-quantile.

The algorithm proposed in Zhang and Ong [2021] called Q-SAR (Quantile Successive Accept-Reject) adopts the wellknown algorithm of Bubeck et al. [2013] to the risk-aware setting. Q-SAR first divides the time budget n into M - 1 phases, where the number of samples drawn for each arm in each phase is chosen exactly as in [Bubeck et al., 2013] for the risk neutral setting. At each phase p ∈ {1, 2, . . . ,M-1}, the algorithm maintains two sets of arms, namely the active set, which contains all arms that are actively drawn in phase p, and the accepted set which contains arms that have been accepted. During each phase, based on the empirical VaR estimates, an arm is removed from the active set, and it is either accepted or rejected. If an arm is accepted, it is added into the accepted set. When the time budget ends, only one arm remains in the active set, which together with the accepted set, forms the recommended set of best arms. In Theorem 4 of Zhang and Ong [2021] the Q-SAR algorithm is shown to have an exponentially decaying probability of error in the budget n, using the VaR concentration bound.

Other papers on risk-aware pure exploration with fixed budget include Kagrecha et al. [2019] and Prashanth et al. [2020], which consider CVaR as the risk measure. In Prashanth et al. [2020], the authors derive concentration bounds for CVaR estimates, considering separately subGaussian, light-tailed (or sub-exponential) and heavy-tailed distributions. For the sub-Gaussian and light-tailed cases, the estimates are constructed as described in Section 3.3. For heavy-tailed random variables, they assume a bounded moment condition, and derive a concentration bound for a truncation-based estimator. For all three distribution classes, the concentration bounds exhibit exponential decay in the number of samples. The authors then consider the best CVaRarm identification problem under a fixed budget. The algorithm, called CVaR-SR, adopts the well-known successive rejects algorithm from Audibert et al. [2010] to best CVaR arm identification. Exponentially decaying bounds on the probability of incorrect arm identification are derived using the CVaR concentration results. We remark that the Wasserstein distance approach outlined in Section 3.2 gives a direct CVaR concentration bound for sub-Gaussian distributions, but does not seem to extend easily for distributions with heavier tails.

In Kagrecha et al. [2019], the authors consider a risk-aware best-arm identification problem, where the merit of an arm is defined as a linear combination of the expected reward and the associated CVaR. A notable feature in this paper is the distribution obliviousness of the algorithms, i.e., the algorithm (which is again a variant of successive rejects) is not aware of any information on the reward distributions, including tails or moment bounds.

We conclude this subsection by commenting on a common desirable feature in all the algorithms reviewed above. The SR (and SAR) family of algorithms does not require knowledge of the constants in the concentration bounds for their implementation. These constants, which are often distribution dependent, are not known in practice. They appear only in the analysis and the upper bound on the probability of the error. This is in contrast with confidence intervals-based algorithms used for regret minimization, where the distribution dependent constants from the concentration bound do appear in the confidence term, necessitating the knowledge of these constants in the algorithm's implementation.

5.2 Fixed Confidence Algorithms

In fixed confidence pure exploration, the objective is to identify with a high degree of confidence (say with probability at least 1 - δ) the best arm with the smallest possible number of arm plays. A related (and less stringent) objective is called PAC (Probably Approximately Correct), where the objective is to identify as quickly as possible, the set of arms with reward values that are ϵ-close to the best arm, with a confidence level at least 1 - δ. To be more precise, a policy in the fixed confidence setting consists of a stopping time T (defined w.r.t. the filtration σ(Ht-1) from the previous section), and an arm selection rule {πt}Tt=1 . The objective is to ensure that the arm identified at the stopping time T is the 'true best arm' k∗ with probability at least 1 - δ. The figure of merit is the expected sample complexity E[T ], which should be as small as possible for a fixed δ.

In Szorenyi et al. [2015], the authors consider PAC best arm identification, where the quality of an arm is defined in terms of VaR (or quantile) at a fixed risk level. The key technique therein is to employ a sup-norm concentration of the empirical distribution (an improved version of the DKW inequality [Massart, 1990]) to obtain a suitable VaR concentration result. The authors also provide a lower bound for the special case of the VaR at the level 0.75. A lower bound was then generalized to any level α in David and Shimkin [2016]. Notably, David and Shimkin [2016] also proposes two PAC algorithms (namely Maximal Quantile and Doubled Maximal Quantile) that have sample complexity within logarithmic factors of the lower bound.

In David et al. [2018], the authors study a PAC problem with risk constraints. Therein, the objective is to find an arm with the highest mean reward (similar to classic best arm identification), but only among those arms that satisfy a risk constraint. The risk measure is defined in terms of the VaRα(·) of the arms being no smaller than a given β. The authors propose a confidence bounds-based algorithm and prove an upper bound on its sample complexity for sub-Gaussian arms' distribution. The upper bound has a similar form to the guarantee available for the risk-neutral PAC bandits problem [Even-Dar et al., 2006]. They also show a lower bound on the sample complexity that matches the upper bound within logarithmic factors, using specific problem instances inspired by similar approaches in the risk-neutral setting [Mannor and Tsitsiklis, 2004]. An improvement to the algorithm in David et al. [2018] based on the LUCB algorithm [Kalyanakrishnan et al., 2012] was proposed by Hou et al. [2022] recently.

6 Future Challenges

The concentration bounds presented herein based on relating the risk measure to Wasserstein distance are likely to be suboptimal in terms of the constants. One can aim to tighten these bounds, which will have impact and utility beyond the study of MABs. One can explore methods other than the empirical estimators for various risk measures. For example, the potential of using importance sampling for estimating tailbased risk measures such as the CVaR has hitherto not been explored adequately. If improved concentration bounds can be derived, they can be used to obtain improved, problemdependent bounds in both in regret minimization and best arm identification settings. These will also ascertain the asymptotic optimality of various algorithms by comparing the achievable bounds to the information-theoretic limits. From Section 5, we notice that there is generally much less work on pure exploration with risk, and only VaR and CVaR have been explored. Finally, from a philosophical perspective, it is natural to wonder which risk measure to use when faced with a certain application scenario, such as portfolio optimization or clinical trials. A deeper, quantitative understanding of various risk measures and the ensuing implications on the scenario at hand requires more inter-disciplinary research.

Acknowledgements

VT is supported by a Singapore National Research Foundation (NRF) Fellowship (A-0005077-00-00) and Singapore Ministry of Education AcRF Tier 1 grants (A-0009042-0000, A-8000189-00-00, and A-8000196-00-00).