acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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 evaluated flat and hierarchical baselines.

Primary area:
reinforcement learning
Keywords:
reinforcement learning, goal-conditioned rl, offline rl

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_wuadOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduces DCRL (Divide-and-Conquer RL) to mitigate the accumulation of value estimation errors in long-horizon offline goal-conditioned reinforcement learning. DCRL recursively decomposes trajectory segments into a balanced binary tree and learns values in a child-to-parent (or leaf-to-root) order, ensuring that long-range estimates are grounded as much as possible in previously learned shorter-range estimates. For demonstrated trajectories, DCRL employs a selection-free exact factorization method using fixed midpoints to learn route-specific behavior values, thereby avoiding the optimistic error amplification associated with max-based intermediate-state selection. Since this objective only recovers values for demonstrated routes, the authors further utilize multistep value propagation and globally relabeled goals, enabling a shared value function to compose shorter paths across trajectories and approximate optimal values. Experiments cover challenging long-horizon OGBench tasks, standard state/pixel OGBench tasks, and CALVIN, alongside analyses of propagation horizons, task horizons, and alternative divide-and-conquer strategies. Overall results demonstrate that DCRL outperforms existing flat GCRL methods in most long-horizon settings and surpasses the tested hierarchical baselines in terms of average performance.

Critical strengths
  1. The core method is simple and grounded in a clear structural rationale. DCRL reformulates long-horizon value learning as a dependency-ordering problem, organizing the progression from short- to long-horizon value learning via an explicit recursive tree and child-to-parent scheduling, rather than merely modifying the loss function or sampling distribution. The ablation studies regarding reverse-order execution and the removal of recursion provide direct empirical support for this core mechanism.
  2. The empirical validation presented in the main text is comprehensive and directly addresses the central hypothesis. The paper evaluates the method against a wide range of offline GCRL baselines, spanning long-horizon tasks, standard OGBench tasks, state- and pixel-based observations, and the CALVIN benchmark, while further investigating factors such as propagation/task horizons, error accumulation, and various divide-and-conquer variants. The experiments not only demonstrate final benchmark performance but also systematically analyze the roles of recursion, ordering, propagation, and update rules.
Critical weaknesses
  1. The theoretical consistency between the two training objectives for the shared critic is not yet fully established. The exact factorization of L_{dc} targets the value of demonstrated-route behavior, whereas L_{prop} trains the same critic to learn the optimal value across trajectories. When the fixed midpoint does not lie on the shortest path, the value semantics associated with the two objectives differ. Although Table 3 indicates that they are empirically complementary, the main text does not articulate the compatibility conditions or a fixed-point interpretation for their joint optimization; consequently, it is currently difficult to determine whether this complementarity holds generally.
  2. The applicability of the method is constrained by the assumption of deterministic dynamics. The exact factorization in DCRL relies on deterministic goal-reaching dynamics; the authors have explicitly noted in the "Limitations" section that this property generally does not hold under stochastic dynamics. While this limitation does not affect the experimental conclusions of this paper, it renders the method less general than the standard offline GCRL setting.
Questions for authors
  1. Regarding the joint optimization of the shared critic: Did the authors observe significant conflict between L_{dc} and L_{prop} during training, such as inconsistent gradient directions or a scenario where the improvement of one objective leads to the deterioration of the other? Please provide details if results are available regarding separate critics, disabling one of the losses, or employing different loss-balancing strategies. This information would help determine whether these two distinct value semantics are stably compatible in practice.
  2. Definition of OGBench evaluation scores. Table 1 in the main text uses a task "score", while Figure 7 uses "Aggregated Score (%)", yet the text does not explicitly define these metrics or the aggregation procedure. Please clarify whether these metrics correspond to the goal-reaching success rate and explain how the aggregation is performed across start-goal tasks and environments.
7 comments

We thank the reviewer for the positive assessment and the concrete questions. We address them with new analyses and experiments, and have uploaded a revised PDF, to which all table and figure numbers below refer:

  • Compatibility of the two objectives (A1, A3). We give a fixed-point interpretation of the joint objective and show that the two losses do not conflict in practice. Their gradients are aligned, they do not trade off during training, and performance is stable once propagation has at least the default weight (λ=1\lambda=1). On a controlled suboptimality sweep, DCRL outperforms TD-n by 1.7–2.2$\times$ at every level. We have added this analysis to App. H.4.
  • Stochastic dynamics (A2). The deterministic assumption is shared by triangle-inequality methods, and we outline a possible extension.
  • Evaluation scores (A4). The per-environment scores and the aggregated score are both goal-reaching success rates under the evaluation setup in App. E, and the aggregated score is the mean over environments. We now state this explicitly in App. E.
AuthorsOpenReview ↗

A1. Compatibility of the two objectives

The exact factorization of LdcL_{dc} targets the value of demonstrated-route behavior, whereas LpropL_{prop} trains the same critic to learn the optimal value across trajectories. ... the main text does not articulate the compatibility conditions or a fixed-point interpretation for their joint optimization.

We thank the reviewer for this question. Under deterministic dynamics, the value of a recorded route is a lower bound on the optimal value, Vroute(s,g)≤V∗(s,g)V^{\text{route}}(s,g) \le V^{\ast}(s,g), with equality when the route is a shortest path. This gives the following interpretation:

  • Compatible case. When recorded routes are shortest paths, the two targets coincide and V∗V^{\ast} is a fixed point of the joint objective.
  • Suboptimal routes. LdcL_{dc} pulls the shared critic toward VrouteV^{\text{route}}, while LpropL_{prop} pulls it toward V∗V^{\ast}. For a shared critic, the joint minimizer on such pairs lies between the two targets, so the fixed point is between VrouteV^{\text{route}} and V∗V^{\ast}, at a position set by the loss weight and by how often each pair is sampled.

Our empirical measurements agree with this picture. We built pointmaze-large datasets with the OGBench navigate procedure, in which the agent turns back to a recently visited cell with probability pp per step. This lengthens the recorded routes at fixed coverage, from a median of 1.18$\times$ the shortest path at p=0p=0 to 2.03$\times$ at p=0.02p=0.02. On state-goal pairs whose recorded route is longer than the shortest path, DCRL's learned distances lie between the two targets (0.71–0.78$\times$ the recorded route and 1.67–1.86$\times$ the shortest path). The remaining pull toward the recorded route does not hurt DCRL in practice. TD-n is DCRL without LdcL_{dc}, so it has no pull toward the recorded route, yet DCRL outperforms it by 1.7–2.2$\times$ at every level of suboptimality (e.g., 62.8 vs. 28.4% at p=0.01p=0.01, n=25n=25, 3 seeds). We have added this fixed-point discussion and the suboptimality sweep to App. H.4 (Table 7).

In short, the two objectives are compatible. They coincide on shortest paths, and on suboptimal routes they settle between the two targets while DCRL still outperforms TD-n at every level of suboptimality.

AuthorsOpenReview ↗

A2. Stochastic dynamics

The applicability of the method is constrained by the assumption of deterministic dynamics. ... it renders the method less general than the standard offline GCRL setting.

We agree. Under stochastic dynamics, the exact factorization generally fails because the expectation of a product need not factorize. This assumption is shared by the quasimetric GCRL methods discussed in Sec. 2, in particular the "implicit" methods that, like DCRL, enforce the triangle inequality through value backups, such as TDP (Jurgenson et al., 2020), COE (Piękos et al., 2023) and TRL (Park et al., 2026). DCRL could potentially be extended to stochastic dynamics by replacing the exact factorization with the stochastic triangle inequality of Myers et al. (2024), which we leave for future work.

In short, this is a limitation shared by triangle-inequality methods, and the stochastic triangle inequality offers a possible extension.

Reviewer_E7MZOpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
2
Presentation
2
Soundness
2(+1)
Read review
Paper summary

The paper proposes Divide-and-Conquer RL, a method for GCRL designed to improve the value propagation using a balanced binary tree to aggregate values inside the dataset trajectories. The main algorithmic contribution is a combination of the tree-based value aggregation with a slot-based scheduler that is claimed to ensure that the ancestor nodes of the tree are updated after the child nodes are updated. The tree-based value aggregation is combined with n-step upper-expectile propagation to learn values that are closer to optimal than behavior ones. This contribution is supported by theoretical analysis and extensive empirical evaluations, including both ablation studies, controlled experiment, and comparisons to multiple baselines.

Critical strengths
  • Strong empirical results: The benchmark numbers reported in the paper show that DCRL substantially outperforms its closest baselines, TD-n and TRL on humanoidmaze and puzzle long-horizon tasks.
  • Broad evaluation: The paper contains a lot of experiments including comparisons to baselines spanning substantial amount of datasets, including locomotion, manipulation, state and visual observations, and CALVIN. It also includes ablations and a sweep over propagation horizon.
Critical weaknesses

The description does not match implementation

The paper describes sampling each node in the tree from leaves to roots with every child learned before its parent. The implementation in the supplementary code is different: every slot emits each tree level to a pool, then the batch size of nodes is sampled from this pool. Next step moves to the next tree level and creates a new pool. My estimates show that this could result in training on 2-8% of all emitted nodes for 4000-horizon tasks. This means not all children are trained before the parent, with most parents being trained using value estimates that were not trained in the previous gradient steps this pass. This also means that not all parent nodes are trained at all. This violates the claim that "all earlier descendants have already appeared in preceding batches". Additionally, the supplementary code uses oracle goal representation, which isn't disclosed in the paper. Neither the dataset types (navigate, play) are reported in the paper. I consider this a minor issue since all baselines seem to use the same setup.

The attribution of the gains is not supported

The paper attributes the gains to logarithmic bootstrap depth, child-to-parent scheduling, and exact trajectory factorization that avoids the optimistic selection bias.

  • Depth: random splits match the midpoint splits (92 vs 93 in Table 2, 72 vs 71 in Table 5). TRL already is logarithmic depth in expectation. I believe the measured decrease in throughput for the random splits is also an implementation artifact mostly explained by a slower sampler implementation using scalar RNG call.
  • Value learning: Divide-and-Conquer Loss is the same across different values of nn. The results in Table 9 show that at n=1 humanoidmaze-giant-1B DCRL has performance of 0% and in Table 10 at n=5 success rate is 1%. At the same time MC (which is regression to γi−j\gamma^{i-j}) is reported at 79% (Table 8). So either the Divide-and-Conquer Loss does not provide the correct long-range values or the Propagation loss overwhelms the training.
  • Overestimation: Figure 2 shows that TRL value function provides higher distances, which corresponds to underestimation of values (values are the opposite to distance, higher value corresponds to smaller distance and vice versa). So it points in the direction that TRL values propagated slower, not that they were overestimated.
  • The main comparison: TRL result of 54% on humanoidmaze is lower than TRL reported result of 79% (Park et al., 2026) which might be attributed to a different policy extraction (if Table 21 is correct) or different sampling procedure (if the supplementary code was used). This make the claim of 1.7×1.7\times gain overstated.
  • I believe reverse order ablation uses a different sampling path that results in a different batch composition (beyond order). In the code your main experiments use _precompute_schedule and shallow_first is implemented in a different code path. I suspect that the difference between DCRL and DCRL \w reverse order (18% vs 93%) is mainly explained by a different distribution of sampled states, not the order.

My hypothesis is that the majority of empirical gain comes from a composition of dense MC regression to γj−i\gamma^{j-i} on close states (both as part of the Divide-and-Conquer Loss and Propagation losses) with n-step propagation that is known to help. The corresponding control is missing: MC on the same node distribution below n steps combined with the same Propagation loss would isolate the effect of your method.

Questions for authors
  • Which configuration produced the reported number on TRL humanoidmaze and how it differs from the one published in Park et al., 2026? How does DCRL compare to TRL under the configuration published in Park et al., 2026?
  • How were the reported results produced, which slot scheduler was used to run the main experiments? What fraction of scheduled nodes was actually used in training?
  • Can you run the proposed control experiment? (MC regression to γj−i\gamma^{j-i} on pairs drawn from the same node distribution as DCRL, truncated at n, combined with the same Propagation loss)
  • Can you run the experiment with reversed node order on the matching distribution of states? Please report the segment length distribution observed in both runs
11 comments

We thank the reviewer for an exceptionally careful review, including a close reading of our code. Several of the reviewer's concerns are valid, and we ran every requested experiment. The results correct how we described and attributed DCRL's gains, but they do not weaken the gains themselves. The gains come from recursive bootstrapping, in which each segment's value is regressed onto the values of its own two sub-segments and shorter segments are trained far more often than longer ones. We have uploaded a revised PDF with these corrections, and all table and figure numbers below refer to it.

Summary of concerns and answers.

  • The scheduler in the code differs from the paper (A1). Correct. The code trains a random subset of tree nodes, not every child before its parent. This is intentional, since it keeps batches diverse, and it outperforms training every node in strict child-first order (92.7 vs. 67.3). We have corrected the description throughout the paper.
  • Bootstrap depth does not explain the gain, since both DCRL and TRL have logarithmic depth in expectation (A2.1). We agree. DCRL with random splits has the same bootstrap depth as TRL, yet it outperforms TRL by a wide margin (92 vs. 54). The difference is recursive bootstrapping, and we now prove that, under a fixed training budget, it admits a tighter error bound at the same bootstrap depth (Prop. 2).
  • Why does DCRL fail at small nn (A2.2)? The cause is neither wrong long-range values nor an overwhelming propagation loss, but optimistic propagation. A symmetric propagation expectile fixes it, raising DCRL from 1 to 78 at n=5n=5.
  • The MC baseline reaches 79%, so is bootstrapping needed (A2.2, A2.3)? The 79% was copied from prior work, and our reproduction reaches only 14±2214\pm22% (seeds range from 1 to 51%). In the control the reviewer proposed, exact MC returns on short tree nodes (j−i≤nj-i\le n) match DCRL at n=100n=100 but collapse at short propagation horizons (4 vs. 78 at n=5n=5), where bootstrapping is needed.
  • The reverse-order ablation changed the sampler as well as the order (A3). Correct. With matched samplers, the order matters only when each batch holds a single tree depth (child-first 67 vs. parent-first 18 under the strict schedule). With our default asynchronous sampler, learning is bottom-up under either order, so DCRL and its reverse-order variant perform similarly (93 vs. 92).
  • TRL underestimates rather than overestimates, and its configuration differs from the TRL paper's (A4). Correct on both counts, and we have fixed the text. Under TRL's own configuration, DCRL still outperforms it (95 vs. 84).

DCRL's own success rates in Tables 1–2 are unchanged. Table 2 now reports matched reverse-order comparisons (A3) and remeasured throughput (A2.1), and entries taken from prior work are marked (†\dagger) or replaced by our reproductions (Tables 1 and 14).

AuthorsOpenReview ↗

A2. Attribution of the gains (1/2)

A2.1 Depth

random splits match the midpoint splits. TRL already is logarithmic depth in expectation.

We agree that depth does not explain the gain. DCRL with random splits has the same bootstrap depth as TRL (logarithmic in expectation, linear in the worst case), yet it clearly outperforms TRL (92 vs. 54 under the same protocol). The difference lies in what each segment is bootstrapped from. DCRL regresses each tree node onto its two children at a fixed split of the same recorded segment, and short segments dominate its batches, so long-range values are built on short-range values that are trained far more often. TRL instead samples pairs of all lengths in no particular order, and each target combines values at a sampled intermediate state.

We now formalize this in a budget-aware analysis (Prop. 2, App. A.2.1). DCRL with random splits and TRL-n with a symmetric transitive expectile share the same backup and depth, so the original bound cannot separate them. Under a fixed training budget, however, DCRL's sampling concentrates updates on the short segments that every long-range value depends on, and its error bound is smaller by a factor of Θ(H/n)\Theta(\sqrt{H/n}) than under TRL's uniform pair sampling (about 10×10\times for H/n=100H/n=100). We no longer present logarithmic depth as a source of the gain and instead attribute it to recursive bootstrapping (abstract, Sec. 1, 2, 4 and App. A.2).

In short, depth alone cannot explain DCRL's gain. Recursive bootstrapping does, as we show empirically (Table 2, Fig. 9) and, under a fixed training budget, theoretically (Prop. 2).

... the measured decrease in throughput for the random splits is also an implementation artifact mostly explained by a slower sampler implementation using scalar RNG call.

The reviewer is correct. With a vectorized generator, DCRL with random splits trains 25% faster than with midpoint splits on humanoidmaze-giant-1B and 21% faster on cube-triple-100M, likely because its deeper trees emit fewer nodes per level. We have removed the throughput argument for midpoint splits (Sec. 5.3, App. I), updated the throughput columns of Tables 2 and 11, and Sec. 4.1 now presents the midpoint as our default and notes that random splits perform on par.

In short, random splits are not slower, and DCRL does not depend on the split point.

AuthorsOpenReview ↗

A2. Attribution of the gains (2/2)

A2.2 Value learning

At the same time MC is reported at 79% (Table 8).

Thank you for pointing this out. In the submission, we took the MC entry on humanoidmaze-giant-1B (79%) from Park et al. (2026) without running it ourselves or marking it as reported. This was a mistake, since the 1B dataset is not released and is collected independently by each work, so the numbers are not directly comparable. We have now trained MC in our pipeline with Park et al.'s published configuration (same network, learning rate, discount, goal sampling and reparameterized gradients with α=0.3\alpha=0.3). It reaches 14±2214\pm22% (avg. 750k–1M, 4 seeds), with seeds ranging from 1% to 51%, so MC is highly seed-sensitive on this task. In the same pipeline, our TRL reproduction exceeds its reported number (84 vs. 79, A4), so we attribute the gap to the different dataset and MC's high variance rather than to an implementation issue. We have replaced the MC entries in Tables 1 and 14 with our reproduction and marked all other numbers taken from prior work (†\dagger).

In short, the 79% was copied from prior work and listed alongside our own runs without being marked. Our reproduction (14±2214\pm22%) now replaces it, and all numbers taken from prior work are marked with †\dagger.

So either the Divide-and-Conquer Loss does not provide the correct long-range values or the Propagation loss overwhelms the training.

We tested both hypotheses on humanoidmaze-giant-1B, and neither explains the small-nn failure.

  • Wrong long-range values? No. With the same propagation loss, adding the divide-and-conquer loss to TD-n lowers the distance error to ground truth by 24–34% for n≤25n\le 25 (n=1n=1: 7.4 vs. 11.2 grid cells), including at the most distant goals.
  • Propagation overwhelms? No. On trained checkpoints (n=1,25,100n=1, 25, 100, 4 seeds), the propagation gradient norm is at most 1.4×1.4\times the divide-and-conquer one (about half at n=1n=1), and the two gradients have positive cosine similarity everywhere (+0.11+0.11 to +0.80+0.80, App. H.4).

The failure lies in the propagation step itself. With κprop=0.7\kappa_{prop}=0.7, a short optimistic bootstrap is chained over thousands of steps, so overestimation accumulates. At n=1n=1, the learned distances are too short by 11.2 cells for TD-n and 7.2 for DCRL, and by only 2.2 and 0.4 at n=25n=25. Changing only κprop\kappa_{prop} to the symmetric 0.5 removes the failure (avg. 750k–1M, 4 seeds):

MethodExpectilesn=1n=1n=5n=5n=10n=10n=25n=25n=100n=100
DCRLκprop=0.7\kappa_{prop}=0.7 (default)01419093
DCRLκprop=0.5\kappa_{prop}=0.5878848989
TRL-n$^*$all 0.50.5101219
TD-nκprop=0.5\kappa_{prop}=0.509447374

∗^*Transitive and propagation expectiles both 0.5, unlike Fig. 12's TRL-n (κ=0.5\kappa=0.5), which lowers only the transitive expectile.

With the same symmetric expectiles, TD-n (DCRL without the divide-and-conquer loss) and TRL-n remain far below DCRL at short horizons, so the fix relies on DCRL's recursive target, not on the expectile alone. We have added these analyses and guidance on choosing nn and κprop\kappa_{prop} to App. H.6 (Table 9).

In short, neither hypothesis explains the small-nn failure. It comes from optimistic propagation, and a symmetric κprop\kappa_{prop} fixes it.

A2.3 Recursive value learning with MC returns

Can you run the proposed control experiment? (MC regression to γj−i\gamma^{j-i} on pairs drawn from the same node distribution as DCRL, truncated at n, combined with the same propagation loss)

The reviewer hypothesized that most of DCRL's gain comes from dense MC regression to γj−i\gamma^{j-i} on nearby states combined with nn-step propagation, rather than from bootstrapping. We ran the proposed control. It keeps DCRL's tree nodes, schedule and propagation loss, and replaces the bootstrapped target with the exact MC return on nodes with j−i≤nj-i\le n (humanoidmaze-giant-1B, avg. 750k–1M, 4 seeds):

κprop\kappa_{prop}Recursive value learning withn=5n=5n=10n=10n=25n=25n=100n=100
0.7MC returns (reviewer's control)0118092
0.7Bootstrapping (DCRL)1419093
0.5MC returns (reviewer's control)4518890
0.5Bootstrapping (DCRL)78848989

At n=100n=100, the control matches DCRL, which supports the reviewer's hypothesis for long propagation horizons. At shorter horizons, it falls far behind (n=10n=10: 11 vs. 41 and 51 vs. 84). We have added these results to App. H.6 (Table 10) and revised our claims accordingly.

In short, the reviewer's hypothesis holds at long propagation horizons, but at short horizons bootstrapping is what keeps DCRL robust.

Reviewer_R2PwOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
3(+1)
Read review
Paper summary

This paper proposes Divide-and-Conquer RL (DCRL) to improve value learning in long-horizon offline goal-conditioned RL.

The main idea is to split an observed trajectory into two shorter segments, recursively repeat this process, and train the value function from short segments to long ones. The value of a longer segment is estimated by combining the values of its two shorter segments. By training the shorter segments first, the method aims to reduce errors caused by learning long-horizon values from inaccurate estimates.

However, observed trajectories may not be optimal. The authors therefore add another learning objective that propagates values across trajectories to find shorter paths.

Experiments on OGBench and CALVIN show that DCRL outperforms several existing methods, including TRL, especially on challenging long-horizon tasks.

Critical strengths
  1. A simple and interesting approach to long-horizon value learning. Instead of randomly sampling trajectory segments for value updates, DCRL explicitly trains shorter segments before longer ones. This is a natural way to use the structure of recorded trajectories. The recursive decomposition also reduces the number of sequential backup steps needed to propagate value information over a long trajectory. The idea is straightforward and could be useful beyond the specific method studied in this paper.

  2. Strong experimental results with useful ablations. DCRL achieves strong performance on several challenging OGBench tasks. On the five hardest tasks, it improves the best baseline's average success rate from 55% to 64%. The authors also compare against TRL and TD-n, investigate how errors change with the task horizon, and test different training orders and decomposition strategies. These experiments provide good evidence that the proposed training schedule is effective.

Critical weaknesses
  1. It is unclear why recursive bootstrapping is better than directly learning from the observed trajectories. DCRL still relies on bootstrapping: it estimates the value of a long segment using the learned values of its two shorter segments. Although the recursive structure reduces the number of sequential backups, errors in the shorter segments can still accumulate when their values are combined. In fact, the paper's theoretical analysis does not establish a better asymptotic bound on the total estimation error. More importantly, the method constructs these segments from recorded trajectories. This means that the number of steps between two states along the recorded trajectory is already known. Why not directly train the value function using these known returns, without bootstrapping? The paper includes a Monte Carlo baseline, but it does not compare direct trajectory-return learning and recursive bootstrapping while keeping the same additional value-propagation objective. Without this comparison, it is difficult to determine whether the improvement comes from recursive bootstrapping itself or simply from a better way of organizing training samples.

  2. The two value-learning objectives may conflict when demonstrations are suboptimal. DCRL trains a single value function using two objectives. The recursive objective tries to match the value of an observed route, while the propagation objective tries to learn the value of a shorter, potentially optimal route. These two targets are not always consistent. For example, a recorded route may take 20 steps to reach a goal, even though a different route could reach it in 10 steps. The recursive objective may push the predicted value toward the longer route, while the propagation objective tries to improve it toward the shorter one. This is also related to the quasimetric triangle inequality: the optimal value of reaching a goal directly should be at least as high as the value of going through an intermediate state, but the two values do not generally need to be equal.The paper acknowledges that the recursive objective learns observed routes rather than optimal ones. However, it does not clearly explain how the two objectives interact when they give different targets, or how this affects learning from highly suboptimal demonstrations.

Questions for authors
  1. Why use recursive bootstrapping instead of direct trajectory returns? Could the authors compare DCRL with a baseline that directly learns the known returns of observed trajectory segments, while keeping the same value-propagation objective, network, and training budget? This would help determine whether recursive bootstrapping is necessary or whether the improvement mainly comes from the training schedule.

  2. How do the two learning objectives interact on suboptimal trajectories? When a recorded route is longer than the optimal route, the recursive and propagation objectives may push the same value estimate in different directions. How significant is this conflict in practice? Would it be better to use the observed route as a lower bound on the optimal value rather than forcing the value to match that route?

  3. How much does DCRL depend on dataset coverage? The recursive objective only uses connections that appear within observed trajectories. Learning better routes therefore depends on the additional propagation objective. How does the method perform when the dataset contains poorly connected trajectories or when many state-goal pairs have little supporting data? An experiment with varying dataset coverage would help clarify this limitation.

9 comments

We thank the reviewer for the thoughtful review and the precise questions. We ran the experiments the reviewer suggested and have uploaded a revised PDF, to which all table and figure numbers below refer:

  • Direct trajectory returns with the same propagation objective (A1). Exact returns on all in-trajectory pairs stay far below DCRL for propagation horizon n≥25n\ge 25, and exact returns on all of DCRL's tree nodes fall behind as the propagation horizon shrinks. DCRL's gain therefore needs both the recursive organization of samples and bootstrapping each segment from its sub-segments.
  • Error accumulation (A2). Recursive bootstrapping accumulates error much more slowly than TD-n's chain. It lowers long-range value error, keeps its performance as the bootstrap chain gets longer (down to n=5n=5), and its error stays nearly flat with the horizon in a controlled environment where the true value is known. Under a fixed training budget, DCRL also admits a tighter error bound than TRL's uniform pair sampling at the same bootstrap depth (new Prop. 2).
  • Interaction of the two objectives on suboptimal data (A3). The two gradients are aligned in practice, and replacing our two losses with a single loss that treats the recorded route as a lower bound (an upper expectile in the divide-and-conquer loss) lowers the average success on standard OGBench from 68% to 45%. On a controlled suboptimality sweep, DCRL outperforms TD-n by 1.7–2.2$\times$ at every level.
  • Low dataset coverage (A4). On humanoidmaze-medium-stitch, whose trajectories only cover short pieces of the maze, DCRL performs best with the full and half datasets.
AuthorsOpenReview ↗

A1. Recursive bootstrapping vs. direct trajectory returns

Why not directly train the value function using these known returns, without bootstrapping? ... it does not compare direct trajectory-return learning and recursive bootstrapping while keeping the same additional value-propagation objective.

We ran this comparison on humanoidmaze-giant-1B (avg. 750k–1M, 4 seeds), keeping the propagation loss, network and training budget fixed and changing only which pairs the regression loss is trained on and its target:

  • MC returns, all in-trajectory pairs: the MC baseline (exact returns on in-trajectory pairs with jj uniform up to the episode end), with the same propagation loss added. Without propagation, this baseline reaches only 14% in our pipeline (the 79% previously in Table 1 was copied from the TRL paper (Park et al., 2026) and is now replaced by our reproduction).
  • Recursive value learning with MC returns on all tree nodes: exact returns on every node DCRL trains on (same sampler and schedule). Only the target differs from DCRL, so this isolates bootstrapping from the training schedule.
Target of the regression lossn=10n=10n=25n=25n=100n=100
MC returns, all in-trajectory pairs424258
Recursive value learning w/ MC returns (all tree nodes)147591
Recursive value learning w/ bootstrapping (DCRL)419093

Adding the propagation loss raises the MC baseline from 14 to 58 at n=100n=100, but it remains far below DCRL at n=25n=25 (42 vs. 90) and n=100n=100 (58 vs. 93). With the same samples and schedule, replacing the bootstrapped target with exact returns also lowers success (14 vs. 41 at n=10n=10, 75 vs. 90 at n=25n=25), while at n=100n=100 the two targets are on par (91 vs. 93). The improvement therefore does not come from organizing the samples alone. With the same recursive structure, bootstrapping is what makes short propagation horizons work. We have added this comparison to App. H.6 (Table 10).

In short, DCRL's gain needs both the recursive organization of samples and bootstrapping each segment from its sub-segments. At long propagation horizons, recursive organization alone lifts MC returns from 58 to 91, and at short horizons bootstrapping is what keeps DCRL strong.

AuthorsOpenReview ↗

A2. Error accumulation in recursive bootstrapping

Although the recursive structure reduces the number of sequential backups, errors in the shorter segments can still accumulate when their values are combined.

Empirically, combining segment values accumulates less error than TD-n's chain. On humanoidmaze-giant-1B, with the same propagation loss, adding the divide-and-conquer loss lowers the long-range value error relative to TD-n by 24–34% for n≤25n\le 25, including at the most distant goals (App. H.6).

Performance tells the same story. We compare methods with all expectiles set to 0.5, so that no update is optimistic and only error accumulation remains (avg. 750k–1M, 4 seeds):

Method (all expectiles 0.5)n=1n=1n=5n=5n=10n=10n=25n=25n=100n=100
TD-n09447374
TRL-n101219
DCRL878848989

Shortening the propagation horizon nn lengthens the chain of bootstrapped backups behind each long-range value. As nn shrinks and the bootstrap chain gets longer, TD-n drops from 74 to 9 and TRL-n from 19 to 0, while DCRL stays at 78–89% down to n=5n=5. DCRL's recursive combination of segment values therefore does not let errors build up as the chain lengthens (App. H.6, Table 9).

In fact, the paper's theoretical analysis does not establish a better asymptotic bound on the total estimation error.

The reviewer is correct that our original bound for DCRL has the same asymptotic order as TD-n's (App. A.2.1), so this static analysis does not establish a better rate. We have added a budget-aware analysis (Prop. 2, App. A.2.1), in which the local error depends on how often each segment length is trained. At the same bootstrap depth, DCRL's recursive sampling concentrates updates on the short segments that every long-range value depends on, and its error bound is smaller by a factor of Θ(H/n)\Theta(\sqrt{H/n}) than under uniform pair sampling, as in TRL.

The empirical results are consistent with this analysis. On the combination-lock environment, where the true value function is known, replacing DCRL's recursive sampling with uniform pair sampling while keeping the same backup sharply increases long-range error at large horizons (Fig. 11). DCRL's own error stays nearly flat as the horizon grows from 256 to 2,048, while TD-n's and TRL-n's errors grow rapidly (Fig. 9 right, App. A.2.2).

In short, under a fixed training budget DCRL's sampling provably tightens the bound relative to TRL's uniform pair sampling, and empirically its error grows far more slowly with the horizon.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.