Technical Summary: Milestone-Guided Policy Learning for Long-Horizon Language Agents (BEACON)

Problem Statement

Training language agents to perform long-horizon tasks—requiring dozens of sequential decisions—via reinforcement learning (RL) faces two fundamental limitations inherent to trajectory-level optimization methods like GRPO:

1. Credit Misattribution: Current methods assign credit based solely on terminal outcomes. Consequently, correct early actions are penalized if subsequent actions lead to failure. This creates contradictory gradient signals for identical state-action pairs depending on downstream stochasticity, causing gradient conflict and learning collapse as task horizons extend.
2. Sample Inefficiency: As task horizons lengthen, successful trajectories become scarce. Crucially, trajectories that achieve significant subgoals but fail the final objective receive the same zero reward as complete failures. This discards valuable learning signals from "partial successes," leading to a high proportion of samples providing no useful gradient.

Existing attempts to densify credit assignment, such as Process Reward Models (PRMs) or Monte Carlo value estimation, introduce prohibitive annotation costs, computational overhead, or rely on state recurrence patterns that diminish in long-horizon settings.

Methodology: BEACON Framework

The authors propose BEACON (Benchmarking Environment for Action-Oriented Navigation), a framework that leverages the compositional structure of long-horizon tasks to decouple credit assignment across phases. The core assumption is the Milestone Markov Property: once a semantic subgoal (milestone) is achieved, the future trajectory distribution depends primarily on remaining subgoals rather than the full execution history.

BEACON operates through three integrated mechanisms:

1. Trajectory Partitioning at Milestone Boundaries

Instead of treating a trajectory as a flat sequence, BEACON partitions it into segments based on observable state transitions that indicate subgoal completion (e.g., picking up an object, reaching a webpage). A milestone detector $\Phi$ identifies these transitions from environment feedback without requiring learned models or manual annotations.

• Result: Trajectories are divided into segments $Seg_k$ bounded by milestones $M_k$.

2. Temporal Reward Shaping

To address sample inefficiency, BEACON assigns shaped rewards within segments to credit partial progress.

• Mechanism: For actions in a segment that successfully reaches a milestone, a positive reward is assigned with temporal decay ($\gamma^{t_k - t}$). Actions in segments that fail to reach a milestone receive zero reward.
• Effect: This transforms sparse terminal signals into dense feedback, ensuring that agents learn from trajectories that complete subgoals even if the final task fails.

3. Dual-Scale Advantage Estimation

To resolve credit misattribution, BEACON estimates advantages at two scales:

• Trajectory-Level Advantage ($A_{traj}$): Computed globally based on terminal outcomes (similar to GRPO) to maintain alignment with the overall task success.
• Segment-Level Advantage ($A_{seg}$): Computed locally by comparing the return of a segment only against other trajectories that reached the same milestone.
• Variance Isolation: By restricting comparison groups to trajectories that share the same milestone history, $A_{seg}$ isolates the quality of local actions from the variance introduced by subsequent segments. This prevents early correct actions from being penalized by later failures.
• Combination: The final advantage is a weighted sum: $\hat{A} = A_{traj} + \lambda \cdot A_{seg}$.

Key Contributions

1. Diagnosis of Limitations: The paper empirically identifies and quantifies credit misattribution (over 40% of gradient updates contain contradictory signals in long tasks) and sample inefficiency (partial successes yielding zero reward) as the root causes of performance collapse in long-horizon RL.
2. BEACON Framework: Introduction of a milestone-guided policy learning framework that partitions trajectories, applies temporal reward shaping, and utilizes dual-scale advantage estimation to decouple local action quality from downstream variance.
3. Theoretical Guarantee: A proof demonstrating that under the Milestone Markov Property, segment-level advantages isolate local action quality from downstream variance, directly addressing credit misattribution.
4. Empirical Validation: Comprehensive evaluation across three diverse benchmarks (ALFWorld, WebShop, ScienceWorld) demonstrating that BEACON scales effectively with task horizon, unlike existing baselines.

Experimental Results

Experiments were conducted using Qwen2.5-1.5B and Qwen2.5-7B models on ALFWorld, WebShop, and ScienceWorld.

• Performance on Long-Horizon Tasks: On ALFWorld, BEACON achieves a 92.9% success rate on long tasks, nearly doubling the 53.5% achieved by GRPO. In contrast, GRPO degrades sharply from 76.7% on short tasks to 53.5% on long tasks.
• Sample Efficiency: BEACON improves effective sample utilization from 23.7% (GRPO) to 82.0%, successfully extracting learning signals from partial successes that other methods discard.
• Gradient Quality: The Zero-Advantage Ratio (samples receiving near-zero advantage) drops from ~55% (GRPO) to ~10% (BEACON), and the Contradictory Action Ratio is significantly reduced.
• Comparison to SFT: BEACON outperforms supervised fine-tuning (SFT) on oracle trajectories (91.4% vs. 43%), confirming that the gains stem from policy optimization discovering strategies superior to the oracle, rather than simple imitation.
• Robustness: BEACON maintains robust performance across short, medium, and long horizons, whereas baselines like GRPO and GiGPO show significant degradation as task length increases.

Significance and Claims

The paper claims that milestone-anchored credit assignment represents an effective paradigm for training long-horizon language agents. By exploiting the inherent compositional structure of agentic tasks, BEACON overcomes the systematic performance collapse associated with increasing decision sequences.

The authors emphasize that their method does not require expensive process reward models or additional learned critics. Instead, it utilizes observable state transitions to provide precise credit assignment, enabling agents to learn efficiently from partial successes and resolve gradient conflicts. The results suggest that structural priors (milestones) are critical for scaling RL in language agents, offering a path toward more capable autonomous systems for complex, multi-step tasks like web navigation, embodied control, and scientific experimentation.