Reinforcement Learning

Reinforcement learning (RL) is learning by trial and error to maximise a reward signal over time. It produced the first systems to learn Atari games from pixels and to beat a top professional at Go, and it now trains robots, tunes data-centre cooling, and plays a central role in post-training large language models, from reinforcement learning from human feedback (RLHF) to the reasoning models trained against verifiable rewards. Unlike supervised learning, nobody tells the agent the right action. It has to discover which actions lead, often much later, to good outcomes.

Intuition: training a dog, playing a long game

Think of teaching a dog a trick with treats. The dog tries things; some actions earn a treat; over time it repeats what worked. Now make it harder: the treat only comes at the end of a long sequence, like winning a chess game after 60 moves. Which of those moves deserves the credit? That is the credit assignment problem, and it is the core of RL. The second core tension is exploration versus exploitation: should the dog repeat the trick it knows earns one treat, or try something new that might earn three?

The formal setup: agents, environments and MDPs

At each time step $t$ the agent observes a state $S_t$, chooses an action $A_t$, and the environment returns a reward $R_{t+1}$ and a next state $S_{t+1}$. This is formalised as a Markov decision process (MDP), a tuple $(\mathcal{S}, \mathcal{A}, p, r, \gamma)$:

• $\mathcal{S}$: the set of states; $\mathcal{A}$: the set of actions.
• $p(s', r \mid s, a)$: the probability of reaching state $s'$ with reward $r$ after taking action $a$ in state $s$.
• $\gamma \in [0, 1]$: the discount factor.

The Markov property says the next state and reward depend only on the current state and action, not on earlier history. When the agent sees only part of the state (a robot's camera, a poker hand), the problem is a partially observable MDP, and agents use memory (recurrent networks, frame stacks) to compensate.

A policy $\pi(a \mid s)$ gives the probability of taking action $a$ in state $s$. The goal is to find a policy that maximises expected return.

Returns and discounting

The return from time $t$ is the discounted sum of future rewards:

Discounting does three jobs. It keeps infinite sums finite when $\gamma < 1$, it encodes a preference for sooner rewards, and it reduces variance. A useful rule of thumb: the effective horizon is about $1/(1-\gamma)$ steps, so $\gamma = 0.99$ looks roughly 100 steps ahead. Returns obey a simple recursion, which everything else builds on:

Worked example. An episode gives rewards $-1, -1, +10$ and then ends. With $\gamma = 0.9$: $G_0 = -1 + 0.9(-1) + 0.81(10) = -1 - 0.9 + 8.1 = 6.2$. Using the recursion backwards: $G_2 = 10$, $G_1 = -1 + 0.9 \times 10 = 8$, $G_0 = -1 + 0.9 \times 8 = 6.2$.

Value functions and Bellman equations

The state-value function of policy $\pi$ is the expected return starting from $s$ and following $\pi$: $v_\pi(s) = \mathbb{E}_\pi[G_t \mid S_t = s]$. The action-value function is $q_\pi(s, a) = \mathbb{E}_\pi[G_t \mid S_t = s, A_t = a]$, the expected return of taking $a$ first and then following $\pi$.

Substituting the return recursion gives the Bellman expectation equation:

In words: the value of a state is the expected immediate reward plus the discounted value of where you land. The optimal value functions $v_*(s) = \max_\pi v_\pi(s)$ and $q_*(s,a) = \max_\pi q_\pi(s,a)$ satisfy the Bellman optimality equations:

Once you know $q_*$, acting optimally is trivial: choose $\arg\max_a q_*(s, a)$. Most of RL is about estimating these quantities when $p$ is unknown and the state space is huge.

Dynamic programming

If the model $p$ is known and the state space is small, dynamic programming (DP) solves the Bellman equations by iteration. Policy evaluation repeatedly applies the expectation equation as an update until $v$ stops changing. Policy improvement makes the policy greedy with respect to $v$. Alternating the two is policy iteration. Value iteration folds them together by applying the optimality equation as an update, $v_{k+1}(s) \leftarrow \max_a \sum_{s',r} p(s', r \mid s, a)[r + \gamma v_k(s')]$, which converges to $v_*$ for $\gamma < 1$ because the update is a contraction. DP is exact but needs the model and sweeps the whole state space, which Bellman called the curse of dimensionality.

Learning from experience: Monte Carlo and TD

When the model is unknown, the agent learns from sampled experience.

Monte Carlo (MC) methods run complete episodes and move the value estimate toward the observed return:

where $\alpha$ is the step size. MC is unbiased but high-variance, and it must wait until the episode ends.

Temporal-difference (TD) learning updates after a single step by bootstrapping, using its own current estimate of the next state's value in place of the rest of the return:

The bracketed quantity is the TD error $\delta_t$. TD learning works online, handles continuing tasks, and usually learns faster than MC because of its lower variance, at the price of bias from the bootstrapped estimate. $n$-step returns and TD($\lambda$) interpolate between the two.

Q-learning

Q-learning (Watkins, 1989) applies TD learning to action values with a max in the target:

It is off-policy: it learns the value of the greedy policy while behaving with an exploratory one. Under standard conditions (every state–action pair visited infinitely often and suitably decaying step sizes), tabular Q-learning converges to $q_*$. Its on-policy cousin SARSA uses the action actually taken next, $Q(S_{t+1}, A_{t+1})$, instead of the max, which makes it more cautious when exploration is risky.

Worked gridworld update

A robot in a gridworld is at cell (2,1). It moves right to cell (2,2) and receives reward $-1$ (a step cost). Current estimates: $Q((2,1), \text{right}) = 0$, and the best action value at the new cell is $\max_{a'} Q((2,2), a') = -2$. Take $\alpha = 0.5$, $\gamma = 0.9$.

1. TD target: $-1 + 0.9 \times (-2) = -1 - 1.8 = -2.8$.
2. TD error: $-2.8 - 0 = -2.8$.
3. Update: $Q((2,1), \text{right}) \leftarrow 0 + 0.5 \times (-2.8) = -1.4$.

Next, from (3,2) the robot moves right into the goal (3,3), receiving $+10$; the episode ends, so there is no bootstrap term. If $Q((3,2), \text{right}) = 2$: target $= 10$, error $= 8$, new value $= 2 + 0.5 \times 8 = 6$. Repeated over many episodes, the goal reward propagates backwards through the grid one step at a time.

Exploration: epsilon-greedy and beyond

With $\varepsilon$-greedy exploration the agent picks a uniformly random action with probability $\varepsilon$ and the greedy action $\arg\max_a Q(s,a)$ otherwise. It is simple and surprisingly effective; $\varepsilon$ is usually decayed from 1.0 toward a small value such as 0.01 or 0.05. Alternatives include softmax (Boltzmann) exploration, optimism in the face of uncertainty (optimistic initial values, upper confidence bounds), and intrinsic-motivation bonuses for novel states, which matter in sparse-reward problems where random actions almost never reach a reward.

A tabular Q-learning implementation

import numpy as np

ROWS, COLS = 4, 4
START, GOAL, PITS = (0, 0), (3, 3), {(1, 1), (2, 3)}
ACTIONS = [(-1, 0), (1, 0), (0, -1), (0, 1)]          # up, down, left, right

def step(s, a):
    r, c = s[0] + ACTIONS[a][0], s[1] + ACTIONS[a][1]
    s2 = (min(max(r, 0), ROWS - 1), min(max(c, 0), COLS - 1))  # walls block
    if s2 == GOAL:  return s2, 10.0, True
    if s2 in PITS:  return s2, -10.0, True
    return s2, -1.0, False

rng = np.random.default_rng(0)
Q = np.zeros((ROWS, COLS, len(ACTIONS)))
alpha, gamma, eps = 0.5, 0.9, 0.1

for episode in range(2000):
    s, done = START, False
    while not done:
        a = int(rng.integers(4)) if rng.random() < eps else int(np.argmax(Q[s]))
        s2, r, done = step(s, a)
        target = r if done else r + gamma * np.max(Q[s2])
        Q[s][a] += alpha * (target - Q[s][a])            # TD update
        s = s2

s, path = START, [START]
for _ in range(20):                                      # greedy rollout
    s, _, done = step(s, int(np.argmax(Q[s])))
    path.append(s)
    if done: break
print("path:", path)
print("V(start) = %.3f" % Q[START].max())

The environment is a 4×4 grid with a goal worth $+10$, two pits worth $-10$ and a step cost of $-1$. After 2,000 episodes the greedy policy walks a six-move shortest path around the pits, and $\max_a Q(\text{start}, a) \approx 1.810$. That matches the true optimal return: five step costs and then the goal, $-\sum_{k=0}^{4} 0.9^k + 0.9^5 \times 10 = -4.095 + 5.905 = 1.810$.

Deep RL: DQN

Tables fail when states are images. Deep Q-Networks (Mnih et al., 2013 preprint; Nature, 2015) replace the table with a convolutional network $Q(s, a; \theta)$ that maps stacked Atari frames to one value per action. Naive Q-learning with neural networks is unstable, so DQN added two ideas:

• Experience replay: store transitions $(s, a, r, s')$ in a buffer and train on random minibatches, which breaks correlations between consecutive samples and reuses data.
• Target network: compute targets with a periodically copied set of weights $\theta^-$, minimising $\big(r + \gamma \max_{a'} Q(s', a'; \theta^-) - Q(s, a; \theta)\big)^2$, so the target does not shift with every gradient step.

The Nature paper reported a single architecture and hyperparameter set learning 49 Atari 2600 games from pixels and score, reaching a level comparable to a professional human games tester across the set. Successors fixed known weaknesses: Double DQN reduces the overestimation caused by the max, and dueling networks, prioritised replay and distributional RL were combined in Rainbow.

Policy gradients: REINFORCE

Value-based methods struggle with continuous actions (a robot joint torque) and only learn deterministic greedy policies. Policy-gradient methods parameterise the policy directly, $\pi_\theta(a \mid s)$, and do gradient ascent on expected return $J(\theta)$. The policy gradient theorem gives

REINFORCE (Williams, 1992) estimates this by sampling episodes: increase the log-probability of actions in proportion to the return that followed them. Intuitively, it is supervised learning on your own actions, weighted by how well things went. The estimator is unbiased but very noisy, so we subtract a baseline $b(S_t)$ that does not depend on the action, which keeps it unbiased while cutting variance: use $G_t - b(S_t)$ instead of $G_t$.

Actor-critic

Use a learned value function $V_w(s)$ as the baseline and you get actor-critic: the actor is the policy $\pi_\theta$, and the critic $V_w$ estimates values. The weight on each action becomes the advantage, $A_t \approx R_{t+1} + \gamma V_w(S_{t+1}) - V_w(S_t)$ (the TD error), which says how much better the action was than expected. Generalised advantage estimation (GAE) blends multi-step advantages with a parameter $\lambda$ to trade bias against variance. A2C and A3C run many environment copies in parallel to decorrelate data.

PPO in one section

Policy-gradient updates are fragile: one step that is too large can collapse the policy, and the data needed to recover is then never collected. Proximal Policy Optimization (Schulman et al., 2017) limits how far each update moves the policy. With the probability ratio $\rho_t(\theta) = \pi_\theta(A_t \mid S_t) / \pi_{\theta_{\text{old}}}(A_t \mid S_t)$ and advantage estimate $\hat{A}_t$, PPO maximises the clipped surrogate

with $\epsilon$ typically 0.1 to 0.2. When an action was good ($\hat{A}_t > 0$), the objective stops rewarding increases in its probability beyond $1+\epsilon$ times the old one; when bad, it stops rewarding decreases below $1-\epsilon$. This lets PPO run several epochs of minibatch updates on each batch of rollouts safely. In practice the loss also includes a value-function term and an entropy bonus. PPO's robustness made it the default on-policy algorithm for robotics, games and, for several years, RLHF. Off-policy actor-critics such as SAC and TD3 are common alternatives for continuous control when sample efficiency matters.

RL for language models: RLHF and verifiable rewards

A language model can be framed as a policy: the state is the prompt plus the text so far, an action is the next token, and an episode ends at the end of the response. RLHF, popularised by InstructGPT (Ouyang et al., 2022), has three stages: supervised fine-tuning on demonstrations; training a reward model on human preference comparisons between responses; and optimising the policy with PPO against the reward model, plus a KL-divergence penalty that keeps it close to the supervised model so it does not exploit reward-model errors (reward hacking). Preference-optimisation methods such as DPO skip the explicit RL loop.

For reasoning, a different reward is available: in maths and code you can check the answer. Reinforcement learning with verifiable rewards (RLVR), a term used in AI2's Tülu 3 report (2024), rewards the model when a final answer matches the reference or the code passes tests. DeepSeek-R1 (2025) showed that large-scale RL with such rule-based rewards, using the GRPO algorithm (which replaces the critic with advantages computed relative to a group of sampled answers to the same prompt), can produce long chain-of-thought reasoning. The lesson on post-training and alignment covers these pipelines in depth.

Famous results

Common pitfalls

• Reward hacking. The agent maximises the reward you wrote, not the one you meant: boat-racing agents circling to collect points, language models padding answers that a reward model likes. Inspect behaviour, not just reward curves.
• Sparse rewards. With reward only at success, random exploration may never find it; use reward shaping carefully (potential-based shaping preserves optimal policies), curricula or demonstrations.
• Seed sensitivity. Deep RL results vary hugely across random seeds; report several seeds with confidence intervals.
• Wrong discount or horizon. A $\gamma$ that is too low makes the agent myopic; one that is too high slows learning.
• Non-stationary targets. Forgetting the target network, or not stopping gradients through targets, destabilises DQN.
• Evaluating with exploration on. Measure the greedy (or deterministic) policy separately from the exploring behaviour policy.
• Simulator exploits. Agents find physics bugs; a policy that exploits them will not transfer to the real world.

In practice

Ask first whether you need RL at all. If you can collect labelled decisions, supervised or imitation learning is cheaper and more stable; if the problem is one-step with feedback (ad selection, recommendations), contextual bandits may suffice. When RL fits (sequential decisions, a simulator or a safe way to interact, a clear reward), start with well-tested implementations from libraries such as Stable-Baselines3, CleanRL or TorchRL and environments with the Gymnasium API. Use PPO as a robust on-policy default, SAC for continuous control with costly samples, and DQN variants for discrete actions. Normalise observations and advantages, log episode returns across several seeds, and watch videos of the agent. For language models, RL now sits inside post-training pipelines: preference-based reward models for helpfulness and style, verifiable rewards for maths and code, always with a KL penalty or reference model and an eye on reward hacking.