Derive How Behavior-Cloning Errors Grow Across a Trajectory

A cloned policy can score 98% on held-out demonstration states and still walk off a cliff in four seconds. The metric and the rollout are measuring two different worlds.

You have probably already met the named failure mode: behavior cloning learns a state-to-action map from expert demonstrations, and at rollout time the policy visits states the expert never showed it. That is covariate shift. What usually stays vague is the arithmetic. How fast does the drift actually accumulate? What assumption makes a clean bound true? And why does your validation number fail to plug into it?

This article answers one bounded question: under a stated per-step error assumption, what is the probability that a rollout of length $H$ contains at least one mistaken action? The answer is a short union-bound derivation. It is illustrative, not universal — it says nothing about any specific trained network unless you can verify the assumption it rests on. That honesty is the point. The derivation tells you exactly which assumption buys the guarantee, and therefore exactly what to fix when the guarantee evaporates.

Why a Low Validation Error Still Drifts

Picture the standard training loop. You collect expert trajectories, split state-action pairs into train and validation, fit a classifier or regressor, and watch validation loss fall. Teacher forcing keeps the model on the expert's states at every step, so each prediction is graded in the comfortable neighborhood the demonstrations cover.

Then you close the loop. The policy picks an action, the environment transitions, and the next input is a state the policy itself produced. Early on, those states still resemble the expert's. A few steps later, they do not. The model is now extrapolating, and its errors are no longer independent draws from the validation distribution — they are consequences of its own past choices.

The mismatch fits in one sentence: training states come from the expert's distribution, rollout states come from the learner's own actions. The validation number is an average over the first distribution. The rollout lives in the second.

So the useful question is not "is my validation error low?" It is "how does a per-step disagreement rate translate into a probability of at least one mistake across a horizon?" That is what we derive next. The payoff is a number you can compute on the back of an envelope, plus a checklist for recognizing when that number is meaningless.

Notation and the Assumption That Does the Work

Before any algebra, pin down the symbols.

Horizon $H$. The number of decision steps in one rollout, indexed $t = 0, 1, \dots, H-1$. If your task runs for 200 control steps, $H = 200$.

Per-step error rate $\varepsilon$. The conditional probability that the learner chooses an action different from the expert's, given the state the learner is actually in at that step. Formally, at step $t$ in state $s_t$:

$\varepsilon_t = P\big(\hat{\pi}(s_t) \neq \pi^\star(s_t) \mid s_t\big)$

where $\hat{\pi}$ is the learner and $\pi^\star$ is the expert.

The assumption that does the work. We assume $\varepsilon_t \le \varepsilon$ at every step $t$, and at every state the learner can reach before its first mistake.

That qualifier is not decoration. It is what keeps the argument from being circular. If we demanded the bound hold at every state the learner could ever reach — including states reachable only after a mistake — we would be assuming the conclusion. Restricting to the pre-mistake region means the assumption is about states the learner arrives at while still behaving correctly, which is a region the expert's demonstrations plausibly cover.

Now contrast this with the quantity you can actually measure. From a demonstration dataset, you can estimate the average disagreement rate over states drawn from the expert's distribution:

$\hat{\varepsilon}_{\text{demo}} = \mathbb{E}_{s \sim d^{\pi^\star}}\big[\mathbf{1}\{\hat{\pi}(s) \neq \pi^\star(s)\}\big]$

This is an average over expert states only. The derivation needs a bound at every reachable rollout state. Those are different objects, and the gap between them is where behavior cloning error compounding lives.

Picture two lanes on a road. The expert lane is smooth and well-marked. The learner lane tracks it closely at first, then a small steering error nudges the car toward the shoulder. The shaded region — states the learner can reach before its first mistake — is the only territory where the assumption is claimed to hold. Past the first divergence, the map goes blank.

Deriving the Union Bound Step by Step

Define the event we care about:

$A = \{\text{at least one mistaken action in the } H\text{-step rollout}\}$

We want an upper bound on $P(A)$.

Step 1: Take the complement. The rollout is clean — no mistakes at all — only if every single step is correct. So $A^c$ is the event "all $H$ steps correct."

Step 2: Factor the clean-rollout probability. By the chain rule of probability:

$P(A^c) = \prod_{t=0}^{H-1} P\big(\text{step } t \text{ correct} \mid \text{steps } 0 \dots t-1 \text{ correct}\big)$

Each factor is a conditional probability of being correct at step $t$, conditioned on the history being clean up to that point. And here is where the assumption gets consumed: if the history is clean, the state at step $t$ is a pre-mistake state, so the conditional error probability is at most $\varepsilon$. Therefore each factor is at least $1 - \varepsilon$:

$P(A^c) \ge (1 - \varepsilon)^H$

Step 3: Flip back to the event of interest. Since $P(A) = 1 - P(A^c)$:

$P(A) \le 1 - (1 - \varepsilon)^H$

Step 4: Apply the standard inequality. For $\varepsilon \in [0, 1]$, the Bernoulli inequality gives $(1 - \varepsilon)^H \ge 1 - H\varepsilon$. Substituting:

$P(A) \le 1 - (1 - H\varepsilon) = H\varepsilon$

Step 5: Cap at one. A probability cannot exceed 1, so the final bound is:

$P(\text{at least one mistake by step } H) \le \min(1, H\varepsilon)$

Read the result as a mechanism, not a ritual. The bound is linear in $H$. Doubling the horizon doubles the ceiling on failure probability. It is also vacuous once $H\varepsilon \ge 1$ — at that point the bound says only "the probability is at most 1," which you already knew.

Notice what the derivation never used: no reward function, no transition model, no claim that the expert is optimal. The entire argument rests on one conditional error assumption. That is the load-bearing wall.

One boundary to state before moving on: the event $A$ is action disagreement, nothing more. A different action does not automatically mean the learner leaves the expert's state support, and it certainly does not mean the task fails. A wrong action can land in a state the demonstrations still cover, and the environment may absorb the deviation entirely. Connecting action disagreement to support departure or task failure requires extra assumptions about how action differences propagate through the transition dynamics and how much the task penalizes them. Keep those links separate, or the arithmetic will quietly claim more than it proved.

A Worked Example: Watch the Bound Go Vacuous

Take $\varepsilon = 0.01$ — a 1% per-step disagreement rate, which sounds excellent. Tabulate $\min(1, H\varepsilon)$:

At $H = 10$, the bound is informative: at most a 10% chance of at least one mistake. At $H = 100$, the bound saturates. Beyond that, the theory has nothing left to say.

The interpretation matters more than the numbers. A 1% per-step disagreement rate is not a 1% rollout failure rate. It is a per-step tax that compounds across the trajectory. This is why long-horizon tasks are the hard case for pure imitation: the same model quality that gives a useful ceiling at 20 steps stops certifying anything at 200.

Two honesty notes. First, the true failure probability may be far below the bound. The bound is a ceiling, and a loose one — it does not claim the worst case occurs, only that it cannot be exceeded. Second, the bound assumes $\varepsilon$ is constant. In reality, the per-step error rate grows as the learner drifts, which is the subject of the next section.

Where the Assumption Breaks: Covariate Shift

Here is the precise reason a demonstration-distribution error rate does not establish the rollout bound.

The measurable quantity $\hat{\varepsilon}_{\text{demo}}$ is an average over the expert's state distribution. The derivation needs a bound at every state the learner can reach before its first mistake. These coincide only if the learner's rollout states stay inside the expert's distribution — which is exactly what we are trying to prove.

The feedback loop closes the trap. A wrong action at step $t$ changes the state at step $t+1$. That new state may be outside the demonstration support, where the learner's conditional error rate is higher than $\varepsilon$. A higher error rate makes another mistake more likely, which pushes the state further out. The per-step rate is not a fixed constant along a rollout; it is a function of how far the learner has already drifted.

This is the same distribution mismatch you have met before, but now you can see why it invalidates the arithmetic rather than merely making it pessimistic. The derivation's assumption is a uniform bound over reachable states. Covariate shift is the mechanism that makes that uniformity false. A small in-distribution error can coexist with a large out-of-distribution error, and the bound silently assumes the latter away.

State the boundary clearly: the derivation is valid under the assumption and says nothing without it. If you cannot argue that your per-step error is bounded across the states your policy actually visits, you have a number, not a guarantee.

What Actually Restores the Assumption

If the problem is that the assumption fails off the demonstration path, the fix is to make the assumption true where the rollout lives. Two approaches do this directly.

Expert correction. Instead of querying the expert only on the expert's own trajectory, query the expert at states the learner actually visits. If the learner drifts left, ask the expert what to do from the drifted state. Now the error rate is measured on the rollout distribution, which is the distribution the derivation cares about.

On-policy data aggregation. Roll out the current learner, label the visited states with expert actions, add them to the training set, retrain, and repeat. The training distribution chases the rollout distribution. Each round pulls the learner's reachable states back under the expert's coverage.

Why is this the honest fix? Because it targets the assumption directly instead of hoping the expert distribution happens to cover the learner's mistakes. The cost is real: environment interaction, expert availability, and repeated training rounds. You are trading data and compute for a more defensible guarantee.

Be careful about what these methods actually deliver. Querying and training on learner-visited states exposes the learner to the states where it errs and can reduce the error there. That is not the same as certifying a uniform conditional bound across every reachable pre-mistake state. The assumption the derivation needs is stronger than the coverage these loops typically provide, so treat them as ways to make the assumption more plausible — not as a proof that it holds.

A cheaper middle ground exists — noise injection during expert rollouts, or stability-oriented training objectives that penalize divergence from expert states. These reshape the training data distribution to expose the learner to plausible deviations. The caveat: they make the assumption more plausible without proving a bound. Do not read a stability penalty as a certificate.

I would not assert a universal rate for any of these methods. The theory gives a conditional statement, and the practical claim is only that these methods make the condition more likely to hold.

When This Bound Is Useful and When It Misleads

Use the derivation when you want a quick sanity check on whether a per-step error rate is compatible with your task horizon. Multiply your measured $\varepsilon$ by $H$. If the product is comfortably below 1, the bound is informative and your task is plausibly within reach of pure imitation. If the product approaches or exceeds 1, the bound can no longer certify a useful low disagreement probability — it is telling you to measure rollout error directly or change the data-coverage loop.

Use it when you need to argue that a long-horizon task requires either a much smaller $\varepsilon$ or a mechanism that repairs distribution shift. The bound makes that tradeoff quantitative.

Do not use it as a performance prediction for a specific trained network. It is a ceiling under an assumption you probably cannot verify.

Three mistakes to avoid:

Common mistake: Reporting a demonstration-distribution error rate and treating it as $\varepsilon$ in this bound. The bound needs a rollout-state conditional rate. These are different quantities, and the gap between them is the whole problem.

Common mistake: Assuming the bound is tight. The true failure probability can be much lower. The bound saturates at 1 and stays there.

Common mistake: Reading a saturated bound as proof that cloning is hopeless. When $H\varepsilon \ge 1$, the bound has simply stopped certifying anything. It does not show the actual disagreement probability is high, and it does not show that better approximation or more training cannot help. It shows that this particular argument can no longer vouch for you.

My practical rule: if $H\varepsilon$ is close to or above 1, stop trusting the bound and go measure rollout-state error instead. The bottleneck may be approximation quality, but the theory has stopped telling you that — and the distribution your training data covers is the first thing to inspect.

The Habit Worth Keeping

The derivation is short enough to reproduce on paper, and that is deliberate. Before you trust a cloned policy, run three checks. Ask which state distribution the error rate was measured on. Multiply that rate by the horizon. Check whether the product is still informative.

If it is, you have a defensible reason to expect the policy to hold together. If it is not, you have learned something more useful than any validation score: the bound has gone quiet, and the next move is to measure error where the rollout actually lives.

The natural next step is to collect rollout-state data — either by querying an expert at the states your learner visits, or by moving toward methods that learn from environment feedback rather than demonstrations alone. The bound is a diagnostic. It tells you when the arithmetic stops protecting you, not whether imitation learning was a mistake.