PaperlayerView exact revision on arXiv

Source-linked AI summary

Emergent Complexity and Zero-shot Transfer via Unsupervised Environment Design

Michael Dennis, Natasha Jaques, Eugene Vinitsky, Alexandre Bayen, Stuart Russell, Andrew Critch, Sergey Levine

arXiv:2012.02096v2cs.LGcs.AIcs.MA

TL;DR

RL training often requires useful environment distributions, yet manually designing them is difficult and existing automatic approaches can miss structure or generate unsolvable tasks. The paper introduces UED and PAIRED, which use underspecified environments and an antagonist-based regret objective to generate solvable curricula; PAIRED agents learn more complex behaviors and achieve higher zero-shot transfer in challenging novel environments. UED is unnecessary when test environments are accurately modeled or important cases are easily enumerated.

  • Problem

    Designing environment distributions for RL training and evaluation is difficult and labor-intensive, while domain randomization and minimax adversarial training have important generation failure modes.

  • Method

    UED generates distributions of fully specified environments from underspecified environments with free parameters, while PAIRED uses an antagonist–protagonist reward difference to approximate minimax regret.

  • Results

    PAIRED produces increasingly complex environment curricula, and its agents learn more complex behaviors with higher zero-shot transfer performance in challenging novel environments.

  • Takeaways & Limitations

    UED offers an approach for building AI systems in real-world settings that are difficult to accurately model, while PAIRED supports complex behavior and transfer to novel environments.

  • Takeaways & Limitations

    UED may be unnecessary when the test environment is accurately modeled or all important cases can be easily enumerated, and the minimax-regret guarantee requires separated reward classes plus an always-successful policy when success is possible.

Abstract

from arXiv · show

A wide range of reinforcement learning (RL) problems - including robustness, transfer learning, unsupervised RL, and emergent complexity - require specifying a distribution of tasks or environments in which a policy will be trained. However, creating a useful distribution of environments is error prone, and takes a significant amount of developer time and effort. We propose Unsupervised Environment Design (UED) as an alternative paradigm, where developers provide environments with unknown parameters, and these parameters are used to automatically produce a distribution over valid, solvable environments. Existing approaches to automatically generating environments suffer from common failure modes: domain randomization cannot generate structure or adapt the difficulty of the environment to the agent's learning progress, and minimax adversarial training leads to worst-case environments that are often unsolvable. To generate structured, solvable environments for our protagonist agent, we introduce a second, antagonist agent that is allied with the environment-generating adversary. The adversary is motivated to generate environments which maximize regret, defined as the difference between the protagonist and antagonist agent's return. We call our technique Protagonist Antagonist Induced Regret Environment Design (PAIRED). Our experiments demonstrate that PAIRED produces a natural curriculum of increasingly complex environments, and PAIRED agents achieve higher zero-shot transfer performance when tested in highly novel environments.

1 Introduction

RL methods across transfer, robustness, unsupervised RL, and emergent complexity require task distributions, but designing them is difficult and labor-intensive. UED and PAIRED automate environment generation to produce challenging, solvable curricula and improve transfer to novel environments.

  • Motivation: Reinforcement learning applications require distributions of tasks and environments for training and evaluating effective policies.This includes transfer learning, robust RL, unsupervised RL, and emergent complexity.
  • Motivation: Designing appropriate environment distributions is difficult because real-world edge cases are complicated, impractical to enumerate, and time-consuming to specify.
  • Unsupervised Environment Design: UED lets developers provide an underspecified environment with free parameters, which are automatically converted into a distribution of fully specified environments.For example, obstacle positions can parameterize a navigation environment.
  • Prior Approaches: Domain randomization rarely generates structured configurations, whereas minimax adversarial training can generate impossible or unsolvable environments.The introduction illustrates these failure modes using maze-navigation environments.
  • PAIRED: PAIRED trains an environment adversary using regret between protagonist and antagonist rewards, motivating difficult but achievable environments as the agents learn.The antagonist is allied with the environment-generating adversary.
  • Results: PAIRED agents learn more complex behaviors and achieve higher zero-shot transfer performance in challenging, novel environments than existing environment-design approaches.

2 Related Work

Related work frames environment design through domain randomization, adversarial training, multi-agent curricula, unsupervised RL, and robust control. PAIRED differs by adapting environment difficulty to learning progress while targeting transfer to unseen environments.

  • Multi-Agent Curricula: Multi-agent training and competition can automatically generate curricula and induce complex skills, while Asymmetric Self Play ensures tasks are solvable in principle.
  • Unsupervised RL: Unlike unsupervised meta-RL methods based on learned task distributions, PAIRED modifies environments and adapts their difficulty to the agent’s learning progress.
  • Contribution: PAIRED provides a curriculum of increasingly difficult environments and a theoretical characterization of when minimax regret should be preferred.
  • Adversarial Training: Minimax adversaries can make environments arbitrarily hard or unsolvable because they lack an incentive to guide the agent’s learning progress.
  • Domain Randomization: Domain randomization samples specified parameters randomly, but it does not guarantee performance on specific challenging configurations and requires careful parameterization.

3 Unsupervised Environment Design

UED constructs training-environment distributions from underspecified environments and policies. The framework formalizes free environment parameters, relates environment policies to decision rules, and motivates PAIRED as minimax-regret environment design.

  • Unsupervised Environment Design: UED constructs a policy by repeatedly generating environments suited to continued learning, training on them, and testing transfer to challenging unseen tasks.
  • Formalization: A fully specified environment is modeled as a POMDP containing actions, observations, states, transitions, observations, rewards, and a discount factor.
  • Formalization: A UPOMDP extends a POMDP with free parameters Θ that affect transitions, and each parameter trajectory θ defines a specific environment M_θ.
  • Environment Policies: An environment policy maps agent policies to distributions over parameter sequences, thereby specifying how environments are generated for continued policy training.
  • Minimax Regret: PAIRED approximates the minimax-regret environment policy, which selects policies that succeed whenever a sufficiently clear success outcome is achievable.
  • Theoretical Conditions: The minimax-regret guarantee assumes separated SUCCESS and FAILURE reward classes and the existence of a policy that succeeds whenever success is possible.

4 Protagonist Antagonist Induced Regret Environment Design (PAIRED)

PAIRED approximates minimax regret by training an environment adversary and antagonist against a protagonist under shared environment conditions. The resulting process can generate challenging but feasible environments and, under stated equilibrium conditions, minimax-regret policies.

  • Regret formulation: Regret is approximated as the difference between two agents’ payoffs in the same environment, with the antagonist representing an alternative decision.The paper defines regret as the gap between obtained and optimal payoff, then uses protagonist–antagonist payoff differences as an approximation.
  • Adversarial training: The environment adversary and antagonist jointly maximize regret while the protagonist is trained in the generated environments.The adversary samples environment parameters shared by both agents; the adversary and antagonist optimize the regret objective.
  • Adversarial training: Multiple trajectories in each generated environment improve the regret signal by comparing the antagonist’s maximum reward with the protagonist’s average reward.The approximation is REGRET ≈ maxτ A Uθ(τ A)−Eτ P[Uθ(τ P )].
  • Adversarial training: Regret can incentivize the adversary to create the easiest task where the protagonist fails but the antagonist succeeds, rather than simply maximizing task difficulty.This follows because the regret objective rewards a performance gap, not an independently specified difficulty target.
  • Theoretical characterization: If each team finds an optimal solution, the protagonist is a minimax-regret policy; the paper connects this result to Nash equilibrium and joint best response.The proof treats the antagonist and environment parameters as one player in a zero-sum game.
  • Theoretical characterization: The theoretical guarantee depends on equilibrium and coordination assumptions, while empirical results examine performance and transfer beyond the proof.The paper notes that multi-agent learning may not always converge and discusses alternative regret approximations that break the coordination assumption.

5 Experiments

Experiments evaluate PAIRED on navigation and continuous-control tasks for emergent complexity, zero-shot transfer, and robustness. PAIRED produces increasingly complex solvable navigation environments and outperforms comparison methods on challenging novel settings, while minimax can make hopper training unsolvable without careful constraints.

  • Experimental setup: The experiments use recurrent policies with PPO for partially observable navigation and compare PAIRED against domain randomization, minimax, and population-based approaches.The environment adversary selects obstacle, goal, and start-position parameters in the navigation setup.
  • Emergent Complexity: PAIRED generates navigation curricula that begin with shorter paths and fewer blocks, then increase in complexity according to the agents’ performance.Domain randomization keeps parameters within a fixed range, while minimax and population-based training show similar complexity to domain randomization.
  • Emergent Complexity: PAIRED protagonists learn to solve more complex environments than domain-randomization, minimax, and population-based-training protagonists.Figure 2 tracks blocks, start–goal distance, shortest paths, and successfully solved path lengths over training.
  • Zero-Shot Transfer: As transfer-task difficulty increases, only PAIRED retains strong generalization to the novel navigation environments.The tests include out-of-distribution block settings, an unlikely Four Rooms configuration, and human-designed 16 Rooms, Labyrinth, and Maze tasks.
  • Continuous Control Tasks: In MuJoCo hopper, unconstrained minimax drives reward to zero after its constraints are removed, whereas PAIRED adjusts adversary difficulty to keep tasks solvable.The adversary strength is scaled during the first 300 iterations; PAIRED remains more robust to unseen force and mass parameters without careful force tuning.

6 Conclusions

The paper presents UED and PAIRED as tools for automatically generating increasingly complex environments and improving robustness or generalization. Their usefulness is greatest when real-world environments are difficult to model accurately, but may be unnecessary when test cases are already known or enumerable.

  • Conclusions: UED automates environment-distribution construction from underspecified environments, supporting increasingly complex behavior, robust policies, and generalization to novel environments.The paper frames UED as relevant across several reinforcement-learning settings.
  • Conclusions: PAIRED uses minimax regret to avoid common environment-design failure modes while generating increasingly complex environments and improving challenging zero-shot transfer.The conclusion reports more complex behaviors and higher transfer performance relative to prior environment-design approaches.

Broader Impact

UED could support robust deployment by automatically generating challenging environments that expose cases designers did not anticipate. Its broader applications may bring both benefits and risks as emergent complexity expands system capabilities.

  • UED applies to unsupervised RL, transfer learning, and robust RL, with potential to improve the viability of real-world AI systems.
  • The potential benefits include reduced costly human error, increased efficiency, and automation of dangerous or difficult tasks.
  • Potential risks include increased unemployment and improved capabilities of automated weapons, with emergent complexity possibly broadening robotics applications.
  • UED could support robust systems that make better decisions in uncertain environments, linking environment design to decisions under ignorance.
  • UED can automatically generate interesting and challenging environments that may reveal troublesome cases before deployment.

A Generality of UED

UED provides a general framework connecting environment-conditioned policy evaluation with decision rules under uncertainty. The paper characterizes the supported orderings through total domination and policy-conditioned environment distributions.

  • Definitions: A policy is totally dominated when every outcome it can obtain is worse than every outcome obtainable by another policy.
  • Definitions: Decision rules that respect total domination never prefer a policy whose best possible outcome is below another policy’s worst possible outcome.
  • Characterization: Any ordering respecting total domination can be represented by maximizing expected value under a policy-conditioned distribution of environments.
  • Minimax regret: The framework includes minimax regret as a representable decision rule, with a constructed environment policy shifting probability toward regret-maximizing parameterizations.
  • Characterization: Theorem 6 states that, in a finite UPOMDP, an ordering is representable by an environment policy exactly when it respects total domination and treats equal deterministic outcomes equally.
  • Proof strategy: The construction defines environment-policy values inductively so each policy’s value remains between constraints imposed by lower- and higher-ranked policies.
  • Minimax regret: Weak total domination is introduced to handle policies whose maximum outcome equals another policy’s minimum outcome, requiring a special proof case.

C Minimax Regret Always Succeeds when There is a Clear Notion of Success

Under separated SUCCESS and FAILURE reward ranges, minimax regret selects a policy that succeeds whenever success is achievable. The compared alternatives can instead favor poor worst-case or average outcomes.

  • Minimax regret chooses a policy that succeeds whenever any policy can succeed, provided SUCCESS and FAILURE rewards are sufficiently separated.
  • The proof shows that a minimax-regret policy cannot leave a solvable parameterization unsolved, because doing so would exceed the regret bound established by a universally successful policy.
  • Maximin may choose a policy that fails on solvable tasks because it optimizes only the worst-case outcome.
  • Expected-return maximization can reject a policy guaranteeing success when other policies have higher average reward under every parameter distribution.
  • Table 3 defines SUCCESS as scores from [75, 100] and FAILURE as scores from [−1, 0].

D Nash solutions to PAIRED

The Nash-equilibrium analysis compares protagonist and antagonist performance across parameterizations. It also indicates that a capable antagonist can support minimax-regret learning even without coordination with the adversary.

  • At Nash equilibrium, the protagonist’s utility is at least the antagonist’s utility for every parameterization.
  • This follows because the protagonist could always copy the antagonist, preventing the adversary from selecting an environment where the antagonist outperforms it.
  • A capable antagonist can lead the protagonist to learn the minimax-regret policy even when antagonist and adversary coordination is absent.
  • The analysis suggests strengthening the antagonist as a possible way to improve the protagonist.

E.1 Alternative methods for computing regret

The paper evaluates population-based and flexible alternatives for approximating regret. Both retain some transfer ability but underperform the original PAIRED method, consistent with the importance of antagonist–adversary coordination.

  • Alternative regret approximations: Population-based training computes regret from the best and mean-performing agents across a population, avoiding reliance on a fixed antagonist.For each generated environment, every population agent collects one trajectory; regret uses the maximum agent return minus the population mean.
  • Alternative regret approximations: Flexible PAIRED uses K = 2 agents and selects the currently best-performing agent as the antagonist.This approach avoids the expense of a larger population but does not keep the antagonist fixed.
  • Complexity: Neither the combined population nor flexible approach shows improved environment complexity over the proposed PAIRED method.Figure 5 measures generated-environment statistics and maze lengths solved; results use five random seeds with 95% CI error bars.
  • Transfer performance: Both alternatives retain the ability to solve complex transfer tasks, unlike minimax and domain randomization, but perform worse than original PAIRED.The comparison includes complex tasks such as labyrinth and maze environments.
  • Interpretation: The authors connect degraded performance to losing coordination between the environment adversary and antagonist.Coordination is an assumption in Theorem 2, which links Nash equilibrium to a minimum-regret protagonist policy.
  • Agent objectives: Training agents on environment reward rather than regret appears more effective for learning complex behavior, although regret optimization can provide good transfer performance.The authors hypothesize that regret is noisy because the other agent’s stochastic performance varies outside the learner’s control.

F.2 Hopper Experiments

The Hopper experiments test PAIRED with an adversary that applies shared joint torques to the protagonist and antagonist. Policies are trained with PPO while adversary strength increases during training.

  • Environment design: The Hopper adversary applies additional joint torques at a proportion α of the original agent’s strength.In PAIRED, both protagonist and antagonist receive the same torques.
  • Architecture and observations: The adversary observes only the timestep, while each policy uses a two-hidden-layer DNN with width 32.The networks use tanh activations internally and a linear output activation.
  • Training: Policies are trained simultaneously with PPO while α is scaled from 0.1 to 1.0 over 300 iterations, followed by full-strength training.Agents are pretrained without an adversary for 100 iterations.
  • Hyperparameters: PAIRED and minimax use different best-performing hyperparameters for learning rate and GAE lambda.Minimax performs best with learning rate 5e-4 and lambda 0.5, whereas PAIRED uses 5e-3 and lambda 0.09.
Loading 2012.02096v2…