Graph connectivity boosts hierarchical reinforcement learning with dense rewards
From Connectivity to Rewards: Dense Reward Learning with Directed State Graphs
Machine Learning
Summary
Many reinforcement learning systems learn tasks by setting and reaching smaller goals, but they often miss important connections between places or states that help guide learning. The authors offer a method that creates a map capturing how strongly different states are connected, even when moving between states isn’t always the same in both directions. They turn these connections into helpful, continuous rewards that guide the learning process more smoothly. Their approach works alongside many existing methods and shows better performance in tasks where rewards are initially rare.
What this means in practice
- •For robotics engineers: Improve robot navigation and task planning by using directed state connectivity to generate dense rewards for better hierarchical learning.
- •For game ai developers: Enhance AI agents' pathfinding and goal achievement in asymmetric game environments using continuous rewards from state connectivity graphs.
Authors
Shuyuan Zhang, Zihan Wang, Xiao-Wen Chang, Doina Precup
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.