Abstract
The multi-armed bandit problems have been studied mainly under the measure of expected total reward accrued over a horizon of length T . In this paper, we address the issue of risk in multi-armed bandit problems and develop parallel results under the measure of mean-variance, a commonly adopted risk measure in economics and mathematical finance. We show that the model-specific regret and the model-independent regret in terms of the mean-variance of the reward process are lower bounded by Ω(log T ) and Ω(T 2/3 ), respectively. We then show that variations of the UCB policy and the DSEE policy developed for the classic risk-neutral MAB achieve these lower bounds.

performance of an arm selection policy is measured by regret defined as the expected cumulative reward loss over the entire time horizon against an omniscient player who knows the reward models and always plays the best arm [1] . In their seminal work [1] , Lai and Robbins showed that the minimum regret achievable by any consistent policy is Ω(log T ). Several online learning policies exist in the literature that achieve the optimal regret order under various assumptions on the reward models (see [1] , [2] , [5] , [18] , [19] ).
The above results were obtained under the so-called model-specific setting which focuses on the class of consistent (i.e., uniformly good) policies and characterizes their regret performance specific to the given set of arm distributions. The model-specific regret thus typically depend on certain statistics of the model such as the Kullback-Leiber (KL) divergence between the reward distributions and the gap in mean value from suboptimal arms to the optimal arm. Subsequent studies also considered the model-independent setting in which the performance of a learning policy is measured against the worst-case assignment of the distribution model. An Ω( √ T ) lower bound on the model-independent regret can be concluded from the lower bound results in [3] and also from the lower bound results on the non-stochastic MAB problem studied in [4] . A modification of the UCB policy was shown to achieve the optimal model-independent regret order [5] . A summary of the main results on risk-neutral MAB problems is given in the first column of Table I . Readers are also referred to the comprehensive survey in [35] .
B. Risk-Averse MAB
The classic MAB formulation targets at maximizing the expected return of an online learning policy. In many applications, especially in economics and finance, a player may be more interested in reducing the uncertainty (i.e., risk) in the outcome, rather than achieving the highest ensemble average. The focus of this paper is to develop results on risk-averse MAB, parallel to those on the classic risk-neutral MAB problems as summarized in the first column of Table I .
The notions of risk and uncertainty have been widely studied, especially in economics and mathematical finance. A commonly adopted risk measure is mean-variance [14] . Introduced by Markowits in 1952, mean-variance is particularly favored for portfolio selection in finance [15] .
Specifically, the mean-variance ξ(X) of a random variable X is given by
where σ 2 (X) and µ(X) are, respectively, the variance and the mean of X, the coefficient ρ > 0 is the risk tolerance factor that balances the two objectives of high return and low risk. The definition of mean-variance can be interpreted as the Lagrangian relaxation of the constrained optimization problem of minimizing the risk (measured by the variance) for a given expected return or maximizing the expected return for a given level of risk.
In [17] , a risk-averse MAB formulation based on the metric of mean-variance of observations was studied. Specifically, let π(t), t = 1, 2, . . . , T , denote the arm played by an arm selection policy π and X π(t) (t) the observed reward at time t. The cumulative mean-variance of the observed reward process is given as 1
where the first term inside the expectation corresponds to the cumulative empirical variance and the second term the cumulative empirical mean. The objective is a learning policy that minimizes ξ π (T ). In this risk-averse model, the time variations in the observed reward process are considered as risk (see Sec. I-C for motivating applications for this metric). Similar to riskneutral MAB, regret is defined as the performance loss in cumulative mean-variance of the observed reward process as given in (2) , comparing to the optimal policy under known model.
Unlike the risk-neutral MAB where the optimal policy under known model is to play the best arm over the entire time horizon, in the risk-verse MAB, the optimal policy is not necessarily a single-arm policy. We discuss this in Sec. III.
While conceptually similar, regret in terms of mean-variance of observations can no longer be written as the sum of certain properly defined immediate performance loss at each time instant, as is the case in risk-neutral MAB. More specifically, under the measure of mean-variance of observations, the contribution from playing a suboptimal arm at a given time t to the overall regret cannot be determined without knowing the entire sequence of decisions and observations. Furthermore, regret in mean-variance involves higher order statistics (rather than only the mean value as in the risk-neutral MAB) of the random time spent on each arm. These fundamental differences in the behavior of regret are what render the problem difficult and call for different techniques from that used in risk-neutral MAB problems. 1 Notice that the cumulative mean-variance of the observed reward process is considered in contrast to a normalized version divided by T . This definition facilitates the comparison with the risk-neutral MAB results given in Table I . [17] ). In other words, the best achievable model-specific regret order remains to be logarithmic as in the risk-neutral MAB. In terms of model-independent regret, we show that the minimum regret growth rate is T 2/3 . Thus, the analysis of MV-DSEE given in [17] is tight. We thus complete in this paper parallel results on risk-averse MAB under the measure of mean-variance of observations as summarized in the second column of Table I . 2 In [17] , regret was defined comparing to the optimal single-arm policy that as we show in this paper is not necessarily the optimal policy under known model. However, we show that the difference between regret with regard to the optimal single-arm policy and the one with regard to the optimal policy is sufficiently small that preserves the order of results (See Sec. III). Also, in [17] , a weaker regret definition was considered and was referred to as the pseudo regret. It was shown that the pseudo regret of MV-UCB was O(log 2 (T )). However, since the gap between pseudo regret and the strict regret is in the order of O( √ T ) (see Lemma 1 in [17] ), the analysis in [17] only showed an O( √ T ) regret order of MV-UCB. We also point out that the two types of regret (model-specific vs. model-independent) were not distinguished in [17] . From their analysis, however, it is clear that the result on MV-UCB was in terms of model-specific regret while the result on MV-DSEE was in terms of model-independent regret.
Risk-neutral MAB Risk-averse MAB
Model-
Specific
Lower Bounds Ω(log T ) Ω(log T )
Order-Optimal [1] , [2] , [18] , [19] MV-UCB
Policies
Model-
Independent

Lower
Bounds
Order-Optimal [5] MV-DSEE Policies [17] 
C. Motivating Applications
In this paper, we have adopted mean-variance of observations as the performance measure.
Mean-variance is a well accepted risk measure whose quadratic scaling captures the natural inclination toward less risky options when the stakes are higher. Studies have confirmed such risk-averse behaviors in investors (e.g. see [16] ).
In the classic application of mean-variance to portfolio selection, the objective is a joint optimization of risk and return for a portfolio over a particular period of time. This guarantees a high expected return and a low variation in the outcome. A similar approach is also taken for intertemporal returns of assets. Specifically, the objective is to guarantee high average return and low variation over time [32] . Such intertemporal variations are commonly referred to as volatility in finance literature and measured by the sample variance of the return process. The metric of mean-variance of the reward process studied in this paper as well as in [17] and [20] precisely captures the objective of low volatility and high expected return. Another motivating application is clinical trial, in which besides obtaining high average return, it is desirable to avoid high variations in the treatment outcomes for different patients [17] .
Besides mean-variance of the return process, one can also consider mean-variance of the total return at the end of the time horizon where the objective is to minimize the ensemble variations of the total return. The two measures of mean-variance of the reward process and mean-variance of the total reward are suitable for different applications. For example, in the return of a financial security, the fluctuations over time are to be avoided as "risk for financial security" [33] , while in a retirement investment one might not be sensitive about fluctuations of annual returns and only be interested in the value of the final return. Some initial results on MAB under mean-variance of the total reward can be found in our preliminary study reported in [23] .
D. Related Work
There is a large body of work on risk-neutral MAB problems under different variations and for various applications, including clinical trials, internet advertising, web search, and communication networks (see [6] [7] [8] [9] [10] [11] [12] and references therein). MAB has also been applied to a variety of scenarios in finance and economics (see, for example, a comprehensive survey in [28] ).
There are relatively few studies on risk-averse MAB as compared to the traditional risk-neutral MAB. In an initial work on this topic, a sequential risk-averse problem using the measure of mean-variance of observations was formulated in [20] . Different from this paper and [17] that consider a stochastic formulation, [20] adopted the so-called non-stochastic full information framework and established a negative result showing the infeasibility of sublinear regret.
There are a couple of results on risk-averse MAB under different risk measures. In [21] , the quality of an arm was measured by a general function of the mean and the variance of the random variable. The MAB problem studied in [21] is, however, closer to the risk-neutral MAB problems than to the problem studied in this paper. This is due to the fact that under the model of [21] , regret remains to be the sum of the immediate performance loss at each time instant.
As discussed earlier, in the risk-averse MAB studied in this paper, regret in mean-variance of observations is no longer the sum of instantaneous performance loss.
In [22] , [23] , MAB under the measure of value at risk, which defines the minimum value of a random variable at a given confidence level, was studied. In [22] , learning policies using the measure of conditional value at risk were developed. However, the performance guarantees were still within the risk-neutral MAB framework (in terms of the loss in the expected total reward) under the assumption that the best arm in terms of the mean value is also the best arm in terms of the conditional josesmith@example.org. In our recent work [23] , we considered risk-averse MAB under the measure of value at risk of the total reward and developed learning policies that offer poly-log regret performance. Another risk measure for MAB problems was considered in [36] in which the logarithm of moment generating function was used as a risk measure and high probability bounds on regret were analyzed.
There are also a couple of studies, while not directly addressing risk-averse MAB, offering relevant results from different perspectives. In [24] , the sample complexity of both mean-variance and value at risk for single-period and multi-period decision making was studied. In [25] , the problem of identifying the best arm in terms of different risk measures assuming the existence of an efficient risk estimator was considered. Identifying the best arm is, however, different from an MAB formulation due to the absence of the tradeoff between exploration and exploitation which is at the heart of online learning problems. The reader is also encouraged to see the work by Audibert et al. [26] on the deviation of regret from its expected value.
II. PROBLEM FORMULATION AND PRELIMINARIES
Consider a K-armed bandit and a single player. At each time t, the player chooses one arm to play. Playing arm i yields a random reward X i (t) drawn i.i.d. from an unknown distribution f i .
Let F = (f 1 , · · · , f K ) denote the set of the unknown distributions. An arm selection policy π specifies a function at each time t that maps from the player's observations and decision history to the arm to play at time t. Let {X π(t) (t)} T t=1 denote the random reward sequence under policy π. The cumulative mean-variance of the reward sequence is given in (2) .
The performance of policy π is measured by regret defined as the increase in cumulative mean-variance over a given horizon of length T as compared to the optimal policy π * under known model. (See Sec. III for a detailed discussion on π * ) R π (T ) = ξ π (T ) − ξ π * (T ).
(3)
A. Notations
Throughout the paper, * is used to indicate the arm that has the smallest mean-variance. If there are more than one arm with the smallest mean-variance value, one of them is chosen arbitrarily as * . Let Γ i,j = µ i − µ j and ∆ i = ξ i − ξ * denote, respectively, the difference between the mean values of arm i and j, and the difference between the mean-variance of arm i and the arm with the smallest mean-variance. Let ∆ = min i = * ∆ i , Γ = max i |Γ i, * |, σ max = max i σ i and
The following notations are used for the sample mean, the sample variance, and the sample mean-variance of the random reward sequence from arm i under a given policy π:
where t i (s) denotes the time instant corresponding to the s'th observation from arm i and τ i (t) denotes the number of times arm i has been played up to time t. Note that these quantities depend on the policy π. For simplicity, this dependency is omitted in these notations. The time argument may also be omitted when it is clear from the context. The use of the biased estimator for the variance is for the simplicity of the expression. The results presented in this work remain the same with the use of the unbiased estimator with τ i (t) replaced by τ i (t) − 1.
The KL-divergence between two distributions f and g is given by
where E f denotes the expectation operator with respect to f .
In the proofs, the notation E[X, E] for a random variable X and an event E is equivalent to
B. Concentration of the Sample Mean-Variance
We assume that the second central moment
for |u| ≤ u 0 for some u 0 > 0. A zero-mean light-tailed random variable X, is also called locally sub-Gaussian and satisfies the following [34] ,
for some constant ζ 0 > 0 and |u| ≤ u 0 . We establish in Lemma 1 a concentration result on the sample mean-variance, which plays an important role in regret analysis. This result is similar to the Chernoff-Hoeffding bound on the concentration of sample mean for sub-Gaussian random variables [27] and locally sub-Gaussian random variables (or equivalently light-tailed with zero mean) [38] . Similar concentration inequalities for mean-variance were given in [17] and [24] for random variables with bounded support.
Lemma 1: Let ξ s be the sample mean-variance of a random variable X obtained from s i.i.d.
observations. Let µ = E[X], and assume that (X − µ) 2 has a light-tailed distribution, i.e.,
for some constant ζ 1 > 0 and |u| ≤ u 1 . As a result, X has a light tailed distribution and
for some constant ζ 2 > 0 and |u| ≤ u 2 .
and for δ ≤ 2 + ρ,
Proof: See Appendix A.
III. THE KNOWN MODEL CASE
In this section, we study the case where all arm distributions are known. This defines the benchmark performance in the regret definition given in (3) . We first show through a counter example that playing the arm * that has the smallest mean-variance may not be optimal. This presents a major difficulty in regret analysis given that explicit characterizations of the optimal policy π * for the known model case are in general intractable. Our approach is to bound the performance gap between π * and the optimal single-arm policy π * (i.e., playing arm * all through), which allows us to obtain results on regret (defined with respect to π * ) by analyzing π * .
To see that π * may not be optimal, the key is to notice that the variance term (i.e., the first term on the right-hand side of (2)) in the cumulative mean-variance is with respect to the sample mean calculated from rewards obtained from all arms. When the remaining time horizon is short and the current sample mean is sufficiently close to the mean value of a suboptimal arm j = * , it may be more rewarding (in terms of minimizing the mean-variance) to play arm j rather than arm * . Consider a concrete example with two Gaussian-distributed arms with parameters µ 1 = 0,
It is easy to see that ξ 1 = 1 and ξ 2 = 1.1, and the optimal single-arm policy π * is to always play arm 1, yielding a cumulative mean-variance of ξ π * (t) = 1. Consider a policy π with π(1) = 1 and π(2) = I X 1 (1)<0.5 + 2I X 1 (1)≥0.5 . It can be shown that ξ π (T ) < 0.7, demonstrating the sub-optimality of π * .
The above example also gives a glimpse of the complexity in finding π * for a general problem.
To circumvent this difficulty, our approach is to show that π * is a good proxy of π * with a performance loss upper bounded by a constant for large T . We can then obtain regret bounds through π * .
Recall that regret R π (T ) in (3) is defined with respect to π * . Using π * as the benchmark, we define a proxy regret R π (T ) as
Our objective is to bound the difference between R π (T ) and R π (T ). To do this, we first derive in Lemma 2 below a closed-form expression of R π (T ) as a function of the number of times
each arm is played over the entire horizon of length T . This lemma is the cornerstone of the regret analysis in subsequent sections. The proof of Lemma 2 shares some techniques used in expanding the variance term with Appendix A of [17] . However, we point out that [17] did not provide an exact expression of R π (T ); rather, the results were obtained using an approximate of R π (T ) (referred to as pseudo-regret in [17] ).
Lemma 2:
The regret of a policy π with regard to the optimal single-arm policy π * under the measure of mean-variance of observations can be written as
Proof: See Appendix B.
Regret in terms of expected total reward can be easily written as a weighted sum of the expected τ i (T ), where the weights are given by the difference in the mean value of a suboptimal arm from the optimal arm. Specifically, based on Wald identity, the regret of policy π in terms of expected total reward is given by
The regret in terms of mean-variance of observations is, however, a much more complex function of τ i (T ) as given in Lemma 2 and depends on not only the expected value of τ i (T ), but also the second moment of τ i (T ) and the cross correlation between τ i (T ) and τ j (T ).
Based on Lemma 2, we characterize in Theorem 1 below the difference between R π (T ) and
R π (T ).
Theorem 1: For any policy π, we have
Proof: Since the performance of optimal policy cannot be worse than optimal single-arm policy we can immediately see that R π (T ) ≤ R π (T ). For the upper bound, we write R π (T ) − R π (T ) = − R π * (T ) and use the regret expression given in Lemma 2 to establish lower bounds on R π * (T ).
We first show that for ∆ > 0 and large T , R π * (T ) is lower bounded by a constant. For the cases with small ∆, we show that, based on Lemma 3, the difference between the second and third terms on the RHS of 12 is bounded by an order of log T term. For a detailed proof, see Appendix D. . We have the following inequality
Proof: See Appendix C.
Theorem 1 shows that for ∆ > 0 and large enough T , the difference between R π (T ) and
R π (T ) is bounded by a constant independent of T . This allows us to establish results on R π (T ) through analyzing R π (T ).
IV. MODEL-SPECIFIC REGRET
In this section, we consider the model-specific setting. We establish lower bounds on modelspecific regret feasible among all consistent policies and then show the order optimality of MV-UCB and the MV-DSEE policies.
A. Lower Bounds on Model-Specific Regret
To avoid trivial lower bounds on regret caused by policies that heavily bias toward certain distribution models (e.g., a policy that always plays arm 1), the model-specific setting focuses on the so-called consistent policies. The model-specific lower bounds for risk-neutral MAB (Theorems 1 and 2 in [1] ) are given for the set of policies that play the suboptimal arms in o(T α ) for all α > 0. We relax this assumption and focus on α−consistent policies defined as follows.
Definition. A policy π is called an α-consistent policy (0 < α < 1) if the following is satisfied: under any distribution model F , for any suboptimal arm j = * ,
Notice that
Thus, for a large enough T , an α-consistent policy plays the optimal arm linear in time.
We prove a model-specific regret lower bound for α−consistent policies over the family of one-parameter distribution models, the same as considered by Lai and Robbins in [1] for riskneutral MAB. Specifically, we assume that the distribution of arm i is given by f (.; θ i ) and the distribution model F = (f (.; θ 1 ), ..., f (.; θ K )) can be represented by Θ = (θ 1 , ..., θ K ). The parameters θ i are taking value from the set U satisfying the following regularity condition (the same as in [1] ).
Assumption 1. For any θ, λ, and λ ′ ∈ U, and for any ǫ > 0, there exists a δ > 0 such that
The lower bound in [1] is asymptotic (T → ∞). In addition to establishing the corresponding asymptotic lower bound for risk-averse MAB, we also provide in Theorem 2 below a finite-time regret lower bound when the following assumption holds. This assumption holds for a wide class of distributions, including the exponential family and the family of distributions with the same bounded support.
Assumption 2. For any θ and λ ∈ U, let X be a random variable with distribution f (.; θ) and is light-tailed as assumed in Sec. II. Then the random variable Y = f (X; λ) is light-tailed 3 .
Theorem 2: Consider the MAB problem under the measure of mean-variance of observations.
Let π be an α−consistent policy and Θ ⊂ U be the distribution model. Under Assumption 1, the model-specific regret satisfies, for any constant
Also, when Assumption 2 is satisfied, for T 1 ∈ N,
where ǫ T 1 can be arbitrary small when T 1 is large enough and 0 < c 2 < 1 is independent of T and F .
Proof: First, in the following lemma, we show that the probability that a suboptimal arm is played at least in the order of log T times approaches to 1, where the leading constant in front of log T depends on the KL-divergence between the distributions. 
Also, when Assumption 2 is satisfied, there exists T 0 ∈ N such that
where constant 0 < c 2 < 1 is independent of T and F .
To prove this lemma, we construct a new distribution model F k where arm i = * is the optimal arm. The log likelihood ratio between the two probability measures, denoted by γ, (see the detailed proof for the precise definition) corresponding to the two distribution models is a key statistic to prove the lemma. Specifically, we show that it is unlikely that τ i is smaller than the logarithmic term under two different cases of γ ≤ c 5 log T and γ > c 5 log T . The former is shown by a change of measure argument and using the consistency assumption. The latter is shown by Chernoff bound when Assumption 2 is satisfied and by law of large numbers otherwise. For a detailed proof see Appendix E.
To prove Theorem 2, we establish lower bounds on the first three terms of regret given in Notice that the constant c 1 in Lemma 4 and Theorem 2 can approach one for policies that satisfy (15) for all α > 0.
B. Risk-Averse Learning Policies
The performance of MV-UCB was first analyzed in [17] , which showed that the model-specific 
where b is a policy parameter whose value depends on the risk measure (see Theorem 3 below). 
Proof: From the regret expression given in (12) , we need to first bound E[τ i ] for i = * . This is established in the following lemma with proof given in Appendix G.
The expected number of times a sub-optimal arm i = * with ∆ i > 0 is played is upper bounded by
The third term in the regret expression in (12) See Appendix H for a detailed proof.
The model-specific regret of MV-UCB is linear in T when ∆ = 0 as discussed in [17] . An alternative policy in this case is MV-DSEE, a variation of the DSEE policy developed in [19] for risk-neutral MAB. In the MV-DSEE policy, time is partitioned into two interleaving sequences:
an exploration sequence denoted by E(t) and an exploitation sequence. In the former, the player plays all arms in a round-robin fashion. In the latter, the player plays the arm with the smallest sample mean-variance.
With 
where f (T ) is a positive increasing diverging sequence with an arbitrarily slow rate.
Proof: Following the similar steps as the performance analysis of DSEE policy given in [19] we can show that for i = * ,
Also similar to the proof of Theorem 3, we have
By substituting the bound on E[τ i ], we arrive at the theorem.
V. MODEL-INDEPENDENT REGRET
In this section, we consider the model-independent setting, in which the performance of a policy is measured against the worst-case reward model specific to the policy and the horizon length T . Specifically, let R π (T ; F ) denote the expected total performance loss of policy π over a horizon of length T for a reward model F . The model-independent regret is given by, for each T ,
and we are interested in the order (in terms of T ) of a thus defined R π (T ). It is easy to see that for any MAB problem, the model-independent regret order cannot be lower than the model-specific regret order.
We establish an Ω(T 2/3 ) lower bound on model-independent regret of any policy. Specifically, in the following theorem we show that there is distribution model such that the regret grows
with Ω(T 2/3 ).
Theorem 5: Consider the MAB problem under the measure of mean-variance of observations.
The model-independent regret of any policy π satisfies, for some constants c 3 > 0 and T 2 ∈ N,
Proof: To prove this theorem, two different sets of distributions, denoted by F and F ′ , are assigned to a two-armed bandit. Under both distribution models, the difference between the mean-variances of optimal and suboptimal arm is ∆. First, it is shown that under at least one of these two sets of distributions, for some constants c 4 > 0 and T 2 ∈ N,
A normal distribution is assigned to arm one which remains the same under both distribution assignments. Two different Bernolli distributions are assigned to arm two such that arm two is the sub-optimal arm under the first distribution assignment and the optimal arm under the second one. Through a coupling argument we show that for the specific distribution assignments designed here
for some constant d 0 > 0. A lower bound on regret can be derived from (28) , which increases as E F τ 2 (T ) decreases. On the other hand, a higher E F τ 2 (T ) indicates a higher regret under distribution assignment F . Optimizing these two lower bounds together on the value of E F τ 2 (T ) for any given policy and some calculation we arrive at the desired lower bound (27) . A proper assignment of ∆ = d 6 T − 1 3 , for some constant d 6 , gives the lower bound on model-independent regret in (26) . For the detailed proof, see Appendix I.
MV-DSEE policy was also considered in [17] and was shown to achieve O(T 
VII. CONCLUSION AN DISCUSSION
We studied risk-averse MAB problems under the risk measure of mean-variance of observations. We fully characterized the regret growth rate in both the model-specific and the modelindependent settings by establishing lower bounds on regret and developing order-optimal online learning policies.
The risk-averse MAB model reduces to the classic risk-neutral MAB when ρ → ∞. Specifically, when ρ → ∞, the mean-variance approaches to the negative expected value multiplied by ρ.
Thus, the mean-variance measure degenerates to a scaled expected value measure. Substituting ∆ i with −ρΓ i, * and neglecting Γ 2 i, * (against −ρΓ i, * ) the model-specific bounds given in Theorems 2 and 3 reproduce bounds on risk-neutral regret. Regarding the model-independent regret, however, as it is shown in this paper, the regret growth rate is different from the risk-neutral MAB. This difference is expected and does not indicate any inconsistency in the results. Specifically, the reason for this difference is that the worst-case assignment of the distributions takes into account the value of ρ (i.e., the worst-case assignment of distribution model is with the knowledge of the risk measure). Thus, even for a large value of ρ, a proper choice of the distributions with small difference between the mean values results in a case where the difference between the expected values multiplied by ρ is comparable to the difference between the variances and the latter cannot be neglected.
The time variations in the reward process have two sources: the randomness of the observed reward from each arm and the switching across arms with different expected values. The latter disappears when Γ → 0. Thus, when Γ → 0, the regret reduces to a a weighted sum of the expected number of times that each suboptimal arm is played, where the weights are given by the difference in the variance of a suboptimal arm from the optimal arm. The reduced measure is similar to the risk-neutral regret where the difference in mean value is replaced by the difference in variance. Thus, as expected, the model-specific bounds given in Theorems 2 and 3 degenerate to the bounds on risk-neutral regret, except ∆ i is the difference in the variance of a suboptimal arm from the optimal arm. Under the model-independent setting, the value of Γ is chosen arbitrarily for the worst-case assignment of the distribution model and cannot be forced to zero.
Our regret lower bounds that hold for all T ≥ T 0 for some constant T 0 ∈ N should be interpreted as finite-time results since one can always find a leading constant large enough (in the case of upper bounds) or small enough (in the case of lower bounds) to accommodate the first T 0 terms. Indeed, how large or small the leading constant needs to be to have results hold for all T can be obtained in our proof procedure. However, such a practice is tedious and leads to an overly complicated expression.
For the risk-neutral MAB, an improved version of the UCB policy developed in [5] was shown to achieve the optimal regret order under both the model-specific and model-independent settings. We have shown in this paper that MV-DSEE approaches both the model-specific and model-independent regret lower bounds, but requiring different values for the cardinality of the exploration sequence. Whether a single policy without any change in its parameter values can achieve the optimal regret order under both settings remains an open question. A satisfactory answer to this question is involved and requires a separate investigation.
Appendix A: Proof of Lemma 1
Let µ s be the sample mean obtained from s i.i.d. observations. By Chernoff-Hoeffding bound [27] ,
≤ exp(−asδ 2 1 ),
where X(t) is the tth observation of the random variable X. The mean-variance deviation term can be written as
Now, for δ 1 = δ 2+ρ ≤ 1, substituting ξ s − ξ(X) from (29)
≤ exp(−asδ 2 1 ) + exp(−asδ 2 1 )
The second inequality in (10) can be proven similarly. In the proof of the second inequality we can choose δ 1 = δ 1+ρ . The rest of the proof will remain the same.
Appendix B: Proof of Lemma 2
Let µ π = 1 T T t=1 X π(t) (t) and µ π = E[µ π ]. In order to show the expression of regret given in (2), we expand the cumulative variance term.
The first term on the RHS of (31) equals to, by Wald identity,
The second term can be written as
The third term can be written as
From (32), (33) and (34) , we have
To arrive at (35) 
Eτ j Γ * ,j ) 2 ] + 1
Eτ j Γ * ,j ) 2 ]
Eτ j Γ * ,j ) 2 ]
Eτ j Γ * ,j )]
Eτ j Γ * ,j ) 2 .
For the third term on the RHS of (36), we have
We know that for any random variable X,
Eτ i Γ i, * )] = 0. Thus, from (36), (37) and (39), we have
Now we can show the expression for R π (T ) for any policy π that plays arm i for τ i times
as desired.
Appendix C: Proof of Lemma 3
In order to prove (14), we write the expected value of τ (µ−µ) 2 divided by log T as integrating the tail probability. For the tail probability we have, for a real number x > 0
Thus, multiplying by log T , we have
Appendix D: Proof of Theorem 1
Since ξ π * ≤ ξ π * , it is straightforward to see that
For the upper bound, we have
From Lemma 2, we have
where τ i are the number of times arm i is played by π * . We have, by Cauchy-Schwartz inequality,
To arrive at (44), we also use
Eτ i σ 2 i as a result of Wald's second identity. For the second term on the RHS we have, by applying again Cauchy-Schwartz inequality,
For a set of positive real numbers h i , we have i h i ≤ i √ h i . We can apply this inequality to the third term on the RHS of (44) and from (44), (45) and 1
Thus we can write
This gives a lower bound on R π * (T ) which translates to an upper bound on R π (T ) − R π (T ) by (42). Although this lower bound is a constant independent of T , it grows unboundedly when ∆ approaches 0. We next drive another lower bound on R π * (T ) that is independent of ∆.
Inequality (47) holds as a result of Cauchy-Schwartz inequality (similar to (45)) and (48) holds by Lemma 3.
Appendix E: Proof of Lemma 4
For k = * , construct F k , by only changing the distribution of arm k to f ′ k such that arm k is the optimal arm (−δ < ξ ′ k − ξ * < 0) and |I(f k , f * ) − I(f k , f ′ k )| ≤ ǫ for arbitrary small ǫ. The possibility of such a model is a result of Assumption 1. Let γ denote the log-likelihood ratio between the F and F k :
) . We show that it is unlikely to have τ k < c 1 log T I(f k ,f ′ k ) under two different scenarios for γ. First, consider γ > c 5 log T for a constant c 5 > c 1 . We have
By strong law of large numbers 1
So when γ > c 5 log T , by strong law of large numbers, we have
Also, when Assumption 2 is satisfied, log f ′ k (X) and log f k (X) have light-tailed distributions. Thus, log 
Inequality (50) holds since I(f k , f ′ k ) ≤ 1 t c 1 log T and (51) holds according to Chernoff bound. We point out that the Chernoff bound constant a 1 is different from the constant specified in Lemma 1 since we have a different random variable here.
Next, we consider γ ≤ c 5 log T . By Markov inequality, we have
We can change the probability measure from F to F k as follows. Let S(T ) be the set of all observations over a time horizon with length T that satisfy a particular event. We have
Using (53) and a change of probability measure from F to F k we have
where to arrive at the last inequality we use the α−consistency assumption. Form (49), (54) and the fact that |I(f k , f * ) − I(f k , f ′ k )| can be arbitrarily small, we conclude that, for
Equivalently,
Form (52) and (54), we conclude that, for c 5 < 1 − α, when Assumption 2 is satisfied
.
Thus, there is a T 0 ∈ N such that for T ≥ T 0 ,
for some constant c 2 > 0 independent of T and F . We emphasize that the constant c 1 and c 5 are chosen to satisfy c 1 < c 5 < 1 − α.
Appendix F: Proof of Theorem 2
Since R π (T ) ≥ R π (T ) we can establish a lower bound on R π (T ). From Lemma 2 we have
A lower bound on E[τ i ] is a straightforward consequence of Lemma 4. By Markov inequality
we have
So we can write
.
Similarly, by Markov inequality we have, when Assumption 2 is satisfied, there is a T 0 ∈ N such that for all T ≥ T 0 ,
For the third term on the RHS of regret expression (55), following the similar steps as in (46), we have
Define the event E as follows. E : for all k = * , τ k ≤ T 1+α 2 .
Notice that (61) holds because the argument inside the expectation in (60) is always positive (similar to (45) by Cauchy-Schwartz inequality).
.
Similarly, we have, when Assumption 2 is satisfied, there is a T 0 ∈ N such that for all T ≥ T 0 ,
Substituting (59) and (62) in regret expression we have
Substituting the lower bounds on E[τ i ] and E[τ i , E] in the above bound we arrive at
Also, when Assumption 2 is satisfied, for T ≥ T 0 ,
We can rewrite the above lower bound such that for all T ≥ T 1 ,
where ǫ T 1 can be arbitrary small when T 1 is large enough. However, precise characterization of ǫ T 1 is tedious and depends on all of the diminishing terms above.
Appendix G: Proof of Lemma 5
Let i = * be a suboptimal arm and b i = ⌈ 4b 2 log T 
We can write
For τ i (t) ≥ b i , the last term in (69) is positive, thus continuing from (68)
Applying Lemma 1
Appendix H: Proof of Theorem 3
Considering the regret expression in Lemma 2 From Theorem 1, we have
To prove Theorem 5, two different sets of distributions are assigned to a two-armed bandit.
Then it is shown that under at least one of these two sets of distributions (27) holds. Consider a two-armed bandit. Let f 1 ∼ N (µ 1 , σ 2 1 ), a normal distribution with mean µ 1 = 3 4 and variance σ 2 1 = 3 16 − 4∆ 2 . Also, let f 2 ∼ B(p), a Bernolli distribution with p = 1/4 + 2∆ and f ′ 2 ∼ B(q) with q = 1/4 − 2∆. Denote F = (f 1 , f 2 ) and F ′ = (f 1 , f ′ 2 ). For the simplicity of presentation let us assume ρ = 0. Note that for the difference between the variance of above distributions we have σ 2 2 − σ 2 1 = ∆ and σ 2 1 − σ ′2 2 = ∆. Since R π (T ) ≤ R π (T ) we can establish a lower bound on R π (T ) that is also a lower bound on R π (T ). From Lemma 2
Following the similar lines as the proof of (48) we show
Eτ i ∆ i − 2 a (log T + 2).
Using Lemma 6 through a coupling argument we establish a lower bound on the regret under one of the two systems.
Let us use the notations R π (T ; F ) and R π (T ; F ′ ) to distinguish between the regrets under distribution assignments F and F ′ , respectively. Also, let f (t) and f ′(t) denote the distribution of the reward process up to time t under F and F ′ , respectively. Spcifically, f (t) (x(1), x(2), ..., x(t)) = Π {s:π(s)=1} f 1 (x(s))Π {s:π(s)=2} f 2 (x(s)) and f ′(t) is defined similarly under F ′ .
max( R π (T ; F ), R π (T ; F ′ )) ≥ 1 2 ( R π (T ; F )) + R π (T ; F ′ )) 
The KL-divergence between f (t) and f ′(t) equals to I(f (t) , f ′(t) ) = E F [log Π {s:π(s)=2} f 2 (X π(s) (s)) Π {s:π(s)=2} f ′ 2 (X π(s) (s))
for some constant d 0 . Substituting (74) in (73) max( R π (T ; F ), R π (T ; F ′ ))

{'paper_id': '6496028', 'title': 'Risk-Averse Multi-Armed Bandit Problems under Mean-Variance Measure', 's2_url': 'https://api.semanticscholar.org/CorpusID:6496028', 'source': 'S2ORC'}