Unlocking the Power of Representations in Long-term Novelty-based Exploration

The presented algorithm demonstrates impressive performance in well-established hard-exploration benchmarks. However, it lacks evaluation in an open-ended (yet equally challenging in terms of exploration) environment, such as Minecraft, which would combine the complexities of long-horizon tasks from Atari with rich observations from environments like DM-Hard-8, as utilized in the paper.

Minecraft is definitely an interesting environment for exploration that combines complex long-horizon tasks and rich observation environments. However, given the complexity of it, the current SOTA approaches combine additional ingredients to exploration to make progress. For example, to make exploration bonuses effective they are combined with video pre-training (https://openai.com/research/vpt, https://minerl.io/) or shaped intrinsic rewards to encourage predetermined policies (e.g. https://openreview.net/pdf?id=ZUXy6d49JNJ). In https://arxiv.org/pdf/2303.16563.pdf a naive state visitation count is implemented in addition to more domain-specific similarity-based rewards based on pre-trained large language models.

In our paper, we propose a novelty-based approach for exploration that does not take into account any domain-specific knowledge about the environment (e.g.hand-engineered action spaces, skills needed for complex tasks, video pretraining). Therefore, we focus on testing its performance in environments where other competing fully-intrinsic approaches can make progress. In Minecraft, a pure intrinsically motivated agent, with an intrinsic reward that does not take into account specific skills to mimic, would likely take a very long time to discover complex skills (e.g. getting a diamond pickaxe), and it would still be necessary to benchmark the performance of the intrinsic exploration mechanism on simpler tasks.

We would expect that our technique can improve the performance of existing techniques on long-horizon tasks on Minecraft when used as a replacement for naive novelty-based rewards, when including some bias towards useful skills or imitation based pretraining and believe that it is an important direction for future research to investigate how to reduce the need for prior knowledge in discovering such complex skills.

The computational resource requirements for training RECODE remain unclear. The paper indicates a substantial number of environment interactions, around 7.5e8 steps, for various environments, comparable to previous studies. However, essential details such as memory usage, CPU requirements, and GPU memory are not provided. This lack of information poses a significant concern, as it could either limit the framework's practical applicability or potentially underscore its uniqueness as a noteworthy contribution.

We updated the submission. For each of the experiments we now report in App. F total resources used to generate one run (i.e. one seed) across the whole distributed agent (including multiple actors, learner and RECODE memory mechanism, see App. H for more details).

One seed for an Atari experiment (MEME-RECODE-AP MEME-NGU-AP) took 24h to execute using multiple servers with a total of 64 CPUs, 1TB RAM, and 5 TPUv4. One seed for a DM-HARD-8 experiment (both MEME-RECODE-CASM and MEME-NGU-CASM) took 90h to execute using multiple servers with a total of 512 CPUs, 1TB RAM, and 5 TPUv4.

While the authors assert the robustness of the presented algorithm to different RL algorithms for policy learning, the RL training solely relies on MEME, a powerful RL algorithm with substantial learning capacity. While this choice appears suitable, the paper lacks an analysis showcasing the performance of more commonly used algorithms like PPO or DQN when coupled with RECODE. Including such comparative results would significantly support the paper's claims regarding RECODE's versatility in enhancing long-horizon exploration across various RL algorithms. VMPO is also used for the DM-Hard-8 suite, but I believe this doesn't provide evidence that RECODE would still work well with more popular RL algorithms.

Indeed, the primary piece of supporting evidence of this claim is the strong performance obtained by VMPO-RECODE in the multitask setting without any additional tuning. We agree that the evidence would be much stronger if a wider variety of popular algorithms were tested. Since implementing and validating performance of any additional algorithms used for such an analysis would require a significant engineering effort, it is not feasible to obtain these results prior to the end of the rebuttal period, but we will look into possibilities to include another off-the-shelf RL agent in an appendix for the camera-ready version of the paper.

As we describe in the general response, our main intention on Atari is to demonstrate that RECODE is in-line with the current state-state-of-the-art achieved by MEME-NGU, since performance on most games already far exceeds the human benchmark and has limited room for improvement. To that end we point out that mean and median Human Normalized Score (HNS) are higher for RECODE, as is the mean capped HNS. In addition RECODE achieves better or equal mean final performance and AUC in 6/8 games (vs 3/8 and 2/8 respectively).

That being said, ​​the difference under these metrics for most games is small, and only statistically significant (to 5% significance level) in a few cases. Specifically, when using a one-sided Mann-Whitney U test for difference in mean across seeds we observe the following: RECODE > NGU in Pitfall (p=0.0043) and Q*Bert (p=0.0465) for final performance and in Solaris (p=0.0011) and Seaquest (p=0.0325) for AUC. Conversely, the only case where NGU > RECODE is final performance for Hero (p=0.0465). For aggregate statistics we can compute p-values via a bootstrap estimate and find that RECODE > NGU for Mean HNS (p=0.0185) and Mean Capped HNS (p=0.0419). We will modify the wording in the main text to avoid possible misinterpretations and include an appendix summarizing all of these metrics with appropriate confidence intervals and hypothesis tests (see Table 6 in the revised appendix).

Is CASM only beneficial over one-step action prediction (AP) when there is high aliasing due to partial observability (like DM-HARD-8)? Are results for MEME-RECODE/NGU-CASM available for the Atari environments? I may have missed them in the appendix.

Results for MEME-RECODE/NGU-CASM on Atari were not included in the initial submission but we have started running these experiments and will include them in the camera-ready version of the paper. While we do not yet have results for all seeds and games, preliminary results suggest that performance is very similar to the AP embeddings on Atari. Indeed, we would suspect that the primary benefit of CASM comes from application to domains with a high degree of partial observability, and our early results would seem to support that hypothesis.

In Appendix L, results are presented for RND on AP (one-step action prediction), where a random net is applied to features extracted by AP. As the random network is typically seen as a feature extractor itself, wouldn’t it be more natural to obtain RND-like intrinsic rewards from a predictor of the AP feature of a state (rather than a random embedding of the AP embedding)? Similarly, it would be helpful to evaluate if RECODE is better than NGU when NGU uses RND on AP (or an RND-like bonus with AP features directly) for its global bonus.

Assuming the AP embedding network is already trained, it could make sense to apply a prediction based reward leveraging it directly as the reviewer suggests. However for the setting we focus on (where the AP embedding network is concurrently trained with the RL network) it seems likely that such a predictor network would just track the AP embedding network closely and thus may not confer any benefit over just using the AP loss itself to construct an intrinsic reward. A high AP loss may be the result of states being novel, but will also happen if many actions lead to the same state transition; which might have the undesirable effect of incentivizing the agent to seek out uncontrollable states. A good example of this occurs in Pitfall; where after jumping, no action will alter the character’s trajectory until the jump has landed.

Additionally, one of the intuitions behind RND is that the random network should not generalize across states, otherwise states which are actually novel but have similar features to frequently observed states may have low reward. Applying a random nonlinear transformation on top of the AP embedding features is intended to reduce this type of inappropriate generalization, and this very feature explains why AP-on-RND performs poorly when the AP embedding network is concurrently trained.

Since we observe that RND-on-AP only helps when using a pretrained AP embedding network, it may make sense to directly compare RECODE and NGU with RND-on-AP in this specific setting, and we can commit to include this experiment in the camera-ready version of the paper.

Note that when compared to NGU, RECODE:

• Removes the complexity of having to rely on a parametric novelty detector (RND) for long-term memory, which involved hard to tune hyperparameters and design choices including selecting a network architecture and network optimizer, and how to combine the RND reward and episodic reward
• Inherits the following hyperparameters from the episodic component of NGU: atoms removal, reward constant, decay rate, # nearest neighbors, and relative tolerance (referred to as cluster distance in that work)
• Adds hyperparameters for discount, insertion probability, memory update and memory size

Taking this into consideration the slight increase in complexity of the memory mechanism is more than offset by the removal of RND, and overall we consider RECODE a less complex novelty detection mechanism (both conceptually and in ease of tuning) than NGU.

Ensuring that the reader can clearly understand which of these new hyperparameters are important to tune and when remains important. We have added some general guidelines in Section 3 of the paper, as well as an ablation over memory size and insertion probability in Appendix L.1, Fig. 20.

Notice also that in general most of RECODE's design space (memory upkeep, representation learning, forgetting) is shared across the family of non-parametric visitation counts estimators (that goes beyond EMM/NGU). More in detail, comparing RECODE to its closest alternative NGU we have that:

• Memory size: NGU side-steps tuning a memory size by implicitly setting the EMM size to be the maximum length of an episode. Note that this is not possible in many cases (long episodes cannot be all stored in RAM), and makes it impossible to preserve long-term memory. To cover these limitations, NGU introduces extra complexity with a completely separate long-term novelty detector (RND). Therefore, both RECODE and NGU are more complex than vanilla EMM: RECODE through the memory management methods with their hyperparameters; and NGU through RND with its hyperparameters that need to be tuned (network architecture, optimizer, etc…). Overall we find that RECODE is robust when choosing its new hyperparameters (see updated ablations after rebuttal). In contrast we found that RND is quite difficult to tune and has a complex interaction with the episodic reward and representation learning which makes it more difficult to reason about. Removing RND makes it easier to tune the overall novelty mechanism.
• Heuristics to update/add/remove atoms of memory: this is an inherent feature of all finite-size memories, since choosing a removal strategy is always necessary when dealing with finite memory and potentially infinite interactions. NGU’s choice in this regard seems simple (add every atom encountered and remove them all at the end of the episode), but it is not applicable to complex real-world scenarios (e.g. if the episode length is larger than what is computationally feasible to store in memory we must remove atoms before the end of an episode). Overall, NGU can avoid memory management heuristics because all the heuristics are pushed into the RND module, while RECODE must explicitly address them. Compared to existing novelty estimation methods for RL our discounting and cluster merging approaches are more novel, but they are still rooted in and inspired by a long tradition of non-stationary clustering methods such as DP-Means (see App. D). Similarly, our particular design choice for removal was motivated by empirical observations in toy experiments (see App. D), but as stated, it is ultimately an arbitrary choice. Our ablation against alternative removal strategies demonstrated that RECODE is robust to this choice.
• Discounting: $\gamma$ is one of the two important hyperparameters that we recommend should be tuned in the guidelines we have added in the latest version. We give more insight on how it impacts RECODE’s performance in Appendix D including illustrative toy experiments, theoretical connections to DP-Means and ablations on the same complex environments used in the main paper. In particular, we show that the usefulness and impact of $\gamma$ strongly depends on the non-stationarity of the observations, which in turns depend on both the evolution of the observation representation and the diversity of the data collected by the agent.
• Representation learning method (i.e. embedding) and the associated distance kernel were also important design choices in prior non-parametric methods. The adaptive kernel we use is also the same as that used in NGU, except for the modification to sum over all atoms within an epsilon ball of the query embedding rather than over a fixed number of nearest neighbours. This complication was unnecessary in NGU because every atom represented a count of 1 and thus did not suffer from the undesirable behaviour that adding an embedding could decrease the count for that embedding when using the latter approach (see discussion under Eq. 3)

We would like to thank the reviewer for the very detailed feedback. We hope our replies adequately address your concerns and give you the confidence to raise your score

Q. In many procedurally generated environments [...]

This is an important question that we have indeed given some thought to. The answer to whether or not hard resets could be preferable depends on both the nature and distribution of procedurally generated elements, as well as the choice of representation used in conjunction with RECODE.

In particular if we consider the example the reviewer mentions (known object in a new context) a “good” learned representation will be capable of capturing this novel context/combination as a novel embedding that will trigger high reward in RECODE. Empirically we note that RECODE-CASM seems to achieve this desirable behaviour, and performs well in DM-HARD-8 which already contains the following procedurally generated elements: initial position and orientation of the agent; shapes, colors, textures, and positions of objects; wall and floor colors and textures, and sensor colors (which can only be activated by an object of the matching color). Following again from the example, the agent learns a representation where a blue ball will mean different things in different contexts and correctly assign novelty. It is also plausible that the action-prediction objective aliases together some of the procedural variability between episodes, though we have not tested this specifically.

On the other hand we would expect that more complex procedurally generated elements such as level geometry and size may be more challenging for generalization across episode boundaries, particularly when the degree of variability is very large. While it would be possible to combine just the episodic memory component of NGU, with RECODE used in place of RND for long-term memory, this solution is not ideal due to the added complexity of implementation and tuning. An simpler approach could be to investigate how to construct representations that are suitable for generalization across episode boundaries in this setting. For example, it is plausible that higher-level semantic representations, or behavior representations can still generalize well in this setting, and we believe these could be promising directions for future research.

We thank the referee for the proposed references, which we will add in the related works section together with the other connections to previous works on novelty-based intrinsic motivation already present. Looking more closely at each of the suggestions:

[1] MIMEx uses the loss of a masked transformer as an intrinsic reward signal. This masked transformer acts on a latent space, which is built on top of an initial fully-connected embedding layer applied on the input. The masked transformer thus estimates novelty according to the prediction error in a latent space. Our approach disentangles the creation of a meaningful embedding and the intrinsic reward signal. In particular, we use a masked transformer (CASM in our paper) to build a robust latent space. Indeed, it is well-known in literature that action-prediction based embeddings are usually more robust to noise, as they tend to ignore uncontrollable factors in the input. Being the output of a neural network, in MIMEx the reward signal will change slowly and might not capture episodic novelty, while also being vulnerable to catastrophic forgetting. On the other hand, we don’t use the masked transformer loss as an intrinsic reward signal, but we use the RECODE component. As described in the introduction of the paper, this allows us to extend the advantages of short-term intrinsic reward techniques (which previously were essentially episodic) to longer horizons, while avoiding slow adaptation and catastrophic forgetting issues that are often connected to the use of a neural network for the reward signal.

We further note that MIMEx uses a sequence auto-encoding objective operating only on states, whereas CASM instead predicts actions, while operating on both states and actions; with the masking strategy being designed so that exactly one of the action and state are observed at any given timestep, so as to better preserve the requisite information needed for the prediction task.

[4] develops the idea of using general value functions to take into account the prediction error on more than a single step. In this way, they couple the prediction task to the current policy, giving it extra incentive for explorative behaviour. This technique is complementary to our novelty-estimation technique (RECODE), as one could also build a value function with it to explore over longer horizons. In addition, their state representation is based on a random network, which might suffer from the presence of noisy observations, and thus is expected to have limited applicability when environments are highly stochastic or contain uncontrollable features.

[2,3] Successor states have been used as an approximation of state visitation count, while successor uncertainties can provide an intrinsic reward signal based on prediction uncertainty. However, those works estimate visitation counts directly in the state space. We emphasize the importance of building an insightful representation in the case of complex environments, where the state space can be extremely large and possibly contain many irrelevant features, thus requiring some type of aggregation or filtering mechanism. In those cases, a good representation is needed to filter out noise and environmental stochasticity. In particular, an efficient exploration strategy should be biased towards controllable novel states, and this is why we focus on action-prediction representations. The proposed multi-step action-prediction (CASM) proved to provide a more robust representation with respect to the competing representation learning techniques. Successor features (Successor Features for Transfer in Reinforcement Learning, arXiv:1606.05312) introduces in the embedding space the same approach of successor states as approximation of novelty.

We note that [1] & [4] evaluate on a different set of tasks so direct comparison is difficult. [2] & [3], and the works extending successor states to successor features, do have some overlap with the Atari games we evaluate, but underperform compared to methods such as RND, NGU, or pseudo-count based rewards on both Montezuma's Revenge or Pitfall which are generally regarded as the most challenging environments for exploration in the Atari57 task suite.

While all reviewers agree that the our main claims (SOTA performance on the harder DM-HARD-8 task and novel capabilities in "Pitfall!"), they also have some questions on the Atari experiments. Our main intention on Atari is to demonstrate that RECODE is in-line with the current state-state-of-the-art achieved by MEME-NGU, since performance on most games already far exceeds the human benchmark and has limited room for improvement. To that end we point out that mean and median Human Normalized Score (HNS) are higher for RECODE, as is the mean capped HNS. In addition RECODE achieves better or equal mean final performance and AUC in 6/8 games (vs 3/8 and 2/8 respectively).

That being said, ​​the difference under these metrics for most games is small, and only statistically significant (to 5% significance level) in a few cases. Specifically, when using a one-sided Mann-Whitney U test for difference in mean across seeds we observe the following: RECODE > NGU in Pitfall (p=0.0043) and Q*Bert (p=0.0465) for final performance and in Solaris (p=0.0011) and Seaquest (p=0.0325) for AUC. Conversely, the only case where NGU > RECODE is final performance for Hero (p=0.0465). For aggregate statistics we can compute p-values via a bootstrap estimate and find that RECODE > NGU for Mean HNS (p=0.0185) and Mean Capped HNS (p=0.0419). We will modify the wording in the main text to avoid possible misinterpretations and include an appendix summarizing all of these metrics with appropriate confidence intervals and hypothesis tests (see Table 6 in the revised appendix).

Human normalized score (HNS) is introduced at the end of Sec. 1 where Fig. 1 is first referenced, as well as in the appendix. We have also include appropriate references and definitions in the caption for completeness in the updated version of the paper.

Note that when compared to NGU, RECODE:

• Removes the complexity of having to rely on a parametric novelty detector (RND) for long-term memory, which involved hard to tune hyperparameters and design choices including selecting a network architecture and network optimizer, and how to combine the RND reward and episodic reward
• Inherits the following hyperparameters from the episodic component of NGU: atoms removal, reward constant, decay rate, # nearest neighbors, and relative tolerance (referred to as cluster distance in that work)
• Adds hyperparameters for discount, insertion probability, memory update and memory size

Taking this into consideration the slight increase in complexity of the memory mechanism is more than offset by the removal of RND, and overall we consider RECODE a less complex novelty detection mechanism (both conceptually and in ease of tuning) than NGU.

Ensuring that the reader can clearly understand which of these new hyperparameters are important to tune and when remains important. We have added some general guidelines in Section 3 of the paper, as well as an ablation over memory size and insertion probability in Appendix L.1, Fig. 20.

Notice also that in general most of RECODE's design space (memory upkeep, representation learning, forgetting) is shared across the family of non-parametric visitation counts estimators (that goes beyond EMM/NGU). More in detail, comparing RECODE to its closest alternative NGU we have that:

• Memory size: NGU side-steps tuning a memory size by implicitly setting the EMM size to be the maximum length of an episode. Note that this is not possible in many cases (long episodes cannot be all stored in RAM), and makes it impossible to preserve long-term memory. To cover these limitations, NGU introduces extra complexity with a completely separate long-term novelty detector (RND). Therefore, both RECODE and NGU are more complex than vanilla EMM: RECODE through the memory management methods with their hyperparameters; and NGU through RND with its hyperparameters that need to be tuned (network architecture, optimizer, etc…). Overall we find that RECODE is robust when choosing its new hyperparameters (see updated ablations after rebuttal). In contrast we found that RND is quite difficult to tune and has a complex interaction with the episodic reward and representation learning which makes it more difficult to reason about. Removing RND makes it easier to tune the overall novelty mechanism.
• Heuristics to update/add/remove atoms of memory: this is an inherent feature of all finite-size memories, since choosing a removal strategy is always necessary when dealing with finite memory and potentially infinite interactions. NGU’s choice in this regard seems simple (add every atom encountered and remove them all at the end of the episode), but it is not applicable to complex real-world scenarios (e.g. if the episode length is larger than what is computationally feasible to store in memory we must remove atoms before the end of an episode). Overall, NGU can avoid memory management heuristics because all the heuristics are pushed into the RND module, while RECODE must explicitly address them. Compared to existing novelty estimation methods for RL our discounting and cluster merging approaches are more novel, but they are still rooted in and inspired by a long tradition of non-stationary clustering methods such as DP-Means (see App. D). Similarly, our particular design choice for removal was motivated by empirical observations in toy experiments (see App. D), but as stated, it is ultimately an arbitrary choice. Our ablation against alternative removal strategies demonstrated that RECODE is robust to this choice.
• Discounting: $\gamma$ is one of the two important hyperparameters that we recommend should be tuned in the guidelines we have added in the latest version. We give more insight on how it impacts RECODE’s performance in Appendix D including illustrative toy experiments, theoretical connections to DP-Means and ablations on the same complex environments used in the main paper. In particular, we show that the usefulness and impact of $\gamma$ strongly depends on the non-stationarity of the observations, which in turns depend on both the evolution of the observation representation and the diversity of the data collected by the agent.
• Representation learning method (i.e. embedding) and the associated distance kernel were also important design choices in prior non-parametric methods. The adaptive kernel we use is also the same as that used in NGU, except for the modification to sum over all atoms within an epsilon ball of the query embedding rather than over a fixed number of nearest neighbours. This complication was unnecessary in NGU because every atom represented a count of 1 and thus did not suffer from the undesirable behaviour that adding an embedding could decrease the count for that embedding when using the latter approach (see discussion under Eq. 3)