Learning State Reachability as a Graph in Translation Invariant Goal-based Reinforcement Learning Tasks
Authors: Hedwin BONNAVAUD
Alexandre Albore
Emmanuel Rachelson
Venue: Accepted by TMLR ()

Abstract: Deep Reinforcement Learning proved efficient at learning universal control policies when the goal state is close enough to the starting state, or when the value function features few discontinuities. 
But reaching goals that require long action sequences in complex environments remains difficult. 
Drawing inspiration from the cognitive process which reuses learned atomic skills in a global planning procedure, we propose an algorithm which encodes reachability between abstract goals as a graph, and produces plans in this goal space.
Transitions between goals rely on the exploitation of a learned policy which enjoys a property we call \emph{translation invariant local optimality}, which encodes the intuition that goal-reaching skills can be reused throughout the state space.
Overall, our contribution permits solving large and difficult navigation tasks, outperforming related methods from the literature.

Published in Transactions on Machine Learning Research (/)
Learning State Reachability as a Graph in Translation Invari- ant Goal-based Reinforcement Learning Tasks
Hedwin Bonnavaud
ISAE-SUPAERO & ONERA/DTIS, Université de Toulouse, France
Alexandre Albore
alerandre.allorreSoeeee
ONERA/DTIS, Université de Toulouse, France
Emmanuel Rachelson
ISAE-SUPAERO, Université de Toulouse, France
Reviewed on OpenReview:
Abstract
Deep Reinforcement Learning proved efficient at learning universal control policies when the goal state is close enough to the starting state, or when the value function features few discontinuities. But reaching goals that roquire long action sequences in complex environ- ments remains difficult. Drawing inspiration from the cognitive process which reuses learned atomic skills in global planning procedure, we propose algorithm which encodes reach- ability between abstract goals as a graph, and produces plans in this goal space. Transitions between goals rely on the exploitation of a learned policy which enjoys a property we call translation invoriant local oplimalily, which encodes the intuition that goal-reaching skills can be reused throughout the state space. Overall, our contribution permits solving large and difficult navigation tasks, outperforming related methods from the literature.
1 Introduction
Model-free Reinforcement Learning (RL) has demonstrated an outstanding ability learn complex optimal policies from raw interaction data, for well-defined atomic tasks involving relatively short time and state space outreach, such as balancing pendulum (Barto al., 1983), learning to walk for quadruped (Kimura et al. 2002), or learning to balance bicycle (Randløv & Alstrom 1998).
But when it comes to solving more structured, long-term tasks, such as navigating through a building or a maze, baking a cake, or assembling furniture, hicrarchical methods that scparate global planning and local learned controllers may appear more appropriate (Eysenbach et al. 2019 Levy el al. 2019 lchter el. al. 2020). It is notable that often (although not always), atomic tasks enjoy a property which we call translational invariance, ie. learned policies can be re-used in unexplored states, without further computation, to reach local goals. Balancing bicycle, for instance, implies in practice optimal policy that recommends the same sequences of actions regardless of the geographical position, mostly because gravity does not change too much across the globe and that we ride bicycles on surfaces that have close enough friction properties. Similarly, when navigating in reasonably homogeneous environment, reaching position B from position A, can be achieved by applying the same policy than reaching position + A from position A + A, provided there are no obstacles the way. The optimal policies might somchow differ, but are close enough in many practical cases. In this paper, we consider enviromments which enjoy this translational invariance property for local, atomic goal-reaching tasks. In such tasks, this invariance property enables pre-training action primitives under the form of local goal-reaching policies, and then transferring and composing them to solve
Code: http:///gthaabccomm////ii//////p

---

Published in Transactions on Machine Learning Research (/)
complex tasks. The typical example of such environments is navigation tasks, upon which we focus in this work. Nonetheless, the framework we propose is more abstract and is designed to generalize to all cases of translational invariance. We exploit this property to efficiently learn an abstract model that is used by the agent to plan its course of action. Our contribution threefold.
We propose generic framework linking goal spaces and state spaces for goal-reaching policy opti- mization.
We formalize the notion of re-usability of a goal-reaching policy throughout the state space one of translation invariance.
We propose a complete graph-based model learning method, which relies on planning in the goal space, and chains local application of translation invariant goal-reaching policies. By combining planning and RL, this method permits solving tasks over long horizons, a common pitfall for classical RL methods.
As such, the proposed algorithm owes to several different inspirations. First, it belongs to the family of goal- based RL methods. Since it couples planning and RL, it also connects with hierarchical RL. It also abstracts navigation problems into more generic class of sequential decision problems. Finally, presents many similarities with the Search on the Reploy Buffer (SoRB) algorithm (Lysenbach et al.) 2019) and subsequent works, with several key differences which can be seen generalization of SoRB and permit better applicability. Section 2 sets the necessary background and puts our contribution in perspective of the current related literature. Section B introducess key ingredients, namely a formal definition of goals as state abstractions, a characterization of policy translation invariance, and finally the reachability graph learning (RGL) procedure. Sections components, discusses its properties and its ability scale up to large and difficult domains. Finally, Section we draw some conclusions and perspectives on the presented work.
and e evaluate RGL empirically, assess the contributions of its different
2 Background and related work
Goals in Reinforcement Learning (RL). RI. (Sutonn& & Barto 2018) considers the problem of learning an optimal decision making policy for an agent intcracting over multiple time steps with a dynamic environment, modeled as a Markov Decision Process (Puterman 2014) of unknown transition and reward models. At each time step, the agent and the environment are described through a state s e S. When an action a E is performed, the system transitions to new state s', while receiving reward r(s, a). Stochastic Shortest Path problems are particular class of MDPs which aim at reaching a terminal goal state as quickly possible. Such problems can be encoded as MDPs featuring -1 rewards for all transitions but those to a terminal goal state. One can quantify the efficiency of a policy : S + A in every state s E S via its value function (*) = Ei y'r (st, (s:)), with y E [0, 1) a discount factor on future rewards (which can also be interpreted as a stepwise probability of non-terminationn H Training an RL agent consists of finding a policy with the highest possible value function. A long-standing goal in RL is to design multi purtiis agents, able to achieve various goals through a single goal-conditioned policy ((8,g) (Kaelbling) 1993), where the goal 9 is either single state in S or abstraction for set of states. The ability of deep neural networks to approximate complex functions has triggered renewal of interest in learning universal value function and policy approximators (Schaul et al.) 2015). V(s,g) and ((s,0) g) respectively. Among the many approaches developed to learn goal-based policies and value functions, Hindsight Experience Replay (Andrychowicz et al.) 2017 HER) proposes a seminal method which defines goal-based reward functions by re-labelling states collected past. trajectorics as goals.
Hierarchical R.L (HRL). Combining local goal-reaching sequences of actions in order to achieve a more general goal is the core idea of HRL (Sutton al. 1999 Precup 2000 Konidaris & Barto 2009). Notably, among recent works, Kulkarni et al. (2016) define bi-level hicrarchical policy, using DQN MMnih et al.
SSPs well-defined for 7 = but this is not the case for all MDPs so keep this discount factor for the sake of genericity in further developments.
2

---

Published in Transactions on Machine Learning Research (/)
2015) agent to select high-level goals, that define options which make use of a low-level goal-based DQN agent. Nachum et al. (2018) specializes this idea to the case when the lower-level policy learns to achieve goals that encode relative changes to the current state. Levy et al. (201)) couples HER with three-level hicrarchy into an architecture called Hicrarchical Actor-Critic (HAC).
Learning abstract representations for planning. An alternative to crafting a hierarchy of learned policies is to rely on RL for producing "lower level" option policies, and on some model of how these options affect the environment. The aim is then to optimize sequence of options, skills, which are abstraction of actions, in global plan, defined for abstraction of states (which can either be learned or can be defined by the goal space). The key to such approaches hence relies on how the model is built. [Silver et al. (2017) train a "predictron" which, for a given lask, predicts n-step returns and long term values from any state, using a network that builds a consistent internal representation (the state abstraction) of the environment' 's dynamics and rewards. Similarly, several approaches (Ha & Schmidhuber 2018 Schrittwicser et al.; 2020; Hafner et al.) 2020 2021) build models that emulate the dynamics and rewards related to a task, and permit planning by simulating this surrogate model, but without. a hierarchy of options and for a single task. In contrast, Nasiriany et al. (2019) optimize sequence of reachable intermediate goal states (represented in the latent space of a variational auto-encoder on states) in order to reach a final goal (single task), using pre- computed reachability metric for a given goal- lower-level policy. Parascandolo et al. (2020) optimize online a similar curriculum of subgoals between a starting state and a given goal. They implement a divide- and-conquer approach by building an AND/OR search tree. Each node corresponds to a new subgoal in the sequence. They explore this tree with Monte Carlo tree search strategy, which exploits the value function of a pre-trained goal-based policy. Some methods store explicitly these links between subgoals by constructing rcachability graph (which encodes transitions between abstractions of states, using abstractions of actions). In lurn, this graph can be used for higher-level goal-based planning. [Savinov et al. (2018) build this graph by randomly exploring the environment, and add node for every encountered state, which yields a very dense graph. For a given goal, a shortest path in this graph is computed. Then a sequence of landmark subgoals is extracted so that each landmark is far enough from the previous one according to a pre-trained neural network. Eysenbach et al. (2019) introduce Search on the Replay Buffer (SoRB), which supposes the availability of replay buffer of states and defines a graph where each state in a random subset of the replay buffer is node. Then it uses the goal-reaching policy's value function to estimate edge weights between these nodes and finds shortest path of state waypoints to the goal. Huang et al. (2019) propose similar approach, but improve the node sampling strategy, and exploit a policy only to reach close goals during pre- treitraining. SGM (Emmons et al., 2020) improves SoRB's results by pruning useless nodes in the graph, and edges that cannot been traversed by the control policy. Pruning useless nodes enables a reduction in the number of graph edges and permits a faster convergence to a close-to-optimal graph (ie. representative of actual reachability with a minimal number of nodes and edges). [haplot al. (2020) learn a reachability graph in robotics navigation environment. For cach new location in its graph, the agent uses its camera to estimate promising exploration directions. Aubret et al. (2021) and Ruan et al. 2022 incrementally grow a graph representing reachability, where nodes are abstractions of sets of states, using neural network as a surrogate of the similarity between states. Similarly to the work of Aubret et al.] (2021), PALMER (Beker et al. 2022)
learns a projection space where the distance between the embeddings of two states represents the number of actions required by an optimal policy to reach one from the other. DADS (Sharma et al., 2019) learns a set of diverse skills, and a higher-level policy to decide the sequence of skills that have to be exccuted to reach a distant goal. DSG (Bagaria et al. p021p incrementally grows graph of options, represented as local finite set of goal-reaching skills in each node. The present contribution uses the goal space state abstraction, and maaslation-invarian pre-trained policies as action abstractions to enable planning in graph of goals.
Re-using policies across states / Connection with navigation tasks. Learning policies locally to re-use them in unexplored states has also been investigated to enable hierarchical RL. Konidaris & Barto (2007) propose to perform skill chaining on skills that are dependent on an discrete set of abstract agent contexts. These skills become reusable across contexts, but the definition of the contexts are specific to the task to solve and cannot be fully assimilated to an abstraction of navigation waypoints. PRM-RI. (Faust) et al.] 2018) and RL-RRT (Chiang et al.) 2019 build re-usable goal-condiitoned policy, and use it to navigate through a graph built using respectively PRM (Kavraki et al.) 1996) and RRT (La 1998)
3

---

Published in Transactions on Machine Learning Research (/)
hence providing an abstraction of navigation features into a more general framework. Note however that none of these methods provide a generic and formal definition of policy re-useablity.
Originality of the present work. With respect to this general body of work, our contribution has several key features. We formalize a set of necessary conditions defining a context which alleviates the need to train the lower-level goal-conditioned policy on all states and goals, and enables policy re-use. Similarly to SoRB, we exploit the policy's value function as a local reachability measure, while introducing a level of abstraction since we clearly distinguish between goals and states. Similarly to DSG, we incrementally explore the environment and build planning graph for chaining local skills, but the pre-training, exploration and graph growth strategies are different (expanded discussion in Appendix this provides a spanser, abstract planning graph, closer to a hierarchy of options. Also in contrast to SoRB and SGM, we do not rely on a pre-existing replay buffer and avoid defining nodes over an arbitrary subset of sampled states; instead we incrementally grow reachability graph to cover the attainable goal space.
D.. As developed in the next sections,
3 Learning a reachability graph to chain translation invariant local policies
We aim to solve large goal-based MDPs, requiring long sequences of actions, and where locally trained policies can be re-used throughout the state space. The rationale for the method we propose below goes as follows. Because they are continuous universal approximators, neural networks are intrinsically unsuited to approximate abrupt environment of skill changes, and discontinuous functions such as the value func- tions arising in some difficult RL environments (e.g. mazes, non-holonomous robots, etc.). For instance, in mazes featuring thin walls, the value function is discontimuous and approximating it with a neural network propagates values through the walls which can lead to catastrophically bad greedy policies. Because neural network optimization assumes that samples are obtained independently and identically from a stationary dist distribution, they are also unsuited to retain local information: either because the dist.ribution (and hence the training set) is unbalanced or because of distributional shift which causes catastrophic forgetting (French) 1999 Kirkpatrick et al. 2017 The sequential nature of RL decisions makes it crucial to make good deci- sions in dnfrequuently-visiteee states, to retain local information even when facing distributional shift, and to approximate some functions that can casily be discontinuous. Neural networks are a viable policy class for low-level policies and that it may be advantageous to add additional known structure to the problem setting (which can be learned) rather than attempting to learn a complete world model with no additional assump- tions which may require high sample-complextty Elaborating on this statement, we turn to a hierarchy of approximators, coupling planning graph of goal space waypoints, with local goal-rcaching skills Icarned with deep neural networks. When we would like to reach a goal g" G from a state so E S, we link g and so to their closest graph nodes. Specifically, we find vertices o* and vo whose waypoints g.- and gea minimize some measure of proximity d(g", ..w-) and (s)) gt.) respectively, with ((o)) an abstraction of so in the goal space. Then we find a shortest path between them in the graph, which defines an erecution curriculum of waypoints, and the local policy is used to reach each waypoint's 's vicinity in sequence.
The core of our contribution lies hence in the graph expansion and pruning method, its ability to accurately represent an abstraction of the environment dynamics despite unbalanced samples and discontinuous prop- erties, and finally its use to design goal-conditioned policies over large and complex state spaces. To present the method in well-defined framework, we restrict the set of MDPs we consider to those enjoying prop- erly we call tvanslation invariance of local optimal policies which we discuss in section 3.2 We also discuss therein to what extent this assumption is a strong constraint and how it can be related to more general transformations than translations. Then, given such a generalist goal-reaching policy n, we grow and prunc a graph g which encodes an abstract notion of reachability and distance over the state space (Section 3.3 The pair (T. 9) can then be used jointly to encode a policy that benefits from the best of both worlds and allows one to exploit planning algorithms over & in order to define an erecution curriculum of waypoints for m; resulting in global agent that can reliably learn to reach distant goals in complex environments.
3.1 Goals as state abstractions
In the general sense, goal g is an abstraction for a set of states. For instance, a goal for a robotic ant might be "reach this room, regardless of orientation, legs configuration, or precise final position". In this
4

---

Published in Transactions on Machine Learning Research (/)
section, for the sake of genericity, we assume that goals live in goal space G, that both S and G are normed vector spaces, and that there exists a projection (s) = g which projects states into the (lower dimensional) goal space 2 Consequently, for any goal there exists a set of states which map to g. Formally, we can define Ko = ker (P)) as the set of states corresponding to the null goal 0g E G. Conversely, there is an inverse function (possibly non-unique) that provides a prolotype state for any goal g. Let P be a mapping from goals to states such that e o P is the identity function on G. There are many possible such mappings if the dimension of G is smaller than that of S. Conversely, when dim(C) dim(S), one can take " although in this case it is practical to straightforwardly identify goals and states, which means S and L are the identity function. When S and G' differ, we assume such a P mapping is provided. Then, Kg { (g) 66 8 E Ko} is the set of states whose projection by P is g- In what follows, we retain the @ and S0 notations for genericity, but the reader is encouraged to discard them as the identity function in order to catch the key intuitions. Finally, when the goal and state spaces differ, we introduce the strong assumption that for a given goal g E G, any 82 E K2 is reachable for negligible cost from any other 81 E Kg. In plain words, moving between any two states which correspond to the same goal (same state a abstraction) is supposed feasible and costless. Note that this is immediately verified when S=
are
3.2 Translation invariance of local optimal policies: re-using macro-actions across all states
Intuition indicates that four-legged robot should not have to learn to walk again when it is moved from a room of the lab to another. We formalize this notion of ro-usability of learned policics one of translational invariance P We say an MDP admits translation invariant local optinal policies (TILO policies) if there exists goal-conditioned optimal policy x' such that
V(s ESE x p E IR, such that Vg E (B()))))), = x-
(8)),
(1)
where (s) is ball, centered in ((s) and of radius p. In plain words, such a policy guarantees that whichever close enough starting states and 8 + 8 we consider, we can always find local goals g and 9 + (6) within a distance of (s), for which the first action recommended by the policy will be the same. A corollary of this property is that in deterministic MDPs, all actions taken to reach g from s are the same as those necessary to reach 9 (5) from s + 5, for goals that are close enough to (s). TILO policies can be trained to reach goals from any starting state, and the TILO property enables their re- usability throughout the state space to reach local goals (which marks a notable difference with the relative goal policies introduced by Nachum el al. (2018) among others). Note that considering only (ranslation invariance is somehow restrictive as one could wish to identify invariances to other transformations (e.g. deformations on images, rotations, etc.) or the more general case of oquivariance (Van der Pol ct al. 2020 Mondal el al.; 2022 Wang et al. 2022) which is a challenge in itself (Konidaris & BBrrt 2007 Faust el al. 2018 Chiang et al. 2019) and which we reserve for future work. Appendix E discusses such a generalization.
Arguably, MDPs that admit TILO policies do not represent the full span of MDPs. However we argue that with an appropriate choice of the metric on G, defining (( p); this property actually applies to many common control problems where the goal space supports an addition operation. Moreover, one can extend the reasoning to e-optimal policies, hence defining e-TILO policies. An MDP admits e-TILO policies if there exists a policy that is e-optimal and obeys equation been trained on the lab's concrete grounds, to some other surface, it is reasonable to assume its translated goal-conditioned policy will not be optimal anymore. However, this policy is still likely to perform better than most other policies and hence to be e-TILO.
! When one takes the four-legged robot that has only
The method we develop herein applies to MDPs which admit e-TILO policies that are pre-trained. Practi- cally, given a starting state s, we directly train a translation invariant goal-conditioned policy T(s,g). To enforce the TILO properly, we actually train the policy as a function of the difference g-8 (or (gg) when G Training of this policy is done before directed exploration and graph learning takes place. We also define a goal-proximitt quasi-metric d (g. g') = (Vmaz - V* (g). g')) - Vmann, indicating how close two goals are under policy τ, with Vmaz and Vnin chosen so that, on the training domain, d= (g.g') [0.1]
2Section 4 will relax the vector space requirement on S and G. 3 "Appendxx D discusses generalization to other transformations.
5

---

Published in Transactions on Machine Learning Research (/)
and df (g. = O. This quasi-metric d" g') can be interpreted as measure of how long it takes for policy a to reach Kg from Kg on average. The goal-conditioned policy training method is any algorithm that trains a universal value function approximator; it trains 7(s,g) and (* within a playground task with no obstacles. For instance, starting with a random exploration strategy, a replay buffer is filled by interaction samples in the playground environement, and the goal-conditioned policy is trained to reach goals sampled from this buffer, using HER. This yields a (s,.g) policy that is also an c-TILO policy, along with the cor- responding dt (g. quasi-metric. We emphasize that this policy is not required to be able reach any possible goal from 8, even in the playground environment (Levy al. (2019) and Nachum et al. (2018) have illustrated how RL algorithms struggle when the goals become too distant). Instead, its performance and goal outreach is as good as the training procedure can make it, and we rely on the graph learning procedure to encode the reachability between states, based on this policy.
This idea of pre-training a policy a playground task meets the intuition of policy transfer in life-long RL. The playground stands for the previous MDPs seen in an agent's life, and the TILO property captures the idea that translation invariance is an abstraction that enables transfer between MDPs. In turn, goal-reaching policies trained in the playground stand as generic action primitives, which are then composed hierarchically when solving a new, complex task.
3.3 Learning reachability topology
Algorithm 1: Reachability graph learning (RGL)
Input: n, d=, Treachh Thode: Redges Tr, Te
Initialize: V =0 0. E
repeat.
22 Function growGraph( (V, F,, (seloE(u.1.)):
8g = env init()
23 for t E T2] do
9o goal associated to closest node to (so)
24
addNode = True, Ein Eout = 0, = aode(.9(s))
if d 9 (so), go) > Nedge V V = 0 then
7
V - V ( (s)))
25
for E V do
8
9o = (sp)
26
In = d (goo Lout = (gm:: 9v)
v' = seleettipploratiinnooelll.l
27
10
(v)).e(o.11 = shortestPath(
(lt)ep/mmmmsoottsssstttt....... E, E. )*)
28
if Ln S. Mmode A lout S Mmode then L addNode = False; break
11
8 == 80, t=
29
12
for i e [1, H|] do
30
if lin S Vedge then
13
while -reached(s, v)) At T, do env etv. n 9v:))
31
Ei Ein U fedge(e, w)} setWeight( (reigghttFfnneF U, w. 4m)
14
15
t
33
if loat &Mdgge then
16
if rreahhed(s s, u) then
Eout + Eous U (edge(w, u)} setWeight (Eout, w, v, lout)
17
setWeight 8- U/ +00) break
18
if addNode= True Em # then 38
19
if reached(s, (s, v*) H then {st)EE(L.T.) explore(s, Te) EV, = growGraph (V, fs hel..)))
37
V - (w),, E EU Ein U Bout
20
38 return V, E
21
To ease the presentation of ideas, we present the proposed Reachability Graph Learning algorithm (RGL, Algorithm D in the context of deterministic MDPs, and defer the discussion of the stochastic case to the end of this section. Given pre-trained e- T-IOO policy т, we wish to construct an oriented graph g = (V, E) which will represent. the reachability between sub-goals, using т. Each vertex v E V of such a graph is associated with a given goal gv, and directed edges e E E indicate reachability the successor node's goal from the states corresponding to the source node's goal. In other words, if an edge exists between v and w, then π successfully reaches Iw from states in K, Kg.. The edge linking e and w is weighted with traversal cost of d= (gv. Iw). Knowledge of this weighted graph permits running a planning algorithm to

---

Published in Transactions on Machine Learning Research (/)
find an execution curriculum of waypoint vertices (intermediate goals go) which eventually link any start state and final goal. This is very similar in spirit to SoRB (although our graph is defined on goals, not states). The (other) key difference lies in the fact that graph nodes are not built on an arbitrary set of sampled states, which might be rather sensitive to the distribution of these sampled states, and graph edges do not rely solely on evaluating the policy's 's value function, which might poorly account for discontinuities (walls) or rarely visited states. Instead we grow and prune the graph dynamically so that it actually encodes reachability between goals, which is a major difference with most other methods in the literature.
Path planning in G. During an iteration of the RGL procedure, a starting state so is first sampled from an initial state distribution. Note that RGL does not suppose fixed starting state. If so is the first sampled starting state ever, or if the closest goal to (sn) lies far from (50) in the goal space, this means 8o does not correspond to any previously explored goal and we add a node in the graph at (so). Then, a node o² in the graph is selected for exploration. This selection relies on a count-based criterion which influences the progressive coverage of the goal space. Although one could design heuristics or refined exploration strategies (Bellemare et. al. 2016; Ecolfet et al., 2019 Badia et al. 2019 Burda al.] 2019 Domingues rely on simple count of the number of times node has been selected
le al. 2021 for this criterion, for exploration, hence promoting uniform visits to every node in the graph. A finite horizon plan (1:)ie(o.H) is computed by finding a shortest path in the graph from the starting state's node to to the selected node v* = -uH- Note that there may not exist a path between up and v* in the graph, in which case H = 0 and the shortestPath procedure returns the single node {vo}. Let (gi)sejo.H)) denote the corresponding sequence of waypoint subgoals. Then is used to sequentially reach each goal. Specifically, when trying to reach Iv: (e) is run until reached (s, v) == [dx (P)), ge) S TTracc)] condition becomes true, a maximum number of steps T₃ is exceeded. If applying æ allowed the agent to reach the Trreack nreuhb--egghboohood of gv. then the next waypoint w in the plan is selected and the procedure is repeated until the node of is reached.
Graph pruning. We interpret not reaching the neighborhood of gu when applying as a mismatch between the notion of reachability encoded in the graph and the actual reachability in the environment using я. As a consequence, we set the cost of edge e bet v and w to +oo to account for this non-reachability. Consequently, if the graph is learned without errors, the existence of an edge e between two nodes v and w indicates that permits reaching the Preack-ncighborhood of INe from states s whose (s) are in the Treack- neighbooodd of ge in less than T, time steps (or that this edge is never selected by the shortest path planning procedure). This pruning procedure keeps the graph free of mis-identified edges. In mazes, it deletes edges that cross walls, and hence accounts for the discontinuities we wished to represent within the policy.
Graph expansion. Conversely, if applying x throughout the sequence of waypoints actually fulfills the goal g" of node v" selected for exploration, then a generic exploration procedure is performed from the reached state s" in the Mreack neighborood of K,+, during T, time steps. The intention of such an exploration procedure is to discover states s whose (s)) permit expansion of the graph. We randomly sample goal within a certain radius of g" and try to reach it using и. If we succeed, we sample another random goal and repeat this exploration until we obtain a complete exploration trajectory of length Te. Note that this exploration strategy could be replaced by any other, which is why we refer to it generically as the explore procedure in Algorithm [ The states visited along the trajectory are collected in a buffer. We wish to expand the graph so that its nodes induce a good coverage of the buffer states' goals and its edges indicate proximity (but. not necessarily reachability at this stage). To that end, we cycle through the buffer and incrementally add vertices to V whenever a goal is -urftrr away from all nodes than threshold Toode. Edges are created from this new vertex to all nodes within Medge > mmode- We differentiate between incoming and outgoing edges from the new candidate node: if there is no incoming edge, then the node is not added to the graph. This greedy procedure expands the graph to create new nodes that complete the goal space coverage wherever required, with limited connectivity between nodes. At this stage, some newly created odges might not account for reachability, e.g. in a maze, this might happen if the closest existing graph node to the newly created node is behind wall. We rely on future iterations to prune the graph presented in the previous paragraph.

---

Published in Transactions on Machine Learning Research (/)
Overall, this growth and pruning RGL procedure results in graph 9 = EV which encodes goal space reachability when using in the state space. The pair (G, 1) implicitly defines general goal-reaching policy which requires computing a shortest path in G to chain local executions of т between subgoals.
Time complexities during learning. At execution time, determining the action to undertake in s in order to reach 9 requires solving a shortest path problem in g. This can be typically implemented using Dijkstra's algorithm (Dijkstral 1959), which has complexity O log V It is important to note however that in deterministic MDPs (or MDPs with limited noise) this shortest path needs only be computed once per goal-reaching task and can be carried over to the next time step of the task, thus strongly dampening the overall computational cost. During learning, the pruning phase of an itcration of RGL has complexity OEE + V (log V + T.)). The exploratory collection of new samples runs in O(Te), while the growGraph function has complexity V) This results in an overall time complexity of OEE + (loo V + +T, Te)) for each iteration of RGL, which involves O(VT, + Te) iteration steps with the environment.
In the general case of MDPs with stochastic transitions, the pruning procedure of RGL needs to be adapted to account for the stochastic outcomes when trying to reach g' from Kg. Note that, in this case, d' (g.gg')) captures a broader notion than the number of required time steps for to reach g' from gi it captures the overall probability to reach g' from Kg, given the transition model and probability of termination of 1 - at each time step. Thus, reachability can be redefined as the probability of reaching g from Kg being actually equal (or close to) d') Verifying this with high confidence requires running several trials between Kg and g', which can be implemented by enhancing the algorithm with a memory of trial outcomes for each edge in the graph. Introducing such delay in updates is similar in spirit to the practice of RMAX (Brafiman & Tennenholtz) 2002) or Delayed Q-learning (Strehl et al., 2006), which introduce an Nanown number of samples which are necessary to correctly identify transition. Note that in most practical implementations of such algorithms, Nanown is arbitrarily set to a small value to preserve computational efficiency. An alternative, which we do not explore here and reserve for future work, is to let the weight of an edge adapt to the observed trial durations between g and g'.
4 Experimental setup
To highlight the behavior of RGL, and provide fair and interpretable benchmark against comparable methods, we consider a set of navigation tasks in mazes, including a high-dimensional state space one.
Environments. In each maze, an agent should be able to reach any goal position from its starting point. Hence the goal space G is always the 2-dimensional set of positions in the maze. We consider mazes of different complexities, with various map sizes and heterogeneous corridor widths, as illustrated in Figure [ Namely, "four-rooms" is 41 41-size maze resembling the classical "four-rooms" benchmark, "medium" is more challenging maze of the same size, "hard" is an even more challenging 57 x 57-size maze and "mixed" has the same size as "hard" and mixes corridors and rooms of different sizes. Note that compared to mazes used in the literature (e.g. those of Eysenbach et al. (2019)), here the walls are thin, inducing sharper discontinuitess in the value function across a wall. For each map, we consider three different dynamics and state spaces for the navigating agent, which we refer to as grid-maze, point-maze and ant-maze (Table D. Grid-maze fcatures a discrete (N, E, W} action space and deterministic transitions which perform unit- length moves, hence emulating navigation on grid. Point-maze emulates a point mass moving freely in the maze. It has continuous, wwo-dimensional action space of position increments in [-1,1] on the and y axes. The transitions are stochastic due to an added Gaussian noise (0, Contrarily to grid-maze which has a fixed starting state, point-maze moint-maze randomly draws the starting point at every episode. In grid-maze and point-maze environments, the state space is simply described by the geographical position of the agent, as in the benchmarks of SoRB (Eyenbbach et al., 2019) or SGM (Emmons et al. 2020), and S 5=6 G. Ant-maze environments build upon the MuJoCo Ant simulator (Todorov et al.] (012) and sets the ant in one of the navigation maps. Actions belong to the standard 8-dimensional action space of the Ant simulator, and the state space is the 29-dimensional space whose first two coordinates are the position of the ant's torso, in the benchmarks of HAC (evv et al. 2019 or Distop (Aubret et al.) 2021). The transitions follow the
For the sake simplicity we adopt the notation ((V) in place of O(IV)) This can be amortized to OTT log V) with efficient. data structures for storing and finding nearest neighhors.
8

---

Published in Transactions on Machine Learning Research (/)
Figure Mazes and starting points. From left to right: "four-rooms", "medium" (size 41 41), "hard", "mixed" (size 57 57).
dynamics of the Ant simulator. In ant-maze environments, the goal space G' describes only the torso's x and y coordinates. In environments, agents receive a -1 reward at each time step, unless they reach the goal which terminates the episode. In all evaluations, every agent independently trained 10 times. For the sake of reproducibility, the hyperparameters for all algorithms are summarized in Appendix A and our code and results are available at Janonymous URL].
Table 1: Summary of environments
dS
dim(G)
actions
starting state fixed single state uniform distribution S deterministic
dynamics
grid-maze
2
discrete (number 4)
deterministic
point-maze
2
continuous (dim( A) = 2)
stochastic
ant-maze
29
continuous (dim(A) (A) = 8)
fixed single state
Baselines. To illustrate the behavior of RGL, we compare against a plain DQN agent (Mnih et al.) 2015) with HER in grid-maze environments, and SAC (Haarnoja et al.] 2018) with HER in point-maze and ant- maze environments. As illustrated by previous works (Nachum et al. 2018 Levy et al., 2019), such a combination can efficiently learn goal-reaching policy for goals lying a few actions away from the starting state, but struggles to reach goals that require turning around walls. These DQN+HER and SAC+HER agents provide a baseline for performance. Another bascline consists in passing the policy learned by these base agents, along with their final replay buffer, SoRB, to extend their outreach throughout the goal space via planning in a random subset of size No of the replay buffer. Since SGM is more efficient than SoRB (due to their pruning method), we directly compare with SGM 6
Ablations. We also implement three variants of RGL. The first one is called TC-RGT, inspired by the STC method [Ruan et al. 2022), where we replace the d= pscudo-metric by so-called temporal correlation network, which is an additional network trained to measure reachability between states, based on their temporal proximity during training trajectories. This variant permits evaluating the core feature STC as an alternative to using the value function as a reachability metric between goals. The second one is called Prune-only RGL (PO-RGL). This version samples n states from S using an oracle, and sets them as graph nodes. Edges computed in the same way than RGL. This algorithm does not need graph extension, and simply prunes the graph as it successively tries to reach random goals. Finally, NoPG-RGL (no playground) is an RGL agent whose lower-level policy has not been pre-trained in an obstacle-free playground but in the true maze, to illustrate the influence of playground environments on the pre-trained policy's 's quality.
Pretraining. First of all, it is important to note that only RGL can, by design, exploit a goal-rea policy which has not been trained on the actual full maze (further discussion in Appendix [ This enables training RGL's geal-reaching policy in a 40 x 40 playground environment with no walls which facilitates pre-training (training in the full maze, as done with NoPG-RGL, is still possible but totally unnecessary since RGL's goal-reaching policy needs only navigate to local goals). Such pre-training is not compatible with SGM or
Note that SoRB and SGM were introduced with tailor-ma made, goal-based, distributional DQN and DDPG agents. We found this necessary for finite-length trajectories and we retain the names even though slightly change the base agents.

---

Published in Transactions on Machine Learning Research (/)
SoRB. To ensure SGM builds sufficiently good pre-trained policy, and following the practice of SoRB, we let the base agent learn goal-reaching policy over 300 (resp. 500) episodes in grid-maze (resp. point-maze). RGL's lower level goal-reaching TILO policy is only trained for 100 (resp. 70) episodes in the playgrounds for grid-maze (resp. point-maze) environments. Because training the temporal consistency network of TC-RGL required more samples, was trained for 200 (resp. 600) episodes the playgrounds. Finally, NoPG-RGI, is trained for 150 episodes the true mazes both grid-maze and point-maze environments. To account for pre-training durations, all figures below (e.g. Figure 3) report them using vertical lines and count them within the total training time. Because ant-maze environments required specific pre-training, defer their discussion to the end of this section.
5 RGL in action
This section illustrates how RGL dynamically grows and prunes its graph, illustrates the comparative im- portance each part of the algorithm, and reports on ability reach far-standing goals.
Visualizing graph growth and pruning. We start assessing separately the influence of the growth and pruming procedures the properties of the final reachability graph. To isolate the effect of pruming, we artificially generate waypoints by using generative model to draw states from the full state space, which yields a graph with the same number of nodes Novit as the SGM agents (edges weights are also initialized with d"), but with better state space coverage since the drawn states are not constrained by the exploration DQN+HER agent. This graph is illustrated in Figures 2a and 2e for the "four-rooms" and
of the "hard" grid-mazes (full results Appendix B In Figure 2 red edges are those whose weights have been +oo by the pruning procedure. We observe that (as anticipated in Section 3 only erroneous edges which were selected in shortest path pruned, and some remain in the graph, especially in grid-maze, which features fixed unique starting state. This bears little consequences in terms of goal reachability since these are never selected in shortest paths from the initial state, but still result in rather dense reachability graph. Conversely, Figures 2d and 2h illustrate the graph growth and the pruning for RGL in the same enviromment after respectively 1,000, 40,000 and 270,000 interaction steps. To avoid misinterpretations, it is important note that since the graph is oriented, each green edge these figures actually stands for two edges in the graph. If only has been pruned and rendering of the other happens afterwards, the segment appears green while only edge in the graph has non-infinite weight. Overall, the incremental growth of RGL's graph yields efficient coverage of the state space, avoiding the clusters of unnecessary nodes of Figures
2a and
2e and reducing the need for pruning.
(a) PO-RGL, 400 nodes
(b) RGL, t= 1,000
(c) RGL, 40,000
(d) RGL, 100,000
(c) PO-RGL, 600 nodes
(0) RGL, = 1,000
(g) RGL, 8 40,000
(h) RGL, 150,000
Figure 2: Reachability graphs.
10

---

Published in Transactions on Machine Learning Research (/)
RGL agents can reach any goal. Figure 3 reports the ability of each agent to reach any goal in the maze, along training. The vertical lines correspond to the time at which each agent starts exploiting the pre-trained policy. Every 1,000 interactions with the environment, we randomly draw 30 goals across the full goal space, and report the fraction of these goals the agent managed to reach. We call this metric the agent's accuracy. As expected, since exploration in mazes is difficult, the pre-training replay bullers do not cover the full state space and the basclines fail to reach all goals. Interestingly, despite the low performance of the pre-trained DQN+HER and SAC+HER agents, RGL is still able to leverage their ability to reach local goals and manages to quickly grow goal graph which eventually covers the full maze. NoPG-RGL, despite its pre-training in the actual maze, still manages to grow a relevant planning graph and outperform SGM. It is interesting to note that this pre-training still costs less than that of SGM in number of interactions. It also yields a local policy which is strongly biased by the obstacles around the starting states. The pre- training might have learned to avoid a specific wall close to the starting point, which hinders the ability of NoPG-RGL to reach waypoints and slows graph expansion. PO-RGL displays clear jumpstart effect in the "four-rooms" maze since its initial graph requires little pruning and most goals are readily reachable. Conversely, early planning graphs of RGL and TC-RGL contain few nodes and require expansion (and thus interaction steps) before their accuracy reaches 1. After 1,000 interactions, even though the planning graph of RGL contains only a few nodes (Figure 2bj, it already reaches more goals than the baseline agents. As the mazes become more difficult, many more edges need to be pruned from PO-RGL's initial graph before it effectively represents graph reachability and the plans reliably lead to goals. This need for extended pruming is completely compensated by the sparse growth of the graph of RGL and TC-RGL; thus PO-RGL presents no advantage in terms of learning curve. In the most difficult "hard" and "mixed" mazes, the set of Nonit initial nodes of PO-RGL is just insufficient to properly cover the full goal space with feasible edges and PO-RGL's 's accuracy is capped around 0.5 and 0.8, while the dynamic growth of RGL permits reaching close to accuracies. Also, the extra temporal consistency network of TC-RGL seems detrimental to the training process compared to RGL. Since this network only approximates the notion of reachability instead of directly using the value function, it induces a graph expansion and pruning phase with more crrors or missed nodes (which were actually reachable). In turn, as TC-RGL's 's graph does not accurately represent reachability, some goals are eventually missed, In all environments, RGL reaches an accuracy of 1 and dominates over all variants.
Four rooms
Medium
Hard
Mixed
accuracy over tests
1.0
1.0
1.0
0.8
0.8
0.8
0.6
0.6
0.6
RGL (ours)
NoPG-RGL
0.4
0.4
0.4
TC-RGL
PO
0.2
0.2
0.2
SGM
HER
0.0
2,5e4
Se4
7.5e4
1e5
Se4
le5
1.5e5
1e5 2c5
Se4
1e5
1.5e5
2e5
Figure 3: Accuracy for all agents on grid-maze environments, versus interaction steps. Take-aways: 1) RGL (all versions) consistently outperform the baselines, 2) the TC metric (TC-RGL) is detrimental to performance compared to the plain d" metric, 3) pre-training in the real maze (NoPG-RGL) can induce suboptimal local reaching behaviors which do not prevent overall coverage but limit performance, 4) online graph expansion is necessary (PO-RGL) as pre-sampled graph nodes do not match the environment's topology.
Graph size. Figures and report the number of nodes and edges for RGL agents their graph grows in the grid-maze environments. Recall that instead of deleting edges that need to be pruned, their traversal weights are set to +oo (to avoid re-crcating them again later). This is why the number of edges of PO- RGL does not decrease. Dotted curves in Figure 5 indicate the nunber of edges with a non-infinite weight. Overall, RGL and TC-RGL create just enough nodes to accurately represent the reachability graph given their underlying dF and temporal consistency networks. The relative number of nodes and edges between RGL and TC-RGL cannot be directly compared as the former uses d= as a distance metric while the latter uses reachability representation, on different (uncontrolled) scale. Still, the number of nodes is similar
11

---

Published in Transactions on Machine Learning Research (/)
Four rooms
Medium
Hard
Mixed
RGL (ours)
(.99().02)
0.98(0.03)
0.93(0.13)
0.97(0.03)
NoPG-RGL
0.86(0.26)
0.6(0.29)
0.7(0.22)
0.8(0.14)
TC-RGL
0.97(0.05)
0.97(0.03)
0.68(0.26)
0.56(0.22)
PO-RGL
(099().01)
0.96(0.05)
0.52(0.26)
0.77().27)
SGM
0.59(0.23)
0.28(0.07)
0.16(0.09)
(.259).09)
DQN + HER
0.4(0..3)
0.14(0.08)
0.06(0.05)
0.1
Table Final average score for each method (standard deviation parenthesis). Take-away: RGL statistically outperforms non-dynamic graph methods.
acTOSs mazes. Interestingly, RGL produces graphs with less connectivity, which can be interpreted as better ability to create meaningful connections between goal waypoints for navigation, and hence sparser abstract models for planning while retaining the useful information for plan efficiency. Additionally, TC-RGL features a large variance in the number of nodes and edges developed in the graph. This appears to stem from the training of the temporal consistency network which is very sensitive to the distribution of trajectories during pro-training. In turn, this strongly affects the estimation of reachability when learning the graph and induces this variance in graph density. Appendix F provides further discussion on the impact of the graph density's hyperparameters (Madde and Meddge) RGL's behavior.
Four rooms
Medium
Hard
Mixed
500
700
1000
modes in graph
400
600
400
800
300
400
nb nodes
200
200
300
400
RGL (ours)
200
100
NoPG-RGL RGL
100
200
TC-RGL
PO-RGL
2.5e4
7.5e4
1e5
1.5e5
1.5e5
Figure Number of graph nodes in grid-maze versus interaction steps. Shaded area the lo confidence interval.
Four rooms
Medium
Hard
Mixed
nb edges 10000 graph
RGL (ours)
40
20
NoPG-RGL
TC-RGL
12.5
PO-RO 30-RGL
30
10.0
7.5
20
2
5.0
10
0.0
2.544
Se4
7.5e4
1e5
Se4
le5
1.5e5
1e5
2c5
Se4
1e5
1.5e5
2e5
Figure Number of graph edges grid-maze versus interaction steps. Shaded area is the a confidence interval.
6 Scaling up RGL to more difficult environments
The previous section demonstrated the overall behavior of RGL and its ability to build a more relevant planning graph than similar methods. In this section, we consider additional challenges and evaluate RGL in other contexts. Namely, we explore how RGL. compares other approaches when the environment is not constrained to start the same states every time. We also evaluate how RGL can cope with stochastic transition dynamics. Finally, scale up RGL the large state space of MuJoCo's ant simulator and
12

---

Published in Transactions on Machine Learning Research (/)
demonstrate its behavior when the state space is much larger than the goal space, while comparing its behavior to state-of-the-arl competitors HAC (Levy et al. 2019) and DSG (Bagaria et al. 2021
Easier exploration in environments with the ability to "reset anywhere". Point-maze environments permit resetting the environment anywhere in the state space at the beginning of each episode, as in the benchmarks of (Eysenbach et al. (2019); Emmons al. (2020). This feature induces diversity in the replay buffers by triggering easier exploration of the state space, simply by enabling these random resets, and somehow departs from the more constrained RL framework with fixed (or limited set of) starting state(s). Consequently, these environments of the state space, and SGM performs better in these environments than in grid-maze ones. Figure O compares the behavior of all methods in the point-maze environments and illustrates how, even in this case, the graph growth of RGL eventually outperforms competing methods, as it dynamically and progressively discovers new goal waypoints to better map the state space.
more favourable to SGM since their replay buffer covers larger portion
Four rooms
Medium
Hard
Mixed
accuracy over tests
1.0
1.0
1.0
0.8
0.8
0.8-
0.6
0.6
0.6
RGL (eurs)
0.4
NoPG-RGL
0.4
0.4
TC-RGL
0.2
PO-RGL
0.2
0.2
0.0
SAC + HER
0.0
0.0
0.0
2,5e4
5e4
7,5e4
1e5
0
Se4
1e5
1.5e5
165
265
0
5e4
165
1.5e5
265
Figure 6: Accuracy for all agents point-maze environments, versus interaction steps. Take-away: the ability to reset anywhere during training strongly helps SGM's coverage by design, but the dynamic graph growth of RGL and its variants still enables more efficient overall goal-reaching behaviors.
Four rooms
Medium
Hard
Mixed
RGL (ours)
(091(
(.85()
0.77(0.2)
0.67(0.23)
NoPG-RGL
0.94(0.05)
0.87(0.05)
0.7(0.15)
(.61().15)
TC-RGL
0.82(0.17)
0.68(0.27)
0.54(0.31)
0.64(0.19)
PO-RGL
0.87(0.18)
0.7(0.18)
0.48(0.2)
0.64(0.17)
SGM
0.88(0.09)
0.79(0.13)
0.43(0.22)
0.34(0.13))
SAC HER
0.51(0.1)
0.23(0.06)
0.11(0.05)
0.11(0.05)
Table 3: Final average score for each method (standard deviation in parenthesis). Take-away: RGL statistically outperforms non-dynamic graph methods, and methods that are unable to expand their graph after pre-training.
Accommodating stochastic transition models. As mentioned in Section version is designed for deterministic dynamics and would require some adaptations to account for transition uncertainty. Point-maze environments feature rather high level of action noise (a 1 for action values in [],, This makes the pruning procedure stochastic, as it will prune out edges depending of single trial's success. Despite this rather naive behavior, RGL still manages to find paths (possibly sub-optimal) to goals and reaches a high level of accuracy (Figure 6) demonstrating a reasonable level of robustness to transition stochasticity.
3.3 RGL in its presented
Scaling-up to high-dimensional and large state spaces, where G o S: ant-maze tasks. A key achievement of deep RL is its ability to scale up to high-dimensional state spaces, either in continuous control (e.g. MuJoCo robotic environments) or in mmage-based tasks (e.g. video games). In this last part, we consider such environments, where RGL retains the same overall behavior, as its planning graph is defined over the goal state G and not the state space. The key challenge in these environments is therefore to derive a good lower-level goal-reaching control policy T(s,g), which is independent of the contribution of this paper and may require large engincering effort, unrelated to RGL itself. In other words, the lower level policy the Ant environment should learn to walk to any nearby position around its starting position, while RGL will enable it to navigate to distant positions in the maze.
13

---

Published in Transactions on Machine Learning Research (/)
Training universal local goal-reaching policy in ant-maze environments, even in obstacle-free playground, is already a challenging task. Appendix G expands on the pre-training procedure set in place to attain such a policy π gs, HAC is the reference method for ant-maze environments but, as discussed in Appendix H its efficiency appears brittle and despite our best efforts and the use of the original HAC implementation, could not solve any of the ant-maze lasks. Similarly, the more recent (and comparable to RGL. in spirit) DSG method reaches an extremely low accuracy, as reported in Figure and discussed in Appendix where
RGL eventually reaches very high levels of accuracy.
Four rooms
Medium
Hard
Mixed
1.0
1.0
0.8
accuracy over tests
0.8
0.8
0.6
RGL (ours)
0.6
0.6
HAC
0.4
0.4
DSG
0.4
0.4
0.0
0.0
0.0
0.0
265
4e5
6e5
265
4e5
6e5
Be5
1e6
Figure 7: RGL accuracy ant-mnaze lasks, as a function of training time steps. See Appendix H and for a detailed
discussion on HAC and DSG's low score.
Four rooms Medium
Hard
Mixed
RGL (ours) НAC
0.91().06) 0.0(0.01) 0.02(0.03)
0.86(0.06)
0.48(0.24) 0.06(0.05)
0.73().16) 0.06(0.05)
0.01() (.01()
DSG (Sparse rwd.)
0.01(..02)
0.0(0.0)
Table Final average score for each method (standard deviation parenthesis). Take-away: RGL statistically outperforms all baselines.
In comparison to the ant-maze environments used in Bagaria et al. (2021), the maps used here are larger. In turn, this makes reaching specific areas (goals) of the maze more difficult to reach. Besides, even when taking into account the pre-training time of RGL's lower-level policy, Figure 7 (and the original DSG paper) shows that DSG requires many more learning steps to correctly learn the individual options corresponding to the vertices in its planning graph. In contrast, RGL leverages the possibility to re-use the same TILO policy throughout the state space, and quickly grows the planning graph while leaving the lower-level policy unchanged after the first 20, 000 time steps. Additionally, DSG relics quite strongly on dense reward models for efficient training of options. The present environments avoid the (dense) reward shaping mechanism used in Bagaria et al. (2021) 's experiments, to avoid pre-training biases, which strongly penalizes DSG. Appendix test DSG in various Ant-Maze settings analyse the reasons of DSG under-performancee in the current context.
Finally, ant-maze tasks, on top of being highly challenging for the baseline agent, also violate the assumption of Section 3.1 that any two states within K, are reachable from each other for a negligible cost. For instance, some ant orientations, velocities and leg configurations are rather complex to reach from others. Consequently, an edge between 9 and g' RGL's graph only represents reachability of g' from a subset of states in Kg, which can lead plan failure (extended discussion in Appendix B) Despite this, RGL manages to achieve large values of accuracy almost. as high as those obtained on point-maze tasks on the "four-rooms", "medium" and "mixed" mazes. The most challenging setting remains the "hard" maze, which requires fine motor skills to efficiently navigate through narrow corridors and requires turning around many corners to navigate to far goals.
High-dimensional goal spaces. The question of scaling up RGL to large goal spaces arises naturally as a follow-up to the previous paragraphs. For instance, when extending RGL from navigation to manipulation tasks, goal space dimension might increase and RGL's graph growth will suffer from the curse of dimension- ality. This issue arises for all methods which design graph in goal space; for instance, SGM or SoRB will
14

---

Published in Transactions on Machine Learning Research (/)
face the same issue their state and goal spaces are identical. RGL's (slight) advantage here is precisely that the P projection enables building the graph in a lower-dinensional space than in the full state space, provided one could provide a suitable mapping for P. We reserve the automated discovery of P for future work as it is a distinct challenge in itself.
7 Conclusion
Efficient coupling of planning and learning in complex MDPs with temporally extended goals is an active field of research. In this work we defend the idea that efficient mechanisms rely on two implicit hypotheses: planning agents should plan in the goal space and learned policies often re-usable throughout the state space. We propose formal framework accounting for these two notions, defining goals as state abstractions, and casting re-usability as translation invariance. This permits deriving algorithm which performs plan- ning over a graph of goal waypoints, reachable by a lower level goal-reaching policy, This agent is named RGL (reachability graph learning) after its training mechanism, which incrementally explores its environ- ment using a pre-trained lower level translation invariant goal-reaching policy, expands and prunes a graph encoding goal reachability. This approach can be seen either as a more grounded version of STC (Ruan al., 2022), or a generalization of SoRB (Eysenbach al.) 2019) or SGM [Emmons et al. 2020) to a hierarchical sctting with translation invariance. Empirical evaluation confirms the relevance of RGL agents and their key features.
This contribution also forms a basis for future research directions. As is, RGL agents build a somewhat uniformly dense graph, as illustrated in Figure 2h This might not be necessary and further sparsity can be achieved in the open rooms of the "four-rooms" or the "mixed" environments. Similarly, weight learning in the graph is currently rather naive and could better exploit interaction data during exploration, in particular in stochastic environments. The influence of playground enviromments on the final policies is also an open question, which connects to lifelong RL and curriculum learning: can one design good playgrounds for pre- training, the same way we let kids learn generic skills from simple (playground) tasks before we encourage them to compose these solutions together?
Finally, RGL requires an e-TILO policy for agent control. Appendix D and propose a discussion on whether such policies are easy to obtain the general case, beyond navigation tasks. We conjecture such policies also cxist in more complex contexts, like vision-based navigation (PO)MDPs, such as those proposed by Kempka al.] (2016) or for real-life robots, since humans seem to exploit such invariances in daily life. Formalizing how these policies can be discovered and how their definition affects the properties derived in the present work is an exciting avenue for rescarch.
References
Marcin Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, OpenAl Pieter Abbeel, and Wojciech Zaremba. Hindsight experience replay. Advances in neural information processing systems, 30, 2017.
Giorgio Angelotti, Nicolas Drougard, and Caroline PC Chanel. Expert-guided symmetry detection in markov decision processes. In Proceedings of the 14th International Conference on Agents and Artificial Intelli- gence, 2022.
Arthur Aubret, Salima Hassas, et al. Distop: Discovering topological representation to learn diverse and rewarding skills. arXiv preprint or arXin:2106.0885x 2021.
Adrià Puigdomènech Badia, Pablo Sprechmann, Alex Vitvitskyi, Daniel Guo, Bilal Piot, Steven Kapturowski, Olivier Tieleman, Martin Arjovsky, Alexander Pritzel, Andrew Bolt, et al. Never give up: Learning directed exploration strategies. In International Conference on Learning Representations, 2019.
Akhil Bagaria and George Konidaris. Option discovery using deep skill chaining. In International Conference on Learning Representations, 2019.
15

---

Published in Transactions on Machine Learning Research (/)
Akhil Bagaria, Jason K Senthil, and George Konidaris. Skill discovery for exploration and planning using deep skill graphs. In International Conference on Machine Learning, pp. 521-531, PMT.R, 2021.
Andrew G Barto, Richard S Sutton, and Charles W Anderson. Neuronlike adaptive elements that can solve difficult learning control problems. IEEE transactions on systems, man, and cybernetics, 13(5):834 846, 1983.
Onur Beker, Mohammad Mohammadi, and Amir Zamir. Palmer: Perception-action loop with memory for long-horizon planning. arXiv preprinl 2iv: 04581, 2022.
Mare Bellemare, Sriram Srinivasan, Georg Ostrovski, Tom Schaul, David Saxton, and Remi Munos. Unifying count-based exploration and intrinsic motivation. Advances in newral information processing systems, 29, 2016.
Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston. Curriculum learning. In Interna- lional conference on Machine Learning, pp. 41 48, 2009.
Ronen I Brafman and Moshe Tennenholtz. R-max-a general polynomial time algorithm for near-optimal reinforcement learning. Journal of Machine Learning Research,
2002.
Yuri Burda, Harrison Edwards, Amos Storkey, and Oleg Klimov. Exploration by random network distillation. In International Conference on Learning Representations, 2019.
Devendra Singh Chaplot, Ruslan Salakhutdinov, Abhinav Gupta, and Saurabh Gupta. Neural topological slam for visual navigation. In IEEE/CVE Conference on Computer Vision and Pattern Recognation, pp. 12875-12884, 2020.
Hao-Tien Lewis Chiang, Jasmine Hsu, Marck Fiser, Lydia Tapia, and Aleksandra Faust. Rl-rrt: Kinodynamic motion planning via learning reachability estimators from rl policies. IEEE Robotics and Automation Letters, 4(4):4298-4305, 2019.
Edsger W Dijkstra. A note on two problems in connexion with graphs. Numerische mathematik, 1(1): 269-271, 1959.
Omar Darwiche Domingues, Corentin Tallec, Remi Munos, and Michal Valko. Density-based bonuses on learned representations for reward-fres exploration in deep reinforcement learning, In ICML Workshop Unsupervised Reinforcement Learning, 2021.
Adrien Ecoffet, Joost Huizinga, Joel Lehman, Kenneth O Stanley, and Jeff Clune. Go-explore: a new approach for hard-oxploration problems. arXiv preprint arxiv:1900 19.1.99190000 2019.
Scott Emmons, Ajay Jain, Misha Laskin, Thanard Kurutach, Pieter Abbeel, and Deepak Pathak. Sparse graphical memory for robust planning, Advances in Neural Information Processing Systems, 33:5251-5262, 2020.
Benjamin Eysenbach, Ruslan Salakhutdinov, and Sergey Levine. Search on the replay buffer: planning and reinforcement learning. arXiv preprint arXiv: 05253, 2019.
Bridging
Aleksandra Faust, Kenneth Oslund, Oscar Ramirez, Anthony Francis, Lydia Tapia, Marek F Fiser, and James Davidson. Prm-rl: Long-range robotic navigation tasks by combining reinforcement learning and sampling- based planning. In 2018 IEEE international conference on robolics and aulomation (ICRA), pp. 5113 5120. TEEE, 2018
Sébastien Forestier, Rémy Portelas, Yoan Mollard, and Pierre-vees Oudeyer. Intrinsically motivated goal exploration processes with automatic curriculum learning. The Journal of Machine Learning Research, 23 (1):6818 6858, 2022.
Robert M French. Catastrophic forgetting in connectionist networks. Trends in cognitive sciences, 3(4): 128-135, 1999.
16

---

Published in Transactions on Machine Learning Research (/)
David Ha and Jürgen Schmidhuber. World models. arXiv preprint wrXiv:1803.10122 2018.
Tuomas Haarnoja, Aurick Zhou, Picter Abbecl, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with stochastic actor. In International conference on machine learning, pp. 1861-1870. PMLR, 2018
Danijar Hafner, Timothy Lillicrap, Jimmy Ba, and Mohammad Norouzi. Dream control: Learning behaviors by latent imagination. In International Conference on Learning Representations, 2020.
Danijar Hafner, Timothy P Lillicrap, Mohammad Norouzi, and Jimmy Ba. Mastering atari with discrete world models. In International Conference on Learning Representations, 2021.
Zhiao Huang, Fangchen Läu, and Hao Su. Mapping state space using landmarks for universal goal reaching. Advances in Newral Information Processing Systems, 32, 2019.
Brian Ichter, Pierre Sermanet, and Corey Lynch. Broadly-exploring, local-policy trees for horg-horizon task planning, arXiv preprint arXiv:2010.064 06491, 2020.
Leslie Pack Kaelbling. Learning to achieve goals. In IJCAI, volume 2, pp. 1094 8. Citeseer, 1993.
Lydia Kavraki, Petr Svestka, J-C Latombe, and Mark H Overmars. Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE transactions Robotics and Automation, 12 (4):566-580, 1996.
Michal Kempka, Marck Wydmuch, Grzegorz Runc, Jakub Toczek, and Wojeiech Jaskowski. Vizdoom: A doom-based ai research platform for visual reinforcement learning. In 2016 IEEE conference on compula- tional intelligence and games (CIG), pp. 1-8. IEEE, 2016.
Hajime Kimura, Toru Yamashita, and Shigenobu Kobayashi. Reinforcement learning of walking behavior for four-legged robot. IEEJ Transactions on Electronics, Information and Systems, (22(3):330 337, 2002.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In 3rd International Conference for Learning Representations, 2015.
James Kirkpatrick, Razvan Pascanu, Neil Rabinowitz, Joel Veness, Guillaume Desjardins, Andrei A Rusu, Kieran Milan, John Quan, Tiago Ramalho, Agnieszka Grabska- Barwinska, et al. Overcoming catastrophic forgetting in neural networks. Proceedings of the national academy of sciences, 114(13):3521 3526, 2017.
George Konidaris and Andrew Barto. Skill discovery in contimuous reinforcement learning domains using skill chaining. Advances in neural information processing systems, 22, 2009.
George Dimitri Konidaris and Andrew G Barto. Building portable options: Skill transfer in reinforcement learning. In Ijeui, volume 7, pp. 895 900, 2007.
Tejas D Kulkarni, Karthik Narasimhan, Ardavan Saeedi, and Josh Tenenbaum. Hierarchical deep reinforce- ment learning: Integrating temporal abstraction and intrinsic motivation. Advances in newral information processing systems, 29, 2016.
Steven VaValee. Rapidly--xxplrrng random trees: A new tool for path planning. Technical Report 98- 11, Department of Computer Science, Towa State University, 1998.
Andrew Levy, George Konidaris, Robert Plaut and Kate Saenko. Learning multi-level hierarchies with hindsight. In International Conference Learning Representations, 2019.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. nature, 518((5400)5599-33 2015.
Arnab Kumar Mondal, Vincet Jain, Kalcem Siddiqi, and Siamak Ravanbakhsh. EqR: Equivariant represen- tations for data-efficient reinforcement learning. In International Conference on Machine Learning, pp. 15908-15926 PMLRR, 2022.
17

---

Published in Transactions on Machine Learning Research (/)
Ofir Nachum, Shixiang Shane Gu, Honglak Lee, and Sergey Levine. Data-efficient hierarchical reinforcement learning. Advances in neural information processing systems, 31, 2018.
Soroush Nasiriany, Vitchyr Pong, Steven Lin, and Sergey Levine. Planning with goal-conditioned policies. arXiv preprint orXic:1911.08455 2019.
Giambattista Parascandolo, Lars Buesing, Josh Merel, Leonard Hasenclever, John Aslanides, Jessica B Hamrick, Nicolas Heess, Alexander Neitz, and Theophane Weber. Divide-and--ooqqerr monte carlo tree search for goal-directed planning. arXiv preprint orXiv:2004.11441 2020.
Alexandre Péré, Sébastien Forestier, Olivier Sigaud, and Pierre- Yves Oudeyer. Unsupervised learning of goal spaces for intrinsically motivaled goal exploration. In International Conference on Leurning Represenla- tions, 2018.
Doina Precup.
Temporal abstraction in reinforcement learning. University of Massachusetts Amherst, 2000.
Martin L Puterman. Markoe decision processes: discrele stochaslic dynamic progromeming. John Wiley Sons, 2014.
Jette Randløv and Preben Alstrøm. Learning to drive a bicycle using reinforcement learning and shaping. In ICML, volume 98, pp. 463 471. Citeseer, 1998.
Xiaogang Ruan, Peng Li, Xiaoqing Zhu, and Pengfei Liu. A target-driven visual navigation method based on intrinsic motivation exploration and space topological cognition. Scientific Reports, 12(1):1-22, 2022.
Nikolay Savinov, Alexey Dosovitskiy, and Vladlen Koltun. Semi-parametric topological memory for naviga- tion. In International Conference on Learning Representations, 2018
Tom Schaul, Daniel Horgan, Karol Gregor, and David Silver. Universal value function approximators. International conference on machine learning, pp. 1312 1320. PMLR, 2015.
Julian Schrittwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, et al. Mastering atari, go, chess and shogi by planning with a learned model. Nature, :68(7839):004-600 2020.
Archit Sharma, Shixiang Gu,, Sergey Levine, Vikash Kumar, and Karol Hausman. Dynamics-awaad aware unsu- pervised discovery of skills. arXie preprint orXiv:1977, 190700167,, 2019.
David Silver, Hado Hasselt, Matteo Hessel, Tom Schaul, Arthur Guez, Tim Harley, Gabriel Dulac-Arnole David Reichert, Neil Rabinowitz, Andre Barreto, al. The predictron: End-to-end learning and planning. In International Conference Machine Learning, pp. 3191-3199. PMLR, 2017.
Alexander Strehl, Lihong Li, Eric Wiewiora, John Langford, and Michael Littman. Pac model-free reinforcement learning. In International Conference on Machine learning, pp. 881-888, 2006.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Richard S Sutton, Doina Precup, and Satinder Singh. Between mdps and semi-mdps: A framework for temporal abstraction in reinforcement learning. Artificial intelligence, 112(1-2):181121) 211, 1999.
Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: physics engine for model-based control. In 2012 IFFF/RSJ international conference on intelligent robots and systems, pp. 5026-5033, IEEF, 2012.
Elise Van der Pol, Daniel Worrall, Herke van Hoof, Frans Oliehoek, and Max Welling, MDP homomorphic networks: Group symmetries in reinforcement learning. In Advances in Neural Information Processing Systems, 2020.
Dian Wang, Robin Walters, and Robert Platt. So (2)-equivariant reinforcement learning. In International Conference on Learning Representations, 2022.
18

---

Published in Transactions on Machine Learning Research (/)
A Hyperparameters and computational setup
Tables 5 to 12 summarize the hyperparameeerrs used when training the different algorithms. The actor network used for the lower level goal-reaching policy takes a state and a goal as input (the dimension varies depending on the task) and processes them through 2 hidden layer MLP. The output layer depends on the algorithm. Training follows the procedure of DQN and HER with discount factor y and exponential smoothing on the target network (factor T), and an Adam (Kingma & Bal 2015) optimizer with default parameters. These parameters are the same for pretraining lower level policies for all algorithms. All RGL agents share the same Te, Mnode nedge: and Treach when applicable (for instance, PO-RGL uses Nedge but not Modde since it does not create new nodes). TC-RGL uses specific values Thode and Redge for thresholds on node and edge crcation, since it uses STC's temporal consistency network to measure node distance instead of our dt pseudo-mebric; the scale of this network's output is unrelated to that of d (hence the different values of Modde and Medge).
The results on grid-maze and point-maze were run on desktop machine (Intel 19, 10th generation processor, 64GB RAM) with no GPU usage. The results on ant-maze were obtained with single node computations. Each of these nodes was composed of 2 12-core Skylake Intel(R) Xeon(R) Gold 6126 2.6 GHz CPUs with 96 Go of RAM (no GPU hardware).
Our code is available at [Anonymous URL).
B Complete results on reachability graphs
Figures and 10 present extended version of the reachability graphs of figure 2 for all mazes in, respectively, grid-maze, point-maze and ant-maze environments. Blue dots in some figures correspond to the current selected goal at the time the graph was printed and should be discarded.
PO-RGL was created purely for didactic reasons in order to illustrate the pruning process independently of the incremental graph growth. Besides this illustration itself, these figures underline two features. First, the fact that RGL creates the graph incrementally makes it much sparser and avoids clusters of really close, redundant nodes. In turn, this sparse graph is much easier to prune than that of PO-RGL. Secondly, in environments with a fixed initial state (grid-maze, ant-maze), some edges never participate in the shortest path to any goal and hence are never pruned. Even if the sparse growth of the RGL graph limits this phenomenon, some impassable edges remain; e.g. some edges at the far right of figure Sp Randomly resctting the starting state at each episode permits a more complete and casier exploration of all shortest paths, and hence results a slightly more accurate pruning; e.g. the unpruned edges in grid-maze are better pruned on figure Op
Figure 10 (ant- (ant-maze environments) deserves a few additional comments. On this graph, to case the readability and account for directed edges, whenever a directed edge exists between and w, we plot the edge's segment closest to v in green. Orange then means the reverse edge has not been created. Red means the edge has been pruned. Some pruned edges appear in areas which seem passable. To explain this phenomenon, one needs to recall that the state space is 29-dimensional and a waypoint in the goal space (a geographical position of the ant's center of mass) can stand for a wide variety of configurations, as discussed in Section For any two nodes g and g', it is possible that g' was reachable from ((g) but is not reachable from some other states in Kg, since ant-maze environments violate the hypothesis that all states in K, are reachable from each other for negligible cost given the pre-trained policy. This leads to some edges being legitimately pruned while "naive eye" laid on the reachability graph might conclude there was a mistake.
Finally, the graphs grown by RGL in ant-maze environments feature very few edges crossing walls. This is a side effect of the default values of Modde and Medge (kept the same throughout all environments and mazes), and the fact that the ant's geometry prevents its center of mass to get close to the wall. This sometimes happens nonetheless when the ant randomly "trics" to climb over the wall (and systematically fails), which also places few nodes that appear to be inside the walls.
19

---

Published in Transactions on Machine Learning Research (/)
Table DQN lyyperaaraneters. DON+HER is used in grid-mazze lasks to compute goal reaching policies.
DQN
model hidden layers
64, ReLU, 64, ReLU
Adam 1e-3, (0.9, 0.999),
optimiser
eps=1e-08, weight decay=0) 1e5
replay buffer size
batch size
100
discount factor 7
0.95
exponential smoothing factor
1e-3
Table 6: SAC hyper-parameters SAC+HER serves as control policy for RGL, PO-RGL, and TC-RGL, as well as baseline, the "point-maze" and "ant-maze" environments.
SAC Point-Maze
Ant-Maze
critic hidden layers actor layers
250, Relu, 150, Relu
Adam(Ir=5o- betas= 0.999),
optimiser
1e-=1 weight decay=0)
replay buffer size
le5
1e6
batch size
100
500
7
0.99
0.99
5e-3
5e-3
crilic alpha
0.6
0.6
actor alpha
0.05
0.1
Table C51 hyper-parameterr,, which serves as a control policy SGM in the "grid-maze" environment.
C51
output distribution
20
size
models layers
64, ReLU, 64, ReLU
Adam(Ir=1e-3, betas=(0.9, 0.999), eps=1e-08, weight decay=0) le5
optimiser
replay buller size batch size
100
7
0.95
1e-3
Table Distributional DDPG hyper-parameters, which serves as a control policy for SGM in the "point-maze" environment.
Distributional DDPG
output distribution size
20
models layers
64, ReLU, 64, ReLU
Adam(1r=1e44, betas (0.9, 0.999), eps=1e-08, weight decay=0)
optimiser
replay buffer size batch size
lc6
64
7
0.99
7
0.05
20

---

Published in Transactions on Machine Learning Research (/)
Table 9: RGL hyper-parameters.
RGL
Grid-maze
Point Point-maze maze
Ant-Maze
Nedges
0.2
0.045
0.3
Tnodes
0.1
0.017
0.1
reachability threshold of the nodes
1
0.8
0.7
max time-steps to reach next node Exploration goal range interactions per exploration
50
50
150
4
90
150
Table 10: PO-RGT hyper-parameters.
PO-RGL
Grid-maze
Point-man maze
nedges
0.2
0.03
reachability threshold of the nodes max time-steps reach next node
0.8
50
four rooms: 400
four rooms: 400
medium: 600
medium: 500
nb nodes
hard: 600
hard: 700
mixed: 900
mixed: 900
Table 11: TC-RGL lyper-parameters. Hyper-parameter that not reported here are the same that the ones in Table 9 for RGL. "targeted edge length" is the minimum number of interactions that must separate two states of the trajectory, that they form positive pair (distant states) in the TC-network training data.
TC-RGL
Grid-maze
Point-maze
Medges
0.4
0.1
Tnodes
0.2
0.03
layers
125. ReLU, 100, ReLU, Sigmoid
batch size
250
TC-Network
buffer max
1c9
size
optimizer
Adam [r=1e-3, betas= (0.tass-00,,, 0.999), eps=1e-08, weight decay=0)
targeted edge length
20
21

---

Published in Transactions on Machine Learning Research (/)
Table 12: SGM aaeer--arameters.
SGM
Grid-maze
Point-maze
four rooms:
four rooms:
node pruning
medium:
medium:
threshold
hard: 3
hard: 3
mixed: 2
mixed: 3
four rooms: 5
four rooms:
max edges
medium:
medium:
length
hard: 6
hard: 7
mixed: 5
mixed: 7
four rooms: 1400
nb initial nodes
medium: 1400
hard: 1800
mixed: 1600
reachability
1
threshold
max interactions per sub task
20
C Complete results on graph sizes
Figures and 15 complement Figures and by reporting the evolution of nodes/edges count across interaction time steps in point-maze environments. Note that graphs on point-maze environments required a log-scale on the y-axis for readability since TC-RGL spanned an order of magnitude more nodes than RGL (and two to three orders of magnitude more edges).
D Are T-TILO policies common?
In the present work, important assumption is the existence of an e-TLOO policy. Thus it seems important to discuss how restrictive this assumption is, and how commonly such policies might occur.
In position-basod navigation tasks where S = G, generalization by translation invariance soems intuitive and easily justified by the translation invariance of the MDP's transition model properties throughout the state space. In navigation tasks where the state space is the agent's full configuration, but with abstract goal spaces (c.g. agent overall position), such the ant-maze benchmarks, finding TILO policies is closcly linked to defining the goal space, and hence the P : S - G projection. In this specific example, P is defined by simply keeping some variables of S and discarding the others. Here again, the TILO property is intuitive and translation invariance permits generalizing learned policies to unexplored parts of the state and goal spaces.
However, when comes to state spaces with confounding variables, such as visual navigation tasks, then defining P for abstract goal spaces might become more difficult as links the input image pixels to positions the navigation map. In way, P encodes expert knowledge about what abstractions of the state define useful goal space, discussed for instance by Forestier et al. (2022). Such abstractions might be learned (Péré et al.) 2018) but since they are pre-requisite for training a goal-based policy, they are generally considered to be provided by some expert. Such a description of goals is sometimes accessible for a minimal cost (as navigation tasks), but a perspective for future work implies learning relevant goal descriptors from data. One one can draw parallel with recent work in expressing goals with natural language and exploiting (large) language models to embed the goal description. Note, however, that in the general case, even if the corresponding P encoding is given, there is guarantee that TILO policy exists.
22

---

Published in Transactions on Machine Learning Research (/)
(d) RGL graph, 100,000
(a) PO-RGI, nodes
(b) RGL graph, 1,000
(c) RGT. graph, 4,000
(h) RGL graph, 150,000
(c) PO-RGL 600 nodes
(f) RGL graph, 1,000
(g) RCL graph, t= 4,000
(1) RGL graph, 250,000
(i) PO-RGL 600 nodes
(i) RGL graph, 1,000
(k) RGL graph, 4,000
(p) RGL graph, 210,000
(m) PO-RGL 900 nodes
(n) RGL graph, 1,000
(o) RCL graph, 4,000
Figure 8: Reachability graphs, grid-mazes.
Besides the considerations above, we argue that the existence of TILO policies is intrinsically linked more the nature of the task at hand than the definition of the goal space. Navigation is implicitly about finding (potentially convoluted) path through terrain with somewhat homogeneous properties. Hence, at least for this family of tasks, the existence of e-TILO policies is plausible assumption.
E From translation invariance to transformation invariance
Considering only translation invariance somchow restrictive as one could wish to identify invariances other transformations (e.g. deformations on images, rotations, etc.). In this section, attempt to abstract the intuitions of translation invariance into more general concept of transformation invariance.
23

---

Published in Transactions on Machine Learning Research (/)
(d) RGL graph, 100,000
(a) PO-RGI, nodes
(b) RGT graph, 1,000
(c) RGT. graph, 4,000
(h) RGL graph, 150,000
(c) PO-RGL 500 nodes
(f) RGL graph, 1,000
(g) RCL graph, t= 4,000
(1) RGL graph, 250.000
(i) PO-RGL 700 nodes
(i) RGL graph, 1,000
(k) RGL graph, == 4,000
(p) RGL graph, 210,000
(m) PO-RGL 900 uodes
(n) RGL graph, 1,000
(o) RCL graph, 4,000
Figure 9: Reachability graphs, point-mazes.
Suppose T(s, d) is transformation of with a parameter 6. In Section 3.2 the transformation was a translation of vector E S, which defined 7(s, = s + 5. But as another example, when stands for geographic coordinates, T(s, can be a rotation angle -, ø] around a central point. For genericity, we shall write 8 A.
Then, to define the invariance of the policy this transformation, need the analogous transformation in the goal space, which write F(g, 8). If S - G this transformation is obviously itself. For translation invariance in the general S * G case of Section 3.2 we defined Fgg,5) (8).
Then, oquation I can be re-written as
Vs 3,E A, 3p RR such that Vg ((P(()()))))))) p), (8,g) (r(5,8),F(g,0))
(2)
24

---

Published in Transactions on Machine Learning Research (/)
RGL, 6,000
(b) RGL. 24,000
(c) RGL, 500,000
(d) RGL, t = 6,000
(e) RGL, t = 24,000
(f) RGL, t= 700,000
(g) RGL, 6,000
(h) RGL, 24,000
(i) RGL, 1200,000
(i) RGL, f = 6,000
(k) RGL, t = 24,000
(1) RGL, 1200,000
Figure 10: Reachability graphs, ant-mazes.
Four rooms
Medium
Hard
Mixed
500
700
nb modes graph
400
600
400
3300
300
600
200
200
300
400
RGL (ours)
200
100
NoPG-RGL
200
TC-RGL
RGL
2.5e4
Se4
7.5e4
1e5
Se4
1e5
1.5e5
1e5
265
1.5p5
265
Figure 11: Number graph nodes grid-maze versus interaction steps. Shaded area the la confidence interval.
25

---

Published in Transactions on Machine Learning Research (/)
rooms
Medium
Mixed
107
mb nodes graph
10a
104
10
10a
10-
RGL (ours)
10-
NoPG
TC-RGL
10a
PO-RGL
10a
10a
10a
2.564
5e4
7.5e4
1e5
5e4
165
1.5e5
0
le5
265
564
165
1.5e5
265
Figure 12: Number of graph nodes in point- maze versus interaction steps.
Shaded area is the 1a confidence interval.
Four
Medium
Hard
Mixed
1400
RGL (ours)
1200
2500
$200
nodes 1n graph
1000
000
800
800
1500
600
600
1030
1000
400
500
200
200
2e5
4e5
6c5
265
465
6e5
Be5
0
Se5
1e6
0
5e5
1e6
Figure 13: Number of graph nodes in ant-maze versus interaction steps.
Shaded area is the 1a confidence interval.
Four
Medium
Hard
Mixed
nb edges 1000 graph
RGL (ours)
15.0
NoPG-RGL
15
PO-RGL
10.0
10
7.5
2
5.0
1
2.5
10
2.5e4
Se4
7.5e4
165
5e4
le5
1.5e5
1e5
2e5
5e4
1e5
1.5e5
2e5
Figure 14: Number of graph edges in grid-maze versus interaction steps.
Shaded area is the confidence interval.
Four rooms
Medium
Hard
Mixed
edges 1000 graph
RGL [ours]
102
10a
10a
NoPG-RGL
TC-AGL
104
10a
PO-RGL
101
10
10a
104
10a
109
109.
10-1
10
10
10-1
1.5e5
285
165
1.5e5
Figure 15: Number of graph edges in point-maze versus interaction steps. Shaded area is the confidence interval.
An optimal policy respecting equation 2 can now be called 7-invariant locally optimal (rILO). Note that translation invariance intuitive and straightforward application of this definition, which holds in
26

---

Published in Transactions on Machine Learning Research (/)
Four rooms
Medium
Hard
Mixed
nb edges / 11000 in graph
25
RGL (ours)
60
15:
20
40
10:
5
10
20-
265
4e5
665
0
265
4e5
6e5
865
0
Se5
1e6
5e5
166
Figure 16: Number of graph edges in ant- versus interaction steps. Shaded area is the confidence interval.
navigation tasks. Depending on the task at hand and the transformation т considered, it might be very difficult to prove the existence of rILO policies (Angelotti et. al. 2022).
A special case of rILO policies appears in visual navigation tasks, as those presented in the work of Eysenbach et al. (2019) or Emmons et al. (2020). Appendix [ further discusses this specific case and the technicalities of training visual goal-reaching policies; in the present paragraph, we restrict ourselves to discussing why the corresponding policies are rILO. In such tasks, the policy's input is first-person view of a robot's surroundings, the goal space is the state space, the action space are relative movements, and previous works discard the fact that the stochastic process defined by the visual observations is likely not an MDP (rather a POMDP). Now, let us consider two different states 8 and s' of the robot in the maze, with the corresponding image observations o(s) and o(s'). Suppose also that the relative positions of the walls around 8 and are the same, that is for instance, if the agent was facing wall from a certain distance and with a certain angle in 8, it is also facing a wall with the same distance and angle in s', Then o(s) and o(s') differ only through graphical features like texture or lighting for example. If the policy (or value function) has been properly trained to detect the wall in the picture, regardless of its texture or lighting, then it will be insensitive to the texture or lighting change between o(s) and o(s'), and hence will be able to generalize goal-reaching policy trained in s, to s'. Formally, let 7 be the transformation that turns s into s', then a locally optimal policy T" (s.g) will output the same action in (T(s), These policies are rILO by construction (because they rely on first-person views and because their neural network embeddings are supposedly trained to be insensitive to irrelevant image features) and respect equation 2
F Influence of graph density hyperparameters.
The thresholds Mode and Medge on node and edge creation condition how coarse the graph is in the goal space. Consequently, they impact the density of the graph, hence the ability to accurately represent transition dynamics. As such, they encode a notion of minimal required granularity to efficiently generate efficient goal-reaching plans in the goal space. Despite RGL's ability to build sparse representative graphs, poor choice of Mnode and Medge parameters can be detrimental to RGL's goal reaching accuracy. Figure 17 reports how sensitive PO-RGL and RGL agents are to these parameters, in the "medium" " grid-maze. Figure I7a illustrates how increasing the values of Toode to 0.2 (then 0.3) and Medge to 0.4 (then 0.5) results in a graph which does not enable reaching distant goals anymore. A similar effect happens for PO-RGL, as choices for Nynit will have a direct impact on the accuracy of the algorithm. Figure 17b reports how varying Nemi from 100 to 600 affects the goal reaching accuracy of PO-RGL. With only 100 nodes, the reachability graph of PO-RGL features subgoals which are very distant from each other and rarely reachable between each-other, resulting in graph with almost no edges (Figure 17c). Hence, goals besides those reachable by the lower-level policy can be reached. With 200 nodes (Figure 17d), the final goal reaching accuracy of PO-RGL improves to about. 50% and keeps improving until Nimit 400 nodes. For Ninit = 500 and 600, the number of edges to prune in the graph becomes so large that it slows the learning down, resulting in less reachable nodes after 100,000 interaction steps because the graph contains too many mislcading edges which have not been pruned yet. Overall, this illustrates how the directed, exploration-die node and edge creation of RGL yields graphs which are both much sparser and much more representative of reachability, than building
27

---

Published in Transactions on Machine Learning Research (/)
graph over randomly sampled goals (either randomly sampled from replay buffer in SoRB, randomly sampled from oracle as PO-RGT.)
Medium
Medium
1.2
FC-RGL 100 nodes
RGL 00. m0.4
PO-RGL
REL 0.3 Dodg 5
FO RGL 330 rodes
PC-RGL 500 nodes
sccuracy
eccuraty
0.2
0.2-
0.0
0.0
stegs aagent-envinne envernmetttnmment nnterattion
steps aagent Enviromment interactions
(a) Inffuence of Awode Medge
(b) Influence Ninit on PO-RGL
(c) PO-RGL initial graph for Ninit 100
(d) PO-RGL initial graph for Ninit 200
Figure 17: Hyperparameter influence on goal-reaching accuracy in the "medium" grid-maze after 100,000 interaction steps.
G Pre-training a goal-conditione TILO policy in ant-maze.
Learning goal-based policies for ant-maze environments is challenging, even in the obstacle-free playground. To let SAC+HER converge efficiently, we build a process inspired from curriculum learning (Bengio et al. 2009). We sample goals uniformly in disc around the agent, starting with radius of Every time the agent reaches a goal, we increment the radius of 0.1, and decrease it when it fails. If the radius reaches value of 6, stop incrementing and let the agent reach accuracy close 100% in this pre-training playground. Note that this value of 6 is much larger than that of Madd and Medge (sce Appendix A).
While navigating in the graph, following a sequence of sub-goals, the agent will change its direction many times in an episode. This may lead to more diversity in the states encountered while navigating the maze than those seen during the pre-training. To mitigate this aspect and improve state diversity during pre- training, every 5 episodes, instead of a full agent reset, we reset only the agent's position but retain the orientation, legs configuration and velocities from the last state of the previous episode.
28

---

Published in Transactions on Machine Learning Research (/)
H Hierarchical actor critic on various tasks
Ant-maze tasks have been tackled in previous work, notably in the important HAC (Levy et al. 2019) contribution, on similar tasks to those reported here, in particular the "four-rooms" maze. In order to provide a fair comparison with RGL, we used the reference implementation of HAC pro- vided by the authors hutps://githuu..com wtt.gghtw..om/nndnwwwwiiaeeeeeee anddewaw-dewwwey Hoaddrew---oyyyyHeearcccha----- Actirai---Attt--C--------- /trce/ /ttrre/asttrrrr// ant environments/ant four rooms 3 levels, This section discusses why this implementation (without modifications) fails the tasks reported here.
Goal and initial state sampling in HAC to promotes diversity. In the original HAC contribution, during training, goals are sampled uniformly in the center of each room (red areas in figure 18] then initial states are sampled uniformly in the center of another room. This induces a variety of starting states and insures that starting states and goals are always at least one room away from each other. In turn, this promotes diversity in the replay buffers, which facilitate policy training. In the experiments reported in Section q argued that this "reset anywhere" feature was a partieularly favourable case for exploration.
3
6.5
Figure 18: Illustration of goals and initial states sampling areas.
Variations in mazes. We also investigated whether the loss of efficiency of HAC could be attributed to the difference between the mazes presented here and those of the HAC paper. For this purpose, we tested HAC on three lasks and report results in Figure 19 (averaged over 10 trials).
The exact 17 x 17 "four-rooms" map used in the HAC paper, with the goal initial state sampling strategy defined above (labelled HAC sampling / small four-rooms in Figure
2. The same 17 x 17 maze map, but with uniformly sampled goals while keeping the starting state fixed (labelled Uniform goals ssmall "four-rooms" " in Figure
3. A larger 41 x 41 "four-rooms" map which is the one used in the RGL experiments of Section 4 with the HAC goal / initial state sampling strategy (labelled HAC sampling / large "four-roomss in Figure 19). This map features slightly narrower passages between each room (proportionally to the size of the room). Actions remain the same: the ant is not scaled up. Goals are sampled uniformly. HAC's states and goals scaled to the size of the map.
The same x 41 "four-rooms" " map with a fixed starting state and uniform goal sampling (labelled Uniform goals / large "four-rooms" " in Figure 19
The evaluation accuracy of each agent reported in Figure 19 follows the agent's goal/ initial state sampling procedure than during training. Specifically, agents that were trained with the HAC sampling strategy are
29

---

Published in Transactions on Machine Learning Research (/)
5e2
1e3
1.5e3
2e3
2.5e3
363
HAC sampling small four-rooms Uniform goals small four-rooms
HAC sampling large four-rooms
Uniform goals large four-rooms
Figure 19: HAC average accuracy on variations of the "four-roons"" ant-maze lask, versus number of episodes (episode length is capped at 700 time steps but be smaller if the goal is reached before).
medium
hard
mixed
0.12
0.12
0.10
0.10
0.10
0.06
0.06
0.04
0.05
0.02
0.00
0.00
2000
500
Figure 20: HAC average accuracy on the "medium", "hard", and "mixed" mazes for the ant-maze task, versus number of episodes (episode length is capped 700 time steps but be smaller if the goal is reached before). Green curve: uniform initial state sampling. Blue curve: fixed initial state.
evaluated by the proportion of reached goals when goals and initial stales are drawn according to HAC's sampling strategy. Similarly, agents that were trained with fixed starting state are evaluated on the same setting. Consequently, the only fair comparison with the RGL results of Section 3 is when the starting state is fixed and the goals sampled uniformly. Recall that RGL reaches accuracy of 89% the large "four-rooms" environment with fixed initial state and uniform goal sampling (Figure
It appears that the goal / initial state sampling strategy is a crucial feature of HAC in ant-maze. Removing this feature, and sampling goals uniformly, reduces the accuracy of HAC's optimized policy from 76% to 28% in the small "four-rooms" environment, and from 29% 5% the large one.
It also appears HAC is rather sensitive to the scale of the map (despite appropriate state scaling in the inputs of the neural networks): even with the HAC initial state / goal sampling strategy, the accuracy of the optimized policy does not exceed 28% (versus the 89% of RGL). More steps are required to cross a room between passages and we hypothesize HAC suffers from this difficulty to span long trajectories between goals and hence struggles to reach good accuracy in larger mazes.
Note that the HAC sampling strategy is tailor-made for the "four-rooms" maze and undefined for other mazes, so the comparison above cannot be reproduced for the "medium", "hard", and "mixed" mazes. Instead (and this goes beyond what proposed by the HAC authors), in attempt to have comparison baseline,
30

---

Published in Transactions on Machine Learning Research (/)
replaced this HAC sampling strategy by uniform sampling of both the initial state and the goal in these three mazes. We also evaluated the fixed initial state / uniform goal sampling setting. Results (Figure 20) on other maps are similar to those of Figure 19] HAC reaches very small accuracy levels compared to RGL, even with the diversity of initial states and goals induced by uniform sampling. For this reason, we chose not to include these results Section 4
Deep Skill Graphs on various tasks
This section discusses the similarities and differences between DSG and RGL. While there are similarities in their design principles, the two approaches remain quite different.
The main difference lies in the fact that DSG trains a different option for every vertex in the graph, following DSC's procedure (Bagaria & Konidaris 2019). In contrast, RGL. does not interleave lower-level policy training (which is a local goal reaching policy instead of a set of options) with graph expansion. This has the drawback (for RGL) of preventing local adaptation of behaviors, but the advantage of sample efficiency and a full re-use of pre-trained policies (which is the key interest of the TILO abstractioon.
Beyond this key difference, initiation and effect sets of DSG play the same role as the neighborhoods defined by Mnode and Rodee in RGL.
Aside from these elements, one should note that RGL generalizes from the S = G context to contexts where S o G.
Also, and quite importantly, DSG uses the Euclidean distance between states as a reachability heuristic in graph construction, while RGL uses the value function V(s.g) which somehow more principled. This distance also used to define dense reward model when training options.
This last point is particularly important in explaining the difference in empirical scores between DSG and RGL (see Figure 7). As indicated by Bagaria et al. (2021 Section 4), DSG makes use of dense rewards and this is where it really shines (Section 5 of the DSG paper actually discusses shortly the need to extend to sparse rewards). Tn the experiments reported in the present paper, the rewards are sparse, as we are in a purely goal-reaching policy search, where we did not introduce any reward shaping.
Four
Medium
Hard
Mixed
1.0
1.0
accuracy over tests
Wh
0.8
0.8
0.6
HAC
RGL (ours)
0.6
1/
0.6
DSG (Derse rwd.)
0.4
0.4
DSG (Sparse rwd.)
0.2
0.2
0.2
0.0
0.0
0.0
0
2e5
4e5
6c5
2e5
4e5
6c5
Be5
Se5
leb
2.3e5
Se5
7.5e5
1e6
Figure 21: Accuracy of various methods in the Maze, using the same maps used in figure
Every methods are
trained using sparse rewards, except the experiments labelled "DSG (Dense rwd.)
reports the difference in performance of DSG the 4-rooms environment, both with dense and sparse rewards. In the case of sparse rewards, using DSC's procedure to ro-train local options for every graph vertex might quickly become inelficient and, in contrast, the TILO policies of RGL appear as a better option in this context. In comparison, performing the same experiment with sparse rewards leads to an accuracy gap, and shows the reliance of this method for dense reward. However, the accuracy observed for DSG with dense reward is still far from the accuracy presented in the original paper. According to the authors, this method can fail to reach some goals while using dense rewards, especially when the goal to reach is at the other side of a wall.
Figure 21
However, the learned value function is less influenced by this reward the further away the goal from the agent.. Such problems are more likely to occur when both the goal and the agent are close to the wall. Tn
31

---

Published in Transactions on Machine Learning Research (/)
our experiments, the goals are sampled uniformly in the reachable space, and walls are thinner (in mujoco units, our mazes have thickness of 1, while the ones used in DSG paper have a thickness of 4). We consider that such walls thickness could lead to a higher chance of seeing the DSG agent failing while trying to reach a goal by trying to cross a wall. DSG suffers from the same issue, but it can be casily corrected by adjusting the graph density hyper-parameter Thode since RGL agent will only try to reach a goal from the closest node. Figure 22 shows the accuracy of DSG in a U-Maze with thick walls. The only difference between this experiment and the one called *DSG (Dense rwd.)" in figure 21 is the walls positions and their thikness.
DSG with dense rewards in U-Maze
0.9
100000 200000
300000
400000
500000
600000
700000
Figure 22: Accuracy of DSG with dense reward in a U-Maze with a wall thickness of 4
J Training in playgrounds and generalizing to unseen states
In Section f we claimed that "only RGL can, by design, exploit a goal-reaching policy which has not been trained on the actual full maze". This contrasts with, for instance, Section 5.5 of the SoRB paper (Eysenbach et al. 2019 where visual policy is first trained to navigate in 100 houses from the SUNCG dataset from first-person images, then this policy's value function is transferred to new houses where it enables building naviaglion graph. We argue the claim of Section 4 still holds and introduce nuance and justification below.
It is important to note that (i) this visual policy is very close to being TILO (see Appendix E and, (ii) more importantly, is trained on data that covers reasonably well the set of images the agent might encounter. This second property makes the policy likely to generalize well to new houses in the first. place. Consequently, although SoRB is indeed tested on new mazes, the combination of a first-person visual value function and the fact that training covers representative set of images creates a favourable setting which implicitly captures translation invariance. We expand on this aspect in the following paragraphs.
SoRB and SGM are designed to build a graph on states from the pre-training replay buffer or on states that are close enough to those of the pre-training replay buffer, when such states can be drawn from an oracle (which what happens in the experiment of Section 5.5 in the SoRB paper). This constraint is lifted with RGL thanks to the TILO property which nicely decouples local TILO skills learning from macro-action graph building. Specifically, for the transfer to new houses in the SoRB paper, is important to examine how the value function is trained. In a nutshell, the authors of SoRB take (s.g) pairs that are about 4 steps away in many different houses, and train value function that indicates "how many consecutive actions does it take to transform this image into this g image?". We conjecture that the combination of a "reset anywhere" possibility, plus training on 100 different houses, permils seeing a diversity of (8,g) g) pairs that enables generalization to similar images in new houses (unfortunately the SUNCG dataset is not available anymore to verify this conjecture, due to legal issucs). Then, SoRB's MAXDIST parameter is set to 3, which means SoRB creates an edge between two nodes whenever the value function estimates one needs most 3 actions to connect the two corresponding states. Our point is that the diversity of (8,9) pairs sampled
32

---

Published in Transactions on Machine Learning Research (/)
from the first 100 houses actually reasonably covers the set of possible images and that the pre-trained value function is good estimator of "can T reach y from 8 in less than 3 actions?", even for images from different houses, that were not seen during training.
From this perspective, SoRB's value function in this precise case captures the notion of translation invariance without stating it explicitly. Once this made clear, then what SoRB really does sample states from an oracle (the reset function the environment) and connects them using this value function, while SGM becomes almost equivalent to PO-RGL: it builds the same graph SoRB and then prunes it. What enables SoRB and SGM to perform this graph building is precisely because the value function was trained on rich enough data to be able to evaluate distances between images sampled from new houses. Without this "implicitly-TILOO" property, they wouldn't it be able to build this graph reliably.
In conclusion, the exploitation of translation invariance RGL can be interpreted as a principled general- ization of the previous example: permits pre-training the lower-level policy in a playground (such as the 100 first houses of the SUNCG dataset) and transferring the pre-trained value function to unseen states in another MDP, where the TILO property ensures to retain local optimality of policies. In turn, this decou- ples, in a principled way, learning lower-level skills (like walking in ant-maze, regardless of locally specific surrounding obstacles) from chaining skills and navigating.
33


Reviews:
[{"review_id": "OvFMBgfIYk", "reviewer": "Reviewer_R9XL", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The direction of combining the traditional graph-based search method and the RL is promising, and the paper demonstrates its effectiveness. I also appreciate the author’s definition of translation invariance, clarifying the conditions for which such a graph-based method can be used.\n\nHowever, the paper should have included several important relative works in hierarchical imitation learning. For example, [1] also demonstrates an approach that builds a graph using a replay buffer and uses shortest path search to find sub-goals for the low-level RL policies. It also leverages the Q or value function as a quasi-metric between subgoals. Except for the tiny differences in how the graph is expanded ([1] simply sampling landmarks using farthest point sampling), most algorithms are quite similar.  Given the similarity between the two algorithms, this paper’s novelty is limited mainly.\n\n[1] Huang, Zhiao, Fangchen Liu, and Hao Su. \"Mapping state space using landmarks for universal goal reaching.\" Advances in Neural Information Processing Systems 32 (2019).\n\nAnother major limitation of the work is that only the navigation style environment is considered, where a low-dimensional goal space can be defined trivially. However, in most manipulation tasks, especially tasks that involve multiple objects, the goal space and state space become high-dimensional. Building such a graph becomes intractable.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "- This paper proposes a graph-based RL method that uses a goal-conditioned RL policy and state reachability to form a graph to solve RL problems.\n- The paper formalizes the notion of translation invariance that enables the use of the goal graph as an abstraction of the original MDP.\n- The proposed method can solve challenging long-horizon RL tasks.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "No", "audience_explanation": "", "requested_changes": "The author should at least include a discussion about the relative work mentioned above. Experiments or discussions about high-dimensional goal space are also required.", "broader_impact_concerns": "no broader concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "1LUUuEL1hs", "reviewer": "Reviewer_JxoC", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n* The paper provides useful definitions of relevant concepts (goal to state mapping, translation invariance) and detailed descriptions of the method.\n* The related work section and context for prior work is quite detailed.\n* The graph results in Figure 2 could be useful from an interpretability to understand what policies are capable of.\n\n**Weaknesses:**\n* Based on the results presented in Section 5 and Section 6, it is unclear if RGL provides benefits compared to other methods. In some cases the baselines are within the margin of error. \n* The ablations often show unclear results about the most important parts of the method. The large variance shown in the learning curve applies to both the baselines and the ablations.\n* The clarity could be improved for the experimental section. For example, the figures could be improved with more detailed captions and the paper could be shortened to fit into 12 pages to make the important takeaways more concise.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a new method to learn control policies for reaching goals based on what the paper describes as reusable skills. To do so, the paper proposes using a graph structure that encodes abstract goals and enables planning in the goal space. The paper starts by introducing how reinforcement learning (RL) has shown promise in learning well-defined skills and proposes using the translational invariance of those skills to perform tasks in settings that should be easily translatable to situation that are practically not very different. The paper then defines its main contributions related to: 1. A generic framework linking goal space and states; 2. Providing a definition of reusability for goal-reaching policies; 3. A graph-based model training method. Section 2 summarizes related work, including goal reaching in RL, hierarchical RL, planning and reusable policies. Section 2 also details how the proposed method (RGL) is different from prior work.\n\nSection 3 describes relevant definitions for the proposed method. The first definition relates to thinking of goals as state abstractions where one can define mapping functions between goals and a set of states in the environment. The definition of goals is then used to define the translation invariance of local optimal policies, which enables translating skills to reach practically similar goals. Next, the paper defines the graph topology that provides insight into reachable states from the current state and builds a graph that can be used for planning. Based on these three components, the paper defines its main algorithm: Reachability graph learning (RGL).\n\nSection 4 describes the experimental setup, which focuses on different maze settings. The section defines the baselines that are compared against RGL and outlines a pre-training method that infuses the relevant skills into the goal-reaching policy. Section 5 outlines the main experimental results starting with visualizations of goal-reaching graphs across the different maze settings. The paper provides an analysis and details on ablation of the method in Figure 3, Figure 4 and Figure 5. Section 6 describes experiments on more challenging tasks using the ant environment in a maze comparing different ablations and baselines. Section 7 provides a conclusion and discussion.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "**Important Changes:**\n* Please provide more descriptive figure captions that summarize the main settings and takeways for each. This will make it easier to understand the relevant context of the results.\n* Please summarize the different ablation in a table or another way to easily find them. They way they are currently presented makes it difficult to track what is what.\n* Please address the variance in the results plots. It appears that in some cases your method has distinction from the baselines, but I would recommened greater clarity on the ablation and where RGL provides clear benefits.\n\n**Nice to Have:**\n* A visual example of the reachability graph pruning and expansion (this can be in the paper or appendix).\n* A discussion on applications of RGL - can be mainly in control problems but potentially also broader.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "26r6TLgo06", "reviewer": "Reviewer_Pgxz", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n* Definition of TILO is a simple and reasonable abstraction in many settings.\n* Policy training pre-training method inspired by TILO (enforce translation property holds for resulting pre-trained policy by training policy as a function of $g - s$)\n* Policy pre-training performed on a simple playground (though this is highly task-specific, the contribution would be significantly stronger if a more general approach to determining and evaluating playgrounds was proposed).\n* A specific graph reachability approach is proposed, with dynamic growing and pruning phases. However, I should also note that the proposed method itself for graph reachability does not strike me as particularly novel though it does seem distinct from existing methods.\n* Many experimental ablations demonstrating the strength of the proposed approach on several varying-complexity maze environments, including continuous and stochastic high-dimensional settings. A lot of the value in the paper is in these ablations and empirics.\n\nWeaknesses\n* It is hard to apply the TILO property in general, and requires significant work and insight to determine a playground for pre-training. Thus it is not clear how far beyond the existing settings studied the approach will generalize, though there are some gestures at applications to image-based settings in Appendix I.\n* DSG, which is mentioned in the paper, seems quite similar in overall high-level concept. While Figure 7 suggests that the presented method drastically outperforms DSG, it is a bit puzzling since the DSG method is overall quite similar.\n* Figure 17 suggests that hyperparameters need to be set quite carefully based on the environment to see a good performance, limiting direct applicability but still providing knobs to turn.\n* There is an additional strong assumption that moving between states which correspond to the same goal is feasible and costless. This seems ok if there’s only really one way to reach a certain goal which has no influence on future strategies (e.g., acquiring some resource and state doesn’t matter for future steps), but it seems like an issue in harder settings. However, it is also nice to note that the ant-maze setting breaks this assumption (ant state configuration is independent of physical location in maze), but the proposed method still performs reasonably well.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work proposes a method for goal-based RL in the context of environments which enjoy a translational invariance  (TILO) property (essentially, the assumption of the existence of ($\\epsilon$-)optimal policies which are \"smooth\" with respect to the state/goal space). In particular, the proposal is to abstract the learning of low-level translation-invariant policies into a pre-training phase on an environment amenable to efficiently learning these low-level policies, followed by a planning on a reachability graph derived from the pre-trained policies. The key novelty in this work appears to be the introduction of the TILO property as well as an approximate and transformation versions thereof, which the authors use to develop their method. The method also combines several techniques existing in prior work and combines them together to achieve improved empirical performance on a set of maze tasks. The authors also perform several ablations of their method and compare to existing methods in their settings.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Overall, I would vote to accept the paper assuming the critical questions below are resolved.\n\nCritical Questions/Change Requests:\n* Why is DSG achieving zero performance in Fig 7? Given that there is such an extreme gap in performance on the tasks evaluated in this paper, it would be good to see an evaluation of the presented methods on the specific tasks in the DSG paper or an explanation and analysis similar to Appendix H explaining the non-performance of DSG. At least, some more evidence is required for explaining the near-zero performance of DSG beyond an implementation error.\n* It would be good to expand on the differences between the proposed method and DSG further. Since the methods are somewhat similar, it is surprising that DSG would perform so much worse.\n* It would be good to lighten the claims in the introduction and emphasize the focus on the setting to which we know TILO properties apply. It is fine to highlight that the method could be more broadly applicable, but it should be emphasized that it is an adhoc procedure to determine a relevant \"playground\" (though I understand that one could always use the existing distribution of environments as a playground, it is still not clear in general how NoPG training generalizes beyond the settings studied in this paper as it is an empirical question).\n\nSuggestions:\n* The underperformance of NoPG-RGL compared to RGL in Fig.3 implies that in the main environment of the actual maze, it is harder to learn the movement policies useful for navigation as compared to the playground. Thus, is it fair to interpret this effect as an instance where completely decoupling the learning of a set of useful low-level skills adds significant information to the problem? Are there examples of cases where training on a “playground” like environment significantly hurts performance compared to training on the distribution of actual environments? Are there ways of detecting whether a “playground environment” will be helpful or harmful prior to running the full experiment?\n* The discussion in Appendix I was quite interesting and helpful, and I wonder if the authors have any more comments on detecting the utility of and/or building potential playgrounds (are there simple tests that might enable one to determine whether a playground is useful? How about constructing playgrounds?)\n* The paper would be greatly strengthened if more insight was given into how one could identify/develop useful playgrounds or at least efficiently test whether a playground is useful quickly, though I understand this may be outside the scope of the current paper.\n\nNits (see beginning of Section 3):\n* I disagree with the statement: \"continuous universal approximators, neural networks are intrinsically unsuited to approximate abrupt environment of skill changes, and discontinuous functions such as the value functions arising in some difficult RL environments\" - it should be framed differently. The problem which arises doesn’t have to do with the fact that neural nets are continuous universal approximators, has to do w/how smooth a function it is, which can be controlled, and the difficulty of learning such functions as dependent on these smoothness parameters. As a simple counterexample, language is discrete and discontinuous yet we have LLMs.\n* I disagree with the statement: \"Because neural network optimization assumes that samples are obtained independently and identically from a stationary distribution, they are also unsuited to retain local information.\" This misattribution issue has nothing to do w/using neural networks or not, it has to do w/what learning problem you set up. Please rephrase or remove - using the wrong learning framework w/a neural net policy class doesn’t imply that the policy class is bad.\n* \"Neural networks are great at learning complex continuous functions such as navigation or movement primitives, or local goal-reaching policies.\" This statement also doesn’t make sense as-is and needs to be considerably clarified. I would discard all of these statements, the only point you need to make is that neural networks are a viable policy class for low-level policies and that it may be advantageous to add additional known structure to the problem setting (which can be learned) rather than attempting to learn a complete world model with no additional assumptions which may require high sample-complexity.\n* \"When requiring to achieve\" → “When we would like to reach”\n* \"its ability to represent accurately an abstraction of the environment dynamics despite unbalanced samples and discontinuous properties\" → accurately represent", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: I recommend accepting this paper. The work introduces a well-formalized framework through the Translation Invariance (TILO) property and demonstrates its effectiveness through a novel graph-based RL method. The empirical results show promising performance on long-horizon tasks in maze navigation environments. Initial reviewer concerns about result variance and baseline comparisons were adequately addressed through additional experiments and clearer result presentations in the revisions. The authors have been responsive to reviewer feedback.

While the practical impact for real-world applications remains to be seen, and there are limitations in generalizability beyond navigation-type tasks, these uncertainties are well-acknowledged by the authors. The paper makes meaningful contributions to goal-conditioned RL and long-horizon planning, and could serve as a foundation for future research in this direction.
Decision: Accept (poster)