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

• URL: http://arxiv.org/abs/2609.10781v1
• Date: Wed, 09 Sep 2026 19:29:22 GMT
• Title: From Connectivity to Rewards: Dense Reward Learning with Directed State Graphs
• Abstract summary: We introduce a state connectivity model designed to predict pairwise state connectivity strength in asymmetric environments.<n>We demonstrate that our proposed framework, Graph-Guided Quasimetric Reward (G2QDR), can theoretically be integrated into any existing Goal-Conditioned Reinforcement Learning architecture.
• Score: 37.10671332775445
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Limit Analysis of Graph Neural Networks with Wireless Conflict Graphs [81.39865232674413]
  Graph Neural Networks (GNNs) have emerged as a powerful tool for wireless resource allocation.<n>This work establishes theoretical results for transferability of GNNs over graphs derived from sparse Random Geometric Graphs (RGGs)
  arXiv  Detail & Related papers  (2026-06-02T15:42:14Z)
• Position: Graph Condensation Needs a Reset -- Move Beyond Full-dataset Training and Model-Dependence [26.234880574328823]
  We argue that graph condensation, in its current form, needs a reset.<n>We call for moving beyond full-dataset training and model-dependent design.<n>We aim to reorient the field toward approaches that deliver on the true promise of condensation.
  arXiv  Detail & Related papers  (2026-05-17T07:08:22Z)
• Graph Signal Diffusion Models for Wireless Resource Allocation [74.84410305593006]
  We consider constrained ergodic resource optimization in wireless networks with graph-structured interference.<n>We show that time-sharing the generated power allocations achieves near-optimal ergodic sum-rate utility and near-feasible ergodic minimum-rates.
  arXiv  Detail & Related papers  (2026-04-06T21:12:25Z)
• Incorporating Spatial Information into Goal-Conditioned Hierarchical Reinforcement Learning via Graph Representations [37.10671332775445]
  The integration of graphs with Goal-conditioned Reinforcement Learning (GCHRL) has recently gained attention.<n>Existing approaches typically rely on domain-specific knowledge to construct these graphs.<n>This paper proposes a solution by developing a graph encoder-decoder to evaluate unseen states.
  arXiv  Detail & Related papers  (2025-11-14T00:58:39Z)
• Toward Robust Signed Graph Learning through Joint Input-Target Denoising [20.15917072156998]
  Signed Graph Neural Networks (SGNNs) are widely adopted to analyze complex patterns in signed graphs with both positive and negative links.<n>We propose RIDGE, a novel framework for Robust graph learning through joint Denoising of Graph inputs and supervision targEts.<n>We extensively validate our method on four prevalent signed graph datasets, and the results show that RIDGE clearly improves the robustness of popular SGNN models under various levels of noise.
  arXiv  Detail & Related papers  (2025-10-26T03:34:40Z)
• Fast State-Augmented Learning for Wireless Resource Allocation with Dual Variable Regression [83.27791109672927]
  We show how a state-augmented graph neural network (GNN) parametrization for the resource allocation policy circumvents the drawbacks of the ubiquitous dual subgradient methods.<n>Lagrangian maximizing state-augmented policies are learned during the offline training phase.<n>We prove a convergence result and an exponential probability bound on the excursions of the dual function (iterate) optimality gaps.
  arXiv  Detail & Related papers  (2025-06-23T15:20:58Z)
• Learning Efficient and Generalizable Graph Retriever for Knowledge-Graph Question Answering [75.12322966980003]
  Large Language Models (LLMs) have shown strong inductive reasoning ability across various domains.<n>Most existing RAG pipelines rely on unstructured text, limiting interpretability and structured reasoning.<n>Recent studies have explored integrating knowledge graphs with LLMs for knowledge graph question answering.<n>We propose RAPL, a novel framework for efficient and effective graph retrieval in KGQA.
  arXiv  Detail & Related papers  (2025-06-11T12:03:52Z)
• Graph as a feature: improving node classification with non-neural graph-aware logistic regression [2.952177779219163]
  Graph-aware Logistic Regression (GLR) is a non-neural model designed for node classification tasks. Unlike traditional graph algorithms that use only a fraction of the information accessible to GNNs, our proposed model simultaneously leverages both node features and the relationships between entities.
  arXiv  Detail & Related papers  (2024-11-19T08:32:14Z)
• T-GAE: Transferable Graph Autoencoder for Network Alignment [79.89704126746204]
  T-GAE is a graph autoencoder framework that leverages transferability and stability of GNNs to achieve efficient network alignment without retraining. Our experiments demonstrate that T-GAE outperforms the state-of-the-art optimization method and the best GNN approach by up to 38.7% and 50.8%, respectively.
  arXiv  Detail & Related papers  (2023-10-05T02:58:29Z)
• Mastering Spatial Graph Prediction of Road Networks [18.321172168775472]
  We propose a graph-based framework that simulates the addition of sequences of graph edges. In particular, given a partially generated graph associated with a satellite image, an RL agent nominates modifications that maximize a cumulative reward.
  arXiv  Detail & Related papers  (2022-10-03T11:26:09Z)
• Data-heterogeneity-aware Mixing for Decentralized Learning [63.83913592085953]
  We characterize the dependence of convergence on the relationship between the mixing weights of the graph and the data heterogeneity across nodes. We propose a metric that quantifies the ability of a graph to mix the current gradients. Motivated by our analysis, we propose an approach that periodically and efficiently optimize the metric.
  arXiv  Detail & Related papers  (2022-04-13T15:54:35Z)
• Tensor Graph Convolutional Networks for Multi-relational and Robust Learning [74.05478502080658]
  This paper introduces a tensor-graph convolutional network (TGCN) for scalable semi-supervised learning (SSL) from data associated with a collection of graphs, that are represented by a tensor. The proposed architecture achieves markedly improved performance relative to standard GCNs, copes with state-of-the-art adversarial attacks, and leads to remarkable SSL performance over protein-to-protein interaction networks.
  arXiv  Detail & Related papers  (2020-03-15T02:33:21Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.