Machine Learning
Topic 33 · Beyond the basics · ⏱ about 4 h

Reinforcement Learning

Learning by trial, error and reward.

Show:
In this topic
Beginner

The RL setup

Reinforcement learning (RL) is learning by trial and error. There is no dataset of correct answers. Instead, an agent interacts with an environment and learns from the consequences of its actions.

Agent(policy π)Environmentaction aₜnext state sₜ₊₁ and reward rₜ₊₁
The reinforcement-learning loop: the agent acts, the environment responds with a new state and a reward, and the agent learns to maximise total reward.

The interaction proceeds in a loop. At each time step, the agent observes the current state of the environment, for example the position of the pieces in a game. It chooses an action, such as a move. The environment responds by moving to a new state and giving the agent a reward, a number that is positive for good outcomes and negative for bad ones. Then the loop repeats. The agent's goal is to learn a policy, a rule for choosing actions in each state, that collects as much total reward as possible over time.

An important subtlety is that rewards often arrive long after the actions that earned them. In chess, the only reward might come at the very end, for winning or losing, yet it depends on every move made along the way. To capture the idea that rewards in the near future matter more than rewards in the distant future, RL uses the discounted return:

Gt=rt+1+γ rt+2+γ2rt+3+…(0≤γ<1). G_t = r_{t+1} + \gamma\, r_{t+2} + \gamma^2 r_{t+3} + \dots \qquad (0 \le \gamma < 1).

The discount factor γ\gamma (gamma) shrinks rewards the further away they are: with γ=0.9\gamma = 0.9, a reward two steps away is worth 0.810.81 of its face value. A γ\gamma close to 0 makes the agent short-sighted, while a γ\gamma close to 1 makes it plan far ahead. This setup is formalised mathematically as a Markov decision process.

RL also faces a dilemma that supervised learning does not: exploration versus exploitation. Should the agent exploit what it already knows, choosing the action that has worked best so far, or should it explore other actions that might turn out to be even better? Exploiting too early can lock the agent into a mediocre strategy; exploring too much wastes time on bad actions. A simple and widely used compromise is the ε-greedy strategy: most of the time, take the best-known action, but with a small probability ε\varepsilon (say 10%), take a random action instead.

Interactive: this part runs in your browser.

Interactive. Discounting: a reward later is worth less now. Change γ and the rewards.
Beginner

Watch it: Reinforcement learning: values spread back from the goal

A short narrated animation. Press ▶ Play, or step through it with ⏮ ⏭. Tick 🔊 narrate to hear each step.

Interactive: this part runs in your browser.

Beginner

Main approaches

There are several families of reinforcement-learning methods, which differ in what the agent learns.

Value-based methods learn how good each action is. Specifically, they learn the Q-function, Q(s,a)Q(s, a), the expected total discounted reward of taking action aa in state ss and acting well afterwards. Once the agent knows QQ, choosing an action is easy: pick the one with the highest Q-value. The classic algorithm, Q-learning, improves its estimate after every step by nudging Q(s,a)Q(s,a) towards the reward just received plus the discounted value of the best action available in the new state:

Q(s,a)←Q(s,a)+α[r+γmax⁡a′Q(s′,a′)−Q(s,a)]. Q(s,a) \leftarrow Q(s,a) + \alpha\big[r + \gamma\max_{a'}Q(s',a') - Q(s,a)\big].

The bracket is the difference between a slightly better-informed estimate and the old one, and α\alpha is a learning rate. In 2015, DeepMind's DQN combined Q-learning with a deep neural network and learned to play dozens of Atari games directly from the screen pixels.

Policy-based methods skip the Q-function and adjust the policy directly. They increase the probability of actions that led to high returns and decrease the probability of actions that led to low returns, using gradient ascent on the expected reward. REINFORCE is the classic example, and PPO (proximal policy optimisation), which adds safeguards against making changes that are too large, is one of the most widely used RL algorithms today.

Actor–critic methods combine both ideas. The actor is a policy that chooses actions, and the critic is a value function that judges how good those actions were. The critic's judgements give the actor a much less noisy learning signal than raw returns, which makes learning faster and more stable.

Model-based methods learn, or are given, a model of how the environment works, and use it to plan ahead by simulating possible futures. AlphaGo and AlphaZero combined deep networks with a search through possible future moves and reached superhuman play in Go, chess and shogi.

FamilyWhat it learnsExamples
Value-basedQ(s,a)Q(s, a); act greedilyQ-learning, DQN
Policy-basedthe policy directlyREINFORCE, PPO
Actor–critica policy and a value functionA2C, SAC
Model-baseda model of the environment, used for planningAlphaZero, MuZero

RL has also become central to modern language models. In reinforcement learning from human feedback (RLHF), people compare pairs of model responses, a reward model is trained to predict which responses people prefer, and the language model is then optimised, often with PPO, to produce responses the reward model scores highly.

Try it

Try it: Q-learning in a grid world

The agent starts at S and must reach the goal while avoiding pits. Each cell shows its best Q-value and greedy action. Run episodes and watch value spread backwards from the goal. Compare with the optimal solution from value iteration.

Interactive: this part runs in your browser.

Intermediate · Maths

MDPs, value functions and the Bellman equations

📐 Maths you'll need: m-prob · m-notation
💡 The idea in plain words

The value of a situation = the reward you get now + the (discounted) value of where you end up next. That one recursive idea, the Bellman equation, lets you compute long-term values by repeatedly looking just one step ahead.

🔤 Symbols in this section
s, a, s′s,\ a,\ s'state, action, next state
P(s′∣s,a)P(s'\mid s,a)transition probability
R(s,a)R(s,a)reward
γ\gammadiscount factor (0 to 1)
π(a∣s)\pi(a\mid s)policy
Vπ(s), Qπ(s,a)V^\pi(s),\ Q^\pi(s,a)value of a state / of a state-action pair
T\mathcal TBellman operator

This section states the reinforcement-learning problem precisely and derives the Bellman equations, the foundation on which almost every RL algorithm is built.

A Markov decision process (MDP) is described by five ingredients: a set of states S\mathcal S; a set of actions A\mathcal A; transition probabilities P(s′∣s,a)P(s'\mid s, a), giving the chance of reaching state s′s' after taking action aa in state ss; a reward function R(s,a)R(s, a); and a discount factor γ\gamma. "Markov" means that the next state depends only on the current state and action, not on the whole history. The agent's behaviour is described by a policy π(a∣s)\pi(a\mid s), the probability of choosing action aa in state ss, and its return from time tt is Gt=∑k≥0γkrt+k+1G_t = \sum_{k\ge0}\gamma^k r_{t+k+1}.

Two functions measure how good it is to be in a situation when following policy π\pi. The state-value function is the expected return starting from state ss, and the action-value function is the expected return after taking action aa in state ss:

Vπ(s)=Eπ[Gt∣st=s],Qπ(s,a)=Eπ[Gt∣st=s,at=a]. V^\pi(s) = \mathbb E_\pi[G_t\mid s_t = s], \qquad Q^\pi(s,a) = \mathbb E_\pi[G_t\mid s_t = s, a_t = a].

The Bellman expectation equation. The return has a simple recursive structure: the return from now equals the next reward plus γ\gamma times the return from the next step, Gt=rt+1+γGt+1G_t = r_{t+1} + \gamma G_{t+1}. Taking expectations of both sides, averaging over the actions the policy might choose and the states the environment might move to, gives an equation that links the value of a state to the values of its possible successors:

Vπ(s)=∑aπ(a∣s)[R(s,a)+γ∑s′P(s′∣s,a) Vπ(s′)]. V^\pi(s) = \sum_a\pi(a\mid s)\Big[R(s,a) + \gamma\sum_{s'}P(s'\mid s,a)\,V^\pi(s')\Big].

In words: the value of a state is the expected immediate reward plus the discounted expected value of wherever you end up next. This one-step relationship means long-term values can be computed by repeatedly looking just one step ahead.

The Bellman optimality equations. For the best possible policy, instead of averaging over the policy's choices, we take the best action:

V∗(s)=max⁡a[R(s,a)+γ∑s′P(s′∣s,a)V∗(s′)] V^*(s) = \max_a\Big[R(s,a) + \gamma\sum_{s'}P(s'\mid s,a)V^*(s')\Big]
Q∗(s,a)=R(s,a)+γ∑s′P(s′∣s,a)max⁡a′Q∗(s′,a′) Q^*(s,a) = R(s,a) + \gamma\sum_{s'}P(s'\mid s,a)\max_{a'}Q^*(s',a')

Once Q∗Q^* is known, the optimal policy is simply to choose π∗(s)=arg⁡max⁡aQ∗(s,a)\pi^*(s) = \arg\max_a Q^*(s,a) in every state.

Value iteration. If we know the transition probabilities and rewards, we can solve the optimality equation by starting from any guess V0V_0 (for example all zeros) and repeatedly applying its right-hand side, Vk+1=TVkV_{k+1} = \mathcal T V_k, where T\mathcal T is called the Bellman optimality operator. Why does this converge? Because T\mathcal T is a contraction: applying it to any two value functions brings them closer together by at least a factor γ\gamma, in the sense that ∥TU−TV∥∞≤γ∥U−V∥∞\lVert\mathcal T U - \mathcal T V\rVert_\infty \le \gamma\lVert U - V\rVert_\infty (the largest difference over all states shrinks by γ\gamma). By the Banach fixed-point theorem, repeatedly applying a contraction converges to its unique fixed point, which here is V∗V^*, and the error shrinks geometrically, by a factor γ\gamma per sweep. An alternative, policy iteration, alternates between computing the exact value of the current policy and improving the policy by acting greedily with respect to it; it converges in a finite number of iterations.

Key takeaway. V(s) = immediate reward + γ × expected next value; iterating the Bellman optimality operator converges to V* because it is a γ-contraction.
Advanced

Q-learning, DQN, policy gradients and PPO

📐 Maths you'll need: m-calculus · m-prob · m-stats
💡 The idea in plain words

Without a model of the world, the agent learns from its own experience. Q-learning nudges its estimate toward "reward + best estimate of what comes next". Policy-gradient methods instead make good actions more likely, in proportion to how much better than average they turned out. PPO adds a safety rail so each update doesn't change the policy too much.

🔤 Symbols in this section
δ\deltaTD error: target − current estimate
α\alphalearning rate
θ, θ−\theta,\ \theta^-network weights and target-network weights
∇θlog⁡πθ\nabla_\theta\log\pi_\thetadirection that makes the action more likely
A(s,a)A(s,a)advantage: how much better than average
rt(θ)r_t(\theta)new/old policy probability ratio
ϵ\epsilonPPO clip range

In most real problems, the agent doesn't know the transition probabilities, so it can't run value iteration directly. It must learn from experience: the transitions (s,a,r,s′)(s, a, r, s') it actually observes. This section derives the main model-free algorithms.

Q-learning. The optimality equation says that Q∗(s,a)Q^*(s, a) should equal r+γmax⁡a′Q∗(s′,a′)r + \gamma\max_{a'}Q^*(s', a') on average. Q-learning uses each observed transition as a single noisy sample of that target and moves its estimate a step of size α\alpha towards it. The difference between the target and the current estimate is called the temporal-difference (TD) error:

δ=r+γmax⁡a′Q(s′,a′)−Q(s,a),Q(s,a)←Q(s,a)+α δ. \delta = r + \gamma\max_{a'}Q(s', a') - Q(s,a), \qquad Q(s,a) \leftarrow Q(s,a) + \alpha\,\delta.

If δ\delta is positive, the outcome was better than expected, so the estimate is raised; if negative, it is lowered. Q-learning is off-policy: it learns the value of acting optimally even while the agent is behaving exploratorily (for example ε-greedily), because the target uses the best next action, not the one actually taken. For a table of Q-values, it is proven to converge to Q∗Q^*, provided every state–action pair keeps being visited and the step sizes shrink appropriately (their sum is infinite but the sum of their squares is finite). The on-policy variant, SARSA, uses Q(s′,a′)Q(s', a') for the action the agent actually takes next.

Deep Q-networks (DQN). For large problems, such as video games where the state is a screen image, a table is impossible, so DQN represents QQ with a neural network QθQ_\theta and trains it to minimise the squared TD error:

(r+γmax⁡a′Qθ−(s′,a′)−Qθ(s,a))2. \Big(r + \gamma\max_{a'}Q_{\theta^-}(s',a') - Q_\theta(s,a)\Big)^2.

Naively training a network this way is unstable, and DQN adds two stabilisers. An experience replay buffer stores past transitions and trains on random samples from it, which breaks the strong correlations between consecutive steps. A target network θ−\theta^-, a copy of the network that is updated only occasionally, computes the targets, so that the targets don't shift every time the network changes. A known flaw is that the max operator tends to overestimate values (it picks whichever estimate happens to be too high), and Double DQN reduces this by using one network to choose the action and another to evaluate it.

Policy gradients. Instead of learning values, we can parameterise the policy directly as πθ(a∣s)\pi_\theta(a\mid s), for example with a neural network that outputs action probabilities, and climb the gradient of the expected return J(θ)J(\theta). The policy gradient theorem gives that gradient in a form we can estimate from experience:

∇θJ(θ)=Eπθ[∑t∇θlog⁡πθ(at∣st) (Gt−b(st))]. \nabla_\theta J(\theta) = \mathbb E_{\pi_\theta}\Big[\sum_t \nabla_\theta\log\pi_\theta(a_t\mid s_t)\,\big(G_t - b(s_t)\big)\Big].

It rests on the "log-derivative trick", ∇p=p ∇log⁡p\nabla p = p\,\nabla\log p, which turns the gradient of an expectation into an expectation we can sample. The meaning is intuitive: ∇θlog⁡πθ(at∣st)\nabla_\theta\log\pi_\theta(a_t\mid s_t) is the direction that makes action ata_t more likely, and we move in that direction in proportion to how good the outcome was. The baseline b(s)b(s) is subtracted to reduce noise; it can be shown not to change the expected gradient, only its variance. The usual baseline is the state value V(s)V(s), in which case Gt−V(st)G_t - V(s_t) estimates the advantage A(s,a)=Q(s,a)−V(s)A(s, a) = Q(s, a) - V(s), how much better this action was than average. Learning VV alongside the policy gives the actor–critic methods.

PPO. Policy gradients can be destabilised by a single large update that changes the policy drastically. Proximal policy optimisation limits each update. It compares the new and old probabilities of each action through the ratio rt(θ)=πθ(at∣st)/πθold(at∣st)r_t(\theta) = \pi_\theta(a_t\mid s_t)/\pi_{\theta_{\text{old}}}(a_t\mid s_t) and maximises

LCLIP(θ)=Et[min⁡(rtA^t, clip⁡(rt,1−ϵ,1+ϵ) A^t)], L^{\text{CLIP}}(\theta) = \mathbb E_t\Big[\min\big(r_t\hat A_t,\ \operatorname{clip}(r_t, 1-\epsilon, 1+\epsilon)\,\hat A_t\big)\Big],

with ϵ\epsilon typically around 0.2. The clipping removes any incentive to push the ratio outside the range from 1−ϵ1-\epsilon to 1+ϵ1+\epsilon, so each update can only change the policy a little. In RLHF for language models, PPO (or alternatives such as DPO, which optimise human preferences more directly) is used to improve the model's score from a learned reward model, together with a penalty, based on the KL divergence, that keeps the model from drifting too far from its original behaviour.

Key takeaway. Q-learning: Q ← Q + αδ; policy gradient: increase log π(a|s) in proportion to the advantage; PPO clips the update ratio to [1 − ε, 1 + ε].
Code

Code: value iteration and Q-learning on a grid world

A self-contained 4×4 grid world (no extra libraries): reach the goal, avoid the pit. Value iteration uses the model; Q-learning learns from experience alone.

Python · NumPy from scratch
import numpy as np

# 4x4 grid. Start top-left (0), goal bottom-right (15) = +1, pit at 5 = -1, each step -0.01
N, GOAL, PIT, GAMMA = 4, 15, 5, 0.95
ACTIONS = [(-1, 0), (1, 0), (0, -1), (0, 1)]            # up, down, left, right
ARROWS = "^v<>"

def step(s, a):
    if s in (GOAL, PIT):
        return s, 0.0, True
    r, c = divmod(s, N)
    dr, dc = ACTIONS[a]
    r, c = min(max(r + dr, 0), N - 1), min(max(c + dc, 0), N - 1)
    s2 = r * N + c
    reward = 1.0 if s2 == GOAL else -1.0 if s2 == PIT else -0.01
    return s2, reward, s2 in (GOAL, PIT)

# ---- Value iteration (model-based, deterministic transitions) ----
V = np.zeros(N * N)
for it in range(200):
    V_new = np.array([max(r + GAMMA * V[s2] * (not done)
                          for s2, r, done in (step(s, a) for a in range(4)))
                      if s not in (GOAL, PIT) else 0.0 for s in range(N * N)])
    if np.max(np.abs(V_new - V)) < 1e-8:
        break
    V = V_new
print("value iteration converged in", it, "sweeps")
print(V.reshape(N, N).round(2))

# ---- Q-learning (model-free, epsilon-greedy) ----
rng = np.random.default_rng(0)
Q = np.zeros((N * N, 4))
alpha, eps = 0.2, 0.3
for episode in range(8000):
    s, done = 0, False
    while not done:
        a = rng.integers(4) if rng.random() < eps else int(Q[s].argmax())
        s2, r, done = step(s, a)
        target = r + (0.0 if done else GAMMA * Q[s2].max())
        Q[s, a] += alpha * (target - Q[s, a])            # TD update
        s = s2

policy = np.array([ARROWS[a] for a in Q.argmax(1)])
policy[GOAL], policy[PIT] = "G", "X"
print(policy.reshape(N, N))
Open in playground ↗
Python · Gymnasium + Stable-Baselines3 (pip install gymnasium stable-baselines3)
import gymnasium as gym
from stable_baselines3 import PPO

env = gym.make("CartPole-v1")
model = PPO("MlpPolicy", env, learning_rate=3e-4, n_steps=2048, clip_range=0.2, verbose=0)
model.learn(total_timesteps=50_000)

obs, _ = env.reset(seed=0)
total = 0.0
for _ in range(500):
    action, _ = model.predict(obs, deterministic=True)
    obs, reward, terminated, truncated, _ = env.step(action)
    total += reward
    if terminated or truncated:
        break
print("episode return:", total)          # 500 = balanced the pole for the full episode
This code needs Gymnasium, which cannot run inside a web page. To run it, press Copy, then paste it into a new notebook in Google Colab ↗ (free; Runtime → Change runtime type → GPU for deep learning).
Check yourself

Quiz

1. The discount factor γ controls…

2. ε-greedy is a strategy for…

3. DQN is an example of…

4. Value iteration converges because the Bellman optimality operator is…

5. Subtracting a baseline b(s) in the policy gradient…

6. DQN's target network is used to…

Go deeper

📚 Further reading

Trusted, mostly free sources: official documentation, well-known textbooks and courses. When you want to confirm or go deeper on anything here, start with these.

Ready