Year: 2019

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.

heading: 1 INTRODUCTION
text: 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).

heading: 2 BACKGROUND AND RELATED WORK
text: 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, Ras is the expected reward of taking action a in state s and T ass′ is the transition probability of reaching state s
′ when taking action a in state s. Without loss of generality, we assume Ras ∈ [0, 1]. Given a discount factor γ ∈ [0, 1), the expected cumulative return ∑ t γ
tRatst 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) = maxa∈AQ∗(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
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 L1 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.

heading: 3 LIPSCHITZ CONTINUITY OF Q-FUNCTIONS
text: 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 spaceM. 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:
DMM̄f (s, a) , |Ras − R̄as |+ ∑ s′∈S f(s′)|T ass′ − T̄ ass′ |. (1)
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). For two MDPs M,M̄ , for all (s, a) ∈ S ×A,
|Q∗M (s, a)−Q∗M̄ (s, a)| ≤ ∆ MM̄ (s, a), (2) with the MDPs local pseudo-metric ∆MM̄ (s, a) , min { dM̄M (s, a), d M M̄ (s, a) } , and the local MDP
dissimilarity dM̄M : S ×A → R is the unique solution to the following fixed-point equation for d:
d(s, a) = DMM̄γV ∗ M̄ (s, a) + γ ∑ s′∈S T ass′ max a′∈A d(s′, a′). (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 dM̄M is asymmetric, ∆MM̄ (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.

heading: 4 TRANSFER USING THE LIPSCHITZ CONTINUITY
text: 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 Q∗M induced by Q∗
M̄ is defined as UM̄ (s, a) ≥ Q∗M (s, a) with:
UM̄ (s, a) , Q ∗ M̄ (s, a) + ∆ MM̄ (s, a). (4)
The optimism in the face of uncertainty principle leads to consider that the long-term expected return from any state is the 11−γ 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) = 11−γ 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 Kc of unknown pairs. A state-action pair is known if the number of collected reward and transition samples allows estimating an -accurate model in L1-norm with probability higher than 1− δ. We refer to and δ as the RMax precision parameters. This translates into a threshold nknown 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̄ = {M̄1, . . . , M̄m}, 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 { UM̄1 , . . . , UM̄m } , the function Q defined below is an upper bound on Q∗M for all s, a ∈ S ×A.
Q(s, a) ,
{ Ras + γ ∑ s′∈S T ass′ max a′ Q(s′, a′) if (s, a) ∈ K,
U(s, a) otherwise, (5)
with U(s, a) = min {
1 1−γ , UM̄1(s, a), . . . , UM̄m(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 .

heading: 4.1 A TRACTABLE UPPER BOUND ON Q∗M
text: 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 UM̄ (s, a) can be computed. Unfortunately, the true optimal value functions, transition and reward models, necessary to compute UM̄ , 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 D̂MM̄ 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 L1-norm with probability at least 1− δ,
Pr ( D̂MM̄ (s, a) ≥ DMM̄γV ∗
M̄ (s, a)
) ≥ 1− δ
with the following definition of the upper bound on the pseudo-metric between models D̂MM̄ :
D̂MM̄ (s, a) ,  DM̂ ˆ̄M γV̄ (s, a) + 2B if (s, a) ∈ K ∩ K̄ max µ̄∈M DM̂µ̄ γV̄ (s, a) +B if (s, a) ∈ K ∩ K̄c max µ∈M Dµ ˆ̄M γV̄ (s, a) +B if (s, a) ∈ Kc ∩ K̄
max µ,µ̄∈M2
Dµµ̄ γV̄ (s, a) if (s, a) ∈ Kc ∩ K̄c
(6)
where B = ( 1 + γmaxs′ V̄ (s ′) ) .
This upper bound D̂MM̄ 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, maxs′ V ∗M̄ (s ′) 11−γ ; e.g. for stochastic shortest path problems, which feature rewards only upon reaching terminal states, maxs′ V ∗M̄ (s ′) = 1 and thus B = (1 + γ) is a tighter bound for transfer. Using D̂MM̄ 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 L1-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 dM̄M with probability at least 1− δ:
d̂(s, a) = D̂MM̄ (s, a) +  γ ( ∑ s′∈S T̂ ass′ max a′∈A d̂(s′, a′) + max s′,a′∈S×A d̂(s′, a′) ) if s, a ∈ K,
γ max s′,a′∈S×A
d̂(s′, a′) otherwise. (7)
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
ÛM̄ (s, a) = Q̄(s, a) + min { d̂M̄M (s, a), d̂ M M̄ (s, a) } . (8)
And the associated upper bound on U(s, a) (Equation 5) given previous tasks M̄ = {M̄i}mi=1 is Û(s, a) = min {
1 1−γ , ÛM̄1(s, a), . . . , ÛM̄m(s, a)
} (9)
This upper bound can be used to transfer knowledge from a partially solved task to a target task. If Û(s, a) ≤ 11−γ 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.
Algorithm 1: Lipschitz RMax algorithm
Initialize M̂ = ∅. for each newly sampled MDP M do
Initialize Q(s, a) = 11−γ ,∀s, a, and K = ∅ Initialize T̂ and R̂ (RMax initialization) Q← UpdateQ(M̂, T̂ , R̂) for t ∈ [1, max number of steps] do
s = current state, a = arg max a′
Q(s, a′)
Observe reward r and next state s′ n(s, a)← n(s, a) + 1 if n(s, a) < nknown then
Store (s, a, r, s′) if n(s, a) = nknown then
Update K, T̂ ass′ and R̂ a s Q← UpdateQ(M̂, T̂ , R̂)
Save M̂ = ( T̂ , R̂,K,Q ) in M̂
Function UpdateQ(M̂, T̂ , R̂): for M̄ ∈ M̄ do
Compute D̂MM̄ and D̂M̄M (Eq. 6) Compute d̂M̄M and d̂ M M̄
(DP on Eq. 7) Compute ÛM̄ (Eq. 8)
Compute Û (Eq. 9) Compute and return Q (DP on Eq. 5 using Û )

heading: 4.2 LIPSCHITZ RMAX
text: 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 9 for 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 D̂MM̄ , d̂M̄M and eventually Û , 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 Û 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 Õ(S2A/( 3(1− γ)3)), which is improved by LRMax in Proposition 5 and meets Condition C2. Finally Û 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
Õ
( S|{s, a ∈ S ×A | Û(s, a) ≥ V ∗M (s)− }|
3(1− γ)3
)
samples (when logarithmic factors are ignored), with Û defined in Equation 9 a non-static, decreasing quantity, upper bounded by 11−γ .
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 Õ ( τ + S2A2(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.

heading: 4.3 REFINING LRMAX BOUNDS WITH MAXIMUM MODEL DISTANCE
text: 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 DMM̄γ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 Dmax(s, a) , maxM,M̄∈M2{DMM̄γV ∗
M̄ (s, a)} be the maximum model distance at a particular s, a pair.
Prior knowledge might indicate a smaller upper bound for Dmax(s, a) than 1+γ1−γ . We will note such an upper bound Dmax. Solving Equation 7 boils down to accumulating D̂MM̄ (s, a) values in d̂(s, a). Reducing a D̂MM̄ (s, a) estimate in a single (s, a) pair actually reduces d̂(s, a) in all (s, a) pairs. Thus, replacing D̂MM̄ (s, a) in Equation 7 by min{Dmax, D̂MM̄ (s, a)}, provides a smaller upper bound d̂M̄M on d M̄ M , and thus a smaller Û which allows transfer if it is lesser than 1 1−γ . Consequently, such an upper bound Dmax can make a difference between successful and unsuccessful transfer, even if its value is of little importance. Conversely, setting a value for Dmax quantifies the distance between MDPs where transfer is efficient.
Furthermore, one can estimate online the value of Dmax(s, a), lifting the previous hypothesis of available prior knowledge. One can build an empirical estimate of the maximum model distance at s, a: D̂max(s, a) , maxM,M̄∈M̂2{D̂MM̄ (s, a)}, M̂ being the set of explored tasks. The pitfall being that, with few explored tasks, D̂max(s, a) could underestimate Dmax(s, a). Proposition 7 provides a lower bound on the probability that D̂max(s, a) does not underestimate Dmax(s, a), depending on the number of sampled tasks. In turn this indicates when D̂max(s, a) upper bounds Dmax(s, a) with high probability, which can be combined with Algorithm 1 to improve the performance.
Proposition 7. Consider an algorithm producing -accurate in L1-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 pmin = minM∈M Pr(M), the following lower bound holds:
Pr ( D̂max(s, a) ≥ Dmax(s, a) ) ≥ 1− 2(1− pmin)m + (1− 2pmin)m.
The assumption of a lower bound pmin on the sampling probability of a task implies thatM is finite and is commonly seen as a non-adversarial task sampling strategy (Abel et al., 2018).

heading: 5 EXPERIMENTS
text: The experiments reported here1 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 Dmax = 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 11−γ . Computing both upper-bounds and taking the minimum results in combining the two approaches. We include such a combination in
1Link to open-source code omitted for anonymity.
our study with the LRMaxQInit algorithm. Similarly, LRMaxQInit(x) consists in the latter algorithm, benefiting from prior knowledge Dmax = x.
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 nknown = 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 Dmax 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 Dmax on D̂MM̄ 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 Dmax: ρLip, is the ratio of the time the Lipschitz bound was tighter than the RMax bound 11−γ ; ρ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 Dmax becomes tighter. This means that the Lipschitz bound of Equation 8 becomes effectively smaller than 11−γ . 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 Dmax 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 Dmax, LRMax increasingly stops using this prior as the task is explored. This confirms the claim of section 4.3 that providing Dmax enables transfer even if it’s value is of little importance.

heading: 6 CONCLUSION
text: 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 Szepesvá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.

heading: ACKNOWLEDGEMENTS
text: Omitted for anonymity.

heading: A A NEGATIVE TRANSFER EXAMPLE
text: 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
always s0. In the first MDP M1 ∈M, the reward is 0 everywhere except for Ra0s0 = 1. In the second MDP M2 ∈ M, the reward is 0 everywhere except for Ra1s1 = 1. With a discount factor γ = 0.9, the value functions and Q-functions of both MDPs are summarized in Table 3 Using the weighted
transfer technique from M1 to M2 proposed by Song et al. (2016) (Definition 4.1), the Q-function described below is used as an initialization for the exploration of M2.
QtransferM2 (s0, a0) = 2.03 QtransferM2 (s0, a1) = 2.25 QtransferM2 (s1, a0) = 2.5 QtransferM2 (s1, a1) = 2.03
First, QtransferM2 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. QtransferM2 would never discover the state-action pair s1, a1 in M2 which is the maximum-reward pair. Instead, the agent would go from s0 to s1 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.

heading: B DISCUSSION ON METRICS AND RELATED NOTIONS
text: 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, DM̄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 dM̄M (s, a) of Proposition 1 does not respect properties 2 and 3, hence the name dissimilarity. The ∆M̄M (s, a) , min { dM̄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.
The same goes for the global dissimilarity dM̄M = 1 1−γ maxs,a∈S×A [ DM̄M,γV ∗
M̄ (s, a)
] . However,
using min { dM̄M , d M M̄ } allows to regain property 3 and makes this quantity a pseudo-metric again between MDPs.

heading: C PROOF OF PROPOSITION 1
text: Lemma 1. Given two MDPs M and M̄ , this equation on d is a fixed-point equation admitting a unique solution which we call dM̄M
d(s, a) = DM̄M,γV ∗ M̄ (s, a) + γ ∑ s′ T ass′ max a′ d(s′, a′),∀s, a ∈ S ×A.
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 d1 and d2 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 7→ DM̄M,γV ∗ M̄ (s, a) + γ ∑ s′ T ass′ max a′ d(s′, a′).
Then Ld1(s, a) − Ld2(s, a) = γ ∑ s′ T a ss′ [maxa′ d1(s
′, a′)−maxa′ d2(s′, a′)]. But maxa′ d1(s
′, a′) − maxa′ d2(s′, a′) ≤ maxa′ [d1(s′, a′)− d2(s′, a′)] ≤ ‖d1 − d2‖∞. And so ‖Ld1 − Ld2‖∞ ≤ γ‖d1 − d2‖∞. Since γ < 1, L is 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.
Lemma 1 guarantees the existence of dM̄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 { dM̄M (s, a), d M M̄ (s, a) } .
Proof of Proposition 1. The proof is by induction. The Value Iteration sequence of iterates (QnM )n∈N for task M is:
Q0M (s, a) = 0,∀s, a ∈ S ×A
Qn+1M (s, a) = R a s + γ ∑ s′∈S T ass′ max a′∈A QnM (s ′, a′),∀s, a ∈ S ×A.
It is obvious that Q0M (s, a) − Q0M̄ (s, a) ≤ d M̄ M (s, a). Suppose that |QnM (s, a) − QnM̄ (s, a)| ≤ dM̄M (s, a). Then:
∣∣Qn+1M (s, a)−Qn+1M̄ (s, a)∣∣ = ∣∣∣∣∣Ras − R̄as + γ ∑
s′∈S
[ T ass′ max
a′∈A QnM (s ′, a′)− T̄ ass′ max a′∈A QnM̄ (s ′, a′) ]∣∣∣∣∣ ≤ ∣∣Ras − R̄as ∣∣+ γ ∑
s′∈S
∣∣∣∣T ass′ maxa′∈AQnM (s′, a′)− T̄ ass′ maxa′∈AQnM̄ (s′, a′) ∣∣∣∣
≤ ∣∣Ras − R̄as ∣∣+ γ ∑
s′∈S max a′∈A
QnM̄ (s ′, a′) ∣∣T ass′ − T̄ ass′ ∣∣ + γ
∑ s′∈S T ass′ ∣∣∣∣maxa′∈AQnM (s′, a′)−maxa′∈AQnM̄ (s′, a′) ∣∣∣∣
≤ ∣∣Ras − R̄as ∣∣+ ∑
s′∈S γV ∗M̄ (s
′) ∣∣T ass′ − T̄ ass′ ∣∣
+ γ ∑ s′∈S T ass′ max a′∈A ∣∣QnM (s′, a′)−QnM̄ (s′, a′)∣∣ ≤ DM̄M,γV ∗
M̄ (s, a) + γ ∑ s′∈S T ass′ max a′ dM̄M (s ′, a′)
Since Q∗M and Q ∗ M̄ are respectively the limits of the (QnM )n∈N and ( Qn M̄ ) n∈N sequences, the result that |Q∗M (s, a)−Q∗M̄ (s, a)| ≤ d M̄ M (s, a) follows from passage to the limit.
By symmetry, on also has |Q∗M (s, a)−Q∗M̄ (s, a)| ≤ d M M̄ (s, a) and thus |Q∗M (s, a)−Q∗M̄ (s, a)| ≤ min { dM̄M (s, a), d M M̄ (s, a) } .

heading: D SIMILAR RESULTS TO PROPOSITION 1
text: Similar results to Proposition 1 can be derived with a similar proof as in Section C. The first result is for the value function and is stated below.
Proposition (Local bound on the distance between value functions). For any two MDPs M and M̄ , for all s ∈ S,
|V ∗M (s)− V ∗M̄ (s)| ≤ maxa∈A ∆ M̄ M (s, a)
where the local MDP pseudo-metric ∆M̄M (s, a) has the same definition as in Proposition 1.
Another result can be derived for any policy π that one wishes to evaluate in both MDPs. For the sake of generality, we state the result for any stochastic policy mapping states to distributions over actions. A deterministic policy is a stochastic policy choosing the selected action with probability 1 and the others with probability 0.
Proposition (Local bound on the distance between value and Q-value functions for any policy.). For any two MDPs M and M̄ , for a stochastic policy π, for all s, a ∈ S ×A,
|V πM (s)− V πM̄ (s)| ≤ ∆ π, M̄ M (s)
where dπ,M̄M (s) is defined with the following fixed-point equation:
dπ,M̄M (s) = Ea∼π [ DM̄M,γV ∗
M̄ (s, a) + γ ∑ s′∈S T ass′d π,M̄ M (s ′)
] ,
and ∆π, M̄M (s) = min { dπ,M̄M (s), d π,M M̄ (s) } .

heading: E GLOBAL PSEUDO-LIPSCHITZ CONTINUITY RESULT
text: 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
{ DMM̄γ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 ∣∣Q0M (s, a)−Q0M̄ (s, a)∣∣ ≤ dM̄M , and∣∣Q0M (s, a)−Q0M̄ (s, a)∣∣ ≤ dMM̄ . Hence, the result holds for n = 0. Let us suppose that∣∣QnM (s, a)−QnM̄ (s, a)∣∣ ≤ dM̄M , and∣∣QnM (s, a)−QnM̄ (s, a)∣∣ ≤ dMM̄ . Then,∣∣Qn+1M (s, a)−Qn+1M̄ (s, a)∣∣ ≤ DM̄M,γV ∗M̄ (s, a) + γ ∑
s′∈S T ass′ max a′∈A ∣∣QnM (s′, a′)−QnM̄ (s′, a′)∣∣ ≤ max s,a∈S×A [ DM̄M,γV ∗ M̄ (s, a) ] + γ ∑ s′∈S T ass′ 1 1− γ max s,a∈S×A [ DM̄M,γV ∗ M̄ (s, a)
] ≤ max s,a∈S×A [ DM̄M,γV ∗ M̄ (s, a) ]( 1 + γ 1− γ
) ≤ dM̄M

heading: F PROOF OF PROPOSITION 2
text: 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:{
Q∗M,0(s, a) = 0 Q∗M,n(s, a) = R a s + γ ∑ s′ T a ss′ maxa′ Q ∗ M,n−1(s
′, a′){ U0(s, a) = 0
Un(s, a) = R a s + γ ∑ s′ T a ss′ maxa′ Un−1(s ′, a′)
Obviously, Q∗M,0(s, a) ≤ U0(s, a). Suppose the property true at rank n and consider rank n+ 1:
Q∗M,n+1(s, a)− Un+1(s, a) = γ ∑ s′ T ass′ ( max a′ Q∗M,n(s ′, a′)−max a′ Un(s ′, a′) )
≤ γ ∑ s′ T ass′ max a′ ( Q∗M,n(s ′, a′)− Un(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.

heading: G PROOF OF PROPOSITION 3
text: 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 L1-norm with probability at least 1− δ, i.e. we have that,
Pr ( |Ras − R̂as | ≤ ) ≥ 1− δ, ∀s, a ∈ K, (11)
Pr ( ‖T ass′ − T̂ ass′‖1 ≤ ) ≥ 1− δ, ∀s, a ∈ K, (12)
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 ∩ K̄c and 3) s, a ∈ Kc ∩ K̄c, the case s, a ∈ Kc ∩ 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:
DMM̄γV ∗ M̄ (s, a) = |Ras − R̄as |+ γ ∑ s′∈S V ∗M̄ (s ′)|T ass′ − T̄ ass′ |. (13)
The first term of the RHS of Equation 13 respects the following sequence of inequalities with probability at least 1− δ:
|Ras − R̄as | ≤ |Ras − R̂as |+ |R̂as − ˆ̄Ras |+ |R̄as − ˆ̄Ras |
≤ |R̂as − ˆ̄Ras |+ 2 . (14) The second term of the RHS of Equation 13 respects the following sequence of inequalities with probability at least 1− δ:
γ ∑ s′∈S V ∗M̄ (s ′)|T ass′ − T̄ ass′ | ≤ γ ∑ s′∈S V̄ (s′) ( |T ass′ − T̂ ass′ |+ |T̂ ass′ − ˆ̄T ass′ |+ |T̄ ass′ − ˆ̄T ass′ | ) ≤ γmax
s′ V̄ (s′) ∑ s′∈S |T ass′ − T̂ ass′ |+ γ ∑ s′∈S V̄ (s′)|T̂ ass′ − ˆ̄T ass′ |+
γmax s′ V̄ (s′) ∑ s′∈S |T̄ ass′ − ˆ̄T ass′ |
≤ γ ∑ s′∈S V̄ (s′)|T̂ ass′ − ˆ̄T ass′ |+ 2 γmax s′ V̄ (s′). (15)
Summation of Equations 14 and 15 reveals D̂MM̄ (s, a) = |R̂as − ˆ̄Ras |+ γ ∑ s′∈S V̄ (s
′)|T̂ ass′ − ˆ̄T ass′ | 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):
DMM̄γV ∗ M̄
(s, a) ≤ D̂MM̄ (s, a) + 2 (
1 + γmax s′
V̄ (s′) ) .
2) If s, a ∈ K ∩ K̄c, 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:
|Ras − R̄as | ≤ |Ras − R̂as |+ |R̂as − R̄as | ≤ + max
R̄ |R̂as − R̄|. (16)
Similarly, with probability at least 1− δ, we have: γ ∑ s′∈S V ∗M̄ (s ′)|T ass′ − T̄ ass′ | ≤ γ ∑ s′∈S V̄ (s′) ( |T ass′ − T̂ ass′ |+ |T̂ ass′ − T̄ ass′ | ) ≤ γmax
s′ V̄ (s′) + γmax
T̄ ∑ s′∈S V̄ (s′)|T̂ ass′ − T̄s′ |. (17)
Combining inequalities 16 and 17, we get the following with probability at least 1 − δ, noticing DMM̄γV ∗
M̄ (s, a) on the LHS:
DMM̄γV ∗ M̄ (s, a) ≤ max µ̄∈M DM̂µ̄ γV̄
(s, a) + (
1 + γmax s′
V̄ (s′) ) ,
which is the expected result.
3) If s, a ∈ Kc ∩ K̄c, then properties 11 and 12 do not hold. In such a case, the result
DMM̄γV ∗ M̄ (s, a) ≤ max µ,µ̄∈M2 Dµµ̄ γV̄ (s, a)
is straightforward by remarking that V ∗ M̄ (s) ≤ V̄ (s) with probability at least 1− δ.

heading: H ANALYTICAL CALCULATION OF D̂MM̄ IN PROPOSITION 3
text: 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 L1-norm with probability at least 1 − δ. We note Vmax, a known upper-bound on the maximum achievable value. In the worst case where one does not have any information on the value of Vmax, one can always set Vmax = 11−γ . We recall the definition of the upper bound on the pseudo-metric between models:
D̂MM̄ (s, a) =  DM̂ ˆ̄M γV̄ (s, a) + 2B if (s, a) ∈ K ∩ K̄, max µ̄∈M DM̂µ̄ γV̄ (s, a) +B if (s, a) ∈ K ∩ K̄c, max µ∈M Dµ ˆ̄M γV̄ (s, a) +B if (s, a) ∈ Kc ∩ K̄,
max µ,µ̄∈M2
Dµµ̄ γV̄ (s, a) if (s, a) ∈ Kc ∩ K̄c.
(18)
with B = ( 1 + γmaxs′ V̄ (s ′) )
and DMM̄f defined as in Equation 13. We detail the computation of D̂MM̄ (s, a) for each cases 1) s, a ∈ K ∩ K̄, 2) s, a ∈ K ∩ K̄c (the s, a ∈ Kc ∩ K̄ is symmetric to this one), and 3) s, a ∈ Kc ∩ K̄c. Recall that we consider a finite, countable, state-action space S ×A. 1) If s, a ∈ K ∩ K̄, we have
D̂MM̄ (s, a) = DM̂ ˆ̄M
γV̄ (s, a) + 2B = |R̂as − ˆ̄Ras |+ γ ∑ s′∈S V̄ (s′)|T̂ ass′ − ˆ̄T ass′ |+ 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 maxs′ 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 ∩ K̄c, we have
D̂MM̄ (s, a) = max µ̄∈M DM̂µ̄ γV̄ (s, a) +B
= max R̄as ,T̄ a ss′
( |R̂as − R̄as |+ γ ∑ s′∈S V̄ (s′)|T̂ ass′ − T̄ ass′ | ) + ( 1 + γmax s′ V̄ (s′) ) ,
= max r∈[0,1] |R̂as − r|+ γ max t∈[0,1]|S|∑
t=1
(∑ s′∈S V̄ (s′)|T̂ ass′ − ts′ | ) + ( 1 + γmax s′ V̄ (s′) ) .
First, we have max r∈[0,1] |R̂as − r| = max { R̂as , 1− R̂as } .
Maximizing the maxt∈[0,1]|S| term is maximizing a convex combination of V̄ (whose values are all positive) whose terms are not independent (since the ts′ 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:
• ts′ = 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 maxt∈[0,1] |T̂ ass′ − t| to s′ (note that ts′ ∈ {0, 1}) – If ∑ s∈S ts > 1, then ts′ ← 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′) = maxs V̄ (s) (often these are states in K̄c). Among those states, let us suppose there exists s+ unreachable from s, a, according to T̂ , that is T̂ ass+ = 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 maxt∈[0,1]|S| term. Conversely, if such a state does not exist (that is, if for all such states T̂ ass+ > 0), then maxs V̄ (s) is an upper bound on the maxt∈[0,1]|S| term. Therefore:
max t∈[0,1]|S| (∑ s′∈S V̄ (s′)|T̂ ass′ − ts′ | ) ≤ max s V̄ (s), with equality in many cases.
3) If s, a ∈ Kc ∩ K̄c, the resolution is trivial and we have
D̂MM̄ (s, a) = max µ,µ̄∈M2 Dµµ̄ γV̄ (s, a)
= max Ras ,T a ss′ ,R̄ a s ,T̄ a ss′
( |Ras − R̄as |+ γ ∑ s′∈S V̄ (s′)|T ass′ − T̄ ass′ | ) = max r,r̄∈[0,1]
|r − r̄|+ γ max t,t̄∈[0,1]|S|∑
t=1∑ t̄=1
∑ s′∈S V̄ (s′)|ts′ − t̄s′ |
= 1 + γmax s V̄ (s).

heading: I PROOF OF PROPOSITION 4
text: Lemma 2. Given two tasks M and M̄ , K the set of state-action pairs for which 〈R, T 〉 is known with accuracy in L1-norm with probability at least 1− δ. If γ(1 + ) < 1, this equation on d̂ is a fixed-point equation admitting a unique solution which we call d̂M̄M
d̂(s, a) =  D̂MM̄ (s, a) + γ ( ∑ s′∈S T̂ ass′ max a′∈A d̂(s′, a′) + max s′,a′∈S×A d̂(s′, a′) ) if s, a ∈ K,
D̂MM̄ (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 d1 and d2 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 7→  D̂MM̄ (s, a) + γ ( ∑ s′∈S T̂ ass′ max a′∈A d(s′, a′) + max s′,a′∈S×A d(s′, a′) ) if s, a ∈ K,
D̂MM̄ (s, a) + γ max s′,a′∈S×A
d(s′, a′) otherwise.
If s, a ∈ K, we have
Ld1(s, a)− Ld2(s, a) = γ ∑ s′ T ass′ ( max a′ d1(s ′, a′)−max a′ d2(s ′, a′) ) +
γ ( max s′,a′ d1(s ′, a′)−max s′,a′ d2(s ′, a′) ) ≤ (γ + γ ) ( max s′,a′ d1(s ′, a′)−max s′,a′ d2(s ′, a′)
) ≤ γ(1 + ) max
s′,a′ (d1(s
′, a′)− d2(s′, a′))
≤ γ(1 + )‖d1 − d2‖∞.
If s, a /∈ K, we have Ld1(s, a)− Ld2(s, a) = γ (
max s′,a′
d1(s ′, a′)−max
s′,a′ d2(s
′, a′) ) ≤ γmax
s′,a′ (d1(s
′, a′)− d2(s′, a′))
= γ(1 + )‖d1 − d2‖∞.
In both cases, ‖Ld1 − Ld2‖∞ ≤ γ(1 + )‖d1 − d2‖∞. If γ(1 + ) < 1, L is 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 dM̄M and d̂ M̄ M following the value iteration algorithm. Those values can respectively be computed via the sequences of iterates (dn)n∈N and (d̂n)n∈N defined as follows:
d0(s, a) = 0,∀s, a ∈ S ×A
dn+1(s, a) = DMM̄γV ∗ M̄ (s, a) + γ ∑ s′∈S T ass′ max a′∈A dn(s′, a′)
and,
d̂0(s, a) = 0,∀s, a ∈ S ×A,
d̂n+1(s, a) =  D̂MM̄ (s, a) + γ ( ∑ s′∈S T̂ ass′ max a′∈A d̂n(s′, a′) + max s′,a′∈S×A d̂n(s′, a′) ) if s, a ∈ K,
D̂MM̄ (s, a) + γ max s′,a′∈S×A
d̂n(s′, a′) otherwise.
The proof at rank n = 0 is trivial. Let us assume the proposition dn ≤ d̂n,∀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 have
dn+1(s, a)− d̂n+1(s, a) = DMM̄γV ∗ M̄ (s, a)− D̂MM̄ (s, a)+
γ ∑ s′∈S ( T ass′ max a′∈A dn(s′, a′)− T̂ ass′ max a′∈A d̂n(s′, a′) ) +
− γ max s′,a′∈S×A
d̂n(s′, a′).
Using Proposition 3, we have that D̂MM̄ (s, a) is an upper bound on DMM̄γV ∗ M̄ (s, a) with probability at least 1− δ. Hence
Pr ( DMM̄γV ∗
M̄ (s, a)− D̂MM̄ (s, a) ≤ 0
) ≥ 1− δ.
This plus the fact that dn ≤ d̂n by induction hypothesis, we have that dn+1(s, a)− d̂n+1(s, a) ≤ γ ∑ s′∈S max a′∈A d̂n(s′, a′) ( T ass′ − T̂ ass′ ) +
− γ max s′,a′∈S×A
d̂n(s′, a′)
≤ γ max s′,a′∈S×A d̂n(s′, a′) ∑ s′∈S ( T ass′ − T̂ ass′ ) +
− γ max s′,a′∈S×A
d̂n(s′, a′)
Since Pr ( ‖T − T̂‖1 ≤ ) ≥ 1− δ, we have with probability at least 1− δ,
dn+1(s, a)− d̂n+1(s, a) ≤ γ max s′,a′∈S×A d̂n(s′, a′) − γ max s′,a′∈S×A d̂n(s′, a′)
= 0,
which concludes the proof in this case.
Conversely, if s, a /∈ K, we have
dn+1(s, a)− d̂n+1(s, a) = DMM̄γV ∗ M̄ (s, a)− D̂MM̄ (s, a)+ γ ∑ s′∈S T ass′ max a′∈A dn(s′, a′)− γ max s′,a′∈S×A d̂n(s′, a′).
Using the same reasoning than in case s, a ∈ K, we have with probability higher than 1− δ dn+1(s, a)− d̂n+1(s, a) ≤ γ ∑ s′∈S T ass′ max a′∈A d̂n(s′, a′)− γ max s′,a′∈S×A d̂n(s′, a′)
≤ γ max s′,a′∈S×A d̂n(s′, a′)− γ max s′,a′∈S×A d̂n(s′, a′)
≤ 0,
which concludes the proof in the second case.

heading: J PROOF OF PROPOSITION 6
text: 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):
Õ ( 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.

heading: K PROOF OF PROPOSITION 7
text: Proof. Consider a fixed state-action pair s, a ∈ S × A. For two sampled tasks M, M̄ ∈ M̂2, we assume our algorithm to provide an upper-bound on DMM̄γ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− δ,
D̂MM̄ (s, a) ≥ DMM̄γV ∗ M̄ (s, a),∀M, M̄ ∈ M̂2.
Hence, with probability at least 1− δ, max
M,M̄∈M̂2 D̂MM̄ (s, a) ≥ max M,M̄∈M̂2 DMM̄γV ∗ M̄ (s, a)
i.e. D̂max(s, a) ≥ Dmax(s, a). In turn, the event of underestimatingDmax(s, a) occurs only if the two tasks, that we note M∗1 ,M ∗ 2 ∈ M2, maximizing M,M̄ 7→ DMM̄γ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 pmin, the quantity pmin(1 − pmin)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 2pmin, we follow the same reasoning as for P̃ and obtain that :
Pr(X = i) ≥ 2pmin(1− 2pmin)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− pmin)k−i−1(1− 2pmin)i−1p2min (19)
Pr(Y = k) is the probability of first success at step k. For D̂max(s, a) to estimate Dmax(s, a) in m steps, we require that this success occurs any time during the first m steps, so we have:
Pr(D̂max(s, a) ≥ Dmax(s, a)) = m∑ k=2 Pr(Y = k)
Using Equation 19, we can deduce our result when remarking that necessarily pmin ≤ 1/2:
Pr(D̂max(s, a) ≥ Dmax(s, a)) ≥ 2p2min m∑ k=2 k−1∑ i=1 (1− pmin)k−i−1(1− 2pmin)i−1
≥ 2p2min m−2∑ k=0 k∑ i=0 (1− pmin)k−i(1− 2pmin)i
≥ 2p2min m−2∑ k=0 (1− pmin)k k∑ i=0 ( 1− 2pmin 1− pmin )i
≥ 2p2min m−2∑ k=0 (1− pmin)k 1 p ( 1− pmin − (1− 2pmin)k+1 (1− pmin)k )
≥ 2pmin m−2∑ k=0 ( (1− pmin)k+1 − (1− 2pmin)k+1 ) ≥ 2pmin(1− pmin) 1− (1− pmin)m−1
1− (1− pmin)
− 2pmin(1− 2pmin) 1− (1− 2pmin)m−1 1− (1− 2pmin) ≥ 1− 2(1− pmin)m + (1− 2pmin)m

heading: L DISCUSSION ON AN UPPER BOUND ON DISTANCES BETWEEN MDP MODELS
text: Section 4.3 introduced the idea of exploiting prior knowledge on the maximum distance between two MDP models. This idea begs for a more detailed discussion. Consider two MDPs M and M̄ . By definition of the local model pseudo metric DMM̄γV ∗
M̄ in Equation 1, the maximum possible distance is
given by
max M,M̄∈M2 DMM̄γV ∗ M̄
(s, a) = 1 + γ
1− γ .
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 Dmax 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 Dmax, 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 Dmax allows a faster and more efficient transfer between environments.

heading: M THE “TIGHT” ENVIRONMENT USED IN EXPERIMENTS OF SECTION 5
text: 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].

heading: N ADDITIONAL LIFELONG RL EXPERIMENTS
text: 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 Dmax 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 12 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 Dmax 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
to the MaxQInit estimation of maximum Q-values, we unsurprisingly observe that both algorithms feature a similar performance in the maze environment.
O PRIOR Dmax USE EXPERIMENT
Each time an s, a pair is updated, we compute the local distance upper bound D̂ (Equation 6) for all (s, a) ∈ S ×A. In this computation, one can leverage knowledge of Dmax to select min{D̂,Dmax}. We show that LRMax relies less and less on Dmax as knowledge on the current task increases. For this experiment, we used the two grid-worlds environments displayed in Figures 9 and 10.
The rewards collected with any actions performed in the teal cells of both tasks are defined as:
Rsa = exp
( − (sx − gx) 2 + (sy − gy)2
2σ2
) ,∀s = (sx, sy) ∈ S, a ∈ A,
where (sx, sy) are the coordinates of the current state, (gx, gy) the coordinate of the goal cell labelled with a G and σ is a span parameter equal to 1 in the first environment and 1.5 in the second environment. The agent starts at the cell labelled with the S letter. Black cells represent unreachable
cells (walls). We run LRMax twice on the two different maze grid-worlds and record for each model update the proportion of times Dmax is smaller than D̂ in Figure 11 via the % use of Dmax.
With maximum value Dmax = 19, D̂ is systematically lesser than Dmax, resulting in 0% use. Conversely, with minimum value Dmax = 0, the use expectedly increases to 100%. The in-between value of Dmax = 10 displays a linear decay of the use. This suggests that, at each update, D̂ ≤ Dmax is only true for one more unique s, a pair, resulting in a constant decay of the use. With fewer prior (Dmax = 15 or 17), updating one single s, a pair allows D̂ to drop under Dmax for more than one pair, resulting in less use of the prior knowledge. The conclusion of this experiment if that Dmax is only useful at the beginning of the exploration, while LRMax relies more on its own bound D̂ when partial knowledge of the task has been acquired.
P DISCUSSION ON RMAX PRECISION PARAMETERS , δ, nknown
We used nknown = 10, δ = 0.05 and = 0.01. Theoretically, nknown should be a lot larger (≈ 105) in order to reach an accuracy = 0.01 according to Strehl et al. (2009). However, it is common practice to assume such small values of nknown are sufficient to reach an acceptable model accuracy . Interestingly, empirical validation did not confirm this assumption for any RMax-based algorithm. We keep these values nonetheless for the sake of comparability between algorithms and consistency with the literature. Despite such absence of accuracy guarantees, RMax-based algorithms still perform surprisingly well and are robust to model estimation uncertainties.
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.

Review summaries:
This paper studies the problem of reusing prior experience in Reinforcement learning. The main contribution of this work is to introduce a novel metric between MDPs. They use the value functions Lipschitz continuity in the task space w.r.t the metric and show the connection. The theoretical results of this paper show the value transfer and they can derive results for the same. They demonstrate the benefit of their method in experiments.