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

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.

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:

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:

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:

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

1. 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.
2. 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.
3. 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:

1. To compute V(s), you need to know which policy π the agent is following.
2. 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?

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.

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.

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.

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:

1. The world is states and actions — that's an MDP.
2. Rewards define what "good" means — and you're the one writing them, so be careful.
3. Value is a score for how promising the future looks from here — the number Thorndike's cat never had.
4. The Bellman Equation makes future reward flow backward through states, leaving a slope you can climb.
5. A policy is just a rule for picking actions — a lookup table, not a plan.
6. 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.