Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper argues that the DQN and its algorithm and its variants do not guarantee convergence and that they can diverge in realistic settings. 

The authors develop a new technique that guarantees convergence of DQN. The authors show that in the case of very large discount factors (such as 0.9998) this algorithm outperforms baseline algorithms on certain Atari games. 
main_review: The primary way in which the authors approach the problem of convergence of DQN and related algorithms is replace the use of a DQN-style target network with a minimization of the mean squared Bellman error (MSBE), the foundation of the residual gradient-type algorithms introduced in 1995. This type of algorithms however did not traditionally perform better than other approaches, especially in the context of deep RL. 

The authors are proposing an approach where the loss of their new algorithm C-DQN is the expectation of the maximum between the MSBE loss and a DQN loss which is derived from interpreting DQN as a form of fitted iteration. This definition enforces that both the DQN and the MSBE loss are decreasing during learning. 

While this guarantee is interesting, the experimental results do not show a clear motivation for the use of this approach. The experiments in which the authors succeed to show an improvement are hand engineered to show off the benefits of the approach - for instance the authors compare against DQN on space invaders where half of the data is randomly discarded, or when the replay buffer is using a random replacement strategy.
summary_of_the_review: The paper introduces an interesting perspective on guaranteed convergence for DQN. However, this is not the first algorithm that is doing so, and the experimental results show improvement only in specific selected, somewhat unusual circumstances.
review_title: null

final_score: rating: 10: strong accept, should be highlighted at the conference
review_content: summary_of_the_paper: The paper addresses the problem of unstable learning that arises in NFQ type RL methods. 
It is assumed that the problem can be overcome by a provably convergent NFQ-like method.
Such a provably convergent method is presented and tested on a selection of benchmarks and compared to DQN.

main_review: Strengths\
The topic is very relevant, with potentially very strong impact on the field of Q-function based RL.

The paper is excellently written.

The method presented is extremely simple and can be incorporated into a wide variety (probably even most) Q-function based RL procedures without much effort.

Weaknesses\
In my opinion, the choice of benchmarks is not well suited for examining limitations of the method. I suspect that in benchmarks that are strongly stochastic in the sense that from a state-action pair, successor states with strongly different values of the value function can be reached, the Bellman residual loss function dominates and therefore no advantage is gained over optimization with respect to the Bellman residual loss function and thus the solutions do not solve the RL problem.
It would, in my opinion, add considerable value to the already good paper if the behavior of the method were additionally examined on one or more benchmarks that have the property that from a state-action pair, successor states with strongly different values of the value function can be reached.
I realize that this cannot be easily incorporated into the limited number of pages, and the current excellent clarity of presentation should not suffer. Possibly this investigation could go into the appendix. Or this investigation could be considered as Future-Work.

Further comments\
I would appreciate it if in addition to current works that represent the field well, the pioneering works would also be referenced in each case. So instead of (Mnih et al., 2015; Hessel et al., 2018) rather (Riedmiller 2005, Mnih et al., 2015; Hessel et al., 2018).

Riedmiller 2005, Neural Fitted Q Iteration - First Experiences with a Data Efficient Neural Reinforcement Learning Method

And instead of (Munos & Szepesvári, 2008), rather (Ernst et al. 2005, Munos & Szepesvári, 2008).

Ernst et al. 2005, Tree-Based Batch Mode Reinforcement Learning 

A simple benchmark where the property that successor states with widely varying values of the value function can be reached from a single state-action pair is pronounced is the wet chicken benchmark (e.g., Hans & Udluft 2011). There is a one-dimensional variant and a two-dimensional variant that is somewhat more difficult. Perhaps an investigation with this, or a similar benchmark, would eliminate the concerns that in this case the Bellman residual is always dominant and CDQN performs worse than DQN ... or confirm it.

Hans & Udluft 2011, Ensemble Usage for More Reliable Policy Identification in Reinforcement Learning

I am not sure what is meant by the term "overgeneralization". If this means something other than the following definition: \
*The American Psychological Association defines overgeneralization as, “a cognitive distortion in which an individual views a single event as an invariable rule, so that, for example, failure at accomplishing one task will predict an endless pattern of defeat in all tasks.”*
then this should be explained and/or supported by a reference.

In "we construct a loss does not" probably a "that" is missing.

In Table 1 in the Appendix is written "DQN (ours)".

Please check the bibliography for accidental lower case letters, like „bellman“, „q-“, „td“

summary_of_the_review: The paper is excellently written. The method presented could be groundbreaking. However, it is not explored whether the proposed method is generally applicable (see "Main Review" for details).
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies several issues of DQN (basically FQI, a version of fixed-point iteration) and empirical Bellman error minimization (has a clear loss function). Several issues of MSBE are pointed out. The authors propose a new approach by replacing the DQN loss by the maximum of DQN loss and MSBE loss. Several experiments on Atari games support the argument. 
main_review: Overall, I feel this paper is well-organized and well-written. I can understand the message that the authors want to deliver. The experiments are well-designed and clean. The main limitation from my point of view is that there seems to be not too much new stuff. 

The only change w.r.t to DQN is Line 12 which modifies the loss to be the maximum of DQN loss and MSBE loss. All the other components remain the same and all the drawbacks are inherited (sample-inefficiency and exploration). A lot of efforts are made on some corner cases that DQN and MSBE fail. Since there is no theory for C-DQN (I mean convergence is not the ultimate goal since it may converge to a bad local solution. For online RL, you should study regret. For policy optimization, you should study sample-complexity), I am wondering if there exist other corner cases that C-DQN could also suffer. 

When the paper mentioned efficiency or inefficiency, I think it is worth pointing out it is sample-efficiency or computational efficiency. For the problem pointed out in Section 3, how it relates to the problem of exploration? Because from the description, the data quality seems to play an important role. I admit the exploration for deep RL is hard, but at least for tabular cases, there are sample and computationally efficient algorithms, say https://arxiv.org/abs/1807.03765 Is Q-learning Provably Efficient?. The community may need some principle ways to understand the inefficiency. Current Section 3.2 seems to be not very in principle. 

The limitation of MSBE has been studied for a long time in RL community. There are multiple important improvements on this but the authors didn't discuss in detail (although the authors cited them in one sentence). That means this paper is not properly positioned in literature. The widely known issue is the double-sampling issue (empirical MSBE is biased) and several works have been proposed to remedy this, "A Kernel Loss for Solving the Bellman
Equation". But in this paper, the authors still discussed and compared the original version of RG algorithm. Since the discussion in Section 3.1 is quite specific, it's hard for me to know if a similar limitation holds for recently proposed algorithms. 

"Although convergent gradient-based methods have also been proposed (Sutton et al., 2009; Bhatnagar et al., 2009; Feng et al., 2019; Ghiassian et al., 2020), they cannot be used with neural networks easily, and they often have worse performance than TD methods and DQN." If you want to make such arguments, please provide detailed references and explain the reason.
 
"In this work, we only consider the deterministic case and drop the notation Est+1 [·] where appropriate." I am wondering if the whole paper is limited to deterministic transition. If so, I think this should be highlighted in the abstract. In theory, there is a huge difference between deterministic case and stochastic transition. 

Minor: 1. "If the task is difficult" is vague. What do you mean by a difficult task? 2. In Figure 4, what the loss is for? 

summary_of_the_review: The noverlty and significance of the proposed algorithm is limited.
review_title: null

Meta-review: It is important to have good stable and trustworthy algorithms.  Though I am unconvinved that the C-DQN algorithm proposed here is the final word (and I suppose this is not controversial, and the authors might agree), the ideas presented here are sufficiently interesting to be disseminated and discussed more widely.  All reviewers recommended accepting the paper, and I'll follow their lead.

That said, the paper can still be improved, and the authors are encouarged to carefully consider the feedback provided by the reviewers.  In particular, it is good to be clear about which parts are principled, and which parts are somewhat heuristic or arbitrary, and could therefore presumably be improved in future work.  In fact, doing so clearly could make the paper _more_ rather than less impactful.

In any case, it seems good to include this paper at the conference, to highlight the questions and partial answers given here, and to inspire more discussion.
Decision: Accept (Poster)