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 transition 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 skew 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.
Introduction
In Deep Q-learning (DQN), the experience replay buffer is a cornerstone for breaking correlations between consecutive samples and improving data efficiency. However, standard uniform sampling assumes that all transitions in the buffer are equally valuable. In practice, the distribution of states is often highly skewed. As agents frequently restart from initial states or get stuck in specific regions of the state space, these "common" states dominate the buffer.
As shown in the figure above, a small fraction of clusters (the top 20%) can account for up to 93% of the transitions in games like Atlantis. Uniform sampling thus leads to redundant updates for well-explored states while neglecting rare, high-uncertainty transitions, hindering overall convergence speed.
State Distribution-aware Sampling (SDAS)
To address this imbalance, we propose State Distribution-aware Sampling (SDAS). The core idea is to group similar states into clusters and balance the sampling probability across these clusters to target "knowledge gaps" in the agent's experience.
Efficient Clustering with SimHash
Clustering high-dimensional raw inputs like Atari frames is computationally prohibitive in real-time. SDAS utilizes SimHash, a locality-sensitive hashing (LSH) technique, to map similar states to the same hash code efficiently. For complex environments, we extract features from the 3rd convolutional layer of the DQN to ensure clusters represent semantically meaningful state features rather than raw pixel noise.
Sampling Strategy
We define the sampling probability $p_i$ for a transition $i$ as a weighted interpolation between uniform sampling and cluster-balanced sampling:
$$p_i = \beta \cdot \frac{1}{n} + (1 - \beta) \cdot \frac{1}{k \cdot num_i}$$
Where $n$ is the total transitions, $k$ is the number of clusters, $num_i$ is the count of transitions in the cluster containing transition $i$, and $\beta$ is a hyperparameter controlling the balance. When $\beta=0$, every cluster is sampled with equal total probability, effectively boosting the importance of rare states.
Experimental Results
We evaluated SDAS on OpenAI Gym benchmarks, including classic control tasks (Acrobot, MountainCar) and Atari 2600 games (BattleZone, Atlantis, Amidar).
- Faster Convergence: In BattleZone, SDAS achieved convergence in approximately 5,000 episodes, compared to 10,000 episodes for the baseline DQN—a 2x speedup.
- Higher Performance: SDAS consistently reached higher final scores. In Atlantis, the agent achieved an average reward of 1345, an 18.5% improvement over standard DQN.
- Sample Efficiency: Experiments on classic control tasks demonstrated that SDAS with a buffer only 20% of the standard size could still outperform a baseline DQN with a full-sized buffer.
Conclusion
SDAS provides a computationally efficient way to mitigate the negative effects of skewed state distributions in experience replay. By prioritizing rare states with higher uncertainty, it accelerates learning and improves final agent performance. Future work will investigate the synergy between SDAS and Prioritized Experience Replay (PER) based on TD-error.
Summary updated