Bilal Piot
email: bilal.piot@supelec.fr

Matthieu Geist
email: matthieu.geist@supelec.fr

Olivier Pietquin
email: olivier.pietquin@supelec.fr

Learning from Demonstrations: Is It Worth Estimating a Reward Function?

This paper provides a comparative study between Inverse Reinforcement Learning (IRL) and Apprenticeship Learning (AL). IRL and AL are two frameworks, using Markov Decision Processes (MDP), which are used for the imitation learning problem where an agent tries to learn from demonstrations of an expert. In the AL framework, the agent tries to learn the expert policy whereas in the IRL framework, the agent tries to learn a reward which can explain the behavior of the expert. This reward is then optimized to imitate the expert. One can wonder if it is worth estimating such a reward, or if estimating a policy is sufficient. This quite natural question has not really been addressed in the literature right now. We provide partial answers, both from a theoretical and empirical point of view.

Introduction

This paper provides a comparative study between two methods, using the Markov Decision Process (MDP) paradigm, that attempt to solve the imitation learning problem where an agent (called the apprentice) tries to learn from demonstrations of an expert. These two methods are Apprenticeship Learning (AL) [START_REF] Abbeel | Apprenticeship learning via inverse reinforcement learning[END_REF] and Inverse Reinforcement Learning (IRL) [START_REF] Russell | Learning agents for uncertain environments[END_REF]. In the AL framework, the agent tries to learn the expert policy or at least a policy which is as good as the expert policy (according to an unknown reward function). In the IRL framework, the agent tries to learn a reward which can explain the behavior of the expert and which is optimized to imitate it. AL can be reduced to classification [START_REF] Pomerleau | Alvinn: An autonomous land vehicle in a neural network[END_REF][START_REF] Atkeson | Robot learning from demonstration[END_REF][START_REF] Langford | Relating reinforcement learning performance to classification performance[END_REF][START_REF] Syed | A reduction from apprenticeship learning to classification[END_REF] where the agent tries to mimic the expert policy via a Supervised Learning (SL) method such as classification. There exist also several AL algorithms inspired by IRL such as [START_REF] Abbeel | Apprenticeship learning via inverse reinforcement learning[END_REF][START_REF] Syed | A game-theoretic approach to apprenticeship learning[END_REF] but they need to solve recursively MDPs which is a difficult problem when the state space is large and the dynamics of the MDP is unknown.

The key idea behind IRL is that the reward is the most succinct representation of the task. However, as the outputs of IRL algorithms are rewards, it is still required to solve an MDP to obtain an optimal policy with respect to this reward. With AL algorithms, the output is a policy which can be directly used. However, this policy is fixed and cannot adapt to a perturbation of dynamics which could be done if one knew the true reward, as it is a representation of the task possibly independent of the dynamics. Thus, a natural question arises: in which circumstances is it interesting to use an IRL algorithm, knowing that it still needs to solve an MDP in order to obtain a policy? First, we analyse the difference of value functions between the apprentice and the expert policies when a classifier is used as AL method (in the infinite horizon case). When compared to the sole (as far as we know) related result in IRL, quantifying the quality of an apprentice trained with the recently introduced SCIRL (Structured Classification based IRL) algorithm [START_REF] Klein | Inverse reinforcement learning through structured classification[END_REF], this analysis tells us that estimating a reward only adds errors. Then, we perform an empirical study on the generic Garnet framework [START_REF] Archibald | On the generation of markov decision processes[END_REF] to see if this first partial answer is confirmed. It turns out that it actually strongly depends on the (unknown) reward optimized by the expert: roughly, the less informative the reward is, the more IRL provides gains compared to AL. Finally, we push this empirical study even further by perturbing the dynamics of the MDP, which goes beyond the studied theory. In this case, the advantage of IRL is even clearer.

Background and Notations

General Notations

Let X = (x i ) {1≤i≤N X } be a finite set and f ∈ R X a function, f is identified to a column vector and f T is the transposition of f . The powerset of X is noted P(X). The set of probability distributions over X is noted ∆ X . Let Y be a finite set, ∆ Y X is the set of functions from Y to ∆ X . Let ζ ∈ ∆ Y X and y ∈ Y, ζ(y) ∈ ∆ X , which can be seen as the conditional distribution probability knowing y, is also noted ζ(.|y) and ∀x ∈ X , ζ(x|y) = [ζ(y)](x). Besides, let A ∈ P(X ), then χ A ∈ R X is the indicator function on the subset A ⊂ X . The support of f is noted Supp(f ). Moreover, let µ ∈ ∆ X , E µ [f ] is the expectation of the function f with respect to the probability µ. Let x ∈ X , x ∼ µ means that x is sampled according to µ. Finally, we define also for p ∈ N * , the L p -norm of the function f :

f p = ( x∈X (f (x) p )) 1 p , and f ∞ = max x∈X f (x).

Markov Decision Process

A finite Markov Decision Process (MDP) is a tuple M = {S, A, P, R, γ} where S = (s i ) {1≤i≤N S } is the finite state space, A = (a i ) {1≤i≤N A } is the finite action space, P ∈ ∆ S×A S is the Markovian dynamics of the MDP, R ∈ R S×A is the reward function and γ is the discount factor. A stationary and Markovian policy π ∈ ∆ S A represents the behavior of an agent acting in the MDP M. The set of all Markovian and stationary policies is noted Π M S = ∆ S A . When the policy π is deterministic, it can also be seen as an element of A S and π(s) is the action chosen by the policy π in state s. The quality of this behavior in the infinite horizon framework is quantified by the value function v π R ∈ R S which maps to each state the expected and discounted cumulative reward for starting in this state and following the policy π afterwards:

∀s ∈ S, v π R (s) = E[ t≥0 γ t R(s t , a t )|s 0 = s, π].
A policy π * R (according to the reward R) is said optimal if its value function v * R satisfies v * R ≥ v π R for any policy π and component wise. Let P π be the stochastic matrix P π = ( a∈A π(a|s)P(s |s, a)) {(s,s )∈S 2 } and R π ∈ R S the function such that: ∀s ∈ S, R π (s) = a∈A π(a|s)R(s, a). With a slight abuse of notation, we may write a the policy which associates the action a to each state s. The Bellman evaluation (resp. optimality) operators T π R (resp. T * R ) : R S → R S are defined as

T π R v = R π + γP π v and T * R v = max π T π R v.

These operators are contractions and v π

R and v * R are their respective fixed-points:

v π R = T π R v π R and v * R = T * R v * R . The action-value function Q π R ∈ S ×
A adds a degree of freedom on the choice of the first action, it is formally defined as

Q π R (s, a) = [T a R v π R ](s).
We also write, when it exists, ρ π ∈ R S the stationary distribution of the policy π (satisfying ρ T π P π = ρ T π ). The existence and uniqueness of ρ π is guaranteed when the Markov chain induced by the matrix of finite size P π is irreducible which will be supposed true in the remaining of the paper.

AL and IRL

AL and IRL are two methods that attempt to solve the imitation problem using the MDP paradigm. More precisely, in the AL framework, the apprentice, given some observations of the expert policy π E , tries to learn a policy π A which is as good as the expert policy according to the unknown reward R that the expert is trying to optimize (often the expert is considered optimal:

v π E R = v * R
). This can be expressed numerically: the apprentice tries to find a policy π A such that the quantity:

E ν [v π E R -v π A R ]
is the lowest possible, where ν ∈ ∆ S . In general ν = ρ where ρ is the uniform distribution or ν = ρ π E (ρ π E is also noted ρ E ). In the IRL framework, the apprentice is trying to learn a reward R which could explain the expert behavior. More precisely, given some observations of the expert policy π E , the apprentice is trying to learn R such that π E ≈ π * R. This can be expressed numerically, the apprentice is trying to learn a reward R such that the quantities

E ν [v π * R R -v π E R ] or E ν [v π E R -v π * R R ]
are the lowest possible.

Theoretical Study

This section gives some theoretical insights into the question: Is it worth estimating a reward. First, we present a theoretical result for AL reduced to classification for the infinite horizon case. A proof of this result is given on the appendix 6. The result is an upper bound on the difference of the value functions of the expert and apprentice policies. As a previous bound for AL reduced to classification in the finite horizon case had been proposed in [START_REF] Syed | A reduction from apprenticeship learning to classification[END_REF], we give an informal comparison of the two results. Besides, there is also a performance bound for an IRL algorithm [START_REF] Klein | Inverse reinforcement learning through structured classification[END_REF] (SCIRL) which allows us to compare IRL and AL performances from a theoretical point of view. We choose to compare those bounds because the classification and the SCIRL algorithms does not need to resolve iteratively MDPs. Thus, there is no Approximate Dynamic programming error to deal with and to propagate to obtain the performance of the algorithm.

AL Reduced to Classification for the Infinite Horizon Case

A simple way to realize an AL method is by pure mimicry via an SL method such as classification. More precisely, we assume that some demonstrations examples D E = (s i , a i ) {1≤i≤N } where a i ∼ π E (.|s i ) are available. Without loss of generality, we assume that the states s i are sampled according to some probability distribution ν ∈ ∆ S . So, the data (s i , a i ) are sampled according to the distribution µ E such that: µ E (s, a) = ν(s)π E (a|s). Then, a classifier is learnt based on these examples (with discrete actions, it is a multi-class classification problem) thanks to an SL algorithm. This outputs a policy π C ∈ A S , which associates to each state an action. The quality of the classifier is quantified by the classification error:

C = E µ E [χ {(s,a)∈S×A,π C (s) =a} ] = s∈S a∈A,a =π C (s) ν(s)π E (a|s).
The quality of the expert (respectively to the unknown reward function R) may be quantified with v π E R . Usually, it is assumed that the expert is optimal (that is,

v π E R = v * R
), but it is not necessary for the following analysis (the expert may be sub-optimal respectively to R). The quality of the policy π C can also be quantified by its value function v π C R . In the following, we bound

E ν [v π E R -v π C R ]
which represents the difference between the quality of the expert and the classifier policy. If this quantity is negative, that is fine, because (in mean), π C is better than π E . So, only an upper bound is computed. This upper-bound shows the soundness of the AL through classification method for the infinite horizon case.

Let define the following concentration coefficient:

C ν = (1 -γ) t≥0 γ t c ν (t)
where ∀t ∈ N, c ν (t) = max s∈S

(ν T P t π E )(s) ν(s) . Notice that if ν = ρ E , which is a quite reasonable assumption, then C ν = C ρ E = 1.
Theorem 1. Let π C be the classifier policy (trained on the data set D E to imitate the expert policy π E ). Let also C be the classification error and C ν the above defined concentration coefficient. Then ∀R ∈ R S×A :

E ν [v π E R -v π C R ] ≤ 2C ν R ∞ (1 -γ) 2 C .
The proof of Th. 1 is given on the appendix 6 and is based on the propagation of the classification error. In [START_REF] Syed | A reduction from apprenticeship learning to classification[END_REF], the authors have established similar bounds in the finite horizon case. However, as most of AL and IRL algorithms considered so far the infinite horizon framework, we think that our result has its interest.

The Bound on the Finite-Horizon Case

In this section, we introduce specific notations to the finite horizon case and we interpret the results from [START_REF] Syed | A reduction from apprenticeship learning to classification[END_REF]. Let consider a finite MDP M = {S, A, P, R} with horizon H and without discount factor γ. A Markovian and non-stationary policy is an element of the set Π H M S ; if π is non-stationary, then π t refers to the stationary policy that is equal to the t th component of π. Similarly to the infinite horizon case, we define the value function of the policy π at time t:

∀s ∈ S, v π t,R (s) = E[ H t =t R(s t , a t )|s t = s, π].
Let D t π be the distribution on state-action pairs at time t under policy π. In other words, a sample (s, a) is drawn from D t π by first drawing s 1 ∼ ν ∈ ∆ S , then following policy π for time steps 1 through t, which generates a trajectory (s 1 , a 1 , . . . , s t , a t ), and then letting (s, a) = (s t , a t ). More formally, we have:

∀1 ≤ t ≤ H, ∀(s, a) ∈ S × A, D t π,ν (s, a) = (ν T (P π 1 × • • • × P π t-1 ))(s)π t (a|s).
In [START_REF] Syed | A reduction from apprenticeship learning to classification[END_REF], the authors suppose the availability of the set of trajectories

D E = (ω i ) {1≤i≤N } where ω i = (s i 1 , a i 1 , . . . , s i H , a i H ) with s i 1 ∼ ν ∈ ∆ S and (s i t , a i t ) ∼ D t
π E where 1 ≤ t ≤ H and π E is the non-stationary and Markovian expert policy. In the finite horizon case, Apprenticeship Learning through classification will consists in learning an apprentice policy π C = (π t C ) {1≤t≤H} thanks to H classifiers trained on the sets

D t E = (s i t , a i t ) {1≤i≤N } . Thus, for each set D t E = (s i t , a i t ) {1≤i≤N }
, we train a multi-class classifier and learn a deterministic policy π t C with classification error:

t C = E D t E [χ {(s,a)∈S×A,π t C (s) =a} ].
We note C = max 1≤t≤H t C . Then we have the following theorem:

Theorem 2. Let π E be the expert non-stationary and Markovian expert policy, D E a set of N trajectories with s i 1 ∼ ν ∈ ∆ S and π C the policy learnt by the H classifiers, then:

E ν [v π E 1,R -v π C 1,R ] ≤ min(2 √ C H 2 , 4 C H 3 + δ π E ) R ∞ ,
where

δ π E = Eν [v * 1,R -v π E 1,R ] R ∞
represents the sub-optimality of the expert.

It is possible to compare these results with our bound, even if one deals with the infinite horizon case and the other with the finite horizon case, by informally noticing that the introduction of the discount factor γ in the infinite horizon corresponds to an horizon of length 1 1-γ : t≥0 γ t = 1 1-γ . By replacing H by 1 1-γ in the the precedent bound, we obtain:

E ν [v π E 1,R -v π C 1,R ] ≤ min( 2 √ C (1 -γ) 2 , 4 C (1 -γ) 3 + δ π E ) R ∞ .
So, if we informally identify the classification errors and the horizon H to 1 1-γ , our bound is slightly better either by √ C or by 2 1-γ . Moreover, as our bound is specific to the infinite horizon, it is more adapted to AL and IRL algorithms as most of them consider the infinite horizon case.

SCIRL and Its Performance Bound

[5] assume that the unknown reward is linearly parameterized by some feature vector. More precisely, let φ(s, a) = (φ 1 (s, a), . . . , φ p (s, a)) T be a feature vector composed of p ∈ N * basis functions φ i ∈ R S×A , the parameterized reward function is R θ (s, a) = θ T φ(s, a) = 1≤i≤p θ i φ i (s, a). Searching a good reward thus reduces to searching a good parameter vector θ ∈ R p . The choice of features is done by the user. Moreover, SCRIL needs the estimation of the expert feature expectation ω π E [START_REF] Klein | Inverse reinforcement learning through structured classification[END_REF] which is the expected discounted cumulative feature vector for starting in a given state, applying a given action and following the expert policy:

ω π E (s, a) = E[ t≥0 γ t φ(s t , a t )|s 0 = s, a 0 = a, π E ].
It can be seen that:

Q π E R θ (s, a) = θ T ω π E (s, a
). An estimation of the feature expectation ωπ E is done via the expert data set: D E . The problem of estimating the expert feature is a policy evaluation problem. Then, SCIRL uses the estimation of the expert feature expectation ωπ E as the basis function of a linearly parameterized score-based multi-class classifier fed by the set

D E . The classification error is C = E µ E [χ {(s,a)∈S×A,π C (s) =a} ] with π C (s) = argmax a∈A θ T
C ωπ E (s, a) and θ C the output of the score-based classifier. The reward outputted by the SCIRL algorithm is R C = θ T C φ. Then, the performance bound for this algorithm is:

0 ≤ E ρ E [v * R C -v π E R C ] ≤ C f (1 -γ) 2 R C ∞ C 1 -γ + Q , With C f = (1 -γ) t≥0 γ t c f (t) where ∀t ∈ N, c f (t) = max s∈S (ρ T E P t π * R C )(s) ρ E (s) . Moreover, Q = E ρ E [max a∈A Q (., a) -min a∈A Q (., a)], where Q (s, a) = θ T C (ω π E (s, a) -ω π E (s, a))
, is a measure of the error estimation of the feature expectation. This bound is specific to the reward R C and the constant C f is not equal to 1 when ν = ρ E , which makes this bound possibly quite worst than the pure classification bound, even when the expert feature expectation is perfectly estimated ( Q = 0). This seems to indicate that this IRL algorithm is less interesting than a simple classification algorithm in theory. However, in practice, we will see that for specific unknown rewards SCIRL can have much better performance than a classification algorithm (see Sec. 4).

Empirical Study

This section shows through experiments that the previous theoretical bounds does not tell everything about AL methods and IRL methods. Here, several experiments are conducted and show the interest of finding a reward thanks to a general framework of experiments called the Garnet framework. We choose a particular framework where all the problems are finite MDPs with a tabular representation. Even if those problems are not challenging, they allow comparing fairly the different approaches without the problem of bias induced by the choice of representation. The comparison is done between a pure classification algorithm and two recently published IRL algorithms which are SCIRL and Relative Entropy IRL (RE) [START_REF] Boularias | Relative entropy inverse reinforcement learning[END_REF], for which there is no known error analysis. The pure classification algorithm was chosen as a benchmark for the AL approach because it has a theoretical performance guarantee and does not need to resolve iteratively MDPs unlike most of the other algorithms. SCIRL and RE were chosen as benchmarks for the IRL approach because they also do not need to resolve iteratively MDPs which reduces the impact of Approximate Dynamic Programming (ADP) in the interpretation even if the outputted reward is optimized via the policy iteration algorithm. These experiments show that the choice of the underlying unknown reward, which is used in order to create the expert policy thanks to the policy iteration algorithm, is crucial. Indeed when the unknown reward is normally distributed on each state-action-couple the classification has quite good performance whereas it has quite low performance when the reward is sparse or state-only-dependent. The intuitive idea behind those results is: when the reward is too informative, the impact of the optimization horizon is reduced, which favors the classification approach.

AL and IRL Algorithms

The first algorithm is a pure classification algorithm. More precisely, it is multiclass classification algorithm fed by the set D E using a structured large-margin approach [START_REF] Taskar | Learning structured prediction models: A large margin approach[END_REF] which consists in minimizing the following criterion with respect to Q ∈ R S×A :

L0(Q) = 1 N N i=1 max a∈A [Q(si, a) + l(si, a)] -Q(si, ai) + λ Q 2 2 ,
where l(s, a) = 0 when ∃1 ≤ i ≤ N, (s, a) = (s i , a i ) and l(s, a) = 1 otherwise. The minimization is realized via a sub-gradient descent [START_REF] Shor | Minimization methods for non-differentiable functions[END_REF]. Then the policy obtained by the algorithm is a deterministic policy such that π C (s) ∈ argmax a∈A Q * (s, a) where Q * is the output of the minimisation of the criterion L 0 via the subgradient descent. The two other algorithms are IRL algorithms. SCIRL (presented in Sec. 3.3) needs only the set D E to be implemented and outputs a reward R C . The instantiation of SCIRL, in our experiments, is the one described in the original paper. In order to obtain a policy π C , this reward is optimized by the policy iteration algorithm with respect to the reward R C . The policy iteration algorithm needs the knowledge of the whole dynamics of the MDP to be implemented but allows a comparison which does not depend on the choice of an ADP algorithm (we need solving an MDP to measure the efficiency of the estimate, but not to obtain the estimate). Like SCIRL, the RE algorithm supposes a linear parametrization of the reward. The principle of the Relative Entropy method is based on minimizing the relative entropy (KL divergence) between the empirical distribution of the state-action trajectories under a random policy and the distribution of the trajectories under a policy that matches the expert feature expectation [START_REF] Boularias | Relative entropy inverse reinforcement learning[END_REF]. The RE algorithm used in this paper is the one described in the original paper. It needs the set D E and also requires a set D P of sampled trajectories according to a non-expert policy. In the experiments, the random policy will be chosen in order to generate the set D P (see Sec. 4.3). The output of the algorithm is a reward R C and a policy iteration algorithm is also used to obtain the policy π C relative to the outputted reward.

The Garnet Framework

The Garnet problems are a class of randomly constructed finite MDPs meant to be totally abstract while remaining representative of the kind of finite MDPs that might be encountered in practice [START_REF] Archibald | On the generation of markov decision processes[END_REF]). The routine to create an instance of a stationary Garnet problem is characterized by 3 parameters and written as Garnet(N S , N A , N B ). The parameters N S and N A are the number of states and actions respectively, and N B is a branching factor specifying the number of next states for each state action pair. The next states are chosen at random from the state set without replacement. The probability of going to each next state is generated by partitioning the unit interval at N B -1 cut points selected randomly. The reward R(s, a) will be chosen depending on the experiments. For each Garnet problem, it is possible to compute an expert policy π E thanks to the reward R via the policy iteration algorithm. Finally, the discount factor is fixed to 0.99.

Pure Classification Versus SCRIL and RE

The idea, in order to obtain a general result, is to run the same experiment on hundreds of MDPs and regroup the results at the end. All the algorithms are fed with data sets of the the following type: D E = (s i , a i ) {1≤i≤N } where a i ∼ π E (.|s i ). More particularly, D E = (ω j ) {1≤i≤K E } where ω j = (s i,j , a i,j ) {1≤i≤H E } is a trajectory obtained by starting from a random state s 1,j (chosen uniformly) and applying the policy π E H E times (s i+1,j ∼ P (.|s i,j , a i,j )). So, D E is composed by K E trajectories of π E of length H E and we have K E H E = N . We also fed the RE algorithms with a data set of sampled transitions D P = (s i , a i , s i ) {1≤i≤N } where a i ∼ π R (.|s i ) with π R the random policy (uniform distribution over the actions for each state) and where s i ∼ P (.|s i , a i ). Actually, D P has the particular form D P = (τ j ) {1≤j≤K P } where τ j = (s i,j , a i,j , s i,j ) {1≤i≤H P } is a trajectory obtained by starting from a random state s 1,j (chosen uniformly) and applying the policy π R H P times (s i,j = s i+1,j ∼ P (.|s i,j , a i,j )). So, D P is composed by K P trajectories of π R of length H P and we have K P H P = N . Therefore, if we have for a given Garnet problem π E and π R , the set of parameters (K E , H E , K P , H P ) is sufficient to instantiate sets of types D E and D P . Our first experiment shows the performance of the algorithms when H E is increasing and when the reward for each Garnet is chosen normally distributed for each state-action couple. The reward R(s, a) is selected randomly according to a normal distribution with mean 0 and with standard deviation 1. It consists in generating 100 Garnet problems of the type Garnet(N S , N A , N B ), where N S is uniformly chosen between 50 and 100, N A uniformly chosen between 5 and 10 and N B uniformly chosen between 2 and 5 . This gives us the set of Garnet problems G = (G p ) {1≤p≤100} . On each problem p of the set G, we compute π p E and π p R . The parameter H E takes its values in the set (H k E ) {1≤k≤11} = (50, 100, 150, .., 500), K E = 1, H P = 10, K P = 50. Then, for each set of parameters (K E , H k E , K P , H P ) and each G p , we compute 100 expert policy sets (D i,p,k E ) {1≤i≤100} and 100 random policy sets (D i,p,k P ) {1≤i≤100} . Our criteria of performance for each couple

(D i,p,k E , D i,p,k P ) is the following: T i,p,k = Eρ[v π p E R -v π i,p,k C R ] Eρ[v π p E R ]
, where π p E is the expert policy, π i,p,k C is the policy induced by the algorithm fed by the couple (D i,p,k E , D i,p,k P ) and ρ is the uniform distribution over the state space S. For the pure classifier, we have

π i,p,k C (s) ∈ argmax a∈A Q * (s, a)
where Q * is the minimizer of L 0 . For the SCIRL and RE algorithms, π i,p,k C is the policy obtained by optimizing the reward R C outputted by the algorithm via the policy iteration algorithm. Our mean criterion of performance for each set of parameters

(K E , H k E , K P , H P ) is: T k = 1 10000 1≤p≤100,1≤i≤100 T i,p,k .
For each algorithm we plot (H k E , T k ) {1≤k≤15} . Another criterion is also useful in order to interpret the results. For each Garnet problem and each set of parameters, we calculate the standard deviation std p,k for each algorithm: has a better performance over the IRL algorithms when the number of data is increasing. This can be explained by the particular shape of the reward which is particularly suited to make the pure classification algorithm work well and IRL algorithms work bad. Indeed, as there are rewards for each state-action couples which are normally chosen, doing a misclassification is not so important as there will be rewards with the same form in the next states. However, as there are a lot of rewards everywhere, a lot of data is needed for an IRL algorithm to be able to estimate a meaningful reward. Another possible but complementary interpretation of those results is: as the reward is very informative, the choice of the action does not depend too much on the future states and the impact of the optimization horizon is strongly reduced.

std p,k = 1 100 1≤i≤100 [T i,p,k -1≤j≤100 T j,p,k ] 2
The second experiment is exactly the same as the first one, except that the reward is no longer normally distributed. For each Garnet, we generate a reward with a small support: Supp(R) ≤ N S N A 50 by randomly choosing between 1 and

N S N A 50
couples (s, a) such that R(s, a) = 0 (reward randomly chosen between 0 and 1). For the other couples (s, a), R(s, a) = 0. Results are reported on Fig. 2. Here, we see that the IRL algorithms work better than previously and the pure classification algorithms has its performance deteriorated a little bit compared to the previous experiment. This can be explained by the shape of the unknown reward. As the unknown reward is sparse, doing a misclassification on a state where the expert choose the action that gives a reward is important as there are only few state-action couples with rewards. Thus, the pure classification algorithm may have some problems with few data which is what we observe on Fig. 2(a). Moreover, the IRL algorithms have a better performance, maybe because the unknown reward has a simpler structure to learn. Again as the reward is less informative, the impact of the optimization horizon may be more important than for the previous reward which deteriorates the performance of the classification. The third experiment is exactly the same as the first one, except that the reward is state-only-dependent. To construct a state-only-dependent reward, it is sufficient for each s ∈ S to select randomly a value R(s) according to a normal distribution with mean 0 and with standard deviation of the IRL algorithms is better than the second experiment and than the pure classification. This can be explained by the fact that the structure of the reward is even simpler. The pure classification see its performance deteriorated compared to the second experiment. As the unknown reward depends only on the state and not on the action, it is very important to follow the path of the expert to obtain a good performance. Thus, a misclassification on a given state which leads to a bad path can be very damageable and lead to bad performance.

Dynamics Perturbations

In this section, we want to show that it can be interesting to retrieve the reward in order to be more stable to dynamics perturbations. As the reward is seen as the most succinct hypothesis explaining the behavior of the expert, we can expect that the reward outputted by the IRL algorithms is such that its optimization will lead to a near-optimal behavior even if there is a dynamics perturbation.

The dynamics perturbations considered are the ones which keep identical the structure of the MDP. The structure of the MDP is for a given state-action couple (s, a) the different states that could be reached by choosing the action a in state s, that is Supp(P s,a ). The structure of the MDP is the set (Supp(P s,a )) {(s,a)∈S×A} . Therefore a dynamic perturbation is the choice of a dynamics P different from P such that: (Supp(P s,a )) {(s,a)∈S×A} = (Supp( Ps,a )) {(s,a)∈S×A} .

The first experiment consists in in generating 100 Garnet problems of the type Garnet(N S , N A , N B ), where N S is chosen randomly between 50 and 100, N A randomly chosen between 5 and 10 and N B chosen randomly between 2 and 5 . This gives us the set of Garnet problems G = (G p ) {1≤p≤100} . Here, The reward R(s, a) is selected randomly according to a normal distribution with mean 0 and with standard deviation 1. Then for each G p , we realize 50 dynamics perturbation and we obtain the set of Garnets problems G = (G p,q ) {1≤p≤100,1≤q≤50} . On each problem p, q of the set G, we compute π p,q E and π p,q R and on each problem p of the set G, we compute π p E and π p R . The parameter H E takes its values in the set (H k E ) {1≤k≤15} = (50, 100, 150, .., 500), K E = 1, H P = 10, K P = 50. Then, for each set of parameters (K E , H k E , K P , H P ) and each G p , we compute 100 expert policy sets (D i,p,k E ) {1≤i≤100} and 100 random policy sets (D i,p,k P ) {1≤i≤100} . Our criteria of performance for each couple (D i,p,k E , D i,p,k P ) each G p,q problem is the following:

T i,p,q,k = Eρ[v π p,q E R -v π i,p,k C R ] Eρ[v π p,q E R ]
, where π p,q E is the expert policy on the problem G p,q , π i,p,k C is the policy induced by the algorithm fed by the couple (D i,p,k E , D i,p,k P ) and ρ is the uniform distribution over the state space S. For the pure classifier, we have π i,p,k C (s) ∈ argmax a∈A Q * (s, a) where Q * is the output.

For the SCIRL and RE algorithms, π i,p,k C is the policy obtained by optimizing the reward R outputted by the algorithm via the policy iteration algorithm. Moreover, when π i,p,k C = π p E , then T i,p,q,k represents the best performance possible to achieve by an AL algorithm: this curve will be noted AL in our figures. Finally, when π i,p,k C = π p R , then T i,p,q,k represents the performance of the random policy and this curve will be noted Rand in our figures.

Our mean criterion of performance for each set of parameters (K E , H k E , K P , H P ) is: T k = 1 500000 1≤p≤100,1≤q≤50,1≤i≤100 T i,p,q,k . For each algorithm we plot (H k E , T k ) {1≤k≤15} . Another criterion is also useful in order to interpret the results. For each Garnet problem G p and each set of parameters, we calculate the standard deviation std p,k for each algorithm:

p,k std =    1 5000 1≤q≤50 1≤i≤100 [T i,p,q,k - 1≤q ≤50 1≤j≤100 T j,p,q ,k ] 2    1 2
.

Then we compute the mean standard deviation over the 100 Garnet problems for each set of parameters: std k = 1 100 1≤p≤100 std p,k . For each algorithm we plot (H k E , std k ) {1≤k≤15} . Results are reported on Fig. 4. Here, the reward is normally distributed so a dynamic perturbation may not deteriorate too much the expert policy. Indeed, as the reward is very informative, the impact of the optimization horizon must be very small and the perturbation of dynamics will not change too much the optimal policy. We can observe this on Fig. 4(a), where we see that the yellow curve noted AL is not so far away from 0. With this shape of reward, it is better to use a pure classification algorithm to have this stability property.

The second experiment is exactly the same as the previous one, except that the reward is sparse. Results are reported on Fig. 5. As the reward is sparse, we can expect that a dynamic perturbation leads to an important deterioration of the performance of the expert policy. Here, we see that IRL algorithms are under the yellow curve when the number of data is increasing, which means that no AL algorithms will be able to reach that level of stability. Thus, it seems that estimating a reward function in that case can be very useful because it guarantees a level of stability that no AL algorithms is able to provide.

The third experiment is exactly the same as the previous one, except that the reward is state-only-dependent. Results are reported on Fig. 6. Here the shape of reward is even simpler that the previous experiment. It seems that the IRL algorithms are even more stable with less data. Again, as the impact of the optimization horizon becomes important, the performance of the pure classification and the one of the best possible AL algorithm are really deteriorated.

Conclusion and Perspectives

In this paper, we tried to give some theoretical and empirical insights into the following question: is it worth estimating a reward function? First, we upperbounded the difference between the value function of the expert and the value function of the apprentice policy, for AL reduced to classification in the infinite horizon case. This result gives a better bound than the theoretical performance bound of the SCIRL algorithm and is informally better than the bound in the finite horizon case proved in [START_REF] Syed | A reduction from apprenticeship learning to classification[END_REF]. Thus, in theory, there are no specific reason to use an IRL algorithm which still needs to solve an MDP in order to obtain an optimal policy according to the reward found by the algorithm. However, in practice, the experiments conducted in this paper on a generic task (Garnet problems) show that for specific shapes of the unknown reward function, IRL algorithms have better performance than the pure classification algorithms and possess a stability property that no AL algorithm will be able to achieve. Besides, it seems that the reward functions that favor the IRL algorithms are the less informative ones. We think that the less informative the reward is, the bigger the impact of the optimization horizon is. This is an obvious disadvantage for the pure classification method which doest not take into account this optimization horizon.

However, there is no theoretical proof explaining why IRL algorithms work better with specific forms of reward functions. This can be an interesting perspective to give more soundness to the experiments leaded in this paper. Moreover, it would be interesting to create an algorithm able to use data coming from different perturbed dynamics of the same MDP in order to learn a reward function which will be even less sensible to perturbed dynamics. This can be useful with applications where human are involved: in those kind of real-life applications, each human can be seen as a perturbed version of an MDP.

1 2 .Fig. 1 .

 21 Fig. 1. Garnets experiment: normally distributed reward.

Fig. 2 .

 2 Fig. 2. Garnets experiment: sparse reward.

1 Fig. 3 .

 13 Fig. 3. Garnets experiment: state-only-dependent reward.

Fig. 4 .Fig. 5 .

 45 Fig. 4. Perturbed dynamics: normally distributed reward.

Fig. 6 .

 6 Fig. 6. Perturbed dynamics: state-only-dependent reward.

Acknowledgements. The research leading to these results has received partial funding from the European Union Seventh Framework Programme (FP7/2007-2013) under grant agreement n°270780.

Appendix: Proof of Th.1

We have:

R and Equality (c) is true by invertibility of I -γP π E where I ∈ R S×S is the identity matrix. The next step is to work on the term

Noticing that:

and by definition of Q π C R (s, a), we have:

So:

Thus by definition of C ν :

and Equality (e) is true by definition of C . This ends the proof.


Edouard Klein

Bilal Piot

Matthieu Geist

Olivier Pietquin

A Cascaded Supervised Learning Approach to Inverse Reinforcement Learning

This paper considers the Inverse Reinforcement Learning (IRL) problem, that is inferring a reward function for which a demonstrated expert policy is optimal. We propose to break the IRL problem down into two generic Supervised Learning steps: this is the Cascaded Supervised IRL (CSI) approach. A classification step that defines a score function is followed by a regression step providing a reward function. A theoretical analysis shows that the demonstrated expert policy is nearoptimal for the computed reward function. Not needing to repeatedly solve a Markov Decision Process (MDP) and the ability to leverage existing techniques for classification and regression are two important advantages of the CSI approach. It is furthermore empirically demonstrated to compare positively to state-of-the-art approaches when using only transitions sampled according to the expert policy, up to the use of some heuristics. This is exemplified on two classical benchmarks (the mountain car problem and a highway driving simulator).

Introduction

Sequential decision making consists in choosing the appropriate action given the available data in order to maximize a certain criterion. When framed in a Markov Decision Process (MDP) (see Sec. 2), (Approximate) Dynamic programming ((A)DP) or Reinforcement Learning (RL) are often used to solve the problem by maximizing the expected sum of discounted rewards. The Inverse Reinforcement Learning (IRL) [START_REF] Russell | Learning agents for uncertain environments[END_REF] problem, which is addressed here, aims at inferring a reward function for which a demonstrated expert policy is optimal.

IRL is one of many ways to perform Apprenticeship Learning (AL): imitating a demonstrated expert policy, without necessarily explicitly looking for the reward function. The reward function nevertheless is of interest in its own right. As mentioned in [START_REF] Russell | Learning agents for uncertain environments[END_REF], its semantics can be analyzed in biology or econometrics for instance. Practically, the reward can be seen as a succinct description of a task. Discovering it removes the coupling that exists in AL between understanding the task and learning how to fulfill it. IRL allows the use of (A)DP or RL techniques to learn how to do the task from the computed reward function. A very straightforward non-IRL way to do AL is for example to use a multi-class classifier to directly learn the expert policy. We provide in the experiments (Sec. 6) a comparison between AL and IRL algorithms by using IRL as a way to do AL.

A lot of existing approaches in either IRL or IRL-based AL need to repeatedly solve the underlying MDP to find the optimal policies of intermediate reward functions. Thus, their performance depends strongly on the quality of the associated subroutine. Consequently, they suffer from the same challenges of scalability, data scarcity, etc., as RL and (A)DP. In order to avoid repeatedly solving such problems, we adopt a different point of view.

Having in mind that there is a one to one relation between a reward function and its associated optimal action-value function (via the Bellman equation, see Eq. ( 1)), it is worth thinking of a method able to output an action-value function for which the greedy policy is the demonstrated expert policy. Thus, the demonstrated expert policy will be optimal for the corresponding reward function. We propose to use a score function-based multi-class classification step (see Sec. 3) to infer a score function. Besides, in order to retrieve via the Bellman equation the reward associated with the score function computed by the classification step, we introduce a regression step (see Sec. 3). That is why the method is called the Cascaded Supervised Inverse reinforcement learning (CSI). This method is analyzed in Sec. [START_REF] Guermeur | A generic model of multi-class support vector machine[END_REF], where it is shown that the demonstrated expert policy is near-optimal for the reward the regression step outputs.

This algorithm does not need to iteratively solve an MDP and requires only sampled transitions from expert and non-expert policies as inputs. Moreover, up to the use of some heuristics (see Sec. 6.1), the algorithm is able to be trained only with transitions sampled from the demonstrated expert policy. A specific instantiation of CSI (proposed in Sec. 6.1) is tested on the mountain car problem (Sec. 6.2) and on a highway driving simulator (Sec. [START_REF] Melo | Learning from demonstration using mdp induced metrics[END_REF].3) where we compare it with a pure classification algorithm [START_REF] Taskar | Learning structured prediction models: A large margin approach[END_REF] and with two recent successful IRL methods [START_REF] Klein | Inverse Reinforcement Learning through Structured Classification[END_REF] as well as with a random baseline. Differences and similarities with existing AL or IRL approaches are succinctly discussed in Sec. 5.

Background and Notation

First, we introduce some general notation. Let E and F be two non-empty sets, E F is the set of functions from F to E. We note ∆ X the set of distributions over X. Let α ∈ R X and β ∈ R X : α ≥ β ⇔ ∀x ∈ X, α(x) ≥ β(x). We will often slightly abuse the notation and consider (where applicable) most objects as if they were matrices and vectors indexed by the set they operate upon.

We work with finite MDPs [START_REF] Puterman | Markov decision processes: Discrete stochastic dynamic programming[END_REF], that is tuples {S, A, P, R, γ}. The state space is noted S, A is a finite action space, R ∈ R S×A is a reward-function, γ ∈ (0, 1) is a discount factor and P ∈ ∆ S×A S is the Markovian dynamics of the MDP. Thus, for each (s, a) ∈ S × A, P (.|s, a) is a distribution over S and P (s |s, a) is the probability to reach s by choosing action a in state s. At each time step t, the agent uses the information encoded in the state s t ∈ S in order to choose an action a t ∈ A according to a (deterministic4 ) policy π ∈ A S . The agent then steps to a new state s t+1 ∈ S according to the Markovian transition probabilities P (s t+1 |s t , a t ). Given that P π = (P (s |s, π(s))) s,s ∈S is the transition probability matrix, the stationary distribution over the states ρ π induced by a policy π satisfies ρ T π P π = ρ T π , with X T being the transpose of X. The stationary distribution relative to the expert policy π E is ρ E .

The reward function R is a local measure of the quality of the control. The global quality of the control induced by a policy π, with respect to a reward R, is assessed by the value function V π R ∈ R S which associates to each state the expected discounted cumulative reward for following policy π from this state:

V π R (s) = E[ t≥0 γ t R(s t , π(s t ))|s 0 = s, π]. This long-term criterion
is what is being optimized when solving an MDP. Therefore, an optimal policy π * R is a policy whose value function (the optimal value function V * R ) is greater than that of any other policy, for all states: ∀π,

V * R ≥ V π R . The Bellman evaluation operator T π R : R S → R S is defined by T π R V = R π + γP π V where R π = (R(s, π(s))) s∈S .
The Bellman optimality operator follows naturally:

T * R V = max π T π R V .
Both operators are contractions. The fixed point of the Bellman evaluation operator T π R is the value function of π with respect to reward R:

V π R = T π R V π R ⇔ V π R = R π + γP π V π R .
The Bellman optimality operator T * R also admits a fixed point, the optimal value function V * R with respect to reward R.

Another object of interest is the action-value function Q π R ∈ R S×A that adds a degree of freedom on the choice of the first action, formally defined by

Q π R (s, a) = T a R V π R (s)
, with a the policy that always returns action a (T a R V = R a +γP a V with P a = (P (s |s, a)) s,s ∈S and R a = (R(s, a)) s∈S ). The value function V π R and the action-value function Q π R are quite directly related: ∀s ∈ S, V π R (s) = Q π R (s, π(s)). The Bellman evaluation equation for Q π R is therefore:

Q π R (s, a) = R(s, a) + γ s ∈S P (s |s, a)Q(s , π(s )). (1)
An optimal policy follows a greedy mechanism with respect to its optimal action-value function Q * R :

π * R (s) ∈ argmax a Q * R (s, a). (2)
When the state space is too large to allow matrix representations or when the transition probabilities or even the reward function are unknown except through observations gained by interacting with the system, RL or ADP may be used to approximate the optimal control policy [START_REF] Sutton | Reinforcement learning[END_REF].

We recall that solving the MDP is the direct problem. This contribution aims at solving the inverse one. We observe trajectories drawn from an expert's deterministic 4 policy π E , assuming that there exists some unknown reward R E for which the expert is optimal. The suboptimality of the expert is an interesting setting that has been discussed for example in [START_REF] Melo | Analysis of inverse reinforcement learning with perturbed demonstrations[END_REF][START_REF] Syed | A reduction from apprenticeship learning to classification[END_REF], but that we are not addressing here. We do not try to find this unknown reward R E but rather a non trivial reward R for which the expert is at least near-optimal. The trivial reward 0 is a solution to this ill-posed problem (no reward means that every behavior is optimal). Because of its ill-posed nature, this expression of Inverse Reinforcement Learning (IRL) still has to find a satisfactory solution although a lot of progress has been made, see Sec. 5.

The Cascading Algorithm

Our first step towards a reward function solving the IRL problem is a classification step using a score function-based multi-class classifier (SFMC 2 for short). This classifier learns a score function q ∈ R S×A that rates the association of a given action5 a ∈ A with a certain input s ∈ S. The classification rule π C ∈ A S simply selects (one of) the action(s) that achieves the highest score for the given inputs:

π C (s) ∈ argmax a q(s, a). (3)
For example, Multi-class Support Vector Machines [START_REF] Guermeur | A generic model of multi-class support vector machine[END_REF] can be seen as SFMC 2 algorithms, the same can be said of the structured margin approach [START_REF] Taskar | Learning structured prediction models: A large margin approach[END_REF] both of which we consider in the experimental setting. Other algorithms may be envisioned (see Sec. 6.1). Given a dataset D C = {(s i , a i = π E (s i )) i } of actions a i (deterministically) chosen by the expert on states s i , we train such a classifier. The classification policy π C is not the end product we are looking for (that would be mere supervised imitation of the expert, not IRL). What is of particular interest to us is the score function q itself. One can easily notice the similarity between Eq. (3) and Eq. ( 2) that describes the relation between the optimal policy in an MDP and its optimal action-value function. The score function q of the classifier can thus be viewed as some kind of optimal action-value function for the classifier policy π C . By inversing the Bellman equation [START_REF] Abbeel | Apprenticeship learning via inverse reinforcement learning[END_REF] with q in lieu of Q π R , one gets R C , the reward function relative to our score/action-value function q: R C (s, a) = q(s, a)γ s P (s |s, a)q(s , π C (s )).

(

) 4
As we wish to approximately solve the general IRL problem where the transition probabilities P are unknown, our reward function R C will be approximated with the help of information gathered by interacting with the system. We assume that another dataset D R = {(s j , a j , s j ) j } is available where s j is the state an agent taking action a j in state s j transitioned to. Action a j need not be chosen by any particular policy. The dataset D R brings us information about the dynamics of the system. From it, we construct datapoints {r j = q(s j , a j )γq(s j , π C (s j ))} j .

(

) 5
As s j is sampled according to P (•|s j , a j ) the constructed datapoints help building a good approximation of R C (s j , a j ). A regressor (a simple least-square approximator can do but other solutions could also be envisioned, see Sec. 6.1) is then fed the datapoints ((s j , a i ), rj ) to obtain RC , a generalization of {((s j , a j ), rj ) j } over the whole state-action space. The complete algorithm is given in Alg. 1.

There is no particular constraint on D C and D R . Clearly, there is a direct link between various qualities of those two sets (amount of data, statistical representativity, etc.) and the classification and regression errors. The exact nature of the relationship between these quantities depends on which classifier and regressor are chosen. The theoretical analysis of Sec. 4 abstracts itself from the choice of a regressor and a classifier and from the composition of D C and D R by reasoning with the classification and regression errors. In Sec. 6, the use of a single dataset to create both D C and D R is thoroughly explored.

Algorithm 1 CSI algorithm

Given a training set DC = {(si, ai = πE(si))} 1≤i≤D and another training set DR = {(sj, aj, s j )} 1≤j≤D Train a score function-based classifier on DC , obtaining decision rule πC and score function q : S × A → R Learn a reward function RC from the dataset {((sj, aj), rj)}1≤j≤D , ∀(sj, aj, s j ) ∈ DR, rj = q(sj, aj) -γq(s j , πC (s j )) Output the reward function RC Cascading two supervised approaches like we do is a way to inject the MDP structure into the resolution of the problem. Indeed, mere classification only takes into account information from the expert (i.e., which action goes with which state) whereas using the Bellman equation in the expression of rj makes use of the information lying in the transitions (s j , a j , s j ), namely information about the transition probabilities P . The final regression step is a way to generalize this information about P to the whole state-action space in order to have a well-behaved reward function. Being able to alleviate the ill effects of scalability or data scarcity by leveraging the wide range of techniques developed for the classification and regression problems is a strong advantage of the CSI approach.

Analysis

In this section, we prove that the deterministic expert policy π E is near optimal for the reward RC the regression step outputs. More formally, recalling from Sec. 2 that ρ E is the stationary distribution of the expert policy, we prove that

E s∼ρ E [V * RC (s) -V π E RC (s)
] is bounded by a term that depends on:

the classification error defined as

C = E s∼ρ E [1 {π C (s) =π E (s)} ];
the regression error defined as R = max π∈A S R π 1,ρ E , with: • the subscript notation already used for R π and P π in Sec. 2 meaning that, given an X ∈ R S×A , π ∈ A S , and a ∈ A, X π ∈ R S and X a ∈ R S are respectively such that: ∀s ∈ S, X π (s) = X(s, π(s)) and ∀s ∈ S, X a (s) = X(s, a) ;

• R π = R C π -RC π ; • . 1,µ the µ-weighted L 1 norm: f 1,µ = E x∼µ [|f (x)|]; -the concentration coefficient C * = C πC with: • C π = (1 -γ) t≥0 γ t c π (t), with c π (t) = max s∈S (ρ T E P t π )(s) ρ E (s) ;
• πC , the optimal policy for the reward RC output by the algorithm ; The constant C * can be estimated a posteriori (after RC is computed). A priori, C * can be upper-bounded by a more usual and general concentration coefficient but C * gives a tighter final result: one can informally see C * as a measure of the similarity between the distributions induced by πC and π E (roughly, if πC ≈ π E then C * ≈ 1).

-∆q = max s∈S (max a∈A q(s, a)min a∈A q(s, a)) = max s∈S (q(s, π C (s))min a∈A q(s, a)), which could be normalized to 1 without loss of generality. The range of variation of q is tied to the one of R C , RC and V π C RC . What matters with these objects is the relative values for different state action couples, not the objective range. They can be shifted and positively scaled without consequence.

Theorem 1. Let π E be the deterministic expert policy, ρ E its stationary distribution and RC the reward the cascading algorithm outputs. We have:

0 ≤ E s∼ρ E [V * RC (s) -V π E RC (s)] ≤ 1 1 -γ ( C ∆q + R (1 + C * )) .
Proof. First let's recall some notation, q ∈ R S×A is the score function output by the classification step, π C is a deterministic classifier policy so that ∀s ∈ S, π C (s) ∈ argmax a∈A q(s, a), R C ∈ R S×A is so that ∀(s, a) ∈ S × A, R C (s, a) = q(s, a)γ s ∈S P (s |s, a)q(s , π C (s )), and RC ∈ R S×A is the reward function output by the regression step. The difference between R C and RC is noted R = R C -RC ∈ R S×A . We also introduce the reward function R E ∈ R S×A which will be useful in our proof, not to be confused with R E the unknown reward function the expert optimizes:

∀(s, a) ∈ S × A, R E (s, a) = q(s, a) -γ s ∈S P (s |s, a)q(s , π E (s )).
We now have the following vectorial equalities

R C a = q a -γP a q π C ; R E a = q a -γP a q π E ; R a = R C a -RC a .
Now, we are going to upper bound the term:

E s∼ρ E [V * RC -V π E RC ]
≥ 0 (the lower bound is obvious as V * is optimal). Recall that πC is a deterministic optimal policy of the reward RC . First, the term

V * RC -V π E RC is decomposed: V * RC -V π E RC = (V πC RC -V πC R C ) + (V πC R C -V π E R C ) + (V π E R C -V π E RC ).
We are going to bound each of these three terms. First, let π be a given deterministic policy. We have, using

R = R C -RC : V π R C -V π RC = V π R = (I -γP π ) -1 R π . If π = π E ,
we have, thanks to the power series expression of (I -γP π E ) -1 , the definition of ρ E and the definition of the µ-weighted L 1 norm, one property of which is that ∀X, µ T X ≤ X 1,µ :

ρ T E (V π R C -V π RC ) = ρ T E (I -γP π E ) -1 R π E = 1 1 -γ ρ T E R π E ≤ 1 1 -γ R π E 1,ρ E .
If π = π E , we use the concentration coefficient C π . We have then:

ρ T E (V π R C -V π RC ) ≤ C π 1 -γ ρ T E R π ≤ C π 1 -γ R π 1,ρ E .
So, using the notation introduced before we stated the theorem, we are able to give an upper bound to the first and third terms (recall also the notation

C πC = C * ): ρ T E ((V π E R C -V π E RC ) + (V πC RC -V πC R C )) ≤ 1+C * 1-γ R
. Now, there is still an upper bound to find for the second term. It is possible to decompose it as follows:

V πC R C -V π E R C = (V πC R C -V π C R C ) + (V π C R C -V π E R E ) + (V π E R E -V π E R C ). By construction, π C is optimal for R C , so V πC R C -V π C R C ≤ 0 which implies: V πC R C -V π E R C ≤ (V π C R C -V π E R E ) + (V π E R E -V π E R C ).
By construction, we have

V π C R C = q π C and V π E R E = q π E , thus: ρ T E (V π C R C -V π E R E ) = ρ T E (q π C -q π E ) = s∈S ρ E (s)(q(s, π C (s)) -q(s, π E (s)))[1 {π C (s) =π E (s)} ].
Using ∆q, we have:

ρ T E (V π C R C -V π E R E ) ≤ ∆q s∈S ρ E (s)[1 {π C (s) =π E (s)} ] = ∆q C .
Finally, we also have:

ρ T E (V π E R E -V π E R C ) = ρ T E (I -γP π E ) -1 (R E π E -R C π E ) = ρ T E (I -γP π E ) -1 γP π E (q π C -q π E ), = γ 1 -γ ρ T E (q π C -q π E ) ≤ γ 1 -γ ∆q C .
So the upper bound for the second term is:

ρ T E (V πC R C -V π E R C ) ≤ (∆q + γ 1-γ ∆q) C = ∆q 1-γ C .
If we combine all of the results, we obtain the final bound as stated in the theorem.

Readers familiar with the work presented in [START_REF] Klein | Inverse Reinforcement Learning through Structured Classification[END_REF] will see some similarities between the theoretical analyses of SCIRL and CSI as both study error propagation in IRL algorithms. Another shared feature is the use of the score function q of the classifier as a proxy for the action-value function of the expert Q π E R E . The attentive reader, however, will perceive that similarities stop there. The error terms occurring in the two bounds are not related to one another. As CSI makes no use of the feature expectation of the expert, what is known as ¯ Q in [START_REF] Klein | Inverse Reinforcement Learning through Structured Classification[END_REF] does not appear in this analysis. Likewise, the regression error R of this paper does not appear in the analysis of SCIRL, which does not use a regressor. Perhaps more subtly, the classification error and classification policy known in both papers as C and π C are not the same. The classification policy of SCIRL is not tantamount to what is called π C here. For SCIRL, π C is the greedy policy for an approximation of the value function of the expert with respect to the reward output by the algorithm. For CSI, π C is the decision rule of the classifier, an object that is not aware of the structure of the MDP. We shall also mention that the error terms appearing in the CSI bound are more standard than the ones of SCIRL (e.g., regression error vs feature expectation estimation error) thus they may be easier to control. A direct corollary of this theorem is that, given perfect classifier and regressor, CSI produces a reward function for which π E is the unique optimal policy. Corollary 1. Assume that ρ E > 0 and that the classifier and the regressor are perfect ( C = 0 and R = 0). Then π E is the unique optimal policy for RC .

Proof. The function q is the optimal action-value function for π C with respect to the reward R C , by definition (see Eq. ( 4)). As C = 0, we have π C = π E . This means that ∀s, π E (s) is the only element of the set argmax a∈A q(s, a). Therefore, π C = π E is the unique optimal policy for R C . As R = 0, we have RC = R C , hence the result.

This corollary hints at the fact that we found a non-trivial reward (we recall that the null reward admits every policy as optimal). Therefore, obtaining RC = 0 (for which the bound is obviously true: the bounded term is 0, the bounding term is positive) is unlikely as long as the classifier and the regressor exhibit decent performance.

The only constraints the bound of Th. 1 implies on datasets D R and D C is that they provide enough information to the supervised algorithms to keep both error terms C and R low. In Sec. 6 we deal with a lack of data in dataset D R . We address the problem with the use of heuristics (Sec. 6.1) in order to show the behavior of the CSI algorithm in somewhat more realistic (but difficult) conditions.

More generally, the error terms C and R can be reduced by a wise choice for the classification and regression algorithms. The literature is wide enough for methods accommodating most of use cases (lack of data, fast computation, bias/variance trade-off, etc.) to be found. Being able to leverage such common algorithms as multi-class classifiers and regressors is a big advantage of our cascading approach over existing IRL algorithms.

Other differences between existing IRL or apprenticeship learning approaches and the proposed cascading algorithm are further examined in Sec. 5.

IRL was first introduced in [START_REF] Russell | Learning agents for uncertain environments[END_REF] and then formalized in [START_REF] Ng | Algorithms for inverse reinforcement learning[END_REF]. Approaches summarized in [START_REF] Neu | Training parsers by inverse reinforcement learning[END_REF] can be seen as iteratively constructing a reward function, solving an MDP at each iteration. Some of these algorithms are IRL algorithms while others fall in the Apprenticeship Learning (AL) category, as for example the projection version of the algorithm in [START_REF] Abbeel | Apprenticeship learning via inverse reinforcement learning[END_REF]. In both cases the need to solve an MDP at each step may be very demanding, both sample-wise and computationally. CSI being able to output a reward function without having to solve the MDP is thus a significant improvement.

AL via classification has been proposed for example in [START_REF] Ratliff | Imitation learning for locomotion and manipulation[END_REF], with the help of a structured margin method. Using the non-trivial notion of metric in an MDP, the authors of [START_REF] Melo | Learning from demonstration using mdp induced metrics[END_REF] build a kernel which is used in a classification algorithm, showing improvements compared to a non-structured kernel.

Classification and IRL have met in the past in [START_REF] Ratliff | Maximum margin planning[END_REF], but the labels were complete optimal policies rather than actions and the inputs were MDPs, which had to be solved. It may be unclear how SCIRL [START_REF] Klein | Inverse Reinforcement Learning through Structured Classification[END_REF] relates to the proposed approach of his paper. Both algorithms use the score function of a classifier as a proxy to the action-value function of the expert with respect to the (unknown) true reward:

Q π E R .
The way this proxy is constructed and used, however, fundamentally differs in the two algorithms. This difference will cause the theoretical analysis of both approaches (see Sec. 4) to be distinct. In SCIRL, the score function of the classifier is approximated via a linear parametrization that relies on the feature expectation of the expert µ E (s) = E[ t≥0 γ t φ(s t )|s 0 = s, π E ]. This entails the use of a specific kind of classifier (namely linearly-parametrized-score-functionbased classifiers) and of a method of approximation of µ E . By contrast, almost any off-the-shelf classifier can be used in the first step of the cascading approach of this paper. The classification step of CSI is unaware of the structure of the MDP whereas SCIRL knows about it thanks to the use of µ E . In CSI, the structure of the MDP is injected by reversing the Bellman equation prior to the regression step (Eq. 4 and ( 5)), a step that does not exist in SCIRL as SCIRL directly outputs the parameter vector found by its linearly-parametrized-scorefunction-based classifier. The regressor of CSI can be chosen off-the-shelf. One can argue that this and not having to approximate µ E increases the ease-of-use of CSI over SCIRL and makes for a more versatile algorithm. In practice, as seen in Sec. 6, performance of SCIRL and CSI are very close to one another thus CSI may be a better choice as it is easier to deploy. Neither approach is a generalization of the other.

Few IRL or AL algorithms do not require solving an MDP. The approach of [START_REF] Syed | Apprenticeship learning using linear programming[END_REF] requires knowing the transition probabilities of the MDP (which CSI does not need) and outputs a policy (and not a reward). The algorithm in [START_REF] Dvijotham | Inverse optimal control with linearly-solvable MDPs[END_REF] only applies to linearly-solvable MDPs whereas our approach does not place such restrictions. Closer to our use-case is the idea presented in [START_REF] Boularias | Relative entropy inverse reinforcement learning[END_REF] to use a subgradient ascent of a utility function based on the notion of relative entropy. Importance sampling is suggested as a way to avoid solving the MDP. This requires sampling trajectories according to a non-expert policy and the direct problem remains at the core of the approach (even if solving it is avoided).

Experiments

In this section, we empirically demonstrate the behavior of our approach. We begin by providing information pertaining to both benchmarks. An explanation about the amount and source of the available data, the rationale behind the heuristics we use to compensate for the dire data scarcity and a quick word about the contenders CSI is compared to are given Sec. 6.1. We supply quantitative results and comparisons of CSI with state-of-the art approaches on first a classical RL benchmark (the mountain car) in Sec. 6.2 and then on a highway driving simulator (Sec. 6.3).

Generalities

Data Scarcity The CSI algorithm was designed to avoid repeatedly solving the RL problem. This feature makes it particularly well-suited to environments where sampling the MDP is difficult or costly. In the experiments, CSI is fed only with data sampled according to the expert policy. This corresponds for example to a situation where a costly system can only be controlled by a trained operator as a bad control sequence could lead to a system breakdown.

More precisely, the expert controls the system for M runs of lengths

{L i } 1≤i≤M , giving samples {(s k , a k = π E (a k ), s k ) k } = D E . The dataset D C
fed to the classifier is straightforwardly constructed from D E by dropping the s k terms:

D C = {(s i = s k , a i = a k ) i }.
Heuristics It is not reasonable to construct the dataset D R = {((s k , a k = π E (s k )), rk ) k } only from expert transitions and expect a small regression error term R . Indeed, the dataset D E only samples the dynamics induced by the expert's policy and not the whole dynamics of the MDP. This means that for a certain state s k we only know the corresponding expert action a k = π E (s k ) and the following state s k sampled according to the MDP dynamics :

s k ∼ P (•|s k , a k ).
For the regression to be meaningful, we need samples associating the same state s k and a different action a = a k with a datapoint r = rk . Recall that rj = q(s j , a j )γq(s j , π C (s j )) (Eq. ( 5)); without knowing s k ∼ P (•|s k , a = a k ), we cannot provide the regressor with a datapoint to associate with (s k , a = a k ). We artificially augment the dataset D R with samples ((s j = s k , a), r min ) j;∀a =π E (sj )=a k where r min = min k rk -1. This heuristics instructs the regressor to associate a state-action tuple disagreeing with the expert (i.e., (s k , a = a k )) with a reward strictly inferior to any of those associated with expert state action tuples (i.e., (s k , a k = π E (s k ))). Semantically, we are asserting that disagreeing with the expert in states the expert visited is a bad idea. This heuristics says nothing about states absent from the expert dataset. For such states the generalization capabilities of the regressor and, later on, the exploration of the MDP by an agent optimizing the reward will solve the problem. Although this heuristics was not analyzed in Sec. 4 (where the availability of a more complete dataset D R was assumed), the results shown in the next two subsections demonstrate its soundness.

Comparison with State-of-the-Art Approaches The similar looking yet fundamentally different algorithm SCIRL [START_REF] Klein | Inverse Reinforcement Learning through Structured Classification[END_REF] is an obvious choice as a contender to CSI as it advertises the same ability to work with very little data, without repeatedly solving the RL problem. In both experiments we give the exact same data to CSI and SCIRL.

The algorithm of [START_REF] Dvijotham | Inverse optimal control with linearly-solvable MDPs[END_REF] also advertises not having to solve the RL problem, but needs to deal with linearly solvable MDPs, therefore we do not include it in our tests. The Relative Entropy (RE) method of [START_REF] Boularias | Relative entropy inverse reinforcement learning[END_REF] has no such need, so we included it in our benchmarks. It could not, however, work with the small amount of data we provided SCIRL and CSI with, and so to allow for importance sampling, we created another dataset D random that was used by RE but not by SCIRL nor CSI.

Finally, the classification policy π C output by the classification step of CSI was evaluated as well. Comparing classification and IRL algorithms makes no sense if the object of interest is the reward itself as can be envisioned in a biological or economical context. It is however sound to do so in an imitation context where what matters is the performance of the agent with respect to some objective criterion. Both experiments use such a criterion. Classification algorithms don't have to optimize any reward since the classification policy can directly be used in the environment. IRL algorithms on the other hand output a reward that must then be plugged in an RL or DP algorithm to get a policy. In each benchmark we used the same (benchmark-dependent) algorithm to get a policy from each of the three rewards output by SCIRL, CSI and RE. It is these policies whose performance we show. Finding a policy from a reward is of course a non-trivial problem that should not be swept under the rug; nevertheless we choose not to concern ourselves with it here as we wish to focus on IRL algorithms, not RL or DP algorithms. In this regard, using a classifier that directly outputs a policy may seem a much simpler solution, but we hope that the reader will be convinced that the gap in performance between classification and IRL is worth the trouble of solving the RL problem (once and for all, and not repeatedly as a subroutine like some other IRL algorithms).

We do not compare CSI to other IRL algorithms requiring repeatedly solving the MDP. As we would need to provide them with enough data to do so, the comparison makes little sense.

Supervised Steps

The cascading algorithm can be instantiated with some standard classification algorithms and any regression algorithm. The choice of such subroutines may be dictated by the kind and amount of available data, by ease of use or by computational complexity, for example.

We referred in Sec.3 to score-function based multi-class classifiers and explained how the classification rule is similar to the greedy mechanism that exists between an optimal action-value function and an optimal policy in an MDP. Most classifications algorithms can be seen as such a classifier. In a simple knearest neighbor approach, for example, the score function q(s, a) is the number of elements of class a among the k-nearest neighbors of s. The generic M-SVM model makes the score function explicit (see [START_REF] Guermeur | A generic model of multi-class support vector machine[END_REF]) (we use a SVM in the mountain car experiment Sec. 6.2). In the highway experiment, we choose to use a structured margin classification approach [START_REF] Taskar | Learning structured prediction models: A large margin approach[END_REF]. We chose a SVR as a regressor in the mountain car experiment and a simple least-square regressor on the highway.

It is possible to get imaginative in the last step. For example, using a Gaussian process regressor [START_REF] Rasmussen | Gaussian processes for machine learning[END_REF] that outputs both expectation and variance can enable (notwithstanding a nontrivial amount of work) the use of reward-uncertain reinforcement learning [START_REF] Regan | Robust online optimization of reward-uncertain MDPs[END_REF]. Our complete instantiation of CSI is summed up in Alg. 2.

Algorithm 2 A CSI instantiation with heuristics

Given a dataset DE = (s k , a k = πE(a k ), s k ) k Construct the dataset DC = {(si = s k , ai = π E (si)) = a k }

Mountain Car

The mountain car is a classical toy problem in RL: an underpowered car is tasked with climbing a steep hill. In order to do so, it has to first move away from the target and climb the slope on its left, and then it moves right, gaining enough momentum to climb the hill on the right on top of which lies the target. We used standard parameters for this problem, as can for example be found in [START_REF] Sutton | Reinforcement learning[END_REF].

When training an RL agent, the reward is, for example, 1 if the car's position is greater than 0.5 and 0 anywhere else. The expert policy was a very simple hand crafted policy that uses the power of the car to go in the direction it already moves (i.e., go left when the speed is negative, right when it is positive).

The initial position of the car was uniformly randomly picked in [-1.2; -0.9] and its speed uniformly randomly picked in [-0.07; 0]. From this position, the hand-crafted policy was left to play until the car reached the objective (i.e., a position greater than 0.5) at which point the episode ended. Enough episodes were played (and the last one was truncated) so that the dataset D E contained exactly n samples, with n successively equal to 10, 30, 100 and 300. With these parameters, the expert is always able to reach the top on the first time it tries to climb the hill on the right. Therefore, a whole part of the state space (when the position is on the hill on the right and the speed is negative) is not visited by the expert. This hole about the state space in the data will be dealt with differently by the classifier and the IRL algorithms. The classifier will use its generalization power to find a default action in this part of the state space, while the IRL algorithms will devise a default reward; a (potentially untrained) RL agent finding itself in this part of the state space will use the reward signal to decide what to do, making use of new data available at that time.

In order to get a policy from the rewards given by SCIRL, CSI and RE, the RL problem was solved by LSPI fed with a dataset D random of 1000 episodes of length 5 with a starting point uniformly and randomly chosen in the whole state space and actions picked at random. This dataset was also used by RE (and not by SCIRL nor CSI).

The classifier for CSI was an off-the-shelf SVM6 which also was the classifier we evaluate, the regressor of CSI was an off-the-shelf SVR 7 . RE and SCIRL need features over the state space, we used the same evenly-spaced hand-tuned 7 × 7 RBF network for both algorithms.

The objective criterion for success is the number of steps needed to attain the goal when starting from a state picked at random ; the lesser the better. We can see Fig. 1 that the optimal policies for the rewards found by SCIRL and CSI very rapidly attain expert-level performance and outperform the optimal policy for the reward of RE and the classification policy. When very few samples are available, CSI does better than SCIRL (with such a low p-value for n = 10, see Tab. 1a, the hypothesis that the mean performance is equal can be rejected); SCIRL catches up when more samples are available. Furthermore, CSI required very little engineering as we cascaded two off-the-shelf implementations whereas SCIRL used hand-tuned features and a custom classifier.

Highway Driving Simulator

The setting of the experiment is a driving simulator inspired from a benchmark already used in [START_REF] Syed | Apprenticeship learning using linear programming[END_REF][START_REF] Syed | A game-theoretic approach to apprenticeship learning[END_REF]. The agent controls a car that can switch between the three lanes of the road, go off-road on either side and modulate between three speed levels. At all timesteps, there will be one car in one of the three lanes. Even at the lowest speed, the player's car moves faster than the others. When the other car disappears at the bottom of the screen, another one appears at the top in a randomly chosen lane. It takes two transitions to completely change lanes, as the player can move left or right for half a lane's length at a time. At the highest speed setting, if the other car appears in the lane the player is in, it is not possible to avoid the collision. The main difference between the original benchmark [START_REF] Syed | Apprenticeship learning using linear programming[END_REF][START_REF] Syed | A game-theoretic approach to apprenticeship learning[END_REF] and ours is that we made the problem more ergodic by allowing the player to change speed whenever he wishes so, not just during the first transition. If anything, by adding two actions, we enlarged the stateaction space and thus made the problem tougher. The reward function R E the expert is trained by a DP algorithm on makes it go as fast as possible (high reward) while avoiding collisions (harshly penalized) and avoiding going off-road (moderately penalised). Any other situation receives a null reward.

The performance criterion for a policy π is the mean (over the uniform distribution) value function with respect to R E : E s∼U [V π R E (s)]. Expert performance averages to 7.74 ; we also show the natural random baseline that consists in drawing a random reward vector (with a uniform law) and training an agent on it. The reward functions found by SCIRL, CSI and RE are then optimized using a DP algorithm. The dataset D random needed by RE (and neither by CSI nor SCIRL) is made of 100 episodes of length 10 starting randomly in the state space and following a random policy. the dataset D E is made of n episodes of length n, with n ∈ {3, 7, 10, 15, 20}.

Results are shown Fig. 2. We give the values of E s∼U [V π R E (s)] with π being in turn the optimal policy for the rewards given by SCIRL, CSI and RE, the policy π C of the classifier (the very one the classification step of CSI outputs), and the optimal policy for a randomly drawn reward. Performance for CSI is slightly but definitively higher than for SCIRL (see the p-values for the mean equality test in Tab. 1b, from 49 samples on), slightly below the performance of the expert itself. Very few samples (100) are needed to reliably achieve expert-level performance.

It is very interesting to compare our algorithm to the behavior of a classifier alone (respectively red and green plots on Fig. 2a). With the exact same data, albeit the use of a very simple heuristics, the cascading approach demonstrates far better performance from the start. This is a clear illustration of the fact that using the Bellman equation to construct the data fed to the regressor and outputting not a policy, but a reward function that can be optimized on the MDP truly makes use of the information that the transitions (s, a, s ) bear (we recall that the classifier only uses (s, a) couples). Furthermore, the classifier whose results are displayed here is the output of the first step of the algorithm. The classification performance is obviously not that good, which points to the fact that our algorithm may be empirically more forgiving of classification errors than our theoretical bound lets us expect.

Conclusion

We have introduced a new way to perform IRL by cascading two supervised approaches. The expert is theoretically shown to be near-optimal for the reward function the proposed algorithm outputs, given small classification and regression errors. Practical examples of classifiers and regressors have been given, and two combinations have been empirically (on two classic benchmarks) shown to be very resilient to dire lack of data on the input (only data from the expert was used to retrieve the reward function), with the help of simple heuristics. On both benchmarks, our algorithm is shown to outperform other state-of-the-art approaches although SCIRL catches up on the mountain car. We plan on deepening the analysis of the theoretical properties of our approach and on applying it to real world robotics problems.

  Train a score function-based classifier on DC , obtaining decision rule πC and score function q : S × A → R Construct the dataset {((sj = s k , aj = a k ), rj)j} with rj = q(sj, aj) -γq(s j = s k , πC (s j = s k )) Set rmin = minj rj -1. Construct the training set DR = {((sj = s k , aj = a k ), rj)j} ∪ {((sj = s k , a), rmin) j;∀a =π E (s j )=a k } Learn a reward function RC from the training set DR Output the reward function RC : (s, a) → ω T φ(s, a)

Fig. 1 :

 1 Fig.1: Performance of various policies on the mountain car problem. This is the mean over 100 runs.

  Mean performance over 100 runs on the Highway driving problem.

  Zoom of Fig 2a showing the ranking of the three IRL algorithms.

Fig. 2 :

 2 Fig. 2: Results on the highway driving problem.

Table 1 :

 1 Student or Welch test of mean equality (depending on whether a Bartlett test of variance equality succeeds) p-values for CSI and SCIRL on the mountain car (1a) and the highway driving simulator (1b). High values (> 1.0 × 10 -02 ) means that the hypothesis that the means are equal cannot be rejected.

	(a) Mountain Car				(b) Highway Driving
	Number of expert samples p-value		Number of expert samples p-value
	10		1.5e -12			9	3.0e -01
	30			3.8e -01			49	8.9e -03
	100			1.3e -02			100	1.8e -03
	300			7.4e -01			225	2.4e -05
							400	2.0e -50
		250
						CSI
						SCIRL
						Relative Entropy
	Average length of episode	100 150 200				Classification Expert
		50
		0	50	100	150	200	250	300
				Number of samples from the expert

We restrict ourselves here to deterministic policies, but the loss of generality is minimal as there exists at least one optimal deterministic policy.

Here, actions play the role of what is known as labels or categories when talking about classifiers.

http://scikit-learn.org/stable/modules/generated/sklearn.svm.SVC.html

http://scikit-learn.org/stable/modules/generated/sklearn.svm.SVR.html

The research leading to these results has received funding from the European Union Seventh Framework Programme (FP7/2007-2013) under grant agreement n°270780.


M ithila Paintings introduced to world, redefined through outsiders' needs and Western paradigms. Devoted places to paintings and more than 130 exhibitions in 25 countries (cf. maps).

phases of reception with valued discourses of Zeitgeist:

 Late colonial and post-independence moment. Archer's universal aesthetics stemming from colonialism, vanguards, psychoanalyze, surrealism, organic art vision. Since at least 14 th c., women's domestic wall and floor (aripana) imagery: Hindu deities, icons of fertility (elaborately for weddings in bridal room, kohbar ghar). 14 th c.: rigid matrimonial relations in upper castes (Panji), purdah (veil...), painting as outlet for women assertion. Impact of Vidyapati's Maithili songs. 3 styles: geru (mostly red), bharni (vivid colors), kachni (mostly lines in black and red). - 1970 1975-1980-1985-1990-1995-2000-2005-



  1 st phase of globalization, 'global 60s', 1960-1989 (climax 70s). Romantic world re-enchantment vs 'technocratic soc.' Véquaud: 'hippie' bohemia, neo-tantrism, prophetic painters, village communitarian utopia, return to pre-industrial & holistic community. Mithila art misunderstood as homogenous, stable and rural.  2 nd phase of globalization, 'postmodernity', 1995-today, (climax 1 st half 2010s). Techn. & styles shared, wider motives. Transversal dynamics of 'Neo' or 'New' Mithila artists. Women painters considered mostly through gender studies. Between religious, political and cultural fields. Diplomacy crucial to paintings globalization (I. Gandhi; A. Malraux; M. Singh, Indian ambassador in Finland, 80s...) Interactions between stakeholders, vectors of cross-cultural transfers, led to construction of 'transnational' cultural field. Y. Véquaud, B.S. Mandal, Baua Devi, her husband J.Jha making Snakes, acrylics. Behind: King and Queen Story and a River Inside, fresco. Magiciens de la Terre, Paris, 1989. Photo: Fr.-X. Bouchart © N. Beauthéac International Reception of Mithila Painting Hélène Fleury, PhD Candidate, Université Paris-Saclay, assoc. to CEIAS EHESS/CNRS . Bihar (IND) & Terai (NEP). Birth place of Sita & Janaki (Râmâyana). Mithila painting: umbrella term for ritual & art forms.

1934:

  Nepal-Bihar earthquake, W. Archer, local officer, 'discovered' paintings on walls. 47 photogr. (Brit. Library). Close to nationalist Bengali scholars, search for popular paintings. 1949: his article Maithil Painting underpinned by univer- sal aesthetics based on dominant movements in Post-War Anglophone World. Ritual & formal aspects set in unchanging tradition (styles per castes; feminine, anonymous & collective practice). Mithila art on global village, transnational spaces (airports, galleries...). 'New Mithila' artists, art graduated, mix aesthetics, symbolic elem. of global & local cultures. Awareness of national & global position of a firstly local practice. Transnational flows renew syncretic painting. 2000 60s: transferred on paper, paintings undergo changes: recognition of artistic individuality, new styles (tantric & godana/tattoos)... 1956: 1 st commercialization (B. Kulkarni). 1966: Indian govt (P. Jayakar, I. Gandhi) provides patronage by giving women paper & colors: relief program further to drought & famine of Bihar. Marketing policies (govt, develop. agencies) to attract national and worldwide audience: exhibitions, paintings on Jayanti-Janata Express, Madhubani station (L.N. Mishra), National Awards for Craftsmen... visions of S. Asian universe as spiritual, pantheist & sensorial. 'Flower power' quest: 'on the road' rather than 'on the job', freelove, spontaneous creation, anti-bourgeois. Kairos of 60s indophily. Internat. mediators: E. Moser-Schmitt (D), J. Elder, R. & N. Owens (USA), T. Hasegawa (J), Y. Véquaud (F). Véquaud's writings: timeless village utopia, Sehnsucht of lost Eden. Late 90s: deconstruction of male Westerner interpretations through gender & cultural studies, like paintings as immemorial expression of Hindu women rituals... Appearance of men painters (10 %): gender categories redefined? But patriarchy not called into question. 'Indianness', nation & art 2003: Mithila Art Institute 1980: Ethnic Art Foundation, USA. Bright fanning, Sabhapati Das household, Kayasth, vill. Darema, Photogr. W. Archer, 1940, Brit. Library Aspects of Franco-Indian cultural network around Mithila Paintings in 70s Kohbar-ghar (lotus, bamboo grove) Godawari Dutt, April 2017, Ranti.

  Shiva and Parvati mural, Godawarri Dutt, Ranti, 2002. Lakhola Jha, Krishna and Gopis, c. 1970, s.l., Bharni style. Holi Pigm. Priv. Collect. N. N. S. Nirala. Photogr. 2017.


Christelle Hatik

Optimization of Waste Management Scenarios by Principal Component Analysis: A Case Study in Reunion Island

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Waste management is often defined at a territorial level. The overall waste production is determined and a waste management scenario is built accordingly, covering the entire territory. Although this approach is interesting to size and deploy massive treatment plants, it lacks adaptation to sub-territorial specific waste flux characterization and treatment.

In fact, when waste management is studied at small-scale like municipalities, waste production can be analyzed in depth in order to capture specificities and optimize its management. Starting from this observation, our goal is to obtain a territorial waste management scenario out of small-scale waste management scenarios without multiplying the number of scenarios to build.

So, we propose a methodology to optimize waste management at small-scale by identifying correlation between small-scale areas' waste production, thus enabling mutualisation and co-creation of local scenarios.

Our approach is directly based on the quantitative and qualitative evaluation of wastes at the desired level of observation.

So, the first step is to choose waste categories (municipal solid wastes, organic wastes, recyclable wastes, e-wastes, etc.) and to determine the associated waste production for each studied area. At this step, we build a database with the classified wastes streams and their quantities. The database must be consolidated and reliable since all the analysis is based on it.

At the second step, we use Principal Component Analysis as our main analysis tool. With this method, we want to determine: i) if there is any correlation or similar behaviors in terms of composition and tonnages between two or more areas; ii) if there are indeed some similarities, which waste management scenarios can be established and for which towns.

So, this methodology can be used as follow: ➢ To compare behaviors into different administrative area (regions, municipalities, towns, etc.); ➢ To extract some similarities between studied areas; ➢ And to classify areas with the same profile.

With landfills having reached their maximal capacity and an ever-growing population, the waste management scenario on RI must be revised. An optimal global scenario is particularly difficult to build due to the specificities of waste composition and production of each municipality. These differences motivate the definition of waste management scenarios at the municipality scale, thus facing the creation of 24 local scenarios. PCA is used as the main analysis tool. It enables to highlight similarities between local administrative areas.

3.1) Wastes stream graphical repartition

Axes interpretation of PCA results: ➢ F1 is positively correlated with municipal wastes (green wastes, school wastes, used oil, FOOM, food wastes, fast food and restauration, etc.). ➢ F2 is positively correlated with farming sludges and industrial wastes (food industries).

3.2) Towns graphical repartition

Interpretation of PCA results: ➢ 5 groups of municipalities ➢ 5 different waste management scenarios ➢ Correlation between towns and characteristics of towns (urban, farming or industrial waste production)

F2 Wastes Streams

F1 Tons (+) (-)

Farming Towns Industrial Towns

With our PCA application, we demonstrate that it is possible to analyze a dataset of wastes production for many towns with greater ease than the usual analytical techniques like classic plots. Based on waste flux analysis, this approach is useful to better anticipate waste and urban development, thus improving forecasting decisionmaking. It enables to highlight similarities between local administrative areas. It also highlights the shared or discriminant waste characteristics, thus inducing collaboration strategy. This study will be particularly useful toward making towns of a same group working together to mutualize solutions. We think it is important to propose more specific waste management scenario adapted to the territory. Our methodology has been applied to Reunion Island (RI) and is focused on Biowastes streams. Reunion Island is a French oversea territory of approximately 2500 km², located in the Indian Ocean, between Mauritius and Madagascar. Its population reached 833 000 inhabitants in 2010. RI is structured with 24 municipalities which are regrouped into 5 public communities in charge of waste management.

Christelle

Axis F2 organizes towns according to the composition of their waste (farming character to industrial character). Thus, Le Tampon does not produce the same waste as Le Port. But we can say that Le Tampon and Le Port have the same quantity of wastes (the same position on axis F1). Moreover, the least productive town is La Plaine des Palmistes (PdP) and the most productive is Saint-Denis (location at the opposite on axis F1).

To interpret the waste streams graphic repartitions, we can see that food wastes and FOOM are positively correlated. This means that the more food wastes are produced by a town, the more FOOM wastes will be produced, and inversely. And the more GMS and FOOM wastes are produced, the less institutional catering wastes, fast food waste and open market wastes will produced. Lastly, farming sludge are principally represented in the axis F1 and are positively correlated to F1 (quasi aligned with axis F1).

So, we can conclude that the axis F2 is representing anthropic activities and the axis F1 farming activities.

Results

  HATIK christelle.hatik@univ-reunion.fr ICEER2017 -the 4 th International Conference on Energy and Environment Research -17-20 July 201 7, Porto, Portugal

  typology Correlation/anti-correlation between waste streams

of Waste Management Scenarios by Principal Component Analysis: A Case Study in Reunion Island

  University of La Réunion , 117, rue Général Ailleret, 97430 Le Tampon, Ile de la Réunion, France

	Context	01 Methodology
	PLACEZ photo
	ICI...
	02 Focus on La Réunion	03 PCA Results: Case Study Of La Réunion
	04 Conclusion

²

Optimization

PhD Christelle HATIK a , Pr Jean-Claude Gatina a Laboratory PIMENT a