PaperlayerView exact revision on arXiv

Source-linked AI summary

Recursive Value Learning for Long-Horizon Offline Goal-Conditioned RL

Hyeonseong Jeon, Youngwoon Lee

arXiv:2609.02237v1cs.LGcs.RO

TL;DR

Long-horizon offline GCRL is challenged by inaccurate short-range dependencies and error-amplifying max backups. DCRL organizes trajectory segments into balanced trees trained bottom-up, complements behavior-value learning with cross-trajectory propagation, and outperforms prior flat and hierarchical methods on challenging benchmarks.

  • Problem

    Long-horizon offline GCRL must learn long-range values from shorter estimates that may be inaccurate, while max-based backups can amplify overestimation through repeated propagation.

  • Method

    DCRL recursively decomposes in-trajectory segments into balanced binary trees, trains values from leaves to root, and jointly propagates values across trajectories to recover optimal routes.

  • Results

    DCRL substantially outperforms prior flat offline GCRL methods across diverse tasks and surpasses hierarchical methods on several challenging long-horizon tasks.

  • Takeaways & Limitations

    DCRL provides a foundation for scaling offline GCRL to longer horizons by mitigating horizon-induced error accumulation.

  • Takeaways & Limitations

    DCRL assumes deterministic dynamics, and hierarchical approaches outperform it on cube-manipulation tasks despite their shorter horizons.

Abstract

from arXiv · show

Scaling offline goal-conditioned reinforcement learning (GCRL) to long-horizon tasks is difficult because (1) long-range value learning depends on shorter-range estimates that may still be inaccurate, and (2) max-based value backups can amplify overestimation through repeated propagation. We propose DCRL (Divide-and-Conquer RL), which recursively decomposes each trajectory segment into a balanced binary tree and trains the values from leaves to root. Each parent is therefore updated only after its children, using an exact factorization of the observed route rather than selecting among noisy alternatives. Since this objective learns values along demonstrated routes that are not necessarily optimal, DCRL jointly propagates values across trajectories to discover shorter routes. Thanks to the balanced binary tree, DCRL reduces worst-case bootstrap depth from linear to logarithmic, and this shorter dependency structure empirically corresponds to much slower error accumulation. Across diverse goal-reaching tasks, DCRL substantially outperforms prior flat offline GCRL methods, and on the five most challenging long-horizon OGBench tasks, it improves the best prior average score from 55 to 64, surpassing all flat and hierarchical baselines.

1. Introduction

DCRL addresses long-horizon offline GCRL by enforcing bottom-up value learning over balanced trajectory trees and avoiding optimistic selection among noisy alternatives. It combines recursive behavior-value learning with cross-trajectory propagation, outperforming prior methods on challenging tasks.

  • Motivation: Long-range values can inherit inaccurate shorter-range estimates, while max-based backups can repeatedly propagate overestimated candidates.These two mechanisms turn small local errors into larger long-horizon inconsistencies.
  • Method: DCRL recursively splits trajectory segments at their midpoint and trains the resulting balanced binary tree from leaves to root.A horizon-H segment has O(H) nodes but only O(log2 H) sequential composition levels.
  • Method: Exact factorization evaluates the observed route through an intermediate state instead of maximizing over noisy alternatives.Each parent is updated only after its children, while the route is supported by the dataset.
  • Method: DCRL explicitly constructs and executes dependent divide-and-conquer trees, unlike TRL, which samples isolated transitive relations in no particular order.Slot scheduling interleaves multiple trees while preserving bottom-up ordering within each tree.
  • Method: DCRL jointly uses recursive learning for reliable behavior routes and multistep propagation across trajectories to recover shorter optimal routes.The two objectives serve complementary roles: within-trajectory value learning and cross-trajectory route composition.
  • Results: DCRL substantially outperforms prior flat offline GCRL methods across diverse goal-reaching tasks and surpasses hierarchical approaches on several challenging long-horizon tasks.The analysis reports logarithmic rather than linear worst-case bootstrap depth, corresponding to substantially slower error accumulation.

2. Related Work

Related GCRL methods exploit quasimetric structure through explicit constraints, implicit backups, or planning. DCRL is most closely related to TDP and TRL but differs in fixing midpoint decompositions and enforcing bottom-up ordering.

  • Quasimetrics in GCRL: In deterministic environments, GCRL can learn shortest-path distances that form an asymmetric quasimetric satisfying the triangle inequality.This structure is used by several families of goal-conditioned methods.
  • Quasimetrics in GCRL: Explicit methods impose quasimetric constraints in value or distance representations, whereas implicit methods enforce triangle inequalities through value backups.Planning-based methods instead compose shortest paths at inference time.
  • Implicit methods: TDP recursively predicts intermediate subgoals and learns top-down, while DCRL fixes the midpoint subgoal and learns bottom-up.Greedy decomposition selection in TDP can overestimate the chosen decomposition.
  • Implicit methods: TRL uses in-trajectory backups with optimistic split selection, but learns values in no particular order from independently sampled relations.DCRL instead preserves parent–child dependencies in an explicitly constructed balanced tree.

3. Preliminaries

The paper studies deterministic offline GCRL, where any state may be a goal and values are defined by discounted first hitting time. In this setting, optimal values correspond to shortest-path distances satisfying a triangle inequality.

  • Problem Setting: The problem setting is a deterministic controlled Markov process with state and action spaces, an initial-state distribution, deterministic transitions, and a discount factor.The dataset consists of unlabeled trajectories, and any state can serve as a goal.
  • Value Function: The hitting-time formulation gives reward 1 upon first reaching the goal, after which the agent enters an absorbing state.The value is the expected discounted reward under a goal-conditioned policy.
  • Value Function: The optimal value is the maximum over policies, and in deterministic environments it corresponds to shortest-path distance through V* = γ^d*.Here d* is the minimum number of steps from a state to a goal.
  • Triangle Inequality: Optimal distance satisfies the triangle inequality for any states, with equality when the intermediate state lies on a shortest path.Through V* = γ^d*, this becomes a multiplicative triangle inequality on values.
  • Triangle Inequality: Prior methods use a transitive backup that maximizes V(s,w) · V(w,g) over intermediate states w.This backup turns the triangle-inequality property into a value-learning procedure.

4. Recursive Value Learning for Long-Horizon Offline GCRL

DCRL recursively decomposes trajectory segments into balanced binary trees, learns values bottom-up, and combines this with cross-trajectory propagation to recover shorter routes and optimal values. Its logarithmic bootstrap depth and selection-free route factorization target long-horizon error accumulation while slot scheduling preserves ordering and minibatch diversity.

  • Recursive Divide-and-Conquer Value Learning: DCRL recursively bisects each trajectory segment into a balanced binary tree and trains values from single-step leaves to the root.A horizon-H segment contains O(H) nodes and O(log2 H) sequential composition levels.
  • Recursive Divide-and-Conquer Value Learning: O(log2 H) bootstrap depth replaces the O(H) worst-case depth of standard backups for horizon-H segments.The shallower dependency path is intended to reduce long-range error accumulation.
  • Update Rule for Recursive Value Learning: Exact midpoint factorization evaluates a fixed observed route without maximizing over noisy intermediate states, thereby learning behavior values rather than necessarily optimal values.The route distance upper-bounds the shortest-path distance, and route suboptimality can grow under composition.
  • Value Propagation for Optimality: DCRL adds globally relabeled multistep propagation to compose segments across trajectories and recover optimal values that recursive learning alone cannot provide.The two objectives have complementary roles: recursive learning supplies reliable behavior routes, while propagation identifies shorter routes.
  • Implementation: Parallel Slot Scheduling: Multiple independent slots process trees bottom-up while desynchronization mixes short-horizon and long-horizon segments within minibatches.Each slot schedules a new tree after consuming its current one.
  • Implementation: Critic Learning: DCRL trains a shared action-value function with divide-and-conquer and propagation losses simultaneously.The divide-and-conquer loss uses recursive tree samples and exact value factorization.

5. Experiments

Experiments evaluate DCRL against diverse offline GCRL and hierarchical baselines across long-horizon tasks, then analyze propagation horizons, error accumulation, and divide-and-conquer design choices. DCRL performs strongly across benchmarks, while recursive scheduling, propagation, and exact factorization emerge as important design components.

  • 5.1. How Well Does DCRL Compare with Prior Offline GCRL Methods?: DCRL achieves the best average score on the five most challenging long-horizon OGBench tasks, outperforming flat and hierarchical baselines.It is the only flat method with nonzero success on cube-octuple and attains the highest scores on humanoidmaze-giant and both puzzle tasks.
  • 5.1. How Well Does DCRL Compare with Prior Offline GCRL Methods?: DCRL performs best on both state-based and pixel-based standard-horizon OGBench tasks across diverse domains and observation modalities.Figure 7 aggregates results over 10 state-based and 10 pixel-based environments.
  • 5.1. How Well Does DCRL Compare with Prior Offline GCRL Methods?: DCRL is the only flat method that completes all four CALVIN subtasks consecutively in the evaluated compositional long-horizon manipulation setting.The evaluation uses four sequential subtasks and 1,239 task-agnostic trajectories spanning 34 subtasks.
  • 5.2. Is DCRL Better Than TD and TRL Across Propagation and Task Horizons?: For propagation horizons n≥25, DCRL-n outperforms TD-n and TRL-n on both long-horizon tasks, whereas smaller n limits its advantage.At n∈{1,5}, DCRL-n performs similarly to TD-n and worse than TRL-n because its propagation chain remains long, O(H/n).
  • 5.2. Is DCRL Better Than TD and TRL Across Propagation and Task Horizons?: DCRL-n’s logarithmic bootstrap depth is accompanied by slower long-range Q-error growth than TD-n and TRL-n as task horizon increases.In the controlled combination-lock comparison at fixed n=64, DCRL-n remains relatively flat while both baselines accumulate error rapidly.
  • 5.3. How Does DCRL Compare with Alternative Divide-and-Conquer Strategies?: Reversing recursive learning order reduces success from 93% to 18%, while DCRL achieves over 1.7× TRL’s success rate at 24% lower throughput.Random splitting preserves performance but lowers throughput, whereas removing recursion, propagation, or exact factorization degrades performance in ablations.

6. Conclusion

DCRL uses balanced-tree recursive value learning, exact route factorization, and cross-trajectory propagation to reduce long-horizon error while recovering shorter routes. Its analysis gives logarithmic bootstrap depth, but deterministic dynamics are required and hierarchy can remain advantageous on some tasks.

  • Conclusion: DCRL recursively splits in-trajectory segments into a balanced binary tree and learns behavior values from leaves to root before propagating them across trajectories toward optimality.The two objectives provide reliable behavior routes and combine segments from different trajectories to identify shorter routes.
  • Conclusion: DCRL substantially outperforms prior flat methods and surpasses hierarchical methods on several challenging long-horizon tasks.The paper presents this as evidence that recursive value learning can support longer-horizon offline GCRL.
  • Limitations: DCRL assumes deterministic dynamics because exact factorization generally fails under stochastic dynamics, and hierarchical approaches outperform it on cube-manipulation tasks.The paper identifies extending recursive sampling to stochastic dynamics and understanding when hierarchy remains beneficial as future work.
  • Theoretical validation: DCRL-n has Θ(log(𝐻/𝑛)) sequential propagation levels, compared with Θ(𝐻/𝑛) for TD-n, while TRL-n depends on its realized splits.Midpoint splitting halves the longest remaining segment at each level; random or endpoint-adjacent splits can have different depths.
  • Theoretical validation: Logarithmic-depth realizations yield a polynomial error bound in 𝐻/𝑛, whereas highly unbalanced realizations can produce a much looser bound because selection amplification compounds with depth.The static upper bound cannot separate TD-n from DCRL because both ultimately depend on the same 𝐻/𝑛 grounded segments.
  • Theoretical validation: A shorter propagation path requires fewer sequential stages for grounded information to reach long-horizon values, and experiments test whether this corresponds to lower finite-budget error.The analysis treats this as a structural advantage rather than a complete determination of estimation error.
  • Conclusion: Exact route factorization avoids optimistic selection among noisy alternatives, while child-to-parent scheduling explicitly orders propagation from grounded segments to long-horizon values.These mechanisms target selection error and dependency-ordering error separately.

A.2.2. Empirical Validation

The empirical validation uses controlled combination-lock experiments and benchmark success-rate comparisons to isolate bootstrap depth, scheduling, selection, and propagation effects. DCRL-n shows the lowest long-range error and performs best for larger propagation horizons, although symmetric TRL-n improvements do not consistently transfer to benchmark performance.

  • Experimental design: The experiments test whether shallower dependency structures slow long-range error growth and whether training children before parents realizes the depth advantage.The controlled study holds architecture and optimization budgets fixed across variants.
  • Didactic environment: Combination-lock provides exact ground-truth distances, d*(s, g) = g−s, enabling direct measurement of long-range error without benchmark proxy discretization error.The task is adapted to goal-conditioned value learning because the methods factor through intermediate state–goal pairs.
  • Error accumulation: At long horizons, error ranks TRL > TRL-n (𝜅= 0.7) > TRL-n (𝜅= 0.5) ≈ TD-n > DCRL-n, with DCRL-n remaining relatively flat and lowest.The comparison spans seven horizons from 256 to 2,048.
  • Scheduling ablation: Beyond 𝐻=1024, unscheduled DCRL degrades sharply, reaching 3.72 at 𝐻=1536 and 9.14 at 𝐻=2048, supporting child-to-parent scheduling.At 𝐻=1024, DCRL (w/o sched.) reports 𝒜=1.61 versus DCRL: 1.78.
  • Scope: The controlled error study uses distance-space squared-loss variants and omits policy learning, so it does not measure action-selection amplification under multimodal benchmark data.Its tied intermediate-state values also make upper-expectile transitive selection effects especially interpretable.
  • Propagation horizons: DCRL-n performs best for 𝑛≥25 on all three evaluated tasks, while the two TRL-n variants perform similarly overall.Thus, symmetric transitive regression reduces controlled-environment error but does not consistently yield higher benchmark success.

D. Alternative Divide-and-Conquer Strategies

The section compares fixed, random, learned, curriculum, and distance-weighted divide-and-conquer strategies, alongside ablations removing recursive scheduling, propagation, or forward traversal.

  • Alternative recursive strategies: Curriculum learning increases trajectory lengths in manually defined stages, while distance re-weighting makes short pairs dominate through a distance-dependent loss weight.The curriculum uses step size Δ; distance re-weighting uses λ to control decay, with λ = 0 giving uniform weighting.
  • Alternative recursive strategies: DCRL splits each trajectory recursively at its midpoint, whereas random-split variants sample an interior subgoal uniformly during tree construction.The random-split implementation otherwise follows the same recursive procedure.
  • Alternative recursive strategies: Max-based backup samples 10 interior subgoals and selects the candidate with the highest factorized value under the current critic.Because the critic determines both the split and its children, this variant constructs the tree top-down.
  • Ablations: Removing recursive scheduling eliminates the guarantee that child subproblems are trained before their parent and omits the one-step leaves that ground the recursive tree.The ablation samples trajectory pairs independently and splits each once at its midpoint.
  • Ablations: Without reliable base-case supervision, the factorization target becomes self-referential and the critic collapses toward zero; an explicit adjacent-transition loss restores the γ^1 base case.This grounding term isolates scheduling while retaining factorization and propagation objectives.
  • Ablations: Removing propagation raises κdc from 0.5 to 0.7 so the recursive objective favors higher-valued routes rather than only behavior values.Reverse scheduling preserves the midpoint tree and objectives but emits parents before children.

E. Experimental Setup

The experiments evaluate offline goal-conditioned methods across OGBench and CALVIN, using state and pixel observations, multiple seeds, checkpoints, rollouts, and policy-extraction procedures.

  • Policy extraction: Policy extraction selects the highest-Q action after training the goal-conditioned action-value function.Experiments also compare reparameterized-gradient and rejection-sampling extraction procedures.
  • Benchmarks: The evaluation uses OGBench and CALVIN environments to assess offline goal-conditioned reinforcement learning algorithms.OGBench includes distinct start–goal test tasks, while CALVIN uses an in-domain four-subtask sequence.
  • Pixel-based CALVIN: Pixel-based CALVIN re-renders cached 128 × 128 × 3 RGB observations and combines each image with a 15-dimensional proprioceptive vector.The goal is the rendered target scene with all four subtasks complete, and success at level k requires completing at least k subtasks in order.
  • Pixel-based CALVIN: The study uses a smaller Impala CNN for pixel-based CALVIN, with separate observation and goal encoders trained end-to-end and random-crop augmentation.The encoder matches that used for pixel-based OGBench to avoid an architectural confound.
  • OGBench protocol: Long-horizon OGBench results average four seeds across the 800k, 900k, and 1M checkpoints, using propagation n = 100 on humanoidmaze-giant-1B and puzzle-{4x5,4x6}-1B.Cube-quadruple-100M and cube-octuple-1B use n = 25 because their subtasks are shorter.
  • Ablation protocol: The DCRL child-estimate ablation evaluates Q·Q̄, Q̄·Q̄, Q·Q, and Q̄·Q across humanoidmaze-giant and puzzle-4x6.Using only the online network causes value estimates to collapse, while other configurations degrade performance on at least one task.

H.2. Expectile Parameters

The expectile and training-budget studies identify default expectiles and compare DCRL with TRL across performance–efficiency trade-offs.

  • Expectile sensitivity: κdc = 0.5 and κprop = 0.7 yield the best performance on humanoidmaze-giant and cube-triple.Deviating from either value generally degrades performance.
  • Training efficiency: In humanoidmaze-giant, DCRL reaches 90% success in under 3 hours, whereas TRL remains below 80% after 8 hours.The comparison varies DCRL’s slot count and TRL’s batch size.
  • Training efficiency: In cube-triple, DCRL reaches 70% success in under 2 hours, whereas TRL stalls below 50% and does not improve with a larger training budget.The figure reports the same Pareto-style performance versus training-time comparison.

I. Divide-and-Conquer Strategies on Cube Manipulation

The cube-triple comparison evaluates alternative divide-and-conquer strategies using identical batch size and reports both success rate and training throughput.

  • Results: DCRL achieves performance comparable to random splitting and about 1.7× the success rate of the best TRL variant on cube-triple.DCRL incurs approximately 7% lower throughput than the comparison setting.
  • Ablation results: Random splitting performs no better than DCRL while reducing throughput by 43%.Curriculum learning remains highly sensitive to Δ, and distance re-weighting does not improve upon TRL.

J.1. CALVIN Benchmark

This benchmark section organizes results across CALVIN and OGBench settings, including state-based, pixel-based, standard, and long-horizon evaluations, with accompanying hyperparameter tables.

  • Benchmark results: Full results are reported separately for state-based CALVIN, pixel-based CALVIN, and large-scale long-horizon OGBench tasks.The pixel-based CALVIN table reports consecutive-subtask success rates and average subtasks completed per rollout.
  • Benchmark results: Additional result tables cover state-based and pixel-based OGBench tasks.
  • Experimental configuration: Hyperparameter tables distinguish common settings from long-horizon OGBench, standard OGBench, and CALVIN configurations.A task-specific table defines parameters including the BC coefficient, sample count, subgoal count, random goal distance, goal regularization weight, expectile, and distance re-weighting factor.
Loading 2609.02237v1…