PaperlayerView exact revision on arXiv

Source-linked AI summary

Milestone-Guided Policy Learning for Long-Horizon Language Agents

Zixuan Wang, Yuchen Yan, Hongxing Li, Teng Pan, Dingming Li, Ruiqing Zhang, Weiming Lu, Jun Xiao, Yueting Zhuang, Yongliang Shen

arXiv:2605.06078v1cs.CLcs.AI

TL;DR

Long-horizon language-agent reinforcement learning struggles with credit misattribution and sample inefficiency. BEACON uses milestone-based segmentation, temporal reward shaping, and dual-scale advantage estimation to address these problems. Across ALFWorld, WebShop, and ScienceWorld, it consistently outperforms GRPO and GiGPO, with especially large gains on long-horizon tasks.

  • Problem

    Long-horizon policy optimization suffers from credit misattribution and sample inefficiency because terminal outcomes penalize correct early actions and partial successes often yield no learning signal.

  • Method

    BEACON partitions trajectories at milestone boundaries, applies temporal reward shaping within segments, and estimates advantages at dual scales.

  • Results

    BEACON outperforms GRPO across ALFWorld, WebShop, and ScienceWorld, with relative gains over GRPO increasing from 26.2% on short ALFWorld tasks to 73.6% on long tasks.

  • Takeaways & Limitations

    Milestone-anchored credit assignment provides an effective approach for training long-horizon language agents.

  • Takeaways & Limitations

    BEACON assumes that future trajectory distributions depend primarily on remaining subgoals after reaching a milestone, rather than on the full history.

Abstract

from arXiv · show

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.

1. Introduction

Long-horizon language-agent training suffers from horizon-dependent performance collapse because terminal-only optimization misattributes credit and discards partial progress. BEACON addresses these problems by assigning credit around milestones and improves performance and sample utilization across benchmarks.

  • Long-horizon reinforcement-learning agents face performance collapse as decision sequences lengthen.
  • Trajectory-level optimization misattributes credit by giving actions identical terminal-outcome advantages, while scarce successful trajectories make partial progress yield no reward.Correct early actions can be penalized by later failures, and trajectories completing substantial subgoals may still receive zero reward.
  • BEACON partitions trajectories at milestone boundaries, shapes rewards within segments, and estimates advantages at dual scales.These design choices target local action quality without allowing later failures to determine all earlier credit.
  • BEACON outperforms GRPO across ALFWorld, WebShop, and ScienceWorld, with relative gains over GRPO scaling from 26.2% on short tasks to 73.6% on long tasks.
  • Sample utilization improves from 23.7% to 82.0%, while more than 40% of gradient updates contain contradictory signals as task horizons extend.

2. Failures in Flat Trajectory Optimization

Flat trajectory optimization wastes partial successes and corrupts remaining learning signals through contradictory credit assignment. Both failures intensify with longer horizons, motivating methods that exploit task compositionality.

  • GRPO success on ALFWorld falls from 76.7% on Short tasks to 53.5% on Long tasks.Tasks are stratified by optimal trajectory length: Short (L∗≤4), Medium (5≤L∗≤7), and Long (L∗>7).
  • Sample Inefficiency: Partial successes comprise 39–47% of training samples but receive zero reward like complete failures, while full successes remain below 27%.Consequently, over 73% of samples yield no learning signal under GRPO.
  • Credit Misattribution: The Contradictory Action Ratio exceeds 40%, and the effective learning signal collapses below 20%.The same correct action can receive opposite-sign credit because trajectory-level advantages conflate action quality with downstream stochasticity.
  • Takeaways: Sample inefficiency discards partial-success signals, while credit misattribution corrupts the signal that remains; both worsen as horizons extend.Longer tasks produce lower success rates and more opportunities for downstream variance to corrupt credit assignment.

3. Milestone-Anchored Policy Optimization

BEACON exploits milestone structure to partition long-horizon trajectories, shape rewards for partial progress, and combine global and milestone-matched advantages to reduce credit corruption from later outcomes.

  • Trajectory Partitioning: BEACON partitions trajectories at verifiable milestone boundaries into segments corresponding to successive task phases.The milestone indicator detects observable state changes, such as object pickup or heating completion.
  • Temporal Reward Shaping: Completed segments receive positive temporally decayed rewards, giving all actions partial-success credit while favoring actions closer to milestone completion.Only segments ending in a completed milestone receive positive reward; the final incomplete segment receives zero.
  • Dual-Scale Advantage Estimation: Trajectory-level advantages compare terminal outcomes across sampled trajectories, preserving a global task-performance signal.The trajectory-level advantage follows GRPO and normalizes terminal rewards using the group mean and standard deviation.
  • Dual-Scale Advantage Estimation: Segment-level advantages compare returns only among trajectories reaching the same milestone, isolating local action quality from downstream variance.This comparison is motivated by the problem that trajectory-level methods assign identical credit to all actions and can reflect later failures.
  • Optimization: BEACON combines trajectory- and segment-level advantages so local credit is protected from variance in later segments while global performance remains represented.The method uses a balance parameter λ between global task performance and local segment quality.

4. Experiments

Experiments evaluate BEACON against prompting and reinforcement-learning baselines on three long-horizon environments, using matched training configurations and fixed BEACON parameters.

  • Experimental Setup: The evaluation covers ALFWorld, WebShop, and ScienceWorld, which require multi-step household interaction, product search and purchase, or virtual scientific experiments.The environments provide sparse or compositional long-horizon tasks across embodied, web-navigation, and scientific-reasoning settings.
  • Baselines: Baselines include GPT-4o and Gemini-2.5-Pro under ReAct, ReAct prompting, PPO, GRPO, and GiGPO.The comparisons span closed-source models, prompting, actor-critic reinforcement learning, and group-based advantage methods.
  • Implementation: BEACON uses identical training configurations across reinforcement-learning methods, with γ = 0.95 and λ = 1.0 fixed across benchmarks.These BEACON-specific parameters are not task-specifically tuned.
  • Overall Performance: BEACON achieves the highest success rate across all benchmarks and model scales.With the 1.5B model, it reaches 91.4% on ALFWorld, 75.6% on WebShop, and 45.3% on ScienceWorld.
  • Overall Performance: 91.4% average success on ALFWorld with the 1.5B model surpasses GiGPO's 86.1% and GRPO's 72.8%.On WebShop, BEACON reaches 75.6% versus 65.0% for GiGPO and 56.8% for GRPO; on ScienceWorld, it reaches 45.3% versus 25.8% and 21.1%.

Appendix B, showing consistent gains across all task types.

BEACON's advantages increase with task horizon, while its reward shaping converts partial successes into useful learning signal and reduces zero-advantage samples.

  • Horizon-Dependent Performance: 92.9% Long-task success for BEACON contrasts with 53.5% for GRPO on ALFWorld with the 1.5B model.BEACON records 96.8% on Short and 87.0% on Medium tasks, while GRPO declines from 76.7% on Short to 53.5% on Long.
  • Gradient Starvation: Approximately 10% Zero-Advantage Ratio for BEACON at iteration 150 contrasts with around 55% for GRPO.BEACON starts at 45% ZAR and rapidly decreases, whereas GRPO starts near 100%.
  • Credit Concentration: 2.36 Credit Concentration Ratio for GiGPO exceeds GRPO's 1.37, while BEACON is reported as having lower concentration.CCR measures average advantage magnitude for milestone actions relative to non-milestone actions.
  • Beyond Behavior Cloning: 81% success for BEACON with γ=0 exceeds the 43% achieved by supervised fine-tuning on oracle trajectories.The γ=0 condition supplies milestone reward only, isolating the contribution of milestone-anchored credit assignment in this comparison.

BEACON (Ours)

BEACON improves long-horizon policy learning by exploiting milestone structure for more targeted credit assignment and useful gradient signals. Its ablations and trajectory analyses show that temporal shaping, dual-scale advantages, and task-inherent milestones each contribute to performance and training stability.

  • Training Dynamics: BEACON reaches 60% success by iteration 50, whereas GRPO requires iteration 120, alongside smoother entropy reduction during training.These dynamics are consistent with more trajectories contributing useful gradient signal per batch.
  • Ablation Study: Random partitioning reaches 74.2% versus GRPO’s 72.8%, but the 17.2% gap to full milestones exceeds the 1.4% gap to random partitioning.This indicates that BEACON’s gains primarily exploit task-inherent structure rather than segmentation alone.
  • Ablation Study: Temporal decay improves ALFWorld performance from 81.2% at γ = 0 to 91.4% at γ = 0.95, whereas uniform shaping reaches only 71.8%.The ablation attributes the additional gain to distinguishing critical from preparatory actions within segments.
  • Ablation Study: Removing segment-level advantage reduces performance to GRPO’s 72.8% on ALFWorld and 56.8% on WebShop, while trajectory-level feedback is especially necessary on ALFWorld.The dual-scale formulation combines local milestone feedback with downstream task-success correction.
  • Credit Assignment: BEACON credits completed milestones while penalizing errors and inefficient detours, unlike GRPO’s uniform credit and GiGPO’s counterintuitive assignments.On a failed trajectory, BEACON assigns positive advantage to completed milestones even when the final task fails.

A. Theoretical Analysis

BEACON’s variance-isolation guarantee rests on approximately Markovian milestone states: segment-level advantages separate local action quality from downstream variance. The guarantee is strongest when milestones encode complete subgoal achievement, but can weaken when resources or efficiency carry across segments.

  • Assumption: Under the Milestone Markov Property, future segments are conditionally independent of earlier segment actions once a milestone state is reached.This assumption models compositional tasks where subsequent success depends on remaining subgoals rather than how earlier subgoals were achieved.
  • Variance Isolation: The variance-isolation result is established for comparison groups Gk under the Milestone Markov Property.The formal proposition concerns trajectories that reach at least milestone k.
  • Variance Isolation: Segment-level advantages isolate local action quality from downstream variance, so later outcomes do not affect gradients for earlier-segment actions.This directly addresses credit misattribution in trajectory-level optimization.
  • Assumption Limits: The assumption may be approximate when inventory limits or time constraints make future success depend on resources or execution efficiency carried across segments.BEACON may still benefit empirically through shaped rewards and reduced, though not fully eliminated, downstream variance.

B. Task-wise Analysis on ALFWorld

Across ALFWorld task types and both Qwen2.5 model scales, BEACON consistently outperforms other methods, with especially strong gains on the multi-milestone Pick2 task.

  • Task-wise Results: BEACON consistently outperforms other methods across all six ALFWorld task types and both Qwen2.5-1.5B and Qwen2.5-7B scales.The comparison covers success rates for both model sizes.
  • Task-wise Results: 13% on Pick2 with Qwen2.5-1.5B and 11% with Qwen2.5-7B are BEACON’s reported gains over other methods.Pick2 requires locating and picking up two separate objects, involving more milestones for credit assignment.
  • Task-wise Results: 91.4% success for BEACON-trained 1.5B models substantially exceeds the reported GPT-4 comparison.The passage identifies this as a notable ALFWorld result.

C.1. Benchmark Descriptions

The evaluation spans embodied reasoning, web navigation, and scientific experimentation through ALFWorld, WebShop, and ScienceWorld, each testing different long-horizon capabilities.

  • Benchmark Scope: The benchmarks cover embodied reasoning, web navigation, and scientific experimentation.The three environments are ALFWorld, WebShop, and ScienceWorld.
  • ALFWorld: ALFWorld contains six household-task types requiring natural-language navigation and object manipulation.Its tasks include PICK, CLEAN, HEAT, COOL, LOOK, and PICK2, with short, medium, and long trajectory strata.
  • ALFWorld: Table 3 reports ALFWorld success rates separately for each task type.The table is identified as ALFWorld task-wise results.
  • WebShop: WebShop evaluates product-search and purchasing decisions over 1.18 million products and 12,087 human instructions.Agents must satisfy compositional constraints such as color, size, price, and features.
  • ScienceWorld: ScienceWorld evaluates 30 scientific reasoning tasks involving virtual experiments and action sequences frequently exceeding 30 steps.It reports both normalized progress and success rate, while exposing explicit subgoal feedback.

C.2. Diagnostic Metrics

The diagnostic framework measures contradictory credit signals and surviving gradient magnitude, while experiments use matched group-based configurations and fixed evaluation settings.

  • Contradictory Action Ratio: CAR measures the fraction of repeated state-action pairs receiving contradictory gradient signals.It uses shared state-action pairs and counts positive versus negative advantages across trajectories.
  • Effective Gradient Ratio: EGR measures the proportion of gradient magnitude that survives cancellation from contradictory signals.An EGR of 1.0 indicates fully consistent gradients, while lower values indicate greater cancellation.
  • Implementation: Training uses veRL with vLLM on eight NVIDIA A100 80GB GPUs, with reported 150-iteration runtimes varying by benchmark.ALFWorld and ScienceWorld take approximately 10 hours, while WebShop takes approximately 8 hours.
  • Experimental Controls: Group-based methods use identical base configurations, differing only in their advantage computation mechanisms.All experiments use random seed 0 and evaluate 128 samples per checkpoint.

D. Limitations and Future Work

BEACON’s limitations concern milestone detection, milestone granularity, and benchmark scope. Future work includes automated milestone discovery and adaptive or hierarchical milestone structures.

  • Milestone Detection: Milestone detection requires domain-specific designs and may not generalize to environments without clear subgoal structure or verifiable state transitions.The experiments use pattern matching, page transitions, or explicit subgoal signals across the three environments.
  • Future Work: Automated milestone discovery and adaptive or hierarchical milestone structures remain directions for future work.
  • Milestone Granularity: BEACON’s effectiveness depends on milestones occurring at an appropriate granularity.Sparse milestones approach trajectory-level optimization, whereas overly dense milestones may make segment-level advantages noisy.
  • Milestone Granularity: The experiments use naturally occurring milestones without tuning granularity, although optimal milestone density likely varies across tasks.
  • Benchmark Scope: The evaluation covers discrete action spaces and text-based interaction, leaving continuous control, multi-agent settings, and less compositional tasks unexplored.
Loading 2605.06078v1…