Research map / Reinforcement learning / Visual and representation RL
No Regrets: Investigating and Improving Regret Approximations for Curriculum Discovery
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that regret approximations used by UED methods (PVL, MaxMC) track success rate rather than regret or learnability, and proposes Sampling For Learnability (SFL), which trains on levels with success rate p(1-p) high, evaluated with a CVaR-based adversarial protocol on JaxNav, Minigrid and XLand-Minigrid.
Problem
Unsupervised environment design methods use regret approximations (PVL, MaxMC) to prioritise training levels, but these approximations may not identify levels where the agent can sometimes but not always succeed, so much experience comes from already-mastered levels.
Approach
Score levels by learnability p(1-p), estimated by rolling out the current policy on randomly sampled levels, and train on a buffer of the top-K learnable levels mixed with fresh random levels; a CVaR-style evaluation measures robustness on the worst alpha% of sampled solvable levels.
Key results
- SFL achieves higher CVaR of success than DR, PLR and ACCEL on single-agent JaxNav across a wide range of alpha values, matching only the oracle Perfect Regret.
- On Minigrid, SFL significantly outperforms all baselines on the adversarial (worst-case) evaluation while performing similarly on the hand-designed test set.
- Correlation analysis shows MaxMC and PVL scores track success rate rather than learnability, and PLR/ACCEL buffers have very low average learnability (about 0.01-0.02).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Select levels by learnability instead of sampling all candidate levels | SFL on JaxNav · JaxNav level buffers | Learnability (Mean): 0.01 (0.00) -> 0.22 (0.01) | Helped |
| Select levels by learnability instead of sampling all candidate levels | SFL on JaxNav · JaxNav level buffers | Success (Mean): 0.69 (0.01) -> 0.59 (0.02) | Hurt |
| Train with learnability-based level selection | SFL · Single-agent JaxNav | CVaR of success | Helped |
| Train with learnability-based level selection | SFL · Multi-agent JaxNav | Success | Helped |
| Train with learnability-based level selection | SFL · Minigrid | CVaR of success | Helped |
| Train with learnability-based level selection | SFL · XLand-Minigrid high-3m | CVaR of success | Helped |
| Prioritize levels with PVL or MaxMC regret approximations | PLR and ACCEL · JaxNav level buffers | Learnability (Mean) | Hurt |
Surprising findings
- Regret approximations (MaxMC, PVL) correlate with success rate rather than with regret or learnability, so UED buffers mostly contain already-solved levels.
- Unrestricted-sampling Perfect Regret performs poorly because it prioritises unsolvable levels.
Limitations
- Only applicable to deterministic binary-outcome domains, as the learnability score relies on Bernoulli success.
- Requires additional environment rollouts to fill the learnability buffer, which can be costly outside JAX.
- Random level generation may be infeasible when the environment space is vast or valid levels are rare.
Experimental setup
Datasets: Minigrid levels XLand-Minigrid high-3m rulesets JaxNav randomly generated levels
Benchmarks: JaxNav hand-designed test set Minigrid hand-designed holdout levels XLand-Minigrid evaluation set
Metrics: CVaR of success rate at alpha levels mean success rate domination heatmap episodic return
Baselines: Domain Randomisation PLR (PVL) PLR (MaxMC) ACCEL (MaxMC) Robust PLR
Builds on: Unsupervised Environment Design Prioritised Level Replay ACCEL PPO JaxUED
Closest papers by meaning
- Improving Regret Approximation for Unsupervised Dynamic Environment Generation (NeurIPS 2025 · similarity 0.93)
- Improving Environment Novelty Quantification for Effective Unsupervised Environment Design (NeurIPS 2024 · similarity 0.91)
- Marginal Benefit Driven RL Teacher for Unsupervised Environment Design (AAAI 2025 · similarity 0.90)
- Refining Minimax Regret for Unsupervised Environment Design (ICML 2024 · similarity 0.90)
- Adversarial Environment Design via Regret-Guided Diffusion Models (NeurIPS 2024 · similarity 0.90)
- Reward-Free Curricula for Training Robust World Models (ICLR 2024 · similarity 0.90)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.