acceptodds
Under review as a conference paper at ICLR 2027

Cross-Rollout Bellman Closure for Long-Horizon Agentic Reinforcement Learning

16 views

Abstract

Group-based reinforcement learning such as GRPO has become a standard recipe for post-training LLM agents, replacing a learned critic with relative comparison among rollouts sampled for each task. In long-horizon settings, these rollouts revisit shared anchor states, offering cross-rollout evidence for step-level credit. Ideally, step-level credit should incorporate evidence beyond the realized suffixes observed at an anchor while aggregating alternative continuations according to their empirical frequencies. Existing estimators capture only one of these properties: visit-local averaging pools realized suffix returns at shared anchors and respects observed frequencies, but does not recursively propagate evidence across rollouts, whereas shortest-path estimators have global reach but allow a rarely observed route to dominate an anchor's value. Instead, we introduce a Cross-Rollout Bellman Closure (CRBC) method, which merges each rollout group into a finite empirical process with absorbing success and failure boundaries and evaluates its behavior-policy Bellman fixed point with one linear solve. This fixed point uses the same empirical action and transition frequencies to propagate evidence through shared anchors and aggregate alternative continuations. Backing up the resulting state values through observed transitions yields action values, whose gain over the corresponding state value provides step-level credit. A corresponding finite-depth family recovers visit-local return averaging at zero depth and converges to the exact closure as depth increases. The normalized closure credit is combined with the trajectory-level group advantage for policy optimization, without additional environment rollouts. Across ALFWorld, WebShop, and Sokoban benchmarks with multiple model scales, CRBC consistently improves final performance and learning efficiency. For example, CRBC outperforms the strongest baseline by 5.59 percentage points on ALFWorld with Qwen2.5-1.5B-Instruct, achieving a new state-of-the-art performance.

Primary area:
reinforcement learning
Keywords:
Reinforcement Learning, Agentic RL, Large Language Models, Group-based RL

Reviews

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

This paper proposes Cross-Rollout Bellman Closure (CRBC), a step-level credit assignment method for long-horizon agentic reinforcement learning. CRBC constructs an empirical transition model from shared states across rollouts and solves a Bellman fixed point to estimate state and action values. The resulting step-level advantages are combined with trajectory-level advantages for policy optimization.

Critical strengths
  1. Strong empirical results. The proposed method consistently outperforms existing baselines across multiple benchmarks and model scales, demonstrating clear improvements in both task performance and training efficiency.

  2. Well-motivated methodology. The paper clearly identifies limitations of existing state-based credit assignment methods, particularly regarding cross-rollout information propagation and the aggregation of alternative continuations. The proposed Bellman closure provides a principled and intuitive solution to these limitations.

Critical weaknesses
  1. Limited benchmark difficulty. Several existing methods already achieve relatively high success rates on the evaluated benchmarks, raising concerns about potential performance saturation. More challenging environments would provide stronger evidence of the method's effectiveness.

  2. Limited applicability to open-ended environments. The method relies on identifying and matching shared states across rollouts. While this is feasible in the evaluated environments, defining reliable states can be substantially more difficult in realistic scenarios such as computer use and software engineering, potentially limiting its general applicability.

Questions for authors
  1. Benchmark difficulty: Since several baselines already achieve high performance on the evaluated tasks, have the authors considered evaluating CRBC on more challenging long-horizon agent benchmarks to further demonstrate its effectiveness?

  2. Generalization to open-ended environments: How could the proposed graph-based framework be extended to environments where explicit state representations are unavailable or difficult to define, such as computer use or software engineering? Could learned state abstractions or semantic state matching provide a feasible extension?

  3. Missing baseline: In Table 1, the Qwen2.5-7B-Instruct experiments appear to omit HGPO, although it is included in the 1.5B comparison. Could the authors clarify the reason for this omission and, if possible, provide the corresponding results?

5 comments
AuthorsOpenReview ↗

Response to Q1/W1

Response

We thank the reviewer for the careful review and for recognizing CRBC’s empirical performance and methodological motivation. In response to the questions, we have added Search-R1 multi-turn retrieval-augmented question-answering experiments, discussed a path for extending CRBC to open-ended environments, and completed the missing HGPO baseline experiments with the 7B model. We address each question below, and the corresponding additions have been incorporated into the revised manuscript. The code will be released after the final decisions are announced.

Q1/W1: Experiments on More Challenging Retrieval-Augmented Question Answering

Thank you for the suggestion. We have added Search-R1 multi-turn retrieval-augmented question-answering experiments [1] to evaluate the model’s ability to use external evidence to answer factual and multi-hop questions. We use Qwen2.5-1.5B-Instruct, trained on a mixture of NQ [2] and HotpotQA [3], and compare GRPO, GiGPO, GraphGPO, and CRBC, consistently reporting results after 100 training updates. Evaluation covers NQ [2], TriviaQA [4], PopQA [5], HotpotQA [3], 2WikiMultiHopQA [6], MuSiQue [7], and Bamboogle [8]. We select a fixed set of 128 questions from each of the first six datasets and retain all 125 Bamboogle questions, yielding 893 questions shared across all methods. Apart from method-specific state grouping, credit computation, and associated parameters, model initialization, data, prompts, the retriever, question-sampling budgets, and shared optimization settings are held fixed.

As shown below, CRBC achieves an overall exact-match (EM) rate of 35.83%, compared with 25.08% for GRPO, 28.00% for GiGPO, and 29.23% for GraphGPO, and achieves the highest EM on six of the seven evaluation subsets. These additional experiments extend our evaluation to a challenging agentic QA setting involving multiple rounds of retrieval and evidence integration. Under the current model and training budget, all methods retain substantial room for improvement, while CRBC achieves the highest overall accuracy, showing that its gains also hold on tasks that remain far from performance saturation. We have added the benchmark setup and results to Appendix D.2 of the revised manuscript.

Evaluation subsetQuestionsGRPOGiGPOGraphGPOCRBC
NQ12839.06%38.28%42.19%50.00%
TriviaQA12845.31%50.00%53.13%58.59%
PopQA12821.88%25.00%25.00%43.75%
HotpotQA12821.88%26.56%27.34%33.59%
2WikiMultiHopQA12819.53%28.13%28.13%26.56%
MuSiQue1286.25%7.03%6.25%10.16%
Bamboogle12521.60%20.80%22.40%28.00%
Overall89325.08%28.00%29.23%35.83%

In addition, in the main ALFWorld-1.5B and 7B experiments, CRBC achieves relative reductions in failure rate of 54.5% and 60.8%, respectively, compared with the strongest baseline. This shows that substantial reductions in the remaining errors are possible even when success rates are already high. The ALFWorld-1.5B training curves in Figure 3 further show that CRBC reaches the training reward attained by GraphGPO at update 150 using approximately half as many training updates, demonstrating an advantage in learning efficiency as well.

References

[1] Search-R1: Training LLMs to Reason and Leverage Search Engines with Reinforcement Learning. COLM, 2025.

[2] Natural Questions: A Benchmark for Question Answering Research. Transactions of the Association for Computational Linguistics, 2019.

[3] HotpotQA: A Dataset for Diverse, Explainable Multi-hop Question Answering. EMNLP, 2018.

[4] TriviaQA: A Large Scale Distantly Supervised Challenge Dataset for Reading Comprehension. ACL, 2017.

[5] When Not to Trust Language Models: Investigating Effectiveness of Parametric and Non-Parametric Memories. ACL, 2023. (PopQA)

[6] Constructing A Multi-hop QA Dataset for Comprehensive Evaluation of Reasoning Steps. COLING, 2020. (2WikiMultiHopQA)

[7] MuSiQue: Multihop Questions via Single-hop Question Composition. Transactions of the Association for Computational Linguistics, 2022.

[8] Measuring and Narrowing the Compositionality Gap in Language Models. Findings of EMNLP, 2023. (Bamboogle)

AuthorsOpenReview ↗

Response to W2/Q2 and Q3

W2/Q2: Extension to Open-Ended Environments

Thank you for highlighting this important direction. We believe semantic state matching is a feasible extension, and we already have preliminary evidence for it. In the retrieval-QA experiments in Q1, we use text-similarity-based state grouping, which allows observations that are not textually identical but sufficiently similar to be assigned to the same group. Under this setting, CRBC still achieves the highest overall EM (35.83%, compared with 29.23% for GraphGPO). CRBC’s core computation relies on anchor identifiers and empirically sampled transitions; its computational interface therefore allows the current rule-based anchor mapping ϕ(h)\phi(h) to be extended to a learned state abstraction.

Specifically, we consider constructing anchors in three steps. (1) State representation: a pretrained encoder represents the current observation. In partially observable settings, this representation can be supplemented with a decision-relevant state summary, similar to the item-state change records in the ALFWorld anchor. If a task-specific encoder is further trained, reward and latent-transition prediction objectives inspired by DeepMDP can constrain the representation [1]. (2) Candidate matching: embeddings are used to retrieve visits that may correspond to the same state. (3) Verification and merging: following UI-KOBE's retrieval-and-verification approach [2], candidates are checked against information that affects action outcomes. For computer use, this includes page structure, control states, and selected options, such as product specifications and form completion states. For software engineering, this includes workspace differences, tool feedback, and execution history, such as code changes, test results, and previously executed commands.

Verified visits are assigned to the same anchor, and the merged action identifiers are kept consistent in meaning. With the grouping fixed within the current batch, empirical transitions are aggregated and the original Bellman solve and credit computation are performed. Thus, semantic similarity only proposes candidate matches, while credit computation remains grounded in sampled actions, rewards, and transitions. For visits that cannot be reliably matched, CRBC naturally falls back to the trajectory-level signal: at nodes with only one observed action, the gate in Eq. (13) sets the step-level credit to zero. The anchor ablation in Table 4 of the revised manuscript provides empirical evidence for this behavior (see our response to Reviewer 2iuS, Q1). Tightening the matching criteria by including recent history and remaining steps reduces coverage from 77.33% to 14.57% and success from 96.09% to 86.72%, which still exceeds GRPO's 77.34%. This indicates that CRBC degrades gracefully rather than breaking down when matching is limited. We have added this discussion to Appendix E of the revised manuscript and leave the evaluation of this extension in computer-use and software-engineering environments to future work.

Q3: 7B HGPO Baseline

Thank you for pointing out the missing 7B HGPO baseline. During the rebuttal period, we conducted HGPO experiments with Qwen2.5-7B-Instruct on both ALFWorld and WebShop. To better assess variability across runs, we used seeds 1–5, yielding five runs per environment, with common training and evaluation settings held fixed across methods. We consistently report the final validation results after 150 training updates. The following results have been incorporated into the revised manuscript.

ALFWorld-7B: subtask and overall success rates (%)

RunPickCleanCoolLookHeatPick2Overall success rate
Seed 1100.0089.4792.3183.3385.7190.0091.41
Seed 2100.0089.4792.31100.0090.4885.0092.97
Seed 396.7778.9592.00100.0080.9590.0089.84
Seed 4100.0084.2188.0091.6780.9595.0090.63
Seed 5100.0089.4796.0091.6790.9195.0094.53
Mean ± SD99.35 ± 1.2986.32 ± 4.2192.12 ± 2.5393.33 ± 6.2485.80 ± 4.3691.00 ± 3.7491.88 ± 1.68

WebShop-7B: task score and success rate

RunScoreSuccess rate (%)
Seed 187.0276.56
Seed 290.2381.25
Seed 389.7380.47
Seed 489.4479.69
Seed 589.0178.13
Mean ± SD89.09 ± 1.1179.22 ± 1.68

References

[1] DeepMDP: Learning Continuous Latent Space Models for Representation Learning. ICML, 2019.

[2] UI-KOBE: Knowledge-Oriented Behavior Exploration for Lightweight Graph-Guided GUI Agents. arXiv:2605.29534, 2026.

Dear Reviewer,

Thank you again for your valuable feedback. As the discussion period draws to a close, we would appreciate hearing whether our rebuttal and additional experiments have addressed your concerns. Please let us know if there are any remaining questions or points we could clarify.

Thank you for your time and consideration.

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

This paper proposes CRBC: merging multiple rollouts for the same task into an empirical process, then using a linear solution to obtain the Bellman fixed point under the behavioral policy, and using normalized Q−VQ-V as step-level credit to improve the trajectory-level advantage of GRPO. The authors report outperformance compared to baselines such as GiGPO, GraphGPO, and HGPO in ALFWorld, WebShop, and Sokoban.

Critical strengths

The method is simple, theoretically sound, and practically valuable for reinforcement learning of critic-free agents, partially addressing the problems caused by the average token reward in GRPO.

The comparative experiments were quite thorough. The ablation experiments recorded the advantages of the components under different conditions in detail, and the theoretical explanation was somewhat clear.

Critical weaknesses

The fairness of the comparative experiments is questionable, and the core empirical conclusions lack credible support.

  1. Experimental Conclusions of GraphGPO. The experimental setup in this paper is consistent with the original GraphGPO paper (arXiv:2605.26684, Appendix C) item by item, including backbone, group size, number of training epochs, maximum number of steps, reward design, and optimization hyperparameters. The reproduction results of GiGPO also match the original paper; however, GraphGPO is significantly biased on 7B ALFWorld (95.31→90.10) and lower than GiGPO, contrary to the conclusions of the original paper. The authors do not explain why only the GraphGPO method failed to reproduce the results (the code for GraphGPO is open source).

  2. The baseline differences given by contemporaneous works under the same settings are completely unexplained. The concurrent GraphHCA (arXiv:2609.35084), under identical settings (Qwen2.5-VL-3B, 6×6 Sokoban, group size 8), reported GRPO=71.1 and GraphGPO=81.6, while this paper only reports 46.48 and 77.60, a difference of nearly 25 percentage points in GRPO alone.

  3. The experimental conclusion of "exceeding the strongest baseline by 5.59 percentage points" is questionable. The source of the HGPO used, 90.50, is not cited. According to our own protocol (128 validation tracks, 2–3 seeds), the success rate can only be an integer multiple of 1/256 or 1/384, and 90.50 is impossible to obtain under this setting. Furthermore, the 7B experiment also omitted HGPO.

  4. The baseline source is opaque. The number of subtask samples in line 7B GRPO is inconsistent with the other runs in this paper, indicating that it was not obtained on the same validation set, which contradicts the statement in the paper that "the same protocol was reproduced".

Questions for authors

Please see the section on weaknesses above.

7 comments
AuthorsOpenReview ↗

Response to Q1 (Part 1/2)

We thank the reviewer for the careful review. We have addressed all four concerns by clarifying result sources, experimental settings, and aggregation protocols, and adding baseline experiments, including five-seed comparisons in selected settings.

Within two weeks after the final decisions are announced, we will release the complete code for CRBC and the reproduced baselines, together with training and evaluation scripts and full experimental configurations.

Q1: GraphGPO Reproduction and Comparisons Across Random Seeds

Thank you for raising these concerns. We address them from the following four perspectives.

1. Environment seeds, evaluation sampling, and run-to-run variability may affect absolute performance.

The official GraphGPO training script for the 7B model uses environment seed 0 by default, whereas our original experiments used seeds 1, 2, and 3. Differences in training and evaluation sampling induced by environment seeds, together with run-to-run variability, may contribute to differences in absolute performance.

(a) The composition of the validation tasks may differ. Both studies use the ALFWorld valid_seen split, but the 128 trajectories evaluated at each validation round do not correspond to a fixed task list; their composition can vary with the environment seed and evaluation round. For example, GraphGPO’s evaluation with seed 0 contains 14 Look tasks, whereas our final evaluation contains 12 Look tasks per seed. Thus, although both studies use the same valid_seen split, the sampled validation tasks differ slightly in composition (Table 1 of GraphGPO).

(b) Prior work also reports variability in overall success rates across runs. For example, Table 1 of GiGPO reports a standard deviation of 5.2 percentage points for GRPO’s overall success rate on ALFWorld-7B, while Table 1 of GraphGPO reports 3.86 percentage points for GraphGPO on WebShop-1.5B. These results indicate that averages based on a small number of runs can be affected by randomness.

2. Additional experiments with five seeds for the 7B model further assess the stability of the comparisons.

We have completed experiments with seeds 1–5 for all five group-based methods using Qwen2.5-7B-Instruct on ALFWorld and WebShop, consistently reporting final validation success rates after 150 training updates. All methods use the same shared training and evaluation settings, with 128 evaluation trajectories per seed. All ALFWorld runs use valid_seen. In our evaluations, Clean/Look/Pick2 counts are 19/12/20 for every seed; Pick/Cool/Heat counts are 30/26/21 for seeds 1–2, 31/25/21 for seeds 3–4, and 30/25/22 for seed 5. Within each seed, these counts are identical across methods.

ALFWorld-7B: success rate (%)

MethodSeed 1Seed 2Seed 3Seed 4Seed 5Mean ± SD (5 seeds)
GRPO79.6980.4777.3478.1382.0379.53 ± 1.67
GiGPO93.7589.0685.9490.6392.9790.47 ± 2.81
GraphGPO94.5389.8485.9494.5395.3192.03 ± 3.61
HGPO91.4192.9789.8490.6394.5391.88 ± 1.68
CRBC (Ours)95.3198.4495.3197.6697.6696.88 ± 1.31

ALFWorld-7B: subtask and overall success rates across five seeds (%)

MethodPickCleanCoolLookHeatPick2Overall
GRPO99.35 ± 1.2976.84 ± 7.1469.20 ± 8.6263.33 ± 8.5076.28 ± 9.1778.00 ± 7.4879.53 ± 1.67
GiGPO98.71 ± 1.5889.47 ± 6.6685.11 ± 7.4490.00 ± 6.2485.84 ± 5.2291.00 ± 3.7490.47 ± 2.81
GraphGPO98.71 ± 2.5892.63 ± 7.1492.18 ± 4.9290.00 ± 6.2485.76 ± 8.0289.00 ± 5.8392.03 ± 3.61
HGPO99.35 ± 1.2986.32 ± 4.2192.12 ± 2.5393.33 ± 6.2485.80 ± 4.3691.00 ± 3.7491.88 ± 1.68
CRBC (Ours)100.00 ± 0.0098.95 ± 2.1195.29 ± 4.5298.33 ± 3.3392.42 ± 2.3996.00 ± 2.0096.88 ± 1.31

With the same five seeds used for all methods, CRBC exceeds the strongest baseline in mean success rate by 4.84 percentage points on ALFWorld-7B and 2.03 percentage points on WebShop-7B. GraphGPO also exceeds GiGPO by 1.56 percentage points on ALFWorld-7B, consistent with the relative ranking reported in the GraphGPO paper, and by 2.97 percentage points on WebShop-7B. Our review identified an aggregation-script error that caused the original ALFWorld-7B GiGPO result to average only the first two seeds. We have corrected this issue and expanded the comparison to the same five seeds for all methods, providing stronger evidence for the stability of the results. Table 1 now reports five-seed means and standard deviations for all five group-based methods using Qwen2.5-7B-Instruct.

AuthorsOpenReview ↗

Response to Q1 (Part 2/2)

Q1: GraphGPO Reproduction and Comparisons Across Random Seeds

Continuing our response to Q1, we present the WebShop-7B results and the remaining analyses below.

WebShop-7B: success rate (%)

MethodSeed 1Seed 2Seed 3Seed 4Seed 5Mean ± SD (5 seeds)
GRPO76.5673.4472.6675.7870.3173.75 ± 2.24
GiGPO78.1375.0077.3474.2273.4475.63 ± 1.81
GraphGPO78.1378.1378.1378.9179.6978.59 ± 0.63
HGPO76.5681.2580.4779.6978.1379.22 ± 1.68
CRBC (Ours)83.5976.5684.3882.0379.6981.25 ± 2.84

3. Additional CRBC experiments with environment seed = 0 and comparison with published results.

We additionally set the ALFWorld-7B environment seed to the official launch script’s default value of 0 and completed three CRBC runs, reporting final validation results after 150 training updates. CRBC achieves a mean success rate of 97.14 ± 0.74%. The table below also includes the GiGPO and GraphGPO results reported in Table 1 of GraphGPO as supplementary references. Relative to the values displayed in that paper, CRBC is higher by 2.87 and 1.83 percentage points, respectively.

MethodResult sourceSuccess rate (%)
GiGPOGraphGPO, Table 194.27 ± 1.33
GraphGPOGraphGPO, Table 195.31 ± 1.10
CRBC (Ours)Environment seed = 0, three local runs97.14 ± 0.74

4. Performance differences across studies also occur in prior work.

The same method can have different reported results across studies. The original GiGPO paper reports success rates of 86.7% and 90.8% for GiGPO with standard-deviation normalization on ALFWorld-1.5B and ALFWorld-7B, respectively. The corresponding GiGPO results in the GraphGPO paper are 90.88% and 94.27%, higher by 4.18 and 3.47 percentage points, respectively. These differences suggest that run-to-run variability and differences in experimental settings may substantially affect absolute performance. They also show that differences across studies are not unique to our reproduction of GraphGPO.

AuthorsOpenReview ↗

Response to Q2, Q3, Q4

Q2: Verification of Sokoban Runs and Updated Results

Thank you for bringing this to our attention. Following our review, we reran training with three seeds and consistently report the final validation results after 150 training updates. The updated statistics have been incorporated into the revised manuscript, and all other local results have been checked against the original logs. This correction updates the reported GRPO results and the associated performance gaps; it does not change the existing direct comparisons between CRBC and step-level baselines such as GiGPO and GraphGPO.

MethodRun 1Run 2Run 3Mean ± SD (3 seeds)
GRPO67.97%66.41%73.44%69.27 ± 3.01%
GraphGPO74.22%77.34%81.25%77.60 ± 2.88%

As discussed in Q1, differences in random seeds and evaluation sampling may affect absolute performance across papers. Table 2 of GraphHCA [1] also uses three seeds and reports a standard deviation of 4.03 percentage points for GraphGPO’s success rate, indicating appreciable variation across runs. To further check our reproduction results, we completed two additional GraphGPO runs with seeds 4 and 5, obtaining success rates of 81.25% and 79.69%, respectively. The five-seed aggregate is 78.75 ± 2.68%, close to the original three-seed result. These two additional runs serve as supplementary checks; the main Sokoban table retains the statistics from the original three seeds.

Q3: Source of HGPO Results and Additional Experiments

Thank you for pointing out this issue. The original manuscript did not explicitly identify the source and aggregation protocol for the HGPO results. The HGPO results for Qwen2.5-1.5B-Instruct in the original Table 1 were taken from Table 2 of Gated-BEPO [2], following its protocol of 3 training seeds × 3 environment seeds, yielding 9 evaluation runs, each containing 128 trajectories. The source reports 90.5 ± 0.4% to one decimal place. We added trailing zeros solely for formatting consistency, giving 90.50 ± 0.40% without changing the values.

To further standardize the comparison, we conducted local HGPO experiments with Qwen2.5-1.5B-Instruct using three seeds, following the same training budget, evaluation configuration, and result-selection rule as the other methods. We report final validation results after 150 training updates. HGPO achieves 91.41 ± 1.10% success on ALFWorld-1.5B, close to the originally cited result; accordingly, CRBC’s improvement over the strongest baseline is updated to 4.69 percentage points. We have also updated the local reproduction results for WebShop in the revised Table 1 and added the missing 7B HGPO baseline, as reported in Q1.

RunPickCleanCoolLookHeatPick2Overall success rate
Seed 1100.0084.2188.4683.3390.4885.0089.84
Seed 296.6794.7496.1583.3395.2480.0092.19
Seed 3100.0094.7492.0083.3395.2480.0092.19
Mean ± SD98.89 ± 1.5791.23 ± 4.9692.21 ± 3.1483.33 ± 0.0093.65 ± 2.2481.67 ± 2.3691.41 ± 1.10

Q4: Source of the ALFWorld-7B GRPO Results and Additional Experiments

Thank you for pointing out this issue. The original manuscript did not clearly distinguish these results taken from prior work from our local reproductions, making the statement that the methods were “reproduced under the same protocol” insufficiently precise. The ALFWorld-7B GRPO results in the original Table 1 were taken from Table 1 of GraphGPO, with all means and standard deviations retained as reported. As discussed in Q1, both studies use the same valid_seen split, but the 128 trajectories evaluated at each validation round do not correspond to a fixed task list. The sampled tasks and subtask counts may vary with the environment seed and evaluation round. Therefore, different subtask counts do not imply that different validation splits were used.

To strengthen the comparison under a common protocol, we conducted local experiments for GRPO with the 7B model. The per-seed results and aggregate statistics are provided in Q1, all based on the final validation after 150 training updates. In these additional experiments, GRPO’s mean success rate remains below those of GiGPO and GraphGPO, consistent with the trends reported in prior work. These local results replace the cited values in the revised manuscript, with the reproduction protocol clarified accordingly. The existing comparisons between CRBC and step-level baselines and their supported conclusions remain unchanged.

References

[1] GraphHCA: Closed-Form Hindsight Credit Assignment for Long-Horizon LLM Agents. arXiv:2609.35084, 2026.

[2] Gated-BEPO: Confidence-Gated Bellman Credit Assignment for Large Language Model Agents. arXiv:2608.06861, 2026.

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

This paper proposes CRBC, a critic-free method for step-level credit assignment in LLM-agent reinforcement learning. It merges same-task rollouts through shared anchors, solves the resulting empirical behavior-policy Bellman system, and combines normalized Q−V credit with trajectory-level advantages. A finite-depth formulation connects visit-local return averaging to full cross-rollout closure.

Critical strengths
  1. CRBC combines cross-rollout propagation with empirical-frequency aggregation without a learned critic or additional rollouts, allowing broader use of the collected experience at little extra cost.
  2. Experiments show consistent gains across three environments and multiple model scales, while matched depth ablations and runtime profiling support the effectiveness and practicality of full closure.
Critical weaknesses
  1. The current anchors omit recent prompt history and remaining horizon, which may affect the comparability of merged visits. The sensitivity of CRBC to these choices remains unclear.
  2. Evaluation covers three environments, but uses in-distribution ALFWorld validation, a small WebShop catalogue, and one-box Sokoban. With depth ablations limited to ALFWorld-1.5B, evidence for broader generalization remains limited.
Questions for authors
  1. How sensitive is CRBC to the anchor definition? Could the authors compare the current anchors with variants that include recent history or remaining steps, and report both matching coverage and task performance?
  2. On ALFWorld-1.5B, do the gains over GiGPO and GraphGPO hold with comparable tuning budgets for step/trajectory weights and method-specific discounts under the same training protocol?
6 comments
AuthorsOpenReview ↗

Response to Q1/W1

Thank you for your careful review. We have added anchor sensitivity analyses, ALFWorld OOD evaluation, Search-R1 multi-turn retrieval-augmented QA experiments, WebShop closure-depth ablations, and baseline weight and discount comparisons. We address each point below; these additions are included in the revised manuscript. Code will be released after the final decisions are announced.

Q1/W1: Sensitivity to the anchor definition

We compare four anchor definitions on ALFWorld with Qwen2.5-1.5B-Instruct, fixing seed 1 and keeping model inputs and training settings unchanged. The default anchor includes the current observation, location, inventory, and a summary of state changes. We add the two most recent observation–action pairs, remaining interaction steps, or both. Matching coverage is the fraction of visits at anchors shared by at least two trajectories within the same task group, pooling visit counts across training. Multi-action coverage additionally requires at least two distinct actions. Success rates and validation scores are evaluated on 128 trajectories after training update 150.

The results show that finer-grained anchors do not improve performance; performance declines as matching coverage decreases. Adding history, remaining steps, or both reduces success by 3.12, 7.81, and 9.37 percentage points, respectively, while validation scores fall from 8.20 to 7.28, 5.71, and 5.36. Stricter matching separates visits reaching the same state through different paths or at different times into distinct nodes, reducing cross-trajectory experience sharing. Nevertheless, performance degrades gradually rather than collapsing: anchors with only one observed action receive zero step-level credit and retain the trajectory-level signal. The strictest variant still achieves 86.72% success with only 14.57% matching coverage, exceeding GRPO’s 77.34%.

Anchor definitionCross-trajectory matching coverageMulti-action coverageFinal validation successValidation score
Default anchor77.33%58.16%96.09%8.20
+ Recent history (2 turns)30.02%20.60%92.97%7.28
+ Remaining interaction steps28.95%21.14%88.28%5.71
+ History and remaining steps14.57%8.12%86.72%5.36

These results illustrate a trade-off between contextual specificity and experience sharing. Finer anchors can reduce state aliasing, but the loss of sharing outweighs this benefit under the current sampling budget, supporting the current anchor design in this setting. We have added these ablations and analyses to Section 5.3 of the revised manuscript.

AuthorsOpenReview ↗

Response to W2

W2: Generalization evaluation and closure-depth ablation on WebShop

Thank you for this feedback. The in-distribution ALFWorld validation split, the small WebShop product catalog, and the 6×6 single-box Sokoban environment are standard settings used in related work, including GiGPO and GraphGPO. We adopt these settings to facilitate direct comparison with existing results. We further extend this evaluation with ALFWorld valid_unseen, Search-R1 multi-turn retrieval-augmented QA, and WebShop closure-depth ablations to examine the mechanism beyond ALFWorld.

1. Out-of-distribution evaluation on ALFWorld.

We evaluate Qwen2.5-1.5B-Instruct checkpoints after training update 150 on all 134 valid tasks in valid_unseen. This split contains the same six task types but uses scenes not encountered during training. All three methods use the same task list and evaluation settings.

MethodPick (24)Clean (31)Cool (21)Look (18)Heat (23)Pick2 (17)Overall (134)Score
GiGPO83.3380.6585.7194.4491.3094.1287.316.02
GraphGPO87.5087.1090.48100.0086.9688.2489.556.34
CRBC (Ours)87.5090.32100.00100.0091.3088.2492.546.75

CRBC achieves the highest success rate on unseen scenes, exceeding GraphGPO by 2.99 percentage points. Its advantage persists under this scene distribution shift, providing additional generalization evidence. Results are included in Appendix D.3.

2. Retrieval-augmented QA evaluation across a broader range of tasks.

To broaden the evaluation, we add Search-R1 multi-turn retrieval-augmented QA experiments. We train Qwen2.5-1.5B-Instruct on a dataset comprising NQ and HotpotQA, and compare GRPO, GiGPO, GraphGPO, and CRBC on seven datasets: NQ, TriviaQA, PopQA, HotpotQA, 2WikiMultiHopQA, MuSiQue, and Bamboogle. All methods use the same fixed evaluation set of 893 questions and shared training settings. We report intermediate results after 100 training updates for all methods.

CRBC achieves 35.83% overall exact match (EM), exceeding GraphGPO by 6.6 percentage points, and leads on six of seven subsets (except 2WikiMultiHopQA). These tasks require external retrieval, multi-turn interaction, and evidence integration, extending the evaluation across task types. Settings and detailed results are in Appendix D.2.

Evaluation subsetQuestionsGRPOGiGPOGraphGPOCRBC
NQ12839.06%38.28%42.19%50.00%
TriviaQA12845.31%50.00%53.13%58.59%
PopQA12821.88%25.00%25.00%43.75%
HotpotQA12821.88%26.56%27.34%33.59%
2WikiMultiHopQA12819.53%28.13%28.13%26.56%
MuSiQue1286.25%7.03%6.25%10.16%
Bamboogle12521.60%20.80%22.40%28.00%
Overall89325.08%28.00%29.23%35.83%

3. Closure-depth ablation on WebShop.

We further compare K∈0,1,2,∞K\in\\{0,1,2,\infty\\} on WebShop with Qwen2.5-1.5B-Instruct. We vary only the closure depth while keeping anchors, aggregation rules, and all other training settings fixed. All results are evaluated after training update 150.

Closure depthSuccess rate (%)Score
K=0K=0: Visit-local estimation78.1388.72
K=1K=1: One-step propagation80.4789.15
K=2K=2: Two-step propagation80.4789.73
K=∞K=\infty: Full closure82.0390.36

As on ALFWorld, success rate and score generally improve with closure depth, with full closure performing best. The benefit of more extensive cross-trajectory Bellman propagation on WebShop supports the mechanism’s effectiveness across environments.

AuthorsOpenReview ↗

Response to Q2

Q2: Ablations on advantage weights and discount parameters

Thank you for this suggestion. First, CRBC’s advantage does not depend on additional tuning of advantage weights. In the weight ablation in Appendix D.1 of the original manuscript (original Table 5; Table 6 in the revision), CRBC achieves a three-seed mean success rate of 93.75% with (wG,wS)=(1,1)(w_{\mathrm{G}},w_{\mathrm{S}})=(1,1), matching the default weights of GiGPO and GraphGPO. This already exceeds the Table 1 results for GiGPO (89.32%), GraphGPO (90.10%), and the strongest baseline, HGPO (91.41%). Building on this result and the sensitivity analyses in the original baseline papers, we conduct additional comparisons of advantage weights and discount parameters on ALFWorld-1.5B.

1. Advantage weights.

Both baselines use (wG,wS)=(1,1)(w_{\mathrm{G}},w_{\mathrm{S}})=(1,1) as their official default. Appendix E.5 of the GiGPO paper compares eight step-level weights on WebShop-1.5B: the best weight, 0.8, achieves 68.3% success, while the default weight of 1 achieves a comparable 67.4%. To further assess sensitivity on ALFWorld-1.5B, we fix the trajectory-level weight at 1, GiGPO’s temporal discount at 0.95, and GraphGPO’s distance discount at 0.1, and compare four step-level weights:

MethodwS=0.5w_{\mathrm{S}}=0.51 (default)2.55
GiGPO87.50%90.63%88.28%89.84%
GraphGPO89.06%91.41%90.63%90.63%

2. Discount parameters.

GiGPO computes discounted returns along sampled trajectories, with a default of γ=0.95\gamma=0.95. We fix the advantage weights at (1,1)(1,1) and keep all other settings unchanged while comparing the following values:

Temporal discount γ\gamma0.95 (default)0.980.991.0
Success rate90.63%89.84%87.50%61.72%

At γ=1.0\gamma=1.0, success drops to 61.72%. One possible explanation is that, with terminal success/failure rewards, removing discounting makes step-level returns insensitive to the number of steps required to reach termination, weakening their ability to distinguish path efficiency.

GraphGPO constructs step-level rewards using shortest-path costs on the graph:$ R^G(s,a,s')=r_{\mathrm{succ}}\omega^{d(s')+c(s,a)}. $ Here, ω\omega controls reward decay with shortest-path cost. It operates differently from GiGPO’s γ\gamma and CRBC’s β\beta, so applying the same numerical search range directly would be inappropriate. Appendix D.1 of the GraphGPO paper compares five discount configurations on each of ALFWorld and WebShop. On ALFWorld-1.5B, the default value of 0.1 and the best tested value of 0.4 achieve 92.71% and 92.97%, respectively—a difference of only 0.26 percentage points. We therefore retain the default of 0.1.

3. Comparison results.

Under the same training and evaluation protocol, CRBC achieves 96.09% success, exceeding the best GiGPO and GraphGPO results in these sweeps by 5.47 and 4.69 percentage points, respectively. Together with the results using default advantage weights, these experiments support that CRBC retains its advantage within the parameter ranges examined.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.