Sample Complexity of Risk-Averse Bandit-Arm Selection

1 Introduction

Multiarmed bandit problems arise in diverse applications such as tuning parameters, Internet advertisement, auction mechanisms, adaptive routing in networks, project management, and clinical trials. The goal is typically to find a policy, that is, a sequence of decisions, that maximizes the cumulative expected reward [Lai and Robbins, 1985]. The essence of the problem, and its principal challenge, lies in the uncertainty of rewards. Due to the risk-averse nature of users in many applications, a solution with guarantees in expectation is often unsatisfactory, i.e., the best solution may be the one with smallest risk as opposed to highest mean.

Risk measures have recently received renewed attention in the financial mathematics and optimization literature [Artzner et al., 1999; Rockafellar, 2007]. However, until now, these risk measures have been rarely applied to multiarmed bandit problems. One reason is that risk analysis often assumes distributional knowledge of the underlying uncertainty, whereas in bandit models, this knowledge is unavailable a priori. The uncertainty must be estimated before making risk-averse decisions. Another reason is that the complexity of estimating risk associated with sequential decision-making increases greatly as the number of decisions increases. This work addresses both of these challenges.

∗ IBM Research-Ireland, Damastown, Dublin 15, Ireland, jiayuanyu@ie.ibm.com. This work was supported in part by the EU FP7 project INSIGHT under grant 318225.

†Department of Computer Science and Engineering, Texas A&M University, College Station, TX 77843-3112 USA, nikolova@tamu.edu. This work was partly done while the author was visiting IBM Research-Ireland and was supported in part by NSF CCF 1216103.

Although the underlying randomness is a priori unknown in many real problems, it is useful to consider notions of risk measures with respect to this unknown randomness. In this work, we consider a data-driven approach to risk aversion, wherein we estimate the true risk measure from a sequence of observations of the randomness. One of our contributions is to quantify the effect of finite samples on the residual risk. We do so for modern and traditional risk measures: the valueat-risk (V@R), the average value-at-risk 1 (AV@R), and the mean-variance risk. This work is the first to apply the AV@R to bandit problems, which is widely used elsewhere because an important class of convex risk measures can be expressed as its integral. Our notion of risk is defined differently from previous work on risk-averse bandits.

When the objective is the expected reward-as in most of the literature on bandit problems, by linearity of expectation, the cumulative expected reward is simply the sum of singleperiod expected rewards. In contrast, the instantaneous or single-period risk and cumulative or multi-period risk can vary greatly in complexity. A risk-averse objective is nonlinear and does not typically decompose into a sum over singleperiod risks. When comparing different arms, it is natural to compare their single-period risks; however, these will not always imply the correct preference with respect to a multiperiod risk objective.

Example 1.1 below gives insight into the subtlety of measuring risk over multiple periods. It demonstrates the following counter-intuitive fact: one arm may be better than another in terms of the single period risk , while it may be worse over two or more periods. In addition, even if arm 1 is better than arm 2 in a single period, pulling arm 1 twice may be worse than consecutively pulling arm 1 and arm 2. In contrast to the expected reward criterion, one cannot infer multi-period risk bounds from single-period risk bounds.

1 The average value-at-risk is also called expected shortfall and conditional value-at-risk.

Example 1.1 (Lack of translation symmetry). Consider two arms and two periods. The first arm has rewards X1,X2 in periods 1, 2 respectively and the second arm has rewards Y1, Y2. Let X1, X2 be independent and identically distributed according to the normal distribution N(μ1, σ2 1 ), whereas Y1, Y2 are i.i.d. N(μ2, σ2 2 ). For normal random variables, both the V@Rβ and the AV@Rβ, with probability level β ⩾ 0.5, reduce to a linear combination of mean and standard deviation: ρ(X) = -E[X] + λ√VAR[X], where λ is only a function of β (cf. [Rockafellar and Uryasev, 2000, Proof of Proposition 1]). Thus, the single period risk measures are ρ(X1) = -μ1 + λσ1 for arm 1 and ρ(Y1) = -μ2 + λσ2 for arm 2.

Let ϵ > 0 be fixed. Suppose that σ1 = 1, σ2 = 2, and μ1 = λ, μ2 = 2λ-ϵ, then we have ρ(X1) = -μ1 +λσ1 = 0 and ρ(Y1) = -μ2 + λσ2 = ϵ. Moreover, by independence, we have ρ(Y1 + Y2) = -2μ2 + λ√2σ2 2 = 2(√2-2)λ+2ϵ, ρ(X1 + Y2) = -μ1 - μ2 + λ√σ2 1 + σ2 2 = (√5 - 3)λ + ϵ, ρ(X1 + X2) = -2μ1 + λ√2σ2 1 = (√2 - 2)λ. It is easy to verify that, for all ϵ > 0 and λ > 6ϵ, we have ρ(X1) < ρ(Y1) and ρ(X1 + X2) > ρ(X1 + Y2) > ρ(Y1 + Y2). We conclude that for two periods, we incur less risk (V@R and AV@R) by choosing arm 2 twice; whereas for a single period, it is preferable to choose arm 1.

The following is an engineering example of a bandit problemwhere risk is important.

Example 1.2 (Communication channel selection). Consider a transmitter with access to a number of communication channels (e.g., different media and spectrum frequencies). Its task is to choose a single channel to transmit one important message so as to minimize the risk corresponding to the probability that the error rate exceeds a threshold λ-instead of minimizing the expected error rate. The channel error rates are random with unknown distribution, but can be sampled. The question is: How many samples are required to find a channel satisfying some prescribed confidence guarantees on its risk?

We proceed as follows. In Sections 2 and 3, we present our bandit model and discuss it with respect to related literature. In Section 4, we present PAC bounds on the single-period risk of a greedy arm-selection policy with respect to an appropriate risk estimate. Section 5 presents our main result: a PAC bound for multi-period risk using a new algorithm and under an additional assumption. Section 6 illustrates empirically the distinction between risk-averse and expected-reward bandit problems. We discuss open problems in Section 7.

2 Problem formulation

Let {1, . . . , n} denote a set of arms-or possible choices of actions. Let {Xi t : i = 1, . . . , n, t = 1, 2, . . .} denote the real-valued rewards for pulling the arms i = 1, . . . , n at time instants t = 1, 2, . . . Let d1, . . . , dn denote time-invariant probability density functions. We assume that for every fixed arm i, the rewards {Xi1 ,Xi2 , . . .} are independent and identically distributed according to di. Let (Ω,F, P) denote the probability space generated by the arm rewards. In contrast to most of the literature on risk measures, we assume that Plikewise the densities d1, . . . , dn-are fixed but unknown.

Let it denote the action chosen by the decision-maker at time t. Let μi denote the expected reward of arm i-with density di. In the traditional bandit problem formulation, we are interested in algorithms for choosing the sequence of arms {it} with expected regret guarantees of the form

Let Y denote the set of bounded random variables, and let ρ : Y → R denote a risk measure. We discuss specific types of risk measures in the coming sections. We are interested in a risk-averse version of bandit problems, where one objective is to give a PAC bound on the single-period risk error ∣∣∣minj=1,...,n ρ(Xj 1 ) - ρ(Xi∗ 1 )∣∣∣ of the chosen arm i∗ . Another objective is to give a PAC bound on the multi-period risk error of a sequence of actions i1, . . . , iτ :

In this paper, our notion of multi-period risk assumes that the arm choices for time instants 1, . . . , τ are made at time 1, while ignoring outcomes after time 1. An alternative would be to consider risk associated with policies that act at time t according to all observed outcomes up to time t - 1. Under some assumptions-particularly, when the decision horizon τ is short compared to the number of past observations, these risk measures are close.

Remark 1 (Notation). Since {Xi1 , Xi2 , . . .} are identically distributed, we have ρ(Xi1 ) = ρ(Xi2 ) = . . ., and we write ρ(i) to denote ρ(Xi1 ).

For every fixed arm i, let X i denote a set of observations or samples of the rewards of arm i. Throughout the paper, we assume that these sets contain the same number N of samples, i.e., ∣∣X 1 ∣∣ = . . . = |X n | = N. The number N is called the sample complexity; it represents the number of samples that is sufficient to give a certain guarantee.

3 Related work

The notion of risk has been widely studied in finance, engineering, and optimization, yet there is no single agreed-upon definition for it. It is generally meant to express and quantify one's preferences over a set of random outcomes. Two main approaches to modeling risk have been via utility functions [Neumann and Morgenstern, 1944] and via the meanvariance framework [Markowitz, 1952]. More recently, due to a variety of paradoxes and pitfalls of the traditional approaches, an axiomatic approach to risk has been proposed for applications in finance [Artzner et al., 1999]. This approach to risk-aversion spans both static and sequential decision problems, such as [Artzner et al., 1999] in financial hedging; [Le Tallec, 2007; Osogami, 2011] in Markov decision problems; [Shapiro and Ahmed, 2004] in stochastic and robust optimization. Both the traditional and modern approaches have been comprehensively described in multiple surveys (cf. [Schied, 2006; Rockafellar, 2007]).

Multiarmed bandit problems have been studied in a variety of settings, including the Markovian (rested and restless), stochastic and adversarial settings. For surveys on bandit problems, we refer the reader to [Gittins et al., 2011; Cesa-Bianchi and Lugosi, 2003]. Two types of results are found in the literature: results on the average regret (i.e., in a regret-minimization setting [Lai and Robbins, 1985]) and results on the sample complexity (i.e., in a pure-exploration setting [Even-Dar et al., 2002; Bubeck et al., 2011]). Our work is of the second type. It is related to work on sample complexity of bandit arm-selection [Even-Dar et al., 2002; Kalyana et al., 2012], which is also known as pure exploration or best-arm identification [Audibert et al., 2010; Gabillon et al., 2012].

As far as we know, this is the first work to consider the sample complexity of bandit arm-selection in a risk-averse setting. Risk aversion in bandit problems has previously been studied in two settings, Markovian [Gittins et al., 2011] and stochastic [Lai and Robbins, 1985]. In the Markovian setting, [Denardo et al., 2007; Chancelier et al., 2009] consider a one-armed bandit problem in the setting of Gittins indices and model risk with concave utility functions. In the stochastic setting, the notion of risk has been limited to empirical variance [Audibert et al., 2009; Sani et al., 2012]. Besides this limitation, our notion of risk is also very different from this previous work in its definition. In [Audibert et al., 2009; Sani et al., 2012], the risk measure assigns real values to the decision-maker's policies (i.e., confidence-bound algorithms) and guarantees are given for the regret in retrospect. Our risk measure assigns a real value to random variables, i.e., rewards of individual arms or deterministic sequences of arm choices, and guarantees are given on the sample complexity of various estimators. This is more in line with the risk notions of the finance and optimization literature. Our results on the sample complexity of estimating the V@R and the AV@R are new. Our results on the mean-variance risk complement those of [Sani et al., 2012].

Our notion of data-driven risk, estimated using random samples, is similar to [Jones and Zitikis, 2003; Brown, 2007; Kim and Hardy, 2009]: [Jones and Zitikis, 2003] presents an empirical study of bootstrapped risk estimators; we present an alternative AV@R estimator to that of [Brown, 2007] that has comparable sample-complexity guarantees, but is more efficient by virtue of not solving a minimization problem; [Kim and Hardy, 2009] estimate tail-deviation risk measures using L-statistics and show asymptotic properties of the estimators. In this paper, we consider different risk measures and present non-asymptotic results. Our sample complexity results on estimating risk measures is also reminiscent of black-box models [Shmoys and Swamy, 2006; Nemirovski and Shapiro, 2006]. However, the notion of risk-aversion in [Shmoys and Swamy, 2006] is limited to V@R and the setting is that of the two-stage recourse model. For [Nemirovski and Shapiro, 2006], the setting is chanceconstrained optimization and the sample complexity is analyzed for given confidence and reliability parameters.

Even when the underlying probability distribution is known, some risk measures are hard to compute and approximations are used. For instance, methods such as parametric estimation, Monte Carlo simulation, etc. have been used extensively to approximate the risk measures (cf. [Kreinin et al., 1998]). [Vanduffel et al., 2002] presents techniques for approximating risk measures of a sum of random variables with known lognormal distributions. In our setting, the multiperiod risk is defined for random variables with arbitrary and unknown distributions.

In this paper, we first want to raise awareness of the need to incorporate risk in machine learning problems-the experiments of Section 6 illustrate this. Secondly, we investigate how risk affects the underlying theory compared to the classical expected-reward setting. We show where existing techniques can give sample complexity guarantees in the new risk-averse formulations and where new techniques are needed. In particular, we present the gap in complexity between the single-period and the multi-period risk-averse bandit problems. The latter is hard even with an additional assumption of independence between arms. Our main contribution is to present an arm-selection algorithm (the CuRisk algorithm) with a PAC guarantee on its multi-period risk.

4 Single-period risk

In this section, we present results on the sample complexity of estimating single-period risk, and derive PAC bounds for the single-period best-arm identification problem. The results for the mean-variance risk can be deduced from well-known results in the literature. We present them separately because they do not require an assumption of independence between arms (cf. Assumption 5.1). We consider the multi-period case in the next section.

4.1 Value-at-risk

Let λ be given and fixed. In this section, we consider the value-at-risk, for every arm i:

where qi is the right-continuous quantile function 2 of Xi1 .

Suppose that up to time T, each arm is sampled N times. Let Xi1 , . . . ,XiN denote the sequence of rewards generated by arm i. Let Xi (1) ⩽ . . . ⩽ Xi (N) denote a reordering of the random variables {Xi1 , . . . ,XiN }, where Xi (k) is the k-th order statistic of the sequence {Xi1 , . . . ,XiN }. We consider the following V@R estimators for all i:

where each ̂Xiλ is the following λ-quantile estimator 3 :

We define our V@R estimator as ̂ ρVλ (i) = - ̂Xiλ .

Assumption 4.1 (Differentiable reward density). For each arm i, the reward probability density functions di are continuously differentiable.

2 Formally, qi(λ) = inf{x ∈ R : Fi(x) > λ}, where Fi is the distribution function of Xi1.

3 With slight modifications, we can derive similar results with other quantile estimators, such as the Wilks estimator.

Next, we bound the single-period risk error of the armchoice i∗ ∈ argmini=1,...,n ρVλ (i). Recall that although ρVλ (i) is a scalar for every fixed i, the arm-choice i∗ is a random variable and ρVλ (i∗ ) is a function of i∗ . All proofs appear in the appendix of [Yu and Nikolova, 2013].

Theorem 4.1 (V@R PAC bound). Suppose that Assumption 4.1 holds. Suppose that there exist D and D′ such that di(z) ⩽ D and d′i (z) ⩽ D′ for all z ∈ R and all i, and that

If i∗ ∈ argmini=1,...,n ̂ ρVλ (i), then arm i∗ is (ε, δ)- optimal with respect to the V@R risk measure, i.e., ∣∣minj=1,...,n ρVλ (j) -ρVλ (i∗ )∣∣ ⩽ ε w.p. 1- δ.

Remark 2. In Theorem 4.1, the sample complexity T is of the order of Ω(nε-2 δ-1 ). By comparison, the sample complexity for the bandit problem with expected rewards is of the order of Ω(ε-2 log(δ-1 )) [Even-Dar et al., 2002]. We can easily improve the suboptimal dependence in the number of arms n by using the arm-elimination method of [Even-Dar et al., 2002]. Our V@R estimator is very distinct from the empirical mean or distribution estimates in [Even-Dar et al., 2002] and elsewhere in the literature, which allow the use of particular concentration inequalities to obtain a logarithmic dependence in δ-1 .

Remark 3 (Lower bound). If X is a Bernoulli random variable with mean p, then the λ-quantile of X is qX(λ) = 1[λ⩾p], so that estimating the quantile is at least as hard as estimating the mean p. Hence, we can derive a lower bound of Ω(nε-2 log δ-1 ) on the sample complexity by using the approach of [Mannor and Tsitsiklis, 2004].

4.2 Average value-at-risk

Modern approaches to risk measures [Artzner et al., 1999] advocate the use of convex risk measures, which capture the fact that diversification helps reduce risk. In this section, we consider only one instance of convex risk measures: the average value-at-risk. Nonetheless, it can be shown that an important subset of convex risk measures (i.e., those continuous from above, law invariant, and coherent) can be expressed as an integral of the AV@R (cf. [Schied, 2006]). Guarantees can be obtained for those risk measures by using the approach of this section.

The AV@R has the following two equivalent definitionsfirst, as an integral of V@R:

and second, as a maximum over a set of distributions: ρAλ (X) = maxQ∈Qλ(P) -EQX, where Qλ(P) is the set of probability measures {Q : dQ dP ⩽ 1/λ}. Depending on the choice of definition, we can estimate the AV@R either via quantile estimation or density estimation. In this section, we adopt the first definition and introduce the following estimator using a Riemann sum of quantile estimator of (2):

We define our AV@R estimator as ̂ ρAλ (i) = - ̂ Y i λ . Our estimator is distinct from and computationally more efficient than the one introduced in [Brown, 2007].

The following result bounds the single-period risk of a simple arm-selection policy.

Theorem 4.2 (AV@R PAC bound). Suppose that the assumptions of Theorem 4.1 hold. Suppose that the rewards are bounded such that ∣∣Xi t ∣∣ ⩽ M almost surely, for every arm i and time t. Suppose that

where λ′ denotes the smallest real number greater than λ such that λ′N is an integer. If i∗ ∈ argmini=1,...,n ̂ ρAλ (i), then arm i∗ is (ε, δ)-optimal with respect to the AV@R risk measure, i.e., ∣∣minj=1,...,n ρAλ (j) -ρAλ (i∗ )∣∣ ⩽ ε w.p. 1-δ.

4.3 Mean-variance risk

In this section, we consider the mean-variance risk measure

where μ(i) and σ2 (i) denote the mean and variance of arm i. The mean-variance risk measure has been used in risk-averse problem formulations in a variety of applications in finance and reinforcement learning [Markowitz, 1952; Mannor and Tsitsiklis, 2011; Sani et al., 2012].

Let λ be given and fixed. We assume that we are given N samples Xi1 , . . . ,XiN for every arm i. We look at the meanvariance risk measure. We employ the risk estimate

where ̂ μ(i) and ̂ σ2 (i) denote the sample-mean and the unbiased variance estimator ̂ σ2 (i) = 1 N-1 ∑Nk=1 (Xik - ̂ μ(i))2 .

The following theorem gives a single-period risk error bound for the arm-choice i∗ ∈ argmini=1,...,n ̂ ρMλ (i).

Theorem 4.3 (MV PAC bound). Suppose that there exist A, B such that P(Xi t ∈ [A, B]) = 1 for all i. Suppose that N is at least

If i∗ ∈ argmini=1,...,n ̂ ρMλ (i), then arm i∗ is (ε, δ)- optimal with respect to the mean-variance risk, i.e., ∣∣minj=1,...,n ρMλ (j) -ρMλ (i∗ )∣∣ ⩽ ε w.p. 1- δ.

5 From single- to multi-period risk

Obtaining multi-period risk bound estimates from singleperiod risk is not obvious (cf. Example 1.1). We present in this section multi-period risk bounds for the V@R. The same method can be extended to other risk measures. For instance, by employing the averaging and Riemann approximation method of Section 4.2, we can obtain multi-period risk bounds for the AV@R.

One naive approach to compare the risk of two consecutive actions is to estimate ρ(X1 + . . . +Xτ ) for all sequences of arm-choices, but this method requires a number of samples exponential in the time-horizon. We can drastically cut the number of samples when the arms' rewards are mutually independent. In that case, we can estimate the density of X1 + . . . + Xτ by constructing histogram density estimates for each Xi individually, performing the convolution of these histograms (in the transform domain) to obtain a density estimate for X1 + . . . + Xτ , and then computing quantile estimates from the latter. Hence, in this section, we make the additional assumption that the rewards are independent across different arms. The exposition is also simplified by assuming that the rewards take a finite number of values instead of Assumption 4.1.

Assumption 5.1 (Arm-wise independence). For every fixed time t, the arms rewards {X1 t , . . . ,Xn t } are independent.

Assumption 5.2 (Discrete-valued rewards). Let K be a fixed integer. For every arm i, the rewards Xi t take values in a finite set {vk ∈ R : k = 1, . . . ,K} and there exists a constant γ ≜ γK > 0 such that the probability mass function satisfies di(k) ⩾ γ for all k = 1, . . . ,K.

The results of this section extend easily to the case where the rewards take values in interval [A, B]; in this case, we partition the subset [A, B] into K intervals u1, . . . , uK such that each interval has length |B -A| /K, and take the midpoint of each interval.

We begin by considering the special case of the meanvariance risk measure ρMλ . We can easily derive a multiperiod PAC risk bound, provided that the rewards are independent between different arms.

Corollary 5.1 (Multi-period MV PAC bound). Suppose that the assumptions of Theorem 4.3 hold. Suppose further that Assumption 5.1 holds. If the arm i∗ ∈ argmini=1,...,n ρMλ (i) is chosen repeatedly at time periods 1, . . . , τ , then, with probability 1 - δ, we have

However, for more general risk measures, more complex techniques are needed to bound the multi-period risk. For the case of the V@R risk measure, we present the CuRisk Algorithm of Figure 1. This algorithm first estimates the probability density of each arm's reward, then solves an allocation problem with respect to the risk measure of interest. The algorithm can be adapted to other risk measures by replacing the ALC-VAR step with corresponding allocation problems. For instance, we can modify the CuRisk Algorithm to tackle the case of the AV@R risk measure using the method of Section 4.2.

The CuRisk Algorithm works as follows. For every arm i, ̂ di denotes the empirical probability mass function or histogram. The function ̂Dj in Eq. (3) denotes the probabilitygenerating function of Xj 1 , which is the z-transform of the

• 1: Input: A set of arms {1, . . . , n}, integers N > 0 and K > 0, scalar r ∈ (0, 1), and sets of reward samples X 1 , . . . ,X n .
• 2: Output: Arm choices i1, . . . , iτ .
• 3: for all i = 1, . . . , n do
• 4: Compute empirical histogram estimates ̂ di:

• 5: end for
• 6: Solve the allocation problem (ALC-VAR):

where ι = √-1, ℜ denotes the real-part operator, and ̂Dℓ is the z-transform:

• 7: for t = 1, . . . , τ do
• 8: Output each arm j exactly m∗j times, where (m∗1 , . . . ,m∗n ) is a solution to ALC-VAR.
• 9: end for

Figure 1: CuRisk Algorithm for V@R

probability-mass function ̂ dj. The decision variables of the optimization problem ALC-VAR are integers m1, . . . ,mn and a real number x. The damping parameter r of the CuRisk Algorithm affords a trade-off between round-off errors in the constraints of ALC-VAR and the generality of the following multi-period risk bound.

One of the features of the CuRisk Algorithm is that it does not estimate the risk for each possible sequence of actions ⃗a, since this would require a number of times exponential in the length of ⃗a. Instead, the CuRisk Algorithm solves an optimization problem ALC-VAR. Another important feature of the CuRisk Algorithm is that the computational complexity does not increase with the time horizon τ, which is guaranteed in the following theorem. This feature comes from the use of the product of probability-generating functions to approximate a convolution of τ probability mass functions.

Theorem5.2 (Multi-period V@RPAC bound). Suppose that Assumptions 5.1 and 5.2 hold, and that

Suppose that the arm choices i1, . . . , iτ follow the CuRisk Algorithm. Then, with probability 1 - δ, we have

Although we have bounded the sample-complexity of the multi-period problem, the computational complexity remains high due to the non-linear constraint and integer-valued decision variables of ALC-VAR. A possible relaxation is to first solve the real-valued problem and follow-up by rounding.

6 Empirical results

In this section, we first show how different risk measures induce different optimal decisions in the single-period case. Then, we illustrate the complexity of the multi-period case. Details of these examples appear in the appendix of [Yu and Nikolova, 2013].

For the single-period case, we consider a set of five arms with different reward distributions, but the same mean. The reward distributions are: uniform, normal, exponential, Pareto, and Beta. Figure 2 illustrates the convergence of the single-period AV@R estimates for an arm with Pareto reward distributions. Figure 3 shows how different arms are optimal for a single period with respect to different risk measures.

Next, we consider a three-period case with three arms. The first arm generates i.i.d. rewards with values -10 and -20 with probabilities 0.9 and 0.1; the second arm values -5 and -15 with equal probability 0.5; the third arm generates a deterministic reward -14. Figure 4 shows that choosing each of the three arms once minimizes the V@R for a parameter λ ∈ (0.05, 0.1). This shows that non-intuitive solutions can arise from even the simplest of multi-period riskminimization problems.

7 Discussion

To summarize, for single-period risk, Ω(n2 δ-1 ε-2 ) samples are sufficient for a simple policy to find an (ε, δ)- optimal arm with respect to the V@R and AV@R. With respect to the mean-variance risk, Ω(n log(nδ-1 )ε-2 ) samples are sufficient. For the multi-period risk over τ periods, Ω(nτ 2 log(τnτ δ-1 )ε-2 ) samples are sufficient for the CuRisk Algorithm to find an (ε, δ)-optimal sequence of τ arm choices. Using sampling methods that quickly eliminate arms with high risk and low variance [Even-Dar et al., 2002], it is possible to reduce the dependence in the number n of arms.

A number of questions remain open. Is it possible to devise an algorithm with similar PAC risk bounds that do not depend on the problem parameters D and D′ of Theorem 4.1? This could, for instance, be achieved by estimating these parameters in parallel. What are lower bounds on the sample complexity for various risk measure estimates? Can we extend our results for V@R and AV@R to the setting of [Sani et al., 2012], where risk measures are associated with policies instead of fixed sequences of actions? A natural policy is one to act greedily according to risk estimates that are updated after each reward observation.

In our analysis, we consider separately the risk due to exploration (or estimation) and the risk due to randomness. It would be interesting to introduce a new notion of risk that combines the two risks. For example, we can define a new risk measure as a weighted sum of two components: the risk with respect to an estimated distribution and the risk of the estimation error.