Strict Subgoal Execution: Reliable Long-Horizon Planning in Hierarchical Reinforcement Learning
Jaebak Hwang, Sanghyeon Lee, Jeongmo Kim, Seungyul Han · 2025
Read Strict Subgoal Execution: Reliable Long-Horizon Planning in Hierarchical Reinforcement Learning by Jaebak Hwang, Sanghyeon Lee, Jeongmo Kim, Seungyul Han (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-21039.txt.
Introduction
Jaebak Hwang, Sanghyeon Lee, Jeongmo Kim, and Seungyul Han present a planning method for robots that must reach far-off goals. Their 2025 paper works in hierarchical reinforcement learning, where a high level picks subgoals and a low level acts. Distant goals with sparse rewards make this planning unreliable.
A common fix relabels past tries as if other goals were intended, but that can bless subgoals that were never reachable. Their method keeps a strict rule for subgoal execution. A new replay scheme marks the frontier between reachable and unreachable subgoals from failed and partial tries. A separate explorer visits neglected regions, and path costs update from low-level failures. Tests across long-horizon benchmarks beat rival methods on speed and success.
Catalog record
| CREATOR | Jaebak Hwang, Sanghyeon Lee, Jeongmo Kim, Seungyul Han |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 87 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-21039
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Strict Subgoal Execution: Reliable Long-Horizon Planning in Hierarchical Reinforcement Learning Jaebak Hwang, Sanghyeon Lee, Jeongmo Kim, Seungyul Han Abstract Long-horizon goal-conditioned tasks pose fundamental challenges for reinforcement learning (RL), particularly when goals are distant and rewards are sparse. While hierarchical and graph-based methods offer partial solutions, they often suffer from subgoal infeasibility and inefficient planning. We introduce Strict Subgoal Execution (SSE), a graph-based hierarchical RL framework that enforces single-step subgoal reachability by structurally constraining high-level decision-making. To enhance exploration, SSE employs a decoupled exploration policy that systematically traverses underexplored regions of the goal space. Furthermore, a failure-aware path refinement, which refines graph-based planning by dynamically adjusting edge costs according to observed low-level success rates, thereby improving subgoal reliability. Experimental results across diverse long-horizon benchmarks demonstrate that SSE consistently outperforms existing goal-conditioned RL and hierarchical RL approaches in both efficiency and success rate. 1 Introduction Recent advances in reinforcement learning (RL) have achieved impressive success across various domains [ 1 , 2 ] . In many real-world applications, agents must achieve specific objectives, motivating the development of goal-conditioned RL (GCRL), where agents learn to reach a designated goal state provided by the environment [ 3 , 4 , 5 ] . Unlike conventional RL methods that rely on carefully designed reward functions, GCRL allows agents to directly pursue target states based on goal specifications. However, in sparse-reward and long-horizon environments, goals are often distant, making exploration difficult and hindering effective learning due to a lack of intermediate guidance. To address this, hierarchical RL (HRL) decomposes the decision process into a high-level policy that selects subgoals and a low-level policy that executes actions to reach them [ 6 , 7 ] . Since subgoals are typically closer and more attainable than the final goal, this structure facilitates learning in long-horizon settings. Nevertheless, HRL can still fail when the selected subgoals are too difficult for the low-level policy to reach reliably. To mitigate this issue, graph-based HRL methods have been proposed [ 8 , 9 , 10 , 11 , 12 , 13 ] . These approaches construct a graph over the goal space, where nodes represent states or regions and edges denote feasible transitions. Subgoal selection is guided by shortest paths on the graph, improving success rates in complex tasks. However, even graph-based HRL remains limited in performance when the final goal lies far from the current state, as the high-level policy may require too many steps, resulting in unstable training and poor scalability. While recent approaches have explored graph-based GCRL without hierarchical structures to mitigate the limitations of high-level policies, such methods often lack the flexibility to handle environments involving multiple goals or diverse reward signals, due to the absence of high-level reasoning [ 14 , 15 ] . To address these limitations, we propose a novel graph-based HRL framework, Strict Subgoal Execution (SSE) , which retains the advantages of high-level planning while enhancing robustness and improving long-horizon goal-reaching by enforcing subgoal completion within a single high-level decision step. Our contributions are summarized as follows: 1. HRL Framework with Single-Step Subgoal Execution: We introduce a hierarchical framework that guarantees each subgoal is reached within a single high-level decision, removing step limits and reducing the number of high-level actions required for long-horizon tasks. 2. Decoupled Exploration for Goal Space Coverage: A dedicated exploration policy is decoupled from the reward-driven high-level policy to guide the agent through underexplored regions of the goal space, improving spatial coverage and training efficiency. 3. Failure-Aware Path Refinement: To enhance subgoal reliability, we adjust graph edge costs based on low-level failure statistics, encouraging path planning to avoid unstable transitions and improving the robustness of subgoal execution. By ensuring that any high-level subgoal in the map is reachable in a single step, our SSE achieves robust performance even when the final goal lies far across the map. The high-level layer enables sequential decision-making in more complex environments with multiple goals or intermediate objectives. Through extensive evaluation on diverse long-horizon, goal-conditioned tasks, our method consistently demonstrates superior success rates and sample efficiency compared to prior GCRL and HRL approaches, validating the effectiveness of the proposed framework. 2 Preliminaries 2.1 Universal Markov Decision Process and Goal-Conditioned RL We consider a universal Markov decision process (UMDP) defined as a tuple (\mathcal{S},\mathcal{G},\mathcal{A},P,R,\gamma) , where \mathcal{S} is the state space, \mathcal{G} is the goal space, \mathcal{A} is the action space, P is the transition dynamics, R is the reward function, and \gamma\in(0,1] is the discount factor [ 3 ] . At each time step t , the agent observes a goal g\in\mathcal{G} and state s_{t} , selects an action a_{t}\sim\pi(\cdot|s_{t},g) , and receives a reward r_{t}=R(s_{t},a_{t},s_{t+1},g) and next state s_{t+1}\sim P(\cdot|s_{t},a_{t}) . The goal of GCRL is to learn a goal-conditioned policy \pi that maximizes the expected return \sum_{t=0}^{H}r_{t} , where H is the episode length. When \mathcal{S}\neq\mathcal{G} , we assume the existence of a mapping \phi such that \phi(s)\in\mathcal{G} , allowing the agent to infer goal progress from the current state. The goal g may be fixed or randomly sampled per episode; while random goals aid generalization through diversity, the fixed-goal setting is more challenging due to its singular target. 2.2 HRL Frameworks and Graph-Based Subgoal Planning in GCRL In goal-conditioned settings, HRL addresses long-horizon challenges by decomposing the policy into a high-level policy \pi^{h} and a low-level policy \pi^{l} [ 6 , 7 ] . Every k steps, \pi^{h}(\cdot|s_{t},g) selects a subgoal \tilde{g}_{t}\in\mathcal{G} , which \pi^{l}(\cdot|s_{t},\tilde{g}_{t}) attempts to reach using an auxiliary reward [ 16 , 17 , 18 ] . However, when subgoals are too distant, the low-level policy may fail to reach them within the given horizon, and distance-based penalties can hinder learning, especially under sparse rewards. To mitigate this, graph-based approaches construct a goal-space graph G=(V,E) , where V denotes a set of landmark nodes and E consists of edges weighted by the expected effort required to transition between nodes. Landmark nodes are typically selected either by applying farthest point sampling (FPS) to choose states that are maximally distant from one another [ 12 , 19 , 20 ] , or by placing virtual goals uniformly from a predefined grid over the goal space [ 15 ] . In general, the edge cost is defined as d(v_{1}\rightarrow v_{2}):=\log_{\gamma}(1+(1-\gamma)Q^{G}(v_{1},v_{2},\pi^{l})), (1) where Q^{G} estimates the feasibility of reaching v_{2} from v_{1} under \pi^{l} , defined as the value function Q^{l} of the low-level policy or a predefined estimator. Full details on Q^{G} are provided in Appendix B.1 . In graph-based HRL, given a subgoal \tilde{g}_{t} , the shortest path from the current state’s embedding \phi(s_{t}) to \tilde{g}_{t} is computed via Dijkstra’s algorithm [ 21 ] , producing a sequence of intermediate waypoints (\mathrm{wp}_{1},\dots,\mathrm{wp}_{n}) , where each \mathrm{wp}_{i}\in V . The low-level policy \pi^{l}(\cdot|s_{t},\mathrm{wp}_{i}) guides the agent through these waypoints in order: once \mathrm{wp}_{i} is reached, the next target subgoal for \pi^{l} is updated to \mathrm{wp}_{i+1} , continuing until \tilde{g}_{t} is reached. The high-level policy is trained on transitions (s_{t},g,\tilde{g}_{t},\sum_{j=t}^{t+k-1}r_{j},s_{t+k}) in buffer \mathcal{B}^{h} , while the low-level policy \pi^{l} is trained using (s_{t},\mathrm{wp}_{i},a_{t},r^{l}_{t},s_{t+1}) in buffer \mathcal{B}^{l} , where the low-level reward r^{l}_{t}=-1 if the agent has not reached \mathrm{wp}_{i} , and r^{l}_{t}=0 otherwise [ 12 , 19 , 20 ] . In