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

Long-horizon agents are outgrowing pass/fail evaluation.

A short task can be scored as one outcome. A longer workflow is different. The agent may plan correctly, navigate to the right place, call the right tool, and still fail during execution. A final failure score does not show which phase broke.

Training has the same shape of problem. Reinforcement learning for long-horizon agents often gives one reward at the end of the task. In a 50-step trajectory, that terminal reward has to stand in for every planning decision, tool call, state change, and execution step.

Milestones make those trajectories easier to measure. A milestone breaks the task into phases that can be checked separately, so teams can see which phases passed, which phase failed, and which later steps were blocked by the failure.

The two unsolved problems in RL agent development

Models are now capable enough to run longer agent workflows. The bottleneck has moved to the signals used to evaluate and train them. That shift creates two problems for RL agent development.

Evaluation is the first problem. Current benchmarks often return a single pass/fail score per task. If an agent fails, the benchmark says the task failed, but it does not show where the failure happened, which phase broke, or what the team should fix.

Training is the second problem. Standard RL often assigns one reward at the end of a long task. In a 50-step trajectory, the model receives one signal for all 50 actions. The reward does not tell the model which planning decision, tool call, state change, or execution step caused the final outcome.

Both problems collapse a long trajectory into one result. Milestones give evaluation and training a more granular structure: one score becomes a per-phase diagnostic report, and one terminal reward can become feedback tied to specific phases of the task.

Why evaluation becomes a black box

Agent benchmarks compress long workflows into one outcome, even when the agent’s trajectory contains several distinct phases.

Take some common agentic workflows.

• A browser agent may need to understand the task, navigate to the right page, select the right tool, fill the right fields, and complete a final state change before the benchmark assigns a score.
• A coding agent may need to inspect files, plan edits, run commands, interpret errors, and produce a final artifact.
• A workplace agent may need to move across documents, messages, tools, and approvals before the task is complete.

With these tasks, long-horizon workflows create ambiguity when the agent fails after partial progress. The agent may gather the right context, navigate to the right interface, and prepare the right action before failing on one state change or tool action.

A final score reports the task as failed. It does not show which earlier phases worked or which later phases were blocked. Milestone-based evaluation can report the trajectory by phase: what passed, what failed, and what never ran.

Agent teams need that phase-level trace because different failures require different fixes.

What milestone-based evaluation should tell you

Milestone-based evaluation starts from the information a standard benchmark leaves out.

A standard benchmark can say the task failed. A milestone-based report can say the agent parsed the task, planned the approach, searched for relevant information, and extracted structured data before failing during cross-referencing. The later synthesis and formatting steps depended on cross-referencing, so the workflow stalled before those phases could run.

The report gives the team a different debugging target. The failed phase points to the capability that needs work.

The same idea becomes more useful across repeated runs. A single run can show where one trajectory broke. Repeated runs can show whether that phase is consistently weak or whether the failure appears only under certain task conditions.

Milestone-based evaluation turns one task-level score into a per-phase performance breakdown. The benchmark can show where the agent succeeds, where it fails, which later phases were blocked, and where model improvement should start.

Milestone evidence across agent benchmarks

Recent agent benchmarks use milestones, checkpoints, subgoals, or process labels to recover information that final success rates lose.

Paper / benchmark	Milestone mechanism	Key result	What it shows
Math-Shepherd	Step-level process supervision	Individual reasoning steps receive reward scores before the final answer is checked	Reasoning failures can be located inside the solution trace
BEACON	Milestone-guided policy learning	Navigation milestones exceed 90% success, while manipulation milestones fall below 55%	One task can contain separate capability bottlenecks
HiPER	Planner-executor decomposition	91% planner accuracy, 71% executor success, and 83% aggregate score	Planning and execution can fail at different rates
AgentBoard	Progress Rate over subgoal completion	Llama2-13B reaches 2.1% success and 18.9% progress. Mistral-7B reaches 3.9% success and 24.6% progress	Low final success can still contain measurable partial progress
TheAgentCompany	Checkpoints with point values	A CI/CD task can score 45/100 after repository creation and pipeline-file setup	Workflow evaluation can score completed stages before later failure
WindowsWorld	Intermediate subgoal scoring	181 tasks across 17 Windows applications, with about five subgoals per task	GUI evaluation needs progress scoring across multi-step workflows
Agents’ Last Exam	Hard gates plus weighted rubrics	1,490 tasks across 55 subfields and 13 industry clusters, with a 2.6% full-pass rate	Hard tasks need validity checks before partial-credit scoring

Final success rates compress different failures into the same number. Recent benchmarks add milestone labels, checkpoints, subgoals, or gates so evaluation can show where the trajectory stopped.

What per-milestone evaluation reveals across models and tasks

The value of milestone-based evaluation becomes clearer when aggregate scores make different failures look the same. A task-level score can say that an agent failed, but it cannot show whether the failure came from reasoning, navigation, manipulation, planning, or execution.

Step-level reasoning

Process-level reasoning work shows the same problem in a smaller setting. Math-Shepherd is a process-supervision method for math reasoning, where individual solution steps are scored instead of only checking the final answer.

That setup makes the failure location visible. A model may start with a correct approach, make one flawed intermediate step, and still produce a wrong final answer.

For agent evaluation, the useful analogy is the location of the failure: a model that fails early in a trajectory and a model that fails near the end should not receive the same diagnostic report just because the final task failed.

Embodied task phases

Embodied and interactive tasks make the diagnostic gap larger because one benchmark item can contain several capabilities.

ALFWorld (Sridhar et al.), for example, connects abstract text-based policies with embodied execution, which makes it a useful setting for separating high-level planning from concrete environment actions.

In BEACON, a milestone-guided policy learning framework, milestone-level results show a clear split between navigation and manipulation: agents can exceed 90% success on navigation milestones while falling below 55% on manipulation milestones.

A single final score would blend those phases together, even though they point to different model weaknesses.

Planning and execution

Planning and execution create a different diagnostic split. An agent can choose the right high-level strategy and still fail when it has to carry out the concrete steps. The reverse can also happen: the agent may be capable of taking individual actions, but fail because the plan sends it toward the wrong goal.

HiPER separates a high-level planner that proposes subgoals from a low-level executor that carries them out over multiple action steps.

On WebShop, which is a simulated online-shopping environment where agents must search, inspect products, compare options, and choose an item that satisfies a user instruction, HiPER reports 91% planner accuracy and 71% executor success, while the aggregate score is 83%.

The aggregate number sits between the two, but the useful diagnosis is the gap: the agent can often identify the right plan while still failing to carry it out.

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.

Measuring progress when success rates are near zero

Success rates can collapse near zero on difficult agent tasks, even when models make different amounts of partial progress. A metric based only on final success makes those models look similarly weak.

AgentBoard (Ma et al., 2024) addresses this with Progress Rate, a metric that tracks the highest subgoal completion fraction reached at any point in the trajectory.

The near-zero success case shows why that metric is useful. In AgentBoard, Llama2-13B reaches a 2.1% success rate but an 18.9% progress rate. Mistral-7B reaches a 3.9% success rate but a 24.6% progress rate.

Binary success makes both models look almost equally weak. Progress Rate shows that Mistral gets farther through the task before failing, even though both final success rates remain low.

Turning workflows into scored checkpoints

Professional workflows need a different kind of partial-progress signal. A workplace task can involve several tools, files, messages, and approvals before the final deliverable is complete. When the task fails late, a binary score cannot show whether the agent failed immediately or completed most of the workflow.

TheAgentCompany (Xu et al., 2024) applies checkpoint scoring to this kind of setting. The benchmark simulates a software company with tools such as GitLab, Jira, Slack, and code execution, then breaks workplace tasks into explicit checkpoints with point values.

In a CI/CD task for example, an agent can receive 20 points for creating the correct GitLab repository and 25 points for adding a valid .gitlab-ci.yml file, even if the pipeline does not pass and the Slack notification is never sent. The final score is 45/100 because the first two checkpoints were completed.

Checkpoint scoring changes what the benchmark can report. Instead of assigning zero to every failed workflow, the benchmark can show which parts of the workflow were completed and where the breakdown started.

Scoring intermediate subgoals in GUI tasks

Desktop GUI tasks also have the same partial-progress problem. An agent may open the right application, find the right file, fill most required fields, and still fail the final save, export, or submission step. A binary score would erase the useful progress made before that final failure.

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.

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

That means an agent that completes four out of five subgoals can score 80%, rather than receiving 0% because the final task 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 1,490 tasks across 55 subfields and 13 industry clusters. Each task is treated as a full deliverable, not just a short interaction. 

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. The benchmark reports an average full pass rate of 2.6% across mainstream frontier models. With pass/fail scoring alone, most results collapse near zero. Gate-and-score evaluation separates invalid outputs from valid but incomplete work.

Standard vs milestone signals in long-horizon agent development

Evaluation and training both lose information when a long rollout becomes one final outcome.

In evaluation, the final score hides where the task broke. In training, the terminal reward gives the same delayed signal to many decisions. Milestones keep the rollout split into phases, so the same structure can support both diagnosis and learning.

Dimension	Standard setup	Milestone-aware setup
Reward signal	One final score or terminal reward covers the full trajectory.	Intermediate checkpoints attach feedback to completed, failed, and blocked phases.
Failure localization	A failed run says the task failed, but not which phase caused it.	A milestone trace shows where progress stopped and which later phases were blocked.
Data efficiency	Failed trajectories provide weak training value because useful and harmful actions share the same outcome.	Partial progress stays usable. Completed phases can become training data, verifier targets, or subtask examples.
Convergence	Long rollouts make updates noisy because many actions receive the same delayed signal.	Shorter milestone segments give the optimizer cleaner feedback about which behavior changed the rollout.

Milestone structure gives evaluation a failure trace and gives training a cleaner credit-assignment target.

The evaluation side explains what happened inside the rollout. The training side uses the same phase structure to decide which behavior should receive credit, penalty, or more data.

Why training on long tasks is unstable

A long agent trajectory can contain dozens or hundreds of actions, but standard RL often assigns one reward at the end. When the task fails, that terminal reward does not identify which action caused the failure, which earlier actions were useful, or which phase should receive a different training signal.

Sparse rewards make credit assignment noisy

The problem is credit assignment. A browser agent might choose the right search strategy, open the right page, extract the right information, and then fail during the final submission step. A coding agent might inspect the correct files, generate a reasonable patch, and then fail because one test still breaks.

With only a terminal reward, all of those actions are updated from the same final result. The model receives a weak signal about the whole trajectory instead of a precise signal about the decision that caused the failure. That makes long-horizon training noisy because useful actions and harmful actions can be reinforced or penalized together.

The longer the task gets, the worse this becomes.

A reward at step 50 has to explain every planning decision, tool call, state change, and execution step that came before it. The update becomes less about learning which action mattered and more about guessing from a delayed outcome.

Failed trajectories can still contain useful behavior

Long-horizon agents also create many failed trajectories that are not fully bad. A run can fail overall while still containing useful planning, correct retrieval, valid tool calls, or partial task completion.

Without milestones, the failed final outcome can punish the whole trajectory. That means the model may receive negative feedback for steps that were actually useful. In practice, this can discourage the behaviors the training process should preserve.

Milestones give the trajectory more structure. Completed phases can receive local positive feedback, while the failed phase can receive a more targeted penalty. The model can learn from partial progress instead of treating every failed run as a uniformly bad example.

What milestone training achieves

Milestone training changes the reward signal from a delayed task-level judgment into feedback tied to intermediate progress. Instead of waiting until the end of a long trajectory, the training loop can reward the agent when it completes a meaningful phase of the task.

That changes how the model learns from long workflows. A completed retrieval phase, a valid tool call, or a correct subgoal can receive positive feedback even if the final task later fails. The failed phase can still be penalized, but the update does not have to treat the full trajectory as one undifferentiated outcome.

The main benefit is local credit assignment. The model gets a clearer connection between a behavior and its consequence: this phase worked, this phase failed, this subgoal moved the task forward, this action blocked the next step.

That local signal can make training more stable because the model is not relying only on a sparse terminal reward. Long tasks become a sequence of learnable segments rather than one large outcome judged at the end.

Milestone decomposition as the shared mechanism

The ALFWorld results show the same training pattern across several methods. Each method improves the reward signal by moving feedback closer to the part of the trajectory that caused progress or failure.

A broad episode-level reward, as used in GRPO, tells the agent whether the rollout worked. The reward gives weaker guidance about which intermediate decision helped or hurt the task.

Intermediate-state methods such as GiGPO and GRPO-λ make the update more specific. The training loop compares smaller parts of the rollout, so the model gets feedback on decisions closer to where progress changed.

Milestone-guided methods such as BEACON divide the trajectory into meaningful segments. A completed segment can still help training even when the full task fails later.

Hierarchical methods such as HiPER separate planning from execution. The planner learns which subgoal to choose. The executor learns how to carry out the steps under that subgoal.

The ALFWorld progression reads as a credit-assignment result. Success improves as the update moves from whole-rollout feedback toward intermediate states, milestone segments, and planner-executor structure.

Failed long-horizon rollouts often contain useful behavior. An agent can choose the right plan, navigate correctly, or complete a subgoal before failing later. Milestone decomposition lets training keep those useful parts instead of treating the whole rollout as one failed example.

How subgoal and adaptive milestone methods work

Milestone training can be implemented in several ways. Some methods change how credit is assigned across intermediate states. Others turn a long task into explicit subgoals, or adapt the milestone structure based on successful and failed trajectories.

That is the difference from the earlier evaluation examples. The methods below focus more directly on training: how to create denser reward signals, how to compare partial trajectories, and how to make long-horizon tasks easier for RL to optimize.

Credit assignment across intermediate states

Full-trajectory comparison is still coarse for long agent rollouts. A trajectory may succeed or fail because of a decision made many steps earlier, but the final reward has to stand in for the whole run.

Recent variants of Group Relative Policy Optimization (GRPO) make that comparison more local. GiGPO (Feng et al., 2025) and GRPO-λ move the advantage signal closer to intermediate states, so the model can learn from partial trajectory differences instead of waiting for the final episode reward.

For milestone training, the useful idea is local comparison. If two continuations start from a similar intermediate state, the training signal can show which continuation made better progress from that state. The model gets feedback closer to the decision that changed the trajectory.

Subgoal rewards for long-horizon agents

Subgoal methods make the milestone structure more explicit. Instead of training only from the final task result, the workflow is decomposed into intermediate objectives that can be rewarded during the rollout.

One example is MiRA (Wang et al., 2026), a subgoal-driven framework for long-horizon web agents that uses subgoal completion as denser feedback during training. The reward follows the workflow more closely: search, inspect, compare, act, and complete the final state.

In the reported WebArena-Lite result, a MiRA-style subgoal reward setup improves an open Gemma3-12B agent from 6.4% to 43.0%. The useful point is that the task becomes easier to optimize when the reward structure matches the task structure.

Adaptive milestone rewards for GUI agents

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.

The method also treats successful and failed trajectories differently: successful trajectories provide cleaner milestone anchors, while failed trajectories can still receive partial credit when they move toward useful intermediate states.

This is useful for GUI agents because progress should be tied to the state the agent reaches, not only the exact sequence of clicks or actions it used to get there. The milestone signal becomes less brittle while still giving the model denser feedback than a terminal reward.

What milestone-aware data and environment products need

Milestone-based development raises the bar for agent data products. Evaluation datasets, training environments, and reward pipelines all need access to the same underlying structure: milestones, checkpoint states, dependency paths, hard gates, and failure labels.

Product need	What it should provide
Progress visibility	Milestone labels, checkpoint states, or progress-rate scoring that show how far the agent got before failing
Phase-level diagnosis	Task decomposition into planning, navigation, tool use, execution, synthesis, or final-state completion
Dependency tracking	Reports that show when later steps were blocked by an earlier failure
Reliability measurement	Repeated-run evaluation with per-milestone success rates
Hard-gate validation	Checks for required files, parse validity, schema validity, or other binary preconditions
Partial-credit scoring	Weighted rubrics or subgoal scoring for valid but incomplete work
Training signal	Intermediate rewards, hierarchical task structure, and partial trajectory value for RL training
Product feedback loop	Failure labels mapped to evaluation data gaps, training data needs, or model-development actions

This is the point where evaluation data and training environments start to share the same design language. A milestone can act as an evaluation label, a partial-credit unit, a hard gate, or a reward signal depending on where it appears in the agent development loop.

That shared structure makes the data more useful after the score is reported. Teams can see what happened inside the trajectory, which progress was real, which phase blocked the rest of the task, and what data should be collected or trained on next.