TRACED: Transition-aware Regret Approximation with Co-learnability for Environment Design
Authors: Geonwoo Cho
Jaegyun Im
Jihwan Lee
Hojun Yi
Sejin Kim
Sundong Kim
Venue: ICLR 2026 Poster (2026)
Keywords: unsupervised environment design
autocurricula
zero-shot coordination
Primary area: reinforcement learning
TL;DR: Introduce a regret‐based curriculum that augments value loss with transition‐prediction loss and a lightweight co‐learnability metric.

Abstract: Generalizing deep reinforcement learning agents to unseen environments remains a significant challenge. One promising solution is Unsupervised Environment Design (UED), a co‑evolutionary framework in which a teacher adaptively generates tasks with high learning potential, while a student learns a robust policy from this evolving curriculum. Existing UED methods typically measure learning potential via regret, the gap between optimal and current performance, approximated solely by value‑function loss. Building on these approaches, we introduce the transition-prediction error as an additional term in our regret approximation. To capture how training on one task affects performance on others, we further propose a lightweight metric called Co-Learnability. By combining these two measures, we present Transition‑aware Regret Approximation with Co‑learnability for Environment Design (TRACED). Empirical evaluations show that TRACED produces curricula that improve zero-shot generalization over strong baselines across multiple benchmarks. Ablation studies confirm that the transition-prediction error drives rapid complexity ramp‑up and that Co‑Learnability delivers additional gains when paired with the transition-prediction error. These results demonstrate how refined regret approximation and explicit modeling of task relationships can be leveraged for sample-efficient curriculum design in UED. https://geonwoo.me/traced

Published as a conference paper at ICLR 2026
TRACED: TRANSITION-AWARE REGRET APPROXI- MATION WITH CO-LEARNABILITY FOR ENVIRONMENT DESIGN
Geonwoo Cho Jacgyun Im
Jihwan Lee Hojun Yi
Sejin Kim"
Sundong Kim"
Gwangju Institute of Science and Technology (gwcho.public jacgyun.public, qhddl2650, hojum 1 72635, sjkim7822, sdkim0211 gmmai..cm
ABSTRACT
Generalizing deep reinforcement learning agents to unseen environments remains significant challenge. One promising solution is Unsupervised Environment De- sign (UED), a co-evolutionary framework which a teacher adaptively generates tasks with high learning potential, while student learns a robust policy from this evolving curriculum. Existing UED methods typically measure learning poten- tial via regret, the gap between optimal and current performance, approximated solely by salue-function loss. Building on these approaches, we introduce the cansitionn-pedicctii error as additional term in our regret approximation. To capture how training on one task affects performance on others, we further pro- pose lightweight metric called Co-Learnability, By combining these two mea- sures, we present Transition-awart Regret Approximation with Co-lcarnability for Environment Design (TRACED). Empirical evaluations show that TRACED pro- duces curricula that improve zero-shot generalization over strong baselines across rransition-rrediction multiple benchmarks. Ablation studies confirm that the transition- prediction er- ror drives rapid complexity ramp-up and that Co-I earnability delivers additional gains when paired with the cunsition-prediction error. These results demonstrate how refined regret approximation and explicit modeling of task relationships can be leveraged for sample-efficien curriculum design in UED.
https: //wp:///goooooooooooooooooo/o..o me me/ traee///
INTRODUCTION
Deep reinforcement learning (RL) has achieved remarkable success in games, continuous control, and robotics (Sutton et al., 1998). Ideally, we want agents that generalize robustly to a broad range of unseen environments. However, hand-crafting training distribution that captures all real-world variability is intractable, and agents often overfit even large training sets, performing poorly distriibtitiiiiio (Kirk et al., 2023; Korkmaz, 2024).
Unsupervised Environment Design (UED) tackles this by adapting the curriculum: a teacher module generates training tasks that challenge the student agent (Dennis et al., 2020). popular class of UED methods measures task difficulty by regret, the difference between the optimal return and the agent's s achieved return, and uses this metric to guide curriculum design (Dennis al., 2020; Jiang et al., b;a;;;a; Marker-Holder et al., 2022; Azad et al., 2023; Mediratta et al., 2023; Erlebach & Cook, 2024). Unfortunately, genuine regret requires knowing each environment's optimal Q", which is infeasible in complex domains. Existing approaches, therefore, resort to coarse proxies such as Positive Value Loss (PVL) or maximum observed return (MaxMC) (Rutherford et al., 2024). In this paper, refine regret estimation by augmenting PVL with transition prediction error term that captures how poorly a learned model predicts the environment's is dynamics. This combined signal provides more faithful approximation of regret and sharper basis for curriculum design.
censition--reddccionn
We further introduce a metric called Co-Learnability to quantify how training on one task benefits others. For instance, consider three 100-word vocabulary tasks, Spanish, English, and Japanese, whose transfer patterns differ: because Spanish and English share many cognates, learning Spanish
"Correpoonding authors.

---

Published as a conference paper at ICLR 2026
accelerates lexical access and boosts English accuracy (Ramirez et al., 2013; Costa al., 2000; Lemhöfer & Dijkstra, 2004), reflecting high Co-Learnability;; in contrast, Japanese is typologically distant (Chiswick & Miller, 2005), gains from Japanese may not transfer to English, reflecting low Co-l Co-LLearaailltty. We present a lightweight estimator of Co-Leernabilltyy that leverages observed changes in approximated regret, avoiding any additional modeling overhead in the UED loop.
We propose TRACED (Transition-awarr Regret Approximation with Co-Learnability for Environment Design), which combines refined regret and Co-Learnability to yield a task-priority land- scape (Figure 1). We evaluate TRACED on procedurally gener- ated MiniGrid (MG) Sidevalier-Boiveed et al., 2023) and Bipedal- Walker (BW) (Romac al., 2021). In MG, we compare against Domain Randomization (DR) (Jakobi, 1997), PLR- (Jiang et al., 2021b), ADD (Chung et al., 2024), and ACCEL Holder et al., 2022) (the strongest baseline). In BW, we additionally in- clude the state-of-the-art method CENIE (Teoh et al., 2024).
high
Task Difficulty low
Task 1
Task 2
Task 5
Task
Task 4
TRACED surpasses all baselines in mean solved rate across 12 MiniGrid mazes, Bipedal and even the extreme Perfect- Maze variants. Ablation studies show that the munsition-prediction emor term accelerates curriculum ramp-up, while Co-Learnability provides additional gains when combined with our regret term. An analysis of curriculum evolution indicates that TRACED progres- sively increases task difficulty from easy challenging. Taken together, these results chart path toward more sample-efficient UED by coupling refined regret approximation with explicit mod- eling of task relationships.
high
Co-Learnabiliyy
Task Priority Land- scape. Task with high diffi- culty and high Co-Learnability are scheduled with the highest priority the curriculum.
Figure 1:
We provide the full implementation of TRACED facilitate the reproduction of our main results https: / hwtp:/cooocooooooooooooooo
2
PRELIMINARIES
2.1
UNDERSPECIFIED PARTIALLY OBSERVABLE MDPS (UPOMDPS)
We model our environments underspecified partially observable Markov decision processes (UP- OMDPs) following Dennis et al. (2020). A UPOMDP is a tuple M = (A, 0, P. Pr. I, R, 7), where A is finite set of actions, $ is latent state space, and O is observation space. The ob- servation function
S + A(O) generates each observation o, given the true state 8,, the reward function S A + and discount factor ? [0, 1) are shared across all levels. Crucially, O is a set of underspecified parameters that distinguish individual "levels": for each 0 E θ, the initial state is drawn from Po( (SS) and transitions follow Pr St, 9t,a,,6)
At each time step f, the agent observes vajectory-conditione policy x(a Oo: ao oo....,or). For a fixed level 6, the utility of policy æ is the expected discounted return (T( = E E 7 rt T = R(s,, az) with the expectation taken over both the stochastic dynamics and the policy's choices. We denote an optimal policy on level by π E arg max, (T(
I(s:) and selects an action a, according to
2.2 UNSUPERVISED ENVIRONMENT DESIGN (UED)
UED provides a series of levels with unknown parameters that are used to produce task environments automatically curriculum for the agent so efficiently train single generalist policy π& across the entire parameter space θ (Dennis et al., 2020). Recent UED methods maximize regret of the agent to generate distribution of environments that guide effective learning (Jiang et al., 202 Harker-Holder et al., 2022; Teoh et al., 2024). The regret of policy æ is defined as the difference in expected reward between optimal policy x¹ and policy म, Regreta (T) Ua(**) (())))
Because the true optimal policy x* is unknown in complex environments, existing methods ap- proximate the instantaneous regret using proxy metries. For example, P (Jiang al., 2021a)
2

---

Published as a conference paper at ICLR 2026
evaluates two such proxies: Positive Value Loss (PVL) and Maximum Monte Carlo (MaxMC), PVL estimates the instantaneous regret as the average positive part of the Generalized Advantage Estima- tion (GAE)-basee) Temporal Difference (TD) errors over episode. PVL for episode of length is defined as
T
PVL(T)
L 2 k=
maX
EGS k-t dg,
(I)
T
where 7 is the discount factor, is the GAE coefficient and = -- -+ - V(s) is the one-step TD-error timestep 6. MaxMC uses the highest undiscounted return observed the task instead of bootstrap target. Other criteria such as policy entropy. one-step TD error, GAE,
policy man-mnrgin, and policy least-confidence have also been evaluated in curriculum learning contexts (Jiang et al., 2021b).
3 TRACED: TRANSITION-WAARE REGRET APPROXIMATION WITH CO-LEARNABILITY FOR ENVIRONMENT DESIGN
TRACED improves UED via (i) regret approximation combining value and transition prediction transition-prediction emors and (ii) Co-Learnability measure. These yield unified Task Priority score that governs new-task generation and replay sampling. We first present the motivating regret decomposition, then the curriculum derived from the approximated regret.
3.1 REGRET APPROXIMATION VIA TRANSITION PREDICTION LOSs
Since regret quantifies the difficulty an agent experiences on a task, improving its approximation can yield more accurate difficulty estimates and, in turn, more effective curricula. We approximate one-step regret at a state-action pair (s, a) via the following decomposition:
Regret (8, a) = (s) (s,
V*) V') Vi())) (s,
= v-())) + ar(s,a")-r(s
(2)
( Value estimation crror
(i) Reward
+ EE (E (x)) Eg V (s')))
(ii)) Puture value gop
Notation. A hat (e.g., (*) indicates empirical/leamed estimator of the optimal value; Q", V are the optimal value functions; Q V are the value functions under policy n,; P is the true transi- tion kernel and P is learned transition model; y is the discount factor.
Eq. 2 makes clear that Positive Value Loss (PVL), which evaluates only the accuracy of the empirical value estimator and thus corresponds to term (i), insufficient as proxy for regret. The future- value gap in term (iii) is influenced not only by value-functtin error but also by mismatch between the learned dynamics P and the true dynamics P. Motivated by this, augment PVL with cnansition-predcctiin error term, explicitly accounting for modellenvirrnment dynamics mismatch when approximating regret.
Definition 1 (Average Transition Prediction Loss). Train a transition dynamics estimator far implemented as a recurrent model, minimize a one-step reconstruction loss Ltraus (st, az) between the observed next state 8141 and the prediction š = fa a+) Detailed design choices for the transition model are provided in Appendix I.3. Over an episode = (So, ap. oo...., 8r), define
1 T
ATPL(T)
Livans (St,
(3)
t=0
Combine the two estimates into single scalar:
R7gret(7) PVT.(7) ATPP.(T),
3

---

Published as a conference paper at ICLR 2026
Task Difficuity Buffer (TDB)
Rollouts Buffer (RB)
Compute Difficulties
Task
Sample tasks
Task 2,1
Task &
at time-step k
2.7
1.5
0.7
0.3
Episode
Episode
PVL
Task
New Task Difficulties
1.4
0.9
Difficulty &
Difficulty b
ATPL
Time-step
difficulties
Update
0.1
Figure 2: Task Difficulty Calculation Workflow. The Task Difficulty Buffer (TDB) records each task's history of approximated regret. The agent interacts with sampled tasks to collect episode trajectories, which are stored in the Rollouts Buffer (RB). For each trajectory, we compute the Positive Value Loss (PVL) and the Average the updated task difficulty (approximated regret), which is appended to the TDB to refresh each sampled task's stored difficulty.
Loss (ATPL). Their sum produces
where 0 balances value versus transition terms.
By explicitly incorporating both components, our regret approximation more faithfully captures task difficulty and, in turn, yields more effective curricula. For each sampled task instance т, compute Regret(r) and append it the task difficulty buffer (TDB), which subsequently used drive curriculum updates (Figure 2). Detailed theoretical analysis of the relationship between term (iii) in Eq. and ATPL is provided in Appendix A, where we show that the dynamics-inducee component of the future-value gap is upper-bounde aoper-bounded by ATPL. This establishes ATPL principled correction term for regret approximation.
3.2 TASK PRIORITY CONSTRUCTION
A central challenge in UED is to decide which tasks to present to the agent at each step (Hughes et al., 2024). Intuitively, we want to (1) focus on tasks that remain challenging, while (2) exploiting tasks whose training yields transfer to others. To this end, we introduce two complementary quantities, Task Difficulty and Co-Learnability, and combine them into a single Task Priority score. In the following sections, time t indexes the teacher's curriculum-selcctinn cycles (not environment time).
Definition 2 (Task Difficulty). Let (k) = max s < k TDB(i, s) exists} denote the most recent time at or before l when task i was sampled, that its approximated regret was stored at time (k). We define the task difficulty of task at time as
TDB(i, s(()),, (k) is finite,
TaskDifficulty(i.
(5)
0.
i has never been sampled before t.
This ensures that (iskDiffiuulty(,, k) always reflects the most recent approximated regret for task i, with larger values indicating greater remaining challenge. Note that a difficulty value for task i is well-defined at time & only if the task has been sampled at least once on or before k. This difficulty estimate becomes available for use when constructing the curriculum time k+1.
Definition 3 (Co-Learnability), Beyond difficulty, we wish to capture how training on one task accelerates progress on others. Let Tk-1 be the set of tasks replayed at time k 1. We define the Co-Learnability (CL) of task at time k as
CoLearnability,
Σ JET
[TaskDiffieulty(]] k) TaskDifficulty
(6)
(Te+1
which measures the average reduction the difficulty of replayed tasks when task i selected at time k. In principle, the true marginal contribution could be computed via Shapley values; however, due to computational constraints we approximate task i's effect on reducing other tasks' difficulty using this surrogate. A positive Co-Learnability value indicates that visiting yields transfer bene- fits. Since CoLearnability (k) depends on difficulty updates that occur at time & + 1, it becomes available beginning timestep l: +
4

---

Published as a conference paper at ICLR 2026
Task Sampling
2. Priority Update
3. Task Mutate
Priority
Priority
Task Prionity
Update priorities
3nd
1st
8th
2nd
3rd
2nd
8th
Sth
3rd
2nd
4th
1st
Sample levels
Level Buffer
based on prority
Level Buffer
Buffer
Mutate tasks
Agent
Agent
Method Workflow Overview. The three panels in the figure depict: (1) Task Sam- pling: levels are drawn from the buffer based on their priority scores. (2) Priority Update: we recompute each level's priority based lowest-priority levels are mutated into new variants and reinserted into the buffer.
Figure 3:
task priority definition (Eq. 7). (3) Task Mulation: the
Definition 4 (Task Priority). We combine difficulty and Co-Learnability into scalar score and then apply a rank transform, which replaces raw values with their relative order (e.g.. the largest value receives rank 1, the next largest rank 2, etc.), as in ACCEL (Parker-Holded et al., 2022):
Task TaskPriority (i, 1) = Rank (TaskDifficully((,, () + Col.carnabilit((..))
where 0 trades off challenge versus transfer. At each step, we sample tasks inversely their priority (e.g.. ( t) & 1 1/TaskPriority t)), so lower ranks (higher priority) are selected more often.
The rank transform mitigates the influence of outliers by discarding the absolute magnitude of raw scores and retaining only their relative ordering. Without this transformation, single task with an anomalously large difficulty or Co-Learnability value can dominate the sampling distribution, collapsing the curriculum toward that task.
3.3 OVERALL UED WORKFLOW
The overall UED algorithm follows the ACCEL loop (Parker-Holder et al., 2022), with the sole change that task scoring uses our Task Priority (Eq. 7) in place of Positive Value Loss (PVL) alone (Figure 3). At each curriculum update time with probability we sample a new level uniformly at random, and with probability 1 - d we sample a level from the replay buffer according to its Task Priority score. Early in training, when the buffer empty, we sample levels uniformly at random for warm-up period. The warm-up length matches ACCEL's setting.
After training the agent on the selected level, we approximate regret using the agent's value- related loss and the cunsition-predictio task difficulty buffer. Co-Learnability is updated following Eq. after the next curriculum step, the newly visited levels have had their difficulties updated. The updated Task Difficulty and Co-Learbabilityy define Task Priority via Eq. 7, which then governs both new-task sampling and pri- oritized replay at future times. The algorithm alternates between sampling new tasks and prioritized replay until policy performance converges. The full procedure is given in Algorithm 1.
loss (for Task Difficulty), and append the result to the
4 EXPERIMENTS
We evaluate TRACED on two procedurally generated domains: MiniGrid (MG) and Biakdal (BW). In both environments. we compare against DR, PLR ACCEL (our primary baseline, since TRACED builds directly upon it), and ADD. In BW only, we additionally include the recent method CENIE (Teoh et al., 2024). While SFI. (Rutherford al., 2024) not included the main ex- perimental suite, we provide comprehensive comparison against SFL in the multi-agent JaxNav environment in Appendix R, following its original evaluation protocol. Detailed descriptions of all baselines can be found in Appendix L.
For each domain, we track the emergent complexity of the sampled curricula during training and evaluate zero test performance on held-out levels. To summarize test results, report the median, interquartile mean (IQM), mean, and optimality gap using the rliable library (Agarwal et al., 2021). The optimality gap measures how far algorithm falls short of target performance level,
5

---

Published as a conference paper at ICLR 2026
Stairs
SixteenRooms
Maze
Labyrinth
LargeCorridor
Roughness
(a) Minigrid
(b) SipedalWalkee
Figure Held-out Evaluation Environments. (a) Example held-out MiniGrid mazes for zero-shot evaluation: 4 tasks are shown (see Appendix I.1 for all 12 task definitions). BipedalWalker terrains for zero-shot evaluation: tasks are shown (see Appendix 1.2 for all task definitions).
(b) Example held-out
beyond which further gains are deemed negligible. Accordingly, higher IQM and lower optimality gap values indicate better performance. Shaded regions in all plots denote 95% confidence intervals.
All methods use Proximal Policy Optimization (PPO) (Schulman et al., 2017) the student agent. Following prior work (Parker-Holder et al., 2022: Teoh et al., 2024), we plot performance versus the number of PPO updates and report the corresponding environment interactions per update in Appendix G. Our only deviation from ACCEL the number of PPO workers (i.e., parallel trajectory collectors), chosen for computational constraints: MiniGrid uses 16 workers instead of 32, and Bipeda/Walker uses 4 instead of 16. Consequently, some baseline scores may differ from those in the ACCEL paper. However, Appendix B.4 shows that TRACED has worker-specific tuning and that reducing workers does not render the comparison unfair. We report TRACED at 10k updates (rather than 20k) because single-seed. long-horizon runs (45k PPO updates) MiniGrid reveal post- convergence oscillations in both TRACED and ACCEL, and reporting earlier avoids this confound (Appendix C). Additional hyperparameters and architectures are provided Appendix I.
4.1 PARTIALLY OBSERVABLE NAVIGATION
We evaluate our curriculum design partially observable maze navigation domain based MiniGrid Schevalier-Boisvee et al., 2023), as in prior UED work. Four representatives are shown in Figure 4. The agent observes 147-dimensional pixel observation and is trained for up 20k PPO updates.
Median
IQM
Mean
Optimality Gap
TRACED (Ours) 10k
ACCEL 20k
ACCEL 10k
ADD 20k
ADD 10k
20k
PLR 10k
DR 20k
DR 10k
0.2
0.4
0.6
0.2
0.4
0.6
0.8
0.30
0.45
0.60
0.30
0.45
0.60
0.75
Score
Figure 5: Zero-Shot Transfer Performance in MiniGrid. Aggregated solved rates on held-out MiniGrid mazes after 10k and 20k PPO updates. TRACED at 10k updates outperforms baselines at 20k updates.
Our method achieves a superior solved rate at only 10k updates, matching or exceeding the 20k update performance of all baselines (Figure 5). In particular, TRACED's median solved rate 10k surpasses ACCEL at 20k, and its IQM leads the field, indicating that the majority of runs benefit rapidly from combined regret and Co-Leamability scoring.
Compared to ACCEL, TRACED halves the wall-clock training time while maintaining equivalent better transfer performance (Table 1). Even relative to ACCEL at the same 10k update budget,

---

Published as a conference paper at ICLR 2026
Table I: Wall-clock training time comparison. Average training duration (hours + SE over 10 runs) on the MiniGrid domain.
TRACED l0k ACCEL 10k
ACCEL 20k ADD lok
ADD 20k
PLR
10k
PLR
20k
DR 10k
DR 20k
0.66
22.48 0.27
0.18
TRACED incurs 6% computational overhead yet delivers a 22% relative increase in mean solved rate. Taken together, these metrics demonstrate that TRACED not only accelerates learning but also delivers more consistent and reliable zero-shot transfer across diverse MiniGrid mazes. Detailed per-task zero-shot results are provided in Appendix Q, and the number of environment interactions per PPO update for each method is in Appendix G.
TRACED (Ours)
ACCEL ATPL
ACCEL
140
70-
100-
60-
30-
20-
Student PPO Updates
Student PPO Updates
(a) Shortest Path Length
(b) Number Blocks
Figure 6: Emergent maze complexity metrics. Shortest path length and number of blocks both grow faster under TRACED (pink) than ACCEL (blue). This faster ramp-up up indicates that our curriculum effectively escalates difficulty in lockstep with agent learning.
To analyze emergent environment complexity, we track two structural metrics for each generated maze: (i) the length of the shortest solution path and (ii) the number of obstacles (Figure 6). Curves are averaged over 10 seeds with shaded 95% confidence intervals. Both metrics increase substantially faster under TRACED than under ACCEL, indicating that our priority scoring more effectively separates easy from challenging tasks and yields steadily escalating curriculum. No- tably, ACCEL+ATPL. also drives complexity upward far faster than ACCEL alone and closely tracks TRACED, demonstrating that the transition-predic component on its own contributes strongly to complexity ramp-up.
PerfectMazeLarge
0.6
Ours 10k
ACCEL 20k
0.3
ACCEL 10k
ADD 20k
0.6
0.0
PerfectMazeXL
ADD 10k
PLR 20k
PLR 10k
933
DR 20k
10k
(a) PerfectMazel.agge
(b) PerfectMazeXT.
(c) Zero-shot solved rates
Figure 7: PerfectMaze Evaluation. (a), (b) Two held-out maze instances, PerfectMazel Large and
PerfectMazeXI. used for zero-shot testing. (c) Zero-shot solved rates. TRACED achieves the high- est 10k performance on PerfectMazze.arge and closely matches the best 20k performance on Per- FectMazeXL.
To stress-test our curriculum extremely large, procedurally generated mazes, introduce two PerfectMaze benchmarks. PerfectMazzearge consists of 51 x 51 grids with a maximum episode length exceeding 5k steps, while PerfectMazeXL scales this to 100 x 100 grids. Figure shows representative levels from each variant. We evaluate zero-shot transfer performance, measuring the mean success rate over 100 episodes per seed (10 seeds total).

---

Published as a conference paper at ICLR 2026
On PerfectMazeLarge,, TRACED achieves the highest 10k solved rate (27% = 23%), outperforming ACCEL's best 20k rate (20% + 25%) and far exceeding ADD, DR and PLR (Figure 7). On the even more complex PerfeetaazeXL, ACCEL narrowly leads at 12% 28% after 20k updates, with TRACED close behind at 10% + 14% after just 10k updates, demonstrating that TRACED scales to extremely large mazes. Complete per-baseline numerical results for both benchmarks are reported in Appendix Q, and the full set of aggregate metrics (Median, IQM, Mean, and Optimality Gap) for PerfectMaze shown in Figure 21.
4.2 WALKING IN CHALLENGINGG TERRAIN
We further validate our curriculum in the continuous-contro) Bipeeda alkkrHarrdeee environment from OpenAl Gym (Brockman al., 2016), modified by Wang al. (2019). This domain features procedurally generated terrain controlled by eight parameters, terrain roughness, pit gap frequency, stump height, stair spacing, etc., that jointly determine locomotion difficulty. We consider the com- plete set of eight parameters in our design space. Figure 4 illustrates two representative terrains with varying stair heights and surface roughness. We evaluate zero-shot transfer on six held-out test terrains over 100 episodes each, averaged over five random seeds.
Median
IQM
Mean
Optimality Gap
TRACED (Ours) 10k-
ACCEL-CENIE 20k-
ACCEL-CENIE
ACCEL 20k
ACCEL 10k
ADD 20k
ADD 10k
PLA 10k-
DR 20k
DR 10k
0.00
0.15
0.30
0.00
0.15
0.30
0.00
0.15
0.30
0.75
0.90
1.05
Normalized
Figure 8: Aggregate zero-shot performance on Bipedal terrains. All scores are normal- ized by the maximum return 300 the BipedalWalker domain. TRACED at 10k updates (pink) matches or exceeds ACCEL-CENIE at 20k updates (purple) across all metrics.
TRACED (Ouns)
ACCEL
ADD
DR
305
Raim
-00
100
12C-
-100
110
the
PPd Updanos
Studont PRO Updates
Studont PPO Updates
(a) Basic
(b) Hardcore
(c) Stair
94hu
-100
100
-100
Studert PPO Updares
Stutent PPO Updates
Statent PPO Updates
(d) Pitgap
(c) Stump
(f) Roughness
Figure 9: Return progression on BipedalWalker terrains. baselines.
TRACED consistently outperforms
TRACED delivers consistent gains across all four aggregate metrics, median. interquartile mean (IQM), mean, and optimality gap. on the six held-out BipedalWalker terrains (Figure 8). After only 10k updates, it already outperforms all baselines evaluated at 20k. As in MiniGrid, TRACED
8

---

Published as a conference paper at ICLR 2026
also reaches its peak performance in roughly half the wall-clock time of ACCEL BipedalWalker (Appendix G). Moreover, TRACED consistently surpasses ACCEL in zero-shot returns across all terrains throughout training (Figure 9), further underscoring the effectiveness of its curriculum de- sign. Detailed numerical results are provided in Appendix Q
4.3
ABLATION STUDY
Optimality Gap
TRACED (Ours) 10K TRACED
TRACED ATPL 10k
Figure 10: Ablation Study on TRACED. Both ATPL and CL are important design choices.
To isolate component contributions, compare TRACED at 10k updates with two ablations (Fig- ure 10): ATPL only (TRACED CL) and Co-Learnability only (TRACED - ATPL), each evaluated with five seeds. Results reported following Agarwal al. (2021). On MiniGrid, TRACED out- performs both variants across four metrics, indicating that each component contributes meaningfully to performance. The same trend holds BipedalWalker (Appendix B). Ablations the scaling factors a and /3 further show that both elements play significant roles TRACED and that carefully balancing ATPL and CL can yield additional gains (Appendix B.1). Detailed numerical results provided in Appendix Q.
4.4 ANALYSIS ON CURRICULUM PROGRESSION
Table 2: Proportions (%) of Easy, Moderate, and Challenging levels in the level buffer during
PPO updates.
Method
Difficulty
Ok
5k
10k
15k
20k
Easy
100
100
79.2
26.7
9.2
ACCEL
Moderate
0
20.8
73.3
90.8
Challenging
Easy
100
72
24.5
19.5
11.2
TRACED
Moderate
25.7
60.9
77.3
Challenging
2.3
14.6
12.5
11.5
To analyze how the curriculum evolves, we examine the Walker level buffer over time and categorize each generated level into three difficulty bands: Easy, Moderate, Challenging, based on environment hyperparameters. Following Teoh et al. (2024), we set thresholds for Stump Height (2.4), Pit Gap (6), Ground Roughness (4.5), and Stairs Height (5). Levels exceeding no thresholds are labeled Easy, those exceeding exactly one threshold are Moderate, and those exceeding least two thresholds are Challenging. Table 2 reports the proportion of cach difficulty in the buffer at different PPO update steps.
TRACED progressively shifts mass from Easy to Moderate and Challenging, introducing nontrivial proportions of Challenging levels by 10k (14.6%) and maintaining them thereafter (11.5% at 20k). In contrast, ACCEL never surfaces Challenging levels even at 20k (0% throughout), with the buffer dominated by Moderate levels by 20k (90.8%). This steady escalation under TRACED aligns with its faster convergence and stronger performance already at 10k updates. The respective contributions of ATPL and Co-Learnability (CL) curriculum progression are analyzed in Appendix D, and visualization of level evolution is provided in Appendix E.
5 CONCLUSION
In this paper, introduced Unsupervised Environment Design (UED) method with two key components: (i) an explicit transition prediicion error term for regret approximation, and (ii) a lightweight Co-Leammability metric that captures cross-task transfer effects. By integrating these into

---

Published as a conference paper at ICLR 2026
the standard cenerator--eplay loop, TRACED produces curricula that escalate environment complex- ity in tandem with agent learning.
Empirically, demonstrated two procedurally generated domains (MiniGrid navigation and BilkealWalker) that TRACED outperforms baselines (DR, PLR* ADD, ACCEL), including CE- NIE, using only half the training updates. We showed superior zero-shot transfer success rates, faster growth in structural complexity, and scalability to extremely large mazes. Ablation studies confirmed that each component is essential: ATPL drives the primary complexity ramp-up, while Co-Learnaiility yields gains when paired with our regret estimates.
Looking forward, Co-Leearabilityy offers a simple, computationally light mechanism for capturing inter-task influences and could be further refined via more sophisticated causal estimators or learned models. More broadly, any RL setting that relies on regret-approximation stands to benefit from in- corporating transition-predien prediction error, providing an easy-to- to-iplleel boost in sample efficiency. We anticipate that these ideas will inspire future work on adaptive curricula, advanced editing mech- anisms, and broader applications of regret-guided exploration in open-ended learning environments.
ACKNOWLEDGMENTS
This work was supported by ITTP RRS-2024-004450077 10%, RSS-2025-25410844 10%, No. 2019- 0-01842; 10%), NRF (RS-2024-00451 20%. RS-2024-00454000; 20%. RS-2025-25419920; 20%), GIST (KH0870; 10%) funded by the Ministry of Science and ICT, Korea. Computing re- source were supported by GIST SCENT-AI, AICA, KISTI, and NIPA.
10

---

Published as a conference paper at ICLR 2026
REFERENCES
Rishabh Agarwal, Max Schwarzer, Pablo Samuel Castro, Aaron Courville, and Marc G. Bellemare. Deep Reinforcement Learning at the Edge of the Statistical Precipice. In NeurIPS, 2021.
Abdus Salam Azad, Izzeddin Gur, Jasper Emhoff, Nathaniel Alexis, Aleksandra Faust, Pieter Abbeel, and Ion Stoica. CLUTR: Curriculum Learning via Unsupervised Task Representation Learning. In ICML, 2023.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. OpenAl Gym. arXiv preprint arXiv:1606.011400 2016.
Maxime Chevalier-Boisver,, Bolun Dai, Mark Towers, Rodrigo Perez-Vicente Lucas Willems, Salem Lahlou, Suman Pal, Pablo Samuel Castro, and Jordan Terry. Minigrid & Miniworld: Modular & Customizable Reinforcement Learning Environments for Goal-Oriented Tasks. In NeurIPS, 2023.
Barry R. Chiswick and Paul W. Miller. Linguistic distance: A quantitative measure of the distance between english and other languages. Journal of Multilingual and Multicultural Development, 26(1):1-11, 2005. doi: 10. 1111000017977100066663383 URL httpthtsss/:...ooopgoooo
147907105086688 668995
François Chollet. On the Measure of Intelligence. arXiv preprint arXiv:/911.01154,,200
Hojun Chung, Junseo Lee, Minsoo Kim, Dohyeong Kim, and Songhwai Oh. Adversarial En- vironment Design via Regret-Guided Diffusson Models. In NeurIPS, 2024. URL https:
//github.cc// com/ rllab- Canu/ADD/tre//ree
Albert Costa, Alfonso Caramazza, and Nuria Sebastian-Galles. The Cognate Facilitation Effect: Implications for Models Lexical Access. Journal of Experimental Psychology: Learning, Memory, and Cognition, 26(5): 2000.
Robby Costales and Stefanos Nikolaidis. Enabling Adaptive Agent Training in Open-Enden Ended Simu- lators by Targeting Diversity. In NeurIPS, 2024.
Michael Dennis, Natasha Jaques, Eugene Vinitsky, Alexandre Bayen, Stuart Russell, Andrew Critch, and Sergey Levine. Emergent Complexity and Zero-shot Transfer via Unsupervised Environment Design. In NeurIPS, 2020.
Theresa Eimer, André Biedenkapp. Frank Hutter, and Marius Lindauer. Self-Paced Context Evalu- ation for Contextual Reinforcement Learning. In ICML, 2021.
Hannah Erlebach and Jonathan Cook. RACCOON: Regret-based Adaptive Curricula for Coop- eration. In RLC Workshop Coordination and Cooperation for Multi-Agent Reinforcement Learning Methods, 2024.
Carlos Florensa, David Held, Xinyang Geng, and Pieter Abbeel. Automatic Goal Generation for Reinforcement Learning Agents. ICML, 2018.
Scott Fujimoto, Herke van Hoof, and David Meger. Addressing Function Approximation Error in Actor-Critic Methods. ICML, 2018
David Ha and Jürgen Schmidhuber. World Models. arXiv preprint arXiv: 1803. /0/22, 2018.
Tuomas Haamoja. Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft Actor-Critic Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor. In ICML, 2018.
Danijar Hafner, Jurgis Pasukonis, Jimmy Ba, and Timothy Lillicrap. Mastering Diverse Control Tasks through World Models. Nature, pp. 1-7, 2025.
Edward Hughes, Michael Dennis, Jack Parker-Holder Feryal Behbahani, Aditi Mavalankar, Yuge Shi, Tom Schaul, and Tim Rocktäschel. Open-Endedme Endedness is Essential for Artificial Superhuman Intelligence. In ICML, 2024.
11

---

Published as a conference paper at ICLR 2026
Matthew Thomas Jackson, Minqi Jiang, Jack Parker-Holder, Risto Vuorio, Chris Lu, Gregory Far- quhar, Shimon Whiteson, and Jakob Nicolaus Foerster. Discovering general reinforcement learn- ing algorithms with adversarial environment design. In NeurlPS, 2023.
Nick Jakobi. Evolutionary robotics and the radical envelope-of-noise hypothesis. Adaptive behavior, ((2):325-368, 1997.
Minqi Jiang, Michael Dennis, Jack Parker-Holder Jakob Foerster, Edward Grefenstette, and Tim Rocktäschel. Replay-Guided Adversarial Environment Design. NeurIPS, 2021a.
Minqi Jiang, Edward Grefenstette, and Tim Rocktäschel. Prioritized Level Replay. In ICML, 2021b.
Mingi Jiang, Michael Dennis, Jack Parker- Holder,, Jakob Foerster, Edward Grefenstette, and Tim
Rocktäschel. Replay-guided adversarial environment design, 2022. URL https://gåthhn
Soon/facebookesearccoo ded.
Robert Kirk, Amy Zhang, Edward Grefenstette, and Tim Rocktäschel. A Survey of Zero-shot Gen- eralisation in Deep Reinforcement Learning. Journal of Artificial Intelligence Research, 76:201- 264, 2023.
Pascal Klink, Carlo D'Bramo, Jan Peters, and Joni Pajarinen. Self-Paced Deep Reinforcement Learning. In NeurlPS, 2020.
Pascal Klink, Haoyi Yang, Carlo D'Eramo, Jan Peters, and Joni Pajarinen. Curriculum Reinforce- ment Learning via Constrained Optimal Transport. ICML, 2022.
Ezgi Korkmaz. A Survey Analyzing Generalization in Deep Reinforcement Learning. arXiv preprint arXiv:2401.02349, 2024.
Kristin Lemhöfer and Ton Dijkstra. Recognizing Cognates and Interlingual Homographs: Effects of Code Similarity in Sanguage-SSeciife and Generalized Lexical Decision. Memory & cognition, 32:533-550, 2004.
Dexun Li, Wenjun Li, and Pradeep Varakantham. Marginal Benefit Induced Unsupervised Environ- ment Design, 2024. URL htttt:::///peeeeviewe det.eeeeeeee//torrmmdd/oooooooo
Wenjun Li, Pradeep Varakantham, and Dexun Li. Generalization through Diversity: Improving Unsupervised Environment Design. In IJCAI, 2023.
A Rupam Mahmood, Dmytro Korenkevych, Gautham Vasan, William Ma, and James Bergstra. Benchmarking Reinforcement Learning Algorithms on Korld Robots. CoRL, 2018.
Ishita Mediratta, Minqi Jiang, Jack Parker-Holder, Michael Dennis, Eugene Vinitsky, and Tim Rocktäschel. Stabilizing Unsupervised Environment Design with a Learned Adversary, In CoL- LAs, 2023.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-Level Control through Deep Reinforcement Learning. Nature, 51 518(7540):529-555 23329 2015.
Sanmit Narvekar, Bei Peng. Matteo Leonetti, Jivko Sinapov, Matthew E Taylor, and Peter Stone. Curriculum Learning for Reinforcement Learning Domains: A Framework and Survey. Journal of Machine Learning Research, 21(181):1-50 2020.
Junhyuk Oh, Xiaoxiao Guo, Honglak Lee, Richard I. Lewis, and Satinder Singh. Action-Conditionl Video Prediction using Deep Networks in Atari Games. In NeurIPS, 2015.
Jack Parker-Holder, Minqi Jiang, Michael Dennis, Mikayel Samvelyan, Jakob Foerster, Edward Grefenstette, and Tim Rocktäschel. Evolving Curricula with Regret- Environment Design. In ICMI, 2022.
Gloria Ramírez, Xi Chen, and Adrian Pasquarella. Cross- lingu-iin transfer of morphological aware- ness in Spanish-Speakinn English language learners: The facilitating effect of cognate knowledge. Topics in Language Disorders, 33(1):73-922 jan 2013. doi: 10.1097/TL...00 12208555....
12

---

Published as a conference paper at ICLR 2026
Mare Rigter, Minqi Jiang, and Ingmar Posner. Reward- Freee Curricula for Training Robust World Models. In ICLR, 2024.
Clément Romac, Rémy Portelas, Katja Hofmann, and Pierre-Yves Oudeyer. TeachMyAgent: Benchmark for Automatic Curriculum Learning Deep RL. ICML, 2021.
Alexander Rutherford, Michael Beukman, Timon Willi, Bruno Lacerda, Nick Hawes, and Jakob Nicolaus Foerster. No Regrets: Investigating and Improving Regret Approximations for Curriculum Discovery. NeurlPS, 2024.
Mikaycl Samvelyan, Akbir Khan, Michael D Dennis, Minqi Jiang, Jack Parker-Holder, Jakob Foer- ster, Roberta Raileanu, and Tim Rocktäschel. MAESTRO: Open-Ended Environment Design for Multi-Agent Reinforcement Learning. ICLR, 2023.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal Policy Optimization Algorithms. arXiv preprint 17Xiv:1707.0634/ 2017.
Richard $ Sutton, Andrew G Barto, et al. Reinforcement Learning: An Introduction, volume MIT Press Cambridge, 1998.
Jayden Teoh, Wenjun Li, and Pradeep Varakantham. Improving Enviromment Novelty Quantification for Effective Unsupervised Environment Design. In NewrlPS, 2024.
Georgios Tzannetos, Bárbara Gomes Ribeiro, Parameswaran Kamalaruban, and Adish Singla. Prox- imal Curriculum for Reinforcement Learning Agents. TMLR, 2023.
Linji Wang, Zifan Xu, Peter Stone, and Xuesu Xiao. Grounded curriculum learning. arXiv preprint arXiv:2409. /9800 2024.
Rui Wang, Joel Lehman, Jeff Clune, and Kenneth O Stanley. Paired Open-Ended Ended Trailblazer (POET): Endlessly Generating Increasingly Complex and Diverse Learning Environments and Their Solutions. arXiv preprint arXiv: /0010//90//0755 2019.
Rui Wang, Joel Lehman, Aditya Rawal, Jiale Zhi, Yulun Li, Jeff Clune, and Kenneth O. Stanley. Enhanced POET: Open-ended reinforcement learning through unbounded invention of learning challenges and their solutions. In ICML, 2020.
Hang Zhao, Orazio Gallo, luri Frosio, and Jan Kautz. Loss Functions for Image Restoration with Neural Networks. IEEE Transactions Computational Imaging, 3(1):47-57, 2016.
13

---

Published as a conference paper at ICLR 2026
A
THEORETICAL ANALYSIS OF ATPL
We restate the one-step regret decomposition (Eq. 2 in the main paper):
Regret(s,a)
(*(s) - (s) +r(s, -
Value estimation crror
(it Reward gap
y
E Ba'aP("laa"
V (s") E Bx V [*(s'))
(ii) Future value
Our objective is to isolate and control the portion term (iii) that arises specifically from the mis- match between the true transition kernel P and the learned transition model P. In particular, we focus on the discrepancy between the value predictions under and P. and show that this dynamics- induced error can be bounded by the transition loss used in ATPL.
A.1 ASSUMPTIONS
Assumption (Lipschitz value function). Let (S, be the state space equipped with metric d(;;) ).. The approximate optimal value function V S + R is -ypsschhtttz with respect to d, i.e.,
- Lv ((118) 82);
V8,, 82 E.
Assumption 2 (Loss dominating the metric). Let e S x S - [0, oo) be the reconstruction loss used train the transition model (e.g., (xx,8) y) = || - y/13). We assume that there exists a constant C₂ > 0 such that
d(x, v) S C ((r,y),
Ve,yES.
Definition 5 (Coupling-based) transition loss).
For each state-action pair (s, a., let P(- s. and P( s, s,a) denote the true and learned transition kernels, respectively. A coupling of P(. s,a) and P(- a) is any joint distribution I' I' S S such that its marginals satisfy
(st 8+) Ts.a
st P(- 8, a),
st~ P(. 11, a)-
Given such coupling aa we define the one-step transition loss as
Lerans (8, a) == Es ,tt) [e(s 8+}]
A.2 BOUNDING THE DYNAMICS MISMATCH TERM
Lemma 1. Define the dynamics mismatch term
Adyn a) : E (P(), (V -s)))s))Err(e.... Er(.ss)) [+'(']]
Under Assumptions and 2. for any coupling 1s,a of P(. s) and P s, a). we have
Adya(s, a) S Ly Ct (s)
Proof. Let (8)) ~ Tsa be a coupling P(. | s,a) and P(. s, s, i.c, st ~ P(- s, and g+ P(: s,)). Then, by the definition of the marginal distributions.
E Ept)s.)) [s')] =
[V' (8+)))
and
Ep(le.)) (s'')
B (TT))
14

---

Published as a conference paper at ICLR 2026
Hence
dyn (s,
((ltt,+t) [**)+]] B(st [st)
BBtt
[V+(tt) [*{)))]
S st)t. (i-(st) (s
Ly B(st,ttt [(ss" st)]
(by Lipschitzness of Vi))
Lv Ce S- [(st 5-]]
(by the dominance S C₂
Lv Ce Liraus (s, a).
A.3 REGRET APPROXIMATION
We compare two regret proxies:
Regretpyt(T) = PVI,(7,, ATPL() PVI(T) + a ATPL(T).
Theorem (Regret Approximation Improvement with ATPL). For any trajectory T,
Regret(T) - Regrettyi & Co ATPL(TT
where Co collects the remaining terms in the regret decomposition that do not depend on the transi- tion mismatch. Furthermore,
Reg Regret Regret Co [Lv - ATPL(T).
In particular, choosing = LvC2 yields a strictly tighter worst-case approximation bound than PVL alone.
Proof. Lemma bounds the dynamics induced component of the regret by LvCr ATPL(T). Substi- tuting this bound into the regret decomposition and subtracting a ATPL(T)) gives the inequality. O
Interpretation. PVL captures only the value-estimation component of regret and assigns zero weight to the error arising from transition modell mismatch. Lemma shows that this missing com- ponent controlled by ATPL. Theorem then establishes that augmenting PVL with a ATPL reduces the worst-case approximation whenever is chosen to match the scale of the transition mis- match (i.e., CtC,). Thus, ATPL provides principled correction for the future-value error, yielding more faithful regret proxy for unsupervised environment design.
15

---

Published as a conference paper at ICLR 2026
B ADDITIONAL EXPERIMENTS
B.I ABLATION STUDY ON THE SCALING FACTOR
In this ablation, keep every setting in Appendix P fixed except for one of the weight-scaling factors, a (ATPL. weight), 8 CCo-Leearabilityy weight). Results are averaged over five random seeds and reported as mean + standard error on 12 held-out MiniGrid tasks. Each method is evaluated after 10k PPO updates.
Table 3: Ablation study on the scaling factor. Comparing different fixed projection Weight base-
lines (a 0.0, 100.0, / 0.0, 3 100.0) and TRACED (a 1.0, 3 1.0). Bold indicates the best; underline indicates the second-best
Environment
0=0.0
a=100.0
8=0.0
3=100.0
TRACED
16Rooms
0.81 0.1
0,06 = 0.04
0.73 1 0.09
0.74 0.17
0.79 0.19
16Rooms2
0.94 0.05
0.0
0.28 0.2
0.59 0.15
0.72 0.17
SimpleCrossing
0.84 0.04
0.43 0.08
0.86 0.04
0.82 = 0.04
0.89 +
0.01 0.01
FourRooms
0.45 0.05
0,23
0.41 0.05
0.52 0.03
0.47
SmallCorridor
0.42 = 0.24
0.12
0.62
= 0.12
0.49
LargeCoridor
0.44 2.44:00 0.26
0.02
0.54
0.56 = 0.18
0.5 0.14
Labyrinth
0.5 0.29
0.0
0.29
0.19 0.18
1.0 0.0
Labyrinth2
0.61 0.2
0.0
0.17
0.2 0.2
0.98 0.01
Maze
0.74 =
0.0
0.08
0.39 = 0.24
0.59 0.17
Maze2
0.56 0.26
0.0
0.51
0.14 0.12
0,42 + 0.19
Maze3
0.51 0.27
0.0
0.59
0,51 = 0.21
0.86 0.07 0.07
PerfectMaze(M)
0.4 + 0.16
0,01 0.02
0,4 0.06
0.34 = 0.07
0.66 + 0.11
Mean
0.6 0.1
0.07 = 0.01
0.5 0.09
0.46 = 0.05
0.7 0.04
Deviating from defaults on either a or 3 reduces the solved rates in most domains (Table 3). For both ignoring of the weighted terms (a 0.0 or / 0.0) and using excessively large weight (a = 100.0 or 3 = 100.0), solved rates show slight improvement for some individual tasks, but statistical drops for overall performance. The default TRACED weights show the best performance compared to fixed projection baselines. This result shows that an effective balance between ATPL. and Co-Learnability is needed.
B.2 ABLATION STUDY ATPL AND CO-LEARNABILITY
In this ablation, we evaluate TRACED by removing each of its two components in turn. Table 4 reports zero-shot solve rates on six held-out Balker tasks after 10k PPO updates. Results are averaged over five random seeds and reported as mean + standard error.
Table 4: Ablation study on ATPL and Co-Learnability. Comparing ACCEL (10k), TRACED ATPL (10k), TRACED CL (10k), and TRACED (10k, 1.5, 0.6). Bold indicates the best result per task; underline indicates the second-best
Environment
ACCEL 10k
TRACED ATPL 10k
TRACED CL 10k
TRACED 10k
Basic
281.65 + 5.25
282.61 1 4.64
286.75 1 5.01
293.67 1 3.56
Hardcore
37.59 + 15.0
53.77 + 20.8
48.35 +: 23.74
86.83 +: 17.96
Stairs
-38.71 + 10.54
-43.99 + 12.99
-34.1 8.44
-29.0 + 10.4
PitGap
-65.07 = 7.57
-72.92 + 13.95
-5.2 + 66.89
-39.26 + 11.42
Stump
-79.18 - 5.45
-38.06 + 39.88
-19.89 64.11
34.16 1: 54,58
Roughness
161.72 28.36
191.75 + 25.07
191.68 4.99
193.29 21.6
Mean
49.67 + 11.24
62.19 + 11.21
77.93 = 17.58
89.95 + 12.95
TRACED achieves the top score in five of six tasks (Basic, Hardcore, Stairs, Stump, Roughness) and ranks second in the remaining one. The ATPL only variant (TRACED CL) leads to the first place in one task (PitGap) and second place in two tasks (Basic, Stump), while the Co-Learnability only variant (TRACED ATPL) only reaches the second place in two tasks (Hardcore, Roughness). Removing both components (the ACCEL baseline) ranks second one (Stairs). These results confirm that both transition and stable performance across diverse tasks.
raasition-preediction prediction enror and Co-Learnailltyy are essential to TRACED's s high
16

---

Published as a conference paper at ICLR 2026
B.3 HYPERPARAMETER SENSITIVITY ANALYSIS
We analyze impact of varying the ATPL weight a and the Co-Learnability weight 3 in TRACED across the 12 held-out MiniGrid environments and six held-out WileealWalker terrains. Results reported for a single random seed due to computational constraints.
Table 5: Effect of hyperparameter weights (a, 3) on MiniGrid environments. Evaluations are performed under varying (a. 3) settings. Bold indicates the best; underline indicates the second- best.
Environment
(0.75, 1.0)
(1.25, 1.0)
(1.0, 0.75)
(1.0, 1.25)
(1.25, 0.75)
TRACED (1.0, 1.0)
16Rooms
0.26
0.90
1.00
0.96
1.00
0.79 + 0.19
16Rooms2
0.00
0.05
0.08
0.78
0.10
0.72 + 0.17
SimpleCrossing
0.82
0.84
0.85
0.71
0.78
0.89 + 0.01
FourRooms
0.68
0.36
0.52
0.39
0.51
0.47 = 0.02
SmallCorridor
0.55
0.00
0.01
0.00
0.01
0.49 + 0.17
LargeCorridor
0.94
0.02
0.01
0.00
0.01
0.50 0.14
Labyrinth
0.98
1.00
1.00
1.00
1.00
1.00 0.00
Labyrinth2
1.00
0.73
0.76
1.00
0.95
0.98 + 0.01
Maze
0.76
0.16
0.39
0.00
1.00
0.59 0.17
Maze2
0.07
0.00
0.94
1.00
0.98
0.19
Maze3
0.92
1.00
0.10
0,89
0.93
0.86 - 0.07
PerfectMazeeMi
0.56
0.38
0.55
0.55
0.85
0.66 + 0.11
Mean
0.63
0.45
0.52
0.61
0.67
+ 0.04
In MiniGrid environments, four of the six (a, 3) settings outperform the 10k-update baselines (Ap- pendix Q), and even the weakest setting matches the performance PLR 10k (Table 5). These results indicate that TRACED provides consistently strong zero-shot generalization across broad range of hyperparameters, without extensive tuning.
Table Effect of hyperparameter Weights (a, 3) on Bipedal environments. Evaluations performed under varying (a, settings. Bold indicates the best; underline indicates the second- best.
Environment (1.25, 0.6)
(1.75, 0.6)
(1.5, 0.45)
(1.5, 0.75)
TRACED (1.5, 0.6)
Basic
282.06
291.04
281.32
279.37
293.67+3..6
Hardcore
-7.60
115.87
29.55
50.10
86.83
Stairs
-52.78
-21.94
-42.37
-66.02
0.9.0+100.4
PitGap
12.96
-52.72
-52.21
-122.54
-39.26 11.42
Stump
-100.95
-40.11
-74.83
-73.93
34.16=54.58
Roughness
148.22
187.43
244.57
185.83
193.29421.66
Mean
46.99
79.93
64.34
42.13
89.95
In Bileda/ three of the configurations outperform all 10k-update baselines (Appendix Q)
(Table 6). Even the mean return across all five (a, 3) choices (>: 64.9) exceeds every baseline. These results demonstrate that TRACED delivers consistently strong zero-shot generalization across a wide range of weight settings, without requiring extensive hyperparameter tuning.
17

---

Published as a conference paper at ICLR 2026
B.4 ABLATION STUDY THE NUMBER OF WORKERS
We analyze the effect of the number of PPO workers, which determines how many agents collect trajectories in parallel. The only difference between our experimental setup and ACCEL (Parker- Holder et al., 2022) is the worker count: we use 16 workers for MiniGrid and 4 for Bipeda/Walker, whereas the original ACCEL paper uses 32 and 16, respectively. To ensure this configuration does not unfairly disadvantage TRACED, we additionally evaluate MiniGrid with 32 workers. Even under this setting, TRACED consistently outperforms ACCEL, indicating that our gains are robust to the PPO worker configuration (Table 7).
Table 7: Ablation study on Number of Workers. Bold indicates the best; underline indicates the second-best.
Enviromment
ACCEL 5k
ACCEL 10k
TRACED Sk
TRACED 10k
16Rooms
0.37 = 0.17
0.78 1.78#0.1. 0.14
0.95 0.02
0.93 = 0.07
16Rooms2
0.20 : 0.20
0.77 0.23
0.29 0.14
0.91 + 0.04
SimpleCrossing
0.65 + 0.09
0.73 0.07
0.00
0.88 + 0.05
FourRooms
0.33 + 0.08
0.45 + 0.04
0.33 0.04
0.59 + 0.01
SmallCorridor
0.52 = 0.21
0.27 0
0.62
0.10 0.04
LargeCorridor
0.42 0.17
0.36 0.30
0.49 0.24
0.16 1 0.13
Lahyrinth
0.15 + 0.15
0.49 0.29
0.67 0.33
0.91 0.09
Labyrinth2
0.0 + 0.0
0.51 : 0.29
0.65 0.20
1.0 0.0
Maze
0.33 = 0.33
0.36 133:00 0.32
0.95
0.99 - 0.01
Maze2
0.01 = 0.01
0.24
0.22 1
0.60 + 0.20
Maze3
0.14 + 0.13
0.48 0.27
0.63 + 0.29
1.0 + 0.0
PerfectMaze(()
0.20 = 0.09
0.48
0.58 + 0.10
0.63 = 0.18
Mean
0.28 + 0.10
0.54 0.09
0.60 + 0.06
0.72 + 0.09
18

---

Published as a conference paper at ICLR 2026
C LONG-TERM ANALYSIS ON TRACED
30000
2000
3009 Updates
40090
30000
20008
30089
40033
31000
23008
3008 Updazes
40800
Student Updates
Maze
(b) FourRooms
(c) Labyrinth
0.3
0.8
0.2
30005
32008
30089
40090
30000
20008
30083
40090
31000
33008
30003 Updanes
40800
Student Updates
(d) PerfectMaze(M)
(e) SimpleCrossing
(1) SmallCorridor
Figure 11: TRACED Solved-Rate Time Series. Solved rate progression on MiniGrid tasks plotted over 0-45k PPO updates.
0.8
0.7
0.5
20000
2006
2000
45893
20000
2,008
20003
40030
20000
200C
20003
00000
Student PPO Updates
Student PPD Updates
Student PPO Updates
(a) Maze
(b) FourRooms
(c) Labyrinth
0.8
0.4
0.2
0.2
33000
30089 Studient Updates
20008
40690
20000
20006
30009
40030
33000
20006
30009 Updatees
40800
Studknt Updattes
(d) PerfectMaze(M)
(c) SimpleCrossing
(f) SmallCorridor
Figure 12: ACCEL Solved-Rate Time Series. Solved rate progression MiniGrid tasks plotted
over 0-45k PPO updates.
To study long-horizon behavior, we ran single-seed, 45k PPO updates for both TRACED and AC- CEL in the MiniGrid environment. Both methods exhibit post- convergence oscillations success rate (i.e., solved rate). TRACED reaches near-peak success rapidly, but its performance subse- quently oscillates rather than remaining perfectly stable (Figure 11). The same post-peak fluctua- tions appear under the ACCEL curriculum (Figure 12): although ACCEL attains its maximum more
19

---

Published as a conference paper at ICLR 2026
slowly, it shows similar up-and-down pattern thereafter. These oscillations likely reflect inherent instability the RL policy on held-out levels, and may be further influenced by ACCEL's mutation dynamics, rather than pathology introduced by task- prioritizationn strategy. For this reason, report TRACED's performance at 10k updates (rather than 20k), before long-horizon oscillations confound comparisons. Mitigating these fluctuations in the student policy is an important direction for future work.
D VISUALIZING CURRICULUM DYNAMICS
(a) 2.5k, Low ATPL, Low Co- Co-Leamability
(b) 2.5k, Low ATPL, High Co- Lo-annrbability
(c) 2.5k, High ATPL, Low Co-Learnability
(d) 2.5k, High ATPL, High Co-Learnability
(c) 5k, Low ATPL, Low Co-Lcarnabilitt
(f) 5k, Low ATPL, High Co-l.carnability
(g) 5k, High ATPL, Low Co-Learability
(h) 5k, High ATPL, High Co-Learnability
Figure 13: Representative terrains from BipedalWalker selected by ATPL and co-learnability at two training stages. The top two rows show terrains after 2.5k PPO updates, and the bottom two rows after 5k updates.
Figure 13 illustrates the joint impact of ATPL and Co-Learnability on terrain selection at 2.5k and 5k PPO updates. ATPL alone captures the raw challenge level: low-ATPL terrains (first and third rows) remain relatively smooth, while high-ATPL terrains (second and fourth rows) feature larger gaps and steeper bumps. As training proceeds from 2.5k systematically harder, demonstrating TRACED's ability to ramp up difficulty in lockstep with the agent's improving skills. Co-LLearaability then refines this progression by filtering out extremes: low Co-L ee--baatbablityy (left column) tends to generate either trivial or overwhelmingly difficult levels that can stall learning, whereas high Co-Learnability (right column) favors intermediate-difficull terrains that transfer more effectively across tasks. Together, these visualizations confirm that ATPL drives steadily increasing complexity trajectory, while Co-Learnability smooths to sustain robust, transferable learning throughout the curriculum.
updates, the overall terrains become
20

---

Published as a conference paper at ICLR 2026
E LEVEL EVOLUTION
VISUALIZATION OF LEVEL EVOLUTION IN MINIGRID
The visualization of how the Minigrid environment evolves as the number of blocks increases (Fig-
14). Each step of the evolutionary process produces an edited level that has high learning efficiency.
Figure 14: Visualization of a single level's evolving progression in the MiniGrid environ- ment. Starting from top-left, ending bottom-right. This progress is automatically designed by TRACED algorithm.
E.2 EVOLUTION OF LEVELS IN BIPEDALWALKER
Figure 15 shows the complexity metric results trained by three methods, TRACED (Ours), ACCEL ATPL,, ACCEL. Starting with plain terrain (near zero point), all three methods guide levels with more complex terrain. With respect to (a) Stump height, (b) Stump height high, (e) Stair height step metries, the results show TRACED and ACCEL + ATPL quickly evolve levels compared to ACCEL. This rapid level increase leads to shorter wall-clock time and higher performance across various test environments.
TRACED (Qurs)
ACCEL ATPL
ACCEL
2.5
2.5
2.-
2.
25
24
(a) Stump height low
(b) Stump height high
(c) Stair height low
(d) Stair height high
25
(e) Stair height step
(f) Pit gap low
Pit gap high
(h) Roughness
Figure 15: Emergent Bipedal terrain complexity metrics. Aspect of (a) Stump height low, (b) Stump height high, and (e) Stair height step. complexity grows faster under TRACED (Ours, pink) or ACCEL + ATPL (brown) than under ACCEL (blue). The result is averaged over five random seeds. This faster ramp-up indicates that our curriculum more effectively escalates difficulty in lockstep with agent learning.
21

---

Published as a conference paper at ICLR 2026
E.3 VISUALIZATION OF LEVEL EVOLUTION IN WALKER
Figure 16 shows the visualization of how the environment evolves as the complexity of the task increases. The process starts from plain terrain and gradually evolves to level of terrain with increasingly complex parameters.
Figure 16: Visualization of the level evolving progression in the BipedalWalker environment. Starting from top-left, ending bottom-right. In this example, starting with plain terrain, the pits are created and their number increases, then the roughness increases, then stairs and stumps are created and their number, width, and height increase. This progress is automatically designed by our TRACED algorithm.
F AGENT TRAJECTORY VISUALIZATIONS ACROSS ENVIRONMENTS
F.1 MINIGRID
Figure 17: Agent trajectory visualization the PerfectMaze evaluation task. TRACED enables efficient path planning and robust generalization to challenging maze environments, as demonstrated by the agent's successful navigation to the goal (green).
F.2 BIPEDALWALKER
Figure 18: Agent trajectory visualization in the Bipedal Walkeraaoakrrrrrdcorre TRACED agent suc- cessfully overcomes various combined obstacles, including stairs, pit gaps, stumps, and roughness, demonstrating robust generalization to complex environments.
22

---

Published as a conference paper at ICLR 2026
G EFFICIENCY ANALYSIS
G.1 WALL-CLOCK TRAINING TIME IN BIPEDALWALKER
Table 8 reports wall-clock training times on the BipedalWalker domain, in hours (mean + s.c.) over five runs at 10k and 20k PPO updates. At 10k updates, TRACED requires 35.64 + 0.53 h, about 7% more than ACCEL's 33.26 1.17 h, yet achieves 22% higher mean solved rate (Section 4).
Table 8: Wall-Clock Training Time on BipkdalWalker. Average wall-clock duration for each algorithm
Domain
TRACED 10k ACCEL 10k ACCEL 20k
ADD 10k
ADD 20k
10k
PLR 20k
DR 10k
DR
BipedalWalker 35.64 = 0.53 33.26 :: 1.17 70.22 + 59 21.13 + 0.11 41.58 = 0.24 35.49 +: 1.07
71.01 2.17
18.38 0.1 37.03 +: 0.3
G.2 SAMPLE COMPLEXITY: ENVIRONMENT STEPS
Table 9 shows total environment steps required to achieve fixed number of PPO updates. TRACED matches ACCEL's sample complexity exactly, confirming that its superior generalization stems from improved curriculum design rather than additional data.
Table 9: Environment Steps. Total environment interactions (millions) for each method per given number of student PPO updates.
Environment
PPO Updates
PLR-
ADD
ACCEL
TRACED
MiniGrid
10k
82M
41M
93M
93M
MiniGrid
20k
165M
82M
185M
BipedalWalker
10k
165M
80M
174M
174M
BipedalWalker Walker
20k
329M
160M
347M
23

---

Published as a conference paper at ICLR 2026
H OVERALL WORKFLOW
Algorithm summarizes our overall UED procedure under the TRACED framework. We followed ACCEL (Parker-Holder al., 2022) in all respects except the procedure used compute task pri- ority. At each iteration, with probability Preplay the teacher enters the exploration phase by sampling a fresh level 9, executing the current policy a collect a trajectory, and computing its approximated regret
Regret(r) PVL(T) ATPL(T).
If the buffer is full, evict the lowest-priority task before appending. Otherwise, with probability Preplay the teacher enters the replay+mutation phase, drawing batch of B tasks from the buffer pro- portional to their TrskPriority scores, updating the policy each, and recomputing regret. We then select the mutate tasks with the smallest regret, mutate each via the editor, evaluate the new variant, and replace its parent in the buffer. Finally, for every modified task we recompute TaskDifficulty. CoLearrability, and PrioPiy (Eq. 7) before proceeding to the next timestep.
Algorithm UED Workflow with Preedictionn Loss and Co-Learnability
Given: policy ne level generator G, buffer capacity K, replay probability Proplay batch size B, mutation count N mutate, scaling factors
2: Initialize Task Buffer A f- 0, timestep f- 0
3: while policy has not converged do
4: Sample decision de Bernoulli (Preplay)
5: if d, then
Exploration phase
6: Sample new task 0 ~ g
7: Collect trajectory by executing n & (no gradient)
8:
Compute regret estimate
Regret(T) PVI(T) + a ATPL(T)
9:
Append buffer A (if K, remove lowest-priority)
10:
else
D Replay + Mutation phase
Sample batch {0x]e= from A w.p. TuskPriority(..]] for = 1... do
12:
13:
Collect trajectory тІ by executing Tे on 0₂
14:
Update policy & using rewards from т Compute Regret(Tx)
15:
16:
end for
17:
Select the Numutate tasks (0w) with smallest Regret(Tw) for each selected 0% do
18:
19:
i editor(@:.)
20:
Collect trajectory on 0 (no gradient)
Compute Regret(F)
22:
Replace Ow with 0
23:
end for
24:
end
25:
Buffer update:
26:
for each task i E A updated at / do
27:
Recompute Diffiullll () Recompute CoLearnability(i.. 1)
28:
Update TaskPriority(i. via Eq.
30:
end for
+ +++1
32:
end while
24

---

Published as a conference paper at ICLR 2026
1 IMPLEMENTATION DETAILS
1.1 MINIGRID ENVIRONMENT
SixteenRooms
SixteenRooms2
SmallCorridor
LargeCorridor
SimpleCrossing
FourRooms
Labyrinth
Labyrinth2
Maze
Maze2
Maze3
PerfectMaze
Figure 19: MiniGrid zero-shot environments used for evaluation. In SmallCorridor and LargeCorridor, the goal can appear in any of the corridor paths. SimpleCrossing and FourRooms are adapted from MiniGrid (Chevalier- Eehevalier-Boiseert et al., 2023), and PerfectMaze from REPAIRED (Jiang al., 2021a).
The partially observable navigation environment is designed 15 15 grid maze, based on MiniGrid (Chevalier-Boiss Boisvert et al., 2023). Each tile in the maze can be either an empty tile, wall, goal, the agent itself. The empty tile is navigable space through which the agent whereas the wall is an impassable obstacle that blocks the agent's movement. At the beginning of each episode, the initial position of the agent, the goal location, and the wall layout randomly initialized. Up to 60 walls can be placed throughout the maze, increasing navigational complexity. At each timestep. the agent receives 5 local observation, along with its current direction. The action space is defined as a discrete set of seven possible actions, although only three, turn left, turn right, and move forward, are relevant maze navigation. These actions are selected without masking the unused action outputs. A reward is provided when the agent successfully reaches the goal, calculated as 1 - max, where the number steps taken and Tmax = 250 denotes maximum allowed steps per episode. If the agent fails to reach the goal within the time limit, it does not receive a reward.
To evaluate performance in partially observable navigation, we include additional results on the Min- iGrid environments, covering a suite of challenging zero-shot tasks from prior UED work (Dennis et al., 2020; Jiang et al., 2021a). Figure 19 displays all evaluation tasks.
1.2 SIPEDALWALKER ENVIRONMENT
The environment is based on the BipedalWalkerHardde environment of the OpenAl gym (Brock- man et al., 2016). At each timestep. the agent receives a 24-dimensional observation, which in- cludes information such the hull angle and angular velocity, joint angles and speeds for the hips and knees, ground contact indicators for each foot, the robot's horizontal and vertical velocities, and lidar-based distance measurements the ground ahead. The action space is represented by a 4- dimensional vector that controls the torques applied to the robot's two hip joints and two knee joints. Rewards are structured encourage efficient and stable locomotion across the terrain. The agent receives positive rewards for processing while maintaining straight hull posture, with small penal- ties applied for energy expenditure to discourage unnecessary motor use. The maximum achievable score is 300. If the agent falls moves backward, the episode ends immediately, and a penalty of -100 is applied. The maximum episode length is 2000 timesteps. To introduce additional diffi- culty and test the robustness of the agent's 's locomotion policy, the environment includes variety of challenging terrain features. These include stairs, which consist of sequences of elevated steps that the agent must ascend descend; pit gaps, which are horizontal gaps which the agent must
25

---

Published as a conference paper at ICLR 2026
jump step over; stumps, which vertical obstacles with varying heights and widths that ob- struct movement; and surface roughness, which introduces uneven ground textures that can disrupt balance and foot placement.
We evaluate agents in the BipedalWalker-F environment, which features relatively smooth terrain, well as in the more demanding BipedalWalkert SipedalWalkerrarrdoeeewy which introduces variety of chal- lenging obstacles. The BipedalWalker-v3 focuses on basic locomotion and balance without signifi- cant terrain disturbances. Terrain in this environment does have obstacles such as stairs, pit gaps, and stumps, and only gentle slopes are generated by adding noise in the range of approximately -1 In contrast, Bipedal Hipedd/WalkeHHardcorre includes complex terrain elements such as stairs, pit gaps, stumps, and roughness, which require precise control and adaptive strategies. These obstacles are procedurally generated with randomized parameters. The stair height is randomly set to either +1 (ascending) -1 (descending), with the number of steps and step width randomly sampled be- tween 3-5 steps and 4-5 units, respectively. The pit width determined by sampling single integer between 3-5 units. Both the height and width of each stump sampled as single random integer between 1-3 units, ensuring the stumps are always square-shaped. Terrain roughness noise range is the same Bipedal Walker-v.
To further probe the agent's generalization capabilities, we include four targeted evaluation environ- ments that isolate specific terrain challenges: Stairs, PitGap, Stump, and Roughness. Stairs specifies a fixed stair height of units, with 5 steps and a step width between and 5. PitGap sets the pit width to exactly 5 units. Stump defines the stump height 2 units while allowing the stump width to vary between 1 and units. Finally, Roughness generates terrain by adding noise 5. Figure 20 displays all evaluation tasks.
(a) BipedalWalker-yy
(b) Bipedk/WalkcrHHaddoree2
(c) Stairs
(d) PitGap
(e) Stump
(f) Roughness
Evaluation Terrains in BipedalWalker. 6 held-out environments used sess zero-shot generalization: (a) BipedalWalker-v3 with gentle noise-induced slopes; (b) SipedalWWllkerHarddoeeww combining multiple obstacle types; (c) Stairs, fixed 5-step sequence requiring precise stepping; (d) PitGap, a 5-unit horizontal gap; (e) Stump, 2-unit tall obstacles with variable width; and (f) Roughness, continuous uneven ground generated by noise.
Figure 20:
1.3 NETWORK STRUCTURES
For partially observable navigation, the LSTM-based transition prediction model fe consists of three components: 1. an image encoder that compresses the input observation into a 128-dimensional latent embedding, 2. an LSTM module (hidden size 128, layer) that processes the concatenation of this embedding and the action a, 3. and an image decoder that reconstructs the predicted next observation š141 from the LSTM output. We adopt an LSTM here because recurrent architectures have proven effective at capturing temporal dependencies in transition and video-prediction tasks under partial observability (Ha & Schmidhuber, 2018: 8: Oh et al., 2015).
For walking in challenging terrain (BipedalWalker)) the model instead concatenates the raw state vector 8, with a, and feeds this into an LSTM (hidden size 128, layer); the recurrent output is then linearly mapped to the predicted next state 8,41.
Its instantaneous error is defined by
f1 8141 se+1 Il1
in MiniGrid environments,
l,
||141
S141l2.
in BilkdalWalker.
26

---

Published as a conference paper at ICLR 2026
We use L1 loss for MiniGrid because it preserves sharp edges and reduces blurring in image recon- struction (Zhao et al., 2016), while mean squared error is a standard, reliable choice for continuous state regression in locomotion domains (Mnih et al., 2015).
We adopt ACCEL's network architecture (Parker-Holke et al., 2022), differing only in the LSTM design choice. The PPO network serves the student agent in our system, directly learning opti- mize both the policy and value functions through interaction with the environment. The architecture follows the standard actor-critic structure where the actor head outputs an action distribution, and the critic head predicts the scalar value (ss).
For partially observable navigation, the input consists of 3-channel 5 local image observation and a directional scalar with dimension 4 indicating the agent's 'sss current orientation. The image is processed by a convolutional encoder with filter size of 16, kernel size of 3, and Rectified Linear Unit (ReLU) activations, followed by flattening. The directional scalar is passed through fully connected layer of size 5, and the resulting embedding is concatenated with the flattened image features. The combined feature vector is fed separately to the actor and critic heads, each consisting of fully connected layers of size [32, 32). The actor outputs a categorical distribution over discrete actions, while the critic produces scalar value estimate V88).
For walking challenging terrain (BipedalWalker), the input flat state vector of dimension 24. This input is processed through Multilayer Perceptron (MLP) with two hidden layers of 64 dimensions, followed by actor and critic heads. The actor head outputs the mean and standard deviation parameters of diagonal Gaussian distribution over continuous 4-dimensional action space, and the critic head outputs a scalar state value V(s). The PPO learning process optimizes a clipped surrogate policy loss with clip parameter 0.2 combined with value function loss.
J DIFFERENCE WITH FORMER STUDIES
J.1 DIFFERENCE WITH ACCEL
Our approach builds on ACCEL's evolutionary, regret-based curriculum design, refining both its regret estimator and its sampling criterion. Like ACCEL, we maintain level buffer and record each task's difficulty. However, instead of relying solely on Positive Value Loss (PVL) to approximate regret, we decompose regret into value error and transition-predictoo error and incorporate both components into our difficulty measure.
Furthermore, prior UED methods sample levels independently based solely their individual dif- ficulty, ignoring cross-tast task transfer effects. We address this with our Co-Leamabilityy metric, which quantifies how training their difficulty after replay. By integrating Co-Learrability into our priority score, we can prioritize tasks that not only challenge the agent but also deliver broad transfer benefits across the entire task space.
task influences regret others by measuring the average change in
J.2 DIFFERENCE WITH CENIE
CENIE introduces complementary curriculum strategy by explicitly measuring environmental nov- elty, rather than relying solely on regret signals as in PLR or ACCEL. It fits a Gaussian mixture model (GMM) to the agent's 's past trajectories and scores new tasks by how poorly the GMM explains them, thereby steering the agent toward unfamiliar regions of the state-action space. This model- agnostic approach can be applied on top of any UED framework, including PLR and ACCEL
However, CENIE's iiversity-driverr objective differs from ours. TRACED's primary goal is to ap- proximate task difficulty more faithfully, by decomposing regret into value and cransition-predictti errors, and to capture how training one task transfers to others via our Co-Learnabiliyy metric. While CENIE accounts for per-task novelty and regret, it ignores cross-task transfer effects. More- over, TRACED is agnostic to the choice of level generator or editor, meaning our method could be combined with CENIE's novelty scoring to yield a curriculum that balances both transfer- aware difficulty and environmental diversity.
27

---

Published as a conference paper at ICLR 2026
K RELATED WORKS
Unsupervised Environment Design (UED) defines a co-evolutionary framework in which teacher agent generates task instances for a student policy, selecting those tasks with high learning potential to promote robust generalization to unseen environments (Wang et al., 2019; 2020; Dennis et al,, 2020: Chung et al., 2024). PAIRED (Dennis et al., 2020) trains the teacher to maximize the regret between a protagonist and antagonist policy, causing the teacher to create increasingly challenging yet solvable environments. However, non-stationary task distributions and the high dimensionality of the task space impede convergence to optimal curricula. To mitigate these limitations, Mediratta et al. (2023) introduce entropy bonuses, alternative optimization algorithms,, and online behavioral cloning, and Clutr (Azad et al., 2023) employs variational autoencoder- based unsupervised task representation learning to compress the task manifold and yield more stable curricula.
Another line of work is based on Prioritized Level Replay (PLR) (Jiang et al., 2021b), which avoids training a teacher agent and instead randomly generates tasks while introducing replay buffer that stores previously generated tasks. This approach prioritizes tasks with high learning potential from the buffer to more effectively train the student agent. PLR- (Jiang al., 2021a) make improvement of PLR, which used stop-gradient on trajectories from newly generated tasks but updated only with replayed tasks from buffer. This leads better performance on unseen environments counterintu- itively. ACCEL (Parker-Holder et al., 2022) extends the PLR by implementing an evolutionary approach that makes small mutation to high-regret levels from the buffer. This evolutionary mecha- nism enables the development of progressively more complex challenges starting with simpler tasks. However, these methods (Jiang et al., 2021 b;a; Parker-Holder et al., 2022) approximate regret solely via value loss, thereby implicitly learn true environment dynamics that could improve regret estima- tion.
Moving beyond regret-based approaches, CENIE (Teoh et al., 2024) integrates novelty with regret to expose agents to more diverse learning situations. Using Gaussian Mixture Models, CENIE quan- tifies how much new task's trajectory differs from previous experiences stored in the buffer. This verricllu--awarenn
leads to better exploration and generalization. DIPLR (Li et al., 2023) intro- duces a diversity that quantifies the similarity between different levels by computing the Wasserstein distance between their occupancy distributions over state-action trajectories. MBeDED (Li et al., 2024) introduces the marginal benefit metric to quantify the performance gain of student policy from training on generated task. It compares a base policy (before training) and the updated stu- dent policy by measuring the difference in their expected returns on that task. SFL (Rutherford et al., 2024) assigns a learnability score to each level, computed from the empirical success rate achieved by evaluating the agent on sampled levels. Levels whose success rates fall in the intermediate range, neither too easy nor too difficult, are prioritized, guiding the agent toward tasks that are most con- ducive to further learning. A related idea appears in GoalGAN (Florensa et al., 2018), which is not UED method but similarly adapts task difficulty by training generative model to propose goals of suitable challenge. So far, to the best of our knowledge, there are no prior works that explicitly consider Co-Leaanability between tasks.
UED's benefit on robust generalization performance in unseen environments has led to its applica- tion in other domains. For Multi-Agent Reinforcement Learning, MAESTRO (Samvelyan et al., 2023) extends UED to competitive multi-agent settings by creating a regret-based curriculum over the joint environment and co-player space, leveraging self-play to generate opponents while train- ing agents robust to environment and co-player variations. In contrast, RACCOON (Erlebach & Cook, 2024) applies UED to cooperative scenarios. developing a curriculum that prioritizes high- regret partners from pre-trained partners to enhance collaboration. For meta-RL, GROOVE (Jack- son et al., 2023) suggested policy meta-optimization (PMO) introducing algorithmic regret (AR), which measures the performance gap between a meta-leamed optimizer and RL algorithms like A2C, creating curricula that identify informative environments for meta-training. DIVA (Costales & Nikolaidis, 2024) is the first method that extends UED to semi-supervised environment design, employing quality- -uality-diversity search to maintain a population of diverse training tasks in open-ended simulators, maximizing behavioral coverage. In sim-to-real settings, GCL (Wang et al., 2024) aligns the simulated curriculum with actual deployment tasks by sampling from woal-world task distribu- tions and adapting subsequent task generation based on the robot's past performance.
28

---

Published as a conference paper at ICLR 2026
Similar to UED works, Curriculum Reinforcement Learning (CRL) accelerates agent training by constructing a sequence of progressively challenging tasks rather than directly confronting the agent with a single, complex target task (Narvekar et al., 2020). Early approaches distinguished between fixed curricula in which task order is predefined and self-paced learning, in which task selection adapts dynamically based on the agent's learning progress (Klink et al., 2020). Modern CRL meth- ods have advanced this paradigm by framing curriculum generation as an inference process (Eimer et al., 2021; Klink et al., 2022). WAKER (Rigter et al., 2024) leverages reward-free curricula to train robust world models, thereby underscoring the versatility of self paced approaches in diverse learning scenarios. Akin to the concept underlying SFL (Rutherford et al., 2024), ProCuRL (Tzan- netos et al., 2023) operationalizes the pedagogical notion of the Zone of Proximal Development by using probability of success score-based scoring combined with softmax sampling to prioritize tasks of intermediate difficulty. However, these approaches assume access to the target task distribution, which conflicts with UED's core assumption of an unknown distribution.
L MORE DETAILS ON BASELINE ALGORITHMS
In Unsupervised Environment Design (UED). Domain Randomization (DR) constructs the curricu- lum by uniformly sampling tasks from the environment parameter space O Formally, DR samples tasks according to ~ p(0) where p(O) represents uniform distribution over the task parameter space. The agent is trained on these randomly sampled tasks.
Robust PLR (PLR-) (Jiang et al., 202 was introduced as an extension of the original PLR (Jiang et al., 2021b). While DR treats all tasks equally, PLR prioritizes tasks with high learning potential, maintaining a buffer A of previously encountered tasks for replay. When sampling new tasks, the agent's policy parameters
sop-gradientedd, meaning the policy is not updated trajectories collected from these newly sampled tasks. The collected trajectories are used to compute PVL scores to decide whether add the task the replay buffer. Policy updates are exclusively performed on tasks sampled from the replay buffer. By stopping the gradient on randomly sampled levels, PLR- ensures that the policy only updated on tasks specifically selected maximize regret, leading to more robust generalization compared to both DR and PLR unintuitively.
Adversarially Compounding Complexity by Editing Levels (ACCEL) (Parker-Holder et al.. 2022) actively evolves environments through an editing mechanism, allowing it to more efficiently explore the environment design space. This enables reusing the structure of sampled levels in the buffer for high-regret, rather than curating randomly sampled levels for high-regret. ACCEL maintains buffer A and employs a cycle of sampling, editing, and curation. The key insight of ACCEL that fitness function for evolution, enabling it to produce batches of
regret serves as a levels at the frontier of agent capabilities. The editing mechanism involves making small mutations to previously high-regret levels, which can operate directly on environment elements such as blocks in MiniGrid. This evolutionary process creates an expanding frontier that matches the agent's ' capa- bilities, starting with simple levels and progressively increasing in complexity. Like PLR ACCEL employs stop-gradient when evaluating new or edited levels to ensure theoretical guarantees.
Coverage- based Evaluation of Novelty In Environment (CENIE) (Teoh et al., 2024) introduces envi- ronment novelty as a complementary objective to regret in UED. CENIE quantifies environment nov- city through state-action space coverage derived from the agent's accumulated experiences across previous environments in its curriculum. The framework operates on the intuition that novel envi- ronment should induce unfamiliar experiences, pushing the student agent into unexplored regions of the state-action space. At the core of CENIE's implementation is the use of Gaussian Mixture Mod- els (GMMs) to model the distribution of state-action pairs from the agent's 's past experiences. Given a state-action buffer I containing pairs collected from previous environments, CENIE fits GMM with parameters Ar to represent this distribution. The novelty of candidate environment is then quantified by measuring the similarity between its newly observed state-action pairs and the learned distribution of past state-action experiences. CENIE integrates with existing UED algorithms by combining both novelty and regret into a unified priority score for environment selection.
Adversarial Environment Design via Regret-Guided Diffusson Models (ADD) (Chung et al., 2024) frames environment generation uniformly sampled tasks, a pretrained score network s, is guided by the gradient of a differentiable regret estimate, computed via a learned return critic, during reverse diffusion.
diffusion process steered by the agent's 's regret. Starting from
29

---

Published as a conference paper at ICLR 2026
In our empirical study, DR, PLR', and ACCEL were evaluated with the DCD codebase (Jiang al., 2022), and assessed ADD with the ADD codebase (Chung et al., 2024). CENIE's performance data were incorporated from its original publication, open-souree implementation was available.
M LIMITATIONS
As with any research, approach presents several limitations that highlight opportuiitss for future investigation:
Co-Learnability. In this paper, proposed Co- Co-Learnability, simple yet effective method. Follow- up studies could address these gaps by developing multi-step Co-Learnability estimators, incorpo- rating wetporttannewwighting observational co-learn signals with auxiliary models (e.g., task-conditioned value predictors) for stronger causal inference.
counterfactual techniques reduce sampling bias, and combining
ATPL. In environments with highly stochastic transitions, the ATPL signal (transition-preddice error) can become noisy, potentially reducing the fidelity of our regret approximation.
Sampling levels. We sampled a fixed number of the lowest-regret levels as easy tasks to mirror AC- CEL's approach and enable fair comparisons with baseline methods. However, this simple strategy leaves room to explore more advanced task-selection mechanisms.
Heuristic weighting. We introduced weighted approach regret approximation and task prioritiza- tion that relies on two key parameters a, PVL and ATPL in the regret approximation, and 8, which weights the relative importance of Co-Learnability against task difficulty. While these parameters were manually tuned in the current implementation and demonstrated effective results across envi- ronments, future work could explore more principled methods for automatically determining these weights.
Extension to other RI. algorithms. Our experiments have been conducted with PPO-based student agents. While this allows for fair comparisons with previous work, there is much broader range of algorithms that may interact differently with our regret-based curriculum. Off-policy methods such SAC (Haarnoj et al., 2018) 8) and TD3 (Fujimoto et al., 2018) feature distinct exploration strate- gies, which may yield different performance dynamics under our curriculum framework. Moreover, Model-based approaches like DreamerV3 (Hafner al., 2025) build world models for planning, offering complementary insights into curriculum design. Evaluating these methods under our cur- riculum framework remains important direction for future work.
Extend to other UED methods. We empirically demonstrated that TRACED yields more effec- tive curricula, thereby enhancing agents' generalization capabilities half the training cost. While our experiments focus on the ACCEL framework, future work will integrate our approach into al- ternative UED methods (PLR - (Jiang al., 2021a) and CENIE (Teoh al., 2024)) and conduct comprehensive experiments to assess its performance in these settings.
Evaluation in other domains. Our experimental validation has been conducted in Mini- Grid (Chevalier-Boisvertt et al., 2023; Dennis et al., 2020) and BipedalWalker (Brockman et al., 2016; Parker-Holder et al., 2022). Evaluating TRACED in other domains such as Car Rac- ing (Brockman et al., 2016; Jiang et al., 2021a), physical robotics applications (Mahmood et al., 2018), and reasoning task ARC (Chollet, 2019) would provide a more comprehensive assessment of the approach's generality and scalability across diverse settings.
N EXPERIMENTAL SETUP AND REPRODUCIBILITY
All experiments were conducted using Python 3.8.20 on Ubuntu 22.04.4 LTS. The hardware setup included an AMD EPYC 7543 32-core processor, 80GB of RAM, and an NVIDIA A100 GPU. Experiments
shared server with 8 GPUs, with each experiment using single GPU. We implemented all experiments in Python 3.8.20, using PyTorch(y1.95 1.9.0h/ll (1). The environment stack was built using MiniGrid (v1.0.1), Gym (v0.15.7).
30

---

Published as a conference paper at ICLR 2026
O LLM USAGE
We used a large language model (LLM) solely for language editing. Concretely, the LLM assisted with grammar and style polishing, LaTeX phrasing (e.g., equation and caption wording), and im- proving clarity and concision of author-writeen text. The LLM was not used to generate ideas, design algorithms, select hyperparameters, run experiments, analyze data, create figures/tables, write code, or produce mathematical results.
P HYPERPARAMETERS
Table 10 summarizes the hyperparameters used. Unless otherwise noted, values are adopted directly from the DCD repository (Jiang al., 2022). The only deviation from the DCD defaults is the number of PPO workers (see Appendix B.4). We tune two key weights, and B, on MiniGrid and BipedalWallers exploring a E (0.5, 1.0, 1.5) and 3 E (0.6, 0.8, 1.0).
Table 10: Hyperparameters used for training each method each environment.
HyperParameter
MiniGrid Bilkerl
PPO
Y
0.995
0.99
AGAE
0.95
0.9
PPO rollout length
256
2048
PPO epochs
5
PPO minibatches per epoch
32
PPO clip range
0.2
0.2
PPO number of workers
16
4
Adam learning rate
le-4
3e-4
Adam
le-5
le-5
PPO max gradient norm
0.5
0.5
PPO value clipping
True
False
Return normalization
False
True
Value loss coefficient
0.5
0.5
Student entropy coefficient
0.0
le-3
Generator entropy coefficient
0.0
1e-2
TRACED
ATPL weight,
1.0
1.5
Co-Leamability weight, ,
1.0
0.6
ACCEL
Replay rate, Preplay
0.8
0.9
Buffer size, K
4000
1000
Number of edits
3
Batch Size, B
4
4
Number of mutated tasks, Nuuuate
Temperature
0.3
0.1
Staleness coefficient, p
0.3
0.5
31

---

Published as a conference paper at ICLR 2026
Q NUMERICAL RESULTS
Q.1 MINIGRID ENVIRONMENT
Table 11: MiniGrid Zero-Shot Solved Rates. Bold indicates the best result per task; underline
indicates the second-best.
Environment
Update
DR
PLR
ADD
ACCEL
TRACED
10k
0.4 0.12
0.81
0.06
0.1
0.76
0.53 0.14
16Rooms
0.51 0.13
0.64
0.65 0.1
10k
0.1 + 0.09
0.11
0.14
0.48 + 0.13
0.58 0.13
16Rooms2
20k
0.27 0.11
0.15
0.18
0.14
10k
0.58 0.05
0.03
0.63
0.81 0.03
0.85 0.03
SimpleCrossing
0.73 1: 0.02
0.8
0.74
0.85 0.02
10k
0.32 1: 0.04
0.04
0.01
0.39
0.46 0.02
0.46 0.02
FourRooms
20k
0.02
0.00
0.61
0.49 0.03
10k
0.07
0.4 0.13
0.37 0.14
0.49 0.13
SmallCorridor
20k
0.74
0.11
0.22 0.74
10k
0.36 0.13
0.13
0.35
0.44
0.43 = 0.11
LargeCorridor
20k
0.54 0.13
0.11
0.72
0.12
10k
0.1 0.1
0.15
0.22
0.15
0.93 0.03
Labyrinth
0.16
0.06
0.9
0.13
0.1 + 0.1
0.13
0.0
0.52
0.96 0.03
Labyrinth2
20k
0.18 + 0.12
0.15
0.14
0.78 + 0.13
10k
0.02 + 0.01
0.1
0.02
0.13
0.7 0.1
Maze
20k
0.1 0.1
0.16
0.2
0.59 0.14
0.19 + 0.12 0.12
0.14
0.08
0.44 - 0.15
0.1
Maze2
20k
0.16 1 0.11
0.14
0.28 0.1
0.65 + 0.13
10k
0.27 1 0.13
0.57
0.13
0.2
0.78 + 0.13
0.81 0.06
Maze3
20k
0.46 1 0.14
0.04
0.54
0.86 1 0.09
1 0.02
0.05
0.17
0.41 0.05
0.64
PerfectMaze(M)
20k
0.2 1 0.05
0.55
1 0.08
0.36 0.08
0.53 1 0.08
10k
0.23 = 0.05
0,45 0.04
0.28
0.54 0.03
0.66 0.03
Mean
20k
0.41 1 0.03
0.65 0.04
0.55 1 0.04
0.6 1 0.05
Table 11 reports per-task zero-shot solved rates on twelve held-out MiniGrid mazes, averaged over 10 seeds (mean + s.e.). following Agarwal et al. (2021). We compare TRACED 10k updates against DR, PLR ACCEL, and ADD (each at 10k and 20k). At 10k, TRACED achieves the high- est solved rate in six mazes (16Rooms2, SimpleCrossing. Labyrinth, Labyrinth2, Maze, Perfect- Maze(M)) and the second-best in one maze (Maze2). Averaged across all twelve mazes, TRACED attains solved rate of 0.66, outperforming all baseline configurations.
Table 12: MiniGrid Ablation Results. Bold indicates the best result per task; underline indicates the second-best.
Environment
ACCEL 10k
TRACED ATPL 10k
TRACED CL 10k
TRACED 10k
16Rooms
0.7 0.19
0.72 + 0.14
0.91 + 0.06
0.79 + 0.19
16Rooms2
0.44 1 0.17
0.01 1 0.01
0.79 1: 0.17
0.72 - 0.17
SimpleCrossing
0.68 1
0.86 0.04
0.89 0.01
FourRooms
0.46 + 0.04
0,36 1 0.02
0.48 1. 0.04
0.47 1 0.02
SmallCorridor
0.03 + 0.03
0.4
A.2
0.49 1 0.17
LargeCorridor
0.11 0.1
0.42
0.65 0.21
0.5 0.14
Labyrinth
0.4
0.2
1.0
Labyrinth2
0.88 + 0.1
0.16 0.11 0.11
0.62 + 0.18
0.98 = 0.01
Maze
0.42 + 0.24
0.29 + 0.19
0.63 0.2
0.59 + 0.17
Maze2
0.42 + 0.24
0.3
0.41 + 0.15
0.42 0.19
Maze3
+ 0.2
0.68 +
0.86 0.12
0.86 - 0.07
PerfectMaze(M)
0.33 + 0.04
0,34 + 0.02
0.53 + 0.07
0.66 - 0.11
Mean
0.49 + 0.04
0.4 + 0.04
0.65 + 0.03
0.7 0.04
32

---

Published as a conference paper at ICLR 2026
Table 12 presents zero-shot solved rates twelve held-out MiniGrid mazes for TRACED and its ablations at 10k updates, averaged over 10 seeds (mean = s.c.). Full TRACED achieves the highest score in six mazes (SimpleCrossing. Labyrimth, Labyrinth2. Maze3, PerfectMazeeMM), and Four- Rooms) and ranks second the remaining six, yielding mean solved rate of 0.70 and outperform- ing every variant. These results indicate that both the caansitionprrdiictinn emror and Co-Learnability are critical to TRACED's strong, consistent performance across diverse tasks.
Table 13: PerfectMaze Zero-Shot Solved Rates. Bold indicates the best result per environment; underline indicates the second-best
Environment
Update
DR
PLR-
ADD
ACCEL
TRACED
10k
0.0 0.0
0.02 1 0.01
0.04::0000
0.09 1 0.03
0.27 0.07
PerfectMazz(Large)
20k
0.02 0.01
0.09
0.1
0.20 0.08
10k
0.01
0.02 0.02
PcrlcctMazz(XL))
20k
0.0
0.12 0.09
0.14 0.09
0.09
Table 13 compares zero-shot solved rates of TRACED against DR, PLR ADD, and ACCEL on two large-scale PerfectMaze environments: PerfectMazeLargg and PerfectMazeXL, averaged over 10 seeds (mean + s.e.). After 10k updates, TRACED achieves the highest success rate on Perfect- MazeLarge (27% + 7%) and the third-highest on PerfectMazeXL. (10% + 4%), matching ADD 20k. These results underscore TRACED's ability to scale to extreme maze sizes.
Median
IQM
Moan
Optimality Gap
ACCEL 20k
ACCEL 10k I
ADD 20k-
PLR 20k
PLR 10k
DR 20k
0.3 0.00
Score
(a) PerfectMazeeI.
Mediann
IQM
Mean
Optimality Gap
TRACED (Ours)
ACCEL 20k
ACCEL 10k-
ADD 20k
PLR 10k
DR 20k
DR 10k
0.15
0.00
0.00
0.30
0.75
0.90
(b) PerfectMazeLarge
Figure 21: Aggregate zero-shot performance PerfectMaze. Full metric curves (Median, IQM, Mean, Optimality Gap) for PerfectMazeXLL (top) and PerfectMazeLarge (bottom).
Figure presents the full aggregate metrics for both PerfectMaze benchmarks. Despite the high variance inherent to these large-scale tasks, TRACED achieves the strongest 10k performance and closely matches the best 20k performance among all baselines.
33

---

Published as a conference paper at ICLR 2026
Q.2 BIPEDAL ENVIRONMENT
Table 14 compares TRACED's zero-shot returns with DR, PLR- ADD, ACCEL, and ACCEL- CENIE six BipedalWalker terrains, averaged five seeds (mean + s.e.). ACCEL-CENIE is estimated by applying the ACCEL-tO-CENIE performance ratio reported in Teoh et al. (2024) to our ACCEL implementation. At 10k updates, TRACED achieves the highest mean return on three terrains (Basic, Hardcore, and Stump) and attains an overall mean of 89.95 + 31.72, outperforming all baselines.
Table 14: Waleee Zero-Shot Test Returns. Bold indicates the best result per terrain; underline indicates the second-best
Environment
Update
DR
ADD
ACCEL
ACCEL-CENTIR
TRACED
Basic
112.56
131.63 + 56.58
63.72
273.56
293.67 +
20k
68.17 + 44.71
97.67 61.73
63.64 1664-00 62.71
281.85 3.72
275.04 = 3.19
10k
-19667 = 7.35
-17.36 + 5,99
3.83 9.07
37.59
15.0
66.83 + 17.48
86.83 + 17.96
Hardcore
10k
-17.6 7.21
-2.23
7.16
-5.87 9.07
-38.71 + 10.54
-30.4 + 8.15
-29.0 + 10.4
Stairs
20%
99.11
7.67
-10.2 4.5
9.22
-46.44 5.78
36.39
11.48
PdCaap
10k
34.39
15.66
46.21
15.69
-17.8 = 13.82
65.07
7.57
39.81
18:75
-39.26 + 11.42
20L
.6.03 + 10.98
-48.72
12.23
-7.65 7.52
64.89 + 18.93
-5.922 33.9
Stump
20k
-25.52
12.39
-23661 2.866
3.26 + 19.1
-67.18
15.56
-46.34
176.21
10%
0.66 1: 12.01
3.55 9.991
20.61 1: 13.78
161.72
28.36
174,92 1: 2.25
193.29 1: 21.6
Roughness
224.4
10k.
2.54
15.44
6.1 = 10.69
14.4 + 14.05
49.67 + 11.24
64.18
89.95
12.95
20k
-1.55
8.83
-1.89
8.93
14.63 1: 21.99
62.69
1:8.9
75.81
Table 15 reports zero-shot solved rates across six BipedalWalker terrains for DR, PLR- ADD, AC- CEL, and TRACED, averaged over five seeds. trajectory is considered "solved" if its return ex- ceeds 230. At 10k updates, TRACED achieves the highest solved rate on five of the six tasks (Basic, Hardcore, Stairs, PitGap, Stump) and ranks second on Roughness, yielding an overall mean of 0.36, substantially higher than ACCEL's 0.29 and the other baselines. No baseline matches TRACED's combined efficiency and reliability in zero-shot generalization.
Table 15: BipedalWalker Zero-Shot Solved Rates. Bold indicates the best per terrain; underline indicates the second-best
Environment
Update
DR
PLR
ADD 0.34 +
ACCEL
TRACED
10k
0.35 + 0.2
0,43 = 0.21
0.34
0.98 = 0.02
1.00 0.0
Basic
20k
0.16 + 0.13
0.35 + 0.22
0.2
0.99 0.0
0.0 0.0
0.0
0.01
0.15 0.03
0.28 + 0.05
Hardcore
20k
0.0
0.0
0.04
0.23 = 0.08
10k
0.0
0.0
0.0
0.03 = 0.02
0.03 1 0.02
Stairs
20k
0.0
0.0
0.0
0.03 0.01
10k
0.0
0.0
0.0
0.0 0.0
0.02 0.01
PitGap
20k
0.0
0.0
0.0
0.02 = 0.02
10k
0.0
0.0
0.0
0.0 0.0
0.18 + 0.12
Stump
20k
0.0
0.0 0.0
0.0 0.02
10k
0.01 + 0.01
0.01
0.01
0.56 0.1
0.65 1 0.08
Roughness
20k
0.0 +
0.0 +
0.03 0.03
0.03
10k
0.06 = 0.04
0.07 = 0.04
0.06 0.04
0.29 = 0.02 0.02
0.36 - 0.03
Mean
20k
0.03 + 0.02
0,06 = 0.04
0.05 + 0.05
0.34 = 0.03
34

---

Published as a conference paper at ICLR 2026
R COMPARISON WITH SFL
TRACED
SFL
PLR PLR-(RobustPLR)
Aeg Win Halk on Vie WOACAA 0% Lavale
Mean Win Rate Evallaatio set
80
60
0.4
20
0~
1%
100%
0
1k
3k
4k
Student PPO Updates
(a) CVRR across a levels.
(b) Mean win rate on the evaluation set.
Figure 22: TRACED vs. SFL and Robust PLR on multi-agent JaxNav. TRACED consistently
outperforms Robust PLR and achieves performance comparable to across all metrics.
Sampling for Learnability (SFL.) (Rutherford al., 2024) learnability- UED method that prioritizes levels with intermediate difficulty by selecting tasks with high learnability scores, com- puted as p(1 - p) where p is the agent's empirical success rate on a given level obtained from rollouts.
We evaluate TRACED on the multi-agent JaxNav benchmark following the evaluation protocol in- troduced in Rutherford et al. (2024), including CVaR and mean win rate computed over sampled evaluation levels. While the original SFL experiments trained basclines for 22,850 PPO updates, perform comparison using 4,550 updates for computational efficiency. This training regime corresponds to a phase in which SFL is reported to exhibit strong performance relative to other UED baselines (Rutherford al., 2024). Aside from the inclusion of TRACED, all training and evalua- tion details (e.g., level sampling, CVaR estimation, and construction of evaluation sets) match those in Rutherford et al. (2024). Results averaged
three seeds.
Figure 22 shows CVaR across several risk levels and the mean win rate on the evaluation set. In addi- tion SFL. we include PLR (Robust PLR), the strongest baseline used in Rutherford al. (2024). TRACED consistently outperforms Robust PLR across all CVaR levels and achieves performance comparable SFL. in both CVaR and mean win rate. Notably, TRACED attains this performance without relying any learmbilliy-driver evaluation during training.
These results suggest that TRACED captures many of the benefits of learnability- curricula while depending solely regret-based difficulty signal. Incorporating SFL-style evaluation tools, such as those used quantify Co-Learnability, may further enhance TRACED's performance in complex multi-agent settings.
35

---

Published as a conference paper at ICLR 2026
S
TEMPORAL CONSISTENCY OF CO-LEARNABILLTT
1.5
1.0
0.5
0.0
-0.5
t step Co-Learnability
step Co-Learnability
-1.0
0
500
1000
1500
2000
Student PPO Updates
Figure 23: Temporal consistency of Co-Learnability. Shadow testing produces aligned Co- Learnability sequences, enabling direct comparison of CoLearnsbility and CoLearnability, 1). The two signals exhibit positive correlation throughout training.
To examine whether training on tasks with high Co-Learaailityy at time t continues to facilitate progress at time 1+1, we quantify the temporal consistency Co-Learnability values. key challenge is that Co-Learnability is only computed for tasks selected by the curriculum at each step, resulting in irregularly sampled time series in which many tasks are not evaluated at both and f++1. This prevents direct computation of temporal correlation.
To obtain umee-alinned Co-Learnability estimates, we apply a shadow-testing procedure. Let Le denote the indices of levels selected by the curriculum at timestep f. After the update on Lt, we clone the agent's parameters to construct a shadow agent. While the main learner proceeds normally (so that Lt+11 may differ from Lt), the shadow agent is forced to replay the same levels by setting L L. At the next timestep, the shadow agent resumes standard TRACED updates without further intervention. This procedure yields aligned pairs of Co-Learnability values, CoLearnability, (!) and CoLearnability, (t+ 1), for the same set of levels across all timesteps. enabling direct temporal comparison.
Figure 23 shows the resulting time series of Co-Learnability at steps t and + 1, averaged over three random seeds on multi-agent JaxNav. Although both signals exhibit substantial variance early in training, they converge toward small positive values as the policy improves and performance becomes more uniform across levels. The temporal correlation between the two estimates is sum- marized below:
Pearson correlation: 0.3998 (p 3.9 10 10- 87)
Spearman correlation: 0.2013 (p R 5.4 x 10-22)
Time-averaged Co-Learnability at step 1: 0.0547
Hime-averaged Co- Co-Learnability at step 1+11: 1: 0.0473
The slightly lower mean at step t++1 expected, as Co-Learnability values naturally decrease over training due overall improvement across levels. The positive correlations indicate that tasks hibiting higher Co-Leearabillity at time / tend to retain elevated Co-Learnability at f. f++,, suggesting mild but non-neglig temporal persistency.
36


Reviews:
[{"review_id": "u6U1rjIL72", "reviewer": "Reviewer_3WBM", "summary": "The authors propose TRACED, a novel curriculum selection criterion for Unsupervised Environment Design methods. TRACED consists of a novel, transition-aware regret approximation and adds a co-learnability term. They evaluate TRACED in standard UED benchmarks. They provide an ablation analysis over their proposed changes and additional analyses over the curricula differences between existing methods and TRACED. They claim to show improved performance over existing methods.", "questions": "1. Could you please clarify the error bars for each figure? For example, in Figure 5, what is the shaded area for the median or for the mean?\n2. Could you please change the y-axis tick size in Figure 7?\n3. Could you please clarify the performance differences between SFL's PLR and the author's implementation?\n4. The reviewer typically tries to avoid suggesting extra experiments. However, given that MultiAgent JaxNav has been released for at least a year and it has been demonstrated that most existing methods perform worse than DR on JaxNav, I believe it's only fair to request an evaluation of TRACED on JaxNav against SFL and other existing methods. This is especially true if the authors claim to beat the \"state-of-the-art\" CENIE (line 67, 251, 475).\n5. Could you clarify how the ATPL loss term is calculated? The reviewer is unsure if the LSTM that's used for the transition prediction is also the backbone model used to calculate the value function? Or is the LSTM transition prediction model a completely separate network and no weights are shared with he value function? The authors state in the appendix, line 1246, that they differ only in the LSTM design choice. Could they clarify what they mean?\n\nTo summarise, the paper is overall pretty solid, and the idea of including the trajectory loss to capture the distribution difference is definitely interesting. The paper may feel somewhat incremental, but that doesn't detract from its solid execution. While it's nice to know that the transition loss and co-learnability influence performance, it lacks a really in-depth explanation of why co-learnability or transition loss improves performance. The reviewer is looking forward to the rebuttal period and hearing back from the authors.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Overall, the writing is easy to follow and straightforward.\n2. The transition-aware regret approximation is well motivated.\n3. The notation is simple, and the definitions (Section 3.2) are easy to follow.\n4. The figures are mainly well formatted and readable.\n5. The authors provide fair computational comparisons and a wall-clock time comparison with most existing methods.", "weaknesses": "1. The authors do not rely on novel analysis tools as proposed by SFL [1], which would allow the authors to strengthen their claim that TRACED improves performance over existing methods. For example, the authors could have analysed CVaR to show robustness to worst-case levels. Similarly, SFL provides density maps, such as those in Figures 4 and 6 of the SFL paper, which would strengthen the claim of TRACED that they improve performance. It is also unclear to the reviewer why they do not compare their method with SFL. The authors state that SFL does not outperform PLR; however, this seems directly contradicted by the authors, as seen in Figure 7a and Figure 14b.\n2. There appears to be some performance difference between PLR results reported at 10k in TRACED and SFT. In SFT, it appears that PLR can achieve a mean success rate of over 0.8 on the Minigrid evaluation set at 4k PPO update steps. In TRACED, the reported performance at 10k update steps is around 0.45. How can these performance differences be consolidated?\n\n\n## Clarity\n1. The authors could do a more thorough job of properly reporting statistically significant results and be more transparent in what they report. For example, Figure 7 present mean and standard deviation over clearly heavily skewed results, where standard deviation is not particularly meaningful, e.g., (12% +/- 28%). Again, median and IQR would have been more appropriate.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "CiSjDAad4F", "reviewer": "Reviewer_S2xS", "summary": "The paper proposes TRACED (transition-aware regret approximation with co-learnability for environment design), an unsupervised environment design framework based on not only positive value loss (PVL) but also average transition prediction loss (ATPL) and co-learnability. On MiniGrid and BipedalWalker, the method achieves strong performance with relatively few PPO updates.", "questions": "Does training on tasks with high co-learnability at time $k$ continue to accelerate progress on other tasks at subsequent times? Could you quantify this temporal persistency of co-learnability? (e.g., reporting the covariance between $\\mathrm{CoLearnability}_i(k)$ and $\\mathrm{CoLearnability}_i(k+1)$)", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "By introducing an intuitive transition-prediction loss and co-learnability metric, the method yields strong empirical gains with inexpensive changes.", "weaknesses": "* While co-learnability is interesting and intuitive, the paper lacks theoretical analysis or guarantees.\n* Despite its stochastic dynamics formulation, ATPL is computed based on deterministic predictions. For state–action pairs with high aleatoric stochasticity, the next state is inherently unpredictable, so ATPL can be large even when the future-value gap is negligible.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "IAywNbxIpy", "reviewer": "Reviewer_y3M6", "summary": "The paper studies the unsupervised environment design (UED) problem, where a teacher adaptively generates tasks and a student learns a policy from them. The authors identify a limitation in existing UED methods: their learning potential (task difficulty) measures fail to capture the mismatch between learned and true dynamics when approximating regret. To address this, the authors refine regret estimation by augmenting the positive value loss with a transition-prediction error term. Based on the refined regret and a co-learnability metric (measuring how training on one task affects others), they propose a new curriculum strategy called TRACED. Empirical results on MiniGrid and BipedalWalker demonstrate the efficacy of TRACED, supported by thorough ablation studies and wall-clock time comparisons.", "questions": "clarification question: the learned policy $\\pi_\\phi$ is not conditioned task/environment parameter $\\theta$, but rather adapts through trajectory conditioning (i.e., non-stationary behavior), right?\n\nLines 268-269 mention post-convergence oscillations in long-horizon MiniGrid runs for TRACED and ACCEL. How is early stopping handled in practice-by evaluating on a validation set and stopping when returns plateau?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is generally well written and provides a solid review of related work.\n\nProposes a novel and computationally efficient curriculum strategy for UED that achieves competitive performance without additional overhead.\n\nIncludes systematic empirical evaluation, with detailed ablation studies and reporting of wall-clock time.", "weaknesses": "Clarity of Section 3.2 could be improved: \n- co-learnability term in Eq. (7) requires one-step lookahead in the curriculum\n- task-difficulty $(i, t)$ defined as the regret approximation of the task $i$ when last sampled before time $t$\n- co-learnability $(i, t)$ computed when task $i$ was last drawn before time $t-1$\n- Please clarify why the rank transform prevents outliers from dominating the sampling distribution.\n\nMissing discussion of ZPD-based curriculum strategies (e.g., Florensa et al., 2018; Tzannetos et al., 2023).\n\nSFL was excluded as a baseline due to a lack of advantage in MiniGrid, but in other environments, SFL has been reported to outperform PLR. Are experiments on those domains prohibitively expensive (if so, this is understandable)?\n\nFlorensa et al., 2018: Automatic Goal Generation for Reinforcement Learning Agents.\n\nTzannetos et al., 2023: Proximal Curriculum for Reinforcement Learning Agents.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "WXqOFqpEgJ", "reviewer": "Reviewer_mbPu", "summary": "This paper focuses on the problem of Unsupervised Environment Design (UED)  by improving the environment sampling strategy. For instance, it enhances the regret estimation metric by incorporating the model's transition-prediction error , and proposes a 'Co-Learnability' metric. These contributions are designed to efficiently sample environment tasks with high learning potential , and the experiments demonstrate that this method effectively improves efficiency.", "questions": "1. Although the authors attempt to use Equation (2) to illustrate their insight for introducing ATPL, there is no theoretical proof of the relationship between ATPL and term (iii) . I believe it would be more convincing if the paper could show the progression curve of regret during training, both with and without the ATPL component.\n\n2. I have concern about the reconstruction loss. The performance improvement from ATPL stems from introducing dynamics modeling into the loop. Is it possible that introducing the dynamics model directly on the student agent (e.g., as an auxiliary loss) would be more direct and potentially yield even better results?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper's core insight is introduced very clearly, allowing the reader to easily follow the authors' thought process and understand the proposed method. The writing quality is high.\n\n2. The concept of \"Co-Learnability\" is novel and interesting, and the paper provides a helpful visual analysis to support it . This idea appears to be a promising direction for multi-task generalization in reinforcement learning and deserves further investigation.\n\n3. The experimental analysis is both thorough and solid, supported by sufficient ablation studies and insightful visualizations.", "weaknesses": "1. The novelty of the contributions appears limited. The use of a transition-prediction (reconstruction) loss is a well-established technique in RL, and the method itself is an incremental improvement upon the existing frameworks.\n\n2. The estimation of 'Co-Learnability' is relatively coarse. As it is highly dependent on the sampling of the batch $\\mathcal{T}$, its stability is a concern. The justification for using ATPL as a proxy for the 'Future value gap' (term iii in Eq. 2) lacks sufficient theoretical backing or direct experimental validation; it appears to be a heuristic choice rather than a formally derived approximation.\n\n3. The improvement in performance appears relatively limited, even though the sample efficiency has increased. Moreover, the experiments are conducted in relatively simple envs (MiniGrid and Bipedal Walker) , which calls into question the practical to more complex tasks .", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)