Grounded Transitive RL | Abdul Monaf Chowdhury

TL;DR

Divide-and-conquer value learning reaches a goal \(T\) steps away in \(O(\log T)\) updates instead of \(O(T)\), but its base case treats every logged transition as something the agent can choose. Under stochastic dynamics it ends up valuing the luckiest route through the data, and state–goal pairs that share no trajectory never receive a target. GTRL grounds the composition in a one-step TD target, which averages over successors and needs no subgoal. The whole change costs one extra forward pass.

72.7%

Average success on 10 standard deterministic tasks

+17.5 over TRL

42.2%

On 4 stochastic teleport tasks

+4.2 over next best

35.2%

On 5 stitching tasks

+10.4 over next best

+1pass

Extra forward pass per update. No new network.

Three panels: divide and conquer halving the horizon; the two ways its base case fails; and a one-step TD target that repairs both.

Figure 1. Where divide and conquer breaks. (a) The transitive rule halves the horizon down to one logged transition, and that base case is the step that breaks. (b) It breaks twice: under stochastic dynamics it reads the lucky successor as the agent's own choice (top), and it has no subgoal when the state and the goal lie on different trajectories (bottom). (c) A one-step TD target averages over the successors and needs no subgoal, so it repairs both, while the composition keeps the long horizon.

Background

Two ways to carry value across a long horizon

In offline goal-conditioned RL, an agent learns from a fixed dataset of trajectories, with no further access to the environment, to reach any state from any other. Goals are assigned in hindsight from the data, and the reward is collected on arrival. With \(T^\pi(s,g)\) the first step at which policy \(\pi\) reaches \(g\) from \(s\), the value is

\[ V^\pi(s,g) = \mathbb{E}\big[\gamma^{\,T^\pi(s,g)}\big], \qquad Q^\pi(s,a,g) = \mathbb{E}\big[\gamma^{\,T^\pi(s,g)} \,\big|\, a_0 = a\big]. \]

hitting-time value

A larger value means a shorter expected trip. Under deterministic dynamics the optimal policy takes the shortest route, so \(V^*(s,g) = \gamma^{d^*(s,g)}\), where \(d^*\) is the temporal distance. The question is how to propagate that value across hundreds of steps.

Temporal difference

Regress each value toward a target built from the next state:

\( Q(s,a,g) \leftarrow \gamma\, \mathbb{E}_{s'}\big[V(s',g)\big] \)

Value moves one step per backup, so a goal \(T\) steps away needs \(O(T)\) backups, and each regression inherits the error of the last.

Divide and conquer

Temporal distances obey the triangle inequality, so values compose through any subgoal \(w\):

\( V^*(s,g) \,\ge\, V^*(s,w)\, V^*(w,g) \)

Joining two halves at the best subgoal needs only \(O(\log T)\) updates: at best, 10 compositions instead of 1,000 backups for a goal 1,000 steps away.

Transitive RL (TRL; Park et al., 2026) made the composition practical at scale with two changes: an in-sample expectile replaces the maximum over subgoals, and subgoals are drawn from the same trajectory as the state and the goal. For indices \(i \lt k \lt j\) on one trajectory,

\[ \mathcal{L}_{\text{TRL}}(Q) = \mathbb{E}\Big[\rho(s_i,s_j)\, L_{0.7}\big(Q(s_i,a_i,s_j),\, \bar Q(s_i,a_i,s_k)\,\bar Q(s_k,a_k,s_j)\big)\Big], \]

TRL critic loss

where \(L_\kappa\) is an expectile loss that penalises under-estimating the target by \(\kappa\) and over-estimating it by \(1-\kappa\), and \(\rho\) puts more weight on short segments. Both changes assume deterministic dynamics.

The problem

Where divide and conquer breaks

The composition step is sound; the base case is not. The transitive rule bottoms out at a single logged transition, valued at \(\gamma\) as if the agent could take it whenever it wanted. Under stochastic dynamics, the agent chooses the action but the environment chooses the successor.

Fault 1: it values the luckiest route

Let \(G\) be the directed graph with an edge \(s \to s'\) whenever some action reaches \(s'\) with positive probability, and let \(d_G(s,g)\) be the shortest path in \(G\): the fewest steps to \(g\) if every random transition goes the agent's way.

Proposition 1Fixed point of the transitive update

Assume every edge of \(G\) appears in the dataset, and iterate the update from its base cases. Let \(V_{\text{DC}}(s,g) = \gamma^{d_G(s,g)}\). Then:

the iterates increase pointwise to \(V_{\text{DC}}\), and reach it after \(\lceil \log_2 \operatorname{diam}(G) \rceil\) steps;
\(V_{\text{DC}} \ge V^*\), with equality at \((s,g)\) if and only if some policy reaches \(g\) from \(s\) in exactly \(d_G(s,g)\) steps almost surely;
if the dynamics are deterministic, \(V_{\text{DC}} = V^*\).

Once the two come apart, the error has one sign, so the rule overestimates. The gap belongs to the fixed point itself; more data does not close it.

Example 1The teleporter

State \(s\) has a single action that leads to \(A\) or \(B\) with probability \(\tfrac12\) each. From \(A\), one step reaches \(g\); from \(B\), the only route is a 10-step corridor. Then \(d_G(s,g) = 2\), so \(V_{\text{DC}}(s,g) = \gamma^2\), while \(V^*(s,g) = \tfrac12\gamma^2 + \tfrac12\gamma^{11}\). At \(\gamma = 0.99\) that is 0.980 against 0.938: a reported distance of 2 steps against a true 6.4.

Transitive fixed point, \(\gamma^{d_G(s,g)}\) V = 0.980 · 2.0 steps

True optimal value, \(V^*(s,g)\) V = 0.938 · 6.4 steps

One-step target, \(\gamma\,\mathbb{E}_{s'}[V^*(s',g)]\) V = 0.938 · 6.4 steps

Fault 2: pairs no trajectory connects never get a target

A subgoal has to lie between \(s\) and \(g\) on a single trajectory, so \(g\) must appear after \(s\) on that trajectory in the first place.

Proposition 2Which pairs receive a target

Let \(\mathcal{R}\) be the set of pairs \((s_i, s_j)\), \(i \le j\), that lie on a common trajectory in the dataset. Every target the transitive loss forms is for a pair in \(\mathcal{R}\). For \((s,g) \notin \mathcal{R}\) the loss never produces a target, so in the tabular case the value stays wherever it was initialised.

This is the everyday situation in stitching datasets, where trajectories are short and most state–goal pairs never share one. In the teleport maze of Figure 2a, only a third of the states ever receive a target for the goal.

The two propositions point at the same missing piece. One says the base case needs a one-step expectation; the other says off-trajectory pairs need a target at all. A single one-step TD term supplies both.

Method

Keep the composition, ground its base case

TD learning is what divide and conquer set out to replace: slow and error-prone over a long horizon. Over a single step, though, it is exactly right. Its target is an expectation over the next state, so randomness averages out, and it needs only a transition and a goal, so every state–goal pair gets one. GTRL adds this one-step target to the composition rather than replacing it.

Teleport maze heatmaps. Left: TRL trains a third of the states for the goal while GTRL trains every state. Right: the hindsight goal distribution after one outcome, and the average over outcomes that the weight restores.

Figure 2. Both components on a teleport maze, where one action leads to \(A\) or \(B\) with probability \(\tfrac12\); every panel is computed exactly. (a) Counterfactual goals: TRL trains only the states that reach \(g\) on a shared trajectory, while GTRL trains all of them. (b) Hindsight weighting: a hindsight goal is picked after the environment has chosen a successor, so it reflects that one outcome. The weight corrects it back to the average over every successor the action could have produced.

Counterfactual goalsHalf of the critic's goals are drawn from the whole dataset instead of the state's own trajectory, so targets for the same input come from every outcome of a stochastic transition.
A one-step target everywhereGoals with no subgoal between them and \(s\) still get \(y_{\text{TD}} = \gamma\,\bar Q(s',a',g)\), fit at the mean.
Take the largerWhere a subgoal exists, the composition and the one-step target are both valid, so GTRL regresses toward the larger of the two.
Hindsight weightingIn-trajectory goals are reweighted by how reachable they were from the other successors, a ratio read off the critic in one forward pass.

Counterfactual goals and the one-step target

For a transition \((s,a,s')\) with next logged action \(a'\), call a goal decomposable (\(m = 1\)) if it lies ahead of \(s\) on the same trajectory, and non-decomposable (\(m = 0\)) otherwise. TRL trains only decomposable goals, whose target is the product \(y_{\text{DC}} = \bar Q(s,a,w)\,\bar Q(w,a_w,g)\). Every goal, decomposable or not, also has a one-step target:

\[ y_{\text{TD}} = \begin{cases} 1 & \text{if } g = s, \\ \gamma & \text{if } g = s', \\ \gamma\, \bar Q(s',a',g) & \text{otherwise.} \end{cases} \]

one-step target

This is the transitive target at subgoal offset one. The two kinds of goal call for different statistics. On a decomposable goal the target varies with the subgoal draw, and we want the best decomposition, so the expectile is optimistic. On a non-decomposable goal the target varies with the environment's transition, and we want the average over outcomes:

\[ \begin{aligned} \kappa(s,g) &= \begin{cases} 0.7 & m = 1 \\ 0.5 & m = 0 \end{cases} \\[6pt] y_{\text{A}} &= \begin{cases} \max\{y_{\text{DC}},\, y_{\text{TD}}\} & m = 1 \\ y_{\text{TD}} & m = 0 \end{cases} \end{aligned} \]

split expectile · target selection

The maximum follows from the rule itself: the transitive update is a maximum over subgoals, and the one-step case is one of those subgoals. For a non-decomposable goal the subgoal set is empty, so the maximum runs over the one-step case alone.

Hindsight weighting

\(Q(s,a,g)\) should average over every successor that \(a\) could produce, but hindsight relabelling picks the goal after the successor is known: a trajectory that went to \(A\) only yields goals near \(A\). Because the trajectory offset is drawn from a \(\mathrm{Geometric}(1-\gamma)\) with the critic's own \(\gamma\), a decomposable goal is a sample from the discounted occupancy \(\mu(\cdot \mid s')\) of the successor that happened. Reweighting it toward the average over successors, and using \(\mu(g \mid s) = V(s,g)\,\mu(g \mid g)\) so that the goal-only factor cancels,

\[ h(s,a,s',g) = \frac{\mathbb{E}_{\tilde s \sim p(\cdot \mid s,a)}\big[\mu(g \mid \tilde s)\big]}{\mu(g \mid s')} = \frac{\mathbb{E}_{\tilde s}\big[V(\tilde s,g)\big]}{V(s',g)} = \frac{Q(s,a,g)}{\gamma\, V(s',g)}. \]

hindsight weight

A successor that landed close to \(g\) is weighted down, and one that landed far from it is weighted up. Under deterministic dynamics \(h = 1\) identically, and non-decomposable goals, drawn without looking at the successor, keep \(h = 1\) as well. In practice both terms come from the target critic (the denominator \(\bar Q(s',a',g)\) is already computed for \(y_{\text{TD}}\)), and \(h\) is clipped to \([1/(1+c),\, 1+c]\) with \(c = 1\) and normalised to mean one over the decomposable goals in the batch.

The full objective

\[ \mathcal{L}_{\text{GTRL}}(Q) = \mathbb{E}\Big[\, h \cdot \rho \cdot L_{\kappa(s,g)}\big(Q(s,a,g),\ y_{\text{A}}\big) \Big] \]

GTRL critic loss

It fits a composition wherever the data supports one, and a one-step expectation everywhere else. The policy is extracted with reparameterised gradients and a behaviour-cloning term, as in TRL.

Proposition 3Where the GTRL fixed point lies

In the tabular setting (entries fit exactly, successors drawn from \(p(\cdot \mid s,a)\), every dataset pair sampled with positive probability), iterating the GTRL update from zero converges to a fixed point \(Q_{\text{A}}\) with

\( Q^\beta(s,a,g) \,\le\, Q_{\text{A}}(s,a,g) \,\le\, V_{\text{DC}}(s,g), \)

where \(Q^\beta\) is the value of the behaviour policy that collected the data. The upper bound says the maximum costs nothing: GTRL is no more optimistic than the rule it grounds. The lower bound is what counterfactual goals buy: off-trajectory pairs, which TRL leaves at their initialisation, are floored at the behaviour value.

Algorithm 1: the full GTRL update pseudo-code

Requires dataset \(\mathcal{D}\), discount \(\gamma\), clip constant \(c\), target update rate \(\eta\).

Initialise critic \(Q_\theta\), target critic \(\bar Q_{\bar\theta} \leftarrow Q_\theta\), and policy \(\pi_\phi\)
for each gradient step do
Sample transitions \((s,a,s')\) from \(\mathcal{D}\) with the action \(a'\) logged at \(s'\), and a goal \(g\) for each
Set \(m = 1\) where \(g\) lies ahead of \(s\) on the same trajectory, and \(m = 0\) otherwise
Where \(m = 1\), sample a subgoal \(w\) uniformly between \(s\) and \(g\), with its logged action \(a_w\)
\(y_{\text{DC}} \leftarrow \bar Q(s,a,w)\,\bar Q(w,a_w,g)\) composition
\(y_{\text{TD}} \leftarrow \gamma\,\bar Q(s',a',g)\), or a base case where \(g = s\) or \(g = s'\) one-step target
\(y_{\text{A}} \leftarrow \max\{y_{\text{DC}}, y_{\text{TD}}\}\) where \(m = 1\), and \(y_{\text{TD}}\) elsewhere target selection
\(\kappa \leftarrow 0.7\) where \(m = 1\), and \(0.5\) elsewhere split expectile
\(h \leftarrow \bar Q(s,a,g) \,/\, \gamma\bar Q(s',a',g)\) where \(m = 1\), and \(1\) elsewhere hindsight weight
Clip \(h\) to \([1/(1+c),\, 1+c]\), then normalise it to mean 1 over the goals with \(m = 1\)
\(\theta \leftarrow \theta - \nabla_\theta\, \mathcal{L}_{\text{GTRL}}(Q_\theta)\) critic
\(\phi \leftarrow \phi + \nabla_\phi\, J(\phi)\) policy extraction
\(\bar\theta \leftarrow \eta\,\theta + (1-\eta)\,\bar\theta\)
end for

Results

Nineteen OGBench tasks, three regimes

We evaluate on the oracle-representation variants of 19 OGBench tasks against ten baselines from four families: behavioural cloning (BC, FBC), temporal difference (IVL, IQL, TD, TD-n), Monte Carlo (CRL, MC) and triangle-inequality methods (QRL, TDP, COE, TRL). Each score is the success rate over five evaluation goals, averaged over the checkpoints at 800K, 900K and 1M steps and over four seeds.

Hover or focus a bar for its value

Deterministic navigation (point, ant and humanoid mazes, ant soccer) and manipulation (cube, scene, puzzle).

Standard · 10 deterministic tasks Average success rate (%)

BC 7.2

FBC 16.9

IVL 38.0

IQL 53.5

TD-n 51.5

CRL 38.2

MC 35.7

QRL 12.2

TDP 8.8

COE 9.9

TRL 55.2

GTRL 72.7

+17.5 points over TRL (+32% relative). The largest gains are on the four maze-navigation tasks, where GTRL adds 18 to 46 points over TRL.

IQL and MC finish ahead on ant soccer and the two cube tasks. On cube-double-play, where every triangle-inequality method struggles, GTRL's 37% is still the best of them.

Per-task results · Standard 10 tasks × 12 methods

Task	BC	FBC	IVL	IQL	TD-n	CRL	MC	QRL	TDP	COE	TRL	GTRL
pointmaze-large-navigate	25±3	71±4	48±10	34±3	31±7	33±7	4±4	7±7	30±5	34±7	33±5	79±6
antmaze-large-navigate	22±4	22±4	21±6	37±8	55±6	85±7	39±5	67±8	27±3	26±3	46±5	87±1
humanoidmaze-medium-navigate	7±2	9±3	24±4	36±3	60±3	72±5	49±3	18±17	7±0	9±2	57±1	75±4
humanoidmaze-large-navigate	2±1	1±1	3±1	5±1	20±2	28±5	6±2	3±2	1±1	2±0	8±1	41±9
antsoccer-arena-navigate	3±1	17±2	62±2	77±3	64±4	35±5	42±3	13±1	5±1	5±2	73±4	74±1
cube-single-play	7±2	18±5	88±2	95±1	95±2	63±5	98±1	6±3	3±1	13±8	95±2	93±4
cube-double-play	1±1	4±2	59±2	64±4	10±2	35±3	8±2	1±1	1±0	0±0	30±5	37±1
scene-play	4±2	23±2	68±10	61±3	75±3	26±5	25±5	6±2	12±1	8±2	77±2	84±4
puzzle-3x3-play	1±1	3±1	2±1	98±0	99±0	5±1	81±12	1±1	2±0	2±0	99±0	100±0
puzzle-4x4-play	0±0	1±0	5±2	28±4	6±3	0±0	5±2	0±0	0±0	0±0	34±4	57±8
Average	7.2	16.9	38.0	53.5	51.5	38.2	35.7	12.2	8.8	9.9	55.2	72.7

Success rate (%) ± standard deviation over four seeds. Bold marks the best in each row and underline the runner-up.

Teleporters send the agent to one of three exits at random, and one exit is a dead end. The same action has several successors, so the transitive base case breaks.

Teleport · 4 stochastic tasks Average success rate (%)

BC 28.2

FBC 30.5

IVL 38.0

IQL 26.2

TD 27.7

CRL 21.5

MC 26.0

QRL 14.2

TRL 32.5

GTRL 42.2

+4.2 points over the next best, GC-IVL (+11% relative), and ahead of TRL on every task, by 9.7 points on average.

The one exception is antmaze-teleport-navigate, where the Monte Carlo method CRL finishes a point ahead.

Per-task results · Teleport 4 tasks × 10 methods

Task	BC	FBC	IVL	IQL	TD	CRL	MC	QRL	TRL	GTRL
pointmaze-teleport-navigate	25±3	28±2	35±3	29±4	24±7	24±9	29±4	4±4	26±5	37±7
pointmaze-teleport-stitch	31±9	34±6	43±2	29±2	36±2	0±0	26±1	12±5	40±4	47±2
antmaze-teleport-navigate	26±3	29±3	40±4	29±3	27±3	50±2	27±2	28±4	32±2	49±2
antmaze-teleport-stitch	31±6	31±4	34±3	18±4	24±2	12±4	22±0	13±4	32±4	36±2
Average	28.2	30.5	38.0	26.2	27.7	21.5	26.0	14.2	32.5	42.2

Success rate (%) ± standard deviation over four seeds. Bold marks the best in each row and underline the runner-up.

Trajectories are cut into four-cell pieces and a goal needs up to eight of them joined, so most state–goal pairs never share a trajectory.

Stitch · 5 tasks Average success rate (%)

BC 13.8

FBC 14.2

IVL 12.8

IQL 21.3

TD 9.2

CRL 16.4

MC 9.4

QRL 24.8

TRL 9.8

GTRL 35.2

+10.4 points over the next best, QRL (+42% relative), and +25.4 over TRL, which averages only 9.8% when goals lie off its trajectories.

The exception is pointmaze-large-stitch, where QRL's quasimetric reaches 84% and nothing else passes 34%.

Per-task results · Stitch 5 tasks × 10 methods

Task	BC	FBC	IVL	IQL	TD	CRL	MC	QRL	TRL	GTRL
pointmaze-large-stitch	7±5	20±13	12±6	34±2	0±0	0±0	0±0	84±15	0±0	19±2
antmaze-large-stitch	3±3	6±4	18±2	8±1	4±1	8±5	5±1	18±2	8±1	31±4
humanoidmaze-medium-stitch	29±5	38±3	12±2	29±7	38±1	59±1	35±3	18±2	36±0	70±3
humanoidmaze-large-stitch	6±3	6±1	1±1	1±1	3±1	12±2	7±1	3±1	5±1	18±2
antsoccer-arena-stitch	24±8	2±3	21±3	34±2	1±1	2±1	1±0	1±1	1±0	38±2
Average	13.8	14.2	12.8	21.3	9.2	16.4	9.4	24.8	9.8	35.2

Success rate (%) ± standard deviation over four seeds. Bold marks the best in each row and underline the runner-up.

Ablations

What each component contributes

We remove one component at a time and track success over training, on two deterministic and two stochastic tasks each.

Learning curves: GTRL versus GTRL without counterfactual goals on four tasks.

Without counterfactual goals, goals come only from the state's own trajectory, as in TRL, and the divide-and-conquer product is the only target. Success drops on every task: by up to 60.6 points on the deterministic tasks and 20.1 on the stochastic ones. These goals are what let the critic generalise past its own trajectories instead of memorising them.

Learning curves: GTRL versus GTRL without the maximum over targets on four tasks.

Without the maximum, decomposable goals always take the divide-and-conquer target and only non-decomposable goals take the one-step target. The drop is almost as large as losing counterfactual goals altogether: target selection is what lets the one-step target fix the composition instead of just filling in for it.

Learning curves: GTRL versus GTRL with a single expectile on four tasks.

Without the split expectile, every goal is fit at \(\kappa = 0.7\). That costs 40.2 points on humanoidmaze-large-navigate and 25.3 on antmaze-large-navigate, and 9.0 and 8.6 points on the stochastic tasks. Half of the batch carries the one-step target, so fitting it optimistically inflates values everywhere.

Limitations

The composition still draws its subgoal from the data, so unconnected pairs rely on one-step backups alone. The hindsight weight is read off the critic, so it inherits the critic's error. Learning subgoals for unconnected pairs, and estimating the weight independently of the critic, are natural next steps.

Cite

Citation

If this work is useful to you, please cite it as:

@article{chowdhury2026gtrl,
  title   = {{GTRL}: Grounding Divide-and-Conquer Value Learning with Temporal Differences},
  author  = {Chowdhury, Abdul Monaf and Chowdhury, MD Sameer Iqbal and Arman, Shifat E and Hasan, Md Mehedi},
  journal = {arXiv preprint arXiv:2609.33259},
  year    = {2026},
  eprint  = {2609.33259},
  archivePrefix = {arXiv},
  url     = {https://arxiv.org/abs/2609.33259}
}