Reinforcement Learning
Every model in this archive learned from a labelled answer key. This one gets nothing but consequences — a reward when it does well, a cost when it does not, and the job of working out which of its own actions put it there.
Learning From Consequences
Everything so far in this archive has been supervised: you hand the model rows of features with the correct answer attached, and it learns to reproduce that mapping. The signal is immediate and specific — “for this input, the answer was that”.
Reinforcement learning removes the answer key. An agent takes an action, the world changes, and it receives a single number — a reward — that may arrive long after the decision that caused it. It is never told which action was wrong. It has to infer that from outcomes.
Win a game in 40 moves and which of those 40 moves deserves the credit? The reward is unambiguous; attributing it across a long sequence of decisions is the hard part, and it is what separates RL from everything else in this archive.
That changes the data too. In supervised learning the dataset is fixed before training begins. Here the agent's own choices determine what data it sees next — explore badly and you train on a distorted view of the world.
“Here is the input; here is the correct output.” Dense, immediate, independent per example.
“You scored 0.7.” Sparse, delayed, and correlated with every choice you just made.
The Problem Structure
Almost every RL problem is formalised the same way — as a Markov decision process. Five ingredients, and then one rule for choosing what to do.
Everything the agent can observe about where it currently is. On a board, the position of every piece.
The moves available in a state. Often shared across states, but not always.
The scalar feedback after each transition. This is the whole specification of what you actually want.
How the world moves when you act — possibly stochastic, which is why the same action need not give the same result twice.
How much a reward now is worth versus the same reward later. In .
The thing being learned: a rule mapping states to actions. The goal is the policy that maximises total discounted reward.
Not the next reward — the discounted sum of everything that follows. That single change is what makes an agent willing to accept a small cost now for a large payoff later.
The Bandit: Explore or Exploit?
Strip away states and sequences and one hard question remains. You face several slot machines, each with an unknown payout rate. Every pull is either experience or money — never both.
Pull the machine that looks best so far and you collect the reward you already understand (exploitation). Pull a different one and you learn something that might change your mind (exploration). Spend all your turns exploiting and you may never discover the better machine. Spend them all exploring and you never collect.
Usually take the best-known action; occasionally, at random, take something else. Crude, and remarkably hard to beat on many problems.
The mechanism that makes this work is the running average. Each machine's estimated value updates a little toward each new observation, so early noise gets averaged out rather than believed:
Estimate, plus a fraction of the surprise — the gap between what you expected and what you got. That prediction error shape reappears in every RL algorithm, right up to the modern deep ones.
Locks onto whatever looked good in the first few pulls. Often a permanently wrong answer.
Learns each machine's true rate perfectly, and cashes in on none of it.
Buys information at a controlled, decaying price. Neither extreme, and better than both.
Every RL algorithm inherits this problem. The bandit is where you meet it without the distraction of long sequences and delayed reward.
The Grid World
Now give the agent a body and a map. It starts top-left, wants the goal bottom-right, and must avoid the pit. Shading shows how good each cell is; the dot re-walks the learned route on a loop. Drag the discount factor to see what patience does to the map.
Each cell holds the total reward the agent expects from there onward · the walk never enters the pit
Value Iteration
Those numbers in the grid were not learned by trial and error. They were computed directly, by sweeping the same update over and over until it stops changing:
Read it in words: the value of a state is the best immediate reward available, plus the discounted value of wherever that action lands you. The definition is recursive — value is expressed in terms of value — and that is exactly why iteration works. Start every cell at zero and sweep.
After one sweep, only cells adjacent to the goal have picked up its reward. After two, their neighbours have. Value propagates backward through the grid one ring at a time, which is precisely what the γ slider above lets you watch — a low discount stops the wave early; a high one carries it all the way to the start.
Once you know how good every state is, the best move is just the one leading to the best next state. That is the greedy walk the dot is running.
You know the transition probabilities, so you can iterate the equation directly — what this page does. Needs a model of the world.
You do not know the transitions, so you estimate values from experience instead — Q-learning and its relatives. Needs only the ability to act and observe.
Q-learning nudges its estimate by the gap between what it expected and what it got — the identical prediction-error move as the bandit's running average — only now the target is reward plus the value of the next state.
From A Grid To Everything Else
The 4×4 grid is where RL is tractable and honest: you can compute the true values and see the agent get it right. Real problems drop both guarantees. State spaces become enormous or continuous, and the transition model is unavailable.
The classical answer is to stop storing a value per state and instead approximate the value function with something that generalises — which is where this archive closes its loop. Topic 07 built a function approximator that learns from a gradient; swap the supervised loss for the Bellman error and you have deep reinforcement learning.
That combination is powerful and notoriously unstable. The targets move as the network updates, the data is heavily correlated because consecutive states resemble each other, and the exploration/exploitation tension from the bandit never goes away. Most of the engineering in modern RL exists to manage exactly those three problems.
Reward design deserves its own warning. The agent optimises precisely the number you wrote down — not the outcome you intended. Specify it carelessly and it will find the technically-correct, practically-wrong behaviour with unfailing enthusiasm.
- • No answer key — only consequences, often delayed far from the decision that caused them.
- • An MDP is states, actions, rewards, transitions and a discount; the policy is what you learn.
- • Exploration buys information; exploitation spends it. You need both, balanced.
- • Every algorithm here learns from a prediction error — the same idea as the bandit's running average.
- • You get exactly the reward you specify, which is rarely exactly the behaviour you wanted.
Adapted from MLU-Explain (Amazon, CC BY-SA 4.0).