Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: This paper proposes Episode Reinforcement Learning with Associative Memory (ERLAM), which maintains a graph based on the state transitions (i.e. nodes correspond to states, and edges correspond to transitions) and propagates the values through the edges in the graph in the reverse order of each trajectory. The learned associative memory is then used for the regularization loss for training Q-network. Experimental results show that ERLAM significantly improves the sample efficiency in Atari benchmarks.

- Overall, the paper is well-motivated and easy to follow. The experimental results demonstrate that the proposed method is promising. For the states that are already visited, instead of simply replacing the value to the better return (i.e. Eq. (1)), ERLAM makes join points to connect different trajectories, which enables further improvement via Bellman optimality-like backup (i.e. Eq. (3)).

- Can ERLAM deal with a stochastic environment? It seems that ERLAM would more likely to over-estimate the values for the state than the existing episodic RL algorithms.

- In order to make join points, it should be possible to determine whether two features of states are equal or not. How was this determined? It seems rare to reach the 'exact' same feature in Atari domains (i.e. 4 consecutive frames should be equal).

- In Algorithm 2, the pseudo-code is somewhat confusing in that R_t is appended to G before the episode ends.
review_title: Official Blind Review #1

final_score: rating: 3: Weak Reject
review_content: The paper proposes a new method for organizing episodic memory in with deep Q-networks. It organizes the memory as a graph in which nodes are internal representations of observed states and edges link state transitions. Additionally, nodes from different episodes are merged into a single node if they represent the same state, allowing for inter-episode value propagation of stored rewards. The authors experimentally evaluate the method against reasonable baselines and show improved performance in the majority of tasks.

While the proposed method seemingly leads to better performance, the analysis of the results appears superficial. First, it lacks theoretical rigor to explain why the proposed propagation mechanism works, for instance, a proof of the optimal substructure in Eq. (3) would be helpful. While I see the authors mentioned previous work which do not have optimal substructures and mention this for the case of navigation-like tasks, the matter is not discussed and unclear in other scenarios. 

This in itself would not be much of an issue if the experiments highlighted advantages and limitations of the proposed method, but that is not the case. For instance, per-task comparisons to EVA (mentioned in the paper) could indicate how useful inter-episode value propagation was in each task.  Table 1 mentions EVA, but only on aggregated results, thus not providing insight into this. Furthermore, the experiments selected to be detailed in Figure 4 are, in my opinion, suboptimal choices, as the worst-performing of the selected tasks is still better than the baselines. It would be more insightful to also compare those whose performance is close to the baselines, such as the Boxing environment, and significantly worse than baselines, such as the StarGunner environment (as shown in Figure 3). With those issues in mind, my conclusion is to recommend to reject the paper in the current state.

Minor comments:
- Thoroughly review the writing and grammar, the text in its current state needs significant improvement in this regard
- Equation references missing parentheses
- Introduction, 1st paragraph, second sentence is incomplete
- Algorithm 2: tuples taken from/appended to sets G and D are not consistent (cf. lines 11 and 13)
- Figure 3: The large amount of bars in the plot would benefit from horizontal lines across the plot for each tick on the y axis
- Table 1: caption before the table; should also state the meaning of numbers (percentage or normalized score, calculated from what?)
- Figure 4: labels (all text except plot titles) are impossible to read in print
- Section 3 could be placed before Section 2, laying the mathematical framework, and then following the discussion with related work
- There is redundant content in Sections 2 and 3


----

I am happy with the authors response and changed the score accordingly
review_title: Official Blind Review #2

final_score: rating: 6: Weak Accept
review_content: The paper proposes to combine DQN with a nonparametric estimate of the optimal Q function based on the graph of all observed transitions in the buffer. Specifically, they use the nonparametric estimate as a regularizer in the DQN loss. They show that this regularizer facilitates learning, and compare to other nonparametric approaches. I found the paper easy to read. The ideas are intuitive and seem to work.

It would be great to have more experiments providing insight into when the associative memory estimate works and when it doesn't. Since at the end of the day both DQN and the non-parametric estimate use the same data, there's no fundamental reason why the later should contain more information. Is it possible that more aggressive training of DQN would eliminate the need for the nonparametric estimate? Why would I expect the nonparametric estimate based on random projections to generalize better to new states than DQN? What would be the performance of DQN with only the random projections as inputs? I believe including experiments probing in this direction would make the paper better.

-------------------------------------------------------------------------------------------------------------------
Thanks for your response and the additional experiments. I still find the paper interesting and hence keeping my score as is.
review_title: Official Blind Review #3

Meta-review: The submission tackles the problem of data efficiency in RL by building a graph on top of the replay memory and propagate values based on this representation of states and transitions. The method is evaluated on Atari games and is shown to outperform other episodic RL methods.

The reviews were mixed initially but have been brought up by the revisions to the paper and the authors' rebuttal. In particular, there was a concern about theoretical support and the authors added a proof of convergence. They have also added additional experiments and explanations. Given the positive reviews and discussion, the recommendation is to accept this paper.
Decision: Accept (Poster)