Reinforcement Learning (2): Q-Learning and Deep Q-Networks (DQN)
Chen Kai BOSS
  2024-08-09 14:00:00 2024-08-09 14:00      7.5k Words  46 Mins  

From board games to Atari video games, value function methods have been a cornerstone of reinforcement learning. Q-Learning learns to select optimal actions by iteratively updating state-action values, but faces the curse of dimensionality when dealing with high-dimensional state spaces (like an 84x84 pixel game screen). DeepMind's Deep Q-Network (DQN), proposed in 2013, broke through this barrier by using neural networks as function approximators, combined with two key innovations: experience replay and target networks. This enabled computers to achieve superhuman performance on multiple Atari games for the first time. This breakthrough not only accelerated the development of deep reinforcement learning but also spawned a series of improvements like Double DQN, Dueling DQN, and Prioritized Experience Replay, culminating in the Rainbow algorithm. This chapter starts from the mathematical foundations of Q-Learning, progressively deconstructs DQN's core mechanisms, and analyzes the design motivations and implementation details of various variants.

Q-Learning Foundations: From Dynamic Programming to Temporal Difference

Bellman Optimality Equation and Q-Values

In Chapter 1, we introduced the value functionand action-value function. For the optimal policy, its Q-function satisfies the Bellman optimality equation:The intuition is: the optimal value of taking actionin stateequals the immediate rewardplus the maximum discounted value achievable from the next state. This recursive definition looks like a chicken-and-egg problem, but Banach's fixed-point theorem guarantees it has a unique solution that can be approached through iteration.

Unlikefor policy evaluation,corresponds to the optimal policy — once we know, we can directly obtain optimal behavior through the greedy policy. This is the core idea of Q-Learning: we don't need to explicitly model the policy, just learn the Q function, and the policy is implicit within it.

Q-Learning Algorithm: Incremental Updates

Q-Learning is an off-policy temporal difference (TD) algorithm, proposed by Watkins in 1989. Its update rule is:Hereis the learning rate, and the term in brackets is called the TD error (temporal difference error):TD error measures the gap between "actually obtained return" and "current estimate". If, we underestimated this action's value and need to increase it; otherwise, decrease it. This update is incremental — after eachtransition, we immediately update the Q-value without waiting for episode completion.

Why is it called off-policy? Because the update formula uses (corresponding to the greedy policy), but the actual behavior policy can be anything — like an-greedy policy that explores randomly with probability. This separation of "saying one thing and doing another" allows Q-Learning to both ensure exploration and learn the optimal policy.

Convergence Guarantees: Watkins & Dayan (1992)

Q-Learning's convergence was proven by Watkins and Dayan in 1992, requiring the following conditions:

  1. Tabular representation: Both state and action spaces are finite, Q-values stored in a table
  2. All state-action pairs visited infinitely: Eachmust be updated infinitely many times
  3. Learning rate satisfies Robbins-Monro conditions:Intuitively, the first conditionmeans the sum of learning rates is large enough to overcome any initial error; the second conditionensures learning rates decay small enough for the algorithm to eventually stabilize near the optimal value. Typical choices areor.

Under these conditions, Q-Learning converges to the optimal Q functionwith probability 1, regardless of the behavior policy (as long as the visitation condition is met). This is a very strong theoretical guarantee — it tells us that even if we use a random policy during exploration, we will eventually learn the optimal policy with enough patience.

Cliff Walking Example: Q-Learning Intuition

Let's build intuition with a classic example. Cliff Walking is a grid world: the agent starts from the bottom-left corner and needs to reach the goal at the bottom-right corner, but there's a row of cliffs at the bottom — falling off gives -100 reward and returns to start. Each step gives -1 reward.

In this environment, the optimal path is to walk along the cliff edge (shortest path), but it's easy to fall during exploration. What happens with Q-Learning updates?

Initially, all Q-values are 0. When the agent first falls off the cliff, the transitionleads to:This negative value propagates to the previous state: when moving right fromto:Ifandis already -100, thenwill choose right or up (higher Q-values), so the negative value doesn't directly propagate. But if the agent continues exploring and falls multiple times, the Q-values at cliff edges gradually decrease, forcing the policy to learn detours.

This example demonstrates two properties of Q-Learning: 1. Propagation of negative rewards: Low Q-values in dangerous areas propagate forward, forming "forbidden zones" 2. Advantage of off-policy: Even if the behavior policy frequently falls (exploration), the learnedstill corresponds to the optimal path (exploitation)

Complete Python implementation:

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
import numpy as np
import matplotlib.pyplot as plt

class CliffWalkingEnv:
    """
    Cliff Walking environment: 4x12 grid world
    Start: (3,0), Goal: (3,11)
    Cliff: (3,1) to (3,10)
    """
    def __init__(self):
        self.height = 4
        self.width = 12
        self.start = (3, 0)
        self.goal = (3, 11)
        self.cliff = [(3, i) for i in range(1, 11)]
        
    def reset(self):
        self.state = self.start
        return self.state
    
    def step(self, action):
        # Actions: 0=up, 1=right, 2=down, 3=left
        row, col = self.state
        if action == 0:
            row = max(0, row - 1)
        elif action == 1:
            col = min(self.width - 1, col + 1)
        elif action == 2:
            row = min(self.height - 1, row + 1)
        elif action == 3:
            col = max(0, col - 1)
        
        next_state = (row, col)
        
        # Check if fell off cliff
        if next_state in self.cliff:
            reward = -100
            done = False
            next_state = self.start  # Return to start
        elif next_state == self.goal:
            reward = 0  # Reached goal (each step already penalized with -1)
            done = True
        else:
            reward = -1
            done = False
        
        self.state = next_state
        return next_state, reward, done

def q_learning(env, episodes=500, alpha=0.1, gamma=0.99, epsilon=0.1):
    """
    Q-Learning algorithm
    """
    Q = {}  # Use dictionary for sparse representation of Q-values
    for s in [(i,j) for i in range(env.height) for j in range(env.width)]:
        for a in range(4):
            Q[(s, a)] = 0.0
    
    rewards_per_episode = []
    
    for ep in range(episodes):
        state = env.reset()
        total_reward = 0
        steps = 0
        
        while steps < 1000:  # Prevent infinite loops
            # epsilon-greedy policy
            if np.random.rand() < epsilon:
                action = np.random.randint(4)
            else:
                q_values = [Q[(state, a)] for a in range(4)]
                action = np.argmax(q_values)
            
            next_state, reward, done = env.step(action)
            total_reward += reward
            
            # Q-Learning update
            best_next_q = max([Q[(next_state, a)] for a in range(4)])
            td_error = reward + gamma * best_next_q - Q[(state, action)]
            Q[(state, action)] += alpha * td_error
            
            state = next_state
            steps += 1
            
            if done:
                break
        
        rewards_per_episode.append(total_reward)
        
        if (ep + 1) % 100 == 0:
            avg_reward = np.mean(rewards_per_episode[-100:])
            print(f"Episode {ep+1}, Avg Reward: {avg_reward:.2f}")
    
    return Q, rewards_per_episode

# Run experiment
env = CliffWalkingEnv()
Q, rewards = q_learning(env, episodes=500)

# Visualize learning curve
plt.figure(figsize=(10, 5))
plt.plot(rewards, alpha=0.3)
plt.plot(np.convolve(rewards, np.ones(50)/50, mode='valid'), linewidth=2)
plt.xlabel('Episode')
plt.ylabel('Total Reward')
plt.title('Q-Learning on Cliff Walking')
plt.grid(True)
plt.show()

# Extract optimal policy
def extract_policy(Q, env):
    policy = {}
    for s in [(i,j) for i in range(env.height) for j in range(env.width)]:
        q_values = [Q[(s, a)] for a in range(4)]
        policy[s] = np.argmax(q_values)
    return policy

optimal_policy = extract_policy(Q, env)
print("Optimal policy example (near start):", 
      {s: ['↑','→','↓','←'][optimal_policy[s]] 
       for s in [(3,0), (2,0), (2,1), (2,2)]})

This code demonstrates the complete Q-Learning flow: initialize Q-table, interact with environment, compute TD error, update Q-values. After running, you'll find the learning curve has large oscillations early on (frequent cliff falls), but as training progresses, the agent gradually learns to avoid the cliff, eventually stabilizing around -13 reward (optimal path length).

Necessity and Challenges of Function Approximation

Curse of Dimensionality: Why Tables Aren't Enough

Cliff Walking has only 48 states, so storing Q-values in a table is no problem. But consider Atari games:

  • Breakout: Input is 84x84x4 grayscale frame stack (4 frames of history), state space size approximately
  • Go: 19x19 board, each intersection has 3 states (black/white/empty), state spaceEven with the most advanced storage technology, we cannot store a Q-value for every state. More seriously, in such huge spaces, the agent will almost never encounter the exact same state twice — meaning each state is visited only once, violating Q-Learning's convergence conditions.

The solution is function approximation: use a parameterized functionto approximate the true Q-values, whereare learnable parameters. For neural networks,are weights and biases. This way, even when encountering new states, as long as they're "similar" to seen states, the network can generalize and give reasonable Q-value estimates.

Deadly Triad: Triple Threat to Stability

However, function approximation brings serious stability issues. Sutton and Barto summarized the Deadly Triad in "Reinforcement Learning: An Introduction":

  1. Bootstrapping: Updating estimates with estimates
    • Q-Learning's update targetitself depends on Q estimates
  2. Function Approximation: Replacing tables with parameterized functions
    • Updating Q-value of one state affects Q-values of other "similar" states
  3. Off-Policy: Learning policy differs from behavior policy
    • Distribution mismatch between behavior and target policies introduces distributional shift

Combining all three can cause training divergence. Let's mathematically analyze why.

Mathematics of Divergence

Consider linear function approximation:, whereis a feature vector. Q-Learning's parameter update is:The problem is the targetdepends on— when we update, the target also moves (moving target). It's like shooting at a moving target where the target's movement direction depends on your aim.

Worse, function approximation introduces generalization: updatingaffects(ifandare similar). If update directions are inconsistent, oscillations can occur:

  • Updatingincreases it → due to generalization,also increases
  • But's true Q-value is low → next update decreases
  • Generalization affectsagain, forming a cycle

Baird constructed a counterexample in 1995 showing even simple linear function approximation + Q-Learning can diverge. In his "star counterexample", 7 states connected in a star structure with 6 features, standard Q-Learning updates cause parametersto explode exponentially.

Early Attempts: Neural Fitted Q-Iteration (NFQ)

Before DQN, Riedmiller proposed Neural Fitted Q-Iteration (NFQ) in 2005. The idea:

  1. Collect a batch of experiences$(s,a,r,s')y = r + _{a'} Q(s',a') = (y - Q(s,a))^2$4. Repeat steps 1-3

NFQ worked on simple tasks but remained unstable in high-dimensional environments like Atari. Reasons: - Sample correlation: Consecutively collected experiencesare highly correlated (directly follows) - Non-stationary distribution: After each policy update, newly collected data distribution changes

DQN's two innovations address exactly these two problems.

Core Innovations of DQN

Experience Replay: Breaking Correlations

Experience replay draws from supervised learning's "data shuffling". In supervised learning, training sequentially (e.g., training all cat images first, then all dog images) causes models to overfit to data order, leading to catastrophic forgetting. The solution is randomly shuffling data at each epoch start.

DQN applies this to reinforcement learning:

  1. Store experiences: Maintain a replay bufferwith capacity(e.g., 1 million)

  2. Add experiences: After each environment interaction yielding, store it in

  3. Sample for training: Each update samples a mini-batch uniformly from(e.g., 32 transitions)

  4. Overwrite old data: Whenis full, new experiences overwrite oldest (FIFO queue)

This has three major benefits:

Benefit 1: Break Temporal Correlations

Consecutive experiencesandare highly correlated (sharing). Training on them consecutively makes gradient directions very similar, causing parameter updates to get stuck in local patterns. After random sampling, samples in each mini-batch come from different timesteps, greatly reducing correlation.

From an information theory perspective, let the mutual information between consecutive samples be. After random sampling, the expected mutual information becomes:This reduces gradient estimate variance, making training more stable.

Benefit 2: Improve Sample Efficiency

In on-policy methods, each experience can only be used once (discarded after use). Experience replay allows us to reuse the same experience multiple times — as long as it's still in the buffer, it can be sampled. This is especially important for sample-expensive environments (like robot control).

Let each experience be used an average oftimes (depending on buffer size and update frequency), sample efficiency improves by approximatelytimes. In DQN implementations,can reach tens.

Benefit 3: Smooth Distribution Changes

When policies update, new policies collect different data distributions. But since the buffer stores data from many old policies, the current training data distribution is a mixture of multiple policies, changing more smoothly. This avoids "sharp turns"— one policy update causing dramatic distribution change, making the next update's target completely different.

Mathematically, let the-th policy bewith corresponding state distribution. The buffer distribution is:whereis the number of new samples added per round. This mixed distribution's change rate is much smaller than single's change rate.

Implementation Details: ReplayBuffer

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
import numpy as np
import random
from collections import deque

class ReplayBuffer:
    """
    Experience replay buffer
    """
    def __init__(self, capacity=100000):
        self.buffer = deque(maxlen=capacity)
    
    def push(self, state, action, reward, next_state, done):
        """Add an experience"""
        self.buffer.append((state, action, reward, next_state, done))
    
    def sample(self, batch_size):
        """Randomly sample a batch of experiences"""
        batch = random.sample(self.buffer, batch_size)
        
        # Convert to numpy arrays (convenient for PyTorch)
        states = np.array([x[0] for x in batch])
        actions = np.array([x[1] for x in batch])
        rewards = np.array([x[2] for x in batch])
        next_states = np.array([x[3] for x in batch])
        dones = np.array([x[4] for x in batch], dtype=np.float32)
        
        return states, actions, rewards, next_states, dones
    
    def __len__(self):
        return len(self.buffer)

This implementation uses deque (double-ended queue) to automatically handle capacity limits — new elements push out oldest. Sampling uses random.sample to ensure uniformity.

Target Network: Stabilizing Moving Targets

Even with experience replay, DQN still faces the "moving target" problem: updating parameterchanges the TD target. The target network idea is: use a separate network to compute targets and synchronize periodically.

Specifically, DQN maintains two networks:

  1. Online network: Parameters, used for action selection and computing current Q-values
  2. Target network: Parameters, only used for computing TD targets

The update rule becomes: The key: for a certain period (e.g., 10000 steps),remains fixed while onlyupdates. This way, TD targets are fixed during this period (or at least change slowly), avoiding "chasing a moving target".

Everysteps (e.g., 10000), perform hard update:Or use soft update, executed every step:The original DQN paper uses hard updates, while many later algorithms (like DDPG, SAC) use soft updates. Soft updates make target network changes smoother, but hard updates are simpler to implement.

Theoretical Analysis: Why Target Networks Work

Target networks can be understood through the variance-bias tradeoff. Consider the variance of TD targets:Ifchanges rapidly (updated every step),becomes large. Fixing the target networkforsteps greatly reduces variance:The cost is introducing bias:is outdated, so targetisn't completely accurate. But experiments show this bias is much smaller than the benefit of variance reduction.

Mathematically, we can quantify using the expectation of Bellman error:whereis the Bellman operator,uses fixed parameters. The second term has smaller variance and is easier to optimize.

Complete DQN Algorithm Analysis

Pseudocode and Flow

Now we can write the complete DQN algorithm:

Algorithm: Deep Q-Network (DQN)

Input: - Environment - Q-network architecture - Replay buffer capacity - Batch size - Learning rate - Discount factor - Exploration rate - Target network update frequency Output: Trained Q-network parameters$N^- $

  1. for episodedo 5.Initialize state$s_0t = 0, 1, 2, a_ta_t = a Q(s_t, a)a_tr_t, s_{t+1}, (s_t, a_t, r_t, s_{t+1}, )(s_i, a_i, r_i, s'i, i)By_i = r_i + (1 - i) {a'} Q{-}(s'i, a')() = i (y_i - Q(s_i, a_i))^2- ()C- ({}, _{})$then break
  2. end for

Key points:

  • Line 11:ensures terminal state targets are(no future returns)
  • Line 10: Only start training when(prefill buffer)
  • Exploration decay: Initiallyencourages exploration, gradually decays tofavoring exploitation

Loss Function and Gradient Computation

DQN's loss function is the mean squared TD error:Gradient with respect to:Note: 1. Targetis treated as constant (detached), doesn't participate in gradient computation 2. Only gradient ofis retained

This is identical to supervised learning's regression loss, except here the "true label"is self-estimated (bootstrapping).

Training Tricks

Gradient Clipping

Atari environments have large reward ranges (e.g., Breakout brick scores can accumulate to hundreds), causing large TD errors and potential gradient explosion. DQN uses gradient clipping:In PyTorch: torch.nn.utils.clip_grad_norm_(model.parameters(), max_norm=10).

Learning Rate Scheduling

DQN typically uses fixed learning rate (e.g.,), but in some tasks, cosine annealing or exponential decay can improve late-stage performance:

Reward Clipping and Normalization

Atari games have vastly different reward scales (Pong is -1/0/+1, Breakout can reach hundreds). The DQN paper clips all positive rewards to +1, negative to -1:This allows using the same hyperparameters across different games. But it discards reward magnitude information — may not be suitable for some tasks.

Complete Atari DQN Implementation

Below is a complete DQN implementation for Atari Pong (approximately 350 lines):

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
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
import torch
import torch.nn as nn
import torch.optim as optim
import torch.nn.functional as F
import numpy as np
import random
from collections import deque
import gym

# ===== Neural Network Architecture =====
class DQN(nn.Module):
    """
    DQN network: 3 conv layers + 2 fully connected layers
    Input: 84x84x4 state (4-frame grayscale stack)
    Output: Q-value for each action
    """
    def __init__(self, n_actions):
        super(DQN, self).__init__()
        self.conv1 = nn.Conv2d(4, 32, kernel_size=8, stride=4)
        self.conv2 = nn.Conv2d(32, 64, kernel_size=4, stride=2)
        self.conv3 = nn.Conv2d(64, 64, kernel_size=3, stride=1)
        self.fc1 = nn.Linear(64 * 7 * 7, 512)
        self.fc2 = nn.Linear(512, n_actions)
    
    def forward(self, x):
        # x: (batch, 4, 84, 84)
        x = F.relu(self.conv1(x))  # -> (batch, 32, 20, 20)
        x = F.relu(self.conv2(x))  # -> (batch, 64, 9, 9)
        x = F.relu(self.conv3(x))  # -> (batch, 64, 7, 7)
        x = x.view(x.size(0), -1)  # flatten
        x = F.relu(self.fc1(x))
        x = self.fc2(x)
        return x

# ===== Experience Replay Buffer =====
class ReplayBuffer:
    def __init__(self, capacity):
        self.buffer = deque(maxlen=capacity)
    
    def push(self, state, action, reward, next_state, done):
        self.buffer.append((state, action, reward, next_state, done))
    
    def sample(self, batch_size):
        batch = random.sample(self.buffer, batch_size)
        states, actions, rewards, next_states, dones = zip(*batch)
        return (np.array(states), np.array(actions), 
                np.array(rewards), np.array(next_states), 
                np.array(dones, dtype=np.float32))
    
    def __len__(self):
        return len(self.buffer)

# ===== DQN Agent =====
class DQNAgent:
    def __init__(self, n_actions, device='cuda'):
        self.n_actions = n_actions
        self.device = device
        
        # Initialize networks
        self.policy_net = DQN(n_actions).to(device)
        self.target_net = DQN(n_actions).to(device)
        self.target_net.load_state_dict(self.policy_net.state_dict())
        self.target_net.eval()  # Target network doesn't need training
        
        # Optimizer
        self.optimizer = optim.Adam(self.policy_net.parameters(), lr=2.5e-4)
        
        # Replay buffer
        self.memory = ReplayBuffer(capacity=100000)
        
        # Hyperparameters
        self.gamma = 0.99
        self.batch_size = 32
        self.epsilon_start = 1.0
        self.epsilon_end = 0.01
        self.epsilon_decay = 0.995
        self.epsilon = self.epsilon_start
        self.target_update_freq = 10000
        self.steps_done = 0
    
    def select_action(self, state, training=True):
        """Select action (epsilon-greedy)"""
        if training and random.random() < self.epsilon:
            return random.randrange(self.n_actions)
        else:
            with torch.no_grad():
                state_t = torch.FloatTensor(state).unsqueeze(0).to(self.device)
                q_values = self.policy_net(state_t)
                return q_values.argmax(dim=1).item()
    
    def train_step(self):
        """Execute one training update"""
        if len(self.memory) < self.batch_size:
            return None
        
        # Sample batch of experiences
        states, actions, rewards, next_states, dones = self.memory.sample(self.batch_size)
        
        # Convert to tensors
        states = torch.FloatTensor(states).to(self.device)
        actions = torch.LongTensor(actions).to(self.device)
        rewards = torch.FloatTensor(rewards).to(self.device)
        next_states = torch.FloatTensor(next_states).to(self.device)
        dones = torch.FloatTensor(dones).to(self.device)
        
        # Current Q-values: Q(s, a)
        current_q = self.policy_net(states).gather(1, actions.unsqueeze(1)).squeeze(1)
        
        # Target Q-values: r + gamma * max_a' Q_target(s', a')
        with torch.no_grad():
            next_q = self.target_net(next_states).max(1)[0]
            target_q = rewards + (1 - dones) * self.gamma * next_q
        
        # Compute loss
        loss = F.mse_loss(current_q, target_q)
        
        # Backpropagation
        self.optimizer.zero_grad()
        loss.backward()
        # Gradient clipping
        torch.nn.utils.clip_grad_norm_(self.policy_net.parameters(), max_norm=10)
        self.optimizer.step()
        
        # Update step count
        self.steps_done += 1
        
        # Update target network
        if self.steps_done % self.target_update_freq == 0:
            self.target_net.load_state_dict(self.policy_net.state_dict())
        
        # Decay epsilon
        if self.epsilon > self.epsilon_end:
            self.epsilon *= self.epsilon_decay
        
        return loss.item()
    
    def save(self, path):
        torch.save(self.policy_net.state_dict(), path)
    
    def load(self, path):
        self.policy_net.load_state_dict(torch.load(path))
        self.target_net.load_state_dict(self.policy_net.state_dict())

# ===== Environment Wrapper (Preprocessing) =====
class AtariPreprocessing:
    """Atari preprocessing: grayscale, resize, frame stack"""
    def __init__(self, env, frame_stack=4):
        self.env = env
        self.frame_stack = frame_stack
        self.frames = deque(maxlen=frame_stack)
    
    def reset(self):
        obs = self.env.reset()
        obs = self._preprocess(obs)
        for _ in range(self.frame_stack):
            self.frames.append(obs)
        return self._get_state()
    
    def step(self, action):
        obs, reward, done, info = self.env.step(action)
        obs = self._preprocess(obs)
        self.frames.append(obs)
        return self._get_state(), np.sign(reward), done, info
    
    def _preprocess(self, frame):
        """Grayscale and resize to 84x84"""
        frame = frame[34:194]  # Crop Pong top/bottom borders
        frame = frame[::2, ::2, 0]  # Downsample and take single channel
        frame = frame / 255.0
        return frame
    
    def _get_state(self):
        """Return 4-frame stack"""
        return np.array(self.frames)

# ===== Training Loop =====
def train_dqn(env_name='PongNoFrameskip-v4', n_episodes=1000, device='cuda'):
    # Create environment
    env = gym.make(env_name)
    env = AtariPreprocessing(env)
    n_actions = env.env.action_space.n
    
    # Create agent
    agent = DQNAgent(n_actions, device=device)
    
    # Training statistics
    episode_rewards = []
    episode_losses = []
    
    for episode in range(n_episodes):
        state = env.reset()
        total_reward = 0
        losses = []
        
        while True:
            # Select action
            action = agent.select_action(state)
            
            # Execute action
            next_state, reward, done, _ = env.step(action)
            total_reward += reward
            
            # Store experience
            agent.memory.push(state, action, reward, next_state, done)
            
            # Train
            loss = agent.train_step()
            if loss is not None:
                losses.append(loss)
            
            state = next_state
            
            if done:
                break
        
        episode_rewards.append(total_reward)
        avg_loss = np.mean(losses) if losses else 0
        episode_losses.append(avg_loss)
        
        # Print progress
        if (episode + 1) % 10 == 0:
            avg_reward = np.mean(episode_rewards[-10:])
            print(f"Episode {episode+1}, Avg Reward: {avg_reward:.2f}, "
                  f"Epsilon: {agent.epsilon:.3f}, Loss: {avg_loss:.4f}")
        
        # Save model
        if (episode + 1) % 100 == 0:
            agent.save(f'dqn_pong_{episode+1}.pth')
    
    return agent, episode_rewards, episode_losses

# ===== Run Training =====
if __name__ == '__main__':
    device = 'cuda' if torch.cuda.is_available() else 'cpu'
    print(f"Using device: {device}")
    
    agent, rewards, losses = train_dqn(n_episodes=1000, device=device)
    
    # Visualization
    import matplotlib.pyplot as plt
    
    plt.figure(figsize=(12, 5))
    
    plt.subplot(1, 2, 1)
    plt.plot(rewards, alpha=0.3)
    plt.plot(np.convolve(rewards, np.ones(50)/50, mode='valid'), linewidth=2)
    plt.xlabel('Episode')
    plt.ylabel('Total Reward')
    plt.title('Training Rewards')
    plt.grid(True)
    
    plt.subplot(1, 2, 2)
    plt.plot(losses, alpha=0.3)
    plt.plot(np.convolve(losses, np.ones(50)/50, mode='valid'), linewidth=2)
    plt.xlabel('Episode')
    plt.ylabel('Loss')
    plt.title('Training Loss')
    plt.grid(True)
    
    plt.tight_layout()
    plt.savefig('dqn_training.png')
    plt.show()

This code contains all key DQN components: convolutional neural network, experience replay, target network, epsilon-greedy exploration, gradient clipping. After training for about 200-300 episodes on Pong, the agent typically reaches near-optimal performance (average reward close to +21, winning by 21 points per game).

DQN Variants: From Double to Rainbow

Double DQN: Addressing Q-Value Overestimation

Problem: Positive Bias ofOperation

Theoperation in DQN's update targetcauses systematic overestimation. The reason:

Let true Q-values be, our estimates, whereis estimation error (zero mean). Then:Even though, taking the maximum tends to select actions with positive errors:This inequality is Jensen's inequality (for convex function). Overestimation accumulates: current state's overestimation propagates to previous states, forming positive feedback.

Solution: Decouple Selection and Evaluation

Double DQN (van Hasselt et al., 2016) uses the online network to select actions and the target network to evaluate them. The update target becomes:Note thatuses(online network), but evaluation uses(target network). This way, even if the online network overestimates an action, the target network is unlikely to simultaneously overestimate the same action (errors uncorrelated), reducing bias.

Mathematically, let two independent estimates have errors(i.i.d.), then:Becauseis independent of theselection, its expectation remains zero.

Numerical Example

Consider a statewith 3 actions, true Q-values, estimation errors:

  • DQN:(overestimate by 2)
  • Double DQN: Online network selects action 2 (Q=12), target network evaluates(assume target network's error), getting 9.5 (closer to true value)

Implementation

Only need to modify one line:

1
2
3
4
5
6
7
8
9
10
# Original DQN target
with torch.no_grad():
    next_q = self.target_net(next_states).max(1)[0]  # Target network selects + evaluates
    target_q = rewards + (1 - dones) * self.gamma * next_q

# Double DQN target
with torch.no_grad():
    next_actions = self.policy_net(next_states).argmax(1)  # Online network selects
    next_q = self.target_net(next_states).gather(1, next_actions.unsqueeze(1)).squeeze(1)  # Target network evaluates
    target_q = rewards + (1 - dones) * self.gamma * next_q

Experiments show Double DQN reduces overestimation in most Atari games, improving stability and final performance.

Dueling DQN: Separating State Value and Advantage

Motivation: Not All States Need to Care About Actions

Consider two scenarios in Atari games: 1. Urgent situations (like ball about to be missed in Pong): action choice is critical 2. Calm moments (like ball far from paddle): regardless of action, values are similar

Traditional DQN uses the same network head to output all, needing to simultaneously learn "how good is this state" and "relative merit of each action". Dueling DQN separates the two:Where: -: State value, measures expected return at, action-independent -: Advantage function, measures how much better actionis than average

Intuitively,answers "how good is this state",answers "how much better is this action than average".

Identifiability Problem

Directly separatingandhas a problem: given, the decomposition isn't unique. For example,can decompose asor. For uniqueness, force advantage function's mean to be zero:Or use maximum advantage as zero (more common in practice):This way, the optimal action'sis 0, andequals.

Network Architecture

Dueling DQN's convolutional layers are same as DQN, but fully connected layers split into two streams:

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
class DuelingDQN(nn.Module):
    def __init__(self, n_actions):
        super(DuelingDQN, self).__init__()
        # Shared convolutional layers
        self.conv1 = nn.Conv2d(4, 32, kernel_size=8, stride=4)
        self.conv2 = nn.Conv2d(32, 64, kernel_size=4, stride=2)
        self.conv3 = nn.Conv2d(64, 64, kernel_size=3, stride=1)
        
        # Value stream
        self.value_fc = nn.Linear(64 * 7 * 7, 512)
        self.value_head = nn.Linear(512, 1)
        
        # Advantage stream
        self.advantage_fc = nn.Linear(64 * 7 * 7, 512)
        self.advantage_head = nn.Linear(512, n_actions)
    
    def forward(self, x):
        # Shared feature extraction
        x = F.relu(self.conv1(x))
        x = F.relu(self.conv2(x))
        x = F.relu(self.conv3(x))
        x = x.view(x.size(0), -1)
        
        # Value stream
        value = F.relu(self.value_fc(x))
        value = self.value_head(value)  # (batch, 1)
        
        # Advantage stream
        advantage = F.relu(self.advantage_fc(x))
        advantage = self.advantage_head(advantage)  # (batch, n_actions)
        
        # Combine: Q = V + (A - mean(A))
        q_values = value + (advantage - advantage.mean(dim=1, keepdim=True))
        return q_values

Why It Works

Dueling architecture's advantage is more efficient value function learning. In many states, action choice has little impact on value — at this pointcan learn from experiences of all actions (data sharing), rather than eachlearning independently. This is like introducing inductive bias: telling the network "first learn to evaluate state quality, then learn details".

Experiments show Dueling DQN has significant improvements in tasks requiring long-term planning (like Seaquest, Enduro), because in these tasks differences in state value matter more.

Prioritized Experience Replay: Importance Sampling

Problem: Not All Experiences Are Equally Important

Uniform random sampling in experience replay assumes all experiences are equally important, but intuitively: - High TD-error experiences are more "surprising", contain more information - Low TD-error experiences are already well-learned, repeated training has diminishing returns

Prioritized Experience Replay (PER, Schaul et al., 2016) allocates sampling probability based on TD error magnitude.

Priority Definition

Each experience's priority is defined as:whereis the TD error,is a small constant (avoid zero priority). Sampling probability:wherecontrols priority strength (degrades to uniform sampling,fully prioritized).

Importance Sampling Weights

Prioritized sampling changes data distribution, introducing bias. To correct, use importance sampling weights:And normalize:. Loss function becomes weighted version: anneals from 0.4 to 1.0 (weak bias correction initially, full correction later).

Implementation

Needs to maintain a priority queue, can use SumTree data structure forsampling and updating:

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
class PrioritizedReplayBuffer:
    def __init__(self, capacity, alpha=0.6):
        self.capacity = capacity
        self.alpha = alpha
        self.buffer = []
        self.priorities = np.zeros(capacity, dtype=np.float32)
        self.position = 0
    
    def push(self, transition):
        max_priority = self.priorities.max() if self.buffer else 1.0
        
        if len(self.buffer) < self.capacity:
            self.buffer.append(transition)
        else:
            self.buffer[self.position] = transition
        
        self.priorities[self.position] = max_priority
        self.position = (self.position + 1) % self.capacity
    
    def sample(self, batch_size, beta=0.4):
        N = len(self.buffer)
        priorities = self.priorities[:N]
        
        # Compute sampling probabilities
        probs = priorities ** self.alpha
        probs /= probs.sum()
        
        # Sample indices
        indices = np.random.choice(N, batch_size, p=probs)
        
        # Compute importance sampling weights
        weights = (N * probs[indices]) ** (-beta)
        weights /= weights.max()
        
        # Extract experiences
        batch = [self.buffer[i] for i in indices]
        
        return batch, indices, weights
    
    def update_priorities(self, indices, td_errors):
        """Update priorities based on TD errors"""
        for idx, td_error in zip(indices, td_errors):
            self.priorities[idx] = abs(td_error) + 1e-6

PER significantly improves sample efficiency but has higher implementation complexity and slightly increased training time.

Other Rainbow Components

Noisy Networks: Replace-greedy exploration with learnable noise. Add noise parameters to weights:where bothare learnable. This way exploration policy can also be optimized through gradients.

Multi-step Learning: Replace 1-step TD target with n-step return:n-step propagates reward signals faster but has higher variance (typically).

Distributional RL (C51): Don't learn Q-value expectation, learn entire distribution. Discretize value range into 51 bins, train distribution prediction with cross-entropy loss. This captures risk (variance) information, beneficial for exploration.

Rainbow: Combines all 6 techniques (Double DQN, Dueling, PER, Noisy Nets, Multi-step, C51), achieving state-of-the-art performance on Atari at the time. Ablation studies show each technique contributes, and combined effect exceeds simple addition (synergy).

Theoretical Analysis

Theoretical Guarantees of Experience Replay

From an optimization perspective, experience replay samples from experience distributionrather than immediate policy. Let current policy's state distribution be, buffer's mixed distribution be. Training objective is to minimize:If(buffer covers optimal policy's distribution), convergence point is optimal Q function. But actuallyis a mixture of multiple policies, potentially deviating significantly from— an inherent issue of off-policy methods.

Good news: Munos et al. (2016) proved that if replay buffer data satisfies certain coverage conditions, and target network updates slowly enough, DQN can still converge to approximately optimal solution with certain probability, error bound, whereis function approximation error,is sampling error.

Variance Analysis of Target Networks

Target networks' role can be understood through the variance-bias tradeoff. Consider TD target variance:Ifchanges rapidly (updated every step),becomes large. Fixing target networkforsteps greatly reduces variance:The cost is introducing bias:is outdated, so targetisn't completely accurate. But experiments show this bias is much smaller than variance reduction benefits.

Mathematically, we can quantify using Bellman error expectation:whereis the Bellman operator,uses fixed parameters. The second term has smaller variance and is easier to optimize.

Practical Tips and Debugging

Hyperparameter Selection

Hyperparameter Typical Value Description
buffer_size 100k-1M Larger is better, but memory limited; Atari uses 1M
batch_size 32-128 Too small unstable, too large slow training; 32 common
learning_rate 1e-4 to 1e-3 Adam optimizer typically uses 2.5e-4
gamma 0.99 Discount factor, 0.99 for long-term, 0.9 for short-term
epsilon_start 1.0 Initial exploration rate
epsilon_end 0.01-0.1 Final exploration rate, 0.01 for Atari
epsilon_decay 0.995 Per-episode decay factor, or linear decay
target_update_freq 1k-10k Target network update frequency, 10k common

Tuning Advice: 1. Start with smaller buffer_size and larger learning_rate to quickly verify code correctness 2. After confirming loss decreases and reward increases, use full hyperparameters for long training 3. If training unstable (loss oscillates, reward collapses), reduce learning_rate or increase target_update_freq

Training Curve Analysis

Normal Curve: Reward gradually rises, loss first rises then falls - Early stage (0-100 episodes): Reward near random level, loss rises (Q-values grow from 0, TD error increases) - Middle stage (100-500 episodes): Reward improves rapidly, loss peaks then falls (Q-values stabilize) - Late stage (500+ episodes): Reward converges near optimal, loss stabilizes at low level

Anomalies: - Loss Explosion: Suddenly increases to 1e3 or 1e6 - Cause: Gradient explosion or Q-value divergence - Solution: Check gradient clipping, reduce learning rate, check if rewards are unnormalized - Reward Collapse: First rises then suddenly drops and doesn't recover - Cause: Catastrophic forgetting or local optimum - Solution: Increase buffer_size, reduce learning rate, check if target network updates too frequently - Reward Stagnation: Stays at random level for long time - Cause: Insufficient exploration or inadequate network capacity - Solution: Increase epsilon or extend epsilon_decay, check network architecture

Debugging Techniques

1. Monitor Q-Value Distribution

Print Q-value statistics during training:

1
2
3
4
with torch.no_grad():
    q_values = agent.policy_net(states)
    print(f"Q mean: {q_values.mean():.2f}, Q std: {q_values.std():.2f}, "
          f"Q max: {q_values.max():.2f}, Q min: {q_values.min():.2f}")

Normally, Q-values should gradually increase and stabilize. If Q-values continuously explode (e.g., exceed 1000), there's a problem.

2. Check TD Error

Print TD error distribution:

1
2
td_errors = (target_q - current_q).abs()
print(f"TD error mean: {td_errors.mean():.4f}, max: {td_errors.max():.4f}")

TD error should gradually decrease. If it stays high for long, the network isn't learning useful patterns.

3. Visualize Action Distribution

Count frequency of agent selecting each action:

1
2
3
4
5
action_counts = np.zeros(n_actions)
for _ in range(100):
    action = agent.select_action(state, training=False)
    action_counts[action] += 1
print("Action distribution:", action_counts / 100)

If an action is never selected, the network may be stuck in a local optimum.

4. Test on Simplified Environments

When debugging complex environments (like Atari), first verify code correctness on simple environments (like CartPole):

1
2
env = gym.make('CartPole-v1')
# CartPole should solve in 100-200 episodes (average reward > 195)

If simple environments don't work, there's a bug in the code.

Deep Q&A

Q1: Why does DQN use off-policy instead of on-policy?

A: Off-policy's core advantage is data utilization efficiency. On-policy methods (like SARSA, A3C) require training data to come from the current policy — after each policy update, old data becomes obsolete. Off-policy methods (like Q-Learning, DQN) can use data collected by any policy, as long as it explored relevant state-action pairs.

DQN's experience replay leverages this: data in the buffer comes from multiple past policies (), but all can be used to update the current policy. This allows each experience to be reused dozens of times, dramatically improving sample efficiency.

The cost is off-policy methods are harder to converge (due to distribution mismatch between data and target policy), requiring additional stabilization techniques (like target networks). But in sample-expensive scenarios (like robotics, Atari), this trade-off is worthwhile.

Q2: How to choose experience replay buffer size?

A: Buffer sizechoice balances three factors:

  1. Coverage: Largermeans buffer covers broader state distribution, smaller off-policy bias
  2. Freshness: Smallermeans buffer data is more "fresh", closer to current policy
  3. Memory Limits: Storingrequires memory, Atari's 84x84x4 images take ~28KB

Typical choices: - Atari: 1M (~28GB memory) - Simple environments (like CartPole): 10k-100k - Continuous control (like MuJoCo): 100k-1M

Rule of thumb: Buffer should hold at least 100 complete episodes of data. If too small (like only 10 episodes), buffer gets overwritten frequently, insufficient sample diversity.

Experimental suggestion: Start with smaller buffer (like 10k) for fast iteration, confirm code correctness, then use large buffer for training.

Q3: How serious is Double DQN's overestimation problem?

A: In many Atari games, DQN's Q-value overestimation is very significant. van Hasselt et al. showed in their paper an example:

  • Pong game: True Q-value range approximately -21 to +21 (game score)
  • DQN estimates: Q-values gradually inflate to +50 or even +100
  • Double DQN estimates: Stable around -21 to +21

Overestimation severity depends on environment randomness and action space size: - High randomness (like noisy rewards) → large estimation error → severe overestimation - Many actions (like 18 actions) → largeoperation bias → severe overestimation

In some games (like Seaquest), overestimation causes agents to choose suboptimal policies — because some "seemingly good" actions (overestimated Q-values) are actually poor. Double DQN can reduce overestimation bias by 50%-90% through decoupling selection and evaluation.

But there are exceptions: in deterministic environments (like chess), overestimation is less problematic, Double DQN's improvement is limited.

Q4: When does Dueling DQN work best?

A: Dueling DQN improves most in scenarios where action impact differences are small. Specifically:

  1. Long-term planning tasks (like Seaquest, Enduro): Most time spent "cruising", only a few critical moments need precise actions. State valueis more important than advantage.

  2. High action redundancy (like some Atari actions nearly equivalent): For example, "left" and "left+shoot" have same effect when no enemies present. Dueling can automatically identify this redundancy, focus on learning.

  3. Sparse reward environments: In most states, all actions have similar Q-values (due to sparse rewards), sois close to 0,carries main information.

Counterexample: In environments with large action differences (like fighting games where every action is critical), Dueling's advantage is less obvious, because the advantage functionitself is complex, separation doesn't simplify learning.

Q5: Why isn't Rainbow a simple 1+1=2?

A: Rainbow's performance improvement isn't a simple sum of individual techniques, but has synergy. Ablation studies show:

  • Double DQN alone: 30% improvement
  • Dueling DQN alone: 20% improvement
  • Both combined: 60% improvement (greater than 30%+20%)

Reasons: - Double DQN reduces overestimation → Dueling'smore accurate → advantagelearning more stable - PER prioritizes important samples → accelerates Double DQN's overestimation correction → faster convergence - Multi-step Learning accelerates credit assignment → combined with Distributional RL captures uncertainty → more efficient exploration

But there are negative interactions too: PER's importance sampling weightsincrease gradient variance, requiring smaller learning rate; Noisy Networks' exploration noise may conflict with Multi-step's variance. Rainbow's success lies in carefully tuning these components' hyperparameters to maximize synergy.

Q6: Why can't DQN handle continuous action spaces?

A: DQN's core operation isand, requiring enumeration of all actions. In discrete action spaces (like Atari's 18 actions), this is simple — network outputs 18 Q-values, take maximum.

But in continuous action spaces (like robot joint angles),operation becomes an optimization problem:No analytical solution, need optimization algorithms (like gradient ascent, genetic algorithms) to solve. This is not only computationally expensive but also introduces additional approximation errors.

Solutions: - Discretization: Divide continuous action space into grid (like 10x10), but curse of dimensionality causes combinatorial explosion - Actor-Critic methods: Use separate actor networkto output actions, critic networkto evaluate. This is the approach of DDPG, TD3, SAC (introduced in next chapter) - NAF (Normalized Advantage Functions): Parameterize Q-function as quadratic, optimal action has analytical solutionSummary: DQN is designed for discrete actions, extending to continuous actions requires additional architectural innovations.

Q7: How to judge if DQN training has converged?

A: Multiple indicators for judging convergence:

  1. Reward Stability: In test environment (deterministic, no exploration), average reward over 100 consecutive episodes no longer increases, and variance less than 5%.

  2. Q-Value Stability: Monitor change rate of:Iffor 1000 consecutive steps, Q-values have converged.

  3. Policy Stability: Consistency of actions over multiple inferences in same state:Extra close brace or missing open brace\text{Consistency} = \frac{\#\{\text{same actions}} }{\#\{\text{total times}} } > 0.95

  4. TD Error Stability: Average TD error on test setdrops close to 0.

In practice, Atari games typically need 10M-50M frames (about 200-1000 episodes) to converge. If reward still random walks after 1000 episodes, there's a problem.

Q8: DQN vs PPO, when to use which?

A: DQN and PPO each have suitable scenarios:

Feature DQN PPO
Action Space Discrete (small scale) Discrete + Continuous
Sample Efficiency High (experience replay) Low (on-policy)
Stability Needs tuning (target network etc.) Out-of-box
Parallelization Single environment Multi-environment
Suitable Tasks Atari, discrete control Robotics, continuous control

Selection Advice: - Discrete actions + expensive samples (like robot grasping 5 minutes per try) → DQN - Continuous actions + abundant sampling (like simulator environments) → PPO - Need fast prototyping (don't want to tune) → PPO - Pursue ultimate performance (willing to fine-tune) → Rainbow DQN

Interesting phenomenon: On Atari, DQN's final performance is usually higher than PPO, but PPO's training curve is smoother. This reflects off-policy methods' "high risk high reward" characteristic.

Q9: How to handle high-dimensional image input (Atari)?

A: Atari environment's raw observation is 210x160x3 RGB image, direct input causes:

  1. Too high dimensionality: 210x160x3 = 100,800 dimensions, network parameters explode
  2. Redundant information: Most pixels are background (black), low information density
  3. Temporal correlation: Single frame can't determine velocity (like ball motion direction)

DQN's preprocessing pipeline:

Step 1: Grayscale 

1
gray = np.dot(rgb[...,:3], [0.299, 0.587, 0.114])  # Convert to grayscale

Step 2: Crop irrelevant regions 

1
cropped = gray[34:194, :]  # Remove Pong's top scoreboard

Step 3: Downsample 

1
resized = cv2.resize(cropped, (84, 84))  # Resize to 84x84

Step 4: Frame Stacking 

1
state = np.stack([frame_t, frame_{t-1}, frame_{t-2}, frame_{t-3}], axis=0)  # 4-frame stack

Frame stacking solves velocity information problem — network can infer motion direction by comparing adjacent frames.

Step 5: Normalization 

1
state = state / 255.0  # Normalize to [0, 1]

After these processes, input reduces from 100,800 to 84x84x4 = 28,224 dimensions, information density greatly improved.

Q10: How is DQN's sample efficiency?

A: Sample efficiency measures "how many samples needed to reach target performance". DQN's performance is moderate:

Compared to tabular methods: - Tabular Q-Learning (CartPole): about 5000 steps - DQN (CartPole): about 50,000 steps

DQN needs 10x samples because neural networks need more data to fit Q-function.

Compared to on-policy methods: - DQN (Atari Pong): about 2M frames - A3C (on-policy): about 10M frames

DQN's experience replay improves sample efficiency by 5x.

Compared to model-based methods: - DQN (simulator): about 100k steps - Dyna-Q (model-based): about 10k steps

Model-based methods can use fewer real interactions by learning environment model and simulating in model.

Absolute numbers: On Atari, DQN typically needs 10M-50M frames (about 40-200 hours game time) to reach human level. This is unacceptable for real environments like robotics — so in practice, DQN is more used in simulator environments or combined with sim-to-real techniques.

Directions for improving sample efficiency: - Better network architectures (like ResNet, Transformer) - Auxiliary tasks (like self-supervised learning, contrastive learning) - Transfer learning (pretraining + fine-tuning)

References

Core papers on DQN and its variants (chronological order):

  1. Watkins, C. J., & Dayan, P. (1992). Q-learning. Machine Learning, 8(3-4), 279-292.
    Paper Link
    Q-Learning convergence proof

  2. Mnih, V., Kavukcuoglu, K., Silver, D., et al. (2013). Playing Atari with Deep Reinforcement Learning. NIPS Deep Learning Workshop.
    arXiv:1312.5602
    First DQN proposal, introducing experience replay and target networks

  3. Mnih, V., Kavukcuoglu, K., Silver, D., et al. (2015). Human-level control through deep reinforcement learning. Nature, 518(7540), 529-533.
    Nature Paper
    Complete DQN, achieving human-level performance on 49 Atari games

  4. van Hasselt, H., Guez, A., & Silver, D. (2016). Deep Reinforcement Learning with Double Q-learning. AAAI.
    arXiv:1509.06461
    Double DQN, addressing Q-value overestimation

  5. Wang, Z., Schaul, T., Hessel, M., et al. (2016). Dueling Network Architectures for Deep Reinforcement Learning. ICML.
    arXiv:1511.06581
    Dueling DQN, separating state value and advantage

  6. Schaul, T., Quan, J., Antonoglou, I., & Silver, D. (2016). Prioritized Experience Replay. ICLR.
    arXiv:1511.05952
    PER, prioritized sampling based on TD error

  7. Fortunato, M., Azar, M. G., Piot, B., et al. (2018). Noisy Networks for Exploration. ICLR.
    arXiv:1706.10295
    Noisy Networks, learnable exploration noise

  8. Bellemare, M. G., Dabney, W., & Munos, R. (2017). A Distributional Perspective on Reinforcement Learning. ICML.
    arXiv:1707.06887
    C51, learning value distributions instead of expectations

  9. Hessel, M., Modayil, J., van Hasselt, H., et al. (2018). Rainbow: Combining Improvements in Deep Reinforcement Learning. AAAI.
    arXiv:1710.02298
    Rainbow, integrating 6 DQN improvement techniques

  10. Sutton, R. S., & Barto, A. G. (2018). Reinforcement Learning: An Introduction (2nd ed.). MIT Press.
    Online Version
    Classic RL textbook, detailed explanation of Q-Learning and Deadly Triad

From tabular Q-Learning to DQN's deep learning, from single algorithm to Rainbow's technical integration, value-based methods have undergone tremendous evolution over the past thirty years. DQN's two innovations — experience replay and target networks — not only solved deep Q-network stability issues but also provided design paradigms for subsequent Deep RL algorithms. Variants like Double DQN, Dueling DQN, and PER each have their focus, addressing overestimation, learning efficiency, and sample efficiency issues. Rainbow's success demonstrates that carefully combined technical stacks can produce synergistic effects exceeding simple addition.

However, DQN's limitations are also obvious: only applicable to discrete action spaces, struggling with continuous control tasks. The next chapter will turn to Policy Gradient methods and Actor-Critic architectures, exploring how to directly optimize policies and naturally handle continuous action spaces — leading us into the world of modern algorithms like DDPG, TD3, and SAC.

  • Post title：Reinforcement Learning (2): Q-Learning and Deep Q-Networks (DQN)
  • Post author：Chen Kai
  • Create time：2024-08-09 14:00:00
  • Post link：https://www.chenk.top/reinforcement-learning-2-q-learning-and-dqn/
  • Copyright Notice：All articles in this blog are licensed under BY-NC-SA unless stating additionally.
 Comments