mlsanityData to 14 Oct 2026

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

arXiv 2609.10781 ↗First posted 9 Sep 2026cs.LGcited by 0

On the map: Deep reinforcement learning methods → Deep RL algorithms and representations

Abstract (arXiv)

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.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in Deep RL algorithms and representations, one of 15 directions in Deep reinforcement learning methods. Builds on 23 of its 33 references that are in the map. First posted on arXiv 9 Sep 2026.

Builds on

23 of 33 references.

Closest ancestors · 3

Same direction, newest first

  1. 2025Incorporating Spatial Information into Goal-Conditioned Hierarchical Reinforcement Learning via Graph Representations14 Nov
  2. 2025Hierarchical Reinforcement Learning with Uncertainty-Guided Diffusional Subgoals27 May
  3. 2024Probabilistic Subgoal Representations for Hierarchical Reinforcement learning24 Jun

Other references · 20

  1. 2017Proximal Policy Optimization Algorithmscited by 15,215
  2. 2018Addressing Function Approximation Error in Actor-Critic Methodscited by 2,417
  3. 2018World Modelscited by 1,513
  4. 2018Soft Actor-Critic Algorithms and Applicationscited by 1,240
  5. 2018Data-Efficient Hierarchical Reinforcement Learningcited by 455
  6. 2016Benchmarking Deep Reinforcement Learning for Continuous Controlcited by 371
  7. 2019Search on the Replay Buffer: Bridging Planning and Reinforcement Learningcited by 194
  8. 2023Optimal Goal-Reaching Reinforcement Learning via Quasimetric Learningcited by 121
  9. 2018Near-Optimal Representation Learning for Hierarchical Reinforcement Learningcited by 110
  10. 2020World Model as a Graph: Learning Latent Landmarks for Planningcited by 69
  11. 2019Mapping State Space using Landmarks for Universal Goal Reachingcited by 44
  12. 2023Deep Laplacian-based Options for Temporally-Extended Explorationcited by 29
8 more
  1. 2022DHRL: A Graph-Based Approach for Long-Horizon and Sparse Hierarchical Reinforcement Learningcited by 19
  2. 2021Active Hierarchical Exploration with Stable Subgoal Representation Learningcited by 17
  3. 2022Topological Experience Replaycited by 17
  4. 2020Reward Propagation Using Graph Convolutional Networkscited by 15
  5. 2022On the Learning and Learnability of Quasimetricscited by 15
  6. 2019Learning World Graphs to Accelerate Hierarchical Reinforcement Learningcited by 12
  7. 2022Value Memory Graph: A Graph-Structured World Model for Offline Reinforcement Learningcited by 12
  8. 2021Adjacency constraint for efficient hierarchical reinforcement learningcited by 10

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2024HG2P: Hippocampus-inspired High-reward Graph and Model-Free Q-Gradient Penalty for Path Planning and Motion Control
  2. 2025Hierarchical Reinforcement Learning with Targeted Causal Interventions
  3. 2026Topology-Aware State Abstraction with Tangle Cores for Markov Decision Processes
  4. 2024Highway Graph to Accelerate Reinforcement Learning
  5. 2025Graph-Assisted Stitching for Offline Hierarchical Reinforcement Learning
  6. 2026RewardFlow: Topology-Aware Reward Propagation on State Graphs for Agentic RL with Large Language Models
  7. 2024Transductive Reward Inference on Graph
  8. 2025From Sparse to Dense: Toddler-inspired Reward Transition in Goal-Oriented Reinforcement Learning