PaperlayerView exact revision on arXiv

Source-linked AI summary

Multiscale Policy Optimization for Long-Horizon LLM Agents

Tao Ren, Hui Yang, Jia Deng, Tingyang Chen, Qiyao Wang, Shuo Tang, Ziyang Zeng, Yuhua Jiang, Guanghao Li, Huatong Song, Yining Li, Yifan Luo, Kunbao Ding, Feng Chang, Chuan Hao, Ran Tao, Bryan Dai, Jiafeng Liang, Jinyang Jiang

arXiv:2610.35013v1cs.AI

TL;DR

Long-horizon LLM agents act through complete turns but generate each output token by token, leaving credit assignment and policy updates to span both scales. MPO combines cross-turn advantage propagation, local token credit, and turn-level importance weighting; experiments report consistent gains over strong RL baselines across search, tool-use, and automation tasks.

  • Problem

    Common group-relative methods share one advantage across a generated sequence, while token-level critic methods do not explicitly separate within-turn generation from turn-level interaction.

    Source: §1 · p. 2

  • Method

    MPO combines turn-level GAE with a mean-preserving local token-credit correction and turn-level importance weighting that retains token-specific advantages in policy gradients.

    Source: §1 · p. 3, §7 · p. 14

  • Results

    MPO reports consistent gains over strong RL baselines across search, tool-use, and automation tasks at 4B and 30B-A3B model scales.

    Source: §1 · p. 3, §6.2 · p. 10

  • Takeaways & Limitations

    The findings motivate using both interaction-turn and token-generation scales when optimizing long-horizon LLM agents.

    Source: §7 · p. 14

    The theoretical analysis assumes a fixed turn horizon of T + 1.

    Source: §3.2 · p. 5

Abstract

from arXiv · show

Long-horizon LLM agents interact with their environments through complete assistant turns while generating each action token by token. We observe that critic values vary primarily across turns, motivating optimization anchored at turns with finer credit allocation among tokens. We propose Multiscale Policy Optimization (MPO), combining Multiscale Advantage Estimation (MAE) and turn-level importance sampling to align credit assignment and policy updates at the turn scale. Extensive experiments across search, tool-use, and automation tasks with 4B and 30B-A3B models demonstrate consistent gains over strong RL baselines.

1. Introduction

Long-horizon agents generate token-by-token outputs but interact through complete turns, so optimization must assign credit and update policies at both scales. MPO combines turn-level credit propagation and importance weighting with token-specific credit, addressing the gap between common RL approaches.

1. Introduction

  • Agentic RL needs credit that captures both each complete interaction’s contribution and the relative contributions of tokens within it.Group-relative methods use one shared sequence advantage, while token-level critic methods do not explicitly separate token generation from turn-level interaction.Source: §1 · p. 2
  • Across 2,048 trajectories and 16,323 turns, between-turn variance exceeded within-turn variance in 93.8% of trajectories.Differences between turn means accounted for a median 89.5% of token-weighted within-trajectory value variance in one search-agent run.Source: §1 · p. 2
  • MPO combines multiscale credit assignment with turn-level importance weighting, preserving token-specific credit while aligning optimization with complete interactions.MAE propagates credit across turns, then applies a centered local correction that preserves the turn mean.Source: §1 · p. 3
  • The paper analyzes policy improvement at turn and token scales and identifies an additional within-turn distribution-shift discrepancy for token-level surrogates.Its experiments report consistent gains over strong RL baselines across search, tool-use, and automation tasks with 4B and 30B-A3B models.Source: §1 · p. 3

2. Related Work

Prior work developed multi-turn agents through tools, memory, planning, and feedback, while RL posttraining methods address policy optimization and credit assignment. MPO builds on these lines by aligning advantage estimation and importance correction with complete turns while retaining token-level credit.

2.1. Tool use and multi-turn agent learning

  • Tool-using and coding agents combine interaction, execution feedback, and accumulated experience across practical tasks.Earlier agent work also developed reflection, memory, planning, reusable skills, and multi-agent collaboration.Source: §2.1 · p. 3

2.2. RL in LLM Posttraining

  • RL posttraining spans policy-gradient and trust-region methods, group-relative optimization, critic learning, exploration objectives, and multi-turn agent training.MPO aligns advantage estimation and importance correction with complete turns while retaining centered token-level credit within each turn.Source: §2.2 · pp. 3–4

3. Agentic RL Across Turns and Tokens

The paper models terminal-reward agent tasks as trajectories of assistant outputs and environment observations, with each output generated autoregressively. Treating complete outputs as macro actions preserves the task objective while distinguishing interaction turns from their constituent tokens.

3.1. Agentic RL with Terminal Reward

  • The agent alternates assistant outputs and environment observations, receives a single terminal reward, and has no intermediate rewards.The assistant output is a token sequence, and only the final assistant token of the trajectory receives the terminal reward.Source: §3.1 · p. 4

3.2. Turns as Macro Decisions

  • The paper treats each complete assistant output as a macro action because the environment does not interact between tokens within that output.Under lossless token refinement, identical reward and stopping rules, and γ = 1, the macro and token descriptions have the same task return.Source: §3.2 · pp. 4–5
  • The theoretical comparison assumes a fixed horizon of T + 1 turns.The assistant policy factorizes autoregressively over tokens, while complete-turn probabilities are induced by those token probabilities.Source: §3.1 · p. 4, §3.2 · p. 5

4. Policy Improvement Across Turns and Tokens

The analysis compares turn- and token-level policy surrogates for the same task-return objective. It establishes a turn-level improvement bound and identifies an additional within-turn distribution-shift penalty for token surrogates under the same KL constraints.

4. Policy Improvement Across Turns and Tokens

  • The analysis compares turn- and token-level surrogates for the same task-return objective and motivates combining multiscale credit with turn-level importance weighting.The paper follows a surrogate-and-distribution-shift analysis of TRPO [27].Source: §4 · p. 5

4.1. Turn-Level Policy Improvement

  • A turn-level surrogate certifies improvement when its exact gain covers the distribution-shift penalty.The surrogate pairs turn-level advantage with a complete-output importance ratio.Source: §4.1 · p. 6

4.2. Additional Cost of Token Surrogates

  • Under the same KL constraints, token-surrogate improvement bounds incur an additional within-turn distribution-shift penalty relative to turn-surrogate bounds.The paper attributes the discrepancy to averaging token advantages over old-policy rather than new-policy prefixes; its stated penalty is (T + 1)(Lmax − 1)Δ for the specified KL setting.Source: §4.2 · p. 7

5. Multiscale Policy Optimization

MPO combines multiscale credit assignment with turn-level importance weighting: it propagates credit across turns, refines token credit within turns, and preserves token-specific credit in the policy gradient.

5. Multiscale Policy Optimization

  • MPO combines Multiscale Advantage Estimation with complete-turn importance weighting to propagate credit across turns, refine it within turns, and retain token-specific credit in policy gradients.Source: §5 · p. 7, §5.3 · p. 9

5.1. Turn-Level Credit Propagation

  • Turn-level GAE propagates shared credit across interactions, decaying once per turn rather than per token and remaining independent of turn lengths and internal critic predictions for fixed rewards and boundary values.Source: §5.1 · pp. 7–8

5.2. Within-Turn Credit Allocation

  • Within-turn allocation preserves the turn estimate as the mean token credit while retaining relative differences in local estimates through a least-squares projection.Setting β=0 recovers turn broadcasting.Source: §5.2 · p. 8

5.3. Turn-Level Importance Correction

  • Stop-gradient correction gives each token the complete-turn ratio for forward weighting and clipping while its own MAE advantage determines its score gradient.Source: §5.3 · p. 9

6. Experiments

Across search, tool-use, and automation evaluations, MPO outperforms strong RL baselines at both model sizes. Training dynamics, test-time scaling, and ablations examine its behavior and the contributions of its design choices.

6.1. Experimental Settings

  • Experiments use Qwen3-4B-Thinking and Qwen3-30B-A3B-Instruct across Search, Claw-Eval, and Automation Bench, averaging five offline evaluations of each selected best checkpoint.Comparisons include Base, GRPO, GSPO, PPO, VAPO, and SAO.Source: §6.1 · pp. 9–10

6.2. Main Results

  • MPO leads all nine metrics at both scales; Search pass@1 gains over the strongest baselines are BrowseComp-Plus/GAIA/HLE: 4B +4.33/+3.85/+0.66 points, 30A3B +3.59/+3.80/+0.12.MPO also improves both Claw-Eval metrics and Automation Bench performance.Source: Table 1 · p. 10, §6.2 · p. 10

6.3. Training Dynamics

  • With the same terminal-return critic target (λcritic = 1), MPO has higher average late-training explained variance at both scales, but on-policy rollouts and return variance prevent isolating critic accuracy.Each method has one run per model size; Figure 4 tracks entropy, reward, validation pass@1, response length, explained variance, and turns for 4B.Source: Figure 4 · p. 11, §6.3 · p. 12

6.4. Test-Time Scaling

  • On 4B, MPO leads GRPO and PPO at every evaluated k across all three search benchmarks; its pass@32 gains are 3.61, 5.82, and 5.80 points on BrowseComp-Plus, GAIA, and HLE.MPO's pass@32 scores are 75.90, 69.90, and 34.00, respectively.Source: §6.4 · p. 12, Figure 6 · p. 13

6.5. Ablation Studies

  • Turn-scale λ = 0.80 performs best among tested values; moving to 0.85 or 0.60 reduces performance, favoring a balance in cross-turn credit propagation.At λ = 0.85, pass@1 falls by 1.72, 2.21, and 1.05 points on BrowseComp-Plus, GAIA, and HLE, respectively.Source: §6.5 · pp. 13–14
  • Within-turn λintra = 0.95 performs best across all six metrics; both shorter and longer tested traces reduce scores, supporting separate propagation ranges for turns and tokens.The nominal trace lengths are five turns for λ = 0.80 and twenty tokens for λintra = 0.95.Source: §6.5 · p. 14
  • Setting β = 0 removes token-level allocation and still beats PPO on all six Search metrics, but reduces scores versus full MPO; β = 1.00 performs best in the sweep.Increasing β to 1.50 and then 2.00 progressively reduces pass@1 and pass@3 across all three benchmarks.Source: §6.5 · p. 14

7. Conclusion

MPO organizes LLM-agent policy optimization across turns and tokens, combining cross-turn credit propagation with mean-preserving local allocation. The analyses and experiments motivate using both scales when optimizing long-horizon agents.

7. Conclusion

  • MAE combines cross-turn credit propagation with mean-preserving local allocation, while the update pairs complete-turn importance correction with token-specific gradients.The conclusion presents these choices as distinct credit horizons for interaction and generation.Source: §7 · p. 14

A.1. Objective Consistency and the Macro PDL

  • Token and macro descriptions induce the same trajectory law and expected task returns under γ = 1, unchanged rewards, and the same stopping rule.The proof also establishes the performance-difference identity without replacing new-policy state distributions with old-policy ones.Source: §A.1 · pp. 21–22

A.2. Turn-Level Policy Improvement

  • The turn-level theorem’s condition is sufficient for improvement, but it is not necessary.At T = 0 the occupancy-measure remainder is zero; when α_M = 0, both the surrogate gain and remainder are zero.Source: §A.2 · p. 24

A.3. Within-Turn Surrogate Shift and KL Conversion

  • For δ = Δ/L, the last penalty is (T + 1)(L − 1)Δ; when R ∈ [0, 1], all exact remaining-return values lie in [0, 1].Source: §A.3 · p. 27

A.4. Arbitrary Estimators and Action-Independent Baselines

  • With a common estimator-error bound ε_A, the estimation penalty is 2(T + 1)α_M ε_A.The result applies to the estimator-robust policy-improvement theorem.Source: §A.4 · p. 27

A.5. Boundary Critic Error and the Turn-Credit Guarantee

Turn-level GAE’s error guarantee assumes true termination and bounded boundary critic error; token GAE instead faces errors at internal prefixes as well as within-turn distribution shift.

A.5. Boundary Critic Error and the Turn-Credit Guarantee

  • For rollouts reaching true termination (e_{T+1}=0), with λ∈[0,1] and |e_t(h)|≤ε_B, the turn-level GAE bound is at most 2(T+1)α_M ε_B(1−λ^T).Source: §A.5 · pp. 28–29
  • Without true termination, the terminal boundary error must be retained unless its bootstrap error is separately controlled.The cancellation of e_(T+1) in the guarantee relies on true termination.Source: §A.5 · p. 29

A.6. Token GAE and Internal Critic Error

  • Token GAE decays credit at each assistant token; environment tokens add neither TD residuals nor decay steps.At λ = 1, the value differences telescope.Source: §A.6 · p. 29
  • Token-GAE bias cannot serve as scalar macro bias; its bound includes within-turn distribution shift and errors at internal prefixes.The comparison setup freezes critic predictions during the policy update.Source: §A.6 · pp. 30–31

A.7. Matched-Budget Comparison and an Internal-Error Example

The matched-budget analysis compares macro- and token-level improvement bounds, while an internal-error example shows how bootstrapping at token prefixes can reverse a surrogate’s direction. The appendix also distinguishes local gradient agreement between macro and broadcast-ratio objectives from finite-update equivalence.

A.7. Matched-Budget Comparison and an Internal-Error Example

  • Under a common token KL cap and rewards in [0, 1], Corollary 2 gives matched-budget improvement bounds with macro- and token-level penalty envelopes.With a common positive critic-error cap and matched boundary decay q^L=λ for L>1, the estimation-term comparison is strict; at q=λ=1 both estimation terms vanish.Source: §A.7 · p. 31, This also exceeds · p. 31

This also exceeds

  • With internal critic error, the token surrogate can favor a lower-reward action while the macro surrogate favors the higher-reward action, even for arbitrarily small updates.The example uses 𝑐=0.05, 𝜀=0.2, 𝑞=0.8, and 𝐿=4; the difference comes from bootstrapping at internal prefixes.Source: This also exceeds · p. 32

A.8. Macro and Token Ratio Objectives

  • Broadcast-ratio and macro objectives have equal gradients at the old policy under the stated frozen-estimate and regularity conditions, but can differ at finite updates.In the two-sign example, the token objective is 0 while the macro objective is 4uv; PPO clipping changes the objective and does not impose a hard macro trust region.Source: §A.8 · pp. 32–33

B. Implementation and Ablation Settings

The implementation uses multiscale traces and Monte Carlo critic targets, with specified normalization and reference hyperparameters. Ablations vary one parameter at a time and use one training run per setting with repeated offline checkpoint evaluation.

B. Implementation and Ablation Settings

  • Claw and Automation use proprietary internal training datasets whose details are undisclosed, while BCP follows SUPO’s training-data setup.Table 4 lists RL hyperparameters for BCP, Claw, and Automation, with BCP settings shared by the 4B and 30B-A3B runs.Source: B. Implementation and Ablation Settings · p. 33, Table 4 · p. 33
  • The turn anchor broadcasts the turn-start value and uses a token GAE scan with internal decay 1 and λ at the final token; the local branch uses original token values.The traces and turn reductions take linear time in stored trajectory length.Source: B. Implementation and Ablation Settings · pp. 33–34
  • The critic regresses the final Monte Carlo return at every valid assistant token, while advantage normalization uses the batch mean and sample variance plus 10^-8.Masked positions are zeroed, and batches with at most one valid action receive zero policy advantages.Source: B. Implementation and Ablation Settings · p. 34
  • The reference configuration uses λ=0.8, λ_intra=0.95, λ_critic=1, and β=1, with dense token-level KL rewards excluded.It also uses γ=1, an explicit assistant action mask, and terminal reward placement in Eq. (4).Source: B. Implementation and Ablation Settings · p. 34
  • Each 4B Search ablation varies one parameter around (λ, λ_intra, β)=(0.80, 0.95, 1.00), using one training run and five repeated offline evaluations of its best checkpoint.At β=0, only turn-level GAE remains, so λ_intra has no effect on actor credit.Source: B. Implementation and Ablation Settings · p. 34

C. Critic Values Across Turns

Across the analyzed search-agent trajectories, critic-value variance is primarily between turns, although local token variation remains relevant. Additional examples show pronounced critic-value changes at multiple turn boundaries.

C. Critic Values Across Turns

  • Turn boundaries exceed within-turn spans in only 22.4% of trajectories, and account for 9.2% of pooled squared adjacent value changes.Small within-turn fluctuations accumulate across more tokens, so turn-level differences do not mean most local value movement occurs at boundaries.Source: C. Critic Values Across Turns · p. 35
  • Between-turn differences explain a median 89.5% of token-weighted within-trajectory value variance, and between-turn variance exceeds within-turn variance in 93.8% of trajectories.The median share is 90.2% with equal turn weighting, so the pattern is not solely driven by turn-length differences.Source: C. Critic Values Across Turns · p. 34, Figure 7 · p. 35

C.1. More Examples

  • Figure 8 adds six trajectories with pronounced critic-value changes at multiple turn boundaries.The examples complement Figure 2; turns are shown at equal display width with unsmoothed assistant-action values.Source: §C.1 · p. 36, Figure 8 · p. 36

D. Validation Curves for Parameter Ablations

Figures 9–11 compare the 4B BrowseComp-Plus validation pass@1 curves through training step 300 for the MPO reference and one-parameter ablations. The supplied descriptions identify the varied parameters and reference settings but do not report curve outcomes.

D. Validation Curves for Parameter Ablations

Related papers

Loading 2610.35013v1…