State Distribution-Aware Sampling for Deep Q-Learning

Weichao Li, Fuxian Huang, Xi Li, Gang Pan, Fei Wu

TL;DR

This paper introduces State Distribution-aware Sampling (SDAS), a novel method for experience replay in Deep Q-learning. By clustering states and balancing sampling probabilities, the authors reduce redundant updates for frequent states and prioritize learning for rare, high-uncertainty states, leading to significantly faster convergence and higher final scores.

What Problem Does This Paper Address?

In Deep Q-learning (DQN), agents store their experiences (state, action, reward, next state) in a "replay buffer." Traditionally, these experiences are sampled uniformly to train the neural network.

However, the authors point out a major flaw: the distribution of states in the buffer is usually highly skewed. Because agents often fail and restart from an initial position, states near the beginning of a task appear much more frequently than states near the goal. Uniform sampling effectively becomes "frequency-based sampling," where the network wastes time performing redundant updates on well-known states while neglecting rare states. This imbalance leads to high uncertainty in the value estimates of rare states and slows down the overall learning process.

Methods

The authors propose a sampling strategy that interpolates between uniform sampling and a "balanced" approach that treats every part of the state space equally.

  1. Efficient Clustering with SimHash: To understand the state distribution, the agent must group similar states together. Since raw state data (like Atari pixels) is high-dimensional, the authors use SimHash, a locality-sensitive hashing (LSH) technique. This maps similar states to the same hash code (cluster) efficiently without the heavy computational cost of algorithms like K-means.
  2. Feature Extraction: For complex tasks like Atari, they use the output of the 3rd convolutional layer of the DQN itself as the feature vector for clustering, ensuring the clusters are based on semantically meaningful information.
  3. Distribution-aware Sampling Formula: They calculate the sampling probability $p_i$ for a transition $i$ using a balance parameter $\beta$: $$p_i = \beta \cdot \frac{1}{n} + (1 - \beta) \cdot \frac{1}{k \cdot num_i}$$
    • $n$: Total transitions in the buffer.
  4. $k$: Number of clusters.
  5. $num_i$: Number of transitions in the cluster containing transition $i$.
  6. $\beta$: A hyperparameter. When $\beta=1$, it’s uniform sampling; when $\beta=0$, every cluster is sampled with equal total probability regardless of its size.

Datasets

The method was evaluated using the OpenAI Gym platform on two categories of benchmarks:

  • Classic Control Tasks: Acrobot, MountainCar, and LunarLander.
  • Atari 2600 Games: BattleZone, Atlantis, and Amidar (via the Arcade Learning Environment).

Key Insights and Ideas

  • Uniform is not "Fair": The "aha moment" here is realizing that uniform sampling is actually biased toward the agent's most common mistakes or starting positions.
  • Uncertainty vs. Frequency: There is an inverse relationship between how often a state is updated and how much uncertainty remains in its Q-value. By artificially boosting the sampling rate of rare clusters, the algorithm targets the "knowledge gaps" in the agent's experience.
  • Computational Efficiency: By using SimHash and existing CNN features, the authors provide a way to perform state-space clustering in real-time during training, which is usually a bottleneck in RL.

Key Results

The proposed SDAS method consistently outperformed the baseline DQN across all tests:

  • Faster Convergence: In the game BattleZone, the SDAS approach began to converge at roughly 5,000 episodes, whereas the baseline DQN required 10,000 episodes—a 2x speedup.
  • Higher Performance: In Atlantis, the agent achieved an average total reward of 1345, roughly 18.5% higher than the baseline.
  • Robustness to Buffer Size: In classic control tasks, the authors showed that their method with a small buffer (20% of standard size) could still outperform a baseline DQN using a full-sized buffer.

Limitations and Future Work

  • Hyperparameter Sensitivity: The paper introduces $\beta$ and the number of clusters $k$ as hyperparameters. While they provide values used in experiments (e.g., $k=128$ for Atari), the optimal balance might vary significantly between different environments.
  • Comparison to PER: While the paper mentions Prioritized Experience Replay (PER)—which samples based on TD-error—it primarily benchmarks against standard uniform DQN. A deeper exploration of how state distribution-aware sampling interacts with or complements TD-error-based priority would be a valuable next step.
  • Static Hashing: The use of a static hash might not perfectly capture the evolving representation of the state space as the CNN learns, suggesting a potential move toward dynamic or learned hashing.

Summary updated

Abstract

A critical and challenging problem in reinforcement learning is how to learn the state-action value function from the experience replay buffer and simultaneously keep sample efficiency and faster convergence to a high quality solution. In prior works, transitions are uniformly sampled at random from the replay buffer or sampled based on their priority measured by temporal-difference (TD) error. However, these approaches do not fully take into consideration the intrinsic characteristics of transitions distribution in the state space and could result in redundant and unnecessary TD updates, slowing down the convergence of the learning procedure. To overcome this problem, we propose a novel state distribution-aware sampling method to balance the replay times for transitions with imbalanced distribution, which takes into account both the occurrence frequencies of transitions and the uncertainty of state-action values. Consequently, our approach could reduce the unnecessary TD updates and increase the TD updates for state-action value with more uncertainty, making the experience replay more effective and efficient. Extensive experiments are conducted on both classic control tasks and Atari 2600 games based on OpenAI gym platform and the experimental results demonstrate the effectiveness of our approach in comparison with the standard DQN approach.
BibTeX
@inproceedings{li2019state,
  author = {Weichao Li and Fuxian Huang and Xi Li and Gang Pan and Fei Wu},
  title = {{State Distribution-Aware Sampling for Deep Q-Learning}},
  booktitle = {Neural Process. Lett},
  year = {2019},
  url = {https://openreview.net/forum?id=nLre5ihjfE3},
}

Loading related content...

Figure