Case Studies: Learning to Play

The methods in these notes were built to be general, but generality is not the same as evidence. What settles whether an idea works is a system that beats the best alternative on a problem nobody could hand-tune. Chapter 16 of Sutton and Barto collects those systems, and read in sequence they show one pattern. Every landmark shares the same skeleton: a value function, learned by acting or by playing against a copy of itself, refined by search at decision time, and, in the later cases, carried by a deep network that discovers its own features. The pieces were assembled a little more each decade; the last assembly, AlphaGo Zero, needed no human data at all.

Samuel's checkers player: the historical root

Before there was a name for it, Arthur Samuel was doing temporal-difference learning. His checkers programs, written for the IBM 701 starting in 1952 with a learning version finished in 1955, are the earliest ancestor in the line.¹ Samuel chose checkers over chess deliberately: simple enough that learning, not search bookkeeping, could be the object of study, yet still taken from life.

The program played by a minimax lookahead from the current position. Terminal positions of the search were scored by a linear evaluation function, a scoring polynomial over hand-chosen features, and the score was backed up through the tree under the assumption that each side plays to its own advantage. The most important feature was piece advantage, weighted by a fixed, non-modifiable coefficient, so the program's goal was, in effect, to win.

The learning was the interesting part. Samuel's second method, which he called learning by generalization, adjusted the weights of the scoring polynomial after each move by pushing a position's value toward the backed-up minimax value of a search launched one move later. That is a TD update in all but name: the value of a state is made to equal the value of the states likely to follow it. Sutton and Barto state the connection plainly — Samuel's method was the same in concept as that used much later by Tesauro in TD-Gammon.

Samuel's checkers player rose to a strong amateur level and was, for years, one of the most visible achievements of machine learning. It also carried a warning that the modern theory later formalized. Samuel included no rewards and no special treatment of terminal positions, so nothing tied his value function to actually winning. As he himself noted, a constant value for every position would satisfy his self-consistency criterion perfectly while playing terrible checkers. He kept the piece-advantage weight fixed precisely to forbid that degenerate fixed point. The lesson — that a self-consistent value function must be anchored to a reward and to terminal values — names the discipline that dynamic programming and TD learning build in from the start.

TD-Gammon: self-play meets a neural net

TD-Gammon, written by Gerald Tesauro around 1992, is the system that first showed reinforcement learning could reach expert human play. It put three ideas together that recur through every later case: TD(λ), self-play, and a neural network as the value function.²

Backgammon suits reinforcement learning better than chess or checkers do. The game is stochastic (a dice roll before each move) with a branching factor near 400, far too large for the deep heuristic search that dominated chess. But its full state is always visible, and every game ends in a win or a loss that reads naturally as a reward. Tesauro set the reward to zero on every step except the final one, so the estimated value $\hat{v}(s,\mathbf{w})$ of a board position $s$ is literally the probability of winning from $s$.

The value function was a standard multilayer network: an input layer encoding the board (198 units in the first version), one hidden layer, and an output unit whose sigmoid produces a win probability. Weights were updated by the semi-gradient TD(λ) rule with the gradient computed by backpropagation,

with $\gamma =1$ and the reward zero until the game is won, so the TD error is usually just $\hat{v}(S_{t+1},\mathbf{w})-\hat{v}(S_t,\mathbf{w})$. Nothing here is new to these notes; it is the eligibility-trace form of TD applied to a nonlinear approximator.

The source of games was the second idea. Tesauro's learner played against itself. To move, it considered every position its dice roll allowed, evaluated each with the network, and chose the highest-valued one; these are afterstates, the position after the move but before the opponent's dice. Both sides moved this way, generating an endless stream of games at no cost.

Started from random weights, early play was near-random and games ran for hundreds of moves, but after a few dozen games performance climbed fast. TD-Gammon 0.0, with a raw board encoding and essentially zero backgammon knowledge, learned in about 300,000 self-play games to match the best previous programs — programs stuffed with hand-built expert features. Adding a small set of backgammon-specific input features produced TD-Gammon 1.0, which beat every prior program and competed with human experts. Later versions added a shallow two- or three-ply search over the opponent's likely rolls, combining a learned value function with decision-time lookahead — the same pairing AlphaGo would scale up. By the mid-1990s the program played at or above the level of the world's best humans, and it changed how those humans played certain openings.

Watson's Daily-Double wagering: RL for a sub-decision

Not every application asks a learner to play the whole game. IBM's Watson, which won Jeopardy! against human champions in 2011, is celebrated for its natural language answering — but that is not the part that owes anything to reinforcement learning. The reinforcement-learning component is a single sub-decision: how much to wager on a Daily Double.³

When Watson hit a Daily-Double square it had to bet before seeing the clue. Its designers adapted the TD-Gammon recipe to learn a state-value function $\hat{v}(\cdot ,\mathbf{w})$ (the probability of an eventual win from a game state, learned by a multilayer network trained with TD errors) over features specific to Jeopardy!: the three players' scores, how many Daily Doubles remained, the value of clues left. To turn that value into a bet it also estimated $p_{DD}$, the in-category confidence that Watson would answer the upcoming clue correctly. Watson then scored each legal bet by the expected afterstate value,

where $S_W$ is Watson's current score, and picked the bet with the largest action value — an action value that equals the expected next-afterstate value.

For example, suppose Watson leads with $S_W=12,000$ against opponents at $9,000$ and $6,000$, and its in-category confidence is $p_{DD}=0.8$. Compare a cautious bet of $2,000$ against an all-in bet of $12,000$. Reading approximate win probabilities off the learned $\hat{v}$: a correct $2,000$ bet lifts Watson to $14,000$ with, say, $\hat{v}\approx 0.83$, and a wrong one drops it to $10,000$ with $\hat{v}\approx 0.62$, so $\hat{q}(s,2000)=0.8\cdot 0.83+0.2\cdot 0.62=0.664+0.124=0.788$. The all-in bet swings further: correct takes Watson to $24,000$ and near-certain victory, $\hat{v}\approx 0.97$, while wrong collapses it to $0$ and a poor position, $\hat{v}\approx 0.15$, giving $\hat{q}(s,12000)=0.8\cdot 0.97+0.2\cdot 0.15=0.776+0.030=0.806$. On raw expected value the all-in bet edges ahead, $0.806$ versus $0.788$ — but its outcomes are spread across a huge range ($0.97$ down to $0.15$), and subtracting a fraction of that spread as a risk penalty, exactly the standard-deviation term the designers added, reverses the ranking and picks the $2,000$ bet. That penalty is what keeps a single wrong answer on a Daily Double from throwing away a winning game.

Two details matter. First, unlike TD-Gammon, Watson could not learn $\hat{v}$ by self-play: Jeopardy! is a game of imperfect information — a contestant does not know how confident opponents are — and self-play would explore states no human match ever reaches, like poker against someone holding the same cards. So $\hat{v}$ was trained over millions of simulated games against carefully-built stochastic models of human contestants. Second, maximizing the raw expected value incurred a frightening amount of risk, so the designers subtracted a fraction of the standard deviation from each bet's value to damp catastrophic all-in wagers. In simulation the learned strategy raised the win rate from 61% (a heuristic baseline) to 67% — a large edge given that a Daily-Double bet arises only about one or two times per game.

Optimizing memory control: RL below the game layer

Reinforcement learning need not sit at the top of a system. İpek, Mutlu, Martínez, and Caruana built a DRAM memory controller whose scheduling policy is learned online, on the chip, while programs run.⁴ A memory controller decides, at each cycle, which pending read/write request to service subject to a thicket of timing constraints — a genuine scheduling problem that conventional controllers attack with fixed heuristics that ignore past experience.

They cast it as an MDP: the state is the contents of the transaction queue, the actions are the DRAM commands (activate, precharge, read, write, and a NoOp when nothing else is legal), and the reward is 1 whenever the action is a read or write (the commands that actually move data) and 0 otherwise. Transitions are stochastic because the next state depends on processor workloads the scheduler cannot control.

The scheduling agent used Sarsa with a linear action-value function over six integer features, approximated by tile coding with hashing and ε-greedy exploration. One design detail: the features used to learn values were not the ones used to define which actions were legal, so the learner's exploration could never violate a hardware constraint. In simulation the learned controller beat the best fixed policy (FR-FCFS) by 7% to 33% across nine memory-intensive workloads (averaging a 19% speedup) and its ability to adapt online was worth another 8% over a controller frozen after learning. The point is not the numbers but the placement: the same value-and-reward machinery works two levels below where anyone would call it AI.

DQN: human-level video game play

The deep Q-network (DQN) from Google DeepMind is the case study these notes have already met in deep Q-networks; here it stands as the demonstration that one learning system, unchanged, can reach human level across a wide range of tasks.⁵ DQN combined Q-learning with a deep convolutional network and learned to play 49 Atari 2600 games from raw pixels. Its weights were reset to random before each game, so it learned a different policy for each, but the raw input, architecture, hyperparameters, and algorithm were identical for all of them. No per-game feature engineering.

DQN is the descendant of TD-Gammon on the video-game branch: both use a multilayer network as a semi-gradient TD approximator with backpropagated gradients. The differences are what made Atari tractable. Where TD-Gammon estimated afterstate values (cheap in backgammon, where the rules give the post-move position), DQN estimated action values $\hat{q}(s,a,\mathbf{w})$ directly, so it never needed a model to generate next states. It used the semi-gradient form of Q-learning,

and — being off-policy — could reuse stored transitions. Three modifications stabilized the notoriously fragile combination of bootstrapping, function approximation, and off-policy updates — the deadly triad:

• Experience replay. Each transition $(S_t,A_t,R_{t+1},S_{t+1})$ is stored in a replay memory; updates draw minibatches sampled uniformly at random. This reuses experience, decorrelates successive updates, and cuts variance.
• A target network. The bootstrap target uses a duplicate network $\tilde{q}$ whose weights are frozen and only refreshed every $C$ steps, so the target does not chase the parameters being updated.
• Reward clipping. Score changes are mapped to $+1$, $-1$, or $0$, letting one step size work across games with wildly different score scales.

DQN reached or exceeded human level on 29 of the 46 games tested. Its failures — Montezuma's Revenge, which needs long-horizon planning — marked the open problems. But as a proof that deep networks can supply the features a reinforcement learner needs, on tasks as varied as Breakout and Space Invaders, without a human touching the representation, DQN is the starting point of modern deep RL.

Mastering Go: AlphaGo

Go was the standing challenge. Its search space dwarfs chess — roughly 250 legal moves per position against 35, games twice as long, but size is not the real obstacle. The obstacle is that no one could write a good position evaluation function for Go; Müller's 2002 verdict was that none would ever be found. AlphaGo, from DeepMind, broke through by learning that evaluation and pairing it with search.⁶

AlphaGo learns a network that estimates who is winning and which moves look promising, then uses those estimates to steer a search a few moves ahead. The network narrows the search; the search sharpens the network's raw estimate.

Two ideas combine. The first is Monte Carlo Tree Search, the decision-time planner from the tabular chapter: run many simulated games from the current position, growing a search tree whose edges accumulate statistics (a visit count $N$ and an action value $Q$) and, when time runs out, playing the most- visited move from the root. Plain MCTS uses uniform-ish rollouts to evaluate leaves. AlphaGo's contribution was to guide and replace those rollouts with deep networks learned by reinforcement learning.

Three networks did the work. A policy network $p(a\mid s)$, a 13-layer convolutional net, output a probability over legal moves; it was first trained by supervised learning to imitate nearly 30 million human expert moves (the SL policy), then improved by policy-gradient reinforcement learning through self-play (the RL policy). A separate value network $v(s)$, same shape but a single output, estimated the probability of winning from a position; it was trained by regression on the outcomes of self-play games generated by the RL policy. A small, fast linear rollout policy supplied quick simulations. In the search, a newly added leaf $s$ was evaluated by mixing its value-network estimate with the return $G$ of a rollout,

and the team found $\eta =0.5$ — value network and rollouts weighted equally — gave the best play, each covering the other's blind spots.

AlphaGo defeated the European champion Fan Hui 5–0 and then, in 2016, the 18-time world champion Lee Sedol 4–1 — a result experts had expected to be a decade away. It is a descendant of TD-Gammon (self-play and a neural value function) and of DQN (deep convolutional approximation), with MCTS supplying the decision-time search that TD-Gammon only hinted at with its two-ply lookahead.

AlphaGo Zero: self-play from scratch

AlphaGo still leaned on people: its policy network was bootstrapped from 30 million human moves. AlphaGo Zero removed that dependence. It used no human data or guidance beyond the rules — the Zero — and learned entirely from self-play, starting from random weights.⁷ It is both stronger and simpler, and it is the purest statement of the through-line: value, self-play, and search, with nothing borrowed from humans.

Three simplifications define it. One network, not three: a single two-headed convolutional net $f_{\theta }$ takes a raw board $s$ and outputs both a move distribution $\mathbf{p}$ and a scalar value $v$ — the policy and value networks of AlphaGo fused into one body with two heads. MCTS inside the training loop: where AlphaGo ran MCTS only during live play, AlphaGo Zero runs it during learning too. And no rollouts: each MCTS simulation ends at a tree leaf scored by the network's value head, not at the end of a simulated game.

The training loop is a form of policy iteration. The network plays itself. At each position, MCTS — guided by the current $f_{\theta }$ — runs many simulations and returns an improved move distribution $\pi$, better than the network's raw $\mathbf{p}$ because the search looked ahead. The game plays out to a winner $z$. Then the network is trained to make its policy head match $\pi$ and its value head match $z$. Silver and colleagues put it exactly: MCTS acts as a policy-improvement operator, and self-play under that operator drives the whole system upward.

The result is decisive. Started from random play, AlphaGo Zero surpassed the Lee-Sedol version of AlphaGo in three days and beat it 100 games to 0; a larger, longer-trained version reached an Elo rating above 5,000, well past every prior program and every human. Trained only against itself, it rediscovered classical Go openings and then, in places, discarded them for moves no human had played. This lesson followed the through-line through the game-playing systems. The same skeleton reaches problems with no opponent at all — web personalization, a glider learning to ride turbulent air, and the industrial-scale systems (AlphaStar, OpenAI Five, GT Sophy, and RLHF) that carried it past Sutton & Barto — which continue in Reinforcement Learning Beyond Games.