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

• Sparse terminal feedback leaves most intermediate decisions without direct task feedback, making credit assignment over long agentic trajectories difficult.Source: §1 · p. 1
• In hard long-horizon tasks, low-effect actions remain over-sampled while effective actions are under-sampled, producing all-failed groups whose shared outcomes cannot correct that imbalance.Source: §1 · pp. 1–2
• GRPO, GiGPO, and HGPO miss behavioral differences among failed trajectories because their reward-based trajectory or step comparisons yield identical advantages.Source: §1 · pp. 1–2
• CovGPO uses first-visit observation coverage as a fallback signal in all-failed groups and restores the original reward-based advantage when outcome variation exists.It credits transitions to observations not previously visited in the trajectory.Source: §1 · pp. 2–3
• CovGPO consistently boosts strong group-based baselines on ALFWorld and WebShop with Qwen2.5-1.5B/7B-Instruct models.Source: §1 · p. 3

• Group-based methods refine credit assignment through trajectory, state, history, or graph comparisons, but assume a usable comparison signal exists.Source: §2 · p. 3
• Remedies for outcome-degenerate groups include resampling, scaffolding, virtual baselines, heuristic step rewards, and intermediate verifiers, with some relying on auxiliary supervision or domain-specific scoring.Source: §2 · p. 3
• Progress and exploration approaches use learned progress rewards, process reward models, information gain, or state-change bonuses.Source: §2 · p. 3
• Unlike persistent or model-based auxiliary signals, CovGPO applies model-free first-visit coverage only when within-group outcome rewards provide no ordering.Source: §2 · p. 4

• Tasks provide delayed terminal rewards, with binary completion in ALFWorld and fractional matching in WebShop, leaving intermediate transitions unrewarded.Source: §3 · p. 4
• Group-based RL samples multiple trajectories for a task and estimates advantages from their relative outcomes; GiGPO and HGPO also compare steps grouped by state or interaction history.Source: §3 · p. 4
• An all-failed rollout group contains no successful trajectory, so its members receive zero feedback and within-group reward variance vanishes.Source: §3 · p. 4

4 Training Agents with CovGPO for Long-Horizon Agentic Tasks

• CovGPO combines a first-visit coverage score with a conditional switch that uses coverage only when reward-based comparisons degenerate.The overview samples K rollouts from the same initial state and prompt, then normalizes coverage scores within an all-failed group.Source: §4 · p. 4, Figure 3 · p. 5

4.1 Why the Trap Is Exact

• When an all-failed group has uniform zero outcomes, reward-based advantages vanish exactly; under the fixed-policy chain model, the expected groups until a success is at least ε^-H/K.Updates from other groups can still improve the policy.Source: §4.1 · pp. 4–5

4.2 First-Visit Coverage Score

• At equal trajectory lengths, first-visit coverage orders trajectories by distinct observations, while repetitions and cycles earn no added credit.For unequal lengths it compares coverage rates, but coverage does not determine which failed trajectory is closer to success.Source: §4.2 · pp. 5–6

4.3 Conditional Advantage Algorithm

• The conditional fallback injects coverage when reward advantages vanish and coverage varies, while leaving informative groups unchanged.The analysis characterizes this as a strict extension at fixed policy parameters, not as identical subsequent training data or trajectories.Source: §4.3 · p. 6

5.1 Experiment Setup

• Experiments use Qwen2.5-1.5B/7B-Instruct, rollout groups of size K=8, 150 training epochs, and a fallback ceiling λaux=0.3.Evaluation uses held-out tasks and reports success rate with mean±standard deviation over three seeds, except the specified five-seed ALFWorld entry.Source: §5.1 · p. 7

5.2 Main Results

• At 1.5B, GiGPO+CovGPO raises success on hard ALFWorld subtasks Look, Cool, and Pick2 from 67.5→74.5, 79.8→90.6, and 76.4→90.9.The easy Pick subtask is saturated; improvements concentrate where the base policy almost never succeeds and all-failed groups dominate.Source: §5.2 · p. 7
• CovGPO improves group-based baselines across ALFWorld and WebShop at both model scales, with aggregate gains reported for most settings.The 1.5B results include ALFWorld gains of 72.8→74.5, 86.7→92.2, and 92.8→95.7; WebShop success gains are 56.8→60.9, 65.0→72.4, and 71.5→75.7.Source: §5.2 · pp. 7–8, Table 1 · p. 8
• Always-on coverage underperforms conditional CovGPO on several settings, including GRPO–ALFWorld and both GiGPO–WebShop metrics.Always-on coverage scores 68.3 versus 72.8 for GRPO–ALFWorld, and 78.5/68.8 versus 85.6/72.4 for GiGPO–WebShop; the authors state gating is necessary for the exact guarantee.Source: §5.2 · p. 8, Table 2 · p. 9
• On 1.5B ALFWorld, GiGPO+CovGPO reaches 49.2% success at epoch 60 versus GiGPO’s 32.8% in the reported single-seed trace.From epochs 10 to 150, its zero-score step-group fraction falls from 92.0% to 43.6%, while fallback use falls from 29.4% to 4.7%.Source: §5.2 · pp. 8–9, Figure 4 · p. 9
• CovGPO adds negligible measured computation cost, with advantage computation at 0.587 versus 0.585 seconds and total iteration time at 184.0 versus 171.8 seconds.The authors characterize these measurements as negligible added cost, not an intrinsic speedup.Source: §5.2 · p. 9, Figure 5 · p. 10

5.3 Why CovGPO Works

• Shuffled or random fallback scores underperform trajectory-aligned coverage, while CovGPO shifts probability toward mid-band state-changing actions and penalizes low-effect actions.In the controls, Shuffle-h, Random-h, Shuffle, and Random score 74.2%, 77.3%, 78.1%, and 83.6%, respectively, versus 92.2% for CovGPO; aggregate redistribution alone does not ensure higher success.Source: §5.3 · pp. 9–10, Figure 6 · p. 10
• Coverage is an exploration heuristic rather than an established continuation-value proxy, and λaux=0.3 achieves 92.2% success within 2.3 percentage points of the single-seed peak.The diagnostics report 4.47% versus 3.25% success when resuming higher- versus lower-coverage failed trajectories; the authors therefore restrict coverage to fallback use when reward comparisons offer no distinction.Source: §5.3 · p. 10

6 Conclusion

• CovGPO ranks trajectories in all-failed groups by first-visit observation coverage, using existing interactions without extra rollouts, learned reward models, or intermediate supervision.It is described as a lightweight, model-free framework compatible with trajectory-, state-, and history-level baselines.Source: §6 · p. 10
• CovGPO consistently improves over GRPO, GiGPO, and HGPO across ALFWorld and WebShop and Qwen2.5-1.5B/7B model scales.The conclusion also reports suppression of repetitive, state-invariant actions.Source: §6 · p. 11
• The findings suggest structured failures can supply low-cost conditional credit without requiring an auxiliary behavioral statistic to act as a calibrated value estimator or success proxy.The conclusion identifies representation-level coverage metrics and adaptive disengagement as possible avenues for future agent learning.Source: §6 · p. 11

Supplementary Material

• The supplied section is identified as supplementary material for “Learning from All-Failed Groups via First-Visit Coverage in Long-Horizon Agentic Tasks.”Source: Supplementary Material for “Learning… · p. 14

7.1 Proof of Proposition 4.1

• When every rollout in a group fails, reward-relative trajectory and step advantages vanish; under a fixed policy, the first successful group arrives after a geometric waiting time with parameter q = 1 − (1 − ε^H)^K.The waiting-time result concerns repeated sampling from the specified fixed policy, separately from the zero-advantage result on collected all-failed groups.Source: §7.1 · pp. 16–17

7.2 Coverage Exactness

• At equal trajectory length, first-visit coverage orders trajectories exactly by distinct-observation count, ignores no-op repetitions and cyclic revisits, and yields a task-specific necessary coverage threshold for success.The threshold depends on the task, observation representation, and length domain; sufficient coverage need not complete the task, and coverage rate need not order raw counts across unequal lengths.Source: §7.2 · pp. 17–18

7.3 The Coverage Deficit Bounds the Remaining Work

• For a prefix admitting a valid, reset-free successful continuation within budget, its coverage deficit lower-bounds the additional distinct observations needed, but does not order continuation values or actual remaining work.Irreversibly terminated failures do not satisfy the continuation hypothesis; for equal positive prefix lengths, higher coverage weakly lowers the deficit bound.Source: §7.3 · p. 18

7.4 Ordering under Coverage-Monotone Continuation

• Under the additional coverage-monotone continuation assumption, equal-length triggered groups have centered coverage advantages ordered with coverage and nonnegative empirical covariance with continuation success probability.This is a fixed-group ordering result, not a policy-gradient improvement guarantee; the assumption is neither required by the algorithm nor implied by the deficit bound.Source: §7.4 · pp. 18–19

7.5 Proof of Proposition 4.2

• The ideal exact-zero fallback preserves reward-relative gradients outside triggered components, but the deployed near-zero gate inherits this non-interference guarantee only under a score-gap condition.Without that condition, normalization can make a small nonzero score contrast large enough for the wrapper to replace it with coverage advantages or zero.Source: §7.5 · pp. 19–21

7.6 The Unnormalized REINFORCE Identity and Groupwise Normalization

• The unnormalized failure-conditioned score identity is stated before conditioning on coverage dispersion or normalizing by its random standard deviation; for a fixed admitted group, the unclipped score contribution is a positive scale times centered coverage.The scale is c(Gx) = λ/(σP(Gx) + ϵ) > 0.Source: §7.6 · pp. 21–22
• Equation (56) applies to the auxiliary unnormalized statistic, while the algorithm uses dispersion-gated, normalized advantages.The numerical wrapper additionally uses batch-dependent λeff and numerical eligibility.Source: §7.6 · p. 23
• Random scaling and selection cannot be removed from an expectation by Equation (56), and length-weighted or clipped losses and dependent step-comparison groups require separate algorithms.Positive scaling preserves a fixed admitted group’s unweighted score-sum direction.Source: §7.6 · p. 23

7.7 A Counterexample to Fallback-Only Escape Guarantees

• The fallback’s expected frontier-logit update can be negative even among all-failed trajectories, so positive coverage dispersion does not guarantee positive frontier drift.The example gives conditional covariance −1/36; successful-group reward updates are separate from this failed-group calculation.Source: §7.7 · p. 23

7.8 A Static Norm Bound for the Gated Fallback

• The auxiliary contribution is zero outside the fallback gate, and a uniform bound requires an additional score-norm condition; bounded coverage alone supplies no such condition.With that condition, fixed-λ auxiliary contributions are bounded by λM*; this is not a bound on the full base-plus-fallback gradient.Source: §7.8 · p. 24

7.9 Disengagement Bounds: Two Conditions

• The trigger-probability factorization relies on independence across rollouts, not independence between reward eligibility and coverage dispersion; dependent selected groups need another sampling assumption.Source: §7.9 · p. 25

7.10 Why the Fallback Must Be Conditional: Reward–Progress Conflict

• Coverage-rate rankings can conflict with binary reward rankings: a short, efficient success may score below a long, wandering failure, so the mixed-outcome fallback preserves reward advantages.The passages distinguish advantage rankings from policy-gradient effects, which also depend on trajectory scores and the loss.Source: §7.10 · p. 25

7.11 A Worked all-failed Group: Instantiating the Main-Text Results

• The worked group’s Obs-Change score ranks the cycler first, while first-visit coverage credits only 2 of its 9 observation changes.These are score rankings, not certified task-value rankings.Source: Table 4 · p. 26, §7.11 · p. 26

8.1 Computing Details

• CovGPO is a drop-in advantage-computation replacement that leaves rollout collection, the optimizer, and the model unchanged.Progress scores use a per-trajectory hash set of visited observation strings, with expected O(1) membership lookups per step during CPU-side advantage estimation.Source: §8.1 · p. 27

8.2 Reference Advantage Computation

• The reference algorithm inserts the initial observation before acting and processes each next observation, including a terminal one, as an exact environment-emitted string.Trajectory length counts executed actions, including a terminating action.Source: §8.2 · p. 27, §8.3 · p. 28

8.3 Deployed Per-Update Scaling and Conformance Boundary

• The deployed wrapper uses a batch-dependent effective scale and numerical eligibility gate, so its behavior can differ from the ideal exact-zero algorithm.The gate tests whether max_i |y_i| < 10^-3; the effective scale is λ_aux q_fail, where q_fail is measured over groups in the update.Source: §8.3 · pp. 28–29
• Inherited trajectory coverage rates can credit a no-op positively in step-level anchor groups, and the authors report no unbiasedness claim for this fallback.The rate is deliberately coarse; its use is limited to all-failed comparisons, bounded by a configured scale ceiling, and triggered less often as rewarded rollouts reappear.Source: §8.3 · pp. 29–30

8.4 Training Hyperparameters

• Within matched baseline–CovGPO pairs, rollout, optimization, and evaluation hyperparameters are held fixed so the advantage algorithm is the controlled difference.The section distinguishes configured constants from quantities computed per update.Source: §8.4 · p. 30

8.5 ALFWorld; 8.6 WebShop

• ALFWorld uses six task categories, held-out unseen test tasks, and a 50-step budget; WebShop uses a 15-step budget and reports product-match scores and exact success.WebShop exact success thresholds the terminal score at 1.0.Source: §8.5 · p. 30, §8.6 · p. 30

8.7 Progress Measure across Environments

• The same first-visit measure checks novelty in visited observation strings across ALFWorld game-state text and WebShop page-summary text, without environment-specific filtering.Coverage is used only to modify training advantages, not at inference time.Source: §8.7 · p. 31, §8.8 · p. 31

8.8 Evaluation and Reporting Protocol

• Main results are reported as mean±standard deviation over independent seeds, and ALFWorld and WebShop retain their specified success and product-match evaluation metrics.Most main-table entries use three seeds; the 1.5B GiGPO+CovGPO ALFWorld entry and hyperparameter sweeps use five.Source: §8.8 · p. 31

9.1 Base-Policy Action Audit

• 100% of audited no-change actions fell in the head band, while 83.2% of state-changing actions fell in the mid/low bands.The audit covered 27 ALFWorld games and 463 decision records; its labels indicate observation change, not oracle task value.Source: Table 6 · p. 32, §9.1 · p. 32

9.2 Sampler-Side Intervention: Band-Conditioned Sampling; 9.3 Action-Level Audit: Metric Definitions and Rationale

• The sampler intervention redistributed rollout probability toward mid- and low-band candidates, and action-level audits tracked policy shifts against novelty and oracle-progress measures.The action-level audit used one random seed and a fixed support of 2,835 executed-action records; novelty alignment is target-related because novelty enters the optimized score.Source: §9.2 · p. 32, §9.3 · p. 33

9.2 Sampler-Side Intervention: Band-Conditioned Sampling

• 13.3 pp peak success improvement came from combining band-conditioned sampling and advantage repair, versus 12.5 pp for repair alone and 6.3 pp for band-only sampling.The combination was less than 1 pp above repair alone in this 30-epoch, single-seed run.Source: §9.2 · p. 32, Table 7 · p. 33

9.3 Action-Level Audit: Metric Definitions and Rationale

• At epoch 150, CovGPO exceeded Shuffle-h by 0.032 in oracle-progress correlation and 2.357 nats in no-op suppression, but fixed-support diagnostics do not explain held-out success differences.The paired 95% intervals were [0.007, 0.054] and [1.701, 3.021], respectively; final novelty alignment did not order methods by final success.Source: §9.3 · p. 33

10.1.1 SokoBan: Implementation and Evaluation Linkage

• The visual SokoBan variant is an exploratory extension: its progress indicator also uses native step rewards, and key aliasing can undercount first visits.The results do not isolate first-visit coverage from observation-key artifacts.Source: §10.1.1 · p. 35

10.2 What the Coverage Score Tracks: Protocol and Full Results

• Controlled coverage–progress estimates include zero, and paired continuation tests detect no overall advantage for higher-coverage states at either budget.These measurements do not validate coverage as a progress or continuation-value estimate, but do not establish that it lacks such information.Source: §10.2 · pp. 35–37, Table 10 · p. 36

10.3 Per-Category Snapshots across Training Progress

• Validation success increases across all six ALFWorld categories as training progresses, while the supplementary analysis also reports DAPO-MT per-category results.The available passage gives the trend, not the table’s category-specific values.Source: §10.1 · p. 34, §10.3 · p. 37, Table 11 · p. 37

10.4 Per-Category Breakdown of Signal-Analysis Variants

• Score-only Random and Shuffle reach 83.6% and 78.1%, versus 77.3% and 74.2% for horizontal counterparts; protocol differences prevent isolating the gate’s contribution.Obs-Change improves over GiGPO but remains below CovGPO overall, with its largest reported deficit on Pick2 (81.3% vs. 90.9%).Source: §10.4 · p. 37, Table 12 · p. 38, Table 13 · p. 38

10.5 Novelty/Revisit Decomposition of the Obs-Change Anomaly

• Coverage and revisit policy shifts differ by aggregation: pooled mid-band shifts favor more novelty for Obs-Change, but Pick2 shows the opposite signs from CovGPO.The single-seed, fixed-support decomposition does not establish which behavior causes the success-rate difference or mediation by reduced cycling.Source: §10.5 · p. 38, Table 14 · p. 39

10.7 Fallback-Scale Sweep

• The ALFWorld fallback-scale sweep is non-monotone: results at λaux 0.5 and 0.7 are 78.3% and 83.6%, both below the reported 86.7% base.The 0.1 result is single-run, and fixed implementation tolerances were not swept.Source: §10.7 · p. 39, Table 15 · p. 39

10.8.1 Zero-Score Group Rates across Training Progress

• In the single-run GiGPO traces, zero-score step groups decline from 92.0% to 43.6%, while the baseline declines from 92.1% to 74.1%.The reported GiGPO trigger rate also falls from 29.4% at progress index 10 to 4.7% at 150; this alone does not establish a monotonic multiplier hand-off.Source: §10.8.1 · p. 39, §10.8.2 · p. 39, Table 16 · p. 40

10.8.4 Fallback Runtime Diagnostics: Definitions and Additional Curves

• Figure 7 reports single-run traces, with trigger frequency, conditional repair magnitude, and group counts as distinct diagnostics; a separate HGPO summary also reports low trigger frequency.Among all-failed groups at progress index 30, the reported category shares are P(category | all-failed), not category-specific failure rates.Source: §10.8.4 · p. 40, §10.8.3 · p. 40, Table 17 · p. 40

11 Case Study: all-failed Groups

• CovGPO’s case studies compare first-visit exploration coverage among trajectories in all-failed groups, where conventional reward-relative updates have degenerate signals.Figure 7 separately reports runtime diagnostics for GiGPO anchor-state groups; its faint lines are raw values and bold lines are smoothed values, not uncertainty bands.Source: §11 · pp. 40–41, Figure 7 · p. 41

11.1 ALFWorld: Heat an Egg

• In the ALFWorld example, τ1 has 7 novel observations (P = 0.35, reported contrast +1.67), versus 3 (P = 0.15, −1.00) for τ4.These reported contrasts lack the deployed scale and verified full-group normalization, and do not show that the higher-ranked state has greater continuation value.Source: §11.1 · p. 41, Table 19 · p. 42

11.2 WebShop: Searching for Pants

• In the WebShop example, τ3 has 7 novel observations (P = 0.47, reported contrast +1.17), while τ1 has 2 (P = 0.13, −1.43).Exact observation-string novelty does not establish that each new page helps the shopping goal; these selected cases do not demonstrate task-value ordering or broad effectiveness.Source: §11.2 · p. 42, Table 20 · p. 42

Limitations

• Observation identity can mistake surface variation for novelty or miss hidden state changes; semantic novelty and visual generalization are not established by these experiments.The deficit-bound interpretation depends on stated assumptions and is not a continuation-value guarantee.Source: §12 · p. 43
• The evidence has statistical and mechanistic limits: most main-table standard deviations aggregate three seeds, and exact non-interference applies to the ideal algorithm, not automatically to its numerical implementation.Offline policy shifts do not isolate fallback gradients or explain the reported aggregate success gap between CovGPO and Random-h; the scale sweep is non-monotone.Source: §12 · p. 43
• Uniform-success groups retain the base algorithm, while coverage-degenerate failures have no coverage ranking to exploit; snapshots do not establish how common these cases are across settings.Uniform success in a sampled group does not prove mastery, and equal coverage does not imply every trajectory stagnates.Source: §12 · p. 43

Broader Impact

• CovGPO inherits underlying agent risks, and the timing audit establishes neither lower total energy use nor intrinsic speedup; deployment calls for safeguards such as filters, sandboxing, and human oversight.Capability improvements can benefit useful applications while increasing the consequences of unsafe actions.Source: §12 · p. 43