# No Regrets: Investigating and Improving Regret Approximations for Curriculum Discovery

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

## Key facts

- Cited by 31 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 43 of its 64 references that are in the map.
- First posted on arXiv 27 Aug 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, 30 of 43)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [High-Dimensional Continuous Control Using Generalized Advantage Estimation](https://mlsanity.com/paper/1506.02438/) (2015)
- [Dream to Control: Learning Behaviors by Latent Imagination](https://mlsanity.com/paper/1912.01603/) (2019)
- [Domain Randomization for Transferring Deep Neural Networks from Simulation to the Real World](https://mlsanity.com/paper/1703.06907/) (2017)
- [Mastering Diverse Domains through World Models](https://mlsanity.com/paper/2301.04104/) (2023)
- [Mastering Atari with Discrete World Models](https://mlsanity.com/paper/2010.02193/) (2020)
- [Robust Adversarial Reinforcement Learning](https://mlsanity.com/paper/1703.02702/) (2017)
- [Curriculum Learning for Reinforcement Learning Domains: A Framework and Survey](https://mlsanity.com/paper/2003.04960/) (2020)
- [Minigrid & Miniworld: Modular & Customizable Reinforcement Learning Environments for Goal-Oriented Tasks](https://mlsanity.com/paper/2306.13831/) (2023)
- [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)
- [Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks](https://mlsanity.com/paper/1906.08291/) (2019)
- [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)
- [Automatic Curriculum Learning For Deep RL: A Short Survey](https://mlsanity.com/paper/2003.04664/) (2020)
- [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)
- [Craftax: A Lightning-Fast Benchmark for Open-Ended Reinforcement Learning](https://mlsanity.com/paper/2402.16801/) (2024)
- [RORL: Robust Offline Reinforcement Learning via Conservative Smoothing](https://mlsanity.com/paper/2206.02829/) (2022)
- [Towards Optimally Decentralized Multi-Robot Collision Avoidance via Deep Reinforcement Learning](https://mlsanity.com/paper/1709.10082/) (2017)
- [Motion Planning and Control for Mobile Robot Navigation Using Machine Learning: a Survey](https://mlsanity.com/paper/2011.13112/) (2020)
- [XLand-MiniGrid: Scalable Meta-Reinforcement Learning Environments in JAX](https://mlsanity.com/paper/2312.12044/) (2023)
- [Collision Avoidance in Pedestrian-Rich Environments with Deep Reinforcement Learning](https://mlsanity.com/paper/1910.11689/) (2019)
- [DRL-VO: Learning to Navigate Through Crowded Dynamic Scenes Using Velocity Obstacles](https://mlsanity.com/paper/2301.06512/) (2023)
- [MAESTRO: Open-Ended Environment Design for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2303.03376/) (2023)
- [Corruption-Robust Offline Reinforcement Learning with General Function Approximation](https://mlsanity.com/paper/2310.14550/) (2023)
- [Proximal Curriculum for Reinforcement Learning Agents](https://mlsanity.com/paper/2304.12877/) (2023)
- [Benchmarking Reinforcement Learning Techniques for Autonomous Navigation](https://mlsanity.com/paper/2210.04839/) (2022)

## Built on by (most cited first, 30 of 31)

- [Kinetix: Investigating the Training of General Agents through Open-Ended Physics-Based Control Tasks](https://mlsanity.com/paper/2410.23208/) (2024)
- [Learning to Reason at the Frontier of Learnability](https://mlsanity.com/paper/2502.12272/) (2025)
- [MEAL: A Benchmark for Continual Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2506.14990/) (2025)
- [An Optimisation Framework for Unsupervised Environment Design](https://mlsanity.com/paper/2505.20659/) (2025)
- [Bootstrapping Task Spaces for Self-Improvement](https://mlsanity.com/paper/2509.04575/) (2025)
- [ROTATE: Regret-driven Open-ended Training for Ad Hoc Teamwork](https://mlsanity.com/paper/2505.23686/) (2025)
- [BuilderBench: The Building Blocks of Intelligent Agents](https://mlsanity.com/paper/2510.06288/) (2025)
- [GASP: Guided Asymmetric Self-Play For Coding LLMs](https://mlsanity.com/paper/2603.15957/) (2026)
- [Improving Human-AI Coordination through Online Adversarial Training and Generative Models](https://mlsanity.com/paper/2504.15457/) (2025)
- [Efficient Skill Discovery via Regret-Aware Optimization](https://mlsanity.com/paper/2506.21044/) (2025)
- [Unsupervised Partner Design Enables Robust Ad-hoc Teamwork](https://mlsanity.com/paper/2508.06336/) (2025)
- [Preventing Learning Stagnation in PPO by Scaling to 1 Million Parallel Environments](https://mlsanity.com/paper/2603.06009/) (2026)
- [Syllabus: Portable Curricula for Reinforcement Learning Agents](https://mlsanity.com/paper/2411.11318/) (2024)
- [CAMAR: Continuous Actions Multi-Agent Routing](https://mlsanity.com/paper/2508.12845/) (2025)
- [Beyond Fixed Tasks: Unsupervised Environment Design for Task-Level Pairs](https://mlsanity.com/paper/2511.12706/) (2025)
- [IR-SIM: A Lightweight Declarative Simulator for Navigation Learning and Benchmarking](https://mlsanity.com/paper/2606.08729/) (2026)
- [Automatic Curriculum Design for Zero-Shot Human-AI Coordination](https://mlsanity.com/paper/2503.07275/) (2025)
- [TRACED: Transition-aware Regret Approximation with Co-learnability for Environment Design](https://mlsanity.com/paper/2506.19997/) (2025)
- [Mitigating Goal Misgeneralization via Minimax Regret](https://mlsanity.com/paper/2507.03068/) (2025)
- [Improving Regret Approximation for Unsupervised Dynamic Environment Generation](https://mlsanity.com/paper/2601.14957/) (2026)
- [Scaling Curriculum Learning For Autonomous Driving](https://mlsanity.com/paper/2608.22549/) (2026)
- [Active Curriculum Refinement for Reinforcement Learning](https://mlsanity.com/paper/2608.26469/) (2026)
- [Towards a Formal Theory of the Need for Competence via Computational Intrinsic Motivation](https://mlsanity.com/paper/2502.07423/) (2025)
- [D'ej`aQ: Open-Ended Evolution of Diverse, Learnable and Verifiable Problems](https://mlsanity.com/paper/2601.01931/) (2026)
- [TABX: A High-Throughput Sandbox Battle Simulator for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2602.01665/) (2026)
- [Solving Parameter-Robust Avoid Problems with Unknown Feasibility using Reinforcement Learning](https://mlsanity.com/paper/2602.15817/) (2026)
- [Rethinking Ratio-Based Trust Regions for Policy Optimization in Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2605.09212/) (2026)
- [Self-Supervised On-Policy Reinforcement Learning via Contrastive Proximal Policy Optimisation](https://mlsanity.com/paper/2605.13554/) (2026)
- [FlashNav: Training Deployable Robot Navigation Policies in Seconds](https://mlsanity.com/paper/2606.15846/) (2026)
- [Open-ended Multi-agent Autocurricula via Visual Inspection of Policies with Multi-modal LLMs](https://mlsanity.com/paper/2607.08193/) (2026)

## Abstract (arXiv)

What data or environments to use for training to improve downstream performance is a longstanding and very topical question in reinforcement learning. In particular, Unsupervised Environment Design (UED) methods have gained recent attention as their adaptive curricula promise to enable agents to be robust to in- and out-of-distribution tasks. This work investigates how existing UED methods select training environments, focusing on task prioritisation metrics. Surprisingly, despite methods aiming to maximise regret in theory, the practical approximations do not correlate with regret but with success rate. As a result, a significant portion of an agent's experience comes from environments it has already mastered, offering little to no contribution toward enhancing its abilities. Put differently, current methods fail to predict intuitive measures of ``learnability.'' Specifically, they are unable to consistently identify those scenarios that the agent can sometimes solve, but not always. Based on our analysis, we develop a method that directly trains on scenarios with high learnability. This simple and intuitive approach outperforms existing UED methods in several binary-outcome environments, including the standard domain of Minigrid and a novel setting closely inspired by a real-world robotics problem. We further introduce a new adversarial evaluation procedure for directly measuring robustness, closely mirroring the conditional value at risk (CVaR). We open-source all our code and present visualisations of final policies here: https://github.com/amacrutherford/sampling-for-learnability.