Reinforcement Learning Free of Temporal-Difference Methods

A new algorithm called Transitive RL (TRL) replaces temporal difference learning with a divide-and-conquer approach, cutting the number of Bellman recursions logarithmically rather than linearly. Developed in a recent work co-led by Seohong Park and Aditya, the method achieved the best performance on some of the hardest tasks in OGBench, a benchmark for offline goal-conditioned RL, using datasets with roughly 1 billion transitions.

Why Off-Policy RL Still Lacks a Scalable Recipe

Reinforcement learning splits into two families. On-policy methods like PPO and GRPO can only use fresh data from the current policy, discarding old data at every update. Off-policy methods, exemplified by Q-learning, can reuse old experience, human demonstrations, and Internet data. That flexibility matters enormously in domains where data collection is expensive, such as robotics, dialogue systems, and healthcare.

As of 2025, Park argues, on-policy RL has reasonably good scaling recipes, but off-policy RL does not. The bottleneck lies in how value functions are learned.

The Error-Accumulation Problem in TD Learning

Off-policy RL typically trains a value function with temporal difference (TD) learning, bootstrapping from the next state's value. The flaw is that errors in Q(s', a') propagate backward into Q(s, a), accumulating across the entire horizon — which is why TD learning struggles on long-horizon tasks.

The common fix, n-step TD, mixes in Monte Carlo returns: the first n steps use actual returns from the dataset, and only the remainder is bootstrapped, reducing Bellman recursions by a factor of n. But this only buys a constant-factor improvement. As n grows, variance and suboptimality rise, so n must be tuned per task.

A Third Paradigm: Divide and Conquer

Divide and conquer splits a trajectory into two equal-length segments and combines their values, reducing Bellman recursions logarithmically. In goal-conditioned RL — where a policy must reach any state from any other — the shortest-path distance between states satisfies a triangle inequality: d*(s, g) ≤ d*(s, w) + d*(w, g). This translates into a "transitive" Bellman update, where the value of reaching goal g from s can be computed from two smaller values via an optimal midpoint subgoal w.

The idea dates back to Kaelbling's 1993 work on goal-conditioned RL, but it stalled because choosing the optimal w requires enumerating all states — essentially Floyd-Warshall — which is impossible in continuous environments. TRL's contribution is a practical workaround: restrict w to states between s and g within dataset trajectories, and replace the hard max with a soft argmax computed through expectile regression, which also curbs value overestimation.

Results on OGBench

Evaluated on the hardest humanoidmaze and puzzle tasks in OGBench, which demand combinatorially complex skills over up to 3,000 environment steps, TRL outperformed strong TD, Monte Carlo, and quasimetric baselines on most tasks. Most notably, TRL matched the best individually tuned TD-n setting — spanning n from 1 (pure TD) to infinity (pure Monte Carlo) — without requiring anyone to set n at all.

What to Watch Next

TRL currently assumes deterministic dynamics and targets only goal-conditioned RL. The authors' stated priorities include extending the method to reward-based tasks, handling stochastic environments via "stochastic" triangle inequalities, improving subgoal candidate selection, and stabilizing training. Park frames the broader stakes clearly: finding a scalable off-policy RL algorithm remains one of the most important open problems in machine learning, and recursion-based approaches — alongside model-based RL — are among the strongest candidates.