Experience Replay

The replay buffer is the core data structure of experience replay, typically implemented as a fixed-size circular buffer (FIFO queue). It stores individual transitions in the form of tuples: (state, action, reward, next_state, done_flag). This design decouples the data generation process (acting in the environment) from the learning process (updating the neural network). Key characteristics include:

• Capacity: A large buffer (e.g., 1 million transitions) provides a diverse sample but increases memory usage.
• Uniform Sampling: Early algorithms sampled uniformly at random, providing independent, identically distributed (I.I.D.) data.
• Overwriting Policy: When full, the oldest experiences are overwritten, ensuring the buffer contains recent interactions.

The primary technical benefit of experience replay is decorrelating sequential experiences. In on-policy RL (e.g., standard Q-learning), updates are made using consecutive states, which are highly correlated. This leads to several problems:

• High-Variance Updates: Correlated samples cause the gradient updates to have high variance, destabilizing training.
• Catastrophic Forgetting: The network can overfit to recent trajectories and forget earlier, useful behaviors.
• Inefficient Data Use: Each experience is used only once for a single update.

By randomly sampling mini-batches from the replay buffer, experience replay creates a dataset where each sample is statistically independent, mimicking the I.I.D. assumption central to most supervised learning. This stabilizes convergence and allows the agent to learn from rare but important events multiple times.

Prioritized Experience Replay is a sophisticated enhancement that samples transitions not uniformly, but based on their temporal-difference (TD) error. The intuition is that transitions with a higher TD error (a larger mismatch between predicted and target Q-values) offer more learning potential. Key mechanisms include:

• Sampling Probability: P(i) = (p_i^α) / Σ_k p_k^α, where p_i is the priority of transition i (often |TD error| + ε).
• Importance Sampling (IS) Weights: To correct the bias introduced by non-uniform sampling, updates are weighted by w_i = (1/N * 1/P(i))^β. This ensures the convergence properties of stochastic gradient descent are maintained.
• α and β Hyperparameters: α controls the prioritization strength (0 = uniform, 1 = full priority). β anneals the IS correction over time. PER dramatically improves sample efficiency in complex environments like Atari games and robotic control.

Experience replay was popularized by Deep Q-Networks (DQN). The canonical DQN algorithm integrates the replay buffer into its training loop:

1. Act: The agent selects an action using an ε-greedy policy based on the online Q-network.
2. Store: The resulting transition (s, a, r, s', done) is stored in the replay buffer D.
3. Sample: A mini-batch of transitions is sampled randomly from D.
4. Compute Target: For each transition, the target Q-value is computed: y = r + γ * max_a' Q_target(s', a') * (1 - done).
5. Update: Perform a gradient descent step on the loss (y - Q_online(s, a))^2.
6. Synchronize: Periodically copy weights from the online network to the target network. This decoupling allows DQN to learn stable value functions from high-dimensional visual inputs, a landmark achievement in deep RL.

Experience replay can be extended to store and sample sequences of transitions to enable multi-step learning. Instead of single-step transitions (s_t, a_t, r_t, s_{t+1}), the buffer stores (s_t, a_t, R_t, s_{t+n}), where R_t is the n-step return: R_t = r_t + γ r_{t+1} + γ^2 r_{t+2} + ... + γ^{n-1} r_{t+n-1}

Benefits:

• Lower Bias: Multi-step returns provide a less biased estimate of the true return compared to single-step bootstrapping, especially early in training.
• Faster Reward Propagation: Rewards are propagated back to relevant states more quickly.

Trade-offs:

• Higher Variance: Longer sequences increase the variance of the target.
• Implementation Complexity: Requires storing sequences and handling terminal states within the sequence. Algorithms like Rainbow DQN integrate n-step returns with prioritized replay for state-of-the-art performance.

While powerful, experience replay introduces several engineering and algorithmic challenges:

• Memory vs. Performance Trade-off: Large buffers (1M+ transitions) are standard but require significant RAM. Using compressed representations or storing experiences on disk with caching is an active area of optimization.
• Non-Stationary Data Distribution: The policy generating data (the behavior policy) improves over time, meaning the buffer contains a mixture of old (poor) and new (good) policies. This can lead to extrapolation error if the Q-network is asked to evaluate actions not represented in the buffer.
• Hyperparameter Sensitivity: Buffer size, mini-batch size, and prioritization parameters (α, β) require careful tuning.
• Off-Policy vs. On-Policy Algorithms: Experience replay is inherently off-policy (learning from old data). It cannot be naively applied to strictly on-policy algorithms like A2C or PPO without modifications (e.g., using a short buffer or importance sampling). Techniques like V-trace or Retrace are used to correct for policy mismatch in actor-critic methods.