A new reinforcement learning method avoids temporal difference learning to handle long tasks
Researchers have introduced a reinforcement learning algorithm that relies on a divide and conquer approach rather than temporal difference learning. This method scales effectively to long-horizon tasks where traditional techniques struggle.
We can perform Reinforcement Learning (RL) based on divide and conquer instead of temporal difference (TD) learning.
Problem setting: off-policy RL
The problem setting focuses on off-policy reinforcement learning. There are two main classes of algorithms in this field: on-policy and off-policy. On-policy RL requires using only fresh data collected by the current policy. Practitioners must discard old data whenever they update the policy. Algorithms like PPO and GRPO fall into this category.
Off-policy RL removes this restriction. It allows the use of any data, including old experience, human demonstrations, and internet data. This makes off-policy RL more general and flexible than on-policy RL, though it is also more difficult. Q-learning is the most well-known off-policy RL algorithm. In domains where data collection is expensive, such as robotics, dialogue systems, and healthcare, practitioners often have no choice but to use off-policy RL. This makes it a critical problem to solve.
As of 2025, there are reasonably good recipes for scaling up on-policy RL, including PPO, GRPO, and their variants. However, a scalable off-policy RL algorithm that performs well on complex, long-horizon tasks remains elusive. This is because of how value learning works.
Two paradigms in value learning: Temporal Difference (TD) and Monte Carlo (MC)
In off-policy RL, practitioners typically train a value function using temporal difference (TD) learning, such as Q-learning. The standard Bellman update rule is:
Q(s, a) = r + γ max(a’) Q(s’, a’)
The issue is that error in the next value Q(s’, a’) propagates to the current value Q(s, a) through bootstrapping. These errors accumulate over the entire horizon. This is the core reason why TD learning struggles to scale to long-horizon tasks.
To mitigate this, researchers have mixed TD learning with Monte Carlo (MC) returns. For example, n-step TD learning (TD-n) works as follows:
Q(s_t, a_t) = Σ(γ^i r_{t+i}) + γ^n max(a’) Q(s_{t+n}, a’)
Here, the algorithm uses the actual Monte Carlo return from the dataset for the first n steps, then uses the bootstrapped value for the rest of the horizon. This reduces the number of Bellman recursions by a factor of n, meaning errors accumulate less. In the extreme case where n is infinite, the method recovers pure Monte Carlo value learning.
While this is a reasonable solution and often works well, it is unsatisfactory. First, it does not fundamentally solve the error accumulation problem; it only reduces the number of Bellman recursions by a constant factor. Second, as n grows, the method suffers from high variance and suboptimality. Practitioners cannot simply set n to a large value and must carefully tune it for each task.
Is there a fundamentally different way to solve this?
The third paradigm: divide and conquer
The claim is that a third paradigm in value learning, divide and conquer, may provide an ideal solution for off-policy RL that scales to arbitrarily long-horizon tasks.
Divide and conquer reduces the number of Bellman recursions logarithmically.
The key idea is to divide a trajectory into two equal-length segments and combine their values to update the value of the full trajectory. This reduces the number of Bellman recursions logarithmically rather than linearly. Moreover, it does not require choosing a hyperparameter like n, and it does not necessarily suffer from high variance or suboptimality.
Conceptually, divide and conquer has all the desirable properties for value learning. The challenge was determining how to implement it in practice until recently.
A practical algorithm
In recent work co-led with Aditya, the team made meaningful progress toward realizing and scaling up this idea. Specifically, they scaled up divide-and-conquer value learning to highly complex tasks. This is, to the authors’ knowledge, the first such work in one important class of RL problems: goal-conditioned RL.
Goal-conditioned RL aims to learn a policy that can reach any state from any other state. This provides a natural divide-and-conquer structure.
The structure follows the triangle inequality for the shortest path distance between two states s and g, denoted as d*(s, g). The inequality holds for all states s, g, w in the state space S:
d*(s, g) ≤ d*(s, w) + d*(w, g)
In terms of values, this translates to a transitive Bellman update rule:
V(s, g) = γ^0 if s = g
V(s, g) = γ^1 if (s, g) is an edge in the environment’s transition graph
V(s, g) = max(w in S) V(s, w)V(w, g) otherwise
Intuitively, this means we can update the value of V(s, g) using two smaller values: V(s, w) and V(w, g), provided that w is the optimal midpoint on the shortest path. This is the divide-and-conquer value update rule required.
The problem
There is one issue. It is unclear how to choose the optimal subgoal w in practice. In tabular settings, practitioners can enumerate all states to find the optimal w, which is essentially the Floyd-Warshall shortest path algorithm. But in continuous environments with large state spaces, this is impossible. This is why previous works have struggled to scale up divide-and-conquer value learning, even though the idea dates back to Kaelbling (1993).
The solution
The key idea is to restrict the search space of w to states that appear in the dataset, specifically those that lie between s and g in the dataset trajectory. Instead of searching for the optimal argmax w, the team computes a soft argmax using expectile regression. They minimize the following loss:
E[ℓ^2_κ (V(s_i, s_j) – V̄(s_i, s_k) V̄(s_k, s_j))]
Here, V̄ is the target value network, ℓ^2_κ is the expectile loss with an expectile κ, and the expectation is taken over all (s_i, s_k, s_j) tuples with i ≤ k ≤ j in a randomly sampled dataset trajectory.
This has two benefits. First, the search does not need to cover the entire state space. Second, it prevents value overestimation from the max operator by using the softer expectile regression. The team calls this algorithm Transitive RL (TRL).
Does it work well?
humanoidmaze
puzzle
To test scaling on complex tasks, the team evaluated TRL on OGBench, a benchmark for offline goal-conditioned RL. They used the hardest versions of humanoidmaze and puzzle tasks with large, 1B-sized datasets. These tasks require performing combinatorially complex skills across up to 3,000 environment steps.
TRL achieves the best performance on highly challenging, long-horizon tasks.
The results are strong. Compared to strong baselines across different categories, including TD, MC, and quasimetric learning, TRL achieves the best performance on most tasks.
TRL matches the best, individually tuned TD-n without needing to set n.
This is a key result. The team compared TRL with n-step TD learning using different values of n, from 1 (pure TD) to infinity (pure MC). TRL matches the best TD-n on all tasks without needing to set n. This is the desired outcome from the divide-and-conquer paradigm. By recursively splitting a trajectory into smaller ones, it naturally handles long horizons without arbitrarily choosing the length of trajectory chunks.
The paper includes additional experiments, analyses, and ablations. Further details are available in the paper.
What’s next?
The post concludes with a discussion of future directions for the research.
