Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: **SUMMARY**

The 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.

**STRENGTHS**
- 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.
- I also liked that the authors compared with a big variety of different scoring metrics.

**WEAKNESSES**
- The intuition of "greater discrepancy between expected and actual
returns, making $\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. 
- 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?
- 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?

**REPRODUCIBILITY**

The 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.

**CLARITY**

Overall, I found the work to be very clearly written and have only minor questions/remarks:
- 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.
- 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?


**EVALUATIONS**

The 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.

It 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? 

**NOVELTY / RELEVANCE**

The 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.

I 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.

**SUMMARY**

I 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.

**POST-DISCUSSION UPDATE**

I 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.
review_title: Review [Updated]

final_score: rating: 5: Marginally below acceptance threshold
review_content: ### Paper Summary

This 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. 

### Summary Review (highlights re: quality, clarity, originality and significance)

The 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.  

### Pros

- 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.
- 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). 
- The paper is well written/presented, easy to understand, and the empirical evaluation seems well done. The results do not seem difficult to replicate. 

### Cons

- 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.  

    ($\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. 

    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. 
- 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). 
- 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).

### Questions / Etc.

- My main question for the authors is to ask for a counterargument to ($\dagger$) above. 
- 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. 



review_title: Well done paper, but unclear significance / potentially limited applicability

final_score: rating: 7: Good paper, accept
review_content: 

This 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.

The 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). 

Point: The notion of level and its relevance to learning potential.
First, 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.

Point: The conjecture about curriculum learning. 
It 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?

Questions
Q1. Would different algorithms other than (PPO + GAE) make the results different from the current form? 

Q2: 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?

Q2. How about learning hyper-parameters on the fly? Both \beta and \rho might be adjusted throughout learning. 
Further, 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. 

Minor
Figure 1, there are two taus. The top would be \pi?
Background "We to refer to"
=======
I read through all the reviews and rebuttals and I could better understand and evaluate the paper. I updated my score to 7. 

Given 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).

One more comment about staleness.
I 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.

Some idea.
It 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).
review_title: review

final_score: rating: 6: Marginally above acceptance threshold
review_content: ##########################################################################

**Summary**:

This 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. 
##########################################################################

**Strengths**:

The method of the paper is simple and can be incorporated into many existing RL algorithms.

The paper shows that L1 value loss is a good scoring metric for the prioritization by comparing several different choices.


##########################################################################

**Weaknesses**:

The 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).


The 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.


While 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.

In 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?

In 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.


##########################################################################

**Minor points**:

Some 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.

review_title: Official Blind Review #2 

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