acceptodds
Under review as a conference paper at ICLR 2027

GHGPO: Finite-Budget Graph-Hit Credit Assignment for Multi-turn Agentic Tasks

18 views

Abstract

Fine-grained credit assignment is critical for reinforcement learning in multi-turn agents, yet critic-free group-based methods typically provide only coarse trajectory-level supervision. Recent graph-based approaches improve process credit by using structural distance to success states, but structural efficiency alone does not fully characterize the downstream success probability under the current policy and the finite interaction budget. We propose **Graph-Hit Group Policy Optimization (GHGPO)**, which retains both the state-transition topology and the empirical frequencies of repeated transitions in grouped rollouts to construct an empirical probabilistic state-transition graph reflecting policy-dependent transition behaviors. Based on this graph, GHGPO estimates a finite-budget graph-hit probability to characterize policy-dependent success probability within the available interaction budget, and uses it for fine-grained process credit assignment. Across ALFWorld, WebShop, and Sokoban, GHGPO consistently improves aggregate performance over strong reinforcement learning baselines across different model scales. Ablation studies further validate the importance of finite-budget estimation and the complementarity between policy-dependent success probability and structural efficiency, while GHGPO requires no additional environment interactions and introduces less than 0.2% additional per-iteration computation.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Reinforcement learning, Policy optimization, Agentic task

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_XKeCOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
3(+1)
Read review
Paper summary

This paper introduces Graph-Hit Group Policy Optimization (GHGPO), a graph-based reward estimation method for agentic RL. By incorporating both the topological distance and the policy-dependent success probability of each action, this paper provides a more comprehensive combination of reward estimation compared with GraphGPO. The empirical results show that GHGPO consistently improves agentic RL performance in various agentic tasks.

Critical strengths
  1. The motivation of this idea is clear: previous graph-based reward estimation methods do not consider policy-dependent success. GHGPO incorporates this feature, which makes the soundness of this paper easy to understand.

  2. This paper conducts comprehensive experiments, including two text-based and one visual-based agentic environments. In addition, this paper also involves analysis of the motivation and efficiency, broadly showing the benefits of this method.

Critical weaknesses
  1. One main concern is that GHGPO is established on an assumption: the policy-dependent success that is characterized by the finite-budget graph-hit probability is helpful for reward estimation. However, the reliability of policy-dependent success highly relies on the performance of the base model. Given a weak base model, the policy-dependent success induced from the sampled trajectories may be unstable for analysis. Further clarification on the reliability of this feature could be helpful.

  2. Another main concern is that the contribution of GHGPO is strongly based on graph-based reward estimation. The authors only mention one graph-based reward estimation method (GraphGPO), which suggests that this paper is just a follow-up of a previous method. In addition, GraphGPO also cannot be applied to all agentic tasks (for example, for math and coding tasks, the observations are very stochastic, which introduces significant challenges for state determination for group computation), which also limits the generality of GHGPO.

  3. The formulation of Sec. 4 is a little hard to follow, especially in Eq. (8), the matrix and the subscript of P^\hat{P}. It would be better to further explain or change the representation of this formulation.

  4. Minor: In Figure 1, Prefix: visting -> visiting. Besides, using complex formulas in Figure 1 without explicit explanation may decrease readability.

Questions for authors

See main weaknesses

7 comments
AuthorsOpenReview ↗

Response to Reviewer XKeC (1/4)

We thank the reviewer for the thoughtful review and valuable feedback. Below, we address the reliability of graph-hit credit under weak base policies, clarify GHGPO's distinct methodological contributions and generalizability, and provide further explanations to improve the clarity of the paper.


W1: One main concern is that GHGPO is established on an assumption: the policy-dependent success that is characterized by the finite-budget graph-hit probability is helpful for reward estimation. However, the reliability of policy-dependent success highly relies on the performance of the base model. Given a weak base model, the policy-dependent success induced from the sampled trajectories may be unstable for analysis. Further clarification on the reliability of this feature could be helpful.

A1: We thank the reviewer for raising this question. GHGPO assigns relative process-level credit by comparing the finite-budget graph-hit probabilities of candidate actions' successor states. Ideally, actions with higher probabilities of eventual task success should receive higher credit. Therefore, reliable credit assignment should preserve action rankings consistent with their underlying success probabilities. To examine whether graph-hit estimates obtained from limited rollouts achieve this, we use a large number of sampled trajectories to estimate empirical success probabilities as a reference and evaluate the consistency of the resulting action rankings.

Experimental setup. We evaluate five checkpoints of Qwen2.5-1.5B-Instruct during training on ALFWorld, representing policies at different training stages and performance levels. Policy Success Rate denotes the task success rate of each checkpoint on the ALFWorld validation set, measuring the policy's overall task-solving ability.

At each checkpoint, we sample 256 trajectories for each of 64 ALFWorld tasks, yielding 16,384 trajectories in total. For each task separately, we estimate the empirical success probability of each observed state ss using its corresponding 256 trajectories:

\frac{\\#\text{occurrences of }s\text{ in successful trajectories}} {\\#\text{total occurrences of }s}.$$ This estimate serves as a large-sample Monte Carlo empirical reference for the corresponding task under the same checkpoint policy. We then subsample **$M=8$ trajectories per task**, matching the rollout budget used during training, to construct empirical transition graphs and compute finite-budget graph-hit probabilities. For pairs of candidate actions originating from the same state, we compare the rankings induced by their successor states' graph-hit probabilities with those induced by the empirical success probabilities. **A higher proportion of consistent action-pair rankings indicates that the relative credit ordering induced by finite-sample graph-hit estimates is more consistent with the ordering implied by large-sample empirical success frequencies.** Thus, action-ranking consistency reflects the effectiveness of finite-sample graph-hit estimates in relative credit assignment. We compute **Pairwise Ranking Agreement (PRA)** as the number of action pairs with consistent rankings divided by the total number of compared action pairs, requiring agreement on greater-than, less-than, and equality relations. **Results.** | Training Step | Policy Success Rate | Graph-hit PRA | |---|---:|---:| | 0 | 8.67% | 84.80% | | 40 | 51.83% | 76.57% | | 80 | 78.04% | 84.03% | | 120 | 80.62% | 77.40% | | 150 | 83.94% | 80.14% | **Notably, at the initial checkpoint, the policy achieves only 8.67% task success, while graph-hit already reaches 84.80% PRA.** Across all five checkpoints, despite substantial differences in policy success rates, PRA remains between **76.57% and 84.80%**. These results indicate that, even when the base policy has a low overall task success rate, graph-hit estimates obtained using the training-time rollout budget can still largely preserve action rankings consistent with the large-sample empirical reference. Furthermore, Figure 3 shows favorable early-training validation performance of GHGPO compared with GraphGPO, providing complementary evidence of its effectiveness in policy optimization.
AuthorsOpenReview ↗

Response to Reviewer XKeC (2/4)

W2(a): Another main concern is that the contribution of GHGPO is strongly based on graph-based reward estimation. The authors only mention one graph-based reward estimation method (GraphGPO), which suggests that this paper is just a follow-up of a previous method.

A2: We thank the reviewer for raising this concern. We agree that GHGPO should be more clearly positioned within the broader literature on graph-based credit assignment to better highlight its distinct contributions.

Distinctions from existing graph-based methods. SALT [1] and G2PO [2] both leverage graph structures to aggregate recurring states or transitions across trajectories, enabling cross-trajectory sharing of credit information. Specifically, SALT mainly aggregates trajectory-level outcome advantages over shared transitions, while G2PO aggregates discounted terminal returns within identical state groups and uses the resulting state values to compute process advantages. In contrast, GraphGPO further exploits the multi-step topology of the graph to assign process credit based on shortest-path distances to successful states. GHGPO goes beyond structural distance by explicitly modeling probabilistic success reachability, using empirical transition probabilities and multi-step recursion to estimate the probability of reaching success under the current policy within a finite interaction budget.

Distinct methodological contributions. GHGPO reveals the limitations of structural distance in characterizing success reachability. As demonstrated in Sec. 4.1, states with identical shortest-path distances can have different success probabilities, and a state that is structurally closer to success may even have a lower success probability than a more distant state.

To address this limitation, GHGPO preserves empirical transition frequencies from grouped rollouts to construct a policy-dependent probabilistic transition model. It then computes finite-budget graph-hit probabilities through dynamic programming and visiting-step marginalization. Unlike existing methods that primarily derive process credit through outcome-information aggregation, state-value differences, or structural distances, GHGPO explicitly models success reachability using multi-step probabilistic transitions and the remaining interaction budget. Consequently, even with identical graph topology, different empirical transition frequencies can yield different graph-hit credit, while shortest-path distances remain unchanged. This constitutes a distinct methodological contribution to graph-based process-level credit assignment.

Empirical evidence. The ablation results in Table 3 further validate the effectiveness of graph-hit credit and its complementarity with distance-based credit. On WebShop, AE+AdA_E+A_d achieves 78.65% success, AE+AhA_E+A_h achieves 83.33%, and the full combination AE+Ad+AhA_E+A_d+A_h reaches 84.63%. On ALFWorld, the corresponding overall success rates are 92.71%, 93.75%, and 96.61%, respectively. These results demonstrate that finite-budget success reachability provides an effective process-credit signal beyond structural distance, and that combining the two can further improve policy optimization.

We will expand the Related Work section to include a comparison with these graph-based credit assignment methods and further clarify GHGPO's distinct contribution in explicitly modeling policy-dependent, finite-budget success reachability.

References

[1] Jiazheng Li et al. SALT: Step-level Advantage Assignment for Long-horizon Agents via Trajectory Graph. Findings of EACL 2026, pp. 4709–4725.

[2] Yunan Wang et al. Group-Graph Policy Optimization for Long-Horizon Agentic Reinforcement Learning. NeurIPS 2026.

AuthorsOpenReview ↗

Response to Reviewer XKeC (3/4)

W2(b): In addition, GraphGPO also cannot be applied to all agentic tasks (for example, for math and coding tasks, the observations are very stochastic, which introduces significant challenges for state determination for group computation), which also limits the generality of GHGPO.

A3: We thank the reviewer for highlighting the challenges of state identification and merging in complex tasks. While mathematical reasoning and coding tasks involve more diverse state representations, making state aggregation more challenging, this does not preclude the application of graph-based RL to such tasks. In fact, recent studies have explored this direction through both more flexible state-matching and merging strategies and RL algorithms built upon aggregated states, demonstrating encouraging potential.

Specifically, regarding state matching, GraphPO [3] uses semantic summaries of reasoning prefixes and embedding similarity to identify and merge equivalent states across reasoning trajectories. SALT [1] further employs semantic matching in complex environments such as AppWorld, where actions involve free-form code and natural-language instructions, allowing functionally equivalent steps with different surface forms to be merged. Regarding RL algorithms, GraphPO leverages merged reasoning graphs for advantage estimation and demonstrates performance improvements on mathematical reasoning tasks. SALT and G2PO [2] also exploit shared states across trajectories for fine-grained credit assignment, demonstrating effectiveness on complex long-horizon agentic tasks, including AppWorld. Together, these studies suggest that with task-appropriate state-matching mechanisms, state aggregation and graph-based RL have promising potential for more complex tasks.

Adaptation to mathematical reasoning. Inspired by GraphPO's semantic state construction and merging strategy, we conducted an additional experiment using Qwen2.5-7B-Math. Specifically, we divide reasoning trajectories into reasoning segments and represent intermediate states using semantic summaries of their reasoning prefixes. We then encode these summaries into embeddings and use cosine similarity to identify and merge semantically equivalent states across trajectories. This enables intermediate states representing similar reasoning progress to be aggregated despite differences in their textual expressions.

On the resulting state-transition graph, GHGPO preserves empirical transition frequencies and computes finite-budget graph-hit probabilities for process credit assignment. We express the finite interaction budget in reasoning-segment units by dividing the response token budget by the minimum semantic-segment length.

Experimental results.

MethodAIME24AIME25MATH500LiveCodeBench
Qwen2.5-7B-Math†13.66.354.85.7
GRPO†23.315.579.511.4
GraphPO†32.124.591.616.9
GraphGPO31.1 ± 1.720.9 ± 0.987.8 ± 0.713.6 ± 0.5
GHGPO33.2 ± 1.923.3 ± 1.191.9 ± 0.817.1 ± 0.3

† Results are taken from GraphPO [3]. Results for GraphGPO and GHGPO are obtained from our experiments and reported as mean ± standard deviation over three independent random seeds.

GHGPO achieves the best performance on three of the four benchmarks (AIME24, MATH500, and LiveCodeBench), while remaining competitive on AIME25. It consistently outperforms the base model and GRPO across all benchmarks. Compared with graph-based methods, GHGPO outperforms GraphGPO on all four benchmarks and achieves better results than GraphPO on three of them. These results further demonstrate that, with a suitable semantic state-matching and merging mechanism, GHGPO's finite-budget graph-hit credit assignment can be effectively applied to mathematical reasoning, with improvements also observed on the LiveCodeBench coding benchmark. This provides additional empirical support for extending state-aggregation-based graph RL to more complex tasks.

References

[1] Jiazheng Li et al. SALT: Step-level Advantage Assignment for Long-horizon Agents via Trajectory Graph. Findings of EACL 2026, pp. 4709–4725.

[2] Yunan Wang et al. Group-Graph Policy Optimization for Long-Horizon Agentic Reinforcement Learning. NeurIPS 2026.

[3] Yuliang Zhan et al. GraphPO: Graph-based Policy Optimization for Reasoning Models. arXiv:2606.18954, 2026.

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

This paper proposes Graph-Hit Group Policy Optimization (GHGPO), a critic-free reinforcement learning method for fine-grained credit assignment in multi-turn agents. Building upon GraphGPO, which assigns process rewards using shortest-path distances to successful states, GHGPO additionally estimates policy-dependent transition probabilities from grouped rollouts. These probabilities are used to compute finite-budget graph-hit probabilities, which are combined with distance-based and trajectory-level advantages for policy optimization. Experiments on ALFWorld, WebShop, and Sokoban demonstrate consistent performance improvements over existing group-based RL methods, with minimal additional computational overhead.

Critical strengths
  1. Well-motivated extension of graph-based credit assignment. The paper identifies a meaningful limitation of distance-based process rewards: structural proximity to a goal does not necessarily reflect the probability of reaching it under the current policy. Incorporating transition frequencies and finite interaction budgets offers a reasonable way to address this limitation.

  2. Consistent empirical improvements. GHGPO outperforms GraphGPO across three interactive environments and multiple model scales. The improvements on WebShop are particularly encouraging, and the ablation studies generally support the complementary roles of distance-based and graph-hit advantages.

  3. Low computational overhead. The proposed method requires neither additional environment interactions nor a learned critic, and the reported advantage-computation overhead is less than 0.2% of the total training time.

Critical weaknesses
  1. Potential mismatch between the empirical Markov model and the actual agent policy. Equations (5)–(11) model state transitions using a stationary transition matrix. However, the agent's policy conditions on interaction history and the current step count, as shown in Appendix C.3. Identical environment states encountered under different histories or remaining budgets may therefore induce different action distributions. Consequently, the estimated graph-hit probabilities may not accurately reflect the actual policy's success probabilities.

  2. Potential confounding from advantage scaling. GHGPO combines three independently normalized advantage signals, whereas GraphGPO uses only trajectory-level and distance-based advantages. Adding (A_h) changes not only the information available for credit assignment but also the relative weight and scale of process-level supervision. Without controlling these factors, the observed improvements cannot be conclusively attributed to the complementary information provided by (A_h).

Questions for authors
  1. What is the precise probabilistic interpretation of Equation (11)? The visitation distribution (q_\pi(k\mid s)) accounts for repeated visits rather than only first visits. For example, suppose an agent reaches state (s) after one step, where each subsequent step has a 50% chance of success and a 50% chance of remaining in (s), with a total budget of three steps. The success probability upon first reaching (s) is 0.75, whereas Equation (11) yields approximately 0.571 due to repeated-visit weighting. Could the authors clarify the intended probabilistic quantity and explain why this visitation-weighted estimate is appropriate for action-level credit assignment?

  2. Can the authors disentangle the contribution of (A_h) from advantage scaling? Could the authors compare GHGPO against GraphGPO with an increased distance-advantage coefficient (e.g., (A_E+2A_d)), or normalize the combined process advantages to a matched scale? Such comparisons would help establish whether the improvements arise from the additional graph-hit information rather than stronger process-level supervision.

4 comments
AuthorsOpenReview ↗

Response to Reviewer tzyr (1/3)

We thank the reviewer for the careful assessment and insightful questions. Below, we clarify the probabilistic interpretation of Eq. (11), explain the role of shared graph-based credit under history-dependent policies, and provide additional experiments to disentangle graph-hit credit from advantage scaling.


Q1: What is the precise probabilistic interpretation of Equation (11)? The visitation distribution qπ(k∣s)q_\pi(k\mid s) accounts for repeated visits rather than only first visits. For example, suppose an agent reaches state ss after one step, where each subsequent step has a 50% chance of success and a 50% chance of remaining in ss, with a total budget of three steps. The success probability upon first reaching ss is 0.75, whereas Equation (11) yields approximately 0.571 due to repeated-visit weighting. Could the authors clarify the intended probabilistic quantity and explain why this visitation-weighted estimate is appropriate for action-level credit assignment?

A1: Clarification of Eq. (11)

(1) Probabilistic interpretation of Eq. (11). Eq. (11) represents the expected probability of reaching success within the remaining interaction budget when a visitation instance of state ss is randomly sampled under the finite-horizon visitation measure induced by the aggregated empirical transition model, rather than the success probability conditioned on reaching state ss at a particular step.

Therefore, it differs from the success probability conditioned on the first arrival at state ss. In the reviewer's example, 0.75 corresponds to the probability of reaching success within the remaining budget upon first reaching ss (at step 1), whereas 0.571 represents the expected probability of reaching success within the corresponding remaining budget from a randomly sampled visitation instance of ss under the above finite-horizon visitation measure. These values correspond to different probabilistic quantities.

As noted immediately after Proposition 1 in Sec. 4.3, the visiting-step distribution is derived from the aggregated empirical transition graph rather than the actual visitation positions in individual trajectories. The visitation positions and remaining budgets of the same state may vary considerably across sampled trajectories. Directly using the remaining budget of each visitation instance from its original trajectory may make process credit overly dependent on individual samples, potentially reducing the robustness of advantage estimation. In contrast, deriving the visiting-step distribution from the aggregated empirical graph allows us to reuse transition evidence across grouped rollouts, reduce reliance on sparse occurrence-level statistics, and obtain a unified finite-budget success-reachability estimate shared across repeated visits.

The ablation results in Appendix D.1 (Table 4) further support this design: replacing the aggregated visitation distribution with trajectory-specific remaining budgets reduces ALFWorld success from 96.61% to 95.89% and WebShop success from 84.63% to 80.98%.

(2) Role in action-level credit assignment. Consider the reviewer's example, with the initial state denoted by s1s_1. The state transitions can be unfolded according to visitation steps as follows:

s₁ ─────→ s ──0.5──→ s⁺
           │
          0.5
           ↓
           s ──0.5──→ s⁺
           │
          0.5
           ↓
           s

Here, s1s_1 denotes the initial state, s+s^+ denotes the successful terminal state, and the three occurrences of ss represent repeated visits to the same state at different steps. The transition from s1s_1 to ss belongs to the state group originating from s1s_1. Both transitions from ss to s+s^+ and from ss back to itself belong to the state group originating from ss. As described in Sec. 4.3, the graph-hit probability of the successful terminal state s+s^+ is 1, whereas the graph-hit probability of ss computed using Eq. (11) is approximately 0.571. Therefore, by comparing the graph-hit probabilities of the successor states within the latter state group, GHGPO can distinguish transitions leading to success from those returning to the same state and assign higher relative process credit to the former.

This illustrates that, although the shared state-level success reachability defined by Eq. (11) differs from the success probability conditioned on the visitation step of state ss, it can still effectively distinguish the success prospects of different transitions and provide informative relative signals for action-level credit assignment.

AuthorsOpenReview ↗

Response to Reviewer tzyr (2/3)

W1: Equations (5)–(11) model state transitions using a stationary transition matrix. However, the agent's policy conditions on interaction history and the current step count, as shown in Appendix C.3. Identical environment states encountered under different histories or remaining budgets may therefore induce different action distributions. Consequently, the estimated graph-hit probabilities may not accurately reflect the actual policy's success probabilities.

A2: Clarification of History Dependence

(1) History dependence and shared graph-based process credit. Existing graph-based credit assignment methods, including SALT [1], G2PO [2], and GraphGPO, leverage repeated states or transitions across different trajectories to construct shared graph-based process credit, which differs from trajectory-level credit assignment. Following this paradigm, GHGPO aggregates transitions observed from the same state under different historical contexts across grouped rollouts to construct an empirical probabilistic transition model P^π\widehat P_\pi. This aggregation implicitly averages transition behavior across different histories according to empirical visitation frequencies.

Based on this model, GHGPO computes finite-budget success reachability through multi-step probabilistic recursion, providing unified process credit for different visits to the same state. The key idea is to reuse transition evidence across trajectories and provide relative process-level supervision for sampled actions through aggregated state-level success reachability, rather than separately estimating success probabilities under each particular history.

(2) Future research directions. HGPO [3] suggests that incorporating historical context in a more fine-grained manner may further improve the fidelity of graph-based credit estimation to the actual history-dependent policy. However, explicitly incorporating complete interaction histories into state definitions introduces a trade-off between historical-context fidelity and cross-trajectory statistical sharing. Preserving more historical information can help distinguish policy behavior under different contexts, but may also excessively fragment state groups, reduce the number of repeated states and shared transitions, and make empirical transition estimation sparser. Therefore, developing methods that preserve important historical information while maintaining effective cross-trajectory evidence sharing is a promising direction for future research.

References

[1] Jiazheng Li et al. SALT: Step-level Advantage Assignment for Long-horizon Agents via Trajectory Graph. Findings of EACL 2026.

[2] Yunan Wang et al. Group-Graph Policy Optimization for Long-Horizon Agentic Reinforcement Learning. NeurIPS 2026.

[3] Shuo He et al. Hierarchy-of-Groups Policy Optimization for Long-Horizon Agentic Tasks. International Conference on Learning Representations (ICLR), 2026.

AuthorsOpenReview ↗

Response to Reviewer tzyr (3/3)

W2: GHGPO combines three independently normalized advantage signals, whereas GraphGPO uses only trajectory-level and distance-based advantages. Adding AhA_h changes not only the information available for credit assignment but also the relative weight and scale of process-level supervision. Without controlling these factors, the observed improvements cannot be conclusively attributed to the complementary information provided by AhA_h.

Q2: Can the authors disentangle the contribution of AhA_h from advantage scaling? Could the authors compare GHGPO against GraphGPO with an increased distance-advantage coefficient (e.g., AE+2AdA_E+2A_d), or normalize the combined process advantages to a matched scale? Such comparisons would help establish whether the improvements arise from the additional graph-hit information rather than stronger process-level supervision.

A3: We thank the reviewer for this valuable suggestion. Following the reviewer's recommendation, we additionally evaluate AE+2AdA_E+2A_d to examine whether increasing the strength of distance-based process supervision can reproduce GHGPO's improvements. We also include AE+2AhA_E+2A_h to further investigate the complementary contributions of the two process-level signals.

The results with Qwen2.5-1.5B-Instruct are reported below (mean over three random seeds, with standard deviations in parentheses):

Advantage CombinationALFWorld All ↑WebShop Score ↑WebShop Succ. ↑
AE+AdA_E+A_d (GraphGPO)92.71(1.32)89.29(1.48)78.65(3.86)
AE+2AdA_E+2A_d93.41(1.20)89.53(1.97)80.39(2.36)
AE+2AhA_E+2A_h94.53(2.48)91.54(1.73)83.59(1.61)
AE+Ad+AhA_E+A_d+A_h (GHGPO)96.61(1.96)92.27(2.46)84.63(2.74)

The results show that increasing the distance-advantage coefficient alone does not reproduce GHGPO's gains. Compared with AE+2AdA_E+2A_d, GHGPO improves ALFWorld success by 3.20 percentage points, WebShop task score by 2.74 points, and WebShop success by 4.24 percentage points.

Moreover, GHGPO also outperforms AE+2AhA_E+2A_h across all three aggregate metrics. With the same total coefficient assigned to process-level advantages, combining AdA_d and AhA_h performs better than doubling either component alone.

These findings support that GHGPO's improvements arise from the complementary information provided by finite-budget graph-hit credit, rather than merely increasing the weight of process-level supervision. Structural distance and graph-hit credit capture distinct aspects of process credit—structural efficiency and policy-dependent finite-budget success reachability, respectively—and their combination achieves the best overall performance.

AuthorsOpenReview ↗

Looking Forward to Your Reply

Dear Reviewer tzyr,

Thank you once again for your thoughtful review and insightful questions.

We greatly appreciate the time and effort you have devoted to evaluating our work. As the author–reviewer discussion period approaches its end, we would sincerely welcome any further feedback on our rebuttal, particularly whether our explanations and additional evidence have addressed your questions. Please feel free to let us know if anything remains unclear.

Thank you again for your consideration.

Best regards,
The Authors

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

This paper introduces Graph-Hit Group Policy Optimization (GHGPO) as another group-based and graph-based credit assignment method for LLM agent training. The existing GraphGPO uses the shortest distance from current state to success state to assign step-level advantage. This paper points out that the structural distance may not reflect the underlying probability of the current policy being successful. Therefore, GHGPO calculates state-transition frequencies from grouped rollouts to construct a policy-dependent probabilistic transition graph. It then employs dynamic programming to estimate the probability that each state will reach a success state within a finite interaction budget. This probability-based "process advantage" is then combined with the distance-based advantage from GraphGPO and the trajectory-level advantage from GRPO to guide policy optimization. Experimental results demonstrate that GHGPO outperforms GraphGPO on ALFWorld, WebShop, and Sokoban.

Critical strengths

Clear and Validated Motivation. This paper points out that the structural distance may not reflect the underlying probability of the current policy being successful, and further validates this discrepancy between distance-based credit and success probability through empirical analysis. This key observation well motivates the design of the proposed finite-budget graph-hit probability.

Critical weaknesses
  1. Small and Saturated Environments. The evaluated environments (ALFWorld, WebShop and Sokoban) are relatively simple and structured, and the agent execution traces can easily produce overlapping states, which makes it easy to construct. However. in more complex agent environments where states tend to be highly diverse, estimates of the "graph-hit probability" may be unreliable. It would be beneficial to include analysis of how estimation errors affect the final credit assignment and evaluation on GHGPO's generalizability to more complex environments.

  2. The paper directly combines distance-based advantage, graph-hit advantage and the outcome GRPO advantage together, while it is unclear why this would benefit training, or why they should be combined in this way. Also in the experiments the three advantages are all set to 1 without weight sensitivity analysis.

Questions for authors

See weakness.

6 comments
AuthorsOpenReview ↗

Response to Reviewer 2yTC (1/3)

We thank the reviewer for the careful evaluation and constructive suggestions. Below, we address the concerns regarding finite-sample credit estimation, generalization to more complex environments, and the motivation and weighting of the three advantage signals, supported by additional analyses and experiments.


W1(a): The evaluated environments (ALFWorld, WebShop and Sokoban) are relatively simple and structured, and the agent execution traces can easily produce overlapping states, which makes it easy to construct. However. in more complex agent environments where states tend to be highly diverse, estimates of the "graph-hit probability" may be unreliable. It would be beneficial to include analysis of how estimation errors affect the final credit assignment and evaluation on GHGPO's generalizability to more complex environments.

A1(a): Effect of Finite-Sample Estimation on Credit Assignment.

GHGPO assigns relative process-level credit by comparing the graph-hit probabilities of candidate actions' successor states. Ideally, actions with higher probabilities of eventual task success should receive higher credit. We therefore examine the effect of finite-sample estimation on credit assignment by comparing the action rankings induced by limited-sample graph-hit estimates with those induced by a large-sample empirical success-rate reference. A higher proportion of consistent action-pair rankings indicates that the relative credit ordering induced by finite-sample graph-hit estimates is more consistent with the ordering implied by large-sample empirical success frequencies. Thus, action-ranking consistency reflects the effectiveness of finite-sample graph-hit estimates in relative credit assignment.

Experimental setup. We evaluate five checkpoints of Qwen2.5-1.5B-Instruct during training on ALFWorld. At each checkpoint, we sample 256 trajectories for each of 64 ALFWorld tasks, yielding 16,384 trajectories in total. For each task separately, we use its 256 trajectories to construct a large-sample Monte Carlo empirical success-rate reference:

\frac{\\#\text{occurrences of }s\text{ in successful trajectories}} {\\#\text{total occurrences of }s}.$$ We then subsample $M\in\\{8,16,32,64\\}$ trajectories per task to construct empirical transition graphs and compute finite-budget graph-hit probabilities, where **$M=8$ matches the rollout group size used during training**. For each sampled graph, we form pairs of candidate actions originating from the same state and compare their rankings according to the graph-hit probabilities and $\widehat p_{\mathrm{emp}}$ of their successor states. **Pairwise Ranking Agreement (PRA)** is calculated as the number of action pairs with consistent rankings divided by the total number of compared action pairs, requiring agreement on greater-than, less-than, and equality relations. **Results (PRA, %).** | Training Step | $M=8$ | $M=16$ | $M=32$ | $M=64$ | |---|---:|---:|---:|---:| | 0 | 84.80 | 86.90 | 86.94 | 88.84 | | 40 | 76.57 | 83.51 | 85.78 | 91.38 | | 80 | 84.03 | 87.24 | 88.82 | 92.12 | | 120 | 77.40 | 82.04 | 85.93 | 88.63 | | 150 | 80.14 | 82.22 | 84.51 | 88.59 | At the training-time rollout budget of $M=8$, graph-hit achieves **76.57%–84.80% PRA** across the five checkpoints, indicating that it largely preserves action-credit rankings consistent with the large-sample reference despite limited sampling. Increasing the graph-construction budget from $M=8$ to $M=64$ improves PRA at every checkpoint, suggesting that additional sampled trajectories help reduce the unreliability of finite-sample estimation on relative action-credit rankings.
AuthorsOpenReview ↗

Response to Reviewer 2yTC (2/3)

W1(b): The evaluated environments (ALFWorld, WebShop and Sokoban) are relatively simple and structured, and the agent execution traces can easily produce overlapping states, which makes it easy to construct. However. in more complex agent environments where states tend to be highly diverse, estimates of the "graph-hit probability" may be unreliable. It would be beneficial to include analysis of how estimation errors affect the final credit assignment and evaluation on GHGPO's generalizability to more complex environments.

A1(b): Generalization to More Complex Environments.

To evaluate the generalizability of GHGPO beyond the original three environments, we conduct additional experiments on ScienceWorld and mathematical reasoning tasks.

(1) ScienceWorld. ScienceWorld involves multi-step scientific experiments, diverse task variations, and dynamic environment interactions. We use Qwen2.5-1.5B-Instruct as the base model, with a maximum of 30 interaction steps per episode and a rollout group size of 8. All compared methods use the same training and evaluation settings. Results are reported as mean ± standard deviation over three independent random seeds.

MethodScienceWorld ScoreScienceWorld Succ. (%)
GRPO31.60 ± 1.5320.90 ± 1.24
GiGPO34.12 ± 1.7925.90 ± 1.83
GraphGPO38.71 ± 1.9328.94 ± 1.82
GHGPO40.13 ± 2.1430.19 ± 1.96

GHGPO achieves the highest average score and success rate among the compared methods, improving upon GraphGPO by 1.42 points in score and 1.25 percentage points in success rate. These results show that finite-budget graph-hit credit remains beneficial in a more complex scientific interaction environment.

(2) Mathematical reasoning. We further evaluate GHGPO using Qwen2.5-7B-Math. Following the semantic state definition and merging strategy of GraphPO [1], we first partition sampled reasoning trajectories into reasoning segments. At each segment boundary, we summarize the entire reasoning prefix, including the original problem and all preceding reasoning steps, to represent the intermediate semantic state. We then encode these summaries into embeddings and merge semantically equivalent states across trajectories based on cosine similarity. This allows reasoning trajectories with different textual expressions but similar intermediate progress to share state groups.

Using the resulting graph, GHGPO estimates empirical transition frequencies from sampled reasoning segments and computes finite-budget graph-hit probabilities for process credit assignment. We express the interaction budget in reasoning-segment units by dividing the response token budget by the minimum reasoning-segment length. GraphGPO and GHGPO use the same state construction and merging procedure.

Experimental results.

MethodAIME24AIME25MATH500LiveCodeBench
Qwen2.5-7B-Math†13.66.354.85.7
GRPO†23.315.579.511.4
GraphPO†32.124.591.616.9
GraphGPO31.1 ± 1.720.9 ± 0.987.8 ± 0.713.6 ± 0.5
GHGPO33.2 ± 1.923.3 ± 1.191.9 ± 0.817.1 ± 0.3

† Results are taken from GraphPO [1]. Results for GraphGPO and GHGPO are obtained from our experiments and reported as mean ± standard deviation over three independent random seeds.

GHGPO achieves the best performance on three of the four benchmarks (AIME24, MATH500, and LiveCodeBench), while remaining competitive on AIME25. It consistently outperforms the base model and GRPO across all four benchmarks. Among graph-based methods, GHGPO outperforms GraphGPO on all four benchmarks and GraphPO on three of them. These results provide further evidence that, with appropriate semantic state matching, GHGPO can be extended beyond structured interactive environments to mathematical reasoning tasks, with improvements also observed on the LiveCodeBench coding benchmark.

Together, the ScienceWorld and mathematical reasoning experiments provide further evidence that GHGPO is applicable beyond the original structured interactive environments. With task-appropriate state matching and merging, the method can be extended to more complex agentic interaction and reasoning tasks.

References

[1] Yuliang Zhan et al. GraphPO: Graph-based Policy Optimization for Reasoning Models. arXiv:2606.18954, 2026.

AuthorsOpenReview ↗

Response to Reviewer 2yTC (3/3)

W2(a): The paper directly combines distance-based advantage, graph-hit advantage and the outcome GRPO advantage together, while it is unclear why this would benefit training, or why they should be combined in this way.

A2: The three advantage signals provide complementary information at different levels.

First, outcome and process advantages are complementary. The trajectory-level outcome advantage AEA_E provides supervision aligned with final task success, while process advantages AdA_d and AhA_h distinguish the contributions of intermediate actions within state groups. In particular, when a state group contains only one transition, its process advantage cannot provide a meaningful relative signal; with very few samples, the signal may also be less reliable. The outcome advantage does not depend on the size of individual state groups and therefore complements process-level supervision.

Second, the two process advantages are complementary. Structural distance and success probability are fundamentally different quantities. As analyzed in Sec. 4.1, states with the same shortest distance can have different success probabilities, and a structurally closer state can even have a lower success probability. Intuitively, graph-hit credit may favor reliable solution paths that the current policy has already learned, whereas distance-based credit encourages structurally shorter paths that the policy may not yet have mastered. Relying solely on distance may emphasize efficient but difficult-to-execute routes, while relying solely on graph-hit may favor familiar, reliable routes without sufficiently encouraging structural efficiency. Combining them therefore incorporates both structural efficiency and policy-dependent finite-budget success reachability.

Third, ablation results support their complementarity. As shown in Table 3, on ALFWorld, AE+AdA_E+A_d, AE+AhA_E+A_h, and the full AE+Ad+AhA_E+A_d+A_h achieve overall success rates of 92.71%, 93.75%, and 96.61%, respectively. On WebShop, their success rates are 78.65%, 83.33%, and 84.63%, respectively. The full combination achieves the best results, empirically supporting the benefit of integrating these complementary advantage signals.


W2(b): Also in the experiments the three advantages are all set to 1 without weight sensitivity analysis.

A3: Weight selection. As defined in Eq. (15), GHGPO combines the three advantage signals as A=λEAE+λdAd+λhAhA=\lambda_E A_E+\lambda_d A_d+\lambda_h A_h. Since the three advantages are normalized before combination, we adopt λE=λd=λh=1\lambda_E=\lambda_d=\lambda_h=1 as a simple and unified default, without benchmark- or model-specific weight tuning.

Weight sensitivity analysis. We conduct additional experiments on WebShop using Qwen2.5-1.5B-Instruct, fixing λE=1\lambda_E=1 and varying the weights of the two process advantages separately.

(1) Graph-hit weight sensitivity (λd=1\lambda_d=1).

λh\lambda_hWebShop ScoreWebShop Succ.
089.2978.65
0.490.7382.89
0.891.8084.03
192.2784.63
292.4384.77

(2) Distance weight sensitivity (λh=1\lambda_h=1).

λd\lambda_dWebShop ScoreWebShop Succ.
091.1983.33
0.491.7783.89
0.891.9384.14
192.2784.63
292.1284.73

The results show that GHGPO maintains strong performance across different weighting configurations. When λh\lambda_h varies from 0.4 to 2, the success rate ranges from 82.89% to 84.77%. Similarly, varying λd\lambda_d from 0.4 to 2 yields success rates between 83.89% and 84.73%. The default equal-weight configuration achieves a WebShop Score of 92.27 and a success rate of 84.63%, demonstrating competitive performance without weight-specific tuning. These results indicate that GHGPO's effectiveness does not depend on a narrowly chosen weighting configuration.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Reviews and Rebuttals

Dear ICLR 2027 AC, SAC, and PC,

We sincerely thank the reviewers and the committee for their time and effort in evaluating our work. We provide a concise summary of the reviews and our rebuttal responses for easier reference.


Summary of Reviews

Our paper initially received three reviews, with 2yTC and XKeC both giving a rating of 2, and tzyr giving a rating of 3. Following the rebuttal, both 2yTC and XKeC raised their ratings from 2 to 3, resulting in all three reviewers currently rating the paper as 3 (Weak Accept). Specifically:

  • Reviewer 2yTC (2 → 3) acknowledged the clear and validated motivation, while questioning finite-sample reliability, generalization, and advantage combination. Following our responses and additional experiments, the reviewer stated that "My concerns have been largely addressed" and updated the rating to 3.
  • Reviewer XKeC (2 → 3) recognized the clear motivation and comprehensive experiments, while raising concerns about reliability under weak policies, methodological novelty, and broader applicability. After our rebuttal, the reviewer explicitly confirmed that the weak-policy analysis and new mathematical reasoning and coding results addressed the main concerns, and raised the rating from 2 to 3.
  • Reviewer tzyr (rating: 3) appreciated the well-motivated approach, consistent improvements, and low computational overhead, while requesting clarification of the probabilistic formulation, history dependence, and advantage scaling. We provided detailed explanations and additional controlled ablations, although no further feedback has been received.

Summary of Rebuttals

During the rebuttal period, we provided additional experiments and detailed clarifications addressing the reviewers' concerns:

ReviewerConcernOur Response and Additional Evidence
2yTCFinite-sample credit reliabilityIntroduced Pairwise Ranking Agreement (PRA). At the training budget M=8M=8, PRA reaches 76.57%–84.80% across five checkpoints and improves with larger sampling budgets.
Generalization beyond structured environmentsAdded experiments on ScienceWorld, mathematical reasoning, and coding, demonstrating improvements beyond the original benchmarks.
Advantage combination and weight sensitivityExplained the complementary roles of the three advantages and provided additional weight-sensitivity experiments.
XKeCReliability under weak policiesAt the initial checkpoint, the policy achieves only 8.67% success, while graph-hit achieves 84.80% PRA against the large-sample empirical reference.
Methodological novelty and broader applicabilityClarified the distinctions from SALT, G2PO, and GraphGPO. With semantic state matching, GHGPO outperforms GraphGPO on all four reasoning and coding benchmarks.
Equation and figure clarityClarified the transition-matrix notation in Eq. (8) and provided explanations and planned corrections for Figure 1.
tzyrEq. (11) and history dependenceClarified the visitation-weighted interpretation of finite-budget graph-hit probability and how the empirical graph aggregates transitions across historical contexts.
Advantage scalingAdded AE+2AdA_E+2A_d and AE+2AhBA_E+2A_h^B comparisons. The full GHGPO combination performs best across the evaluated ALFWorld and WebShop metrics.

We will incorporate the additional experiments, analyses, and methodological clarifications presented during the rebuttal period into the revised manuscript to further strengthen the empirical evidence and improve the clarity of our work.


Major Contributions and Strengths

We would like to highlight three key aspects of our work:

  • Distinct Process Credit: GHGPO models policy-dependent finite-budget success reachability using empirical transition frequencies and probabilistic recursion, capturing information not represented by structural shortest-path distance.
  • Consistent Effectiveness: The original experiments demonstrate improvements across ALFWorld, WebShop, and Sokoban. Additional experiments provide evidence of applicability to ScienceWorld, mathematical reasoning, and coding.
  • Practical Efficiency: GHGPO requires neither an auxiliary critic nor additional environment interactions, with advantage-computation overhead below 0.2% of total training time.

We hope this summary helps the committee assess our responses and the additional evidence provided during the rebuttal period.

Thank you again for your time and consideration.

Best regards,

The Authors

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.