A Survey of Risk-Aware Multi-Armed Bandits

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 mean-variance proposed by Markowitz (1952).

We can recover two extreme cases by considering the extremal values of the risk tolerance $\gamma$. When $\gamma\to\infty$, maximizing $\mathrm{MV}$ simply reduces to maximizing the mean, turning the mean-variance MAB problem into a standard reward maximizing problem. When $\gamma=0$, the mean-variance MAB problem reduces to a variance-minimization problem. When one only has access to samples, one can estimate the mean-variance by using plug-in estimates for the mean and variance. Concentration results for the mean-variance can be found in Zhu and Tan (2020). Here, we present a simpler form of the result.

We now provide a concentration result for the mean-variance, assuming that the underlying r.v. $X$ is sub-Gaussian. Define the empirical mean-variance $\widehat{\mathrm{MV}}_{n}:=\gamma\hat{\mu}_{n}-\hat{\sigma}_{n}^{2}$ where $\hat{\mu}_{n}$ and $\hat{\sigma}_{n}^{2}$ are the sample mean and sample variance respectively.

This result can be proved by using concentration bounds for sub-Gaussian and sub-exponential r.v.s; see, for example Wainwright (2019, Prop. 2.2).

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 (2022) use the notion of Wasserstein distance as the underlying norm in defining a continuous class of risk measures as given below.

Using the EDF $F_{n}$ computed from $n$ i.i.d. samples, we estimate the risk measure $\rho(F)$ satisfying (3) as follows:

$\displaystyle\rho_{n}:=\rho(F_{n}).$

(4)

Conditional Value-at-Risk (Rockafellar and Uryasev, 2000), the spectral risk measure (Acerbi, 2002), and the utility-based shortfall risk (Föllmer and Schied, 2002) are three popular risk measures that are Lipschitz continuous. We describe these risk measures below. For other examples of risk measures satisfying (3), the reader is referred to Cassel et al. (2018) and Bhat and Prashanth (2019).

It is well known (Rockafellar and Uryasev, 2000) that the infimum in the definition of CVaR above is achieved for $\xi=\textrm{VaR}_{\alpha}(X)$, where $\textrm{VaR}_{\alpha}(X)=\inf\{\xi:\mathbb{P}\left(X\leq\xi\right)\geq\alpha\}$ is the Value-at-Risk (VaR) of $X$ at confidence level $\alpha$. 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:

$$\mathrm{CVaR}_{\alpha}(X)=\textrm{VaR}_{\alpha}(X)+\frac{1}{1-\alpha}\mathbb{E}\left[X-\textrm{VaR}_{\alpha}(X)\right]^{+}.$$

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

Let $X_{1},\ldots,X_{n}$ denote i.i.d. samples drawn from the distribution of $X$, and let $\{X_{[k]}\}_{k=1}^{n}$ denote the order statistics of these samples in decreasing order. $\mathrm{CVaR}_{\alpha}(X)$ can be estimated as follows:

$$c_{n,\alpha}=\inf_{\xi\in\mathbb{R}}\bigg{\{}\xi+\frac{1}{n(1-\alpha)}\sum_{i=1}^{n}\left(X_{i}-\xi\right)^{+}\bigg{\}}.$$

(6)

Let $Y$ denote a r.v. with distribution $F_{n}$, the EDF of $X$. Then, it can be shown that

$$c_{n,\alpha}\!=\!\mathrm{CVaR}_{\alpha}(Y)\!=\!\hat{v}_{n,\alpha}+\frac{1}{n(1\!-\!\alpha)}\sum_{i=1}^{n}\left(X_{i}\!-\!\hat{v}_{n,\alpha}\right)^{+},$$

where $\hat{v}_{n,\alpha}=\inf\{x\in\mathbb{R}:F_{n}(x)\geq\alpha\}$ is the empirical VaR estimate, which can been shown to coincide with the order statistic $X_{[\lfloor n(1-\alpha)\rfloor]}$. Thus, the CVaR estimator $c_{n,\alpha}$ coincides with the general template $\rho_{n}=\rho(F_{n})$.

The result below presents a concentration bound for CVaR estimation under a sub-Gaussianity assumption.

The proof of the bound above follows as a corollary to Theorem 1 in lieu of Lemma 2.

We next present an alternative bound with explicit constants under the assumption that the r.v. $X$ is continuous with a density $f$ satisfies a growth condition, which is made precise in the lemma below.

The reader is referred to Prashanth et al. (2020) for a proof of the result above. 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).

Given a risk spectrum $\phi:[0,1]\rightarrow[0,\infty)$, the SRM $M_{\phi}$ associated with $\phi$ is defined by (Acerbi, 2002)

$\displaystyle M_{\phi}(X):=\int_{0}^{1}\phi(\beta)F_{X}^{-1}(\beta)\,\mathrm{d}\beta.$

(8)

$M_{\phi}$ is a coherent risk measure if the risk spectrum is increasing and integrates to 1. Further, $M_{\phi}$ generalizes CVaR, since setting $\phi(\beta)=(1-\alpha)^{-1}\mathbb{I}\left\{\beta\geq\alpha\right\}$ leads to $M_{\phi}=\mathrm{CVaR}_{\alpha}(X)$.

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

Specializing the estimator $\rho_{n}=\rho(F_{n})$ for SRM leads to the following estimator:

$$m_{n,\phi}=\int_{0}^{1}\phi(\beta)F_{n}^{-1}(\beta)\,\mathrm{d}\beta.$$

(10)

Using Lemma 4 and Theorem 1, it is straightforward to obtain the following concentration bound for SRM estimation.

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); 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.

In financial applications, one would be interested in bounding a high loss that occurs with a given low probability. This amounts to bounding the VaR of the loss distribution, at a pre-specified level $\alpha$. VaR as a risk measure is not preferable as it violates sub-additivity, which implies diversification could increase risk. In Artzner et al. (1999), the authors identified certain desirable properties for a risk measure, namely, monotonicity, sub-additivity, homogeneity, and translational invariance. A risk measure satisfyingt these properties is said to be coherent. CVaR is a risk measure that is closely related to VaR, and is also coherent. Convex risk measures Föllmer and Schied (2002) are a further generalization of risk measures beyond coherence, because sub-additivity and homogeneity imply convexity. A popular convex risk measure is UBSR. We introduce this risk measure below.

For a r.v. $X$, the UBSR $S_{\alpha}(X)$ is defined as follows:

$\displaystyle S_{\alpha}(X):=\inf\left\{\xi\in\mathbb{R}:\mathbb{E}\left[l(X-\xi)\right]\leq\alpha\right\},$

(11)

where $l:\mathbb{R}\rightarrow\mathbb{R}$ is a utility function. For the purpose of showing that UBSR is a Lipschitz risk measure, we require that $l$ is Lipschitz. While our results below require no additional assumptions on $l$, we point out that a convexity assumption on $l$ leads to a useful dual representation (Föllmer and Schied, 2002). Further, if the utility is increasing, then the estimation of UBSR from i.i.d. samples can be performed in a computationally efficient manner; see Hu and Zhang (2018).

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

To estimate the UBSR $S_{\alpha}(X)$ from $n$ i.i.d. samples $X_{1},\ldots,X_{n}$, we use the following sample-average approximation to the optimization problem in (11) (also see Hu and Zhang (2018)):

$\displaystyle\min_{\xi\in\mathbb{R}}\;\xi\quad\textrm{ subject to }\quad\frac{1}{n}\sum_{i=1}^{n}l(X_{i}-\xi)\leq\alpha.$

(13)

As in the case of CVaR and SRM, the UBSR estimator provided above is a special case of the general estimate given by $\rho_{n}:=\rho(F_{n})$. Further, the estimation problem in (13) can be solved in a computationally efficient fashion using a bisection method; see Hu and Zhang (2018).

Using Lemma 5 and Theorem 1, we obtain the following concentration bound.

Next, we present an example of a risk measure that is not Lipschitz. Consider a risk measure $\rho(F)=\int_{0}^{\infty}w(1-F(x))\,\mathrm{d}x$, where $w$ is a weight function. Letting $w(p)=\sqrt{p}$, we claim there does not exist a norm $\|\cdot\|$, on the space of distribution functions, such that the following condition holds for all distributions functions $F_{1},F_{2}$ of non-negative r.v.s:

$\displaystyle\left|\rho(F_{1})-\rho(F_{2})\right|\leq L\|F_{1}-F_{2}\|.$

(14)

Consider two Bernoulli distributions $F_{1}$ and $F_{2}$, with parameters $p_{1}$ and $p_{2}$, respectively. It is easy to see that

$$\rho(F_{1})=w(p_{1})\;\textrm{ and }\;\rho(F_{2})=w(p_{2}).$$

Setting $p_{1}=4\epsilon$ and $p_{2}=\epsilon$, for some $\epsilon>0$, we claim that the condition in (14) does not hold for $F_{1}$ and $F_{2}$. To see this, observe that the left-hand side of (14) is $\sqrt{4\epsilon}-\sqrt{\epsilon}=\sqrt{\epsilon}$. On the other hand, $(F-G)(x)=\epsilon\mathbbm{1}_{[0,1)}(x)$. By the homogeneity property of norms, $\|F-G\|$ must scale linearly with $\epsilon$, and hence the inequality in (14) cannot hold for sufficiently small $\epsilon$. Thus this risk measure $\rho(\cdot)$ violates the Lipschitz condition in Definition 5.

While the above measure appears contrived, it is not the case. The $\rho(\cdot)$ defined above is closely related to a risk measure based on cumulative prospect theory, where one employs a weight function to distort cumulative probabilities. We describe such a risk measure in the next section.

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)

	$\displaystyle\mathcal{C}(X)$	$\displaystyle:=\int_{0}^{\infty}w^{+}\left(\mathbb{P}\left(u^{+}(X)>z\right)\right)\,\mathrm{d}z$
		$\displaystyle\qquad-\int_{0}^{\infty}w^{-}\left(\mathbb{P}\left(u^{-}(X)>z\right)\right)\,\mathrm{d}z,$		(15)

where $u^{+},u^{-}:\mathbb{R}\rightarrow\mathbb{R}_{+}$ are the utility functions that are assumed to be continuous, with $u^{+}(x)=0$ when $x\leq 0$ and increasing otherwise, and with $u^{-}(x)=0$ when $x\geq 0$ and decreasing otherwise, $w^{+},w^{-}:[0,1]\rightarrow[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 $\{X_{i}\}_{i=1}^{n}$, 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:

$\displaystyle\overline{\mathcal{C}}_{n}\!=\!\int_{0}^{\infty}\!\!\!\!w^{+}\left(1\!-\!F_{n}^{+}\left(x\right)\right)\,\mathrm{d}x\!-\!\int_{0}^{\infty}\!\!\!\!w^{-}\left(1\!-\!F_{n}^{-}\left(x\right)\right)\mathrm{d}x,$

(16)

The integrals above can be computed using the order statistics; see Jie et al. (2018). More precisely, let $X_{[1]}\leq X_{[2]}\leq\ldots\leq X_{[m]}$ denote the order statistics. Then, the first and second integrals in (16), denoted by $\overline{\mathcal{C}}_{m}^{+}$ and $\overline{\mathcal{C}}_{m}^{-}$, respectively, are estimated as follows:

	$\displaystyle\overline{\mathcal{C}}_{n}^{+}$	$\displaystyle:=\sum_{i=1}^{n}u^{+}(X_{[i]})\bigg{(}w^{+}\!\Big{(}\frac{n+1-i}{n}\Big{)}\!-\!w^{+}\!\Big{(}\frac{n-i}{n}\Big{)}\bigg{)},$
	$\displaystyle\overline{\mathcal{C}}_{n}^{-}$	$\displaystyle:=\sum_{i=1}^{n}u^{-}(X_{[i]})\bigg{(}w^{-}\Big{(}\frac{i}{n}\Big{)}-w^{-}\Big{(}\frac{i-1}{n}\Big{)}\bigg{)}.$

We now present a concentration result for CPT-value estimation assuming bounded support for the underlying distribution; see Prashanth et al. (2016); Jie et al. (2018) for the proofs. We start by stating some assumptions.

The proof is based on the Dvoretzky–Kiefer–Wolfowitz (DKW) inequality, which establishes concentration of the EDF around the true distribution. For the sub-Gaussian case, one can use a truncated CPT-value estimator, and establish an exponentially decaying tail bound. In this case, we use a truncated CPT-value estimator (Bhat and Prashanth, 2019). For a given truncation level $\tau_{n}$ (to be specified later), let $\left(F_{n}|_{\tau_{n}}\right)^{+}$ and $\left(F_{n}|_{\tau_{n}}\right)^{-}$ denote the truncated EDFs formed from the samples $\{u^{+}(X_{i})\}_{i=1}^{n}$ and $\{u^{-}(X_{i})\}_{i=1}^{n}$, respectively. Using the truncated EDFs, the CPT-value is estimated as follows:

	$\displaystyle C_{n}=$	$\displaystyle\int_{0}^{\tau_{n}}w^{+}(1-\left(F_{n}|_{\tau_{n}}\right)^{+}(x))\,\mathrm{d}x$
		$\displaystyle\quad-\int_{0}^{\tau_{n}}w^{-}(1-\left(F_{n}|_{\tau_{n}}\right)^{-}(x))\,\mathrm{d}x.$		(18)

In comparison to (16), we have used complementary (truncated) EDFs in the estimator defined above.

We present an adaptation Risk-LCB of the well-known UCB algorithm (Auer et al., 2002) to handle an objective based on abstract risk measures $\rho$. 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 $\delta\in[\exp(-n),1]$, with probability $\geq 1-\delta$,

$$|\rho_{m}-\rho(X)|\leq\frac{L\sigma\left(\sqrt{256\mathsf{e}\log(\frac{1}{\delta})}+512\right)}{\sqrt{m}},$$

where $\rho_{m}=\rho(F_{m})$ is an $m$-sample estimate of the risk measure $\rho(X)$. The range of $\delta$ is restricted to $[\exp(-n),1]$ due to the following constraint on $\epsilon$ in Theorem 1:

$\displaystyle\frac{512\sigma}{\sqrt{n}}<\frac{\epsilon}{L}<\frac{512\sigma}{\sqrt{n}}+16\sigma\sqrt{\mathsf{e}}.$

(19)

For the classic bandit setup with a expected value objective, the finite sample analysis provided by Auer et al. (2002) chose to set $\delta=t^{-4}$ for obtaining a sub-linear regret guarantee. In our setting, we set $\delta=\frac{8}{t^{4}}$ as this choice satisfies the constraint coming from (19), in turn facilitating the application of the high confidence guarantee on $\rho_{m}$ given above. Under this choice of $\delta$, in any round $t$ of Risk-LCB and for any arm $k\in\{1,\ldots,K\}$, we have

	$\displaystyle\mathbb{P}\left(\rho(i)\in[\rho_{i,T_{i}(t-1)}\pm w_{i,T_{i}(t-1)}]\right)\geq 1-8t^{-4},\textrm{ where}$
	$\displaystyle\qquad\quad w_{i,T}:=\frac{L\sigma\left(32\sqrt{\mathsf{e}\log t}+512\right)}{\sqrt{T}}.$		(20)

In the above, $\rho_{i,T_{i}(t-1)}$ is the estimate of the risk measure for arm $i$ computed using $\rho_{n}=\rho(F_{n})$ from $T_{i}(t-1)$ samples.

The Risk-LCB algorithm would play all arms once in the initialization phase, and in rounds $t\geq K+1$, play an arm $A_{t}$ according to the following rule:

$$A_{t}=\operatorname*{arg\,min}\limits_{1\leq i\leq K}\left(\textrm{LCB}_{t}(i):=\rho_{i,T_{i}(t-1)}-w_{i,T_{i}(t-1)}\right).$$

This bound mimics that of risk-neutral UCB except that the $\Delta_{i}$’s depend on $\rho$.

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\big{(}\sum_{i:\Delta_{i}>0}\frac{\log n}{\Delta_{i}^{{2}/{\alpha}-1}}\big{)}$, where $\alpha$ is the Hölder 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 (2022).

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 risk-averse 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 mean-variance by Sani et al. (2012) and Vakili and Zhao (2015). For the Gaussian case, Zhu and Tan (2020) considered sampling the precision (inverse variance) of the Gaussian $\tau_{i,t}$ of arm $i$ at time $t$ from a Gamma distribution with parameters $\alpha_{i,t}$ and $\beta_{i,t}$. Subsequently, the mean of the Gaussian $\theta_{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

$\displaystyle\!\limsup_{n\to\infty}\frac{R_{n}^{\rho}}{\log n}\!\leq\!\sum_{i=2}^{K}\!\max\bigg{\{}\frac{2}{\Gamma_{1,i}^{2}},\frac{1}{h(\frac{\sigma_{i}^{2}}{\sigma_{1}^{2}})}\bigg{\}}\big{(}\Delta_{i}\!+\!2\overline{\Gamma}_{i}^{2}\big{)},\!$

(21)

where $\Gamma_{i,j}:=\mu_{i}-\mu_{j}$ is the gap between the means of arms $i$ and $j$, $\overline{\Gamma}_{i}^{2}:=\max_{j=1,\ldots,K}(\mu_{i}-\mu_{i})^{2}$, $\Delta_{i}:=\mathrm{MV}_{i^{*}}-\mathrm{MV}_{i}$ is the gap between the mean-variance of arm $i$ and the arm with the best MV $i^{*}$, and $h(x):=\frac{1}{2}(x-1-\log x)$. This bound was shown to be order-optimal in the sense of meeting a problem-dependent information-theoretic lower bound as $\gamma$ tends to either $0$ or diverges to $\infty$.

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 novel 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 $\alpha$ 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, such as the empirical distribution performance measures (EDPMs) and distorted risk functionals (DRFs) proposed in Cassel et al. (2018) and Huang et al. (2021) respectively are discussed in Chang and Tan (2022).

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 $\rho(\nu_{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 $\pi=\{\pi_{t}\}_{t=1}^{n}$ samples the arms as before, and at the end of the budget, identifies the arm $k_{n}^{\pi}$ 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 $\mathbb{P}\left(k_{n}^{\pi}\neq k^{*}\right).$

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 $\alpha,$ 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_{(\lfloor n(1-\alpha)\rfloor)}$ 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 $\alpha$-quantile.

The algorithm proposed in Zhang and Ong (2021) called Q-SAR (Quantile Successive Accept-Reject) adopts the well-known 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\in\{1,2,\dots,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 sub-Gaussian, 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 CVaR-arm 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.

In fixed confidence pure exploration, the objective is to identify with a high degree of confidence (say with probability at least $1-\delta$) 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 $\epsilon$-close to the best arm, with a confidence level at least $1-\delta.$ More precisely, a policy in the fixed confidence setting consists of a stopping time $T$ (defined w.r.t. the filtration $\sigma(\mathcal{H}_{t-1})$ from the previous section), and an arm selection rule $\{\pi_{t}\}_{t=1}^{T}.$ 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-\delta.$ The figure of merit is the expected sample complexity $\mathbb{E}[T],$ which should be as small as possible for a fixed $\delta.$

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 $\alpha$ 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 the classic best arm identification problem), but only among those arms that satisfy a risk constraint. The risk measure is defined in terms of the $\textrm{VaR}_{\alpha}(\cdot)$ of the arms being no smaller than a given $\beta.$ The authors propose a confidence interval-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.

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-00-00, A-8000189-00-00, and A-8000196-00-00).