We appreciate the reviewer's careful attention to detail and the positive feedback provided. The following clarifications will hopefully address your concerns and strengthen the case for our paper:

Weaknesses

Q: While the focus on unordered transition tuples is mentioned as a benefit, I would think that there are certain environments where the temporal nature of trajectories are important. Could you comment on this please?

A: Revieiwer kpCs brought up the same point and we have answered it above (see question 1 in discussion with Revieiwer kpCs). TL;DR: agree and GENIE's design choice on prioritising individual transition tuples is flexible to accommodate non-Markovian states.

Q: Minor: 1. Line 88, for minimax one also often cites [1]; 2. The $\tau$'s beneath the max/expectation in equation (1) don't have the A and P superscripts.

A: Appreciate the sharp eye, we have revised this.

Questions

Q: Algorithm 1, please indicate what the blue text means (I assume changes to ACCEL but being clear on this would be helpful.)

A: Thank you, we have made this clearer in the revised manuscript.

Q: Please provide aggregate results averaged over all of the minigrid eval. levels. It is hard at a glance to see how the algorithms compare.

A: Figure 4a is what you are looking for. The IQM and Optimality Gap are metrics introduced by the rliable library (Agarwal et al., 2021) used for fair aggregation of performances across different tasks (levels) and comparing the performance of algorithms.

Q: Do the GENIE generated levels actually look more diverse than those generated by e.g. ACCEL? Please show a sampling of levels.

A: Answered in our global rebuttal. The sections "GENIE Introduces Level Complexity", "Low Regret but High Novelty Levels Provide Interesting Experiences" and their accompanying plots visually demonstrates the diversity of the levels generated by GENIE.

Q: In table 1, PLR-GENIE has the most state-action coverage, but performs much worse than the ACCEL-based methods. This seems to contradict the claim that the increased diversity is causing better performance. Could you explain this please?

A: It is important to note that there are fundamental differences in the curriculum generation mechanisms of ACCEL and PLR outside of GENIE's control. ACCEL mechanism initiates the curriculum with "easy" levels (e.g. a Minigrid with no walls and only the goal) and leverages minor edits (mutation) to gradually introduce complexity to the levels. In contrast, PLR relies on domain randomization (DR) to generate new levels. DR lacks the fine-grained control over the difficulty progression that ACCEL's mutation-based method offers. As a result, even though GENIE exposes the PLR agent to a wider coverage of state-action pairs, the PLR teacher does not present these experiences to the student in an order that facilitates optimal learning. The inherent difference in curriculum generation mechanism between the two algorithms (i.e. ACCEL and PLR) admits a significant difference in performance from the get-go that cannot be recovered by GENIE. To summarize, GENIE enhances the state-action space coverage for both ACCEL and PLR, but ACCEL's gradual curriculum complexity introduction mechanism simply capitalizes on that better.

Q: There may be some confusion between your GENIE and [1]

A: Acknowledged in global rebuttal.

Q: For car racing you do use images, is the image simply flattened? Could this have problems with e.g. not being translationally invariant?

A: All algorithms incorporate a CNN model over the images, in accordance with previous UED literature. We thank you for bringing up this point and we have included a small section in the appendix to make this clear.

Q: Choosing the range of $K$ (number of GMM) kernels can be challenging?

A: Actually, $K$ does not need to be constricted to a fixed range and can be adapted online. Metrics like silhouette score (that we used) or other metrics such as AIC/BIC provide a score for the fit of the GMM and Bayesian methods can be applied to search for the $K$ (not bounded to a range) that fulfils a desired threshold of the metric. The reason why we used a fixed range for $K$ in GENIE is simply because we found that a range of 6-15 kernels already provided significant improvements to the GENIE-augmented algorithms and did not necessitate further optimization.

Q: Do I understand correctly that you just concatenate the observation and actions to form $x$, which is then used to fit the GMM? How can this scale to much larger observations?

A: Yes, your understanding is correct. Regarding the dimensionality issue, it is an issue which can be easily remedied. Dimensionality reduction techniques such as Principal Component Analysis (PCA) or learned autoencoders can be employed to scale down large observation spaces without significant loss of information. This is a direction that is also mentioned in the "Future Work and Limitations" section of the appendix of the main paper. High-dimensional state spaces present issues for deep learning methods in general, and remedies used by the policy algorithm to scale down the state space can be applied in parallel for the fitting of GMMs in GENIE.

We sincerely appreciate the reviewer's feedback and the recognition of the key strengths of our method. The following clarifications will effectively address your concerns and further enhance our paper:

Weaknesses:

Q: There is a strong assumption that all transitions are independent, which is not always true. What if there is an environment where an agent needs to conduct some initial behavior (e.g. finding a key) and then using it to act later (e.g. opening a door)? It just feels like the method is designed based on the toy environments we use in RL research, and is not actually scalable for larger more complex domains in the future.

A: Temporal information can be accounted for by using the augmented states and it should be addressed by the underlying RL mechanism (hierarchical RL, constrained RL, etc.). We would like to highlight that GENIE's design to focus on individual (s, a) transitions and not entire trajectories is agnostic to these augmented state representations used by the policy. On this note, we would make this advantageous characteristic of GENIE's design clearer in the revised manuscript."

Q: Hate to be that person, but the name GENIE is taken by multiple works already and recently by Bruce et al. (2024) in a highly relevant paper. It would be recommended to find a more relevant acronym or simpler name.

A: Acknowledged in global rebuttal.

Q: The arrows in figure 2 are too small.

A: Thank you and we have fixed this in the revised manuscript.

Questions:

Q: What other approaches could be used to assess novelty at larger scale?

A: With regards to assessing novelty at a large scale, Section B in the appendix touches on how dimensionality-reduction techniques can be paired with GMMs for better scalability to higher-dimensional domains. As you pointed out, there is no need to restrict ourselves to GMMs. However, on the flip side, we showed that such a simple yet general method for quantifying novelty and combining it with regret could result in significant empirical gains. GENIE's main contribution lies in demonstrating the importance of novelty in UED and highlighting how it complements minimax regret. That opens the door to future UED research to look into incorporating novelty into their curriculum.

Q: Can you show any examples of levels that have high novelty but low regret, and turn out to be useful training levels for the agent?

A: Addressed in the global rebuttal (see section "Low Regret but High Novelty Levels Provide Interesting Experiences", i.e. Figure 2's explanation)

We appreciate the reviewer's time and valuable feedback. We believe the concerns raised generally pertain to broader problems in RL and are not inherent problems of GENIE. The following clarifications will explain our stance and strengthen the case for our paper. We kindly request the reviewer to reconsider the score, given that the issues raised do not detract from the contributions of GENIE and the promising direction of novelty-driven autocurricula:

Questions

Q: Using unfamiliar states to measure uncertainty is conceptually similar to curiosity-driven approaches in RL. However, the paper doesn't review the relevant literature. It would be helpful if the authors explained how their idea aligns with curiosity-based RL theories and what their paper adds to this field.

A: We appreciate the reviewer's astute observation regarding the conceptual similarity between our approach and curiosity-driven RL. While we acknowledge that our original manuscript should have addressed this relationship more explicitly, we're grateful for the opportunity to clarify these connections and distinctions. Indeed, both curiosity-driven RL and our UED approach leverage the concept of novelty or unfamiliarity to guide learning. However, they differ significantly in their application and theoretical foundations. Curiosity-driven learning literature is build on prioritising interesting experiences in a static environment [1], or across a set of predefined tasks [2]. Meanwhile, UED is focussed on generating environments that are interesting/useful for learning. UED shapes the learning curriculum itself rather than the exploration strategy within environments. This is analagous to the difference between Prioritized Experience Replay [3] from traditional RL and Prioritized Level Replay [4] from UED. The former is an "inner-loop" method to prioritize past experiences for training and the latter is an "outer-loop" method that uses past experiences to inform the collection/generation of future experiences. In the same vein, curiosity-driven learning is focussed on prioritizing novel experiences for policy updates but GENIE is focussed on generating/curating levels that can induce these novel experiences. This fundamental difference in purposes means that theoretical and empirical comparison between curiosity-driven approaches and GENIE is not as direct. As such, we focussed our attention mostly towards current novelty measures in UED literature, which we are of more relevance. Still, we thank the reviewer for making this observation as the general audience would also appreciate clarity on this matter. We have included a short section clarifying the distinctions between curiosity-driven learning and GENIE in the appendix of the revised paper.

[1] Pathak, D., Agrawal, P., Efros, A. A., & Darrell, T. (2017). Curiosity-driven exploration by self-supervised prediction.

[2] Burda, Y., Edwards, H., Pathak, D., Storkey, A., Darrell, T., & Efros, A. A. (2018). Large-Scale Study of Curiosity-Driven Learning.

[3] Schaul, T., Quan, J., Antonoglou, I., & Silver, D. (2016). Prioritized experience replay.

[4] Jiang, M., Grefenstette, E., & Rocktäschel, T. (2021). Prioritized level replay.

Q: In UED for curriculum learning to train generalizable policies, Genetic Curriculum (Song et al., 2022) also employs UED. Since both papers were evaluated on BipedalWalker and BipedalWalkerHardcore, it would be useful to compare GENIE with Genetic Curriculum.

A: Thanks for pointing to the work by Song et al. (2022). The other UED papers had not referenced this work or compared against this work. This is likely due to the fact that their problem definition in their paper differs from the Underspecified Partially Observable Markov Decision Process (UPOMDP) setting in UED and there is not many parallels other than sharing a commonly-used domain. Also, the original POET [5] paper which they compare against used a 5D-BipedalWalker domain (we used 8D), and it is not clear in their paper which domain they use. To the best of our knowledge and thorough search, their code repository is not publicly accessible and we are unable to replicate their work to compare the results.

[5] Wang, R., Lehman, J., Clune, J., & Stanley, K.O. (2019). Paired Open-Ended Trailblazer (POET): Endlessly Generating Increasingly Complex and Diverse Learning Environments and Their Solutions.

Q: GENIE uses a fixed window FIFO buffer. Will this achieve equilibrium? For instance, if the agent cycles through level sets A, B, and C, potentially forgetting each set as it explores others, will agents trained by GENIE converge to steady-state behavior?

A: Your description of a potential "mode collapse" behavior is reasonable. However, this seems to be pointing at the general negative effects of catastrophic forgetting within the broader RL literature and function approximation methods. While GENIE does not explicitly guarantee convergence to a steady-state behavior with respect to novelty, it's important to note that this challenge is not unique to our approach. The leading approaches, PLR and ACCEL are also unable to provide robustness guarantees against such oscillatory exploration patterns. It would be interesting to start having conversations on how we can bridge insights from "continual learning" and "stability-plasticity dilemma" literature with UED, and see how minimax-regret and GENIE's novelty could possibly circumvent the negative effects of catastrophic forgetting.

Q: Finally, there are some minor typos and editorial mistakes. For example, line 63, PLR, and ACCEL are mentioned without explaining what those are.

A: Thank you for pointing this out, we have fixed this in the revised manuscript.

We sincerely appreciate the reviewer's insightful comments and recognition of the valuable direction of novelty-driven autocurriculum that GENIE is pushing for the UED field. Also, it is always refreshing to engage with a reviewer who has in-depth knowledge of UED. The new results within the global rebuttal and our following clarifications would be of interest to you and strengthen the case for our paper:

Weaknesses

Q: The method would be more convincing if the generated levels were visualized and directly compared. Ideally, demonstrate that new motifs are being generated. For example, display the distribution over stump height late in training of ACCEL and ACCEL-GENIE to show more even coverage by ACCEL-GENIE, and randomly sample a few levels from each for visual confirmation.

A: Answered in global rebuttal, refer to the section "GENIE Introduces Level Complexity" explanation.

Q: The paper would be improved by exploring the mechanism behind the results in more depth. If the theory is that the diversity term introduces high-regret levels previously excluded from the buffer, it should be demonstrated directly.

A: This is something we have thought about while working on GENIE. The main struggle with trying to demonstrate this is that both the regret and novelty metric are inherently policy-dependent. As such, it is impossible to directly measure whether prioritising or not prioritising a level via GENIE would lead to discovering a higher regret level down the road because the divergence in realities would result in different policies with non-commensurable subjective regrets. However, one way we can indirectly measure this is by observing whether a greedy selection of high regret levels (as in ACCEL and PLR) or a balanced regret-novelty prioritization (as in ACCEL-GENIE and PLR-GENIE) results in better cumulative/mean regret in the replay buffer across the training horizon. The section "Prioritizing Novelty Actually Increases Regret" in our global rebuttal demonstrates that GENIE actually results in higher regret across the replay buffer in the Car-Racing domain despite not directly optimising for it.

Q: On line 258, results are overstated, as ACCEL-GENIE's performance is within ACCEL's margin of error in nearly all environments. This claim should be corrected. This isn't essential for paper acceptance, as the minigrid benchmark is nearly saturated and serves as an MNIST for the field. The empirical results in the other two environments are sufficient.

A: We have amended line 258 to exclude the remark on ACCEL-GENIE's outperformance over its predecessor but the point on PLR-GENIE's clear improvement over PLR still holds.

Q: Add error bars to Table 1. Ensure matching colors for the same method in Figure 7. Fix the stray parenthesis on line 303. Equation 1 should reflect the canonical PAIRED objective, comparing the two expected returns directly, rather than being "optimized" for deterministic domains.

A: Thank you for the attentiveness to detail, we have addressed this in our revised manuscript.

Q: Consider renaming the model since another prominent environment-generating model named GENIE has been released recently. This will avoid confusion when discussing how the two could be combined.

A: Addressed in global rebuttal.

Q: In the abstract I think it is not clear that novelty, on its own, is critical for agent's generalisation ability. Two situations that are different but not in a way that is relevant for the task and are processed by the network in the same way are effectively the same, and would not affect generalisation ability.

A: We are actively refining our abstract to more effectively advocate for the benefits of novelty-driven autocurricula methods, while being mindful of the brevity throughout this rebuttal process. Regarding the notion that "different situations processed similarly by the network do not affect generalization ability," we believe this holds true primarily for fixed curriculum methods but not necessarily for autocurricula methods. We hope to have a constructive discussion about this.

Although the two situations present differently but provide similar learning experiences (with relation to the task) at the current moment, they both independently inform the collection/generation of future environments. The fact that these environments behave differently (in state-action distribution) indicates the potential that they can lead to totally different and novel environments down the training horizon, especially with mutation-based methods. Therefore, even if these scenarios yield similar learning signals initially, prioritizing them for the unique state-action distributions they cover via GENIE remains beneficial for generalisation. This is an exciting discussion which can be correspondingly highlighted in our revised manuscript.

Q: It also appears that in a few places the "underspecified" in UPOMDP is taken to mean that there is a one-to-many mapping between parameters and environments. In general this is not the case, as the minigrid environment has a one-to-one mapping between parameters and environments, the "underspecified" simply means that these parameters are not given by the designer. It is fair to want UED algorithms to work even when there is such a one-to-many mapping, but it is not required as part of the problem formulation.

A: We acknowledge that the one-to-many mapping between free parameters and environments, while common, is not a mandated characteristic of UED. We have amended the manuscript to reflect that nuance more clearly (e.g., "entails there is a one-to-many mapping" is revised to "possibly entails a one-to-many mapping").

Questions

Q: What sort of qualitative difference do you see between ACCEL-GENIE and ACCEL levels?

A: Answered in global rebuttal, refer to the section "GENIE Introduces Level Complexity".