Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: ##################################

Summary: This paper investigates the effects of approximation error in Q-learning - more specifically, the problem of having multiple non-optimal fixed points in double Q-learning. The authors claim that double Q-learning, which is a well-known approach to alleviate overestimation bias of Q-learning, can suffer from underestimation bias, and can lead to non-optimal fixed points. This paper provides theoretical evidence to support this claim. The main idea of this paper is to add real returns as a lower bound to the objective, and alleviate underestimation bias. Empirical results in Atari domains are presented. 

################################################

Pros

1. This paper addresses an important problem in reinforcement learning - approximation errors and bias in Q-learning. The major focus of the RL community on estimation bias has been overestimation bias (van Hasselt 2010), but this paper brings up the issue of underestimation bias (Lan et al 2020). 

2. This paper formalizes a way to model approximation error in Bellman operators in Q-learning (by setting a random noises as approximation error), and derives multiple theoretical insights and propositions (Existence of multiple fixed points in double q-learning). 

3. The idea of having return signal V_\tau (the returns gained from real trajectories) as a lower bound is simple and easy to implement. As for V(frozen\theta), the authors use both DDQN and clipped-DDQN objective; they combined these two with the lower-bound objective, and showed the performance of DDQN-LB and clipped-DDQN-LB., which performs better than previous baselines in multiple Atari domains. 

4. Comparison with n-step bootstrapping (Figure3) is also helpful; the idea is compatible with n-step bootstrapping, so it can be combined to improve the performance. 

################################################



Questions

1. Section 4: Choice of trajectory \tau for return signal V_\tau(s_{t+1}): this term is the discounted return of trajectory \tau in the replay buffer. Is this just a return value of one trajectory? How do you address the stochasticity of having real return value of one trajectory? Or is this an average of multiple trajectories that start from s_{t+1}? 

2. Have you ever considered other baselines like duel-DQN or Rainbow to compare the performance of your approach? I don’t think the empirical results (comparison with DDQN, DDQN, cDDQN, maxmin DQN, etc)  are already sufficient, but I’m just curious how it performs well compared to SOTA baselines. 


###################################################

Reasons for score: I think this paper addresses an important problem in RL, and presents a simple yet effective approach to address this problem. This paper is also theoretically well supported. 
review_title: simple yet effective approach to address estimation bias

final_score: rating: 3: Clear rejection
review_content: The paper considers the problem of learning a value function in a deterministic MDP and proposes a heuristic to reduce the bias of value estimates under the greedy policy. For this, they consider the class of Double Q-learning algorithms and describe a setting where estimation under this algorithm can lead to multiple fixed point solutions. They propose to control underestimation bias by estimating the next-state value as the maximum of either the current next-state value or the value of some trajectory in the replay buffer. They also propose another version that uses clipped target values. The two algorithms are evaluated on several Atari games and show, in some cases, improved transient behavior over double DQN. 

Controlling for bias due to function approximation is an important problem, and one where general solutions could have a potentially large impact for RL and AI. Giving this subject the attention it deserves will require an understanding of the bias problem in stochastic settings. Many will be curious about what can be said about this problem and its solution(s) using formal mathematical language. The multiple-solutions hypothesis is a plausible approach to gaining a better understanding of bias, but there could also be other angles to explore. 

I think the current research this paper presents should be broadened to understand not just deterministic environments, but stochastic ones as well. The experimental results should also be questioned: why is there little to no asymptotic performance gain using the proposed method if it indeed produces an estimate with less bias? There are more questions the community would wish to answer with a paper like this; Where does underestimation bias come from, and how can it be controlled in general? Currently, however, the presentation and technical material are not sharp enough to answer such questions. Therefore, it is important that the authors continue to mature this work so that, when it is ready for publication, it will make a significant contribution.

review_title: An interesting topic that needs to be better understood

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper analysed the underestimation bias induced by approximation error, by formalizing the underlying approximation, they theoretically proved the existence of multiple approximated fixed points which causes the converging to non-optimal solution. Besides, they proposed the lower bound double q-learning to overcome the underestimation bias. 

Strengths:
1.The paper is well-organized and the algorithm is simple yet effective.

2.The thought of formalizing the approximation error into noise is delighted which provides a way to theoretically analyze the effect of such error.

3.The definition and existence prove of approximated fixed points would helps the algorithm design to overcome the underestimation bias.

Weakness:
1.Some experiment is hard to understand. Table1 shows the TD-error and the absolute state-action value which didn’t demonstrate the small approximation error would cause significant estimation error which would cause the sub-optimal fixed points.

2.The effectiveness of lower bound double q-learning is doubtful. In MsPacman of Figure2, the algorithm shows slight performance decrease of Clipped DDQN, in some environment such as WizardOfWor, Zaxxon RoadRunner and BattleZone, these algorithms seems converge into same solutions. Besides, the algorithm would cause the overestimate the true maximum value. 
review_title: This paper analysed the underestimation bias induced by approximation error, by formalizing the underlying approximation, they theoretically proved the existence of multiple approximated fixed points which causes the converging to non-optimal solution. Besides, they proposed the lower bound double q-learning to overcome the underestimation bias. 

final_score: rating: 6: Marginally above acceptance threshold
review_content: This submission focused on the double Q-learning and investigated its underestimation bias issue. The authors claimed that using a double estimator can lead to multiple fixed points. To alleviate this issue, the authors proposed a correction approach by using the lower bound w.r.t. the real return. Finally, experiments on Atari games were conducted to show the improved performance, when compared with double DQN.

The authors aimed to analyze the underestimation issue in double Q-learning. The observation of multiple fixed points under the stochastic Bellman operator is interesting. The authors also tried to give more interpretation by providing sufficient conditions when this phenomenon happens. The proposed lower bounded double Q learning looks novel and reasonable. 

I am a bit confused about the authors' explanation on the multiple fixed points in Section 3.2. The authors claimed in the last paragraph that "..due to the existence of the approximation error, the induced policy π˜ suffers from a remarkable uncertainty in determining the best action on state s0, which is the main cause of these extra fixed points. " If this is indeed the case, the multiple fixed points are not necessarily linked to double Q-learning, as the approximation error can appear in any form of function approximation. 

Following the above point, I also don't quite understand the motivation about Definition 3. The authors claimed in Page 5 that "The monotonicity property is not a sufficient condition for Eq. (5) but it usually becomes a source of risks in practice." I just do not see how Definition 3 is necessarily connected with Proposition 3. The authors provided empirical observation that "During this process, a large magnitude of the first-order derivative could be found to meet the condition stated in Eq. (5)" However, this part in the curve also corresponds to the case of underestimation vanishing. Is this a contradiction here?

Another concern I have is regarding the comparison w.r.t. multi-step learning: The authors plot in Figure 3 the performance of n-step bootstrapping vs. LB, which I really appreciate. Note that this comparison is for the game Alien only; therefore, I am wondering if the conclusion holds for other games? It would be more convincing if the authors can provide more experimental results, as it can reinforce the authors' claim that the lower bounded approach rather than multi step learning is the main factor for performance improvement.

There is a related work on correcting biases in DDQN as follows, which may need to be discussed as well. The authors there also showed the improved performance on Atari games.

Song Z, Parr R, Carin L. Revisiting the softmax bellman operator: New benefits and new perspective, ICML 2019.

Minor comments: "...are meet..." -> "...are met..." in Page 5.
review_title: Review

Meta-review: This paper is rejected.

I and the reviewers appreciate the changes made by the authors. The paper presents:
* An analysis (based on techniques from previous work) of double Q-learning which shows that in an analytic model, double Q-learning can have multiple sub-optimal "approximated" fixed points.
* Propose a modification of the update that uses collected trajectories to lower bound the optimal value.
* Experiments on several Atari games.

While the theoretical results on double Q-learning are interesting, the authors provide little theoretical analysis of their proposed approach. Doing so will significantly strengthen the paper. Additionally, reviewers had concerns about the experiments. R2 questions the parameter setting in the multi-step experiments. 
Decision: Reject