Issue #01: All about Reinforcement Learning(3)

Part 2 gave the agent a world — states, transitions, and the Bellman equation. The gap we left was Value Iteration, which requires knowing the full model. What if we just let the agent play, and learn Q* from raw experience? That is Q-Learning. And when the state space explodes beyond any table, that is where Deep Q-Networks come in.

1 — Q-Learning: Bellman Without a Map

Q-Learning is a model-free, off-policy TD method. It learns Q*(s,a) directly from experience — without ever needing to know the transition probabilities T(s,a,s') or the reward function R. All it needs is to interact with the environment and observe what happens.

After every step (s, a, r, s'), the agent computes how wrong its current Q-estimate was and nudges it toward the Bellman target:

Q(s,a)  ←  Q(s,a)  +  α · [ r + γ · max_a' Q(s',a')  −  Q(s,a) ]

α = learning rate · γ = discount factor · [ ] = TD error (δ) · max_a' Q(s',a') = best next-state value

Notice the max_a' — Q-Learning always bootstraps toward the greedy action in the next state, regardless of what the behaviour policy actually did. This is what makes it off-policy: the policy used to explore (ε-greedy) is different from the policy being learned (greedy).

THE CHESS ANALOGY

Q-Learning is like a chess player who has never read a book. They play thousands of games, and after every move they ask: "Given what happened next, was that move better or worse than I thought?" The Q-value of each (position, move) pair is updated based on the outcome. No engine, no theory — just accumulated experience nudging the estimates toward truth.

The Q-Learning Algorithm — Step by Step

• Initialise Q(s,a) = 0 for all states and actions

• Observe current state s

• Choose action a using ε-greedy on Q (explore vs exploit — exactly as in Part 1)

• Execute a, observe reward r and next state s'

• Update: Q(s,a) ← Q(s,a) + α·[r + γ·max_a' Q(s',a') − Q(s,a)]

• Set s ← s', repeat until convergence

Figure 1 — Q-Learning convergence across learning rates. Left: episode reward over time. Right: Q-table error vs true Q*. Higher α learns faster initially but can oscillate; lower α is more stable but slower to converge.

Figure 2 — Left: the learned Q-table as a heatmap after 1,000 episodes. Right: the derived optimal policy — maximum Q-value per state and the corresponding best action. The agent correctly learns to always move toward the goal.

2 — The Problem with Tables: Curse of Dimensionality

Tabular Q-Learning works beautifully for small, discrete state spaces. But consider Atari Breakout: the screen is 84×84 pixels with 3 colour channels, giving approximately 10^33,600 possible states. A Q-table with one row per state is not just impractical — it is physically impossible to store or compute.

Even for continuous state spaces like a robot's joint angles, the table breaks down immediately. We need a way to generalise — to infer the Q-value of states the agent has never seen, based on similar states it has visited. Enter function approximation.

THE KEY INSIGHT

Instead of storing Q(s,a) in a table, approximate it with a parameterised function Q_θ(s,a) — where θ are the parameters of a neural network. The network takes the state as input and outputs Q-values for every action simultaneously. Training the network = updating θ to make Q_θ(s,a) closer to the Bellman target.

3 — Deep Q-Networks (DQN)

DQN, introduced by DeepMind in 2013, was the first algorithm to successfully combine Q-Learning with deep neural networks. It learned to play 49 Atari games from raw pixels, beating human-level performance on 29 of them — using the same network architecture and hyperparameters for every game.

The core update is the same Bellman equation as Q-Learning, but now Q is a neural network parameterised by θ:

L(θ) = E [ ( r + γ · max_a' Q_θ⁻(s',a')  −  Q_θ(s,a) )² ]

θ = main network weights · θ⁻ = frozen target network weights · L = mean squared TD error (loss function)

In principle, this is just gradient descent on the Bellman error. In practice, it was completely unstable until two tricks were introduced — tricks so important they are now standard in every deep RL implementation.

Figure 3 — DQN architecture. The main network maps state s to Q(s,·) for all actions. Two stabilising components are added below: the Replay Buffer stores past transitions for random batch sampling, and the Target Network provides stable Bellman targets that are synced with the main network every N steps.

Trick 1 — Experience Replay

Naively training on each transition as it arrives causes two fatal problems: (1) consecutive transitions are highly correlated — the network overfits to recent experience; (2) learning from a stream of non-stationary data causes the network to "forget" earlier states as it specialises on recent ones.

The fix: store every transition (s, a, r, s', done) in a circular replay buffer of size N (typically 100k–1M). At each training step, sample a random mini-batch of 32–64 transitions. This breaks the correlation, smooths the data distribution, and allows each transition to be reused many times.

Trick 2 — Target Network

The Bellman update requires a target: r + γ·max_a' Q(s',a'). If we use the same network for both Q(s,a) and Q(s',a'), the target shifts every time the weights update — like chasing a moving goalpost. Training becomes a feedback loop that diverges.

The fix: maintain a second frozen copy of the network — the target network θ⁻ — which only syncs with the main network every N steps (typically every 1,000–10,000 steps). The target is now stable for long stretches, giving the main network a fixed objective to optimise toward.

Figure 4 — Training stability with and without the two DQN tricks. Without both replay buffer and target network, the TD loss diverges or oscillates badly. Together, they produce a stable, monotonically decreasing loss — the signature of a healthy DQN run.

4 — Minimal DQN in TensorFlow (Keras)

Here is the core DQN loop from Chapter 18, stripped to its essentials. This is the actual structure used to train on OpenAI Gymnasium environments:

import tensorflow as tf, numpy as np, collections, random

# ── Replay buffer ──────────────────────────────────────────

buffer = collections.deque(maxlen=100_000)

# ── Main + Target networks (same architecture) ─────────────

def build_model(n_states, n_actions):

    return tf.keras.Sequential([

        tf.keras.layers.Dense(64, activation="relu", input_shape=(n_states,)),

        tf.keras.layers.Dense(64, activation="relu"),

        tf.keras.layers.Dense(n_actions)   # linear output = Q-values

    ])

model        = build_model(n_states, n_actions)

target_model = build_model(n_states, n_actions)

target_model.set_weights(model.get_weights())  # start in sync

optimizer = tf.keras.optimizers.Adam(lr=1e-3)

# ── ε-greedy action selection ──────────────────────────────

def select_action(state, epsilon):

    if np.random.rand() < epsilon:

        return env.action_space.sample()          # explore

    return np.argmax(model(state[np.newaxis])[0]) # exploit

# ── Single training step ───────────────────────────────────

def train_step(batch_size=64, gamma=0.99):

    batch = random.sample(buffer, batch_size)

    s, a, r, s2, done = map(np.array, zip(*batch))

    # Bellman target using FROZEN target network

    next_Q = target_model(s2)                    # θ⁻, not θ

    target = r + gamma tf.reduce_max(next_Q, axis=1) (1 - done)

    with tf.GradientTape() as tape:

        Q_vals = model(s)                        # main network

        Q_sa   = tf.reduce_sum(Q_vals * tf.one_hot(a, n_actions), axis=1)

        loss   = tf.reduce_mean((target - Q_sa) ** 2)  # MSE TD error

    grads = tape.gradient(loss, model.trainable_variables)

    optimizer.apply_gradients(zip(grads, model.trainable_variables))

# ── Main training loop ─────────────────────────────────────

for episode in range(500):

    state, _ = env.reset()

    epsilon   = max(0.01, 1.0 - episode / 400)  # decay exploration

    while True:

        action          = select_action(state, epsilon)

        next_s, r, done, , = env.step(action)

        buffer.append((state, action, r, next_s, done))

        state           = next_s

        if len(buffer) >= 1000: train_step()

        if episode % 10 == 0:   # sync target network

            target_model.set_weights(model.get_weights())

        if done: break

Key Takeaways — Part 3

• Q-Learning is model-free TD: it learns Q*(s,a) from raw transitions without knowing T or R, using the Bellman optimality update after every step

• It is off-policy — the exploration policy (ε-greedy) is separate from the target policy (greedy). This is what allows stable, consistent convergence

• Tabular Q-Learning collapses for large or continuous state spaces — a neural network replaces the table to generalise across unseen states

• DQN = Q-Learning + neural network + Experience Replay + Target Network. The last two are not optional extras — without them, training diverges

• Experience Replay breaks temporal correlations in training data and allows transitions to be reused many times

• The Target Network provides a stable Bellman target by freezing weights for N steps — eliminating the moving-goalpost problem

Next Week — Part 4

Policy Gradient methods and REINFORCE: skipping value estimation entirely and optimising the policy directly. Then Actor-Critic and why it combines the best of both worlds.

Based on Hands-On Machine Learning with Scikit-Learn, Keras, and TensorFlow, 3rd Ed., Chapter 18  ·  Aurélien Géron  ·  O'Reilly Media