- Rating
- 2
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper proposes Structure-Guided Policy Optimization (SGPO) to improve credit assignment in long-horizon language-agent reinforcement learning. The method aggregates on-policy trajectories into a frequency-weighted state-transition graph, partitions the graph into regions using Leiden clustering, and derives inter-regional and intra-regional guidance from graph distances to successful outcomes. These signals are added to the trajectory-level GRPO advantage to provide step-level supervision. Experiments on ALFWorld, WebShop, and Sokoban show improvements over GRPO and generally over GiGPO. However, the main contribution is not yet fully established, as the paper does not directly compare against closely related graph-based credit assignment methods or isolate the benefit of regional abstraction itself.
Critical strengths
The paper addresses a meaningful problem, since assigning credit to individual actions from sparse terminal rewards is a genuine challenge in long-horizon agent training. The proposed distinction between global task progression and local navigation is intuitive, and the graph-based formulation provides an interpretable way to construct additional learning signals without introducing a separate reward model.
The experiments cover several environments and model scales, and the ablations provide some evidence that both guidance signals contribute to the reported gains.
I also appreciate the additional analyses of state canonicalization and success-scarce graph construction, which address practical limitations of the approach. The reported computational overhead is small compared with rollout sampling, making the method relatively easy to incorporate into existing group-based RL pipelines.
Critical weaknesses
- The novelty over existing graph-based credit assignment methods is not sufficiently established. The closest related work is GraphGPO (ICML 2026), which also aggregates rollout trajectories into a state-transition graph and uses changes in graph distance to the goal for step-level credit assignment. SGPO adds Leiden-based regional abstraction and separates global progression from local navigation, but the paper does not clearly establish how much this additional hierarchy contributes beyond direct graph-distance guidance. Although the related-work section cites methods such as GEPO and SALT, the distinction from these graph-based approaches remains underdeveloped. A direct comparison with GraphGPO under matched training budgets, state representations, and evaluation settings is needed to establish the actual methodological advance.
- The current ablation does not isolate the contribution of regional abstraction. Figure 4 removes the inter-regional or intra-regional guidance signal, showing that both are useful within the proposed framework. However, these experiments do not establish that Leiden clustering is necessary. A natural baseline would construct the same empirical graph but calculate progress directly on the original state graph, without partitioning it into regions. This would help determine whether the improvement comes from the hierarchical abstraction or simply from adding graph-based distance signals to GRPO. Adding more substantial evidence would significantly enhance the rigor of the paper’s argumentation.
- The role of edge frequency in the distance-based guidance is unclear. Section 4.1 emphasizes that transition edges are weighted by their empirical frequency. However, the abstract graph in Section 4.2 retains an edge whenever at least one transition connects two regions, and the inter-regional distance is then computed using reverse BFS. Thus, a region-to-region transition observed once can have the same effect on shortest-path distance as one observed frequently. This matters because a rare transition caused by an unusual trajectory or imperfect state matching could introduce a shortcut and change the structural advantage assigned to multiple actions. Although edge frequencies influence community detection, their role in the subsequent distance calculation is limited. Could the authors clarify this design choice?
- The statistical evidence is insufficient to establish the reliability of the reported improvements. The experiments use three random seeds, but no paired significance tests or confidence intervals are reported. While SGPO generally outperforms GiGPO, the gains are relatively small in some settings. For example, on Sokoban, SGPO achieves 82.1 ± 2.8%, compared with 81.0 ± 3.6% for the strongest GiGPO variant. Given the reported variability, it is unclear whether such improvements are consistent across runs.
Questions for authors
See above.