The DQN Algorithm Structure

Having explored the motivations for using deep neural networks with Q-learning and the techniques of Experience Replay and Target Networks to improve stability, we can now assemble these pieces into the standard Deep Q-Network (DQN) algorithm. This algorithm provides a framework for training an agent to learn optimal action-value functions in complex environments.

The core idea remains rooted in Q-learning: we want to learn an action-value function $Q(s, a)$ that approximates the expected return after taking action $a$ in state $s$ and following the optimal policy thereafter. However, instead of a table, we use a deep neural network, parameterized by weights $\theta$, to represent this function: $Q(s, a; \theta)$. To handle the instability issues discussed previously, we incorporate two main modifications:

1. Experience Replay: We store the agent's experiences (state, action, reward, next state tuples) in a replay memory buffer. During training, we sample mini-batches of these experiences randomly from the buffer to update the network. This breaks the temporal correlations in the sequence of observations and smooths out changes in the data distribution.
2. Target Network: We use a separate neural network, called the target network, with weights $\theta^-$, to calculate the target Q-values used in the update rule. The weights $\theta^-$ are periodically copied from the primary Q-network's weights $\theta$, but kept fixed for a certain number of steps in between updates. This provides a more stable target for the Q-learning update, preventing the target values from chasing the constantly changing predictions of the primary network.

The DQN Algorithm Flow

Here's a breakdown of the typical DQN training loop:

1. Initialization:

   • Initialize the replay memory buffer $D$ with a fixed capacity.
   • Initialize the primary Q-network $Q$ with random weights $\theta$.
   • Initialize the target Q-network $\hat{Q}$ with weights $\theta^- = \theta$.

2. Episode Loop: For each episode:

   • Reset the environment and get the initial state $s_1$.
   • Preprocess the initial state if necessary (e.g., stacking frames) to create the input representation for the network.

3. Step Loop: For each step $t = 1, 2, ... T$ within the episode:

   • Action Selection: Choose an action $a_t$ based on the current state $s_t$ using an $\epsilon$-greedy strategy derived from the primary Q-network:
     • With probability $\epsilon$, select a random action.
     • With probability $1-\epsilon$, select $a_t = \arg\max_a Q(s_t, a; \theta)$. (Often, $\epsilon$ is annealed, starting high and decreasing over time to shift from exploration to exploitation).
   • Execute Action: Take action $a_t$ in the environment. Observe the reward $r_{t+1}$ and the next state $s_{t+1}$. Preprocess $s_{t+1}$.
   • Store Experience: Store the transition tuple $(s_t, a_t, r_{t+1}, s_{t+1})$ in the replay memory $D$.
   • Sample Mini-batch: If the replay memory contains enough experiences, sample a random mini-batch of $N$ transitions $(s_j, a_j, r_{j+1}, s_{j+1})$ from $D$.
   • Calculate Targets: For each transition $(s_j, a_j, r_{j+1}, s_{j+1})$ in the mini-batch, calculate the target value $y_j$:
     • If $s_{j+1}$ is a terminal state, the target is simply the reward: $y_j = r_{j+1}$.
     • Otherwise, the target is calculated using the target network $\hat{Q}$: $$y_j = r_{j+1} + \gamma \max_{a'} \hat{Q}(s_{j+1}, a'; \theta^-)$$ where $\gamma$ is the discount factor. Notice the max operation is performed over the outputs of the target network for the next state $s_{j+1}$.
   • Gradient Descent Update: Perform a gradient descent step on the primary Q-network weights $\theta$. The loss function is typically the Mean Squared Error (MSE) between the predicted Q-values (from the primary network for the actions taken, $a_j$) and the calculated target values $y_j$: $$L(\theta) = \frac{1}{N} \sum_{j=1}^{N} (y_j - Q(s_j, a_j; \theta))^2$$ Update $\theta$ using an optimizer like Adam or RMSprop: $\theta \leftarrow \theta - \alpha \nabla_\theta L(\theta)$.
   • Update Target Network: Every $C$ steps (where $C$ is a hyperparameter), update the target network weights by copying the primary network weights: $\theta^- \leftarrow \theta$.
   • Advance State: Set $s_t \leftarrow s_{t+1}$.
   • Check Termination: If $s_t$ is a terminal state, end the current episode.

High-level interaction flow in the DQN algorithm. The agent uses its Q-Network for action selection, stores experiences in Replay Memory, samples batches to compute targets using the Target Network, and updates the Q-Network via gradient descent. The Target Network is periodically updated from the Q-Network.

This structured approach, integrating experience replay and fixed Q-targets, allows DQN to successfully train deep neural networks for Q-learning, enabling agents to learn complex behaviors directly from high-dimensional sensory inputs like pixels, which was a significant advancement in reinforcement learning. The next section looks at some of the architectural choices for the neural networks used within DQNs.