- Rating
- 1
- Confidence
- 2
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper propose GraphHCA, a model-free hindsight credit assignment method. GraphHCA combines step-level hindsight signal with the trajectory-level advantage, eliminating the explicit hindsight-distribution estimation. GraphHCA achieves best results on ALFWorld, WebShop, and Sokoban.
Critical strengths
-
The motivation of this paper is clear. The method that combines rollout, constructing state transition and calculate step-level advantage is potentially useful.
-
The experiments of this paper cover multiple domains and involves a variety of models, which I think is complete.
Critical weaknesses
-
The presentation of this paper is loose, many parts in this paper are verbose and not informative. For example, authors can merge Figure 1 and 2 to make it more concise; Also, related work and preliminary work repeatedly compare the same set of credit assignment methods. In addition, there are many sentences describing the same thing throughout this article. The authors should consider increasing the information density of the paper to improve its presentation.
-
The theoretical contribution of this paper is thin, and many propositions are trivial. While I understand some propositions are included to demonstrate the favorable properties of their design methods, I prefer not to bring in too many relatively trivial "propositions". For example, Proposition 4.2 is just a standard contraction result for a discounted Bellman operator. I suggest the author remove these propositions and use simple illustrations to describe these properties.
-
The improvements shown by GraphHCA on GraphGPO and GiGPO are minor. I'm not sure whether this is a statistically significant improvement, especially considering LLM post-training involves very high variance and results are just averaged with few seeds. Also, the performance trend of each method is identical across all tasks. Though likely possible, I recommend the authors to discuss more about why such consistency is general rather than simply listing the performance numerics. I am not suggesting the author to add experiments on new domains, but I think it would be helpful that they could also include some discussion on when this method can be no longer effective.
Questions for authors
- I'm wondering why not having RLOO, PPO RL and the prompting baselines just like Figure 1 (e.g., react) in Figure 2 to keep them consistent?
- How are the all success rates in Tables 4 and 5 are computed? Why does Table 5 report 93.3% overall success for the 0.75 discount when the results in Table 4 and 5 imply at least 94.2% under the same subtask weights?
5 comments
[Q1] Baseline Selection. We thank the reviewer for this comment. Our original baseline selection followed the evaluations in GiGPO and GraphGPO, focusing on GRPO and existing step-level credit assignment methods. To provide a more comprehensive comparison, we have additionally included PPO and RLOO in the revised Table 3. GraphHCA achieves a success rate of 84.0%, outperforming PPO (66.65%), RLOO (66.56%), GRPO (71.1%), GiGPO (79.0%), and GraphGPO (81.6%).
Regarding prompting baselines, the base Qwen2.5-VL model provides a prompting baseline for Sokoban. While ReAct and Reflexion are evaluated in our text-based environments, applying their existing implementations to Sokoban would require adaptation to visual observations. Our primary focus is on evaluating step-level credit assignment, for which comparisons with GRPO, GiGPO, and GraphGPO directly assess the benefits over trajectory-level and existing step-level approaches. The corresponding additions are highlighted in blue in the revised manuscript.
[Q2] Overall Success Rate Calculation. We thank the reviewer for this careful observation. The key distinction is that the overall success rate is computed from task-level results for each seed, rather than as a weighted average of the reported subtask means. Following GraphGPO and GiGPO, we first compute the overall success rate for each seed and then average across three seeds:
where and denote the numbers of successful and evaluated tasks in category for seed , respectively.
In contrast, the reported subtask success rates are averaged independently across seeds. Since evaluation tasks are sampled without fixed category quotas, the subtask proportions may vary across seeds. Consequently, a weighted average of the reported subtask means need not equal the overall mean, accounting for the apparent discrepancy at .
Dear Reviewer,
Thank you again for your valuable feedback. As the discussion period is approaching its end, we would greatly appreciate it if you could let us know whether our rebuttal and additional experiments have addressed your concerns, or if any further clarification is needed.
Thank you for your time and consideration.
We appreciate the reviewer's careful assessment and detailed comments. We have revised the manuscript to address the concerns raised and provide point-by-point responses below.
[W1] Presentation Improvements. We thank the reviewer for this constructive feedback. We have substantially revised the presentation to improve clarity and information density. Specifically, we merged the original Figures 1 and 2 into a unified overview (now Fig. 1), introduced Table 1 to clearly distinguish GraphHCA from existing credit assignment methods, and removed redundant method descriptions from the Preliminaries. We further revised several passages throughout the paper to reduce redundancy and improve clarity and conciseness.
[W2] Refining Theoretical Contributions. We thank the reviewer for this constructive suggestion. We have removed the original Propositions 4.2 and 4.3, incorporating their standard properties directly into the text.
The revised theoretical presentation focuses on two key results. Proposition 4.1 establishes a closed-form characterization of the hindsight ratio in terms of state-wise success probabilities, enabling model-free credit estimation without auxiliary hindsight models or additional policy evaluations. The revised Proposition 4.2 further characterizes the relationship between GraphHCA and GraphGPO, showing that the latter's shortest-path criterion corresponds to best-case aggregation, whereas GraphHCA evaluates expected continuations under empirical transition frequencies. We further illustrate this distinction through a concrete example in Fig. 1(b), contrasting shorter but less reliable paths with longer, more reliable alternatives (Lines 346-350).
These revisions distinguish standard theoretical properties from our central contribution: to the best of our knowledge, the first model-free realization of HCA for LLM agents through a closed-form hindsight ratio, without auxiliary models or additional policy evaluations.
[W3] Statistical Significance, Consistency, and Limitations. We thank the reviewer for these thoughtful comments.
Statistical Significance. We follow the standard evaluation protocol of three random seeds, consistent with GiGPO and GraphGPO. To further assess the reliability of our results, we conduct Welch's t-tests. GraphHCA achieves statistically significant improvements over both baselines on ALFWorld at both model scales (p≤0.035) and on WebShop score with the 1.5B model (p≤0.012). Beyond these statistically significant gains, GraphHCA matches or exceeds both baselines across all aggregate benchmark metrics, providing further evidence of its effectiveness across diverse settings.
Consistency. We have further clarified the underlying mechanism in the revised Introduction and Sec. 4.4 (Lines 50–90 and 318–354). Unlike GiGPO, which relies on realized rollout returns, and GraphGPO, which favors shortest-path progress, GraphHCA derives a closed-form hindsight ratio in terms of state-wise success probabilities and estimates these probabilities from pooled rollouts, without the additional outcome-conditioned LLM inference required by HCAPO. By aggregating expected continuations under empirical transition frequencies, GraphHCA accounts for how reliably actions lead to success. Proposition 4.2 characterizes the distinction between expected and best-case aggregation, while the ablation in Table 4 shows that replacing expectation with max aggregation reduces ALFWorld success from 95.7% to 90.1%. These findings provide a mechanistic explanation for the observed performance trends.
Limitations. The benefits of GraphHCA depend on informative state sharing across rollouts. When states rarely recur, no successful continuations are observed, or actions from the same state have similar successor potentials, step-level credit becomes sparse or uninformative. Consequently, GraphHCA may offer limited improvements in such settings. We have explicitly discussed these limitations in Appendix F.2 (Lines 1110–1116).