Deep Q-Learning with Space Invaders

Deep Q-Learning (DQN) enables reinforcement learning agents to operate in environments with massive state spaces by replacing traditional Q-tables with neural networks. This approach allows agents to learn complex tasks, such as playing Atari games like Space Invaders, where the number of possible states is too large for tabular methods to handle.

From Q-Learning to Deep Q-Learning

Traditional Q-Learning is a tabular method that uses a Q-table to store the value of every possible state-action pair. While effective for small environments (e.g., FrozenLake with 14 states or Taxi-v3 with 500 states), it does not scale to complex environments.

In Atari environments, the observation space is (210, 160, 3) with pixel values from 0 to 255, resulting in a state space of $256^{100800}$. Because creating a table for this many states is impossible, Deep Q-Learning uses a parametrized Q-function $Q_{\theta}(s, a)$—a neural network that approximates the Q-values for each possible action given a state.

The Deep Q-Network (DQN) Architecture

The DQN architecture takes a stack of four preprocessed frames as input and outputs a vector of Q-values for each possible action. The agent then uses an epsilon-greedy policy to select the action with the highest estimated value.

Input Preprocessing and Temporal Information

To reduce computational complexity and training time, the input frames undergo the following preprocessing:

  • Downsampling and Grayscaling: Images are reduced to 84x84 pixels and converted to grayscale, reducing three RGB channels to one.
  • Cropping: Unnecessary parts of the screen are removed.
  • Frame Stacking: Four consecutive frames are stacked together to solve the problem of temporal limitation. A single frame cannot convey motion (e.g., the direction of a ball in Pong); stacking four frames allows the network to capture velocity and direction.

The processed input passes through three convolutional layers to exploit spatial relationships across frames, followed by fully connected layers that output the final Q-values.

The Deep Q-Learning Algorithm

Unlike standard Q-Learning, which updates state-action pairs directly, Deep Q-Learning uses a loss function to calculate the difference between the predicted Q-value and the Q-target. Gradient descent is then used to update the network weights to minimize this loss.

Training consists of two alternating phases:

  1. Sampling: The agent performs actions and stores the resulting experience tuples (state, action, reward, next state) in a replay memory.
  2. Training: A small batch of tuples is randomly sampled from the replay memory to perform a gradient descent update.

Stabilizing Training

Combining non-linear function approximators (neural networks) with bootstrapping can lead to instability. DQN implements three primary solutions to mitigate this:

1. Experience Replay

Experience Replay uses a replay buffer to store experience samples for reuse. This provides two main benefits:

  • Efficiency: The agent can learn from the same experience multiple times.
  • Decorrelation: Randomly sampling from the buffer prevents the network from only learning from the most recent sequential experiences, which avoids catastrophic forgetting and prevents action values from oscillating or diverging.

2. Fixed Q-Targets

In basic Q-learning, the target value shifts every time the weights are updated, creating a "moving target" problem that causes training oscillations. DQN solves this by using a separate target network with fixed parameters to estimate the TD Target. The parameters of the target network are updated to match the Deep Q-Network only every $C$ steps.

3. Double DQN

Double DQN addresses the overestimation of Q-values. In standard DQN, the maximum Q-value for the next state is used to calculate the target, which can lead to false positives if noisy estimates give non-optimal actions higher values. Double DQN decouples action selection from target generation:

  • The DQN network selects the best action for the next state.
  • The Target network calculates the Q-value for that specific action.

This separation reduces overestimation and leads to faster, more stable learning.

Sources