## POSSIBILITY BEFORE UTILITY: LEARNING AND USING HIERARCHICAL AFFORDANCES

**Robby Costales[1][∗]** **Shariq Iqbal[1]** **Fei Sha[2]**

1University of Southern California 2Google Research

ABSTRACT

Reinforcement learning algorithms struggle on tasks with complex hierarchical
dependency structures. Humans and other intelligent agents do not waste time
assessing the utility of every high-level action in existence, but instead only consider ones they deem possible in the first place. By focusing only on what is
feasible, or “afforded”, at the present moment, an agent can spend more time both
evaluating the utility of and acting on what matters. To this end, we present Hier_archical Affordance Learning (HAL), a method that learns a model of hierarchical_
_affordances in order to prune impossible subtasks for more effective learning. Ex-_
isting works in hierarchical reinforcement learning provide agents with structural
representations of subtasks but are not affordance-aware, and by grounding our
definition of hierarchical affordances in the present state, our approach is more
flexible than the multitude of approaches that ground their subtask dependencies
in a symbolic history. While these logic-based methods often require complete
knowledge of the subtask hierarchy, our approach is able to utilize incomplete
and varying symbolic specifications. Furthermore, we demonstrate that relative
to non-affordance-aware methods, HAL agents are better able to efficiently learn
complex tasks, navigate environment stochasticity, and acquire diverse skills in the
absence of extrinsic supervision—all of which are hallmarks of human learning.[1]

1 INTRODUCTION

Reinforcement learning (RL) methods have recently achieved success in a variety of historically
difficult domains (Mnih et al., 2015; Silver et al., 2016; Vinyals et al., 2019), but they continue to
struggle on complex hierarchical tasks. Human-like intelligent agents are able to succeed in such
tasks through an innate understanding of what their environment enables them to do. In other words,
they do not waste time attempting the impossible. Gibson (1977) coins the term “affordances” to
articulate the observation that humans and other animals largely interpret the world around them
in terms of which behaviors the environment affords them. While some previous works apply the
concept of affordances to the RL setting, none of these methods easily translate to environments with
hierarchical tasks. In this work, we introduce Hierarchical Affordance Learning (HAL), a method
that addresses the challenges inherent to learning affordances over high-level subtasks, enabling
more efficient learning in environments with complex subtask dependency structures.

Many real-world environments have an underlying hierarchical dependency structure (Fig. 1a), and
successful completion of tasks in these environments requires understanding how to complete individual subtasks and knowing the relationships between them. Consider the task of preparing a
simple pasta dish. Some sets of subtasks, like chopping vegetables or filling a pot with water, can
be successfully performed in any order. However, there are many cases in which the dependencies
between subtasks must be obeyed. For instance, it is inadvisable chop vegetables after having mixed
them with the sauce, or to boil a pot of water before the pot is filled with water in the first place.
Equipped with structural inductive biases that naturally allow for temporally extended reasoning
over subtasks, hierarchical reinforcement learning (HRL) methods are well-suited for tasks with
complex high-level dependencies.

_∗Correspondence to rscostal@usc.edu_
[1Code and videos of agent trajectories are available at https://github.com/robbycostales/HAL](https://github.com/robbycostales/hal)


-----

Task Hierarchy Automata Stochasticity Affordances

**Goal** +1

(-1  )

+(1)

+(2) **?**

(-1  )

**Start** (3  ) (1  )

(a) (b) (c) (d)

Figure 1: Many real world tasks, like making PASTA, can be conceptualized as a hierarchy (a) of subtasks.
Automata-based approaches (b) map a history of subtask completion symbols to a context that indicates
progress in the hierarchy. Approaches that assume symbolic history deterministically defines progress are
not robust to stochastic changes in context (c) not provided symbolically. Hierarchical affordances (d) enable
us to use incomplete symbolic information in the face of stochasticity by grounding context in the present state.

Existing HRL methods fall along a spectrum ranging from flexible approaches that discover useful subtasks automatically, to the structured approaches that provide some prior information about

subtasks and their interdependencies. The former set of approaches (e.g. Vezhnevets et al., 2017;
Eysenbach et al., 2018) have seen limited success, as the automatic identification of hierarchical abstractions is an open problem in deep learning (Hinton, 2021). But approaches that endow the agent
with more structure, to make complex tasks feasible, do so at the cost of rigid assumptions. Methods
that use finite automatas (Fig. 1b) to express subtask dependencies (e.g. Icarte et al., 2020) require
the set of symbols, or atomic propositions, provided to the agent to be complete, in that the history
of symbols maps deterministically to the current context (i.e. how much progress has been made;
which subtasks are available). Importantly, these methods and many others (e.g. Andreas et al.,
2017; Sohn et al., 2020) consider subtasks to be dependent merely on the completion of others.

Unfortunately, these assumptions do not hold in the real world (Fig. 1c). For instance, if one completes the subtask cook noodles, but they clumsily spill them all over the floor, are they now
ready for the next subtask, mix noodles and sauce? While the subtask cook noodles is
somehow necessary for this further subtask, it is not sufficient to have completed it in the past. The
only way for automata-based approaches to handle this complexity is to introduce a new symbol that
indicates that the subtask has been undone. This is possible, but extraordinarily restrictive, since,
unless the set of symbols is complete, none of the subtask completion information can be used to
reliably learn and utilize subtask dependencies. Modeling probabilistic transitions allows the symbolic signal to be incomplete, but still requires a complete set of symbols, in addition to predefined
contexts. In order to make use of incomplete symbolic information, our approach instead learns
a representation of context grounded in the present state to determine which subtasks are possible
(Fig. 1d), rather than solely relying on symbols.

The contributions of this paper are as follows. First we introduce milestones (§4), which serve
the dual purpose of subgoals for training options (Sutton et al., 1999) and as high-level intents
(Kulkarni et al., 2016) for training our affordance model. Milestones are a flexible alternative to
atomic propositions used in automata-based approaches, and they are easier to specify due to less
rigid assumptions. Unlike a dense reward function, the milestone signal does not need to be scaled
or balanced carefully to account for competing extrinsic motives. Next, we introduce hierarchical
_affordances, which can be defined over any arbitrary set of milestones, and describe HAL (§6), a_
method which learns and utilizes a model of hierarchical affordances to prune impossible subtasks.
Finally, we demonstrate HAL’s superior performance on two complex hierarchical tasks in terms
of learning speed, robustness, generalizability, and ability to explore complex subtask hierarchies
without extrinsic supervision, relative to baselines provided with the same information (§7.3).

2 RELATED WORK

Multi-task RL methods take advantage of shared task structure in order to generalize to new tasks
from the same distribution (Andreas et al., 2017; Shiarlis et al., 2018; Devin et al., 2019; Sohn
et al., 2020; Lu et al., 2021). Sohn et al. (2020) learn subtask preconditions, but use symbol-based
contexts and do not learn and use their model of preconditions concurrently. Instead they assume a
naive policy can sufficiently reach all subtasks. Furthermore, they assume ground-truth affordances


-----

are provided at each step. Some works provide the agent with high-level task sketches (Andreas
et al., 2017; Shiarlis et al., 2018) describing the order in which subtasks must be completed. While
these sketches are advertised as “ungrounded” Andreas et al. (2017), they are in fact grounded by
the inclusion of short sketches, which are the first to be introduced to the agent in a curriculum
learning scheme (Bengio et al., 2009). Our approach instead uses a direct signal, which alone need
not determine task progress, and can learn without exposure to other tasks with shared structure.

In using a set of discrete symbols to indicate subtask completion, our work is similar to the variety
of approaches that apply temporal logic (TL) to the RL setting (Yuan et al., 2019; Hasanbeig et al.,
2018; 2020; Li et al., 2017; 2018). These works typically provide the agent with a TL formula, as
well as assignments of atomic propositions at each time-step. Some works use reward shaping to
encourage satisfaction of the formula (Li et al., 2017; 2018), whereas others convert the TL formula
to some finite state machine, which provides the agent with a structure that roughly expresses subtask
dependencies (Hasanbeig et al., 2018; 2020; Yuan et al., 2019). Icarte et al. (2020) bypass this
formula-to-automata conversion, and instead directly provide the automata to the agent in the form
of a reward machine (RM). While RMs are more expressive than LTL formulas, they are less flexible
than HAL, which can deal with incomplete sets of symbols, as well as context stochasticity.

Gibson (1977) introduces a theory of affordances, defined roughly as properties of the environment
which must be measured relative to the agent. Heft (1989) and Chemero (2003) clarify affordances
as relations between the agent and its environment. Khetarpal et al. (2020) formalize this relational
definition of affordances in the context of RL, and model which low-level actions, given corresponding intents, are afforded in each state. In this work, milestones represent high-level intents
corresponding to each subtask. They also demonstrate that modeling affordances speeds up and
improves planning through the pruning of irrelevant actions, and allows for the learning of more
accurate and generalizable partial world models. This approach does not directly translate to the
hierarchical setting because subtasks, unlike actions, may fail for reasons other than affordances,
meaning we do not have access to ground-truth affordance labels with which to train our model.
Manoury et al. (2019) and Khazatsky et al. (2021) present approaches that can discover and use
affordances to learn new skills, but their definition of affordances (i.e. a behavior is either afforded
or not, with no notion of preconditions) does not translate to the hierarchical setting.

3 PRELIMINARIES

Our setting involves learning behavior policies in Markov Decision Processes (MDP) using RL. An
MDP is defined by the state space S, action space A, reward function R : S × A → R, and state
transition distribution P : S ×A →△(S). The objective is to learn a policy, π : S →△(A), which
selects actions that maximize expected future returns: G(π) = E [[P][∞]t=0 _[γ][t][r][t][ |][ a][t][ ∼]_ _[π, s][t][ ∼]_ _[P]_ []][,]
where γ is the discount factor. Sutton et al. (1999) introduce the options framework, which flexibly models hierarchical abstractions with minimal modification to the RL paradigm. Each option,
_o :=_ _o, πo, βo_, is defined by an initiation set, _o_, indicating where the option can be selected,
the corresponding option policy, ⟨I _⟩_ _πo, and the termination condition, I_ _⊆S_ _βo : S_ [+] _→_ [0, 1], indicating the
probability of termination in each state. Options turn our typical MDP into a semi-Markov deci_sion process (SMDP) since the state transition distribution is, in general, no longer dependent on_
the current state and action, but also the present option, which was decided in a previous time-step.
The design of this framework allows options to be treated similarly to actions, except they may be
executed across multiple time-steps, interrupted, composed, and learned as separate subpolicies.

4 MILESTONES AND HIERARCHICAL AFFORDANCES

We consider tasks that can be decomposed into subtasks, each represented by a milestone symbol,
_g ∈G, where G is the set of symbols relevant to the task, and |G| = K. For each subtask, we_
introduce a separate option, ⟨Ig, πg, βg⟩, and we call πg a subpolicy. At each time-step, in addition
to the extrinsic reward signal provided by the environment to indicate success on the overall task,
we have access to a milestone signal, which is a vector b[t] where each element b[t]g
whether g ∈G was completed on time-step t. In our PASTA example, we might receive a milestone[∈{][0][,][ 1][}][ indicates]
each time we cut a vegetable, make the sauce, cook the noodles, etc. Milestones serve two main purposes. Firstly, milestones function as option subgoals (Sutton et al., 1999) that are in this work used
to train each subpolicy (discussed in Section 5). Secondly, each milestone represents the intent of
its corresponding subtask—similar to the action intents introduced to learn action-level affordances
in the work of Khetarpal et al. (2020)—which we use to learn hierarchical affordances (discussed in


-----

Section 6). In contrast to the standard options framework, primitive actions can only be executed as
part of an option’s subpolicy in our method. Generally, policies trained solely over options have no
guarantee of optimality (Sutton et al., 1999), but we ensure the existence of an optimal solution by
requiringour setting is standard, flat RL. Each additional milestone gK ∈G, where gK is the task’s final milestone (indicating task success). When g[′] added to G is useful as an intermediate G = {gk},
signal so long as g[′] corresponds to a unique behavior necessary for achieving gK.

_Hierarchical affordances are defined over G in the following way. The vector f_ _[s]_ = f _[∗](s) of size K_
represents which milestones are immediately achievable from the present state s, without requiring
the collection of any intermediate milestones, where f is a hierarchical affordance classifier, and f _[∗]_
is the optimal one[2]. Formally, fg[s] [= 1][ if at time][ t][0] [it is possible for future][ b]g[T] [= 1][ without any][ b]j[t] [=]
1, j ̸= g, where t0 < t < T . In PASTA, the milestone mix cooked noodles and sauce is
not afforded at the beginning since cook noodles is required first. A successful policy trained
within the vanilla options framework will eventually learn to execute options in contexts where
they are most useful, regardless of each option’s predefined initiation set. However, hierarchical
affordances give us a principled way to directly adjust this set: for subtask g, we can set Ig =
_{s | s ∈S, fg[s]_ [= 1][}][. One can think of hierarchical affordances as using milestones to impose a]
state-grounded subtask dependency structure on top of the options framework, which we can use
to prune impossible subtasks. If = _g[′], gK_, an affordance-aware agent with access to optimal
_G_ _{_ _}_
_f_ _[∗](s) will never initiate subtask gK from the beginning if g[′]_ is a necessary intermediate behavior.

Some logic-based RL approaches (e.g. Yuan et al., 2019; Icarte et al., 2020) use atomic proposi_tions as markers of subtask achievement to transition between contexts in a finite state machine._
These approaches, and many other HRL works (e.g. Andreas et al., 2017; Sohn et al., 2020) define subtask preconditions in terms of other subtasks. There are two forms of stochasticity that
hierarchical affordances, by virtue of being grounded in the present state, can more naturally address than symbolically-defined dependencies. We can conceptualize potential agent trajectories as
graphs where nodes represent the attainment of milestones, and edges are the segments between
them. Node stochasticity is affordance-affecting randomness that occurs either when milestones are
attained (e.g. receiving varying quantity of an item), or at the beginning of the episode (i.e. starting
in different contexts). Edge stochasticity is when affordances change at any time within a segment.
We treat edge stochasticity events as infrequent exceptions to the typical subtask dependency rules.
For example, after cook noodles is complete, mix cooked noodles and sauce is afforded, even if the agent may eventually spill the noodles on the floor. By grounding these rules in
the current state, an affordance-aware agent can detect and adapt to edge anomalies. In Section 6,
we describe in detail how hierarchical affordances are learned and used in stochastic environments
where symbols alone would fail to reliably determine the current context.

5 LEARNING CONTROLLERS

Like h-DQN (Kulkarni et al., 2016), we use a meta-controller that selects the current subtask to
attempt and a low-level controller which executes the subpolicy relevant to that subtask. The controller, π : S × G →△(A), selects low-level actions, a ∈A, given a state, s ∈S, and milestone,
_g_, and aims to maximize the expected milestone signal rewards, bg. Q-Learning (Watkins,
_∈G_
1989) trains these controllers by learning an estimate of the optimal Q-function: Q[∗]c [(][s, a][;][ g][) =]
such:maxπ π Eg(a _s, g∞t=0) =[γ][t][b] 1g[t]_ _[|]([ s]a[0] = arg max[=][ s, a][0]_ [=][ a, a]a′ Q[t]c([∼]s, a[π, s][′]; g[t] ))[∼]. Deep Q-Learning (Mnih et al., 2015) estimates[P] and deriving a policy from the Q-function as
P| 
_Q[∗]_ using deep neural networks. This Q-function is parameterized by θ = {θbase, ..., θg, ...}, where
_θbase is a set of shared base parameters and θg is a goal-specific head. It is updated via gradient_
descent on the following loss function, derived from the original Q-learning update:

2[#]

_LQc = E(st,at,rt,st+1,gt)∼Dc_ _Qc(st, at; gt, θ) −_ _b[t]g_ _[−]_ [max]at+1 _[Q][c][(][s][t][+1][, a][t][+1][;][ g][t][,][ ¯]θ)_ (1)

" 

where Dc is a replay buffer that stores previously collected transitions, and _θ[¯] are the parameters of a_
periodically updated target network. Both of these components are included to avoid the instability
associated with using function approximation in Q-Learning.

The meta-controller Π : S →△(G) aims to execute subtasks to maximize extrinsic rewards received by the environment. Again, we estimate a Q-function, this time over a dilated time scale

2Unlike option completion predictions (Precup et al., 1998), affordances predict possibility of success.


-----

_HAL meta-controller_ _HAL controller_

|achievement affordance context classifier meta-controller controller|Col2|Col3|
|---|---|---|
||||
||||



Figure 2: Left: Architecture diagram for complete HAL method. Q-values of the meta-controller are masked
by the output of the affordance classifier. The ϵ operator represents the standard ϵ-greedy action selection
procedure used in Q-learning, while ϵ[2] represents our affordance aware version. Right: For an optimal policy
(top), the mask will have no effect since Q values will naturally be low for unafforded subtasks. However,
a suboptimal policy (bottom) will benefit from a mask since it can be efficiently learned and used to prune
irrelevant subtasks before TD errors can propagate.

(i.e. we allow the low-level controllers to run for multiple steps before choosing new goals):
_Q[∗]mc[(][s, g][) =][ E]_ _Nt=0_ _[r][t][ + max][g][′][ Q]mc[∗]_ [(][s][N] _[, g][′][)][ |][ s][0]_ [=][ s, g][0] [=][ g, a][t] _[∼]_ _[π][g][, s][t]_ _[∼]_ _[P]_, where N is the
(variable) number of steps the option runs for. When collecting data in the environment, we addhP i
transitions (st, gt, _t_ _rt, st+N_ ) to a separate meta-replay buffer, Dmc, used to train our meta-Qfunction (parameterized by Θ) with a loss similar to Eq. 1, but without any goal-conditioning. In
Section 6 we describe how hierarchical affordances are integrated into this training procedure.

[P][t][+][N]

6 HIERARCHICAL AFFORDANCE LEARNING

In typical HRL methods, if the meta-controller is yet to receive extrinsic reward from the environment, there will be no preference for selecting any subtask over the others. However, by restricting
the selection of subtasks to ones that have proven merely to be possible, an agent can avoid wasting time attempting the impossible, and reach more fruitful subtasks faster. Suppose from experience, gained through random exploration, the agent achieves milestone g (where achievement means
_bg = 1) very often from the initial state set I, but never j ∈G, despite being able to achieve j in later_
states. With enough experience, the agent should become confident that j is not achievable without
completing other milestones first, and should not bother selecting j from any s ∈I, while g, and
any others that are achievable from those states, should instead be considered. If we had access to
an oracle function, f _[∗](s), that accurately computes hierarchical affordances for our task, we could_
prune impossible subtasks by masking the otherwise uninformed policy with the affordance oracle
output: p(g _s)_ _fg[s]_
approximate| f ∝(s) ≈ _f[∗][∗][Π](s[Θ])[(] from experience and leverage it in real-time for more effective learning.[g][|][s][)][. In the following sections, we describe a method that can learn an]_

**The false negative problem** Recall that f (s) outputs a vector f _[s], where each fg[s]_ [indicates the]
possibility of collecting milestone g from state s without requiring intermediate milestones. To train
each binary classification head, fg(s), we must somehow generate labeled data for each milestone.
Suppose an option was initialized at time to, and in time T milestone g is received. If no others were
received since the start of the option, we may assume that for any t where to _t_ _T_, the collection
of milestone g was afforded, so we can use the set of states _sto_ _, sto+1, . . ., s ≤_ _≤T_ as positive (i.e.
_fg[∗][(][s][) = 1][) training examples for the affordance classifier. Even if] {_ _[ g][ was not the intended milestone,] }_
we can still generate positive training examples for fg in this way. If an option has failed to collect
intended milestone g, either through timing out or collecting an unintended milestone, we might
be tempted to use the states encountered during that option as negative examples (i.e. fg[∗][(][s][) = 0][).]
However, this occurrence can either be indicative of the states not affording g, or that the subpolicy
corresponding to g is sub-optimal and has failed despite g being afforded. These false negatives
are a problem for any approach requiring function approximation via neural networks, which are
generally not robust to label noise (Song et al., 2020). It is particularly troublesome in our case
since the noise is greater than the true signal when the subpolicies are under-trained.


-----

**Context learning** Suppose we had access to an abstract state representation zaff[s] [=][ z]aff[∗] [(][s][)][, where]
any states si and sj are mapped to the same value only when f _[∗](si) = f_ _[∗](sj). With a representation_
that could cluster states in this way, we could trivially determine the falsity of a collected negative
_s ∈Dg[−]_ [by checking if][ z]aff[∗] [(][s][) =][ z]aff[∗] [(][s][j][)][ for any][ s][j][ ∈D]g[+][, that is, if we have encountered a]
true positive with the same representation. The classification procedure could be interpreted as
“labeling” these contexts with affordance values. This is somewhat of a “chicken and egg” problem,
since to learn affordances, we require a representation that maps states to contexts with the same
affordance values, which clearly requires some prior knowledge about affordances. Fortunately,
from Section 4, we know that affordances will only change when either (1) a milestone is collected
and (2) when edge stochasticity occurs. Since (2) is by definition a rare occurrence, states st and
_st+1 are more likely than not to satisfy f_ _[∗](st) = f_ _[∗](st+1), so long as they exist in the same segment_
between milestones. In this case, we can say that st and st+1 share the same achievement context,
**_z[s]_** = z(s). Let zψ(s) be an achievement context embedding represented by a differentiable function
parameterized by ψ. We can train zψ(s) from experience using the following contrastive loss:

_Lψ =_ _j_ _zψ(s[a]j_ [)][ −] _[z][ψ][(][s]j[p][)]_ 2 _[−]_ _zψ(s[a]j_ [)][ −] _[z][ψ][(][s]j[n][)]_ 2 [+][ α] + _[,]_

where each s[a]j [is a randomly chosen]X h _[ anchor][, each][2]_ _[ s]j[p]_ [is a][ positive][3][ example chosen within the][2] i
segment according to a (truncated) normal distribution, NT (0, σ[2]), centered around (and excluding)
_s[a]j_ [,][ s]j[n] [is chosen randomly among other segments and is treated as a][ negative][ example, and][ α][ is an]
arbitrary margin value. This loss pushes representations of states from the same achievement context
together, and pulls representations of states from different contexts apart. We show in Appendix B
that a wide range of σ produce useful representations. For our edge stochasticity experiments (Figure
5) we use a low σ = 2.0 to reduce the risk of sampling across affordance changes.

**False negative filtering** In the learned representation space, we expect false negative points to
be closer to positive points than true negatives. Given a negatively-labeled state sq for classifier
head fg, we compute[4] the mean distance from zψ(sq) to the representations of the k closest positive
points in a population uniformly sampled[5] from Dg[+][, denoted][ d]q[k][. We expect][ d][k]q [to be large for]
true negatives and small for false ones, and we can determine an effective separating margin in the
following way. First we compute distance scores for a random sample of positive points, denoted
_{d[k]p[}][, to use as reference. We ensure these points come from segments that are disjoint from the]_
population points’ segments to avoid trivially low scores that might skew the distribution. We then
fit a Gaussian distribution to {d[k]p[}][ and compute an upper confidence bound][ ρ][ for a given percentile]
value and confidence level. Any d[k]q _[< ρ][ is very similar to positive points in the representation space,]_
so we count sq as a false negative and exclude it from our training set. Note, we do not train head
_fg (and therefore do not reliably prune) until we have access to both positives and negatives for g._

**Method overview** The HAL architecture consists of a bi-level policy like h-DQN, a context embedding network, and an affordance classifier (see Figure 2), which are all learned concurrently (full
algorithm in Appendix E). Intuitively, the affordance classifier is able to generalize to a novel state,
_s, by first identifying the abstract achievement context, zψ(s), associated with the state, and then_
outputting an affordance value based on previous experience in that context. If zψ(s) has also not
been encountered, that context will not be strongly “labeled” either way, so we will not be invariably
pruning it. The meta-controller selects a subtask g at the beginning of the episode, and selects a new
subtask g[′] after collecting any milestone or whenever an option times out after a predefined number
of steps (our βg). At each step, the current state is fed to the controller, which outputs an action conditioned on the most recently selected subtask. After discretizing the classifier’s output to a binary
mask, we perform an affordance aware version of ϵ-greedy as follows. Given parameters ϵaff and
_ϵmc, we select a random subtask within the mask with probability ϵaff, randomly across all subtasks_
with probability ϵmc, and otherwise select greedily with respect to meta-Q within the mask.

7 EXPERIMENTS

In our experiments we aim to answer the following questions: (1) Does HAL improve learning in
tasks with complex dependencies? (2) Is HAL robust to milestone selection and context stochasticity? (3) Can HAL more effectively learn a diverse set of skills when trained task-agnostically?

3Here, the usage of “positive” and “negative” refers to whether points share the same achievement context.
4This procedure is akin to the particle entropy approach used in (Liu & Abbeel, 2021).
5For efficiency, we sample just enough points so that we are likely to cover all encountered contexts.


-----

Figure 3: Screenshots of CRAFTING (left) and TREASURE (right) environments. Displayed to the
right of the environments are each item’s ground-truth affordance indicator and inventory count.

7.1 ENVIRONMENTS

We evaluate our method, along with several baselines, on two complex environments with intricate
subtask dependency structures: CRAFTING and TREASURE. Both environments (visualized in Figure 3) are extensions of the minigrid framework (Chevalier-Boisvert et al., 2018). Agents receive
an egocentric image of the environment, as well as a vector describing their inventory (items picked
up from the environment and currently in their possession) as observations. The action spaces are
discrete and include actions for turning left/right, and moving forward/backward, as well as environment specific actions detailed below. Task hierarchies, walk-throughs of successful trajectories,
and additional information about both environments are included in Appendix A.

**CRAFTING is based on Minecraft, a popular open-ended video game in which players collect re-**
sources from their environment and use them to craft objects which can be used to then obtain more
resources. As such, the hierarchy of possible subtasks is immensely complex and presents a significant challenge for AI agents to reach subtasks deeper in the hierarchy. We develop an environment
that replicates this hierarchical complexity without the commensurate visuomotor complexity which
our method does not aim to address. In addition to movement actions, CRAFTING includes actions to
mine the object immediately in front of the agent (which requires an appropriate pickaxe), as well as
to craft and smelt the various objects (pickaxes, iron ingots, etc.). The full set of milestones contains
items that are either craftable or collectable. CRAFTING naturally contains node stochasticity since
the collection of certain items, due to the random procedural generation, requires slightly different
milestone trajectories across episodes (e.g. mining variable amount of stone to encounter diamond).

**TREASURE is a navigation task that requires the agent to collect various items and use them to**
unlock rooms to reach further items. The ultimate goal is to unlock a treasure chest, which requires a
sequence of collecting several keys, as well as placing an object on a weight-based sensor, in order to
open the requisite doors. Agents can only carry one object at a time, so they must reason about which
object to pick up based on what it will afford them (e.g. if the weight-based sensor room is locked,
the weight object is not currently useful). Like CRAFTING, TREASURE contains node stochasticity
due to the procedural generation. For example, the central room that the agent is spawned in can
contain either of the red or yellow key individually, or both together. Unlike CRAFTING, which has
a large action space to accommodate the various crafting recipes, this environment only contains
actions to move and a single “interaction” action that is used to pick up keys, open doors, etc. While
CRAFTING has a more complex hierarchy and greater diversity in the potential ordering of subtasks,
TREASURE has on average more difficult subtasks. The full set of milestones contains each object
the agent can successfully interact with in the environment (e.g. opening door, collecting key).

7.2 BASELINES Table 1: Summary of baselines.

Our set of baselines is summarized in Table 1. All
methods are based on the Rainbow (Hessel et al., Hier- Afford- Hind- False

archical ance sight Negative

2018) Deep Q-Learning algorithm, which combines Agent Mask Replay Filtering
several improvements to vanilla DQNs (Mnih et al., Oracle ✓ _Truth_ ✓ N/A
2015). To compensate for the lack of milestone sig- HAL (ours) ✓ Learned ✓ ✓
nals, non-hierarchical methods use a dense reward HAL(–FNF) ✓ Learned ✓ _×_
function that incorporates milestone signals for the H-RainbowH-Rainbow ✓ N/A _×_ N/A
first time each milestone is obtained in the episode. (+HER) ✓ N/A ✓ N/A
To evaluate the efficacy of our affordance classifier Rainbow _×_ N/A N/A N/A


-----

1.0

0.8

0.6

0.4

Success Rate

0.2

0.0

0.00 0.25 0.50 0.75 1.00 1.25

Step _×10[6]_


Oracle
**HAL (ours)**

HAL(–FNF)
H-Rainbow
H-Rainbow(+HER)
Rainbow

0 2 4 6 8

Step _×10[5]_


1.0

0.8

0.6

0.4

Sub-Policy Success Rate 0.2

0.0

0.0 0.2 0.4 0.6 0.8 1.0

Step _×10[6]_


Figure 4: Success rate over the course of training for CRAFTING iron task (left) and TREASURE
(center). Sub-policy success for TREASURE (right). Success rate is the proportion of episode where
the agent receives the target milestone, and sub-policy success is how often sub-policies, on average,
receive the correct milestone when called, before a timing out or collecting incorrect milestones.

online learning procedure, we compare our method to an “oracle” that differs only by using ground_truth affordances for masking subtasks. The node stochasticity inherent to both environments, as_
well as the edge stochasticity later explored, preclude the use of any methods that reason solely over
symbols (i.e. automata-, sketch-, or subtask dependency-based approaches). We also incorporate a
version of Hindsight Experience Replay (HER) (Andrychowicz et al., 2017) adapted for the discrete
milestone setting, which involves re-using “failed” trajectories that result in the collection of an unintended milestone (given the selected subpolicy) as successful data for the relevant subpolicy. For
instance, if an agent accidentally collects iron while executing its wooden pickaxe sub-policy, it can
use this trajectory to train its iron sub-policy.

7.3 RESULTS
**Learning efficacy** First, we evaluate the ability of HAL and our baselines to learn successful policies for complex tasks in each environment. Learning curves are shown in Figure 4 (plots depict
mean and 95% confidence interval over 5 seeds). In both environments, HAL significantly outperforms the strongest baseline, H-Rainbow(+HER) (HR+H), despite both methods receiving the same
information, and performs only slightly worse than the oracle, which has access to ground truth.
Incorporating HER into H-Rainbow leads to a significant improvement. False negative filtering (and
all other HAL components; see Appendix B) appears crucial for learning in the TREASURE environment, but not as much for CRAFTING, though in both cases filtering improves mask accuracy.
Removing false negative filtering causes HAL(-FNF) to be pessimistic (i.e. over-pruning subtasks,
see Figure 15 in Appendix D), ultimately leading to its unstable learning. Since masking impossible
subpolicies would have no impact on an optimal meta-controller, HAL’s success must stem from its
ability to learn a useful mask before TD errors are able to propagate through the meta-controller’s Q
function. HAL utilizes a more easily learnable function (affordance classifier) to reduce the amount
of unnecessary expensive learning (TD error propagation) required. We see from Figure 15 that,
throughout training, HAL’s mask has an impact on greedy subtask selection ∼60% of the time,
which is evidence that HAL avoids wasting time learning Q-values that the mask is able to prune.
Lastly, because affordance-aware methods are more likely to initiate subtasks in an appropriate context, we see they achieve a significantly higher average subpolicy success rate (Figure 4, right).

**Robustness to milestone selection** In this section we evaluate HAL’s robustness to the selection
of milestones. Affordances change when a milestone is removed since that milestone no longer acts
as an intermediate link between others. One downside of some approaches that use symbol-based
contexts is that an entirely different automata or subtask dependency graph must be defined over
the new set of symbols. HAL does not use prior information of this kind, so the learning process
is the same across all sets. Figure 5 shows HAL’s success on the CRAFTING environment’s iron
task when using “incomplete” milestone sets, relative to the full human-designed set. We see that
randomly removing 1 milestone makes no significant difference for HAL, and even after removing 4
milestones, HAL still achieves better performance than HR+H using the full set. HAL’s performance
drops when 5 milestones are removed likely due to the increased sparsity of the signal (i.e. greater
subtask length) and variance in milestone set quality. However, when we double the training time
for these same sets, we find that HAL is able to converge to a 97% success rate on at least one set,
while HR+H fails to converge on any set and ends with a maximum success rate of around 70%.


-----

1.0

1.0 None None

0.8 1/100 1/100

0.8 1/50 1/50

1/30 1/30

0.6

0.6

0.4

Success Rate 0.4 Success Rate

**HAL (ours)** 0.2

0.2

H-Rainbow(+HER)

0.0

11 10 9 8 7 6 0.25 0.50 0.75 1.00 1.25 0.25 0.50 0.75 1.00 1.25

# of Milestones Step _×10[6]_ Step _×10[6]_


Figure 5: Comparing the robustness of HAL and HR+H to varying milestone sets (left) and various
edge stochasticity frequencies (center and right, respectively) in CRAFTING iron task.

**Robustness to stochasticity** We modify CRAFTING so that at each environment step, there is a
certain probability that an item in the inventory will disappear. In order to make the task feasible, rare
items are less likely to disappear than common ones. This procedure produces edge stochasticity,
since the disappearance of items may alter affordances, and this can occur at any time. We test three
different levels of stochasticity, and display the learning curves in Figure 5. With a disappearance
frequency of 1/100 that cuts HR+H’s success rate in half, HAL is still able to reach its non-stochastic
success rate. With a frequency of 1/50, HAL performs comparably to HR+H with no stochasticity.
To put these stochasticity rates into context, the algorithm’s average episode length about halfway
through training is still over 1000 steps (see Figure 14 in Appendix C), meaning dozens of items
are removed from the agent’s inventory over the course of an episode. By learning a model of
affordances grounded in the present state, HAL is able to detect and adapt to these stochastic events.


**Task-agnostic learning** We next test the ability of HAL
to learn skills when no task-specific extrinsic rewards
(only milestones) are provided by the environment. Since
we cannot learn a meta-controller in the absence of rewards, we instead randomly select subtasks with some
probability ϵmc, and random afforded subtasks otherwise
(only for HAL). We evaluate both HAL and HR+H. In
Figure 6 we see that by the end of 10[6] steps, HAL is
able to more reliably complete the milestones deeper in
the hierarchy in the CRAFTING environment. We note
that HR+H is able to marginally outperform HAL in tasks
shallower in the hierarchy (e.g. wood pickaxe, stone, furnace), potentially as a result of failing to reach deeper
tasks and getting more practice on shallower ones. This
result is an indication of the general utility of HAL in environments with complex task hierarchies.


1.0

0.8

0.6

0.4


10


0.2

|Col1|Col2|Col3|Col4|
|---|---|---|---|
||||HAL (ours) H-Rainbow(+HER|
|||||
|||||
|Log|Wo|od|k B e ni Pi cS kt acc xh e St n F ur n ce e Pi c ko aa x|


**HAL (ours)**

H-Rainbow(+HER)

LogWoodStickWood PickaxeStoneFurnaceStone PickaxeCoalIron OreIron PickaxeIron Diamond


Subtask

Figure 6: Percentage of episodes where
each milestone is achieved in CRAFTING environment task-agnostic setting.


8 CONCLUSION AND FUTURE WORK
The present work can be viewed as a first step towards bridging the substantial gap between flexible
hierarchical approaches that are currently intractable, and methods that impose useful structures but
are too rigid to be of practical use. We introduce HAL, a method that is able to utilize incomplete
symbolic information in order to learn a more general form of subtask dependency. By grounding
subtask dependencies in the present state by learning a model of hierarchical affordances, HAL is
able to navigate stochastic environments that approaches relying solely on symbolic history are unable to. We demonstrate that HAL learns more effectively than baselines provided with the same
information, is more robust to milestone selection and affordance stochasticity, and can more thoroughly explore the environment’s subtask hierarchy. Given HAL’s flexible formulation and success
in the face of incomplete and stochastic symbolic information, we foresee future work integrating
HAL with option (or subgoal) discovery methods (e.g. Bacon et al., 2017; Machado et al., 2017;
Bagaria & Konidaris, 2019) to obtain performance gains in complex tasks without requiring prespecified milestones. Additionally, future work might be able to extend HAL to continuous goalspaces, but this would require revising the definition of hierarchical affordances provided here, as it
currently requires a notion of intermediate subgoal completion.


-----

9 ACKNOWLEDGEMENTS

We thank Natasha Jaques, S´ebastien Arnold, and the anonymous reviewers for their feedback
on mature drafts of this manuscript. This work is partially supported by NSF Awards IIS1513966/ 1632803/1833137, CCF-1139148, DARPA Award#: FA8750-18-2-0117, FA8750-19-10504, DARPAD3M - Award UCB-00009528, Google Research Awards, gifts from Facebook and
Netflix, and ARO# W911NF-12- 1-0241 and W911NF-15-1-0484.

10 REPRODUCIBILITY STATEMENT

All code for environments, HAL, and other relevant baseline algorithms is provided at the following
[link: https://github.com/robbycostales/HAL. We provide instructions for installing the necessary de-](https://github.com/robbycostales/hal)
pendencies, and enumerate commands that allow researchers to replicate results in this paper. Most
relevant hyperparameters and additional implementation details are also listed in the Appendix.

REFERENCES

Jacob Andreas, Marcus Rohrbach, Trevor Darrell, and Dan Klein. Neural module networks. In
_Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 39–48, 2016._

Jacob Andreas, Dan Klein, and Sergey Levine. Modular multitask reinforcement learning with
policy sketches. In International Conference on Machine Learning, pp. 166–175. PMLR, 2017.

Marcin Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob
McGrew, Josh Tobin, Pieter Abbeel, and Wojciech Zaremba. Hindsight experience replay. In
_Proceedings of the 31st International Conference on Neural Information Processing Systems, pp._
5055–5065, 2017.

Pierre-Luc Bacon, Jean Harb, and Doina Precup. The option-critic architecture. In Proceedings of
_the AAAI Conference on Artificial Intelligence, volume 31, 2017._

Akhil Bagaria and George Konidaris. Option discovery using deep skill chaining. In International
_Conference on Learning Representations, 2019._

Yoshua Bengio, J´erˆome Louradour, Ronan Collobert, and Jason Weston. Curriculum learning. In
_Proceedings of the 26th Annual International Conference on Machine Learning, ICML ’09, pp._
41–48, New York, NY, USA, June 2009. Association for Computing Machinery.

Anthony Chemero. An outline of a theory of affordances. Ecol. Psychol., 15(2):181–195, April
2003.

Maxime Chevalier-Boisvert, Lucas Willems, and Suman Pal. Minimalistic gridworld environment
[for openai gym. https://github.com/maximecb/gym-minigrid, 2018.](https://github.com/maximecb/gym-minigrid)

C Devin, D Geng, P Abbeel, T Darrell, and S Levine. Plan arithmetic: Compositional plan vectors
for multi-task control. In Neural Information Processing Systems (NeurIPS), 2019.

Benjamin Eysenbach, Abhishek Gupta, Julian Ibarz, and Sergey Levine. Diversity is all you need:
Learning skills without a reward function. In International Conference on Learning Representa_tions, 2018._

James J Gibson. The theory of affordances. Hilldale, USA, 1(2):67–82, 1977.

William H Guss, Brandon Houghton, Nicholay Topin, Phillip Wang, Cayden Codel, Manuela
Veloso, and Ruslan Salakhutdinov. Minerl: A large-scale dataset of minecraft demonstrations.
In IJCAI, 2019.

Danijar Hafner. Benchmarking the spectrum of agent capabilities. arXiv preprint arXiv:2109.06780,
2021.

Mohammadhosein Hasanbeig, Alessandro Abate, and Daniel Kroening. Logically-constrained reinforcement learning. arXiv preprint arXiv:1801.08099, 2018.


-----

Mohammadhosein Hasanbeig, Daniel Kroening, and Alessandro Abate. Deep reinforcement learning with temporal logics. In Formal Modeling and Analysis of Timed Systems, pp. 1–22. Springer
International Publishing, 2020.

Harry Heft. Affordances and the body: An intentional analysis of gibson’s ecological approach to
visual perception. J. Theory Soc. Behav., 19(1):1–30, March 1989.

Matteo Hessel, Joseph Modayil, Hado Van Hasselt, Tom Schaul, Georg Ostrovski, Will Dabney, Dan
Horgan, Bilal Piot, Mohammad Azar, and David Silver. Rainbow: Combining improvements in
deep reinforcement learning. In Thirty-second AAAI conference on artificial intelligence, 2018.

Geoffrey Hinton. How to represent part-whole hierarchies in a neural network. arXiv preprint
_arXiv:2102.12627, 2021._

Rodrigo Toro Icarte, Toryn Q Klassen, Richard Valenzano, and Sheila A McIlraith. Reward
machines: Exploiting reward function structure in reinforcement learning. _arXiv preprint_
_arXiv:2010.03950, 2020._

Alexander Khazatsky, Ashvin Nair, Daniel Jing, and Sergey Levine. What can I do here? Learning
new skills by imagining visual affordances. arXiv preprint arXiv:2106.00671, 2021.

Khimya Khetarpal, Zafarali Ahmed, Gheorghe Comanici, David Abel, and Doina Precup. What can
I do here? A theory of affordances in reinforcement learning. In International Conference on
_Machine Learning, pp. 5243–5253. PMLR, 2020._

Tejas D Kulkarni, Karthik Narasimhan, Ardavan Saeedi, and Josh Tenenbaum. Hierarchical deep
reinforcement learning: Integrating temporal abstraction and intrinsic motivation. Advances in
_neural information processing systems, 29:3675–3683, 2016._

X Li, C Vasile, and C Belta. Reinforcement learning with temporal logic rewards. In 2017 IEEE/RSJ
_International Conference on Intelligent Robots and Systems (IROS), pp. 3834–3839, September_
2017.

X Li, Y Ma, and C Belta. A policy search method for temporal logic specified reinforcement learning
tasks. In 2018 Annual American Control Conference (ACC), pp. 240–245, June 2018.

Hao Liu and Pieter Abbeel. Behavior from the void: Unsupervised active pre-training. arXiv preprint
_arXiv:2103.04551, 2021._

Yuchen Lu, Yikang Shen, Siyuan Zhou, Aaron Courville, Joshua B. Tenenbaum, and Chuang Gan.
Learning task decomposition with ordered memory policy network. In International Conference
_on Learning Representations, 2021._

Marlos C Machado, Marc G Bellemare, and Michael Bowling. A laplacian framework for option discovery in reinforcement learning. In International Conference on Machine Learning, pp.
2295–2304. PMLR, 2017.

Alexandre Manoury, Sao Mai Nguyen, and C´edric Buche. Hierarchical affordance discovery using intrinsic motivation. In Proceedings of the 7th International Conference on Human-Agent
_Interaction, pp. 186–193, 2019._

Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, Stig Petersen,
Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning.
_Nature, 518(7540):529–533, February 2015._

Doina Precup, Richard S Sutton, and Satinder Singh. Theoretical results on reinforcement learning
with temporally abstract options. In European conference on machine learning, pp. 382–393.
Springer, 1998.

Kyriacos Shiarlis, Markus Wulfmeier, Sasha Salter, Shimon Whiteson, and Ingmar Posner. Taco:
Learning task decomposition via temporal alignment for control. In International Conference on
_Machine Learning, pp. 4654–4663. PMLR, 2018._


-----

David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George van den Driessche,
Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, Sander Dieleman,
Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lillicrap, Madeleine
Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis. Mastering the game of go with
deep neural networks and tree search. Nature, 529(7587):484–489, January 2016.

Sungryull Sohn, Hyunjae Woo, Jongwook Choi, and Honglak Lee. Meta reinforcement learning
with autonomous inference of subtask dependencies. In International Conference on Learning
_Representations, 2020._

Hwanjun Song, Minseok Kim, Dongmin Park, Yooju Shin, and Jae-Gil Lee. Learning from noisy
labels with deep neural networks: A survey. arXiv preprint arXiv:2007.08199, 2020.

Richard S Sutton, Doina Precup, and Satinder Singh. Between MDPs and semi-MDPs: a framework
for temporal abstraction in reinforcement learning. Artif. Intell., 112(1-2):181–211, August 1999.

Alexander Sasha Vezhnevets, Simon Osindero, Tom Schaul, Nicolas Heess, Max Jaderberg, David
Silver, and Koray Kavukcuoglu. Feudal networks for hierarchical reinforcement learning. In
_International Conference on Machine Learning, pp. 3540–3549. PMLR, 2017._

Oriol Vinyals, Igor Babuschkin, Wojciech M Czarnecki, Micha¨el 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 S Vezhnevets, R´emi Leblond, Tobias Pohlen, Valentin Dalibard, David
Budden, Yury Sulsky, James Molloy, Tom L Paine, Caglar Gulcehre, Ziyu Wang, Tobias Pfaff,
Yuhuai Wu, Roman Ring, Dani Yogatama, Dario W¨unsch, Katrina McKinney, Oliver Smith, Tom
Schaul, Timothy Lillicrap, Koray Kavukcuoglu, Demis Hassabis, Chris Apps, and David Silver.
Grandmaster level in StarCraft II using multi-agent reinforcement learning. Nature, 575(7782):
350–354, November 2019.

Christopher John Cornish Hellaby Watkins. Learning from delayed rewards. PhD thesis, Cambridge
_University, 1989._

Lim Zun Yuan, Mohammadhosein Hasanbeig, Alessandro Abate, and Daniel Kroening. Modular
deep reinforcement learning with temporal logic specifications. arXiv preprint arXiv:1909.11591,
2019.

Shangtong Zhang. Modularized implementation of deep rl algorithms in pytorch. [https://](https://github.com/ShangtongZhang/DeepRL)
[github.com/ShangtongZhang/DeepRL, 2018.](https://github.com/ShangtongZhang/DeepRL)


-----

# Appendix

### Table of Contents

**A Additional Environment Details** **13**
A.1 CRAFTING . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

A.2 TREASURE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

A.3 Walk-throughs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

**B** **Ablation and Robustness Results** **16**
B.1 Component Ablations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

B.2 Hyperparameter Robustness . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

B.3 Varying σ under Stochasticity . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

**C Episode Length Plots** **17**

**D Affordance Plots** **18**

**E** **Algorithm** **19**

**F** **Implementation Details** **20**

A ADDITIONAL ENVIRONMENT DETAILS

In both environments, extrinsic rewards are a sparse binary signal provided upon the completion of
a final goal. Milestone signals are similarly formulated for each of the possible subtasks. For both
types of rewards (extrinsic and milestone) we introduce a per step penalty that encourages agents to
achieve their goal as quickly as possible. TREASURE and CRAFTING environments are extensions
of the minigrid framework (Chevalier-Boisvert et al., 2018).

A.1 CRAFTING

As discussed in Section 7.3, our CRAFTING environment is designed to maximize hierarchical complexity while minimizing visuomotor complexity, which we do not aim to address with our method.
Similar Minecraft-based environments have been used in the literature; however they do not meet
these requirements. The MineRL environment (Guss et al., 2019) provides an interface into the
full game of Minecraft; however, effective behavior in this environment requires learning complex
visuomotor policies in addition to understanding the hierarchical relationships between subtasks.
In order to evaluate our method effectively, we only aim to test the latter. Other work has used
Minecraft-inspired environments (Andreas et al., 2016; Sohn et al., 2020); however, these versions
involve simplified subtask hierarchies. Our environment replicates the complexity of the MineRL
subtask hierarchy while remaining perceptually simple. A concurrently developed environment contains similar hierarchical complexity while minimizing perceptual complexity (Hafner, 2021).

Figure 7 displays an abstract representation of the CRAFTING environment subtask hierarchy. Each
arrow points from one subtask to another, where the latter subtask requires the former in some
way. The CRAFTING environment contains a variety of dependency types. Many items must be
built or crafted from other resources. Some of these require the agent to be within the vicinity of a
crafting bench. Other items require specific pickaxes to be mined, and yet others must be smelted
in a furnace using a raw material and a fuel source. Another complexity missing from Figure 7 is
that crafting recipes require specific amounts of items. For instance, in our environment a stone
pickaxe requires three stone and two sticks. Each stone must be mined individually, resulting in
three separate milestones, while just two wood are required to craft four sticks. Lastly, there are


-----

Depth 1 2 3 4 5 6 7 8 9 10

iron

stick stone coal iron pickaxe

Milestones

stone

wood pickaxe

log wood iron ore diamond

pickaxe

crafting furnace

bench

Figure 7: Abstract representation of CRAFTING subtask hierarchy, where milestones are circled and
arrows indicate to explicit subtask dependencies between milestones and numbers indicate the depth
of each item in the hierarchy (used in Figure 6). Numerical preconditions for crafting recipes are not
shown, as well as other possible implicit environmental dependencies (e.g. mining x to reach y).

Depth 1 2 3 4 5 6 7 8 9

red green

door weight yellow door

Milestones

red yellow blue blue green purple treasure
key key door door key

key


Figure 8: Abstract representation of one possible TREASURE subtask hierarchy, where milestones
are circled and arrows indicate to explicit subtask dependencies between milestones.

other implicit dependencies than the ones shown, depending on the definition of the milestones
set. For example, although the only official prerequisite for obtaining diamond is having an iron
pickaxe, in practice, an agent will need to mine stone and other blocks to reach the diamond, and
the successful mining of each of these blocks may be considered a milestone.

CRAFTING is procedurally generated in the following way. For the lower half of the environment,
each cell is randomly assigned stone, coal, iron, or dirt to each cell with varying probabilities.
Diamond is randomly assigned to a cell in the bottom-most layer. Trees (from which logs are
obtained) are abundantly scattered in the upper half, and a few irrelevant dirt blocks are placed in
this region as well. If the generated environment does not have enough resources, it is regenerated
with the next random seed.

A.2 TREASURE

In Figure 8 one possible TREASURE subtask hierarchy is displayed. Unlike CRAFTING, there are
multiple different abstract hierarchies depending on the initial state of the environment. At the
beginning of each episode, either both keys are available, only the yellow key, or only the red key
(the instance shown in Figure 8). While the environment dynamics remain the same across all
episodes, the agent must infer which hierarchy is appropriate based on the initial configuration of
the environment. TREASURE is procedurally generated by randomly assigning each colored door to
the room entrances, randomly determining which keys are accessible from the starting room, and
lastly placing all objects behind their appropriate doors at random positions within the room.

A.3 WALK-THROUGHS

Successful human walk-throughs for both TREASURE and CRAFTING environments are described in
Figures 9 and 10 respectively.


-----

(a) Agent is initialized in the central (b) Agent picks up the the red key
room, with only the red key and moves toward the red door.
afforded. Note that the red door milestone is

now afforded.

(d) Agent opens the door to the (e) Agent picks up the ball and
room with the scale by first drops it on the scale, opening up the
proceeding into the left-side room room containing the final key.
and picking up the blue key.


(c) Agent opens the red door and
must choose between two possible
afforded subtasks. Only the yellow
key will result in further progress,
as the green weight must be placed
on the scale in the locked room on
the right.

(f) Agent picks up the purple key,
and the final desired milestone
(treasure) is now afforded.


Figure 9: Walk-through of a successful TREASURE task episode. Items currently in the agent’s
possession are indicated by the numbers on the right hand side and ground-truth affordances are
indicated by green circles if the milestone is afforded and red if not.


(a) Agent is initialized in the
“woods” surrounded by trees, with
only logs afforded.

(d) Agent collects stone that it uses
to create a furnace and stone
pickaxe.


(b) Agent collects logs, and
converts them into wood and sticks.

(e) Agent uses the stone pickaxe to
collect iron ore and coal which it
turns into iron ingots, which in turn
are crafted into an iron pickaxe.


(c) Agent uses sticks and wood to
create a crafting bench and wood
pickaxe.

(f) With the iron pickaxe, the agent
can finally reach and mine
diamond, the final goal.


Figure 10: Walk-through of successful CRAFTING environment diamond task episode.


-----

B ABLATION AND ROBUSTNESS RESULTS

B.1 COMPONENT ABLATIONS


In Figure 11 we plot success on TREASURE after removing various integral components of the full
HAL method. We find that all components introduced in this work are necessary for achieving the
best performance on this task. The only variation that also reliably converges to 100% success rate
is when the affordance classifier is provided with the raw state as input rather than using the learned
representation, but this variation is undesirable since more learnable parameters are introduced.






1.0

0.8

0.6

0.4

Success Rate

0.2

0.0

0 2 4 6 8

Step _×10[5]_


4000

**HAL (ours)**
**–RAI**

3000 **–RT**

**–CL**
**–FNF**

2000 **–FNF,RAI**

Episode Length

1000

0

0 2 4 6 8

Step _×10[5]_


Figure 11: Training curves for component-wise ablations of HAL on TREASURE task. HAL refers
to the full method, while the rest of the items displayed in the legend indicate which components
are removed. −RAI no longer uses the context representation as input to the affordance classifier
(the classifier is trained directly over the state). −RT no longer uses affordance classifier loss to
additionally tune the context representation weights. −CL removes the contrastive loss altogether,
allowing the weights to be trained solely with affordance classifier gradients. Lastly, −FNF no
longer filters false negatives using the learned context representation.

B.2 HYPERPARAMETER ROBUSTNESS


In Figure 12 we demonstrate HAL’s robustness to modifications of the most significant newly introduced hyperparameters on the TREASURE task. In only two cases over the wide range of values we
tested did all runs not converge. The first is when the upper confidence bound percentile is set too
low, which results in more false negatives being left unfiltered. The second is when the affordance
classifier threshold is set too low, which results in less pruning. We see that a wide range of more
aggressive settings for both of these hyperparameters are reliable. We find that the standard deviation hyperparameter is not sensitive across the values we test in the non-edge-stochastic TREASURE
environment, and that lower values (e.g. σ = 2.0), which we initially hypothesized might fare better
with edge stochasticity but could lead to worse representations, are in actuality still effective.






1.0

0.8

0.6

Success Rate 0.4

0.2

0.0

0.83 0.87 0.90 0.93 0.97

Upper Confidence Bound Percentile


2 5 7 9 12

Sampling Distribution Standard Deviation


**HAL (ours)**
HR+H mean

0.3 0.4 0.5 0.6 0.7

Affordance Classifier Threshold


Figure 12: Plots comparing HAL’s final success rate with that of HR+H’s on TREASURE task with
alternative hyperparameter settings. Left: percentile values used for defining the upper confidence
bound ρ for false negative filtering. Center: standard deviation values, σ, used for sampling positive
points from the (truncated) normal distribution in the contrastive loss. Right: threshold value over
which the affordance classifier output is discretized.


-----

B.3 VARYING σ UNDER STOCHASTICITY

In Appendix B.2, we demonstrated that in TREASURE, various values of σ centered around the value
we used in that setting (σ = 7.0) are all conducive to good performance on that task. In Figure 13,
we plot the results of using different values in a stochastic version of the CRAFTING environment in
the iron task. Although all values lead to significantly better performance than HR+H, the value
we happened to used in this setting (σ = 2.0) appears to strike the best balance. Very low values
(e.g. σ = 1.0) likely do not learn as general a context representation, while higher values (e.g.
_σ = 8.0, 16.0) are more likely to sample positive points across occurrences of edge stochasticity. It_
is intriguing that the final loss for σ = 2.0 is lower than for σ = 1.0. We speculate that the context
learned by sampling points too close to the anchor could be a less natural representation to learn
than a more general one, which considers further points.




**HAL (ours)**

0.0030 0.8 HR+H mean

0.0025 0.6

0.0020 Success Rate 0.4

Contrastive Loss

0.0015

0.2

1 2 4 8 16 1 2 4 8 16

Sampling Distribution Standard Deviation Sampling Distribution Standard Deviation


Figure 13: Plots evaluating the efficacy of various σ values used for the contrastive loss in a stochastic CRAFTING environment on the iron task, with item disappearance rate 1/50 steps. Left: final
contrastive loss values for HAL. Right: final HAL success rates compared to HR+H.

C EPISODE LENGTH PLOTS


In Figure 14 we display the episode length plots corresponding to the success rate results shown in
Figures 4 and 5.





4000

3000

2000

Episode Length

1000

0.00 0.25 0.50 0.75 1.00 1.25

Step _×10[6]_


Oracle
**HAL (ours)**

3000

HAL(–FNF)
H-Rainbow

2000 H-Rainbow(+HER)

Rainbow

1000

0

0 2 4 6 8

Step _×10[5]_


None None

4000

1/100 1/100

1/50 1/50

3000 1/30 1/30

2000

Episode Length

1000

0.25 0.50 0.75 1.00 1.25 0.25 0.50 0.75 1.00 1.25

Step _×10[6]_ Step _×10[6]_


Figure 14: Episode length over the course of training for all baselines on CRAFTING iron (top
left) and TREASURE (top right), corresponding to Figure 4. Episode length with variable levels of
stochasticity CRAFTING iron (bottom), corresponding to Figure 5.


-----

AFFORDANCE PLOTS


We provide metrics tracked over the course of training for affordance masking as well as false
negative filtering in Figure 15. The mask metrics (Figure 15a for CRAFTING iron and Figure 15c
for TREASURE) consist of (from left to right):

-  Affordance Classifier Accuracy: The accuracy of the affordance classifier w.r.t truth.



-  Mask Impact: The percentage of times that the affordance mask prevents selecting an subtask that would have otherwise had the highest Q-value.

-  Pruning Percentage: Percentage of subtasks pruned.



-  Overpruning Percentage: Percentage of subtasks that are afforded but are pruned.

-  Underpruning Percentage: Percentage of subtasks that are not afforded but are not pruned.


The false negative filtering metrics (Figure 15b for CRAFTING iron and Figure 15d for TREASURE)
consist of:

-  Filtering Margin: L2 distance at which we consider negatives to be true negatives.



-  True Negative Accuracy: Percentage of true negatives falling above filtering margin.

-  False Negative Accuracy: Percentage of false negatives falling below filtering margin.



-  Percentage False Negatives: Percentage of negatives that are false negatives.

-  False Negatives Flagged: Percentage of negatives that are flagged as false by our margin.












1.0 1.0 1.0 1.0 1.0

0.8 0.8 0.8 0.8 0.8

0.6 0.6 0.6 0.6 0.6

0.4 Method Mask Impact 0.4 0.4 0.4 0.4

Affordance Classifier Accuracy 0.2 OracleHALHAL( (ours)–FNF) 0.2 Pruning Percentage 0.2 Overpruning Percentage 0.2 Underpruning Percentage 0.2

0.0 0.0 0.0 0.0 0.0

0.0 0.5 1.0 1.5 0.0 0.5 1.0 1.5 0.0 0.5 1.0 1.5 0.0 0.5 1.0 1.5 0.0 0.5 1.0 1.5

Step _×10[6]_ Step _×10[6]_ Step _×10[6]_ Step _×10[6]_ Step _×10[6]_


(a) Mask metrics for CRAFTING environment iron task.






14 Method 1.0 1.0 1.0 1.0

12 **HAL (ours)** 0.8 0.8 0.8 0.8

10 0.6 0.6 0.6 0.6

8 0.4 0.4 0.4 0.4

KNN Filtering Margin 6 True Negative Accuracy 0.2 False Negative Accuracy 0.2 Percentage False Negatives 0.2 False Negatives Flagged 0.2

0.0 0.0 0.0 0.0

0.0 0.5 1.0 1.5 0.0 0.5 1.0 1.5 0.0 0.5 1.0 1.5 0.0 0.5 1.0 1.5 0.0 0.5 1.0 1.5

Step _×10[6]_ Step _×10[6]_ Step _×10[6]_ Step _×10[6]_ Step _×10[6]_

(b) KNN filtering metrics for CRAFTING environment iron task.











1.0 1.0 1.0 1.0 1.0

0.8 0.8 0.8 0.8 0.8

0.6 0.6 0.6 0.6 0.6

0.4 Method Mask Impact 0.4 0.4 0.4 0.4

Affordance Classifier Accuracy 0.2 OracleHALHAL( (ours)–FNF) 0.2 Pruning Percentage 0.2 Overpruning Percentage 0.2 Underpruning Percentage 0.2

0.0 0.0 0.0 0.0 0.0

0.0 0.2 0.4 0.6 0.8 1.0 0.0 0.2 0.4 0.6 0.8 1.0 0.0 0.2 0.4 0.6 0.8 1.0 0.0 0.2 0.4 0.6 0.8 1.0 0.0 0.2 0.4 0.6 0.8 1.0

Step _×10[6]_ Step _×10[6]_ Step _×10[6]_ Step _×10[6]_ Step _×10[6]_


(c) Mask metrics for TREASURE environment.








1.0 1.0 1.0 1.0

Method

4 **HAL (ours)** 0.8 0.8 0.8 0.8

3 0.6 0.6 0.6 0.6

0.4 0.4 0.4 0.4

2

KNN Filtering Margin True Negative Accuracy 0.2 False Negative Accuracy 0.2 Percentage False Negatives 0.2 False Negatives Flagged 0.2

1

0.0 0.0 0.0 0.0

0.0 0.2 0.4 0.6 0.8 1.0 0.0 0.2 0.4 0.6 0.8 1.0 0.0 0.2 0.4 0.6 0.8 1.0 0.0 0.2 0.4 0.6 0.8 1.0 0.0 0.2 0.4 0.6 0.8 1.0

Step _×10[6]_ Step _×10[6]_ Step _×10[6]_ Step _×10[6]_ Step _×10[6]_


(d) KNN filtering metrics for TREASURE environment.

Figure 15


-----

E ALGORITHM

**Algorithm 1 Learning procedure for HAL**

1: Initialize replay buffer for meta-controller (Dmc), controllers (Dc), positive affordance examples
(Dg[+][), potential negative examples (][D]g[−][) for each goal][ g][ ∈G][, and parameters for meta-controller]
(Θ), controllers (θ), achievement context function (ψ), and affordance classifier (φ).

2: steps ← 0
3: while steps < max steps do
4: env steps, option steps ← 0

5: Receive initial state, s, from the environment

6: **while s is not terminal or env steps < max env steps do**

7: **if env steps = 0 or option steps > max option steps or** _j_ **[b][j][ >][ 0][ then]**

8: option steps ← 0

9: **if env steps > 0 then**

[P]

10: Store transition (sinit, g, bg, s) in Dmc

11: Store examples st _t_ [init, env steps] in positive buffers Dj[+]
_|_ _∈_

12: where bj = 1 and negative buffers Dk[−] [where][ b][k][ = 0]

13: **end if**

14: init ← env steps

15: **f** _[s]_ _fφ(zψ(s))_ _▷_ Get predicted affordances
_←_

16: **q ←** _Qmc(s, · ; Θ)_ _▷_ Compute Q-values for all goals

19:18:17: _ggqaffmaxj ←−∞∀ ← ←Randarg max(fjj[s] | f[= 0] qj[s]_ [= 1)] _▷▷Get randomMask non-afforded goals▷_ Get best afforded afforded goal goal

20:21: _gg ←rand ←gaff w.pRand ϵaff(G, g)_ rand w.p ϵmc, else gmax _▷ϵ[2]-greedy goal selection▷_ Get random goal

22: **end if**

24:25:23: _aaa ←randmax ← ←arandarg maxRand w.p ϵ(Ac, Q else)_ c(s, a ·max ; g, Θ) _▷_ Get best action – conditioned on goal▷ϵ-greedy action selection▷ Get random action

26: steps + +, option steps + +, env steps + +

27: Send action a to the environment and receive next state s[′], rewards r, and milestones b

28: Store transition (s, a, r, s[′], g) in Dc

29: _s ←_ _s[′]_

30: **if steps % update freq = 0 then**

31: Sample batch of transitions from Dc and use it to update θ via Q-learning loss

32: **end if**

33: **if steps % meta update freq = 0 then**

34: Sample batch of transitions from Dmc and use it to update Θ via Q-learning loss

35: **end if**

36: **if steps % margin update freq = 0 then**

37: Sample disjoint sets of positive examples from Dg[+] [and update negative filtering]

38: margin

39: **end if**

40: **if steps % aff update freq = 0 then**

41: Sample positive and negative examples from Dg[+] [and][ D]g[−] [respectively to update][ φ]

42: with binary cross entropy loss (ignoring any negatives with computed distance

43: scores less than false negative filtering margin)

44: **end if**

45: **if steps % rep update freq = 0 then**

46: Sample anchor, positive, and negative states from Dc to update ψ via contrastive loss

47: **end if**

48: **end while**

49: end while
50:


-----

F IMPLEMENTATION DETAILS

All experiments are run with 5 random seeds each. We use 4 parallel environments for data collection with all methods. We do not include Noisy Nets or C51 in our implementation of Rainbow,
as we do not find them to improve performance in our domains and only increase training time.
Hyperparameters are shown in Table 2. All update frequency parameters are computed with respect
to total environment steps (across parallel environments). Relative to the controller’s Q-learning updates, all other algorithmic mechanisms are updated less frequently for the sake of efficiency, at rates
which do not appear to affect the performance of our method. The meta-controller, affordance classifier, and the context representation are all trained every 10 controller updates. Since the optimal
separation margin between false negatives and true negatives changes slowly over time, and each
computation is expensive, each classifier head’s margin is updated every 150 controller updates.

Table 2: Hyperparameters used in HAL and baselines

Name Description Value

adam lr Adam learning rate (across all networks) 0.000625
adam eps Adam epsilon 0.00015
batch size Training batch size 32

_λ_ Discount factor 0.99
targ update Target network update frequency 10[3]
exp steps Exploration steps before updates 400
_ϵc_ Epsilon used in controller’s ϵ-greedy procedure 0.5 0.05
_ϵmc_ Epsilon used in meta-controller’s ϵ-greedy procedure 0.2 0.05
_ϵaff_ Affordance eps. used to randomly select within mask 0.8 0.00

n steps # of steps used for n-step returns 10

max option steps Maximum option steps before timeout 50


update freq Freq. of controller weight updates 4
meta update freq Freq. of meta-controller weight updates 40
margin update freq Freq. that false negative filtering margins are updated 600
aff update freq Freq. of affordance classifier weight updates 40
rep update freq Freq. of context representation weight updates 40

_σ_ Standard deviation used for inter-context sampling 7.0
_σstoch_ _σ used for edge stochasticity runs_ 2.0
knn n # of points used for sampling for KNN procedure 1000
knn k # of nearest neighbors used for KNN procedure 1
fnf conf Confidence value used for upper confidence bound 0.95
fnf perc Percentile value used for upper confidence bound 0.9


-----

