Year: 2021

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 minimaxregret properties. However, in partially-observable or stochastic settings (those featuring aleatoric uncertainty), optimal policies may depend on the groundtruth 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 groundtruth 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.

heading: 1 INTRODUCTION
text: Adaptive curricula, which dynamically adjust the distribution of training environments to optimize the performance of the resulting policy, have played a key role in many recent achievements in deep reinforcement learning (RL). Applications have spanned both single-agent RL (Portelas et al., 2020; Wang et al., 2019; Zhong et al., 2020; 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 (Matiisen et al., 2017; Dennis et al., 2020; Jiang et al., 2021b;a).
This work introduces a fundamental problem relevant to adaptive curriculum learning methods for RL, which we call curriculum-induced covariate shift (CICS). Analogous to the covariate shift that occurs in supervised learning (SL), CICS refers to a mismatch between the input distribution at training and test time, and in 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 as in RL (Wu et al., 2021). 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 to future work.
To establish precise language around adaptive curricula, we cast our discussion under the lens of Unsupervised Environment Design (UED, Dennis et al., 2020). UED provides a formal problem description for which curriculum learning is the solution, by defining the Underspecified POMDP (UPOMDP; see Section 2), which expands the classic POMDP with a set of free parameters Θ, representing the dimensions along which the environment may vary across episodes. The goal of UED is then to adapt distributions over Θ, so to maximize some objective, which could be tied to an RL agent’s performance over this distribution. This allows us to view adaptive curricula as emerging via a multi-agent game between a teacher that proposes environments with parameters θ ∼ Θ and a student that learns to solve them. In addition to the notational clarity it provides, this formalism lends
the analysis of adaptive curricula to useful game theoretic constructs, such as Nash equilibria (NE, Nash et al., 1950).
This game-theoretic view has led to the development of curriculum methods with principled robustness guarantees, such as PAIRED (Dennis et 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, 1951) 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 regret-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 1 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 1 is closed—perhaps because it finds the agent needs more practice on Route 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 to each player randomly playing each option half the time. Randomly picking the route in this way is suboptimal, because in reality Route 1 is faster in expectation. This example is depicted in Figure 1, where the two routes are replaced by an apple and banana.
If, on a given day, the faster route could be identified before having to pick one, the agent could choose optimally. Instead, it is an aleatoric parameter, inducing irreducible uncertainty in the limit of infinite experiential data (Der Kiureghian & Ditlevsen, 2009). When CICS occurs over such parameters, with respect to a ground-truth distribution of environments P (θ), the learned policy can be suboptimal with respect to P . It can therefore be useful to ground—that is, to constrain—the aleatoric parameters Θ′ ⊂ Θ to P (θ′) when it is known or can be learned, as in simulation or from real-world data. However, grounding all θ is undesirable, preventing the curriculum from sampling enough opportunities to learn from useful scenarios with low support under P (θ).
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 θ′ is grounded to P (θ′). Our solution called Sample-Matched PLR (SAMPLR) extends PLR, a state-of-the-art UED algorithm, by constraining the advantage estimates to match those observed if training under P (θ′). This advantage correction adapts Off-Belief Learning (Hu et al., 2021) from cooperative MARL, revealing an intriguing connection between curriculum biases observed in single and multi-agent RL. Our experiments in challenging
environments based on 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.

heading: 2 BACKGROUND

heading: 2.1 UNSUPERVISED ENVIRONMENT DESIGN
text: 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 a 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 a POMDP, along which each concrete instantiation, or level, of the UPOMDP. For instance, these free parameters can be the position of obstacles in a maze, or friction coefficients in a physics-based task. Formally a UPOMDP is defined as a tupleM = 〈A,O,Θ,S, T , I,R, γ〉, where A is a set of actions, O is a set of observations, Θ is a set of free parameters, S is a set of states, T : S ×A×Θ→∆(S) is a transition function, I : S → O is an observation (or inspection) function,R : S → R is a reward function, and γ is a 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.
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 a buffer of the most useful levels for training, according to some learning potential score—typically based on a regret approximation, such as 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 selective-sampling mechanism has been demonstrated to greatly improve sample-efficiency and generalization in several domains, while provably leading to a minimax regret policy for the student at NE. In maximizing regret, PLR curricula naturally avoid unsolvable levels, which have no regret.

heading: 2.2 OFF-BELIEF LEARNING
text: In cooperative MARL, self-play promotes the formation of cryptic conventions—arbitrary 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-trained agents or humans at test time. Crucially, this leads to policies that fail to perform zero-shot coordination (ZSC, Hu et al., 2020), where independentlytrained agents must cooperate successfully without additional learning steps, or ad-hoc team play. Off-Belief Learning (OBL) resolves this problem by forcing agents to assume their co-players act according to a fixed, known policy π0 until the current time t, and optimally afterwards, conditioned on this assumption. If π0 is playing uniformly random, this removes the possibility of forming arbitrary conventions.
Formally, let G be a decentralized, partially-observable MDP (Dec-POMDP, Bernstein et al., 2002), with state s, joint action a, observation function Ii(s) for each player i, and transition function T (s, a). Let the historical trajectory τ = (s1, a1, ...at−1, st), and the action-observation history (AOH) for agent i be τ i = (Ii(s1), a1, ..., at−1, Ii(st)). Further, let π0 be an arbitrary policy, such as a uniformly random policy, and Bπ0(τ |τ i) = P (τt|τ it , π0), a belief model predicting the current state, conditioned on the AOH of agent i and the assumption of co-players playing policy π0 until the current time t, and optimally according to π1 from t and beyond. OBL aims to find the policy π1 with the optimal, counter-factual value function,
V π0→π1(τ i) = Eτ∼Bπ0 (τ i) [V π1(τ)] . (1)
As the agent conditions its policy on the realized AOH τ i, while transition dynamics are based on states sampled from B, this mechanism is called a fictitious transition. In Section 5, we show how OBL’s fictitious transition can be adapted to the single-agent curriculum learning setting to address CICS, by interpreting the curriculum designer in UED as a co-player.

heading: 3 RELATED WORK
text: The mismatch between training and testing distributions of input features is 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 et 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, 2019; 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 al., 2019; 2021). More generally, CICS can be interpreted as a 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., 2016), StarCraft 2 (Vinyals et al., 2019), and achieving comprehensive task mastery in open-ended environments (Stooke et al., 2021). While this work focuses on PLR, other recent methods include minimax adversarial curricula (Wang et al., 2019; 2020) and curricula based on changes in return (Matiisen et al., 2017; Portelas et al., 2020). Most similar to our work, OFFER (Ciosek & Whiteson, 2017) adapts a curriculum over transition functions and uses importance sampling to correct for biased gradient estimates. Unlike this work, Ciosek & 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-conditioned RL (Florensa et al., 2018; Campero et al., 2021; Sukhbaatar et al., 2018; OpenAI et al., 2021), though CICS does not occur here as goals are observed by the agent. Lastly, domain randomization (DR, Sadeghi & Levine, 2017; Peng et al., 2017) can be seen as a degenerate form of UED, though curriculum-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 on 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 to reduce its uncertainty about the identity of the MDP. In contrast, SAMPLR 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 a 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.

heading: 4 CURRICULUM-INDUCED COVARIATE SHIFT
text: As UED algorithms formulate curriculum learning as a multi-agent game between teacher and student agents, we can formalize when CICS become problematic by considering the equilibrium point of this game: Let θ be the environment parameters controlled by UED, P (θ), the ground truth distribution of θ, and P (θ), the curriculum distribution at equilibrium. Further, let τt be (o1, a1, ..., at−1, ot), the student agent’s action-observation history (AOH) until time t (though we will use simply τ when clear from context). The optimal action-value function Q∗ with respect to P (θ) can then be expressed as a marginalization over θ:
Q ∗ (at|τt) = Eτt+1:∞
at+1:∞ ∼π∗ [ ∞∑ l=0 γlrt+l ] = ∑ θ P (θ|τt)Q ∗ P (at|τt, θ) (2)
∝ ∑ θ P (θ)P (τt|θ)Q ∗ P (at|τt, θ). (3)
From Equation 2, we see that Q ∗ (at|τt) remains optimal under different values of P (θ) at each time t as long as it is possible to infer θ deterministically from τt, implying that P (θ′|τt) = 1 for some θ,
in which case the RHS of Equation 1 reduces to the LHS. If P (θ|τt) < 1 for all θ, then some subset θ′ ⊂ Θ results in irreducible uncertainty at time t, thereby constituting aleatoric parameters. Letting Q∗(at|τt) be the optimal action-value function when P (θ) is replaced with P (θ) in Equation 2, we can then state that curriculum-induced covariate shift results in suboptimal policies with respect to the ground truth distribution when
arg max a Q∗(a|τt) 6= arg max a Q ∗ (a|τt).
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 (θ) into two categories: The first type of error, which we call a mistake, simply arises when P (θ′′) = 0 for some non-aleatoric θ′′ where P (θ′′) > 0, i.e. the policy did not train on 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 we call a misunderstanding, and which corresponds to the problematic mismatch between training and test time distributions of specifically aleatoric parameters θ′, so that P (θ′) 6= P (θ′), as we just previously characterized. This taxonomy also clarifies errors in cooperative MARL, where the co-players shape environment interactions, and thus play a similar role to the UED teacher. Failures in ZSC can then be diagnosed as due to (i) a mistake, because the co-players fail to generate trajectories that occur with test-time co-players; or (ii), a misunderstanding, because the train-time co-players shift the training distribution of aleatoric parameters P (θ′), which impacts the inference of P (τ) = ∑ θ′ P (θ
′)P (τ |θ′) 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 in one of the settings may be adapted for the other. Indeed, we now describe our method, which does exactly this: By adapting OBL to single-agent curriculum learning, we can ground the values of P (θ′|τt) by forcing P (θ′) = P (θ′), thereby ensuring that the distribution of the aleatoric parameters at equilibrium is equivalent to their ground truth distribution.

heading: 5 SAMPLE-MATCHED PLR (SAMPLR)
text: We now describe how OBL’s fictitious transition can be adapted for PLR⊥ (Jiang et al., 2021a) to address CICS, resulting in Sample-Matched PLR (SAMPLR). To avoid CICS, we must ground θ′ to the ground-truth distribution P (θ′), 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 as a co-player—one that performs the single action of choosing the level θ at the start of each episode, and subsequently performs no-ops. Under this fictitious transition, we ground the teacher’s choice of θ such that the aleatoric parameters θ′ are assumed to be sampled from P (θ).
Thus, at each time t, the agent takes actions at based on its AOH as usual, but estimates the advantage A(at, st) using fictitious transitions, which assume subsequent state transitions and rewards occur with Θ′ fixed to θ′ ∼ P (θ′), sampled at the start of the episode. More formally, the fictitious transition is performed as s′t ∼ B(s′t|τ), at ∼ π(·|τ), s′t+1 = T (s′t, at), and r′t = R(st+1), where τ is the
Algorithm 1: Sample-Matched PLR (SAMPLR) Randomly initialize policy π(φ), an empty level buffer Λ of size K, and belief model B(st|τ). while not converged do
Sample replay-decision Bernoulli, d ∼ PD(d) if d = 0 or |Λ| = 0 then
Sample level θ from level generator Collect π’s trajectory τ on θ, with a stop-gradient φ⊥ Use observed ground-truth states to update B
else Use PLR to sample a replay level from the level store, θ ∼ Λ Collect fictitious trajectory τ ′ on θ, based on s′t ∼ B Update π with rewards R(τ ′) end Compute PLR score, S = score(τ ′, π) Update Λ with θ using score S
end
AOH of the student. Figure 2 summarizes this transition mechanism. Here, the belief model B(st|τ) can be expressed as
B(st|τ) = ∑ θ′ P (st|τ, θ′)P (θ′|τ). (4)
This shows that, assuming blackbox simulator access, we can generally implement B as follows: Periodically during training, we sample N trajectories, such that each is generated under a level with θ′ ∼ P (θ′). We use these {(θ′k, τk)} N k=1 pairs to update a posterior model P (θ
′|τ) that predicts the underlying θ′ given τ . We can then sample from B by first sampling θ ∼ P (θ′|τ), followed by stepping forward a parallel simulator that has been initially reset to the current AOH τ , with fixed Θ′ = θ′, thereby yielding a desired sample of st according to B. In practice, it is often the case that θ′ can be uniquely identified by some revelatory event by time t, so that P (θ′|τ) = 1 for some θ′ and τ , and P (st|τ, θ′) = P (st|τ) otherwise. In this case, we can implement the fictitious transition by setting θ′ ∼ P (θ′) at 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 is deterministically revealed by the final reward, and otherwise, does not impact transition dynamics. Additionally, we often only have limited access to P (θ) throughout training, for example, if sampling P (θ) is costly. In this case, we can learn an estimate P̂ (θ′) using the samples we do collect from P (θ), which can occur online. We then use P̂ (θ′) in sampling fictitious transitions during UED. We refer to the resulting P̂ (θ′) as a learned belief prior.
SAMPLR, summarized in Algorithm 1, 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 PLR⊥ for training. To reduce the cost of sampling P (θ′), we can use the new levels regularly sampled by PLR⊥ to estimate the learned belief prior P (θ′), and use P (θ′) in sampling fictitious transitions on replay levels.

heading: 6 GROUNDED POLICIES ARE ROBUSTLY BAYES OPTIMAL
text: We can view OBL-based correction as a method for training a policy to be optimal with respect to the ground-truth value function, with levels sampled from some generating distribution Λ defined as:
V Λ (π) = Eτ∼MΛ(π) [ V π (τ) ] . (5)
Note that when Λ = P (θ) this reduces to the ground-truth value function notated simply as V (π). First, we 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 fromMΛ(π), the distribution of trajectories of π in levels sampled from Λ.
Remark 1. If π is optimal with respect to the grounded value function V Λ(π) then it is Bayes optimal with respect to the ground-truth parameter distribution P (θ) on the support ofMΛ(π).
Proof. By definition we have that π ∈ arg max π∈Π {V Λ(π)} = arg max π∈Π
{Eτ∼MΛ(π) [ V π (τ) ] }. Since
π can condition on the initial trajectory τ , the action selected after each trajectory can be independently optimized. Thus we have, for all τ ∈MΛ(π), π ∈ arg max
π∈Π {V π(τ)} implying that π is the optimal
grounded policy and V π = V ∗ .
Thus, assuming the base RL algorithm finds Bayes optimal policies, a UED method that optimizes the grounded value function, as done by SAMPLR, will result in Bayes optimal performance over the ground-truth distribution. When the UED method aims to maximize worst-case regret, we can prove an even stronger property we call robust -Bayes optimality.
Let V θ (π) be the value function for π evaluated on a specific level θ. We will say that a policy is robustly -Bayes optimal iff for all θ in the domain of P (θ) and for all π′ we have
V θ (π) ≥ V θ(π′)− .
Note how this differs from being only -Bayes optimal, which means for all π′,
V (π) ≥ V (π′)−
With robust -Bayes optimality, we must be -optimal even on levels which are rarely sampled from the ground-truth distribution. We will show that if SAMPLR is in an -Nash Equilibrium, then a policy is robustly -Bayes optimal with respect to the grounded value function V (π) rather than only -Bayes optimal as one would expect from training directly on the true distribution of levels.
Theorem 1. If π is -Bayes optimal by V Λ(π) for Λ minimizing worst-case regret as is done in SAMPLR, then it is robustly -Bayes optimal with respect to the grounded value function, V (π).
Proof. Let π be -optimal with respect to V Λ
(π) where Λ minimizing worst-case regret with respect to π. Let π∗ be an optimal grounded policy, and let θ be arbitrary. Then we have:
V θ (π∗)− V θ(π) ≤ V Λ(π∗)− V Λ(π) ≤ (6)
Where the first inequality follows from Λ minimizing worst-case regret with respect to π, and the second follows from π being -optimal on Λ. Rearranging terms gives the desired condition.

heading: 7 EXPERIMENTS
text: We investigate the performance of SAMPLR with respect to the the standard PLR and domain randomization in environments based on MiniHack (Samvelyan et al., 2021), a library for creating custom environments based on the runtime of the NetHack Learning Environment (NLE) (Küttler et 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 PLR-specific hyperparameters shared among PLR⊥ and SAMPLR variants for each environment, based on the performance of PLR⊥. 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 a variant called LP-SAMPLR that learns a 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 to curriculum learning and our proposed correction for CICS.
0 100M 200M 0
1
2
3
4
5
M ea
n ep
is od
ic re
tu rn
0 100M 200M 0.0
0.5
1.0
1.5
2.0
2.5
S ol
ve d
ro om
c ou
nt
Test Train
Steps
DR PLR SAMPLR LP-SAMPLR q = 0.3
0 200M
q = 0.5
0 200M
1
0 0 200M
q = 0.7
0 200M0 200M
1
0 0 200M
M ea
n te
st r
et ur n P ro po rti on a pp le
Figure 4: Episodic returns (left) and number 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-generated 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 as 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, as well as the NLE-specific skills of kicking doors and eating. 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⊥’s adaptive curriculum to improve learning by selectively sampling levels at the threshold of the agent’s abilities.
Let πA be the policy in which the agent always chooses the apple, and πB , the banana. If the probability of the goal being apple P (A) = q, the expected return of the agent is RAq under πA and RB(1 − q) under πB . The optimal policy is then to act according to πA when q > RB/(RA +RB), and according to πB otherwise. We expect training under domain randomization, which samples each level completely at random from the ground-truth distribution P (θ), defined by the environment parameterization, would converge to the correct choice of πA or πB , assuming the environment is learnable by the choice of RL algorithm. In contrast, PLR evolves an adversarial curriculum, incentivizing PLR to shift the distribution over goals throughout training. For example, PLR is incentivized to flip the curriculum distribution to favor eating apples whenever the agent begins to consistently succeed at eating bananas. We thus expect the PLR curriculum to continually oscillate the preferred choice of goal.
In our experiments, we set RA = 3, RB = 10, and q in {0.7, 0.5, 0.3}, making it always optimal to follow the banana-eating policy πB , but with the marginal benefit of doing so varying with q. 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.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 q 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 5, 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 LP-SAMPLR realize a marked improvement in test performance by grounding PLR’s
0 100M 200M 0.0
1.0 None
0 100M 200M 0.0
0.2
0.4
0.6
0.8
1.0 Apple
0 100M 200M 0.0
0.2
0.4
0.6
0.8
1.0 Banana
P ro
po rti
on s
el ec
te d
Steps
DR PLR SAMPLR LP-SAMPLR
0 50M 100M 150M 200M
4.4 4.6 4.8 5.0 5.2 5.4 5.6 5.8 Tr ai ni ng ro om c ou nt
Figure 5: Left: Proportion of training episodes in which the agent fails to eat 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.
0 50M 100M 150M
0.0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
P ro
po rti
on fi
re pr
oo f
0 50M 100M 150M 0.00
0.05
0.10
0.15
0.20
0.25
M ea
n te
st e
pi so
de re
tu rn
DR PLR SAMPLR LP-SAMPLR
Steps
Figure 6: Left: Levels from FireDungeon. Middle: Test return on the ground-truth distribution of FireDungeon. Right: Proportion of training levels with fireproof armor. Plots show mean and standard error of 10 runs.
otherwise wild shifts in q. Figure 4 shows this improvement is most pronounced when the expected difference in πA and πB is smaller, and therefore easier for PLR to flip the agent’s policy. Moreover, we see in Figure 5 that both SAMPLR methods present levels with higher room counts on average, indicating that early in training, it is able to 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 a more challenging environment that introduces additional NetHack-specific dynamics. The FireDungeon environment (see Figure 6 for example levels), requires the agent to navigate through up to 13 chambers, and ultimately choose between chamber A or B, each containing a valid goal. Reaching this goal ends the episode and provides the agent with a sparse reward. Further, in this penultimate chamber, there is an 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 is fireproof. This environment presents an even more difficult exploration problem for the agent, yet we see in Figure 6, 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 aleatoric parameter, which in this case, determines whether the armor is fireproof.

heading: 8 CONCLUSION
text: Using the formal notions of environment parameterizations in the framework of UED, we defined the problem of curriculum-induced 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 a 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.

Review summaries:
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.

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.

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.