Milestone-Based Evaluation and Training for Long-Horizon AI Agents

Long-horizon agents operate across many dependent states and transitions, often spanning multiple tools, environments, and periods of external feedback. The difficulty comes from preserving coherent progress as earlier decisions constrain later actions.

A single workflow may involve researching evidence, changing files or records, waiting for external responses, revising plans, validating intermediate results, and returning to earlier systems with new information.

Late failure can hide substantial successful work. A terminal score cannot distinguish a bad plan from a mostly correct trajectory that broke during one dependency, approval, validation, or state transition.

Long trajectories are expensive to collect and difficult to diagnose. Preserving intermediate progress keeps partially successful behavior available for evaluation, targeted data collection, and later reinforcement learning.

Why evaluation on long-horizon becomes a black box

Long-horizon difficulty comes from maintaining coherent progress across changing states, delayed feedback, and dependencies that unfold over time. Earlier outcomes repeatedly determine which actions remain valid later in the trajectory.

• Sales: Advance an enterprise opportunity over several days by researching the account, updating stakeholder hypotheses, coordinating meetings, responding to replies, revising outreach, tracking objections, and keeping CRM state synchronized.
• Marketing: Launch a campaign from research through measurement by building the brief, generating assets, coordinating reviews, publishing across channels, monitoring early results, correcting problems, and updating targeting or messaging.
• Finance: Complete a monthly close by collecting records, reconciling accounts, investigating exceptions, requesting missing evidence, updating spreadsheets or systems, routing approvals, and revisiting blocked entries when new information arrives.
• Engineering: Ship a production change across a large codebase by tracing dependencies, implementing updates, running tests, debugging failures, coordinating review, deploying gradually, monitoring behavior, and repairing regressions without losing prior context.

Each long-horizon workflow contains many valid intermediate states and several points where later work depends on earlier decisions. A failure near completion can therefore leave most of the underlying trajectory correct.

Binary task success compresses a long-horizon workflow into one label. Milestone-based evaluation preserves which states were reached, which transitions succeeded, and which downstream work became unreachable after a specific failure.

What milestone-based evaluation should tell you

Long-horizon evaluation needs more than a record of completed actions. A useful milestone trace should show how the agent moved through many dependent states and whether each transition actually advanced the task.

A trajectory can remain plausible for dozens of steps while drifting into the wrong state. Milestones should identify where that divergence began, rather than assigning the failure only to the final unsuccessful action.

Milestone evidence should also preserve dependencies. A failed validation step may block reporting, approval, delivery, and downstream system updates, even when the research and implementation phases were completed correctly.

Across repeated runs, milestone success rates can reveal whether one transition is consistently fragile or whether failures emerge under particular environments, tools, or task conditions.

Milestone evidence across agent evaluation and training

Earlier research established intermediate supervision at smaller scales, from reasoning steps to interactive environments. Those approaches provide the foundation for milestone-based evaluation across longer agent trajectories and more complex dependencies.

Evaluation progressively expanded from individual reasoning steps to multi-turn interactions, environment states, subgoal completion, and workplace checkpoints. Each stage preserved more information about how an agent reached an outcome.

Long-horizon evaluation extends the same principle across larger state spaces and deeper dependency chains, where intermediate evidence becomes necessary for diagnosing failures and preserving useful progress.

How agent benchmarks are moving toward partial progress

In short tasks, pass/fail scoring may be enough. In long-horizon agent tasks, the agent can make meaningful progress before one missing action, failed tool call, or invalid final state causes the benchmark to mark the whole task as failed.

Combining hard gates with partial credit

Some professional tasks need stricter scoring than subgoal completion alone. An output may be partially correct, but it still has to satisfy hard requirements before partial credit makes sense. If required files are missing, if an output cannot be parsed, or if the result is in an invalid state, the benchmark should fail that attempt before scoring quality.

Agents’ Last Exam (Sun et al., 2026) uses that gate-and-score structure for long-horizon professional tasks. The benchmark covers more than 1,000 tasks across 55 subfields and 13 industry clusters.

The gate checks whether the output satisfies required preconditions. If the gate fails, the score is zero. If the gate passes, a weighted rubric can assign partial credit for completeness, correctness, and quality.

This matters because full success is rare on hard professional tasks. Across mainstream harness and backbone configurations, the hardest tier has an average full-pass rate below 1%. With pass/fail scoring alone, most results collapse near zero. Gate-and-score evaluation separates invalid outputs from valid but incomplete work.

Fine-grained checkpoints for long computer-use workflows

OSWorld 2.0 extends partial-progress evaluation to substantially longer computer-use workflows. Its 108 tasks take skilled human users a median of about 1.6 hours and are scored against an average of 27.25 task-specific checkpoints.

The benchmark evaluates the final environment state across those checkpoints rather than enforcing one fixed execution path. Different action sequences can therefore receive credit when they reach the same valid intermediate state.

The reported results expose how much information binary completion loses. The strongest configuration completes 20.6% of tasks under strict binary scoring while reaching a 54.8% partial score.

Checkpoint quality also becomes part of benchmark design. OSWorld 2.0 audits its partial-reward checks for reward hacking and false negatives, testing whether checkpoints represent meaningful progress and whether valid alternative solutions still receive credit.

Scoring intermediate subgoals in GUI tasks

WindowsWorld (Li et al., 2026) turns that kind of workflow into subgoal scoring. The benchmark includes 181 tasks across 17 professional Windows applications, with 78% of tasks spanning multiple applications.

Figure: WindowsWorld combines multi-step, multi-application workflows, with harder tasks requiring more intermediate checkpoints across connected desktop tools. Source: https://arxiv.org/pdf/2604.27776

Each task has about five intermediate subgoals, and the final score averages subgoal completion rates instead of reducing the task to pass/fail.

Why long-horizon training needs intermediate credit

A long-horizon rollout can span hundreds of actions and state transitions, while standard RL may still assign one reward at the end. A failed outcome gives little guidance about which decisions actually caused it.

Terminal rewards also waste expensive trajectory data. A rollout may contain correct planning, useful tool interactions, and verified intermediate progress before one late dependency or validation failure collapses the full run into failure.

Milestone-aware training preserves credit for verified progress inside the rollout. Intermediate rewards can reinforce successful states or completed segments while reserving negative credit for the part of the trajectory associated with failure.

Recent methods such as BEACON, MiRA, and ADMIRE use milestone boundaries, learned progress estimates, or adaptively discovered milestones to provide denser credit across long-horizon trajectories.

How training methods assign intermediate credit

Once intermediate credit is available, the design problem is choosing what should receive it. Current approaches derive that structure from repeated states, explicit task decomposition, or milestone patterns learned from successful trajectories.

Subgoals and milestones serve different roles inside that structure. A subgoal defines an objective the agent should pursue; a milestone records observable progress that can justify assigning credit.

Local credit assignment from repeated states

GiGPO extracts local comparisons from states that recur across the agent’s existing rollouts. When different trajectories reach the same environment state, their next actions form a comparison group for estimating step-level advantage.

Consider a shopping agent that reaches a results page across long rollouts. Some trajectories choose correctly; others recover or fail later. GiGPO compares downstream returns from the shared state, separating choices from the final outcome.

Figure: GiGPO retains trajectory-level comparison while grouping actions from repeated anchor states into step-level comparison groups. Source: GiGPO.

The episode-level signal is still retained. GiGPO combines the relative quality of the complete trajectory with the relative quality of actions taken from shared anchor states, giving the policy both global and local credit signals.

The step-level groups are constructed retrospectively from existing trajectories, so GiGPO avoids launching additional rollouts from every intermediate state. The paper reports performance gains of more than 12% over GRPO on ALFWorld and more than 9% on WebShop while keeping the same rollout workload and GPU memory overhead.

Credit through task decomposition

As trajectories grow longer, BEACON addresses a weakness of repeated-state grouping: exact state recurrence becomes less common. Verified milestone completion instead partitions the rollout into segments representing meaningful intermediate progress.

At each boundary, BEACON’s milestone detector reads observable environment feedback rather than step-level reward annotations. Completed segments receive temporally decayed credit, while unfinished final segments receive no milestone reward.

Figure: BEACON separates a long task at verified milestone boundaries, preventing later failure from overwriting credit for earlier completed phases. Source: BEACON.

Credit then operates at two scales. Trajectory-level advantage preserves final task success, while segment-level advantage compares rollouts reaching the same milestone, limiting how much distant failures distort earlier completed work.

On long ALFWorld tasks, BEACON reports 92.9% success versus 53.5% for GRPO, while effective sample utilization rises from 23.7% to 82.0%.

Other methods keep the same basic idea, but change what the intermediate unit represents: a planning subgoal in one case, or a learned estimate of progress in another.

At the planning level, HiPER separates subgoal selection from execution. Hierarchical Advantage Estimation assigns returns across the full subgoal segment while evaluating the actions used to execute it at a finer timescale.

Between milestone completions, MiRA learns a smoother estimate of progress from subgoal checks. Changes in predicted progress shape reward during the long stretches where no explicit milestone has yet been completed.

Across all three methods, task decomposition provides the common structure, while credit lands at different resolutions: completed segments, planning-versus-execution decisions, or continuous progress between explicit subgoals inside long trajectories.

Adaptive milestone discovery

Fixed subgoals can be brittle in GUI environments. A desktop or mobile agent may reach the same useful state through different menus, layouts, or action paths, so a hand-written checklist can miss valid progress.

Adaptive milestone methods handle that problem by learning milestone structure from trajectories. In ADMIRE (Zheng et al., 2026), milestones are distilled from successful explorations and then used to guide future training.

Figure: ADMIRE dynamically derives milestones from successful trajectories, updates them as better strategies emerge, and uses the resulting milestones to assign credit across subsequent rollouts. ADMIRE 

ADMIRE also assigns credit asymmetrically. Successful trajectories reward only milestone-triggering steps to filter redundant actions, while failed trajectories receive partial credit for reaching intermediate milestones before the final failure.

On AndroidWorld, ADMIRE improves success by more than 10 percentage points across base models, showing that adaptive milestones can increase reward density without relying on a fixed sequence of GUI actions

What long-horizon agent development needs

Long-horizon agent development requires evaluation and training systems to represent the same intermediate structure. Milestones, dependencies, checkpoint states, and failure labels should remain available across scoring, diagnosis, and reinforcement learning.

Evaluation then becomes more than reporting a final score. Milestone traces show where progress held, where dependencies broke, and which partially successful trajectories contain evidence worth reusing for training or data curation.

As agents operate across longer workflows, useful supervision increasingly lives inside the trajectory. Agent-development systems that preserve that structure can turn long rollouts into better diagnostics, better training data, and more reliable autonomy.