Source-linked AI summary
From Connectivity to Rewards: Dense Reward Learning with Directed State Graphs
Shuyuan Zhang, Zihan Wang, Xiao-Wen Chang, Doina Precup
TL;DR
Existing graph-based GCHRL methods often underuse connectivity information, especially when state transitions are asymmetric. G2QDR learns directional state connectivity from an online directed graph and converts it into auxiliary dense rewards. Across diverse environments, it consistently improves baseline GCHRL methods while remaining broadly compatible, though its dense signal must be annealed and training-data selection trades accuracy for speed.
Problem
Graph-based GCHRL methods often use graphs for sampling without fully modeling state connectivity, limiting their treatment of asymmetric transitions.
Method
G2QDR builds a directed state graph online, learns pairwise connectivity, and converts the predicted connectivity into auxiliary dense rewards across hierarchical levels.
Results
G2QDR consistently improves baseline GCHRL methods across diverse environments and is broadly compatible with existing GCHRL architectures.
Takeaways & Limitations
Modeling directional state-space structure and translating connectivity into auxiliary rewards provides a flexible approach for complex environments.
Takeaways & Limitations
Because the dense reward is not potential-based, its weight must be annealed to zero to realign optimization with the original task.
Abstract
from arXiv · showhide
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.
1 Introduction
Sparse-reward GCHRL improves exploration through hierarchical subgoals, but existing graph-based approaches often fail to model directional connectivity. G2QDR addresses this gap with an online directed state graph, connectivity-based dense rewards, and broad compatibility with GCHRL methods.
- Motivation: Existing GCHRL methods can be sample-inefficient because high-level policies select subgoals across the state space without structured connectivity information.Prior approaches constrain, smooth, or stochastically sample subgoals but do not organize visited states into a connectivity-aware representation.
- Motivation: Quasimetric environments require directed graphs because transitions can be substantially easier in one direction than the reverse.Undirected graphs cannot represent this asymmetric state accessibility.
- Proposed framework: G2QDR constructs a directed state graph online and predicts state connectivity to generate dense rewards for hierarchical learning.The graph is built during exploration, while the learned connectivity model serves as a proxy for transition distance.
- Contributions: Connectivity-derived auxiliary rewards improve learning signals for both high-level and low-level agents.The rewards provide guidance for subgoal selection and low-level execution.
- Contributions: The architecture is theoretically compatible with any GCHRL algorithm and improves four representative backbones across a broad range of tasks.The evaluated backbones are HIRO, HRAC, HESS, and HLPS.
- Empirical evaluation: Across MuJoCo environments, the method improves the success rate of the underlying GCHRL framework.The approach was evaluated across a range of sparse-reward environments.
2 Preliminaries
These preliminaries define reinforcement learning and hierarchical goal-conditioned control, then formalize graphs as representations of state relationships and transition structure. Together, they establish the notation and structural basis for connectivity-aware GCHRL.
- 2.1 Markov Decision Processes: An MDP specifies states, actions, transitions, rewards, and a discount factor, with policies selecting actions from states.The transition and reward functions govern state evolution and feedback.
- 2.2 Goal-conditioned Hierarchical RL (GCHRL): GCHRL decomposes long-horizon tasks into subgoals selected by a high-level policy and executed by a low-level policy.The low-level policy receives the current state representation and selected subgoal.
- 2.2 Goal-conditioned Hierarchical RL (GCHRL): The low-level intrinsic reward penalizes the distance between the achieved state representation and the subgoal.This encourages the agent to minimize subgoal-reaching distance.
- 2.3 Graph Abstraction of MDP: A graph represents relationships using nodes and edges, with adjacency entries indicating whether connections exist.The graph is defined as G = (V, E), and its adjacency matrix records node connectivity.
- 2.3 Graph Abstraction of MDP: In an MDP graph, nodes represent states while edge weights encode transition probabilities or reachability statistics.This graph acts as an abstract representation of environment dynamics.
- 2.3 Graph Abstraction of MDP: Graph structure compresses transition relationships and supports planning, exploration, and representation learning in large or continuous state spaces.The abstraction avoids explicitly modeling the full transition function.
3 Methods
G2QDR models asymmetric state connectivity with an online directed graph and converts learned connectivity into dense auxiliary rewards for hierarchical policy learning.
- 3 Methods: G2QDR explicitly models state connectivity with a directed graph and uses the resulting connectivity to generate dense rewards within GCHRL.The directed representation addresses environments where opposite transition directions differ.
- 3.1 State graph: The graph is built incrementally during exploration from visited states and recent trajectory relationships, without expert data or handcrafted construction.A fixed-size graph adds sufficiently novel states, connects them to recent preceding states, and updates or replaces nodes as needed.
- 3.1.1 Incremental graph construction: Graph edge weights encode transition frequency and trajectory distance, using polynomial decay so farther preceding states receive weaker connectivity increments.Repeated transitions increase weights, while larger temporal gaps contribute smaller increments w^-p.
- 3.2 State connectivity model: A neural connectivity model predicts pairwise connectivity for observed and unseen state pairs from learned paired-state representations.The model maps each paired representation to a connectivity score and is instantiated as a feed-forward network; updates alternate with policy training.
- 3.2 State connectivity model: Order-sensitive paired representations allow the model to distinguish asymmetric connectivity, with gated fusion producing different representations for reversed state pairs.This design preserves directional transition information rather than treating state pairs as interchangeable.
- 3.3 Induced dense reward: The induced dense reward penalizes risky transition asymmetry through max(·, 0), encouraging policies to remain in more reversible and safer regions.Dense signals are provided across hierarchical agent levels, while annealing later removes the non-potential-based signal to realign optimization with the original task.
4 Experiments
Experiments evaluate G2QDR across sparse-reward MuJoCo tasks, comparing directed and undirected graph variants, auxiliary-reward components, and computational trade-offs. Results generally show higher and more stable performance, especially in asymmetric environments, while sampling adjustments reduce computation with limited degradation.
- Comparative analysis: G2QDR generally improves final success rates and reduces variance over corresponding GCHRL baselines, with larger gains in more asymmetric tasks.The overall improvement is not consistent across every environment.
- Comparative analysis: Directed G2QDR typically outperforms both original baselines and the undirected G4RL variant in asymmetric environments.The comparison is intended to assess the value of explicitly modeling directional relationships.
- Impact of auxiliary reward components: Combining high-level constraint and low-level correction rewards usually performs strongly, while penalty terms further help some tasks but do not uniformly outperform the penalty-free combination.The penalty effect is environment-dependent.
- Impact of auxiliary reward components: Low-level correction rewards produce clear, consistent gains in AntMaze, where Euclidean distance poorly reflects transition distance because walls separate nearby states.The high-level constraint also helps by guiding policies toward more feasible subgoals, especially alongside low-level corrections.
- Balancing between time and performance: Increasing state-sampling intervals substantially reduces computation time while causing only minor success-rate degradation on AntPush and Pusher.The results identify graph construction and node comparisons, rather than connectivity-model training, as the primary computational bottleneck.
- Balancing between time and performance: Using 75% of available connectivity-model training data slightly shortens computation while preserving largely stable success rates on AntPush and Pusher.Reducing the dataset provides only modest computational gains.
- Dense signal scheduling: Immediate full dense rewards slow convergence, whereas schedules with late-stage annealing perform better than keeping λ high throughout later episodes.The findings associate early graph and model instability with reduced efficiency and convergence speed.
5 Conclusion
The paper presents G2QDR as a unified framework that learns directional state connectivity online and converts it into auxiliary rewards for hierarchical control. Across diverse environments, it is broadly compatible with existing GCHRL methods and improves baseline performance, particularly when transitions are asymmetric.
- Conclusion: G2QDR incrementally builds a directed state graph, learns connectivity to estimate transition feasibility, and supplies auxiliary rewards at multiple agent levels.The framework also evaluates newly encountered states through the learned connectivity model.
- Conclusion: Explicitly modeling asymmetric, non-reversible transitions extends undirected graph-based approaches for environments with directional dynamics.The framework is positioned as an extension of G4RL that better captures realistic environment structure.
- Conclusion: G2QDR is broadly compatible with existing GCHRL methods, and evaluations across diverse environments demonstrate improvements over baseline methods.The conclusion characterizes the approach as effective and robust within the evaluated scope.
- Conclusion: Translating state connectivity into auxiliary rewards offers a flexible approach for using directional structure in complex goal-conditioned hierarchical tasks.The stated consequence is limited to the framework’s supported application scope.
A Limitations and Future Work
G2QDR has limitations involving hyperparameter sensitivity, policy-dependent graph construction, unavailable ground-truth connectivity, and objective-altering auxiliary rewards. Future work targets adaptive tuning, improved efficiency, and larger, more complex environments.
- Limitations: G2QDR performance is highly sensitive to several hyperparameters, requiring careful manual tuning that may limit scalability and practical applicability.The cited parameters include ϵd, α, p, and W.
- Limitations: Policy-dependent graph construction can introduce exploration bias, causing dense rewards to inherit incomplete or unrepresentative environmental structure.The graph reflects the behavior policy of the underlying backbone method.
- Limitations: Because ground-truth connectivity and transition distances are generally unavailable in high-dimensional continuous environments, graph quality is evaluated indirectly through downstream task performance.Direct comparison with an optimal or reference graph is infeasible in the considered settings.
- Limitations: The auxiliary reward is not potential-based, so it changes the optimization objective and optimal policy while potentially affecting exploration bias and replay-buffer contents.A dense signal scheduling strategy is introduced to mitigate this issue.
- Future Work: Future work will develop adaptive hyperparameter mechanisms and improve computational efficiency for larger, more complex environments.These directions aim to reduce manual tuning and improve robustness and generalization.
B Implementation details
Experiments use sparse-reward continuous-control environments spanning navigation, collection, manipulation, and robotic pushing. Because rewards are terminal and not transferred between hierarchy levels, auxiliary rewards are added to high-level transitions.
- Environments: The implementation evaluates navigation, collection, manipulation, bridge-building, and robotic pushing tasks in continuous environments.The environments include AntMaze-U, AntMaze-W, AntGather, AntPush, AntFall, and Pusher.
- Reward handling: Terminal sparse rewards are supplemented with framework-generated auxiliary rewards for each high-level transition.No reward information is communicated between high-level and low-level agents, so low-level rewards are not aggregated.
B.2 Network architecture details
The experiments use TD3-based hierarchical policies and a fully connected state-connectivity model, with location-focused state representations and one fixed hyperparameter configuration across experiments.
- Policy networks: HIRO, HRAC, HESS, and HLPS use TD3 for both high-level and low-level policies, with actor and critic hidden layers of size 300.The architecture follows prior hierarchical reinforcement learning implementations.
- Connectivity model: The state connectivity model is a four-layer fully connected network with hidden dimension 128 and ReLU activations.Adam is used to optimize the actor, critic, and connectivity-model networks.
- State representation: The state representation retains location-related features while discarding other variables such as angular velocities, joint angles, and kinematic features.Retained features include positions of agents, objects, and targets or goals.
- Hyperparameters: Experiments use a single n1–n4 configuration, with n1 and n2 assigned to early training and n3 and n4 to late training; alternatives were not explored.Tables 3 and 4 list the high-/low-level TD3 and G2QDR hyperparameters.
D.1 Measure of spatial asymmetry
Spatial asymmetry is approximated with rule-based state-pair criteria because precise reachability gaps are difficult to estimate in high-dimensional continuous control. The resulting sampled asymmetry scores support using directed connectivity where environmental structure is more asymmetric.
- Approximation criteria: Rule-based criteria approximate transition asymmetry from environmental geometry and constraints because forward/reverse reachability gaps are difficult to estimate reliably.These criteria provide a tractable but incomplete characterization of state-pair asymmetry.
- Environment-specific criteria: AntMaze transitions are treated as symmetric because the environments contain no irreversible obstacles or traps.This criterion applies to both U-shape and W-shape variants.
- Environment-specific criteria: AntGather and AntPush classify transitions involving unrecoverable wall-adjacent regions as asymmetric.The affected object cannot be pulled away from the wall.
- Environment-specific criteria: AntFall classifies transitions as asymmetric when the agent or block differs in chasm status, while Pusher uses whether the object lies inside the arm’s reachable workspace.Transitions across either category boundary are considered asymmetric.
- Estimated asymmetry and results: Asymmetry scores estimate the fraction of asymmetric classifications among 10,000 uniformly sampled valid state pairs, and the scores indicate directed G2QDR is more likely to outperform G4RL on AntGather, AntPush, and AntFall.The scores are reported in Table 5 and align with the qualitative environment analysis.
D.2 Direct evaluation of the state connectivity model
The evaluation tests whether the learned connectivity model captures directional structure and transition feasibility. Across diagnostics, the model increasingly aligns with these properties during training.
- Symmetry-gap analysis: The separation between asymmetry-gap curves gradually increases, indicating that Cθ(·) assigns larger gaps to asymmetric than symmetric state pairs.AntMaze contains only symmetric state pairs under the stated rule-based criteria.
- Diagnostic proxy: Graph shortest-path distance provides the independent feasibility proxy because nearby states require fewer actions and have higher rollout success under AntMaze’s deterministic dynamics.States are mapped to nearest vertices on a square lattice with spacing 0.1 before distance computation.
- Monotonicity analysis: Monotonicity-preservation rates generally increase during training on AntMaze U-shape and W-shape, aligning connectivity-score rankings with graph-based transition-feasibility rankings.The diagnostic uses graph shortest-path distance as a reachability proxy in AntMaze.
D.3 Ablation study on hyperparameters
The ablations examine window size, decay exponent, novelty threshold, and reward weights. They show useful operating ranges, saturation or degradation beyond them, and trade-offs between guidance quality and computational or optimization effects.
- Window size W: Increasing window size W improves final performance up to a point, after which gains plateau while computational overhead rises substantially.Further increases yield only marginal or no improvement.
- Decay exponent p: The method performs well when decay exponent p = 1 or p = 2, while larger p suppresses long-range temporal dependencies and approaches the W = 1 behavior.Rapid decay makes edge weights between temporally distant states negligible.
- Novelty threshold ϵd: Performance is generally strongest at novelty threshold ϵd = 0.5 or 1; smaller values destabilize graph structure, whereas larger values produce coarse representations and biased connectivity scores.The two regimes respectively reflect frequent node changes and excessive state aggregation.
- Reward weights α: Small reward weight α limits the auxiliary signal, whereas large α can dominate the environmental reward and degrade performance when the objectives are misaligned.The small-α regime approaches the backbone method.