Preface: In 1950, the core equation of modern AI was smuggled past the Pentagon under a fake name.
Following the previous #AI series and #MarvinMinksy series. This post is co-written with Claude.

Reinforcement learning is usually told as a story about imitating the brain: cats, pigeons, neurons, synapses, a machine that wants to learn the way an animal does. But the other half of its foundation has nothing to do with the brain. That half comes from Cold War military logistics: how to allocate missiles, how to schedule aircraft, when to restock a warehouse. The man who came up with it never studied animals and never built a machine that could learn. He was a mathematician who only wrote equations, and to protect his research funding, he even had to pretend that what he was doing wasn't mathematics.

1920: The Grocer's Son

Richard Bellman was born in New York in 1920. His parents, descended from Russian and Polish Jewish immigrants, ran a small grocery store on Bergen Street, near Prospect Park in Brooklyn. When he was nine, the Great Depression hit. It ruined his father's business, but even in those hard years, the family managed to keep him in school.

He first encountered algebra at eleven and was hooked on mathematics from then on. In high school he competed for his school's math team, and in his final year he earned the top ranking among all the high school students in New York. He graduated from Brooklyn College in 1941, then went on to the University of Wisconsin for a master's in mathematics.

The war upended everything. At the end of 1944, Bellman was drafted and assigned to Los Alamos, New Mexico, where he spent two years in the theoretical physics division of the Manhattan Project. After his discharge in 1946, he returned to Princeton and finished his PhD in just three months. He then went to Stanford as an associate professor, working in his favorite branch of pure mathematics: analytic number theory.

Number theory is the mathematics of whole numbers, especially primes, the numbers divisible only by 1 and themselves, like 2, 3, 5, 7, and 11. It asks questions that sound simple but are extraordinarily hard to answer: Are there infinitely many primes? How are they distributed among the whole numbers? Can every even number greater than 2 be written as the sum of two primes? Analytic number theory is the branch that uses tools built for studying continuous change, like calculus, to answer questions about whole numbers.

That sounds backwards. Whole numbers come in separate, discrete steps, so why use methods designed for smooth curves and continuous change? Yet it turns out to work remarkably well.

Looked at one by one, the primes follow no pattern. After 7 comes a gap of four to 11, then a gap of two to 13, then four again to 17. Sometimes two primes sit right next to each other, like 101 and 103; sometimes there's a long empty stretch between them. No one can predict where the next prime will appear.

But change the question. Instead of asking where the next prime is, ask how many primes there are up to a given number, and draw the answer as a line, with the size of the number along the bottom and the count of primes up the side. You get a staircase that steps up by one every time it hits a prime. Up close, the steps are uneven, some tall, some wide. But step back and look across thousands or tens of thousands, and the staircase blurs into a remarkably smooth curve.

It's the same principle as population statistics. No one can predict the day any one person will die, but an insurance company can calculate quite accurately how many out of a million sixty-year-olds will die next year. Individuals are random; the whole has a pattern. And once the distribution of primes becomes a smooth curve, the tool built for smooth curves, calculus, suddenly has something to work on.

The story goes that Gauss noticed this curve when he was fifteen. He counted thousands of primes by hand and saw that the larger the numbers got, the sparser the primes became, and that how sparse they got was related to something called the logarithm. For example, 10 × 10 = 100 uses two tens, so the base-10 logarithm of 100 is 2. Six tens multiplied together make a million, so the base-10 logarithm of a million is 6. The fixed number being multiplied is called the base. The most important thing about logarithms is how slowly they grow. Going from 1,000 to a million, the number gets a thousand times bigger, but the logarithm only goes from 3 to 6. Every time a number gets ten times larger, its logarithm goes up by just one.

Logarithms don't have to be whole numbers. Fifty falls between 10 and 100, so its base-10 logarithm falls between 1 and 2, at about 1.7. "Multiplying 1.7 times" sounds like nonsense, but think of it as growth: if a sum of money grows smoothly to ten times its size every year, after one year it's 10 times bigger, after two years 100 times bigger, and after 1.7 years it's exactly 50 times bigger. Once you allow a single "time" to be cut into smaller pieces, the count can be a fraction. Every number greater than zero has a logarithm.

Change the base, and the logarithm changes too. The same number 50 has a base-10 logarithm of 1.7, but a base-7 logarithm of about 2, since 7 × 7 = 49. The smaller the base, the more times you have to multiply, and the larger the logarithm. Gauss used a special base, about 2.718, which mathematicians call e. Logarithms with base e are called natural logarithms, because they're the most natural way to describe smooth, continuous growth, like compound interest or reproduction.

The rule Gauss guessed was this: the number of primes up to a given number is roughly that number divided by its natural logarithm. Let's plug in some numbers. The natural log of 100 is about 4.6, and 100 ÷ 4.6 is about 22; there are actually 25 primes. The natural log of 1,000 is about 6.9, which gives an estimate of about 145; the real count is 168. Up to 10,000, the estimate is about 1,086, against an actual 1,229. The natural log of a million is about 13.8, giving an estimate of about 72,382; the real number is 78,498. The estimate always runs a little low, but the bigger the number, the smaller the error in proportion: 12% off up to 100, only 8% off up to a million.

There's an even more intuitive way to read this rule: near any given number, a prime turns up on average once every "natural log of that number" numbers. Near 100, the natural log is 4.6, so roughly one number in every four or five is prime. Count the numbers from 90 to 110: 97, 101, 103, 107, 109, five primes in twenty numbers, exactly one in four. Near a million, the natural log is 13.8, so only about one number in fourteen is prime. The numbers have grown ten thousand times larger, but the average gap between primes has only tripled. The primes thin out, but they thin out very, very slowly.

Gauss never proved his rule. What finally let calculus get a grip on the primes was a clever transformation. In 1737, the Swiss mathematician Leonhard Euler discovered an equation: if you add up a certain kind of reciprocal of every positive whole number, the result is exactly equal to a product made up only of primes. That equation tied "all whole numbers" and "all primes" together in a single expression. On one side was a continuous function, something you could differentiate, graph, and analyze with calculus. On the other side, hidden inside, were all the primes. Studying the function meant studying the primes indirectly.

Euler used this method to prove an astonishing result: if you add up the reciprocals of all the primes, 1/2 + 1/3 + 1/5 + 1/7 + 1/11 and so on, the total never settles on any number. It just keeps growing. Mathematicians call this “diverging.”

It grows extraordinarily slowly. Add up the reciprocals of the primes below 10 and you get about 1.18. Below 100, about 1.8. Below a million, about 2.9. Add every prime below a billion and the total is still only about 3.3; go all the way to a billion billion, 10 to the 18th power, and it barely reaches 4. It creeps so slowly you can hardly see it move, but it never stops. Name any number you like, 10 or 100, and if you keep adding, the total will eventually pass it.

Many infinite sums don’t behave this way. Take 1/2 + 1/4 + 1/8 + 1/16 and so on, where each term is half the one before. No matter how many terms you add, the total only gets closer and closer to 1 and never gets past it. This is called “converging”: infinitely many terms, but a finite total, because the terms shrink too quickly. Or take the reciprocals of the square numbers, 1/1 + 1/4 + 1/9 + 1/16 and so on. Added up forever, they settle at about 1.645, a problem Euler himself had cracked a few years earlier.

Whether an infinite sum stops depends on how fast its terms shrink. As the primes thin out, their reciprocals get smaller and smaller. If the primes thinned out quickly, their sum would stop the way 1/2 + 1/4 + 1/8 does. Euler proved that it doesn’t, and that tells us two things. First, there must be infinitely many primes, because a finite list of them would add up to a finite number. Second, the primes thin out very slowly, far more slowly than the square numbers do. If you only stared at the whole numbers one at a time, you would almost never discover this.

In 1859, the German mathematician Bernhard Riemann extended Euler's function into the complex numbers. It later became known as the Riemann zeta function. He found that there is always some error between the smooth curve of prime distribution and the actual staircase, and that this error is completely determined by the points where the function equals zero.

It's a bit like music. A chord sounds like a single blended sound, but it's really several notes of different frequencies layered on top of each other; if you know the frequencies, you can rebuild the sound exactly. What Riemann discovered was that the jagged staircase of the primes could also be broken down into a combination of "frequencies," and those frequencies are the zeros of the zeta function. Know the zeros, and you can reconstruct the distribution of the primes precisely.

The Riemann Hypothesis says that all of these zeros line up neatly along a single straight line. If it's true, the primes deviate from the smooth curve in the "quietest" possible way. It has never been proven, and it is one of the seven problems for which mathematicians have offered a million-dollar prize.

In 1896, two mathematicians, Jacques Hadamard and Charles de la Vallée Poussin, working independently along the path Riemann had laid out, finally proved the rule Gauss had guessed a century earlier. This is the Prime Number Theorem: the bigger the numbers, the closer the proportional error between the estimate and the actual count gets to zero.

The theorem means several things.

First, there is order hidden inside chaos. "Divisible only by 1 and itself" is a completely deterministic rule with nothing random about it, yet the primes it produces look like a handful of sand tossed at random. And the overall spread of that sand falls precisely along a smooth curve.

Second, it has a very practical use. Online banking, credit card payments, and the little padlock next to your browser's address bar often depend on enormous primes hundreds of digits long. Encryption systems need to find new large primes all the time, which requires that they not be too rare. The Prime Number Theorem guarantees exactly that. A 300-digit number has a natural logarithm of about 690, which means that among numbers that size, roughly one in every 690 is prime. Pick random 300-digit odd numbers and test them, and you'll hit a prime within a few hundred tries.

Third, it builds a bridge between two worlds. Whole numbers are discrete, but e comes from continuous growth. No one would have guessed in advance that asking which whole numbers are divisible only by themselves would produce an answer with 2.718 in it. The discrete and the continuous, two worlds of mathematics that seem to have nothing to do with each other, turn out to be connected at a very deep level.

Whole-number problems are hard because every number is an isolated point. You can't describe them with ideas like change, trend, or slope, and calculus is precisely the language of change and trend. The trick of analytic number theory is to find a bridge: by looking at the whole in aggregate, or by building a function, it translates a discrete problem into a continuous one, solves it with continuous tools, and then translates the answer back.

1949: A Summer at RAND

In the summer of 1949, Bellman went to the RAND Corporation in Santa Monica, California. RAND was a think tank spun off after the war from a U.S. Air Force research project, and it studied strategy and logistics for the Air Force. When he arrived, he asked a colleague, Ed Paxson, what RAND was interested in. Paxson suggested he work on "multistage decision processes." Bellman took the suggestion.

A multistage decision process is a chain of linked decisions, where each decision changes the situation facing the next one. A great many real problems work this way. How much ammunition you ship to the front today determines how much is left in stock tomorrow; what's left tomorrow determines how much you can ship the day after. Which route a plane flies today determines which airport it's sitting at tomorrow. You can't look at any decision in isolation, because each step sets up the next. For a while, Bellman wavered between Stanford and RAND: on one side, the number theory he loved; on the other, a brand-new problem that looked rough but full of possibility. In 1952 he left Stanford and became a research mathematician at RAND.

1950: A Name Not Even a Congressman Could Object To

In the fall of 1950, Bellman's first task at RAND was to come up with a name for his research.

He explained why in his 1984 autobiography. The 1950s, he said, were not good years for mathematical research. There was a Secretary of Defense in Washington, Charles Wilson, who had a pathological fear and hatred of the word "research." Hearing it would make his face flush red with rage. You can imagine how he felt about the word "mathematics." RAND worked for the Air Force, and the Air Force's boss was Wilson. Bellman felt he had to find a way to keep both the Air Force and Wilson from noticing that what he was really doing at RAND was mathematics.

First he chose "programming." At the time, this was a military term for drawing up a schedule for training or logistics, and it had nothing to do with what we now call programming. Then, to convey that the problem was multistage and changed over time, he added "dynamic." The word "dynamic," he said, has an interesting property: it's impossible to use it in a pejorative sense. It was a name not even a Congressman could object to. Dynamic programming is the method of taking a large problem made up of a chain of decisions, breaking it into smaller problems, and solving them by working backward from the last step.

Working Backward

Take a concrete example. Say you're driving from Oakland to Los Angeles, passing through a lot of towns along the way, and at every town there are several roads to choose from. You want to find the route with the shortest total distance.

The brute-force approach is to list every possible route, add up the length of each one, and pick the shortest. But once there are enough towns, the number of routes explodes. With three roads to choose from at each town, ten towns gives you three to the tenth power, or almost sixty thousand routes. Twenty towns gives you more than three billion.

Bellman's idea was this: don't calculate forward from the start. Calculate backward from the finish.

First, look at the towns that are just one step from Los Angeles. The shortest distance from each of them to LA is obvious at a glance, so write it down. Then step back one more stage, to the towns two steps away. From each of these, all you have to do is compare: the distance to the next town, plus that town's shortest distance to LA, which you've already worked out. Which combination is smallest? Write it down. Step back again and do the same thing, all the way back to Oakland.

This way, you never have to list every route. Each town only needs to be worked out once, and each time you only have to look at the few roads right in front of you.

Behind this method is a very simple idea, which Bellman called the principle of optimality. In terms of this example: if the shortest route from Oakland to Los Angeles passes through Fresno, then the stretch of that route from Fresno to LA must itself be the shortest route from Fresno to LA. Otherwise you could swap that stretch for a shorter one, and the whole route would get shorter too, which contradicts the claim that it was the shortest route in the first place.

The principle of optimality: the best plan has the property that, wherever you start and whatever your first move, the remaining decisions must also be the best ones for the position you're in after that first move. In other words, the best whole is made up of best parts. So you can start with the last stretch and piece the route together backward, one stretch at a time.

The Bellman Equation

Write this idea down as a formula, and you get what is today the most central equation in reinforcement learning.

First, a definition: the "value" of a situation. In the driving example, a town's value is how far you still have to go from there to Los Angeles. More generally, the value of a situation is the total reward you'll end up with if you start from there and make the best choice at every step afterward.

The Bellman equation: the value of a situation equals the reward you get at this step, plus the value of the situation you move into next. And the best choice is the one that makes those two together as large as possible.

The beauty of the equation is that it turns a long problem into a short one. You don't need to see the whole future at once. You only need to know two things: what you'll get from this step, and what the next situation is worth. And what the next situation is worth can be worked out with the same equation, from the situation after that.

In real life, many things are uncertain. A shipment of ammunition sent to the front might arrive on time, or it might get blown up on the way. A flight route you choose might go smoothly, or it might run into bad weather. Bellman's equation handles this too: if there are several possible next situations, you take the value of each and average them, weighted by how likely each one is. The value of a situation becomes "the reward right now, plus the average value of the next situation."

"Value" Is a Prediction

As we saw in the first post, reinforcement learning needs two things. One is prediction: knowing which situations lead to good outcomes. That's what Pavlov's dog learned. When the bell rang, it predicted food was coming. The other is choice: knowing which actions will get you into those good situations. That's what Thorndike's cat learned. It learned to pull the string.

Bellman's "value" is the mathematical version of the first. The value of a situation is, at bottom, a prediction about the future: starting from here, how much good will I end up with? And the Bellman equation provides the second as well. Once you know the value of every situation, choosing becomes simple: at every step, move toward the situation with the highest value. For Pavlov and Thorndike, prediction and choice were two animals in two different countries. With Bellman, they were written into the same equation for the first time.

1957: The Markov Decision Process

In 1957, Bellman published a book titled Dynamic Programming, and the same year a paper called "A Markovian Decision Process." In it, he laid out a standard framework for this whole class of problems. The framework has four parts:

• States: the situation the system is in at a given moment, like the position on a chessboard, the stock in a warehouse, or which airport a plane is sitting at.

• Actions: the choices available in each state.

• Transitions: the probability that a given action will take you into each new state.

• Rewards: the gain or loss that comes with each transition.

The "Markov" in the name comes from the Russian mathematician Andrey Markov, and refers to a particular assumption: what happens next depends only on the state you're in now, not on how you got there. Chess works this way. What determines your next move is the position on the board in front of you; the sequence of moves that produced that position doesn't matter.

Today's textbooks call this four-part framework the "Markov decision process." It's the common language of the entire field of reinforcement learning. The game of Go that AlphaGo faced, and the word-by-word answers ChatGPT generates during training, are both written mathematically in this framework.

The Curse of Dimensionality

Dynamic programming has a fatal weakness.

In the driving example, the situation has only one variable: which town you're in. But real problems usually have many. In a warehouse problem, for instance, the situation might include the stock level of ten different products. Say each product's stock is divided into just ten levels. Then the total number of possible situations is ten to the tenth power: ten billion. Dynamic programming requires working out every one. At one per second, that would take about 2.77 million hours, or more than three hundred years.

And that's only ten products at ten levels each. Every added variable multiplies the number of situations again. Bellman called this problem the "curse of dimensionality." Chess and Go are classic victims of the curse. The number of possible positions in chess is around ten to the forty-somethingth power; Go has far more, vastly more than the number of atoms in the universe. No machine could ever work through all of them.

1960: The Sears Catalog

In 1960, Ronald Howard, a young engineer at MIT, published Dynamic Programming and Markov Processes. He proposed a new method of solution called "policy iteration." Start with any set of rules for what to do, and work out what each situation is worth under those rules. Then, in each situation, check whether a different choice would do better, and if so, switch. Recalculate the values, improve the rules again, and keep going around until the rules stop changing. He proved that each round gets better, and that the process is guaranteed to stop after a finite number of steps with the best possible set of rules.

Howard later revealed that he invented the method to solve a real problem for Sears, Roebuck and Company: deciding which customers to send catalogs to. Because it involved trade secrets, he couldn't describe the actual problem in his book and had to demonstrate the method with made-up examples instead.

By the end of the 1950s, this whole toolkit, dynamic programming, the Bellman equation, the Markov decision process, and policy iteration, was already quite mature. But all of it rested on one assumption: that you know the rules of the world completely in advance.

Which actions are available in each situation, how likely each action is to take you where, how much reward each step brings: all of it has to be known. Most of RAND's logistics problems met this condition, because the rules were set by people and the probabilities could be estimated from historical data. So strictly speaking, what Bellman's method solved was planning, not learning. You hold a complete map, sit down, and calculate the best route.

Thorndike's cat had no map. It didn't know in advance which string opened the door, or what would happen when it pulled one; it could only try, again and again. The rat in SNARC had no map either. Real learning means working out the value of each situation from experience, little by little, with no map at all.

And even with a map, Bellman's method gets trapped by the curse of dimensionality: there are too many situations to ever finish calculating.

In 1965, Bellman left RAND for the University of Southern California, where he held professorships in mathematics, electrical engineering, and medicine at the same time. In his later years his interests turned increasingly toward biology and medicine. In 1973 he was diagnosed with a brain tumor. Surgery removed it, but complications left him severely disabled. Even so, he published more than a hundred papers in the last eleven years of his life. Over his career he wrote more than six hundred papers and about forty books. He died in Los Angeles in March 1984, at sixty-three. His autobiography came out the same year.

In those same years when Bellman was arriving at RAND and naming dynamic programming, an engineer at IBM's lab in Poughkeepsie, New York, was getting a computer to teach itself checkers. He didn't know in advance what each board position was worth, and there were far too many positions to work them all out. So he had the program play game after game against itself, estimating the value of each position bit by bit from experience, using exactly Bellman's idea of working backward. 🧪