PaperlayerView exact revision on arXiv

Source-linked AI summary

Prioritized Level Replay

Minqi Jiang, Edward Grefenstette, Tim Rocktäschel

arXiv:2010.03934v4cs.LGcs.AI

TL;DR

Deep RL can overfit training experiences, so PCG environments provide a setting for testing generalization to unseen levels, where prior methods usually sample training levels uniformly. The paper introduces PLR to prioritize levels by estimated future learning potential, and reports improved sample efficiency and generalization, including a new Procgen state of the art when combined with UCB-DrAC. The method’s scope is limited where seed-based simulation or environment resets cannot adequately represent the target setting.

  • Problem

    Prior work commonly samples PCG training levels uniformly despite the policy-dependent learning potential of different levels, limiting the evidence for selective level sampling.

  • Method

    PLR selectively samples training levels by maintaining a replay distribution that prioritizes previously visited levels with higher estimated learning potential under the current policy.

  • Results

    PLR improves sample efficiency and generalization across the evaluated Procgen and MiniGrid settings, and combining it with UCB-DrAC sets a new Procgen state of the art.

  • Takeaways & Limitations

    Policy-dependent sampling can produce an implicit curriculum and improve deep-RL performance on procedurally generated environments.

  • Takeaways & Limitations

    PLR is not universally applicable when problems cannot be adequately represented by seed-based simulation or lack explicit environment resets.

Abstract

from arXiv · show

Environments with procedurally generated content serve as important benchmarks for testing systematic generalization in deep reinforcement learning. In this setting, each level is an algorithmically created environment instance with a unique configuration of its factors of variation. Training on a prespecified subset of levels allows for testing generalization to unseen levels. What can be learned from a level depends on the current policy, yet prior work defaults to uniform sampling of training levels independently of the policy. We introduce Prioritized Level Replay (PLR), a general framework for selectively sampling the next training level by prioritizing those with higher estimated learning potential when revisited in the future. We show TD-errors effectively estimate a level's future learning potential and, when used to guide the sampling procedure, induce an emergent curriculum of increasingly difficult levels. By adapting the sampling of training levels, PLR significantly improves sample efficiency and generalization on Procgen Benchmark--matching the previous state-of-the-art in test return--and readily combines with other methods. Combined with the previous leading method, PLR raises the state-of-the-art to over 76% improvement in test return relative to standard RL baselines.

1. Introduction

Deep RL often overfits training experiences, motivating procedural-content-generation benchmarks for testing generalization across unseen levels. The paper introduces Prioritized Level Replay, which samples training levels according to estimated future learning potential rather than uniformly.

  • Motivation: PCG environments generate levels with varying layouts, appearances, or dynamics, enabling evaluation on held-out test levels.Levels can represent configurations ranging from game instances to robotic manipulation states or Hanabi deck orderings.
  • Motivation: Prior methods commonly sample training levels uniformly, although different levels may offer different learning potential under the current policy.The paper frames policy-dependent level selection as a selective-sampling problem inspired by active learning.
  • Method: Prioritized Level Replay samples the next training level using estimated learning potential when replaying previously visited levels.PLR is presented as a method that can replace the experience-collection process in a broad range of RL algorithms.
  • Method: PLR updates level scores from the current policy and TD-errors collected along recent trajectories, then derives a replay distribution from those scores.The method tracks visited levels, their latest scores, and the episode counts at which they were last sampled.
  • Results: PLR improves generalization on 10 of 16 Procgen environments and combines with the previous leading method to achieve a new Procgen state of the art.The paper also reports an implicit curriculum over training levels in sparse-reward settings.

2. Background

PCG environments provide varied levels for studying RL robustness and generalization to unseen test levels. Background training typically samples from a finite set of levels, while prior curriculum findings motivate automatically discovering which levels are useful throughout training.

  • Definitions: A PCG environment maps a level identifier, such as a seed, to an environment instance with a unique configuration of varying factors.Examples include layouts, asset appearances, environment dynamics, and MiniGrid mazes with different room counts.
  • Definitions: Replaying a level means collecting a new trajectory on that level with the agent’s latest policy.This operational meaning distinguishes replaying levels from simply reusing past off-policy experiences.
  • Evaluation protocol: PCG generalization is evaluated by training on finite training levels and measuring performance on unseen test levels.Training levels are sampled from Ptrain(l|Λtrain), with finite training sets typically using a uniform distribution.
  • Curriculum learning: Prior curriculum-learning results suggest that the levels most useful for improving a policy change over the course of training.The paper therefore considers automatically discovering a curriculum rather than fixing level difficulty in advance.

3. Prioritized Level Replay

Prioritized Level Replay (PLR) selectively samples training levels according to estimated future learning potential, while using staleness to keep replay scores current. Its scoring and prioritization mechanisms integrate into policy-gradient training and can induce a curriculum in sparse-reward settings.

  • Prioritized Level Replay: PLR replaces uniform level selection with replay decisions that prioritize visited levels estimated to offer greater future learning potential.It is designed as a drop-in replacement for experience collection in a broad range of RL algorithms.
  • Replay Distribution: PLR maintains a dynamic replay distribution over visited levels by combining score-based prioritization with a staleness-based distribution.The score-based component reflects trajectory properties, while the staleness component tracks how long each level has gone without resampling.
  • Experience Collection: PLR alternates between unseen-level sampling and replay, with replay becoming more frequent as the proportion of visited training levels increases.For finite training sets, unseen levels are sampled uniformly from the remaining levels, and the replay decision is naturally annealed with coverage.
  • Scoring Levels for Learning Potential: After each episode, PLR scores the sampled level from trajectory TD-errors, using average absolute GAE as its default learning-potential measure.The absolute value treats large positive and negative errors as equally informative; the default instantiation is equivalent to an L1 value loss.
  • Prioritization Function: Rank prioritization maps score differences to sampling probabilities through h(S_i)=1/rank(S_i), while proportional and greedy alternatives tend to perform worse.The temperature parameter β controls how strongly prioritization affects the resulting distribution.
  • Staleness-Aware Prioritization: The staleness component assigns more probability to levels whose scores are older, limiting policy drift in score estimates and ensuring stale levels regain support.A level becomes more likely to be sampled when its score is high or it has not been sampled for a long time.

4. Experimental Setting

The experiments evaluate PLR across Procgen and MiniGrid using PPO-based training, unseen-level test returns, normalized returns, and generalization gaps. The study also examines combinations of scoring and prioritization schemes and extends PLR to unbounded level distributions.

  • Procgen Evaluation: PLR is evaluated against uniform training-level sampling across all 16 Procgen Benchmark environments on easy and hard difficulties.The comparison also includes UCB-DrAC and mixreg on the easy setting.
  • Metrics: Evaluation tracks episodic test returns, final performance on 100 unseen levels per game, mean normalized test return, and mean generalization gap.The generalization gap is train return minus test return, so a larger gap indicates more overfitting.
  • Training Setup: All experiments use PPO with GAE; Procgen uses the original baseline setup of 200 easy training levels and 25M total steps.MiniGrid uses a three-layer CNN and approximately 1000 training levels per difficulty and environment.
  • Unbounded Level Sets: An extended PLR variant supports unbounded level sets by retaining a finite rolling buffer containing the highest-learning-potential levels encountered so far.Results for this extension are reported for the full level distribution of the main MiniGrid environments.

5. Results and Discussion

PLR improves sample efficiency and generalization across Procgen and MiniGrid, with its strongest gains arising from staleness-aware level prioritization and an emergent curriculum toward harder levels.

  • Procgen Benchmark: PLR attains the highest normalized mean test and train returns and the largest reduction in Procgen generalization gap among individual methods.The method matches UCB-DrAC in test improvement relative to PPO.
  • Procgen Benchmark: 76% improvement in mean test return relative to PPO with uniform sampling, and 28% relative to UCB-DrAC, is achieved by UCB-DrAC + PLR.PLR with rank prioritization improves test return on 10 of 16 environments; proportional prioritization improves 11 of 16.
  • Procgen Benchmark: PLR gains occur when replay sampling combines level scores with staleness, with 0 < ρ < 1 preventing scores from drifting off-policy.The result highlights staleness-based sampling as important to effective prioritization.
  • Scoring Functions: Alternative TD-error and classifier-uncertainty scoring functions improve some games but produce no improvement or degraded performance on others.The inconsistent pattern contrasts with the stronger aggregate performance of the preferred L1 value-loss scoring function.
  • MiniGrid: PLR significantly improves sample efficiency and generalization on two challenging MiniGrid environments, with ρ = 0.3 yielding the best test performance.These results support the Value Correction Hypothesis in discrete state spaces.
  • Emergent Curriculum: PLR progressively shifts sampling probability toward harder levels, although discovering a useful curriculum can initially take about 4,000 updates.The curriculum can let 6,000 training levels outperform uniform sampling using roughly 4 billion available levels.
  • Emergent Curriculum: An extended PLR variant using a buffer of levels with the highest estimated learning potential outperforms uniform sampling over the full level distribution.This result is reported for the two MiniGrid environments.

6. Related Work

PLR differs from prior generalization and curriculum approaches by changing only level sampling and replaying visited levels, while remaining compatible with other methods.

  • Generalization Methods: Prior generalization methods modify model architecture, learning algorithms, observations, or environment structure, whereas PLR changes only the next-level sampling rule.This design makes PLR straightforward to combine with any model or RL algorithm.
  • Selective Sampling: PLR resembles active learning and task-selection methods that use progress signals, but it does not require a known maximum target return for each task.Its sampling signal is based on estimated learning potential for revisiting levels.
  • Adaptive Generation: Unlike adaptive level-generation methods, PLR requires no control over generation or additional modules because it replays previously visited levels.The method assumes only the ability to revisit levels.
  • Prioritized Replay: PLR uses TD-errors to prioritize revisiting levels for new experience collection, rather than prioritizing previously collected experiences directly.This makes PLR a forward-view, online counterpart to prioritized experience replay.
  • Exploration: Exploration strategies are complementary to PLR, but their transfer from low-dimensional PCG settings to complex Procgen environments remains unresolved.The authors identify combining such methods with PLR as a future research direction.

7. Conclusion and Future Work

The paper concludes that PLR improves generalization and sample efficiency across procedural environments while offering practical extensions and clear deployment boundaries.

  • Conclusion: PLR improves sample efficiency and generalization across most Procgen environments and two challenging MiniGrid environments, while combining with UCB-DrAC to set a new Procgen state of the art.On MiniGrid, PLR also induces an emergent curriculum of increasingly difficult levels.
  • Applications and Extensions: PLR may extend to robotic manipulation and singleton environments when domain-randomized variations can be indexed as levels.The paper also identifies goal-conditioned PLR as a natural extension by incorporating goals into level parameterization.
  • Limitations: PLR is constrained when real-world problems cannot be faithfully represented by seed-based simulation or lack explicit environment resets.Car driving and continual learning are cited as examples of these boundaries.
  • Applications and Extensions: Simulation pre-training may still help such settings because real-world interaction can be slow, expensive, and precarious.The authors suggest adapting PLR to improve learning in these settings.
  • Future Work: The L1 value loss is effective as a scoring function, but directly learning scoring functions may produce stronger alternatives.Combining PLR with exploration strategies is another stated future direction.

A.1. Procgen Benchmark

Procgen and MiniGrid provide procedurally generated levels for testing generalization, with MiniGrid offering ordered difficulty settings. The experiments evaluate PLR and comparison methods under standard training and testing protocols.

  • Procgen Benchmark: Procgen contains 16 environments whose seeded levels vary in layout, appearance, and entity positions, while test levels are sampled from the full distribution.Agents train on a finite set of levels and are evaluated on unseen levels.
  • Procgen Benchmark: The standard Procgen protocol trains on Ntrain finite levels and computes normalized test returns using game-specific minimum and maximum returns.The normalization is (R − Rmin)/(Rmax − Rmin).
  • Procgen Benchmark: Hyperparameters are primarily swept on Procgen easy, using Ntrain = 200 and 25M training steps for comparability with prior work.The experiments share a ResNet policy architecture and PPO hyperparameters across games.
  • Procgen Benchmark: Procgen hard trains on 500 levels for 200M steps, but the reported baselines are not directly comparable to prior hard-setting results because of reduced batch sizes.The implementation uses 128 environments in one actor instead of quadrupling GPU actors.
  • MiniGrid: MiniGrid levels have ordered difficulty, with harder tasks requiring longer action sequences over richer entities and larger grids.The experiments use full-grid observations and evaluate generalization across seeded levels.
  • MiniGrid: MultiRoom-N4-Random requires navigating through one to four rooms, whereas ObstructedMazeGamut-Easy adds key retrieval, hidden keys, and blocked doors across three difficulty levels.The figures illustrate increasing difficulty from left to right.

B.1. Extended Results on Procgen Benchmark

Extended Procgen experiments show that PLR’s benefits depend on combining level scores with staleness and extend to the hard setting. When PLR improves generalization, it generally also preserves or improves training efficiency.

  • Ablations and prioritization: PLR gains over uniform sampling require both level scores and staleness; using only staleness or only L1 value-loss scores is considerably worse.Rank prioritization yields slightly larger mean improvements on several games, while proportional prioritization adds a significant gain on CoinRun.
  • Sample efficiency: When PLR improves generalization, it also matches or improves training sample efficiency, whereas two games show reduced efficiency without generalization gains.The authors suggest uniform sampling may better support memorization on those games.
  • Procgen hard: On Procgen hard, PLR and UCB-DrAC + PLR significantly outperform the comparison methods in normalized train and test return and reduce the mean generalization gap.The hard-setting evaluation uses five runs per environment and 200M training steps.
  • Robustness across runs: Figure 8 provides two additional independent training runs supporting the consistency of PLR’s emergent curriculum.The figure is presented as evidence across runs rather than a single training trajectory.

B.2. Extended Results on Minigrid

Additional MiniGrid runs show that PLR consistently shifts its sampling distribution from easier to harder levels during training, forming an emergent curriculum.

  • Emergent curriculum: Across additional runs, Preplay gradually shifts probability mass from easier to harder difficulty bins over training.This supports consistency of the emergent curriculum beyond the original run.

B.3. Training on the Full Level Distribution

With access to the full level distribution, PLR maintains a finite buffer of levels with the highest estimated learning potential and improves performance over uniform sampling in both evaluated environments.

  • Full level distribution: PLR tracks the top M levels by learning potential in a finite buffer when the available training level distribution is unbounded.The buffer uses modified score and timestamp lists.
  • Buffer replacement: A newly sampled level replaces the current minimum only when its learning-potential score is higher, preserving the buffer’s highest-scored levels.The replacement rule is applied when the Bernoulli decision samples a new level.
  • Results: PLR improves sample efficiency and generalization over uniform sampling with access to the full level distribution in both MultiRoom-N4-Random and ObstructedMazeGamut-Easy.In MultiRoom, full-distribution PLR outperforms PLR trained on a fixed level set.
  • Buffer-size sensitivity: The buffer size M has little effect in MultiRoom, while smaller M worsens ObstructedMazeGamut-Easy test performance; most tested settings still outperform uniform sampling.The exception is M = 500 in ObstructedMazeGamut-Easy.

C. Algorithms

PLR extends policy-gradient training by selecting unseen or replayed levels through prioritized sampling, updating level scores and staleness during T-step rollout collection. On Procgen, PLR-based methods outperform uniform sampling in train and test returns and significantly reduce generalization gaps.

  • Rollout collection: During T-step rollout collection, PLR records transitions, tracks partial time-averaged scores, and updates a level’s score when an episode ends.The procedure also handles rollouts that begin or end between episode boundaries by maintaining partial scores and trajectory buffers.
  • Benchmark results: PLR-based methods statistically significantly outperform all others in Procgen hard-setting train and test returns and are the only methods that significantly reduce the generalization gap.The reported curves average results across all environments over 5 runs, with shaded one-standard-deviation regions.
  • Benchmark results: On Procgen easy, PLR-based methods consistently match or outperform uniform sampling across games, while TSCL produces inconsistent outcomes, including drastically lower StarPilot test returns.PLR significantly reduces the generalization gap on 7 games by itself; the supplied passage also reports 10 of 16 games when combined with UCB-DrAC.
  • Prioritization design: The replay distribution must combine value-loss scores with staleness to improve generalization and sample efficiency under both rank and proportional prioritization.The figures vary the staleness coefficient ρ while holding β = 0.1, and show that PLR can improve training efficiency as well as generalization on some games.
  • Training loop: The generic training loop initializes level scores, partial scores, timestamps, visited levels, and an experience buffer before collecting rollouts and applying policy updates.Each update collects T-step experiences across parallel environments and passes the resulting buffer to the policy-update function.
  • Level selection: PLR alternates between sampling unseen training levels and replaying visited levels according to score-based and staleness-based distributions.Replay uses a mixture of (1 − ρ)·P_S and ρ·P_C, while unseen levels are sampled when available.
Loading 2010.03934v4…