- 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
-
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.
-
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.
-
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
-
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.
-
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
-
How does the aggregated arrival matrix in GRAFT-Online approximate the start-state-dependent, discount-weighted distribution defined in Equation (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
Q1: Aggregated arrival matrix approximation
The theory defines as dependent on the starting state , while the algorithm uses a single arrival matrix 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 is determined primarily by what the agent has achieved (inventory, unlocked capabilities) rather than by the spatial starting location. Once the policy for commanding 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 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:
| Environment | TRL (reproduced) | GRAFT-Offline | -value (paired t-test) |
|---|---|---|---|
| puzzle-4x5 | 0.012 | ||
| puzzle-4x6 | 0.018 | ||
| humanoidmaze-giant | 0.003 |
All three gains are statistically significant at . We add this table to the revision.
Algorithm 2 conditional structure: The cross-trajectory target is used with probability ; 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.
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.
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), the two states are identical in all task-relevant dimensions, so β(sj,sk)=Vˉ(sj,sk)≈1. The lower bound is exact in this case.
For maze tasks, the crossing key is the spatial cell of side length rκ. The cell size is chosen so that any two states within the same cell are reachable in at most bκ steps in an open maze. The bridge value γbκ is a conservative lower bound. The threshold β≥γbmax filters out crossings where the bridge is too long or blocked by obstacles.
We measured crossing statistics from the OGBench datasets (Table 4):
Puzzle tasks have high acceptance due to exact matching; maze tasks have lower acceptance due to obstacles. The threshold γbmax 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.