PaperlayerView exact revision on arXiv

Source-linked AI summary

Open-Ended Learning Leads to Generally Capable Agents

Open Ended Learning Team, Adam Stooke, Anuj Mahajan, Catarina Barros, Charlie Deck, Jakob Bauer, Jakub Sygnowski, Maja Trebacz, Max Jaderberg, Michael Mathieu, Nat McAleese, Nathalie Bradley-Schmieg, Nathaniel Wong, Nicolas Porcel, Roberta Raileanu, Steph Hughes-Fitt, Valentin Dalibard, Wojciech Marian Czarnecki

arXiv:2107.12808v2cs.LGcs.AIcs.MA

TL;DR

The paper addresses the challenge of training agents that generalise beyond fixed game goals across vast, diverse task spaces. It introduces an open-ended learning process in XLand and obtains agents with broad held-out-task ability, emergent behavioural heuristics, and rapid finetuning transfer.

  • Problem

    Agents trained for specific games can catastrophically fail when test-time goals differ, while broad task spaces also make progress difficult to measure because task returns are incomparable.

  • Method

    The authors combine the multi-agent, procedurally generated 3D XLand environment with open-ended deep reinforcement learning and an iterative evaluation metric based on normalised score percentiles.

  • Results

    The resulting agents show broad ability across held-out tasks, including out-of-distribution probes, with general heuristics such as experimentation, success recognition, and cooperation.

  • Takeaways & Limitations

    The results support training agents without human demonstrations that generalise across vast task spaces and can be quickly finetuned for complex out-of-distribution tasks.

  • Takeaways & Limitations

    Agents fail on some unseen environmental conditions, such as inescapable chasms, and lack theory-of-mind behaviour for manipulating a co-player’s movements.

Abstract

from arXiv · show

In this work we create agents that can perform well beyond a single, individual task, that exhibit much wider generalisation of behaviour to a massive, rich space of challenges. We define a universe of tasks within an environment domain and demonstrate the ability to train agents that are generally capable across this vast space and beyond. The environment is natively multi-agent, spanning the continuum of competitive, cooperative, and independent games, which are situated within procedurally generated physical 3D worlds. The resulting space is exceptionally diverse in terms of the challenges posed to agents, and as such, even measuring the learning progress of an agent is an open research problem. We propose an iterative notion of improvement between successive generations of agents, rather than seeking to maximise a singular objective, allowing us to quantify progress despite tasks being incomparable in terms of achievable rewards. We show that through constructing an open-ended learning process, which dynamically changes the training task distributions and training objectives such that the agent never stops learning, we achieve consistent learning of new behaviours. The resulting agent is able to score reward in every one of our humanly solvable evaluation levels, with behaviour generalising to many held-out points in the universe of tasks. Examples of this zero-shot generalisation include good performance on Hide and Seek, Capture the Flag, and Tag. Through analysis and hand-authored probe tasks we characterise the behaviour of our agent, and find interesting emergent heuristic behaviours such as trial-and-error experimentation, simple tool use, option switching, and cooperation. Finally, we demonstrate that the general capabilities of this agent could unlock larger scale transfer of behaviour through cheap finetuning.

1| Introduction

The paper targets agents that generalise beyond trained games, using XLand and open-ended learning to develop broad capabilities across diverse held-out tasks.

  • Deep RL agents often remain constrained to trained games, and changing task goals can cause catastrophic failure.
  • The resulting agent generalises beyond training distributions, scoring reward across humanly solvable held-out tasks including hide and seek and capture the flag.
  • XLand provides procedurally generated 3D worlds and multiplayer games spanning competitive, cooperative, balanced, imbalanced, and strategically deep tasks.
  • The training process measures performance with normalised score percentiles and iteratively adapts task distributions and objectives to improve agents across the task space.
  • Successive agent generations bootstrap from earlier policies through policy distillation and contribute new multiplayer policies for later training.
  • The study reports general heuristics, cooperation, and strong gains from finetuning for 100 million steps compared with zero-shot performance and training from scratch.

2| XLand Environment Space

XLand combines consistent interaction mechanics with smoothly varying physical worlds, games, and co-player policies to form a broad multi-agent task space.

  • XLand is a 3D multi-player environment with rigid-body physics, first-person observations, egocentric movement, manipulable objects, and world-affecting gadgets.
  • Consistency comes from shared controls, observations, gadget and movement dynamics, while topology, object placement, lighting, goals, and co-player policies vary smoothly.
  • Each task is a Cartesian product of a world, one goal per player, and policies for the remaining players.
  • Players receive pixel-based first-person renders and proprioceptive readings together with their goals, while environmental reward is excluded from observations.
  • A task’s physics transition depends on the simultaneous actions of all players, and reward is given when a player’s goal is satisfied.
  • The environment’s smooth game construction supports transitions from simple object-finding tasks to strategically deep games.

3| Environment Properties

XLand combines vast, diverse worlds and games into a task space whose navigational and game properties can vary smoothly, enabling structured analysis of environment complexity.

  • World representation: Worlds are high-dimensional grid environments represented by height maps and topology graphs that encode navigable paths.Topology edges represent straight-line travel between neighboring tiles, including same-level movement, falling, and accessible ramps.
  • World vastness: More than 10^16 unique 9×9 world topologies remain after correcting for 8 possible symmetries.The count concerns topologies with connected ramps and at least 50% accessible area, estimated using Monte Carlo sampling.
  • World smoothness: Small topographic mutations produce bounded changes in shortest-path and resistance-distance distributions, supporting empirical smoothness of the world space.Figure 5 relates tile-space L2 distance to Cauchy-Schwarz Divergence, while local mutations generate the compared world pairs.
  • Game properties: Games vary across options, exploration difficulty, and cooperative or competitive structure, forming a diverse and smooth game space.Exploration difficulty is the fraction of predicate states in which no player receives reward; trivial goals have κ(g) equal to 0 or 1, making every policy optimal.
  • Game vastness: More than 10^37 unique 2-player games arise from 200 atomic predicates and 3 options, including more than 10^18 goals.These bounds are provided as functions of options, atoms, and conjunctions, illustrating the scale of the evaluation space.

4| Goal and Metric

The paper defines general capability through few catastrophic failures, broad competence, and preference for broad ability over narrow expertise. It measures progress with normalized score percentiles, iteratively updated using estimated game-level optima and Pareto dominance.

  • Different task reward scales make averaging misleading because high-value tasks dominate and rare failure modes disappear.
  • The infimum captures worst-case performance but provides little learning signal when some tasks are impossible or extremely hard.
  • General capability prioritizes few catastrophic failures, competence across many tasks, and broad ability over narrow competency.
  • Normalized Percentiles: Game-level Nash-equilibrium estimates provide dynamic normalizers that improve as successive agents exceed the existing frontier.The resulting metric supports iterative improvement without requiring a fixed scalar objective.
  • Normalized Percentiles: Normalized percentiles represent performance as 51 ordered values from the 0th through 50th percentile, including coverage and median performance.Lower percentiles expose performance on harder tasks, while the first positive percentile indicates the fraction of games receiving any reward.
  • Normalized Percentiles: Agents are considered better only under Pareto dominance across percentiles, preserving improvements in both breadth and competency.

5| Learning Process

The learning process combines deep RL, dynamically generated task distributions, and population-based training to improve agents across XLand’s held-out task space. Its goal-conditioned architecture represents observations and goals separately, predicts predicate states and option values, and switches options when their estimated value is higher.

  • Training combines deep RL, dynamic task generation, and population-based training to improve normalized percentiles on validation tasks.
  • The agent receives RGB images, proprioception, and a task goal, then a recurrent network produces its value prediction and policy.
  • Goal attention network: Goal attention embeds the goal and its options separately, enabling the network to compare option-specific value estimates.
  • Goal attention network: The agent switches to another option when its predicted value exceeds the current estimate for the whole goal.
  • Goal attention network: An auxiliary predicate predictor shapes internal representations without directly affecting the policy, while consistency losses align full-goal and option values.
  • Dynamic task generation: Task proposals are filtered using agent and control-policy performance so training emphasizes tasks that are neither uninformatively easy nor unusably hard.

3. The control policy is not performing well

The process adapts task-generation criteria, hyperparameters, objectives, and populations over successive generations to avoid training saturation. Early self reward-play improves exploration and participation, while later regular RL supports competence within an open-ended learning process.

  • Dynamic filtering criteria must change during training because fixed notions of task difficulty can later cause saturation or stalled learning.
  • Population-based training gives each agent its own task distribution and evolves agents only when one Pareto-dominates another across normalized percentiles.
  • Generational training: Generational training bootstraps from prior populations through policy distillation while adding new policies as multiplayer training opponents.
  • Generational training: Self reward-play is used in early generations to encourage exploration before later generations use the regular RL objective.
  • Self reward-play: Self reward-play drastically improves exploration and yields significantly higher participation within the same training time, but leaves normalized percentiles low.
  • Combined Learning Process: The combined system can remain open-ended because it iteratively updates agents and the validation metric without optimizing a bounded objective.

6| Results and Analysis

The final agent achieved broad held-out performance, with strongest relative gains on challenging competitive and relational tasks. Its analysis revealed emergent strategies including cooperation, experimentation, option switching, and simple tool use, while failures remained concentrated in impossible or untrained situations.

  • Overall performance: 95% participation, 82% 10th percentile, and 112% 50th percentile normalised test scores were reached by the final generation-5 agent.It also achieved 585 average return on hand-authored tasks, at least 65% of the optimal policy value.
  • Training dynamics: Generation 3 onward produced harder training distributions through stronger opponents, more competitive scenarios, and fewer game options.These changes emerged from the agent’s performance rather than direct control over the training properties.
  • Coverage: After impossible tasks were removed, the agent participated in every test task, indicating broad coverage of the solvable evaluation space.The excluded tasks required impossible cooperation, unreachable physical placements, or contained a rare physics bug.
  • Relative performance: Relative normalised scores were higher on more competitive games and on tasks requiring many goal predicates, initial atom changes, or object-object interactions.The largest improvements occurred in challenging regions of the game space, including games with fewer options.
  • Emergent behaviour: The final agent improved behaviour across Hide and Seek, Capture the Flag, King of the Hill, XRPS, and Stop Rolling through task-general heuristics.Examples include following opponents, consistently navigating, countering opponent choices, and blocking objects with its body.
  • Emergent behaviour: Probe tasks showed within-episode experimentation: the agent reshuffled objects, visually inspected them, and retained configurations it inferred were rewarding.The agent did not perceive reward directly and instead inferred success from observations.

7| Related Work

The work connects open-ended learning to prior research on multi-agent learning, procedural generation, automated curricula, goal curricula, and world-agent co-evolution. Its approach combines these lines of work while extending iterative improvement beyond agents to worlds, games, and co-players.

  • Multi-agent and progressive learning: The paper addresses multi-agent learning challenges including nonstationarity, exploration, and interaction modelling, while treating multi-agent systems as potential sources of autocurricula.
  • Iterative improvement and percentiles: Its iterative improvement framework builds on prior methods using opponent-relative goals, internal agent rankings, and self-play, extending these ideas to worlds, games, and co-players.
  • Procedural environment generation: Related procedural-generation work evolves game rules, levels, or paths using methods including GANs, CPPNs, NEAT, and PCGRL.
  • Curriculum over tasks: The paper's dynamic task generation and world-agent co-evolution are forms of automated curriculum learning that adapt the agent's training distribution over time.
  • Curriculum over goals: Prior goal curricula generate goals from previously observed states, adversarial procedures, epistemic uncertainty, or curriculum mechanisms, whereas this work applies curriculum ideas within a broader task space.
  • World-agent co-evolution: World-agent co-evolution shares with POET and PAIRED the generation of dynamic, high-dimensional world distributions for agents.

8| Conclusions

The paper introduces XLand and an open-ended learning process for training generally capable agents across a vast, held-out task space. The resulting agents show broad abilities, emergent behavioural heuristics, and rapid finetuning on complex out-of-distribution tasks.

  • XLand combines procedurally generated worlds and multiplayer games into a vast, diverse, smooth task space for training and evaluating generally capable agents.
  • Training dynamically generates task distributions from agent behaviour, sequentially distills populations across generations, and iteratively improves normalized score percentiles.
  • Agents show broad ability across held-out tasks, with emergent heuristics including experimentation, success recognition, and greater cooperation with competent agents.
  • The pretrained agents generalize zero-shot across vast task spaces and can be quickly finetuned on complex out-of-distribution tasks.

A.1.1| Procedural World Generation

Procedural world generation constructs playable 3D environments from tiled topology, probabilistic object and player placement, and conditioning mechanisms. World-agent co-evolution then shifts generation toward navigationally challenging worlds that track the agent's capabilities.

  • Topology: Wave Function Collapse generates topology by assigning compatible 3D geometry tiles under connectivity constraints.
  • Objects and players: CPPN-based probability maps determine initial 3D positions for objects and players within the playable topology.
  • Conditional world generation: Conditional generation samples worlds similar to an existing world by biasing topology and adding noise to object and player locations.
  • Game-conditioned worlds: Game-conditioned generation modifies a world so every player, object, and topological element referenced by a game is present and exposed in the playable area.
  • World-agent co-evolution: World-agent co-evolution mutates existing worlds and retains worlds whose success probability lies within a target range, producing increasingly challenging training worlds.

A.1.2| Counting worlds

The counting analysis estimates how many procedurally generated world topologies contain a large, internally connected, non-escaping playable region. It uses structural bounds and Monte Carlo sampling rather than an exact count.

  • The target worlds contain a region A of at least half the world, with paths between every pair of points and no path leaving the region.
  • The analysis gives lower and upper bounds because the constraints make the exact number of qualifying worlds difficult to compute.
  • An upper bound counts all combinations of six flat tiles, four ramp orientations, and four diagonal-tile orientations across the grid.
  • For the lower bound, a strongly connected subgrid is embedded into the full grid using ramps, flat tiles, and highest-floor fillers while preserving accessibility and containment.
  • The number of qualifying worlds is estimated with Monte Carlo sampling using 200,000 worlds, with additional edge flexibility contributing a factor of 2^(w+h) when dimensions are even.

A.1.3| Worlds linear projection

The paper learns low-dimensional linear projections of world topologies to visualize properties such as navigational complexity, using symmetry-aware parameterization to reduce overfitting. The resulting templates include checkerboard-like patterns associated with navigational complexity and shortest-path structure.

  • Projection method: The analysis learns a linear projection of world space for visualizing a positive-valued property h·(w).The projection is optimized through gradient descent over parameters θ=(θ_W, θ_b, θ_c).
  • Projection method: The topology encoding assigns normalized floor levels to flat tiles and half-floor values to ramps between adjacent levels.For flat tiles at level k, τ(t_k)=1/5 k; ramps receive the midpoint value.
  • Projection method: The projection is designed so Euclidean distance from a learned point predicts distance from the target property plus a learned bias.This geometry can produce circular or more linear arrangements depending on the learned bias location.
  • Projection method: 81 to 15 trainable weights are reduced by enforcing invariance to rotations and symmetries, significantly reducing overfitting.The 9 by 9 topology projection is parameterized as an average over all 8 rotations and symmetries.
  • Results: Checkerboard-like templates emerge and correspond naturally to navigational complexity and the distribution of shortest paths.The first two figure columns show projection dimensions, while the following columns show entry signs to emphasize the pattern.

A.2| Games

The described XLand instance is presented as a current, expandable configuration rather than a fixed system definition.

  • Scope: The technical details describe the current instance of XLand’s game space.The listed relations, predicates, player counts, and options characterize this instance.
  • Scope: The system is not constrained to the listed relations, predicates, number of players, or options.These components can be expanded to cover a richer space.
  • Scope: The stated design leaves room for expanding XLand beyond its current game-space configuration.The passage explicitly connects this flexibility to a richer space.

A.2.1| Relations

XLand defines games through spatial and perceptual relations among objects, players, and floors, with symmetry-aware enumeration producing 212 unique atomic predicates. Naive random game sampling produces highly non-uniform balance and competitiveness distributions.

  • Relations: near(a,b) is true when object a is at most 1 meter from object b.A player avatar is given as 1.65m tall for reference.
  • Game distributions: Randomly sampling predicate matrices creates an extremely non-uniform distribution over balance and competitiveness, making fully competitive games almost impossible to obtain.The figure compares distributions from naive uniform sampling and alternative mechanisms.
  • Relations: The near relation measures surface-aware distance rather than merely distance between object centers.The construction accounts for object size by comparing closest surface points around a midpoint.
  • Relations: see(a,b) checks unobstructed center-to-center visibility for objects and field-of-view visibility when a is a player.The rule depends on whether the first argument is a player.
  • Relations: on(a,b) denotes contact between a player or object and the upper surface of a specified floor colour.The relation applies only to a floor and a player or object.
  • Relations: hold(a,b) denotes a player holding a specific object with its beam, including the possibility that two agents hold the same object simultaneously.The relation is restricted to players and objects.

A.2.3| Generating games

Games are generated by local search over predicate-based option matrices to target specified balance and competitiveness, with validity checks and repeated improvement steps. The process also supports recoloured variants, simple three-player construction, and PCA over game representations.

  • Generating games: Naive random sampling of six predicates and a {-1,0,1} matrix yields highly non-uniform balance and competitiveness.Fully competitive games are almost impossible to sample randomly.
  • Generating games: Local search generates games with specified numbers of options and conjunctions while targeting balance b* and competitiveness c*.The procedure starts from a random game matrix and predicate set, computes b and c, and iteratively modifies a goal.
  • Generating games: Candidate modifications flip, add, remove, copy, or negate predicates and are retained only when they preserve nontriviality and option uniqueness.The highest non-negative improvement is selected; search terminates when all modifications are negative.
  • Generating games: The search is repeated 10 times and the best game is selected by distance to the target balance and competitiveness.Exact convergence is not guaranteed because some target combinations are impossible.
  • Generating games: A game can be recoloured bijectively to create another game with the same number of options, conjunctions, balance, and competitiveness.The recolouring preserves the relevant game characteristics by bijectivity.
  • Generating games: Recolouring may fail to produce a distinct game, so the process retries until success or after 100 unsuccessful attempts.Games without objects, such as Hide and Seek, cannot produce new games through this method.
  • Generating games: Three-player games are constructed by mixing options from two-player games, randomly negating predicates, and permuting agents with their goals.The construction is explicitly described as a simplification.
  • Game-space representation: PCA over game space uses predicate-valuation vectors whose dimensions indicate whether particular predicate valuations are active.The mapping produces vectors of length N_φ.

A.3| Holding out tasks from training

The paper constructs held-out task sets by excluding unique games and worlds from dynamically generated training, then uses theory to characterize the resulting task space and its local properties.

  • Training generation rejects any game colliding with the unique test or validation games, including collisions under recolouring.
  • Training generation similarly rejects worlds colliding with the unique held-out test or validation worlds.
  • Validation and test tasks are formed by randomly matching corresponding worlds and games, with no shared game, world, or task between them or dynamic training.
  • The task space uses a decomposed action representation with six discrete action dimensions, making all combinations feasible across 2100 possible actions.
  • The theory establishes that every policy is optimal for goals with κ(g)=0 or κ(g)=1, while exploration difficulty is 1-Lipschitz.
Loading 2107.12808v2…