A new reinforcement learning algorithm called Transitive RL (TRL) has been released that solves long-horizon tasks without relying on temporal difference (TD) learning.
The method, developed by researchers at the Berkeley AI Research (BAIR) lab, introduces a “divide and conquer” approach to value learning. It addresses scalability issues found in standard off-policy RL methods like Q-learning, which struggle when tasks require hundreds or thousands of steps to complete.
Why off-policy learning is difficult
Reinforcement learning algorithms generally fall into two categories: on-policy and off-policy. On-policy methods, such as PPO and GRPO, discard older data once a policy is updated. They rely strictly on fresh data collected by the current version of the agent.
Off-policy methods allow the use of any available data, including historical experience, human demonstrations, or internet-collected information. This flexibility makes them essential for fields like robotics, healthcare, and dialogue systems, where gathering new data is costly or impossible. However, creating a scalable off-policy algorithm for complex, long-horizon tasks has remained a significant challenge.
The limits of current value learning
Most off-policy systems train a value function using TD learning. This approach updates values based on the next step’s estimated value, a process known as bootstrapping. While efficient, errors in these estimates accumulate over time. In long tasks, these small mistakes compound, degrading performance.
To reduce this accumulation, researchers have combined TD learning with Monte Carlo (MC) methods. This involves looking ahead $n$ steps before bootstrapping. While this reduces error propagation by a factor of $n$, it introduces new problems. High variance and suboptimality increase as $n$ grows, requiring careful tuning for every specific task.
There is no fundamental solution to the error accumulation issue within this existing framework. The method relies on reducing the number of recursive steps by a constant amount, rather than solving the structural problem.
A third paradigm: divide and conquer
The new approach proposes a different structure for value learning. Instead of linear updates, the algorithm splits a trajectory into two equal segments and combines their values to update the full path. This reduces the number of Bellman recursions logarithmically rather than linearly.
The method does not require choosing a hyperparameter like $n$. It avoids the high variance associated with large step counts and handles long-horizon tasks naturally by recursively splitting the problem.
How the algorithm works
Recent work co-led by Aditya Agarwal at BAIR demonstrates this concept in goal-conditioned reinforcement learning. In these tasks, the agent learns to reach a specific target state from any starting position. This setup provides a natural structure for divide and conquer.
The system treats the environment as a graph where states are nodes. It uses a “transitive” Bellman update rule based on the triangle inequality. If the agent knows how to get from state A to a midpoint B, and from B to the goal C, it can combine these values to estimate the path from A to C.
The practical challenge was identifying the optimal midpoint, or subgoal, in complex environments. Previous methods struggled because they had to search the entire state space. The new algorithm restricts the search to states present in the dataset. It uses expectile regression to calculate a “soft” optimal midpoint, preventing the value overestimation common in standard maximisation operators.
Performance on complex tasks
Researchers tested TRL on the OGBench benchmark, a collection of offline goal-conditioned RL tasks. They focused on the most difficult versions of humanoid maze and puzzle tasks, which require up to 3,000 environment steps.
The results show TRL outperforms strong baselines across different categories, including TD, MC, and quasimetric learning. It achieves the best performance on most tasks without needing to tune the step count parameter.
Comparisons with $n$-step TD learning highlight the advantage. TRL matches the performance of the best-tuned TD-$n$ configurations on all tasks. Crucially, it does this without requiring the user to set the value of $n$. By recursively splitting trajectories, the method handles long horizons without arbitrary choices about chunk length.
What it means
For practitioners building agents for complex environments, this shift removes the need to manually tune step counts to balance variance and bias. The algorithm scales naturally to longer tasks, offering a more stable alternative to traditional off-policy methods that rely on fixed window sizes.