Organizations: Peking University · IQuest Research · Tsinghua University · Renmin University of China · Independent Researcher · The University of Hong Kong
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.
Figures & tables
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.
BrowseComp-Plus
GAIA
HLE
Claw-Eval
Automation Bench
Method
pass@1
pass@3
pass@1
pass@3
pass@1
pass@3
pass@3
pass 3
pass@1
Qwen3-4B-Thinking
Base
8.84
18.07
24.92
33.98
5.53
9.60
25.22
8.09
0.00
GRPO
39.34
52.12
33.92
44.63
8.51
14.43
64.45
48.79
4.33
GSPO
38.56
52.11
34.34
45.26
9.26
13.71
63.83
49.35
5.22
PPO
40.85
54.30
31.71
45.03
7.22
12.82
63.25
50.78
11.67
Table 1: Main evaluation on search and agent tasks. Search benchmarks report pass@1 and pass@3; Claw-Eval reports pass@3 and pass 3 . Automation Bench reports pass@1. Search and Claw-Eval scores are percentages; higher is better for all metrics. Base denotes the initial checkpoint before task-specific RL. Trained-model Search pass@1 and pass@3 are estimated using 32 rollouts per task.
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 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.
Setting
BrowseComp-Plus
GAIA
HLE
(λ,λintra)
pass@1
pass@3
pass@1
pass@3
pass@1
pass@3
(0.80, 0.95)
48.08
61.83
39.47
52.67
9.92
16.78
(0.60, 0.95)
47.51
59.22
38.92
50.79
9.11
15.17
(0.85, 0.95)
46.36
58.91
37.26
51.04
8.87
14.89
(0.80, 0.90)
46.25
57.81
37.92
50.35
8.15
15.22
(0.80, 1.00)
47.67
59.18
38.23
50.95
8.43
16.16
Table 2: Search ablation over turn-scale propagation and within-turn trace. Scores are percentages. The bold setting reproduces 4B MPO from Table 1 . We vary (λ,λintra) with β=1.00 fixed.
Setting
BrowseComp-Plus
GAIA
HLE
β
pass@1
pass@3
pass@1
pass@3
pass@1
pass@3
0.0
41.80
56.77
34.20
48.90
7.88
12.96
0.5
44.13
58.10
37.24
51.85
8.26
13.22
1.0
48.08
61.83
39.47
52.67
9.92
16.78
1.5
46.23
60.35
38.26
51.26
8.93
16.23
2.0
45.14
59.75
37.05
50.01
8.11
15.43
Table 3: Search ablation over local refinement strength. Scores are percentages. The bold setting reproduces 4B MPO from Table 1 . We vary β with λ=0.80 and λintra=0.95 fixed.
Appendix figures & tables6 assets
Supplementary material from the paper’s appendix.
Appendix
Hyperparameter
BCP
Claw
Automation
max_prompt_length
4096
8000
8000
max_response_length
32768
64000
64000
train_batch_size
32
64
64
Actor optim.lr
10−6
1.6×10−6
1.6×10−6
Critic optim.lr
10−5
10−5
10−5
rollout.n
8
8
8
Appendix
Table 4: RL training hyperparameters for BCP, Claw, and Automation. The BCP settings are shared by the 4B and 30B-A3B runs. Length limits are measured in tokens. The max_turn row corresponds to max_assistant_turns for BCP, max_turns for Claw, and max_steps for Automation.
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.
Figure 9: Local refinement strength β : 0.0 (left) and 2.0 (right), compared with the MPO reference.
Figure 10: Cross-turn propagation λ : 0.60 (left) and 0.85 (right), compared with the MPO reference.
Figure 11: Within-turn trace λintra : 0.90 (left) and 1.00 (right), compared with the MPO reference.
Training LLMs as interactive agents for multi-turn decision-making remains challenging, particularly in long-horizon tasks with sparse and delayed rewards, where agents must execute extended sequences of actions before receiving meaningful feedback. Most existing reinforcement learning (RL) approaches model LLM agents as flat policies operating at a single time scale, selecting one action at each turn. In sparse-reward settings, such flat policies must propagate credit across the entire trajectory without explicit temporal abstraction, which often leads to unstable optimization and inefficient credit assignment. We propose HiPER, a novel Hierarchical Plan-Execute RL framework that explicitly separates high-level planning from low-level execution. HiPER factorizes the policy into a high-level planner that proposes subgoals and a low-level executor that carries them out over multiple action steps. To align optimization with this structure, we introduce a key technique called hierarchical advantage estimation (HAE), which carefully assigns credit at both the planning and execution levels. By aggregating returns over the execution of each subgoal and coordinating updates across the two levels, HAE provides an unbiased gradient estimator and provably reduces variance compared to flat generalized advantage estimation. Empirically, HiPER achieves state-of-the-art performance on challenging interactive benchmarks, reaching 97.4% success on ALFWorld and 83.3% on WebShop with Qwen2.5-7B-Instruct (+6.6% and +8.3% over the best prior method), with especially large gains on long-horizon tasks requiring multiple dependent subtasks. These results highlight the importance of explicit hierarchical decomposition for scalable RL training of multi-turn LLM agents.
Jiangweizhi Peng, Yuanxin Liu, Ruida Zhou +4
University of Minnesota · Northwestern University · Amazon AGI +2
Recent advances in multi-turn reinforcement learning (RL) have substantially improved the performance of LLM agents on complex, long-horizon interactive tasks. However, despite progress in fine-grained credit assignment, policy optimization still applies these learning signals through response-specific probability ratios. Different textual responses can induce the same executable effect, yet credit differences arising from subsequent outcomes remain tied to their individual textual realizations. We identify this mismatch as credit-update misalignment. Our analysis reveals that credit-text pairing directly shapes policy-update directions, even when the policy context and executable effect are held fixed. Motivated by this finding, we propose Effect-Marginal Policy Optimization (EMPO), which aligns policy optimization with execution-level equivalence through an effect-level surrogate that couples updates across alternative textual realizations. EMPO preserves the original credit signals, integrates with both trajectory-level and step-level credit estimators, and requires no additional critics or rollouts. Experiments on ALFWorld, WebShop, and Sokoban show that EMPO outperforms strong baselines in both task performance and learning efficiency.
Shaojin Ma, Ruitao Wang, Pengyi Li +6
Tianjin University · Fudan University · Renmin University of China
Large Language Model (LLM) agents increasingly solve long-horizon tasks through multi-turn interactions with users and external tools. In these settings, relevant task information often unfolds over time rather than being fully specified at the initial prompt. Service agents make this challenge especially concrete: users may clarify or revise their goals, while tool responses provide information needed for subsequent decisions. Thus, a final reward alone cannot indicate which actions contributed to resolving the task. Recent methods rely on comparative evidence from other trajectories or resampled continuations, or on separately constructed step-level learning signals, to refine credit. However, a completed rollout already records how information and errors flow between agent actions. We introduce Influence-Aware Policy Optimization (IAPO), which represents each rollout as a typed influence-dependency graph over trainable agent actions, with user and tool observations serving as evidence. IAPO converts support-use and failed-use structure into routing weights that redistribute the same trajectory-level advantage. Experiments with Qwen3-4B and Qwen3-8B demonstrate superior performance over multi-turn reinforcement learning (RL) baselines across three service-agent benchmarks: τ2-Bench, UserBench, and AgentChangeBench. BFCL-v4 Multi-Turn further shows that these gains do not compromise multi-turn function-calling performance. This work advances the understanding of credit assignment in multi-turn user interactions and provides a principled approach to training service agents from sparse outcome feedback.