Long horizon llm agents learn better from partial failed tries

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

Artificial Intelligence

Summary

When AI agents try to solve complex tasks that take many steps, they often get rewarded only at the very end, which makes it hard to know which early steps were good or bad. The authors show that existing methods struggle because they ignore useful early parts in failed attempts, assigning no helpful feedback to those steps. They introduce a new method called Milestone Viability Potential Policy Optimization (MVPO), which identifies useful partial successes even in failed tries and uses them to better update the AI’s decisions. Experiments show this method improves success rates in complex environments compared to previous approaches.

What this means in practice

  • For software developers: Develop AI agents that better handle tasks requiring many careful steps by learning from partial success in early failed attempts.
  • For ecommerce platform teams: Improve automated assistants for web shopping by enabling them to learn effectively from partly successful attempts in complex browsing and purchasing tasks.

Authors

Qi Zhou, Yuanfan Li

Abstract

Long-horizon LLM agents require reinforcement learning methods that can assign credit to intermediate decisions under sparse and delayed rewards. Existing group-based methods such as GRPO and GiGPO alleviate this issue by comparing rollout returns or repeated anchor states, but they still fail when the compared returns have no variation. We identify this failure mode as zero-credit failure: during early training, many failed rollouts contain useful prefixes, yet existing methods assign them no task-discriminative advantage. To address this issue, we propose Milestone Viability Potential Policy Optimization (MVPO), a potential-routed policy optimization algorithm that learns from viable failure prefixes. MVPO estimates prefix potential over Union-Find viability regions, repairs zero-credit groups with potential-difference advantages, and attenuates the potential branch according to relative performance progress. Experiments with Qwen2.5-1.5B-Instruct show that MVPO outperforms eight strong baselines, including GRPO and GiGPO. Under the same training length, MVPO improves over the GiGPO baseline by +4.4 success points on ALFWorld and +5.3 on WebShop, while adding only 0.16%-0.20% advantage-construction overhead.
View PDFOpen arXiv