MileGPO: Milestone Inference with Local Evidence for Graph-Based Policy Optimization of Long-Horizon LLM Agents

• URL: http://arxiv.org/abs/2608.19803v2
• Date: Sat, 22 Aug 2026 03:12:30 GMT
• Title: MileGPO: Milestone Inference with Local Evidence for Graph-Based Policy Optimization of Long-Horizon LLM Agents
• Abstract summary: We propose MileGPO, which derives process-level credit from grouped on-policy rollouts through three designs.<n>MileGPO requires neither auxiliary models nor additional environment interaction.
• Score: 26.262385802144323
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Credit assignment is challenging in long-horizon agentic reinforcement learning, where supervision often comes only from final rewards. Existing methods refine trajectory-level signals into step-level credits through step grouping or graph-based advantage estimation, but can overlook meaningful intermediate milestones. We propose MileGPO (Milestone Inference with Local Evidence for Graph-Based Policy Optimization), which derives process-level credit from grouped on-policy rollouts through three designs. Milestone Discovery identifies candidate milestones on successful rollouts and recurring traps on failed ones. Reliability-Calibrated Shaping (RCS) weights these candidates by outcome-based confidence, strengthening reliable milestones and traps while down-weighting uncertain ones. Progress-Contrastive Calibration (PCC) further tests whether a candidate reflects local progress and whether its incoming transition outperforms observed alternatives from the same state. MileGPO requires neither auxiliary models nor additional environment interaction. Experiments on ALFWorld and WebShop show state-of-the-art performance and a small in-distribution to out-of-distribution gap on ALFWorld. Ablations and credit diagnostics indicate that reliability weighting, local progress, and same-state branch evidence complement milestone discovery and resolve ambiguous intermediate credit.

Related papers

• PGPO: Potential-Guided Policy Optimization for Multi-Turn Agentic Tasks [41.82007055765541]
  We propose Potential-Guided Policy Optimization for multi-turn agentic tasks.<n>It estimates empirical state potentials from anchor-state-group return statistics within each rollout group.<n>It then derives action advantages from potential differences between adjacent states, enabling cross-trajectory credit propagation.
  arXiv  Detail & Related papers  (2026-09-02T07:44:16Z)
• 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)
• TRIAGE: Role-Typed Credit Assignment for Agentic Reinforcement Learning [10.917273110894469]
  Agentic reinforcement learning requires assigning credit to environment-facing actions.<n>Standard GRPO uses the final verifier outcome as a uniform advantage over all action tokens.<n>We propose TRIAGE, a role-typed credit assignment framework that adds a semantic role axis to outcome credit.
  arXiv  Detail & Related papers  (2026-06-30T17:48:07Z)
• TRACE: A Unified Rollout Budget Allocation Framework for Efficient Agentic Reinforcement Learning [52.67756371231985]
  Reinforcement learning with verifiable rewards (RLVR) is a promising approach for enhancing reasoning and agentic behavior in large language models.<n>We introduce Tree Rollout Allocation for Contrastive Exploration (TRACE), a unified rollout allocation framework.<n>Technically, TRACE allocates rollout budget to both prompt roots and intermediate prefixes that are most likely to yield mixed terminal rewards.
  arXiv  Detail & Related papers  (2026-06-09T17:16:03Z)
• PBSD: Privileged Bayesian Self-Distillation for Long-Horizon Credit Assignment [35.978805768172656]
  Long-horizon agentic tasks pose a fundamental credit assignment challenge for outcome-base reinforcement learning.<n>We propose PBSD (Privileged Bayesian Self-Distillation), a Bayes-calibrated self-distillation method for fine-grained credit assignment under sparse final rewards.
  arXiv  Detail & Related papers  (2026-06-08T11:20:58Z)
• Self-evolving LLM agents with in-distribution Optimization [60.05867547965365]
  Large Language Models (LLMs) have recently emerged as powerful controllers for interactive agents in complex environments.<n>We propose Q-Evolve, a self-evolving framework for LLM agents that unifies automatic process-reward labeling and policy learning.<n>We evaluate our method on AlfWorld, WebShop, and ScienceWorld, showing Q-Evolve outperforms strong baselines in sample efficiency, robustness, and overall task performance.
  arXiv  Detail & Related papers  (2026-06-05T15:09:52Z)
• StainFlow: Entity-Stain Tracking and Evidence Linking for Process Rewards in GUI Agents [67.03593791535786]
  Reinforcement Learning (RL) has become a promising approach for improving GUI Agents in long-horizon, digital environments.<n>To mitigate this issue, recent studies introduce Process Reward Models (PRMs)<n>PRMs provide finer-grained training feedback through global milestone verification or local step-level evaluation.<n>We propose StainFlow, an entity-stain-flow process reward model for GUI Agents.
  arXiv  Detail & Related papers  (2026-06-05T08:17:28Z)
• VeriGate: Verifier-Gated Step-Level Supervision for GRPO [51.26100506256885]
  Group Relative Policy Optimization is an effective recipe for training reasoning models with verifier-based outcome rewards.<n>We present VeriGate, a verifier-gated extension of GRPO that addresses these limitations with three design choices.<n>We show that VeriGate improves average accuracy by about 20% and 12% for 1.5B and 7B models respectively.
  arXiv  Detail & Related papers  (2026-05-28T18:20:32Z)
• StepOPSD: Step-Aware Online Preference Distillation for Agent Reinforcement Learning [6.365332042924078]
  We present StepOPSD, a post-rollout preference self-distillation framework that takes the agent step as the unit of credit redistribution.<n>StepOPSD decomposes trajectories into action-centered step segments, rescoring them under hindsight-enriched teacher contexts.<n>Results reveal a consistent two-knob law: smaller _clip acts as a broadly stabilizing local trust region, whereas the optimal global mixing strength _mix remains task-dependent.
  arXiv  Detail & Related papers  (2026-05-26T15:07:03Z)
• Self-Induced Outcome Potential: Turn-Level Credit Assignment for Agents without Verifiers [26.97849381770806]
  Self-Induced Outcome Potential treats semantic clusters of final answers as latent future outcome states for potential-based turn-level credit assignment.<n>We formalize the framework, characterize its supervised gold-answer limit, and show that SIOP improves average performance over verifier-free outcome-level baselines.
  arXiv  Detail & Related papers  (2026-05-06T14:38:48Z)
• Verified Critical Step Optimization for LLM Agents [67.05296684575445]
  Critical Step Optimization focuses preference learning on verified critical steps.<n>Method starts from failed policy trajectories rather than expert demonstrations.<n>Experiments on GAIA-Text-103 and XBench-DeepSearch show that CSO achieves 37% and 26% relative improvement over the SFT baseline.
  arXiv  Detail & Related papers  (2026-02-03T11:41:02Z)

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.