Bain: learning by “groping and experiment”
Woodworth traces the idea of trial-and-error learning back to Alexander Bain’s discussion in the 1850s.
Three threads of reinforcement learning
Reinforcement learning did not begin as one neat branch of machine learning. For more than a century, three groups worked on different versions of the same question without yet sharing a language:
- Psychologists asked how consequences change behaviour.
- Control theorists asked how a sequence of decisions can maximise a long-term objective.
- Prediction researchers asked how one estimate can learn from the next.
Modern RL appeared when those three threads were finally braided together.
Three problems looking for each other
Section titled “Three problems looking for each other”Trial and error: what should I do again?
Section titled “Trial and error: what should I do again?”This is the oldest thread. An action followed by a satisfying result becomes more likely; an action followed by discomfort becomes less likely. It sounds simple, but it creates the defining RL dilemma: the learner must act to discover which actions are good, and every experiment has a real consequence.
This thread gives RL its agent, actions, rewards, and the tension between exploration and exploitation.
Optimal control: what is this situation worth?
Section titled “Optimal control: what is this situation worth?”Control theory approached the problem from mathematics rather than psychology. Given a model of a changing system, which sequence of decisions produces the best total outcome? Richard Bellman’s answer was to break the problem into smaller problems and assign each situation a value.
This thread gives RL Markov decision processes, value functions, Bellman equations, and dynamic programming.
Temporal difference: was my prediction too high or too low?
Section titled “Temporal difference: was my prediction too high or too low?”The third thread learns by comparing two successive predictions. You do not have to wait until a chess game—or a life—ends before updating an earlier estimate. If the next moment looks better than expected, revise upward now; if it looks worse, revise downward.
This thread gives RL bootstrapping: improving an estimate using another estimate before the final outcome is known.
Follow the threads
Section titled “Follow the threads”Use the filters to isolate one lineage, then return to All threads and watch the ideas begin to cross. The brighter cards mark the moments that changed the direction of the field.
Showing all 30 moments
-
-
Lloyd Morgan names “trial and error”
The British ethologist uses the term explicitly to describe what he observes in animal behaviour.
-
Thorndike’s Law of Effect
Responses followed by satisfaction become more likely to recur; those followed by discomfort, less likely. This is the first succinct statement of the principle.
-
“Reinforcement” enters the vocabulary
The word first appears in this context in the English translation of Pavlov’s monograph on conditioned reflexes.
-
Ross builds a maze-learning machine
Possibly the earliest electro-mechanical learner: it finds its way through a simple maze and remembers the path in switch settings.
-
Turing’s “pleasure–pain system”
A report sketches a machine that makes random choices where action is undetermined, cancelling them on pain and fixing them on pleasure.
-
Shannon: a program that improves its own evaluation
Shannon suggests a chess program could improve online by modifying its evaluation function—the seed of Samuel’s method.
-
Walter’s tortoise and Shannon’s Theseus
Mechanical creatures learn simple behaviours; Shannon’s maze-running mouse finds a route by trial and error while the maze remembers through magnets and relays.
-
SNARCs and simulated neural learning
Minsky describes Stochastic Neural-Analog Reinforcement Calculators, while Farley and Clark simulate a network that learns by trial and error.
-
Minsky links secondary reinforcement to machines
A stimulus paired with a primary reinforcer can itself become predictive—a psychological idea with consequences for artificial learning systems.
-
Bellman: dynamic programming and MDPs
Bellman defines the value function and Bellman equation, then introduces the discrete stochastic case: Markov decision processes.
-
Samuel’s checkers player
The first learning method to implement temporal-difference ideas is developed with no reference to Minsky or animal learning.
-
Howard’s policy iteration
A method for solving Markov decision processes that remains an essential element of modern reinforcement-learning theory.
-
Minsky names the credit-assignment problem
How should credit for success be distributed among the many decisions that produced it?
-
MENACE and STeLLA
Michie’s matchbox engine learns tic-tac-toe with coloured beads. Andreae’s STeLLA learns by trial and error with an internal model of the world.
-
“Reinforcement learning” enters engineering
Waltz and Fu—followed by Mendel, Fu, and others—use the terms for engineering applications of trial-and-error learning.
-
BOXES balances a pole
Michie and Chambers build a controller that learns from a failure signal alone—an early RL task under incomplete knowledge.
-
Klopf revives the hedonic thread
Klopf argues that the drive to get a result from the environment was being lost as research turned toward supervised learning.
-
Learning with a critic
Widrow, Gupta, and Maitra modify LMS to learn from success and failure instead of examples. Learning automata and the k-armed bandit join the thread.
-
Holland’s adaptive systems
Selection-based classifier systems lead to a bucket-brigade credit-assignment algorithm with a family resemblance to temporal difference.
-
Witten publishes the first TD rule
What we now call tabular TD(0) appears inside an adaptive controller for Markov decision processes.
-
Learning from successive predictions
Sutton develops learning rules driven by changes between temporally successive predictions, with links back to animal learning.
-
A TD model of classical conditioning
Sutton and Barto build a psychological model of classical conditioning on temporal-difference learning.
-
The actor–critic architecture
Barto, Sutton, and Anderson combine temporal-difference learning with trial and error, then return to the pole-balancing problem.
-
Werbos argues for interrelating DP and learning
An explicit case for joining dynamic programming with learning methods—and for connecting both to neural and cognitive mechanisms.
-
TD(λ) separates prediction from control
Sutton treats temporal-difference learning as a general prediction method, introduces TD(λ), and proves convergence properties.
-
Q-learning unites the threads
Watkins integrates trial-and-error learning, optimal control, and temporal difference inside the Markov decision process formalism.
-
TD-Gammon
Tesauro combines temporal-difference learning with a neural network for backgammon’s enormous state space, eventually reaching elite human play.
-
Dopamine looks like a TD signal
Researchers find a striking similarity between temporal-difference errors and dopamine-neuron activity, opening a new thread in neuroscience.
-
Neurodynamic programming
Bertsekas and Tsitsiklis develop the relationship between dynamic programming and artificial neural networks that Watkins helped open.
1989: the braid
Section titled “1989: the braid”Watkins’s Q-learning is the hinge of the story. It learns by trial and error, uses the value-based structure of optimal control, and updates estimates by a temporal difference. After 1989, “reinforcement learning” increasingly names this combined field rather than any one of its ancestors.
The familiar agent–environment loop is what the braid looks like in compact form:
An agent observes a situation , chooses an action , and the environment returns a reward and a new situation. A policy chooses actions; a value estimate predicts long-term reward. Every chapter that follows changes one part of this loop or one way of learning from it.
The map of the book is hidden in the history
Section titled “The map of the book is hidden in the history”| Historical thread | Question it contributes | Where it reappears |
|---|---|---|
| Trial and error | Which action should I try? | Multi-armed bandits and exploration |
| Optimal control | What are future outcomes worth now? | MDPs and dynamic programming |
| Temporal difference | How can one prediction improve another? | TD learning and eligibility traces |
| The braid | How can an agent learn control from experience? | Q-learning, DQNs, and actor–critic |
Where next
Section titled “Where next”The next chapter removes state, delayed consequences, and almost everything else. What remains is the trial-and-error problem in its purest form: multi-armed bandits.
References
Section titled “References”- Sutton, R. S. & Barto, A. G. Reinforcement Learning: An Introduction, 2nd ed., §1.7.
- Three threads of reinforcement learning—interactive timeline.