Decomposing Long Horizon Tasks in Sparse Reward Reinforcement Learning

569 concepts475 papers3 proposals

Standard reinforcement learning (RL) agents thrive when given a continuous stream of feedback. If an agent receives a small reward for every step it takes toward a destination, it can easily optimize its policy using gradient ascent. However, real-world challenges rarely offer such explicit guidance. In long-horizon tasks—such as navigating building-scale environments, proving mathematical theorems, or executing multi-stage robotic manipulation—the reward signal is often binary and sparse: the agent receives a 1 upon total task completion and a 0 everywhere else.

When a task requires thousands of precise sequential actions, the mathematical probability of an agent stumbling upon the correct sequence through random exploration is statistically negligible. This creates a "needle in a haystack" problem. If the agent never encounters a positive reward, it cannot compute meaningful policy updates, causing the learning process to stall completely.

To bypass this exploration bottleneck, modern research focuses on temporal and semantic decomposition. Instead of forcing a single "flat" policy to navigate an immense state space over thousands of timesteps, these approaches break the long-horizon problem down into shorter, manageable sub-problems where rewards are easier to discover.

Temporal Abstraction via Hierarchical Subgoals

The most prominent framework for task decomposition is Hierarchical Reinforcement Learning (HRL). In a two-level HRL setup, the agent is split into a high-level policy (the planner) and a low-level policy (the executor). Instead of outputting primitive motor commands, the high-level policy periodically emits an abstract subgoal (e.g., "navigate to the doorway"). The low-level policy is then tasked with reaching this subgoal within a limited number of timesteps, receiving an intrinsic reward when it succeeds.

[High-Level Policy] ---> Emits Subgoal (e.g., "Find Key") ---> [Low-Level Policy]
       ^                                                              |
       |--- Receives Sparse External Reward                           |--- Executes Primitive Actions

As Siyuan Li demonstrates, structured policies that utilize bottom-up skill adaptation and top-down subgoal representations significantly improve exploration efficiency. By dividing a 1,000-step horizon into five 200-step subgoals, the effective search space shrinks exponentially.

However, HRL introduces a secondary challenge: the high-level policy's action space—the set of all possible subgoals—is often massive. If the high-level policy proposes subgoals that are physically impossible or too far away, the low-level policy will fail to reach them, yielding no learning signal.

To solve this, Shangqi Guo et al. proposed HRAC (Adjacency constraint for efficient hierarchical reinforcement learning), which restricts the high-level policy to selecting subgoals within a valid "$k$-step adjacent" region. By bounding the subgoal space to states that are known to be reachable within a short horizon, the low-level policy receives a steady stream of achievable milestones, stabilizing the training process.

Complementing this, Junsu Kim et al. introduced landmark-guided subgoal generation (Landmark-Guided Subgoal Generation in Hierarchical Reinforcement Learning). Instead of sampling arbitrary states, their approach identifies topological bottlenecks (landmarks) in the environment, forcing the high-level policy to plan across critical transit points and preventing the agent from wandering aimlessly in uninformative regions.

Skill Discovery and Backward Chaining

Rather than relying on a top-down planner to dictate subgoals, an alternative paradigm focuses on discovering reusable behavioral primitives, or skills, that can be chained together.

A major hurdle in sparse-reward environments is anchoring these skills to meaningful outcomes. If an agent discovers skills purely through unsupervised exploration, it may master behaviors that are entirely irrelevant to the final objective. Akhil Bagaria addressed this with Deep Skill Chaining (Option Discovery using Deep Skill Chaining), an algorithm that constructs a sequence of skills by working backward from the final goal.

The intuition behind backward chaining is elegant:

  1. The agent first learns a skill that can achieve the ultimate goal from a nearby region (the goal's "initiation zone").
  2. Once that skill is mastered, the boundaries of its initiation zone become the target for a second skill.
  3. The agent repeats this process, growing a chain of skills backward into the environment.

By anchoring the skill discovery process to the final reward and expanding outward, the agent ensures that every discovered skill acts as a stepping stone directly connected to the ultimate objective, effectively pulling the sparse reward signal back to the agent's starting position.

To make this process fully autonomous and sample-efficient without manual intervention, Kelvin Xu introduced a competitive "reset-game" framework (Continual Learning of Control Primitives : Skill Discovery via Reset-Games). By training a reset policy to return the agent to challenging starting configurations, the system naturally discovers a robust library of control primitives, bypassing the need for simulated resets.

Geometry and Distance as Intrinsic Rewards

When external rewards are absent, agents must rely on intrinsic motivation to explore. A powerful metric for structuring exploration in multi-goal environments is temporal distance—the number of environmental steps required to travel between two states.

In TLDR (TLDR: Unsupervised Goal-Conditioned RL via Temporal Distance-Aware Representations), Junik Bae et al. demonstrate that learning representations embedded with temporal distance allows agents to build an internal topological map of the environment. Instead of relying on a binary success/failure signal, the agent can use its representation space as a continuous compass, optimizing its policy by minimizing the predicted temporal distance to a target state.

Similarly, Silviu Pitis et al. developed MEGA (Maximum Entropy Gain Exploration for Long Horizon Multi-goal Reinforcement Learning), an approach that directs exploration toward the "frontier" of the agent's current capabilities. By mapping the density of reached states and prioritizing goals in low-density regions, the agent systematically pushes its boundary of knowledge outward, preventing the vanishing learning signals that occur when agents attempt goals that are too distant.

Injecting Semantic Knowledge and Structural Priors

While purely mathematical formulations of HRL and skill discovery can mitigate the long-horizon problem, they still require the agent to learn the underlying structure of the world from scratch. In highly complex environments, bootstrapping exploration with external semantic guidance can drastically accelerate learning.

Policy Sketches and Demonstrations

Instead of forcing an agent to discover task hierarchies blindly, researchers can provide high-level structural hints. Jacob Andreas et al. introduced Policy Sketches (Modular Multitask Reinforcement Learning with Policy Sketches), which provide the agent with an ordered sequence of named sub-tasks (e.g., [make_plank, grab_iron, craft_pickaxe]). While the agent receives no information on how to execute these sub-tasks, the sketch provides a critical semantic scaffolding that eliminates the high-level exploration bottleneck.

When explicit sketches are unavailable, unstructured human demonstrations can serve a similar purpose. As shown by Abhishek Gupta et al. in Relay Policy Learning (Relay Policy Learning: Solving Long-Horizon Tasks via Imitation and Reinforcement Learning), agents can learn to hand off subgoals by fine-tuning hierarchical policies directly on top of demonstration data, bypassing the need for manual task segmentation.

Guidance via Large Language Models

Recently, the common-sense reasoning capabilities of Large Language Models (LLMs) have been leveraged to provide this semantic structure automatically. LLMs possess extensive web-scale knowledge about physical and procedural dependencies (e.g., knowing that a door requires a key, or that a staircase must be stable).

Runyu Ma et al. developed ExploRLLM (ExploRLLM: Guiding Exploration in Reinforcement Learning with Large Language Models), which uses an LLM to dynamically bias the agent's exploration toward high-utility regions of the state space. Instead of searching uniformly in all directions, the agent focuses its exploration on actions that are semantically plausible.

[Environment State] ---> [LLM Planner] ---> Restricts Search to High-Utility Actions
                                                  |
                                                  v
                                      [Targeted RL Exploration]

For physical systems, Yutao Ouyang et al. demonstrated a cascaded architecture (Long-horizon Locomotion and Manipulation on a Quadrupedal Robot with Large Language Models) where an LLM handles high-level strategic planning and code generation, while low-level RL policies manage high-frequency physical control. If a physical action fails, the LLM dynamically replans, combining semantic reasoning with robust motor execution to solve long-horizon robotic tasks that end-to-end RL cannot resolve alone.

Automated Curricula

When external guidance is unavailable, the agent must rely on an automated curriculum to scale the task complexity. The goal of an automated curriculum is to dynamically adjust the training distribution so that the agent is always challenged by tasks at the edge of its current capabilities—neither too easy (which yields no new information) nor too difficult (which results in zero rewards).

In DISCOVER (DISCOVER: Automated Curricula for Sparse-Reward Reinforcement Learning), Leander Diaz-Bone et al. introduced a goal-selection strategy that balances task achievability, novelty, and relevance to a final target. By automatically tuning this curriculum, the agent avoids the curse of dimensionality in high-dimensional state spaces, systematically building up its skill repertoire until the final, long-horizon sparse reward becomes reachable.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 439 papers
  2. Version 1 · 2026-10-04 · 437 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_sparse_reward_exploration_sparse_reward__49c30faa,
  title = {sparse reward exploration (sparse reward problem)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sparse-reward-exploration-sparse-reward-problem/rdr_49c30faac4a04b698c4dc3a2ded45ecb},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_sparse_reward_exploration_sparse_reward__49c30faa_v2,
  title = {sparse reward exploration (sparse reward problem)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sparse-reward-exploration-sparse-reward-problem/rdr_49c30faac4a04b698c4dc3a2ded45ecb/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake