Reconciling Spatial and Temporal Abstractions for Goal Representation
Authors: Mehdi Zadem
Sergio Mover
Sao Mai Nguyen
Venue: ICLR 2024 poster (2024)
Keywords: Hierarchical Reinforcement Learning
Goal Representation
Reachability Analysis
Primary area: reinforcement learning

Abstract: Goal representation affects the performance of Hierarchical Reinforcement Learn- ing (HRL) algorithms by decomposing the complex learning problem into easier subtasks. Recent studies show that representations that preserve temporally ab- stract environment dynamics are successful in solving difficult problems and pro- vide theoretical guarantees for optimality. These methods however cannot scale to tasks where environment dynamics increase in complexity i.e. the temporally abstract transition relations depend on larger number of variables. On the other hand, other efforts have tried to use spatial abstraction to mitigate the previous issues. Their limitations include scalability to high dimensional environments and dependency on prior knowledge.

In this paper, we propose a novel three-layer HRL algorithm that introduces, at different levels of the hierarchy, both a spatial and a temporal goal abstraction. We provide a theoretical study of the regret bounds of the learned policies. We evaluate the approach on complex continuous control tasks, demonstrating the effectiveness of spatial and temporal abstractions learned by this approach.

Published as a conference paper at ICLR 2024
RECONCILING SPATIAL AND TEMPORAL ABSTRAC- TIONS FOR GOAL REPRESENTATION
Mehdi Zadem', SSegio Mover Sao Mai Nguyen 3,4
LIX, École Polytechnique, Institut Polytechnique de Paris, France CCNSS, FFlowers Team, U2IS, ENSTA Paris, IP Paris 'IMT Atlantique, Lab-STICC, UMR CNRS 6285 http://.eeeeee....o.ooeeeeeeeeee nguyensmai @eaeiiiimmaaal.....m
{ (aadem, sergio mov.r) wtw../pppyttthiiuueeeeeee fr
ABSTRACT
Goal representation affects the performance of Hierarchical Reinforcement Learn- ing (HRL) algorithms by decomposing the complex learning problem into easier subtasks. Recent studies show that representations that preserve temporally ab- stract environment dynamics are successful in solving difficult problems and pro- vide theoretical guarantees for optimality. These methods however cannot scale to tasks where environment dynamics increase in complexity i.e. the temporally abstract transition relations depend on larger number of variables. On the other hand, other efforts have tried to use spatial abstraction to mitigate the previous issues. Their limitations include scalability to high dimensional environments and dependency prior knowledge.
In this paper, propose novel three-layer HRL algorithm that introduces, different levels of the hierarchy, both a spatial and a temporal goal abstraction. We provide a theoretical study of the regret bounds of the learned policies. We evaluate the approach on complex continuous control tasks, demonstrating the effectiveness of spatial and temporal abstractions learned by this approach.'
INTRODUCTION
Goal-conditioned Hierarchical Reinforcement Learning (HRL) (Dayan & Hinton, 1992) tackles task complexity by introducing a temporal abstraction over learned behaviours, effectively decomposing large and difficult task into several simpler subtasks. Recent works (Vezhnevets al.. 2017; Kulkarni et al., 2016; Nachum et al., 2019; Zhang et al., 2023; Li et al., 2021) have shown that learning abstract goal representations is key to proposing semantically meaningful subgoals and to solving more complex tasks. In particular, representations that capture environment dynamics over abstract temporal scale have been shown to provide interesting properties with regards to bounding the suboptimality of learned policies under abstract goal spaces (Nachum et al., 2019; Abel et al., 2020), as well efficiently handling continuous control problems.
However, temporal abstractions that capture aspects of the environment dynamics (Ghosh et al., 2019; Savinov al., 2019; Eysenbach al., 2019; Zhang et al., 2023; Li al., 2021) still cannot scale to environments where the pairwise state reachability relation is complex. For instance, Zhang al. (2023) compute k-reachability relation for subset of the environment's states defined with an oracle (e.g., the oracle selects only the x dimensions). While sampling reachable goals is useful to drive efficiency, the learned k-adjacency relation is difficult learn for higher dimensions. This situation typically happens when temporally abstract relations take into account more variables in the state space. The main limitation of these approaches is the lack of spatial abstraction to generalise such relations over states.
Alternatively, other works (Kulkarni et al., 2016; Illanes et al., 2020; Garnelo & Shanahan, 2019; Zadem et al., 2023) have studied various forms of spatial abstractions for goal spaces. These ab-
Find open-source code https//gghhaaaccmmooayssssiiiiis Sit.

---

Published as a conference paper at ICLR 2024
stractions effectively group states with similar roles in sets to construct discrete goal space. The advantage of such representation is a smaller size exploration space that expresses large and long- horizon tasks. In contrast to the algorithms that require varying levels of prior knowledge (Kulkarni et al., 2016; Ly et al., 2019; Illanes et al., 2020), GARA (7adem et al., 2023) gradually learns such spatial abstractions by considering reachability relations between sets of states. We refer to abstraction. While such representation is efficient for low-
this abstraction as reachability-awaan dimensional tasks, scalability remains an issue due the lack of temporal abstraction mechanism. What is challenging about scaling GARA's 's approach to more complex environments is exactly what makes the set-based representation effective: the low-level agent must learn how reach set of states that, especially in the initial phases of the algorithm when the abstraction is coarser, may be "far" away. We tackle this problem introducing new agent the hierarchy that introduces a fem- poral abstraction. Such an agent learns to select intermediate subgoals that: can be reached from state s executing the low-level agent; and helps constructing a trajectory from s to a goal abstract state.
In this paper, we propose a three-layer HRL algorithm that achieves both a temporal and spatial abstraction for capturing the environment dynamics. We motivate the use of temporal abstraction as the key factor that can scale the abstraction proposed in Zadem et al. (2023), and the reachability- way to efficiently represent goals in complex tasks. We complement
aware spatial abstraction the approach by adding theoretical guarantees on the bounds of suboptimality of policies learned under this abstraction. Our approach empirically evaluated on a of challenging continuous control tasks. Our work presents the following contributions:
(1) A novel Feudal HRL algorithm, STAR, to learn online subgoal representations and policies. STAR consists of 3 agents: the high-level agent selects regions in the abstract reachability- aware goal space, the middle-level agent selects concrete subgoals that help reaching abstract goals, and the low-level agent learns to take actions in the environment (Section 3).
(2) Provide theoretical motivation for using sachability-awan aware goal representations, showing suboptimality bound on the learned policy and that our algorithm progressively improves the reachability-awarr abstraction. (Section 4)
(3) Empirically show that STAR successfully combines both temporal and spatial abstraction for more efficient learning, and that the reachability-awar abstraction scales to tasks with more complex dynamics. (Section 5).
2 RELATED WORK
Building ideas for introducing hierarchy in Reinforcement Learning (Sutton et al., 1999; Barto Mahadevan, 2003; Dayan & Hinton, 1992), recent advances have managed to considerably el- evate HRL algorithms to tackle complex continuous control environments. Nachum et al. (2018) introduces a two-level hierarchy that sample goals from a pre-defined oracle on the state space. This approach provides good basis for HRL algorithms it is generic and addresses non-stationary learning but may still be suboptimal as the goal sampling is unconstrained in the oracle.
To remedy this, Ghosh et al. (2019); Savinov al. (2019); Eysenbach al. (2019): Zhang et al. (2023); Li et al. (2021) learn different goal representations that try to capture the environment dy- namies. This idea has been validated under different theoretical formulations (Nachum al., 2019; Abel et al., 2020; Li et al., 2021). In particular, Li et al. (2021) learns a latent representation based on slow-dynamics in the state space. The idea is that meaningful temporally abstract relations (over k steps) are expressed by state features that slowly change over time. However, these features may not be always sufficient to capture all the critical information about dynamics. Both Savinov et al. (2019) and Zhang et al. (2023) use k-step reachability relations ment dynamics. Their idea is to learn goals (mappings of states in an embedding / oracle) reach a potential goal in k steps. These relations are later used to drive the sampling of goals that can be reached, resulting in more efficient learning. However, such learned pairwise relations are binary and lack the information of which goals can be reached by applying specific policy. Additionally, without any spatial abstraction, it can be difficult to learn these relations for a complex transition relation (e.g. relation that require monitoring more that few variables).
characterisation for environ-
2

---

Published as a conference paper at ICLR 2024
5"
Commander S S.x.
Giiz on (t.0"))
Tutor
Controller S S
S x G :->
EDD
91+1
a oEA
N0
Refinement
Environment
Figure I: Architecture of STAR. The algorithm's inputs the initial state so. the task goal g" , and initial abstraction No. STAR rums a feedback loop Feudal HRL algorithm (dashed red block) and abstraction refinement (blue box). The solid red blocks show the HRL agents (Commander, Tutor, Controller). The agents run at different timescales (k > 1 > 1), shown with the solid, dashed, and dotted lines carrying the feedback from the environment the agents. The Refinement abstract goals (E) visited during the last episode, and outputs an abstraction.
inputs the past episodes (D) and the list of
To introduce spatial abstraction, Zadem et al. (2023) introduce GARA, a spatial abstraction for the goal space that captures richer information from k step reachability relations. This algorithm learns online discretisation of the state space that serves as an abstract goal space. This abstraction generalizes reachability relations over sets of states, greatly reducing the difficulty of the learning problem. This approach however was only validated on a 4-dimensional environment and suffers from scalability issues as the abstraction is learned concurrently with the hierarchical policies. As GARA starts learning from a coarse abstraction (composed of a small number of large sets), the goal set is often distant from the current state, thus it can be difficult to learn meaningful policies that manage to reach a desired goal set. Under such circumstances, the approach is blocked targeting a hard reach goal and cannot improve as it lacks any mechanism propose easier, more granular subgoals. To alleviate this discrepancy, we introduce a new agent in the hierarchy of GARA that applies temporal abstraction (Sutton et al., 1999). Our intuition is synthesise between the discrete goal chosen from the top-down process and the temporal transitions allowed by the current low-level policy from the bottom-up process, through mid-level agent that acts as an intelligent tutoring system and learns to select intermediate goals g E S that: (a) can be reached from state executing the current low-level agent; and (b) helps constructing trajectory from to a goal abstract state G G.
3 SPATIO-TEMPORAA ABSTRACTION VIA REACHABILITY
We consider goal-conditioned Markov Decision Process (S, Peren) as environment, where C R" a continuous state space, A an action space, P(* 18t, at) is a probabilistic transition function, and Fezt S x S - R is parameterised reward function, defined the negative distance to the task goal g" E S, i.c (ex g²) = -وا s||2- The multi-tas task reinforcement learning problem consists in learning goal conditioned policy to sample each time step i. an action a ~ T(s g²), so as to maximizes the expected cumulative reward. The spatial goal abstraction is modeled by set-based abstraction defined by function N S - 2 that maps concrete states to sets of states (i.e., Vs E (s) C S). We write Gx to refer to the range of the abstraction A,, which is intuitively the abstract goal space. We further drop the subscript (i.e., write G) when A is clear from the context and denote elements of G with the upper case letter G.
We propose HRL algorithm, Opatio-Tempont Abstraction via Reachability (STAR), that learns, at the same time, spatial goal abstraction N and policies at multiple time scales. The STAR algorithm, shown in Figure 1, has two main components: 3- Feudal HRL algorithm (enclosed in the red dashed lines); and an abstraction refinement component (shown in the blue solid lines). STAR runs the Feudal HRL algorithm and the abstraction refinement a feedback loop, refining the abstraction A' at the end of every learning episode. Observe that the high-level agent (called Commander) samples a goal G from the abstract goal space G, and that such a goal can be difficult to reach from the current state. The first intuition of the algorithm is that. to reach possibly very far goal G set by the high-level agent (Controller), the middle-level agent (Tutor) achieves a temporal abstraction of the Controller actions by sampling intermediate subgoal g E S of difficulty
3

---

Published as a conference paper at ICLR 2024
level adapted to the current non-optimal policy. The second intuition is that the algorithm learns the abstraction iteratively. Every refinement obtains a finer abstraction ''' from W. Intuitively, N'' will split at least a goal G1 E GN in two goals G₁, G E GA there are different states in G1 (i.e., Sa,86 86 E G1) that cannot reach the same target G2 E 9 when applying the same low-level policy. While we will define such reachability property precisely later, intuitively the refinement separates goal states that "behave differently" under the same low level policy (i.e., A'' would represent more faithfully the environment dynamic).
We first explain how STAR uses the different hierarchy levels address the challenges of learning policies when the abstraction is coarse (Section 3.1), and then formalize a refinement that obtains a reachability aware abstraction (Section 3.2).
3.1 A 3-LEVEL HIERARCHICAL ALGORITHM FOR TEMPORAL ABSTRACTION
The feudal architecture of STAR is composed of a hierarchy with three agents:
1. Commander: the highest- level agent learns the policy #Comm S x S - G that is a goal- conditioned on g* and samples an abstract goal G É g that should help to reach the task goal g* from the current agent's state (G++k T8omm(8 (81.9") ))
2. Tutor: the mid-level agent is conditioned by the Commander goal G. It learns the policy Tia S x G - S and picks subgoals in the state space (g++1 (Tte G+++)).
3. Controller: the low-level policy Tomn x S - AA is goal-conditioned by the Tutor's subgoal g and samples actions to reach given goal
TCom (5),
The agents work at different time scales: the Commander selects goal Gi+b every l steps, the Tutor selects goal gt+1 every 1 steps (with k multiple of (), and the Controller selects an action to execute at every step. Intuitively, the Commander's ' role in this architecture to select an abstract goal GL+* (i.e. a set of states that are similar and of interest to solve the task) from the current state 8t, However, the initial abstraction & of the state space very coarse (i.e., the abstract regions are large sets and still do not represent the agent's dynamic). This means that learning a flat policy that reaches Ge+* from 8 is very challenging. The Tutor samples subgoals 96+s from that are intermediate, casier targets to learn to reach for the Controller, instead of possibly far away state that might prove too difficult to reach. Intuitively, the Tutor implements a temporal abstraction mechanism. The structure of STAR guides the agent through the large state-goal abstraction, while it also allows the agent to learn manageable lewelevel policies.
We set the reward at each level of the hierarchy following the above intuitions. The Comman- der receives the external environment reward after & steps for learning to reach the task goal g": (art (x,,") This reward is computed as the extrinsic reward of the clos- point in (s+)) g" The Tutor helps the Controller reach the abstract goal, and is thus warded by a distance measure between 8 and the G1+ki (st, G++R) -1 Center Center(G++*)) (G++))]l2, where Center(G (G++) is the center of the goal Gr+k- Finally, the Controller is rewarded with respect to the Euclidean distance between subgoals sampled by the Tutor and the reached state: TCont (r+) := 1|g++1 scl12. This intrinsic reward allows the Controller to learn how reach intermediate subgoal states g1+1-
CComm (8)) == maxxeNV(s.) (
3.2 REFINING N VIA REACHABILITY ANALYSIS
While we follow the high level description of the refinement procedure of the GARA (Zadem al., 2023) algorithm, we adapt it to our notation and to the new theoretical results on the refinement we present later (which holds for both GARA and STAR). Furthermore, in the rest of this Section and in Section 4, we will assume 2-level hierarchy, where Tcomm is the high-level policy (e.g., Anigh), and Now is the hierarchical policy obtained composing TTu and T.oot
We first define the k-step reachability relation for goal-conditioned policy NN
R R G,,, == s ESSSSEG
TNim (c, G5)
II the following, use the upper-case G letter for goals in and the lower-case g for subgoals in S.
4

---

Published as a conference paper at ICLR 2024
k
where 8
s means that can reach s' by executing the policy (NG,). (targeting G3)
TNi [N G3)
in l steps. In other words, R Re (Gú, G5) is the set of states reached when starting in any state in G2 and applying the policy ( (.) for ls steps.
The algorithm uses the notion of reachability property among a pair of abstract goals:
Definition 1 (Pairwise Reachability Property) Let N S + 2 be a set-based abstraction and G2, Gj E 9x. N satisfies the pairwise reachability property for (G,, G2) if R N GG,
The algorithm decides to refine the abstract representation after an episode of the HRL algorithm. Let 3 := {Ga..... G,3 be the list of goals visited in the last episode. The refinement algorithm analyzes all the pairs (G;, G.+1) E E, for S i < ni and refines N' in a new abstraction N by "splitting" G; if it does not satisfy the pairwise reachability property. Each refinement obtains a new, finer abstraction N where the reachability property is respected in one more goal. We formalize when abstraction '" refines an abstraction A with respect to the reachability property as follows:
Definition 2 (Pairwise Reachability-Aaare Refinement) Let N S - 2 and N ::S + 2 be two set-based abstractions such that there exists G3 E GN, GX- (Gx M (G,)) U UYG', G G₁ UG2-- = G. and Gi, n G22 0. N refines N (written as No < N) if. for some G, E 9N, N" satisfies the pairwise reachability property for (G', Gz), while N does not sutisfy the pairwise reachability property for (Ge, Gz).
3.2.1 REFINEMENT COMPUTATION
We implement the refinement similarly to GARA. We represent an abstraction N'' directly with the set of abstract states GN == {GI,..., (G.,...,G...B a partition of the state space S (i.e., all the sets in Gy are disjoint and their union is S). We represent each G E GNV as a multi-dimensional interval (i.e.. a hyper-rectangle). We (i) train a neural network F& predicting the k-step reachability from each partition in GN; and (ii) for each G,, G++1 E E, we check pairwise reachability from Fx: and (iii) if pairwise reachability does not hold, we compute a refinement A" of ...
We approximate the reachability relation with forward model, a fully connected feed forward neural network F& S GN + S. Fst,,, Gj), is trained from the replay buffer and predicts the state 8t4* the agent would reach in k steps starting from a state 8, when applying the low level policy T.i (s, G3) conditioned on the goal Gj. We avoid the non-stationarity issue of the lower- level policy TNi... by computing the refinement only when TNi. is stable. See Appendix C for more details. We use the forward model Fx to evaluate the policy's S stability in the regions visited in E by computing the Mean Squared Error of the forward model predictions replay buffer, and consider the model stable only if the error remains smaller than a parameter o over window of time.
batch of data from the
Checking the reachability property for (Gi, Gj) amounts to computing the output of Fa G5), for all states & E G, i.e., R (G:, G;)= (s, E Gi), and checking if R (G,, Gj) g
Gy. Technically, we compute an over-approximaatoon RA (G,, G,) 2 B (G., G,) with the Ai2 (Gehr et al., 2018) tool. Ai2 uses abstract interpretation (Cousot & Cousot, 1992; Rival & Yi, 2020) to compute such an over-approximation: the tool starts with a set-based representation (e.g.. intervals, zonotopes, ...) of the neural network input, the set G,, and then computes the set of outputs layer- In Fg. each layer applies first a linear transformation (i.e. for the weights and biases) and then piece-wise ReLU activation function. For each layer, Ai2 computes first an over-approximation of the linear transformation (i.e., it applies the linear transformation to the input set), and then uses this result to compute an over-approximation of the ReLU activation function, producing the new input set to use in the next layer. Such computations work on abstract domains: for example, one over-appro linear transformation applied to interval by computing the transformation, and then a convex-hul to obtain the output in the form of an interval. The over-approximmtionn for ReLU activation functions are described in detail in Gehr et al. (2018).
We split the set G, when it does not satisfy the reachability property w.r.. G Since G3 is an interval, we implement the algorithm from (7adem al., 2023; Wang et al., 2018) that: (i) stops if
5

---

Published as a conference paper at ICLR 2024
G2 satisfies the reachability property none of the states in G, reach Gy; and otherwise (ii) splits G2 in two intervals, G; and G", calling the algorithm recursively on both intervals. This results in two sets of intervals, subsets of G. that either satisfy the reachability property not. Such intervals are the new intervals replacing G; in the new abstraction (see Appendix F).
THEORETICAL PROPERTIES OF THE REFINEMENT
In this section, motivate the adoption of the goal-space abstraction and the reachability- aware refinement showing that: (i) there exists a bound on the sub-optimality of policies trained with a reachability-wwan abstraction; and (ii) the reachabilit--aware refinement gradually finds reachability-wwaee abstraction. Our results apply to both STAR and GARA (Zadem et al., 2023), and all the proofs are available in the Appendix A.
The theoretical results hold under the assumptions that the environment M is deterministic and the reward signal Cext is bounded in the environment. Consequently, we assume that the distance separating state E S from all the states s' E S that can reach in one step is bounded. Thus, there is an upper bound Rmax
max s,y'E5.E.EA P))1)s,))00' ||s 8'112 on the reward signal.
Let π² be the optimal hierarchical policy composed by a high-level policy g ~ (sigh g") that sam- ples g E S, and a low-level policy a ~ [s. g) that samples actions a E A. Since the environment deterministic, there exists optimal high-level trajectory containing the goals sampled with Tnigh and optimal low-level trajectory containing all the visited states:
Thigh = (90..1.......................... :. Im T := {50, 81...., km.k). with s g9. for 0 Sii SiS m.
Let N S + 2 be set-based abstraction. We write T for the optimal hierarchical policy obtained with the abstraction N. We write TNima and Thim for the optimal high- and low-level trajectories respectively. Below, we provide an upper bound on the difference between the optimal hierarchical policy x² and the optimal hierarchical policy "N when N is reachabiliy-awwre.
Definition (Reachabiltyy-Aware Abstraction) Let N S- 2 be a set-based abstraction, T' the corresponding optimal hierarchical policy, and Thigh the optimal high-level trajectory from Fiigh N is reachability-awwa aware abstraction with respect to Thigh if:
1. States are contained in their abstraction; Vs E S, (N))
2. The abstractions of the goals in the optimal trajectory are disjoint:
Yge. 9j Tright (g. $ 9, + Ng,)) (N( = 0).
3. The abstractions of each consecutive goals in the optimal trajectory satisfy the pairwise reachability property:
Vgs, 9i+1 Thight
R Ni..
((())) C
4. The reward in the final abstract goal (gm) is bounded:
7e 0,4' (rgg))-rrallmm) Teu())) Se.
Theorem (Sub-optimal Learning) Let M be a deterministic environment with task goal g E S and T Text (8) -Ilg* -812- Let N S + 2 be reachabiliy-aware abstraction with respect to high Then, for 8o E Tiom and s E TNN.... we have that:
(mk 1) -1) 22 + 1 - 1-ynk+3 n
V*- (su) Vag (s6)] <
Eri+
Σ
7 C,
where Vs(s) is the value function for policy n (Sutton & Barto, 1998).
Moreover, if there exists a B 2 E > O such that for all 1 <iis m. max || - bl1 5 B, then z.veN(
ss; E Tim and Vs E @Tr... we have that:
1 1- 1-7tk+1 mk
VV (80) - V Vasiun (s6)) 5
(kRmax + B).
(2)
1 1-9

---

Published as a conference paper at ICLR 2024
Equation (I) in the above theorem provides bound the sub-optimality of the hierarchical policy when trained under a set-based reachability- abstraction N.. Intuitively, the worst trajectory Thi.. starting from 5/1 (sp)). can progressively deviate from Low increases. When i 2 22, the trajectories progressively converge around (gm). Equation (2) defines tighter upper bound when there is a bound B on the maximum distance between two states each abstract goal in Timmn In practice, the existence of the bound B is valid when the state space is bounded. In this case, the deviation of the two trajectories is independent from and is stable across time.
má
Lemma 1 Let N and N" be two set-based abstractions such that N' x N and N satisfies the Conditions (1), and (4) of a reachability- aware abstraction (Definition 3). Also, let G; TNmo (note that G₁ E Grr), and G; be the goal refined in No. Then, the abstraction N' satisfies the following:
1. 3 9i ThTigh Thggh such that N does not satisfy the reachability property for (N(o:) while N' does for (
2. If there exists Yj E Higgh such that 9j E (g()), then 93 & (g))
Theorem Given an initial set-based abstraction N and assuming (gmm satisfies the Conditions (1), and (4) of Definition 3, we compute a reachability-wware abstraction after applying a finite number of reachability-wware refinements.
Theorem 2 follows from Lemma and shows that applying the reachability aware refinement for finite number of times we compute saachabiltt--warr abstraction. In practice, the assumption that (gm) verifies criteria and 4 of Def.3 is reasonable since the goal g known in the environment. That is to say, NN (gm) could correspond to region whose center is g and radius is Rmaa.
EXPERIMENTAL EVALUATION
In this section we answer the following research questions: 1) Do the spatial and temporal abstrac- tion of STAR allow for more data-efficient learning? 2) Does the reachability abstraction scale to more complex environments compared to a more concrete reachability relation? 3) How does the learned abstraction decompose the environment to allow for learning successful policies?
5.1 ENVIRONMENT SETUP
(a) Ant Maze
(b) Ant Fall
(c) Ant Maze Cam
Figure Ant environments
We evaluate our approach on set of challenging tasks in the Ant environments (Fig.2) adapted from Duan et al. (2016) and popularised by Nachum et al. (2018). The Ant is simulated quadrupedal robot whose body is composed of torso and four legs attached by joints. Furthermore, each leg is split into two parts by joint in the middle to allow bending. The observable space of the Ant composed of the positions, orientations and velocities of the torso as well as the angles and an- gular velocities in each joint. Overall the state space is comprised of 30 dimensions. The actions correspond to applying forces on actuators the joint. This actions space is continuous and 8- dimensional. We propose the following tasks:
Ant Maze: this task, the ant must navigate a ''' "sh-ppd maze to reach the exit posi-
tioned at the top left.

---

Published as a conference paper at ICLR 2024
2. Ant Fall: the environment is composed of two raised platforms seperated by a chasm. The ant starts on one of the platforms and must safely cross to the exit without falling. A mov- able block can be push into the chasm to serve required by the ant, falling into the chasm is a very likely yet irreversible mistake.
bridge. Besides the precise maneuvers
3. Ant Maze Cam: this is more challenging version of Ant Maze. The upper half of the maze is fully blocked by an additional obstacle that can only be opened when the ant looks at the camera (in yellow in Fig. 2c) when on the red spot. The exit remains unchanged.
We note that these tasks are hierarchical in nature as reaching the goal requires correctly controlling the ant to be able to move (low-level) and then navigating to the exit (high-level). Moreover, both Ant Maze Cam and Ant Fall, no reward is attributed to the intermediate behaviour that unlocks the path to the exit (looking at the camera, pushing the block). Under such circumstances, the underlying dynamics more complex making the reachability relations more difficult to extract.
5.2 COMPARATIVE ANALYSIS
We compare STAR with the following algorithms:
1. GARA (Zadem et al., 2023): this algorithm learns a spatial abstraction via reachability analysis using a two-level hierarchical policy.
2. HIRO (Nachum et al., 2018): this algorithm relies a Manager to sample goals directly from the state space S and learns how to achieve them using the controller.
3. HRAC (Zhang et al., 2023): adopting the same architecture as HIRO, this approach tries to approximate a reachability relation between goals in an abstract space and use to sample rewarding reachable goals. The reachability relation is derived from measuring the shortest transition distance between states in the environment.
4. LESSON (Li et al., 2021): a HRL algorithm that learns a latent goal representations based on slow dynamics in the environment. The latent space learns from features that are slow to change over & steps, in order to capture temporal abstraction.
In line with HIRO and HRAC, STAR relies on an oracle (sss that transforms the observations of the high-level agents (Tutor and Commander). In practice e corresponds to a feature selection applied to states. In contrast, LESSON learns a latent goal space without an oracle. In Ant Maze (b(s) = (I. v). in Ant Fall (s{s) = (ar, y, z). and in Ant Maze Cam, (b()) = (ar, y, 0z, 6z)
Fig.3 shows that STAR outperforms all of the state-of-are art approaches by reaching a higher success rate with less timesteps. particular GARA, operating only under a spatial abstraction mechanism is unable to solve Ant Maze, the easiest task in this analysis. HIRO the other hand learns less efficient policies due to lacking spatial abstraction component. These results show that STAR, which combines temporal and spatial abstractions, is more efficient approach.
To discuss the second research question, we first observe that, while the high-level dynamics of Ant Maze can be captured by the x, y dimensions, the dynamics of Ant Fall require all the z, V, dimensions (2 expresses if the ant is safely crossing above the pit or it has fallen), and Ant Maze unlock the access to the
Cam requires x, y, oz, By: and f_ (the orientation angles are necessary upper part of the maze). Fig.3 shows that HRAC is unable to capture meaningful relations between subgoals and fails in capturing the high-level task dynamic. Similarly, LESSON is unable to learn a good subgoal representation using slow dynamics in Ant Maze Cam. In fact, 0g.0y. and 02 are features that do not respect the LESSON's slowness objective (i.e., they can vary rapidly across k steps). As results, the goal abstraction in LESSON may overlook them, losing critical information in the process. Instead, STAR is capable of abstracting these dimensions and converging to successful policy. We remark that STAR, similarly to HRAC, can be seen as extensions of HIRO with the addition of a reachability-base component that improves goal representation. However, the results shown in Fig. 3 highlight how the addition of the reachability information in HRAC is even detrimental for the performance when the number of features in the oracle increases (e.g., on Ant Fall and Ant Maze Cam). Instead, the STAR's s reachability aware spatial abstraction and intermediate temporal abstraction allow the algorithm scale to more complex tasks.
solving either Ant Fall or Ant Maze Cam due to the increased complexity
8

---

Published as a conference paper at ICLR 2024
AntMaze
AntFall
AntMazeCam
Average suCcesS rate
0.8
Averege SUccesS rate
WannWay wW
0.3
Average
mw
Timestaps
Timesteps
Ses
Timestaps
STAR
GARA
HRAC
HIRO
LESSON
Figure 3: Comparative evaluation averaged over 10 runs for STAR, GARA, HRAC, HIRO and LESSON.
5.3 REPRESENTATION ANALYSIS
We answer the third research question examining the progress of the STAR's Commander agent at different timesteps during learning when solving the Ant Maze. From Fig.4 we can see that, progressively. the ant explores trajectories leading to the goal of the task. Additionally, the frequency of visiting goals in the difficult areas of the maze (e.g., the tight corners) is higher, and these goals eventually refined later in the training, jibing with the configuration of the obstabcles. Note that the Commander'ss trajectory at 3M timesteps sticks close to the obstacles and pass through the maze's opening. resembling an optimal trajectory. This study provides some insight on how STAR gradually refines the goal abstraction to identify successful trajectories in the environment. In particular, STAR learns a more precise abstraction in bottleneck areas where only a few subset of states manage to reach the next goal. We provide the representation analysis on Ant Fall in Appendix B.
1M Timesteps
Timesteps
3M Timesteps
Figure 4: Frequency of goals visited by the Commander when evaluating a policy learned after 1M, 2M, and 3M timesteps (averaged over different evaluations with 500 maximum timesteps). The subdivision of the mazes represent (abstract) goals. The color gradient represents the frequeney of visits of each goal. Grey areas correspond the obstacles of the environment
Maze.
CONCLUSION
In this paper, propose novel goal-conditioned HRL algorithm,, STAR, that combines spatial and temporal abstractions. The spatial representation groups states with similar environment dynamics, and the temporal abstraction compensates for the non-optimality of the low-level policy, allow- ing online learning of both the policies and the representations. STAR's high-level agent learns coarse, although precise, spatial approximation of the environment dynamics that, differently from other algorithms using reachability for goal representation, scales to more complex continuous con- trol environments. STAR outperforms the existing algorithms that either one of the abstractions and that struggle to learn meaningful representations. Here, we further provide theoretical justi- fication for reachability-an sub-optimal policies and learn them with sequence of refinements. In the future, plan to tend our approach stochastic environments, which would require a different reachability property, and oon-Makovvian environments, which would require adding history component to the spatial abstraction.
abstractions, showing that we can use such representations learn

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
We thank the anonymous reviewers for their detailed feedback and discussion on our work.
This research work was partially supported by the Hi! PARIS Center, the Labex DigiCosme (project ANR BREILAAADDD4DSIISSSMMME operated by ANR as part of the program "Investisse- ment d' Avenir" Idex ParisSaclay (ANRI LIDEX003322), the SAIF project (funded by the "France 2030" government investment plan managed by the French National Research Agency under the reference SARR-3-PEIIA-0006 and the AID/CIEDS project FARO.
We additionally extend our thanks the members of the VISTA team in LIX, Ecole Polytechnique for their generous support and provision of computational resources, which were instrumental in conducting the experiments for this research.
REFERENCES
David Abel, Nate Umbanhowar, Khimya Khetarpal, Dilip Arumugam, Doina Precup, and Michael Littman. Value preserving state-action abstractions. In Silvia Chiappa and Roberto Calandra (eds.), Proceedings of the Twenty Third International Conference on Artificial Intelliencce and Statisties, volume 108 of Proceedings of Machine Learning Research, pp. 1639-1650. PMLR, 26-28 Aug 2020. URL
Andrew G. Barto and Sridhar Mahadevan. Recent advances in hierarchical reinforcement learning. Discrete Event Dynamic Systems, 13(1), 2003.
Patrick Cousot and Radhia Cousot. Abstract interpretation frameworks. Log. Comput., 2(4): 511-547, 1992.
Peter Dayan and Geoffrey E Hinton. Feudal reinforcement learning. In NeurIPS, volume 5, 1992.
Yan Duan, Chen, Rein Houthooft, John Schulman, and Pieter Abbeel. Benchmarking deep reinforcement learning for continuous control. In Maria Florina Balcan and Kilian Q. Weinberger (eds.), Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pp. 1329-1338, New York, New York, USA, 20-22 Jun 2016. PMLR. URL
Ben Eysenbach, Ruslan Salakhutdinov, and Sergey Levine. Search on the replay buffer: Bridging planning and reinforcement learning. In NeurIPS 2019, 2019.
Scott Fujimoto, Herke van Hoof, and David Meger. Addressing function approximation error in actor-critic methods. In Jennifer G. Dy and Andreas Krause (eds.), Proceedings of the 35th Inter- national Conference on Machine Learning, ICML 2018, Stockholmsmmsssn, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pp. 1582-1591. http://eeennnmmmmeeee//////iinnn l 8a.html.
PMLR, 2018. URL
Marta Garnelo and Murray Shanahan. Reconciling deep learning with symbolic artificial intelli- gence: representing objects and relations. Current Opinion in Behavioral Sciences, 29:17-23, 2019. ISSN 2352-1546. doi: https://doi.or//10 cobee.. 12.010. Artificial Intelli- gence.
Timon Gehr, Matthew Mirman, Dana Drachsler-Cohert Petar Tsankov, Swarat Chaudhuri, and Mar- tin T. Vechev. AI2: safety and robustness certification of neural networks with abstract interpre- tation. In IEEE Symposium on Security and Privacy, 2018.
Dibya Ghosh, Abhishek Gupta, and Sergey Levine. Learning actionable representations with goal conditioned policies. In ICLR 2019, 2019.
León Illanes, Xi Yan, Rodrigo Toro Iearte, and Sheila Mellraith. Symbolic plans as high-level instructions for reinforcement learning. In AAAI, 2020.
Tejas D Kulkami, Karthik Narasimhan, Ardavan Saeedi, and Josh Tenenbaum. Hierarchical deep reinforcement learning: Integrating temporal abstraction and intrinsic motivation. In NeurIPS, volume 29, 2016.
10

---

Published as a conference paper at ICLR 2024
Siyuan Li, Lulu Zheng, Jianhao Wang, and Chongjie Zhang. Learning subgoal representations with slow dynamics. In ICLR, 2021.
Daoming Lyu, Fangkai Yang, Bo Liu, and Steven Gustafson. SDRL: interpretable and data-efficient deep reinforcement learning leveraging symbolic planning. In AAAI, 2019.
Ofir Nachum, Shixiang Gu, Honglak Lee, and Sergey Levine. Data-efficient hierarchical reinforce- ment learning. In NeurlPS 20/8, 2018.
Ofir Nachum, Shixiang Gu, Honglak Lee, and Sergey Levine. Near-optimal represtttiin learning for hicrarchical reinforcement learning. In ICLR, 2019.
X. Rival and K. Yi. Introduction to Static Analysis: An Abstract Interpretation Perspective. 2020.
Nikolay Savinov, Anton Raichuk, Damien Vincent, Raphaël Marinier, Mare Pollefeys, Timothy P. Lillicrap, and Sylvain Gelly. Episodic curiosity through reachability. ICLR, 2019.
Richard Sutton and Andrew G. Barto. Reinforcement Learning: an Introduction. 1998.
Richard S. Sutton, Doina Precup, and Satinder Singh. Between mdps and semi-mdps: framework for temporal abstraction in reinforcement learning. Artificial Intelligence, 112, 1999.
Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physies engine for model-based control. In 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 5026-5033, 2012. doi: 1...100//RO..2022.6550
Alexander Sasha Vezhnevets, Simon Osindero, Tom Schaul, Nicolas Heess, Max Jaderberg, David Silver, and Koray Kavukcuoglu. Feudal networks for hierarchical reinforcement learning. CoRR, abs/1703.01161, 2017.
Shiqi Wang, Kexin Pei, Justin Whitehouse, Junfeng Yang, and Suman Jana. Formal security analysis of neural networks using symbolic intervals. In USENIX Security Symposium, 2018.
Christopher C. H. Watkins and Peter Dayan. Technical note: q -learning. Mach. Learn., 8(3-4): 279-292, may 1992. ISSN 0885-6125. doi: 10. 10.1007/BF009996998 URL https://doi.org/10..000 0000/ BF00992698.
Mehdi Zadem, Sergio Mover, and Sao Mai Nguyen. Goal space abstraction in hierarchical rein- forcement learning via set-based reachability analysis. In ICDL, pp. 423-428. IEEE, 2023.
Mehdi Zadem, Sergio Mover, and Sao Mai Nguyen. STAR code from: Reconciling Spatial and Tem- poral Abstractions for Goal Representation, March 2024. URI. https://do..og//105888 10814795.
Tianren Zhang, Shangqi Guo, Tian Tan, Xiaolin Hu, and Feng Chen. Adjacency constraint for efficient hierarchical reinforcement learning. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(4):4152 4166, 2023. doi: 10. 11..3199....2..1124111....

---

Published as a conference paper at ICLR 2024
A PROOFS OF THEOREMS
A.1 PROOF OF THEOREM 1:
In this part of the proof, we will study the optimality of the hierarchical policies across the last steps of the trajectory. First, we consider the optimal trajectory for flat (non-hierarchical policy) in the environment described by M:
T := (50, $1, $1....,, SM) where SM =
The optimal hierarchical policy n² composed by "High and TLo samples goal g S every ls steps (where & is parameter). The following optimal trajectories thus:
High (go. 01 . -.m where Im =
Tow = {su, $1 Smk) where Sn-k = In, n E [o..... ml and 8mik g"
The optimal hierarchical policy कं under the abstraction (defined by Def.3) yields the optimal trajectories:
Nima = (((g)).
Thim. (86: 8/,.
) where s/2. E (N E [o,..., m] and s' (N(gg))
We make the distinction between s and s' since Tiow and Mi. do not necessarily follow the same trajectory. Whereas "Low is conditioned by goals that act points in the state space, "ii, is conditioned by whole set of points. Moving forward, we specify the following rewards functions for the hierarchical policies learning without abstraction and with the abstraction AV
For n²" FTiggh (s,g"( Fex((s) - "llg* $112 and FLo (8,g) -1lg s|12
For TM, TNigs (s, g¹) max FIx max xEN(ss
- -1lg" -20== and TN (s)) (z)
=EN((e
Intuitively, TN (s) computed over the closest point g" in M(s). TAL (s, Ng)) binary reward that expresses if the agent reaches its abstract goal. This reward is chosen in this proof for its generality; it simply expresses that the agent should reach (g).. practice is sparse and difficult to optimise (it is replaced in STAR by the negative distance to the center of (g))..
suboptimality bound will be derived for the last steps of the trajectory, and by induction will be proven for the rest. Given criteria.4:
Vs E
rex)(s) Se
we can claim that:
V=: (8mk) VaNi (5 S
To derive the upper bound on suboptimality, we will proceed by computing V on the worst possible optimal trajectory TNi... This gives:
VV (8mk-1) - Va (5'mk-1)1= = (8rkk(mmk)1) + (8az)(mm)) - Text feeee( (8'mk Tezt (m'mk)
< Nest (9mk-1) (5 + 7/Fent (5mb)) Tezt (s
By triangle inequality.
The second term in the inequality corresponds exactly to >/ Tim (8mkk Va (smm)) which is bounded by ry. The first term can be expanded as such:
(eaatSmk--a - Tezt (s/m = Teat (ewt(Smk- 1) - Tezt (s'mmmm))) since Tews (eaerSmmo-11 2 Teue &
= - "lg" - 8mnk | + l|g - 1m1-1112
< - 1lg" 8mnk 1/ + l|g" - 8mk 1/12 + ||8mkk1 - 8mk-1l12
< |smk-11 - 1'1k-1112
k is chosen divisor of M simplify the notations.
12

---

Published as a conference paper at ICLR 2024
Since the abstraction guarantees that starting from .V (gmm-1), state s' (gmm) is reached with TMi. in & steps, then the state S'x should at the worst, be reachable in one step from m In addition, the state n should at the worst be reachable from (m
steps.
In other words, the worst state m 1 is the farthest state from 9m that reaches s in 1 step and is reached by (mm-1) in steps. We will bound ||smk- - 5 smmn- 1ll2 using the two reachability relations.
On one hand, since Smk-1 also reaches Im = =g in step then g1 Smk S Rmax- Then:
1mmk-1 1 S 55mk-1 gmll2 2 + Il.m s Ils'm s'nk-11l2
S 2 Rmaa +
On the other hand, 9m-1 = S(m 1)k reaches Smk-1 1 in h - steps, and then 19mm11 smk 1/12 S (k Rmman Similarly, we could have:
|mnk- 111--1122 S |smk-1 9m 1/12 + 119m-1 (m 11a (m s'mk-1l12
S 2(h: P) + 119m-1 1m=11)
This results in two distinct bounds for [|smk-1 - 8 ll2 origination from forward reachability relation, and a backwards reachability relation. This provides the following bound:
IV (5mk-1) - VaiLa (m I min + e, 2(k 1) + l1gm-1 m (22 + ye
Bounding I19m-1 - 1) depends on the nature of the abstraction, and more specifically the abstract sets can be bounded or not. Starting from the more general case, Def.3 guarantees that s(m--) 1)k. is reachable from s in m..k ft 1) steps. To simplify the computation, can also assume that ||5o - 16112 S e. (In practice usually 8p = *6)- Also, 8(m-1jk is reachable from 8p in m.(k: 1)
steps. Thus
119m-1 ((m-1) = [1gmm 80 + 80 8/ 6 8 mmn--188
2k(m Rmmax
Then:
VVa (5mk-1) Vasjan (s min + e, 2,2mm 1) + + ye
< 2 min (1, (mk 1)) (y 1)e
< 2mmaz + (y + 1)c
With an iteration process the above reasoning can extended: Vi (O...., mkk:
(rene(s:) - Teat (s:) (ext(ss) - Text (s/) since (ent(si) 2 Texr(s)))
- "1gg - s:ll2 + I|g" - s/l12
S - -llg" - sill2 + llg" - s:ll2 + ||s 1 s/ll2
||s - s/112
min(2(mk Rmaa + e, 2iRmax + c) 2 min(mkk - i, immaa +
with min(mn- i,1) -iffi <
mk m
else min(mk i, mk i.
13

---

Published as a conference paper at ICLR 2024
Finally the bound can be computed as:
mik
IV (00) - Vagiem (06))
Σ
7 (Feze((1) - Teor (5())
mk
111s: -8ell2
mk
y min min(mk- i, + +c)
mike
(2iR Rax c) +
Σ
(2(mk - Rmaz + +c)
mike
(2(mk Rmax) + 1 - mmk+1
? (2i Reax) Σ
?
==
mm
mi
mkk
1 m
+
(mk - 1))2Rmaa +
e
1=0
We will now examine the case 3B 2 e >> such that Vi E (1,..., m], max max.. al1 B. Following the reasoning established before, we can claim that:
(e)) (x)) < ||+ s/1l2
< min (2iRmax + +,2(k - i) + B)
K
2 Rmaz) + B
2
< & Rmax +
Ultimately,
mkk
Viii (80)
V Va (s6) Σ (rene(())) Tewt (s())
< 1 mk++1
Rkra + B)
A.2 PROOF OF LEMMA I AND THEOREM
By definition of N², since G3 E Timo then 3g. E G2 (since the reward for the high-level agent is TNim (G,) max (s)) such that Ji reaches state in Ni+1: To prove this we can first consider
max sEG;
the coarsest abstraction N S + GV C 2 s.t G. (Go, G1 with G, ((mm)) (assumed to satisfy criteria and 4) and Go = N N(o)) = .... = -N (1) In this case, the goal in question 9i is in ((mm-1) and by definition reaches 9m G,. This corresponds
Jm-1- Thus, the process of refinement splits Go such as Go G" U G' n G" = 0 and identifies G' such that 9m-1 E G' (since G satisfies the reachability property for (G", G++1)) and G" =V'(go) Additionally, G', G" and G₁ are disjoint by definition of the refinement.
N (gm-2).
By induction, the lemma proven. The induction also leads reachability abstraction proving theorem 2.
B REPRESENTATION ANALYSIS IN ANT FALL
Similarly to the study established in 5.3, we provide the results obtained in Ant Fall (visualizing the 5 dimensional representation for Ant Maze Cam is less feasible).
14

---

Published as a conference paper at ICLR 2024
0.8
0.
04
30
30
30
-0
13
13
0.0
1M Timesteps
2M Timesteps
3M Timesteps
Figure 5: Frequency of goals visited the Commander when evaluating a policy learned after 1M. 2M, and 3M timesteps (averaged over different evaluations with maximum timesteps). The subdivision mazes represent (abstract) goals. The color gradient represents the frequency of visits of each goal. Grey areas correspond to the platforms of the environment in Ant Fall. The red box is the movable block. Observe that, around 3M timesteps, goals are further split across the a-axis above the pit.
Fig.5 shows that after 1M steps the ant gradually learns to approach the area nearing the movable block (colored in yellow in the figure). Around 2M steps, the starts succeeding crossing the pit by pushing the block forward. By 3M steps, the Commander has refined the abstraction and identified goal the bridge-like region (immediately at the back of the movable block) that it targets most frequently to maximise its success to cross the chasm.
This representation further validates our hypothesis regarding the ability the reachability aware ab- straction to identify areas of interest in the environment and orient the learning of the agent towards optimal behaviour.
C ADDRESSING NON-STATIONARITY
Since STAR 3-vevel HRL algorithm, non-stationarity can affect the learning of the Tutor as well as the Commander.
To solve this problem the Tutor, we incorporate the policy correction approach from Nachum et al. (2018) which adequately relabels subgoals in the replay buffer that are unadapted to the current policy of the agent.
Additionally, we address non-stationarity in the Commander level by only refining the abstraction when the controller's s policy is stable. Precisely, reachability analysis for (G,, ) is only engaged deterministie behaviour
when the controller's policy T.i... (s G., Gу) has roughly converged and is not randomly taking actions. Since the forward model is trained on data generated by T it could be used proxy for assessing behaviour stability. Every time the transition (Gi, Gj) is explored, the error prror(Fx(s E G,, Gj)) is evaluated and stored. Finally, we infer the stability of learned policies from the progress of the error the forward model during a window of time; if the last 10 evaluated errors satisfy error F&& (s G,, Gý)) < a then the policy is considered stable and reachability analysis conducted.
D COMMANDER POLICY LEARNING
D. POLICY TRAINING
The Commander's policy mainly uses Q-learning (Watkins & Dayan, 1992) to learn a policy commm for goal sampling. This choice is adapted to the discrete and small nature of the problem that the Commander is expected to solve. More precisely, both the state and action spaces of the Commander correspond to since the Commander is in state G, and has to select next partition G to target. Additionally, we use the learned reachability relations to orient the exploration of the agent towards reachable goals. This is done by restricting the exploration sample reachable goals when
15

---

Published as a conference paper at ICLR 2024
possible. Formally, at goal G2 the Q-values computed only goals Gy that G3 is known reach (following reachability analysis).
D.2 HANDLING A GROWING STATE SPACE
Following refinement of the goal space G, new goal space G' is formed such that [9'] > [g]. To handle a growing state space, the Commander transfer the Q-talee computed on the state space G the new state space G'. Assuming that G2 is the goal that was refined in G, then Gy and 2222 are the newly created goals with G², reaching G/41 Gi+1. In that case, Q(G", G1+1) = max Q(G", ((++)), and Q(G", G/+1) GEg' GEG
min ((G)) Additionally,
VG' E E9, s.t G' G2 and G' + C Q(G", ( versely, YG" G, G * G1+ G,+1, Q(G G') Q(G',, G') = Q(G,, G") (here G G"). In summary, the new Q-tables modifies the Q-values between the refined goal and its target while preserving the rest of the values.
= Q(G', G.
Q("', G.) (here G = G'). In-
D.3 INITIALISATION OF THE ABSTRACTION
The algorithm start without an abstract goal. After initial exploration, and once the controller's policy stable (see C for more details), we split S into set of visited states and a of unvisited ones. Consequently the initial abstraction becomes G = Go U Go. with Go the set of visited states and Gū the complement of Go in S, representing unvisited states. This resulting abstraction still coarse (e.g., partitions the state once space over the and dimensions) and is mainly useful to identify an abstract state enclosing neighborhood of the initial state.
E ENVIRONMENT DETAILS
The implementation adapts the same environments (Ant Maze, Ant Fall) used in Nachum et al. (2018) with the addition of Ant Maze Cam. All of the environments use the Mujoco physics simula- tor (Todorov al., 2012). all the following setups, the training episode ends mar timesteps = 500. The reward signal is dense and corresponds to the negative Euclidean distance to the goal y" scaled by a factor of 0.1. Success achieved when this distance is less than fixed threshold of
1. Ant Maze: The maze is composed of immovable blocks everywhere except in (0, 0), (8, 0), (16, 0), (16, 8), (16, 16), (8, 16), 16). The agent initializes at position
(0, 0). At each episode, target position is sampled uniformly from z [-4,200], 20).
[-4, 20). At evaluation time, the agent is only evaluated for a fixed exit 16).
2. Ant
the agent is initialized Immovable blocks are placed everywhere except at (-8,0), 0). (0. (- (), (-8, 16), (0. 16). (-8,24) (0, 24). A pit is within range 12] x [12, 20). A movable block placed at (8, 8). The agent is initialized at position (0, 0, 4.5). At each episode, the target position is fixed to (o 9y 9
Fall:
an elevated platform of
height 4.
(0, 27, 4.5). The ant has to push the block into the pit and use it as a bridge to cross to the second platform. At evaluation time, the agent is only evaluated for fixed exit at (0, 27, 4.5).
3. Ant Maze Cam: This maze is similar to Ant Maze with the addition of new block at (16, 8) effectively closing any passage to the top half of the maze. For the block to be re- moved, the ant needs to navigate to the area in the range [16, 20] [0, 8] where camera is placed. the area, the orientation ori(Oz. 20.00 Oy, 0z) needs to be negative simulating an iden- tification process by the camera. ori(O,, By. 02) is function that projects the orientation on the xy plane.
F THE REACHABILITY ANALYSIS
The reachability analysis STAR closely follows the process detailed in Zadem et al. (2023). First, approximate the k-step reachability relations between states with neural network model: Fk- More precisely. (s,, G2) predicts the state s'44 reached after steps when starting from s, and targeting the abstract goal Gj-
16

---

Published as a conference paper at ICLR 2024
To generalise these approximations from state-wise relations to set-wise relations, we rely off ofe-the- shelf neural network reachability analysis techniques. Specifically, we use Ai2 (Gehr et al. (2018)) to compute the output of neural network given set of inputs. Consider the reachabilty analysis of a transition (G;, Gj). Ai2 computes an over-approximation the output set of the forward model; R (G,, G2) = { = (s,, Gy), E G This over-approximation is efficiently computed layerr in the neural network using operations abstract domains. In practice, abstract goals are represented as disjoint hyperrectangles since they are expressive our applications and simple to analyse.
The algorithm checks if R TT (G,,G) S Gj, i.. the reached set of states is inside the abstract goal. If the inclusion is valid, then the reachability property is verified (G,, G₃) and no splitting is then the reachability property cannot be respected
required. Similarly, R& Nui (Gi, G2) n GG; for any subset in G; and no refinement occurs. Otherwise, the algorithm splits the starting set G; in two subsets across dimension of the hyperrectangle. Each split is recursively tested through reachability analysis and searched accordingly until a subset that respects reachability is found or maximal splitting depth is reached.
Abstraction Refinement: As detailed in section F, an important step of our algorithm when conducting reachability analysis on transition (G,, Gÿ) is to verify if R Rx (G,, G2) S Gj- In practice, since R is an over-approximation, we can expect to have estimation errors in such way that verifying the precise inclusion is very difficult. We rely on a heuristic that checks V(R Ni (G,G)))GG,)
TI, with V( the volume of hyperrectangle and T a predefined thresh- old. This heuristic roughly translates to checking if most of the approximated reached states Noo (G,,G) n G, 0, we verify
V(G,)
are indeed in the abstract goal. Similarly, to check if Rk
v(R Ni (G,,G))nG,) S 12 with 72 preset parameter. That is to say, we check that most of the V(G,) abstract goal is not reached. Finally, we set minimum volume ratio of split compared to G,-
G HYPERPARAMETERS
G.1 TUTOR- CITOR-CONTROLLER NETWORKS
The implementation of our algorithm is adapted from the work of Zhang et al. (2023). The Tu- tor and Controller use the same architecture and hyperparameters goal space). It should also be noted that the policy correction method introduced in HIRO, is simi- larly used in HRAC and STAR. Both the Tutor and Controller use TD3 (Fujimoto al., 2018) for learning policies with the same architecture and hyperparameters as in Zhang et al. (2023). The hyperparameters for the Tutor and Controller networks are in table
HRAC (albeit with different
G.2 THE COMMANDER TRAINING
The Commander uses an e-greedy exploration policy with 6p = 0.99 and emin 0.01 with linear decay of factor of 0.000001. The learning rate of the Commander is 0.01 for Ant Maze and Ant Maze Cam and 0.005 for Ant Fall. The Commander's experience is stored in buffer of size 100000 (this buffer used to train Fz). The Commander's actions frequency is k = 30.
G.3 FORWARD MODEL.
For the forward model size (32, 32). We use the ADAM optimiser. This neural network is updated every episode for transi- tions (G,, Gj) E & if this transition has been sampled for defined minimal number of Commander steps (to acquire sufficient data). Table.2 shows the hyperparameters of Fi.
fully connected neural network with MSE loss. The network is of
G.4 REACHABILITY ANLYSIS
Table.3 shows the hyperparametes of the reachability analysis.
17

---

Published as a conference paper at ICLR 2024
Hyperparameters
Values
Ranges
Tutor (TD3)
Actor learning rate
0.0001
Critic learning rate
0.001
Replay buffer size
200000
Batch size
128
Soft update rate
0.005
Policy update frequency
0.99
Tutor action frequency
10
Reward scaling
0.1 for Ant Maze (and Cam) / 1.0 for Ant Fall {0.1, 1.0)
Exploration strategy
Gaussian (a 1.0)
{1.0, 2.0
Controller (TD3)
Actor learning rate
0.0001
Critic learning rate
0.001
Replay buffer size
200000
Batch size
128
Soft update rate
0.005
Policy update frequency
0.95
Reward scaling Exploration strategy
1.0
Gaussian (a = 1.0)
Table I: Hyperparameters for Tutor and Controller networks based on Zhang (2023)
Hyperparameters
Values
Forward Model
learning rate
0.001
Buffer size
100000
Batch size
64
Commander steps for data-acquisition
5000 for Ant Maze and Cam/ fam//0000 for Ant Fall
Epochs
5
Table 2: Hyperparameters for the forward model
H STAR'S PSEUDO-CODE
For reproducibility, the code for STAR along with the experimental data are published in Zadem al. (2024).
Hyperparameters
Values
Reachabililty Analysis
NN reachability analysis tool
A12 (Gehr et al., 2018)
Ti
0.7
72
0.01
Minimal volume ratio of a split
0.125
Table Hyperparameters reachability analysis
18

---

Published as a conference paper at ICLR 2024
Algorithm STAR
Input: Learning environment E.
Output: Computes TCoom, Tia and TCoo Dommamder f- V. Druur f- 0, Controller +- 0, G +- S
for mar. támesteps do
E
4: Sinir f- initial state from E, 81 6- Sinit
G. + G G such that G
Ga TComm (G.. 9
St (Sc, Ga)
while truc do - EU [(G,, Ga)]
10:
de (st, gt)
(st+1, done) & execute the action ae 8, in
12:
TCmntoller lige 8t|l2
13:
Update TCoa
14:
if not done then
St+1, 1-1
if mod then
17:
TCommander = - 8t Center(Gaa)le
18:
Drute +- (8t-1, Gd, It-L, PTuner, done) Update
19:
9i Trai (st, Gx) if l mod
21:
then
22:
TCommunder = -1 g"
23:
Update Deoomander + (S Ga, St, ('Commaddr, done)
24:
Update 7Camm
G. G such that se G
26:
Ga ~ Tecmm (8,, Jearit
27:
else
28:
Update Fs with the data from Deommanee
G RefineeG, Fi)
30:
break the while loop and start a new episode
19


Reviews:
[{"review_id": "HRQDbZorve", "reviewer": "Reviewer_L6eb", "summary": "The paper addresses reachability-aware abstraction with temporal abstraction in goal representation for Hierarchical Reinforcement Learning. The proposed model, building from ideas described in GARA(Zadem et al., 2023), tries to overcome the limitations of SOTA methods suffering from scalability when dealing with complex goals or high-dimensional environments. \\\nSTAR introduces a three-agent architecture where every agent acts on distinct timescales with separate reward functions. The three layers feed different goal abstractions, subject to a reachability condition that refines them. Under the assumption that the environment is deterministic and the reward signal is bound in the environment, the authors show that the newly refined abstraction leads to a bound on the sub-optimality of the hierarchical policy.\\\nThe experiments are three of increasing dimensionality, namely bi-dimensional Ant Maze, tri-dimensional Ant Maze Fall, and five-dimensional Ant Maze Cam. Results show that the method proposed achieves a higher success rate in fewer time steps w.r.t. three recent HRL methods.\\\n In the appendices, the authors report proofs of the theorems appearing in the main text, details of the architecture, specifications of the experiments, and STAR pseudo-code.", "questions": "1. Have STAR been experimented on different tasks than the maze?\n2. What network is used to train {\\mathcal F}_K?\n3. Why not compare with Nachum et Al. ICLR 2019?\n4. Have STAR been experimented with larger scale space than the example given?\n5. 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?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "Originality:\\\nThe idea is original, as far as the reviewer knows, though limited to 'an extension of HIRO with the addition of a reachability component', as the authors note. The idea of abstraction based on a recursive splitting states partition to refine the agents' dynamics is new, and it ensures reachability for each agent at different levels of abstraction.\n\n\nQuality:\\\nAs far as the reviewer could check, the paper provides sound statements that support the implementation and the results. There are a few misprints that can be easily checked. \n  \nClarity:\\\nThe paper has a good structure; it is quite straightforward, and it explains nicely the problem and its collocation in the literature. The proofs in the appendix are reasonably clear, and the STAR pseudo code supports a good procedural understanding of the proposed method.\n\n\nSignificance:\\ \nThe experiments improve the results over the chosen HRL competitors.   The paper provides a contribution to HRL with a simple yet effective idea.", "weaknesses": "The goal space {\\mathcal G} and the state space S need to be more clearly stated. By definition, {\\mathcal G} is a partition of S, initially a coarse one. In B.1. of the Appendix, it is written that \"both the state and action spaces of the Navigator correspond to {\\mathcal G}\". \n\n What does not seem clear is:\\\n1. What are initially {\\mathcal G} and G_t.  Namely, if {\\mathcal G} initially contain the whole set S and not just some subset of S, then it is clear that the next partition is chosen from {\\mathcal G} or from the current G_t, otherwise, some clarification on the initial {\\mathcal G} might be needed, also for actions.\n2. The action space is said to be in {\\mathcal G}, and it needs to be explained if it is in {\\mathcal G} regarding the history or possible actions. Thus, it would be better to clarify R_{max}.\n\nMaybe I missed something, but I do not see how just assuming \n{\\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. In particular, what is M in the last but one line on page 6? \n\nThe sentence on page 4, after the Navigator reward, \"The max in this reward is computed over observed exploration data\", is not entirely clear, \"observed\" in which sense? \n\nIn 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.\n\nIt seems that to do the exploration for checking the reachability property (page 5), the complete partition of the states is required, but how the exploration scales with the dimension of S is not discussed.  \nAppendix B.2 discusses the growing state space, but there is no discussion about the computational cost of the exploration given the state space partition.  \n\nFigure 4 is not so exciting; I do not see that \"progressively, the ant explores trajectories leading to the goal of the task.\" \nI found the representation of the exploration of the Ant Maze environment given in Nachum et Al. ICLR 2019 quite appealing. The pictures could be improved.", "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": "", "extra_scores": {}}, {"review_id": "ginifn37M2", "reviewer": "Reviewer_ep9K", "summary": "In this paper, the authors introduce a groundbreaking three-layer Hierarchical Reinforcement Learning (HRL) algorithm known as STAR, designed to tackle complex tasks by combining spatial and temporal abstractions in goal representation. Goal-conditioned HRL has proven effective in breaking down challenging tasks into simpler subtasks, but previous methods encountered limitations when dealing with environments characterized by intricate state reachability relations. STAR, on the other hand, addresses these challenges by introducing both temporal and spatial abstractions, presenting a novel approach that bridges the gap between these two essential aspects of HRL.\n\nAdditionally, they provide theoretical insights into the regret bounds of learned policies. Furthermore, the authors empirically demonstrate the power of STAR in complex continuous control tasks, showing its ability to scale to environments with intricate dynamics. This work is said to contribute three elements to the field of HRL: the novel STAR algorithm with its three-layer hierarchy, the theoretical justification for reachability-aware goal representations, and empirical evidence of STAR's effectiveness in combining temporal and spatial abstractions to handle complex tasks. These contributions position STAR as a solution for addressing the challenges posed by complex, high-dimensional environments in reinforcement learning.", "questions": "1- In section 3-1, at the end of manager and navigator definitions, what do you exactly mean by $Gt+k ∼ \\pi_{Nav}(s_t, g∗)$ and $g_{t+l} ∼ \\pi_{Man}(st, G_{t+k})$? Is not '~' used to show sampling from a distribution everywhere else in the paper? I assume it is only meant to say the abstract goal set and subgoals are conditioned on $\\pi_{Nav}$ and $\\pi_{Man}$, respectively.\n\n2- How is the composition of $\\pi_{Man}$ and $\\pi_{Cont}$ to generate $\\pi_{low}$? \n\n3- How do you initialize $N$ and a state set $G$ of interest to solve the task? Is there a measurement for that or is it randomly chosen based on $pi_{nav}$? If it is based on $pi+{nav}$ behavior, how do you deal with the high variance during training? Especially when the dimensionality of the environment increases, variance exponentially grows. \n\n4- The Manager's reward can help in simple cases to learn how to sample subgoals that help the agent reach Gt+k. But if there are fixed randomly shaped barriers in an environment, is this still working? Planning might help with such cases. I think it is important to design the Manager's reward carefully based on the environment's dynamics. \n\n5- Are all the proofs in section 4 novel, or did they exist in previous work (e.g. in GARA or Liu 2021)?\n\n6- \"....  $g ∼ \\pi^∗_{high}(s, g^∗)$ that samples $g \\in S$, and a low-level policy $a ∼ π^∗_low(s, g)$ that samples actions $a \\in A$\", how come that both actions and goals are sampled from policies?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "- STAR performs online learning of both policies and representations. \n- Using reachability provides meaningful goal representations by exploiting the dynamics of the environment, and allows scaling up to complex continuous state space control problems.\n- Theoretical contributions: The authors attempted to define a bound on the sub-optimality of policies trained with reachability-aware abstractions, reinforcing their approach's theoretical basis, and providing support for the progressive refinement of these abstractions during the learning process. (Question 3)\n- Reasonable choices of environment settings and baselines to evaluate the proposed approach.\n\nWriting skills: \n- In addition to explaining the intuition behind the proposed solution, the authors have nicely put it into a mathematical description that is also easy to follow and understand.", "weaknesses": "Majors:\n- The results have been plotted only for 5 runs. Usually, this is not enough number of runs. Especially, in AntMaze and AntMazeCam where the results of HIRO and HRAC are close to STAR. \n\n- It is not clear what a \"Complex\" continuous control task means. How to measure the complexity? Is it only related to scaling up the dimensionality, or is it also affected by distribution changes or even complications in the environment? \n\n- It seems important to have a deterministic environment. The paper mentions that STAR is able to perform online. I assume it might be able to adjust to the stochasticity of the environment with some tricks.\n\n- I suspect this approach might suffer from high variance during learning due to the high non-stationarity between multiple layers of hierarchical agents. However, I believe there exist some tricks to alleviate the problem. For example, define the reachability for a backward model, so that it starts from the Goal set that the task goal $g*$ belongs to, and find all groups of states that FROM them, $g*$ group is reachable. This way, we might not need to go over all G_0 to G_n subset of abstract goal sets visited in an episode, but just visit the ones that lead to the G* set.\n\n- I think there are two types of policies based on the way you are using them in this paper. One type of policy maps state to state (maybe a policy-conditioned transition probability?), and goals can be sampled from them; the other type is the common concept of policy in RL, where maps state to actions. See Q1 and Q6, please. \n\n\nMinors:\n- imprecise usage of motifs: see questions 1 for example\n- And some minor typos like: e.g., in Conclusion, ln 2: 'spactial' instead of 'spatial*', in 5.3: 'In Fig.4 we we',\n\nAll in all, I have doubts about the soundness of the conclusions and proofs in the paper. I would be happy to change my rating if I learn more about my questions. I see the value of the core idea of this work.", "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": "", "extra_scores": {}}, {"review_id": "D4kHczmbOQ", "reviewer": "Reviewer_awpo", "summary": "The paper introduces STAR, a hierarchical reinforcement learning algorithm. The main components of STAR are: the Navigator that selects high-level abstract subgoals, the Manager that chooses single-state subgoals that lead towards the Navigator's abstraction, and the Controller that executes low-level actions. During training, the representations are refined to better relate to the environment dynamics and agent capabilities. The authors test the performance of STAR in AntMazes.", "questions": "How do you estimate the reachability for _all states_, provided that the state space is continuous?\n\nWhat is the computational cost of refining the abstractions?\n\nHow are the abstractions represented? I bet the sets are not represented explicitly.\n\nWhy is the Navigator useful? Why not just leave the Manager and Controller? What are the theoretical and practical advantages of introducing the Navigator? Especially, given that in the end there are only several abstractions, as you show in the experiments.\n\nWhy does Theorem 2 make your method sound (recalling that you prove there exist _some refinements_, not necessarily the one you actually do in the algorithm, right?), and why it is not trivial to construct such an abstraction (e.g. by partitioning the space into any $\\varepsilon$-diameter sets)?\n\nIt's a pity that by introducing the Manager you lose the abstraction of the Navigator. Can you instead of sampling a single subgoal, sample a few subgoals and somehow aggregate the low-level policy predictions to reach any of them?\n\nWhy are the proposed rewards sound? Without any justification, they look quite arbitrary.\n\nAre there any implicit properties of the abstractions that you learn? In the experiments, they seem to be always box-shaped and disjoint, is it always the case?\n\nIs the splitting operation the only way to refine the abstraction? Can you also incorporate the join operation if the abstractions are too fine? Is being too fine a problem in any case? Is $\\mathcal N=(x\\mapsto \\\\\\{x\\\\\\})$ always a good abstraction?\n\nHow do you handle the initial stage, when hardly any subgoal is reachable (because the agent can barely move)? Is there a danger that it will shatter the goal space arbitrarily before becoming capable of acting?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The high-level idea of the algorithm is presented clearly, which makes the paper easier to follow. The theoretical results are coupled with their intuitive description, which despite the complex notation makes them easier to understand.", "weaknesses": "I doubt that the presented results are practical. My main concern is that the _Approximating the reachability property_ step seems very costly. It's a pity that the authors didn't describe this essential part in more detail, leaving only the reference to other papers (are they published anyway?). Furthermore, how do you estimate the reachability for _all states_, provided that the state space is continuous? And I think that the reachability approximation model should be analyzed as well.\n\nThe practicality issues could be addressed by adding a wall-time comparison between the presented methods. An additional discussion on the compute utilization would do as well.\n\nI acknowledge the theoretical results, although I think that Section 4 can be restructured to be more interesting to the reader. The crucial element of this analysis is clearly Theorem 2. I suggest giving it more space and discussion. I suggest moving Theorem 1 and Lemma 1 to the appendix, as they serve only as a tool for proving Theorem 2 (as long as they are not referenced in the experiments). I would like to read here a discussion of the importance of Theorem 2, including: why does it make your method sound (recalling that you prove there exist _some refinements_, not necessarily the one you actually do in the algorithm, right?) and why it is not trivial to construct such an abstraction (e.g. by partitioning the space into any $\\varepsilon$-diameter sets).\n\nOverall, the paper lacks quite a few details, which makes it hard to understand the contribution. Since the full algorithm consists of many parts, it should be described much more clearly, not only the high-level idea. I suppose that addressing my concerns and questions should help.\n\nI am willing to increase my rating if my concerns are addressed.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)