# XSQ-Learning: Adaptive Similarity Thresholds for Accelerated and Stable Q-Learning
## 2 Related Work
### Similarity-Based Approaches
Transition similarity compares the relative effects of taking an action given a state and where the environment transitions to. The Q-learning algorithm was upgraded through the integration of representational similarity between elements of the MDP's two spaces--\(S\) for states and \(A\) for actions--as proposed by [7]. They state that similarity in these sets could be measured by a norm (though noting this would not always be true or useful in every environment, as [8] remarks). These norms allow some measurement of similarity that is used to select items as \"most-likely similar\" with a threshold \(\|s^{\prime}-s_{t}\|\leq\delta_{s}\) or \(\|a^{\prime}-a_{t}\|\leq\delta_{a}\). The observed information in Q-learning (the temporal-difference error) is then integrated into these states or actions that are considered similar, as shown in Equation (1), in addition to the normal algorithm behavior. These approaches are denominated as QL-Smooth Observation and QL-Smooth Action, respectively. \[ \begin{split} Q(s^{\prime},a)=& Q(s^{\prime},a)+\\ &\alpha\left[\beta_{s}\left(r_{t}+\gamma\max_{a^{\prime}\in A(s_{ t})}Q(s_{t+1},a^{*})\right)-\beta_{s}Q(s^{\prime},a)\right]\\ \end{split}  \tag{1}\]  
\[ \begin{split} Q(s,a^{\prime})=& Q(s,a^{\prime})+\\ &\alpha\left[\beta_{a}\left(r_{t}+\gamma\max_{a^{\prime}\in A(s_{ t})}Q(s_{t+1},a^{*})\right)-\beta_{a}Q(s,a^{\prime})\right]\end{split} \]  
Meanwhile, the authors of [8] used a similarity function between states, enabling transitional similarity, denominated as SSAS, with custom similarity functions \(\sigma(s_{t},a_{t},s,a)\mapsto[0,1]\) for all \((s,a)\in S\times A\). They also modified the Q-learning algorithm by integrating this \(\sigma\) value, as shown in Equation (2), for each pair whose similarity value is above zero. This algorithm is denominated as QSLearning. \[ \begin{split} Q(s^{\prime},a^{\prime})=& Q(s^{\prime},a^{ \prime})+\\ &\alpha\sigma(s_{t},a_{t},s^{\prime},a^{\prime})\left[r_{t}+\gamma \max_{a^{\prime}\in A(s_{t})}Q(s_{t+1},a^{*})\right]\end{split}  \tag{2}\]  
Both proposals add a mechanism that uses similarity and performs extra off-policy updates for the same Q-object. QL-smooth uses a norm operation and a threshold to determine which states or actions to update additionally, with a fixed smooth rate \(\beta\). The norm measures distance and then chooses a threshold that may disconnect the concept of similarity for some environments and their state-action pairs, while QSLearning updates all pairs available in the MDP where \(\sigma>0\), meaning that any positive amount of similarity between state-action pairs is considered sufficient. This could be wasteful and destructive, as the size of \(S\times A\) could potentially be large, and allowing \(\sigma>0\) for any value to modify the Q-table with Equation (2) with any value of \(\alpha\) equates to an excessive number of updates with excessive data. Nevertheless, these methods have shown good results in their respective applications. Ref. [7] has shown significant speed-up in grid-world tasks and classic control even after a single training episode. And the authors of [8] demonstrated that their algorithm can outperform Q-learning with different designs for \(\sigma\) in their corresponding tasks. At this point, it is relevant to emphasize that the choice of a similarity function is a crucial aspect that must be carefully designed according to the problem domain. Although the effectiveness of similarity-based approaches heavily depends on this measure--since, in the worst case, a poorly chosen metric can compromise results--this characteristic is also one of their key strengths. Their flexible framework allows for an adaptation to diverse problems by leveraging existing similarity measures that naturally fit the context. In continuous spaces, kernel-based similarities or cosine similarity can be used. For discrete spaces, measures such as exact match or the Jaccard index may be suitable. In geometric problems, position-based metrics are often appropriate.