Prioritized Level Replay
Authors: Minqi Jiang
Edward Grefenstette
Tim Rocktäschel
Venue:  (2021)
Keywords: Reinforcement Learning
Procedurally Generated Environments
Curriculum Learning
Procgen Benchmark

Abstract: Simulated environments with procedurally generated content have become popular benchmarks for testing systematic generalization of reinforcement learning agents. Every level in such an environment is algorithmically created, thereby exhibiting a unique configuration of underlying factors of variation, such as layout, positions of entities, asset appearances, or even the rules governing environment transitions. Fixed sets of training levels can be determined to aid comparison and reproducibility, and test levels can be held out to evaluate the generalization and robustness of agents. While prior work samples training levels in a direct way (e.g.~uniformly) for the agent to learn from, we investigate the hypothesis that different levels provide different learning progress for an agent at specific times during training. We introduce Prioritized Level Replay, a general framework for estimating the future learning potential of a level given the current state of the agent's policy. We find that temporal-difference (TD) errors, while previously used to selectively sample past transitions, also prove effective for scoring a level's future learning potential when the agent replays (that is, revisits) that level to generate entirely new episodes of experiences from it. We report significantly improved sample-efficiency and generalization on the majority of Procgen Benchmark environments as well as two challenging MiniGrid environments. Lastly, we present a qualitative analysis showing that Prioritized Level Replay induces an implicit curriculum, taking the agent gradually from easier to harder levels.

Under review as a conference paper at ICLR 2021
PRIORITIZED LEVEL REPLAY
Anonymous authors Paper under double-blind review
ABSTRACT
Simulated environments with procedurally generated content have become pop- ular benchmarks for testing systematic generalization of reinforcement learning agents. Every level in such environment is algorithmically created, thereby ex- hibiting a unique configuration of underlying factors of variation, such as layout, positions of entities, asset appearances, or even the rules governing environment transitions. Fixed sets of training levels can be determined to aid comparison and reprodueibility, and test levels can be held out to evaluate the generalization and robustness of agents. While prior work samples training levels in a direct way (e.g, uniformly) for the agent to learn from, we investigate the hypothesis that dif- ferent levels provide different learning progress for an agent at specific times dur- ing training. We introduce Prioritized Level Replay, a general framework for esti- mating the future learning potential of level given the current state of the agent's s policy. We find that lemporal-difference (TD) errors, while previously used to se- lectively sample past transitions, also prove effective for scoring level's future learning potential when the agent replays (that is, revisits) that level to generate entirely new episodes of experiences from it. We report significantly improved cample-effiiieng and generalization on the majority of Procgen Benchmark envi- ronments as well as two challenging MiniGrid environments. Lastly, we present a qualitative analysis showing that Prioritized Level Replay induces an implicit curriculum, taking the agent gradually from easier to harder levels.
INTRODUCTION
Environments generated using procedural content generation (PCG) have garnered increasing inter- est in RL research, leading to a surge of PCG environments such as MiniGrid Shhevalier-Boisver et al., 2018) 8), the Obstacle Tower Challenge (Juliani et al., 2019), the Procgen Benchmark (Cobbe et al., 2019), and the NetHack Learning Environment (Küttler et al., 2020). Unlike singleton envi- ronments, like those in the Arcade Learning Environment benchmark (Bellemare et al., 2013), which are exploitable by memorization and deterministic reset strategies (Ecoffet et al., 2019; 2020). PCG environments create novel environment instances levels algorithmically. Every such level exhibits a unique configuration of underlying factors of variation, such as layout, positions of game entities, asset appearances, or even different rules governing environment transitions, making them a promis- ing target for evaluating systematic generalization in RL (Risi & Togelius, 2020). Each level can be associated with a level identifier (c.g. an index, random number generator seed, etc.) used by the PCG algorithm to generate specific level. This allows for a clean notion of train-test split and testing on held-out levels, in line with the best practices from supervised learning.
Due to the variation among algorithmically generated levels, random selection of PCG levels can, in principle, correspond levels of varying difficulty as well as reveal different- perhaps vare-environment dynamics This diversity among levels implies that different levels hold differing learning potential for an agent at any point training, a fact exploited by methods that both learn to generate levels well as to solve them (Wang et al., 2019; 2020). Here, focus on the less intrusive setting where we do not have control over level generation, but can instead replay (that is, revisit) any previously visited level during training generate entirely new experiences from it.
We introduce Prioritized Level Replay, illustrated in Figure 1, a method for sampling training levels that exploits this difference among levels. Our method induces level-sampling distribution that prioritizes levels based on the learning potential of replaying each level anew. Throughout agent training, method updates heuristic score appraising the agent's learning potential on level

---

Under review as a conference paper at ICLR 2021
Poew
Equivolent
direct level saxpling 1T Prow Pants
Ansi
Ageen
d PD
update
updote to
scorefz, m)
Train
P Preplay
T
Figure I: Overview of Prioritized Level Replay. The next level is either sampled from a distribution with support unseen levels (top), which could be the environment's (perhaps implicit) full training-level distribution, or alternatively, sampled from the replay distribution, which prioritizes levels based on future learning potential (bottom). In either case, trajectory T is sampled from the next level and used to update the replay distribution. This update depends on the lists of previously seen levels Agens their latest estimated learning potentials S, and last sampled timestamps C.
based on cemporal-differenc (TD) errors collected along the last trajectory sampled from that level. Rather than sampling from the default, typically static (e.g. uniform), training level distribution, our method samples from distribution derived from a normalization procedure over these level scores. Prioritized Level Replay does not make any assumption about how the policy is updated, and is therefore compatible with any RL method. Furthermore, our method does not rely some external or general method for quantifying difficulty of a level, but instead derives a level score directly from the policy. The only requirements- satisfied in wide number of settings where simulator game is used to collect experience- are as follows: sampled from the environment in an identifiable way, and (iii) given level identifier, it is possible to set the environment to that level to be able to collect new experiences from it.
(i) some notion of "level" exists, (ii) such levels can be
While previous works in off off-policy RL devised effective methods directly reuse past experiences for training (Schaul et al., 2015; Andrychowicz et al., 2017), Prioritized Level Replay uses past experiences to inform the collection of future experiences by assessing how much replaying each level anew will benefit learning. Our method can thus be seen forward-view variation of pri- oritized experience replay, and an online counterpart to this off-policy method for policy-gradient algorithms.
This paper makes the following core contributions: (i) we introduce a computationally efficient algorithm for adaptively prioritizing levels throughout training using heuristic-based assessment of the learning potential of replaying each level, (ii) we empirically demonstrate our method leads to significant gains 11 of 16 Procgen Benchmark environments and two challenging MiniGrid environments, (iii) we demonstrate our method combines with a previous leading method to set a new state-of-the-ane Procgen Benchmark, and (iv) provide evidence that our method induces an implicit curriculum over training levels in sparse reward settings.
BACKGROUND
In this paper, we refer to PCG environment as any computational process that, given level iden- tifier (e.g. an index or seed), generates a level, defined as an environment instance exhibiting unique configuration of its underlying factors of variation, such as layout, positions of game en- tities, asset appearances, even rules that govern the environment transitions (Risi & Togelius, 2020). For example, MiniGrid's MultiRoom environment instantiates mazes with varying numbers of rooms based on the seed "Chevalier-Boisvii et al., 2018). We refer to sampling generated from the agent's latest policy acting on a given level [ as replaying that level
trajectory
The level diversity of PCG environments makes them useful testbeds for studying the robustness and generalization ability RL agents, measured by agent performance on unseen test levels. The standard test evaluation protocol for PCG environments consists of training the agent number training levels, Amai and evaluating performance on unseen test levels Aget- drawn from the set of all levels. A common variation of this protocol sets Amain the set of all levels, though the
finite
2

---

Under review as a conference paper at ICLR 2021
agent will still effectively only sees finite set of levels during training. Training levels are sampled from an arbitrary distribution Pram (4) Alann). We call this training process direct level sampling. In practice, for the case of a finite training set, typically (anin (4rrii) = Uniform((. Aminn. See Appendix D for the pseudocode outlining this procedure.
In generating levels of varying difficulty, PCG environments naturally lend themselves the study of curriculum-baat training protocols. For example, Justesen et al. (2018) and Wang et al. (2019; 2020) show that generating progressively harder levels improves generalization of agents across difficulty settings, demonstrating that the set of levels most useful for improving an agent's 's perfor- mance varies throughout the course of training. When levels cannot directly be generated, many previous works have exploited handcrafted curricula to learn policies on harder levels (Chevalier- Boisvert et al., 2018; Zhong et al., 2020). Instead, we are interested in answering how an effective curriculum over an existing set Auain can be automatically discovered.
3 PRIORITIZED LEVEL REPLAY
In this section, we present Prioritized Level Replay, a level-sampling algorithm that exploits differ- ences in the learning potential for the current agent in replaying previously visited levels. It is a drop-in replacement for the experience-collectinn To exemplify this, we show how it is straight-forwan to incorporate Prioritized Level Replay into generic policy-gradient training loop, as described in Algorithm I where, for clarity, we focus on training on batches of complete trajectories (see Appendix D for detailed pseudocode on how our procedure works with Ttstep rollouts).
process used in a wide range of RL algorithms.
Our method, illustrated in Figure 1 and fully specified in Algorithm 2, induces a dynamic and non- parametric sampling distribution Preplay (d]A over previously visited training levels Agen that prioritizes visited levels with higher learning potential based on properties of the agent's 's past tra- jectories. We refer Preplay (1 Ageen) the replay distribution. Throughout an agent's 's training, our method updates this replay distribution adaptively according to a heuristic score, assigning greater weight to visited levels with higher future learning potential. Through variable-size lists S and C of equal length to Asean Prioritized Level Replay tracks level scores S: E S for each visited training level based on the latest episode trajectory on 4, as well as the episode count C. C' which each level 4 E Aseen was last sampled. Our method updates Peeplay after each terminated episode by computing a mixture of two distributions, Ps, based on the level scores, and Pc, based on how long ago each level was last sampled:
Preplay = p)- Ps + P.P.P Pc.
where the staleness coefficient م [0. is a hyperparameter. We discuss how compute level scores (5,) parameterizing the scoring (P's distribution, and the staleness (Pc) distribution, in Sec- tions 3.1 and 3.2, respectively.
Prioritized Level Replay chooses the next level at the start of every training episode by first sampling replay-decisiog from Bernoulli (or similar) distribution Pp (d) to determine whether to replay level sampled from the replay distribution Preplay([AAuee) or to experience a new, unseen level from Arain. according to some distribution Pnew (2) Ar)Ano (Aseen). ). In practice, for the case of a finite number of training levels, we implement Pnew as a uniform distribution over the remaining unseen levels. For the case of a countably infinite number of training levels, we simulate Paew by sampling levels from Pirain until encountering an unseen level. In our experiments based on finite number of training levels, we opt to perform a "warm start" by setting PD 0) (i.e. sampling a new level) as long as |Arain Aseen| > 0 (i.e. not every level has been seen), ensuring the replay distribution takes into account scores from at least one trajectory from each level.
The following sections describe the main steps of how Prioritized Level Replay updates the replay distribution Preplay (1) (een, namely level scoring and staleness-aware prioritization.
3.1 SCORING LEVELS FOR LEARNING POTENTIAL
After collecting each full trajectory over completed episode on level 4, using policy n, our method assigns I; a score S, = score(r, π) measuring the learning potential of replaying 4 in the future. We employ a function of the TD-error timestep I, 5, rtt + (V V(s)), proxy
3

---

Under review as a conference paper at ICLR 2021
Algorithm Generic policy-gratne gradient training loop with Prioritized Level Replay
Input: Training levels Amia environment policy ne, policy update function L4(5, 0) + 8", and batch size
No.
Initialize level scores S and level timestamps C, global episode counter c <- 0
Initialize the ordered set of visited levels Agenn Ø Initialize experience buffer B while training do
B + Ø
while collecting experiences do B B U collect collect_experiences( Agen; No, S,
D Using Algorithm 2
end while
()
> Update policy using collected experiences
end while
Algorithm Experience collection with Prioritized Level Replay
Input:
Training levels Auain visited levels A Awen- policy ग,, the training level distribution Puain: global level scores S, global level timestamps C, and global episode counter
Output: A sampled trajectory?
e <- c++
Sample replay decision d ~ (d(
if = 0 and |Anain \. Asecal > 0 then
Sample an unseen level, if any
Define new index 4- +
Sample l ~ Przw (1) Amnin Alsca)
Add I to Asees add initial value to
else
b Sample level for replay
Sample 1; - p) (1 Ayems S) p- Po(1 Aveens C,
end
Sample (T(() Update score S; t score(r, T) and timestamp C. +
D Update level replay lists
for this learning potential. Its expectation over next states is equivalent to the advantage estimate, and therefore gigher-magnitue TD-errors imply greater discrepancy between expected and actual returns, making useful measure of the learning potential in revisiting particular state transition. To prioritize the learning potential of future experiences resulting from replaying level, we use a scoring function based on the average magnitude of the Generalized Advantage Estimate (GAE; Schulman et al., 2015) over each of T time steps in the latest trajectory from that level:
T
T
5; = score (T
(GA) Σ
1=0
kmt
Importantly, while the GAE at time is most commonly expressed as the discounted sum of all 1-step TD-errors starting at in Equation 2, it is equivalent of all k-step TD-errors from f, with discount factor X. By considering ke-seep TD-errors, the GAE mitigates the bias introduced by the bootstrap term in 1-step TD-errors. The discount factor À then controls the trade-off between bias and variance. Our scoring function considers the absolute value of the GAE, as we assume the degree of learning potential grows with the magnitude of the TD-error irrespective of its sign.
apponentially-diccounte
sum
Another useful interpretation of Equation 2 comes from observing that the GAE is equivalent the L1 value loss VV Vel when applied the context
policy-gradien algorithm that uses GAE for its own advantage estimates- and therefore value targets V.-as done in state-of-the-ar implementations of PPO (Schulman et al., 2017) used in our experiments. For this reason, will refer to this instantiation of our algorithm as value-based level replay.
While we provide principled motivations for our specific choice of scoring function, emphasize that general, the scoring function can be any approximation learning potential based on per- trajectory values. In Section 4, will compare choice of the unsigned GAE, equivalently,
4

---

Under review as a conference paper at ICLR 2021
the L1 value loss, alternative DD-error-basee and uncertainty- scoring approaches listed in Table
Given level scores, the normalized outputs of a prioritization function h evaluated over these scores and tuned using a temperature parameter 3 defines the coree-proritized distribution Ps (Aurain) over the training levels, under which
1(5.)
Ps(4 A sgen: 5) Σ, h(S))
The function h defines how differences in level scores translate into differences in prioritization. The temperature parameter allows us to tune how much h(S) ultimately determines the resulting distribution. We make the design choice of using rank prioritization, for which k(S)) = 1//rankS:)) where ran the rank of level score S, among all scores sorted descending order. We also experimented with proportional prioritization (h(S,) = Sj). which performs comparably rank prioritization, as well as greedy prioritization (the level with the highest score receives probability 1), which tends to perform worse.
3.2
STALENESS-AWARY PRIORITIZATION
As the scores used to parameterize Ps are a function of the state of the policy at the time the associated level was last played, they come to reflcc a gradually more off off-policy measure the longer they remain without an update through replay. We mitigate this drift towards "off-policy-ness" by explicitly mixing the sampling distribution with staleness staleness-prioritzeed prioritiied distribution Pc
C-C, Po(4/Aseem: C,C)= Ec,ec
(4)
which assigns probability mass each level i, in proportion to the level's staleness C.. Here, is the count of total episodes sampled so far in training and C; (referred to as the level's timestamp) the episode count which was last sampled. By pushing support levels with staler scores, Po ensures no score drifts too far off-policy.
Plugging Equations and 4 into Equation 1 gives replay distribution that is calculated as
P Prepla (4) (1 p) Ps(4 Aween 3) p Po C,c).
Thus, level has an increased chance of being sampled when its score is high or it has not been sampled for long time.
EXPERIMENTAL SETTING
We evaluate the effectiveness of Prioritized Level Replay several PCG environments with various implementations of scoring functions and prioritization schemes, and compare against the most com- mon direct level sampling baseline for which (l Uniform(1 Again) Specifically, train and test on all 16 games in the Procgen Benchmark on the easy difficulty setting (Cobbe et al., 2019) and select hard exploration environments from the MiniGrid suite Chhealier-Booivee 2018). In addition, we demonstrate that our method, when combined with UCB-DrAC (Raileanu al., 2020), sets new state-of-the-ar on Procgen Benchmark. In line with the standard baseline for these environments, all our experiments use PPO with GAE for training. For Proegen Bench- mark we use the same ResBlock architecture as Cobbe et al. (2019) and the 200 training levels used in the original baselines, while sampling unseen levels for every test run. For MiniGrid, we use 3-layer CNN architecture similar to that in Igl et al. (2019), and provide approximately 1000 levels of each difficulty for every environment during training. Detailed descriptions of the environ- ments, architectures, and hyperparameters used in our experiments (as well as how they were set or obtained) can be found in Appendices A and B. See Table for the full set of scoring functions score(r, т) investigated in our experiments. Additionally, we report results of training on the full level distribution of select MiniGrid levels in Appendix C.2.
al.,
5

---

Under review as a conference paper at ICLR 2021
Table Choices of scoring function score(r, TT) investigated in this work.
Scoring metric
score( π)
Policy entropy
T E 1=0 Eo aa, 8t) log (a,
Policy min-margin
T >
t=o (maxa Ta, 8t) maXastmax, m(a,s)) (a, st))
Policy least-confidence
T 2
max, < sa)
Unsigned 1-step TD error
1 E +E
16p1
T 1=0
GAE
1 T
55
1=0
Unsigned GAE (Ll value loss)
(TA)t
Random
p- 1.0
value loss, rank, p
UCB-DrAC PLR
bigfish
bossfight
caveflyer
chaser
climber **
coinrun
dodgeball
fruiboot *
test episode
heist
jumper
leaper
maze
miner
ninja **
plunder
starpilot
Steps
Figure 2: Mean episodic test returns (10 runs) while training under value-based level replay with rank prioritization, both with and without UCB-AutoDrAC, compared to baseline sampling meth- ods. Each colored * indicates statistically significant (p = 0.05) gains in final test performance or sample complexity along the curve, relative to uniform sampling for the condition of the same color.
RESULTS AND DISCUSSION
Prioritized Level Replay consistently provides better (or at least on-par) results than direct level sam- pling. particular, we find that: (i) value-based level replay consistently outperforms direct level sampling in generalization and sample-efficiency across environments, (ii) alternative scoring func- tions lead to inconsistent improvements across environments, (iii) our method can yield significant additive gains combined with other methods, and (iv) value-based level replay induces implicit curriculum over training levels, which substantially aids training in hard exploration environments.
5.1 PROCGEN BENCHMARK
Our results in Figure show that value-based level replay combined with rank prioritization, with = 0.1 and = 0.1, leads to the most drastic improvements across games. This setting yields sta- tistically significant (p 0.05) improvements in generalization performance over unimonn-sampling on 10 out of 16 environments, according to Welch's 's t-test. In comparison, value-based level replay with proportional prioritization provides statistically significant gains over uniform sampling on one more game, but average worse mean test returns. Notably, gains only occur when the replay distribution considers both level scores and staleness, highlighting the importance of salleness-basee sampling in keeping scores from drifting off- off-policy. Further, report considerable improvements over uniform evee--ampling on the hard setting, when directly using the best hyperparameters found for the easy setting. Figures 8, 9, 11 and Table in Appendix C report these additional results.

---

Under review as a conference paper at ICLR 2021
biglish
ninja
Mean test episode retum
unioom
confidence
min mergin
pollcy
10.0
GAE
7.5
1-stop TD emeer
10M
Steps
Figure 3: Two example Procgen games, between which all scoring functions except for L1 value loss show inconsistent improvements to generalization and sample efficiency, with rank prioritization = 0.1, and p 0.3. This inconsistency held across settings in our grid search.
The remaining scoring metrics based on TD-error and classifier uncertainty perform inconsistently across games. While certain games such as BigFish seem amenable to improvements in both training sample complexity and generalization under various Prioritized Level Replay scoring metrics, other games, such as Ninja, see no improvement or even degraded sample complexity and generalization. See Figure 3 for an example of this inconsistent effect across games.
We conjecture that sampling levels with Prioritized Level Replay under value- basue replay induces an implicit curriculum over the training levels. Easier levels result in non-zero, non-stationary re- turns earlier in training, while harder levels give rise to near stationary returns until the agent learns an improved policy that allows making further progress on the level. Therefore, meaningful non- stationary value regression targets appear earlier in easier levels than in harder levels, leading to higher value losses on easier levels than on harder levels, where the agent can not yet make progress. Sampling levels according to the L1 value-loss then leads to implicit curriculum from easier to harder levels. In the next section, we test this conjecture in hard exploration environments in Mini- Grid, whose levels are clearly separated into discrete, qualitatively different difficulties.
Prioritized Level Replay easily combines with most other methods, as simply defines a process for adapting the training level-sampling distribution function of the agent's past trajectories and policy instantiations during those trajectories. To demonstrate this fact, we combine our method with UCB-DrAC (Raileanu al., 2020). At the time of writing, UCB-DrAC had attained state- of-the-art results on the Procgen Benchmark. Our combined setup trains agents using UCB-DrAC while sampling training levels at the start of each episode according to value-based level replay. As summarized in Table 2. MCB-DrAC combined with our method sets a new state-of satte-of-the-arr tet-hheart art on the Procgen Benchmark. Figure showcases the test performance throughout training of this combined approach. The full details of this experiment are provided in Appendix C.3.
5.2 MINIGRID
As in the case of the Procgen Benchmark, find that value-based level replay with rank prioriti- zation significantly improves the sample efficiency and generalization performance in both environ- ments. On these MiniGrid environments, we find slightly higher staleness coefficient of p 0.3 leads to better test performance. The results are summarized in the top row of Figure 4.
For evaluation purposes, we bin each level into its corresponding difficulty, expressed ascending. discrete values (note that Prioritized Level Replay does not have access to this privileged informa- tion). From Figure 4 we see how the expected difficulty of levels sampled using value-based level replay changes throughout training for each environment. We observe that as level weights are up- dated based on the agent's past experiences of each level, these levels become sampled according to implicit curriculum over the training levels that prioritizes progressively harder levels. No- tably, value-based level replay struggles to discover a useful curriculum for around the first 4,000 updates on ObstruueedMMaeGGamutMMeeeee
at which point it discovers a curriculum that gradually assigns more weight to harder levels. This curriculum appears quite effective, enabling aalue-based level replay with access to only 6,000 training levels to attain even higher mean test returns than the uniform-se sarioommmmmmmminggg baseline with access to the full set of training levels, of which there are roughly billion by our estimate (so training levels constitute 0.00015% 5% of the total number).

---

Under review as a conference paper at ICLR 2021
Table 2: Comparison of test performance of policies trained each method. Here PLR denotes value-based level replay with rank prioritization with = 0.1 and p 0.1. Following the evaluation protocol in Raileanu et al. (2020), the reported mean and standard deviation per environment is computed by evaluating the final policy's average return on 100 test episodes, aggregated across multiple training runs (10 runs for Proegen Benchmark and for MiniGrid). Each is initialized with a different training seed. Normalized test returns per run are computed by dividing the average test return per run for each environment by the corresponding average test return of the uniform- sampling baseline over all runs. We then report the means and standard deviations of normalized test returns aggregated across runs. Note, we report the normalized return statistics for Procgen and MiniGrid environments separately.
Environment
Uniform
UCB-DrAC
PLR UCB-DrAC+PLR
BigFish
3.72 + 1.24
8.73 173:1.13
10.91 2.81
14.28 + 2.12
BossFight
7.7 0.37
0.67
8.94 0.35
8.84 + 0.8
CaveFlyer
5.37 + 0.79
6.32 4.93
6.76 0.7
Chaser
5.29
0.99
6.9 1.21
8.01
Climber
0.6
0.99
6.33
6.8 : 6.8
CoinRun
8.62
0.42
3.76=0.47
8.95 199+0.3 0.37
Dodgeball
1.69 +.23
1.11
1.78
10.33 + 1.36
FruitBot
27.29
1 1.35
2
Heist
2.99
3.17
2.93
4.93 + 1.3
Jumper
0.41
5.41
5.83 + 0.48
5.86
Leaper
4.18
4.42
6.83 1.15
0.98
Maze
0.37
6.21
5.49
7.23 + 0.82
Miner
0.72
10.09 0.6
9.56 0.62
10.03
Ninja
0.44
5.83
+.24
6.96
Plunder
0.55
0.89
8.68 + 2.18
7
StarPilot
26.84 1.54
31.68
+ 2.36
27.9 4.35
29.64 + 2.22
Normalized Returns (%)
100.0 + 4.5
129.8 + 8.2
128.3 + 5.8
176.4 + 6.1
MultiRoom-N4-Random
0.80 + 0.04
0.81 + 0.01
ObstructedMazzaammu-Eayy
0.53 + 0.04
0.85 + 0.04
ObstructedMazeGamut-ccee
0.65 + 0.01
0.73 + 0.07
Normalized Returns (%)
100.0 + 2.5
124.3 + 4.7
MulBRooo-NM-Rardde
ObstuciedMaaaaGmmllaaaa
Mean test splaode return
uniform
value loss, p 0.3 unioom, full cistribution
0.0
0.4
0.2
60M
30M
100M
00M
100M
150M
200M
250M
Steps
1.00
3
5
Probabilty
0.50
1
0.00
4K
10K
15K
PPO updates
Figure 4: Top: Mean episodic test returns of value-based level replay and the uniform- sampling baseline on CaltiRoom-N4-Randdee (4 runs), ObstruetedMazeGGamutt Easy (3 runs), and ObstructedMazeGammut Mediuum (3 runs). Bottom: The probability mass assigned to levels of vary- ing difficulty over the course of training the respective environment for a single run.
8

---

Under review as a conference paper at ICLR 2021
6 RELATED WORK
Prior work for improving generalization in deep RL adapt techniques from supervised learning, in- cluding stochastic regularization (Igl al., 2019; Cobbe al., 2019), data augmentation (Kostrikov et al., 2020; Raileanu et al., 2020), and knowledge distillation (Igl et al., 2020; Cobbe et al., 2020). In contrast, Prioritized Level Replay requires no modifications to the model architecture or training algorithm-it only modifies the order in which rollouts are sampled from a collection of training lev- els. Our method is compatible with any model or volicy-gradien algorithm, and can be implemented alongside these approaches for potentially orthogonal gains.
Prioritized Level Replay is related to active learning (Cohn et al., 1994; Settles, 2009) and echoes ideas from Graves et al. (2017), which uses gradient-based progress signals for training adver- sarial multi-armed bandit that selectively samples the next task in multi-task supervised learning. Sharma et al. (2018) extend these ideas to multi-task RL, but add the additional requirement of knowing a maximum target return for each task priori. More recently, Zhang et al. (2020) use an ensemble of value functions for selective goal sampling in the off-policy continuous control set- ting, requiring prior knowledge of the environment structure to generate candidate goals. Notably, tasks, an
these methods depend on the ability sample instances of specific assumption that breaks in the PCG setting. Rather, we show that our method automatically uncovers similarly difficult levels, inducing curriculum without any prior knowledge of the environment.
A recent theme in automated curriculum learning explores adaptively modifying the environment to facilitate learning. Khalifa et al. (2020) and Wang al. (2019; 2020) introduce methods that jointly generate levels and train agents to solve them, leading to co-evolving curriculum. Like Prioritized Level Replay, such curricula exploit the changing differences in learning potential across levels throughout training. Unlike these approaches, our method does not assume control over level generation, requiring only the ability to replay previously visited levels, as referenced by a level identifier such as the corresponding seed used by the PCG algorithm to generate the level. A related set of approaches makes use of multi-agent RL to train a separate teacher agent, which learns a goal task proposal policy (Matiisen et al., 2020; Campero et al., 2020; Sukhbaatar et al., 2017). In contrast to such teacher-student auto-curriculum methods, our approach relies only on a single agent, and therefore does not require extending the environment to accommodate additional agents, such as including teacher-specifer action spaces.
Like our method, Schaul et al. (2015) uses TD-errors as a signal for learning potential. However, while their method only scores 1-step TD-errors to assess the value of revisiting individual past transitions, our method uses estimators based on k-step TD errors to predict the relative value of different choices for generating and training on entire trajectories of future experiences.
7 CONCLUSION AND FUTURE WORK
We introduced Prioritized Level Replay, method for improving sample-efficiency and general- ization performance of RL agents trained and evaluated on procedurally generated environments. Prioritized Level Replay updates level sampling weights according to a scoring metric throughout the course of training. We surveyed the effectiveness of several variations of our method to find that LI value-loss scores consistently lead statistically significant improvements in sample efficiency and generalization on a wide variety of PCG games, including the majority of environments in the ProcGen Benchmark and two challenging MiniGrid environments. Our method combines with prior leading method to improve the state-of-the-as on Proegen Benchmark. Further, on MiniGrid environments, we observe that our method induces an implicit curriculum over the training levels.
While we evaluated Prioritized Level Replay on PCG environments, we believe our method may be generally applicable to any RL environment, given a procedure for generating novel variations of the underlying MDP as a function of a level identifier, for example by varying the starting positions of game entities. Furthermore, as our method modifies only how levels are sampled per episode, combines easily with any on-policy RL algorithm, well as other methods for improving sample complexity and generalization, potentially leading to additive gains. Lastly, the scoring metric can be more generally parameterized as a learned function of the level and statisties of past trajectories over that level, which may prove even more effective than the LI value-loss. We plan to investigate these promising directions in future work.
9

---

Under review as a conference paper at ICLR 2021
REFERENCES
Marcin Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, OpenAl Pieter Abbeel, and Wojeiech Zaremba. Hindsight experience re- play. In Advances in neural information processing systems, pp. 5048-5058, 2017.
M. G. Bellemare, Y. Naddaf, J. Veness, and M. Bowling. The arcade learning environment: An evaluation platform for general agents. Journal of Artificial Intelligence Research, 47:253-279, Jun 2013. ISSN 1076-9757. doi: 10.1613/jair.391. URL htttt::/// doi. 1ttgg/1..11.. jair. 3912.
Andres Campero, Roberta Raileanu, Heinrich Küttler, Joshua B. Tenenbaum, Tim Rocktäschel, and Edward Grefenstette. Learning with amigo: Adversarially motivated intrinsic goals, 2020.
Maxime Chevalier Chevalier-Boisvertt, Dzmitry Bahdanau, Salem Lahlou, Lucas Willems, Chitwan Saharia, Thien Huu Nguyen, and Yoshua Bengio. Babyai: First steps towards grounded language learning with a human in the loop. CoRR, abs/18 810.08272, 2018. URL
1810. 08272.
Maxime Chevalier Chevalier-Boisvert, Lucas Willems, and Suman Pal. Minimalistic gridworld environment for openai gym. hitps: / /tt.bbb.tthuuu/ggo// com/ mww.mmec//aaaaamm.mmm...tawmaeae wttpe///ggmmmiiiiiiiii.m. 2018.
Karl Cobbe. Christopher Hesse, Jacob Hilton, and John Schulman. Leveraging procedural genera- tion benchmark reinforcement learning. arXiv preprint drXiv.1912.01588, 2019.
Karl Cobbe, Jacob Hilton, Oleg Klimov, and John Schulman. Phasic policy gradient, 2020.
David Cohn, Les Atlas, and Richard Ladner. Improving generalization with active learning. Machine learning, 15(2):201-221, 1994.
Adrien Ecoffet, Joost Huizinga, Joel Lehman, Kenneth O. Stanley, and Jeff Clune. Go-explore: new approach for hard-exploration problems, 2019.
Adrien Ecoffet, Joost Huizinga, Joel Lehman, Kenneth Stanley, and Jeff Clune. First return then explore. CoRR, abs/2004. 122199 2020. URL https: httpaaxivvv.r..../..a orw.oogg/////..ooooooooo.oooooos abs//00ss//0/// 12919.
Alex Graves, Mare G. Bellemare, Jacob Menick, Rémi Munos, and Koray Kavukcuoglu. Automated curriculum learning for neural networks. In Doina Precup and Yee Whye Teh (eds.), ), Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 of Proceedings Machine Learning Research, pp. 1311-1320. PMLR, 2017. URL ht.t:: http::://proceeddnege mir. wwwppsswss//pppppppppppppppp wra.e///rrgaa11// ht..essl1a...............
Maximilian Igl, Kamil Ciosek, Yingzhen Li, Sebastian Tschiatschek, Cheng Zhang, Sam Devlin, and Katja Hofmann. Generalization in reinforcement learning with selective noise injection and information bottleneck. Advances in Neural Information Processing Systems, pp. 13978- 13990, 2019.
Maximilian Igl, Gregory Farquhar, Jelena Luketina, Wendelin Boehmer, and Shimon Whiteson. The impact of non-stationarity generalisation in deep reinforcement learning, 2020.
Arthur Juliani, Ahmed Khalifa, Vincent-Pierre Berges, Jonathan Harper, Ervin Teng. Hunter Henry, Adam Crespi, Julian Togelius, and Danny Lange. Obstacle tower: A generalization challenge in vision, control, and planning. Proceedings of the Twenty-Eighle International Joint Conference Artificial Intelligence, Aug 2019, doi: 10. 0.24963/jjaai.2011/377 URL http: dx doi. org 2 24963/443442 www./////e/.....eee http::jaaaaa..........
Niels Justesen, Ruben Rodriguez Torrado, Philip Bontrager, Ahmed Khalifa, Julian Togelius, and Sebastian Risi. Illuminating generalization in deep reinforcement learning through procedural level generation, 2018
Ahmed Khalifa, Philip Bontrager, Sam Earle, and Julian Togelius. Pegrl: Procedural content gener- ation via reinforcement learning, 2020.
10

---

Under review as a conference paper at ICLR 2021
Ilya Kostrikov, Denis Yarats, and Rob Fergus. Image augmentation is all you need: Regularizing deep reinforcement learning from pixels. 2020.
Heinrich Küttler, Nantas Nardelli, Alexander H. Miller, Roberta Raileanu, Marco Selvatici, Edward Grefenstette, and Tim Rocktäschel. The nethack learning environment, 2020.
Tambet Matisen, Avital Oliver, Taco Cohen, and John Schulman. Teacher-student curriculum learning. IEEE Transactions Neural Networks and Learning Systems, 31(9):3732-33) 3730--74000 Sep 2020. ISSN 2162-2388. doi: 10. 109/tmns.2019.299552 1109/TNNLS, 201 2934906.
URL http: /xx doi www.do........o.oo...........o.. .rr./rg///o /10.
Roberta Raileanu, Max Goldstein, Denis Yarats, Ilya Kostrikov, and Rob Fergus. Automatic data augmentation for generalization in deep reinforcement learning, 2020.
Sebastian Risi and Julian Togelius. Increasing generality in machine learning through pro- cedural content generation. Nature Machine Intelligence, 2(8):428-438) Aug 2020. ISSN 2522-5839. doi: 10.1038/s4225--20-00000 s42256- 02000-000---------
URL http: dx dei.dci..oo aei.orrg/o00
Tom Schaul, John Quan, loannis Antonoglou, and David Silver. Prioritized experience replay. CoRR, 1tss11511.0995,,,, 2015.
John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Pieter Abbeel. High- dimensional continuous control using generalized advantage estimation. arXiv preprint S5ff::1500002438, 2015.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. CoRR, abs/1 707.06347, 2017. URL
org. /
Burr Settles. Active learning literature survey. Technical report, University of Wisconsin-Madians Department of Computer Sciences, 2009.
Sahil Sharma, Ashutosh Kumar Jha, Parikshit Hegde, and Balaraman Ravindran. Learning multi- task by active sampling. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April May 3, 2018, Conference Track Proceedings. OpenRe- view.net, 2018. URL https:////// //wp///eeeeeew..e//////e net wwt.:/eettetrrrro/eeee
Sainbayar Sukhbaatar, Zeming Lin, Ilya Kostrikov, Gabriel Synnaeve, Arthur Szlam, and Rob Fer- gus. Intrinsic motivation and automatic curricula via asymmetric self-play, 2017.
Rui Wang, Joel Lehman, Jeff Clune, and Kenneth O. Stanley. POET: open-ended coevolution of environments and their optimized solutions. In Anne Auger and Thomas Stützle (eds.), Proceed- ings the Genetic and Evolutionary Computation Conference, GECCO 2019, Prague, Czech Republic, July 13-17, 2019, pp. 142-151. ACM, 2019. doi: 10.1145/3321707.33277777 URL https: //os:///oo.... www./r/g//.. 100 1 /1111113331111 33213332177 33217399299
Rui Wang, Joel Lehman, Aditya Rawal, Jiale Zhi, Yulun Li, Jeff Clune, and Kenneth Stanley. Enhanced poet: Open-ended reinforcement learning through unbounded invention of learning challenges and their solutions, 2020.
Yunzhi Zhang, Pieter Abbeel, and Lerrel Pinto. Automatic curriculum learning through value dis- agreement, 2020.
Victor Zhong, Tim Rocktäschel, and Edward Grefenstette. RTFM: generalising to new envi-
ronment dynamics via reading. In 8th International Conference Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL https: / //openzeview. wtt///ormm..ddSleee.........

---

Under review as a conference paper at ICLR 2021
A EXPERIMENT DETAILS
A.1 PROCGEN BENCIIMAR
The OpenAl ProcGen Benchmark suite consists of 16 procedurally-generaeed games of varying styles, exhibiting a diversity of gameplay similar that of the ALE benchmark. Levels in each game are determined by a seed, and can vary in many ways, including layout, visual appearance, and starting positions of game entities. All ProcGen environments share the same discrete 15- dimensional action space and produce 64 x 64 x 3 RGB observations. Cobbe et al. (2019) provides a comprehensive description of each of the 16 environments.
We follow the original protocol for testing generalization performance on ProcGen defined by Cobbe et al. (2019): We train an agent for each game on a finite number of levels, Nuain and test on the full distribution of levels. Previous benchmarks showed that training under this protocol using satt--of-the-al policy-gradient gradient algorithms leads to a significant generalization gap between test and train performance in all games, making ProcGen useful benchmark for assessing generalization performance.
To make the most efficient of our computational resources, we train on the easy difficulty mode using the recommended settings of Numin 200 and 25M steps of training, as well as the same ResNet policy architecture and PPO hyperparameters shared across all games as Cobbe al. (2019). We find 25M steps to be sufficient for uncovering differences in generalization performance among our methods and standard baselines. Moreover, under this setup, we find ProcGen training runs re- quire much less wall-clock time than training runs on our MiniGrid environments of interest over an equivalent number of steps needed to uncover differences generalization performance. Therefore we perform a survey of the empirical differences of various settings of Prioritized Level Replay on ProcGen rather than MiniGrid.
We evaluate each combination of the scoring function choices in Table with both rank and pro- portional prioritization, performing a coarse grid search for each pair over different settings of the temperature parameter 3 in {0.1, 0.5, 1.0, 1.4, 2.0) and the staleness coefficient P in {0.1, 0.3, 1.0). For each setting, we run 4 trials across all 16 of games of the Procgen Benchmark. We find that rank prioritization tends to produce larger improvements to test performance than proportional pri- oritization, and the best setting across Proegen games was 3 = 0.1, p = 0.1. In our TD-error-basee based scoring functions, we set y and À equal to the same respective values used by the GAE in PPO dur- ing training. See Appendix for an comprehensive overview of the same hyperparameter setting we used for PPO across all Procgen environments.
A.2 MINIGRID
In order to validate the conjecture that Prioritized Level Replay with L1 value-loss scores induces an implicit curriculum over the training levels, we turn to the MiniGrid suite Beevaller-Boiiver et al., 2018). MiniGrid features a series of highly structured environments of increasing difficulty. Each environment features task in gridworld setting, and in ProcGen, environment levels determined by a seed. Harder levels require the agent to perform longer action sequences over a combinatorially-rich set of game entities, on increasingly larger grids. The clear ordering of dif- ficulty over subsets of MiniGrid environments allows us to track the relative difficulty of levels sampled under Prioritized Level Replay over the course of training.
MiniGrid environments share discrete 7-dimensional action space and produce a 3-channel integer state encoding of the x grid immediately including and in front of the agent. However, following the training setup in Igl et al. (2019), we modify the environment to produce an N M x 3 encoding of the full grid, where N and M vary according to the maximum grid dimensions of each environ- ment. This fully observable setup requires the agent to generalize across different level layouts.
We evaluate value-based level replay with rank prioritization on two distinct MiniGrid environ- ments, whose levels are uniformly distributed across several difficulty settings. Training levels of varying difficulties helps agents make use of the easier levels as stepping stones to learn useful behaviors that help the agent make progress on harder levels. However, under the sniforrm-smpling baseline, learning may be inefficient, as the training process does not selectively train the agent on levels of increasing difficulty, leading to wasted training steps when difficult level is sampled
12

---

Under review as a conference paper at ICLR 2021
early in training. On the contrary, if value-based level replay scores samples levels according to the iime-vveaaged LI value loss recently experienced level trajectories, the average difficulty of the sampled levels should increase over time, following the reasoning outlined in 5.1, that significant non-stationary value targets will be encountered earlier in easier levels.
As in Igl et al. (2019), we parameterize the agent policy channels. with a final hidden layer of size 64. All kemnlls are 2 x and use a stride of For the ObstructedMazzGammuu environments, we increase the number of channels of the final CNN layer to 64. We follow the same generalization evaluation protocol as used for ProcGen, training the agent on fixed set of 4000 levels for MultiRoom- -a-------aandnnn 3000 levels for ObstrictedMazeGamuut Easy, and 6000 levels
3-layer CNN with 16, 32, and 32
and testing on the full level distribution. We chose these values for Arain to ensure roughly 1000 training levels of each represented difficulty setting of each environment. As in the case of our Procgen experiments, we we set and À equal to the same respective values used by the GAE in PPO during training, and use reward normalization during training. All MiniGrid experiments shared the same hyperparameters listed in B and, when using value-based level replay, set 3 0.1, P = 0.3 with rank prioritization.
The remainder of this section provides more details about the various MiniGrid environments used in this work.
This environment requires the agent navigate through 2, 3, rooms respectively to reach a goal object, resulting in natural ordering of levels over four levels of difficulty. The agent always starts at random position in the furthest from the goal object, facing a random direction. The goal object is also initialized to a random position within its room. See Figure 5 for screenshots of example levels.
MultiRoom-NN4Ramte
Figure 5: Example levels of each of the four difficulty levels of MultiRoom-N4-Ran in order of increasing difficulty from left to right. The agent (red triangle) must reach the goal (green square).
ObstructedMMaze-aaamae Easy This environment consists levels uniformly distributed across the first three difficulty settings of the ObstructedMaae environment, in which the agent must locate and pick-up the key order to unlock the door pick-up goal object in a second room. The agent and goal object always initialized in random positions in different rooms separated by the locked door. The second difficulty setting further requires the agent to first uncover the key from under a box before picking up the key. The third difficulty level further requires the agent first move ball blocking the door before entering the door. See Figure for screenshots of example levels.
Figure 6: Example levels of each the three difficulty levels of ObstrnctedMaze--aamtt in order of increasing difficulty from left to right. The agent must find the key, which may be hidden under box, unlock door granting access to the goal object (blue circle).
13

---

Under review as a conference paper at ICLR 2021
This environment consists of levels uniformly distributed across the first six difficulty levels of the ObstructedMaze environment. Harder levels corresponding to the fourth, fifth, and sixth difficulty settings include two additional rooms with goal object to distract the agent. Each instance of these harder levels also contain two pairs keys of different colors, each opening door of the same color. The agent always starts room away from the randomly positioned goal object. Each of the two keys is visible in the fourth difficulty setting and doors unobstructed. The fifth difficulty setting hides the keys under boxes, and the sixth again places obstacles that must be removed before entering two of the doors, one of which is always the door the goal-containing room. See Figure for example screenshots.
ObstrrucedMMazze-Gaautte
Figure 7: Example levels in increasing difficulty from left right of each additional difficulty setting introduced by ObstructedMaae- Gamet-Gaauuttaaa Hard addition to those in ObstructedMaze- Gamut- Easy.
B HYPERPARAMETERS
Table lists the hyperparameters used during training. The values in each column were shared across all environments in Procgen and MiniGrid respectively. For Procgen, these are the defaults used by Cobbe et al. (2019). We adapted these for Minigrid, but did no further grid-searching of these values.
Table 3: Hyperparameters used for training.
Parameter
Procgen
MiniGrid
0.999
0.999
AGAE
0.95
0.95
PPO rollout length
256
256
PPO epochs
4
PPO minibatches epoch
8
PPO clip range
0.2
0.2
PPO number of workers
64
64
Adam learning rate
5e-4
7e-4
Adam
le-5
le-5
reward normalization
yes
yes
entropy bonus coefficient
0.01
0.01
value loss coefficient
0.5
0.5
C ADDITIONAL EXPERIMENTAL RESULTS
C.I EXTENDED RESULTS ON PROCGEN BENCHMARK
We show Figures and 9, the mean test episodic returns on the Procgen Benchmark for value- based level replay with rank and proportional prioritization, respectively. In both of these plots,
14

---

Under review as a conference paper at ICLR 2021
that using only staleness (p 1) only L1 value loss scores = 0) is considerably worse than direct level sampling. Thus, we only observe gains compared to the baseline when both level scores and staleness used for the sampling distribution. Comparing Figures 8 with 9 we find that value-hased level replay with proportional instead of rank prioritization provides more statistically significant gains compared to direct level sampling, but average leads worse mean test returns than rank prioritization.
Lastly, show in Figure 10 that when value-based level replay improves generalization perfor- mance on a game, it also either matches or improves training sample efficiency. This shows that when beneficial duced by our method prove similarly useful on the training levels. However we see that our method reduces training sample efficiency on two games on which our method does not improve general- ization performance. Since our method does not discover useful auto-curricula for these games, it likely that uniformly sampling levels training time allows the agent to better memorize use- ful behaviors on each of the training levels compared to the selective sampling performed by our method.
test-time performance, the representations learned via the auto-curriculum
L1 value loss rank priorilization for various uniform-sampliinn baseline
p
p
bightsh *
bossiigh
caveftyer *
chaser
climber *
colnrun
dodgeball
trubbl *
Mcan epsode
1.50
Steps
Figure 8: Mean test episodic returns on the Procgen Benchmark for value-based level replay with rank prioritization with 8 0.1 across a range of values p. which weighs how much importance the final replay distribution assigns to staleness. The replay distribution must consider both the LI value-loss and staleness values to realize improvements to generalization and sample complexity. Plots are averaged over 10 runs, and the shaded area indicates one standard deviation around the mean. * next to the game name indicates the condition p = 0.1 exhibits statistically significantly better final test returns sample efficiency along the test curve 0.05, which we observe in 10 of games.
15

---

Under review as a conference paper at ICLR 2021
L1 value loss proportonal proriozation for vanous P vs unitorm-sammplnng baseline
P
p
bigftsh
bosstight
caveflyer
thaser
climbor *
colnrum
dodgoball+
fruibol
Mean episode
helst
Jamper
leaper
m720
miner
ninja
plunder
starp
22
104
130
236 302
120
2004
1.00
134
254
200
Steps
Figure 9: Mean test episodic returns the Procgen Benchmark for value-based level replay with proportional prioritization with 0.1 across a range values of p. As in the case of rank prioritization, the replay distribution must consider both the LI value loss score and level staleness values in order to realize performance improvements. Plots are averaged over 10 runs, and the shaded area indicates the condition p = 0.1 exhibits statistically significantly better final test returns or sample efficiency along the test curve p 0.05, which observe in 11 of 16 games.
standard deviation around the mean. A * next to the game name indicates
16

---

Under review as a conference paper at ICLR 2021
Training sample efficiency of value-based level replay uniform-sampiiee baseline
Unifarm
Rank, 0.1
Proportional 0.1
Bigiahh
bossiight
caveflyer
dodgeball
Mean episode
hebd
jumper
leaper
maze
miner
rirja
plundar
starpiol
Steps
Figure 10: Mean train episodic returns on the Procgen Benchmark for value-based level replay with = 0.1 and each of the prioritization methods investigated. On some games, value-based replay improves both training sample efficiency and generalization performance (e.g. BigFish and Chaser), while on others, only generalization performance (e.g. CaveFlyyr for rank prioritization). Plots averaged over 10 runs, and the shaded area indicates one standard deviation around the mean.
17

---

Under review as a conference paper at ICLR 2021
Table 4: Comparison test scores PPO with value-based level replay (PLR) against PPO with uniform-sampling on the hard setting of Procgen Benchmark. As in Table 2, reported figures rep- resent the mean and standard deviation of average test scores over 100 episodes aggregated across 10 runs, each initialized with unique training seed. For each run, normalized average return is computed by dividing the average test return for each game by the corresponding average test return of the uniform-sani sampling baseline over all 1000 test episodes of that game, followed by averaging these normalized returns over all 16 games. The final row reports the mean and standard deviation of the normalized returns aggregated across runs. Note that while the uniform-sampling bascline achieves a higher mean return on BigFish and StarPilot than value-based level replay, this difference was not found to be statistically significant according to Welch's t-test.
Games
Uniform
PLR
BigFish
9.13 + 4.51
7.77 + 1.01
BossFight
6.82 + 0.59
8.67 +
CaveFlyer
3.13 0.47
6.36
Chaser
5.311.22
6.26
Climber
3.46
6.76
CoinRun
0.24
+.33
Dodgeball
1.76
2.01 1.09
FruitBot
2.559
15.8611.24
Heist
0.84
1.24 0.37
Jumper
0.46
3.58 + 0.46
Leaper
2.52 + 1.45
6.42 0.43
Maze
3.98 0.18
4.12 + 0.46
Miner
9.5
9.67 + 0.44
Ninja
3.34
5.36 + 0.52
Plunder
2 0.34
4.32
StarPilot
2.85 0.7
2.63 0.3
Normalized Return (%)
100.0 + 9.5
138.6 9.6
18

---

Under review as a conference paper at ICLR 2021
priorilization uniform-sampiing Procgen (Hard)
Uniform
Li-value
higfshh
boselight
cwvelyar
choleer
climber
cotarun
dodgeball
Truibor
Mean lest epsode
Ieaper
plunder
My
29M 50H 250 1094 1220 15MH 1750 2006
206 52V 733 1904 1330 190M 1730 200M
25H
20U
15k
1800
120H
150V
(734
200V
Steps
Figure 11: Comparison of mean train episodic returns Procgen Benchmark's 's hard setting for value-based level replay against the uniform-sanee -aarrming baseline. These results were generated with the best hyperparameters for value-based level replay found for Procgen Benchmark 's easy setting, where B P 0.01. Plots are averaged over runs, and the shaded area indicates one standard deviation around the mean. Note that even without tuning level-replay hyperparameters for Procgen Benchmark's hard setting, we reach statistically significant improvements in test performance on the majority of the benchmark (9 of 16 games).
19

---

Under review as a conference paper at ICLR 2021
C.2 TRAINING ON THE FULL LEVEL DISTRIBUTION
While assessment of generalization performance calls for using fixed set of training levels, ideally our method can also make use of the full level distribution given access to it. To take advantage modify the
of unspecified number of training levels sampled from the full level distribution, list structures for storing scores and timestamps (see Algorithm and 2) to keep up to maximum of level buffer size, M, items. When the lists are full, we the next level for replacement be
min arg min Preplay(1). (!).
When the outcome of the Bernoulli PD entails sampling from the replay distribution, resulting in sampling a new level I, the score and timestamps replace those of miin only if the score of min lower than that of In this way, Prioritized Level Replay keeps running buffer throughout training of the top M levels appraised have the highest learning potential for replaying anew.
Figure 12 shows that with access to the full level distribution at training, value-based level replay im- proves
and generalization performance in both environments compared to uniform sampling. In MultiRoom-Nal -o-o----aandom the value M makes little difference to generalization perfor- mance, and access to the full level distribution at training leads to a policy outperforming one trained with value- based level replay Easy, a smaller yields comparable generalization performance the full level distribution. These results confirm that for certain environments, the auto-curriculum discovered by method leads to more sample-efficient training fixed of levels than training on the full level distribution.
fixed set of training levels. However, leads to worse test performance, while training on a fixed set of 3000 levels
ObstructedMuzzGaamud
policy trained with value-based level replay
MultiRoom-N4Ranndom
Mean test episode retum
0.8
Uniform + full dist
0.6
L1 value loss 4000 fixed seeds
L1 value loss full dist, = 500
0.4
L1 value loss full dist, M 1000
L1 value loss full dist, 4000
0.2
0.0
20M
40M
60M
80M
100M
Steps
1.0
ObstructetMazeGammutaaay
Mean test episode return
0.8
Uniform + full dist
L1 value loss 3000 fixed seeds
0.6
L1 value loss full dist, 500
0.4
L1 value loss full dist, 1500
L1 value loss full dist, 3000
0.2
0.0
20M
40M
60M
80M
100M
Steps
Figure 12: Mean test episodic returns on MultiRoom-N4RRandonn (top) and ObstrnctedMezeGaamut. Easy (bottom) with access the full level distribution at training. We set PD to a Bernoulli param- eterized p 0.5 for MultRoom-NN4-P -a-nooo and p 0.95 for ObstructedMazzeamuut Easy (the best values found via grid search). As with all MiniGrid experiments using Prioritized Level Replay, set 0.1 and p 0.3.
20

---

Under review as a conference paper at ICLR 2021
C.3 ADDITIVE GAINS WITH UCB-DRAC
UCB-AutoDrAC, introduced in Raileanu et al. (2020), has been shown to improve the generalization of PPO agents Procgen Benchmark by making of data augmentation strategy. This method extends PPO by introducing a UCB bandit trained concurrently with the agent. Given a set of predefined image transformations, F, this bandit Iearns to select, the start of each PPO update, single transformation to apply to every frame in the update. Following the standard UCB algorithm, the selection rule for data augmentation ft before the 1-th update defined as
log(t) N(J)
arg max Q()) + JEF
where Q()) computed as sliding window of the most recent mean returns obtained by agent after the policy was updated on frames transformed by f. the constant is the UCB exploration constant, and (ff) counts how many times transformation f has been selected. Note that the UCB- AutoDrAC algorithm also introduces additional KL-divergence term in the loss function to ensure the policy exhibits ceeeformaaionnnnvaiiaan optimality. We refer the reader to Raileanu et al. (2020) for the full description of this method.
We use the best hyperparameters for Proegen Benchmark reported in Raileanu et al. (2020), setting K 10 and 0.1. For Prioritized Level Replay, we make of the LI-value-loss scoring func- tion with 3 = 0.1. Figure 13 shows test performance throughout training of UCB-AutoDrAC with LI-value-loss level replay against UCB-DrAC without level replay and PPO with uniform sam- pling.
Combining Value-Based Level Replay with Automatic Data Augmentation
Uniiomm
UCB-DrAC Uniioom
UCB-DrAC + Livallue-oos leval raplay
bigfish
bosstight
caveflyer
colnrun
dodgeball
Mean episode retur
jumper
lsoper
miner
ninja
pluncer
starplet
Steps
Figure 13: Mean test episodic returns of UCB-DrAC with value-based level replay on Procgen Benchmark (casy), attaining statistically signiiiia (* generalization gains 14 of 16 games.
21

---

Under review as a conference paper at ICLR 2021
D ALGORITHMS
In this section, we provide detailed pseudocode for how Prioritized Level Replay can be used for experience collection with policy-gradient method based on T'step rollouts. Algorithm presents the extension of the generic policy-gradient training loop presented in Algorithm to the case of T-step rollouts, and Algorithm presents an implementation of experience collection in this setting (extending Algorithm 2). Note that when using T-step rollouts in the training loop, rollouts may start and end between episode boundaries. To compute level scores on full trajectories segmented across rollouts, we compute scores of partial episodes according to Equation 2, and record these partial scores alongside the partial episode step count in separate buffer S. The function S then technically takes S as an additional argument to combine the partial score with the score computed on the final trajectory segment.
Algorithm 3 Generic T Ttep policy-gradien training loop with prioritized level replay
Input:
Training levels Auain an environment, policy ng, rollout length T, number of updates Ny, batch size No, policy update function (1,,, 0) - 0¹.
Initialize level scores S, partial level scores S, and level timestamps C Initialize global episode count c + Initialize set of visited levels Aseen Ø
Initialize experience buffer B Ø Initialize No parallel environment instances E to random level in Airii for to N, do Ø for k 1 to N₂ do < B end for + ((, 0) end for
Dellecteepprrienees(: E, Again: Awen To. S,S, C, Using Algorithm
22

---

Under review as a conference paper at ICLR 2021
Algorithm Collect 7 step rollouts with prioritized level replay
Input:
Actor index k, batch environments E, training levels Amain visited levels Aween current level
policy ne, rollout length T, scoring function score, level scores S, partial scores S, staleness values C, and global episode count
Output:
Experience buffer B
Initialize B Ø, and set current level / Es
Observe current state termination flag do
if dy then
Choose current level 4 < SAMPLENEXTLEVEIL S, c) and Eg +- l Update level timestamp C + Observe initial state
end
Choose dn (-(0s)))
t=
Initialize episodic trajectory buffer while < T do
Observe (st, Tr, de) B - B U ($:-1, a1-1: St,
ru, de, log To(a)) < T (st-1, a1-1, St, re. de, log (a))
if de then
Update level score <- score(t, no, S.) and partial score S; +-
T f- Ø
Update current level + SAMPLENEXTLEVELLAMmi. S, C, c) and Eg
Update level timestamp C; t-c
end
Choose a++1 (-(ss))) 1 1+1++
end while
not de then
S, (5(().1))
Track partial score and |r| for time-averaged scores.
end if
function SAMPLENEXTLEVELAAU.. S, S,C.O
C f c+1
Sample replay decision d ~ (d)
0 and JArain \ Asceal > then
Sample an unseen level, if any
Define new index 4- |
Sample 4 ~ Prew [|rriin Aseen)
Add to Aween add initial value O to S and C
else
Sample a level for replay
Sample 4; ~ (1 - p) Ps( Assen S) p- Po(l|Ascen C,c)
end if
end function
23


Reviews:
[{"review_id": "rmojgdtSgyc", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "##########################################################################\n\n**Summary**:\n\nThis paper proposes a prioritized sampling strategy for task sampling in procedurally generated environments. While training an RL agent across many tasks (levels), we can either sample a new task uniformly from the training task distribution or sample a new task with different weights. The paper claims that sampling based on the average magnitude of generalized advantage estimate (GAE) yields faster learning in most Procgen environments and a few MiniGrid environments. Overall, I found the idea to be simple and intuitive. But the benefit of using prioritized level replay is also not very consistent across different environments used in the paper. \n##########################################################################\n\n**Strengths**:\n\nThe method of the paper is simple and can be incorporated into many existing RL algorithms.\n\nThe paper shows that L1 value loss is a good scoring metric for the prioritization by comparing several different choices.\n\n\n##########################################################################\n\n**Weaknesses**:\n\nThe advantage of using prioritized level replay against uniform sampling is rather small in many tasks (11 out of 19 tasks) shown in the paper (Climber, Coinrun, Dodgeball, Fruitbot, Heist, Jumper, Maze, Miner, Ninja, Starpilot, ObstructedMazeGamut-Medium).\n\n\nThe paper only presents results in the easy mode of procgen. While I understand the reason due to the limit on the computational resources, it would be more convincing to show the results on at least 1 or 2 procgen tasks in the difficult mode. If the overall task difficulty is increased, then the advantage of learning in a curriculum (starting from the easy tasks and then to the difficult tasks) are expected to be more salient.\n\n\nWhile the scoring metrics used in the paper are all related to the policy function or value function that is being learned, how about a scoring metric that is only based on the number of steps that the agent experiences in a task and whether the agent fails or succeeds? Intuitively, if the lifetime of an agent is short and the agent solves the task, it is an easy task. If the agent does not solve the task or it takes the agent many more steps to solve the task, it is a difficult task. Another metric to compare to is prioritize based on the return value of the trajectories. If the return value is high, then the task is probably already solved by the current policy, so we can sample such tasks less frequently.\n\nIn Figure 4, it seems the advantage of using L1 value loss for the prioritization in sampling is more obvious in easy environments (Multiroom-N4-Random and ObstructedMazeGamut-Easy). But its performance becomes very close to the uniform sampling strategy in harder environments (ObstructedMazeGamut-Medium). Why would the advantage of using prioritization (hence implicit curriculum) fade as the task difficulty increases?\n\nIn Figure 4, it is hard to connect the top row to the bottom row as the top row uses the environment steps for the x-axis, the bottom row uses the number of PPO updates for the y-axis. I would suggest plot the bottom row figures in terms of the environment steps as well and use the same x-range.\n\n\n##########################################################################\n\n**Minor points**:\n\nSome details about the experiment setup, especially the MiniGrid environments, are missing. For example, how do the MiniGrid environments look like, what does the difficulty mean in these environments, which parts of the environments are randomized across levels, reward structure, etc.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "prdz98BzGD4", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "**SUMMARY**\n\nThe present work considers the problem of learning in procedurally generated environments. This is a class of simulation environments in which each individual environment is created algorithmically where certain environmental factors are varied in each instance (referred to as levels in this work). Learning algorithms in this setting typically use a fixed set of training and evaluation environments. The present work proposes to sample the training environments such that the learning progress of the agent is optimized. This is achieved by proposing an algorithm for level prioritization during training. The performance of the approach is demonstrated on the Procgen Benchmark and two MiniGrid benchmarks and the authors argue that their approach induces an implicit curriculum in sparse reward settings.\n\n**STRENGTHS**\n- The general idea of prioritization for level sampling makes a lot of sense and is demonstrated to improve sample-efficiency for skill learning in procedurally generated environments.\n- I also liked that the authors compared with a big variety of different scoring metrics.\n\n**WEAKNESSES**\n- The intuition of \"greater discrepancy between expected and actual\nreturns, making \u000e$\\delta_t$ a useful measure of the learning potential\" makes sense. The heuristic score also works well in practice. One limitation I see is that there is no theoretical justification for why the TD-error is a good predictor for learnability. \n- This is maybe more an avenue for future work than an actual weakness but it seems to me that the algorithm is not making use of all potentially useful information. In each timestep, it only considers the last score achieved in a level. Maybe it would also be interesting to consider the full history of scores. My intuition is that levels in which agents were historically very slow to learn are maybe not as useful (or at least not useful at the moment). I.e., maybe in order to learn competing at such levels it is better to compete on other levels first?\n- Is there, at least from a qualitative perspective, an explanation for why certain environments do not benefit as much from the proposed level sampling approach?\n\n**REPRODUCIBILITY**\n\nThe work seems reproducible. Most of the information relevant for reproducibility is given in Appendices A & B. It would be great if the authors would also make the source code available.\n\n**CLARITY**\n\nOverall, I found the work to be very clearly written and have only minor questions/remarks:\n- To what extent does the use of TD-errors potentially limit the type of learning algorithms that can be used in the context of the proposed framework. Computing the TD-error requires a value function. As I understand it, some RL algorithms never compute a value function.\n- If I haven't overlooked it, there is no explanation of $c$ after eq. (4) while $C_i$ is explained earlier. Is $c$ simply the current episode?\n\n\n**EVALUATIONS**\n\nThe work is compared with several scoring function baselines using PPO. While the authors claim that the method is applicable to other RL agents, the evaluations do not show any results with other agent types. The authors mention several different benchmarks in that space. It would be interesting to know why particularly Procgen Benchmark and MiniGrid environments were chosen.\n\nIt is also not clearm to me why PPO is used as the base agent. Was this for ease of implementation / its popularity? Wouldn't it make sense to use more recent agents to see the added benefit of the proposed approach. E.g., would V-MPO be applicable here? \n\n**NOVELTY / RELEVANCE**\n\nThe work is very interesting and the authors make a compelling case that procedurally generated environments can benefit from a conscious sampling of the levels with regard to usefulness for learnability.\n\nI am not sure whether the claim \"Prioritized Level Replay induces an implicit curriculum, taking the agent gradually from easier to harder levels.\" is fully valid. As I understand it, the hardest levels are also the most likely to be sampled. The force counteracting this to some extent is the staleness-based sampling term $P_C$. For a gradual curriculum, I would expect $P_S$ to be designed such that it does not choose the hardest level but the one promising the best learning outcome. Particularly in the early stages of the training, the hard levels might be less useful than levels of medium difficulty.\n\n**SUMMARY**\n\nI found that paper very interesting. While I am not working in the particular subfield of the work and cannot sufficiently judge relation with prior works, I can confidently say that the idea and implementation details were conveyed very well. My main concerns are regarding the understanding of the \"failure cases\" and to what extent the graduality claim applies. That being said, I believe this line of work to be really interesting and to have a lot of potential for improved sample-efficiency when training RL agents in algorithmically generated simulation environments.\n\n**POST-DISCUSSION UPDATE**\n\nI want to thank the authors for correcting my misunderstandings, answering my questions, and providing additional material. As a consequence of this, I have raised my score to \"Accept\". To answer your question about what would be needed for a higher score: For a strong accept recommendation, I would have expected a mix of several additional things such as a clear impact outside of own subfield, code availability at time of submission (to evaluate how easy it is to reproduce the results and re-use the code), or more additional theoretical justification (in the sense of new formal guarantees for at least certain aspects of the proposed method). While not directly working in this subfield, I still think this work is solid and worthy of publication.", "extra_scores": {}, "extra_text": {}}, {"review_id": "WTfKFzqEG3u", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\n\nThis paper concerns about the use of experience replay in a way that past experience is sampled based on (implicit) levels so as for the agent to better adapt to the current task at hand. The authors defined a replay distribution (where experience is sampled) based on two scores relevant to learning potential and staleness. Due to its formulation, the change of replay distribution can be used as an outer-layer of a learning algorithm without any modification of the underlying learning mode. The authors conducted experiments over a set of benchmark data sets relevant to level-ness and found statistically significant improvements over more than half of the tasks.\n\nThe overall impression of the paper is that it presents a simple yet effective solution to prioritizing experience in the presence of level-ness in a given task. The basic idea is finding out past experience with high \"learning potential\" by examining a past trajectory's 'wrongness' and how long the policy was not updated (= likely still wrong). \n\nPoint: The notion of level and its relevance to learning potential.\nFirst, the paper does not contain any mathematical (or clear) definition of level, which should be crucial to understand the paper. At the beginning it is only explained as different configurations (i.e., any non-singleton environment). Further, it is hard to understand why the notion of levels is even needed to be employed in the paper. An RL agent has a specific way to learn experience (updating parameters) and its artifacts makes \"experience replay\" useful in most RL agents. Then, there would be an optimal way of replaying experience at any given time --- a certain order of a subset of past trajectories to be replayed for a current policy. The current form of P_replay (Eq. 1) does not need any specific notion of level-ness but only 'learning potential'. I suspect that Eq. 1 also works for a singleton environment, which the authors excluded from consideration.\n\nPoint: The conjecture about curriculum learning. \nIt is reasonable to assume that the notion of hardness of a task for an RL agent is the difficulty of optimizing its policy (=resulting in higher TD-errors). When the human understanding of easiness of a task (i.e., level) matches the agent's ability to optimize, we would safely say that PLR induces curriculum implicitly. It is nice to see such plots (Figure 4) that empirically validate the conjecture. However, isn't it a much anticipated result?\n\nQuestions\nQ1. Would different algorithms other than (PPO + GAE) make the results different from the current form? \n\nQ2: If we interpret P_S and P_C as two probability distributions, multiplying them seems more natural to me. What is the rationale behind for adding them not multiplying them (or use (1-rho) log P_S + (rho) log P_C)? Further, any reason for P_C being proportional to c-C_i?\n\nQ2. How about learning hyper-parameters on the fly? Both \\beta and \\rho might be adjusted throughout learning. \nFurther, it is conceivable that the optimal \\beta and \\rho are not fixed quantities but can be dependent to a given pair of policy and trajectory. \n\nMinor\nFigure 1, there are two taus. The top would be \\pi?\nBackground \"We to refer to\"\n=======\nI read through all the reviews and rebuttals and I could better understand and evaluate the paper. I updated my score to 7. \n\nGiven that this replay scheme works fairly well (intuitively, empirically), easy to understand and implement, fairly sufficient amount of empirical experimentation, I would like to see the paper accepted (and adopted and improved by others).\n\nOne more comment about staleness.\nI think staleness is a proxy measure for the (unmeasured) score of the 'current' policy on that level. So I would like to see (in future or revised version) some experiments that measure how well staleness measure correlate with such score. Further, the way staleness is designed properly reflects how the score degrades as the level isn't played.\n\nSome idea.\nIt would be nice to make a connection to multi-task learning where tasks share some similarities. Currently, level is somewhat 'linearly' defined. If an agent plays level x, then staleness for level x' (something similar to x') doesn't have to be updated a lot compared to another task which might be dissimilar to level x. Hence, some similarity measure can be further employed (or learn a metric).", "extra_scores": {}, "extra_text": {}}, {"review_id": "KUSGE5Ix8S", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "### Paper Summary\n\nThis paper allows agents to set the initial conditions (level) for procedurally generated episodes during exploration to past observed values, and proposes to have agents form an intrinsic curriculum by resampling past levels based on a heuristic measure of expected learning progress. The authors test several heuristic measures and find that the average absolute magnitude of the generalized advantage estimate works well. The authors hypothesize that this intrinsic curriculum will improve optimization/learning relative to an agent that always samples initial conditions from the environment distribution. The authors verify that their prioritization strategy usually improves performance in several Progen Benchmark and MiniGrid environments, usually by a small but statistically significant amount, but sometimes by a large amount. \n\n### Summary Review (highlights re: quality, clarity, originality and significance)\n\nThe paper is well written and clear after one understands the basic idea. The idea is simple, and the algorithm/experiments seem straightforward to reimplement. The experiments are about what one would expect and seem to be well executed. The idea is original but not particularly innovative (this seems like the first heuristic prioritization approach that would come to mind given that the agent is able to choose the level). The improvement in empirical results is not particularly surprising (if anything, I would have expected more large improvements like the ones on bigfish/leaper environments). As this method is constrained to procedurally generated environments (or at least, evaluation of the method is constrained to procedurally generated environments), the significance seems rather limited. The required assumption seems rather strong, as it requires a simulator / control over the environment, which limits applicability.  \n\n### Pros\n\n- This a simple idea that can improve performance in Procedurally Generated Environments given that the agent is allowed to set the initial conditions / pick the level.\n- The performance improvement in 4 of the 19 environments tested is large & seems absolute (i.e., it's seems like a final performance improvement, not just a sample efficiency improvement). \n- The paper is well written/presented, easy to understand, and the empirical evaluation seems well done. The results do not seem difficult to replicate. \n\n### Cons\n\n- Despite being less intrusive than direct access to the level generation mechanism, the assumption that the agent can replay levels seems rather strong to me, and simplifies the task of learning procedurally generated environments very substantially.  \n\n    ($\\dagger$) I would argue that we don’t use procedurally generated environments as benchmarks in order to solve procedurally generated environments, but rather a tool for measuring generalization, so it's unclear to me that a technique that improves sample efficiency only in a procedurally generated environment is useful. \n\n    Unlike environment-agnostic techniques like prioritized replay, HER, intrinsic reward, intrinsic goal selection, etc., this requires you to have control over the environment, which seems to limit the applicability. If this is only useful with a simulator, then the small gains in sample efficiency aren’t actually that relevant, though this approach does seem to improve final performance in 4 of the 19 environments tested. \n- It’s not clear until the second page whether your method is a prioritized replay buffer scheme, or a task selection scheme. Actually, I was certain it was a prioritized replay buffer scheme until the second page, because that is the more natural/general setting (as noted above, I find the assumption that the agent can replay levels to be rather strong). \n- Several new hyperparameters are introduced; this said, guidance/ablations are performed, and it seems like the choices will generalize decently well (albeit there were different choices for ProcGen/Minigrid).\n\n### Questions / Etc.\n\n- My main question for the authors is to ask for a counterargument to ($\\dagger$) above. \n- It would be good if this can be shown to work in multi-goal setting, as it is quite similar to ProcGen setting... you draw some distinctions, but I do think your approach would be applicable there. \n\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents a method for automatically generating levels of varying complexity for training the agent.  The results are well summarized in the paper abstract, "significantly improved sample-efficiency and generalization on the majority of Procgen Benchmark environments as well as two challenging MiniGrid environments." The work is clearly presented, and the experiments are thorough. 

R1, R2, and R3 voted to accept the paper with 7, 6, and 7 scores. R4 voted to reject the paper with a score of 5. The reviewers mostly agree (except for R4) that significant performance gains have been achieved. R4 is unsatisfied as he/she believes that performance gains are small and exploit the simulator (e.g., using resets). 

The paper's main pro is well summarized by R4's comment, "The method of the paper is simple and can be incorporated into many existing RL algorithms."

The main drawback of the paper is that many curriculum learning techniques have been proposed in the past. E.g., Matiisen et al. (https://arxiv.org/pdf/1707.00183.pdf). In fact the authors discuss this work in the related work section, but dub it multi-agent RL work. This is not true. The method of Matiisen et al. is very similar to the proposed approach but uses a different criterion for learning progress. Comparison to this work is warranted, without which the paper should not be accepted. In the post-rebuttal discussion, R2 and R3 agree that this comparison is necessary. Therefore, I recommend that this paper be rejected for now and resubmitted to a future venue after incorporating a comparison with Matiisen et al. 



Decision: Reject