A Brief History of Reinforcement Learning

This builds on What Is Reinforcement Learning?, which set up the agent–environment loop, the four elements, and the temporal-difference backup that trained the tic-tac-toe player. That same backup is the thread we now follow both backward, into the field's history, and forward, into the deep reinforcement learning systems built on it.

A brief history of reinforcement learning

The subject did not arrive in one piece. Its early history has two long threads, pursued independently for decades, plus a third, thinner thread that stitched them together. One is learning by trial and error, from the psychology of animal learning. The second is optimal control and its solution by value functions and dynamic programming — a line that, for most of its length, involved no learning at all. The third is temporal-difference learning, driven by the difference between successive estimates of the same quantity, exactly the update that trained the tic-tac-toe player above. All three converged in the late 1980s to produce the modern field.¹

Trial and error, from psychology to machines

The trial-and-error thread runs through the psychology of animal learning. Its earliest succinct statement is Edward Thorndike's Law of Effect (1911): of several responses to the same situation, those followed by satisfaction are more firmly connected to it and more likely to recur, while those followed by discomfort have their connection weakened. Reward strengthens a behavior, punishment weakens it, and the effect scales with the satisfaction or discomfort. In one form or another it is still regarded as a basic principle of much behavior.¹

Putting the Law of Effect inside a computer appeared among the first thoughts about artificial intelligence. Turing sketched a pleasure–pain system in 1948; through the 1950s came a menagerie of electro-mechanical learners — maze-running machines, Shannon's mouse Theseus. Most consequential here, Marvin Minsky, in his 1954 doctoral work, built an analog reinforcement machine from components he called SNARCs (Stochastic Neural-Analog Reinforcement Calculators), meant to resemble modifiable synapses. Minsky's 1961 Steps Toward Artificial Intelligence then named the central problem: the credit-assignment problem — how to distribute credit for an eventual success among the many decisions that produced it.

A recurring confusion dogged the thread. Early neural-network learners (Rosenblatt's perceptron, Widrow and Hoff's Adaline) borrowed the language of reward and punishment and were often mistaken for reinforcement learners, but they were supervised systems, learning from labelled examples of the correct answer. Genuine trial-and-error research — learning from evaluative feedback that never states the right action — grew rare through the 1960s and 70s. The person most responsible for reviving it inside AI was A. Harry Klopf (1972), who argued that the rush toward supervised learning had lost the hedonic aspect of behavior: the drive to make something happen in the environment, to steer it toward desired ends. That drive distinguishes a reinforcement learner from a pattern recognizer, and grasping it is what led Sutton and Barto to separate reinforcement learning from supervised learning in the first place.

Optimal control and dynamic programming

The second thread had nothing to do with animals. In the mid-1950s Richard Bellman, extending the nineteenth-century Hamilton–Jacobi theory, attacked the optimal control problem — designing a controller to optimize a dynamical system's behavior over time — using a system's state and a value function (an optimal return function) to write a functional equation, now the Bellman equation. The methods that solve control problems through that equation became dynamic programming (Bellman, 1957). Bellman also introduced the discrete stochastic version — the Markov decision process — and Ronald Howard (1960) devised policy iteration for MDPs. These are the exact elements underlying the theory in these notes.

Dynamic programming remains, in Bellman's phrase, cursed by dimensionality: its cost grows exponentially in the number of state variables. Still, it is the only feasible general method for stochastic optimal control, and far more efficient than any alternative. What it lacked was any connection to learning: it was viewed as an offline computation requiring an accurate model and running backward in time — hard to reconcile with a learner that must go forward through experience. The two disciplines did not talk to each other.

Temporal difference, and the convergence

The third thread is the thinnest but the most distinctive. Temporal-difference methods learn from the difference between temporally successive estimates of the same quantity — the probability of winning, updated guess-toward-next-guess, as in the tic-tac-toe backup. Its roots are partly psychological, in the secondary reinforcer: a neutral stimulus that, once paired with a primary reward like food, itself takes on reinforcing power. Minsky (1954) may have been the first to see this mattered for artificial learners, but the first to build a temporal-difference method was Arthur Samuel, whose checkers program (1959) improved an evaluation function by adjusting it toward the value of later positions — a value backed up along the game, learned online, with no reference to animal psychology. Samuel took his cue from Shannon's suggestion that a program could improve a chess evaluation function by modifying it during play.

The threads then converged in stages. Klopf (1972) linked trial-and-error learning to the animal-learning literature and, indirectly, to temporal-difference ideas. Sutton developed Klopf's ideas into learning rules driven by changes in successive predictions and, with Barto, built a temporal-difference model of classical conditioning; a key step was Sutton's (1988) separation of temporal-difference learning from control, treating it as a general prediction method and introducing TD($\lambda$). The three threads met fully in 1989, when Chris Watkins's Q-learning integrated all of them under the MDP formalism. Three years later Tesauro's TD-Gammon — the same tic-tac-toe update, scaled by a neural network to backgammon — put the field on the map.

The moral of the history is that reinforcement learning is not a branch of any one of its parents. It inherited the problem (goal-directed learning from interaction) from animal psychology, the formalism (states, value functions, the Bellman equation) from optimal control, and its most characteristic mechanism (the temporal-difference update) from a line that ran between them. The tic-tac-toe player above is a miniature of the whole convergence: a trial-and-error learner that solves the credit-assignment problem with a value function updated by temporal differences.

From a lookup table to deep reinforcement learning

Sutton and Barto's tic-tac-toe player keeps one number per state in a table, and that table is the bottleneck the modern field grew out of. Tic-tac-toe has a few thousand states, so a table fits; backgammon has around $10^{20}$, Go around $10^{170}$, and a game read from raw pixels effectively infinitely many. No table can hold that. The response was to replace the lookup table $V(s)$ with a parameterized function $\hat{v}(s,\mathbf{w})$ — a neural network — that generalizes across unseen states while keeping the same temporal-difference backup. Deep reinforcement learning is that one substitution, together with the fixes for everything it broke.

The first system to make the substitution work at scale was Deep Q-Networks (Mnih et al., 2015, Nature). DQN learned 49 Atari 2600 games from the raw screen and the score alone, reaching human-level play on most with a single architecture and one hyperparameter set. Its learning signal is the same temporal-difference error that trained the tic-tac-toe player — an estimate nudged toward a bootstrapped later estimate — but computed over a convolutional network instead of a table. Two ideas kept the network from diverging, a real risk once function approximation, bootstrapping, and off-policy data combine. Experience replay stores past transitions in a buffer and trains on random minibatches, breaking the temporal correlations that destabilize gradient descent; a target network, a slowly-updated copy of the value network, supplies the bootstrap target so the target does not move in lockstep with the network being trained. Both address problems the tabular case never faced.

Games remained the proving ground, and the direct heir of the tic-tac-toe player is AlphaGo (Silver et al., 2016, Nature), which defeated a top professional Go player — a feat expected to be a decade away. AlphaGo pairs deep value and policy networks with Monte Carlo tree search, a lookahead that grows a search tree by simulating games and backing their outcomes up through it — the back-up-the-value idea generalized to search. AlphaZero (Silver et al., 2018, Science) dropped all human game records and learned Go, chess, and shogi from self-play alone from random weights — the tic-tac-toe setup's learn by playing, no labelled set taken to its limit, superhuman in each game within hours. MuZero (Schrittwieser et al., 2020, Nature) removed even the rules from the inputs: it learns a model of the environment's dynamics and plans inside it, closing the loop back to the optional fourth element — a model of the environment — that Sutton and Barto introduce and then set aside.

The same value-based core reaches well past games. Reinforcement learning has controlled the plasma in a tokamak fusion reactor (Degrave et al., 2022, Nature) and, in the form most people now encounter, fine-tuned large language models from human preference judgments — reinforcement learning from human feedback (Christiano et al., 2017; Ouyang et al., 2022). There the reward is a learned model of which of two responses a person prefers, and the policy improved is the language model itself. The reward is still evaluative, not instructive: the model is told that one answer was preferred, never what the ideal answer was — the same evaluative-feedback signature that separated reinforcement learning from supervised learning in the first section of this lesson.

What has not changed is the frame Sutton and Barto set up. The agent still observes a state, takes an action, and receives a reward one step later; still balances exploration against exploitation; still estimates values; still assigns delayed credit with a temporal-difference backup. Deep reinforcement learning replaced the lookup table with a function approximator and scaled compute by many orders of magnitude, but the agent–environment loop underneath is the one drawn in the first figure of this lesson.²