Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a new way to make experience replay more efficient. Inspired by episodic learning, the authors treat the replay memory as an empirical replay memory MDP (RM-MDP). With dynamic programming, conservative value esimtate is learned by only considering transitions observed in the replay memory. Based on the empirical estimated dynamics, the authors propose value regularizer and policy regularizer and use these two regularizers to boost the learning process of DQN. To better understand the proposed method, the authors design metric for memory density, and empirically find a strong correlation between performance improvement and memory density. Extensive experiments show that the proposed CEER algorithm improves sample efficiency across several benchmarks in discrete action domains.
strength_and_weaknesses: Strength:
+ The perspective of treating the replay memory as an empirical MDP is interesting, and the proposed algorithms successfully improve sample efficiency by leveraging this empirical MDP.
+ The authors conduct a lot of solid experimental analysis to demonstrate the effectiveness of the methods, and provide interesting insights for future direction based on this work.

Weaknesses:
- The proposed method is only evaluated on limited environments. I think experiments on more complicated environments such as full suite of atari games are necessary to make the work more solid and convincing.
- The baseline considered in this work is not strong enough. It would be better to see if the CEER techniques can improve sample efficiency upon more powerful existing RL algorithms such as RAINBOW.
clarity,_quality,_novelty_and_reproducibility: I like this paper in general. The motivation of this paper is clear and make senses to me. The clarity is good. Related work is fully survey. The authors discuss about both limitation and advantages of CEER.

The results are significant, and the writing quality is good. The proposed approach is novel. The authors report most of hyper-paremeter settings. I believe this approach can be reproduced.

Typos:
1. Section 5.3, outperforms other baselines to a large margin -> by a large margin
summary_of_the_review: The paper proposes a new way to make replay memory more efficient. The authors conduct thorough empirical analysis to demonstrate the advantages of this work. I think this work could benefit future research on replay memory in RL community. However, further experiments on more complicated should be demonstrated to make the proposed algorithms more convincing.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: By considering it as an empirical Replay Memory MDP (RM-MDP), the authors in this study take advantage of the information contained in the experience replay memory. The authors discovered a conservative value estimate that solely considers transitions seen within the replay memory by solving it using dynamic programming. Based on this conservative estimate, value and policy regularizers are developed and integrated with model-free learning algorithms. To gauge the effectiveness of RM-MDP, they develop a memory density metric. According to the authors' empirical findings, there is a significant correlation between memory density and performance enhancement. They use a technique called Conservative Estimation with Experience Replay (CEER), which significantly boosts sampling efficiency, mainly when the memory density is high. Such a conservative approximation can nonetheless assist in preventing suicidal behavior and hence increase performance even when the memory density is low.
strength_and_weaknesses: **Strengths:**
- The paper is well-written and easy to follow.
- There are not many typos or punctuation mistakes as far as I noticed.
- The motivation is great, that is, considering the importance of neither temporally correlated nor single transitions but the entire replay buffer.
- Constructing an MDP over the collected transitions, and solving it through a modified dynamic programming scheme is novel.
- The authors perform a credible set of experiments on various benchmarks, such as using 20 random seeds and training for 2 million time steps are promising. The experimental setup and implementation details are explained in depth (e.g., hyper-parameter tuning).
- A comprehensive supplementary material is provided that enlights the depth of the study.

**Weaknesses:**
- The paper lacks a discussion over the competing methods. The authors only translate the results given in the Tables and Figures into sentences. Please describe in detail why competing methods exhibit poor performance, and what the reasons are. Focusing only on the proposed method in discussions decreases the explainability of the work and the introduced novelties. 
- The authors solve an MDP over the created graph according to the transitions contained in the replay buffer. However, in such a case, the MDP is always changing as new transitions are added to the buffer. Hence, this MDP is non-stationary. The authors did not address this. 
- The proposed method relies on prior offline/batch reinforcement learning approaches as the authors provide a reference to the corresponding papers. Moreover, the authors mention Experience Replay (ER) with reweighted updates, ER with episodic RL, and ER with reverse updates. The proposed framework contains similar entities from these three categories. I suggest the authors also discuss the most similar approach to their method in detail so that the novelty becomes more clear. Moreover, the work is very similar to the [paper](https://openreview.net/forum?id=HkxjqxBYDB) by Zhu et al. Please clarify this.
- The transition probabilities in Eq. (3) are calculated using visitation counts. How should the probabilities be calculated if the agent has never experienced a state or performed a certain action?
- The proposed method is _clearly for discrete action spaces_ as I believe constructing a graph for continuous action domains is impossible even under discretized environments because a slight numerical deviation may yield significant results in especially locomotion tasks and result in loss of information. 
- Conservative regularization is used for Q-network and policy to make their update closer to the MDP corresponding to the collected transitions. However, if the behavioral policy never improves (e.g., choosing similar actions for similar states), how come the proposed method is expected to advance the underlying RL algorithm, as the updates are conservatively regularized? Specifically, the conservative updates prevent the RL algorithm from taking large gradient steps; hence, the policy may never improve. This would go on recursively. Am I correct? The authors should discuss this.  
- Although the introduced performance metric, ARPI, seems to be a reasonable proxy for evaluating the performances, why didn't the authors use other metrics as given in the [work](https://ojs.aaai.org/index.php/AAAI/article/view/11694) of Henderson et al.? At least the authors could've discussed the existing metrics given in that [study](https://ojs.aaai.org/index.php/AAAI/article/view/11694) and maybe tried one of them.

**Detailed Comments**:
- Although the related work gives insights into the current approaches to experience replay, I believe the following work is worth discussing as they focus on either the Prioritized Experience Replay algorithm or reweighting the importance of transitions:
1) [An Equivalence between Loss Functions and Non-Uniform Sampling in Experience Replay](https://papers.nips.cc/paper/2020/hash/a3bf6e4db673b6449c2f7d13ee6ec9c0-Abstract.html) by Fujimoto et al.
2) [Actor Prioritized Experience Replay](https://arxiv.org/abs/2209.00532) by Saglam et al.
3) [Model-augmented Prioritized Experience Replay](https://openreview.net/forum?id=WuEiafqdy9H) by Oh et al.
4) [Off-Policy Correction for Deep Deterministic Policy Gradient Algorithms via Batch Prioritized Experience Replay](https://ieeexplore.ieee.org/abstract/document/9643162) by Cicek et al.
5) [Experience Replay Optimization](https://www.ijcai.org/proceedings/2019/589) by Zha et al.
- Fifth line in Section 3: Replace "expected cumulative rewards" with "expected discounted sum of rewards"
- First line on page 3: Give a reference to the [Dynamic Programming book](https://www.degruyter.com/document/doi/10.1515/9781400835386/html) when mentioning Bellman optimality equation
- Third line on page 3: No need to give a reference when mentioning deep neural networks
- Final paragraph in Section 3: There are sentences: _"Though the replay memory in online learning
is usually a time-changing first in first out queue, at a specific time step, the memory can be
considered as a static dataset that contains finite transitions. Thus, solving RM-MDP is similar to
offline RL setting that solves an empirical MDP and finally results in a conservative estimate."_ Are there any references?
- Fourth sentence in Section 4.3: There is a sentence: _"Our ˆQ value from RM-MDP is constrained in the replay memory that will never overestimate."_ The overestimation is induced by the maximization in the Q-network updates. Similarly, the proposed method also uses maximization even if across the recorded transitions. This sentence should be explained in more detail or a reference should be given, as it is a very strong claim.
- Please express the considered baseline algorithms in the full form, not using acronyms.
clarity,_quality,_novelty_and_reproducibility: **Clarity:** As I understood the study easily, I believe the authors clearly explain the majority of the work. 

**Quality:** This is a high-quality study. The approach is novel, in my opinion, and the empirical studies satisfy the deep RL benchmarking standards.

**Novelty:** The idea is very intuitive, and the proposed framework is novel.

**Reproducibility:** One of my main concerns is reproducibility. Although the experimental setup and implementation are broadly explained, there is no code given, even in the supplementary material. I strongly suggest the authors provide the source code for their project, either in a .zip file or an anonymous GitHub repository. Open an anonymous account, upload the code to a repo, and anonymize the repo to provide a link in the paper so that no one can identify the authors. This is a major concern.
summary_of_the_review: Although the paper combines model-based and model-free methods, many other papers have done the same. There hasn't been any discussion of their connections. Additionally, it is clear that the strategy could not be scalable to continuous state space. Moreover, the reproducibility of the introduced work is a major concern.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper presents an idea of combining conservative estimation with experience replay to improve sample efficiency. The key idea is to construct a graph based on the transitions stored in the buffer, where the transition probabilities are estimated based on the visiting counts. Then they use value iteration to solve the graph (i.e., an estimated MDP) to obtain the optimal Q-value for the estimated MDP. The obtained Q-value is further derived to an optimal policy. Finally, the optimal Q-values and policy are used to regularize the policy and value networks, where the optimal Q-values are combined with the RL Q-values with the weighted sum, and the optimal policy network is used as the target of policy distillation with KL divergence loss. Experimental results on several environments show that the proposed method CEER outperforms the baselines.
strength_and_weaknesses: Strengths:

1. The motivation is clear. The algorithm is interesting.
2. The authors show improvement in sample efficiency in a toy environment and some more complex environments in various domains.

Weaknesses:

1. While the paper focuses on the experience repay, I find the idea is actually to combine model-based and model-free algorithms. Several related methods should be discussed and compared, such as World Models [1] [2], and works that combine model-based and model-free methods, such as [3]. That being said, it is unclear what the novelty is without a comparison with these previous works.
2. Some missing related works in experience replay [4] [5].
3. I find the idea is very similar to ERLAM [6]. It seems the only difference is the way the regularizer is added.
4. In Eq. (3), the transition probabilities are estimated by visiting counts. In the case that a state has never been seen or an action has never been tried by the agent, how should the probabilities be estimated?
5. Can the methods be used in continuous state space? In this case, how to construct the graph, and how the value iteration can be applied?
6. The paper only reports sample efficiency but not wall-clock time. It is unclear how many additional computational resources are needed for the graph construction and value iteration.
7. How the memory density in Eq. (10) could be applied in continuous state space.




[1] Ha, David, and Jürgen Schmidhuber. "World models." arXiv preprint arXiv:1803.10122 (2018).

[2] Hafner, Danijar, et al. "Dream to Control: Learning Behaviors by Latent Imagination." International Conference on Learning Representations. 2019.

[3] Sun, Wen, et al. "Dual policy iteration." Advances in Neural Information Processing Systems 31 (2018).

[4] Zha, Daochen, et al. "Experience replay optimization." Proceedings of the 28th International Joint Conference on Artificial Intelligence. 2019.

[5] Fujimoto, Scott, David Meger, and Doina Precup. "An equivalence between loss functions and non-uniform sampling in experience replay." Advances in neural information processing systems 33 (2020): 14219-14230.

[6] Zhu, Guangxiang, et al. "Episodic reinforcement learning with associative memory." (2020).

clarity,_quality,_novelty_and_reproducibility: I do not have concerns about clarity, quality, or reproducibility. The novelty is unclear since the paper is similar to many works that combine model-based and model-free algorithms.
summary_of_the_review: The paper is well-motivated and presents an interesting idea. However, the paper is similar to many works that combine model-based and model-free algorithms. Their relationships have not been discussed. Also, the method may not be able to scale to large or continuous state space.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: In Strength And Weaknesses
strength_and_weaknesses: Summary: This paper considers constructing an empirical MDP from experience replay and estimates a Q-value function and policy from this empirical MDP. Then this paper applies these estimators to help train original Q-network. The benefit of the empirical MDP on replay buffer is the conservative estimation, which helps accelerate the learning process of orinigal Q-network.

Overall, I reckon the idea of this paper is quite novel and interesting, and this paper provides convincing empirical studies of their algorithms. However, there existing some writing issues and some further questions to me in the following. At the first stage, I would give a conservative evaluation of this paper with the score of 6. I will consider change my score with other reviewers' opinions and authors' responses.

Questions and Comments:
1. Eqn (1), the LHS is Q(s,a) but the RHS is the expectation over (s,a,s'). I believe it's a typo?
2. Eqn (3), what does the 't' mean for (s_t, a_t, s_t+1)?
3. In Data Structure of Section 4.1, the main purpose is to estimate the empirical transition probabilities by frequency estimation. My question is what is the role of the Graph? Without the Graph, it seems the estimation can also be derived.
4. I think the authors should be more specific on the expression of the sampling method in Section 4.2. Though I can understand what the authors are trying to say, others may not.
5. The authors should offer references on the overestimation problem on DQN in paragraph "value regularize".
6. Could the authors tell me more about how conservative policy $\hat{\pi}$ lower bounds the performance of policy $\pi$.
7. In algorithm 1, do updates in Line 9 and Line 10 share the sample minibatch? Why？
8. Actually, I'm curious about the choice of $\alpha$ in value regularize. It would be great if the author compare the performances of their algorithm with different choice of alphas.
9. To my knowledge, the model-free methods mean the memory space is taken up to $\mathcal{O}(SA)$. However, by constructing empirical MDP with estimation of transition probability, the memory space is taken up to $\mathcal{O}(S^2A)$, which should be model-based. I think the authors should be more precise on description of their methods in introduction and abstract.
10. In Section 5.4, the authors investigate the relationship between the performance improvement and conservative estimation. But I'm still confused with the intuition why density is correlated with the performance improvement. Could the authors provide a more high-level explanation in rebuttal?

==========================

After reading the authors responses and other reviewers' comments, I find the current version is qualified to be published. At the current stage, I prefer to raise my score to 8. If the other reviewers have more concerns, I'm willing to discuss with them and adjust my evaluation.
clarity,_quality,_novelty_and_reproducibility: In Strength And Weaknesses
summary_of_the_review: In Strength And Weaknesses
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: Summary:
The paper proposes to learn a graph-based MDP approximation from the data in the replay buffer, which is then solved and used to regularize both the policy and value function. They also develop a metric that can indicate whether the approach will work well for a given replay buffer. The approach is validated experimentally

Strengths:
- Well written paper
- Innovative approach
- Most questions resolved in discussion

Weaknesses:
- The approach is designed based on discrete states and discrete actions. The experiments show empirically that it also works well for large and continuous state spaces, there are some ideas on how to deal with continuous action spaces.
- The discussion on why baselines perform better has improved a lot, but still reads a bit more like hypotheses
justification_for_why_not_higher_score: The method makes intuitively a lot of sense but does not come with any formal guarantees While working well empirically with continuous/high-dimensional states combined with hashing, but I still have doubts how general this is.
justification_for_why_not_lower_score: All reviewers recommend accepting the paper.
Decision: Accept: poster