Deep Q-Networks (DQN) Algorithm

Standard Reinforcement Learning algorithms often struggle when state or action spaces become very large. Representing the value function or policy explicitly for every state (or state-action pair) becomes computationally infeasible. While function approximation offers a solution, simple linear approximators lack the capacity to capture the complex relationships present in many challenging problems, such as learning from raw pixel data in video games or robotic control from high-dimensional sensor inputs.

Deep Q-Networks (DQN) marked a significant step forward by integrating deep neural networks with the Q-learning algorithm. Instead of a table or a linear function, DQN uses a neural network to approximate the optimal action-value function, $Q^*(s, a)$.

Approximating the Q-Function with Neural Networks

The core idea is straightforward: we define a neural network, often called the Q-network, parameterized by weights $\theta$. This network takes a representation of the state $s$ as input and outputs a vector of Q-values, one for each possible action $a$ in that state. We denote the network's output for a given state $s$ and action $a$ as $Q(s, a; \theta)$.

For example, when learning to play Atari games from screen pixels, a common architecture involves:

1. Input: Raw pixel data from the game screen, typically preprocessed (e.g., converted to grayscale, downsampled, and stacked over a few consecutive time steps to capture motion).
2. Convolutional Layers: Several convolutional layers to extract spatial features from the input image stack. These act similarly to feature extractors in computer vision tasks.
3. Fully Connected Layers: One or more fully connected layers following the convolutional layers.
4. Output Layer: A final fully connected layer with a linear activation function. The number of output neurons equals the number of valid actions the agent can take in the environment. Each output neuron represents the estimated Q-value for taking the corresponding action in the input state.

A typical convolutional neural network architecture used in DQN for processing image-based inputs.

Training the Q-Network: Minimizing the Bellman Error

How do we train the weights $\theta$ of this Q-network? We adapt the standard Q-learning update rule. Recall the Bellman equation for the optimal action-value function $Q^*(s, a)$:

$$Q^*(s, a) = \mathbb{E}_{s' \sim P(\cdot|s,a)} [r + \gamma \max_{a'} Q^*(s', a')]$$

Q-learning iteratively approaches this optimum using updates based on experienced transitions $(s_t, a_t, r_t, s_{t+1})$. In the context of function approximation, we want our network $Q(s, a; \theta)$ to satisfy this equation. We can define a target value $y_t$ based on the reward received and the estimated value of the next state:

$$y_t = r_t + \gamma \max_{a'} Q(s_{t+1}, a'; \theta)$$

We then train the network by minimizing the difference between the target $y_t$ and the network's current prediction $Q(s_t, a_t; \theta)$. A common loss function is the Mean Squared Error (MSE), often referred to as the Mean Squared Bellman Error (MSBE):

$$L(\theta) = \mathbb{E}_{(s_t, a_t, r_t, s_{t+1})} \left[ (y_t - Q(s_t, a_t; \theta))^2 \right]$$

The expectation is typically approximated by averaging the squared error over a mini-batch of transitions sampled from the agent's experience. The network weights $\theta$ are updated using gradient descent methods (like RMSprop or Adam) to minimize this loss.

Addressing Training Instability

Applying this update rule directly with a non-linear function approximator like a deep neural network proved to be notoriously unstable in early attempts. This instability arises primarily from two sources, related to the "Deadly Triad" mentioned in Chapter 1 (function approximation, bootstrapping, and off-policy learning):

1. Correlated Samples: When the agent interacts with the environment, the sequence of observed transitions $(s_t, a_t, r_t, s_{t+1})$, $(s_{t+1}, a_{t+1}, r_{t+1}, s_{t+2})$, ... are highly correlated. Training the network on consecutive samples in the order they are experienced violates the independent and identically distributed (i.i.d.) data assumption underlying most stochastic gradient descent optimization methods. This can lead to inefficient learning and potential oscillations.
2. Moving Target Values: The target value $y_t = r_t + \gamma \max_{a'} Q(s_{t+1}, a'; \theta)$ depends on the current network weights $\theta$. As the weights $\theta$ are updated at each step to reduce the loss for the current batch, the target values for subsequent batches also shift. It's like chasing a moving target, which can cause the learning process to oscillate or diverge.

DQN's Innovations for Stability

The original DQN paper introduced two fundamental techniques to mitigate these instabilities and enable stable training of deep Q-networks:

1. Experience Replay: Instead of training on samples immediately as they are collected, transitions $(s_t, a_t, r_t, s_{t+1})$ are stored in a large buffer called the replay memory or replay buffer ($D$). During training, mini-batches of transitions are sampled randomly from this buffer. This breaks the temporal correlations between samples within a batch, leading to more stable and efficient learning. It also allows the agent to reuse past experiences multiple times. (This will be detailed in the section "Experience Replay Mechanism").

2. Target Network: To address the moving target issue, DQN uses a separate, periodically updated target network, denoted $\hat{Q}$, with parameters $\theta^{-}$. This target network has the same architecture as the online Q-network ($Q$ with parameters $\theta$) but its weights are kept frozen for a number of steps. The target values $y_t$ are computed using this fixed target network:

   $$y_t = r_t + \gamma \max_{a'} \hat{Q}(s_{t+1}, a'; \theta^{-})$$

   The online network $Q(s, a; \theta)$ is then trained using gradient descent to minimize the MSE loss: $L(\theta) = \mathbb{E}_{(s, a, r, s') \sim D} [ (y_t - Q(s, a; \theta))^2 ]$. Periodically (e.g., every $C$ training steps), the weights of the target network are updated by copying the weights from the online network: $\theta^{-} \leftarrow \theta$. This use of a fixed target network significantly stabilizes the learning process. (This will be detailed in the section "Target Networks for Training Stability").

The DQN Algorithm

Combining these ideas leads to the following algorithm:

1. Initialize replay memory $D$ to capacity $N$.
2. Initialize the online Q-network $Q$ with random weights $\theta$.
3. Initialize the target Q-network $\hat{Q}$ with weights $\theta^{-} = \theta$.
4. For episode = 1 to M: a. Observe initial state $s_1$. b. For t = 1 to T (or until episode termination): i. Select action $a_t$ using an $\epsilon$-greedy strategy based on $Q(s_t, \cdot; \theta)$ (i.e., with probability $\epsilon$ select a random action, otherwise select $a_t = \arg\max_{a} Q(s_t, a; \theta)$). ii. Execute action $a_t$ in the environment. iii. Observe reward $r_t$ and next state $s_{t+1}$. Determine if $s_{t+1}$ is a terminal state. iv. Store the transition (s_t, a_t, r_t, s_{t+1}, \text{is_terminal}) in $D$. v. Sample a random mini-batch of $K$ transitions $(s_j, a_j, r_j, s_{j+1}, \text{is\_terminal}_j)$ from $D$. vi. For each transition $j$ in the mini-batch, calculate the target $y_j$: If $\text{is\_terminal}_j$ is true: $y_j = r_j$ Else: $y_j = r_j + \gamma \max_{a'} \hat{Q}(s_{j+1}, a'; \theta^{-})$ vii. Perform a gradient descent step on the loss function with respect to the online network parameters $\theta$: $L = \frac{1}{K} \sum_{j=1}^{K} (y_j - Q(s_j, a_j; \theta))^2$ $\theta \leftarrow \theta - \alpha \nabla_{\theta} L$ viii. Every $C$ steps, update the target network weights: $\theta^{-} \leftarrow \theta$. c. Optionally decay $\epsilon$.

A schematic overview of the Deep Q-Network (DQN) algorithm, illustrating the interaction between the agent (containing the online and target networks), the environment, the replay buffer, and the training update mechanism.

The introduction of DQN was a landmark achievement, demonstrating that deep neural networks could be trained effectively for reinforcement learning tasks, enabling agents to learn complex policies directly from high-dimensional sensory inputs like pixels. It formed the foundation upon which many subsequent advancements in deep reinforcement learning have been built, several of which we will explore in the following sections of this chapter.