Summary
Prior UED methods (PAIRED, PLR, ACCEL) only have robustness guarantees if the teacher–student game reaches a Nash equilibrium, and their nonconvex–nonconcave objectives give no reason to expect it will. This paper reframes UED as min–max optimisation over the agent’s parameters and an adversary that holds a categorical distribution over a level buffer, with an entropy regulariser that makes the objective nonconvex–strongly-concave. Two-timescale gradient descent-ascent then provably converges to a first-order Nash equilibrium in the zero-sum (regret) case. Because true regret is intractable, the practical algorithm NCC generalises the learnability score (variance of agent success) from binary-outcome domains to arbitrary deterministic ones. NCC beats the strongest prior UED baselines on two of three JAX environments (Craftax, XLand-MiniGrid, Minigrid), including on worst-case (α-CVaR) evaluation.
Key points
- Reformulation: minimax regret = expected regret under a categorical level distribution y; adding an entropy term αH(y) makes the objective strongly concave in y, enabling convergence proofs.
- First convergence guarantee in UED: two-timescale GDA with separated learning rates converges to an ε-first-order NE (via Lin et al. 2020), rather than assuming NE is reached.
- Argues the normal-form-game analysis of PAIRED does not describe practice: stochastic neural policies trained with PPO make the real objective nonconvex–nonconcave.
- Score function: generalised learnability = variance of success, extending Rutherford et al. (2024) beyond deterministic binary outcomes; regret is intractable since it needs the optimal policy per level.
- Practical NCC loop: agent trains on levels sampled from y; adversary updates y from scores on the whole buffer; a static buffer worked best in Craftax.
- Empirics: outperforms PLR-MaxMC and other baselines on Craftax and XLand-MiniGrid; competitive on Minigrid (the only domain with a regret oracle); robust on α-CVaR worst-case levels.
Relevance
- Open-Endedness — the current (2025) theoretical state of UED: replaces “guarantees at equilibrium” with an actual convergence result and moves the score function from regret to learnability; the newest entry in the UED lineage from Emergent Complexity and Zero-shot Transfer via Unsupervised Environment Design through Evolving Curricula with Regret-Based Environment Design.
- Unsupervised Environment Design — home concept since 2026-09-10
Notes
(batch ingest; no notes yet)