XSQ-Learning: Adaptive Similarity Thresholds for Accelerated and Stable Q-Learning

Reinforcement Learning (RL) enables agents to learn optimal policies through environment interaction, with Q-learning being a fundamental algorithm for Markov Decision Processes (MDPs). However, Q-learning suffers from slow convergence due to its exhaustive exploration requirements, particularly in large state spaces where Q-value estimation becomes computationally expensive, whether using tabular methods or Deep Neural Networks (DNNs). To address this limitation, we propose XSQ-Learning, a novel algorithm that accelerates convergence by leveraging similarities between state–action pairs to generalize Q-value updates intelligently. XSQ-Learning introduces two key innovations: (1) an adaptive update mechanism that propagates temporal-difference errors to similar states proportionally to their similarity, and (2) a similarity-aware control strategy that regulates which updates are propagated and to what extent. Our experiments demonstrate that XSQ-Learning can reduce the required iterations by 36.83% compared to standard Q-learning and by 24.43% versus state-of-the-art similarity-based methods, while maintaining policy stability. These results show that similarity-based value propagation can significantly enhance RL efficiency without compromising learning reliability.