POSSIBILITY BEFORE UTILITY: LEARNING AND USING HIERARCHICAL AFFORDANCES
Year: 2021

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 Hierarchical Affordance Learning (HAL), a method that learns a model of hierarchical affordances in order to prune impossible subtasks for more effective learning. Existing 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.

heading: 1 INTRODUCTION
text: 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.
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 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 a form of finite automata (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).

heading: 2 RELATED WORK
text: 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.

heading: 3 PRELIMINARIES
text: 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 → 4(S). The objective is to learn a policy, π : S → 4(A), which selects actions that maximize expected future returns: G(π) = E [ ∑∞ t=0 γ
trt | at ∼ π, st ∼ 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 := 〈Io, πo, βo〉, is defined by an initiation set, Io ⊆ S, indicating where the option can be selected, the corresponding option policy, πo, and the termination condition, βo : S+ → [0, 1], indicating the probability of termination in each state. Options turn our typical MDP into a semi-Markov decision 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.

heading: 4 MILESTONES AND HIERARCHICAL AFFORDANCES
text: 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 bt where each element btg ∈ {0, 1} indicates whether g ∈ G was completed on time-step t. In our PASTA example, we might receive a milestone 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 requiring gK ∈ G, where gK is the task’s final milestone (indicating task success). When G = {gk}, our setting is standard, flat RL. Each additional milestone g′ added to G is useful as an intermediate 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 fs = 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 one1. Formally, fsg = 1 if at time t0 it is possible for future b T g = 1 without any b t j = 1, j 6= 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, fsg = 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 = {g′, gK}, an affordance-aware agent with access to optimal 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 propositions 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.

heading: 5 LEARNING CONTROLLERS
text: 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 → 4(A), selects low-level actions, a ∈ A, given a state, s ∈ S, and milestone, g ∈ G, and aims to maximize the expected milestone signal rewards, bg . Q-Learning (Watkins, 1989) trains these controllers by learning an estimate of the optimal Q-function: Q∗c (s, a; g) = maxπ E [∑∞ t=0 γ tbtg | s0 = s, a0 = a, at ∼ π, st ∼ P ]
and deriving a policy from the Q-function as such: πg(a|s, g) = 1(a = arg maxa′ Qc(s, a′; g)). Deep Q-Learning (Mnih et al., 2015) estimates 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:
LQc = E(st,at,rt,st+1,gt)∼Dc [( Qc(st, at; gt, θ)− btg −max
at+1 Qc(st+1, at+1; gt, θ̄)
)2] (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 → 4(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
1Unlike option completion predictions (Precup et al., 1998), affordances predict possibility of success.
(i.e. we allow the low-level controllers to run for multiple steps before choosing new goals): Q∗mc(s, g) = E [∑N t=0 rt + maxg′ Q ∗ mc(sN , g ′) | s0 = s, g0 = g, at ∼ πg, st ∼ P ] , where N is the (variable) number of steps the option runs for. When collecting data in the environment, we add transitions (st, gt, ∑t+N 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.

heading: 6 HIERARCHICAL AFFORDANCE LEARNING
text: 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) ∝ fsg ∗ ΠΘ(g|s). In the following sections, we describe a method that can learn an approximate f(s) ≈ f∗(s) from experience and leverage it in real-time for more effective learning. The false negative problem Recall that f(s) outputs a vector fs, where each fsg 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, . . . , sT } as positive (i.e. f∗g (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. f∗g (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 zsaff = 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 ∈ D−g by checking if z∗aff(s) = z∗aff(sj) for any sj ∈ 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, zs = 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ψ(saj )− zψ(spj )∥∥22 − ∥∥zψ(saj )− zψ(snj )∥∥22 + α]+ , where each saj is a randomly chosen anchor, each s p j is a positive
2 example chosen within the segment according to a (truncated) normal distribution,NT (0, σ2), centered around (and excluding) saj , s n j 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 compute3 the mean distance from zψ(sq) to the representations of the k closest positive points in a population uniformly sampled4 from D+g , denoted dkq . We expect dkq 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 {dkp}, 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 {dkp} and compute an upper confidence bound ρ for a given percentile value and confidence level. Any dkq < ρ 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.

heading: 7 EXPERIMENTS
text: 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?
2Here, the usage of “positive” and “negative” refers to whether points share the same achievement context. 3This procedure is akin to the particle entropy approach used in (Liu & Abbeel, 2021). 4For efficiency, we sample just enough points so that we are likely to cover all encountered contexts.

heading: 7.1 ENVIRONMENTS
text: 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 resources 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.
Hierarchical Agent Affordance Mask Hindsight Replay False Negative Filtering
Oracle X Truth X N/A HAL (ours) X Learned X X HAL(–FNF) X Learned X × H-Rainbow X N/A × N/A H-Rainbow
(+HER) X N/A X N/A Rainbow × N/A N/A N/A Our set of baselines is summarized in Table 1. All methods are based on the Rainbow (Hessel et al., 2018) Deep Q-Learning algorithm, which combines several improvements to vanilla DQNs (Mnih et al., 2015). To compensate for the lack of milestone signals, non-hierarchical methods use a dense reward function that incorporates milestone signals for the first time each milestone is obtained in the episode. To evaluate the efficacy of our affordance classifier
online learning procedure, we compare our method to an “oracle” that differs only by using groundtruth 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.

heading: 7.3 RESULTS
text: 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. 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 successful 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 Figures 15a and 15c in the 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 (the 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%.
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 106 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.

heading: 8 CONCLUSION AND FUTURE WORK
text: The present work can be viewed as a first step towards bridging the substantial gap between flexible hierarchical approaches that are presently 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.

heading: 9 REPRODUCIBILITY STATEMENT
text: All code for environments, algorithms, and baselines is provided at the following link: https://github.com/jamesdoewhat/hal-anonymous. We enumerate the list of commands to reproduce all experiments in the paper, as well as a file specifying the python packages and versions required which can be installed via the Anaconda python package manager. All hyperparameters and additional implementation details are listed in the Appendix.

heading: A Additional Environment Details 13
text: A.1 CRAFTING . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 A.2 TREASURE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 A.3 Walk-throughs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

heading: B Ablation and Robustness Results 16
text: B.1 Component Ablations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 B.2 Hyperparameter Robustness . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 B.3 Varying σ under Stochasticity . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

heading: C Episode Length Plots 17

heading: D Affordance Plots 18

heading: E Algorithm 19
text: F Implementation Details 20

heading: A ADDITIONAL ENVIRONMENT DETAILS
text: 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
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.

heading: B ABLATION AND ROBUSTNESS RESULTS
text: 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.
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.
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.

heading: C EPISODE LENGTH PLOTS
text: In Figure 14 we display the episode length plots corresponding to the success rate results shown in Figures 4 and 5.

heading: D AFFORDANCE PLOTS
text: 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 sub-
task 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:

heading: E ALGORITHM
text: Algorithm 1 Learning procedure for HAL 1: Initialize replay buffer for meta-controller (Dmc), controllers (Dc), positive affordance examples
(D+g ), 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 bj > 0 then 8: option steps← 0 9: if env steps > 0 then
10: Store transition (sinit, g,bg, s) in Dmc 11: Store examples st | t ∈ [init,env steps] in positive buffers D+j 12: where bj = 1 and negative buffers D−k where bk = 0 13: end if 14: init← env steps 15: fs ← fφ(zψ(s)) . Get predicted affordances 16: q← Qmc(s, · ; Θ) . Compute Q-values for all goals 17: qj ← −∞ ∀ fsj = 0 . Mask non-afforded goals 18: gmax ← arg maxq . Get best afforded goal 19: gaff ← Rand(j | fsj = 1) . Get random afforded goal 20: grand ← Rand(G) . Get random goal 21: g ← gaff w.p aff, grand w.p mc, else gmax . 2-greedy goal selection 22: end if 23: amax ← arg maxQc(s, · ; g,Θ) . Get best action – conditioned on goal 24: arand ← Rand(A) . Get random action 25: a← arand w.p c, else amax . -greedy action selection 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 D+g and update negative filtering 38: margin 39: end if 40: if steps%aff update freq = 0 then 41: Sample positive and negative examples from D+g 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 fromDc 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 significantly 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 computing a new margin is expensive, each classifier head’s margin is updated every 150 controller updates.

Review summaries:
This paper is in the realm of hierarchical reinforcement learning, and the aim is to employ a particular kind of affordance model: milestones of subtasks which can be achieved and a coupling between states and "affordable" subgoal completion (from that state). Basically, this makes it possible to limit action choices (or more general: bias choices) to actions/subpolicies for which it is known from experience that they are in reach from this state with this action/subpolicy. The paper introduces the HAL method, in which an indicator function for the milestones, a state generalization function (mapping similar affordance abilities to similar abstract states), and low level and hight level Q-functions are all learned in parallel. Using two domains, the method is evaluated and put against competetive baselines and it is shown that there are benefits in general, but also for specific aspects such as inexact milestone knowledge or stochasticity.

The paper proposes Hierarchical Affordance Learning (HAL) that predicts sub-task affordance grounding on the current state. The affordance prediction can be used to prune impossible subtasks leading to a more efficient exploration.  The paper proposes a trick called "predicting achievement context, " which filters out false-negative samples during affordance classification.  The paper presents experiments on CRAFTING and TREASURE that demonstrate the proposed method's effectiveness and provides extensive ablation studies.

Given a task hierarchy specified as a dependency graph of milestones, this work employs a two-level hierarchical reinforcement-learning method similar to Kulkarni et al. 2016.  The lower level learns to achieve a given milestone in a classical fashion, while the upper level learns to choose milestones such that ultimately the agent will achieve the overall goal.  The core contribution is a method for pruning candidate milestones (upper-level actions) that are not currently achievable (afforded to the agent by the environment), using an affordance classifier trained on the fly.

This paper incorporates the concept of affordances (the idea that humans and agents perceive the world in terms of relevant action possibilities) from ecological psychology with hierarchical reinforcement learning. While affordance theory has been previously incorporated into agent action-reasoning-perception models and more recently with reinforcement learning, this work specifically looks at incorporating the concept with HRL. This is significant because many complex problems need to be broken down into subtasks. One of the challenges of many RL domains is the large action spaces that agents have to explore. While HRL helps to reduce this burden by breaking down a complex task into sub-tasks the incorporation of an affordance concept can further reduce the action space which the agent needs to consider. This paper combines these two ideas and has the potential to allow researchers to use RL in more challenging domains.  The paper develops a theoretical framework for combining affordances with HRL and conducts a number of experiments in two simple grid world domains allowing for comparison with baseline RL algorithms.