M8-T3 — Extrapolation Error in Offline RL

Learning objectives

After this lesson, you should be able to:

• Explain why a max over actions in a bootstrapped target trusts Q values of actions the data never show.
• Reproduce the tabular demonstration: sweep an optimistic initial value and read the believed and true values of the greedy policy.
• Work a chain of backups to show how one wrong value contaminates its predecessors, and why bootstrapping does not average it away.
• Describe the function-approximation version, the deadly triad, and what behaviour-constrained and penalised backups change.

The intuition

Ask ten colleagues which restaurant on a street is the best, but let them only report places they have eaten at. Nine of them name places they know. A tenth says "the one at the end must be fantastic" and has never been in. If you pick the maximum over everything you have heard, you may pick the one with no evidence behind it. The more places a restaurant guide lists without reviews, the more likely a made-up score is the highest one.

Offline Q-learning does exactly this. For each logged transition it computes a target from "the best action in the next state". In a state where the log shows two actions, the other two have never been scored by data. Their entries hold the initial value, or, in a neural network, whatever the function happens to extrapolate. The max chooses the highest number among all four, scored or not.

In the online setting the story ends better. An online learner that overrates an unvisited action tends to take it, finds the real, lower, result and updates; the error is corrected by the very act of going there. The figure shows what happens when it cannot go there. The belief rises with q0; the policy’s true value falls; nothing in the log ever argues. This is extrapolation error: the error from evaluating the Q function on state-action pairs outside the data distribution, and then acting on it.

The mathematics

Where the Bellman target reads unseen entries

naive offline Q-learning, one pass over each logged transition (s, a, r, s′, d):

Every entry that the log never visits is read but never written, so it keeps its initial value for ever. If that value is higher than the truth, the max prefers it, and every pair that leads to that state inherits the inflated number through the target. The update only repairs entries with data; it cannot repair a belief about an entry without data.

Overestimation compounds through bootstrapping

Suppose the value at some state s is overestimated by e: the table says V(s) + e. A pair (s₋₁, a) whose logged transition leads to s gets the target r + γ (V(s) + e), which is wrong by γ e. The next one back is wrong by γ² e, and so on. The error shrinks by only the factor γ per link, and with γ = 0.95 and a route of 20 steps 36% of it survives. Bootstrapping does not average errors out; it relays them. In the online case, new data about the culprit entry fix the whole chain from its source; offline, the source is never touched.

q0

The initial value of every table entry, 0 unless stated. A large q0 is the tabular stand-in for optimistic extrapolation (the notes of this module call it that); it is a modelling device, not what a real network does.

phantom value

A Q entry whose pair is absent from the log, so that no update ever changes it.

believed value

The largest Q at the start state: what the learner thinks its policy is worth.

true value

The exact expected return of the learner’s greedy policy from the start (evaluatePolicyDP).

extrapolation error

The error in the Q value of a pair that lies outside the data, which the target uses without checking.

The function-approximation version

With a network Q(s, a; θ) there is no table and no initial value, but the same two ingredients are present. The network is trained by regression on logged pairs only. At other pairs its output is whatever its architecture and weights happen to extrapolate, and nothing ties it to the truth; a smooth network makes errors that are correlated with those of nearby pairs and unrelated to the consequences. The max (or, with continuous actions, an actor trained to find actions of maximum Q) searches precisely for the pairs where the output is largest. Fujimoto, Meger and Precup (2019) named this extrapolation error and, to the best of my recollection, reported that standard off-policy deep RL agents trained from a fixed batch performed poorly even when the batch came from a good policy; they proposed constraining the learned policy to actions similar to those in the batch (BCQ). I describe their argument at this level and have not run a network here. The effect is not always optimistic: extrapolation can be too low as well. The max selects the high errors, which is why the effect on decisions tends to be optimistic.

The deadly triad, and a similar but different bias

Sutton and Barto (2018, chapter 11) call function approximation, bootstrapping and off-policy training together "the deadly triad": any two are manageable, all three can make learning diverge, with value estimates growing without bound. The offline setting has all three by construction (the data are off-policy, the target bootstraps, the value is approximated by a network). Divergence is the extreme case; the milder case is the one in this lesson, a stable but wrong fixed point. A separate effect is the maximisation bias of Q-learning, which overestimates even when every action has data, because a max over noisy estimates is biased upward; it is the reason for double Q-learning (van Hasselt, Guez and Silver, 2016, for the deep version). Extrapolation error is worse because the noise is not just large but unconstrained by any data.

What constrained and penalised backups change

A worked example

Every number below is a real output of Node against RLCore: the ward (slip 0.2, step reward −0.1, goal +10, stairwell −10; discount 0.95; optimal value at the start 3.31), the behaviour policy optimal with ε = 0.2, 60 episodes per log (about 937 transitions), offlineQ naive with 80 sweeps and step size 0.3, mean of 20 seeds. "True value" is the exact value of the greedy policy at the start. The table sweeps q0.

For q0 up to 3 the rows are identical (I did not investigate why, beyond noting that the unseen entries then do not change which action is largest); q0 = 4 changes one number. From 5 the phantoms start to win, and from 8 every seed is stuck. "Stuck at −2.00" means the policy never reaches the goal: −0.1 / (1 − 0.95) is exactly −2. The believed value does the opposite of the true value: 4.52 at q0 = 0 against 9.13 at q0 = 10, while the optimum of the world is 3.31. At q0 = 10 the learner believes its start is worth 9.13 and its policy is worth −2.00, an overestimate of 11.13 (95% interval 10.95 to 11.31). Even the behaviour-constrained learner, which does not read unseen entries, overestimates by 3.68 (2.82 to 4.55) at q0 = 0; I attribute it to the max over noisy estimates and the constant step size, and did not separate those two. The q0 threshold of about 5 is for this world and this log; it is not general. With a broader log the same sweep is gentler: at ε = 0.5, q0 = 0, 5, 10 gave 1.85, 1.21 and −1.93; at ε = 0.9 they gave 2.29, 2.29 and 1.71.

Tracing one log by hand (seed 1, q0 = 10). The logged transitions at state 19 (row 2, column 1, the corridor cell below the start) are up 8 times and left once. The pair (19, right) is a bump into a wall, (19, down) goes to an open cell; neither appears in the log. Their entries stay at 10.00 for ever. The row of Q for state 19 is up 8.89, right 10.00, down 10.00, left 9.40; the true values are 2.99, 2.74, 2.50, 2.74.

Now every logged pair that leads to 19 reads max Q(19, ·) = 10. The start (state 10) has one logged transition "down", which leads to state 19, so its target is −0.1 + 0.95 × 10 = 9.40 and Q(10, down) converges to 9.40. The logged bump "left" at the start keeps Scout at 10, so it reads max Q(10, ·) = 9.40 and settles at −0.1 + 0.95 × 9.40 = 8.83. The learner’s row at the start is up 8.57, right 8.39, down 9.40, left 8.83. The true values are 3.09, 3.31, 2.84, 3.02. The greedy action is "down" because the number is the largest, the number is large only because of the phantom at 19, and the policy then arrives at state 19 and chooses "right", into the wall. It stays there. In this log the greedy choice is an unlogged action in 13 of 23 states; over the 20 seeds the mean is 13.45 (13.13 to 13.77), and 48% of those choices (45% to 51%) bump into a wall, an action that cannot be a good idea in a hall.

The chain, computed. Take a route of states each with one logged step of reward −0.1 leading to state 19, whose phantom entry holds 10 against a true value of V(19) = 2.99. After k backups the naive value k links before 19 and the true one are:

(The chain is an idealisation I built: a deterministic route with reward −0.1 per step. The numbers 9.40 and 8.83 are the ones the real log produced.) The error shrinks by only 5% per link. Twenty links away, 2.5 units remain, almost as much as the whole optimal value of the world (3.31). All the routes through state 19 are inflated; any route that gets to a state with a phantom looks better than the true best route, and the gap grows with how many logged transitions feed it.

What the conservative backups do to the same logs. The behaviour-constrained backup (max only over logged actions at s′) and the penalised backup (target − 1/√count), both with q0 = 0, gave 0.84 and 1.85 on these 20 logs against −2.00 for the naive one at q0 = 10. But do not read those as "fixed". At q0 = 10 the constrained backup gave −0.16 (−1.15 to 0.84) and the penalised backup −2.00: the constrained learner never reads an unseen entry in a max, I suspect, without having tested it, that its logged entries also start at 10 and 80 sweeps do not wash that out; and the penalty, in this implementation, lowers the target of the pair being updated and not the unseen entry that the max reads, so it depends on q0 being modest. I take this as a reminder that "conservative" is a property of how a backup is built, and that the preview of lesson M8-T4 has to look at these details.

What this simulation simplifies. The initial value q0 stands in for the extrapolation of a network, which has no initial value and may be too high or too low. A tabular world cannot show the generalisation between nearby pairs that makes a network’s errors correlated. The sweep holds the log and the learner fixed and varies only q0; the demonstration is of a mechanism, not a measurement of any deep-RL system.

Engineering implications and limitations

Symptoms of extrapolation error in a training run

Practical rules

• Plot the believed value against the logged returns. A believed value above the best logged return is a warning, as it was in the sweep (9.13 against an optimum of 3.31). The sign is only a warning: a value below the truth is also possible.
• Bound the learner by the data. Restrict the max or the actor to actions near the logged ones, or penalise by uncertainty (lesson M8-T4). The tabular rule is a count; the deep rule is a distance, a learned behaviour model or an ensemble.
• Keep targets stable with the tools of lesson M6-T6: target networks, clipped double Q, and small learning rates. These reduce divergence but do not fix a gap in the data.
• Compare with the behaviour policy. If the learned policy cannot be shown to beat the logged behaviour on a held-out evaluation, deploy the behaviour policy.
• Relate it to the model case. A model-based planner exploits model errors in the same way a value function exploits its extrapolation (lesson M7-T3); and a cloned policy drifts off the data in the way of lesson M3-T3. The common cause is acting where the data do not reach. Lab M8-L2 measures where that is, and lab M8-L3 compares the naive, constrained and penalised backups on the same logs; replay buffers (lesson M8-T5) are the online-side relative of the same data question.

Common misconceptions

Engineering takeaways

1. A max over actions in the Bellman target reads Q at pairs the log never visits; those entries are never updated, so they keep their arbitrary value and the max prefers the largest.
2. On the ward, sweeping the unseen entries’ value q0 from 0 to 10 moved the believed value at the start from 4.52 to 9.13 and the true value of the greedy policy from 0.84 to −2.00 (optimum 3.31, 20 seeds).
3. Bootstrapping relays an overestimate backwards at a factor γ per link (7.01 becomes 2.5 after 20 links at γ = 0.95), and offline nothing corrects its source.
4. With a network the same thing happens through extrapolation (Fujimoto, Meger and Precup, 2019), and together with bootstrapping and off-policy data it is the deadly triad of Sutton and Barto (see also lesson M6-T1).
5. Behaviour-constrained and penalised backups limit or discount the unseen entries (lesson M8-T4), but the construction details decide whether they work.

References and further reading

Fujimoto, Meger and Precup introduced the term extrapolation error for fixed-batch deep RL; Levine et al. survey the offline problem; Sutton and Barto discuss the deadly triad; van Hasselt et al. is the deep double Q-learning paper.

• S. Fujimoto, D. Meger and D. Precup, “Off-Policy Deep Reinforcement Learning without Exploration”, Proceedings of the 36th International Conference on Machine Learning (ICML), 2019.
• S. Levine, A. Kumar, G. Tucker and J. Fu, “Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems”, arXiv:2005.01643, 2020.
• R. S. Sutton and A. G. Barto, Reinforcement Learning: An Introduction, 2nd edition, MIT Press, 2018.
• H. van Hasselt, A. Guez and D. Silver, “Deep Reinforcement Learning with Double Q-learning”, Proceedings of the AAAI Conference on Artificial Intelligence, 2016.

Knowledge check

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

What’s next

We now know what goes wrong and where. The next lesson, M8-T4, describes the families of methods that keep the learner within the data: behaviour-constrained backups, conservative value estimates and implicit methods that never query an unseen action, and what each does and does not guarantee.

Related content

Nothing below is required to finish this lesson.

• Before
  M8-T2: Dataset Coverage and Quality

  Measure what a dataset covers and what it never shows, and relate coverage to what can be learned.

• Lab
  M8-L3: Compare Online and Offline Policies

  Train one policy online and one from a fixed log, and explain why the offline one fails in states the log never showed.