Inverse Reinforcement Learning

Why learn the reward at all

Every RL problem in the course so far came with a reward function, typically programmed by hand. But what if the task is easy to demonstrate and hard to specify? Inverse reinforcement learning asks: observing an expert perform a task successfully, can you back out the reward function they were optimizing — and then re-optimize it with RL?

Levine gives three motivations. The intellectual one: over a century of work models human behavior through the lens of optimality — one definition of rational behavior is behavior that maximizes a well-defined utility function — and while the classic deterministic-optimality model is often a poor fit (humans are neither deterministic nor perfectly optimal), the soft model from the previous lecture explains human behavior quite well. The imitation-learning motivation: behavioral cloning copies the expert’s actions “without reasoning about the purpose of those actions.” Humans don’t imitate that way — “when humans imitate, we copy the intent of the expert.” Levine shows a psychology experiment in which a child, watching an experimenter, performs not the demonstrated action but the action that achieves the inferred goal: same outcome, possibly very different actions. The RL-centric motivation: for a game the score is printed on the screen, but for an autonomous car — reach the destination, obey traffic law, don’t annoy other drivers, keep passengers comfortable — writing one equation that balances all of that is very hard, while asking a professional driver to demonstrate is comparatively easy.

The catch: as stated, the problem is severely underspecified. In a $4 \times 4$ grid world, a four-step demonstration to a corner square is explained equally well by “big reward at that square,” “big reward at the square past it,” “reward everywhere in the lower half with penalties on certain cells,” or even “reward $-\infty$ for any action other than the demonstrated ones.” Infinitely many rewards make the observed behavior optimal. Levine deliberately uses a semantics-free grid: to the algorithm the driving task is also just states and actions, with no prior saying sensible rewards involve traffic laws rather than particular GPS coordinates.

The classical answer: feature matching and maximum margin

Before the probabilistic view, the classical literature disambiguated via feature matching: pick $\psi$ so that the optimal policy under $r_\psi$ matches the expert’s expected features, $\mathbb{E}_{\pi^{r_\psi}}[\mathbf{f}] = \mathbb{E}_{\pi^\star}[\mathbf{f}]$, the right-hand side estimated by averaging features over demonstrations. Still ambiguous: every reward in the grid-world example induces the same policy, hence identical feature expectations. The next fix borrowed from SVMs — a maximum margin principle: choose $\psi$ so the expert’s expected reward beats every other policy’s by the largest possible margin, $\psi^\top \mathbb{E}_{\pi^\star}[\mathbf{f}] \ge \max_\pi \psi^\top \mathbb{E}_{\pi}[\mathbf{f}] + m$. Since policies nearly identical to the expert’s shouldn’t need a large margin, the SVM trick (minimize $\|\psi\|^2$ with margin 1) generalizes by replacing the 1 with a divergence $D(\pi, \pi^\star)$ — difference in feature expectations, or expected KL. This yields usable algorithms (Abbeel’s apprenticeship learning, Ratliff’s maximum margin planning), but Levine flags three problems: the margin is a heuristic whose underlying assumption about the expert is never made explicit; there is no clear model of expert sub-optimality (slack variables are a patch, not a model); and the messy constrained optimization becomes a real obstacle once rewards are neural networks.

Maximum entropy IRL: learning in the graphical model

The main event replaces heuristics with the probabilistic model of the previous lecture: states, actions, and optimality variables with $p(\mathcal{O}_t \mid s_t, a_t, \psi) = \exp(r_\psi(s_t, a_t))$. Before, we did inference — probability of a trajectory given optimality and a known reward, $p(\tau \mid \mathcal{O}_{1:T}, \psi) \propto p(\tau) \exp\left(\sum_t r_\psi(s_t, a_t)\right)$, under which the optimal trajectory is most likely and sub-optimal ones exponentially less so. Now we do learning: choose $\psi$ to maximize the likelihood of the demonstrations,

$\max_\psi \; \frac{1}{N} \sum_{i=1}^{N} \log p(\tau_i \mid \mathcal{O}_{1:T}, \psi) = \max_\psi \; \frac{1}{N} \sum_{i=1}^{N} r_\psi(\tau_i) - \log Z$

(the $p(\tau)$ term drops — it doesn’t depend on $\psi$). Without $\log Z$ this is “at once both intuitive and kind of silly”: just make the demos high-reward. The partition function $Z = \int p(\tau) \exp(r_\psi(\tau))\, d\tau$ is what forbids assigning huge reward to everything — you must make the observed trajectories more likely than the ones you didn’t see — and it is exactly what makes IRL difficult.

Ziebart’s original paper used this to infer taxi drivers’ route preferences in Pittsburgh (city streets versus highways) and plan routes the way a taxi driver would.

Scaling up: sampling, lazy inner loops, and guided cost learning

MaxEnt IRL needs the soft-optimal policy in its inner loop and needs to enumerate all state–action tuples — impossible with large or continuous spaces, sample-only access to states, and unknown dynamics. The fix targets the second expectation in the gradient. Idea one: run any max-ent RL algorithm from the previous lecture (soft Q-learning, entropy-regularized policy gradient) to convergence, sample trajectories $\tau_j$, and estimate the expectation — viable, but it solves a full forward RL problem for every gradient step on the reward.

Idea two — the practical one: be lazy. Improve the policy just a little per reward update, even a single gradient step, starting from where the previous $\psi$ left it. The samples now come from the wrong distribution, so the estimator is biased — and importance sampling corrects it. With self-normalized weights $w_j$ (divide by $\sum_j w_j$), the unknown initial-state and dynamics terms cancel exactly as in the importance-weighted policy gradient lecture, leaving

$w_j = \frac{\exp\!\left(\sum_t r_\psi(s_t, a_t)\right)}{\prod_t \pi(a_t \mid s_t)}$

— computable, since you know your current reward and you know the policy you just trained. Crucially, every policy update brings the sampler closer to the target distribution, so the weights drift toward one as training proceeds: you can take reward steps with an incompletely optimized policy, and the correction shrinks as the policy catches up.

This is guided cost learning (Finn et al.), the first deep inverse RL algorithm to scale to high-dimensional state and action spaces. Loop: sample from the current policy; use policy samples plus human demonstrations to update the reward via the importance-weighted gradient; use the updated reward to update the policy (regular policy gradient plus the entropy term). At convergence you get both a reward that explains the expert and a policy that optimizes it. In the original paper the demonstrations were a real robot pouring into a cup; the learned policy had to find the cup with vision and pour wherever it was — inferring the intent of the task.

IRL is a GAN with a peculiar discriminator

Step back and the algorithm looks like a game: the reward tries to make human demos look good and policy samples look bad; the policy tries to make its samples indistinguishable from demos under that reward. The connection to generative adversarial networks is not just superficial. A GAN trains a generator $p_\theta$ against a discriminator $D_\psi(x)$ — a binary classifier maximizing $\log D_\psi$ on data and $\log(1 - D_\psi)$ on generations — and the Bayes-optimal discriminator at convergence is a density ratio, $D^\star(x) = p^\star(x) / (p_\theta(x) + p^\star(x))$: it cannot output 1 on real-looking images once the generator produces identical ones, and when $p_\theta = p^\star$ it outputs 0.5 everywhere.

To cast IRL as a GAN, plug the soft-optimality form $p(\tau) \frac{1}{Z} \exp(r_\psi(\tau))$ in place of $p^\star$ in that formula. The trajectory terms cancel top and bottom, giving a discriminator with a very particular structure:

$D_\psi(\tau) = \frac{\frac{1}{Z} \exp(r_\psi(\tau))}{\prod_t \pi(a_t \mid s_t) + \frac{1}{Z} \exp(r_\psi(\tau))}$

which equals 0.5 exactly when the policy’s probabilities match the exponentiated reward — i.e., when the policy has converged. Train $\psi$ with the standard GAN discriminator objective, and — the neat part — optimize $Z$ jointly with $\psi$ under that same objective, which turns out to yield the correct answer (derivation in “A Connection Between Generative Adversarial Networks, Inverse Reinforcement Learning, and Energy-Based Models”). The importance weights disappear, subsumed into the learned partition function; the policy is the generator, trained to maximize reward plus entropy.

Instantiating this (adversarial IRL) shows why recovering the reward matters: infer a reward from a running quadrupedal ant, disable two of its legs, re-optimize — and the agent discovers a completely different gait that still achieves the goal. What IRL does is decouple the goal — the reward — from the dynamics; copying actions would not transfer. And if you don’t need the reward? Use an ordinary binary classifier as the discriminator and train the policy to maximize $\mathbb{E}[\log D]$ — generative adversarial imitation learning (Ho and Ermon). Simpler to set up, fewer moving parts; but at convergence the discriminator outputs 0.5 and “doesn’t really know anything,” so there is no reward to re-optimize in new settings. GAIL recovers the expert’s policy; guided cost learning and AIRL recover the reward. Same game, different discriminator.

Check yourself

Exercises in the lecture’s spirit — work them on paper before reading the solutions.

Problem 20.1 reward ambiguity

An expert in a deterministic grid world demonstrates a single trajectory of four steps ending at cell $g$. (a) Give three structurally different reward functions under which this trajectory is optimal in the classical (hard-optimality) sense. (b) Explain precisely how the max-ent model distinguishes between rewards that classical IRL cannot — what observable property of the demonstration distribution carries the extra information?

Show solution

(a) Following the lecture: reward $+R$ at $g$ and $0$ elsewhere; reward $+R$ at some cell beyond $g$ that the four observed steps are also en route to; reward $-\infty$ for any state–action pair not appearing in the demonstration (and anything for the rest). All make the observed trajectory optimal. (b) Under hard optimality all three induce the same argmax behavior, so no amount of data separates them. Under soft optimality, $p(\tau \mid \mathcal{O}_{1:T}, \psi) \propto p(\tau) \exp(r_\psi(\tau))$ — the relative magnitudes of rewards control how concentrated the trajectory distribution is. Higher reward differences make the expert more deterministic; near-equal rewards make them visibly random over the tied options. So the spread of the demonstrations across trajectories — not just which trajectory is best — identifies the reward: consistent, repeated behavior implies a large reward gap, random behavior implies the alternatives are roughly equally good. Maximizing likelihood fits exactly this.

Problem 20.2 likelihood gradient derivation

Starting from $\mathcal{L}(\psi) = \frac{1}{N}\sum_i r_\psi(\tau_i) - \log Z$ with $Z = \int p(\tau) \exp(r_\psi(\tau))\, d\tau$, derive the gradient $\nabla_\psi \mathcal{L}$ and show the second term is an expectation under $p(\tau \mid \mathcal{O}_{1:T}, \psi)$. Why is this expectation the entire difficulty of the algorithm?

Show solution

$\nabla_\psi \log Z = \frac{1}{Z} \nabla_\psi Z = \frac{1}{Z} \int p(\tau) \exp(r_\psi(\tau))\, \nabla_\psi r_\psi(\tau)\, d\tau$. But $\frac{1}{Z}\, p(\tau) \exp(r_\psi(\tau))$ is by definition the soft-optimal trajectory distribution $p(\tau \mid \mathcal{O}_{1:T}, \psi)$, so $\nabla_\psi \log Z = \mathbb{E}_{\tau \sim p(\tau \mid \mathcal{O}_{1:T}, \psi)}[\nabla_\psi r_\psi(\tau)]$ and $\nabla_\psi \mathcal{L} = \frac{1}{N}\sum_i \nabla_\psi r_\psi(\tau_i) - \mathbb{E}_{p(\tau \mid \mathcal{O}_{1:T}, \psi)}[\nabla_\psi r_\psi(\tau)]$. The first term is a fixed average over demos — trivial. The second requires expectations under the soft-optimal policy for the current reward, i.e., solving a (soft) RL problem inside every gradient step: tractable by dynamic programming (forward–backward messages) only in small discrete spaces with known dynamics, and requiring sampling approximations everywhere else. Everything after Ziebart’s algorithm in the lecture — lazy policy updates, importance weights, the GAN framing — is a strategy for estimating this one term cheaply.

Problem 20.3 importance weights

In guided cost learning, samples come from a partially trained policy $\pi(a_t \mid s_t)$ rather than the soft-optimal policy for the current $\psi$. (a) Starting from the target density $p(\tau \mid \mathcal{O}_{1:T}, \psi) \propto p(s_1) \prod_t p(s_{t+1} \mid s_t, a_t) \exp(r_\psi(s_t, a_t))$ and the sampler $\pi(\tau) = p(s_1) \prod_t p(s_{t+1} \mid s_t, a_t)\, \pi(a_t \mid s_t)$, derive the importance weight $w_j$ and explain why unknown dynamics are not a problem. (b) What happens to the weights as the policy is trained further, and why does that matter?

Show solution

(a) The (unnormalized) weight is the ratio of target to sampler densities. The $p(s_1)$ and every $p(s_{t+1} \mid s_t, a_t)$ appear in both numerator and denominator and cancel, leaving $w_j = \exp\!\left(\sum_t r_\psi(s_{t}, a_{t})\right) / \prod_t \pi(a_t \mid s_t)$. The dynamics never need to be known — they only need to be shared between target and sampler, which they are since both describe trajectories in the same environment. The numerator uses the current reward (known); the denominator uses the just-trained policy’s action probabilities (known, e.g., a Gaussian density). Self-normalizing over the batch handles the unknown $Z$. (b) Each policy update moves $\pi$ toward the soft-optimal policy for the current reward, whose action probabilities approach $\exp$-reward form — so numerator and denominator converge and $w_j \to 1$. This is what licenses laziness: early on, the weights do the correcting; later, the policy itself is nearly the right sampler, so variance from the weights fades rather than compounding.

Problem 20.4 GAIL vs AIRL discriminators

Two adversarial imitation setups: (i) the discriminator is a plain binary classifier over trajectories; (ii) the discriminator has the form $D_\psi(\tau) = \frac{\frac{1}{Z}\exp(r_\psi(\tau))}{\prod_t \pi(a_t \mid s_t) + \frac{1}{Z}\exp(r_\psi(\tau))}$. (a) For (ii), show that $D_\psi = 0.5$ exactly when the policy matches the soft-optimal distribution for $r_\psi$. (b) At full convergence, what does each discriminator “know,” and which setup supports re-optimizing behavior in an environment with altered dynamics (the crippled-ant experiment)? (c) Name one practical reason to prefer (i) anyway.

Show solution

(a) $D_\psi = 0.5$ iff numerator equals half the denominator, i.e., $\frac{1}{Z}\exp(r_\psi(\tau)) = \prod_t \pi(a_t \mid s_t)$ — the policy’s trajectory probability (dynamics terms cancel on both sides) equals the normalized exponentiated reward, which is precisely the soft-optimality condition: the policy has converged to the max-ent optimal policy for $r_\psi$. (b) The plain classifier (GAIL) outputs 0.5 everywhere at convergence and “doesn’t really know anything” — all task information has been absorbed into the policy, which is tied to the training dynamics. Setup (ii) (guided cost learning / AIRL) carries an explicit $r_\psi$ inside the discriminator, so at convergence you hold a reward function decoupled from the dynamics; disable two of the ant’s legs and re-optimizing $r_\psi$ yields a new gait achieving the same goal. Copied actions or the GAIL policy would not transfer. (c) GAIL is often simpler to set up — fewer moving parts, no partition-function handling, just a standard GAN objective — and if you only ever need the expert’s policy in the original environment, recovering the reward buys you nothing.