Reconciling Spatial and Temporal Abstractions for Goal Representation

Response (part 1)

Thank you for your thorough review and questions to understand our work. Here, we answer your questions about (1) the approach’s practicality, (2) the missing algorithm’s details, and (3) the understanding of the theoretical results. We will modify our pdf to incorporate these responses to our paper. ## 1. Practicality: > How do you estimate the reachability for all states…? The reachability computation has two steps. *(A)* We approximate the k-steps reachability relation for a continuous state space with a neural network model $\mathcal{F}_k(s_t,G_d)$, called forward model (see Sec. 3.2). $\mathcal{F}_k (s_t, G_d)$ predicts the state the agent would reach in k steps starting from a state $s_t$ when applying the low level policy conditioned on the goal $G_d$ (i.e., the abstract state we want to reach). In practice, $\mathcal{F}_k$ is capable of generalizing the reachability relation to unvisited states. We train $\mathcal{F}_k$ from past explorations at the end of each episode (see Line 26 of Algorithm 1, Sec. E and Sec. D.3). *(B)* We use the set-based reachability analysis algorithm Ai2 (T. Gehr et al., "AI2: Safety and Robustness Certification of Neural Networks with Abstract Interpretation," SP 2018 and Liu et al., 2021) on the neural network $\mathcal{F}_k$ to compute the set of states that $G_i$ can reach applying $\mathcal{F}_k$ with $G_j$ (i.e., the set $\mathcal{R} := {s’ \mid \mathcal{F}_k(s, G_j), s \in G_i}$). Such an algorithm works on continuous states via efficient **set-based operation** (i.e., all the computations are done on sets and not on single states). We then check if $R \cap G_j^C = \emptyset$ to check the reachability property from Definition 1. > What is the computational cost of refining the abstractions? The computational cost of the reachability analysis is negligible. We are measuring execution time on a NVIDIA RTX A5500 GPU powered computer to compare the time costs of the different environments. We are continuing to run measures of these execution times and will report in a few days the time costs over a whole run of each algorithm. Over 3M steps, the refinement operation (which includes the reachability analysis) takes on average 0.361s (variance 0.072, maximum 0.80s) for an oracle of 2 variables, 0.423s for 3 variables (variance 0.026, maximum 0.944s), 0.429s for 5 variables (variance 0.053, maximum 1.637). Compared to other reachability based methods (HRAC) our reachability approximation is much less costly and scalable to more variables. Running HRAC over 3M steps, we observed that the reachability relation learning step takes an increasing duration. Our measures average for the last 100 calls at 49.27s (variance:15.468 and maximum:52.206s) for 2 variables, 85.140s (variance: 12.667 max:89.940s) for 3 vars, and to 902.373s for 5 variables (the execution time continues to grow exponentially in this setting). A key difference is that the reachability relations are approximated over sets of states in STAR and not single states as in HRAC. HRAC stores all pairs of visited states in a transition matrix which is then used to repeatedly train a neural network predicting if a state reaches another. This creates a large memory constraint. The objective function of this model has to minimize the error of predicted relations compared to the transition matrix which becomes exponentially costly since it searches all the paths encoded in the matrix, which grows with more visited states (the size of the matrix increases, and the matrix is less sparse with added transition relations). On the other hand training the forward model in STAR is straightforward and uses an MSE loss to predict reached states from the replay buffer, and neural network reachability analysis extends the computation of the forward model to predict reached sets of states. > How are the abstractions represented? In our implementation each abstract state is a hyperrectangle (i.e., a multi-dimensional interval) and the abstraction is a partition of the state space that we represent with a set of *disjoint* hyperrectangles. We could substitute hyperrectangles with different abstract domains to gain precision (which we did not need), as long as the abstract states are disjoint. > Are there any implicit properties of the abstraction …? We try to learn a reachability-aware abstraction (Definition 3).

Response (part 2)

## 2. Algorithm details: > Why is the Navigator useful … as you show in the experiments. The 3-layer architecture with the Navigator, Manager, and Controller is key for performance and one of our main contributions. The Navigator learns a policy, via RL and planning, that decides what is the next *abstract state* to explore from the current state to fulfill a task. Since abstract states are finite and discrete (i.e., a *spatial abstraction*), the Navigator can solve a long-horizon task. What is difficult is to have an abstraction that “respects the lower agents dynamics”, so that the low-level policies (the Manager and Controller) manage to reach a goal $G_j$ from $G_i$. This is why we learn a reachability-aware abstraction. While having an abstraction with **fewer states** is desirable for easier planning for long-horizon tasks, the abstractions need to be detailed enough to represent the properties of the environment and the task, thus finding the right granularity is key. For example, in Ant Maze Fall the Navigator does not need a fine-grained subdivision of the states in the pit, but only the abstraction helping to cross the pit in correspondence with the block (see Figure 4 b). Similarly, in Ant Maze Cam having a fine-grained representation of the orientation angles most useful close to the camera position. Without the Navigator, our algorithm would not perform a spatial abstraction (similarly to HIRO). Figure 3 shows the practical advantages of our architecture: temporal abstraction (HIRO) and spatial abstraction (GARA) alone do not scale when increasing the dimensions *of the oracle*. Theoretically, Theorem 1 proves sub-optimality when using the reachability-aware abstraction. > … introducing the Manager you lose the abstraction of the Navigator. Can you instead … sample a few subgoals and … aggregate the low-level policy …? The Manager does not lose the abstraction but instead samples *a sequence of subgoals* that eventually reaches a target abstract state, acting as an intelligent tutoring system setting realistic goals for the controller (the Manager’s reward measures the success in reaching the abstract goal, see next answer). If we understand correctly, the question asks if the Manager can sample multiple subgoals (i.e., a breadth-first exploration). We think this strategy, differently from our implementation, will explore “closer” states first but will struggle to learn to reach a different abstract state. > Why are the proposed rewards sound? … they look quite arbitrary. We designed the rewards following the common intuition from goal-conditioned HRL algorithms: the highest-level agent in the hierarchy is rewarded when it accomplishes the task goal. Each lower-level agent is rewarded for achieving the subgoal set by its higher-level agent. The Navigator’s reward measures the negative distance from the task goal: the higher the reward, the closer is the agent to the task goal. The Manager’s reward measures the negative distance of the agent from the goal set by the Navigator. However, the goal in this case is a set of states (and not a single state). Thus we need to compute the distance between a point and a set. In practice, instead of computing the exact distance to a set which can be costly, we experimented with different distances (e.g., the minimum distance from a point in the set, the distance from the center of the set). We converged, after some experiments, on the distance from the center of the set. The Controller’s reward measures the negative distance from the subgoal state picked by the Manager, in line with the lower-level agent’s reward in HIRO, HRAC, …. > How do you handle the initial stage … before becoming capable of acting? You are correct, we cannot refine the abstraction using the forward model in the initial stages and, in general, before the low-level policies (Manager and Controller) are “stable”. In fact, we refine the abstraction *only* when the forward model approximates the reachability relation induced by the low-level policies “well enough”, and continue with the low-level policies training otherwise. In practice, we test if the forward model predicts well the reachability relation of the latest episodes (i.e., the Mean Squared Error on the prediction of the latest 10 episodes is lower than a threshold). When the test succeeds, the forward model approximates the reachability relation obtained executing the low-level policies. So, this test avoids arbitrary splittings of the goal space. We briefly explained this mechanism in Appendix D.4, but we will provide the above explanation in Section 3.2.

Response (part 3)

> Is the splitting operation … good abstraction? Currently, the splitting operation is the only operation on the abstract space. We are considering join operation for future works. Currently, we avoid too fine abstractions through the hyperparameter “Minimal volume ratio of a split”, as mentioned in Table 3 of Annex D4. Moreover, in practice, the goal of our hierarchical representation is to drastically reduce the size of the space (from a continuous thus uncountable state space, to a finite abstraction space) to orient better exploration. Thus, with respect to this idea, a “too fine” abstraction would not be good. ## 3. Theoretical results > Why does Theorem 2 make your method sound … you prove there exist some refinements, not necessarily the one you actually do in the algorithm … and why it is not trivial to construct such an abstraction …? Thank you, we see the ambiguity in the use of “there exists” in Theorem 2. A more precise statement of Theorem 2 is: “Given an initial set-based abstraction $\mathcal{N}$ and assuming $\mathcal{N}(g_m)$ satisfies the Conditions (1), (2), and (3) of Definition 3, we compute a reachability-aware abstraction after a finite number of **reachability-aware refinements**.” Theorem 2 proves that applying the reachability-aware refinement **we use in the algorithm** for a finite number of times we compute a reachability-aware abstraction. Your observation about the existence of a trivial refinement is correct: that refinement would halve the grid in each dimension so that, for example, in 2 dimensions we’ll have 1 cell initially, then 4 cells, then 16 cells, … (a uniform grid size that is reduced by epsilon may also work). However, the trivial refinement *is not what we use in the algorithm* and it’s not useful in practice, since it does not respect the dynamic of the lower-level policies! We clarify a misunderstanding on Theorem 1, Theorem 2, and Lemma 1. Theorem 1 is important on its own and proves that, if we have a reachability-aware abstraction, we learn a sub-optimal policy. So Theorem 1 **is not used to prove** Theorem 2. Then, Theorem 2 proves that the refinement computes the hypothesis of Theorem 1. We will improve Theorem 2 wording as above, integrate this discussion in Section 4, move Lemma 1 in the Appendix and explain Theorem 2’s proof informally.

Response to second message (part1)

Thank you for taking the time to read our response and understand our work. > … I understand how you propose to check the reachability… That is however hardly understandable from the paper. > (3) Providing at least a high-level idea of how the reachability is estimated. Simply stating that you use set-based operations is not enough (that's exactly what concerns me). > I would like to see here even a brief (say a paragraph) summary of Sections III and IV from Gehr et al. and how you instantiate it in your algorithm (at least that you use box representations; then, focusing only on boxes and forgetting polyhedra and zonotopes in summarizing AI2 is fine). We agree, our paper misses to explain the background on reachability analysis and how we instantiate it in our context. We will add a paragraph at the end of Section 3.1 explaining how we approximate the reachable sets using abstract interpretation with Ai2, which computes an over-approximation of the network’s output layer-by-layer using operations on an abstract domain. We remark that our paper *does not provide* a novel contribution for reachability analysis of neural networks, but instead uses off-the-shelf techniques. In fact, neural network reachability analysis is a known problem with multiple algorithms and tools available (e.g., see the (Verification of Neural Network competition)[https://sites.google.com/view/vnn2023] organized during CAV and AAAI). > In fact, what you do (I think) is more approximating the bounding boxes of the output sets by consecutively bounding the sets after each operation performed by the network (right?). Yes! Your understanding about over-approximating the neural network outputs is correct. > I suggest (1) analyzing how reliable is $F_k$ (I suppose it's not perfect, so how accurate it is? How deep, since you have to balance its reliability and the overhead of AI2-related bounding boxes? ) In the algorithm, we try to train a precise $\mathcal{F}_k$: we use $\mathcal{F}_k$ in the reachability analysis only when it accurately approximates the data we observed so far (see last answer from (our second response)[https://openreview.net/forum?id=odY3PkI5VB&noteId=uoi64FiwJ0]). Yes, there are tradeoffs between the size of the $\mathcal{F}_k$ model (see Appendix D.3), its precision, and the overhead of running reachability analysis. The architecture of $\mathcal{F}_k$ is a hyperparameter that we decided via hyper parametrization on the Ant Maze environment. > how do you perform the splitting operation, We will add a high-level description of the splitting at the end of Section 3.1, and a more in depth description of the procedure in the Appendix. The input to the refinement is a sequence of visited abstract goals $G_0, \ldots, G_n$. For each pair $G_i, G_j$ in the sequence, the refinement computes a subset $G_\text{split}$ of states in $G_i$. Each state $s \in G_\text{split}$ is such that $\mathcal{F}_k(s, G_j) \in G_j$, and each state $s \in G_{\text{split}}^C$ ($G_\text{split}$’s complement) will not reach $G_j$. Then, the refinement removes $G_i$ from the abstraction, adding $G_{\text{split}}$ and $G_{\text{split}}^C$. In practice, since we use intervals, which are convex, we find *a set of subsets* $\mathcal{G}_{\text{reach}}$ of $G_i$ that contains states that reach $G_j$. We use the same splitting mechanism from (Shiqi Wang, Kexin Pei, Justin Whitehouse, Junfeng Yang, Suman Jana. Formal Security Analysis of Neural Networks using Symbolic Intervals. USENIX Security Symposium 2018) and GARA (Zadem et al., 2023). At the high level, the algorithm recursively splits a set $G_s$ (initially, it is $G_i$) to find such subsets by: 1.Computing the over-approximation $G_R$ of the states reachable from $G_s$ using Ai2. 2.Checking if $G_R \subseteq G_j$ to see if $G_s$ should be part of $\mathcal{G}_\text{reach}$. If it is the case, $G_R$ satisfies the reachability property (Definition 1) and is added to $\mathcal{G}_\text{reach}$. 3.Otherwise, checking if $G_R \subseteq G_j$ is empty. In that case, the algorithm stops. 4.Otherwise, the algorithm splits $G_s$ in two, along one of the interval dimensions (with the highest sensibility on the output, measured via its gradient) , and recursively applies the same procedure to each one of the two new sets. In practice, during step 2 and 3 we do not check exactly that $G_R \subseteq G_j$ but instead use an approximation: we compute the ratio $\frac{\text{volume}(G_R \cap G_j)}{\text{volume}(G_j)}$, and if that is smaller than a threshold (the hyperparameter $\tau1$ we show in Table 3) we add the set to $\mathcal{G}_\text{reach}$. This translates to checking if most of $G_R$ is inside $G_j$.

Response to second message (part 2)

> how do you schedule the refinements > How do you handle the moving targets issue, as the low-level policy constantly changes? We answer this question in (this)[https://openreview.net/forum?id=odY3PkI5VB&noteId=rRpjSVPgLh] recent answer to reviewer ep9K, which clarifies how the refinement copes with * High-variance during training*. > how do you train the models until you get the first successful episode. We describe the “Abstract state initialization” heuristic we use in (this)[https://openreview.net/forum?id=odY3PkI5VB&noteId=rRpjSVPgLh] recent answer to reviewer ep9K. Note we don’t need to get a successful episode (i.e., reaching the task goal $g^*$) to refine the abstraction, but we need to train a “stable” forward model $\mathcal{F}_K$. Although you refer to optimal trajectories in the theorems, I believe that using sub-optimal ones can be fine in practice. However, I'm not sure what you do before the first solution is found. Now, when I understand approximating the reachability, the practicality is no longer a strong issue. > … I suggest comparing the performance of your approach with "Learning Multi-Level Hierarchies with Hindsight" in the future … related concepts Yes, thank you for this suggestion. For this work, we decided to compare with HRAC since it captures similar state-wise reachability relations (albeit more efficiently) to Levy et al. 2019 to drive the learning. We will consider adding this in our future comparisons. > Please clarify the Lemma 1. I suppose it states that after refinement the new abstraction satisfies one more reachability constraint. Thank you for reading Lemma 1 carefully! Yes, your intuition on the Lemma is correct. When answering your questions we realized that the statements of Lemma 1 and Theorem 2 had a typo in the required pre-conditions on $\mathcal{N}$ (in one of our later paper revision we refactored Definition 3 - reachability-aware abstraction - but we did not correctly update Lemma 1 and Theorem 2). Instead of `satisfies the Conditions (1), (2), and (3) (but not (4)) of a reachability-aware abstraction (Definition 3)`, the Lemma just needs condition (1) and (4) from Definition 3 (and the other condition we state that $\mathcal{N}’$ is a reachability-aware refinement of $\mathcal{N}$). Requiring Conditions (2) and (3) is too strong and is not needed in the Lemma’s proof (which instead requires (4)). We apologize for the oversight, we updated the paper’s pdf applying the correct fixes (you can see the old text is strikeout and the diff from our previous version is colored in blue). > What does point (2) say? Why $g_i=g_j$ never works? Point 2 in Definition 3 implies that in a reachability-aware abstraction, all optimal goals should belong to disjoint abstract sets. This property plays a critical role in proving the regret bound for the policy in Theorem 1. Intuitively, it results in the optimal high level policy $\pi_{\mathcal{N}_{High}}$ having a trajectory that visits the abstract sets containing g_0, g_1, … which correspond to neighborhoods around these points (where there is a bound on the reward). Point 2 in Lemma 1 specifies that the new abstraction separates at least two optimal subgoals $g_i, g_j \in \mathcal{T}_{\text{high}}^*$ (concrete states) into disjoint new abstract states, satisfying property 2 in Definition 3 in one more pair. > Also, could you comment whether it is true that after refinement we do get one more reachable pair, but at the same time another pair may become non-reachable (e.g. right before the splitted set)? Yes that is correct and only possible for incoming reachability relations to the split abstract goal. In such cases the algorithm simply re-examines the modified relations in the later episodes and refines if necessary.

Response (part1)

We thank you for the insightful review and all the feedback on our work. In the following, we first clarify some points from the weaknesses section, and then answer your questions. We will modify our pdf to incorporate these clarifications. ## Clarifications > The results have been plotted only for 5 runs … not enough… We agree the confidence in our results could increase with more runs. We’re running more experiments and plan to obtain about 8 runs before the discussion ends for AntMaze (STAR, HIRO, HRAC algorithms) and AntMazeCam (STAR, HIRO algorithms) and then update the pdf accordingly (runs are computationally expensive *for all the algorithms*). We will collect up to 10 runs for all the environments and algorithms before the paper acceptance deadline (both the HIRO and LESSONS algorithms provide an evaluation with 10 runs). > … what a "Complex" continuous control task means. How to measure the complexity? … affected by distribution changes …? Indeed, task complexity is an ill-defined notion and no consensus has been reached on a single measure of task complexity, as there are many orthogonals measures to be considered. In our case, the complexity is linked to (1) scaling up the dimensionality of the state and action spaces and, in particular, the dimension of the oracle state space, as we show that we scale to 5 dimensions, compared to 2 in the SOTA; (2) the sparse reward function which translates the idea of a long-horizon task. We do not explicitly consider distribution changes. > It seems important to have a deterministic environment. … adjust to the stochasticity … with some tricks. STAR does not have a specific mechanism to cope with stochasticity. *We share* the deterministic environment assumption with HIRO and LESSONS. Only HRAC showed to be robust to small perturbations in the environment, which is a limited form of stochasticity. We hypothesize STAR’s abstraction to be also robust to small perturbations, since they would not drastically change the reachability relation among goals. However, we think STAR’s abstraction and reachability analysis should be extended (e.g., to quantify the environment uncertainty) to handle stochastic environments. ## Answers to direct questions > 1. In section 3.1, … Is not '~' used to show sampling from a distribution …? > I think there are two types of policies based on the way you are using them in this paper…. > 6. … how come that both actions and goals are sampled from policies? We thank you for highlighting the imprecision with respect to the use of '~'; we improperly used it to show sampling from a policy, be it stochastic or deterministic. We clarify the input and output of each of the goal-conditioned policies in STAR: $\pi_{Nav}: \mathcal{S} \times \mathcal{S} \rightarrow \mathcal{G}$. This policy takes a state $s_t$, and a task goal $g^*$ and outputs an abstract goal $G_{t+k}$. $\pi_{Man}: \mathcal{S} \times \mathcal{G} \rightarrow \mathcal{S}$. This policy takes a state $s_t$, and an abstract goal $G_{t+k}$ and outputs a subgoal $g_{t+l}$. $\pi_{Cont}: \mathcal{S} \times \mathcal{S} \rightarrow \mathcal{A}$. This policy takes a state $s_t$, and a subgoal $g_{t+l}$ and outputs an action $a_t$. Similarly we’d like to clarify the goal-conditioned policies used in the theoretical sections: $\pi^*_{high}: \mathcal{S} \times \mathcal{S} \rightarrow \mathcal{S}$. This policy takes a state $s_t$, and a task goal $g^*$ and outputs a concrete goal (state) $g_{t+k}$. $\pi^*_{low}: \mathcal{S} \times \mathcal{S} \rightarrow \mathcal{A}$. This policy takes a state $s_t$, and a subgoal $g_{t+k}$ and outputs an action $a_t$. $\pi^*_\mathcal{N, High}: \mathcal{S} \times \mathcal{S} \rightarrow \mathcal{G}$. This policy takes a state $s_t$, and a task goal $g^*$ and outputs an abstract goal $G_{t+k}$. $\pi^*_\mathcal{N, Low}: \mathcal{S} \times \mathcal{G} \rightarrow \mathcal{A}$. This policy takes a state $s_t$, and an abstract goal $G_{t+k}$ and outputs an action $a_t$. Such hierarchical policies that output goals of different levels of abstractions are standard in goal-conditioned HRL with a 2-level hierarchy (e.g., see HIRO, HRAC, LESSON). > 2. How is the composition of $\pi_{\text{Man}}$ and $\pi_{\text{Cont}}$ to generate $\pi_{\text{low}}$? Focusing on the composition of $\pi_{\text{Cont}}$ and $\pi_{\text{Man}}$ to generate a hierarchical policy $\pi_{\text{low}}$, we can write: $\pi_{\text{low}}(s_t, G_{k*[ t/k ])}) := \pi_{\text{Cont}}(s_t,\pi_{\text{Man}}(s_{l*[ t/l ]},G_{k*[ t/k ]}))$ where $[n]$ computes the floor of the number $n$.

Response (part 1)

We thank you for your careful review and insightful feedback, we will use that to improve the clarity of our paper. ## Clarifications > What are initially $\mathcal{G}$ and $G_t$ … > … action space … explained if it is in {\mathcal G} regarding the history or possible actions. $\mathcal{G}$ is *a partition* of the environment’s space $S$: that is, $\mathcal{G}$ is a set of states $\{G_1, \ldots, G_n\}$, where each $G \in \mathcal{G}$, $G \subseteq S$, all the subsets are disjoint (for any $i \neq j$, $G_i \cap G_j = \emptyset$ and the union of the subsets cover $S$, i.e., $\bigcap_{G \in \mathcal{G}} = S$). The Navigator policy $\pi_{Nav}$ takes as input the current environment state $s_t \in S$ and a task goal state $g^* \in S$ (this is the final environment’s state the agent should reach), and outputs a goal state $G \in \mathcal{G}$. So, the action space of the Navigator is also $\mathcal{G}$. In practice, we initialize the partition $\mathcal{G}$ as explained in the last answer in this [message](https://openreview.net/forum?id=odY3PkI5VB&noteId=uoi64FiwJ0) to reviewer ep9K. > clarify $R_{max}$ $R_{\text{max}}$ is the maximum distance between two states in the environment that are reachable in 1 step, and this value bounds the reward signals at each step. > Maybe I missed something, but I do not see how just assuming $\mathcal {N}(g_m)$, with the required conditions of Definition 3, cannot happen at a splitting point of a chosen $G_i$ that no state satisfies the reachability property. We do not understand this question completely, we’d be glad if you could provide more context. Here, we try to answer explaining what happens during a refinement. We have a sequence of abstract states $G_1, G_2, \ldots $ that we visited in the last episode. We check the reachability property between every $G_i, G_{i+1}$ in the sequence. If the reachability property does not hold, then we split the abstract state, otherwise not. If all the pair of states satisfy the reachability property, then we do not split the abstraction. Then, in Lemma 1, we show that if $\mathcal{N’}$ is a reachability-aware refinement of $\mathcal{N}$, then it contains a new abstract state $G_i$ that “separates” points from the optimal high-level trajectory. > In particular, what is $M$ in the last but one line on page 6? $M$ is the deterministic environment. > "The max in this reward is computed over observed exploration data", is not entirely clear, "observed" in which sense? The Navigator’s reward for $s_t \in G_{t+k}$ is the maximal reward obtained by any state visited inside $G_{t+k}$ during the past $k$ steps. Since the Navigator operates every $k$ steps, multiple (environment) states can be visited inside $G_{t+k}$ before the reward of the Navigator $r_{Navigator}$ is computed. > In Definition 2, after removing $G_i$ from $\mathcal{G_{\mathcal N}}$ and adding $G_1'$ and $G_2'$, why is it necessary to specify that $G_i$ is the union of the two after $G_i$ has been removed and since only $G_1'$ is chosen. This operation is motivated by our initial presentation of the abstraction as a **partition** of the state space $\mathcal{S}$. It is true that $G’_1$ is the one that reaches $G_j$, but $G’_2$ is not discarded as a potential abstract goal that can be explored by the agents (i.e., it is still part of the partition). > … how the exploration scales with the dimension of $S$ is not discussed … there is no discussion about the computational cost of the exploration given the state space partition. The exploration using the abstract state space is challenging in high-dimensional environments (i.e., it is difficult to explore an abstract state from another one). This is in fact the main issue of the GARA algorithm that we address in STAR by adding a temporal abstraction mechanism. > Figure 4 … I do not see that "progressively, the ant explores trajectories leading to the goal of the task … representation in Nachum et al. ICLR 2019 quite appealing. We see the representation from Figure 2 in (Nachum et al., ICLR 2019): we will provide a similar figure for the policy we learn after 3M timesteps. Note that Figure 2 in (Nachum et al., ICLR 2019) does not show how the abstract goal representation evolves during training.

Response (part 2)

## Answers to direct questions > 1. Have STAR been experimented on different tasks than the maze? > 4. Have STAR been experimented with larger scale space than the example given? No, STAR has been experimented on the different variants of the maze environment described in the experiments. > 2. What network is used to train $\mathcal{F}_K$? $\mathcal{F}_K$ is a connected neural network with (32 x 32) size (see appendix D.3, and Table 2 for the network’s hyperparameters). > 3. Why not compare with Nachum et Al. ICLR 2019? We agree, the comparison could be interesting. We think HIRO, HRAC, and LESSONS to be the most significant baselines for evaluating our research questions: they implement temporal abstraction with different goal representations (a subset of the environment’s state space, an embedding representing a reachability relation, and a latent space via slow features respectively). > 5. Can you estimate the trade-off between results and resources (e.g. memory usage, algorithm time cost, etc.) for STAR compared to the other methods? We are collecting the data for estimating the run times of the different algorithms and will report them in the pdf as soon as we have them.