Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: Edit: in light of the discussion below, I have decided to raise my score to a 6.

* Summary
This paper introduces a pseudo-metric based on a notion of Lipschitz continuity for action-value functions between different MDPs.
The algorithmic improvement is the use of the pseudo metric with RMax in lifelong RL.
In particular, the pseudo-metric is defined as the minimum between two dissimilarity measures, each of which can be solved with dynamic programming.
The pseudo metric is then used in conjunction with the optimal state-action value function for a previous MDP to form an upper bound heuristic.
This upper bound is used in RMax to improve exploration since it can be tighter than the naive RMax bound.
Empirically, the theoretical results are supported by thorough investigation on a variant of the grid-world environment.


* Decision
The main contribution of this paper is hard to discern, but the ideas presented are interesting.
Despite the theoretical nature of the paper, I find that the experimentation is overall lacking.
In the paper's current state, I would recommend a weak rejection.
However, I am willing to increase this score if the presentation is improved and if the experiments are expanded.


* Reasons
While the paper motivates and explains the problem well, the proposed method is much less clear.
For example, Section 2 leading up to proposition 3 seems like it should motivate Section 3.
Instead, I think that Section 2 does not communicate enough how the pseudo-metrics are planned to be used.
Perhaps proposition 3 can be in the appendix and RMax should be discussed in section 2.
Otherwise, the pseudo-metrics in Section 2 (and 3) should be motivated some other way.

For experiments, the paper provides a thorough investigation of one interesting environment.
I think a similarly thorough investigation of another environment would greatly strengthen the paper.
Multiple experiments that are less thorough would also benefit the paper, but less so.
Lastly, it would be interesting to compare to other non-PAC-MDP lifelong learning RL algorithms.


* Details

Minor concerns:

I have trouble following the statement and proof of your probability bounds (for example, proposition 4).
It would be good to make more explicit what is a random variables.
For example, you define R_s^a to be the expected reward, but I assume that $(s,a)$ are random variables in the probability bound.
In addition, you occasionally refer to the propositions and equations as properties.

Page 2: "The extension to continuous spaces is straightforward but beyond the scope"
This does not seem relevant since you only look at the tabular problem.
While the definition might hold for continuous state spaces, the extension of LRmax to continuous spaces does not seem straightforward.

Minor typos:
Page 4: "this information when the task changes allows to compute the upper bound"

review_title: Official Blind Review #4

final_score: rating: 3: Weak Reject
review_content: 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. 

Pros of this paper:
- The idea of using the Lipschitz continuity of the value seems interesting 
- The paper seems to solve an important problem

Cons of this work
- 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
- The intuition and the utility of this work is hidden behind the math and the theory
- What are the key insights which a practitioner can derive from this?
- The experiments do not seem realistic and rather contrived
- Because of the mathematical density, the motivation of Lipschitz continuity  is not very clear
- 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). 

Overall, 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,
review_title: Official Blind Review #1

final_score: rating: 6: Weak Accept
review_content: 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. 

------------------------------------------------------------------------------------------------------------------------------------------------------------
Summary: 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. 

I 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. 

The 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?

I 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. 
(Using T for transition function and the time step is confusing). 
But then how can computational complexity (that measures the time required) be expressed in terms of time?

The 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).

Experiments: 
The 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?

Minor comments: 
- 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. 
- 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?
 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?
review_title: Official Blind Review #3

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