Possibility Before Utility: Learning And Using Hierarchical Affordances
Authors: Robby Costales
Shariq Iqbal
Fei Sha
Venue: ICLR 2022 Spotlight (2022)
Keywords: RL
HRL
reinforcement learning
hierarchical reinforcement learning
affordances
hierarchical affordances

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.

Published as a conference paper at ICLR 2022
POSSIBILITY BEFORE UTILITY: LEARNING AND USING HIERARCHICAL AFFORDANCES
Robby Costales' Shariq Iybal'
Fei Sha? University of Southern California
?Google 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 con- sider ones they deem possible in the first place. By focusing only what is feasible, or "afforded", at the present moment, an agent can spend more time both evaluating the utility of and acting what matters. To this end, we present Hier- archical Affordance Learning (HAL), 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 symbolic history. While these logic-based methods often require complete knowledge of the subtask hierarchy, our approach is able to utilize incomplete demonstrate that relative
and varying symbolic specifications. Furthermore, to non-affordance-avee 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- of which are hallmarks of human learning
INTRODUCTION
Reinforcement learning (RL) methods have recently achieved success in variety of historically difficult domains (Mnih al. 2015) [iilvrr et al.. 2016)] |Vinyals et al.) 2019), but they continue to struggle complex hierarchical tasks. Human-like like intelligent agents are able succeed in such tasks through an innate understanding of what their environment enables them to do. other words, they do not waste time attempting the impossible. Gibson (997) 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 RI. setting, none of these methods easily translate to environments with hierarchical tasks. In this work, introduce Hierarchical Affordance Learning (HAL), method that addresses the challenges inherent to learning affordances over high-level subtasks, enabling more efffcient learning in environments with complex subtask dependency structures.
Many real-world environments have an underlying hierarchical dependency structure (Fig. 1b), and successful completion of tasks in these environments requires understanding how complete dividual subtasks and knowing the relationships between them. Consider the task of preparing 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 obcyed. For instance, it is inadvisable chop vegetables after having mixed them with the sauce, or to boil 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 well-suited for tasks with complex high-level dependencies.
"Correspondence to r rscosta" a @uu "Code and videos of agent trajectories available http://ghhhhh.cmmmrooooccssssaa

---

Published as a conference paper at ICLR 2022
Task Hierarchy
Automata
Stochasticity
Affordances
Goal
(-1
+(2)
Start
(1
(a)
(c)
(d)
Figure 1: Many real world tasks, like making PASTA, can be conceptualized as a hierarchy (a) of subtasks, Automata-based approaches (h) map 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 to use incomplete symbolic information in the face of stochasticity by grounding context in the present state.
Existing HRL methods fall along spectrum ranging from flexible approaches that discover use- ful 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 ab- stractions 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. (p) 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 dependent merely on the completion of others.
Unfortunately, these assumptions do not hold in the real world (Fig. [p). For instance, if one com- pletes 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 in the past. The only way for automata-ba based approaches to handle this complexity is 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 reliably learn and utilize subtask dependencies. Modeling probabilistic transitions allows the sym- bolic signal be incomplete, but still requires a complete ser 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. (t), rather than solely relying on symbols.
be used to
The contributions of this paper are 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., (016) 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 model of hierarchical affordances prune impossible subtasks. Finally, we demonstrate HAL's superior performance on two complex hierarchical tasks in terms of learning speed, robustness, generalizability, and ability explore complex subtask hierarchies without extrinsic supervision, relative to baselines provided with the same information $7.))
RELATED WORK
Multi-task RL methods take advantage of shared task structure in order to generalize new tasks from the same distribution (Andreas et al.) 2017]] Shiarls et al., 2018 Devin et al. 2019 Sohn et al. 2020 Lu et al. 2021). Sohn et al. 2020) learn subtask preconditions, but symbol-basee based contexts and do not learn and use their model preconditions concurrently. Instead they assume a naive policy can sufficiently reach all subtasks. Furthermore, they assume ground-truth affordances
2

---

Published as a conference paper at ICLR 2022
provided at each step. Some works provide the agent with high-level task sketches (Andreas) let al. 2017: Shiarlis et al.) 2018) describing the order in which subtasks must be completed. While these sketches are advertised as "ungrounded" [Andrea 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., 22009) Our approach instead uses direct signal, which alone need not determine task progress, and can learn without exposure to other tasks with shared structure.
In using set of discrete symbols to indicate subtask completion, our work is similar 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 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 TI. formula to some finite state machine, which provides the agent with structure that roughly expresses subtask dependencies (Hasanbeig et al.] 2018 2020, Yuan et al., 2019). |[carte et al. (2020) bypass this formula-to-autoomate 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, well context stochasticity.
Gibson (197)) introduces a theory of affordances, defined roughly as properties of the environment which must be measured relative to the agent. Heff (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 RI., and model which low-level actions, given corre- sponding 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. (202T) 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 Markov Decision Processes (MDP) using RL. An MDP is defined by the state space S, action space A, reward function R S x A - R, and state transition distribution P: : S x A + (S)) The objective is to learn a policy, π S + ((A). which selects actions that maximize expected future returns: G(TT) E E I're a, 3t ~ Pl, where 7 is the discount factor. [Sutton et al. (1999) introduce the options framework, which flex- ibly models hierarchical abstractions with minimal modification to the RL paradigm. Each option, o = (Io: To. Bo), is defined by an initiation set, Io S S, indicating where the option can be selected, the corresponding option policy, No, and the termination condition, 8, : 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 E G. where 9 is the set of symbols relevant to the task, and [ = K. For each subtask, we introduce a separate option, Tg. 0g). and we call Tg 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 vector b' where each element by {0, }} indicates whether g E G was completed on time-step t. In our PASTA example, we might receive a milestone each time we cut vegetable, make the sauce, cook the noodles, etc. Milestones serve two main pur- poses. 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 which we learn hierarchical affordances (discussed in
Tg.
3

---

Published as a conference paper at ICLR 2022
In contrast to the standard options framework, primitive actions can only be executed as part of an option's '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 9K E 9, where 9K is the task's 's final milestone (indicating task success). When ş = {9)} ). our setting is standard, flat RI.. Each additional milestone g' added to 9 is useful an intermediate signal so long as g' corresponds to unique behavior necessary for achieving 9K-
Section 6).
Hierarchical affordances are defined over G in the following way. The vector f 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 -I Formally, fg = 1 if at time to it is possible for future 6y = without any bj 1,J * g. where ig <<< T. In PASTA, the milestone mix cooked noodles and sauce 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 Zy = {s S, f = 1]. One can think of hierarchical affordances as using milestones to impose state- state-groundee grounded subtask dependency structure on top of the options framework, which we can use to prune impossible subtasks. If G {g', 9K') J. affordance-aware agent with access 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 learte al., 2020)
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) de- fine 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 ad- dress than symbolically-define 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 cetordance-affecttn randomness that occurs either when milestones are attained (c.g. receiving varying quantity of an item), or at the beginming of the episode (i.c. starting in different contexts). Edge stochasticity is when affordances change any time within segment. We treat edge stochasticity events as infrequent exceptions to the typical subtask dependency rules. For example, after cock noodles is complete, mix cocked noodles and s sauce is af- forded, even the agent may eventually spill the noodles on the floor. By grounding these rules in the current state, an affordance-awarn 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 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 lew-level controller which executes the subpolicy relevant to that subtask. The con- troller, π: S x G - (AA), selects low-level actions, a E A, given a state, $ E S, and milestone, G G. and aims to maximize the expected milestone signal rewards, by. Q-Learning (Watkins) 1989) trains these controllers by learning an estimate of the optimal Q-function: Q;(s,,;; 0;
max, m E T/C 80 = 8, 4g = a, ag ~ T., 8t ~ P] and deriving a policy from the Q-function as such: Ty (a g) = 1(a = arg max.. Qe(s, g)). Deep Q-Learning (Mnih et al. 2015) estimates Q' using deep neural networks. This Q-function is parameterized by & == (Bosse ..., 1......, where Ohase is a set of shared base parameters and 0g is a goal-specific head. It is updated via gradient descent the following loss function, derived from the original Q-learning update:
Co. = (es. (
Gr: (Qotst, az Sr, 0) - b%g max Qc($441,44+15000 0)
(I)
a++1
where De is replay buffer that stores previously collected transitions, and 0 are the parameters of periodically updated target network. Both of these components are included to avoid the instability associated with using function approximation in Q-Learnnng
The meta-controller 11 : S + Ag) aims to execute subtasks to maximize extrinsic rewards re- ceived by the environment. Again, we estimate Q-function, this time over dilated time scale
Unlike option completion predictions (Precup al. 1998 affordances predict possihility of success.
4

---

Published as a conference paper at ICLR 2022
HAL meta-controller
HAL controller
-
achievement context
afTordance classifier
f(e)
a
Zrb
fΦ
(%(4)
(5)()
f
Qc(3,-:g,0)
Qm (s,-;)))
> [(0
meta- controller
controller
8
Qx(e)
m
g
Figure 2: Left: Architecture diagram for complete HAL method. Q-values of the meta-controoleer are masked by the output the affordance classifier. The e operator represents the standard e-greedy action selection procedure used in Q-learning, while e² 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, suboptimal policy (bottom) will benefit from mask since it can be efficiently learned and used 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): ( E E tr + max,' (SN, 80 8, 9o = 9. ag ~ Tg 8, P where N is the (variable) number of steps the option runs for. When collecting data the environment, we add transitions (st, St. >x+= It,, S14-N) to separate meta-replay buffer, Dme. used to train our meta-Q- function (parameterized by θ) with loss similar Eq. [ but without any goal-conditioning In Section 6 we describe how hierarchical affordances are integrated into this training procedure.
HIERARCHICAL AFFORDANCE LEARNING
In typical HRI methods, if the meta-controller is yet to receive extrinsic reward from the environ- ment, there will be 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 wast- ing time attempting the impossible, and reach more fruitful subtasks faster. Suppose from experi- ence, gained through random exploration, the agent achieves milestone (where achievement means by 1) very often from the initial state set I, but never j 9, despite being able to achieve j in later states. With enough experience, the agent should become confident that is not achievable without completing other milestones first, and should not bother selecting j from any 8 E I, while g, and any others that are achievable from those states, should instead be considered. If we had access to an oracle function, (s), that accurately computes hicrarchical affordances for our task, we could prune impossible subtasks by masking the otherwise uninformed policy with the affordance oracle output: p(g]s) x f * (g]s)... In the following sections, we describe a method that can learn an approximate f(s) == f (s) from experience and leverage in real-time for more effective learning.
The false negative problem Recall that f(s) outputs a vector f", where each f indicates the possibility of collecting milestone from state without requiring intermediate milestones. To train each binary classification head, (s), we must somehow generate labeled data for each milestone. Suppose option was initialized at time la and in time T milestone g received. If no others were received since the start of the option, we may assume that for any / where t, S S T, the collection of milestone g was afforded, so we can use the set of states {st,. St.t1... ST} as positive (i.e. fg (s) = 1) training examples for the affordance classifier. Even if was not the intended milestone, we can still generate positive training examples for fg this way. If option has failed to collect intended milestone
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. (s) = 0). However, this occurrence can either be indicative of the states not affording g. that the subpolicy corresponding to is sub-optimal and has failed despite g being afforded. These false negatives problem for any approach requiring function approximation via neural networks, which are generally not robust to label noise (Song et al.) 2020). is particularly troublesome in our case since the noise is greater than the true signal when the subpolicies are under-trained.
5

---

Published as a conference paper at ICLR 2022
Context learning Suppose we had access to an abstract state representation Z 2 (s), where any states 8; and 8, are mapped to the same value only when (s;) = f',)). With a representation that could cluster states in this way, could trivially determine the falsity of collected negative 8 E DDj by checking if (s) = (8y) for any 8j E DJ 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 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 | 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 and 8141 are more likely than not to satisfy (*+) = f* so long as they exist in the same segment between milestones. In this case, we can say that 8, and 81+1 share the same achievement context, x* = 2()), Let 2 (s) be an achievement context embedding represented by a differentiable function parameterized by v. We can train 2g. (s) from experience using the following contrastive loss:
S Σ, || (59) 2 (3) |kv()))) z +
where each of is a randomly chosen anchor, each sy is a positive example chosen within the segment according (truncated) normal distribution, (0, (0, centered around (and excluding) sy. sy is chosen randomly among other segments and is treated as a negative example, and a 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 wide range of a produce useful representations. For our edge stochasticity experiments (Figure 5) we use a low o 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-labell
state sg for classifier head fg. we compute the mean distance from (*g) to the representations of the k closest positive points in a population uniformly sampled" from Di-- denoted d' We expect de to be large for true negatives and small for false ones, and we can determine effective separating margin in the following way. First we compute distance scores for a random sample of positive points, denoted ] to as reference. We ensure these points come from segments that disjoint from the population points' segments to avoid trivially low scores that might skew the distribution. We then fit Gaussian distribution to [d+} and compute an upper confidence bound p for given percentile value and confidence level. Any db < p very similar to positive points in the representation space, so we count 8, 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 em- bedding network, and an affordance classifier (see Figure D 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 y at the beginning of the episode, and selects new subtask g' after collecting any milestone or whenever an option times out after a predefined number of steps (our 8g). At each step, the current state is fed to the controller, which outputs an action con- ditioned on the most recently selected subtask. After discretizing the classifier's s output to a binary mask, we perform an affordance aware version of e-greedy follows. Given parameters ear and 'nc, we select a random subtask within the mask with probability car, 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 stochastic- ity? (3) Can HAL more effectively learn a diverse set of skills when trained aas-stgnosi
'Here, the usage of "positive" and "negative" refers to whether points share the same achievement context.
"This procedure is akin to the particle entropy approach used in (Liu & Abheel 2021). 5 For efficiency, we sample just enough points so that we are likely to cover all encountered contexts.

---

Published as a conference paper at ICLR 2022
3
0
0
1
4
11
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 Fig- ure 3) are extensions of the minigrid framework (Chevalier- Boisvert et al., 2018). Agents receive egocentric image of the environment, well as 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, ronment specific actions detailed below. Task hierarchies, walk-throughs of successful trajectories, and additional information about both environments are included in Appendix [A]
well envi-
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 immensely complex and presents a signifi- cant challenge for AI agents to reach subtasks deeper in the hierarchy. We develop environment that replicates this hierarchical complexity without the commensurate visuomotor complexity which 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 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 sequence of collecting several keys, as well as placing an object open the requisite doors. Agents can only carry one object at time, 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 single "interaction" action that is used to pick up keys, open doors, etc. While CRAFTING has 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).
weight- bashd sensor, in order to
7.2 BASELINES
Table I: Summary of baselines.
Our set of basclines is summarized in Table D 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 sig- nals, non non-hierarchical methods use a dense reward function that incorporates milestone signals for the first time each milestone obtained in the episode. To evaluate the efficacy of our affordance classifier
lierr.
Afford ance Mask
Hind- sight Replay
False
archical
Negarive Filtering
Agent
Oracle
Truth
NIA
HAL (ours)
Learned
HAL(-ENE)
Learndd
x
Rainbow
N/A
H. Rainboww
(+HER)
N/A
Rainbow
x
N/A
N/A
N/A

---

Published as a conference paper at ICLR 2022
1.0
0.6
HAL (ours)
0.8
HAL[-FNF)
Succoss Rate
H-Rainhaw
2.6
Rainbowk +HER)
0.6
Rainbow
Sub-Policy
0.4
0.2
0.0
0.0
0.00
0.22
0.50
0.73
1.00
1,20
Step x10F 0.0
0.2
0.4
0.6
08
Step
Step
XIP
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 timing out or collecting incorrect milestones.
online learning procedure, we compare method to "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-basel approaches). We also incorporate a version of Hindsight Experience Replay (HER) (Andrychowicz al. 2017) adapted for the discrete milestone setting, which involves re- re-using "failed" trajectories that result in the collection of an un- intended 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 poli- cies 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 outper- forms the strongest baseline, H- R-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 significant improvement. False negative filtering (and all other HAL components; see Appendix B) appears crucial for learning in the TREASURE envi- ronment, but not as much for CRAFTING, though in both cases filtering improves mask accuracy. Removing false negative filtering causes HAL(-FNF) be pessimistic (i.e. over- wver-pruning subtasks, see Figure 13 in Appendix D ultimately leading to its unstable learning. Since masking impossible optimal meta-controller, HAL'S success must stem from its
subpolicies would have no impact ability to learn useful mask before TD errors are able to propagate through the meta-controller's Q function. HAL utilizes more easily learnable function (affordance classifier) 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 an appropriate con- text, we see they achieve a significantly higher average subpolicy success rate (Figure right).
Robustness to milestone selection In this section we evaluate HAL'S robustness to the selection of milestones. Affordances change when 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 the same across all sets. Figure 5 shows HAL'S success on the CRAFTING environment's ron task when using "incomplete" milestone sets, relative to the full human-designed set. We see that randomly removing milestone makes no significant difference for HAL, and even after removing 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 able to converge to a 97% success rate on at least one set, while HR+H fails converge any set and ends with maximum success rate of around 70%.
8

---

Published as a conference paper at ICLR 2022
1.0
1.0
None
kone
3/200
0.8
1/50
1,50
Sucoes Bate
1/30
1,30
11.6
Success
0.4
HAL [nurs]
02
R-Rinboow ++ER))
0.0
0:25
0.50
0.25
1.00
1.25
0.25
0.90
0.75
1.00
1.25
of Milestones
Step
X10
Step
X10
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 stochasticity We modify CRAFTING so that at each environment step, there is 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 disappearance frequency of 1 1/100 that cuts HR+H's success rate in half, HAL is still able to reach its non-stochastic success rate. With 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 removed from the agent's inventory over the course of episode. By learning 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 meta-controller in the absence of re- wards, instead randomly select subtasks with some probability Eme, 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 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 marginally outperform HAL tasks shallower in the hierarchy (e.g. wood pickaxe, stone, fur- nace), potentially as result of failing reach deeper tasks and getting more practice on shallower ones. This result an indication of the general utility of HAL in en- vironments with complex task hierarchies.
1.0
0.8
Heerorcy Depth
Success Hate
0.6
0.4
HAL (ours)
Rainboor/++HEr
0.2
10
Log
Wood
Cratting Booth
Steck
Wind Pockats
State
Fimanca
Stome Pelkoer
Coal
Ore
toa Podast Dimmndd
Iron
Subtask
Figure 6: Percentage episodes where each milestone is achieved in CRAFT- ING environment task-agnostic setting.
CONCLUSION AND FUTURE WORK The present work can be viewed as a first step towards bridging the substantial gap between flexible hierarchical approaches that 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 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 un- able to. We demonstrate that HAL learns more effectively than baselines provided with the same information, more robust to milestone selection and affordance stochasticity, and can more thor- oughly explore the environment's 's subtask hierarchy. Given HAL's flexible formulation and success in the face incomplete and stochastic symbolic information, we foresee future work integrating HAL with option (or subgoal) discovery methods (e.g. [acoo et al. 2017 Machado et al. 2017 Bagaria & Konidaris 2019) to obtain performance gains in complex tasks without requiring pre- specified milestones. Additionally. future work might be able to extend HAL continuous goal- spaces, but this would require revising the definition of hierarchical affordances provided here, as currently requires notion of intermediate subgoal completion.

---

Published as a conference paper at ICLR 2022
9 ACKNOWLEDGEMENTS
We thank Natasha Jaques, Sébastien Arool,, and the anonymous reviewers for their feedback mature drafts of this manuscript. This work is partially supported by NSF Awards IIS- 1513966/ 1632803/1833133 0504, DARPAD3M Award UCB-00009528, Google Research Awards, gifts from Facebook and Netflix, and ARO# W911NF-122 1-0241 and W911NF-15-1-0484
CCF-1139148, DARPA Award#: FA8750-18-2-0111 FA8750-19-1-
10 REPRODUCIBILITY STATEMENT
All code for environments, HAL, and other relevant baseline algorithms is provided at the following link: httpgghhww..oo/oooooosttteeeeeee
We provide instructions for installing the necessary de- 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, Mareus 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. 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 Learning Representations, 2019.
Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston. Curriculum learning. In Proceedings of the 26th Annual International Conference on Machine Learning, ICMI. '09, pp- 41 41-48, New York, NY, USA, June 2009. Association for Computing Machinery.
Anthony Chemero. An outline of theory of affordances. Ecol. Psychol., 15(2)1881-195, April 2003.
Maxime Chevalier-Boisvert Lucas Willems, and Suman Pal. Minimalistic gridworld environment for openai gym. battp:://qttuut com/ http://wwmmmmammmmmmmiiiiaiaa/aa
2018.
Devin, D Geng, Abbeel, T Darrell, and 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 reward function. 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: large-scale dataset of minecraft demonstrations. In IJCAI, 2019.
Danijar Hafner. Benchmarking the spectrum of agent capabilities. arXiv preprint arXiv:2109.06788 2021.
Mohammadhosein Hasanbeig. Alessandro Abate, and Daniel Kroening. Logically-constriinee re- inforcement learning. arXiv preprint arXiv: arXiv:1801.00 18011180999 2018.
10

---

Published as a conference paper at ICLR 2022
Mohammadhosein Hasanbeig, Daniel Kroening, and Alessandro Abate. Deep reinforcement learn- ing with temporal logics. In Formal Modeling and Analysis of Timed Systems, pp. 1 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 neural network. arXiv preprint AXXi:2202.112627, 2021.
Rodrigo Toro Icarte, Toryn Q Klassen, Richard Valenzano, and Sheila Mcllraith. 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 do here? Learning new skills by imagining visual affordances. arXiv preprini arXiv:2106.00671, 2021.
Khimya Khetarpal, Zafarali Ahmed, Gheorghe Comanici, David Abel, and Doina Precup. What can do here? A theory of affordances in reinforcement learning. In International Conference on PMLR, 2020.
Machine Learning, pp.
Tejas D Kulkamni, 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 Belta. Reinforcement learning with temporal logic rewards. In 2017 JEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 3834-3839, September 2017.
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.000 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 Bellemare, and Michael Bowling. A laplacian framework for op- tion discovery in reinforcement learning. In International Conference Machine Learning, pp- 2295-2304 PMLR, 2017.
Alexandre Manoury, Sao Mai Nguyen, and Cédric Buche. Hierarchical affordance discovery us- ing intrinsic motivation. In Proceedings of the 7th International Conference on Human-Agent Interaction, 186-193, 2019.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver. Andrei A Rusu, Joel Veness, Mare G Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Joannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wier- stra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. February 2015.
Nature, 518(7500))7559995555555
Doina Precup, Richard S Sutton, and Satinder Singh. Theoretical results reinforcement learning with temporally abstract options. 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.

---

Published as a conference paper at ICLR 2022
David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre. George den Driessche, Julian Schrittwieser, loannis Antonoglou, Veda Panneershelvam, Mare 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 arXtv:2007.08119, 2020.
Richard S Sutton, Doina Precup, and Satinder Singh. Between MDPs and semi-MDPs: a framework for temporal abstraction in reinforcement learning. Artif. Intell., 12(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.
PMLR, 2017.
Oriol Vinyals, Igor Babuschkin, Wojeiech M Czamecki,, Michaël Mathieu, Andrew Dudzik. Juny- oung 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émi 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ünsch, Katrina McKinney, Oliver Smith, Tom Schaul, Timothy Lillicrap, Koray Kavukeuoglu, 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 1909: 2019.
Shangtong Zhang. Modularized implementation of deep algorithms in pytorch. https:/
g t hub. cow./SShanggggoggggggg//eeeg 2018.
12

---

Published as a conference paper at ICLR 2022
Appendix
Table of Contents
Additional Environment Details
13
A. CRAFTING
13
A.2 TREASURE
14
A.3 Walk- talk-throughs
14
B Ablation and Robustness Results
16
B.1
Component Ablations
16
B.2 Hyperparameter Robustness
16
B.3 Varying a under Stochasticity
17
C Episode Length Plots
17
D Affordance Plots
18
Algorithm
19
Implementation Details
20
A ADDITIONAL ENVIRONMENT DETAILS
In both environments, extrinsic rewards are a sparse binary signal provided upon the completion of final goal. Milestone signals are similarly formulated for each of the possible subtasks. For both types of rewards (extrinsic and milestone) we introduce 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 al. 2018).
A.1 CRAFTING
As discussed in Section 7.3 our CRAFTING environment is designed to maximize hierarchical com- plexity while minimizing Visuomotor complexity, which we do not aim to address with our method. Similar Minecraft-baset 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 addition to understanding the hierarchical relationships between subtasks. In order evaluate our method effectively, we only aim test the latter. Other work has used Minecraft-inspired environments (Andreas et al. [0166] (Shhn 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 con- tains similar hierarchical complexity while minimizing perceptual complexity (Hafner 2021).
Figure Z 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 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 crafting bench. Other items require specific pickaxes to be mined, and yet others must be smelted in 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 environment stone pickaxe requires three stone and two sticks. Each stone must mined individually, resulting in three separate milestones, while just wood required craft four sticks. Lastly, there
13

---

Published as a conference paper at ICLR 2022
1
2
10
Jrun pickaze
stone
coal
Iron
log
wood
pickaze
wood
pickase
iron
diamond
crafting bench
furnace
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 Figure Numerical preconditions for crafting recipes are not shown, well other possible implicit environmental dependencies (e.g. mining x reach y).
2
5
red door
green weight
yellow door
8
i purple key
key
yellow key
key
blue door
green door
treasure
9
Figure 8: Abstract representation of one possible TREASURE subtask hierarchy, where milestones 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 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 randomly assigned stone, coal, iron, or dirt each cell with varying probabilities. Diamond is randomly assigned to 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 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 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 B). While the environment dynamics remain the same across episodes, the agent must infer which hierarchy is appropriate based the initial configuration of the environment. TREASURE 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- SELK-THHOUGHS
Successful human walk-throughs for both TREASURE and CRAFTING environments described in Figures and I0 respectieely.
14

---

Published as a conference paper at ICLR 2022
(a) Agent is initializedd the central room, with only the red key afforded.
(b) Agent picks up the the red key and moves toward the red door. Note that the red door milestone is now afforded.
(c) Agent opens the red door and must choose hetween 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.
(d) Agent opens the door to the room with the scale by first proceeding into the left-side room picking up the blue key.
(c) Agent picks the ball and drops the scale, opening up the room containing the final key.
(f) Agent picks the purple key, and the final desired milestone (treasure) afforded.
Figure 9: Walk-through of 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.
7
7
(a) Agent is initialized in "woods" surrounded by trees, with converts them into wood and sticks. only logs afforded.
(b) Agent collects logs, and
(c) Agent uses sticks wood create a crafting bench and wood pickaxe.
680
(d) Agent collects stone that uses to create furnace and stone pickaxe.
(c) Agent uses the stone pickaxe to (f) With the iron pickaxe, the agent collect iron and coal which it turns into iron ingots, which turn are crafted into an iron pickaxe.
finally reach and mine diamond, the final goal.
Figure 10: talk-through of successful CRAFTING environment d diamond task episode.
15

---

Published as a conference paper at ICLR 2022
B ABLATION AND ROBUSTNESS RESULTS
B.1 COMPONENT ABLATIONS
In Figure II plot success 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 this task. The only variation that also reliably converges 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
4000
HAL (ouns)
-RAI
3000
-RT
Success Rate
Episodo Length
0.6
ENF
-FN,
0.2
2
0
4
Step
Step
x10
Figure 11: Training curves for component-wiss ablations of HAL TREASURE task. HAL refers to the full method, while the rest of the items displayed in the legend indicate which components removed. -RAI longer uses the context representation (the classifier is trained directly over the state). -TT no longer uses affordance classifier loss to additionally 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.
input to the affordance classifier
B.2 HYPERPARAMETER ROBUSTNESS
In Figure 12 we demonstrate HAL's robustness to modifications of the most significant newly intro- duced 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 aggressive settings for both of these hyperparameters are reliable. We find that the standard devia- tion hyperparameter is sensitive across the values test the non-edge-stochaste 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 actuality still effective.
low, which results in less pruning. We that wide range of more
0.8
0.6
(sun)
IR meon
0.0
0.53
0.87
01:00
0.50
0.7
12
0.3
0,6 Affordance Classifoe Thosheld
0.4
0.5
Upper Conlidanc Bound Percentile
Sampling Divinbuiion Standand Devistion
Figure 12: Plots comparing HAL's final success rate with that of HR+H's on TREASURF task with alternative hyperparameter settings. Left: percentile values used for defining the upper confidence bound p for false negative filtering. Center: standard deviation values, a, used for sampling positive points from the (truncated) normal distribution in the contrastive loss. Right: threshold value over which the affordance classifier output discretized.
16

---

Published as a conference paper at ICLR 2022
B.3 VARYING UNDER STOCHASTICITY
In Appendix B.2 we demonstrated that in TREASURE, various values of a centered around the value used in that setting (o 7.0) all conducive to good performance that task. In Figure [3 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 (a = 2.0) appears to strike the best balance. Very low values (e.g. 0 1.0) likely do not learn as general a context representation, while higher values (e.g. = 8.0, 16.0) are more likely sample positive points across occurrences of edge stochasticity. It intriguing that the final loss for = 2.0 is lower than for a 1.0. We speculate that the context learned by sampling points too close to the anchor could be less natural representation to learn than more general one, which considers further points.
HAL (ours)
0.0090
0.8
HR+ mean
Contrcsive Loss
0,0025
0.6
0,00220
0.4
0.0015
16
Sampling Distribution Standard Deviation
Sampling Distribution
Figure 13: Plots evaluating the efficacy of various values used for the contrastive loss in stochas- tic CRAFTING environment on the ron 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 we display the episode length plots corresponding to the success rate results shown in Figures
Cracle
1000
HAL (ours)
HAL(-FNF)
Gpiadd Lengtt
H Rainbow
2000
Fainbook HER)
2000
Rainbow
1000
0.00
0.25
0.50
0.75
1.00
1.25
Stop
K30
Step
XII
None
None
1/100
1/100
1/50
1/50
Epieode Longth
3000
1/30
2000
0.50 0.75
1.25
0.75
1.00
Step
Step
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
17

---

Published as a conference paper at ICLR 2022
D AFFORDANCE PLOTS
We provide metrics tracked over the course of training for affordance masking as well as false negative filtering in Figure [5] The mask metries (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 subtasks that are afforded but are pruned.
Underpruning Percentage: Percentage of subtasks that are afforded but are not pruned.
The false negative filtering metrics (Figure 15b for CRAFTING iron and Figure 15d for TREASURE)
consist of:
Filtering Margin: L.2 distance at which we consider negatives to 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.
Sae
300
2
65
Oep
Mask metrics for CRAFTING environment iron task.
Medes
(b) KNN filtering metrics for CRAFTING environment iron task.
Oode
H511 Iul
(c) Mask metrics for TREASURE environment.
(d) KNN filtering metrics for TREASURE environment.
Figure 15
18

---

Published as a conference paper at ICLR 2022
E ALGORITHM
Algorithm Learning procedure for HAL
Initialize replay buffer for meta-controller (Dme). controllers (Da), positive affordance examples
(DT), ). potential negative examples (D2) for each goal g E 9, and parameters for meta-controller
(0), controllers (0), achievement context function (19), and affordance classifier (o)
2: steps <- 0
3: while steps < max_steps do
4: env_steps, opt cettionnstepp +
5: Receive initial state, 8, from the environment
6: while is not terminal or env steps max env steps do if env steps = 0 or opt on steps > max option steps or Σ, by > 0 then option_steps if d'env-steps > then
7:
8:
9:
Store transition (sinicig, by. .) in Dm
Store examples s, s [init, env_steps] in positive buffers D
12:
where bj = and negative buffers Dj where by = 0
end if
14:
init + env_steps
fa (s)
Get predicted affordances Compute Q-values for all goals
16:
t (s.
q x PAAA. =0
Mask non-afforded goals
18:
Jamx + arg max
> Get best afforded goal
19:
Jatt + Rand(j f3 = 1)
Get random afforded goal
20:
Gand Rg)d(g)
> Get random goal
21:
end g 9aX w.p Calts Irand w.p Eme, else Jmax
2 --greddy goal selection
22:
23:
Omax arg max (s ()
Get best action
conditioned goal
24:
Grand <- Rand(A)
> Get random action
25:
Grand w.p Ezz else Omax
é-greedy action selection
26:
steps +, opt otttoiootttepp + +, env_steps +
Send action the environment and receive next state s', rewards r, and milestones
28:
Store transition (s, s' g) in D.
30:
if steps % update... freq 0 then Sample batch of transitions from De and use update via Q-learning loss end if
31:
32:
33:
steps % aemea.update aueettuuuateeeeeee = 0 then
34:
Sample batch of transitions from Dm and use it to update θ via Q-learning loss end
35:
36:
if steps % mmargin_update. freq then
37:
Sample disjoint sets of positive examples from Dj and update negative filtering margin
38:
39:
end if
if steps % aff.update.freg
then
41:
Sample positive and negative examples from D and D respectively to update é with binary cross entropy loss (ignoring any negatives with computed distance scores less than false negative filtering margin)
43:
44:
end
45:
if steps % rep.update_fress 0 then
46:
Sample anchor, positive, and negative states from D. to update i via contrastive loss end if
47:
48:
end while
49:
end while
50:
19

---

Published as a conference paper at ICLR 2022
F IMPLEMENTATION DETAILS
All experiments are run with 5 random seeds each. We use 4 parallel environments for data col- lection with all methods. We do not include Noisy Nets 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 Table 2 All update frequency parameters are computed with respect to total environment steps (across parallel environments). Relative to the controller's Q-learning up- dates, all other algorithmic mechanisms are updated less frequently for the sake efficiency, rates which do not appear to affect the performance of our method. The meta-controller, affordance clas- sifier, and the context representation are all trained every controller updates. Since the optimal separation margin between false negatives and true negatives changes slowly over time, and each computation expensive, each classifier head's s margin updated every 150 controller updates.
Table 2: Hyperparameters used in HAL and baselines
Name
Description
Value
adam_Ir adam_eps
Adam learning rate (across all networks)
0.000625
Adam epsilon
0.00015
batch-size
Training batch size
32
Discount factor
0.99
targ.update exp-steps 6 6me car n steps option on steps
Target network update frequency
103
Exploration steps before updates
400
Epsilon used in controller's e-greedy procedure
0.5 0.05
Epsilon used in meta- meta-controller's c-greedy procedure
0.2 + 0.05
Affordance eps. used to randomly select within mask
0.8 0.00
of steps used for n-step returns
10
Maximum option steps before timeout
50
update
Freq. of controller weight updates
4
meea..udate.
Freq. of meta-controller weight updates
40
margin.updatte_freg
Freq. that false negative filtering margins are updated
600
aff.update_fres
Freq. of affordance classifier weight updates Freq. of context representation weight updates
40
rep.update.freq
40
Standard deviation used for inter-context sampling
7.0
aucch
used for edge stochasticity runs of points used for sampling for KNN procedure of nearest neighbors used for KNN procedure
2.0
knn
1000
knn_k
1
fnf.conf
Confidence value used for upper confidence bound
0.95
fnf-perc
Percentile value used for upper confidence bound
0.9
20


Reviews:
[{"review_id": "nCtlLV2KYXv", "reviewer": "Reviewer_LfMQ", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength: \n1. I like the idea of learning affordance and using them to prune impossible subtasks during exploration.\n2. Grounding on the current state, the affordance prediction can get rid of the history of subtask completion and handle stochasticity.\n3. The paper proposes an \"achievement context\" trick that is used to filter out false-negative samples during affordance classification.\n4. The paper presents experiments that demonstrate the effectiveness of the proposed method and provides extensive ablation studies.\n5. The overall writing is easy to follow.\n\nWeakness and comments:\n1. Why affordance classifier is learning faster than the meta-controller? Do we need to collect tons of samples to train an affordance classifier? When coming to a novel state, why is the classifier able to make a correct affordance prediction? Could you provide more intuition or motivation behind the affordance classifier?\n2. For methods using \"atomic propositions\", it seems that they can also handle the stochasticities if they model probabilistic transitions instead of deterministic transitions.\n3. \"each additional milestone must correspond to a behavior that is necessary for achieving the final milestone\" confuses me. Why is this true? Can we have redundant milestones?\n4. For CRAFTING, \"The full set of milestones contains items that are either craftable or collectable.\" Do the milestones include the number of items? What if we need multiple blocks of wood to make a pickaxe?\n5. Currently, the milestones are manually defined, which involves human prior. Do you have any idea how to select milestones automatically? This may be important for the proposed method to be generalized to various tasks.\n\n6. page 3: $\\mathcal{G}$ appears but is not explained. (explained on page 4).\n7. page 3: Could you use another symbol to replace $b_g$, since there is another $b_g$ on page 4.\n8. page 4: $\\mathbb{E}\\left[\\sum_{t=0}^{N} r_{t}+\\max _{g^{\\prime}} Q_{m}^{*}\\left(s_{N}, g^{\\prime}\\right) \\mid s_{0}=s, g_{0}=g, a_{t} \\sim \\pi_{g}, s_{t} \\sim P\\right]$. what is $g_0$ here? Is $N$ fixed and why is it so?\n9. page 4: what is $T$ in $t_{0}<t<T$?\n10. page 4: Does $b_{g}^{t}$ indicate the completion of subtask at time t only, or also include the completion before t.\n11. \"Crucially, unlike atomic propositions, the history of milestones alone need not define which subtasks are currently possible.\" confuses me.\n12. \"we have achieved something notable without having to assign it utility.\" confuses me.", "summary_of_the_paper": "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.\n\nThe paper proposes a trick called \"predicting achievement context, \" which filters out false-negative samples during affordance classification.\n\nThe paper presents experiments on CRAFTING and TREASURE that demonstrate the proposed method's effectiveness and provides extensive ablation studies.", "summary_of_the_review": "I like the idea of this paper, and the experiments also convinced me.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "VWafNbKIKEc", "reviewer": "Reviewer_3eiv", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "# Strengths\n- The central idea of the paper is very good.\n- The paper is well written and structured.\n- The motivation is clearly explained and I liked the running example with the pasta making to explain some of the concepts. As I was reading it, I was hoping to find an experiment with an agent using the approach to learn to make pasta. That would have been a nice example.\n- I like Figure 1 that explains the different approaches to the problem.\n\n# Weaknesses\n- One of the advantages of the approach proposed is that you could potentially tackle problems with more complex action spaces. I'm not 100% convinced that the two example domains (Crafter and Treasure) are necessarily the best domains to show what the approach can do. \n- In the introduction (page 2, 2nd paragraph) you discuss the completion of tasks. You mention that if a task is not completed some approaches need to introduce a symbol that indicates that tasks are undone. However, there are existing approaches (especially in the planning and agent communities) which can specifically deal with goals not being achieved. In fact in the BDI (beliefs, desires, intentions) agent literature there are agent programming languages that can specifically handle plan failure.\n- Something that was just briefly touched on in the paper was the relationship between an affordance and an agent's intent. If we look Gibson's, Chemero's and the work of Norman in affordance theory from the cognitive sciences literature we see that the relationship between an agent's goals, their intentions and the affordances available to an agent; these are deeply linked. It would have been good to explore this a bit more especially since this a link to HRL where goals and sub-goals play a much more prominent role compared to regular RL. Perhaps something to look at for future work.\n- This is just a minor point, but it is perhaps more accurate to say that your model was inspired by theory of affordances (or perhaps a model of affordances) rather than saying you have incorporated affordances into your approach. \n- One of the arguments for introducing affordances into these type of algorithms (and you have made a similar argument in this paper) is that it has the potential to reduce the action space the agent needs to explore. This would imply that by incorporating affordances in a HRL model that my learning times for a particular task/game could be reduced. Comparing the learning times for the same task using the same RL algorithm (with and without affordances) would have been nice to see. This would have been a nice complement to Figure 4.\n- Evaluation needs some additional work. A discussion of limitations and future directions is needed. \n\n# Questions / Issues\n- Many references are missing publication details. For example (Kulkarni 2016), the conference where this paper was published is not shown. This is the case for many of the references and should be fixed before the paper can be accepted. \n- Question about the terminology \"milestone\". Is this basically goal or sub-goal achievement?\n- First sentence in Section 5. Reads a bit off. I think you might have missed a word in this sentence. \"...for selecting any subtasks the others.\"\n- It wasn't 100% clear to me what you meant by the oracle function. I noticed this also in the results when you are plotting the Oracle against other RL algorithms. How is the oracle computing which action to take?", "summary_of_the_paper": "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.\n\nThe 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.", "summary_of_the_review": "- I think this is a good paper. There are some issues that need to be addressed but not enough to not recommend it for acceptance.\n- The central idea is a good one. I would say this is an incremental improvement to existing work, but has the potential to reduce the action space that agents have to explore and potentially reduce learning times. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "QzuZhmCczcF", "reviewer": "Reviewer_m66y", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall an interesting paper with a simple idea, yet a fairly complicated algorithm to achieve the envisioned gains. The paper is well written and polished (although I have spotted several grammatical errors here and there) and the experimental evaluation is nice and fairly extensive and includes proper baselines. Related work is done fairly well too, and up-to-date. The conceptual steps (state abstraction which is induced from data, milestones and the f-function, their interdependence, and the mix with HRL) are clear although quite some practical choices are made and it is hard to see how robust these choices are (e.g. can the method diverge with a poor choice for some of the elements/hyperparameters?). Overall, I see several reasons for accept, but I also have a couple of things that are not yet entirely clear to me:\n1) The option framework is chosen early, but after that the formalization is not appealing to the simple option formalism at all. I think it would be more clear to define the milestones etc in an option framework first, and only then go to the deep approximations. Now things are mixed, and not clear enough. A more thorough definition of the approach and the underlying (semi)MDP first would be preferred.\n2) Related to the options, the affordances --as modeled here-- are actually some indication of a mix of option completion prediction and estimating the applicability of subpolicies, but not entirely clear enough (also not in the context of related work). Work like Ketharpal et al uses affordances purely for limiting action selection (ie. what is used here too) but based on \" intended effects\", whereas here it is about \"possibility to obtain the milestone/effect\" but it is also about \"completion\" of subpolicies and this is less clearly defined. Even more; the paper is unclear about the relation between subgoal policies and the vector induced by the f-function. The last sentence of section 6.1. says that for this domain \"the set of milestones contains each object the agent can successfully interact with\" whereas in the caption of Fig 4 it is said that \"sub-policies, on average, receive the correct milestone when called\", and earlier in the paper I wrote in the margin something like \"f(.) =?= #options???\" meaning that in the right part of Fig 2 f() is used as a mask over Q-values (of subpolicies) but does this mean there is a milestone for each subpolicy? This triggers the question again about \"option completion prediction\" (and related work) but at least it signifies that there is something unclear about the definition of f and what the milestones are in relation to the subpolicies.\n3) The experiments are nice, and informative. Yet, if affordances are modeled as they are here, as ways to mask out particular \"probably unsuccessful options\", they seem to mainly improve sample complexity, with as cost the increased computational complexity. That is, the 4 parallel learning tasks are more complex than a standard HRL method (like H-Rainbow here). I wish more would be said about this tradeoff. In addition, I think that some kind of ablation study on the four learning tasks would be useful: they do influence each other very much, hence if one or more would be absent (or stable by using an oracle) it would be easier to see how they help and interrelate. Also, because many practical choices have been made (and thresholds, and hyperparameters been chosen) I would like to see how robust the method is over these choices (but the general case for this is maybe out of scope for this paper).\n4) Based on some of the unclarity in 1-3, the comparison to related work is also not entirely clear. The comparison against recent LTL-style representations in RL is no strong anyway, since these are very different settings (with very different aims and goals). I do see that the authors try to make the case that they do not need complex symbolic structures, and there is some overlap with the specifications of (hierarchical) tasks, but the work in this paper is much more practical on a deep HRL method with an extra signal (milestones) and I do not see a deep connection. Also: the supply of the milestones can also be quite a bias and something one has to deliver as input (although, indeed, HAL can also work if this specification is incomplete). One aspect that could be made more explicit is the link between \"milestones\" in this paper, and \"task monitors\" as used by LTL-style work, in which several papers feed these into a deep RL system to enrich the state with \"information about progress on a task\" (which is, to me, very related). I would expect also more connection to HRL and the discovery of options and subgoals maybe.\n\nIn addition, some other issues are raised throughout the paper:\n- Caption Fig 1 grammar error (\"defines\").\n- There is no real definition of \"affordance\" in this paper. It is only implied, even though there are many definitions in the literature.\n- Section 5, 2nd sentence is key: \"restriction of subtask selection\". It would be good to introduce this more strongly earlier in the paper, since many other affordance models (e.g. in robotics) are about probabilistic models (between actions, objects and effects).\n- Page 5: line end-3: \"to collected\" (grammar)\n- The part about context learning is ok (page 6) but if there is space, it could be expanded to say more about the rationale and the underlying technical components to make this work. \n- Page 6: explain \"KNN\" and connect it to the method.\n- The experiments are well done, and \"learning efficacy\", \"robustness\" (twice) are clear, but the task-agnostic setting is not at all.\n- Fig 5 shows how relative the performance is/can be (see also my remarks above about the experiments). With half of the milestones, H-Rainbow+HER is as good as HAL. Turning it around: HAL needs at least half of the milestones to be better. Not much is said in the paper about this.\n- Fig 5 also shows the stochasticity results, but I prefer a more thorough explanation in terms of how the algorithms work.", "summary_of_the_paper": "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.", "summary_of_the_review": "Overall, the approach is interesting, and valid, and significant. There are some unclarities about particular aspects (see review), and I think that the positioning can be done better, but my feeling is that they do not hinder acceptance too much.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "DnCZYBMhrXc", "reviewer": "Reviewer_QUoN", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n- The paper addresses an important problem and contributes real progress.\n- The paper is mostly really well written, using clear wording and notation.\n- The results, though limited in quantity, are indicative and make a solid case for the method.\n\nWeaknesses:\n\nNot many, none serious.\n\nI'm not sure I fully understand the contrastive loss function; its description is definitely too terse.  Unlike earlier, $N$ does not appear to be the segment length but some constant.  The anchor is apparently chosen from the current segment, but this is not stated.  What does it mean for $s_j^p$ to be chosen \"according to a segment-truncated normal distribution\"? I guess it is its rank within the segment that is chosen from a normal distribution centered at the rank of the anchor point.  This should also be reflected in the mean of the normal distribution; $a$ does not make sense.  And shouldn't $s_j^a$ be excluded from this choice?\n\n\"We show in Figure 5 that this parameter is relatively easy to set\": If all runs shown used the same parameter value then the results are suggestively reassuring, but they do not show how performance would differ if (say) specially-tuned values had been used.\n\nSome Details:\n\n- The fact that the milestone dependency structure must be pre-specified becomes clear pretty late into the paper.  This should be noted in the introduction, if not in the abstract.\n- The elements $b_g^t$ (4th row of Sec. 4) are the same as the elements $b_{g,t}$ near the bottom of p. 3 but the latter uses a lower instead of an upper index.  Reading the paper, it is quite obvious that this is in fact the same $b$, but it would be nice to make this connection explicit since it is key to understanding the method.\n- Two crippled sentences on p. 5:\n  - \"subtask the others\"\n  - \"failed to collected\"\n- p. 6, \"Context learning\": $f^*(s_i) = f^*(s_j)$ should read $f^*(s_t) = f^*(s_{t+1})$\n- p. 6, \"set used in the KNN procedure\": I found this wording misleading and suggest its replacement by \"$k$ closest positive points in $D_g^+$\", or perhaps simply \"$d_q^k$\".\n- Fig. 5 left: It would be interesting to know why the HAL curve drops sharply upon removal of the 5th milestone.\n- Fig. 5 center and right: it would be interesting to know how policies trained without edge stochasticity would perform in environments with various levels of edge stochasticity.\n- Fig. 6: Quantify the depth of each milestone within the task hierarchy.", "summary_of_the_paper": "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.", "summary_of_the_review": "The paper addresses an important problem and proposes a novel and effective solution that is likely to be used and built upon.  \"Do not exist in prior works\" is a strong statement; there is certainly work this paper builds upon, but, if one draws the line around the \"contributions\" tightly enough, I cannot point to specific prior work in which \"aspects of the contributions exist\".", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a hierarchical reinforcement learning approach that exploits affordances to better explore/prune the subtasks, and thus making the overall learning more efficient. 

The idea of the paper is novel and interesting. 

After the rebuttal, all the reviewers agree that the paper is a solid contribution.
Therefore, I recommend acceptance of this paper.
Decision: Accept (Spotlight)