Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: #### SUMMARY

The paper proposes a strategy for computing and propagating uncertainty to improve exploration in deep reinforcement learning. While the architecture necessary for computing the uncertainty is reliant on the framework of an existing deep RL algorithm — bootstrap DQN — the idea for propagation of this uncertainty to yield effective behaviour, or optimistic value estimates, hinges upon strategies used in the finite-horizon algorithms — constraining learning to be at the timescale of episodes (instead of samples).

The proposed main algorithm OEB3 — Optimistic Exploration with Backward Bootstrapped Bonus — combines ideas from existing literature to promote optimistic value estimates, and hence, as a product, effective exploratory behaviour. Particularly, I think it brings together 4 ideas from 4 different referenced papers: 
1. a learning architecture that implements non-parametric Bayesian Value Iteration (as done in Osband et. al. 2016)
2. uncertainty estimation (as done in Chen et. al. 2019)
3. uncertainty propagation by constraining learning timescale (as done in Lee et. al. 2019 and Jin et. al. 2019)
4. uncertainty propagation by bootstrapping from optimistic estimates (as done in Jin et. al. 2019)

The paper also highlights that due to the uncertainty propagation achieved by incorporating ideas from (3) and (4) the induced exploratory behaviour is more effective, and hence the sample complexity of learning is reduced. Therefore, instead of the more common 200M frames used for training deep RL agents, 20M frames are used for training in the experiments here.


#### STRENGTHS

I think the paper is a fine example of research that builds on existing ideas in the field. The relevant work is discussed and the paper gradually builds up to the core proposal. The empirical analysis is comprehensive across the Atari suite, in order to be wary of recent work that suggests design of deep RL exploration methods may be overfitting to performance measures in a skewed subset of Atari (although, as it seems to be de-facto standard of the field, it averages across 5 seeds). Additionally, as the algorithm does have many components, the paper does a good job of explaining the strategy employed for uncertainty propagation well in the text.


#### WEAKNESSES

While I do think incremental research that builds on existing work is very valuable, I think the paper can be improved due to the following three key limitations:
1.  the presentation style currently obfuscates the incremental nature of the paper. For instance 
	(a) the uncertainty estimation strategy is as proposed by Chen et. al. 2019, but the presentation seems to suggest it is novel. While Chen et. al. 2019 do not propose to “propagate” it during bootstrap as well, the bonus computed is the straightforward empirical standard deviation, as proposed by them.
	(b) the informal Theorem 1 (and corresponding formal Theorem 2) I think are well known in that the bonus used by UCB algorithms for linear regression is proportional to the posterior variance of bayesian linear regression. I am having a hard time seeing this as an insightful contribution. Further, LSVI-UCB is a frequentist solution approach and bootstrap DQN a non-parametric Bayesian approach — combining the two definitely warrants some discussion.
	(c) BEBU is essentially EBU as proposed in Lee et. al. 2019 with bonuses added. I do not think the text presents it so. Further, “faithfully follows the backward update of optimistic LSVI” may be a stretch as the optimistic LSVI bootstrap estimates are post learning at every step of backward induction.
2. While I understand a complete empirical comparison to the many existing deep RL methods can be very expensive, the literature review does miss methods proposed with a similar ethos — propagation of uncertainty. I think they need to be discussed and compared against
	(a) Bayesian Deep Q-Networks : Azizzadenesheli et. al. 2019 [https://arxiv.org/pdf/1802.04412.pdf]
	(b) Uncertainty Bellman Equation: Osband et. al. 2018 [https://arxiv.org/pdf/1709.05380.pdf]
3. Some of the proposals made are unclear and left unexplored/discussed.
	(a) bonus in bootstrap target - different from LSVI-UCB
	(b) $\epsilon$-greedy with bootstrap dqn - non-parametric “optimistic” bayesian approach with dithering?
	(c) computation of $\tilde{B}^k$ (I may have missed this, but presumably its the empirical standard deviation with the target networks of the ensembles)

Further, I think some discussion in the main/appendix are warranted in terms of the empirical setup: 
1. the buffer is a circular buffer of size 1M — is it 1M trajectories or 1M samples?
2. handling of episode cutoffs (which I presume are used), for bootstrapping at the end of the trajectory.
3. the magnitude of $\alpha_1$ and $\alpha_2$ are really small — the scale of the bonuses would be interesting to look into as well.


#### QUESTIONS
1. I understand the bonus proposed is an empirical surrogate to promote optimistic values (with respect to the seen data) — but ideally, do we not need optimistic values that include q*. What is the guarantee that q^* is included in the set (as it seems to be for the example in Figure 1).
2. What do you see are the key advantages of the proposed approach? Is scalability by constraining learning to be at the episode level an issue in practical applications? (I think this also can be discussed in the paper).


#### SUGGESTIONS
My concrete suggestions to improve the paper while keeping the core idea the same is two fold:
1. a more thorough empirical section comparing to methods designed for uncertainty propagation
2. a rewrite which reflects that the components of the core idea are existing proposals in literature in the case of both bonus estimation and the EBU algorithm.
3. I think it is surprising that OEB3 is poorer that Bootstrap DQN in Montezuma’s revenge - presumably an increased number of training steps should alleviate the discrepancy; if not, the bonuses propagated by OEB3 may actually hinder performance which I think warrants acknowledgment/discussion.

#### Minor typos
1. Mnist  —> MNIST
2. Medium —> Median (Table 1)
3. Presumably Figures 2 and 3 are bonuses during learning — but a phrase in Section 5.2 says “trained OEB3”.
4. Section 5.2: incentive —> incentivize



## POST-REBUTTAL

I really appreciate the author's engagement and response during the discussion phase to help me understand the paper better, and the revisions incorporated in the paper.
But after much thought, I do not think the current form of the paper meets the bar for publication.

Here are my main concerns that I hope is useful for the next version or final submission.

I think the core idea of the algorithm is uncertainty propagation is necessary for inducing effective exploratory behaviour. This core idea is theoretically motivated from sound strategies for exploration in finite-horizon RL, but as the paper addresses the discounted problem setting with deep neural networks the soundness is traded-in for computational tractability — which is a fine choice.

But, currently the choices are presented in a confusing way, and the actual contributions of the algorithm are unclear: most importantly, is it a Frequentist approach to exploration or Bayesian?

- under the Frequentist approach setting, utilizing e-greedy seems justifiable just based on the reasoning of this is “the widely accepted practice in the field”.
- under the Bayesian viewpoint, which is the crux of the architecture used here (Bootstrap DQN), the attempted theoretical connections in the paper (Theorem 1) and the practical algorithm proposed (based on the ideas of Optimistic LSVI), do not provide a clear picture.

To show theoretical soundness the algorithm is anchored to a Bayesian architecture and theoretical uncertainty connection, but for practical performance purposes the paper leverages reasoning from Frequentist Deep RL methods. Maybe this is a step in the right direction, and the extensive empirical results do seem to suggest it is effective, but the presentation is unclear. From the current draft:
- “OEB3 relies on the posterior of Q-functions” — Bayesian
- “UBE uses posterior sampling for exploration, whereas OEB3 uses optimism for exploration” — Frequentist

Therefore, this can be improved and presented more clearly to communicate the idea.


review_title: Incremental paper. Needs a clearer presentation and a more thorough empirical analysis.

final_score: rating: 6: Marginally above acceptance threshold
review_content: The authors of the submission "Optimistic Exploration with Backward Bootstrapped Bonus for Deep Reinforcement Learning" draw inspiration from the theoretical reinforcement learning literature to propose an optimism based bonus for deep q learning. The idea is to compute an optimistic bonus based on a Q function ensemble, and use this to augment the present reward signal and the future return estimator (future optimism) to yield an algorithmic approach that reduces to LSVI in the case of linear MDPs (or at least reduces to something akin to LSVI in that case). 

The authors then introduce a generic procedure (BEBU) that can be plugged into a variety of Q learning algorithms to produce an "optimistic" bootstrapped backward episodic update. Crucially the order of the updates matters, since the uncertainty bonuses should be propagated backwards in time. This is a very nice poin: the uncertainty propagation should be done backwards. 

The authors are right in my opinion to claim their work represents a welcome addition to the emerging literature that proposes the use of uncertainty bonuses around the value function as opposed to myopic uncertainty bonuses only at the immediate reward level. There exist other recent works that introduce similar ideas (bringing in bonuses for the future uncertainty as opposed to solely penalizing immediate  ) are some missing citations in the related work section, most notably "On optimism in model based reinforcement learning" (using value optimism in model based RL and deep RL), "Efficient model based RL through optimistic policy search and planning"(optimism and GPs in model based RL), and also SUNRISE which looks awfully related to BEBU-UCB. 

The experimental results of this work are strong. It is nevertheless unclear how much of these results are the consequence of accessibility to massive computing resources. I would like to see the paper positioned more faithfully within the relevant optimism-at-value-level literature, even though these works are model based in nature. It would also be very useful to have algorithm boxes for the different methods or method templates that the authors describe in the text. It is hard to follow what they intended to say or at least a table listing succinctly in a reader friendly way what the differences are between the different instantiations of the approach (OEB3, BEBU, BEBU-UCB, etc ...). 
review_title: Combining optimism with Deep RL

final_score: rating: 7: Good paper, accept
review_content: The paper proposes a UCB-based optimistic exploration method for DRL, called Optimistic Exploration algorithm with Backward Bootstrapped Bonus (OEB3). The algorithm builds on the idea of optimistic exploration developed in the theoretical optimistic LSVI algorithm for linear MDP. In optimistic LSVI, the optimistic Q-value is backward updated for each episode with an UCB bonus at each step. OEB3 extends this backward update of UCB bonus to DRL by estimating the UCB bonus using bootstrapped Q-learning. OEB3 learns an ensemble of bootstrapped Q-values and estimates the UCB bonus as the variance of the Q-values. Another important part of OEB3 is to adapt episodic backward update to bootstrapped Q-learning. This is done by procedure called Bootstrapped Episodic Backward Update (BEBU) which extends previous episodic update idea to the ensemble of bootstrapped Q-values. 

Experiments have be done in Mnist Maze and Atrari games comparing OEB3 with previous exploration methods and some OEB3 variants. Table 2 nicely summarizes the algorithm design difference of related algorithms and highlight the two important components of backward update and UCB bonus in OEB3, and the improvements clearly helps OEB3 to outperforms similar exploration approaches. However, it may be miss-leading to say that OEB3 outperforms all existing bonus-based methods since it actually performs worse than some prior methods in Montezuma’s Revenge.

I think this is a nice work given its connection to theory and the nice empirical performance, but I think the following questions about steps in the OEB3 algorithm should be answered.

- The paper claims to use bootstrapped Q-learning, but in the algorithm description, at each time only one episode E is sampled for all head. This is different from the original bootstrapped Q-learning design where different heads are learned using different samples with bootstrap. Are there some steps missing in the algorithm description or no bootstrapped samples are used? If all heads are learned from the same sample, does the diversity among different heads only depend on their initialization?

- In training, the action is selected by randomly picking a head, i.e. the Thompson sampling approach. However, in evaluation the action seems to be selected by majority vote. Is there a reason for this difference in training and evaluation? Does random sampling help exploration in training?

- In algorithm description, epsilon-greedy is actually used in OEB3 during training. The use of epsilon-greedy is different from other exploration methods which guide exploration by bonus or other randomness. Why does OEB3 need epsilon-greedy given its exploration bonus design? In experiments, do other baselines also use epsilon-greedy?




review_title: An optimistic exploration method for DRL using backward bootstrapped bonus which outperforms previous exploration approaches in Mnist Maze and Atrari games. 

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper focuses on deep reinforcement learning and proposes a practical exploration algorithm called Optimistic Exploration algorithm with Backward Bootstrapped Bonus. Based on the Optimistic LSVI algorithm, the authors propose a new optimistic exploration bonus for general cases, similar to the optimistic exploration bonus in the LSVI algorithm under the linear MDP setting. Experiment results show that the QWR algorithm has better performance than previous algorithms.
This paper is well-written and easy to follow.  The main contributions are delivered:  Proposed optimistic exploration bonus for general cases; New deep reinforcement learning algorithm. However, I still have some concerns about this paper.
First, the actor-value function Q is the expected cumulative reward with discounted factor \gamma. However, it is usually set 0<\gamma<1 for infinite-horizon MDP and set \gamma=1 for episodic MDP or finite-horizon MDP. Besides, the LSVI algorithm also set \gamma=1, and it seems strange that there is a discounted factor \gamma in the OEB3 algorithm.
Second, in the LSVI algorithm, the agent chooses action by the totally greedy policy with the state-actor value function. In the OEB3 algorithm, the agent chooses action by the \epsilon-greedy policy. Even the optimistic exploration bonus in the OEB3 algorithm is the same as the LSVI algorithm under the linear MDP setting, theoretic proof of LSVI may not support the OEB3 algorithm.
Finally, in the experiment, it seems that the action space is relatively small. It is better to do more experiments with a broader action set and show the OEB3 algorithm's performance in those experiments.
review_title: Official Blind Review #3

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper studies optimistic exploration for deep reinforcement learning. They propose an algorithm called OEB3, which utilizes the disagreement of bootstrapping Q-functions as the confidence bonus to guide exploration. They show that their confidence bonus matches the confidence bonus of optimistic LSVI in linear setting. After that, they evaluate their algorithm on plenty of benchmark problems including Mnist maze and 49 Atari games. Their algorithm outperforms other SOTA exploration approaches.

Pros:

- The optimistic exploration problem is very important for the RL community. From the theoretical perspective, the classical $\epsilon$-greedy exploration method has been shown to be inefficient, and UCB-based algorithms are shown to be sample efficient with regret guarantee. However, how to apply these theoretical insights into practical algorithms is still an open problem. The paper proposes a method that uses bootstrapping to construct confidence bonus, and connects the theoretical findings to practical algorithms.

- The experimental results on 49 Atari games are rich enough to show the improvement of the algorithm, with visualization results and ablation studies. 

Other comments:

- The connection with optimistic LSVI is interesting but not satisfying. Theorem 2 assumes that $\epsilon$ follows the standard Gaussian distribution. Why does this assumption hold? A more natural and reasonable assumption is that the rewards and transitions are sampled from a Gaussian distribution. Can theorem 2 still hold under such assumptions?


-------Post Rebuttal---------


Thanks for the feedback from the authors. After the rebuttal and discussion period, I believe that the contribution of the paper are mainly empirical. The Theorems (Theorem 1 and 2) are proposed to show the intuition of the bootstrapping and backward-update methods, and to connect the algorithm with recent theoretical results. During the discussion, there are mainly three concerns about the theorems among reviewers. 

- Firstly, the algorithm uses eps-greedy to help exploration, which is theoretically unclear. 
- Secondly, the theorems focus on episodic setting, while the algorithm is designed for discounted setting. 
- Lastly, it is unclear whether the algorithm is a frequentest approach or Bayesian. 

I believe that the former two concerns can be addressed in the following way, and don't weaken the contribution of the paper.
- From the theoretical perspective, the feedback from the authors does tackle this problem. The eps-greedy will only add an epsilon-term to the final regret. I am eager to see the discussion in the final version. From the experimental view, the authors also claim that all the algorithms in the experiments use eps-greedy to help exploration. In that case, the improved performance of their algorithms are mainly due to their bootstrapping and backward-update methods, instead of eps-greedy trick. Besides, I think applying several widely-used tricks (such as eps-greedy) to the algorithm is acceptable, which makes the results comparable to other methods that also use the tricks. 
- To the best of my knowledge, there is currently no paper studying linear MDP in the discounted setting from the theoretical perspective. I think this is the reason why this paper studies the connection of the theorems in episodic setting. Meanwhile, it is hard to conduct experiments in episodic setting (In that case, the algorithm needs to learn the value function of all the possible horizon). Moreover, we can reduce an MDP with discounted rewards to episodic MDP by setting the effective horizon $H = \frac{1}{1-\gamma}$. This means that the theorem for episodic MDP can hold in the discounted setting with slight modification. Maybe such discussion should be added to the paper.

However, for the last concern, I am still puzzled whether the algorithm is a frequentest approach or Bayesian, as there are many unclear statements.

Overall, I believe the main contribution of the paper is from the empirical perspective. The theorem is intended to show the intuition of the algorithm and to connect the approach to the recent theoretical results. The experimental results look nice in general. I am a little disappointed that the authors missed the comparison with two related literatures in the initial version. I agree with R5 that these results may be done under a time-crunch. As a result, I change my score to 6, and I hope the above problems can be addressed in the next version.

review_title: An interesting paper which applies optimism principle to practical algorithms

Meta-review: This paper represents a practical extension of sound theoretical uncertainty propagation ideas for exploration in deepRL. All the reviewers agreed this was a promising direction and the empirical results strong. It was nice to see additional qualitative analysis of the proposed method, beyond the typical "my number is bigger than yours" type of claims. The discussion was extensive; reviewers with specific subject matter expertise provided high quality and detailed reviews.  Several reviewers were in favour of the paper, but none were willing to champion it as a clear accept. 

Indeed the discussion highlighted important concerns with the paper. Several reviewers found the paper to overclaim: most importantly the paper suggests strong theoretical underpinnings of the method without clear evidence. Some found the text very imprecise. The reviewers were torn if such changes represented wording changes or major rewrites. The original submission missed two key pieces of work which were added during the rebuttal phase---UBE was added by including the scores from the literature, and the other (Bayesian-DQN) was only added to the discussion. Good on the authors for doing so, though ideally both would be implemented again. 

The AC's own reading of the paper highlighted a few other concerns. The writing needs work. In addition, the majority of improvement in overall performance appears to be due to very large improvements in a handful of games (e.g. Atlantis, Krull) and significant losses in performance in other games. This was not discussed at all. More surprisingly these games with huge performance gains were not used in the qualitative visualizations of the utility of the bonus found in the paper. The game breakout was used for analysis instead. Oddly the proposed method actually does worse or the same as SOTA methods (e.g., Adaptive EBU, Boot-DQN, UBE) in breakout.  This is difficult to get to the bottom of because: (a) the per-game score tables in the appendix don't include the scores achieved by important baselines (e.g., Boot-DQN, EBU, Adapt EBU), (b) different setups are used across the relevant literature (Boot-Q & UBE papers use 200m frames, EBU paper uses 10m frames, and this paper uses 20m), (c) the per-game analysis in the appendix focuses on comparing methods proposed in the paper under review. That might all make sense, but it is left to the reader to figure out and I never got to the bottom of it all (table 3 of the Lee et al contains some of the relevant comparison data). Such missing details and lack of analysis are particularly important when the paper boldly claims state of the art performance improvement.

All put together a clear picture emerges: the paper needs polishing, is unclear in places, over-claiming, and missing important analysis and explanations---in regards to both the theory and the experiments. The reviews are extensive and have provided many insights in how to improve the paper. 
Decision: Reject