Multiscale Policy Optimization for Long-Horizon LLM Agents
Large language model (LLM) agents often operate over extended interactions, generating outputs token by token within discrete assistant turns. Optimizing such agents via reinforcement learning (RL) poses a unique challenge: credit assignment must bridge two scales simultaneously—the complete assistant turns that interact with the environment, and the individual tokens generated within each turn. In their recent work, the authors propose a novel approach called Multiscale Policy Optimization (MPO) that explicitly addresses this multiscale credit assignment problem, yielding improved performance across diverse agentic tasks.
The Problem: Credit Assignment Across Turns and Tokens
LLM agents engage in long-horizon tasks by alternating between producing assistant outputs (turns) and receiving environment feedback. Each assistant turn consists of a sequence of tokens generated autoregressively, and the environment only observes the complete turn as an atomic action. The agent receives a terminal reward only at the end of the entire interaction, making credit assignment particularly challenging.
Existing RL methods for LLM agents typically fall into two categories:
- Critic-free group-relative methods (e.g., GRPO, DAPO, GSPO) assign a single shared advantage to entire generated sequences, lacking granularity to distinguish contributions of individual turns or tokens.
- Critic-based token-level methods (e.g., PPO, VC-PPO, VAPO, SAO) estimate advantages at the token level but do not explicitly separate the environment-level interactions (turns) from token generation within turns.
Neither approach fully captures the hierarchical structure of LLM agent interactions, where turns represent macro actions and tokens represent micro actions. The authors observe that critic values tend to be relatively stable within turns but vary significantly across turn boundaries, suggesting that credit assignment should reflect this multiscale structure.
The Proposed Method: Multiscale Policy Optimization (MPO)
MPO combines two key innovations to align policy optimization with the natural scales of LLM agent interactions:
- Multiscale Advantage Estimation (MAE): This method first propagates credit across turns using a turn-level generalized advantage estimation (GAE) to capture long-range dependencies. Then, within each turn, it refines token-level credit assignment by applying a centered local correction that preserves the turn-level mean advantage. This two-stage process balances coarse credit propagation across turns with fine-grained token-level distinctions.
- Turn-Level Importance Sampling: Instead of applying importance weighting at the token level, MPO applies importance correction at the complete-turn level. This aligns the policy update with the environment’s granularity of interaction, reducing distribution-shift penalties that arise when correcting at finer token scales. To retain token-specific credit in the gradient, MPO uses a stop-gradient construction that weights each token’s policy gradient by the complete-turn importance ratio while preserving its own MAE advantage.
The authors provide theoretical analysis showing that token-level surrogates incur an additional within-turn distribution-shift penalty compared to turn-level surrogates under the same KL divergence constraints. MPO’s design mitigates this penalty by anchoring importance correction at the turn scale while maintaining token-level credit distinctions.
Empirical Evidence: Consistent Gains Across Tasks and Models
The authors evaluate MPO on three agentic settings—Search, Claw-Eval, and Automation Bench—using Qwen3-4B-Thinking and Qwen3-30B-A3B-Instruct models. They compare MPO against strong RL baselines including GRPO, GSPO, PPO, VAPO, and SAO.
- Performance Improvements: MPO achieves the highest scores on all nine reported metrics across both model scales. For example, on the Search benchmarks, MPO improves pass@1 accuracy by 3.59 to 4.33 percentage points over the strongest baselines.
- Importance of Turn-Level Importance Sampling: Ablations replacing turn-level importance ratios with token-level ratios reduce performance across all metrics, confirming the benefit of aligning importance correction with the turn scale.
- Training Dynamics: MPO exhibits higher critic explained variance during training compared to PPO, suggesting improved value estimation. Despite lower entropy in token distributions, MPO maintains strong validation performance and benefits from increased sampling at test time.
- Test-Time Scaling: MPO’s advantage persists and even grows with larger numbers of sampling attempts per task, outperforming baselines consistently across multiple benchmarks.
Limitations and Considerations
While MPO shows clear empirical benefits and is supported by theoretical analysis, some limitations and open questions remain:
- Critic Estimation Errors: The authors demonstrate that internal critic errors can potentially reverse update directions at the token level, highlighting the importance of accurate value estimation and the risks of bootstrapping errors within turns.
- Parameter Sensitivity: Ablation studies reveal that hyperparameters controlling credit propagation across turns and tokens (e.g., decay rates and local refinement strength) significantly affect performance, indicating the need for careful tuning.
- Assumptions on Reward and Environment: The analysis assumes terminal rewards and fixed environment dynamics independent of policy parameters, which may not hold in all real-world settings.
- Computational Overhead: Although the authors note that advantage computations scale linearly with trajectory length, the multiscale approach introduces additional complexity compared to simpler token-level methods.
Practical Implications for LLM Agent Training
MPO provides a principled framework for optimizing LLM agents that interact over long horizons with sparse terminal rewards. Its multiscale credit assignment aligns naturally with the hierarchical structure of agent interactions, enabling more stable and effective policy updates.
Practitioners training LLM agents for complex tasks involving multiple environment interactions—such as search, tool use, or automation—may benefit from adopting MPO or similar multiscale approaches. The method’s ability to retain token-level credit distinctions while anchoring importance correction at the turn level can improve learning stability and final task performance.
Moreover, the theoretical insights into the distribution-shift penalties incurred by token-level importance sampling highlight the value of designing RL algorithms that respect the natural granularity of environment interactions.
Summary
The authors introduce Multiscale Policy Optimization (MPO), a novel RL method for long-horizon LLM agents that combines turn-level credit propagation with token-level refinement and aligns importance weighting with complete assistant turns. Supported by theoretical analysis and extensive experiments on multiple benchmarks and model scales, MPO consistently outperforms strong baselines, offering a promising direction for optimizing agentic LLMs in complex environments.
Sources
AI-assisted research summary. Check the original paper for complete methods, results, and limitations.