# Refining Minimax Regret for Unsupervised Environment Design

arXiv: https://arxiv.org/abs/2402.12284 · HTML: https://mlsanity.com/paper/2402.12284/

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- Placed in Deep RL algorithms and representations, one of 15 directions in Deep reinforcement learning methods.
- Builds on 28 of its 56 references that are in the map.
- First posted on arXiv 19 Feb 2024.

## Placed in

- Deep reinforcement learning methods / [Deep RL algorithms and representations](https://mlsanity.com/deeprl/deep-rl-algorithms-and-representations/)

## Builds on (most cited first, 28 of 28)

- [Domain Randomization for Transferring Deep Neural Networks from Simulation to the Real World](https://mlsanity.com/paper/1703.06907/) (2017)
- [Robust Adversarial Reinforcement Learning](https://mlsanity.com/paper/1703.02702/) (2017)
- [Brax -- A Differentiable Physics Engine for Large Scale Rigid Body Simulation](https://mlsanity.com/paper/2106.13281/) (2021)
- [Emergent Complexity and Zero-shot Transfer via Unsupervised Environment Design](https://mlsanity.com/paper/2012.02096/) (2020)
- [Automatic Goal Generation for Reinforcement Learning Agents](https://mlsanity.com/paper/1705.06366/) (2017)
- ["Other-Play" for Zero-Shot Coordination](https://mlsanity.com/paper/2003.02979/) (2020)
- [Prioritized Level Replay](https://mlsanity.com/paper/2010.03934/) (2020)
- [Paired Open-Ended Trailblazer (POET): Endlessly Generating Increasingly Complex and Diverse Learning Environments and Their Solutions](https://mlsanity.com/paper/1901.01753/) (2019)
- [Evolving Curricula with Regret-Based Environment Design](https://mlsanity.com/paper/2203.01302/) (2022)
- [Intrinsic Motivation and Automatic Curricula via Asymmetric Self-Play](https://mlsanity.com/paper/1703.05407/) (2017)
- [Human-Timescale Adaptation in an Open-Ended Task Space](https://mlsanity.com/paper/2301.07608/) (2023)
- [Teacher algorithms for curriculum learning of Deep RL in continuously parameterized environments](https://mlsanity.com/paper/1910.07224/) (2019)
- [Replay-Guided Adversarial Environment Design](https://mlsanity.com/paper/2110.02439/) (2021)
- [Discovered Policy Optimisation](https://mlsanity.com/paper/2210.05639/) (2022)
- [RORL: Robust Offline Reinforcement Learning via Conservative Smoothing](https://mlsanity.com/paper/2206.02829/) (2022)
- [Off-Belief Learning](https://mlsanity.com/paper/2103.04000/) (2021)
- [A Unified Approach to Reinforcement Learning, Quantal Response Equilibria, and Two-Player Zero-Sum Games](https://mlsanity.com/paper/2206.05825/) (2022)
- [Emergence of Maps in the Memories of Blind Navigation Agents](https://mlsanity.com/paper/2301.13261/) (2023)
- [Environment Generation for Zero-Shot Compositional Reinforcement Learning](https://mlsanity.com/paper/2201.08896/) (2022)
- [Provably Efficient Model-Free Constrained RL with Linear Function Approximation](https://mlsanity.com/paper/2206.11889/) (2022)
- [Adversarial Model for Offline Reinforcement Learning](https://mlsanity.com/paper/2302.11048/) (2023)
- [Corruption-Robust Offline Reinforcement Learning with General Function Approximation](https://mlsanity.com/paper/2310.14550/) (2023)
- [On the Foundation of Distributionally Robust Reinforcement Learning](https://mlsanity.com/paper/2311.09018/) (2023)
- [Stabilizing Unsupervised Environment Design with a Learned Adversary](https://mlsanity.com/paper/2308.10797/) (2023)
- [Grounding Aleatoric Uncertainty for Unsupervised Environment Design](https://mlsanity.com/paper/2207.05219/) (2022)
- [Distributionally Robust Partially Observable Markov Decision Process with Moment-based Ambiguity](https://mlsanity.com/paper/1906.05988/) (2019)
- [Distributionally Robust Markov Decision Processes and their Connection to Risk Measures](https://mlsanity.com/paper/2007.13103/) (2020)
- [minimax: Efficient Baselines for Autocurricula in JAX](https://mlsanity.com/paper/2311.12716/) (2023)

## Built on by (most cited first, 18 of 18)

- [No Regrets: Investigating and Improving Regret Approximations for Curriculum Discovery](https://mlsanity.com/paper/2408.15099/) (2024)
- [Scalable Reinforcement Post-Training Beyond Static Human Prompts: Evolving Alignment via Asymmetric Self-Play](https://mlsanity.com/paper/2411.00062/) (2024)
- [EnvHarness: Awakening Static Worlds for Agent Learning](https://mlsanity.com/paper/2608.19880/) (2026)
- [The Overcooked Generalisation Challenge: Evaluating Cooperation with Novel Partners in Unknown Environments Using Unsupervised Environment Design](https://mlsanity.com/paper/2406.17949/) (2024)
- [An Optimisation Framework for Unsupervised Environment Design](https://mlsanity.com/paper/2505.20659/) (2025)
- [Improving Environment Novelty Quantification for Effective Unsupervised Environment Design](https://mlsanity.com/paper/2502.05726/) (2025)
- [Unsupervised Partner Design Enables Robust Ad-hoc Teamwork](https://mlsanity.com/paper/2508.06336/) (2025)
- [Syllabus: Portable Curricula for Reinforcement Learning Agents](https://mlsanity.com/paper/2411.11318/) (2024)
- [Beyond Fixed Tasks: Unsupervised Environment Design for Task-Level Pairs](https://mlsanity.com/paper/2511.12706/) (2025)
- [Mitigating Goal Misgeneralization via Minimax Regret](https://mlsanity.com/paper/2507.03068/) (2025)
- [Co-Evolution in Agentic Systems: Toward Self-Directed Evolution Beyond Human Design](https://mlsanity.com/paper/2608.10299/) (2026)
- [Active Curriculum Refinement for Reinforcement Learning](https://mlsanity.com/paper/2608.26469/) (2026)
- [Task Scheduling & Forgetting in Multi-Task Reinforcement Learning](https://mlsanity.com/paper/2503.01941/) (2025)
- [D'ej`aQ: Open-Ended Evolution of Diverse, Learnable and Verifiable Problems](https://mlsanity.com/paper/2601.01931/) (2026)
- [PACE: Parameter Change for Unsupervised Environment Design](https://mlsanity.com/paper/2605.01358/) (2026)
- [Predicting Task Difficulty Without Rollouts](https://mlsanity.com/paper/2608.05797/) (2026)
- [Efficient Exploration Is Enough](https://mlsanity.com/paper/2609.07575/) (2026)
- [Anchor-and-Harvest Curriculum: A Fully Unmasked Non-LLM Curriculum for Craftax](https://mlsanity.com/paper/2610.15328/) (2026)

## Abstract (arXiv)

In unsupervised environment design, reinforcement learning agents are trained on environment configurations (levels) generated by an adversary that maximises some objective. Regret is a commonly used objective that theoretically results in a minimax regret (MMR) policy with desirable robustness guarantees; in particular, the agent's maximum regret is bounded. However, once the agent reaches this regret bound on all levels, the adversary will only sample levels where regret cannot be further reduced. Although there are possible performance improvements to be made outside of these regret-maximising levels, learning stagnates. In this work, we introduce Bayesian level-perfect MMR (BLP), a refinement of the minimax regret objective that overcomes this limitation. We formally show that solving for this objective results in a subset of MMR policies, and that BLP policies act consistently with a Perfect Bayesian policy over all levels. We further introduce an algorithm, ReMiDi, that results in a BLP policy at convergence. We empirically demonstrate that training on levels from a minimax regret adversary causes learning to prematurely stagnate, but that ReMiDi continues learning.