# XSQ-Learning: Adaptive Similarity Thresholds for Accelerated and Stable Q-Learning
###### Abstract  
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. reinforcement learning; similarity; fast learning; Q-learning Article  
1  
Econference Learning (RL) [1] has established itself as a fundamental paradigm for solving sequential decision-making problems through environment interaction. Among its various algorithms, Q-learning [2] stands out as a widely adopted model-free approach capable of learning optimal policies in Markov Decision Processes (MDPs). Despite its theoretical guarantees, Q-learning requires an impractical number of interactions to achieve policy convergence, particularly in large state spaces where the Q-function must be represented either as sparse tables [3] or approximated using function approximators like Deep Neural Networks [4]. This limitation becomes especially critical in real-world applications such as robotic control or adaptive systems, where each interaction carries substantial time or computational costs. These challenges are even more pronounced in complex real-world scenarios, such as multi-robot exploration of unknown environments or dynamic path planning for mobile robots. Recent studies have applied RL to these tasks, including Voronoi-based explorationstrategies [5] and hierarchical control frameworks [6]. Such advanced applications highlight the growing need for adaptive algorithms that can handle large, dynamic state spaces while ensuring reliable policy convergence. These examples reinforce the motivation for XSQ-Learning, which aims to accelerate convergence and improve stability in environments with complex dynamics. Existing similarity-based Q-learning methods, such as QL-Smooth [7] and QSLearning [8], attempt to address the inefficiency of standard Q-learning by propagating updates to similar state-action pairs. However, three fundamental limitations constrain their effectiveness. First, computational complexity becomes prohibitive as most methods require exhaustive pairwise state comparisons scaling quadratically with state space size. Second, existing approaches employ static similarity thresholds that cannot adapt to local variations in state space density. Third, methods risk policy degradation by propagating updates indiscriminately to all states with any positive similarity measure. For example, consider a grid-world environment where two disjoint regions exist: a safe region with high rewards and a hazardous region with negative rewards. In QSLearning, even small similarities between states in these regions (e.g., based on coordinate proximity) can lead to an undesired propagation of updates. This indiscriminate propagation degrades learning because the algorithm updates Q-values for states in the safe region using transitions observed in the hazardous region.