PaperlayerView exact revision on arXiv

Source-linked AI summary

AdaStep: Adaptive Step Credit Weighting for Agentic Reinforcement Learning

Xin Wang, Wenhao Wu, Menghao Zhang, Zhi Wang, Kun Shao, Jian Luan

arXiv:2610.03223v1cs.LGcs.CL

TL;DR

Long-horizon LLM agents receive sparse outcome rewards, leaving trajectory-level signals too coarse to distinguish individual decisions, while local step-credit estimates can be noisy. AdaStep adapts the local correction with a per-state shrinkage coefficient derived from a mean-squared-error objective. Across three backbones and benchmarks, it consistently improves over GRPO, GiGPO, and HGPO; extending it to continuous or partially observable environments remains open.

  • Problem

    Sparse, delayed rewards and trajectory-level credit make it difficult to distinguish which intermediate actions contributed to an outcome.

    Source: §1 · p. 2

  • Method

    AdaStep derives a per-state shrinkage coefficient from a mean-squared-error objective to adapt how strongly local step-level advantages modify the trajectory-level signal.

    Source: §1 · p. 2

  • Results

    Across three backbones and three benchmarks, AdaStep consistently improves over GRPO, GiGPO, and HGPO, with gains that persist with and without advantage normalization.

    Source: §6 · p. 10

  • Takeaways & Limitations

    The coefficient reflects the fraction of return variance explained by the selected action, and AdaStep adds negligible computational cost.

    Source: §6 · p. 10

    The derivation assumes action–return pairs are i.i.d. conditional on the anchor state and that within-group return variance is finite.

    Source: §4.3 · p. 6

Abstract

from arXiv · show

Long-horizon LLM agents are typically trained with sparse outcome rewards, making trajectory-level objectives too coarse to distinguish the contribution of individual decisions. Step-level credit assignment provides finer-grained supervision, but its estimates can be unreliable because observed returns also depend on subsequent actions, environment transitions, and trajectory length. We propose AdaStep, an Adaptive Step-credit weighting method that controls how strongly each group-derived local advantage modifies the trajectory-level signal. We formulate this weighting as a mean-squared-error estimation problem for the latent step advantage and, under an explicit conditional sampling assumption, derive an optimal per-state shrinkage coefficient. The coefficient admits a signal-to-total-variance interpretation: it preserves local credit when return variation is attributable to the selected action and suppresses it when variation is dominated by downstream randomness. AdaStep requires only lightweight scalar computation, with no critic, additional rollouts, or extra model inference. Experiments with three model backbones on ALFWorld, WebShop, and ScienceWorld show consistent improvements over baselines at low computational cost.

1 INTRODUCTION

Long-horizon agent tasks expose the limits of trajectory-level credit, while local step-level corrections can be unreliable. AdaStep adapts the strength of each local correction to its credibility, and improves performance across three benchmarks.

1 INTRODUCTION

  • Trajectory-level credit broadcasts one outcome advantage across a trajectory, so useful actions in failed episodes may be penalized and unhelpful actions in successful episodes reinforced.Sparse, delayed rewards make it difficult to identify which intermediate actions contributed to an outcome.Source: §1 · p. 2
  • GiGPO adds finer-grained local credit, but finite-sample step advantages can be unreliable because downstream randomness may produce opposite estimates even for the same state–action pair.Strong corrections can amplify noise, while weak corrections can suppress useful action information.Source: §1 · p. 2
  • AdaStep retains the global advantage and adapts each group’s local correction to its estimation credibility, deriving the coefficient under a mean-squared-error objective from existing rollout statistics.It requires no critic, additional rollouts, or extra model forward passes.Source: §1 · p. 2
  • The method frames local advantage weighting as estimating the true step-level advantage relative to the trajectory-level signal, making the trade-off between useful local information and sampling error explicit.Its per-group correction coefficient is computationally tractable under stated assumptions.Source: §1 · p. 2
  • AdaStep tops all trained baselines across three benchmarks, gaining up to +9.36 points over GiGPO.The method adds about 1% credit-computation time.Source: §1 · p. 2

2 RELATED WORK

Prior group-based reinforcement-learning methods estimate relative advantages without a separately trained value function. For step-level credit, AdaStep derives state-specific scaling from an estimation objective, while related approaches use other grouping, supervision, or calibration strategies.

Reinforcement learning for large language models

  • Group-based methods estimate relative advantages from multiple responses to the same prompt, avoiding a separately trained value function and reducing training costs.Examples include RLOO, GRPO, Dr. GRPO, DAPO, and CPPO.Source: §2 · p. 3

Step-level advantage assignment

  • AdaStep derives state-specific scaling for GiGPO’s step-level correction from an explicit estimation objective, accounting for action-conditional bias from a shared group baseline and its cancellation after marginalizing over actions.The related-work passage contrasts this with PGPO, which does not explicitly control correction strength, and ECPO’s heuristic calibration.Source: §2 · p. 3

3 PRELIMINARIES

The paper studies multi-step LLM-agent tasks with sparse binary success rewards and reviews group-relative methods for estimating trajectory- and step-level advantages. GRPO supplies a global signal; GiGPO adds local corrections from matched states across rollouts.

3.1 PROBLEM SETUP

  • For the studied tasks, rewards are zero before the final step and binary at the end, so each trajectory’s return indicates success or failure.The agent acts over a horizon T in an environment modeled as an MDP, with textual actions and scalar rewards.Source: §3.1 · p. 3

3.2 GRPO AND GIGPO

  • GRPO contrasts returns from multiple rollouts of the same prompt and applies each trajectory’s scalar group-relative advantage to all its state–action pairs.This is a global but coarse signal that does not distinguish individual actions’ contributions.Source: §3.2 · pp. 3–4
  • GiGPO groups actions and returns from matched anchor states across rollouts, using subsequent discounted returns to form step-level advantages.These local corrections supplement the episode-level relative advantage, which remains the global reference.Source: §3.2 · p. 4

4 METHODS

AdaStep addresses coarse trajectory-level credit by adjusting how strongly noisy group-based local advantages modify the policy signal. It frames this adjustment as an optimal per-state estimation problem and computes the weight from group return statistics.

4.1 MOTIVATION

  • GRPO broadcasts one trajectory-level advantage across decisions, while local returns can reflect randomness in subsequent actions and transitions rather than the current action.Thus, the local signal can provide finer credit but may not faithfully represent the true step advantage.Source: §4.1 · p. 5

4.2 OPTIMAL PER-STATE SHRINKAGE

  • AdaStep chooses a per-state scalar by minimizing mean-squared error between the weighted group estimate and the true step-level advantage.The optimal projection requires a strictly positive second moment of the estimate; its expression involves the estimate’s alignment with the truth and its second moment.Source: §4.2 · pp. 5–6

4.3 COMPUTABLE FORM FROM GROUP STATISTICS

  • AdaStep exceeds GiGPO in every displayed metric for both model blocks shown in Table 1.The table reports performance across three benchmarks, averaged over three random seeds.Source: Table 1 · p. 7
  • Under conditionally i.i.d. action–return pairs and finite return variance, the optimal weight can be expressed using return-variance statistics collected within a group.The weight is the fraction of return variance attributable to differences in expected return across actions; it approaches 1 when signal dominates and 0 when noise dominates.Source: §4.3 · pp. 6–8
  • The computed group-specific weight replaces GiGPO’s global coefficient and scales the local advantage; with standard-deviation normalization, normalization is applied before weighting.The return-variance form estimates the weight without explicitly estimating action values.Source: §4.3 · p. 8

5 EXPERIMENTS

Across three backbones and benchmarks, AdaStep consistently outperforms HGPO and GiGPO. Further experiments examine normalization, fallback weights, coefficient sensitivity, step-credit estimation, and computation.

5.1 MAIN RESULTS

  • AdaStep consistently outperforms HGPO and GiGPO across all model–benchmark combinations, with more pronounced gains over GRPO and PPO.The evaluation uses Qwen3-1.7B, Qwen3-4B, and Qwen2.5-7B-Instruct on ALFWorld, WebShop, and ScienceWorld.Source: §5.1 · p. 8, §5 · p. 8

5.2 ROBUSTNESS TO ADVANTAGE NORMALIZATION

  • AdaStep achieves higher mean performance than GiGPO with and without standard-deviation normalization.The coefficient is computed from unnormalized group statistics before step-level advantages are normalized.Source: §5.2 · p. 8, Table 2 · p. 8

5.3 FALLBACK WEIGHTS FOR NON-ESTIMABLE GROUPS

  • Groups need at least two actions, two returns per action, and positive return variance for coefficient estimation; among fallback weights, w = 1 has the highest observed success on WebShop and ALFWorld.The fallback comparison uses Qwen2.5-7B-Instruct.Source: §5.3 · pp. 8–9, Table 3 · p. 9

5.4 SENSITIVITY TO THE STEP-LEVEL COEFFICIENT

  • On ALFWorld and WebShop, moderate local weighting improves performance, excessive weighting degrades it, and AdaStep beats every tested fixed coefficient.The comparison uses Qwen2.5-7B-Instruct.Source: §5.4 · p. 9, Figure 3 · p. 9

5.5 ANALYSIS OF STEP-CREDIT ESTIMATION ON WEBSHOP

  • On 3,666 historical WebShop anchor-state groups, AdaStep reduces within-action variation and achieves the lowest held-out reference MSE.The diagnostics measure within-action credit fluctuation and deviation from action-level advantages estimated on a separate sample subset.Source: §5.5 · p. 9, Figure 3 · p. 9

5.6 COMPUTATIONAL EFFICIENCY

  • On WebShop with Qwen2.5-7B-Instruct, AdaStep has the highest mean success rate, uses approximately 1.0% more credit-computation time than GiGPO, and less time than HGPO.Table 4 compares per-iteration return and advantage computation.Source: §5.6 · p. 9, Table 4 · p. 9

6 CONCLUSION

AdaStep derives a per-state shrinkage coefficient from a mean-squared-error objective for latent step advantage. It improves over GRPO, GiGPO, and HGPO across three backbones and benchmarks, while extension to continuous or partially observable environments remains open.

6 CONCLUSION

  • AdaStep derives an optimal per-state shrinkage coefficient from a mean-squared-error objective on latent step advantage.The coefficient represents the fraction of return variance explained by the selected action.Source: §6 · p. 10
  • Across three backbones and three benchmarks, AdaStep consistently improves over GRPO, GiGPO, and HGPO at negligible computational cost.Gains persist with and without advantage normalization.Source: §6 · p. 10
  • Extending AdaStep to continuous or partially observable environments, where anchor states cannot be matched directly, remains open.Source: §6 · p. 10

A PROOFS OF MAIN RESULTS

The proofs establish the optimal per-state correction weight under conditional sampling assumptions and explain how it reflects the credibility of a step-level estimate. They also distinguish population-level uniqueness from degenerate or uninformative return groups.

Proofs of main results

  • Under conditional i.i.d. action–return sampling with finite return variance, the optimal weight uniquely minimizes a strictly convex mean-square objective when the estimate has positive second moment.The objective is a quadratic in the correction weight; its minimizer is the projection of the true step advantage onto the estimate.Source: A PROOFS OF MAIN RESULTS · pp. 12, 15
  • The step-level estimate is biased by a 1/Ns factor conditional on a fixed action, but unbiased after averaging over actions at the state.The group mean includes the sampled return itself; the remaining group members’ deviations have conditional mean zero.Source: A PROOFS OF MAIN RESULTS · pp. 12–13
  • An individual group with identical returns cannot determine a unique correction weight, even when the population-level objective has a unique minimizer.At zero state-level return variance, the variance-ratio formulas are undefined.Source: A PROOFS OF MAIN RESULTS · p. 15
  • The optimal weight is the variance of expected returns across actions divided by total return variance, separating action-related signal from conditional return variability.The weight lies in [0, 1]; it is 1 when expected conditional return variance is zero and 0 when action values are constant.Source: A PROOFS OF MAIN RESULTS · pp. 12, 15

B PSEUDO CODE

AdaStep builds step-level groups from rollouts, estimates a separate coefficient from group and within-action return variability, and combines the local correction with the trajectory-level advantage. The resulting advantages are held fixed during policy optimization.

Pseudo code

  • For each task, the procedure groups rollout steps by anchor-state key and collects discounted returns, actions, and group-level statistics.It also partitions each group by observed action to estimate within-action return variability.Source: B PSEUDO CODE · p. 16
  • The empirical coefficient is computed only when a group has at least two distinct actions, at least two returns per action, and positive total return variance; otherwise it falls back to 1.If all group returns are identical, the step-level advantages are set to zero and the variance ratio is skipped.Source: B PSEUDO CODE · pp. 16–17
  • AdaStep combines the trajectory-level advantage with the group-weighted step-level advantage, using benchmark-specific normalization where specified.The coefficients and advantages are computed from old-policy rollouts and held fixed during policy optimization.Source: B PSEUDO CODE · pp. 16–17

B.1 POLICY OPTIMIZATION OBJECTIVE

AdaStep uses GiGPO’s clipped policy objective with an adaptive combined advantage. The clipping interval and KL penalty are controlled by separate parameters, and a fixed coefficient recovers GiGPO’s objective.

Policy optimization objective

  • AdaStep optimizes the clipped policy objective using its adaptive combined advantage and an importance-sampling ratio for each sampled action.The objective is averaged across tasks in a batch, with only valid steps contributing.Source: §B.1 · p. 17
  • The parameter ϵ sets the importance-ratio clipping interval, while β controls the KL penalty toward the fixed reference policy.The old policy is refreshed before each rollout iteration.Source: §B.1 · p. 17
  • Replacing AdaStep’s adaptive coefficient with a fixed ω recovers GiGPO’s advantage and corresponding clipped objective.When every trajectory has length T, the number of valid steps is M = NT.Source: §B.1 · p. 17

C EXPERIMENTAL DETAILS

The experiments evaluate AdaStep across three long-horizon benchmarks and three Qwen backbones, against prompting, frontier-model, and reinforcement-learning baselines. The prompt templates use tagged reasoning and action fields.

C EXPERIMENTAL DETAILS

  • The evaluation covers ALFWorld, WebShop, and ScienceWorld, with ScienceWorld restricted to eight simple tasks.The benchmarks use maximum episode lengths of 50 steps for ALFWorld and 30 for WebShop and ScienceWorld.Source: C EXPERIMENTAL DETAILS · p. 18
  • Baselines span frontier models, prompting methods, and RL methods, including PPO, GRPO, GiGPO, and HGPO.The reported runs use 8 NVIDIA H100 GPUs for 160 training steps, with each run taking no more than 16 hours; reported means and standard deviations use three seeds.Source: C EXPERIMENTAL DETAILS · pp. 18–19
  • Experiments use Qwen2.5-7B-Instruct, Qwen3-4B, and Qwen3-1.7B; AdaStep replaces GiGPO’s fixed coefficient without adding tunable hyperparameters.Qwen3’s built-in thinking mode is disabled throughout training and evaluation.Source: C EXPERIMENTAL DETAILS · p. 18

D PROMPT TEMPLATES

E DETAILS OF THE WEBSHOP STEP-CREDIT ANALYSIS

The WebShop diagnostics compare coefficient rules on historical return samples, separating coefficient fitting from held-out action-level reference evaluation. AdaStep has lower reported aggregate within-action variation and reference MSE than GiGPO, but the reference error is only a proxy.

Offline diagnostics

  • The analysis compares coefficient rules on the same historical return samples across 3,666 WebShop anchor-state groups, without new policy-training runs.The reported aggregate averages over 32 splits within each group, then equally over groups; repeated splits are not independent training seeds.Source: E DETAILS OF THE WEBSHOP STEP-CREDIT… · pp. 20–21

Fit and reference subsets

  • Within each group, action-specific returns are split into disjoint fit and reference halves, repeated 32 times; only fit rows estimate group statistics and the adaptive coefficient.Reference rows supply empirical action-level targets and do not choose the coefficient; no value model or critic is trained.Source: E DETAILS OF THE WEBSHOP STEP-CREDIT… · p. 20

Coefficient rules

  • The four rules scale the step credit by 1 for GiGPO, 0.5 for fixed scaling, 0 for step-off, or the adaptive coefficient for AdaStep.AdaStep's coefficient comes from empirical means, variances, and a scalar ratio, with a fallback of 1 when the fit subset cannot support estimation; it is not optimized against reference MSE.Source: E DETAILS OF THE WEBSHOP STEP-CREDIT… · p. 21

Reference MSE

  • The reference MSE measures agreement with a finite-sample held-out action-level signal, not error against true action values or ground-truth advantages.Lower values indicate closer agreement with that empirical reference, and removing the step component can increase error when reference action advantages are nonzero.Source: E DETAILS OF THE WEBSHOP STEP-CREDIT… · p. 21

Aggregation and interpretation

  • 0.1576 vs 0.0564 for within-action variation and 0.3313 vs 0.2180 for reference MSE, comparing GiGPO with AdaStep, respectively.These are descriptive aggregate values from historical samples, not measures of downstream policy performance.Source: E DETAILS OF THE WEBSHOP STEP-CREDIT… · p. 21

F LIMITATIONS AND FUTURE WORK

AdaStep estimates its adaptive coefficient from return statistics for samples sharing an anchor state, so it depends on constructing step-level state groups across rollouts. The paper leaves suitable grouping for settings without repeated exact states as an open question.

Limitations and future work

  • AdaStep estimates its coefficient from return statistics for samples sharing an anchor state, requiring step-level state groups across multiple rollouts.In the three studied benchmarks, discrete, exactly reproduced states make identical-state matching readily available.Source: F LIMITATIONS AND FUTURE WORK · p. 21
  • In continuous, partially observable, or open-ended environments, states are rarely revisited verbatim, making suitable groups for the variance-ratio estimate an open question.The paper leaves state abstractions or learned grouping criteria that preserve the reliability interpretation of w*(s) to future work.Source: F LIMITATIONS AND FUTURE WORK · p. 21
  • The supported scope is narrower than settings where exact state matches are uncommon; the paper does not establish a suitable grouping method for those settings.Source: F LIMITATIONS AND FUTURE WORK · p. 21
Loading 2610.03223v1…