Lipschitz Lifelong Reinforcement Learning
Authors: Erwan Lecarpentier
David Abel
Kavosh Asadi
Yuu Jinnai
Emmanuel Rachelson
Michael L. Littman
Venue:  (2020)
Keywords: Reinforcement Learning
Lifelong Learning

Abstract: We consider the problem of reusing prior experience when an agent is facing a series of Reinforcement Learning (RL) tasks. We introduce a novel metric between Markov Decision Processes and focus on the study and exploitation of the optimal value function's Lipschitz continuity in the task space with respect to that metric. These theoretical results lead us to a value transfer method for Lifelong RL, which we use to build a PAC-MDP algorithm that exploits continuity to accelerate learning. We illustrate the benefits of the method in Lifelong RL experiments.

Under review as a conference paper at ICLR 2020
LIPSCHITZ LIFELONG REINFORCEMENT LEARNING
Anonymous authors
Paper under double-blind review
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 Lifelong RL experiments.
INTRODUCTION
Lifelong Reinforcement Learning (RL) is an online problem where an agent faces 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 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, transfer, practically deployable in the online Lifelong RL setting. Specifically, we introduce a metric between MDPs and prove that the optimal Q-value function Lipschitz continuous with respect to MDPs. This property allows to compute a provable upper-bound on the optimal value function of target task, given the learned optimal value function of 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.
design novel method for value
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 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 Lifclong 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 typically modeled as a Markov Decision Process (MDP) (Puterman, 2014) consisting in t-tupe (S, R, T) where S is state space, AA an action space, R is the expected reward of taking action state s and TV. is the transition probability of reaching state s' when taking action in state Without loss of generality, we assume R [0, 1]. Given discount factor y E [0, 1), the expected cumulative return Σ, 7 RR: obtained along a trajectory starting with state and action is noted ((s, a) and called the Q-function. The optimal Q-function Q* is the highest attainable expected return from s, a and V (s) = m 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 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 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 novel method for such

---

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 x A. For brevity, we will refer indifferently to MDPs, models tasks, and write them M (R,
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 al. (2013) and Brunskill and Li (2013) propose MDP clustering methods respectively using 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 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 applicable in a batch RL setting as opposed 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 soft homomorphism exists between the state spaces. Brunskill and Li (2013) also provide 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 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.
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 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 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- (), and function J S + Rt, we define the meeudo-metric between models at (s, E E x A w.r.. f as:
DM (s, a) 2 Rg
Re + Σ f(s')
T.
S'ES
This pseudo-metric is relative to positive function f. We implicitly cast this definition in the context of discrete state spaces. The extension continuous spaces is straightforward but beyond the scope of this paper. Let Qi, denote the optimal Q-function of MDP M E M. Proposition 1 (Local pseudo-Lipschin continuity). For two MDPs M, M. for all (s. E E A.
1Q a) - (s,(s,))) < A MM (s, a). with the MDPs local meeudo-metric A AM (s, a) A min {dM a), d a)) and the local MDP dissimilarity dM S x A + R is the unique solution to the following fixed-point equation for d:
(2)
d(s, a) = MM (s, a) + 7
Σ
T max d(sl,a'). ,a')
(3)
M
e'EA
2

---

Under review as a conference paper at ICLR 2020
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) E S x A is controlled by a local dissimilarity between the MDPs. The latter follows fixed-point equation (Equation 3), which can be solved by Dynamic Programming (DP) (Bellman, 1957). Note that, although the local MDP dissimilarity d is asymmetrie, A AMM (s. a) is pseudo-metrie, hence the name pseudo- results for the value function of fixed policy and the optimal value function As can easily be continuity property (Appendix, Sections D and E). Thus,
continuity. Similar
derived, as well as a global pseudo-Lipschn overall, the optimal Q-functions of two close MDPs (in the sense of Equation 1) are themselves close to each other. direct consequence in Lifelong RL is that previously solved tasks can help bound the value function of bounds are known or if it provably overestimates the true Q'. The next section exploits this property to build PAC-MDP algorithm that performs provably non-negative transfer between successive tasks and accelerates learning.
task. Even partially learned Q-function can be used for that purpose if error
4 TRANSFER USING THE LIPSCHITZ CONTINUITY
A purpose of value transfer, when interacting online with new MDP, is to initialize the value function and drive the exploration to accelerate learning. We aim to exploit value transfer in method guaranteeing three conditions: CI. 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- Q-function of an MDP given the optimal Q-function of another MDP.
Definition 2. Given two tasks M and for all (s,a) E S x A, the Lipschitz upper bound on Qi induced by 2% is defined as U (s, a) 2 Qir(s,a) a) with:
Un (8, a) Qir + MM AM (8,a).
(4)
The optimism in the face of uncertainty principle leads consider that the long-term expected return from any state is the - maximum return, unless proven otherwise. The RMax algorithm (Brafman and Temnenholtz, 2002) in particular explores an MDP so as to shrink this upper bound. RMax is 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 Uss, I 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 x A is split into subset of known state-action pairs K and its complement K of unknown pairs. A state-action pair is known if the number of collected reward and transition samples allows estimating an e-accurate model in Li-norm with probability higher than - 6. We refer to e and ō as the RMax precision parameters. This translates into a threshold Nenown on the number of visits n(s,, a) pair s, a that are necessary to reach this precision. Given the experience of a set of m MDPs M = [M....., Mm J. we define the total bound as the minimum over all the Lipschitz bounds induced by each previous MDP.
Given a partially known task M = =RR, T), the set of known state-action pairs K. and the set of Lipschitz bounds on Qi induced by previous tasks (Us....., ....,U,, U. defined below is an upper bound on Qia for all a E S x A.
Proposition 2.
the function Q
R + Σ To max Q(s',a') if (s,
K,
Q(s,a) A
EE
(5)
(U),a))
otherwise,
with (s, = min - Un, (8, (8. ... .....,, UMa (s, })
Traditionally in RMax, Equation 5 is solved to a precision EQ via Value Iteration. This yields a function Q that is valid heuristic (provable upper bound on Q ) for the exploration of MDP M.
3

---

Under review as a conference paper at ICLR 2020
4.1 A TRACTABLE UPPER BOUND ON Qi
The key issue addressed in this Section is how to actually compute (s, a). Consider two tasks M and M, which vanilla RMMx 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, Rt,, and the upper bounds Q and Q respectively on Q'M and 2/ Equation 5 allows the transfer of knowledge from M to M if Uyr(s, (8, a) can be computed. Unfortunately, the true optimal value functions, transition and reward models, necessary to compute U Ut are unknown. Thus, we propose to compute looser upper bound based on the learned models and value functions. First, we provide an upper bound D DMM 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 e in Li-norm with probability at least 8,
Pr (DMM
(s,a)
D
MM VV (s.a)) 2 1
with the following definition of the upper bound on the pseudo-metric between models MMM
DM (s, a) + 2B
K(KK
dEM y (8, +
max D MR
KK
(MM(s, &
(6)
max DUM HEM ,V (8,0) + ((<s,
max DAR AREM² 7P (s,a)
where = e (1+ max. V(s)).
This upper bound DMM on the distance between MDPs can be calculated analytically (see Appendix, Section H). The magnitude of the B term controlled by c. In the case where no information is available on the maximum value of V, B = --.. e measures the accuracy with which the tasks are known: the smaller e, the tighter the bound. Note that V is used as an upper bound on the true V In many cases, max,' V (s") < --qi e.g. for stochastic shortest path problems, which feature rewards only upon reaching terminal states, max,/ Vi (s') 1 and thus B (1 + 7) tighter bound for transfer. Using DMM and Equation 3, one can derive an upper bound a on d detailed Proposition
Proposition 4. Given two tasks M and M, K the set of state-action pairs for which (R, T) is known with accuracy in Cı-norm with probability at least 1 6. If 7(1 + e) < the solution d of the following fixed-point equation on d is an upper bound on d with probability at least 1
Σ t max dis', a²) + s',x' FEES max SSEA
d(s), ifs K,
?
d(s,a) a) MM (s) -M,
d'EA d(s', d') otherwise.
Similarly as in Proposition 3, the condition 7(1 + E) illustrates the fact that for large return horizon (large 7), a high accuracy (small e) is needed for the bound to be computable. Finally, a tractable upper bound on Qi, given M with high probability is given by
(s, Q(s a) + min { (aM (s, a), (s (s)
(8)
And the associated upper bound on Uss a) (Equation 5) given previous tasks M = {M,
Ú a) min { - Ü'Z, (s, ..... U.... (s)
This upper bound can be used to transfer knowledge from a partially solved task to a target task. If Üs. a) < - for some (s, a) pairs, then the convergence rate can be improved. As complete knowledge of both tasks not needed, it can be applied online in a Lifelong RL setting. In the next section, we explicit algorithm that leverages this value transfer method.
4

---

Under review as a conference paper at ICLR 2020
Algorithm 1: Lipschitz RMax algorithm
Initialize M 0.
Function UpdateQ T, R): for M E M do Compute D and DDM (Eq. 6) Compute d and MM (DP on Eq. 7) Compute ÜM (Eq. 8)
for each newly sampled MDP M do
Initialize Q(a,0) a) I-y: Vs, o, and K = 0
1_
Initialize T and R (RMax initialization) Q Updatee(M, T" R)) for t E [1, max number steps] do current state, arg max Q(s, d')
Compute Ù (Eq. 9)
Compute and return Q (DP on Eq. 5 using Ú)
Observe reward and next state n(s,a) a) t n
if n((8 a) Nlkoown then Store (s,0, r,
if n((s, a) = Tknoww then Update K, T and R U,, R)
Save M (T) in M
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 î and ft, and the upper bound Q on QM- Saving this information when the task changes allows to compute the upper bound Equation 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 MM git and eventually Ú, allowing for more efficient transfer where the task similarity is appraised. The resulting algorithm, Lipschitz RMax (LRMax), presented in Algorithm 1. To avoid ambiguities with M, use M store learned features (T, R, K, Q) about previous MDPs. In 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 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 A - 3), which is improved by LRMax in Proposition 5 and meets Condition C2. Finally Ü is a proved upper bound with high probability on Qi which avoids negative transfer and meets Condition C3.
M
Proposition 5 (Sample complexity (Strehl al., 2009)). With probability 1 5, the greedy policy w.r.t. Q computed by LRMax achieves an e-optimal return in MDP M after
SH x A ( 2 (i(())
(011-)) 7)3
samples (when logarithmic are ignored), with Ü defined in Equation 9 a non-static, decreasing quantity, upper bounded by I-4.
Consequently from Proposition 5, the sample complexity of LRMax no worse than that of RMax.
Proposition 6 (Computational complexity). The total computational complexity of Lipschitz RMax
ò T+ ( A2 (og(A))(2N + +1) log cQ(1-7)
(1-
with the number of interaction steps, EQ the precision of value iteration and N the number of tasks.
5

---

Under review as a conference paper at ICLR 2020
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 I' 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 TV (s, (), it is easy to show that model pseudo-distances are al- 1+7 ways upper bounded by I- 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+y. For instance, the distance between two games in the Arcade Learning Environment (ALE) 1-y
(Bellemare et al., 2013), is smaller than the maximum distance between any two MDPs defined on the common aate-acciin space of the ALE (extended discussion in Appendix, Section L). Let Duax (8, a) - max M. M.M.EMM (WW (s, a)} be the maximum model distance at a particular s, a pair. At
Prior knowledge might indicate a smaller upper bound for Dmax a) than 1+% We will note such I-
an upper bound Dmax-- Solving Equation 7 boils down to accumulating MM (s. values in d(ss, a). Reducing a MM (s. a) estimate in a single (s. pair actually reduces di(s, a) in all (s, a) pairs. Md (s, a) in Equation 7 by min ( DM (s, a)}, provides a smaller upper bound M on d and thus a smaller Ú which allows transfer if it is lesser than - Consequently, such an upper bound Dmxx can make a difference between successful and unsuccessful transfer, even if its value is of little importance. Conversely, setting value for Diax quantifies the distance between MDPs where transfer is efficient.
Thus, replacing AM
Furthermore, one can estimate online the value of Dmax(ss a), lifting the previous hypothesis of available prior knowledge. One can build an empirical estimate of the maximum model distance at 8, a: D mmax(s, a) A M, MM (s, a)}, M being the set of explored tasks. The pitfall being that, with few explored tasks, Dima (s, a) could underestimate Dmmxx a). Proposition provides a lower bound on the probability that Dmaa a) does not underestimate Dmax (8, a). depending on the number of sampled tasks. In turn this indicates when i maxx (8. a) upper bounds D a) with high probability, which can be combined with Algorithm to improve the performance.
Proposition 7. Consider an algorithm producing c-accurate in La Li-norm model estimates with probability at least 1 - 6 for subset of S x A after interacting with an MDP. For all s,a a E S x A. after sampling m tasks with Pmii MinMEM Pr(M), the following lower bound holds:
Pr (Dmax (s, 2) Dmmxx(s, a)) 2 1 - 2(1 - -Pmin)" + +11 10-22 -2pmin)
The assumption of a lower bound Pmiin on the sampling probability of a task implies that M is finite and is commonly seen non-adversarial task sampling strategy (Abel et al., 2018).
EXPERIMENTS
The experiments reported here' 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 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. (RMax(z) denotes Algorithm 1 with prior Dmax = x. Max MnxQInit 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 tighter upper-bound bound on Q' than 1--.- Computing both upper- bounds and taking the minimum results in combining the two approaches. We include such a combination in
I Link to open-source code omitted for anonymity.

---

Under review as a conference paper at ICLR 2020
3.0
Average Relative Discomated Retum
1.2
Awenge Belasive Discouated Retum
2.5
1.0
2.0
0.8
1.3
0.6
1.0
Task namber
RMax
MaxQInit
LRMax
LRMoxQUait
(0
(RMa
250
5000
750
1000
1250 1500 1750 2000
Episade sumber
(a) Average discounted return vs. tasks
(b) Average discounted return vs, episodes
100
Relativ Relstive diccuntedd petuen
% use Lipechice boand
140
% convergenace speed-up
%. total return gain
120
100
0.5-
80
0.0
250
500
730
1000
1250
1300
1750
2000
Epiande mamber
RMax Teek =1
MasQlait Taok
11
L.RMaoo(0.)) Task
MasQlait Taok
12
LRM Task =
1.0
0.1
Priot knowleegee (known upper bound mank., DMR (s.
(c) Discounted return for specific tasks
(d) Algorithmic properties vs. Dmax
Figure 1: Experimental results
our study with the LRMaxQInit algorithm. Similarly, LRMaxXInit(z) consists in the latter algorithm, benefiting from prior knowledge Dmax =X. Jr.
The environment we used in all experiments is variant of the "tight" environment used by Abel et al. (2018). This is 11 11 grid-world, the initial state is the centre, actions are the cardinal moves (Appendix. Section M). The reward is zero everywhers except for the three goal cells in the upper-right corner. Each time a task sampled, a new reward value is drawn from [0.8, 1] for each of the three goal cells and probability of slipping (performing 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 pool of 5 possible different sampled tasks. Each is for 2000 episodes of length 10. The operation is repeated 10 times to provide narrow confidence intervals. We used Aknown 10, 0.05 and 0.01 (discussion Appendix, Section P). We drew tasks from 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 be finite, which a noticeable advantage in applicability. Other lifelong RL experiments are reported in the Appendix, Section N.
The results are reported Figure 1. Figure la 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 la). Figure 1e 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 Ie display moving average over 100 episodes. Figure 1d reports the benefits of various values of Duax on the algorithmic properties.
In Figure la, first observe that LRMax benefits from the transfer method, the average discounted return increases as more tasks are experienced. Moreover, this advantage appears as early as the second task. Conversely, the Max algorithm needs wait for task 12 before benefiting from

---

Under review as a conference paper at ICLR 2020
transfer. As suggested in Section 4.3, various amounts of prior allow the LRMax transfer method to be more or less efficient: smaller known upper-bound Pmax on D causes 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 x AA 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 x A, our case yielding low returns. Indeed, as promising regions 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 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 1e 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 allow for almost zero exploration of the task.
In Figure 1d, we display the following quantities for various values of Dmax: PLip. is the ratio of the time the Lipschitz bound was tighter than the RMax bound - PSpeed-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: PReturn: the relative total return gain on 2000 episodes of LRMax w.r.t. RMax. First, we observe an increase of Ptip as Dmax becomes tighter. This means that the Lipschitz bound of Equation 8 becomes effectively smaller than r- This phenomenon leads to faster convergence, indicated by PSpeed up. Eventually, this increased convergence rate allows for a net total return gain, illustrated by the increase of PReturn.
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 Mmax further increases this benefit. The method is comparable to the MaxQInit method and has some advantages such 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.
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- negaaiete 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 neganege value transfer via MDP similarity, development that was lacking in the literature. Key insights for the practitioner lie both in the theoretical analysis and in the practical derivation of transfer scheme that achieves non-negative transfer with PAC guarantees.
8

---

Under review as a conference paper at ICLR 2020
ACKNOWLEDGEMENTS
Omitted for anonymity.
REFERENCES
David Abel, Yuu Jinnai, Sophie Yue Guo, George Konidaris, and Michael Littman. Policy and Value Transfer in Lifelong Reinforcement Learning. In International Conference on Machine Learning, pages 20-29, 2018.
Haitham Bou Ammar, Eric Eaton, Matthew Taylor, Decebal Constantin Mocanu, Kurt Driessens, Gerhard Weiss, and Karl Tuyls. An automated measure of MDP similarity for transfer in rein- forcement learning. In Workshops at the Swenty-Fighth AAAI Conference on Artificial Intelligence, 2014.
M. G. Bellemare, Y. Naddaf, J. Veness, and M. Bowling. The arcade learning enviromment: An evaluation platform for general agents. Journal of Artificial Intelligence Research, 47:253-279, 2013.
Richard Bellman. Dynamic programming. Princeton, USA: Princeton University Press, 1957.
Ronen I. Brafman and Moshe Tennenholtz. R-max-a general polynomial time algorithm for near- optimal reinforcement learning. Journal of Machine Learning Research, 30ct):22 2002.
Emma Brunskill and Lihong Li. Sample complexity of multi-task reinforcement learning. arXiv preprint arXiv:1309.6821. 2013.
Emma Brunskill and Lihong Li. Pac-inspired option discovery in lifelong reinforcement learning, In International Conference on Machine Learning, pages 316-324, 2014.
James L. Carroll and Kevin Seppi. Task similarity measures for transfer in reinforcement learning task libraries. In Proceedings. 2005 IEEE International Joint Conference Neural Networks, 2005., volume 2, pages 903-808. IEEE, 2005.
Christoph Dann, Tor Lattimore, and Emma Brunskill. Unifying PAC and regret: Uniform PAC bounds for episodic reinforcement learning. In Advances in Neural Information Processing Systems, pages 5713-5723, 2017.
Norm Ferns, Prakash Panangaden, and Doina Precup. Metrics for finite Markov decision processes. In Proceedings of the 20th conference Uncertainty in artificial intelligence, pages 162-169. AUAI Press, 2004.
Alessandro Lazaric. Transfer in reinforcement learning: a framework and a survey. In Reinforcement Learning, pages 143-173. Springer, 2012.
Alessandro Lazarie, Marcello Restelli, and Andrea Bonarini. Transfer of samples in batch reinforce- ment learning. In Proceedings of the 25th international conference on Machine learning, pages 544-551. ACM, 2008
MM Mahmud, Majd Hawasly, Benjamin Rosman, and Subramanian Ramamoorthy, Clustering Markov decision processes for continual transfer. arXiv preprint 13/ 2013.
Jerzy Neyman. X outline of a theory of statistical estimation based on the classical theory of probability. Philosophical Transactions of the Royal Society of London. Series A, Mathematical and Physical Sciences, 236(767):333-385) 1937.
Jason Pazis, Ronald E. Parr, and Jonathan P. How. Improving PAC exploration using the median of means. In Advances in Neural Information Processing Systems, pages 3898-3906. 2016.
Joëlle Pineau. Machine learning reproducibility checklist. https: / www. cs. mcg. 1 ca/ jtplieee//egrrooucibiitttyttoiie
.df, 2019. Version 1.2, Mar:27 2019.
Martin L. Puterman. Markov decision processes: discrete stochastic dynamic programming. John
Wiley & Sons, 2014.

---

Under review as a conference paper at ICLR 2020
Karun Rao and Shimon Whiteson. V-MAX: tempered optimism for better PAC reinforcement learning. In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems, pages 375-382, 2012.
Daniel L. Silver, Qiang Yang, and Lianghao Li. Lifelong machine learning systems: Beyond learning algorithms. In 2013 AAAI spring symposium series, 2013.
Jinhua Song, Yang Gao, Hao Wang, and Bo An. Measuring the distance between finite Markov decision processes. In Proceedings of the 2016 international conference on autonomous agents & multiagent systems, pages 468-476. International Foundation for Autonomous Agents and Multiagent Systems, 2016.
Jonathan Sorg and Satinder Singh. Transfer via soft homomorphisms. Proceedings The 8th International Conference Autonomous Agents and Multiagent Systems- Volume 2, pages 741-748. International Foundation for Autonomous Agents and Multiagent Systems, 2009.
Alexander L. Strehl, Lihong Li, and Michael L. Littman. Reinforcement learning in finite MDPs:
PAC analysis. Journal of Machine Learning Research, 10(Nov):2413-244: 2009.
Richard S. Sutton and Andrew G. Barto. Introduction to reinforcement learning, volume 135. MIT press Cambridge, 1998.
István Szita and Csaba Szepesvári. Model-based reinforcement learning with nearly tight exploration complexity bounds. In Proceedings of the 27th International Conference on Machine Learning, pages 1031-1038, 2010.
Matthew E. Taylor and Peter Stone. Transfer learning for reinforcement learning domains: A survey. Journal of Machine Learning Research, 10(Ju)):6333166) 2009.
Cédric Villani. Optimal transport: old and new, volume 338. Springer Science & Business Media, 2008.
10

---

Under review as a conference paper at ICLR 2020
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 that, for new target task, the value function of the closest source task 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 the optimal policy while interacting with 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 deterministic and the initial state is
a1
a0
80
$1
ao
a1
Figure 2: 2-states MDP
always so. In the first MDP M1 E .,, the reward is 0 everywhere except for R2: = 1. In the second MDP M2 E M, the reward is everywhere except for Rs With a discount factor y 0.9, the value functions and Q- O-functions of both MDPs are summarized in Table 3 Using the weighted
M (-) 10
Qi, (.. ag)
Qi (,a))
V M.(+)
(-)
(,,,),a)
Qi,, (.a1)
80
10
8.1
4.74
4.26
4.74
9
8.1
9
5.26
4.74
5.26
Figure 3: Value functions and Q-functions MDPs Mi and M2
transfer technique from Mj 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.
Qiranterr (so, 0p) = 2.03
Qreanster (so, 01) 2.25
transfer (81, ao) 2.5
Ma
transfer (81, 01) 2.03
M2
First, Qtransfer 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. Quanster would never discover the state-action pair 81, 01 in M2 which is the maximum-rewan pair. Instead, the agent would go from so 8 and perform self-loops thereafter.
As 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 too high. The approach we develop in this paper used the distance to build optimistic upper-bounds bounds on the f-funciio.. Those upper-bounds are simply of no use when the distance too high which is equivalent as avoiding transfer.
11

---

Under review as a conference paper at ICLR 2020
B DISCUSSION ON METRICS AND RELATED NOTIONS
metric on a set X function X X which has the following properties for any 2, X:
1. m(x; y) 0,
2. m(x, y) 0 +x==1
3. m(z, y) m(y,x),
4. m(z 2) S m( y) + my 2).
With only m(x 0 instead of property 2, would be pseudo-metric. Without property 3, one has a quasi- Without property and 4, and when X is a set probability measures, one has divergence.
In Definition 1, DM, zero distance between different models.
M, (, a) is indeed pseudo-metric over MDPs since the choice of f can lead to
The local MDP dissimilarity between MDPs (s, a) of Proposition does not respect properties and 3, hence the name dissimilarity. The A (s, å min [d (s, (s.a), a), d (s, a) quantity, however,
regains property and is hence pseudo-metric. An important consequence is that Proposition 1 "in the spirit" of Lipschitz continuity theorem but cannot be called as such, hence the name pseudo-1 isschi-Lipschitz continuity.
The same goes for the global dissimilarity dM T- aeSxA PM (s. However,
using min ddd dM 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 unique solution which we call add
d(s,a) D M (8,a) ETe Toe max dis' Vs, E A.
Proof of Lemma 1. The proof follows closely that in Puterman (2014) that proves that the Bellman operator over value functions is contraction mapping. Let d, and d2 be two functions from S x A to IR and let I. be the functional operator that maps any function d S x A IR to
Ld 8,
D DM (8, a) + Σ Ta max d(s',a''.
a'
Then (s, - Ldb(s, a)
E. Ta [max,/ di (s', a') max d2(s', a')). max (8 a') - max. d2(8' a') < max, (d',"'''') de(,', a')l < 1d d2 lol. And so [[d, Ldzlloo < <7lld
But
d2 dolloc- Since 7 T. is contraction mapping in the metric space (S A. ll This metric space being complete and non-empty, it follows from Banach fixed point theorem that d Ld admits single solution.
Lemma guarantees the existence of d. Proposition states that for any two MDPs M and M and for all as S A. (s. - (s, a)) S min { ( a), a (s.
Proof of Proposition I. The proof is by induction. The Value Iteration sequence of iterates (Q), nNN for task M is:
(s) 0, S x A
2 (s,a) R + Σ The max Q Vs
a'EA
s'ES
12

---

Under review as a conference paper at ICLR 2020
It is obvious that ()r(s,a) (s) I as) Suppose that (Qir(s, (2 1
(s, a). Then:
1M (s, -QM
- (s,
R2 Rg + +
Σ
The max Qi: (s d'EA
T max Q (s',
(s',a' ,a')
a'EA
S'ES
S
R
R +
Σ
The max QM (5', ,a))
T max Q 17 (s') d'EA
d'EA
S'ES
$
R
Ra
+Y
Σ
max
Q (s',a') T - Tsa
d'EA
S'ES
+
T
max R'EA
Q (8 a') - max 2 (5',
a'EA
ES
S
R
R
(s') T - |
ES
+7
The
max a'EA
Q (2','''')) a²) - (''
E'ES
DM Ma
(8,0)
Σ The max (8', a')
(M
#'ES
Since Qi and Qh respectively the limits of the (Qir) and (2 NEN sequences, the result that (s, Q (s, a)l I did (s, a) follows from passage to the limit.
By symmetry, on also has 10 (s. a) Qaa a) s d (s,a) and thus (s, as) s min d (s, a), a (s.
D SIMILAR RESULTS TO PROPOSITION 1
Similar results to Proposition I can be derived with similar proof in Section C. The first result is for the value function and stated below.
Proposition (Local bound on the distance between value functions). For any two MDPs M and M, for all s E S,
VV (s) V (s) max (s.a)
a
where the local MDP pseudo-metric A MM (s, a) has the same definition as Proposition 1.
Another result can be derived for any policy æ that one wishes to evaluate both MDPs. For the sake of generality, we state the result for any stochastic policy mapping states distributions over actions. 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, E S x A.
(s) V (+) A (s)
where dz (8) is defined with the following fixed-point equation:
d (s) BRawT
D DMvva (s. + Σ The Tay dr (5))
e'ES
and A n. A0 (8) = min { M
d (6), d.T.M((() (5)
13

---

Under review as a conference paper at ICLR 2020
E
GLOBAL PSEUDO-LIPSCHITE CONTINUITY RESULT
consequence of Proposition is a global geeudo-Lipschite continuity property: Proposition 8 (Global pseudo-Lipschitz continuity). For two MDPs M, M. foror all (s, 8 A.
(Q - (s, S min { &M 5 M
with 5 - 1 8.0ESXA
{
DDMM 7 (8, (s, a)}. (10)
max
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 happens, is too late for transfer to be useful).
Proof. The proof by induction and reuses the notations introduced in the proof of Proposition 1. is immediate that
(M, - Uie (s, a) < d and (Rr(s - Q (s, a) & d
Hence, the result holds for n 0. Let us suppose that
(s, - Q/ (s, a)
- d and
(M,(s, Qie (8. d
Then. 1 (s,a)-Qka -Q (s,a)) S DM
M (8,a) +7 Σ
Th max
Qir(s',
22r (5',6'a))) ,a)l
a'EA
3'ES
DM MMV (8,
+ Σ 98'
1
1 M (s)
s.aESxA
e.EEAA
DMM |M (0,
(1 1+
-
7
S max
1-7
saaESxA
s M
F PROOF OF PROPOSITION
Proof. The result is clear for all 8, a & K since the Lipschitz bounds are provably greater than Q% %/- For s,a E K, the result is by induction. Let us consider the Dynamic Programming (Bellman, 1957) sequences converging Qi and at rank n whose definitions follow:
Qir,o(s,a) = 0
(Qmmn(s, = R + +,E, Tog max, Qiin-1 a')
(o(ssa) 0
(n( = R + 7 Eg The max Un Un-1(s',a')
Obviously, QM. a) I Uo(s, a). Suppose the property true rank n and consider rank
@M a) Un+ (s, = Σ T [max Qian a') max Un(s',a')) (()))')))
a'
< 7
Ta max a'
(Qi (s' d') Un(s',a') aa))
<
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.
14

---

Under review as a conference paper at ICLR 2020
G PROOF OF PROPOSITION 3
Consider two tasks M = (T, R) and M = (T, Rb, with K and K the respective sets of state-action
pairs where their learned models M (T, R2 and M (Ý. Rt) are known with accuracy e in -i-norm with probability at least 1 - 8, i.c. we have that,
Pr [ Real se 5 1 -11-6,80 a. EK,
(11)
Pr [
- l1 S E) 2 - V,Vs
Ths
(12)
and the same goes for M and its learned model M. We state the result for each one of the three
cases 1) 8, a E K, 2) 8, E Kn K and 3) 8, a E K n KS, the case 8, a E K n K being the symmetric of case 2).
1) If 8, E K n K, then properties 11 and 12 hold for both (R, with (R,,T) and (R,T) with (R. f). We have by definition:
D MM (s,a) R +
V - TTe
(13)
s'ES
The first term of the RHS of Equation 13 respects the following sequence of inequalities with probability at least 1 - 8:
R
R < R
Rg [Rg R
+ |
RM
R. + 2c.
(14)
The second term of the RHS of Equation 13 respects the following sequence of inequalities with probability at least 1 - ō:
7 Vi (s)) Tus S Y
V(s')
(Tap - fay
|
-Ta/
+
TTg
T
S'ES
2'E8
y max ((5)
Tag pa +7 Σ
V(s')
frz -f -faa ++
e'ES
s'ES
? max (s*)
ITa
Ta
3EES
S Σ V(8)
35' -
Tag + 20y max V('').
(15)
8'
e'ES
Summation of Equations 14 and 15 reveals DMM () = lR= R + (ss fm on the RHS of the inequality. Remarking this, we can upper-bound bound the model pseudo-distang of Equation 13 by the expected quantity with probability at least 1 8, proving the Proposition for case 1):
DMM We (s,a) a) S DMM (s,a) a) + (1 (1+ max V(s'))
8¹
2) 8f E K n Ke then properties 11 and 12 hold for (R, with (R. 7) only. Similarly to the proof of case 1), we upper bound sequentially the two terms of the RHS of Equation 13. With probability least 1 d, we have the following:
R
RCl
R
Ag +
|R
R
+ max ligg R.
(16)
ft
Similarly, with probability least 1 8, we have:
Σ EE
Vi
(s')
To < Σ V(s') (ITO - foa + 1/a T Tw/l)
EES
< max V )c max Σ ((s')(T - Tyll
(17)
3'ES
15

---

Under review as a conference paper at ICLR 2020
Combining inequalities 16 and 17, get the following with probability at least 1 6, noticing vV (s, a) on the LHS:
MM VV (8,a) S max D Mr
D PEM 7V (8,a) + 01+7 V(d'))
which is the expected result.
3) If 8 KS KS then properties 11 and 12 do not hold. In such a case, the result
D (s, a) - max D p.PEM. 7p (s.a)
straightforward by remarking that V (s) - (ss) with probability at least 6.
H ANALYTICAL CALCULATION OF AMM IN PROPOSITION
Consider two tasks M (T, R) and M (T, R), with and K the respective sets state-action pairs where their learned models M (T, Rt and M (T. It) are known with accuracy in Li-norm with probability at least achievable value. In the worst case where does not have any information the value of Vaax. one can always set Vaax y We recall the definition of the upper bound on the pseudo-metric between models:
note Vmax, known upper-bound on the maximum
DAM (s, a) + +2B
((ssa))KKK
D Ma
(s,a) +
PEM 7V
BMM (8,0)=
(18)
max Dus 7V (s, +
KK
max M.E.
D (s,
K
with B (1+1 7 max, V(s')) and D defined as in Equation 13. We detail the computation of DMM (s, a) for each cases 1) 8, E Kn K, 2) 8.8 E Kn K (the 8, K K is symmetric to this one), and 3) s, K n K Recall that we consider a finite, countable, state-action space S A.
I we have
DMM a) = -
7V (s,a) + 2B
= RR R. + Σ Vis'iTa - -fal + 2c (1 max V(s')) S'ES
Since is a known state-action pair, everything is known and computable in this last equation. Note that max,' V(s') can tracked along the updates of V and thus computation does not induce any additional complexity.
2) sf a Kn KnK- KS we have
DMM (s, a) max D
FEM 78 (s, a) +
max Ru Te
[ige Rgg +y
v(s') - -Ta.1) +e (1 max v(5)))
FES
Σ V(s))TT tol) + (1 7 max v(s'))
max
R
rl +
γ
max
re 0.1]
is
Σ 1=1
First, we have
max
|ス - r| = max
Rgg
ha
Reg
r
16

---

Under review as a conference paper at ICLR 2020
Maximizing the max4e]o.1] 1|j1a term is maximizing a convex combination of V (whose values are all positive) whose terms are not independent (since the to terms should sum to one). This is easily cast 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:
Vs'
A'' E E
/ = Sort states by decreasing value of V
While Eees t(s) <
- =op first state in
Assign t(5') & arg max [ 1| to (note that by {0, 13)
- -If Eeest te > 1, then to' + 1 Esesr t(s)
This allows calculating the maximum over transition models.
There is however 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 (s*) max, V(s) (often these are states in K Among those states, let If M has not been
us suppose there exists s unreachable from s, a, according T", that is T fully explored, is often the case in RMax, there may be many such states. Then the distribution t with all mass on s a maximizer of the (a, term. Conversely, if such state does not 0), then max, (ss) is an upper bound the ma,
exist (that is, if for all such states T
term. Therefore:
Σ VV))
tarl -brl)))r)))) max (s), with equality in many cases.
max tE tE(0,1]is) (s
3) If K Ks the resolution is trivial and we have
DMM (s,a) = max D M.E.M 70 (s,
[R - RCl + Σ V(S)]To - -Tay
max Rg a Reg. Rg.
e'ES
= max r.FE[0,1]
|r |-- Fl +
max
Σ V(s') 1oa 1o.--ta Tarl
1
s'ES
Σ 1=1
=1 y max (()).
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 Ci-norm with probability at least 1 - 8. If < this equation on d is fixed-point equation admitting a unique solution which we call d
d(s,a)= = (M +
Σ To Te max d(s', , a²) + max
dis) ifs K. e'xe
WES
ast
a'EA d(s', otherwise.
max
a'EEAA
Proof of Lemma 2. The proof is similar to the proof of Lemma 1. Let dy and d2 be two functions from S A to IK and let T. be the functional operator that maps any function d: S A + R
DMM (s, +7
Σ T ast
max d(s', a') +e max a'EA d(s',d a') otherwise.
d(s) if if K, s'aa'
Ld: 8
WES
BM (8, +y
max A'xAA
17

---

Under review as a conference paper at ICLR 2020
If E K, we have
Ldi ()) = Σ Two (na - max d2(5', a')) +
o
max 8''aa
,'), - ds))s,a))
< ( rc)
max di (s','') max d2(6 maxd2((' a')
s'.a'
$ 7(1 + e) s'a"
(d''s'a'') - d2(s',a'))
S >1 + e)lld1 - d2112x
If & K, have
Ldi(s,a) - Ld2(s,0)= =7 max d1 (5', max (
8'
8'a
S ty max (d1 dd) - d2(ss' d'))
8'
7 c)lld] d2ll c0.
In both cases, [Tdd Td22 |o S ~1 +clld d2 If (1 + < 1, T. is contraction mapping in the metric space (S A. || ll This metric space being complete and non-empty, it follows from Banach fixed point theorem that d = Ld admits single solution.
Proof of Proposition 4. The proof is done by induction, by calculating the values of d and d following the value iteration algorithm. Those values can respectively be computed via the sequences of iterates (d")) and (dm) MEN defined as follows:
(s. = Ys a E A
d (s. DMM (s, +7 Σ
To max (s' d')
a'EAA
S'ES
and,
(s))a) 0. Vs, a E S x A.
(M, +7
(s,
Σ ns' max (s', + max
)(),at) if E K, d'EeE
(s,
E'ES
a'EA (s','aa)) otherwise.
BMM (8, +7 max A'xA
The proof at rank n = is trivial. Let us assume the proposition d" < dm, Vs, a E S x A true at rank and consider rank 1. There
cases, depending on the fact that 8, is in K or not.
8, a E K, we have
d (s, -d (s,+ = D.M (s,a) - DM (s, (s,
Σ
Th max d'Ed
(s',a') - .r max d' (b,
d'EA
s'ES
d' (s',a').
max
o ESeA
Using Proposition 3, we have that AMM (8, a) is an upper bound on D&A (8, a) with probability at least 1 - 5. Hence
Pr (DMM (8, AMs (s, a) m0) 2 1 --
18

---

Under review as a conference paper at ICLR 2020
This plus the fact that dm d by induction hypothesis, we have that
dr+ (s, a)) d 7 E
max d' (s',a') (Tes a'EA s'E8
d" (s',a')
76
max
e' a''EAxA
Sy max
d" s' a'EAA
Tog - 1 +
e'ES
dm (s',aa))
76 max d'EEE
Since Pr (IT-T]li -11 =c) 2 1 8, we have with probability at least 8,
d (s,0) - dr+l( (+, S ,, max
(s'ss'a'') 7EE max
ds')
s',e'ESXA
s'Ee'ESXA
0,
which concludes the proof in this case. Conversely, s, a of K, we have
d=+ (s, a) dr (8, =000 17
DTVs (8, BMM (s,a)+ (s,a(s))++++
Σ The max (s', (s',a))=)) a')
ad',
max
a'Ed
o' ESxA
d'ES
Using the same reasoning than in case E K, have with probability higher than - ô
( (s, v Σ
The max d' (s', (s', max sa,'ESxA
(d',da'))
a'Ed
s'ES
S max 8' d'EEA
(d -7 o d'EeA
max
(s'
<
which concludes the proof in the second case.
J PROOF PROPOSITION 6
Proof. We follow the proof of the computational complexity of RMax proposed by Strehl al. (2009). The cost of Lipschitz RMax is constant 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 new state-action pair (labelling it as a known pair), the algorithm performs 2NV 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)) log
1
E(1 (1-7)
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 fixed state-action pair s, E S x A. For two sampled tasks M, M E M² we assume our algorithm to provide an upper-bound on vV (s, a) with probability at least 1 8. This assumption is actually guaranteed by Proposition while running Algorithm 1. With probability least 1 - ö,
D MM (8, 2 DMN (8,a), VM, E M?.
19

---

Under review as a conference paper at ICLR 2020
Hence, with probability at least - 8, DA (s,a) 2 DAVA (s)
max M.MEM
M.MEM
i.e. D (s)) 2 D Dmax(s.a).
In turn, the event of underestimating Dmax (s, a) occurs only the two tasks, that we note MI. Mgg M maximizing M, M + DMM yV (s, a), are not sampled, i.e. do not belong to M. Mj and M2 are not necessarily unique, but they could be. Since we aim at deriving lower bound on the probability of sampling Mi and M2. 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)" Consequently, if the sampling probability p of this task is lower bounded by Pmins the quantity Pmiin (1 - Pmin )
lower bounds P. Let us write X the random variable the number of samples required for sampling either Mī or Mī for the first time. By considering that the sampling probability of either sampling M1 M2 is lower bounded by 2pmin: follow the same reasoning as for P and obtain that
Pr(X=1) 2 2pmii (1 2pmin)'
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 x|x=
K-1
Pr(Y = k)=
Σ
Pr(Y K,
Pr(Y = k| = i)Pr(X = =1)
2
Σ (1 1=1
Pmin) )
22pmin) ( P-
(19)
Pr(Y = k) is the probability of first success step k. For Dmax (8, a) to estimate Dmax (8,a) in m steps, we require that this success occurs any time during the first m steps. we have:
Pr( max (s, (s,a) a) 2 Dmxx (8, a))
Pr = k)
k=2
Using Equation 19, we can deduce our result when remarking that necessarily pmin S 1/22
m k-1 (1 Pmin)
Pr(D max (s, a) 2 Diaax (s, a)) 2 2pthn.
) b
2pmin)) )a-1
1m im
m
I (1 Pmin ) j 2pmin) )
> 2p min
k=0 1=0
m-2
1
2pmin
2 2pm
Purin )
Pinin
i=0
m-2
1 (1
(1 2pmin k+1
2 2p
Pmiin )+
Pinin
p
(1 Pmin)
k=
2 2pmin
((1 Pmnin) ) k+1 (1 2pmin )+t1)
k=0
1 (1 Pmni)) m-1
> 2pmin (1 (miin)
1 - (1 Punin)
(1 2pmnnn) m-
22pmiu (1 2Pmmnu)
- (1 - 22pmiu)
> 1 - 2(1 Pmii)) m
+ (1 2pmin) )m
20

---

Under review as a conference paper at ICLR 2020
S
Figure 4: The tight grid-world environment.
L DISCUSSION AN UPPER BOUND ON DISTANCES BETWEEN MDP MODELS
Section 4.3 introduced the idea of exploiting prior knowledge the maximum distance between two MDP models. This idea begs for more detailed discussion. Consider two MDPs M and M. By definition of the local model pseudo metric D M in Equation 1, the maximum possible distance is given by
DMA (s,
1+2 1-7
M.MEM²
But this assumes any transition 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 game within the Arcade Learning Environment (Bellemare 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 given screen to another screen full of static. These examples illustrate why the knowledge of Dmax 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 neighboring state and never "teleport" the agent 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 priori is given on the maximum distance between MDPs. On the contrary, the knowledge of D allows faster and more efficient transfer between environments.
M THE "TIGHT" ENVIRONMENT USED IN EXPERIMENTS OF SECTION
The tight environment a 11 x grid-world illustrated in Figure 4. The initial state of the agent the central cell displayed with "S". The actions are moving I cell in one of the four cardinal directions. The reward is everywhere, except for executing an action in one of the three teal cells in the upper-right corner. Each time task is sampled, slipping probability of executing another action as the one selected is drawn in [0, 1] and the reward received each one of the teal cells is picked in [0.8, 1.0].
21

---

value of sampled in Under review as a conference paper at ICLR 2020
20 cells
S
Figure 5: The corridor grid-world environment.
Average Relative Discomatdd Return
2.0
Avenge Relative Disomated Raturn
1.5
0.6
0.5
0.4
Task namber
0.2
RMax
MaxQUnii
LRtMax
LRMoxQInit
0.0
()
()Max)
12
Episode number
Average discounted return vs. episodes Figure 6: Results of the corridor lifelong RL experiment with 95% confidence interval.
(a) Average discounted return vs. tasks
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 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 It > 0 is received when reaching the goal and 0 otherwise. At each new task, [0.8, 1]. The transition function is fixed and deterministic.
The key insight in this experiment is to lose time exploring the left part of the corridor. We ran 20 episodes of 1l 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 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 reported earlier and the combination of LRMax with MaxQInit outperforms all other methods by providing tighter upper-bound the optimal Q-value function. This decrease of sample complexity is also observed in the episode-wise wise display of Figure 6b where the convergence happens more quickly on average for LRMax and even more for MaxQInit. This figure allows the three learning stages of L.RMax 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 "G" while the initial state of the agent is the central cell, labeled possible, yielding different tasks with probability & of
with "S" Two walls configurations 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 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 Dinax decreases. The three stages behavior LRMax reported Section 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 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
its value and refines the upper- bound
22

---

Under review as a conference paper at ICLR 2020
G
S
Figure 7: The maze grid-world environment. The walls correspond to the black cells and either the green ones the orange ones.
0.35
Average Discomited Returu
0.30
0.25
0.20
0.15
RMax
LRMax-prior2.0
0.10
LRMax-prior1.0
LRMax-priorO.5
0.05
LRMax
0.00
RMax-MaxQUPB
Episode Number
Figure 8: Averaged discounted return tasks for the maze grid-world lifelong RL experiment.
to the MaxQInit estimation of maximum Q-values, we unsurprisingly observe that both algorithms feature a similar performance the maze environment.
O PRIOR Dma USE EXPER IMENT
Each time s, pair is updated, compute the local distance upper bound Đ (Equation 6) for all (s, a) E S x A. In this computation, We show that LRMax relies less and less on Dmax as knowledge on the current task increases. For this experiment, we used the grid-worlds environments displayed in Figures 9 and 10.
leverage knowledge of D select min D, D }
The rewards collected with any actions performed in the teal cells of both tasks are defined as:
(8z gn )2 (sy gyy}
R% exp
Vs (8z, 8y) E SSSa A.
2
where (sz, sy) are the coordinates of the current state, (gz: 9v) the coordinate of the goal cell labelled with and o a span parameter equal to the first environment and 1.5 in the second environment. The agent starts the cell labelled with the letter. Black cells represent unreachable
23

---

Under review as a conference paper at ICLR 2020
G
G
S
S
Figure 9: 4 times 4 heat-map grid-world. Slipping probability is 10%.
Figure 10: 4 times 4 heat-map grid-
world. Slipping probability is 5%.
I.MMa Dams 19)
LRMax max 17)
LRMax Daax 15)
LRMax Diax 10)
LRMax Danx 0)
% Prior Use
60
40
20-
0-
12
18
30
36
Computation Number
Figure 11: Proportion of times where D Dmax & DMM i.e. use of the prior, vs computation of the Lipschitz bound. Each curve is displayed with 95% confidence intervals.
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 D Dmax-
With maximum value D = 19, D is systematically lesser than Dinax resulting in 0% use. Conversely, with minimum value Dmax = O, the use expectedly increases to 100%. The in-between value of Dmax = 10 displays a linear decay the use. This suggests that, at each update, D < Dmax only true for more unique s, pair, resulting in constant decay of the use. With fewer prior (Dmax 15 17), updating pair, resulting in less use of the prior knowledge. The conclusion of this experiment that D max is only useful at the beginning of the exploration, while LRMax relies more on its own bound Ó when partial knowledge of the task has been acquired.
single 8, pair allows Î to drop under Dmax for more than one
P DISCUSSION ON RMAX PRECISION PARAMETERS e, ô, Tkknown
We used Mknown = 10, 8 = 0.05 and = 0.01. Theoretically, Rknown should be lot larger (> 109) 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 Rknoou are sufficient to reach an acceptable model accuracy Interestingly, empirical validation did not confirm this assumption for any RMax-baser 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 robust to model estimation uncertainties.
24

---

Under review as a conference paper at ICLR 2020
Q INFORMATIONS ABOUT THE MACHINE LEARNING REPRODUCIBILITY CHECKLIST
For the experiments Section 5, the computing infrastructure used laptop using single 64-bit CPU (model: Inte((R) Core(T'M) i7-48 17-4810MG 10MQ CPU @ 2.80GHz). The collected samples sizes and number of evaluation runs for each experiment is summarized Table 1.
Number of experiment repetitions
Maximum length of episodes
Total number of collected transition samples (s, r, s')
Number of sampled tasks
Number of episodes
Task
"Tight" task of Figures la lb and lc
10
15
2000
10
3,000,000
"Tight" task of Figure ld
100
2000
10
4,000,000
Corridor task
20
20
11
4400
Section N
Maze task
30
100
15
45000
Section N
Heat-map
100
100
600,000
Section O
Table 1: Summary of the number of experiment repetition, number of sampled tasks, number of episodes, maximum length of episodes and upper bounds the number of collected samples.
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-parametert were determined our appreciation, they may be sub-optimal but found the results convincing enough to display interesting behaviors.
25


Reviews:
[{"review_id": "SJxAe_yXoH", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Edit: in light of the discussion below, I have decided to raise my score to a 6.\n\n* Summary\nThis paper introduces a pseudo-metric based on a notion of Lipschitz continuity for action-value functions between different MDPs.\nThe algorithmic improvement is the use of the pseudo metric with RMax in lifelong RL.\nIn particular, the pseudo-metric is defined as the minimum between two dissimilarity measures, each of which can be solved with dynamic programming.\nThe pseudo metric is then used in conjunction with the optimal state-action value function for a previous MDP to form an upper bound heuristic.\nThis upper bound is used in RMax to improve exploration since it can be tighter than the naive RMax bound.\nEmpirically, the theoretical results are supported by thorough investigation on a variant of the grid-world environment.\n\n\n* Decision\nThe main contribution of this paper is hard to discern, but the ideas presented are interesting.\nDespite the theoretical nature of the paper, I find that the experimentation is overall lacking.\nIn the paper's current state, I would recommend a weak rejection.\nHowever, I am willing to increase this score if the presentation is improved and if the experiments are expanded.\n\n\n* Reasons\nWhile the paper motivates and explains the problem well, the proposed method is much less clear.\nFor example, Section 2 leading up to proposition 3 seems like it should motivate Section 3.\nInstead, I think that Section 2 does not communicate enough how the pseudo-metrics are planned to be used.\nPerhaps proposition 3 can be in the appendix and RMax should be discussed in section 2.\nOtherwise, the pseudo-metrics in Section 2 (and 3) should be motivated some other way.\n\nFor experiments, the paper provides a thorough investigation of one interesting environment.\nI think a similarly thorough investigation of another environment would greatly strengthen the paper.\nMultiple experiments that are less thorough would also benefit the paper, but less so.\nLastly, it would be interesting to compare to other non-PAC-MDP lifelong learning RL algorithms.\n\n\n* Details\n\nMinor concerns:\n\nI have trouble following the statement and proof of your probability bounds (for example, proposition 4).\nIt would be good to make more explicit what is a random variables.\nFor example, you define R_s^a to be the expected reward, but I assume that $(s,a)$ are random variables in the probability bound.\nIn addition, you occasionally refer to the propositions and equations as properties.\n\nPage 2: \"The extension to continuous spaces is straightforward but beyond the scope\"\nThis does not seem relevant since you only look at the tabular problem.\nWhile the definition might hold for continuous state spaces, the extension of LRmax to continuous spaces does not seem straightforward.\n\nMinor typos:\nPage 4: \"this information when the task changes allows to compute the upper bound\"\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "H1lP_6Mfjr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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. \n\nPros of this paper:\n- The idea of using the Lipschitz continuity of the value seems interesting \n- The paper seems to solve an important problem\n\nCons of this work\n- I think this paper is not yet ready for publication. It is not clearly written and the intuitions does not come up clearly through the writing\n- The intuition and the utility of this work is hidden behind the math and the theory\n- What are the key insights which a practitioner can derive from this?\n- The experiments do not seem realistic and rather contrived\n- Because of the mathematical density, the motivation of Lipschitz continuity  is not very clear\n- Lot of important details are not clear from the write-up. Is this the offline or the online setting (pointed out by the other reviewer as well). \n\nOverall, I think this paper is an important contribution. However, in its current form it does not seem accessible and lacks a lot of the motivation,", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BJx61rA3KH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Updated review: Thanks to the authors for response. I think it clarifies a few points for me except one, which is that I still dont understand how the ATARI games share the same state space? Under what model is this true? And if the paper really wants to use this as an example, why are there no results on even a single ATARI game. \n\n------------------------------------------------------------------------------------------------------------------------------------------------------------\nSummary: The paper presents a method for lifelong reinforcement learning problems. By lifelong reinforcement learning the paper means that a set of tasks, specified by MDPs, specified by reward and transition function (R and T) are presented to the agent sequentially and the agent must solve them. The idea of the paper is to assume that the tasks that live in the space <R, T> are Lipschitz continuous and if that is so the experience from the previous task can be used to upper bound the Q values for the current task. The paper suggests using the RMax algorithm that can take as input an upper bound (optimistic initialization) on the Q values of the MDP it is trying to solve and solve the MDP efficiently. For the proposed algorithm called LRMax, the paper presents theoretical results on the sample and computational complexity. The experiments on an 11x11 grid world show that LRMax is more efficient compared to other baselines. \n\nI think this is an interesting paper that takes a principled approach towards a lifelong RL problem. However, I find the paper hard to read and I think that the connection of what paper presents to a real-life problem is missing. \n\nThe assumption of Lipschitz continuity of tasks makes little sense to me. Does this mean that the state and action space of the MDPs that specify these tasks have to be the same always? Is that not a very restrictive set of lifelong RL problems? And if it is tried to remove the restriction just by assuming a very big state and action space and how do we verify the Lipschitz continuity and will the method scale to large state, action spaces?\n\nI also found it difficult to understand if the paper is considering an online setting or an offline setting. It seems to me it is considering an online setting, but then proposition 6 and 7 are called sample and computational complexity. In general, in online setting sample complexity can be expressed in terms of T - time step, or the number of rounds. But the paper presents computational complexity in terms of timesteps. Is it just wrong naming or Is the computational complexity the cost of computation at every time step? But then it includes a T term. For quite a lot of time, I thought that this is computational complexity and the T denotes the transition function until I realized, T in this theorem denotes time step. \n(Using T for transition function and the time step is confusing). \nBut then how can computational complexity (that measures the time required) be expressed in terms of time?\n\nThe paper claims that it proposes an upper bound on Q values of an MDP that can be computed analytically. I doubt that. First, I think that if this is true then it would have been useful to keep this algorithm in the main body of the paper. I particularly feel that such a bound is a big and important contribution. In any case, it is in the appendix. In the appendix, the paper basically proposes to use dynamic programming to compute the upper bound. So we do assume a model of the transition probabilities of the world that is explicitly maintained and probably learned from the experience of the agent. Does this not restrict the approach of this paper to very small problems for which such tables can be maintained? (This restriction is in addition to the restriction imposed by the assumption of Lipschitz continuity).\n\nExperiments: \nThe experiments shows that LRMax is more efficient compared to other baselines when it is presented with sequential MDP to solve. This is nice and expected. I think one of the experiments that would have been interesting is what happens when the tasks are not Lipschitz continuous. I would not expect the algorithm the perform well in such cases, but it would be good to know how poorly does the algorithm performs compared to other baselines. So how robust the proposed algorithm is to the assumption it is specifically designed for?\n\nMinor comments: \n- the paper keeps using the phrase ‘agent explores greedily wrt to Q function.’ I found this confusing, I think the paper meant agent acts greedily wrt to Q function. The world explore seems to indicate that there is a separate exploration phase. \n- The paper claims that distance between two games in arcade learning environment is smaller than the maximum distance between any two MDPs defined on a common state-action space of ALE. Can the paper clarify what this means. Is there a way to verify this claim. What are the common state action space of all games in ALE?\n If it is so, then the LRMax will do great in terms of transferring knowledge in between games on ALE. Why did the paper choose not to show results on ALE then?", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: While there was some support for this paper, there was not enough support to accept it for publication at ICLR.

The following concern is characteristic of the concerns raised by the reviewers: "The "main contribution of this paper is hard to discern, but the ideas presented are interesting." Other reviewers said it was "hard to read" and not ready for publication.

Decision: Reject