acceptodds
Under review as a conference paper at ICLR 2027

Learning from All-Failed Groups via First-Visit Coverage in Long-Horizon Agentic Tasks

Abstract

Group-based policy optimization has been increasingly used to train large language model (LLM) agents from sparse outcome rewards by comparing trajectories or steps within a group. However, on difficult long-horizon agentic tasks, we found this comparison suffers from a sampling imbalance: repeated or low-effect actions dominate the high-probability region of the policy, leaving useful state-changing actions under-sampled. This imbalance produces many all-failed rollout groups, where the relative advantages within such a group provide no direction for updating the policy. Consequently, the sampling imbalance and the all-failed groups collapse into a self-perpetuating credit trap: failure-dominated sampling yields no learning signal, allowing repeated low-effect actions to persist. To break this trap, we propose Coverage-conditioned Group Policy Optimization (CovGPO), which uses first-visit observation coverage only when all samples in a group receive zero outcome reward. Specifically, within such groups, CovGPO assigns higher relative advantages to state-exploring actions without corrupting the original reward signal, as reaching new observations is a prerequisite for task success. Experiments on two challenging agentic benchmarks, ALFWorld and WebShop, show that CovGPO consistently improves over group-based baselines, with particularly large gains on hard tasks.

Primary area:
reinforcement learning
Keywords:
Reinforcement learning, Policy optimization, Long-horizon tasks, all-fail group

Reviews

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

CovGPO addresses zero-reward groups whose outcome-relative advantages vanish. It ranks failed trajectories by first-visit observation coverage and conditionally substitutes normalized coverage advantages. The method requires no additional learned components or rollouts. Experiments augment GRPO, GiGPO and HGPO on ALFWorld and WebShop, with an exploratory Sokoban extension.

Critical strengths
  1. Low-cost integration. CovGPO reuses collected trajectories without extra models or environment interactions, making it a practical augmentation of existing optimizers.

  2. Relevant experimental controls. Comparisons with always-on coverage and substituted signals support the usefulness of conditional, trajectory-aligned feedback in the tested settings.

Critical weaknesses
  1. The contribution is incremental, and the coverage signal does not adequately capture semantic redundancy. The main modification is a conditional replacement of advantages using a trajectory-level exploration statistic. Appendix C.2 specifies exact observation-string matching rather than semantic equivalence. Equivalent actions can therefore contribute to coverage when their outputs differ superficially, while hidden state changes may go undetected. The authors acknowledge this limitation, but do not directly test representation sensitivity. This weakens the case for a broadly reliable credit-assignment improvement.

  2. Performance gains are uneven, and broader effectiveness remains insufficiently established. Although some improvements over GiGPO are meaningful, aggregate gains over GRPO and the stronger 7B HGPO baseline are modest. Table 1 also shows substantial subtask variation, including gains on Look and Cool but regressions on Clean and Heat with the 1.5B GRPO base. The category breakdowns and diagnostics do not adequately explain these regressions. Text experiments use only 1.5B and 7B models on two benchmarks, while Sokoban changes the signal. Consistent benefits with larger models or more diverse tasks therefore remain uncertain.

  3. The proofs provide limited support for task-performance improvement. Appendix B.4 assumes that greater coverage implies better continuation value rather than establishing this relationship. B.6 proves a gradient identity for an unnormalized estimator of coverage conditioned on failure, not for the deployed gated and normalized update. B.7 further shows that fallback credit can suppress a key forward action. These results characterize the mechanism but do not establish a theoretical link between coverage-based updates and escaping the credit trap.

  4. Presentation suggestion. The main idea is understandable, but the frequent colon-led lists make the exposition fragmented. Related work should be integrated into the main paper.

Questions for authors

see weaknesses above

11 comments
AuthorsOpenReview ↗

Response to Reviewer qJMP – Part 1

We sincerely thank you for the detailed and constructive feedback. We address each weakness and suggestion point by point below.


Q1: Value and Core Novelty of Lightweight Signal Extraction from All-Failed Rollouts

A: Regarding your concern in W1 that "the contribution is incremental... the main modification is a conditional replacement of advantages using a trajectory-level exploration statistic," we respectfully view uncovering an insightful perspective through a lightweight (O(1)O(1)), non-interfering mechanism as a deliberate strength: our core novelty lies in extracting credible, structured signals from degenerate all-failed trajectories so rollout compute is fully utilized rather than discarded.

  • Methodological simplicity, compute reuse, and core novelty: Instead of introducing heavy auxiliary reward/world models or discarding zero-variance groups (as in dynamic resampling like DAPO, which throws away already-paid rollout compute and incurs 3× to 4× wall-clock cost), our novelty centers on extracting credible, structured learning signals from all-failed trajectories in an extremely lightweight (O(1)O(1)) and efficient manner, paired with strict non-interference whenever reward variance exists (σR>0\sigma_R \gt 0, Proposition 2), so rollout compute resources are fully utilized.
  • Mechanism and empirical significance of first-visit coverage: Even when an environment's global state space is vast or infinite, within a given task over a finite horizon TT, the agent's effective action space is finite and becomes even more constrained in erroneous failure modes. Stuck rollouts repeatedly issue invalid commands or failed queries and revisit seen observations (oi,t+1∈Vi,t  ⟹  Pi≪1o_{i,t+1} \in \mathcal V_{i,t} \implies P_i \ll 1), contrasting sharply against exploratory rollouts (Pi→1P_i \to 1) to maintain structured contrast (σP≫0\sigma_P \gg 0). Achieving consistent gains across ALFWorld and WebShop (Main Table 1) via this lightweight signal demonstrates that extracting learning signals from uniform-outcome (all-failed and all-succeeded) trajectories is a highly promising direction.
  • Broader vision for the community: While bounded by training time and compute budgets from scaling to every high-complexity domain in one paper, in more complex domains such as coding, analogous structured signals can likewise be extracted (e.g., via semantic, policy hidden-state, or representation-level signals). Advancing the perspective that degenerate uniform-outcome rollouts contain rich, extractable structure is the central contribution we bring to the community.

Revision: We will sharpen this core contribution framing and broader uniform-outcome signal-extraction perspective in Section 1 and Section 3.2.


Table R6: Offline String-Similarity Threshold (τsim\tau_{\text{sim}}) Representation-Sensitivity Sweep Across 4 Benchmarks with Qwen2.5.

EnvironmentModelReturn > 0τ=1.0\tau=1.0 Multi-Memberτ=1.0\tau=1.0 Signalτ=0.9\tau=0.9 Sig / Contamτ=0.8\tau=0.8 Sig / Contamτ=0.7\tau=0.7 Sig / Contamτ=0.6\tau=0.6 Sig / ContamTrade-off (1.0→0.61.0 \to 0.6)
ALFWorld1.5B12.5%96.1%19.1%20.7% / 31.0%21.4% / 47.4%21.6% / 52.9%22.2% / 54.9%+3.1pp vs. 54.9%
ALFWorld7B18.0%97.4%35.9%36.6% / 17.4%37.9% / 25.7%38.8% / 28.8%39.4% / 29.9%+3.5pp vs. 29.9%
ScienceWorld1.5B3.1%98.6%1.7%1.7% / 2.9%1.7% / 4.4%1.7% / 4.9%1.7% / 5.4%+0.0pp vs. 5.4%
ScienceWorld7B12.9%97.2%22.0%22.7% / 8.7%22.9% / 14.0%23.1% / 18.0%23.3% / 20.5%+1.3pp vs. 20.5%
WebShop1.5B5.1%85.8%11.5%12.2% / 16.7%12.3% / 20.7%12.4% / 26.0%12.7% / 32.6%+1.2pp vs. 32.6%
SearchQA1.5B8.1%76.2%14.1%14.1% / 0.0%14.1% / 0.0%14.5% / 0.8%14.9% / 7.4%+0.8pp vs. 7.4%
SearchQA7B28.1%76.9%23.5%23.5% / 0.3%23.5% / 0.3%23.7% / 4.4%28.6% / 26.9%+5.1pp vs. 26.9%
AuthorsOpenReview ↗

Response to Reviewer qJMP – Part 2

Q2: Controlled Protocol (Appendix C.2), Direct Representation-Sensitivity Test, and Fail-Safe Gating

A: Regarding your concern in W1 that "Appendix C.2 specifies exact observation-string matching rather than semantic equivalence; equivalent actions can contribute to coverage when outputs differ superficially, while hidden state changes may go undetected, and the authors do not directly test representation sensitivity," our 4-benchmark string-similarity sweep directly quantifies representation sensitivity (showing that relaxing exact matching incurs a 5× to 27× state-contamination penalty) while our σP≥τP\sigma_P \ge \tau_P gate safely neutralizes superficial output differences and hidden state changes.

  • Controlled protocol & description of Table R6: First, Appendix C.2 adopts exact observation matching (τsim=1.0\tau_{\text{sim}} = 1.0) to strictly follow GiGPO (Feng et al., 2025, arXiv:2505.10978) in verl-agent, ensuring CovGPO and step-level baselines (GiGPO, HGPO) operate on identical anchor groups without confounding state abstraction with credit assignment. Second, to directly test representation sensitivity, we replayed stored rollouts (256 trajectories per setting on ALFWorld/ScienceWorld/WebShop; 320 on SearchQA) through GiGPO's approximate string-similarity grouping across τsim∈{1.0,0.9,0.8,0.7,0.6}\tau_{\text{sim}} \in \{1.0, 0.9, 0.8, 0.7, 0.6\}, measuring multi-member grouping rate, non-zero advantage Signal rate (γ=0.95\gamma=0.95), and false state-merging Contam rate (% of execution steps).

  • Summary of findings from Table R6 & fail-safe analysis:

  1. Signal-noise-ratio degradation under relaxed string matching: Lowering τsim\tau_{\text{sim}} from 1.0→0.61.0 \to 0.6 increases non-zero advantage steps by only +0.0 to 5.1 pp, while falsely merging genuinely distinct states in 20.5% to 54.9% of steps (a 5× to 27× noise-to-signal penalty; e.g., conflating distinct rooms or objects sharing surface templates).
  2. Open-ended retrieval (SearchQA) stability: Exact matching (τsim=1.0\tau_{\text{sim}}=1.0) groups 76.2% (1.5B) / 76.9% (7B) of steps and remains nearly invariant across τsim∈{1.0,0.9,0.8}\tau_{\text{sim}} \in \{1.0, 0.9, 0.8\} (0.0% to 0.3% contamination).
  3. Fail-safe gating under superficial output differences and hidden state changes: In edge cases where superficial output differences mark every step novel (∀i,Pi=1\forall i, P_i = 1) or undetected hidden state changes leave observations unchanged across the group (∀i,Pi=0\forall i, P_i = 0), within-group dispersion vanishes (σP=0<τP\sigma_P = 0 \lt \tau_P) and our variance gate automatically withholds the fallback, reducing CovGPO exactly to the base learner (Proposition 2) instead of injecting corrupted advantages.

Revision: We will include Table R6 and the superficial/hidden-state fail-safe proof discussion in Appendix C.2 and Section 4.3.


Q3: Subtask Regressions Under 1.5B GRPO vs. Simultaneous Gains Under Step-Level GiGPO and HGPO

A: Regarding your observation in W2 that "Table 1 shows substantial subtask variation, including gains on Look and Cool but regressions on Clean and Heat with the 1.5B GRPO base, and the category breakdowns do not adequately explain these regressions," 1.5B GRPO's drops on Clean and Heat arise from broadcasting a single coarse trajectory-wide scalar across 20 to 50 steps onto shared low-level primitives under compact 1.5B capacity, whereas step-level grouping in GiGPO/HGPO protects mastered states and improves all 6 subtasks simultaneously.

  • Coarse trajectory-level broadcasting and shared-primitive interference in 1.5B GRPO: All six ALFWorld subtasks share common low-level interaction primitives (goto, take, open, put), while the three hardest subtasks Pick2 (34%), Cool (26%), and Look (18%), account for 78% of all-failed groups (Appendix Table 17). Vanilla GRPO assigns zero advantage (AiR≡0A_i^R \equiv 0) to these failed groups, leaving Look (53.7%) and Cool (59.7%) under-trained while concentrating updates on easier subtasks* (Clean and Heat). Recovering gradients on all-failed groups enables 1.5B GRPO+CovGPO to substantially boost Look (+22.6 pp) and Cool (+23.5 pp) and lift overall success (72.8%→74.5%72.8\% \to 74.5\%). However, because GRPO broadcasts a single trajectory-wide scalar advantage uniformly across all 20 to 50 steps, a high-coverage failed trajectory that explores new rooms but later wanders receives positive credit on every step, whereas a low-coverage failed trajectory that executes valid early navigation/pickup primitives before stalling is penalized across its entire prefix. Under compact 1.5B capacity, this coarse trajectory-wide update introduces gradient interference on shared primitives and trades off part of Clean and Heat (where 1.5B GRPO already shows high seed variance of ± 6.8 to 9.2).
AuthorsOpenReview ↗

Response to Reviewer qJMP – Part 3

Table R7: ALFWorld 1.5B Subtask Breakdown vs. All-Failed Group Composition (Main Table 1 & Appendix Table 17).

SubtaskShare of All-Failed Groups1.5B GRPO →\to +CovGPO1.5B GiGPO →\to +CovGPO1.5B HGPO →\to +CovGPO
Pick2 (Hard)34%53.5%→50.8%53.5\% \to 50.8\% (-2.7)76.4%→90.9%76.4\% \to \mathbf{90.9\%} (+14.5)88.0%→93.5%88.0\% \to \mathbf{93.5\%} (+5.5)
Cool (Hard)26%59.7%→83.2%59.7\% \to \mathbf{83.2\%} (+23.5)79.8%→90.6%79.8\% \to \mathbf{90.6\%} (+10.8)87.6%→92.3%87.6\% \to \mathbf{92.3\%} (+4.7)
Look (Hard)18%53.7%→76.3%53.7\% \to \mathbf{76.3\%} (+22.6)67.5%→74.5%67.5\% \to \mathbf{74.5\%} (+7.0)85.4%→91.3%85.4\% \to \mathbf{91.3\%} (+5.9)
Clean12%84.5%→74.8%84.5\% \to 74.8\% (-9.7)94.8%→98.4%94.8\% \to \mathbf{98.4\%} (+3.6)95.0%→98.3%95.0\% \to \mathbf{98.3\%} (+3.3)
Heat6%78.2%→69.6%78.2\% \to 69.6\% (-8.6)94.4%→95.9%94.4\% \to \mathbf{95.9\%} (+1.5)97.4%→97.1%97.4\% \to 97.1\% (-0.3)
Pick (Saturated)4%85.3%→84.1%85.3\% \to 84.1\% (-1.2)94.4%→94.9%94.4\% \to \mathbf{94.9\%} (+0.5)97.8%→100.0%97.8\% \to \mathbf{100.0\%} (+2.2)
Overall100%72.8%→74.5%72.8\% \to \mathbf{74.5\%} (+1.7)86.7%→92.2%86.7\% \to \mathbf{92.2\%} (+5.5)92.8%→95.7%92.8\% \to \mathbf{95.7\%} (+2.9)
  • Summary of findings from Table R7: Once paired with step-level credit assignment, 1.5B GiGPO+CovGPO improves all 6 subtasks simultaneously (86.7%→92.2%86.7\% \to 92.2\%, led by +14.5 pp on Pick2 and +10.8 pp on Cool) without any regression on Clean (+3.6 pp) or Heat (+1.5 pp), 1.5B HGPO+CovGPO reaches 95.7% overall, and at larger model capacity 7B GRPO+CovGPO likewise boosts Heat from 74.7%→91.2%74.7\% \to 91.2\%.

Revision: We will add this mechanistic diagnosis of trajectory-wide broadcasting interference vs. step-level local gating to Section 4.1.


Q4: Non-Interference on Near-Saturated 7B HGPO and Broader Task/Model Validation

A: Regarding your concern in W2 that "aggregate gains over the stronger 7B HGPO baseline are modest, text experiments use only 1.5B and 7B models on two benchmarks, so consistent benefits with diverse tasks and models remain uncertain," on near-saturated 7B HGPO (95.4%), Proposition 2 guarantees non-interfering disengagement, while expanded runs across harder text benchmarks (SearchQA, ScienceWorld) and newer model families (Qwen3.5-2B/4B).

Table R8: Expanded Evaluation Across Harder Benchmarks and Newer Model Generations.

MethodNQ†TriviaQA★PopQA★HotpotQA†2Wiki★MuSiQue★Bamboogle★Avg.ScienceWorld SRScienceWorld Score
Qwen2.5-3B-Instruct
GRPO45.24 ± 0.2960.64 ± 0.0645.37 ± 0.0936.37 ± 0.1835.21 ± 0.1712.26 ± 0.3226.67 ± 0.9237.40 ± 0.12--
GRPO+CovGPO43.46 ± 0.2860.08 ± 0.0444.29 ± 0.2639.45 ± 0.2539.46 ± 0.1414.98 ± 0.6529.87 ± 2.0138.80 ± 0.29--
GiGPO44.9 ± 0.360.4 ± 0.046.7 ± 0.136.3 ± 0.235.0 ± 0.412.0 ± 0.363.0 ± 0.542.6 ± 0.0--
GiGPO+CovGPO42.4 ± 0.659.8 ± 0.145.6 ± 0.339.3 ± 0.339.6 ± 0.214.7 ± 0.764.7 ± 1.043.7 ± 0.2--
Qwen2.5-7B-Instruct
GRPO41.6 ± 2.360.7 ± 0.943.5 ± 1.439.6 ± 0.037.7 ± 2.615.2 ± 0.549.9 ± 25.241.2 ± 2.921.6 ± 2.329.3 ± 2.6
GRPO+CovGPO46.0 ± 1.363.2 ± 0.445.7 ± 0.740.4 ± 0.142.2 ± 0.118.1 ± 0.969.5 ± 1.546.5 ± 0.322.9 ± 2.330.1 ± 4.0
GiGPO40.2 ± 0.461.3 ± 0.141.8 ± 1.039.5 ± 0.237.5 ± 2.215.7 ± 0.167.9 ± 0.343.4 ± 0.322.9 ± 2.329.8 ± 4.3
GiGPO+CovGPO45.4 ± 0.363.7 ± 0.646.4 ± 0.242.7 ± 0.041.1 ± 1.118.9 ± 0.172.2 ± 1.747.2 ± 0.125.3 ± 0.936.3 ± 1.7
Reviewer_uxjrOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies the credit trap in group-style RL multi-turn agents where the group reward advantage remains zero upon complete failure, and proposes CovGPO: only in the case of complete failure, conditional rollback advantage is constructed based on the coverage of first-visited observations, and the original advantage is restored when there is a reward difference; the contributions include identifying the trap and ensuring non-interference. Experiments on ALFWorld/WebShop with Qwen2.5-1.5B/7B demonstrate improvements over GRPO, GiGPO, and HGPO.

Critical strengths

1.The true pain point is that the GRPO advantage in the completely failed group is consistently zero. CovGPO only reverts when there is no reward difference; when a difference exists, it restores the original advantage. Ensuring non-interference is very important, as it prevents exploration signals from contaminating normal learning.

2.It is lightweight and pluggable, requiring no additional models or rollouts. It consistently improves GRPO, GiGPO, and HGPO on ALFWorld/WebShop, which is of practical value for text-constrained agents.

Critical weaknesses
  1. The novelty assessment is overly simplistic and crude, relying solely on observed string hash matching without semantic clustering. In open Agent or code scenarios, synonymous expressions or format variations may be misjudged as new states. Moreover, validation is only performed on the two simple text Agents, ALFWorld and WebShop, lacking coverage of code scenarios, resulting in insufficient scalability and making it difficult to support a generality claim. Second, the backbone is only Qwen2.5-1.5B/7B, meaning the model is relatively old and singular, lacking updated models and inference/code benchmarks, so improvements may be constrained by the backbone's capability, and conclusions have limited generalizability.
Questions for authors
  1. The paper only uses observational string hash matching to judge new state, without semantic clustering or equivalence assessment. In open Agent or code scenarios, synonymous expressions, formatting changes, and irrelevant outputs may all be mistakenly judged as new states.

  2. Validation is only conducted on two simple text Agents, ALFWorld and WebShop, without including more complex scenarios such as code environments. Therefore, there is no proof that the method can scale to open action spaces or heterogeneous Agent environments.

  3. Only Qwen2.5-1.5B/7B was used, without validation on newer models or other model families. Thus, the conclusions may be constrained by the capabilities of the base model, making cross-model generalization inadequate.

5 comments
AuthorsOpenReview ↗

Response to Reviewer uxjr – Part 1

We sincerely thank you for the positive assessment. We address each weakness and question point by point below.


Q1: Credible Signal Extraction in Open Tasks and Similarity-Threshold Sweep

A: Regarding your concern in W1 and Question 1 that "relying solely on observational string hash matching without semantic clustering... synonymous expressions or formatting changes may be mistakenly judged as new states," **constrained action loops in erroneous failure modes preserve strong within-group coverage contrast, and our 4-benchmark similarity sweep confirms that exact matching avoids severe state-merging contamination.

  • Infinite environment states vs. finite failure-mode agent behaviors: Although an open environment's global state space may be infinite, within a given task over a finite horizon TT, the agent's effective action space is finite, and becomes even more constrained when the agent falls into an erroneous failure mode (e.g., re-issuing identical failed search queries, or repeatedly clicking the same option). Repeating erroneous actions within these constrained states naturally triggers repeated observations or identical error feedback within that trajectory (oi,t+1∈Vi,t  ⟹  Pi≪1o_{i,t+1} \in \mathcal V_{i,t} \implies P_i \ll 1), whereas exploratory rollouts in the same all-failed group take diverse actions that advance into new states (Pi→1P_i \to 1) under sampling imbalance (Fig. 1, Fig. 2a). CovGPO exploits these behavioral and action differences across rollouts (σP≫0\sigma_P \gg 0) to extract credible relative signals, encourage outward exploration, and reuse already-sampled rollouts instead of discarding failed groups as in dynamic resampling (e.g., DAPO).
  • Controlled protocol & description of Table R3: We adopt exact matching (τsim=1.0\tau_{\text{sim}} = 1.0) to strictly follow GiGPO in verl-agent for fair comparison across identical anchor groups GS(s)G^S(s). To test sensitivity to synonymous or formatting variations, we replayed stored rollouts (256 trajectories on ALFWorld/ScienceWorld/WebShop; 320 on SearchQA) across string-similarity thresholds τsim∈{1.0,0.9,0.8,0.7,0.6}\tau_{\text{sim}} \in \{1.0, 0.9, 0.8, 0.7, 0.6\}, measuring Multi-Member group rate, non-zero advantage Signal rate (γ=0.95\gamma=0.95), and false state-merging Contam rate (% of total steps).

Table R3: String-Similarity Threshold (τsim\tau_{\text{sim}}) Sensitivity Sweep Across 4 Benchmarks with Qwen2.5

EnvironmentModelReturn > 0τ=1.0\tau=1.0 Multi-Memberτ=1.0\tau=1.0 Signalτ=0.9\tau=0.9 Sig / Contamτ=0.8\tau=0.8 Sig / Contamτ=0.7\tau=0.7 Sig / Contamτ=0.6\tau=0.6 Sig / ContamTrade-off (1.0→0.61.0 \to 0.6)
ALFWorld1.5B12.5%96.1%19.1%20.7% / 31.0%21.4% / 47.4%21.6% / 52.9%22.2% / 54.9%+3.1pp vs. 54.9%
ALFWorld7B18.0%97.4%35.9%36.6% / 17.4%37.9% / 25.7%38.8% / 28.8%39.4% / 29.9%+3.5pp vs. 29.9%
ScienceWorld1.5B3.1%98.6%1.7%1.7% / 2.9%1.7% / 4.4%1.7% / 4.9%1.7% / 5.4%+0.0pp vs. 5.4%
ScienceWorld7B12.9%97.2%22.0%22.7% / 8.7%22.9% / 14.0%23.1% / 18.0%23.3% / 20.5%+1.3pp vs. 20.5%
WebShop1.5B5.1%85.8%11.5%12.2% / 16.7%12.3% / 20.7%12.4% / 26.0%12.7% / 32.6%+1.2pp vs. 32.6%
SearchQA1.5B8.1%76.2%14.1%14.1% / 0.0%14.1% / 0.0%14.5% / 0.8%14.9% / 7.4%+0.8pp vs. 7.4%
SearchQA7B28.1%76.9%23.5%23.5% / 0.3%23.5% / 0.3%23.7% / 4.4%28.6% / 26.9%+5.1pp vs. 26.9%
  • Summary of findings: (1) Relaxing τsim\tau_{\text{sim}} from 1.0→0.61.0 \to 0.6 yields only +0.0 to 5.1 pp additional signal while falsely merging distinct states in 20.5% to 54.9% of steps (a 5× to 27× noise-to-signal penalty); (2) On open-ended SearchQA, τsim=1.0\tau_{\text{sim}} = 1.0 already groups 76.2% to 76.9% of steps and matches τsim∈[0.8,1.0]\tau_{\text{sim}} \in [0.8, 1.0] almost identically (0.0% to 0.3% contamination), confirming that clean exact boundaries preserve high signal-noise-ratio without collapsing on open web retrieval.

Revision: We will add this finite failure-mode analysis to Section 3.2 and include Table R3 in Appendix C.2.

AuthorsOpenReview ↗

Response to Reviewer uxjr – Part 2

Q2: Safe Fallback Under Irrelevant Outputs and Extensions to Coding Scenarios

A: Regarding your concern in W1 and Question 1 that "in code scenarios... irrelevant outputs may all be mistakenly judged as new states", we acknowledge that it is difficult to design a universal string heuristic for Agentic RL that accommodates diverse environment dynamics; CovGPO guarantees safe fallback (σP<τP  ⟹  ACovGPO=Abase\sigma_P \lt \tau_P \implies A^{\text{CovGPO}} = A^{\text{base}}) under noisy outputs and extends naturally to semantic or hidden-state matching for code.

Complex coding domains (e.g., SWE-bench) decouple surface text from program semantics: equivalent buggy states may produce different stack traces or timestamps, while a one-line fix may leave string similarity above 99%, limiting both exact and fuzzy matching. Despite these challenges, we are working toward broader applicability:

  1. Predicate-agnostic and fail-safe: Our gated fallback supports any state-equivalence rule, with formal non-interference and variance gating (σP≥τP\sigma_P \ge \tau_P). If noisy outputs make every step appear novel (∀i,Pi=1\forall i, P_i = 1), then σP=0<τP\sigma_P = 0 \lt \tau_P, automatically disabling the fallback and recovering the base learner without injecting noisy coverage advantages.
  2. Semantic and representation-level extensions: Instead of applying a universal string heuristic to code, we aim to integrate semantic clustering, policy hidden states, or learned representations tailored to coding dynamics to extract credible signals from all-failed groups.

Revision: We will incorporate the fail-safe property and discuss semantic/hidden-state extensions for coding agents in Section 3.2.


Q3: Scaling to Open-Action Web Retrieval (SearchQA) and Complex Reasoning (ScienceWorld)

A: Regarding your point in W1 and Question 2 on "scaling to more complex scenarios and open action spaces," we expanded to open-query web retrieval (SearchQA, 3B/7B) and multi-step scientific experimentation (ScienceWorld, 7B), where 76.5% to 98.3% of execution steps suffer zero reward advantage.

Table R4: Evaluation on SearchQA and ScienceWorld.

MethodNQ†TriviaQA★PopQA★HotpotQA†2Wiki★MuSiQue★Bamboogle★Avg.ScienceWorld SRScienceWorld Score
Qwen2.5-3B-Instruct
GRPO45.24 ± 0.2960.64 ± 0.0645.37 ± 0.0936.37 ± 0.1835.21 ± 0.1712.26 ± 0.3226.67 ± 0.9237.40 ± 0.12--
GRPO+CovGPO43.46 ± 0.2860.08 ± 0.0444.29 ± 0.2639.45 ± 0.2539.46 ± 0.1414.98 ± 0.6529.87 ± 2.0138.80 ± 0.29--
GiGPO44.9 ± 0.360.4 ± 0.046.7 ± 0.136.3 ± 0.235.0 ± 0.412.0 ± 0.363.0 ± 0.542.6 ± 0.0--
GiGPO+CovGPO42.4 ± 0.659.8 ± 0.145.6 ± 0.339.3 ± 0.339.6 ± 0.214.7 ± 0.764.7 ± 1.043.7 ± 0.2--
Qwen2.5-7B-Instruct
GRPO41.6 ± 2.360.7 ± 0.943.5 ± 1.439.6 ± 0.037.7 ± 2.615.2 ± 0.549.9 ± 25.241.2 ± 2.921.6 ± 2.329.3 ± 2.6
GRPO+CovGPO46.0 ± 1.363.2 ± 0.445.7 ± 0.740.4 ± 0.142.2 ± 0.118.1 ± 0.969.5 ± 1.546.5 ± 0.322.9 ± 2.330.1 ± 4.0
GiGPO40.2 ± 0.461.3 ± 0.141.8 ± 1.039.5 ± 0.237.5 ± 2.215.7 ± 0.167.9 ± 0.343.4 ± 0.322.9 ± 2.329.8 ± 4.3
GiGPO+CovGPO45.4 ± 0.363.7 ± 0.646.4 ± 0.242.7 ± 0.041.1 ± 1.118.9 ± 0.172.2 ± 1.747.2 ± 0.125.3 ± 0.936.3 ± 1.7
  • Summary of findings from Table R4: These runs validate CovGPO on unrestricted search queries (SearchQA, +3.8 to 5.3 pp at 7B) and complex multi-step state spaces (ScienceWorld, lifting 7B GiGPO from 22.9% to 25.3% SR and 29.8 to 36.3 Score). Consistently, more details onScienceWorld7B show that CovGPO actively rescues starved anchor groups (triggering on ~22.7% of step groups (~46% of execution steps)) to sustain exploration where vanilla GiGPO receives zero gradient.

Revision: We will include the complete multi-seed evaluation tables for SearchQA and ScienceWorld in Section 4 and Appendix D of the revised paper.

AuthorsOpenReview ↗

Response to Reviewer uxjr – Part 3

Q4: Base-Model Capability Interaction, Data Utilization, and Convergence Speed

A: Regarding your concern in W1 and Question 3 that "improvements may be constrained by the capabilities of the base model," limited base-model capability actually works in the opposite direction of artificially favoring CovGPO: stronger backbones naturally disengage the gate on easy tasks, while on hard tasks CovGPO maximizes rollout data utilization and accelerates convergence across model scales.

Because CovGPO activates strictly on all-failed groups (RˉGx=0\bar R_{G_x} = 0, Proposition 2), its intervention is governed solely by how frequently the policy encounters zero-reward groups on hard tasks, rather than by any model-specific artifact:

  • Smooth non-interfering convergence on solved tasks: A stronger backbone produces fewer all-failed groups on easier tasks, which naturally lowers the fallback trigger rate and causes CovGPO to smoothly converge to the base learner without negative interference, as confirmed on strong 7B HGPO baselines (ALFWorld 95.4%→95.7%95.4\% \to 95.7\%, WebShop Score 89.0) (Main Table 3).
  • Unlocking hard tasks, fuller data utilization, and faster convergence (Figure 4): Whenever any backbone (including larger or newer models) faces hard long-horizon tasks where rollouts initially fail (e.g., 7B on ScienceWorld and SearchQA, where >76%\gt 76\% of steps suffer zero advantage), vanilla group-relative RL wastes zero-reward rollouts with zero gradient (or pays 3× to 4× resampling wall-clock overhead in DAPO-MT). By extracting structured gradient signals directly from already-collected all-failed groups, CovGPO utilizes rollout data far more fully, improves learning speed, and achieves markedly faster convergence, as shown by the training dynamics curves in Figure 4 (e.g., on ALFWorld, GiGPO+CovGPO reaches 49.2% success by epoch 60 vs. 32.8% for vanilla GiGPO, accelerating convergence across both 1.5B and 7B on ALFWorld and WebShop).

Revision: We will expand the discussion of Figure 4 in Section 4.2 to emphasize how hard-task signal extraction drives data efficiency and faster convergence across model capabilities.


Q5: Cross-Model Generalization on Newer Qwen3.5 Backbones (Qwen3.5-2B and Qwen3.5-4B)

A: Regarding your point in W1 and Question 3 that "only Qwen2.5-1.5B/7B was used, without validation on newer models or other model families, making cross-model generalization inadequate," we directly evaluated CovGPO on newer-generation Qwen3.5-2B and Qwen3.5-4B backbones on ALFWorld under the GiGPO framework.

  • Setup & description of Table R5: Keeping the exact same verl-agent GiGPO hyperparameters and evaluation protocol as Main Table 1, we trained CovGPO across two model scales of the newer Qwen3.5 generation (Qwen3.5-2B and Qwen3.5-4B), complementing Qwen2.5-1.5B/3B/7B.

Table R5: Cross-Model Generalization on Qwen3.5 Backbones (ALFWorld).

ExperimentPromptingGRPOGRPO+CovGPOGiGPOGiGPO+CovGPO
Qwen3.5-2B5.3 ± 3.673.2 ± 1.282.0 ± 2.184.4 ± 1.187.5 ± 2.3
Qwen3.5-4B30.9 ± 3.2--94.9 ± 0.695.6 ± 0.8
Llama-3.1-8B23.8 ± 1.6--87.8 ± 0.988.8 ± 0.9
  • Summary of findings from Table R5: On Qwen3.5-2B, CovGPO improves ALFWorld success by +8.8 pp under GRPO (73.2% to 82.0%) and +3.1 pp under GiGPO (84.4% to 87.5%). On Qwen3.5-4B, it further improves the strong GiGPO baseline from 94.9% to 95.6%. These results extend our validation to a newer model generation. We will further evaluate Llama-family models to assess cross-family generalization.

Revision: We will include the complete multi-seed evaluation results on Qwen3.5-2B and Qwen3.5-4B in Section 4 of the revised manuscript.

Thank you again for your review. We will incorporate all the revisions discussed above into the manuscript over the next few days and do hope our response could address your concerns. If you have any further questions, we would be happy to discuss them further.

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

This paper addresses a shared problem of group-relative algorithms such as GRPO, GiGPO, and HGPO: when every rollout in a group scores zero, both the mean and the standard deviation of group rewards are zero, every trajectory gets zero advantage, and the gradient signal vanishes entirely. The authors propose CovGPO as a fallback mechanism: only in such all-failed groups is an auxiliary advantage based on first-visit observation coverage (the fraction of observations encountered for the first time in a trajectory) injected; once any reward variance appears within the group, the method falls back exactly to the base algorithm's output. Evaluated with Qwen2.5 1.5B and 7B models on ALFWorld and WebShop, the 1.5B model gains steadily in most configurations, while the 7B model gains little because the tasks are near saturation.

Critical strengths
  • The problem is precisely located: Fig. 1 and Table 16 show that zero-score groups account for 92.1% at progress index 10; Eq. 3-4 unify the degradation of the three grouping schemes into a single mechanism: when all rewards in a group are zero, the standard deviation is zero and so is every trajectory's advantage.
  • The method is lightweight and effective: Eq. 5 costs O(1) per step in expectation; for 1.5B GiGPO, success rises from 86.7 to 92.2 on ALFWorld and from 65.0 to 72.4 on WebShop, the most solid results of the paper.
  • The ablations are on point: in Sec 4.3, Shuffle/Random (78.1/83.6) versus Shuffle-h/Random-h (74.2/77.3) shows that what works is trajectory-aligned coverage, not non-zero variance or gating itself.
Critical weaknesses
  1. Reliance on exact observation equality severely limits applicability. Coverage judges novelty via a hash set of visited observation strings (Appendix C), which appears applicable only to discrete, finite-state environments. Although Sec 7 lists representation-level coverage as future work, this severely limits applicability: in environments such as SWE or web search, observations almost never repeat verbatim, so every step would be judged novel, groups would lose all contrast, the fallback would never trigger, and the method degenerates to plain GRPO.

  2. The relationship to a repeated-visit penalty is not clarified, and the corresponding baseline is missing. After group-mean normalization, what exactly distinguishes the symmetric revisit-penalty variant from the coverage bonus? Count-based and RIDE-style state-novelty signals are discussed only in related work, with no experimental comparison, leaving unanswered how coverage improves over classical exploration bonuses.

  3. The evaluation benchmarks are too simple to demonstrate the method's advantage. On ALFWorld and WebShop, baselines such as GiGPO already reach high, near-saturated performance (7B success 90.8/72.8), while the method only acts on all-failed groups that provide no gradient. A very high success rate means that most groups already contain successful trajectories after RL, so the method's value is not sufficiently demonstrated.

Questions for authors
  1. Baselines are near saturation on both benchmarks (7B: 90.8 on ALFWorld, 72.8 on WebShop), so after RL training most groups should already contain successful trajectories: what fraction of groups actually triggers the fallback in late training? Would the method show a clearer effect on a harder benchmark where all-fail groups are more common and far from saturation?

  2. Coverage novelty relies on exact string equality of observations. In environments where observations never repeat verbatim (e.g., SWE, web search), hash equality marks every step as novel, groups lose contrast, the fallback stops triggering, and the method degenerates to plain GRPO: what is the minimal assumption on observation comparability?

If the authors can address these concerns, I would consider raising my score.

10 comments
AuthorsOpenReview ↗

Response to Reviewer cnnh – Part 1

We sincerely thank you for the thorough and constructive feedback. We address each weakness and question point by point below.


Q1: Observation Repetition in Open Agentic Environments

A: Regarding your concern in W1 and Question 2 that "in environments such as SWE or web search, observations almost never repeat verbatim", infinite global environment states do not cause trajectory observations to stop repeating (Pi=1,σP=0P_i = 1, \sigma_P = 0), because task-conditioned agent actions over a finite horizon TT are finite and strongly repeat when the policy falls into erroneous failure modes.

It is important to distinguish the environment's global state space from the agent's action behavior:

  • Action-repeating failure modes (Pi≪1P_i \ll 1): While an open environment's global states may be infinite and unlikely to repeat on their own, within the same task over a finite horizon TT, the agent's effective actions are finite and can repeat, especially when the agent falls into an erroneous failure mode (e.g., repeatedly issuing the same invalid command, repeating the same failed search query, or clicking the same option). In interactive agentic environments, repeating a failed action naturally triggers repeated observations or identical error feedback within that trajectory (oi,t+1∈Vi,to_{i,t+1} \in \mathcal V_{i,t}, so Pi≪1P_i \ll 1).
  • Exploratory rollouts (Pi→1P_i \to 1): By contrast, exploratory rollouts in the same all-failed group take diverse actions that advance to new states (Pi→1P_i \to 1) under sampling imbalance (Fig. 1, Fig. 2a). Because CovGPO checks state novelty strictly against each trajectory's own history Vi,t\mathcal V_{i,t}, this contrast between exploratory rollouts (Pi→1P_i \to 1) and action-repeating failure modes (Pi≪1P_i \ll 1) preserves strong within-group variance (σP≫0\sigma_P \gg 0) instead of collapsing to σP=0\sigma_P = 0.

Revision: We will clarify this distinction between global environment states and task-conditioned failure-mode action dynamics in Section 3.2.


Q2: State-Matching Protocol and Fuzzy String-Similarity Threshold (τsim\tau_{\text{sim}}) Sweep

A: Regarding your concern in W1 that "coverage judges novelty via a hash set of visited observation strings, which appears applicable only to discrete, finite-state environments," exact state matching (τsim=1.0\tau_{\text{sim}} = 1.0) ensures a strictly controlled comparison under GiGPO's protocol, and our 4-benchmark threshold sweep demonstrates that relaxing surface string similarity introduces 5× to 27× more cross-state contamination than advantage-signal gain.

  • Controlled protocol: In our main experiments, we strictly follow GiGPO (Feng et al., 2025, arXiv:2505.10978) in the verl-agent framework, using the exact same anchor-state definition (τsim=1.0\tau_{\text{sim}} = 1.0) so all step-level methods (GiGPO, HGPO, and +CovGPO) are evaluated on identical state groups without confounding state-abstraction changes with credit assignment.
EnvironmentModelReturn > 0τ=1.0\tau=1.0 Multi-Memberτ=1.0\tau=1.0 Signalτ=0.9\tau=0.9 Sig / Contamτ=0.8\tau=0.8 Sig / Contamτ=0.7\tau=0.7 Sig / Contamτ=0.6\tau=0.6 Sig / ContamTrade-off (1.0→0.61.0 \to 0.6)
ALFWorld1.5B12.5%96.1%19.1%20.7% / 31.0%21.4% / 47.4%21.6% / 52.9%22.2% / 54.9%+3.1pp vs. 54.9%
ALFWorld7B18.0%97.4%35.9%36.6% / 17.4%37.9% / 25.7%38.8% / 28.8%39.4% / 29.9%+3.5pp vs. 29.9%
ScienceWorld1.5B3.1%98.6%1.7%1.7% / 2.9%1.7% / 4.4%1.7% / 4.9%1.7% / 5.4%+0.0pp vs. 5.4%
ScienceWorld7B12.9%97.2%22.0%22.7% / 8.7%22.9% / 14.0%23.1% / 18.0%23.3% / 20.5%+1.3pp vs. 20.5%
WebShop1.5B5.1%85.8%11.5%12.2% / 16.7%12.3% / 20.7%12.4% / 26.0%12.7% / 32.6%+1.2pp vs. 32.6%
SearchQA1.5B8.1%76.2%14.1%14.1% / 0.0%14.1% / 0.0%14.5% / 0.8%14.9% / 7.4%+0.8pp vs. 7.4%
SearchQA7B28.1%76.9%23.5%23.5% / 0.3%23.5% / 0.3%23.7% / 4.4%28.6% / 26.9%+5.1pp vs. 26.9%
AuthorsOpenReview ↗

Response to Reviewer cnnh – Part 2

  • Setup & description of Table R1: Using GiGPO's approximate string-similarity grouping function, we replayed stored rollouts (256 trajectories per setting on ALFWorld/ScienceWorld/WebShop; 320 on SearchQA) across similarity thresholds τsim∈{1.0,0.9,0.8,0.7,0.6}\tau_{\text{sim}} \in \{1.0, 0.9, 0.8, 0.7, 0.6\}. All percentages are measured over total execution steps: Return > 0 is the fraction of trajectories achieving positive return; τ=1.0\tau=1.0 Multi-Member is the fraction of steps placed in anchor groups of size ≥2\ge 2; Signal is the fraction of steps receiving non-zero discounted advantage (γ=0.95\gamma=0.95); and Contam is the cross-state contamination rate (fraction of steps grouped with genuinely distinct exact observation strings, 0.0% at τ=1.0\tau=1.0).
  • Summary of findings from Table R1:
  1. Structured interactive environments (ALFWorld, ScienceWorld, WebShop): Exact matching (τsim=1.0\tau_{\text{sim}}=1.0) already groups 85.8% to 98.6% of execution steps. Lowering τsim→0.6\tau_{\text{sim}} \to 0.6 increases steps with non-zero advantage signal by only +0.0 to 3.5 pp, while falsely merging distinct states (e.g., different rooms, receptacles, or temperatures sharing text templates) in 20.5% to 54.9% of steps (a 5× to 27× noise-to-signal ratio).
  2. Open-ended retrieval (SearchQA): Exact matching (τsim=1.0\tau_{\text{sim}} = 1.0) already places 76.2% to 76.9% of steps into multi-member groups and behaves almost identically across τsim∈[0.8,1.0]\tau_{\text{sim}} \in [0.8, 1.0] (0.0% to 0.3% contamination), because repeating a failed query returns identical text (oi,t+1∈Vi,to_{i,t+1} \in \mathcal V_{i,t}) whereas issuing a distinct query retrieves passages with less than 0.8 text overlap. Lowering τsim→0.6\tau_{\text{sim}} \to 0.6 adds only +0.8 to 5.1 pp signal at the cost of 7.4% to 26.9% false passage merging.
  3. Unlocking all-failed groups requires preserving a high signal-to-noise ratio via clean state boundaries so that repeated search/action loops are penalized without corrupting step-level credit across distinct states.

Revision: We will include Table R1 and this signal-to-noise ratio analysis in Appendix C.2 and reference it in Section 4.3.


Q3: Applicability Boundary and Extensions in Complex Coding Domains (e.g., SWE)

A: Regarding your point in W1 that "although Sec 7 lists representation-level coverage as future work, reliance on exact observation equality severely limits applicability in environments such as SWE," raw string matching indeed reaches its boundary in repository-level coding tasks where surface text decouples from program semantics, whereas CovGPO is predicate-agnostic and extends naturally to semantic or representation-level state abstractions.

Moving to complex coding tasks like SWE-bench introduces a domain shift where equivalent buggy states may produce different stack traces, while two files differing by a single-line fix still share >99%\gt 99\% string similarity, making raw string matching unsuitable for extracting high signal-noise-ratio signals. However, this reflects the boundary of surface string matching in code instead of a limitation of CovGPO's core mechanism. Following GiGPO, our paper focuses on interactive agent environments and demonstrates that (unlike dynamic resampling methods such as DAPO that discard all-failed groups and waste rollout compute on hard tasks) CovGPO reuses already-collected failed rollouts whenever state comparisons remain credible, structured, and gated against interfering with task rewards. Because agentic RL algorithms should adapt state representations to specific environment dynamics instead of relying on a single universal string heuristic, future extensions to coding agents can plug semantic state representations (such as execution/test-feedback signatures, abstract-grouping functions, policy hidden states, or learned embeddings) directly into CovGPO's non-interfering fallback framework.

Revision: We will add an explicit discussion of this coding applicability boundary and semantic/representation-level extensions in Section 3.2.


Q4: Minimal Formal Assumption on Observation Comparability

A: Regarding your direct question in Question 2 asking "what is the minimal assumption on observation comparability," over a finite horizon TT, observations only need to be comparable enough within the same trajectory to distinguish local action repetition (oi,t+1∈Vi,to_{i,t+1} \in \mathcal V_{i,t}) from state progression (oj,t+1∉Vj,to_{j,t+1} \notin \mathcal V_{j,t}) across at least one pair of rollouts in GxG_x.

  • Formal formulation: For an all-failed group GxG_x (RˉGx=0\bar R_{G_x} = 0) of rollouts with horizon TT, the minimal condition for CovGPO to extract a non-zero learning signal is:

For some τi,τj∈Gx\tau_i, \tau_j \in G_x, there exists a step tt such that oi,t+1∈Vi,to_{i,t+1} \in \mathcal V_{i,t} (a looping rollout, implying Pi≤1−1/TP_i \le 1 - 1/T), and Pj>PiP_j \gt P_i (an exploratory rollout, e.g., Pj=1P_j = 1).

AuthorsOpenReview ↗

Response to Reviewer cnnh – Part 3

  • Formal guarantees: This minimal condition directly guarantees two complementary properties:
  1. Breaking the credit trap (when satisfied): Since Pj−Pi≥1T>0P_j - P_i \ge \frac{1}{T} \gt 0, within-group dispersion is strictly positive (σP(Gx)≥τP>0\sigma_P(G_x) \ge \tau_P \gt 0 for τP≤1T∣Gx∣\tau_P \le \frac{1}{T\sqrt{|G_x|}}), yielding AjP>0>AiPA_j^P \gt 0 \gt A_i^P to reward outward exploration over local looping whenever σR(Gx)=0\sigma_R(G_x) = 0 (Proposition 1).
  2. Safe fallback (when violated): If observations never match even under repeated actions (∀i∈Gx, Pi=1\forall i \in G_x,\, P_i = 1), then σP(Gx)=0<τP\sigma_P(G_x) = 0 \lt \tau_P, and the variance gate 1[σP(Gx)≥τP]=0\mathbf{1}[\sigma_P(G_x) \ge \tau_P] = 0 automatically turns off the fallback and reduces CovGPO exactly to the base learner without injecting noise (Proposition 2).

Revision: We will incorporate this formal minimal assumption and its guarantee proof into Section 3.2 and Appendix B.


Q5: Mathematical Equivalence with the Symmetric Revisit Penalty

A: Regarding your question in W2 asking "after group-mean normalization, what exactly distinguishes the symmetric revisit-penalty variant from the coverage bonus," under length normalization and group standardization, the symmetric revisit penalty produces pointwise identical advantages (AiQ≡AiPA_i^Q \equiv A_i^P) to our first-visit coverage score.

For any trajectory τi\tau_i of length TiT_i, let Qi=−1Ti∑t=1Ti1[oi,t+1∈Vi,t]Q_i = -\frac{1}{T_i}\sum_{t=1}^{T_i} \mathbf{1}[o_{i,t+1} \in \mathcal V_{i,t}] denote the length-normalized symmetric revisit penalty. Since every step t∈{1,…,Ti}t \in \{1,\dots,T_i\} is partitioned into either a first visit (oi,t+1∉Vi,to_{i,t+1} \notin \mathcal V_{i,t}) or a revisit (oi,t+1∈Vi,to_{i,t+1} \in \mathcal V_{i,t}), we have the exact affine identity Qi=Pi−1Q_i = P_i - 1. Shifting all scores within group GxG_x by the constant -1 leaves both the mean-centered differences Qi−QˉGx=Pi−PˉGxQ_i - \bar Q_{G_x} = P_i - \bar P_{G_x} and the group standard deviation σQ(Gx)=σP(Gx)\sigma_Q(G_x) = \sigma_P(G_x) invariant, yielding pointwise identical normalized advantages (AiQ≡AiPA_i^Q \equiv A_i^P). A discrepancy only arises if one uses unnormalized revisit counts, which conflate state repetition with trajectory length TiT_i, precisely the reason we normalize by TiT_i.

Revision: We will include this formal equivalence proof between the length-normalized revisit penalty and first-visit coverage in Section 3.2 and Appendix B.1.


Q6: Controlled Empirical Comparison to Count-Based and RIDE Exploration Bonuses

A: Regarding your concern in W2 that "count-based and RIDE-style state-novelty signals are discussed only in related work, with no experimental comparison, leaving unanswered how coverage improves over classical exploration bonuses," Main Table 2 directly ablates both defining components of classical episodic count-based and RIDE bonuses: persistent reward addition (Always-on coverage) and single-step state change (Obs-Change) and both underperform conditional first-visit CovGPO.

Classical episodic count-based bonuses and RIDE (Raileanu & Rocktäschel, 2020), which rewards single-step state change 1[ot+1≠ot]\mathbf{1}[o_{t+1} \neq o_t] scaled by episodic visit counts 1/Nep(st+1)1/\sqrt{N_{\text{ep}}(s_{t+1})}, have two defining features: (1) they measure episode-local state novelty or single-step change, and (2) they add this intrinsic bonus persistently to all groups throughout training (Rtotal=Rtask+λRintR^{\text{total}} = R^{\text{task}} + \lambda R^{\text{int}}). Our paper isolates and tests both components in controlled group-relative RL ablations:

  • Persistent ("Always-on") bonus vs. conditional fallback ( in Main Table 2 & Appendix A.4): In group-relative RL, once a group contains successful rollouts (RˉGx>0\bar R_{G_x} \gt 0), persistently adding an exploration bonus distorts group standardization and can invert the advantage ranking between a short, efficient success and a long, wandering rollout that visits more states (formally proved in Appendix A.4). Main Table 2 ("Always-on coverage") directly evaluates this persistent count-based paradigm by applying the exact same episode-local novelty score to all groups regardless of RˉGx\bar R_{G_x}: it violates Proposition 2, degrades performance below the base learner on GRPO-ALFWorld(68.3% vs. 72.8% base vs. 74.5% conditional CovGPO), and clearly trails conditional CovGPO on GiGPO-WebShop (78.5 / 68.8 vs. 85.6 / 72.4).
  • Single-step state change vs. episodic first-visit filter ("Obs-Change" in Fig. 3c & Main Table 2): Isolating RIDE's single-step state-change indicator 1[oi,t+1≠oi,t]\mathbf{1}[o_{i,t+1} \neq o_{i,t}] (Obs-Change) without episodic first-visit filtering allows the policy to earn bonus by cycling back and forth between two states, underperforming first-visit coverage on GiGPO-ALFWorld (88.9% vs. 92.2% overall, and 81.3% vs. 90.9% on hard Pick2).

Revision: We will explicitly connect "Always-on coverage", "Obs-Change", and Appendix A.4's ranking-inversion proof to classical count-based / RIDE bonuses in Main Tab. 2 and Sec. 4.3.


Comments on the paper

2 comments
AuthorsOpenReview ↗

Summary of Rebuttal – Part 1

We thank the reviewers and the Area Chair for their time and constructive feedback. Below we summarize the main points of the discussion, our core contributions, the additional evidence provided during the rebuttal, and the revisions in the updated PDF.

Strengths Noted by the Reviewers

  • Clear problem formulation: Precisely identifies the all-failed credit trap where group-relative advantages vanish across grouping granularities (cnnh, uxjr).
  • Lightweight and non-interfering design: Plug-and-play integration (O(1)O(1) per step, no extra models or rollouts) that reverts exactly to the base advantage once reward variance returns (cnnh, uxjr, qJMP).
  • Solid empirical evidence and controls: Consistent gains over GRPO, GiGPO, and HGPO, supported by targeted signal-substitution and gating ablations (cnnh, uxjr, qJMP).

Main Points and Our Responses

1. Core Contribution: Extracting Credible Signals from Degenerate All-Failed Rollouts (cnnh, uxjr, qJMP).

  • Compute reuse without overhead. Instead of discarding zero-variance groups via costly dynamic resampling (e.g., DAPO-MT, which incurs 3–4×3\text{--}4\times wall-clock overhead) or training auxiliary reward/world models, CovGPO recycles already-collected all-failed trajectories with O(1)O(1) per-step overhead (0.5870.587 vs. 0.5850.585 s/iter).
  • Strict non-interference across granularities. CovGPO activates strictly when all rollouts in a group receive zero outcome reward and reverts pointwise to the base advantage once reward variance emerges (Proposition 3), working seamlessly across trajectory-level (GRPO) and step-level (GiGPO, HGPO) optimizers.

2. Observation Matching, Semantic Redundancy, and Applicability Boundaries (cnnh, uxjr, qJMP).

  • Minimal comparability & fail-safe gating. Over a finite horizon with an agent trajectory, erroneous failure modes still repeat actions and observations even in open environments. We formalized the minimal comparability condition (Proposition 2) and proved that when observations never repeat, the variance gate safely reverts CovGPO to the base learner without injecting noise (Proposition 3).
  • 4-benchmark string-similarity sweep. Offline replay across ALFWorld, ScienceWorld, WebShop, and SearchQA shows exact matching (τsim=1.0\tau_{\text{sim}}=1.0) already groups 85.8–98.6%85.8\text{--}98.6\% of steps on structured tasks and 76.2–76.9%76.2\text{--}76.9\% on open-ended SearchQA. Relaxing τsim\tau_{\text{sim}} to 0.60.6 adds only 0.0–5.10.0\text{--}5.1 pp non-zero advantage steps while **introducing 20.5–54.9%20.5\text{--}54.9\% cross-state contamination—a 5–27×5\text{--}27\times noise-to-signal penalty **(Table 17, Appendix D.7).
  • Direct semantic-matching audit. Replacing exact matching with L2-normalized hidden-state cosine similarity across three trained encoders (Llama-3.1-8B-Instruct, Qwen3.5-2B, Qwen3.5-4B) shows 90%90\% (ALFWorld) and 99%99\% (WebShop) of merged pairs are genuinely distinct states. At τcos⁡=0.99\tau_{\cos}=0.99, coverage rankings closely align with exact matching (ρ=0.71–0.99\rho = 0.71\text{--}0.99 on ALFWorld, ScienceWorld, SearchQA-1.5B) while adding only 0.0–2.70.0\text{--}2.7 pp step-level signal; loosening to τcos⁡=0.90\tau_{\cos}=0.90 causes severe encoder sensitivity (ρ\rho drops from 0.530.53 to −0.03-0.03) (Tables R9–R11). We note that this is an initial hidden-state probe, and more carefully designed semantic representations warrant further exploration.
  • Scope and coding-domain boundary. Following GiGPO, our work targets interactive agentic environments instead of repository-level coding (e.g., SWE-bench), where surface text decouples from program semantics. Consistent with our core contribution (Point 1), our focus is demonstrating how to extract credible, non-interfering learning signals from degenerate all-failed rollouts; CovGPO's gated architecture is predicate-agnostic and can naturally pair with execution-feedback or representation-level state abstractions if extended to coding domains.
AuthorsOpenReview ↗

Summary of Rebuttal – Part 2

3. Benchmark Saturation, Harder Tasks, and Cross-Model Generalization (cnnh, uxjr, qJMP).

  • Harder, far-from-saturation benchmarks. Offline replay confirms 76.5–98.3%76.5\text{--}98.3\% of steps on SearchQA and ScienceWorld receive zero reward advantage under vanilla GiGPO. Full multi-seed RL training (Table 3) shows consistent gains: on SearchQA with Qwen2.5-7B-Instruct, CovGPO lifts GRPO from 41.2→46.541.2 \to 46.5 (+5.3+5.3 pp) and GiGPO from 43.4→47.243.4 \to 47.2 (+3.8+3.8 pp), alongside gains on Qwen2.5-3B-Instruct (GRPO 37.4→38.837.4 \to 38.8, GiGPO 42.6→43.742.6 \to 43.7). On ScienceWorld with Qwen2.5-7B-Instruct, CovGPO improves GiGPO from 22.9→25.322.9 \to 25.3 SR and 29.8→36.329.8 \to 36.3 Score (+6.5+6.5), complementing our multimodal SokoBan (Qwen2.5-VL-3B-Instruct, +2.0–6.3+2.0\text{--}6.3 pp, Table 5) results.
  • Newer and cross-family backbones. On ALFWorld (Table 4), CovGPO generalizes across model generations and families: Qwen3.5-2B (GRPO 73.2→82.073.2 \to 82.0, GiGPO 84.4→87.584.4 \to 87.5), Qwen3.5-4B (GiGPO 94.9→95.694.9 \to 95.6), and Llama-3.1-8B (GiGPO 87.8→88.887.8 \to 88.8).
  • Trigger decay & local step-group starvation. On ALFWorld, fallback triggering naturally decays from 29.4%29.4\% early in training to 11.1%11.1\% (epoch 30) and 4.7%4.7\% (epoch 150), driving faster early convergence (49.2%49.2\% vs. 32.8%32.8\% at epoch 60). Even at 86.7%86.7\% trajectory success (Qwen2.5-1.5B-Instruct GiGPO), 74.1%74.1\% of local anchor-state step groups still score zero, which CovGPO reduces to 43.6%43.6\% (−30.5-30.5 pp) (Table 19, Appendix D.9).

4. Revisit Penalties, Exploration Baselines, and Theoretical Grounding (cnnh, qJMP).

  • Equivalence and exploration controls. Under length normalization and group standardization, a symmetric revisit penalty (Qi=Pi−1Q_i = P_i - 1) yields pointwise identical advantages (AiQ=AiPA_i^Q = A_i^P). Table 2 and Figure 6c directly ablate persistent count-based bonuses (Always-on coverage, dropping Qwen2.5-1.5B-Instruct GRPO ALFWorld from 74.5→68.374.5 \to 68.3) and RIDE-style single-step change (Obs-Change, 88.988.9 vs. 92.292.2 on GiGPO ALFWorld), confirming the necessity of conditional first-visit gating.
  • Scope of theoretical claims. Our theory guarantees group-level non-interference (Proposition 3) and bounded fallback updates (Proposition 4, Lemma 4), without assuming higher coverage implies higher continuation value. Section 5.3 empirically validates the causal chain from reduced repetition to earlier task success.

5. Presentation (qJMP). We converted fragmented colon-led lists into cohesive narrative prose and integrated Related Work comparisons directly into the method and ablation sections.

Discussion Status

Reviewer qJMP followed up on Nov 18 noting remaining concerns regarding semantic redundancy (W1) and the theoretical link to task performance (W3); we posted a follow-up response with the direct semantic-matching audit (Tables R9–R11) and clarified the theoretical scope. Reviewers cnnh and uxjr have not yet replied to our responses and follow-up notes; notably, Reviewer cnnh indicated a willingness to raise their score if their concerns were addressed, though we have not yet received further feedback.

Revisions in the Updated PDF (shown in blue)

  • Introduction & Related Work (Secs. 1–2): Tightened narrative flow and integrated comparisons with persistent exploration bonuses and dynamic resampling. (qJMP)
  • Method (Sec. 4): Added Proposition 2 (minimal comparability), clarified Proposition 3 (non-interference) and the coding-domain boundary. (cnnh, uxjr, qJMP)
  • Experiments (Sec. 5): Added full RL results on SearchQA and ScienceWorld (Table 3), cross-generation/cross-family validation on Qwen3.5-2B/4B and Llama-3.1-8B (Table 4), and explicit connections to count-based/RIDE ablations (Sec. 5.3). (cnnh, uxjr, qJMP)
  • Appendix:
    • A.8: formal analysis of why always-on coverage conflicts with task reward. (cnnh, qJMP)
    • D.7–D.9: 4-benchmark string-similarity sweep (Table 17), subtask all-failed breakdown (Table 18), and trigger-rate decay diagnostics (Table 19). (cnnh, uxjr, qJMP)

We thank the reviewers again for their constructive feedback, which has substantially strengthened both the empirical evidence and clarity of the paper.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.