Granularity-Adaptive Credit Assignment for Long-Horizon LLM Agent Reinforcement Learning

1 INTRODUCTION

• GACA adapts episode- and step-level credit because episode-wide signals are coarse while step comparisons have context-dependent estimation noise.The method addresses whether every decision should use the two signals in the same proportion.Source: §1 · p. 1
• A trajectory-normalized sampled-response mean per-token NLL becomes a criticality score that sets each decision’s mixture weight, reusing rollout log-probabilities without extra rollouts or model evaluations.Higher scores receive more step-level credit.Source: §1 · pp. 1–2
• The analysis characterizes score-dependent error trade-offs and conditions under which expected NLL bounds action-value variation, motivating more step-level credit at higher scores.The result is conditional, rather than a claim that NLL always identifies consequential decisions.Source: §1 · p. 2
• GACA complements methods that refine step estimators by using uncertainty to control the relative contribution of two credit granularities.The introduction contrasts this with methods that rescale an existing advantage.Source: §1 · p. 2
• 96.88% success on ALFWorld 1.5B, versus 93.05% for the best tested fixed mixture and 88.54% for random score assignment.The matched comparisons test both mixing weights and their assignment to individual decisions.Source: §1 · p. 2

2.1 SEQUENTIAL INTERACTION AND POLICY OPTIMIZATION

• A per-step advantage is broadcast to valid response tokens for the clipped policy update.The rollout group supplies trajectories for relative advantage estimation.Source: §2.1 · p. 2

2.2 EPISODE- AND STEP-LEVEL CREDIT

• Episode-side credit compares a trajectory outcome, adjusted by the configured local invalid-action penalty, with its prompt group.The trajectory outcome is shared across decisions, with validity adjustment applied before normalization.Source: §2.2 · p. 2
• Step credit groups steps with identical anchor observations and compares their discounted returns; singleton groups use prompt-group normalization.Anchor matching can group steps with different histories, and the resulting estimation error is included in the analysis.Source: §2.2 · pp. 2–3
• Figure 1 depicts episode credit, anchor-grouped step credit, and sampled-response NLL feeding a mixed advantage that is broadcast to response tokens.Its trajectories and signal values are schematic.Source: Figure 1 · p. 3

3 GRANULARITY-ADAPTIVE CREDIT ASSIGNMENT

• GACA reuses group-relative episode and step advantages and logged token probabilities, adding scalar score and mixing operations to assign each step a weight.The resulting advantage is used for the policy update.Source: §3 · p. 3

3.1 AN NLL-BASED CRITICALITY SCORE

• The criticality score is sampled-response mean per-token NLL normalized by the trajectory mean; ct > 1 marks a response more surprising than that trajectory’s average.For positive trajectory NLL, scores have mean one and preserve the within-trajectory ordering of NLL.Source: §3.1 · p. 3

3.2 BOUNDED ADAPTIVE MIXING

• The bounded gate λt = min{λ0(1 + αλct), 1} sets a step-weight floor and increases the weight with criticality until saturation.With defaults λ0 = αλ = 0.5, the weight is 0.75 at ct = 1 and reaches its cap at ct = 2.Source: §3.2 · p. 4

3.3 WHY ADAPT THE CREDIT GRANULARITY?

• The oracle conditional weight balances episode- and step-estimator errors, and it can improve on the best constant mixture when its unique optimum varies across scores where q > 0.The weight is projected onto [0,1].Source: §3.3 · p. 4
• Holding residual moments and other stated quantities fixed, greater action-value variation favors the finer estimator when vS > χ, strictly so in the interior when η > 0.This condition reflects the greater cost of coarse credit when action values vary more.Source: §3.3 · p. 5
• Under the stated finite-support, length, and within-action variation assumptions, expected NLL bounds uncertainty over distinct actions, with a positive diversity bound when Lminh > Bs.For fixed Ks, Bs, and Lmin, the bound is nondecreasing in expected NLL.Source: §3.3 · p. 5
• Composing the diversity bound with the action-value analysis yields a nondecreasing lower bound on preferred step-level weight under fixed regularity and residual-noise parameters.The claimed route from expected NLL to finer credit is conditional on those parameters.Source: §3.3 · p. 5

4.1 EXPERIMENTAL SETUP

• The evaluation uses Qwen2.5-Instruct 1.5B and 7B on ALFWorld and WebShop, selects ALFWorld checkpoints by three-seed mean, and compares published references under their source protocols.For ALFWorld 1.5B, the selected update is 275; evaluations use 128 in-distribution tasks and temperature 0.4.Source: §4.1 · pp. 5–6

4.2 OVERALL PERFORMANCE

• 96.88% and 98.18% on ALFWorld and 80.99% and 83.59% on WebShop make GACA highest in mean success among listed methods across four settings.These values correspond to the 1.5B and 7B backbones, respectively.Source: Table 1 · p. 6, §4.2 · p. 6
• 92.19 ± 3.88% at update 150 rises to 96.88±0.64% at update 275, with 96.09±1.10% at update 300.The curve and band show mean and population SD across three evaluation seeds for one training run.Source: Figure 2 · p. 7, §4.2 · p. 7
• 0.09 seconds per iteration: GACA's added scalar operations are small beside an approximately 372-second iteration, with peak memory of 62.4 GB.The timings average 20 iterations on the same hardware.Source: §4.2 · p. 7

4.3 EFFECT OF ADAPTIVE CREDIT ALLOCATION

• 96.88% versus 93.05%: adaptive mixing beats the best tested fixed weight, λ = 0.5, by 3.83 points; every tested interior mixture beats both endpoints.The episode-only and step-only endpoints reach 85.94% and 84.60%, respectively.Source: §4.3 · p. 7, Figure 3 · p. 8
• 8.34 points: permuting criticality scores within trajectories lowers success from 96.88% to 88.54%, indicating that weight assignment to individual decisions matters.The control retains each trajectory's collection of gate values but changes their pairing with episode- and step-level advantages.Source: §4.3 · p. 7, Figure 3 · p. 8

4.4 WITHIN-TRAJECTORY ANALYSIS OF THE NLL SCORE

• 0.1789 versus 0.1041: higher-score states have greater mean action disagreement than lower-score states, with a paired difference of 0.0747 (95% task-bootstrap interval [0.0248, 0.1334]).The diagnostic uses paired states from 32 training tasks and estimates disagreement from fresh responses.Source: §4.4 · p. 8, Figure 4 · p. 9

• GACA uses rollout NLL to adapt the mixture of episode- and step-level credit during policy optimization, without additional training rollouts or model evaluations.Source: §5 · p. 9
• Across ALFWorld and WebShop with two backbone sizes, GACA achieves the highest reported mean success rates among compared methods.Source: §5 · p. 9
• Matched ALFWorld ablations show gains over tested fixed weights and within-trajectory random assignment, supporting step-dependent credit mixing as a practical design choice for critic-free agent training.Source: §5 · p. 9

• Generative AI tools assisted with manuscript editing and theoretical exposition.Source: AI USE STATEMENT · p. 9
• The tools also assisted with figure preparation.Source: AI USE STATEMENT · p. 9
• Diagnostic experiment design was another area of assistance; the authors state that they are responsible for verifying arguments, implementation descriptions, references, and reported results.Source: AI USE STATEMENT · p. 9

REPRODUCIBILITY STATEMENT

• Appendices B–C contain theoretical statements and proofs, while D–E specify training settings, advantage normalization, singleton fallback, and criticality construction.Source: REPRODUCIBILITY STATEMENT · p. 9
• Appendix G gives the full numerical ablation grid, Appendix H defines diagnostic estimators, and Section 4.1 records checkpoint selection and external baseline sources.Source: REPRODUCIBILITY STATEMENT · p. 9

A EXTENDED RELATED WORK

• HGPO, BiPACE, and ProGPO refine local credit construction, whereas GACA changes the relative weight assigned to local and episode-level credit at each step.Source: A EXTENDED RELATED WORK · p. 12
• Process supervision and intermediate-state rollouts provide other routes to denser credit; GACA instead reuses rollout log-probabilities to mix existing critic-free estimates using a per-step score.Source: A EXTENDED RELATED WORK · p. 12
• AEM and STARE rescale pre-existing credit signals, while GACA uses its score to construct a mixture of episode- and step-level estimates.Source: A EXTENDED RELATED WORK · p. 12
• GACA uses uncertainty at the environment-step level to determine how much to rely on the two credit granularities.Source: A EXTENDED RELATED WORK · p. 12

B DETAILED THEORY STATEMENTS

• The risk-minimizing score-dependent mixture is no worse than the best constant weight, with strict improvement when its optimum varies over scores with q(c) > 0.When q(c) = 0, the two credit estimates agree conditionally and the weight is irrelevant.Source: B DETAILED THEORY STATEMENTS · p. 13
• When vS > χ, the preferred fine-credit weight is nondecreasing in local action-value heterogeneity C, and strictly increases in the interior when η > 0.Under the stated shared-noise structure, vS − χ equals the fine estimator’s residual-noise variance.Source: B DETAILED THEORY STATEMENTS · p. 14
• Expected response NLL lower-bounds canonical-action diversity, with a positive bound whenever Lminh(s) > Bs.Bs bounds textual variation among responses that execute the same action.Source: B DETAILED THEORY STATEMENTS · p. 14
• Under fixed regularity and residual-noise parameters, the preferred fine-credit weight has a nondecreasing lower envelope in expected NLL when vS > χ and the stated conditions hold.The argument links expected NLL to action diversity, then to local value heterogeneity and the preferred granularity.Source: B DETAILED THEORY STATEMENTS · pp. 14–15
• GACA uses each completed rollout’s sampled-response NLL to set a trajectory-relative gate that assigns at least as much step-level weight to higher-scoring responses.The increasing direction is motivated by the population analysis; the gate floor and modulation strength are empirical design choices.Source: B DETAILED THEORY STATEMENTS · p. 15

C.4 PROOF OF COROLLARY 4

• The expected squared difference between two independently sampled action values equals 2C(s), and also equals D(s)κs when D(s) > 0.Here D(s) is the probability that the sampled canonical actions differ, and κs is the conditional squared value difference given distinct actions.Source: §C.4 · p. 16

C.5 PROOF OF COROLLARY 5

• With fixed coarse-to-fine parameters and vS > χ, the bound on action-value heterogeneity yields a nondecreasing lower envelope on preferred fine-credit weight in expected NLL.The proof composes the nondecreasing optimum in C with the lower bound C(s) ≥ Cs(h(s)).Source: §C.5 · p. 17

C.6 THE IMPLEMENTED NLL SCORE

• The population analysis uses expected mean per-token NLL, while GACA computes a sampled response’s NLL after rollout completion and normalizes it within the trajectory.The sampled score may depend on the action and continuation; scores and advantages are held fixed during policy optimization.Source: §C.6 · p. 17

D TRAINING CONFIGURATION AND HYPERPARAMETERS

• Both benchmarks use the agent-environment interface with sparse episode-level success rewards and a small invalid-action penalty.The training-settings and hyperparameter tables record configurations and GACA defaults with their search ranges.Source: Table 2 · p. 17, D TRAINING CONFIGURATION AND… · p. 17, Table 4 · p. 18

D.1 EVALUATION PROTOCOL AND PUBLISHED REFERENCES

• Each selected ALFWorld checkpoint is evaluated three times, and the final update 300 is reported independently of checkpoint selection.The reported mean and population SD use the three scores at the same update; the checkpoint is selected by maximizing their mean.Source: §D.1 · p. 18, Table 6 · p. 18
• The published-reference comparison retains source protocols, including distinct WebShop horizons and framework versions.GACA’s ALFWorld deviations summarize three evaluation seeds at one selected checkpoint.Source: Table 7 · p. 19, §D.1 · p. 19

E IMPLEMENTATION DETAILS

• The centered gate expresses the criticality-dependent mixture; singleton step groups use prompt-group statistics for return normalization.The implementation also specifies normalization conventions over step rows and loss and regularization settings for the archived ALFWorld 1.5B run.Source: E IMPLEMENTATION DETAILS · pp. 19–20

F COMPUTATIONAL COST

• 0.09 s per iteration covers GACA’s two added components over GiGPO; this timing comparison reports overhead below 0.2% over GRPO.The timing breakdown averages 20 iterations on the same hardware; peak memory is reported as the same across the three configurations.Source: F COMPUTATIONAL COST · p. 20, Table 8 · p. 20

G.1 MODULATION STRENGTH AND THE MIXING LAW

• 96.88% at αλ = 0.5 exceeds the fixed-mixture result of 93.05%; αλ = 0.25 and 1 yield 95.12% and 95.44%, respectively.The sweep varies mean weight together with sensitivity to criticality and the extent of clipping.Source: Table 9 · p. 21, §G.1 · p. 21

G COMPLETE ABLATION RESULTS

• The complete ALFWorld 1.5B ablation grid varies one design choice per block; its two fixed-0.5 entries are the same configuration and result.The full default configuration is shaded, and best results per block are bolded.Source: G COMPLETE ABLATION RESULTS · p. 20, Table 9 · p. 21

G.2 CHOICE OF CRITICALITY SIGNAL

• 96.88% for pure NLL (αc = 1) compares with 96.05% and 95.20% for NLL shares 0.7 and 0.5, supporting the NLL-only choice among tested constructions.Source: §G.2 · p. 21, Table 9 · p. 21

H SUPPLEMENTARY DIAGNOSTICS

• The supplementary diagnostics use the frozen ALFWorld 1.5B final@300 checkpoint, with a 50-step episode limit and two-step history window.The weight-distribution sample uses 16 fixed training tasks; paired diagnostics use 32 stratified tasks.Source: H SUPPLEMENTARY DIAGNOSTICS · p. 22

H.1 TRAINING MEAN AND FROZEN-POLICY WEIGHTS

• 0.7484 is the sampled weight mean in the frozen-policy diagnostic; the training log’s step-weighted mean is approximately 0.748.The frozen-policy sample comprises 128 trajectories and 1,269 decisions; 2.68% of steps reach λt = 1.Source: Figure 5 · p. 22, §H.1 · p. 22

H.2 WITHIN-TRAJECTORY SCORE AND ACTION DIVERSITY

• 11 of 32 paired action-diversity differences are positive, five negative, and 16 zero; the difference remains positive after every leave-one-task-out exclusion.The leave-one-task-out range is 0.0569–0.0834, and normalization preserves the within-trajectory NLL ordering.Source: §H.2 · p. 23

H.3 ACTION-VALUE MEASUREMENTS

• The action-value-difference interval includes zero, providing no clear evidence of value separation between higher- and lower-score states in this panel.Table 10 reports paired measurements ordered by original rollout criticality, with differences defined as higher-score minus lower-score.Source: §H.3 · p. 23, Table 10 · p. 23