acceptodds
Desk rejected at ICLR 2027

State-Graph Policy Optimization for Long-Horizon Agentic Reinforcement Learning

Desk rejected at ICLR 2027, so left out of the paper lists and the map.

12 views

Abstract

Group-relative reinforcement learning removes the need for a learned critic, but trajectory-level advantages provide coarse credit assignment for long-horizon language-model agents. Stepwise group methods refine this signal by comparing actions from a shared anchor state, yet they still score each action using the Monte Carlo return of its own sampled suffix. For long remaining horizons, these suffix returns can accumulate substantial downstream policy and environment stochasticity and cannot exploit future evidence from other trajectories that revisit the same successor states. We introduce State-Graph Policy Optimization (SGPO), a critic-free step-return estimator that shares such evidence across task-matched rollouts. For each rollout group, SGPO merges observed transitions into an empirical state graph, performs certainty-equivalent policy evaluation on the graph, and uses the resulting values to bootstrap a TD() return along each real trajectory. \method shares value information only through actually visited states, requires no additional environment interactions or model evaluations, and leaves the outer group-relative optimizer unchanged. We prove that the empirical Bellman system is well posed for , characterize its behavior-policy value target under a Markov anchor abstraction, and show that recovers the matched Monte Carlo step advantage. Across two Qwen model scales on ALFWorld and WebShop, SGPO achieves higher mean aggregate performance than the strongest evaluated group-based baselines. On WebShop, shuffling successor connectivity substantially reduces performance, providing evidence that the gain depends on the observed transition structure rather than bootstrapping alone.

Primary area:
reinforcement learning
Keywords:
Large Language Mode, Reinforcement Learning, Long-Horizon Decision Making, Credit Assignment, Value Estimation, Policy Optimization

Reviews

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

Addressing the limitations of existing methods in long-horizon agentic reinforcement learning, this study proposes a state-graph policy optimization approach SGPO. SGPO aggregates transitions observed across a group of related tasks into an empirical state graph. By solving the deterministic equivalence (CE) Bellman equation on this graph, it derives the expected discounted return—serving as a shared successor value—thereby enabling the sharing of future evidence across different trajectories that revisit the same successor states. SGPO combines the CE values ​​computed from the graph with the sampled rewards from each actual trajectory using backward TD(λ)\text{TD}(\lambda). It explicitly balances bias and variance by introducing an interpolation parameter, λ\lambda. Across two benchmarks—ALFWorld (long-horizon embodied tasks) and WebShop (web navigation)—SGPO has demonstrated strong average overall performance and task success rates, consistently achieving these results across various Qwen model scales.

Critical strengths
  1. SGPO retains the outer training loop, rollout sampling, anchor-point partitioning, and episode-based advantage estimation, replacing only the step-wise return estimator. It requires neither a learned critic network nor any additional environment interactions or model evaluations.
Critical weaknesses

1.There is a logical gap between the value derived from the empirical anchor-point model and the true value of the policy. The certainty-equivalent (CE) Bellman system shown in the diagram is solved by averaging over observed transition frequencies, rather than by maximizing over policy actions.

2.In reinforcement learning, the unbiasedness of policy gradients typically serves as a crucial cornerstone for the theoretical convergence of algorithms. In Section 6 (Limitations), the paper explicitly notes that "same-batch value fitting" and "state reweighting through local standardization" preclude the direct application of guarantees for unbiased policy gradients. Because SGPO utilizes empirical values—computed within groups—to normalize and bootstrap trajectories, the resulting "certainty-equivalent" values ​​(derived on-the-fly from the current batch of samples) do not constitute globally unbiased estimates; this represents a clear logical compromise in the theoretical derivation.

Questions for authors

1.In Appendix D, the authors state that anchor keys rely strictly on exact-string matching of environment-defined anchor_obs, which trades coverage against aliasing. Given that text-based or web environments (like ALFWorld and WebShop) often exhibit historical context divergence under the same observation string, how severe is the impact of state aliasing on the certainty-equivalent (CE) Bellman system? Have the authors explored soft or semantic-based matching to mitigate this?

2.In Section 5.3 and Appendix C.4, the offline evaluation demonstrates that Real CE achieves lower MSE. However, the authors appropriately note that a reduction in pooled MSE does not directly establish a reduction in policy-gradient variance. Do the authors have empirical or theoretical evidence from online training to confirm that SGPO actually reduces the variance of the policy gradient compared to the MC endpoint (λ=1\lambda=1)?

3.The default trace parameter λ=0.75\lambda = 0.75 is fixed on a development split (Section 4.2). How sensitive is SGPO's performance to λ\lambda when transferring to environments with significantly different stochasticity or longer horizons? Is there a heuristic rule for choosing λ\lambda without extensive validation splits?

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

This paper proposes State-Graph Policy Optimization (SGPO) for long-horizon agentic reinforcement learning. The method constructs a state-transition graph from multiple rollouts and performs empirical Bellman evaluation to estimate state values. These values are then incorporated into TD(λ) returns to compute step-level advantages. Experiments on ALFWorld and WebShop demonstrate improvements over several group-based RL baselines.

Critical strengths

The paper is reasonably well motivated, and the proposed Bellman-based value estimation provides an alternative to Monte Carlo returns for step-level credit assignment. The experimental results also show consistent improvements over the evaluated baselines.

Critical weaknesses

1. Substantial overlap with prior work and insufficient novelty.

The paper does not discuss Beyond Trajectory-Level Attribution: Graph-Based Credit Assignment for Agentic Reinforcement Learning (GraphGPO, ICML 2026), which is highly relevant to the proposed method. GraphGPO has already established much of the core framework, including constructing state-transition graphs from multiple rollouts, propagating information across trajectories, and computing graph-based step-level advantages.

The main difference appears to be the replacement of graph-distance-based credit assignment with Bellman value estimation and TD(λ). However, to my knowledge, subsequent work building upon GraphGPO has already explored incorporating Bellman values into graph-based credit assignment. This further raises concerns about the novelty of SGPO.

The authors should clearly distinguish their contributions from GraphGPO and its follow-up work, and explain what genuinely new methodological insights SGPO provides.

2. Missing comparison with the most relevant baseline.

Although the paper demonstrates improvements over GiGPO and HGPO, it does not compare against GraphGPO. Without such a comparison, it remains unclear whether the proposed Bellman Value + TD(λ) approach actually improves upon existing graph-distance-based credit assignment. This missing baseline significantly weakens the empirical justification for the proposed method.

Questions for authors
  1. How does SGPO fundamentally differ from GraphGPO (ICML 2026), beyond replacing graph-distance-based credit assignment with Bellman value estimation and TD(λ)? What are the main novel contributions relative to this prior work?

  2. Can the authors provide a direct comparison with GraphGPO under the same experimental settings? In particular, does Bellman-based value estimation consistently outperform graph-distance-based credit assignment on ALFWorld and WebShop?

  3. How does SGPO differ from GraphGPO (ICML 2026) and its subsequent extensions? In particular, given that Bellman value estimation has reportedly been explored in follow-up graph-based credit assignment methods, what is the fundamental novelty of combining empirical Bellman evaluation with TD(λ) in SGPO?

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

SGPO replaces the step-level Monte Carlo return in GiGPO. Transitions within a rollout group are merged into a graph keyed by exact anchor strings, a certainty-equivalent (CE) Bellman system is solved on it, and its values serve as TD(λ) bootstrap targets before anchor-wise normalization. Experiments on ALFWorld and WebShop with Qwen2.5 1.5B and 7B report gains over GiGPO and HGPO.

Critical strengths

S1. The change is a clean drop-in with no critic or extra rollouts, and λ=1 recovers GiGPO exactly.

S2. The mechanism probes and the candid limitations section are above the norm.

Critical weaknesses

W1. [Motivation] The long-horizon variance motivation is asserted and never tested. The paper attributes its gains to reducing Monte Carlo return variance that grows with the remaining horizon, yet the largest gain is on WebShop, where episodes average under six steps and leave almost no horizon for suffix variance to accumulate. The paper's own offline study shows the estimator improving most on ALFWorld, where the online gain is smallest. The step-advantage variance diagnostic defined in the appendix is never reported, and cross-environment comparisons are confounded by baseline headroom. The mechanism also requires verbatim anchor repeats with shared successors, which confines it to templated observations, and the only test outside text environments falls below GiGPO.

W2. [Method] The theoretical contribution is a restatement of classical results. Proposition 1 is the Neumann series for a substochastic matrix, Proposition 2 is CE consistency under a model-irrelevance abstraction (Li et al., 2006), Theorem 1 is TD(1) equals Monte Carlo plus shift invariance of normalization, and Eq. 12 with Appendix A.5 combines the simulation lemma (Kearns and Singh, 2002) with a Bellman-residual bound. Neither source is cited. Every result is a known fact restated in the paper's notation, and the paper itself concedes that it proves neither lower variance nor unbiasedness, so the second claimed contribution does not stand.

W3. [Method] Mixed-bias returns within one comparison group suppress rare successes. The step advantage ranks actions that share an anchor, but SGPO scores them unequally. An action whose successor is also visited by other trajectories has its return shrunk toward the pooled graph value, while an action whose downstream chain is visited by no other trajectory keeps its raw Monte Carlo return, so the shrinkage depends on how often the sampled policy happened to revisit a successor rather than on the action itself. The Appendix C.5 case studies show the consequence. In both groups, the single highest-return trajectory is pulled hardest toward the pooled value, so under sparse reward the estimator weakens the rare success that step-level credit should reward. The step signal therefore no longer tracks action quality, which undermines the claim that SGPO improves credit assignment and leaves the reported gains unexplained by the method's own mechanism.

W4. [Experiments] Gains track signal densification rather than shared-successor evidence. The paper claims that pooling returns at shared successors yields better value estimates, which drive the gains. Its own evidence contradicts this. Offline, the real graph beats Monte Carlo by 0.41 and 0.21 MSE and ranks anchors no better. Online, a randomly rewired graph predicts worse yet keeps a third of the success gain. At λ=0.75, the early-training share of anchor groups with all-zero step advantages falls from 87.5% to 50% on WebShop, so the gain is consistent with merely giving silent groups a nonzero signal. The Zero and Local controls that could settle this run only offline. The graph, the paper's central contribution, is not shown to contribute to the gains.

W5. [Experiments] The reported margins are not established against the right baselines. G2PO (Wang et al., 2026) is discussed in one sentence without empirical comparison, and GraphGPO (Cheng et al., 2026), which likewise merges group rollouts into a state-transition graph for step-level credit, is not mentioned. Whether the Table 1 baselines were re-run is unstated. The in-house Qwen3.5-2B table shrinks the WebShop success margin over GiGPO from 16.5 and 10.9 points to 4.7 and places HGPO below GiGPO, contradicting the HGPO paper. λ is tuned on an unspecified split. The implementation variance is of the same order as the claimed gains, so the main table cannot support the superiority claim.

Questions for authors

Q1. Could you report the step-advantage variance diagnostic defined in Table 5 for λ=0.75 and λ=1, and show how the gain over GiGPO varies with the remaining horizon of a row?

Q2. Could the Zero and Local estimators and a randomly perturbed value control be run online at λ=0.75? Recovering a comparable gain would attribute the improvement to breaking ties in silent groups.

Q3. Were the baseline rows in Table 1 produced under the same codebase and protocol as SGPO, and could a same-protocol comparison with G2PO and GraphGPO be added?

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

Related papers

Discussion (0)

Sign in to comment.