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
Multiscale Policy Optimization aligns credit assignment and policy updates across both turn-level interactions and token-level generation.
How can we optimize LLM agents that generate actions token-by-token but interact with environments at the turn level?
Long-horizon LLM agents interact through complete turns, but standard reinforcement learning methods either treat the entire sequence as one unit or treat every token as an independent action, failing to capture the distinct credit structure of multi-turn tasks. Multiscale Policy Optimization (MPO) addresses this by propagating credit across turns using boundary values while simultaneously refining token-level credit through a centered local correction that preserves the turn mean. On search and tool-use benchmarks, MPO consistently outperforms strong baselines like PPO and GRPO, with gains that persist as sampling budgets increase.
Paper Primer
Agentic tasks require connecting a final terminal reward to a long sequence of assistant turns. Standard methods struggle because they either ignore the internal structure of a turn (group-relative methods) or fail to distinguish between turn-level environment interactions and token-level generation (token-level methods).
MPO is a multiscale policy optimization framework: it uses turn-level advantage estimation to propagate long-range credit and a centered local trace to allocate credit within each turn. The core move is a constrained projection that fixes the mean token credit to the turn-level estimate while preserving relative token differences, combined with turn-level importance weighting that retains token-specific gradients.
MPO achieves consistent performance gains over strong RL baselines across search, tool-use, and automation tasks.
Evaluations on BrowseComp-Plus, GAIA, and HLE benchmarks using 4B and 30B-A3B models. Improvements of up to 5.90 points in pass@3 on GAIA and 4.33 points in pass@1 on BrowseComp-Plus.
The authors demonstrate that aligning importance correction with complete turns—rather than individual tokens—is critical. Replacing turn-level importance ratios with token-level ratios consistently reduces performance across all tested benchmarks.
Why does the paper argue that token-level surrogates are suboptimal for agentic tasks?
Token-level surrogates introduce an additional within-turn distribution-shift penalty because they evaluate credit using old-policy prefixes, whereas the macro-turn surrogate correctly accounts for the complete interaction.
What is the role of the "centered local correction" in the advantage estimation?
It ensures that while the model refines credit for individual tokens, the average credit for all tokens within a turn remains anchored to the turn-level advantage, preventing the local refinement from distorting the shared task-level credit.
Motivation: The Turn-Level Structure of Agents
We expose the mismatch between turn-level interactions and token-level RL, motivating multiscale credit assignment.
LLM agents act in whole assistant turns—search queries, tool calls, or final replies—while standard RL treats each generated token as an independent action. Empirically, critic values are stable within a turn but shift sharply at turn boundaries, accounting for the majority of variance (median 89.5% of token‑weighted variance, and between‑turn variance dominates in 93.8% of trajectories). This mismatch motivates a policy‑optimization approach that anchors credit at the turn level and refines it among tokens.
The agent’s environment feedback changes mainly when a whole turn finishes, not after each token.
**Figure 2.** Critic values exhibit structure at the turn scale. A failed trajectory (a) and a successful trajectory (b) both exhibit relatively stable values within turns and pronounced changes across turn boundaries.
**Figure 7. Critic-value structure across turns.** (a) Within-turn (horizontal) versus between-turn (vertical) RMS deviations, weighted by token count. Each point is a trajectory; the dashed line marks equality. (b) Median between-turn variance share versus training step, with token weighting (blue) and equal turn weighting (green). Error bars are 95% prompt-cluster bootstrap intervals within each checkpoint. (c) Cumulative distributions of per-trajectory mean absolute boundary jumps (orange) and mean within-turn P95–P05 spans (green). (d) Shares of pooled squared adjacent value changes at turn boundaries (orange) and within turns (pale green), by training step.
**Figure 8.** More examples of critic-value structure across turns. Blue curves show raw token values, dashed lines show turn means, and orange segments mark changes between successive turns. As in Figure 2, turns have equal display width and curves are unsmoothed; only assistant-action positions are included, with no appended terminal zero.
Critic values are stable within turns but shift between turns.
Related Work
We situate our work among prior tool‑using agents and RL approaches for LLMs.
Early research linked language models to external tools, enabling reflection, memory, planning, and multi‑agent collaboration over many turns. Modern coding agents further integrate repository editing, execution, testing, and browsing, motivating optimization across whole turns and the tokens they contain.
GRPO extends policy optimization to large‑scale language models by treating the entire assistant turn as the decision unit.
PPO performs stable policy updates by clipping the probability ratio between the new and old policies.
Turns as Macro Decisions
Defines macro actions and derives turn‑ vs token‑level improvement bounds.
Treating each token as an independent action ignores that the environment only observes complete assistant turns, which leads to inefficient credit assignment and noisy gradients.
A macro action is the entire assistant turn— all tokens generated until the turn ends—treated as a single decision for the environment.
How does a macro action differ from a token‑level action?
A token‑level action is a single generated token $a_{t,i}$; a macro action $a_t$ bundles all tokens of a turn, including the stop decision, so the environment sees only $a_t$ as the atomic interaction.
These identities let us relate turn‑level and token‑level surrogates while keeping a single policy $\pi_{\theta}$.
Lemma 1 shows that, under lossless token refinement and $\gamma\!=\!1$, the turn‑ and token‑level objectives coincide, and their gradients match as in (7).
Lemma 2 rewrites the performance difference between two policies as an expectation of the old‑policy advantage weighted by the new‑policy distribution.
Defining the turn‑level surrogate $S_M$ using the complete‑turn importance ratio $\rho_t$ yields a tractable improvement estimate.
Theorem 1 proves that if the total‑variation distance between $\pi'$ and $\pi$ is bounded by $\alpha_M$, then $J(\pi') - J(\pi) \ge S_M - 2 A_{\max} T (T\!+\!1) \alpha_M^{2}$, guaranteeing monotonic improvement.
When we replace the turn surrogate with token‑level terms, the importance ratio factorizes as $\rho_t = \prod_i \rho_{t,i}$, introducing an additional distribution‑shift penalty.
Multiscale Policy Optimization
MPO propagates turn‑level credit then refines token‑level advantages while preserving the turn mean.
MPO unifies turn‑level credit propagation with token‑level refinement, letting RL respect the natural turn structure of LLM agents. Figure 1 visualizes the three stages of the method.
**Figure 1.** Overview of Multiscale Policy Optimization (MPO). Agents interact through complete assistant turns while generating actions token by token. MAE refines shared turn advantages into token-level credit while preserving each turn's mean. The policy update combines a shared complete-turn importance ratio with token-specific gradients. Top right: validation pass@1 during 4B training.
MAE starts from a shared turn advantage and nudges each token’s advantage so the average stays equal to the turn value while the relative ordering from the intra‑turn signal is kept.
Compute the mean of the intra‑turn vector: $\frac{1.5+2.5+0.5}{3}=1.5$.
Center each entry: $[1.5-1.5,\,2.5-1.5,\,0.5-1.5]=[0.0,\,1.0,\,-1.0]$.
Add the turn mean: $A^{\text{MAE}}_{t,i}=2.0 + [0.0,\,1.0,\,-1.0]=[2.0,\,3.0,\,1.0]$.
Centering forces the token advantages to sum to $3\times2.0=6.0$, preserving the turn‑level credit while still differentiating tokens.
How does MAE differ from applying standard GAE independently to each token?
Standard GAE would give each token its own advantage, which can shift the average away from the turn‑level credit. MAE first fixes the mean to the turn advantage and only adjusts deviations, so the total credit matches the turn estimate while still capturing token‑specific signals.
For every token $(t,i)$ compute the TD residual $\delta_{t,i}=r_{t,i}+V_{t,i+1}-V_{t,i}$ using the fixed critic $V_{t,i}=V(h_{t,i})$.
Sum the residuals within each turn: $\delta^{\text{turn}}_{t}= \sum_{i=1}^{L_t}\delta_{t,i}$.
Apply GAE on the macro time axis (turns) to obtain the turn‑level advantage $A^{\text{turn}}_{t}$.
Compute the intra‑turn trace $A^{\text{intra}}_{t,i}= \sum_{j=i}^{L_t}\lambda^{\,j-i}\,\delta_{t,j}$ for each token $i$.
Solve the least‑squares projection that enforces $\frac{1}{L_t}\sum_i w_i = A^{\text{turn}}_{t}$ while keeping $w$ close to $\beta A^{\text{intra}}_{t}$.
Obtain the final token advantage $A^{\text{MAE}}_{t,i}$ by centering the scaled intra‑turn vector around the turn mean (see the MAE formula).
Compute token‑wise importance ratios $\rho_{t,i}(\theta)=\frac{\pi_\theta(a_{t,i}\mid h_{t,i})}{\pi(a_{t,i}\mid h_{t,i})}$.
Form the complete‑turn ratio $\rho_t(\theta)=\sum_{i=1}^{L_t}\rho_{t,i}(\theta)$.
Apply a stop‑gradient to the product of all other token ratios so that each token keeps the full turn weight in the forward pass but only its own gradient contributes.
Define the MPO surrogate loss $L_{\text{MPO}}(\theta)$ using the clipped importance ratio and the MAE token advantages.
Experimental Results
MPO outperforms baselines across benchmarks, showing consistent gains at both model scales.
LLM agents act in whole turns, yet standard RL treats each token as an independent action. MPO aligns advantage estimation at the turn level while refining credit at the token level, bridging this gap.
MPO leads on all nine evaluation metrics for both the 4B and 30B model families.
Table 1 shows MPO attaining the highest score in every column compared with Base, GRPO, GSPO, PPO, VAPO, SAO, and MPO w/ token IS.
MPO consistently outperforms GRPO and PPO across agentic benchmarks.
**Evaluation protocol.** For the trained-model results in all tables, we select the best-performing checkpoint from each training run. We evaluate the selected checkpoint offline five times and report the mean of the five evaluation scores. The benchmark-specific rollout budgets and metrics described below apply to each evaluation repetition. For BrowseComp-Plus, we follow the held-out evaluation setup of Lu et al. [17]. For GAIA and HLE, we use WebThinker's text-only evaluation subsets, drawn from their validation and test sets, respectively [15]. Base results use three rollouts per task. For trained Search models, pass@1 and pass@3 are estimated from a pool of 32 independent rollouts per task, using the same samples across evaluation budgets. We follow the original evaluation protocols for Claw-Eval [43] and Automation Bench [32]. Claw-Eval uses three independent trials, reporting pass@3 for success in at least one trial and pass^3 for success in all three. Automation Bench reports pass@1 using its end-state assertion checks. All score differences below are percentage points.
**Figure 4.** Training dynamics of GRPO, PPO, and MPO on 4B through step 600, showing entropy, reward, validation pass@1, response length, explained variance, and number of turns.
**Figure 3.** 4B validation pass@1 (left) and training reward (right) through step 300.
**Figure 5.** Training dynamics of GRPO, PPO, and MPO on 30A3B through step 300, using the same metrics as Figure 4.
**Figure 6.** Test-time scaling of GRPO, PPO, and MPO on BrowseComp-Plus, GAIA, and HLE for 4B and 30A3B, showing pass@k as the number of attempts increases.
**Table 3.** Search ablation over local refinement strength. Scores are percentages. The bold setting reproduces 4B MPO from Table 1. We vary $\beta$ with $\lambda = 0.80$ and $\lambda_{intra} = 0.95$ fixed.
**Table.** Ablation study results for varying $\beta$ on BrowseComp-Plus, GAIA, and HLE benchmarks, reporting pass@1 and pass@3 metrics.
Theoretical Guarantees
Formal proofs of the policy‑improvement guarantees and related lemmas.
This appendix supplies the rigorous derivations for the lemmas and theorems that underpin the turn‑level policy‑improvement analysis.
Token‑level and macro‑level descriptions induce identical trajectory probabilities and therefore assign the same expected return to any complete interaction $\tau$.
Factorizing the joint probability of a trajectory into turn‑level components yields the same product as factorizing into token‑level components.
The log‑likelihood sums are equal for a fixed trajectory.
With $\gamma=1$ and identical reward and stopping rules, the expected returns are equal.
The policy‑difference lemma holds with an importance‑ratio representation: $J(\pi')-J(\pi)=\sum_{t=0}^{T}\mathbb{E}_{d_{\pi'}^{t},\pi'}[A_{\pi}^{t}]$, and replacing $d_{\pi'}^{t}$ by the surrogate $S_{M}$ yields the same expression up to absolute‑continuity assumptions.
Define the one‑turn temporal difference $\delta_{\pi}^{t}= \sum_{i=1}^{L_{t}} r_{t,i}+V_{\pi}^{t+1}(h_{t+1})-V_{\pi}^{t}(h_{t})$.
Taking expectation under $\pi'$ and conditioning on $(h_{t},a_{t})$ gives $\mathbb{E}_{\pi'}[\delta_{\pi}^{t}\mid h_{t},a_{t}]=A_{\pi}^{t}(h_{t},a_{t})$.
Summing $\delta_{\pi}^{t}$ over $t$ telescopes to $R(\tau)-V_{\pi}^{0}(h_{0})$.
Taking expectations under a trajectory sampled from $\pi'$ yields the PDL identity.
Replacing $d_{\pi'}^{t}$ by the surrogate $S_{M}$ introduces only the importance‑ratio term because of absolute continuity.
For turn‑level policies $\pi$ and $\pi'$, if $\alpha_{M}=\max_{h,a}\|\pi'(a\mid h)-\pi(a\mid h)\|_{1}/2$, then $|J(\pi')-J(\pi)-S_{M}|\le A_{\max}T(T+1)\alpha_{M}^{2}$, where $A_{\max}$ bounds the per‑turn advantage.
Bound the total‑variation distance between successive turn‑start occupancy measures.
Induction gives $D_{\text{TV}}(d_{\pi'}^{t},d_{\pi}^{t})\le t\,\alpha_{M}$.
The mean old‑policy advantage under $\pi'$ is bounded by $2A_{\max}\alpha_{M}$.
Combine the bounds to obtain $|J(\pi')-J(\pi)-S_{M}|\le 2A_{\max}\alpha_{M}\sum_{t=0}^{T}t\alpha_{M}=A_{\max}T(T+1)\alpha_{M}^{2}$.
Within a turn, the surrogate shift error is bounded by $2A_{\text{tok}}^{\max}\alpha_{T}\sum_{i=1}^{L_{\max}}i$, leading to an overall bound of $A_{\text{tok}}^{\max}L_{\max}(L_{\max}+1)\alpha_{T}^{2}$ for the KL‑converted surrogate.
Define the token‑level value $V_{\pi,\text{tok}}(x)=\mathbb{E}_{\pi}[R(\tau)\mid h_{t},i=x]$ and the token advantage $A_{\pi,\text{tok}}^{t,i}(h_{t,i},a_{t,i})=V_{\pi,\text{tok}}(h_{t,i+1})-V_{\pi,\text{tok}}(h_{t,i})$.
Bound the total‑variation distance between conditional token‑prefix occupancies: $D_{\text{TV}}(d_{\pi'}^{t,i+1}(\cdot\mid h),d_{\pi}^{t,i+1}(\cdot\mid h))\le (i-1)\alpha_{T}$.
The mean token advantage under $\pi'$ satisfies $\mathbb{E}_{a\sim\pi'}[A_{\pi,\text{tok}}^{t,i}(x,a)]\le 2A_{\text{tok}}^{\max}\alpha_{T}$.
Summing over token positions yields the surrogate shift bound $|J(\pi')-J(\pi)-S_{M}|\le A_{\text{tok}}^{\max}L_{\max}(L_{\max}+1)\alpha_{T}^{2}$.
Arbitrary Estimators
Analyzes arbitrary macro estimators and derives robust policy‑improvement bounds.
This section formalizes how arbitrary macro‑level estimators and action‑independent baselines fit into the policy‑improvement analysis.
Boundary Critic and Token GAE
Introduce the Boundary Critic and Token GAE mechanisms that align turn‑level and token‑level credit.
Standard RL treats every generated token as an independent action, which misallocates credit across the multi‑turn interaction that LLM agents actually perform.
The Boundary Critic measures the mismatch between the turn‑level value estimate and the value at the first token of that turn, anchoring advantage estimation to the turn boundary.
Compute $e_0 = 5 - 4 = 1$.
Compute $e_1 = 3 - 3.5 = -0.5$.
The absolute errors are $|e_0|=1$ and $|e_1|=0.5$, both ≤ $\epsilon_B=1$.
With $\lambda=0.9$, the bound $\epsilon_B(1-\lambda^{\,T-t})$ gives $0.1$ for $t=1$ and $0.19$ for $t=0$.
The Boundary Critic isolates turn‑boundary mismatch, allowing the turn‑level GAE to inherit a provably shrinking error as the horizon recedes.
How does the Boundary Critic differ from a standard per‑token TD error?
A per‑token TD error compares successive token values within a turn, while the Boundary Critic compares the turn‑level value to the value at the turn’s first token, thus linking turn‑level and token‑level critics.
Corollary 1 shows that if the boundary error is uniformly bounded by $\epsilon_B$, the turn‑level GAE error decays as $\epsilon_B(1-\lambda^{\,T-t})$, yielding the policy‑improvement bound (42‑43).
Token GAE propagates advantage across every assistant token, accumulating TD residuals with decay $\lambda$ while respecting the turn‑level baseline.
Compute $\text{GAE}_3 = \delta_3 = 0.5$ (no future token).
Compute $\text{GAE}_2 = \delta_2 + 0.9 \times 0.5 = -1 + 0.45 = -0.55$.
Compute $\text{GAE}_1 = \delta_1 + 0.9 \times (-0.55) = 2 - 0.495 = 1.505$.
The final token‑level advantage vector is $(1.505,\,-0.55,\,0.5)$.
Token GAE spreads credit from later tokens back to earlier ones, with the decay factor controlling how far the influence reaches.
Why not apply the turn‑level GAE directly to each token instead of using Token GAE?
Turn‑level GAE yields a single advantage per turn, discarding intra‑turn temporal structure; Token GAE preserves that structure by propagating residuals across tokens, enabling finer‑grained credit assignment.
Proposition 1 derives an analogous error bound for Token GAE: with bounded token error $\epsilon_T$ and decay $q$, the bias decays as $\epsilon_T(1-q^{\,N-j})$, leading to the performance guarantee (48‑49).
Ablation Studies
Ablations test how removing macro or token components affects performance under a shared KL budget.
The paper’s central premise is that MPO anchors advantage estimation at the turn level while refining credit at the token level, enabling coherent credit assignment across long interactions.
**Figure 9.** Local refinement strength $\beta$: 0.0 (left) and 2.0 (right), compared with the MPO reference.
**Figure 10.** Cross-turn propagation $\lambda$: 0.60 (left) and 0.85 (right), compared with the MPO reference.
**Figure 11.** Within-turn trace $\lambda_{intra}$: 0.90 (left) and 1.00 (right), compared with the MPO reference.
Internal critic error can reverse the update direction, causing the surrogate advantage to increase while the true return decreases.
With $c=0.05$, $\varepsilon=0.2$, $q=0.8$, $L=4$, and a policy shift $u=-0.1$, the surrogate gain is $+0.00952$ whereas the actual return change is $-0.01$.