Learning objectives

  • Explain the difference between naive adversarial environment design (minimizing agent return) and PAIRED (maximizing agent regret relative to an antagonist).
  • Implement an environment design setup: an adversary proposes environment parameters (e.g. maze layouts), a protagonist agent attempts to solve them, and the curriculum adapts.
  • Train the adversary and agent in a loop: adversary generates environments, agent learns, and the adversary adapts difficulty.
  • Explain why regret prevents the adversary from collapsing into generating impossible, walled-off environments.
  • Compare agent performance and generalization on adversary-generated curricula vs fixed or uniformly random levels.
  • Relate PAIRED and UED to game AI (procedural level generation) and robot navigation (curriculum for diverse obstacles).

Concept and real-world RL

Unsupervised Environment Design (UED) trains an adversary (or generator) to create training environments (e.g. maze layouts, obstacle densities) alongside the learning agent. If the adversary simply plays a zero-sum game to minimize agent return, it quickly collapses into creating trivially impossible environments (e.g. walling off the start or removing the goal), leaving the agent with zero learning signal.

PAIRED (Protagonist Antagonist Induced Regret Environment Design) solves this pathology by introducing a second agent (the antagonist) and defining the adversary’s reward as regret: \[\text{Regret} = V^{\text{antagonist}} - V^{\text{protagonist}}\] If the maze is impossible, neither agent can solve it (Regret = 0). If the maze is trivially easy, both solve it (Regret = 0). The adversary is rewarded only when the antagonist can solve the maze but the protagonist has not yet mastered it, dynamically targeting the protagonist’s “zone of proximal development” without any manual difficulty labels.

Where you see this in practice: PAIRED (Dennis et al., NeurIPS 2020), ACCEL, and Domain Randomization; procedural content generation and robust policy learning.

Illustration (PAIRED): The adversary designs mazes to minimize agent return; the agent learns to solve harder mazes. The chart below shows agent return on a fixed test maze over training iterations.

Exercise: Implement a simple version of PAIRED: an adversary designs a maze to minimize the agent’s performance, and the agent learns to solve any maze. Train both adversary and agent in a loop.

Professor’s hints

  • Maze parameterization: e.g. binary grid (wall or free) of size H×W, or a small set of parameters (e.g. number of rooms, corridor length). The adversary outputs these parameters; the environment is built from them.
  • Adversary objective (Zero-sum vs Regret):
    • Naive zero-sum: Adversary maximizes negative protagonist return \(-R_{\text{protagonist}}\). You must enforce hard solvability constraints (e.g. BFS check that a path exists), or the adversary will immediately wall off the agent!
    • Full PAIRED: Train a protagonist policy \(\pi_P\) and an antagonist policy \(\pi_A\). Reward the adversary with \(R_{\text{adversary}} = R_A - R_P\). The antagonist provides an existence proof that the maze is solvable.
  • Stability: Alternate or joint updates: update agent on current maze(s), then update adversary to generate mazes that create learning opportunities.
  • Use a small maze (e.g. 5×5 or 7×7) and a discrete set of maze designs so that the adversary’s output is tractable (e.g. small neural network or categorical distribution).

Common pitfalls

  • Adversary collapses into impossible mazes: Without regret (or a strict path-finding constraint), a return-minimizing adversary simply blocks the goal. Always either verify a valid start-to-goal path via BFS or implement the antagonist regret signal.
  • Agent too weak early: If the agent never solves any maze at the start, the adversary has no gradient. Consider starting with a pretrained agent or an initial phase where the adversary is weak (e.g. random mazes).
  • Balance: The relative learning rates of adversary and agent matter; if the adversary improves too fast, the agent may never learn. Tune or use a curriculum (e.g. limit adversary strength initially).
Worked solution (warm-up: adversarial RL)
Key idea: In adversarial RL we have two agents (or an agent and an adversary). The agent tries to maximize return; the adversary tries to minimize it (or to make the task hard). We train both; the equilibrium (if it exists) can yield a robust or diverse policy. Balance is key: curriculum (e.g. weak adversary first) or separate learning rates so the agent can keep up. Used in robust RL and some multi-agent settings.

Extra practice

  1. Warm-up: Why might training an agent on adversarially chosen mazes lead to more robust behavior than training on fixed or random mazes?
  2. Coding: Implement a minimal PAIRED: 5×5 grid, adversary outputs a 5×5 binary wall grid (with constraints: start at (0,0), goal at (4,4), at least one path). Agent is a small policy (e.g. MLP). Train for 500 iterations: agent does 10 episodes on current maze, adversary updates to reduce agent return. Plot agent return on a fixed test maze over training.
  3. Challenge: Add diversity to the adversary: encourage it to generate mazes that are different from each other (e.g. diversity bonus or entropy regularizer on maze distribution). Compare the diversity of mazes and agent generalization with and without diversity.
  4. Variant: Replace the PAIRED adversary with a random curriculum (uniformly random mazes) and a fixed curriculum (hand-designed easy-to-hard sequence). Compare agent generalization on a held-out test set across all three curricula after 500 iterations.
  5. Debug: The PAIRED adversary immediately generates impossible mazes (no path from start to goal) and the agent always gets 0 reward. The adversary is maximizing agent regret but never receives a penalty for unsolvable environments. Add a solvability check and describe how to penalize the adversary for generating unsolvable mazes.
  6. Conceptual: PAIRED optimizes for the “regret” of the agent — the gap between a protagonist’s return and an antagonist’s return. Why is regret a better curriculum signal than simply minimizing the agent’s return? What prevents the adversary from always generating trivially hard environments?