Title: LIPSCHITZ LIFELONG REINFORCEMENT LEARNING

Abstract: We consider the problem of knowledge transfer when an agent is facing a series of Reinforcement Learning (RL) tasks. We introduce a novel metric between Markov Decision Processes and establish that close MDPs have close optimal value functions, that is that optimal value functions are Lipschitz continuous with respect to tasks. These theoretical results lead us to a value transfer method for Lifelong RL, which we use to build a PAC-MDP algorithm with improved convergence rate. We illustrate the benefits of the method in Lifelong RL experiments.
Under review as a conference paper at ICLR 2020 transfer by characterizing the way the optimal Q-function can evolve across tasks. We restrict the scope of the study to the case where sampled MDPs share the same state-action space S × A. For brevity, we will refer indifferently to MDPs, models or tasks, and write them M = R, T .
Using a metric between MDPs has the appealing characteristic of quantifying the amount of similarity between tasks, which intuitively should be linked to the amount of transfer achievable. Song et al. ( 2016) define a metric based on the bi-simulation metric introduced by Ferns et al. ( 2004) and the Wasserstein metric (Villani, 2008) . Value transfer is performed between states with low bi-simulation distances. However, this metric requires knowing both MDPs completely and is thus unusable in the Lifelong RL setting where we expect to perform transfer before having learned the current MDP. Further, the transfer technique they propose does allow negative transfer (see Appendix, Section A). Carroll and Seppi (2005) also define a value-transfer method based on a measure of similarity between tasks. However, this measure is not computable online and thus not applicable to the Lifelong RL setting. Mahmud et al. (2013) and Brunskill and Li (2013) propose MDP clustering methods respectively using a metric quantifying the regret of running the optimal policy of one MDP in the other MDP and the L 1 norm between the MDP models. An advantage of clustering is to prune the set of possible source tasks. They use their approach for policy transfer, which differs from the value-transfer method proposed in this paper. Ammar et al. ( 2014) learn the model of a source MDP and view the prediction error on a target MDP as a dissimilarity measure in the task space. Their method makes use of samples from both tasks and is not readily applicable to the online setting considered in this paper. Lazaric et al. (2008) provide a practical method for sample transfer, computing a similarity metric reflecting the probability of the models to be identical. Their approach is applicable in a batch RL setting as opposed to our online setting. The approach developed by Sorg and Singh ( 2009) is very similar to ours in the sense that they prove bounds on the optimal Q-function for new tasks, assuming that both MDPs are known and that a soft homomorphism exists between the state spaces. Brunskill and Li (2013) also provide a method that can be used for Q-function bounding in multi-task RL. Abel et al. (2018) present the MaxQInit algorithm, providing transferred bounds on the Q-function with high probability while preserving PAC-MDP guarantees. Given a set of solved tasks, they derive the probability that the maximum over the Q-values of previous MDPs is an upper bound on the current task's optimal Q-function. This results in a method for non-negative transfer with high probability once enough tasks have been sampled.

1. INTRODUCTION:

Lifelong Reinforcement Learning (RL) is an online problem where an agent faces a series of RL tasks, drawn sequentially. Transferring the knowledge of prior experience while solving new tasks is a key question in that setting (Lazaric, 2012; Taylor and Stone, 2009) . We elaborate on the intuitive idea that similar tasks should allow a large amount of transfer. An agent able to compute online a similarity measure between source tasks and the current target task should be able to perform transfer. By measuring the amount of inter-task similarity, we design a novel method for value transfer, practically deployable in the online Lifelong RL setting. Specifically, we introduce a metric between MDPs and prove that the optimal Q-value function is Lipschitz continuous with respect to MDPs. This property allows to compute a provable upper-bound on the optimal value function of a target task, given the learned optimal value function of a source task. Knowing this upper bound allows to accelerate the convergence of an RMax algorithm (Brafman and Tennenholtz, 2002) . This transfer method is non-negative (it cannot cause performance degradation) as the computed upper bound does not underestimate the optimal Q-value function.

Our contributions are as follows. First, we study theoretically the Lipschitz continuity of the optimal value function in the task space (Section 3). Then, we use this continuity property to propose a value-transfer method based on a local distance between MDPs (Section 4). Full knowledge of both MDPs is not required and the transfer is non-negative, which makes the method both practical and safe. In Section 4.2, we build a PAC-MDP algorithm called Lipschitz RMax, applying this transfer method online in the Lifelong RL setting. We provide sample and computational complexity bounds and showcase the algorithm in Lifelong RL experiments (Section 5).

2. BACKGROUND AND RELATED WORK:

Reinforcement Learning (RL) (Sutton and Barto, 1998 ) is a framework for sequential decision making. The problem is typically modeled as a Markov Decision Process (MDP) (Puterman, 2014) consisting in a 4-tuple S, A, R, T where S is a state space, A an action space, R a s is the expected reward of taking action a in state s and T a ss is the transition probability of reaching state s when taking action a in state s. Without loss of generality, we assume R a s ∈ [0, 1]. Given a discount factor γ ∈ [0, 1), the expected cumulative return t γ t R at st obtained along a trajectory starting with state s and action a is noted Q(s, a) and called the Q-function. The optimal Q-function Q * is the highest attainable expected return from s, a and V * (s) = max a∈A Q * (s, a) is the optimal value function in s.

Lifelong RL (Silver et al., 2013; Brunskill and Li, 2014) is the problem of experiencing online a series of MDPs drawn from an unknown distribution. Each time an MDP is sampled, a classical RL problem takes place where the agent is able to interact with the environment to maximize its expected return. In this setting, it is reasonable to think that knowledge gained on previous MDPs could be re-used to improve the performance in new MDPs. In this paper, we provide a novel method for such 3 LIPSCHITZ CONTINUITY OF Q-FUNCTIONS

The intuition we build on is that similar MDPs should have similar optimal Q-functions. Formally, this insight can be translated into a continuity property of the optimal Q-functions over the MDP space M. The remainder of this section mathematically formalizes this intuition that will be used in the next Section to derive a practical method for value transfer. To that end, we introduce a local pseudo-metric characterizing the distance between the models of two MDPs at a particular state-action pair. A reminder and a detailed discussion on the metrics (and related objects) used herein can be found in the Appendix, Section B. Definition 1. Given two tasks M = R, T and M = R, T , and a function f : S → R + , we define the pseudo-metric between models at (s, a) ∈ S × A w.r.t. f as:

EQUATION

This pseudo-metric is relative to a positive function f . We implicitly cast this definition in the context of discrete state spaces. The extension to continuous spaces is straightforward but beyond the scope of this paper. Let Q * M denote the optimal Q-function of MDP M ∈ M. Proposition 1 (Local pseudo-Lipschitz continuity). (3)

All the proofs of the paper can be found in the Appendix. This result establishes that the distance between the optimal Q-functions of two MDPs at (s, a) ∈ S × A is controlled by a local dissimilarity between the MDPs. The latter follows a fixed-point equation (Equation 3), which can be solved by Dynamic Programming (DP) (Bellman, 1957) . Note that, although the local MDP dissimilarity d M M is asymmetric, ∆ M M (s, a) is a pseudo-metric, hence the name pseudo-Lipschitz continuity. Similar results for the value function of a fixed policy and the optimal value function V * M can easily be derived, as well as a global pseudo-Lipschitz continuity property (Appendix, Sections D and E). Thus, overall, the optimal Q-functions of two close MDPs (in the sense of Equation 1) are themselves close to each other. A direct consequence in Lifelong RL is that previously solved tasks can help bound the value function of a new task. Even a partially learned Q-function can be used for that purpose if error bounds are known or if it provably overestimates the true Q * . The next section exploits this property to build a PAC-MDP algorithm that performs provably non-negative transfer between successive tasks and accelerates learning.

4. TRANSFER USING THE LIPSCHITZ CONTINUITY:

A purpose of value transfer, when interacting online with a new MDP, is to initialize the value function and drive the exploration to accelerate learning. We aim to exploit value transfer in a method guaranteeing three conditions: C1. the resulting algorithm is PAC-MDP (Strehl et al., 2009) ; C2. the transfer accelerates learning; C3. the transfer is non-negative. From Proposition 1, one can naturally define a local upper bound on the optimal Q-function of an MDP given the optimal Q-function of another MDP. Definition 2. Given two tasks M and M , for all (s, a) ∈ S × A, the Lipschitz upper bound on

EQUATION

The optimism in the face of uncertainty principle leads to consider that the long-term expected return from any state is the 1 1-γ maximum return, unless proven otherwise. The RMax algorithm (Brafman and Tennenholtz, 2002) in particular explores an MDP so as to shrink this upper bound. RMax is a model-based, online RL algorithm with PAC-MDP guarantees (Strehl et al., 2009) which means that convergence to near-optimal policy is guaranteed in a polynomial number of steps. It relies on an optimistic model initialization that yields an optimistic upper bound U on the optimal Q-function, then acts greedily w.r.t. U . By default, it takes the maximum value U (s, a) = 1 1-γ but any tighter upper bound is admissible. Thus, shrinking U with Equation 4 is expected to improve the learning speed for new tasks in Lifelong RL.

In RMax, during the resolution of a task M , S × A is split into a subset of known state-action pairs K and its complement K c of unknown pairs. A state-action pair is known if the number of collected reward and transition samples allows estimating an -accurate model in L 1 -norm with probability higher than 1 -δ. We refer to and δ as the RMax precision parameters. This translates into a threshold n known on the number of visits n(s, a) to a pair s, a that are necessary to reach this precision. Given the experience of a set of m MDPs M = { M1 , . . . , Mm }, we define the total bound as the minimum over all the Lipschitz bounds induced by each previous MDP.

Proposition 2. Given a partially known task M = R, T , the set of known state-action pairs K, and the set of Lipschitz bounds on Q * M induced by previous tasks U M1 , . . . , U Mm , the function Q defined below is an upper bound on Q * M for all s, a ∈ S × A.

EQUATION

with U (s, a) = min 1 1-γ , U M1 (s, a), . . . , U Mm (s, a) .

Traditionally in RMax, Equation 5 is solved to a precision Q via Value Iteration. This yields a function Q that is a valid heuristic (provable upper bound on Q * M ) for the exploration of MDP M .

4.1. A TRACTABLE UPPER BOUND ON Q *:



M:

The key issue addressed in this Section is how to actually compute U (s, a). Consider two tasks M and M , on which vanilla RMax has been applied, yielding the respective sets of known state-action pairs K and K, along with the learned models M = T , R and M = T, R , and the upper bounds Q and Q respectively on Q * M and Q * M . Equation 5 allows the transfer of knowledge from M to M if U M (s, a) can be computed. Unfortunately, the true optimal value functions, transition and reward models, necessary to compute U M , are unknown. Thus, we propose to compute a looser upper bound based on the learned models and value functions. First, we provide an upper bound DM M on the pseudo metric between models M and M . Proposition 3. Given two tasks M and M , K and K the respective sets of state-action pairs where their models are known with accuracy in L 1 -norm with probability at least 1 -δ,

Pr DM M (s, a) ≥ D M M γV * M (s, a) ≥ 1 -δ

with the following definition of the upper bound on the pseudo-metric between models DM M :

EQUATION

where

B = 1 + γ max s V (s ) .

This upper bound DM M on the distance between MDPs can be calculated analytically (see Appendix, Section H). The magnitude of the B term is controlled by . In the case where no information is available on the maximum value of V , B = 1-γ . measures the accuracy with which the tasks are known: the smaller , the tighter the B bound. Note that V is used as an upper bound on the true V * M . In many cases, max s V * M (s ) M with probability at least 1 -δ:

EQUATION

Similarly as in Proposition 3, the condition γ(1 + ) < 1 illustrates the fact that for a large return horizon (large γ), a high accuracy (small ) is needed for the bound to be computable. Finally, a tractable upper bound on Q * M given M with high probability is given by

EQUATION

And the associated upper bound on U (s, a) (Equation 5) given previous tasks

EQUATION

This upper bound can be used to transfer knowledge from a partially solved task to a target task. If Û (s, a) ≤ 1 1-γ for some (s, a) pairs, then the convergence rate can be improved. As complete knowledge of both tasks is not needed, it can be applied online in a Lifelong RL setting. In the next section, we explicit an algorithm that leverages this value transfer method. 

Q ← UpdateQ( M, T , R) Save M = T , R, K, Q in M Function UpdateQ( M, T , R): for M ∈ M do Compute DM M and D M M (Eq. 6)

Compute d M M and dM M (DP on Eq. 7) Compute Û M (Eq. 8)

Compute Û (Eq. 9) Compute and return Q (DP on Eq. 5 using Û )

4.2. LIPSCHITZ RMAX:

In Lifelong RL, MDPs are encountered sequentially. Applying RMax to task M yields the set of known state-action pairs K, the learned models T and R, and the upper bound Q on Q * M . Saving this information when the task changes allows to compute the upper bound of Equation 9for the new task, and to use it to shrink the optimistic heuristic of RMax. This effectively transfers value functions between tasks based on task similarity. As the new task is explored online, the task similarity is progressively assessed with better confidence, refining the values of DM M , d M M and eventually Û , allowing for more efficient transfer where the task similarity is appraised. The resulting algorithm, Lipschitz RMax (LRMax), is presented in Algorithm 1. To avoid ambiguities with M, we use M to store learned features ( T , R, K, Q) about previous MDPs. In a nutshell, the behavior of LRMax on a given task M is precisely that of RMax, but with a tighter admissible heuristic Û that becomes better as the new task is explored (while this heuristic remains constant in vanilla RMax). LRMax is PAC-MDP (Condition C1) as stated in Propositions 5 and 6 below. With S = |S| and A = |A|, the sample complexity of vanilla RMax is Õ(S 2 A/( 3 (1 -γ) 3 )), which is improved by LRMax in Proposition 5 and meets Condition C2. Finally Û is a proved upper bound with high probability on Q * M , which avoids negative transfer and meets Condition C3. Proposition 5 (Sample complexity (Strehl et al., 2009) ). With probability 1 -δ, the greedy policy w.r.t. Q computed by LRMax achieves an -optimal return in MDP M after

Õ S|{s, a ∈ S × A | Û (s, a) ≥ V * M (s) -}| 3 (1 -γ) 3

samples (when logarithmic factors are ignored), with Û defined in Equation 9 a non-static, decreasing quantity, upper bounded by 1 1-γ .

Consequently from Proposition 5, the sample complexity of LRMax is no worse than that of RMax. Proposition 6 (Computational complexity). The total computational complexity of Lipschitz RMax is

Õ τ + S 2 A 2 (S + log(A))(2N + 1) (1 -γ) log 1 Q (1 -γ)

with τ the number of interaction steps, Q the precision of value iteration and N the number of tasks.

4.3. REFINING LRMAX BOUNDS WITH MAXIMUM MODEL DISTANCE:

LRMax relies on upper bounds on the local distances between tasks (Equation 7). The quality of the Lipschitz bound on Q * M greatly depends on the quality of those estimates and can be improved accordingly. We discuss two methods to provide finer estimates.

First, from the definition of D M M γV * M (s, a), it is easy to show that model pseudo-distances are always upper bounded by 1+γ 1-γ . However, in practice, the tasks experienced in Lifelong RL might not cover the full span of possible MDPs and may be systematically closer to each other than 1+γ 1-γ . For instance, the distance between two games in the Arcade Learning Environment (ALE) (Bellemare et al., 2013) , is smaller than the maximum distance between any two MDPs defined on the common state-action space of the ALE (extended discussion in Appendix, Section L). Let , and thus a smaller Û which allows transfer if it is lesser than1 1-γ . Consequently, such an upper bound D max can make a difference between successful and unsuccessful transfer, even if its value is of little importance. Conversely, setting a value for D max quantifies the distance between MDPs where transfer is efficient.

D max (s, a) max M, M ∈M 2 {D M M γV * M (s,

Furthermore, one can estimate online the value of D max (s, a), lifting the previous hypothesis of available prior knowledge. One can build an empirical estimate of the maximum model distance at s, a: Proposition 7. Consider an algorithm producing -accurate in L 1 -norm model estimates with probability at least 1 -δ for a subset of S × A after interacting with an MDP. For all s, a ∈ S × A, after sampling m tasks with p min = min M ∈M Pr(M ), the following lower bound holds:

Dmax (s, a) max M, M ∈ M2 { DM M (s,

Pr Dmax (s, a) ≥ D max (s, a) ≥ 1 -2(1 -p min ) m + (1 -2p min ) m .

The assumption of a lower bound p min on the sampling probability of a task implies that M is finite and is commonly seen as a non-adversarial task sampling strategy (Abel et al., 2018) .

5. EXPERIMENTS:

The experiments reported here 1 illustrate how 1) LRMax allows for early performance increase in Lifelong RL by efficiently transferring knowledge between tasks; 2) the Lipschitz bound of Equation 8 improves the sample complexity compared to RMax by providing a tighter upper bound on Q * . Graphs are displayed with 95% confidence intervals. Information in line with the Machine Learning Reproducibility Check-list (Pineau, 2019) is documented in the Appendix, Section Q.

We evaluate different variants of LRMax in a Lifelong RL experiment. The RMax algorithm will be used as a no-transfer baseline. LRMax(x) denotes Algorithm 1 with prior D max = x. MaxQInit denotes the MAXQINIT algorithm from Abel et al. (2018) , consisting in a state-of-the art PAC-MDP algorithm achieving transfer with PAC guarantees. Both LRMax and MaxQInit algorithms achieve value transfer by providing a tighter upper-bound on Q * than 1 1-γ . Computing both upper-bounds and taking the minimum results in combining the two approaches. We include such a combination in The environment we used in all experiments is a variant of the "tight" environment used by Abel et al. (2018) . This is a 11 × 11 grid-world, the initial state is in the centre, actions are the cardinal moves (Appendix, Section M). The reward is zero everywhere except for the three goal cells in the upper-right corner. Each time a task is sampled, a new reward value is drawn from [0.8, 1] for each of the three goal cells and a probability of slipping (performing a different action than the one selected) is picked in [0, 0.1]. Hence, tasks have different reward and transition functions. We sample 15 tasks in sequence among a pool of 5 possible different sampled tasks. Each is run for 2000 episodes of length 10. The operation is repeated 10 times to provide narrow confidence intervals. We used n known = 10, δ = 0.05 and = 0.01 (discussion in Appendix, Section P). We drew tasks from a finite set of five MDPs. This allows the application of MaxQInit and the subsequent comparison below. Note, however, that LRMax does not require the set of MDPs to be finite, which is a noticeable advantage in applicability. Other lifelong RL experiments are reported in the Appendix, Section N.

The results are reported in Figure 1 . Figure 1a displays the discounted return for each task, averaged across episodes. Similarly, Figure 1b displays the discounted return for each episode, averaged across tasks (same color code as Figure 1a ). Figure 1c displays the discounted return for five specific instances, detailed below. To avoid inter-task disparities, all the aforementioned discounted returns are displayed relatively to an estimator of the optimal expected return for each task. For readability purposes, Figures 1b and 1c display a moving average over 100 episodes. Figure 1d reports the benefits of various values of D max on the algorithmic properties.

In Figure 1a , we first observe that LRMax benefits from the transfer method, as the average discounted return increases as more tasks are experienced. Moreover, this advantage appears as early as the second task. Conversely, the MaxQInit algorithm needs to wait for task 12 before benefiting from transfer. As suggested in Section 4.3, various amounts of prior allow the LRMax transfer method to be more or less efficient: a smaller known upper-bound D max on DM M causes a larger discounted return gain. Combining both approaches in the LRMaxQInit algorithm outperforms all other methods. Episode-wise, we observe in Figure 1b that the LRMax transfer method allows for faster convergence, hence decreases the sample complexity. Interestingly, LRMax features three stages in the learning process. 1) The first episodes are characterized by a direct exploitation of the transferred knowledge, causing these episodes to yield high payoff. This is due to the combined facts that the Lipschitz bound of Equation 8 is larger on promising regions of S × A seen on previous tasks and the fact that LRMax acts greedily w.r.t. that bound. 2) This high performance regime is followed by the exploration of unknown regions of S × A, in our case yielding low returns. Indeed, as promising regions are explored first, the bound becomes tighter for the corresponding state-action pairs, enough for the Lipschitz bound of unknown pairs to become larger, thus driving the exploration towards low payoff regions. Such regions are quickly identified and never revisited thereafter. 3) Eventually, LRMax stops exploring and converges to the optimal policy. Importantly, in all experiments, LRMax never features negative transfer as supported by the provability of the Lipschitz upper-bound with high probability. This is indeed demonstrated by the fact that it is at least as efficient in learning as the no-transfer RMax baseline.

Figure 1c displays the collected returns of RMax, LRMax(0.1), and MaxQInit for specific tasks. We observe that LRMax benefits from the transfer as early as task 2, where the aforementioned 3-stages behavior is visible. Again, MaxQInit needs to wait for task 12 to leverage the transfer method. However, the bound it provides are tight enough to allow for almost zero exploration of the task.

In Figure 1d , we display the following quantities for various values of D max : ρ Lip , is the ratio of the time the Lipschitz bound was tighter than the RMax bound 1 1-γ ; ρ Speed-up , is the relative gain of time steps before convergence when comparing LRMax to RMax. This quantity is estimated based on the last updates of the empirical model M ; ρ Return , is the relative total return gain on 2000 episodes of LRMax w.r.t. RMax. First, we observe an increase of ρ Lip as D max becomes tighter. This means that the Lipschitz bound of Equation 8 becomes effectively smaller than 1 1-γ . This phenomenon leads to faster convergence, indicated by ρ Speed-up . Eventually, this increased convergence rate allows for a net total return gain, illustrated by the increase of ρ Return .

Overall, in this analysis, we have showed that LRMax benefits from an enhanced sample complexity thanks to the value transfer method. The knowledge of a prior D max further increases this benefit. The method is comparable to the MaxQInit method and has some advantages such as the early fitness for use and the applicability to infinite sets of tasks. Moreover, the transfer is non-negative while preserving the PAC-MDP guarantees of the algorithm. Additionally to the analysis performed here, we show in the Appendix, Section O that, when provided with any prior knowledge D max , LRMax increasingly stops using this prior as the task is explored. This confirms the claim of section 4.3 that providing D max enables transfer even if it's value is of little importance.

6. CONCLUSION:

We have studied theoretically the Lipschitz continuity property of the optimal Q-function in the MDP space. This led to a local Lipschitz continuity result, establishing that the optimal Q-functions of two close MDPs are themselves close to each other. This distance between Q-functions can be computed by Dynamic Programming. We then proposed a value-transfer method using this continuity property with the Lipschitz RMax algorithm, practically implementing this approach in the Lifelong RL setting. The algorithm preserves PAC-MDP guarantees, accelerates the learning in subsequent tasks and performs non-negative transfer. Potential improvements of the algorithm were discussed in the form of prior knowledge introduction on the maximum distance between models and online estimation with high probability of this distance. We showcased the algorithm in lifelong RL experiments and demonstrated empirically its ability to accelerate learning. The results also confirm that no negative transfer occurs, regardless of parameter settings. It should be noted that our approach can directly extend other PAC-MDP algorithms (Szita and Szepesvári, 2010; Rao and Whiteson, 2012; Pazis et al., 2016; Dann et al., 2017) to the Lifelong setting. In hindsight, we believe this contribution provides a sound basis to non-negative value transfer via MDP similarity, a development that was lacking in the literature. Key insights for the practitioner lie both in the theoretical analysis and in the practical derivation of a transfer scheme that achieves non-negative transfer with PAC guarantees.

APPENDIX A A NEGATIVE TRANSFER EXAMPLE:

In their paper, Song et al. (2016) propose two transfer methods based on the metric between MDPs they introduce, stemming from the bi-simulation metric introduced by Ferns et al. (2004) . The intuition is that, for a new target task, the value function of the closest source task in terms of that metric is used as an initialization. However, if no similar source task is available, using the closest task's value function as an initialization can lead to negative transfer. We here understand negative transfer as the fact that it prevents a learning algorithm to converge to the optimal policy while interacting with a new task. We make the hypothesis that the learning algorithm acts greedily w.r.t. the current Q-value function. This is for example the behavior of the RMax algorithm (Brafman and Tennenholtz, 2002) . We now illustrate a negative transfer case with an example. Let us consider the 2-states MDP of Figure 2 . We assume that the transitions are deterministic and the initial state is

s 0 s 1 a 0 a 0 a 1 a 1 Figure 2: 2-states MDP

always s 0 . In the first MDP M 1 ∈ M, the reward is 0 everywhere except for R a0 s0 = 1. In the second MDP M 2 ∈ M, the reward is 0 everywhere except for R a1 s1 = 1. With a discount factor γ = 0.9, the value functions and Q-functions of both MDPs are summarized in Table 3 Using the weighted Q transfer

V * M1 (•) Q * M1 (•, a 0 ) Q * M1 (•, a 1 ) V * M2 (•) Q * M2 (•, a 0 ) Q * M2 (•,

M2:

(s 0 , a 0 ) = 2.03

Q transfer M2 (s 0 , a 1 ) = 2.25 Q transfer M2 (s 1 , a 0 ) = 2.5 Q transfer M2 (s 1 , a 1 ) = 2.03

First, Q transfer

does not respect the principle of "optimism under the face of uncertainty" that often results in sound and efficient exploration (Strehl et al., 2009; Brafman and Tennenholtz, 2002; Sutton and Barto, 1998) . Further, a greedy policy w.r.t. Q transfer M2 would never discover the state-action pair s 1 , a 1 in M 2 which is the maximum-reward pair. Instead, the agent would go from s 0 to s 1 and perform self-loops thereafter.

As a conclusion, this negative transfer example motivates the need for distance between MDPs not only to account for the best-source task to use for transfer but also to discourage the transfer when the distance is too high. The approach we develop in this paper used the distance to build optimistic upper-bounds on the Q-function. Those upper-bounds are simply of no use when the distance is too high which is equivalent as avoiding transfer.

B DISCUSSION ON METRICS AND RELATED NOTIONS:

A metric on a set X is a function m : X × X → R which has the following properties for any x, y, z ∈ X:

1. m(x, y) ≥ 0, 2. m(x, y) = 0 ⇔ x = y, 3. m(x, y) = m(y, x), 4. m(x, z) ≤ m(x, y) + m(y, z).

With only m(x, x) = 0 instead of property 2, m would be a pseudo-metric. Without property 3, one has a quasi-metric. Without property 3 and 4, and when X is a set of probability measures, one has a divergence.

In Definition 1, D M M,f (s, a) is indeed a pseudo-metric over MDPs since the choice of f can lead to a zero distance between different models.

The local MDP dissimilarity between MDPs d M:

M (s, a) of Proposition 1 does not respect properties 2 and 3, hence the name dissimilarity. The ∆ M M (s, a) min d M M (s, a), d M M (s, a) quantity, however, regains property 3 and is hence a pseudo-metric. An important consequence is that Proposition 1 is "in the spirit" of a Lipschitz continuity theorem but cannot be called as such, hence the name pseudo-Lipschitz continuity. Proof of Lemma 1. The proof follows closely that in Puterman (2014) that proves that the Bellman operator over value functions is a contraction mapping. Let d 1 and d 2 be two functions from S × A to R and let L be the functional operator that maps any function d : Proof of Proposition 1. The proof is by induction. The Value Iteration sequence of iterates

The same goes for the global dissimilarity d:

M M = 1 1-γ max s,a∈S×A D M M,γV * M (s,

S × A → R to Ld : s, a → D M M,γV * M (s, a) + γ s T a ss max a d(s , a ). Then Ld 1 (s, a) -Ld 2 (s, a) = γ s T a ss [max a d 1 (s , a ) -max a d 2 (s , a )]. But max a d 1 (s , a ) -max a d 2 (s , a ) ≤ max a [d 1 (s , a ) -d 2 (s , a )] ≤ d 1 -d 2 ∞ . And so Ld 1 -Ld 2 ∞ ≤ γ d 1 -d 2 ∞ . Since γ < 1, L is a contraction mapping in the metric space (S × A, • ∞ ).

(Q n M ) n∈N for task M is: Q 0 M (s, a) = 0, ∀s, a ∈ S × A Q n+1 M (s, a) = R a s + γ s ∈S T a ss max a ∈A Q n M (s , a ), ∀s, a ∈ S × A. It is obvious that Q 0 M (s, a) -Q 0 M (s, a) ≤ d M M (s, a). Suppose that |Q n M (s, a) -Q n M (s, a)| ≤ d M M (s, a). Then: Q n+1 M (s, a) -Q n+1 M (s, a) = R a s -Ra s + γ s ∈S T a ss max a ∈A Q n M (s , a ) -T a ss max a ∈A Q n M (s , a ) ≤ R a s -Ra s + γ s ∈S T a ss max a ∈A Q n M (s , a ) -T a ss max a ∈A Q n M (s , a ) ≤ R a s -Ra s + γ s ∈S max a ∈A Q n M (s , a ) T a ss -T a ss + γ s ∈S T a ss max a ∈A Q n M (s , a ) -max a ∈A Q n M (s , a ) ≤ R a s -Ra s + s ∈S γV * M (s ) T a ss -T a ss + γ s ∈S T a ss max a ∈A Q n M (s , a ) -Q n M (s , a ) ≤ D M M,γV * M (s, a) + γ

E GLOBAL PSEUDO-LIPSCHITZ CONTINUITY RESULT:

A consequence of Proposition 1 is a global pseudo-Lipschitz continuity property: Proposition 8 (Global pseudo-Lipschitz continuity). For two MDPs M , M , for all (s, a) ∈ S × A,

|Q * M (s, a) -Q * M (s, a)| ≤ min δ M M , δ M M , with δ M M 1 1 -γ max s,a∈S×A D M M γV * M (s, a) . (10)

Despite being interesting from a theoretical perspective, we do not use this result for transfer because it is impractical to compute. Indeed, estimating the maximum in Equation 10 might be as hard as solving both MDPs (which, when it happens, is too late for transfer to be useful).

Proof. The proof is by induction and reuses the notations introduced in the proof of Proposition 1. It is immediate that

Q 0 M (s, a) -Q 0 M (s, a) ≤ d M M , and Q 0 M (s, a) -Q 0 M (s, a) ≤ d M M .

Hence, the result holds for n = 0. Let us suppose that

Q n M (s, a) -Q n M (s, a) ≤ d M M , and Q n M (s, a) -Q n M (s, a) ≤ d M M .

Then,

Q n+1 M (s, a) -Q n+1 M (s, a) ≤ D M M,γV * M (s, a) + γ s ∈S T a ss max a ∈A Q n M (s , a ) -Q n M (s , a ) ≤ max s,a∈S×A D M M,γV * M (s, a) + γ s ∈S T a ss 1 1 -γ max s,a∈S×A D M M,γV * M (s, a) ≤ max s,a∈S×A D M M,γV * M (s, a) 1 + γ 1 -γ ≤ d M M F PROOF OF PROPOSITION 2

Proof. The result is clear for all s, a / ∈ K since the Lipschitz bounds are provably greater than Q * M . For s, a ∈ K, the result is by induction. Let us consider the Dynamic Programming (Bellman, 1957) sequences converging to Q * M and U at rank n whose definitions follow: a) . Suppose the property true at rank n and consider rank n + 1:

Q * M,0 (s, a) = 0 Q * M,n (s, a) = R a s + γ s T a ss max a Q * M,n-1 (s , a ) U 0 (s, a) = 0 U n (s, a) = R a s + γ s T a ss max a U n-1 (s , a ) Obviously, Q * M,0 (s, a) ≤ U 0 (s,

Q * M,n+1 (s, a) -U n+1 (s, a) = γ s T a ss max a Q * M,n (s , a ) -max a U n (s , a ) ≤ γ s T a ss max a Q * M,n (s , a ) -U n (s , a ) ≤ 0

Which concludes the proof by induction. The result holds by passage to the limit since the considered Dynamic Programming sequences converge to the true functions.

G PROOF OF PROPOSITION 3:

Consider two tasks M = T, R and M = T , R , with K and K the respective sets of state-action pairs where their learned models M = T , R and M = T, R are known with accuracy in L 1 -norm with probability at least 1 -δ, i.e. we have that,

EQUATION

)

EQUATION

and the same goes for M and its learned model M . We state the result for each one of the three cases 1) s, a ∈ K ∩ K, 2) s, a ∈ K ∩ Kc and 3) s, a ∈ K c ∩ Kc , the case s, a ∈ K c ∩ K being the symmetric of case 2). 1) If s, a ∈ K ∩ K, then properties 11 and 12 hold for both R, T with R, T and R, T with R, T . We have by definition:

EQUATION

)

The first term of the RHS of Equation 13respects the following sequence of inequalities with probability at least 1 -δ:

EQUATION

)

The second term of the RHS of Equation 13respects the following sequence of inequalities with probability at least 1 -δ:

EQUATION

)

Summation of Equations 14 and 15 reveals DM M (s, a) = | Ra s -Ra s | + γ s ∈S V (s )| T a ss -T a ss | on the RHS of the inequality. Remarking this, we can upper-bound the model pseudo-distance of Equation 13 by the expected quantity with probability at least 1 -δ, proving the Proposition for case 1):

D M M γV * M (s, a) ≤ DM M (s, a) + 2 1 + γ max s V (s ) .

2) If s, a ∈ K ∩ Kc , then properties 11 and 12 hold for R, T with R, T only. Similarly to the proof of case 1), we upper bound sequentially the two terms of the RHS of Equation 13. With probability at least 1 -δ, we have the following:

EQUATION

)

Similarly, with probability at least 1 -δ, we have:

EQUATION

Combining inequalities 16 and 17, we get the following with probability at least 1 -δ, noticing D M M γV * M (s, a) on the LHS:

D M M γV * M (s, a) ≤ max μ∈M D M μ γ V (s, a) + 1 + γ max s V (s ) ,

which is the expected result.

3) If s, a ∈ K c ∩ Kc , then properties 11 and 12 do not hold. In such a case, the result

D M M γV * M (s, a) ≤ max µ,μ∈M 2 D µμ γ V (s, a)

is straightforward by remarking that V * M (s) ≤ V (s) with probability at least 1 -δ.

H ANALYTICAL CALCULATION OF DM M IN PROPOSITION 3:

Consider two tasks M = T, R and M = T , R , with K and K the respective sets of state-action pairs where their learned models M = T , R and M = T, R are known with accuracy in L 1 -norm with probability at least 1 -δ. We note V max , a known upper-bound on the maximum achievable value. In the worst case where one does not have any information on the value of V max , one can always set V max = 1 1-γ . We recall the definition of the upper bound on the pseudo-metric between models:

EQUATION

with B = 1 + γ max s V (s ) and D M M f defined as in Equation 13. We detail the computation of DM M (s, a) for each cases 1) s, a ∈ K ∩ K, 2) s, a ∈ K ∩ Kc (the s, a ∈ K c ∩ K is symmetric to this one), and 3) s, a ∈ K c ∩ Kc . Recall that we consider a finite, countable, state-action space S × A.

1) If s, a ∈ K ∩ K, we have DM M (s, a) = D M M γ V (s, a) + 2B = | Ra s -Ra s | + γ s ∈S V (s )| T a ss -T a ss | + 2 1 + γ max s V (s ) .

Since s, a is a known state-action pair, everything is known and computable in this last equation. Note that max s V (s ) can be tracked along the updates of V and thus its computation does not induce any additional complexity.

2) If s, a ∈ K ∩ Kc , we have

DM M (s, a) = max μ∈M D M μ γ V (s, a) + B = max Ra s , T a ss | Ra s -Ra s | + γ s ∈S V (s )| T a ss -T a ss | + 1 + γ max s V (s ) , = max r∈[0,1] | Ra s -r| + γ max t∈[0,1] |S| t=1 s ∈S V (s )| T a ss -t s | + 1 + γ max s V (s ) .

First, we have max

r∈[0,1] | Ra s -r| = max Ra s , 1 -Ra s .

Maximizing the max t∈[0,1] |S| term is maximizing a convex combination of V (whose values are all positive) whose terms are not independent (since the t s terms should sum to one). This is easily cast as a linear programming problem. A straightforward (simplex-like) resolution procedure consists in progressively adding mass on the terms that will maximize the convex combination as follows:

• t s = 0, ∀s ∈ S • l = Sort states by decreasing value of V

• While s∈S t(s) < 1 -s = pop first state in l -Assign t(s ) ← arg max t∈[0,1] | T a ss -t| to s (note that t s ∈ {0, 1}) -If s∈S t s > 1, then t s ← 1 -s∈S\s t(s)

This allows calculating the maximum over transition models.

There is however a simpler computation that almost always yields the same result (when it does not, it provides an upper bound) and does not require the burden of the previous procedure. Consider the subset of states for which V (s ) = max s V (s) (often these are states in Kc ). Among those states, let us suppose there exists s + unreachable from s, a, according to T , that is T a ss + = 0. If M has not been fully explored, as is often the case in RMax, there may be many such states. Then the distribution t with all its mass on s + is a maximizer of the max t∈[0,1] |S| term. Conversely, if such a state does not exist (that is, if for all such states T a ss + > 0), then max s V (s) is an upper bound on the max t∈[0,1] |S| term. Therefore:

max t∈[0,1] |S| s ∈S V (s )| T a ss -t s | ≤ max s V (s)

, with equality in many cases.

3) If s, a ∈ K c ∩ Kc , the resolution is trivial and we have

DM M (s, a) = max µ,μ∈M 2 D µμ γ V (s, a) = max R a s ,T a ss , Ra s , T a ss |R a s -Ra s | + γ s ∈S V (s )|T a ss -T a ss | = max r,r∈[0,1] |r -r| + γ max t, t∈[0,1] |S| t=1 t=1 s ∈S V (s )|t s -ts | = 1 + γ max s V (s).

I PROOF OF PROPOSITION 4:

Lemma 2. Given two tasks M and M , K the set of state-action pairs for which R, T is known with accuracy in L 1 -norm with probability at least 

1 -δ. If γ(1 + ) < 1,

≤ γ(1 + ) d 1 -d 2 ∞ .

If s, a / ∈ K, we have

Ld 1 (s, a) -Ld 2 (s, a) = γ max s ,a d 1 (s , a ) -max s ,a d 2 (s , a ) ≤ γ max s ,a (d 1 (s , a ) -d 2 (s , a )) = γ(1 + ) d 1 -d 2 ∞ .

In both cases, J PROOF OF PROPOSITION 6

Ld 1 -Ld 2 ∞ ≤ γ(1 + ) d 1 -d 2 ∞ . If γ(1 + ) < 1, L is a

Proof. We follow the proof of the computational complexity of RMax proposed by Strehl et al. (2009) . The cost of Lipschitz RMax is constant on most time steps since the action is greedily chosen w.r.t. the upper-bound on the optimal Q-value function which is a lookup table. When updating a new state-action pair (labelling it as a known pair), the algorithm performs 2N DP computations to update the Lipschitz bounds plus one DP computation to update the total-bound. The cost of one DP computation is given by (Strehl et al., 2009) :

Õ SA(S + log(A)) 1 1 -γ log 1 (1 -γ)

The result comes out by remarking that at most SA state-action pairs are updated, each resulting in (N + 1) DP computations.

K PROOF OF PROPOSITION 7:

Proof. Consider a fixed state-action pair s, a ∈ S × A. For two sampled tasks M, M ∈ M2 , we assume our algorithm to provide an upper-bound on D M Hence, with probability at least 1 -δ, max

M, M ∈ M2 DM M (s, a) ≥ max M, M ∈ M2 D M M γV * M (s, a)

i.e. Dmax (s, a) ≥ D max (s, a). In turn, the event of underestimating D max (s, a) occurs only if the two tasks, that we note

M * 1 , M * 2 ∈ M 2 , maximizing M, M → D M M γV *

M (s, a), are not sampled, i.e. do not belong to M . M * 1 and M * 2 are not necessarily unique, but they could be. Since we aim at deriving a lower bound on the probability of sampling M * 1 and M * 2 , we consider the worst case where they are unique. The probability P of sampling one particular task, whose sampling probability is p, after i samples, is given by the cumulative distribution function of the geometric distribution and is p(1 -p) i-1 . Consequently, if the sampling probability p of this task is lower bounded by p min , the quantity p min (1 -p min ) i-1 lower bounds P . Let us write X the random variable of the number of samples required for sampling either M * 1 or M * 2 for the first time. By considering that the sampling probability of either sampling M * 1 or M * 2 is lower bounded by 2p min , we follow the same reasoning as for P and obtain that :

Pr(X = i) ≥ 2p min (1 -2p min ) i-1

Let us write Y the random variable of the number of samples required for sampling the remaining task for the first time. We have the following result using the geometric distribution for the conditional Pr(Y = k|X = i):

Pr(Y = k) = k-1 i=1 Pr(Y = k, X = i) = k-1 i=1 Pr(Y = k|X = i)Pr(X = i) ≥ 2 k-1 i=1 (1 -p min ) k-i-1 (1 -2p min ) i-1 p 2 min (19)

Pr(Y = k) is the probability of first success at step k. For Dmax (s, a) to estimate D max (s, a) in m steps, we require that this success occurs any time during the first m steps, so we have:

Pr( Dmax (s, a) ≥ D max (s, a)) = m k=2 Pr(Y = k)

Using Equation 19, we can deduce our result when remarking that necessarily p min ≤ 1/2: But this assumes any transition or reward model can define M . In other words, the maximization is made on the whole set of possible MDPs. To illustrate why this is too naive, consider a game within the Arcade Learning Environment (Bellemare et al., 2013) . We, as humans, have a strong bias concerning similarity between environments. If the game changes, we still assume groups of pixels will move together on the screen as the result of game actions. For instance, we generally discard possible new games M that "teleport" objects across the screen without physical considerations. We also discard new games that allow transitions from a given screen to another screen full of static. These examples illustrate why the knowledge of D max is very natural (and also why its precise value may be irrelevant). The same observation can be made for the "tight" experiment of Section 5; the set of possible MDPs is restricted by some implicit assumptions that constrain the maximum distance between tasks. For instance, in these experiments, all transitions move to a neighboring state and never "teleport" the agent to the other side of the gridworld. Without the knowledge of D max , LRMax assumes such environments are possible and therefore transfer values very cautiously. Overall, the experiments of Section 5 confirm this important insight: safe transfer occurs slowly if no a priori is given on the maximum distance between MDPs. On the contrary, the knowledge of D max allows a faster and more efficient transfer between environments.

Pr( Dmax (s, a) ≥ D max (s, a)) ≥ 2p 2 min m k=2 k-1 i=1 (1 -p min ) k-i-1 (1 -2p min ) i-1 ≥ 2p 2 min m-2 k=0 k i=0 (1 -p min ) k-i (1 -2p min ) i ≥ 2p 2 min m-2 k=0 (1 -p min ) k k i=0 1 -2p min 1 -p min i ≥ 2p 2 min m-2 k=0 (1 -p min ) k 1 p 1 -p min - (1 -2p min ) k+1 (1 -p min ) k ≥ 2p min m-2 k=0 (1 -p min ) k+1 -(1 -2p min ) k+1 ≥ 2p min (1 -p min ) 1 -(1 -p min ) m-1 1 -(1 -p min ) -2p min (1 -2p min ) 1 -(1 -2p min ) m-1 1 -(1 -2p min ) ≥ 1 -2(1 -p min ) m + (1 -2p min ) m

M THE "TIGHT" ENVIRONMENT USED IN EXPERIMENTS OF SECTION 5:

The tight environment is a 11 × 11 grid-world illustrated in Figure 4 . The initial state of the agent is the central cell displayed with an "S". The actions are moving 1 cell in one of the four cardinal directions. The reward is 0 everywhere, except for executing an action in one of the three teal cells in the upper-right corner. Each time a task is sampled, a slipping probability of executing another action as the one selected is drawn in [0, 1] and the reward received in each one of the teal cells is picked in [0.8, 1.0].

20. cells:



S G:

Figure 5 : The corridor grid-world environment. 

N ADDITIONAL LIFELONG RL EXPERIMENTS:

We ran additional experiments on the corridor grid-world environment represented in Figure 5 . The initial state of the agent is the central cell labeled with the letter "S". The actions are {left, right} and the goal is to reach the cell labeled with the letter "G" on the extreme right. A reward R > 0 is received when reaching the goal and 0 otherwise. At each new task, a new value of R is sampled in [0.8, 1]. The transition function is fixed and deterministic.

The key insight in this experiment is not to lose time exploring the left part of the corridor. We ran 20 episodes of 11 time steps for each one of the 20 sampled tasks. Results are displayed in Figure 6a and 6b, respectively for the average relative discounted return over episodes and over tasks. Similarly as in Section 5, we observe in Figure 6a that LRMax benefits from the transfer method as early as the second task. The MaxQInit algorithm benefits from the transfer from task number 12. Prior knowledge D max decreases the sample complexity of LRMax as reported earlier and the combination of LRMax with MaxQInit outperforms all other methods by providing a tighter upper-bound on the optimal Q-value function. This decrease of sample complexity is also observed in the episode-wise display of Figure 6b where the convergence happens more quickly on average for LRMax and even more for MaxQInit. This figure allows to see the three learning stages of LRMax reported in Section 5.

We also ran lifelong RL experiments in the maze grid-world of Figure 7 . The tasks consists in reaching the goal cell labeled with a "G" while the initial state of the agent is the central cell, labeled with an "S". Two walls configurations are possible, yielding two different tasks with probability 1 2 of being sampled in the lifelong RL setting. The first task corresponds to the case where orange walls are actually walls and green cells are normal white cells where the agent can go. The second task is the converse, where green walls are walls and orange cells are normal white cells. We run 100 episodes of length 15 time steps and sample a total of 30 different tasks. Results can be found in Figure 8 . In this experiment, we observe the increase of performance of LRMax as the value of D max decreases. The three stages behavior of LRMax reported in Section 5 does not appear in this case. We tested the performance of using the online estimation of the local model distances of Proposition 7 in the algorithm referred by LRMax in Figure 8 . Once enough tasks have been sampled, the estimate on the model local distance is used with high confidence on its value and refines the upper-bound computed analytically in Equation 6. Importantly, this instance of LRMax achieved the best result in this particular environment, demonstrating the usefulness of this result. This method being similar Q INFORMATIONS ABOUT THE MACHINE LEARNING REPRODUCIBILITY CHECKLIST For the experiments run in Section 5, the computing infrastructure used was a laptop using a single 64-bit CPU (model: Intel(R) Core(TM) i7-4810MQ CPU @ 2.80GHz). The collected samples sizes and number of evaluation runs for each experiment is summarized in Table 1 The displayed confidence intervals for any curve presented in the paper is the 95% confidence interval (Neyman, 1937) on the displayed mean. No data were excluded neither pre-computed. Hyper-parameters were determined to our appreciation, they may be sub-optimal but we found the results convincing enough to display interesting behaviors.

:

Link to open-source code omitted for anonymity.

Figures and Tables:

For two MDPs M, M , for all (s, a) ∈ S × A,|Q * M (s, a) -Q * M (s, a)| ≤ ∆ M M (s, a),(2)with the MDPs local pseudo-metric ∆ M M (s, a) min d M M (s, a), d M M (s, a) , and the local MDP dissimilarity d M M : S × A → R is the unique solution to the following fixed-point equation for d: d(s, a) = D M M γV * M (s, a) + γ s ∈S T a ss max a ∈A d(s , a ).

; e.g. for stochastic shortest path problems, which feature rewards only upon reaching terminal states, max s V * M (s ) = 1 and thus B = (1 + γ) is a tighter bound for transfer. Using DM M and Equation 3, one can derive an upper bound d M M on d M M , detailed in Proposition 4. Proposition 4. Given two tasks M and M , K the set of state-action pairs for which R, T is known with accuracy in L 1 -norm with probability at least 1 -δ. If γ(1 + ) < 1, the solution d M M of the following fixed-point equation on d is an upper bound on d M

a)} be the maximum model distance at a particular s, a pair. Prior knowledge might indicate a smaller upper bound for D max (s, a) than 1+γ 1-γ . We will note such an upper bound D max . Solving Equation 7 boils down to accumulating DM M (s, a) values in d(s, a). Reducing a DM M (s, a) estimate in a single (s, a) pair actually reduces d(s, a) in all (s, a) pairs. Thus, replacing DM M (s, a) in Equation 7 by min{D max , DM M (s, a)}, provides a smaller upper bound d M M on d M M

a)}, M being the set of explored tasks. The pitfall being that, with few explored tasks, Dmax (s, a) could underestimate D max (s, a). Proposition 7 provides a lower bound on the probability that Dmax (s, a) does not underestimate D max (s, a), depending on the number of sampled tasks. In turn this indicates when Dmax (s, a) upper bounds D max (s, a) with high probability, which can be combined with Algorithm 1 to improve the performance.

knowledge (known upper-bound on maxs,a = D M M γV * M (s, a)) bound % convergence speed-up % total return gain (d) Algorithmic properties vs. Dmax

Figure 1: Experimental results

Figure 3: Value functions and Q-functions of MDPs M 1 and M 2

a) . However, using min d M M , d M M allows to regain property 3 and makes this quantity a pseudo-metric again between MDPs. C PROOF OF PROPOSITION 1 Lemma 1. Given two MDPs M and M , this equation on d is a fixed-point equation admitting a unique solution which we call d M a ), ∀s, a ∈ S × A.

This metric space being complete and non-empty, it follows from Banach fixed point theorem that d = Ld admits a single solution. Lemma 1 guarantees the existence of d M M . Proposition 1 states that for any two MDPs M and M and for all (s, a) ∈ S × A, |Q * M (s, a) -Q * M (s, a)| ≤ min d M M (s, a), d M M (s, a) .

this equation on d is a fixed-point equation admitting a unique solution which we call d , a ) if s, a ∈ K, DM M (s, a) + γ max s ,a ∈S×A d(s , a ) otherwise. Proof of Lemma 2. The proof is similar to the proof of Lemma 1. Let d 1 and d 2 be two functions from S × A to R and let L be the functional operator that maps any function d : S × A → R to Ld : s, a →      DM M (s, a) + γ s ∈S T a ss max a ∈A d(s , a ) + max s ,a ∈S×A d(s , a ) if s, a ∈ K, DM M (s, a) + γ max s ,a ∈S×A d(s , a ) otherwise. If s, a ∈ K, we have Ld 1 (s, a) -Ld 2 (s, a) = γ (s , a ) -d 2 (s , a ))

contraction mapping in the metric space (S × A, • ∞ ). This metric space being complete and non-empty, it follows from Banach fixed point theorem that d = Ld admits a single solution. Proof of Proposition 4. The proof is done by induction, by calculating the values of d M M and d M Mfollowing the value iteration algorithm. Those values can respectively be computed via the sequences of iterates (d n ) n∈N and ( dn ) n∈N defined as follows:d 0 (s, a) = 0, ∀s, a ∈ S × A d n+1 (s, a) = D M dn (s , a ) if s, a ∈ K, DM M (s, a) + γ max s ,a ∈S×A dn (s , a ) otherwise.The proof at rank n = 0 is trivial. Let us assume the proposition d n ≤ dn , ∀s, a ∈ S × A true at rank n and consider rank n + 1. There are two cases, depending on the fact that s, a is in K or not.If s, a ∈ K, we haved n+1 (s, a) -dn+1 (s, a) = D M M γV * M (s, a) -DM M (s, ∈S×Adn (s , a ). Using Proposition 3, we have that DM M (s, a) is an upper bound on D M M γV * M (s, a) with probability at least 1 -δ. Hence Pr D M M γV * M (s, a) -DM M (s, a) ≤ 0 ≥ 1 -δ.This plus the fact that d n ≤ dn by induction hypothesis, we have thatd n+1 (s, a) -dn+1 (s, a) ≤ γ Pr T -T 1 ≤ ≥ 1 -δ, we have with probability at least 1 -δ, d n+1 (s, a) -dn+1 (s, a) ≤ γ max s ,a ∈S×A dn (s , a ) -γ max s ,a ∈S×A dn (s , a ) = 0,which concludes the proof in this case.Conversely, if s, a / ∈ K, we haved n+1 (s, a) -dn+1 (s, a) = D M M γV * M (s, a) -DM M (s, a)+ γ s ∈S T a ss max a ∈A d n (s , a ) -γ max s ,a ∈S×A dn (s , a ).Using the same reasoning than in case s, a ∈ K, we have with probability higher than 1 -δ d n+1 (s, a) -dn+1 (s, a) ≤ γ proof in the second case.

M γV * M (s, a) with probability at least 1 -δ. This assumption is actually guaranteed by Proposition 3 while running Algorithm 1. With probability at least 1 -δ, DM M (s, a) ≥ D M M γV * M (s, a), ∀M, M ∈ M2 .

Figure 4: The tight grid-world environment.

Figure 6: Results of the corridor lifelong RL experiment with 95% confidence interval.

. Summary of the number of experiment repetition, number of sampled tasks, number of episodes, maximum length of episodes and upper bounds on the number of collected samples.

Table content: <table><tr><td>Task</td><td>Number of experiment repetitions</td><td>Number of sampled tasks</td><td>Number of episodes</td><td>Maximum length of episodes</td><td>Total number of collected transition samples (s, a, r, s )</td></tr><tr><td>"Tight" task</td><td/><td/><td/><td/><td/></tr><tr><td>of Figures 1a 1b</td><td>10</td><td>15</td><td>2000</td><td>10</td><td>3,000,000</td></tr><tr><td>and 1c</td><td/><td/><td/><td/><td/></tr><tr><td>"Tight" task of Figure 1d</td><td>100</td><td>2</td><td>2000</td><td>10</td><td>4,000,000</td></tr><tr><td>Corridor task Section N</td><td>1</td><td>20</td><td>20</td><td>11</td><td>4400</td></tr><tr><td>Maze task Section N</td><td>1</td><td>30</td><td>100</td><td>15</td><td>45000</td></tr><tr><td>Heat-map Section O</td><td>100</td><td>2</td><td>100</td><td>30</td><td>600,000</td></tr></table>

Peer review (iclr2020):
Edit: in light of the discussion below, I have decided to raise my score to a 6. * Summary This paper introduces a pseudo-metric based on a notion of Lipschitz continuity for action-value functions between different MDPs. The algorithmic improvement is the use of the pseudo metric with RMax in lifelong RL. In particular, the pseudo-metric is defined as the minimum between two dissimilarity measures, each of which can be solved with dynamic programming. The pseudo metric is then used in conjunction with the optimal state-action value function for a previous MDP to form an upper bound heuristic. This upper bound is used in RMax to improve exploration since it can be tighter than the naive RMax bound. Empirically, the theoretical results are supported by thorough investigation on a variant of the grid-world environment. * Decision The main contribution of this paper is hard to discern, but the ideas presented are interesting. Despite the theoretical nature of the paper, I find that the experimentation is overall lacking. In the paper*s current state, I would recommend a weak rejection. However, I am willing to increase this score if the presentation is improved and if the experiments are expanded. * Reasons While the paper motivates and explains the problem well, the proposed method is much less clear. For example, Section 2 leading up to proposition 3 seems like it should motivate Section 3. Instead, I think that Section 2 does not communicate enough how the pseudo-metrics are planned to be used. Perhaps proposition 3 can be in the appendix and RMax should be discussed in section 2. Otherwise, the pseudo-metrics in Section 2 (and 3) should be motivated some other way. For experiments, the paper provides a thorough investigation of one interesting environment. I think a similarly thorough investigation of another environment would greatly strengthen the paper. Multiple experiments that are less thorough would also benefit the paper, but less so. Lastly, it would be interesting to compare to other non-PAC-MDP lifelong learning RL algorithms. * Details Minor concerns: I have trouble following the statement and proof of your probability bounds (for example, proposition 4). It would be good to make more explicit what is a random variables. For example, you define R_s^a to be the expected reward, but I assume that are random variables in the probability bound. In addition, you occasionally refer to the propositions and equations as properties. Page 2: *The extension to continuous spaces is straightforward but beyond the scope* This does not seem relevant since you only look at the tabular problem. While the definition might hold for continuous state spaces, the extension of LRmax to continuous spaces does not seem straightforward. Minor typos: Page 4: *this information when the task changes allows to compute the upper bound*