Novelty-aware Graph Traversal and Expansion for Hierarchical Reinforcement Learning

Hierarchical Reinforcement Learning (HRL) is specially designed for environments characterized by long-term goals and sparse rewards. High-level policies in HRL learn to generate appropriate subgoals aimed at accomplishing the final goal, while low-level policies focus on achieving these designated subgoals. Recently, graph-based HRL algorithms have demonstrated enhanced learning capabilities through the structural representation of state spaces as graphs. However, existing graph-based HRL methods still often generate inefficient subgoals. This paper introduces a new method, Novelty-aware Graph Traversal and Expansion (NGTE), which selects an optimal node at the graph boundary, termed an Outpost Subgoal, as a direct path toward the final goal. Once the Outpost Subgoal is reached, NGTE transitions into an exploration phase, offering exploration subgoals within a reachable distance to efficiently expand the graph. Demonstrated in complex environments such as quadruped robot navigation and robotic arm manipulation, NGTE consistently outperforms existing graph and non-graph HRL methods, showing outstanding performance, especially in the most challenging scenarios with fixed start and fixed goal conditions.