Deep Q-Network (DQN)

A replay buffer stores the agent's experiences (state, action, reward, next state) as they interact with the environment. During training, mini-batches are sampled randomly from this buffer.

• Breaks Temporal Correlations: Random sampling decorrelates sequential experiences, which is crucial for stable learning with neural networks.
• Improves Data Efficiency: Each experience can be used for multiple weight updates.
• Mitigates Catastrophic Forgetting: By repeatedly revisiting past experiences, the network retains knowledge of earlier states.

This technique transforms the inherently non-stationary, correlated data stream of online RL into an independent and identically distributed (IID) dataset suitable for supervised deep learning.

DQN uses a separate, periodically updated target network to calculate the Q-learning update target. This network is a copy of the main online Q-network.

• Stabilizes Training: The update target r + γ * max_a' Q_target(s', a') becomes fixed for a period, preventing a moving target problem where the network chases its own rapidly changing predictions.
• Update Mechanism: The target network's weights are either:
  • Hard Update: Copied from the online network every C steps (original DQN).
  • Soft Update: Slowly blended with the online network's weights using a parameter τ (e.g., θ_target = τ*θ_online + (1-τ)*θ_target).

This decoupling is critical for converging to a stable Q-function approximation.

To handle partially observable environments (like Atari games where a single frame doesn't show velocity), DQN's input is not a single image but a stack of the last k consecutive frames (typically k=4).

• Provides Temporal Information: The stack allows the convolutional neural network to infer motion and direction from the sequence of pixels.
• Transforms POMDP to MDP: This technique effectively converts a Partially Observable Markov Decision Process (POMDP) into a Markov Decision Process (MDP) where the state is the frame stack, which is often sufficient for decision-making.

Each frame is also preprocessed (e.g., grayscaled, downsampled, and cropped) to reduce input dimensionality.

DQN clips all environment rewards to be within [-1, +1] or [0, 1]. This is a simple but effective reward scaling technique.

• Normalizes Error Scales: It prevents large reward magnitudes in certain games from dominating the gradient updates and causing instability.
• Simplifies Learning Across Games: It allows the same learning rate and network architecture to be used across diverse environments with vastly different reward scales (e.g., Pong vs. Boxing).

While effective, it's a lossy transformation that discards information about relative reward magnitudes within a game. Later algorithms often use more advanced reward normalization techniques.

DQN uses a deep convolutional neural network (CNN) to approximate the Q-function directly from raw pixel inputs.

• Spatial Feature Extraction: The CNN layers automatically learn hierarchical features (edges, shapes, objects) relevant for decision-making.
• Architecture (NIPS 2013):
  • Input: 84x84x4 (stack of 4 grayscale frames).
  • Conv1: 16 filters of 8x8, stride 4, ReLU.
  • Conv2: 32 filters of 4x4, stride 2, ReLU.
  • Fully Connected: 256 units, ReLU.
  • Output: Linear layer with one unit per valid action (Q-value).

This end-to-end architecture eliminated the need for hand-crafted feature engineering, enabling learning directly from pixels.

DQN is trained by minimizing the mean-squared error between the current Q-value prediction and the Q-learning target, treating it as a regression problem.

• Loss Function: L(θ) = E[(r + γ * max_a' Q_target(s', a'; θ⁻) - Q(s, a; θ))²]
• Optimizer: Uses RMSProp or Adam with gradient clipping.
• Key Insight: The Q-learning update is framed as minimizing a sequence of temporal difference (TD) errors. The use of a target network and experience replay makes this loss function stable enough for stochastic gradient descent.

This approach successfully combined the Bellman optimality equation from dynamic programming with the scalable function approximation of deep learning.

Q-Learning is the foundational, model-free, off-policy reinforcement learning algorithm upon which DQN is built. It learns an action-value function, Q(s, a), representing the expected cumulative reward of taking action a in state s and following the optimal policy thereafter. Its core update rule is based on the Bellman optimality equation: Q(s,a) ← Q(s,a) + α [r + γ max_a' Q(s',a') - Q(s,a)]. DQN's primary innovation was using a deep neural network to approximate this Q-function for high-dimensional state spaces where traditional tabular methods fail.

Experience Replay is a critical stabilization technique introduced with DQN. The agent stores its experiences (state, action, reward, next state, done) in a finite replay buffer. During training, it samples mini-batches of experiences randomly from this buffer. This provides two key benefits:

• Breaks temporal correlations between sequential experiences, which can lead to unstable training.
• Increases data efficiency by allowing the same experience to be learned from multiple times. Without experience replay, learning from correlated sequential frames (like video) is highly unstable.

A Target Network is a second neural network, identical in architecture to the main Q-network, used to generate stable temporal difference (TD) targets during training. The main network's parameters are copied to the target network only periodically (e.g., every C steps). The TD target in the loss function becomes: r + γ max_a' Q_target(s', a'). Using a slowly updating target network prevents a moving target problem, where the Q-values the network is trying to converge toward are constantly shifting, which is a major source of divergence in naive deep RL.

Policy Gradient Methods represent the other major branch of deep RL, contrasting with DQN's value-based approach. Instead of learning a value function and deriving a policy implicitly (e.g., argmax over Q-values), policy gradient algorithms directly parameterize and optimize the policy π(a|s) itself. Key algorithms include REINFORCE, Proximal Policy Optimization (PPO), and Soft Actor-Critic (SAC). While DQN is effective for discrete action spaces, policy gradient methods naturally handle continuous action spaces and can offer better convergence properties in many complex environments.

Model-Based Reinforcement Learning is an approach where the agent learns an explicit model of the environment's dynamics—the transition function P(s'|s,a) and reward function R(s,a). This model can then be used for planning (e.g., via Monte Carlo Tree Search) to choose actions. This contrasts with model-free methods like DQN, which learn a policy or value function directly from experience without a world model. Model-based methods are often more sample-efficient but can suffer from model bias—errors in the learned model that compound during planning.

Double DQN (DDQN) is a direct enhancement to the original DQN algorithm designed to address overestimation bias. In standard DQN, the same network selects and evaluates the action for the next state (max_a' Q(s', a')), which systematically overestimates Q-values. DDQN decouples this by:

• Using the online network to select the best action for the next state: a* = argmax_a' Q_online(s', a').
• Using the target network to evaluate the Q-value of that action: Q_target(s', a*). This simple modification leads to more stable learning and often better final policies.