Technical Summary: Strict Subgoal Execution (SSE)

Problem Statement

Long-horizon goal-conditioned reinforcement learning (GCRL) faces fundamental challenges when goals are distant and rewards are sparse. While Hierarchical Reinforcement Learning (HRL) attempts to address this by decomposing tasks into high-level subgoals and low-level execution, existing methods often suffer from subgoal infeasibility.

Traditional graph-based HRL methods frequently rely on Hindsight Experience Replay (HER) to relabel intermediate states as successful subgoals. The authors argue that this approach is flawed in long-horizon settings because it treats failed trajectories as successes without verifying if the agent actually reached the intended subgoal. This leads to:

1. Inefficient High-Level Planning: The high-level policy learns to select subgoals that are unreliable or unreachable, resulting in unnecessarily long trajectories and unstable training.
2. Credit Assignment Issues: Rewards are spread over too many steps, preventing the reinforcement of earlier, critical decisions.
3. Scalability Limits: As the distance between the current state and the final goal increases, the number of required high-level decisions grows, leading to training instability.

Methodology: Strict Subgoal Execution (SSE)

The paper proposes Strict Subgoal Execution (SSE), a graph-based HRL framework designed to enforce reliability in subgoal selection and execution. SSE operates on the principle that a high-level subgoal is only valid if the low-level policy can reach it within a single high-level step.

1. Frontier Experience Replay (FER)

The core innovation of SSE is Frontier Experience Replay (FER), which replaces standard HER with a mechanism that explicitly distinguishes between reachable and unreachable subgoals. Instead of relabeling all visited states as successes, FER categorizes high-level transitions into three types:

• Success: The low-level policy reaches the subgoal within a defined threshold ($\lambda$). The transition is stored with the full cumulative reward.
• Stop-on-Failure: The low-level policy fails to reach the subgoal. The episode is immediately terminated, the reward is set to zero, and the transition is stored to penalize the selection of this subgoal.
• Partial Success: If the agent fails to reach the final subgoal but reaches a specific waypoint on the planned path, this "last reliably reached" state is recorded as a partial success.

This mechanism delineates a reachability frontier, allowing the agent to identify and avoid unreliable subgoals while reinforcing only feasible transitions.

2. Decoupled Exploration Policy

To counteract the conservatism introduced by strict failure penalties (which might cause the agent to avoid exploring risky but necessary regions), SSE employs a decoupled exploration policy ($\pi_{exp}$).

• Exploitation Policy ($\pi_h$): Trained on FER to select optimal subgoals for reaching the final goal.
• Exploration Policy ($\pi_{exp}$): A dedicated policy that targets underexplored regions of the goal space. It samples subgoals from novel regions (identified via grid-based visitation counts or model-based prediction errors) to ensure broad coverage of the state space.
• The agent alternates between these policies, controlled by an exploration ratio $\eta$, ensuring that the agent discovers reachable subgoals even in sparse reward environments.

3. Failure-Aware Path Refinement

SSE introduces a dynamic adjustment to the graph edge costs used for path planning (e.g., Dijkstra's algorithm).

• The framework tracks failure ratios for specific regions (grid cells or nodes) based on low-level execution statistics.
• Edge costs are increased for transitions leading to regions with high failure rates: $\tilde{d}(v_1 \to v_2) = d(v_1 \to v_2) \times \max(1, c_d \cdot \rho_f(v_2))$.
• This steers the high-level planner away from unstable transitions (e.g., narrow bottlenecks or collision-prone areas) toward safer, more reliable paths.

4. Implementation Variants

The authors propose two variants of SSE to handle different goal space dimensions:

• SSE (Grid): Uses a grid-based partition of the goal space for landmark selection, novelty estimation, and failure tracking. Suitable for 2D/3D environments.
• SSE (Model): Uses model-based approaches (Random Network Distillation for novelty, a failure predictor network for reliability) to handle higher-dimensional goal spaces where grid discretization is infeasible.

Key Contributions

1. Frontier Experience Replay (FER): A novel replay mechanism that separates failure and partial-success transitions to define a reachability frontier, eliminating the noise caused by conventional hindsight relabeling in long-horizon tasks.
2. Decoupled Exploration: A strategy that separates the goal-reaching policy from the exploration policy, enabling the agent to cover underexplored regions without compromising the stability of the high-level planner.
3. Failure-Aware Path Refinement: A method to dynamically adjust graph edge costs based on observed low-level failure statistics, improving the reliability of the planned subgoal sequences.
4. Empirical Validation: Extensive evaluation across nine diverse long-horizon benchmarks (including AntMaze, KeyChest, and Reacher tasks) demonstrating superior performance over state-of-the-art HRL and graph-based methods.

Experimental Results

The authors evaluated SSE on nine challenging environments, ranging from simple mazes to complex tasks requiring intermediate objectives (e.g., collecting keys).

• Success Rate: SSE consistently achieved higher success rates than baselines (including HIRO, HRAC, HIGL, DHRL, NGTE, and BEAG) across all environments.
• Sample Efficiency: SSE converged significantly faster, particularly in bottleneck and multi-step tasks. For instance, in the AntDoubleKeyChest task, SSE solved the task in a minimal number of high-level steps, whereas baselines largely failed or required excessive timesteps.
• Robustness: In random-goal settings, SSE maintained strong performance, while many baselines struggled due to a lack of structured exploration mechanisms.
• Ablation Studies: Removing FER, the exploration policy, or path refinement resulted in significant performance degradation, confirming the necessity of each component. Specifically, methods using HER or standard replay buffers failed to learn in complex sequential tasks.

Significance and Claims

The paper claims that SSE addresses a critical gap in hierarchical reinforcement learning: the disconnect between high-level planning and low-level execution capabilities. By enforcing strict subgoal reachability, SSE enables agents to:

• Solve complex, long-horizon tasks with fewer high-level decisions, often reaching distant goals in a single high-level step once the policy is trained.
• Achieve stable training by preventing the propagation of credit through unreliable or failed trajectories.
• Operate effectively in sparse reward environments without relying on extensive retraining or manual curriculum design.

The authors position SSE as a scalable framework for hierarchical control that improves both the efficiency and reliability of goal-conditioned agents, making it a promising approach for real-world applications requiring robust long-horizon planning. The work emphasizes that the framework's effectiveness stems from its ability to learn the boundaries of what is achievable, rather than assuming all intermediate states are valid subgoals.