- 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
-
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.
-
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
-
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.
-
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
-
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?
-
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?
-
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
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 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 (%)
| Run | Pick | Clean | Cool | Look | Heat | Pick2 | Overall success rate |
|---|---|---|---|---|---|---|---|
| Seed 1 | 100.00 | 89.47 | 92.31 | 83.33 | 85.71 | 90.00 | 91.41 |
| Seed 2 | 100.00 | 89.47 | 92.31 | 100.00 | 90.48 | 85.00 | 92.97 |
| Seed 3 | 96.77 | 78.95 | 92.00 | 100.00 | 80.95 | 90.00 | 89.84 |
| Seed 4 | 100.00 | 84.21 | 88.00 | 91.67 | 80.95 | 95.00 | 90.63 |
| Seed 5 | 100.00 | 89.47 | 96.00 | 91.67 | 90.91 | 95.00 | 94.53 |
| Mean ± SD | 99.35 ± 1.29 | 86.32 ± 4.21 | 92.12 ± 2.53 | 93.33 ± 6.24 | 85.80 ± 4.36 | 91.00 ± 3.74 | 91.88 ± 1.68 |
WebShop-7B: task score and success rate
| Run | Score | Success rate (%) |
|---|---|---|
| Seed 1 | 87.02 | 76.56 |
| Seed 2 | 90.23 | 81.25 |
| Seed 3 | 89.73 | 80.47 |
| Seed 4 | 89.44 | 79.69 |
| Seed 5 | 89.01 | 78.13 |
| Mean ± SD | 89.09 ± 1.11 | 79.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.
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.
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)