We appreciate your thorough review and useful comments, particularly highlighting that we are focusing on an "important problem", and that our algorithm is "simple, and easy to understand". Please find our responses below.

Weaknesses

Different Definitions of Learnability

Intuitively, we justify our definition as follows (in a goal-based setting where there is only a nonzero reward for reaching the goal):

• $p$ represents how likely the agent is to obtain positive learning experiences from a level.
• $1-p$ represents the maximum potential improvement the agent can make on that level.
• Multiplying these yields (probability of improvement) * (improvement potential), i.e., expected improvement.

$p(1-p)$ can also be seen as the variance of a Bernoulli distribution with parameter $p$, i.e., how inconsistent the agent's performance is.

We have added this explanation to the updated manuscript to increase clarity.

To confirm this choice we have run a set of experiments on single-agent JaxNav where we represent the learnability function as a piecewise quadratic. During this test, the peak learnability value remained at 0.25 but we varied the success rate at which the peak occurs. The results are in Figure 4(c) of the attached PDF; overall, a peak around $p=0.5$ performs the best, and moving away from this reduces performance slightly. However, as performance is not dramatically worse, this indicates that the most important aspect of learnability is in rejecting levels with perfect or zero success rates.

Hyperparameter choices / Ablations

Thank you for raising this point. We have tuned all of the hyperparameters, and have run ablations on SFL. Our conclusions remain unchanged (i.e., that SFL outperforms UED), but we have more insights now into which parameters are most important for SFL. Furthermore, we find that SFL is less sensitive to hyperparameters than PLR or ACCEL. The new tuned results are in Figure 1, and the ablations are in Figure 2 of the 1-page PDF.

More seeds and environments

Thank you for raising this point. We have run more seeds for multi-agent JaxNav, bringing the total count to 5, and our results have not changed. We have also included results on an additional environment, XLand-MiniGrid, as described in our global response. Here, SFL also outperforms PLR and DR.

We now have results in four environments demonstrating SFL's superiority compared to SoTA UED methods. We further compare against several ablations. We believe these results are sufficiently broad to showcase SFL's performance.

Writing

Thank you for raising the writing quality issues, and we apologise for letting them slip through. We have carefully reviewed the submitted manuscript and have fixed these issues for our updated version.

Questions

Different values of the sampling ratio $\rho$

We agree that this is an important question and we have tested various values of $\rho$ on single-agent JaxNav with results shown in Figure 2 of the attached PDF. Increasing $\rho$ beyond 0.5 increases performance slightly. Due to the high maximum fill % used for JaxNav, we hypothesise that the randomly generated levels are able to present challenging control and navigation problems. While increasing $\rho$ makes the agent train on more learnable levels, it may also decrease the diversity of the levels seen by the agent.

Decreasing order of learnability

Thank you for this suggestion, we agree it is a useful question to answer. We have trialled selecting levels in decreasing order of learnability rather than randomly and, as illustrated in Figure 1 of the attached PDF, this has roughly the same effect as reducing the buffer size. This makes sense, as by reducing the buffer size or selecting in decreasing order, we are restricting the range of levels that can be chosen to only the highest-learnability ones.

Average vs top-k learnability

For 45 iterations for single-agent JaxNav, we logged the average and median learnability of the entire set of sampled levels, and the subset we use to train on, with results below. In short, the entire set of sampled levels generally has low learnability, whereas the top 100 levels have much higher values. This shows that SFL is filtering out levels with very low learnability (i.e., levels that the agent either already perfectly solves or that are currently too hard). This result further explains why we outperform existing methods. We appreciate you raising this point and have added this analysis to the manuscript.

What we did to make UED better

For the existing UED methods, we used the open-source implementations provided by JaxUED and conducted a thorough sweep of hyperparameters, as explained in our general response. Additionally, as JaxUED showed, and as we've also found, DR can be surprisingly competitive if the PPO parameters are tuned appropriately. Indeed, in the multi-agent setting of JaxNav, DR is in line with or outperforms all existing UED methods during CVaR evaluation; albeit the UED methods use hyperparameters tuned on the single-agent JaxNav setting.

Different learnability definitions?

Following your suggestion, we have experimented with different peak values, as outlined above. We have not tried an altogether different definition because ours followed from the intuition explained above. However, our code will be open-sourced, allowing the community to easily try alternative definitions.

Conclusion

Thank you once again for your detailed review. We hope our responses have addressed your concerns, and we welcome any further discussion or questions you might have. If we have successfully alleviated your concerns, we kindly ask you to consider updating your score to recommend accepting our paper.

Dear Authors, Thanks for your detailed response and additional experiments.

Different values of the sampling ratio: Thanks for producing these results. In the final manuscript, I would be interested in seeing other possible features of the environment which are common in levels sampled with SFL

Average vs top-k learnability in UED: This result is interesting. I would consider to appropriately insert it in the appendix of the final version of the paper.

Justification for SFL & Different Definitions of Learnability: Thanks for providing additional examples of learnability. This addresses the issues I raised.

Given the above discussion, I believe most of the issues I raised were appropriately addressed by the authors. I will raise my score accordingly.

Thanks again for the detailed answers and the additional experiments, and good luck with the paper

Thank you for your positive review, particularly highlighting that our paper is "technically sound" and that the learnability score is "original". Please find our responses to your comments below.

Lines 15-17. Suggest to delete spurious statements such as “We had tried our best to make current UED methods work for our setting before going back to the basics and developing our new scoring function, which took a few days and worked out-of-the-box. We hope our lessons and learnings will help others spend their time more wisely.” Don’t complain!

We agree and have removed this from our manuscript.

The authors should make an effort to assist readers familiar with RL but not ACL methods by providing details in the appendix. For example in line 175, Algorithm 1 does not provide information on how \phi is updated. The update algorithm could be provided in the appendix.

Thank you for your suggestion and we agree that we should provide a more detailed background on ACL in our appendix. On line 175, $\phi$ is updated using any RL policy learning algorithm (we use PPO) and as such is not affected by the ACL process, we will make this distinction clearer in our updated manuscript.

Figure 2 includes statements about “learnability” prior to a definition of learnability

Lines 154-157. Learnability has not yet been defined so statements about slight/no correlation with learnability are vacuous. It is not clear to reader whether learnability in these lines/Figure 2 is the same as the definition of learnability given later (and used by SLR).

Thank you for pointing this out! We apologise for this oversight and we have rectified this by defining learnability earlier on in our paper.

Lines 133-135 might better go in the later section on weaknesses/limitations.

We appreciate this suggestion and have implemented this in the updated manuscript.

Line 214. The authors do not define “solvable.” The reader needs to know how you are operationalizing this term.

We added an explanation to the manuscript., thank you for bringing it to our attention. "Solvable" in our paper means that the goal state can be reached in a particular level, i.e., it is not impossible to complete.

Line 274-5. Unclear what “perfect regret” means.

Regret is defined as the difference in return between the optimal policy on a level, and the current policy. However, since it is intractable in practice to compute this, most methods use approximations (such as PVL and MaxMC). We use "perfect regret" to refer to the exact implementation of regret, which is sometimes possible (e.g. in gridworlds we can compute the optimal return). We have made this clear in our updated manuscript.

It would be cool if the authors could comment on how SFL might be generalized to continuous outcomes and stochastic environments.

Here are just some possible options to explore. We have added this discussion to our updated manuscript, thank you for raising this point as an important step of future work!

• In a non-binary-outcome domain, we could potentially reuse the intuition that $p(1-p)$ can be seen as the variance of a Bernoulli distribution; therefore, in a continuous domain, an analogous metric would be the variance of rewards obtained by playing the same level multiple times.
• For stochastic environments, we could form an extended level space, where the random seed and the level $\theta$ are bundled into $\tilde \theta$. In this way, we could turn a stochastic environment into a deterministic one, and since we assume simulator access already, this is not a significantly stronger assumption.

Conclusion

Thank you again for your helpful review, we hope we have addressed your comments satisfactorily, and welcome further discussion.

We thank the reviewer for their comments, especially for highlighting our "simple yet novel UED approach" and that our paper is "well-written". Below, we address the issues raised in the review:

Correlation analysis for SFL

Section 4.1 analyses MaxMC and PVL, popular UED score functions, in terms of their predictiveness of learnability. However, there is no demonstration of a similar analysis for SFL. Although SFL's scoring function is intuitive and it is not as challenging to guess what the scoring would look like, including such an illustrative comparison would support the claims in this paper.

We agree such analysis would be helpful, and we have added this to our updated manuscript. Due to space constraints we have not included this in the attached rebuttal PDF.

Easy Levels

To assess performance on easy levels we have run our evaluation procedure over 10,000 uniformly sampled levels with fewer obstacles than usual. For JaxNav, we used a maximum fill % of $\leq 30\%$, half of the standard 60%. Meanwhile, for Minigrid, we use a maximum number of 30 walls instead of 60. These levels, therefore, are generally easier than the levels we evaluated on in the main paper. Results are reported in Figure 4(a,b) of the attached PDF.

On JaxNav, SFL still demonstrates a significant performance increase while on Minigrid all methods are very similar. Due to the challenging dynamics of JaxNav, even levels with a small number of obstacles can present difficult control and navigation problems meaning Automated Curriculum Learning (ACL) methods (such as SFL) still lead to a performance differential over DR. Meanwhile, in Minigrid, due to its deterministic dynamics, difficulty is heavily linked to the obstacle count as this allows for more complex mazes. As such, DR is competitive to ACL methods in settings with fewer obstacles.

SFL runtime speed

Thank you for raising this important point, as it highlights how SFL takes advantage of parallel computations on the GPU.

Looking at a single iteration (including training + eval) in Minigrid on an L40S GPU, the time breakdowns are as follows:

We note that the SFL rollouts are fast for two reasons:

• We aggressively parallelise them, running up to 5000 environments in parallel, which takes about the same time as running only hundreds in parallel.
• We do not compute any gradients for these transitions.

The upshot is that they take significantly less time than the actual training step. Furthermore, UED's training step is more complex than SFL's, since it must maintain a buffer of levels, compute the scores during training, and potentially update the buffer.

For JaxNav, obtaining the learnable levels takes a little longer, but still takes less time than our logging. Due to this, slight differences in logging between PLR and SFL masked this additional computational cost. To better control for this, we measure how long SFL takes vs PLR in the absence of logging. We find that SFL is about 6% slower than PLR, despite running all of the additional rollouts. In Figure 1(a) of the attached PDF (and our updated manuscript), we have provided compute-time matched results for single-agent JaxNav (where SFL runs for 6% fewer timesteps). Despite running for fewer timesteps, SFL still significantly outperforms UED methods. SFL on Minigrid runs as fast, or slightly faster than PLR.

We apologise for the oversight in not specifying how long our rollouts are. We use a consistent rollout length of 2000 steps. We have updated this in our manuscript.

Conclusion

We hope we have addressed the reviewer's comments and are happy to discuss any of these points further. We would further ask if our responses have addressed the reviewer's concerns, and that they consider increasing their support for our paper.

Dear reviewer, thank you for your thorough review and helpful suggestions! We also appreciate you mentioning that our paper "includes many contributions" and "could help to move further ACL research toward more promising directions." Please find our responses and changes below.

Hyperparameters and UED underperformance

As rightfully requested by the reviewer, we have performed extensive hyperparameter tuning for all methods (excluding DR). Using these new, optimised hyperparameters (see Figure 1 in the attached 1-page PDF), UED outperforms DR (in Minigrid and Single-agent Jaxnav) but SFL still outperforms UED. For DR, we use the PPO hyperparameters as discussed in the main response, and did not tune it further, as it has no other relevant hyperparameters. Please see our main response for details regarding how we performed our sweep.

Furthermore, when comparing our results to previous work please note that in the original Robust PLR paper, they use 25 walls for Minigrid. However, they also show that changing the number of walls can drastically alter results; for instance, in appendix C.1.2, they show that using 50 walls causes DR to be competitive to UED. Following Minimax [1] and JaxUED [2], we use 60 walls. Therefore, we cannot directly compare the results of our work and that of the original Robust PLR & ACCEL papers.

[1] Jiang, et al. "Minimax: Efficient Baselines for Autocurricula in JAX."

[2] Coward, et al. "JaxUED: A simple and useable UED library in Jax."

Episodic Return Plots

We primarily include success on the set of held-out levels during training rather than episodic return because, in these goal-oriented domains, the success rate is a more intuitive and clearer marker of performance. This is because the actual environment reward may include reward shaping terms that do not directly correspond to our ultimate aim of reaching the goal (but are nonetheless necessary to learn a policy).

We also find that the average return in all our domains is closely tied to success rate. This is illustrated in Figure 5 of the manuscript where 5(c) reports success rate while 5(d) reports return (note, there is a naming error on the y-axis of Figure 5(d)).

Therefore, the performance trends illustrated in 3(b), 5(c), 7(b) are mirrored in the episodic return throughout training. We have clarified this in the revised manuscript, and have included reward curves in the appendix.

Learnability as PLR score function and PVL as SFL's metric

Thank you for suggesting this, we agree that this is an important ablation to understand the source of improvement and have included these results in the attached PDF (Figure 3).

We ran this ablation for both Minigrid and single-agent JaxNav, and in both domains, SFL + Learnability outperforms all other combinations. Using learnability with PLR/ACCEL has a slight positive effect for PLR in JaxNav and a negative effect in Minigrid. Using PVL as the score function inside our SFL algorithm performs worse, except when we have a large buffer of levels in JaxNav.

Some intuition for why this is:

• In the large buffer case for PVL on JaxNav, the training levels are more random, since we also include levels with lower scores. Indeed, with a small buffer, PVL performs very poorly, a result in line with our analysis in Figure 2 of the submitted manuscript as PVL fails to predict the frontier of learnability accurately.
• Conversely, a large buffer results in a set of levels that is slightly biased towards higher success rates, as illustrated in Figure 2 of the submitted manuscript (i.e., PVL correlates slightly with success rate). This bias helps screen out some unsolvable levels using the scoring function, a feature of regret-based UED algorithms [3]. Additionally, our observation shows that random JaxNav levels often provide a good learning signal, as demonstrated by a sampling ratio $\rho$ of 0.5 performing similarly to 1.0 in the SFL ablations shown in Figure 2 of the 1-page PDF. Therefore, SFL-PVL with a large batch of levels creates a learning curriculum that leads to decent performance, although it is still inferior to SFL with learnability.

The results of this ablation suggest that the improvements due to SFL can be attributed to both the learnability score function and our improved sampling approach.

Note, however, that we did not hyperparameter-tune these results, as we used the optimised hyperparameters found above, and just swapped the score function.

[3] Jiang, et al. "Replay-guided adversarial environment design."

Poor explanations and presentation

Thank you for pointing out these problems, we appreciate your thoroughness. We have rectified them in our updated manuscript. We have also defined learnability earlier on, making the paper clearer.

Questions

Using our heuristic with PLR?

See above and Figure 3 in the attached 1-page PDF. We find that SFL + Learnability outperforms the other combinations.

A discrepancy between UED's performance in this paper and [2]?

See above, in "Hyperparameters and UED underperformance".

Are the 10,000 solvable levels unseen?

The levels used during evaluation are sampled from our environment generator separately from the training process. As the space of possible levels is very large, generating the same random level twice is unlikely.

Is the method restricted to Jax-based settings?

Our implementation is in JAX but the method is general. However, as raised in our limitations section, one must take the cost of SFL's additional environment rollouts into account when considering implementing our algorithm; we chose JAX because its speed and parallelisation significantly alleviates this constraint.

Conclusion

We hope that the reviewer feels we have addressed their questions and welcome any further discussion. We also ask that, if all their concerns are met, the reviewer consider revising their score to recommend accepting the paper.