# XSQ-Learning: Adaptive Similarity Thresholds for Accelerated and Stable Q-Learning
## 2 Related Work  
### Q-Learning Algorithm  
Q-learning, introduced in [2], is a foundational algorithm in RL. It enables agents to learn optimal action-selection policies within Markov Decision Processes (MDPs) without requiring an environment model.  
In an MDP, the agent interacts with an environment composed of states, actions, transition probabilities, and rewards. At each timestep, the agent observes the current state, selects an action, and transitions to a new state according to the environment dynamics. The agent receives a reward based on this transition and aims to learn a policy that maximizes cumulative rewards over time.  
An MDP is formally defined by a tuple \((S,A,T,R,\gamma)\), where  
* \(S\) is the set of states, with \(s\in S\) representing a particular state;
* \(A\) is the set of actions, with \(a\in A\) representing a particular action;
* \(T(s,a,s^{\prime})\) is the transition probability function, which gives the probability of transitioning from state \(s\) to state \(s^{\prime}\) after taking action \(a\);
* \(R(s,a,s^{\prime})\) is the reward function, which gives the immediate reward obtained after transitioning from state \(s\) to state \(s^{\prime}\) due to taking action \(a\);
* \(\gamma\) is the discount factor, which determines the importance of future rewards relative to immediate rewards--it is a value between 0 and 1.  
The objective in an MDP is typically to find a policy \(\pi\), which is a mapping from states to actions, that maximizes the expected cumulative reward over time. This is often formulated as finding the policy that maximizes the expected value of the sum of discounted rewards:  
\[V^{\pi}(s)=\sum_{t=0}^{\infty}\gamma^{t}\mathbb{E}[R_{t+1}|s_{t}=s,\pi]\]  
where \(V^{\pi}(s)\) is the value function, representing the expected cumulative reward starting from state \(s\) and following policy \(\pi\), and \(\mathbb{E}[R_{t+1}|s_{t}=s,\pi]\) is the expected immediate reward obtained after taking action \(a\) in state \(s\) and following policy \(\pi\).  
The optimal value function \(V^{*}(s)\) represents the maximum expected cumulative reward achievable from each state, and the optimal policy \(\pi^{*}(s)\) is the policy that achieves this maximum expected cumulative reward.  
Q-learning maintains an estimate of the value of taking action \(a\) in state \(s\), denoted as \(Q(s,a)\), which represents the expected cumulative reward the agent will receive if it starts in state \(s\), takes action \(a\), and follows an optimal policy thereafter.  
The Q-learning algorithm iteratively updates the Q-values based on the Bellman equation:  
\[Q(s,a)\gets Q(s,a)+\alpha\bigg{[}R(s,a)+\gamma\max_{a^{\prime}}Q(s^{ \prime},a^{\prime})-Q(s,a)\bigg{]}\]  
where \(\alpha\) is the learning rate, controlling the extent to which new information overrides old information, and \(s^{\prime}\) is the state reached after taking action \(a\) in state \(s\).  
The agent interacts with the environment by selecting actions according to an exploration-exploitation strategy, such as \(\epsilon\)-greedy or softmax, to balance between exploring new actions and exploiting the current best-known actions. Over time, as the agent interacts with the environment and receives feedback, Q-learning updates its Q-values to converge toward the optimal action-selection policy, maximizing the cumulative rewards obtained over the agent's lifetime.