🤖 machine learning

Recursive Value Learning for Long-Horizon Offline Goal-Conditioned RL

The paper proposes DCRL (Divide-and-Conquer RL), a recursive offline goal-conditioned reinforcement learning method that decomposes trajectories into balanced binary trees to reduce bootstrap depth and error accumulation, thereby substantially outperforming existing flat and hierarchical baselines on long-horizon tasks.

Original authors: Hyeonseong Jeon, Youngwoon Lee

Published 2026-09-03

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Hyeonseong Jeon, Youngwoon Lee

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of artificial intelligence, there is a specific challenge known as goal-conditioned learning. Imagine teaching a robot not just to walk, but to walk to a specific chair, or to a specific door, or to a specific light switch, using only a library of past videos of other robots moving around. The robot must look at these old recordings, figure out how to get from point A to point B, and then try to do it itself. This works well for short trips. If the goal is just a few steps away, the robot can easily connect the dots. But when the journey is long—requiring hundreds or thousands of steps to reach a distant destination—the robot often gets lost. It struggles to remember the beginning of the path while trying to plan the end, and small mistakes in its memory of short steps pile up into massive errors by the time it reaches the goal.

This problem becomes even harder when the robot cannot learn by trying things out in the real world. In many real-world scenarios, like operating heavy machinery or navigating a complex factory, making mistakes is too dangerous or expensive. The robot must learn entirely from a fixed dataset of past experiences, a field known as offline reinforcement learning. Researchers have long known that to solve a long journey, you must understand the shorter segments that make it up. However, standard methods for teaching robots from these static datasets often try to learn the entire journey all at once, or they jump around randomly between short and long segments. This approach is like trying to read a book by flipping to random pages; the robot ends up guessing the meaning of a long chapter based on a sentence it hasn't fully understood yet, leading to confusion and failure.

A team of researchers from Yonsei University and Seoul National University has proposed a new way to teach these robots, called DCRL. Instead of guessing the whole path at once, their method breaks every long journey down into a structured, step-by-step hierarchy, much like organizing a large task by first mastering the smallest pieces and then combining them. The researchers took a long path from a dataset and split it exactly in half, then split those halves in half again, continuing this process until they reached single steps. They then taught the robot to understand these tiny, single-step movements first. Once the robot was confident about these small steps, it used that knowledge to understand the slightly longer segments, and then the longer ones, building its understanding from the ground up to the top. This "divide and conquer" strategy ensures that the robot never tries to learn a long, complex route until it has already mastered the shorter routes that compose it.

The researchers found that this structured approach solved a major problem that had plagued previous methods. Older methods often looked at many possible intermediate points and picked the one that looked best, hoping for a shortcut. But because the data was limited, the robot often picked a point that looked good only because of a mistake in its memory, and then it would build its entire plan on that error. The new method avoids this by strictly following the actual path shown in the data, splitting it at the exact middle, and learning the value of that specific route without guessing.

When tested on a variety of difficult tasks, including navigating a giant humanoid robot through a maze and solving complex puzzles, this new method outperformed all previous approaches. On the five most challenging long-horizon tasks available in their benchmark, the new method improved the average success score from 55 to 64, surpassing even more complex, hierarchical systems that were previously considered the state-of-the-art. In one specific test involving a humanoid robot in a massive maze, the new method achieved a success rate of 93 percent, while the next best method only reached 79 percent. On the CALVIN benchmark, the method also showed significant strength in completing sequences of four consecutive subtasks. Perhaps most impressively, on a task involving a cube that required eight separate moves to solve, the new method was the only one that could successfully complete the task, achieving a 5 percent success rate while all other methods failed completely.

The researchers also discovered that the order in which the robot learns is essential. While previous methods often use a scrambled-order approach—learning segments of different lengths in a random sequence—DCRL relies on a strict "bottom-up" progression. The study suggests that by respecting the natural dependency of long journeys on short steps, and by organizing the learning process to reflect that dependency, robots can learn to navigate much longer and more complex paths than ever before. This work does not just offer a new algorithm; it provides a clearer understanding of how to scale artificial intelligence to handle the long, intricate tasks that define the real world.

Technical Summary: Recursive Value Learning for Long-Horizon Offline Goal-Conditioned RL

Problem Statement

Scaling offline Goal-Conditioned Reinforcement Learning (GCRL) to long-horizon tasks faces two primary challenges:

Error Accumulation via Dependency: Long-range value estimates inherently depend on shorter-range estimates. Standard offline GCRL methods often bootstrap long-range values from shorter-range values that are themselves inaccurate or not yet converged, leading to compounding errors.
Overestimation via Max-Based Backups: Standard Bellman-style and transitive value backups select optimistically among actions or intermediate states (e.g., $\max_w V(s, w) \cdot V(w, g)$ ). With finite offline data, this selection process tends to favor overestimated candidates, propagating their errors through repeated backups and creating large global inconsistencies.

Existing methods, including hierarchical approaches and standard transitive learning (like Transitive RL or TRL), often fail to explicitly enforce the dependency order where shorter-horizon values must be learned before longer-horizon values, or they rely on noisy, optimistic selections that amplify errors over long horizons.

Methodology: DCRL (Divide-and-Conquer RL)

The authors propose DCRL, an algorithm that explicitly instantiates a divide-and-conquer strategy for value learning. DCRL addresses the aforementioned challenges through three core mechanisms:

1. Recursive Divide-and-Conquer Structure

Instead of sampling trajectory segments of arbitrary lengths independently, DCRL recursively decomposes a sampled trajectory segment $(s_i, s_j)$ into a balanced binary tree:

Divide: A segment is split at its midpoint $k = \lfloor (i+j)/2 \rfloor$ into two children: $(s_i, s_k)$ and $(s_k, s_j)$ . This recursion continues until single-step segments (leaves) are reached.
Conquer: The value function is trained bottom-up. Single-step leaves are grounded (e.g., $V(s_i, s_{i+1}) = \gamma$ ). Parent nodes are updated only after their children have been trained.
Benefit: This structure reduces the worst-case bootstrap depth from linear ( $O(H)$ ) in standard methods to logarithmic ( $O(\log_2 H)$ ) relative to the horizon $H$ . This shorter dependency chain empirically corresponds to significantly slower error accumulation.

2. Exact Route Factorization (Selection-Free Updates)

To avoid the overestimation caused by maximizing over noisy intermediate states, DCRL uses an exact factorization along the observed route for the behavior value $V_\tau$ :
$V_\tau(s, g) = V_\tau(s, w) \cdot V_\tau(w, g)$
where $w$ is the fixed midpoint of the segment.

Unlike standard transitive backups that maximize over all possible $w$ , this update rule evaluates a single route supported by the dataset.
This ensures the algorithm learns behavior values (values of demonstrated routes) without introducing selection bias. The authors prove that route suboptimality grows under composition, motivating the need to learn from shorter, less-suboptimal constituents first.

3. Value Propagation for Optimality

While the recursive factorization learns reliable behavior values, it does not inherently discover shorter, optimal routes not present in the specific trajectory. To recover optimal values ( $V^*$ ), DCRL employs a second objective:

Multistep Propagation: The value function is trained using globally relabeled goals (Hindsight Experience Replay style) with an upper-expectile loss.
Mechanism: This objective composes segments across different trajectories to identify shorter routes.
Synergy: The recursive divide-and-conquer component provides a reliable, shallow-dependency foundation for long-range behavior values, which the propagation objective then leverages to compose optimal paths.

Implementation: Parallel Slot Scheduling

To execute this recursive training efficiently without sacrificing batch diversity, DCRL uses slot scheduling:

Multiple independent "slots" maintain separate recursive trees for different root segments.
Each slot processes its tree from leaves to root.
During training, samples are drawn from these slots. Because slots drain and refill at different rates, minibatches contain a mix of segment lengths (short and long) while strictly preserving the child-to-parent training order within each slot.

Key Contributions

Algorithm: The introduction of DCRL, which explicitly constructs balanced binary trees over in-trajectory segments, enforces bottom-up training via value factorization, and utilizes slot scheduling for parallel execution.
Analysis: A theoretical proof that DCRL reduces the worst-case bootstrap depth from linear to logarithmic in the horizon. Empirical analysis in a controlled environment demonstrates that this shorter dependency structure leads to substantially slower error accumulation compared to linear-depth methods.
Performance: DCRL achieves state-of-the-art performance across diverse offline GCRL benchmarks, including state-based and pixel-based environments. Notably, on the five most challenging long-horizon tasks in OGBench, DCRL improves the best prior average score from 55 to 64, surpassing both flat and hierarchical baselines.

Results

Long-Horizon Tasks: On OGBench tasks like humanoidmaze-giant and complex puzzle environments, DCRL significantly outperforms prior flat methods (e.g., IQL, TD, TRL) and hierarchical methods (e.g., HIQL, SHARSA). It is the only flat method to achieve non-zero success on the cube-octuple task.
Error Accumulation: In controlled experiments (combination-lock environment), DCRL's Q-error remains relatively flat as the horizon increases, whereas standard TD and TRL methods exhibit rapid error growth.
Ablation Studies: Removing the recursive scheduling (training in random order) causes a drastic performance drop (success rate falling from 93% to 18% in humanoidmaze-giant), confirming the necessity of the child-to-parent ordering. Removing the propagation objective also degrades performance, validating the need for both behavior learning and optimal value recovery.
Comparison with TRL: While Transitive RL (TRL) uses similar in-trajectory backups, it lacks the explicit recursive structure and balanced scheduling, leading to linear worst-case depth and higher error accumulation.

Significance and Limitations

The paper claims that DCRL provides a foundation for scaling GCRL to longer horizons by mitigating horizon-induced error accumulation through a structured, recursive learning process. It demonstrates that explicitly modeling the dependency structure of value learning (shorter segments before longer ones) is critical for stability in offline settings.

Limitations acknowledged by the authors:

Deterministic Dynamics: Like other triangle-inequality methods, DCRL assumes deterministic dynamics. In stochastic environments, the exact factorization $E[XY] \neq E[X]E[Y]$ generally fails.
Hierarchical Superiority in Specific Domains: While DCRL excels in long-horizon tasks like humanoidmaze-giant, hierarchical approaches still outperform it on cube-manipulation tasks, suggesting that task difficulty is not solely a function of horizon length and that hierarchy may remain beneficial in certain contexts.

The authors identify extending recursive sampling to stochastic dynamics and understanding the conditions under which hierarchy remains beneficial as important directions for future work.