ELLA: Exploration through Learned Language Abstraction
Year: 2022

Abstract:
Building agents capable of understanding language instructions is critical to effective and robust human-AI collaboration. Recent work focuses on training these agents via reinforcement learning in environments with synthetic language; however, instructions often define long-horizon, sparse-reward tasks, and learning policies requires many episodes of experience. We introduce ELLA: Exploration through Learned Language Abstraction, a reward shaping approach geared towards boosting sample efficiency in sparse reward environments by correlating high-level instructions with simpler low-level constituents. ELLA has two key elements: 1) A termination classifier that identifies when agents complete low-level instructions, and 2) A relevance classifier that correlates low-level instructions with success on high-level tasks. We learn the termination classifier offline from pairs of instructions and terminal states. Notably, in departure from prior work in language and abstraction, we learn the relevance classifier online, without relying on an explicit decomposition of high-level instructions to low-level instructions. On a suite of complex BabyAI [11] environments with varying instruction complexities and reward sparsity, ELLA shows gains in sample efficiency relative to language-based shaping and traditional RL methods.

heading: 1 Introduction
text: A long-standing goal for robotics and embodied agents is to build systems that can perform tasks specified in natural language [1, 8, 20, 25, 38, 41, 42]. Central to the promise of language is its ability to cleanly specify complex, multi-step instructions. Instructions like make a cup of coffee define long-horizon tasks as abstractions over lower-level components—simple instructions like pick up a cup or turn on the coffee maker. Leveraging these abstractions can help amplify the sample efficiency and generalization potential of our autonomous agents.
One way to do this is through the lens of instruction following, which can be framed in several ways. One common framing—and the one we use in this work—is via reinforcement learning (RL): an agent is given a start state, a language instruction, and a corresponding reward function to optimize that usually denotes termination [20, 30]. While RL can be a useful framing, such approaches are often not sample efficient [11, 20]. Especially in the case of complex, highly compositional language instructions, RL agents can fail to make progress quickly—or at all. There are several reasons for poor performance in these settings; paramount is that in many environments, these instructions are
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
tied to sparse reward functions that only provide signal upon completion of the high-level task, which drastically hurts sample efficiency. For example, seeing reward for make a cup of coffee would require already having turned on the coffee maker, which could itself be a difficult task. Such “bottleneck" states, which have zero intermediate reward, complicate exploration and learning [29, 39].
Our goal is to improve sample efficiency for instruction following agents operating in sparse reward settings. Driving our approach is using the principle of abstraction—the fact that complex instructions entail simpler ones—to guide exploration. Consider our coffee example; we would like to guide the agent to explore in a structured fashion, learning low-level behaviors first (pick up a cup, turn on the coffee machine) and building up to solving the high-level task. To do this, we frame our problem via reward shaping, the general technique of supplying auxiliary rewards to guide learning [31, 35].
Our approach, Exploration through Learned Language Abstraction (ELLA) provides intermediate rewards to an agent for completing relevant low-level behaviors as it tries to solve a complex, sparse reward task. Notably, our approach 1) learns to identify the low-level primitives helpful for a high-level language task online, and 2) does not require a strict hierarchical decomposition of language instructions to these primitives. Rather, ELLA uses low-level instructions to support agents performing complex tasks, bonusing agents as they complete relevant behaviors. In contrast to prior work [3, 23] that assumes strict contracts over instruction decomposition, our contract is simple and general. This prior work assumes each high-level task is comprised of exact series of low-level policies—an assumption that is only possible when the full set of primitives is known ahead of time, and fails when new actions or further exploration are necessary.
In order to bonus agents as they complete relevant subtasks, ELLA assumes access to a set of lowlevel instructions and corresponding termination states, similar to the data assumed in prior work [6]. While collecting such data for complex tasks may require time and effort, annotations for low-level instructions are more tractable. Humans can quickly annotate instructions like pick up the cup or open the cupboard, or even build tools for generating such examples. This is increasingly apparent in prior work [5, 22, 25, 43]; low-level instructions are used to simplify the problem of interpreting high-level instructions, through a variety of mechanisms. In our case, these low-level instructions provide the basis for reward shaping.
We empirically validate our abstraction-based reward shaping framework on a series of tasks via the BabyAI platform [11]. We compare against a standard RL baseline as well as to a strong languagebased reward shaping approach [17], and find that our method leads to substantial gains in sample efficiency across a variety of instruction following tasks.

heading: 2 Related Work
text: We build on a large body of work that studies language in the context of reinforcement learning (RL) [27] with a focus on methods for instruction following, leveraging hierarchy, and reward shaping.
Instruction Following. Instruction following focuses on the automated execution of language commands in simulated or real environments [1, 16, 26, 41, 44]. We focus on the RL setting [11, 30], where agents learn language-conditioned policies in a Markov decision process (MDP).
Even simple instruction following problems are difficult to learn [28], which has made 2D environments important test-beds for new learning methods [3, 11, 46]. Such environments, which are procedurally-generated, are useful because they decouple exploration from the problem of perception, and demand policies that do not overfit to narrow regions in the state space [10, 13].
We use BabyAI [11] as the platform for our tasks. BabyAI’s language is synthetic, similar to prior work examining RL for instruction following at scale [20, 21]. These environments are scalable starting points for new instruction following approaches, since deep RL remains sample-inefficient but has the potential to flexibly deal with complex environments [21]. Simplified environments also make investigating concepts such as language abstraction possible, and these concepts can generalize to real human-AI interactions [25, 43]. We describe our experimental setup in Section 5.
Hierarchical and Language-Structured Policies. A large body of work in hierarchical RL studies temporal abstractions of MDPs, where policies are designed or learned at multiple levels of hierarchy [40]. Recent works have made the connection to language: for example, high-level policies can act over the space of low-level instructions [23]. Other hierarchical language techniques include learning models that predict symbolic representations of reward functions at different granularities [5, 24], and compositional approaches like policy sketches [3] and modular control [15], methods that explicitly decompose high-level instructions into sequences of predefined low-level instructions, or subtasks.
In this work, we use language hierarchically, but without the strict decomposition assumption made by prior work: we do not assume high-level tasks are composed of an exact series of low-level tasks. Without this assumption, it is infeasible to use explicitly modular approaches [3, 5, 15]. A further distinguishing factor of our method relative to prior work is that we do not require high-level task decompositions be provided a priori. We expand on these features in Section 3.
Language and Reward Shaping. Reward shaping is a general technique for supplying auxiliary rewards in order to guide an agent’s learning process. Certain types of reward transformations, such as potential-based rewards, do not change the optimal policy but can impact sample efficiency [31]. Prior work has applied reward shaping to language-based instruction following settings. Goyal et al. [17] train a classification network on (trajectory, language) data to predict if a trajectory (parameterized by action frequencies) matches a language description, and evaluate the network at every time step to form a potential-based reward shaping function. They evaluate their method on Montezuma’s Revenge, which is a complex task, but with a static, deterministic layout that does not speak to the generalization potential of such methods. Relatedly, Waytowich et al. [45] use a narration-based approach, where high-level tasks are explicitly broken down into low-level tasks as narrations. Finally, Misra et al. [30] use a shaping function based on spatial distance to goals specified in language, but require the location of the goal to be known. In this work, we use the same high level principle— language can yield useful intermediate rewards—but do not make the restrictive assumptions of prior work about the environment or the way tasks are structured.
Other Forms of Guidance. Several other methods exist for improving the sample efficiency of RL in sparse reward settings. These methods reward an aspect of exploration that is orthogonal to our approach, and we see potential for combining these methods with ours. One popular technique is hindsight experience replay (HER), in which failed trajectories are stored in a replay buffer and relabeled with new goals that get nonzero reward [4]. Jiang et al. [23] extend the method to hierarchical language settings, assuming a mapping from states to corresponding goals. Cideron et al. [12] learn this mapping alongside policy training using the environment reward as supervision. Another technique for improving sample efficiency is through intrinsic motivation [9, 32, 34, 36]. In general, these methods instantiate reward shaping to incentivize accessing novel, diverse, or unpredictable parts of the state space via intrinsic rewards, and they can be extended to language-
conditioned settings as well [14]. In Appendix D, we evaluate the performance of RIDE [34], an intrinsic motivation method that rewards actions that cause significant changes to the state, and discuss potential synergies with ELLA.

heading: 3 Problem Statement
text: We consider an augmented MDPM defined by the tuple (S,A, T,R,G, γ) where S,A, T , and γ are standard. A consists of primitive actions—in BabyAI, these are navigation primitives (forward, pick up, etc.). G is a set of language instructions, from which a high-level task instruction g is drawn, and R : S × A × G → [0, 1] represents the state-action reward given some g. Via RL, we wish to find some policy π : S × G → A that maximizes the expected discounted return. We specifically consider cases where M has a finite horizon H and R is sparse with respect to goal-completion, making exploration difficult. Our aim is to construct a reward transformation R → R′ which is policy invariant with respect to the original MDP (i.e. an optimal policy for M′ = (S,A, T,R′, g, γ) is also optimal inM and vice versa), while providing the agent strong signal conducive to sample-efficient exploration.
We assume access to a set of low-level instructions Gℓ such that every g ∈ G is supported by some gℓ ∈ Gℓ. Note that we do not require that high-level tasks fully factorize into low-level tasks. To clarify the distinction, say that Gℓ consists of go to “x” instructions: go to the red ball, go to the blue ball, etc. The instruction go to the red ball and then go to the blue ball can be fully factorized into low-level tasks in Gℓ. On the other hand, the instruction put the red ball next to the green key is supported by go to the red ball, but it also requires picking up and putting down the ball—actions not covered by Gℓ. Our framing permits exploration using a mixture of low-level instructions as well as primitive actions in A (such as pick up and put down). We assume that examples of the corresponding termination states of instructions in Gℓ are easy to obtain—via a human expert or automation. This is reasonable for simple low-level tasks like the go to tasks in Figure 1. However, it is less feasible in domains where data collection is costly and the environment is hard to simulate; we address this further in Section 7.
The environments in our experiments are partially observable, so we use recurrent networks that ingest sequences of observations (o1, o2, ..., ot) rather than a single state st [19]. Though our notation describes the fully observable setting, the extension to the partially observable case is straightforward.

heading: 4 ELLA
text: We present ELLA, our reward shaping framework for guiding exploration using learned language abstractions.1 Figure 1 provides a graphical overview of ELLA. Our approach rewards an agent when it has completed low-level tasks that support a given high level task. To do this, it predicts 1) when a low-level task terminates and 2) when a low-level task is relevant. Section 4.1 describes our low-level termination classifier. Section 4.2 describes our relevance classifier, and how we learn it online during RL. Finally, Section 4.3 details our reward shaping scheme, which bonuses an agent for exploring states that satisfy relevant low-level tasks.

heading: 4.1 Learning the Low-Level Termination Classifier
text: We train a binary termination classifier hϕ : S × Gℓ → {0, 1} parameterized by ϕ to predict if a low-level task gℓ ∈ Gℓ terminates in a particular state s ∈ S. We assume access to Gℓ as well as positive and negative examples of low-level task termination states. This dataset could be annotated by a human or created automatically. While providing demonstrations of high-level tasks (e.g., make a cup of coffee) across varied environments is costly, it is more feasible to do so for low-level tasks (e.g., pick up the mug) which are shorter, simpler, and more generalizable. To represent hϕ, we adapt the architecture from [11] which merges state and language representations using feature-wise linear modulation (FiLM) [33].
1Our code is available at https://github.com/Stanford-ILIAD/ELLA.
Algorithm 1 Reward Shaping via ELLA Input: Initial policy parameters θ0, relevance classifier parameters ρ0, update rate n, lowlevel bonus λ, and RL optimizer OPTIMIZE Initialize D ← {(g : Gℓ) for all g in G} for k = 0, 1, . . . do
Collect trajectories Dk using πθk. for τ ∈ Dk do
Set N ← length of τ Set (r′1:N , Ŝ)← SHAPE(τ ) if U(τ) > 0 then
Set r′N ← NEUTRALIZE(r′1:N ) Set D[g]← UPDATEDECOMP(D, Ŝ)
Update θk+1 ← OPTIMIZE(r′1:N ). if k is a multiple of n then
Update ρk+1 by optimizing cross entropy loss on a balanced sample from D.
function SHAPE(τ ) Set Ŝ← ∅ for gℓ ∈ Gℓ do
for g, (st, rt) ∈ τ do if hϕ(st, gℓ) = 1 and gℓ ̸∈ Ŝ then
Update Ŝ← Ŝ ∪ {gℓ} Set r′t ← rt + λ · I[fρ(g, gℓ) = 1]
return (r′1:N , Ŝ)
function NEUTRALIZE(r′1:N ) Set TS ← {t | 1 ≤ t ≤ N, r′t > 0} return r′N − ∑︁ t∈TS γ t−Nλ
function UPDATEDECOMP(D, Ŝ) Set S← D[g] return S ∩ Ŝ (or Ŝ if S ∩ Ŝ = ∅)

heading: 4.2 Learning the Relevance Classifier
text: Our reward shaping approach also needs to evaluate relevance of a low-level instruction in addition to being able to classify termination. The relevance mapping from G to P(Gℓ) (the power set of Gℓ) is initially unknown to the agent. We refer to the output of this mapping as a decomposition of g, but note again that it need not be a strict decomposition. We propose that this mapping is represented by a separate binary relevance classifier fρ : G × Gℓ → {0, 1} learned during policy training from a dataset of decompositionsD collected online. The output of fρ indicates whether a particular gℓ ∈ Gℓ is relevant to some g ∈ G. We use a Siamese network to represent fρ.
Training the Relevance Classifier. SupposeD already contains key-value pairs (g,S) where g ∈ G and S ∈ P(Gℓ). Each S is an estimate of the oracle decomposition S̄ of a particular g. For every g in D, we enumerate negative examples of relevant subtasks from Gℓ \ S and accordingly oversample positive examples from S; we then optimize a cross entropy objective on this balanced dataset.
Collecting Relevance Data Online. We describe any trajectory that solves the high-level task as successful, regardless of whether they do so optimally, and any other trajectories as unsuccessful. For every successful trajectory of some g we encounter during RL training, we record the lowlevel instructions which terminated. That is, we relabel the steps in the trajectory and use hϕ to determine which low-level instructions were completed (if any), yielding an estimate Ŝ of the true decomposition S̄. If D already contains an estimate S for g, we simply deduplicate the multiple decomposition estimates by intersecting S and Ŝ. As the agent completes more successful trajectories, decompositions in D are more likely to get revisited.
Intuition for Deduplication. Intuitively, this method for deduplication denoises run-specific experiences, and distills the estimate S in D for a given g to only those gℓ that are shared among multiple successful runs of g. Consider g = put the red ball next to the blue box; successful runs early in training could highlight go to the red ball along with irrelevant go to low-level instructions. As πθ improves, so do the decomposition estimates. Later runs may highlight only go to the red ball. Taking the intersection would yield only go to the red ball as our final estimate S. This approach also helps to deal with false positives of hϕ by effectively boosting the estimate across runs. If deduplication produces a null intersection, which may happen due to false negatives of hϕ, we err on the side of using the latest estimate. If we assume hϕ has perfect accuracy, the intersection will never be null, and the continual intersections will reflect the set of completed gℓ common to all successful runs of g. For an initialization conducive to deduplication and that provides πθ strong incentive to complete low-level tasks from the beginning of training, we initialize fρ to predict that S = Gℓ for all g.

heading: 4.3 Shaping Rewards
text: We now describe the shaped reward function R′ which relies on hϕ and fρ. R′ provides a bonus λ whenever a relevant low-level task terminates. We do this by relabeling the current (st, at, rt, st+1) with every gℓ and using hϕ to predict low-level task termination, and fρ to predict relevance.
Critically, we do not want the shaping transformation from R → R′ to be vulnerable to the agent getting “distracted” by the shaped reward (reward hacking), as in Randløv and Alstrøm [35] where an agent learns to ride a bicycle in a circle around a goal repeatedly accruing reward. To this end, we cap the bonus per low-level instruction per episode to λ to prevent cycles. More generally, we want R′ to be policy invariant with respect toM: it should not introduce any new optimal policies, and it should retain all the optimal policies fromM. Policy invariance is a useful property [31]: we do not want to reward a suboptimal trajectory (such as one that repeatedly completes a low-level instruction) more than an optimal trajectory inM, and policy invariance guarantees this. We establish two desiderata for R′ [7]: (a) The reward transformation should be policy invariant with respect toM for states from which the task is solvable, and (b) R′ should improve sample efficiency by encouraging subtask-based exploration. To satisfy our desiderata, we choose R′ such that successful trajectories get the same return underM andM′, and that unsuccessful trajectories get lower returns underM′ than trajectories optimal inM. We will describe and intuitively justify each of these choices with respect to (a) and (b).
Neutralization in Successful Trajectories. We neutralize shaped reward in successful trajectories— that is, subtract the shaped reward at the final time step—so that successful trajectories gets the same return under both R′ and R.
More specifically, let U(τ) := ∑︁N
t=1 γ tR(st, at), the cumulative discounted return under R of a
successful trajectory τ . Let U ′(τ) be likewise defined for R′. If τ has N steps, the sparse reward under R is U(τ) = γNrN . Under R′, if TS is the set of the time steps at which a λ bonus is applied, we set r′N to rN − ∑︁ t∈TS γ
t−Nλ. This is the value required to neutralize the intermediate rewards, such that U ′(τ) = γNrN = U(τ). (Note that we cap the bonus per time step to λ—if multiple low-level language instructions terminate at a single state, only a bonus of λ is applied.)
Theoretically, we could apply neutralization to all trajectories, not just successful ones, and we would satisfy property (a) [18]. However, this is harmful to property (b), because unsuccessful trajectories would result in zero return: a negative reward at the last time step would negate the subtask rewards, potentially hurting boosts in sample efficiency.
Tuning λ to Limit Return in Unsuccessful Trajectories. Any successful trajectory gets the same return under R′ as under R because of neutralization. By choosing λ carefully, we can additionally satisfy the property that any unsuccessful trajectory gets a lower return under R′ than any trajectory selected by an optimal policy π∗M inM. To achieve this, we need λ to be sufficiently small. Assume that a trajectory τ selected by π∗M takes no longer than M time steps to solve any g. In the worst case, M = H , and U(τ) would be γHrH . If TS is the set of the time steps at which R′ provides λ bonuses, U ′(τ) would be λ ∑︁ t∈TS γ
t. We can upper bound ∑︁ t∈TS γ t with |Gℓ|. Then, the following inequality is sufficient for maintaining (a):
λ < γHrH |Gℓ| , (1)
where rH is the value of a sparse reward if it were attained at time step H . We provide a more thorough justification of this choice of λ in Appendix F. Note that λ and the sparse reward can be both scaled by a constant if λ is otherwise too small to propagate as a reward.
An important feature of our work is the realization that we can make this bound less conservative through minimal knowledge about the optimal policy and the environment (e.g., knowledge about the expected task horizon M , or a tighter estimate of the number of subtasks available in an environment instance). Such reasoning yields a feasible range of values for λ, and these can empirically lead to faster learning (Section 6.1). At a minimum, reasoning over the value of λ using via (1) provides a generalizable way to incorporate this technique across a variety of different settings in future work.
We summarize our shaping procedure in Algorithm 1, with an expanded version in Appendix C.

heading: 5 Experiments
text: Experimental Setup. We run our experiments in BabyAI [11], a grid world platform for instruction following, where an agent has a limited range of view and receives goal instructions such as go to the red ball or open a blue door. Grid worlds can consist of multiple rooms connected by a closed/locked door (e.g., the UNLOCK-MAZE environment in Figure 2). The action space A consists of several navigation primitives (forward, pickup, etc.). Every task instance includes randomly placed distractor objects that agents can interact with. Rewards in BabyAI are sparse: agents receive a reward of 1− 0.9 tH where t is the time step upon succeeding at the high-level goal. If the goal is not reached, the reward is 0. By default, all rewards are scaled up by a constant factor of 20.
We evaluate our reward shaping framework using Proximal Policy Optimization (PPO) [37], but note that ELLA is agnostic to the RL algorithm used. We compare to PPO without shaping, as well as to LEARN, a prior method on language-based reward shaping [17] that provides rewards based on the predicted relevance of action frequencies in the current trajectory to the current instruction.
We focus on several high- and low-level tasks. Table 1 describes each task with examples. ROOM levels consist of a single 7 × 7 grid, while MAZE levels contain two such rooms, connected by a door; agents may need to open and pass through the door multiple times to complete the task. In the UNLOCK environment, the door is “locked,” requiring the agent to hold a key of the same color as the door before opening it, introducing significant bottleneck states [29, 39]. We choose six high- and low-level task pairs in order to differ along three axes: sparsity of the high-level task, similarity of the low- and high-level tasks, and compositionality of the tasks in G—the number of gℓ ∈ Gℓ relevant to some g. We use these axes to frame our understanding of how ELLA performs in different situations.
We used a combination of NVIDIA Titan and Tesla T4 GPUs to train our models. We ran 3 seeds for each of the 3 methods in each environment, with runs taking 1 to 6 days.
Results. Figure 2 presents learning curves for ELLA, LEARN, and PPO (without shaping) across the six environments. We explain our results in the context of the three axes described above.
→ How does ELLA perform on tasks with different degrees of sparsity?
In both single room (PUTNEXT-ROOM) and two room (PUTNEXT-MAZE) environments, ELLA induces gains in sample efficiency, using GOTO as Gℓ. Relative gains are larger for the bigger
environment because reward signals are more spatially sparse and so spatial subgoals—visiting relevant objects—help the agent navigate.
Another degree of sparsity comes from bottleneck states: for example, in the UNLOCK environment, the agent must pick up a key of the corresponding color (the bottleneck) before it can successfully open a colored door and see reward. Without shaping, random exploration rarely passes such bottlenecks. However, in this experiment, ELLA rewards picking up keys, via the PICK low-level instruction, quickly learning to correlate picking up keys of the correct color with successfully unlocking doors, allowing agents to navigate these bottlenecks and improving sample efficiency.
→ How does ELLA perform when the low-level tasks are similar to the high-level task?
Tasks in the COMBO environment consist of multiple instruction types (e.g., put the red ball next to the green box, open the green door, and pick up the blue box). The latter instructions require minimal exploration beyond “going to” an object — such as executing an additional open or pick up primitive actions. That is, the low-level task GOTO is more similar to this high-level task set than in the other environments such as PUTNEXT. As a result, ELLA does not increase in sample efficiency in COMBO. However, it notably does not perform worse than baselines: the exploration it encourages is not harmful, but is simply not helpful. This is expected as achieving the COMBO tasks is about as difficult as exploring the relevant GOTO subtasks.
→ How does ELLA perform when the high-level tasks are compositional and diverse?
We test ELLA on OPEN&PICK using two low-level instruction families, OPEN and GOTO. The instruction open the yellow door and pick up the blue box abstracts over go to the yellow door, open the yellow door, and go to the blue box. Although learning fρ becomes harder with more compositional instructions, the boost in sample efficiency provided by ELLA remains.
Similarly, SEQUENCE has a combinatorially-large number of compositional instructions: it requires two of put next, open, and pick up in the correct order. It has over 1.5 million instructions compared to the other high-level tasks with 300 to 1500 instructions. Although the exploration problem is very difficult, we see marginal gains from ELLA; we discuss this further in Section 7.

heading: 6 Analyzing ELLA
text: In this section, we analyze two aspects of ELLA: the effect of different choices for the low-level reward hyperparameter (Section 6.1), and the performance of the relevance classifier (Section 6.2).

heading: 6.1 Effect of the Low-Level Task Reward
text: The magnitude of the low-level reward λ is a critical hyperparameter. Instead of using ad hoc methods for tuning λ, Section 4.3 provides guidelines for choosing a reasonable range for λ. To summarize, we want to pick λ small enough that any unsuccessful trajectory does not receive greater return than any optimal trajectory. In this section, we examine PUTNEXT-ROOM and evaluate various λ values determined using the multi-tier assumptions alluded to in Section 4.3. For this task, we have that H = 128 and |Gℓ| = 36. With no knowledge of the environment or optimal policy, the loosest bounds for M and |TS| (H and |Gℓ| respectively), as in (1) yield λ = 0.015. With the minimal assumption that an optimal policy solves the task in under 100 steps, we arrive at λ = 0.05. For 40 steps, we arrive at λ = 0.25. Figure 3 compares learning curves for λ—the smallest being more conservative and not having a great effect on sample efficiency, the middle values illustrating the value of rewarding relevant subtasks, and the largest values chosen specifically to demonstrate that egregious violations of policy invariance can “distract” the agent from the high-level task and lead to unstable learning. The results in Section 5 use λ=0.25 for PUTNEXT, UNLOCK, and COMBO, and use λ = 0.5 for OPEN&PICK and SEQUENCE (which have longer horizons H).

heading: 6.2 Progress of the Relevance Classifier
text: The online relevance dataset and classifier provide transparency into the type of guidance that ELLA provides. Figure 4 focuses on PUTNEXT-MAZE and SEQUENCE-MAZE, and shows two metrics: the average number of subtasks per high-level instruction in D, which we expect to decrease as decomposition estimates improve; and the validation accuracy of fρ in classifying a balanced oracle set of subtask decompositions, which we expect to increase if ELLA learns language abstractions.
For PUTNEXT-MAZE, the number of subtasks per high-level instruction decreases and the relevance classifier becomes very accurate. This happens as, from Figure 2, the policy improves in terms of average return. For the SEQUENCE-MAZE task, ELLA has marginal gains in performance compared to baselines (Figure 2). This is likely due to ELLA incentivizing general subtask completion, evidenced by the growing average length of the decompositions. However, the large number of diverse language instructions in SEQUENCE-MAZE makes it difficult to estimate good decompositions via our deduplication method (as it is uncommon to see the same instruction multiple times). It is difficult to learn fρ online and offer the most targeted low-level bonuses in this case.

heading: 7 Discussion
text: We introduce ELLA, a reward shaping approach for guiding exploration based on the principle of abstraction in language. Our approach incentivizes low-level behaviors without assuming a strict hierarchy between high- and low-level language, and learns to identify relevant abstractions online.
As noted in Section 2, several other methods exist for addressing sample inefficiency in sparse reward settings. While we focus on using language as the basis for reward shaping, intrinsic rewards can also be based on the dynamics of the environment. For example, RIDE [34] provides rewards for actions that produce significant changes to the state. In Appendix D, we discuss how ELLA can synergize with such methods to reward different aspects of exploration.
Limitations and Future Work. Our framework requires termination states for each low-level instruction. This assumption is similar to that made by Jiang et al. [23] and Waytowich et al. [45], and is weaker than the assumption made by the LEARN baseline of Goyal et al. [17], where full demonstrations are required. Even so, training accurate termination classifiers can require many examples—in this work, we used 15K positive and negative pairs for each low-level task. In Appendix E, we provide an ablation on the data budget for the termination classifier. Our approach is less feasible in domains where collecting examples of low-level terminating conditions is costly.
Highly compositional and diverse instructions, as in the SEQUENCE-MAZE environment, remain a challenge. Data augmentation (e.g., GECA [2]) on the online relevance dataset could potentially improve performance on these large instruction sets. Additional boosts in performance and generalization could emerge from instilling language priors via offline pre-training. More sophisticated relevance classifiers may also prove helpful: instead of deduplicating and training on D, we could maintain a belief distribution over whether high- and low-level instructions are relevant conditioned on trajectories observed online. Furthermore, the relevance classifier could be extended to model the temporal order of the low-level tasks.
Our approach shows strong performance in several sparse reward task settings with synthetic language. Extensions to natural language could model a broad spectrum of abstraction beyond two tiers.
Acknowledgments and Disclosure of Funding
This project was supported by NSF Award 1941722 and 2006388, the Future of Life Institute, the Office of Naval Research, and the Air Force Office of Scientific Research. Siddharth Karamcheti is additionally supported by the Open Philanthropy AI Fellowship.
Furthermore, we would like to thank Dilip Arumugam, Suneel Belkhale, Erdem Bıyık, Ian Huang, Minae Kwon, Ben Newman, Andrea Zanette, and our anonymous reviewers for feedback on earlier versions of this paper.

Review summaries:
The paper present ELLA, a three-part solution to instruction following tasks with a high-level instruction and a pre-defined set of low-level instructions:  1. a termination classifier is trained offline to identify the completion of a low-level goal at a state; 2. a relevance classifier is learned online to predict a binary relevance of a low-level goal to a high-level goal. 3. reward shaping is used to encourage low-level goals suggested by the relevance classifier.  ELLA is shown to improve sample complexity on 5/6 BabyAI tasks of diverse environment and instruction complexities, compared to an ablation PPO model with reward shaping, and a baseline model LEARN.

This paper presents a reward shaping approach that provides immediate rewards through the achievement of low-level sub-tasks. The authors assume a problem where a high-level task given in the natural language in a sparse reward environment consists of several low-level sub-tasks, and aim to guide the agent to effectively explore using task structure. Two components (termination classifier and relevance classifier) are proposed, and reward shaping is performed using them. Finally, the authors demonstrated the results on BabyAI, a grid world platform for instruction following tasks.