Tabular Solution Methods: Q-Learning and SARSA

Model-free methods in reinforcement learning focus on algorithms that learn value functions directly from experience, without needing a predefined model of the environment's dynamics (transitions and rewards). These methods operate within the framework of Markov Decision Processes (MDPs) and their associated value functions. Among the most foundational are Q-Learning and SARSA, both belonging to the family of Temporal Difference (TD) learning algorithms. They update value estimates based on other learned estimates, bootstrapping from the current value function. These methods operate effectively when the state and action spaces are small enough to be represented in a table, hence the term 'tabular methods'.

Q-Learning: Learning the Optimal Value Function Off-Policy

Q-Learning is a popular off-policy TD control algorithm. Its goal is to directly learn the optimal action-value function, $Q^*(s, a)$, which represents the expected return starting from state $s$, taking action $a$, and thereafter following the optimal policy $\pi^*$. Being "off-policy" means that Q-learning learns the optimal value function even if the actions taken during learning are determined by a different, potentially exploratory policy (like epsilon-greedy).

The agent interacts with the environment, observing transitions $(S_t, A_t, R_{t+1}, S_{t+1})$. After each transition, it updates its estimate of $Q(S_t, A_t)$ using the following rule:

$$Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha [R_{t+1} + \gamma \max_{a'} Q(S_{t+1}, a') - Q(S_t, A_t)]$$

Let's break down this update:

• $Q(S_t, A_t)$: The current estimated value of taking action $A_t$ in state $S_t$.
• $\alpha$: The learning rate (a small value, e.g., 0.1), controlling how much the new information overrides the old estimate.
• $R_{t+1}$: The reward received after taking action $A_t$.
• $\gamma$: The discount factor (between 0 and 1), balancing immediate vs. future rewards.
• $\max_{a'} Q(S_{t+1}, a')$: The main part for Q-learning. This is the estimate of the optimal future value achievable from the next state $S_{t+1}$. It looks at the Q-values for all possible next actions $a'$ in state $S_{t+1}$ and picks the maximum. This greedy choice regarding the next action is what makes Q-learning directly approximate the optimal $Q^*$.

The term $R_{t+1} + \gamma \max_{a'} Q(S_{t+1}, a')$ is called the TD target. The difference between the TD target and the current estimate $Q(S_t, A_t)$ is the TD error, which drives the learning update.

To ensure sufficient exploration, Q-learning is often paired with a policy like epsilon-greedy, where the agent chooses a random action with probability $\epsilon$ and the action with the highest current Q-value ($argmax_a Q(S_t, a)$) with probability $1-\epsilon$. Importantly, the update rule uses the max operator, learning about the greedy (optimal) action, even if an exploratory action was actually taken.

Diagram illustrating the flow of information for a single Q-learning update step.

SARSA: Learning the Value Function On-Policy

SARSA (State-Action-Reward-State-Action) is an alternative TD control algorithm that is on-policy. Unlike Q-learning, SARSA learns the action-value function $Q(s, a)$ corresponding to the current policy being followed, including its exploration behavior.

The update process requires knowing the next action $A_{t+1}$ that the current policy chooses in the next state $S_{t+1}$. The quintuple $(S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1})$ gives the algorithm its name. The update rule is:

$$Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha [R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t)]$$

Notice the main difference from Q-learning: instead of taking the maximum Q-value over all possible next actions ($\max_{a'} Q(S_{t+1}, a')$), SARSA uses the Q-value of the specific next action $A_{t+1}$ that the agent actually will take according to its current policy (e.g., the action chosen by the epsilon-greedy strategy for state $S_{t+1}$).

This makes SARSA sensitive to the policy being executed. If the policy is exploratory (high $\epsilon$), SARSA will learn Q-values that account for the possibility of taking suboptimal exploratory actions. This can lead to a more "conservative" agent during learning compared to Q-learning, which always assumes the optimal action will be taken in the next step for its update target.

Diagram illustrating the flow of information for a single SARSA update step, requiring the next action $A_{t+1}$.

Q-Learning vs. SARSA: A Quick Comparison

• Policy Type: Q-learning is off-policy; SARSA is on-policy.
• Update Target: Q-learning uses the max Q-value of the next state ($\max_{a'} Q(S', a')$), aiming directly for the optimal value. SARSA uses the Q-value of the actual next action taken ($Q(S', A')$), evaluating the current policy.
• Behavior: Q-learning can learn the optimal policy even while exploring suboptimally. SARSA's learned values reflect the exploration strategy; it might learn a safer path if exploration sometimes leads to negative consequences (like falling off a cliff in a grid), whereas Q-learning might learn values assuming it can avoid the cliff, even if the exploration policy sometimes fails.

Both Q-learning and SARSA form the foundation of many advanced RL techniques. They work by iteratively updating value estimates stored in a table, indexed by state-action pairs. However, their reliance on this explicit table becomes a major bottleneck when dealing with problems where the number of states or actions is very large or infinite (e.g., continuous spaces), which is the topic of the next section.