HALMA: Humanlike Abstraction Learning Meets Affordance in Rapid Problem Solving
Authors: Sirui Xie
Xiaojian Ma
Peiyu Yu
Yixin Zhu
Ying Nian Wu
Song-Chun Zhu
Venue:  (2021)
Keywords: Visual Concept Development
Rapid Problem Solving
Abstract Reasoning

Abstract: Humans learn compositional and causal abstraction, \ie, knowledge, in response to the structure of naturalistic tasks. When presented with a problem-solving task involving some objects, toddlers would first interact with these objects to reckon what they are and what can be done with them. Leveraging these concepts, they could understand the internal structure of this task, without seeing all of the problem instances. Remarkably, they further build cognitively executable strategies to \emph{rapidly} solve novel problems. To empower a learning agent with similar capability, we argue there shall be three levels of generalization in how an agent represents its knowledge: perceptual, conceptual, and algorithmic. In this paper, we devise the very first systematic benchmark that offers joint evaluation covering all three levels. This benchmark is centered around a novel task domain, HALMA, for visual concept development and rapid problem solving. Uniquely, HALMA has a minimum yet complete concept space, upon which we introduce a novel paradigm to rigorously diagnose and dissect learning agents' capability in understanding and generalizing complex and structural concepts. We conduct extensive experiments on reinforcement learning agents with various inductive biases and carefully report their proficiency and weakness.

Under review as a conference paper at ICLR 2021
HALMA: HUMANLIKE ABSTRACTION LEARNING MEETS AFFORDANCE IN RAPID PROBLEM SOLVING
Anonymous authors Paper under double-blind review
ABSTRACT
Humans learn compositional and causal abstraction, iee. knowledge, in response to the structure of naturalistic tasks. When presented with a problem-solving task involving some objects, toddlers would first interact with these objects to reckon what they are and what can done with them. Leveraging these concepts, they could understand the internal structure of this task, without seeing all of the prob- lem instances. Remarkably, they further build cognitively executable strategies to rapidly solve novel problems. To empower learning agent with similar capability, we argue there shall be three levels generalization how an agent represents its knowledge: perceptual, conceptual, and algorithmic. In this paper, we devise the very first systematic benchmark that offers joint evaluation covering all three lev- els. This benchmark is centered around a novel task domain, HALMA, for visual concept development and rapid problem solving. Uniquely, HALMA has mini- mum yet complete concept space, upon which we introduce novel paradigm to rigorously diagnose and dissect learning agents' capability in understanding and generalizing complex and structural concepts. We conduct extensive experiments reinforcement learning agents with various inductive biases and carefully re- port their proficiency and weakness
2<4
INTRODUCTION
2>
2+2=0
Have you ever heard of Super Halma a fast-paced variant Halma? case you have not played Halma or its fast-paced variant before, we briefly introduce both of them here. Halma strategic board game, also known as Chinese checkers. The rules of Halma are minimal; can be perspicuously explained using basic concepts of numbers and arithmetic. To win the game, one needs to transport pawns initially in one's 's own camp into the target camp. In each turn, a player could either move into an empty adjacent hole and end the play, or jump over an adjacent pawn, place on the opposite side of the jumped pawn, and recursively apply this jump rule till the end of the play. While the standard rules allow hopping over only single adja- cent occupied position at a time, Super Halma allows pieces catapult over multiple adjacent occupied po- sitions in a line when hopping; see an illustration Fig. [ We will use the term Halma to specifically re- fer to Super Halma in the remainder of the paper.
1+1=2
(a)
(b)
2on-boddingg pawm
blocking
dilante
Figure Illustration of the Super Halma playing task. By playing the game with scarce supervi- sion, Ada should be able to learn hasic concepts of numbers and arithmetic, such concepts with both (a) valid and (b) invalid actions (jumps).
Now, imagine you are teaching your preschool cousin, Ada, to play Halma. Since she has not yet formed complete notion of natural numbers or arithmetic, verbally explaining the rules her will render in vain. Alternatively, you can play with her while providing scarce supervisions, e.g., if move allowed; you can even reward her when she successfully moves a pawn the target camp.
WW will make HALMA and tested agents publicly accessible upon publication. publicicccin.ii..oi.... ant for details.
See https: /en.. wi kidi httg://iil//cchieeeeeeeeeeeeeerr

---

Under review as a conference paper at ICLR 2021
By the time Ada could independently and rapidly solve unseen scenarios. we would know she has mastered the game. How many scenarios do you think Ada has to play before achieving this goal?
This Halma playing task is quintessential in the open-ended world; its environment is minimal yet complete playground to test the rapid problem-solving capability of a learning agent. Under lim- ited exposure to the underlying structure of the complex and immense concept space, we humans, by observing and interacting with entities, could form abstract concepts of "what it is" and "what can be done with it." The former one is dubbed semantics (Jackendoff) 1983) and the latter affor- dance (Gibson 1986). These abstract concepts, once accepted as know ledge, generalize robustly over scenarios; they are considered as milestones of human evolution in abstract reasoning and gen- eral problem solving (Holyoak et al.) [196).. In the case of Halma playing task, Ada would be able to solve unseen scenarios within no time if she were able to master (i) the abstract concept of natural numbers, emerged from and grounded to visual stimuli, (ii) both valid and invalid actions, and (iii) causal relations and potential outcomes risen from the grounded natural numbers and valid actions.
What is the proper machinery to learn these generalizable concepts from scarce supervisions? By scarce supervision, we mean the way to provide supervision is akin to how you teach Ada; one only provides sparse and indirect feedback without direct rules or dense annotations. By general- izable concepts, we emphasize more than the competence of memorization and interpolation; the learned representation ought to appropriately extrapolate and generalize in out-of-distributi narios. Such a superb generalization capability is often regarded as one of the celebrated signatures of human intelligence (Lake et al. 2015 Marcus 2018 Lake & Baroni 2018): it is attributed to rich compositional and casual structures in human mind (Fodor al. 1988). Inspired by these observa- tions, in this work, we quest for a computational framework to learn abstract concepts emerged in challenging and interactive problem-solving tasks, with a humanlike generalization capability: The learned abstract knowledge should be easily transferred to outtof-distribution scenarios.
sce-
The general context of interactive problem solving poses extra challenges over classic settings of concept learning; instead of merely emerging concepts, it further demands the learning agent to leverage such emerged concepts for decision-making and planning. Ada, after understanding mantics and affordance in Halma, can effortlessly perceive and parse novel scenarios (Zhu et al.] 2020). Yet, she would still struggle in strategically playing the game she needs to decide among multiple affordable moves. In essence, the central question is: If conceptual knowledge can general- ize as such, what meta-benete does it offer on solving unseen problems (Schmidhuber et al. 1996)? The classic decision-makee can develop cognitively executable strategies with high planning (Sanner) 2008) and exploration efficiency (Kaelbling et al. 1998); these strategies facilitate us solve problems rapidly in unseen scenarios. They are what we call the algorithms or heuristics of this task. Taking step further, Wang al.] (208):(Gues et al. (2019) hypothesize that modern reinforcement learning agents, incentivized by these meta-benefits, have already discovered such al algorithms. However, to date, their argument is still speculative since these agents have not been evaluated in tasks with rich internal structures yet limited exposure (Lake et al. 2017 Kansky et al. 2017). A diagnosis benchmark for generalization capability is thus in demand bridge communities of concept development and decision making.
account of these meta-benefits would be: Leveraging knowledge, we
The main contribution of this paper is a Halma-inspired competence benchmark: Humanlike Ab- straction Learning Meets Affordance (HALMA). We rigorously devise HALMA with three levels of generalization in visual concept development and rapid problem solving; see details Section 2 HALMA is unique in its minimum yet complete concept spaces, a miniature of compositional and causal structures in human knowledge. It dynamically generates test problems to informatively eval- uate learning agents' capability in out-of- tit-off-ditribution scenarios under limited exposure. We conduct extensive experiments with reinforcement learning agents to benchmark proficiency and weakness.
2 THREE LEVELS OF GENERALIZATION
Our motivations might seem, prima facie, bold. To convince readers and support our optimism, we summarize some recent progress in this section. In particular, provide taxonomy of three levels of generalization on a competency basis. Indeed, generalization is multifaceted phenomenon. Pre- vious evaluations for generalization were predominantly defined in a statistical sense, following the classical paradigm of train- evaluation test random split (Cobbe et al., 2019) while ignoring internal structures. However, we argue this classical paradigm should not be the only objective approach wherein agents can or should generalize beyond their experience (Barrett et al. 2018)) especially our goal is to construct humanlike general-purpose problem-solving agents (Lake et al. 2017).
2

---

Under review as a conference paper at ICLR 2021
Perceptual Generalization Perceptual generalization characterizes agents' capability to repre- sent unseen perceptual signals, e.g.. appearance or geometry in vision. In his seminal book, Vision, Marr (1982) describes the process of vision constructing set of representations, parsing visual sensory data into descriptions. Such descriptions provide conceptual primitives (Carey 2009) for agents' understanding of the environment, boosting the efficacy of downstream cognitive activities (e.g., memory, learning, and reasoning). Learning an object-oriented representation of independent generative factors without supervision is thus believed to be crucial precursor for the development of humanlike artificial intelligence. Although unsupervised disentanglement and segmentation (Es-)
lami et al. 2016 Higgins et al., 2017) resurged years ago, it is only till Locatello et al. (2019) did we realize the importance of evaluation on their generalization. More recently, Burgess et al. (2019),
Greff et al. (2019), and Lin et al. 2020) evaluate their seenttnglemennssemmenttee
models outside of training regimes, especially on unseen combinations of visual attributes and numbers of objects.
Although a hypothetically perfect semantic description can truthfully represent the primitive concept of "what it is," it could only contribute partially to achieving the understanding of "what can be done with it" (Montesano et al. 2008; Zhu et al., 2015). Humanlike agents should equip with such task- oriented abstraction, affordance, supported by compelling evidences in the field of developmental psychology; for instance, 18 to 24-month-old infants can distinguish bootstrapped concepts (Quine, 1960), such as "a walkable step is not a cliff" (Kretch & Adolph 2013). At a computational level, given a task specified by Markov decision process, irrelevant features should be abstracted out (Li ct al. 2006 Ferns et al., 2011 Khetarpal et al. 2020). Representation learned in this way bootstraps conceptual content. Recently, disentanglement as such has demonstrated efficacy (Gelada et al.
2019 Wayne et al.] 2018) and elementary perceptual generalizability (Zhang et al. 2020).
Conceptual Generalization While perceptual generalization closely interweaves with vision and control, conceptual generalization resides completely in cognition, assuming the readiness of all primitive concepts and some bootstrapped ones. The central challenge in conceptual generalization is: How well can an agent perform in unseen scenarios given limited exposure to the underlying configurations [Grenander] 1993)? It is connected with the Language of Thought Hypothesis (Fodor ct al. 1988 Goodman et al.] 2008): The productivity, systematicity, and inferential coherence in languages characterize compositional and causal generalization of concepts (Lake et al. 2015).
How to learn representations with conceptual generalization is still an open question, drawing in-
creasing attention in our community. With synthetic translation task, Take & Baroni (2018) reveal
the incompetence of general purpose recurrent models (Elman 1990, Hochreiter & Schmichuber,
Chung et al., (2014) in generalizing to (i) unseen primitives, (ii) unseen compositions, and (iii)
longer sequences than training data. Similar incompetence of relational inductive biases (Battaglia ct al. 2018) on hard compositional extrapolation has also been exemplified in abstract visual rea- soning (Barrett et al. 2018). Notably, there is also a line of research on emerging these linguistic
structures from bootstrapped communication (Lazaridou et al. 2018 Mordatch & Abbeel 2018).
Algorithmic Generalization Agents' understanding of the structured environment should be re- flected in their performance in solving novel problem instances; they ought to build strategies upon the developed concepts, resembling cognitive control in human mind (Rougier et al.. 2005 [Bovinick] & Cohen 2014). We use the term algorithmic generalization to describe such flexibility. Specifically, for a problem domain where the internal structure contains an optimal exploration strategy, algorith- mic generalization requires agents to discover this optimal strategy to explore efficiently in new problem instances. For example, in the domain of dependent bandit problems designed by [Wang] et al. (2016), there is one arm whose return leaks the index of the optimal arm. Given new prob- lem, agents who discovered the algorithm of this domain would first try the leaky arm and then go straight to the optimal arm. Furthermore, as an acid test, algorithmic generalization also measures the agent's ability in long-term planning in unseen problem configurations, after acquiring adequate information. Evaluation as such has been discussed by Tamar et al. (2016) and Guez et al. (2019).
Problem domains discussed above, however, still lack rich concept spaces, nor do they test agents' perceptual generalization, omitting the interaction among the three levels introduced in this paper. Essentially, they are still far-off from the famous Atari game, Frostbite, which is argued to be a testbed for humanlike problem solving (Lake et al. 2017). In this work, we introduce new problem domain to facilitate joint efforts towards representations with these three levels of generalization.
Conventionally, it is dubbed combinatorial generalization or systematic generalization. We use the term con- ceptual to highlight its functional signature.
3

---

Under review as a conference paper at ICLR 2021
(a) visual panels
(c) temporal grammar
all options
visual pamels
instances of visual panel
set options
2+3
1+2+2 C2 Q2een
option
MNIST digits
primitive action
more grenn
3 0 000
5>3
time
lacatite 126, 120
Secation (23 Sal
(N. +/
causal structure
game console
O
40
K
maze
Mindreeser
(b) spatial grammar
(c) maze
4D
O
problem generation, and concept space (sec Section 3.2 (a) Given a visual panel with various colored MNIST digits and a hint, an autonomous agent tasked to reach the goal in maze. The concept space guides the generation of the visual pancls; it consists of (b) spatial grammar, (c) temporal grammar, and (d) causal structure. (e) The semantics and affordance of the not shown the agent.
Figure 2: Illustration of the HALMA basics (sec Section 3.1
colored MNIST digits augmented on the corresponding maze; the
HUMANLIKE ABSTRACTION LEARNING MEETS AFFORDANCE (HALMA)
3.1 HALMA BASICS
The setup of HALMA is minimal and interpretable. Instead of replicating the entire game of Halma, we only preserve the most essential ingredients: The learning agent is cast as one pawn, navigat- ing around the "magical" Halma landscape by itself. simplify the environment without lost of generality, we build maze in grid-world for each scenario (or problem henceforth), resembling cognitive map of the agent. Distinct from vanilla grid-world maze games, HALMA is novel in terms of our design of its observation space and action space. The agent perceives neither the global map nor any local patch of the global map: instead, it is shown with a visual panel of various numbers of MNIST digits in various color, randomly scaled and placed; see Fig. 2 (a). These colored digits indicate the semantics of (i) the distance till wall towards each direction, (ii) the distance till the nearest crossing or T-junction towards each direction, and (iii) the distance and direction the goal; the visual panel only displays non-zero distances. For example, in Fig. (ig-((a) the left 5-grid away, and 3 indicates the nearest crossing is is 3-gnd away the left: the visual color of red refers to the semantics of "left." The agent will also be hinted with a symbol from the set fo, A. D. O} at any crossing for the correct direction; see an example of Fig. 2 (a). When mak- ing a decision, the agent needs to first select direction and then select either primitive action or an option composed by a sequence of primitive actions (Sutton et al. 1999) with maximum length max_opt_len. The direction set is (a, 4.D). The primitive action set, in terms of the number of moves, is [, [] this design of primitive numbers with a maximum three aligns with the doctrine of core knowledge in developmental psychology (Feigenson & Carey 2003 Dehaene, 2011]. If an option is selected, consecutive hops as in Halma are simulated; all observations from intermediate states will be skipped, and only the observation of the final state is provided. A move would fail if a wall stops the agent, leaving the agent's s position unchanged; failure moves bring penalties to the agent. The agent would receive positive reward when reaching the goal. Such design encourages the agent to comprehend which MNIST digit affords it to take which moves.
(a) (e), 5 indicates the wall
Essentially, HALMA is 2D contextual navigation game, sharing the same spirit with those in Mirowski et al. (017)) and Ritter et al. (2018). However, contexts in these prior works are elusive and conceptually meaningless. As such, they only evaluate generalization or algorithmic level. In stark contrast, HALMA is unique, possessing rich, crisp, and challenging configuration space of problems, semantics, and affordance; see details in the next subsection.
either the visuomotor
3.2 PROBLEM GENERATION AND CONCEPT SPACE
Generating HALMA problem consists of two sub-procedures: (i) generating a grid-world maze problem with valid optimal paths, and (ii) producing a set of visual panels, based on an explicit spatial grammar of the concept space, that uniquely represent observations in the maze.
4

---

Under review as a conference paper at ICLR 2021
Generating grid-world maze problem is intricate since HALMA is partially observable game. A randomly generated maze may perplex the agent with ambiguous observations that hinders the agent's formation of a coherent strategy; see Appendix [A] for an example. To alleviate this issue, instead of first generating complete maze and then producing optimal paths, our solution is to reverse this process by first generating valid optimal paths and then adding deceptive branches to construct a grid-world maze. Formally, a path is said to be invalid if an agent who possesses an oracle understanding of the concept space fails to make the oracle decision; such definition of validity is deeply rooted in the concept space that the agent is required to learn. We refer the readers to check Appendix A for an example of invalid optimal path, an example of a successfully generated maze with valid optimal path, an example sequence, and additional implementation details.
Producing visual panels heavily relies on the concept space. The concept space of HALMA consists of an explicit spatial grammar for visual panels, an implicit temporal grammar for actions and options, and an underlying causal structure that specifies the intersection of spatial and temporal grammar. For simplicity, we only introduce them verbally here; see an illustration in Fig. 2 their formal definitions in Appendix(Bi Intuitively, the spatial grammar produces all possible descriptions
of visual panels, spanning all configurations of semantics introduced in Section 3.1] To generate a visual panel for given state, we first sample an MNIST digit for each entry of its description and then sample a random scale and position. The sampled MNIST digit is then colored on the basis of its semantics, i.e., directions to a wall, a crossing, or a goal; see Fig. (b) and the legend. The temporal grammar produces all possible moves, either a single primitive action or a composed option, regardless of the visual stimuli. For instance, a non-terminal node : can be parsed into options opt, such as G + C + Q and 4 + + E see Fig. (c). Despite of their distinction in terms of how an option is decomposed into primitive actions, these options are equivalent in their causal effects. Specifically, these causal effects bind visual MNIST digits with digital actions based on one of the simplest mathematical structures in human cognition (Flavell) 1963): (N, +/-, <)); namely, natural numbers N. operations +/-, and relations < over N. For example (see also Fig. (d)), a learning agent expected to understand relations between 5 and 3 via
(s, <): the set of semantic generators with order over it, e.g., 3 5:
[. +/+//- -, => the set of affordance generators with operations and equality, e.g., 5 = 4:
0 = 4:400 +
+ = ....
1/,+/-
the set of affordance generators with operations and inequality, e.g.
5.
5 < D
+
Q
+ F.:
(C,
C/
>: the set of causal generators with operations and equality, egg., 5 = 3 +
3.3 TASK FORMULATION AND EVALUATION
We expect agents who developed the concept space leverage this knowledge and rapidly solve new problems in HALMA. To this end, we formulate this rapid problem-solving task with an objective to maximize the agent's 's rewards accumulated over a a. trials in novel problem instance:
E
1== - len(Ts)
7f 7/R( ((,,),,)a,..)).
Specifically, an agent's 's experience in each problem instance is dubbed an episode < <Wang et al. 2016), which terminates when a maximum number of steps L is reached or a maximum number of trials N have been accomplished. A trial proceeds with actions dr,,, spanning multiple steps t; it starts from an initial state 8q and terminates when the agent reaches the goal 8y (thus accomplished), or when it consumes the maximum number of steps H (thus failed). The agent is respawned to the initial state when trial terminates. It is awarded R(sg.)) .) if the trial is accomplished. The cumulative reward in one episode is the sum of temporally 7 decayed accomplishments. When one episode terminates, the agent is presented with the next problem.
Under this task formulation, learning agents should be evaluated against oracle solutions, analogous to ground-trute truth annotations in supervised learning; recall that the oracle agent has complete under- standing of the concept space and the problem domain. Since HALMA is partially observable domain, its oracle behavior consists of two aspects: optimal exploration and optimal planning. As introduced in Section 3.2 problems are generated by adding deceptive branches to optimal paths. Hence, the optimal exploration strategy is to stop at each crossing to obtain the hint from the visual
4 'For the sake of formalism, we adopt the terminology from General Pattern Theory (Grenander 1993). wherein the term generator refers to basic units in a configuration space. Intuitively, an object file (Kahneman et al. 1992). is semantic generator. It is also generator for configuration spaces of affordance and causality, for which actions/options also generators. We refer the readers to Appendix B for detailed formal definitions.
5

---

Under review as a conference paper at ICLR 2021
panel. Intuitively, the agent should understand "when two digits with the same color exhibited in the visual panel, the lesser one indicates the crossing, and should stop there for hint" based on the concept of (s, <) J (A. +/-, <). An oracle agent would sacrifice the first trial to explore; note that the cost is still low as it would explore along the optimal path with the guidance of hints, avoiding all deceptive branches. Afterwards, the oracle agent should retrieve its experience and merges con- secutive moves towards the same direction to form the optimal plan. Take the maze example shown in Fig. (e): during exploration, the agent sees 5 and a 3 in the visual panel and takes an option - until the wall. Then in the second trial, the agent should exploit (A, +/-, =) (/,,+/,,=) via + + Q With this or- acle agent, we can have evaluation metries normalized across different problems. Instead of directly calculating the ratio of Eq. (I) between proposed agents and the oracle agent, which involves strong non- non-linearity, carefully decompose it into three metries with more intuitive measures:
: t to obtain a hint D. which guides it to keep moving left
Ratio of invalid moves Pa = .ccl #innalid moves for semanties and affordance understanding;
L, len(T.)
Success rate of goal reaching Py = E.I N Σ, 5(5T,-1 = sg)] for leveraging concepts to explore;
Efficiency in exploration and planning Pp = E Σ len(T.) for algorithmic understanding.
3.4 GENERALIZATION TEST
One of our key contributions in HALMA is a novel paradigm to test agents' capability in all three levels of generalization, which extends the classical paradigm of statistical learning. Our training set consists of 100 mazes along with their visual panels; we summarize the statistics of these vi- sual panels in Appendix C to show that the generated dataset is balanced, yielding fair distributions of crucial statistics. Different from the classic paradigm, the evaluation of agent's 's performance in
HALMA would emphasize on the explicit extrapolation test, which should be conducted in the held-out compositional and relational configurations: such design echoes recent trend in evaluating agent's 's generalization capability (Burgess et al.] [211 [Lake & Baroni] [0088] Zambaldi et al.) 2019)) Compared to these prior domains, HALMA unique as a partially observable and interactive groblem-solvingg task, wherein an agent is tasked to autonomously learn the immense concept space and form the abstract knowledge. Hence, simply holding off a pre-selected, fixed subset of con- ceptual configurations would impose severe restrictions on problem generators. For instance, if we would like to allow agents to see a 4, they must be able to see a 3 by simply moving 4 [ from where they see 4. In other words, if we managed to strictly withhold 3 from agents, they would not see any red digits larger than in this interactive problem solving task. Therefore, an ex post evaluation protocol that dynamically generates tests is more desirable.
In this paper, we propose an ingenious solution: Instead of aimlessly generating large test set of random cases, we devise an algorithm to prouctively generate tailored tests in accord to what the agent might have learned; this design would produce a definitive and much more informative eval- uation of agent's competence. The intuition is simple: When a teacher finds a student consistently make right decisions during training, wherein the student only needs to understand 3 < 5 and 5 and 2 vs 4. To implement this
2- + : a. the teacher may quiz the student on protocol in HALMA, we first store agents' experience during training as their external memory MEM. We then construct a representation to emulate agents' knowledge bases (KB) for (5, <> and semantics, and
(A. (A.+/-,=) U (c, (/-+/- KB, tracks the agent's 's understood configurations KBave tracks the agent's understood configurations on affordance and causality. Here, we assume that (i) valid decision 5 in experience were made upon understanding inequality configurations, and (ii) agents understand configurations involving equality and operations in experienced transitions. With these KBs, we dynamically generate test problems with novel configurations, wherein agents should likewise act appropriately if they understood not only seen configurations but their underlying concepts; see details of constructing KBs and generating test problems in Appendix D
Tests in HALMA are on the competence basis: Conceptual generalization is built upon perceptual generalization, with the algorithmic generalization resides on top. Tests for perceptual generalization are backed by the spatial grammar, including unseen MNIST images and unseen compositions of visual attributes, i.e., shape and color. Tests for conceptual generalization are based on the concept of +/-,, =, <), consisting of novel equality and inequality configurations. Results of these two
TThis design reflects thesis argument, i.e., agents shall generalize their understanding from limited exposure to the concept space. An ablation study on the volume of training set can he found in Appendix G.T Note that some decisions may come from random exploration. We introduce threshold on the visitation count to filter them out.
6

---

Under review as a conference paper at ICLR 2021
tests are manifested in algorithmic generalization. Specifically, agents could only pass all of these tests by making right exploration decisions based on relations of novel digit pairs (d,, d2 [tpe),, where type refers to various directions. Inappropriate exploration may cause agent to miss hints at crossings to be trapped in dead-ends, resulting in failures of the tests. Moreover, these novel digit pairs also test the agents' understanding of the temporal grammar, requiring agents to make proper exploitation decisions by merging novel consecutive actions/options into greater option.
Since conceptual generalization connects the other two, all three levels of generalization are cov- ered when test problems are dynamically generated with novel configurations in (N, +/-,-, <) Recall that the generation mechanism of problem is to first generate an unseen configuration of optimal path and then add deceptive branches; the latter is pivotal for test problem since it involves generating novel digit pairs (d,, dz|Eype). By design, the lesser digit within pair should indicate the distance to the nearest crossing, and the greater the distance to the wall. Hence, agents could be tested by these novel digit pairs, queried based on the agent's KBs. We categorize the problems into:
Semantic Test (ST): 3B = (<d, dyltype) KBB) A (3, dzlx) KBs), i.e., testing visual panels differentiated from KBg in terms of color, shape, or other MNIST digits.
Affordance Test (ArT): XBAr7 = (Vx de (x) & KB3) ^ ((3(d), dg|x) E KBavo) (d1 = opt, e KBave A d2 opt, KBave)), L.e, testing inequalities inferred from equalities in KBAvo. opt denotes actions or options.
Analogy Test (AnT)): Ka = (d1, d3 d=|x) & KBStvaer) A (3Kd1, de [x), (d2, ]s|x)} c KBSTvarT) ( xx, (d',, x) (d,, x (BSTvArT); L.., testing inequalities in- ferred from the transitivity of <. KBSTvACT = KB KBACT-
Specific examples of these tests can be found in Table See Appendix D for detailed explanation.
4 MODELS AND EXPERIMENTS
The motivating questions of our experiments are: (i) Do model-free agents, exploiting generic in- ductive biases, develop concepts that generalize in a way, akin to human knowledge? (ii) If there are indeed certain meta-benefits induced by these architectural priors towards problem solving, are they achievable with only limited exposure to the concept space? As it is logistically challenging to experiment with all existing models, representative subset is culled for benchmark: model-free reinforcement learning agents (Wang et al., 2016 Zambaldi al., 2019) with gated memory mech- anism (Hochreiter& & Schmidhuber 1997). self-attention mechanism (Vaswani et al.) (017). or both. Notably, Wang et al. (2016) argued that when an RNN agent is fed with previous actions and re- wards, its LSTM module would emulate an inner reinforcement learning algorithm; the agent is thus learning to reinforcement learn. They demonstrated that the learned exploration strategy is more ef- ficient than near-optimal model-free exploration algorithm. Zambaldi et al. (019) argued that by exploiting stacked attention modules, Transformer agents can conduct iterated reasoning with seen relational units and generalize to unseen scenarios. By our evaluation protocol, however, these prior models did not demonstrate conclusive evidence to support all three levels of generalization pro- posed in this paper; hence, the precise level of generalization obscure. Crucially, neither of them evaluated the learned agents under limited exposure to a complex concept space as in HALMA.
Table T shows the full list of agents used in our experiments; see Appendix E for implementation details. All agents are trained with an off-the-shelf reinforcement learning method, TD3 (Fujimoto) et al. 2018). All agents' policies converged at the end of training.
To decouple the evaluation of conceptual generalization from perceptual generalization, conduct experiments with symbolic one-hot observations, which can be regarded as the ground- truth representation of perception; see details of this observation space in Appendix F.I All agents show relatively high invalid action ratio Pa in tests of random split, indicating their understanding of affordance is brittle even with the ground-trutt semantics. Under this precondition, we find that all agents can still perform relatively well in terms of goal-reaching Pg and efficiency Pp in ran- dom splits. However, when transferred to our generalization tests, MLP agents exhibits significant degradation. Agents with LSTM modules, on the contrary, can somehow maintain or even surpass their Pg. and Pp in training problems. One possible explanation to their high Pg is: With a memory mechanism, they learn to recover from dead-ends even if they missed the hints at crossings. Even though they also have higher Pp than MLP agents, consistent with the findings reported by |Wann et al. (2016), this measure is still disconcertingly low. Such low performance implies that agents do not understand the concept space well, especially terms of the temporal grammar. Transformer agents do perform better than MLP agents in generalization tests, but not as good as LSTM agents. In particular, even though Zambaldi et al. (2019) argued that Transformer agents such may learn
first
7

---

Under review as a conference paper at ICLR 2021
Table 1: Examples and results of generalization tests indicates problem is dynamically generated)
Models & Results
Test Type & Examples
SYMBOLIC LSTM
[max max. 1mam5)
VISUAL (max, J.nee)
MLP
TRAN
TRAN+LSTM
CNN+MLP
CNN+TRAN
SPACE
$:2214.11
12.12 2.14
14.7716.77
13:05
7..2
10.291261
16.45126
Training problems
1
99.231.663
57.22-3.07
95.851126
72.3325.70
75.761-4.77
58.3824.11
16.3322094
41.77
50.91-3.44
67.89:063
63,97:5.84
63.771.268
35,31:3000
12.02:1:17
Pa
37,02+1522
23.1-2210
14.85+445
$7.892200
S6. $6.70=2.30
56.91
58.38+1.00
Random split
Pg [
51,00:2.21
57.78-3.49
$2.82:0966
54,001294
7.58-0043
14.00:4424
3.67=0047
Py
54.91+2.85
45.15-1446
58.07+101
40.13+2.52
5.09=1.17
8,33+1 96
2.66 19
(J. S. I 7 BEOM
Pg]
55
30,00.816
41,671830
66.67113312
0.0010.00
00010000
00001000
lest S. N. 2) KEN.
Pp
19.90:22.18
24.02-21.20
16.34:3.90
35.74:5.85
0.00-0.00
0,00+:000
0.00
< 5 KBa
25.0018.16
63.33 6.24
43.3316.23
78.3311236
0.001
00010000
0.001
(3. & KB
7.37:42.3
26.31=2.34
12.22+11.3
34.79:4.25
0.00=000
0,00+0000
0.00=0000
3 4 2 KRAVEI
Py
41.67#2.36
10.00
36.6728.00
58. 10.33==1022
0.00=0.00
0,000000
0.00=0000
test (3 5) 2 KB..
15.10=00.35
28.91-7622
14:01+375
27.11=2.12
0.00=6000
0,00+0000
0.00=0000
(N KB lest (3, B) KB
31
10.00
23
71.776634
0.0000000
Py
11.68
17.15
17.6:3300
35/1013.11
0.00:0..0
0
T KBAvar
Ps
6.712336
100000
10:00
25000000
0.0000:00
0X0F0000
0X001000
lest (3
KBs
148::9152
51.56-0.15
5.83+0024
0.00=00:00
0.00
0.00=0000
C KBave. test 5 XBg.
Pe
000010000
86.67 9.43
50,001000
0.00100:00
0,0010000
1,00
Pa
0,00+4000
29.89-2.18
10.00:0000
0.00=0000
0.00:g0000
0.00==000
13 < v 5. 5,66
35.00=2.00
48. 48.33-4771
41.67=2.36
41.6721312
0.00=00.00
0.00000000
Apt
$7.77
Pp
12.1911.44
2..84_00.33
14.451166
22.03.6644
0.00.00.00
0,001,000
B) KORT
to plan, their lower Pp in HALMA task implies the opposite, at least under partial observation with- out a memory mechanism. Combining the benefits from the attention and the memory mechanisms, TRAN+LSTM agents outperform others in almost all generalization tests on both Pg and Pp- An- other interesting phenomenon is: By removing the constraint of limited exposure (e.g.. we increase the training volume 10x). ), all agents, no matter what inductive biases are encoded, achieve around 80% measured by Pg. and those with LSTM modules have Pp at around 45%; see details in Ap- pendix G.1 Since no state-of-the-art agents could pass the test Pp. we summarize the results of symbolic experiments as: In the spectrum of model-based vs model-free, emerged strategies still reside on the model-free side of the oracle agent. Significant efforts are needed to devise agents capable of humanlike conceptual and algorithmic generalization.
Under visual observation, however, all agents fail the generalization test when simply connected with a convolutional module, even in the easiest setup (max_opt_len-1)) Assuming CNNs do not offer sufficient priors induce an object-oriented, independently disentangled representation, we pretrain a state-of-the-ee iet al., [2020]. with all visual panels in the training set. The converged model exhibits remarkable generalization in reconstruction, segmentation, and detection, consistent with the results reported by Lin et al. (2020); see details in Appendix F3, One would expect that, by connecting the encoder of this powerful pretrained visual module with an RL agent using a Transformer module for the object-oriented encoding, the model would have superb performance. Counter-intuitively, our sults show that SPACE agents perform worse than CNN+TRAN agents even under random split. A further investigation reveals that the latent space of object slots fails to disentangle shapes or colors (e.g.. 3 vs 5). even though they can be substantially distinguished and reconstructed by the strongly nonlinear decoder. This explanation also accounts for SPACE agents' high invalid action ratio in test problems (Pa 58.38 + 1.20). In principle. they misunderstand affordance because they fail to recognize "what it is" in the first place. More details on this SPACE experiment can be found in Appendix F.3 Taking together, we argue that HALMA does extend the evaluation paradigm of per- ceptual generalization, posing new challenges the community of unsupervised disentanglement.
multi-object segmentation and disentanglement model, SPACE (Lin)
5 RELATED WORK
Recently, there emerges burst-out of benchmarks for diagnosing set of clearly defined compe- tencies of Al systems, which we draw inspiration from and sincerely honor. In a word, HALMA differentiates from all of them in its holistic evaluation towards all three levels of generalization.
Readers may be curious about the relation between HALMA and conventional navigation tasks such as MiroMski et al. (2017). We hope we have made it clear the difference between HALMA and them in Section 3.1 of main text: In these navigation tasks, there is only one maze, and new problem instances are simply new combinations of initial and goal states. Hence, rapid problem solving only requires agents to memorize the whole maze, whereas in HALMA the only shared structure between problem instances is the concept space. Going beyond memorization, HALMA requires two extra cognitive sallitiss-understanaddi
and reasoning. We also notice that another embodied naviga- tion task, the Habitat challenge (Savva et al. 2019). agents are indeed evaluated in completely un- seen environments, under the protocol of which Wijmans et al. 2020 has achieved close-to-optimal
8

---

Under review as a conference paper at ICLR 2021
performance with large-scale training. However, without clearly specified concept space, the eval- uation Habitat is akin the Random Split in HALMA under the setup of max. mon=1en=1. The reason why we emphasize max.opt_len is that the very idea of affordance is only interesting if the action/option space is large enough and highly structured. Otherwise, when max oottopt____________ _en=1,, agents with memory or attention do generalize well in both Random Split and our Dynamic Test; see detailed results in Appendix G.2 Perhaps the notion of affordance seems bit abstract in HALMA and can be more intuitive in visual semantic navigation and control (Yang et al. 2019 Chaplot al. 2020). We hope our work can inspire the future development of benchmarks for these topics.
Compositional Language and Elementary Visual Reasoning (CLEVR) (Johnson et al. 2017) is one of the earliest datasets that diagnose models' visual reasoning abilities. High-level reasoning skills required in CLEVR include counting, comparing, logical inference, and memory. The same set of skills are also required in HALMA, but without the guidance of language. Accounting for a sim- ilar purpose. Bahdannuu et al. (2019) propose minimalist alternative, Spatial Queries On Object Pairs (SQOOP). While relations in SQOOP are only spatial, benchmarks inspired by Raven's 's Pro- gressive Matrices (RPM) are proposed towards abstract visual reasoning (Barrett al. 2018 Zhang al., 2019), in which the capacity of sequential decision making not required. In sum, prior works listed in this paragraph are discriminative tasks. Different from them, the generative nature of interactive problem solving in HALMA akin to human exploration in the open-ended world.
As for planning and reinforcement learning, Wox-d and StarCraft II minigames (Vinyals al.) 2017) in Zambaldi et al. (2019) are tasks that also require relational concept learning; the concepts within, however, mostly spatial. In contrast, the concept space in HALMA is abstract and com- plex. The mapping from the visual space to the semantic space is non-trivial to learn, which requires agents' understanding of the temporal grammar and the causal structure. Moreover, HALMA is partially observable domain that requires dedicated efforts for exploration.
The closest one that is also inherently generative, compositional, and abstract is the Simplified ver- sion of the CommAl Navigation (SCAN) (Lake & Baroni 2018), an instruction following task. Essentially, SCAN seq2seq translation, with little uncertainty variation in primitives. Hence, does not test agents' perceptual generalization or algorithmic generalziation. In contrast, HALMA is task for visual concept development and rapid problem solving. Agents need to understand concepts from visuomotor experience and make smart decisions to acquire utility.
6 GENERAL DISCUSSIONS
In spite of its synthetic nature, we believe HALMA is an impeccable testbed for rapid problem solv- ing that resembles real-world ones. The dedicated design of its internal state facilitates in-depth and comprehensive analyses on agents' capacity in concept development, abstract reasoning, and meta learning that are otherwise impossible with existing mooblem-solving tasks. Agents can only pass the dynamically generated generalization tests if they possess adequate capacity to understand the abstract structure of this task and build a powerful solver upon this understanding. Our experiments demonstrate the inefficacy of model-free reinforcement learning agents in generalizing their under- standing, even when incorporated with generic inductive biases. Towards this end, we would like to invite colleagues across the machine learning community to join our challenge.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton. Layer normalization. arXiv preprint mrXiv:1607.06450. 2016.
Dzmitry Bahdanau, Shikhar Murty, Michael Noukhovitch, Thien Huu Nguyen, Harm de Vries, and Aaron Courville. Systematic generalization: What is required and can it be learned? In Interna- tional Conference on Learning Representations, 2019.
David Barrett, Felix Hill, Adam Santoro, Ari Morcos, and Timothy Lillicrap. Mcasuring abstract reasoning in neural networks. In Proceedings of International Conference on Machine Learning (ICML), 2018.
Peter Battaglia, Jessica B Hamrick. Victor Bapst, Alvaro Sanchez-Gonzale Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al. Re- lational inductive biases, deep learning, and graph networks. arXiv preprint 10XXvv/8060011 2018.
Matthew M Botvinick and Jonathan D Cohen. The computational and neural basis of cognitive control: charted territory and new frontiers. Cognitive Science, 38(6):1249-1283 2014.
Christopher P Burgess, Loic Matthey, Nicholas Watters, Rishabh Kabra, Irina Higgins, Matt Botvinick, and Alexander Lerehner. Monet: Unsupervised scene decomposition and represen- tation. arXiv preprint arXiv: 1901.191111111 13390, 2019.
Susan Carey. The origin of concepts. Oxford Press, 2009.
Devendra Singh Chaplot, Lisa Lee, Ruslan Salakhutdinov, Devi Parikh, and Dhruv Batra. Embodied multimodal multitask learning. In Proceedings of the Twenty-Ninth International Joint Confer- ence on Artificial Intelligence, IJCAI-20, 2020.
Junyoung Chung, Caglar Gulcehre, KyungHyun Cho, and Yoshua Bengio. Empirical evaluation of gated recurrent neural networks on sequence modeling. arXiv preprint arXiv:1412.3555 2014.
Karl Cobbe, Oleg Klimov, Chris Hesse, Taehoon Kim, and John Schulman. Quantifying generaliza- tion in reinforcement learning. In Proceedings of International Conference on Machine Learning (ICML), 2019.
Stanislas Dehaene. The number sense: How the mind creates mathematics. OUP USA, 2011.
Stanislas Dehaene and Jacques Mchler. Cross-linguistic regularities in the frequency of number words. Cognition, 43(1):1-29, 1992.
Jeffrey I. Elman. Finding structure in time. Cognitive Science, 14(2):179-211, 1990.
SM Ali Eslami, Nicolas Heess, Theophane Weber, Yuval Tassa, David Szepesvari, Geoffrey E Hin- ton, et al. Attend, infer, repeat: Fast scene understanding with generative models. In Proceedings of Advances in Neurul Information Processing Systems (NeurIPS), 2016
Lisa Feigenson and Susan Carey. Tracking individuals via object-files: evidence from infants' man- ual search. Developmental Science, 6(5):568-588) 2003.
Norm Ferns, Prakash Panangaden, and Doina Precup. Bisimulation metrics for continuous markov decision processes. SIAM Journal on Computing, 4066):166-11114, 2011.
Richard Fikes and Nils Nilsson. Strips: A new approach to the application of theorem proving to problem solving. Artificial Intelligence,
1971.
John H Flavell. The developmental psychology of Jean Piaget. D Van Nostrand, 1963.
Jerry A Fodor, Zenon W Pylyshyn, et al. Connectionism and cognitive architecture: A critical analysis. Cognition, 28 28(1-2):3-71, 1988.
Scott Fujimoto, Herke Hoof, and David Meger. Addressing function approximation error in actor- critic methods. In International Conference Machine Learning, pp. 1588-1159, 2018.
10

---

Under review as a conference paper at ICLR 2021
Carles Gelada, Saurabh Kumar, Jacob Buckman, Ofir Nachum, and Mare G Bellemare. Deepmdp: Learning continuous latent space models for representation learning. In Proceedings of Interna- tional Conference on Machine Learning (ICML), 2019.
James Jerome Gibson. The Ecological Approach to Visual Perception. Psychology Press, 1986.
Noah D Goodman, Joshua B Tenenbaum, Jacob Feldman, and Thomas L Griffiths. A rational anal- ysis of rule-based concept learning. Cognitive Science, 32(1):008-154, 2008
Klaus Greff, Raphaël Lopez Kaufman, Rishabh Kabra, Nick Watters, Christopher Burgess, Daniel Zoran, Loic Matthey, Matthew Botvinick, and Alexander Lerchner. Multi-object representation learning with iterative variational inference. In Proceedings of International Conference on Ma- chine Learning (ICML), 2019.
Ulf Grenander. General pattern theory: A mathematical study of regular structures Oxford mathe- matical monographs. Oxford University Press: Clarendon, 1993.
Arthur Guez, Mehdi Mirza, Karol Gregor, Rishabh Kabra, Sebastien Racaniere, Theophane Weber,
David Raposo, Adam Santoro, Laurent Orseau, Tom Eccles, et al. An investigation of model-free planning. In Proceedings of International Conference on Machine Learning (ICML), 2019.
Irina Higgins, Loic Matthey, Arka Pal, Christopher Burgess, Xavier Glorot, Matthew Botvinick, Shakir Mohamed, and Alexander Lerchner. beta-vae: Learning basic visual concepts with a con- strained variational framework. In Proceedings of International Conference on Machine Learning (ICML). 2017.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural Computation, 9(8): 1735-1780. 1997.
Keith Holyoak, Keith James Holyoak, and Paul Thagard. Mental leaps: Analogy creative thought. MIT press, 1996.
Ray Jackendoff. Semantics and cognition, volume 8, MIT press, 1983.
Justin Johnson, Bharath Hariharan, Laurens van der Maaten, Li Fei-Fei, C Lawrence Zitnick, and Ross Girshick. Clevr: A diagnostic dataset for compositional language and elementary visual reasoning. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2017.
Leslie Pack Kaelbling, Michael I. Littman, and Anthony Cassandra. Planning and acting in par- tially observable stochastic domains. Artificial Intelligence, 101(1-2):9--13, 1998.
Daniel Kahneman, Anne Treisman, and Brian J Gibbs. The reviewing object files: Object-specific integration of information. Cognitive Psychology, 24(2):175-219, 1992.
Ken Kansky, Tom Silver, David A Mély, Mohamed Eldawy, Miguel Nimrod Dorfman, Szymon Sidor, Scott Phoenix, and Dileep George. Schema networks: zero- shot transfer with generative causal model of intuitive physics. In Proceedings of International Conference on Machine Learning (ICML), 2017.
Xinghua Lou,
Khimya Khetarpal, Zafarali Ahmed, Gheorghe Comanici, David Abel, and Doina Precup. What can do here? a theory of affordances in reinforcement learning. In Proceedings of International Conference Machine Learning (ICML), 2020.
Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint arXiv:1412.69880 2014.
Kari S Kretch and Karen E Adolph. Cliff step? posture-specific learning at the edge of drop-off. Child Development, 84(1):226-240 2013.
Brenden Lake and Marco Baroni. Generalization without systematicity: On the compositional skills of sequence-to-sqquenee recurrent networks. In Proceedings of International Conference on Ma- chine Learning (ICML), 2018.
11

---

Under review as a conference paper at ICLR 2021
Brenden M Lake, Ruslan Salakhutdinov, and Joshua B Tenenbaum. Human-leved concept learning through probabilistic program induction. Science, 350(6266):1332-113333 2015.
Brenden M Lake, Tomer D Ullman, Joshua B Tenenbaum, and Samuel J Gershman. Building ma- chines that learn and think like people. Behavioral and Brain Sciences, 40, 2017.
Angeliki Lazaridou, Karl Moritz Hermann, Karl Tuyls, and Stephen Clark. Emergence of linguistic communication from referential games with symbolic and pixel input. In International Confer- ence on Learning Representations (ICLR), 2018
Lihong Li, Thomas J Walsh, and Michael L Littman. Towards a unified theory of state abstraction for mdps. In International Symposium Artificial Intelligence and Mathematics, 2006.
Zhixuan Lin, Yi-Fu Wu, Skand Vishwanath Peri, Weihao Sun, Gautam Singh, Fei Deng, Jindong Jiang, and Sungjin Ahn. Space: Unsupervised object-oriented scene representation via spatial attention and decomposition. In International Conference on Learning Representations (ICLR), 2020.
Francesco Locatello, Stefan Bauer, Mario Lucic, Gunnar Raetsch, Sylvain Gelly, Bernhard Schölkopf, and Olivier Bachem. Challenging common assumptions in the unsupervised learn- ing of disentangled representations. In Proceedings of International Conference on Machine Learning (ICML), 2019.
Gary F Marcus. The algebraic mind: Integrating connectionism and cognitive science. MIT Press, 2018.
David Marr. Vision: A Computational Investigation into the Human Representation and Processing of Visual Information. Henry Holt and Co., Inc., USA, 1982.
Piotr Mirowski, Razvan Pascanu, Fabio Viola, Hubert Soyer, Andy Ballard, Andrea Banino, Misha Denil, Ross Goroshin, Laurent Sifre, Koray Kavukcuoglu, al. Learning to navigate in complex environments. In International Conference on Learning Representations (ICLR), 2017.
Luis Montesano, Manuel Lopes, Alexandre Bernardino, and José Santos-Victor. Victor. Learning object affordances: from sensory-motor coordination to imitation. Transactions on Robotics (T-RO), 24 (1):15-23 2008
Igor Mordatch and Pieter Abbeel. Emergence of grounded compositional language in multi-agent populations. In Proceedings of AAAI Conference on Artificial Intelligence (AAAI), 2018
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830, 2011.
Willard Van Orman Quine. Word and object. MIT press, 1960.
Samuel Ritter, Jane Wang, Zeb Kurth-Nelson, Siddhant Jayakumar, Charles Blundell, Razvan Pas- canu, and Matthew Botvinick. Been there, done that: Meta-learning with episodic recall. In Proceedings of International Conference on Machine Learning (ICML), 2018.
Nicolas P Rougier, David C Noelle, Todd S Braver, Jonathan D Cohen, and Randall C CO O'iRellly Pre- frontal cortex and flexible cognitive control: Rules without symbols. Proceedings of the National Academy of Sciences (PNAS), (02(20):3388-734) 2005.
Scott Patrick Sanner. First-order Decision-theoreet planning in structured relational environments. PhD thesis, University of Toronto. 2008
Manolis Savva, Abhishek Kadian, Oleksandr Maksymets, Yili Zhao, Erik Wijmans, Bhavana Jain, Julian Straub, Jia Liu, Vladlen Koltun, Jitendra Malik, al. Habitat: A platform for embodied ai research. In Proceedings of the IEEE International Conference on Computer Vision, pp. 9339- 9347, 2019.
12

---

Under review as a conference paper at ICLR 2021
Juergen Schmidhuber, Jieyu Zhao, and MA Wiering. Simple principles of metalearning. Technical report, IDSIA, 1996.
Richard S Sutton, Doina Precup, and Satinder Singh. Between mdps and semi-mdps: A frame- work for temporal abstraction in reinforcement learning. Artificial intelligence, 112((12):181-
211, 1999.
Aviv Tamar, Yi Wu, Garrett Thomas, Sergey Levine, and Pieter Abbeel. Value iteration networks. In Proceedings of Advances in Neural Information Processing Systems (NeurIPS), 2016.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Eukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Proceedings of Advances 2017.. 2017.
in Neural Information Processing Systems (NeurIPS),
Oriol Vinyals, Timo Ewalds. Sergey Bartunov, Petko Georgiev, Alexander Sasha Vezhnevets, Michelle Yeo, Alireza Makhzani, Heinrich Küttler, John Agapiou. Julian Schritwieser, al. Star- craft ii: A new challenge for reinforcement learning. arXiv preprint 1rxiv:108.00477 2017.
Jane X Wang, Zeb Kurth-Nelson, Dhruva Tirumala, Hubert Soyer, Joel Z Leibo, Remi Munos, Charles Blundell, Dharshan Kumaran, and Matt Botvinick. Learning to reinforcement learn. arXiv preprint arXiv:1611.057633 2016.
Jane X Wang, Zeb Kurth-Nelson Dharshan Kumaran, Dhruva Tirumala, Hubert Soyer, Joel Z Leibo, Demis Hassabis, and Matthew Botvinick. Prefrontal cortex as a meta-reinforcement learning system. Nature Neuroscience, (6)88660-866, 2018
Greg Wayne, Chia-Chun Hung, David Amos, Mehdi Mirza, Arun Ahuja, Agnieszka Grabska- Barwinska, Jack Rae, Piotr Mirowski, Joel Z Leibo, Adam Santoro. et al. Unsupervised predictive memory a goal-directed agent. arXiv preprint arXiv: 1803. 10760, 2018
Erik Wijmans, Abhishek Kadian, Ari Morcos, Stefan Lee, Irfan Essa, Devi Parikh, Manolis Savva, and Dhruv Batra. Dd-ppo: Learning near cear--eerfet pointgoal navigators from 2.5 billion frames. In International Conference on Learning Representations, 2020.
Wei Yang, Xiaolong Wang, Ali Farhadi, Abhinav Gupta, and Roozbeh Mottaghi. Visual semantic navigation using scene priors. In International Conference on Learning Representations, 2019.
Vinicius Zambaldi, David Raposo, Adam Santoro, Victor Bapst, Yujia Li, Igor Babuschkin, Karl Tuyls, David Reichert, Timothy Lillicrap, Edward Lockhart, et al. Deep reinforcement learning with relational inductive biases. In International Conference on Learning Representations (ICLR), 2019.
Amy Zhang, Rowan McAllister, Roberto Calandra, Yarin Gal, and Sergey Levine. Learning invariant representations for reinforcement learning without reconstruction. arXiv preprint arXiv:2006. 10742, 2020.
Chi Zhang, Feng Gao, Baoxiong Jia, Yixin Zhu, and Song- ChungChunnaa Zhu. Raven: dataset for relational and analogical visual reasoning. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2019.
Song-Chun Zhu and David Mumford. A stochastic grammar of images. Now Publishers Inc, 2007.
Yixin Zhu, Yibiao Zhao, and Song-Chun Zhu. Understanding tools: Task-oriented object modeling, learning and recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2015.
Yixin Zhu, Tao Gao, Lifeng Fan, Siyuan Huang, Mark Edmonds, Hangxin Liu, Feng Gao, Chi Zhang, Siyuan Qi, Ying Nian Wu, Josh B Tenenbaum, and Song-Chur Zhu. Dark, beyond deep: A paradigm shift to cognitive ai with humanlike common sense. Engineering, 6(3):310-345, 2020.
13

---

Under review as a conference paper at ICLR 2021
CONTENTS
Problem Space of HALMA
S2
A.1
Validity of Optimal Paths
S2
A.2 Generating Maze Problems
S3
A.3 An Example Trial
S3
Formal Definitions of Concept Spaces
S4
B.
I Preliminary
S4
B.2 Concept Spaces of HALMA
S6
Statistics of Visual Panels
S8
D Dynamically Generate Generalization Tests
S9
Details of Models
S11
Hyper-parameters of TD)
$11
E.2
Architecture of Agents
$11
Experimental Details
S13
Task Parameters and Experimental Protocol
$13
Learning Curves
S14
SPACE Mode]
S14
Additional Experiments
S15
G.1
Ablation Study the Volume of Training Set
S15
Ablation Study on the Maximum Option Length max opt 1en
S18
SI

---

Under review as a conference paper at ICLR 2021
A PROBLEM SPACE OF HALMA
A.1 VALIDITY OF OPTIMAL PATHS
(a)
(b)
(c)
9
3
8 q
3
q
5
9
(d)
Figure S1: Examples mazes and visual panels. (a) (b) Mazes have valid optimal paths in HALMA, high- lighted in green and blue. (c) A maze configuration leads to ambiguous observations, highlighted by a red circle at the bottom-right corner. (d) (e) Visual panels correspond to the corner highlighted in blue in (a) (b), respectively. (f) Visual panels corresponds the corner, highlighted in red in (c).
A common method to generate mazes in the grid-world is to (i) use randomized Prim's 's algorithm to create connected area in the grid, and (ii) decide the positions of initial state and goal state, which naturally produce an optimal path between them. However, these randomly generated mazes may lead to ambiguous observations in HALMA and hinder the agent's formation of coherent strategy. Specifically, let us look at the example mazes as shown Fig. ST all three configurations could be generated by the Prim's algorithm. Mazes in Fig. ST (a) (b) indeed produces valid optimal paths in HALMA. Unfortunately, the maze in Fig. SI (c) leads to ambiguous observations, highlighted by red circle the bottom-right. Below, we analyze them in-depth one by one. Recall that in HALMA, the agent observes visual panel that contains several MNIST digits indicating the surrounding maze layout and the position of goal state. At the bottom-right Fig. (a), the agent may observe visual panels as in Fig. (T (d), wherein a and
indicate that there are walls 1-grid away to the left and 3-grid away right above 4. The agent can also know from & and 9 that the goal state is 4-grid away the right and 9-grid away above Hence, the agent should make towards the direction of goal; in this case, it is d, the direction that 3 and 9 align on. The same strategy would work in all corners highlighted in green blue circles in Fig. ST (a) (b). However, the strategy may fail at the bottom-right corner in Fig. ST (c), wherein the agent may observe a visual panel depicted in Fig. (I). This visual panel contains a & and 9, indicating that there are walls 8-grid away to the left and 9-grid away above a. The visual panel also includes a 3 and a 9, indicating that the goal state 3-grid away the left and 9-grid away right above a. By adopting the very same strategy described above, the agent would be able to choose either or However, based on the global map. we know that only is correct.
affordable move
To eliminate the aforementioned ambiguity, instead of first generating the complete maze and then producing the optimal path, our solution to reverse this generation process, i.e., first generating the valid optimal path that rules out the ambiguity and then adding deceptive branches to construct grid-world maze. Formally, a path is considered invalid if an agent possessing an oracle understand- ing of the concept space and acting in accord to the above strategy fails to make proper decisions. We find that valid optimal paths can typically be divided into "L'-pd segments (see Fig. ST (a) (b)), whereas invalid paths are commonly 'C' C'-shaped, rendering the observations at of their cor- ners ambiguous. In short, each single step on the valid optimal path from the initial state position to the goal state position should reduce the Manhattan distance the goal state position by 1.
S2

---

Under review as a conference paper at ICLR 2021
A.2 GENERATING MAZE PROBLEMS
Figure $2: Illustration of valid optimal path generation. Given the initial state position and the goal state posi- tion, one can determine directions where the optimal path should expand towards. For example, (a) Based on the initial state position. the optimal path can only expand upwards or to the right to reach the goal state position. (b) Examples of possible valid optimal paths.
After clarifying the validity of optimal paths, we are able to build a pipeline automatically generate the desired mazes. Assuming that the position the initial state on the bottom-left to the position of the goal state (see an example in Fig. (2), the optimal path should only expand upwards or to the right to reach the goal state position. Hence, given the horizontal offset m and vertical offset n from the initial state position the goal state position, there should be C(m + 2, 1) valid optimal paths in total. Note that in HALMA, although all the positions the initial state and the goal state restricted within 10x 10 grid, it is able to produce 738, 980 possible optimal paths, exhibiting a rich and immense problem space in HALMA.
Next, uniformly sample the optimal path from the maze set and add deceptive branches these optimal paths. To maintain the validity of optimal path, we add hint (i.e., D. O. A. or o) each T-junction and crossing indicate the direction the agent should move towards. In theory, the deceptive branches can be arbitrar- ily complex as they do not influence the valid- ity of the optimal path. To test whether an agent understands the concept of these hints and suc- cessfully transfers the Iearned knowledge to novel problems, set the average depth of de- ceptive branches to 2 in the training set and 5 in the testing set. To provide sufficient training data for agent to recognize these hints, set the average branching number to in the training set.
(a)
(b)
Figure S3: An example of adding deceptive branches
the valid optimal path.
A.3 AN EXAMPLE TRIAL
In this section, we visualize an example trial completed by the oracle agent to further illustrate HALMA. The example trial finished in steps; consecutive frames are shown in Fig. SS4 Below, we provide detailed explanation of how the oracle agent makes its decision at each step:
(a) The oracle agent is spawned an initial state position, highlighted by the red dot in the maze panel in Fig. S4 (a). Its observation is the visual panel, consisting of MNIST digits and A hint. Recall that ground-truth semantics of A indicates that the agent should move to the right, i.e., Therefore, the agent who understands the meaning of A would only need to know the distance to the wall and to the nearest T-junction or crossing to the right in order decide which action to take. Finally, recall that the yellow color is connected with i the agent needs to make a comparison between the a and the 5, and chooses the lesser digit (i.e., as the distance it moves
We will the crossing refer either of them henceforth, well in the main text.
S3

---

Under review as a conference paper at ICLR 2021
2
7
3
u
5
>
2
2
5
3
4
2
2
5
2
2
3
22
H
2
6
(a) step
(b) step 2
(c) step 3
(d) step 4
3
?
2
2
a
3
6
2
2
2
2
H
(e) step 5
(f) step 6
(g) step 7
(h) step 8
Figure $4: Visualization of example trial completed by the oracle agent 8 steps. Mazes at the Nottom-right (a)-(h) illustrate the trajectory of the oracle agent.
(b)-(d) In these frames, the oracle agent takes similar actions as in Fig. S4 (a). Note that in Fig. S4
(d), there only one yel low color MNIST digit (i.e., / the visual panel; therefore agent may not need to make comparisons between digits. Hints A appear in all these visual panels since the oracle agent always stops at crossings.
(e) The oracle agent does not observe any hints for direction (i.e., (O, (0,0, A. O}) in the visual panel because is not at crossing, therefore needs to reason from the observation to decide which direction to move towards. The 2. and the white digit indicate that the goal state position is 2-grid below and 2-grid to the right. Additionally, the agent also observes ye 1 ow digit in the panel, which indicates that the agent's current position is against the wall to the right. Therefore, the agent should move downwards. Finally, recall that the green color is connected with the agent needs make comparison between the and the 4, and chooses the lesser digit (i.e., 1) as the distance it moves
(g-(g) The oracle agent takes similar actions in these frames in previous frames. Note that in frame (g), the hint is O, which indicates that the agent should move downwards (i.e., w). Additionally, the a and indicate that the goal state position is downwards 1-grid away, and there is no obstacle in the way until 2-grid away. The oracle agent can infer that it should move downwards w by step reach the goal state position.
(h) This frame shows the goal state in this trial. The example trial ends at this frame.
B FORMAL DEFINITIONS OF CONCEPT SPACES
B.1 PRELIMINARY
For the sake of formalism, we borrow the terminology from the General Pattern Theory (Grenander) 1993). In case readers are not familiar with the General Pattern Theory, it is mathematical study of regular structures configuration spaces, patterns to account for the combinatory principle of world. Adopting the language of abstract algebra, Grenander calls the basic unit of regular strueture/confiiuuratoo space a generator, generically denoted as 9i- Any 9: is associated with a number of bonds By. whose value (y(9) shall be within the bond value space B. Generators
S4

---

Under review as a conference paper at ICLR 2021
combined together by connectors. A connector is graph, say with sites. When generators placed on connectors' sites, we have a configuration, c (g1: 92, 92..... In), which comes together with set of bond relations p : B x B (TRUE, FALSE). A configuration is called regular if all bond relations return TRUE.
Despite of its generality, the formal language used by Grenander might appear somewhat abstract peculiar to researchers in our community. Hence, we further elaborate below, from the perspective of grammar. grammar is regular structure, mostly studied the community of natural language or linguistics to elucidate the combinatorial expressiveness in generating an immense set of config- urations by composing only a considerably smaller of words, using production rules. To account for the similar compositional and hierarchical nature in visual scenes, Zhu & Mumford (2007) in- troduced stochastic grammar to the community of vision. They proposed an image grammar in an And-Or Graph (AOG) representation, where each Or-node points to alternative sub-configurations, and each And-node is decomposed into a number of sub-components. An AOG represents (i) the hierarchical decompositions from scenes to primitives and pixels, via non-terminal and terminal nodes, and (ii) the contexts for spatial and functional relations by horizontal links among the nodes. Below, to make this appendix self-contained, we summarize some key definitions:
Definition 1 (Vocabulary), The vocabulary V is a set of generators g((a),, each associated with its bonds, 3g (B.,1, ..., (1)d a, is vector of attributes. For instance, visual generator may contain material properties of object or the gender of person its attributes Bonds need be connected with other bonds to form attributed relations; see the next definition.
Definition 2 (Attributed Relations). Given an arbitrary of generators V, binary relation is subset of the product set V x V
{(u, v}} V V.
An attributed binary relation is augmented binary relation with vector of attributes and p
E = {(u, 0; p) e V},
where (u, represents the connector that binds and v, and p(s, is real number measuring the compatibility between and v. Then (V, E) is a graph, expressing the generalized relation E' on S. It is the relation that you are familiar with in object-oriented language such First-Order Logics. For instance, the distance between two objects is an attributed relation. A k-way attributed relation defined in similar way as subset of V
Definition 3 (Configuration). A configuration C is one-layer graph, often flattened from its hier- archical representation
C = (V, E).
For a visual scene, it is spatial layout of entities in a scene at certain level of abstraction.
Definition 4 (Parse Graph). A parse graph pg consists of hierarchical parse tree (defining "verti- cal" edges) and a number of relations E (defining "horizontal edges"):
pg Ept,
The parse tree pl is also an And-tree, whose non-terminal nodes are all And-nodes. The decompo- sition of each And-node into its parts is given by a production rule, which now produces not string (like in natural language or linguistics) but a configuration:
σ A
E).
A production should also associate the open bonds of A with open bonds in C. The whole parse tree a sequence of production rules:
pt = (a), ,,))
The horizontal links E consists of a number of directed or undirected relations among the terminal non-terminal nodes:
== U Er, U Ery-
These relations can be spatial relations, semantic relations, affordance relations, and causal rela- tions. A parse graph pg, when collapsed, produces series of flat configurations each level of abstraction/detail:
pg
C.
In computer vision, attributes are some properties of objects or agents that tend to remain the same.
S5

---

Under review as a conference paper at ICLR 2021
Definition 5 (And-Or Graph). An And Or Graph is 6-tuple for representing grammar G.
G= (S. VN, Vr, R,
S is the root node of a scene, VN V Var set of non-terminal nodes, including an And- node set Vand and an Or-node set Vor, The And-nodes plus sub-graphs formed by their children are the productions, whereas the Or-nodes are the vocabulary items. Vr is set of terminal nodes, for instance, visual primitives, parts, and objects. R is number of relations between the nodes, Σ the set of all valid/regular configurations derivable from the grammar, i.e., its language. P the probability model defined on the And-Or Ordrr Graph.
In sum, generic representation, an And-Or Graph can represent the hierarchical and relational knowledge of a visual scenario - In the following subsections, we concretely define the configuration space of HALMA by grounding abstract notions in this subsection to specific components.
B.2 CONCEPT SPACES OF HALMA
Definition 6 (Axioms for Equivalence Relation =). An equivalence relation is binary relation that reflexive, symmetric, and transitive. For any generators 91, I2. and Ø3:
gl = 91. (Reflexivity)
Ø1 D2 if and only if 92 91. (Symmetry)
if 91 = and 92 93. then 91 93. (Transitiviity)
Definition 7 (Axioms for Partial Order Relation <). A partial order is binary relation that is reflexive, antisymmetric, and transitive. For any generators 9l, 92. and g3:
91 < 91, (Reslexivity) if gi & 92 and 92 & 9i, then 9I = 92. (Antisymmetry)
gi $ 92 and 92 93. then 91 & 93- (Transitivitty
Definition 8 (Addition on Nature Numbers +). Given N and its successor function s by Peano
Axioms, may have a group (N, +) if we define addition + as: for n, m E N,
n + 0 n, n + s(m) s(n m).
Definition (Subtraction on Nature Numbers -). Given N and E,
* let m, E N. such that & let p N. such that n m + p-
We define subtraction - as Definition 10 (Spatial Grammar of HALMA). The spatial grammar of HALMA an Spatial And-Or Graph (S-AOG), which is 6-tuple
Gg (Ss, VNo: Vr. Rs, Ps)
where Sş is the root node that represents the set of all visual panels, thus an Or-Node con- nected nodes in VNg. There only one element in VNg. representing an instance of visual panel. v is a Set-Node since the number of digits in the panel may vary with different state; re- call that it is because zero does not appear in the panel. u produces all MNIST digits d, (or hints) in the panel; it is a composed concept. These MNIST digits consist the terminal node Vr.. They are attributed with color, scale, location, indication, and category. Specifically, color = {red, orange, yellow, green, cyan, blue, purple, white), and indicat
{wall crossing, goal). Ideally. the visual panel contains all nature num- bers, category* = N o (o. Currently, however, we only consider category = (1, 3, 4, 5, 7, 8, 9} u (0.4.0)) There bijection between color and (.) x indication, on, which gives rise to a partition, type, over Vrz, As terminal nodes, Vr, are atomic generators, hence primitive concepts. Though there can be many possible relations between these generators (e.g., distance between MNIST digits, ordering of scale between MNIST digits), only the (strict) partial order over category
J.D. i.e., (s, <) crucial to the task of HALMA. The definition of (S, <) would come clear once we define S and how the concept of N is boot- strapped and grounded to Vr.. P depends on the underlying maze problem since the valid configu- ration space Σg of this grammar is all descriptions of states.
"Note that by representation, we do not necessarily mean how artificial agent should represent such knowl- edge. Rather, is formalism for humans understand the internal structure of HALMA.
S6

---

Under review as a conference paper at ICLR 2021
Definition 11 (Semantics in HALMA), The semantics S in HALMA is relation, subset of Vrs x category x
S c Vr x category X
which is the ground-trume truth labeling of MNIST digits and their colors. For simplicity, we would slighly abuse this notion: In the remainder of the paper, we may regard & as function Vr;- - category x and also regard the range of this function.
Definition 12 (Temporal Grammar of HALMA), The temporal grammar of HALMA is a Temporal And Or Graph (T-AOG), which is a 6-tuple
GT = (Sr, VN,, VT,, Rr, Er, Pr),
where ST is the root node that represents the set of all options, thus an Or-Node connected to elements in VNg. Different from the spatial grammar, the temporal grammar has richer hierar- chical structure, therefore there are more than one element in VNg. each representing an option opt. An option is composed concept, which produces its constituting options/actions. The pro- duction rule p is defined by the operation +. Production terminates when reaching terminal nodes VT, (.O.C) Since each of them mapped to semantic meaning (i.e., moving O, 1, 2, or steps), they are primitive concepts of this grammar. All actions and options are attributed with , ).)), which regularizes the production to be within the same ype. Idcally, if could build maze with infinite size, for each type, the production rule would specify a group over all nature numbers (N, +). With that said, the only element in Ry is equality =. If we represent all elements in (N, +> with sequences of primitive set along with equality over them, we have the valid configuration space Er. P is the prior distribution of this numerical decomposition.
Definition 13 (Affordance in HALMA). The affordance A in HALMA is relation, subset of VTg x (Vnz O VTz)
A VTg X (VNT VTy),
which is a partial 3 relation between the semantics of atomic generators in the spatial grammar and all generators in the temporal grammar. It is partial relation because defined within each type and its inverse. Namely, it is defined based on (N. +/-, .). An action/option is affordable state if this relation returns true. Hence, affordance is bootstrapped concept emerged from agents' interaction with the environment. Recall that there may be two MNIST digits with the same color in one panel; the lesser one indicates the distance till the nearest crossing, and the greater one indicates the distance to the wall. Regardless of their difference in semantics, both of them fit this definition well, though only the greater digit indicates the ground truth affordance in the current maze.
a
Definition 14 (Causal Structure of HALMA). The causal structure of HALMA is Causal And-Or Graph (C-AOG), which is 6-tuple
Gc=(Sc: VNe. Vra: Ro, Ec,
where Se is the root node that represents the set of all scenarios, thus an Or-Node connected to elements in VNO. Ge links Gs and GT together. Since the environment of HALMA is Markovian, we have Eg C Es x Σx Es] [1] With that said, generators in the causal structure include VN₂ u Vrs and VN, Vry. Namely, VNe VNS U VN Vro VTs Vr,- Definitions of production rules in the causal structure inherit from the spatial grammar and the temporal grammar. What uniquely defined here is Rc {<S, <) +/- <). +/-, -}} All these three relations are derivable from (N, +/- =, <). In the current setup of HALMA, Po is deterministic. Reader who are familiar with symbolic planning may find the similarity between Gc and STRIPS-style action languages (Fikes & Nilsson| 1971). Specifically, affordance A corresponds to the precondition of an action, whereas causality corresponds to the effect of an action, to be defined below.
Definition 15 (Causality in HALMA). The causality C in HALMA is relation, a subset of Vry x (VNr U Vz,) x Vrs
c V1s (VNr Vir) x Vis,
which is partial = relation between (i) the Cartesian product of the semantics of atomic generators in the spatial grammar and (ii) all generators in the temporal grammar and (iii) the semantics of atomic generators in the spatial grammar. Similar to the semantics in HALMA, we would somewhat abuse its notion and refer to it as a function Vr, (VN, U VTZ)) VT Similar to A. is partial relation because defined within each type and its inverse. For domains where it is defined, its definition is based on <N,+/-,>> It is also bootstrapped concept emerged from interaction.
Otherwise, causal configurations would be non-Markovian, Ec = (Eis x Fx))* Fis-
S7

---

Under review as a conference paper at ICLR 2021
C STATISTICS OF VISUAL PANELS
2000
1750
Ocnirrence num.
1500
Occumnnce hum.
800
1250
1000
600
250
Red
Orge.
Om.
Cyan
Blue
Prpl.
Wht.
Color
Panel digit numn.
(a) Colors
(b) Number of digits in panel
Log.
Linear fi:
Log octumeince nim.
Oscurence num.
3000
2000
1000
1
2
9
Digit
Digil
(c) Digits distribution 10
Digit distrihution in log-scale
Figure S5: Key statistics of visual panels in HALMA training set. Each training set contains 100 HALMA grid-world mazes. We randomly sample 10 training sets and report the mean and standard deviation of the occurrence count of (a) colors, (b) number of digits in a panel, (c) digits distribution over these 10 sets, and (d) digits distribution in log-scale.
Recall that in HALMA, we use eight colors, ie., red, orange, yellow, green, cyan, blue, purple, and white, to specify the type of digits. Digits indicating the distance till wall or the nearest crossing towards each direction (iee,, 4 a >. and v) are colored red, orange, yellow, and green, respectively. Digits indicating the offset to the goal state colored cyan, blue, purple, and white. Following the design of CLEVR (Johnson et al. 2017). in HALMA, we deliberately control the distribution of visual attributes, especially of COLOR, by sightly adjusting generated mazes to form a uniform distribution
digit type. Such design help to avoid possible strong biases in the data that agents can exploit correctly take actions without reasoning. Below, we report key statistics of visual panels in the training set to demonstrate the uniformity of attributes distribution.
Fig. S5 (a) illustrates the color distribution of the visual panels. We produce an approximately uni- form distribution for the color connected with distance walls and crossings (i.e., red, orange, yellow, and green) and for the color connected with offiset to goal state (i.e., cyan, blue, purple, and white) separately. We uniformly sample optimal paths and add deceptive branches when creating the mazes in the training set (see details in Appendix A to form this distribution as an attempt to mitigate the color-conditional bias in the training set.
Fig. S5 (b) shows the distribution of number of digits in the panel. Number of digits in the panel are an unimodal distribution. More than 90% panels in the training set has number of digits between 3 and 6. Only <10% panels have 1-2 or 7-8 digits. No panel has number of digits greater than 8.
(c) (d) plot the distribution of digit in visual panels, revealing a long-tail distribution, where digit 'I' has an occurrence number over 4,000, and digit '9' has an occurrence number less than 100. We consider this design as a nature of HALMA training set. Note that a greater digit tends to co-occur with the lesser digits in HALMA. For instance, if the agent passes 9-grid-long passage step-by-step in a maze, it would observe not only the digit '9, but also all the digits from 'I' to '8.' Additionally, since we uniformly add branches the optimal paths create crossings, it adds to
Fig, (c)
S8

---

Under review as a conference paper at ICLR 2021
the occurrence of lesser digits. In essence. this almost log-linear distribution aligns well with the natural distribution of digits or words for numbers in human language (Dehaene Mehler 1992).
D DYNAMICALLY GENERATE GENERALIZATION TESTS
test problem generation
KB construction
KB for semantics
KBg : (d1, (type)
external memory MEK: (8,S', a/opt)
KB for causality & affordance
testing set
KBave (ds, /opp, d2 type)
Figure S6: Illustration of the testing maze generation pipeline.
One of the unique features that HALMA possesses is its capability of pinpointing the model weak- nesses by dynamically generating informative and definitive generalization tests according to agents' experience. During training, we save the running experience of the agent as its external memory MЕM, specifically a tuple, containing (i) pair of states s and s', and (ii) the action/option a/opt the agent takes in this transition. Based on this external memory MEM, we build pipeline that automatically generates the diagnostic testing that tests a range of generalization abilities.
Knowledge Base Construction As shown in Fig. S6 we first construct the Knowledge Base (KB) from the external memory MEM by converting the tuples to inequality hitmaps following these rules:
If a pair of red, orange, yellow, green digits (d1, d2) occur in the same panel, then they are considered represent the relation (d1, dpltype) that belongs to semantics inequality, where d, is the greater digit and d, the lesser one. Recall that the color mentioned above are connected with directions v, 4, and ,, respectively. In short, this KB is for (s, <).
If the digit colored red, orange, yellow, green changes in states and s', and if both digits are non-zero, then they are considered to represent the relation (dg, dly ttpe) that belongs affordance inequality and causality equality, where d, is the greater digit in s and s' and d2 the lesser one. In short, this KB for (A, +/-,<) (c,+/-.)).
If the digit colored red, orange, yellow, green appears in state and disappear in s', meaning that the agent consumes the distance the digit d represents, we consider the indication of that digit is revealed to the agent. We therefore consider that the relation (d,, da (type) that belongs to affordance inequality is explored. where d and d2 are digits understood through affordance, and d; is the greater digit and d2 the lesser one. short, this KB for (A, +/--=)
Test Problem Generation We pull inequality pairs from the constructed KB according to Sec- tion 3.4 to generate the testing mazes. Specifically, each inequality relation pair (d1, d2 yyee) contains pair of digits (d1, d2); we use the greater one as the distance till wall, and the lesser one as the distance till a crossing. Therefore, we are able to incorporate the concepts to the maze layout and use the generated maze set to test the agent abilities of generalization.
generalization test problems in HALMA are categorized into 3 dif- ferent groups, i.e., Semantic Test (ST), Affordance Test (AfT), and Analogy Test (AnT); there also some more specific tests within each of these groups. Below, we provide detailed, concrete, and illustrative examples for each test unit:
As mentioned in Section 3.4
ST-1: 1: We would like to know whether the agent can understand novel MNIST-digit-level combi- nations and make right decisions from those observations. Therefore, we pull inequality relation pairs that rarely co-occur in the external memory MEM and create ST-1 mazes based on these digit pairs For instance, if the agent observed combination {3, 5: 1, 7) during training, would
S9

---

Under review as a conference paper at ICLR 2021
like to test whether the agent can make right decisions given (3. 5. 4. 2). which is rarely or never observed during training, i.e., (3, 5, 4: 2) & MEM. To achieve this goal, we can create a maze segment, where there is crossing 3-grid away upwards and wall 5-grid away in the same direction to ensure that the visual panel includes (3, 5). We then add a wall 4-grid away downwards to include the 4, and set the goal state position 2-grid away downwards to include the
2. Finally, we can assemble this kind of maze segments to create the desired testing mazes. ST-2: We would like to know whether the agent can recognize novel digit attributes combinations. We focus on the novel combination of color and MNIST category in ST-2 mazes. For in- stance, if the agent observes (3, 1.35 5) during training, we would test whether the agent can take right actions given (3, 5), which should be never seen during training, i.e., (3, 5) $ MEM. We can create a maze segment, where there a crossing 3-grid away downwards and wall 5-grid away in the same direction to ensure that the visual panel includes (3, 5).
Aft-1: We would like to know whether the agent can understand the indication of MNIST digits through causal transitions in Aft-1. For instance. if the agent observed the in the visual panel, moved 2 steps to the left 4 : Q. and observed the 3, we would expect the agent to understand that 3 < 5 through this transition. We can directly pull this kind of inequality pairs from KBaye- Note that to create pure testing mazes for Aft-1, we need to ensure that there are neither direct ob- servations of the digit pair 3, 5) from visual panels, nor visual observations of (3, 5), (3, 5), or (3. 5) which would help to infer the inequality relation 3 < if the agent could recognize novel digit attributes combinations as in ST. In short, an inequality pair (d1, d2) is pulled from KBAvc to create the testing mazes for Aft-1, then we must have {d1, da> $ KB5. We can then similarly create a maze segment as in ST.
2ft-2: We would like to know whether the agent can understand the indication of MNIST digits through affordance in Aft-2. For instance, if the agent exploited the affordance of 5 with ( during training, we would expect it to understand these two digits. We can directly pull such inequality pairs from KB,, to create testing mazes for Aft-2. Note that the inequality pair (d1, d2) pulled from KB, should not be in KB, for the same reason as in A
+ 3 and exploited the affordance of 3 with
Aft-3 and Aft-4: We would like to know whether the agent can understand the indication of MNIST digits through transitions and affordance based on their understanding of the composition of visual attributes. For instance, if the agent's causality and affordance knowledge base KB included the inequality pair (3, 5) or {3, 5), we would test whether the agent can understand
(3, 5) Note that we need to ensure that 3, 5) not in the KBg-
AnT: Note that in ST and Aft, we only test the direct inequality relation between digits. Here, we test the agent's understanding of transitivity of inequality relations in AnT. We expect agents to acquire the understanding of transitivity with analogical reasoning. For instance, if the agent's s KBATTvTT included a analogical template ((3, 4).{+ 4, (3, 5}}, we would expect agents to learn analogical reasoning from this base case. If there was another pair of tuples < 6, 7), (7, 8) in KBACтиET, and further given that < 6, 8) was not in the KBArTWST, we would test the agent's
understanding of transitivity from the analogical template.
Recall that in HALMA, we use 10 MNIST categories to indicate the distance till a wall or the nearest crossing, from which extract the inequality relations and form the knowledge base. The number of inequality pairs is thus limited. Because the test units listed above are mutually exclusive, it is likely that some of the test problems may not be generated if the agent's experience, along with already generated tests, cover the full space of inequality. This explains the "_" in Table
S10

---

Under review as a conference paper at ICLR 2021
E
DETAILS OF MODELS
E.1 PYPEE-PARAMETERS OF TD3
Table S1: Hyper-paramcters of TD3
Hyper-parameters
Value
Optimizer
Adam Kingma & Ba 2014
Learning rate for actor Batch size of Adam
le4
128
1c-8
Discounting factor
0.95
Initial for e-greedy
0.1
Ending e for c-greedy
0.95
Decay steps for e-greedy
100,000
Policy update delay
5
Target update rate
0.995
Replay buffer size
10,000
E.2 ARCHITECTURE OF AGENTS
St
Encoder
Decoder
Action Decoder
at
X
ht
RNN
RNN
af
Figure S7: Architecture the actor model, where equal to max opt. len,
a
S2
Encoder
Decoder
he
Value Decoder
at
a
h; RNN
RNN
RNN
Figure Architecture of the critic model, where T equal to max max-opt..en.
The overall architectures of the actor and the critic model employed by our agents are illustrated in Fig. S7 and Fig. [S8 respectively. All agents share the same implementation of the action decoder and the value decoder, which allows them to work with action sequences, i.e., option. Note that the hidden vector h, in the actor is simply initialized decoder instead to condition its output Q value on the state input.
zero vector, and the critic uses the output of
The major difference among agents lies in the implementation of their inductive biases, iee. encoder and decoder. We provide a summary, along with some other hyperparemeters, in Table S2
S11

---

Under review as a conference paper at ICLR 2021
Table S2: Architectural parameters of evaluated agents
Agent
Architecture
Shared
Nonlinearity
ReLU
MLP Agent
Encoder
MLP with hidden units [128, 128]. None
Decoder
LSTM Agent
Encoder
MLP with hidden units [128, 128).
Decoder
LSTM with layer normalization (Ba et al. 2016) and hidden units [128).
Transformer Agent Encoder
A stack of four multi-head self-attention layers, with hidden units [128], four heads and layer normalization, followed by maximum pooing layer. Parameters are shared across all the attention layers (Zambaldi al. 2019). MLP with hidden units [128. 128].
Decoder
TST Agent Encoder
Identical to Transformer Agent.
Decoder
MLP with hidden units [128, 128], followed by LSTM with layer normalization (Ba et al. 2016) and hidden units [128].
CNN Agent
Encoder
CNN with kernel parameters [(3, 32, 6, 4), (32, 64, 6, 4), (64, 128, 7, 1)] (number of input filters, number of output filters, kernel size, and stride size by ordering).
Decoder
MLP with hidden units [128).
CNN+ TWWassffformmrr Agent Encoder
CNN with kernel parameters [(3, 32, 4, 4, 0), (32, 64, 4, 4, 0),
(64, 128, 3, 1)] (number of input filters, number of output filters, kernel size, stride size, and padding size by ordering); resized to 4 slots, concatenated with positional embedding (Appendix F.1); followed by the encoder of Transformer Agent. Identical to Transformer Agent.
Decoder
SPACE Agent Encoder
We adopt the original setup of SPACE Lin et al. 2020 for the image_encodee and the what We concatenate latent vectors for the shape (Zwhat) and the presence (Zwhere) of each object. In sum, there are 8 x object slots, each is a 33-D vector. They then fed to the encoder of Transformer Agent. Identical to Transformer Agent.
Decoder
S12

---

Under review as a conference paper at ICLR 2021
F EXPERIMENTAL DETAILS
F.1 TASK PARAMETERS AND EXPERIMENTAL PROTOCOL
Task parameters Task parameters for HALMA are mostly defined in Section 3.3 explicitly spec- ified for the formulation of rapid problem solving. Table S3 summarizes these parameters.
Table $3: Task parameters HALMA
Task parameters
Value
Maximum #steps in an episode (L)
500
Maximum #trials in an episode (N)
10
Maximum #steps in a trial(HF)
200
Discounting factor (?)
0.95
Goal reward (Rg)
100
Penalty on invalid action (R.))
-5
Penalty on invalid action (Ra)
-5
Auxiliary rewards (Rz)
1.0x (Im (agent,,,, goal)
- Lm (agent,, g where Lm is the Manhattan distance.
Given a set of generated HALMA problems, there is still one task parameter: max.opt.len, which the maximum length of option in one step. We tried three different setups, {1. 5]. Intuitively, when max_opt_len- though they may still need decide between [0,0. 2 E3 With that said, the exploration and planning efficiency Pp may be close to the optimal 1 as long as the ratio of goal reaching Pg is high. In contrast, when max_opt_ler the option space (i.e., the temporal grammar) to improve Pp. In this case, as shown in Appendix F.2 most agents find quite challenging to plan optimally. They may even get trouble in understanding affordance, hence have higher ratio of invalid moves Py than when max.opt_len-1
agents do not need to merge sub-options to improve planning efficiency,
3 or 5, agents would need to understand the compositionality of
Two types of observations We provide two types of observations the agents. One is low- dimensional symbolic observation space. It represents the ground-truth MNIST digits, colors, and shape of hint symbols at crossing. Recall that in HALMA, the observation may have most 10 MNIST digits plgs crossing hint, and the value of digit range from -9 to 9 12 which results in 10 one-hot vectors with an overall size of 11 19. For agents with permutation invariant modules (e.g., transformers). we enforce the positional sensitivity by augmenting each one-hot vector with an extra indexing vector of size 10, which is essentially another one-hot vector that indicates the index. In our experiments, we observe that this index encoding is crucial to all the transformer-
agents.
We also offer visual observation space, where the only observation is the visual panel of HALMA, as introduced in Sections 3.1 (.22 We downsample them to a RGB image with size (128, 128, 3) and re-scaled [0, 1]. Agents for this type of observations require visual modules, such as CNN or SPACE (Lin et al. 2020 as detailed in Appendix E.2
Training protocol We generated 100 mazes for training. An ablation study on the volume of training set can be found in Appendix G Each agent is trained for 2000 episodes under the task All of them converged the end of training, as illustrated in We tried 5 different seeds during training and report the best result. Note that different from classical reinforcement learning tasks, where there is no explicit split for training and testing hence training curves are reported for quantitative evaluation, we provide training curves merely for justifying the validity of our training.
formulation introduced in Section 3.3
their learning curves in Appendix F2
Testing protocol We test all agents in (i) the training problems, (ii) test problems generated by random split in the problem space, and (iii) test problems dynamically generated according Sec- tion 3.4 The former two are provided mainly for reference. Interestingly, most agents perform al- most equally well on these two, consistent with prior works (Guez et al.) 2019 Cobbe et al. 2019). For all tests or dynamically generated subtests, we test with 150 mazes and summarize over 3 dif- ferent seeds to calculate mean and standard deviation. A test is skipped if the dynamic generation fails, as introduced in Appendix D
"I for crossings, for distance to the walls, and the remainder, 2, for distance to the goal.
For the two goal digits only, while others only allowed to he in (0, 1, 2, 3, 4, 5, 6, 7, 8, 9): the hint only has 4 different values)
S13

---

Under review as a conference paper at ICLR 2021
F.2 LEARNING CURVES
To validate the convergence during training, we provide the learning curves of agents trained under different settings (mainly on the different choice of weexx.ot.eeeee number of finished trials and the ratio of invalid actions in each training episode. The moving average (with a window size of the number of mazes in the training set) of these two metrics can reflect Pg and Pa in training. These curves suggest that all agents with symbolic observations converge before 2000 episodes in terms the goal reaching rate and invalid action ratio. For the visual observation, however, agents struggles on both metries when the action space is large (max.opt.len- or max opt 1en=5). Their performances remain almost the same after 2000 episodes. Hence, we report the test results with opt len=1 in the main paper; full results can be found below.
to S11 We report the
Training 10, up to 2000 episodes, maximum option length
Invalid Actor Ratio (per-epison per-eplsode)
Finished Trials (per-episode]
9
8
0.5
7
0.4
6
0.3
5
0.2
500
1000
1500
2000
500
1000
1500
2000
Episodes
Episodes
Agent
Transformer Agent
CNN+MLP Agent
LSTM Agent
LSTM+Transfomme Agent
CNN+ Transfrmee Agent
Figure $9: Learning curves the evaluated agents with ma max_opt__eem Training 10, up to 2000 episodes, maximum option length 3)
10
0.8
Invalid Actor Ratio (per-eplsode
Finished Trials (per-cut ver-episode)
0.7
8
0.6
7
0.5
0.4
6
0.3
5
0.2
0.1
0.0
500
1000
1500
2000
500
1000 Episodes
1500
2000
Episodes
MLP Agent LSTM Agent
Transformer Agent
CNN+MLP Agent
-STM*Trarsformer Agent
CNN+ Transfrrrf Agent
Figure S10: Learning curves of the evaluated agents with max.opt.
F.3 SPACE MODEL
Architecture and Hyperparemeters We adopt the original setup of SPACE (Lin et al., 2020) except for a simple modification the background encoder. Specifically, we replace their St.rongCompeccoder with their CompDecoder.
Reconstruction, Segmentation and Detection on Testing Set We train the SPACE model with all visual panels in the training set. To qualitatively evaluate the generalization capability of the SPACE model. we visualize their inference results in a hold-out testing set; is essentially a set visual panels from randomly generated test problems; see Fig. S12 for example. The SPACE model
S14

---

Under review as a conference paper at ICLR 2021
Training (N 10, to 2000 episodes, maximum option length
10
0.6
Invalid Actor Ratio (per-episode)
Finished Trials (per (er-episode)
0.5
8
0.4
7
0.3
0.2
5
0.1
2000
Episodes
Episodes
MLP Agent
Transformer Agent
CNN+ MLP Agent
LSTM Agent
Transfrasorm Agent
CNN+ Transformrr Agent
Figure S11: Learning curves of the evaluated agents with max.opt.Len-1.
generalizes remarkably well terms of reconstruction, detection, and segmentation, consistent with the original results reported by (Lin al. 2020).
Investigating the Latent Space We further investigate the efficacy of the SPACE model disen- tangling independent latent factors from visual panels. Specifically, adopt standard methodol-
ogy in the unsupervised disentanglement learning literature (Higgins et al. 2017), linear probing.
We train linear SVM classifier using the latent representations of colored MNIST digits obtained from the encoder of the SPACE model. We observe that the output vector SPACE encoder have multiple slots representing the objects (digits) in the input image, and that the connection between slots and input objects is implicit. Hence, we calculate the IoU of predicted bounding box and ground-trutt bounding box assign each slot to an input object as its semantic label. In this work, there are 64 slots in the output vector and no more than 11 objects in the input image. Therefore, it is likely that several slots are assigned to the same object. We save for each object only the slot with the maximum IoU to remove redundancy in the data and obtain 8, 932 33-D latent vectors in total. We use 70% of these samples as training data and perform testing on the held-out 30% data by randomly splitting the latent vectors. We set the penalty parameter 'C' of SVM 10 in all experiments and use balanced sampling when training the classifier. SVM classifier is implemented with the scikit-learn package (Pedregosa et al. 2011).
Table $4: Accuracy color and MNIST category classification.
Task
color
MNIST category
Acc.
59.67
50.56 10.92
We the classification accuracy terms of color and MNIST category and report the overall accuracy in Table[S4] Each result is averaged over 10 random split of latent vectors. In addition, we provide the confusion matrix of these two attributes (Fig ST3) illustrate the categorical accuracy. Results in Fig- S13 (a) demonstrates that the SPACE model performs relatively well the first four colors, i.e., red, orange, yel ow, and green, while poorly on the rest. partly explains SPACE agents' high invalid move ratio Pa and low goal reaching ratio Pg in HALMA, i.e., agents cannot tell the correct direction. Results in Fig. [S3 (b) demonstrates that the SPACE model does not handle the long-tail distribution of digits, and partly explains SPACE agents' high invalid move ratio Pa and low efficiency ratio Pp in HALMA, iee, agents do not know "what is" in the first place.
G ADDITIONAL EXPERIMENTS
G. ABLATION STUDY ON THE VOLUME OF TRAINING SET
The thesis argument our work is that humanlike agents shall generalize their understanding under limited exposure the underlying concept spaces. To further investigate how the degree of expo-
S15

---

Under review as a conference paper at ICLR 2021
6
6
5
5
5
6
2
2
1
9
5
5
/
4
8
8
8
2
8
8
2
2
a
4
4
3
3
/
]
1
1
(a) Input
(b) Reconstruction
(c) Detection
(d) Segmentation
Figure S12: Visualization of SPACE's reconstruction, detection, and segmentation hold-out testing set.
sure would affect agents performance in HALMA, we first conduct ablations study with different numbers of training mazes. Specifically, we experiment with four setups of the maze quantity for agents to explore during training: 100, 300, 500, 1000 (results 100 training mazes are reused from the main experiment as it is default setting). Here only evaluate agents with symbolic in- put: MLP agents, LSTM agents, Transformer agents and Transformer+LSTT agents. We report the three measures Pa. Py and Pp with all the testing protocols (training problems, problems from ran- dom split in the problem space and dynamically -eiccallyygeeeattedd generated testing problems) in Fig, S14 Note that measures in dynamically- generated tests merged across subtests for better comparison.
The results read that, all agents could gain a performance boost with increased exposure during training. Specifically, there is significant promotion for the metric of goal reaching rate Pg in the
S16

---

Under review as a conference paper at ICLR 2021
Ytn: Drge. Red
91/32
.23-01
.02:20
00/02
22001
20.00
-2000
60:01
65.00
03:01
.01.00
0.6
00:20
06:00
14101
19/01
.0/00
0.6
12/00
10.00
34.00
D6 01
13002
LES 01
000.30
.22100
A3/02
69:02
22000
00003
22.00
221.0
0.4
0.5
True label
43:40
A1/20
True label
13:00
(4:0
66.02
66
34/02
49101
601
13:00
65:01
0.4
244.0
0X//3
13.03
0.3
Blue
132-2
01,03
63106
4700
10
42/
09:00
03.02
05.01
12/00 11/02
08.01
18.00
0.2
0.2
Prpl.
8
22.02
0.1
0.1
Wht.
00).90
11101
22022
80.02
23100
01203
621
40.00
05.00 25.03
15/00
10/06
11.01
Red Orge. Ylw. Gm. Cyan Blue Prpp.
Wht.
0.0
1
4
5
Predicted
Predicted label
(a)
(b)
Figure S13: Confusion matrix of linear classifier trained on latent representations from SPACE encoder. Confu-
sion matrix (a) color and (b) MNIST category measured and averaged 10 random split testing set. Mean value standard deviation the accuracy are displayed in matrix.
training, Po
training, Po
training, Po
100
100
100
Value of Mesures
75
75
50
50
50
25
25
25
100
300
500
1000
100
300
500
1000
100
300
500
1000
testing (random), A
testing (random), Pg
testing (random), Pp
100
100
100
Value of Mesures
75
75
75
50
25
25
25
0
0
100
300
500
1000
100
300
500
1000
100
300
500
1000
testing (dynamic), Ps
testing (dynamic), Pg
testing (dynamic), Po
100
Value of Mesures
75
75
75
50
50
50
25
25
100
500 300
1000
100
300
500
1000
100
300
500
1000
Number of Mazes
Number of Mazes
Number of Mazes
MLP Agent
LSTM Agent
Transformer Agent
Transformer+LSTM Agent
Figure $14: Ablation study of different number of training mazes.
challenging dynamic testing (from 30-60% 80%). More interestingly, starting from 300 training mazes, the distinction between different inductive biases vanishes. While the efficiency ratio could also benefit from increased exposure, it reaches only around 50% at best. As for the ratio of invalid moves Pa. even though reaches around 10% in random split for stateless agent when trained with 1000 mazes, clear trend can be detected in dynamic testing overall, which may
S17

---

Under review as a conference paper at ICLR 2021
suggest agents' limitation in understanding affordance with the temporal grammar under the long-tail distribution of digits.
G.2 ABLATION STUDY ON THE MAXIMUM OPTION LENGTH MAX.CFI.LEN
Our design include the notion of option challenges agents' understanding in the temporal grammar and the causal structure. To further illustrate the difficulty of this specific challenge, we also perform an ablation study on three setups of maximum option length max-opt In general, agents' performance degrades on all metrics with max max_opt. len increases. In particular, the ratio of invalid moves Pa increases and the efficiency ratio Pp drops significantly since max opt len_ in dy- namic testing, suggesting that agents all have hard time understanding either the temporal grammar or the causal structure of HALMA. These results validate our argument that significant efforts are still in need for humanlike abstraction learning. Therefore, we choose to make the length of 5 as default setting in the main paper so as to make HALMA a more challenging territory. training, Pg
training, P.
training, Pp
100
100
100
Value of Mesures
75
75
75
50
50
50
25
25
0
5
1
3
5
testing (random), Pa
testing (random),
testing (random),
100
100
100
Value of Mesures
75
75
50
50
25
25
25
0
0
testing (dynamic), Pa
testing (dynamic), Pg
testing (dynamic), Pp
100
100
100
Value Mesures
75
75
75
50
50
50
25
0
0
1
3
5
1
3
5
action seq. length
action seq. length
action seq. length
MLP Agent
LSTM Agent
Transformer Agent
Transformer+LSTM Agent
Figure S15: Ablation study of different max-opt.lee (symbolic observations).
S18

---

Under review as a conference paper at ICLR 2021
training, Ps
training. Pg
training, Pr
100
100
100
Value of Mesures
75
75
75
50
25
25
0
0
1
3
5
1
3
5
testing (random), Pa
testing (random), Pg
testing (random), Pp
100
100
Value of Mesures
75
75
75
50
50
50
25
25
25
0
3
1
testing (dynamic),
testing (dynamic), Pg
testing (dynamic), Pe
100
100
100
Value of Mesures
75
50
25
25
25
0
0
5
3
5
action seq. length
action seq, length
action seq, length
CNN +MLP Agent
Crn+ Agent
SPACE Agent
Figure $16: Ablation study of different max.opt_len (visual observations).
S19


Reviews:
[{"review_id": "tR_0QATSCCd", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "---Post rebuttal---\n\nThank you for the detailed response. Overall, I think the proposed work provides a valuable benchmark for testing generalization ability of RL agents. However, I agree with R3 regarding the writing being dense/difficult to follow. I keep my rating unchanged (Weak Accept).\n\n----\n\nThis work proposes a benchmark for evaluating the task-solving capabilities of agents on three levels: perceptual, conceptual, and algorithmic. The tasks are procedurally-generated contextual 2D gridworld environments.\n\nI believe there is a lack of RL benchmarks on evaluating the agent’s understanding of object affordances, so this is a useful benchmark for the RL community.\n\nClarity: The paper is well-written and well-motivated.\n\nSuggestions:\n\n1. The paper provides empirical evaluations of TD3 with various encoder/decoder architectures. However, there does not seem to be evaluations of model-based/planning methods, despite the task requiring planning & reasoning. I think the comparison of model-free vs. model-based on this benchmark would be valuable.\n\n2. For future work, I think it would be valuable to add continuous control to the benchmark tasks for more “humanlike abstraction learning”. For example, use locomotion actions instead of gridworld actions; or a robotic arm learning to play a logical puzzle game.\n\n3. The related works section (Appendix H) can also add prior work on visual semantic navigation, which connects visual and semantic understanding with control:\n[1] VIsual Semantic Navigation using Scene Priors https://arxiv.org/pdf/1810.06543.pdf\n[2] Embodied Multimodal Multitask Learning https://arxiv.org/pdf/1902.01385.pdf\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "smGYZL1Mvl", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Disclaimer: Apologies I have very little background in the area of this paper and should have probably opted out. However I did read the text twice with interest. \n\nThe authors propose a task HALMA which involves a grid-world maze that is partially observed, and includes visual panels that contain conceptual reasoning tasks which the agent must solve to find an optimal path. The aim of this environment is to test three proposed 'levels of generalisation': 'perceptual', 'conceptual' and 'algorithmic'. The authors propose several tests for generalisation: 'semantic', 'affordance', 'analogy'. The authors propose a dynamic manner of evaluating the agents by showing them problems that they appear to not yet have demonstrably understood. The authors conclude that existing agents are woefully inadequate at these generalisation tests and invite researchers to approach this novel task. \n\nI found the paper had an enjoyable positive style of discourse and built up the problem area quite nicely in the introduction, but was unfortunately very verbose and many important details were relegated to the appendix. For example the actual algorithm used to dynamically produce test-set elements was relegated to Appendix D --- however this seemed to be one of the central contributions to the paper. Furthermore the environment of HALMA was not very succinctly described. Possibly this paper has too much information for a conference submission and should fit better in a journal, otherwise it should be edited down to make room for a succinct description of the environment, and the evaluation approaches *in the main text*.\n\nI was curious to what effect many of the research findings depended on the arbitrary size of the training set; and would have been interested to see some generalisation metrics reported as a function of training set size (100 mazes seems very small). I would have also liked to see a human baseline and then to have had human-normalised scores.", "extra_scores": {}, "extra_text": {}}, {"review_id": "jS9tykHuQj1", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\nSummary\n---\n\nChildren generalize to new sights that combine known perceptual elements.\nChildren generalize to new instances of known abstract concepts like order and number.\nChildren know what actions they can take in new scenarios, because those actions have been available in similar contexts.\nMachines should be able to generalize in the same ways.\n\nThis paper proposes a new environment, HAMLA, where machines are tested on their\nability to generalize in all of these ways.\nAgents navigate through a maze to a goal location using only carefully designed\nsignals extracted from carefully constructed mazes.\nThey must learn perception (MNIST digits, color, location), abstract concepts\n(number, order), affordances (move up/down/left/right as available), and\nefficient exploration strategies at once, like humans seem to be able to.\n\nEvaluation is dynamic, estimating what an agent already knows then generating\nnew test instances that test the model on something slightly outside what it knows.\nThere is no static test set or test environment.\n\nTD3 is used to train various agents based on different NN architectures\nthat incorporate more or less structure.\nAgents often fail to navigate to the goal and do so efficiently in scenarios basically similar to those it was successful at.\nFailure happens more often as the generalization gap becomes larger and when the agents must also learn perception in addition to concepts and exploration.\n\n\nStrengths\n---\n\nThe motivation is ambitious, interesting, and relevant. It makes sense. It pulls strongly from cognitive science. Explicitly attacking multiple specific modes of generalization at once is an interesting direction.\n\nThis could establish a new baseline task that tests multiple kinds of generalization in a toy manner.\n\nThe dynamically generated evaluation strategy is new and interesting. It may make it harder to compare performance across models, but clearer about how well a single model is actually performing. That could inspire a significant shift in evaluation methodology.\n\nThe paper is highly sylized and polished.\n\n\nWeaknesses\n---\n\n1) The paper is hard to understand in just 8 pages.\n\nThe writing is so dense and so many details are left to the 20 page appendix that it is hard to understand the approach or experiments at more than a very high level by reading just the main 8 pages of the paper.\n\nThe main example here is the notation. Much of it is non-standard. It is also used frequently and most definitions are left for the appendix.\n\n\n2) Novelty relative to some related work isn't clear.\n\nHow does this compare to point-goal nav? [1] I think the test procedure and available senses make it different, but it's still fundamentally navigating to a goal location. Will scaling training help solve this problem as evaluated by the proposed metric?\n\n[1]: Wijmans, Erik et al. “DD-PPO: Learning Near-Perfect PointGoal Navigators from 2.5 Billion Frames.” ICLR (2020).\n\n\n3) Impact may be limited by difficulty. Tackling this whole problem may be too difficult right now. All approaches completely fail to solve the full problem including vision, as indicated by the bottom right of table 1, which is filled with 0s. If progress is limited to the symbolic setting then the problem is significantly less interesting.\n\n\nPreliminary Evaluation\n---\n\nAt the moment the paper is not very clear. That makes it hard to evaluate the quality of the experiments. The quality and novelty of the motivation is high, being fairly novel and interesting. Its significance is highly uncertain because of the paper's clarity and potential difficulty. The paper might be significant as either 1) a central reference for applying some cognitive science concepts to AI, 2) a benchmark that spurs new agent designs, or 3) inspiration for designing new evaluation metrics.\n\nMy main uncertainty in this evaluation is because I haven't understood the paper in its full 30 pages of depth.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "1hXNtUrhPzQ", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "##########################################################################\n\nSummary:\n\nThe paper introduces a new benchmark which measures agent reasoning abilities and their generalization of 3 kinds: perceptual, conceptual and algorithmic. The paper extensively motivates this benchmark and shows experiments with training RL agents on it. \n\n\n\n##########################################################################\n\nReasons for score:\n\nNew benchmarks for measuring intelligence are important for driving the field. This one seems interesting.\n\n\n##########################################################################\n\nPros:\n\n1. New benchmark which tries to provide a comprehensive measure of generalization, which is a very important topic.\n2. Paper is nicely written and illustrated - pleasure to read!\n3. Benchmark/code will be published upon acceptance, so the whole community will be able to profit from it.\n\n##########################################################################\n\nCons:\n\n1. The history of artificial domains as AGI playgrounds has taught us a few bitter lessons. To give one very recent example, the winner of Abstraction and Reasoning Challenge (yeah, that one proposed by Francois Chollet to measure general intelligence https://arxiv.org/abs/1911.01547) wrote \"Unfortunately, I don't feel like my solution itself brings us closer to AGI.\" https://www.kaggle.com/c/abstraction-and-reasoning-challenge/discussion/154597. The solution was some handcrafted search algorithm, no machine learning. To be fair, the challenge is very far from being solved - and yet the winning solution from 914 teams didn't teach us much. Is there anything in the design of HALMA which we expect will protect it from similar problems?\n\n2. No human baselines are given. How do we know that our agents achieved human performance?\n\n##########################################################################\n\nQuestions during rebuttal period: \n\nI would be curious to know the authors' opinion on Cons above.\n\n#########################################################################\n\nMinor suggestions and typos: \n\n(1) affordnace -> affordance", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a new task domain for learning-based AI agents, HALMA, a game that is designed to bring together multiple areas of research in AI. Perception, in the form of recognition of MNIST digits, learning mathematics - in the form of arithmetic operations on the natural numbers, and navigation and planning. When combined into a game, these elements are argued to require various important properties of human cognition, such as abstraction, analogy and affordance. 

I commend the ambitious goals of this work, and its multidisciplinary motivations. I believe the benchmark can indeed eventually be an important challenge for the community. I think that the dynamic testing aspect is particularly interesting, where the environment produces trials designed to go beyond the agent's experience to that point. However, having considered the views of the reviewers and read the (main body) paper entirely myself, I unfortunately cannot recommend acceptance in its current form. 

The main reason for the decision is simply that it is prohibitively challenging for me to grasp exactly how the game actually works after a thorough reading and considerable thought. The authors spend two pages motivating the approach with (arguably excessively grandiose) allusions to Marr's levels of analysis, Gibson's affordances, Holyoak's analogy and various other famous works from the history of AI and philosophy of mind; as well as to the board game HALMA. But as a reader I can't myself start to make any of these connections because the game proposed by the authors has not been explained to me! It is finally introduced on the fourth page - with reference to Figure 2 which is too small to consult and very hard to interpret. After consulting the appendix (where the idea is a bit clearer) I was able to decipher the way in which the numbers related to the maze itself, but was (and am still) unclear on the actions available to the agent. These are explained as follows: 

""The direction set is t , , , u. The primitive action set, in terms of the numberof moves, is t , , , u; this design of primitive numbers with a maximum of three aligns withthe doctrine of core knowledge in developmental psychology (Feigenson & Carey, 2003; Dehaene,2011). If an option is selected, consecutive hops as in Halma are simulated; all observations fromintermediate states will be skipped, and only the observation of the final state is provided. A movewould fail if a wall stops the agent, leaving the agent’s position unchanged; failure moves bringpenalties to the agent. The agent would receive a positive reward when reaching the goal""

From reading this I am left with the following questions: 
- Are directions primitive actions? 
- How can a primitive action also be a number of moves? 
- What does it mean to select an option? 
- Can I select an option and an action at the same timestep? 

Most importantly, I still don't really know how the game works. 

This example is intended to illustrate the difficulty faced by readers of this paper in general.  

I note that the reviewers awarded this work scores that place it on the borderline for acceptance, but with consistently low confidence. On consulting with the reviewers it is clear that this is not because they lack expertise but because they too did not understand the full details of how this domain/task works. This is also clear from the lack of detail in their reviews; only reviewer 3 engaged with any of the details of the task itself. 

To summarise, I think there is potentially a very interesting and important contribution in this dataset. However, the work will only have impact in the community if it can be understood and adopted after a single read of the paper. I therefore recommend that the authors resubmit this work to a different venue taking account of the following: 

- Explain how the game works *then* connect it to the literature on human learning *not* vice versa (from the concrete to the abstract)
- Be very concrete, perhaps guide the reader through a single particular episode explaining the observations available to the agent and the options open to it at each important point-
 Get to the point of your contribution. Tenuous connections to cogsci etc can go in the discussion
- Make all diagrams and illustrations extremely simple to interpret and large enough to easily read
- Avoid use of subjective adjectives, and particularly describing one's own contributions as "ingenious solutions" and "impeccable"
- Avoid rhetorical flourishes and latin
- Submission to a journal may allow the authors greater space to draw the desired connections to disparate fields without compromising on readability or exposition of their methods
Decision: Reject