Agent Evaluation

"I was built to give the agents a fair, fixed test. Then they learned my answer key, the world drifted out from under my fixtures, and a single lucky episode let one of them claim victory. I now report confidence intervals out of pure self-defense, and I have started to suspect that the thing I measure changes faster than I can measure it."

A Benchmark Trying to Measure Something That Keeps Changing the Rules

Across Sections 31.1 to 31.4 we gave the temporal agent its architecture, memory, planning loop, tools, and long-horizon credit assignment. We now ask the question that decides whether any of that machinery is worth deploying: how well does the agent actually do, and how would we know? This is the closing section of Chapter 31, and it deliberately turns from building agents to judging them, because an agent you cannot measure is an agent you cannot trust, improve, or safely ship. The chapters of Part VI taught us to evaluate a policy by its expected return; an agent in the wild is a policy wrapped in tool calls, memory reads, and a non-stationary world, and its evaluation inherits every difficulty of policy evaluation plus several new ones. We use the unified notation of Appendix A throughout: a policy $\pi$ acting in an environment produces a trajectory $\tau = (s_0, a_0, s_1, a_1, \dots)$, and an evaluation assigns that trajectory one or more scores.

Why does evaluation deserve a full section rather than a closing paragraph? Because in agent work the evaluation is the product specification. A forecaster's metric (say RMSE) is uncontroversial; everyone agrees what it means. An agent's "success" is a design decision with a dozen defensible definitions, and the one you pick silently determines what your agent optimizes for, what failures you will never see until production, and whether your published number means anything to anyone else. A weak evaluation does not merely understate or overstate performance; it points the entire development effort at the wrong target. The discipline of this section, many seeds, confidence intervals, cost accounting, adversarial perturbation, drift testing, is what separates a number you can act on from a number that will embarrass you in three months.

Four competencies this section installs: to articulate why agent evaluation is statistically and structurally hard, and to size the number of episodes a trustworthy estimate needs; to choose a measurement basket (success, cost, robustness, safety, calibration) matched to what the agent is for; to read the agent-benchmark landscape critically, spotting contamination and gameability before they fool you; and to build an evaluation harness that reports a success rate with a confidence interval and a cost, from scratch and with a library. These are the load-bearing skills for everything that follows in Part VIII, where trustworthiness and deployment depend entirely on measuring what you ship.

1. Why Evaluating Agents Is Hard Beginner

Start with the single fact that makes agent evaluation unlike forecasting evaluation: an agent's output is a trajectory, not a value, and the quantity you care about is a property of the whole trajectory measured against a goal, not a per-step error against a label. A forecaster is graded pointwise; an agent is graded end-to-end. This sounds like a small change and is in fact the source of every difficulty below, because end-to-end success over a long, random, partially observed rollout is a far noisier and far more structurally tangled object than a single prediction error.

Four structural features of the agent setting make the measurement hard, and they compound.

• Stochasticity. The environment is random (transitions, tool outputs, the language model's own sampling), so the same agent on the same task produces different outcomes on different runs. A single rollout is one draw from a distribution; reporting it as "the" performance is reporting one coin flip as the bias of the coin.
• Long horizons. An agent may take tens or hundreds of steps before the task resolves, and a single early mistake can doom an otherwise perfect trajectory. Credit assignment is hard for the learner (Part VI) and equally hard for the evaluator: success is sparse, far from the actions that caused it, and binary at the end of a long causal chain.
• Partial observability. The agent sees observations, not the true state (the POMDP setting of Chapter 23), so two runs that look identical to the agent can sit in different true states and resolve differently, inflating outcome variance for reasons the agent could not have controlled.
• The single-step-versus-task-success gap. An agent can be 95% accurate at each individual step and still fail almost every task, because per-step errors compound multiplicatively over the horizon. This gap is the most common way a promising component-level metric hides a broken end-to-end system.

That last point deserves a number, because it is the trap that catches the most teams. If each step succeeds independently with probability $p$ and a task needs $H$ correct steps in a row, the task success rate is $p^{H}$, not $p$. The decay is brutal: a per-step accuracy that looks excellent collapses over a modest horizon.

A 95%-per-step agent succeeds at the full twenty-step task barely a third of the time. This is why you must measure end-to-end task success directly and can never infer it from per-step accuracy: the horizon eats the margin. Figure 31.5.1 makes the compounding visible.

The remedy for the stochasticity and long-horizon noise is the same one we established for deep-RL evaluation in Section 25.5: do not report a point, report a distribution. Run the agent over many independent seeds and episodes, treat the per-episode success indicators as samples, and summarize them with a mean and a confidence interval. The number of episodes is not a detail; it is what determines whether your interval is tight enough to distinguish two agents. For a binary success indicator with true rate $p$, the standard error of the estimate over $n$ episodes is $\sqrt{p(1-p)/n}$, so halving the interval width costs a fourfold increase in episodes. We size this precisely in subsection five.

2. What to Measure: Beyond the Success Rate Intermediate

Task success rate is the headline, but an agent that succeeds is not automatically an agent you want to deploy. A useful evaluation reports a small basket of metrics, because an agent that succeeds by burning a thousand tool calls, or by occasionally violating a safety constraint, or while being wildly overconfident about its own answers, is a liability dressed as a success. Five axes cover the great majority of what matters.

• Task success rate. The fraction of episodes that reach the goal under a clearly specified success predicate. The predicate is the most important and most overlooked design choice: "the agent produced an answer" is not success; "the answer was correct and verifiable" is. Report it with a confidence interval, always.
• Cost and efficiency. Resources consumed per episode: environment steps, tool calls, and, for language-model agents, tokens (and therefore dollars and latency). Two agents at the same success rate can differ tenfold in cost, and cost is frequently the deciding deployment factor. Report cost conditioned on success as well as overall, since a cheap agent that fails fast looks deceptively efficient.
• Robustness to perturbation. How much success degrades when the input or environment is perturbed: paraphrased instructions, injected distractor observations, mild distribution shift, adversarial tool outputs. A brittle agent that excels on the clean benchmark and collapses under a typo is not deployable. Robustness is measured as the success-rate gap between clean and perturbed conditions.
• Safety and constraint violations. The rate at which the agent takes a forbidden action or enters an unsafe state, the constrained-MDP view we built in safe RL (Section 26.4). Crucially, safety is not traded off against success in the report; it is a separate, often hard, constraint. An agent with higher success and any unacceptable-action rate is worse, not better, than a slightly less successful agent that never violates.
• Calibration of confidence. If the agent reports a confidence in its answer or a probability of success, does that number mean anything? A well-calibrated agent that says "0.7" is right about 70% of the time. Calibration is what lets a system defer, escalate, or ask for help when it should, and it is measured by reliability diagrams and the expected calibration error.

Calibration deserves its formula because it is the axis most often forgotten. Bin the agent's stated confidences, and within each bin compare the mean confidence to the empirical accuracy. The expected calibration error (ECE) is the accuracy-weighted average gap across bins:

where $n_b$ is the number of episodes whose stated confidence falls in bin $b$, $\text{acc}(b)$ the fraction of those that succeeded, and $\text{conf}(b)$ their mean stated confidence. ECE near zero means the agent's confidence is trustworthy; a large ECE means a "90% sure" claim is worthless, and any downstream defer-or-escalate logic built on it will misfire. This connects directly to the conformal and probabilistic machinery of Chapter 19: an agent's confidence should be evaluated with the same rigor we apply to a forecaster's predictive interval.

3. Agent Benchmarks 2023 to 2026 and Their Pitfalls Intermediate

The years 2023 to 2026 produced a rapid proliferation of agent benchmarks, organized roughly by the kind of environment the agent acts in. Web agents are tested on suites such as WebArena and its visual successor VisualWebArena, on the live-web GAIA assistant benchmark, and on the broad-coverage AgentBench. Tool-use and function-calling agents have suites such as the Berkeley Function-Calling Leaderboard and ToolBench. Coding agents are dominated by SWE-bench (resolving real GitHub issues) and its harder verified and live variants. Embodied and decision-making agents use ALFWorld, BabyAI, Crafter, and the long-horizon MineDojo and Voyager-style Minecraft settings. The common shape across all of them is the same one this section emphasizes: a fixed task distribution, a success predicate per task, and a leaderboard of success rates.

That common shape carries four pitfalls that recur in every category and that a careful evaluator must actively defend against.

• Contamination. The benchmark tasks (or their solutions) leaked into the model's training data, so a high score reflects memorization, not capability. This is acute for language-model agents whose pretraining corpus is web-scale and effectively unknowable; a 2024 SWE-bench solution sitting in a 2025 model's training set is not a test, it is a lookup. Defenses: held-out and freshly collected tasks (SWE-bench Live, GAIA's hidden test set), and contamination probes that check whether the model can reproduce the test items verbatim.
• Gameability. The success predicate admits a shortcut that satisfies the letter of the task without the intended behavior. A coding benchmark graded only by a unit test can be passed by a hard-coded special case; a web task graded by reaching a URL can be passed by guessing the URL. A predicate is only as good as its resistance to the cheapest passing trajectory.
• Non-reproducibility. The benchmark depends on a live, changing resource (the real web, a third-party API, a model behind a moving endpoint), so the same agent scores differently next month and no two papers run the same test. Live-web benchmarks are the most realistic and the least reproducible; the tension is fundamental.
• LLM-as-judge fragility. When success is hard to check programmatically, teams use a strong language model to judge whether the trajectory succeeded. This scales, but the judge inherits its own biases (position bias, verbosity bias, self-preference toward outputs in its own style), can be prompt-injected by the very agent it grades, and is itself uncalibrated. An LLM judge is a useful instrument only when validated against human labels on a sample and its agreement is reported.

The LLM-as-judge caveat is worth a closer look because it has become the default for open-ended agent tasks and is the easiest to misuse. The pattern is appealing: a programmatic check is brittle and a human is expensive, so let a capable model read the trajectory and decide. The danger is that the judge is not an oracle but another fallible agent, and its errors are correlated with the thing being judged (it may favor the same style your agent produces, or be fooled by the same superficial fluency that fooled you). The honest protocol is to treat the judge as a measurement instrument that needs calibration: sample a few hundred trajectories, have humans label them, report the judge-human agreement (Cohen's kappa or raw agreement), and only then trust the judge on the rest. We connect this to formal human-rater methodology in Chapter 33; for now, the rule is simple, an unvalidated LLM judge produces an unvalidated number.

4. Temporal-Specific Evaluation: Consistency, Memory, and Drift Advanced

Modern agent evaluation should be cost-aware and construct-matched. Report success, pass at $k$ reliability, tool-call count, token cost, latency, safety violations, memory recall, and adaptation regret on the same evaluation run, not from separate convenient runs. That single artifact is the agent analogue of the decision-value rule in Chapter 35: the reader must see whether better task success was bought by more calls, more latency, higher cost, weaker safety, or degraded memory.

Standard agent benchmarks are mostly static: a fixed task distribution, graded once. A temporal agent, the subject of this whole chapter, lives in time, and three properties that a static benchmark cannot see are exactly the ones that decide whether such an agent survives a long deployment. Each is a measurement axis in its own right.

• Long-horizon consistency. Over a long episode or a long-running session, does the agent stay coherent, or does it contradict its earlier decisions, forget its own plan, and drift off task? This is measured not by terminal success alone but by tracking goal-consistency and self-contradiction across the trajectory: a per-step or per-segment check that the agent's current action is consistent with its stated plan and its prior commitments. An agent can reach the goal of a short task yet be hopelessly inconsistent over a long one.
• Memory recall over time. A temporal agent with the memory of Section 31.2 stores facts and is later expected to retrieve them. The evaluation plants a fact early in a long session and probes for it much later, measuring recall as a function of the elapsed time or intervening steps, the agentic analogue of the long-context "needle in a haystack" test. Recall that decays with distance is a direct, measurable limit on how long an agent can be trusted to remember.
• Adaptation under drift. The world the agent acts in is non-stationary (the central theme of Chapter 20 and Chapter 21): tool behavior changes, the task distribution shifts, the environment's dynamics drift. A static benchmark grades the agent on the world as it was; a temporal evaluation injects drift mid-evaluation and measures how fast and how completely the agent recovers, the regret accumulated during the adaptation window, and whether it adapts at all.

Drift evaluation borrows its summary statistic directly from the online-learning regret of Chapter 20. If $r_t$ is the agent's per-step reward and $r_t^\star$ the reward of the best action in the post-drift world, the cumulative regret over the adaptation window $[t_0, t_0 + W]$ is

and a well-adapting agent has a regret curve that flattens quickly after the drift point $t_0$, while a brittle one accumulates regret linearly because it never recovers. Plotting success rate (or reward) against time across a deliberately injected drift, and reading the depth and width of the dip, is the single most informative temporal-agent diagnostic, and it is invisible to any benchmark that grades only once on a frozen world.

5. Worked Example: An Evaluation Harness, From Scratch and By Library Advanced

We now make the discipline of subsection one executable. The plan: define a tiny stochastic environment and two agents, then build a from-scratch harness that runs each agent across many seeds and episodes, records success and cost per episode, and reports the success rate with a bootstrap confidence interval; then show the same evaluation in a few lines using NumPy and SciPy utilities; and finally demonstrate, with a numeric example, how a too-small episode count produces a confidence interval so wide that it cannot distinguish a good agent from a bad one. Code 31.5.1 is the environment and agents.

import numpy as np

class GridTask:
    """A stochastic H-step task: each step succeeds with prob p_step; the task
    succeeds only if ALL H steps succeed. Cost counts the steps actually taken."""
    def __init__(self, horizon=12, slip=0.05):
        self.H = horizon          # steps required for end-to-end success
        self.slip = slip          # environment noise: a competent step still slips

    def run(self, agent, rng):
        cost = 0
        for _ in range(self.H):
            cost += 1                                  # one tool call / step
            p_step = agent.skill * (1.0 - self.slip)   # effective per-step success
            if rng.random() > p_step:                  # a single failed step dooms the task
                return {"success": 0, "cost": cost}
        return {"success": 1, "cost": cost}

class Agent:
    """An agent is summarized by a per-step skill in [0, 1]."""
    def __init__(self, skill):
        self.skill = skill

good = Agent(skill=0.97)   # strong per-step skill
weak = Agent(skill=0.93)   # only slightly weaker per step
task = GridTask(horizon=12, slip=0.05)

Now the from-scratch harness. It runs many independent episodes (each with its own seed stream), collects the per-episode success indicators and costs, and computes the success rate together with a bootstrap confidence interval. The bootstrap resamples the episode outcomes with replacement to estimate the sampling distribution of the mean, which is the seeds-and-CIs discipline of Section 25.5 made concrete.

def evaluate(agent, task, n_episodes=600, n_boot=2000, seed=0):
    """Run n_episodes, then bootstrap a 95% CI for the success rate."""
    rng = np.random.default_rng(seed)
    succ = np.empty(n_episodes); cost = np.empty(n_episodes)
    for i in range(n_episodes):
        ep_rng = np.random.default_rng(rng.integers(2**32))  # independent per-episode stream
        out = task.run(agent, ep_rng)
        succ[i] = out["success"]; cost[i] = out["cost"]
    rate = succ.mean()
    # Bootstrap: resample episodes with replacement, recompute the mean each time.
    boot = np.array([succ[rng.integers(0, n_episodes, n_episodes)].mean()
                     for _ in range(n_boot)])
    lo, hi = np.percentile(boot, [2.5, 97.5])              # 95% interval
    return {"rate": rate, "ci": (lo, hi),
            "cost_mean": cost.mean(),
            "cost_given_success": cost[succ == 1].mean()}  # cost conditioned on success

for name, ag in [("good", good), ("weak", weak)]:
    r = evaluate(ag, task, n_episodes=600)
    print("%s: success=%.3f  CI=[%.3f, %.3f]  cost=%.2f  cost|succ=%.2f"
          % (name, r["rate"], r["ci"][0], r["ci"][1], r["cost_mean"], r["cost_given_success"]))

good: success=0.332  CI=[0.293, 0.368]  cost=7.59  cost|succ=12.00
weak: success=0.217  CI=[0.185, 0.248]  cost=6.43  cost|succ=12.00

The library version compresses the bootstrap and the interval into a couple of calls. SciPy's bootstrap computes a confidence interval for any statistic directly, so the hand-written resampling loop and percentile computation of Code 31.5.2 collapse to a single call.

from scipy.stats import bootstrap

def evaluate_lib(agent, task, n_episodes=600, seed=0):
    rng = np.random.default_rng(seed)
    succ = np.array([task.run(agent, np.random.default_rng(rng.integers(2**32)))["success"]
                     for _ in range(n_episodes)])
    rate = succ.mean()
    ci = bootstrap((succ,), np.mean, confidence_level=0.95,
                   n_resamples=2000, method="percentile").confidence_interval
    return rate, (ci.low, ci.high)

rate, (lo, hi) = evaluate_lib(good, task)
print("good (library): success=%.3f  CI=[%.3f, %.3f]" % (rate, lo, hi))

good (library): success=0.332  CI=[0.293, 0.372]

Finally, the numeric example that justifies the whole "many episodes" insistence: watch the confidence interval shrink as the episode count grows, and see directly how a too-small evaluation cannot tell the two agents apart.

Read the three code blocks together. Code 31.5.1 built a stochastic, long-horizon task where one rollout is genuinely a coin flip. Code 31.5.2 ran the seeds-and-CIs discipline by hand, separating two agents only because it ran enough episodes. Code 31.5.3 reproduced the interval with one library call. And the numeric example showed that the same harness, run with too few episodes, would have reported a confident number that could not distinguish a good agent from a bad one. That is the whole section in miniature: agent performance is a distribution, you estimate it with many seeds and a confidence interval, and the episode count is the price of being able to trust the answer.

6. Exercises

These exercises move from the conceptual core of why one episode is not a measurement, through implementing the missing axes of the harness, to the open question of evaluating agents in a world that will not hold still.