Comparing SARSA and Q-Learning

A direct comparison of the SARSA and Q-learning algorithms is valuable. Both are fundamental Temporal-Difference (TD) control methods designed to learn optimal behavior by estimating action-value functions ($Q$-values). They share the core TD idea of bootstrapping – updating estimates based on other learned estimates. However, their update rules and learning philosophies differ significantly, primarily stemming from SARSA being an on-policy algorithm and Q-learning being an off-policy algorithm.

Update Rule Differences

The core distinction lies in how each algorithm calculates the target value used in the update. Let's revisit their update rules for a transition from state $S_t$ to $S_{t+1}$ after taking action $A_t$ and receiving reward $R_{t+1}$.

SARSA Update: SARSA stands for State-Action-Reward-State-Action. This name reflects its update rule, which uses the actual action $A_{t+1}$ taken in state $S_{t+1}$ according to the current policy $\pi$.

$$Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha [ \underbrace{R_{t+1} + \gamma Q(S_{t+1}, A_{t+1})}_{\text{TD Target (uses actual next action } A_{t+1})} - Q(S_t, A_t) ]$$

The target value, $R_{t+1} + \gamma Q(S_{t+1}, A_{t+1})$, depends on the next state $S_{t+1}$ and the next action $A_{t+1}$ chosen by the current policy (often an $\epsilon$-greedy policy during learning). SARSA learns the value of taking action $A_t$ in state $S_t$ and then following the current policy thereafter.

Q-Learning Update: Q-learning, on the other hand, uses the maximum possible Q-value in the next state $S_{t+1}$ to form its target, irrespective of the action actually taken next.

$$Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha [ \underbrace{R_{t+1} + \gamma \max_{a} Q(S_{t+1}, a)}_{\text{TD Target (uses maximum Q-value over next actions)}} - Q(S_t, A_t) ]$$

The target value, $R_{t+1} + \gamma \max_{a} Q(S_{t+1}, a)$, represents the reward received plus the discounted value of the best action possible from state $S_{t+1}$, according to the current Q-value estimates. Q-learning learns the value of taking action $A_t$ in state $S_t$ and then acting optimally (greedily) thereafter, even if the agent's actual next action $A_{t+1}$ (chosen via $\epsilon$-greedy exploration, for instance) was different.

On-Policy vs. Off-Policy Learning

This difference in update targets directly relates to the on-policy/off-policy distinction:

• SARSA (On-Policy): Learns the value function $Q^\pi$ for the policy $\pi$ the agent is currently following. If the agent explores using an $\epsilon$-greedy strategy, SARSA learns the value of acting $\epsilon$-greedily. The behavior policy (used to select actions like $A_{t+1}$) and the target policy (the policy being learned about) are the same.
• Q-Learning (Off-Policy): Learns the value function $Q^*$ for the optimal greedy policy, regardless of the policy the agent is currently following to explore the environment. The behavior policy (e.g., $\epsilon$-greedy) can be different from the target policy (which is always the greedy policy implied by $\max_a Q(S_{t+1}, a)$).

Behavioral Consequences

The difference between learning the value of the exploration policy (SARSA) versus the optimal policy (Q-learning) can lead to different learned behaviors, especially in environments where exploration can be risky.

Consider a scenario like the "Cliff Walking" problem often used in RL literature. The agent needs to find the shortest path from a start to a goal state, but a region of the grid ('the cliff') yields a large negative reward if entered.

Path difference in a Cliff Walking environment. SARSA tends to learn a safer, possibly longer path away from the cliff because it accounts for the negative consequences of suboptimal exploratory actions near the edge. Q-learning learns the shortest path, assuming optimal actions will ultimately be taken, ignoring the risks inherent in the exploration strategy used during learning.

Because SARSA includes the actually chosen action $A_{t+1}$ (which might be a random exploratory move) in its update, it learns Q-values that are lower for state-action pairs near the cliff. This encourages a policy that steers clear of the danger zone. Q-learning, by using the $\max$ operator, learns that the optimal path is right along the edge of the cliff, assuming that the agent won't make an exploratory mistake when it matters. It's more optimistic about future actions.

Convergence

• Q-Learning: Converges to the optimal action-value function $Q^*$ under standard stochastic approximation conditions, provided all state-action pairs continue to be visited. Its convergence is independent of the policy being followed.
• SARSA: Converges to the action-value function $Q^\pi$ for the specific policy $\pi$ being followed (e.g., $\epsilon$-greedy). If $\epsilon$ is gradually decreased towards zero, SARSA will also converge towards $Q^*$.

Summary Table

Feature	SARSA	Q-Learning
Type	On-Policy TD Control	Off-Policy TD Control
Update Rule	Uses $(S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1})$	Uses $(S_t, A_t, R_{t+1}, S_{t+1})$ and $\max Q$
Target Value	$R_{t+1} + \gamma Q(S_{t+1}, A_{t+1})$	$R_{t+1} + \gamma \max_{a} Q(S_{t+1}, a)$
Learns About	Value of the behavior policy (incl. exploration)	Value of the optimal (greedy) policy
Behavior	Can be more conservative, avoids risky exploration	Can be more aggressive, learns optimal path directly
Convergence	To $Q^\pi$ (for policy $\pi$)	To $Q^*$ (optimal values)

Choosing between SARSA and Q-learning depends on the specific application. If you need to evaluate or guarantee performance under a specific exploration strategy, or if safety during learning is a major concern (avoiding catastrophic exploratory moves), SARSA might be preferred. If the primary goal is to find the optimal policy as efficiently as possible, and performance during the learning phase is secondary, Q-learning is often the more direct approach and forms the basis for many advanced deep RL algorithms.