Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The estimation bias is a quite general problem in Reinforcement Learning originally examined in Q-learning and due to the fact that the Bellman operator has a max operation which causes a systematic overestimation of state-action values. Double Q-learning had first been proposed as a way of mitigating this maximization bias, at the expense however of an opposite minimization bias.
This papers tackles the estimation bias in particular of Double Q-learning by proposing a new way of analyzing the problem from the perspective of the fixed points of a stochastic Bellman operator (where the stochastic components models the approximation error in minimizing the Bellman error). The main theoretical message of the paper is that the estimation bias is the result of suboptimal fixed points of the stochastic Bellman operator. Loosely based on this observation the authors then propose a "Doubly bounded estimator" which they show has a variance reduction effect. Although they do not provide any theoretical guarantees in regard to bias  reduction,t hey then test their algorithm on a few tasks of the Atari 2600 benchmark, empirically demonstrating that their algorithm results in faster rewards maximization compared to DQN, Double DQN.
main_review: The paper provides a new interesting point of view on the estimation bias in Q-learning in terms of suboptimal fixed points of a stochastic Bellman operator. This insight might have future implication of use for the field. However, there is a little bit of disconnect between this theoretical development and the algorithm proposed by the authors, in the sense that the theoretical insights do not seem to help much in motivating the proposed Doubly bounded estimator and the new training algorithm proposed by the authors, except for motivating the analysis of variance reduction. To justify the absence of theoretical guarantees in regard to bias redction, the authors state that "In general, there is no existing approach [that] can completely eliminate the estimation bias in Q-learning
algorithm." This might be right, however this statement should be qualified by specifying that there are methods to construct estimators that are guaranteed to still reduce the minimization bias of the double estimator. For instance, the papers [Zhu, R; Rigotti, M. 2021. Self-correcting Q-learning, AAAI 2021] and [D’Eramo, C.; Nuara, A.; and Restelli, M. 2016. Estimatingthe Maximum Expected Value through Gaussian Approximation. ICML 2016] each propose such an estimator. So, even if these methods are not guaranteeing a complete elimination of the estimation bias, they can still guarantee a reduction.
The experimental part on the Atari 2600 games show impressive speed up compared to DQN and Double DQN. It would be beneficial to the readership to know what criterion the authors used in order to select these specific games from Atari.
It would also be instructive to see a few benchmarks of the use of the new learning algorithm on classical RL tasks where the tabular case is "exact" in terms of state representations, to observe the behavior of the Doubly bounded estimator in this case.
limitations_and_societal_impact: 1. The paper gives a good overview of the relevant literature, but is failing to cite some recent related work like the following published papers:
- Zhu, R; Rigotti, M. 2021. Self-correcting Q-learning, AAAI 2021
- D’Eramo, C.; Nuara, A.; and Restelli, M. 2016. Estimatingthe Maximum Expected Value through Gaussian Approximation. ICML 2016
- Lee, D.; Defourny, B.; and Powell, W. 2013. Bias-Corrected Q-Learning to Control Max-Operator Bias in Q-Learning. IEEE ADPRL Symposium, 93–99
It would be nice if for completeness the authors considered citing these in relation to their work.
2. The paper could benefit from some additional experiments, in particular on classical RL tasks to help tease apart the benefit of the individual components of the algorithm, in the same spirit as the ablation study at the end of the paper.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes a new problem of double Q-learning, that is, the multiple fixed points caused by underestimation bias. This problem may lead to the non-optimal model after value iterations. Meanwhile, the authors provide many mathematical approvals. To solve it, the authors integrate another value estimator to escape the saddle points and approve its effectiveness with experiments. 
main_review: 1)	The existence of multiple approximate fixed points in double Q-learning. The examples used are so special that the existence of multiple approximate fixed points are unclear in practical games. Even if there is an approval in Proposition 2, the authors do not show the visualization of fixed points of the practical games.
2)	The authors use a well-shaped perturbation mechanism to remove non-optimal saddle points. But what is a well-shaped perturbation mechanism? Maybe, different network initialization is a good perturbation. This paper lacks the definition and discussion of perturbation. 
3)	The paper lacks the Algorithm table for detailed descriptions. 

limitations_and_societal_impact: This paper presents methodological work and does not have foreseeable direct societal implications.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper tries to address the possible underestimation issue of double Q-learning. Specifically, it shows underestimation bias may lead to multiple non-optimal fixed points, so it adds another target value from abstracted MDP to construct an integrated estimator, named doubly bounded estimator. It conducts serval experiments based on the standard Atari benchmark tasks, and the proposed doubly bounded estimator has shown promising results in bootstrapping the performance of double Q-learning algorithms.
main_review: This paper propose a simple but effective approach as a partial fix for the underestimation bias in double Q-learning. In pecular, it presents a doubly bounded estimator in Eq. 7, which takes maximum over two different bias estimators. The main idea is to leverage an abstracted dynamic programming as a second value estimator to rule out non-optimal fixed points.

Over all quality and clarity: its idea is clear, which is motived by the possible underestimation bias from double q-learning. This paper analyze non-optimal fixed points issue in both theoretically and empirically. And its experiment with a second value estimator does improve performance on a variety of Avari tasks.  

Originality/Significance: this work introduces a novel abstracted dynamic programming as a second value estimator to overcome the possible underestimation bias in double q-learning.


Some issues:
How do you guarantee y^{DP} >= y^{Boots} in Eq.7 while you use abstracted MDP to get y^{DP}? Otherwise, it falls back to original double q-learning.  It is better to add the condition in  Lemma 4 to Proposition 4 in line 274. The variance result in Proposition 4 needs V^{DP} <=E[T^{Boots}] to make it holds. In addition, it seems it is not easy to satisfy both y^{DP} >= y^{Boots} and y^{DP} <= E(y^{Boots})?

Possible lack of citation:
Deep Reinforcement Learning With Adaptive Combined Critics, 2020
Decorrelated double q-learning, 2020


limitations_and_societal_impact: NO
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: This paper studies the effect of the underestimation induced by Double Q-Learning, a well-known method to solve the overestimation problem of Q-Learning. The paper shows that Double Q-Learning might incur in suboptimal fixed points under an approximated setting, e.g. Double DQN, and proposes a method, i.e, Doubly Bounded Q-Learning, to curb this problem. The method consists of computing the target of the Q-Learning update as a maximum operator between the application of the Bellman operator on an approximation of the value function, and the application of the Bellman operator on the optimal value function computed on a discrete abstraction of the original MDP. The method is evaluated on several Atari games.
main_review: The paper investigates the important problem of biased estimate of the target value of the Q-Learning update. In particular, it describes an issue of Double Q-Learning that is not documented in literature, that causes the algorithm to incur in suboptimal fixed points in approximated settings. I think the paper conducts a reasonable analysis of the problem, and supports its claims with a simple, but meaningful, toy problem.
However, despite a satisfying analysis of the problem, I consider the proposed solution not rigorous enough. Although the authors make some claims about the effectiveness of the method to escape suboptimal fixed points, these claims are not supported by theoretical reasons. The sketch of the analysis on the saddle point-nature of these fixed points, and the connection with perturbed gradient descent, are interesting considerations that I think deserve a deeper analysis. The absence of theoretical guarantees on the bias obtained by Doubly Bounded Q-Learning is an important weakness of this paper, as well as the absence of theoretical guarantees about the performance w.r.t. the quality of the approximation of the MDP model.
The empirical analysis on Atari games is not satisfying enough, as many results of the baseline are significantly different from the ones reported in literature [1,2]. In general, I am aware Atari experiments are extremely sensitive to the choice of hyperparameters, thus, I’d rather see more reliable benchmarks to complement them. A toy problem to study more rigorously the effect of Doubly Bounded Q-Learning would be desirable. Also, it would be nice to have some evidence of the estimate of the Q-function computed by Doubly Bounded Q-Learning w.r.t. other methods. I encourage authors submitting a revised version addressing these points. Overall, this work is promising, but it needs still much work to be recommendable for publication.

[1] Van Hasselt, Hado, Arthur Guez, and David Silver. "Deep reinforcement learning with double q-learning." Proceedings of the AAAI conference on artificial intelligence. Vol. 30. No. 1. 2016.
[2] Wang, Ziyu, et al. "Dueling network architectures for deep reinforcement learning." International conference on machine learning. PMLR, 2016.
limitations_and_societal_impact: Not applicable.
review_title: null

Meta-review: This paper received mixed reviews, but the majority of reviewers were of the opinion the paper passes the threshold to be accepted.

The topic of the paper remains of interest to the community, and I think this paper might spark additional useful thoughts and investigations, so I'm also in favour of accepting the paper for presentation at the conference.
Decision: Accept (Poster)