Amir Sani
email: amir.sani@inria.fr

Alessandro Lazaric
email: alessandro.lazaric@inria.fr

Rémi Munos
email: remi.munos@inria.fr

Risk-Aversion in Multi-armed Bandits

Stochastic multi-armed bandits solve the Exploration-Exploitation dilemma and ultimately maximize the expected reward. Nonetheless, in many practical problems, maximizing the expected reward is not the most desirable objective. In this paper, we introduce a novel setting based on the principle of risk-aversion where the objective is to compete against the arm with the best risk-return trade-off. This setting proves to be more difficult than the standard multi-arm bandit setting due in part to an exploration risk which introduces a regret associated to the variability of an algorithm. Using variance as a measure of risk, we define two algorithms, investigate their theoretical guarantees, and report preliminary empirical results.

Introduction

The multi-armed bandit [START_REF] Robbins | Some aspects of the sequential design of experiments[END_REF] elegantly formalizes the problem of on-line learning with partial feedback, which encompasses a large number of real-world applications, such as clinical trials, online advertisements, adaptive routing, and cognitive radio. In the stochastic multi-armed bandit model, a learner chooses among several arms (e.g., different treatments), each characterized by an independent reward distribution (e.g., the treatment effectiveness). At each point in time, the learner selects one arm and receives a noisy reward observation from that arm (e.g., the effect of the treatment on one patient). Given a finite number of n rounds (e.g., patients involved in the clinical trial), the learner faces a dilemma between repeatedly exploring all arms and collecting reward information versus exploiting current reward estimates by selecting the arm with the highest estimated reward. Roughly speaking, the learning objective is to solve this exploration-exploitation dilemma and accumulate as much reward as possible over n rounds. Multi-arm bandit literature typically focuses on the problem of finding a learning algorithm capable of maximizing the expected cumulative reward (i.e., the reward collected over n rounds averaged over all possible observation realizations), thus implying that the best arm returns the highest expected reward. Nonetheless, in many practical problems, maximizing the expected reward is not always the most desirable objective. For instance, in clinical trials, the treatment which works best on average might also have considerable variability; resulting in adverse side effects for some patients. In this case, a treatment which is less effective on average but consistently effective on different patients may be preferable to an effective but risky treatment. More generally, some applications require an effective trade-off between risk and reward.

A large part of decision-making theory focuses on defining and managing risk (see e.g., [START_REF] Gollier | The Economics of Risk and Time[END_REF] for an introduction to risk from an expected utility theory perspective). A variety of behaviours result in an uncertainty which might be deemed unfavourable for a specific application and referred to as a risk, but there is no agreed upon definition for risk. For example, a solution with guarantees over multiple runs of an algorithm may not satisfy the desire for a solution with low variability over a single implementation of an algorithm. Two foundational risk modeling paradigms are Expected Utility theory [START_REF] Neumann | Theory of games and economic behavior[END_REF] and the historically popular and accessible Mean-Variance paradigm [START_REF] Markowitz | Portfolio selection[END_REF].

Risk has mostly been studied in on-line learning within the so-called expert advice setting (i.e., adversarial full-information on-line learning). In particular, [START_REF] Even-Dar | Risk-sensitive online learning[END_REF] showed that in general, although it is possible to achieve a small regret w.r.t. to the expert with the best average performance, it is not possible to compete against the expert which best trades off between average return and risk. On the other hand, it is possible to define no-regret algorithms for simplified measures of risk-return. [START_REF] Warmuth | Online variance minimization[END_REF] studied the case of pure risk minimization (notably variance minimization) in an on-line setting where at each step the learner is given a covariance matrix and must choose a weight vector that minimizes the variance. The regret is then computed over a horizon and compared to the fixed weights minimizing the variance in hindsight. In the multi-arm bandit domain, the most interesting results are by [START_REF] Audibert | Exploration-exploitation trade-off using variance estimates in multi-armed bandits[END_REF] and [START_REF] Salomon | Deviations of stochastic bandit regret[END_REF]. [START_REF] Audibert | Exploration-exploitation trade-off using variance estimates in multi-armed bandits[END_REF] introduced an analysis of the expected regret and its distribution, revealing that an anytime version of UCB [START_REF] Auer | Finite-time analysis of the multi-armed bandit problem[END_REF] and UCB-V might have large regret with some nonnegligible probability. 1 This analysis is further extended by [START_REF] Salomon | Deviations of stochastic bandit regret[END_REF] who derived negative results which show no anytime algorithm can achieve a regret with both a small expected regret and exponential tails. Although these results represent an important step towards the analysis of risk within bandit algorithms, they are limited to the case where an algorithm's cumulative reward is compared to the reward obtained by pulling the arm with the highest expectation.

In this paper, we focus on the problem of competing against the arm with the best risk-return tradeoff. In particular, we refer to the popular mean-variance model introduced by [START_REF] Markowitz | Portfolio selection[END_REF]. In Sect. 2 we introduce notation and define the mean-variance bandit problem. In Sect. 3 and 4 we introduce two algorithms and study their theoretical properties. In Sect. 5 we report a set of numerical simulations aiming at validating the theoretical results. Finally, in Sect. 7 we conclude with a discussion on possible extensions. The proofs and additional experiments are reported in the extended version [START_REF] Sani | Risk-aversion in multi-arm bandit[END_REF].

Mean-Variance Multi-arm Bandit

In this section we introduce the notation and define the mean-variance multi-arm bandit problem.

We consider the standard multi-arm bandit setting with K arms, each characterized by a distribution ν i bounded in the interval [0, 1]. Each distribution has a mean µ i and a variance σ2 i . The bandit problem is defined over a finite horizon of n rounds. We denote by X i,s ∼ ν i the s-th random sample drawn from the distribution of arm i. All arms and samples are independent. In the multiarm bandit protocol, at each round t, an algorithm selects arm I t and observes sample X It,Ti,t , where T i,t is the number of samples observed from arm i up to time t (i.e., T i,t = t s=1 I{I t = i}). While in the standard bandit literature the objective is to select the arm leading to the highest reward in expectation (the arm with the largest expected value µ i ), here we focus on the problem of finding the arm which effectively trades off between its expected reward (i.e., the return) and its variability (i.e., the risk). Although a large number of models for the risk-return trade-off have been proposed, here we focus on the most historically popular and simple model: the mean-variance model proposed by [START_REF] Markowitz | Portfolio selection[END_REF], Definition 1. The mean-variance of an arm i with mean µ i , variance σ 2 i and coefficient of absolute risk tolerance ρ is defined as

2 MV i = σ 2 i -ρµ i .
Thus the optimal arm is the arm with the smallest mean-variance, that is i * = arg min i MV i . We notice that we can obtain two extreme settings depending on the value of risk tolerance ρ. As ρ → ∞, the mean-variance of arm i tends to the opposite of its expected value µ i and the problem reduces to the standard expected reward maximization traditionally considered in multi-arm bandit problems. With ρ = 0, the mean-variance reduces to σ 2 i and the objective becomes variance minimization. Given {X i,s } t s=1 i.i.d. samples from the distribution ν i , we define the empirical mean-variance of an arm i with t samples as MV i,t = σ2 i,tρμ i,t , where

μi,t = 1 t t s=1 X i,s , σ2 i,t = 1 t t s=1 X i,s -μi,t 2 . ( 1
)
We now consider a learning algorithm A and its corresponding performance over n rounds. Similar to a single arm i we define its empirical mean-variance as

MV n (A) = σ2 n (A) -ρμ n (A), (2)
where

μn (A) = 1 n n t=1 Z t , σ2 n (A) = 1 n n t=1 Z t -μn (A) 2 , (3)
with Z t = X It,Ti,t , that is the reward collected by the algorithm at time t. This leads to a natural definition of the (random) regret at each single run of the algorithm as the difference in the meanvariance performance of the algorithm compared to the best arm. Definition 2. The regret for a learning algorithm A over n rounds is defined as

R n (A) = MV n (A) -MV i * ,n . (4)
Given this definition, the objective is to design an algorithm whose regret decreases as the number of rounds increases (in high probability or in expectation).

We notice that the previous definition actually depends on unobserved samples. In fact, MV i * ,n is computed on n samples i * which are not actually observed when running A. This matches the definition of true regret in standard bandits (see e.g., [START_REF] Audibert | Exploration-exploitation trade-off using variance estimates in multi-armed bandits[END_REF]). Thus, in order to clarify the main components characterizing the regret, we introduce additional notation. Let

Y i,t =    X i * ,t if i = i * X i * ,t with t = T i * ,n + j<i,j =i * T j,n + t otherwise
be a renaming of the samples from the optimal arm, such that while the algorithm was pulling arm i for the t-th time, Y i,t is the unobserved sample from i * . The corresponding mean and variance is

μi,Ti,n = 1 T i,n Ti,n t=1 Y i,t , σ2 i,Ti,n = 1 T i,n Ti,n t=1 Y i,t -μi,Ti,n 2 . ( 5
)
Given these additional definitions, we can rewrite the regret as (see App. A.1 in [START_REF] Sani | Risk-aversion in multi-arm bandit[END_REF])

R n (A) = 1 n i =i * T i,n (σ 2 i,Ti,n -ρμ i,Ti,n ) -(σ 2 i,Ti,n -ρμ i,Ti,n ) + 1 n K i=1 T i,n μi,Ti,n -μn (A) 2 - 1 n K i=1 T i,n μi,Ti,n -μi * ,n 2 . ( 6
)
Since the last term is always negative and small3 , our analysis focuses on the first two terms which reveal two interesting characteristics of A. First, an algorithm A suffers a regret whenever it chooses a suboptimal arm i = i * and the regret corresponds to the difference in the empirical mean-variance of i w.r.t. the optimal arm i * . Such a definition has a strong similarity to the standard definition of regret, where i * is the arm with highest expected value and the regret depends on the number of times suboptimal arms are pulled and their respective gaps w.r.t. the optimal arm i * . In contrast to the standard formulation of regret, A also suffers an additional regret from the variance σ2 n (A), which depends on the variability of pulls T i,n over different arms. Recalling the definition of the mean μn (A) as the weighted mean of the empirical means μi,Ti,n with weights T i,n /n (see eq. 3), we notice that this second term is a weighted variance of the means and illustrates the exploration risk associated to the algorithm. In fact, if an algorithm simply selects and pulls a single arm from the beginning, it would not suffer any exploration risk (secondary regret) since μn (A) would coincide with μi,Ti,n for the chosen arm and all other components would have zero weight. On the other hand, an algorithm accumulates exploration risk through this second term as the mean μn (A) deviates from any specific arm; where the maximum exploration risk peaks at the mean μn (A) furthest from all arm means.

The previous definition of regret can be further elaborated to obtain the upper bound (see App. A.1)

R n (A) ≤ 1 n i =i * T i,n ∆ i + 1 n 2 K i=1 j =i T i,n T j,n Γ 2 i,j , (7)
where

∆ i = (σ 2 i,Ti,n -σ2 i,Ti,n ) -ρ(μ i,Ti,n -μi,Ti,n ) and Γ 2 i,j = (μ i,Ti,n -μj,Tj,n ) 2 .
Unlike the definition in eq. 6, this upper bound explicitly illustrates the relationship between the regret and the number of pulls T i,n ; suggesting that a bound on the pulls is sufficient to bound the regret.

Finally, we can also introduce a definition of the pseudo-regret.

Input: Confidence δ for t = 1, . . . , n do for i = 1, . . . , K do Compute Bi,T i,t-1 = MVi,T i,t-1 -(5 + ρ) log 1/δ 2T i,t
R n (A) = 1 n i =i * T i,n ∆ i + 2 n 2 K i=1 j =i T i,n T j,n Γ 2 i,j , (8)
where

∆ i = MV i -MV i * and Γ i,j = µ i -µ j .
In the following, we denote the two components of the pseudo-regret as

R ∆ n (A) = 1 n i =i * T i,n ∆ i , and R Γ n (A) = 2 n 2 K i=1 j =i T i,n T j,n Γ 2 i,j . (9)
Where R ∆ n (A) constitutes the standard regret derived from the traditional formulation of the multiarm bandit problem and R Γ n (A) denotes the exploration risk. This regret can be shown to be close to the true regret up to small terms with high probability.

Lemma 1. Given definitions 2 and 3,

R n (A) ≤ R n (A) + (5 + ρ) 2K log(6nK/δ) n + 4 √ 2 K log(6nK/δ) n ,
with probability at least 1δ.

The previous lemma shows that any (high-probability) bound on the pseudo-regret immediately translates into a bound on the true regret. Thus, we report most of the theoretical analysis according to R n (A). Nonetheless, it is interesting to notice the major difference between the true and pseudoregret when compared to the standard bandit problem. In fact, it is possible to show in the risk-averse case that the pseudo-regret is not an unbiased estimator of the true regret, i.e.,

E[R n ] = E[ R n ].
Thus, to bound the expectation of R n we build on the high-probability result from Lemma 1.

The Mean-Variance Lower Confidence Bound Algorithm

In this section we introduce a risk-averse bandit algorithm whose objective is to identify the arm which best trades off risk and return. The algorithm is a natural extension of UCB1 [START_REF] Auer | Finite-time analysis of the multi-armed bandit problem[END_REF] and we report a theoretical analysis of its mean-variance.

The Algorithm

We propose an index-based bandit algorithm which estimates the mean-variance of each arm and selects the optimal arm according to the optimistic confidence-bounds on the current estimates. A sketch of the algorithm is reported in Figure 1. For each arm, the algorithm keeps track of the empirical mean-variance MV i,s computed according to s samples. We can build high-probability confidence bounds on empirical mean-variance through an application of the Chernoff-Hoeffding inequality (see e.g., [START_REF] Antos | Active learning in heteroscedastic noise[END_REF] for the bound on the variance) on terms μ and σ2 . Lemma 2. Let {X i,s } be i.i.d. random variables bounded in [0, 1] from the distribution ν i with mean µ i and variance σ 2 i , and the empirical mean μi,s and variance σ2 i,s computed as in Equation 1, then

P ∃i = 1, . . . , K, s = 1, . . . , n, | MV i,s -MV i | ≥ (5 + ρ) log 1/δ 2s ≤ 6nKδ,
The algorithm in Figure 1 implements the principle of optimism in the face of uncertainty used in many multi-arm bandit algorithms. On the basis of the previous confidence bounds, we define a lower-confidence bound on the mean-variance of arm i when it has been pulled s times as

B i,s = MV i,s -(5 + ρ) log 1/δ 2s , ( 10
)
where δ is an input parameter of the algorithm. Given the index of each arm at each round t, the algorithm simply selects the arm with the smallest mean-variance index, i.e., I t = arg min i B i,Ti,t-1 .

We refer to this algorithm as the mean-variance lower-confidence bound (MV-LCB ) algorithm.

Remark 1. We notice that MV-LCB reduces to UCB1 for ρ → ∞. This is coherent with the fact that for ρ → ∞ the mean-variance problem reduces to expected reward maximization, for which UCB1 is known to be nearly-optimal. On the other hand, for ρ = 0 (variance minimization), the algorithm plays according to a lower-confidence-bound on the variances.

Remark 2. The MV-LCB algorithm has a parameter δ defining the confidence level of the bounds employed in [START_REF] Markowitz | Portfolio selection[END_REF]. In Thm. 1 we show how to optimize the parameter when the horizon n is known in advance. On the other hand, if n is not known, it is possible to design an anytime version of MV-LCB by defining a non-decreasing exploration sequence (ε t ) t instead of the term log 1/δ.

Theoretical Analysis

In this section we report the analysis of the regret R n (A) of MV-LCB (Fig. 1). As highlighted in eq. 7, it is enough to analyze the number of pulls for each of the arms to recover a bound on the regret. The proofs (reported in [START_REF] Sani | Risk-aversion in multi-arm bandit[END_REF]) are mostly based on similar arguments to the proof of UCB.

We derive the following regret bound in high probability and expectation. Theorem 1. Let the optimal arm i * be unique and b = 2(5 + ρ), the MV-LCB algorithm achieves a pseudo-regret bounded as

R n (A) ≤ b 2 log 1/δ n i =i * 1 ∆ i + 4 i =i * Γ 2 i * ,i ∆ 2 i + 2b 2 log 1/δ n i =i * j =i j =i * Γ 2 i,j ∆ 2 i ∆ 2 j + 5K n , with probability at least 1 -6nKδ. Similarly, if MV-LCB is run with δ = 1/n 2 then E[ R n (A)] ≤ 2b 2 log n n i =i * 1 ∆ i + 4 i =i * Γ 2 i * ,i ∆ 2 i + 4b 2 log n n i =i * j =i j =i * Γ 2 i,j ∆ 2 i ∆ 2 j + (17 + 6ρ) K n .
Remark 1 (the bound). Let ∆ min = min i =i * ∆ i and Γ max = max i |Γ i |, then a rough simplification of the previous bound leads to

E[ R n (A)] ≤ O K ∆ min log n n + K 2 Γ 2 max ∆ 4 min log 2 n n .
First we notice that the regret decreases as O(log 2 n/n), implying that MV-LCB is a consistent algorithm. As already highlighted in Def. 2, the regret is mainly composed by two terms. The first term is due to the difference in the mean-variance of the best arm and the arms pulled by the algorithm, while the second term denotes the additional variance introduced by the exploration risk of pulling arms with different means. In particular, this additional term depends on the squared difference of the arm means Γ 2 i,j . Thus, if all the arms have the same mean, this term would be zero. Remark 2 (worst-case analysis). We can further study the result of Thm. 1 by considering the worst-case performance of MV-LCB, that is the performance when the distributions of the arms are chosen so as to maximize the regret. In order to illustrate our argument we consider the simple case of K = 2 arms, ρ = 0 (variance minimization), µ 1 = µ 2 , and σ 2 1 = σ 2 2 = 0 (deterministic arms). 4In this case we have a variance gap ∆ = 0 and Γ 2 > 0. According to the definition of MV-LCB, the index B i,s would simply reduce to B i,s = log(1/δ)/s, thus forcing the algorithm to pull both arms uniformly (i.e., T 1,n = T 2,n = n/2 up to rounding effects). Since the arms have the same variance, there is no direct regret in pulling either one or the other. Nonetheless, the algorithm has an additional variance due to the difference in the samples drawn from distributions with different means. In this case, the algorithm suffers a constant (true) regret

R n (MV-LCB) = 0 + T 1,n T 2,n n 2 Γ 2 = 1 4 Γ 2 ,
independent from the number of rounds n. This argument can be generalized to multiple arms and ρ = 0, since it is always possible to design an environment (i.e., a set of distributions) such that ∆ min = 0 and Γ max = 0.5 This result is not surprising. In fact, two arms with the same meanvariance are likely to produce similar observations, thus leading MV-LCB to pull the two arms repeatedly over time, since the algorithm is designed to try to discriminate between similar arms. Although this behavior does not suffer from any regret in pulling the "suboptimal" arm (the two arms are equivalent), it does introduce an additional variance, due to the difference in the means of the arms (Γ = 0), which finally leads to a regret the algorithm is not "aware" of. This argument suggests that, for any n, it is always possible to design an environment for which MV-LCB has a constant regret. This is particularly interesting since it reveals a huge gap between the mean-variance and the standard expected regret minimization problem and will be further investigated in the numerical simulations in Sect. 5. In fact, UCB is known to have a worst-case regret of Ω(1/ √ n) [START_REF] Audibert | Regret bounds and minimax policies under partial monitoring[END_REF], while in the worst case, MV-LCB suffers a constant regret. In the next section we introduce a simple algorithm able to deal with this problem and achieve a vanishing worst-case regret.

The Exploration-Exploitation Algorithm

The ExpExp algorithm divides the time horizon n into two distinct phases of length τ and nτ respectively. During the first phase all the arms are explored uniformly, thus collecting τ /K samples each 6 . Once the exploration phase is over, the mean-variance of each arm is computed and the arm with the smallest estimated mean-variance MV i,τ /K is repeatedly pulled until the end.

The MV-LCB is specifically designed to minimize the probability of pulling the wrong arms, so whenever there are two equivalent arms (i.e., arms with the same mean-variance), the algorithm tends to pull them the same number of times, at the cost of potentially introducing an additional variance which might result in a constant regret. On the other hand, ExpExp stops exploring the arms after τ rounds and then elicits one arm as the best and keeps pulling it for the remaining nτ rounds. Intuitively, the parameter τ should be tuned so as to meet different requirements. The first part of the regret (i.e., the regret coming from pulling the suboptimal arms) suggests that the exploration phase τ should be long enough for the algorithm to select the empirically best arm î * at τ equivalent to the actual optimal arm i * with high probability; and at the same time, as short as possible to reduce the number of times the suboptimal arms are explored. On the other hand, the second part of the regret (i.e., the variance of pulling arms with different means) is minimized by taking τ as small as possible (e.g., τ = 0 would guarantee a zero regret). The following theorem illustrates the optimal trade-off between these contrasting needs.

Theorem 2. Let ExpExp be run with τ = K(n/14) 2/3 , then for any choice of distributions

{ν i } the expected regret is E[ R n (A)] ≤ 2 K n 1/3 .
Remark 1 (the bound). We first notice that this bound suggests that ExpExp performs worse than MV-LCB on easy problems. In fact, Thm. 1 demonstrates that MV-LCB has a regret decreasing as O(K log(n)/n) whenever the gaps ∆ are not small compared to n, while in the remarks of Thm. 1 we highlighted the fact that for any value of n, it is always possible to design an environment which leads MV-LCB to suffer a constant regret. On the other hand, the previous bound for ExpExp is distribution independent and indicates the regret is still a decreasing function of n even in the worst case. This opens the question whether it is possible to design an algorithm which works as well as MV-LCB on easy problems and as robustly as ExpExp on difficult problems.

Remark 2 (exploration phase). The previous result can be improved by changing the exploration strategy used in the first τ rounds. Instead of a pure uniform exploration of all the arms, we could adopt a best-arm identification algorithms such as Successive Reject or UCB-E, which maximize the probability of returning the best arm given a fixed budget of rounds τ (see e.g., [START_REF] Audibert | Best arm identification in multiarmed bandits[END_REF]).

Numerical Simulations

In this section we report numerical simulations aimed at validating the main theoretical findings reported in the previous sections. In the following graphs we study the true regret R n (A) averaged over 500 runs. We first consider the variance minimization problem (ρ = 0) with K = 2 Gaussian arms set to µ 1 = 1.0, µ 2 = 0.5, σ 2 1 = 0.05, and σ 2 2 = 0.25 and run MV-LCB 7 . In Figure 2 we report the true regret R n (as in the original definition in eq. 4) and its two components R ∆ n and R Γ n (these two values are defined as in eq. 9 with ∆ and Γ replacing ∆ and Γ). As expected (see e.g., Thm. 1), the regret is characterized by the regret realized from pulling suboptimal arms and arms with different means (Exploration Risk) and tends to zero as n increases. Indeed, if we considered two distributions with equal means (µ 1 = µ 2 ), the average regret coincides with R ∆ n . Furthermore, as shown in Thm. 1 the two regret terms decrease with the same rate O(log n/n).

A detailed analysis of the impact of ∆ and Γ on the performance of MV-LCB is reported in App. D in [START_REF] Sani | Risk-aversion in multi-arm bandit[END_REF]. Here we only compare the worst-case performance of MV-LCB to ExpExp (see Figure 2). In order to have a fair comparison, for any value of n and for each of the two algorithms, we select the pair ∆ w , Γ w which corresponds to the largest regret (we search in a grid of values with µ 1 = 1.5, µ 2 ∈ [0.4; 1.5], σ 2 1 ∈ [0.0; 0.25], and σ 2 2 = 0.25, so that ∆ ∈ [0.0; 0.25] and Γ ∈ [0.0; 1.1]). As discussed in Sect. 4, while the worst-case regret of ExpExp keeps decreasing over n, it is always possible to find a problem for which regret of MV-LCB stabilizes to a constant. For numerical results with multiple values of ρ and 15 arms, see App. D in [START_REF] Sani | Risk-aversion in multi-arm bandit[END_REF].

Discussion

In this paper we evaluate the risk of an algorithm in terms of the variability of the sequences of samples that it actually generates. Although this notion might resemble other analyses of bandit algorithms (see e.g., the high-probability analysis in [START_REF] Audibert | Exploration-exploitation trade-off using variance estimates in multi-armed bandits[END_REF]), it captures different features of the learning algorithm. Whenever a bandit algorithm is run over n rounds, its behavior, combined with the arms' distributions, generates a probability distribution over sequences of n rewards. While the quality of this sequence is usually defined by its cumulative sum (or average), here we say that a sequence of rewards is good if it displays a good trade-off between its (empirical) mean and variance. The variance of the sequence does not coincide with the variance of the algorithm over multiple runs. Let us consider a simple case with two arms that deterministically generate 0s and 1s respectively, and two different algorithms. Algorithm A 1 pulls the arms in a fixed sequence at each run (e.g., arm 1, arm 2, arm 1, arm 2, and so on), so that each arm is always pulled n/2 times. Algorithm A 2 chooses one arm uniformly at random at the beginning of the run and repeatedly pulls this arm for n rounds. Algorithm A 1 generates sequences such as 010101... which have high variability within each run, incurs a high regret (e.g., if ρ = 0), but has no variance over multiple runs because it always generates the same sequence. On the other hand, A 2 has no variability in each run, since it generates sequences with only 0s or only 1s, suffers no regret in the case of variance minimization, but has high variance over multiple runs since the two completely different sequences are generated with equal probability. This simple example shows that an algorithm with small standard regret (e.g., A 1 ), might generate at each run sequences with high variability, while an algorithm with small mean-variance regret (e.g., A 2 ) might have a high variance over multiple runs.

Conclusions

The majority of multi-armed bandit literature focuses on the problem of minimizing the regret w.r.t. the arm with the highest return in expectation. In this paper, we introduced a novel multi-armed bandit setting where the objective is to perform as well as the arm with the best risk-return trade-off.

In particular, we relied on the mean-variance model introduced in [START_REF] Markowitz | Portfolio selection[END_REF] to measure the performance of the arms and define the regret of a learning algorithm. We show that defining the risk of a learning algorithm as the variability (i.e., empirical variance) of the sequence of rewards generated at each run, leads to an interesting effect on the regret where an additional algorithm variance appears. We proposed two novel algorithms to solve the mean-variance bandit problem and we reported their corresponding theoretical analysis. To the best of our knowledge this is the first work introducing risk-aversion in the multi-armed bandit setting and it opens a series of interesting questions. Lower bound. As discussed in the remarks of Thm. 1 and Thm. 2, MV-LCB has a regret of order O( K/n) on easy problems and O(1) on difficult problems, while ExpExp achieves the same regret O(K/n 1/3 ) over all problems. The primary open question is whether O(K/n 1/3 ) is actually the best possible achievable rate (in the worst-case) for this problem. This question is of particular interest since the standard reward expectation maximization problem has a known lower-bound of Ω( 1/n), and a minimax rate of Ω(1/n 1/3 ) for the mean-variance problem would imply that the risk-averse bandit problem is intrinsically more difficult than standard bandit problems. Different measures of return-risk. Considering alternative notions of risk is a natural extension to the mean-variance setting. In fact, over the years the mean-variance model has often been criticized. From a point of view of the expected utility theory, the mean-variance model is only justified under a Gaussianity assumption on the arm distributions. It also violates the monotonocity condition due to the different orders of the mean and variance and is not a coherent measure of risk [START_REF] Artzner | Coherent measures of risk[END_REF]. Furthermore, the variance is a symmetric measure of risk, while it is often the case that only one-sided deviations from the mean are undesirable (e.g., in finance only losses w.r.t. to the expected return are considered as a risk, while any positive deviation is not considered as a real risk). Popular replacements for the mean-variance are the α value-at-risk (i.e., the quantile) or Conditional Value at Risk (otherwise known as average value at risk, tail value at risk, expected shortfall and lower tail risk) or other coherent measures of risk [START_REF] Artzner | Coherent measures of risk[END_REF]. While the estimation of the α value-at-risk might be challenging 8 , concentration inequalities exist for the CVaR [START_REF] David | Large deviations bounds for estimating conditional value-at-risk[END_REF]. Another issue in moving from variance to other measures of risk is whether single-period or multi-period risk evaluation should be used. While the single-period risk of an arm is simply the risk of its distribution, in a multi-period evaluation we consider the risk of the sum of rewards obtained by repeatedly pulling the same arm over n rounds. Unlike the variance, for which the variance of a sum of n i.i.d. samples is simply n times their variance, for other measures of risk (e.g., α value-at-risk) this is not necessarily the case. As a result, an arm with the smallest single-period risk might not be the optimal choice over a horizon of n rounds. Therefore, the performance of an algorithm should be compared to the smallest risk that can be achieved by any sequence of arms over n rounds, thus requiring a new definition of regret.

Simple regret. Finally, an interesting related problem is the simple regret setting where the learner is allowed to explore over n rounds and it only suffers a regret defined on the solution returned at the end. It is known that it is possible to design an algorithm able to effectively estimate the mean of the arms and finally return the best arm with high probability. In the risk-return setting, the objective would be to return the arm with the best risk-return tradeoff.

Figure 1 :

 1 Figure 1: Pseudo-code of the MV-LCB algorithm. Definition 3. The pseudo regret for a learning algorithm A over n rounds is defined as

Figure 2 :

 2 Figure 2: Regret of MV-LCB and ExpExp in different scenarios.

The analysis is for the pseudo-regret but it can be extended to the true regret (see Remark

at p.23 of[START_REF] Audibert | Exploration-exploitation trade-off using variance estimates in multi-armed bandits[END_REF]).[START_REF] Artzner | Coherent measures of risk[END_REF] The coefficient of risk tolerance is the inverse of the more popular coefficient of risk aversion A = 1/ρ.

More precisely, it can be shown that this term decreases with rate O(K log(1/δ)/n) with probability 1-δ.

Note that in this case (i.e., ∆ = 0), Thm. 1 does not hold, since the optimal arm is not unique.

Notice that this is always possible for a large majority of distributions with independent mean and variance.

In the definition and in the following analysis we ignore rounding effects.

Notice that although in the paper we assumed the distributions to be bounded in [0, 1] all the results can be extended to sub-Gaussian distributions.

While the cumulative distribution of a random variable can be reliably estimated (see e.g.,[START_REF] Massart | The tight constant in the dvoretzky-kiefer-wolfowitz inequality[END_REF]), estimating the quantile might be more difficult

Acknowledgments This work was supported by Ministry of Higher Education and Research, Nord-Pas de Calais Regional Council and FEDER through the "contrat de projets état region 2007-2013", European Community's Seventh Framework Programme (FP7/2007-2013) under grant agreement n • 270327, and PASCAL2 European Network of Excellence.


Mohammad Ghavamzadeh

Alessandro Lazaric

Conservative and Greedy Approaches to Classification-based Policy Iteration

The existing classification-based policy iteration (CBPI) algorithms can be divided into two categories: direct policy iteration (DPI) methods that directly assign the output of the classifier (the approximate greedy policy w.r.t. the current policy) to the next policy, and conservative policy iteration (CPI) methods in which the new policy is a mixture distribution of the current policy and the output of the classifier. The conservative policy update gives CPI a desirable feature, namely the guarantee that the policies generated by this algorithm improve at each iteration. We provide a detailed algorithmic and theoretical comparison of these two classes of CBPI algorithms. Our results reveal that in order to achieve the same level of accuracy, CPI requires more iterations, and thus, more samples than the DPI algorithm. Furthermore, CPI may converge to suboptimal policies whose performance is not better than DPI's.

Introduction

Policy iteration [START_REF] Howard | Dynamic Programming and Markov Processes[END_REF]) is one of the two main classes of dynamic programming (DP) algorithms to find an optimal policy for a Markov decision process (MDP). It is an iterative algorithm that discovers an optimal policy by generating a sequence of monotonically improving policies. At each iteration k of this algorithm, given the current policy π k , an improved policy π k+1 is generated as the greedy policy w.r.t. the action-value function Q π k , i.e., π k+1 = Gπ k . In MDPs with large or continuous state and action spaces, policy iteration often fails to improve the policy π k efficiently (to find the exact Gπ k ), mainly because it cannot compute Q π k exactly, and as a result approximation schemes are required. There are two main approaches to approximate policy iteration (API). The most common approach is to find a good approximation of the value function of π k in a real-valued function space, and then compute π k+1 as the greedy policy w.r.t. this approximation (e.g., Lagoudakis and Parr 2003a). The other variant of API, which is more recent and less studied, replaces the approximation of the action-value function over the entire stateaction space with a learning step in a policy space [START_REF] Kakade | On the Sample Complexity of Reinforcement Learning[END_REF]Lagoudakis and Parr 2003b;[START_REF] Fern | Approximate policy iteration with a policy language bias: Solving relational Markov decision processes[END_REF]Lazaric, Ghavamzadeh, and Munos 2010a). In this approach, at each iteration we solve a classification problem in order to find a policy in a given policy space that best predicts the greedy action at every state. Thus, this class of API algorithms is called classification-based policy iteration (CBPI).

The existing CBPI methods can be divided into two groups according to the way that they generate the next policy π k+1 from the output of the classifier. The first group directly assigns the output of the classifier to the next policy, therefore are called direct policy iteration (DPI) algorithms. The CBPI algorithms by Lagoudakis and Parr (2003b) and [START_REF] Fern | Approximate policy iteration with a policy language bias: Solving relational Markov decision processes[END_REF] and the algorithm presented and analyzed in Lazaric et al. (2010a) belong to this category. The second group of CBPI algorithms perform a more conservative policy update in which the new policy π k+1 is a mixture distribution of the current policy π k and the output of the classifier. This group of algorithms are introduced and analyzed in [START_REF] Kakade | Approximately optimal approximate reinforcement learning[END_REF] and [START_REF] Kakade | On the Sample Complexity of Reinforcement Learning[END_REF] under the name conservative policy iteration (CPI).1 By using a conservative policy update, CPI aims at avoiding the main drawback of the DPI methods, i.e., the significant policy degradation resulted from the direct use of approximate greedy policies. This gives CPI two particularly desirable features: 1) it guarantees to improve the policy at each iteration, i.e., the value function of π k+1 is larger on average than the value function of π k , and 2) it has a stopping condition based on the quality of the generated policy (it stops whenever it cannot guarantee that the new policy has a better performance than the previous one). These features can potentially make CPI a very appealing API algorithm, mainly because other API methods have no guarantee to generate monotonically improving policies. This includes both value function based API algorithms such as LSPI (Lagoudakis and Parr 2003a) and classificationbased API methods other than CPI. Unfortunately, unlike the DPI methods, that have been fully analyzed (Lazaric, Ghavamzadeh, and Munos 2010a) and successfully applied to benchmark problems (Lagoudakis and Parr 2003b;[START_REF] Fern | Approximate policy iteration with a policy language bias: Solving relational Markov decision processes[END_REF][START_REF] Gabillon | Classification-based policy iteration with a critic[END_REF]), CPI has not been empirically evaluated and its performance bounds have not been studied in details and thoroughly compared to other API algorithms.

The main objective of this paper is to better understand the behavior of the CPI algorithm and to find out whether its two main features actually lead to a better performance.

To answer this question, we perform a detailed algorithmic and theoretical comparison of these two classes of CBPI algorithms. Our analysis reveals that in order to achieve the same level of accuracy, CPI requires more iterations, and thus, more samples than the DPI algorithm. This indicates that although CPI's conservative update allows it to have a monotonically improving behavior, it slows down the algorithm and increases its sample complexity. Furthermore, CPI may converge to suboptimal policies whose performance is not better than DPI.

Preliminaries

In this section, we set the notation used throughout the paper. A discounted Markov decision process (MDP) M is a tuple X , A, r, p, γ , where the state space X is a bounded closed subset of a Euclidean space ℜ d , the set of actions A is finite (|A| < ∞), the reward function r : X × A → [0, 1], the transition model p(•|x, a) is a distribution over X , and γ ∈ (0, 1) is a discount factor. We denote by ρ a distribution over the state space X . We define a policy π : X → P(A) as a function mapping each state to a probability distribution over actions. If the policy is deterministic then π simply maps each state to an action in A, i.e., π : X → A. We use B π (X ) to denote the space of deterministic policies.

For a given policy π, we define its γ-discounted value function V π : X → [0, 1] as the normalized expected sum of discounted rewards obtained by following π, i.e.,

V π (x) = (1 -γ)E ∞ t=0 γ t r(x t , a t )|x 0 = x, a t ∼ π(x t ) ,
where the expectation is w.r.t. to the stochastic transitions and the stochastic policy (if π is stochastic). Given a state distribution ρ, with an abuse of notation, we define the average value function as V π (ρ) = E x∼ρ V π (x) . The optimal policy π * is the policy which maximizes the value function (i.e., π * = arg max V π (ρ)) and its corresponding value is the optimal value function V * = V π * . We also define the γ-discounted action-value function

Q π : X × A → [0, 1] as Q π (x, a) = (1 -γ) r(x, a) + E ∞ t=1 γ t r(x t , a t )|a t ∼ π(x t ) .
If the action a is chosen according to a policy π ′ , then we define

Q π (x, π ′ ) = E a∼π ′ (x) Q π (x, a) , whose average value w.r.t. a state distribution ρ is denoted by Q π (ρ, π ′ ) = E x∼ρ Q π (x, π ′ ) .
We then define the greedy policy operator G : B π (X ) → B π (X ) as

(Gπ)(x) = arg max a∈A Q π (x, a), ∀x ∈ X , (1)
so that Gπ is the greedy policy w.r.t. Q π . We also define the advantage function A π : X × A → [-1, 1], which indicates how much an action a improves the performance of π in state x,

A π (x, a) = Q π (x, a) -V π (x).
We define the advantage of a policy π ′ w.r.t. to π as A π (x, π ′ ) = E a∼π ′ (x) A π (x, a) , and its average advantage w.r.t. to a state distribution ρ as A π (ρ, π ′ ) = E x∼ρ A π (x, π ′ ) . Finally, we recall the definition of the future-state discounted distribution d π ρ of policy π when the initial state is drawn from a distribution ρ as

d π ρ (x) = (1 -γ) ∞ t=0 γ t P[x t = x|ρ, π].
For each of the above quantities, we need to define their estimated counterparts. First, a H-horizon rollout of a policy π for a state-action pair (x, a) is defined as

R π (x, a) = (1 -γ) r(x, a) + H-1 t=1 γ t r(x t , a t ) , (2)
where

x 1 ∼ p(•|x, a), x t ∼ p • |x t-1 , a t-1
, and a t-1 ∼ π(x t-1 ). If M independent rollouts are available at a stateaction pair (x, a), then we can estimate Q π (x, a) as

Q π (x, a) = 1 M M j=1 R π j (x, a). (3)
Let D = {x i } N i=1 be a set of N states drawn independently from a state distribution µ, then the estimated average action-value function for a policy π ′ is defined as

Q π ( µ, π ′ ) = 1 N N i=1 E a∼π ′ (xi) Q π (x i , a) .
Similarly, we may define the estimated advantages A π (x, a), A π (x, π ′ ), and A π ( ρ, π ′ ).

CPI and DPI Algorithms

In this section, we provide a detailed algorithmic comparison of direct policy iteration (DPI) (Lazaric, Ghavamzadeh, and Munos 2010a) and conservative policy iteration (CPI) [START_REF] Kakade | Approximately optimal approximate reinforcement learning[END_REF][START_REF] Kakade | On the Sample Complexity of Reinforcement Learning[END_REF] methods.

The General Structure

Before getting into the details of each of the two algorithms, we first describe their common structure (Figure 1). A classification-based policy iteration (CBPI) algorithm takes as input a policy space Π, a state distribution ρ, and an accuracy parameter ǫ that defines the stopping condition of the algorithm. Given the desired accuracy ǫ, the algorithm first sets the number of rollout states N , the number of rollouts per state-action pair M , and the rollout horizon H (Step (a)).

These parameters define the total number of transitions used at each iteration of the algorithm (the per-iteration budget B). As it will be discussed in the next section, the choice of these parameters depends on the performance bound of the algorithm at each iteration. Starting with an arbitrary policy π 0 ∈ Π, the algorithm can be summarized in the following main steps. At Step (b), the algorithm builds a rollout set D k = {x i } N i=1 , with states x i drawn from a sampling distribution µ k defined according to the input distribution ρ and the current policy π k . For each of the rollout states x ∈ D k and for each action a ∈ A, a rollout estimate of the actionvalue function of the current policy

(ǫ) repeat (b) Set µ k = ρ Build the rollout set D k = {xi} N i=1 , xi ∼ µ k for all states xi ∈ D k and actions a ∈ A do (c) Compute an estimate Q π k (xi, a) with M rollouts end for (d) Compute the approximate greedy policy π ′ w.r.t. π k (e) π k+1 = π ′ k = k + 1 until (f) k ≤ K(ǫ)
Q π k (x, a) is computed at Step (c) (see Eqs. 2 and 3). Step (d) receives the estimated action-values Q π k (x, a), ∀x ∈ D k , ∀a ∈ A,
and computes an approximation of Gπ k . More precisely, the approximated greedy policy π ′ is computed as

π ′ = arg max π∈Π Q π k ( µ k , π). (4)
Note that this problem can be cast as a cost-sensitive classification problem, in which the training set is of the form

(x i , a), Q π k (x i , a) N i=1 , ∀a ∈ A. Finally, at
Steps (e) and (f), the algorithm first constructs the next policy π k+1 using π k and π ′ , and then checks a termination condition. ). After computing the per-iteration budget (i.e, N , M , and H), DPI also determines the total number of iterations K(ǫ) needed to meet the required accuracy ǫ (Step (a')). This reduces the termination condition at Step (f) to a simple condition on the number of iterations ran so far. Note that at each iteration the algorithm builds the rollout set with states drawn from ρ (Step b), and runs M rollouts for each state-action pair (Step (c)). Finally, the policy at the next iteration π k+1 is set to π ′ (Step (e)).

DPI Algorithm

′ w.r.t. π k (e) Compute α = A( µ k ,π ′ )-ǫ/3 4 (1 -γ) (e') π k+1 = (1 -α)π k + απ ′ k = k + 1 until (f) A( µ k , π ′ ) ≤ 2ǫ 3

CPI Algorithm

Figure 3 shows how the conservative policy iteration (CPI) algorithm [START_REF] Kakade | Approximately optimal approximate reinforcement learning[END_REF][START_REF] Kakade | On the Sample Complexity of Reinforcement Learning[END_REF] implements each of the steps of the general CBPI structure. In CPI, the sampling distribution µ k is set to the future-state discounted distribution d π k ρ of the current policy π k (Step (b)). In practice, in order to generate samples x i from the distribution d π k ρ , we first draw a state x 0 from ρ and then we follow policy π k . At each step t, the current state x t is either accepted as x i with probability γ and the simulation stops or it is rejected with probability 1 -γ and the rollout continues. If the rollout is not terminated after H steps (the rollout horizon), then it is forced to terminate and the last state x H is selected as x i . Once the rollout set is built, one single rollout is run for each state-action pair (Step (c)). While the approximate greedy policy π ′ is computed as in Eq. 4 (Step (d)), CPI constructs the next policy π k+1 in a conservative way as a mixture distribution of the current policy π k and the approximate greedy policy π ′ with a suitable mixing parameter α. The algorithm stops when the estimated advantage of π ′ is smaller than 2ǫ/3 (Step (f)).

The Algorithmic Comparison

Given the sketch of the DPI and CPI algorithms in Figures 2 and3, we can now easily highlight their most relevant algorithmic differences. The first difference is in the construction of the rollout set D k , where DPI and CPI use the sampling distributions ρ and d π k ρ , respectively. This implies that the greedy policies approximated by the two algorithms are different. In fact, if we let the size of the rollout set, the number of rollouts, and the rollout horizon go to infinity, we have

π ′ CPI = arg max π∈Π Q π k (d π k ρ , π), π ′ DPI = arg max π∈Π Q π k (ρ, π).
If Π contains the actual greedy policy G(π k ), then π ′ CPI = π ′ DPI , otherwise CPI favors policies that improve π k in the regions of the state space reachable by π k itself, while DPI prefers policies with high action-values in the states covered by the state distribution ρ. The choice of d π k ρ is critical since it allows CPI to estimate the advantage A π k (d π k ρ , π ′ CPI ) which is used to compute a suitable α that guarantees π k+1 improves over π k (Step (e)). On the other hand, since DPI does not ensure any monotonic improvement, it does not require any specific sampling strategy. Once the rollout set is built, Steps (c) and (d) are the same for both algorithms. The other major difference is in the way the next policy π k+1 is generated in Step (e). While DPI simply sets the next policy π k+1 to π ′ , CPI returns a policy π k+1 which is a mixture of the current policy π k and the approximate greedy policy π ′ . In fact, CPI is based on the evidence that if π ′ has a sufficiently large average advantage A π k (µ k , π ′ ), then it is possible to compute a mixing parameter α such that the corresponding mixture π k+1 is guaranteed to improve the current policy (see Corollary 7.2.3 in Kakade 2003 for more details), i.e., the value function of π k+1 is larger than the value function of π k (V π k+1 (ρ) ≥ V π k (ρ)). Although this is a major advantage over DPI, it comes at the cost of using stochastic policies instead of deterministic ones, which may be problematic in some applications (e.g., in robotics). The difference in the computation of π k+1 also explains the different termination conditions (Step (f)). In fact, while DPI simply limits the number of iterations, CPI stops whenever it cannot guarantee a sufficient improvement over the current policy (which depends on the advantage A π k ( µ k , π ′ )). As discussed in the next section, this difference has a deep impact on the actual performance of the algorithms. In fact, the monotonic improvement of CPI may result in an excessively slow convergence to a solution which may not even be better than the solution found by DPI in fewer iterations.

CPI and DPI Performance Bounds

While in the last section we compared CPI and DPI from an algorithmic perspective, we now study how these differences affect the performance of these algorithms. In particular, we elaborate on their theoretical analysis in [START_REF] Kakade | Approximately optimal approximate reinforcement learning[END_REF]) (for CPI) and (Lazaric, Ghavamzadeh, and Munos 2010a) (for DPI), and reformulate their performance bounds in order to capture their similarities and differences and better explain their behaviors.

Thanks to the comparison in the previous section, we notice that, while the two algorithms are very similar in approximating the greedy policy π ′ at each iteration, they mainly differ in the way they compute the next policy π k+1 . Thus, we split the theoretical comparison into two parts, the part that takes into account the error in approximating the greedy policy π ′ , and the one which studies how this error is propagated through the iterations of the algorithms.2

Error in Approximating the Greedy Policy

As described in Figure 1 Steps (b-d), at each iteration k, the two algorithms (a CBPI algorithm in general) build a rollout set D k according to µ k , compute a rollout estimate Q π k (x i , a), ∀x i ∈ D k , ∀a ∈ A, and finally generate a training set for a classifier that solves a cost-sensitive classification problem and returns an estimated greedy policy π ′ (w.r.t. π k ). The quality of such a policy depends on two main factors (see also Eqs. 1 and 4): the number of transitions used to compute Q π k (x i , a), i.e., the per-iteration budget B(ǫ) at

Step (a), and the policy space Π (the classifier) to which π ′ belongs to. Although the results in [START_REF] Kakade | Approximately optimal approximate reinforcement learning[END_REF] and (Lazaric, Ghavamzadeh, and Munos 2010a) are stated differently and analyze slightly different quantities, it is easy to derive a general theorem bounding the actionvalue of π ′ w.r.t. policy π k and a distribution µ k . A proof of the following theorem is reported in Appendix.

Theorem 1 If the policy space Π received by the algorithm of Figure 1 has a finite VC-dimension V C(Π) = h < ∞, and the per-iteration budget is

B(ǫ) = 2N M H with N = Ω h ǫ 2 log 1 ǫδ , M = Ω(1), H = Ω log 1/ǫ 1 -γ ,
then at each iteration k, the algorithm returns an approximate greedy policy π ′ such that

Q π k (µ k , Gπ k ) -Q π k (µ k , π ′ ) ≤ (5) inf π∈Π Q π k (µ k , Gπ k ) -Q π k (µ k , π) + ǫ,
with probability at least 1 -δ (w.r.t. to random rollouts).

This bound actually decomposes the loss in the performance of π ′ w.r.t. Gπ k into a term which depends on the "richness" of the policy space Π and is usually referred to as approximation error, and the term ǫ which depends on the per-iteration budget (i.e., the number of transitions needed at each iteration) and is called the estimation error. As we will see in the next section, this decomposition is crucial to understand how this error is propagated by the two algorithms. We also notice that the number of rollouts per state-action pair M can be actually set to 1 for both algorithms.

Error Propagation

In Step (e), CPI and DPI use the approximate greedy policy π ′ in a completely different way. While DPI simply uses it as the next policy π k+1 and then iterates for K(ǫ) iterations, CPI generates a more conservative policy π k+1 by combining the current policy π k and π ′ which guarantees a monotonic improvement over π k in terms their average value functions. This different behavior naturally leads to a difference in the final performance. In fact, DPI usually does not converge to a fix policy and keeps oscillating between different policies (i.e., the so-called convergence to region). On the other hand, CPI monotonically improves the policies until it converges to a policy that cannot be improved any further. Although this nice property may suggest that CPI outperforms DPI, by a careful inspection of their theoretical properties we obtain some surprising results. Before stating the main theorems that contain the performance bounds of the algorithms, we need to introduce a few terms and assumptions that play a critical role in the comparison. Since we are interested in bounding the final performance of the algorithms in σ-norm, which might be different than the sampling distribution ρ, we use the following assumptions:

Assumption 1 For any policy π and any non-negative integers s and t, there exists a constant C σ,ρ (s, t) < ∞ such that σ(P * ) s (P π ) t ≤ C σ,ρ (s, t)ρ. We define

C DPI (σ, ρ) = (1 -γ) 2 ∞ s=0 ∞ t=0 γ s+t C µ,ρ (s, t). Assumption 2 The term C CPI (σ, ρ) = ||d π *
σ /ρ|| ∞ , which represents the mismatch between the γ-discounted future state distribution of the optimal policy π * for the starting state distribution σ and the distribution ρ, is bounded.

Similar to (Lazaric, Ghavamzadeh, and Munos 2010a), we refer to C DPI and C CPI as concentrability terms. We also define the approximation error of the algorithms as:

Definition 1 The inherent greedy error of a policy space Π is defined for DPI and CPI as follows:

d DPI (Π, GΠ) = sup π∈Π inf π ′ ∈Π Q π (ρ, Gπ) -Q π (ρ, π ′ ) , d CPI (Π, GΠ) = sup π∈Π inf π ′ ∈Π Q π (d π ρ , Gπ) -Q π (d π ρ , π ′ ) .
We now state the main results, i.e., the performance bounds of the algorithms.

Theorem 2 If the policy space Π received by CPI has a finite VC-dimension V C(Π) = h < ∞, and the per-iteration budget is B(ǫ) as in Theorem 1, then CPI stops after at most

K(ǫ) = O 1 ǫ 2
iterations and returns a policy π CPI such that

V * (σ) -V πCPI (σ) ≤ C CPI (σ, ρ) (1 -γ) 2 d CPI (Π, GΠ) + ǫ ,
with probability 1 -Kδ.

Theorem 3 If the policy space Π received by DPI has a finite VC-dimension V C(Π) = h < ∞, and the per-iteration budget is B(ǫ) as in Theorem 1, then DPI runs for

K(ǫ) = O log 1/ǫ (1 -γ)
iterations and returns a policy π DPI such that

V * (σ) -V πDPI (σ) ≤ C DPI (σ, ρ) (1 -γ) 2 d DPI (Π, GΠ) + ǫ ,
with probability 1 -Kδ.

While the proof of Theorem 2 is reported in the Appendix, Theorem 3 is a rewriting of Theorem 6 in [START_REF] Lazaric | Analysis of a classification-based policy iteration algorithm[END_REF].

Remark 1 (approximation error). The first interesting result is the definition of approximation error d CPI (Π, GΠ) in CPI. In order to understand it better, let us consider the asymptotic case where ǫ = 0 (using infinite number of rollouts and iterations). Since CPI improves the quality of the policy at each iteration, one might expect it to return the policy π ∈ Π that best approximates the performance of π * , i.e., π = arg max π∈Π V π (d π * ρ ). However, unlike exact policy iteration where monotonic improvement is enough to guarantee convergence to the optimal policy, CPI may converge to a suboptimal policy. The approximation error d CPI (Π, GΠ) exactly bounds the error of the worst suboptimal policy that CPI can converge to (see also Appendix to find out how the approximation error appears in the final bound of CPI). Another interesting aspect of the result is the striking similarity between the approximation error terms of the algorithms. Apart from the use of two different norms ρ and d π ρ , CPI may converge to a policy with the same quality as the one returned by DPI. This is surprising since at each iteration DPI does not have any guarantee to improve over the current policy and it may oscillate between multiple policies. Nonetheless, the performance of such policies is not worse than the suboptimal policy CPI can converge to. Finally, we note that

d CPI (Π, GΠ) ≥ (1 -γ)d DPI (Π, GΠ).
Although this inequality does not imply any strict ordering between the two error terms, it suggests that for γ close to 1, CPI may have a worse approximation error than DPI.

Remark 2 (number of iterations). One of the major differences in the bounds is the number of iterations K(ǫ) that CPI needs to converge and DPI needs to run in order to guarantee an ǫ accuracy (estimation error). This indicates that CPI requires exponentially more iterations than DPI to obtain the same accuracy. This is because it converges after 1/ǫ 2 iterations, while DPI only needs log(1/ǫ)/(1 -γ) steps. This result is not completely surprising since CPI performs conservative updates and modifies the current policy with a step-size α, which can be very small, while DPI always performs a full update and set the new policy to the (approximate) greedy policy. Based on the number of iterations and the approximation error, we may conclude that CPI is over-conservative, and although DPI does not necessarily improve its performance monotonically, it could converge to policies which are as good as CPI with much less iterations, and thus, less number of samples. However, we should note that K(ǫ) in DPI has a factor 1/(1 -γ) which can be large when γ is close to 1, thus forcing DPI to run for many iterations before having ǫ accuracy. Moreover, we remark that the K(ǫ) in Theorem 2 may largely over-estimate the actual number of iterations the algorithm needs before stopping. In fact, the upper-bound is tight only when at each iteration the advantage of π ′ is very close to ǫ (see Step (f) in Figure 3), the starting policy has an average value of 0, and the returned policy has an average value of 1, conditions which are not likely to happen in general.

Remark 3 (concentrability terms). Another difference in the bounds is in the concentrability terms C DPI (σ, ρ) and C CPI (σ, ρ) defined in Assumptions 1 and 2. These terms indicate that selecting the input distribution ρ (in relation to the evaluation distribution σ and the MDP) may have a significant effect on the final performance of the algorithms. Unfortunately, selecting the right ρ requires complete knowledge of the MDP and some related quantities that are not usually available in advance, such as the optimal policy π * itself. This is why we usually set ρ to a safe distribution such as uniform in order to make sure that the concentrability terms remain bounded. One potential advantage of CPI over DPI is that if some knowledge about the stationary distribution d π * σ of the optimal policy π * is available, it would be possible to select ρ so as to minimize C CPI (σ, ρ), while knowing π * is not enough to optimize the concentrability terms C DPI (σ, ρ) in the DPI algorithm.

Remark 4 (convergence of DPI). In case the DPI algorithm converges to a policy π, using the results of Sec. 4.2 of Lazaric et al. (2010a), we can show that

V * -V π ≤ (I -γP * ) -1 Q π (G π) -Q π (π) .
This point-wise inequality implies the following final performance bound for the DPI algorithm:

V * (σ) -V π (σ) ≤ C CPI (σ, ρ) 1 -γ d DPI (Π, GΠ) + ǫ . (6)
Comparing Eq. 6 with the bound of Theorem 3, we note two major improvements in the performance bound of DPI: 1) the bound has been improved by a factor 1/(1 -γ), which is significant especially when γ is close to 1, and 2) the CPI concentrability term, which can be better optimized than its DPI counterpart (see Remark 3), appears in the DPI bound. This indicates that in case DPI converges, it achieves a performance superior to the one by CPI with a factor 1/(1 -γ).

Conclusions

In this paper, we provided a detailed algorithmic and theoretical comparison of the two classes of classification-based policy iteration algorithms: direct policy iteration (DPI) and conservative policy iteration (CPI). The main objective was to fully understand the potential advantages of the CPI algorithm, particularly the fact that it guarantees to generate policies that improve at each iteration before the algorithm terminates. This desirable feature suggests that CPI could outperform the standard approximate policy iteration methods whose full greedy updates do not necessarily lead to monotonically improving policies. In this paper, we first identified similarities and differences between CPI and DPI, and highlighted the parts of the algorithms that have major impact in their performance. The theoretical analysis then led to two interesting findings: 1) in order to achieve the same level of accuracy, CPI requires more iterations, and thus, more samples than DPI (see Remark 2), and 2) CPI may converge to suboptimal policies whose performance is no better than the one achieved by DPI (see Remark 1). This indicates that CPI's conservative update comes at the cost of increasing the sample complexity of the algorithm. Nonetheless, as reported in Remarks 2 and 3, CPI may still be a valid choice when γ is close to 1 and some knowledge of the stationary distribution of the optimal policy is available. Finally, we remark that the results reported in the paper in terms of the comparison between the conservative and direct policy updates are not necessarily limited to the classification-based approach to policy iteration. In fact, the results and analysis can be easily extended to any value function based policy iteration methods (e.g., LSPI) by simply replacing Theorem 1 with a suitable bound on the policy evaluation error (Theorems 2 and 3 remain unchanged).

2003), if N and H are chosen as in Theorem 1, and the second two terms are smaller than zero by the definition of π ′ as the best policy in Π w.r.t. the estimated action-value function Q π k ( µ k , •). The statement follows by adding and subtracting Q π k (µ k , Gπ k ) and reordering the terms.

We now turn to the proof of Theorem 2. In the original analysis of CPI reported in [START_REF] Kakade | Approximately optimal approximate reinforcement learning[END_REF] no approximation error appears explicitly in the final bound. The reason is that by Definition 4.3 in [START_REF] Kakade | Approximately optimal approximate reinforcement learning[END_REF], it is assumed that the greedy policy π ′ returned at Step (d) is always ǫ close to the actual greedy policy Gπ k . In general, it is not possible to guarantee such a performance, since the quality of the policy space Π in approximating the greedy policy is directly related to the classifier. In fact, it is clear from Theorem 1 that even if an infinite number of rollouts is used to compute π ′ , its performance is still constrained by the quality of the policy space Π. In the following, we report the steps needed to introduce the approximation error in the analysis of [START_REF] Kakade | Approximately optimal approximate reinforcement learning[END_REF].

Proof of Theorem 2: Similar to [START_REF] Kakade | Approximately optimal approximate reinforcement learning[END_REF], we define OPT(µ, π) = max π ′ A π (µ, π ′ ) as the maximum amount a policy π can be improved w.r.t. a distribution µ. Note that π ′ is any stationary policy defined over the MDP at hand and not the best policy in the policy space Π. We may rewrite OPT(µ, π) as OPT(µ, π) = max

π ′ Q π (µ, π ′ ) -V π (µ) = Q π (µ, Gπ) -V π (µ) = Q π (µ, Gπ) -Q π (µ, π) + Q π (µ, π) -V π (µ) = inf π ′ ∈Π Q π (µ, Gπ) -Q π (µ, π ′ ) + A π (µ, π),
where π = arg max π ′ ∈Π Q π (µ, π ′ ). From Theorem 7.3.3 in [START_REF] Kakade | On the Sample Complexity of Reinforcement Learning[END_REF], if the per-iteration budget is the same as in Theorem 1 and CPI is run for O(1/ǫ 2 ) iterations, then it returns a policy π CPI such that for any policy π ∈ Π, A(d πCPI ρ , π) ≤ ǫ. This means that the returned policy cannot be improved more than ǫ w.r.t. d πCPI ρ by the policies in the policy space Π. As a result, for any π ∈ Π, and thus, also for π, and µ = d πCPI ρ , we have OPT(µ, π CPI ) ≤ inf

π ′ ∈Π Q πCPI (µ, Gπ CPI ) -Q πCPI (µ, π ′ ) + ǫ.
Since π CPI is a random variable, the first term above is also a random variable, and thus, needs to be further upper bounded as

OPT(µ, π CPI ) ≤ sup π∈Π inf π ′ ∈Π Q π (µ, Gπ) -Q π (µ, π ′ ) + ǫ = d CPI (Π, GΠ) + ǫ.
We obtain the statement of Theorem 2 by plugging this result into Theorem 6.2 in [START_REF] Kakade | Approximately optimal approximate reinforcement learning[END_REF].

Input:

  Figure 1: The general structure of a classification-based policy iteration (CBPI) algorithm. Input: policy space Π, state distribution ρ, accuracy ǫ Initialize: Select an arbitrary policy π0 ∈ Π and set k = 0 (a) Compute the per-iteration budget B(ǫ) and N , M , H (a') Compute the total number of iterations K(ǫ) repeat (b) Set µ k = ρ Build the rollout set D k = {xi} N i=1 , xi ∼ µ k for all states xi ∈ D k and actions a ∈ A do (c) Compute an estimate Q π k (xi, a) with M rollouts end for (d) Compute the approximate greedy policy π ′ w.r.t. π k (e) π k+1 = π ′k = k + 1 until (f) k ≤ K(ǫ)

Figure 2 :

 2 Figure 2: The direct policy iteration (DPI) algorithm.

Figure 2

 2 Figure2shows how the direct policy iteration (DPI) algorithm implements each of the steps of the general CBPI structure. Although we focus on the specific DPI algorithm

Figure 3 :

 3 Figure 3: The conservative policy iteration (CPI) algorithm.

While in[START_REF] Kakade | Approximately optimal approximate reinforcement learning[END_REF] the algorithm is presented as a rollout value-based approach, in the more detailed description and analysis of CPI found in[START_REF] Kakade | On the Sample Complexity of Reinforcement Learning[END_REF], the algorithm is presented as a CBPI method. In Conclusions we will discuss how the comparison between DPI and CPI reported in this paper can be easily extended to any value-based approach.

As in[START_REF] Kakade | Approximately optimal approximate reinforcement learning[END_REF] and(Lazaric, Ghavamzadeh, and Munos 2010a), from this point on, we assume that the action space contains only two actions |A| = 2.

Acknowledgments

This work was supported by French National Research Agency (ANR) through the project LAMPADA n • ANR-09-EMER-007, by Ministry of Higher Education and Research, Nord-Pas de Calais Regional Council and FEDER through the "contrat de projets état region (CPER) 2007-2013", European Community's Seventh Framework Programme (FP7/2007-2013) under grant agreement n • 231495, and by PASCAL2 European Network of Excellence.

Appendix

In this section, we sketch the proof of Theorems 1 and 2.

Proof of Theorem 1: For DPI, the bound of Eq. 5 is obtained by noting that maximizing the action value (Eq. 4) is equivalent to minimize the loss defined in (Lazaric, Ghavamzadeh, and Munos 2010a) and by inverting the bound in Theorem 1 of (Lazaric, Ghavamzadeh, and Munos 2010a) (or more accurately in Theorem 5 of [START_REF] Lazaric | Analysis of a classification-based policy iteration algorithm[END_REF]).

For CPI, we first notice that the maximization of the action-value function corresponds to maximize the advantage and the bound of Eq. 5 is an immediate consequence of Lemma 7.3.4 in [START_REF] Kakade | On the Sample Complexity of Reinforcement Learning[END_REF]. We can write the following sequence of inequalities

where π = arg max π∈Π Q π k (µ k , π), and the first and the last two terms are bounded by Lemma 7.3.4 in (Kakade