Milestone-Guided Policy Learning for Long-Horizon Language Agents

• URL: http://arxiv.org/abs/2605.06078v1
• Date: Thu, 07 May 2026 12:00:40 GMT
• Title: Milestone-Guided Policy Learning for Long-Horizon Language Agents
• Abstract summary: We introduce a milestone-guided policy learning framework, BEACON, to train long-horizon language agents.<n>On ALFWorld, WebShop, and ScienceWorld, BEACON consistently outperforms GRPO and GiGPO.<n>These results establish milestone-anchored credit assignment as an effective paradigm for training long-horizon language agents.
• Score: 67.87164829944238
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Act More, Decide Less: Skill-Guided Adaptive Action Chunking for Long-Horizon LLM Agents [50.85250898062218]
  Large language model (LLM) agents for long-horizon interactive tasks typically follow a ReAct-style protocol.<n>A natural alternative is to let the agent emit variable-length action chunks.<n>But naively training such policies with standard reinforcement learning fails.
  arXiv  Detail & Related papers  (2026-09-02T03:17:11Z)
• TRCA: Transition-wise Rubric Credit Assignment for Long-horizon LLM Agents [22.01777615106231]
  Long-horizon large language model (LLM) agents are typically optimized with sparse terminal outcomes.<n>We propose Transition-wise Credit Assignment, which derives step-level supervision directly from action-induced transitions.<n>Experiments on ALFWorld, WebShop, and seven search-augmented question-answering benchmarks show consistent improvements over the evaluated baselines.
  arXiv  Detail & Related papers  (2026-08-17T06:19:12Z)
• AgentOPSD: Recursive Self-Distillation for Agentic Reinforcement Learning [58.76655851910778]
  AgentOPSD is a critic-free, recursive method for turn-level credit assignment in agentic reinforcement learning.<n>We evaluate AgentOPSD on ALFWorld, WebShop, and Search-QA using Qwen2.5 models at two scales (3B and 7B)
  arXiv  Detail & Related papers  (2026-08-06T13:00:59Z)
• Semantic Consistency Policy Optimization for Reinforcement Learning of LLM Agents [45.62262776712415]
  Group-based reinforcement learning effectively post-trains agents for long-horizon, sparse-reward tasks by deriving step-level credit from trajectory outcomes.<n>This inconsistency sends conflicting gradients to similar actions and wastes the partially-correct progress inside failed rollouts.<n>We propose Semantic Consistency Policy Optimization ( SCPO), a value-free reward-shaping method that mitigates this inconsistency.<n> SCPO scores each failed step against a successful sibling and adds positive step-level credit for new progress along that sibling.
  arXiv  Detail & Related papers  (2026-06-24T14:02:13Z)
• PolicyTrim: Boosting Intrinsic Policy Efficiency of Vision-Language-Action Models [50.232333672172395]
  Vision-Language-Action (VLA) models provide a unified paradigm for robotic manipulation, yet their real-world deployment is often bottlenecked by execution efficiency.<n>We propose textbfPolicyTrim, a reinforcement learning-based post-training framework that extends the reliable action chunk length and reduces redundant physical steps.<n>Our framework delivers up to a 5.83$times$ end-to-end deployment speedup without compromising task success rates.
  arXiv  Detail & Related papers  (2026-06-21T14:54:07Z)
• Odysseys: Benchmarking Web Agents on Realistic Long Horizon Tasks [67.44219836008348]
  We introduce Odysseys: a benchmark of 200 long-horizon web tasks derived from real world browsing sessions evaluated on the live Internet.<n>We find that binary pass/fail evaluation is inadequate for long-horizon settings and introduce a rubric-based evaluation, annotating each Odysseys task with an average of 6.1 graded rubrics.<n>We find that the strongest models achieve a success rate of 44.5%, which leaves substantial room for future improvements.
  arXiv  Detail & Related papers  (2026-04-27T20:05:41Z)
• The Long-Horizon Task Mirage? Diagnosing Where and Why Agentic Systems Break [69.91172974854422]
  HORIZON is a cross-domain diagnostic benchmark for analyzing long-horizon failure behaviors in large language model (LLM) agents.<n>We evaluate state-of-the-art (SOTA) agents from multiple model families to study horizon-dependent degradation patterns.<n>Our findings offer an initial methodological step toward systematic, cross-domain analysis of long-horizon agent failures.
  arXiv  Detail & Related papers  (2026-04-13T19:11:42Z)
• A Subgoal-driven Framework for Improving Long-Horizon LLM Agents [12.411629679174183]
  Large language model (LLM)-based agents have emerged as powerful autonomous controllers for digital environments.<n>We present MiRA, an RL training framework that uses dense, milestone-based reward signals.<n>Our findings demonstrate that combining explicit inference-time planning with milestone-based rewards significantly improves an agent's long-horizon capabilities.
  arXiv  Detail & Related papers  (2026-03-20T06:32:16Z)
• Hindsight Credit Assignment for Long-Horizon LLM Agents [25.156923297108836]
  We introduce HCAPO, the first framework to integrate hindsight credit assignment into Large Language Model (LLM) agents.<n> Evaluations across three benchmarks, including WebShop and ALFWorld, demonstrate that HCAPO consistently outperforms state-of-the-art RL methods.<n>These results indicate that HCAPO significantly enhances exploration efficiency, promotes concise decision-making, and ensures scalability in complex, long-horizon tasks.
  arXiv  Detail & Related papers  (2026-03-07T06:05:20Z)
• Harmonizing Dense and Sparse Signals in Multi-turn RL: Dual-Horizon Credit Assignment for Industrial Sales Agents [29.076822653598885]
  We propose a framework that disentangles optimization across time scales.<n>Experiments with a high-fidelity user simulator show DuCA outperforms the state-of-the-art GRPO baseline.
  arXiv  Detail & Related papers  (2026-03-02T05:44:50Z)
• LongCLI-Bench: A Preliminary Benchmark and Study for Long-horizon Agentic Programming in Command-Line Interfaces [65.11019654023978]
  LongCLI-Bench is a benchmark designed to evaluate agentic capabilities across long-horizon, realistic tasks.<n>We curated 20 high-quality, long-horizon tasks from over 1,000 computer science assignments and real-world tasks.<n>Experiments reveal that even state-of-the-art agents achieve pass rates below 20% in LongCLI-Bench.
  arXiv  Detail & Related papers  (2026-02-15T23:12:57Z)
• Intrinsic Credit Assignment for Long Horizon Interaction [20.67253382614053]
  Belief-RL teaches information-seeking capabilities that consistently outperform purely outcome-based rewards for Reinforcement Learning.<n>Our work introduces a scalable training strategy for navigating uncertainty over a long-horizon, by enabling credit assignment to intermediate actions via intrinsic Belief rewards.
  arXiv  Detail & Related papers  (2026-02-12T19:00:54Z)
• WebAnchor: Anchoring Agent Planning to Stabilize Long-Horizon Web Reasoning [82.12501258760814]
  Large Language Model(LLM)-based agents have shown strong capabilities in web information seeking.<n>Plan anchor is where the first reasoning step disproportionately impacts downstream behavior in long-horizon web reasoning tasks.<n>We propose Anchor-GRPO, a two-stage RL framework that decouples planning and execution.
  arXiv  Detail & Related papers  (2026-01-06T16:36:40Z)
• Agentic Reinforcement Learning with Implicit Step Rewards [92.26560379363492]
  Large language models (LLMs) are increasingly developed as autonomous agents using reinforcement learning (agentic RL)<n>We introduce implicit step rewards for agentic RL (iStar), a general credit-assignment strategy that integrates seamlessly with standard RL algorithms.<n>We evaluate our method on three challenging agent benchmarks, including WebShop and VisualSokoban, as well as open-ended social interactions with unverifiable rewards in SOTOPIA.
  arXiv  Detail & Related papers  (2025-09-23T16:15:42Z)
• Strict Subgoal Execution: Reliable Long-Horizon Planning in Hierarchical Reinforcement Learning [5.274804664403783]
  Strict Subgoal Execution (SSE) is a graph-based hierarchical RL framework that enforces single-step subgoal reachability.<n>We show that SSE consistently outperforms existing goal-conditioned RL and hierarchical RL approaches in both efficiency and success rate.
  arXiv  Detail & Related papers  (2025-06-26T06:35:42Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.