No Regrets: Investigating and Improving Regret Approximations for Curriculum Discovery

Authors: alex  rutherford
michael  beukman
timon  willi
bruno  lacerda
nick  hawes
jakob  foerster
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 22:01:14

Abstract: What data or environments to use for training to improve downstream performance is a longstanding and very topical question in reinforcement learning. 
In particular, Unsupervised Environment Design (UED) methods have gained recent attention as their adaptive curricula promise to enable agents to be robust to in- and out-of-distribution tasks.
This work investigates how existing UED methods select training environments, focusing on task prioritisation metrics.
Surprisingly, despite methods aiming to maximise regret in theory, the practical approximations do not correlate with regret but with success rate.
As a result, a significant portion of an agent's experience comes from environments it has already mastered, offering little to no contribution toward enhancing its abilities. Put differently, current methods fail to predict intuitive measures of *learnability*. Specifically, they are unable to consistently identify those scenarios that the agent can sometimes solve, but not always.
Based on our analysis, we develop a method that directly trains on scenarios with high learnability. This simple and intuitive approach outperforms existing UED methods in several binary-outcome environments, including the standard domain of Minigrid and a novel setting closely inspired by a real-world robotics problem. 
We further introduce a new adversarial evaluation procedure for directly measuring robustness, closely mirroring the conditional value at risk (CVaR).
We open-source all our code and present visualisations of final policies here: https://github.com/amacrutherford/sampling-for-learnability.

Main paper: 
 introduction: 
 Curriculum discovery-automatically generating environments for reinforcement learning (RL) agents to train on-remains a longstanding and active area of research [1, 2] . Automated curriculum learning (ACL) methods offer the potential to generate diverse environments, leading to the development of more general and robust agents. Recently, a class of methods under the umbrella of Unsupervised Environment Design (UED) has gained popularity, owing to their theoretical guarantees of robustness and empirical improvements in out-of-distribution generalisation [3] [4] [5] .Currently, the most popular and empirically successful subfield of UED develops methods that aim to maximise regret-the difference in performance between an optimal agent and the current agent [3] [4] [5] [6] [7] [8] . However, computing regret is intractable in all but the simplest tasks, forcing practical methods to instead approximate it [4, 9] . While the prevailing assumption has been that these approximations are faithful, we investigate this further and find that this is not the case: specifically, these scoring functions correlate with success rate rather than regret. This means that these methods tend to prioritise tasks that the agent can already solve, leading to much of the collected experience not contributing to learning an improved policy.While we find that regret performs well in settings where we can compute it-confirming that the underlying theory is sound-we show that the common approximations are unreliable. Therefore, we focus on a different scoring mechanism which instead prioritises levels that provide a clear learning signal to the agent. More specifically, these levels are those where the agent's success rate is neither 100% nor 0%, i.e., levels that are neither too difficult nor too easy [1, 10] .Using this scoring function, we develop Sampling For Learnability (SFL), a method that estimates learnability by rolling out the current policy on randomly sampled levels and selecting those that the agent solves sometimes, but not always. We find that this simple and intuitive approach outperforms DR [11] , Prioritised Level Replay [4, 9] and ACCEL [5] on four challenging environments, including our novel single-and multi-agent robotic navigation domain, Xland-Minigrid [12] and Minigrid [13] .To truly put our method to the test, we develop a new, more rigorous robustness evaluation protocol for ACL, and demonstrate that SFL significantly outperforms all other methods. Rather than evaluating on a set of arbitrary hand-designed environment configurations, our protocol computes a risk metric on the performance of the method, by evaluating its performance in the worst α% of a newly sampled set of environments.Our contributions are as follows:1. We illustrate the inefficacy of current UED methods on several domains, including a novel robot navigation environment.2. We identify the reason for this observation: current UED regret approximations are flawed.3. We present Sampling For Learnability (SFL), a simple algorithm that trains on environment configurations that have a positive, but not perfect, solve rate, and show that it significantly outperforms current UED approaches on four domains.4. We introduce a new evaluation protocol: the conditional value at risk (CVaR) of success of a trained agent on a set of sampled levels. This metric specifically measures the risk of poor generalisation, quantifying robustness in the ACL setting.2 Background 
reinforcement learning & upomdps: 
 We model the reinforcement learning problem as an underspecified partially observable Markov decision process (UPOMDP) [3] , denoted by M = ⟨A, O, Θ, S, T , I, R, γ⟩. Here, A, S, and O represent the action, state, and observation spaces, respectively. The agent receives an observation o (without directly knowing the true state s) and selects an action, which results in a transition to a new state, a new observation, and an associated reward. Θ represents the set of possible parameters, where each θ ∈ Θ defines a specific level. Each θ corresponds to a particular instantiation of the POMDP, with an associated transition function P θ : S × A → ∆(S) and an observation function I θ : S → O.In a multi-agent setting, n agents make decisions simultaneously. At each step, agent i chooses an action a i , forming a joint action a = {a 1 , . . . , a n } that transitions the environment according to P θ . Each agent then receives a reward based on the reward function R : S → R, which may be shared among all agents or be agent-specific.UED is an autocurricula paradigm that frames curriculum design as a two-player zero-sum game between a level-generating adversary and an agent. The agent seeks to maximise its expected return in the standard RL manner, while the adversary can pursue various objectives. Domain Randomisation (DR) fits within this framework by assigning a constant utility to each level, reducing level generation to mere random sampling [11] . Worst-case methods, on the other hand, incentivise the adversary to minimise the agent's reward, aiming to enhance performance on the most challenging levels [14] . However, this approach often results in the generation of unsolvable levels [3] .Regret-based UED methods offer an alternative by generating levels that maximise the agent's regret.Here, the regret of a policy π on a level θ is defined as the difference between the policy's discounted return on θ and the optimal return achievable on that level, expressed as U (π ⋆ θ ) -U (π), where U denotes the policy's discounted return and π ⋆ θ is the optimal policy on θ. This approach deprioritises unsolvable levels and should, in theory, generate levels on which the agent can continue to improve. Moreover, using regret as the adversary's objective provides additional theoretical benefits. At the convergence of the two-player zero-sum game, the agent's policy enjoys minimax regret robustness, meaning that the maximum regret over the entire level space Θ is bounded [3] . However, computing regret in complex settings is intractable because it requires access to the optimal policy for each level. As a result, current UED methods rely on heuristic score functions that aim to approximate regret. The two most commonly used heuristic approaches are Positive Value Loss (PVL) and Maximum Monte Carlo (MaxMC).Positive Value Loss (PVL). PVL approximates regret as the average of the value loss across all timesteps where it is positive. When using GAE [15] (as in PPO [16] ), PVL can be written as follows:PVL = 1 T T t=0 max T k=t (γλ) k-t δ k , 0 ,where γ is the discount factor, λ is the GAE coefficient and T is the length of the episode. δ t is the TD-error at timestep t, defined as δ t =R t + γV (o t+1 ) -V (o t ), with V denoting the agent's value function, corresponding to the discounted return by following π from o t .Maximum Monte Carlo (MaxMC). Instead of using the bootstrapped value target, MaxMC instead uses the highest return obtained on a particular level:MaxMC = 1 T T t=0 (R max -V (o t )) .Prioritised Level Replay (PLR) [4, 9] involves two key steps: generating random levels and replaying levels from a buffer. Initially, random levels are created, and the agent is evaluated on them, with each level being assigned a score. High-scoring levels are then added to a buffer. Subsequently, levels are sampled from this buffer based on their score and the time elapsed since their last selection, and the agent is trained on these sampled levels. PLR has two variants: standard PLR and Robust PLR. In standard PLR, the agent's policy is updated using rollouts from the randomly generated environments, whereas in Robust PLR, the policy is not updated during this phase. ACCEL [5] extends the PLR framework by incorporating a mechanism that randomly mutates previously high-scoring levels, generating new levels that push the agent to the edge of its capabilities. For additional methods, see Section 8, and for a more detailed introduction to ACL, refer to Appendix E.2.3 JaxNav In this section, we first touch on hardware-accelerated environments, and robotic navigation. We then go on to introduce JaxNav, a hardware-accelerated, single and multi-agent robotic navigation environment. While similar on a surface level to Minigrid, JaxNav has several additions that make it closer to real-world robotics environments. 
hardware accelerated environments: 
 Recently, Bradbury et al. [18] released JAX, a Python numpy-like library that allows computations to run natively on accelerators (such as GPUs and TPUs). This has led to an explosion in reinforcementlearning environments being implemented in JAX, leading to the time it takes to train an RL agent being reduced by hundreds or thousands of times [12, [19] [20] [21] . This has enabled researchers to run experiments that used to take weeks in a few hours [22, 23] . One side effect of this, however, is that current UED libraries are written in JAX, meaning they are primarily compatible with the (relatively small) set of JAX environments.Motion planning is a fundamental problem for mobile robotics. The general aim is to find a collisionfree path from a starting location to a goal region in two or three dimensions. We focus specifically on the popular setting of 2D navigation problems for differential drive robots using 2D LiDAR readings as the sensory input for their navigation policies. Given range readings, the robot's current velocity and the direction of its goal, the navigation policy must produce velocity commands to move the robot to its goal location while avoiding static and dynamic obstacles.The observation space of JaxNav is highly partially observable and is based on LiDAR readings, depicted by the blue dots in Figure 1b . This is in contrast to Minigrid, which provides a top-down, ego-centric, image-like observation, as shown by the highlighted region in Figure 1a . Additionally, while Minigrid features discrete forward and turn actions, the robots in JaxNav operate in continuous space using differential drive dynamics. Similar to Minigrid, agents in JaxNav must navigate from a starting location to a goal region, with the goal centre represented by the green cross in Figure 1b .These design choices make JaxNav a close approximation of many real-world robotic navigation tasks [24, 25] , including the ICRA BARN Challenge [26] , which is depicted in Figure 1c . This challenge, which has run annually since 2022, aims to benchmark single-robot navigation policies in constrained environments for differential drive robots using 2D LiDAR as sensory input. Even with a cell size of 1.0 m, JaxNav offers a similar clearance between robots and obstacles as the test maps used in the BARN Challenge, underscoring its relevance not only for evaluating UED methods but also for advancing robotics research. Our environment's full design is outlined in Appendix A. 
understanding and improving level selection in goal directed domains: 
 In this section, we examine current UED methods, and investigate how they select levels to train on.In particular, we investigate how well currently-used score functions correlate with (a) success rate (i.e., the fraction of times the agent solves the level); and (b) learnability (defined below). We then develop a method which directly samples levels according to their learnability potential, with the following sections detailing our experimental setup and results.Similarly to the Goals of Intermediate Difficulty objective proposed by Florensa et al. [1] and the ProCuRL curriculum strategy proposed by Tzannetos et al. [10] , we desire agents to learn on levels that they can solve sometimes but have not yet mastered. Such levels hold the greatest source of possible improvement for an agent's policy and so a successful autocurricula method must be able to find these. Indeed, given a success rate (i.e., the fraction of times the agent solves the level) of p on a given level, we follow Tzannetos et al. [10] and define learnability to be p • (1 -p). In a goal-based setting where there is only a nonzero reward for reaching the goal, we justify this definition as follows:1. p represents how likely the agent is to obtain positive learning experiences from a level, while 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. (c) Learnability (ours)Figure 2 : Our analysis of UED score functions shows that they are not predictive of "learnability".Having defined learnability, we now turn our attention to the current UED score functions. As demonstrated in Section 7, the latest state-of-the-art UED methods fail to outperform Domain Randomisation (DR) in the multi-agent JaxNav environment. To highlight the limitations of these approaches, we examine whether their score functions can reliably identify the frontier of learning, i.e., levels that agents can only sometimes solve.We focus on the single-agent version of JaxNav and conduct rollouts using the top-performing seed for PLR-MaxMC on randomly sampled levels over 5000 timesteps. From these rollouts, we compile a set of 2500 levels, evenly distributed into 10 bins based on mean success rate values ranging from 0 to 1. We then perform additional rollouts on this collected set, running for 512 environment timesteps (the same number as used during training) across 10 parallel workers, and average the results. In Figure 2 , we plot the mean MaxMC, PVL and Learnability scores against the mean success rate for each level. We additionally report the Pearson correlation coefficient, r, and p-value for the linear relationship between the success rate and the regret score.Our analysis reveals no correlation between MaxMC and learnability, and MaxMC instead shows a slight correlation with success rate. While PVL has a weak correlation with learnability, the high variance causes already-solved maps to be prioritised alongside those with high learnability. These plots contrast heavily with that of our learnability metric, which directly prioritises levels with the greatest expected improvement. We hypothesise that the root cause of this issue is the agent's poor value estimation. In a highly partially observable environment, the agent struggles to accurately estimate the value of a state, leading to noisy MaxMC and PVL scores, which in turn hinder UED methods from effectively identifying the learning frontier. Given that reward is strongly correlated with success rate, these findings also apply when comparing scores against reward, as detailed in Appendix F.Following on from our analysis, we now present Sampling For Learnability (SFL), a simple approach that directly chooses levels that optimise learnability. Our approach maintains a buffer of levels with high learnability and trains on a set of levels drawn from this buffer alongside randomly generated levels. Algorithm 1 outlines the overall approach for SFL and illustrates the relative simplicity of our method compared to SoTA UED approaches. The policy's weights ϕ are updated using any RL algorithm; we use PPO [16] for all of our experiments. Meanwhile, our method for collecting learnable levels is detailed in Algorithm 2. We find that the default values of T = 50, ρ = 0.5, N L = 256, L = 2000, N = 5000 and K = 1000 work well across domains. However, the per-environment hyperparameters we use are listed in Appendix C, and Appendix I contains plots showing the effect of changing each of these hyperparameters.Initialize: policy π ϕ , level buffer D while not converged do D ← collect_learnable_levels(π ϕ ) Using Alg. 2 While a key limitation of this approach is the additional timesteps required to form the learnability buffer, we find that due to the speed of forward rollouts on JAX-based environments, this does not dramatically increase our overall compute time, see Appendix H for a more detailed discussion.for t = 1, . . . , T do D t ← ρ • N L levels sampled uniformly from D D t ← D t ∪ (1 -ρ) • N L randomly 
experimental setup: 
 We now outline the domains used along with our adversarial evaluation protocol. Rather than taking the common approach of reporting average performance on a set of hand designed levels (which by their very nature are arbitrary), we sample a large set of levels and examine each method's performance on their worst-case levels. This directly targets the tails of the level distribution and as such is a superior measure of robustness. We further report the comparative performance of methods on the sampled set to determine the degree to which one method dominates another.We use four domains for our experiments, JaxNav in single-agent mode, JaxNav in multi-agent mode, the common UED domain Minigrid [13] and XLand-Minigrid [12] . See Appendix B for more details about the environments. We use 10 seeds for Minigrid and single-agent JaxNav, and 5 seeds for multi-agent JaxNav and XLand-Minigrid. In all of our plots, we report mean and standard error.Since SFL performs more environment rollouts, we perform fewer PPO updates in single-agent JaxNav and XLand-Minigrid to ensure that SFL uses as much compute time as ACCEL. In Minigrid, the additional environment interactions take a negligible amount of time, so we run the same number of PPO updates for all methods. For multi-agent JaxNav, we compare each method using the same number of PPO updates. See Appendix H for more information on the relative speed of each method, and how many updates we run for each method. Generally, the additional SFL rollouts take much less time than the updates themselves, due to the massive parallelisation afforded by hardware-accelerated environments. Additionally, recent work suggests that world-models could also allow more samples to be taken than the base environment allows [27] [28] [29] [30] , highlighting the future potential of this approach.We compare against several state-of-the-art UED methods as baselines, implemented with JaxUED [22] . We use ACCEL, with the MaxMC score function, where the agent trains on randomly generated, mutated and curated levels. We also include a "robust" version [4] , where no gradient updates are performed on the former two sets of levels. This uses three times as many environment interactions and is roughly twice as slow as SFL for single-agent JaxNav. We use PLR with both the PVL and MaxMC score functions. We also include a robust version of PLR which only performs gradient updates on the curated levels; this uses twice as many environment interactions and is 80% slower than SFL on single-agent JaxNav. We also use Domain Randomisation (DR), which trains only on randomly generated levels, with no curation or prioritisation. 
a risk-based evaluation protocol: 
 The standard approach to evaluating UED agents is to test them on a set of hand-designed holdout levels [3] [4] [5] . Whilst this evaluation approach illustrates the performance of agents on human-relevant tasks, we believe it has several limitations. First, the hand-designed levels are arbitrary, so performance on them is not representative of general performance; second, it does not test a central claim of UED: that it trains agents which are robust to worst-case (yet solvable) environments. To address this, we propose a novel evaluation protocol that rectifies both of these problems: measuring the conditional value at risk (CVaR) of the success of the trained agent on a set of sampled levels.To calculate the CVaR we sample N (10, 000 in practice) random, but solvable,2 levels and rollout the agent policy for 10 episodes on each level. We then find the α% of levels on which the agent performs worst. To mitigate bias, we rollout the agent again on these levels, and report the average success rate on this α% subset, i.e., the CVaR at level α. This metric directly quantifies the performance of a training method on its own worst-case levels, which measures its ability to produce robust agents. We perform this computation for each seed, and report the mean and standard error over seeds, at various α levels. We further use the N sampled levels to calculate the following metrics.Mean Success Rate We average the success of each method over all N levels and then report this as the mean success rate and its standard error over multiple independent seeds. Due to space requirements, these results are included in Appendix G.To identify the degree to which one method dominates another, we obtain the average solve rate of each method (averaging over seeds) per environment. We then plot a heatmap, where cell (x, y) contains the number of levels method A solves x% of the time while method B solves them y% of the time. This metric measures how many environments one method strictly solves more often than another. 
single-agent jaxnav: 
 Figure 3a shows the CVaR results on single-agent JaxNav. We find that optimising for learnabilityas our method does-results in superior robustness over a wide range of α values, despite all methods performing similarly with α = 100% (which amounts to expected success rate over the entire distribution). In this plot, we also plot the results of an oracle method named Perfect Regret. This uses the same procedure as SFL but with the score function: 1 -p(success). Importantly (and different to all other methods), this method only samples solvable levels, so this metric corresponds closely to regret. While not shown here, using the same metric with unrestricted level sampling-which is a more realistic setting-performs poorly due to it prioritising unsolvable levels. In Figure 4 , we perform pairwise comparisons of each baseline against our approach. We find that there are a large number of environments that all methods solve (the bright top-right corner). However, the bottomright is generally brighter than the top-left, indicating that SFL performs better in general. Overall, SFL's superiority, and Perfect Regret's strong performance, indicates that the flawed approximations of regret are responsible for UED's lack of performance. We provide further evidence for this claim in Appendix I.2, where we use learnability as a score function within PLR and ACCEL. n i=1 (p i • (1 -p i )), where p i is the success rate for agent i on on a given level. We find that JaxNav significantly outperforms all UED methods. SFL outperforms all UED baselines in each of these. We do not include oracle regret, since it cannot be easily measured in this setting.We next move on to the standard domain of Minigrid (see Figure 7 ). Here we find that most methods perform similarly on the hand-designed test set; however, SFL significantly outperforms all other methods on the adversarial evaluation, indicating it results in more robust policies. Our final evaluation domain is XLand-Minigrid's [12] meta-RL task using their high-3m benchmark. We report performance using our CVaR evaluation procedure and, in line with [12] , as the mean return on an evaluation set during training. Our results are presented in Figure 8 , with SFL outperforming both PLR and DR. During evaluation each ruleset was rolled out for 10 episodes. Due to the large number of levels being rolled out to fill SFL's buffer, SFL was slower than DR and PLR. As such, we report results for SFL compute-time matched to PLR.  
related work: 
 Unsupervised Environment Design (UED) has emerged as a prominent method in the ACL field, promising robust agent training through adaptive curricula. Early works focused on learning potential, where the improvement in an agent's performance determined the choice of training levels [1, 2, 31, 32] . However, robustness-oriented methods such as adversarial minimax introduced the notion of training on levels that minimise agent performance, though these often resulted in infeasible scenarios offering no learning benefits [3, 14, 33] . Minimax regret (MMR), a more refined robustness approach, alleviates some of these issues by ensuring the chosen levels are learnable [3] [4] [5] . However, recent work [8] demonstrated that even true regret does not always correspond to learnability, and this mismatch can lead to stagnation during training. Our work extends this line of research by utilising a scoring mechanism that estimates expected improvement, targeting environments with a positive but not perfect solve rate. Unlike existing MMR methods, our approach directly optimises for learnability, instead of using an imperfect proxy for regret, leading to more effective training on our domains.Relatedly, Tzannetos et al. [10] introduce ProCuRL, which uses a similar learnability score as SFL (and further introduce an approximation to the solve rate p using the agent's value function). However, their problem setting is distinct from ours as they assume only a limited fixed pool of tasks are utilised during training, with the goal of improving an agent's performance over a uniform distribution over this pool. We, instead, consider the standard UED setting where we can sample an effectively unbounded number of tasks from some large distribution Θ, with the goal of achieving an agent that is robust to worst-case settings and can generalise to unseen problems. Following on from this, Tzannetos et al. [34] extend ProCuRL to the setting where the target distribution of tasks is given, and they take into account both how learnable the selected task is, as well as how correlated it is with learnable tasks from the target distribution. While this approach outperforms the original method, it tackles a different problem to SFL and UED in general, i.e., where the target distribution is known.Finally, robust RL methods have the goal of improving an agent's robustness to environmental disturbances, and worst-case environment dynamics [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] . However, these methods generally consider continuous perturbations instead of a mix of discrete and continuous environment settings. Furthermore, these methods tend to be overly conservative and prioritise unsolvable levels. 
discussion and limitations: 
 In this work we only consider deterministic, binary outcome domains and due to the nature of the learnability score, SFL is only applicable to such settings. In other domains, we could potentially reuse the intuition that p(1-p) is the variance of a Bernoulli distribution; in a continuous domain, an analogous metric would be the variance of rewards obtained by playing the same level multiple times. Furthermore, our implementation of SFL is in JAX but the method is general. However, 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. Next, while most current SoTA UED methods, including SFL, randomly generate and curate levels, this approach may become infeasible when the environment space is vast, as random generation may have a very low likelihood of generating valid levels. Finally, while JaxNav does have deterministic dynamics, Fan et al. [48] successfully transferred an RL-based multi-robot navigation policy from a simulator of identical fidelity to the real world, suggesting this should be equally possible with JaxNav. 
conclusion: 
 In this paper, we investigate the scoring functions used by current regret-based UED methods and analyse whether they can accurately approximate regret. We find that this is not the case and that these prioritisation metrics instead correlate with success rate, leading to a large amount of experience not contributing to learning an improved policy. Inspired by this analysis, we develop a method based on an intuitive notion of learnability and find that this improves the robustness of the final policies. We also introduce a new robustness-measuring evaluation protocol, reporting a risk measure on performance over the α% worst-case (but solvable) levels for each method. We hope that our findings inspire future work on more general, domain-agnostic scoring functions, and we open-source all of our code to facilitate this process. Ultimately, we believe this work is a stepping stone towards bridging the gap between popular testbeds for UED and real-world applications. 
 
 Appendix: Here we describe the other environments we use, with environment parameters listed in Tables 1 to 3 . Minigrid is a goal-oriented grid world where a triangle-like agent must navigate a 2D maze. As illustrated in Figure 1a , the agent only observes a small region in front of where it is facing and must explore the world to move to a goal location.This domain combines an XLand-inspired system of extensible rules and goals with a Minigridinspired goal-oriented grid world to create a domain with a diverse distribution of tasks. Each task is specified by a ruleset, which combines rules for environment interactions with a goal, and [12] provide a database of presampled rulesets for use during training. Following [12] , we use a 13x13 grid with 4 rooms and sample rulesets from their high diversity benchmark with 3 million unique tasks.As training involves sampling from a database of precomputed rulesets, ACCEL is not applicable. PLR and SFL select rulesets for each meta-RL step to maximise return on a held-out set of evaluation rulesets.Table 4 contains the hyperparameters we use, with their selection process for each domain outlined below. We tuned PPO for DR for each domain and then used these same PPO parameters for all methods, tuning only UED-specific parameters. For PPO, we conducted an extensive sweep on the JaxNav environment ensuring robust DR performance. We only tuned hyperparameters for single-agent JaxNav, and used the best hyperparameters for multi-agent JaxNav. JaxNav hyperparameter searches were done over 3 seeds.For PLR, we performed a grid search, over replay probabilities {0.5, 0.8}, buffer capacity {1000, 4000, 8000}, prioritisation {rank, topk}, temperature {0.3, 1.0}, and k {1, 32, 128}. For ACCEL, we searched over the same set and additionally included the number of edits, where we considered values of {5, 20, 50}.For SFL, we performed line searches over N of {500, 5000, 25000}, L {1000, 2000, 4000}, K of {100, 1000, 5000}, T of {10, 50, 500, 1000, 2000} and ρ of {0.25, 0.5, 0.75, 1.0}.Since this is a line search and not a grid search, the total number of tuning runs (and total compute) is less than for PLR and ACCEL (60 runs for SFL vs 90 for PLR and 270 for ACCEL).For Minigrid, our JaxNav PPO parameters performed similarly to those given in the JaxUED implementation but allowed us to use 256 environment rollouts in parallel during training compared to JaxUED's 32. For the UED-specific parameters we used the same sweep settings as for JaxNav, again conducting the search over 3 seeds.For PPO, we used the default parameters provided by [12] and the search for UED parameters was conducted over 1 seed. For PLR, we conducted a grid search over replay probabilities {0. The hand-designed levels used for evaluating policy performance throughout training are illustrated in Figures 9 and 10 . The set used for multi-agent policies also includes the first 3 maps in Figure 9 .Minigrid's levels are shown in Figure 11 and are the same as those used by JaxUED. Multi-robot path planning presents unique challenges due to the need for coordination among robots to avoid deadlocks in dynamic environments. Traditional methods often discretise the environment, turning the problem into a multi-agent pathfinding task managed by a central planner [51, 52] . While effective at scale, these approaches rely heavily on communication infrastructure, making them impractical in scenarios with unreliable connectivity or third-party obstacles. In contrast, our method leverages decentralised learning approaches without relying on centralised communication, making it more robust in partially observable and communication-limited settings.Decentralised approaches like velocity obstacles [53] and ORCA [54] offer a solution by mapping environmental constraints into the robot's velocity space. However, these methods are susceptible to measurement errors and often exhibit short-sighted behavior, limiting their real-world applicability [17] . Our method, by comparison, incorporates a broader evaluation framework that assesses performance in adversarial and challenging environments, ensuring robustness beyond simple dynamic obstacle avoidance.Recent advancements leverage machine learning to overcome these limitations. CADRL [55] uses RL to address short-sightedness, but its state-based representation limits its adaptability. Our approach, instead, employs lidar-based observations to model a more realistic and complex navigation task, which allows for better generalisation to real-world scenarios.More sophisticated RL-based approaches, such as those by Long et al. [50] and Tan et al. [56] , demonstrate improved performance in open spaces but struggle in constrained settings. Our method specifically addresses this by focusing on environments that are solved intermittently, thereby enhancing the agent's ability to learn in varied and complex settings.Hybrid methods, combining RL with conventional planning [48] , show promise but do not fully address these challenges. In contrast, our method integrates an adaptive curriculum that dynamically adjusts based on the agent's performance, leading to sustained learning improvements even in diverse and adversarial environments.The design of reward functions is critical in RL-based navigation. Enhancements using velocity obstacles [17, 57] improve performance but still face challenges in real-world transferability. Techniques like perceptual hallucination [58] further enhance robustness by reducing multi-robot planning to static obstacle avoidance, though they typically consider simple scenarios and do not account for dynamic third-party obstacles. Our method, however, introduces a novel evaluation protocol that rigorously tests the robustness of learned policies in a variety of adversarially generated environments, ensuring better real-world applicability.Automated Curriculum Learning (ACL) is a subfield of RL where agents are presented with increasingly challenging tasks that are adapted to the agent's current progress [59, 60] . One common idea idea is to train the agent on tasks that are neither too easy nor too hard, such that it achieves maximum learning potential [1, 61] . Autocurricula methods have various aims, such as improving learning speed on a set of target environments [62] or increasing robustness to unknown environment configurations [3, 4] . Unsupervised environment design (UED) focuses on the latter. One commonality between autocurricula methods is that the environment generator controls aspects of the environment, such as the transition dynamics, state and observation spaces, goals, and so on [1, 3] . Each of these environment configurations is commonly referred to as a level [3] .Methods also differ in how they generate these environment configurations. One class of methods uses generative models, such as Gaussian Mixture Models (GMMs) [2] . While this approach generally makes the problem theoretically tractable, GMMs are limited to continuous-valued parameter settings. More recently, other generative models, such as Variational Autoencoders, have been used [62] . However, these models often require data to train, which may be unavailable or bias the learning process. Other methods use an RL-based level generator, where the generator's objective is based on how the agent performs on the generated level [3] . This approach has been surpassed by the more recent technique of randomly generating and curating levels [4, 5, 9] .An extension of Section 4.2, Figure 12 illustrates the correlation between mean reward and the two most popular regret scores, MaxMC and PVL. These graphs illustrate that the trends seen for success rate also hold for episodic reward, this is expected for our environment as the two are strongly correlated. In Figure 13 we conduct the same analysis for the L1 Loss Score [9] , defined as: L1 Loss = 1 T T t=0 T k=t (γλ) k-t δ k .Figure 14 shows each method's overall solve rate on the set of 10000 sampled solvable levels on a log scale. We find that while all methods solve the vast majority of levels, SFL slightly outperforms all the baseline methods. Figure 15 reports the pairwise comparisons of each base against SFL for Minigrid. While, again, most methods solve most levels, SFL has a slight advantage. Figure 16 shows episodic return and success rate plots for single-agent JaxNav and Minigrid. We find that the episodic return is very strongly correlated with the success rate, which is why we primarily show the latter in the main text.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 ≤ 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 17 On JaxNav, SFL still demonstrates a significant performance increase while on Minigrid all methods are very similar (with the robust methods performing slightly better for low values of α). Due to the challenging dynamics of JaxNav, even levels with a small number of obstacles can present difficult control and navigation problems meaning 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.Table 5 shows the mean and median of learnability and success rate for a variety of methods. We find that the average learnability of levels in the PLR/ACCEL buffers is very low. While not shown For single-agent JaxNav, we plot the shortest path length, number of walls and the solvability of levels in the PLR/SFL buffers in Figure 18 . We find that SFL has marginally longer shortest paths and marginally fewer walls. The SFL levels are also considerably more solvable.Aside from solvability, there is not a large difference in these metrics between PLR and SFL, despite SFL significantly outperforming PLR. Qualitatively, we find that in JaxNav, levels with high learnability tend to involve a lot of turning and intricate obstacle avoidance (as opposed to long paths).As such, the number of walls and shortest path length do not fully capture a level's difficulty. For XLand-Minigrid, we report the mean number of rules for the PLR/SFL buffer rulesets in Figure 19 , which illustrates a significant difference in the rulesets seen by the different agents. SFL samples well below the mean value throughout training, whereas PLR starts on par with DR before tending easier as training progresses. This result, coupled with the performance difference, illustrates how SFL's learnability score allows it to find the frontier of learning, leading to more robust agents. Here we plot some generated levels for single-agent JaxNav in Figure 20 , multi-agent JaxNav in Figure 21 and Minigrid in Figure 22 . Overall, ACCEL tends to have the most walls, since its mutation operator is able to add more walls over time. Despite this, the levels do not involve a large amount of complicated turning and maneuvering. The levels selected by SFL, on the other hand, tend to involve going around many corners, which is an important part of JaxNav. In multi-agent JaxNav, SFL occasionally generates levels where not all of the agents can reach their goals; however, these are still useful to learn on, as the other agents can complete their tasks.For completeness, we include levels from XLand in Figure 23 but, unlike the other domains, it is difficult to assess a level's difficulty solely from a render. ACCEL PLR DR SFLTables 6 and 7 report compute time for all methods on single-agent JaxNav and Minigrid, respectively. Each individual seed was each run on 1 Nvidia L40s using a server which has 8 NVIDIA L40s', two AMD EPYC 9554 processors (128 cores in total) and 768GB of RAM. These times are without logging, and we find that with logging, SFL is around 6% slower than ACCEL on single-agent JaxNav. Therefore, for the results in Figure 17b , we use 6% fewer environment steps for SFL to ensure a fair comparison. For Minigrid, SFL is as fast or slightly faster than the other methods. As this is surprising (since SFL performs significantly more environment rollouts), we investigate this further. In Table 8 , we compare the time it takes for a single iteration (including training and evaluation) in Minigrid on an L40s GPU.We note that the SFL rollouts are fast for two reasons:1. We aggressively parallelise them, running up to 25, 000 environments in parallel, which takes about the same time as running only hundreds in parallel.2. We do not compute any gradients for these transitions.The effect of this is that these additional rollouts 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.The multi-agent results were run on a variety of machines, including the aforementioned L40s system, a similar system featuring NVIDIA A40's and a workstation containing 2 RTX 4090's. On a 4090, a SFL run takes 1d 1h 13m 54s while ACCEL takes 18h 17m 26s.All XLand-Minigrid experiments were run on 1 Nvidia L40s, with the same server specification as mentioned above. Table 9 reports the compute time for all methods; these times are with logging where each method logs the same data. Note that SFL was compute-time matched to PLR for this environment. This section of our appendix focuses on running ablations for SFL, investigating the effect of hyperparameters in Appendix I.1, using learnability as a score function in UED in Appendix I.2, and other definitions of learnability in Appendix I.3In this section we investigate the effects of SFL's hyperparameters. For computational reasons, we run these ablation experiments over three seeds; furthermore, we consider only JaxNav's single agent setting. Our results, for single-agent JaxNav and Minigrid, respectively, are shown in Figures 24 and 25 , with the effects of the hyperparameters as follows:Number of Sampled Levels N Sampling more levels results in improved performance, but increases computation time.Rollout Length L For JaxNav, there is a small reduction in performance by using a rollout length of 1000, but no gain from using 4000 compared to 2000. In Minigrid, all values perform roughly the same, possibly due to the shorter episodes.Buffer Size K In JaxNav, a smaller buffer outperforms larger ones, whereas in Minigrid, there is no significant difference between K = 100 and K = 1000. This could relate to how easy the environment is (corresponding to how long it takes to learn a particular level). As JaxNav is harder than Minigrid (as it also involves low-level continuous control obstacle avoidance in addition to maze solving), it may be that training on each level more times is beneficial.Buffer Update Period T Increasing the time between updating the set of training levels reduces performance. However, sampling more often increases the computational load of the additional SFL rollouts.Sampled Ratio ρ In JaxNav, a higher sampling ratio seems preferable, similarly to the "robust" version of PLR [4] . In Minigrid, however, using ρ = 0.5 performs slightly better than ρ = 1.Sampling in decreasing order of learnability For JaxNav, we trialled selecting levels in decreasing order of learnability rather than randomly among the top K. This performs better, and 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. We now apply our learnability metric as a score function for UED. In particular, when performing our DR rollouts, we compute the learnability as in Section 4.3 and use that as the score function.Figure 26 shows these results; Learnability improves performance compared to MaxMC, supporting our claim that the score function is the primary limitation of current UED methods. a, c ), the large buffer is of size 1000 while the small is of size 100. We find that SFL with learnability outperforms all other combinations.In this section, we investigate alternative definitions of learnability. All of the following functions have a learnability value of 0 for a success rate of 0.0 and 1.0, but differ in how scores are assigned to intermediate success rates p. We aim to assess whether our learnability score's main contribution is, in fact, just excluding unsolvable and perfected levels; our analysis indicates that this is not the case.First, on JaxNav, we investigate the case where the peak learnability is not at p = 0.5, but at other values. To do this, we represent the learnability function as a piecewise quadratic, see Figure 27a for an illustration. 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 27b , and we find that a peak of 0.6 performs the best, and that performance slightly degrades as the peak moves towards higher success rates. In particular, performance is poor when the peak is at p = 0.99.In Figures 27c and 27d , we consider other definitions of learnability on JaxNav and XLand. We keep the restriction that learnability equals zero when p = 0 or p = 1. The first is Uniform, where all levels with success rates 0 < p < 1 are assigned an equal score. Linear(0) has learnability linearly increasing from 1.0 to 0.0, and Linear(1) has learnability linearly increasing from 0.0 to 1.0.We find that Linear(0) (which is an approximation of true regret) performs similarly to the default definition of learnability on JaxNav but struggles on XLand. Meanwhile, Uniform sampling performs worse than our approach but still outperforms all UED methods on JaxNav and XLand (albeit by a smaller margin than SFL). Finally, Linear(1) performs significantly worse on JaxNav but is the closest to SFL's performance on XLand. These results indicate that our chosen definition of the learnability score function is more robust than these alternatives across different domains. Solvable means that the goal state can be reached in a particular level, i.e., it is not impossible to complete. 


Decision: This paper introduces a novel metric for evaluating the learning potential of tasks in a multi-task RL environment. It also proposes a new evaluation protocol to better characterize the robustness of different methods, and compares its proposed method with several Unsupervised Environment Design baselines using this protocol. This paper shows that its proposed method outperforms the baselines.

This paper is very interesting and I believe that many researchers in the field of RL will find this paper important. All the reviewers recommend to accept this paper, and three reviewers have given a rating of 7. After reading the paper, the reviews, and the rebuttals, I agree with the reviewers and recommend to accept this paper.

Reviews: review: paper_summary: paper_summary: The paper introduces a new metric based on solve rates for evaluating the learning potential of tasks in a multi-task RL environment. It also presents a new evaluation protocol based on worst-case performance to better characterize the robustness of different methods. The work uses this protocol to compare their method with several Unsupervised Environment Design baselines and concludes that it outperforms the baseline. They also find that their UED baselines perform worse than Domain Randomization on this new evaluation metric, and conduct additional experiments to confirm and analyze these results.
strength_weakness: strength_weakness: The main weakness of the paper is the claim that domain randomization and their new heuristic outperform all UED algorithms, which is not entirely convincing from the results. The PLR hyperparameters used in this work are different from [1] and [2], for example the prioritization, temperature, and number of edits are all different. PLR in particular has several hyperparameters that need to be tuned for new domains, such as the buffer size, sampling temperature, and staleness coefficient. The authors do not explain whether they tuned the hyperparameters for the baselines or how they tuned the hyperparameters for their own method. I think even a small grid search over reasonable parameters that worked in other domains would help to make the comparisons throughout this paper more convincing.

Another concern is that this work does not include any standard episodic return plots, which is the main metric of comparison in RL. Without these plots, it is difficult to tell whether their method truly outperforms the baselines, or whether their baselines are properly tuned. For instance, if the SFL algorithm performs better according to the CVaR evaluation but not on a standard test return plot, then it's debatable which method is more useful. That being said, [2] does compare the mean evaluation solve rate of UED baselines on Minigrid, and finds that Accel and PLR both significantly outperform DR. In this work, PLR severely underperforms DR using the same metric in Figure 3. This seems to be strong evidence that its hyperparameters or implementation are not correct.

Even if we assume that the baselines are working as intended, I PLR and SFL have many differences which makes it unclear what change is actually leading to better performance. I think this work would benefit from additional experiments using the learnability metric in SFL as the prioritization metric in PLR, and possibly the alternative, using PVL and MaxMC as the selection metrics in the full SFL algorithm.

Overall the writing and presentation was quite good, but there were a few notable issues. The paper somewhat confounds its description of PLR with Robust PLR in section 2.2.1. PLR trains on randomly sampled levels, while Robust PLR evaluates randomly sampled levels and only trains on levels from its replay buffer. Also, "learnability" is not clearly defined until 4.2, after it has been referenced many times. This is ok when discussing "intuitive notions of learnability" in a vague sense, but not when making statements such as "no correlation exists between learnability and regret score".

[1] Jiang, Minqi, et al. "Replay-guided adversarial environment design." Advances in Neural Information Processing Systems 34 (2021): 1884-1897.
[2] Parker-Holder, Jack, et al. "Evolving curricula with regret-based environment design." International Conference on Machine Learning. PMLR, 2022.
questions: questions: * Why did you not simply use your heuristic instead of PVL or MaxMC in prioritized level replay?
* Why does there appear to be a discrepancy between the UED baseline solve rates reported in this paper and the ones reported in [2]?
* On line 214 you describe sampling 10,000 solvable levels to evaluate on. Are these unseen levels (at least with high probability) or are they sampled from the training set?
* You mention in the Limitations section that your method is restricted to Jax-based settings. Is the method limited to those settings, or just your particular Jax-based implementation?
limitations: limitations: The authors adequately discuss the limitations in the paper and throughout the work. Their SFL method appears to be less general that the UED baselines that they compare against, but performs much better on the domains tested in this work. Simple methods on new benchmarks can serve as stepping stones to more general methods, so I do not believe this impacts their contribution.
paper_summary: paper_summary: This work proposes a new Unsupervised Environment Design (UED) method, called Sampling for Learnability (SFL), developed for navigation tasks. SFL upsamples environment configurations with high learnability scores, i.e., p*(1-p), where p is the success rate in a specific configuration. The paper highlights the failure of some of the state-of-the-art (SOTA) UED approaches on such tasks and argues that they cannot approximate learning agents' regret, unlike SFL. They evaluate SFL in JaxNav, a Jax-based single and multi-agent navigation benchmark they introduce, and MiniGrid. Their empirical results evidence that SFL is robust and can outperform Domain Randomisation (DS) and SoTA UED approaches in JaxNav and MiniGrid. The paper demonstrates these outcomes by following two evaluation protocols, respectively: 1) A risk-based protocol that they introduce, computing the conditional value-at-risk (CVaR) of the distribution of success rate based on randomly sampled levels, and 2) a common protocol in the UED literature that evaluates performance/success in hand-designed test sets, as they focus on complex, yet, solvable configurations.
strength_weakness: strength_weakness: - 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.

- The empirical results according to the proposed evaluation protocol for robustness (Figures 3a, 5a, and 7a) show that SFL outperforms the rest of the evaluated methods for alpha < 1 (100%). However, except in the multi-agent case (Fig 5a), the expected success rates indicate marginal or no improvement. In MiniGrid, the difference between DR and SFL drops quickly as alpha gets above 0.1 (10%). This is likely due to SFL not doing so well in easier levels compared to other baselines. Although this is expected, as the proposed metric results in upsampling learnable environments, not easy ones, I suggest a comparison of results in easy levels to conclude whether this is the case or not.
questions: questions: Table 4 showcases compute times for each evaluated approach. Most of these approaches have similar components, except maybe SFL's extra rollout phase. So why is SFL one of the fastest?
limitations: limitations: - The major limitation of the proposed approach is the rollouts needed to compute the learnability score of randomly sampled levels. Section 4.2 indicates that 5000 levels are sampled, and n-step rollouts, where n is not specified, are generated to compute the scores. It would be more informative if the amount of computation and time spent in this phase were reported (in comparison to the usual curriculum learning task sampling phase). In addition, I wonder how SFL is one of the fastest in the single agent nav environment, as reported in Table 4 in Appendix F, despite having this additional phase.
paper_summary: paper_summary: This experimental paper proposes a UED method (SFL) for JaxNav, a continuous single- and multi-robot navigation task in a partially observable setting.  The authors document the shortcomings of UED methods, (Domain Randomisation, Prioritised Level Replay, and ACCEL) on this partially observed, continuous action, continuous state setting.  The authors provide a demonstration that the scoring mechanism used by the above UED methods is misguided.  Their method, SFL, uses a “learnability score” which focuses learning on levels for which agents achieve success rates closer to 50%.   To better focus on robustness and generalization, the authors develop an empirical CvaR measure of success for evaluation and comparison of methods.
strength_weakness: strength_weakness: See questions below.
questions: questions: 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!

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.

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).

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

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

Line 274-5.  Unclear what “perfect regret” means.
limitations: limitations: Limitations are nicely discussed.  It would be cool if the authors could comment on how SFL might be generalized to continuous outcomes and stochastic environments.
paper_summary: paper_summary: The paper investigates the limitations of popular UED approaches, such as PLR and ACCEL, demonstrating that they do not improve upon the Domain Randomisation baselines, where levels are randomly sampled. The author's main claim is that learnability does not correlate with the scoring functions MaxMC and PVL used by current UED approaches, leading to sub-optimal performance.

To address this issue, they propose Sampling For Learnability (SFL), a simple algorithm where levels are chosen to prioritize learnability. In the context of the paper, the learnability of a level is defined as $p \cdot (1-p)$, where p is the success rate of the agent on that given level.
The authors conduct experiments on three different environments: MiniGrid, Single, and Multi-Agent JaxNav. As a metric, they propose the use of the conditional value at risk (CVaR), evaluating on an α% of levels on which the agent performs worst, from a randomly generated buffer of levels.

The results show that SFL outperforms current UED approaches. Simultaneously, when it is possible to compute it, true regret outperforms SFL, indicating that the flaw of UED algorithms is indeed in the scoring function approximation. To summarize, the main contributions of the authors are:

- Demonstrate sub-optimality of current UED approaches, due to lack of correlation between their scoring function and learnability
- Propose a new algorithm, SFL, which prioritizes levels with high learnability
strength_weakness: strength_weakness: - Learnability definition: why are environments that are solved exactly half of the time the most valuable ( given the $p(1-p)$ function used to define it)? It seems an arbitrary choice, which should need to be justified better through additional experiments. I do not agree that levels that are solved 5% of the time are as valuable as ones solved 95% for example.

- Many parameter choices are just reported with no justification supporting it ( e.g. hyperparameter $\rho$ for the algorithm)

- Experiments are poor in broadness. Given the purely empirical nature of the paper, I would expect way more experiments to indeed show that SFL outperforms the UED baselines. This includes more seed for the Multi-agent JaxNav, and more environments. As of now, it is not possible to actually confirm that SFL is indeed better than UED algorithms.

- The writing is poor and sometimes confusing. Learnability is referenced way before being formally defined, the syntax of some sentences is poor, etc... By reading the paper, it seems the writing has been rushed.
questions: questions: - In Algorithm 1, $\rho$ is set to $0.5$. Hence, half of the levels used for updating the policy $\pi_\phi$ are ones with high learnability, and half are sampled at random. Why do not set $\rho$ to a higher value? I would like to see a plot showing the performance of SFL upon varying $\rho$, so as to have a better idea of how indeed training in 'more learnable' environments correlates with better performances

- In Alg.1, what are the performances if instead of sampling uniformly from the high-learnable levels $\mathcal{D}$, you select levels in decreasing order of learnability? 

- What is the average/median learnability of the randomly created levels in Alg 2? What about the top-K ones? It is important to see and report it so indeed one is sure that the levels you are using are indeed ones with high-learnability. As far as I can infer from the paper, it could still be that most of the randomly created levels have low learnability.

- Can you provide more details on what you did to make current UED methods work better? The poor performance of UED algorithms was already highlighted in the JAXUED paper, but I am not sure if this is just because they were not optimized fully, e.g. via a more extensive hyper-parameter search

- Did you try using different definitions of Learnability? How did they perform?
limitations: limitations: No ethical limitations

Comments: title: Response to ycoo
Response to authors
Response 2/2
Response 1/2
Re: Rebuttal by Authors
Thanks for the answer
Thanks
comment: I’d like to thank the authors for their very thorough response and comprehensive additional experiments, as well as apologize for not responding sooner.

Thank you for performing a more thorough hyperparameter sweep, and for pointing out the difference in minigrid block budgets from prior work. After looking through JaxUED and Robust PLR again, I agree with the authors that UED is comparable to DR in the 50 and 60 block setting. That being said, I think the authors should also experiment in the more challenging 25 block setting where UED methods are most effective. Regardless, these new results provide convincing evidence that the proposed method is better than the SOTA in at least some settings.

Than you also for running the requested ablations so quickly. The results seem inconsistent across hyperparameters and environments, but it does appear that SFL is generally better, and both the sampling and prioritization metrics positively impact performance.

My main concern was that there seemed to be strong evidence that the evaluations in the paper were not fair. With these extensive new results and changes, I believe the contribution of this work is convincing, and I hope the authors will incorporate these new results in their paper as promised. I will raise my score to a 7.
Dear Reviewer,

Thank you for your timely response to our comments. We believe we have addressed the concerns you have raised in detail, including through additional experiments which confirm and strengthen our original findings. We also appreciate the increase in your score but were hoping for more significant support given your positive response.
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
# Justification for SFL & Different Definitions of Learnability
We believe the intuition for learnability is simple, easy to understand, and our score function works well empirically compared to prior approaches. However, we are not claiming that learnability is the be-all and end-all for score functions; we fully agree that there may be other variations of it that could perform better, and we are glad the reviewer raised this important point for future work.

Furthermore, we would like to point out that the regret approximations used in current UED methods (e.g., MaxMC and PVL) are not particularly principled and are at best a loose approximation to regret. Indeed, in [1], six possible functions are trialled with their final choice based solely on empirical results. Prior work has also not investigated how closely these metrics correlate to true regret, and recent work has not investigated any alternatives to PVL and MaxMC.

Further justification for our score function is presented below in three parts:

**First, we wish to emphasise that our learnability definition is deeply connected to a large body of prior work in learning theory and curriculum development.** Intuitively, many curriculum methods (including SFL) aim to obtain experiences within the agent's "zone of proximal development", i.e., those that are neither too easy nor too hard [2].

Works such as [3] use hardcoded reward thresholds to define a goal that is of appropriate difficulty. Similarly, POET [4] also uses predefined reward thresholds to filter environments. SFL, meanwhile, directly uses the success rate of the agent on the level to compute the score.


**Second, we believe our empirical results are a strong justification of SFL**, with the reviewer agreeing that "SFL outperforms UED". We would also note that most prior peer-reviewed work in UED uses two ([5, 6]) or three ([7]) environments, and we have strong empirical results in four.


**Third, we have run several other variations on learnability, all of these assign a level a score of zero when $p=0$ or $p=1$** (in JaxNav):
1. Uniform sampling of levels with $0 < p < 1$.
2. Learnability linearly increasing from $p=1$ to $p=0$.
3. Learnability linearly increasing from $p=0$ to $p=1$.

We find that variation 2. (which is an approximation of true regret) performs similarly to the default definition of learnability.
Variation 1. performs worse than our approach, but still outperforms all UED methods (albeit by a smaller margin than SFL).
Finally, variation 3. performs significantly worse, and we believe this is due to this score function prioritising easy levels, which provide less opportunity for the agent to improve. We will include these results in our updated Appendix.


While we focused on $p(1-p)$, these results (and the previous results with different learnability peaks) show that our method performs robustly under other reasonable learnability estimates, demonstrating the potential of learnability in the UED setting and the robustness of SFL. 
While we agree that the exact choice of learnability metric is still an open question, we believe that all our claims are justified empirically, and our results make an impactful contribution to the UED community.




**References**

[1] Jiang, Minqi, et al. "Prioritized level replay." International Conference on Machine Learning. PMLR, 2021.

[2] L. Vygotsky. Interaction between learning and development. Readings on the Development of Children, pages 34–40, 1978.

[3] Carlos Florensa, David Held, Xinyang Geng, Pieter Abbeel. ICML, 2018

[4] Wang, Rui, et al. "Paired open-ended trailblazer (poet): Endlessly generating increasingly complex and diverse learning environments and their solutions." arXiv preprint arXiv:1901.01753 (2019).

[5] Dennis, Michael, et al. "Emergent complexity and zero-shot transfer via unsupervised environment design." Advances in neural information processing systems 33 (2020): 13049-13061.

[6] Jiang, Minqi, et al. "Replay-guided adversarial environment design." Advances in Neural Information Processing Systems 34 (2021): 1884-1897.

[7] Parker-Holder, Jack, et al. "Evolving curricula with regret-based environment design." International Conference on Machine Learning. PMLR, 2022.



# Conclusion
Once again, we appreciate the reviewer's engagement in the review process, and their helpful suggestions. We believe these results further strengthen our paper.
Dear reviewer, thank you for your response, your continued engagement, and your commitment to improving our paper! Please find our responses below.


# Hyperparameter choices / Ablations
First, as illustrated in Figure 2 in the rebuttal PDF, SFL is robust to all of its hyperparameters, and suboptimal choices do not lead to catastrophic failure.

That being said, the most important hyperparameters are:
- $N$: How many levels to sample. Sampling more levels increases performance, as more levels gives SFL a larger sample to draw high-learnability levels from.
- $K$: Buffer Size. In Jaxnav, we find a small buffer size is beneficial, and in Minigrid it is better to have a slightly larger one. This could relate to how easy the environment is (corresponding to how long it takes to learn a particular level). As JaxNav is harder than Minigrid (as it also involves low-level continuous control obstacle avoidance in addition to maze solving), it may be that training on each level more times is beneficial. By contrast, since Minigrid is easier, the number of episodes required in a level may be much less.
- $T$: The buffer update period. If this value is too large, then performance degrades. This is because the learnability of the buffer, and therefore the usefulness of the levels, decreases as the agent trains on it.


# Writing

We kept the structure of our manuscript largely the same and made several local and low-level writing changes and fixes to ensure the writing flows better. One structural change we did make is to define learnability earlier on, in Section 4.1. We finally also added additional explanations and descriptions based on the reviews by yourself and the other reviewers.

# Different values of the sampling ratio
We agree such a plot would be useful, and will provide one in our revised manuscript. 
Since we are unable to share figures during the discussion period, we report the shortest path, number of walls, and solvability, averaged over training in the table below. 
We find that SFL has marginally longer shortest paths and marginally fewer walls. The SFL levels are also considerably more solvable.

| Method     | Shortest Path (Mean)   | N Walls (Mean)   | Solvable (Mean)   |
|:-----------|:-----------------------|:-----------------|:------------------|
| PLR (PVL)   | 4.74 (0.06)            | 25.59 (0.19)     | 0.89 (0.01)       |
| PLR (MaxMC) | 7.03 (0.49)            | 22.63 (0.21)     | 0.89 (0.02)       |
| SFL        | 8.12 (0.02)            | 21.98 (0.43)     | 1.00  (0.00)       |


Aside from solvability, there is not a noticable difference in these metrics between PLR and SFL, despite SFL significantly outperforming PLR. Qualitatively, we find that in JaxNav, levels with high learnability tend to involve a lot of turning and intricate obstacle avoidance (as opposed to long paths). As such, the number of walls and shortest path length do not fully capture a level's difficulty. We will add illustrative examples of generated levels to our Appendix to demonstrate this point.

# Average vs top-k learnability in UED: 
Thank you for suggesting this experiment, we have run the same analysis for ACCEL and PLR in JaxNav. We further compute the correlation between the score (e.g. MaxMC or PVL) and learnability for all levels in the buffer. We find that:
- **The average learnability of levels in the PLR/ACCEL buffer is very low.** This is also true when selecting only the levels with the top 50 PVL/MaxMC scores.
- There is no significant correlation between PVL/MaxMC and learnability.
- Most of the levels selected by PVL and MaxMC can consistently be solved by the agent.

The table below reports the learnability and success rates for levels within the PLR/ACCEL buffers averaged over training. At each evaluation step, we calculate the average and median values for the entire buffer and then average these values over training. Finally, we report the mean and standard deviation across three different seeds.

| Method       | Learnability (Mean)   | Learnability (Median)   | Success Rate (Mean)   | Success Rate (Median)   |
|:-------------|:----------------------|:------------------------|:-----------------|:-------------------|
| PLR (PVL)     | 0.01 (0.00)           | 0.00 (0.00)             | 0.85 (0.01)      | 0.96 (0.00)        |
| PLR (MaxMC)   | 0.02 (0.00)           | 0.00 (0.00)             | 0.85 (0.03)      | 0.95 (0.04)        |
| ACCEL (MaxMC) | 0.02 (0.00)           | 0.00 (0.00)             | 0.93 (0.01)      | 0.97 (0.02)        |
| ACCEL (PVL)   | 0.01 (0.00)           | 0.00 (0.00)             | 0.94 (0.02)      | 0.97 (0.02)        |


This result further strengthens our findings (shown in Figure 2 of the original manuscript) that current UED score functions do not correspond to learnability. Instead, most levels in the UED buffers can already be solved 100% of the time. By contrast, as shown in our rebuttal, SFL consistently selects levels with high learnability.
Thank you for your effort in responding to my comments and questions and providing new results that support the validity of your work.

 My concerns have been thoroughly addressed, so I'll raise my score from 6 to 7.
Thanks for your detailed answer. I took some more time to think about the points you raised:

**Different Definitions of Learnability**: I see that indeed rejecting impossible or already completely solved level is indeed the biggest factor in increasing performance. I would still argue however that I find the learnability definition not very principled - if what mentioned in the first sentence is true, many other scoring function which do the same in those extreme cases, and which chosoe a better heuristic in the remaining scenarios will outperform SFL. Isn't that the natural thing to try? 

**Hyperparameter choices / Ablations**: Can you clarify the sentence ' we have more insights now into which parameters are most important for SFL'. Which are these hyperameters, and more specifically, why is that the case? 

**More seeds and environments**: Thanks for adding more seeds and an additional environment.

**Writing**: can you provide the most significant changes done to the writing?

**Different values of the sampling ratio**:   You say *increasing makes the agent train on more learnable levels, it may also decrease the diversity of the levels seen by the agent* - do you have any insight on the structure of the levels that are create by SFL, especially when $\rho$ is increased to 1? Many similar plots have been produced by other similar papers, such as Fig. 3 in the ACCEL paper (https://arxiv.org/pdf/2203.01302). 

**Average vs top-k learnability**: You should also compare this with the levels of learnability in the buffers of PLR and ACCEL for example, such as one can have a complete picture of where the advantage by using SFL is coming from.

**What we did to make UED better** and **Different learnability definitions?**: Thanks for your answer

In general, I agree with the authors when saying that SFL outperforms UED method in the environments considered. However, beside the remaining doubts above, I am still on the fence for this work. My main criticism comes from the fact that a new method (SFL) is proposed, but that there is no extensive justification on why this is happening. I believe it would be good to have more insight in the structure of the levels SFL prioritizes, and if there are other gaps SFL is actually filling beside excluding impossible or completely solved levels. Is learnability itself better, or any method which excludes the pathological type of levels I just mentioned would actually perform similarly? I believe this is an important point to address.

Sorry for the delay in the answer, and I understand if you are not able to produce a response in time!
Thanks for your response.  I will hold to the rating of 7.