RL without TD learning

In this post, I’ll introduce a reinforcement learning (RL) algorithm based on an “alternative” paradigm: divide and conquer. Unlike traditional methods, this algorithm is not based on temporal difference (TD) learning (which has scalability challenges), and scales well to long-horizon tasks.

Problem setting: off-policy RL

Our problem setting is off-policy RL. There are two classes of algorithms in RL: on-policy RL and off-policy RL. On-policy RL means we can only use fresh data collected by the current policy (e.g., PPO, GRPO). Off-policy RL means we can use any kind of data, including old experience and human demonstrations. Q-learning is the most well-known off-policy RL algorithm.

As of 2025, we still haven’t found a “scalable” off-policy RL algorithm that scales well to complex, long-horizon tasks.

Two paradigms in value learning: Temporal Difference (TD) and Monte Carlo (MC)

In off-policy RL, we typically train a value function using TD learning. The problem is that error in future values propagates to the current value through bootstrapping, and these errors accumulate over the entire horizon. To mitigate this, people use n-step TD, but it doesn't fundamentally solve the error accumulation problem and requires careful tuning.

The “Third” Paradigm: Divide and Conquer

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. This doesn't require choosing a hyperparameter like $n$ and theoretically handles long-horizon tasks much better.

Transitive RL (TRL): A practical algorithm

In recent work, we scaled up divide-and-conquer value learning to highly complex tasks through Transitive RL (TRL). In goal-conditioned RL, we use the triangle inequality to update values.

The main contribution is a practical solution to finding the optimal midpoint (subgoal) $w$. We restrict the search space of $w$ to states in the dataset and use expectile regression to prevent value overestimation.

Does it work well?

TRL was evaluated on OGBench, specifically on challenging tasks like humanoidmaze and puzzle with 1B-sized datasets. These tasks require complex skills across up to 3,000 environment steps. TRL achieves the best performance compared to strong baselines across different categories.