Alessandro Lazaric
email: alessandro.lazaric@inria.fr

Marcello Restelli
email: restelli@elet.polimi.it

Transfer from Multiple MDPs

Transfer reinforcement learning (RL) methods leverage on the experience collected on a set of source tasks to speed-up RL algorithms. A simple and effective approach is to transfer samples from source tasks and include them in the training set used to solve a target task. In this paper, we investigate the theoretical properties of this transfer method and we introduce novel algorithms adapting the transfer process on the basis of the similarity between source and target tasks. Finally, we report illustrative experimental results in a continuous chain problem.

Introduction

The objective of transfer in reinforcement learning (RL) [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF] is to speed-up RL algorithms by reusing knowledge (e.g., samples, value function, features, parameters) obtained from a set of source tasks. The underlying assumption of transfer methods is that the source tasks (or a suitable combination of these) are somehow similar to the target task, so that the transferred knowledge can be useful in learning its solution. A wide range of scenarios and methods for transfer in RL have been studied in the last decade (see [START_REF] Taylor | Transfer learning for reinforcement learning domains: A survey[END_REF][START_REF] Lazaric | Knowledge Transfer in Reinforcement Learning[END_REF] for a thorough survey). In this paper, we focus on the simple transfer approach where trajectory samples are transferred from source MDPs to increase the size of the training set used to solve the target MDP. This approach is particularly suited in problems (e.g., robotics, applications involving human interaction) where it is not possible to interact with the environment long enough to collect samples to solve the task at hand. If samples are available from other sources (e.g., simulators in case of robotic applications), the solution of the target task can benefit from a larger training set that includes also some source samples. This approach has been already investigated in the case of transfer between tasks with different state-action spaces in [START_REF] Taylor | Transferring instances for model-based reinforcement learning[END_REF], where the source samples are used to build a model of the target task whenever the number of target samples is not large enough. A more sophisticated sample-transfer method is proposed in [START_REF] Lazaric | Transfer of samples in batch reinforcement learning[END_REF]. The authors introduce an algorithm which estimates the similarity between source and target tasks and selectively transfers from the source tasks which are more likely to provide samples similar to those generated by the target MDP. Although the empirical results are encouraging, the proposed method is based on heuristic measures and no theoretical analysis of its performance is provided. On the other hand, in supervised learning a number of theoretical works investigated the effectiveness of transfer in reducing the sample complexity of the learning process. In domain adaptation, a solution learned on a source task is transferred to a target task and its performance depends on how similar the two tasks are. In [START_REF] Ben-David | A theory of learning from different domains[END_REF] and [START_REF] Mansour | Domain adaptation: Learning bounds and algorithms[END_REF] different distance measures are proposed and are shown to be connected to the performance of the transferred solution. The case of transfer of samples from multiple source tasks is studied in [START_REF] Crammer | Learning from multiple sources[END_REF]. The most interesting finding is that the transfer performance benefits from using a larger training set at the cost of an additional error due to the average distance between source and target tasks. This implies the existence of a transfer tradeoff between transferring as many samples as possible and limiting the transfer to sources which are similar to the target task. As a result, the transfer of samples is expected to outperform single-task learning whenever negative transfer (i.e., transfer from source tasks far from the target task) is limited w.r.t. to the advantage of increasing the size of the training set. This also opens the question whether it is possible to design methods able to automatically detect the similarity between tasks and adapt the transfer process accordingly.

In this paper, we investigate the transfer of samples in RL from a more theoretical perspective w.r.t. previous works. The main contributions of this paper can be summarized as follows:

• Algorithmic contribution. We introduce three sample-transfer algorithms based on fitted Qiteration [START_REF] Ernst | Tree-based batch mode reinforcement learning[END_REF]. The first algorithm (AST in Section 3) simply transfers all the source samples. We also design two adaptive methods (BAT and BTT in Section 4 and 5) whose objective is to solve the transfer tradeoff by identifying the best combination of source tasks. • Theoretical contribution. We formalize the setting of transfer of samples and we derive a finite-sample analysis of AST which highlights the importance of the average MDP obtained by the combination of the source tasks. We also report the analysis for BAT which shows both the advantage of identifying the best combination of source tasks and the additional cost in terms of auxiliary samples needed to compute the similarity between tasks. • Empirical contribution. We report results (in Section 6) on a simple chain problem which confirm the main theoretical findings and support the idea that sample transfer can significantly speed-up the learning process and that adaptive methods are able to solve the transfer tradeoff and avoid negative transfer effects.

The rest of the paper is organized as follows. In Section 2 we introduce the notation and we define the transfer problem. Section 3 reports the theoretical analysis of AST. BAT is described in Section 4 along with its theoretical analysis. A more challenging setting is introduced in Section 5 together with BTT. Section 6 reports the experimental results and Section 7 concludes the paper. Finally, in the appendix we report the proofs and some additional experimental analysis.

Preliminaries

In this section we introduce the notation and the transfer problem considered in the rest of the paper.

Notation for MDPs.

We define a discounted Markov decision process (MDP) as a tuple M = X , A, R, P, γ where the state space X is a bounded closed subset of the Euclidean space, A is a finite (|A| < ∞) action space, the deterministic1 reward function R : X × A → R is uniformly bounded by R max , the transition kernel P is such that for all x ∈ X and a ∈ A, P(•|x, a) is a distribution over X , and γ ∈ (0, 1) is a discount factor. We denote by S(X × A) the set of probability measures over X × A and by B(X × A; V max = Rmax 1-γ ) the space of bounded measurable functions with domain X × A and bounded in [-V max , V max ]. We define the optimal action-value function Q * as the unique fixed-point of the optimal Bellman operator T : B(X × A; V max ) → B(X × A; V max ) defined by

(T Q)(x, a) = R(x, a) + γ X max a ′ ∈A Q(y, a ′ )P(dy|x, a).
Notation for function spaces. For any measure µ ∈ S(X × A) obtained from the combination of a distribution ρ ∈ S(X ) and a uniform distribution over the discrete set A, and a measurable function f :

X × A → R, we define the L 2 (µ)-norm of f as ||f || 2 µ = 1 |A| a∈A X f (x, a) 2 ρ(dx). The supremum norm of f is defined as ||f || ∞ = sup x∈X |f (x)|. Finally, we define the standard L 2 -norm for a vector α ∈ R d as ||α|| 2 = d i=1 α 2 i . We denote by φ(•, •) = ϕ 1 (•, •), . . . , ϕ d (•, •) ⊤ a feature vector with features ϕ i : X × A → [-C, C],
and by F = {f α (•, •) = φ(•, •) ⊤ α} the linear space of action-value functions spanned by the basis functions in φ. Given a set of state-action pairs

{(X l , A l )} L l=1 , let Φ = [φ(X 1 , A 1 ) ⊤ ; . . . ; φ(X L , A L ) ⊤
] be the corresponding feature matrix. We define the orthogonal projection operator Π : Problem setup. We consider the transfer problem in which M tasks {M m } M m=1 are available and the objective is to learn the solution for the target task M 1 transferring samples from the source tasks {M m } M m=2 . We define an assumption on how the training sets are generated. Definition 1. (Random Tasks Design) An input set {(X l , A l )} L l=1 is built with samples drawn from an arbitrary sampling distribution µ ∈ S(X × A), i.e. (X l , A l ) ∼ µ. For each task m, one transition and reward sample is generated in each of the state-action pairs in the input set, i.e. Y m l ∼ P(•|X l , A l ), and R m l = R(X l , A l ). Finally, we define the random sequence {M l } L l=1 where the indexes M l are drawn i.i.d. from a multinomial distribution with parameters (λ 1 , . . . , λ M ). The training set available to the learner is

B(X × A; V max ) → F as ΠQ = arg min f ∈F ||Q - f || µ . Finally, by T (Q) we denote the truncation of a function Q in the range [-V max , V max ]. Input: Linear space F = span{ϕi, 1 ≤ i ≤ d}, initial function Q 0 ∈ F for k = 1, 2, . . . do Build the training set {(X l , A l , Y l , R l )} L l=1 [according to random tasks design] Build the feature matrix Φ = [φ(X1, A1) ⊤ ; . . . ; φ(XL, AL) ⊤ ] Compute the vector p ∈ R L with p l = R l + γ max a ′ ∈A Q k-1 (Y l , a ′ ) Compute the projection αk = (Φ ⊤ Φ) -1 Φ ⊤ p and the function Q k = f αk Return the truncated function Q k = T ( Q k ) end for
{(X l , A l , Y l , R l )} L l=1 where Y l = Y l,M l and R l = R l,M l .
This is an assumption on how the samples are generated but in practice, a single realization of samples and task indexes M l is available. We consider the case in which λ 1 ≪ λ m (m = 2, . . . , M ). This condition implies that (on average) the number of target samples is much less than the source samples and it is usually not enough to learn an accurate solution for the target task. We will also consider the pure transfer case in which λ 1 = 0 (i.e., no target sample is available). Finally, we notice that Def. 1 implies the existence of a generative model for all the MDPs, since the stateaction pairs are generated according to an arbitrary sampling distribution µ.

All-Sample Transfer Algorithm

We first consider the case when the source samples are generated beforehand according to Def. 1 and the designer has no access to the source tasks. We study the algorithm called All-Sample Transfer (AST) (Fig. 1) which simply runs FQI with a linear space F on the whole training set {(X l , A l , Y l , R l )} L l=1 . At each iteration k, given the result of the previous iteration Q k-1 = T ( Q k-1 ), the algorithm returns

Q k = arg min f ∈F 1 L L l=1 f (X l , A l ) -(R l + γ max a ′ ∈A Q k-1 (Y l , a ′ )) 2 .
(1)

In the case of linear spaces, the minimization problem is solved in closed form as in Fig. 1. In the following we report a finite-sample analysis of the performance of AST. Similar to [START_REF] Munos | Finite time bounds for fitted value iteration[END_REF], we first study the prediction error in each iteration and we then propagate it through iterations.

Single Iteration Finite-Sample Analysis

We define the average MDP M λ as the average of the M MDPs at hand. We define its reward function R λ and its transition kernel P λ as the weighted average of reward functions and transition kernels of the basic MDPs with weights determined by the proportions λ of the multinomial distribution in the definition of the random tasks design (i.e., R λ = M m=1 λ m R m , P λ = M m=1 λ m P m ). The resulting average Bellman operator is

(T λ Q)(x, a) = M m=1 λ m T m Q (x, a) = R(x, a) + γ X max a ′ Q(y, a ′ )P(dy|x, a). (2)
In the random tasks design, the average MDP plays a crucial role since the implicit target function of the minimization of the empirical loss in Eq. 1 is indeed T λ Q k-1 . At each iteration k, we prove the following performance bound for AST. Theorem 1. Let M be the number of tasks {M m } M m=1 , with M 1 the target task. Let the training set {(X l , A l , Y l , R l )} L l=1 be generated as in Def. 1, with a proportion vector λ = (λ 1 , . . . , λ M ). Let

f α k * = ΠT 1 Q k-1 = arg inf f ∈F ||f -T 1 Q k-1 || µ , then for any 0 < δ ≤ 1, Q k (Eq. 1) satisfies ||T ( Q k ) -T 1 Q k-1 || µ ≤ 4||f α k * -T 1 Q k-1 || µ + 5 E λ ( Q k-1 ) + 24(V max + C||α k * ||) 2 L log 9 δ + 32V max 2 L log 27(12Le 2 ) 2(d+1) δ .
with probability 1 -δ (w.r.t. samples), where

||ϕ i || ∞ ≤ C and E λ ( Q k-1 ) = (T 1 -T λ ) Q k-1 2 µ .
Remark 1 (Analysis of the bound). We first notice that the previous bound reduces (up to constants) to the standard bound for FQI when M = 1 (see Section B). The bound is composed by three main terms: (i) approximation error, (ii) estimation error, and (iii) transfer error. The approximation

error ||f α k * -T 1 Q k-1
|| µ is the smallest error of functions in F in approximating the target function T 1 Q k-1 and it is independent from the transfer algorithm. The estimation error (third and fourth terms in the bound) is due to the finite random samples used to learn Q k and it depends on the dimensionality d of the function space and it decreases with the total number of samples L with the fast rate of linear spaces (O(d/L) instead of O( d/L)). Finally, the transfer error E λ accounts for the difference between source and target tasks. In fact, samples from source tasks different from the target might bias Q k towards a wrong solution, thus resulting in a poor approximation of the target function T 1 Q k-1 . It is interesting to notice that the transfer error depends on the difference between the target task and the average MDP M λ obtained by taking a linear combination of the source tasks weighted by the parameters λ. This means that even when each of the source tasks is very different from the target, if there exists a suitable combination which is similar to the target task, then the transfer process is still likely to be effective. Furthermore, E λ considers the difference in the result of the application of the two Bellman operators to a given function Q k-1 . As a result, when the two operators T 1 and T λ have the same reward functions, even if the transition distributions are different (e.g., the total variation ||P 1 (•|x, a) -P λ (•|x, a)|| TV is large), their corresponding averages of Q k-1 might still be similar (i.e., max a ′ Q(y, a ′ )P 1 (dy|x, a) similar to max a ′ Q(y, a ′ )P λ (dy|x, a)).

Remark 2 (Comparison to single-task learning). Let Q k

s be the solution obtained by solving one iteration of FQI with only samples from the source task, the performance bounds of Q k and Q k s can be written as (up to constants and logarithmic factors)

T ( Q k ) -T 1 Q k-1 µ ≤ ||f α k * -T 1 Q k-1 || µ + (V max + C||α k * ||) 1 L + V max d L + E λ , T ( Q k s ) -T 1 Q k-1 µ ≤ ||f α k * -T 1 Q k-1 || µ + (V max + C||α k * ||) 1 N 1 + V max d N 1 ,
with N 1 = λ 1 L (on average). Both bounds share exactly the same approximation error. The main difference is that Q k s uses only N 1 samples and, as a result, has a much bigger estimation error than Q k , which takes advantage of all the L samples transferred from the source tasks. At the same time, Q k suffers from an additional transfer error which does not exist in the case of Q k s . Thus, we can conclude that AST is expected to perform better than single-task learning whenever the advantage of using more samples is greater than the bias due to samples coming from tasks different from the target task. This introduces a transfer tradeoff between including many source samples, so as to reduce the estimation error, and finding source tasks whose combination leads to a small transfer error. In Section 4 we show how it is possible to define an adaptive transfer algorithm which selects proportions λ so as to keep the transfer error E λ as small as possible. Finally, in Section 5 we consider a different setting where the maximum number of samples in each source is fixed.

Propagation Finite-Sample Analysis

We now study how the previous error is propagated through iterations. Let ν be the evaluation norm (i.e., in general different from the sampling distribution µ). We first report two assumptions.2 Assumption 1. [START_REF] Munos | Finite time bounds for fitted value iteration[END_REF] Given µ, ν, p ≥ 1, and an arbitrary sequence of policies {π p } p≥1 , we assume that the future-state distribution µP

1 π1 • • • P 1 πp is absolutely continuous w.r.t. ν. We assume that c(p) = sup π1•••πp ||d(µP 1 π1 • • • P 1 πp )/ν|| ∞ satisfies C µ,ν = (1 -γ 2 ) 2 p pγ p-1 c(p) < ∞.
We also need the features ϕ i to be linearly independent w.r.t. µ.

Assumption 2. Let G ∈ R d×d be the Gram matrix with [G] ij = ϕ i (x, a)ϕ j (x, a)µ(dx, a)
. We assume that its smallest eigenvalue ω is strictly positive (i.e., ω > 0).

Using the two previous assumptions we derive the following performance bound for AST.

Theorem 2. Let Assumptions 1 and 2 hold and the setting be as in Theorem 1. After K iterations, AST returns an action-value function Q K , whose corresponding greedy policy π K satisfies

||Q * -Q πK || ν ≤ 2γ (1 -γ) 3/2 C µ,ν 4 sup g∈F inf f ∈F ||f -T 1 g|| µ + 5 sup α (T 1 -T λ )T (f α ) µ + 56(V max + V max √ ω ) 2 L log 9K δ + 32V max 2 L log 27K(12Le 2 ) 2(d+1) δ + 2V max C µ,ν γ K .

Remark (Analysis of the bound).

The bound reported in the previous theorem displays few differences w.r.t. to the single-iteration bound. The additional term O(γ K ) accounts for the error due to the finite number of iterations of FQI and it decreases exponentially with base γ. The approximation error is now sup g inf f ||f -T 1 g|| µ . This term is referred to as the inherent Bellman error [START_REF] Munos | Finite time bounds for fitted value iteration[END_REF] of the space F and it is related to how well the Bellman images of functions in F can be approximated by F itself. It is possible to show that for particular classes of MDPs (e.g., Lipschitz), if a large enough number of carefully designed features is available, then this term is small. In the estimation error, the norm ||α k * || is bounded using the linear independency between features (Assumption 2) and the boundedness of the functions Q k returned at each iteration. The resulting term has an inverse dependency on the smallest eigenvalue ω which tends to be small whenever the Gram matrix is not well-defined (i.e., the features are almost linearly dependent). The transfer error sup α (T 1 -T λ )T (f α ) µ characterizes the difference between the target and average Bellman operators through the space F . As a result, even MDPs with significantly different rewards and transitions might have a small transfer error because of the functions in F . This introduces a tradeoff in the design of F between a "large" enough space containing functions able to approximate T 1 Q (i.e., small approximation error) and a small function space where the Q-functions induced by T 1 and T λ can be closer (i.e., small transfer error). This term also displays interesting similarities with the notion of discrepancy introduced in [START_REF] Mansour | Domain adaptation: Learning bounds and algorithms[END_REF] in domain adaptation.

Best Average Transfer Algorithm

As discussed in the previous section, the transfer error E λ plays a crucial role in the comparison with single-task learning. In particular, E λ is related to the proportions λ inducing the average Bellman operator T λ which defines the target function approximated at each iteration. We now consider the case where the designer has direct access to the source tasks (i.e., it is possible to choose how many samples to draw from each source) and can define an arbitrary proportion λ. In particular, we propose a method that adapts λ at each iteration so as to minimize the transfer error E λ . We consider the case in which L is fixed as a parameter of the algorithm and λ 1 = 0 (i.e., no target samples are used in the learning training set). At each iteration k, we need to estimate the quantity E λ ( Q k-1 ). We assume that for each task additional samples available. Let {(X s , A s , R s,1 , . . . , R s,M )} S s=1 be an auxiliary training set where (X s , A s ) ∼ µ and R s,m =

Input: Space F = span{ϕi, 1 ≤ i ≤ d}, initial function Q 0 ∈ F,
E λ ( Q k-1 )
Run one iteration of AST (Fig. 1) using L samples generated according to λ k end for R m (X s , A s ). In each state-action pair, we generate T next states for each task, that is Y t s,m ∼ P m (•|X s , A s ) with t = 1, . . . , T . Thus, for any function Q we define the estimated transfer error as

E λ (Q) = 1 S S s=1
Rs,1 -

M m=2 λmRs,m + γ T T t=1 max a ′ Q(Y t s,1 , a ′ )- M m=2 λm max a ′ Q(Y t s,m , a ′ ) 2 . (3)
At each iteration, the algorithm Best Average Transfer (BAT) (Fig. 2) first computes

λ k = arg min λ∈Λ E λ ( Q k-1
), where Λ is the (M -2)-dimensional simplex, and then runs an iteration of AST with samples generated according to the proportions λ k . We denote by λ k * the best combination at iteration k, that is

λ k * = arg min λ∈Λ E λ ( Q k-1 ) = arg min λ∈Λ E µ M m=2 λ m (T m Q k-1 )(x, a) -(T 1 Q k-1 )(x, a) 2 . (4)
The following performance guarantee can be proved for BAT.

Lemma 1. Let {(X s , A s , R 1 s , . . . , R M s )} S s=1 be a training set where (X s , A s )
iid ∼ µ and R m s = R m (X s , A s ) and for each state-action pair and for each task m, T next states Y m s,t ∼ P m (•|X s , A s ) with t = 1, . . . , T are available. For any fixed bounded function Q ∈ B(X × A; V max ), the λ returned by minimizing Eq. 3 is such that

E λ (Q) -E λ * (Q) ≤ 2V max (M -2) log 4S/δ S + 16V 2 max log 4SM/δ T ( 5
)
with probability 1 -δ.

From the previous lemma the approximation performance of BAT at each iteration follows.

Theorem 3. Let Q k-1 be the function returned at the previous iteration and Q k BAT the function returned by the BAT algorithm (Fig. 2). Then for any 0

< δ ≤ 1, Q k BAT satisfies ||T ( Q k BAT ) -T 1 Q k-1 || µ ≤ 4||f α k * -T 1 Q k-1 || µ + 5 E λ k * ( Q k-1 ) + 5 2V max (M -2) log 8S/δ S 1/4 + 20V max log 8SM/δ T + 24(V max + C||α k * ||) 2 L log 18 δ + 32V max 2 L log 54(12Le 2 ) 2(d+1) δ .
with probability 1 -δ.

Remark 1 (Comparison with AST and single-task learning).

The analysis of the bound shows that BAT outperforms AST whenever the advantage in achieving the smallest possible transfer error E λ k * is larger than the additional estimation error due to the auxiliary training set. It is also interesting to compare BAT to single-task learning. In fact, BAT performs better than single-task learning whenever the best possible combination of source tasks has a small transfer error and the additional estimation error related to the auxiliary training set is smaller than the estimation error in singletask learning. In particular, this means that O((M/S) 1/4 ) + O((1/T ) 1/2 ) should be smaller than O((d/N ) 1/2 ) (with N the number of target samples). The number of calls to the generative model for BAT is ST . In order to have a fair comparison with single-task learning we set S = N 2/3 and T = N 1/3 , then we obtain the condition M ≤ d 2 N -4/3 that constrains the number of tasks to be smaller than the dimensionality of the function space F . We remark that the dependency of the auxiliary estimation error on M is due to the fact that the λ vectors (over which the transfer error is optimized) belong to the simplex Λ of dimensionality M -2. Hence, the previous condition suggests that, in general, adaptive transfer methods may significantly improve the transfer performance (i.e., in this case a smaller transfer error) at the cost of additional sources of errors which depend on the dimensionality of the search space used to adapt the transfer process (i.e., in this case Λ).

Remark 2 (Iterations).

BAT recomputes the proportions λ k at each iteration k. In fact a combination λ 1 approximating well the reward function R 1 at the first iteration (i.e., R 1 ≈ R λ 1 ) does not necessarily have a small transfer error ||(T 1 -T λ 1 ) Q 1 || µ at the second iteration. We further investigate how the best source combination changes through iterations in the experiments of Section 6.

Remark 3 (Best source combination).

The previous theorem shows that BAT achieves the smallest transfer error

E λ k * ( Q k-1
) at the cost of an additional estimation error which scales with the size of the auxiliary training set as O((M/S) 1/4 )+O((1/T ) 1/2 ). We notice that the first term of the estimation error depends on how well the µ is approximated by using a finite number S of state-action pairs and it has a slower rate w.r.t. the other terms. The second term depends on the number of next states T simulated at each state-action pair which are used to estimate the value of the Bellman operators. As a result, in order to reduce the estimation error we need to increase both S and the number of next states T in each state-action pair. It is interesting to notice that similar estimation errors appear in FVI [START_REF] Munos | Finite time bounds for fitted value iteration[END_REF] where the optimal Bellman operator is approximated by Monte-Carlo estimation.

Remark 4 (Training set).

The implicit assumption in the definition of the auxiliary training set is that it is possible to generate a series of next states and rewards for all the tasks at the same stateaction pairs. If the source training sets are fixed in advance and the designer has no access to the source tasks, then this assumption is not verified and it is not possible to test the similarity between the MDP M and the target task. Nonetheless, if the generative model for the source tasks is available at learning time, the auxiliary training set could be generated before the learning phase actually begins. Furthermore, in the theoretical analysis, BAT does not use the samples in the auxiliary training set at learning time. A trivial improvement is to include the auxiliary samples to the training set.

Remark 5 (Comparison to other transfer methods).

In [START_REF] Lazaric | Transfer of samples in batch reinforcement learning[END_REF] a method to compute the similarity between MDPs is proposed. In particular, the authors introduce the definition of compliance as the average probability of the target samples to be generated from an sample-based estimation of the source MDPs. The compliance is later used to determine the proportion of samples to be transferred from each of the source tasks. Although this algorithm shares a similar objective as BAT, they use different notions of similarity. In particular, the method in [START_REF] Lazaric | Transfer of samples in batch reinforcement learning[END_REF] tries to identify source tasks which are individually similar to the target task, while the transfer error minimized in BAT considers the average MDP obtained by the transfer process. Furthermore, the notion of compliance tries to measures the overall distance between two MDPs, while E λ (Q) always measures the distance of the images of a function Q through two different Bellman operators.

Remark 6 (Computational complexity). Finally, we notice that the minimization of E λ is a convex quadratic problem since the objective function is convex in λ and λ belongs to the (M -2)dimensional simplex.

Best Transfer Trade-off Algorithm

The previous algorithm is proved to successfully estimate the combination of source tasks which better approximates the Bellman operator of the target task. Nonetheless, BAT relies on the implicit

Input: Linear space F = span{ϕi, 1 ≤ i ≤ d}, initial function Q 0 ∈ F,
for k = 1, 2, . . . do Compute β = arg min β∈[0,1] M E β + c d M m=1 βmNm
Run one iteration of AST (Fig. 1) using L samples generated according to β end for assumption that L samples can always be generated from any source task 3 and it cannot be applied to the case where the number of source samples is limited. Here we consider the more challenging case where the designer has still access to the source tasks but only a limited number of samples is available in each of them. In this case, an adaptive transfer algorithm should solve a tradeoff between selecting as many samples as possible, so as to reduce the estimation error, and choosing the proportion of source samples properly, so as to control the transfer error. The solution of this tradeoff may return non-trivial results, where source tasks similar to the target task but with few samples are removed in favor of a pool of tasks whose average roughly approximate the target task but can provide a larger number of samples.

Here we introduce the Best Tradeoff Transfer (BTT) algorithm (see Figure 3). Similar to BAT, it relies on an auxiliary training set to solve the tradeoff. We denote by N m the maximum number of samples available for source task m. Let β ∈ [0, 1] M be a weight vector, where β m is the fraction of samples from task m used in the transfer process. We denote by E β ( E β ) the transfer error (the estimated transfer error) with proportions λ where

λ m = (β m N m )/ m ′ (β m ′ N m ′ ).
At each iteration k, BTT returns the vector β which optimizes the tradeoff between estimation and transfer errors, that is

βk = arg min β∈[0,1] M E β ( Q k-1 ) + τ d M m=1 β m N m , ( 6
)
where τ is a parameter. While the first term accounts for the transfer error induced by β, the second term is the estimation error due to the total amount of samples used by the algorithm.

Unlike AST and BAT, BTT is a heuristic algorithm motivated by the performance bound in Theorem 1 and we do not provide any theoretical guarantee about its performance. The main technical difficulty w.r.t. the previous algorithms is that the setting considered here does not match the random task design assumption (see Def. 1) since the number of source samples is constrained by N m . As a result, given a proportion vector λ, we cannot assume samples to be drawn at random according to a multinomial of parameters λ. Without this assumption, it is an open question whether a similar bound to AST and BAT could be derived. Nonetheless, the experimental results reported in Section 6 show the effectiveness of BTT in solving the transfer tradeoff.

Experiments

In this section, we report and discuss preliminary experimental results of the transfer algorithms introduced in the previous sections. The main objective is to illustrate the functioning of the algorithms and compare their results with the theoretical findings. Thus, we focus on a simple problem and we leave more challenging problems for future work.

We consider a continuous extension of the 50-state variant of the chain walk problem proposed in [START_REF] Lagoudakis | Least-squares policy iteration[END_REF]. The state space is described by a continuous state variable x and two actions are available: one that moves toward left and the other toward right. With probability p each action makes a step of length l, affected by a noise η, in the intended direction, while with probability 1 -p it moves in the opposite direction. For the target task M 1 , the state-transition model is defined by the following parameters: p = 0.9, l = 1, and η is uniform in the interval [-0.1, 0.1]. The reward function provides +1 when the system state reaches the regions [-11, -9] and [START_REF] Lazaric | Knowledge Transfer in Reinforcement Learning[END_REF][START_REF] Munos | Finite time bounds for fitted value iteration[END_REF] and 0 elsewhere. Furthermore, to evaluate the performance of the transfer algorithms previously described, we considered eight source tasks {M 2 , . . . , M 9 } whose state-transition model parameters and reward functions are reported in Tab. 1 and 2. To approximate the Q-functions, we use a linear combination of 20 radial basis functions. In particular, for each action, we consider 9 Gaussians with means uniformly spread in the interval [-20, 20] and variance equal to 16, plus a constant feature. The number of iterations for the FQI algorithm has been empirically fixed to 13. Samples are collected through a sequence of episodes, each one starting from the state x 0 = 0 with actions chosen uniformly at random. For all the experiments, we average over 100 runs and we report standard deviation error bars.

We first consider the pure transfer problem where no target samples are actually used in the learning training set (i.e., λ 1 = 0). The objective is to study the impact of the transfer error due to the use of source samples and the effectiveness of BAT in finding a suitable combination of source tasks. The left plot in Fig. 4 compares the performances of FQI with and without the transfer of samples from the first four tasks listed in Tab. 1. In case of single-task learning, the number of target samples refers to the samples used at learning time, while for BAT it represents the size S of the auxiliary training set used to estimate the transfer error. Thus, while in single-task learning the performance increases with the target samples, in BAT they just make estimation of E λ more accurate. The number of source samples added to the auxiliary set for each target sample was empirically fixed to one (T = 1). We first run AST with L = 10000 and λ 2 = λ 3 = λ 4 = λ 5 = 0.25 (which on average corresponds to 2500 samples from each source). As it can be noticed by looking at the models in Tab. 1, this combination is very different from the target model and AST does not learn any good policy. On the other hand, even with a small set of auxiliary target samples, BAT is able to learn good policies. Such result is due to the existence of linear combinations of source tasks which closely approximate the target task M 1 at each iteration of FQI. An example of the proportion coefficients computed at each iteration of BAT is shown in the right plot in Fig. 4. At the first iteration, FQI produces an approximation of the reward function. Given the first four source tasks, BAT finds a combination (λ ≃ (0.2, 0.4, 0.2, 0.2)) that produces the same reward function as R 1 .

However, after a few FQI iterations, such combination is no more able to accurately approximate functions T 1 Q. In fact, the state-transition model of task M 2 is different from all the other ones (the step length is doubled). As a result, the coefficient λ 2 drops to zero, while a new combination among the other source tasks is found. Note that BAT significantly improves single-task learning, in particular when very few target samples are available.

In the general case, the target task cannot be obtained as any combination of the source tasks, as it happens by considering the second set of source tasks (M 6 , M 7 , M 8 , M 9 ). The impact of such situation on the learning performance of BAT is shown in the left plot in Fig. 5. Note that, when a few target samples are available, the transfer of samples from a combination of the source tasks using the BAT algorithm is still beneficial. On the other hand, the performance attainable by BAT is bounded by the transfer error corresponding to the best source task combination (which in this case is large). As a result, single-task FQI quickly achieves a better performance.

Results presented so far for the BAT transfer algorithm assume that FQI is trained only with the samples obtained through combinations of source tasks. Since a number of target samples is already available in the auxiliary training set, a trivial improvement is to include them in the training set together with the source samples (selected according to the proportions computed by BAT). As shown in the plot in the right side of Fig. 5 this leads to a significant improvement. From the behavior of BAT it is clear that with a small set of target samples, it is better to transfer as many samples as possible from source tasks, while as the number of target samples increases, it is preferable to reduce the number of samples obtained from a combination of source tasks that actually does not match the target task. In fact, for L = 10000, BAT has a much better performance at the beginning but it is then outperformed by single-task learning. On the other hand, for L = 1000 the initial advantage is small but the performance remains close to single-task FQI for large number of target samples. This experiment highlights the tradeoff between the need of samples to reduce the estimation error and the resulting transfer error when the target task cannot be expressed as a combination of source tasks (see Section 5). BTT algorithm provides a principled way to address such tradeoff, and, as shown by the right plot in Fig. 5, it exploits the advantage of transferring source samples when a few target samples are available, and it reduces the weight of the source tasks (so as to avoid large transfer errors) when samples from the target task are enough. It is interesting to notice that increasing the number of samples available for each source task from 5000 to 10000 improves the performance in the first part of the graph, while keeping unchanged the final performance. This is due to the capability of the BTT algorithm to avoid the transfer of source samples when there is no need for them, thus avoiding negative transfer effects.

Conclusions

In this paper, we formalized and studied the sample-transfer problem. We first derived a finitesample analysis of the performance of a simple transfer algorithm which includes all the source samples into the training set used to solve a given target task. At the best of our knowledge, this is the first theoretical result for a transfer algorithm in RL showing the potential benefit of transfer over single-task learning. Then, in the case when the designer has direct access to the source tasks, we introduced an adaptive algorithm which selects the proportion of source tasks so as to minimize the bias due to the use of source samples. Finally, we considered a more challenging setting where the number of samples available in each source task is limited and a tradeoff between the amount of transferred samples and the similarity between source and target tasks must be solved. For this setting, we proposed a principled adaptive algorithm. Finally, we report a detailed experimental analysis on a simple problem which confirms and supports the theoretical findings.

This work opens several directions for future work.

• Transfer with transformations. In many problems, there exist simple transformations to the source tasks dynamics and reward which would increase their similarity w.r.t. the target task, thus making the transfer process more effective. How affine transformations could be used in the adaptive transfer algorithms presented in this paper is an interesting direction for future work. In particular, it is an open question whether the cost (in terms of samples) of finding a suitable transformation would be effectively counter-balanced by transferring more similar samples. • Transfer between tasks with different state-action spaces. In many real applications source and target tasks might have a different number of state variables and different actions. Thus, the current work should be extended to the more general case of tasks with different stateaction spaces and it should be integrated with inter-task mapping transfer methods (see [START_REF] Taylor | Transfer learning for reinforcement learning domains: A survey[END_REF]). • Transfer with fixed tasks design. Definition 1 prescribes the process used to generate the training set used in learning the target task. At each state-action pair, the sample is generated from a source task chosen at random according to a multinomial distribution. When the designer has no access to the source tasks and their samples are generated beforehand, this generative model is not reasonable. A different model (fixed tasks design) should be defined where each sample is coming from a specific source which is fixed in advance. An interesting direction for future work is to understand how this different generative model affects the performance of the transfer algorithm and whether it is possible to define effective adaptive algorithms for this case. satisfies

||q -q|| N ≤ || Πq -q|| N + 4V max 2 N log 3(9N e 2 ) d+1 δ . (8)
Proof. We denote by u ∈ R N the orthogonal projection of the target vector q onto the vector space F N , that is u = Πq. By the definition of orthogonal projection and the Pythagorean theorem we decompose the error ||q -q|| N as

||q -q|| 2 N = ||q -u|| 2 N + ||u -q|| 2 N , (9)
where the first term represents the estimation error and the second term is the approximation error (see Fig. 7). We denote by ξ n = p n -q n the noise in the observations p w.r.t. q. It is easy to notice that

E [ξ n ] = E Y ∼P(•|xn,an) R(x n , a n , Y ) + γ max a ′ ∈A Q(Y, a ′ ) -(T Q)(x n , a n ) = 0, (10)
and that |ξ n | ≤ 2V max . We also define the projected noise ξn = qn -u n , that is ξ = Πξ. Thus, we can rewrite the estimation error as

||q -u|| 2 N = || ξ|| 2 N = ξ, ξ = ξ, ξ , (11)
where the last equality follows from the fact that ξ is the orthogonal projection of ξ. Since ξ ∈ F N , let f β ∈ F be any function such that f β (x n , a n ) = ξn , and by a straightforward application of a variation of Pollard's inequality [START_REF] Györfi | A distribution-free theory of nonparametric regression[END_REF] we obtain

ξ, ξ = 1 N N n=1 ξ n f β (x n , a n ) ≤ 4V max 1 N N n=1 f β (x n , a n ) 2 1/2 2 N log 3(9N e 2 ) d+1 δ = 4V max || ξ|| N 2 N log 3(9N e 2 ) d+1 δ (12)
with probability 1 -δ. Thus from equation 11 we bound the estimation error by

||q -u|| N ≤ 4V max 2 N log 3(9N e 2 ) d+1 δ . (13)
Putting together the estimation error bound and the approximation error term, the statement of the theorem follows.

B.2 Random Samples Design

While in the previous section we analyzed the performance of FQI on the very same state-action pairs in the training set, we now focus on the generalization (i.e., prediction) performance on the whole state-action space.

Let Q be any function f α ∈ F satisfying Φα = q, where q is the vector defined in the previous section. Then we derive the following theorem.

Theorem 5. Let F = {φ(•, •) ⊤ α, α ∈ R d } be a d-dimensional linear space. Let {(X n , A n , Y n , R n )} N n=1 be the training set where (X n , A n ) iid ∼ µ, Y n ∼ P(•|X n , A n ), and R n = R(X n , A n ).
Given a function Q ∈ B(X × A, V max ), let Q be the solution of a single iteration of fitted value iteration. Then with probability 1 -δ (w.r.t. the samples and the next states), Q satisfies

||T ( Q) -T Q|| µ ≤ 4 inf fα∈F ||f α -T Q|| µ + 24(V max + L||α * ||) 2 N log 9 δ + 32V max 2 N log 27(12N e 2 ) 2(d+1) δ . ( 14
)
Proof. The proof mainly relies on the application of concentration of measures inequalities for linear spaces to the deterministic design bound in Theorem 4.

Let f α * ∈ F be any function such that f α * (X n ) = ( Πq) n , thus the approximation error || Πq -q|| N can be rewritten as ||f α * -T Q|| μ. Furthermore we denote by f α * = Π(T Q), that is the best approximation of the target function T Q onto F w.r.t. the distribution µ. Since f α * is the minimizer of the empirical squared error, any function in F different from f α * has a bigger empirical loss, thus we obtain

||f α * -T Q|| μ ≤ ||f α * -T Q|| μ ≤ 2||f α * -T Q|| µ + 12(V max + L||α * ||) 2 N log 3 δ ′ , (15)
with probability 1 -δ ′ , where the second inequality is an application of a variation of Theorem 11.2 in [START_REF] Györfi | A distribution-free theory of nonparametric regression[END_REF] with a bound ||f α * -T Q|| ∞ ≤ V max + L||α * ||. Similar, we notice that the left hand side of Eq. 8 is ||q -q|| N = || Q -T * Q|| μ and we obtain

2|| Q -T Q|| μ ≥ 2||T ( Q) -T Q|| μ ≥ ||T ( Q) -T Q|| µ -24V max 2 N log 9(12eN ) 2(d+1) δ ′ (16)
with probability 1 -δ ′ , where the second inequality is an application of a variation of Theorem 11.2 in [START_REF] Györfi | A distribution-free theory of nonparametric regression[END_REF]. Putting together Eqs 8, 15, and 16 we obtain

||T ( Q) -T Q|| µ ≤2 2||f α * -T Q|| µ + 12(V max + L||α * ||) 2 N log 3 δ ′ + + 4V max 2 N log 3(9N e 2 ) d+1 δ ′ + 24V max 2 N log 9(12eN ) 2(d+1) δ ′
Finally, by setting δ = 3δ ′ the statement follows.

C Analysis of AST C.1 Proof of Theorem 1

Proof. Since the proof follows similar steps as in the proof of Theorem 5, we discuss here only the fixed samples design bound. We define the vector p ∈ R L such that for any l = 1, . . . , L,

p l = M m=1 I {M l = m} (R m l + γ max a ′ Q(Y m l , a ′ )).
The target vector q ∈ R L is the image of the function Q through the average optimal Bellman operator. In fact, by defining q l = (T λ Q)(X l , A l ) we obtain a zero-mean noise vector ξ l = p l -q l such that E [ξ l ] = 0 and |ξ l | ≤ 2V max . 4The statement of the theorem simply follows by decomposing the prediction error of Q as

T ( Q) -T 1 Q µ ≤ T ( Q) -T λ Q µ + T λ Q -T 1 Q µ . (17)
By substituting T ( Q) -T λ Q µ with a FQI bound w.r.t. the target function T λ Q we obtain

T ( Q) -T 1 Q µ ≤ 4||f α -T λ Q|| µ + T λ Q -T 1 Q µ (18) + 24(V max + C||α||) 2 L log 9 δ + 32V max 2 L log 27(12Le 2 ) 2(d+1) δ . (19)
By rewriting the approximation error as ||f α -T λ Q|| µ ≤ ||f α -T 1 Q|| µ + ||T 1 Q -T λ Q|| µ and using α = α * the final bound follows.

C.2 Proof of Theorem 2

Proof.

[Sketch] The main structure of the proof is exactly the same as in [START_REF] Munos | Finite time bounds for fitted value iteration[END_REF]. The main differences are due to the use of linear spaces and the transfer error. Following the passages in the proof of Theorem 2 in [START_REF] Munos | Finite time bounds for fitted value iteration[END_REF], we obtain

||Q * -Q πK || ν ≤ 2γ (1 -γ) 3/2 C µ,ν max k ||T ( Q k ) -T 1 Q k || µ + 2V max γ K .
Thus, we need to study all the terms in the statement of Theorem 1 affected by the maximization over the iterations.

Approximation error. The approximation term becomes

max k min f ∈F ||f -T 1 Q k || µ ≤ sup g∈F min f ∈F ||f -T 1 g|| µ .
This term is referred to as the inherent Bellman error of the space F and it is related to how well the Bellman images of functions in F can be approximated by F itself.

Estimation error. The second relevant term is the term ||α k * || appearing in the estimation error. We recall that f α k * = ΠT 1 Q k-1 is the projection on F of the Bellman image of the function returned at the previous iteration. The function Q k-1 is truncated in the interval [-V max , V max ] and its Bellman image T 1 Q k-1 is still bounded in the same interval. Since the projection operator Π is a non-expansion, we finally have that ||f α k * || ∞ ≤ V max . Using Assumption 2, for any f α ∈ F , it is possible to relate the norm of the function to the norm of the vector α as

||f α || 2 µ = ||φ ⊤ α|| 2 µ = α ⊤ Gα ≥ ωα ⊤ α = ω||α|| 2
. By combining the bound on α with the bound on f α , we obtain that

max k ||α k * || ≤ max k ||f α k * || µ √ ω ≤ V max √ ω Transfer error. Since Q k is the truncation of a function f αk = Q k belonging to F , the transfer error is max k ||(T 1 -T λ ) Q k || µ = sup α (T 1 -T λ )T (f α ) µ .
Finally, the statement of the theorem follows by taking a union bound over K iterations.

D Analysis of BAT

E λ (Q) -E λ * (Q) ≤ 2V max (M -2) log 4S/δ S + 16V 2 max log 4SM/δ T ( 20
)
with probability 1 -δ.

Proof. [Lemma 2]

The sketch of the proof is as follows. For any state-action pair X s , A s , we define

E λ (X s , A s ) = R 1 s - M m=2 λ m R m s + γ 1 T T t=1 max a ′ Q k-1 (Y 1 s,t , a ′ ) - M m=2 λ m max a ′ Q k-1 (Y m s,t , a ′ ) , and
E λ (X s , A s ) = (T 1 Q k-1 )(X s , A s ) - M m=2 λ m (T m Q k-1 )(X s , A s ). As a result, E λ = E µ E λ (x, a) 2 and E λ = 1 S S s=1 E λ (X s , A s ) 2 . By Pollard's inequality on the (M -2)-dimensional simplex Λ, we have for any λ ∈ Λ |E µ E λ (x, a) 2 - 1 S S s=1 E λ (X s , A s ) 2 | ≤ V max (M -2) log S/δ ′ S (21)
with probability 1 -δ ′ . Using Chernoff-Hoeffding inequality we now bound the distance between the true Bellman operators in E λ (X s , A s ) and their estimates in E λ (X s , A s ). By triangle inequality and the previous definitions, we obtain the following series of inequlities

| 1 S S s=1 E λ (X s , A s ) 2 - 1 S S s=1 E λ (X s , A s ) 2 | ≤ | 1 S S s=1 (E λ (X s , A s ) -E λ (X s , A s )) 2 | ≤ max s E λ (X s , A s ) - 1 S S s=1 E λ (X s , A s ) 2 ≤ 2 max s max m (T m Q k-1 )(X s , A x ) -R m s -γ 1 T T t=1 max a ′ Q(Y m s,t , a ′ ) 2 ≤ 2 2V max log SM/δ ′ T 2 (22)
By using Eqs 21 and 22, we have for any λ ∈ Λ

|E λ -E λ | ≤ V max (M -2) log S/δ ′ S + 8V 2 max log SM/δ ′ T ,
with probability 1 -2δ ′ . Finally, we can prove the following sequence of inequalities

E λ -E λ * = E λ -E λ + E λ -E λ * + E λ * -E λ * ≤ 2 sup λ∈Λ |E λ -E λ | ≤ 2V max (M -2) log S/δ ′ S + 16V 2 max log SM/δ ′ T ,
with probability 1 -4δ ′ . By setting δ = 4δ ′ the statement follows.

E Additional Experimental Analysis

In this section, we provide additional experimental results related to the BTT algorithm.

E.1 Analysis of parameters β

In order to have a better understanding on how BTT trades off between the need for samples and the risk of introducing a large transfer error, in Figure 8 we show the values of parameters β (which represent the percentage of samples transferred from each task) as optimized by the BTT algorithm at each FQI iteration. The tasks considered are the target task M 1 and the source tasks M 6 , M 7 , M 8 , M 9 , each one with 5000 samples available. Figure 8 compares the values of β in two scenarios: when the available target samples are 100 (left pane) and 10000 (right pane). Obviously, BTT always exploits all the target samples (β 1 = 1). When few target samples are available, BTT transfers high percentages of samples from the source tasks. In particular, it transfers all the samples available from task M 9 in each iteration, and also the percentage of samples taken from task M 8 is almost constant (about 0.7). The percentage of samples transferred from tasks M 6 and M 7 starts from 100% and decreases (with different rates) through iterations reaching zero after iteration 10. This behavior can be explained by the attempt to include as many samples as possible at the earlier iterations when it is still possible to find combinations of sources with a small transfer error. As the iterations continue, no suitable combination of sources is possible and the algorithm is forced to reduce the number of samples from the more different source tasks. On the other hand, when the number of target samples is large enough, we notice that the percentage of samples transferred from all the source tasks drop down after the first FQI iterations. In fact, in this case, BTT exploits a lot of source samples to produce a more accurate approximations only when a very small error is introduced. On the other hand, as the iterations progress, the samples from the source tasks (even when optimally combined) provide a poor approximation of the Q-functions and, as a result, BTT, given the large number of target samples (10000), prefers to reduce the number of samples transferred from the source tasks.

In Figure 9 we show the proportions λ induced by the weights β computed by BTT. When only 100 target samples are available, BTT tries to compensate the lack of target samples by transferring a large amount of samples from a suitable combination of source tasks, while, when many target samples are available, it considers source samples only when they can guarantee a good approximation of the target Q-functions, otherwise the proportions are changed in favor of the target samples.

Finally, in Figure 10, we consider the total number of samples used to train FQI at each iteration under the two scenarios. As expected, at the first iterations, due to the similarity between source tasks and target task, the number of samples provided to FQI by BTT is very large and then it decreases through iterations. It is interesting to notice that the total number of samples selected in the two scenarios are quite similar (in particular starting from the third iteration), which is an effect of the tradeoff realized by the BTT algorithm.

E.2 Analysis of parameter τ

The tradeoff realized by the BTT algorithm is tuned by the parameter τ multiplying the estimation error. In Figure 11 we analyze the effect of τ on the learning performances. Different values of the tradeoff parameter have been tried (τ = 0.25, 0.50, 0.75, 1.0) when both 5000 samples (left pane) and 10000 samples (right pane) are available for each source task. As we can notice, BTT is quite robust w.r.t. the choice of the tradeoff parameter. The main differences appear when a small number of target samples is available. In this case, low values of τ make BTT more concerned about the transfer error and, as a result, it tends to avoid transferring source samples, even if target samples are not enough. On the other hand, with high values of τ , BTT is pushed to use more source samples, and this may negatively affect the performance when several target tasks are available and no combination of source tasks provides a good target approximation.

Figure 1 :

 1 Figure 1: A pseudo-code for All-Sample Transfer (AST) Fitted Q-iteration.

Figure 2 :

 2 Figure 2: A pseudo-code for the Best Average Transfer (BAT) algorithm.

Figure 3 :

 3 Figure 3: A pseudo-code for Best Tradeoff Transfer (BTT).

Figure 4 :

 4 Figure 4: Transfer from M 2 , M 3 , M 4 , M 5 . Left: Comparison between single-task learning, AST with L = 10000, BAT with L = 1000, 5000, 10000. Right: Source task probabilities estimated by BAT algorithm as a function of FQI iterations.

  source samples + target samples BAT with 10000 source samples + target samples BTT with max 5000 samples for each source BTT with max 10000 samples for each source

Figure 5 :

 5 Figure 5: Transfer from M 6 , M 7 , M 8 , M 9 . Left: Comparison between single-task learning and BAT with L = 1000, 5000, 10000. Right: Comparison between single-task learning, BAT with L = 1000, 10000 in addition to the target samples, and BTT (τ = 0.75) with 5000 and 10000 samples for each source task. To improve readability, the plot is truncated at 5000 target samples.

Figure 7 :

 7 Figure 7: This figure shows that the vectors used in the proof of Theorem 4.

9 Figure 9 :

 99 Figure 9: Proportions in the combination of task samples induced by BTT β parameters as a function of FQI iterations. Left: 100 target samples available. Right: 10000 target samples available.

Figure 10 :

 10 Figure 10: Number of samples actually used at each iteration (after the transfer) by FQI. Left: 100 target samples available. Right: 10000 target samples available.

  with τ = 0.25 BTT with τ = 0.50 BTT with τ = 0.75 BTT with τ = 1.00

Figure 11 :

 11 Figure 11: Comparison of the performance of FQI using BTT algorithm with different values of the tradeoff parameter τ . Left: 5000 samples available for each source. Right: 10000 samples available for each source.

  number of samples L Build the auxiliary set {(Xs, As, Rs,1, . . . , Rs,M } S s=1 and {Y t s,1 ,. . ., Y t s,M } T t=1 for each s for k = 1, 2, . . . do Compute λ k = arg min λ∈Λ

  maximum number of samples available for each task Nm, transfer parameter c Build a training set {Xs, As, R 1 s , . . . , R M s } S s=1 and the next states {Y 1 s,t , . . . , Y M s,t } T t=1 for each state-action pair

Table 1 :

 1 Parameters for the first set of tasks

	tasks	p	l	η	Reward
	M1	0.9	1	0.1	+1 in [-11, -9] ∪ [9, 11]
	M2	0.9	2	0.1	-5 in [-11, -9] ∪ [9, 11]
	M3	0.9	1	0.1	+5 in [-11, -9] ∪ [9, 11]
	M4	0.9	1	0.1	+1 in [-6, -4] ∪ [4, 6]
	M5	0.9	1	0.1	-1 in [-6, -4] ∪ [4, 6]

Table 2 :

 2 Parameters for the second set of tasks

	tasks	p	l	η	Reward
	M1	0.9	1	0.1	+1 in [-11, -9] ∪ [9, 11]
	M6	0.7	1	0.1	+1 in [-11, -9] ∪ [9, 11]
	M7	0.1	1	0.1	+1 in [-11, -9] ∪ [9, 11]
	M8	0.9	1	0.1	-5 in [-11, -9] ∪ [9, 11]
	M9	0.7	1	0.5	+5 in [-11, -9] ∪ [9, 11]

1 Proof of Theorem 3 Lemma 2.

  Let {(X s , A s , R 1 s , . . . , R M s )} S s=1 be a training set where (X s , A s ) and R m s = R m (X s , A s ) and for each state-action pair and for each task m, T next states Y m s,t ∼ P m (•|X s , A s ) with t = 1, . . . , T are available. For any fixed bounded function Q ∈ B(X × A; V max ), the λ returned by minimizing Eq. 3 is such that

D.

iid ∼ µ

  Figure 8: Percentage of samples for each task as selected by BTT as a function of FQI iterations when 5000 samples are available for each source task. Left: 100 target samples available. Right: 10000 target samples available.

		100										100
		80										80
	β values	40 60									β values	40 60
		0 20									β 1 β 6 β 7 β 9 β 8	0 20									β 1 β 6 β 7 β 8 β 9
		1	2	3	4	5	6	7	8	9	10 11 12 13	1	2	3	4	5	6	7	8	9	10 11 12 13
							Number of iterations								Number of iterations

The extension to stochastic reward functions is straightforward.

We refer to[START_REF] Munos | Finite time bounds for fitted value iteration[END_REF] for a thorough explanation of the concentrability terms.

If λm = 1 for task m, then the algorithm would generate all the L training samples from task m.

The expectation is taken w.r.t. both the random realization of the reward R m l and next state Y m l and task index M l .

Acknowledgments This work was supported by French National Research Agency through the projects EXPLO-RA n • ANR-08-COSI-004, by Ministry of Higher Education and Research, Nord-Pas de Calais Regional Council and FEDER through the "contrat de projets état region 2007-2013", and by PASCAL2 European Network of Excellence. The research leading to these results has also received funding from the European Community's Seventh Framework Programme (FP7/2007-2013) under grant agreement n 231495.

Input: Linear space F = span{ϕi, 1 ≤ i ≤ d}, initial function Q 0 for k = 1, 2, . . . do

Draw training samples {(Xn, An, Yn, Rn)} N n=1

Build the feature matrix Φ = [φ(X1, A1) ⊤ ; . . . ; φ(Xn, An) ⊤ ] Compute the vector pn

A Additional Notation

Besides the notation introduced in Section 2, here we introduce additional symbols used in the proofs. We define two empirical norms on functions and vectors. Given a set of N state-action pairs

Similarly, given a vector y ∈ R N we define the empirical norm ||y|| N as

, and

Note that the orthogonal projection Πy of any y ∈ R N always exists and is unique.

B Fitted Q-iteration with Linear Spaces

Although fitted iterative methods have been already analyzed in detail in [START_REF] Munos | Finite time bounds for fitted value iteration[END_REF] and [START_REF] Antos | Fitted Q-iteration in continuous actionspace MDPs[END_REF], at the best of our knowledge no explicit finite-sample bounds for FQI with linear spaces is available. Since at each iteration, FQI solves an explicit regression problem, the derivation is mostly a straightforward application of regression bounds for linear spaces and quadratic loss. Here we just report the result and the proof of the single iteration error for the so-called fixed and random samples design settings.

In Algorithm 6 we report the structure of the algorithm.

B.1 Fixed Samples Design

Similar to the analysis of LSTD in [START_REF] Lazaric | Finite-sample analysis of LSTD[END_REF] we first derive the fixed design bound (i.e., the performance is evaluated exactly on the states in the training set).

n=1 be the training set where {(x n , a n )} N n=1 is an arbitrary sequence of stateaction pairs, Y n ∼ P(•|x n , a n ), and R n = R(x n , a n ). Given a function Q ∈ B(X × A, V max ), let q ∈ R N be the vector whose components are q n = (T Q)(x n , a n ) and q be the solution of a single iteration of fitted value iteration. Then with probability 1 -δ (w.r.t. the random next states Y n ), q


Olivier Pietquin

Matthieu Geist

Senthilkumar Chandramohan

Sample Efficient On-line Learning of Optimal Dialogue Policies with Kalman Temporal Differences

Designing dialog policies for voice-enabled interfaces is a tailoring job that is most often left to natural language processing experts. This job is generally redone for every new dialog task because cross-domain transfer is not possible. For this reason, machine learning methods for dialog policy optimization have been investigated during the last 15 years. Especially, reinforcement learning (RL) is now part of the state of the art in this domain. Standard RL methods require to test more or less random changes in the policy on users to assess them as improvements or degradations. This is called on policy learning. Nevertheless, it can result in system behaviors that are not acceptable by users. Learning algorithms should ideally infer an optimal strategy by observing interactions generated by a non-optimal but acceptable strategy, that is learning off-policy. In this contribution, a sample-efficient, online and off-policy reinforcement learning algorithm is proposed to learn an optimal policy from few hundreds of dialogues generated with a very simple handcrafted policy.

Introduction

After 60 years of research, speech and language processing techniques have come to such a level of maturity that voiceenabled interfaces are now industrialized and have the potential of creating billions of profits. Yet, the design of such interfaces is far from being simple and requires expert skills in speech and language technologies, ergonomics, low level programming, etc. Indeed, it is not enough to put speech recognition and synthesis systems together to build a natural interface but the management of the interaction is responsible for its efficiency and naturalness. Dialog management is highly task dependent and it has to be designed again for each new application. Hiring or training personals with all the required skills is very difficult as well as expensive and this probably slows down the development of speech-based interfaces for the general public.

Because of this, research in the domain of Spoken Dialogue Systems (SDS) have experienced an increasing growth during the last decade. Machine learning, and especially Reinforcement Learning (RL) [START_REF] Sutton | [END_REF]], for optimal dialog management policy learning is now part of the state of the art [Singh et al., 1999;[START_REF][END_REF][START_REF] Pietquin | [END_REF][START_REF] Williams | [END_REF]. RL is a machine learning method for optimizing sequential decision making by maximizing a cumulative of local rewards obtained through actual interactions as described in Section 2. Dialogue management can indeed be seen as a sequential decision making problem where a dialog manager has to select which information to ask or transmit to a human user according to the context of the dialogue. Yet, standard RL algorithms are very data demanding and dialog corpora are very hard to collect and annotate. To alleviate this data sparsity problem, dialogue simulation based on user modeling is most often used to artificially expand training datasets [START_REF] Schatzmann | [END_REF][START_REF] Pietquin | [END_REF][START_REF][END_REF]. However, the learnt strategies are sensible to the quality of the user model which is very difficult to assess [START_REF] Schatzmann | [END_REF].

An alternative to this bootstrapping method would be to use generalization frameworks adapted to RL such as approximate dynamic programming [Gordon, 1995;Lagoudakis and Parr, 2003] or online value function approximation [START_REF] Sutton | [END_REF]]. Very few attempts to do so in the framework of dialogue management can be found in the literature. In [START_REF] Henderson | [END_REF], the authors use the SARSA(λ) algorithm [START_REF] Sutton | [END_REF]] with linear function approximation which is known to be sample inefficient. In [START_REF] Li | Reinforcement Learning for Dialog Management using Least-Squares Policy Iteration and Fast Feature Selection[END_REF], LSPI [Lagoudakis and Parr, 2003] is used with feature selection and linear function approximation. Recently, Fitted Value Iteration (FVI) [Gordon, 1995] have also been applied to dialogue management [Chandramohan et al., 2010;Pietquin et al., 2011]. All these studies report batch learning of dialog policies from fixed sets of data and thus learn in an off-policy manner, meaning that they learn an optimal policy from observations generated with another policy (which is mandatory for learning from fixed sets of data). Online learning using Gaussian Processes [START_REF] Gasic | [END_REF] or Natural Actor Critic [START_REF] Jurcicek | [END_REF] has also been proposed. These works report the use of online and on-policy algorithms which requires permanently changing the policy to be learnt (an issue known as the dilemma between exploration and exploitation). These changes to the policy made during learning are visible to the user which may cause problems in real applications at the early stage of learning where the changes in the policy can lead to very bad behaviors of the dialogue manager. Thus, user simulation is still required.

This contribution proposes a sample-efficient, online and off-policy learning algorithm for dialogue management policy optimization, namely the Kalman Temporal Differences (KTD) algorithm [Geist and Pietquin, 2010a] 1 .This algorithm meets many requirements of this specific task. First, offpolicy learning is mandatory because collecting data requires real interactions with users which needs a fairly good initial dialogue policy. So the optimal policy has to be learnt from observations generated by another policy producing an acceptable behavior (even if suboptimal) by the users. Second, sample-efficient online learning can react rapidly to changes in the average behavior of users. Such changes can occur because of the users getting used to interacting with the system. It should of course use as few samples as possible because of the cost of data collections. KTD is compared to other offline (FVI and LSPI) and online (Q-learning) off-policy methods. Experimental results show that KTD learns a policy that compares positively to those learnt by other algorithms with only few tens of dialogue samples while several thousands of dialogues are required by the others to reach convergence.

Dialogue Management and Reinforcement Learning

In the general RL paradigm [START_REF] Sutton | [END_REF]], an agent learns to control optimally a dynamic system through actual interactions with this system. At each time step i, the system is in a given state s i and the agent chooses an action a i according to its current strategy (or policy) π and to the current state s i . Following its own dynamics, the system is then driven (stochastically) to a new state s i+1 , and the agent receives a reward r i which is a local hint on the quality of the strategy. The goal of RL is to learn a policy maximizing the expected cumulative reward on the long run (and not the immediate rewards).

Markov Decision Process

Formally, the problem can be cast into the Markov Decision Processes (MDP) paradigm [Bellman, 1957]. An MDP is a tuple {S, A, P, R, γ} where S is the state space, A is the action space, P ∈ P(S) S×A is the set of Markovian transition probabilities2 , R ∈ R S×A×S is the reward function and γ is a discount factor weighting long-term rewards. A policy is a mapping from states to actions: π ∈ A S . The quality of a policy π is quantified thanks to the so-called value function V π ∈ R S which associates to each state the expected discounted cumulative reward (expectation being done according to trajectories) obtained by starting in this state and then following the policy π:

V π (s) = E[ ∞ i=0 γ i r i |s 0 = s, π] (1)
The state-action value (or Q-) function (Q π : R S×A ) adds a degree of freedom for the choice of the first performed action:

Q π (s, a) = E[ ∞ k=0 γ k r k |s 0 = s, a 0 = aπ] (2)
An optimal policy π * maximizes the value of each state:

π * ∈ argmax π V π (or ∈ argmax π Q π ) (3)
The optimal policy is greedy respectively to the optimal Qfunction Q * : π * (s) = argmax a∈A Q * (s, a). Finding the optimal policy therefore reduces to finding the optimal Qfunction. Because of the Markov property of transition probabilities, the optimal Q-function can be expressed by the Bellman optimality equation :

Q * (s, a) = E s |s,a [R(s, a, s ) + γ max b∈A Q * (s , b)] (4)
Most often, the state-action space is too large to obtain an exact representation of the Q * function. In such a case, it is convenient to adopt a parametric representation. Let θ ∈ R p represent the parameter vector and Qθ the approximate Qfunction belonging to the hypothesis space H (the functional space spanned by parameters). The goal is therefore to compute a good approximation Qθ of Q * . For example, considering a linear parameterization:

H =    Qθ : Qθ (s) = p j=0 θ j φ j (s)    (5)
where φ j (s) are features or basis functions, for instance Gaussian functions. In this case, the Q-function is approximated by a weighted sum of such basis functions, the parameter vector to be found being the weights θ.

Dialogue Management as an MDP

Dialogue management can be seen as a sequential decision making problem where a dialogue manager has to select which information should be asked or provided to the user when in a given dialogue context. It can thus be cast into the MDP framework. The set A of actions a dialog manager can select is defined by the so called dialog acts it can perform. There can be different types of dialog acts such as: greeting the user, asking for a piece of information, providing a piece of information, asking for confirmation about a piece of information, closing the dialog etc. The state of a dialog is usually represented efficiently by the Information State paradigm [Larsson and Traum, 2000]. In this paradigm, the dialogue state contains a compact representation of the history of the dialogue in terms of dialog acts and its user responses. It summarizes the information exchanged between the user and the system until the considered state is reached.

It is a representation of the context. A dialogue management strategy or policy π is therefore a mapping between dialogue states and dialogue acts. According to the MDP framework, a reward function has to be defined. The immediate reward is often modeled as the contribution of each action to the user's satisfaction [Singh et al., 1999]. This is a subjective reward which is usually approximated by a linear combination of objective measures (dialogue duration, number of ASR errors, task completion etc.). Weights of this linear combination can be computed from empirical data [START_REF] Walker | [END_REF].

Kalman Temporal Differences

There exists many RL algorithms in the literature [START_REF] Sutton | [END_REF]] aiming at estimating the optimal Q-function for a given MDP (see eq. ( 1)). The Kalman Temporal Differences (KTD) framework [Geist and Pietquin, 2010a] has been recently introduced as an alternative way to estimate this Qfunction. The basic idea behind this work is to cast value function approximation as a filtering problem, and to solve it using Kalman filtering [Kalman, 1960] (as well as variations). Like Kalman filtering extensions, it allows handling nonlinearities (nonlinear parameterizations but also the max operator of eq. ( 4)), handling non-stationarity which can be helpful to adapt to changes in the average behavior of users but also active sampling of the state-action space [Geist and Pietquin, 2010b]. This approach is also very sample efficient and therefore allows learning good policies from very few samples. Moreover, it can be used in an off-policy setting, making the algorithm able to learn optimal policies while simply observing sub-optimal policies. That is the aspect investigated here.

The KTD-Q algorithm is the KTD's specialization devoted to learning the optimal state-action value function, and it is briefly presented here.

Q-function approximation as a filtering problem

A filtering problem consists in estimating hidden quantities X from related observations Y . For instance, estimating the position of an object from noisy observations (case of the radar). In [Kalman, 1960], the author proposes the wellknow Kalman filter solution which is a statistical sequential solution. The quantities X and Y are modeled as random variables, the searched solution is the conditional expectation Xi|i = E[X|Y 1 , . . . , Y i ] and the algorithm is based on a socalled state-space formulation (not to be confounded with the state space of the MDP). This formulation specifies (via 2 equations) how the hidden quantities evolve (see eq. ( 6)), and how they are linked to observations (see eq. ( 7)).

X i+1 = f i (X i , v i ), (6)
Y i = g i (X i , w i ). (7)
Given these equations, the Kalman filter proposes a linear update rule providing the best linear estimate of the conditional expectation Xi|i = E[X|Y 1 , . . . , Y i ]:

Xi|i = Xi|i-1 + K i (Y i -Ŷi|i-1 ) (8)
where K i is the so-called Kalman gain (which is computed according to some statistics not developed here) and Ŷi|i-1

is the prediction of the observation given the current estimate of Xi|i-1 and eq. ( 7). In the KTD framework, the hidden quantities to be estimated are the Q-function parameters (X = θ), and the observations are the rewards (Y = r i ) (as well as related transitions from states to states given actions: {s, a, s }). Optimal parameters can evolve with time, meaning that the optimal policy is not fixed (so is the associated Q-function). It is the case if the system is not stationary for example, which happens in dialogue systems because the user population evolves for instance. Yet, this evolution is not known (the function f of eq. ( 6) is not known) and, adopting the Occam's razor principle, a random walk evolution model is assumed for parameters (θ i = θ i-1 + v i with v i being a centered white evolution noise). Rewards are linked to parameters through the (sampled) Bellman optimality equation (see eq. ( 4)) which provides the g i function of eq. ( 7). A centered and white observation noise n i is added because the estimated value Q θ doesn't necessary live in the functional space H (inductive bias). This provides the following statespace formulation in the Kalman filtering paradigm:

θ i = θ i-1 + v i r i = Qθi (s i , a i ) -γ max a∈A Qθi (s i+1 , a) + n i (9)
According to the Kalman Filtering theory, the KTD-Q algorithm provides among all linear estimators the one minimizing the expectation (remember that parameters θ i are modeled as random variables) of the mean-squared error conditioned on past observed rewards:

J i (θ) = E[ θ i -θ 2 |r 1:i ].
The full algorithm is not given here for the seek of brevity (all details can be found in [Geist and Pietquin, 2010a]), however the general update rule is provided. Parameters θ i but also an associated variance P i are maintained. For each new transition, some statistics P ri (scalar) and P θri (vector) as well as the predicted reward ri (basically, this predicted reward is computed using the observation equation, and r i -ri , the difference between the observed reward and its prediction, is actually a temporal difference error) are computed (using notably θ i-1 and P i-1 ), and parameters (as well as the variance matrix) are updated using according to the Kalman gain

K i :    K i = P θri P -1 ri θ i = θ i-1 + K i (r i -ri ) P i = P i-1 -K i P ri K T i (10)
4 Application to a dialog management problem

The considered system to control is a form-filling and taskoriented spoken dialog system. The problem is a tourism information task, similarly to the one in [Lemon et al., 2006].

Its goal is to provide information about restaurants in a city based on specific user preferences. There are three slots in this dialog problem, namely the location of the restaurant in the city, the cuisine of the restaurant and its price-range. Given past interactions with the user, the agent has to ask questions so as to propose the best choice according to the user preferences.

Related MDP

The corresponding MDP's state has 3 continuous components ranging from 0 to 1, each representing the averaging of filling and confirmation confidence scores (provided by the speech recognition system) of the respective slots. There are 13 possible actions: ask for a slot (3 actions), explicit confirmation of a slot (3 actions), implicit confirmation of a slot and ask for another slot (6 actions) and close the dialog by proposing a restaurant (1 action). The corresponding reward is always 0, except when it closes the dialog. In this case, the agent is rewarded 25 per correct slot filling, -75 per incorrect slot filling and -300 per empty slot. The discount factor is set to γ = 0.95 and it thus favors shorter interactions (see eq. ( 2)).

Experimental setup

Even if the ultimate goal is to implement RL on a real dialog management problem, a user simulation technique was used here to generate data. This way, the sensibility of learning can be analyzed, and obtained policies can be tested sufficiently often to obtain meaningful statistics. The user simulator was plugged to the DIPPER dialogue management system [Lemon et al., 2006] to generate dialogue samples. To generate data, the dialogue manager strategy was based on a simple hand-coded policy (which aims at filling each slot by explicitly asking before closing dialog) combined with random action selection. With a probability , the system acts randomly, and with a probability 1 -, the system acts according to the specified policy. Random actions are actually chosen among "reasonable actions" and a set of hand-crafted rules prevents the dialogue manager to confirm a slot while it has never been asked before, for instance. This ensures that the state-action space is sufficiently explored (even if considered algorithms are off-policy, they cannot learn what to do in situations which are not similar to any seen dialogue turn). KTD-Q is compared to 3 other algorithms, namely fitted-Q [Gordon, 1995], LSPI [Lagoudakis and Parr, 2003] and Q-learning [START_REF] Sutton | [END_REF]]. All algorithms are offpolicy. Fitted-Q and LSPI are sample-efficient batch algorithms. Q-learning is an online algorithm (the off-policy variation of SARSA, the mostly used algorithm in the SDS literature). KTD is a sample-efficient online algorithm.

Reinforcement Learning setup

The Q-function is represented using one Radial Basis Function (RBF) network per action. Each RBF network has three equi-spaced Gaussian functions per dimension, each one with a standard deviation of σ = 1 3 (state variables ranging from 0 to 1). Therefore, there are 351 (i.e., 33 × 13) parameters. The corresponding feature vector is zero everywhere, except in the 9 components corresponding to the considered actions which are of the form exp(-s-si 2 2σ 2 ), s i being the i th RBF center. For all the algorithms, the initial parameter vector θ 0 is set to 0. For LSPI and fitted-Q, no parameters have to be tuned (which is an advantage of these approaches). For Q-learning, one has to choose the learning rate α. Here a learning rate of 0.2 is chosen, divided by two each 10 4 interactions (similarly to what is done in [Lemon et al., 2006] for SARSA). For KTD-Q, a prior variance over parameters (matrix P 0 ) and the variance of the observation noise have to be chosen. It is less usual than choosing a learning rate, but not really more difficult (see [Geist and Pietquin, 2010a] for details about parameters tuning for KTD in general).

Results

Obtained results are presented on figures 1 (abscissa in linear scale) and 2 (abscissa in logarithmic scale). These curves show the mean discounted cumulative rewards and associated standard deviations of each learnt policy in addition to the hand-coded policy. The hand-coded policy is not provided as a baseline but only to show that the learnt policies (with all the algorithms) were obtained by observing dialogues generated with this quite poor policy (there is no need of a good initial policy). The abscissa represents transitions (or dialog turns) and not dialogs. In average, a dialog obtained with an optimal policy is composed of 4 to 8 turns. To compute these statistics, each algorithm was trained 8 times for 5.10 4 interactions on different simulations (for each training phase, all algorithms used the same transitions), and each obtained policy was tested 50 times. Therefore, each point is an average of 400 runs. Notice that we stopped each testing dialog if not finished after 100 turns. The associated reward is close to 0. Therefore, a value of 0 means that the agent did not learn to stop the dialog, and it is therefore normal that the associated standard deviation is low. Fitted-Q and LSPI curves start only at 5.10 3 samples: these algorithms require inverting some matrices which are too badly conditioned below a few thousands of samples (knowing that we have a few hundreds of parameters) 3 . According to figure 1, Q-learning learns very slowly, it does not even learn a policy as good as the hand-coded one after 5.10 4 interactions. This is compliant with the literature [Lemon et al., 2006]. KTD-Q learns near optimal policies in very few samples. They are a little bit underperforming compared to those learnt by LSPI or fitted-Q. However, recall that KTD-Q is an online algorithm. Therefore, it process each sample only one-time, contrary to fitted-Q or LSPI which process each transition many times in the regression process. One can notice that KTD-Q learns good policies very fast, that is why we provide on figure 2 the same curves with a logarithmic scale for the x-axis.

This figure shows that after 300 hundred transitions, Qlearning learns a not so bad policy (approximately equivalent to the hand-crafted policy). However, it looses this performance quite quickly, learning is not stable at this stage (according to experiments not reported here, tuning the learning rate does not help here).On the other hand, the KTD-Q algorithm learns good policies (performing equally to LSPI after convergence) after only a few hundreds of transitions, and in a stable manner (variance is decreasing). Another interesting aspect is its ability to provide good policies when there is not enough sample to even run fitted-Q or LSPI (they do not converge). So, 500 turns (about 100 dialogues) are sufficient to learn a near-optimal policy while standard Q-learning would require 1000 times more. This amount of dialogs can be easily collected in real applications to learn optimal policies with KTD-Q. Also, the variance is much lower with KTD after 5000 turns than for LSPI meaning that results are more reproducible.

Discussion

Results presented in the previous section are very promising. The proposed online algorithm could learn high performance policies from few tens of dialogue turns collected with a very simple strategy (its performance is quite bad when compared to the learnt ones) and without having to change the policy while interacting with users during the learning phase. One should remember that the learning curves are drawn with respect to dialogue turns and not dialogues. In average, a complete learnt dialogue was about 4 to 5 turns long (it is shorter than the optimal control, but it does not always satisfies the user). Since the Fitted-Q and LSPI learn quasi-optimal policies after only 5 to 10k dialogue turns, it means that only 1k to 2k dialogues were required to learn. The KTD algorithm learns dialogue policies before the Fitted-Q and LSPI don't even converge, this is why the curves for the these batch algorithms only start later.

Although the task addressed in this paper is relatively simple (3-slots), its size is similar in terms of state-action space to those presented in the state of the art dealing with RL for SDS optimization [START_REF] Levin | [END_REF][START_REF][END_REF]Singh et al., 1999;Lemon et al., 2006]. Actually, scaling up in terms of dialogue task is not to be compared to scaling up in terms of RL problems. For example, the dialogue task described in [START_REF] Gasic | [END_REF][START_REF] Jurcicek | [END_REF] is a 12-slot dialogue problem (so 4 times more than the system described in this paper). Yet, the RL state space used by the authors to optimize the strategy is only composed of 2 continuous and 2 discrete dimensions which makes this problem of comparable size with the one addressed in this paper in terms of RL complexity. Moreover, the MDP framework is chosen and not the Partially Observable MDP (POMDP) framework like in [START_REF] Gasic | [END_REF][START_REF] Jurcicek | [END_REF]]. Yet, the POMDP resumes to an MDP in these works through the summary space trick. So, the complexity of the example described in this paper is comparable to state-of-the-art but simpler to analyse, this is why we have opted for this task.

It is rare that in the SDS literature, algorithms are compared according to their sample-efficiency, that is the number of required dialogues to reach convergence toward a good dialogue policy. Learning curves are generally provided to show that some methods out-perform others but the actual number of dialogues required to learn is not the main focus. In [START_REF] Levin | [END_REF][START_REF][END_REF] the authors mention that more than 700k dialogues were needed to learn the optimal policy on a 3 slots problem (for a database querying task). This seminal work encouraged researchers to build user simulation so as to generate enough data for RL algorithms to converge, this is probably why sample-efficiency has not been investigated so much. Yet, some recent works [START_REF] Gasic | [END_REF][START_REF] Jurcicek | [END_REF] have focused on sample-efficient RL algorithms. Nevertheless they use online and on-policy algorithms which also require user simulation, not only for expanding the datasets but simply to be run. Therefore, all the problems induced by simulation are still present [START_REF] Schatzmann | [END_REF].

In [Chandramohan et al., 2010], the authors also propose the use of sample-efficient algorithms but batch ones while this paper proposes an online algorithm. The work reported in [START_REF] Li | Reinforcement Learning for Dialog Management using Least-Squares Policy Iteration and Fast Feature Selection[END_REF] is also about a sample-efficient batch algorithm. In that paper, the task is not more complex (although the vocabulary is, but the study reported here stands at the intention level) since a maximum of three slots are also requested by the system (most of dialogues only need one slot to be filled). The system is also helped by the introduction of human knowledge to pre-select actions. Also, [START_REF] Li | Reinforcement Learning for Dialog Management using Least-Squares Policy Iteration and Fast Feature Selection[END_REF] makes use of a user simulation method to generate different sets of data as was done in this paper which makes the work presented here suitable for comparison with the state of the art. Yet, simulation is not mandatory in the general case. In addition, the user simulation doesn't simplify the task to be learnt (which only depends on the state-action space size and the quality of the exploration done with the handcrafted policy) and results are not losing generality.

Finally, the comparison of the reproducibility of the results when using Fitted-Q and LSPI shows that KTD is more stable. Indeed, the variance on the performances seems to be lower and decreasing with time with this new algorithm.

Conclusion

This contribution addressed the problem of rapid learning of optimal spoken dialogue management policies with reinforcement learning from online interaction while simply observing a poor policy behaving (off-policy learning). Several generalization schemes have been compared including batch and online learning algorithms. All the algorithms are off-policy meaning that they learn by observing a lowperformance but acceptable policy. The experimental results show that the KTD-Q algorithm can learn a near optimal policy in few hundreds of dialog turns (corresponding to less than 100 dialogs). This means that an optimal policy could be directly learnt from collected data avoiding data expansion methods based on user modeling. Also better approximation schemes than linear parameterizations are envisioned such as neural networks. Moreover, similarly to GPTD [START_REF] Gasic | [END_REF], uncertainty maintained by the KTD framework can be used to actively explore the state-action space so as to fasten convergence. Finally, the Kalman filtering paradigm would allow introducing prior knowledge to handle partial observability by extending the parameter vector and adding evolution equations into the state-space model described in Section 3.

Figure 1 :

 1 Figure 1: Results, linear scale.

Figure 2 :

 2 Figure 2: Results, log. scale.

The previous work by the authors focused on theoretical aspects of KTD and artificial benchmarks.

Notation f ∈ A B is equivalent to f : B → A.

Although the convergence problem can be solved by regularizing the matrices to be inverted, our experiments showed that regularized LSPI resulted in unstable policies.

The work presented here has been done during the CLASSiC project (Grant No. 216594, www.classic-project.org) funded by the European Commission's 7th Framework Programme (FP7).