Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper introduced NoveId, a new exploration technique that can extend any exploration bonus. The new bonus is computed by looking at the difference in novelty between a new state and the previous state. The authors argue that this bonus does not suffer from detachement and improves exploration in many complex environments. These claims are substantiated by experiments on Mini Grid, the Arcade learning environment and NetHack that shows that NoveId outperforms existing exploration methods.
main_review: Overall I enjoyed this paper, I think that the NoveID bonus is a good idea to encourage the agent towards regions with large intrinsic reward variance. The idea is simple and builds on existing techniques nevertheless it was properly evaluated through a series  of experiments.
Exploration remains a big challenge in reinforcement learning and papers like this one making progress in this area are important.

While I agree that NoveID improves exploration it is not clear to me if it actually fixes detachement. In particular I don't agree with the explanation provided in Figure 1. I am not sure that RND would forget that it visited the upper right corner and increase the reward in 3. after decreasing it in 2. My guess would be that instead in 3 the whole right side would be light blue. In this case the agent might indeed get stuck if it is in the middle of this region however I believe the same thing would happen with NoveID. NoveID will do better here because the agent will receive a higher reward signal if it manages to reach the exploration frontier; however NoveID will not provide a better signal than RND in regions already explored.

I'm also not sure I agree with the asymptotic inconsistency mentioned in section 3.2. Once the prediction network has gathered enough data about the environment is should be able to match the embedding network, in this case I don't see why a state in representation would happen. It is also not clear why NoveID would asymptotically consistent, can the authors provide more insight here?
 I also really enjoyed the different visualizations to help understand how NoveId behaves differently from existing algorithms. 

Regarding experiments I found the MiniGrid experiments in section 4.1 and 4.2 particularly interesting and they demonstrate well the benefits of NoveID. Though in section 4.3 I found it hard to draw any statistically significant conclusion from plots given that there are only 4 seeds. Given the lower computation resources needed to run MiniGrid vs other benchmarks like Atari it would have been nice to see more seeds here.

It is also hard to draw any conclusion from Atari experiments as only evaluating hard exploration games is not enough to evaluate an exploration algorithm (see [1]). Evaluating NoveID on more games is necessary to properly evaluate its performance on Atari games and see if the increased performance on hard exploration games does not lead to a decrease performance on easier exploration games. It would also be helpful to add epsilon-greedy as a baseline and mention whether or not sticky actions were used.

In the end I still lean towards acceptance given the results on MiniGrid and NetHack however the paper would stronger with a better evaluation on Atari games.

L55: "in NoveID, there is almost no hyperparameters", I don't think this is a fair statement given that NoveID adds a new hyperparameter on top of the novelty algorithm it is using.

**Clarity**

Overall I found the paper well written and easy to follow. The authors made an effort to provide many graphics to back up their claim and help the reader.


**Small typos:**
 
L47: Atari games is
L52: MonteZuma's Revenge instead of Montezum's Revenge
L64: What is t?
L112: Is it Eq 4 or 2? If it is 4 it is a bit confusing as this equation is only referenced many pages later.

[1] On bonus-based exploration methods in the arcade learning environment, ICLR 2020


limitations_and_societal_impact: The authors have adequately addressed the limitations and potential negative societal impact of their work
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper proposes a novel exploration bonus for reinforcement learning, NovelD, which consists in adding a weighted clipped difference of the novelty of two consecutive states to the reward. The paper argues that this provides a breadth-first kind of exploration, in contrast to pure novelty based methods that would provide a more depth-first exploration. The paper provides extensive experimental validations, on a variety of environments. 
main_review: Overall, I have very few complaints about the paper. The idea provided by the paper is novel, interesting, and the presentation is clear. 

My main comment is that the paper introduces two distinct contributions to exploration: the exploration bonus, based on a difference of novelty of subsequent states, and Episodic Restriction on Intrinsic Reward, which only limits intrinsic rewards to state that were only visited once in an episode. While the exploration bonus is very general and can be used in most RL problems, ERIR is arguably more ad-hoc: it requires discrete or hashable states, potentially with a well-suited hash. The authors provide an ablation of ERIR on one of the environments, and show that NovelD with ERIR outperforms RND with ERIR. However, I feel that the relative weighting of the two contributions could be better explicited, by providing:
  - Results for NovelD - ERIR on the MiniGrid environment.
  - Results for both NovelD - ERIR and RND + ERIR on Nethack and Atari.

In addition to this comment I have a few minor comments:
- There are a few english mistakes, including, but not restricted to:
  l5. in a depth-first manner
  l8. it won't suffer -> optimistic ... won't suffer
  l9-10. in a breadth-first manner
  l29. they fail
  l30. we observe that
  l32. these methods can get trapped
  l34. the detachment
  l37. approximately
  l42. compared
  l51. by a significant
  l55. is a one-stage
  l57. asymptotically consistent
  l58. are not
  l72. has not
- There is a small notational inconsistency: alpha is used twice, once for the intrinsic reward weighting, once for the weighting between the current and next state novelty.
limitations_and_societal_impact: Yes, to the best of my understanding.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper presents a simple exploration criterion NovelD. The basic idea is to use the difference of the novelties between the next state and the current state as an intrinsic reward, which is the "boundary" of the explored and unexplored regions. This idea is implemented with a max operation to avoid negative rewards, a binary indicator that only rewards the state visited for the first time, and RDN as the novelty measure. The experiments are conducted on MiniGrid, NetHack, and some hard exploration environments in Atari.
main_review: Strengths:
1. The idea of exploration "boundary" is interesting. The intrinsic reward is simple and intuitive. 
2. The results are strong. It solves all the tasks in MiniGrid in a short time. It significantly outperforms the baselines. In addition, it also shows advantages in NetHack and some hard exploration problems in Atari.
3. The paper is clearly written.

Weaknesses:
1. The paper mentions SOTA many times. However, some SOTA algorithms in MiniGrid are not discussed/compared. [AGAC](https://openreview.net/forum?id=_mQp5cr_iNy) seem to also be able to solve many tasks in MiniGrid. In particular, AGAC is shown to be able to solve KeyCorridorS8R3, which is more challenging and is not included in this paper. [RAPID](https://openreview.net/forum?id=MtEE0CktZht) can also solve many MiniGrid environments efficiently. In particular, RAPID seems to be more sample efficient than NovelD on some MultiRoom environments (such as MultiRoom-N7-S8) based on the reported results. It is unclear why these two methods are not compared in MiniGrid tasks and are not even discussed.
2. The authors noted that "NovelD puts a more aggressive restriction: the agent is only rewarded when it visits the state for the first time in an episode." It is unclear why the authors apply this aggressive restriction. How will it perform if using the scaling method in RIDE?
3. The authors noted "Asymptotic Inconsistency" is one of the advantages of NovelD. However, the authors ignore a simple strategy. One could simply anneal the coefficient of the intrinsic to zero in the training process. In this way, the policy could still maximize the extrinsic reward eventually.
4. For Atari games, the NovelD uses a simple pixel-based hash table for counting. The pixel-based hash table seems to be not well-suited for image input. A possible reason it works is that the Atari environments are not procedurally generated so that we can encounter the same states in different episodes. It is unclear how this method can be applied to procedurally generated settings, such as procgen.

Questions:
1. The authors mention "two-stage" and "one-stage" approaches. I can not find an explanation for this.
2. In procudually-generated environments, both $s_t$ and $s_{t+1}$ could be very novel if the observation space is large. MiniGrid has a very simple observation space. Can NovelD handle procedurally-generated image input, such as procgen?

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper introduces a simple but effective improvement for novelty-based exploration methods: using regulated novelty difference of consecutive states in a trajectory. Extensive experiments on MiniGrid, Atari and NetHack demonstrate the effectiveness of the proposed approach.
main_review: Strengths:
* The proposed modification is simple but effective, significantly outperforming prior works on MiniGrid benchmark.
* The experiments are extensive and solid.
* The writing is clear and easy to follow.

Comments:
* In Section 3.1, NovelD is described as a general meta-criterion that can be applied on top of any novelty measure. However, the authors only use RND in experiments. It would be better to test other novelty measures.
* In Section 3.2, the authors mention that one of the advantages of NovelD is asymptotic consistency. But it is unclear whether this is a severe issue. How seriously it would affect exploration if an approach is asymptotic inconsistent? The authors could add more discussions on this.
* Some implementation details are missing. The authors say they use PPO in Section 4. However, the hyper-parameters mentioned in Appendix are more like for IMPALA. Did the authors implement NovelD with PPO and other baselines with IMPALA? Is the policy a feed-forward one or recurrent one? For PPO, hyper-parameters like num_epoch, num_minibatch and GAE lambda are missing. I suggest the authors doing a through check on this and include missing implementation details.
* Some descriptions in Section 4.3 (NovelD under Different Representations) are a little bit confusing. Why "replace f(s) with f'(s) periodically"? I do not quite understand how training with different representations is done. Please give some clarifications.
* For the main results in Figure 4, it would be better to include comparisons to recent SOTAs (RAPID [1] and AGAC [2]).

Minor points (I do not factor these into my assessment):

* The authors should carefully go through the paper and fix some typos and errors:
  * Extra right parenthesis in Line 111.
  * Line 196: "Clipping n NovelD" -> "Clipping in NovelD"?
  * Line 225: Figure 11 does not have 4th figure.
* Please, use up-to-date reference instead of arXiv version, e.g., PC-PG, Agent 57, NGU. Please go over all of them.

Overall, I think the method is simple and works well as demonstrated by extensive experiments. However, the concerns need to be addressed before acceptance.

[1] Daochen Zha, Wenye Ma, Lei Yuan, Xia Hu, and Ji Liu. Rank the episodes: A simple approach for exploration in procedurally-generated environments. In International Conference on Learning Representations, 2021.

[2] Yannis Flet-Berliac, Johan Ferret, Olivier Pietquin, Philippe Preux, and Matthieu Geist. Adversarially guided actor-critic. In International Conference on Learning Representations, 2021.
limitations_and_societal_impact: Yes
review_title: null

Meta-review: After reading the reviews, the authors response and the discussions, I suggest to accept the paper. All reviewers agree that the paper presents an original idea in a clear way. Minor questions and concerns have been answered during the rebuttal by the authors. Overall the idea is simple but yet effective on a spectrum of different tasks. In addition, the method is compared with state of the art baselines. To improve the paper, experiments on more challenging environments such as 3D visual game could be considered.
Decision: Accept (Poster)