Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 1: Reject
review_content: The paper aims to build an understanding of deep RL. Because RL remains under-investigated from a theoretical point of view. Many algorithms use function approximation, off-policy learning and bootstrapping together--This is an unstable combination of techniques. In this paper, the authors propose a graph-perspective on the replay memory which allows to analyze the structure of deep RL.

The paper aims at an important issue in deep RL. The motivation of the paper is meaningful.
The paper gives a good summary of the previous related works in Section2.

The paper in the current form needs to be polished again. To obtain a better score, I suggest the authors to modify this paper in these ways: First, the introduction section needs to provide more details, including the pros and cons of previous related works on the research problem of this paper, the challenges you face when dealing with this issue and the contributions; Second, there were more than a few spelling and grammatical errors, please proofread the work and improve the writing; Third, the paper lacks logic in writing. The writing from Section.2 to Section.6 needs to be organized better. It is difficult for readers to grasp the key ideas of the paper through a quick assessment.
The paper focuses on the understanding of RL when deep Q-learning diverges, however, most of the conclusions in the paper are not based on the necessary theoretical proof, but the observations on the experiments.

It would be better if this paper can provide a clear illustration for the proposed method as well as the experiments section.
review_title: Official Blind Review #3

final_score: rating: 6: Weak Accept
review_content: This paper is trying to tackle the soft divergence issue in deep RL when algorithms combine function approximation, off-policy learning and bootstrapping, which is also called deadly triad by Sutton & Barto (2018). The paper proposes a way to represent the transitions in the replay memory as a data graph, then construct a simple MDP from it. Much more accurate Q values could be computed from the simple MDP and it provides a lower bound for the Q-values in the original problem. In this way, the method becomes less prone to soft divergence.

The idea of constructing a smaller MDP whose Q-values can be computed exactly by dynamic programming on tabular states, then use these Q-values to help dealing with the instability issues in deep RL is very interesting. In the rebuttal, I'd like the authors to address my major concern of the paper, where the proposed method seems to assume that the finite number of transitions could form a graph, which might not be always true. In typical continuous state spaces, the same state might not appear twice in the sampled transitions. In these cases, the graph becomes a number of disconnected chains and the Q-values from this MDP might not be accurate. Maybe I'm missing something, it's not very clear to me how the proposed method could be applied in the common case in deep RL where there's seldom a loop and the states are rarely visited twice. 
review_title: Official Blind Review #2

final_score: rating: 3: Weak Reject
review_content: 
The paper proposes Qgraph, an algorithm that  addresses the problem of extrapolation error that appear in RL tasks with continuous action spaces. The authors describe a method to construct a graph from transitions generated by some policy. In this graph nodes correspond to states and (s, a, r, s’, t) define transitions between these nodes. Then this representation is simplified and  used to compute Q-values using methods for tabular MDPs.

The related work section is missing several methods that attempt to address the same problem. Batch Constrained Q-learning (Fujimoto etal, 2018) introduces a formulation of Q-learning that constrains action selection with a generative model trained on a replay buffer in order to omit unseen actions. BEAR-QL (Kumar etal, 2019) describes a similar approach that uses a hard constraint based on MMD. It would be interesting to discuss connections with the recent work on off-policy batch RL.

The clarity of the paper can be improved. In particular, I have several questions regarding the method:
1) How are node of the graph are constructed? Does one state correspond to a single node or several states are merged into a different node?
2) How the actions are selected?
3) What are the assumption regarding the initial state distribution? Does the set of initial states have to be finite?
4) If two similar states appear in different branches of the graphs, are the corresponding nodes merged or not?
5) If the considered environments are deterministic, what is the motivation for stochastic approximation of dynamic programming?

The approach has several major limitations. One of the main limitations of the approach is that it can be applied only to deterministic tasks. Although it is not stated clearly in the paper, it seems also requires to have a finite set of initial states. 

The experimental evaluation is performed on a limited set of tasks and it is rather unclear whether the method can be scaled to higher dimensional control problems.

Overall, I feel that the paper needs to be significantly improved. 

review_title: Official Blind Review #1

Meta-review: This paper proposes a method to reduce the instability issues of off-policy deep reinforcement learning.  The proposed solution constructs a simple MDP from the experience in the agent's replay memory.  This graph is used to compute a lower bound for the values from the original problem. Incorporating this bound can make the learning system less prone to soft divergence.

The reviewers appreciated the motivation of the paper and the direction of this research.  However, the reviewers were not convinced that the formulation was sufficiently complete.  There were concerns that the method makes additional assumptions about the data distribution (the presence of state aggregation and the absence of repeated states in continuous spaces).  Reviewers found related work was missing.  The reviewers also found multiple aspects of the presentation unclear even after the author response.  

This paper is not ready for publication as the generality of the proposed method was not sufficiently clear to the reviewers after the author response.
Decision: Reject