Learning from Viable Failure Prefixes: Milestone Viability Potential Policy Optimization for Long-Horizon LLM Agents

1 Introduction

• +4.4/+5.3 success points over GiGPO on ALFWorld/WebShop with Qwen2.5-1.5B-Instruct; +1.1/+2.7 with Qwen2.5-7B-Instruct, with 0.16%–0.20% additional advantage-construction overhead.MVPO outperforms eight strong baselines under the same training length.Source: Figure 1 · p. 1, §1 · pp. 2–3
• In early WebShop training, zero-advantage steps affect over 90% of GRPO steps and about 65% of GiGPO steps.Both methods require variation among compared returns; identical returns leave them unable to distinguish useful from unproductive decisions.Source: Figure 1 · p. 1, §1 · p. 2
• Failed rollouts can contain viable prefixes, such as reaching the kitchen and approaching the fridge, even when all sampled trajectories receive zero returns.Other rollouts in the example pick up the wrong object or explore irrelevant locations.Source: §1 · p. 2
• MVPO estimates prefix potential over Union-Find viability regions, repairs zero-credit groups with potential-difference advantages, and preserves anchor-based comparative credit when informative.It attenuates potential-based credit as relative performance improves, allowing anchor-based credit to take a larger role later.Source: §1 · pp. 2–3

2 Related Work

• Prompting-based agents such as ReAct (Yao et al., 2022b), Reflexion (Shinn et al., 2023), WebGPT (Nakano et al., 2021), and Toolformer (Schick et al., 2023) use pretrained knowledge but provide limited mechanisms for improving policies from failed interactions.Benchmarks cover embodied and text-based tasks, web navigation, shopping, mobile-device control, and application-centered workflows.Source: §2 · p. 3
• Agent-focused methods including ArCHer (Zhou et al., 2024b), Agent Q (Putta et al., 2024), Tree-GRPO (Ji et al., 2025), and GiGPO (Feng et al., 2025) add hierarchical learning, search, or denser step-level credit.Other methods listed include RAGEN/StarPO (Wang et al., 2025a), SIRI (He et al., 2026), and ECPO (Li et al., 2026).Source: §2 · p. 3
• Group-relative estimators still collapse when rollout or anchor groups have identical returns, leaving viable prefixes in failed trajectories unlearned; MVPO routes those cases to prefix-potential advantages.MVPO preserves comparative credit when it is available.Source: §2 · p. 3

3 Preliminaries

• An agent receives a task instruction, observes a state, samples a textual action, receives a reward, and transitions to the next state; an episode is a trajectory of these interactions.Intermediate actions often receive no direct supervision, and early rollouts frequently fail before reaching the goal.Source: §3 · p. 3
• GRPO computes trajectory-level group-relative advantages, but all actions in a trajectory share the same advantage and identical failed-rollout returns provide no task-discriminative signal.Its return variation is measured by the standard deviation of trajectory returns.Source: §3 · pp. 3–4
• GiGPO constructs step-level credit by comparing future returns at repeated anchor states, but its advantage also collapses when continuations from an anchor have identical returns.Such zero-credit groups are especially common early in long-horizon training, when agents may make partial progress but fail to complete tasks.Source: §3 · p. 4

4 Methodology

• MVPO addresses zero-credit groups—where rollout or repeated-anchor returns cannot distinguish outcomes—by learning from viable failure prefixes.These groups are especially common early in long-horizon training, when agents make partial progress but fail to complete tasks.Source: §4 · p. 4

4.1 Viability Potential Estimation

• MVPO merges semantically equivalent prefixes into Union-Find viability regions and estimates potential from milestone progress, empirical future success, and loop frequency.Milestones are statistical features rather than fixed rewards; their predictive importance is learned from rollout data.Source: §4 · p. 4, §4.1 · p. 5

4.2 Progress-Aware Credit Routing

• MVPO preserves anchor comparisons when returns vary, repairs repeated zero-credit anchors with potential differences, and leaves singleton states neutral.Potential repair is strong when policy progress is limited and fades as successful rollouts become more frequent.Source: §4.2 · p. 6

4.3 Policy Optimization

• The repaired step-level advantage is assigned to action tokens and combined with episode-level group advantage in a clipped, critic-free objective without a learned value model.The objective retains comparative credit when return variation is available and repairs zero-credit transitions with a progress-aware potential signal.Source: §4.3 · p. 6, §4.2 · p. 6

5.1 Results on Long-Horizon Agentic Tasks

• Across ALFWorld and WebShop, MVPO improves over GiGPOw/std at both scales: 1.5B success rises from 86.7% to 91.1% and 65.0% to 70.3%, with gains at 7B.The main results table reports ALFWorld success rates and WebShop task score and success rate.Source: Table 1 · p. 7, §5.1 · pp. 7–8
• MVPO reaches 40% ALFWorld success at step 52, ahead of GiGPOw/std at step 62 and GRPO at step 73.The reported comparison frames this as faster progress through the early sparse-reward stage.Source: §5.1 · p. 7

5.2 Ablation Study

• On WebShop, full MVPO achieves 70.3% success and 84.6 task score; removing anchor credit lowers both, while disabling κ decay lowers success to 60.4%.The ablation results support retaining anchor comparisons and attenuating potential guidance as performance improves.Source: §5.2 · p. 8, Table 2 · p. 8

5.3 Training Time Analysis

• MVPO adds only 0.16% of GiGPO’s total step time on ALFWorld and 0.20% on WebShop, with extra computation confined to advantage construction.The time analysis attributes the added computation to Union-Find grouping, region statistics, and potential routing.Source: §5.3 · p. 8, Table 3 · p. 8

• Identical returns leave GRPO and GiGPO unable to distinguish useful failure prefixes from unproductive trajectories.The conclusion names this zero-credit failure as a bottleneck in long-horizon agent training.Source: §6 · p. 9
• MVPO repairs zero-credit steps with prefix-potential advantages estimated over Union-Find viability regions and attenuated by performance progress.Source: §6 · p. 9
• MVPO reports consistent gains on ALFWorld, WebShop, and search-augmented QA with 0.16%–0.20% advantage-computation overhead.Source: §6 · p. 9

• Viability estimation depends on meaningful prefix abstraction; highly unstructured observations can make the regions noisy and weaken potential-based repair.Source: Limitations · p. 9
• MVPO is most beneficial in long-horizon sparse-reward settings with recoverable failure prefixes; gains may be smaller in short-horizon tasks with frequent rewards or weak progress indicators.Source: Limitations · p. 9
• Experiments focus on ALFWorld, WebShop, and search-augmented QA with Qwen2.5-based agents; broader tool-use, multiagent, and real-world interactive evaluation remains future work.Source: Limitations · p. 9

Ethics Statement

• The evaluations use public or standard benchmarks, but real-world deployment raises misuse, reward-misspecification, privacy, and safety concerns.The authors recommend scoped tasks, explicit safety constraints, access controls, sandboxing, logging, human oversight, and further domain-specific evaluation.Source: Ethics Statement · p. 9
• Large-scale RL training should account for energy efficiency, hardware utilization, and reproducibility despite MVPO’s lightweight advantage-construction overhead.The authors identify compute-efficient variants as future work.Source: Ethics Statement · p. 10, §A.1 · pp. 12–13

A.1 Details of Training

• Training uses sparse success rewards and matched rollout settings, with 128 parallel environments for group-based methods and PPO.ALFWorld episodes allow up to 50 steps and WebShop episodes up to 15; the reported runs use 150 iterations and average three random seeds.Source: §A.1 · p. 12
• MVPO constructs routed advantages during advantage construction without a critic, reward model, extra model inference, or additional policy passes.Its added computations are CPU-side Union-Find grouping and region statistics.Source: §A.1 · pp. 12–13

A.2 Prompt Templates

• The prompt templates provide recent interaction history and admissible actions, require step-by-step reasoning in think tags, and place the selected action in action tags.The ALFWorld template uses the embodied-environment task and current observation; the WebShop template describes the e-commerce environment and shopping goal.Source: §A.2 · p. 13

A.3 Implementation Details of Prefix Abstraction

• The abstraction maps raw histories to coarse regions and progress indicators; the deterministic string-matching rules are replaceable without changing the optimization algorithm.The method assumes coarse prefix regions and weak progress indicators, which may come from environment metadata, tool traces, or learned embeddings.Source: §A.3 · pp. 13–14
• The ALFWorld signature uses location, two matched object keywords, and a three-step depth bin; search-augmented QA omits depth binning because its horizon is at most four turns.For example, a kitchen observation containing an apple and knife at depth six maps to kitchen|apple+knife|d6.Source: §A.3 · pp. 13–14
• Milestones are progress features, not fixed dense rewards, and AMP updates their weights online from rollout statistics.The weights reflect empirical association with future progress.Source: §A.3 · p. 14
• Milestone triggers are tailored to each setting: ALFWorld tracks object and task-operation progress, WebShop tracks page and purchase progress, and QA tracks search, retrieved information, and answer actions.The implementations use five milestones for each setting.Source: §A.3 · p. 14
• Union-Find merges identical progress signatures and also merges intervening regions when a trajectory revisits a signature, treating the path as a local loop.The structural cycle rule does not use task-success labels or manually assigned reward values.Source: §A.3 · p. 14
• Region potentials aggregate milestone return-to-go, the frequency of subsequent milestone progress, and loop counts; potentials are normalized within each rollout batch.As policy performance improves, κt decreases and the potential branch fades, leaving more gradient space for anchor-based comparative credit.Source: §A.3 · p. 14, Figure 3 · p. 15

B.1 Training Dynamics Analysis

• κt remains 1.0 early, then falls to about 0.20 on ALFWorld and 0.40 on WebShop by step 150 as EMA success rises.EMA success increases from about 13% on ALFWorld and 3% on WebShop during the first several steps to approximately 82.5% and 61.2%, respectively, by step 150.Source: §B.1 · p. 15
• As successful continuations become more common, anchor-based credit becomes more informative, and declining κt reduces potential’s influence rather than letting it dominate late-stage updates.The paper links this design to the ablation in Table 2, where disabling κ decay substantially reduces success rate.Source: §B.1 · pp. 15–16
• On WebShop, successful-trajectory mean potential stays positive (+0.44 at step 1; +0.09 at step 150), while failed-trajectory mean potential stays negative (−0.02; −0.12).The sign of the separation does not flip during training.Source: §B.1 · p. 15
• The WebShop grouping ratio remains around 70%–78% as batch success rises from approximately 2.3% to 56%.This indicates that the Union-Find regions continue to provide coverage for estimating prefix potential as trajectories change.Source: §B.1 · p. 16

B.2 Evaluation on Search-Augmented QA Tasks

• +2.2 points: MVPO raises the search-augmented QA average from 42.1% under GiGPO to 44.3%, also improving TriviaQA from 59.5% to 61.8% and PopQA from 42.4% to 45.7%.The reported results also improve NQ, HotpotQA, 2WikiMultiHopQA, and MuSiQue.Source: §B.2 · p. 17

C Theoretical Analysis

• MVPO’s expected early-stage improvement comes from adding a potential-gradient component when sparse rewards leave useful intermediate decisions without task-discriminative credit.The argument requires the prefix potential to align positively with future task progress.Source: C Theoretical Analysis · p. 17

C.1 Zero-Credit Gradient Decomposition

• MVPO preserves informative baseline anchor advantages and injects prefix-potential credit when the baseline signal collapses in zero-credit groups.This is where its routed estimator differs from GiGPO.Source: §C.1 · p. 18

C.2 Expected Improvement Bound

• The expected gain grows with the zero-credit ratio, potential strength, and alignment quality, under smoothness and positive-alignment assumptions.The analysis says the positive first-order term dominates when the learning rate is small and the potential gradient is bounded.Source: §C.2 · p. 18

C.3 Optimization-Speed Consequence

• MVPO is expected to reach a target faster when potential repair’s positive term exceeds the second-order penalty, with the advantage fading as zero-credit groups decline and κ is attenuated.The largest improvement is predicted when the zero-credit ratio is high and κ is approximately 1.Source: §C.3 · p. 19

C.4 Empirical Verification on ALFWorld

• +4.7 points at step 20, +12.5 at step 30, +14.9 at step 50, and +19.5 at step 60: MVPO’s early lead over GiGPO grows before narrowing to 78.1 vs. 76.6 at step 90.The later gap narrows as anchor-level return variation becomes more informative and performance progress attenuates the potential branch.Source: §C.4 · p. 19
• The observed early lead and later narrowing match MVPO’s design to accelerate sparse-reward learning without permanently overriding anchor-based credit.The potential-routed repair is most useful when zero-credit groups dominate, then fades as comparative anchor credit becomes reliable.Source: §C.4 · p. 19

D Pseudo Code of MVPO

• The training procedure builds Union-Find viability regions from semantically equivalent prefixes, estimates region potential, then computes potential advantages and routes credit by progress and availability.The routed and repaired advantages are assigned to action tokens before policy optimization.Source: D Pseudo Code of MVPO · p. 20