RL 7: How Machines Learned to Guess Better — Sutton, Barto & Temporal Difference Learning

Part 7 of the RL series. In Blog 6, Werbos gave us backpropagation and Klopf gave us the idea of a "hedonistic" neuron that chases reward. Both were brilliant sparks. But sparks aren't a system. Nobody had yet built a clean method for learning from predictions as time unfolds. That is the job Richard Sutton and Andrew Barto took on between 1981 and 1984.

Where We Are, and Where We're Going

Blog 6 left us with a gap. We had a way to adjust weights (backprop) and a motive for the learner (chase reward). What we were missing was an answer to a very practical question:

When the reward shows up late, who gets the credit?

By the end of this post you'll be able to:

1. Explain the temporal credit assignment problem in plain English.
2. Read the three core formulas of RL (Return, Value, TD error) without flinching.
3. Walk through TD learning by hand on a tiny 3-step example.
4. Explain why the Actor-Critic split exists, and where you've already met its descendants.
5. Know what Sutton's 1984 dissertation did, and what it did not yet do (this part is a common misconception).

The Problem That Wouldn't Go Away: Temporal Credit Assignment

Picture a chess game. You make 40 moves, then lose. Which move lost it?

Maybe it was move 40, the blunder you can see. Or maybe move 12, a quiet pawn push that looked harmless and slowly strangled your position. No one stamped "mistake" on it. And the only feedback you got, "you lost", arrived 28 moves later.

That is the Temporal Credit Assignment Problem: when a reward arrives late, how do you decide which earlier decisions deserve the credit (or the blame)?

The problem is older than Sutton. Samuel's checkers program (1959) already wrestled with it, and Marvin Minsky gave it its name in his 1961 paper "Steps Toward Artificial Intelligence." But in the early 1980s it was still a pile of clever hacks. Sutton and Barto's contribution was to turn it into a clean, mathematical story.

To attack this we need three tools. Think of them as three questions:

Let's take them one by one.

Tool 1: The Return (What Does "Good" Mean Over Time?)

A single reward only tells you about one moment. But life, and games, are about the whole stream of rewards ahead of you. So we add them up, giving less weight to the ones further away:

This total is called the Return. The symbol γ (gamma, the discount factor) is a number between 0 and 1 that sets how patient the agent is.

A tiny example. Say you'll get rewards of 0, 0, then 10 over the next three steps, and γ = 0.9:

G = 0 + (0.9 × 0) + (0.9² × 10) = 0 + 0 + 8.1 = 8.1

The 10 is worth only 8.1 to you today because it's two steps away. Same prize, further away, smaller feeling.

• γ close to 1 → patient, plans far ahead.
• γ close to 0 → short-sighted, grabs what's in front of it.
• It also keeps the math safe: for never-ending tasks, an undiscounted sum of rewards can grow without bound. Discounting keeps it finite.

So the Return is what actually happened to you from this moment on. But when you're standing in a state, you haven't lived the future yet. You have to guess it. That guess has a name.

Tool 2: The Value Function (An Honest Guess About the Future)

Read it out loud: "The value of state s, under policy π, is the **average Return* I expect if I start in s and keep following π."*

Return = the score you actually got on this run.
Value = the score you'd expect on average from here.

Two chess positions can both pay zero reward right now, yet one is a winning attack and the other a slow trap. Their values differ even though their immediate rewards don't. That's the whole point of the value function: it lets you judge a situation before the payoff arrives.

This gives us the cleanest way to see what Sutton and Barto were after:

• Reactive learning: "I just got +10, so my last action was good."
• Predictive learning: "I'm in a state that usually leads to +10, so this state is already good, right now."

And remember the Bellman idea from Blog 3: a state's value can be written using the next state's value. That small fact is about to become a learning machine.

1981: When Pavlov Met the Computer

In 1981 Sutton and Barto published "Toward a Modern Theory of Adaptive Networks: Expectation and Prediction." It was unusual for an AI paper: it started with Pavlov's dogs.

You know the experiment. Bell, then food. Repeat. Eventually the dog drools at the bell alone.

Psychologists called it association. Sutton and Barto asked a sharper question: what is the dog actually computing? Their answer was that the dog is learning to predict food from the bell. The bell becomes valuable because of what it forecasts.

Two things followed from that framing:

• When the prediction is right, there's nothing to learn.
• When it's wrong, the surprise is what drives the update.

Surprise as the learning signal. Hold on to that phrase, because it is the entire next section.

(A fair footnote: the 1981 model was a precursor to TD learning, not TD itself, and similar ideas had been floating around, for example in Ian Witten's 1977 work. The clean, general version came a few years later.)

Tool 3: Temporal Difference Learning (Fix Your Guess With a Better Guess)

The old way: wait until the end

The classic approach is Monte Carlo: play the whole episode, see the final outcome, then go back and update every state you visited. If the game lasts 100 moves, you learn nothing until move 100. And if the task never ends? You never learn at all.

Sutton's idea: don't wait, update your guess using your next guess

You're driving home. When you leave the office, you estimate 30 minutes. Five minutes in, you hit a traffic jam and revise to 60. You didn't have to reach home to realize your first guess was off. The gap between your two guesses is the learning signal.

That gap is the TD error (TD = Temporal Difference, the difference between estimates at two moments in time):

And the update that uses it, called TD(0):

In plain words:

Notice the trick. The target contains V(S_{t+1}), which is itself just a guess. We're improving a guess using another guess. This is called bootstrapping (pulling yourself up by your own bootstraps), and it feels suspicious until you see it work.

Let's actually do it: a 3-step world

Here's the smallest example I could build. A little robot walks A → B → C → Goal. It gets +1 only when it reaches the Goal, and 0 otherwise. Set γ = 1 and α = 0.5. All guesses start at 0.

Episode 1. The robot walks A→B→C→Goal.

• A→B: δ = 0 + V(B) − V(A) = 0 − 0 = 0 → V(A) stays 0
• B→C: δ = 0 + V(C) − V(B) = 0 → V(B) stays 0
• C→Goal: δ = 1 + 0 − V(C) = 1 → V(C) = 0 + 0.5 × 1 = 0.5

Only C learned anything: it's the only state next to the reward.

Episode 2.

• A→B: δ = 0 + 0 − 0 = 0 → V(A) = 0
• B→C: δ = 0 + 0.5 − 0 = 0.5 → V(B) = 0.25
• C→Goal: δ = 1 − 0.5 = 0.5 → V(C) = 0.75

Episode 3.

• A→B: δ = 0.25 − 0 = 0.25 → V(A) = 0.125
• B→C: δ = 0.75 − 0.25 = 0.5 → V(B) = 0.5
• C→Goal: δ = 1 − 0.75 = 0.25 → V(C) = 0.875

Watch what happened. The news of the reward travels backward, one state per step, like a rumor passing down a line. Nobody had to wait for a final verdict and replay history. Each state corrected itself using its neighbor's opinion. That is temporal credit assignment, solved with arithmetic you did on a napkin.

(Run it forever and all three values head toward 1.0, the true value.)

So is TD just "better" than Monte Carlo?

Not exactly. They trade off differently:

TD often learns faster in practice precisely because it's low-variance and online, but the real win is that it can learn while living. Sutton would later show (Blog 8) how to dial smoothly between the two with λ.

And here's why this matters beyond the toy: that δ signal is the ancestor of the learning signal in Q-learning, DQN, and the critics inside modern algorithms. The machinery around it keeps changing; the "surprise" at the center doesn't.

1983: Actor-Critic (Splitting the Brain in Two)

Now we have prediction. But prediction alone doesn't act. The agent still has to decide what to do next.

The naive route is to look at every possible next state and pick the one with the highest V. But that requires knowing how the world responds to each action, the environment's transition probabilities, which in real problems you usually don't have.

Barto, Sutton, and Anderson (1983) in "Neuronlike Adaptive Elements That Can Solve Difficult Learning Control Problems" took a different route. Make two learners and let them specialize:

• The Actor holds the policy. It picks actions. It doesn't judge them.
• The Critic holds the value function. It watches and computes the TD error δ, the surprise.

Think of an athlete and a coach:

Actor (athlete): "I'll try jumping."
Critic (coach): "That went 0.3 better than I expected. Do more of that."
or
Critic: "That went 0.8 worse than I expected. Don't."

The coach's feedback is the TD error we just learned. Same signal, new job: it now steers the Actor.

In today's notation, the Actor's update looks like this:

Read it as: "Nudge the actor's settings so the action it just took becomes more likely if δ is positive, and less likely if δ is negative." (A note for the careful: this log-probability form is how we write it today. The 1983 paper used a simpler, more hand-built version of the same idea, and the clean policy-gradient math arrived later in the 1990s. The spirit, a TD error steering the actor, is exactly 1983.)

Why split them at all?

If one system both acts and evaluates, then raw luck sneaks straight into behavior. One lucky win and the agent thinks "that move is genius!" and stops exploring. Good luck and skill look identical.

The Critic fixes this by averaging over time, so the Actor responds to a smoothed, expectation-based signal rather than single noisy outcomes. Result: more stable learning.

The pole-balancing demo

The team tested it on the classic cart-pole task: push a cart left or right to keep a pole balanced upright. No physics equations given, no pre-programmed strategy, only failure signals and the Actor-Critic loop. It learned to balance.

Two honest caveats that make the story more interesting rather than less: this was a simulation, and the system divided the pole's state into coarse "boxes," a trick borrowed from Michie and Chambers' earlier BOXES work (1968). So it wasn't the first learner to balance a pole. What was new was the architecture: an adaptive critic generating a better teaching signal for an adaptive actor, learning from a rare, delayed failure signal.

Where you've already met its descendants

• PPO (Blog 12) is an actor-critic method, and it was the RL step used to fine-tune models like InstructGPT and ChatGPT.
• In RLHF, careful with the mapping: the LLM is the Actor, a separate reward model scores outputs, and PPO also trains its own value network (that's the Critic). The reward model is not the critic.
• GRPO (Blog 16) removes the learned Critic and uses group-relative scores instead. A good reminder that the idea (get a baseline to compare against) survives even when the component disappears.

1984: The Dissertation (and a Myth Worth Clearing Up)

Sutton's 1984 PhD thesis, "Temporal Credit Assignment in Reinforcement Learning," is a landmark. It's where the ideas above were pulled together and studied systematically: prediction learning, the adaptive critic, and the credit assignment problem treated as the central issue.

Here's the myth to clear up. You'll often read that this thesis proved TD learning converges. That's not quite right, and the true timeline is more interesting:

So the accurate sentence is: 1984 gave RL its central framework, and the rigorous proofs matured over the following decade. Still a huge deal, and honestly a better story: science rarely arrives in one tidy "proof moment."

The Bellman chase

The math TD chases is the Bellman idea from Blog 3. In its honest form (with an average over what could happen next):

TD never solves this equation outright. It chases it: each step nudges V(S_t) toward one sampled version of the right-hand side. Averaged over many samples, with a suitably shrinking learning rate, the chase lands on the true values. That's the convergence story in a sentence.

Backprop vs TD

A cleaner way to think about it: they're not rivals, they do different jobs.

• Backprop answers: "Given a target, how do I adjust my weights to hit it?"
• TD answers: "Where does the target come from when no one gives me labels?"

In supervised learning, a human supplies the target ("this image is a cat"). In RL, nobody does, so TD builds one from reward plus your next estimate. The target keeps moving as your guesses improve, which is what makes this subtle. Later systems combined the two: a neural network (trained by backprop) learns the values, and TD supplies the targets.

This is also why you can't just train a great game-playing agent by imitating a database of human games. The true value of a position depends on what play follows, and that only gets discovered through experience.

TD(λ): the preview

The thesis also planted seeds of TD(λ), a knob (λ) that slides between TD(0) (look one step ahead) and Monte Carlo (look to the end of the episode). The full treatment is in Blog 8.

What 1981–1984 Actually Built

Sutton and Barto didn't invent every piece. Thorndike gave us reward-shaped behavior (1898), Bellman gave us value functions (1957), and Werbos gave us backprop (1974). What they did was assemble those pieces into a coherent, learnable system for improving predictions as time unfolds.

Cheat Sheet (screenshot this)

• Return = total (discounted) reward you actually get from here on.
• Value = the Return you expect on average from a state.
• TD error δ = (reward + discounted next-state value) − (current-state value) = the surprise.
• Bootstrapping = updating a guess using another guess.
• Actor picks actions; Critic judges them with δ.
• Credit assignment = deciding which past decisions caused a delayed result.

Next Up

We now have prediction (TD) and a stable acting loop (Actor-Critic). But everything so far still leans on one convenient assumption: that we know something about how the world behaves.

What if we know nothing? No transition probabilities, no model, just raw experience?

In Blog 8, we first meet Sutton's 1988 TD(λ) paper, the formal bridge between TD and Monte Carlo, and then Chris Watkins' Q-Learning (1989), the first algorithm proven to converge to the optimal policy with no model of the environment at all.

See you there.