PaperlayerView exact revision on arXiv

Source-linked AI summary

GTRL: Grounding Divide-and-Conquer Value Learning with Temporal Differences

Abdul Monaf Chowdhury, MD Sameer Iqbal Chowdhury, Shifat E Arman, Md Mehedi Hasan

arXiv:2609.33259v2cs.LG

TL;DR

Offline goal-conditioned reinforcement learning needs long-horizon value estimates, but transitive composition can overvalue lucky transitions and cannot train state-goal pairs without a shared-trajectory subgoal. GTRL grounds composition in one-step TD targets and corrects hindsight weighting; across nineteen OGBench tasks, it achieves the highest average success rate across stochastic, stitch, and deterministic settings.

  • Problem

    Under stochastic dynamics, transitive updates can value the luckiest route through the data, and state-goal pairs with no trajectory connecting them receive no target.

    Source: §1 · p. 1

  • Method

    GTRL grounds divide-and-conquer value composition in a one-step TD target and reweights hindsight goals by their reachability from other successors.

    Source: §1 · p. 1, §4.2 · p. 6, §4.3 · p. 6

  • Results

    GTRL achieves the highest average success rate across nineteen OGBench stochastic, stitch, and deterministic tasks without trading performance across settings.

    Source: §1 · p. 2, §6 · p. 10

  • Takeaways & Limitations

    One-step targets repair the stochastic and missing-subgoal faults while unchanged divide-and-conquer composition retains long-horizon value learning.

    Source: §6 · p. 10

    Unconnected pairs rely on one-step backups, and hindsight weights inherit errors from the critic.

    Source: §6 · p. 10

Abstract

from arXiv · show

In offline goal-conditioned reinforcement learning (GCRL), divide-and-conquer scales to long horizons by joining two shorter segments at a subgoal. However, under stochastic dynamics, the base case of this rule values the luckiest trajectories through the data. The subgoal must also lie on a shared trajectory, so a state-goal pair that no trajectory connects gets no value update at all. To address both, we present Grounded Transitive RL (GTRL), an offline GCRL value learning algorithm that grounds the divide-and-conquer update with a one-step TD target. Over a single step, TD is correct, as its target averages over the successors and needs no subgoal. GTRL adds this target to the composition rather than replacing it, so every pair receives an update, and the composition still carries the long horizon. GTRL also corrects the bias from hindsight relabeling by reweighting each goal against how reachable it was from other successors. We evaluate our algorithm on nineteen OGBench tasks spanning stochastic, deterministic, and stitching environments, where it achieves the highest average success rate. Code will be released soon.

1 INTRODUCTION

Divide-and-conquer reduces long-horizon value learning from O(T) to O(log T) updates, but its base case can overvalue lucky outcomes and leave unconnected state-goal pairs untrained. GTRL grounds composition in a one-step TD target, adds counterfactual goals and hindsight weighting, and achieves the highest average success rate across OGBench settings.

1 INTRODUCTION

  • Divide-and-conquer reduces the required updates for a goal T steps away from O(T) to O(log T) by composing estimates through a subgoal.The composition follows from the triangle inequality for temporal distances.Source: §1 · p. 1
  • Under stochastic dynamics, transitive updates value the luckiest route through logged data, and pairs with no shared-trajectory subgoal receive no target.The overestimation gap does not shrink with more data.Source: §1 · p. 1
  • GTRL retains value composition but grounds it with a one-step TD target that averages over successors and needs no subgoal.The one-step target gives every state-goal pair an update while composition carries long-horizon information.Source: §1 · p. 1, Figure 1 · p. 2
  • GTRL samples goals from the whole dataset as well as the state’s own trajectory, and takes the larger valid target when composition is available.Hindsight weighting reweights trajectory goals by state occupancies to correct bias from successor-dependent reachability.Source: §1 · pp. 1–2
  • GTRL achieves the highest average success rate across OGBench’s long-horizon stochastic, deterministic, and stitch tasks without trading performance across settings.The update adds one extra forward pass.Source: §1 · p. 2

2 RELATED WORK

Prior offline goal-conditioned RL methods use either general offline-RL approaches or structure specific to goal-reaching, including value composition through the triangle inequality. Work on stochastic dynamics addresses distance estimates or relabeled data, while the cited methods do not change the divide-and-conquer transitive update.

Offline goal-conditioned RL

  • Offline goal-conditioned methods adapt offline RL or supervised learning to goals, while another group exploits goal-reaching structure such as quasimetrics, hierarchical policies, and contrastive value views.GTRL belongs to the structure-based group and uses the triangle inequality.Source: §2 · p. 2

Composition through subgoals

  • Value composition follows the triangle inequality: joining estimates through a subgoal can reduce horizon-dependent backups to O(log T) in the best case.TRL uses in-sample expectiles and same-trajectory subgoals, changes that assume deterministic dynamics.Source: §2 · pp. 2–3

Stochastic dynamics

  • For stochastic dynamics, prior methods change either the distance being estimated or the relabeled data, but none changes the divide-and-conquer transitive update.Examples include stochastic temporal distances, distributional distance classifiers, and relabeling corrections.Source: §2 · p. 3
  • Hindsight relabeling can overvalue lucky outcomes under stochastic dynamics, while USHER corrects relabeling bias using a separately trained future-goal density for a one-step online backup.GTRL instead takes its relabeling correction from the critic.Source: §2 · p. 3

3 PRELIMINARIES

The paper formulates offline goal-conditioned RL as estimating a goal-reaching value from fixed trajectories and uses temporal-distance structure to motivate value composition. TD backups propagate information one step at a time, whereas subgoal composition can reduce the number of updates to logarithmic in the horizon.

3 PRELIMINARIES

  • The offline GCRL setting uses an unlabeled fixed dataset of trajectories, with tasks defined by reaching a state and one policy serving the task family.The goal is absorbing and reward is collected upon arrival.Source: §3 · p. 3
  • Under deterministic dynamics, optimal goal-conditioned values are a monotone reparameterization of shortest-path distance and inherit its triangle inequality.The value is γ^d*(s,g).Source: §3 · p. 3

3.1 OFFLINE GOAL-CONDITIONED VALUE LEARNING

  • TD learning fits a one-step recursion, but a goal T steps away requires O(T) backups, each inheriting error from the previous estimate.Offline fitting avoids an unsafe action maximum by using asymmetric regression over in-sample actions.Source: §3.1 · p. 4
  • Subgoal composition uses the triangle inequality to multiply two value estimates, and a shortest-route subgoal makes the bound an equality.The best-case backup count falls to O(log T), though maximizing over the state space can select an overvalued subgoal and compound estimator error.Source: §3.1 · p. 4
  • For continuous actions, policy extraction trains a policy to maximize the critic at its sampled action while including a behavior-cloning term.The behavior-cloning coefficient controls how tightly the policy stays tied to the data and can be tuned per environment.Source: §3.1 · p. 4

4 METHODOLOGY

GTRL preserves transitive value composition while adding one-step targets to address stochastic-dynamics bias and missing state-goal coverage, then reweights hindsight goals to correct successor-conditioned sampling.

4 METHODOLOGY

  • TRL makes deterministic transitive learning practical through asymmetric regression and in-trajectory subgoals; GTRL adds counterfactual goals and hindsight weighting to that loss.The baseline loss weights short segments more heavily.Source: §4 · p. 4

4.1 THE PROBLEM

  • Under stochastic dynamics, the transitive update converges to the luckiest possible route’s value, overestimating the optimal value unless the shortest route is reached almost surely.With all graph edges represented in the dataset, the update reaches this fixed point after ⌈log2 diam(G)⌉ steps; deterministic dynamics recover the optimal value.Source: §4.1 · p. 5
  • Pairs absent from any shared trajectory receive no transitive target, so a one-step term supplies targets for these otherwise uncovered state-goal pairs.The proposition states that their values remain at initialization under the transitive loss alone.Source: §4.1 · p. 6

4.2 COUNTERFACTUAL GOALS

  • Counterfactual goals without an in-trajectory subgoal use a one-step target, while decomposable goals retain the composition and use the larger of the two targets.The non-decomposable goal’s target uses the logged successor action; the expectile is 0.7 for decomposable goals and 0.5 otherwise.Source: §4.2 · p. 6

4.3 HINDSIGHT WEIGHTING

  • Hindsight weighting reweights decomposable goals by the ratio of average successor occupancy to realized-successor occupancy, correcting goals sampled conditional on the observed successor.The correction is unnecessary for deterministic transitions and non-decomposable goals; it is clipped and batch-normalized.Source: §4.3 · pp. 6–7

4.4 THE FULL OBJECTIVE

  • GTRL fits composition where data supports it and a one-step expectation elsewhere, combining the targets through the full objective.The objective also uses the expectile target, hindsight weight, and distance weight.Source: §4.4 · p. 7

5 EXPERIMENTS

Across teleport, stitch, and standard deterministic tasks, GTRL has the highest average success rate in the reported environment groups. Ablations show that counterfactual goals, target selection, and hindsight weighting each contribute to its performance.

5 EXPERIMENTS

  • The evaluation covers nineteen OGBench tasks across stochastic teleport, trajectory-stitching, and standard deterministic settings, using success rates averaged over five goals, four seeds, and the last three checkpoints.The nine teleport and stitch tasks test stochastic transitions and joining short trajectory segments; the remaining ten are deterministic navigation and manipulation tasks.Source: §5 · pp. 7–8, §5.1 · p. 8

5.1 DOES GTRL REPAIR THE FAULTS OF DIVIDE AND CONQUER?

  • On teleport tasks, GTRL averages 42.2%, 4.2 points above GC-IVL; on stitch tasks, it averages 35.2%, 10.4 points above QRL.Against TRL, GTRL leads by 9.7 points on average on teleport tasks and 25.4 points on stitch tasks; pointmaze-large-stitch is an exception where QRL reaches 84%.Source: §5.1 · p. 8, Table 1 · p. 8

5.2 DOES GTRL HELP ON STANDARD TASKS AS WELL?

  • On ten standard deterministic tasks, GTRL averages 72.7%, 17.5 points above TRL, and has the highest average in all three environment types.Its largest gains are 18–46 points on the four maze navigation tasks; IQL or MC leads on antsoccer-arena-navigate and two cube tasks.Source: §5.2 · pp. 8–9, Table 2 · p. 9, Figure 3 · p. 9

5.3 ABLATION

  • Removing counterfactual goals causes drops of up to 60.6 points on deterministic tasks and 20.1 points on stochastic tasks.The ablation uses only in-trajectory goals, leaving the divide-and-conquer product as the only target; the authors say counterfactual goals help the critic generalize beyond its own trajectories.Source: §5.3 · p. 9, Figure 4 · p. 9
  • Always choosing the divide-and-conquer target on decomposable goals causes a large performance drop on both deterministic and stochastic tasks.The authors report that this is almost as costly as removing counterfactual goals.Source: §5.3 · p. 10
  • Hindsight weighting improves performance on stochastic tasks, while removing it causes a small drop on deterministic tasks.The deterministic drop is small because transition probability is one; the ablation sets the weight to 1, returning to plain hindsight relabeling.Source: §5.3 · p. 10

6 CONCLUSION

GTRL grounds divide-and-conquer value updates in one-step temporal differences, addressing stochastic overestimation and pairs that lack a shared trajectory. Across nineteen OGBench tasks, it achieves the highest average success rate across stochastic, stitch, and deterministic settings, while two limitations remain.

6 CONCLUSION

  • Across nineteen OGBench tasks, GTRL achieves the highest average success rate on stochastic, stitch, and deterministic tasks without trading performance across settings.The method grounds divide-and-conquer updates in temporal differences while retaining value composition.Source: §6 · p. 10
  • The hindsight weight is read from the critic, so it inherits the critic’s error.The authors identify independent weight estimation as a direction for future work.Source: §6 · p. 10
  • Divide-and-conquer value composition still draws its subgoal from the data, leaving unconnected state-goal pairs to rely on one-step backups.Learning subgoals for unconnected pairs is proposed as a next step.Source: §6 · p. 10
  • The code is included in the supplementary material and is slated for public release upon publication.The README provides commands to reproduce reported numbers.Source: REPRODUCIBILITY STATEMENT · p. 11

A PROOFS

The proof defines an update operator that fixes base-pair values and composes values through candidate subgoals for all other pairs.

A PROOFS

  • The operator writes base values of 1 for identical state-goal pairs and γ for graph edges.All other pairs are updated by maximizing the product of values through a subgoal.Source: A PROOFS · p. 15
  • For non-base pairs, the operator assigns the maximum over subgoals of the product of the two leg values.The operator applies this update to every pair at once.Source: A PROOFS · p. 15
  • The proof studies repeated application of this operator, written Vn+1 = T Vn.The initial values are denoted V0.Source: A PROOFS · p. 15

A.1 PROOF OF PROPOSITION 1

The transitive update converges to divide-and-conquer values in logarithmically many iterations, while those values upper-bound the optimal value. Its trajectory-based loss does not directly train pairs absent from the data’s shared-trajectory relation.

A.1 PROOF OF PROPOSITION 1

  • The transitive operator is monotone, and VDC is its fixed point.The monotonicity and fixed-point arguments bound the iterates above by VDC.Source: §A.1 · p. 15
  • After ⌈log2 diam(G)⌉ iterations, the transitive update equals VDC for every pair, including unreachable pairs.The iterates increase pointwise toward VDC; the convergence argument uses the graph diameter restricted to reachable pairs.Source: §A.1 · p. 15
  • VDC upper-bounds V*, with equality exactly when some policy reaches the goal in the shortest-path distance almost surely.For deterministic dynamics, VDC = V*; the proof also identifies base-case overestimation at transitions whose outcome cannot be forced.Source: §A.1 · pp. 15–16

A.2 PROOF OF PROPOSITION 2

  • The trajectory-based loss forms targets only for pairs in R, so tabular entries outside R retain their initialization.With a shared function approximator, those entries move only through generalization from pairs in R; the loss itself provides no target for them.Source: §A.2 · p. 16

A.3 WHERE THE GTRL FIXED POINT LIES

Under stated tabular and sampling assumptions, the GTRL fixed point lies between the behavior-policy value and the divide-and-conquer value. The appendix also specifies the experimental platform and groups the baselines by value-learning approach.

A.3 WHERE THE GTRL FIXED POINT LIES

  • Qβ ≤ QA ≤ VDC, and Qβ ≤ Q* ≤ VDC, for dataset state-action pairs and goals.The fixed point is obtained by iterating TA from Q0 = 0 under assumptions including exact fitting and positive goal-sampling probability.Source: §A.3 · p. 16

B.1 EXPERIMENTAL SETUP

  • The experiments ran on one workstation with an RTX 5090 GPU, an Intel Core i9-14900K, and 61 GB of system memory.The implementation used JAX, Flax, and Optax; the tasks come from OGBench and run through MuJoCo and Gymnasium.Source: §B.1 · p. 17

B.2 BASELINES

  • The baselines are grouped as behavioral cloning, temporal-difference, Monte Carlo, and triangle-inequality methods.The descriptions distinguish, for example, bootstrapped TD methods from Monte Carlo methods that fit behavior-policy values without bootstrapping.Source: §B.2 · p. 17

B.3 DATASETS

The experiments use nineteen OGBench tasks covering stochastic, deterministic, and stitching settings, with implementation choices adapted to oracle-goal representations. Training and evaluation use shared procedures and task-specific hyperparameters.

B.3 DATASETS

  • Stitch datasets contain trajectories of at most four cell units, while tasks require joining up to eight; most state-goal pairs therefore lack a shared trajectory.Teleport mazes model stochastic transitions, and the remaining ten tasks are deterministic.Source: §B.3 · p. 18

B.4 IMPLEMENTATION DETAILS

  • Two critics handle oracle goals that are state slices: a full-state critic carries Equation 10’s loss, and an oracle-goal critic regresses to it for policy extraction.The implementation also uses a two-network ensemble with sigmoid values and binary cross-entropy; its policy uses the smaller ensemble value normalized by its absolute mean.Source: §B.4 · p. 18

B.5 TRAINING AND EVALUATION

  • Each task is evaluated on five goals with 50 episodes per goal, and its success rate is averaged across checkpoints at 800K, 900K, and 1M.Agents train for 10^6 gradient steps on four seeds; reported scores are means and standard deviations across seeds.Source: §B.5 · p. 18

B.6 HYPERPARAMETERS

C FULL RESULTS

The full-results table presents per-goal success rates and standard deviations for the ten deterministic OGBench tasks. Each task’s overall row averages its five evaluation goals.

C FULL RESULTS

  • Each deterministic task’s overall result is the average of its five evaluation goals.Table 6 supplies the per-goal results behind Table 2.Source: C FULL RESULTS · p. 20
  • Table 6 reports success rate (%) and standard deviation over four seeds for each of five evaluation goals across ten deterministic tasks using oracle-rep variants.The overall row in each task block averages the five goals.Source: Table 6 · p. 20, C FULL RESULTS · p. 20
  • Table 6 marks the best results in red.The supplied passages do not state the table’s numerical comparisons.Source: Table 6 · p. 20

D ADDITIONAL ABLATIONS: SPLIT EXPECTILE

The split-expectile ablation compares the proposed split with using κ = 0.7 for both goal types. The all-optimistic setting reduces performance, especially on two deterministic navigate tasks.

D ADDITIONAL ABLATIONS: SPLIT EXPECTILE

  • 40.2 points on humanoidmaze-large-navigate and 25.3 points on antmaze-large-navigate are lost when κ = 0.7 is used for both goal types.Figure 7 presents the split-expectile ablation; the passage also reports smaller drops of 9.0 and 8.6 points on stochastic tasks.Source: D ADDITIONAL ABLATIONS: SPLIT EXPECTILE · p. 21, Figure 7 · p. 21
  • The split sets κ = 0.7 for decomposable goals and κ = 0.5 for the rest, while the ablation uses κ = 0.7 for both.The passage describes κ = 0.5 as averaging over outcomes and κ = 0.7 as optimistic over subgoals.Source: D ADDITIONAL ABLATIONS: SPLIT EXPECTILE · p. 21
  • Because half the batch carries the one-step target, fitting that target optimistically inflates values everywhere.This is the passage’s explanation for the performance drops under the all-optimistic setting.Source: D ADDITIONAL ABLATIONS: SPLIT EXPECTILE · p. 21

Related papers

Loading 2609.33259v2…