Deep Q-Networks (DQN), Double DQN & Dueling Architectures

In complex environments such as Atari games, autonomous driving, or high-dimensional physics simulations, the state space $\mathcal{S}$ is vast or continuous. Tabular representations require $|\mathcal{S}| \times |\mathcal{A}|$ discrete memory entries, rendering them intractable due to the curse of dimensionality.

Deep Q-Networks (DQN) replace discrete lookup tables with parameterized neural networks $Q(s, a; \theta) \approx Q^*(s, a)$ . However, naively combining non-linear deep neural networks with temporal difference learning causes catastrophic training divergence.

Double DQN TargetDeep RL

Y_t = R + gamma * Q(S', argmax_a' Q(S', a'; theta); theta^-)

Decoupling action selection (online network) from action evaluation (target network) completely eliminates maximization overestimation bias.

1. The Deadly Triad in Reinforcement Learning#

As formalized by Richard Sutton and Andrew Barto, reinforcement learning algorithms become fundamentally susceptible to instability and divergence whenever three elements coincide:

Architecture Diagram

Rendering diagram...

Function Approximation: The state space is compressed into a parameter vector $\theta$ , meaning updating the value of state $s_1$ inherently perturbs the values of nearby states $s_2$ .
Bootstrapping: Value targets are generated using the network's own current predictions ( $R + \gamma \max Q(s', a')$ ) rather than ground-truth Monte Carlo empirical rollouts.
Off-Policy Learning: The distribution of transitions used to compute gradients differs from the state distribution generated by the current greedy target policy.

When all three are present, errors in value estimates compound recursively across Bellman updates, causing network weights to explode or oscillate chaotically.

2. The Nature DQN Innovations (Mnih et al. 2015)#

To stabilize deep Q-learning, the DeepMind team introduced two foundational mechanisms that tame the deadly triad:

1. Experience Replay Buffer $\mathcal{D}$ #

In standard sequential interaction, consecutive transition tuples $(s_t, a_t, r_t, s_{t+1})$ are strongly correlated across time, violating the standard Independent and Identically Distributed (IID) assumption required for stable stochastic gradient descent.

An Experience Replay Buffer stores historical transitions in a fixed-capacity FIFO circular queue $\mathcal{D} = \{e_1, e_2, \dots, e_N\}$ . During training, mini-batches of size $B$ are sampled uniformly at random:

(s, a, r, s', d) \sim \text{Uniform}(\mathcal{D})

Decorrelation: Sampling transitions at random breaks temporal correlations between consecutive steps.
Sample Efficiency: Each observed transition is reused across multiple parameter updates rather than discarded immediately.

2. Separate Target Network $\theta^-$ #

In naive Q-learning with neural networks, updating $\theta$ simultaneously modifies both the prediction $Q(s, a; \theta)$ and the target $r + \gamma \max_{a'} Q(s', a'; \theta)$ . This is analogous to a dog chasing its own tail: the target moves with every gradient step.

DQN maintains two distinct parameter sets:

Online Network $\theta$ : Updated at every training iteration via gradient descent.
Target Network $\theta^-$ : Kept frozen for $C$ steps, periodically cloned from $\theta$ :

\theta^- \leftarrow \theta \quad \text{every } C \text{ steps}

Alternatively, $\theta^-$ is updated smoothly using Polyak averaging: $\theta^- \leftarrow \tau \theta + (1 - \tau)\theta^-$ .

The DQN Loss Function and Gradient Derivation#

The Mean Squared Bellman Error (MSBE) loss is formulated as:

L(\theta) = \mathbb{E}_{(s, a, r, s', d) \sim \mathcal{D}} \left[ \left( r + \gamma (1 - d) \max_{a' \in \mathcal{A}} Q(s', a'; \theta^-) - Q(s, a; \theta) \right)^2 \right]

where $d \in \{0, 1\}$ indicates whether state $s'$ is terminal.

Differentiating with respect to the online parameters $\theta$ :

\nabla_\theta L(\theta) = -2 \, \mathbb{E}_{(s, a, r, s', d)} \left[ \left( r + \gamma (1 - d) \max_{a'} Q(s', a'; \theta^-) - Q(s, a; \theta) \right) \nabla_\theta Q(s, a; \theta) \right]

Note that the target parameters $\theta^-$ are treated as constant with respect to $\theta$ during the gradient step.

3. Double DQN (DDQN)#

While DQN with a target network stabilizes training, it retains the maximization operator $\max_{a'} Q(s', a'; \theta^-)$ , which induces systematic overestimation of action values (proven via Jensen's inequality).

In 2016, Hado van Hasselt, Arthur Guez, and David Silver introduced Double DQN.

Mathematical Derivation of Decoupled Evaluation#

In standard DQN, the target network performs both:

Selecting the best action: $\arg\max_{a'} Q(s', a'; \theta^-)$
Evaluating the value of that action: $Q(s', a^*; \theta^-)$

Double DQN decouples action selection from action evaluation:

The online network $\theta$ selects the best candidate action $a^*$ :

a^*(s') = \arg\max_{a' \in \mathcal{A}} Q(s', a'; \theta)

The target network $\theta^-$ evaluates the value of that chosen action:

Y_t^{\text{DoubleDQN}} = r + \gamma (1 - d) Q\left(s', a^*(s'); \theta^-\right) = r + \gamma (1 - d) Q\left(s', \arg\max_{a'} Q(s', a'; \theta); \theta^-\right)

Architecture Diagram

Rendering diagram...

Because an overestimate in the online network does not necessarily correspond to an overestimate in the target network, this decoupling effectively eliminates maximization bias across training.

4. Dueling DQN Architecture#

In many environments, the absolute value of being in a state $V(s)$ is critical, whereas the relative advantage of specific actions $A(s, a)$ may be negligible (for instance, when a car is on an empty highway, steering left or right makes little immediate difference).

Ziyu Wang et al. (2016) proposed Dueling DQN, which splits the neural network into two separate computation streams after shared feature layers:

Architecture Diagram

Rendering diagram...

The Identifiability Issue and Centered Advantage#

If we naively define $Q(s, a) = V(s) + A(s, a)$ , the decomposition is mathematically unidentifiable: given $Q$ , we cannot uniquely recover $V$ and $A$ (adding a constant $c$ to $V$ and subtracting $c$ from $A$ produces identical outputs).

To enforce uniqueness and numerical stability, Dueling DQN forces the advantage stream to have zero mean across all actions:

Q(s, a; \theta, \alpha, \beta) = V(s; \theta, \beta) + \left( A(s, a; \theta, \alpha) - \frac{1}{|\mathcal{A}|} \sum_{a' \in \mathcal{A}} A(s, a'; \theta, \alpha) \right)

This subtraction forces the advantage stream to track only relative differences, while the scalar stream learns the comprehensive state value.

5. From-Scratch Implementation: Deep Q-Learning & Replay Buffer#

We implement a complete Deep Q-Learning agent from first principles without external machine learning frameworks in both Python and Rust. The network consists of a multi-layer perceptron (forward pass, backpropagation, and target network parameter synchronization) with a FIFO replay buffer.

Python Implementation (Pure Standard Library)#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
"""
Deep Q-Learning with Replay Buffer and Target Network from scratch
using only the Python standard library (math, random, collections).
"""
import math
import random
from collections import deque
from typing import List, Tuple

class SimpleMLP:
    """A 2-layer perceptron: Input -> Hidden (ReLU) -> Output (Linear)"""
    def __init__(self, in_dim: int, hidden_dim: int, out_dim: int, lr: float = 0.01):
        self.in_dim = in_dim
        self.hidden_dim = hidden_dim
        self.out_dim = out_dim
        self.lr = lr

        # He initialization
        scale_1 = math.sqrt(2.0 / in_dim)
        self.w1 = [[random.gauss(0, scale_1) for _ in range(hidden_dim)] for _ in range(in_dim)]
        self.b1 = [0.0] * hidden_dim

        scale_2 = math.sqrt(2.0 / hidden_dim)
        self.w2 = [[random.gauss(0, scale_2) for _ in range(out_dim)] for _ in range(hidden_dim)]
        self.b2 = [0.0] * out_dim

    def forward(self, x: List[float]) -> Tuple[List[float], List[float]]:
        # Hidden layer with ReLU
        hidden = []
        for j in range(self.hidden_dim):
            s = self.b1[j]
            for i in range(self.in_dim):
                s += x[i] * self.w1[i][j]
            hidden.append(max(0.0, s))

        # Output layer (linear)
        out = []
        for k in range(self.out_dim):
            s = self.b2[k]
            for j in range(self.hidden_dim):
                s += hidden[j] * self.w2[j][k]
            out.append(s)

        return hidden, out

    def backward(self, x: List[float], hidden: List[float], out: List[float], target_q: List[float], action: int):
        # Compute gradient for selected action: grad = (out[action] - target_q[action])
        error = out[action] - target_q[action]

        # Gradients for W2 and b2
        grad_w2 = [[0.0] * self.out_dim for _ in range(self.hidden_dim)]
        grad_b2 = [0.0] * self.out_dim
        grad_hidden = [0.0] * self.hidden_dim

        grad_b2[action] = error
        for j in range(self.hidden_dim):
            grad_w2[j][action] = error * hidden[j]
            grad_hidden[j] += error * self.w2[j][action]

        # Backprop through ReLU
        grad_h_pre = [grad_hidden[j] if hidden[j] > 0 else 0.0 for j in range(self.hidden_dim)]

        # Gradients for W1 and b1
        grad_w1 = [[0.0] * self.hidden_dim for _ in range(self.in_dim)]
        grad_b1 = grad_h_pre[:]
        for i in range(self.in_dim):
            for j in range(self.hidden_dim):
                grad_w1[i][j] = grad_h_pre[j] * x[i]

        # SGD Update
        for j in range(self.hidden_dim):
            self.w2[j][action] -= self.lr * grad_w2[j][action]
            self.b1[j] -= self.lr * grad_b1[j]
            for i in range(self.in_dim):
                self.w1[i][j] -= self.lr * grad_w1[i][j]
        self.b2[action] -= self.lr * grad_b2[action]

    def copy_from(self, source: 'SimpleMLP'):
        self.w1 = [row[:] for row in source.w1]
        self.b1 = source.b1[:]
        self.w2 = [row[:] for row in source.w2]
        self.b2 = source.b2[:]

class DQNAgent:
    def __init__(self, state_dim: int, action_dim: int, gamma: float = 0.95):
        self.state_dim = state_dim
        self.action_dim = action_dim
        self.gamma = gamma
        self.online_net = SimpleMLP(state_dim, 16, action_dim, lr=0.01)
        self.target_net = SimpleMLP(state_dim, 16, action_dim, lr=0.01)
        self.target_net.copy_from(self.online_net)
        self.buffer = deque(maxlen=500)
        self.epsilon = 0.5
        self.sync_steps = 20
        self.step_count = 0

    def select_action(self, state: List[float]) -> int:
        if random.random() < self.epsilon:
            return random.randint(0, self.action_dim - 1)
        _, q_vals = self.online_net.forward(state)
        return max(range(self.action_dim), key=lambda a: q_vals[a])

    def store_transition(self, s, a, r, s_next, done):
        self.buffer.append((s, a, r, s_next, done))

    def train_step(self, batch_size: int = 16):
        if len(self.buffer) < batch_size:
            return
        batch = random.sample(self.buffer, batch_size)
        for s, a, r, s_next, done in batch:
            hidden, q_vals = self.online_net.forward(s)
            target = q_vals[:]
            if done:
                target[a] = r
            else:
                # Double DQN: online net selects action, target net evaluates
                _, next_online_q = self.online_net.forward(s_next)
                best_next_a = max(range(self.action_dim), key=lambda act: next_online_q[act])
                _, next_target_q = self.target_net.forward(s_next)
                target[a] = r + self.gamma * next_target_q[best_next_a]

            self.online_net.backward(s, hidden, q_vals, target, a)

        self.step_count += 1
        if self.step_count % self.sync_steps == 0:
            self.target_net.copy_from(self.online_net)

if __name__ == "__main__":
    agent = DQNAgent(state_dim=2, action_dim=2)
    # Simulate synthetic training transitions
    for step in range(100):
        s = [random.uniform(-1, 1), random.uniform(-1, 1)]
        a = agent.select_action(s)
        r = 1.0 if s[0] > 0 else -1.0
        s_next = [s[0] + 0.1, s[1] - 0.1]
        agent.store_transition(s, a, r, s_next, False)
        agent.train_step(batch_size=8)
    print("DQN Training completed successfully.")

Rust Implementation (Pure Standard Library)#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
// Deep Q-Network with decoupled Double DQN evaluation and experience replay
// Implemented strictly from scratch in pure Rust std.

use std::collections::VecDeque;

struct SimpleRng {
    seed: u64,
}

impl SimpleRng {
    fn new(seed: u64) -> Self {
        Self { seed }
    }

    fn next_f64(&mut self) -> f64 {
        self.seed = self.seed.wrapping_mul(6364136223846793005).wrapping_add(1);
        ((self.seed >> 11) as f64) / ((1u64 << 53) as f64)
    }

    fn next_gaussian(&mut self) -> f64 {
        let u1 = self.next_f64().max(1e-10);
        let u2 = self.next_f64();
        (-2.0 * u1.ln()).sqrt() * (2.0 * std::f64::consts::PI * u2).cos()
    }
}

#[derive(Clone)]
struct LinearLayer {
    weights: Vec<Vec<f64>>, // in_dim x out_dim
    biases: Vec<f64>,       // out_dim
}

impl LinearLayer {
    fn new(in_dim: usize, out_dim: usize, rng: &mut SimpleRng) -> Self {
        let stddev = (2.0 / (in_dim as f64)).sqrt();
        let mut weights = vec![vec![0.0; out_dim]; in_dim];
        for i in 0..in_dim {
            for j in 0..out_dim {
                weights[i][j] = rng.next_gaussian() * stddev;
            }
        }
        let biases = vec![0.0; out_dim];
        Self { weights, biases }
    }

    fn forward(&self, x: &[f64]) -> Vec<f64> {
        let out_dim = self.biases.len();
        let mut out = self.biases.clone();
        for i in 0..x.len() {
            for j in 0..out_dim {
                out[j] += x[i] * self.weights[i][j];
            }
        }
        out
    }
}

struct MLP {
    l1: LinearLayer,
    l2: LinearLayer,
    lr: f64,
}

impl MLP {
    fn new(in_dim: usize, hidden_dim: usize, out_dim: usize, lr: f64, rng: &mut SimpleRng) -> Self {
        Self {
            l1: LinearLayer::new(in_dim, hidden_dim, rng),
            l2: LinearLayer::new(hidden_dim, out_dim, rng),
            lr,
        }
    }

    fn forward(&self, x: &[f64]) -> (Vec<f64>, Vec<f64>) {
        let z1 = self.l1.forward(x);
        let h1: Vec<f64> = z1.into_iter().map(|v| if v > 0.0 { v } else { 0.0 }).collect();
        let q = self.l2.forward(&h1);
        (h1, q)
    }

    fn update(&mut self, x: &[f64], h1: &[f64], q: &[f64], target_val: f64, action: usize) {
        let error = q[action] - target_val;

        // Gradient for L2
        let mut grad_h = vec![0.0; h1.len()];
        for j in 0..h1.len() {
            grad_h[j] = error * self.l2.weights[j][action];
            self.l2.weights[j][action] -= self.lr * error * h1[j];
        }
        self.l2.biases[action] -= self.lr * error;

        // Gradient for L1
        for j in 0..h1.len() {
            let d_act = if h1[j] > 0.0 { 1.0 } else { 0.0 };
            let delta = grad_h[j] * d_act;
            self.l1.biases[j] -= self.lr * delta;
            for i in 0..x.len() {
                self.l1.weights[i][j] -= self.lr * delta * x[i];
            }
        }
    }

    fn copy_weights(&mut self, other: &MLP) {
        self.l1 = other.l1.clone();
        self.l2 = other.l2.clone();
    }
}

#[derive(Clone)]
struct Transition {
    s: Vec<f64>,
    a: usize,
    r: f64,
    s_next: Vec<f64>,
    done: bool,
}

fn main() {
    let mut rng = SimpleRng::new(1337);
    let mut online_net = MLP::new(2, 8, 2, 0.02, &mut rng);
    let mut target_net = MLP::new(2, 8, 2, 0.02, &mut rng);
    target_net.copy_weights(&online_net);

    let mut buffer: VecDeque<Transition> = VecDeque::with_capacity(200);

    // Populate buffer with synthetic transitions
    for _ in 0..50 {
        let s = vec![rng.next_f64(), rng.next_f64()];
        let a = if rng.next_f64() < 0.5 { 0 } else { 1 };
        let r = if s[0] > 0.5 { 1.0 } else { -0.5 };
        let s_next = vec![s[0] * 0.9, s[1] * 0.9];
        if buffer.len() >= 200 { buffer.pop_front(); }
        buffer.push_back(Transition { s, a, r, s_next, done: false });
    }

    // Double DQN update step
    let gamma = 0.95;
    for transition in buffer.iter().take(20) {
        let (h1, q_vals) = online_net.forward(&transition.s);

        // Action selection from online net
        let (_, next_online_q) = online_net.forward(&transition.s_next);
        let best_a = if next_online_q[0] >= next_online_q[1] { 0 } else { 1 };

        // Action evaluation from target net
        let (_, next_target_q) = target_net.forward(&transition.s_next);
        let target_val = transition.r + gamma * next_target_q[best_a];

        online_net.update(&transition.s, &h1, &q_vals, target_val, transition.a);
    }

    target_net.copy_weights(&online_net);
    println!("Double DQN updates executed cleanly with pure Rust std.");
}

6. Architectural Comparison#

Architecture	Action Selection	Action Evaluation	Key Innovation
Standard DQN	$\arg\max_{a'} Q(s', a'; \theta^-)$	Target Network $\theta^-$	Replay buffer + periodic target cloning
Double DQN	$\arg\max_{a'} Q(s', a'; \theta)$ (Online)	Target Network $\theta^-$	Decoupled evaluation eliminates overestimation bias
Dueling DQN	Argmax over combined $Q(s, a)$	Decoupled value stream $V(s)$ and advantage stream $A(s, a)$	Zero-mean centered advantage for identifiability

7. Knowledge Check#

Concept check

Question

question: "What constitutes the 'Deadly Triad' in reinforcement learning?"

options:

"(Recommended) Function approximation, bootstrapping, and off-policy training"
"Stochastic environments, sparse rewards, and high dimensionality"
"Experience replay, target networks, and dueling architecture"
"Continuous state spaces, discrete action spaces, and decaying epsilon"

explanation: "The Deadly Triad, identified by Sutton and Barto, occurs when function approximation, bootstrapping (TD updates), and off-policy learning occur simultaneously, frequently causing value function divergence."

:::

Concept check

Question

question: "Why does Dueling DQN subtract the mean advantage (1/|A| sum A(s, a')) rather than directly adding V(s) + A(s, a)?"

options:

"(Recommended) To resolve mathematical unidentifiability, ensuring that V(s) uniquely represents state value and A(s, a) represents relative advantage"
"To prevent gradient clipping during backpropagation"
"To ensure the policy satisfies the Markov property"
"To eliminate the need for an experience replay buffer"

explanation: "Direct addition V(s) + A(s, a) is unidentifiable because shifting V(s) by a constant and subtracting that constant from A(s, a) yields identical Q-values. Subtracting the mean advantage centers the stream at zero, guaranteeing identifiability."

:::

Deep Q-Networks (DQN), Double DQN & Dueling Architectures

1. The Deadly Triad in Reinforcement Learning#

2. The Nature DQN Innovations (Mnih et al. 2015)#

1. Experience Replay Buffer D\mathcal{D}D#

2. Separate Target Network θ−\theta^-θ−#

The DQN Loss Function and Gradient Derivation#

3. Double DQN (DDQN)#

Mathematical Derivation of Decoupled Evaluation#

4. Dueling DQN Architecture#

The Identifiability Issue and Centered Advantage#

5. From-Scratch Implementation: Deep Q-Learning & Replay Buffer#

Python Implementation (Pure Standard Library)#

Rust Implementation (Pure Standard Library)#

6. Architectural Comparison#

7. Knowledge Check#

1. Experience Replay Buffer $\mathcal{D}$ #

2. Separate Target Network $\theta^-$ #