M3-T3 — Distribution Shift and Compounding Errors

Learning objectives

After this lesson, you should be able to:

• Define covariate shift for a policy and say why a clone’s test distribution depends on the clone.
• Derive the quadratic-in-horizon bound on the cost of behaviour cloning and state its assumptions.
• Measure deviation from the expert against time and fit a growth exponent with an honest uncertainty.
• Describe how recovery data and noise injection reduce the shift, and what they cost.

The intuition

Picture a driver learning from a video of a careful chauffeur. The video shows the car in the middle of the lane, always. The learner drives well until a gust pushes it a handrail’s width to the left. That view never appeared in the video, so the learner has no example of what to do, and its guess is a little worse than usual. It drifts a little farther. Now it is in an even less familiar view, and the guess is worse again.

In the usual supervised setting the test examples are drawn from the same distribution as the training examples, so errors do not feed back. In imitation they do: the learner’s action decides the next observation. The states the learner sees at deployment, d_π̂, differ from the states the expert showed, d_π*. That mismatch is covariate shift, and it grows with the length of the episode because every step adds a chance to leave the data.

The mathematics

Setup

T

the horizon: the number of steps in an episode

π*, π̂

the expert and the learned policy (the clone)

d_π*, d_π̂

the distribution of states visited by the expert, and by the clone when it drives

ℓ(s, π̂)

a per-step cost of disagreeing with the expert in state s, between 0 and 1 (for example, the probability of choosing a different action)

ε

the average training-distribution error: ε = E over s from d_π* of ℓ(s, π̂)

J(π)

the total cost of a policy over T steps

The T-squared argument

Take a task in which the expert incurs no cost, J(π*) = 0. Suppose the clone disagrees with the expert in a state from the expert’s own distribution with probability at most ε at each step. Make three assumptions: (1) while the clone has made no mistake it is in the expert’s state distribution, so the next mistake probability is at most ε; (2) after the first mistake it can be anywhere, so assume the worst: it pays cost 1 at every remaining step; (3) the events at different steps follow the union bound, so the probability of at least one mistake in t steps is at most εt.

Ross, Gordon and Bagnell state the bound with a looser constant, J(π̂) ≤ J(π*) + T² ε, for any task with per-step cost in [0, 1], and constructed examples show that the quadratic dependence can be attained for a policy trained only on d_π*. A learner that is trained on its own distribution (lesson M3-T4, DAgger) has a cost bound that grows linearly in T, of the form J(π̂) ≤ J(π*) + O(T ε) provided it keeps the error ε low on the states it visits.

cost about ε T

What the argument assumes, honestly

The result is an upper bound. It says what can happen, and it is attainable on constructed problems; it does not say every cloned policy suffers a squared growth. In practice many clones are fine, and the useful lesson is the direction: the cost of the clone’s mistakes depends on what the mistakes lead to, and training error on the expert’s states cannot see that.

Covariate shift in general

Supervised learning guarantees nothing when the test inputs are drawn from a different distribution than the training inputs (lesson M2-T5). Here the test inputs come from d_π̂, which is a function of the model being trained: changing the model changes the test set. That coupling is what turns a small per-step error into a trajectory-level error, and it is the reason the track’s first rule of evaluation, held-out closed-loop rollouts (lesson M1-T5), cannot be replaced by held-out prediction error.

Reducing the shift

• Recovery data. Collect demonstrations that include off-path states and the expert’s corrections: start the expert from perturbed positions, or let a person drive back after a drift. The clone then has examples of what to do where it will be.
• Noise injection (DART). While the expert demonstrates, add noise to the executed action but record the expert’s clean action as the label. The robot visits the states a drifting learner would, and the label says how to return. Laskey et al. (2017) set the noise to match the error the learner is expected to make.
• Interactive correction (DAgger). Run the learner, ask the expert for the right action at the states the learner reached, add them, retrain. Lesson M3-T4.
• Model choice and data volume. A model that degrades gracefully off the data, or simply more demonstrations that cover more states, shrinks ε in the states that matter.

A worked example

All numbers come from RLCore. The expert is the RLCore expert, the clone is a 5-nearest-neighbour regressor on the four observation values, trained on 5 demonstrations (starts(1, 5, 'all'), 156 pairs). Both are rolled out from the same 100 held-out starts, starts(500, 100, 'all'). This is the experiment of lab M3-L2 (watch-the-clone-drift), done once with a fixed set of seeds.

The clone in closed loop. It reaches the goal from 61 of 100 starts, crashes into the pillar from 11 and times out after 80 steps from 28. The expert reaches the goal from all 100.

Deviation against time. At each step t = 1 .. 24 compute the distance between the clone’s and the expert’s position from the same start, then average over the 100 starts. If an episode has ended (goal reached or crash) the robot stays where it ended. The shortest expert episode on these starts is 23 steps, so up to step 22 every expert is still driving; at steps 23 and 24 a few experts have already stopped at the goal. Mean deviation, with the 95% confidence interval for the mean from the t distribution over the 100 starts:

The mean is an average over very different starts: at step 8 the typical start has a small deviation and a few have 2 to 3 m. The distribution is skewed; the confidence interval is a statement about the mean, not about a typical run.

A growth exponent, with its uncertainty. Fit a straight line to log(deviation) against log(t), so that deviation ≈ c · t^p. The 95% interval for p comes from resampling the 100 starts with replacement 1000 times (a bootstrap):

Read the table carefully. The growth is about linear over the whole window (p near 1.1), a little faster than linear (p = 1.3) during the first dozen steps, and then flat (p near 0.4), because the episodes end and the hall is finite. The point estimates of the whole window and the first half differ (1.12 against 1.34) and their intervals only partly overlap, so the exponent depends on where you look. No window shows a deviation growing like t², and that is not a contradiction of the quadratic bound: the bound is about the accumulated cost. Summing the deviation over time, as a cost would, gives 1.31 at step 8, 6.02 at 16 and 12.28 at 24, and the fitted exponent of that cumulative sum is 2.09. That is near 2 only because a deviation that grows linearly accumulates quadratically, which is the same fact seen twice, not an independent confirmation of the bound.

Why the deviation grows: the error moves with the clone. A deviation that grows linearly is expected from a constant action error alone, since in a velocity-controlled robot position is the integral of the action. The extra, compounding part is that the action error itself grows when the robot leaves the data. The mean norm of the action error, |π̂(o) − π*(o)|, at the same steps:

At step 0 the two are equal, because both are at the same start. Then they part: at step 12 the clone’s action error on its own states, 0.515, is three times the 0.163 it has on the expert’s states. Pooled over steps 0 to 23, the error is 0.105 on the expert’s states and 0.309 on the clone’s. This is covariate shift measured: the quantity the training loss sees is the left column, the quantity that determines the drift is the right one. (After step 16 the left column is small because the expert is near the goal, where the demonstrations are dense, while the clone is stuck elsewhere.)

Toy check of the bound. With ε = 0.01 and the worst-case assumption, the expected cost Σ (1 − 0.99^t) is 0.53 for T = 10, 10.9 for T = 50, 37.2 for T = 100 and 114.3 for T = 200, against ε T of 0.1, 0.5, 1.0 and 2.0. The ratio of the quadratic to the linear cost grows with T (5 at T = 10, 37 at T = 100). This is arithmetic about the bound, not a measurement of any robot.

Noise injection. Collect the 5 demonstrations again with Gaussian noise of standard deviation σ added to each executed expert action, recording the clean expert action at each visited state as the label. Fit the same 5-NN clone and score it on the same 100 starts. Because 5 demonstrations are a small sample, repeat with 20 different sets of 5 starts (seeds 1 to 20) and average:

With σ = 0.4 the paired difference in success over the 20 datasets is 14.1 starts of 100 (95% confidence interval 8.5 to 19.7), better in 19 of 20 datasets and worse in one. The effect is real in this setup, and its size varies a great deal with the dataset (range 45 to 100). Three cautions: the noisy datasets also contain slightly more pairs (174 against 152 on average), so part of the gain is just more data; the noise level was not tuned and DART chooses it from the learner’s error; and one expert in a noise-free, single-obstacle world is the easiest case. The result supports “recovery data helps this clone”, not a general number.

What the simulation simplifies. The world is deterministic and bounded, the expert is perfect and stops at the goal, so deviations saturate; real tasks with unstable dynamics, a bicycle that falls over or a drone that crashes have no such ceiling, and drift there is more severe. The exponents above describe this clone, this window and these 100 starts, not imitation in general.

Engineering implications and limitations

Evaluate in the loop, then explain

Prediction error on held-out demonstrations (lesson M2-T5) tells you whether the clone generalises across the expert’s states. Only closed-loop rollouts tell you what happens when its errors feed back. Do both; report the second.

Log the deviation, not just the outcome

Run the clone and, where an expert or planner is available, the expert from the same starts, and plot the distance against time with its interval. A curve that bends upward early is drift; one that jumps is a single bad state, often a missing piece of data.

Compare the states, not the actions

Plot where the clone goes against the visited cells of the dataset (lesson M3-T1). Failures cluster at the edge of the coverage. A simple monitor for a deployed clone is the distance from the current observation to its nearest training example (lesson M10-T5).

Collect recovery on purpose

Plan demonstrations that start away from the nominal path, add controlled noise or perturbations to the executed command with clean labels, and keep the corrections. More recovery data costs more operator time but it targets exactly the states the clone reaches.

Keep the horizon short where you can

Fewer steps between decisions means fewer chances to drift. Action chunking (lesson M3-T2), a lower-rate high-level policy, or a hand-written low-level controller that returns the robot to the path all shorten the effective horizon.

Do not tune on the test starts

The noise level, the number of neighbours and the window of the exponent fit are all choices. Fix them on separate starts, as in lesson M1-T5.

Common misconceptions

Engineering takeaways

1. Covariate shift: a clone is trained on the expert’s state distribution and tested on its own, which its mistakes shape.
2. Under worst-case assumptions the cost of behaviour cloning can grow as ε T², against ε T for a learner trained on its own states (Ross, Gordon and Bagnell, 2011); with ε = 0.01 and T = 100 that is 37.2 against 1.0.
3. On Scout, a 5-demonstration 5-NN clone drifted from 0.34 m at step 8 to 0.8 m at step 24; the fitted growth exponent was 1.12 (95% interval 0.95 to 1.30) for steps 2 to 24, higher early and flat late.
4. The clone’s action error on its own states reached 0.515 at step 12 against 0.163 on the expert’s states: the training loss sees only the second.
5. Recovery data and noise injection with clean labels reduce the shift (success 64.8 to 78.9 of 100 on average here); interactive correction removes it more directly (lesson M3-T4).

References and further reading

The primary analysis of compounding errors in imitation and the noise-injection method.

• S. Ross, G. Gordon and J. A. Bagnell, “A Reduction of Imitation Learning and Structured Prediction to No-Regret Online Learning”, AISTATS, 2011.
• S. Ross and J. A. Bagnell, “Efficient Reductions for Imitation Learning”, AISTATS, 2010.
• M. Laskey, J. Lee, R. Fox, A. Dragan and K. Goldberg, “DART: Noise Injection for Robust Imitation Learning”, Conference on Robot Learning (CoRL), 2017.
• D. A. Pomerleau, “ALVINN: An Autonomous Land Vehicle in a Neural Network”, Advances in Neural Information Processing Systems 1, 1989.

Knowledge check

Three conceptual questions. Write an answer, then reveal the explanation. Your answers stay in your browser.

What’s next

Next: lesson M3-T4, DAgger and Interactive Imitation, lets the learner drive, asks the expert for the right action at the states it reaches, and trains on them, so the training distribution matches the one the clone creates.

Related content

Nothing below is required to finish this lesson.

• Before
  M3-T2: Behavior Cloning

  Frame behaviour cloning as supervised learning of actions from observations, and write its loss.

• Lab
  M3-L2: Watch the Clone Drift

  The clone is fine for ten seconds and then leaves the path: measure the drift and show it grows with the horizon.