Q-Learning / DQN

Q-learning is the canonical value-based reinforcement learning algorithm: it learns the action-value function Q(s,a) — the expected discounted return of taking action a in state s and acting optimally afterwards — and acts greedily on it. A Deep Q-Network (DQN) replaces the lookup table with a neural network, which is what let DeepMind (Mnih et al., 2015) learn to play many Atari games from raw pixels with one architecture.

1. Tabular Q-Learning

Q-learning is a temporal-difference (TD) method: it updates an estimate toward another estimate (bootstrapping) rather than waiting for the episode's full return. The update after each transition (s, a, r, s') is:

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

It is off-policy: the target uses max, i.e. the greedy policy, regardless of which (exploratory) action the agent actually takes next. Its on-policy sibling SARSA uses the action actually taken, Q(s',a'), which makes it more conservative near hazards because it accounts for its own exploration. Tabular Q-learning is practical when states and actions are small and discrete (grid worlds, inventory problems with a few hundred states).

2. Python: Q-Learning on FrozenLake

import numpy as np
import gymnasium as gym

env = gym.make("FrozenLake-v1", is_slippery=True)
nS, nA = env.observation_space.n, env.action_space.n
Q = np.zeros((nS, nA))
alpha, gamma = 0.1, 0.99
eps, eps_min, eps_decay = 1.0, 0.05, 0.9995
rng = np.random.default_rng(0)

for ep in range(20_000):
    s, _ = env.reset()
    done = False
    while not done:
        a = env.action_space.sample() if rng.random() < eps else int(np.argmax(Q[s]))
        s2, r, terminated, truncated, _ = env.step(a)
        target = r + gamma * np.max(Q[s2]) * (not terminated)   # no bootstrap past terminal
        Q[s, a] += alpha * (target - Q[s, a])
        s, done = s2, terminated or truncated
    eps = max(eps_min, eps * eps_decay)

# Evaluate the greedy policy
wins = 0
for _ in range(1000):
    s, _ = env.reset(); done = False
    while not done:
        s, r, term, trunc, _ = env.step(int(np.argmax(Q[s])))
        done = term or trunc
    wins += r
print("greedy success rate:", wins / 1000)
print(np.argmax(Q, axis=1).reshape(4, 4))   # learned policy map

3. From Table to Network: DQN

For large or continuous state spaces (images, sensor vectors) a table is impossible; DQN approximates Qθ(s,·) with a network that outputs one value per discrete action. Naively regressing a network onto its own bootstrapped targets diverges, so DQN adds two stabilizers:

• Experience replay. Transitions go into a large ring buffer; training samples random mini-batches. This breaks the strong correlation between consecutive frames and reuses each transition many times.
• Target network. The TD target y = r + γ maxa' Qθ−(s',a') uses a frozen copy updated every C steps (or by Polyak averaging θ− ← τθ + (1−τ)θ−). Without it, every gradient step moves the target it is chasing.

The loss is usually Huber (smooth L1) rather than MSE, which clips the gradient for large TD errors. The combination of function approximation, bootstrapping and off-policy learning is called the "deadly triad"; replay and target networks are the practical mitigations, not a guarantee.

4. Python: A Compact DQN in PyTorch

import random, collections
import numpy as np, torch, torch.nn as nn, gymnasium as gym

env = gym.make("CartPole-v1")
nS, nA = env.observation_space.shape[0], env.action_space.n
def mlp(): return nn.Sequential(nn.Linear(nS, 128), nn.ReLU(), nn.Linear(128, 128), nn.ReLU(), nn.Linear(128, nA))
q, q_tgt = mlp(), mlp(); q_tgt.load_state_dict(q.state_dict())
opt = torch.optim.Adam(q.parameters(), lr=5e-4)
buf = collections.deque(maxlen=50_000)
gamma, batch, eps = 0.99, 64, 1.0

s, _ = env.reset(seed=0); ep_ret, returns = 0.0, []
for step in range(60_000):
    if random.random() < eps:
        a = env.action_space.sample()
    else:
        with torch.no_grad(): a = int(q(torch.tensor(s, dtype=torch.float32)).argmax())
    s2, r, term, trunc, _ = env.step(a)
    buf.append((s, a, r, s2, float(term))); s = s2; ep_ret += r
    if term or trunc:
        returns.append(ep_ret); ep_ret = 0.0; s, _ = env.reset()
    eps = max(0.05, eps - 1 / 20_000)

    if len(buf) >= 1_000:
        S, A, R, S2, D = map(np.array, zip(*random.sample(buf, batch)))
        S, S2 = torch.tensor(S, dtype=torch.float32), torch.tensor(S2, dtype=torch.float32)
        A = torch.tensor(A); R = torch.tensor(R, dtype=torch.float32); D = torch.tensor(D, dtype=torch.float32)
        with torch.no_grad():                                   # Double DQN target
            a_star = q(S2).argmax(1, keepdim=True)
            y = R + gamma * (1 - D) * q_tgt(S2).gather(1, a_star).squeeze(1)
        pred = q(S).gather(1, A.unsqueeze(1)).squeeze(1)
        loss = nn.functional.smooth_l1_loss(pred, y)
        opt.zero_grad(); loss.backward(); nn.utils.clip_grad_norm_(q.parameters(), 10); opt.step()
    if step % 1_000 == 0:
        q_tgt.load_state_dict(q.state_dict())
        if returns: print(step, "avg return (last 20):", np.mean(returns[-20:]))

Note that (1 - D) uses terminated only; a time-limit truncation still bootstraps.

5. Improvements and Variants

Standard DQN overestimates Q-values because max of noisy estimates is biased upward; Double DQN selects the action with the online net and evaluates it with the target net (used in the code above). Dueling networks split a state value V(s) and per-action advantages A(s,a), helping when many actions have similar value. Prioritized replay samples transitions with large TD error more often, correcting the bias with importance-sampling weights. Distributional RL (C51, QR-DQN) learns the full return distribution rather than its mean.

6. When to Use and Pitfalls

• Discrete actions only. The argmax over actions needs a finite set. For continuous control use DDPG/TD3/SAC or policy gradients.
• Reward scale. Large or unbounded rewards destabilize training; clip or normalize them.
• Exploration schedule matters more than most hyperparameters; too-fast ε decay locks in a poor policy.
• Terminal vs truncated bootstrapping errors silently bias Q.
• Stale replay. A huge buffer of very old experience slows adaptation; a tiny one re-introduces correlation.
• Q-values are not calibrated returns early in training — judge progress by evaluation episodes, not Q magnitude.

7. A Worked Q-Update

Take a tiny corridor: states A → B → Goal. Moving right from B reaches the goal with reward +1 and ends the episode; every other step gives 0. Use learning rate α = 0.5, discount γ = 0.9, and start all Q-values at zero.

• Episode 1, step A→B (right). Target = 0 + 0.9 · max Q(B,·) = 0. Q(A,right) stays 0.
• Episode 1, step B→Goal (right). Terminal, so target = 1 with no bootstrap. Q(B,right) = 0 + 0.5(1 − 0) = 0.5.
• Episode 2, step A→B. Target = 0 + 0.9 · 0.5 = 0.45. Q(A,right) = 0 + 0.5(0.45 − 0) = 0.225.
• Episode 2, step B→Goal. Q(B,right) = 0.5 + 0.5(1 − 0.5) = 0.75.

With repetition, Q(B,right) approaches 1 and Q(A,right) approaches γ · 1 = 0.9: the value of the reward propagates backwards one step per visit. That backward propagation is why sparse-reward problems with long horizons learn slowly, and why techniques such as n-step returns (bootstrapping after several real rewards instead of one) speed up credit assignment.

The discount also sets an effective horizon of roughly 1 / (1 − γ) steps: γ = 0.9 looks about 10 steps ahead, 0.99 about 100. Choosing γ too low makes the agent short-sighted; too high makes targets noisy and learning slower.

8. Inside the Double DQN Target

The overestimation problem comes from using the same noisy estimates to both choose and value the best action: the maximum of several noisy numbers is biased upward even if each estimate is unbiased. Double DQN (van Hasselt, Guez and Silver, 2016) decouples the two jobs. The online network picks a* = argmax_a' Q_θ(s', a'), and the target network supplies the value Q_θ−(s', a*). It is a one-line change to the target and rarely hurts, which is why it is a default in most implementations.

9. Hyperparameters That Matter

These ranges are common defaults in open-source implementations (for example Stable-Baselines3 and CleanRL), not guarantees; RL results vary strongly with seeds, so evaluate any change across at least several random seeds and report the spread rather than the best run.

10. Q-Learning in the RL Landscape

Real uses of value-based methods include game-playing agents, recommendation and ad-slot selection framed as sequential decisions (see Recommender Systems), resource scheduling, and network or traffic-signal control in simulation. Many production "RL" problems are actually one-step contextual bandits, where a simpler bandit algorithm is easier to deploy and evaluate offline. For the broader framework see Reinforcement Learning; for RL applied to language models see RLHF.

11. Further Reading

• Watkins (1989), Learning from Delayed Rewards (PhD thesis); Watkins and Dayan (1992), Q-learning, Machine Learning 8.
• Mnih et al. (2015), Human-level control through deep reinforcement learning, Nature 518.
• van Hasselt, Guez and Silver (2016), Deep Reinforcement Learning with Double Q-learning.
• Wang et al. (2016), Dueling Network Architectures for Deep Reinforcement Learning.
• Hessel et al. (2018), Rainbow: Combining Improvements in Deep Reinforcement Learning.
• Sutton and Barto (2018), Reinforcement Learning: An Introduction, 2nd ed., MIT Press.

Related Topics

• Reinforcement Learning
• Machine Learning (ML)
• Policy Gradient (PPO)
• RLHF
• Convolutional Neural Networks (CNN)
• PyTorch