Introduction to Reinforcement Learning
What RL is, how it differs from supervised and unsupervised learning, the four elements of an RL system, and a first algorithm — a temporal-difference learner for tic-tac-toe.
- The two distinguishing features of RL: trial-and-error search and delayed reward.
- The exploration–exploitation dilemma and why it does not arise in (pure) supervised/unsupervised learning.
- The four elements — policy, reward signal, value function, model — and the difference between reward (immediate) and value (long-term).
- The tic-tac-toe TD update and the effect of reducing (or not reducing) the step size $\alpha$.
- Why value-function methods use information that evolutionary methods throw away.
1.1 What is reinforcement learning?
Reinforcement learning is learning what to do — how to map situations to actions — so as to maximise a numerical reward signal. The learner is not told which action to take; it must discover which actions yield the most reward by trying them. Actions may affect not only the immediate reward but also the next situation and, through it, all subsequent rewards.
- Trial-and-error search — the agent must try actions to find out what they do.
- Delayed reward — an action's consequences can show up many steps later, so the agent must solve a credit-assignment problem over time.
"Reinforcement learning" names three things at once: a problem, a class of solution methods that work well on that problem, and the field that studies both. Keep the problem separate from the methods — confusing them is, per the book, "the source of many confusions". The problem is formalised (Chapter 3) as the optimal control of incompletely-known Markov decision processes, capturing three aspects in their simplest form: sensation, action, and goal.
RL vs. the other machine-learning paradigms
| Supervised learning | Unsupervised learning | Reinforcement learning | |
|---|---|---|---|
| Feedback | Labelled examples from a knowledgeable supervisor: "the correct action is …" | None — unlabelled data | A scalar reward: evaluative ("how good"), not instructive ("what is right") |
| Goal | Generalise to situations not in the training set | Find hidden structure | Maximise cumulative reward over the long run |
| Data | Fixed, i.i.d. training set | Fixed data set | Generated by the agent's own actions — the agent controls what it sees |
| Explore/exploit? | Does not arise | Does not arise | Central challenge |
| Time | Each example independent | — | Sequential; actions have delayed consequences |
"RL is a kind of unsupervised learning because there are no labels." — No. RL maximises a reward signal; finding structure is at most a useful sub-step. The book calls RL a third paradigm.
Exploration vs. exploitation
To get a lot of reward the agent must exploit actions it already knows are good; to find such actions it must explore actions it has not tried. Neither can be pursued exclusively without failing. On a stochastic task each action must be tried many times to get a reliable estimate of its expected reward. The dilemma "has been intensively studied by mathematicians for many decades, yet remains unresolved" — Chapter 2 studies it in its simplest setting.
RL also takes the whole-problem view: it starts with a complete, interactive, goal-seeking agent (which may itself be a component of a larger system, e.g. a battery-monitoring agent inside a robot) instead of studying isolated sub-problems.
1.2 Examples
The book's examples — a chess master, an adaptive refinery controller, a gazelle calf learning to run, a trash-collecting robot deciding whether to recharge, Phil making breakfast — share the same features:
- Interaction between an active decision-maker and its environment.
- A goal pursued despite uncertainty about the environment.
- Actions affect future states and therefore future options ⇒ need for foresight/planning.
- Effects can't be fully predicted ⇒ the agent must monitor and react.
- The goal is explicit: the agent can judge progress from what it senses.
- The agent uses experience to improve over time.
1.3 Elements of reinforcement learning
1 · Policy $\pi$
Maps perceived states to actions — the agent's way of behaving. A lookup table, a simple function, or an extensive search. May be stochastic. The policy alone is sufficient to determine behaviour.
2 · Reward signal $R$
Defines the goal. Each step the environment sends a single number. The agent's sole objective is to maximise total reward in the long run. The primary basis for changing the policy. Immediate and intrinsic ("pleasure / pain").
3 · Value function $v$
What is good in the long run: the total reward an agent can expect to accumulate starting from a state. Values are predictions of reward. Decisions are made on values, but values are much harder to determine than rewards.
4 · Model (optional)
Mimics the environment: given state and action, predicts next state and reward. Used for planning. Methods using models are model-based; pure trial-and-error learners are model-free.
Rewards are primary; values are secondary (without rewards there could be no values, and the only purpose of estimating values is to get more reward). Yet we choose actions by value, not reward, because we seek the states that yield the most reward over the long run. A state can have low immediate reward and high value (it leads to good states), or vice versa.
"The most important component of almost all reinforcement learning algorithms we consider is a method for efficiently estimating values" — arguably the most important lesson of six decades of RL research.
| Model-free | Model-based | |
|---|---|---|
| Uses a model of the environment? | No — learns directly from experience | Yes — uses (learned or given) model to plan |
| Key strength | No need for an accurate model; simple; building block for model-based methods | Can look ahead / plan without acting |
| Where in the book | Ch. 5 (MC), 6 (TD), 7 (n-step) | Ch. 4 (DP — needs a perfect model), Ch. 8 (Dyna) |
1.4 Limitations and scope
RL relies heavily on the concept of state — the input to policy and value function. The book treats state informally as "whatever information is available to the agent about its environment" and does not address how to construct the state signal; its concern is deciding what to do given the state.
Evolutionary methods vs. value-function methods
Not all solution methods estimate value functions. Evolutionary methods (genetic algorithms, genetic programming, simulated annealing, …) apply many static policies, each interacting over an extended period with its own copy of the environment, then carry the best (and random variations of them) into the next generation.
| Evolutionary methods | Value-function (RL) methods | |
|---|---|---|
| What is evaluated | Whole policies, by final outcome over many episodes | Individual states (or state–actions) |
| When the policy changes | Only after many complete games | During play, after each move |
| Uses within-episode information? | No — ignores which states were visited and which actions taken | Yes |
| Credit assignment | All moves of a won game get credit — even moves that never occurred | Credit flows to the specific states along the trajectory |
| Good when | Policy space small or easy to search; lots of time; agent cannot sense the full state | Most problems: learning while interacting is usually far more efficient |
1.5 Extended example: tic-tac-toe
We play X against an imperfect opponent and treat draws and losses as equally bad. Classical methods struggle:
- Minimax assumes a particular (optimal) opponent — it would never enter a state from which it could lose, even if this opponent always blunders there.
- Dynamic programming could compute the optimal solution, but needs a complete model of the opponent (its move probabilities in every state), which we don't have.
- An evolutionary method would hill-climb in policy space, evaluating each policy over many games.
The value-function approach
- Make a table with one number per board state: the latest estimate of the probability of winning from that state. This is the value function.
- Initialise: three X's in a row → 1; three O's in a row or a full board → 0; all other states → 0.5.
- To move, look at the state each legal move would lead to. Usually move greedily (highest value); occasionally make a random exploratory move.
- After each greedy move, back up the value of the later state to the earlier one:
$\alpha$ is a small positive fraction called the step-size parameter — it controls the rate of learning. This is a temporal-difference (TD) method because the change is driven by the difference $V(S_{t+1}) - V(S_t)$ between estimates at two successive times. Exploratory moves do not trigger learning in the book's version.
- If $\alpha$ is reduced properly over time, the method converges (for any fixed opponent) to the true probabilities of winning under optimal play by us, and its greedy moves are optimal against this opponent.
- If $\alpha$ is not reduced all the way to zero, the player also plays well against opponents that slowly change their play — it keeps tracking.
This trade-off (convergence on stationary problems vs. tracking on nonstationary ones) is developed formally in §2.5.
What the example shows
- Learning while interacting with an environment (the opponent).
- A clear goal with delayed effects — the player learns to set up multi-move traps for a short-sighted opponent, achieving the effects of planning without a model of the opponent and without explicit search.
- It is model-free with respect to the opponent (though it uses the game rules to know which state each move leads to).
- It scales via function approximation: Tesauro's TD-Gammon combined this algorithm with a neural network for backgammon (~1020 states) — generalisation is where supervised learning enters RL.
Our learner (X, moves first) plays a random opponent (O). Values start at 0.5 and are updated with the rule above after every greedy move. Every 250 training games we freeze learning and play 400 greedy games to measure the win rate.
Exercises 1.1 – 1.5 (with model answers)
Ex 1.1 — Self-play: if the algorithm played against itself, with both sides learning, what would happen? Would it learn a different policy?
Both sides keep improving, so each faces a changing (non-stationary) opponent that gets stronger. Instead of learning to exploit one particular imperfect opponent, it tends toward a policy that is good against strong play — approaching minimax-style play (in tic-tac-toe, mostly draws). So yes, it learns a different policy: it no longer exploits a specific opponent's weaknesses.
Ex 1.2 — Symmetries: how could we exploit board symmetries? Should we, if the opponent doesn't?
Map each state to a canonical representative of its symmetry class (8 rotations/reflections) and share one value entry. This shrinks the table and speeds learning because experience in one position generalises to its mirror images. But if the opponent does not play symmetrically, symmetric positions need not have equal value against that opponent — tying them together can then hurt. Symmetric positions are only guaranteed equal value against a symmetric opponent.
Ex 1.3 — Greedy play: would a purely greedy player learn better or worse? What problems might occur?
Usually worse. With no exploration it may never try moves whose current estimates are low but whose true values are high; it can lock into a sub-optimal line forever. (Exploitation without exploration — the core dilemma.) It might only do comparably well if initial values happen to drive sufficient exploration.
Ex 1.4 — Learning from exploration: what two sets of probabilities are learned with and without updating after exploratory moves? Which is better to learn, and which wins more?
Without learning from exploratory moves, values converge to the win probabilities under the greedy (optimal) policy from each state. Learning from all moves gives win probabilities under the actual behaviour policy, including exploration. If we keep exploring, the second set is more accurate about what will actually happen (and is "safer", cf. Sarsa vs. Q-learning in Ch. 6); the first set describes the better policy and, when we act greedily, leads to more wins. This foreshadows off-policy vs. on-policy learning.
Ex 1.5 — Other improvements?
Exploit symmetries; initialise values with prior knowledge; decay exploration and α over time; look ahead more than one move (search) using the known rules; learn a model of the opponent and plan with it; use function approximation to generalise across similar positions; learn from exploratory moves with appropriate correction.
1.7 Early history (three threads)
Optimal control
Bellman (mid-1950s): state, value function, the Bellman equation, dynamic programming, and MDPs (1957). Howard (1960): policy iteration. DP suffers from the curse of dimensionality. Mostly no learning. Full integration with online learning: Watkins (1989).
Trial-and-error learning
Psychology of animal learning: Thorndike's Law of Effect (1911) — actions followed by satisfaction become more likely. Early AI: Minsky's SNARCs, Michie's MENACE for tic-tac-toe, Widrow's "learning with a critic", Klopf's hedonistic neurons — revived RL in the early 1980s.
Temporal-difference learning
Learning driven by differences between successive estimates. Samuel's checkers player (1959), Klopf's generalised reinforcement, the actor–critic of Barto, Sutton & Anderson (1983), Sutton's TD(λ) (1988), Watkins' Q-learning (1989); Tesauro's TD-Gammon (1992).
The three threads came together in the late 1980s to produce modern RL.
Chapter summary & self-test
RL is a computational approach to goal-directed learning from direct interaction, without exemplary supervision or complete models. It uses the MDP framework (states, actions, rewards) to capture cause-and-effect, uncertainty, and explicit goals. Value functions are key — they are what make search in policy space efficient and distinguish RL from evolutionary methods.
Name the two features that most distinguish RL from other kinds of learning.
Trial-and-error search and delayed reward.
Why does the exploration–exploitation dilemma not arise in supervised learning?
Because the data (with correct labels) are given; the learner's choices don't determine what information it receives. In RL, the agent's own actions determine which experience it gets, and the feedback is only evaluative.
Give an example of a state with low reward but high value.
Studying the night before an exam (unpleasant now, leads to high reward later); in chess, sacrificing a piece (immediate loss) to set up checkmate.
Which of the four elements is optional, and what is it used for?
The model of the environment — used for planning (considering possible futures before experiencing them).
In the tic-tac-toe TD rule, what is the role of $\alpha$, and what happens if it is decreased to zero vs. kept constant?
$\alpha$ is the step size (learning rate): the fraction of the TD difference applied each update. Reduced properly over time → converges to true win probabilities against a fixed opponent. Kept constant (not to zero) → never fully converges but keeps adapting to an opponent who slowly changes.
Why is the tic-tac-toe method called "temporal-difference"?
Its update is driven by the difference between estimates at two successive times: $V(S_{t+1}) - V(S_t)$.
What information do evolutionary methods ignore that value-function methods use?
The fact that a policy is a function from states to actions, and which states were visited and which actions were taken during each lifetime/episode. They only use the final outcome.
Who introduced Q-learning, and what did it unite?
Chris Watkins (1989). It fully integrated dynamic programming (optimal control thread) with online trial-and-error and temporal-difference learning.
Chapter quiz — check your understanding
Scored quiz: pick an answer (or type a number) to get instant feedback and an explanation. Questions marked Exam-style give you values to interpret (sweeps, logs, returns, learning curves), the way exam problems do. Your best score is saved in this browser and shown on the home page. "Shuffle & restart" re-orders the questions.