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).
Figures & tables
Figure 1: Overview of the proposed FOCUS rollout scheduler for a deep-research-style problem. FOCUS continues working on a rollout tree. At each iteration, FOCUS STEP 1: takes an expanded tree; STEP 2: scores each compaction-induced state with the critic; STEP 3: compares against outcomes to decide critic quality ( subsection 2.2 ); STEP 4: sources additional continuations that are expected to correct critic errors most efficiently ( subsection 2.3 ). With this active learning loop for rollout acquisition, FOCUS provides a more accurate value estimate with limited rollout budgets ( subsection 3.4 ).
Algorithm 1 Selective rollout allocation and value refinement, with continuation helper
Figure 2: Preliminary evaluation with Qwen3.5-4B on MATH Level 4–5. Accuracy and the mean number of generated tokens per evaluation question are shown at the base checkpoint (update 0) and after 8, 16, 24, and 32 completed updates. Markers denote recorded checkpoints. Panel (c) shows FOCUS’s mean g(c) over all pre-allocation score evaluations within each update from 1 to 32; shading denotes ±1 standard deviation of those scores, computed as the square root of the reported variance.
Model
Method
DeonticBench
BrowseComp -Plus
LocBench
Airline
SARA-N
SARA-B
Hard
Overall
File@1
File@5
Reference (no RL)
gpt-oss-20b (medium)
2.7
8.0
76.8
14.1
33.7
18.6
54.0
57.5
Nemotron 3 Nano 30B A3B
2.7
12.0
89.9
18.3
36.1
19.3
57.9
66.6
Qwen3.5-9B
5.3
30.0
89.9
19.7
45.9
29.7
62.1
67.8
Qwen3.5-27B
58.7
60.0
94.2
43.7
73.4
50.6
66.7
79.3
Table 1: Evaluation results for FOCUS vs critic-free methods. Entries are accuracy (%) on the held-out split of each benchmark. DeonticBench Hard aggregates dataset-marked hard subsets from Airline, SARA-N, and SARA-B. Reference rows are untrained. Δ is FOCUS minus GRPO in percentage points; subscripts and superscripts give the lower and upper endpoints of marginal 90% paired bootstrap CIs, respectively. Bootstrap and checkpoint details are in Appendix B . For cost reasons, we only report DeonticBench at Qwen3.5-27B.
Figure 3: Training dynamics. Each column is one benchmark, showing training reward against optimizer step (top), held-out evaluation (middle), and mean numbers of tool calls per episode on the held-out split (bottom), for GRPO, VinePPO, and FOCUS under a matched per-step generation budget. Top panels plot mean terminal reward from on-policy collection; LocBench held-out reward is File@5. BrowseComp-Plus results are the equivalence judgement of Qwen3-32B ( Qwen Team, 2025 ) .
Figure 4: Value refinement for FOCUS. (a) MSE on fixed audit trees as MCTS continuations are allocated by each rule (solid: constant critic init; dashed: random critic init). (b) Rank agreement between checkpoint critic values and an oversampled, critic-blind MCTS target on fixed audit states.
Figure 5: Ablations at evaluation checkpoints. (a) Varying the compaction operator on DeonticBench under a matched budget; (b) FOCUS with full refinement vs. FOCUS without refinement rollouts on BrowseComp-Plus; (c) free-form vs. structural compaction on LocBench (File Acc@5).
Appendix figures & tables7 assets
Supplementary material from the paper’s appendix.
Appendix
Table 8Table 9Table 10Table 11Table 12Table 13
Free-form
Structural
Compaction instruction
LocBench-specific instruction with the NullWorkspace guidance inserted
Generic instruction with the NullWorkspace guidance, followed by a LocBench schema and an output contract
Reply format
Four suggested headings; the reply is kept verbatim
Exactly one <summary> block with four non-empty sections: State, Evidence, Open questions, Next steps
Validation
Rejected if empty, cut off at the reply cap, or inside unclosed reasoning
Also parsed into the four sections and held to the 2,048-token target; one repair retry. Compaction turns are penalized −0.01 on failure and −0.002 when the wrapper is recovered
Next steps
Always “None”
A short next action; any reread must match an Open question
Re-entry
Notes appended to the original request inside <your_notes> (user turn)
Request left untouched; notes in their own <assistant_memory> turn, then a resume instruction
Execution state
None
Harness-rendered JSON of executed calls, counters, and submissions
Appendix
Table 14: Free-form versus structural compaction on LocBench. Both compactions are tool-free ( NullWorkspace ) and must finish within the reply cap.
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.
Jiaxi Liu, Shixiong Kai, Zhentao Tang +4
Shanghai Jiao Tong University · Huawei Noah’s Ark Lab
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.
Training large language model agents in long-horizon environments requires assigning credit from sparse terminal outcomes to individual actions. Existing critic-free methods propagate trajectory-level rewards uniformly across steps, while recent approaches construct step-level groups by matching repeated states and compare actions within each group. The former cannot distinguish useful actions in failed trajectories from ineffective actions in successful ones. The latter rely on step credit derived directly from individual trajectory outcomes and fixed-weight fusion with episode-level credit. We propose Gated-BEPO, which derives step-level credit from empirical rollout graphs. For each rollout group, Gated-BEPO constructs an empirical graph and estimates node values through a mean-backup Bellman fixed point that reflects the empirical action distribution of the current policy. We then accumulate these temporal-difference residuals along each sampled trajectory using generalized advantage estimation, yielding step-level Bellman advantages that capture both immediate and downstream effects. To adaptively fuse episode- and step-level credit, a confidence gate incorporates Bellman credit only at states with multiple observed successors and otherwise uses episode-level credit. Experiments on WebShop, ALFWorld, and visual Sokoban show consistent improvements across language and vision-language models, while diagnostic ablations support the effectiveness of Bellman fixed-point value estimation and show that step-level credit should be incorporated selectively rather than uniformly into the final advantage.
Hongxi Yan, Ziyue Huang, Shichao Fan +1
State Key Laboratory of Virtual Reality Technology and Systems, Beihang University, Beijing, China · Zhongguancun Laboratory, Beijing, China · Qualcomm, Beijing, China