Grounding Aleatoric Uncertainty in Unsupervised Environment Design
Authors: Minqi Jiang
Michael D Dennis
Jack Parker-Holder
Andrei Lupu
Heinrich Kuttler
Edward Grefenstette
Tim Rocktäschel
Jakob Nicolaus Foerster
Venue: ICLR 2022 Submitted (2022)
Keywords: reinforcement learning
curriculum learning
generalization
environment design
procedural content generation

Abstract: In reinforcement learning (RL), adaptive curricula have proven highly effective for learning policies that generalize well under a wide variety of changes to the environment. Recently, the framework of Unsupervised Environment Design (UED) generalized notions of curricula for RL in terms of generating entire environments, leading to the development of new methods with robust minimax-regret properties. However, in partially-observable or stochastic settings (those featuring aleatoric uncertainty), optimal policies may depend on the ground-truth distribution over the aleatoric features of the environment. Such settings are potentially problematic for curriculum learning, which necessarily shifts the environment distribution used during training with respect to the fixed ground-truth distribution in the intended deployment environment. We formalize this phenomenon as curriculum-induced covariate shift, and describe how, when the distribution shift occurs over such aleatoric environment parameters, it can lead to learning suboptimal policies. We then propose a method which, given black box access to a simulator, corrects this resultant bias by aligning the advantage estimates to the ground-truth distribution over aleatoric parameters. This approach leads to a minimax-regret UED method, SAMPLR, with Bayes-optimal guarantees.

Under review as a conference paper at ICLR 2022
GROUNDING ALEATORIC UNCERTAINTY IN UNSUPERVISED ENVIRONMENT DESIGN
Anonymous authors Paper under double-blind review
ABSTRACT
In reinforcement learning (RL), adaptive curricula have proven highly effective for learning policies that generalize well under wide variety of changes the environment. Recently, the framework of Unsupervised Environment Design (UED) generalized notions of curricula for RI. in terms of generating entire environments, leading to the development of new methods with robust minimax- regret properties. However, in partially-observat featuring aleatoric uncertainty), optimal policies may depend on the ground- truth distribution over the aleatoric features of the environment. Such settings are potentially problematic for curriculum learning, which necessarily shifts the environment distribution used during training with respect to the fixed ground- truth distribution in the intended deployment environment. We formalize this phenomenon as curriculum- induced covariate shift, and describe how, when the distribution shift occurs over such alcatoric environment parameters, it can lead learning suboptimal policies. We then propose a method which, given black-box access to simulator, corrects this resultant bias by aligning the advantage estimates to the ground-truth distribution over aleatoric parameters. This approach leads to a minimax-regret UED method, SAMPLR, with Bayes-optimal guarantees.
or stochastic settings (those
INTRODUCTION
Adaptive curricula, which dynamically adjust the distribution of training environments to optimize the performance of the resulting policy, have played key role in many recent achievements in deep reinforcement learning (RI.). Applications have spanned both single-agent RI. (Portelas et al., 2020: Wang et al. 2019 (Zhong et al. 22200) Justesen et al.] 2018). where adaptation occurs over environment variations, and multi-agent RL (MARL), where adaptation can additionally occur over co-players (Silver et al. 2016 Vinyals et al. 2019 Stooke et al. 2021). By presenting the agent with challenges at the threshold of its abilities, such methods demonstrably improve the sample efficiency and the generality of the final policy (Matüisnn et al. 2017 Dennis et al. 2020 Diang et al.) a))
This work introduces a fundamental problem relevant to adaptive curriculum learning methods for RL, which call perriculum-induced covariate shift (CICS). Analogous the covariate shift that occurs in supervised learning (SL), CICS refers to a mismatch between the input distribution at training and test time, and this case, specifically when the distribution shift is caused by the selective sampling performed by an adaptive curriculum. While there may be cases in which CICS impacts model performance in SL, adaptive curricula for SL have generally not been found to be as impactful in RL (Wu et al. (02I). Therefore, here we focus on addressing this problem specifically as it arises in the RL setting, and leave investigation of its potential impact in SL future work.
To establish precise language around adaptive curricula, we cast our discussion under the lens of Unsupervised Environment Design (UED, Dennis al. 2020). UED provides a formal problem description for which curriculum learning is the solution, by defining the Underspecifted POMDP (UPOMDP; see Section 2). which expands the classic POMDP with a set of free parameters O representing the dimensions along which the environment may vary across episodes. The goal of UED is then to adapt distributions over e, so to maximize some objective, which could be tied to an RL agent's 's performance over this distribution. This allows us view adaptive curricula emerging via a multi-agent game between a teacher that proposes environments with parameters f ~ and a student that learns solve them. In addition to the notational clarity it provides, this formalism lends

---

Under review as a conference paper at ICLR 2022
Adoptive currioulum
Vou Visal
Sampled levels
V(ry V(Ta
SAMPUR (OBL)
Layset
Vhui Vi
Advartage
Figure 1: Adaptive curricula can result covariate shifts in environment parameters with respect to a fixed ground-truth distribution P(0) (see top path), e.g. whether apple banana is the correct fruit to choose per level. Here, the policy T (iT always chooses apple (banana). Our method, SAMPLR (bottom path) matches the advantages in sampled levels to the advantages observed sampling levels from P(0) (blue triangles), thus constraining the optimal policy under the curriculum distribution P(0) to match that under P(0).
the analysis of adaptive curricula to useful game theoretic constructs, such as Nash equilibria (NE, Nash et al. 1950).
This theoretc view has led to the development of curriculum methods with principled robustness guarantees, such PAIRED (Dennis al. 2020) and Prioritized Level Replay (PLR. Jiang et al. 2021a), which showed that curricula optimizing for the student's regret lead to minimax regret (Savage) [95I) policies at Nash equilibria, implying the agent can solve all solvable environments within the training domain. While other methods can also be cast in this framework, they do not hold the same desirable property at equilibrium. For this reason, we will focus on addressing CICS for pogret-maximizing UED, but note that our solution can be used with other UED methods.
To see how the CICS can be problematic, consider the simplified case of training a self-driving car in simulation, so it learns to take the fastest route from home to office. Suppose traffic data shows on 70% of the days, Route is faster than Route 2. Moreover, on any given day the self-driving car cannot infer which route is faster ahead of time, so always picking Route 1 is faster in expectation. To support training a policy using an adaptive curriculum, one could build a simulator which sets road conditions per episode based on a random day sampled from the traffic data. However, adaptive curriculum over the traffic settings may oversample days when Route is closed closed-perhaps because it finds the agent needs more practice Route 2 2-shifting the best choice to Route 2 in training. In fact, methods for minimax regret UED like PLR would keep shifting the distribution of fastest route, to maximize the agent's regret. Their curriculum dynamics would map to the zero-sum game of matching pennies, in which one player wins for guessing whether the other chose heads or tails; the NE corresponds each player randomly playing each option half the time. Randomly picking the route in this way is suboptimal, because in reality Route is faster in expectation. This example depicted in Figure [ where the two routes are replaced by an apple and banana.
If, on given day, the faster route could be identified before having to pick one, the agent could choose optimally. Instead, is an alcatoric parameter, inducing irreducible uncertainty the limit of infinite experiential data (Der Kiureghian & Ditlevsen 2009). When CICS occurs over such parameters, with respect to ground-truth distribution of environments P(0), the learned policy can be suboptimal with respect to P. It can therefore be useful to ground -that is, to constrain the aleatoric parameters O' C θ to P(0') when it is known or can be learned, as in simulation or from real-world data. However, grounding all 0 is undesirable, preventing the curriculum from sampling enough opportunities to learn from useful scenarios with low support under P(0).
In this work, we formalize the problem of CICS in RL, and provide a solution by proposing a UED method to find robustly Bayes-optimal policies where 0' is grounded to P(O'). Our solution called Sample-Maten Matched PLR (SAMPLR) extends PLR, a -fate-of-the-an UED algorithm, by constraining the advantage estimates match those observed if training under P(0'). This advantage correction adapts Off- Belief Learning Hu et al. 202I) from cooperative MARL, revealing an intriguing connection between curriculum biases observed in single and multi-agent RI. Our experiments in challenging
2

---

Under review as a conference paper at ICLR 2022
environments based the NetHack Learning Environment (NLE, Küttler et al. 2020) demonstrate that SAMPLR learns near-optimal policies under CICS, in cases where standard PLR fails.
BACKGROUND
2.1
UNSUPERVISED ENVIRONMENT DESIGN
The problem of Unsupervised Environment Design (UED, Dennis et al. (2020) is the problem of automatically generating an adaptive distribution of environments which will lead to policies that successfully transfer within target domain. The domain of possible environments is represented by an Underspecified POMDP (UPOMDP), which adds a set of free parameters to the standard definition of POMDP, along which each concrete instantiation, instance, these free parameters can be the position of obstacles in a maze, or friction coefficients in physics- based task. Formally a UPOMDP is defined as a tuple M (A, 1, S, T,S,TTT T. R, 7)- where A is set of actions, O is a set of observations, θ is set of free parameters, S is set of states, : S A x θ - (S) is transition function, I -> O is an observation (or inspection) function, R : 5 -> IR is reward function, and y is discount factor. UED typically approaches the curriculum design problem as training a teacher agent that co-evolves an adversarial curriculum for a student agent, for example, by maximizing the student's ' regret.
level, of the UPOMDP. For
We will focus on a recent UED algorithm called Robust Prioritized Level Replay (PLR+, Jiang et al., 2021b), which performs environment design via random search. PLR maintains buffer of the most useful levels for training, according to some learning potential score slorr--yppcallly based on regret approximation, such the positive value loss-and with probability p, actively samples the next training level from this level buffer instead of the ground-truth training distribution. This selpetive-sampling mechanism has been demonstrated to greatly improve sample-efficienyy and generalization in several domains, while provably leading to a minimax regret policy for the student NE. In maximizing regret, PLR curricula naturally avoid unsolvable levels, which have no regret.
2.2 OFF-BELIEF LEARNING
In cooperative MARL. self-play promotes the formation of cryptic conventions coaventions-aabitaaryy sequences of actions that allow agents to communicate information about the environment state. These conventions are learned jointly among all agents during training, but are arbitrary and hence, indecipherable to independently-traieee policies that fail to perform zero-shot coordination (ZSC, Hu et al. 2020), where independently- trained agents must cooperate successfully without additional learning steps, ad-hoc team play. lff-Belief Learning (OBL) resolves this problem by forcing agents to assume their co-players act according to fixed, known policy To until the current time f, and optimally afterwards, conditioned on this assumption. To is playing uniformly random, this removes the possibility of forming arbitrary conventions.
agents or humans at test time. Crucially, this leads to
Formally, let G be decentralized, partially-observable MDP (Dec-POMDP, Bernstein et al. 2002) with state s, joint action a, observation function (s) for each player i, and transition function T(s, a). Let the historical trajectory 7 = (81, @1 00, 11)) and the action-observation history (AOH) for agent be 7Z (I(ss), (s1))a,,...) a1, ...; 0r-1, (s.)). Further, let mo be an arbitrary policy, such as uniformly random policy, and Bx, (T|7") = P(r T To). belief model predicting the current state, conditioned on the AOH of agent and the assumption of co-players playing policy To until the current time i, and optimally according to n from & and beyond. OBL aims to find the policy m with the optimal, counter-factual value function.
7 (T*) = E EywB. (+)) [V (7)]
As the agent conditions its policy on the realized AOH r', while transition dynamics are based on states sampled from B, this mechanism is called a ficritious transition. In Section show how OBL's fictitious transition can be adapted to the single-agent curriculum learning setting to address CICS, by interpreting the eurriculum designer in UED co-player.
3

---

Under review as a conference paper at ICLR 2022
3 RELATED WORK
The mismatch between training and testing distributions of input features referred to as covariate shift, and has long served as a fundamental problem for the machine learning community. Covariate shifts have been extensively studied in supervised learning ( (Vapnik & Chervonenkis 1971 Huang
ee al. 2006; Bickel et al., 2009 Arjovsky et al. 2019). In RL. prior works have largely focused
on covariate shifts due to Training on off-policy data (Sutton et al., 2016 Rowland et al. 2020
Espeholt et al. 2018 Hallak & Mannor 2017 Gelada & Bellemare [019:] Thomas Brunskill
2016) including the important case of learning from demonstrations (Pomerleau) 1988) Ross &
Bagnell 2010). Recent work also aims to learn invariant representations robust to covariate shifts
(Zhang et 2019 (02T). More generally, CICS can be interpreted as kind of sample-selection bias (Heckman 1979). We believe this work to be the first to formalize and provide a solution to the problem of covariate shifts in reinforcement learning due to curriculum learning.
Our method fixes a critical flaw that can cause curricula to fail under CICS-an important problem as curricula have been shown to be essential for training RL agents across many of the most challenging domains, including combinatorial gridworlds (Zhong et al. 2020), Go (Silver et al.] (0166) StarCraft
(Vinyals et al. 2019), and achieving comprehensive task mastery open-ended environments (Stooke
eet all 2021). While this work focuses on PLR, other recent methods include minimax adversarial
curricula (Wang al. 2019; 2020) and curricula based changes in return (Matiisen al. 2017]
Portelas et al. 22200. Most similar to our work, OFFER (Ciosek & Whiteson] 2017) adapts curriculum over transition functions and uses importance sampling to correct for biased gradient estimates. Unlike this work, Ciosek & W Whiteson (2017) requires whitebox access to the transition function and does not directly study the impact of CICS on the learning dynamics. Curriculum methods have also been studied in goal coal-conditioned RL (Florensa et al.) 2018 Campero et al. 2021
Sukhhaatar et al. 2018 OpenAl et al. 202T), though CICS does not occur here as goals are observed by the agent. I Lastly, domain randomization (DR. DR.,ghhe & Levine 2017 Peng et al., 2017) can be seen as degenerate form of UED, though curriculum-baas based extensions of DR have also been studied (Jakobi 1997 Tobin et al. 2017).
Prior work has also investigated methods for learning Bayes optimal policies under uncertainty about the task (Zintgraf et al. 2020; Osband et al. 2013). based the framework of Bayes-adaptive MDPs (BAMDPs) (Bellman 1956 Duff, 2002). ). In this setting, the agent can adapt to an unknown MDP over several episodes by acting reduce its uncertainty about the identity of the MDP. In contrast, SAMPIR learns a robustly Bayes optimal policy for the case of zero-shot transfer. Further unlike these works, our setting assumes the distribution of certain aleatoric parameters are biased during training, which would lead to biased a posteriori uncertainty estimates with respect to the ground-truth distribution when optimizing for the BAMDP objective. Instead, SAMPLR proposes means to correct for this bias assuming knowledge of the true environment parameters for each level, to which we can safely assume access in curriculum learning.
CURRICULUM-INDUCCE COVARIATE SHIFT
As UED algorithms formulate curriculum learning as multi-agent game between teacher and student agents, we can formalize when CICS become problematic by considering the equilibrium point of this game: Let 0 be the environment parameters controlled by UED, P(0). the ground truth distribution of 0. and P(0), the curriculum distribution at equilibrium. Further, let T. be (0), a1....... 4t-1, or), the student agent's 's action-observation history (AOH) until time (though we will use simply when clear from context). The optimal action-vall value function Q' with respect to P(0) can then be expressed as a marginalization over 0:
(aallt))
ETe+1000
Σ Intu 1
Σ
P
(2)
at 1:00 wu
From Equation see that Q' (ax(TT) remains optimal under different values of P(0) at each time I as long as it is possible to infer 0 deterministically from 7,, implying that P(0'(7.) for some 0,
4

---

Under review as a conference paper at ICLR 2022
T1.
St
86+1
Tt
Tt
a2
A(s a.)
A(5 0s)
ag
Figure 2: A standard RT. transition (left) and the fictitious transition used by SAMPIR (right).
in which case the RHS of Equation 1 reduces to the LHS. If m() < 1 for all 6, then some subset C results in irreducible uncertainty at time t, thereby constituting aleatoric parameters. Letting Q" (ax Te)) be the optimal action-value function when P(0) is replaced with P(0) in Equation 2, we can then state that iarriculum-innuuce covariate shift results in suboptimal policies with respect to the ground truth distribution when
arg max Q" (alm:) * arg max Q' (alTr).
Moreover, this formulation highlights how this effect results from the presence of aleatoric parameters.
This description categorizes errors made by a policy trained on P evaluated on levels drawn from P(0) into two categories: The first type of error, which we call mistake, simply arises when P(0") 0 for some non-aleatoric 0" where P(0")= 0, i.e. the policy did not train trajectories needed to learn to behave optimally under some set of otherwise identifiable level parameters. This is distinct from the second kind of error, which call a misunderstandinn. and which corresponds to the problematic mismatch between training and test time distributions of specifically aleatoric parameters 0', so that P(O')= * P(O"), as we just previously characterized.
This taxonomy also clarifies errors in cooperative MARL,, where the co-players shape environment interactions, and thus play similar role to the UED teacher. Failures in ZSC can then be diagnosed as due to (i) mistake, because the co-players fail to generate trajectories that occur with test-time co-players; (ii), a misunderstanding. because the train-time co-players shift the training distribution of aleatoric parameters P(0'), which impacts the inference of ( = Ee, P(0') P((1(") needed for optimal cooperation for example, through the use of cryptic conventions. This view then connects generalization errors in cooperative MARL to those in single-agent RL, implying that methods like OBL devised to solve one type of error one of the settings may be adapted for the other. Indeed, we now describe our method, which does exactly this: By adapting OBI. to single-agent curriculum learning, we can ground the values P(0'(17) (T:) by forcing P(O')= = P(0'), thereby ensuring that the distribution of the alcatoric parameters at equilibrium is equivalent to their ground truth distribution.
5 SAMPLE-MATCHER PLR (SAMPLR)
We now describe how OBL's fictitious transition can be adapted for PLR L JJang et al. 202 aa to address CICS, resulting Cample-Matched PLR (SAMPLR). To avoid CICS, we must ground 6' to the ground-truth distribution P(0'), while allowing the remaining parameters in θ to vary under UED, so as to still benefit from a curriculum. To achieve this, we adapt the fictitious transition to single-agent curriculum learning by treating the UED teacher single action of choosing the level 8 at the start of each episode, and subsequently performs no-ops. Under this fictitious transition, we ground the teacher's choice of 0 such that the aleatoric parameters o' are assumed to he sampled from P(0).
co-player-one that performs the
Thus, each time f. the agent takes actions at based on its AOH usual, but estimates the advantage A(at, 8t) using fictitious transitions, which assume subsequent state transitions and rewards occur with e' fixed to 8 ~ P(O"), sampled at the start of the episode. More formally, the fictitious transition is performed si B(s (T, at a (.17), 8/m1 T(s', at), and r = R(s 1), where is the
5

---

Under review as a conference paper at ICLR 2022
Algorithm 1: Sample-Matched PLR (SAMPLR)
Randomly initialize policy T()), empty level buffer A of size K, and belief model ((s./r).
while not converged do
Sample replay-decision Bernoulli, d ~ (D(d)
if d 0 or |A 0 then
Sample level / from level generator
Collect rT's trajectory
6, with stop-gradient du
Use observed ground-truth states to update
else
Use PLR to sample a replay level from the level store, ~ A
Collect fictitious trajectory r' on 0, based on si ~ B
Update with rewards R(T')
end
Compute PLR score, S score(7', Update A with 0 using score S
end
AOH of the student. Figure summarizes this transition mechanism. Here, the belief model (+((T)) can be expressed as
=(slr)= P
This shows that, assuming blackbox simulator access, can generally implement B as follows: Periodically during training, we sample N trajectories, such that each is generated under level with 0' P(0'). We use these [=)]=== pairs to update posterior model P(0'(T) that predicts the underlying 8' given We then sample from B by first sampling 0 ~ P(0" (T), followed by stepping forward a parallel simulator that has been initially reset to the current AOH т, with fixed O' = 0', thereby yielding desired sample of 8, according to B.
In practice, it is often the case that l' can be uniquely identified by some revelatory event by time f, so that (() implement the fictitious transition by setting 0' P(O") the start of each episode; subsequent transitions will then be consistent with B. For example, in the fruit choice example, whether apple or banana was the right goal deterministically revealed by the final reward, and otherwise, does not impact transition dynamics. Additionally, we often only have limited access to P(0) throughout training. for example, if sampling P(O) is costly. In this case, can learn an estimate P(O") using the samples we do collect from P(0), which can oceur online. We then use P(0') in sampling fictitious transitions during UED. We refer to the resulting P(0') as a learned prior.
for some 0' and T, and P(s:|T,60 0') P(selT) otherwise. In this case, we can
SAMPLR, summarized in Algorithm | incorporates this fictitious transition by replacing the advantages of trajectories on replay levels sampled by PLR with their fictitious counterparts. as only these trajectories are used by PI.R- for training. To reduce the cost of sampling P(0"), we can use the new levels regularly sampled by PLR to estimate the learned belief prior P(0"), and use P(O") in sampling fictitious transitions replay levels.
6 GROUNDED POLICIES ARE ROBUSTLY BAYES OPTIMAL
We can view OBL-based correction as method for training policy to be optimal with respect to the ground-truth value function, with levels sampled from some generating distribution defined as:
V (T) E.- (7)
Note that when = P()) this reduces to the ground-truth value function notated simply as V(T). First, will note that, for any UED method, our OBL-based correction will ensure that, in equilibrium, the resulting policy is Bayes-optimal on the ground truth beliefs, on any trajectory sampled from (x), the distribution of trajectories of in levels sampled from A.

---

Under review as a conference paper at ICLR 2022
Remark I optimal with respect to the grounded value fanction V (T) then it is Bayes optimal with respect to the ground-truth parameter distribution P(0) on the support of M
Proof. By definition we have that и E arg max (V (T)} = arg max
[ (B
V (r)) Since
TEll
*Ell
л can condition on the initial trajectory т, the action selected after each trajectory can be independently
optimized. Thus we have, for T E (T), arg maxx("(( implying that a is the optimal
nEll
grounded policy and V
Thus, assuming the base RL algorithm finds Bayes optimal policies, UED method that optimizes the grounded value function, as done by SAMPLR, will result Bayes optimal performance over the ground-truth distribution. When the UED method aims maximize worst-case regret, can prove an even stronger property we call robust e-Bayes optimality.
Let V (T)) be the value function for evaluated on specific level 0. We will say that policy is robustly e-Bayes optimal iff for all in the domain of P(0) and for all x' we have
Note how this differs from being only e-Bayes optimal, which means for all n',
V(T) 2 V(T) c
With robust e-Bayes optimality, we must be e-optimal even on levels which are rarely sampled from the ground-trutt distribution. We will show that if SAMPLR is in an c-Nash Equilibrium, then policy is robustly e- e-Bayes optimal with respect to the grounded value function V(T)) rather than only e-Bayes optimal as one would expect from training directly on the true distribution of levels.
Theorem 1. If æ is e-Bayes optimal by V (TT) for A minimizing worst-case regret as is done in SAMPLR, then it is robustly e-Bayes optimal with respect to the grounded value function, V V(T)..
Proof. Let h be e-optimal with respect to V (T)) where A minimizing worst-case regret with respect to π. Let 7* be an optimal grounded policy, and let 0 be arbitrary. Then we have:
(T>
(T)
(
Se
(6)
Where the first inequality follows from minimizing worst-case regret with respect to æ, and the second follows from being c-optimal on A. Rearranging terms gives the desired condition. Li
EXPERIMENTS
We investigate the performance of SAMPLR with respect the the standard PLR and domain randomization in environments based on MiniHack (Samvelyan et al. 2021). library for creating custom environments based on the runtime of the NetHack Learning Environment (NLE) (Küttler al. 2020). Acting optimally in our environments requires grounding to the ground-truth distribution.
Our agents are trained using PPO (Schulman et al. 2017), using the best hyperparameters found via grid search, and use the policy architecture in Küttler et al. (2020). We tune the PL.R-seccffic hyperparameters shared among PLR and SAMPLR variants for each environment, based on the performance of P Full details of our environments, agent architecture, and hyperparameters are provided in Appendix A and our SAMPLR implementation, in Appendix B We compare both standard SAMPLR and variant called LP-SAMPLR that learns belief prior over the true goal, against PLR and standard PPO baselines. These baselines allows us to separate the relative changes in performance metrics due curriculum learning and our proposed correction for CICS.
7

---

Under review as a conference paper at ICLR 2022
DR
PLR
SAMPLR
LP-SAMPLR
q 0.7
Q= 0.5
Q 0.3
2.5
Mean lest return
6
Tist
Moan apisodic return
4-
Solved room count
2.0
3.
200M
200M
200M
1.0
Proparton apple
0
0.0
100M 200M
200M
200M 200M
Steps
Figure 4: Episodic returns (left) and numher of rooms in solved levels (middle) during training (dotted lines) and test on the ground-truth distribution (solid lines), for q 0.7. Normalized test returns and proportion of apple goals during training for various q are shown on the right. Plots show mean and standard error of 10 runs.
In our experiments, we first adapt the apple and banana example, depicted in Figure 3 into a fully procedurally -egeeraed RL environment set in the world of NetHack. For each level, the agent can only learn to choose optimally in expectation at test time by grounding to the distribution of correct choices in the deployment domain. Specifically, in each level, the agent must traverse between one to eight randomly generated rooms, and in the final room, the agent must choose to eat the apple or the banana. The correct choice is fixed for each level, but indiscernible to the agent. Thus, the identity of the true goal acts the aleatoric parameter. Figure 3 shows example levels from this environment.
This environment presents a hard exploration challenge for standard RL algorithms, as it requires learning to both navigate multiple rooms, well the NLE-specific skills of kicking doors and cating. The doors opening into adjacent rooms are locked. In order to go from one room to the next, the agent must learn to, potentially repeatedly, kick the locked door until it opens. Likewise, upon reaching a piece of fruit in the final room, the agent must learn to deliberately choose to eat the fruit. If the right choice of fruit were determinable per episode, we expect PLR- adaptive curriculum to improve learning by selectively sampling levels at the threshold of the agent's 's abilities.
Let TA be the policy in which the agent always chooses the apple. and hB. the banana. If the probability of the goal being apple P(A) q. the expected return of the agent is Raq under Ta and Rg (1 q) under πg. The optimal policy is then to act according to A when q > RB/ (Ra + RB), and according to To otherwise. We expect training under domain randomization, which samples each level completely distribution P(O), defined by the environment parameterization, would converge to the correct choice of T or и, assuming the environment is learnable by the choice of RL algorithm. In contrast, PLR evolves an adversarial curriculum, incentivizing PLR shift the distribution over goals throughout training. For example, PLR is incentivized to flip the curriculum distribution to favor cating apples whenever the agent begins consistently succeed at cating bananas. We thus expect the PLR curriculum to continually oscillate the preferred choice of goal.
RB/(RA=
random from the ground-truth
Levels from the stochastic fruit-choice environment. Across levels, the correct choice of fruit is distributed according to
Figure 3:
In our experiments, we set RA- = 3, Rg = 10, and in (0.7, 0.5, 0.3). making it always optimal to follow the banana-eating policy π but with the marginal benefit of doing so varying with g. We report train and test performance of each agent over 200M training steps in Figure 4 We find that DR struggles to learn an effective policy, plateauing at an expected return under 1. 1.0; PLR performs even worse, due to its adversarial curriculum shifting the distribution over the correct goal, leading to rapid oscillations in the optimal choice of fruit under the curriculum distribution, as visible in the high-variance oscillations in the proportion of apple goals selected by PLR for each value of in 4). This makes it difficult for the agent to settle on the optimal policy with respect to any ground-truth distribution. The proportion of each choice outcome, shown in Figure 55 reveals that both DR and PLR policies fail to eat any fruit most of the time, even after 200M training steps. In contrast, both SAMPLR and I. LP-SAMPLR realize marked improvement in test performance by grounding PLR's
8

---

Under review as a conference paper at ICLR 2022
PLR-
LP-SAMPLR
1.0
None
1.0
Apple
1.0
Banana
5.8
Proportinn selected
0.8
0.8
5.6
5.4
0.6
0.6
5.2
5.0
4.8
0.2
02
4.6
4.4
100M
200M
100M
200M
100M
200M
50M
100M
150M
200M
Steps
Figure 5: Left: Proportion of training episodes in which the agent fails to cat any fruit; eats the apple: or eats the banana. Right: Number of rooms in levels during training. Plots show mean and standard error of 10 runs.
DR
SAMPLR
LP-SAMPLR
0.25
Miai text aptcode reburn
0.20
Proporton Inreproot
0.8
0.15
0.3
0.10
0.0
60M
100M
150M
100M
Steps
Figure 6: Left: Levels from FireDungoon Middle: Test return on the ground ground-truth distribution of FireDungoon. Right: Proportion of training levels with fireproof armor. Plots show and standard error of 10 runs.
otherwise wild shifts in Figure 4 shows this improvement is most pronounced when the expected difference in π and T smaller, and therefore easier for PLR flip the agent's policy. Moreover, we see in Figure 5haat that both SAMPLR methods present levels with higher room counts on average, indicating that early training, it able discover easier, few-room levels in which the agent can capture reward signal, and which can then be made more complex to push the agent along its threshold of abilities.
We next turn to more challenging environment that introduces additional NetHack- dynamics. The FireDungeon environment (see Figure example levels), requires the agent to navigate through up to 13 chambers, and ultimately choose between chamber A or B, each containing valid goal. Reaching this goal ends the episode and provides the agent with a sparse reward. Further, in this penultimate chamber, there is armor, which if worn grants the agent with fire resistance with probability q. Chamber B is marked by a red gemstone by the door and contains enemy units, whose fire attack will instantly kill the agent. Killing each enemy grants the agent with +1 final reward, which is only provided upon reaching either goal. The agent thus stands to attain a higher reward by attacking the enemies in Chamber B. before reaching the goal, only if the armor fireproof. This environment presents an even more difficult exploration problem for the agent, yet we see in Figure both SAMPLR variants begin to learn to solve this environment with significantly greater sample-efficiency than DR, while PLR again struggles to learn. As in the case of the previous stochastic choice environment, we see that PLR rapidly oscillates the key alcatoric parameter, which in this case, determines whether the armor is fireproof.
8 CONCLUSION
Using the formal notions of environment parameterizations in the framework of UED, we defined the problem of curriculmm-inuueed covariate shift in RL. Our definition highlights the issues that can arise when there is persisitent uncertainty over the environment parameters, either because the uncertainty is irreducible or because reducing the uncertainty is costly. We then adapted fictitious transition mechanism previously used to improve zero-shot coordination in cooperative MARL to correct for this covariate shift. We demonstrated that our resulting algorithm, SAMPLR, avoids the pitfalls of this type of covariate shift, while preserving the benefits of curriculum learning.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Martín Arjovsky, Léon Bottou, Ishaan Guirajani, and David Lopez-Paz. Invariant risk minimization. CoRR, abs/1907. 0009930 2019. URL htt.tbttp///iii/// wwwpexiv......veooooo.oe abgg/bb/// hbss/901 02893
Richard Bellman. A problem in the sequential design of experiments. Sankhyā: The Indian Journal of Statistics (1933-/900 (993), (6(3/4):221-23) 1956.
Daniel S Bernstein, Robert Givan, Neil Immerman, and Shlomo Zilberstein. The complexity of decentralized control of markov decision processes. Mathematics of operations research, 27(4): 819-840, 2002.
Steffen Bickel, Michael Brückner, and Tobias Scheffer. Discriminative learning under covariate shift. J. Mach. Learn, Res., 10:2137-2155, 2009. httthhtt://aal. acm. owg.or/////o..oooo.ooooo.o arg/ciiaiion. cfm?
1d=1755858
Andres Campero, Roberta Raileanu, Heinrich Kuttler, Joshua B. Tenenbaum, Tim Rocktäschel, and Edward Grefenstette. Learning with AMIGo: Adversarially motivated intrinsic goals. In International Conference on Learning Representations, 2021.
Kamil Andrzej Ciosek and Shimon Whiteson. OFFER: off-environment reinforcement learning, In Satinder P. Singh and Shaul Markovitch (eds.), Proceedings of the Thirty- Firrt--Frrttta AAAI Conference on Artificial Intelligence, February 4-9, 2017, San Francisco, California. USA, pp. 1819-1825. AAAI Press, 2017. OtLhtto:// org. ocs index. php/ AAAI AAA.AAAAAA/... AAAA///AA11/ppaprr
vi view/14378
Michael Dennis, Natasha Jaques, Eugene Vinitsky, Alexandre Bayen, Stuart Russell, Andrew Critch, and Sergey Levine. Emergent complexity and zero-shot transfer via unsupervised environment design. In Advances in Neural Information Processing Systems, volume 33, 2020.
Armen Der Kiureghian and Ove Ditlevsen. Aleatory or epistemic? does it matter? Structural safety, 31(2):005-112, 2009.
Michael O'Gordon Duff. Optimal Learning: Computational procedures for Bayes-adaptive Markov decision processes. University of Massachusetts Amherst, 2002.
Lasse Espeholt, Hubert Soyer, Remi Munos, Karen Simonyan. Vlad Mnih, Tom Ward, Yotam Doron, Vlad Firoiu, Tim Harley, lain Dunning, Shane Legg, and Koray Kavukcuoglu. IMPALA: Scalable distributed deep-RL with importance weighted actor-learner architectures. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning. volume 80 of Proceedings of Machine Learning Research, pp. 1407-1416. PMIR, 10-15 Jul 2018.
Carlos Florensa, David Held, Xinyang Geng, and Pieter Abbeel. Automatic goal generation for reinforcement learning agents. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning. volume 80 of Proceedings of Machine Learning Research, pp. 1515-1528, PMLR, 10-15 Jul 2018. URL htll:tt:/ppoceeeninng
mlr. wwwpppeesssee.... v80 https///////oooeesslseeee html
Carles Gelada and Mare G. Bellemare. Off-policy deep reinforcement learning by bootstrapping the covariate shift. In The Thirty-Third AAAI Conference Artificial Intelligence, AAAI 2019, The Thirty-First Innovative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium Hawaii, USA, Jamuary 27 February 2019, pp. 7/doi Pooi.org/10 10. 609 /aa9//aaa... v331 01 3301363333 367
Educational Advances in Artificial Intelligence, EAAI 2019, Honolulu, AAAI Press, 2019. (tthttss
Assaf Hallak and Shie Mannor. Consistent on-line off off-policy evaluation. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 1372-1383. PMLR, 06-11 Aug ml wttps/mmm..p...eemmmmmmmmmmm 11alkkak ak 7a html
2017. URL URL
James J Heckman. Sample selection bias as a specification error. Econometrica: Journal of the econometric society, pp. 153-161, 1979.
10

---

Under review as a conference paper at ICLR 2022
Hengyuan Hu, Adam Lerer, Alex Peysakhovich, and Jakob Foerster. "Other-play" for zero-shot coordination. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 4399 4319--441. PMIR, 13-18 Jul 2020. U wtw..httss:///o hatttps:/pprceeet ngs ..m.s.m... . www.m...r........mmmmmm.mm..
hu20a. h
Hengyuan Hu, Adam Lerer, Brandon Cui, Luis Pineda, Noam Brown, and Jakob N. Foerster. Off- belief learning. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International
Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pp. 4369 4379. PMLR, 2021. URL http: //proceedings.u mil.mmmirs press
Jiayuan Huang, Arthur Gretton, Karsten Borgwardt, Bernhard Schölkopf, and Alex Smola. Correcting sample selection bias by unlabeled data. Advances in neural information processing systems, 19: 601-608, 2006.
Nick Jakobi. Evolutionary robotics and the radical envelope-of-noise hypothesis. Adaptive Behavior, 6(2):325-368, 1997.
Minqi Jiang, Michael Dennis, Jack Parker-Holder Jakob Foerster, Edward Grefenstette, and Tim Rocktäschel. Replay guided adversarial environment design. arXiv, 2021a.
Minqi Jiang, Edward Grefenstette, and Tim Rocktäschel. Prioritized level replay. In Proceedings of the 38th International Conference on Machine Learning. ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pp. URL httphht:pppppcceeeeiiiee
PMLR, 2021b.
m wtt..........///////a//.2222
html
Niels Justesen, Ruben Rodriguez Torrado, Philip Bontrager, Ahmed Khalifa, Julian Togelius, and Sebastian Risi. Procedural level generation improves generality of deep reinforcement learning. CoRR, abs/ (0s//900..1072, 2018. Utthttp::/// www.a.xxiii.......a wwtp:/i..rr//.o... 1806 10729
Heinrich Küttler, Nantas Nardelli, Alexander Miller, Roberta Raileanu, Marco Selvatici, Edward Grefenstette, and Tim Rocktäschel. The NetHack Learning Environment. In Proceedings of the Conference on Neural Information Processing Systems (NeurIPS), 2020.
Tambet Matiisn, Avital Oliver, Taco Cohen, and John Schulman. Teacher-studens curriculum learning. IEEE Transactions on Neural Networks and Learning Systems, PP, 07 2017.
John F Nash et al. Equilibrium points in n-person games. Proceedings of the national academy of sciences, 36( 49,) 1950.
OpenAI OpenAI, Matthias Plappert, Raul Sampedro, Tao Xu, Ilge Akkaya, Vineet Kosaraju, Peter Welinder, Ruben D' D'Sa, Arthur Petron, Henrique Ponde de Oliveira Pinto, Alex Paino, Hyeonwoo Noh, Lilian Weng, Qiming Yuan, Casey Chu, and Wojeiech Zaremba. Asymmetric self-play for automatic goal discovery in robotic manipulation, 2021.
lan Osband, Daniel Russo, and Benjamin Van Roy. (more) efficient reinforcement learning via posterior sampling. In Christopher J. C. Burges, Léon Bottou, Zoubin Ghahramani, and Kilian Q. Weinberger (eds.), Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of meeting held December 5-8, 2013, Lake Tahoe, Nevada, United States, pp. 3003-3011, 2013. URL https::/procceed//e neurips wt.pc//paaa htc/paperr2213/hasll html
Xue Bin Peng. Marcin Andrychowicz, Wojciech Zaremba, and Pieter Abbeel. Sim-to-real transfer of robotic control with dynamics randomization. CoRR, abs/1710.06537, 2017.
Dean Pomerleau. ALVINN: an autonomous land vehicle in a neural network. In David S. Touretzky (ed.), Advances in Neural Information Processing Systems I, [NIPS Conference, Denver, Colorado,
USA, 1988], pp. 305-313, Morgan Kaufmann, 1988. URL http: www.serrr.iii.oooooo.om paper/95-al nn an htt.

---

Under review as a conference paper at ICLR 2022
Rémy Portelas, Cédric Colas, Katja Hofmann, and Pierre- Yves Oudeyer. Teacher algorithms for curriculum learning of deep rl in continuously parameterized environments. In Leslie Pack Kaelbling, Danica Kragic, and Komei Sugiura (eds.), Proceedings of the Conference on Robot Learning, volume 100 Proceedings of Machine Learning Research, pp. 835-853. PMIR 30 Oct- 01 Nov 2020. httpttss::///// http:::::///occeedeeeee ngs. ml www.ssppppe//esee wtt..pppeess//o00ppptteeeeeeeeee
html
Stephane Ross and Drew Bagnell. Efficient reductions for imitation learning. In Yee Whye Teh and Mike Titterington (eds.), Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, volume 9 of Proceedings of Machine Learning Research, pp. 661-668.
Chia Laguna Resort, Sardinia, Italy, 13-15 May 2010. PMLR. URL https::: httpp::s///prrreeiiggg m wwwps/sweee/.ppp.ppp wttps///v/rossll0e rossl 0a httll
Mark Rowland, Will Dabney, and Remi Munos. Adaptive trade-offs in off- off-policy learning. In Silvia Chiappa and Roberto Calandra (eds.), Proceedings of the Twenty Third International Conference Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pp. 34 44. PMLR, 26-28 Aug 2020. URL
ngs ml prwss/v108 08/
Fowland22 html
Fereshteh Sadeghi and Sergey Levine. CAD2RL: real single-image flight without a single real image. In Nancy M. Amato, Siddhartha S. Srinivasa, Nora Ayanian, and Scott Kuindersma (eds.), Robotics: Science and Systems XIII, Massachusetts Institute of Technology. Cambridge, Massachusetts, USA, July 12-16, 2017.
Mikayel Samvelyan, Robert Kirk, Vitaly Kurin, Jack Parker-Holder, Minqi Jiang. Eric Hambro, Fabio Petroni, Heinrich Kuttler, Edward Grefenstette, and Tim Rocktäschel. Minihack the planet: A sandbox for open-ended reinforcement learning research. In Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2021.
Leonard J Savage. The theory of statistical decision. Journal of the American Statistical association, 46(253):55-61 67, 1951.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov, Proximal policy optimization algorithms, 2017
David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George van den Driessche, Julian Schritwieser,, Ioannis Antonoglou, Vedavyas Panneershelvam, Marc Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy P. Lillicrap, Madeleine Leach, Koray Kavukeuoglu, Thore Graepel, and Demis Hassabis. Mastering the game of go with deep neural networks and tree search. Nat., 529(7587):484488, 2016. URL fittps://det .org 10. 1038/natttueneeeee 6961
Adam Stooke, Anuj Mahajan, Catarina Barros, Charlie Deck, Jakob Bauer, Jakub Sygnowski, Maja Trebacz, Max Jaderberg, Michaël Mathieu, Nat McAleese, Nathalie Bradley-Schmieg, Nathaniel Wong, Nicolas Porcel, Roberta Raileanu, Steph Hughes-Fitt, Valentin Dalibard, and Wojciech Marian Czameekk.. Open-ended learning leads to generally capable agents. CoRR, abs/2107.12808, 2021. URL
12808
Sainbayar Sukhbaatar, Zeming Lin, Ilya Kostrikov, Gabriel Synnaeve, Arthur Szlam, and Rob Fergus. Intrinsic motivation and automatic curricula via asymmetric self-play. In International Conference on Learning Representations, 2018 URL htttps://openzeviers net net//orumm
(d-skkTyg-- R2
Richard S. Sutton, A. Rupam Mahmood, and Martha White. An emphatic approach to the problem of off- temporal-difffeence learning. Journal of Machine Learning Research, 17(73):1-29,
2016. URL htt.::/:///.ll..ooorrp////////// 1881111111418111111 html
Philip Thomas and Emma Brunskill. Data-efficient off- ool-po policy evaluation for reinforcement learning. In Maria Florina Balcan and Kilian Q. Weinberger (eds.), Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pp. 2139-2148, New York, New York, USA, 20-22 Jun 2016. PMLR.
12

---

Under review as a conference paper at ICLR 2022
Josh Tobin, Rachel Fong, Alex Ray, Jonas Schneider, Wojeiech Zaremba, and Pieter Abbeel. Domain randomization for transferring deep neural networks from simulation to the real world. In 2017 IEEE/RSJ International Conference Intelligent Robots and Systems, IROS 2017, Vancouver, BC, Canada, September 24-28, 2017, pp. 23-30. IEFE, 2017.
Vladimir N Vapnik and A Ya Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilitiess. Theory of Probability and Its Applications, pp. 264-280, 1971.
Oriol Vinyals, Igor Babuschkin, Wojciech M. Czarnecki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung, David H. Choi, Richard Powell, Timo Ewalds, Petko Georgiev, Junhyuk Oh, Dan Horgan, Manuel Kroiss, Ivo Danihelka, Aja Huang. Laurent Sifre, Trevor Cai, John P. Agapiou, Max Jaderberg, Alexander Sasha Vezhnevets, Rémi Leblond, Tobias Pohlen, Valentin Dalibard, David Budden, Yury Sulsky, James Molloy, Tom L. Paine, Çaglar Gülçehre, Ziyu Wang, Tobias Pfaff, Yuhuai Wu, Roman Ring. Dani Yogatama, Dario Wünsch, Katrina McKinney, Oliver Smith, Tom Schaul, Timothy P. Lillicrap, Koray Kavukcuoglu, Demis Hassabis, Chris Apps, and David Silver. Grandmaster level in starcraft II using multi-agent reinforcement learning. Nat. 575(7882): 350-354, 2019. doi: 10. 10.1038/441886-1991111
URL https: https://doi..org/0...
s41586 019-8---199-72--2
Rui Wang. Joel Lehman, Jeff Clune, and Kenneth O. Stanley. Paired open-ended trailblazer (POET): endlessly generating increasingly complex and diverse learning environments and their solutions. CoRR, abs/1901.01753, 2019.
Rui Wang, Joel Lehman, Aditya Rawal, Jiale Zhi, Yulun Li, Jeffrey Clune, and Kenneth Stanley. Enhanced POET: Open-ended reinforcement learning through unbounded invention of learning challenges and their solutions. Proceedings of the 37th International Conference on Machine Learning, pp. 9940-9951, 2020.
Xiaoxia Wu, Ethan Dyer, and Behnam Neyshabur. When do curricula work? In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021.
Amy Zhang, Zachary C. Lipton, Luis Pineda, Kamyar Azizzadenesheli, Anima Anandkumar, Laurent Itti, Joelle Pineau, and Tommaso Furlanello. Leaming causal state representations of partially observable environments. CoRR, abs/1906. 10437, 2019. URL http:ttt://axiiiorrggg/
10437
Amy Zhang, Rowan Thomas McAllister, Roberto Calandra, Yarin Gal, and Sergey Levine. Learning invariant representations for reinforcement learning without reconstruction. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021.
2FWDEEEREE CWDKRREU
Victor Zhong, Tim Rocktäschel, and Edward Grefenstette. RTFM: generalising to new environment dynamics via reading. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL https://
Luisa M. Zintgraf. Kyriacos Shiarlis, Maximilian Igl, Sebastian Schulze, Yarin Gal, Katja Hofmann, and Shimon Whiteson. Varibad: A very good method for bayes-adaptive deep RL via meta-learning In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL htttp::///ppeeeeeeeeeeepe Hk 9J1BYvr
net / forum?id=
13


Reviews:
[{"review_id": "RacGuMgfKOf", "reviewer": "Reviewer_AAp9", "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": "**Strengths:**\n\nThis work delivers what is promised experimentally. It tests the algorithm on NetHack and MiniHack and demonstrates that the proposed algorithm reduces the gap between training and test time evaluation.\n\n**Weaknesses:**\n\nThere are a several issues with the clarity. I've expanded those comments in the clarity section of the review.\n\n**Detailed Comments:**\n\nC1: In figure 1 text you say ground-truth distribution $P(\\theta)$ where in the main text you use $\\bar{P}(\\theta)$ for the ground-truth. I assume that the ground-truth is notated as $\\bar{P}$, can you verify that this is correct and fix the figure 1?\n\nC2: The belief is $P(\\tau_t \\bar \\tau^i_t, \\theta)$. What is $\\tau_t$ since $\\tau$ is $(s1, a1, s2, a2, \\dots)$? Is the subscript index the state only? I know that this is inherited by off belief work but would be good to clarify the notation.\n\nC3: What is the difference between $\\bar{Q}$ and $Q$?\n\nC4: \"If $\\bar{P}(\\theta \\dots)<1$ .. then some $\\theta'$ result in irreducible uncertainty\". Let's examine an example. Say we have $\\theta_1$, $\\theta_2$ and $\\theta_3$. Say we have a trajectory $\\tau$ for which the transitions and emissions where the same for all three environments but in the future all three environments end up in different states. Therefore, $\\bar{P}(\\theta \\bar \\tau_t)<1$ (since we can't tell which one of the parameters is for sure). Your claim is that this is aleatoric uncertainty however, you'll be able to reduce such uncertainty if you progress in the environment and acquire more evidence. \n\nC5: You say \"we see that $\\bar{Q}*$ remains optimal ... as long as $\\bar{P}(\\theta' \\bar \\tau_t) = 1$\" - Can you explain why is this the case? I can't see why you rely on $\\bar{P}(\\theta' \\bar \\tau_t)=1$ for the optimality argument.\n\nC6: Shouldn't \"if d = 0 then\" be \"if d = 0 or $\\Lambda$ is empty\" in algorithm 1?\n\nC7: You say $\\lambda=\\bar{P}(\\theta)$. Is $\\Lambda$ a distribution or a parameter? Also what is $M^\\Lambda$? Is it the simulator where you sample parameters from the distribution $\\Lambda$? Is it fair to say that in the expectation in eq 5) you sample a $\\theta \\sim \\Lambda$ and then play $\\pi$ in the environment parametrized by $\\theta$ and gather the trajectory $\\tau$?\n\nC8: Related to C7 but at some point you say $\\bar{V}^\\theta$ which confuses me. Is this an expectation like $\\bar{V}^\\Lambda$ ?\n\nC9: In the experiments, can you clarify how many seeds were run and what's the shaded area means?\n\n\nC10: Related work: [https://www.aaai.org/ocs/index.php/AAAI/AAAI17/paper/viewPaper/14378](https://www.aaai.org/ocs/index.php/AAAI/AAAI17/paper/viewPaper/14378) - this work is using importance sampling to fix the bias of sampling rare environments", "summary_of_the_paper": "This work proposes a solution to the problem of covariate shift appeared in adaptive curriculum learning where the distribution of parameters of the environment at test time is different from the one at training time. This is caused in algorithms like PAIRED or PLR because the adaptive curriculum learning algorithm biases towards regret maximising environments and as such trains the learner on a biased distribution instead of the ground truth one. The authors propose a solution to the problem under the assumption that the designer knows the ground truth distribution of the parameters of the environment. The solution relies on using fictitious transitions to compute the value function, using Off Belief learning — an algorithm for cooperative MARL.", "summary_of_the_review": "I'm suggesting marginal below acceptance threshold because I find certain parts of the paper unclear. The experiments support the argument of the paper which is great however I'd like to understand and see the paper improved in a few aspects:\n- Understand if the notion of aleatoric parameters is the correct one here. See C4\n- Understand C6 and C7 better in order to follow the complete argument and the proofs.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "5wXcDbGo3WH", "reviewer": "Reviewer_R1Z8", "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": "Strengths:\n\n- This paper studies unsupervised environment design which is an intriguing and important problem to facilitate reinforcement learning with minimum human intervention. \n\n- The proposed method consistently outperforms TLR and DR baselines in two discrete space task domains.\n\nWeaknesses: \n\n- The problem formulation does not seem to be entirely convincing to me. In this paper, an inference model $\\bar{P}(\\theta | \\tau)$ is trained with the policy to predict the environment parameter $\\theta$ given $\\tau$. Given this belief model, why do the authors still stick to a Q value function as a marginalization over θ in Eqn. 2 instead of using $\\bar{P}(\\theta | \\tau)$ to conduct online system identification and learns a policy $\\pi(a | s, \\theta)$ conditioned on the inferred $\\theta$? Wouldn't that lead to better performance?\n\n- The definition of the belief model in Eqn. 4 does not seem to be correct. Based on the Bayes' theorem, the RHS is supposed to be $\\sum_{\\theta'} \\bar{P}(s_t | \\tau, \\theta') \\bar{P}(\\theta' | \\tau)$. The marginalization is missing here. \n\n- Several definitions are missing, which makes the paper hard to read. For example, how is $\\mathcal{M}^{\\Lambda}(\\pi)$ defined? In Sec.2, $\\mathcal{M}$ is defined as the tuple of UPOMDP but in Sec. 6 it seems to become a probability distribution. The definition of $\\bar{Q}^*_{\\bar{P}}(a_t | \\tau_t, \\theta)$ is also missing.\n\n- Could the authors provide more discussions on how the fictitious trajectories help mitigate the curriculum-induced covariate shift? I do not think the explanation is sufficiently convincing in the current draft.\n\n- The experiment setups seem to be a bit too simple. As shown in Figure 3 and Figure 6, the different goals are always placed next to each other in the same room. And there is no penalization for reaching the wrong goal. Therefore, the policies for solving different $\\theta$ will only have minor differences. Specifically, the policy only needs to distinguish the goals in the last 1-2 steps, but the actions before that will be exactly the same. As a result, the learned Q value functions will be insensitive to the changes of $\\theta$ except for the final state. Without evaluating the proposed method in a more challenging setup (e.g. different goals placed in different rooms, and negative rewards for reaching the wrong goal), it would be hard to justify the effectiveness of the proposed method. \n\n- Although the authors claim that the proposed method generates curricula to facilitate the training of the policy, there is no quantitative or qualitative results that demonstrate what kind of curricula are generated. It would be better to include an analysis of how $\\theta$ evolves during training and how it facilitates the training. ", "summary_of_the_paper": "This paper aim at generating curricula for training an RL agent to solve tasks sampled from an unknown distribution. Based on Prioritized Level Replay and Off-Belief Learning, an algorithm is proposed to train the policy using trajectories sampled from a learned belief model. The proposed method is evaluated in two goal-reaching tasks of discrete state and action spaces.", "summary_of_the_review": "Although the paper tackles an important problem, the proposed technical solutions do not seem to be entirely convincing and the experiments are insufficient. I believe this paper needs another iteration before being ready for publication. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "3nxSe7OiZe0", "reviewer": "Reviewer_ZRvM", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "1. I am not sure what the \"unsupervised environment design\" in the title has got to do with the paper. The proposed method only selects/corrects for a distribution over a known set of environments. \n\n2. I am really confused about what is the formal problem statement that the method is trying to solve, and what are the assumptions and properties available to the agent. Having a clear formal statement with assumptions after the introduction could be really helpful.\n\n3. Since the method builds so heavily upon the previous work on PLR, it is worth including a summary of it in the background.\n\n4. What do super-scripts of $\\mathcal M$ in the POMDP tuple stand for? They are not used anywhere else again.\n\n5. Why is the observation function assumed to deterministically map states to observations? Why is reward only a function of state, and not (s,a,s')? How do these choices impact the method?\n\n6. In the definition of $\\mathcal B$, it seems like $\\tau_t$ is used as both the trajectory till step $t$ and the state in $\\tau$ at step $t$. I am not sure how to interpret this.\n\n7. In eqn 1, what does it mean to have $\\pi_0 \\rightarrow \\pi_1$ in superscript? I don't see this notation being used like this anywhere else in the paper. \n\n8. The paper introduces again introduces a new terminology and additional discussions on _mistake_ vs _misunderstanding_, but does not really use it again after. Further, I don't really see the difference, _mistake_ seems to be a sub-problem resulting due to _misunderstanding_, resulting from distribution mismatch where supports are not overlapping.\n\n9. Paper uses \"grounding X\" everywhere, where X is some parameter. I am not sure what the authors mean by that. \n\n10. One of the biggest drawbacks of the work is the assumption about access to the simulator. To perform the off-belief learning, the simulator is used in parallel to sample the next state transition under the true distribution of POMDP parameters instead of the distribution induced by the curriculum learning procedure.\n - a) The entire point of model-free methods is to not rely upon access to the simulator and just work with the data.\n - b) If the simulator/model is assumed to be known and accurate, then the comparisons should be made with other methods that leverage the simulator access as much as possible.\n- c) Even when the simulator is known, how tractable is it to reset to a state corresponding to a particular trajectory's history under a different parameters of the POMDP, specifically when transition dynamics are stochastic? That is, how do you bring the parallel stochastic simulation to a state that corresponds exactly to observing that specific history?\n\n11. It is later mentioned that \"in practice, it is often the case the environment dynamics are uniquely determined by $\\theta'$\", and it is discussed how this can be exploited. However,  in this case, isn't the main motivation for aleatoric uncertainty as developed in eqn (2) and (3) non-existent?\n\n12. Entire section 6 on Bayes optimality seems very uninformative. The arguments presented are only good for the tabular setting, which is probably not where one would be using curriculum learning or seeing the aleatoric uncertainly problem in practice. With function approximations you will need to additionally constrain policy comparison to policies with the function class, talk about optimality gap between the best policy in your class and $\\pi^*$, and also discuss why it is reasonable to think that the proposed method will converge to $\\epsilon$-Nash Equilibrium when using these function approximations.\n\n13. While in the ideal setting the proposed method can address the covariate shift in the return _given_ a state, I am not sure how the distirbution shift in observing the specific states itself impacts the test performance. This is not a problem in tabular because states are not aliased, but in the function approximation setting the states that are visited often will tend to have a better policy as compared to the states which are visited less frequently. But if these less frequently visited states tend to get visited more frequently during test time, then there might be problems.\n", "summary_of_the_paper": "Paper proposes a method to fix the covariate shift issue induced by curriculum learning RL methods when dealing with parameterized POMDPs. Specifically, curriculum learning methods choose a training distribution over the parameters of the POMDPs that might differ from the distribution that the agent might face during test-time, therefore the optimal solution under the distribution induced by the curriculum method might not be optimal under the test-time distribution. To fix this problem, the paper assumes access to the simulator such that given any previous trajectory the next state can be sampled under the true/test distribution, which is then used to update the policy. ", "summary_of_the_review": "I think the paper falls short because of strong assumptions made by the proposed method on simulators, uninformative theory, and poor presentation of the problem being addressed.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "1tVThwJCDY8", "reviewer": "Reviewer_UQqT", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "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": "The problem here appears to be that an adversarial curriculum approach is allowed to modify a stochastic parameter that is not observable at run-time by the agent, but drastically changes the optimal policy. I had difficulty understanding the authors' approach, which at first glance appears very complicated but somehow reduces to something extremely simple in their experiments. This might be due to their choice of rather simple 2D grid-world type environments. I believe they may be correct in identifying a problem in this type of approach, but I am not sure that this is novel.\n\nI have some concerns with this paper:\n- Adversarial curriculum learning over a parameter that completely changes the optimal policy seems like an obviously bad thing. The (Dennis et al, 2020) paper you cite even mentions in the abstract that minimax often leads to unsolvable environments. Can you not just exclude these manually?\n\n- Their approach is introduced in sec 2.2 by analogy to \"cryptic conventions\" in cooperative MARL, which is unfortunately not very intuitive unless you have a background in this subject. Reading this, I am not sure this connection is needed or helpful. \n\n- \"In practice, it is often the case that environment dynamics are uniquely determined by θ′ so that\nP(θ′|τ) = 1\" - EDIT for clarity: The math indicates you mean there other way around - that the curriculum parameter can be uniquely determined by the trajectory. This might be correct in your simple fruit environment, but seems like a questionable assumption in general? One could move a box in the environment that does not impact the policy, or if you have random elements in the agent actions, noise in agent transitions, or observations, you might get similar trajectories using very different curriculum parameters. This will also complicate the modelling you make when learning \\bar{P}(theta|tau), in the general case it seems like you might need a more complex density estimator than e.g. a regular Guassian model.\n\n- The experiments use very simple environments. As I understand it, there is only one curriculum parameter in the fruit world?\n\nMinor:\ntypo: \"persisitent\"", "summary_of_the_paper": "The authors consider the problem of covariate shift in recent adaptive curriculum learning methods. They propose to address this by changing how the adversarial approach interacts with aleatoric (stochastic) parameters and demonstrate it on two 2D grid environments.\n", "summary_of_the_review": "While automated curriculum learning is an important topic, the purported problem they are attacking seems a bit too obvious. I am not sure how novel this is, and their solution appears needlessly confusing and demonstrated only on toy examples.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper tackles the problem of covariate shift in adaptive curriculum learning.  Unfortunately, the paper lacks clarity and the experiments are insufficient.  The author response clarified the notation and corrected many typos, however, the paper remains conceptually unclear as pointed out by the reviewers.  Hence this work is not ready for publication.
Decision: Reject