--- title: "A Brief History of Reinforcement Learning" module: Foundations moduleNumber: 1 lessonNumber: 2 order: 102 summary: > The origins of reinforcement learning. Three threads — trial-and-error learning from animal psychology, optimal control and dynamic programming, and temporal-difference learning — ran independently for decades and merged around 1989 into the modern field. Replacing the lookup table with a neural network then produced deep reinforcement learning: DQN, AlphaGo, AlphaZero, MuZero, and RLHF. topics: [Foundations] sources: - book: Sutton & Barto ref: "§1.7 Early History of Reinforcement Learning" --- This builds on [What Is Reinforcement Learning?](/reinforcement-learning/foundations/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.[^sb-history] $$ % caption: The three threads of reinforcement learning and their convergence. % Trial-and-error learning (top) and optimal control / dynamic programming % (bottom) ran independently for decades; temporal-difference learning (middle) % linked them, and the three merged around 1989 with Q-learning. \begin{tikzpicture}[>=stealth, font=\footnotesize, node distance=2mm] \definecolor{acc}{HTML}{2348F2} \definecolor{red}{HTML}{C0392B} % three horizontal lanes % trial-and-error (top) \node[anchor=east, font=\scriptsize, text=acc, align=right] at (-0.2,3.0) {trial-and-error\\learning}; \draw[acc, thick, ->] (0,3.0) -- (10.2,3.0); \node[acc, anchor=south, font=\scriptsize] at (0.8,3.05) {Thorndike}; \node[acc, anchor=south, font=\scriptsize] at (3.6,3.05) {Minsky}; \node[acc, anchor=south, font=\scriptsize] at (6.4,3.05) {Klopf}; \node[acc, anchor=south, font=\scriptsize] at (8.6,3.05) {Sutton-Barto}; \fill[acc] (0.8,3.0) circle (1.6pt); \fill[acc] (3.6,3.0) circle (1.6pt); \fill[acc] (6.4,3.0) circle (1.6pt); \fill[acc] (8.6,3.0) circle (1.6pt); % temporal-difference (middle) \node[anchor=east, font=\scriptsize, text=red, align=right] at (-0.2,1.6) {temporal-dif\/ference\\learning}; \draw[red, thick, ->] (2.6,1.6) -- (10.2,1.6); \node[red, anchor=south, font=\scriptsize] at (3.6,1.65) {Samuel}; \node[red, anchor=south, font=\scriptsize] at (7.0,1.65) {Sutton TD}; \fill[red] (3.6,1.6) circle (1.6pt); \fill[red] (7.0,1.6) circle (1.6pt); % optimal control (bottom) \node[anchor=east, font=\scriptsize, align=right] at (-0.2,0.2) {optimal control /\\dynamic programming}; \draw[black, thick, ->] (2.4,0.2) -- (10.2,0.2); \node[anchor=south, font=\scriptsize] at (3.3,0.25) {Bellman}; \node[anchor=south, font=\scriptsize] at (5.3,0.25) {Howard}; \fill[black] (3.3,0.2) circle (1.6pt); \fill[black] (5.3,0.2) circle (1.6pt); % convergence: dashed lines from each lane into a merge node \node[draw, acc, thick, align=center, font=\scriptsize, fill=acc!6] (merge) at (9.6,1.6) {Q-learning\\1989}; \draw[dashed, black] (8.6,3.0) -- (merge.north west); \draw[dashed, black] (5.3,0.2) -- (merge.south west); % decade axis \draw[black] (0,-0.7) -- (10.2,-0.7); \foreach \x/\d in {0.5/1910, 3.3/1955, 5.6/1972, 8.0/1988} { \draw[black] (\x,-0.62) -- (\x,-0.78); \node[anchor=north, font=\scriptsize, text=black] at (\x,-0.72) {\d}; } \end{tikzpicture} $$ ### 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.[^sb-history] > **Definition (Law of Effect).** Thorndike's principle that actions followed by > satisfaction become more likely to be repeated in the same situation, and actions > followed by discomfort less likely. It combines two features that define > reinforcement learning: it is **selectional** (it chooses among alternatives by > trying them) and **associative** (the alternatives it finds are associated with > particular situations). Selection alone is evolution; association alone is > supervised learning; their combination is trial-and-error learning. 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. > **Definition (Credit-assignment problem).** Named by Minsky (1961): when a > long sequence of decisions leads to an outcome, how should the credit (or blame) > for that outcome be apportioned among the individual decisions? Delayed reward > makes this the central difficulty of reinforcement learning, and value functions > are the tool for solving 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](/reinforcement-learning/foundations/value-functions-and-optimality). 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](/reinforcement-learning/foundations/markov-decision-processes) — 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. > **Definition (Dynamic programming).** Bellman's family of methods that solve an > optimal control problem by iterating the Bellman equation over states, building > the value function from that of successor states. Historically it required a > complete model and involved no learning; its integration with online, model-free > learning is what took decades and defines much of modern reinforcement learning. ### 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. | Thread | Key figures | Central contribution | | --- | --- | --- | | Trial and error | Thorndike, Minsky, Klopf, Barto & Sutton | learning from evaluative feedback; the credit-assignment problem | | Optimal control | Bellman, Howard | value functions, dynamic programming, the MDP | | Temporal difference | Samuel, Sutton & Barto, Watkins | learning from successive estimates; secondary reinforcement; Q-learning | 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. $$ % caption: The one substitution behind deep reinforcement learning. The tabular % temporal-difference update keeps a number per state in a lookup table (left); % deep RL replaces the table with a neural network $\hat v(s,\mathbf{w})$ that % generalizes across states (right), but drives it with the same TD error. The % network trades exact per-state memory for the ability to act in state spaces too % large to enumerate. \begin{tikzpicture}[>=stealth, font=\footnotesize, bx/.style={draw, minimum width=30mm, minimum height=13mm, align=center}, rowbox/.style={draw, minimum width=8mm, minimum height=5mm, inner sep=0pt}] \definecolor{acc}{HTML}{2348F2} % --- left: table --- \node[font=\footnotesize] at (0.9,2.5) {lookup table}; \foreach \i/\v in {0/0.50, 1/0.72, 2/0.31, 3/0.55} { \node[rowbox] (r\i) at (0,1.7-\i*0.55) {s\i}; \node[rowbox, anchor=west] at (0.4,1.7-\i*0.55) {\v}; } \node[anchor=north, align=center, font=\scriptsize, text=black] at (0.7,-1.0) {one entry per state:\\breaks past ~1e6 states}; % --- middle: TD arrow --- \node[align=center, font=\scriptsize, text=acc] at (4.0,0.8) {same TD backup\\V $\gets$ V + a (target - V)}; \draw[->, acc, thick] (2.4,0.4) -- (5.6,0.4); % --- right: network --- \node[font=\footnotesize] at (7.6,2.5) {neural network}; \node[bx, draw=acc, text=acc] (net) at (7.6,1.0) {v-hat(s, w)}; \node[anchor=north, align=center, font=\scriptsize, text=black] at (7.6,-1.0) {generalizes across states:\\scales to pixels, Go, robots}; \draw[->, black] (5.5,1.0) -- (net.west) node[pos=0.4, above, font=\scriptsize] {s}; \end{tikzpicture} $$ 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. | System | Year | Domain | New ingredient | | --- | --- | --- | --- | | DQN | 2015 | 49 Atari games from pixels | replay buffer + target network | | AlphaGo | 2016 | Go (vs. professional) | deep value/policy nets + MCTS | | AlphaZero | 2018 | Go, chess, shogi | self-play only, no human data | | MuZero | 2020 | Atari + board games | plans in a _learned_ model | 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.[^beyond] [^sb-history]: **Sutton & Barto**, §1.7 — Early History of Reinforcement Learning: the two main threads (trial-and-error learning from animal psychology; optimal control and dynamic programming) and the thinner temporal-difference thread that joined them. Trial and error: Thorndike's Law of Effect (1911), Turing's 1948 "pleasure–pain system," Minsky's 1954 SNARC machine and the credit-assignment problem of his 1961 "Steps Toward Artificial Intelligence," the confusion of supervised nets (Rosenblatt; Widrow and Hoff) for RL, and Klopf's (1972) revival of the hedonic, trial-and-error view. Optimal control: Bellman's (1957) dynamic programming, the Bellman equation, MDPs, the curse of dimensionality, and Howard's (1960) policy iteration. Temporal difference: secondary reinforcement, Samuel's (1959) checkers program, Sutton's development of TD and the TD($\lambda$) algorithm (Sutton, 1988), and the convergence of all three threads in Watkins's (1989) Q-learning, with Tesauro's TD-Gammon (1992) following. [^beyond]: Deep reinforcement learning developments past Sutton and Barto's introduction. **DQN**: V. Mnih et al., "Human-level control through deep reinforcement learning," _Nature_ 518 (2015), 529–533 — a convolutional network trained by Q-learning with experience replay and a target network reaches human-level play on 49 Atari games from pixels and score. **AlphaGo**: D. Silver et al., "Mastering the game of Go with deep neural networks and tree search," _Nature_ 529 (2016), 484–489 — deep value/policy networks with Monte Carlo tree search defeat a professional Go player. **AlphaZero**: D. Silver et al., "A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play," _Science_ 362 (2018), 1140–1144 — superhuman play in three games from self-play with no human data. **MuZero**: J. Schrittwieser et al., "Mastering Atari, Go, chess and shogi by planning with a learned model," _Nature_ 588 (2020), 604–609 — planning in a learned dynamics model, without being given the rules. **Fusion control**: J. Degrave et al., "Magnetic control of tokamak plasmas through deep reinforcement learning," _Nature_ 602 (2022), 414–419. **RLHF**: P. Christiano et al., "Deep reinforcement learning from human preferences," _NeurIPS_ (2017); L. Ouyang et al., "Training language models to follow instructions with human feedback" (InstructGPT), _NeurIPS_ (2022) — a policy improved against a learned reward model of human preference judgments. Monte Carlo tree search is also treated in Sutton & Barto itself, §8.11.