Offline RL I

The case for RL without interaction

Levine opens with an observation about where deep RL works: the settings where RL succeeds “just look kind of different than the settings where we’ve seen supervised deep learning techniques be very effective.” The gap isn’t task complexity — it’s generalization. Image recognizers handle photos from anywhere in the world; AlphaGo beats the world champion but “doesn’t have to worry about somebody spilling coffee on the go board.” A plausible diagnosis is data variability, and the fix would be to train RL on huge, diverse datasets. But an on-policy algorithm would then demand an ImageNet-sized dataset every iteration, and even an off-policy algorithm demands one per training run. What makes modern machine learning work is large models plus large datasets collected once and reused — offline RL is the attempt to give RL that recipe.

A related subproblem is off-policy evaluation (OPE): given $\mathcal{D}$, estimate $J(\pi)$ for some other policy $\pi$ — often a building block inside offline RL, and in a sense harder than policy learning, because learning never needs to evaluate policies that don’t arise during optimization. And “best possible policy” carries a caveat: it means the best policy supported by the data. If all your Montezuma’s Revenge data is from the first room, no algorithm can recover the true optimum — the evidence simply isn’t there.

Better than the best thing in the data

The naive expectation is that offline RL should “find the good stuff” in a mixed dataset — from a pile of good, mediocre, and bad drivers, imitation learning gets you the average driver, while offline RL should get you the best one. But that undersells it: offline RL can exceed the best behavior in the dataset. Generalization means good behavior in one place suggests good behavior in another, and dynamic programming can stitch behaviors: if the data contains transitions from A to B and from B to C, RL can figure out how to go from A to C — a route no trajectory ever took. Scaled up, a maze dataset of short point-to-point snippets yields navigation between arbitrary pairs.

What actually happens when you run it naively

That divergence between believed and actual value is not an accident — it is the fundamental problem of offline RL, which Levine frames as one of counterfactual queries. Human drivers in your dataset do many things, some unsafe, but they never swerve off the road in the middle of nowhere. Training a policy implicitly asks “of all actions available in this state, which is best?” — including actions nobody took. An online algorithm can erroneously conclude that swerving is great, try it, and learn otherwise. An offline algorithm never gets that correction; it must somehow understand that unfamiliar actions cannot be assumed good. These are out-of-distribution actions — and the distinction from merely out-of-sample actions is critical. New actions drawn from the same distribution as the data are exactly what generalization handles (early offline RL work stumbled by conflating the two); actions outside the support of $\pi_\beta$ are the danger. The delicate trade-off: exploit generalization enough to beat the data, without trusting values where there is no evidence.

Distribution shift, and why maximization makes it worse

The statistics underneath is distribution shift. Empirical risk minimization fits $f_\theta(x)$ on $x \sim p(x)$, guaranteeing low expected error under $p$. Under a different $\bar{p}(x) \neq p(x)$, nothing is guaranteed; even for a test point sampled from $p(x)$ itself, individual errors can be large. Usually neural networks generalize well enough that we shrug. But now suppose the test point is chosen: $x^\star \leftarrow \arg\max_x f_\theta(x)$. You will land precisely on the point where the fit errs most in the positive direction — this is exactly how adversarial examples are constructed, and “when you optimize with respect to inputs into a neural net, you can fool that neural net into doing just about anything.”

Q-learning does exactly this. The critic minimizes Bellman error under the data distribution while the targets query the new policy:

$\phi \leftarrow \arg\min_\phi \; \mathbb{E}_{(s,a) \sim \pi_\beta}\!\left[\big(Q_\phi(s,a) - y(s,a)\big)^2\right], \qquad y(s,a) = r(s,a) + \gamma\, \mathbb{E}_{a' \sim \pi_{\text{new}}}\!\left[Q_\phi(s', a')\right]$

Q-values are accurate in expectation under $\pi_\beta$ but evaluated under $\pi_{\text{new}}$ — and $\pi_{\text{new}}$ (the argmax policy, or a trained actor) is selected to maximize the Q-value.

Classic recipe I: importance sampling

The rest of the lecture surveys the classic, pre-deep-RL approaches. First, importance-sampled policy gradients, familiar from earlier lectures: with only samples from $\pi_\beta$, weight each trajectory by $\prod_{t} \pi_\theta(a_t \mid s_t) / \pi_\beta(a_t \mid s_t)$ (initial-state and transition terms cancel). Unbiased — but the weight is a product of $O(T)$ ratios, so it is exponential in $T$ and the weights degenerate: one sample dominates, all others vanish, and the variance is exponentially large. The advanced-policy-gradients trick of simply dropping the early ratios is justified only when $\pi_\theta$ stays close to the data-collecting policy — which defeats the whole point of offline RL, where we want a much better policy. Splitting the weight into the ratios before $t$ (accounting for the different probability of reaching $s_t$) and after $t$ (correcting the reward-to-go estimate), and truncating each reward’s weight at its own time step, softens the constants but not the exponent. Levine is blunt: “to avoid exponentially exploding importance weights, we must use value function estimation.”

A final variant, marginalized importance sampling, replaces the product of action ratios with a single weight on state–action marginals, $w(s,a) = d^{\pi_\theta}(s,a) / d^{\pi_\beta}(s,a)$, which makes evaluation trivial: average $w(s_i, a_i)\, r_i$ over the dataset. Since neither marginal is known, $w$ is found by solving a consistency condition — the analogue of a Bellman equation for importance weights, relating $d^{\pi_\beta}(s',a')\,w(s',a')$ to the probability of starting in $(s',a')$ plus the probability of transitioning into it from weighted predecessors. The trick in deriving practical algorithms is expressing the residual as an expectation under $d^{\pi_\beta}$, so it can be estimated purely from dataset samples with a single network for $w$.

Classic recipe II: linear fitted value functions

The second classic family assumes a feature matrix $\Phi$ ($|S| \times K$, one $K$-dimensional feature row per state) and does everything linearly — valuable today less as a practical method than as an analysis toolkit that yields closed-form solutions. Fit a linear reward model $\Phi w_r \approx r$ by least squares, $w_r = (\Phi^\top \Phi)^{-1} \Phi^\top r$, and a feature-space transition matrix $P_\phi$ ($K \times K$) with targets $P^\pi \Phi$ — an embedding of the MDP into feature space, for a fixed policy. Then the vector Bellman equation $V^\pi = r + \gamma P^\pi V^\pi$ is linear, giving $V^\pi = (I - \gamma P^\pi)^{-1} r$ (the inverse always exists), and its feature-space analogue $w_V = (I - \gamma P_\phi)^{-1} w_r$. Substituting the least-squares solutions and simplifying collapses the model entirely:

$w_V = \big(\Phi^\top \Phi - \gamma\, \Phi^\top P^\pi \Phi\big)^{-1} \Phi^\top r$

— least-squares temporal difference (LSTD): a journey through model-based RL that lands on a model-free formula. Replace enumeration over states with the dataset’s samples (one row of $\Phi$ per sample, $P^\pi \Phi$ replaced by the next-state features $\Phi'$, $r$ by the sampled rewards) — the “empirical MDP” — and the same equations hold with sampling error. Because evaluating a new policy’s value function would require $P^\pi$ for that policy, the practical algorithm uses Q-functions instead: state–action features, where $\Phi'$ featurizes the dataset’s $s'$ with the action $\pi(s')$ the learned policy would take — $\Phi'$ is the only policy-dependent quantity. Least-squares policy iteration (LSPI) alternates: compute $w_Q$ for $\pi_k$ by LSTDQ, set $\pi_{k+1}$ greedy with respect to it, rebuild $\Phi'$, repeat.

The catch: none of this addresses distribution shift. LSTD is empirical risk minimization by least squares, and the greedy improvement step is exactly the adversarial maximization from earlier — so LSPI and all approximate dynamic programming methods still suffer action distribution shift. These methods answer “how do you estimate a value function from a batch,” assuming simple function approximators where the damage is mild; with deep networks the damage is severe, and fixing it properly is the subject of the next lecture.

Check yourself

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

Problem 15.1 stitching beats the data

Construct (or reason through) a deterministic MDP with states A, B, C and a dataset containing only two trajectories: one going A to B with reward 0, one going B to C with reward 10 (episodes end at C). No trajectory in the data starts at A and reaches C. Explain (a) what behavior cloning on the best trajectory gives you if you start at A, (b) why Q-learning on this dataset recovers the A-to-C behavior, and (c) which property of value-based methods this illustrates.

Show solution

(a) The best trajectory in the data is B-to-C, but it says nothing about A: cloning it gives undefined (or arbitrary) behavior at A, and cloning the A-trajectory gives reward 0. No pure imitation of any single trajectory achieves reward 10 from A. (b) Q-learning propagates value through the Bellman backup regardless of which trajectory a transition came from: the B-to-C transition gives $Q(B, \text{go-C}) = 10$, and then the A-to-B transition’s target $r + \gamma \max_{a'} Q(B, a')$ assigns $Q(A, \text{go-B}) = \gamma \cdot 10$. The greedy policy from A goes to B then C, a composite behavior present in no trajectory. (c) This is stitching: dynamic programming recombines pieces of different trajectories, which is why offline RL can exceed the best behavior in the dataset — and why value-based methods, not imitation, are its natural foundation.

Problem 15.2 OOD vs out-of-sample

A Q-function is trained on driving data where the behavior policy chooses steering angles from a Gaussian centered on lane-following. At test time it is queried on: (i) a steering angle never present in the dataset but well within the Gaussian’s high-density region; (ii) a hard swerve far outside the support of the behavior distribution; (iii) an in-distribution action in a state whose exact pixel observation was never seen. For each, say whether this is an out-of-sample or out-of-distribution query, and whether a well-trained Q-function should be trusted. Why did early offline RL research go wrong by conflating these?

Show solution

(i) Out-of-sample but in-distribution: new point from the same distribution — exactly what supervised generalization handles; trust it. (ii) Out-of-distribution: outside the support of $\pi_\beta$, so there is no evidence about its value; the Q-function’s output is unconstrained extrapolation and must not be trusted (and a maximizing policy will seek out precisely such actions). (iii) Also out-of-sample, in-distribution — with respect to the state distribution this time; generalization across similar states is again expected to work. Early methods that penalized all unseen actions threw away generalization entirely, and could never do better than the data; methods that trusted all unseen actions got fooled by OOD extrapolation. The entire design problem of offline RL is keeping (i) and (iii) while refusing (ii).

Problem 15.3 doubly robust unbiasedness

In the bandit setting with actions sampled as $a \sim \pi_\beta(\cdot \mid s)$, prove that the doubly robust estimator $V_{\text{DR}}(s) = \hat{V}(s) + \rho(s,a)\,(r(s,a) - \hat{Q}(s,a))$ with $\rho = \pi_\theta(a \mid s)/\pi_\beta(a \mid s)$ satisfies $\mathbb{E}_{a \sim \pi_\beta}[V_{\text{DR}}(s)] = \mathbb{E}_{a \sim \pi_\theta}[r(s,a)]$ whenever $\hat{V}(s) = \mathbb{E}_{a \sim \pi_\theta}[\hat{Q}(s,a)]$ — for any $\hat{Q}$. Where does the variance reduction come from?

Show solution

Take the expectation term by term. The importance-weighted reward is the standard unbiased estimator: $\mathbb{E}_{a \sim \pi_\beta}[\rho\, r] = \sum_a \pi_\beta(a \mid s) \frac{\pi_\theta(a \mid s)}{\pi_\beta(a \mid s)} r(s,a) = \mathbb{E}_{a \sim \pi_\theta}[r(s,a)]$. By the same computation, $\mathbb{E}_{a \sim \pi_\beta}[\rho\, \hat{Q}] = \mathbb{E}_{a \sim \pi_\theta}[\hat{Q}(s,a)] = \hat{V}(s)$. So $\mathbb{E}[V_{\text{DR}}] = \hat{V}(s) + \mathbb{E}_{\pi_\theta}[r] - \hat{V}(s) = \mathbb{E}_{a \sim \pi_\theta}[r(s,a)]$: the $\hat{V}$ and $\rho\hat{Q}$ terms cancel exactly in expectation, regardless of how bad $\hat{Q}$ is — only the consistency of $\hat{V}$ with $\hat{Q}$ was used. Variance: the high-variance object is the importance-weighted term, now $\rho\,(r - \hat{Q})$ instead of $\rho\, r$. If $\hat{Q} \approx r$, the residual is near zero and the importance weight multiplies almost nothing; the deterministic low-variance $\hat{V}$ carries the estimate. This is precisely the control-variate logic of baselines, applied to importance sampling.

Problem 15.4 LSTD mechanics

(a) Starting from the vector Bellman equation $V^\pi = r + \gamma P^\pi V^\pi$, derive the closed-form solution for $V^\pi$ and state the dimensional bookkeeping ($V^\pi$, $r$, $P^\pi$). (b) In sample-based LSTDQ, exactly one quantity must be recomputed when the policy changes during LSPI. Which one, and why not the others?

Show solution

(a) Move the value term left: $V^\pi - \gamma P^\pi V^\pi = r$, i.e. $(I - \gamma P^\pi) V^\pi = r$. Here $V^\pi$ and $r$ are vectors of length $|S|$ (one entry per state) and $P^\pi$ is the $|S| \times |S|$ state-transition matrix induced by $\pi$ — so this is $|S|$ linear equations in $|S|$ unknowns. The matrix $I - \gamma P^\pi$ is always invertible (as the lecture notes, not trivial to show but true), so $V^\pi = (I - \gamma P^\pi)^{-1} r$ exists and is unique. Policy evaluation for fixed $\pi$ is a linear solve. (b) Only $\Phi'$, the matrix of features at the next time step. Each of its rows featurizes the dataset’s $s'_i$ paired with the action $\pi(s'_i)$ that the current learned policy would take there — so it changes every time the policy is improved. The feature matrix $\Phi$ (dataset states and dataset actions) and the reward vector come straight from the fixed dataset, and no new environment samples are needed: the dynamics enter only through the recorded $s'_i$. That is what makes LSPI a genuinely offline algorithm — and its greedy $\arg\max$ improvement step is also exactly where the unaddressed distribution-shift problem lives.