Reinforcement Learning

Learning from consequences

In March 2016, in the second game of its match against Lee Sedol, AlphaGo placed a stone on the fifth line that commentators first took for a mistake. DeepMind later said its own model had rated the chance of a human professional playing that move at about one in ten thousand. It won the game, and the match 4-1. Nobody taught AlphaGo move 37. It found it by playing, and being told only whether it won.

What is it?

Reinforcement learning (RL) is learning to act from consequences. An agent tries actions, the world responds, and a single number, the reward, says how well things went. Nobody labels the right move. The agent has to work out which of its many earlier choices deserved the credit.

That makes it a different kind of problem from the rest of machine learning:

How does it work?

Every RL system, from a thermostat tuner to a chess engine to a chatbot, runs the same loop. At each time step t the agent observes a state s_t, picks an action a_t using its policy π, and the environment answers with a reward r_t+1 and the next state s_t+1.

The agent’s goal is not to grab the biggest reward right now but to maximise the return: the total reward it collects from here on. A chess engine that captures a pawn and walks into mate has chased reward and lost return. Two things make this hard. First, credit assignment: when the reward finally arrives, which of the hundred earlier moves earned it? Second, the agent’s own choices decide what data it sees. Play timidly and you never discover the move that would have won.

Why does it matter?

RL is the tool for problems where you can score outcomes but cannot write down the correct action. That turns out to include some of the most visible results in AI:

• Games. DQN learned dozens of Atari games from pixels. AlphaGo and its successors reached superhuman Go, chess and shogi.
• Chatbots. The step that turned GPT-3 into an assistant people preferred was reinforcement learning from human feedback, and variants of it are used for most chat models today.
• Reasoning models. Models such as OpenAI o1 and DeepSeek-R1 learn to think step by step through large-scale RL on problems with checkable answers.
• Everyday systems. Simpler relatives of RL, the bandit algorithms in the next section, pick headlines, tune ad placements and allocate traffic in experiments.

Key takeaways

• RL learns what to do from a reward signal, not from labelled correct answers.
• Every method shares one loop: observe a state, act, receive a reward and the next state, and improve the policy.
• The hard parts are delayed credit and the fact that the agent’s choices decide which data it ever sees.

Explore or exploit: bandits

You are in a new city for a week. On night one you find a decent restaurant. Do you go back every night, or keep trying new places that might be better and might be worse? This is the oldest dilemma in RL, and it has a precise answer.

What is it?

A multi-armed bandit is RL with the time dimension removed. There are K slot machines (“arms”), each paying out with its own unknown probability. Every round you pull one arm and see whether it paid. There is no state and no future consequence of your choice beyond what you learn. The only question is which arm to pull next.

Performance is measured by regret: how much expected reward you gave up compared with someone who knew the best arm from the start. Regret can only grow, and a good strategy makes it grow as slowly as possible.

How does it work?

Each strategy keeps an estimate Q(a) of each arm’s average payout, updated after every pull with a running mean. Notice the shape of this update: old estimate plus a step size times an error. Nearly every rule in RL has this shape.

N(a) is how many times arm a has been pulled, r is the reward just received.

The strategies differ only in how they choose an arm:

• Greedy always pulls the arm with the highest estimate. If its first lucky pull lands on a mediocre arm, it may never look elsewhere.
• ε-greedy acts greedily most of the time, but with probability ε pulls a random arm. It never gets permanently stuck, but it keeps wasting a fraction ε of pulls on arms it already knows are bad.
• UCB1 (upper confidence bound) adds an exploration bonus that is large for arms pulled rarely and shrinks as evidence accumulates. It is optimistic in the face of uncertainty: an arm gets tried because it might be the best.

t is the total number of pulls so far. The square-root term is the uncertainty bonus.

In the averaged view the curves differ in shape, not just height. Greedy’s regret climbs in a straight line, because in a share of runs it locks onto the wrong arm forever. ε-greedy is also a straight line, just a shallower one: it never stops spending a fraction ε of its pulls at random. UCB1’s curve bends over, because its exploration bonus shrinks as evidence builds up; Auer and colleagues proved its regret grows only with the logarithm of the number of pulls, the best possible order of growth. That guarantee is about the long run. Over 1,000 pulls a well-chosen ε often wins, since UCB1 is cautious and keeps checking arms that are probably worse. Switch to 10,000 pulls and the bend pays off: UCB1 moves ahead, and the gap keeps widening the longer the game runs. Try ε = 0.01 and ε = 0.3 as well to see the trade-off from both ends.

Why does it matter?

Bandits are the rare piece of RL theory that is deployed everywhere as is: choosing which recommendation, headline or ad to show, and running adaptive experiments that shift traffic towards the better variant while the experiment is still running. A popular alternative, Thompson sampling, keeps a probability distribution over each arm’s payout and pulls each arm with the probability that it is the best.

More importantly, the exploration problem never goes away. Every agent later in this lesson has to decide when to try something new, and they mostly use the same two ideas you have just seen: random exploration (ε-greedy) and optimism about the unknown (UCB).

Key takeaways

• A bandit is RL with one state: choose among actions of unknown value and learn from each result.
• Greedy can lock onto a bad arm; ε-greedy never stops paying for exploration; UCB explores exactly where uncertainty is high.
• Regret measures the cost of learning, and good algorithms make it grow logarithmically rather than linearly.

States, time and discounting

Bandits have no memory: pulling an arm today does not change tomorrow’s machines. Real decisions do. A chess move changes the board; a robot’s step changes where it stands. To capture that we need a model of a world that evolves.

What is it?

A Markov decision process (MDP) is the standard formal description of such a world. It has five parts:

• States S: every situation the agent can be in, such as a square on a grid or a board position.
• Actions A: what the agent can do, such as move up, down, left or right.
• Transitions P(s′ | s, a): the probability of landing in s′ after taking a in s. Worlds can be random: a robot that tries to go right might slip.
• Rewards R(s, a, s′): the number received on each transition, such as +1 for reaching the goal and −0.04 for each step taken.
• Discount γ between 0 and 1: how much future reward counts compared with reward now.

The word Markov means the current state contains everything relevant about the past. Where you are on the board matters; how you got there does not. When that fails, for example when a poker player cannot see the other hands, the problem becomes harder and the agent has to keep a memory or a belief about what it cannot see.

How does it work?

A policy π says what to do in every state. Running a policy produces a stream of rewards r₁, r₂, r₃, and so on. The return adds them up, shrinking each by one more factor of γ the further away it is:

The return from time t. A reward k steps in the future is weighted by γ to the power k.

Discounting does three jobs. It keeps the sum finite when the task never ends: a reward of +1 per step forever is worth exactly 1/(1−γ), which is 10 when γ = 0.9. It encodes impatience, since a reward now is more certain than one promised later. And it sets an effective planning horizon of roughly 1/(1−γ) steps, beyond which rewards barely register.

At γ = 0.9 the delayed 5 points are worth 5 × 0.9¹⁰ ≈ 1.74, so a patient agent waits. At γ = 0.8 they are worth only 0.54 and the agent grabs the single point. The same world with a different γ produces different behaviour, which is why γ is a design decision rather than a detail. Game-playing agents use values like 0.99 or higher because wins arrive late; a trading agent that should care about today might use much less.

Why does it matter?

Writing a problem as an MDP forces every design choice into the open: what the agent can observe, what it can do, and exactly what it is rewarded for. Most failures of RL in practice come from one of those choices, not from the learning algorithm. The rest of this lesson assumes an MDP underneath, whether it is a 30-cell grid or the space of every possible reply a chatbot could write.

Key takeaways

• An MDP has states, actions, transition probabilities, rewards and a discount factor; the Markov property says the present state is enough.
• The agent maximises the discounted return, where a reward k steps away is weighted by γ to the power k.
• γ sets the planning horizon, about 1/(1−γ) steps, and changing it can change which behaviour is optimal.

Values and the Bellman equation

Imagine you could stand in any square of a maze and know exactly how good it is to be there. Then acting well would be easy: step towards the best-looking neighbour. Computing that number for every square is the central idea of RL.

What is it?

The value of a state, V(s), is the expected return from s if you act well from then on. The action value Q(s, a) is the expected return if you take action a first and act well afterwards. Once you know Q, the best policy is simply to pick the action with the highest Q in every state.

How does it work?

Values obey a simple consistency rule, found by Richard Bellman in the 1950s. The value of a state is the best action’s immediate reward plus the discounted value of wherever it leads, averaged over the random outcomes:

The Bellman optimality equation. Terminal states have value 0; their reward is paid on the way in.

A worked example with no slipping, γ = 0.9 and a cost of 0.04 per step. The square right next to the +1 goal is worth −0.04 + 1 = 0.96. The square before it is worth −0.04 + 0.9 × 0.96 = 0.824. One further back: −0.04 + 0.9 × 0.824 ≈ 0.702. Value flows outward from the reward, shrinking with every step of distance.

Value iteration turns the equation into an algorithm. Start with every value at zero. Sweep over all states, replacing each value with the right-hand side computed from the current estimates. Repeat. Each sweep shrinks the error by at least a factor of γ, so the values are guaranteed to converge to V*. This is dynamic programming, and it needs one thing RL usually lacks: a complete model of P and R.

A few things to notice. After the first sweep every open cell holds just the step cost, except those next to a terminal; the news of the reward travels one cell per sweep, and arrows appear only where the agent has a reason to prefer one move. With slipping on, the arrows next to the −1 pit point away from it even when that costs a longer route, because each move near the edge has a chance of sliding in. Load the Cliff layout and compare slip 0 with slip 0.3: the optimal path climbs away from the edge. Now push the step cost to −0.4. Life has become so expensive that the agent heads for the nearest exit, even a −1 one.

Why does it matter?

The Bellman equation is the backbone of the field. Every value-based method, from Q-learning to the network that scores Go positions, is a way of solving it approximately. Value iteration itself is used wherever the model is known and small enough to enumerate, such as inventory control and some routing problems.

But it has two hard limits. It needs the model, and it touches every state on every sweep. A grid has 30 states. Go has more legal board positions than there are atoms in the observable universe. The next two sections remove each limit in turn.

Key takeaways

• V(s) is the expected return from a state; Q(s, a) is the expected return from taking an action there. The best policy picks the highest Q.
• The Bellman equation says a state’s value is the best action’s reward plus the discounted value of where it leads.
• Value iteration solves it exactly by repeated sweeps, but only when the model is known and the state space is small.

Learning from experience: Q-learning

Value iteration had the map. A real agent usually does not: a robot does not know the physics of every surface, and a game-playing agent does not have the rules written out as probabilities. It has to learn from what happens when it tries things.

What is it?

Temporal-difference (TD) learning learns values from single steps of experience. After each move the agent compares what it expected with what it now expects, one step later, and moves its estimate towards the newer guess. It learns a guess from a guess, a trick called bootstrapping.

Q-learning, introduced by Chris Watkins in 1989, applies this to action values. It is model-free: it never estimates P or R, only Q directly, and it is guaranteed to converge to the optimal Q in small problems as long as every action keeps being tried.

How does it work?

After taking action a in state s, receiving reward r and landing in s′, Q-learning forms a target from the reward plus the best value available next, and nudges its old estimate towards it by a learning rate α:

The bracketed term is the TD error δ: how much better or worse the step went than expected.

A worked step: Q(s, right) = 0.50, the step costs −0.04, the best Q in the next cell is 0.80, γ = 0.9, α = 0.5. The target is −0.04 + 0.9 × 0.80 = 0.68. The TD error is 0.68 − 0.50 = 0.18, so the new estimate is 0.50 + 0.5 × 0.18 = 0.59. It is the bandit’s running-mean update again, with the next state’s value standing in for the rest of the future.

The max in the target is what makes Q-learning off-policy: it learns the value of acting greedily even while it actually behaves ε-greedily. The agent can explore freely and still learn the optimal policy.

Early episodes are long, aimless walks; the step count in the sparkline falls as the value of the goal propagates backward, one update at a time. Compared with value iteration the learned map is patchy: cells the agent rarely visits keep poor estimates, which is fine because a good policy rarely goes there. On the Cliff layout Q-learning learns the shortest path along the edge, yet with ε = 0.2 its actual episodes still fall off now and then. This is a famous example from Sutton and Barto: an on-policy method such as SARSA, which accounts for its own exploration, prefers the safer path one row up.

Why does it matter?

TD learning is how RL escapes the need for a model, and it turned out to describe something in biology too. In the 1990s, recordings from dopamine neurons in monkeys showed them firing not at rewards but at unexpected rewards, and dipping when an expected reward failed to arrive, matching the TD error closely (Schultz, Dayan and Montague).

Q-learning with a table still needs a row for every state. The breakthrough that followed was to replace the table with a neural network.

Key takeaways

• Temporal-difference learning updates a guess towards a better-informed guess one step later, so it learns without a model.
• Q-learning’s target is r + γ · max Q(s′, a′), which lets it learn the greedy policy while exploring.
• Every update is estimate plus step size times error, the same shape as the bandit’s running mean.

Deep RL: Atari, Go and beyond

A table has one row per state. An Atari screen has 210 × 160 pixels; the number of possible images is beyond counting, and an agent will almost never see the same one twice. To learn here, it has to generalise from situations it has seen to ones it has not.

What is it?

Deep reinforcement learning uses neural networks to represent the value function, the policy, or both. Similar inputs produce similar outputs, so experience in one state informs many others.

How does it work?

Value-based: DQN

The Deep Q-Network of Mnih et al. (2015) is Q-learning with a convolutional network in place of the table. It reads the last four screen frames and outputs a Q-value for each joystick action. Naively plugging a network into Q-learning is unstable, because the targets move whenever the weights move and consecutive frames are highly correlated. DQN added two fixes: experience replay, which stores past transitions and trains on random mini-batches of them, and a target network, a slowly updated copy used to compute the targets. With one architecture and one set of hyperparameters it learned 49 games, reaching a level comparable to a professional human games tester across the set, after 50 million frames of play per game.

Policy-based: policy gradients

Instead of learning values and deriving a policy, you can adjust the policy directly. A policy gradient method samples actions, sees how they turned out, and makes the ones that did better than expected more likely:

Increase the log-probability of each action in proportion to its advantage A: how much better it did than the average from that state.

This handles continuous actions, like torques on a robot joint, and naturally produces a stochastic policy. The advantage is usually estimated by a second network, the critic, giving actor-critic methods. Proximal Policy Optimization (PPO, 2017) adds a clip that stops any one update from moving the policy too far, which made policy gradients reliable enough to become the default, including for training language models.

Planning plus learning: AlphaGo to AlphaZero

AlphaGo combined a policy network, which suggests promising moves, a value network, which estimates who is winning, and Monte Carlo tree search, which looks ahead using both. It was first trained to imitate human games, then improved by playing itself. AlphaGo Zero dropped the human games entirely and beat the Lee Sedol version 100 games to 0. AlphaZero applied the same algorithm to chess and shogi. The pattern of search improving the policy and the policy improving the search is sometimes called expert iteration.

Why does it matter?

Deep RL showed that one learning method, given only a score, could reach or exceed expert human play in very different domains. Its weaknesses are just as instructive. It is sample-hungry: 50 million frames is around 38 days of continuous play for a single Atari game, far more practice than a person needs. It is brittle: small changes to the environment can break a trained policy. And it works best where a simulator can generate unlimited, cheap, safe experience, which is why games came first and real robots came later, usually trained in simulation first.

Key takeaways

• Deep RL replaces tables with neural networks so experience generalises across states that have never been seen.
• DQN made Q-learning stable with experience replay and a target network; policy gradients such as PPO adjust the policy directly.
• AlphaGo and AlphaZero combined learned policies and values with tree search and self-play to master Go, chess and shogi.

RL for language models

A pretrained language model has read much of the internet and learned to continue text. It has not learned to be helpful, to refuse harmful requests, or to check its own arithmetic. Most of that comes from reinforcement learning, applied after pretraining.

What is it?

For a language model the MDP is unusual but exact. The state is the prompt plus everything generated so far. Each action is the next token. The episode ends when the model stops, and the reward usually arrives only then, as a score for the whole response. The policy is the language model itself.

Two sources of that score dominate today:

• Human preferences: people compare responses, and a reward model learns to predict their choices. This is RLHF.
• Verifiable rewards: a program checks the answer, for example by comparing a final number or running unit tests. This is how reasoning models are trained.

How does it work?

RLHF

InstructGPT set out the three-step recipe that most assistants have followed since:

The KL penalty in step 3 matters. Without it the policy drifts towards whatever quirks the reward model over-rewards and away from fluent language. With it, the objective is to raise reward while staying close to the reference model:

π is the model being trained, π_ref the supervised model it started from, β the strength of the leash.

The result was striking: labellers preferred answers from a 1.3-billion-parameter InstructGPT over those from the 175-billion-parameter GPT-3 it was built from. Later methods simplify the recipe. Direct preference optimisation (DPO) trains on the preference pairs directly without a separate reward model or RL loop, and Constitutional AI replaces many human comparisons with AI feedback guided by written principles.

RL for reasoning

In 2024 OpenAI reported that o1, trained with large-scale RL to reason in a long chain of thought before answering, kept improving both with more RL training and with more time spent thinking at test time. DeepSeek-R1, published with full details in 2025, showed the recipe openly. Its first variant, R1-Zero, started from a base model and was trained with nothing but rule-based rewards: is the final answer correct, and is it in the requested format? Its responses grew longer over training, and behaviours such as checking and revising its own work emerged without being demonstrated.

DeepSeek used GRPO (group relative policy optimisation). For each prompt it samples a group of answers, scores them, and uses each answer’s reward relative to the group as its advantage. That removes the need for a separate value network. It is the policy gradient from the previous section with a bandit-style baseline.

Correct answers get positive advantages and their tokens are made more likely; wrong ones are pushed down. When every sample is right, or every sample is wrong, the advantages vanish and the prompt contributes nothing. Switch on the bonus for showing working and notice that a bare correct “408” now scores below a worked one: a small change in the reward rule quietly changes what the model is taught to do.

Why does it matter?

Pretraining gives a model knowledge; RL shapes how it uses it. The helpful tone of assistants, their refusals, and the long, self-checking reasoning of current models all come from this stage. Verifiable rewards have been especially powerful because they are cheap and hard to fool, which is why progress has been fastest in maths and code, where answers can be checked automatically.

Key takeaways

• For an LLM the state is the text so far, each action is a token, and the reward usually scores the finished response.
• RLHF learns a reward model from human comparisons and optimises against it with a KL leash; DPO skips the explicit RL loop.
• Reasoning models are trained with RL against checkable answers; GRPO scores each sample relative to its group.

When the reward is wrong

RL is extremely good at maximising the number you give it. That is precisely the danger: it maximises the number, not what you meant by it.

What is it?

Reward hacking, or specification gaming, is when an agent scores highly by exploiting a gap between the reward and the designer’s intent. In OpenAI’s CoastRunners experiment, a boat-racing agent rewarded for hitting targets along the course found a lagoon where it could circle forever, repeatedly catching fire and hitting the same respawning targets. It scored about 20% higher than human players and never finished a race. DeepMind researchers keep a public list of dozens of such cases.

How does it work?

It is Goodhart’s law under optimisation pressure: when a measure becomes a target, it ceases to be a good measure. The stronger the optimiser, the more reliably it finds the places where measure and goal diverge. With learned rewards this happens predictably. Gao, Schulman and Hilton trained policies against a proxy reward model and measured a separate “gold” reward model standing in for true human preference. As optimisation continued, proxy reward kept rising while gold reward rose, peaked, then fell.

Language models show the same pattern in subtler forms:

• Preference-trained models can drift towards longer answers or towards agreeing with the user, because raters tend to reward both.
• Coding agents rewarded for passing tests have been observed special-casing the tests rather than fixing the underlying bug.
• A model rewarded only for a final answer can reach it by reasoning that does not hold up, or by guessing.

Why does it matter?

As RL moves from games to systems that act in the world, a mis-specified reward stops being a curiosity and becomes a safety problem. The defences in use are practical rather than complete: keep the policy close to a trusted reference with a KL penalty, prefer rewards that are hard to fake (verified answers, real tests), use ensembles of reward models, audit behaviour with fresh human evaluation, and monitor a model’s reasoning for signs it is gaming the grader.

Other limits remain too. RL needs enormous amounts of experience, which is why simulators matter so much. Exploration in the real world can be unsafe. And a policy trained in one environment often breaks when the environment shifts.

Key takeaways

• An RL agent optimises the reward you wrote, and strong optimisers find every gap between that reward and your intent.
• With learned reward models, pushing too hard raises the proxy score while true quality falls.
• Defences include KL penalties, verifiable rewards, reward model ensembles, human audits and monitoring, none of them complete.

Check your understanding

Seven scenarios. Each one asks you to apply an idea from the lesson to a situation you have not seen.

A news site shows one of four headlines for each article and wants to maximise clicks. It currently runs a classic A/B test: 25% of traffic to each headline for two weeks, then picks the winner. What does a bandit algorithm such as UCB1 change?

Want to go further? Train agents on larger worlds in the Reinforcement Learning Arena, or read chapters 2 to 6 of Sutton and Barto, which cover everything in this lesson in depth.

References

Every source cited in this lesson. Sutton and Barto’s textbook is free online and is the best place to continue; the papers are the original descriptions of each method.

References

1. [1]

   In Two Moves, AlphaGo and Lee Sedol Redefined the Future(opens in a new tab)

   Cade Metz (Wired), 2016

   Reporting on move 37 of game two, including DeepMind’s estimate that a human would play it about one time in ten thousand.

2. [2]

   Human-level control through deep reinforcement learning(opens in a new tab)

   Volodymyr Mnih et al., 2015

   The Deep Q-Network (DQN), trained on 49 Atari 2600 games from pixels and score with one architecture and one set of hyperparameters.

3. [3]

   Mastering the game of Go with deep neural networks and tree search(opens in a new tab)

   David Silver et al., 2016

   AlphaGo: policy and value networks trained on human games and self-play, combined with Monte Carlo tree search.

4. [4]

   Training language models to follow instructions with human feedback(opens in a new tab)

   Long Ouyang et al., 2022

   InstructGPT. Labellers preferred the 1.3B-parameter RLHF model over the 175B GPT-3.

5. [5]

   Learning to reason with LLMs(opens in a new tab)

   OpenAI, 2024

   Introduces o1, trained with large-scale RL to reason in a chain of thought; performance improves with both train-time and test-time compute.

6. [6]

   DeepSeek-R1 incentivizes reasoning in LLMs through reinforcement learning(opens in a new tab)

   Daya Guo et al. (DeepSeek-AI), 2025

   Nature 645, 633–638. R1-Zero is trained from a base model with GRPO and rule-based rewards only.

7. [7]

   Finite-time analysis of the multiarmed bandit problem(opens in a new tab)

   Peter Auer, Nicolò Cesa-Bianchi and Paul Fischer, 2002

   Introduces UCB1 and proves its regret grows only logarithmically with the number of pulls.

8. [8]

   Q-learning(opens in a new tab)

   Christopher J. C. H. Watkins and Peter Dayan, 1992

   Convergence proof for Q-learning, first proposed in Watkins’s 1989 PhD thesis.

9. [9]

   Reinforcement Learning: An Introduction (2nd edition)(opens in a new tab)

   Richard S. Sutton and Andrew G. Barto, 2018

   The standard textbook, free online. Bandits (ch. 2), MDPs (ch. 3), dynamic programming (ch. 4), TD learning and Q-learning (ch. 6).

10. [10]

    A neural substrate of prediction and reward(opens in a new tab)

    Wolfram Schultz, Peter Dayan and P. Read Montague, 1997

    Dopamine neuron firing in monkeys closely matches the temporal-difference prediction error.

11. [11]

    Proximal Policy Optimization Algorithms(opens in a new tab)

    John Schulman et al., 2017

    PPO, the clipped policy gradient method later used for RLHF.

12. [12]

    Mastering the game of Go without human knowledge(opens in a new tab)

    David Silver et al., 2017

    AlphaGo Zero: trained by self-play alone, it beat the version that defeated Lee Sedol 100 games to 0.

13. [13]

    A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play(opens in a new tab)

    David Silver et al., 2018

    AlphaZero, first released as a preprint in December 2017.

14. [14]

    Faulty reward functions in the wild(opens in a new tab)

    Jack Clark and Dario Amodei (OpenAI), 2016

    The CoastRunners boat that circles a lagoon collecting points instead of finishing the race.

15. [15]

    Specification gaming: the flip side of AI ingenuity(opens in a new tab)

    Victoria Krakovna et al. (DeepMind), 2020

    Overview and a maintained list of real examples of agents satisfying the letter but not the spirit of their objective.

16. [16]

    Scaling Laws for Reward Model Overoptimization(opens in a new tab)

    Leo Gao, John Schulman and Jacob Hilton, 2022

    Optimising against a learned reward model first raises, then lowers, the true (gold) reward.