What is reinforcement learning?

Nobody gave you a dataset of correct handlebar angles when you learned to ride a bicycle. You got on, wobbled, fell, and tried something slightly different. The only feedback was how it went: you stayed up for a few more meters, or you scraped your knee. Out of that thin, delayed, noisy signal, your brain built a skill.

Reinforcement learning (RL) is the study of learning from that kind of signal. A learner acts, the world responds, and a number says how well things are going. No one ever says what the right action was. This chapter sets out the vocabulary of the field, lets you drive a small world by hand and then watch a program learn to drive it, and names the three problems that make RL hard. The rest of the course builds on these ideas. By the end of it you will see the same loop running inside a chatbot: it writes an answer, the answer is scored, and the model is nudged toward answers that score well.

The agent–environment loop

Every RL problem has two parts. The agent is the learner and decision-maker. The environment is everything else: the part of the world the agent interacts with but does not control directly. They talk to each other in a loop of discrete time steps $t = 0, 1, 2, \dots$:

                    action a_t
          ┌───────────────────────────────┐
          │                               ▼
     ┌─────────┐                   ┌──────────────┐
     │  agent  │                   │ environment  │
     └─────────┘                   └──────────────┘
          ▲                               │
          └───────────────────────────────┘
              reward r_t, next state s_{t+1}

1. The agent observes the state $s_t$: whatever information it gets about the current situation.
2. It picks an action $a_t$.
3. The environment responds with a reward $r_t$, a single number saying how good that step was, and moves to a new state $s_{t+1}$.
4. Repeat.

The reward $r_t$ is the one that arrives after action $a_t$. (Sutton & Barto’s textbook calls it $R_{t+1}$. Same thing, shifted index; see the notation page.) Many tasks come in episodes that end: a game is won or lost, a robot reaches its target, a chatbot finishes its reply. The sequence $s_0, a_0, r_0, s_1, a_1, r_1, \dots$ of one episode is a trajectory.

In code, the loop is this short:

s = env.reset()                      # start an episode
done = False
while not done:
    a = agent.act(s)                 # decide
    s_next, r, done = env.step(a)    # the world responds
    agent.learn(s, a, r, s_next)     # improve from the experience
    s = s_next

That is the whole interface. You will write this loop in this chapter’s lab (without the learn line: learning starts in Chapter 2). Every algorithm in the course, up to the ones that train reasoning models, is a choice of what goes inside act and learn.

Where to draw the line

The agent–environment boundary is a modeling choice, not a physical one. For a robot, the motors and even the robot’s own body are usually part of the environment. The agent is the decision-making software, and its “actions” are the voltages it sends. If you know thermodynamics, it is the same move as choosing what counts as the system and what counts as the surroundings. The rule of thumb is that anything the agent cannot change at will is environment. That includes the reward: the agent cannot just decide to be rewarded. The reward is computed outside its control, even when, as with an animal’s pleasure and pain, it is physically produced inside the body.

The same loop, everywhere

The plasma row is real: in 2022 DeepMind and EPFL reported a controller trained with RL in simulation that then shaped plasmas on the TCV tokamak (Degrave et al., Nature). The last row is where this course is heading.

A tiny world to think with

Abstract definitions only stick once you use them, so here is one small world that we will use for the rest of the chapter and its lab. It is a gridworld (Chapters 3, 4 and 5 use gridworlds too):

    col:  0 1 2 3 4 5 6
    row 0 . . . . . . .      the long way round
    row 1 . # # # # # .
    row 2 S . . . . . G      the bridge
    row 3 . P P P P P .      pits under the bridge

• The agent starts on S. Each step it chooses up, down, left or right.
• Landing on the goal G gives reward $+1$ and ends the episode. Landing in a pit P gives $-1$ and also ends it.
• Every other move gives the step reward, which is 0 unless we change it. Walking into a wall # or off the edge leaves you where you are.
• Optionally, the floor is slippery. With probability equal to the slip probability, your move is replaced by one of the two perpendicular moves, each equally likely. Press “right” on the bridge and you may slide down into a pit.

There are two sensible routes. The bridge reaches G in 6 moves, with pits right underneath. The long way round goes up, along the top row and down: 10 moves, and safe. Which one is better? It depends, and working out what it depends on is a good first lesson in RL.

Reward and return

The agent does not want a large reward now. It wants a large total over time. Choosing the bridge gives a reward of 0 for five steps, and only then $+1$. The thing to maximize is the return: the sum of future rewards, each one discounted by a factor $\gamma \in [0, 1]$ per step of delay:

where $T$ is the length of the episode: it ends on arriving in state $s_T$, so the last reward is $r_{T-1}$. With $\gamma = 1$ this is the plain sum. With $\gamma = 0.9$ a reward that arrives 10 steps from now counts for $0.9^{10} \approx 0.35$ of its face value.

A worked example

Take $\gamma = 0.9$ and step reward 0, with no slipping. Walking the bridge, you collect $r_0 = r_1 = r_2 = r_3 = r_4 = 0$ and then $r_5 = +1$:

So the bridge’s return is $G_0 = 0.9^5 \approx 0.590$. The long way round reaches G on its 10th move, so $G_0 = 0.9^9 \approx 0.387$. With no risk involved, discounting makes the shorter route better, which is what we want.

Now make every ordinary move cost a little: step reward $-0.04$. The bridge pays $-0.04$ five times, then $+1$:

The long way round pays $-0.04$ nine times, then $+1$: $G_0 = -0.04 \cdot \frac{1 - 0.9^9}{1 - 0.9} + 0.9^9 = -0.245 + 0.387 = 0.142$. A step penalty is a second, more explicit way of saying “hurry up”.

Why discount at all?

There are three reasons, and they are worth keeping apart.

1. Preference for sooner. A reward now is often worth more than the same reward later: money earns interest, and a robot’s battery may run out.
2. Uncertainty. If there is a probability $1 - \gamma$ at each step that the episode is cut short, then the expected undiscounted return equals the discounted return. Discounting is then just honest bookkeeping.
3. Mathematics. In a task that never ends, the plain sum of rewards can be infinite. With $\gamma < 1$ and bounded rewards it cannot: if every $\lvert r_t \rvert \le r_\text{max}$, then $\lvert G_t \rvert \le r_\text{max}/(1 - \gamma)$. A geometric series is the only tool needed.

The value of $\gamma$ sets how far ahead the agent looks. With $\gamma = 0$ only the immediate reward counts (a completely myopic agent). As $\gamma$ approaches 1, distant rewards count almost as much as near ones. Chapter 3 makes this precise as an effective horizon of about $1/(1-\gamma)$ steps (Markov decision processes).

One small identity is worth noticing now, because the next four chapters are built on it. Pull out the first term of the return:

The return from now is the reward now plus the discounted return from the next step. It is also the fastest way to compute returns: go backwards through the episode. In Chapter 3, taking expectations of this recursion gives the Bellman equation.

Drive it yourself, then watch an agent learn

The demo below is the gridworld above. Start in You drive mode. Move with the arrow keys (click the grid first), the on-screen buttons, or by tapping a square next to the agent. Below the grid you will see each reward $r_t$ as it arrives, the weight $\gamma^t$ it gets, and your running return $G_0$. The “best possible” number is what a perfect player would get on average with the current settings. The demo computes it exactly by planning with full knowledge of the rules, the way Chapter 4 will teach you.

What you should have noticed

Randomness changes the right answer. With a dry floor, the bridge is clearly better (0.590 against 0.387). With slip 0.2, each of the five moves along the bridge drops you into a pit with probability 0.1, so you survive the crossing with probability only $0.9^5 \approx 0.59$. The long way round now wins. The map has not changed, only the dynamics. Exercise 1.5 finds the crossover by hand, and the lab finds it by simulation.

The agent knows nothing at first. In Let an agent learn mode, the agent starts with no idea what the colored squares mean. It sees only which square it is on, and the rewards. It runs an algorithm called Q-learning, which you will build yourself in Chapter 5. For now, treat it as a black box that keeps a table of estimates of how good each move is in each square, and nudges those estimates after every step. When “show what the agent has learned” is ticked, the arrows are its current choice in each square and the colors are its estimates of the return from there. With slip 0 and $\gamma = 0.9$, once it has learned to use the bridge you can read the numbers off the grid: 0.59 on S, 0.66 on the next square, then 0.73, 0.81, 0.90 and 1.00 next to G. Those are $0.9^5, 0.9^4, \dots, 0.9^0$: the returns from each square of the bridge.

The curve flattens below the line. The learning curve shows the return of each episode. Even after learning, the average stays below “best possible”, because the agent still picks a random move a fraction ε of the time (10% by default) so that it keeps trying things. On the bridge a random move can be fatal. Slide ε to 0 after it has learned and the curve climbs to the line.

Sometimes it gets stuck on the long way round. Reset the agent a few times with slip 0. In most runs it finds the bridge within a few dozen episodes. In some runs it settles on the long route and stays there for thousands of episodes: the arrow on S points up, and with ε set to 0 its return sits at 0.387 instead of 0.590. It found something that works, and finding out that the bridge is better would mean walking the bridge, which its current choices never do. That is the exploration problem, which we come back to below. Tick optimistic start and the problem goes away. Exercise 1.6 asks you why.

Policy, value and model: the rest of the vocabulary

You have now met four of the core words (agent, environment, state, action) and two more (reward, return). Three more complete the vocabulary of the whole field. Here they are, lightly; later chapters make each one precise.

Policy: how the agent behaves

A policy is the agent’s rule for choosing actions: a mapping from states to actions. It can be deterministic (“on the bridge, go right”) or stochastic, giving a probability for each action. We write $\pi(a \mid s)$ for the probability that policy $\pi$ chooses action $a$ in state $s$. The lab has two hand-written deterministic policies, bridge and safe, and a stochastic one, random, which gives each of the four actions probability $1/4$ in every state. The goal of RL, in one line, is to find a policy that gets as much return as possible, on average.

Note that a policy must say what to do in every state, not just along its favorite path. On a slippery floor you can end up anywhere.

Value: how good it is to be here

The return of a single episode is random: on a slippery floor the same policy sometimes reaches G and sometimes falls. What we care about is its average. The value of a state $s$ under a policy $\pi$ is the expected return if you start in $s$ and follow $\pi$ from then on:

Some numbers, all at $\gamma = 0.9$ from the start square:

The “best possible” value at slip 0.2 is a little higher than the safe policy’s. The optimal policy knows a trick or two that the safe one does not (Exercise 1.4 asks you to find them). The random policy’s value does not depend on the slip at all. Can you see why? (A uniformly random action, sent through a slippery floor, is still uniformly random.)

A close cousin, the action value $Q^\pi(s, a)$, is the expected return if you take action $a$ in $s$ first and follow $\pi$ afterwards. The colored squares and arrows in the demo show the agent’s estimates of action values: the color is its largest estimated $Q$ in that square and the arrow is the action with that value. (To be exact, Q-learning estimates the action values of the best policy, not of the policy it is currently following. Chapter 5 explains why.) Chapter 3 defines value functions properly and shows how to compute them. In the lab you will estimate $V^\pi(\text{S})$ the direct way, by averaging the returns of many episodes. That is called a Monte Carlo estimate, and Chapter 5 builds on it.

Value is the long-term counterpart of reward. Reward says how good this step was. Value says how good this situation is, counting everything that is likely to follow. A move with zero reward can lead to a state of high value (the square next to G), and vice versa.

Model: the agent’s own picture of the world

A model is the agent’s internal prediction of how the environment behaves: given $s$ and $a$, what $s'$ and $r$ come next. If you have a model, you can plan, trying out action sequences in your head before acting. The “best possible” number in the demo comes from planning with a perfect model (the demo knows the rules). Methods that learn or use a model are model-based. Methods that learn values or policies directly from experience, like the Q-learning agent in the demo, are model-free. Chapter 4 plans with a known model (Dynamic programming). Chapter 10 shows how AlphaZero and MuZero combine learned models with search (The wider RL landscape).

What makes RL different from other machine learning

You likely know supervised learning: fit a function to labeled examples, such as images with the correct class or sentences with their translations. And unsupervised learning: find structure (clusters, low-dimensional manifolds, a density) in unlabeled data. RL is neither, and the differences explain most of what makes it hard.

1. Evaluative feedback, not instructive feedback

A label is instructive: it says what the right answer was. A reward is evaluative: it says how good your answer was, and nothing about what you should have done instead. Compare two ways of marking an exam. In one you get back the correct answers. In the other you get back only “62%”. From the second you learn something, but you have to work out what by trying different answers and seeing how the score moves. That trial and error is built into RL. If the agent never tries an action, it never learns what that action would have earned.

2. Delayed consequences

In supervised learning, every prediction is judged on the spot. In RL, an action’s consequences can unfold over many steps. Stepping onto the bridge earns 0 right away. Whether it was a good idea is decided five steps later, by a $+1$ or a $-1$. A chess move might win or lose the game forty moves later. The agent must trade immediate reward against future reward, and it has to work out which earlier actions deserve the credit.

3. Your actions change your data

Supervised learning assumes the training examples are drawn independently from a fixed distribution. In RL, the agent’s own behavior decides which data it sees. An agent that always takes the long way round collects experience about the top row and almost none about the bridge. It then has nothing to update its beliefs about the bridge with. You saw exactly this in the demo, when an agent got stuck on the long route. The data are not independent (each state depends on the previous one), and their distribution shifts every time the policy changes. The objective and the data distribution are tied together, and that causes problems all the way up to LLM training. As Chapter 9 explains, one bad update produces a bad policy, which collects bad data, which makes the next update worse.

Three problems that make RL hard

Credit assignment

An episode ends with $+1$ or $-1$. Which of the many actions before it deserve the credit or the blame? That is the credit assignment problem. In the gridworld it is mild: episodes are short and the reward is clear. In Go, one bit of feedback (won or lost) arrives after about 200 moves, and the decisive mistake may have been move 37. For a reasoning model, one reward (was the final answer correct?) arrives after thousands of tokens of working.

RL’s main answer is the value function. If you can estimate how good every intermediate situation is, you can judge each action by whether it made things better or worse, without waiting for the end. Chapter 8 makes this precise as the advantage (Actor-critic and advantage estimation).

Exploration versus exploitation

To get reward, the agent should exploit what it already knows works. To find something better, it must explore: try actions whose value it is unsure of, and accept that some will turn out worse. You cannot do both with the same action. Picture choosing a restaurant: the favorite you know, or the new place that might be better or might be awful.

The stuck agent in the demo is a case of too little exploration. On S its arrow points up, and on the first bridge square its arrow points back to S, because retreating to the route it knows is the best thing it has seen. Its random moves (10% of the time) rarely carry it past both of those squares, so it seldom gets far enough along the bridge to learn that the bridge is better. Optimistic start fixes this in an instructive way. The agent begins by assuming every untried move is worth $+1$, so it keeps trying moves until experience talks it out of them. Chapter 2 studies exploration in its purest form (Bandits), including why optimism works and how to explore with provable guarantees.

Generalization

Our gridworld has 23 squares you can stand on, so the agent can keep a separate estimate for each. Real problems are not like that. Go has about $10^{170}$ legal positions. An Atari screen is $210 \times 160$ pixels. A language model’s “state” is any possible text prefix, which is astronomically many. The agent will almost never see the same state twice, so it must generalize: use what it learned in states it has seen to act well in states it has not. That is why neural networks entered RL, and why the combination is powerful but unstable (Chapter 6). Pretrained language models are an extreme case. They arrive with an enormous amount of general knowledge, which is a large part of why RL on top of them works at all.

The reward hypothesis, and how rewards go wrong

Everything above treats a single number per step as enough to say what we want. That is a strong claim, and it has a name. Sutton and Barto state the reward hypothesis like this (Reinforcement Learning: An Introduction, section 3.2):

That all of what we mean by goals and purposes can be well thought of as the maximization of the expected value of the cumulative sum of a received scalar signal (called reward).

It is a working hypothesis, not a theorem, and it can fail. Some goals are about risk, not averages: “never crash” is not the same as “crash rarely on average”. Some trade off several objectives in ways no fixed weighting captures. Bowling, Martin, Abel and Dabney (2023) worked out exactly which conditions a set of preferences over behaviors must satisfy to be expressible as expected cumulative reward. The hypothesis is still productive: a single scalar interface lets one algorithm handle Atari, robots and chatbots. But it puts all the weight on getting the reward right. That is much harder than it sounds.

Specification gaming

An RL agent optimizes the reward you wrote, not the goal you meant. When the two differ, a good optimizer finds the difference. In a well-known example from 2016, OpenAI trained an agent on the boat-racing game CoastRunners. The intended goal was to win the race, but the reward was the game’s score, which comes from hitting targets along the course. The agent found a lagoon where a few targets kept reappearing. It kept circling, catching fire and crashing into other boats, and never finished the race, yet scored higher than by racing. DeepMind researchers keep a public list of such cases. In one, an agent rewarded for the height of the bottom face of a red Lego block flipped the block over instead of stacking it on the blue one (Krakovna et al., 2020). The name for this behavior is specification gaming, or reward hacking.

You can produce both kinds of failure in the demo:

• The “helpful” bonus tile. Suppose you want to encourage the agent to explore the top row, so you put a $+0.3$ bonus there. Tick it and let the agent learn. It walks to the coin and steps on and off it until time runs out. Why finish for $+1$ when looping is worth more? With $\gamma = 0.9$, looping is worth $0.3\,\gamma^4 (1 + \gamma^2 + \gamma^4 + \dots) = 0.3 \cdot 0.9^4/(1 - 0.81) \approx 1.04$ from the start, against 0.590 for the bridge. Exercise 1.8 works through this.
• A positive step reward. Set the step reward to $+0.2$. “Reward the agent for staying alive” sounds harmless. The agent’s answer is never to reach the goal at all. Exercise 1.7 shows that with $\gamma < 1$ the agent prefers to finish exactly when the step reward is below $1 - \gamma$, however far away the goal is.

Neither agent is broken. Both are doing exactly what they were told. The bug is in the reward.

A short, honest history

RL draws on three older threads: the psychology of trial-and-error learning (Thorndike’s “law of effect”, 1911), optimal control, and the computer science of search and planning. Some milestones:

• 1950s: Bellman and dynamic programming. Richard Bellman formulated sequential decision problems with the recursive structure you saw in $G_t = r_t + \gamma G_{t+1}$, and solved them by dynamic programming (his 1957 book Dynamic Programming). This is Chapter 4’s material.
• 1959: Samuel’s checkers player. Arthur Samuel’s program improved by playing against itself and adjusting its evaluation of board positions toward later, better-informed evaluations. That idea later became temporal-difference learning.
• 1988–1989: TD learning and Q-learning. Sutton formalized learning from temporal differences (1988), and Watkins introduced Q-learning in his 1989 PhD thesis. Q-learning is the algorithm running in the demo (Chapter 5).
• 1992–1995: TD-Gammon. Gerald Tesauro trained a neural network by TD learning and self-play to play backgammon close to the level of the best human players. It was a striking early success, and for years a hard one to repeat in other games.
• 2013–2015: DQN. DeepMind’s deep Q-network learned to play Atari games from raw pixels. The 2015 Nature paper reports one network architecture and one set of hyperparameters reaching a level comparable to a professional human games tester across 49 games. This started the modern era of deep RL (Chapter 6).
• 2016: AlphaGo. AlphaGo defeated Lee Sedol 4–1 at Go, a game long considered beyond reach. It combined supervised learning on human games, RL from self-play and tree search. AlphaGo Zero (2017) and AlphaZero (2018) then dropped the human games entirely (Chapter 10).
• 2017: Learning rewards from human preferences. Christiano and colleagues trained agents from human comparisons between pairs of behavior clips instead of a hand-written reward. This is the ancestor of RLHF (Chapter 12).
• 2022: InstructGPT and ChatGPT. OpenAI fine-tuned GPT-3 with RL from human feedback (RLHF): a reward model trained on human rankings of responses, then optimization with PPO. Labelers preferred the outputs of a 1.3B-parameter InstructGPT model to those of the 175B-parameter GPT-3 (Ouyang et al., 2022). OpenAI said ChatGPT, released later that year, was trained with the same methods, with small differences in how the data was collected.
• 2024–2025: Reasoning models. OpenAI’s o1 (September 2024) was trained with large-scale RL to produce a long chain of thought before answering. OpenAI reports that performance kept improving both with more RL training and with more thinking time at inference. In January 2025 DeepSeek published R1, with an open description of the recipe: RL with automatically checkable rewards on math and code problems. One variant, R1-Zero, was trained by RL directly from a base model with no supervised fine-tuning (Chapter 15).

The honest version of this story has long quiet stretches. For decades RL worked mostly on small or simulated problems. Many headline successes needed a perfect simulator, enormous amounts of experience or compute, and careful engineering, and many results were fragile to reproduce. RL for language models works as well as it does largely because pretraining supplies a policy that is already very good, so RL only has to steer it. Keep both halves in mind: RL is powerful, and it is finicky.

Summary

• RL is learning to act from evaluative feedback. An agent takes actions in an environment, which returns rewards and new states. The whole interface is reset() and step(a).
• The agent’s objective is the return, the discounted sum of future rewards: $G_t = \sum_k \gamma^k r_{t+k} = r_t + \gamma G_{t+1}$. The discount $\gamma$ sets how far ahead it looks.
• A policy $\pi(a \mid s)$ says how to act. A value $V^\pi(s)$ is the expected return from a state when following $\pi$. A model predicts what the environment will do. The goal of RL is a policy with maximal expected return.
• RL differs from supervised learning in three ways. Feedback says how good your action was, not what the right one was. Consequences can be delayed. The learner’s own actions decide what data it sees.
• The three core challenges are credit assignment (which actions earned the reward), exploration versus exploitation (try new things or use what works), and generalization (act well in states never seen before).
• What the best behavior is depends on the dynamics and on $\gamma$, not just the map. In the gridworld the bridge wins on a dry floor and loses once the slip probability passes about 0.07.
• The reward hypothesis says a scalar reward can express any goal. In practice, the agent optimizes the reward you wrote, and specification gaming is what happens when that differs from what you meant. This is a central problem for RL on language models.

Exercises

cd 01-what-is-rl
python -m pytest -q          # your code: tests fail until you fill in the TODOs
RL_SOLUTIONS=1 python -m pytest -q   # reference solutions: all pass

Further reading

• Sutton & Barto (2018), Reinforcement Learning: An Introduction, 2nd ed., ch. 1 and 3.1–3.2. The standard textbook, free online. Chapter 1 covers this chapter’s ground with a tic-tac-toe example, and section 3.2 has the reward hypothesis.
• OpenAI Spinning Up (2018), Part 1: Key Concepts in RL. A compact, deep-RL-flavored tour of the same vocabulary, with notation close to ours.
• Krakovna et al. (2020), Specification gaming: the flip side of AI ingenuity. A short essay on why reward hacking happens, with a link to a list of real examples. Read it before Chapter 19.
• Clark & Amodei (2016), Faulty reward functions in the wild. The CoastRunners boat, with video.
• Mnih et al. (2015), Human-level control through deep reinforcement learning. The DQN paper. Readable now for the setup and results; Chapter 6 explains the method.
• Ouyang et al. (2022), Training language models to follow instructions with human feedback. InstructGPT. Skim the introduction and Figure 2 now to see where the course is going.
• Bowling, Martin, Abel & Dabney (2023), Settling the reward hypothesis. For when you want to know exactly when a scalar reward is enough.

Next: the simplest RL problem there is, with no states at all, just a row of slot machines. It is the cleanest place to study exploration. On to Chapter 2: Bandits.