acceptodds
Under review as a conference paper at ICLR 2027

FESGPO: Free-Energy and Structure-Aware Credit Assignment for Multi-Turn Agents

15 views

Abstract

Reinforcement Learning (RL) for multi-turn Large Language Model (LLM) agents often needs to identify which intermediate decisions actually drive task completion from sparse terminal feedback. Existing group-based methods do not fully exploit the probabilities and costs of successful paths across rollouts or the decision structure within trajectories. To bridge this gap, we propose FESGPO, which treats the rollout group of a given task as a finite observation of the policy–environment interaction process. In this view, transition frequency and path length capture the reliability and cost of an action's route to success. From these statistics, FESGPO estimates empirical transition probabilities and aggregates all successful paths in the empirical graph into a statistical-physics free energy. The corresponding Bellman recursion decomposes this free energy into the shortest success distance, the empirical success probability, and the excess path cost. Furthermore, exact repeated transitions, temporal order, and the final outcome enable more precise attribution of terminal credit to specific decisions. FESGPO exploits this structure to redistribute terminal credit, concentrating the training signal on decisions that materially shape subsequent behavior. At Qwen2.5-1.5B, FESGPO improves strict success over the strongest trained baselines by 7.29 percentage points on ALFWorld and 2.87 percentage points on WebShop. It raises nonzero PPO-advantage coverage from 24.07% to 56.68% and surpasses GraphGPO with dynamic sampling on ALFWorld using 16.15% as many rollouts. We verify our main theoretical results in Lean 4. Our implementation is available at https://anonymous.4open.science/r/FESGPO.

Primary area:
reinforcement learning
Keywords:
Large Language Model Agents, Reinforcement Learning, Credit Assignment

Reviews

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

This paper studies the problem that how to assign credit in long horizion agentic tasks. The formulation generally follows GraphGPO (https://arxiv.org/abs/2605.26684), while the authors propose free-energy as the creteria for the credit assignment. Empirically, the proposed method has good performance in ALFWorld and Webshop, illustrating the superior of the proposed credit assignment method.

Critical strengths
  • The proposed method shows very well empirical performance. The proposed method shows very good performance in ALFWorld and Webshop.
  • The proposed structure aware credit refinment is interesting. It shows performance improvement even if it is somehow heuristic.
Critical weaknesses
  • The presentation need to be improved. I highly recommend the author clarify more about the meaning of figure 1 and figure2, it is confusing when I first read the figure. Meanwhile, I would recommend add some illustrative figure in section 4.2 to understand your method.

  • Lack of comparison with standard RL advantage estimation. Since the authors formulate the problem using an empirical state-transition graph, the proposed free-energy credit can be directly interpreted from a standard RL perspective. Specifically, under unit transition costs, the partition function Zβ(s)Z_\beta(s) in Eq. (3) is equivalent to the discounted value function V(s)=E[γT1{success}∣s]V(s)=\mathbb{E}[\gamma^T\mathbf{1}_{\{\mathrm{success}\}} \mid s], where TT is the number of remaining transitions until termination. At the same time, Eq. (4) corresponds to the standard Bellman evaluation equation. I would encourage the authors to clarify this connection and include comparisons.

Questions for authors
  1. Could the author clarify the experimental setup, if I understand correctly, the authors are doing eval on the 128 tasks (might not unique) in seen env in ALFWorld, I am curious about the performance on unseen env, could the authors also report the number in unseen env?

  2. The proposed method didn't show too much improvement in Webshop, is it because of it doesn't have too much same state? Can the author provide some statistics that shows how many state merged in training for webshop if available? More general question here is how to define same state, I believe this question is easy for ALFWorld since the state is clear, but for Webshop and harder tasks, how can we define state in this context, for example, for a general tool calling task, how can we apply this method to the setting?

6 comments

W1: Figures 1 and 2 are unclear, and Section 4.2 lacks an illustration, making the method harder to understand.

We thank the reviewer for the suggestion. In the revised manuscript, we updated the descriptions and captions for Figures 1 and 2 as follows.

Figure 1. Two limitations of current credit assignment. (a) Shortest-distance scoring gives equally distant successor states the same score despite different observed success rates. (b) Trajectory-level credit can reward repeated loop closures in successful rollouts and assigns them zero advantage in all-failure groups with identical rewards.

Figure 2. Overview of FESGPO. Free-energy credit scores successor states using successful-path probabilities and costs, then standardizes these scores among transitions sharing the same source state. Structure-aware refinement adjusts episode credit using repeated loop closures, persistent exits, and rollout outcomes. The two components are combined through a weighted sum for token-level PPO updates.

We also added an illustration to Section 4.2 of the revised manuscript showing repeated loop closures, persistent exit actions, and the corresponding credit adjustments. The figure uses illustrative numerical examples to show how credit changes in each case. The new illustration is available in the anonymous repository.

W2: The connection to standard value functions and Bellman evaluation is insufficiently explained, and comparisons with standard RL advantage estimation methods are missing.

We thank the reviewer for the feedback. We address the value-function interpretation, how our method constructs credit, and the additional comparison with a standard return estimator. In the final manuscript, we will clarify how the partition function relates to standard value functions and Bellman evaluation and include the Monte Carlo (MC) comparison to connect the mathematical interpretation and credit construction to the experimental evidence.

(1) Under unit transition costs, the partition function can be interpreted as the discounted success value of an empirical transition process.

As the reviewer points out, under unit transition costs, Eq. (3) has the following value-function interpretation.

\qquad \gamma=e^{-\beta}.$$ Here, $q_x$ is the empirical transition process constructed from a group of sampled trajectories for the same task. Equation (4) already gives the Bellman recursion for computing this quantity. We will clarify its correspondence to standard value evaluation in reinforcement learning. **Our contribution is to use continuation evidence from the sampled trajectories to construct relative action credit that accounts for both the probabilities and costs of successful continuations.** **(2) FE constructs action credit by jointly accounting for the probabilities and costs of successful continuations across trajectories.** GiGPO uses the return observed after each action, and GraphGPO uses the shortest distance to success in the merged graph. **FE aggregates the transition probabilities and path costs of successful continuations supported by the empirical graph while retaining the effect of failed branches on the success probability.** Compared with per-trajectory returns, shared states allow continuation evidence to propagate across trajectories. Compared with shortest-path scoring, the empirical probabilities and excess costs of the paths also affect action credit. The free-energy formulation follows the framework of Kivimäki et al., already cited in the submission. Its variational view of path distributions provides a theoretical basis for jointly evaluating probabilities and costs. For our empirical success process, **Proposition 1, Eq. (5), and Appendix C.2 of the submission give the following decomposition and its full proof.** $$F_\beta(s)=d_{\mathrm{SP}}(s)-\frac{\log p_+(s)}{\beta}-\frac{\log\eta_\beta(s)}{\beta}.$$ Here, $p_+(s)$ is the empirical success probability, and $\eta_\beta(s)$ captures the discounted contribution of the costs that successful paths incur beyond the minimum successful path cost. This decomposition applies to states from which a successful terminal state is reachable. **It identifies two factors omitted by shortest-path valuation and provides a testable mathematical explanation of how FE changes action credit.**

(3) To assess the effect of this valuation relative to standard sampled returns, we added an ablation that replaces FE with per-trajectory discounted Monte Carlo (MC) returns.

We replaced the FE step-level scores with discounted returns computed from each trajectory, keeping source-state grouping and normalization, episode-level advantages, structure-aware refinement rules, the discount factor, and the training budget fixed. The table also includes the shortest-path ablation reported in Table 2 of the submission.

Step-level valuation (other components held fixed)ALFWorld success rate (%)WebShop success rate (%)
Shortest-path valuation (Table 2 of the submission)94.53 ± 0.7878.13 ± 3.58
Per-trajectory discounted MC (additional ablation)95.57 ± 3.1676.56 ± 3.13
FE valuation (full method)99.22 ± 0.7880.21 ± 3.93

All results use Qwen2.5-1.5B trained for 150 updates. We report the mean and sample standard deviation across the same three evaluation seeds used in the paper. We ran the additional MC ablation on both ALFWorld and WebShop.

On ALFWorld, FE improved the success rate by 3.65 percentage points over the MC ablation. On WebShop, the matched MC ablation achieved a success rate of 76.56 ± 3.13%, compared with 80.21 ± 3.93% for FE. Compared with shortest-path valuation, FE improved success rates by 4.69 and 2.08 percentage points on ALFWorld and WebShop, respectively. These comparisons show that aggregating successful continuations improves task success rates when the other components of the credit assignment framework are held fixed.

Reviewer_MEbuOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes FESGPO, a two-stage credit assignment framework designed for multi-turn large language model agents. The framework integrates a free-energy-based graph credit mechanism—which accounts for both the probability and the cost of successful paths—with a structure-aware optimization mechanism that penalizes redundant cycles while rewarding effective exit paths. Experimental results on ALFWorld and WebShop demonstrate that this approach outperforms existing reinforcement learning baselines for agents.

Critical strengths

S1. The free-energy formulation extends shortest-path-based credit assignment methods by incorporating empirical success probabilities and path costs, and is supported by theoretical analysis. S2. FESGPO achieves performance improvements across two model scales; these findings are further corroborated by ablation studies and separate continuation experiments.

Critical weaknesses

W1. Although FESGPO penalizes repeated loop closures, it cannot distinguish non-repetitive actions when no successful trajectory is observed. Advantage collapse remains unresolved in challenging sparse-reward settings. W2: FESGPO achieves near-saturated performance on ALFWorld (99.22% success), limiting the benchmark's ability to distinguish further improvements. Meanwhile, gains on WebShop are relatively modest, particularly at the 7B scale (+1.30 percentage points). Evaluation on more challenging long-horizon tasks would better demonstrate the method's effectiveness and generalizability.

Questions for authors
  1. Could the authors evaluate FESGPO on more challenging long-horizon benchmarks where existing methods have not yet reached near-saturated performance, like scienceworld, SWE?
  2. How does FESGPO address credit assignment for non-repetitive actions in all-failure rollout groups? Could the authors evaluate its effectiveness in settings with extremely sparse successful trajectories?
3 comments

W1 & Q2: Credit assignment for non-repetitive actions and advantage collapse under extremely sparse rewards.

We thank the reviewer for the suggestion. We address credit signals in groups where all trajectories fail and the ability to distinguish action quality when only a few trajectories succeed. In the revised manuscript, we will include the credit statistics, component ablation, and trajectory diagnostics to clarify the roles of negative supervision in all-failure groups and action credit when successful trajectories are scarce.

(1) In trajectory groups where all trajectories fail and receive identical returns, we penalize unproductive repetition to turn failed experience into a training signal that guides further exploration.

We use no additional reward for non-repetitive actions. When both the FE and episode-level advantages are zero, structural refinement (SC) applies a negative advantage correction to eligible repeated loop closures, making the policy less likely to select those actions. This mechanism uses structural information from failed trajectories to guide the policy toward fewer unproductive repetitions and greater exploration of other behaviors.

Appendix B.1 reports an offline credit diagnostic on discovery rollouts sampled from the frozen Step-150 policy. Using the training implementation to recompute credit, we found that 58 repeated loop-closing positions with zero graph and episode-level advantages received negative corrections, covering 4,740 response tokens. To examine this signal during training, we separately analyzed training batches saved every five updates from update 5 through update 50 in the ALFWorld 1.5B run. Of the 38 all-failure groups, 27 (71.1%) received negative credit from SC alone, covering 654 valid actions.

To assess the contribution of this branch to learning, we compared the full method with a variant that disables the all-failure branch under the same training budget.

MethodALFWorld success rate (%)WebShop success rate (%)
Without the all-failure branch96.09 ± 0.7879.95 ± 3.25
Full FESGPO99.22 ± 0.7880.21 ± 3.93

Retaining this branch improved success rates by 3.13 and 0.26 percentage points, respectively. The credit logs show how negative supervision arises, and the component ablation measures the branch’s contribution to task performance under the given training budget.

(2) To test whether the method can distinguish action quality when successful experience is limited, we analyzed task groups with only a few successful trajectories used to construct the graph.

In the independent continuation experiment on WebShop, we selected task groups in which only 1–3 of the eight trajectories used to construct the graph succeeded and 5–7 failed. We identified the comparison points and actions during graph construction, then froze the policy and graph and restored the same interaction context and remaining budget. We sampled 32 independent continuations per comparison branch and used the final success rate to evaluate action quality.

The table reports the FE comparison at update 50 and the persistent exit comparison at update 100.

ComparisonTarget action continuation success rate (%)Control continuation success rate (%)Tasks / comparisons
Update 50 — FE-preferred action vs. the other action with the same shortest distance to success29.065.635 / 10
Update 100 — Persistent exit action vs. policy-selected first action98.9637.53 / 3

Continuation success rates were 23.44 and 61.46 percentage points higher, respectively. In these task groups, where most trajectories used to construct the graph failed, FE-preferred actions and identified persistent exit actions had higher continuation success rates than their respective controls.

When all trajectories fail, SC uses repeated structure to provide negative supervision. When successful continuations are available, FE uses success probabilities and path costs to distinguish action credit.

W2 & Q1: Effectiveness and generalization on more challenging long-horizon benchmarks.

We thank the reviewer for the suggestion. We conducted additional training and evaluation on ScienceWorld and Search-R1 to assess the method’s performance on interactive science tasks and search tool-use tasks, respectively.

(1) To assess the method’s performance on multistep science tasks, we trained and evaluated it on ScienceWorld.

ScienceWorld [3] is a text-based interactive environment for scientific experiments. Its tasks cover topics such as changes in states of matter, electrical circuits, and chemical and biological processes. The agent must locate and manipulate objects, use experimental equipment, observe the results, and complete a scientific objective through a sequence of interactions.

We trained both FESGPO and GraphGPO with Qwen2.5-1.5B for 150 updates and evaluated the fixed checkpoint at update 150 with an inference temperature of 0.4. We used a strict success criterion that required the environment to mark the task as complete and the native task score to reach 100.

For each of the three evaluation seeds, we randomly sampled 128 tasks from the ScienceWorld evaluation task pool. We then evaluated FESGPO and GraphGPO on the same sampled tasks within each seed. The table reports the mean and sample standard deviation of the strict success rate across these seeds. FESGPO achieved a mean strict success rate of 45.05%, 4.43 percentage points higher than GraphGPO, demonstrating its ability to generalize to these multistep science tasks and outperform GraphGPO on the evaluated subset.

FESGPO success rate (%)GraphGPO success rate (%)Difference (pp)
46.09 (59/128)40.63 (52/128)5.47
43.75 (56/128)39.84 (51/128)3.91
45.31 (58/128)41.41 (53/128)3.91
45.05 ± 1.1940.63 ± 0.784.43

(2) To assess the method’s applicability to other interactive tasks, we extended it to the Search-R1 search tool-use task.

We trained both GraphGPO and FESGPO with Qwen2.5-3B for 200 updates using five trajectories per group and evaluated them on the same 3,125 questions across seven datasets. We computed the exact match (EM) rate for each dataset and took the macro-average across all seven. FESGPO achieved a macro-average EM 1.31 percentage points higher than GraphGPO, extending the experimental evidence to a retrieval tool-use environment and the 3B model in the Qwen2.5 family.

MethodMacro-average EM across seven datasets (%)
GraphGPO37.00
FESGPO38.31

[1] Hashemzadeh, Maryam, et al. "Sub-goal distillation: A method to improve small language agents." arXiv preprint arXiv:2405.02749 (2024).

[2] Jin, Bowen, et al. "Search-r1: Training llms to reason and leverage search engines with reinforcement learning." arXiv preprint arXiv:2503.09516 (2025).

[3] Wang, Ruoyao, et al. "Scienceworld: Is your agent smarter than a 5th grader?." Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing. 2022.

Thank you for your constructive feedback. We have provided detailed responses and added the following experiments and analyses:

  • Credit signals under sparse rewards. We analyzed SC-only negative credit in all-failure groups and evaluated the contribution of this branch through a component ablation.
  • Independent continuation tests. On WebShop, we tested FE-preferred actions and persistent exit actions in groups where only 1–3 of eight trajectories succeeded.
  • Additional benchmarks. We trained and evaluated FESGPO on ScienceWorld and Search-R1, obtaining improvements over GraphGPO of 4.43 percentage points in strict success rate and 1.31 percentage points in macro-average EM, respectively.

With two days remaining before the discussion deadline, we would greatly appreciate hearing whether these responses and additional results address your concerns. If any questions remain, please let us know so we can provide further clarification before the deadline.

Thank you again for your time and consideration!

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

This paper studies step-level credit assignment for multi-turn LLM agents. Existing group-based methods either collapse future success into a single graph statistic, such as shortest-path distance, or broadcast a terminal outcome uniformly across a trajectory, including to repeated loop-closing actions. FESGPO computes two signals from the same on-policy group. Free-energy credit aggregates empirical successful paths into a partition function and converts it into a source-normalized successor advantage. Structure-aware refinement then penalizes repeated closures in all-failure groups and, in mixed groups, moves positive episode credit from those closures to later persistent exits. Combined advantages are used in a clipped PPO update. On Qwen2.5-1.5B and 7B, FESGPO reports 99.22% ALFWorld strict success and modest WebShop gains over GraphGPO and related baselines.

Critical strengths
  • Clear motivation. Shortest-path graph credit ignores how much support a route to success has. The equal-distance example (success probability 1 vs. 1/3) makes this intuitive, and Eqs. (32)/(39) state it formally.
  • This method has low overhead that needs no extra models and no extra environment interaction.
  • Reasonable experimental coverage. The paper uses two model scales and compares against recent methods, including GiGPO, GraphGPO, HGPO, and BEACON.
Critical weaknesses
  • Under the “free energy” framing, the core quantity is a discounted success probability on an empirical Markov chain, so the novelty is overstated.
  • The method relies on exact state matching and discrete admissible-action sets. ALFWorld and WebShop both satisfy these conditions, and both are close to saturated. In environments where observations rarely repeat, such as WebArena, SWE tasks, search, or tool use, the graph breaks into disjoint chains. FE then reduces to a per-trajectory discounted return, and repeated-closure detection rarely triggers.
  • Training runs for only 150 steps. In Fig. 4, some baselines do not appear to have converged, so the advantage may reflect faster convergence rather than better final performance.
  • PPO and RLOO numbers are copied from the GraphGPO paper, while the other baselines are reproduced. Please confirm that the settings match exactly.
  • The only real difference between FE and GiGPO-style discounted Monte Carlo returns is path stitching after merging states across trajectories. Two additions are needed: (1) An ablation that uses each trajectory’s own discounted return, standardized within the same source-state groups, with everything else unchanged. (2) Graph statistics, such as the fraction of merged states, the fraction of source states with out-degree > 1, and the fraction of stitched successful paths that do not appear in any single rollout.
Questions for authors

See the weakness.

12 comments

W1: The core free-energy quantity can be interpreted as a discounted success probability on an empirical Markov chain, so the method’s novelty is overstated.

We thank the reviewer for the feedback. Our contribution is to use evidence of successful continuations from multiple trajectories within the same task group to construct action credit that accounts for both success probability and path cost, and to use this credit for policy training. We explain the theoretical basis, the differences from prior methods, and the experimental evidence for this contribution below. In the revision, we will clarify that our method builds on the classical free-energy framework to construct action credit from trajectories within a task group. We will also present matched comparisons with per-trajectory returns and shortest-path valuation to evaluate its effect.

(1) Relationship between free energy and discounted success value

Under unit transition costs, the partition function can indeed be interpreted as a discounted success value on an empirical Markov chain. The original manuscript cites the free-energy framework of Kivimäki et al. (2014). Building on this framework, we construct an empirical transition graph from multiple rollouts collected by the current policy on the same task, convert evidence of successful continuations across trajectories into relative action credit, and use that credit for policy updates.

Proposition 1 of the original manuscript further characterizes the information captured by this valuation.

$F_\beta(s) = d_{\mathrm{SP}}(s) - \frac{\log p_+(s)}{\beta} - \frac{\log \eta_\beta(s)}{\beta}. $

Here, dSP(s)d_{\mathrm{SP}}(s) is the cost of the shortest successful path, p+(s)p_+(s) is the success probability on the empirical graph, and ηβ(s)\eta_\beta(s) characterizes the distribution of costs in excess of the shortest-path cost, conditional on success. FE thus uses the shortest successful path cost, the success probability, and the costs of other successful continuations to compute action credit.

(2) Differences from prior agent RL methods

The methods differ in which trajectory evidence they use to estimate credit and how they aggregate it. FESGPO constructs an empirical transition kernel from transition frequencies within each task group, retains the probability mass of failed branches, and aggregates successful continuations from multiple trajectories through shared successor states. This allows an action to receive credit based on continuation evidence from other trajectories and distinguishes actions that have the same shortest distance to success but differ in success probability and continuation cost distributions. This contribution is reflected in how we construct the graph from trajectories within each task group, aggregate probabilities and costs, and compute relative credit among actions from the same source state.

MethodContinuation evidence used for action credit
GiGPOThe realized suffix return of the trajectory in which the action occurs
GraphGPOThe shortest successful path in the merged graph
FESGPOJoint valuation of successful continuations with different costs under empirical transition probabilities estimated within the same task group

(3) Ablations that replace the valuation while holding other components fixed

To test how this aggregation affects learning, we held normalization across actions from the same source state, the structural refinement (SC) rules, and the training budget fixed. We replaced FE with shortest-path valuation to assess the additional value of success probabilities and path cost distributions, and with per-trajectory discounted Monte Carlo (MC) returns to assess the value of joint graph-based valuation relative to realized returns from individual trajectories.

Step-level valuationALFWorld success rate (%)WebShop success rate (%)
Shortest-path valuation with SC retained (original ablation)94.53 ± 0.7878.13 ± 3.58
Per-trajectory MC with SC retained (new ablation)95.57 ± 3.1676.56 ± 3.13
FE valuation (full FESGPO)99.22 ± 0.7880.21 ± 3.93

Compared with per-trajectory MC, FE improved the success rate by approximately 3.65 percentage points in both environments. Compared with shortest-path valuation, it improved the success rate by 4.69 and 2.08 percentage points on ALFWorld and WebShop, respectively. Together, these comparisons show that sharing continuation evidence within task groups and aggregating success probabilities and path costs provides additional information for action credit.

To verify that successful paths combining evidence across trajectories occur during training, we also examined 480 training graphs from each environment. In ALFWorld, 324 graphs contained successful paths that required combining edges from multiple rollouts, as did 225 graphs in WebShop. See our response to W5 for the definition and statistics. These counts establish that the training graphs contain cross-trajectory evidence that joint valuation can use. The valuation ablations assess its effect on learning.

[1] Kivimäki, Ilkka, Masashi Shimbo, and Marco Saerens. "Developments in the theory of randomized shortest paths with a comparison of graph node distances." Physica A: Statistical Mechanics and its Applications 393 (2014): 600-616.

[2] Cheng, Xin, et al. "Beyond Trajectory-Level Attribution: Graph-Based Credit Assignment for Agentic Reinforcement Learning." arXiv preprint arXiv:2605.26684 (2026).

[3] Feng, Lang, et al. "Group-in-group policy optimization for llm agent training." Advances in Neural Information Processing Systems 38 (2025): 46375-46408.

W2: Reliance on exact state matching and predefined candidate actions may limit generalization, as may the scarcity of repeated loops that can inform credit assignment in other tasks.

We thank the reviewer for raising these concerns. We added experiments on noisy WebShop and Search-R1 to examine state aggregation when observation texts differ and credit assignment without a predefined list of candidate actions, respectively.

SC uses detected loops to refine action-level credit and can work with approaches beyond exact observation matching, such as embedding similarity to match states or an LLM judge to identify unproductive revisits. To examine how often unproductive revisits occur in more complex environments, we analyzed trajectories from ScienceWorld and DiscoveryWorld. We used an LLM judge to assess task progress and information gain, allowing it to identify unproductive returns to states that are equivalent for the task even when observation texts or action forms differ.

(1) To test whether cross-trajectory sharing can be preserved when observation texts vary, we used similarity-based state aggregation on noisy WebShop.

We used GPT-6-Astra to append two random advertisements to each observation with a probability of 60%. Both the policy input and graph construction used the noisy observations. We merged states only within the same task and required identical visible product IDs, buttons, and selected options, as well as a cosine similarity greater than 0.95 between the observation embeddings. This rule uses key state information to constrain merging and text similarity to accommodate observation differences caused by irrelevant advertisements.

GraphGPO and FESGPO used the same noise settings and state aggregation rule. Both used Qwen2.5-1.5B with eight trajectories per group and were trained for 150 updates. FESGPO achieved a success rate 3.39 percentage points higher than GraphGPO, indicating that its credit assignment benefits can persist with similarity-based state aggregation when observation texts differ.

MethodNoisy WebShop success rate (%)
GraphGPO78.13 ± 3.58
FESGPO81.51 ± 2.39

To further examine how similarity matching affects cross-trajectory sharing, we held FESGPO’s sampled training trajectories fixed and rebuilt the graphs using exact matching and the similarity-based matching rule described above. Across all 150 training batches, shared-visit coverage increased from 27.13% to 73.46%. This metric measures the proportion of action visits whose source state is supported by at least two distinct trajectories.

These results show task performance under noisy observations and how the matching rule affects cross-trajectory sharing. Similarity-based state aggregation preserves cross-trajectory sharing when observation texts differ and supports FESGPO’s graph-based credit computation.

(2) To assess applicability in the absence of a predefined candidate action list, we ran a search tool-use experiment on Search-R1.

In Search-R1, the model freely generates search queries and final answers, and the environment provides no enumerated list of available actions. We construct the empirical graph from the sampled text actions and their observed state transitions, then compute training credit on that graph.

We trained both GraphGPO and FESGPO with Qwen2.5-3B for 200 updates using five trajectories per group and evaluated them on the same 3,125 questions across seven datasets. We computed the exact match (EM) rate for each dataset and took the macro-average across all seven. FESGPO achieved a macro-average EM 1.31 percentage points higher than GraphGPO, extending the experimental evidence to a retrieval tool-use environment and the 3B model in the Qwen2.5 family.

MethodMacro-average EM across seven datasets (%)
GraphGPO37.00
FESGPO38.31
Reviewer_TZgsOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

FESGPO improves credit assignment for multi-turn LLM agents by building a graph from their sampled trajectories. It combines a free-energy estimate of successful continuation with structural rules that penalize repeated loops and redirect credit toward actions that escape them. Experiments with two Qwen2.5 model sizes show improvements on ALFWorld and WebShop, with particularly strong results on ALFWorld.

Critical strengths

Thank you for submitting your paper. Overall, the motivation is clear, and I appreciated the substantial amount of detail. The strengths are as follows.

  • Well-motivated approach to graph-based credit assignment: I particularly liked the argument for going beyond shortest-path distance. A short route to success does not necessarily represent a reliable continuation, so incorporating empirical transition probabilities and continuation costs is a sensible extension. The free-energy decomposition makes this distinction precise and connects the proposed valuation to the shortest-path baseline. The structural refinement also addresses a practical limitation: groups containing only failed trajectories can still contain recognizable, repeated mistakes. Together, these components provide a compelling motivation for extracting more useful supervision from the same rollouts.
  • Promising results supported by meaningful diagnostic experiments: The ALFWorld improvements are substantial: at 1.5B, success increases from 91.93% for GraphGPO to 99.22%, and the component ablations support contributions from both stages. I also appreciated the independent continuation experiments in Appendix B. These go beyond reporting benchmark scores and directly examine whether preferred actions and persistent exits lead to better continuations. Finally, the measured runtime difference of approximately 0.75% relative to the matched GraphGPO run supports the practical usefulness of the approach.

There are also other points that I appreciated:

  • Implementation details: The appendix carefully specifies graph construction, matching rules, exceptional cases, and the actual optimization procedure.
  • Compute reporting: Providing rollout counts, GPU-hours, and a timing breakdown makes the efficiency claims easier to assess.
Critical weaknesses

Despite the aforementioned strengths, there is one key weakness that limits how confidently I can interpret the results and the proposed credit assignment.

The graph representation does not fully match the policy’s decision context: Appendix F.2 explains that graph nodes merge identical serialized environment states, while the policy also receives recent observation–action history and the current step count. Consequently, one graph node can combine occurrences with different policy histories and remaining interaction budgets. The resulting empirical transition probabilities and recombined paths need not accurately describe continuation quality from each individual occurrence. The theoretical results remain valid for the constructed graph, but they do not by themselves establish that this abstraction gives reliable behavioral credit. I appreciate the continuation experiments, although these use a late ALFWorld checkpoint and therefore provide limited evidence about this issue throughout training. An ablation incorporating history or remaining budget into the graph representation, together with measurements of the resulting credit coverage, would help establish how consequential this approximation is.

There are some other points that I would like to phrase as questions below.

Questions for authors

As mentioned above, there are some non-critical but nevertheless important points that I would like to phrase as questions to the authors.

1) Evaluation splits and parameter selection: Could you specify the exact training and evaluation splits, how the 128 evaluation episodes per seed are selected, and whether all methods use identical evaluation instances? Appendix B explicitly uses ALFWorld’s valid_seen split, but I could not clearly identify the corresponding split for the main results. Also, Figure 3 reports test performance across different discount values. Were the default values selected using a separate validation set?

2) Simpler structural controls: Could you compare the structural refinement with a simpler repeated-loop penalty and a control that redistributes the same amount of positive credit to other eligible actions? The current ablations show that the components can help, especially on ALFWorld, but these controls would clarify how much benefit comes specifically from identifying persistent exits rather than from discouraging repetition or changing the distribution of supervision.

3) Mechanism checks throughout training: I appreciated Appendix B’s independent continuation experiments. Could you repeat a smaller version at an early or intermediate checkpoint, and ideally on WebShop? The final ALFWorld policy is already highly successful, while the proposed credit assignment also needs to work when the graph is estimated from mostly unsuccessful rollouts.

4) Dynamic-sampling comparison: Appendix F.3 describes filtering groups according to whether their episode returns are identical. However, graph-based advantages can still differ within such groups. Would the large rollout-efficiency advantage over GraphGPO with dynamic sampling persist if filtering considered whether the actual graph-based advantages were informative? This would help clarify how much of the observed difference depends on the sampling rule.

5) Baseline provenance: Appendix F.3 states that the PPO and RLOO results are adopted from GraphGPO. Could you mark these rows explicitly in Table 1 and clarify whether their observation formats, task splits, and evaluation settings match yours? I appreciate that the closest graph-based baseline is rerun, so this concern primarily affects the interpretation of the broader comparison.

6) Generalizability: Both model sizes belong to the Qwen2.5 family, and the method relies on exact state matching within relatively small rollout groups. Could you discuss or measure its sensitivity to group size and less frequent state repetition? This would help identify when the proposed method is likely to remain useful beyond the evaluated settings.

I would appreciate it if you could address these points!

12 comments

W1: State merging ignores history and the remaining budget, and the reliability of action credit has yet to be adequately validated.

We thank the reviewer for the suggestion. We added a training ablation on state representations and an offline comparison using fixed trajectories to examine whether stricter context matching improves learning and how it affects the credit signal, respectively. The results show that, under the current sampling budget, requiring exact matches on history or the remaining budget reduces cross-trajectory sharing and nonzero Free Energy (FE) advantage coverage, with no improvement in final task success rates.

(1) To examine whether history and the remaining budget should be included in FE state matching, we conducted a training ablation on state representations.

We compared three FE state representations on ALFWorld with Qwen2.5-1.5B:

  • the original environment state
  • the environment state augmented with the two most recent observation–action pairs
  • the environment state augmented with the exact number of remaining interaction steps

Each graph was constructed within a single task group. For nonterminal states, the original representation requires only that the environment states match. The history-augmented representation additionally requires that the contents and order of the two most recent observation–action pairs match, while the budget-augmented representation additionally requires that the number of remaining interaction steps match. The two ablations examine the effects of history and the remaining budget on state merging, respectively. For example, visits to the same environment state with different numbers of remaining steps are assigned to different nodes under the budget-augmented representation.

Both new ablations started from the pretrained model and ran for 150 updates, with 8 trajectories sampled per task group and all other training settings following the main experiment. The policy input retains the two most recent observation–action pairs in all settings. The ablations change only FE state matching and credit computation. Both ablations use the original SC state identification rule and computation formula.

FE state representationShared visits (%)FE coverage (%)Success rate (%)
Original environment state74.0043.0699.22 ± 0.78
+ Two most recent observation–action pairs19.808.5586.98 ± 1.97
+ Remaining interaction steps22.477.8088.02 ± 3.25

The shared-visit rate is the proportion of valid action positions whose source state is supported by at least two distinct trajectories within the same task group. FE coverage is the proportion of valid actions with a nonzero FE advantage, defined as an absolute advantage greater than 10−610^{-6}. Both metrics are aggregated over all valid actions in the 30 batches saved at updates 5, 10, …, 150 in each training run. Success rates are reported as the mean and standard deviation across three evaluation seeds, with the new ablations evaluated at the fixed checkpoint after update 150.

Under this configuration and a sampling budget of eight trajectories per task, requiring exact matches on either history or the remaining budget reduced both cross-trajectory sharing and nonzero FE advantage coverage, with no improvement in final task success rates.

(2) To distinguish the effect of the matching rule from that of the sampled trajectories, we conducted an offline comparison that held the trajectories fixed and varied only the matching rule.

For each of the history and budget ablations, we used the 30 saved batches described above. We held all actions, state transitions, realized rewards, and success or failure outcomes fixed, then rebuilt the graphs and recomputed FE advantages using each of the 3 matching rules: original, history, and budget. We used the same set of valid actions as the denominator for all three computations. The table below reports nonzero FE advantage coverage, including the results recomputed with the matching rule used during training.

Trajectory sourceOriginal matching (%)History matching (%)Budget matching (%)
History ablation35.518.556.84
Budget ablation39.4811.017.80

Each row uses exactly the same trajectories and varies only the matching rule used for credit computation. For both trajectory sources, requiring an exact match on history or the remaining budget reduces nonzero FE advantage coverage. A finer state partition separates transitions and subsequent paths that could previously be shared and reduces the size of the groups of actions from the same source state used to normalize relative advantages. For example, when an action is assigned to a group containing only itself, subtracting the group mean from its score yields zero. Even if the action contributes to the task, it receives zero relative advantage within that group.

(3) Reliability of action credit

The training ablation tests whether stricter context matching improves learning, and the fixed-trajectory comparison isolates the effect of the matching rule on the credit signal. Under the current ALFWorld configuration and a sampling budget of eight trajectories per task, original state matching preserves more cross-trajectory sharing and nonzero FE signals and achieves higher task success rates in the training comparison. Requiring exact matches on history or the remaining budget partitions shareable experience into smaller action groups, reducing the coverage of the relative credit signal.

These results support using the original environment state for FE matching under the current configuration. We will add the experimental designs, metric definitions, and full comparisons to the revised manuscript to explain how the granularity of state matching affects experience sharing, credit signals, and final task performance.

Q1: Details on data splits, the selection and consistency of evaluation instances, and parameter choices.

We thank the reviewer for the detailed suggestions on the evaluation protocol and parameter settings. The results for the trained methods and their ablations that we evaluate ourselves in the main experiments follow the GraphGPO evaluation protocol, including the data splits, task sampling rules, number of evaluation episodes, and metric definitions. Appendix B uses a separate mechanism-analysis protocol with a frozen Step-150 policy, a sampling temperature of 1.0, eight discovery rollouts for each of 140 ALFWorld tasks, and 32 continuations per comparison branch. In the final manuscript, we will add these evaluation details, the sources of the reported results, and the rationale for the default parameter settings to the experimental setup.

(1) ALFWorld and WebShop data splits and evaluation sampling

For both benchmarks, the trained methods and their ablations that we evaluate ourselves follow GraphGPO’s evaluation protocol, with 128 episodes per evaluation seed.

  • ALFWorld. We train on train and evaluate on valid_seen, which contains 140 task entries. Each parallel environment uses a sub-seed derived from the evaluation seed to randomize its task order. Task selection is performed independently across parallel environments, so the 128 evaluation episodes may include repeated task instances. The episode count therefore does not necessarily equal the number of unique tasks.
  • WebShop. Task IDs 0–499 form a fixed test pool, and IDs 500 onward are used for training. For each seed, we sample 128 distinct test tasks without replacement and run one episode per task. We compute the mean native task score and strict success rate for each seed and report the mean and standard deviation across three seeds.

(2) Evaluation consistency across methods and sources of results

For each evaluation seed, all methods and ablations that we evaluate ourselves in the main experiments use the same task IDs in the same order, with 128 episodes per seed. The paired supplementary comparisons also use identical evaluation instances. We report the mean and sample standard deviation across three evaluation seeds. The PPO and RLOO results are taken from GraphGPO, and we will explicitly indicate their source in the main table.

(3) Rationale for the default parameters and sensitivity analysis

The default discount factors were fixed heuristically before the sensitivity evaluation in Figure 3 (now Figure 4); no separate validation set was used to select them. We chose γ=0.2\gamma=0.2 for ALFWorld’s 50-step interaction limit and γ=0.1\gamma=0.1 for WebShop’s 15-step limit, allowing relatively more weight on longer successful paths in ALFWorld. Figure 4 reports a subsequent sensitivity analysis around these defaults.

Comments on the paper

2 comments

Dear Area Chair and Reviewers,

Thank you again for reviewing our paper and for your constructive feedback. We responded to your comments point by point and added the following experiments and analyses:

  • State matching and cross-trajectory sharing. We tested whether adding recent interaction history or the remaining step budget to the state representation improves learning, and used fixed trajectories to isolate how each matching rule affects credit coverage. We also measured how often successful paths in the training graphs require transitions from multiple rollouts.
  • Credit assignment controls. We compared free-energy valuation with per-trajectory Monte Carlo returns and shortest-path scoring. We also compared exit-aware refinement with loop penalties alone and random redistribution of the same credit mass, and examined when the all-failure rule supplies a training signal.
  • Independent continuations on WebShop. At six training checkpoints, we sampled new continuations to test free-energy action rankings and persistent exits, including cases where only one to three of the eight trajectories used to build the graph succeeded.
  • Training budget and sampling efficiency. We extended the ALFWorld comparison to 200 updates at both model sizes, tested sensitivity to rollout group size, and compared rollout counts, GPU-hours, and task success under reward-based and advantage-aware dynamic sampling.
  • Robustness and generalization. We tested similarity-based state aggregation under noisy WebShop observations, evaluated on unseen ALFWorld tasks, and trained and evaluated FESGPO on ScienceWorld and Search-R1. Search-R1 tests credit assignment when the model generates actions without a predefined candidate list.

We also clarified the connection between free-energy valuation and discounted success, documented the evaluation protocol and the source of the PPO and RLOO results, and revised the method figures. All manuscript changes are marked in blue.

With three days remaining before the discussion deadline, we would appreciate hearing whether the responses and revisions address your concerns. If any questions remain, please let us know in the discussion thread so we can respond before the deadline.

Thank you again for your time and feedback!

AuthorsOpenReview ↗

Final Summary of Contributions and Rebuttal Responses

Dear Area Chair and All Reviewers,

Greetings! We sincerely thank the reviewers for their time and thoughtful feedback.

We would like to take this opportunity to clarify and highlight our contributions. In this paper, we study action-level credit assignment for multi-turn agents under sparse terminal rewards. Existing credit-assignment methods face two limitations: shortest-path valuation can overlook differences in success probability and downstream cost, while propagating terminal outcomes across a trajectory can reward repeated loops in successful trajectories or leave them indistinguishable in all-failure groups. To address these two problems, we propose FESGPO, with the following contributions:

  • Free-energy credit (FE) merges trajectories from each task group into an empirical transition graph and evaluates actions using the probabilities and costs of successful continuations, including the effect of failed branches. It can therefore distinguish actions with the same shortest distance to success.
  • Structure-aware refinement (SC) adjusts credit using repeated transitions, action order, and trajectory outcomes. It penalizes eligible repeated loop closures in all-failure groups. In mixed-outcome groups, it transfers positive credit from repeated closures to later persistent exits in successful trajectories and removes conflicting negative credit from matching exit transitions in failed trajectories. This directs the training signal more closely toward decisions that help the agent escape loops.
  • Training performance and efficiency. With Qwen2.5-1.5B, FESGPO improves strict success rates over the strongest trained baselines by 7.29 and 2.87 percentage points on ALFWorld and WebShop, respectively. On ALFWorld, compared with GraphGPO, FESGPO samples 40.94% fewer trajectories. At the shared checkpoint of update 95, it also uses 37.42% fewer GPU-hours.

During the rebuttal discussion, we received further feedback from the reviewers. Reviewer QnK7 indicated that their main concern had been addressed and raised their overall score from 2 to 3. Reviewer TZgs thanked us for the detailed response and maintained their positive score. We summarize the main concerns and our responses below:

  1. Evidence for FE’s cross-trajectory valuation. To test the value of aggregating successful continuations across trajectories, we replaced FE with per-trajectory discounted Monte Carlo returns or shortest-path valuation while holding other components fixed. FE improved success by 3.65 percentage points over Monte Carlo returns on both ALFWorld and WebShop, and by 4.69 and 2.08 points over shortest-path valuation, respectively. Training-graph statistics also show that cross-trajectory stitched paths contribute to FE’s path weight. (Reviewer QnK7, nVLM)

  2. Validation of action-level credit. We selected actions using graph-construction rollouts, then evaluated them with independent continuations. In pooled WebShop comparisons, FE-preferred actions had 4.68 percentage points higher continuation success than equal-distance controls; the tested persistent exits also outperformed their controls. Full SC further outperformed loop penalties alone and random redistribution of the same positive credit. (Reviewer TZgs, MEbu)

  3. Sparse rewards, longer training, and sampling efficiency. SC assigns negative credit to eligible repetitions even when FE and trajectory-level advantages vanish in all-failure groups; removing this branch lowers ALFWorld success by 3.13 percentage points. FESGPO remained ahead of GraphGPO at 200 updates for both 1.5B and 7B models. An advantage-aware dynamic-sampling control narrowed the efficiency gap, but FESGPO still used 44.77% fewer trajectories and 37.42% fewer GPU-hours through update 95. (Reviewer TZgs, QnK7, MEbu)

  4. Applicability across state representations and tasks. To test whether the method works when observation text varies, we added irrelevant advertisements to WebShop observations and merged states with observation similarity. FESGPO achieved 81.51% success, compared with 78.13% for GraphGPO. On ScienceWorld’s multi-step science tasks and Search-R1’s search tasks, FESGPO achieved 45.05% strict success and 38.31% macro-average EM, exceeding GraphGPO by 4.43 and 1.31 percentage points, respectively. (Reviewer TZgs, Reviewer QnK7, MEbu, nVLM)

Together, we believe FESGPO is well aligned with the ICLR community’s interest in reinforcement learning methods. By deriving more discriminative action-level credit from existing rollouts, our work can contribute to research and practice on credit assignment under sparse rewards, multi-turn agent learning, and sample-efficient training.

We thank the reviewers again for their constructive feedback, which helped us strengthen the experiments and presentation.

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.