From Connectivity to Rewards: Dense Reward Learning with Directed State Graphs

# From Connectivity to Rewards: Dense Reward Learning with Directed State Graphs
Source: [https://arxiv.org/html/2609.10781](https://arxiv.org/html/2609.10781)
Shuyuan Zhangshuyuan\.zhang@mail\.mcgill\.caZihan Wangzihan\.wang5@mail\.mcgill\.caAffiliation:School of Computer Science, McGill UniversityAffiliation:Mila – Quebec AI InstituteXiao\-Wen Changchang@cs\.mcgill\.caAffiliation:School of Computer Science, McGill UniversityDoina Precupdprecup@cs\.mcgill\.caAffiliation:School of Computer Science, McGill UniversityAffiliation:Mila – Quebec AI InstituteAffiliation:Google DeepMind,Affiliation:CIFAR Fellow

###### Abstract

The integration of graphs with Goal\-Conditioned Hierarchical Reinforcement Learning \(GCHRL\) has received increasing attention, as graphs naturally encode task hierarchies for effective subgoal sampling\. However, existing methods often overlook intrinsic connectivity information, failing to fully leverage the underlying topology for efficient learning\. Most graph\-based GCHRL methods use the graph as a stochastic sampling tool rather than as an environmental model that encodes connectivity and state\-accessibility information\. This limitation is particularly acute in quasimetric environments, where the inherent asymmetry of state transitions poses a fundamental challenge to stable policy learning and robust path planning\. In this paper, we address these problems by introducing a state connectivity model designed to predict pairwise state connectivity strength in asymmetric environments\. We transform these connectivity strengths into scalar auxiliary dense rewards, providing continuous guidance across multiple hierarchical levels\. We demonstrate that our proposed framework, Graph\-Guided Quasimetric Dense Reward \(G2QDR\), can theoretically be integrated into any existing GCHRL architecture, and the state connectivity model is efficiently implemented via a neural network trained on a directed state graph generated during exploration\. Empirical results across a wide range of sparse reward environments indicate that, in general, G2QDR can enhance the performance of baseline GCHRL approaches with acceptable computational overhead\.

## 1Introduction

Sparse rewards remain a fundamental challenge in reinforcement learning \(RL\), where agents must learn from infrequent and delayed feedback signals\. In such settings, traditional, non\-hierarchical approaches\([Schulman et al\., 2017](https://arxiv.org/html/2609.10781#bib.bib29);[Fujimoto et al\., 2018](https://arxiv.org/html/2609.10781#bib.bib27);[Haarnoja et al\., 2018](https://arxiv.org/html/2609.10781#bib.bib28)\)often struggle with inefficient exploration and poor credit assignment\. Goal\-Conditioned Hierarchical Reinforcement Learning \(GCHRL\) addresses this issue by decomposing a long\-horizon task into a sequence of intermediate subgoals: a high\-level policy proposes subgoals, while a low\-level policy learns to achieve them\. This hierarchical decomposition significantly improves learning efficiency by transforming a difficult global objective into a set of more tractable local problems\.

Despite these advantages, early GCHRL methods\([Nachum et al\., 2018a](https://arxiv.org/html/2609.10781#bib.bib21);[Nachum et al\., 2018b](https://arxiv.org/html/2609.10781#bib.bib20)\)often suffer from sample inefficiency, as the high\-level agent must select subgoals from the entire state space—a task that can be even more challenging than selecting actions in non\-hierarchical approaches\. Prior work has attempted to address this issue by constraining subgoal selection to local regions\([Zhang et al\., 2022](https://arxiv.org/html/2609.10781#bib.bib24)\), imposing smoothness constraints on sampled subgoals\([Li et al\., 2022](https://arxiv.org/html/2609.10781#bib.bib32)\), or employing stochastic sampling strategies\([Wang et al\., 2024](https://arxiv.org/html/2609.10781#bib.bib23);[Wang et al\., 2025](https://arxiv.org/html/2609.10781#bib.bib1)\)\. While these approaches reduce the burden on the high\-level agent, they do not organize visited states or subgoals into a structured representation, thereby losing important connectivity information\.

In contrast, graph\-based GCHRL methods\([Lee et al\., 2022](https://arxiv.org/html/2609.10781#bib.bib19);[Gieselmann and Pokorny, 2021](https://arxiv.org/html/2609.10781#bib.bib15)\)model relationships and connectivity between states explicitly through a state graph, which is inherently well\-suited for representing the environment and task structure\. Previous graph\-based work has explored directions such as decision\-making via graph search or traversal\([Wan et al\., 2021](https://arxiv.org/html/2609.10781#bib.bib17);[Shang et al\., 2019](https://arxiv.org/html/2609.10781#bib.bib18);[Eysenbach et al\., 2019](https://arxiv.org/html/2609.10781#bib.bib10)\), as well as the use of graphs as world models\([Zhang et al\., 2021](https://arxiv.org/html/2609.10781#bib.bib14);[Huang et al\., 2019](https://arxiv.org/html/2609.10781#bib.bib22)\)\. However, many of these approaches rely on pre\-crafted graphs, which limit their generalizability\. Moreover, most existing methods\([Zhu et al\., 2022](https://arxiv.org/html/2609.10781#bib.bib8);[Hong et al\., 2022](https://arxiv.org/html/2609.10781#bib.bib7)\)operate directly on the constructed graph, making them less effective when the agent encounters states that are not represented in the graph\.

Graph learning, alternatively, enables the agent to leverage relational structure even when the current state is not explicitly represented in the graph, by generalizing through learned embeddings and connectivity patterns\. Recent studies\([Zhang et al\., 2025](https://arxiv.org/html/2609.10781#bib.bib5)\)have shown that incorporating graph representations into the learning process can significantly enhance the performance of underlying reinforcement learning algorithms, improving both sample efficiency and generalization\. Moreover, graph learning\([Klissarov and Precup, 2020](https://arxiv.org/html/2609.10781#bib.bib30);[Klissarov and Machado, 2023](https://arxiv.org/html/2609.10781#bib.bib16)\)facilitates more informed exploration and planning by capturing the topology of the state space, allowing agents to reason about long\-range dependencies and transitions beyond their immediate experience\.

Another common challenge in graph\-based methods is that distances between states are often quasimetric\([Wang and Isola, 2022](https://arxiv.org/html/2609.10781#bib.bib3);[Wang et al\., 2023](https://arxiv.org/html/2609.10781#bib.bib4)\), meaning that transition costs are asymmetric: moving from B to A can be significantly more difficult than moving from A to B\. Undirected state graphs\([Zhang et al\., 2025](https://arxiv.org/html/2609.10781#bib.bib5)\)fail to capture this asymmetry, motivating the use of directed graphs instead\.

In this paper, we propose a graph\-based online GCHRL framework that addresses these challenges\. We construct a directed state graph online during exploration, incrementally incorporating visited states while pruning outdated nodes and connections\. We then train a model on this graph to predict state connectivity, which serves as a proxy for transition distance\. This connectivity measure is subsequently used to generate dense reward signals, enabling more efficient learning and improved understanding of the environment\.

The main contributions of this paper are as follows:

- •We introduce a method for the online construction of a directed state graph as a graph\-based environmental model\([Ha and Schmidhuber, 2018](https://arxiv.org/html/2609.10781#bib.bib13);[Zhang et al\., 2021](https://arxiv.org/html/2609.10781#bib.bib14)\)\. The graph is built directly during exploration, eliminating the need for expert data or manually designed structures\.
- •We propose a novel architecture that incorporates a state connectivity model to predict empirical connectivity between states based on observed arrivals\. This model allows the evaluation of newly visited states that are not yet represented in the graph\.
- •We leverage auxiliary rewards\([Simsek and Barto, 2006](https://arxiv.org/html/2609.10781#bib.bib12);[Nehmzow et al\., 2013](https://arxiv.org/html/2609.10781#bib.bib11)\), derived from state connectivity, to improve learning efficiency for the high\-level agent and to provide well\-calibrated learning signals for the low\-level agent\.
- •Our architecture is theoretically compatible with any GCHRL algorithm in both symmetric and asymmetric environments\. In our experiments, we evaluate it with four representative backbone methods \(HIRO, HRAC, HESS, and HLPS\), and observe performance improvements across a broad range of tasks\.

We evaluated our approach across a range of MuJoCo environments\([Todorov et al\., 2012](https://arxiv.org/html/2609.10781#bib.bib25)\)to assess the significance of our experimental results\. The results show that our method improves the performance of the underlying GCHRL framework in terms of success rate\.

## 2Preliminaries

### 2\.1Markov Decision Processes

As the most widely used framework for modeling reinforcement learning problems, the Markov Decision Process \(MDP\)\([Puterman, 2014](https://arxiv.org/html/2609.10781#bib.bib26)\)is defined as a tuple⟨𝒮,𝒜,P,R,γ⟩\\langle\\mathcal\{S\},\\mathcal\{A\},P,R,\\gamma\\rangle\. At each time steptt, the agent observes the current statest∈𝒮s\_\{t\}\\in\\mathcal\{S\}provided by the environment and selects an actionat∈𝒜a\_\{t\}\\in\\mathcal\{A\}according to its policyπ⁡\(at∣st\)\\pi\(a\_\{t\}\\mid s\_\{t\}\), which specifies the probability of choosing actionata\_\{t\}given statests\_\{t\}\.

Once the action is executed, the environment transitions the agent to a new statest\+1s\_\{t\+1\}according to the transition probability functionP⁡\(st\+1∣st,at\)P\(s\_\{t\+1\}\\mid s\_\{t\},a\_\{t\}\), which is typically unknown in model\-free settings\. The agent then receives a rewardrtr\_\{t\}determined by the reward functionR⁡\(st,at\)R\(s\_\{t\},a\_\{t\}\), which evaluates the action taken in the current state and is also not directly accessible to the agent\.

The objective of the agent is to learn an optimal policyπ\\pithat maximizes the expected discounted cumulative reward𝔼π​\[∑t=0Tγt​rt\]\\mathbb\{E\}\_\{\\pi\}\\big\[\\sum\_\{t=0\}^\{T\}\\gamma^\{t\}r\_\{t\}\\big\], whereγ∈\[0,1\)\\gamma\\in\[0,1\)is a predefined discount factor that prioritizes immediate rewards over those in the distant future, ensuring the total return remains finite\.

### 2\.2Goal\-conditioned Hierarchical RL \(GCHRL\)

Goal\-Conditioned Reinforcement Learning \(GCRL\)\([Liu et al\., 2023](https://arxiv.org/html/2609.10781#bib.bib2)\)extends standard reinforcement learning by training agents to achieve specific goals, typically defined as target states\. In this setting, the agent receives an additional goal inputgtg\_\{t\}alongside the statests\_\{t\}and learns a goal\-conditioned policyπ⁡\(at∣st,gt\)\\pi\(a\_\{t\}\\mid s\_\{t\},g\_\{t\}\)that aims to reach the desired goal\. By explicitly incorporating goals into the policy input, the agent’s behavior is guided toward achieving specified outcomes\. The reward function is often goal\-dependent, providing positive feedback when the agent successfully reaches the target state\.

To address the challenges posed by large and complex environments, Goal\-Conditioned Hierarchical Reinforcement Learning \(GCHRL\)\([Nachum et al\., 2018b](https://arxiv.org/html/2609.10781#bib.bib20);[Zhang et al\., 2022](https://arxiv.org/html/2609.10781#bib.bib24);[Wang et al\., 2024](https://arxiv.org/html/2609.10781#bib.bib23)\)decomposes the task into a hierarchy of simpler and more manageable sub\-tasks\. Typically, this framework consists of two levels of control\. For everyppsteps, the high\-level agent selects a subgoalgtg\_\{t\}, representing an intermediate target state, which is then passed to a low\-level agent for execution\. The subgoal is sampled from a high\-level policyπh​\(gt∣ϕ⁡\(st\)\)\\pi\_\{h\}\(g\_\{t\}\\mid\\phi\(s\_\{t\}\)\), whereϕ:𝒮→ℝd\\phi:\\mathcal\{S\}\\rightarrow\\mathbb\{R\}^\{d\}denotes a state representation function that maps the raw state to a compact feature space\.

Given the subgoalgtg\_\{t\}and the state representationϕ⁡\(st\)\\phi\(s\_\{t\}\), the low\-level policy selects an actionata\_\{t\}according to the policyπl​\(at∣ϕ⁡\(st\),gt\)\\pi\_\{l\}\(a\_\{t\}\\mid\\phi\(s\_\{t\}\),g\_\{t\}\)\. The low\-level policy is trained using an intrinsic reward signal defined asrint​\(st,gt,at,st\+1\)=−‖ϕ⁡\(st\+1\)−gt‖2r\_\{\\text\{int\}\}\(s\_\{t\},g\_\{t\},a\_\{t\},s\_\{t\+1\}\)=\-\\\|\\phi\(s\_\{t\+1\}\)\-g\_\{t\}\\\|\_\{2\}, which encourages the agent to minimize the distance between the achieved state representation and the subgoal\.

Both the high\-level and low\-level agents can be implemented using policy\-based reinforcement learning methods, including those developed in prior work on policy gradients, such as\([Fujimoto et al\., 2018](https://arxiv.org/html/2609.10781#bib.bib27);[Haarnoja et al\., 2018](https://arxiv.org/html/2609.10781#bib.bib28);[Schulman et al\., 2017](https://arxiv.org/html/2609.10781#bib.bib29)\)\.

### 2\.3Graph Abstraction of MDP

A graph is a general and flexible data structure for modeling complex relationships among objects in many real\-world problems\. A graph is defined as𝒢=\(𝒱,ℰ\)\\mathcal\{G\}=\(\\mathcal\{V\},\\mathcal\{E\}\), where\|𝒱\|=N\|\\mathcal\{V\}\|=Ndenotes the set of nodes andℰ=\{ei​j\}\\mathcal\{E\}=\\\{e\_\{ij\}\\\}denotes the set of edges \(without self\-loops\)\. The adjacency matrix of𝒢\\mathcal\{G\}is given by𝑨=\(𝑨i,j\)∈ℝN×N\{\\bm\{A\}\}=\(\{\\bm\{A\}\}\_\{i,j\}\)\\in\{\\mathbb\{R\}\}^\{N\\times N\}, where𝑨i,j=1\{\\bm\{A\}\}\_\{i,j\}=1if there exists an edge between nodesiiandjj, and𝑨i,j=0\{\\bm\{A\}\}\_\{i,j\}=0otherwise\.

This formulation can be naturally extended to a weighted adjacency matrix, in which𝑨i,j\{\\bm\{A\}\}\_\{i,j\}represents the weight associated with edgeei​je\_\{ij\}, capturing the strength or significance of the relationship\.

In the context of Markov Decision Processes \(MDPs\), nodes can be interpreted as states, while edge weights encode transition probabilities or reachability statistics between states\. Under this perspective, the graph serves as an abstract representation of the environment dynamics, capturing how states are interconnected through agent–environment interactions\([Lee et al\., 2022](https://arxiv.org/html/2609.10781#bib.bib19)\)\.

More generally, such a graph can be viewed as a compressed or learned structural model of the MDP\([Zhang et al\., 2025](https://arxiv.org/html/2609.10781#bib.bib5)\), where the connectivity reflects feasible transitions and the edge weights quantify their likelihood or frequency\. This abstraction is particularly useful in large or continuous state spaces, where explicitly modeling the full transition function is intractable\. By operating on the graph structure, one can exploit relational information between states to facilitate planning, exploration, and representation learning\.

## 3Methods

Previous work\([Zhang et al\., 2025](https://arxiv.org/html/2609.10781#bib.bib5)\)focuses on deriving dense rewards from undirected graphs, but this approach encounters difficulties in environments with directed connectivity, where state symmetry does not hold\. In this section, we present our framework, Graph\-Guided Quasimetric Dense Reward \(G2QDR\)111The term ’quasimetric’ in the method name does not imply that our approach explicitly or implicitly employs a quasimetric model\. Rather, it emphasizes the underlying motivation of the method: enabling the agent to distinguish between opposite directions of transition between states\., which explicitly models the state connectivity with a directed graph\. The overall structure of our framework within the traditional GCHRL pipeline is illustrated in Figure[1](https://arxiv.org/html/2609.10781#S3.F1)\.

![Refer to caption](https://arxiv.org/html/2609.10781v1/diagram.png)Figure 1:Overview of the G2QDR framework\.G2QDR serves as an auxiliary reward generator that takes the environmental state and interaction history as inputs, producing auxiliary rewards at multiple levels to facilitate the learning of both the high\-level and low\-level policies\.By integrating auxiliary rewards derived from state transitions with the original sparse rewards for both high\- and low\-level policies, the policy learning process more rapidly adapts to the underlying state connectivity structure\. This improves learning efficiency by encouraging more plausible subgoal proposals and more effective use of implicit spatial information\.

### 3\.1State graph

To record the visited states and their relationships, we maintain a directed state graph𝒢=\(𝒱,ℰ\)\\mathcal\{G\}=\(\\mathcal\{V\},\\mathcal\{E\}\)with a fixed numberNNof nodes222The number of training examples for the state connectivity model grows quadratically withNNbecause the adjacency weight matrix hasN2N^\{2\}elements\. The choice ofNNdepends on the machine’s capabilities\.\. This graph is built incrementally during the exploration phase of training, without relying on expert data or a handcrafted process\.

Each node is associated with a state\. For a node corresponding to statests\_\{t\}, we store the corresponding state representation vectorϕ⁡\(st\)∈ℝd\\phi\(s\_\{t\}\)\\in\{\\mathbb\{R\}\}^\{d\}as the node feature and usests\_\{t\}as the node label for simplicity\. The edges in the graph then represent the connectivity between states\.

We model the state graph as directed to capture the potentially asymmetric nature of transitions in directed connectivity environments; directed edges naturally encode these directional discrepancies\.

#### 3\.1\.1Incremental graph construction

The graph is initialized withNNempty nodes and no edges\. The corresponding weighted adjacency matrix𝑨\{\\bm\{A\}\}is set to anN×NN\\times Nzero matrix\. We explore the environment using the backbone agent with randomly initialized high\- and low\-level policiesπh\\pi\_\{h\}andπl\\pi\_\{l\}\. Whenever the agent encounters a previously unseen state representation—i\.e\., one that is sufficiently distant from all state representations currently stored in the graph, as defined in Equation \([1](https://arxiv.org/html/2609.10781#S3.E1)\), the state is added to the graph as a node, with the representationϕ⁡\(st\)\\phi\(s\_\{t\}\)as its feature\. We define a window of sizeWW, such that theWWmost recent preceding states are considered connected to the current state\. Accordingly, we create edges between the current node and the nodes corresponding to these preceding states, as shown in equation \([2](https://arxiv.org/html/2609.10781#S3.E2)\)\.

∀sv∈𝒱,‖ϕ⁡\(st\)−ϕ⁡\(sv\)‖2\>ϵd,\\forall\_\{s\_\{v\}\\in\\mathcal\{V\}\},\\,\\\|\\phi\(s\_\{t\}\)\-\\phi\(s\_\{v\}\)\\\|\_\{2\}\>\\epsilon\_\{d\},\(1\)𝑨st−w,st=w−p,w=1,…,W,\{\\bm\{A\}\}\_\{s\_\{t\-w\},s\_\{t\}\}=w^\{\-p\},\\ \\ w=1,\\dots,W,\(2\)whereϵd\\epsilon\_\{d\}is a hyperparameter that specifies the distance threshold between state representations, andp\>0p\>0is a hyperparameter that controls the polynomial decay’s exponent\. Naturally, we initialize the edge weight using the decayw−pw^\{\-p\}, as states that are farther apart in the trajectory \(i\.e\., largerww\) are considered more weakly connected\.

When the agent encounters a statests\_\{t\}with representationϕ⁡\(st\)\\phi\(s\_\{t\}\)that is similar to some node features already stored in the graph, it finds the state whose representation is the closest to the current state feature:

sv=arg​minsu:‖ϕ⁡\(st\)−ϕ⁡\(su\)‖2≤ϵd∥ϕ\(st\)−ϕ\(su\)∥2\.s\_\{v\}=\\argmin\_\{s\_\{u\}:\\\|\\phi\(s\_\{t\}\)\-\\phi\(s\_\{u\}\)\\\|\_\{2\}\\leq\\epsilon\_\{d\}\}\\\|\\phi\(s\_\{t\}\)\-\\phi\(s\_\{u\}\)\\\|\_\{2\}\.\(3\)Then, we treat the statests\_\{t\}assvs\_\{v\}, relabel the nodesvs\_\{v\}assts\_\{t\}, and relabel the corresponding edges accordingly\. The weight for the edge\(st−w,st\)\(s\_\{t\-w\},s\_\{t\}\)is then updated as follows:

𝑨st−w,st:=𝑨st−w,st\+w−p,w=1,…,W\.\{\\bm\{A\}\}\_\{s\_\{t\-w\},s\_\{t\}\}:=\{\\bm\{A\}\}\_\{s\_\{t\-w\},s\_\{t\}\}\+w^\{\-p\},\\ \\ w=1,\\dots,W\.\(4\)Note that larger weights correspond to more frequent transitions between the underlying states\. Conversely, for states that are farther apart in the trajectory \(i\.e\., with largerww\), the incrementw−pw^\{\-p\}is smaller, reflecting the weaker connection between them\.

We use the Euclidean norm to measure the distance between representation vectors\. However, since some components may encode more spatial information than others, a weighted Euclidean norm can alternatively be employed to define distances between state representations, allowing the metric to better reflect the structure of the environment\.

#### 3\.1\.2Updating in a full graph

The graph has a fixed number of nodes\. Suppose the graph is full, when a new statests\_\{t\}is encountered, ifsvs\_\{v\}from equation \([3](https://arxiv.org/html/2609.10781#S3.E3)\) exists, as before we relabel the node assvs\_\{v\}and perform edge update as shown in equation \([4](https://arxiv.org/html/2609.10781#S3.E4)\); Otherwise, we replace the oldest state node in the graph with the current state node, delete all edges previously linked to that node, and initialize the edges using equation \([2](https://arxiv.org/html/2609.10781#S3.E2)\)\. Alternatively, one could replace the node that is most weakly connected to the rest of the graph—that is, the node with the lowest sum of edge weights\.

### 3\.2State connectivity model

To assign appropriate connectivity strengths to all possible state pairs, including those not yet observed, we use node features and edges to train a state connectivity model, which predicts connectivity strengths between unseen states whose representations are not stored in the graph\.

The model𝒞θ\\mathcal\{C\}\_\{\\theta\}maps every paired state representationψ⁡\(su,sv\)\\psi\(s\_\{u\},s\_\{v\}\), which is a column vector, to a connectivity scorecc, whereθ\\thetadenotes its parameters\. We instantiate𝒞θ\\mathcal\{C\}\_\{\\theta\}as a multi\-layer feed\-forward network \(FFN\):

c=𝒞θ​\(ψ⁡\(su,sv\)\)=FFN​\(ψ⁡\(su,sv\)\)\.c=\\mathcal\{C\}\_\{\\theta\}\(\\psi\(s\_\{u\},s\_\{v\}\)\)=\\text\{FFN\}\(\\psi\(s\_\{u\},s\_\{v\}\)\)\.\(5\)
The state connectivity model and the policies are updated alternately during policy training\.

##### Order\-sensitive paired state representation

Since transition distances between states are often asymmetric, the paired\-state representation should be order\-dependent to enable learning asymmetric state connectivities \(i\.e\.𝒞θ​\(ψ⁡\(su,sv\)\)≠𝒞θ​\(ψ⁡\(sv,su\)\)\\mathcal\{C\}\_\{\\theta\}\(\\psi\(s\_\{u\},s\_\{v\}\)\)\\neq\\mathcal\{C\}\_\{\\theta\}\(\\psi\(s\_\{v\},s\_\{u\}\)\)\)\. Here, we propose some candidates for order\-sensitive paired state representation:

- •Vector ConcatenationThe inputψ⁡\(su,sv\)=\[ϕ⁡\(su\)ϕ⁡\(sv\)\]∈ℝ2​d\\psi\(s\_\{u\},s\_\{v\}\)=\\begin\{bmatrix\}\\phi\(s\_\{u\}\)\\\\ \\phi\(s\_\{v\}\)\\end\{bmatrix\}\\in\{\\mathbb\{R\}\}^\{2d\}is just a simple concatenation of the two state representation vectors\. In this case, the intermediate layers of𝒞θ\\mathcal\{C\}\_\{\\theta\}learn higher\-level features of the paired inputψ⁡\(su,sv\)\\psi\(s\_\{u\},s\_\{v\}\)\.
- •Gated FusionThe inputψ⁡\(su,sv\)∈ℝd\\psi\(s\_\{u\},s\_\{v\}\)\\in\\mathbb\{R\}^\{d\}is computed via gated fusion parameterized by learnable weights𝑾∈ℝd×2​d\{\\bm\{W\}\}\\in\\mathbb\{R\}^\{d\\times 2d\}and biases𝒃∈ℝd\\bm\{b\}\\in\{\\mathbb\{R\}\}^\{d\}: g⁡\(su,sv\)=σ⁡\(𝑾​\[ϕ⁡\(su\)ϕ⁡\(sv\)\]\+𝒃\)∈ℝd,ψ⁡\(su,sv\)=g⁡\(su,sv\)⊙ϕ⁡\(su\)\+\(1−g⁡\(su,sv\)\)⊙ϕ⁡\(sv\),g\(s\_\{u\},s\_\{v\}\)=\\sigma\(\{\\bm\{W\}\}\\begin\{bmatrix\}\\phi\(s\_\{u\}\)\\\\ \\phi\(s\_\{v\}\)\\end\{bmatrix\}\+\\bm\{b\}\)\\in\{\\mathbb\{R\}\}^\{d\},\\ \\psi\(s\_\{u\},s\_\{v\}\)=g\(s\_\{u\},s\_\{v\}\)\\odot\\phi\(s\_\{u\}\)\+\(1\-g\(s\_\{u\},s\_\{v\}\)\)\\odot\\phi\(s\_\{v\}\),\(6\)whereσ\\sigmais a gating function\. Gated fusion learns the contribution of each input at the feature level\. Instead of enforcing a fixed combination, it enables data\-dependent weighting between the two inputs\. Consequently, the representationsψ⁡\(su,sv\)\\psi\(s\_\{u\},s\_\{v\}\)andψ⁡\(sv,su\)\\psi\(s\_\{v\},s\_\{u\}\)are distinctly different, rather than being related by a simple permutation\.

##### Training loss

Naturally we can use𝑨su,sv\{\\bm\{A\}\}\_\{s\_\{u\},s\_\{v\}\}as a measure of connectivity between nodessus\_\{u\}andsvs\_\{v\}\. However, to constrain the scale of the network outputs during training, we instead normalize this quantity as𝑨su,sv/maxsi,sj⁡𝑨si,sj\{\\bm\{A\}\}\_\{s\_\{u\},s\_\{v\}\}/\\max\_\{s\_\{i\},s\_\{j\}\}\{\\bm\{A\}\}\_\{s\_\{i\},s\_\{j\}\}\.

Accordingly, the loss function is defined as:

ℒ=∑ϕ⁡\(su\),ϕ⁡\(sv\)∈𝒱\[𝒞θ​\(ψ⁡\(su,sv\)\)−𝑨su,sv/maxsi,sj⁡𝑨si,sj\]2\.\\mathcal\{L\}=\\sum\_\{\\phi\(s\_\{u\}\),\\phi\(s\_\{v\}\)\\in\\mathcal\{V\}\}\\big\[\\mathcal\{C\}\_\{\\theta\}\(\\psi\(s\_\{u\},s\_\{v\}\)\)\-\{\\bm\{A\}\}\_\{s\_\{u\},s\_\{v\}\}/\\max\_\{s\_\{i\},s\_\{j\}\}\{\\bm\{A\}\}\_\{s\_\{i\},s\_\{j\}\}\\big\]^\{2\}\.\(7\)
This loss function encourages the model to preserve the local neighbourhood structure of the graph in its predictions\. In doing so, the model learns the empirical connectivity between states as induced by the graph\.

Note that in each training phase of the model \(except the first\), the parameters are initialized using the values learned in the previous phase, which serves as a good initial point\.

### 3\.3Induced dense reward

Our proposed method introduces induced dense reward signals across all levels of agents in traditional goal\-conditioned settings, enabling better utilization of experienced environmental dynamics and promoting more efficient learning\.

##### High\-level constraint reward

The high\-level policyπh​\(gt\|ϕ⁡\(st\)\)\\pi\_\{h\}\(g\_\{t\}\|\\phi\(s\_\{t\}\)\)proposes a subgoal everyPPsteps and is trained using the external environmental rewardrextr\_\{\\text\{ext\}\}\. It can be implemented using any policy\-based reinforcement learning algorithm that operates on transition tuples\(st,gt,rt,st\+1\)\(s\_\{t\},g\_\{t\},r\_\{t\},s\_\{t\+1\}\)

To promote more efficient exploration, we encourage the policy to generate subgoals that are easier to reach from the current statests\_\{t\}\. Specifically, we augment the high\-level reward with an intrinsic term that rewards strong connections between the current statests\_\{t\}and generated subgoalgtg\_\{t\}\. The resulting reward is defined as follows:

rh​\(st,gt,st\+1\)=rext\+rint=rext\+αh⋅𝒞θ​\(ψ⁡\(st,gt\)\),r\_\{h\}\(s\_\{t\},g\_\{t\},s\_\{t\+1\}\)=r\_\{\\text\{ext\}\}\+r\_\{\\text\{int\}\}=r\_\{\\text\{ext\}\}\+\\alpha\_\{h\}\\cdot\\mathcal\{C\}\_\{\\theta\}\(\\psi\(s\_\{t\},g\_\{t\}\)\),\(8\)whereαh≥0\\alpha\_\{h\}\\geq 0is a hyperparameter that controls the significance of the intrinsic term in the high\-level reward\.

##### Low\-level correction reward

The low\-level policyπl​\(at\|ϕ⁡\(st\),gt\)\\pi\_\{l\}\(a\_\{t\}\|\\phi\(s\_\{t\}\),g\_\{t\}\)can be implemented using any policy\-based reinforcement learning algorithm that operates on transition tuples\(st,gt,at,rt,st\+1\)\(s\_\{t\},g\_\{t\},a\_\{t\},r\_\{t\},s\_\{t\+1\}\)\. In the traditional low\-level policy learning process\([Nachum et al\., 2018b](https://arxiv.org/html/2609.10781#bib.bib20)\), the policy learns exclusively from reward signals derived from the Euclidean distance between the subsequent state representation and the subgoal\. However, this approach is limited as it ignores environmental connectivity and fails to reflect the \(true\) transition distance between states accurately\. We address this limitation by introducing a connectivity\-based term as follows:

rl​\(st,gt,at,st\+1\)=−‖ϕ⁡\(st\+1\)−gt‖2\+αl⋅𝒞θ​\(ψ⁡\(st\+1,gt\)\),r\_\{l\}\(s\_\{t\},g\_\{t\},a\_\{t\},s\_\{t\+1\}\)=\-\\\|\\phi\(s\_\{t\+1\}\)\-g\_\{t\}\\\|\_\{2\}\+\\alpha\_\{l\}\\cdot\\mathcal\{C\}\_\{\\theta\}\(\\psi\(s\_\{t\+1\},g\_\{t\}\)\),\(9\)whereαl≥0\\alpha\_\{l\}\\geq 0is a hyperparameter controlling the significance of the reward term in the low\-level reward\.

##### Asymmetric penalty

In certain environments, asymmetric transitions can prevent an agent from reaching its goal \(e\.g\., one\-way dead ends, pits, or cliffs\)\. In such cases, a statesvs\_\{v\}may be easily reachable fromsus\_\{u\}, while the reverse transition fromsvs\_\{v\}tosus\_\{u\}is significantly more difficult or unlikely\. To capture this asymmetry, we compare the learned directed connectivity scores𝒞θ​\(ψ⁡\(su,sv\)\)\\mathcal\{C\}\_\{\\theta\}\(\\psi\(s\_\{u\},s\_\{v\}\)\)and𝒞θ​\(ψ⁡\(sv,su\)\)\\mathcal\{C\}\_\{\\theta\}\(\\psi\(s\_\{v\},s\_\{u\}\)\), which serve as proxies for transition ease in each direction\.

We define penalty terms for both the high\- and low\-level policies as:

rh​p=−αh​p⋅max\(𝒞θ\(ψ\(st,gt\)\)−𝒞θ\(ψ\(gt,st\)\),0\),rl​p=−αl​p⋅max\(𝒞θ\(ψ\(st,st\+1\)\)−𝒞θ\(ψ\(st\+1,st\)\),0\)\.r\_\{hp\}=\-\\alpha\_\{hp\}\\cdot\\max\(\\mathcal\{C\}\_\{\\theta\}\(\\psi\(s\_\{t\},g\_\{t\}\)\)\-\\mathcal\{C\}\_\{\\theta\}\(\\psi\(g\_\{t\},s\_\{t\}\)\),0\),\\quad r\_\{lp\}=\-\\alpha\_\{lp\}\\cdot\\max\(\\mathcal\{C\}\_\{\\theta\}\(\\psi\(s\_\{t\},s\_\{t\+1\}\)\)\-\\mathcal\{C\}\_\{\\theta\}\(\\psi\(s\_\{t\+1\},s\_\{t\}\)\),0\)\.\(10\)whereαh​p≥0\\alpha\_\{hp\}\\geq 0andαl​p≥0\\alpha\_\{lp\}\\geq 0are hyperparameters, which control the strength of the penalty\. The asymmetric gap𝒞θ​\(ψ⁡\(su,sv\)\)−𝒞θ​\(ψ⁡\(sv,su\)\)\\mathcal\{C\}\_\{\\theta\}\(\\psi\(s\_\{u\},s\_\{v\}\)\)\-\\mathcal\{C\}\_\{\\theta\}\(\\psi\(s\_\{v\},s\_\{u\}\)\)quantifies directional irreversibility\. A large positive gap indicates that the transition fromsus\_\{u\}tosvs\_\{v\}is substantially easier than the reverse, suggesting a potentially hazardous or trapping structure in the environment\.

The use of themax⁡\(⋅,0\)\\max\(\\cdot,0\)operator ensures that only risky asymmetry is penalized\. Without this clipping, the term could encourage the agent to favour transitions that are difficult to reach but easy to leave, which is an undesirable and unintended behavior\. This penalty encourages both high\- and low\-level policies to remain within regions of the state space that exhibit more balanced bidirectional connectivity, corresponding to more reversible and safer transitions\.

### 3\.4Evolution of dense signal strength

Due to the varying quality of the dense signal across different training stages, we introduce a stage\-dependent controllerλ\\lambdato modulate the induced reward terms\. Specifically, the hyperparametersαh\\alpha\_\{h\},αl\\alpha\_\{l\},αh​p\\alpha\_\{hp\}, andαl​p\\alpha\_\{lp\}are all scaled byλ\\lambda\. Letntn\_\{t\}denote the current episode, with the activation phase spanning episodesn1n\_\{1\}ton2n\_\{2\}and the annealing phase spanning episodesn3n\_\{3\}ton4n\_\{4\}\. The controller is defined as:

λ=\{0warm\-up stagent−n1n2−n1activation stage1full reward stagen4−ntn4−n3annealing stage0final stage\\lambda=\\begin\{cases\}0&\\text\{warm\-up stage\}\\\\ \\frac\{n\_\{t\}\-n\_\{1\}\}\{n\_\{2\}\-n\_\{1\}\}&\\text\{activation stage \}\\\\ 1&\\text\{full reward stage \}\\\\ \\frac\{n\_\{4\}\-n\_\{t\}\}\{n\_\{4\}\-n\_\{3\}\}&\\text\{annealing stage \}\\\\ 0&\\text\{final stage\}\\end\{cases\}\(11\)
The construction of the graph and the training of the state connectivity model follow a bootstrapping process: in early episodes, the graph covers only a limited region of the environment, its edges are poorly calibrated, and the model is correspondingly biased\. Therefore, during the warm\-up stage, the graph is used to update the model, but the model is not used for policy learning \(i\.e\.,λ=0\\lambda=0\), reflecting the limited reliability of the graph and the model\.

In the activation stage, we linearly increaseλ\\lambdafrom00to11, gradually introducing the dense signal induced by our model\. This additional signal guides more efficient exploration and policy learning\.λ\\lambdais fixed to11afterwards, in the full reward stage\.

In the annealing stage, since the dense reward is not potential\-based\([Ng et al\., 1999](https://arxiv.org/html/2609.10781#bib.bib6)\), it not only alters the optimal policy but also changes the underlying optimization problem\. To realign with the original task, we gradually phase out the dense signal by decreasingλ\\lambdafrom11to00\. In the final stage,λ\\lambdais fixed to00\.

### 3\.5Algorithm: GCHRL \+ G2QDR

A detailed description of how the proposed G2QDR strategy can be integrated into online GCHRL algorithms is provided in Algorithm[1](https://arxiv.org/html/2609.10781#alg1)\.

Algorithm 1GCHRL\+G2QDRInput:High\-level policy

πh​\(g∣ϕ​\(s\)\)\\pi\_\{h\}\(g\\mid\\phi\(s\)\), low\-level policy

πl​\(a∣ϕ​\(s\),g\)\\pi\_\{l\}\(a\\mid\\phi\(s\),g\), replay buffer

ℬ\\mathcal\{B\}, state connectivity model

𝒞θ\\mathcal\{C\}\_\{\\theta\}, high\-level action frequency

KK, window size

WW, significance thresholds

αh\\alpha\_\{h\},

αl\\alpha\_\{l\},

αh​p\\alpha\_\{hp\},

αl​p\\alpha\_\{lp\}, adaptive signal strength

λ\\lambda, number of episodes

NN, maximum number of steps per episode

TT\.

n←0n\\leftarrow 0;

while*n<Nn<N*do

t←0t\\leftarrow 0;

while*t<Tt<T*do

if*tmodK=0t\\bmod K=0*then

Sample subgoal

gt∼πh\(⋅∣ϕ\(st\)\)g\_\{t\}\\sim\\pi\_\{h\}\(\\cdot\\mid\\phi\(s\_\{t\}\)\);

else

Retain the current subgoal

gtg\_\{t\};

Sample atomic action

at∼πl\(⋅∣ϕ\(st\),gt\)a\_\{t\}\\sim\\pi\_\{l\}\(\\cdot\\mid\\phi\(s\_\{t\}\),g\_\{t\}\);

Execute

ata\_\{t\}and observe reward

rtr\_\{t\}and next state

st\+1s\_\{t\+1\};

if*λ≠0\\lambda\\neq 0*then

Compute

rh​\(st,gt,st\+1\)r\_\{h\}\(s\_\{t\},g\_\{t\},s\_\{t\+1\}\),

rl​\(st,gt,at,st\+1\)r\_\{l\}\(s\_\{t\},g\_\{t\},a\_\{t\},s\_\{t\+1\}\), and penalty terms

rh​pr\_\{hp\}and

rl​pr\_\{lp\}using Eqs\. \([8](https://arxiv.org/html/2609.10781#S3.E8)\), \([9](https://arxiv.org/html/2609.10781#S3.E9)\), and \([10](https://arxiv.org/html/2609.10781#S3.E10)\);

Store transition

\(st,gt,at,λ,\[rext,−‖ϕ⁡\(st\+1\)−gt‖2,𝒞θ​\(ψ⁡\(st,gt\)\),𝒞θ​\(ψ⁡\(st\+1,gt\)\),rh​p,rl​p\],st\+1\)\(s\_\{t\},g\_\{t\},a\_\{t\},\\lambda,\[r\_\{\\mathrm\{ext\}\},\-\\\|\\phi\(s\_\{t\+1\}\)\-g\_\{t\}\\\|\_\{2\},\\mathcal\{C\}\_\{\\theta\}\(\\psi\(s\_\{t\},g\_\{t\}\)\),\\mathcal\{C\}\_\{\\theta\}\(\\psi\(s\_\{t\+1\},g\_\{t\}\)\),r\_\{hp\},r\_\{lp\}\],s\_\{t\+1\}\)in replay buffer

ℬ\\mathcal\{B\};

else

Store transition

\(st,gt,at,0,\[rext,−‖ϕ⁡\(st\+1\)−gt‖2,0,0,0,0\],st\+1\)\(s\_\{t\},g\_\{t\},a\_\{t\},0,\[r\_\{\\mathrm\{ext\}\},\-\\\|\\phi\(s\_\{t\+1\}\)\-g\_\{t\}\\\|\_\{2\},0,0,0,0\],s\_\{t\+1\}\)in replay buffer

ℬ\\mathcal\{B\};

Update graph node representations and edge weights using the collected transition and Eqs\. \([1](https://arxiv.org/html/2609.10781#S3.E1)\)–\([4](https://arxiv.org/html/2609.10781#S3.E4)\);

Update the state connectivity model

𝒞θ\\mathcal\{C\}\_\{\\theta\}using the current graph structure;

t←t\+1t\\leftarrow t\+1;

Update the low\-level policy

πl​\(a∣ϕ​\(s\),g\)\\pi\_\{l\}\(a\\mid\\phi\(s\),g\)using the selected GCHRL learning algorithm and samples from

ℬ\\mathcal\{B\};

Update the high\-level policy

πh​\(g∣ϕ​\(s\)\)\\pi\_\{h\}\(g\\mid\\phi\(s\)\)using the selected GCHRL learning algorithm and samples from

ℬ\\mathcal\{B\};

Update the adaptive signal strength

λ\\lambdaaccording to the current episode index

nn;

n←n\+1n\\leftarrow n\+1;

## 4Experiments

As is standard in the GCHRL community, we evaluate our method across a range of long\-horizon continuous control tasks simulated in the MuJoCo\([Todorov et al\., 2012](https://arxiv.org/html/2609.10781#bib.bib25)\)environment\. In this section, we employ gated fusion to construct an order\-sensitive representation of state pairs\.

### 4\.1Environment settings

We adopt theAntMaze,AntGather,AntPush,AntFall, andPusherenvironments from MuJoCo, all configured with sparse reward settings\. The first four involve complex navigation and manipulation tasks performed by a simulated multi\-limbed robot, whereasPusherfocuses on object manipulation using a multi\-jointed robotic arm\. These environments exhibit varying degrees of asymmetry in their state transitions\.AntMazeis largely symmetric, as the agent can relatively easily return to previously visited states\. In contrast,AntGather,AntPush,AntFall, andPusherexhibit different types of asymmetry: reversing object displacement in AntGather, AntPush and Pusher is considerably more difficult, and ascending cliffs in AntFall is substantially harder than descending them\.

### 4\.2Comparative analysis

We incorporated G2QDR in the following existing GCHRL methods:

- •HIRO\([Nachum et al\., 2018b](https://arxiv.org/html/2609.10781#bib.bib20)\): One of the earliest approaches to demonstrate effective integration of goal\-conditioned information in online hierarchical reinforcement learning\.
- •HRAC\([Zhang et al\., 2022](https://arxiv.org/html/2609.10781#bib.bib24)\): Extends HIRO by introducing an adjacency network that generates subgoals which are more readily reachable from the current state, thereby improving overall performance\.
- •HESS\([Li et al\., 2022](https://arxiv.org/html/2609.10781#bib.bib32)\): This method adds a regularization term over consecutive subgoal representations during each update to promote stability across episodes\.
- •HLPS\([Wang et al\., 2024](https://arxiv.org/html/2609.10781#bib.bib23)\): Uses a Gaussian process over subgoal representations to enable smoother and more consistent updates\.

In addition to comparing these four G2QDR\-augmented methods with their original counterparts, we also evaluate them against the following undirected\-graph baseline to highlight the advantages of directed graph learning in asymmetric environments:

- •G4RL\([Zhang et al\., 2025](https://arxiv.org/html/2609.10781#bib.bib5)\): A plug\-in state connectivity estimator based on undirected graphs\. It employs a graph encoder–decoder to learn the subgoal space and estimate transition plausibility from learned subgoal representations\.

We report average success rates onAntMaze,AntPush,AntFall, andPusher, along with the average number of objects collected inAntGather\(Table[1](https://arxiv.org/html/2609.10781#S4.T1)\)\. All results are averaged over 10 independent runs and reported as the mean±\\pmstandard deviation\.

The agents are trained for a total of 20000 episodes in each environment\. Every 1,000 training episodes, the current policy is evaluated over 100 independent evaluation trials without further learning\. The performance metric is the success rate, defined as the percentage of trials in which the agent completes the task\. The success rate is recorded after each evaluation to monitor the learning progress\.

Table 1:Main results on MuJoCo environments across different methods\.For each method, we report the performance of the original baseline together with its undirected variant \(\+G4RL\) and directed variant \(\+G2QDR\)\. The variant\(\+G2QDR w/o PT\)applies G2QDR with combined constraints and corrections but without penalty terms, while\(\+G2QDR w/ PT\)additionally incorporates penalty terms\. All results are reported at the final training episode\. Within each method group, the best\-performing variant is underlined\.From Table[1](https://arxiv.org/html/2609.10781#S4.T1), we observe that incorporating G2QDR into the base GCHRL methods generally improves performance across the evaluated environments\. In many cases, the G2QDR\-augmented variants achieve higher final success rates than their corresponding baselines while also exhibiting lower performance variance\. These improvements are particularly pronounced in tasks that heuristically exhibit a higher degree of asymmetry\. Although the gains are not consistent across all environments, the overall trend indicates that G2QDR enhances both the effectiveness and the stability of the underlying methods\.

In asymmetric environments, G2QDR typically provides larger improvements over both the original baselines and the undirected G4RL variant\. These results indicate that explicitly modeling directional relationships can be particularly beneficial in environments with asymmetric dynamics\.

### 4\.3Ablation study

#### 4\.3\.1Impact of auxiliary reward components

To evaluate the effectiveness of different auxiliary reward components within G2QDR, we consider the following variants:

- •a: High\-level constraint rewards only: Equation \([8](https://arxiv.org/html/2609.10781#S3.E8)\) is applied to the high\-level rewards, while the low\-level significance is set toαl=0\\alpha\_\{l\}=0in equation \([9](https://arxiv.org/html/2609.10781#S3.E9)\)\.
- •b: Low\-level correction rewards only: Equation \([9](https://arxiv.org/html/2609.10781#S3.E9)\) is applied to the low\-level rewards, while the high\-level significance is set toαh=0\\alpha\_\{h\}=0in equation \([8](https://arxiv.org/html/2609.10781#S3.E8)\)\.
- •c: Combined constraint rewards and correction rewards: Equations \([8](https://arxiv.org/html/2609.10781#S3.E8)\) and \([9](https://arxiv.org/html/2609.10781#S3.E9)\) are applied simultaneously to the high\-level and low\-level reward structures, respectively\.
- •d: Full G2QDR \(with penalty terms\): Both equations \([8](https://arxiv.org/html/2609.10781#S3.E8)\) and \([9](https://arxiv.org/html/2609.10781#S3.E9)\) are applied as in variant c, supplemented by the additional penalty terms defined in equation \([10](https://arxiv.org/html/2609.10781#S3.E10)\)\.
- •Baselines \(HIRO/HRAC/HESS/HLPS\): Standard implementations of the vanilla baseline methods for performance comparison\.

As before, all data reported in this section are averaged over 10 independent runs and reported as the mean±\\pmstandard deviation\.

Table 2:Ablation study of G2QDR variants\. For each method, we report the performance of the original baseline together with its variants augmented by different types of auxiliary rewards \(a–d\)\. All results correspond to the final training episode\. Within each method group, the best\-performing variant is underlined\.Table[2](https://arxiv.org/html/2609.10781#S4.T2)presents the results of the ablation study across all evaluated environments and algorithms\. Overall, combining high\-level constraints and low\-level corrections \(variant \(c\)\) yields strong performance, often outperforming the use of either component in isolation\. While the full G2QDR variant with penalty terms \(d\) further improves performance in several tasks, it does not uniformly dominate variant c, indicating that the effect of the penalty is environment\-dependent\.

In environments where Euclidean distance is a poor proxy for the actual transition distances, for example, inAntMaze, where walls separate states that are close in Euclidean space but far in terms of transition distance, incorporating the low\-level correction term leads to clear and consistent gains, highlighting its role in improving local policy accuracy\. The high\-level constraint term also contributes to performance improvements by guiding the policy toward more feasible subgoals, although its effect is generally more pronounced when combined with low\-level corrections\.

The penalty term exhibits mixed behavior across tasks\. It tends to improve performance in environments with asymmetric or partially irreversible dynamics, such as Pusher and AntPush, where it discourages transitions to states that are easy to reach but difficult to recover from\. However, in more symmetric environments, the same penalty can restrict exploration and slightly degrade performance\. These results suggest that, while the full G2QDR formulation is beneficial in certain settings, the combination of constraints and corrections alone provides strong performance overall\.

#### 4\.3\.2Balancing between time and performance

Several aspects of our method involve a tradeoff between performance and computational cost:

- •State sampling frequency:Lowering the sampling frequency of candidate states for node features reduces comparisons during graph updates but may weaken the graph’s representativeness\.
- •Training data selection:Training𝒞θ\\mathcal\{C\}\_\{\\theta\}on a subset of node pairs and edges speeds up training, at the potential cost of accuracy\.

We first vary the sampling frequency of candidate states used as node features, considering intervals of 1, 5, and 10 steps in HLPS forAntPushandPusher\.

All curves reported in Section[4](https://arxiv.org/html/2609.10781#S4)represent averages over 10 independent runs, with standard deviations shown as shaded regions\. For clarity, all results are uniformly smoothed for visualization\.

Figure 2:Success rates on \(a\) AntPush and \(b\) Pusher using HLPS\+G2QDR\. The number of steps in the legend denotes the chosen state sampling frequency, and the timescale is reported relative to the vanilla HLPS algorithm\. Increasing the sampling interval substantially reduces computation time, with only minor degradation in success rates across both tasks\.As shown in Figure[2](https://arxiv.org/html/2609.10781#S4.F2), increasing the sampling interval substantially reduces computation time by reducing the number of graph interactions, while causing only minor degradation in success rates across both tasks\.

Next, we vary the proportion of training data used for the state connectivity model, evaluating sizes of50%50\\%,75%75\\%, and100%100\\%of all available training samples in the graph\. The results in Figure[3](https://arxiv.org/html/2609.10781#S4.F3)show that reducing the amount of training data yields only modest improvements in computational efficiency\. In particular, decreasing the dataset size slightly shortens computation time, but the gains are limited\. At the same time, the success rates on both AntPush and Pusher remain largely stable, with only minor degradation when using75%75\\%of the available training samples\. This suggests that G2QDR is relatively robust to moderate data reductions and does not rely heavily on the full dataset to achieve strong performance\.

Figure 3:Success rate on \(a\) AntPush and \(b\) Pusher using HLPS\+G2QDR\. The percentages in the legend indicate the proportion of training samples used relative to the total number of edges in the graph\. The timescale is computed with respect to the vanilla HLPS algorithm\. Reducing the amount of data slightly decreases computation time; using75%75\\%of the data results in only minor degradation in success rates across both AntPush and Pusher tasks\.These findings suggest that the primary computational bottleneck of G2QDR lies in the graph construction and node comparison procedures described in Section[3\.1\.1](https://arxiv.org/html/2609.10781#S3.SS1.SSS1), rather than in the model training stage\. Consequently, adjusting the sampling frequency emerges as an effective way to reduce computational cost, while largely preserving the performance gains provided by G2QDR integration\.

### 4\.4Experimental analysis of dense signal schedule variations

This section examines how different dense reward schedules influence the performance of G2QDR\. We introduce several variants of dense signal schedules, illustrated in Figure[4](https://arxiv.org/html/2609.10781#S4.F4)\(b\), and present the corresponding success rate curves forPusherusing HLPS\+G2QDR in Figure[4](https://arxiv.org/html/2609.10781#S4.F4)\(a\)\.

Figure 4:Ablation study of dense signal\-strength scheduling\.Left:Training curves under differentλ\\lambdaschedules\.Right:Evolution of the scheduling parameterλ\\lambdaacross episodes\.From Figure[4](https://arxiv.org/html/2609.10781#S4.F4), several key observations can be drawn\. An immediate full reward setting \(λ=1\\lambda=1\) leads to slower convergence compared to other configurations, suggesting that instability in the state graph and the state connectivity model adversely affects both efficiency and convergence speed of the backbone method\. Moreover, keepingλ\\lambdahigh throughout later episodes results in inferior performance relative to variants that apply late\-stage annealing\. In contrast, a well\-designed schedule forλ\\lambdaenables the architecture to achieve its full potential\.

## 5Conclusion

In this paper, we present a unified framework for graph\-based GCHRL that incrementally constructs a directed state graph during exploration, learns a state connectivity model to estimate transition feasibility and evaluate newly encountered states, and leverages connectivity\-based auxiliary rewards to enhance learning efficiency across multiple levels of agents\.

Building upon the G4RL framework\([Zhang et al\., 2025](https://arxiv.org/html/2609.10781#bib.bib5)\), our approach improves and extends its capabilities by explicitly modeling asymmetric state transitions, making it well\-suited for asymmetric environments where transition dynamics are inherently directional and non\-reversible\. This enhancement allows the architecture to better capture realistic environment structures that are often overlooked by symmetric assumptions\.

The proposed framework is broadly compatible with existing GCHRL methods, enabling seamless integration with a wide range of prior approaches\. Empirical evaluations across diverse environments demonstrate consistent improvements over baseline methods, highlighting the effectiveness and robustness of our approach\.

Overall, this work highlights the importance of modeling directional structure in state spaces for goal\-conditioned hierarchical reinforcement learning\. By translating state connectivity into auxiliary rewards, the proposed framework offers a flexible and scalable approach for tackling complex environments\.

## References

- Duanet al\.\(2016\)Y\. Duan, X\. Chen, R\. Houthooft, J\. Schulman, and P\. AbbeelBenchmarking deep reinforcement learning for continuous control\.InInternational conference on machine learning,pp\. 1329–1338\.Cited by:[§B\.1](https://arxiv.org/html/2609.10781#A2.SS1.p3.1)\.
- Eysenbachet al\.\(2019\)B\. Eysenbach, R\. R\. Salakhutdinov, and S\. LevineSearch on the replay buffer: bridging planning and reinforcement learning\.Advances in neural information processing systems32\.Cited by:[§1](https://arxiv.org/html/2609.10781#S1.p3.1)\.
- Fujimotoet al\.\(2018\)S\. Fujimoto, H\. Hoof, and D\. MegerAddressing function approximation error in actor\-critic methods\.InInternational conference on machine learning,pp\. 1587–1596\.Cited by:[§1](https://arxiv.org/html/2609.10781#S1.p1.1),[§2\.2](https://arxiv.org/html/2609.10781#S2.SS2.p4.1)\.
- Gieselmann and Pokorny \(2021\)R\. Gieselmann and F\. T\. PokornyPlanning\-augmented hierarchical reinforcement learning\.IEEE Robotics and Automation Letters6\(3\),pp\. 5097–5104\.Cited by:[§1](https://arxiv.org/html/2609.10781#S1.p3.1)\.
- Ha and Schmidhuber \(2018\)D\. Ha and J\. SchmidhuberWorld models\.arXiv preprint arXiv:1803\.10122\.Cited by:[1st item](https://arxiv.org/html/2609.10781#S1.I1.i1.p1.1)\.
- Haarnojaet al\.\(2018\)T\. Haarnoja, A\. Zhou, K\. Hartikainen, G\. Tucker, S\. Ha, J\. Tan, V\. Kumar, H\. Zhu, A\. Gupta, P\. Abbeel,et al\.Soft actor\-critic algorithms and applications\.arXiv preprint arXiv:1812\.05905\.Cited by:[§1](https://arxiv.org/html/2609.10781#S1.p1.1),[§2\.2](https://arxiv.org/html/2609.10781#S2.SS2.p4.1)\.
- Honget al\.\(2022\)Z\. Hong, T\. Chen, Y\. Lin, J\. Pajarinen, and P\. AgrawalTopological experience replay\.arXiv preprint arXiv:2203\.15845\.Cited by:[§1](https://arxiv.org/html/2609.10781#S1.p3.1)\.
- Huanget al\.\(2019\)Z\. Huang, F\. Liu, and H\. SuMapping state space using landmarks for universal goal reaching\.Advances in Neural Information Processing Systems32\.Cited by:[§1](https://arxiv.org/html/2609.10781#S1.p3.1)\.
- Kingma and Ba \(2014\)D\. P\. Kingma and J\. BaAdam: a method for stochastic optimization\.arXiv preprint arXiv:1412\.6980\.Cited by:[§B\.2](https://arxiv.org/html/2609.10781#A2.SS2.p3.1)\.
- Klissarov and Machado \(2023\)M\. Klissarov and M\. C\. MachadoDeep laplacian\-based options for temporally\-extended exploration\.arXiv preprint arXiv:2301\.11181\.Cited by:[§1](https://arxiv.org/html/2609.10781#S1.p4.1)\.
- Klissarov and Precup \(2020\)M\. Klissarov and D\. PrecupReward propagation using graph convolutional networks\.Advances in Neural Information Processing Systems33,pp\. 12895–12908\.Cited by:[§1](https://arxiv.org/html/2609.10781#S1.p4.1)\.
- Leeet al\.\(2022\)S\. Lee, J\. Kim, I\. Jang, and H\. J\. KimDHRL: a graph\-based approach for long\-horizon and sparse hierarchical reinforcement learning\.Advances in Neural Information Processing Systems35,pp\. 13668–13678\.Cited by:[§1](https://arxiv.org/html/2609.10781#S1.p3.1),[§2\.3](https://arxiv.org/html/2609.10781#S2.SS3.p3.1)\.
- Liet al\.\(2022\)S\. Li, J\. Zhang, J\. Wang, Y\. Yu, and C\. ZhangActive hierarchical exploration with stable subgoal representation learning\.arXiv preprint arXiv:2105\.14750\.Cited by:[§B\.2](https://arxiv.org/html/2609.10781#A2.SS2.p1.1),[§1](https://arxiv.org/html/2609.10781#S1.p2.1),[3rd item](https://arxiv.org/html/2609.10781#S4.I1.i3.p1.1)\.
- Liuet al\.\(2023\)B\. Liu, Y\. Feng, Q\. Liu, and P\. StoneMetric residual network for sample efficient goal\-conditioned reinforcement learning\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.37,pp\. 8799–8806\.Cited by:[§2\.2](https://arxiv.org/html/2609.10781#S2.SS2.p1.1)\.
- Nachumet al\.\(2018a\)O\. Nachum, S\. Gu, H\. Lee, and S\. LevineNear\-optimal representation learning for hierarchical reinforcement learning\.arXiv preprint arXiv:1810\.01257\.Cited by:[§1](https://arxiv.org/html/2609.10781#S1.p2.1)\.
- Nachumet al\.\(2018b\)O\. Nachum, S\. S\. Gu, H\. Lee, and S\. LevineData\-efficient hierarchical reinforcement learning\.Advances in neural information processing systems31\.Cited by:[§B\.2](https://arxiv.org/html/2609.10781#A2.SS2.p1.1),[§1](https://arxiv.org/html/2609.10781#S1.p2.1),[§2\.2](https://arxiv.org/html/2609.10781#S2.SS2.p2.1),[§3\.3](https://arxiv.org/html/2609.10781#S3.SS3.SSS0.Px2.p1.1),[1st item](https://arxiv.org/html/2609.10781#S4.I1.i1.p1.1)\.
- Nehmzowet al\.\(2013\)U\. Nehmzow, Y\. Gatsoulis, E\. Kerr, J\. Condell, N\. Siddique, and T\. M\. McGuinnityNovelty detection as an intrinsic motivation for cumulative learning robots\.Intrinsically Motivated Learning in Natural and Artificial Systems,pp\. 185–207\.Cited by:[3rd item](https://arxiv.org/html/2609.10781#S1.I1.i3.p1.1)\.
- Nget al\.\(1999\)A\. Y\. Ng, D\. Harada, and S\. RussellPolicy invariance under reward transformations: theory and application to reward shaping\.InIcml,Vol\.99,pp\. 278–287\.Cited by:[§3\.4](https://arxiv.org/html/2609.10781#S3.SS4.p4.1)\.
- Puterman \(2014\)M\. L\. PutermanMarkov decision processes: discrete stochastic dynamic programming\.John Wiley & Sons\.Cited by:[§2\.1](https://arxiv.org/html/2609.10781#S2.SS1.p1.1)\.
- Schulmanet al\.\(2017\)J\. Schulman, F\. Wolski, P\. Dhariwal, A\. Radford, and O\. KlimovProximal policy optimization algorithms\.arXiv preprint arXiv:1707\.06347\.Cited by:[§1](https://arxiv.org/html/2609.10781#S1.p1.1),[§2\.2](https://arxiv.org/html/2609.10781#S2.SS2.p4.1)\.
- Shanget al\.\(2019\)W\. Shang, A\. Trott, S\. Zheng, C\. Xiong, and R\. SocherLearning world graphs to accelerate hierarchical reinforcement learning\.arXiv preprint arXiv:1907\.00664\.Cited by:[§1](https://arxiv.org/html/2609.10781#S1.p3.1)\.
- Simsek and Barto \(2006\)O\. Simsek and A\. G\. BartoAn intrinsic reward mechanism for efficient exploration\.InProceedings of the 23rd international conference on Machine learning,pp\. 833–840\.Cited by:[3rd item](https://arxiv.org/html/2609.10781#S1.I1.i3.p1.1)\.
- Todorovet al\.\(2012\)E\. Todorov, T\. Erez, and Y\. TassaMujoco: a physics engine for model\-based control\.In2012 IEEE/RSJ international conference on intelligent robots and systems,pp\. 5026–5033\.Cited by:[§1](https://arxiv.org/html/2609.10781#S1.p7.2),[§4](https://arxiv.org/html/2609.10781#S4.p1.1)\.
- Wanet al\.\(2021\)G\. Wan, S\. Pan, C\. Gong, C\. Zhou, and G\. HaffariReasoning like human: hierarchical reinforcement learning for knowledge graph reasoning\.InInternational Joint Conference on Artificial Intelligence,Cited by:[§1](https://arxiv.org/html/2609.10781#S1.p3.1)\.
- Wang and Isola \(2022\)T\. Wang and P\. IsolaOn the learning and learnability of quasimetrics\.arXiv preprint arXiv:2206\.15478\.Cited by:[§1](https://arxiv.org/html/2609.10781#S1.p5.1)\.
- Wanget al\.\(2023\)T\. Wang, A\. Torralba, P\. Isola, and A\. ZhangOptimal goal\-reaching reinforcement learning via quasimetric learning\.InInternational Conference on Machine Learning,pp\. 36411–36430\.Cited by:[§1](https://arxiv.org/html/2609.10781#S1.p5.1)\.
- Wanget al\.\(2025\)V\. H\. Wang, T\. Wang, and J\. PajarinenHierarchical reinforcement learning with uncertainty\-guided diffusional subgoals\.arXiv preprint arXiv:2505\.21750\.Cited by:[§1](https://arxiv.org/html/2609.10781#S1.p2.1)\.
- Wanget al\.\(2024\)V\. H\. Wang, T\. Wang, W\. Yang, J\. Kämäräinen, and J\. PajarinenProbabilistic subgoal representations for hierarchical reinforcement learning\.arXiv preprint arXiv:2406\.16707\.Cited by:[§B\.2](https://arxiv.org/html/2609.10781#A2.SS2.p1.1),[§1](https://arxiv.org/html/2609.10781#S1.p2.1),[§2\.2](https://arxiv.org/html/2609.10781#S2.SS2.p2.1),[4th item](https://arxiv.org/html/2609.10781#S4.I1.i4.p1.1)\.
- Zhanget al\.\(2021\)L\. Zhang, G\. Yang, and B\. C\. StadieWorld model as a graph: learning latent landmarks for planning\.InInternational conference on machine learning,pp\. 12611–12620\.Cited by:[1st item](https://arxiv.org/html/2609.10781#S1.I1.i1.p1.1),[§1](https://arxiv.org/html/2609.10781#S1.p3.1)\.
- Zhanget al\.\(2025\)S\. Zhang, Z\. Wang, X\. Chang, and D\. PrecupIncorporating spatial information into goal\-conditioned hierarchical reinforcement learning via graph representations\.Transactions on Machine Learning Research\.Note:External Links:ISSN 2835\-8856,[Link](https://openreview.net/forum?id=a7Bx4s5gA8)Cited by:[§1](https://arxiv.org/html/2609.10781#S1.p4.1),[§1](https://arxiv.org/html/2609.10781#S1.p5.1),[§2\.3](https://arxiv.org/html/2609.10781#S2.SS3.p4.1),[§3](https://arxiv.org/html/2609.10781#S3.p1.1),[1st item](https://arxiv.org/html/2609.10781#S4.I2.i1.p1.1),[§5](https://arxiv.org/html/2609.10781#S5.p2.1)\.
- Zhanget al\.\(2022\)T\. Zhang, S\. Guo, T\. Tan, X\. Hu, and F\. ChenAdjacency constraint for efficient hierarchical reinforcement learning\.IEEE Transactions on Pattern Analysis and Machine Intelligence45\(4\),pp\. 4152–4166\.Cited by:[§B\.2](https://arxiv.org/html/2609.10781#A2.SS2.p1.1),[§1](https://arxiv.org/html/2609.10781#S1.p2.1),[§2\.2](https://arxiv.org/html/2609.10781#S2.SS2.p2.1),[2nd item](https://arxiv.org/html/2609.10781#S4.I1.i2.p1.1)\.
- Zhuet al\.\(2022\)D\. Zhu, L\. E\. Li, and M\. ElhoseinyValue memory graph: a graph\-structured world model for offline reinforcement learning\.arXiv preprint arXiv:2206\.04384\.Cited by:[§1](https://arxiv.org/html/2609.10781#S1.p3.1)\.

## Appendix ALimitations and Future Work

Despite the promising advantages demonstrated by G2QDR in hierarchical reinforcement learning \(HRL\) tasks, several limitations remain\. First, its performance is highly sensitive to a number of key hyperparameters, includingϵd\\epsilon\_\{d\}, the significance\-related hyperparameters \(α\\alpha\),pp, andWW\. Obtaining strong and stable performance across diverse environments therefore requires careful and often time\-consuming manual tuning, which may limit the scalability and practical applicability of the method\.

Second, the graph is constructed dynamically during exploration and is consequently influenced by the behavior policy of the underlying backbone method\. Such policy\-dependent graph construction introduces exploration bias, potentially resulting in an incomplete or unrepresentative approximation of the environment structure\. As a consequence, the dense rewards induced from the learned graph may inherit this bias, which could affect the quality of guidance provided to the agent\.

Third, the environments considered in our experiments are predominantly continuous and characterized by high\-dimensional state representations\. In these settings, the ground\-truth state connectivity structure and the true transition distances between states are generally unavailable\. Therefore, directly evaluating the quality of the constructed graph against an optimal or reference graph is infeasible\. Instead, the effectiveness of the learned graph is evaluated indirectly through its impact on downstream task performance\.

Finally, the introduced auxiliary reward is not potential\-based, indicating that it alters the optimization objective and changes the optimal policy\. Although we introduce a dense signal scheduling strategy to mitigate this issue, the auxiliary reward may still influence exploration bias and the replay buffer, which could potentially affect the performance of our method\.

In future work, we aim to address these limitations by developing adaptive mechanisms that can automatically select or adjust key hyperparameters according to environmental characteristics and learning dynamics\. Such approaches could improve the robustness and generalization capability of G2QDR while reducing the reliance on manual tuning\. Furthermore, we plan to enhance the scalability of G2QDR by improving its computational efficiency and evaluating its performance in larger and more complex environments, particularly those with higher\-dimensional state and action spaces\. Finally, we will investigate more principled approaches for evaluating the quality of learned graphs and reducing the impact of exploration bias during graph construction, enabling more reliable and generalizable dense reward generation\.

## Appendix BImplementation details

### B\.1Environment details

AntMaze\-U ShapeThis environment is part of the Gymnasium\-Robotics benchmark suite\. The environment has a size of \(24×\\times24\)\. Both the state and action spaces are continuous, with state and action dimensions of 31 and 8, respectively\. A reward of 1 is issued only when the agent reaches a position within a Euclidean distance of 1 from the goal; otherwise, the reward is 0\. During evaluation, the goal is fixed at \(0, 16\), and an episode is considered successful if the agent finishes within a Euclidean distance of 1 from the goal\.

AntMaze\-W ShapeThis environment is a variant of AntMaze\-U Shape with an enlarged \(32×\\times32\) maze\. The state and action spaces are identical to those of AntMaze\-U Shape\. As in the previous environment, the agent receives a reward of 1 only when it reaches within a Euclidean distance of 1 from the goal and 0 otherwise\. The goal is fixed at \(2, 16\)\.

AntGatherThis environment is introduced by[Duan et al\. \(2016\)](https://arxiv.org/html/2609.10781#bib.bib9)\. The environment size is \(20×\\times20\), and both the state and action spaces are continuous\. The objective is to collect apples while avoiding bombs\. The agent receives a reward of \(\+1\) for each apple collected and a penalty of \(\-1\) for each bomb collected\. Apples and bombs are randomly distributed throughout the environment\.

AntPushThis environment has a size of \(20×\\times20\) with continuous state and action spaces\. It is a challenging manipulation task requiring both navigation and object interaction\. To reach the goal, the agent must first move left, then upward, and finally push a movable block to the right\. Incorrectly pushing the block may permanently obstruct the path to the goal\.

AntFallThis environment also has a size of \(20×\\times20\)\. The task requires the agent to cross a chasm by pushing a block into it to form a bridge\. If the agent falls into the chasm, recovery is impossible, and the episode effectively terminates\.

PusherIn this environment, the agent controls a 7\-DoF robotic manipulator by applying continuous torques to its joints\. The state space consists of the joint positions and velocities, together with the positions of the manipulated object and the target\. The objective is to push the object to a designated target location\.

For these environments, no reward information is communicated between the high\-level and low\-level agents\. Consequently, no aggregation of low\-level rewards is performed\. Since the environment provides only a terminal sparse reward, each high\-level transition is assigned the auxiliary reward generated by our framework, in addition to the terminal environment reward\.

### B\.2Network architecture details

Our network architecture for the HRL agents follows prior work\([Nachum et al\., 2018b](https://arxiv.org/html/2609.10781#bib.bib20);[Zhang et al\., 2022](https://arxiv.org/html/2609.10781#bib.bib24);[Li et al\., 2022](https://arxiv.org/html/2609.10781#bib.bib32);[Wang et al\., 2024](https://arxiv.org/html/2609.10781#bib.bib23)\)\. For HIRO, HRAC, HESS, and HLPS, both the high\-level and low\-level policies are implemented using TD3\. The actor and critic networks in TD3 each consist of hidden layers with size300300\.

For the state connectivity model, we employ a four\-layer fully connected network with a hidden dimension of128128and ReLU activation\.

We use Adam as the optimizer for the actor and critic networks, as well as for the state connectivity model\([Kingma and Ba, 2014](https://arxiv.org/html/2609.10781#bib.bib31)\)\.

## Appendix CHyperparameters

In this section we list the values of hyperparameters used in our experiments\.

Table 3:Hyperparameters used in high\- and low\-level TD3 agents\.Table 4:Hyperparameters used in G2QDR\.The state representation functionϕ⁡\(⋅\)\\phi\(\\cdot\)is a feature selection function that maps the raw state to a reduced representation by retaining only location\-related features, such as the positions of the agent, objects, and designated targets \(or goals\)\. All other state variables, including arm angular velocities, joint angles, and other kinematic features, are discarded\.

The hyperparametersn1n\_\{1\}throughn4n\_\{4\}are chosen such thatn1n\_\{1\}andn2n\_\{2\}fall within the early stage of training, whilen3n\_\{3\}andn4n\_\{4\}correspond to the late stage\. All experiments are conducted using this single choice ofn1n\_\{1\}ton4n\_\{4\}, and alternative configurations were not explored\.

## Appendix DAdditional experimental evaluations

### D\.1Measure of spatial asymmetry

Although measures such as forward/reverse reachability gaps would provide a more precise characterization, they are difficult to estimate reliably in continuous control environments with high\-dimensional state spaces\. Instead, forAntMaze,AntGather,AntFall,AntPush, andPusher, we introduce rule\-based criteria that approximate transition asymmetry induced by environment structure and constraints\. The criteria are defined as follows\.

##### AntMaze \(U\-shape/W\-shape\)

All transitions between arbitrary pairs of states are considered symmetric, as these environments contain no irreversible obstacles or traps\.

##### AntGather

We define an unrecoverable region adjacent to each wall, within which an object cannot be retrieved because the agent is unable to pull it away from the wall\. Consequently, transitions between states in which a given object moves into or out of this region are considered asymmetric\.

##### AntFall

We determine whether the agent or the block is located inside the chasm\. If two states differ in this status for either the agent or the block \(i\.e\., inside versus outside the chasm\), the transitions between them are considered asymmetric\.

##### AntPush

Similar toAntGather, we define an unrecoverable region adjacent to each wall, within which the block cannot be retrieved because the agent is unable to pull it away from the wall\. Consequently, transitions between states in which the block moves into or out of this region are considered asymmetric\.

##### Pusher

We partition the state space into two categories depending on whether the object lies within the robotic arm’s reachable workspace\. Transitions between states belonging to different categories are considered asymmetric\.

Although these rule\-based criteria do not fully characterize all kinds of transition asymmetry for state pairs, they provide a tractable approximation for quantifying spatial asymmetry induced by environmental geometry and constraints\.

We estimate an asymmetry score for each environment by uniformly sampling 10,000 state pairs from the valid state space and computing the fraction classified as asymmetric under the proposed criteria\. This score estimates the probability that a randomly sampled state pair is classified as asymmetric under the proposed criteria, providing a tractable proxy for structural transition asymmetry\. The scores are reported in Table[5](https://arxiv.org/html/2609.10781#A4.T5)\.

Table 5:Asymmetry scores across environments\.We estimate the asymmetry score by uniformly sampling 10,000 state pairs and computing the fraction classified as asymmetric under the proposed rule\-based criteria\.The estimated asymmetry scores are consistent with the qualitative discussion in Section[4\.2](https://arxiv.org/html/2609.10781#S4.SS2): the directed G2QDR is more likely to outperform its undirected counterpart, G4RL, onAntGather,AntPush,AntFall, andPusher, supporting our characterization of these environments as exhibiting greater structural asymmetry\.

### D\.2Direct evaluation of the state connectivity model

Based on the rule\-based asymmetry criteria defined in Section[D\.1](https://arxiv.org/html/2609.10781#A4.SS1), we evaluate the absolute asymmetry gap\|𝒞θ​\(ψ⁡\(si,sj\)\)−𝒞θ​\(ψ⁡\(sj,si\)\)\|\|\\mathcal\{C\}\_\{\\theta\}\(\\psi\(s\_\{i\},s\_\{j\}\)\)\-\\mathcal\{C\}\_\{\\theta\}\(\\psi\(s\_\{j\},s\_\{i\}\)\)\|of the state connectivity model𝒞θ​\(⋅\)\\mathcal\{C\}\_\{\\theta\}\(\\cdot\)using symmetric and asymmetric state pairs sampled from the valid state space\. The difference in this quantity between symmetric and asymmetric pairs can be interpreted as an indicator of whether the model captures underlying directional structure in the environments\. Figure[5](https://arxiv.org/html/2609.10781#A4.F5)reports the average absolute asymmetry gap for each group at different stages of training\. The underlying training backbone isHLPS\.

\(a\)\(b\)\(c\)\(d\)\(e\)\(f\)
Figure 5:Symmetry gap in different environments\.We report the average absolute asymmetry gaps for sampled symmetric and asymmetric state pairs\. The red curves show the evolution of the averaged absolute asymmetry gap under the state connectivity model𝒞θ​\(⋅\)\\mathcal\{C\}\_\{\\theta\}\(\\cdot\)for symmetric state pairs, while the green curves show the corresponding values for asymmetric state pairs\. Note that theAntMazeenvironments contain only symmetric state pairs under our rule\-based criteria\.The overall trend shown in the figures is that the separation between the two curves gradually increases across environments\. This suggests that the model is indeed learning to distinguish asymmetric state pairs from symmetric ones by assigning larger asymmetry gaps to the former\.

##### Direct diagnosis of𝒞θ​\(⋅\)\\mathcal\{C\}\_\{\\theta\}\(\\cdot\)\.

To directly evaluate whether the learned state connectivity scores reflect transition feasibility, we perform a diagnostic analysis onAntMaze\. Since the environment contains only a single movable agent and its dynamics are nearly deterministic and reversible, graph shortest\-path distance provides a reliable proxy for empirical reachability between states\.

We discretize the workspace into a regular square grid with spacing0\.10\.1, such that the coordinates of each grid point are multiples of0\.10\.1\. Adjacent valid grid points are connected to form a square lattice graph\. For two arbitrary statessis\_\{i\}andsjs\_\{j\}, we map them to their nearest grid verticesviv\_\{i\}andvjv\_\{j\}, respectively, and compute the shortest\-path distance on the grid graph, denoted bydg​\(vi,vj\)d\_\{g\}\(v\_\{i\},v\_\{j\}\)\. Because transitions between nearby states generally require fewer actions and have higher rollout success under the deterministic dynamics of AntMaze, this graph\-based distance serves as a practical approximation of transition feasibility\.

To evaluate whether the learned connectivity model preserves this notion of feasibility, we uniformly sample four states from the valid state space, denoted bys1s\_\{1\},s2s\_\{2\},s3s\_\{3\}, ands4s\_\{4\}, and compare the ordering induced by the connectivity scores with the ordering induced by the graph\-based distances\. Specifically, a sampled quadruple is considered monotonicity preserving if

\(𝒞θ​\(ψ⁡\(s1,s2\)\)\>𝒞θ​\(ψ⁡\(s3,s4\)\)\)⟺\(dg​\(v1,v2\)<dg​\(v3,v4\)\)\.\\left\(\\mathcal\{C\}\_\{\\theta\}\(\\psi\(s\_\{1\},s\_\{2\}\)\)\>\\mathcal\{C\}\_\{\\theta\}\(\\psi\(s\_\{3\},s\_\{4\}\)\)\\right\)\\Longleftrightarrow\\left\(d\_\{g\}\(v\_\{1\},v\_\{2\}\)<d\_\{g\}\(v\_\{3\},v\_\{4\}\)\\right\)\.\(12\)
We uniformly sample a large number of quadruples and compute the fraction that preserves monotonicity\. A higher monotonicity\-preservation rate indicates that the learned connectivity scores rank state pairs more consistently with their underlying transition feasibility\. As shown in Figure[6](https://arxiv.org/html/2609.10781#A4.F6), this metric generally improves throughout training on both AntMaze\(U\-shape\) and AntMaze\(W\-shape\), demonstrating that𝒞θ​\(⋅\)\\mathcal\{C\}\_\{\\theta\}\(\\cdot\)becomes increasingly aligned with an independent reachability proxy rather than merely exhibiting directional score differences\.

Figure 6:Monotonicity preservation rate on \(a\) AntMaze U\-shape and \(b\) AntMaze W\-shape using HLPS\+G2QDR\. The monotonicity\-preservation rate generally increases during training, indicating that the learned connectivity model becomes increasingly aligned with the graph\-based transition\-feasibility proxy\.

### D\.3Ablation study on hyperparameters

In this section, we present an ablation study to evaluate the influence of several key hyperparameters on the performance of the proposed framework onHESSandHLPS\. Specifically, we investigate the effects of the window sizeWW, the decay exponentpp, the novelty thresholdϵd\\epsilon\_\{d\}, and the reward weightsα\\alpha\. Unless otherwise specified, all hyperparameters are fixed to the values reported in Section[C](https://arxiv.org/html/2609.10781#A3), with only the hyperparameter under investigation varied in each experiment\.

Table 6:Ablation study on the window sizeWWFrom Table[6](https://arxiv.org/html/2609.10781#A4.T6), we observe that increasing the window sizeWWimproves the final performance up to a certain point\. Beyond this point, however, the gains quickly plateau, and further increasingWWyields only marginal or no improvement while incurring substantially higher computational overhead\.

Table 7:Ablation study on the decay exponentppTable[7](https://arxiv.org/html/2609.10781#A4.T7)shows that our method performs well whenp=1p=1orp=2p=2\. However, increasingppcauses the connection weights to decay much more rapidly over time, making the edge weights between temporally distant states negligible\. Consequently, long\-range temporal dependencies contribute little to the graph, causing the model to behave similarly to theW=1W=1setting\.

Table 8:Ablation study on the novelty thresholdϵd\\epsilon\_\{d\}Table[8](https://arxiv.org/html/2609.10781#A4.T8)shows that in generalϵd=0\.5\\epsilon\_\{d\}=0\.5or11yields the best overall performance\. Whenϵd\\epsilon\_\{d\}is too small, the graph structure changes too frequently due to the continual insertion and removal of nodes, preventing the edge weights from remaining well synchronized\. Conversely, whenϵd\\epsilon\_\{d\}is too large, each node may aggregate too many distinct states, resulting in overly coarse graph representations and biased connectivity scores between those states\.

Table 9:Ablation study on the reward weightsαh\\alpha\_\{h\}andαl\\alpha\_\{l\}Table[9](https://arxiv.org/html/2609.10781#A4.T9)shows that whenα\\alphais small, the contribution of the additional reward signal becomes limited, causing the method to approach the behavior of the backbone method\. In contrast, a largeα\\alphamay cause the auxiliary reward to dominate the environmental reward, shifting the optimization objective and potentially degrading performance when the two objectives are misaligned\.