PaperlayerView exact revision on arXiv

Source-linked AI summary

Replay-Guided Adversarial Environment Design

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

arXiv:2110.02439v2cs.LGcs.AI

TL;DR

Deep RL agents can fail to transfer to slightly different environments, and suitable training distributions are not always easy to specify. This paper frames PLR and PAIRED as instances of Dual Curriculum Design and derives robustness results that motivate replay-only policy updates. PLR⊥ and REPAIRED significantly improve zero-shot generalization over their respective baselines in two distinct environments.

  • Problem

    Deep RL agents can fail to transfer to slightly different environments, while specifying an appropriate training distribution or generator is not always feasible.

    Source: §1 · p. 1

  • Method

    The paper unifies PLR and PAIRED as Dual Curriculum Design and introduces PLR⊥, which updates the policy only on replay-level trajectories.

    Source: §1 · p. 2

  • Results

    In two distinct environments, PLR⊥ significantly improves zero-shot generalization over PLR, and REPAIRED over PAIRED.

    Source: §8 · p. 10

  • Takeaways & Limitations

    Because the methods modify the order of levels visited during training, they can in principle be combined with other RL methods for potentially orthogonal improvements in sample-efficiency and generalization.

    Source: §8 · p. 10

    The robustness guarantee applies at Nash equilibria but does not guarantee convergence to them, and replay-based methods depend on the quality of levels proposed by the generator.

    Source: §8 · p. 10

Abstract

from arXiv · show

Deep reinforcement learning (RL) agents may successfully generalize to new settings if trained on an appropriately diverse set of environment and task configurations. Unsupervised Environment Design (UED) is a promising self-supervised RL paradigm, wherein the free parameters of an underspecified environment are automatically adapted during training to the agent's capabilities, leading to the emergence of diverse training environments. Here, we cast Prioritized Level Replay (PLR), an empirically successful but theoretically unmotivated method that selectively samples randomly-generated training levels, as UED. We argue that by curating completely random levels, PLR, too, can generate novel and complex levels for effective training. This insight reveals a natural class of UED methods we call Dual Curriculum Design (DCD). Crucially, DCD includes both PLR and a popular UED algorithm, PAIRED, as special cases and inherits similar theoretical guarantees. This connection allows us to develop novel theory for PLR, providing a version with a robustness guarantee at Nash equilibria. Furthermore, our theory suggests a highly counterintuitive improvement to PLR: by stopping the agent from updating its policy on uncurated levels (training on less data), we can improve the convergence to Nash equilibria. Indeed, our experiments confirm that our new method, PLR$^{\perp}$, obtains better results on a suite of out-of-distribution, zero-shot transfer tasks, in addition to demonstrating that PLR$^{\perp}$ improves the performance of PAIRED, from which it inherited its theoretical framework.

1 Introduction

Deep RL agents can be brittle on unfamiliar environments, while specifying a suitable training distribution is not always feasible. The paper connects PLR and PAIRED through Dual Curriculum Design, derives robustness guarantees, and reports improved zero-shot generalization for its methods.

1 Introduction

  • Agents may fail to transfer even to slightly different environments, and specifying an appropriate training distribution or generator is not always feasible.The introduction motivates methods that adapt environment distributions during training.Source: §1 · p. 1
  • PLR⊥ selects challenging randomly generated CarRacing tracks that more closely resemble human-designed tracks such as the Nürburgring Grand Prix.The figure contrasts tracks from Domain Randomization, PAIRED, REPAIRED, and PLR⊥.Source: Figure 1 · p. 2
  • DCD unifies PLR’s replay-based curation and PAIRED’s active level generation, with minimax regret guarantees similar to PAIRED’s.The framework has two co-evolving teachers: one generates challenging levels and the other selects existing levels for replay.Source: §1 · p. 2
  • Training PLR only on replay levels yields PLR⊥, which is provably robust at Nash equilibria; adding PLR-based replay to PAIRED yields REPAIRED.The paper also proves a robustness guarantee for REPAIRED.Source: §1 · pp. 2–3
  • In maze and CarRacing settings, the proposed methods significantly improve zero-shot generalization over PLR and PAIRED, including transfer to human-designed mazes and Formula 1 tracks.The experiments compare PLR⊥ and REPAIRED with their replay-free counterparts.Source: §1 · pp. 2–3

2 Background

The background defines UED as adapting environment distributions to an agent, then introduces PAIRED and PLR as contrasting approaches to selecting training levels.

2.1 Unsupervised Environment Design

  • UED adapts a distribution of environments to the learning agent by varying free parameters in an underspecified POMDP; a fully specified environment is called a level.Free parameters can vary by time step, such as obstacle positions in a maze.Source: §2.1 · p. 3

2.2 Protagonist Antagonist Induced Regret Environment Design

  • PAIRED trains protagonist and antagonist agents against a teacher that maximizes their regret, producing increasingly complex levels near the protagonist’s capability boundary.The teacher’s gradient-based adaptation is inherently slow as student policies change.Source: §2.2 · p. 3

2.3 Prioritized Level Replay

  • PLR maintains a buffer of high-learning-potential visited levels and uses a bandit to choose replay levels, adapting faster than PAIRED but without a robustness guarantee.It samples a new simulator level with probability 1 − p and otherwise replays from its buffer.Source: §2.3 · pp. 3–4

3 The Robustness of Dual Curriculum Design

Dual Curriculum Design combines level generation with replay curation in a game between a student and two teachers. Nash equilibria of this game approximate equilibria of the corresponding single-teacher games, with approximation quality depending on the mixing probability.

3 The Robustness of Dual Curriculum Design

  • DCD pairs a teacher that gradually generates levels, as in PAIRED, with a curator that rapidly prioritizes existing levels, as in PLR.PLR combines prioritized replay with a random generator; PAIRED uses a regret-maximizing generator without a curator.Source: §3 · p. 4
  • The dual curriculum game combines teachers by having the first play with probability p and the second with probability 1−p.The student’s utility is its environment return, while each teacher has its own utility function.Source: §3 · p. 4
  • DCD models a student and two teachers in a game whose equilibria approximate equilibria of either single-teacher game, with approximation quality depending on the mixing probability.The teachers can also be viewed as one combined strategy for the base game with a joint objective.Source: §3 · pp. 4–5
  • At a Nash equilibrium, the student’s strategy is an approximate minimax-regret strategy when both teachers maximize regret.The theorem describes the combined strategy as a 2Bp(1−p)-approximate Nash equilibrium when the teacher utility is the probability-weighted joint objective.Source: §3 · pp. 4–5

4 Robustifying PLR

The section analyzes PLR’s robustness and motivates PLR⊥, which trains only on replay levels. It also discusses regret-based scores for prioritizing levels when true regret is unavailable.

4.1 Achieving Robustness Guarantees with PLR

  • At equilibrium, PLR’s policy is within 2(B+−B−)(1−p) of optimal worst-case regret under bounded returns.The bound is stated as worst-case regret at least R*−2(B+−B−)(1−p); the authors also give environments achieving the bound within a constant factor.Source: §4.1 · p. 5
  • Setting p to zero makes the equilibrium policy converge to minimax regret, motivating PLR⊥’s omission of policy updates on randomly sampled levels.The authors describe this as training on less data for robustness at Nash equilibrium.Source: §4.1 · p. 5

4.2 Estimating Regret

  • True level regret may be unavailable without an oracle, and PLR’s usual L1 value loss does not generally correspond to regret.The section therefore considers alternative scoring functions that better approximate regret.Source: §4.2 · p. 6
  • Maximum Monte Carlo scoring reduces positive value loss’s bias by using the highest return achieved on a level rather than a target tied to the current policy.Positive value loss can optimistically prioritize levels because it uses policy-dependent value targets and considers only positive losses.Source: §4.2 · p. 6

5 Replay-Enhanced PAIRED (REPAIRED)

REPAIRED combines PLR⊥ with the PAIRED teacher, using replay buffers for training and newly generated levels for evaluation. In the theoretically ideal setting, its Nash equilibria yield minimax-regret strategies for the protagonist.

5 Replay-Enhanced PAIRED (REPAIRED)

  • REPAIRED replaces PLR⊥’s random generator with the PAIRED teacher and gives both protagonist and antagonist their own regret-prioritizing replay buffers.With probability p, the students evaluate without training on a newly generated level; otherwise, they train on levels sampled from their respective buffers.Source: §5 · p. 6
  • In the theoretically ideal setting, a Nash equilibrium of REPAIRED yields a protagonist strategy that minimizes worst-case regret.The authors say this offers some assurance of robustness and versatility across environments in the domain when the relevant environments are solvable and sufficiently well-defined.Source: §5 · p. 6

6 Experiments

Across navigation and CarRacing, replay-based methods improve zero-shot transfer over replay-free counterparts. The experiments also examine how replay affects curriculum complexity and how performance varies across the two settings.

6.1 Partially-Observable Navigation; 6.2 Pixel-Based Car Racing with Continuous Control

  • Replay-based methods improve zero-shot transfer over replay-free counterparts in navigation and CarRacing, with PLR⊥ also outperforming PLR on the full F1 benchmark.The navigation comparison includes PLR⊥ and REPAIRED; on the full F1 benchmark, PLR⊥ gains over PLR are statistically significant (p < 0.001).Source: §6.1 · p. 7, Figure 3 · p. 7, Figure 4 · p. 8

6.1 Partially-Observable Navigation

  • In navigation, PLR and PLR⊥ achieve greater sample-efficiency and zero-shot generalization than replay-free counterparts, and both outperform PAIRED well before its reported 3B training steps.PLR⊥'s test-performance improvement over DR and PLR at an equivalent number of gradient updates is statistically significant (p < 0.05).Source: §6.1 · p. 7
  • In maze training, PAIRED slowly increases level complexity, while REPAIRED grows it faster initially; PLR and PLR⊥ reach comparable complexity in a fraction of the gradient steps.The reported measures include block count and shortest path length; Figure 5 examples show PLR levels with complex structure.Source: §6.1 · p. 7, Figure 5 · p. 7

6.2 Pixel-Based Car Racing with Continuous Control

  • Random-track training yields moderately successful CarRacing transfer, but regret-prioritized track sampling significantly outperforms uniform sampling on OOD F1 tracks.PLR⊥ with replay rate 0.5 significantly improves over PLR on the full F1 benchmark (p < 0.001), despite using half the rollout data and half as many gradient updates.Source: §6.2 · pp. 8–9
  • In CarRacing, PAIRED's curriculum can steer its protagonist toward poor performance even on simple tracks; REPAIRED substantially mitigates, but does not eliminate, this degeneracy.REPAIRED significantly exceeds PAIRED but underperforms DR on mean performance across the full F1 benchmark; PLR⊥ exceeds AttentionAgent despite using less than 0.25% as many environment steps.Source: Figure 6 · p. 8, §6.2 · p. 9

7 Related Work

The related work connects replay-based level selection to curriculum learning and fictitious self-play, and contrasts DCD with other environment-generation and domain-randomization approaches. These comparisons highlight differences in task assumptions, compute demands, and guarantees.

7 Related Work

  • PLR⊥ resembles selective-sampling curriculum methods such as TSCL, while replayed levels can be viewed as past teacher strategies linking replay to fictitious self-play.TSCL prioritizes by return rather than value loss and has been shown to overfit to training levels in some settings; Prioritized FSP selectively samples opponents using historic win ratios.Source: §7 · p. 9
  • Unlike goal-focused approaches such as Asymmetric Self-Play and AMIGo, the paper's methods do not presuppose a goal-based setting; the authors also claim broader applicability and principled robustness guarantees.The passage contrasts the methods with approaches based on generative modeling, latent skill learning, and model disagreement,,.Source: §7 · p. 9
  • POET constructs terrain with a population of minimax adversaries but requires substantial compute, while APT-Gen requires access to target tasks unlike methods focused on zero-shot transfer.Source: §7 · p. 9
  • The authors frame adaptive domain randomization and procedural content generation as related forms of UED and DCD, respectively, placing them within a decision-theoretic framework.The passage notes adaptive domain randomization's use in sim-to-real robotics transfer.Source: §7 · p. 9

8 Discussion

The discussion presents DCD as a framework unifying PLR and PAIRED, and reports robustness guarantees for PLR and REPAIRED at Nash equilibria. It also identifies limits on what the theory guarantees and proposes possible extensions beyond environment design.

8 Discussion

  • DCD models a generator and a replay curator as co-adapting regret-maximizing teachers, unifying PLR and PAIRED and supporting a minimax-regret guarantee for PLR at Nash equilibria.The authors describe this as the first theoretical characterization of PLR robustness.Source: §8 · p. 9
  • PLR⊥ and REPAIRED significantly improve zero-shot generalization over PLR and PAIRED, respectively, in two distinct environments; REPAIRED shares the stated NE robustness guarantee.The methods alter the order of levels visited during training and may, in principle, combine with other RL methods for potentially orthogonal sample-efficiency and generalization improvements.Source: §8 · p. 10
  • The theory guarantees minimax regret at an NE but does not guarantee that training converges to one.Replay-based methods also depend on generator quality and on free parameters that sufficiently align the environment set with the transfer domain; random search may be ineffective in higher-dimensional domains.Source: §8 · p. 10
  • The authors suggest DCD may extend to continual learning when tasks have episode boundaries and are assumed to be designed by a regret-maximizing teacher.Source: §8 · p. 10

Broader Impact

The broader-impact discussion presents robust RL as potentially useful for real-world deployment, while noting general societal risks and the importance of aligning environment parameters with the target domain.

Broader Impact

  • The authors suggest that improved UED may support safer, more reliable RL agents and help extend RL to real-world problems.Source: Broader Impact · p. 10
  • The authors note possible deployment risks including unemployment, reliance on biased models that reinforce inequalities, and automated weapons.They also state that successful transfer depends on choosing UPOMDP free parameters aligned with the target domain, a concern they describe as shared by robust-policy RL methods generally.Source: Broader Impact · p. 10

A Theoretical Results

The theoretical analysis relates dual-curriculum equilibria to equilibria of simpler games, yielding regret guarantees for PLR and REPAIRED. The appendices also give algorithm details and explain why the 50-block maze setting is less informative.

A Theoretical Results

  • At a dual-curriculum Nash equilibrium, the mixed teacher strategy is a 2Bp(1−p)-approximate Nash equilibrium for the base game.The same result relates equilibria to either teacher’s game and to the joint-reward game.Source: A Theoretical Results · p. 14
  • PLR’s worst-case regret is within 2(B+ − B−)(1−p) of optimal at equilibrium, and the approximation improves as random episodes decrease.The analysis motivates training only on replay levels, the PLR⊥ variant.Source: A Theoretical Results · p. 15
  • The counterexample illustrates that policies with higher expected value under uniform levels can still incur high regret, unlike a minimax-regret policy.The minimax-regret policy mixes uniformly between π0 and π1 to achieve regret of exactly B/2.Source: A Theoretical Results · p. 15
  • REPAIRED’s protagonist is a minimax-regret strategy at Nash equilibrium because both teachers maximize regret.The minimax result follows when both teachers share the regret objective.Source: A Theoretical Results · p. 16

B Algorithms

  • The algorithms appendix gives the PLR level-buffer update and pseudocode for REPAIRED’s protagonist and antagonist replay buffers.REPAIRED collects trajectories on generated and replayed levels, updates both students, then scores and updates their buffers.Source: B Algorithms · p. 17

C Additional Experimental Results

C.1 Extended Results for MiniGrid

  • With a 50-block budget, DR and replay-based methods nearly solve most test mazes after about 500M steps, making performance differences less informative.The authors therefore focus their main maze results on the more challenging 25-block setting.Source: §C.1 · p. 18

C.1.1 Mazes with a 25-block budget

With a 25-block maze budget, replay-based UED methods improve zero-shot transfer over PAIRED, and PLR⊥ improves on PLR at matched gradient updates. At 50 blocks, DR and replay-based methods nearly solve most test mazes, limiting the setting’s ability to distinguish methods.

C.1.1 Mazes with a 25-block budget

  • REPAIRED’s adversary proposes more difficult mazes for both students, while its protagonist has improved test performance.PAIRED’s antagonist attains higher training returns than its protagonist, with the generator’s return oscillating as it finds new configurations.Source: §C.1.1 · p. 18, Figure 9 · p. 19
  • Replay-based UED methods significantly outperform PAIRED on 25-block transfer mazes; after 500M steps, PLR⊥ also improves over PLR at matched gradient updates.The table reports mean test returns and standard errors aggregated over 100 attempts per maze across 10 runs.Source: §C.1.1 · p. 18, Table 2 · p. 19
  • REPAIRED generates mazes with greater block-count complexity than DR, while curated PLR levels are more complex than the random levels on average.The authors also report that curated levels’ path lengths steadily increase; action complexity falls as agents become more decisive.Source: §C.1.1 · p. 19, Figure 10 · p. 19

C.1.2 Mazes with a 50-block budget

  • At 50 blocks, DR and replay-based methods achieve near-perfect solve rates on most test mazes after 500M steps, so the setting is not informative for method comparisons.The larger budget lets DR sample structurally complex mazes, diminishing the benefits of the UED methods studied.Source: §C.1.2 · p. 20, Figure 11 · p. 20, Figure 15 · p. 21

C.2 Extended Results for CarRacing

On the CarRacing-F1 benchmark, PLR⊥ matches or exceeds other methods across tracks and has higher overall mean performance. Its minimum returns are also higher on average for many tracks, while PAIRED’s adversarial curriculum can degrade protagonist performance.

C.2 Extended Results for CarRacing

  • PAIRED’s generator overexploits antagonist–protagonist differences, degrading the protagonist even on simple tracks; REPAIRED mitigates this effect to a degree.PAIRED’s protagonist can no longer successfully drive on the original CarRacing tracks after training.Source: §C.2 · p. 21
  • The AttentionAgent comparison uses author-provided pretrained weights from a single training run, so its standard errors cannot be estimated reliably.Its high compute overhead prevented running multiple training seeds.Source: §C.2 · p. 21
  • PLR⊥ matches or exceeds other methods within standard error on every CarRacing-F1 track and has significantly higher mean benchmark performance than all other methods (p < 0.001).The table aggregates returns over 10 attempts per track across 10 runs per method.Source: §C.2 · p. 21, Table 3 · p. 22
  • PLR⊥ achieves higher average minimum returns on many tracks, including Russia and USA.The figure reports mean and standard error across 10 training runs, using 10 test episodes per track per seed.Source: §C.2 · p. 21, Figure 17 · p. 23

D Experiment Details and Hyperparameters

The experiments use PPO across MiniGrid navigation and CarRacing, with environment-specific agent, generator, and hyperparameter choices. They evaluate zero-shot transfer on held-out mazes and a new benchmark of real-world Formula One tracks.

D Experiment Details and Hyperparameters

  • PPO trains the student and generator policies, and reported results use each method’s best hyperparameter settings.Unless specified, student and teacher PPO settings are shared; hyperparameters are selected separately for each environment.Source: D Experiment Details and Hyperparameters · p. 24

D.1 Partially-Observable Navigation (MiniGrid)

  • MiniGrid mazes are 15 × 15 grids with partial 7 × 7 observations, and agents navigate using turn-left, turn-right, and forward actions.The goal reward is 1 − T/Tmax upon success, with Tmax set to 250; failure yields zero reward.Source: §D.1 · p. 24
  • Maze transfer tests include SixteenRooms, Labyrinth, and Maze, plus rotated, variant, and procedurally generated mazes designed to test backtracking.The additional levels are Labyrinth2, Maze2, PerfectMaze, and LargeCorridor.Source: §D.1 · p. 25

D.2 CarRacing

  • CarRacing tracks are closed loops built from 12 randomly sampled Bézier control points, and agents drive a full lap using pixel observations and continuous steering, gas, and brake actions.The student receives rewards for visiting new track polygons and a −0.1 time-step penalty.Source: §D.2 · pp. 25–26
  • Hyperparameters are selected through environment-specific searches, with student settings chosen on validation levels and PLR settings searched over replay and buffer parameters.CarRacing student settings are selected using F1-Italy, F1-Singapore, and F1-Germany; PLR settings are then shared with REPAIRED except for separately searched scoring functions.Source: §D.2 · pp. 26–27
  • The new CarRacing-F1 benchmark contains 20 real-world Formula One tracks that are out-of-distribution and more complex than the training tracks.The tracks cannot be represented by the training generator’s 12-control-point Bézier curves and require 1,500 or 2,000 steps, versus 1,000 for training tracks.Source: §D.2 · p. 27
  • Figure 18 contrasts average-complexity DR tracks and often-simple PAIRED tracks with the considerable complexity produced by REPAIRED, PLR, and PLR⊥.The caption attributes the PLR methods’ track complexity to prioritizing challenging randomly generated tracks.Source: Figure 18 · p. 28
Loading 2110.02439v2…