Research map / Reinforcement learning / Visual and representation RL
Improving Regret Approximation for Unsupervised Dynamic Environment Generation
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.
Proposes DEGen, a teacher that generates environment cells only as the student observes them (dense generator reward), plus Maximised Negative Advantage (MNA), a new regret approximation, for scaling unsupervised environment design in minigrid variants.
Problem
Unsupervised environment design (UED) struggles to find rare but hard levels (e.g., key-and-door mazes) and to train learnt level generators in larger environments, due to sparse, long-horizon credit assignment and poor regret approximations.
Approach
Generate the level incrementally as the student observes it so the teacher receives dense per-segment rewards derived from a regret approximation, and score levels with MNA, the mean of a maximised n-step negative advantage (lambda-return style) multiplied by a solvability indicator.
Key results
- On Key Minigrid 21x21, DEGen with MNA reaches a mean solve rate of 0.80 ± 0.03 versus 0.43 for PLR-MNA and 0.31 for ACCEL-MNA.
- On Key Minigrid 13x13, DEGen-MNA achieves 0.93 ± 0.02 mean solve rate, above PLR-MNA (0.84) and ACCEL-MNA (0.90) and the prior best PLR-MaxMC-style baselines.
- On standard Minigrid, DEGen-MNA reaches 0.96 ± 0.03 mean solve rate, comparable to replay methods, while Initial Gen-MNA reaches only 0.34 ± 0.05.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use DEGen with MNA instead of the strongest replay baseline, ACCEL - MNA | UED on Minigrid · Minigrid hand-designed test set | solve rate: 0.91 ± 0.01 -> 0.96 ± 0.03 | Helped |
| Use DEGen with MNA instead of the strongest replay baseline, ACCEL - MNA | UED on Key Minigrid 13x13 · Key Minigrid 13x13 hand-designed test set | solve rate: 0.90 ± 0.03 -> 0.93 ± 0.02 | Helped |
| Use DEGen with MNA instead of PLR - MNA | UED on Key Minigrid 17x17 · Key Minigrid 17x17 hand-designed test set | solve rate: 0.77 ± 0.04 -> 0.78 ± 0.03 | Mixed |
| Use DEGen with MNA instead of PLR - MNA | UED on Key Minigrid 21x21 · Key Minigrid 21x21 hand-designed test set | solve rate: 0.43 ± 0.05 -> 0.80 ± 0.03 | Helped |
| Replace MaxMC with MNA (ablation) | PLR on Minigrid · Minigrid hand-designed test set | solve rate: 0.83 ± 0.03 -> 0.92 ± 0.02 | Helped |
| Replace PVL with MNA (ablation) | PLR on Minigrid · Minigrid hand-designed test set | solve rate: 0.75 ± 0.03 -> 0.92 ± 0.02 | Helped |
| Replace MaxMC with MNA (ablation) | ACCEL on Minigrid · Minigrid hand-designed test set | solve rate: 0.86 ± 0.02 -> 0.91 ± 0.01 | Helped |
| Replace PVL with MNA (ablation) | ACCEL on Minigrid · Minigrid hand-designed test set | solve rate: 0.87 ± 0.03 -> 0.91 ± 0.01 | Helped |
| Replace MaxMC with MNA (ablation) | PLR on Key Minigrid 13x13 · Key Minigrid 13x13 hand-designed test set | solve rate: 0.29 ± 0.03 -> 0.84 ± 0.01 | Helped |
| Replace PVL with MNA (ablation) | PLR on Key Minigrid 13x13 · Key Minigrid 13x13 hand-designed test set | solve rate: 0.03 ± 0.01 -> 0.84 ± 0.01 | Helped |
| Replace MaxMC with MNA (ablation) | ACCEL on Key Minigrid 13x13 · Key Minigrid 13x13 hand-designed test set | solve rate: 0.72 ± 0.02 -> 0.90 ± 0.03 | Helped |
| Replace PVL with MNA (ablation) | ACCEL on Key Minigrid 13x13 · Key Minigrid 13x13 hand-designed test set | solve rate: 0.45 ± 0.01 -> 0.90 ± 0.03 | Helped |
Surprising findings
- In Sokoban, MaxMC outperforms MNA for replay-based methods, with ACCEL-MaxMC the best performer, which the authors attribute to MNA scoring all impossible levels zero.
- SFL performs poorly in the key minigrid domain, suggesting learnability on final outcomes alone is insufficient.
Limitations
- Evaluated only on simple grid-world domains with a direct mapping between level parameters and observations; generalisation to 3D or robotics is untested.
- DEGen is about four times more computationally expensive than replay-based methods.
- MNA underperforms MaxMC in Sokoban, where most random levels are unsolvable.
Experimental setup
Datasets: Minigrid procedurally generated levels Key Minigrid procedurally generated levels Sokoban-style procedurally generated levels
Benchmarks: Minigrid hand-designed test levels Key Minigrid hand-designed test levels (13x13, 17x17, 21x21) Sokoban Jr zero-shot levels
Metrics: zero-shot solve rate mean and standard error over 8 runs
Baselines: DR Initial Gen SFL PLR ACCEL PAIRED MaxMC PVL
Builds on: PLR ACCEL PAIRED Sampling for Learnability PPO JaxUED
Closest papers by meaning
- No Regrets: Investigating and Improving Regret Approximations for Curriculum Discovery (NeurIPS 2024 · similarity 0.93)
- Marginal Benefit Driven RL Teacher for Unsupervised Environment Design (AAAI 2025 · similarity 0.92)
- Adversarial Environment Design via Regret-Guided Diffusion Models (NeurIPS 2024 · similarity 0.91)
- Improving Environment Novelty Quantification for Effective Unsupervised Environment Design (NeurIPS 2024 · similarity 0.90)
- Refining Minimax Regret for Unsupervised Environment Design (ICML 2024 · similarity 0.90)
- Unsupervised Training Sequence Design: Efficient and Generalizable Agent Training (AAAI 2024 · similarity 0.89)
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.