PaperlayerView exact revision on arXiv

Source-linked AI summary

Evolving Curricula with Regret-Based Environment Design

Jack Parker-Holder, Minqi Jiang, Michael Dennis, Mikayel Samvelyan, Jakob Foerster, Edward Grefenstette, Tim Rocktäschel

arXiv:2203.01302v3cs.LG

TL;DR

Training generally capable RL agents remains difficult, especially when curricula must discover effective environments in challenging design spaces. ACCEL addresses this by editing previously curated high-regret levels, combining evolutionary complexity growth with regret-based selection. It produces increasingly complex curricula and strong agents across navigation and locomotion while matching POET’s level complexity with less than 0.05% of the interaction samples.

  • Problem

    RL agents often struggle with systematic generalization, while existing curricula can have difficulty finding effective levels in challenging design spaces.

  • Method

    ACCEL evolves curricula by making small edits to previously high-regret levels, producing new levels near the frontier of the student’s capabilities.

  • Results

    ACCEL achieves strong empirical gains across sparse-reward navigation and 2D bipedal locomotion, reaching comparable level complexity to POET with less than 0.05% of its environment-interaction samples.

  • Takeaways & Limitations

    ACCEL combines evolutionary generation of increasingly complex environments with a principled regret-based curriculum that avoids domain-specific heuristics.

  • Takeaways & Limitations

    Larger design spaces may require explicit diversity mechanisms, and ACCEL assumes that a simplest base level can be identified and used.

Abstract

from arXiv · show

It remains a significant challenge to train generally capable agents with reinforcement learning (RL). A promising avenue for improving the robustness of RL agents is through the use of curricula. One such class of methods frames environment design as a game between a student and a teacher, using regret-based objectives to produce environment instantiations (or levels) at the frontier of the student agent's capabilities. These methods benefit from their generality, with theoretical guarantees at equilibrium, yet they often struggle to find effective levels in challenging design spaces. By contrast, evolutionary approaches seek to incrementally alter environment complexity, resulting in potentially open-ended learning, but often rely on domain-specific heuristics and vast amounts of computational resources. In this paper we propose to harness the power of evolution in a principled, regret-based curriculum. Our approach, which we call Adversarially Compounding Complexity by Editing Levels (ACCEL), seeks to constantly produce levels at the frontier of an agent's capabilities, resulting in curricula that start simple but become increasingly complex. ACCEL maintains the theoretical benefits of prior regret-based methods, while providing significant empirical gains in a diverse set of environments. An interactive version of the paper is available at accelagent.github.io.

1. Introduction

Training generally capable RL agents remains difficult, motivating curricula that adapt environment difficulty to the student. ACCEL combines regret-based curriculum selection with evolutionary level editing to produce increasingly complex challenges and strong empirical performance with far less compute.

  • Motivation: Systematic generalization remains a challenge despite RL successes, motivating adaptive curricula for more generally capable agents.Adaptive curricula alter environment parameters and can produce more robust policies in fewer training steps.
  • Regret-based curricula: Regret-based UED uses teacher-designed levels and theoretically converges at equilibrium to a minimax-regret student capable of solving all solvable environments.The teacher uses feedback from the student to select levels, and prior work reports zero-shot transfer to challenging human-designed environments.
  • Evolutionary approaches: Evolutionary curricula can support open-ended learning and diverse challenging tasks, but prior methods rely on domain-specific heuristics and vast computational resources.They exploit useful structures through mutation and selection, unlike methods that only search independently sampled levels.
  • ACCEL: ACCEL edits previously high-regret levels with small mutations, continually generating levels at the frontier of the student’s capabilities.Levels begin simple, quickly become more complex, and allow the policy and environment to co-evolve without environment-specific exploration heuristics.
  • Results: ACCEL achieves strong gains in sparse-reward navigation and 2D bipedal locomotion, reaching POET-comparable complexity with less than 0.05% of its environment-interaction samples on one GPU.The method produces and solves challenging levels while rapidly increasing level complexity.

2. Background

The paper formulates environment variation through underspecified POMDPs and reviews regret-based UED methods. These methods provide principled curriculum selection, but practical regret estimation and random search remain important challenges in large design spaces.

  • Problem formulation: MDPs define states, actions, transitions, rewards, and discounting, but their fixed dynamics and full observability can poorly model real-world variation.POMDPs address partial observability, while varying environments motivate richer formulations for robust transfer.
  • Problem formulation: UPOMDPs add free environment parameters Θ, with each fixed θ defining a level Mθ that can vary transitions, observations, rewards, or world topology.This formulation supports environment instances spanning changes relevant to sim2real and procedurally generated environments.
  • UED: UED treats level generation as a teacher maximizing a utility function over environment parameters and the student policy.Random generation is a baseline with constant utility across levels.
  • Regret-based UED: Regret-based teachers select levels where the optimal policy would outperform the current student, favoring the simplest currently unsolved levels.At Nash equilibrium, the student policy is provably a minimax-regret policy.
  • Practical methods: Because optimal policies are unavailable, practical methods approximate regret; PAIRED uses a second agent, whereas PLR curates high-regret levels from random search.PLR can achieve minimax-regret behavior at equilibrium when training uses only curated levels.
  • Practical methods: PLR’s random sampling makes discovering frontier levels increasingly unlikely in higher-dimensional design spaces and prevents directly extending discovered structures.This limitation motivates methods that edit previously discovered levels.

3. Adversarially Compounding Complexity

ACCEL combines evolutionary level editing with regret-based curation: it edits previously high-regret levels, evaluates the edits, and replays only levels that remain challenging. This produces increasingly complex curricula while retaining regret-based robustness properties and avoiding some evolutionary methods’ domain-specific requirements.

  • Algorithm and motivation: ACCEL combines an evolutionary environment generator with a regret-based curator that edits previously curated high-regret levels.Regret provides the fitness signal for retaining levels in the replay buffer, replacing handcrafted domain-specific filtering.
  • Algorithm and motivation: The procedure samples and evaluates generator levels, stores high-regret levels, trains the student on replay levels, then edits and reevaluates replayed levels.Edited levels enter the buffer only when their estimated regret meets the curation threshold.
  • Compounding complexity: ACCEL’s replay buffer rapidly increases level complexity, producing levels near the frontier of the student agent’s capabilities.The method’s curricula begin simple and become more complex through iterative editing and curation.
  • Editing assumption: Small edits to high-regret levels are intended to discover batches of challenging levels when regret varies smoothly over nearby environment parameters.ACCEL predominantly uses simple random mutations, although more advanced search-based editing mechanisms are possible.
  • Guarantees and practical design: At Nash equilibrium, ACCEL’s student follows a minimax regret strategy, preserving the corresponding regret-based robustness guarantee.The method trains one generalist agent rather than maintaining a population of agents, requiring only a single desktop GPU according to the authors.

4. Experiments

ACCEL is evaluated across maze navigation and challenging bipedal locomotion, where it produces increasingly complex curricula and strong transfer or test performance. The experiments also compare its level complexity, generality, and computational cost with prior methods.

  • Experimental setup: ACCEL is compared with Robust PLR, domain randomization, PAIRED, and a minimax adversarial teacher using PPO-trained student agents.Evaluation is reported by student-policy gradient updates, with environment interactions often comparable for PLR and ACCEL.
  • Partially Observable Navigation: ACCEL achieves an IQM near a perfect solved rate across maze test environments, versus below 80% for PLR, with an 80.2% probability of improvement.ACCEL performs at least as well as the next-best method in almost all individual test environments and produces more structured mazes.
  • Partially Observable Navigation: ACCEL reaches a 53% success rate on 51 × 51 procedurally generated mazes, compared with 25% for PLR, while all other methods fail.The evaluation uses 100 episodes per training seed, and the test mazes are approximately an order of magnitude larger than training levels.
  • Walking in Challenging Terrain: ACCEL attains close to 75% of optimal normalized return in BipedalWalker, almost three times the performance of PLR.The comparison aggregates 100 test episodes per environment and uses a return range normalized to [0, 300].
  • POET Comparison: ACCEL produces increasingly challenging levels and complexity comparable to POET while using less than 0.5% of POET’s environment-interaction compute in the reported comparison.At 30k student updates, ACCEL uses 2.07B environment steps and produces difficult levels without POET’s novelty bonus or steppingstone procedure.
  • Discussion and Limitations: ACCEL trains a single generalist that performs well across BipedalWalker challenge settings, including stairs that are out-of-distribution during training.The paper contrasts this with POET’s population of specialists and reports ACCEL’s broader robustness across environment challenges.

5. Related Work

Related work spans adaptive curricula, domain randomization, evolutionary environment design, UED, and procedural content generation. ACCEL combines evolutionary level editing with regret-based curation while training one generalist agent.

  • Adaptive curricula and domain randomization: Domain randomization trains robust agents by sampling environment parameters, while adaptive curricula alter the training distribution over environment instances.These approaches have been applied to settings such as robotics parameters and maze layouts.
  • Unsupervised Environment Design: UED frames curriculum generation as a teacher designing levels for a student, with regret-based formulations targeting systematic generalization.The related-work comparison includes PAIRED, Robust PLR, and other teacher-based approaches.
  • Evolutionary environment design: Evolutionary methods such as POET evolve levels and populations of specialists, whereas ACCEL evolves levels while training a single generally capable agent.ACCEL uses a minimax-regret objective; PLR instead curates levels generated through domain randomization.
  • Procedural content generation: Procedural content generation seeks distributions of levels for an environment, connecting level-generation research with curriculum construction.The paper also situates its approach alongside symbolic-AI environment-design literature.

6. Conclusion and Future Work

ACCEL combines evolutionary level editing with regret-based curation to produce increasingly complex curricula without domain-specific heuristics. The experiments report robust agents across challenging design spaces, while future work highlights diversity and richer editing mechanisms as open directions.

  • ACCEL evolves curricula by editing previously curated levels, producing environments matched to the agent’s current capabilities.
  • ACCEL agents outperform the best-performing baselines across a series of challenging design spaces.
  • Future extensions include richer level editors, predictive search for useful descendants, extinction events, and explicit diversity objectives.
  • The approach is intended to improve generalization across environment distributions through unsupervised environment design.

B.1. Learning with Lava

In Lava Grid, ACCEL edits high-regret levels to increase challenge complexity while maintaining strong training performance. It also achieves the best aggregate test performance and generates progressively harder levels across several environments.

  • The Lava Grid task uses a 7 × 7 grid where touching lava terminates the episode with zero reward, making random exploration difficult.
  • ACCEL quickly produces Lava Grid levels with more lava than other methods while reaching near-perfect training-distribution performance.PLR has a similar training profile but lower values for each complexity metric.
  • ACCEL is the best-performing method on aggregate Lava Grid tests after 1000 PPO updates.It performs best on all in-distribution environments and is one of two approaches meaningfully above zero on the human-designed LavaCrossing S9N1 task.
  • ACCEL’s evolutionary paths generate levels at the student frontier, with edits compounding into challenges that become more constrained or combine multiple obstacles.The figures include Lava Grid, MiniGrid mazes, and BipedalWalker examples.

B.3. The Expanding Frontier

ACCEL’s evolving levels track the student’s expanding capabilities: later generations challenge earlier checkpoints while remaining learnable by later agents. Complexity, return, and positive value loss shift systematically across generations and checkpoints.

  • Later ACCEL generations become harder for the 5k checkpoint, while the 20k checkpoint obtains the highest return on the more complex Gen 63 level.
  • The frontier analysis compares return and positive value loss for ACCEL policies at 5k, 10k, 15k, and 20k PPO updates.At generation 27 all checkpoints solve the level, while later generations separate checkpoint capabilities.
  • Across generation bands, later levels have higher learning potential for the 20k checkpoint, whereas the 5k checkpoint has the lowest return on them.
  • Block count and shortest-path length relate to difficulty: the 5k agent struggles with higher values, while the 20k agent solves almost all levels.

B.4. Full Experimental Results

Full experiments evaluate ACCEL on zero-shot navigation, highly challenging POET levels, and individual locomotion challenges. Across these settings, ACCEL outperforms baselines, including PLR, while the hardest BipedalWalker environment remains unsolved by all agents.

  • Partially-Observable Navigation: Zero-shot navigation experiments evaluate agents on challenging human-designed environments using 100 trials across five training runs.The environments include procedurally generated corridors and established MiniGrid tasks.
  • Partially-Observable Navigation: ACCEL and its variant using more complex base levels significantly outperform the baselines, with large gains over baselines in complex environments such as Labyrinth.PLR outperforms the other baselines, while ACCEL outperforms PLR.
  • Partially-Observable Navigation: The reported navigation comparisons include ACCEL’s probability of improvement over PLR across the evaluation environments.
  • BipedalWalker: BipedalWalker evaluation covers Stairs, PitGap, Stump, Roughness, BipedalWalker-v3, and BipedalWalkerHardcore-v3.The individual challenges use fixed obstacle parameters specified for each environment.
  • BipedalWalker: None of the evaluated agents fully solve BipedalWalkerHardcore-v3 under the stated mean-reward criterion.The environment is considered solved at mean reward greater than 300 over 100 independent evaluations.
  • Test plots report mean and standard error for each environment across ten runs.
  • POET Generated Levels: POET-level evaluation reports mean and maximum performance across ACCEL runs and trials for six extremely challenging environments.

B.5. Testing the Limits of Current Approaches

ACCEL remains stronger than baseline methods on a highly challenging 101x101 partially observable maze, although performance is weak for all methods.

  • 101x101 maze: 8% and 7% mean success rates were achieved by ACCEL with empty and DR generators, respectively, versus 4% for DR and PLR.All methods performed significantly weaker on the 101x101 maze than on smaller mazes.
  • 101x101 maze: The 101x101 maze requires zero-shot transfer from training on a 15x15 grid.The agent has only a partially observable view and must memorize its location to explore all corners.
  • 101x101 maze: The environment is challenging even for humans because partial observability makes complete exploration difficult.Successful exploration requires continuously remembering the agent’s current location.

B.6. Additional Experiments

Additional experiments examine ACCEL’s design choices and level-buffer diversity, showing that editing and lower concentration of generated levels support stronger zero-shot performance.

  • Ablation Studies: Editing levels is essential: No Editor performs worse than PLR, while editing-based ablations outperform PLR’s mean solved rate of 0.69.The ablations use the DR generator with sampling at the start of 10% of new episode rollouts.
  • Ablation Studies: A learned editor that maximizes positive value loss degrades zero-shot performance relative to the full ACCEL method.The learned editor uses RL to optimize an editing policy for the resulting levels.
  • Diversity of the Level Buffer: Smaller replay buffers produce significantly higher concentration among the top 200 levels, while lower concentration corresponds to better performance on ten-tile test levels.The comparison uses a 4k buffer without DR sampling versus a 10k buffer with 10% DR sampling.
  • Ablation Studies: The zero-shot transfer table reports means and standard errors from five independent runs, with 100 trials per environment.All methods use a DR generator placing between 0 and 60 blocks.
  • Diversity of the Level Buffer: Replay-buffer concentration is measured by the share of top-100 high-regret levels producible by ten parents, while return is evaluated on ten-tile test environments.The small condition uses a 4k buffer without a generator, and the large condition uses a 10k buffer with a generator 10% of the time.

C. Implementation Details

The experiments use several environment domains and single-GPU training, with levels generated by randomization, replay, or parameter edits depending on the method.

  • Training procedure: All training runs use a single V100 GPU and Intel Xeon E5-2698 v4 CPUs.The ACCEL implementation builds directly on the Robust PLR codebase.
  • Environment Details: MiniHack lava tasks use a 7 × 7 grid, randomized lava placement, sparse goal reward, and a −0.01 per-timestep penalty.The DR agent samples the number of blocks uniformly from [0, 20].
  • Environment Details: Partially observable mazes use 15 × 15 grids and reward successful goal-reaching according to episode length, with a maximum training length of 250.Failure to reach the goal yields zero reward.
  • Environment Details: BipedalWalker provides 24-dimensional proprioceptive observations and four continuous motor-torque actions, without positional coordinates.The environment is a modified BipedalWalkerHardcore task.
  • Level generation and editing: ACCEL edits one of eight environment parameters by adding or subtracting its specified edit size, while replayed PLR levels retain their deterministic seeds.Lava edits add or remove obstacles; MiniGrid edits can also change goal locations.
  • Level generation and editing: DR generates levels through uniformly random teacher actions, whereas PAIRED optimizes teacher actions to maximize estimated student regret.The procedure is used for fair comparison across lava and maze domains.
Loading 2203.01302v3…