DEV Community: Mitansh Gor

RL 9: Superhuman Achievement in Games (1992–1999)

Mitansh Gor — Mon, 02 Nov 2026 08:21:34 +0000

For about 30 years, strong backgammon players opened certain rolls the same way. It was in the books. Then a program that had never read a backgammon book said they were all wrong, and it turned out to be right.

In Blog 8 the Q-table hit a wall: one cell per situation, and real problems have more situations than atoms in the universe. The obvious fix was a neural network that guesses values for situations it has never seen. But theory said that mixing a neural network with TD updates might blow up. One researcher at IBM tried it anyway, on a board game with dice. This post covers what happened, how the math works, and why the trick was partly luck.

Where We Are, and Where We're Going

By the end of this post you'll be able to explain, in plain words:

Why backgammon (a game with dice) was a harder test for learning than chess.
How a neural network replaces the Q-table, with a step-by-step example using real numbers.
Where the weight-update formula comes from, and what an eligibility trace does to it.
What self-play is, and why "your opponent levels up with you" is such a powerful trick.
Why TD-Gammon stunned human experts, and why the same recipe didn't instantly work everywhere else.

Words from earlier blogs I won't re-explain: value function V(s) and TD error δ (Blog 7), eligibility traces, a.k.a. "breadcrumbs" (Blog 8), ε-greedy exploration and "model" (Blog 8). If any feel fuzzy, a quick skim of those posts will set you up.

New words in this post:

Word	Plain meaning
Neural network	A stack of layers. Each layer takes numbers in, mixes them using adjustable dials, and passes numbers out. Numbers in one end, a guess out the other.
Weights	Those adjustable dials inside the network. Learning = turning the dials.
Gradient	For every dial: "if I turn you up a tiny bit, how much does the network's guess change?"
Function approximator	Any formula with tunable dials that guesses a value, instead of storing it in a table. A neural network is one.
Self-play	The agent plays against a copy of itself.
Ply	One player's turn (a "half-move").
Rollout	Play a position out to the end thousands of times with random dice, and count who wins. (It's Monte Carlo from Blog 7, in action.)

1. Why Backgammon?

Gerald Tesauro, a researcher at IBM, picked backgammon on purpose. Not because it was easy, but because it was awkward in exactly the ways that break the usual tricks.

Chess is deterministic. No dice. A program can look many moves ahead because the number of options per turn stays manageable: roughly 30–40 legal moves in chess, 8–10 in checkers. In backgammon every turn starts with a dice roll. There are 21 distinct rolls, each allowing around 20 legal moves, so several hundred branches per ply. Look-ahead search drowns almost immediately.

You only need three ideas to follow this post: it's a race around the board, you can hit a lone enemy checker and send it back to the start, and you can block with stacked checkers. Dice make every plan fragile, so even a position's value is a probability, not a verdict.

The old way: copy the experts

Tesauro had already tried the standard approach. His earlier program, Neurogammon, was trained by supervised learning (the "show it labeled examples" method) on recorded games by expert humans. It won the 1989 Computer Olympiad. But it had a ceiling, and the ceiling was the humans it copied. And experts aren't infallible: in backgammon and Othello, expert opinion had been substantially revised over the previous twenty years.

So he built a head-to-head experiment. Same designer, same kind of network, two teachers:

Teacher A: expert-labeled examples (Neurogammon).
Teacher B: nobody. The network plays itself and learns from who wins (TD-Gammon).

It was a gamble. Samuel tried self-play with checkers in the 1950s (Blog 4), and self-playing learners had a reputation for developing weird, brittle strategies that beat themselves but lose to everyone else.

2. The Recipe: How a Network Replaces the Table

Blog 8 ended with the table's fatal flaw. Backgammon has more than 10^20 positions, so a table with one cell per position is impossible. Tesauro's replacement was a plain multilayer perceptron: numbers go in one end, one guess comes out the other.

What goes in, what comes out

Input: 198 numbers describing the board. Roughly: for every point (one of the 24 narrow slots checkers sit on), a few numbers saying how many checkers each player has there, plus a handful for checkers on the bar, checkers borne off, and whose turn it is. (The very first version used only this raw board. No strategy hints.)
Hidden layer: 40 units in the first version, 80 in later ones.
Output: the network's estimate of who's winning. Textbooks simplify this to one number, the probability of winning. Tesauro's actual network had four outputs, covering normal wins and "gammons" (landslide wins worth double) for each side.

That output is V(s, w): the value of board s, computed by a network whose dials (weights) are w.

Count the dials: 198 × 40 + 40 × 4 is roughly 8,000 weights. Eight thousand numbers standing in for 10^20 positions. That compression only works because the network generalizes: what it learns about one position carries over to thousands of near-twins. A table can't do that.

How it picks a move

Because the rules of backgammon are known, the agent doesn't need a Q-table. (Remember the "model" from Blog 8? In a board game with clean rules, you can write the map by hand.) On each turn it:

Rolls the dice.
Lists every legal move and the board each one would create.
Feeds each resulting board into the network.
Plays the move whose board has the best estimated outcome. Greedy. No ε-greedy, no random exploration.

No exploration at all? That should worry you after Blog 8. Section 3 explains why it works anyway: the dice do that job for free.

How it learns, part 1: one game, with numbers

Here's a toy game. The network scores four positions in a row, then the game ends in a win. Inside one game there's no reward until the end and we use γ = 1, so the TD error δ from Blog 7 boils down to next estimate minus this estimate.

Position	Network's win estimate	What happens next	TD error `δ` (next minus this)
1	0.50	next position is rated 0.55	+0.05
2	0.55	next position is rated 0.45	−0.10
3	0.45	next position is rated 0.70	+0.25
4	0.70	game ends: win (= 1.0)	+0.30

Read the last row first. The network said "70% for me", and the game ended in a win. It was underconfident, so the surprise is positive. Notice that the only real information from the outside world is that final win. Everything else is the network comparing its own consecutive guesses (the "fix your guess with a better guess" idea from Blog 7).

How it learns, part 2: where the update rule comes from

The surprise tells us how wrong a guess was. How do we turn that into "turn these dials this way"? It's ordinary gradient descent (the same idea as Blog 6), with one twist.

First, what's a gradient? Take a tiny network, V = 0.2·x₁ + 0.5·x₂, and a board described by x = [2, 1]. Then V = 0.4 + 0.5 = 0.9. Nudge the first dial from 0.2 to 0.21 and V becomes 0.92: it moved by 0.01 × x₁ = 0.02. So the sensitivity of V to dial 1 is x₁ = 2, and to dial 2 it's x₂ = 1. The list of sensitivities [2, 1] is the gradient, written ∇_w V. A real network has about 8,000 dials, and backprop (Blog 6) computes that whole list efficiently.

Now the rule. We want the guess at position t to move toward the next guess, which is our "better guess". Measure the miss with a squared error, treating the target as a fixed number:

L (w) = \frac{1}{2} (y_{t} - V (s_{t}, w))^{2}, y_{t} = V (s_{t + 1}, w) held fixed

Its slope with respect to the dials is −(y_t − V_t) · ∇_w V_t. Stepping downhill (with step size α) gives:

w \leftarrow w + α δ_{t} \nabla_{w} V (s_{t}, w), δ_{t} = V (s_{t + 1}, w) - V (s_{t}, w)

Read it in words: turn each dial in proportion to (how surprised I was) × (how much that dial mattered). That's TD(0) with a neural network.

For the mathematically curious. We froze the target y_t while taking the slope, even though y_t itself depends on w. Because of that, this update is not the true gradient of any single fixed loss. Sutton and Barto call it a semi-gradient method. It's the reason the theory is harder than ordinary supervised learning, and it's the thread we pull in Section 5.

How it learns, part 3: adding the trace (and when things happen)

TD(0) only fixes the position that just happened. But a surprise at move 4 is partly the fault of moves 1 to 3. The eligibility trace (Blog 8's breadcrumbs) handles that. In a table the breadcrumbs sat on cells. A network has no cells, so they sit on the weights.

The update happens after every move, not after the game. Each trip around the loop touches two piles of numbers:

The weights w: the network's actual brain (about 8,000 numbers).
The trace e: a scratchpad the same length as w. A fading memory of "which dials were involved in my recent guesses". It starts at all zeros at the start of every game, and it never changes the network by itself. Only a surprise δ does that.

For each move t:

Forward pass. Rate the current board: V_t.
Gradient. Backprop gives g_t, the list of "how much did each dial matter".
Update the scratchpad. Fade the old memory, add the fresh footprint.
The move happens and the next board arrives. Rate it (or use the real result if the game just ended) and compute the surprise δ_t.
Turn the dials, each in proportion to its breadcrumb.

As formulas, one per step:

g t = \nabla w V (s_{t}, w)

e t = γλ e t - 1 + g_{t}, e_{0} = 0

δ_{t} = V (s_{t + 1}, w) - V (s_{t}, w), δ_{T} = z - V (s_{T}, w)

w \leftarrow w + α δ_{t} e_{t}

Symbol	Meaning
`w`	All the dials (about 8,000 numbers)
`g_t`	The gradient: how much each dial influenced the guess at move `t`
`e_t`	The trace: a fading sum of recent gradients, same length as `w`
`γ`	Discount. We use `γ = 1` inside a game, so it drops out
`λ`	How slowly the memory fades. `λ = 0`: no memory (plain TD(0)). `λ` near 1: long memory
`δ_t`	The surprise at move `t` (`z`, the real result, replaces the next guess on the last move)
`α`	Learning rate: how big a step to take

Notice that with λ = 0 the trace is just g_t, and the update collapses to the TD(0) rule we derived above. The trace is TD(0) plus memory.

Also notice the timing: δ_t needs the next board's rating, so move t's update lands the moment move t+1's board appears. That's why the update sits between positions, not at the end.

How it learns, part 4: run it on the toy game

To keep the vectors small, pretend the network has just 3 dials (w_a, w_b, w_c) instead of 8,000. The gradients are made up (move 1 touches dial a, move 2 touches b, moves 3 and 4 touch c), but the arithmetic is exactly the real algorithm. Settings: λ = 0.5 (old memory halves each step), α = 0.1.

Move `t`	Gradient `g_t`	Trace `e_t = 0.5·e_(t-1) + g_t`	Surprise `δ_t`	Dial change `α · δ_t · e_t`
1	`[1, 0, 0]`	`[1, 0, 0]`	+0.05	`[+0.005, 0, 0]`
2	`[0, 1, 0]`	`[0.5, 1, 0]`	−0.10	`[−0.005, −0.010, 0]`
3	`[0, 0, 1]`	`[0.25, 0.5, 1]`	+0.25	`[+0.006, +0.013, +0.025]`
4	`[0, 0, 1]`	`[0.125, 0.25, 1.5]`	+0.30 (game won)	`[+0.004, +0.008, +0.045]`
Total				`[+0.01, +0.01, +0.07]`

(Rounded to three decimals; the totals use exact values.)

Two things to read off it:

The trace column is the breadcrumb trail. After move 4, dial c (used by the late positions) carries big breadcrumbs (1.5), while dial a (used only in position 1) carries a faint one (0.125).
The last column is where it pays off. Dial a was only involved in position 1, yet the late good news still reached it. That's credit assignment traveling backward through time.

What the trace actually changed. Compare with λ = 0 (plain TD(0)), where each move only touches its own gradient:

Total change	`w_a`	`w_b`	`w_c`
TD(0), no trace	+0.005	−0.010	+0.055
TD(λ), with trace	+0.010	+0.010	+0.070

Look at dial b. Without a trace, position 2's dial gets punished, because its own next-step surprise was negative (−0.10). With a trace, it also hears the later news: the game was won, and position 2 was on the path to that win. The final verdict flips the sign.

The food-critic version: you eat ten courses and get a stomachache. TD(0) blames only the last dish. TD(λ) spreads the blame backward, most to the last course, less to each earlier one.

Online vs offline. You could save up all four rows of the last column and apply them together after the game (offline TD(λ)). You'd still add up every row, not just the last one. TD-Gammon updated after each move (online), so later guesses in the same game already benefit from earlier lessons.

For the mathematically curious. There's a second way to read λ. Instead of breadcrumbs looking backward, imagine each position looking forward: it forms the target "look n steps ahead, then trust my own estimate" for every n, and averages them with weights that decay by λ:
G_t^λ = (1 − λ) · Σ_{n≥1} λ^(n−1) · G_t^(n).
At λ = 0 that's the one-step TD(0) target. At λ = 1 it's the full Monte Carlo return from Blog 7. So λ is a smooth dial between "bootstrap from the next guess" and "wait for the real outcome". The trace is the backward view that achieves the same averaging online, without having to store the future. The two views give the same total update (exactly in the offline case, closely in the online case).

Two roles, to keep straight: TD decides what the target should be when nobody gives you labels (Blog 7). Backprop decides how to turn the dials to move toward that target (Blog 6). TD-Gammon is those two ideas bolted together.

3. Self-Play and the "Infinite Curriculum"

Tesauro started the network with random weights, which means random play. Both sides played randomly, against each other, and the only feedback was who won.

Early games were absurd. Random backgammon can run for hundreds or even thousands of moves, compared to about 50–60 plies in a normal human game. And yet the network learned. In the first few thousand games it picked up the basics: hit the opponent, avoid leaving lone checkers exposed, build solid structures. Subtler ideas showed up after tens of thousands of games.

Why the opponent never gets too easy or too hard

Because the agent plays itself, its opponent is always exactly as strong as it is. The moment it discovers a slightly better strategy, its opponent (itself) uses that strategy too. Difficulty rises automatically with ability. Researchers later called this an infinite curriculum: a training setup that adjusts its own difficulty, with no human designing lesson plans.

It's the same loop AlphaGo Zero used in 2017, playing millions of games against itself (4.9 million, per the paper) starting from random moves.

The dice are secretly doing the exploring

Remember ε-greedy from Blog 8? The deal was: you need random moves or you'll never discover better options. TD-Gammon had none, and it worked anyway. Tesauro's explanation: the dice already randomize which positions the agent visits. Every game wanders through different territory whether the player wants to or not. A deterministic game like chess would need some other source of randomness, or self-play can get stuck replaying one narrow style forever.

5. Plot Twist: Why Didn't It Copy-Paste to Chess and Go?

If a neural network trained by TD and self-play could master backgammon, surely chess and Go were next? They weren't. A major 1996 survey of RL noted that no success close to TD-Gammon's had been repeated.

Three explanations emerged, and the third one is where the math comes back.

Explanation 1: Backgammon was a uniquely friendly game. Tesauro himself listed reasons (we met the first one already):

The dice provide exploration for free. (Remember the worry from Section 1 that self-play learners get brittle? In a deterministic game, a self-player can settle into one narrow style that looks great against itself and falls apart against anyone else. Random dice keep knocking it into new positions.)
Games always end, even with random play. (A deterministic game can loop forever, and then the network never sees a final result to learn from.)
The true value of a position is smooth: a small change to the board nudges the win probability slightly, instead of flipping between "win" and "lose".

Explanation 2: Maybe TD wasn't even the star. In 1996–98, Jordan Pollack and Alan Blair ran a provocative follow-up titled "Why did TD-Gammon work?" They trained a small network (about 4,000 parameters) with plain hill-climbing evolution: no backprop, no reinforcement learning, no TD. It still reached a competitive backgammon level. Their hypothesis: much of the success came from the setup (co-evolving players against each other) and the dynamics of backgammon itself. TD-Gammon still got further, so this didn't erase Tesauro's achievement. But it was a warning that "RL + neural net" wasn't a magic recipe yet.

Explanation 3: The math says it shouldn't have been safe. Remember the semi-gradient twist from Section 2: we froze the target while taking the slope. That's fine for tables. With a function approximator, three ingredients can combine badly. Sutton and Barto later named the combination the deadly triad:

Ingredient	Where we met it
Function approximation (a network instead of a table)	This blog
Bootstrapping (using your own next guess as part of the target)	TD, Blog 7
Off-policy learning (learning about a different policy than the one acting)	Q-learning, Blog 8

With all three present, value estimates can diverge: instead of settling toward the right answer, they grow without bound.

TD-Gammon had two of the three. It learned about its own play, so it was on-policy. That's one plausible reason it got away with it, though nobody has proven that's the whole story. It sat on a lucky island, and the surrounding waters were rough.

6. What TD-Gammon Left Behind

For backgammon. By 1995, rollouts by TD-Gammon were regarded as the most reliable way to analyze checker plays, and opening theory had been rewritten.

For RL. It was the first large-scale success of RL with a nonlinear function approximator, and the blueprint for what came next. The stability problem it dodged is exactly the plot of DQN (Blog 11): DeepMind's real contribution was making this combination stable, not inventing it. And its self-play loop was an early example of the recipe later used in AlphaGo Zero.

An open question. Why did it work? Dice, smoothness, on-policy luck, or the setup? Researchers were still arguing about it years later, which is what makes it such a good puzzle.

Cheat Sheet

TD-Gammon = a neural network V(s, w) trained by TD(λ) through self-play; the first big proof that function approximation + RL can work at scale.
Update rule = turn each dial by α × (surprise) × (breadcrumb). With λ = 0 it's TD(0); the trace adds memory.
Semi-gradient = we freeze the target while taking the slope, so it isn't a true gradient of a fixed loss.
Self-play = you are your own sparring partner, so difficulty rises with your skill (an infinite curriculum).
Why it worked on backgammon: dice (free exploration), games always end, smooth values, and on-policy learning. Maybe the setup mattered too.
Deadly triad = function approximation + bootstrapping + off-policy. TD-Gammon had two of three.
Honest caveat: later versions added hand-made features and a short search, and the result didn't transfer to chess or Go.

What's Coming Next

TD-Gammon worked, but the theory says value-based methods with function approximation can fail to converge. So what if we skip the value function and improve the policy directly?

That's Blog 10.

Sources and Further Reading

G. Tesauro, "Temporal Difference Learning and TD-Gammon", Communications of the ACM, 1995 (the primary source for the architecture, scores, and the opening-play story).
G. Tesauro, "Practical Issues in Temporal Difference Learning", Machine Learning, 1992.
J. Pollack, A. Blair, "Why did TD-Gammon Work?", NIPS 1996.
Sutton and Barto, Reinforcement Learning: An Introduction (TD-Gammon case study; semi-gradient methods; the deadly triad).
J. Tsitsiklis, B. Van Roy, "An Analysis of Temporal-Difference Learning with Function Approximation", 1997.
R. Sutton, D. McAllester, S. Singh, Y. Mansour, "Policy Gradient Methods for Reinforcement Learning with Function Approximation", NIPS 1999.

RL 8: Q-Learning, Model-Free Breakthroughs, and the Off-Policy Meta (1988–1994)

Mitansh Gor — Thu, 22 Oct 2026 20:41:29 +0000

In Blog 7 we watched Sutton teach machines to predict: chase a moving target of better and better value estimates, and the estimates settle down on the truth. That was a big deal. But there was a catch.

Prediction without action is a weather forecast you can't do anything about.

Knowing "this situation is worth 8 points" is nice. Knowing "so I should turn left" is what actually wins games. This post is about the five years (1988–1994) when RL went from predicting to deciding, and did it without ever being handed a map of the world.

By the end of this post you'll be able to explain, in plain words:

why "knowing how good a state is" isn't enough to act
what Q-Learning does and why it was a breakthrough
what on-policy and off-policy mean (the most important vocabulary split in RL)
why the fastest route along a cliff edge can be the wrong thing to learn

Quick refresher (and four new words)

Blog 7 already covered state, action, reward, policy, return, value, the discount γ, bootstrapping and the TD error δ, so I won't re-explain them here. If any feel fuzzy, a quick skim of Blog 7 will set you up. Four words show up in this post that are new:

Word	Plain meaning
Model	A map of the world: "if I do X here, I end up there"
Model-free	Learning what to do without that map
Q-value	The score of a specific action in a specific state (not just the state)
On-policy / off-policy	Whether you learn about the way you actually behave, or about some ideal way of behaving (the big idea of this post)

The gap: knowing the score vs knowing the move

Blog 7's value function V(s) answers "how good is it to be here?" That's the exact gap: it scores places, not moves.

Now suppose you're standing at a crossroads and you know:

the road left leads to a town worth 7
the road right leads to a town worth 9

Easy, go right. But notice what you needed: you had to know where each road leads. That's the model, the map: P(s' | s, a), the probability of landing in s' after doing a in s.

In a board game with clean rules, you can write that map by hand. In a robot's kitchen, a stock market, or a video game you've never seen? Nobody hands you the map. And building one is often harder than the original problem.

The fix, in one sentence: stop scoring places and start scoring choices.

If you know "taking road right from this junction is worth 9," you don't need to know where it goes. You just pick the best-scoring choice. Algorithms that work this way, without a map of the world, are called model-free.

Three ideas, arriving between 1988 and 1994, made that practical. We'll take them in order.

Idea 1: TD(λ), a dial between "impatient" and "patient" (Sutton, 1988)

Technically this one is still about prediction, so why is it here? Because it upgrades the credit-assignment machinery from Blog 7, and Watkins is about to reuse that machinery for choosing actions.

Blog 7 left you with two separate tools: TD(0) (update from the very next state) and Monte Carlo (wait for the whole episode, then update). Sutton's 1988 paper, Learning to Predict by the Methods of Temporal Differences, showed they're not two tools at all. They're the two ends of one dial.

The dial is λ (lambda), a number from 0 to 1. At λ = 0 you get TD(0). At λ = 1 you get (roughly) Monte Carlo. Everything in between is a blend.

How the dial works: eligibility traces. Think of breadcrumbs. Every state you visit gets a breadcrumb, and the crumbs fade as time passes:

e_{t} (s) = γλ e_{t - 1} (s) + 1 [S_{t} = s]

In words: "a state's crumb fades by a factor of γλ each step, and gets topped up whenever you visit it."

When a surprise arrives (the TD error δ from Blog 7), it gets spread backward along the breadcrumb trail. Fresh crumbs get a big share of the credit. Faded ones get a little.

V (s) \leftarrow V (s) + α \cdot δ_{t} \cdot e_{t} (s)

The eligibility trace idea has roots in Klopf's biological thinking from Blog 6. Sutton turned it into a precise, tunable tool.

Why it matters for what comes next: TD(λ) gives RL its credit-assignment machinery. Watkins would soon bolt the same trick onto action-learning (his version is called Q(λ)). But first he needed to solve the bigger problem: learning actions at all.

Idea 2: Q-Learning, scoring choices instead of places (Watkins, 1989)

Chris Watkins introduced Q-Learning in his 1989 Cambridge PhD thesis, Learning from Delayed Rewards. The idea sounds almost too simple to be a breakthrough.

Instead of V(s) (how good is this state?), learn Q(s, a) (how good is this action in this state?). The "Q" stands for "quality."

Formally, Q*(s, a) is the total future reward you'd expect if you take action a in state s and play perfectly from then on:

Q^{(} s, a) = E [R_{t + 1} + γ a^{'} max Q^{(} S_{t + 1}, a^{'}) ∣ ∣ S_{t} = s, A_{t} = a]

That's Bellman's optimality idea from Blog 3, rewritten for actions. And here's the payoff: once you have Q*, the best policy is trivial. In every state, pick the action with the highest Q. No map required.

The table

Picture a spreadsheet. One row per state, one column per action. Each cell holds the agent's current guess for "how good is this action here?" At the start, every cell is 0 (or random). The agent knows nothing.

The update rule

Every time the agent takes a step, it fixes one cell of the table:

Q (s_{t}, a_{t}) \leftarrow Q (s_{t}, a_{t}) + α [r_{t + 1} + γ a^{'} max Q (s_{t + 1}, a^{'}) - Q (s_{t}, a_{t})]

Let's unpack it piece by piece:

Q(s_t, a_t) is the old guess for this action.
r_{t+1} is the reward the agent actually got.
γ max Q(s_{t+1}, a') is the best the next state can offer, discounted. (Bootstrapping again, just as in Blog 7.)
r + γ max Q(...) together form the target: "what this action looks like now that I've seen what happened."
The bracket is the TD error: target minus old guess. How wrong was I?
α is the learning rate: how much of the error to correct per step.

A worked example (with actual numbers)

Say the agent stands in state A and takes action "right," landing in state B.

Old guess: Q(A, right) = 0
Reward for the step: r = 0
Best option in B: max Q(B, ·) = 10 (it already learned that B is next to the goal)
γ = 0.9, α = 0.5

The target is 0 + 0.9 × 10 = 9. The error is 9 − 0 = 9. The update is 0 + 0.5 × 9 = 4.5.

So Q(A, right) jumps from 0 to 4.5, even though the agent got zero reward on that step. It earned that credit because it led somewhere good.

Now repeat this for thousands of steps. The goal's reward leaks into the square next to it, then into the square next to that, then the next, the same backward-spreading "rumor" from Blog 7's 3-step robot, only now it travels through action scores. Eventually every cell holds a sensible number and the best move from anywhere is "follow the biggest number."

The guarantee

Here's the part that made people sit up. Q-Learning isn't just "usually works." It has a proof.

Watkins outlined it in his thesis, and Watkins and Dayan published the full proof in 1992 (Machine Learning journal, "Technical Note: Q-Learning"). The result: with a table of values, and every action tried repeatedly in every state, Q-Learning converges to the optimal action-values with probability 1. Later, Tsitsiklis (1994) and Jaakkola et al. (1994) re-proved it with a more general toolkit.

The fine print matters, and it'll matter later in this post:

Every (state, action) pair must keep getting visited (so you must explore)
The learning rate α must shrink at the right pace over time
The values are stored in a table, not squeezed into a function approximator

Exploring: how does the agent visit everything?

Condition #1 above hides a puzzle. If the agent always picks its current best-looking action, it'll never discover that the road it dismissed early on was actually great. That's the explore vs exploit tension, one we've met before: Samuel wrestled with it in checkers (Blog 4) and Tsetlin built it into his learning automata (Blog 5).

The simplest practical recipe is ε-greedy:

a_{t} = {random action with probability ε ar g max_{a} Q (s_{t}, a) with probability 1 - ε

Roll a die. Most of the time (say 90%), do what the table says is best. The rest of the time (10%), do something random, just to see. Early in training, ε is large; as the table gets trustworthy, ε shrinks.

Hold on to this one detail, because it sets up the whole second half of the post: while exploring, the agent sometimes does dumb things on purpose.

The quiet superpower: off-policy learning

Look back at the Q-Learning update. The target uses max Q(s_{t+1}, a'): the value of the best next action. But what did the agent actually do next? Maybe it explored and did something random. The update doesn't care. It always learns as if the agent will play perfectly from the next step on.

This means two different "policies" are in play:

Behavior policy: what the agent actually does while collecting experience (messy, exploratory)
Target policy: what the agent is learning about (the greedy, best-possible policy)

When these two are different, the algorithm is called off-policy. Q-Learning is the classic example.

An analogy: imagine learning to drive by studying dashcam footage of other people, including clumsy drivers. You can still extract "what's the ideal move at this intersection?" from footage of someone who wasn't playing ideally. That's off-policy. On-policy would be learning to drive only from your own hands-on driving and judging yourself on exactly how you drive.

Why this matters in practice:

Reuse old data. Experience collected yesterday under a worse policy is still valid for updating Q today.
Explore wildly without poisoning what you're learning.
Learn from other people. A human demo, a different bot's game logs: all usable.

This one property is the reason the deep RL systems of the 2010s could store millions of past game frames and keep learning from them. Remember it when we reach DQN.

The table's fatal flaw

Q-Learning worked beautifully on small worlds: grid mazes, toy problems, dozens or hundreds of states. Then people tried it on something real.

Take an Atari game. The "state" is the screen: 210×160 pixels, each with one of 128 possible colors. The number of possible screens is beyond astronomical. You can't build a table with a row for each. You couldn't even store it.

This is the curse of dimensionality from Bellman's era (Blog 3), coming back for revenge. And the fine print from earlier bites: Watkins & Dayan's guarantee covers tables. Swap in a function approximator and the proof no longer applies (and, as people found, training can get unstable).

The natural fix: don't store a row per state. Learn a function that takes any state and estimates its Q-values, generalizing from states it has seen to ones it hasn't. A neural network is exactly that kind of function. Replace the table with a network that outputs one Q-value per action, keep Watkins's update rule almost unchanged, and you get the Deep Q-Network (DQN). That's DeepMind's 2013 breakthrough, and the star of Blog 11.

The table was never the destination. It was the prototype.

Before we get there: Blog 9 takes a detour to 1992, when Gerald Tesauro mixed TD learning with a neural network on a board game. It worked remarkably well, and it happened two decades before DQN.

Idea 3: SARSA, when being realistic beats being optimistic (Rummery & Niranjan, 1994)

By the early 90s, Q-Learning looked great. Then researchers noticed something uncomfortable: it's an optimist.

Its update assumes that after this step, the agent will always make the best possible move. But during training, the agent explores. It stumbles on purpose, on a schedule (remember ε). Q-Learning learns as if those stumbles will never happen.

Most of the time that's harmless. Sometimes it's a disaster. Enter the cliff.

The cliff-walking problem

This is a classic from Sutton & Barto's textbook. A grid, a start square, a goal square, and between them a row of cliff squares. Every step costs -1. Stepping on the cliff costs -100 and sends you back to the start.

The shortest path hugs the cliff edge. If you never slip, it's the best route.

Q-Learning correctly figures this out: the edge path is the optimal path for a perfect agent. So it learns to walk along the edge.
But the agent is still doing ε-greedy exploration while it learns. Occasionally it takes a random step... off the cliff. Ouch, -100. Q-Learning logs the penalty, but its update rule still says "the best move from here is great," so it keeps hugging the edge and keeps falling during training.

The SARSA fix

Gavin Rummery and Mahesan Niranjan (Cambridge, 1994) proposed a small change with a big consequence: learn from what the agent actually does next, not from what it could ideally do.

Compare the two updates. Only one term changes:

Q-Learning: Q (s_{t}, a_{t}) \leftarrow Q (s_{t}, a_{t}) + α ⎣ ⎡ r_{t + 1} + γ best possible next action a^{'} max Q (s_{t + 1}, a^{'}) - Q (s_{t}, a_{t}) ⎦ ⎤

SARSA: Q (s_{t}, a_{t}) \leftarrow Q (s_{t}, a_{t}) + α ⎣ ⎡ r_{t + 1} + γ action actually taken Q (s_{t + 1}, a_{t + 1}) - Q (s_{t}, a_{t}) ⎦ ⎤

Because each update needs the five things State, Action, Reward, next State, next Action, the algorithm is called SARSA.

What SARSA does on the cliff: when it wobbles near the edge and falls, the next-action value it bootstraps from is the real, wobbly one, so the penalty drags down the value of walking near the edge. Over time it prefers a longer, safer path with a buffer from the cliff. Not because that path is theoretically shortest, but because it's the best path for an agent that sometimes makes random moves.

This makes SARSA on-policy: the policy being learned and the policy generating experience are the same thing.

So which one is "better"?

Open Google Colab Notebook : QLearning vs SARSA Cliff Problem

Neither. They answer different questions:

	Q-Learning	SARSA
Type	Off-policy	On-policy
Learns the value of...	the ideal greedy policy	the policy it's actually following (with exploration)
Attitude	Optimist	Realist
Cliff behavior	Learns the risky edge path, falls more while training	Learns the safer detour, fewer falls while training
Great for	Reusing data, learning from demos, squeezing out the true optimum	Settings where mistakes during learning are costly

Two honest footnotes so nobody gets the wrong idea:

Q-Learning's final greedy policy really is the optimal one. The edge path is shortest. Its problem is the cost it pays during training, not the policy it ends up with.
SARSA isn't permanently stuck being cautious. If you shrink ε toward zero as training goes on, SARSA's behavior and Q-Learning's converge on the same optimal policy. SARSA is cautious because of exploration, not by nature.

The divide that never went away

Q-Learning vs SARSA looks like a niche algorithm detail. It turned out to be one of the big forks in the road of all of RL:

Off-policy (Q-Learning, DQN, SAC): learn about the best policy regardless of how you collected the data. Superpower: you can recycle old experience, which makes learning sample-efficient. Cost: learning can be less stable, especially once neural networks get involved.

On-policy (SARSA, PPO, most policy-gradient methods): learn only from data produced by your current behavior. Superpower: updates are consistent with what the agent really does, which tends to be more stable. Cost: you have to throw data away after you use it, so it's less sample-efficient.

You'll see both camps again. PPO, an on-policy method, became the workhorse for fine-tuning large language models with human feedback (RLHF). DQN-style and SAC-style methods, off-policy, dominate where interaction with the world is expensive. Many of today's design debates in RL are really the same question Watkins and Rummery put on the table: do I learn about what I could do, or about what I actually do?

What 1988–1994 actually established

Three things that weren't true in 1987 but were by 1994:

1. A machine can learn good behavior without a map of its world. Given a small enough problem (one a table can hold), Q-Learning learns the optimal policy purely from trial and error, with no transition model, and Watkins and Dayan proved it.

2. How you explore is a design choice, not a side effect. Learn about the ideal (Q-Learning, off-policy) or learn about reality (SARSA, on-policy). Both are useful, and the choice shapes everything downstream.

3. The Q-table is just a function approximator in its simplest form. Swap the table for something that generalizes, and the same update rule keeps working. The theory was already pointing at DQN, twenty years early.

What was missing was the generalizing part. Tables collapse at scale, and neural networks were the obvious replacement, but training them with TD updates turned out to be surprisingly unstable. That problem stayed open for a long time.

Next up: a neural network teaches itself backgammon

While theory was getting tidy, one researcher quietly tried the "obviously unstable" thing anyway. In 1992, Gerald Tesauro paired a neural network with TD learning and had it play backgammon against itself, millions of times, with no hand-written strategy. It reached a level that rivaled the world's best human players.

TD-Gammon was the first big proof that neural networks and RL could work together at scale. It also made self-play a training paradigm, the same idea that eventually leads to AlphaGo, AlphaZero, and beyond.

That's Blog 9.

Quick recap (if you only read this)

Model-free = learn what to do without learning how the world works.
TD(λ) = a dial between impatient and patient learning; breadcrumbs (eligibility traces) spread credit backward.
Q-Learning = score choices, not places; guaranteed to converge for tables; off-policy.
SARSA = learn from what you actually do; on-policy; safer when exploring is risky.
The table breaks at scale, which sets up neural networks.

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

Mitansh Gor — Sat, 17 Oct 2026 21:07:35 +0000

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:

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

Quick refresher: the words I'll use without re-explaining
This series already covered these, so here's just the one-line version:

State (s): the situation the agent is in right now (a board position, a pole's angle).
Action (a): what the agent can do from that state.
Reward (R): the immediate numeric feedback after an action.
Policy (π): the agent's rulebook for picking actions.
Episode: one full run, from start to finish (one game, one attempt).
Bellman equation: the idea from Blog 3 that a state's worth can be written in terms of the next state's worth. Today we put it to work.

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:

Question	Tool
What am I trying to maximize?	The Return
How good is it to be here?	The Value Function
How do I fix my guess when I'm wrong?	TD Learning

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:

G_{t} = R_{t + 1} + γ R_{t + 2} + γ^{2} R_{t + 3} + \dots = k = 0 \sum \infty γ^{k} R_{t + k + 1}

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)

V^{π} (s) = E_{π} [G_{t} ∣ S_{t} = s]

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):

δ_{t} = R_{t + 1} + γV (S_{t + 1}) - V (S_{t})

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

V (S_{t}) \leftarrow V (S_{t}) + α \cdot δ_{t}

In plain words:

Piece	Meaning
`V(S_t)`	My current guess for the state I'm in
`R_{t+1} + γV(S_{t+1})`	The TD target: what actually happened next, plus my guess about everything after
`δ_t`	The surprise: target minus guess
`α`	The learning rate: how big a step I take toward the target

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

After episode	V(A)	V(B)	V(C)
0	0	0	0
1	0	0	0.5
2	0	0.25	0.75
3	0.125	0.5	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:

	Monte Carlo	TD
Learns when?	Only at episode end	Every step
Works on never-ending tasks?	No	Yes
Uses real full outcomes?	Yes (no bootstrapping)	No, it leans on its own guesses
Typical downside	High variance (one lucky/unlucky game swings everything)	Some bias (early guesses are wrong, and they teach the next ones)

View the interactive Mote Carlo video

View the interactive TD Learning Video

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:

Δ θ \propto δ_{t} \cdot \nabla_{θ} lo g π_{θ} (a_{t} ∣ s_{t})

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:

Year	What happened
1984	Sutton's thesis: develops the TD idea and the actor-critic ("adaptive heuristic critic") view, with experiments showing it works
1988	Sutton's "Learning to Predict by the Methods of Temporal Differences": formal analysis (convergence for TD(0) in a limited setting), and the full TD(λ) family
1992	Peter Dayan: convergence with probability 1 for the tabular case
1997	Tsitsiklis & Van Roy: convergence analysis for TD with linear function approximation

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):

V (s) = E [R_{t + 1} + γ V (S_{t + 1}) ∣ S_{t} = s]

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.

Idea	What it gave us
Return `G_t`	A definition of what the agent is optimizing over time
Value Function `V(s)`	A way to judge a state before the reward shows up
TD Learning	Learn online by correcting a guess with a better guess
Actor-Critic	Split "doing" from "judging" for more stable learning
1984 Thesis	The framework that made credit assignment the central problem

1981–1984 Idea	Modern Descendant
Value prediction	Value networks (AlphaGo); critics in PPO
TD learning	Q-learning, DQN, and the bootstrapped targets inside most value-based RL
Actor-Critic	PPO (used in ChatGPT-style fine-tuning); a family of modern policy-gradient methods
Temporal credit assignment	Process reward models; step-level feedback for chain-of-thought
TD(λ) seeds	Eligibility traces in modern control

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.

RL 6: Pleasure-Seeking Neurons and the Birth of Backpropagation (1972–1980)

Mitansh Gor — Sat, 10 Oct 2026 21:33:29 +0000

Quick recap from Blog 5: Learning Automata could adapt to what was happening right now, but they were hopeless at delayed consequences. A chess move that loses you the game 20 turns later. A word that quietly breaks a sentence three clauses down. They had no way to connect "what I did" with "what happened much later."

This post is about the two people who went after that gap, and the third person who spotted a problem hiding behind it. By the end you'll know what an eligibility trace is, how backpropagation actually works (with a tiny example), and why every modern AI system still runs on ideas from this decade.

First, the problem in plain English

Imagine you're baking cookies for the first time. At step 2 you accidentally dump in a tablespoon of salt instead of a teaspoon. You keep going: mix, chill, shape, bake. At step 50 (taste time) the cookies are awful.

Now ask yourself: which step was the mistake?

You didn't taste anything at step 2. The feedback only showed up at the very end. To learn, you need a way to trace the bad result back to the step that caused it. That's the credit assignment problem (or "blame assignment", if you prefer): when something good or bad happens, which of your earlier decisions deserves the credit or the blame?

By the early 1970s the field had two things that didn't talk to each other:

Bellman's equations (Blog 3): mathematically perfect and provably optimal, but they need a complete model of the world. Nobody has that.
Samuel's checkers player and Tsetlin's automata (Blogs 4 and 5): practical and adaptive, but with no theory behind them and no good answer for late-arriving consequences.

The 1970s produced three ideas that started to close that gap. Here's the roadmap so you always know where we are:

Klopf gives a single neuron a drive and a short memory of what it just did. (Who gets credit, and when?)
Werbos gives a whole network a direction: a method to push blame backward through many layers. (How far back does the blame go?)
Grossberg adds a warning: learn too eagerly and you'll erase what you already knew. (How do we keep our old skills?)

Then we'll see how Adaptive Dynamic Programming wired them together, and how it produced the Actor-Critic idea that still runs inside modern AI.

Quick glossary

You'll see these words a lot. Don't memorize them, just glance:

Neuron (artificial): a tiny calculator. It takes numbers in, multiplies each by a weight, adds them up, and outputs a result.
Weight: how much the neuron "listens" to one particular input. Learning = adjusting weights.
Reward: a number telling the system "that went well" (positive) or "that went badly" (negative).
Expectation / baseline: the reward the system predicted it would get.
Layer: a group of neurons. A network stacks layers: input -> hidden layers -> output.
Loss: a single number measuring how wrong the output was. Lower is better.
Gradient: a list of "if I nudge this weight a little, how much does the loss change?"

Harry Klopf and the Hedonistic Neuron (1972)

Most of the 1970s AI crowd was busy building symbolic systems: expert systems, logic provers, decision trees. Harry Klopf, a researcher at the US Air Force Cambridge Research Laboratories, was looking at a single neuron and asking something stranger.

What if the neuron isn't a passive wire? What if it wants something?

In his 1972 report, Brain Function and Adaptive Systems: A Heterostatic Theory, Klopf proposed that neurons act like tiny hedonists: pleasure-seekers that strengthen the connections that led to good outcomes and weaken the ones that didn't.

That was a direct challenge to the textbook picture of a neuron as a threshold switch: inputs in, weighted sum, fire or don't. In that picture the neuron has no memory of outcomes and no preference about them. Klopf said that couldn't be the whole story.

Heterostasis vs. homeostasis (the thermostat vs. the athlete)

Biology textbooks of the time said living systems seek homeostasis: balance and stability. Think of a thermostat. It wants the room at 21°C. Hit 21 and it relaxes.

Klopf proposed heterostasis: a drive to push beyond the comfortable state toward something better. Think of an athlete. Hitting last month's personal best isn't "done", it's the new starting line.

Why does this matter for AI? Because it reframes learning as forward-looking. A thermostat-style learner stops when things are fine. A heterostat-style learner keeps asking "can I do better than I expected?" And that is exactly what reinforcement learning is.

The timing problem, and the eligibility trace

Back to the cookies. Klopf hit the same wall: rewards arrive after the action that caused them. When the reward finally shows up, how does the neuron know which of its recent activity deserves credit?

His answer: the eligibility trace. Think of it like a glowing footprint. When a connection is active, it leaves a footprint that fades over time. If a reward arrives while the footprint is still glowing, that connection is "eligible" for credit. If the footprint has faded, it isn't.

Here's a simplified teaching version of the idea as an update rule (Klopf's own later formulations got more elaborate, but this captures the heart of it):

Δ w_{i} (t) = α \cdot [r (t) - r ˉ (t)] \cdot x_{i} (t - τ)

Let's read it piece by piece:

Δw_i: how much to change the weight on input i (the "learning step").
α (alpha): the learning rate, i.e., how big a step to take.
r(t): the reward you actually got.
r̄(t): the reward you expected to get.
x_i(t − τ): the footprint, i.e., how active input i was a moment ago.

The middle piece, r − r̄, is the important one. It's surprise:

Got more than expected (r > r̄)? Strengthen whatever was recently active.
Got less than expected? Weaken it.
Got exactly what you expected? Change nothing. Nothing to learn.

Example: you order your usual coffee and it's good. No surprise, no learning. You try a new cafe, and the coffee is fantastic. Big positive surprise, and your brain strongly reinforces "go to that cafe." Learning is driven by the gap, not by the raw reward.

Hold onto this "surprise" idea. In Blog 8, Richard Sutton turns it into the TD error, which is arguably the most important quantity in all of RL. Klopf had the biological intuition first; the math came later.

And the footprint idea didn't die either: modern algorithms called TD(λ) still use eligibility traces in essentially this form.

Pause and check. Can you say, in one sentence, why a neuron needs both a surprise signal and an eligibility trace? (Surprise tells it how much to change. The trace tells it what to change.)

Where we are: Klopf gave a neuron a drive and a short memory. But a single neuron is tiny. What happens when you have layers of them, and the reward only connects to the last layer? That's the next problem.

Paul Werbos and the Algorithm Nobody Read (1974)

A neuron that wants reward but can't figure out which of its decisions caused it will thrash forever. And this gets brutal in multi-layer networks. If the final answer is wrong, which weight, in which layer, is responsible? In 1974, nobody had a practical answer for neural networks.

Paul Werbos did. Getting anyone to pay attention was the hard part.

In his 1974 Harvard PhD thesis, Beyond Regression: New Tools for Prediction and Analysis in the Behavioral Sciences, Werbos described how to train multi-layer neural networks by propagating error backward through the layers. Today we call this backpropagation (often just "backprop").

Backprop without the scary math: the assembly line

Picture a three-station assembly line making a gadget. Station 1 passes its work to Station 2, then Station 3, then the finished gadget gets inspected. The inspector says: "This is off by 6 millimeters."

Whose fault is that? The inspector can only see the final product. But here's the trick:

Station 3 asks: "How much did my output contribute to that error?" It can answer directly, because it's the last one.
Station 3 tells Station 2: "Here's how sensitive the final result is to what you gave me."
Station 2 uses that to work out its own share of blame, then tells Station 1.

Blame flows backward, station by station, each one using what the next one told it. That's backpropagation.

The chain rule, with gears

The math behind this is the chain rule from calculus, and it's much friendlier than its name. Here's the idea with gears.

Say turning Knob A by 1 unit moves Knob B by 3 units. And turning Knob B by 1 unit moves the final output by 2 units. Then turning Knob A by 1 unit moves the output by 3 × 2 = 6 units.

That's the whole chain rule: when effects are chained together, you multiply the sensitivities.

\frac{\partial L}{\partial w _{i}} = \frac{\partial L}{\partial a} \cdot \frac{\partial a}{\partial z} \cdot \frac{\partial z}{\partial w _{i}}

Translating the symbols:

L: the loss (how wrong the final output was).
a: a neuron's output (its "activation").
z: the neuron's input sum before it produces its output.
w_i: the weight we want to adjust.

Read the equation left to right as a story: "How much does the loss change if I nudge this weight?" = "how much the loss changes with the neuron's output" × "how much the output changes with its input sum" × "how much the input sum changes with the weight." Three gear ratios multiplied together. Do this for every weight in every layer and you get the gradient: a complete to-do list of nudges that reduce the error.

For the first time, a multi-layer network had a principled way to learn: not just the output layer, but every layer, including the ones far from the reward.

Werbos's bigger vision: backprop as a tool for Bellman

Here's the part that matters for this series. Werbos didn't think of backprop as just "neural network training." He saw it as a way to make Bellman's equations usable on real problems. Remember from Blog 3: Bellman's math is perfect but chokes on large problems because you'd need a giant table with an entry for every possible situation. Werbos's idea: don't store the table, approximate it with a neural network and train that network with backprop. He called this framework Adaptive Dynamic Programming (ADP).

That exact idea (a neural network standing in for a value table) is what DeepMind used in DQN in 2013, thirty-nine years after Werbos's thesis (Blog 11). He saw the destination early; the hardware and data took decades to catch up.

Pause and check. Backprop answers "how much is each weight to blame?" ADP asks "what should we be using backprop on?" The answer: an estimate of how good each situation is. That estimate has a name, and it's next.

Adaptive Dynamic Programming: wiring it all together

We need one new idea before this makes sense: the value function.

A value is a number answering "how good is this situation in the long run?", not just "how good does it feel right now?"

Back to cookies: imagine you've already added the salt disaster and the dough is mixed. Nothing bad has happened yet. No reward, no punishment. But that dough is already doomed. A good value function would score it low immediately, before anyone tastes it. That's the power of values: they let you judge a situation before the consequences show up.

A high-value state is one where, even with no immediate reward, the future looks rich.
A low-value state is a trap: maybe it feels fine now, but it funnels you toward failure.

The Bellman equation says how values relate to each other:

V (s) = a max [R (s, a) + γ s^{'} \sum P (s^{'} ∣ s, a) V (s^{'})]

In words: the value of a situation = the best action's (immediate reward + discounted value of wherever you land next).

V(s): value of situation (state) s.
a: an action you could take. max means "pick the best one."
R(s,a): the immediate reward.
γ (gamma): a discount between 0 and 1. A reward tomorrow is worth a bit less than a reward today.
P(s' | s, a): the probability of landing in the next state s', and V(s') is its value.

The catch, as always: you can't write a table for every state of a real problem. This is the curse of dimensionality: the number of states explodes as problems grow. ADP's workaround is to use a neural network V(s; weights) as a stand-in for the table, and train it with backprop. The curse isn't gone, but it stops being a wall and becomes a negotiation.

The Actor-Critic idea

Out of ADP came one of the cleanest architectural ideas in all of RL, and it's still everywhere: Actor-Critic.

The Actor decides what to do. It tries things, explores, proposes moves. This is Klopf's trial-and-error learner.
The Critic judges how good the situation is, using a value function trained with backprop. This is Werbos's contribution.

An everyday analogy: a student (Actor) writes essays, and a coach (Critic) reads them. The coach doesn't write anything but learns to predict how good an essay will be. The student improves by listening to the coach's feedback, not just waiting for a final grade at the end of term. Meanwhile the coach also improves by comparing predictions to actual results. Both learn at once.

And notice how the pieces line up: the Critic's prediction is the "expectation" in Klopf's update rule. When reality beats the Critic's prediction, that surprise tells the Actor "do more of that."

A quick date check so nothing here gets overstated. ADP was being developed in the late 1970s (Werbos's early forms of it date to around 1977). The actor-critic architecture as a working, tested system came in 1983, when Barto, Sutton and Anderson used it to learn pole balancing, which is the subject of Blog 7.

The big conceptual change: before this, learners mostly reacted. With a value function they could anticipate. A system balancing a pole can learn that a certain tilt is "bad news" before it falls. That's the difference between reflex and planning.

Stephen Grossberg: the warning label (1976)

We now have a learner with drive, direction, and anticipation. Stephen Grossberg raised a problem that sounds almost boring but turned out to be one of the hardest in the field: learning can destroy what you already know.

Train a network hard on chess, then train it on Go, and it may forget chess, not gradually but catastrophically. New updates overwrite old structure. (The name catastrophic forgetting was attached to this in the late 1980s, but Grossberg was already wrestling with the underlying issue in the 1970s.)

An everyday version: you spend a year learning Spanish, then cram Italian for two months, and suddenly your Spanish is full of Italian words. Your brain used the same "shelf space" for both.

Grossberg's Adaptive Resonance Theory (ART), from 1976, framed this as a tug-of-war between two forces:

Plasticity: the ability to learn new things.
Stability: the ability to keep what you already know.

Too much plasticity and you forget everything. Too much stability and you can never learn anything new. ART's answer: when a new input resembles something you already know, the two "resonate" and the memory is updated. When it's very different, don't overwrite, create a new category instead.

This tension never went away. Continual learning, fine-tuning without forgetting, and knowledge distillation are all modern attempts at the problem Grossberg named in the 1970s.

Putting it together: desire, direction, memory

Step back. By 1980 three ideas were on the table:

Person	Gave learning systems	The key idea in one line
Klopf	A drive	Learn from the gap between expected and actual reward; use a fading trace to know what to credit
Werbos	A direction	Send blame backward through layers with the chain rule; use it to train value estimates
Grossberg	A memory	Balance new learning against keeping old knowledge

Learning Automata had none of the three. And remember our cookie problem? Klopf's trace says which recent actions are eligible. Werbos's backprop says how to push the blame back through the whole recipe. The value function says this dough is doomed before anyone tastes it.

The scale was tiny by modern standards: a handful of neurons, small simulations, and a thesis that sat mostly unread. But the logic was complete.

Why this still matters today

Here's a connection that makes this history feel less like a museum visit. Modern RLHF (reinforcement learning from human feedback), the process used to tune chatbots like the one you may be chatting with, follows the same blueprint:

A reward signal encodes what people prefer (helpful, correct, safe). That's Klopf's pleasure.
When an output beats expectations, the pathways behind it get reinforced, and the blame or credit travels back through billions of weights via backprop. That's Werbos.
The algorithm commonly used for this, PPO, is an actor-critic method: one part proposes, another part estimates value. That's the architecture from this post.
Keeping the model from forgetting how to do everything else while it's being tuned? That's Grossberg's problem.

The math is more sophisticated and the networks are enormous. But the skeleton hasn't changed. What evolved over five decades wasn't the idea. It was the scale.

What's next

The pieces are on the table, but they're not assembled yet:

Klopf's biological intuitions need a rigorous mathematical home.
Backprop needs to be tied explicitly to temporal credit assignment (credit across time).
Actor-Critic needs someone to build it, test it, and write it down properly.

In 1981, Richard Sutton and Andrew Barto began doing exactly that, starting from a model of classical conditioning (think Pavlov's dog). Within a few years they'd produce the first rigorous treatment of temporal credit assignment in RL, including that pole-balancing actor-critic. That's when the field stopped being a collection of brilliant isolated ideas and started becoming a coherent science.

Next: Blog 7, The Sutton and Barto Foundation: Formalizing Temporal Credit Assignment (1981–1984).

RL 5: Learning Automata and stochastic environments (1961–1974)

Mitansh Gor — Sat, 03 Oct 2026 04:48:09 +0000

Quick recap, in case you're jumping in from Blog 4.

Arthur Samuel's checkers program learned by guessing how good a board position was (value estimation). Donald Michie's matchbox machine, MENACE, learned by shifting which move it preferred (policy selection). Both worked. Both were fragile: Samuel needed hand-crafted features, and Michie needed one matchbox for every possible board.
That left a question hanging: what is the absolute minimum a machine needs in order to improve from feedback?

The first clean answer came from Moscow.

Before we start: a 60-second jargon cheat sheet

You'll see these words a lot in this post. None of them are scary.

Agent: the thing that acts and learns (here, a tiny machine).
Environment: whatever the agent interacts with (here, a set of slot machines).
Action: a choice the agent can make (which machine to pull).
Reward / Penalty: the feedback after an action. Good outcome = reward, bad outcome = penalty.
Stochastic: "random-ish." The same action can give different results on different tries.
Automaton (plural: automata): a machine that lives in one of a fixed number of states and hops between them by simple rules. Think of a traffic light, not a supercomputer.
State: which "mode" the machine is currently in. Its memory, basically.

Part 1: The smallest learning machines

The problem: how do you learn when feedback is unreliable?

Samuel and Michie taught us that machines can learn from experience. But both of their systems quietly assumed the feedback made sense. Win the game, good. Lose the game, bad.

Real life is messier. Picture vending machines on your street:

Machine A gives you a free snack 70% of the time.
Machine B gives you a free snack 40% of the time.

You don't know these numbers. You can only try a machine, see if it pays, and adjust. And here's the catch: Machine A will sometimes fail you, and Machine B will sometimes get lucky. One result tells you almost nothing.

So the real question becomes: how does a machine learn the right choice when any single outcome might be a lie?

That's the world of stochastic environments, and it's where Mikhail Tsetlin starts.

Meet Mikhail Tsetlin: the "smallest possible brain" guy

Mikhail Tsetlin (1924–1966) was a Soviet mathematician working in Moscow in the era of early cybernetics. In 1961 he published a paper titled "On the behaviour of finite automata in random medium". The title is a mouthful, but the idea is beautifully modest.

Most researchers of the day asked, "how do we build a smarter machine?" Tsetlin asked the opposite question:

What is the smallest internal structure a machine needs to improve its behavior?

Not the most powerful. The smallest. He was hunting for the floor of machine intelligence.

His answer was a finite-state automaton with a twist: no model of the world, no predictions, no calculus, no score. Just:

a handful of internal states (its memory),
a rule for choosing an action based on the current state, and
a rule for moving between states based on feedback.

Note the phrase "random medium" in the title. That's Tsetlin's name for a stochastic environment: a world that answers your actions with reward or penalty according to hidden probabilities. The vending machines are a random medium.

The Rooms: Tsetlin's memory, made visible

The best way to understand a Tsetlin automaton is to picture a hallway of rooms.

The left half of the hallway is "Action A" (pull machine A).
The right half is "Action B" (pull machine B).
The machine is always standing in exactly one room, and whatever side it's on decides what it does next.

Here's a small version with 3 rooms per side (6 states total):

   Action A side              Action B side
 [ 1 ] [ 2 ] [ 3 ] | [ 4 ] [ 5 ] [ 6 ]
  deep        edge  |  edge        deep

The rules are only two lines long:

Reward -> walk deeper into your current side (more committed).
Penalty -> walk one room toward the middle. If you were already at the edge, you cross the border and switch actions.

Feedback is just a single bit: 0 = reward, 1 = penalty. No scores, no probabilities, no gradients. Only movement.

Let's walk through it

Say we start in room 3 (the edge of Action A) and keep pulling machine A, which pays 70% of the time:

Step	Room	Action	Result	Where we go next
1	3	A	Reward	Room 2 (deeper)
2	2	A	Reward	Room 1 (deepest)
3	1	A	Penalty (bad luck!)	Room 2 (one step back)
4	2	A	Reward	Room 1 again

Look at step 3. The machine got unlucky, but it didn't panic. One bad result only moved it one room, and it was still firmly on Team A. The rooms absorbed the noise.

Why memory matters (why not just flip a coin?)

You might ask: if feedback is just reward/penalty, why bother with six rooms? Why not the simplest rule ever: "if it paid, do it again; if not, switch"?

Funny thing: that rule is a Tsetlin automaton, the smallest one, with only 1 room per side. It's the classic win-stay, lose-shift strategy. And it's jumpy. One unlucky penalty and it abandons a perfectly good machine.

Think of your favorite restaurant. You had one bad meal. Do you never go back? Of course not. You have memory of many good meals, so one bad night doesn't flip your opinion. More rooms = more patience.

So let's test it. I simulated the exact hallway above (Machine A pays 70%, Machine B pays 40%, 5,000 pulls per run, averaged over 200 runs), changing only the number of rooms per side, N:

Rooms per side (N)	Share of pulls on the better machine
1 (win-stay, lose-shift)	~67%
2	~80%
3	~89%
5	~97.5%
10	~99.9%

More memory, better decisions. Here's the tiny code if you want to try it yourself:

import random

def tsetlin(pay=(0.7, 0.4), N=3, steps=5000):
    # states 1..N   -> action 0 (1 = deepest, N = edge)
    # states N+1..2N -> action 1 (N+1 = edge, 2N = deepest)
    state = N
    pulls = [0, 0]
    for _ in range(steps):
        action = 0 if state <= N else 1
        pulls[action] += 1
        rewarded = random.random() < pay[action]
        if action == 0:
            state = max(state - 1, 1) if rewarded else state + 1
        else:
            state = min(state + 1, 2 * N) if rewarded else state - 1
    return pulls

print(tsetlin(N=1), tsetlin(N=10))

Tsetlin proved this trend mathematically. As N grows, the automaton gets arbitrarily close to always picking the best action:

P (best action) \to 1 as N \to \infty

Two honest footnotes:

This works when the best action really is better than a coin flip (its penalty probability is below 50%). Our 70% machine qualifies.
Memory has a price. A deep automaton is stubborn: if the world changes (say, Machine B suddenly gets better), a machine sitting in the deepest room needs many penalties to walk out. Stability and adaptability pull in opposite directions. Remember this tension; it comes back in Part 2.

The catch: rooms don't scale

Tsetlin's automaton is elegant, but notice what it needs: a hand-designed hallway. How many rooms? Which transitions? For two actions it's easy. For a hundred actions you'd be designing a giant state machine by hand.

It's the same flavor of problem we hit in Blog 4: Michie needed a matchbox per board. Tsetlin needed a room per memory level. Someone had to ask: what if we just delete the rooms?

Delete the rooms: Variable-Structure Automata

The idea of replacing rooms with probabilities dates to Soviet researchers Varshavskii and Vorontsova (1963), and similar update rules were being explored in mathematical psychology around the same time. Then in 1974, Kumpati Narendra and M. A. L. Thathachar published a landmark survey, "Learning Automata: A Survey", that organized the whole field, gave it its name in the West, and split it into two families:

1. Fixed-Structure Automata (FSA): Tsetlin's world.
The hallway is fixed. Learning = moving through rooms. Where you go next depends only on where you are now and whether you were just rewarded or penalized.

2. Variable-Structure Automata (VSA): throw away the house.
No rooms at all. Instead the machine keeps a list of probabilities, one per action, that always adds up to 100%. Like a set of volume knobs where turning one up turns the others down.

Learning becomes: "that worked, so turn its knob up a bit."

The volume-knob rule, with real numbers

Let p_i be the probability of picking action i, and λ (lambda) a small "step size" called the learning rate. When the chosen action i is rewarded:

p_{i} \leftarrow p_{i} + λ (1 - p_{i})

and every other action j is nudged down so the total stays at 1:

p_{j} \leftarrow (1 - λ) p_{j}

Concrete example with 3 actions, p = [0.50, 0.30, 0.20], λ = 0.1, and action 1 gets rewarded:

Action 1: 0.50 + 0.1 x (1 - 0.50) = 0.55
Action 2: 0.30 x 0.9 = 0.27
Action 3: 0.20 x 0.9 = 0.18
New total: 0.55 + 0.27 + 0.18 = 1.00 ✓

If the same action is penalized instead, the mirror-image rule turns its knob down and spreads that probability over the others:

p_{i} \leftarrow (1 - λ) p_{i}, p_{j} \leftarrow \frac{λ}{r - 1} + (1 - λ) p_{j}

(r is the number of actions.) With our example: action 1 drops to 0.45, action 2 rises to 0.32, action 3 to 0.23. Still totals 1.

Notice something? No rooms, no transition table, no memory hallway. The probability list is the memory. One small rule replaced a whole state machine.

Why this matters for modern RL

This is where the old Soviet-era ideas quietly show up in today's algorithms.

"Raise the probability of what worked" is the heart of policy gradient methods (we'll get there properly in Blog 10). Ronald Williams's REINFORCE algorithm (1992) is a direct descendant, and Williams himself showed that a learning automaton can be viewed as a special case of REINFORCE. It's the volume knob again, just dressed up with gradients so it can tune millions of parameters instead of three numbers.

Tsetlin's rooms have a living descendant too. In 2018, Ole-Christoffer Granmo introduced the Tsetlin Machine, which uses teams of Tsetlin automata to learn human-readable logic rules from data. It's a rare case of a 1961 idea being revived as a modern machine-learning method, notable for being interpretable and cheap to run.

And the same tension keeps returning. Tsetlin's "memory = stability, but also stubbornness" is the modern stability-vs-adaptability problem that every RL practitioner still wrestles with.

Tsetlin vs. Narendra: two halves of one answer

	Tsetlin (rooms)	Variable-structure (volume knobs)
Memory lives in...	Which room you're in	The probability list
Strength	Stable; noise gets absorbed	Simple; scales to many actions
Weakness	Architecture must be designed by hand	Needs a careful step size `λ`
Answers the question	"Where do I go next?"	"How much do I like this action now?"
Modern echo	Tsetlin Machines, stability vs. adaptability	Policy gradients, REINFORCE

Together they gave the field its first solid answer to Tsetlin's question: a machine can improve from nothing but feedback, with no model of the world.

Part 2: The puzzle behind it all, the Multi-Armed Bandit

Zoom out: you've been solving a famous problem

What you just saw, a row of slot machines with unknown payouts and a limited number of pulls, is famously called the Multi-Armed Bandit problem ("one-armed bandit" is old slang for a slot machine). The idea goes back to Thompson (1933), who asked how to split patients between two treatments, and the statistician Herbert Robbins formalized it in 1952. Tsetlin's random-medium experiments attacked the same core dilemma from an automata angle.

It is the cleanest version of the exploration vs. exploitation trade-off we met in Blog 4 with Samuel:

Exploit: keep pulling the machine that seems best.
Explore: try another one, in case it's actually better.

Interesting detail: a Tsetlin automaton never decides to explore. Noise does it for it. Occasional penalties push it toward the boundary, and it sometimes tries the other side. Exploration falls out of the structure for free.

Rooms and volume knobs are two ways to play this game. Engineers have since built sharper ones. To compare them fairly, we first need to state the problem cleanly.

The setup

You face K machines (called arms). Arm a pays out according to some fixed, unknown average μ_a. At every step t = 1, 2, ..., T you pick one arm and see the reward from that arm only. Your goal: collect as much total reward as possible over T steps.

Two things make this hard:

You only see the arm you pulled. You never learn what the other arms would have paid.
Your data depends on your choices. If you stop pulling an arm, you stop learning about it. A bad first impression can become permanent.

Scored, not taught

Compare this to supervised learning, where a teacher hands the machine the right answer ("this image is a cat"). A bandit gets no such answer. It only gets a score for what it did ("that ad got a click") and no hint about whether something else would have scored higher. The only way to find out is to try other things. Sutton and Barto call this evaluative feedback, and it's the reason exploration exists at all.

Why bandits matter

They isolate exploration vs. exploitation. One situation, no delayed consequences, so you can study the dilemma in its purest form.
They score you while you learn. Not "how accurate is the model after training," but "how much did you lose along the way." That score is called regret, coming up next.

A few new words

Arm: one choice you can make (a slot machine, an ad, a headline).
Q(a): your running estimate of how good arm a is.
Gap (Δ): how much worse an arm is than the best arm.
Regret: the total reward you lost by not always playing the best arm.
Posterior: your belief about an arm's true payout after seeing data. Wide = unsure. Narrow = confident.

Two tools you need: estimating and keeping score

Estimating an arm's value, one pull at a time

After n pulls of an arm, the average reward is Q_n = (R_1 + R_2 + ... + R_n) / n. You never need to store the history. Rearranging gives an update that shows up everywhere in RL:

Q_{n + 1} = Q_{n} + \frac{1}{n} (R_{n} - Q_{n})

In words: new estimate = old estimate + step size x (target - old estimate).

Now swap the 1/n for a constant α. Old rewards fade out gradually, so you track a moving target instead of a fixed one. That's how you cope with a world that changes (we'll see the payoff in the practical section).

Q_{n + 1} = Q_{n} + α (R_{n} - Q_{n})

Remember the volume knob? The reward rule p ← p + λ(1 - p) from earlier is this exact update with target 1. Same idea, different clothes.

Regret: the scoreboard

Let μ* be the average payout of the best arm and Δ_a = μ* - μ_a the gap of arm a. After T steps, the regret is how much you earned less than someone who knew the best arm from the start:

R T = T μ^{*} - E [\sum t = 1^{T} R_{t}] = a : Δ_{a} > 0 \sum Δ_{a} E [N_{T} (a)]

(E[...] just means "on average," and N_T(a) is how many times you pulled arm a.) The second form is the useful one: regret = (cost per bad pull) x (number of bad pulls).

Quick example with our vending machines: the gap between A (70%) and B (40%) is 0.3. Every pull of B costs you 0.3 snacks on average, so 100 pulls of B means about 30 snacks of regret. To keep regret low you must pull bad arms as rarely as possible, but you can't skip them entirely, or you'd never know they were bad.

How should regret grow over time?

Linear in T: you never stopped making mistakes. Failure.
Logarithmic in T: mistakes become rarer and rarer, so regret grows slower and slower. This is the best anyone can do, which Lai and Robbins proved in 1985.

One more intuition worth keeping: the closer two options are, the longer it takes to tell them apart, and the more exploring you must pay for. Telling a 70% machine from a 40% one is easy. Telling 12% from 15% takes thousands of pulls.

The strategy zoo

Now the fun part. We'll go through the main strategies, each with its rule, its intuition, its math, and where it breaks.

1. Greedy: always pick the best-looking arm

A_{t} = ar g a max Q_{t} (a)

Simple, and broken. A single lucky early pull on a mediocre arm can make its estimate look best, and since pure greedy never samples anything else, it locks onto that arm forever. That's linear regret, caused by zero exploration.

2. ε-greedy: add some randomness

With probability 1 - ε pick the best-looking arm; with probability ε pick uniformly at random. Dead simple and a great baseline.

Its flaw is mathematical: random exploration continues forever, even when you're certain. Because ε stays fixed (say, 0.10), each arm is chosen with probability at least ε/K at every step, which gives:

R T \geq \frac{ϵ}{K} (\sum a Δ_{a}) T

That's linear regret. A fixed ε is a permanent tax: even after 1,000,000 pulls, when you know exactly which arm is best, you still waste about 10% of pulls on random choices. (Shrinking ε over time can fix this, but then you have a schedule to tune.)

3. Optimistic initialization: let disappointment drive exploration

Start every estimate absurdly high, for example Q_1(a) = +5 when real rewards range from 0 to 1. Every arm you try then "disappoints" compared to that starting hope, so the greedy rule naturally moves on to the untried arms. It's a clever, nearly free trick that gets a purely greedy algorithm to try everything without any random choices.

The catch: once every arm has been sampled enough, the optimism is gone and the estimates settle at their true averages. If the world changes later (a bad machine suddenly starts paying well), the agent won't re-investigate, because that machine's estimate was pushed down long ago. It only drives exploration during the opening phase.

4. UCB: optimism in the face of uncertainty

UCB (Upper Confidence Bound) is the first strategy built on rigorous probability theory. Instead of picking the arm with the best average, you pick the arm with the best plausible upper bound: its estimate plus an uncertainty bonus.

A_{t} = ar g a max [Q_{t} (a) + c \frac{ln t}{N _{t} ( a )}]

How the bonus behaves:

It shrinks with experience. The more you pull an arm (N grows), the smaller its bonus, because its average is already trustworthy.
It grows with time. As t ticks forward, the bonus creeps up for neglected arms, so every option eventually gets another look.

A worked example (using c = 1 to keep things simple; at step t = 200):

	Average `Q`	Pulls `N`	Bonus	Score
Arm A	0.50	100	0.23	0.73
Arm B	0.40	10	0.73	1.13

Arm A has the better average, but UCB plays Arm B, because with only 10 pulls it might still be hiding something great. Pull B a few more times and its bonus shrinks; if its average stays low, A takes over again. Exploration shrinks exactly as fast as your doubt does.

5. Thompson Sampling: let each arm "vote" with a random draw

Thompson's 1933 algorithm is surprisingly simple, and works remarkably well:

Keep a posterior (a curve showing how confident you are about each arm's payout).
Draw one random sample from each arm's curve.
Play the arm whose sample is highest.

For yes/no outcomes (clicks vs. no clicks), the natural curve is the Beta distribution. You start with a flat Beta(1, 1) ("total uncertainty"). After s successes and f failures, it becomes Beta(1 + s, 1 + f).

Worked example

Two ads show roughly the same 30% click rate, but with very different amounts of evidence:

	Data	Posterior	Mean	Std. Dev.
Ad X	3 clicks / 10 views	`Beta(4, 8)`	0.333	0.131
Ad Y	30 clicks / 100 views	`Beta(31, 71)`	0.304	0.045

Similar averages, wildly different certainty:

How self-correcting exploration works

Because Ad X has a wide, uncertain curve, its random draws beat Ad Y's about 58% of the time. That balances exploring and exploiting automatically:

Exploitation (Ad Y): a reliable performer with high confidence, a stable baseline.
Exploration (Ad X): unproven. It could turn out to be a weak ad or a game-changer, and the width of its curve is the potential upside of learning more.
Automatic feedback loop:
- If Ad X's future impressions fail to convert, its curve shifts left and narrows, so it loses future draws and drops out of rotation.
- If Ad X keeps converting, its curve narrows around a high mean and it becomes the new winner.

Thompson Sampling spends exploration effort in proportion to uncertainty, with almost no tuning (no c, no ε).

6. Gradient bandits: learn preferences, not values

Instead of estimating how good each arm is, learn a numerical preference H(a) and turn preferences into probabilities with a softmax (a recipe that turns any list of numbers into probabilities that add up to 1):

π_{t} (a) = \frac{e ^{H_{t} (a)}}{\sum _{b} e ^{H_{t} (b)}}

After pulling A_t and receiving R_t, update, using the running average reward R̄_t as a baseline ("what I normally get"):

H_{t + 1} (a) = H_{t} (a) + α (R_{t} - R ˉ_{t}) (1 [a = A_{t}] - π_{t} (a))

In plain words: better than usual? Push the chosen arm's preference up and the others down. Worse than usual? The reverse. (Mathematically this is gradient ascent on average reward, and the baseline keeps the updates from being too jumpy.)

Back to Part 1, and a preview of Blog 10: this is the volume-knob idea again ("raise the probability of what worked"), now with a gradient. Bandits are where policy gradients start.

Let's measure them

Theory is nice. Here's what actually happens. I ran two experiments.

Experiment 1: the classic 10-armed testbed. Each run draws 10 arm averages at random, rewards are noisy around those averages, 1,000 steps, averaged over 1,000 runs:

Strategy	Avg reward (last 200 steps)	% pulls on best arm	Cumulative regret @ 1,000
Greedy (ε = 0)	0.997	34.7%	508.7
ε-greedy, ε = 0.01	1.345	62.0%	327.5
ε-greedy, ε = 0.1	1.346	79.4%	229.6
Optimistic init (Q₁ = 5, α = 0.1)	1.499	86.2%	238.7
Gradient bandit (α = 0.1)	1.495	83.9%	184.6
UCB (c = 2)	1.524	85.9%	147.7
Thompson sampling	1.546	90.3%	68.4

Two honest footnotes:
(1) Thompson's starting beliefs here exactly match how the arms were generated, which flatters it, so don't expect a 2x regret win in the wild;
(2) c = 2 uses the Sutton-Barto form c·√(ln t / N), and c is a tuning knob.

Experiment 2: how does regret grow? Five arms with success rates 0.10, 0.12, 0.15, 0.20, 0.25 (small gaps, like real conversion rates), averaged over 40 runs:

Strategy	Regret @ 1,000	@ 5,000	@ 20,000
ε-greedy (ε = 0.1)	48	104	233
UCB1 (c = √2)	61	204	418
Thompson	34	57	73

Read this one slowly, because it teaches something the textbooks gloss over:

ε-greedy's regret grows at a constant slope (about 0.0086 per step between 5k and 20k), matching the (ε/K)ΣΔ floor we derived. It will lose in the long run.
UCB1 is worse than ε-greedy at this horizon. Its "grows slower and slower" guarantee is real, but its constants are conservative, and its slope (about 0.014 per step here) is still shrinking. "Best in the long run" does not mean "best at your horizon."
Thompson's slope is about 0.001 per step. Nearly flat. That's why you see it so often in production.

A reference implementation

Small enough to read in one sitting, tested to produce the numbers above:

import numpy as np

class EpsGreedy:
    def __init__(self, K, eps=0.1, alpha=None):
        self.eps, self.alpha = eps, alpha
        self.Q, self.N = np.zeros(K), np.zeros(K)
    def select(self, t):
        if np.random.rand() < self.eps:
            return np.random.randint(len(self.Q))
        return int(self.Q.argmax())
    def update(self, a, r):
        self.N[a] += 1
        step = self.alpha if self.alpha else 1.0 / self.N[a]   # alpha => non-stationary
        self.Q[a] += step * (r - self.Q[a])

class UCB1:
    def __init__(self, K, c=np.sqrt(2)):
        self.c, self.Q, self.N = c, np.zeros(K), np.zeros(K)
    def select(self, t):                      # t starts at 1
        if (self.N == 0).any():
            return int(np.argmin(self.N))     # play every arm once first
        return int((self.Q + self.c * np.sqrt(np.log(t) / self.N)).argmax())
    def update(self, a, r):
        self.N[a] += 1
        self.Q[a] += (r - self.Q[a]) / self.N[a]

class ThompsonBernoulli:
    def __init__(self, K):
        self.wins, self.losses = np.ones(K), np.ones(K)    # Beta(1,1) prior
    def select(self, t):
        return int(np.random.beta(self.wins, self.losses).argmax())
    def update(self, a, r):
        if r: self.wins[a] += 1
        else: self.losses[a] += 1

def run(agent, probs, T):
    best, regret = max(probs), 0.0
    for t in range(1, T + 1):
        a = agent.select(t)
        r = np.random.rand() < probs[a]
        agent.update(a, r)
        regret += best - probs[a]
    return regret

print(run(ThompsonBernoulli(5), [0.10, 0.12, 0.15, 0.20, 0.25], 20000))

The practical corner: using a bandit for real

When a bandit is the right tool

Feedback is immediate. You act, you get a number, and your action doesn't change what situations you'll face next.
Showing the loser has a real cost. Every user sent to a worse option is lost revenue, clicks, or goodwill.
Choices are discrete and few-ish. Headlines, layouts, models, prompts, settings.
You'll keep running it. A bandit is a loop, not a one-off analysis.

when the world changes

Five arms with success rates 0.2, 0.3, 0.4, 0.5, 0.7 for 4,000 steps, and at step 2,000 the order is reversed, so the best arm becomes the worst. Total reward, averaged over 500 runs:

Estimator	Total reward
Plain average (assumes the world never changes)	~1,791
Constant step size, `α = 0.1`	~2,560
Only the last 500 observations ("sliding window")	~2,537
Someone who always knows the best arm	2,800

The plain average never recovers: after 2,000 steps its estimates are so weighed down by history that new evidence barely moves them. Switching to a constant step size, a one-line change, won back about 770 reward. This is Tsetlin's stability-vs-adaptability tension again, now with a dial you control.

Choosing an algorithm

Your situation	Reach for	Why
Clicks / conversions (yes or no), you want a strong default	Thompson (Beta-Bernoulli)	Almost no tuning, strong in practice
You need a deterministic, explainable rule	UCB	Same inputs always give the same choice
Payouts drift over time	Any of these with a constant step size	Old data fades
Each decision comes with info about the user	Contextual bandit (a bandit that first looks at who's in front of it)	Personalizes the choice
You want something trivial to ship today	ε-greedy	Easiest to explain and debug

Where it all runs out of road

So, problem solved? Not quite. Learning automata and bandits share two big blind spots:

1. They don't see the situation, and they don't change it. The machine picks an action, but it never observes anything about the world first. There's no "if the board looks like this, do that." A vending machine is always the same vending machine, and pulling its lever doesn't change what comes next. Real problems change from moment to moment: chess boards, road conditions, the words already written in a sentence. (If you only add the "look at the situation first" part, you get a contextual bandit, which is a halfway house between bandits and full RL. If your actions also change the next situation, you've left bandit territory entirely.)

2. They only understand immediate feedback. Every update reacts to the reward right now for the action just taken. But in most interesting problems, consequences arrive late:

A chess move that quietly weakens your position may not cost you the game for 20 turns.
A financial decision may not show its results for months.
A word you choose early in a sentence shapes everything after it.

The machine would have to guess which of its past actions deserves the blame or credit. It has no mechanism for that. This is the famous credit assignment problem, and it is the gap the next era of RL sets out to fill. (Samuel's checkers program from Blog 4 was already sniffing around this problem. Its temporal-difference trick gets its full moment later in the series.)

Quick recap

Question: what is the smallest structure that lets a machine improve from feedback?
Tsetlin (1961): a hallway of rooms. Reward = go deeper, penalty = step back. More rooms = more stability, but also more stubbornness.
Variable-structure automata (1963-1974): delete the rooms, keep a probability per action, and nudge it up or down with feedback. This is the seed of policy gradients.
Both are ways of playing the multi-armed bandit, the cleanest version of exploring vs. exploiting.
Regret (reward lost vs. always playing the best arm) is the scoreboard. Linear = failing, logarithmic = best possible.
The toolkit: ε-greedy (simple, permanent exploration tax), UCB (optimism about what you haven't tried), Thompson sampling (explore in proportion to doubt, great in practice), gradient bandits (learn preferences, the cousin of policy gradients).
In practice: a bandit beat a fixed A/B split by roughly 4x in lost conversions in our simulation, and a constant step size won back ~770 reward after the world flipped.
Blind spots: no awareness of the situation, and no way to handle delayed rewards.

Up next

So machines can now adapt reliably to noisy feedback. But what if the feedback comes late, and what if the "learner" isn't a tidy algorithm at all, but a neuron? In the 1970s, Harry Klopf proposed exactly that: neurons as tiny, pleasure-seeking units. Around the same time, Paul Werbos quietly described an idea that would later be famous as backpropagation.

Next: Blog 6 - The "Hedonistic" Revival: Klopf's Pleasure-Seeking Neurons and Werbos's Hidden Backpropagation (1972-1980).

RL 4: Early heuristics and the birth of Temporal Difference learning (1959–1968)

Mitansh Gor — Fri, 25 Sep 2026 15:29:09 +0000

TL;DR

Bellman's math told you how to act perfectly — on paper. 1959 computers had neither the memory nor the map of reality to run it. So a few stubborn engineers cheated their way to something that actually worked.

Arthur Samuel (1959) swapped an impossible checkers lookup table for a scoring function — a formula with adjustable weights, trained by playing itself. His real breakthrough wasn't the 1962 headline win (which, spoiler, gets more impressive the more you learn how it actually went). It was an idea called Temporal Difference (TD) learning: don't wait for the game to end — learn from the gap between what you predicted a moment ago and what you predict now. No rulebook required. That's model-free learning, and it turns out to be the exact same rule psychologists later used to explain Pavlov's dogs.

Donald Michie's MENACE (1961) did something similar with 304 matchboxes and coloured beads — but learned a policy ("what should I do?") instead of a value ("how good is this?"). Value-learning and policy-learning are the two ancestors of basically every RL algorithm running today.

Minsky (1961) put a name on why any of this was hard in the first place: the credit-assignment problem.

Michie's BOXES (1968) removed the last training wheel — a human teacher — and balanced a physical pole using nothing but "it fell over" as feedback.

Every system in this post assumes the world is reliable. Blog 5 breaks that assumption.

The blueprint had a bill attached

Bellman's equation is one of those rare results that's simultaneously beautiful and completely useless.

Beautiful, because it tells you the exact optimal move, always. Useless, because to run it you need two things handed to you first: every possible state of the world, written down, and the exact odds of moving between them, also written down.

Neither exists. Computers in 1959 topped out around 32,768 words of memory — smaller than a single photo on your phone today. Checkers alone has roughly 500 billion possible positions. And the "odds of every outcome" problem is even worse than the memory one — more on that in a second.

So the people actually trying to build this did what engineers always do when elegant theory meets a real budget: they cheated. One of the most important cheats in AI history started with a man, a room-sized vacuum-tube computer, and a game of checkers.

Three walls, one problem each

Picture yourself in 1959, staring at Bellman's equation, actually trying to build the thing. You'd hit these three walls, in roughly this order, and none of them have an easy way around them.

Wall 1 — Memory. Store every situation in a table and the table explodes. Tic-tac-toe: ~5,000 positions, fine. Checkers: ~500 billion. Chess: ~10⁴⁵. Bellman called this the curse of dimensionality — add one variable, and your table doesn't grow, it detonates. Lesson: you can't memorise your way to intelligence.

Wall 2 — No rulebook. Bellman's math needs P(s'|s,a) — the odds of every outcome, for every action, in advance. Nobody has that spreadsheet. A self-driving car has no table for "will this pedestrian step off the curb." Reality just doesn't ship with its own source code.

Wall 3 — The score becomes the goal. Turn "behave well" into a number, and machines will take that number extremely literally. Reward a robot vacuum for movement, and it'll ram the same wall forever, racking up points and cleaning nothing — and from its own perspective, winning. Today we'd call this reward hacking. In 1959 it didn't have a name yet, just a very confused engineer staring at the output.

Samuel is about to dent Walls 1 and 2. Michie dents Wall 1 from a totally different angle. Wall 3 is still standing today — it's a large chunk of why "AI alignment" is now a job title.

Arthur Samuel and the machine that learned checkers

In the 1950s, the prevailing wisdom was blunt: computers execute, they don't learn. A program does exactly what it's told, forever, full stop.

Arthur Samuel, an IBM engineer, didn't buy it. He picked checkers — not chess — as his test case. Deep enough to need real strategy, small enough that a 1950s machine stood a chance. He started in 1952 on the IBM 701 and by 1959 had published work that put the phrase "machine learning" into circulation for the first time.

His machine, the IBM 704, maxed out at 32,768 words of memory. Storing every checkers position wasn't "hard" — it was short by seven orders of magnitude. So instead of trying to be comprehensive, Samuel made the machine opinionated.

A scoring function instead of a lookup table

Throw away the table. Replace it with a formula that squeezes an entire board into one number: high = "good for me," low = "bad for me." The machine has no idea why — it just needs a number it can push upward.

If blog 3's V(s) was an exact number, computed by sweeping every state until the answer converged — this is the same object, wearing a disguise. Samuel's scoring function is V(s). The difference is that nobody can compute it exactly here, so the machine has to guess it, and improve its guess through play instead of through a formula that already has the whole map.

That number was built from hand-picked features — piece count, king count, board control, mobility — each with a weight saying how much the machine currently trusts it. Score = features × weights, summed.

Here's the part that still holds up today: the weights weren't fixed. A feature that kept predicting wins got trusted more. One that kept misleading the machine got trusted less, or dropped entirely and swapped for a new candidate. The machine wasn't just learning checkers — it was learning what was worth paying attention to. That's the same basic instinct behind feature learning in neural networks, six decades early.

Self-play

Samuel then had the program play itself. A "student" copy tries tweaked weights against a "teacher" copy running the current best settings. Student wins consistently → student becomes the new teacher → repeat.

This loop is, structurally, identical to what DeepMind ran in 2016 to build AlphaGo. The hardware went from vacuum tubes to TPU pods. The logic didn't change at all.

The famous win (and the asterisk nobody mentions)

In 1962, Samuel's program beat a checkers player named Robert Nealey, and IBM's press release turned it into the first-ever headline about a machine beating a human at a strategy game.

What usually gets left out: Nealey wasn't state champion yet at the time (that came four years later), he beat the program in a rematch the following year, and by 1966 Samuel's program lost eight straight games to serious competition. None of that makes the work less real — it just moves the story from "magic trick" to "science": genuine learning, with a genuine, visible ceiling.

The ceiling Samuel could see from day one

Every strategic idea the program ever had came from a feature Samuel typed in by hand. If he never thought to encode "board control matters," the machine could never discover it on its own. It could re-weight human knowledge with superhuman patience — but it couldn't generate knowledge that wasn't already sitting in the box.

That single limitation defined the next thirty years of AI research, and it's exactly the problem deep learning was eventually built to solve: stop handing the machine features, let it find its own.

A name for the missing piece: Marvin Minsky, in 1961, pointed at exactly this gap and called it the credit-assignment problem — with only a final win or loss, which of a hundred earlier decisions actually deserves the credit? He specifically called out Samuel's scoring updates as the first real attempt at an answer: doling out partial credit one move at a time instead of waiting for the final verdict. That's the problem the rest of this post is trying to crack.

Memorise, or generalise?

Samuel's scoring function created a fork in the road that reinforcement learning is still walking down today.

His first instinct was rote learning: store exact positions and how they turned out, replay the good ones when they reappear. Works great for small games. But nudge a single piece and the "memory" is worthless — that exact position has never happened before, so there's nothing to look up. It's a lookup table wearing a trench coat.

Generalisation was the fix: describe a board by its features instead of memorising the whole thing. Now a position the machine has never seen still gets a sensible score, because it's described, not recognised.

Table lookup asks "have I seen this exact thing?" Generalisation asks "what is this like?" Only the second question scales.

Samuel's update rule for the weights:

Δw_i = α · [V_actual − V_predicted] · f_i

Δw_i — how much to nudge feature i's weight
α — learning rate: how boldly to react to new evidence
[V_actual − V_predicted] — the surprise
f_i — how present that feature was in this position

If you remember one sentence from this whole post, make it this: learning is the size of your mistake, multiplied by how willing you are to change your mind. Everything from here on is a variation on that one bracket.

Thinking deeper on a slower machine: alpha-beta pruning

One quick detour, and it earns its place here: self-play only works if you can play thousands of games against yourself, and thousands of games only fits into a reasonable afternoon if each individual game doesn't take forever to think through. That's the problem this section solves.

The IBM 704 was unbelievably slow by today's standards — looking twenty moves ahead by brute force would've taken longer than the universe has existed. So Samuel needed to skip most of the game tree without missing anything that mattered.

Credit where due: Samuel used alpha-beta pruning, but didn't invent it. John McCarthy proposed it at the 1956 Dartmouth workshop; Hart and Edwards formalised it in 1961; Knuth and Moore gave it full analysis in 1975. Samuel had a working version quietly running in the background — he just thought the learning parts were the interesting bit. (He was right.)

The idea: as the machine explores possible futures, it tracks the best result it can already guarantee (alpha) and the worst its opponent can already force (beta). The moment a branch is provably worse than something already locked in, the machine stops exploring it entirely — not "reads it faster," stops.

Restaurant analogy: someone tells you "the other place has a two-hour wait." You don't need the menu or the parking situation. You're not going. Branch closed.

Crucially, this is lossless — it finds the exact same best move as checking everything, just without wasting time on futures that can't matter. It's also a technique with real staying power: it was the backbone of Deep Blue, the chess machine that beat world champion Garry Kasparov in 1997, decades after Samuel quietly used it for checkers.

pruning comparision - Google Drive

drive.google.com

The idea that mattered most: learning from your own changing mind

This is the part that echoes into every modern RL system, and it's easy to undersell because it sounds so small.

The old assumption

The 1950s default: learning happens at the end. Play the whole game, see who won, then work out what went wrong. This became known as Monte Carlo learning — and it's brutally slow. You need a full game before learning anything, and if the game runs 100 moves, one noisy final signal has to somehow get distributed across all 100 decisions.

Samuel's question: why wait?

The machine already had a second opinion available, one move later, for free. If a position looked 70% winning after move 10, and only 50% winning after move 11 — something was already learned, right there, with no need to finish the game. Your own estimate moved, and estimates don't move for no reason.

Real-life version: you leave home expecting a 20-minute drive. Ten minutes in, you hit an empty motorway and revise to "7 more minutes." You haven't arrived yet, you don't know the true total — and you've unmistakably learned something the moment your prediction jumped.

That's the whole trick: learn from the gap between consecutive predictions, not from the final answer. It sidesteps Minsky's credit-assignment problem rather than solving it head-on — each move only ever has to explain the next move, not the whole game.

The formula

For a game like checkers, where nothing scores until someone wins:

V(S_t) ← V(S_t) + α [ V(S_t+1) − V(S_t) ]

V(S_t) — current guess about this position
V(S_t+1) — the guess one move later
[V(S_t+1) − V(S_t)] — the TD error: how wrong I just turned out to be
α — learning rate: too high and it's jittery, too low and it barely moves

In plain English: nudge what you believed toward what you now believe, in proportion to how surprised you are.

The general version below isn't a new idea — it's the exact same bracket with two extra pieces bolted on, so you can see them coming rather than guessing where they came from. It adds in any reward collected along the way, plus a discount for how much future value matters:

V(S_t) ← V(S_t) + α [ r_t+1 + γ V(S_t+1) − V(S_t) ]

Checkers collapses back to the simple version because nothing is scored mid-game (r = 0) and a win in 10 moves is worth exactly as much as a win now (γ = 1).

The déjà vu moment

That bracket should look familiar if animal learning is on your radar at all — and if you've been following this series, it should ring a very specific bell. This is the prediction error term flagged back in Blog 3, finally getting the job it was promised. Same idea, same shape, just a new name and a new job description: back then it fired once per trial, at the end. Here, it fires on every single move.

Pavlov's dogs weren't learning from bells — they were learning from being wrong about bells. A decade after Samuel, psychologists Rescorla and Wagner wrote down almost the identical rule to explain it: change your belief in proportion to your error. Different letters, same bracket — reality minus expectation, scaled by how much you're willing to update.

An IBM engineer trying to save vacuum-tube cycles, and two psychologists trying to explain salivating dogs, landed on the same equation from completely opposite ends of science, with zero contact between them. That's not a coincidence — it's a strong hint that prediction error is something close to fundamental about what learning actually is. (It gets better: in the 1990s, Wolfram Schultz found dopamine neurons firing in a pattern that looks almost exactly like a TD error signal. More on that in a later post.)

And notice what TD learning never needed: the rulebook Wall 2 said was impossible to get. Just the current state, the next state, and two estimates. That's model-free reinforcement learning — arguably the single most important idea in this post — quietly running on a vacuum-tube computer in 1959, almost thirty years before Richard Sutton formalised it as TD(λ) in 1988.

MENACE: reinforcement learning built out of matchboxes

Samuel had IBM's hardware. British researcher Donald Michie had a rather different constraint: no computer access at all. So in 1961, he built one out of matchboxes.

MENACE — the Matchbox Educable Noughts And Crosses Engine — used 304 matchboxes, each labelled with a tic-tac-toe position MENACE might face, and filled with coloured beads. Each colour maps to one legal move.

To move: find the matching box, shake it, pull a bead blind. Its colour is the move. Leave the box open — you'll need the trail later.

To learn: after the game, walk back along the trail of open boxes. Win → return the bead played, plus three more of the same colour. Draw → add just one. Loss → the bead simply isn't returned; it's gone. More beads of a colour means a better chance of drawing it next time.

Michie played roughly 220 games against it over a weekend. It went from flailing randomly to essentially unbeatable.

The detail worth noticing

Michie didn't load every box with the same number of beads. Early-game boxes started with about four beads per move; late-game boxes tapered down toward one. That's a deliberately engineered exploration schedule. Early moves are far from the outcome, so any one game barely tells you if they were good — you want MENACE to keep trying alternatives. Late moves sit right next to the result, so their feedback is trustworthy and can be locked in fast. That's the explore vs. exploit trade-off, solved in 1961 with nothing but bead-counting.

Why this is a plot point, not a party trick

Samuel's program learned to answer "how good is this position?" MENACE never asked that question — it has no concept of a position being worth 0.7. It only tracks "which move should I make more often from here?"

In blog 3's terms: MENACE is growing a policy — π, a state-to-action lookup — directly. It never computes a value for anything along the way. That's the split worth holding onto:

	Samuel	Michie
Learns	Values — how good is this state?	A policy — what should I do here?
Stores	Feature weights	Action probabilities
Modern descendant	Value-based methods — learn a score for each move, then just pick the best one (Q-learning, and its neural-network upgrade DQN)	Policy-gradient methods — skip the scoring step, learn the action probabilities directly (REINFORCE, and its more stable modern version PPO)

Two men, two continents, same decade — and they'd independently split reinforcement learning into the two halves it still has today. Modern RL doesn't pick a winner; it runs both at once. Actor-Critic methods (more on these in a later post) are literally a Critic estimating values (Samuel's job) paired with an Actor adjusting action probabilities (Michie's job), each sharpening the other.

MENACE also proves something worth sitting with: reinforcement learning isn't a property of silicon. It's a mathematical principle. Run it on vacuum tubes, neurons, or 304 matchboxes on a Sunday afternoon — what matters is the loop: act, observe the consequence, adjust, repeat.

It also hit the exact same wall Samuel did: every position needs its own box, and one extra square collapses the shelf. Same curse, cardboard edition.

Michie didn't stop there. In 1968, with R. A. Chambers, he took the matchbox idea into physics: BOXES, balancing a pole on a moving cart using nothing but a bang when it fell over. Widrow and Smith had balanced the same pole in 1964 — but with a human demonstrating the right move at each step. BOXES threw the teacher out entirely: no demonstration, just eventual failure walked backward through whichever boxes were open. The one new trick it needed was state aggregation — chopping a continuous space (pole angle, cart speed) into discrete chunks, since you can't label a matchbox for infinitely many positions. That's the field's first honest step toward function approximation — a plain-English way of saying "estimate the value instead of memorising it," the same escape hatch this whole post keeps circling back to. Cart-pole balancing went on to become RL's most reused benchmark ever since.

Two roads, one open question

By the late 1960s, two things were true at once. Samuel and Michie both had systems that genuinely learned from experience — no rulebook, no complete map of the world, and they visibly got better over time. But nobody could prove any of it. No convergence guarantee, no theorem saying "this reaches the optimal policy" — just clever hacks that happened to hold up on small problems.

Bellman's framework had the opposite problem: flawless proofs, unusable in practice.

Which set up the question the field spent the next twenty years chasing:

Can you keep Bellman's guarantees without needing Bellman's rulebook?

That question is the birth of model-free reinforcement learning — and chasing it eventually pushes the field toward systems that learn their own features instead of borrowing a human's. Which is to say: toward neural networks.

Worth sitting with for a second before we move on: the technique that trains most modern chatbots to be helpful — RLHF, reinforcement learning from human feedback — is a direct descendant of exactly this idea. No rulebook for "what makes a good response," just a reward signal and a model updating itself against its own predictions. The line from a matchbox in 1961 to a language model in 2026 runs straight through this post.

But not yet. First, someone has to ask a harder version of the question.

Coming up next

Samuel and Michie both had one thing quietly working in their favour: their worlds behaved. Move a checker, it stays moved. Draw a bead, that's the move you play. The environment was unknown, but at least it was reliable.

Now break that assumption. What if pressing the same button in the same situation works 70% of the time and fails the other 30%, for no reason you can see? A single result stops meaning anything — it might just be noise. You need to learn from distributions, not events, while still acting sensibly under real uncertainty.

That discipline was being built in parallel, largely by control theorists who weren't talking to the game-playing crowd at all.

Next up — RL 5: Learning Automata and Stochastic Environments (1961–1974). How do you make good decisions when the world itself won't give you a straight answer?

Series index:
Blog 1 — Biological foundations and the Law of Effect
Blog 2 — Classical conditioning and prediction
Blog 3 — Bellman, MDPs and Dynamic Programming
Blog 4 — Early heuristics and the birth of TD learning (this post)

RL 3: Bellman Equations and Markov Decision Processes (1950s–1960s)

Mitansh Gor — Fri, 18 Sep 2026 20:47:23 +0000

Where we left off

Two quick reminders.

Thorndike (1898) watched cats escape a puzzle box and gave us the Law of Effect: do something, get a good result, do it again. Get a bad result, stop. Learning is bookkeeping over consequences.

Blog 2 turned that idea into hardware. Shannon's mouse ran a maze and remembered the route. Minsky's SNARC strengthened the wires that led to good outcomes.

Both worked. Both were missing the same thing.

Thorndike's cat knew "pulling that loop felt good." It did not know it was three moves from freedom. Shannon's mouse could replay a path, but it couldn't tell you why one path was better than another.

Nobody had a word for this yet:

Value — a number attached to a situation that says how good does the future look from right here?

That one missing number is what this whole post is about.

Side note: the biologists were chasing the same number

Worth thirty seconds, because it makes the maths feel less alien.

Rescorla and Wagner (1972) showed that animals don't learn from repetition. They learn from surprise. If a bell already predicts food perfectly, adding a light next to the bell teaches the animal almost nothing about the light. There's no surprise left to learn from.

Their rule, in plain English:

new belief = old belief + (small step) × (what actually happened − what I expected)

That last bracket — reality minus expectation — is called prediction error. Hold onto it. It comes back in Blog 4 with a much bigger job.

(Yes, 1972 is out of order here. I'm putting it early because it explains "value" better than a grid does.)

Enter Richard Bellman

In 1949, a mathematician named Richard Bellman started working at RAND, a US think tank. His job was a specific shape of problem: you make a choice, the world changes, then you have to choose again. Missile guidance. Supply planning. Anything where today's decision quietly reshapes tomorrow's options.

He cracked it. Then he needed a name for it, So he picked two words that sounded harmless and industrial: Dynamic Programming.

(The story has probably been tidied up over the years — the dates don't quite line up — but the name stuck, and it's now one of the most important terms in computer science.)

Here's the problem he was actually solving.

The problem, in the form we'll use all post

Forget missiles. Here's the setup we'll use for everything that follows.

You're on a grid. You start in one corner. The goal is somewhere else. Every step costs you a little energy. Some cells are bad news. You want to reach the goal having collected as much reward as possible.

Easy to describe. Genuinely nasty to solve systematically.

The obvious approach is to list every possible path and pick the best. That works right up until it catastrophically doesn't. Paths multiply exponentially with grid size. 10×10 is already unpleasant. 100×100 is hopeless. Bellman later gave this failure mode a name — the curse of dimensionality — and we'll come back to it at the end, because it's the villain of the whole post.

So he needed a fundamentally different kind of reasoning.

Dynamic Programming: solve it backward, and only solve it once

Bellman's core insight is called the Principle of Optimality. Here it is in his words:

"An optimal policy has the property that whatever the initial state and initial decision are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision."

That's a mouthful. In human:

If the best route from A to C goes through B, then the B-to-C part of it must itself be the best route from B to C.

Because if it weren't — if there were a better way from B to C — you'd just swap it in and get a better A-to-C route. Contradiction. Done.

Sounds trivial. It isn't, because of what it licenses you to do:

You only ever have to solve each sub-problem once.

Once you know the best way from B onward, every route that passes through B can reuse that answer for free. No recomputation. That's Dynamic Programming: chop a giant sequential problem into overlapping sub-problems, solve them from the end backward, and cache the answers.

The backward part is the counterintuitive bit and it's worth sitting with. Bellman didn't ask "what's my best first move?" He asked "what's my best last move?" Then second-to-last. Then third-to-last, propagating backward until every square on the board has an answer.

This is backward induction, and it's not a historical curiosity — it is still, structurally, how modern RL agents plan.

Hold onto this: the future is easier to reason about than the past, because the future has an ending you can anchor to.

Five nouns you need before the equation shows up

So: five nouns first. Equation after. All five together are called a Markov Decision Process (MDP) — the formal container the maths lives in.

1. State — s
Where you are. On the grid, "row 3, column 4." In chess, the board position. In a delivery robot, position plus battery plus whether it's holding a package. The full set of states is written S.

2. Action — a
What you can do from here. On the grid: up, down, left, right. The full set is A.

3. Transition — P(s' | s, a)
Read it as: "the probability of landing in state s', given that I was in s and did a." The apostrophe just means "next."

4. Reward — R(s, a)
A number the environment hands you for doing a in s. This is where you, the designer, encode what "good" means. Reach the goal: +10. Take a step: −1. Fall in the pit: −100.

Get this wrong and your agent will cheerfully optimise the wrong thing. Reward design is 90% of applied RL pain, and I'm not going to pretend otherwise.

5. Policy — π (pi)
Your strategy. A rule that maps state → action. "When in this square, go right." That's it. A policy isn't a plan or a path — it's a lookup table of what to do anywhere you might find yourself.

The whole field, in one sentence: an MDP describes the world; a policy describes your behaviour in it; and the rest of RL is the search for the best policy.

The one assumption holding all of this up

There's a condition the whole framework quietly depends on, and it's called the Markov Property:

The future depends only on the present state — not on the history of how you got there.

First reaction to this is usually: that's obviously false, history matters all the time. Fair. But that's not quite what it says.

It says history must already be baked into the state.

If your robot's battery level affects the next decision, then battery level belongs in the state definition. Once it's in there, you don't need to replay the last 50 timesteps — you just look at where you are now.

Two quick examples to make it concrete:

Chess is Markov. The board position tells you everything. It doesn't matter whether you reached it through a brilliant sacrifice or a series of blunders — the position is the position.
Poker is not Markov if your state is just "my cards." Whether your opponent has been bluffing all night genuinely changes what you should do. Fix it by expanding the state to include betting history. Now it's Markov again — and much bigger. (Notice the trade you just made. That's foreshadowing.)

The neat way to say it: the state is allowed to have memory. The policy isn't.

This assumption is exactly what makes RL computable. Without it, an agent would have to carry and process its entire past at every step. With it, a policy is just a lookup: current state in, action out.

One more assumption, and it's a big one. For this entire post, the agent is assumed to already know P and R. It knows the physics of the world and the reward structure before it takes a single step. That's called model-based RL, and it's what makes the maths clean here.

It is also completely unrealistic, and Blog 4 takes a sledgehammer to it.

Return and γ: why "how good" needs a definition

One more thing before the equation. If value means "how promising is the future from here," we need to say what the future means numerically.

Add up all the reward you'll collect from now until the end. That total is called the return.

Except there's a problem: if the task never ends, that sum runs to infinity, and "infinity" is a terrible thing to compare against another infinity. So Bellman introduced a discount factor, γ (gamma), a number between 0 and 1. Reward one step away is multiplied by γ. Two steps away, γ². Three steps, γ³. And so on.

G_{t} = R_{t} + γ R_{t + 1} + γ^{2} R_{t + 2} + γ^{3} R_{t + 3} + \dots

Two things fall out of this, and both matter:

Mathematically: the sum now converges. It's a geometric series. No infinities.
Behaviourally: γ is a personality dial.
- γ near 0 — a myopic agent. Only right now exists. It will grab the nearest +1 and ignore a +100 two steps away.
- γ near 1 — a patient agent. Happy to eat a −1 today for a +100 later.
- γ = 0.9 — a reasonable default that says "about ten steps of foresight."

It's compound interest, run backward. A reward ten steps away at γ = 0.9 is worth about 35% of its face value today.

Value: the number Thorndike's cat never had

Now we can define the thing this whole post is chasing.

V(s) — the value of state s — is the expected return you'll collect if you start in s and behave well from there on.

That's the number the cat didn't have. The cat knew "this felt good." A value function knows "this square is worth 7.1, that one's worth 5.4, so go left."

And that's the whole trick: once every square has a number, choosing an action stops being a search problem and becomes a comparison. Look at the neighbouring numbers. Walk toward the big one. Done.

The Bellman Equation

In his 1957 book Dynamic Programming, Bellman wrote down the recursion that ties all of this together:

V (s) = a max [R (s, a) + γ s^{'} \sum P (s^{'} ∣ s, a) V (s^{'})]

In one sentence:

The value of where you are = the best immediate reward you can grab + the discounted value of wherever you end up next.

Every symbol is one of the five nouns you already know:

Piece	Reading
`V(s)`	how good it is to be here
`max_a`	you, choosing. Try every action, keep the best
`R(s, a)`	what you get right now
`γ`	how much you care about later
`∑ P(s':s,a) · V(s')`	the world, responding.Average over every place you might land, weighted by likelihood

Two things I want to flag, because they're where people quietly lose the thread.

First: max and ∑ are doing opposite jobs. The max is the agent choosing. The ∑ is the world rolling dice. You control your action. You do not control the outcome. If the transitions were deterministic, that ∑ would collapse to a single term and disappear — it only exists because the world is uncertain.

Second: V(s) appears on both sides. That's not sloppy notation, it's the entire idea. The equation is self-referential — the value of a state is defined in terms of the values of other states.

Which raises the obvious question: if V is defined in terms of V, how do you ever compute it?

You guess, then you improve. Start with V = 0 everywhere (a wrong but harmless guess), apply the equation, get better numbers, apply again. The values stop changing when they're all consistent with each other. Mathematicians call that a fixed point — the place where applying the rule doesn't change anything anymore.

That "keeps changing until it doesn't" process is the entire computational game. And it's easier to believe once you've watched it happen, so let's watch it happen.

Let's actually put numbers on the board

Here's the smallest example that shows the real behaviour. A corridor, four squares, then the goal:

[ S1 ][ S2 ][ S3 ][ S4 ][ GOAL ]

Rules:

Actions: move left or move right. Deterministic — no ice.
Every move costs −1.
Stepping into GOAL pays +10.
γ = 0.9.
GOAL is terminal, so V(GOAL) = 0.

Work backward, exactly as Bellman said to.

S4 is one step from GOAL: V(S4) = −1 + 10 + 0.9 × 0 = 9.00
S3 is one step from S4: V(S3) = −1 + 0.9 × 9.00 = 7.10
S2: V(S2) = −1 + 0.9 × 7.10 = 5.39
S1: V(S1) = −1 + 0.9 × 5.39 = 3.85

[ 3.85 ][ 5.39 ][ 7.10 ][ 9.00 ][ GOAL ]

Look at what happened. The goal's reward leaked backward through the corridor and left a slope behind it. The agent doesn't need a map, a plan, or a search. It just walks uphill. The value function turned a planning problem into a gradient you can follow like a scent trail.

Animated_heatmap_of_the_x_gr.mp4 - Google Drive

drive.google.com

Now watch it converge from nothing

That was the answer. Here's the process — starting from V = 0 everywhere and sweeping the equation across all four states repeatedly:

Sweep	V(S1)	V(S2)	V(S3)	V(S4)
0	0.00	0.00	0.00	0.00
1	−1.00	−1.00	−1.00	9.00
2	−1.90	−1.90	7.10	9.00
3	−2.71	5.39	7.10	9.00
4	3.85	5.39	7.10	9.00
5	3.85	5.39	7.10	9.00

Three things worth noticing here, and honestly this table is the most important object in the post:

Information travels exactly one square per sweep. Sweep 1, only S4 knows the goal exists. Sweep 2, S3 finds out. It's a wavefront moving backward.
The early numbers are hilariously wrong. At sweep 3, S1 thinks it's worth −2.71 — it can only see step costs and no payoff yet. It's a pessimist with incomplete information. It gets over it.
You don't need a stopping rule, you need a stopping condition. When a full sweep changes nothing, you're done. That's the fixed point, made of actual numbers.

Howard's Policy Iteration: from knowing values to having a strategy

Bellman gave us the value of every square. But there's a subtly separate question: how do you systematically build the strategy — the policy — that goes with it?

Ronald Howard, in his 1960 monograph Dynamic Programming and Markov Processes, noticed the problem is circular:

To compute V(s), you need to know which policy π the agent is following.
To find the best π, you need to know V(s).

Classic chicken and egg. Howard's answer: stop trying to do both at once. Alternate.

Step 1 — Policy Evaluation: "how good is my current strategy?"

Freeze the policy. Don't try to improve it. Just ask: if I followed this exact strategy forever, what would each state be worth?

V^{π} (s) = R (s, π (s)) + γ s^{'} \sum P (s^{'} ∣ s, π (s)) V^{π} (s^{'})

Notice the max is gone. There's no choosing here. π(s) tells you what to do; you're just measuring the consequences. This isn't optimisation, it's scorekeeping.

Step 2 — Policy Improvement: "could I do better?"

Now take those scores and ask, at every state: given what I now know things are worth, is there an action better than the one my policy currently prescribes? If yes, switch to it.

π^{'} (s) = ar g a max [R (s, a) + γ s^{'} \sum P (s^{'} ∣ s, a) V^{π} (s^{'})]

arg max vs max, since this trips everyone up: max returns the best value. arg max returns the action that achieved it. Evaluation wants the number; improvement wants the move.

And repeat

Evaluate. Improve. Evaluate. Improve. Stop when an improvement step changes nothing.

Howard proved two things about this loop that are genuinely reassuring:

The greedy step never makes the policy worse. Every improvement is an improvement or a tie. It can't wander off toward a worse policy — the local, greedy move is globally safe here. (That's a strong guarantee, and one that quietly evaporates once we start using neural networks in later posts.)
On a finite MDP, it terminates in a finite number of iterations. There are only finitely many policies, you never repeat one, so you must stop. Usually in a handful of rounds.

And here's the part that should give you a small jolt: that two-role split — one part measuring, one part deciding — is the direct ancestor of the Actor–Critic architectures we'll get to in Blog 7. The Critic does Policy Evaluation. The Actor does Policy Improvement.

That structure wasn't invented for deep learning. It was sitting in a 1960 operations research monograph the whole time.

Value Iteration: the impatient version

Policy Iteration is a bit fussy. It insists on fully evaluating a policy — running evaluation to convergence — before it'll consider improving anything.

Value Iteration says: why wait? Fold the improvement directly into the update.

V (s) \leftarrow a max [R (s, a) + γ s^{'} \sum P (s^{'} ∣ s, a) V (s^{'})]

The max is back, and it's inside the loop. Every single update implicitly re-decides the best action. No separate improvement phase exists.

Value Iteration never stores a policy at all. It just hammers on the value function until it settles, and then you read the policy off: stand in each state, look at the neighbours, take the action pointing at the biggest number.

(That sweep table you looked at earlier? That was Value Iteration. You've already seen it run.)

Policy Iteration vs Value Iteration, side by side

Same equation, same destination, different temperament.

Policy Iteration is the coach who watches the entire game. Films it. Writes a 40-page report. Rewrites the playbook from scratch before the next match. Few iterations, each one expensive and each one a big leap.

Value Iteration is the coach who stops play after every snap. "Stop — standing three feet left would've been worth two more points." Cheap per update, but it needs a lot of them. Constantly nudging everyone's understanding of the field.

	Policy Iteration	Value Iteration
Explicit policy?	Yes, maintained separately	No, implicit in the values
`max` in the update?	Only in the improvement step	Every update
Cost per iteration	High (full evaluation)	Low (one sweep)
Iterations needed	Few	Many
Terminates when	Policy stops changing	Values stop changing
Best when	State space is small and exact	State space is large or approximate

Which should you use? Small, well-defined state space where you want exactness — Policy Iteration. Large or approximate — Value Iteration.

And worth flagging for later: almost every modern RL algorithm is spiritually a descendant of Value Iteration. They update values continuously and never wait for a full evaluation to finish. Q-learning is Value Iteration with the model ripped out. DQN is Q-learning with a neural network glued on.

The curse they named but couldn't escape

Now the bad news, and Bellman himself is the one who delivered it.

Both algorithms require sweeping over every state in S. Every single one. Every iteration.

4-square corridor: 4 states. Trivial.
10×10 grid: 100 states. Fine.
Chess: roughly 10⁴⁴ positions.
Go: more legal positions than there are atoms in the observable universe.

Bellman named this the curse of dimensionality, in the same 1957 book that gave us the equation. Add one variable to your state description and the state space doesn't grow — it multiplies. A robot tracking position, velocity, battery, and grip status doesn't have four problems. It has (positions × velocities × battery levels × grip states) problems.

And remember the poker example from earlier? Fixing the Markov violation by stuffing betting history into the state made the state space explode. That's the curse arriving in person. Making a problem Markov and making it small are usually opposing goals.

This is why RL went quiet for decades after Bellman. It wasn't that the theory was shaky. The theory was perfect and the computer was too small. Dynamic Programming solves the structure of sequential decision-making completely — it just needs a table with one row per state, and sometimes that table can't exist.

The escape route — stop storing V(s) in a table and start approximating it with a function — wouldn't properly arrive until DeepMind's DQN in 2013. But the problem was named here, in 1957. Nearly everything between then and now is an attempt to get around it.

Why 1957 mathematics is running inside your 2026 chatbot

It sounds like a stretch that equations written for missile guidance underpin modern reasoning models. It isn't.

When a model like o1 or DeepSeek-R1 works through a hard problem, it isn't just emitting the most likely next token. It's exploring reasoning paths, scoring how promising each one looks, and abandoning the ones heading toward a dead end.

Read that again with this post's vocabulary loaded:

A partial chain of reasoning is a state.
The next thing to write is an action.
"Is this line of thinking going anywhere?" is a value estimate.
Backtracking out of a bad path is backward induction — the same move Bellman made when he asked about the last step instead of the first.

The state space changed from grid squares to token sequences. The tables became neural networks. The core question — how good is this situation, really? — is unchanged since 1957.

Six things to keep

If every equation falls out of your head by Thursday, keep these:

The world is states and actions — that's an MDP.
Rewards define what "good" means — and you're the one writing them, so be careful.
Value is a score for how promising the future looks from here — the number Thorndike's cat never had.
The Bellman Equation makes future reward flow backward through states, leaving a slope you can climb.
A policy is just a rule for picking actions — a lookup table, not a plan.
Iteration fixes the circularity. Guess, measure, improve, repeat, stop when nothing changes.

If Bellman clicks, the rest of RL is refinement.

What's coming next

Everything in this post rested on one assumption I flagged and then leaned on hard: the agent already knows P and R. It knows the physics. It knows the payoffs. It's not learning about the world — it's calculating against a world it already has a complete map of.

Real agents don't get that map.

In Blog 4 — Early Heuristics and the Birth of Temporal Difference Learning (1959–1968), that assumption gets torn up. We'll meet a program that had to work out what positions were worth by playing, not by computing — and we'll finally see what happens when you take Rescorla and Wagner's "learn from surprise" idea and let it fire on every single step instead of once per trial.

Remember the prediction error term from the top of this post? It's about to get a job.

The equation was ready. The machine was next.

Next: Blog 4 — Early Heuristics and the Birth of Temporal Difference Learning (1959–1968).

Previously: Blog 1 — Biological Foundations and the Law of Effect (1898–1949) · Blog 2 — The First Machines.

RL 2: The first physical and computational RL machines(1948–1954)

Mitansh Gor — Sat, 12 Sep 2026 05:57:48 +0000

Quick recap, if you're just arriving: Blog 1 showed that every core idea in reinforcement learning was discovered by someone watching animals, not computers. Thorndike's cats taught us that learning is selection, not insight. Pavlov's dogs taught us that a signal can carry information about the future. Skinner's pigeons taught us that big behaviors are built from small rewarded steps. Hebb's neurons taught us that learning lives in the strength of a connection.

Four beautiful observations. Not one of them tells you how to build something that does this.

This is the decade where people tried to build it anyway. What followed was ten years of beautiful, clunky, brilliant hardware — machines that stumbled through mazes, adjusted their own wiring, and learned, in the most primitive sense, from their mistakes. None of the people building them knew they were inventing Reinforcement Learning. They were just trying to make something move on its own.

The Missing Link: Why "a signal predicts the future" Needed a Number

Before we jump to the machines, one 20-second detour — because it's the cleanest bridge between Blog 1 and everything below.

Pavlov noticed his dogs salivated at footsteps, before food even showed up. Nice story. But it doesn't tell you how much the dog should update its expectation each time, or why the association eventually stops getting stronger.

Decades later — 1972, well after everything in this post — psychologists Robert Rescorla and Allan Wagner finally wrote that down as a formula:

Δ V = α β (λ - V)

In plain words: how much you learn from an event equals how surprising it was. V is what you currently expect, λ is what actually happened, and (λ - V) is the surprise — the gap between prediction and reality. If a bell always predicts food, eventually there's no surprise left, and no more learning happens. That gap term is the whole engine.

Why mention a 1972 psychology paper in a post about 1948–1954 engineering? Because the people you're about to meet — Wiener, Turing, Minsky, Shannon — independently backed into the exact same idea from a completely different direction: engineering, not biology. None of them had read Pavlov's fine print. They just kept discovering, on their own, that intelligence seems to boil down to measuring a gap and closing it. Keep that gap-closing idea in your head — it's the thread connecting every section below.

The Cybernetic Spark: Wiener's Feedback Loops (1948)

In 1948, mathematician Norbert Wiener published Cybernetics: Or Control and Communication in the Animal and the Machine, and made a claim that was radical for its time: the same mathematical principle governs both living organisms and machines — negative feedback.

Forget dogs and food for a second. Think of a thermostat. It doesn't "know" temperature in any deep sense — it just tracks one number obsessively: the gap between where it is and where it's supposed to be.

D = T - S

Where T is the target state and S is the current state. If D ≠ 0, the system fires a correction to close the gap. That's it. That's the whole idea.

This is exactly the Rescorla-Wagner gap from above, just wearing an engineer's clothes instead of a psychologist's. D here is the direct ancestor of the Temporal Difference (TD) error you'll see in modern RL — the signal that tells an agent "something's off, adjust." Every gradient update in every deep RL system running today is, underneath the math, a Wiener-style error minimization.

Wiener's punchline: Intelligence isn't magic. It's error minimization on a loop. If you can define a goal and measure your distance from it, a machine can "learn" to close that distance.

So Wiener gave the field a drive — a reason to move, a number to chase to zero. But a drive isn't a mechanism. It doesn't tell you what happens inside the machine when it's wrong versus when it's right. That's exactly what Alan Turing was working out, in the very same year, from a completely different angle.

The Turing Blueprint: Pain, Pleasure, and the First Neural Network on Paper (1948)

Turing's 1948 paper Intelligent Machinery introduced the P-type (Pain-type) Unorganized Machine, and reading it today feels like finding the first design document for a neural network, forty years too early.

Turing's argument was blunt: a human infant's cortex is mostly a random, disorganized network that only becomes useful through experience. So why not build the machine equivalent? He proposed a network built from NAND gates — think of these as the smallest possible decision units, each taking two inputs and spitting out one output based on a simple rule. Each gate could sit in one of two internal "configuration states," and that state is what determined how the gate behaved.

The learning happened through two signals, and this is the part that matters:

Pain — when the machine got something wrong, the gates that had just fired got scrambled at random:

C_{next} = RandomSample (C)

Pleasure — when the machine got something right, those same configurations froze in place. No more random reshuffling:

P (Δ C ∣ Pleasure) = 0

So: wrong answer, shake things up. Right answer, lock it in. It's almost embarrassingly simple — which is exactly why it's important.

Turing also spotted the obvious problem immediately: pure random shuffling doesn't scale. If a machine has n units, each with k possible states, the number of configurations to search through is k^n — a number that explodes into uselessness almost immediately, even for tiny machines.

His fix: bring in a teacher. Instead of letting the machine flail randomly forever, a teacher hands out Pleasure signals early to nudge it toward useful sub-behaviors, and then Pain prunes away the remaining mistakes. That's not just a clever patch — it's the seed of Supervised Fine-Tuning (SFT) and Imitation Learning, ideas that wouldn't get their modern names for another fifty-plus years. Turing had quietly moved the burden of "being smart" off the programmer's shoulders and onto the environment's.

His paper sat mostly unread for decades. But look at the shape of it: a randomly wired network, shaped over time by reward and punishment, converging on useful behavior. Every RLHF pipeline running behind a modern chatbot is, structurally, still running Turing's 1948 loop.

Wiener gave us the why — close the gap. Turing gave us the what happens inside — freeze on success, scramble on failure. What nobody had shown yet was a machine that could do this outside of a chalkboard, with actual physical parts that changed themselves. That's where Marvin Minsky comes in.

Minsky's SNARC: The First Machine That Rewired Itself (1951–1954)

While Turing's ideas stayed on paper, Marvin Minsky and his Princeton colleague Dean Edmonds went to the workshop and actually built something.

In 1951, they built the SNARC — Stochastic Neural Analog Reinforcement Calculator — the first machine to physically implement Hebbian learning (remember Blog 1: neurons that fire together, wire together) combined with reinforcement, in real hardware. Minsky later wrote it up in his 1954 thesis.

The SNARC simulated a rat finding its way through a maze using 40 artificial synapses. Each "synapse" was a vacuum tube paired with a potentiometer — picture a volume knob, a simple dial that changes how much resistance flows through a circuit. That dial's position was the connection's strength, standing in for what we'd now call a "weight."

Here's the learning loop, in plain terms:

A signal representing the "rat" travels through the network, picking a path.
If that path leads to reward, the potentiometers ("volume knobs") along that path get turned to lower resistance — meaning that path becomes electrically easier to travel next time.
If the path leads nowhere, those knobs stay put or drift the other way.

Notice what's happening here: this is credit assignment, done with actual electricity. The machine had no rule anywhere that said "this specific connection caused the reward." It used the reward signal traveling backward through whichever path was active to figure out which knobs to turn. That's structurally the same job that backpropagation does in a modern neural network — just with copper and vacuum tubes instead of calculus.

The SNARC couldn't scale — 40 synapses is barely a network by today's standards, and analog parts drift and degrade over time. But it proved something that had never been physically shown before: a machine can change its own internal wiring in response to reward, with no one programming the change directly.

That single idea — connections that adjust themselves because of reward — is the founding premise of every neural network trained with RL today.

So now we've got a drive (Wiener), a mechanism (Turing), and proof that self-adjusting hardware works (Minsky). One year later, Claude Shannon showed what happens when you point that same idea at something a person can actually watch move.

Claude Shannon's Theseus: Learning You Can See (1952)

Shannon's contribution was the most tangible of the whole decade. In 1952, he built Theseus — a copper mouse that could navigate a 5×5 maze, controlled by a cabinet of 75 telephone relays sitting underneath.

Here's the trick: the mouse itself had no brain. The relays — think of a relay as a mechanical switch that can remember whether it's "on" or "off" — were the brain. Each of the 25 cells in the maze corresponded to a relay setup that remembered which directions had already failed from that spot. Hit a wall, and the relay for that direction-at-that-position flipped off, so the mouse tried something else next time. Find a working path, and those relay settings locked in for good.

The payoff: drop Theseus anywhere in a maze it had already solved, and it walked straight to the goal, no hesitation. Drop it somewhere new, and it explored from scratch — then remembered that too.

What Shannon had actually built was a physical lookup table: a direct map from state (position in the maze) to action (which way to go), stored as the mechanical position of 75 relays. This is the hardware great-grandparent of what's now called a Q-table.

But the genuinely clever part was the "anti-neurotic" circuit. Shannon noticed that a strategy based purely on "eliminate what failed" could trap the mouse in an infinite loop — try North, fail, try East, fail, loop back to North forever, repeat. His fix: a circuit that detected this looping behavior and injected a random direction change to break it.

This is, as far as anyone can tell, the first deliberate hardware solution to exploration vs. exploitation — the tension that sits at the center of nearly every RL algorithm ever written. In plain terms: should the mouse keep using the move it already knows works (exploit), or try something new in case there's a better option (explore)? Shannon's answer was a random kick when stuck. Modern RL answers with names like epsilon-greedy (occasionally pick a random action on purpose) or entropy bonuses (reward the agent slightly for staying unpredictable). Same problem, seventy years of better tools.

Theseus proved something important: "learning" could be reduced entirely to hardware state changes. No probability distributions, no gradients — just relays flipping. Intelligence as a lookup table.

The Bridge (1954–1957): From Wires to Equations

By the mid-1950s, the hardware approach was hitting a wall. Shannon's mouse could solve one specific maze. Minsky's SNARC topped out at 40 synapses. Turing's ideas mostly lived on paper. Every one of these machines was an impressive, custom-built solution to one specific problem — and none of them generalized.

Richard Bellman, among others, got impatient with that. Building a maze-solving mouse was a great parlor trick, but it wasn't a theory. What he wanted was a general rule — something that could handle any problem made of a long chain of decisions, no matter what the environment looked like underneath.

The question shifted from "can we make this specific thing work?" to "can we prove the mathematically best way to act, in general?"

Bellman's answer became the Principle of Optimality and the Bellman Equation: the idea that the value of being in a state is just the immediate reward, plus the (slightly discounted) value of wherever you end up next. He took the mechanical "vibes" of the SNARC and Theseus and translated them into a single recursive formula — one equation that compresses an agent's entire future into a present-tense number.

That equation, and the computational nightmare it revealed (Bellman's own term for it: the Curse of Dimensionality), is where Blog 3 picks up. For now, the point is simpler: after a decade of wiring things together by hand, the field realized it needed math to go any further.

The wires were beautiful. But equations scale.

The Decade in One Frame

Zooming out, here's what this era actually built — not a summary, a thesis:

Wiener (1948) gave learning a drive: minimize the gap on a feedback loop.
Turing (1948) gave learning a mechanism: reward freezes, punishment randomizes.
Minsky (1951/54) gave learning physical weight: the first adjustable synapses that existed as hardware, not theory.
Shannon (1952) gave learning memory: state-action mappings stored in the physical position of relays.
Bellman (1957) gave learning math: a recursive formula that would eventually unify everything above it — that's Blog 3.

In under a decade, "learning" went from a biological observation about cats and pigeons to a wired, probabilistic, physically real process you could point to on a workbench. The machines were small, fragile, and each one could only do exactly one thing. But the ideas inside them were load-bearing — every one of them is still holding up the RL systems built today.

RL 1: Biological foundations and the "Law of Effect" (1898– 1949)

Mitansh Gor — Wed, 02 Sep 2026 22:58:37 +0000

Before GPUs. Before neural networks. Before transistors were even a rumor.

There was a hungry cat in a wooden crate, trying to get to a piece of fish.

The main character of this era isn't an engineer. It's a loose group of psychologists — some of whom actively disliked each other's ideas — poking at animals to answer one question: why do living things do the things they do?

They never wrote a line of code. They were not trying to build AI. And yet, in the fifty years between 1898 and 1949, they collectively reverse-engineered the core loop that every modern reinforcement learning system still runs on.

This post is that story. No math yet — I promise. Just the loop, and the four people who found its pieces.

First, the thing we're building

Let me give you the shape of the answer before the story, so you know what you're collecting.

Reinforcement learning describes any system that learns by doing stuff and seeing what happens. That's it. Not by being shown correct answers — by trying, failing, and adjusting.

We'll call the learner the agent (the cat, the rat, the robot, the model). Everything outside it is the environment (the box, the room, the game). The loop runs like this:

The agent observes its state — the situation it's currently in.
It picks an action.
The environment responds with a reward — a number saying "that was good" or "that was bad."
The agent lands in a new state, and the loop repeats.

Two more, and they're the ones that do the heavy lifting later.

The agent needs a policy: a strategy for choosing actions. Not a fixed script — a rule of thumb that says in this kind of situation, do this kind of thing.

And it needs a sense of value: how good a state is, based not on the reward sitting in it right now, but on everything it tends to lead to. An empty hallway is worth nothing on its own. An empty hallway with the kitchen at the end of it is worth quite a lot.

Six words: agent, state, action, reward, policy, value. Every single one of them was discovered by someone studying animals, decades before anyone could program a computer.

Let's go get them.

1898 — Thorndike's Cats and the Law of Effect

In 1898, a graduate student named Edward Thorndike was annoyed.

The animal literature of his day was full of charming anecdotes — dogs who understood latches, cats who figured out doorknobs. Thorndike's suspicion was that people were flattering their pets. Animals weren't reasoning. They were doing something else, and nobody had bothered to measure it.

So he built the puzzle box.

The setup is almost comically simple. A hungry cat goes in a small wooden crate. The door opens only if the cat pulls a loop of string, or presses a lever, or steps on a pedal. A piece of fish sits outside, in plain view. Then Thorndike started a stopwatch.

Trial one is chaos. The cat claws the bars. It shoves its paws through every gap. It bites things, yowls, thrashes at anything loose. After a few minutes of pure flailing, it hits the lever by accident. The door swings open. Fish.

Trial two: slightly less flailing.

Trial twenty: the cat walks in, hits the lever, and strolls out.

Here's what Thorndike noticed, and it's the part that matters: there was never a lightbulb moment. No trial where the cat suddenly got it. If cats were reasoning about levers, you'd expect the escape time to fall off a cliff — one long trial, then instantly fast ones. Instead, when he plotted escape time against trial number, he got a slow, noisy, gradual curve. The useless behaviors quietly faded. The useful one got faster.

That curve is the first real evidence in this story. Learning wasn't insight. It was selection — good behaviors surviving, bad ones dying off.

Thorndike wrote it up as the Law of Effect:

If an action is followed by a satisfying state of affairs, the bond between that situation and that action is strengthened. If followed by discomfort, it is weakened.

Read that again with our vocabulary. Situation is the state. Action is the action. Satisfying is the reward. Bond strengthened is the policy update.

Thorndike, in 1898, wrote pseudocode for a policy gradient. He just used the word "bond."

🎒 In the backpack: trial-and-error learning. Rewards make actions more likely. Learning is gradual, not sudden.

But something's missing

Thorndike's cat only learns after it gets the fish. The reward does all the teaching.

But watch a real animal for five minutes and you'll notice it reacting to things that aren't rewards at all. Your dog loses its mind at the sound of a cupboard opening. Nothing has been eaten yet. The cupboard predicts food.

Thorndike had no account of that. Rewards were where his story started and ended.

The person who noticed the signal was, characteristically, not looking for it.

The 1900s–1920s — Pavlov and the Problem of Prediction

Ivan Pavlov was a Russian physiologist studying digestion. He won a Nobel Prize for it in 1904. He was, by most accounts, mildly irritated that history remembers him for the dogs.

His actual research required measuring saliva. And his dogs kept ruining the measurements by salivating early — at the sight of the lab assistant who usually brought food, at the sound of footsteps in the corridor. Before any food existed.

Most researchers would call that noise and try to control for it. Pavlov called it the experiment.

He ran it systematically. Present a neutral signal — a metronome, a buzzer, a light, a tone — then deliver food, a second or two later. Repeat.

(Quick myth-correction, since it costs one sentence: the famous bell is mostly folklore. Pavlov's lab notes lean heavily on metronomes, buzzers, and tuning forks. The bell survived because it's easier to draw.)

After enough pairings, the signal alone made the dogs salivate. Nothing about the food had changed. What changed was that the dog had learned the signal carries information about the future.

This is the second piece, and it's a big one. Thorndike's cat learned what to do. Pavlov's dog learned what's coming.

In RL terms, that's value. The value of a state is roughly: how much good stuff do I expect from here on out? A metronome that reliably precedes food is a high-value state — not because a metronome is nutritious, but because of what tends to follow it.

You do this constantly. The smell of coffee is not caffeine. Your inbox badge is not the email. A green light is not arriving anywhere. Every one of these is a state you've assigned value to, purely because of what historically came next.

And this is why RL agents can learn anything at all in sparse environments. A chess engine that only felt reward at checkmate would learn approximately nothing — the signal is 60 moves away from most of the decisions that caused it. What it actually learns is to value positions: this pawn structure tends to precede winning. That's a metronome.

🎒 In the backpack: states have value. Value comes from prediction, not from the reward itself.

But something's still missing

Pavlov's dogs were passive. They sat in a harness and predicted. The dog's salivation doesn't make the food arrive any sooner.

So now we have two halves of an agent and no glue:

	Thorndike's cat	Pavlov's dog
Learns	which actions pay off	which signals predict payoff
Can it act?	✅	❌
Can it anticipate?	❌	✅

A real agent needs both — and it needs someone to make this a controllable science rather than a collection of observations. That took a genuine control freak.

The 1930s–50s — Skinner Turns Behavior Into Engineering

B.F. Skinner's question was different from everyone before him. Not "how do animals learn?" but: "how precisely can I control what an animal learns?"

His tool was the operant conditioning chamber — the Skinner Box. A rat inside can press a bar. A pigeon can peck a disc. Food is dispensed on rules Skinner sets. Simple inputs, measurable outputs, and — critically — the animal stays in the box.

That last detail seems minor and isn't. Thorndike's cats escaped, which meant one trial, then a reset by hand. Skinner's animals could run thousands of trials in an afternoon, uninterrupted. He'd built the first high-throughput training environment. Every RL researcher who has ever run a simulator overnight is doing the same thing.

Two of his findings matter for us.

Finding 1: Unpredictable rewards are the stickiest

Skinner varied when reward arrived — every press, every fifth press, every fifth press on average. These are schedules of reinforcement.

The counterintuitive result: variable reward — where the animal can't predict which press pays — produced behavior that was hardest to extinguish. Reward a pigeon every single time, then stop, and it gives up quickly. Reward it unpredictably, then stop, and it keeps going for a remarkably long time.

Slot machines run on this. So do infinite-scroll feeds. Skinner found the exploit in the 1950s; the attention economy just productized it.

For us, the useful version is that reward structure is a design decision with enormous consequences. Which sets up an entire genre of modern RL failure — agents that learn the reward signal instead of the task, in ways nobody intended. We'll spend real time there in a later post.

Finding 2: You can build complex behavior out of crumbs

The bigger idea is shaping.

Skinner taught pigeons to play a passable game of table tennis. Not by waiting for a pigeon to spontaneously play table tennis — you'd wait forever. He rewarded incremental steps. First, reward the bird for merely facing the table. Once that's reliable, stop rewarding it and only pay for approaching the ball. Then only for contact. Then only for direction.

https://www.youtube.com/shorts/RPJyKSmH9WM?feature=share

You are moving the goalposts on purpose, in small enough increments that the animal never falls off the curve.

This is reward shaping, and it's how we train robots today. A robot arm rewarded only for "successfully assembled the part" will flail randomly forever, because the odds of stumbling into success by accident are effectively zero. So we hand it crumbs: reward for moving toward the part, then for gripping it, then for lifting. Same ladder. Different species.

And the strategy the animal ends up with — in this situation, do this — is exactly what we called a policy at the top of this post. Skinner spent thirty years training policies. He just did it with pigeons and a food dispenser instead of gradients and a GPU.

🎒 In the backpack: policies can be trained, not just observed. Reward timing and reward structure change everything.

But something's still missing

We now have a full behavioral picture: act, predict, get shaped, improve.

Every bit of it is described from the outside. Skinner was deliberate about this — he treated the mind as a black box and argued you should only ever talk about observable behavior. Which is scientifically disciplined and completely useless if you want to build one.

Because if you're going to build this thing, you need to answer a question Skinner refused to ask: where does the learning physically live?

1949 — Hebb Finds the Storage

Donald Hebb, a Canadian psychologist, published The Organization of Behavior in 1949 and proposed a mechanism so simple it fits in a sentence.

If neuron A repeatedly takes part in firing neuron B, some growth process or metabolic change takes place in both cells such that A's efficiency in firing B is increased.

That's Hebb's Rule, and the pop version is stickier: neurons that fire together, wire together.

Two neurons active at the same time? The connection between them — the synapse — physically strengthens. Next time, A triggers B more easily. Do it enough and the path becomes a highway.

Run Thorndike's cat through this. The cat sees the lever (a pattern of neurons firing) and presses it (another pattern firing). They're active together. Their connection thickens. A hundred trials later, seeing the lever is pressing the lever — there's a paved road between them.

That's a habit, described in hardware.

And this is where artificial neural networks come from. In a network, the connection strength between two artificial neurons is a number called a weight. Learning means adjusting weights so that useful inputs reliably produce useful outputs. Hebb is the reason "learning = changing connection strengths" is the default assumption in the entire field.

One important correction, because this gets flattened a lot: Hebb's rule is not backpropagation, and the difference is worth thirty seconds.

Hebb's rule is local. A synapse strengthens based only on what its own two neurons are doing right now. No supervisor, no error signal, nobody keeping score.

Backpropagation — the algorithm that actually trains modern networks — is global and error-driven. It compares the network's output to a desired output, computes how wrong it was, and pushes that error signal backward through every layer, adjusting each weight by how much it contributed to the mistake. Every weight update depends on information from far away in the network.

These are genuinely different mechanisms. In fact, the gap between them is one of the liveliest open arguments in neuroscience: brains clearly don't run backprop — there's no known biological machinery for shipping a precise error signal backward across a network — yet backprop works spectacularly well. Whether the brain approximates something like it, or does something else entirely, is unresolved.

So the honest lineage is: Hebb gave us the idea that memory lives in connection strengths. Backprop is a much later, mathematically-driven answer to how to update those strengths. Same neighborhood, different building.

🎒 In the backpack: learning is stored in connection weights. Local, physical, incremental.

Where that leaves us in 1949

Fifty-one years, four researchers, and the loop is complete:

Idea	From	What it becomes
Rewards strengthen the actions that earned them	Thorndike, 1898	the reward signal
Signals predict future reward	Pavlov, 1900s	value
Behavior can be sculpted step by step	Skinner, 1930s–50s	policies, reward shaping
Learning is stored in connection strengths	Hebb, 1949	weights

Read that table top to bottom and you have a specification. Something that acts, predicts, gets shaped by consequences, and stores what it learned in the strength of its connections.

Nobody had built it. Nobody could — the ideas were all written in the language of biology, describing wet tissue that nobody could manufacture.

But 1949 is the year that stops being true. The war had just produced digital computers. A new field called cybernetics was arguing that control and feedback worked the same way in animals and machines, and that the distinction was less fundamental than everyone assumed.

For the first time, people had a spec for learning and a machine to run it on.

One thing they all got wrong

Before we leave the psychologists, here's the crack in the foundation — worth holding onto, because it takes another twenty years to fix.

Every idea above says learning happens when things co-occur. Metronome and food together → learn. Lever and fish together → learn. Neurons active together → wire together.

But co-occurrence can't be the whole story:

Your alarm has gone off at 7am every day for a year. By the co-occurrence rule, this morning should have strengthened that association a little further, same as every other morning. It didn't. You learned it in the first week and then stopped — even though the pairing kept happening, perfectly, hundreds more times.

So what switches learning off?

Nobody in this post can answer that. The answer arrives in 1972, from a pair of psychologists still studying rats, and when it does it turns out to be the single most important equation in this entire series. We'll get there.

Next up

RL #2 — Cybernetics and Early Machines (1948–1954). The first people to actually build this thing. Alan Turing sketching a "pleasure-pain system" in 1948. Claude Shannon's Theseus, a mechanical mouse that learned a maze by trial and error and could remember it. And Marvin Minsky wiring together the SNARC — 40 vacuum tubes, motors, and a clutch, arguably the first machine that learned by reinforcement.

The cats gave us the algorithm. Now watch people try to solder it.

If you spot an error or think I've oversimplified something, drop it in the comments — I'd rather fix it than have it sit there.

Reinforcement Learning Series

Mitansh Gor — Wed, 19 Aug 2026 18:40:39 +0000

I created this series to make that steep learning curve far less daunting for you. My goal is to trace the evolution of RL chronologically—from its roots in early psychology and physical mechanical machines to digital binary systems and modern mathematical breakthroughs. By breaking down complex concepts with clear visual guides, graphics, and real-world analogies, I hope to demystify RL and give back to the community that inspired me. Let’s dive in!

Blog 1: The Psychological Seeds (1898–1949)

This entry explores the Law of Effect (1911), where Edward Thorndike established that actions followed by satisfaction are strengthened. It also covers Ivan Pavlov’s formal definition of reinforcement (1927) and Donald Hebb’s 1949 hypothesis that "neurons that fire together, wire together," laying the groundwork for neural learning.

Blog 2: Cybernetics and Early Machines (1948–1954)

This blog details the first computational investigations, including Alan Turing’s "pleasure-pain system" (1948) and Marvin Minsky’s construction of SNARCs (1954), the first analog neural-network reinforcement calculators. It also highlights Claude Shannon’s 1952 demonstration of "Theseus," a maze-running mouse that used trial and error to "remember" paths.

Blog 3: The Mathematical Framework (1950s–1960s)

This post focuses on Richard Bellman’s development of Dynamic Programming and the Bellman Equation (1957), which provided the formal tools for solving optimal control problems. It also introduces Markov Decision Processes (MDPs) and Ron Howard’s policy iteration method (1960), which are the bedrock of modern RL theory.

Blog 4: Early Heuristics and Checkers (1959–1968)

This entry discusses Arthur Samuel’s celebrated checkers program (1959), which was the first to implement temporal-difference (TD) ideas by using board evaluation differences to modify earlier positions. It also details Donald Michie’s MENACE (1961), a physical "matchbox" engine that learned to play Noughts and Crosses through reinforcement.

Blog 5: The Birth of Learning Automata (1961–1974)

This blog examines the Soviet lineage of RL, specifically Mikhail Tsetlin’s work on "learning automata" (1961), which were finite-state machines that updated action probabilities based on stochastic environmental feedback. It traces how this research was later systematised by Narendra and Thathachar in 1974.

Blog 6: The "Hedonistic" Revival (1972–1980)

This post covers Harry Klopf’s pivotal role in reviving the trial-and-error thread by proposing the "hedonistic neuron" (1972), which argued that neurons act as pleasure-seeking units. It also explores Paul Werbos’s 1974 thesis, which was the first to describe backpropagation in the context of "Adaptive Dynamic Programming".

Blog 7: The Sutton and Barto Foundation (1981–1984)

This blog highlights the formalisation of modern RL, beginning with Sutton and Barto’s 1981 model of classical conditioning. It details the invention of the Actor-Critic architecture (1983) and Sutton’s 1984 dissertation, which provided the first rigorous computational analysis of temporal credit assignment.

Blog 8: The Q-Learning Breakthrough (1988–1994)

This entry documents two watershed moments: Sutton’s 1988 formalisation of TD learning and Chris Watkins’s 1989 introduction of Q-Learning, the first model-free, off-policy algorithm. It also covers the introduction of SARSA (1994) as an on-policy alternative that prioritises training stability.

Blog 9: Superhuman Achievement in Games (1992–1999)

This post details Gerald Tesauro’s TD-Gammon (1992), which achieved grandmaster-level backgammon play using neural networks and self-play. It also covers the options framework (1999) by Sutton, Precup, and Singh, which introduced temporal abstraction to help RL agents solve problems across different timescales.

Blog 10: Theoretical Refinement (2000–2010)

This entry explains the Policy Gradient Theorem (2000), which proved that policy parameters could be optimised using only local information. It also introduces Sham Kakade’s Natural Policy Gradient (2002), a precursor to modern trust-region methods that account for the geometry of parameter space.

Blog 11: The Deep RL Revolution (2013–2015)

This post chronicles the birth of Deep RL with DeepMind’s DQN (2013/2015), which used Experience Replay and Target Networks to master Atari games directly from pixels. It also details DDPG (2015), which extended these successes to continuous action spaces like robotics.

Blog 12: Mastering Strategy and Control (2015–2017)

This entry explores Trust Region Policy Optimization (TRPO) (2015) and its simpler successor, Proximal Policy Optimization (PPO) (2017), which became the industry standard for stable training. It also covers the historic victory of AlphaGo over Lee Sedol in 2016.

Blog 13: Integrated Mastery: Rainbow and MuZero (2017–2019)

This post details the Rainbow agent (2017), which combined seven independent DQN improvements into one "super-agent". It also highlights MuZero (2019), which learned to master games like Go and Chess without even being told the rules of the environment.

Blog 14: Hard Exploration and Generalisation (2020–2022)

This blog focuses on Agent57 (2020), the first agent to surpass the human benchmark on all 57 Atari games by solving "hard exploration" problems. It also covers Gato (2022), a single transformer-based generalist agent capable of playing Atari, captioning images, and controlling robot arms.

Blog 15: The Transformer Pivot and LLM Alignment (2021–2023)

This entry describes the Decision Transformer (2021), which reframed RL as a sequence modeling problem, bypassing traditional bootstrapping. It also covers the rise of Reinforcement Learning from Human Feedback (RLHF) with InstructGPT and the subsequent development of Direct Preference Optimization (DPO).

Blog 16: Reasoning Models and Incentivized Thought (2024–2025)

This blog explores DeepSeek Math and GRPO (2024), which removed the need for a separate critic model to improve mathematical reasoning. It details the breakthrough of DeepSeek-R1 (2024/2025), which proved that pure RL can spontaneously elicit self-correction and reflection in language models.

Blog 17: Massive Depth and the Future of Scaling (2025–2026)

This final entry discusses the 2025 NeurIPS Best Paper on 1,000-layer RL networks, which broke the "shallow network" assumption to unlock 50x performance gains. It reflects on Kimi k1.5 and the role of the 2024 Turing Award in cementing RL as a foundational pillar of the AI revolution.

Personal Health Agent (PHA): Multi-Agent Health System

Mitansh Gor — Thu, 27 Nov 2025 05:33:43 +0000

VIDEO LINK

In the last few years, we saw different types of AI systems try to answer this question:
PH-LLM (2024) → focused on personalized coaching from wearable data.
PHIA (2024) → acted like an agent that analyzes your data, writes code, and explains results.
IR Prediction + IR Explainer Agent (2025) → estimated your metabolic risk and explained it like a doctor.

All of these systems were important steps. But each one had a weakness:

A single LLM tries to do everything.
It must read data, interpret medical meaning, check safety, and give advice.
This often leads to confident hallucinations — answers that sound correct but are actually wrong.
It also mixes medical reasoning with casual coaching, which creates risk. And one model cannot be an expert in every health domain.

So the big idea behind the Personal Health Agent (PHA) is simple:

Instead of one giant model doing everything, why not create multiple smaller agents — each with a role — working together like a mini health team?
This solves the main problem with earlier systems: no single AI can fully handle the complexity of real human health. But a team of specialized agents can.

Because health is multi-dimensional—where your sleep affects your stress, stress affects metabolic health, exercise influences sleep, and food and biomarkers impact everything—one AI model can’t realistically handle all of it at once. Just like a hospital relies on different specialists, a digital health system also needs different “roles”: one agent to interpret raw data, one agent to check medical safety, and one agent to translate insights into simple coaching. This is why multi-agent systems are becoming so important: they add structure, accountability, and more reliable reasoning, solving many of the issues earlier single-LLM systems struggled with.

A System of Specialized Agents

When I look at the PHA system, what stands out first is the Analyst Agent. I think of this agent like a friend who loves numbers and graphs. Its whole job is to read my raw data — sleep hours, steps, heart rate, and other signals — and turn them into clear observations. It doesn’t try to coach me or act like a doctor. It just says, “Here’s what I see happening in your data,” which makes everything feel clean and easy to understand.

Then there is the Domain Expert Agent, which to me is the “doctor brain” of the whole system. This agent takes what the Analyst found and checks if it makes medical sense. It worries about safety, accuracy, and whether the explanation aligns with real health science. I really like this part because it stops the system from giving random or misleading advice. It acts like the strict friend who always says, “Wait, is this actually correct?”

Next comes the Coach Agent, the most human-feeling part of PHA. This agent talks to me like a supportive friend who wants me to succeed. It takes all the technical pieces and translates them into simple, everyday advice I can act on. No medical jargon. No complicated charts. Just small, doable suggestions like, “Try walking after dinner” or “Aim for an earlier bedtime tonight.” It’s friendly and practical, which is exactly what people need.

What ties everything together is how these agents work as a team. Instead of one giant AI trying to do everything — and often making confident mistakes — each agent stays in its own lane. One analyzes, one verifies, one coaches. Because of this teamwork, the final answer feels clearer, safer, and much more trustworthy. It’s almost like having a mini health team inside your phone, and that makes the whole system feel both smart and human at the same time.

Technical Deep Dive

Even though all agents may start from the same base LLM (like Gemini or GPT-class models), they are trained separately, so each one becomes good at one thing instead of being average at everything.

Finetuning

Analyst Agent is finetuned from wearable logs (heart rate, steps, sleep), time-series patterns, data summaries, and statistical examples. It becomes good at reading numbers and spotting patterns.
Domain Expert needs more serious data for finetuning, like medical guidelines, curated clinical examples, safe/unsafe reasoning samples, and explanations validated by experts. It learns how to avoid hallucinations and unsafe claims
Coach Agent is the “human” one. It is finetuned on a friendly conversational dataset, lifestyle advice examples, behavior-change coaching patterns. It learns to talk in a simple, supportive way.

This division is what makes the final system feel more stable than earlier systems like PHIA or the IR Agent, where a single LLM had to juggle all roles and often made confident mistakes.

The process itself was simple but very intentional. Here’s how I imagine it:

We first collected examples for each agent’s role.
Then we cleaned and organized everything.
Then we cleaned and organized everything.
After that, we fine-tuned each agent separately.
Then we tested the agents together.
Finally, we fixed mistakes and improved the dataset.

System architecture and Data Flow

Underneath all of this, there’s a system architecture that makes their collaboration possible. I picture it like a small command center. The user’s data flows into a main controller, which decides which agent speaks first and who validates whom. The Analyst generates its interpretation, the Domain Expert checks it, and the Coach turns everything into a simple message. Each agent is isolated enough to stay focused, but interconnected enough to build on each other’s work. There’s also a safety layer running quietly in the background — something like a “medical guardrail” — to make sure the final output stays safe, consistent, and responsible before it reaches the user.

Data Pipeline Flow

My raw data comes in (wearable data, blood test results, communication history)
The system cleans and prepares the data.
The Analyst Agent gets the cleaned data first, and it gives a report.
The Expert Agent double-checks everything and makes sure the explanation is medically correct and safe.
The Coach Agent gets the approved explanation and rewrites the message in simple, friendly language
A final safety filter reviews the message and checks for risky things like any medical diagnosis, unsafe suggestions, and harmful claims.
I receive the final output.

Inference time

During inference — which is just a fancy word for “when the system actually responds to me” — the agents talk to each other almost like coworkers passing notes in a group chat. I don’t see any of this, but it’s happening behind the scenes. The Analyst looks at my raw data and says, “Here’s what I think is happening.” The Domain Expert looks at what the Analyst wrote and either approves it or corrects it. And finally, the Coach turns their combined reasoning into something that sounds human and helpful. What I receive as a single answer is actually the teamwork of multiple roles stitched together.

Tools used

To make all of this work, the system relies on a set of tools that help each agent extend its abilities. The Analyst might use data-processing tools to clean and summarize wearable data. The Domain Expert might have access to reference tools that help it compare findings against medical knowledge or validated guidelines. The Coach might use prompt templates designed for empathy, clarity, and motivation. And the main controller uses orchestration tools — something like LangGraph or a custom workflow engine — to decide who talks when and how information flows between them. These tools don’t replace the agents, but they give them structure, context, and external capabilities they wouldn’t have on their own.

Collection of data

Everything starts with a real study they ran called WEAR-ME, which included more than a thousand Fitbit users. People had to explicitly opt-in, sign digital consent, link their wearable device, and even go for a blood draw at a Quest Diagnostics center. So the data wasn’t scraped or assumed—it came from real people who agreed to share it for research. That part mattered to me because it made the whole system feel responsible, not rushed.

Once someone joined the study, their data flowed through a very controlled pipeline.So each person had a mix of: (1) wearable time-series, (2) lab biomarkers, (3) self-reported history, (4) lifestyle questionnaires.

What I liked is that the system doesn’t directly reach into a live Fitbit account or do anything “real-time.” Instead, the PHA gets access to summaries of the participant’s data, organized into tables—like a daily summary table, an activities table, and even a population-level reference table so the system could compare one user’s values against others in their age group. This gave context, not just raw numbers.

Inside the actual agent pipeline, each sub-agent only receives the part of the data that’s relevant to its job. The system never dumps the full raw dataset into every agent. Instead, the orchestrator acts like a coordinator who hands the right information to the right specialist.

Nothing is fetched unless the user asks something that genuinely needs it. And the system also avoids asking the user for things it already knows—like their sleep hours or steps—because the orchestrator checks the available data first.

PHA vs Gemini Results

PHA wasn’t just a small improvement. It was in a completely different league.

From the end-user side, I noticed that people consistently picked PHA as the best experience. Not just once or twice — almost half the time. And this is after comparing it side-by-side against a single Gemini agent and a parallel multi-agent system.

But the biggest eye-opener for me was the expert evaluation. Experts didn’t just prefer PHA — they almost abandoned the Gemini single-agent baseline. Only around 4–5% of expert rankings put Gemini in first place, while PHA was chosen as #1 about 80% of the time. That’s not a small margin.

Strengths of the system

What struck me most was how real the system felt. Not just in terms of architecture, but in how thoroughly it was tested. It wasn’t a small demo — it involved thousands of human annotations and hundreds of hours of expert evaluation. Because of that, the strengths and limitations felt very honest.

One of the biggest strengths I noticed is how well the whole system comes together. The three-agent setup — the data scientist, the domain expert, and the coach — isn’t just theoretical. In the evaluations, PHA actually outperformed both a single-agent system and a parallel multi-agent system. End-users preferred talking to PHA almost half the time, and experts loved it even more, choosing it as the best system in about 80% of cases. To me, that says the collaboration between these agents isn’t just helpful — it genuinely changes the quality of the conversation.

The data agent in particular felt like a major upgrade. It was much better at breaking down messy, vague health questions into proper statistical analyses, catching missing data, choosing the right timeframes, and generating correct code. I could see why the system became more trustworthy — it wasn’t guessing. It was reasoning over the user’s actual data. And the domain expert agent made a big difference too. It produced safer, more accurate, and more personalized medical explanations. Users rated its responses as far more trustworthy than the base model, and clinicians preferred its summaries because they were more complete and clinically meaningful.

The health coach agent also impressed me. It wasn’t just delivering motivational lines. It followed real coaching principles — active listening, SMART goals, motivational interviewing — and this made conversations feel more natural and supportive. Users were more engaged, and the conversations ended more naturally. It reminded me of talking to a real human coach who’s actually paying attention.

As a whole system, PHA feels more thoughtful. The orchestrator doesn’t just mix answers together — it understands the user’s goal, assigns the right agent, reflects on the output, and remembers important details for later turns. This gives the conversation a sense of direction and personalization that the baselines just didn’t have.

Limitations of the System

But the system isn’t perfect. One thing that stood out immediately was the cost. PHA is slower and more computationally expensive because each request triggers multiple agents and reflection steps. Where the single-agent system might respond in around 35 seconds, PHA could take over 200. It’s powerful, but not cheap.

Another limitation is that the diagnostic reasoning, while improved, is still not bulletproof. Sometimes the domain expert agent didn’t complete its reasoning chain, and its reliance on web search occasionally pulled in conflicting information. This reminded me that, even though it acts like a doctor in some ways, it’s not actually one — and the authors make that very clear.

Bias is also a real concern. The system personalizes advice based on user traits, conditions, and context… which is great, but it also means it can unintentionally repeat patterns or assumptions from datasets that might not represent everyone equally. The paper calls out this risk directly.

The coach agent, despite being strong overall, also had a weakness: it wasn’t great at tracking user progress over time. It did a good job helping set goals, but didn’t always follow up on them in later turns. For long-term coaching, that’s something they’ll need to improve.

And finally — maybe the biggest limitation — everything was tested in short-term interactions. We don’t yet know whether PHA can support behavior change over weeks or months, which is where health coaching really matters. The team also notes that this is a research framework, not a clinical tool, and major regulatory work would be needed before deploying anything like this in the real world.

So when I put it all together, here’s how I personally see it:
PHA is a huge improvement over past systems — smarter, safer, more human, and more useful — but it’s still early. It has real strengths, but also real gaps. It’s powerful as an idea, promising as a system, and clearly built with care. But it also reminds me that great AI doesn’t replace medical care — it supports it, and it still has a lot of growing up to do.

Conclusion

After reading the PHA paper, the biggest thing I realized is that this system isn’t just an AI answering health questions — it feels more like a small team working behind the scenes to help you make sense of your own data. The evaluations show that this multi-agent design really does lead to better, clearer, and more personalized guidance compared to older single-agent approaches.

At the same time, the authors are very honest about their limits. The system can still make mistakes, it can be biased depending on the data, and it should never replace real medical care. It’s powerful, but it’s also early — more like a research blueprint than a ready product.

To me, PHA represents a hopeful direction: AI that supports people in understanding their health, not by taking over, but by helping them make smarter choices with empathy, safety, and transparency in mind

PHIA: The Agentic LLM That Writes Code, Analyzes Your Data & Explains Health Insights

Mitansh Gor — Thu, 27 Nov 2025 05:33:34 +0000

VIDEO LINK

I honestly felt like I was looking at the “next version” of what health AI should be. Whenever I asked myself questions like, “Is my sleep improving?” or “Does exercising at night change my deep sleep?”, I realized how hard it is to answer these without real analysis.

That is exactly the problem the PHIA team talks about on page 1 of the paper. They explain that even a simple question like “Do I sleep better after exercising?” requires many steps: checking recent data, comparing different days, calculating metrics, and then interpreting everything in the context of what “healthy” even means. And honestly, I could relate — that’s the kind of analysis I never do on my own.
What really caught my attention is that the paper says today’s LLMs struggle with numerical reasoning, meaning they often miscalculate or oversimplify things. I’ve definitely seen models do that — giving a confident answer but completely messing up basic math. (Limitation of PH-LLM)

So PHIA tries to fix this problem by giving an LLM the ability to plan, use tools, write code, and search the web. It doesn’t just “chat.” It becomes more like a small data analyst that works with your wearable data step-by-step.

PH-LLM vs PHIA

PH-LLM was an earlier coaching system that worked only with simple, pre-aggregated 30-day summaries and relied purely on the LLM’s internal reasoning. That meant it couldn’t actually analyze detailed daily wearable data, couldn’t run calculations, and completely failed on questions that required numbers or step-by-step reasoning. PHIA addresses these limitations by granting the LLM three new capabilities: (1) it can generate authentic Python code to analyze raw wearable data, (2) it can plan and break down tasks using an agent loop, and it can search the web to incorporate fresh, verified health knowledge.

Because of this, PHIA shifts from being “just a health coach” to becoming a true data analyst + coach, delivering insights that are more accurate, personalized, and grounded in both the user’s data and real health science. PHIA feels like the bridge between “AI as a friendly coach” and “AI as a personal data scientist.” By mixing reasoning, code execution, and web search, it finally unlocks the kind of deeper, more accurate insights that wearables have always had the potential to provide.

How PHIA Works

PHIA more like a mini health data analyst that can think step-by-step, write code, check your wearable data, search the web, and then explain everything in normal language. The PHIA paper shows this clearly — PHIA literally cycles through think → act → observe just like a human analyst would.

I’ll explain this in the simple way I understood it.

Instead of guessing answers, PHIA acts more like a small data analyst that plans its steps, checks your wearable data, and only then explains what it found. The paper describes this using the ReAct loop— Thought → Action → Observation — and seeing it in action helped me understand why PHIA is so different.

PHIA starts by thinking through the question. If I ask something like “Is my resting heart rate improving?”, it doesn’t jump to a quick reply. It pauses and decides what it needs—maybe comparing two weeks of data or calculating averages. Then, PHIA takes action by writing and running Python code in a safe virtual environment tool. This lets it analyze real daily time-series data using Pandas, just like a real data scientist. The nice part is that this removes mathematical mistakes that normal LLMs often make. And if its code crashes, PHIA actually fixes the error and tries again (recurrent trials system), which the paper highlights as one of its strengths.

In their evaluation, PHIA scored 84% accuracy on objective questions, way higher than simple LLM reasoning. This happens because PHIA can recover when the code fails.

When a question requires more than numbers—like understanding recommended sleep hours—PHIA uses a built-in web search tool to fetch verified information from trusted sources. Sometimes the user needs context, like: “Is this amount of sleep normal for my age?” “What workouts improve resting heart rate?” “Is my stress score healthy?”
PHIA has a built-in search tool that pulls information from verified online sources. This mixing of data + domain knowledge is what makes PHIA feel smart and practical.

What impressed me most is how PHIA blends everything together. It doesn’t just give numbers or copy facts. It calculates, it checks, it researches, and then it explains the result in clear language. The examples in the paper, like comparing a user’s sleep with national guidelines, really show how these steps come together. In the end, PHIA feels less like a chatbot and more like someone doing careful, step-by-step reasoning to help you understand your own health patterns.

A Deep Dive Into PHIA’s Technical Architecture

PHIA is not a fine-tuned model. It’s an agent framework built around Gemini 1.0 Ultra, with two major tools: (1) Python data analysis runtime, (2) Web search tool.

These tools are orchestrated using the ReAct (Reason + Act) agent pattern, which is why PHIA can do multi-step reasoning without fine-tuning. This design gives PHIA abilities that raw LLMs don’t have: planning, correction, stepwise attention, and grounded analysis.

No Fintuning

One of the most interesting things I learned from the paper is that PHIA is not fine-tuned like PH-LLM. Instead of modifying the model’s weights, the authors built a smart scaffolding around the model and taught it how to act like an agent.

Fine-tuning a huge LLM like Gemini Ultra is expensive, slow, requires tons of supervised data, and risky (can break general reasoning ability).

So instead, PHIA keeps the base model untouched and teaches the model how it should “think” and use tools using few-shot ReAct examples.

This is a totally different philosophy: PH-LLM → change the model. PHIA → change the system around the model

Process

The authors started with thousands of wearable-related questions (objective + open-ended). They needed a tiny set of example tasks that could teach the model how to behave like an agent.
Instead of randomly picking examples, they converted every question into numerical embeddings using Sentence-T5. This turns each question into a vector representing its meaning, so similar questions sit close together in vector space.

They ran k-means clustering (k=20) on these embeddings to automatically group similar questions into 20 clusters. Each cluster represents a whole “type” of question, like sleep trends, workout comparisons, anomaly detection, correlations, and so on.
From each cluster, they selected the most central question — the one closest to the cluster centroid.This gives 20 representative queries, each standing in for a larger family of similar queries.
For each of these 20 representative queries, the team manually wrote a complete ReAct agent trajectory that included every step of reasoning:
- Thought: what the model should plan to do
- Action (Python): the exact Pandas code needed
- Observation: the real output that the code would return
- Thought again: interpreting the output
- Action (Search): when domain knowledge is needed
- Observation: the retrieved information
- Final Answer: a clear, natural-language explanation. These aren’t partial examples — they are full step-by-step walkthroughs that demonstrate how an agent should behave.
These 20 full trajectories were inserted into PHIA’s few-shot prompt, acting as demonstrations inside its system instructions. So the model is not fine-tuned — instead, it is taught by example how to: plan before acting, decide when to run code, decide when to search the web, fix code errors, combine numerical results with domain knowledge, and produce a final personalized insight.

This is called “behavior cloning via prompting.” : It will learn the “pattern of behavior” from the examples, even without changing its internal parameters.

PHIA is a perfect example of how powerful LLMs become when they are paired with the right scaffolding instead of relying only on internal reasoning.

Limitations in the PHIA

PHIA is a huge step forward, especially compared to simple chat-based coaching. But it’s still early-stage. It shows what’s possible when LLMs use tools, but it also exposes how much work is left to make an AI truly trustworthy in personal health.

PHIA hasn’t been tested on real people yet, so we still don’t know if it truly helps users change habits or understand their health better in everyday life.
It only uses wearable data, and I feel it needs more context—like nutrition, medical records, or mood logs—to give deeper and more holistic insights.
PHIA isn’t medically validated, so even though it sounds smart, its recommendations haven’t been checked by doctors or health experts for real accuracy. Personalization still feels limited, because sometimes PHIA gives generic advice even when the user’s data is available right there.
Its reasoning depends heavily on prompting and Gemini Ultra, which means its behavior might change across models or updates, making it less consistent.
Error handling is better than basic LLMs but still imperfect, since PHIA can misread data columns or fail on messy real-world data.
Its toolset is still narrow, and I’d love to see it generate visualizations, analyze other health signals, or track long-term goals instead of just answering one question at a time.

Learnings from the paper

Reading the PHIA paper honestly changed the way I think about building AI systems. Before this, I used to focus mainly on making the model smarter, but PHIA showed me that the real progress comes from giving the model the right tools and the right structure. Seeing how PHIA uses the ReAct loop—think, act, observe—made me realize how important disciplined reasoning is for avoiding hallucinations and building trust.

The use of synthetic data was another eye-opener, because it proved that we can train and evaluate personal-health agents responsibly without touching real user data. On top of that, the way the authors handled safety—650 hours of human review, strict guardrails, and cautious refusal behavior—reminded me that responsible AI isn’t optional; it’s part of the engineering.

More than anything, PHIA taught me that the future of AI isn’t “a bigger model,” but a system where models, tools, data, and reasoning frameworks all work together. As an AI engineer, this shifted how I think about agents: not as chatbots, but as full pipelines designed to solve real problems with accuracy, humility, and safety.

Key Insights I’m Taking With Me

PHIA wins because it’s structured, not because the LLM is smarter.
Reasoning and architecture beat raw model size.
PHIA shines when a question needs data + external knowledge + multi-step logic, not just basic statistics.
Its real strength is disciplined reasoning, not raw computation.
PHIA’s strict safety guardrails make it trustworthy in a way normal LLMs aren’t.