Lecture 02 · Part 1

Imitation Learning

Before any reinforcement learning: can we learn policies by plain supervised learning on demonstrations? Levine sets up the course's notation, shows why behavioral cloning is undermined by compounding errors — a violation of the i.i.d. assumption — and quantifies the damage with an epsilon-T-squared bound. The fixes span smarter data collection, expressive multimodal policy classes, goal conditioning, and DAgger, which repairs the data distribution instead of the policy.

▶ Lecture videos (5 parts) Slides (current revision, PDF) ↗

Policies, observations, and states

A policy is a mapping from what the agent observes to what it does — “not such a strange object”: an image classifier maps inputs $x$ to labels $y$ ; a policy maps observations $o$ to actions $a$ . We write it $\pi_\theta(a_t \mid o_t)$ , with $\theta$ the parameters and $t$ a discrete time index, because decisions live inside a temporal process where the action you pick changes what you observe next. In full generality policies are distributions over actions — a deterministic policy is just the special case putting probability one on a single action — and training distributions is simply more convenient, exactly as in supervised learning. Discrete action spaces look like classification; continuous ones commonly output the mean and covariance of a Gaussian.

The genuinely new object is the state $s_t$ , distinct from the observation $o_t$ . Levine’s example: a picture of a cheetah chasing a gazelle. The pixels are the observation; the state is what produced them — positions, velocities, the concise and complete physical description of the world. A car blocking the camera changes the observation but not the state. You can always render $o_t$ from $s_t$ ; you cannot in general recover $s_t$ from $o_t$ . States form a chain with transition probabilities $p(s_{t+1} \mid s_t, a_t)$ — “basically the physics of the underlying world.”

Some later algorithms will require policies on states $\pi_\theta(a_t \mid s_t)$ ; others happily consume partial observations. Be warned that practitioners “have a very bad habit” of confounding $o$ and $s$ — usually benignly, where it doesn’t matter. Notational aside: controls people write states as $x$ and actions as $u$ ; this course uses the $s, a$ convention descending from Bellman’s dynamic programming.

Behavioral cloning: supervised learning of behaviors

The running example is driving: observations are dashboard-camera images, actions are steering commands. Have humans drive, record image–steering pairs into a dataset of tuples $(o_t, a_t)$ , and train a network exactly the way you’d train a classifier:

$\theta^\star = \arg\max_\theta \sum_{i=1}^{N} \sum_{t=1}^{T} \log \pi_\theta\!\left(a_t^{(i)} \mid o_t^{(i)}\right)$

This idea is old. ALVINN — Autonomous Land Vehicle In a Neural Network, 1989 — trained on human driving data with “a whole heaping load of hidden units, five whole hidden units” over a 30-by-32 image, and could follow lanes.

Is it guaranteed to work? No. Picture state versus time: a black training trajectory and a red execution of the learned policy from the same start. Any learned model makes at least tiny mistakes, and each tiny mistake puts the policy in a state slightly different from training — where it makes a slightly bigger mistake, landing somewhere more unfamiliar still. Errors compound. Regular supervised learning never faces this, and the reason is the i.i.d. assumption: there, one prediction has no bearing on the next input, whereas here the action you output determines the next observation.

Yet in practice naive cloning can work. NVIDIA’s driving system, after 3,000 miles of data, followed lanes and dodged cones competently. Buried in that paper is the detail that matters: the car had three cameras. The left-facing camera’s images were labeled not with the human’s actual steering command but with one nudged right; the right-facing camera, nudged left. When the policy later drifts left, it sees something resembling those left-camera frames — a state no longer unfamiliar, labeled with the correction that steers back.

How bad can it be? Distributional shift, quantified

The training set comes from the human’s observation distribution $p_{\text{data}}(o_t)$ ; the policy is tested on its own distribution $p_{\pi_\theta}(o_t)$ , which differs precisely because the policy doesn’t drive exactly like the person. Training maximizes $\mathbb{E}_{o_t \sim p_{\text{data}}(o_t)}[\log \pi_\theta(a_t \mid o_t)]$ , but log-probabilities high under $p_{\text{data}}$ say nothing about states sampled from $p_{\pi_\theta}$ . This is distributional shift — caused here by the policy’s own mistakes.

To analyze it, define what “good” means. Take the expert to be a deterministic policy $\pi^\star$ and charge one unit per mistake:

$c(s_t, a_t) = \begin{cases} 0 & \text{if } a_t = \pi^\star(s_t) \\ 1 & \text{otherwise} \end{cases}$

so total expected cost is the expected number of mistakes — evaluated, crucially, under $p_{\pi_\theta}$ , the distribution the policy actually inhabits. (The analysis runs in terms of $s$ ; extending it to $o$ is possible but messier.) Assume supervised learning worked: $\pi_\theta(a \neq \pi^\star(s) \mid s) \le \epsilon$ for training states.

The tightrope is the worst case; it is also, up to constants, the bound.

The behavioral cloning error bound

Assume $\mathbb{E}_{s \sim p_{\text{train}}}[\pi_\theta(a \neq \pi^\star(s) \mid s)] \le \epsilon$ . Decompose the state distribution at time $t$ into “made no mistakes yet” and “everything else”:

$p_{\pi_\theta}(s_t) = (1-\epsilon)^t\, p_{\text{train}}(s_t) + \left(1 - (1-\epsilon)^t\right) p_{\text{mistake}}(s_t)$

where $p_{\text{mistake}}$ is some complicated distribution we assume nothing about. Subtracting $p_{\text{train}}$ and using that the total variation distance between any two distributions is at most $2$ (summing $|p - q|$ over states),

$\sum_{s_t} \left| p_{\pi_\theta}(s_t) - p_{\text{train}}(s_t) \right| \le 2\left(1 - (1-\epsilon)^t\right) \le 2\epsilon t,$

the last step by the identity $(1-\epsilon)^t \ge 1 - \epsilon t$ for $\epsilon \in [0, 1]$ . Writing the expected cost under $p_{\pi_\theta}$ as the cost under $p_{\text{train}}$ plus an error term controlled by this divergence (with $c_{\max} = 1$ ) gives

$\sum_{t=1}^{T} \mathbb{E}_{p_{\pi_\theta}}[c(s_t, a_t)] \le \sum_{t=1}^{T} \left(\epsilon + 2\epsilon t\right) = O(\epsilon T^2).$

This is pessimistic — the tightrope is pathological in that one error is instantly unrecoverable, while real tasks usually allow recovery. But being able to recover doesn’t mean imitation learning will learn to; the data has to show it how.

This is why intentionally injecting mistakes during data collection can help — mistakes dilute the data but average out if uncorrelated with state, while the corrections teach — and why domain-knowledge data augmentation works: the Zurich drone paper flew forest trails using nothing but a hiker wearing a three-camera hat, left camera labeled “go right,” right camera labeled “go left,” no recorded human actions at all.

Why you might fail to fit the expert

If $\epsilon$ can be driven small enough, even $\epsilon T^2$ may be tolerable — so why might a powerful model still fail to fit the expert? Two reasons.

Non-Markovian behavior. A policy conditioned on the current observation assumes only the present matters, but humans don’t act that way: a driver who was just cut off drives differently for the next few seconds. The fix is a policy that reads the whole history — a per-frame encoder feeding an LSTM or Transformer, nothing imitation-specific. The caveat: history can worsen things by amplifying spurious correlations. Levine’s example is a car whose brake pedal lights a dashboard indicator visible to the camera. The pedestrian ahead is the true cause of braking; the lit indicator — and, with history, the visible slowing of the car — is an effect of braking that correlates almost perfectly with it, so the policy learns the effect as if it were the cause. This is causal confusion; whether history or even DAgger mitigates it is left as an exercise.

Multimodal behavior. Flying around a tree, half the experts go left, half go right — both correct. Discrete actions handle this for free; a single Gaussian averaging left and right is “very, very bad.” Four escalating remedies:

Mixtures of Gaussians: output $N$ means, covariances, and weights; optimize the log of the mixture likelihood. Simple, but modes are capped at $N$ .
Latent variable models: the output stays Gaussian but the network gets an extra input $z$ from a prior — a random seed selecting the mode. Trained naively the network ignores $z$ ; conditional variational autoencoders (second half of the course) choose $z$ during training to correlate with the demonstrated mode. With a big enough network this can represent any distribution.
Diffusion models: repeatedly add noise to true actions, $a_{t,i+1} = a_{t,i} + \text{noise}$ , and train $f(s_t, a_{t,i})$ to predict the noise; at test time start from pure noise and iteratively denoise into a clean action — the machinery behind image generators, applied to actions.
Autoregressive discretization: discretizing a 10-dimensional action space jointly needs exponentially many bins; instead discretize one dimension per sequence-model step, feeding each output back in. By the chain rule the product of per-step conditionals is exactly $\pi_\theta(a_t \mid s_t)$ , so sequential sampling is exact — a GPT-style decoder over action dimensions.

These aren’t hypothetical: diffusion policies drive manipulation robots from images; a latent-variable Transformer buckles a shoe onto a mannequin foot while “an annoying graduate student distracts the robot”; and RT-1 reads image history plus a language instruction and emits per-dimension discretized arm and base actions, turning control into sequence-to-sequence.

Goal-conditioned behavioral cloning

A perhaps surprising trick: learning many tasks at once can make imitation easier. Suppose the expert drove to lots of places, not just the destination you care about. Condition the policy on a goal — and get goal labels for free by taking each trajectory’s last state as the goal it evidently reached:

$\max_\theta \; \sum_{\text{demos}} \sum_t \log \pi_\theta\!\left(a_t \mid s_t, g = s_T\right)$

Every trajectory becomes a valid demonstration for the state it actually reached, so failed attempts are still useful data and the expert visits far more states — better coverage, more correction examples. When the policy drifts out of distribution for one commanded goal, the state may be perfectly familiar for another. (In theory relabeling introduces distributional shift in a second place — another exercise to ponder.) The idea was popularized by “learning latent plans from play,” where people just fiddle with objects in VR with no assigned task, and the relabeled latent-variable policy can then be commanded to open drawers or close doors. It iterates into a self-improvement loop — command random goals, relabel what was reached, retrain — and it scales: one goal-conditioned policy trained across many ground robots transferred zero-shot to a drone it never saw in training. The same relabeling principle appears in off-policy RL as hindsight experience replay.

DAgger, and why imitation isn’t enough

Everything so far changed the policy to keep $p_{\pi_\theta}$ near $p_{\text{data}}$ . DAgger — Dataset Aggregation — goes the other way: change the data so that it comes from $p_{\pi_\theta}$ in the first place. Be clever about data collection, not about the model.

Code walkthrough — DAgger: Dataset Aggregation

Run the policy, let the human label what the policy saw, and grow the dataset:

D = human_demonstrations()              # {(o, a)} from the expert
for k in range(num_iters):
    policy = supervised_learning(D)     # 1. train pi_theta on D
    O_pi   = run_policy(policy)         # 2. observations the policy visits
    A_star = ask_human_to_label(O_pi)   # 3. expert action for each o in O_pi
    D      = D + zip(O_pi, A_star)      # 4. aggregate: D <- D union D_pi

Each round, the labeled data is drawn from the distribution of the current policy; it can be shown the aggregate converges so that training data eventually comes from $p_{\pi_\theta}$ itself — the mismatch driving the quadratic bound is gone, and DAgger’s bound is linear: $O(\epsilon T)$ . You will implement exactly this in homework 1.

The catch is step 3. Labeling observations after the fact — staring at a frame and naming the correct steering angle — is unnatural for humans, who act inside a temporal process with reaction times; many DAgger successors target exactly this weakness. Still, the original paper flew a real drone through a forest with a handful of iterations and offline mouse-click labels.

Why, then, the rest of the course? Because imitation caps you at human effort and human skill: deep learning thrives on plentiful data, and humans can’t demonstrate everything — “if you want to control a giant robotic spider, well, good luck finding a human who can operate that.” Machines learning from their own experience can get unlimited data and, in principle, improve past us. That requires saying what we want rather than what to copy: a cost $c(s_t, a_t)$ to minimize or a reward $r(s_t, a_t)$ to maximize — the same thing up to a sign. Even imitation fits this frame, with the expert action’s log-probability as reward — but richer rewards, like reaching a destination or not being eaten by a tiger, are what the reinforcement learning algorithms of the coming weeks will optimize.

Back of the chalk tray — what to remember

A policy $\pi_\theta(a_t \mid o_t)$ is a conditional distribution over actions; states satisfy the Markov property, observations need not — you can render $o_t$ from $s_t$ but not always invert it.
Behavioral cloning is maximum likelihood on demonstrations. It violates the i.i.d. assumption: the policy’s outputs determine its future inputs, so small errors compound into unfamiliar states.
Under an $\epsilon$ per-state mistake rate, expected mistakes grow as $O(\epsilon T^2)$ — the tightrope walker realizes the worst case, and the bound is tight.
Paradoxically, data with mistakes and recoveries beats perfect data: corrections teach the policy how to return to distribution. Camera tricks and injected noise exploit this.
Failing to fit the expert traces to non-Markovian behavior (fix: sequence models over history, wary of causal confusion) and multimodality (fix: Gaussian mixtures, latent variables, diffusion, or autoregressive discretization).
Goal-conditioned BC relabels every trajectory with the state it reached, converting failures into data; DAgger instead collects labels on the policy’s own state distribution, cutting the bound to $O(\epsilon T)$ at the cost of online expert labeling.

Check yourself

Conceptual and derivation exercises in the lecture’s spirit — work them before peeking.

Problem 2.1 compounding error bound

Consider a horizon of $T = 200$ and a policy whose per-step mistake probability on in-distribution states is $\epsilon = 0.01$ . (a) Using the tightrope-walker accounting, estimate the order of the expected total number of mistakes. (b) The policy is retrained and $\epsilon$ drops to $0.001$ . By what factor does the bound improve, and what would halving $T$ have done instead? (c) State the exact assumption under which the $O(\epsilon T^2)$ bound was derived, and point to where $p_{\text{mistake}}$ enters the argument.

Show solution

(a) Each of the $T$ time steps contributes on the order of $\epsilon T$ expected mistakes (fall off with probability about $\epsilon$ , then flail for the remaining steps), giving order $\epsilon T^2 = 0.01 \times 200^2 = 400$ — the policy is useless even though it is 99 percent accurate per step. (b) The bound is linear in $\epsilon$ : a 10x drop in $\epsilon$ gives a 10x better bound, $\approx 40$ . Halving $T$ helps quadratically, cutting the bound by 4x. This is why long horizons are the enemy. (c) The assumption is $\mathbb{E}_{s \sim p_{\text{train}}}[\pi_\theta(a \neq \pi^\star(s) \mid s)] \le \epsilon$ — small expected error on the training distribution only. Nothing is assumed about behavior elsewhere: $p_{\text{mistake}}$ is an arbitrary distribution, and it enters only through its total weight $1 - (1-\epsilon)^t$ in the decomposition of $p_{\pi_\theta}(s_t)$ ; the bound $|p - q| \le 2$ summed over states is the only control we have on it. That is exactly why the bound cannot be improved without new assumptions — off-distribution, anything can happen.

Problem 2.2 total variation derivation

Starting from the decomposition $p_{\pi_\theta}(s_t) = (1-\epsilon)^t p_{\text{train}}(s_t) + (1 - (1-\epsilon)^t) p_{\text{mistake}}(s_t)$ , derive the bound $\sum_{s_t} |p_{\pi_\theta}(s_t) - p_{\text{train}}(s_t)| \le 2\epsilon t$ , justifying each inequality, and explain where the constant $2$ comes from.

Show solution

Subtract $p_{\text{train}}(s_t)$ from both sides: the $(1-\epsilon)^t p_{\text{train}}$ term combines with $-p_{\text{train}}$ to give $-(1 - (1-\epsilon)^t) p_{\text{train}}$ , so

$p_{\pi_\theta}(s_t) - p_{\text{train}}(s_t) = \left(1 - (1-\epsilon)^t\right)\left(p_{\text{mistake}}(s_t) - p_{\text{train}}(s_t)\right).$

Take absolute values and sum over states. The sum $\sum_{s_t} |p_{\text{mistake}}(s_t) - p_{\text{train}}(s_t)|$ is at most $2$ : the worst case is two distributions with disjoint support, where one assigns probability mass that the other assigns zero, and each side’s mass sums to 1 — hence the constant $2$ . This yields $2(1 - (1-\epsilon)^t)$ . Finally, the algebraic identity $(1-\epsilon)^t \ge 1 - \epsilon t$ for $\epsilon \in [0,1]$ gives $1 - (1-\epsilon)^t \le \epsilon t$ , so the whole expression is at most $2\epsilon t$ — a slightly looser but exponent-free bound. Summing $\epsilon + 2\epsilon t$ over $t = 1, \ldots, T$ then produces the linear-plus-quadratic total that is $O(\epsilon T^2)$ .

Problem 2.3 multimodal action failure

A quadcopter approaching a tree sees expert demonstrations that go left with probability $\tfrac{1}{2}$ (action $a = -1$ ) and right with probability $\tfrac{1}{2}$ (action $a = +1$ ). (a) A policy outputs a single Gaussian $\mathcal{N}(\mu(o), \sigma^2)$ trained by maximum likelihood on this data. What mean does it learn, and why is the resulting behavior worse than either expert mode? (b) Explain why a discrete 3-way policy (left, straight, right) has no such problem. (c) For a 12-dimensional continuous action space needing many modes, why does naive discretization fail, and how does autoregressive discretization restore tractability while remaining a valid distribution?

Show solution

(a) Maximum likelihood fits the Gaussian mean to the data mean: $\mu = \tfrac{1}{2}(-1) + \tfrac{1}{2}(+1) = 0$ — fly straight into the tree, an action no expert ever took. The unimodal family cannot place high probability on both $-1$ and $+1$ without placing even higher probability between them. (b) A softmax over three discrete actions directly represents probability $\tfrac{1}{2}$ on left, $\tfrac{1}{2}$ on right, and near zero on straight — multimodality is free when you enumerate actions. (c) Discretizing each of 12 dimensions into $k$ bins jointly needs $k^{12}$ bins — exponential in dimension. Autoregressive discretization discretizes one dimension per sequence-model step: predict $a_{t,0}$ given $s_t$ , then $a_{t,1}$ given $s_t, a_{t,0}$ , and so on. The cost is linear in dimension, and by the chain rule the product of the conditionals equals $\pi_\theta(a_{t,0}, \ldots, a_{t,11} \mid s_t)$ exactly, so sequential sampling draws from the true joint — arbitrary correlations and modes included.

Problem 2.4 DAgger and its assumptions

(a) Write out the four steps of DAgger and identify precisely which distribution the newly labeled data is drawn from at each iteration. (b) Explain in one or two sentences why this closes the distributional-shift gap that behavioral cloning suffers from, and what the resulting error bound is. (c) Which step is problematic in practice and why? Give one setting where it is nearly free and one where it is nearly impossible.

Show solution

(a) 1. Train $\pi_\theta(a_t \mid o_t)$ on the human dataset $\mathcal{D}$ ; 2. run $\pi_\theta$ to collect an observation dataset $\mathcal{D}_\pi = \{o_1, \ldots, o_M\}$ ; 3. ask a human to label each observation in $\mathcal{D}_\pi$ with the action they would have taken; 4. aggregate $\mathcal{D} \leftarrow \mathcal{D} \cup \mathcal{D}_\pi$ and repeat. The new observations are drawn from $p_{\pi_\theta}(o_t)$ — the current policy’s own distribution — with expert labels attached. (b) Behavioral cloning’s quadratic term came entirely from testing under $p_{\pi_\theta}$ while training under $p_{\text{data}}$ ; as iterations proceed the aggregate dataset becomes dominated by samples from the policy’s distribution, the two distributions converge, and training error on the training distribution is test error — giving a bound linear in the horizon, $O(\epsilon T)$ . (c) Step 3, the offline labeling. Humans act inside a temporal process with reaction times, and naming the correct action for an isolated frame after the fact can be unnatural. It is nearly free when actions are low-dimensional and legible from a single image — e.g. left/straight/ right for a trail-following drone, labeled with mouse clicks. It is nearly impossible when actions are high-dimensional, high-rate low-level commands — e.g. per-joint torques for a humanoid or rotor thrusts mid-aerobatics — where no human can state the right action for a still frame.

Problem 2.5 hidden distribution shift

Goal-conditioned behavioral cloning relabels each training trajectory with the final state it actually reached, then trains $\pi_\theta(a_t \mid s_t, g)$ . The lecture hints that this introduces distributional shift “in two places.” Identify both, and explain why the method often helps in practice anyway.

Show solution

First place — the familiar one: the state distribution. The policy is trained on states the expert visited but tested on states it visits itself, so $p_{\pi_\theta}(s_t) \neq p_{\text{data}}(s_t)$ , exactly as in ordinary behavioral cloning. Second place — the new one: the goal distribution. Training goals are states the expert happened to reach (the relabeled final states), while test goals are states you actually want — commanded goals sampled from your task distribution, which may look nothing like the endpoints of the collected trajectories. A goal never reached in the data is an out-of-distribution input to the policy. It often helps anyway because relabeling massively broadens state coverage: every trajectory, including failed ones, becomes valid supervision for some goal, so when the policy drifts, the state it lands in is frequently in-distribution for other goals in the dataset — supplying exactly the correction examples whose absence made narrow, optimal demonstrations brittle. The empirical gain from coverage usually outweighs the theoretical cost of the second shift.