Source-linked AI summary
Illuminating Generalization in Deep Reinforcement Learning through Procedural Level Generation
Niels Justesen, Ruben Rodriguez Torrado, Philip Bontrager, Ahmed Khalifa, Julian Togelius, Sebastian Risi
TL;DR
Fixed-level deep RL can overfit and fail to generalize to new levels. This paper trains agents with procedurally generated levels, including difficulty adaptation, and finds generalization within some generated distributions, with human-level transfer depending on generator design.
Problem
Deep RL policies trained in fixed environments often overfit to particular observations and fail on new or slightly modified levels.
Method
The paper generates a new procedural level for each episode, uses Progressive PCG to adapt difficulty to agent performance, and analyzes generator distributions with dimensionality reduction and clustering.
Results
Procedural training enables generalization to unseen levels within the training distribution; PPCG reaches a 57% win rate on difficult Frogs levels versus 0% for non-progressive training.
Takeaways & Limitations
Generalization to human-designed levels depends strongly on the design of the procedural level generators.
Takeaways & Limitations
The results vary across games, and matching procedural-level distributions to human-designed levels remains a challenge.
Abstract
from arXiv · showhide
Deep reinforcement learning (RL) has shown impressive results in a variety of domains, learning directly from high-dimensional sensory streams. However, when neural networks are trained in a fixed environment, such as a single level in a video game, they will usually overfit and fail to generalize to new levels. When RL models overfit, even slight modifications to the environment can result in poor agent performance. This paper explores how procedurally generated levels during training can increase generality. We show that for some games procedural level generation enables generalization to new levels within the same distribution. Additionally, it is possible to achieve better performance with less data by manipulating the difficulty of the levels in response to the performance of the agent. The generality of the learned behaviors is also evaluated on a set of human-designed levels. The results suggest that the ability to generalize to human-designed levels highly depends on the design of the level generators. We apply dimensionality reduction and clustering techniques to visualize the generators' distributions of levels and analyze to what degree they can produce levels similar to those designed by a human.
1 Introduction
Deep RL agents trained on fixed game levels can overfit to specific observations and fail to generalize. The paper studies procedural level generation as a way to investigate and reduce this overfitting.
- Fixed-level training can produce policies that fail on related problems or even slightly modified versions of the same game.
- The paper reports substantial overfitting on 2D arcade games and argues that fixed-level policies may memorize action sequences instead of learning general strategies.
- Procedural Content Generation is introduced into training to address fixed-environment overfitting, while also raising the possibility of overfitting to the generated-level distribution.
- Progressive PCG increases level difficulty to match agent performance while generating a new level at every episode.
- The study analyzes generated-level distributions with dimensionality reduction and clustering to assess similarity to human-designed levels and implications for generalization.
- The primary goal is understanding overfitting and generalization in deep RL, rather than maximizing performance on human-designed levels.
2 Related Work
Related work contrasts standard evaluation on training tasks with evaluation on unseen levels and situates procedural generation and progressive difficulty within broader learning research.
- Supervised learning typically evaluates accuracy on a test set separate from training, whereas RL research often reports performance on the task used for training.
- Several game AI competitions evaluate controllers on inaccessible levels, but these competitions generally do not combine learning agents with procedural level generation.
- Randomization in simulated robotics and video games has been used to improve generality, including transfer from simulation to realistic settings.
- Progressively harder training tasks have appeared as incremental evolution, curriculum learning, and coevolutionary approaches.
- Automated curricula select training samples or tasks according to learning progress, while other methods generate new tasks or use teacher-student selection.
- A prior protocol used large training and test sets to study RL generalization; this work adds adaptive difficulty and near-endless generation across several complex games.
3 General Video Game AI Framework
The study uses the GVG-AI framework, where games and ASCII-grid levels are specified declaratively. Constructive generators create playable levels for four games with controllable difficulty.
- General Video Game AI Framework: GVG-AI is a flexible framework for advancing general AI through video-game playing, with more than 160 games specified in VGDL.
- General Video Game AI Framework: VGDL specifies game objects and interaction rules, while levels are ASCII grids whose characters represent objects.
- General Video Game AI Framework: GVG-AI Gym exposes pixels, incremental rewards, and win-or-loss signals through a unified RL interface.
- Parameterized Level Generators: Constructive generators are designed for Boulderdash, Frogs, Solarfox, and Zelda, using game knowledge to produce directly playable levels.
- Parameterized Level Generators: Boulderdash generation uses cellular automata for map layout before placing the player, door, gems, and enemies.
- Parameterized Level Generators: Frogs generation assigns rows as roads, water, or forest, then adds cars and logs to the corresponding rows.
- Parameterized Level Generators: Solarfox generation places the player centrally, creates gems in one region, and replicates the pattern across the map.
- Parameterized Level Generators: Zelda generation builds a maze with Prim’s algorithm, removes walls, and places the player, key, door, and enemies.
4 Procedural Level Generation for Deep RL
The framework generates a new level at each episode and adapts its difficulty during training. Progressive PCG begins easily and changes difficulty according to episode outcomes.
- The paper proposes generating a new level whenever an episode begins so training exposes the agent to many environment variations.
- Continuous exposure to new levels encourages general strategies but makes learning harder, especially with sparse rewards.
- Progressive PCG lets the learning algorithm control generated-level difficulty, initially creating easy levels and increasing difficulty as the agent learns.
- PPCG starts at difficulty 0, increases difficulty by α after wins, decreases it after losses, and uses α = 0.01 in the experiments.
- The study compares PPCG with PCG X, which trains on procedurally generated levels at a constant difficulty X.
5 Experiments
The experiments evaluate A2C under human-designed, fixed-difficulty procedural, and progressively difficulty-adjusted training regimes across four games.
- A2C uses the OpenAI Baselines implementation with the GVG-AI Gym framework and a convolutional network.The network has three convolutional layers and one fully connected layer, producing policy and value outputs.
- Four training approaches compare single-level, multi-level human-designed, fixed-difficulty procedural, and Progressive PCG training.Progressive PCG adjusts generated-level difficulty to match agent performance.
- Each setting was repeated four times and tested on procedural levels at difficulties 0.5 and 1, plus five human-designed levels.Each model was evaluated 30 times per test setup, yielding 120 episodes per test set for each training approach.
- All four approaches were tested on Zelda, while only PCG 1 and Progressive PCG were tested on Solarfox, Frogs, and Boulderdash.The reduced coverage for three games was due to computational constraints.
6 Results
Fixed-level training produces strong training performance but poor test performance, whereas procedural training supports generalization within generated-level distributions. Generalization to human-designed levels varies substantially by game and generator.
- 6.1 Training on a few Human-Designed Levels: Single-level Zelda policies reach high training scores but perform poorly on both human-designed and procedurally generated test levels.Training scores approach the maximum, while test scores are often below the random-policy baseline, indicating memorization.
- 6.2 Training on Procedurally Generated Levels: Fixed-difficulty procedural training learns general behavior in generated-level distributions for Zelda, Solarfox, and Boulderdash, but not Frogs.The reported scores are mediocre in Zelda, Solarfox, and Boulderdash, with no progress observed in Frogs.
- 6.2 Training on Procedurally Generated Levels: 0.57 (57% win rate) was achieved by Progressive PCG on procedurally generated Frogs test levels at difficulty 1.This difficulty was described as comparable to human levels.
- 6.3 Generalization on Human-Designed Levels: Procedural training enables generalization to unseen levels within the training distribution, but transfer to five human-designed levels remains game-dependent.The paper explicitly raises human-designed-level transfer as a separate question.
- 6.3 Generalization on Human-Designed Levels: PCG 1 shows similar scores on human-designed and procedurally generated Solarfox levels, while PCG and PPCG fail to win on human-designed Frogs levels.In Boulderdash, PCG 1 averages 5.08–10.28 points on human-designed levels versus 8.32–14.63 on generated levels.
- 6.4 Qualitative Analysis of Agent Replays: Qualitative replays show game-specific behaviors, including reliable enemy avoidance in Zelda, diamond collection in Solarfox, goal-directed movement in Frogs, and limited long-term planning in Boulderdash.The Solarfox behavior is described as remarkably human-like, while Zelda agents only sometimes complete the key-and-door objective.
7 Exploring the Distribution of Generated Levels
The paper projects generated and human-designed levels into two dimensions and clusters them to inspect distributional similarity. The resulting structures differ markedly across games, with some human levels appearing as outliers.
- The study generates 1000 difficulty-1 levels per game, reduces level structure to two PCA dimensions, and clusters the results with DBSCAN.Human-designed levels are included in both the dimensionality-reduction and clustering processes.
- Figure 3 encodes level distributions after PCA and DBSCAN, with human-designed levels as white circles, outliers as black points, and larger centroids.DBSCAN uses ϵ = 0.5 and a minimum of 10 samples per cluster.
- Solarfox generated levels form three broad groups based on whether they contain green diamonds, blue diamonds, or both.Human-designed levels use only one diamond type at a time and therefore occupy two clusters.
- Frogs generated levels form 19 clusters because roads and rivers strongly affect level structure.Human-designed level 4 is the most distant outlier because its starting-row river is not captured by the generator.
- In Boulderdash, all human-designed levels are distant outliers relative to the generated distribution.The paper relates this pattern to human levels having fixed open space and one-tile padding, unlike the more varied cave-like generated levels.
8 Discussion
The experiments show that evaluating reinforcement-learning policies on a single game or narrow observation subspace can conceal overfitting. Procedural training introduces new challenges, especially matching level difficulty and human-designed level distributions.
- Evaluation and overfitting: Policies evaluated on a small observation subspace may map specific observations to actions without learning general game concepts.The authors argue that reporting success on the training game alone can mask memorized action sequences.
- Evaluation and overfitting: Evaluating an agent across several game variations is necessary when the goal is to assess whether it learned to play generally.
- Procedural-generation challenges: Scaling level difficulty smoothly is a generator-specific challenge: padding easy Frogs levels helped early training but was insufficient for Boulderdash.
- Procedural-generation challenges: Matching procedurally generated levels to human-designed levels requires analyzing generator distributions with dimensionality reduction and clustering.The tool is intended to improve constructive generators or guide future search-based generators.
- Procedural-generation challenges: Across four games, analyzing both successes and failures provided insights into the generalization abilities of deep-RL algorithms.
9 Conclusion
The paper finds that policies trained on one or a few levels often fail on unseen levels, and proposes Progressive PCG, which generates a new level each episode while adapting difficulty. Its benefits vary by game and evaluation distribution.
- Conclusion: Policies trained on one or a handful of levels often fail to generalize to levels excluded from training.
- Conclusion: Progressive PCG generates a new level for each episode and dynamically adapts difficulty during training.
- Conclusion: 57% win rate was achieved on difficult Frogs levels with Progressive PCG, compared to 0% for the non-progressive approach.
- Conclusion: In Zelda, Progressive PCG was superior across procedurally generated and human-designed levels, whereas Solarfox and Boulderdash favored fixed-difficulty procedural training.