Progress-conditioned Group Policy Optimization for Long-Horizon Agentic Tasks

# Progress-conditioned Group Policy Optimization for Long-Horizon Agentic Tasks
Source: [https://arxiv.org/html/2607.22724](https://arxiv.org/html/2607.22724)
Kaibing Yang1,2, Guangfeng Cai1, Shengtian Yang1,2, Shuo He3, Yu Li1, Mengyi Liu2Pengwei Chen2, Jun Xu2,\*, Lei Feng1,§

###### 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 tasks, this comparison can suffer from a sampling imbalance:repeated or low\-effect actions dominate the high\-probability region of the policywhileuseful state\-changing actions remain under\-sampled\. This imbalance produces many all\-failed rollout groups, where outcome rewards provide no direction for correcting the policy\. Together, these effects can form a self\-reinforcing*credit trap*:failure\-dominated sampling yields no outcome\-based correction, allowing repeated low\-effect actions to persist\.To break this loop, we proposeProgress\-conditionedGroupPolicyOptimization \(ProGPO\), which uses first\-visit observation coverage only when all samples in a group receive zero outcome reward\. Specifically, within such groups, ProGPO assigns higher relative advantages to trajectories or steps that visit more new states since reaching new observations is a prerequisite for task success\. Experiments on two challenging agentic benchmarks, ALFWorld and WebShop with Qwen2\.5\-1\.5/7B\-Instruct, show that ProGPO consistently improves over group\-based baselines, with particularly large gains on hard tasks\.

## 1Introduction

LLM agents\[[1](https://arxiv.org/html/2607.22724#bib.bib1),[27](https://arxiv.org/html/2607.22724#bib.bib27),[37](https://arxiv.org/html/2607.22724#bib.bib37),[28](https://arxiv.org/html/2607.22724#bib.bib28)\]are increasingly moving beyond single\-turn response generation toward interactive problem solving in open\-ended environments such as household tasks\[[26](https://arxiv.org/html/2607.22724#bib.bib26),[15](https://arxiv.org/html/2607.22724#bib.bib15)\], web navigation\[[10](https://arxiv.org/html/2607.22724#bib.bib10),[9](https://arxiv.org/html/2607.22724#bib.bib9)\], and tool use\[[22](https://arxiv.org/html/2607.22724#bib.bib22),[20](https://arxiv.org/html/2607.22724#bib.bib20)\]\. These tasks require agents to plan, act, observe, and revise over many steps\[[7](https://arxiv.org/html/2607.22724#bib.bib7),[29](https://arxiv.org/html/2607.22724#bib.bib29),[33](https://arxiv.org/html/2607.22724#bib.bib33)\], while success is often revealed only through sparse outcome feedback\. Such sparse supervision leaves most intermediate decisions without direct task feedback, making credit assignment over long trajectories difficult\.

To train agents under such sparse outcome feedback, recent work has adopted group\-based policy optimization\[[24](https://arxiv.org/html/2607.22724#bib.bib24),[40](https://arxiv.org/html/2607.22724#bib.bib40),[12](https://arxiv.org/html/2607.22724#bib.bib12)\], which samples multiple trajectories for the same task and updates the policy using their relative outcomes instead of a learned value function\. At the trajectory level, GRPO compares the complete trajectories within each rollout group and assigns a single advantage to all its constituent steps\. To provide finer\-grained credit, GiGPO\[[8](https://arxiv.org/html/2607.22724#bib.bib8)\]groups steps that share an anchor observation and produces step\-varying advantages within the same trajectory, while HGPO\[[11](https://arxiv.org/html/2607.22724#bib.bib11)\]further groups steps by their shared interaction history\. However, they all rely on the same assumption:outcome variation among compared trajectories or steps\. When all fail, the comparison yields no signal\.

![Refer to caption](https://arxiv.org/html/2607.22724v1/x1.png)Figure 1:All\-fail rate across training and credit trap\. \(a\) Most rollout groups are all\-fail during early training, yielding zero reward\-based advantages\. \(b\) The base policy concentrates probability mass on low\-effect actions, leaving state\-changing actions under\-sampled\. These two effects reinforce each other: imbalanced sampling produces more all\-fail groups, while the resulting zero gradients prevent the policy from correcting the imbalance\.This assumption is often reasonable in short\-horizon or moderately difficult tasks\[[17](https://arxiv.org/html/2607.22724#bib.bib17),[40](https://arxiv.org/html/2607.22724#bib.bib40),[34](https://arxiv.org/html/2607.22724#bib.bib34)\], where some sampled trajectories succeed while others fail\. However, in hard long\-horizon environments\[[26](https://arxiv.org/html/2607.22724#bib.bib26),[38](https://arxiv.org/html/2607.22724#bib.bib38)\], many*all\-fail rollout groups*occur:every trajectory receives the same failure outcome\. In such groups, the policy exhibits a sampling imbalance:high\-probability actions tend to be low effect while effective actions remain under\-sampled\(Fig\.[1](https://arxiv.org/html/2607.22724#S1.F1)\)\. This leads to a*self\-reinforcing credit trap*: failure\-dominated sampling produces all\-fail groups, and because every trajectory shares the same outcome, the reward\-based comparison provides no direction for correcting the imbalanced sampling\.

To address this issue, recent research has shifted to denser rewards\[[18](https://arxiv.org/html/2607.22724#bib.bib18)\], learned progress estimators\[[31](https://arxiv.org/html/2607.22724#bib.bib31),[35](https://arxiv.org/html/2607.22724#bib.bib35),[4](https://arxiv.org/html/2607.22724#bib.bib4),[36](https://arxiv.org/html/2607.22724#bib.bib36)\], world\-model guidance\[[41](https://arxiv.org/html/2607.22724#bib.bib41)\], and turn\-level credit designs\[[18](https://arxiv.org/html/2607.22724#bib.bib18)\]\. These designs can enrich the training signal, but they typically introduce auxiliary supervision or learned models\.

![Refer to caption](https://arxiv.org/html/2607.22724v1/x2.png)Figure 2:Not all failures are equal and progress signal\. \(a\) Within the same all\-fail group, some trajectories visit novel states while others stagnate on repeated no\-change actions, revealing behavioral contrast that reward\-only estimators discard\. \(b\) We recover this signal via first\-visit observation coverage: each transition to a previously unseen observation is counted as progress\.However, the credit trap does not imply that failed rollouts are uninformative: equal failure outcomes do not imply equal behavior\. Within the same all\-fail group, one trajectory may repeatedly revisit the same observations, while another reaches more distinct observations before ultimately failing\(Fig\.[2](https://arxiv.org/html/2607.22724#S1.F2)\(a\)\)\. Although both receive the same terminal outcome, the latter exhibits more progress than the former\. Existing estimators fail to capture this contrast: GRPO assigns both trajectories the same zero advantage, while GiGPO and HGPO compare steps whose inherited returns are also identical, causing their step\-level advantages to zero as well\.

To address these issues, we proposeProgress\-conditionedGroupPolicyOptimization \(ProGPO\), a fallback advantage estimator that recovers learning signals from all\-fail groups usingfirst\-visit observation coverage\. Specifically, ProGPO treats a step as progress if and only if it transitions to an observation not previously visited within the same trajectory\. It credits state\-changing transitions, a necessary though not sufficient condition for task success, while assigning no progress to actions that preserve or revisit existing observations\. Consequently, trajectories that reach more novel observations receive higher progress scores, whereas those dominated by stagnation or repetition receive lower scores\. ProGPO uses these scores to construct non\-zero, behavior\-aligned advantages when reward\-based estimators provide no distinction, and reverts exactly to the standard reward\-based advantage once outcome variation is available since coverage is only a proxy and it can rank a wandering failure above an efficient success\. In this way, ProGPO breaks the self\-reinforcing credit trap: within all\-fail groups, trajectories reaching new observations receive positive advantages, promoting the state\-changing actions the base policy was under\-sampling\. Across two challenging agentic benchmarks, ALFWorld and WebShop, and Qwen2\.5\-1\.5B/7B\-Instruct models, ProGPO consistently outperforms strong existing baselines\. Our contributions are summarized as follows:

- •We identify the*all\-fail credit trap*: imbalanced sampling produces all\-fail rollout groups whose identical outcomes prevent reward\-based estimators from correcting the imbalance, despite the behavioral contrast within these groups\.
- •We propose ProGPO, a conditional fallback estimator that recovers credit in all\-fail groups via first\-visit observation coverage, a necessary precondition for task success, and reverts exactly to the base advantage when outcome variation returns\.
- •On ALFWorld and WebShop with Qwen2\.5\-1\.5B/7B\-Instruct, ProGPO consistently outperforms strong group\-based baselines under the same computational constraints\.

## 2Related Work

Group\-Based Reinforcement Learning for Long\-Horizon LLM Agents\.Critic\-free methods such as GRPO\[[24](https://arxiv.org/html/2607.22724#bib.bib24)\]and RLOO\[[2](https://arxiv.org/html/2607.22724#bib.bib2)\]estimate policy advantages from relative outcomes among multiple samples, reducing the memory and computation required by PPO\-style actor–critic training\[[23](https://arxiv.org/html/2607.22724#bib.bib23),[43](https://arxiv.org/html/2607.22724#bib.bib43)\]\. Their agentic extensions increasingly refine the comparison unit: GiGPO\[[8](https://arxiv.org/html/2607.22724#bib.bib8)\]combines trajectory\-level and anchor\-state groups, ProxMO\[[6](https://arxiv.org/html/2607.22724#bib.bib6)\]introduces difficulty\-aware modulation and semantic soft aggregation, and HGPO\[[11](https://arxiv.org/html/2607.22724#bib.bib11)\]forms hierarchical groups to control historical\-context inconsistency\. SALT\[[14](https://arxiv.org/html/2607.22724#bib.bib14)\]and GraphGPO\[[5](https://arxiv.org/html/2607.22724#bib.bib5)\]exploit trajectory or state\-transition graphs to propagate structural credit across related states\. These methods improve the granularity or accuracy of credit assignment once a usable comparison signal exists\. ProGPO addresses a complementary regime in which all sampled trajectories fail and the outcome statistics provide no signal, using first\-visit observation coverage as a conditional fallback instead of introducing another grouping or value\-estimation structure\.

Learning from all\-fail and outcome\-degenerate groups\.Identical outcome rollout groups provide little relative learning signal and have been addressed through sampling, scaffolding, and surrogate advantages\. DAPO\[[40](https://arxiv.org/html/2607.22724#bib.bib40)\]dynamically resamples prompts with zero reward variance, while XRPO\[[3](https://arxiv.org/html/2607.22724#bib.bib3)\]and Scaf\-GRPO\[[42](https://arxiv.org/html/2607.22724#bib.bib42)\]introduce exemplars or hints to turn difficult prompts into mixed\-outcome groups\. Alternatively, NGRPO\[[19](https://arxiv.org/html/2607.22724#bib.bib19)\]constructs virtual reward samples, RL\-ZVP\[[13](https://arxiv.org/html/2607.22724#bib.bib13)\]uses entropy\-guided advantage shaping, and TSPO\[[18](https://arxiv.org/html/2607.22724#bib.bib18)\]introduces partial rewards for multi\-turn search\. These methods primarily rely on answer\-level correctness, confidence, or additional exploration\. ProGPO instead keeps the original all\-fail agent rollouts and extracts relative credit from their observed transition structure\.

Auxiliary progress and exploration signals for agentic credit assignment\.Sparse terminal rewards have motivated dense supervision from learned progress models, interaction structure, and intrinsic exploration\. SPA\-RL\[[32](https://arxiv.org/html/2607.22724#bib.bib32)\]decomposes terminal outcomes into stepwise progress rewards, while iStar\[[16](https://arxiv.org/html/2607.22724#bib.bib16)\]and AgentPRM\[[35](https://arxiv.org/html/2607.22724#bib.bib35)\]learn process reward models for intermediate agent decisions\. IGPO\[[30](https://arxiv.org/html/2607.22724#bib.bib30)\]measures progress through information gain\. Classical approaches such as RIDE\[[21](https://arxiv.org/html/2607.22724#bib.bib21)\]instead reward actions that induce substantial state changes\. Unlike these persistent or model\-based auxiliary signals, ProGPO uses model\-free first\-visit coverage only when outcome rewards provide no within\-group ordering\.

## 3Preliminaries and Problem Formulation

Multi\-Turn Agentic Tasks\.Letx∼p​\(X\)x\\sim p\(X\)be a task instruction andπθ\\pi\_\{\\theta\}an LLM\-based policy\. At each steptt, the policy producesat∼πθ\(⋅∣ht\)a\_\{t\}\\sim\\pi\_\{\\theta\}\(\\cdot\\mid h\_\{t\}\)conditioned on the interaction historyht=\(x,o1,a1,…,ot\)h\_\{t\}=\(x,o\_\{1\},a\_\{1\},\\ldots,o\_\{t\}\), and the environment returns the next observationot\+1o\_\{t\+1\}\. The resulting trajectory isτ=\(o1,a1,…,oT,aT\)\\tau=\(o\_\{1\},a\_\{1\},\\ldots,o\_\{T\},a\_\{T\}\), whereTTis bounded by the interaction budget\. The environment provides a binary reward only at termination,R​\(τ\)∈\{0,1\}R\(\\tau\)\\in\\\{0,1\\\}, indicating task completion; no intermediate reward is available\. We focus on this sparse, delayed\-reward setting\.

Group\-Based Reinforcement Learning\.Group\-based RL methods such as GRPO\[[24](https://arxiv.org/html/2607.22724#bib.bib24)\]estimate advantages critic\-free from intra\-group statistics\. For taskxx, a groupGx=\{τi\}i=1KG\_\{x\}=\\\{\\tau\_\{i\}\\\}\_\{i=1\}^\{K\}ofKKtrajectories is sampled fromπθ\\pi\_\{\\theta\}, each receiving an outcome rewardRi=R​\(τi\)R\_\{i\}=R\(\\tau\_\{i\}\)\. The trajectory\-level group\-relative advantage is

AiR=Ri−R¯GxσR​\(Gx\)\+ϵ,R¯Gx=1K​∑j=1KRj,A\_\{i\}^\{R\}=\\frac\{R\_\{i\}\-\\bar\{R\}\_\{G\_\{x\}\}\}\{\\sigma\_\{R\}\(G\_\{x\}\)\+\\epsilon\},\\quad\\bar\{R\}\_\{G\_\{x\}\}=\\frac\{1\}\{K\}\\sum\_\{j=1\}^\{K\}R\_\{j\},\(1\)and every step inτi\\tau\_\{i\}sharesAiRA\_\{i\}^\{R\}\. For finer\-grained credit, recent variants form step\-level groups: GiGPO\[[8](https://arxiv.org/html/2607.22724#bib.bib8)\]collects steps acrossGxG\_\{x\}that share the same environment statessintoGS​\(s\)G^\{S\}\(s\)and normalizes their discounted returnsRi,tS=γTi−t​RiR^\{S\}\_\{i,t\}=\\gamma^\{T\_\{i\}\-t\}R\_\{i\}within it, while HGPO\[[11](https://arxiv.org/html/2607.22724#bib.bib11)\]groups steps by shared interaction history prefixes instead of a single anchor state\.

Ai,tS=Ri,tS−R¯GS​\(s\)σR​\(GS​\(s\)\)\+ϵ,A^\{S\}\_\{i,t\}=\\frac\{R^\{S\}\_\{i,t\}\-\\bar\{R\}\_\{G^\{S\}\(s\)\}\}\{\\sigma\_\{R\}\(G^\{S\}\(s\)\)\+\\epsilon\},\(2\)The policy is updated via a clipped surrogate objective with KL regularization against a referenceπref\\pi\_\{\\mathrm\{ref\}\}\. Regardless of granularity, these estimators work only when*within\-group reward contrasts*\.

All\-Fail Groups and the Credit Trap\.In hard long\-horizon tasks, success is rare early in training, and a rollout group may contain no successful trajectory\. We call suchGxG\_\{x\}an*all\-fail rollout group*:

Gx​is all\-fail⟺Ri=0,∀τi∈Gx\.G\_\{x\}\\text\{ is all\-fail\}\\;\\Longleftrightarrow\\;R\_\{i\}=0,\\quad\\forall\\,\\tau\_\{i\}\\in G\_\{x\}\.\(3\)The trajectory\-level estimator in Eq\. \([1](https://arxiv.org/html/2607.22724#S3.E1)\) then degenerates:

σR​\(Gx\)=0⟹AiR=0,∀i∈\{1,…,K\}\.\\sigma\_\{R\}\(G\_\{x\}\)=0\\;\\Longrightarrow\\;A\_\{i\}^\{R\}=0,\\quad\\forall\\,i\\in\\\{1,\\ldots,K\\\}\.\(4\)Moreover, every discounted return in Eq\. \([2](https://arxiv.org/html/2607.22724#S3.E2)\) satisfiesRi,tS=γTi−t⋅0=0R^\{S\}\_\{i,t\}=\\gamma^\{T\_\{i\}\-t\}\\cdot 0=0, so step\-level and hierarchical advantages vanish as well: at any granularity, the group contributes zero policy gradient\. This is the technical manifestation of the self\-reinforcing credit trap in Section[1](https://arxiv.org/html/2607.22724#S1)—the reward\-based estimator produces no signal within all\-fail groups, so the imbalanced sampling that generates them cannot be corrected, and such groups persist throughout training\. This degenerate regime is the setting our method targets\.

## 4Training Agents with ProGPO for Long\-Horizon Agentic Tasks

![Refer to caption](https://arxiv.org/html/2607.22724v1/x3.png)Figure 3:Overview of ProGPO\. For each task, the agent samples a group ofKKrollouts from the same initial state and prompt\. When the group is all\-fail, ProGPO scores each trajectory by its first\-visit observation coverage, and normalizes the scores within the group into a fallback advantage, recovering a learning signal that reinforces state\-changing behavior\.A simple insight behind our method is that the behavioral contrast among failed trajectories is observable and can serve as a fallback learning signal when the reward degenerates\. As illustrated in Figure[3](https://arxiv.org/html/2607.22724#S4.F3), we operationalize this through two components: a*first\-visit coverage score*\(Section[4\.1](https://arxiv.org/html/2607.22724#S4.SS1)\) that quantifies the contrast, and a*conditional switch*\(Section[4\.2](https://arxiv.org/html/2607.22724#S4.SS2)\) that uses this score only when the reward\-based estimator has degenerated\.

### 4\.1First\-Visit Coverage Score

For thett\-th transition in trajectoryτi\\tau\_\{i\}, the step\-level indicator is

δi,t=𝟏​\[oi,t\+1∉𝒱i,t\],\\delta\_\{i,t\}=\\mathbf\{1\}\\\!\\left\[o\_\{i,t\+1\}\\notin\\mathcal\{V\}\_\{i,t\}\\right\],\(5\)where𝟏​\[⋅\]\\mathbf\{1\}\[\\cdot\]is the indicator function and𝒱i,t=\{oi,1,…,oi,t\}\\mathcal\{V\}\_\{i,t\}=\\\{o\_\{i,1\},\\ldots,o\_\{i,t\}\\\}is the set of observations already encountered inτi\\tau\_\{i\}up to steptt\. A step counts as progress only when its resulting observation is genuinely new to the trajectory, so the indicator naturally filters both low\-effect transitions \(which leave the observation unchanged\) and cyclic revisitations \(which return to previously seen states\)\. We aggregate step\-level progress into a trajectory\-level score,

Pi=1Ti​∑t=1Tiδi,t,P\_\{i\}=\\frac\{1\}\{T\_\{i\}\}\\sum\_\{t=1\}^\{T\_\{i\}\}\\delta\_\{i,t\},\(6\)whereTiT\_\{i\}is the length ofτi\\tau\_\{i\}\. We writeP​\(τ\)P\(\\tau\)for the score of a generic trajectory\. Maintaining𝒱i,t\\mathcal\{V\}\_\{i,t\}as a per\-trajectory hash set addsO​\(1\)O\(1\)overhead per step to the existing rollout pipeline\.

We emphasize thatPPis a deliberately weak signal: it measures state coverage, not task value, and a trajectory can raise its coverage without approaching the goal\. However, coverage is a*necessary*condition for success:no trajectory succeeds without traversing new states\.

Formally, letD​\(τ\)=\|\{o1,…,oT\+1\}\|D\(\\tau\)=\|\\\{o\_\{1\},\\ldots,o\_\{T\+1\}\\\}\|be the number of distinct observations visited byτ\\tau, and call a taskxx*mxm\_\{x\}\-separated*if completing it requires visiting at leastmx≥2m\_\{x\}\\geq 2distinct observations\. Here,mxm\_\{x\}is an intrinsic property of the task, defined as the minimum number of distinct observations encountered along any successful trajectory\. It is introduced solely to state the bound below and is not required by the method\.

###### Proposition 4\.1\(Progress is a relaxation of success\)\.

Letτ\\taube a trajectory of lengthTTandP​\(τ\)P\(\\tau\)its progress score defined by Eqs\.[5](https://arxiv.org/html/2607.22724#S4.E5)–[6](https://arxiv.org/html/2607.22724#S4.E6)\. Then:

1. \(i\)P​\(τ\)=\(D​\(τ\)−1\)/TP\(\\tau\)=\\bigl\(D\(\\tau\)\-1\\bigr\)/T;
2. \(ii\)if taskxxismxm\_\{x\}\-separated, then\{τ:R​\(τ\)=1\}⊆\{τ:P​\(τ\)≥\(mx−1\)/T\}\\\{\\tau:R\(\\tau\)=1\\\}\\subseteq\\\{\\tau:P\(\\tau\)\\geq\(m\_\{x\}\-1\)/T\\\}\.

Part \(i\)showsPPis an exact measure of state coverage: each observation contributes at its first visit, and revisits receive no positive step credit, weakly reducing the normalized trajectory score\.Part \(ii\)shows the success set lies inside a super\-level set ofPP: promoting probability mass toward high\-PPtrajectories moves the policy toward a region containing*all*successful behaviors\. Because the inclusion is generally strict,PPis a relaxation of the task objective instead of a substitute—which is precisely why we never let it compete with an informative reward signal\.

### 4\.2Conditional Advantage Estimator

An always\-on progress signal may conflict with the task reward once outcome variation is available\. For example, a short and efficient successful trajectory may achieve lower coverage than a long but unsuccessful trajectory\(Appendix[7\.5](https://arxiv.org/html/2607.22724#S7.SS5)\), causing the auxiliary signal to oppose and partially offset the reward\-induced gradient and decreasing the performance\(Tab\.[2](https://arxiv.org/html/2607.22724#S5.T2)\)\. Conversely, discarding progress in all\-fail groups wastes the only within\-group contrast available\. ProGPO therefore switches between reward and progress*conditionally*, based on the observable within\-group variance:

AiProGPO=\{Ri−R¯GxσR​\(Gx\)\+ϵ,if​σR​\(Gx\)≥τR,λ​Pi−P¯GxσP​\(Gx\)\+ϵ,if​σR​\(Gx\)<τR,R¯Gx=0,σP​\(Gx\)≥τP,0,otherwise,A\_\{i\}^\{\\mathrm\{ProGPO\}\}=\\begin\{cases\}\\dfrac\{R\_\{i\}\-\\bar\{R\}\_\{G\_\{x\}\}\}\{\\sigma\_\{R\}\(G\_\{x\}\)\+\\epsilon\},&\\text\{if \}\\sigma\_\{R\}\(G\_\{x\}\)\\geq\\tau\_\{R\},\\\\\[10\.0pt\] \\lambda\\,\\dfrac\{P\_\{i\}\-\\bar\{P\}\_\{G\_\{x\}\}\}\{\\sigma\_\{P\}\(G\_\{x\}\)\+\\epsilon\},&\\text\{if \}\\sigma\_\{R\}\(G\_\{x\}\)<\\tau\_\{R\},\\ \\bar\{R\}\_\{G\_\{x\}\}=0,\\ \\sigma\_\{P\}\(G\_\{x\}\)\\geq\\tau\_\{P\},\\\\\[10\.0pt\] 0,&\\text\{otherwise\},\\end\{cases\}\(7\)whereP¯Gx\\bar\{P\}\_\{G\_\{x\}\}andσP​\(Gx\)\\sigma\_\{P\}\(G\_\{x\}\)mirrorR¯Gx\\bar\{R\}\_\{G\_\{x\}\}andσR​\(Gx\)\\sigma\_\{R\}\(G\_\{x\}\)in Eq\. \([1](https://arxiv.org/html/2607.22724#S3.E1)\),τR\\tau\_\{R\}is a threshold detecting reward\-advantage degeneracy,τP\\tau\_\{P\}prevents injecting a progress signal when failed trajectories also lack coverage variation, andλ\>0\\lambda\>0scales the fallback advantage\. The three branches correspond to distinct regimes: \(a\) the group has outcome contrast, and ProGPO reduces exactly to the base estimator; \(b\) all trajectories fail but their coverage differs, and ProGPO assigns positive relative advantage to above\-average\-coverage trajectories; \(c\) both reward and progress are uninformative, and the group is discarded to avoid injecting noise\. All\-success groups \(R¯Gx=1\\bar\{R\}\_\{G\_\{x\}\}=1,σR<τR\\sigma\_\{R\}<\\tau\_\{R\}\) also fall into \(c\), matching standard group\-relative estimation which likewise yields zero advantage there\.

The piecewise structure makes the safety of this switch exact:

###### Proposition 4\.3\(Non\-interference\)\.

For any policyπθ\\pi\_\{\\theta\}and any groupGxG\_\{x\}withσR​\(Gx\)≥τR\\sigma\_\{R\}\(G\_\{x\}\)\\geq\\tau\_\{R\},AiProGPO=AiRA\_\{i\}^\{\\mathrm\{ProGPO\}\}=A\_\{i\}^\{R\}for allii\. Consequently,∇θ𝒥ProGPO−∇θ𝒥base\\nabla\_\{\\theta\}\\mathcal\{J\}\_\{\\mathrm\{ProGPO\}\}\-\\nabla\_\{\\theta\}\\mathcal\{J\}\_\{\\mathrm\{base\}\}is supported entirely on groups whose reward\-based gradient is identically zero\.

ProGPO is thus a*strict extension*of the base estimator: it modifies the update only where the base method provably provides no signal\. The fallback branch itself admits a clean characterization\. Letg​\(Gx\)=1K​∑iAi​∇θlog⁡πθ​\(τi\)g\(G\_\{x\}\)=\\frac\{1\}\{K\}\\sum\_\{i\}A\_\{i\}\\,\\nabla\_\{\\theta\}\\log\\pi\_\{\\theta\}\(\\tau\_\{i\}\)denote the gradient contribution of groupGxG\_\{x\}\.

###### Proposition 4\.4\(Fallback branch as group\-normalized REINFORCE\)\.

For a group entering the fallback branch of Eq\. \([7](https://arxiv.org/html/2607.22724#S4.E7)\),

g​\(Gx\)=λσP​\(Gx\)\+ϵ⋅1K​∑i=1K\(Pi−P¯Gx\)​∇θlog⁡πθ​\(τi\),g\(G\_\{x\}\)=\\frac\{\\lambda\}\{\\sigma\_\{P\}\(G\_\{x\}\)\+\\epsilon\}\\cdot\\frac\{1\}\{K\}\\sum\_\{i=1\}^\{K\}\\bigl\(P\_\{i\}\-\\bar\{P\}\_\{G\_\{x\}\}\\bigr\)\\nabla\_\{\\theta\}\\log\\pi\_\{\\theta\}\(\\tau\_\{i\}\),i\.e\., up to a positive group\-dependent scale, the REINFORCE update with a group\-mean baseline that treatsPPas the return\. A characterization of the resulting estimator’s bias, conditional on the all\-fail event, is deferred to Appendix[7\.3](https://arxiv.org/html/2607.22724#S7.SS3)\.

Combined with Proposition[4\.1](https://arxiv.org/html/2607.22724#S4.Thmtheorem1), this shows the fallback ascends a principled relaxation of the task objective: within the degenerate regime, ProGPO enlarges the set of trajectories capable of reaching terminal reward; as soon as some trajectory succeeds, the reward branch reclaims control \(Proposition[4\.3](https://arxiv.org/html/2607.22724#S4.Thmtheorem3)\)\. The hand\-off is automatic: the fallback requires allKKtrajectories to fail, so its trigger probability on a task with per\-trajectory success probabilitypθ​\(x\)p\_\{\\theta\}\(x\)is at most\(1−pθ​\(x\)\)K≤e−K​pθ​\(x\)\(1\-p\_\{\\theta\}\(x\)\)^\{K\}\\leq e^\{\-Kp\_\{\\theta\}\(x\)\}, decaying exponentially as the policy improves\. In the long tail of tasks wherepθ​\(x\)p\_\{\\theta\}\(x\)remains small even at convergence, the fallback stays active; we treat this as a feature rather than a bug—such tasks are precisely the ones the base estimator cannot help on\. Proofs are deferred to Appendix[7](https://arxiv.org/html/2607.22724#S7)\.

Finally, ProGPO integrates into any group\-based framework by replacing the reward\-only advantage withAiProGPOA\_\{i\}^\{\\mathrm\{ProGPO\}\}in a clipped surrogate objective:

𝒥ProGPO​\(θ\)=𝔼x,Gx​\[1K​∑i=1K1Ti​∑t=1Timin⁡\(ρi,t​\(θ\)​AiProGPO,clip​\(ρi,t​\(θ\),1−ϵc,1\+ϵc\)​AiProGPO\)\]−β​DKL​\(πθ∥πref\),\\begin\{split\}\\mathcal\{J\}\_\{\\mathrm\{ProGPO\}\}\(\\theta\)&=\\mathbb\{E\}\_\{x,G\_\{x\}\}\\Bigl\[\\frac\{1\}\{K\}\\sum\_\{i=1\}^\{K\}\\frac\{1\}\{T\_\{i\}\}\\sum\_\{t=1\}^\{T\_\{i\}\}\\min\\\!\\bigl\(\\rho\_\{i,t\}\(\\theta\)\\,A\_\{i\}^\{\\mathrm\{ProGPO\}\},\\mathrm\{clip\}\\\!\\bigl\(\\rho\_\{i,t\}\(\\theta\),\\,1\{\-\}\\epsilon\_\{c\},\\,1\{\+\}\\epsilon\_\{c\}\\bigr\)A\_\{i\}^\{\\mathrm\{ProGPO\}\}\\bigr\)\\Bigr\]\\\\ &\\qquad\\qquad\-\\beta\\,D\_\{\\mathrm\{KL\}\}\(\\pi\_\{\\theta\}\\\|\\pi\_\{\\mathrm\{ref\}\}\),\\end\{split\}\(8\)whereρi,t​\(θ\)=πθ​\(ai,t∣hi,t\)/πθold​\(ai,t∣hi,t\)\\rho\_\{i,t\}\(\\theta\)=\\pi\_\{\\theta\}\(a\_\{i,t\}\\mid h\_\{i,t\}\)/\\pi\_\{\\theta\_\{\\mathrm\{old\}\}\}\(a\_\{i,t\}\\mid h\_\{i,t\}\)is the importance ratio,ϵc\\epsilon\_\{c\}is the clipping range, andβ\\betacontrols KL regularization\.

## 5Experiments

### 5\.1Experiment Setup

Benchmarks\.We train and evaluate LLM agents on two challenging benchmarks: ALFWorld\[[26](https://arxiv.org/html/2607.22724#bib.bib26)\]and WebShop\[[38](https://arxiv.org/html/2607.22724#bib.bib38)\]\.ALFWorldis an embodied text environment for multi\-step decision\-making\. In each episode, the agent receives a textual goal and must accomplish it through multi\-turn interaction spanning 20–50 steps, receiving only a binary outcome reward upon termination\. It covers six categories of household activities: Pick & Place \(Pick\), Examine in Light \(Look\), Clean & Place \(Clean\), Heat & Place \(Heat\), Cool & Place \(Cool\), and Pick Two & Place \(Pick2\)\. The categories differ markedly in initial difficulty, which makes ALFWorld a natural testbed for all\-fail degeneracy: on hard categories, the base policy almost never succeeds, so early rollout groups are overwhelmingly all\-fail\.WebShopis a web\-based interactive shopping environment in which the agent must search, navigate, and purchase a suitable item on a simulated HTML website\.

Baselines\.We compare ProGPO against three groups of methods\. \(1\)Prompting agents: the base Qwen2\.5 models, React\[[39](https://arxiv.org/html/2607.22724#bib.bib39)\]and Reflexion\[[25](https://arxiv.org/html/2607.22724#bib.bib25)\], which guide multi\-step behavior through in\-context prompting without parameter updates\. \(2\)RL training methods: PPO\[[23](https://arxiv.org/html/2607.22724#bib.bib23)\], which requires an additional critic network; RLOO\[[12](https://arxiv.org/html/2607.22724#bib.bib12)\], a critic\-free REINFORCE variant with a leave\-one\-out baseline; and the group\-based methods GRPO\[[24](https://arxiv.org/html/2607.22724#bib.bib24)\], GiGPO\[[8](https://arxiv.org/html/2607.22724#bib.bib8)\], and HGPO\[[11](https://arxiv.org/html/2607.22724#bib.bib11)\], where the latter is the state\-of\-the\-art group\-based algorithm for LLM agents and serves as our primary base algorithm\. \(3\)ProGPO\-augmented methods: since ProGPO modifies only the advantage computation, we instantiate it on top of three different base algorithms, GRPO\+ProGPO, GiGPO\+ProGPO and HGPO\+ProGPO, to verify that the repair mechanism is algorithm\-agnostic\. For every base algorithm, the ProGPO\-augmented counterpart uses*exactly*the same rollout strategy, optimization hyperparameters, and compute budget; any difference in performance is therefore attributable to the conditional advantage repair alone\. Full training settings are provided in Appendix[8](https://arxiv.org/html/2607.22724#S8)\.

Table 1:Test performance on ALFWorld and WebShop\. For ALFWorld, we report the average success rate \(%\) for each subtask as well as the overall result; for WebShop, we report the average task score and the average success rate \(%\)\. Most results are averaged over 3 random seeds\.↑\\,\\uparrow/↓\\,\\downarrowgive the change on the aggregate metrics relative to that base algorithm\.Boldmarks the best result within each model scale\.MethodALFWorldWebShopPickLookCleanHeatCoolPick2AllScoreSucc\.Closed\-Source ModelsGPT\-4o75\.360\.831\.256\.721\.649\.848\.031\.823\.7Gemini\-2\.5\-Pro92\.863\.362\.169\.026\.658\.760\.342\.535\.9Qwen2\.5\-1\.5B\-InstructQwen2\.55\.95\.53\.39\.74\.20\.04\.123\.15\.2ReAct17\.420\.515\.76\.27\.72\.012\.840\.111\.3Reflexion35\.322\.221\.713\.619\.43\.721\.855\.821\.9PPO64\.8±\\pm3\.540\.5±\\pm6\.957\.1±\\pm4\.960\.6±\\pm6\.646\.4±\\pm4\.047\.4±\\pm1\.954\.4±\\pm3\.173\.8±\\pm3\.051\.5±\\pm2\.9RLOO88\.3±\\pm3\.052\.8±\\pm8\.671\.0±\\pm5\.962\.8±\\pm8\.766\.4±\\pm5\.556\.9±\\pm4\.769\.7±\\pm2\.573\.9±\\pm5\.652\.1±\\pm6\.7GRPO85\.3±\\pm1\.553\.7±\\pm8\.084\.5±\\pm6\.878\.2±\\pm7\.959\.7±\\pm5\.053\.5±\\pm5\.672\.8±\\pm3\.675\.8±\\pm3\.556\.8±\\pm3\.8GRPO \+ ProGPO84\.1±\\pm5\.676\.3±\\pm15\.174\.8±\\pm8\.169\.6±\\pm9\.283\.2±\\pm4\.450\.8±\\pm11\.374\.5±\\pm1\.6↑\\,\\uparrow1\.776\.2±\\pm1\.0↑\\,\\uparrow0\.460\.9±\\pm2\.2↑\\,\\uparrow4\.1GiGPO94\.4±\\pm5\.967\.5±\\pm4\.694\.8±\\pm3\.894\.4±\\pm7\.879\.8±\\pm4\.776\.4±\\pm5\.486\.7±\\pm1\.783\.1±\\pm1\.665\.0±\\pm3\.2GiGPO \+ ProGPO92\.2±\\pm6\.784\.4±\\pm15\.095\.7±\\pm4\.087\.8±\\pm7\.390\.2±\\pm4\.492\.8±\\pm2\.791\.4±\\pm1\.6↑\\,\\uparrow4\.785\.6±\\pm0\.5↑\\,\\uparrow2\.572\.4±\\pm0\.6↑\\,\\uparrow7\.4HGPO97\.8±\\pm0\.385\.4±\\pm5\.995\.0±\\pm3\.197\.4±\\pm1\.787\.6±\\pm2\.688\.0±\\pm6\.092\.8±\\pm1\.185\.6±\\pm2\.971\.5±\\pm4\.0HGPO \+ ProGPO100\.0±\\pm0\.091\.3±\\pm0\.598\.3±\\pm2\.497\.1±\\pm4\.292\.3±\\pm2\.093\.5±\\pm2\.595\.7±\\pm0\.6↑\\,\\uparrow2\.987\.5±\\pm1\.6↑\\,\\uparrow1\.975\.7±\\pm2\.8↑\\,\\uparrow4\.2Qwen2\.5\-7B\-InstructQwen2\.533\.421\.619\.36\.92\.83\.214\.826\.47\.8ReAct48\.535\.434\.313\.218\.217\.631\.246\.219\.5Reflexion62\.041\.644\.930\.936\.323\.842\.758\.128\.8PPO92\.3±\\pm4\.064\.0±\\pm8\.492\.5±\\pm2\.489\.5±\\pm7\.080\.3±\\pm2\.068\.8±\\pm8\.380\.4±\\pm2\.781\.4±\\pm3\.168\.7±\\pm5\.1RLOO87\.6±\\pm4\.378\.2±\\pm8\.387\.3±\\pm5\.881\.3±\\pm7\.671\.9±\\pm5\.248\.9±\\pm8\.475\.5±\\pm4\.680\.3±\\pm3\.265\.7±\\pm4\.0GRPO90\.8±\\pm5\.166\.1±\\pm6\.789\.3±\\pm5\.474\.7±\\pm6\.972\.5±\\pm5\.464\.7±\\pm7\.377\.6±\\pm5\.279\.3±\\pm2\.866\.1±\\pm3\.7GRPO \+ ProGPO90\.0±\\pm4\.167\.5±\\pm8\.3688\.4±\\pm2\.391\.2±\\pm12\.576\.2±\\pm1\.658\.4±\\pm18\.479\.7±\\pm3\.3↑\\,\\uparrow2\.183\.3±\\pm3\.6↑\\,\\uparrow4\.068\.2±\\pm4\.3↑\\,\\uparrow2\.1GiGPO97\.7±\\pm1\.682\.7±\\pm7\.998\.8±\\pm1\.683\.7±\\pm7\.289\.3±\\pm8\.279\.2±\\pm6\.690\.8±\\pm1\.384\.4±\\pm2\.972\.8±\\pm3\.2GiGPO \+ ProGPO100\.0±\\pm0\.097\.2±\\pm4\.891\.8±\\pm0\.483\.4±\\pm3\.087\.1±\\pm3\.391\.0±\\pm4\.792\.5±\\pm0\.9↑\\,\\uparrow1\.785\.9±\\pm0\.2↑\\,\\uparrow1\.576\.2±\\pm1\.1↑\\,\\uparrow3\.4HGPO98\.9±\\pm1\.288\.8±\\pm1\.698\.9±\\pm0\.495\.3±\\pm6\.086\.8±\\pm1\.398\.1±\\pm1\.295\.4±\\pm0\.689\.0±\\pm1\.078\.5±\\pm1\.4HGPO \+ ProGPO100\.0±\\pm0\.095\.5±\\pm6\.496\.7±\\pm0\.092\.5±\\pm2\.388\.0±\\pm4\.297\.6±\\pm3\.495\.7±\\pm0\.6↑\\,\\uparrow0\.389\.0±\\pm1\.679\.7±\\pm1\.4↑\\,\\uparrow1\.2

### 5\.2Main Results

Table[1](https://arxiv.org/html/2607.22724#S5.T1)summarizes the main results\. Prompting\-only agents, including strong closed\-source models, still struggle on these long\-horizon tasks, while RL training improves substantially over prompting\. We highlight three observations:\(i\) ProGPO improves group\-based RL across scales and benchmarks\.At 1\.5B it lifts GRPO/GiGPO/HGPO on ALFWorld \(72\.8→74\.572\.8\{\\to\}74\.5,86\.7→91\.486\.7\{\\to\}91\.4,92\.8→95\.792\.8\{\\to\}95\.7\) and on WebShop success \(56\.8→60\.956\.8\{\\to\}60\.9,65\.0→72\.465\.0\{\\to\}72\.4,71\.5→75\.771\.5\{\\to\}75\.7\); the same pattern holds at 7B, where GRPO and GiGPO rise on ALFWorld \(77\.6→82\.077\.6\{\\to\}82\.0,90\.8→92\.590\.8\{\\to\}92\.5\) and every base improves on WebShop success \(66\.1→68\.266\.1\{\\to\}68\.2,72\.8→76\.272\.8\{\\to\}76\.2,78\.5→79\.778\.5\{\\to\}79\.7\)\. The sole non\-gaining aggregate is the near\-ceiling 7B HGPO on ALFWorld \(95\.495\.4vs\.95\.395\.3\), exactly where the fallback has no room to act: all\-fail groups are rare and ProGPO provably reduces to the base estimator \(Proposition[4\.3](https://arxiv.org/html/2607.22724#S4.Thmtheorem3)\)—yet even there WebShop success still improves \(78\.5→79\.778\.5\{\\to\}79\.7\)\.\(ii\) ProGPO’s gains concentrate on hard, all\-fail\-prone subtasks\.Improvements are largest where the base policy almost never succeeds and all\-fail groups dominate: at 1\.5B, GiGPO\+ProGPO liftsLook67\.5→84\.467\.5\{\\to\}84\.4,Cool79\.8→90\.279\.8\{\\to\}90\.2,Pick276\.4→92\.876\.4\{\\to\}92\.8, while the easyPickis saturated\. This is the introduction’s diagnosis made quantitative—failed trajectories are not equally wrong, and ProGPO recovers the hidden contrast precisely in the all\-fail regime\.\(iii\) ProGPO compounds with step\-level credit\.The strongest results pair ProGPO with step\-level bases \(1\.5B ALFWorld: GRPO\+ProGPO74\.574\.5vs\. GiGPO\+ProGPO91\.491\.4, HGPO\+ProGPO95\.795\.7\)\. The two mechanisms are complementary: step\-level credit resolves within\-trajectory attribution once any contrast exists, while ProGPO restores the group\-level signal when all trajectories fail\.

Table 2:Ablation on conditional gating \(w/ow/oConditional==always\-on progress\) on ALFWorld and WebShop \(Qwen2\.5\-1\.5B, GRPO and GiGPO bases, 150 epochs\)\.Boldmarks the best per column\.MethodALFWorldWebShopPickLookCleanHeatCoolPick2AllScoreSucc\.GRPO85\.3±\\pm1\.553\.7±\\pm8\.084\.5±\\pm6\.878\.2±\\pm7\.959\.7±\\pm5\.053\.5±\\pm5\.672\.8±\\pm3\.675\.8±\\pm3\.556\.8±\\pm3\.8w/ow/oConditional77\.5±\\pm7\.463\.1±\\pm12\.478\.3±\\pm5\.077\.6±\\pm13\.569\.3±\\pm11\.147\.4±\\pm10\.368\.3±\\pm2\.773\.0±\\pm4\.758\.6±\\pm4\.1GRPO \+ ProGPO84\.1±\\pm5\.676\.3±\\pm15\.174\.8±\\pm8\.169\.6±\\pm9\.283\.2±\\pm4\.450\.8±\\pm11\.374\.5±\\pm1\.676\.2±\\pm1\.060\.9±\\pm2\.2GiGPO94\.4±\\pm5\.967\.5±\\pm4\.694\.8±\\pm3\.894\.4±\\pm7\.879\.8±\\pm4\.776\.4±\\pm5\.486\.7±\\pm1\.783\.1±\\pm1\.665\.0±\\pm3\.2w/ow/oConditional99\.2±\\pm1\.678\.9±\\pm12\.195\.7±\\pm4\.098\.8±\\pm2\.481\.9±\\pm8\.687\.4±\\pm1\.390\.9±\\pm2\.578\.5±\\pm3\.268\.8±\\pm2\.9GiGPO \+ ProGPO92\.2±\\pm6\.784\.4±\\pm15\.095\.7±\\pm4\.087\.8±\\pm7\.390\.2±\\pm4\.492\.8±\\pm2\.791\.4±\\pm1\.685\.6±\\pm0\.572\.4±\\pm0\.6

![Refer to caption](https://arxiv.org/html/2607.22724v1/x4.png)Figure 4:Per\-stage training\-time\(s\) delta of GiGPO vs\. GiGPO\+ProGPO on 1\.5B ALFWorld on four GPUs\.Ablation Study\.Always\-on progress \(w/ow/oConditional\) trails ProGPO on both benchmarks: it trains but stays below conditional ProGPO on ALFWorld \(90\.990\.9vs\.91\.491\.4\) and WebShop \(68\.868\.8vs\.72\.472\.4\), and forfeits the non\-interference guarantee \(Proposition[4\.3](https://arxiv.org/html/2607.22724#S4.Thmtheorem3)\)\. The loss concentrates where terminal reward is already informative, exactly where an unconditional dense signal competes with it\(Appendix[7\.5](https://arxiv.org/html/2607.22724#S7.SS5)\)\. Conditional gating keeps the repair where it helps and removes it where it hurts, under one fixed configuration\.

![Refer to caption](https://arxiv.org/html/2607.22724v1/x5.png)Figure 5:Training dynamics of ProGPO and its baseline on ALFWorld and WebShop\. The lighter curves show the original curves, while the darker curves correspond to exponential moving average \(EMA\) smoothing with decayα=0\.95\\alpha=0\.95, highlighting the overall training trends\.Training dynamics\.Figure[5](https://arxiv.org/html/2607.22724#S5.F5)plots success rate against training epochs, comparing each ProGPO\-augmented method with its baseline under matched rollouts, hyperparameters, and seeds\. All\-fail groups dominate the early phase \(75–92% of groups\), so the baseline draws gradient from only a small slice of its rollouts and climbs slowly \(32\.8% at epoch 60\), whereas ProGPO turns the degenerate majority into weak preference signals and leads throughout \(49\.2% at epoch 60\)\. Late in training the baseline saturates—the remaining hard tasks again yield all\-fail groups with zero gradient—while ProGPO keeps improving to 91\.4% by extracting signal from exactly those residual groups\.

Computational Budget\.ProGPO reuses the base algorithm’s rollouts, log\-probabilities, and clipped updates unchanged, adding no critic, reward model or progress estimator\. Its two ingredients—the per\-step*progress score*\(a per\-trajectory hash\-setO​\(1\)O\(1\)novelty check\) and the group\-level*conditional switch*\(a few scalar statistics per group\)\. Figure[4](https://arxiv.org/html/2607.22724#S5.F4)decomposes the per\-iteration training time on 1\.5B ALFWorld: the Advantage stage moves0\.587→0\.5850\.587\{\\to\}0\.585s while total training time drops from184\.0184\.0to171\.8171\.8s/iter\.

### 5\.3Why ProGPO Works

![Refer to caption](https://arxiv.org/html/2607.22724v1/x6.png)Figure 6:Analysis of the injected signal during training\. \(a\) The*Shuffle*and*Random*controls confirm that ProGPO’s signal is genuinely progress\-aligned rather than incidental\. \(b\) ProGPO suppresses low\-progress actions and shifts probability mass toward under\-sampled, high\-progress ones\. \(c\) ProGPO outperforms alternative signals \(e\.g\. observation\-change, negated\-advantage\)\.We now examine how ProGPO reshapes learning through an offline audit of the policy shiftΔ​log⁡π=log⁡πθ−log⁡πref\\Delta\\log\\pi=\\log\\pi\_\{\\theta\}\-\\log\\pi\_\{\\mathrm\{ref\}\}on admissible\-action decisions from ALFWorld \(protocol and full statistics in Appendix[9](https://arxiv.org/html/2607.22724#S9)\)\. Figure[6](https://arxiv.org/html/2607.22724#S5.F6)summarizes the three findings below\.

ProGPO restores a non\-zero, progress\-aligned gradient\.On all\-fail groups the base estimator emits no update, so ProGPO must first restore a gradient that tracks progress rather than noise\. Figure[6](https://arxiv.org/html/2607.22724#S5.F6)\(a\) shows a clear progress alignment for ProGPO that vanishes under*Shuffle*which permutes scores within each group, and remains only moderate under*Random*\. ProGPO’s contribution is thus the gradient’s*consistent*progress alignment, not its mere non\-zero magnitude\. Exact correlations and low\-effect suppression values are reported in Appendix[9\.3](https://arxiv.org/html/2607.22724#S9.SS3)\.

ProGPO recalibrates the action distribution\.A progress\-aligned gradient helps only if it reaches the under\-sampled actions identified in the introduction \(Section[1](https://arxiv.org/html/2607.22724#S1)\)\. Splitting the paired shiftΔpair​log⁡π=log⁡πProGPO−log⁡πGiGPO\\Delta\_\{\\mathrm\{pair\}\}\\log\\pi=\\log\\pi\_\{\\mathrm\{ProGPO\}\}\-\\log\\pi\_\{\\mathrm\{GiGPO\}\}by reference\-policy probability band and action effect \(Figure[6](https://arxiv.org/html/2607.22724#S5.F6)\(b\)\) reveals a targeted move rather than a uniform entropy rise: ProGPO lifts mid\-band state\-changing actions and holds low\-effect actions down, then fades by the end of training as the fallback disengages\.*Obs\-Change*produces a larger raw mid\-band shift yet scores lower, since without a novelty gate the added mass leaks onto revisits \(per\-band values in Appendix[10\.3](https://arxiv.org/html/2607.22724#S10.SS3)\)\.

Alignment and novelty are necessary\.Figure[6](https://arxiv.org/html/2607.22724#S5.F6)shows that an effective signal requires both trajectory alignment and observation novelty\.Trajectory alignment\.*Shuffle*preserves the within\-group score distribution but permutes scores across trajectories,*Random*replaces them with unrelated noise, and*Neg*reverses their sign\. All underperform the base estimator, indicating that the gain comes from correctly pairing score with the trajectory that produced it instead of the score distribution alone\.Observation novelty\.*Obs\-Change*removes the first\-visit filter and credits every observation change, while*Edit\-D\.*uses the edit distance between consecutive observations as the score\. Both degrade on overall performance and the cycle\-prone Pick2 task, showing filtering revisits is critical for keeping the fallback signal aligned with progress\. More details shown in Appendixx[10\.3](https://arxiv.org/html/2607.22724#S10.SS3)\.

Hyperparameter sensitivity\.ProGPO’s fallback scaleλaux\\lambda\_\{\\mathrm\{aux\}\}is fixed at0\.30\.3across all environments, scales, and base algorithms without per\-task tuning\. The remaining two hyperparameters,τR\\tau\_\{R\}andτP\\tau\_\{P\}, are numerical\-stability thresholds \(10−310^\{\-3\}and10−410^\{\-4\}\) that guard against division by degenerate within\-group variance; they are not task\-tuned and require no sweep\. A full\-budget sweep ofλaux∈\{0\.1,0\.3,0\.5,0\.7,1\.0\}\\lambda\_\{\\mathrm\{aux\}\}\\in\\\{0\.1,0\.3,0\.5,0\.7,1\.0\\\}on ALFWorld \(Table[11](https://arxiv.org/html/2607.22724#S10.T11)\) shows the default0\.30\.3achieves92\.2%92\.2\\%overall success, within2\.32\.3pp of the best setting \(0\.10\.1:94\.5%94\.5\\%\) and clearly above0\.50\.5\(78\.3%78\.3\\%\) and0\.70\.7\(83\.6%83\.6\\%\)\. Full numbers are provided in Appendix[10\.6](https://arxiv.org/html/2607.22724#S10.SS6)\.

## 6Conclusion

We identify the*self\-reinforcing credit trap*as a core obstacle to group\-based RL on long\-horizon LLM agents\. When every trajectory in a rollout group shares the same failure outcome, the group\-relative advantage collapses to zero and the sampling imbalance that produced the group cannot be corrected\. ProGPO repairs credit assignment on such groups by ranking trajectories with a first\-visit observation coverage score, activated only when the within\-group reward variance is uninformative\. It introduces no auxiliary model or reward modification, provably reduces to the base estimator when the reward is informative, and disengages exponentially as the policy improves\. Across ALFWorld and WebShop with Qwen2\.5\-1\.5B/7B, ProGPO improves three group\-based bases \(GRPO, GiGPO, HGPO\) and delivers its largest gains on hard, all\-fail\-prone subtasks where the base estimator stalls\. Offline experiments confirm the mechanism: the injected gradient is progress\-aligned, and probability mass shifts toward under\-sampled state\-changing actions while low\-effect actions are suppressed\. The coverage score measures movement instead of task value and relies on textual observations to detect novelty\. Extending it to non\-textual or partially observed settings is left to future work\. More broadly, our results indicate that failed rollouts are not equally uninformative: the behavioral contrast among them is a resource that outcome\-only estimators discard and that can be recovered without adding supervision\.

## References

- Achiam et al\. \[2023\]Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al\.GPT\-4 technical report\.*arXiv preprint arXiv:2303\.08774*, 2023\.
- Ahmadian et al\. \[2024\]Arash Ahmadian, Chris Cremer, Matthias Gallé, Marzieh Fadaee, Julia Kreutzer, Olivier Pietquin, Ahmet Üstün, and Sara Hooker\.Back to basics: Revisiting reinforce\-style optimization for learning from human feedback in llms\.In*Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics \(Volume 1: Long Papers\)*, pages 12248–12267, 2024\.
- Bamba et al\. \[2025\]Udbhav Bamba, Minghao Fang, Yifan Yu, Haizhong Zheng, and Fan Lai\.Xrpo: Pushing the limits of grpo with targeted exploration and exploitation\.*arXiv preprint arXiv:2510\.06672*, 2025\.
- \[4\]Huacan Chai, Zijie Cao, Maolin Ran, Yingxuan Yang, Jianghao Lin, Renjie Ding, Ziyu Wan, Muning Wen, Weiwen Liu, Weinan Zhang, et al\.Progra: Progress\-aware reinforcement learning for multi\-turn function calling\.
- Cheng et al\. \[2026\]Xin Cheng, Shuo He, Lang Feng, HaiYang Xu, Ming Yan, Lei Feng, and Bo An\.Beyond trajectory\-level attribution: Graph\-based credit assignment for agentic reinforcement learning\.*arXiv preprint arXiv:2605\.26684*, 2026\.
- Fang et al\. \[2026\]Yangyi Fang, Jiaye Lin, Xiaoliang Fu, Cong Qin, Haolin Shi, and Chang Liu\.Proximity\-based multi\-turn optimization: Practical credit assignment for llm agent training\.In*Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics \(ACL 2026\)*, pages 285–307, 2026\.
- Feng et al\. \[2025\]Lang Feng, Weihao Tan, Zhiyi Lyu, Longtao Zheng, Haiyang Xu, Ming Yan, Fei Huang, and Bo An\.Towards efficient online tuning of VLM agents via counterfactual soft reinforcement learning\.In*International Conference on Machine Learning*, 2025\.
- Feng et al\. \[2026\]Lang Feng, Zhenghai Xue, Tingcong Liu, and Bo An\.Group\-in\-group policy optimization for llm agent training\.*Advances in Neural Information Processing Systems*, 38:46375–46408, 2026\.
- Furuta et al\. \[2024\]Hiroki Furuta, Kuang\-Huei Lee, Ofir Nachum, Yutaka Matsuo, Aleksandra Faust, Shixiang Shane Gu, and Izzeddin Gur\.Multimodal web navigation with instruction\-finetuned foundation models\.In*The Twelfth International Conference on Learning Representations*, 2024\.URL[https://openreview\.net/forum?id=efFmBWioSc](https://openreview.net/forum?id=efFmBWioSc)\.
- Gou et al\. \[2025\]Boyu Gou, Ruohan Wang, Boyuan Zheng, Yanan Xie, Cheng Chang, Yiheng Shu, Huan Sun, and Yu Su\.Navigating the digital world as humans do: Universal visual grounding for GUI agents\.In*The Thirteenth International Conference on Learning Representations*, 2025\.URL[https://openreview\.net/forum?id=kxnoqaisCT](https://openreview.net/forum?id=kxnoqaisCT)\.
- He et al\. \[2026\]Shuo He, Lang Feng, Qi Wei, Xin Cheng, Lei Feng, and Bo An\.Hierarchy\-of\-groups policy optimization for long\-horizon agentic tasks\.*arXiv preprint arXiv:2602\.22817*, 2026\.
- Kool et al\. \[2019\]Wouter Kool, Herke van Hoof, and Max Welling\.Buy 4 reinforce samples, get a baseline for free\!In*ICLR 2019 Workshop*, 2019\.
- Le et al\. \[2025\]Thanh\-Long V Le, Myeongho Jeon, Kim Vu, Viet Lai, and Eunho Yang\.No prompt left behind: Exploiting zero\-variance prompts in llm reinforcement learning via entropy\-guided advantage shaping\.*arXiv preprint arXiv:2509\.21880*, 2025\.
- Li et al\. \[2026\]Jiazheng Li, Yawei Wang, Qiaojing Yan, Yijun Tian, Zhichao Xu, Huan Song, Panpan Xu, and Lin Lee Cheong\.Salt: Step\-level advantage assignment for long\-horizon agents via trajectory graph\.In*Findings of the Association for Computational Linguistics: EACL 2026*, pages 4709–4725, 2026\.
- Li et al\. \[2024\]Manling Li, Shiyu Zhao, Qineng Wang, Kangrui Wang, Yu Zhou, Sanjana Srivastava, Cem Gokmen, Tony Lee, Erran Li Li, Ruohan Zhang, et al\.Embodied agent interface: Benchmarking LLMs for embodied decision making\.*Advances in Neural Information Processing Systems*, 37:100428–100534, 2024\.
- Liu et al\. \[2025a\]Xiaoqian Liu, Ke Wang, Yuchuan Wu, Fei Huang, Yongbin Li, Junge Zhang, and Jianbin Jiao\.Agentic reinforcement learning with implicit step rewards\.*arXiv preprint arXiv:2509\.19199*, 2025a\.
- Liu et al\. \[2025b\]Zichen Liu, Changyu Chen, Wenjun Li, Penghui Qi, Tianyu Pang, Chao Du, Wee Sun Lee, and Min Lin\.Understanding r1\-zero\-like training: A critical perspective\.*arXiv preprint arXiv:2503\.20783*, 2025b\.
- Ma et al\. \[2026\]Shichao Ma, Zhiyuan Ma, Ming Yang, Xiaofan Li, Xing Wu, Jintao Du, Yu Cheng, Weiqiang Wang, Qiliang Liu, Zhengyang Zhou, et al\.Tspo: Breaking the double homogenization dilemma in multi\-turn search policy optimization\.*arXiv preprint arXiv:2601\.22776*, 2026\.
- Nan et al\. \[2025\]Gongrui Nan, Siye Chen, Jing Huang, Mengyu Lu, Dexun Wang, Chunmei Xie, Weiqi Xiong, Xianzhou Zeng, Qixuan Zhou, Yadong Li, et al\.Ngrpo: Negative\-enhanced group relative policy optimization\.*arXiv preprint arXiv:2509\.18851*, 2025\.
- Qian et al\. \[2025\]Cheng Qian, Emre Can Acikgoz, Qi He, Hongru Wang, Xiusi Chen, Dilek Hakkani\-Tür, Gokhan Tur, and Heng Ji\.ToolRL: Reward is all tool learning needs\.*arXiv preprint arXiv:2504\.13958*, 2025\.
- Raileanu and Rocktäschel \[2020\]Roberta Raileanu and Tim Rocktäschel\.Ride: Rewarding impact\-driven exploration for procedurally\-generated environments\.*arXiv preprint arXiv:2002\.12292*, 2020\.
- Schick et al\. \[2023\]Timo Schick, Jane Dwivedi\-Yu, Roberto Dessì, Roberta Raileanu, Maria Lomeli, Eric Hambro, Luke Zettlemoyer, Nicola Cancedda, and Thomas Scialom\.Toolformer: Language models can teach themselves to use tools\.*Advances in Neural Information Processing Systems*, 36:68539–68551, 2023\.
- Schulman et al\. \[2017\]John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov\.Proximal policy optimization algorithms\.*arXiv preprint arXiv:1707\.06347*, 2017\.
- Shao et al\. \[2024\]Zhihong Shao, Peiyi Wang, Qihao Zhu, Runxin Xu, Junxiao Song, Xiao Bi, Haowei Zhang, Mingchuan Zhang, YK Li, Y Wu, et al\.DeepSeekMath: Pushing the limits of mathematical reasoning in open language models\.*arXiv preprint arXiv:2402\.03300*, 2024\.
- Shinn et al\. \[2024\]Noah Shinn, Federico Cassano, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao\.Reflexion: Language agents with verbal reinforcement learning\.*Advances in Neural Information Processing Systems*, 36, 2024\.
- Shridhar et al\. \[2021\]Mohit Shridhar, Xingdi Yuan, Marc\-Alexandre Cote, Yonatan Bisk, Adam Trischler, and Matthew Hausknecht\.ALFWorld: Aligning text and embodied environments for interactive learning\.In*International Conference on Learning Representations*, 2021\.URL[https://openreview\.net/forum?id=0IOX0YcCdTn](https://openreview.net/forum?id=0IOX0YcCdTn)\.
- Team et al\. \[2023\]Gemini Team, Rohan Anil, Sebastian Borgeaud, Jean\-Baptiste Alayrac, Jiahui Yu, Radu Soricut, Johan Schalkwyk, Andrew M Dai, Anja Hauth, Katie Millican, et al\.Gemini: A family of highly capable multimodal models\.*arXiv preprint arXiv:2312\.11805*, 2023\.
- Team et al\. \[2025\]Kimi Team, Angang Du, Bofei Gao, Bowei Xing, Changjiu Jiang, Cheng Chen, Cheng Li, Chenjun Xiao, Chenzhuang Du, Chonghua Liao, et al\.Kimi k1\.5: Scaling reinforcement learning with LLMs\.*arXiv preprint arXiv:2501\.12599*, 2025\.
- Wang et al\. \[2024a\]Guanzhi Wang, Yuqi Xie, Yunfan Jiang, Ajay Mandlekar, Chaowei Xiao, Yuke Zhu, Linxi Fan, and Anima Anandkumar\.Voyager: An open\-ended embodied agent with large language models\.*Transactions on Machine Learning Research*, 2024a\.ISSN 2835\-8856\.
- Wang et al\. \[2025a\]Guoqing Wang, Sunhao Dai, Guangze Ye, Zeyu Gan, Wei Yao, Yong Deng, Xiaofeng Wu, and Zhenzhe Ying\.Information gain\-based policy optimization: A simple and effective approach for multi\-turn llm agents\.*arXiv preprint arXiv:2510\.14967*, 2025a\.
- Wang et al\. \[2025b\]Hanlin Wang, Chak Tou Leong, Jiashuo Wang, Jian Wang, and Wenjie Li\.Spa\-rl: Reinforcing llm agents via stepwise progress attribution\.*arXiv preprint arXiv:2505\.20732*, 2025b\.
- Wang et al\. \[2025c\]Hanlin Wang, Chak Tou Leong, Jiashuo Wang, Jian Wang, and Wenjie Li\.Spa\-rl: Reinforcing llm agents via stepwise progress attribution\.*arXiv preprint arXiv:2505\.20732*, 2025c\.
- Wang et al\. \[2024b\]Junyang Wang, Haiyang Xu, Haitao Jia, Xi Zhang, Ming Yan, Weizhou Shen, Ji Zhang, Fei Huang, and Jitao Sang\.Mobile\-Agent\-v2: Mobile device operation assistant with effective navigation via multi\-agent collaboration\.*Advances in Neural Information Processing Systems*, 37:2686–2710, 2024b\.
- Wei et al\. \[2025\]Yuxiang Wei, Olivier Duchenne, Jade Copet, Quentin Carbonneaux, Lingming Zhang, Daniel Fried, Gabriel Synnaeve, Rishabh Singh, and Sida I Wang\.SWE\-RL: Advancing llm reasoning via reinforcement learning on open software evolution\.*arXiv preprint arXiv:2502\.18449*, 2025\.
- Xi et al\. \[2026\]Zhiheng Xi, Chenyang Liao, Guanyu Li, Zhihao Zhang, Wenxiang Chen, Binghai Wang, Senjie Jin, Yuhao Zhou, Jian Guan, Wei Wu, et al\.Agentprm: Process reward models for llm agents via step\-wise promise and progress\.In*Proceedings of the ACM Web Conference 2026*, pages 4184–4195, 2026\.
- Xiong et al\. \[2024\]Weimin Xiong, Yifan Song, Xiutian Zhao, Wenhao Wu, Xun Wang, Ke Wang, Cheng Li, Wei Peng, and Sujian Li\.Watch every step\! llm agent learning via iterative step\-level process refinement\.In*Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing*, pages 1556–1572, 2024\.
- Yang et al\. \[2025\]An Yang, Anfeng Li, Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chang Gao, Chengen Huang, Chenxu Lv, et al\.Qwen3 technical report\.*arXiv preprint arXiv:2505\.09388*, 2025\.
- Yao et al\. \[2022a\]Shunyu Yao, Howard Chen, John Yang, and Karthik Narasimhan\.WebShop: Towards scalable real\-world web interaction with grounded language agents\.*Advances in Neural Information Processing Systems*, 35:20744–20757, 2022a\.
- Yao et al\. \[2022b\]Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao\.React: Synergizing reasoning and acting in language models\.*arXiv preprint arXiv:2210\.03629*, 2022b\.
- Yu et al\. \[2025\]Qiying Yu, Zheng Zhang, Ruofei Zhu, Yufeng Yuan, Xiaochen Zuo, Yu Yue, Tiantian Fan, Gaohong Liu, Lingjun Liu, Xin Liu, et al\.DAPO: An open\-source LLM reinforcement learning system at scale\.*arXiv preprint arXiv:2503\.14476*, 2025\.
- Yu et al\. \[2026\]Xiao Yu, Baolin Peng, Ruize Xu, Yelong Shen, Pengcheng He, Suman Nath, Nikhil Singh, Jiangfeng Gao, and Zhou Yu\.Reinforcement world model learning for llm\-based agents\.*arXiv preprint arXiv:2602\.05842*, 2026\.
- Zhang et al\. \[2025\]Xichen Zhang, Sitong Wu, Yinghao Zhu, Haoru Tan, Shaozuo Yu, Ziyi He, and Jiaya Jia\.Scaf\-grpo: Scaffolded group relative policy optimization for enhancing llm reasoning\.*arXiv preprint arXiv:2510\.19807*, 2025\.
- Zhou et al\. \[2024\]Yifei Zhou, Andrea Zanette, Jiayi Pan, Sergey Levine, and Aviral Kumar\.ArCHer: Training language model agents via hierarchical multi\-turn rl\.In*International Conference on Machine Learning*, pages 62178–62209\. PMLR, 2024\.

## 7Proofs of Propositions and Worked Example

This appendix is organized to make the theoretical and empirical claims in the main text independently checkable\. We first prove Propositions[4\.1](https://arxiv.org/html/2607.22724#S4.Thmtheorem1)–[4\.4](https://arxiv.org/html/2607.22724#S4.Thmtheorem4), state the exact finite\-group bias of the group\-mean estimator, and derive the automatic\-disengagement bound used in Section[4\.2](https://arxiv.org/html/2607.22724#S4.SS2)\. We then work through a complete all\-fail group by hand\. Subsequent sections specify the implementation and evaluation protocols, report disaggregated results and training diagnostics, and conclude with a qualitative case study, limitations, and the required disclosure statement\.

### 7\.1Proof of Proposition[4\.1](https://arxiv.org/html/2607.22724#S4.Thmtheorem1)

Setup\.Fix a trajectoryτ\\tauof lengthTTwith observation sequence\(o1,…,oT\+1\)\(o\_\{1\},\\ldots,o\_\{T\+1\}\)\. Let𝒪​\(τ\)=\{o1,…,oT\+1\}\\mathcal\{O\}\(\\tau\)=\\\{o\_\{1\},\\ldots,o\_\{T\+1\}\\\}denote the set of distinct observations, so thatD​\(τ\)=\|𝒪​\(τ\)\|D\(\\tau\)=\|\\mathcal\{O\}\(\\tau\)\|, and let𝒱t=\{o1,…,ot\}\\mathcal\{V\}\_\{t\}=\\\{o\_\{1\},\\ldots,o\_\{t\}\\\}be the prefix set\. Recall from Eqs\. \([5](https://arxiv.org/html/2607.22724#S4.E5)\)–\([6](https://arxiv.org/html/2607.22724#S4.E6)\) thatδt=𝟏​\[ot\+1∉𝒱t\]\\delta\_\{t\}=\\mathbf\{1\}\[o\_\{t\+1\}\\notin\\mathcal\{V\}\_\{t\}\]andP​\(τ\)=1T​∑t=1TδtP\(\\tau\)=\\frac\{1\}\{T\}\\sum\_\{t=1\}^\{T\}\\delta\_\{t\}\. For eacho∈𝒪​\(τ\)o\\in\\mathcal\{O\}\(\\tau\), define its first\-occurrence index

ρ​\(o\)=min⁡\{s∈\{1,…,T\+1\}:os=o\}\.\\displaystyle\\rho\(o\)\\;=\\;\\min\\\{s\\in\\\{1,\\ldots,T\+1\\\}:o\_\{s\}=o\\\}\.\(9\)
*Part \(i\)\.*By definition of𝒱t\\mathcal\{V\}\_\{t\},

δt=1⟺ot\+1∉\{o1,…,ot\}⟺ρ​\(ot\+1\)=t\+1\.\\displaystyle\\delta\_\{t\}=1\\quad\\Longleftrightarrow\\quad o\_\{t\+1\}\\notin\\\{o\_\{1\},\\ldots,o\_\{t\}\\\}\\quad\\Longleftrightarrow\\quad\\rho\(o\_\{t\+1\}\)=t\+1\.\(10\)Consider the mapΦ:t↦ot\+1\\Phi:t\\mapsto o\_\{t\+1\}restricted to the index set𝒯1=\{t∈\{1,…,T\}:δt=1\}\\mathcal\{T\}\_\{1\}=\\\{t\\in\\\{1,\\ldots,T\\\}:\\delta\_\{t\}=1\\\}\. By Eq\. \([10](https://arxiv.org/html/2607.22724#S7.E10)\),Φ\\Phimaps𝒯1\\mathcal\{T\}\_\{1\}into\{o∈𝒪​\(τ\):ρ​\(o\)≥2\}\\\{o\\in\\mathcal\{O\}\(\\tau\):\\rho\(o\)\\geq 2\\\}; it is injective because two indicest≠t′t\\neq t^\{\\prime\}in𝒯1\\mathcal\{T\}\_\{1\}satisfyρ​\(ot\+1\)=t\+1≠t′\+1=ρ​\(ot′\+1\)\\rho\(o\_\{t\+1\}\)=t\+1\\neq t^\{\\prime\}\+1=\\rho\(o\_\{t^\{\\prime\}\+1\}\), and it is surjective because everyoowithρ​\(o\)=s≥2\\rho\(o\)=s\\geq 2is the image oft=s−1∈𝒯1t=s\-1\\in\\mathcal\{T\}\_\{1\}\. HenceΦ\\Phiis a bijection, and sinceρ​\(o1\)=1\\rho\(o\_\{1\}\)=1accounts for exactly one element of𝒪​\(τ\)\\mathcal\{O\}\(\\tau\),

∑t=1Tδt=\|𝒯1\|=\|\{o∈𝒪​\(τ\):ρ​\(o\)≥2\}\|=D​\(τ\)−1,i\.e\.,P​\(τ\)=D​\(τ\)−1T\.\\displaystyle\\sum\_\{t=1\}^\{T\}\\delta\_\{t\}\\;=\\;\|\\mathcal\{T\}\_\{1\}\|\\;=\\;\\bigl\|\\\{o\\in\\mathcal\{O\}\(\\tau\):\\rho\(o\)\\geq 2\\\}\\bigr\|\\;=\\;D\(\\tau\)\-1,\\qquad\\text\{i\.e\.,\}\\qquad P\(\\tau\)=\\frac\{D\(\\tau\)\-1\}\{T\}\.\(11\)For a fixed horizonTT, replacing a transition by a no\-op repetition \(ot\+1=oto\_\{t\+1\}=o\_\{t\}\) or a cyclic revisit \(ot\+1∈𝒱to\_\{t\+1\}\\in\\mathcal\{V\}\_\{t\}\) cannot increaseD​\(τ\)D\(\\tau\)and therefore cannot increaseP​\(τ\)P\(\\tau\)\. More generally, inserting an additional revisit leavesD​\(τ\)D\(\\tau\)unchanged but increases the denominator toT\+1T\+1, so the normalized score weakly decreases\. Thus repetitions and cycles never receive first\-visit credit\.

*Part \(ii\)\.*Letτ\\taube any trajectory withR​\(τ\)=1R\(\\tau\)=1\. By the definition ofmxm\_\{x\}\-separation, completing taskxxrequires visiting at leastmxm\_\{x\}distinct observations, henceD​\(τ\)≥mxD\(\\tau\)\\geq m\_\{x\}\. Combining with Part \(i\),

P​\(τ\)=D​\(τ\)−1T≥mx−1T,\\displaystyle P\(\\tau\)\\;=\\;\\frac\{D\(\\tau\)\-1\}\{T\}\\;\\geq\\;\\frac\{m\_\{x\}\-1\}\{T\},\(12\)which establishes the containment

\{τ:R​\(τ\)=1\}⊆\{τ:P​\(τ\)≥mx−1T\}\.\\displaystyle\\\{\\tau:R\(\\tau\)=1\\\}\\;\\subseteq\\;\\Bigl\\\{\\tau:P\(\\tau\)\\geq\\tfrac\{m\_\{x\}\-1\}\{T\}\\Bigr\\\}\.\(13\)The inclusion is strict whenever there exists a trajectoryτ′\\tau^\{\\prime\}withR​\(τ′\)=0R\(\\tau^\{\\prime\}\)=0andD​\(τ′\)≥mxD\(\\tau^\{\\prime\}\)\\geq m\_\{x\}\(e\.g\., one that visits all required states but exhausts the step budget before the terminal action, asτ1\\tau\_\{1\}in Appendix[7\.6](https://arxiv.org/html/2607.22724#S7.SS6)\): suchτ′\\tau^\{\\prime\}belongs to the super\-level set but not to the success set\.

This concludes the proof of Proposition[4\.1](https://arxiv.org/html/2607.22724#S4.Thmtheorem1)\. ∎

### 7\.2Proof of Proposition[4\.3](https://arxiv.org/html/2607.22724#S4.Thmtheorem3)

LetgProGPO​\(Gx\)=1K​∑iAiProGPO​∇θlog⁡πθ​\(τi\)g^\{\\mathrm\{ProGPO\}\}\(G\_\{x\}\)=\\frac\{1\}\{K\}\\sum\_\{i\}A\_\{i\}^\{\\mathrm\{ProGPO\}\}\\nabla\_\{\\theta\}\\log\\pi\_\{\\theta\}\(\\tau\_\{i\}\)andgbase​\(Gx\)=1K​∑iAiR​∇θlog⁡πθ​\(τi\)g^\{\\mathrm\{base\}\}\(G\_\{x\}\)=\\frac\{1\}\{K\}\\sum\_\{i\}A\_\{i\}^\{R\}\\nabla\_\{\\theta\}\\log\\pi\_\{\\theta\}\(\\tau\_\{i\}\)denote the per\-group gradient contributions under the two estimators\. We use the population convention

σR2​\(Gx\)=1K​∑i=1K\(Ri−R¯Gx\)2,σP2​\(Gx\)=1K​∑i=1K\(Pi−P¯Gx\)2\.\\displaystyle\\sigma\_\{R\}^\{2\}\(G\_\{x\}\)=\\frac\{1\}\{K\}\\sum\_\{i=1\}^\{K\}\(R\_\{i\}\-\\bar\{R\}\_\{G\_\{x\}\}\)^\{2\},\\qquad\\sigma\_\{P\}^\{2\}\(G\_\{x\}\)=\\frac\{1\}\{K\}\\sum\_\{i=1\}^\{K\}\(P\_\{i\}\-\\bar\{P\}\_\{G\_\{x\}\}\)^\{2\}\.\(14\)The same conclusion applies to the clipped surrogate because the two objectives receive identical advantages on every reward\-informative group\. At the unclipped estimator level,

∇θ𝒥ProGPO−∇θ𝒥base=𝔼x,Gx​\[gProGPO​\(Gx\)−gbase​\(Gx\)\]\.\\displaystyle\\nabla\_\{\\theta\}\\mathcal\{J\}\_\{\\mathrm\{ProGPO\}\}\-\\nabla\_\{\\theta\}\\mathcal\{J\}\_\{\\mathrm\{base\}\}\\;=\\;\\mathbb\{E\}\_\{x,\\,G\_\{x\}\}\\bigl\[\\,g^\{\\mathrm\{ProGPO\}\}\(G\_\{x\}\)\-g^\{\\mathrm\{base\}\}\(G\_\{x\}\)\\,\\bigr\]\.\(15\)Partition the groups into the three regimes of Eq\. \([7](https://arxiv.org/html/2607.22724#S4.E7)\):

𝒢1\\displaystyle\\mathcal\{G\}\_\{1\}=\{Gx:σR​\(Gx\)≥τR\},\\displaystyle=\\\{G\_\{x\}:\\sigma\_\{R\}\(G\_\{x\}\)\\geq\\tau\_\{R\}\\\},\(16\)𝒢2\\displaystyle\\mathcal\{G\}\_\{2\}=\{Gx:σR​\(Gx\)<τR,R¯Gx=0,σP​\(Gx\)≥τP\},\\displaystyle=\\\{G\_\{x\}:\\sigma\_\{R\}\(G\_\{x\}\)<\\tau\_\{R\},\\ \\bar\{R\}\_\{G\_\{x\}\}=0,\\ \\sigma\_\{P\}\(G\_\{x\}\)\\geq\\tau\_\{P\}\\\},\(17\)𝒢3\\displaystyle\\mathcal\{G\}\_\{3\}=\{Gx:σR​\(Gx\)<τR\}∖𝒢2\.\\displaystyle=\\\{G\_\{x\}:\\sigma\_\{R\}\(G\_\{x\}\)<\\tau\_\{R\}\\\}\\setminus\\mathcal\{G\}\_\{2\}\.\(18\)We verify the claim on each cell of the partition\. For completeness, under binary rewards the smallest non\-zero population standard deviation among groups of sizeKKis

σR,min=min1≤m≤K−1⁡m​\(K−m\)K=K−1K,\\displaystyle\\sigma\_\{R,\\min\}=\\min\_\{1\\leq m\\leq K\-1\}\\frac\{\\sqrt\{m\(K\-m\)\}\}\{K\}=\\frac\{\\sqrt\{K\-1\}\}\{K\},\(19\)attained when exactly one trajectory has the minority outcome\. The binary\-outcome settingK=8K\{=\}8andτR=0\.01\\tau\_\{R\}\{=\}0\.01satisfiesτR<σR,min≈0\.331\\tau\_\{R\}<\\sigma\_\{R,\\min\}\\approx 0\.331\. Consequently,σR<τR\\sigma\_\{R\}<\\tau\_\{R\}is equivalent to zero reward variance under the standing assumptions of Proposition[4\.3](https://arxiv.org/html/2607.22724#S4.Thmtheorem3)\. The proposition’s support statement uses this threshold condition; its first statement, exact equality on every group withσR≥τR\\sigma\_\{R\}\\geq\\tau\_\{R\}, holds without it\.

*CaseGx∈𝒢1G\_\{x\}\\in\\mathcal\{G\}\_\{1\}\.*The first branch of Eq\. \([7](https://arxiv.org/html/2607.22724#S4.E7)\) givesAiProGPO=AiRA\_\{i\}^\{\\mathrm\{ProGPO\}\}=A\_\{i\}^\{R\}for allii, hencegProGPO​\(Gx\)=gbase​\(Gx\)g^\{\\mathrm\{ProGPO\}\}\(G\_\{x\}\)=g^\{\\mathrm\{base\}\}\(G\_\{x\}\)and the integrand of Eq\. \([15](https://arxiv.org/html/2607.22724#S7.E15)\) vanishes\. This proves the first statement of the proposition\.

*CaseGx∈𝒢2G\_\{x\}\\in\\mathcal\{G\}\_\{2\}\.*The conditionR¯Gx=0\\bar\{R\}\_\{G\_\{x\}\}=0and binary rewards directly impliesR1=⋯=RK=0R\_\{1\}=\\cdots=R\_\{K\}=0\. Consequently,

AiR=Ri−R¯GxσR​\(Gx\)\+ϵ=0−00\+ϵ=0for all​i,hencegbase​\(Gx\)=0\.\\displaystyle A\_\{i\}^\{R\}\\;=\\;\\frac\{R\_\{i\}\-\\bar\{R\}\_\{G\_\{x\}\}\}\{\\sigma\_\{R\}\(G\_\{x\}\)\+\\epsilon\}\\;=\\;\\frac\{0\-0\}\{0\+\\epsilon\}\\;=\\;0\\qquad\\text\{for all \}i,\\qquad\\text\{hence\}\\qquad g^\{\\mathrm\{base\}\}\(G\_\{x\}\)=0\.\(20\)
*CaseGx∈𝒢3G\_\{x\}\\in\\mathcal\{G\}\_\{3\}\.*The third branch of Eq\. \([7](https://arxiv.org/html/2607.22724#S4.E7)\) setsAiProGPO=0A\_\{i\}^\{\\mathrm\{ProGPO\}\}=0, sogProGPO​\(Gx\)=0g^\{\\mathrm\{ProGPO\}\}\(G\_\{x\}\)=0\. By Eqs\. \([19](https://arxiv.org/html/2607.22724#S7.E19)\) and the configured threshold,σR​\(Gx\)<τR\\sigma\_\{R\}\(G\_\{x\}\)<\\tau\_\{R\}forces zero reward variance; hence eitherRi=0R\_\{i\}=0for everyiiorRi=1R\_\{i\}=1for everyii\. In both casesRi=R¯GxR\_\{i\}=\\bar\{R\}\_\{G\_\{x\}\}, soAiR=0A\_\{i\}^\{R\}=0andgbase​\(Gx\)=0g^\{\\mathrm\{base\}\}\(G\_\{x\}\)=0\. The integrand again vanishes\.

Combining the three cases, the integrand of Eq\. \([15](https://arxiv.org/html/2607.22724#S7.E15)\) can be non\-zero only on𝒢2\\mathcal\{G\}\_\{2\}, wheregbase​\(Gx\)=0g^\{\\mathrm\{base\}\}\(G\_\{x\}\)=0identically\. Thus∇θ𝒥ProGPO−∇θ𝒥base\\nabla\_\{\\theta\}\\mathcal\{J\}\_\{\\mathrm\{ProGPO\}\}\-\\nabla\_\{\\theta\}\\mathcal\{J\}\_\{\\mathrm\{base\}\}is supported entirely on groups whose reward\-based gradient contribution is identically zero\.

This concludes the proof of Proposition[4\.3](https://arxiv.org/html/2607.22724#S4.Thmtheorem3)\. ∎

### 7\.3Proof of Proposition[4\.4](https://arxiv.org/html/2607.22724#S4.Thmtheorem4)and Exact Finite\-Group Characterization

##### Algebraic identity\.

For a group entering the fallback branch of Eq\. \([7](https://arxiv.org/html/2607.22724#S4.E7)\), the advantage isAiProGPO=λ​\(Pi−P¯Gx\)/\(σP​\(Gx\)\+ϵ\)A\_\{i\}^\{\\mathrm\{ProGPO\}\}=\\lambda\\,\(P\_\{i\}\-\\bar\{P\}\_\{G\_\{x\}\}\)/\(\\sigma\_\{P\}\(G\_\{x\}\)\+\\epsilon\)\. Substituting into the per\-group gradient contribution and factoring out the group\-constant scalec​\(Gx\)=λ/\(σP​\(Gx\)\+ϵ\)\>0c\(G\_\{x\}\)=\\lambda/\(\\sigma\_\{P\}\(G\_\{x\}\)\+\\epsilon\)\>0,

g​\(Gx\)=1K​∑i=1KAiProGPO​∇θlog⁡πθ​\(τi\)=λσP​\(Gx\)\+ϵ⏟c​\(Gx\)\>0⋅1K​∑i=1K\(Pi−P¯Gx\)​∇θlog⁡πθ​\(τi\)⏟g^​\(Gx\),\\displaystyle g\(G\_\{x\}\)=\\frac\{1\}\{K\}\\sum\_\{i=1\}^\{K\}A\_\{i\}^\{\\mathrm\{ProGPO\}\}\\,\\nabla\_\{\\theta\}\\log\\pi\_\{\\theta\}\(\\tau\_\{i\}\)=\\underbrace\{\\frac\{\\lambda\}\{\\sigma\_\{P\}\(G\_\{x\}\)\+\\epsilon\}\}\_\{c\(G\_\{x\}\)\>0\}\\cdot\\;\\underbrace\{\\frac\{1\}\{K\}\\sum\_\{i=1\}^\{K\}\\bigl\(P\_\{i\}\-\\bar\{P\}\_\{G\_\{x\}\}\\bigr\)\\nabla\_\{\\theta\}\\log\\pi\_\{\\theta\}\(\\tau\_\{i\}\)\}\_\{\\widehat\{g\}\(G\_\{x\}\)\},\(21\)which is the stated identity\. The factorc​\(Gx\)c\(G\_\{x\}\)rescales but cannot reverse the update computed from a fixed group\. This proves Proposition[4\.4](https://arxiv.org/html/2607.22724#S4.Thmtheorem4)\. ∎

##### Objective estimated after conditioning\.

LetF=\{R​\(τ\)=0\}F=\\\{R\(\\tau\)=0\\\}, letπθF​\(τ\)=πθ​\(τ∣F\)\\pi\_\{\\theta\}^\{F\}\(\\tau\)=\\pi\_\{\\theta\}\(\\tau\\mid F\)be the failed\-trajectory distribution, and define

μF​\(θ\)=𝔼τ∼πθF​\[P​\(τ\)\],sθ​\(τ\)=∇θlog⁡πθ​\(τ\)\.\\displaystyle\\mu\_\{F\}\(\\theta\)=\\mathbb\{E\}\_\{\\tau\\sim\\pi\_\{\\theta\}^\{F\}\}\[P\(\\tau\)\],\\qquad s\_\{\\theta\}\(\\tau\)=\\nabla\_\{\\theta\}\\log\\pi\_\{\\theta\}\(\\tau\)\.\(22\)Conditioning an i\.i\.d\. rollout group onFK=FKF\_\{K\}=F^\{K\}preserves independence: theKKtrajectories are i\.i\.d\. fromπθF\\pi\_\{\\theta\}^\{F\}\. The score of this conditional distribution is

∇θlog⁡πθF​\(τ\)=sθ​\(τ\)−𝔼πθF​\[sθ​\(τ\)\]\.\\displaystyle\\nabla\_\{\\theta\}\\log\\pi\_\{\\theta\}^\{F\}\(\\tau\)=s\_\{\\theta\}\(\\tau\)\-\\mathbb\{E\}\_\{\\pi\_\{\\theta\}^\{F\}\}\[s\_\{\\theta\}\(\\tau\)\]\.\(23\)Therefore

∇θμF​\(θ\)=CovπθF⁡\(P​\(τ\),sθ​\(τ\)\)\.\\displaystyle\\nabla\_\{\\theta\}\\mu\_\{F\}\(\\theta\)=\\operatorname\{Cov\}\_\{\\pi\_\{\\theta\}^\{F\}\}\\\!\\left\(P\(\\tau\),s\_\{\\theta\}\(\\tau\)\\right\)\.\(24\)The fallback is consequently aligned with progress among failed trajectories, which is the regime ProGPO is designed to repair; it should not be interpreted as an unbiased estimator of the unconditional objective∇θ𝔼πθ​\[P\]\\nabla\_\{\\theta\}\\mathbb\{E\}\_\{\\pi\_\{\\theta\}\}\[P\]\.

##### Exact effect of the group\-mean baseline\.

Conditional onFKF\_\{K\}, writePi=P​\(τi\)P\_\{i\}=P\(\\tau\_\{i\}\)andsi=sθ​\(τi\)s\_\{i\}=s\_\{\\theta\}\(\\tau\_\{i\}\)\. ExpandingP¯=K−1​∑jPj\\bar\{P\}=K^\{\-1\}\\sum\_\{j\}P\_\{j\}and using conditional independence fori≠ji\\neq jgives

𝔼​\[g^​\(Gx\)∣FK\]\\displaystyle\\mathbb\{E\}\[\\widehat\{g\}\(G\_\{x\}\)\\mid F\_\{K\}\]=𝔼\[1K∑i=1K\(Pi−P¯\)si\|FK\]\\displaystyle=\\mathbb\{E\}\\\!\\left\[\\frac\{1\}\{K\}\\sum\_\{i=1\}^\{K\}\(P\_\{i\}\-\\bar\{P\}\)s\_\{i\}\\,\\middle\|\\,F\_\{K\}\\right\]\(25\)=\(1−1K\)​\(𝔼F​\[P​s\]−𝔼F​\[P\]​𝔼F​\[s\]\)\\displaystyle=\\left\(1\-\\frac\{1\}\{K\}\\right\)\\left\(\\mathbb\{E\}\_\{F\}\[Ps\]\-\\mathbb\{E\}\_\{F\}\[P\]\\,\\mathbb\{E\}\_\{F\}\[s\]\\right\)\(26\)=K−1K​∇θμF​\(θ\)\.\\displaystyle=\\frac\{K\-1\}\{K\}\\,\\nabla\_\{\\theta\}\\mu\_\{F\}\(\\theta\)\.\(27\)Thus the sample\-dependent group mean introduces an exact multiplicative factor\(K−1\)/K\(K\-1\)/K, rather than an unspecified bias term\. A leave\-one\-out baselineP¯−i=\(K−1\)−1​∑j≠iPj\\bar\{P\}\_\{\-i\}=\(K\-1\)^\{\-1\}\\sum\_\{j\\neq i\}P\_\{j\}would remove this factor, but we retain the standard group\-mean form to match the base algorithms\. WithK=8K\{=\}8, the factor is7/87/8\.

##### Effect of variance gating and normalization\.

Equation \([27](https://arxiv.org/html/2607.22724#S7.E27)\) characterizes the unnormalized estimatorg^\\widehat\{g\}\. The implemented ProGPO update additionally \(i\) discards groups withσP<τP\\sigma\_\{P\}<\\tau\_\{P\}and \(ii\) multiplies retained groups by the random positive factorc​\(Gx\)c\(G\_\{x\}\)\. These operations select and reweight groups according to within\-group progress dispersion, so the expectation of the final normalized update is not, in general, a constant multiple of Eq\. \([24](https://arxiv.org/html/2607.22724#S7.E24)\)\. The claim of Proposition[4\.4](https://arxiv.org/html/2607.22724#S4.Thmtheorem4)is deliberately groupwise: for every triggered group, normalization preserves the direction of its centered progress update\. We make no stronger global\-unbiasedness claim\.

### 7\.4Exponential Disengagement Bound

### 7\.5Why the Fallback Must Be Conditional: Reward–Progress Conflict

The conditional design in Eq\. \([7](https://arxiv.org/html/2607.22724#S4.E7)\) is motivated by a specific mismatch between reward and progress rankings that can arise in mixed\-outcome groups\. In such a groupGx=\{τi\}i=1KG\_\{x\}=\\\{\\tau\_\{i\}\\\}\_\{i=1\}^\{K\}, the reward\-based ranking is monotone inRi∈\{0,1\}R\_\{i\}\\in\\\{0,1\\\}: any successful trajectory ranks above any failed one\. The progress scorePi=\(Di−1\)/TiP\_\{i\}=\(D\_\{i\}\-1\)/T\_\{i\}, by contrast, is a length\-normalized coverage rate and is not monotone inRiR\_\{i\}—a short, efficient success can score lower than a long, wandering failure\.

##### Concrete instance\.

ConsiderGx=\{τ1,τ2\}G\_\{x\}=\\\{\\tau\_\{1\},\\tau\_\{2\}\\\}with

- •τ1\\tau\_\{1\}\(efficient success\):R1=1R\_\{1\}\{=\}1,T1=5T\_\{1\}\{=\}5,D1=3D\_\{1\}\{=\}3, henceP1=0\.4P\_\{1\}\{=\}0\.4;
- •τ2\\tau\_\{2\}\(wandering failure\):R2=0R\_\{2\}\{=\}0,T2=10T\_\{2\}\{=\}10,D2=7D\_\{2\}\{=\}7, henceP2=0\.6P\_\{2\}\{=\}0\.6\.

Reward correctly ranksτ1≻τ2\\tau\_\{1\}\\succ\\tau\_\{2\}, while progress ranksτ2≻τ1\\tau\_\{2\}\\succ\\tau\_\{1\}\. Under an always\-on additive estimatorAi=AiR\+λ​AiPA\_\{i\}=A\_\{i\}^\{R\}\+\\lambda A\_\{i\}^\{P\}, the progress term partially cancels—or, for largeλ\\lambda, overrides—the reward’s correct labeling, effectively teaching the policy that wandering failure is preferred to efficient success\.

##### Empirical consequence\.

The construction above establishes that conflict is possible; the conditional\-gating ablation in Table[2](https://arxiv.org/html/2607.22724#S5.T2)tests whether it matters in practice\. Applying progress on informative groups reduces the aggregate result for several base/benchmark combinations, whereas ProGPO reserves progress for groups in which reward supplies no ordering\. This comparison motivates the switch without assuming that coverage is a universally calibrated proxy for task value\.

##### The conditional resolution\.

By Proposition[4\.3](https://arxiv.org/html/2607.22724#S4.Thmtheorem3), ProGPO takes only the reward branch whenσR​\(Gx\)≥τR\\sigma\_\{R\}\(G\_\{x\}\)\\geq\\tau\_\{R\}, so the progress score is never applied on reward\-informative groups\. The fallback is engaged*only*where reward provides no ordering \(σR<τR\\sigma\_\{R\}\{<\}\\tau\_\{R\},R¯=0\\bar\{R\}\{=\}0\), so it cannot contradict a reward\-based ranking that would otherwise apply\.

### 7\.6A Worked All\-Fail Group: Instantiating Propositions[4\.1](https://arxiv.org/html/2607.22724#S4.Thmtheorem1)–[4\.4](https://arxiv.org/html/2607.22724#S4.Thmtheorem4)

Figure[2](https://arxiv.org/html/2607.22724#S1.F2)\(in the main text\) and the credit trap discussed in Section[1](https://arxiv.org/html/2607.22724#S1)are best understood through a concrete rollout group in which every quantity of Eq\. \([7](https://arxiv.org/html/2607.22724#S4.E7)\) can be computed by hand\. We distill a representative early\-training group on the ALFWorld goal “put a cool tomato on the countertop” down toK=4K\{=\}4trajectories of equal lengthTi=10T\_\{i\}\{=\}10\(the qualitative behaviour types below are the ones we observe recurrently in realK=8K\{=\}8groups; we useK=4K\{=\}4purely for readability\)\. All four trajectories fail,Ri=0R\_\{i\}\{=\}0, but they differ sharply in how they move through the environment:

- •τ1\\tau\_\{1\}\(goal\-directed\):go to fridge 1→\\toopen fridge 1→\\totake tomato 1→\\tocool tomato 1 with fridge 1→\\tonavigates toward the countertop until the step budget expires\. 8 of 10 steps produce a*previously unseen*observation\.
- •τ2\\tau\_\{2\}\(partial explorer\): reaches and opens the fridge, then wanders; 5 novel observations, plus one revisit of an earlier room\.
- •τ3\\tau\_\{3\}\(cycler\): shuttles back and forth between two rooms\. The observation changes at 9 of 10 steps, but only 2 of those observations are novel—the rest revisit states already in𝒱3,t\\mathcal\{V\}\_\{3,t\}\.
- •τ4\\tau\_\{4\}\(no\-op\): repeatslook/inventory; the observation changes once in 10 steps\.

Table[3](https://arxiv.org/html/2607.22724#S7.T3)reports, for each trajectory, the number of observation\-*changing*steps, the number of*novelty\-gated*steps counted by Eq\. \([5](https://arxiv.org/html/2607.22724#S4.E5)\), the resulting progress scorePiP\_\{i\}\(Eq\. \([6](https://arxiv.org/html/2607.22724#S4.E6)\)\), and the advantages assigned by ProGPO versus the ungated Obs\-Change variant from the ablation in Section[5](https://arxiv.org/html/2607.22724#S5)\.

Table 3:A workedK=4K\{=\}4all\-fail group \(Ti=10T\_\{i\}\{=\}10,Ri=0R\_\{i\}\{=\}0for allii;τR=τP=0\.01\\tau\_\{R\}\{=\}\\tau\_\{P\}\{=\}0\.01,λ=1\\lambda\{=\}1,ϵ\\epsilonomitted\)\. ProGPO’s novelty gate separates genuine coverage \(τ1,τ2\\tau\_\{1\},\\tau\_\{2\}\) from cycling \(τ3\\tau\_\{3\}\) and no\-ops \(τ4\\tau\_\{4\}\); the ungated Obs\-Change score is fooled by the cycler and ranksτ3\\tau\_\{3\}*first*\.Traj\.BehaviourObs\.\-changing stepsNovel stepsPiP\_\{i\}AiProGPOA\_\{i\}^\{\\mathrm\{ProGPO\}\}AiObs\-ChangeA\_\{i\}^\{\\text\{Obs\-Change\}\}τ1\\tau\_\{1\}goal\-directed880\.8\+1\.46\+1\.46\+0\.65\+0\.65τ2\\tau\_\{2\}partial explorer650\.5\+0\.37\+0\.370\.000\.00τ3\\tau\_\{3\}cycler920\.2−0\.73\-0\.73\+0\.97\\mathbf\{\+0\.97\}τ4\\tau\_\{4\}no\-op110\.1−1\.10\-1\.10−1\.62\-1\.62##### Branch selection and fallback advantages\.

SinceR=\(0,0,0,0\)R=\(0,0,0,0\), we haveσR​\(Gx\)=0<τR\\sigma\_\{R\}\(G\_\{x\}\)=0<\\tau\_\{R\}andR¯Gx=0\\bar\{R\}\_\{G\_\{x\}\}=0\. The progress scoresP=\(0\.8,0\.5,0\.2,0\.1\)P=\(0\.8,0\.5,0\.2,0\.1\)giveP¯Gx=0\.4\\bar\{P\}\_\{G\_\{x\}\}=0\.4andσP​\(Gx\)≈0\.274≥τP\\sigma\_\{P\}\(G\_\{x\}\)\\approx 0\.274\\geq\\tau\_\{P\}, so the group enters the second branch of Eq\. \([7](https://arxiv.org/html/2607.22724#S4.E7)\) rather than being discarded\. The fallback advantages areAiProGPO=\(Pi−0\.4\)/0\.274A\_\{i\}^\{\\mathrm\{ProGPO\}\}=\(P\_\{i\}\-0\.4\)/0\.274, i\.e\.,\(\+1\.46,\+0\.37,−0\.73,−1\.10\)\(\+1\.46,\\,\+0\.37,\\,\-0\.73,\\,\-1\.10\)\. A group that contributes an identically zero reward\-based gradient now increases the relative likelihood of actions sampled in the higher\-coverage trajectories and decreases it for the cycling and no\-op trajectories\. By Proposition[4\.4](https://arxiv.org/html/2607.22724#S4.Thmtheorem4), the group update is a REINFORCE\-style step on returnPPwith a group\-mean baseline, scaled byλ/σP≈3\.65\\lambda/\\sigma\_\{P\}\\approx 3\.65\.

##### Instantiating Proposition[4\.1](https://arxiv.org/html/2607.22724#S4.Thmtheorem1)\.

Completing this task requires visiting at leastmx=5m\_\{x\}\{=\}5distinct observations \(at the fridge; fridge open; holding the tomato; tomato cooled; at the countertop\), so every successful length\-1010trajectory must satisfyP≥\(mx−1\)/T=0\.4P\\geq\(m\_\{x\}\-1\)/T=0\.4\. The sign structure produced by ProGPO is consistent with this necessary condition: the two above\-mean trajectories \(τ1\\tau\_\{1\}:0\.80\.8,τ2\\tau\_\{2\}:0\.50\.5\) lie inside the relaxation containing all successful behaviours, whereasτ3\\tau\_\{3\}andτ4\\tau\_\{4\}fall below the necessary coverage threshold\. The converse does not hold: membership in the super\-level set does not certify task completion\.

##### Why the novelty gate matters\.

The ungated Obs\-Change score credits any observation change, so it assignsτ3\\tau\_\{3\}the*highest*rate \(0\.90\.9\) and, after group normalization, ranks the cycler above the goal\-directed trajectory \(\+0\.97\+0\.97vs\.\+0\.65\+0\.65\)\. This single group reproduces, in closed form, the hackability gap observed in the ablation of Section[5](https://arxiv.org/html/2607.22724#S5)\(Obs\-Change88\.9%88\.9\\%vs\. ProGPO91\.4%91\.4\\%\): rewarding movement without novelty teaches the policy that shuttling between two rooms is progress\. The novelty gate of Eq\. \([5](https://arxiv.org/html/2607.22724#S4.E5)\) removes exactly these revisits \(9→29\\to 2credited steps forτ3\\tau\_\{3\}\) while leaving the goal\-directed trajectory untouched \(8→88\\to 8\)\.

##### Hand\-off and disengagement\.

Suppose that at a later epoch the same task yieldsR=\(1,0,0,0\)R=\(1,0,0,0\)\. ThenR¯Gx=0\.25\\bar\{R\}\_\{G\_\{x\}\}=0\.25andσR​\(Gx\)≈0\.433≥τR\\sigma\_\{R\}\(G\_\{x\}\)\\approx 0\.433\\geq\\tau\_\{R\}, so the group takes the first branch andAProGPO=\(\+1\.73,−0\.58,−0\.58,−0\.58\)A^\{\\mathrm\{ProGPO\}\}=\(\+1\.73,\\,\-0\.58,\\,\-0\.58,\\,\-0\.58\)—identical to the base estimator, with the progress scores ignored entirely regardless of their values \(Proposition[4\.3](https://arxiv.org/html/2607.22724#S4.Thmtheorem3)\)\. The fallback can only recur while*all*KKtrajectories fail: by the disengagement bound \(Remark[7\.1](https://arxiv.org/html/2607.22724#S7.Thmtheorem1)\) its trigger probability is at most\(1−pθ​\(x\)\)K\(1\-p\_\{\\theta\}\(x\)\)^\{K\}, which atK=8K\{=\}8falls from0\.660\.66atpθ=0\.05p\_\{\\theta\}\{=\}0\.05to0\.100\.10atpθ=0\.25p\_\{\\theta\}\{=\}0\.25and0\.0040\.004atpθ=0\.5p\_\{\\theta\}\{=\}0\.5\. This group\-level mechanism explains why the measured trigger rate can fall from29\.4%29\.4\\%to4\.7%4\.7\\%\(Appendix[10\.7\.2](https://arxiv.org/html/2607.22724#S10.SS7.SSS2)\); the deployed code additionally scales the common fallback magnitude by the current all\-fail fraction, as specified below\. Branch disengagement and magnitude scaling are distinct and are logged separately\.

## 8Implementation Details

In this section, we describe the computing resources, training hyperparameters, and environment configurations used in all experiments, so that every reported result can be reproduced under an identical setup\.

### 8\.1Computing Details

ProGPO is implemented as a drop\-in replacement of the advantage computation in the group\-based RL trainer; no change is made to rollout collection, the optimizer, or the model\. For each rollout group, computing the trajectory progress scores\{Pi\}\\\{P\_\{i\}\\\}requires maintaining a per\-trajectory hash set of visited observation strings and performingO​\(1\)O\(1\)set\-membership checks per step, executed on CPU during advantage estimation\.

Each baseline–ProGPO pair is trained on44GPUs for the 1\.5B configuration and88GPUs for the 7B configuration, with the same configuration within each matched pair\. In our setup the progress\-and\-switch overhead adds less than0\.5%0\.5\\%to per\-epoch wall\-clock time, which is within run\-to\-run noise; rollout generation and policy updates dominate the budget\. The stage\-level timing audit in Figure[4](https://arxiv.org/html/2607.22724#S5.F4)was run separately on four GPUs and is therefore used to measure overhead, not to redefine the training hardware above\. ProGPO adds no learned parameters or persistent model\-state memory \(no critic, reward model, progress estimator, or world model\); its visited sets reside in host memory and its advantage tensor has the same shape as that of the base trainer\.

### 8\.2Reference Advantage Computation

Algorithm[1](https://arxiv.org/html/2607.22724#alg1)gives the complete group\-level computation used by ProGPO\. Observations are compared as the exact strings emitted by the environment: no lower\-casing, whitespace normalization, tokenization, semantic encoder, or environment\-specific equivalence rule is applied\. The initial observation is inserted into the visited set before the first action\. A terminal observation returned by the final environment step is processed exactly like every other next observation\. Trajectory lengthTiT\_\{i\}is the number of executed environment actions, including the terminating action when termination occurs before the maximum horizon\.

Algorithm 1Equation\-level computation of ProGPO advantages for one rollout group1:Trajectories

Gx=\{τi\}i=1KG\_\{x\}=\\\{\\tau\_\{i\}\\\}\_\{i=1\}^\{K\}; terminal rewards

\{Ri\}i=1K\\\{R\_\{i\}\\\}\_\{i=1\}^\{K\}; thresholds

τR,τP\\tau\_\{R\},\\tau\_\{P\}; scale

λ\\lambda; stability constant

ϵ\\epsilon
2:for

i=1,…,Ki=1,\\ldots,Kdo

3:

𝒱i←\{oi,1\}\\mathcal\{V\}\_\{i\}\\leftarrow\\\{o\_\{i,1\}\\\};

Ci←0C\_\{i\}\\leftarrow 0
4:for

t=1,…,Tit=1,\\ldots,T\_\{i\}do

5:if

oi,t\+1∉𝒱io\_\{i,t\+1\}\\notin\\mathcal\{V\}\_\{i\}then

6:

Ci←Ci\+1C\_\{i\}\\leftarrow C\_\{i\}\+1
7:

𝒱i←𝒱i∪\{oi,t\+1\}\\mathcal\{V\}\_\{i\}\\leftarrow\\mathcal\{V\}\_\{i\}\\cup\\\{o\_\{i,t\+1\}\\\}
8:

Pi←Ci/TiP\_\{i\}\\leftarrow C\_\{i\}/T\_\{i\}
9:Compute

R¯,σR,P¯,σP\\bar\{R\},\\sigma\_\{R\},\\bar\{P\},\\sigma\_\{P\}using Eq\. \([14](https://arxiv.org/html/2607.22724#S7.E14)\)

10:if

σR≥τR\\sigma\_\{R\}\\geq\\tau\_\{R\}then

11:for

i=1,…,Ki=1,\\ldots,Kdo

12:

Ai←\(Ri−R¯\)/\(σR\+ϵ\)A\_\{i\}\\leftarrow\(R\_\{i\}\-\\bar\{R\}\)/\(\\sigma\_\{R\}\+\\epsilon\)
13:elseif

R¯=0\\bar\{R\}=0and

σP≥τP\\sigma\_\{P\}\\geq\\tau\_\{P\}then

14:for

i=1,…,Ki=1,\\ldots,Kdo

15:

Ai←λ​\(Pi−P¯\)/\(σP\+ϵ\)A\_\{i\}\\leftarrow\\lambda\(P\_\{i\}\-\\bar\{P\}\)/\(\\sigma\_\{P\}\+\\epsilon\)
16:else

17:for

i=1,…,Ki=1,\\ldots,Kdo

18:

Ai←0A\_\{i\}\\leftarrow 0
19:return

\{Ai\}i=1K\\\{A\_\{i\}\\\}\_\{i=1\}^\{K\}and branch identifier

### 8\.3Deployed Per\-Update Scaling and Conformance Boundary

Algorithm[1](https://arxiv.org/html/2607.22724#alg1)is the equation\-level estimator analyzed in Section[7](https://arxiv.org/html/2607.22724#S7)\. The supplied training code instantiates its positive scale once per policy update\. Letℬ\\mathcal\{B\}be the comparison groups produced by the selected base method, and define

qfail​\(ℬ\)\\displaystyle q\_\{\\mathrm\{fail\}\}\(\\mathcal\{B\}\)=1\|ℬ\|​∑G∈ℬ𝟏​\[maxi∈G⁡\|yi\|<τRimpl\],\\displaystyle=\\frac\{1\}\{\|\\mathcal\{B\}\|\}\\sum\_\{G\\in\\mathcal\{B\}\}\\mathbf\{1\}\\\!\\left\[\\max\_\{i\\in G\}\|y\_\{i\}\|<\\tau\_\{R\}^\{\\mathrm\{impl\}\}\\right\],λeff\\displaystyle\\lambda\_\{\\mathrm\{eff\}\}=λaux​qfail​\(ℬ\),\\displaystyle=\\lambda\_\{\\mathrm\{aux\}\}q\_\{\\mathrm\{fail\}\}\(\\mathcal\{B\}\),\(30\)whereyiy\_\{i\}is the reward or return supplied by the base estimator\. The released runs setlambda\_fixed=false; consequently,λeff\\lambda\_\{\\mathrm\{eff\}\}changes with the current update even though its configured ceilingλaux\\lambda\_\{\\mathrm\{aux\}\}is fixed\. Becauseλeff≥0\\lambda\_\{\\mathrm\{eff\}\}\\geq 0is common to every triggered group within an update, it changes magnitude but not the groupwise direction established by Proposition[4\.4](https://arxiv.org/html/2607.22724#S4.Thmtheorem4)\. Ifqfail=0q\_\{\\mathrm\{fail\}\}=0, no group is eligible and the fallback is exactly inactive\.

Algorithm 2Deployed ProGPO wrapper for one policy update\. The base method determines the group keys: prompt groups for GRPO, anchor\-state groups for GiGPO, and history groups for HGPO\.1:Groups

ℬ\\mathcal\{B\}, base scores

\{yi\}\\\{y\_\{i\}\\\}, progress

\{pi\}\\\{p\_\{i\}\\\},

τRimpl\\tau\_\{R\}^\{\\mathrm\{impl\}\},

τPimpl\\tau\_\{P\}^\{\\mathrm\{impl\}\},

λaux\\lambda\_\{\\mathrm\{aux\}\},

ϵ\\epsilon
2:

nfail←0n\_\{\\mathrm\{fail\}\}\\leftarrow 0
3:foreach

G∈ℬG\\in\\mathcal\{B\}do

4:

fG←𝟏​\[maxi∈G⁡\|yi\|<τRimpl\]f\_\{G\}\\leftarrow\\mathbf\{1\}\\\!\\left\[\\max\_\{i\\in G\}\|y\_\{i\}\|<\\tau\_\{R\}^\{\\mathrm\{impl\}\}\\right\]
5:

nfail←nfail\+fGn\_\{\\mathrm\{fail\}\}\\leftarrow n\_\{\\mathrm\{fail\}\}\+f\_\{G\}
6:

qfail←nfail/max⁡\(\|ℬ\|,1\)q\_\{\\mathrm\{fail\}\}\\leftarrow n\_\{\\mathrm\{fail\}\}/\\max\(\|\\mathcal\{B\}\|,1\)
7:

λeff←λaux​qfail\\lambda\_\{\\mathrm\{eff\}\}\\leftarrow\\lambda\_\{\\mathrm\{aux\}\}q\_\{\\mathrm\{fail\}\}
8:foreach

G∈ℬG\\in\\mathcal\{B\}do

9:Compute unchanged base advantages

AibaseA\_\{i\}^\{\\mathrm\{base\}\}for

i∈Gi\\in G
10:if

fG=1f\_\{G\}=1then

11:

p¯G←\|G\|−1​∑i∈Gpi\\bar\{p\}\_\{G\}\\leftarrow\|G\|^\{\-1\}\\sum\_\{i\\in G\}p\_\{i\}
12:

sp,G←Stdpop⁡\(\{pi:i∈G\}\)s\_\{p,G\}\\leftarrow\\operatorname\{Std\}\_\{\\mathrm\{pop\}\}\(\\\{p\_\{i\}:i\\in G\\\}\)
13:if

sp,G≥τPimpls\_\{p,G\}\\geq\\tau\_\{P\}^\{\\mathrm\{impl\}\}then

14:foreach

i∈Gi\\in Gdo

15:

Ai←λeff​\(pi−p¯G\)/\(sp,G\+ϵ\)A\_\{i\}\\leftarrow\\lambda\_\{\\mathrm\{eff\}\}\(p\_\{i\}\-\\bar\{p\}\_\{G\}\)/\(s\_\{p,G\}\+\\epsilon\)
16:else

17:foreach

i∈Gi\\in Gdo

18:

Ai←0A\_\{i\}\\leftarrow 0
19:else

20:foreach

i∈Gi\\in Gdo

21:

Ai←AibaseA\_\{i\}\\leftarrow A\_\{i\}^\{\\mathrm\{base\}\}
22:return

\{Ai\}\\\{A\_\{i\}\\\}and diagnostics

\(qfail,λeff,nfail,ntrigger\)\(q\_\{\\mathrm\{fail\}\},\\lambda\_\{\\mathrm\{eff\}\},n\_\{\\mathrm\{fail\}\},n\_\{\\mathrm\{trigger\}\}\)

##### Audit note\.

The body states the idealized gate usingσR<τR\\sigma\_\{R\}<\\tau\_\{R\}andR¯=0\\bar\{R\}=0\. For exactly binary non\-negative outcomes and a sufficiently small threshold, this is equivalent to the implemented all\-zero test\. For step\-level base scores or fractional WebShop returns, equivalence must be checked from the run definition rather than assumed; we therefore state the implementation test explicitly in Algorithm[2](https://arxiv.org/html/2607.22724#alg2)\.

##### Numerical and boundary cases\.

Population standard deviations \(division byKK\) are used consistently for rewards and progress\. The strict/weak inequalities in Algorithm[1](https://arxiv.org/html/2607.22724#alg1)match Eq\. \([7](https://arxiv.org/html/2607.22724#S4.E7)\): equality at a threshold enters the informative branch\. TheσP\\sigma\_\{P\}test is evaluated before division, so a progress\-degenerate group returns zero rather than a numerically amplified vector\. SinceτR\\tau\_\{R\}lies below the smallest non\-zero binary\-reward deviation in Eq\. \([19](https://arxiv.org/html/2607.22724#S7.E19)\), floating\-point tolerance does not change the semantic distinction between mixed\-outcome and uniform\-outcome groups in our configuration\.

##### Complexity\.

LetNG=∑iTiN\_\{G\}=\\sum\_\{i\}T\_\{i\}be the number of transitions in a group\. With hash\-set membership, progress computation requiresO​\(NG\)O\(N\_\{G\}\)expected time andO​\(∑iD​\(τi\)\)O\(\\sum\_\{i\}D\(\\tau\_\{i\}\)\)host memory\. The remaining group statistics requireO​\(K\)O\(K\)time\. ProGPO does not add a model forward pass or backpropagation graph; only the resulting scalar advantages are consumed by the unchanged policy objective\.

### 8\.4Training Hyperparameters

Within every base–ProGPO pair, rollout, optimization, and evaluation hyperparameters are held fixed so that the controlled difference is the advantage estimator\. Table[4](https://arxiv.org/html/2607.22724#S8.T4)reports values directly visible in the supplied launch scripts and run configuration, distinguishing configured constants from per\-update effective quantities\.

Table 4:Training hyperparameters recorded by the supplied launch scripts and run configuration\.λaux\\lambda\_\{\\mathrm\{aux\}\}is fixed;λeff\\lambda\_\{\\mathrm\{eff\}\}is computed per update by Eq\. \([30](https://arxiv.org/html/2607.22724#S8.E30)\)\.ComponentValueBase modelQwen2\.5\-1\.5B\-Instruct / Qwen2\.5\-7B\-InstructOptimizerAdamW \(β1=0\.9\\beta\_\{1\}\{=\}0\.9,β2=0\.95\\beta\_\{2\}\{=\}0\.95\)Learning rate \(actor\)1×10−61\\times 10^\{\-6\}Actor KL\-loss coefficient1×10−21\\times 10^\{\-2\}Clipping rangeϵc\\epsilon\_\{c\}0\.20\.2Rollout group sizeKK88Max interaction stepsTmaxT\_\{\\max\}50 \(ALFWorld\) / 15 \(WebShop\)Training epochs150150Batch size \(tasks per iter\.\)1616Reference policyπref\\pi\_\{\\mathrm\{ref\}\}frozen base modelDecoding temperaturerollout1\.01\.0; validation0\.40\.4*ProGPO\-specific implementation settings*Progress signalC2: novelty\-gated binary \(Eq\. \([5](https://arxiv.org/html/2607.22724#S4.E5)\)\)All\-zero thresholdτRimpl\\tau\_\{R\}^\{\\mathrm\{impl\}\}1×10−31\\times 10^\{\-3\}Progress cutoffτPimpl\\tau\_\{P\}^\{\\mathrm\{impl\}\}1×10−41\\times 10^\{\-4\}Configured scaleλaux\\lambda\_\{\\mathrm\{aux\}\}0\.30\.3Effective scaleλeff\\lambda\_\{\\mathrm\{eff\}\}0\.3​qfail​\(ℬ\)0\.3\\,q\_\{\\mathrm\{fail\}\}\(\\mathcal\{B\}\)Fixed\-scale flagfalseNumerical stabilityϵ\\epsilon1×10−61\\times 10^\{\-6\}Progress standard deviationpopulation \(division by group size\)
### 8\.5ALFWorld

We use the textual ALFWorld environment with the standard six\-category split \(Pick, Look, Clean, Heat, Cool, Pick2\)\. Training tasks are drawn from the official train split; we evaluate on the held\-out unseen test split\. Each rollout terminates either upon task completion \(binary reward11\), upon explicit failure, or upon reaching the step budgetTmax=50T\_\{\\max\}\{=\}50\(reward0\)\. At each step, the prompt to the policy contains the task instruction, the running observation–action history, and the admissible\-action list provided by the simulator\.

### 8\.6WebShop

We use the WebShop simulator with goal\-instruction tasks, terminating upon purchase, explicit abandonment, or step budgetTmax=15T\_\{\\max\}\{=\}15\. The terminal reward is the simulator\-provided product\-match score in\[0,1\]\[0,1\]for the score column; for the success\-rate column we threshold at1\.01\.0as in prior work\. The textual action space consists ofsearch\[⋅\\cdot\],click\[⋅\\cdot\], and a small set of navigation primitives; observations are the rendered HTML page summaries returned by the simulator\.

### 8\.7Progress Measure across Environments

Equation \([5](https://arxiv.org/html/2607.22724#S4.E5)\) is computed identically in both environments: we maintain a per\-trajectory hash set of visited observation strings and check whether each new observation is novel, with no environment\-specific tokenization or filtering\. This single observation\-level definition transfers between ALFWorld \(game\-state text\) and WebShop \(page\-summary text\) without modification\.

### 8\.8Evaluation and Reporting Protocol

Training\-time ablations explicitly marked with a seed use matched rollout randomness to isolate the changed component\. Final\-checkpoint results in Table[1](https://arxiv.org/html/2607.22724#S5.T1)are re\-evaluated with three independent inference seeds and reported as mean±\\pmstandard deviation whenever repeated evaluations are available\. ALFWorld reports binary episode success overall and by the official six task categories\. WebShop reports both the simulator’s terminal product\-match score and exact success, defined by a terminal score of1\.01\.0\. No progress score is used at inference time: ProGPO changes training advantages only, so evaluation uses the same decoding and environment interaction interface as the corresponding base method\.

## 9Sampling\-Imbalance Audit and Sampler\-Side Intervention

In this section, we detail the offline analysis protocol behind the sampling\-imbalance observation in Section[1](https://arxiv.org/html/2607.22724#S1)\(Figure[1](https://arxiv.org/html/2607.22724#S1.F1)\(b\)\), and report a controlled comparison between sampler\-side and advantage\-side interventions\.

### 9\.1Base\-Policy Action Audit

To characterize how the base policy distributes probability mass over its action support, we collect an offline analysis set from Qwen2\.5\-1\.5B\-Instruct acting on ALFWorld: 27 games and 463 decision records in total\. At each decision point, we enumerate the admissible actions, record their policy probabilities, and partition them into three probability bands \(head / mid / low\) by rank\. Each action is then labelled as*useful*or*useless*according to whether executing it changes the environment observation at that decision point: actions such asexamine,look, andinventorythat leave the observation unchanged are labelled useless, whereas navigation and object\-manipulation actions that induce observable transitions are labelled useful\.

Table 5:Base\-policy audit on ALFWorld \(27 games, 463 decision records\)\. No\-change actions saturate the high\-probability head, while the majority of state\-changing actions are relegated to the mid/low bands\.StatisticValueTop\-1 action is useless38\.9%Useless actions located in head band100%Useful actions located in mid/low bands83\.2%Typical useless actionsexamine,look,inventoryTable[5](https://arxiv.org/html/2607.22724#S9.T5)quantifies the sampling imbalance discussed in Section[1](https://arxiv.org/html/2607.22724#S1): no\-change actions fully occupy the high\-probability head, while the large majority of state\-changing actions are relegated to the mid\- and low\-probability region\. Notably, at most audited decision points where the top\-1 action is useless, actionable alternatives exist within the admissible action set—the policy fails not because useful actions are unavailable, but because they are under\-sampled\.

### 9\.2Sampler\-Side Intervention: Band\-Conditioned Sampling

A direct response to action\-probability miscalibration is to intervene at sampling time\. We implemented a band\-conditioned candidate strategy that suppresses head\-band no\-op actions and redistributes rollout probability toward mid\- and low\-band candidates, thereby injecting more state\-changing actions into rollout groups\. We compare four configurations under identical training budgets \(Qwen2\.5\-1\.5B\-Instruct, ALFWorld, group sizeK=8K\{=\}8, 30 epochs, seed 42\): the unmodified baseline, band\-conditioned sampling alone, conditional advantage repair alone, and their combination\.

Table 6:Sampler\-side vs\. advantage\-side intervention \(validation SR, %, 30 epochs, seed 42\)\. “Band” denotes band\-conditioned sampling; “Repair” denotes conditional advantage repair on all\-fail groups\. Advantage repair accounts for nearly the entire improvement; adding band\-conditioned sampling on top contributes<1<\\\!1pp at peak\.ConfigurationEp 25 SREp 30 SRPeak SRΔ\\Deltavs\. baseBaseline19\.515\.619\.5—Band only19\.525\.825\.8\+6\.3Repair only32\.028\.132\.0\+12\.5Band \+ Repair32\.828\.932\.8\+13\.3Two observations follow from Table[6](https://arxiv.org/html/2607.22724#S9.T6)\. First, advantage repair alone accounts for nearly the entire improvement: adding band\-conditioned sampling on top of repair contributes less than11percentage point at peak\. Second, band\-conditioned sampling alone barely reduces the all\-fail group rate during training, despite successfully placing more state\-changing actions into rollouts\. This is consistent with the credit trap analysis in Section[1](https://arxiv.org/html/2607.22724#S1): when groups fail uniformly at the terminal level, the zero group\-relative advantage prevents briefly sampled useful actions from being reinforced, so sampler\-side intervention cannot break the loop on its own\. The binding constraint lies on the credit\-assignment side, which is precisely where ProGPO intervenes\.

### 9\.3Action\-Level Audit: Metric Definitions and Rationale

This section defines the two scalar measures used in Section[5\.3](https://arxiv.org/html/2607.22724#S5.SS3)—*progress alignment*and*no\-op suppression*—and explains why they are valid diagnostics of the injected signal\. Both are computed on an offline analysis set ofN=3,236N\{=\}3\{,\}236admissible\-action decision records \(6060ALFWorld games,2525checkpoints spanning epochs2020–150150\), enumerating all admissible actions at each record under identical prompts\.

The base quantity\.For an admissible actionaaat historyhhwe record its policy shift relative to the reference policyπref\\pi\_\{\\mathrm\{ref\}\}\(the initial checkpoint\),

Δ​log⁡π​\(a∣h\)=log⁡πθ​\(a∣h\)−log⁡πref​\(a∣h\)\.\\Delta\\log\\pi\(a\\mid h\)=\\log\\pi\_\{\\theta\}\(a\\mid h\)\-\\log\\pi\_\{\\mathrm\{ref\}\}\(a\\mid h\)\.\(31\)Δ​log⁡π\\Delta\\log\\piis the net cumulative effect of all gradient updates on that action’s log\-probability\. Proposition[4\.3](https://arxiv.org/html/2607.22724#S4.Thmtheorem3)ensures that ProGPO changes the update rule only on reward\-degenerate groups\. A matched comparison against the base algorithm therefore measures the total downstream policy shift induced by adding fallback updates; because the policies subsequently visit different data, it should not be interpreted as isolating every later reward\-driven update at the individual\-sample level\.

Progress alignment\.We tag each action by its transition progressδ​\(a∣h\)∈\{0,1\}\\delta\(a\\mid h\)\\in\\\{0,1\\\}, the per\-step novelty indicator of Eq\. \([5](https://arxiv.org/html/2607.22724#S4.E5)\), and define

Align​\(θ\)=Corr​\(Δ​log⁡π​\(a∣h\),δ​\(a∣h\)\),\\mathrm\{Align\}\(\\theta\)=\\mathrm\{Corr\}\\\!\\bigl\(\\Delta\\log\\pi\(a\\mid h\),\\,\\delta\(a\\mid h\)\\bigr\),\(32\)the Pearson correlation pooled over allNNrecords\. If the restored gradient reinforces progress\-making actions, novel\-transition actions \(δ=1\\delta\{=\}1\) receive higherΔ​log⁡π\\Delta\\log\\pithan the rest, giving a positive correlation; a noisy or anti\-aligned update gives≈0\\approx 0or negative\. We use a correlation rather than a raw mean difference because it is unit\-free, sign\-carrying, and bounded in\[−1,1\]\[\-1,1\]: policies differ in overall update magnitude \(learning rate, entropy\), which a mean difference would conflate with alignment but which a correlation normalizes away, making the measure directly comparable across methods\. Sinceδ\\deltais binary, Eq\. \([32](https://arxiv.org/html/2607.22724#S9.E32)\) is exactly the*point\-biserial*correlation, i\.e\. the standardized difference in meanΔ​log⁡π\\Delta\\log\\pibetween novel and non\-novel actions;Align\\mathrm\{Align\}thus reads directly as “how much more training raised the log\-probability of novel\-transition actions than of the rest, in standard\-deviation units\.”

No\-op suppression\.The credit trap diagnosed in Section[1](https://arxiv.org/html/2607.22724#S1)is sustained by an over\-sampled no\-op head; breaking it requires demoting those actions\. We measure this directly on the fixed no\-op set𝒜noop=\{examine,look,inventory\}\\mathcal\{A\}\_\{\\mathrm\{noop\}\}\{=\}\\\{\\texttt\{examine\},\\texttt\{look\},\\texttt\{inventory\}\\\}identified independently by the base\-policy audit \(Appendix[9\.1](https://arxiv.org/html/2607.22724#S9.SS1)\),

Supprnoop​\(θ\)=−𝔼a∈𝒜noop​\[Δ​log⁡π​\(a∣h\)\]​\(nats\)\.\\mathrm\{Suppr\}\_\{\\mathrm\{noop\}\}\(\\theta\)=\-\\,\\mathbb\{E\}\_\{a\\in\\mathcal\{A\}\_\{\\mathrm\{noop\}\}\}\\\!\\bigl\[\\Delta\\log\\pi\(a\\mid h\)\\bigr\]\\ \\text\{\(nats\)\}\.\(33\)The unit is nats becauseΔ​log⁡π\\Delta\\log\\piis a natural\-log probability difference; it converts directly to a multiplicative factor, e\.g\.Supprnoop=1\.38\\mathrm\{Suppr\}\_\{\\mathrm\{noop\}\}\{=\}1\.38means no\-ops are pushed toe−1\.38≈0\.25e^\{\-1\.38\}\{\\approx\}0\.25of their reference mass \(∼4×\\sim\\\!4\\timesless likely\)\. Fixing𝒜noop\\mathcal\{A\}\_\{\\mathrm\{noop\}\}in advance from the independent audit avoids any post\-hoc selection\.

Why the pair is sound\.Align\\mathrm\{Align\}measures the*direction*of the injected gradient—whether it points toward progress—whileSupprnoop\\mathrm\{Suppr\}\_\{\\mathrm\{noop\}\}measures whether it acts on the*specific mechanism*, the no\-op head, blamed for the collapse; together they test whether ProGPO does what the theory predicts\. Both are observational quantities on an offline analysis, so causal attribution rests on the correspondence\-breaking negative controls: Shuffle and Random share ProGPO’s trigger and keep the fallback equally active, yet only break the trajectory–score binding\. Their alignment collapses \(0\.020\.02and0\.140\.14vs\. ProGPO’s0\.170\.17\) and Shuffle’s no\-op suppression vanishes \(0\.000\.00vs\.1\.381\.38\), showing that these measures are not trivially inflated by any active fallback but genuinely track the bound progress signal\.

## 10Additional Results

In this section, we report additional experimental results that complement the main text: per\-category breakdowns across training epochs, robustness to training and inference seeds, hyperparameter sensitivity, and the full training\-dynamics statistics summarized in Sections[5](https://arxiv.org/html/2607.22724#S5.F5)and[5\.3](https://arxiv.org/html/2607.22724#S5.SS3)\.

### 10\.1Per\-Category Breakdown across Training Epochs

Table[1](https://arxiv.org/html/2607.22724#S5.T1)reports the final\-checkpoint performance after150150training epochs\. To complement this view, we report the success\-rate trajectory of GiGPO and GiGPO\+ProGPO per ALFWorld category at three checkpoints \(epochs30/60/15030/60/150\) under matched training conditions \(Qwen2\.5\-1\.5B\-Instruct, seed 42\), in Table[7](https://arxiv.org/html/2607.22724#S10.T7)\. Two patterns are robust across categories\. First, ProGPO’s advantage emerges earliest on the hardest categories \(Look, Cool, Pick2\), consistent with the higher all\-fail incidence on these subsets\. Second, on the easiest category \(Pick\), the two methods evolve in lockstep, confirming that ProGPO’s conditional design leaves non\-degenerate groups untouched\.

Table 7:Validation success rate \(%\) per ALFWorld category at training epochs 30, 60, and 150 \(Qwen2\.5\-1\.5B\-Instruct, matched training seed\)\. Final\-checkpoint numbers correspond to Table[1](https://arxiv.org/html/2607.22724#S5.T1)\. ProGPO’s gains concentrate on hard categories \(Look, Cool, Pick2\) where all\-fail groups dominate; on the easiest category \(Pick\) the two methods are nearly identical\.EpochMethodPickLookCleanHeatCoolPick2Overall30GiGPO41\.711\.112\.913\.04\.80\.015\.6GiGPO\+ProGPO50\.027\.838\.739\.128\.611\.832\.060GiGPO75\.038\.925\.830\.414\.317\.632\.8GiGPO\+ProGPO79\.250\.051\.656\.542\.923\.549\.2150GiGPO94\.467\.594\.894\.479\.876\.486\.7GiGPO\+ProGPO88\.283\.3100\.094\.492\.090\.991\.4
### 10\.2Per\-Category Breakdown of Signal\-Analysis Variants

Figure[6](https://arxiv.org/html/2607.22724#S5.F6)in the main text summarizes the signal\-analysis controls\. Table[8](https://arxiv.org/html/2607.22724#S10.T8)provides the corresponding per\-category breakdown on ALFWorld for configurations with complete category\-level measurements\. Three patterns stand out\. First,Negcollapses hardest exactly on the long\-horizon categories \(Cool and Pick2 both at0%0\\%\): rewarding stagnation is most destructive where sustained novel\-state coverage is required\. Second,Shuffle’s damage also concentrates on the hard categories \(Pick252\.6%52\.6\\%, Cool65\.0%65\.0\\%\), where misattributed progress scores mislead credit assignment the most, while the easy Pick category is barely affected \(91\.4%91\.4\\%\)\. Third,Obs\-Changetracks ProGPO closely on manipulation\-centric categories \(Clean, Heat\) but loses on the navigation\-heavy ones \(Pick281\.3%81\.3\\%vs\.92\.8%92\.8\\%\), consistent with cycling being the dominant hack it admits\.

Table 8:Per\-category success rate \(%\) of signal\-analysis variants on ALFWorld \(Qwen2\.5\-1\.5B\-Instruct, GiGPO base, 150 epochs\)\. Entries with a standard deviation are averaged over five seeds;†marks single\-seed diagnostic runs\.VariantPickLookCleanHeatCoolPick2AllGiGPO \(base\)94\.4±\\pm5\.967\.5±\\pm4\.694\.8±\\pm3\.894\.4±\\pm7\.879\.8±\\pm4\.776\.4±\\pm5\.486\.7±\\pm1\.7\+ Random†93\.364\.379\.393\.884\.280\.083\.6\+ Shuffle†91\.454\.593\.881\.865\.052\.678\.1\+ Neg†46\.742\.123\.111\.10\.00\.022\.7\+ Obs\-Change90\.8±\\pm4\.777\.2±\\pm9\.794\.0±\\pm6\.294\.9±\\pm4\.387\.2±\\pm5\.281\.3±\\pm7\.988\.9±\\pm1\.6ProGPO \(ours\)92\.2±\\pm6\.784\.4±\\pm15\.095\.7±\\pm4\.087\.8±\\pm7\.390\.2±\\pm4\.492\.8±\\pm2\.791\.4±\\pm1\.6

### 10\.3Novelty/Revisit Decomposition of the Obs\-Change Anomaly

The action\-level audit summarized in Figure[6](https://arxiv.org/html/2607.22724#S5.F6)\(b\) shows that Obs\-Change attains a*larger*aggregate mid\-band state\-changing shift than ProGPO \(\+0\.60\+0\.60vs\.\+0\.47\+0\.47\) yet a lower success rate\. Table[9](https://arxiv.org/html/2607.22724#S10.T9)resolves the paradox by splitting each observation\-changing action into two classes:*revisit*\(the resulting observation was already seen earlier in the trajectory, i\.e\. cycling\) and*novelty*\(a genuinely new observation\)\. For every category we report the paired shiftΔ​log⁡π\\Delta\\log\\piagainst GiGPO for Obs\-Change \(C0, no novelty gate\) and ProGPO \(C2, novelty\-gated\)\.

The decomposition shows that C0’s larger aggregate is spent in the wrong place\. On the navigation\-heavy categories where cycling is easiest—most sharply Pick2, the hardest category—C0*raises*the log\-probability of revisit \(cycling\) actions \(\+0\.61\+0\.61nats on Pick2\) while*suppressing*genuinely novel transitions \(−0\.85\-0\.85nats\); ProGPO does the opposite \(−0\.24\-0\.24on revisits,\+0\.37\+0\.37on novelty\)\. Averaged over all categories, C0 puts\+0\.40\+0\.40nats onto novelty but also a large positive mass onto revisits, whereas ProGPO’s novelty\-gated credit keeps revisit shifts net\-negative\. Rewarding cycling directly explains Obs\-Change’s lower success rate despite its larger undifferentiated shift, and confirms that the novelty gate—not raw observation change—is what channels the recalibration onto task\-advancing actions\.

Table 9:Per\-category novelty/revisit decomposition of the mid\-band state\-changing shiftΔ​log⁡π\\Delta\\log\\pi\(vs\. GiGPO, nats\) for Obs\-Change \(C0, no novelty gate\) and ProGPO \(C2, novelty\-gated\), on the offline expert\-replay audit \(Qwen2\.5\-1\.5B\-Instruct, ALFWorld, single seed\)\.*Revisit*: the target observation was seen earlier in the trajectory;*Novelty*: a genuinely new observation\.nrevn\_\{\\mathrm\{rev\}\}is the number of revisit actions audited\. Heat has no revisits in the audited set\. ProGPO suppresses revisit \(cycling\) credit while promoting novelty; C0 does the reverse on the hard, cycling\-prone categories\.CategoryRevisitΔ​log⁡π\\Delta\\log\\piNoveltyΔ​log⁡π\\Delta\\log\\pinrevn\_\{\\mathrm\{rev\}\}C0 \(Obs\-Ch\.\)C2 \(ProGPO\)C0 \(Obs\-Ch\.\)C2 \(ProGPO\)Clean−\-1\.679−\-1\.538\+0\.699\+0\.699\+0\.092\+0\.092132Cool−\-0\.648−\-1\.181\+0\.892\+0\.892\+0\.046\+0\.04655Heat——\+0\.613\+0\.613\+0\.290\+0\.2900Look−\-3\.398−\-1\.964−\-0\.770\+0\.249\+0\.24948Pick−\-2\.372\+0\.484\+0\.484−\-0\.266−\-0\.17146Pick2\+0\.608\\mathbf\{\+0\.608\}−0\.244\\mathbf\{\-0\.244\}−0\.847\\mathbf\{\-0\.847\}\+0\.372\\mathbf\{\+0\.372\}49All−\-1\.514−\-1\.066\+0\.397\+0\.397\+0\.081\+0\.081330
### 10\.4Training\-Seed Sensitivity

The controlled comparisons in Section[5\.2](https://arxiv.org/html/2607.22724#S5.SS2)fix the training seed to isolate the effect of the injected signal under identical rollout randomness\. To assess sensitivity to training stochasticity, we additionally trained ProGPO under a second training seed at the 30\-epoch budget and observed consistent improvements over the matched baseline \(32\.0% and 43\.0% vs\. 15\.6%\), with the better seed exhibiting healthier disengagement dynamics \(lower trigger rate and lower all\-fail rate at epoch 30\), as summarized in Table[10](https://arxiv.org/html/2607.22724#S10.T10)\.

Table 10:Training\-seed sensitivity on ALFWorld \(Qwen2\.5\-1\.5B\-Instruct, 30\-epoch snapshot\)\. All\-fail and trigger rates are computed over rollout\-level prompt groups\. ProGPO improves over the matched baseline under both seeds\. The second seed shows healthier disengagement: lower trigger rate and lower all\-fail rate at epoch 30\.Metric \(Epoch 30\)ProGPOBaseline \(Seed 42\)Seed 42Seed 0Overall SR \(%\)32\.043\.015\.6Trigger rate \(%\)12\.17\.2—All\-fail rate \(%\)68\.557\.384\.9Progress\-degenerate \(%\)58\.351\.0—
### 10\.5Inference\-Seed Robustness on Final Checkpoints

Final checkpoints in Table[1](https://arxiv.org/html/2607.22724#S5.T1)are re\-evaluated under three independent inference seeds; the reported mean±stdsummarizes that distribution\. Across both model scales, the inference\-seed standard deviation of GiGPO\+ProGPO is comparable to or smaller than that of the matched baseline, indicating that the gains from advantage repair are not produced by a single favourable evaluation run but persist under sampling stochasticity at test time\.

### 10\.6Fallback\-Scale Sweep

Section[5\.3](https://arxiv.org/html/2607.22724#S5.SS3)refers to a robustness check on the configured fallback ceilingλaux\\lambda\_\{\\mathrm\{aux\}\}\. Table[11](https://arxiv.org/html/2607.22724#S10.T11)reports a full\-budget sweep ofλaux∈\{0\.1,0\.3,0\.5,0\.7,1\.0\}\\lambda\_\{\\mathrm\{aux\}\}\\in\\\{0\.1,0\.3,0\.5,0\.7,1\.0\\\}on ALFWorld with the GiGPO base\. The remaining hyperparameters are numerical\-stability thresholds \(τRimpl=10−3\\tau\_\{R\}^\{\\mathrm\{impl\}\}\{=\}10^\{\-3\},τPimpl=10−4\\tau\_\{P\}^\{\\mathrm\{impl\}\}\{=\}10^\{\-4\}\) that guard against division by degenerate within\-group variance; they are not tuned on task performance and are not swept\.

Table 11:Full\-budget sweep ofλaux\\lambda\_\{\\mathrm\{aux\}\}on ALFWorld \(Qwen2\.5\-1\.5B\-Instruct, GiGPO base, 150 epochs\)\. Entries with a standard deviation are reported as five\-seed averages;0\.10\.1is a single\-seed diagnostic\.λaux=0\.3\\lambda\_\{\\mathrm\{aux\}\}\{=\}0\.3is the configured default used throughout the paper; the small numerical difference between the0\.30\.3row here and the91\.491\.4entry in Table[1](https://arxiv.org/html/2607.22724#S5.T1)reflects a different evaluation protocol \(five training seeds here vs\. three inference seeds from one trained checkpoint in Table[1](https://arxiv.org/html/2607.22724#S5.T1)\)\.λaux\\lambda\_\{\\mathrm\{aux\}\}PickLookCleanHeatCoolPick2All0\.1†100\.063\.6100\.0100\.095\.089\.594\.50\.3 \(default\)94\.9±\\pm3\.974\.5±\\pm12\.398\.4±\\pm2\.095\.9±\\pm5\.490\.6±\\pm4\.390\.9±\\pm3\.592\.2±\\pm2\.00\.585\.9±\\pm7\.559\.8±\\pm5\.880\.3±\\pm9\.881\.1±\\pm6\.574\.7±\\pm6\.576\.7±\\pm5\.378\.3±\\pm1\.30\.790\.1±\\pm5\.272\.4±\\pm10\.781\.2±\\pm8\.294\.5±\\pm5\.381\.4±\\pm3\.879\.4±\\pm9\.483\.6±\\pm2\.21\.092\.2±\\pm6\.784\.4±\\pm15\.095\.7±\\pm4\.087\.8±\\pm7\.390\.2±\\pm4\.492\.8±\\pm2\.791\.4±\\pm1\.6

### 10\.7Training Dynamics and All\-Fail Group Statistics

#### 10\.7\.1All\-Fail Rate over 150 Epochs

Section[5](https://arxiv.org/html/2607.22724#S5.F5)summarizes the dynamics figure \(Figure[5](https://arxiv.org/html/2607.22724#S5.F5)\) at four representative training points\. We report the full curve in Table[12](https://arxiv.org/html/2607.22724#S10.T12)for completeness\. The all\-fail group rate begins at∼92%\{\\sim\}92\\%for both methods \(early training\) and decays steadily under ProGPO to43\.6%43\.6\\%by epoch 150, while the baseline plateaus around7474–92%92\\%throughout training—consistent with ProGPO improving the policy precisely on the residual hard tasks that the baseline cannot escape\.

Table 12:All\-fail group rate and ProGPO fallback trigger rate \(%\) over training \(Qwen2\.5\-1\.5B\-Instruct, ALFWorld, matched training seed\)\. Rates are computed over the step\-level anchor\-state comparison groups formed by GiGPO; these differ from the rollout\-level prompt\-group rates reported in Table[10](https://arxiv.org/html/2607.22724#S10.T10)\. Lower values indicate that more groups have recovered outcome contrast\. These branch frequencies are distinct from the effective scaleλeff\\lambda\_\{\\mathrm\{eff\}\}in Eq\. \([30](https://arxiv.org/html/2607.22724#S8.E30)\)\.Epoch10306090120150GiGPO92\.184\.979\.478\.176\.574\.1GiGPO\+ProGPO92\.074\.160\.355\.749\.243\.6Reduction from GiGPO \(pp\)0\.110\.819\.122\.427\.330\.5ProGPO fallback trigger29\.411\.18\.36\.15\.34\.7Table 13:Per\-category share of all\-fail groups at epoch 30 \(%\)\. The shares sum to100%100\\%; hard categories dominate the degenerate\-group budget\.CategoryPickLookCleanHeatCoolPick2Share \(%\)4181262634
#### 10\.7\.2Fallback Trigger Rate and Auto\-Disengagement

A central design property of Eq\. \([7](https://arxiv.org/html/2607.22724#S4.E7)\) is that the progress branch should act as a bootstrap rather than as a permanent dense signal\. We track the fraction of rollout groups that enter the progress fallback branch at each epoch \(i\.e\., the fraction withσR<τR\\sigma\_\{R\}\{<\}\\tau\_\{R\},R¯=0\\bar\{R\}\{=\}0, andσP≥τP\\sigma\_\{P\}\{\\geq\}\\tau\_\{P\}\)\.

At epoch 10 the trigger rate is29\.4%29\.4\\%; it decays to11\.1%11\.1\\%by epoch 30 and to4\.7%4\.7\\%by epoch 150 as outcome variation re\-emerges\. The deployed implementation has two automatic hand\-off channels: fewer groups enter the fallback branch, and the common multiplierλeff=λaux​qfail\\lambda\_\{\\mathrm\{eff\}\}=\\lambda\_\{\\mathrm\{aux\}\}q\_\{\\mathrm\{fail\}\}decreases with the current all\-fail fraction\. Neither quantity uses a hand\-designed epoch schedule, but they must not be conflated in reporting\.

#### 10\.7\.3Per\-Category All\-Fail Composition

The aggregate all\-fail rate hides the fact that different ALFWorld categories contribute very unequally to the degenerate budget\. At epoch 30, the per\-category share of all\-fail groups is dominated by Pick2 \(34%34\\%\), Cool \(26%26\\%\), and Look \(18%18\\%\); Pick contributes only4%4\\%, as shown in Table[13](https://arxiv.org/html/2607.22724#S10.T13)\. This composition matches the per\-category gain pattern observed in Section[5](https://arxiv.org/html/2607.22724#S5): ProGPO’s largest improvements occur exactly where all\-fail groups are most prevalent, and its smallest improvement on Pick is consistent with that category producing very few groups for the fallback branch to repair\.

#### 10\.7\.4Fallback Runtime Diagnostics: Definitions and Additional Curves

Section[5\.3](https://arxiv.org/html/2607.22724#S5.SS3)studies the effect of the conditional switch\. Table[14](https://arxiv.org/html/2607.22724#S10.T14)gives the formal definition of each logged quantity used for the accompanying training\-time diagnostics\. All statistics are computed per policy update over the step\-level groups formed by the base algorithm \(anchor\-state groups in GiGPO; hierarchical groups in HGPO\), then averaged\.

Table 14:Definitions of the deployed fallback diagnostics\.GGranges over the comparison groups of one update andyiy\_\{i\}denotes the base score used by that grouping level\.MetricDefinitionTrigger ratefraction satisfyingmaxi∈G⁡\|yi\|<τRimpl\\max\_\{i\\in G\}\|y\_\{i\}\|<\\tau\_\{R\}^\{\\mathrm\{impl\}\}andStdpop⁡\(pG\)≥τPimpl\\operatorname\{Std\}\_\{\\mathrm\{pop\}\}\(p\_\{G\}\)\\geq\\tau\_\{P\}^\{\\mathrm\{impl\}\}Triggered / total groupsabsolute number of fallback\-branch groups / all groupsRepair magnitudemean of\|AiProGPO\|\|A\_\{i\}^\{\\mathrm\{ProGPO\}\}\|over trajectories in triggered groupsAll\-fail group ratefraction satisfyingmaxi∈G⁡\|yi\|<τRimpl\\max\_\{i\\in G\}\|y\_\{i\}\|<\\tau\_\{R\}^\{\\mathrm\{impl\}\}Uniform\-success group ratefraction with small score dispersion but non\-zero mean magnitude; discarded by the fallbackProgress\-degenerate ratefraction of all\-fail groups withStdpop⁡\(pG\)<τPimpl\\operatorname\{Std\}\_\{\\mathrm\{pop\}\}\(p\_\{G\}\)<\\tau\_\{P\}^\{\\mathrm\{impl\}\}Normal group ratefraction retaining a non\-zero base score and therefore using the unchanged base advantageEffective scaleλeff=λaux​qfail​\(ℬ\)\\lambda\_\{\\mathrm\{eff\}\}=\\lambda\_\{\\mathrm\{aux\}\}q\_\{\\mathrm\{fail\}\}\(\\mathcal\{B\}\)from Eq\. \([30](https://arxiv.org/html/2607.22724#S8.E30)\)For GiGPO\+ProGPO, Figure[7](https://arxiv.org/html/2607.22724#S10.F7)plots the eight runtime diagnostics referenced in the main text: the fallback trigger rate, mean repair magnitude, number of triggered groups, and all\-fail group rate \(top\), together with the composition of the remaining groups and the total group count \(bottom\)\. The trigger rate peaks early on the hardest setting and decays toward zero, the repair magnitude stays strictly positive, and the all\-fail share contracts as ProGPO hands control back to the base estimator\.

![Refer to caption](https://arxiv.org/html/2607.22724v1/x7.png)Figure 7:Runtime diagnostics of the conditional switch for GiGPO\+ProGPO over 150 training epochs \(1\.5B ALFWorld, 7B ALFWorld, 7B WebShop; faint lines are raw values, bold lines are smoothed\)\.Top:fallback trigger rate, mean repair magnitude, number of triggered groups, and all\-fail group rate\.Bottom:composition of the remaining groups \(uniform\-success, progress\-degenerate, normal\) and the total group count\. “Groups” refers to the step\-level anchor\-state groups formed by the base algorithm\.The independently logged HGPO\+ProGPO diagnostics show the same qualitative pattern as Figure[7](https://arxiv.org/html/2607.22724#S10.F7): the trigger rate decays from an early mean of approximately6%6\\%to1\.2%1\.2\\%on 1\.5B ALFWorld while the repair magnitude remains positive \(approximately0\.210\.21\); the all\-fail group rate contracts from45%45\\%to25%25\\%on 1\.5B ALFWorld and from42%42\\%to23%23\\%on 7B WebShop; and uniform\-success groups reach38%38\\%by the end of training\. Replication under different grouping structures supports the interpretation that automatic hand\-off follows from the conditional estimator rather than from a particular base optimizer\.

## 11Case Study: All\-Fail Groups

This section complements the aggregate analyses with two logged all\-fail groups—one from ALFWorld and one from WebShop—that illustrate how ProGPO assigns non\-zero advantages where the base estimator provides none\. Both groups are sampled from the trained GiGPO\+ProGPO checkpoint \(Qwen2\.5\-1\.5B, 150 epochs\) by runningK=8K\{=\}8rollouts on the same task and selecting a group in which every trajectory fails \(Ri=0R\_\{i\}\{=\}0\)\.

### 11\.1ALFWorld: Heat an Egg

##### Setup\.

The task is*“heat some egg and put it in garbagecan\.”*AllK=8K\{=\}8rollouts fail \(Ri=0R\_\{i\}\{=\}0\), so the reward\-based advantage is identically zero for every trajectory\. Table[15](https://arxiv.org/html/2607.22724#S11.T15)reports four representative trajectories of equal lengthT=20T\{=\}20, showing the first few actions, per\-step noveltyδt\\delta\_\{t\}, and the ProGPO advantageAiProGPO=\(Pi−P¯\)/σPA\_\{i\}^\{\\mathrm\{ProGPO\}\}=\(P\_\{i\}\-\\bar\{P\}\)/\\sigma\_\{P\}\.

Table 15:ALFWorld all\-fail group \(K=8K\{=\}8,Ti=20T\_\{i\}\{=\}20,Ri=0R\_\{i\}\{=\}0for allii\)\.τ1\\tau\_\{1\}explores multiple locations and receives the highest advantage;τ4\\tau\_\{4\}remains atbed 1throughout and receives the most negative\. The base estimator assignsAiR=0A\_\{i\}^\{R\}\{=\}0to all\.Traj\.TTNovelPiP\_\{i\}AiProGPOA\_\{i\}^\{\\mathrm\{ProGPO\}\}First actionsτ1\\tau\_\{1\}2070\.35\+1\.67\+1\.67go to cabinet 1,examine cabinet 1,go to cabinet 2,examine cabinet 2τ2\\tau\_\{2\}2040\.20−0\.33\-0\.33go to cabinet 1,take bowl 1,go to countertop 1,examine bowl 1τ3\\tau\_\{3\}2040\.20−0\.33\-0\.33go to cabinet 1,examine cabinet 1,go to countertop 1,examine coffeemachine 1τ4\\tau\_\{4\}2030\.15−1\.00\-1\.00go to bed 1,examine bed 1,examine bed 1,examine bed 1
##### Analysis\.

τ1\\tau\_\{1\}visits multiple locations \(cabinet 1, cabinet 2\) and produces 7 novel observations, earning the highest progress scoreP=0\.35P\{=\}0\.35and a positive advantageA=\+1\.67A\{=\}\{\+\}1\.67\. In contrast,τ4\\tau\_\{4\}navigates tobed 1and repeatedly examines it, producing only 3 novel observations and receivingA=−1\.00A\{=\}\{\-\}1\.00\. The base estimator, which relies on outcome rewards, assigns all trajectories zero advantage; ProGPO recovers a meaningful ranking from observation coverage alone, directing the gradient toward the more exploratory trajectory\.

### 11\.2WebShop: Searching for Pants

##### Setup\.

The task is to find men’s pants with specific attributes \(color: rockdale, size: 29, fit: relaxed, price<<$80\)\. AllK=8K\{=\}8rollouts fail to purchase a matching item \(Ri=0R\_\{i\}\{=\}0\)\. Table[16](https://arxiv.org/html/2607.22724#S11.T16)reports four representative trajectories of lengthT=15T\{=\}15\.

Table 16:WebShop all\-fail group \(K=8K\{=\}8,Ti=15T\_\{i\}\{=\}15,Ri=0R\_\{i\}\{=\}0for allii\)\.τ3\\tau\_\{3\}andτ6\\tau\_\{6\}issue diverse search queries and click different products, reaching 7 novel observations;τ1\\tau\_\{1\}andτ4\\tau\_\{4\}repeat the same search and never leave the search page\.Traj\.TTNovelPiP\_\{i\}AiProGPOA\_\{i\}^\{\\mathrm\{ProGPO\}\}First actionsτ3\\tau\_\{3\}1570\.47\+1\.17\+1\.17search\[rockdale, relaxed, size:29, \.\.\.\],search\[pants men \.\.\.\],click\[B099231V35\]τ2\\tau\_\{2\}1560\.40\+0\.65\+0\.65search\[pants color: rockdale, \.\.\.\],search\[mens rockdale \.\.\.\],click\[B09GPJVQNT\]τ5\\tau\_\{5\}1540\.27−0\.39\-0\.39search\[pants \.\.\.\],click\[Search\],search\[pants \.\.\.\]τ1\\tau\_\{1\}1520\.13−1\.43\-1\.43search\[long lasting, \.\.\.\],click\[Search\],search\[long lasting, \.\.\.\]
##### Analysis\.

τ3\\tau\_\{3\}issues diverse search queries with different keyword orderings and clicks on a specific product \(B099231V35\), generating 7 novel page observations \(P=0\.47P\{=\}0\.47,A=\+1\.17A\{=\}\{\+\}1\.17\)\.τ1\\tau\_\{1\}repeats the same lengthy search query and only clicksSearch, never reaching a product page—it produces just 2 novel observations \(P=0\.13P\{=\}0\.13,A=−1\.43A\{=\}\{\-\}1\.43\)\. ProGPO’s novelty gate correctly distinguishes genuine page transitions from repeated search submissions, assigning higher advantage to trajectories that explore the product space more broadly\.

##### Cross\-environment takeaway\.

In both environments, ProGPO recovers a meaningful within\-group ranking from observation coverage alone when the reward signal is completely degenerate\. The advantage direction is consistent with task progress: trajectories that visit more diverse states—whether embodied locations in ALFWorld or product pages in WebShop—receive higher advantage, while those that stagnate receive negative advantage\. These examples are illustrative rather than statistically conclusive; the controlled quantitative results in Sections[5](https://arxiv.org/html/2607.22724#S5)and[5\.3](https://arxiv.org/html/2607.22724#S5.SS3)establish effectiveness at scale\.

## 12Limitations and Broader Impact

##### Limitations\.

ProGPO’s progress measure is observation\-level: it assumes that meaningful environment transitions are reflected in the observation string\. This is a faithful proxy in text\-rich agentic environments such as ALFWorld and WebShop but may be weaker in environments where consequential state changes are not externalized in the observation \(e\.g\., latent variables, hidden inventory state\)\. In such settings the progress score may need to be replaced or augmented with an environment\-specific signal; ProGPO’s conditional structure \(Eq\. \([7](https://arxiv.org/html/2607.22724#S4.E7)\)\) is independent of which fallback signal is plugged in, so we view this as a generalization direction rather than a fundamental limitation\. A second limitation is that ProGPO repairs only the all\-fail branch of group degeneracy: all\-success groups are discarded exactly as in standard group\-relative estimation \(Section[4\.2](https://arxiv.org/html/2607.22724#S4.SS2)\)\. This is benign in our setting—uniform success indicates the task is already mastered—and such groups are empirically far less common than all\-fail groups in the long\-horizon regime we study, but environments where uniformly successful groups still contain quality differences \(e\.g\., dense\-scored tasks\) may warrant a symmetric treatment\.

##### Broader impact\.

ProGPO is a generic credit\-assignment mechanism for group\-based RL of LLM agents and inherits the broader\-impact considerations of the underlying RL training stack\. By reducing the fraction of wasted rollout groups, it lowers the effective compute cost of training capable long\-horizon agents, which is environmentally favourable but also lowers the resource barrier for training agents that act in real or simulated environments—including settings where action consequences are not benign\. We recommend that downstream applications of ProGPO\-trained agents follow the deployment\-time safeguards \(action filters, sandboxing, human oversight\) that are standard for autonomous LLM agents\.

## 13Use of Large Language Models

In preparing this manuscript, large language models were used solely as writing\-assistance tools \(light copy editing, surface\-level rephrasing, andLaTeXformatting suggestions\) on text drafted by the authors\. They were not used to design the method, derive the equations, run experiments, generate or select results, or produce figures\. All experimental code, analyses, and final scientific claims were authored, executed, and verified by the human authors, who take full responsibility for the content of this paper\.