Trial and Error Perfected: Reinforcement Learning from TD-Gammon to AlphaGo to AlphaZero

The Hook: A Move No Human Would Have Played

On March 10, 2016, in the Four Seasons Hotel in Seoul, arguably the finest Go player of his generation, Lee Sedol, sat in front of a board staring at a stone that had no business being there. It was the 37th move of the second game in the five-game series against AlphaGo, the Go program built by the company DeepMind. AlphaGo had placed a stone on the fifth line, far from the action, at a spot any experienced player would have dismissed as a beginner's blunder. The commentators on the livestream flinched; one said he thought it was a bug. Lee Sedol left the room to compose himself. He needed nearly fifteen minutes to answer.

That move — known in the Go world simply as "Move 37" — was not a mistake. It was a strategic vision that revealed itself, some fifty moves later, as the foundation of a winning position. AlphaGo itself estimated the probability that a human master would have played it at roughly one in ten thousand. The machine had not imitated a human master. It had played something no human had taught it, and something that was nonetheless deeply correct. In the end AlphaGo won the series 4–1 — a result experts had not expected for another decade.

How can a machine master a game whose number of possible positions vastly exceeds the number of atoms in the observable universe, without a human showing it the decisive moves? The answer is one of the most beautiful ideas in artificial intelligence, and it is at the same time strikingly ordinary: learning through trial, error, and reward. That is precisely what reinforcement learning does. This article traces its path from a simple mathematical idea, through the first practical triumph of the 1990s, to the systems that today drive games, robots, and — as a companion article in this vault shows — even the fine-tuning of large language models.

The Core Concept: The Third Way to Learn

Machine learning comes in roughly three families. In supervised learning you show the system examples with the correct answer: this is a cat, that is a dog. In unsupervised learning the system finds structure in data on its own, without given labels. Reinforcement learning is the third, distinctly different family — and it is also the one that comes closest to how living beings learn.

In reinforcement learning there is no teacher revealing the right answer at every step. There is only an agent acting in an environment, and a reward signal that occasionally tells it whether things are going well or badly. The agent chooses actions, observes how the environment responds, collects reward or penalty, and must work out entirely on its own which behavior pays off in the long run. No one tells it which individual move was good — only whether it won or lost the game in the end.

That is exactly where the difficulty and the beauty of the field lie. A child learning to ride a bicycle receives no labeled examples of ideal steering motions. It tries, falls, corrects, and eventually feels the balance. A dog learning a trick understands no rule, but links behavior to treats. Reinforcement learning casts this ancient form of learning into mathematics. Its roots run from behaviorist psychology — Edward Thorndike's "law of effect" from 1911, which holds that rewarded behavior is strengthened — through control theory to Richard Bellman's dynamic programming of the 1950s. The field's canonical textbook, Reinforcement Learning: An Introduction by Richard Sutton and Andrew Barto (first edition 1998, thoroughly revised second edition 2018), remains the standard reference to this day.

The central challenge has a name of its own: the credit assignment problem. When a chess game is lost after forty moves — which move was to blame? The error perhaps happened on move twelve, but the bill did not arrive until move forty. The agent must learn to distribute a late, sparse reward backward across the many actions that caused it. How this is accomplished is the thread running through this article.

Part 1: The Building Blocks – State, Action, Reward, and the Markov Frame

To make reinforcement learning tangible, it was cast into a clear mathematical frame: the Markov Decision Process (MDP). It consists of a few ingredients that are easy to understand through the example of a game.

First there is the state (\(s\)): a complete description of the situation the agent finds itself in — in Go, the arrangement of all stones on the board; for a robot, the joint angles and velocities. Second, the action (\(a\)): the choice the agent can make in that state — a stone at a particular intersection, a motor turned in a particular direction. Third, the reward (\(r\)): a numeric value the environment returns after each action, describing how desirable the outcome was. Fourth, the transition dynamics: the rule by which a state and an action give rise to the next state.

The frame's namesake, the Russian mathematician Andrei Markov, contributes a decisive simplification, the Markov property: the next state depends only on the present state and the present action, not on the entire history. The board as it stands now contains everything you need to know in order to keep playing — how you got there is irrelevant. This assumption is an idealization, but it makes the problem tractable and describes many situations surprisingly well.

The agent's goal can now be stated precisely. It seeks a policy (\(\pi\)) — a rule that assigns to each state an action (or a probability distribution over actions) — that maximizes the expected cumulative reward. The word "cumulative" matters: the aim is not the reward of the next instant, but the sum of all future rewards. So that infinitely long futures remain manageable and near rewards count a little more than distant ones, one introduces a discount factor \(\gamma\) between 0 and 1: a reward \(n\) steps away is weighted by \(\gamma^n\). A \(\gamma\) near 1 makes the agent far-sighted; a small \(\gamma\) makes it short-sighted. The quantity to be maximized — the discounted sum of future rewards — is called the return.

The entire task is thereby captured in a single sentence: find the policy that maximizes the expected discounted return. Everything that follows is the art of actually computing this when you do not know the environment in advance.

Part 2: Bellman's Principle and the Value of a State

The key to cracking this task comes from Richard Bellman, who in the 1950s worked on the tool of dynamic programming. Bellman introduced the central notion of the value function. The value \(V(s)\) of a state is the expected return an agent achieves if it starts in that state and thereafter follows a particular policy. Intuitively: how good is it to be here right now? A chess position with an extra queen has a high value; one with a hopelessly exposed king has a low one.

Bellman's deep insight is a recursion that today bears his name — the Bellman equation. It states: the value of a state is the immediately expected reward plus the discounted value of the state you land in next. In words:

Value of now = immediate reward + \(\gamma\) × value of the next state.

This equation decomposes an enormous problem — evaluating an entire, potentially infinite future — into a single step plus the already-summarized remainder. It is the mathematical heart of the whole field. Bellman's principle of optimality adds: an optimal policy has the property that, no matter how you arrived in a state, it continues to play optimally from there. Good decisions stay good, regardless of history.

Alongside the state-value function \(V(s)\) there is an even more useful variant: the action-value function \(Q(s,a)\). It evaluates not just a state but the pair of state and action — "how good is it to play precisely this move in this position?" The advantage is practical: whoever possesses a good \(Q\)-function needs no model of the environment in order to act. They simply look up which action has the highest \(Q\)-value in the current state and choose it. The \(Q\) stands for "quality," the quality of an action, and it will reappear shortly.

As long as you fully know the environment — all transition probabilities and rewards — the Bellman equation can be solved exactly by dynamic programming. But in reality the agent precisely does not know the environment. It must estimate the values from experience, from games actually played. This is where the real learning begins.

Part 3: Learning from Experience – Temporal Difference and Q-Learning

How do you estimate the value of a state when you do not know the future? The obvious answer: play many complete games to the end and average afterward which returns the individual states actually produced. This so-called Monte Carlo method works, but it is patient to the point of uselessness: you learn only at the end of a game and throw away every piece of intermediate information.

The decisive breakthrough came from Richard Sutton in 1988 with temporal-difference learning (TD learning). His idea combines the best of two worlds and has an almost philosophical elegance: you need not wait until the end to learn. You can correct one estimate by means of a better estimate.

That sounds at first like circular reasoning, but it is exactly what humans do constantly. Suppose you set out in the morning and estimate your arrival at 30 minutes. After five minutes you hit unexpected traffic. You do not wait until arrival to learn that your estimate was wrong — you correct it immediately to 40 minutes, because the new situation permits a better forecast. TD learning formalizes exactly this reflex. It compares the old value estimate of a state with a new one, obtained from the reward just observed plus the estimate of the successor state. The difference between the two — the TD error — is the learning signal that nudges the old estimate a step toward the new one. You learn from every single step, not only at the end. This updating of one estimate from another is called bootstrapping, and it is the hallmark of TD learning.

Fascinatingly, the TD error has a strikingly precise counterpart in the brain. The firing rate of the dopamine neurons in the midbrain, according to the work of Wolfram Schultz, Peter Dayan, and Read Montague in the 1990s, tracks not the reward itself but the reward prediction error — the difference between expected and received reward. Precisely the quantity that TD learning computes. This convergence of computer science and neuroscience is one of the loveliest bridges between artificial and biological intelligence, and it links this topic to the predictive brain treated elsewhere in this vault.

The famous learning algorithms build on the TD principle. Q-learning, introduced in 1989 by Christopher Watkins in his doctoral thesis, learns the optimal action-value function \(Q(s,a)\) directly, and does so "off-policy": the agent may happily experiment and try suboptimal moves while at the same time learning what the optimal policy would do. Its counterpart, SARSA, learns "on-policy," that is, the value of exactly the policy the agent actually follows. A third family, the policy-gradient methods — beginning with Ronald Williams's REINFORCE algorithm of 1992 — dispenses with the detour through value functions and adjusts the policy directly, making actions that led to high reward more probable. The actor-critic methods that dominate today unite both ideas: an "actor" chooses actions, a "critic" evaluates them via a value function.

One problem runs through all these methods like a ground note: the trade-off between exploration and exploitation. Should the agent choose the best action known so far (exploit) or try an untested one that might be even better (explore)? Pure exploitation risks getting stuck in a mediocre optimum; pure exploration never reaps the fruits of its knowledge. The simplest solution is called \(\varepsilon\)-greedy: with high probability the best known action, and with a small probability \(\varepsilon\) a random one. This dilemma is not a technical footnote but a deep pattern of every decision under uncertainty — from choosing a restaurant (the usual place or something new?) to a company's research strategy.

Part 4: TD-Gammon – The First Proof That It Works

The theory was elegant, but for a long time it remained open whether it was any good in a complex, real game. The proof was delivered by Gerald Tesauro in the early 1990s at IBM. His program TD-Gammon learned the board game backgammon — and became a legend of the field.

Tesauro's construction was radical for its time. He coupled TD learning (more precisely, the TD(\(\lambda\)) variant, which spreads learning signals over several steps) with an artificial neural network: a feedforward network with one hidden layer of initially 80 neurons, estimating the win probability for each position. The crucial part was the mode of training: TD-Gammon learned almost entirely through self-play. The program played hundreds of thousands — in the mature version 2.1, around 1.5 million — games against itself, shifting the network weights after each move according to the TD error. No human teacher, no database of master games — only the raw experience of playing against its own, slowly improving shadow.

The result, published in 1995 in the Communications of the ACM, was a sensation. TD-Gammon reached a level just below the best human world-class players of its time. More remarkable than the playing strength was what the program discovered: TD-Gammon played certain opening moves differently from what human backgammon theory had taught for decades. At first this was taken for error. But on closer analysis it turned out the machine was right — human world-class players subsequently adopted some of these moves into their own repertoire. For the first time, a learning machine had taught its human teachers something about their own game.

TD-Gammon was living proof of three principles that would carry AlphaGo twenty years later: first, that TD learning with neural networks works in real, complex domains; second, that self-play is a practically unlimited source of training data; and third, that a machine can find superhuman strategies by freeing itself from human preconceptions. Backgammon did, however, have one friendly feature: the dice bring randomness into the game, naturally mixing up the states and easing exploration. In purely deterministic games like Go, this mercy would not repeat itself — there, further ingredients were needed.

Part 5: The Leap to Depth – DQN and the Atari Games

After TD-Gammon, the marriage of reinforcement learning and neural networks stalled for over a decade. Deep networks were too hard to train, the combination was considered unstable. That changed abruptly between 2013 and 2015 with work by DeepMind, then a young London start-up.

The team around Volodymyr Mnih introduced the Deep Q-Network (DQN) algorithm, crowned by the much-cited publication "Human-level control through deep reinforcement learning" in Nature in February 2015. The task: a single algorithm was to learn to play 49 different Atari 2600 video games — from Breakout to Space Invaders to Pong — and to do so from nothing but the raw pixels of the screen and the score. No knowledge of the game rules, no hand-crafted features, the same architecture and the same settings for every game. The system saw only pixels and points and was to learn the controls from that.

DQN combined Q-learning with a deep convolutional neural network that processed the screen images and estimated a \(Q\)-value for every possible joystick action. Two technical tricks tamed the notorious instability. The first, experience replay, stores experienced transitions in a large buffer and draws random samples from it for learning, rather than learning strictly chronologically; this breaks the harmful correlation between successive frames. The second, a target network, keeps the comparison estimate frozen for a while, so the agent does not chase a constantly shifting target.

The result was impressive: DQN exceeded the level of a professional human tester on a large share of the games, in some titles by a wide margin. In Breakout it discovered on its own the strategy of digging a tunnel along the side to send the ball behind the wall of bricks — a tactic human professionals also prize, but which no one had programmed in. DQN founded modern deep reinforcement learning and provided the building blocks from which AlphaGo would soon emerge. But Go was an altogether different caliber.

Part 6: AlphaGo – When the Machine Won the Impossible Game

For decades Go was regarded as the Everest of game-playing AI. Whereas IBM's Deep Blue conquered chess in 1997 primarily through brute computing power and searching move trees, Go is too large for that. The board has 19×19 intersections; in each position there are on average around 250 possible moves (in chess about 35), and a game lasts about 150 moves. The number of legal positions is on the order of \(10^{170}\) — more than there are atoms in the observable universe. A complete search of the move tree is therefore hopelessly out of reach. On top of that, a Go position is notoriously hard to evaluate: whether a position is good depends on subtle, holistic patterns that human masters describe as "feel."

DeepMind's AlphaGo, presented in Nature in January 2016 (Silver, Huang, Hassabis, et al.), solved both problems with a combination of two deep neural networks and a clever search. The policy network proposed for each position a small selection of promising moves, thereby pruning the absurd breadth of the move tree. The value network estimated directly, for a given position, the win probability, sparing the machine from having to calculate every variation to the game's end — it supplied the "gut feeling" that distinguishes humans.

Both networks were trained in several stages. First the policy network learned in a supervised fashion from roughly 30 million moves of human master games, so it initially imitated humans. Then it improved beyond the human template through reinforcement learning in self-play. From these self-play games, in turn, the value network was trained. At play time, AlphaGo combined the two networks with Monte Carlo Tree Search (MCTS): it selectively simulated thousands of continuations, guided by the policy network (which moves are worth examining?) and evaluated by the value network (how does it stand in the end?). Search and intuition, neatly interlocked.

The results made history. Against other Go programs, AlphaGo won 99.8% of its games. In October 2015 it beat the reigning European champion Fan Hui 5–0 — the first defeat of a Go professional by a machine in the full game. And in March 2016 came the legendary duel in Seoul against Lee Sedol, one of the strongest players in the world, which AlphaGo won 4–1. Move 37 from the second game, with which this article began, became a symbol: the moment when a machine no longer merely imitated human mastery but originally, creatively surpassed it. (Lee Sedol's sole winning game, the fourth, incidentally owed itself to an equally brilliant human move — the "Move 78," which pushed AlphaGo to its limits. The human struck back, if only once.)

Part 7: AlphaGo Zero and AlphaZero – Knowledge from Nothing

As impressive as AlphaGo was, one blemish remained: it had begun with human knowledge, with millions of master moves. Was the human still needed after all, at least as a launch pad? DeepMind gave a radical answer in 2017.

AlphaGo Zero, presented in Nature in October 2017 under the programmatic title "Mastering the game of Go without human knowledge," threw the human data out entirely. It started as a tabula rasa — it knew only the rules of the game and nothing else. It learned exclusively through self-play, beginning with completely random moves. Three further simplifications made it at once stronger and leaner: it used only a single neural network instead of two (outputting policy and value together), it fed the search directly back into the network training, and it dispensed with an assortment of hand-crafted Go heuristics.

The result eclipsed even the original. After only three days of self-play, AlphaGo Zero surpassed the version that had beaten Lee Sedol and defeated it in a direct comparison 100–0. In a matter of days it raced, in fast-forward, through the entire human history of Go: it discovered classical opening patterns (joseki) that humans had developed over centuries, discarded some of them as suboptimal, and found its own patterns unknown to human theory. The lesson was uncomfortable and liberating at once: human prior knowledge was not merely dispensable — it had in fact held the earlier version back to some degree.

The final step of generalization followed in 2018. AlphaZero, described by Silver and colleagues in Science in December 2018, took the same idea and freed it from any specialization to Go. The same algorithm, without any game-specific tuning, learned to master three games from the rules and self-play alone: Go, chess, and shogi (Japanese chess). In a few hours of training, AlphaZero surpassed the best specialized programs in the world for each game — in chess, the human-optimized-over-decades Stockfish; in shogi, the program Elmo. In chess especially, AlphaZero's style caused a stir: it sacrificed material for long-term initiative in a way that recalled the romantic masters of the 19th century and made the pure-calculation engines look alien by comparison. A single, general learning algorithm had conquered three ancient mind sports from the ground up.

Part 8: MuZero and the Limits – When Even the Rules Are Unknown

AlphaZero still needed one thing: the rules of the game. It had to know which moves are legal and how the board changes after a move. The next step was to remove even this last crutch.

MuZero, presented by Julian Schrittwieser and colleagues in Nature in December 2020, additionally learned a model of the environment — that is, the dynamics of the world itself. MuZero is no longer given the rules but learns an internal, abstract model that predicts exactly the quantities that matter for planning: the expected reward, the best action, and the value of a situation. With this, one and the same algorithm mastered the board games Go, chess, and shogi as well as the 57 visual Atari games — without ever being told the rules. The machine built its own understanding of how the world responds to its actions, and planned ahead within it. With that, the arc from TD-Gammon's simple value network to the self-learned world simulation was complete.

For all the fascination, the limits deserve a sober naming. First, these systems are extremely data-hungry. AlphaZero and MuZero played millions of games and devoured enormous computing resources; a human grows wise from a handful of experiences, whereas an RL agent often needs millions. This poor sample efficiency remains a core problem of the field to this day. Second, these triumphs live in perfectly defined worlds with clear rules, clear states, and an unambiguous reward signal (win or loss). The real world rarely supplies such clean rewards. Third, reward hacking lurks everywhere: optimize a poorly chosen reward, and the agent reliably finds the way to maximize precisely that number — often in absurd, unintended ways, instead of doing what was actually meant. That is the machine form of Goodhart's law, and it is one of the reasons why aligning powerful AI is so difficult.

It is precisely here that the circle closes back to today's language models. When a reward like "answer helpfully and honestly" cannot be written down as a clean rule, it must — as described in the companion article on RLHF — be learned from human judgment. And the most recent turn toward "verifiable rewards" in training reasoning models is at heart a return to exactly the clear, checkable reward signal that already made backgammon and Go so accessible to reinforcement learning: in the end there stands an unambiguous right or wrong.

A Framework for Ordering: Five Stages of an Idea

The path of reinforcement learning can be understood as a sequence of five stages, on each of which a human crutch falls away:

The pattern is unmistakable: from stage to stage the system is given less human knowledge, and it grows stronger. This is an illustration of what Richard Sutton, in his much-cited essay "The Bitter Lesson" (2019), called the bitter lesson of the field: in the long run, general methods that scale with more computing power — search and learning — almost always beat the specialized expertise laboriously built in by humans. Not because human knowledge is worthless, but because it scales worse than raw experience and computing power.

The Central Takeaway

The real lesson of reinforcement learning reaches far beyond boards and screens. It is: you can produce competence without specifying it. No one had to explain to AlphaGo what a good Go move is. You only had to give it a clear goal (win), a space of actions, and the ability to learn from the consequences of its own actions. Out of trial, error, and a sparse reward signal grew a mastery that surpassed its human teachers and even taught them something new.

Whoever works in software development, in the cloud domain, or in IT security can draw two practical stances from this. First: the reward is the actual specification. A learning system does not do what you mean, but what you reward. Every metric you make an optimization target — a KPI, a test-coverage number, a latency figure, a security score — will sooner or later be pushed exactly in the way that maximizes the number, not necessarily in the way that improves the thing. That is Goodhart's law, and it applies to teams and incentive systems just as it does to neural networks. So formulate goals with the same care with which you would design a reward function for an agent.

Second: the exploration-exploitation trade-off is everywhere. Whether you stick with a proven architecture or try out a new technology, whether your team takes the safe path or experiments — it is the same tension that an RL agent balances at every step. Too much exploitation lingers in a local optimum; too much exploration squanders the return of what has been learned. A conscious, small budget for exploration — the \(\varepsilon\)-greedy stance — is wise practice for people and organizations too.

Reinforcement learning is thus less a collection of algorithms than a way of thinking: define a goal clearly, let the system learn from the consequences of its actions, and always reckon with the fact that it takes the reward more literally than you would like.

A Closing Question for Reflection

AlphaGo's Move 37 was beautiful because it was right — but no one, not even its builders, would have recognized it as right in advance. The machine found something true that no human could show it, by pursuing an unwaveringly clear goal. When in the future we set systems upon goals in the open, blurry reality — upon "healthy," "just," "safe," "helpful" — where there is no unambiguous won or lost: how then do we know whether a surprising proposal from the machine is a brilliant Move 37 or merely the clever gaming of a poorly chosen reward? And who bears the responsibility of telling the difference, when we ourselves can name the goal only imprecisely?

Cross-References in the Vault

• Praise and Blame for the Machine: RLHF and the Art of Teaching AI What We Want – the direct sequel: reinforcement learning when the reward comes not from game rules but from human judgment.
• Attention Is All You Need: The Transformer, Self-Attention, and the Architecture of Modern AI – the network architecture that today often plays the role of the policy and value networks.
• How Big Is Big Enough? Scaling Laws, Chinchilla, and the Measurement of AI – why more computing power and experience win so reliably (Sutton's "Bitter Lesson").
• The Predictive Brain: Predictive Processing and the Illusion of Perception – the reward prediction error of TD learning has a counterpart in the dopamine neurons.
• The Council of Specialists: Mixture of Experts and How AI Models Grow Without Getting Costlier – another architectural idea by which modern AI systems scale.
• The Two Boxes: Newcomb's Paradox and the Battle Over Rational Choice – what does it even mean to decide "optimally" when prediction and action are entangled?

Sources

• Sutton, R. S., Barto, A. G. (2018): Reinforcement Learning: An Introduction. 2nd edition, MIT Press. (Standard reference; first edition 1998.)
• Sutton, R. S. (1988): Learning to Predict by the Methods of Temporal Differences. Machine Learning 3, 9–44.
• Watkins, C. J. C. H. (1989): Learning from Delayed Rewards. PhD thesis, University of Cambridge (introduction of Q-learning).
• Tesauro, G. (1995): Temporal Difference Learning and TD-Gammon. Communications of the ACM 38(3), 58–68. https://cacm.acm.org/research/temporal-difference-learning-and-td-gammon/
• Mnih, V. et al. (2015): Human-level control through deep reinforcement learning (DQN). Nature 518, 529–533. https://www.nature.com/articles/nature14236
• Silver, D., Huang, A., Hassabis, D. et al. (2016): Mastering the game of Go with deep neural networks and tree search (AlphaGo). Nature 529, 484–489. https://www.nature.com/articles/nature16961
• Silver, D. et al. (2017): Mastering the game of Go without human knowledge (AlphaGo Zero). Nature 550, 354–359. https://www.nature.com/articles/nature24270
• Silver, D. et al. (2018): A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play (AlphaZero). Science 362, 1140–1144. https://www.science.org/doi/10.1126/science.aar6404
• Schrittwieser, J. et al. (2020): Mastering Atari, Go, chess and shogi by planning with a learned model (MuZero). Nature 588, 604–609. https://www.nature.com/articles/s41586-020-03051-4
• DeepMind (2016): AlphaGo versus Lee Sedol. Overview of the match and Move 37. https://en.wikipedia.org/wiki/AlphaGo_versus_Lee_Sedol

← All articles