Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: Some Reinforcement Learning algorithms like Q-learning are subject to a bias known as the maximization or overestimation bias. This is due to the fact that value iteration approximates the value of the next state as the max over actions of Q-values. As a consequence, if the Q-values are approximate, the maximum over such approximations tends to be skewed towards high values. Ensembling many independent estimates of the Q-values helps mitigatin the overestimation bias, but often at the risk of achieving the opposite effect, i.e. an underestimation bias, if the ensemble is too large.
The point of this paper is to propose and develop a method to estimate the current bias, and use that to estimate to dynamically choose the size of the ensemble so as to find a trade-off between over- and underestimation that minimizes the estimation bias.
The method is demonstrated on a simple toy task and then on control tasks with continuous action spaces simulated with MuJoCo physics engine.
main_review: The paper starts with an illustrative synthetic example of how an approximation error in the Q-values gives rise to an estimation bias that persists in the ensemble case, and motivating that an adaptive ensemble size would actually potentially mitigate this problem.
It then develops a theory that bounds the estimation bias of an ensemble of Q-values under the assumption of an approximation error that is uniform across across states and actions, an assumption that allows the authors to postulate an analytic expression for the approximation error that is used in developing the theory. This results in analytical bounds for the bias as a function of the size of the ensemble size M and the approximation error tau.
They then go on to develop a way to estimate the approximation error tau, relying on Monte Carlo returns computed over rollouts of the current policy.
The bias mitigation algorithm AdaEQ then basically consists in using this last estimate of the approximation error tau by plugging it into the expressions for the bias in order to recover a value of the ensemble size M that results in a bias that is between the estimated upper bound indicating overestimation and lower bounds indicating underestimation. 
The authors then demonstrate their algorithms against other ensemble-based bias mitigation strategies (REDQ and Average-Q) on three tasks from MuJoCO demonstrating competitive performance both in faithfully minimizing the estimation bias, and achieving higher average returns.
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
- Song, Z.; Parr, R.; and Carin, L. 2019. Revisiting the Soft-max Bellman Operator: New Benefits and New Perspective. ICML 2019
- D’Eramo, C.; Nuara, A.; and Restelli, M. 2016. Estimatingthe Maximum Expected Value through Gaussian Approxi-mation. ICML 2016
It would be nice if for completeness the authors considered citing these in relation to their work.

2. The paper is proposing a new and interesting theory-driven way of mitigating the estimation bias in Q-learning. Given how general this issue is, one of the main limitations of the paper is arguably the limited number of tasks and settings under which the algorithm has been empirically evaluated. Obviously, one cannot try everything, but it would have been instructive for instance to examine at least a few tasks with discrete action spaces, like for instance Atari 2600, to verify that AdaEQ properties extend to that case and the bias estimation can be used in other settings like DQN.

3. The assumption that the approximation error is uniform across states and actions seems like a big assumption. It is true that the width of the distribution is dynamically re-estimated at each iteration, but it would be instructive if the authors had a way of showing that this is an assumption that can be borne out empirically or if they could at least elaborate on it and why it is not too strong of an assumption.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes a DRL method AdaEQ to solve the overestimation problem of Q-function. The experiment results show that AdaEQ can outperform the baseline methods.
main_review: The overestimation of Q is the targeting problem of this paper. The proposed AdaEQ solves this problem in a two-stage procedure: approximate error characterization and ensemble size adaptation to minimize the bias. This is a natural solution for the targeting problem.
 
Originality: The authors propose to optimize the estimation of Q-value through modifying the number of the ensembled Q_{n}. The authors provide the guarantees of estimation error on Q_i in the proposed method. Unlike the existing ensemble methods, AdaEQ can adaptively choose the ensemble size due to the learning process. The experiment results prove that AdaEQ works.
 
Clarity: The theoretical elaboration part (section3) of this paper is very detailed and logical. But the exposition of the experiment is relatively less comprehensive. The introduction of the environment and the description of the task are unclear. It is unclear whether the authors have made any adjustments and modifications to the environment of Mujoco. It would be better to add some necessary description in the experimental background. Overall, the paper is well-written and easy to understand.
 
Quality: The theoretical part of this article is comprehensive. The experimental part should be enhanced by adding some necessary ablation studies—for example, the effect of the choice of c (in eq.10) on the result. Similarly in eq.10, whether the different sample methods of M affect the result.
 
Below are some questions and suggestions for this paper.
1. In fig.5, In the Ant environment, AdaEQ has a pronounced fluctuation. Considering that Ant is a relatively stable environment, this phenomenon should not happen. How to explain this phenomenon?
2. Does AdaEQ need more compute time than REDQ? If yes, how much time does AdaEQ take more than REDQ in each environment step?
3. Is AdaEQ sensitive to c(in eq.10)?
4. How does AdaEQ perform on other Mujoco tasks? Such as humanoid, hammock? If you have done this experiment, you can also show the results, even if the results are not competitive.
 
Overall, the experimental results can support the claim that AdaEQ can indeed improve performance on some tasks. Although this method is straightforward, it also provides a very general idea for optimization, which is very impressive. The experimental part of this article could be enhanced to provide strong support for the claim.

=== Post Rebuttal ===

The paper proposes a novel idea with a comprehensive theoretical analysis. The experiment can provide basic support to its claims.
limitations_and_societal_impact: See comments in "Main Review".
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: To mitigate the overestimation issue in Q-learning, this paper proposes an adaptive way to control the ensemble size of Q-function approximators. 
Experimentally, this paper demonstrates how the ensemble size affects the estimation bias.
Theoretically, this paper gives the upper bound and lower bound of the estimation bias according to the ensemble size. 
Finally, this paper evaluates the proposed algorithm in the MuJoCo environment. 

main_review: Originality: 
This paper studies the effect of ensemble size on the estimation bias. There are several works studying the ensemble size of Q-function approximators. But this is the first to study how to adaptively control ensemble size on the fly. The originality is incremental.

Quality: 
In response to the estimation bias, this paper discusses the upper and lower bounds experimentally and theoretically. 

Clarity: 
This paper is well written, clear and easy to read. 

Significance: 
The ensemble size heavily affects the estimation bias. This paper proposes a randomized algorithm which updates the ensemble size according to a pre-determined "tolerance". It is a rough way to adjust the ensemble size. In total, this paper makes an incremental contribution.

limitations_and_societal_impact: (1) This paper states in line 264-265 that "Recall that parameter c can be determined by using the upper bound and the lower bound in Theorem 2 (Theorem 1)." However, the upper bound and lower bound are determined by \tau_\min and \tau_\max, which are unknown variables. 
It is not clear how to determine c by the upper and lower bound, since upper and lower bound are unknown. 
(2) This paper studies the estimation bias of the ensemble size. It lacks analysis of how ensemble size affects the cumulative reward. 
(3) This paper selects three MuJoCo environments to evaluate the proposed algorithms. How about the rest MuJoCo environments? More experiments on discrete control tasks can make more evaluation of the algorithm.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: This paper proposes an adaptive ensemble size to prevent the over/under estimation bias that a too small/large ensemble creates due to time-varying approximation errors. They derive bounds on the estimation bias for an argmin ensemble method and propose an adaptive ensemble method to mitigate this over/under estimation bias problem.
main_review: Overall: The paper proposes an interesting problem and an interesting solution. However the paper
spends a lot of time using simple examples to show intuition where it is not clear whether these examples are “degenerate” examples (Figures 2 and 3 are unnecessary and so is Theorem 1 which is a simple case of Theorem 2). Furthermore they need to spend to spend more time justifying their more unusual generative assumptions (Uniform noise and using the argmin ensemble estimator). It is not clear whether this bias changing “signs” above a certain ensemble size problem is an artifact of the unusual “min” estimator. 

Major Comments: 

Line 122: Is the overestimation bias being positive proven in [16] or [6] or somewhere else, if so please state where and how. Otherwise, this seems like an extremely aggressive assumption. Or if by definition a bias being positive implies overestimation, then why can the bias not be negative? Is this not underestimation?

Why is it assumed that the approximation error has Uniform noise, not Gaussian noise? Furthermore the variance of distribution of the noise for each of the ensemble members depends heavily on \tau. For example if \tau is large, then the N \tau_i have higher variance, and this in turn makes the distributions of each error_i be more different from each other.

If too large of an ensemble size causes underestimation bias, and this bias is negative according to Line 189, why does averaging not reduce bias overall. Furthermore, why is Z_M being studied for only the argmin ensemble method and not the averaging ensemble method in Line 188/189. If only the argmin estimator exhibits both positive and negative biases, wouldn’t averaging an “ensemble” of those estimators create an unbiased estimator?

What is K and what is M in the example described after Theorem 1?

In the experiments in Figure 5, why is the bias almost always positive even for the “optimized” methods? Shouldn’t the bias be as likely to be positive as negative if the methods have been “optimized” and centered? Also what is the very large dip (between 1 and 1.5) in the AdaEQ model for Ant?

Minor Comments:

Line 106 missing “the” in “By definition, (the) Q-function is the expected return when” and this phrase is strangely worded “and following with the policy”

Line 230: Typo “thew”

limitations_and_societal_impact: Limitations: Addressed
Societal Impact: Not relevant
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper proposes an ensemble Q-learning which can adaptively adjust the ensemble size based on estimation error. The authors find that the ensemble min(Q_1, Q_2, ..., Q_M) may suffer from overestimation or underestimation with different M, so they propose to adapt M based on approximation error, which can minimize the estimation bias correspondingly. 

The paper analyzes both in theoretically and empirically, show better performance than the existing ensemble q-learning methods on a few MuJoCo benchmark tasks. 
main_review: The major contribution of this paper is to establish the correlation between the ensemble size and estimation bias under the ensemble q-learning framework(min operator). 

Overall Clarity is good. The idea is clear and easy to follow, and the authors show the motivation why they propose this adaptive ensemble size q-learning. 

Originality/Significance: I did not see exactly the same work before (to address the ensemble size). This paper tries to solve the ensemble size problem in ensemble q-learning, but it creates a new problem here, for example how to adjust the new hyperparameter c in Eq. 10. And the experiment show it impacts performance significantly in Fig.6(d). If we need to try different c and also need to set different M to get a good result, I do not see any practical advantage compared to TD3, SAC, etc

Regarding correctness of the algorithm: my main concern is when τ1 > τ2 > 0, \mathcal{K} \in [-τ1, τ1] but how do you get M\K \in [-τ2, τ2] in line 194-196. The problem is how do you define the set range \mathcal{M}. Another question your result in Eqs. 5 and 6 is from uniform distribution assumption, but you decide τ based on Gaussian in Eq. 9. Also you randomly sample in the following equation to get M does not make much sense to me. 

Regarding experimental evaluation: The experimental results show this method is sensitive to new hyperparameter c and it needs to carefully tuned to get good result compared to REDQ. As the authors propose a new ensemble q-learning by adjusting the size M, it is important to compare with TD3 and SAC on a wide range of tasks in MuJoCo environments on which most current continuous control algorithms have been evaluated and compared.

Overall, the authors need to address these concerns above before acceptance. 
limitations_and_societal_impact: NO
review_title: null

Meta-review: The paper presents a novel method to tackle overestimation bias in Q-learning. The majority of reviewers agreed that the paper is a good contribution to the NeurIPS community, albeit empirical evidence could be expanded further to consider additional ablation studies and environments. 
Decision: Accept (Poster)