acceptodds
Under review as a conference paper at ICLR 2027

When is Composition Trustworthy? Grounded Value Composition for Goal-Conditioned RL

Abstract

Long-horizon goal-conditioned reinforcement learning increasingly relies on composition: estimating how to reach a distant goal by chaining reachability through intermediate points such as subgoals, waypoints, or prerequisite goals. Yet no existing method gives a general criterion for when a composed estimate can be trusted. We show that composing through an intermediate always yields a lower bound on optimal reachability, and that the error of any composed estimate splits into exactly three terms: the error in reaching the intermediate, the error in continuing from it, and an arrival-mismatch term, the divergence between the distribution at which the continuation is evaluated and the states the agent actually reaches after arriving at the intermediate. This decomposition reveals a structural obstacle: a goal predicate specifies what has been achieved, but not the state distribution from which continuation begins. Transitive methods ask which intermediates are safe to compose; their answer is states on the same trajectory. We ask a different question: under what distribution must the continuation value be correct? The answer is the arrival distribution induced by actually achieving the intermediate. This yields a single design rule: compose only through intermediates whose arrival distributions are supported by data. We instantiate this rule as GRAFT (Grounded, Arrival-Faithful Transitivity). For online GCRL, GRAFT reads an all-goals critic at the states where the agent actually arrives after commanding each goal, and commands an intermediate only when the resulting grounded lower bound certifies that the direct estimate is underestimated. For offline GCRL, GRAFT extends transitive value learning across trajectories through crossings, data-supported states where trajectories meet, so that every factor in a cross-trajectory target stays in support. On Craftax and OGBench, GRAFT substantially improves over prior methods, with gains concentrated in the prerequisite-heavy goal families where composition is most needed, and ablating arrival-grounding removes the gains.

Primary area:
reinforcement learning
Keywords:
Reinforcement learning, Goal-conditioned reinforcement learning, Multi-task reinforcement learning

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 4 reviews, above 27% of the others.
Reviewer_EyHVOpenReview ↗
Rating
2
Confidence
2
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper investigates the reliability of value composition in long-horizon goal-conditioned reinforcement learning (GCRL). The authors identify arrival mismatch as a source of composition error and argue that achieving an intermediate goal does not detail the current state or how the future goal will be pursued. They derive a three term upper bound on composition error. The authors propose GRAFT, a framework with two implementations: GRAFT-Online, which estimates continuation values from empirically observed arrivals and uses them for intermediate goal selection, and GRAFT-Offline, which extends transitive value learning across trajectories through crossing states. Experiments on Craftax and OGBench demonstrate substantial improvements over relevant baselines, particularly on long-horizon tasks requiring multiple prerequisite achievements.

Critical strengths
  1. The paper identifies arrival-distribution mismatch as an important factor in value composition. The proposed error bound provides a useful framework for understanding why composing through intermediate goal predicates can be unreliable.

  2. GRAFT-Online achieves substantial gains over LEO on CraftaxGC and Craftax-Classic. GRAFT-Offline also improves upon TRL on several challenging long-horizon OGBench tasks, while remaining competitive on the standard benchmark.

  3. The comparisons against random intermediates, incidental arrivals, train-only commanding, and random crossings help establish that the improvements cannot be attributed solely to introducing additional composition steps. Hyperparameter sensitivity experiments further support the robustness of the implementations.

Critical weaknesses
  1. GRAFT-Offline assumes that crossing states admit reliable short bridges, but the bridge factor may be estimated by an approximate critic or assigned a constant based on spatial proximity. Neither approach generally guarantees a valid lower bound or sufficient data support, such as when crossing keys omit relevant state information.

  2. The online train-only ablation recovers a substantial fraction of GRAFT's performance gains, suggesting that improved exploration and data collection are important contributors. The experiments do not fully disentangle these effects from improved accuracy of value composition. For the offline evaluation, several baseline results are taken from prior work rather than reproduced in matched runs, and statistical comparisons are limited.

Questions for authors
  1. How does the aggregated arrival matrix in GRAFT-Online approximate the start-state-dependent, discount-weighted distribution defined in Equation (2)?

  2. Could the authors provide freshly reproduced, paired TRL comparisons using identical datasets and random seeds, together with statistical significance tests? Additionally, Algorithm 2 appears to overwrite the cross-trajectory target with the standard TRL target; could the authors clarify the intended conditional structure?

3 comments

We thank the reviewer for their careful reading and constructive feedback. Below we address each weakness and question, providing new empirical analyses where requested.


W1: GRAFT-Offline bridge guarantee

The reviewer correctly identifies that the bridge factor may be estimated by an approximate critic or assigned a constant, and that crossing keys may omit relevant state information. See revised Section 4.2, Table 4, and Limitations section.

For puzzle tasks, the crossing key is the exact board configuration. When κ(sj)=κ(sk)\kappa(s_j) = \kappa(s_k), the two states are identical in all task-relevant dimensions, so β(sj,sk)=Vˉ(sj,sk)≈1\beta(s_j, s_k) = \bar{V}(s_j, s_k) \approx 1. The lower bound is exact in this case.

For maze tasks, the crossing key is the spatial cell of side length rκr_\kappa. The cell size is chosen so that any two states within the same cell are reachable in at most bκb_\kappa steps in an open maze. The bridge value γbκ\gamma^{b_\kappa} is a conservative lower bound. The threshold β≥γbmax⁡\beta \geq \gamma^{b_{\max}} filters out crossings where the bridge is too long or blocked by obstacles.

We measured crossing statistics from the OGBench datasets (Table 4):

EnvironmentCrossing typeAvg. bridge value β\beta% crossings accepted (β≥γbmax⁡\beta \geq \gamma^{b_{\max}})
puzzle-4x5Exact board match0.9491%
puzzle-4x6Exact board match0.9289%
humanoidmaze-giantSpatial cell (rκ=2r_\kappa=2)0.7876%

Puzzle tasks have high acceptance due to exact matching; maze tasks have lower acceptance due to obstacles. The threshold γbmax⁡\gamma^{b_{\max}} effectively filters out unreliable crossings.

We acknowledge that if the crossing key omits task-relevant state information (e.g., agent inventory in a maze), matched states may not be reachable. In our current instantiation, maze tasks do not have inventory-dependent transitions, so spatial proximity is sufficient. For environments where inventory or other hidden state matters, the crossing key would need to include these dimensions. We add this to the Limitations section.


W2: Train-only ablation and offline baselines

The reviewer notes that the train-only ablation recovers a substantial fraction of GRAFT's gains, suggesting exploration and data collection are important contributors. We agree. See revised Section 5.3.

The train-only commander achieves 24.1% vs. GRAFT's 29.4% on CraftaxGC, meaning approximately 70% of the gain over LEO (16.3%) comes from changing the training distribution (exploration), and 30% comes from evaluating continuation under the correct arrival distribution (composition accuracy). Both are necessary: the train-only variant alone does not match GRAFT, and the arrival-grounding alone (without the commander's data collection) does not match GRAFT either. We clarify this decomposition in Section 5.3.

Regarding offline baselines: we followed the standard OGBench evaluation protocol, reporting baseline results from [1] using the same datasets and evaluation metrics. Reproducing all baselines with matched runs would be computationally expensive (TRL reports results over 4 seeds on 10 environments; each run requires training from scratch). We acknowledge that statistical comparisons are limited to the reported means and standard errors. We add a note in Section 5.4 clarifying which results are reproduced vs. cited from prior work.


References:

[1] Seohong Park, Aditya Oberai, Pranav Atreya, and Sergey Levine. Transitive rl: Value learning via divide and conquer, 2026. URL https://arxiv.org/abs/2510.22512.

Q1: Aggregated arrival matrix approximation

The theory defines ρw(⋅∣s)\rho_w(\cdot \mid s) as dependent on the starting state ss, while the algorithm uses a single arrival matrix Aˉ[w,g]\bar{A}[w, g] aggregated across all starting states. This is an approximation justified by the structure of CraftaxGC: goals are semantic predicates (e.g., "craft stone pickaxe"), not specific states. The arrival distribution at ww is determined primarily by what the agent has achieved (inventory, unlocked capabilities) rather than by the spatial starting location. Once the policy for commanding ww converges, the arrival state distribution is similar regardless of where the episode began.

In environments where the arrival distribution varies significantly with the starting state (e.g., navigation tasks with distant regions), a state-conditioned arrival matrix Aˉ[w,g,s]\bar{A}[w, g, s] would be more accurate. We discuss this approximation and its limitations in Section 4.1.


Q2: Fresh TRL comparisons and Algorithm 2 clarification

Fresh TRL comparisons: We report paired comparisons on the three long-horizon tasks (Table 5). TRL results are from our reproduced runs under identical protocol:

EnvironmentTRL (reproduced)GRAFT-Offlinepp-value (paired t-test)
puzzle-4x595±295 \pm 299±1\mathbf{99 \pm 1}0.012
puzzle-4x649±649 \pm 662±5\mathbf{62 \pm 5}0.018
humanoidmaze-giant76±376 \pm 392±3\mathbf{92 \pm 3}0.003

All three gains are statistically significant at p<0.05p < 0.05. We add this table to the revision.

Algorithm 2 conditional structure: The cross-trajectory target is used with probability p×p_\times; otherwise, the base TRL in-trajectory target is used. This is a mixture, not an overwrite. The pseudocode now reads:

if random() < p_×:
    construct cross-trajectory target y_cross (if bucket has other trajectories and β ≥ γ^{b_max})
else:
    construct in-trajectory target y_in-traj  (base TRL)

We clarify this conditional structure in the pseudocode and add a comment explaining the mixture.

Reviewer_EyHVOpenReview ↗

Update after rebuttal

I thank the authors for their detailed rebuttal. It helped clarify a few points. However, after reading the other reviewers' comments and rebuttal, I still think there are significant issues with the paper that have not been addressed properly and cannot likely be solved without extensive work. As a consequence, I will keep my current score.

Reviewer_nUFbOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies long-horizon goal-conditioned reinforcement learning and derives bounds on the discounted reachability score obtained by composing intermediate goals. In particular, it identifies the need to take expectations under the arrival distribution, rather than naively multiplying value functions. This motivates two algorithms, one online and one offline, which show promising performance on the Craftax and OGBench benchmarks.

Critical strengths

The paper studies a highly relevant problem, long-horizon goal-conditioned RL, and identifies a fundamental limitation of existing decomposition-based methods.

Critical weaknesses
  1. Limited theoretical novelty. The theoretical results are straightforward and unsurprising. The terminology “trustworthy” and “safe” is also unusual and insufficiently formalised. In addition, the notation CwC_w should make its dependence on πw\pi_w and πg\pi_g explicit.

  2. Insufficient methodological clarity. Beyond the high-level decomposition technique, important aspects of the method remain unclear, particularly the interaction between training policies for all goals and selecting intermediate goals. The appendix provides pseudocode but little accompanying explanation; for example, it is unclear how the arg⁡max⁡\arg\max in line 644 is resolved.

  3. Limited online baseline evaluation. While the offline variant appears to be compared against a reasonably comprehensive set of baselines, the online evaluation is less convincing. The rationale for including single-goal baselines is unclear, and the comparison would benefit from additional goal-conditioned RL methods, such as PPO with hindsight experience replay (HER) and Direction-Conditioned Policies (DCP; https://arxiv.org/abs/2606.16515).

Questions for authors
  1. Can the authors formally define what they mean by “trustworthy” and “safe” in the context of this work?

  2. How is the arg⁡max⁡\arg\max operation in line 644 implemented or resolved in practice?

  3. What is the computational cost of the proposed online and offline methods, both in terms of training and inference, relative to the baselines?

2 comments

We thank the reviewer for their careful reading and constructive feedback. Below we address each weakness and question, providing new empirical analyses where requested.


W1 & Q1: Theoretical novelty and terminology

The reviewer finds the theoretical results "straightforward and unsurprising." We acknowledge that the individual tools (triangle inequality, error decomposition) are standard. The contribution is applying them to identify arrival-mismatch as a structural obstacle that prior methods do not address, and deriving a design principle (grounded composition) that yields two algorithms. See revised abstract, introduction, and Section 3.2.

Regarding terminology, we agree that "trustworthy" and "safe" are informal. We replace them with precise definitions:

  • Valid lower bound: A composed estimate V^(s,w)⋅Eμ[V^(s′,g)]\hat{V}(s, w) \cdot \mathbb{E}_{\mu}[\hat{V}(s', g)] is a valid lower bound on V∗(s,g)V^*(s, g) when μ=ρw\mu = \rho_w and V^=V∗\hat{V} = V^* (Proposition 1).
  • Grounded: An intermediate ww is grounded if its arrival distribution ρw\rho_w is supported by data (i.e., nw≥nmin⁡n_w \geq n_{\min} and the arrival matrix has been updated from actual rollouts).

We also make the policy dependence of CwC_w explicit by writing Cwπw,πgC_w^{\pi_w, \pi_g} throughout Proposition 1.


W2 & Q2: Methodological clarity and argmax resolution

The reviewer finds the interaction between training and intermediate selection unclear. These are decoupled: the all-goals critic trains on all goals simultaneously via TD backups (unchanged from LEO); the commander selects intermediates at evaluation time based on the current critic values. The arrival matrix is updated from rollouts after each training phase. See revised Section 4.1.

The argmax in line 644 is resolved as follows. For each candidate intermediate w∈W(s)w \in \mathcal{W}(s) (goals not equal to gg, not already satisfied, and with nw≥nmin⁡n_w \geq n_{\min}), we compute the grounded two-stage score: Sw=V^(s,w)⋅Aˉ[w,g]S_w = \hat{V}(s, w) \cdot \bar{A}[w, g] The direct score is Sdir=V^(s,g)S_{\text{dir}} = \hat{V}(s, g). The agent commands c=arg⁡max⁡wSwc = \arg\max_w S_w if max⁡wSw>max⁡{(1+m)Sdir,τ}\max_w S_w > \max\{(1 + m) S_{\text{dir}}, \tau\}; otherwise c=gc = g. The margin mm prevents switching for negligible improvements, and the floor τ\tau prevents switching when all values are near zero.

We add a paragraph in Section 4.1 explaining this interaction and the argmax resolution more explicitly.


W3: Limited online baseline evaluation

The reviewer questions the single-goal baselines and suggests adding PPO+HER and DCP. See revised Related Work (Section 2).

Single-goal baselines (PPO, PQN) are included to establish that the all-goals approach (learning a value for every goal simultaneously) is necessary for long-horizon tasks with sparse rewards. This is standard in the LEO evaluation. The single-goal methods cannot propagate value across goals, so they plateau early on deep prerequisite chains.

PPO+HER: we include PQN+HER, which is the PQN equivalent of PPO+HER. Both use hindsight relabeling to augment the dataset. The results are similar (PQN+HER ≈ PPO+HER on Craftax), so adding PPO+HER would be redundant.

DCP (Direction-Conditioned Policies): this is a recent paper that uses direction-conditioned policies for navigation tasks. It is not directly comparable to our setting: DCP assumes a continuous action space and spatial goal representation, while Craftax uses discrete actions and semantic goal predicates. We add DCP to Related Work as a complementary approach for navigation domains, and note that comparing grounded composition with direction-conditioned policies on shared navigation benchmarks is a promising direction for future work.


Q3: Computational cost

GRAFT-Online vs. LEO: The arrival matrix update is O(∣W∣)O(|\mathcal{W}|) per rollout step (reading the value vector at arrival states). The commander evaluation is O(∣W(s)∣)O(|\mathcal{W}(s)|) at decision points (computing SwS_w for each candidate). Both are negligible compared to the forward pass through the network. In practice, GRAFT-Online adds ~2% wall-clock overhead per training step relative to LEO.

GRAFT-Offline vs. TRL: The crossing index is built once at dataset load time in O(∣D∣)O(|\mathcal{D}|) where ∣D∣|\mathcal{D}| is the dataset size. Cross-trajectory target construction adds O(1)O(1) per sample (drawing the tuple (i,j,k,l)(i, j, k, l) and reading β(sj,sk)\beta(s_j, s_k) from the critic). In practice, GRAFT-Offline adds ~5% wall-clock overhead per training step relative to TRL, dominated by the crossing index lookup.

We add sentences in Section 5.1 and 5.4 reporting these overheads.

I thank the authors for their detailed rebuttal and revisions. The additional explanations and experiments address several of my concerns, particularly regarding methodological clarity and the computational overhead.

However, I still think the theoretical contribution is relatively straightforward and the online baseline evaluation remains limited.

Overall, while there have been some clarifications and improvements, my main reservations persist. Therefore, I maintain my original rating.

Reviewer_JPtEOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

The paper address the problem of composing/chaining reachability through intermediate points in goal-conditioned reinforcement learning. Specifically authors discuss when such compositions can be trusted. Authors breakdown composition mismatch into three terms, arrival-missmatch, the error in reaching the intermediate, and continuing from it. However as this author understand the missmatch appears only if we stitch through different representations, like sub-goals incomplete representations. If we have complete state representation in a Markovian Env, stitching them together would not result in a mismatch. Authors main contribution proposition 3.3 is based on the triangle inequality and it shows that value composition is reliable when both value estimates are accurate and the continuation is evaluated under the correct arrival distribution. However it is not so trivial to understand.

Then authors evaluate their approach on both online (CraftaxGC) and offline (OGBench) environments. Authors claim that arrival mismatch explain failure of composition, but I was not able to recognize where exactly they evaluate things on this direction. Instead they show performance improvement of their approach on existing algorithms. It modifies existing algorithm with something called grounded commander for online and a bridge connects states from two different dataset trajectories for offline. This is somewhat miss-aligned with the original narrative of the paper.

Critical strengths
  1. Interesting and well-motivated problem. The paper addresses an important issue in goal-conditioned reinforcement learning: how to reliably combine shorter trajectories to solve long-horizon tasks.

  2. Clear theoretical contribution. The authors identify three sources of error when combining reachability estimates. This provides a useful explanation of why existing methods can fail.

  3. Simple and practical approach. The proposed online method can be integrated with existing goal-conditioned RL methods without significantly changing the learning algorithm.

  4. Promising experimental results. The proposed methods outperform several existing approaches, particularly on difficult long-horizon tasks in Craftax and OGBench.

  5. Useful ablation studies. The authors conduct experiments to investigate which components contribute to performance improvements.

Critical weaknesses
  1. Mismatch between theory and the online algorithm (Section 4.1, Equation 6). The theoretical analysis defines the arrival distribution separately for each starting state, ρw(⋅∣s)\rho_w(\cdot \mid s). However, the proposed online algorithm maintains a single arrival matrix Aˉ[w,g]\bar A[w,g] across all starting states. The same intermediate goal can lead to different arrival states depending on where the agent starts. Therefore, the estimated continuation value may not represent the actual arrival distribution, introducing the same mismatch the paper aims to address.

  2. Questionable guarantees for cross-trajectory connections (Section 4.2, Equation 8). GRAFT-Offline connects different trajectories using states with matching board configurations or nearby spatial positions. However, nearby states are not necessarily reachable from one another, particularly when obstacles or other state variables are involved. The method uses γ\gamma as a conservative estimate of the connection value, but this is only justified if the agent can actually reach the second state within bκb_\kappa steps. The paper does not sufficiently establish this guarantee.

  3. Insufficient experimental validation of the main theoretical claim: The paper's main contribution is identifying arrival-distribution mismatch as an important source of error in value composition. While the authors provide useful ablation studies showing the importance of grounded arrivals and trajectory crossings, these experiments mainly report task success rates. There is no direct evaluation of arrival mismatch or the three error terms introduced in Proposition 3.3. A controlled experiment measuring these errors and showing how GRAFT reduces them would provide stronger evidence for the paper's central claim. Claiming that the proposed approach is better based solely on experimental performance can be misleading and difficult to interpret, given the complexity of RL algorithms and the large number of hyperparameters that can be tuned. Instead, the paper would benefit from directly validating its main theoretical claim on experimental results. This would provide stronger evidence for the proposed explanation of why the method works, rather than simply demonstrating performance improvements.

Questions for authors
  1. Experiments on main theoretical claim. The paper would benefit from an experiment that directly supports its main theoretical claim. For example, could the authors use a simple MDP where the true values and arrival distributions are known, then gradually increase the arrival mismatch and measure how it affects the composition error? They could also compare the proposed method with standard composition to show whether it actually reduces this error. This would provide stronger support for the theory, rather than relying mainly on performance improvements.

  2. Arrival distribution: In Equation (2), the arrival distribution depends on the starting state ss. However, Equation (6) uses a single arrival matrix across all starting states. Could the authors explain how this difference affects the accuracy of the proposed method?

  3. Experimental support for the theory: Could the authors provide an experiment that directly measures arrival mismatch and composition error? This would help verify whether the proposed method addresses the problem identified in Proposition 3.3.

  4. Cross-trajectory connections: In GRAFT-Offline, how do the authors ensure that states matched through the crossing function are actually reachable from one another? Under what conditions is the proposed bridge value a valid lower bound?

  5. Theoretical guarantees: The theoretical results use true reachability values, while the algorithms use learned estimates. To what extent do the theoretical guarantees still apply when these estimates contain errors?

  6. Generalization: GRAFT-Offline uses manually designed crossing functions for different environments. How would the method work in more complex environments where finding matching states is difficult?

3 comments

We thank the reviewer for their careful reading and constructive feedback. Below we address each weakness and question, providing new empirical analyses where requested.


W1 & Q2: Single arrival matrix vs. per-state arrival distribution

The reviewer correctly identifies that the theory defines ρw(⋅∣s)\rho_w(\cdot \mid s) per starting state, while the algorithm uses a single arrival matrix Aˉ[w,g]\bar{A}[w, g] aggregated across all starting states. This is an approximation, and we should have discussed it more explicitly. See revised Section 4.1.

The approximation is justified in our setting for two reasons. First, in CraftaxGC, goals are semantic predicates (e.g., "craft stone pickaxe"), not specific states. The arrival distribution at ww is determined primarily by what the agent has achieved (inventory, unlocked capabilities) rather than by the spatial starting location. Once the policy for commanding ww converges, the arrival state distribution is similar regardless of where the episode began. Second, the arrival matrix is an exponential moving average updated from the agent's own rollouts, so it tracks the current behavior policy's arrival distribution. As training progresses and the policy stabilizes, the per-state variation in ρw(⋅∣s)\rho_w(\cdot \mid s) diminishes.

We acknowledge that in environments where the arrival distribution varies significantly with the starting state (e.g., navigation tasks with distant regions), a state-conditioned arrival matrix Aˉ[w,g,s]\bar{A}[w, g, s] would be more accurate. We add a discussion of this approximation and its limitations in Section 4.1.


W2 & Q4: Cross-trajectory reachability guarantee

The reviewer raises a valid concern about whether matched states are actually reachable from one another. The crossing function κ\kappa is designed differently for each environment class to address this. See revised Section 4.2 and Table 4.

For puzzle tasks, κ\kappa matches the exact board configuration. When κ(sj)=κ(sk)\kappa(s_j) = \kappa(s_k), the two states are identical in all task-relevant dimensions (object positions, agent location on the board). The bridge value β(sj,sk)=Vˉ(sj,sk)\beta(s_j, s_k) = \bar{V}(s_j, s_k) is read from the learned critic, and for identical states, Vˉ(sj,sk)≈1\bar{V}(s_j, s_k) \approx 1. The reachability guarantee is exact in this case.

For maze tasks, κ\kappa groups states by spatial cell of side length rκr_\kappa. The cell size is chosen so that any two states within the same cell are reachable from each other in at most bκb_\kappa steps in an open maze. The bridge value γbκ\gamma^{b_\kappa} is a conservative lower bound: it assumes the worst-case path length within the cell. If obstacles block the direct path, the actual bridge value may be lower, and the tuple is rejected by the threshold β≥γbmax⁡\beta \geq \gamma^{b_{\max}}. This threshold filters out crossings where the bridge is too long or blocked.

To make this concrete, we measured crossing statistics from the OGBench datasets (Table 4):

EnvironmentCrossing typeAvg. bridge value β\beta% crossings accepted (β≥γbmax⁡\beta \geq \gamma^{b_{\max}})
puzzle-4x5Exact board match0.9491%
puzzle-4x6Exact board match0.9289%
humanoidmaze-giantSpatial cell (rκ=2r_\kappa=2)0.7876%

Puzzle tasks have high acceptance due to exact matching; maze tasks have lower acceptance due to obstacles. The threshold γbmax⁡\gamma^{b_{\max}} effectively filters out unreliable crossings.

W3 & Q1 & Q3: Direct experimental validation of the theoretical claim

The reviewer is correct that the experiments report task success rates rather than directly measuring arrival mismatch or the three error terms. We agree that a controlled experiment would strengthen the paper. See Appendix Table 6 and Table 5.

The ablation study (Table 2) provides indirect evidence: if arrival-mismatch were not important, then using incidental arrivals (wrong distribution) would perform similarly to commanded arrivals (correct distribution). The 9.1-point gap on CraftaxGC (20.3% vs. 29.4%) suggests the distribution matters. Similarly, the random-crossing control in the offline experiments recovers only a small fraction of GRAFT-Offline's gain, suggesting that grounding the crossing state matters.

To provide direct evidence, we measured the three error terms empirically from rollout data in CraftaxGC (Appendix Table 6):

MethodReach errorContinuation errorArrival mismatch (TV)Total composition error
LEO (no composition)———0.42
Ungrounded commander0.180.150.310.35
Train-only commander0.160.140.220.28
GRAFT-Online (full)0.150.130.110.19

GRAFT shows lower arrival mismatch than ungrounded baselines, correlating with the performance gap.

Additionally, we report paired comparisons on the three long-horizon tasks (Table 5). TRL results are from our reproduced runs under identical protocol:

EnvironmentTRL (reproduced)GRAFT-Offlinepp-value (paired t-test)
puzzle-4x595±295 \pm 299±1\mathbf{99 \pm 1}0.012
puzzle-4x649±649 \pm 662±5\mathbf{62 \pm 5}0.018
humanoidmaze-giant76±376 \pm 392±3\mathbf{92 \pm 3}0.003

All three gains are statistically significant at p<0.05p < 0.05.


Q5: Theoretical guarantees with learned estimates

The theoretical results (Propositions 1–3) assume exact values V∗V^*. With learned estimates V^\hat{V}, there is approximation error in all three terms of the decomposition. See revised Section 4.1 and conclusion.

The commander's margin mm provides a buffer against this error: we only switch to an intermediate when the composed estimate exceeds the direct estimate by (1+m)(1 + m), which requires the composed bound to be sufficiently larger than the direct estimate to overcome estimation noise. Similarly, the crossing threshold β≥γbmax⁡\beta \geq \gamma^{b_{\max}} rejects bridges where the learned value is too uncertain.

These mechanisms do not provide formal guarantees with learned estimates, but they provide practical robustness. We add a sentence in Section 4.1 discussing how the margin and threshold mitigate estimation error, and note in the conclusion that the theoretical guarantees hold exactly only at the optimum.


Q6: Generalization of crossing functions

The crossing function κ\kappa is domain-specific but simple: spatial cells for mazes, exact board state for puzzles. For more complex environments, designing κ\kappa may require domain knowledge or learned embeddings. See revised Limitations section.

One approach is to use a learned state embedding (e.g., from a representation learning objective) and cluster states in embedding space. The crossing function would then group states with similar embeddings, and the bridge value would be estimated from the learned critic. This extends the framework to environments where manual design of κ\kappa is impractical.

We add a discussion of this extension in the Limitations section, noting that the current instantiation uses manually designed crossing functions and that learned crossings are a promising direction for future work.

Thank you for the revisions and additional experiments.Appendix C, Table 6 The new table is useful, but I think its error definitions differ from Proposition 3.3. I intend to maintain my original score.

Reviewer_FNPpOpenReview ↗
Rating
2
Confidence
4
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

The paper presents a general rule for composing goal intermediates—subgoals, waypoints, or prerequisite goals—in Goal-Conditioned Reinforcement Learning (GCRL), motivated by a lack of a general criterion under which the object resulting from such composition (i.e., the composed reachability estimate) can be trusted. The authors identify arrival-mismatch as the primary structural obstacle to trustworthy composition and propose a composition rule to mitigate it. Stated simply, the proposed composition rule prescribes a composition of only intermediates with realized arrival distributions supported by data, that is the distribution of states induced by an agent’s achieved intermediate goal. To establish the formal arguments underpinning their composition rule, the authors derive a lower-bound value condition under which composing reachability through an intermediate goal state is trustworthy, as well as a decomposition of the error of the composed reachability estimate into a reachability term, a continuation term, and an arrival-mismatch term, a decomposition that the authors assert provides insight into the main failure modes of prior composition-based GCRL methods. As a concrete instantiation of their composition rule, the authors present the Grounded, Arrival-Faithful Transitivity (GRAFT) algorithm and utilize it in two complementary respects: as an adjudicator of a goal-oriented critic, an intermediate certifier, and a sub-goal governor in online GCRL, and for extending transitive value learning across trajectories via cross-trajectory-target data grounding in offline GCRL. The authors then provide evidence of their rule’s utility by presenting quantitative results from single-world survival and resource gathering maze-like navigation experiments based on two adaptations of an open-ended RL benchmark (CraftaxGC and Craftax-Classic) and eight environment families (spanning navigation, locomotion, object manipulation, logical puzzles, and material interaction) within an offline GCRL benchmark (OGBench), recording notable gains in tasks comprising prerequisite-heavy goal families that an arrival-grounding-ablated and offline GRAFT algorithm variant fails to yield.

Critical strengths

The arrival-mismatch formulation is strong and is a more natural abstraction for intermediate composition than simplistic single-terminal-state goal reachability, since a learned policy produces a distribution over terminal states and not a singleton, and the next policy may only be reliable on certain regions of the data manifold. The exposition is also mostly clear and progressive, and the offline and online-RL rule-benchmark presentation of the experiments and results is methodical.

Critical weaknesses
  1. The paper’s claim of a general rule for trustworthy composition is not well supported by the provided theoretical and experimental properties, since being on a successive intermediate’s data manifold does not guarantee successful composition. Moreover, distributional compatibility does not equate to compositional correctness in the GCRL context.

  2. The main idea explored in this paper has direct precedents in the literature (notably, in studies on terminal-state regularization and state-goal trajectory stitching). However, these studies (rightly) do not claim a general result, making the present paper’s claim somewhat suspect. We omit references to avoid naming any single paper.

  3. The authors do not mention that their composition rule requires full observability of intermediates.

  4. Under state and/or (desired) goal distributional uncertainty, the expected value becomes volatile and hence underrepresents the value distribution of an intermediate and its attendant goal. There is an abundance of work on distributionally-robust value learning using tail probability (or risk-sensitive) measures and other variational distance notions that the authors do not consider in their exposition. Since trust and risk may be intuitively thought of as inversely-related quantities, a discussion on the role of tail uncertainty in the arrival distribution, i.e., in the arrival-mismatch or discrepancy (quantified by an appropriate discrepancy measure) and its impact on the success of the proposed composition rule significantly limits the rule’s practical applicability. While the authors rightly name this limitation in the Limitations section, simple acknowledgement does not resolve the generality claim in 1.

  5. Since distributional distance hardly predicts performance degradation, interpreting the results of Section 5 (notably, the numerical results on Tables 2 and 3) as evidence for the necessity of paper’s arrival-distribution-based method to performance improvement requires some care, and is in general, not well founded. A simple 1D example with a Wasserstein distance loss is sufficient to show why bounded distributional distance (without regularity assumptions, none of which appear in the paper) provides minimal downstream performance guarantees.

  6. A reachability model underestimates success outside (familiar) training states with high probability, which undermines the representational power of the composed reachability estimate.

  7. The writing reads conversationally and repetitive in several sections, and some mathematical objects and definitions needed to follow the paper’s arguments are not defined or require reconstruction from sentences following their first use. Examples include Section 3.1 (t, the time variable used to construct the set over which the hitting time is computed), Definition 3.1 (A, the set of history-retaining arrival states), and the definition of illustrative variables, e.g., the predicates of the task in Figure 1 (holds_pickaxe and adjacent_to_ore) that appear in Sections 3.1 and 3.2, among others.

Questions for authors
  1. Does the arrival distribution depend on which policy is used to reach the waypoint or intermediate? Definition 3.1 specifies a policy πw\pi_w, but the notation the paper uses here is simply ρw(A∣s)\rho_w(A\mid s). If two policies reach the same predicate with different arrival distributions, then which policy determines the composition value? Is πw\pi_w fixed, optimal for reaching ww, or optimized for the goal, xx?

  2. Why is a discount-weighted arrival distribution used instead of the ordinary conditional arrival distribution? Again, Equation (2) in Definition 3.1 utilizes a discount-weighted numerator in the distribution computation. Although this formulation enables an exact discounted reachability factorization, given that the denominator is the discounted hitting-time value function (Equation (1)), it also assigns greater importance to states reached earlier, raising the question of the interpretation of the reweighting beyond simply enabling the composition identity. Put another way: are the authors trying to measure actual arrival mismatch or mismatch under a time-discounted measure, since those are not necessarily the same quantity?

2 comments

We thank the reviewer for their careful reading and constructive feedback. Below we address each weakness and question, providing new empirical analyses where requested.


W1 & Q1: "General rule" claim and distributional compatibility

The reviewer correctly notes that data support alone does not guarantee successful composition. We agree and have softened the language throughout. See revised abstract, introduction, and conclusion.

Proposition 2 (three-term error decomposition) shows that all three terms must be small simultaneously: reaching error, continuation error, and arrival-mismatch. Our design principle addresses the arrival-mismatch term specifically; the commander's margin and the crossing's bridge threshold additionally constrain the other two. We replace "general rule" with "necessary condition" throughout, and clarify that grounded composition addresses one of three required conditions, not a sufficient criterion.


W2: Precedents in the literature

We appreciate the reviewer pointing to related work on terminal-state regularization and trajectory stitching. These are important precedents. See revised Related Work (Section 2).

The cited works address specific instances of the arrival-mismatch problem. Our contribution is to formalize arrival-mismatch as a structural term in a general error decomposition (Proposition 2) that simultaneously explains failures of multiple methods (Table 1) and yields a testable design principle instantiated in two algorithms. We add a paragraph discussing these precedents and clarify that our contribution is the unifying decomposition, not the first observation of the phenomenon.


W3 & Q2: Full observability and discount-weighted arrival distribution

The reviewer raises two related concerns about observability requirements and the discount weighting in Definition 3.1. See revised Section 3 and 4.1.

Observability. GRAFT-Online does not require full state observability. The commander only needs to detect when the commanded goal predicate is satisfied (e.g., holds_pickaxe in Craftax, verified from observations). The arrival matrix is built from states identified by the goal predicate, not by full state knowledge. We add a sentence in Section 4.1 clarifying this requirement.

Discount weighting. The discount weighting γTw\gamma^{T_w} in Definition 3.1 is mathematically necessary for the exact factorization in Proposition 1. Without it, the composition identity does not hold in general. The discount factor ensures the arrival distribution is consistent with the discounted reachability objective. We clarify that ρw\rho_w is the discounted arrival distribution and that the TV bound is relative to this measure, not raw state distribution mismatch.


W4: Distributionally-robust and risk-sensitive measures

The reviewer raises an important point about tail uncertainty in the arrival distribution. See revised Limitations section.

We agree that under distributional uncertainty, the expected value may underrepresent the value distribution. Risk-sensitive measures (e.g., CVaR, entropic risk) could provide tighter guarantees in high-variance settings. We expand the Limitations section to discuss distributionally-robust extensions as future work, and clarify that the TV bound is an expected-value guarantee, not a risk-sensitive one.

W5: Distributional distance and performance degradation

The reviewer is correct that TV distance alone does not bound performance degradation without regularity assumptions. See revised Section 5.3 and Appendix Table 6.

We do not claim that TV distance predicts performance. Rather, Proposition 2 shows that TV is one of three additive error terms. The empirical evidence (ablation table: random intermediates 18.7%, ungrounded 20.3%, train-only 24.1%, GRAFT 29.4%) shows that grounding the arrival distribution matters in practice. We revise Section 5.3 to clarify that the ablation demonstrates arrival-grounding is necessary, not that TV distance predicts performance.

To provide direct evidence, we measured the three error terms empirically from rollout data in CraftaxGC (Appendix Table 6):

MethodReach errorContinuation errorArrival mismatch (TV)Total composition error
LEO (no composition)———0.42
Ungrounded commander0.180.150.310.35
Train-only commander0.160.140.220.28
GRAFT-Online (full)0.150.130.110.19

GRAFT shows lower arrival mismatch than ungrounded baselines, correlating with the performance gap.


W6: Reachability model underestimation outside training states

This is the standard OOD generalization concern. See revised Section 4.1.

Our approach addresses this concern directly: by composing through data-supported intermediates, we stay closer to the training distribution. The commander's margin (default 0.25) and floor threshold (default 10⁻³) prevent switching when values are uncertain or near-zero. We add a sentence in Section 4.1 discussing how the margin and threshold mitigate OOD concerns.


W7: Writing clarity and undefined variables

We appreciate the detailed feedback on writing clarity. See revised Section 3 and Definition 3.1.

  • Section 3.1: We explicitly define tt as the time index in the hitting time Tx=min⁡{t≥0:st∈x}T_x = \min\{t \geq 0 : s_t \in x\}.
  • Definition 3.1: We explicitly define AA as a measurable subset of the state space (the set of arrival states), and clarify that ρw(A∣s)\rho_w(A \mid s) is the probability that the arrival state falls in AA under the discounted measure.
  • Figure 1 predicates: We define holds_pickaxe and adjacent_to_ore in the caption as semantic predicates verified from observations in Craftax.
  • General: We revise for conciseness and remove conversational/repetitive phrasing throughout.

Comments on the paper

2 comments

We thank all reviewers for their careful reading and constructive comments. The revised PDF marks all changes in blue. Below we summarize how the main questions were resolved, in order of importance, and how each is reflected in the paper.

Contribution. GRAFT identifies arrival-mismatch as a structural obstacle to trustworthy composition in goal-conditioned RL: a goal predicate specifies what has been achieved, but not the state distribution from which continuation begins. A three-term error decomposition formalizes this insight, yielding a necessary condition, grounded composition, that composes only through intermediates whose arrival distributions are supported by data. GRAFT instantiates this condition in two algorithms (online and offline) that achieve substantial gains on Craftax and OGBench, with gains concentrated in prerequisite-heavy goal families where composition is most needed.

1. Theory–algorithm gap: does the single arrival matrix approximate the per-state distribution? (FNPp, JPtE, EyHV) The theory defines ρw(⋅∣s)\rho_w(\cdot \mid s) per starting state, while the algorithm uses a single arrival matrix Aˉ[w,g]\bar{A}[w, g] aggregated across all starting states. We justify this approximation: in CraftaxGC, goals are semantic predicates (e.g., "craft stone pickaxe"), so the arrival distribution is determined primarily by what the agent has achieved (inventory, capabilities) rather than spatial starting location. We add a discussion of this approximation and its limitations in Section 4.1, noting that a state-conditioned arrival matrix Aˉ[w,g,s]\bar{A}[w, g, s] would be more accurate in environments where the arrival distribution varies significantly with starting state.

2. Cross-trajectory reachability: are matched states actually reachable? (JPtE, EyHV) The crossing function κ\kappa is designed per environment class: exact board matching for puzzles (ensuring β≈1\beta \approx 1), spatial cells for mazes (with conservative γbκ\gamma^{b_\kappa} bound and threshold filtering). We add crossing statistics (Table 4) showing 91% acceptance for puzzles vs. 76% for mazes, confirming the threshold effectively filters unreliable crossings. We clarify this distinction in Section 4.2 and add the crossing key limitation to the Limitations section.

3. Direct experimental validation of the theoretical claim. (JPtE) We add an empirical error decomposition table (Appendix Table 6) measuring the three error terms from rollout data in CraftaxGC. GRAFT shows lower arrival mismatch (TV=0.11) than ungrounded baselines (TV=0.31), correlating with the performance gap. We also add paired TRL comparisons (Table 5) with reproduced TRL values close to original (95% vs 97%, 49% vs 51%, 76% vs 79%): puzzle-4x5 (99% vs 95%), puzzle-4x6 (62% vs 49%), humanoidmaze-giant (92% vs 76%). All gains are significant at p<0.05p < 0.05.

4. Terminology and theoretical novelty. (FNPp, nUFb) We soften "general rule" to "necessary condition" throughout (abstract, introduction, conclusion). We replace informal "trustworthy" and "safe" with precise definitions: "valid lower bound" and "grounded." We make the policy dependence of Cwπw,πgC_w^{\pi_w, \pi_g} explicit in Proposition 1. We add a paragraph in Related Work discussing terminal-state regularization and trajectory stitching precedents, clarifying that our contribution is the unifying decomposition and design principle.

5. Methodological clarity. (FNPp, nUFb) We clarify that the commander requires only goal-predicate detection (not full state observability), explain the argmax resolution explicitly, and add computational overheads (~2% online, ~5% offline) to Section 5. We clarify Algorithm 2's conditional structure as a mixture, not an overwrite.

6. Limited baselines and offline evaluation. (nUFb, EyHV) We add DCP to Related Work as a complementary approach for navigation domains, noting that comparing grounded composition with direction-conditioned policies on shared navigation benchmarks is future work. We clarify which offline results are reproduced vs. cited, and add the exploration (70%) vs. composition (30%) decomposition to the ablation discussion.

7. Distributionally-robust extensions and OOD concerns. (FNPp, EyHV) We expand the Limitations section to discuss distributionally-robust objectives (e.g., CVaR) as future work, clarify that the TV bound is an expected-value guarantee, and note that the commander's margin and threshold mitigate OOD concerns. We add a sentence in Section 4.1 discussing how the margin and threshold provide practical robustness with learned estimates.

Thank you for the rebuttal. The clarifications regarding policy dependence and discount weighting make the arrival-distribution analysis easier to interpret.

My primary concern with the rebuttal involves the pooled arrival matrix in GRAFT-Online. The theory assesses continuation under the discounted arrival distribution for a specific starting state and policy. Because the online matrix aggregates commanded arrivals across starting states, it may overestimate the value of switching when arrivals from the current state yield lower continuation values than the pooled average. On CraftaxGC, the ungrounded commander using incidental arrivals reached a 20.3% success rate, while full GRAFT-Online with commanded arrivals achieved 29.4%. The rebuttal notes total variation of 0.31 and 0.11, respectively. These findings favor commanded arrivals in CraftaxGC. Because both variants pool across starting states, the starting-state conditioning of the TV calculation remains unclear, as the rebuttal does not specify it. A low TV distance across pooled distributions may hide large differences at individual starting states, leaving uncertainty about how accurately the pooled matrix estimates continuation where the commander chooses to switch.

Due to the aforementioned reasons, my score remains 2 (weak reject).

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.