Researchers at the University of California, Berkeley, have introduced a new reinforcement learning algorithm called Transitive RL (TRL) that scales to tasks requiring up to 3,000 environment steps without relying on temporal difference learning.
Off-policy reinforcement learning
Reinforcement learning methods fall into two categories based on how they use data. On-policy methods like PPO and GRPO can only use fresh data collected by the current policy. This means old data must be discarded whenever the policy updates.
Off-policy RL removes this restriction. It allows the use of any data, including historical experience, human demonstrations, and internet data. This flexibility makes off-policy RL essential for expensive domains like robotics, dialogue systems, and healthcare, where collecting new data is difficult.
By 2025, researchers have found effective ways to scale on-policy RL. However, a scalable off-policy algorithm for complex, long-horizon tasks remained elusive.
Value learning approaches
Off-policy RL typically trains a value function using temporal difference (TD) learning, such as Q-learning. The update rule works like this:
Q(s, a) gets updated to r + γ max Q(s’, a’)
The issue is that errors in the next value propagate to the current value through bootstrapping. These errors accumulate over the entire task horizon, preventing TD learning from scaling to long tasks.
To fix this, researchers mixed TD learning with Monte Carlo (MC) returns. An n-step TD approach uses actual returns for the first n steps and bootstrapped values for the rest. This reduces the number of Bellman recursions by a factor of n, slowing error accumulation. If n is infinite, the method becomes pure Monte Carlo learning.
This approach works reasonably well but has limitations. It does not fundamentally solve error accumulation; it only reduces Bellman recursions by a constant factor. As n grows, variance increases and performance drops. Tuning n for every task remains necessary.
Divide and conquer
The authors propose a third paradigm: divide and conquer. This method divides a trajectory into two equal segments and combines their values to update the full trajectory. Theoretically, this reduces Bellman recursions logarithmically rather than linearly.
The approach avoids choosing a hyperparameter like n and does not suffer from high variance or suboptimality in the same way n-step TD does.
Goal-conditioned RL
In a recent study co-led with Aditya, the team applied divide-and-conquer value learning to goal-conditioned RL. This problem type aims to learn a policy that can reach any state from any other state. The structure naturally supports divide and conquer.
The method assumes deterministic dynamics and uses the shortest path distance between states. This distance satisfies the triangle inequality:
d*(s, g) is less than or equal to d*(s, w) + d*(w, g)
This translates to a transitive Bellman update rule. The value of reaching state g from s updates using two smaller values: reaching w from s and reaching g from w. This is the divide-and-conquer update rule.
The bottleneck
The problem is finding the optimal subgoal w in practice. In tabular settings, one can enumerate all states to find the best w, similar to the Floyd-Warshall algorithm. Continuous environments with large state spaces make this impossible. Previous works struggled to scale divide-and-conquer value learning for this reason.
The solution
The key idea is to restrict the search space of w to states found in the dataset that lie between s and g in a trajectory. Instead of searching for the optimal argmax, the team computes a soft argmax using expectile regression.
This minimizes a loss function over tuples where i is less than or equal to k, which is less than or equal to j. This has two benefits. First, it avoids searching the entire state space. Second, it prevents value overestimation from the max operator by using a softer regression method.
The team calls this algorithm Transitive RL (TRL).
Performance results
The authors evaluated TRL on OGBench, a benchmark for offline goal-conditioned RL. They used the hardest versions of humanoidmaze and puzzle tasks with datasets containing 1 billion samples. These tasks require performing complex skills across up to 3,000 environment steps.
TRL achieved the best performance on most tasks compared to strong baselines including TD, MC, and quasimetric learning.
A key result compares TRL with n-step TD learning across different values of n, from 1 to infinity. TRL matches the best TD-n performance on all tasks without needing to set n. By recursively splitting trajectories, the method naturally handles long horizons without arbitrarily choosing trajectory chunk lengths.
What it means
For practitioners working on long-horizon tasks, this removes the need to tune the n parameter for n-step TD learning. The algorithm automatically adapts to the task length by splitting trajectories recursively, offering a more stable alternative to traditional value learning methods.
