Reinforcement learning for long-horizon language agents requires identifying whether intermediate actions make eventual task success more or less likely when supervision is available only at trajectory level. The main difficulty is that a critic with aggregate return-prediction accuracy may still fail to resolve the local value differences needed to assign credit to actions, especially under sparse feedback and function approximation. Conventional critics estimate future return, but policy improvement also depends on knowing whether each intermediate decision makes task success more or less likely. We introduce SCALE, an actor-critic framework that augments conventional return estimation with explicit prediction of eventual task success. At each interaction prefix, the critic predicts a return value and a Success Value, defined as the probability that the task will eventually be completed from that prefix. SCALE converts changes in Success Value into multi-step action credit through Success-GAE and modulates its contribution according to the estimated reliability of the predictor, while retaining the token-level PPO objective. Across five agent benchmarks and three model backbones, SCALE improves task performance over the compared RL baselines in most settings, with gains of up to 4.1 percentage points in success rate. Separate critic-learning analyses show that SCALE also improves critic estimation and training stability.
Figures & tables
Figure 1: Comparison between PPO and SCALE . PPO derives step credit from changes in predicted return, which can be unreliable when feedback is sparse. An action may receive positive credit even when it lowers the probability of eventual success. SCALE instead uses changes in Success Value to measure whether each action makes task success more or less likely.
Method
Gran.
Critic
Reliab.
Token PO
Credit Signal
Extra Structure
PPO
Step
✓
✗
✓
Discounted return
None
GRPO
Trajectory
✗
✗
✓
Group outcome
Group rollouts
GiGPO
Step
✗
✗
✓
Step relative adv.
Anchor states
VinePPO
Step
✗
✗
✓
Monte Carlo value
Vine branching
Turn-PPO
Turn
✓
✗
✗
Turn return
Turn MDP
CAPO
Action
✓
✗
✗
Action value
Action optimization
Table 1: Comparison of representative RL methods for credit assignment. “Gran.” denotes credit-assignment granularity. “Critic” indicates whether a learned critic is used. “Reliab.” denotes explicit reliability modeling or control, and “Token PO” indicates token-level policy optimization.
Figure 2: Vanilla PPO critic reliability analysis on ALFWorld and WebShop.
Figure 3: Overview of SCALE . Top: A simple rollout example contrasts an ideal return critic with practical training, where sparse supervision and imperfect learning make reliable action-level credit difficult. Bottom: SCALE learns success-aware critic signals, converts them into reliable environment-step credit, and uses the resulting advantages for token-level policy optimization.
Method
ALFWorld
ScienceWorld
WebShop
Pick
Look
Clean
Heat
Cool
Pick2
All
Score
Succ
Score
Succ
Closed-Source Models
GPT-4o
75.3
60.8
31.2
56.7
21.6
49.8
48.0
54.3
45.4
31.8
23.7
Gemini-2.5-Pro
92.8
63.3
62.1
69.0
26.6
58.7
60.3
47.8
36.7
42.5
35.9
Base: Qwen2.5-1.5B-Instruct
Direct Prompt
5.9
5.5
3.3
9.7
4.2
0.0
4.1
5.9
0.7
23.1
5.2
Table 2: Main results across agentic benchmarks. We report success rate (%) on ALFWorld, and task score and success rate on ScienceWorld and WebShop. Results are averaged over three runs. Best and second-best are highlighted within each base-model block.
Method
AppWorld
BFCL-v4
Avg.
avg@4
pass@4
avg@4
pass@4
avg@4
pass@4
Qwen2.5-7B-Instruct
Base
12.63
24.56
18.00
27.00
15.32
25.78
+PPO
27.36
42.11
34.75
43.00
31.06
42.56
+GRPO
30.70
45.61
37.50
46.00
34.10
45.81
+GSPO
25.00
40.35
40.25
47.00
32.63
43.68
Table 3: Results on agent tool-use benchmarks. We report avg@4 and pass@4 . Best and second-best are highlighted within each base-model block.
Figure 7
Figure 6: Training dynamics across five agent benchmarks. Top: Task performance during training, reported as success rate for ALFWorld, WebShop, and ScienceWorld, and avg@4 for BFCL-v4 and AppWorld. Middle: Critic explained variance during training. Bottom: Critic value loss during training. Compared with PPO, SCALE achieves higher explained variance and generally lower, smoother critic loss across the five benchmarks.
Variant
BFCL-v4
AppWorld
SCALE
51.75
49.12
Success-Aware Critic
w/o Success Value Head
43.25
39.91
w/o Return Value Head
29.75
20.18
Success Credit Estimation
w/ One-Step Success TD
39.75
31.14
Table 4: Ablation study of SCALE with Qwen3-8B. We report avg@4 (%) on BFCL-v4 and AppWorld.
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
Benchmark
Task Reward / Score
Success Criterion
Evaluation Metric
ALFWorld
Environment task completion
info["won"]=True
Success Rate
WebShop
qi∈[0,1]
Terminal and qi=1
Task Score / Success Rate
ScienceWorld
Final score zi
Terminal and zi>0
Task Score / Success Rate
AppWorld
ri=Pi+FiPi
ri=1
Avg@4 / Pass@4
BFCL-v4 MT
Binary correctness (0/1)
Official evaluator returns correct
Avg@4 / Pass@4
Appendix
Table 5: Evaluation protocol across the five benchmarks. We summarize the task reward or score, the criterion for a successful trajectory, and the reported evaluation metrics.
Reinforcement learning studies how agents learn sequential decisions from rewards and interaction, balancing exploration, performance, safety, and adaptation.
Sparse outcome rewards make it difficult for long-horizon language-model agents to assign credit to earlier actions. Learned critics provide value estimates for intermediate states, but these estimates can be inaccurate, while estimating intermediate values with repetitive continuation samples from points within a trajectory incurs substantial costs. To mitigate these issues, we introduce FOCUS, an RL method that uses selective branching to help the critic network learn its value estimator. The rollout controller facilitates active learning for the critic by sampling continuations from states that are expected to most reduce the critic's estimation error. These refined value estimates then score the segment between consecutive states with a TD(λ) advantage, while the sampled evidence supplies training targets for the critic. FOCUS supports long-horizon agentic reinforcement learning through a modular context-management interface that decouples context management from rollout allocation. Our experiments show that using compaction-induced segment boundaries for value estimation and credit assignment, FOCUS outperforms GRPO and VinePPO with matched per-step generation budgets on legal reasoning, deep search, and code localization benchmarks, improving held-out accuracy at Qwen3.5-9B scale by 7.2 points over the strongest baseline on BrowseComp-Plus (55.4 vs. 48.2) and by 4.1 points on DeonticBench (56.5 vs. 52.4).
While long-horizon agentic tasks require language agents to perform dozens of sequential decisions, training such agents with reinforcement learning remains challenging. We identify two root causes: credit misattribution, where correct early actions are penalized due to terminal failures, and sample inefficiency, where scarce successful trajectories result in near-total loss of learning signal. We introduce a milestone-guided policy learning framework, BEACON, that leverages the compositional structure of long-horizon tasks to ensure precise credit assignment. BEACON partitions trajectories at milestone boundaries, applies temporal reward shaping within segments to credit partial progress, and estimates advantages at dual scales to prevent distant failures from corrupting the evaluation of local actions. On ALFWorld, WebShop, and ScienceWorld, BEACON consistently outperforms GRPO and GiGPO. Notably, on long-horizon ALFWorld tasks, BEACON achieves 92.9% success rate, nearly doubling GRPO's 53.5%, while improving effective sample utilization from 23.7% to 82.0%. These results establish milestone-anchored credit assignment as an effective paradigm for training long-horizon language agents. Code is available at https://github.com/ZJU-REAL/BEACON.
Long-horizon language-model agents trained with reinforcement learning oftenreceive sparse outcome rewards that do not reveal which decisions along a tra-jectory deserve credit. Episode-level advantages provide coarse trajectory-widecredit, while step-level comparisons offer finer resolution with context-dependentestimation noise. We propose Granularity-Adaptive Credit Assignment (GACA),a critic-free method that adaptively mixes episode- and step-level credit for eachdecision during policy optimization. GACA normalizes the sampled response'smean per-token negative log-likelihood (NLL) within each trajectory and uses theresulting criticality score to determine the step-specific mixture. The computationreuses rollout log-probabilities without additional training rollouts or model eval-uations. Our analysis characterizes optimal score-dependent mixing and derivesconditions linking expected NLL to a lower bound on the preferred step-levelweight. Across ALFWorld and WebShop with 1.5B and 7B backbones, GACAachieves the highest reported mean success rates among the compared methods,while introducing negligible additional computation.
Taoran Liang, Yang Liu, Shang Luo +10
Nankai University · Peking University · Supply Chain Tech Team Y, JD.com +2