Andrea Tirinzoni

Andrea Sessa

Matteo Pirotta

Marcello Restelli

Importance Weighted Transfer of Samples in Reinforcement Learning

We consider the transfer of experience samples (i.e., tuples s, a, s , r ) in reinforcement learning (RL), collected from a set of source tasks to improve the learning process in a given target task. Most of the related approaches focus on selecting the most relevant source samples for solving the target task, but then all the transferred samples are used without considering anymore the discrepancies between the task models. In this paper, we propose a model-based technique that automatically estimates the relevance (importance weight) of each source sample for solving the target task. In the proposed approach, all the samples are transferred and used by a batch RL algorithm to solve the target task, but their contribution to the learning process is proportional to their importance weight. By extending the results for importance weighting provided in supervised learning literature, we develop a finite-sample analysis of the proposed batch RL algorithm. Furthermore, we empirically compare the proposed algorithm to state-of-the-art approaches, showing that it achieves better learning performance and is very robust to negative transfer, even when some source tasks are significantly different from the target task.

Introduction

The goal of transfer in Reinforcement Learning (RL) [START_REF] Sutton | Reinforcement learning: An introduction[END_REF] is to speed-up RL algorithms by reusing knowledge obtained from a set of previously learned tasks. The intuition is that the experience made by learning source tasks might be useful for solving a related, but different, target task. Transfer across multiple tasks may be achieved in different ways. The available approaches differ in the type of information transferred (e.g., samples, value func-tions, parameters, policies, etc.) and in the criteria used to establish whether such knowledge could be beneficial for solving the target or not.

This work focuses on the problem of transferring samples from a set of source MDPs to augment the dataset used to learn the target MDP. To motivate our approach, consider a typical learning scenario where samples are costly to obtain. This is often the case in robotics applications, where the interaction with the real environment could be extremely time-consuming, thus reducing the number of samples available. The typical remedy of adopting a simulator often leads to sub-optimal solutions due to the differences with respect to the real environment. A more effective approach is to transfer the simulated samples to speedup learning in the target task.

The transfer of samples has been widely studied in the supervised learning community. In particular, [START_REF] Crammer | Learning from multiple sources[END_REF] formalized the problem from a theoretical perspective and provided generalization bounds for the transfer scenario. An interesting result is a trade-off between the number of tasks from which to transfer and the total number of samples. In RL, [START_REF] Taylor | Transferring instances for model-based reinforcement learning[END_REF] and [START_REF] Lazaric | Transfer of samples in batch reinforcement learning[END_REF] proposed almost simultaneously methods to transfer single samples. While the former method focused on a model-based approach, the latter one proposed a selective approach to transfer samples into a batch RL algorithm (e.g., Fitted Q-Iteration [START_REF] Ernst | Tree-based batch mode reinforcement learning[END_REF]). Furthermore, [START_REF] Lazaric | Transfer of samples in batch reinforcement learning[END_REF] considered a model-free approach to compute a similarity measure between tasks, which was used to decide which samples to transfer. More recently, [START_REF] Lazaric | Transfer from multiple mdps[END_REF] analyzed the transfer of samples in batch RL from a theoretical perspective, demonstrating again the trade-off between the total number of samples and the number of tasks from which to transfer. Finally, [START_REF] Laroche | Transfer reinforcement learning with shared dynamics[END_REF] proposed a way to transfer all the samples to augment the dataset used by Fitted Q-Iteration. The limitation of this approach resides in the restrictive assumption that all the tasks are assumed to share the same transition dynamics and differ only in the reward function. For a survey on transfer in RL, we refer the reader to [START_REF] Taylor | Transfer learning for reinforcement learning domains: A survey[END_REF][START_REF] Lazaric | Transfer in reinforcement learning: a framework and a survey[END_REF].

One of the main drawbacks of many previous works is that, even after a detailed selection, transferred samples are used in the target task without accounting for the differences between the original (source) MDP and the target one, thus introducing a bias even in the asymptotic case. In this paper, we present a novel approach to transfer samples into a batch RL algorithm. Unlike other works, we do not assume any particular similarity between tasks besides a shared stateaction space, and we develop a new model-based methodology to automatically select the relevance (importance weight) of each sample. Existing algorithms for transferring across different state-action spaces (e.g., [START_REF] Taylor | Transfer learning via inter-task mappings for temporal difference learning[END_REF] can be straightforwardly combined to our method. Our approach transfers all the samples, but their impact in solving the target task is proportional to their importance weight. To compute the importance weight of each sample, we rely on a non-parametric estimate of the MDP structure.

In particular, we adopt Gaussian processes [START_REF] Rasmussen | Gaussian processes for machine learning[END_REF] to estimate the reward and state transition models of the source and target tasks from samples. Then, we propose a robust way to compute two sets of importance weights, one for the reward model and one for the transition model. We introduce an approximate value iteration algorithm based on Fitted Q-iteration that uses such weights to account for the distribution shift introduced by the different MDPs, thus implicitly selecting which samples have higher priority based on their likelihood to be generated from the target MDP. We provide a theoretical analysis showing the asymptotic correctness of our approach and an empirical evaluation on two classical RL domains and a real-world task.

Preliminaries

In this section, we start by introducing our mathematical notation. Then, we recall concepts of Markov decision processes and approximate value iteration. Finally, we formalize the transfer settings considered in this work.

Notation. For a measurable space Ω, σ Ω , we denote by ∆(Ω) the set of probability measures over σ Ω and by B(Ω, L) the space of measurable functions over

Ω bounded by 0 < L < ∞, i.e., ∀f ∈ B(Ω, L), ∀x, |f (x)| ≤ L.
Given a probability measure µ, we define the p -norm of

a measurable function f as f p,µ = |f | p dµ 1/p . Let z 1:N be a Z-valued sequence (z 1 , . . . , z N ) for some space Z. For D N = z 1:N , the empirical norm of a function f : Z → R is f p p,D N := 1 N N i=1 |f (z i )| p . Note that when Z i ∼ µ, we have that E[ f p p,D N ] = f p p,µ .
Whenever the subscript p is dropped, we implicitly consider the 2 -norm.

Markov Decision Process. We define a discounted Markov Decision Process (MDP) as a tuple M = S, A, P, R, γ , where S is a measurable state space, A is a finite set of actions, P : S × A → ∆(S) is the transi-tion probability kernel, R : S × A → ∆(R) is the reward probability kernel, and γ ∈ [0, 1) is the discount factor. We suppose R(s, a) = E [R(•|s, a)] is uniformly bounded by r max . A Markov randomized policy maps states to distributions over actions as π : S → ∆(A). As a consequence of taking an action a t in s t , the agent receives a reward r t ∼ R(•|s t , a t ) and the state evolves accordingly to s t+1 ∼ P(•|s t , a t ). We define the action-value function of a policy π as

Q π (s, a) = E [ ∞ t=0 γ t r t | M, π, s 0 = s, a 0 = a]
and the optimal action-value function as

Q * (s, a) = sup π Q π (s, a) for all (s, a). Notice that Q is bounded by Q max := rmax 1-γ .
Then, the optimal policy π * is a policy that is greedy with respect to Q * , i.e., for all s ∈ S, π * (s) ∈ arg max a∈A {Q * (s, a)}. The optimal actionvalue function is also the unique fixed-point of the optimal Bellman operator [START_REF] Puterman | Markov Decision Processes: Discrete Stochastic Dynamic Programming[END_REF].

L * : B(S × A, Q max ) → B(S × A, Q max ), which is defined by (L * Q)(s, a) := R(s, a) + γ S P(ds |s, a) max a Q(s , a ) (e.g.,
Approximate solution. Fitted Q-Iteration (FQI) [START_REF] Ernst | Tree-based batch mode reinforcement learning[END_REF] is a batch RL algorithm that belongs to the family of Approximate Value Iteration (AVI). AVI is a value-based approach that represents Q-functions by a hypothesis space H ⊂ B(S × A, Q max ) of limited capacity. Starting from an initial action-value function Q 0 ∈ H, at each iteration k ≥ 0, AVI approximates the application of the optimal Bellman operator in H such that

Q k+1 ≈ L * Q k . Formally, let D N = { s i , a i , s i , r i } N i=1
be a set of transitions such that (s i , a i ) ∼ µ and define the empirical optimal Bellman operator as ( L * Q)(s i , a i ) := r i + γ max a Q(s i , a ). Then, at each iteration k, FQI computes

Q k+1 = arg min h∈H h -L * Q k 2 D N .
(1)

Transfer settings. We consider a set of tasks, i.e., MDPs, {M j = S, A, P j , R j , j = 0, . . . , m}, where M 0 denotes the target and M 1 , . . . , M m the sources. We suppose all tasks share the same state-action space and have potentially different dynamics and reward. Suppose that, for j = 0, . . . , m, we have access to a dataset of N j samples from the j-th MDP,

D j = { s i , a i , s i , r i } Nj i=1
, where state-action pairs are drawn from a common distribution µ ∈ ∆(S × A).1 The goal of transfer learning is to use the samples in D 1 , . . . , D m to speed up the learning process in the target task M 0 .

Importance Weights for Transfer

In this section, we introduce our approach to the transfer of samples. Recall that our goal is to exploit at best samples in

Algorithm 1 Importance Weighted Fitted Q-Iteration Input: The number of iterations K, a dataset D + = m j=0 Nj i=0 s (j) i , a (j)
i , s

(j) i , r (j)
i , w

(j) r,i , w (j) p,i , a hypothesis space H Output: Greedy policy π K R ← arg inf h∈H 1 Zr j,i w (j) r,i h(s (j) i , a (j) i ) -r (j) i 2 Q 0 ← R for k = 0, . . . , K -1 do Y (j) i ← L * Q k (s (j) i , a (j) i ), ∀i, j Q k+1 ← arg inf h∈H 1 Zp j,i w (j) i,p h(s (j) i , a (j) i ) -Y (j) i 2 end for π K (s) ← arg max a∈A {Q K (s, a)}, ∀s ∈ S
{D 1 , . . . , D M } to augment the dataset D 0 used by FQI to solve the target task, thus speeding up the learning process. In the rest of the paper we exploit the fact that FQI decomposes the RL problem into a sequence of supervised learning problems. It is easy to notice that the optimization problem ( 1) is an instance of empirical risk minimization, where

X i = (s i , a i ) are the input data, Y i = ( L * Q k )(s i , a i ) are the targets, and L(f (X i ), Y i ) = |f (X i ) -Y i | 2 is a squared loss.
As mentioned in the introduction, we aim to exploit all the available samples to solve the target task. Suppose we adopt a naive approach where we concatenate all the samples, i.e., D = m j=0 D j = m j=0 Nj i=0 s j i , a j i , s j i , r j i , to solve (1). This approach suffers from sample selection bias [START_REF] Cortes | Sample selection bias correction theory[END_REF], i.e., samples are collected from different distributions or domains. In fact, although we assumed state-action pairs to be sampled from a fixed taskindependent distribution, the target variables Y are distributed according to the MDP they come from.

A standard technique used to correct the bias or discrepancy induced by the distribution shift is importance weighting. This technique consists in weighting the loss function to emphasize the error on some samples and decrease it on others, to correct the mismatch between distributions [START_REF] Cortes | Sample selection bias correction theory[END_REF]. The definition of the importance weight for the point X is w(X) = P (X)/Q(X) where P is the distribution of the target, and Q is the distribution according to which sample X is collected. In our specific case, given an arbitrary sample (X, Y ), its joint distribution under MDP M j is P((X, Y )|M j ) = P(Y |X, M j )µ(X). Denote by (X

(j) i , Y (j)
i ) the i-th sample drawn from MDP M j , then its importance weight is given by w(X

(j) i , Y (j) i ) = P(Y (j) i |X (j) i ,M0) P(Y (j) i |X (j) i ,Mj )
. By feeding FQI on the full dataset D with samples weighted by w (j) i (for short), we get an algorithm that automatically selects which samples to exploit, i.e., those that, based on the importance weights, are more likely to be generated from the target MDP. This approach looks appealing but presents several issues. First, the distribution P(Y |X, M j ) is, even in the case where the MDPs are known, very hard to characterize. Second, consider a simple case where we have a source MDP with the same transition dynamics as the target, but with entirely different reward. Then, the importance weights defined above are likely to be very close to zero for any source sample, thus making transfer useless. However, we would like a method able to leverage the fact that transition dynamics do not change, thus transferring only that part of the sample.

To overcome the second limitation, we consider the following variation of the FQI algorithm. At the first iteration of FQI, we use all the samples to fit a model R ≈ R of the target reward function:

R = arg inf h∈H 1 Z r m j=0 Nj i=0 w (j) r,i h(X (j) i ) -r (j) i 2 , (2)
where H ⊂ B(S × A, Q max ) is the hypothesis space we consider to represent action-value functions2 and w (j)

r,i = R 0 (r (j) i |X (j) i ) R j (r (j) i |X (j) i )
.

(3)

Problem (2) is unbiased if Z r = m j=0 N j , though Z r = i,j w (j)
r,i is frequently used since it provides lower variance. The theoretical analysis is not affected by the choice of Z r , while in the experiments we will use Z r = i,j w (j) r,i . Then, at each iteration k ≥ 0, FQI updates the Q-function as:

Q k+1 = arg inf h∈H 1 Z p m j=0 Nj i=0 w (j) p,i h(X (j) i ) -Y (j) i 2 (4) where Y (j) i = L * Q k (X (j) i ) := R(s (j) i , a (j) i ) + γ max a Q k (s (j) i , a ) and Q 0 = R. Intuitively, instead of considering the reward r (j) i in the dataset D, we use R(s (j) i , a (j) i ).
Since the stochasticity due to the reward samples is now removed, only the transition kernel plays a role, and the importance weights are given by:

w (j) p,i = P 0 (s (j) i |X (j) i ) P j (s (j) i |X (j) i )
.

(5)

The resulting algorithm, named Importance Weighted Fitted Q-Iteration (IWFQI), is shown in Algorithm 1. In practice, we have to compute an estimate of w (j) r,i and w (j) p,i since P j and R j are unknown quantities. We postpone this topic to Section 5 since several approaches can be exploited. Instead, in the following section, we present a theoretical analysis that is independent of the way the importance weights are estimated.

Theoretical Analysis

We now study the theoretical properties of our IWFQI algorithm. We analyze the case where we have samples from one source task, but no samples from the target task are available, i.e., m = 1, N 0 = 0, and N 1 = N . A generalization to the case where target samples or samples from more sources are available is straightforward, and it only complicates our derivation. To ease our notation, we adopt the subscript "T" and "S" to denote the target and the source. Furthermore, we want to emphasize that the results provided in this section are independent from the way the importance weights are estimated.

Consider the sequence of action-value functions

Q 0 , Q 1 , . . . , Q K computed by IWFQI. At each itera- tion k, we incur in an error k = L * Q k -Q k+1 in
approximating the optimal Bellman operator. Our goal is to bound, in terms of such errors, Q * -Q π k 1,ρ , i.e., the expected error under distribution ρ between the performance of the optimal policy and that of the policy π k greedy w.r.t. Q k . Here ρ is an arbitrary evaluation distribution over S × A that the user can freely choose. In practice, it might coincide with the sampling distribution µ. Since IWFQI belongs to the family of AVI algorithms, we can resort to Theorem 3.4 in [START_REF] Farahmand | Regularization in reinforcement learning[END_REF].

We report here the version with 1 -norm for the sake of completeness.

Theorem 1. (Theorem 3.4 of [START_REF] Farahmand | Regularization in reinforcement learning[END_REF])) Let K be a positive integer and

Q max ≤ rmax 1-γ . Then, for any se- quence (Q k ) K k=0 ⊂ B(S × A, Q max ) and the correspond- ing sequence ( k ) K k=0 , where k = L * Q k -Q k+1 , we have: Q * -Q π K 1,ρ ≤ 2γ (1 -γ) 2 2γ K Q max + inf b∈[0,1] C 1 2 VI,ρ,µ (K; b)E 1 2 ( 0 , . . . , K-1 ; b) ,
where:

E( 0 , . . . , K-1 ; b) = K-1 k=0 α 2b k k 2 µ .
We refer the reader to Chapter 3 of [START_REF] Farahmand | Regularization in reinforcement learning[END_REF] for the definitions of the coefficients C VI,ρ,µ and α k .

Intuitively, the bound given in Theorem 1 depends on the errors made by IWFQI in approximating the optimal Bellman operator at each iteration. Thus, our problem reduces to bounding such errors. [START_REF] Cortes | Learning bounds for importance weighting[END_REF] already provided a theoretical analysis of importance weighted regression. However, their results are not immediately applicable to our case since they only consider a regression problem where the target variable Y is a deterministic function of the input X. On the other hand, we have the more general regression estimation problem where Y is a random variable, and we want to learn its conditional expectation given X. Thus, we extend Theorem 4 of [START_REF] Cortes | Learning bounds for importance weighting[END_REF] to provide a bound on the expected 2 -error hh * µ between the hypothesis h returned by a weighted regressor (with estimated weights w) and the regression function h * . Following [START_REF] Cortes | Learning bounds for importance weighting[END_REF], we denote by P dim(U ) the pseudo-dimension of a real-valued function class U . The proof is in the appendix.

Theorem 2. Let H ⊂ B(X, F max ) be a functional space. Suppose we have a dataset of N i.i.d. sam- ples D = {(x i , y i )} distributed according to Q(X, Y ) = q(Y |X)µ(X), while P (X, Y ) = p(Y |X)µ(X) is the target distribution. Assume |Y | ≤ F max almost surely. Let w(x, y) = p(y|x) q(y|x) , w(x, y) be any positive func- tion, h(x) = arg min f ∈H E D w(X, Y )|f (X) -Y | 2 , h * (x) = E p [Y |x], g(x) = E q [ w(x, Y )|x] -1, and
M ( w) = E Q [ w(X, Y ) 2 ] + E D [ w(X, Y ) 2 ]
, where E D denotes the empirical expectation on D. Furthermore, assume

d = P dim({|f (x) -y| 2 : f ∈ H}) < ∞ and E Q [ w(X, Y ) 2 ] < ∞.
Then, for any δ > 0, the following holds with probability at least 1 -2δ:

h -h * µ ≤ inf f ∈H f -h * µ + F max g 1,µ + 2 13/8 F max M ( w) d log 2N e d + log 4 δ N 3 16 + 2F max w -w Q
Notice that this result is of practical interest outside of the reinforcement learning field. Here it is used to bound the errors k µ in order to state the following result. Theorem 3. Let H ⊂ B(S × A, Q max ) be a hypothesis space, µ a distribution over S × A, (Q i ) k+1 i=0 a sequence of Q-functions as defined in Equation (4), and L * the optimal Bellman operator of the target task. Suppose to have a dataset of N i.i.d. samples D drawn from the source task M S according to a joint distribution φ S . Let w p , w r denote the ideal importance weights defined in (5) and (3), and w r (r|s, a), w p (s |s, a) denote arbitrary positive functions with bounded second moments. Define g r (s, a)

= E R S [ w r (r|s, a)|s, a] -1, M ( w r ) = E φ R S [ w r (r|s, a) 2 ]+ E D [ w r (r|s, a) 2 ],
where φ R S (r|s, a) = µ(s, a)R S (r|s, a). Similarly, define g p , M ( w p ), and φ P S (s |s, a) for the transition model. Then, for any δ > 0, with probability at least 1 -4δ:

L * Q k -Q k+1 µ ≤ Qmax gp 1,µ + 2rmax gr 1,µ + 2Qmax wp -wp φ P S + 4rmax wr -wr φ R S + inf f ∈H f -(L * ) k+1 Q0 µ + 2 inf f ∈H f -R µ + Qmax 2 -13 8 M ( wp) + 2 M ( wr) d log 2N e d + log 4 δ N 3 16 + k-1 i=0 (γCAE(µ)) i+1 k-i-1 µ,
where C AE is the concentrability coefficient of one-step transitions as defined in (Farahmand, 2011, Definition 5.2).

As expected, four primary sources of error contribute to our bound: (i) the bias due to estimated weights (first four terms), (ii) the approximation error (fifth and sixth term), (iii) the estimation error (seventh term), (iv) the propagation error (eighth term). Notice that, assuming to have a consistent estimator for the importance weights (an example is given in Section 5), the bias term vanishes as the number of samples N tends to infinity. Furthermore, the estimation error decreases with N , thus vanishing as the number of samples increases. Thus, in the asymptotic case our bound shows that the only source of error is due to the limited capacity of the functional space H under consideration, as in most AVI algorithms. Furthermore, we notice that fitting the reward function and using it instead of the available samples propagates an error term through iterations, i.e., the approximation error inf f ∈H f -R µ . If we were able to estimate the importance weights for the typical case where both reward and transition samples are used, we could get rid of such error. However, since the resulting weights somehow depend on the joint densities between P and R, we expect their variance, as measured by M ( w), to be much bigger, thus making the resulting bound even larger. Furthermore, we argue that, when the reward function is simple enough and only a limited number of samples is available, a separate fit might be beneficial even for plain FQI. In fact, the variance of the empirical optimal Bellman operator can be reduced by removing the source of stochasticity due to the reward samples at the cost of propagating a small approximation error through iterations. The bounds for AVI, (e.g., [START_REF] Munos | Finite-time bounds for fitted value iteration[END_REF][START_REF] Farahmand | Regularization in reinforcement learning[END_REF][START_REF] Farahmand | Value pursuit iteration[END_REF], can be straightforwardly extended to such case by adopting a procedure similar to the one described in the proof of Theorem 3. Finally, in most practical applications the reward function is actually known and, thus, does not need to be fitted. In such cases, it is possible to get rid of the corresponding terms in Theorem 3, allowing transfer to occur without errors even when rewards are completely different between tasks.

Estimation of Importance Weights

In this section, we specify how to compute the importance weights. Since P and R are unknown, we only have access to an estimation of w (j) r,i and w (j) p,i used in (3) and ( 5), respectively. To obtain an approximation of the unknown densities, we consider Gaussian Processes (GPs) although any distribution matching technique and/or probabilistic model can be used.

Gaussian Processes. We use the available samples to fit two Gaussian processes (GPs) [START_REF] Rasmussen | Gaussian processes for machine learning[END_REF] for each task M j : one for the transition model P j and one for the reward model R j . To motivate our choice, GPs have been successfully adopted to model stochastic dynamical systems with high-dimensional and continuous state-action spaces in many existing works (e.g., [START_REF] Kuss | Gaussian processes in reinforcement learning[END_REF][START_REF] Deisenroth | Pilco: A modelbased and data-efficient approach to policy search[END_REF][START_REF] Doshi-Velez | Hidden parameter markov decision processes: A semiparametric regression approach for discovering latent task parametrizations[END_REF]Berkenkamp et al., 2017). For the sake of simplicity, we only show how to compute the importance weights for the reward model. Our procedure straightforwardly generalizes to the transition model. Given a sample s, a, r from the j-th task, the j-th GP returns a Gaussian distribution over the reward's mean, i.e., r(s, a) ∼ N (µ GPj (s, a), σ 2 GPj (s, a)), which, together with the target GP's prediction, induces a distribution over the importance weights. In practice, the choice of a single importance weight can rely on some statistics of such distribution (e.g., its mean or mode). Perhaps not surprisingly, this is made non-trivial by the fact that explicitly characterizing such distribution is very complicated, and computing empirical statistics requires an expensive repeated sampling from the GPs' posteriors. Interestingly, the following theorem shows that this is not necessary when the reward model follows a Gaussian law, as the expected weights under their unknown distribution can be computed in closedform.

Theorem 4 (Reward Weights in Gaussian Models). Assume each task to have Gaussian reward distribution

R j (•|s, a) = N µ (j)
r (s, a), σ 2 j (s, a) with unknown mean. Given the available samples in D, we build an estimate of the reward distribution such that, for any MDP M j , r (j) (s, a) ∼ N (µ GPj (s, a), σ 2 GPj (s, a)). Then, given a sample s, a, r from the j-th MDP, its importance weight w = N (r|r (0) (s,a),σ 2 0 (s,a))

N (r|r (j) (s,a),σ 2 j (s,a)) ∼ G, where G is the distribution induced by the GPs' predictions.

Let C = σ 2 j (s,a) σ 2 j (s,a)-σ 2 GP j
(s,a) and suppose σ 2 GPj (s, a) < σ 2 j (s, a), then

E G [w] = C N r µ GP 0 (s,a),σ 2 0 (s,a)+σ 2 GP 0 (s,a) N r µ GP j (s,a),σ 2 j (s,a)-σ 2 GP j (s,a)
.

The proof is in Appendix A. In practice, we estimate the importance weights by taking their expectation as in (6), i.e., w = E G [w]. Intuitively, using the expected weights is more robust than merely taking the ratio of the estimated densities. Furthermore, the estimated weights converge to the true ones when the GP predictions are perfect, i.e., when µ GP (s, a) = µ r (s, a) and σ 2 GP (s, a) → 0, both in the source and in the target. This is a significant advantage over the more common approach of density-ratio estimation [START_REF] Sugiyama | Density ratio estimation in machine learning[END_REF], where a parametric form for the weight function is typically assumed. One drawback is that the expectation diverges when σ 2 GPj (s, a) > σ 2 j , that is, when the source GP has a prediction variance that is greater than the intrinsic noise of the model. Notice, however, that this happens very rarely since the source GP is never asked to predict samples it has not seen during training. Furthermore, since in practice the model noise is unknown and has to be estimated, an overestimation is beneficial as it introduces a regularization effect [START_REF] Mohammadi | An analytic comparison of regularization methods for gaussian processes[END_REF], thus avoiding the problem mentioned above.

Related Work

In [START_REF] Taylor | Transferring instances for model-based reinforcement learning[END_REF], the authors propose a method to transfer samples for model-based RL. Although they assume tasks might have different state-action space, intertask mappings are used to map source samples to the target. However, the proposed method does not account for differences in the transition or reward models, which could lead to significant negative transfer when the tasks are different. Our approach, on the other hand, can selectively discard samples based on the estimated difference between the MDPs. [START_REF] Lazaric | Transfer of samples in batch reinforcement learning[END_REF] compute a compliance measure between the target and source tasks and use it to specify from which tasks the transfer is more likely to be beneficial. Furthermore, a relevance measure is computed within each task to determine what are the best samples to transfer. These two measures are then combined to transfer samples into FQI. Once again, our approach does not require any explicit condition to decide what to transfer, nor does it require any assumption of similarity between the tasks. Furthermore, the compliance and relevance measures computed in [START_REF] Lazaric | Transfer of samples in batch reinforcement learning[END_REF] jointly account for both the reward and transition models, thus discarding samples when either one of the models is very different between the tasks. On the other hand, our approach can retain at least the part of the sample that is similar, at the cost of introducing a small bias. In [START_REF] Laroche | Transfer reinforcement learning with shared dynamics[END_REF], the authors propose a technique for transferring samples into FQI under the assumption that the transition dynamics do not change between the tasks. Similarly to our method, they learn the reward function at the first iteration and substitute the predicted values to the reward samples in the dataset. This allows them to safely adopt the full set of target and source samples in the remaining FQI iterations, as all tasks share the same transition model and, thus, samples are unbiased. However, we argue that this assumption of shared dynamics indeed limits the applicability of the transfer method to most real-world tasks.

In the supervised learning literature, [START_REF] Crammer | Learning from multiple sources[END_REF] analyzed the transfer problem from a theoretical perspective and extended the classical generalization bounds to the case where samples are directly transferred from a set of source tasks. The most relevant result in their bounds is a trade-off between the total number of samples transferred and the total number of tasks from which transfer occurs. Increasing the first term decreases the variance, while it is likely to increase the bias due to the differences between the tasks. On the other hand, decreasing the first term also decreases the bias, but it is likely to increase the variance due to the limited number of samples. We observe that such trade-off does not arise in our case. Our method transfers all samples while accounting for the differences between the tasks. The only bias term is due to the errors in the estimation of the task models, which is likely to decrease as the number of samples increases.

Another work from the supervised learning literature that is related to our approach is [START_REF] Garcke | Importance weighted inductive transfer learning for regression[END_REF]. The authors proposed a method to transfer samples from a different dataset and used importance weighting to correct the distribution shift. However, they leveraged ideas from density-ratio estimation (e.g., [START_REF] Sugiyama | Density ratio estimation in machine learning[END_REF] and supposed the weight function to have a given parametric form, thus directly estimating it from the data. Conversely, we estimate the densities involved and try to characterize the weight distribution, taking its expectation as our final estimate.

Experiments

We evaluate IWFQI on three different domains with increasing level of complexity. In all experiments, we compare our method to two existing algorithms for transferring samples into FQI: the relevance-based transfer (RBT) algorithm of [START_REF] Lazaric | Transfer of samples in batch reinforcement learning[END_REF] and the shared-dynamics transfer (SDT) algorithm of [START_REF] Laroche | Transfer reinforcement learning with shared dynamics[END_REF].

Puddle World

Our first experimental domain is a modified version of the puddle world environment presented in [START_REF] Sutton | Generalization in reinforcement learning: Successful examples using sparse coarse coding[END_REF]. Puddle world is a discrete-action, continuous-state (stochastic) navigation problem (see Appendix C.1 for a complete description). At each time-step, the agent receives a reward of -1 plus a penalization proportional to the distance from all puddles. Each action moves the agent by α in the corresponding direction. In particular, we con- sider two versions of the environment: (i) shared dynamics, where α = 1 is fixed, and (ii) puddle-based dynamics, where α slows-down the agent proportionally to the distance from all puddles.

We consider three source tasks and one target task, where each task has different puddles in different locations (see Appendix C.1). For each source task, we generate a dataset of 20 episodes from a nearly-optimal policy. We run IWFQI with weights computed according to Equation ( 6), where we set the model noise to be ten times the true value. For evaluating our weight estimation procedure, we also run IWFQI with ideal importance weights (computed as the ratio of the true distributions). In each algorithm, FQI is run for 50 iterations with Extra-Trees [START_REF] Ernst | Tree-based batch mode reinforcement learning[END_REF]). An -greedy policy ( = 0.3) is used to collect data in the target task.

Shared dynamics. We start by showing the results for α = 1 in Figure 1(left). All results are averaged over 20 runs and are reported with 95% confidence intervals.

As expected, FQI alone is not able to learn the target task in such a small number of episodes. On the other hand, IWFQI has a good jump-start and converges to an optimal policy in only 20 episodes. Interestingly, IWFQI with ideal weights has almost the same performance, thus showing the robustness of our weight estimation procedure. RBT also learns the optimal policy rather quickly. However, the limited number of target and source samples available in this experiment makes it perform significantly worse in the first episodes. Since in this version of the puddle world the dynamics do not change between tasks, SDT also achieves good performance, converging to a nearly-optimal policy.

Puddle-based dynamics. We also show the results for the more challenging version of the environment were puddles both penalize and slow-down the agent (see Figure 1(right)). Notice that, in this case, transition dynamics change between tasks, thus making the transfer more challenging. Similarly, as before, our approach quickly learns the optimal policy and is not affected by the estimated weights. Furthermore, the benefits of over-estimating the model noise can be observed from the small improvement over IWFQI-ID. RBT is also able to learn the optimal policy. However, the consequences of inaccurately computing compliance and relevance are more evident in this case, where the algorithm negatively transfers samples in the first episodes. Finally, SDT still shows an improvement over plain FQI, but it is not able to learn the optimal policy due to the bias introduced by the different dynamics.

Acrobot

Acrobot [START_REF] Sutton | Reinforcement learning: An introduction[END_REF]) is a classic control problem where the goal is to swing-up a two-link pendulum by applying positive or negative torque to the joint between the two links. Due to its non-linear and complex dynamics, Acrobot represents a very challenging problem, requiring a considerable amount of samples to be solved. In this experiment, we consider a multi-task scenario where robots might have different link lengths (l 1 , l 2 ) and masses (m 1 , m 2 ). Our target task is the classic Acrobot swing-up problem, where the robot has lengths (1.0, 1.0) and masses (1.0, 1.0). Furthermore, we consider two source tasks. The first is another swing-up task where the robot has lengths (1.1, 0.7) and masses (0.9, 0.6). The second is a constantspin task, where the goal is to make the first joint rotate at a fixed constant speed, with lengths (0.95, 0.95) and masses (0.95, 1.0). The exact definition of the tasks' dynamics and rewards is in Appendix C.2. Notice the intrinsic difficulty of transfer: the first source task has the same reward as the target but very different dynamics, and conversely for the second source task. Using nearly-optimal policies, we generate 100 episodes from the first source and 50 episodes from the second. We run all algorithms (except SDT since the problem violates the shared-dynamics assumption) for 200 episodes and average over 20 runs. Results are shown in Figure 2(left). We notice that both our approach and RBT achieve a good jump-start and learn faster than plain FQI. However, to better investigate how samples are transferred, we show the transfer ratio from each source task in Figure 2(right). Since RBT transfers rewards and transitions jointly, it decides to compensate the highly biased re-ward samples from the constant-spin task by over-sampling the first source task. However, it inevitably introduces bias from the different dynamics. Our approach, on the other hand, correctly transfers almost all reward samples from the swing-up task, while discarding those from the constant-spin task. Due to transition noise over-estimation, IWFQI achieves an interesting adaptive behaviour: during the initial episodes, when few target samples are available, and the GPs are inaccurate, more samples are transferred. This causes a reduction of the variance in the first phases of learning that is much greater than the increase of bias. However, as more target samples are available, the transfer becomes useless, and our approach correctly decides to discard most transition samples, thus minimizing both bias and variance.

Water Reservoir Control

In this experiment, we consider a real-world problem where the goal is to learn how to optimally control a water reservoir system. More specifically, the objective is to learn a per-day water release policy that meets a given demand while keeping the water level below a flooding threshold. [START_REF] Castelletti | Tree-based reinforcement learning for optimal water reservoir operation[END_REF] successfully addressed such problem by adopting batch RL techniques. However, the authors proved that, due to the highly non-linear and noisy environment, an enormous amount of historical data is needed to achieve good performance. Consider now the case where a new water reservoir, for which no historical data is available, needs to be controlled. Since each sample corresponds to one day of release, learning by direct interaction with the environment is not practical and leads to poor control policies during the initial years, when only a little experience has been collected. Although we do not know the new environment, it is reasonable to assume that we have access to operational data from existing reservoirs. Then, our solution is to transfer samples to immediately achieve good performance. However, such reservoirs might be located in very different environments and weight objectives differently, thus making transfer very challenging.

We adopt a system model similar to the one proposed in [START_REF] Castelletti | Tree-based reinforcement learning for optimal water reservoir operation[END_REF]. The state variables are the current water storage s t and day t ∈ [1, 365], while there are 8 discrete actions, each corresponding to a particular release decision. The system evolves according to the simple mass balance equation s t+1 = s t + i ta t , where i t is the net inflow at day t and is modeled as periodic function, with period of one year, plus Gaussian noise. Given the demand d and the flooding threshold f , the reward function is a convex combination of the two objectives, R(s t , a t ) = -α max{0, s tf }β(max{0, da t }) 2 , where α, β ≥ 0. Different tasks have different inflow functions and different reward weights, which model different geographic regions and objectives, respectively. We collected 10800 samples, corresponding to 30 years of historical data, from each of 6 source water reservoirs under a hand-coded expert policy. Further details about the tasks are given in Appendix C.3. We compared our approach to FQI and RBT over the first 10 years of learning. An -greedy policy ( = 0.3) was used to collect batches of 1 year of samples, except for the first batch, for which an expert's policy was used. Results, averaged over 20 runs, are shown in Figure 3. We notice that IWFQI immediately outperforms the expert's policy and quickly achieves nearoptimal performance. RBT, on the other hand, has a good jump-start but then seems to worsen its performance. Once again, this is because each source task has at least few samples that can be transferred. However, selecting such samples is very complicated and leads to negative transfer in case of failure. Finally, FQI performs significantly worse than all alternatives and is, thus, not reported.

Conclusions

In this paper, we presented Importance Weighted Fitted Q-Iteration, a novel AVI algorithm for transferring samples in batch RL that uses importance weighting to automatically account for the difference in the source and target distributions. IWFQI exploits Gaussian processes to learn transition and reward models that are used to compute the importance weights. The use of two different processes for reward and transition models allows maximizing the information transferred. We theoretically investigated IWFQI showing (i) its asymptotic correctness in general settings, and (ii) how to compute a robust statistical estimate of the weights for Gaussian models. Finally, we empirically proved its effectiveness in common benchmarks and on a real-world water control problem.

One of the drawbacks of our method is that it does not fully exploit possible similarities between tasks. Recent approaches (e.g., [START_REF] Doshi-Velez | Hidden parameter markov decision processes: A semiparametric regression approach for discovering latent task parametrizations[END_REF][START_REF] Killian | Robust and efficient transfer learning with hidden parameter markov decision processes[END_REF] learn models relating a family of tasks to ease the transfer of knowledge. Exploring how such relations can benefit our approach (e.g., to improve the weight estimates) is an interesting line for future developments.

A. Gaussian Models: remarks and proofs

In this section we consider the case where the transition and reward models are Gaussian distributions.

A task M j = S, A, P j , R j , γ is jointly Gaussian when it has:

• Gaussian Reward: for any (s, a) ∈ S × A R j (•|s, a) = N (µ (j) r (s, a), σ 2 j (s, a)). (7)
• Gaussian Transitions: for any (s, a) ∈ S × A

P j (•|s, a) = N (µ (j) p (s, a), Σ j (s, a)) (8)
.

In this setting, by using a Gaussian process to estimate the transition and reward models, we can compute the expected importance weights, where the expectation is taken under the distribution induced by the GPs' predictions, in closed form. Note that, since reward and transition weights are independent, we can independently consider Assumptions 7 and 8 for the computation of w r and w p , respectively.

Theorem 4 (Reward Weights in Gaussian Models). Assume each task to have Gaussian reward distribution

R j (•|s, a) = N µ (j)
r (s, a), σ 2 j (s, a) with unknown mean. Given the available samples in D, we build an estimate of the reward distribution such that, for any MDP M j , r (j) (s, a) ∼ N (µ GPj (s, a), σ 2 GPj (s, a)). Then, given a sample s, a, r from the j-th MDP, its importance weight w = N (r|r (0) (s,a),σ 2 0 (s,a))

N (r|r (j) (s,a),σ 2 j (s,a)) ∼ G, where G is the distribution induced by the GPs' predictions. Let C = σ 2 j (s,a) σ 2 j (s,a)-σ 2 GP j (s,a) and suppose σ 2 GPj (s, a) < σ 2 j (s, a), then E G [w] = C N r µ GP 0 (s,a),σ 2 0 (s,a)+σ 2 GP 0
(s,a)

N r µ GP j (s,a),σ 2 j (s,a)-σ 2 GP j (s,a)

.

Proof. In order to simplify our notation, we consider the dependence on (s, a, r) implicit. We have:

E [w] = w N r (0) µ GP0 , σ 2 GP0 N r (j) µ GPj , σ 2 GPj dr (0) dr (j) = w exp - (r (0) -µ GP 0 ) 2 2σ 2 GP 0 2πσ 2 GP0 exp - (r (j) -µ GP j ) 2 2σ 2 GP j 2πσ 2 GPj dr (0) dr (j) = exp -(r-r (0) ) 2 2σ 2 0 2πσ 2 0 exp - (r (0) -µ GP 0 ) 2 2σ 2 GP 0 2πσ 2 GP0 dr (0) 2πσ 2 j exp -(r-r (j) ) 2 2σ 2 j exp - (r (j) -µ GP j ) 2 2σ 2 GP j 2πσ 2 GPj dr (j) .
The first integral is over the product of two Gaussian densities, which is known to be [START_REF] Bromiley | Products and convolutions of gaussian probability density functions[END_REF]:

N r (0) μ0 , σ2 0 N r µ GP0 , σ 2 0 + σ 2 GP0 , (9)
where the values of the mean μ0 and variance σ2 0 of the first density are not important to complete this proof since such density integrates out. By adopting the same procedure as the one described in [START_REF] Bromiley | Products and convolutions of gaussian probability density functions[END_REF], we can write the ratio of the two Gaussian densities in the second integral as:

σ 2 j σ 2 j -σ 2 GPj N r (j) μj , σ2 j N r µ GPj , σ 2 j -σ 2 GPj , (10)
where, again, the values of μj and σ2 j are not relevant to our proof. Finally, we can write:

E [w(r)] = N r (0) μ0 , σ2 0 N r µ GP0 , σ 2 0 + σ 2 GP0 dr (0) σ 2 j σ 2 j -σ 2 GPj N r (j) μj , σ2 j N r µ GPj , σ 2 j -σ 2 GPj dr (j) = σ 2 j σ 2 j -σ 2 GPj N r µ GP0 , σ 2 0 + σ 2 GP0 N r µ GPj , σ 2 j -σ 2 GPj N r (0) μ0 , σ2 0 dr (0) N r (j) μj , σ2 j dr (j) = σ 2 j σ 2 j -σ 2 GPj N (r µ GP0 , σ 2 0 + σ 2 GP0 ) N (r µ GPj , σ 2 j -σ 2 GPj )
.

We can derive a similar result for the transition model by considering Assumption 8.

Theorem 5 (Transition Weights in Gaussian Models). Assume each task to have Gaussian transition distribution

P j (•|s, a) = N (µ (j)
p (s, a), Σ j (s, a)) with unknown mean. Furthermore, suppose that Σ j (s, a) = diag δ 2 j,1 (s, a), δ 2 j,2 (s, a), . . . , δ 2 j,D (s, a) . Given the available samples in D, we build an estimate of the transition distribution such that, for any MDP M j and state component d, p

By noticing that the d-th GP for task j provides an independent estimate of the transition mean's d-th component, p

d , the proof of Theorem 4 can be straightforwardly applied to each component of s , thus proving the theorem.

B. Proofs of Theorems

Theorem 2. Let H ⊂ B(X, F max ) be a functional space. Suppose we have a dataset of N i.i.d. samples

D = {(x i , y i )} distributed according to Q(X, Y ) = q(Y |X)µ(X), while P (X, Y ) = p(Y |X)µ(X) is the target dis- tribution. Assume |Y | ≤ F max almost surely. Let w(x, y) = p(y|x)
q(y|x) , w(x, y) be any positive function,

h(x) = arg min f ∈H E D w(X, Y )|f (X) -Y | 2 , h * (x) = E p [Y |x], g(x) = E q [ w(x, Y )|x]-1, and M ( w) = E Q [ w(X, Y ) 2 ]+ E D [ w(X, Y ) 2 ]
, where E D denotes the empirical expectation on D. Furthermore, assume

d = P dim({|f (x) -y| 2 : f ∈ H}) < ∞ and E Q [ w(X, Y ) 2 ] < ∞.
Then, for any δ > 0, the following holds with probability at least 1 -2δ:

h -h * µ ≤ inf f ∈H f -h * µ + F max g 1,µ + 2 13/8 F max M ( w) d log 2N e d + log 4 δ N 3 16 + 2F max w -w Q
Proof. Applying Hölder's inequality, for all f ∈ H:

E Q w(X, Y )|f (X) -Y | 2 2 ≤ 16F 4 max E Q [ w(X, Y ) 2 ] < ∞. (13)
Thus, by applying Corollary 1 of [START_REF] Cortes | Learning bounds for importance weighting[END_REF] to L h (x, y) = w(x, y)|h(x) -y| 2 , we can write:

E Q [ w(X, Y )| h(X) -Y | 2 ] ≤ 1 N N i=1 w(x i , y i )| h(x i ) -y i | 2 + 2 13/4 F 2 max E Q [ w(X, Y ) 2 ] 8 3 d log 2N e d + log 4 δ N . (14)
Let us now expand the left-hand side of ( 14):

E Q w(X, Y )| h(X) -Y | 2 = E µ E q w(X, Y ) h 2 (X) + Y 2 -2 h(X)Y | X = E µ h 2 (X)E q [ w(X, Y ) | X] + E q [ w(X, Y )Y 2 | X] -2 h(X)E q [ w(X, Y )Y | X] ±E 2 q [ w(X, Y )Y | X] ± h 2 (X) = E µ h(X) -E q [ w(X, Y )Y | X] 2 + h 2 (X)E q [ w(X, Y ) | X] + E q [ w(X, Y )Y 2 | X] -E 2 q [ w(X, Y )Y | X] -h 2 (X) = h -h 2 µ + E µ [ h 2 (X) (E q [ w(X, Y ) -1 | X])] + K, (15)
where

K = E µ [E q [ w(X, Y )Y 2 | X] -E 2 q [ w(X, Y )Y | X]] is a constant term (independent of h) and h(x) = E q [ w(x, Y )Y | x]
is the regression function weighted by w. Plugging this into (14) we get: (16)

h -h 2 µ + E µ [ h 2 (X) (E q [ w(X, Y ) -1 | X])] + K ≤ 1 N N i=1 w(x i , y i )| h(x i ) -y i | 2 + 2 13/4 F 2 max E Q [ w(X, Y )]
Consider now the hypothesis h 0 ∈ H such that h 0 = argmin f ∈H fh 2 µ . Since h 0 is in H and h was defined as the hypothesis minimizing the empirical weighted loss, we have:

1 N N i=1 w(x i , y i )| h(x i ) -y i | 2 ≤ 1 N N i=1 w(x i , y i )|h 0 (x i ) -y i | 2 . ( 17
)
Similarly to what we did for h, we can bound the empirical error of h 0 . According to Corollary 1 of [START_REF] Cortes | Learning bounds for importance weighting[END_REF], we have that for any δ > 0, with probability at least 1δ:

1 N N i=1 w(x i , y i )|h 0 (x i ) -y i | 2 ≤ E Q [ w(X, Y )|h 0 (X) -Y | 2 ] + 2 13/4 F 2 max E D [ w(X, Y )] 8 3 d log 2N e d + log 4 δ N . (18)
By adopting (15) to expand the expected error of h 0 , we obtain: (

1 N N i=1 w(x i , y i )|h 0 (x i ) -y i | 2 ≤ inf f ∈H f -h 2 µ + E µ [h 2 0 (X) (E q [ w(X, Y ) -1 | X])] + K + 2 13/4 F 2 max E D [ w(X, Y )]
) 19
If we now put ( 16) and ( 19) together by means of ( 17), we get that, with probability at least 1 -2δ:

h -h 2 µ ≤ inf f ∈H f -h 2 µ + E µ [ h 2 0 (X) -h 2 (X) (E q [ w(X, Y ) -1 | X])] + 2 13/4 F 2 max E Q [ w(X, Y ) 2 ] + E D [ w(X, Y ) 2 ] 8 3 d log 2N e d + log 4 δ N ≤ inf f ∈H f -h 2 µ + F 2 max E µ [|E q [ w(X, Y ) | X] -1|] + 2 13/4 F 2 max E Q [ w(X, Y ) 2 ] + E D [ w(X, Y ) 2 ] 8 3 d log 2N e d + log 4 δ N = inf f ∈H f -h 2 µ + F 2 max g 1,µ + 2 13/4 F 2 max M ( w) d log 2N e d + log 4 δ N 3 8 . ( 20
)
By taking the square root of both sides of (20) and using i a i ≤ i √ a i for a i ≥ 0, we obtain:

h -h µ ≤ inf f ∈H f -h µ + F max g 1,µ + 2 13/8 F max M ( w) d log 2N e d + log 4 δ N 3 16 . ( 21
) Furthermore: inf f ∈H f -h µ ≤ inf f ∈H f -h µ + h -h µ . (22)
We can now bound the expected error of h with respect to h by:

h -h µ ≤ h -h µ + h -h µ . (23)
We already provided a bound on the first term, so let us analyze the second one. We have:

h -h 2 µ = E µ [| h(X) -h (X)| 2 ] = E µ [|E q [ w(X, Y )Y | X] -E p [Y | X]| 2 ] = E µ [|E q [ w(X, Y )Y | X] -E q [w(X, Y )Y | X]| 2 ] = E µ [|E q [Y ( w(X, Y ) -w(X, Y )) | X]| 2 ] ≤ E µ [E q [|Y | 2 | w(X, Y ) -w(X, Y )| 2 | X]] ≤ F 2 max E Q | w(X, Y ) -w(X, Y )| 2 = F 2 max w -w 2 Q . ( 24
)
where the first inequality is due to Jensen's inequality. Thus, hh µ ≤ F max ww Q . By combining ( 21), ( 22), (23), and (24), we have:

h -h µ ≤ h -h µ + h -h µ ≤ inf f ∈H f -h µ + F max g 1,µ + 2 13/8 F max M ( w) d log 2N e d + log 4 δ N 3 16 + h -h µ ≤ inf f ∈H f -h µ + F max g 1,µ + 2 13/8 F max M ( w) d log 2N e d + log 4 δ N 3 16 + 2 h -h µ ≤ inf f ∈H f -h µ + F max g 1,µ + 2 13/8 F max M ( w) d log 2N e d + log 4 δ N 3 16 + 2F max w -w Q which concludes the proof. Lemma 1. Let H ⊂ B(S × A, Q max ) be a functional space. Call g r (s, a) = E R S [ w r (r|s, a)] -1 and M ( w r ) = E φ R S [ w r (r|s, a) 2 ] + E D [ w r (r|s, a) 2 ], where φ R S (r|s, a) = µ(s, a)R s (r|s, a) and D is a dataset of N i.i.d. samples. Assume d = P dim({|f (s, a) -r| 2 : f ∈ H}) < ∞ and E φ R S [ w r (r|s, a) 2 ] < ∞.
Let R be as defined in (2). Then, for any δ > 0, with probability at least 1 -2δ:

||R -R|| µ ≤ inf f ∈H ||f -R|| µ + r max ||g r || 1,µ + 2 13/8 Q max M ( w r ) d log 2N e d + log 4 δ N 3 16 + 2r max || w r -w r || φ R S . (25)
Proof. The result follows straightforwardly by applying Theorem 2.

|| L * Q k -Q k+1 || µ ≤ inf f ∈H ||f -L * Q k || µ + Q max ||g p || 1,µ + 2 13/8 Q max M ( w p ) d log 2N e d + log 4 δ N 3 16 + 2Q max || w p -w p || φ P S . (26)
Proof. The result follows straightforwardly by applying Theorem 2.

Theorem 3. Let H ⊂ B(S × A, Q max ) be a hypothesis space, µ a distribution over S × A, (Q i ) k+1 i=0 a sequence of Q-functions as defined in Equation (4), and L * the optimal Bellman operator of the target task. Suppose to have a dataset of N i.i.d. samples D drawn from the source task M S according to a joint distribution φ S . Let w p , w r denote the ideal importance weights defined in (5) and (3), and w r (r|s, a), w p (s |s, a) denote arbitrary positive functions with bounded second moments. Define g r (s, a)

= E R S [ w r (r|s, a)|s, a] -1, M ( w r ) = E φ R S [ w r (r|s, a) 2 ] + E D [ w r (r|s, a) 2 ]
, where φ R S (r|s, a) = µ(s, a)R S (r|s, a). Similarly, define g p , M ( w p ), and φ P S (s |s, a) for the transition model. Then, for any δ > 0, with probability at least 1 -4δ:

L * Q k -Q k+1 µ ≤ Qmax gp 1,µ + 2rmax gr 1,µ + 2Qmax wp -wp φ P S + 4rmax wr -wr φ R S + inf f ∈H f -(L * ) k+1 Q0 µ + 2 inf f ∈H f -R µ + Qmax 2 -13 8 M ( wp) + 2 M ( wr) d log 2N e d + log 4 δ N 3 16 + k-1 i=0 (γCAE(µ)) i+1 k-i-1 µ,
where C AE is the concentrability coefficient of one-step transitions as defined in (Farahmand, 2011, Definition 5.2).

Proof. We can decompose the error at iteration k into:

k µ = L * Q k -Q k+1 µ ≤ L * Q k -L * Q k µ + L * Q k -Q k+1 µ = R -R µ + L * Q k -Q k+1 µ , (27)
where, for any pair (s, a), L * Q(s, a) := R(s, a) + S P T (ds |s, a) max a Q(s , a) is the optimal Bellman operator of the target task using the approximated reward function defined in (2). The two terms in ( 27) can be bounded straightforwardly by applying Lemma 1 and Lemma 2, respectively. The application of Lemma 2 to the second term gives rise to inf f ∈H f -L * Q k µ , which can be further bounded by noticing that:

inf f ∈H f -L * Q k µ ≤ inf f ∈H f -L * Q k µ + L * Q k -L * Q k µ . (28)
The second term in ( 28) is again R -R µ , while the first term has already been bounded in Theorem 5.3 of [START_REF] Farahmand | Regularization in reinforcement learning[END_REF]:

inf f ∈H f -L * Q k µ ≤ inf f ∈H f -(L * ) k+1 Q 0 µ + k-1 i=0 (γC AE (µ)) i+1 k-i-1 µ . (29)
Then, by combining the bounds from Lemma 1 and Lemma 2 with ( 28) and ( 29), we can write:

k µ ≤ R -R µ + L * Q k -Q k+1 µ ≤ R -R µ + inf f ∈H ||f -L * Q k || µ + Q max ||g
+ 2Q max || w p -w p || φ P S ≤ 2 R -R µ + inf f ∈H f -(L * ) k+1 Q 0 µ + k-1 i=0 (γC AE (µ)) i+1 k-i-1 µ + Q max ||g p || 1,

C. Additional Details on the Experiments

C.1. Puddle World

Our first experimental domain is a modified version of the puddle world environment presented in [START_REF] Sutton | Generalization in reinforcement learning: Successful examples using sparse coarse coding[END_REF]. Puddle world is a two-dimensional continuous grid with a goal area and some elliptical "puddles". The goal is to drive the agent from a starting position to the goal area while avoiding the puddles. The state-space is [0, 10] 2 , while the action-space is discrete and allows the agent to move in the four cardinal directions. At each time-step, the agent receives a reward of -1 plus a penalization proportional to the distance from all puddles: R(s, a) = -1 -100 u∈U W u (s), where U is the set of puddles and W u (s) is the weight of puddle u for state s. In the goal the reward is zero. In our experiments, we modeled W u (s) as a bivariate Gaussian. Each action moves the agent by α in the corresponding direction. In particular, we consider two versions of the environment: I) shared dynamics where α = 1 and II) puddle-based dynamics where puddles also slow-down the agent by: α = (1 + 5 u∈U W u (s )) -1 . Finally, a white Gaussian noise of σ 2 r = 0.01 and σ 2 p = 0.04 is added to the reward and the transition model, respectively. In our experiments we set γ = 0.99 and a maximum horizon of 50 time-steps. modeled by changing the respective weights α and β. The values for all tasks are reported in Table 1. Notice that there is no source task that is globally similar to the target: either some reward structure is shared or some transition structure is, never both. This makes transfer very challenging since samples have to be accurately selected to prevent detrimental consequences.

In this experiment, we run FQI using extra-trees for 80 iterations with 100 estimators and a minimum of 10 samples to split a node. GPs use the anisotropic squared exponential kernel. For each of the 6 source reservoirs, we gather 30 years of historical data where controls are applied by a human operator's policy. We learn the target task by collecting batches of 1 year, each using an -greedy policy ( = 0.3) on the previously learned Q-function. Evaluation is performed by averaging 10 trajectories of 1 year, each starting from January 1 st and with an initial storage of 200 M m 3 of water.

To better demonstrate the difficulty of this control problem, we run FQI for 500 episodes (equivalent to 500 years of interaction). Furthermore, to make the problem simpler, we allow the agent to sample the state-action space arbitrarily, so as to have a better exploration. The result is shown in Figure 6b. Although we significantly simplified the problem and we allowed FQI to gather an enormous amount of data, the algorithm still needs almost 500 years to achieve optimal performance. This demonstrates that solving this task by directly interacting with the real environment is clearly impractical. Thus, transfer of previous knowledge is, in this case, mandatory to achieve good performance.

Figure 1 .

 1 Figure 1. Puddle world with 20 × 3 episodes transferred from 3 source tasks in the case of shared dynamics (left) and puddle-based dynamics (right).

Figure 2 .

 2 Figure 2. Acrobot swing-up with (100 + 50) episodes transferred from 2 source tasks. (left) learning performance. (right) relative number of samples transferred from each source task.

Figure 3 .

 3 Figure 3. Water reservoir control. Average cost per day during the first 10 years of learning. IWFQI outperforms the expert and quickly achieves near-optimal performance.

  , a) ∼ N (µ GP j,d (s, a), σ 2 GP j,d (s, a)). Then, given a sample s, a, s from the j-th MDP, the importance weight for the transition model given by w = D d=1N s d p (0) d (s,a),δ 2 0,d (s,a) N s d p (j) d (s,a),δ 2 j,d (s,a)is distributed according to some distribution G induced by the GPs' predictions. LetC d = δ 2 j,d (s,a) δ 2 j,d (s,a)-σ 2 GP j,d(s,a) and supposeσ 2 GP j,d (s, a) < δ 2 j,d (s, a) for all d, then E G [w] = D d=1 C d N s d µ GP 0,d (s, a), δ 2 0,d (s, a) + σ 2 GP 0,d (s, a) N s d µ GP j,d (s, a), δ 2 j,d (s, a)σ 2 GP j,d (s, a) .(11)Proof. Notice that the density P j (•|s, a) decomposes into:P j (•|s, a) (s, a), δ 2 j,d (s, a) .

Lemma 2 .

 2 Let H ⊂ B(S × A, Q max ) be a functional space. Call g p (s, a) = E P S [ w p (s |s, a)] -1 and M ( w p ) = E φ P S [ w p (s |s, a) 2 ] + E D [ w p (s |s, a) 2 ], where φ P S (r|s, a) = µ(s, a)P s (r|s, a) and D is a dataset of N i.i.d. samples. Assume d = P dim({|f (s, a) -r| 2 : f ∈ H}) < ∞ and E φ P S [ w p (s |s, a) 2 ] < ∞. Let Q k+1 be as defined in (4) and denote L * Q(s, a) := R(s, a) + S P T (ds |s, a) max a Q(s , a). Then, for any δ > 0, with probability at least 1 -2δ:

+

  µ + 2 13/8 Q max M ( w p ) d log 2N e d 2Q max || w pw p || φ P S ≤ Q max g p 1,µ + 2r max g r 1,µ + 2Q max w pw p φ P S + 4r max w rw r φ M ( w p ) + 2 M ( w r ) d log 2N e d AE (µ)) i+1 k-i-1 µ ,where we recall that g p (s, a)= E P S [ w p (s |s, a)|s, a] -1, M ( w p ) = E φ P S [ w p (s |s, a) 2 ] + E D [ w p (s |s, a) 2 ], and φ P S (s |s, a) = µ(s, a)P S (s |s, a). This concludes the proof.

Figure 5 .

 5 Figure 5. Transfer of samples from the constant-spin task to the swing-up task. (a) discounted expected reward and (b) number of steps before reaching a goal state.

Figure 6 .

 6 Figure 6. Water reservoir control. (a) Inflow profiles for all tasks. (b) Learning without transfer for 500 years.

  p || 1,µ + 2 13/8 Q max M ( w p ) d log 2N e d + log 4

	3
	16
	δ
	N

Table 1 .

 1 Reward parameters for the different water reservoirs.

	Parameter Target Source 1 Source 2 Source 3 Source 4 Source 5 Source 6
	α	0.3	0.8	0.35	0.7	0.4	0.6	0.45
	β	0.7	0.2	0.65	0.3	0.6	0.4	0.55

Politecnico di Milano, Milan, Italy

SequeL Team, IN-RIA Lille, France. Correspondence to: Andrea Tirinzoni <andrea.tirinzoni@polimi.it>.Proceedings of

the 35 th International Conference on Machine Learning, Stockholm, Sweden, PMLR 80, 2018. Copyright 2018 by the author(s).

This assumption can be relaxed at the price of a much more complex theoretical analysis.

Differently from other works (e.g.,[START_REF] Farahmand | Value pursuit iteration[END_REF][START_REF] Tosatto | Boosted fitted q-iteration[END_REF], we suppose, for the sake of simplicity, the hypothesis space to be bounded by Qmax. Although this is a strong assumption, it can be relaxed by considering truncated functions. We refer the reader to[START_REF] Györfi | A distribution-free theory of nonparametric regression[END_REF] for the theoretical consequences of such relaxation.

Acknowledgments

This research was supported in part by French Ministry of Higher Education and Research, Nord-Pas-de-Calais Regional Council and French National Research Agency (ANR) under project ExTra-Learn (n.ANR-14-CE24-0010-01).

We provide additional details on the puddle world experiments. The target task and the three source tasks can be seen in Figure 4. Notice that the optimal paths to solve each task have at least a small overlapping, thus allowing some knowledge transfer. However, the optimal policy for one task is likely to cross a puddle if carelessly used in another domain. This makes the transfer problem more challenging since the algorithm has to figure out which samples should be retained and which should be discarded.

In both experiments, 20 episodes were generated beforehand from each source task. For IWFQI, a Gaussian process was fitted on each of the three source datasets using the squared exponential kernel. The noises of the reward and transition models were estimated as 10 times their true value. In each algorithm, FQI was run for 50 iterations using Extra-Trees with 50 estimators and a minimum of 2 samples to split a node. Results were averaged over 20 independent runs.

C.2. Acrobot

We provide a precise description of the two tasks used in the Acrobot experiment. For both tasks, the state-space is composed of the two link angles (θ 1 , θ 2 ) and their velocities ( θ1 , θ2 ). The transition dynamics are the ones described in [START_REF] Sutton | Reinforcement learning: An introduction[END_REF]. The agent can only apply a torque of +2 or -2 to the joint between the two links. The initial state is (θ 1 , 0, 0, 0), where θ 1 ∼ U(-2, 2). Performance is evaluated starting from multiple states (θ 1 , 0, 0, 0), with θ 1 evenly spaced in [-2, 2]. The swing-up task has reward:

and terminates whenever -cos(θ 1 )cos(θ 1 + θ 2 ) > 1 or 100 time-steps are reached. The constant-spin task has reward:

and terminates whenever 100 time-steps are reached.

We collect 100 episodes from the first source task (corresponding to 3400 samples) and 50 episodes from the second source task (corresponding to 5000 samples). For all algorithms, FQI uses extra-trees with 50 estimators and a minimum of 20 samples to split a node. Data is collected in batches of 10 episodes using an -greedy policy ( = 0.1). For IWFQI, GPs use the squared exponential kernel with parameters estimated by maximum likelihood on the data.

To further demonstrate the advantages of our approach, we show what happens when only the constant-spin source task is available. Clearly, most of the reward samples should be discarded, and conversely for the transition samples. As we can see from Figure 5a and 5b, RBT now performs significantly worse than FQI. This is due to the fact that, by transferring samples jointly, it cannot avoid introducing bias. Our approach, on the other hand, is able to discard the reward samples, thus being robust to negative transfer. Furthermore, it achieves a little improvement over FQI due to the few samples transferred.

C.3. Water Reservoir Control

All tasks used in this experiment are modeled according to the dynamics described in the paper. For the sake of simplicity, each water reservoir is supposed to have capacity of 500 M m 3 , minimum storage of 50 M m 3 , flooding threshold of 300 M m 3 , and per-day demand of 10 M m 3 . Due to the different geographic locations, each task has different inflow function i j (t) = īj (t) + N (0, σ 2 p ), where σ 2 p = 2.0 is the fixed noise variance. The different mean-inflow functions are shown in Figure 6a. Furthermore, each water reservoir weighs the flooding and demand objectives differently. This is