---
title: Animal Learning and Cognition
module: Reinforcement Learning in Minds and Brains
moduleNumber: 6
lessonNumber: 5
order: 605
summary: >
  Three classic associative phenomena turn out to be reinforcement-learning
  mechanisms seen in behavior. Blocking says learning is driven by prediction
  error, not co-occurrence, and reduces to least-squares regression fitting a
  collinear feature. Higher-order conditioning and conditioned reinforcement make a
  value estimate a secondary reinforcer — bootstrapping in an animal. Delayed
  reinforcement is the credit-assignment problem, and the stimulus traces and goal
  gradients of Pavlov and Hull are eligibility traces and TD-learned value
  functions.
topics: [Minds and Brains]
sources:
  - book: Sutton & Barto
    ref: "Ch. 14 — Psychology; §14.2.1 Blocking and Higher-order Conditioning"
  - book: Sutton & Barto
    ref: "§14.4 Delayed Reinforcement"
---

The [psychology of reinforcement](/reinforcement-learning/minds-and-brains/psychology-of-reinforcement)
set out the correspondence: prediction is classical conditioning,
control is instrumental conditioning, and the Rescorla–Wagner and TD models turn
associative learning into prediction-error updates. That lesson compressed
three phenomena. Each deserves a full
treatment, because each is a case where a mechanism this course _derives_ from the
optimization problem was first _measured_ in an animal, decades earlier, by
someone with no computer in mind.[^psych-links]

Take the three in order. **Blocking** is the experiment that forced the field to
say learning is driven by prediction error, not by two events co-occurring in
time; alongside it, **higher-order conditioning** and **conditioned
reinforcement** are how a learned prediction becomes a stand-in reward — the
behavioral face of a value function. **Delayed reinforcement** is the
credit-assignment problem in an animal, and the two mechanisms animal-learning
theory proposed to solve it, stimulus traces and secondary reinforcement, are
eligibility traces and TD-learned values. **Cognitive maps** are internal models:
Tolman's rats learned the layout of a maze with no reward at all, which is
model-based reinforcement learning, and the way they learned it is what control
engineers call system identification.

## Blocking

Beyond the anticipatory nature of the conditioned response, two properties of
classical conditioning figure most prominently in models of it: blocking and
higher-order conditioning. Blocking is the pivotal one. It occurs when an animal
_fails_ to learn a conditioned response to a potential conditioned stimulus,
because that stimulus is presented in compound with another one that was already
conditioned to produce the response.[^blocking-sb]

Kamin's experiment has three phases. Take the rabbit nictitating-membrane
preparation, where a tone conditioned stimulus predicts an air puff to the eye
(the unconditioned stimulus), and the rabbit learns to close its protective
membrane in anticipation.

- **Phase 1.** Condition the rabbit to a tone alone, paired with the air puff,
  until the tone reliably produces the membrane-closure conditioned response. The
  tone now predicts the puff.
- **Phase 2.** Present a _compound_ stimulus — the same tone _plus_ an added light
  — paired with the same air puff, for many trials. The light co-occurs with the
  puff on every one of these trials.
- **Phase 3.** Test the light alone. The rabbit produces very few, or no,
  conditioned responses to the light. Learning to the light was **blocked** by the
  prior learning to the tone.[^kamin-control]

$$
% caption: Kamin's blocking design. Phase 1 conditions the tone alone to the air
% puff; phase 2 adds a redundant light to the already-predictive tone; phase 3
% tests the light alone and finds almost no conditioned response. The light
% predicts the puff as reliably as the tone, yet nothing is learned about it.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  cs/.style={draw, minimum width=12mm, minimum height=7mm, font=\scriptsize},
  us/.style={draw, minimum width=12mm, minimum height=7mm, font=\scriptsize},
  ph/.style={font=\scriptsize, text=black}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % phase 1
  \node[ph] at (1.5,2.9) {phase 1: tone alone};
  \node[cs, draw=acc, text=acc] (t1) at (0.5,2.1) {tone};
  \node[us] (u1) at (2.6,2.1) {pu\/f\/f};
  \draw[->, acc, thick] (t1) -- (u1);
  \node[anchor=west, font=\scriptsize, text=black] at (3.3,2.1) {tone predicts pu\/f\/f};
  % phase 2
  \node[ph] at (1.6,1.05) {phase 2: tone + light compound};
  \node[cs, draw=acc, text=acc] (t2) at (0.5,0.25) {tone};
  \node[cs, draw=red, text=red] (l2) at (0.5,-0.65) {light};
  \node[us] (u2) at (2.6,-0.2) {pu\/f\/f};
  \draw[->, acc, thick] (t2) -- (u2);
  \draw[->, red, thick] (l2) -- (u2);
  \node[anchor=west, font=\scriptsize, text=black] at (3.3,-0.2) {pu\/f\/f already predicted};
  % phase 3
  \node[ph] at (1.5,-1.75) {phase 3: test light};
  \node[cs, draw=red, text=red] (l3) at (0.5,-2.55) {light};
  \node[us, dashed] (r3) at (2.6,-2.55) {no CR};
  \draw[->, red, thick, dashed] (l3) -- (r3);
  \node[anchor=west, font=\scriptsize, text=black] at (3.3,-2.55) {light was blocked};
\end{tikzpicture}
$$

Blocking breaks the simplest theory of conditioning, the one that says
a necessary and sufficient condition for conditioning is _temporal contiguity_ —
the unconditioned stimulus frequently following a conditioned stimulus closely in
time.[^contiguity] By that theory the light should condition just fine: in phase 2
it precedes the air puff on every trial, contiguous with it exactly as the tone
is. Yet almost nothing is learned about the light. Contiguity is present and
learning is absent. What the animal _already predicts_, it does not learn again.

The Rescorla–Wagner model was built mainly to account for this. It reads out of
the summed-error term in one line. After phase 1 the tone's associative strength
has reached the level the unconditioned stimulus supports, $V_{\text{tone}}
\approx R$. When the light (initially $V_{\text{light}} = 0$) joins the compound,
the prediction error on the first compound trial is

$$
R - V_{\text{tone+light}} \;=\; R - (V_{\text{tone}} + V_{\text{light}})
\;\approx\; R - R \;=\; 0,
$$

because the model's key assumption is that the aggregate strength is the _sum_ of
the components present. With the error already at zero, $\Delta V_{\text{light}} =
\alpha\beta \cdot 0 = 0$, and the light learns nothing, trial after trial. The
occurrence of the unconditioned stimulus is already predicted nearly perfectly, so
little or no error — no surprise — is introduced by the new component, and surprise
is the only thing that drives learning.[^rw-blocking]

> **Definition (Blocking).** A previously conditioned stimulus prevents learning
> about a redundant stimulus added in compound with it. Because the outcome is
> already predicted by the pretrained stimulus, the prediction error on the
> compound trials is near zero, so the added stimulus gains no associative
> strength.

The historical weight of the result is that it made a _mechanistic_ rule beat a
_cognitive_ one. Blocking looks like it needs a cognitive story — the animal
noticing that a component was added and reasoning that the old one already explains
the outcome. Rescorla and Wagner showed that no such reasoning is required: a
traditional contiguity theory, adjusted so the error term uses the aggregate
strength of everything present, accounts for blocking with a simple error-driven
update and nothing else.[^mechanistic] From the machine-learning side that update
is the Least-Mean-Square (Widrow–Hoff) rule, a regression algorithm that drives
mean-squared prediction error toward zero. Blocking is what a regression fit does
when a new feature is collinear with one already fit: the residual is gone, so the
new feature gets no weight.

### Blocking, trial by trial

The one-line argument is easy to accept and easy to under-feel. Running the numbers
shows the mechanism at work. Take $\alpha\beta = 0.3$, an unconditioned stimulus
that supports strength $R = 1$, and both components starting at $V = 0$. In phase 1
only the tone is present, so each trial updates $V_{\text{tone}} \gets V_{\text{tone}} +
0.3\,(1 - V_{\text{tone}})$. The strength climbs and the increments shrink as the
error shrinks:

| Phase-1 trial | error $1 - V_{\text{tone}}$ | $\Delta V_{\text{tone}}$ | $V_{\text{tone}}$ after |
| ---: | ---: | ---: | ---: |
| 1 | 1.00 | 0.300 | 0.300 |
| 2 | 0.70 | 0.210 | 0.510 |
| 3 | 0.49 | 0.147 | 0.657 |
| 4 | 0.34 | 0.103 | 0.760 |
| 5 | 0.24 | 0.072 | 0.832 |

After a handful more trials the tone sits near $0.95$; take it into phase 2 at
$V_{\text{tone}} \approx 0.95$, with the light joining fresh at $V_{\text{light}} = 0$.
Now the compound's aggregate strength is $V_{\text{tone}} + V_{\text{light}}$, and the
error every component sees is $1 - (V_{\text{tone}} + V_{\text{light}})$. The tone has
already all but closed the gap, so that error is tiny, and the light's share of a tiny
error is tinier still:

| Phase-2 trial | $V_{\text{tone}}$ | $V_{\text{light}}$ | error | $\Delta V_{\text{light}}$ |
| ---: | ---: | ---: | ---: | ---: |
| 1 | 0.950 | 0.000 | 0.050 | 0.015 |
| 2 | 0.9635 | 0.015 | 0.0215 | 0.0065 |
| 3 | 0.9700 | 0.0215 | 0.0085 | 0.0026 |
| 4 | 0.9727 | 0.0241 | 0.0032 | 0.0010 |

The light gains about $0.024$ over four compound trials and is still crawling toward a
ceiling under $0.03$. It will never do much better: the tone and light split whatever
error remains, and the tone entered the phase already near the ceiling, so there is
almost nothing to split. Contrast a **control** group that skips phase 1 entirely and
meets the compound cold, both components at $0$. There the first-trial error is the
full $1 - (0 + 0) = 1$, the light takes its half-share $\Delta V_{\text{light}} = 0.15$,
and across the same four trials it climbs to roughly $0.28$ — an order of magnitude
above the blocked group. The light is physically identical in the two groups and
equally contiguous with the puff; the only difference is what the animal already
predicted walking in. Prediction, not contiguity, gates the learning.

$$
% caption: Blocking, run out numerically. The tone (blue) is conditioned alone in
% phase 1 and reaches the ceiling. In phase 2 the light (red, solid) joins the
% already-predictive tone and barely moves, because the error the two components
% share is nearly gone. A control light (red, dashed) that meets the compound with
% no phase-1 history sees the full error and conditions normally.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % axes
  \draw[->, black] (0,0) -- (8.0,0) node[anchor=west, black, font=\scriptsize] {trials};
  \draw[->, black] (0,0) -- (0,3.4) node[anchor=south, black, font=\scriptsize] {assoc. strength};
  \draw[black, dotted] (0,3.0) -- (7.5,3.0);
  \node[anchor=south east, font=\scriptsize, text=black] at (7.5,3.0) {ceiling};
  % phase boundary
  \draw[black, dotted] (3.4,0) -- (3.4,3.2);
  \node[anchor=south, font=\scriptsize, text=black] at (1.7,3.15) {phase 1};
  \node[anchor=south, font=\scriptsize, text=black] at (5.4,3.15) {phase 2};
  % tone curve: rises in phase 1, flat in phase 2
  \draw[acc, very thick] (0.15,0.0) .. controls (1.2,2.1) and (2.2,2.75) .. (3.4,2.88)
    -- (7.3,2.94);
  \node[acc, anchor=west, font=\scriptsize] at (7.3,2.94) {tone};
  % blocked light: flat near zero through phase 2
  \draw[red, very thick] (3.4,0.06) .. controls (4.6,0.16) and (6.0,0.22) .. (7.3,0.26);
  \node[red, anchor=west, font=\scriptsize] at (7.3,0.26) {light (blocked)};
  % control light: rises in phase 2
  \draw[red, very thick, dashed] (3.4,0.06) .. controls (4.6,0.9) and (6.0,1.35) .. (7.3,1.55);
  \node[red, anchor=west, font=\scriptsize] at (7.3,1.55) {light (control)};
\end{tikzpicture}
$$

### The collinear-feature view

The regression reading of blocking is the exact
machine-learning mirror of the phenomenon, and it explains _why_ the added stimulus gets
no weight, not merely _that_ it does. Treat each trial as a supervised example: the
input is a feature vector marking which stimuli are present, the target is the
unconditioned-stimulus magnitude $R$, and the associative strengths are the regression
weights. Least-mean-square regression moves the weights down the gradient of squared
error, which is precisely the Rescorla–Wagner update.[^lms]

In phase 1 the tone feature $x_1$ alone is switched on, and its weight $w_1$ is driven
until $w_1 x_1$ matches the target — the residual on those trials goes to zero. Phase 2
switches on a second feature $x_2$ (the light) that, across every compound trial, is
_perfectly correlated_ with the first: whenever the tone fires the light fires, and both
fire on exactly the trials where the target is $R$. A perfectly collinear feature adds
no independent information about the target. The residual it would be fit against is
already zero, so the gradient with respect to $w_2$ is zero, and $w_2$ stays put. Least
squares cannot separate the contributions of two features that always move together; it
credits the one it saw first and leaves the redundant one at whatever it started, which
here is nothing.

$$
% caption: Blocking as collinear regression. The target R is already explained by the
% tone weight fit in phase 1 (blue arrow reaches the target). The light is a second
% feature perfectly correlated with the tone, so the residual it could reduce is zero
% (red bracket) and least squares assigns it no weight. This is the same computation
% as the near-zero prediction error on the compound trials.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % number line for the prediction
  \draw[black, ->] (0,0) -- (7.4,0) node[anchor=west, font=\scriptsize, text=black] {prediction};
  \foreach \x in {0,2,4,6} \draw[black] (\x,-0.08) -- (\x,0.08);
  \node[anchor=north, font=\scriptsize, text=black] at (0,-0.12) {0};
  \node[anchor=north, font=\scriptsize, text=black] at (6,-0.12) {R (target)};
  % tone contribution reaches target
  \draw[acc, very thick, ->] (0,0.7) -- (6,0.7);
  \node[acc, anchor=south, font=\scriptsize] at (3,0.72) {tone weight explains R};
  % light: zero residual to fit
  \draw[red, thick] (6,0.35) -- (6,1.05);
  \draw[red, thick, <->] (5.9,1.35) -- (6.1,1.35);
  \node[red, anchor=west, font=\scriptsize, align=left] at (6.2,1.35)
    {residual $=0$,\\so light gets no weight};
\end{tikzpicture}
$$

The identity is not loose analogy. Widrow and Hoff (1960) derived the least-mean-square
rule as an adaptive filter; Rescorla and Wagner (1972) derived their conditioning rule
from animal data; the update equation is the same, and blocking falls out of the
collinearity structure either way. The animal-learning result and the regression fact
are one computation seen from two disciplines.

## Higher-order conditioning and conditioned reinforcement

The second prominent property is **higher-order conditioning**: a
previously-conditioned conditioned stimulus can itself act as an unconditioned
stimulus for a new, initially neutral stimulus.[^hoc-sb]

Pavlov's demonstration is the cleanest. His assistant first conditioned a dog to
salivate to a metronome that predicted food. Then, in a second stage, a black
square — to which the dog was indifferent — was placed in the dog's line of vision
and followed by the sound of the metronome, and this was _never_ followed by food.
Within about ten trials the dog began to salivate merely on seeing the black
square, even though the sight of it had never been paired with food. The
metronome, though it is not food, acted as an unconditioned stimulus in
conditioning a salivation response to the square. This is **second-order
conditioning**. If the black square were then used to condition yet another
neutral stimulus, that would be third-order, and so on.[^pavlov-square]

$$
% caption: Higher-order conditioning. First the metronome is conditioned to
% predict food (first order). Then the black square is paired with the metronome
% and never with food, yet the square comes to elicit salivation (second order).
% The metronome transfers its predictive value without the food ever appearing.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  s/.style={draw, minimum width=16mm, minimum height=8mm, font=\scriptsize, align=center}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % first order
  \node[s, draw=acc, text=acc] (met) at (0,0.9) {metronome};
  \node[s] (food) at (3.4,0.9) {food};
  \draw[->, acc, thick] (met) -- (food) node[midway, above, font=\scriptsize] {f\/irst order};
  \node[anchor=west, font=\scriptsize, text=black] at (4.3,0.9) {metronome predicts food};
  % second order
  \node[s, draw=red, text=red] (sq) at (0,-1.1) {black square};
  \node[s, draw=acc, text=acc] (met2) at (3.4,-1.1) {metronome};
  \draw[->, red, thick] (sq) -- (met2) node[midway, above, font=\scriptsize] {second order};
  \node[anchor=west, font=\scriptsize, text=black, align=left] at (4.3,-1.1)
    {square predicts metronome,\\never food};
  % transfer arrow
  \draw[->, black, thick, dashed] (met.south) to[bend right=25] (met2.north);
  \node[font=\scriptsize, text=black, anchor=east] at (-0.1,-0.1) {value transfers};
\end{tikzpicture}
$$

Higher-order conditioning is hard to demonstrate above the second order, because a
higher-order reinforcer loses its reinforcing value if it is not itself
occasionally re-paired with the original unconditioned stimulus. Present the black
square enough times without the metronome ever leading back to food, and its
borrowed value extinguishes. Under favorable conditions — intermixing first-order
trials with higher-order ones, or adding a general energizing stimulus — orders
beyond the second can be shown.[^hoc-hard] The Rescorla–Wagner model, which only
ever pushes strengths toward the unconditioned-stimulus level, has no mechanism for
this at all; the TD model produces it for free, because a change in prediction from
one instant to the next has the same status as the unconditioned stimulus, and the
metronome supplies just that to the square.

### Why higher-order conditioning rises then falls

The TD model does more than allow higher-order conditioning; it predicts the peculiar
_shape_ of its time course, and the shape is why third and higher orders are so hard to
get. Run the second-order simulation the way Sutton and Barto do. In a first phase, CSB (the
metronome) is conditioned to the unconditioned stimulus until its strength saturates —
say $V_{\text{B}} \approx 1.65$ in the units of one published run. Then the second phase
begins: CSA (the square) is presented followed by CSB, and the unconditioned stimulus
is _never_ delivered. Two things happen at once on every second-order trial.

CSA learns from the drop in prediction between seeing CSA and then seeing CSB, because
in the TD error the term $\hat v(S_{t+1}) - \hat v(S_t)$ has the same status as a
reward. So long as CSB still carries strength, CSA sees a positive target and climbs.
But CSB is now in extinction — it predicts an unconditioned stimulus that no longer
comes, so its own strength decays trial by trial. The reinforcer CSA is feeding on is
draining. CSA therefore rises while CSB is still strong, reaches a peak, and then falls
as CSB's collapse pulls the target it feeds on down toward zero.

| 2nd-order trial | $V_{\text{B}}$ (drains) | target CSA sees ($\propto V_{\text{B}}$) | $V_{\text{A}}$ |
| ---: | ---: | ---: | ---: |
| 0 | 1.65 | — | 0.00 |
| 2 | 1.30 | high | 0.42 |
| 4 | 0.95 | moderate | 0.68 |
| 6 | 0.62 | falling | 0.71 (peak) |
| 8 | 0.38 | low | 0.58 |
| 10 | 0.21 | near zero | 0.41 |

The numbers are illustrative of the published trajectory, not a fit to any one animal,
but the qualitative pattern — CSA up then down, tracking CSB's decay with a lag — is
what both the TD model and animal experiments show.[^hoc-shape]

$$
% caption: Second-order conditioning in the TD model. CSB (blue), conditioned first,
% goes into extinction during the second-order phase because the US is withheld, so
% its strength decays. CSA (red) borrows strength from CSB through the TD error, so it
% rises while CSB is strong, peaks, then falls as its secondary reinforcer drains away.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \draw[->, black] (0,0) -- (7.6,0) node[anchor=west, black, font=\scriptsize] {second-order trials};
  \draw[->, black] (0,0) -- (0,3.6) node[anchor=south, black, font=\scriptsize] {assoc. strength};
  % CSB decaying from high
  \draw[acc, very thick] (0.1,3.2) .. controls (1.6,2.1) and (3.4,1.1) .. (7.2,0.35);
  \node[acc, anchor=west, font=\scriptsize] at (7.2,0.4) {CSB (extinguishing)};
  % CSA rise then fall
  \draw[red, very thick] (0.1,0.1) .. controls (1.6,1.4) and (2.6,1.85) .. (3.4,1.9)
    .. controls (4.4,1.95) and (5.6,1.35) .. (7.2,0.85);
  \node[red, anchor=west, font=\scriptsize] at (7.2,0.9) {CSA (borrowed)};
  \fill[red] (3.4,1.9) circle (1.6pt);
  \node[red, anchor=south, font=\scriptsize] at (3.4,1.95) {peak};
\end{tikzpicture}
$$

This is the whole difficulty with orders beyond the second, stated mechanically. Each
higher order feeds on the strength of the one below it, and each order below is being
extinguished the moment you stop pairing it with the real unconditioned stimulus. The
borrowed strength decays faster than the next order can accumulate it, so the chain
starves. The fix animal researchers use follows straight from the mechanism:
interleave occasional first-order trials to refresh the bottom of the chain before it
extinguishes. Finch and Culler (1934) reached as high as fifth-order withdrawal
conditioning in dogs by keeping motivation high and periodically renewing the
lower-order links — evidence that the ceiling on order is set by extinction of the
borrowed reinforcer, not by any hard limit on bootstrapping itself.[^finch]

### Conditioned reinforcement

The same phenomenon occurs on the instrumental side, and there it has a name that
connects straight to value functions. A stimulus that consistently predicts primary
reinforcement becomes a reinforcer itself. Primary reinforcement is the innately
rewarding or penalizing kind, built into the animal by evolution; the predicting
stimulus becomes a **secondary**, or more generally a **higher-order** or
**conditioned reinforcer**.[^cond-reinf] A conditioned reinforcer delivers
_conditioned reinforcement_: it acts like primary reinforcement, increasing an
animal's tendency to produce behavior that leads to conditioned reward and
decreasing the tendency to produce behavior that leads to conditioned penalty.

> **Definition (Conditioned reinforcement).** A stimulus that reliably predicts
> primary reinforcement acquires reinforcing power itself, and can then reinforce
> behavior in place of the primary reward. It is _conditioned_ because its value
> is learned from the prediction, not innate.

This is why an animal — or a person — will work for money. Money's worth derives
solely from what having it predicts. It is a conditioned reinforcer, and the
behavior it sustains matches what a value function, not a primary
reward, would drive.[^money]

The tie to this course is precise, and it is the argument of the whole module in
one line: **a value estimate is a secondary reinforcer**. In an actor–critic
architecture the critic uses a TD method to evaluate the actor's policy, and its
value estimates provide conditioned reinforcement to the actor, letting the actor
improve its policy.[^actor-critic] The critic's TD error is a conditioned reinforcer
in the technical, animal-learning sense: it acts like reward, it was learned from
prediction rather than given, and it lets the actor be trained even when primary
reward is absent from the current step. Higher-order conditioning in the lab and
bootstrapping in the algorithm are the same move — a learned prediction standing in
for the outcome it predicts.

$$
% caption: The critic in an actor-critic architecture supplies conditioned
% reinforcement. Its TD error, learned by predicting return, acts as a secondary
% reinforcer for the actor, giving immediate feedback even when the primary reward
% signal is delayed or absent on the current step.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  box/.style={draw, minimum width=22mm, minimum height=11mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[box, draw=acc, text=acc, thick] (critic) at (0,1.4) {critic\\(value estimate)};
  \node[box] (actor) at (0,-1.4) {actor\\(policy)};
  \node[box] (env) at (5.4,0) {environment};
  \draw[->, thick] (actor.east) to[bend right=18] node[midway, below, font=\scriptsize] {action} (env.south west);
  \draw[->, thick] (env.north west) to[bend right=18] node[midway, above, font=\scriptsize] {state, reward} (critic.east);
  \draw[->, acc, very thick] (critic) -- (actor) node[midway, right, font=\scriptsize, text=acc, align=left] {TD error =\\cond. reinforcer};
\end{tikzpicture}
$$

## Delayed reinforcement

The Law of Effect requires a backward effect: a consequence must reach back and
strengthen the connection that produced it. Early critics could not conceive how
the present could affect something already in the past, and the worry sharpened
when experiments showed learning still occurs with a considerable _delay_ between
an action and its consequent reward. The same holds in classical conditioning,
where learning occurs even when the unconditioned stimulus follows conditioned-
stimulus offset by a non-negligible interval. This is the problem of **delayed
reinforcement**, and it is Minsky's (1961) **credit-assignment problem for learning
systems**: how do you distribute credit for success among the many decisions that
may have been involved in producing it?[^delayed-sb]

$$
% caption: The credit-assignment problem. A reward at time T must be apportioned
% back among the many earlier actions that led to it; the trace of an early action
% has to still be present when the reward finally arrives for that action to get
% credit.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  a/.style={circle, draw, minimum size=6mm, inner sep=0pt, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  % action sequence
  \foreach \i/\x in {1/0, 2/1.4, 3/2.8, 4/4.2, 5/5.6} \node[a] (a\i) at (\x,0) {a\i};
  \foreach \i/\j in {1/2,2/3,3/4,4/5} \draw[->, black] (a\i) -- (a\j);
  % reward
  \node[draw, minimum width=12mm, minimum height=8mm, font=\scriptsize, draw=acc, text=acc] (rw) at (7.6,0) {reward};
  \draw[->, acc, thick] (a5) -- (rw);
  % credit-back arrows
  \foreach \i in {1,2,3,4} \draw[->, acc, dashed] (rw.north) to[bend right=20] (a\i.north);
  \node[font=\scriptsize, text=black, anchor=south] at (3.5,1.2) {which action deserves the credit?};
  \draw[->, black] (0,-0.9) -- (7.6,-0.9) node[anchor=west, black, font=\scriptsize] {time};
\end{tikzpicture}
$$

The algorithms in this course address delayed reinforcement with two mechanisms, and
both correspond to mechanisms proposed in theories of animal learning. The first is
**eligibility traces**. The second is **TD-learned value functions** that provide
nearly immediate evaluations of actions, in instrumental tasks, or nearly immediate
prediction targets, in classical ones.[^two-mech]

### Stimulus traces

Pavlov pointed out that every stimulus must leave a **trace** in the nervous system
that persists for some time after the stimulus ends, and he proposed that these
stimulus traces make learning possible when there is a temporal gap between the
conditioned-stimulus offset and the unconditioned-stimulus onset. This is why the
gapped arrangement is called trace conditioning: assuming a trace of the
conditioned stimulus remains when the unconditioned stimulus arrives, learning
occurs through the simultaneous presence of the trace and the unconditioned
stimulus.[^pavlov-trace]

Hull built decaying stimulus traces into his influential learning theory to
account for the **goal gradient** — his term for the way the maximum strength of an
instrumentally conditioned response falls off as the delay of reinforcement
increases. He hypothesized that an action leaves an internal stimulus whose trace
decays exponentially as a function of the time since the action was taken, and,
reading the animal data available to him, he estimated the traces effectively reach
zero after 30 to 40 seconds.[^hull-trace]

$$
% caption: A stimulus trace. An action or stimulus at time 0 leaves an internal
% signal that decays exponentially; reinforcement arriving later assigns credit in
% proportion to the trace's height at that instant, so nearer actions get more
% credit. This is Hull's goal gradient and the shape of an eligibility trace.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % axes
  \draw[->, black] (0,0) -- (7.2,0) node[anchor=west, black, font=\scriptsize] {time since action};
  \draw[->, black] (0,0) -- (0,3.2) node[anchor=south, black, font=\scriptsize] {trace height};
  % decaying trace curve z(t) = e^{-kt}
  \draw[acc, very thick] (0,2.8)
    .. controls (0.9,1.7) and (1.8,1.0) .. (3.0,0.62)
    .. controls (4.2,0.34) and (5.4,0.18) .. (6.6,0.1);
  \node[acc, anchor=west, font=\scriptsize] at (6.6,0.28) {trace};
  % reinforcement instant
  \draw[red, thick, dashed] (4.2,0) -- (4.2,0.34);
  \fill[red] (4.2,0.34) circle (2pt);
  \node[red, anchor=south west, font=\scriptsize] at (4.2,0.36) {reward here};
  \node[anchor=north, font=\scriptsize, text=black] at (4.2,-0.05) {delay};
  % credit height
  \draw[black, <->] (4.35,0) -- (4.35,0.32);
  \node[black, anchor=west, font=\scriptsize] at (4.45,0.16) {credit};
\end{tikzpicture}
$$

The eligibility traces this course uses are like Hull's: decaying traces of past
state visitations, or of past state–action pairs, that mark recent experiences as
_eligible_ for a learning update when reinforcement finally arrives. Klopf (1972)
introduced eligibility traces in a neuronal theory, where they are
temporally-extended traces of past activity at synapses — the connections between
neurons; Klopf's traces are more elaborate than the exponentially-decaying ones our
algorithms use, but the idea is his.[^klopf] The
[eligibility-traces](/reinforcement-learning/approximation/eligibility-traces)
mechanism, the vector $\mathbf{z}_t$ that decays at rate $\gamma\lambda$ and gates
each component's update, is Pavlov's and Hull's stimulus trace made precise.

#### The trace interval sets the credit

The quantitative content of the trace idea is that credit assigned to a conditioned
stimulus is proportional to its trace height at the moment reinforcement arrives. Model
the trace of a stimulus that ended at time $0$ as $z(\Delta) = e^{-k\Delta}$, decaying
with the interval $\Delta$ since offset. If the unconditioned stimulus arrives after a
trace interval $\Delta$, the update the stimulus receives scales with $z(\Delta)$. Two
trace intervals then predict two learning rates from one curve. With a decay constant
$k = 0.15\text{ s}^{-1}$, a stimulus reinforced $2$ s after offset is updated in
proportion to $e^{-0.3} \approx 0.74$; one reinforced $8$ s after offset is updated in
proportion to $e^{-1.2} \approx 0.30$. The near stimulus gets roughly two and a half
times the credit of the far one, and conditioning is correspondingly weaker at the
longer trace interval — the standard finding that trace conditioning degrades as the
gap grows, read straight off the trace's height.

$$
% caption: The trace interval sets the credit. One decaying trace, two reinforcement
% times. A stimulus reinforced soon after offset (near) is credited in proportion to
% the tall trace height; one reinforced after a longer trace interval (far) is credited
% in proportion to a much lower height, so it conditions more weakly.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \draw[->, black] (0,0) -- (7.6,0) node[anchor=west, black, font=\scriptsize] {trace interval};
  \draw[->, black] (0,0) -- (0,3.3) node[anchor=south, black, font=\scriptsize] {trace height};
  % decaying trace
  \draw[acc, very thick] (0,2.9)
    .. controls (1.1,1.85) and (2.2,1.25) .. (3.4,0.9)
    .. controls (4.6,0.62) and (5.8,0.42) .. (7.0,0.3);
  \node[acc, anchor=west, font=\scriptsize] at (7.0,0.42) {trace};
  % near reinforcement
  \draw[red, thick, dashed] (1.7,0) -- (1.7,1.5);
  \fill[red] (1.7,1.5) circle (1.6pt);
  \node[red, anchor=south, font=\scriptsize] at (1.7,1.55) {near};
  \draw[black, <->] (1.85,0) -- (1.85,1.48);
  \node[black, anchor=west, font=\scriptsize] at (1.95,0.75) {much credit};
  % far reinforcement
  \draw[red, thick, dashed] (5.4,0) -- (5.4,0.44);
  \fill[red] (5.4,0.44) circle (1.6pt);
  \node[red, anchor=south, font=\scriptsize] at (5.4,0.5) {far};
  \draw[black, <->] (5.25,0) -- (5.25,0.42);
  \node[black, anchor=east, font=\scriptsize] at (5.15,0.22) {little credit};
\end{tikzpicture}
$$

### Value functions as the longer gradient

Stimulus traces alone cannot span very long delays — Hull's reach zero in half a
minute. To account for goal gradients over longer periods, Hull (1943) proposed
that longer gradients result from **conditioned reinforcement passing backwards
from the goal**, acting together with his molar stimulus traces. Animal experiments
had shown that if conditions favor conditioned reinforcement during a delay — if
there are stimuli that regularly occur during the delay interval — then learning
does not decrease with increased delay as much as it does under conditions that
obstruct secondary reinforcement. It is as if the reward is not actually delayed,
because there is more immediate conditioned reinforcement. Hull envisioned a primary
gradient based on the delay of primary reinforcement, mediated by stimulus traces,
progressively modified and _lengthened_ by conditioned reinforcement.[^hull-cond]

Hull's goal gradient has a definite functional form worth writing down. If a response
leaves a trace that decays exponentially, response strength as a function of the delay
$d$ to reinforcement is $g(d) \propto e^{-k d}$, the same exponential the trace itself
follows. Reading the animal data of his day, Hull put the constant so that the gradient
was already near zero by $30$ to $40$ s of delay: with $k \approx 0.1\text{ s}^{-1}$,
strength at $30$ s is $e^{-3} \approx 0.05$, effectively gone. That short reach is the
problem. Many tasks put reward far more than half a minute past the actions that earn
it, and a raw trace simply cannot span the gap. Hull's answer was that stimuli
regularly occurring _during_ the delay pick up conditioned-reinforcement value and hand
credit backwards in stages, so the effective gradient is the primary exponential
_lengthened_ by secondary reinforcement — a shallow, far-reaching tail grafted onto the
steep near part.

$$
% caption: Hull's goal gradient. The raw stimulus trace (blue) is a steep exponential
% that reaches near zero within 30-40 s, so it credits only nearby actions. When
% stimuli during the delay acquire conditioned-reinforcement value, credit is handed
% back in stages and the effective gradient (red) gains a long shallow tail, reaching
% actions the bare trace could never touch. This is the value-function bridge.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \draw[->, black] (0,0) -- (7.8,0) node[anchor=west, black, font=\scriptsize] {delay to reward};
  \draw[->, black] (0,0) -- (0,3.3) node[anchor=south, black, font=\scriptsize] {response strength};
  % raw trace: steep exponential, dies fast
  \draw[acc, very thick] (0,2.9)
    .. controls (0.7,1.3) and (1.5,0.55) .. (2.6,0.22)
    .. controls (3.6,0.09) and (4.6,0.04) .. (6.0,0.02);
  \node[acc, anchor=west, font=\scriptsize] at (2.7,0.55) {raw trace};
  % lengthened by conditioned reinforcement
  \draw[red, very thick] (0,2.9)
    .. controls (0.9,1.9) and (1.9,1.35) .. (3.2,1.05)
    .. controls (4.6,0.75) and (6.0,0.55) .. (7.3,0.42);
  \node[red, anchor=west, font=\scriptsize] at (7.3,0.42) {+ cond. reinforcement};
  \node[acc, anchor=west, font=\scriptsize] at (6.05,0.14) {trace only};
\end{tikzpicture}
$$

A TD-learned value function does just this, and the actor–critic
architecture illustrates the correspondence most clearly. The critic uses a TD
algorithm to learn a value function for the current policy — to predict the current
policy's return — and the actor updates its policy on changes in the critic's
predictions. The TD error produced by the critic acts as a conditioned reinforcement
signal for the actor, providing an immediate evaluation of performance even when the
primary reward signal is considerably delayed. Action-value methods like
[Q-learning and Sarsa](/reinforcement-learning/tabular-methods/temporal-difference-learning)
use the same TD principle to enable learning with delayed reinforcement by means of
conditioned reinforcement.[^actor-critic-delay] Hull's "primary gradient lengthened
by secondary reinforcement" is a value function bootstrapping credit back across a
gap that a raw trace could never cover — the two mechanisms of this course, working
together, are the two mechanisms he proposed.

## From associations to maps

Blocking, higher-order conditioning, and delayed reinforcement are all mechanisms of
_association_ — cues acquiring predictive strength, predictions standing in for
reward, traces carrying credit across a gap. None of them requires the animal to hold
a _model_ of its world. The next part turns to the phenomenon that does: Tolman's
rats learned the layout of a maze with no reward at all, then used that knowledge the
moment reward appeared. That is a cognitive map — model-based reinforcement learning,
measured in a rat — and it is where this thread continues.

This continues in [Cognitive Maps and Model-Based Learning](/reinforcement-learning/minds-and-brains/cognitive-maps-and-planning).

[^psych-links]: **Sutton & Barto**, _Reinforcement Learning_, Ch. 14 — Psychology: the correspondences between reinforcement learning and animal learning connect ideas that arose from different objectives; blocking, higher-order conditioning, delayed reinforcement, and cognitive maps are each treated as animal-learning phenomena with computational counterparts in their algorithms.
[^blocking-sb]: **Sutton & Barto**, §14.2.1 — Blocking and Higher-order Conditioning: blocking occurs when an animal fails to learn a conditioned response to a potential conditioned stimulus presented in compound with another conditioned stimulus that had been used previously to condition the animal to produce that response.
[^kamin-control]: **Sutton & Barto**, §14.2.1: in the rabbit nictitating-membrane example, stage 1 conditions a tone plus air-puff US; stage 2 adds a light to form a compound followed by the same US; stage 3 tests the light alone and the rabbit produces very few or no CRs — learning to the light had been blocked. A control group conditioned to the tone/light compound with no prior tone conditioning is needed to attribute the effect to prior learning.
[^contiguity]: **Sutton & Barto**, §14.2.1: blocking challenges the idea that conditioning depends on simple temporal contiguity — that a necessary and sufficient condition for conditioning is a US frequently following a CS closely in time.
[^rw-blocking]: **Sutton & Barto**, §14.2.2 — The Rescorla–Wagner Model: when a new component is added to a compound whose animal has already been conditioned, further conditioning produces little or no increase in the added component's associative strength because the error $R_{\mathrm{Y}} - V_{\mathrm{AX}}$ has already been reduced to zero or a low value; the US is already predicted, so little surprise is introduced. The model assumes $V_{\mathrm{AX}} = V_A + V_X$ and updates $\Delta V_i = \alpha_i\beta_{\mathrm{Y}}(R_{\mathrm{Y}} - V_{\mathrm{AX}})$.
[^mechanistic]: **Sutton & Barto**, §14.2.2: the Rescorla–Wagner model was influential because it showed a mechanistic theory could account for the main facts about blocking without resorting to complex cognitive theories (e.g. explicit recognition that a component was added and backward scanning of memory); from the machine-learning view it is essentially the Least-Mean-Square / Widrow–Hoff (1960) error-correction rule.
[^lms]: **Widrow & Hoff (1960)**, "Adaptive switching circuits," _IRE WESCON Convention Record_. The least-mean-square (LMS) rule adjusts weights by the gradient of squared error, $\Delta \mathbf{w} = \alpha (R - \mathbf{w}^\top \mathbf{x})\,\mathbf{x}$. Rescorla and Wagner's conditioning update is the same rule with the associative strengths as weights; blocking follows from the collinearity of the added feature. See **Sutton & Barto**, §14.2.2, which identifies the Rescorla–Wagner model with the LMS / Widrow–Hoff rule.
[^hoc-shape]: **Sutton & Barto**, §14.2.3 / Figure 14.3: in a TD-model simulation of second-order conditioning, CSB is first conditioned to a US (reaching associative strength $\approx 1.65$ in the reported run); in the second phase CSA is paired with CSB without the US, and CSA's strength rises to a peak and then decreases as CSB — now in extinction, since the US is withheld — loses the strength that let it act as a secondary reinforcer. The rise-then-fall is the model's, and matches animal data; the specific per-trial numbers in the table here are illustrative of that trajectory.
[^finch]: **Sutton & Barto**, §14.2.1 and Bibliographic notes; Finch & Culler (1934) reported fifth-order conditioning of a withdrawal response in dogs when motivation was kept high and lower-order links were periodically refreshed. The result illustrates that the practical ceiling on the order of higher-order conditioning is set by extinction of the borrowed (conditioned) reinforcer, not by any limit on bootstrapping.
[^hoc-sb]: **Sutton & Barto**, §14.2.1 — Higher-order Conditioning: higher-order conditioning occurs when a previously-conditioned CS acts as a US in conditioning another initially neutral stimulus.
[^pavlov-square]: **Sutton & Barto**, §14.2.1: Pavlov's assistant conditioned a dog to salivate to a food-predicting metronome, then placed a black square (to which the dog was indifferent) in the dog's line of vision followed by the metronome, never followed by food; within about ten trials the dog salivated to the black square, second-order conditioning, with the metronome acting as a US.
[^hoc-hard]: **Sutton & Barto**, §14.2.1: higher-order conditioning is difficult to demonstrate above the second order because a higher-order reinforcer loses its reinforcing value if not repeatedly re-paired with the original US; under conditions such as intermixing first-order with higher-order trials or providing a general energizing stimulus, higher-order conditioning beyond the second order can be demonstrated.
[^cond-reinf]: **Sutton & Barto**, §14.2.1: a stimulus that consistently predicts primary reinforcement (innately rewarding/penalizing by evolution) becomes a reinforcer itself — a secondary, higher-order, or conditioned reinforcer — and delivers conditioned reinforcement, acting like primary reinforcement in increasing behavior leading to conditioned reward and decreasing behavior leading to conditioned penalty.
[^money]: **Sutton & Barto**, §14.2.1: conditioned reinforcement explains, for instance, why we work for the conditioned reinforcer money, whose worth derives solely from what is predicted by having it.
[^actor-critic]: **Sutton & Barto**, §14.2.1: in actor–critic methods the critic uses a TD method to evaluate the actor's policy, and its value estimates provide conditioned reinforcement to the actor, allowing the actor to improve its policy — the analog of higher-order instrumental conditioning that helps address the credit-assignment problem when the primary reward signal is delayed.
[^delayed-sb]: **Sutton & Barto**, §14.4 — Delayed Reinforcement: the Law of Effect requires a backward effect on connections; learning occurs even with a considerable delay between action and consequent reward, and in classical conditioning when US onset follows CS offset by a non-negligible interval. This is the problem of delayed reinforcement, related to Minsky's (1961) credit-assignment problem: how to distribute credit for success among the many decisions involved in producing it.
[^two-mech]: **Sutton & Barto**, §14.4: their algorithms address delayed reinforcement with two mechanisms — eligibility traces, and TD methods that learn value functions providing nearly immediate evaluations of actions (instrumental tasks) or immediate prediction targets (classical tasks); both correspond to mechanisms proposed in theories of animal learning.
[^pavlov-trace]: **Sutton & Barto**, §14.4: Pavlov (1927) pointed out that every stimulus must leave a trace in the nervous system persisting after the stimulus ends, and proposed stimulus traces make learning possible across a temporal gap between CS offset and US onset — the basis of trace conditioning, where a trace of the CS remains when the US arrives.
[^hull-trace]: **Sutton & Barto**, §14.4: Hull's learning theory used "molar stimulus traces" to account for the goal gradient — how the maximum strength of an instrumentally-conditioned response decreases with increasing delay of reinforcement (Hull 1932, 1943); traces decay exponentially with time since the action and, per the data of the time, effectively reach zero after 30 to 40 seconds.
[^klopf]: **Sutton & Barto**, §14.4: the eligibility traces they use are like Hull's — decaying traces of past state visitations or state–action pairs; eligibility traces were introduced by Klopf (1972) in a neuronal theory as temporally-extended traces of past activity at synapses, more complex than the exponentially-decaying traces those algorithms use.
[^hull-cond]: **Sutton & Barto**, §14.4: to account for goal gradients over longer periods than stimulus traces span, Hull (1943) proposed longer gradients result from conditioned reinforcement passing backwards from the goal, together with molar stimulus traces; experiments showed learning decreases less with delay when stimuli regularly occur during the delay interval (favoring secondary reinforcement), so Hull envisioned a primary gradient based on delay of primary reinforcement, progressively modified and lengthened by conditioned reinforcement.
[^actor-critic-delay]: **Sutton & Barto**, §14.4: algorithms using both eligibility traces and value functions correspond to Hull's hypothesis; the actor–critic architecture illustrates this most clearly, the critic learning a TD value function for the current policy and its TD error acting as a conditioned reinforcement signal for the actor even when primary reward is delayed; action-value methods such as Q-learning and Sarsa use TD principles similarly.