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

arXiv: https://arxiv.org/abs/2609.10781 · HTML: https://mlsanity.com/paper/2609.10781/

## 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.

## Placed in

- Deep reinforcement learning methods / [Deep RL algorithms and representations](https://mlsanity.com/deeprl/deep-rl-algorithms-and-representations/)

## Builds on (most cited first, 23 of 23)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Addressing Function Approximation Error in Actor-Critic Methods](https://mlsanity.com/paper/1802.09477/) (2018)
- [World Models](https://mlsanity.com/paper/1803.10122/) (2018)
- [Soft Actor-Critic Algorithms and Applications](https://mlsanity.com/paper/1812.05905/) (2018)
- [Data-Efficient Hierarchical Reinforcement Learning](https://mlsanity.com/paper/1805.08296/) (2018)
- [Benchmarking Deep Reinforcement Learning for Continuous Control](https://mlsanity.com/paper/1604.06778/) (2016)
- [Search on the Replay Buffer: Bridging Planning and Reinforcement Learning](https://mlsanity.com/paper/1906.05253/) (2019)
- [Optimal Goal-Reaching Reinforcement Learning via Quasimetric Learning](https://mlsanity.com/paper/2304.01203/) (2023)
- [Near-Optimal Representation Learning for Hierarchical Reinforcement Learning](https://mlsanity.com/paper/1810.01257/) (2018)
- [World Model as a Graph: Learning Latent Landmarks for Planning](https://mlsanity.com/paper/2011.12491/) (2020)
- [Mapping State Space using Landmarks for Universal Goal Reaching](https://mlsanity.com/paper/1908.05451/) (2019)
- [Deep Laplacian-based Options for Temporally-Extended Exploration](https://mlsanity.com/paper/2301.11181/) (2023)
- [DHRL: A Graph-Based Approach for Long-Horizon and Sparse Hierarchical Reinforcement Learning](https://mlsanity.com/paper/2210.05150/) (2022)
- [Active Hierarchical Exploration with Stable Subgoal Representation Learning](https://mlsanity.com/paper/2105.14750/) (2021)
- [Topological Experience Replay](https://mlsanity.com/paper/2203.15845/) (2022)
- [Reward Propagation Using Graph Convolutional Networks](https://mlsanity.com/paper/2010.02474/) (2020)
- [On the Learning and Learnability of Quasimetrics](https://mlsanity.com/paper/2206.15478/) (2022)
- [Learning World Graphs to Accelerate Hierarchical Reinforcement Learning](https://mlsanity.com/paper/1907.00664/) (2019)
- [Value Memory Graph: A Graph-Structured World Model for Offline Reinforcement Learning](https://mlsanity.com/paper/2206.04384/) (2022)
- [Adjacency constraint for efficient hierarchical reinforcement learning](https://mlsanity.com/paper/2111.00213/) (2021)
- [Probabilistic Subgoal Representations for Hierarchical Reinforcement learning](https://mlsanity.com/paper/2406.16707/) (2024)
- [Hierarchical Reinforcement Learning with Uncertainty-Guided Diffusional Subgoals](https://mlsanity.com/paper/2505.21750/) (2025)
- [Incorporating Spatial Information into Goal-Conditioned Hierarchical Reinforcement Learning via Graph Representations](https://mlsanity.com/paper/2511.10872/) (2025)

## 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.