SARSA: On-Policy TD Control

We've seen how Temporal-Difference (TD) methods like TD(0) can estimate the state-value function $V_\pi$ for a given policy $\pi$ by bootstrapping. That is, they update the value estimate for a state based on the observed reward and the estimated value of the next state. This allows learning from each step, unlike Monte Carlo methods which wait until the end of an episode.

However, estimating $V_\pi$ isn't enough if our goal is control, finding an optimal policy. For control, especially when we don't have a model of the environment, we typically need to learn action-values, $Q_\pi(s, a)$. This tells us the expected return for taking action $a$ in state $s$ and then following policy $\pi$ thereafter. Knowing the $Q$-values allows the agent to select the best action in each state by simply choosing the action with the highest $Q$-value.

SARSA is a TD method designed for control. It directly estimates the action-value function $Q_\pi$. The name SARSA highlights the sequence of events involved in its update calculation: the agent starts in a State ($S_t$), chooses an Action ($A_t$), receives a Reward ($R_{t+1}$) and transitions to the next State ($S_{t+1}$), and then selects the next Action ($A_{t+1}$) according to its current policy. This quintuple $(S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1})$ forms the basis for the SARSA update.

The SARSA Update Rule

Like TD(0), SARSA performs an update after each time step. The update rule for the action-value function $Q(S_t, A_t)$ is:

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

Let's break this down:

• $Q(S_t, A_t)$ is the current estimate of the value of taking action $A_t$ in state $S_t$.
• $\alpha$ is the learning rate (a small positive number, e.g., 0.1), controlling how much we update the estimate based on the new information.
• $R_{t+1}$ is the immediate reward received after taking action $A_t$.
• $\gamma$ is the discount factor (between 0 and 1), balancing immediate versus future rewards.
• $Q(S_{t+1}, A_{t+1})$ is the estimated value of the next state-action pair. This is the bootstrapping part. Instead of waiting for the final return like in Monte Carlo, we use the current estimate of the value of the next action the agent will take according to its policy.
• $R_{t+1} + \gamma Q(S_{t+1}, A_{t+1})$ is the TD target. It represents a better estimate of $Q(S_t, A_t)$ based on the one-step experience.
• $R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t)$ is the TD error, measuring the difference between the estimated value and the TD target.

The update essentially nudges the current estimate $Q(S_t, A_t)$ towards the TD target. Notice the significant element here: the target includes $Q(S_{t+1}, A_{t+1})$, which uses the action $A_{t+1}$ actually chosen by the agent's current policy in state $S_{t+1}$.

The SARSA Control Algorithm

SARSA uses this update rule within a general control loop that aims to improve the policy over time. Since we need to learn action-values for all actions to find the best one, the policy followed must explore. A common approach is to use an $\epsilon$-greedy policy based on the current $Q$-value estimates. This means the agent usually chooses the action with the highest $Q$-value (exploits) but occasionally chooses a random action (explores) with probability $\epsilon$.

Here's the typical structure of the SARSA algorithm:

1. Initialization:

   • Initialize $Q(s, a)$ for all state-action pairs $s \in \mathcal{S}, a \in \mathcal{A}(s)$ arbitrarily (e.g., to 0 or optimistically).
   • Ensure $Q(\text{terminal\_state}, \cdot) = 0$.
   • Set learning rate $\alpha > 0$ and discount factor $\gamma \in [0, 1]$.
   • Set exploration parameter $\epsilon > 0$ for the $\epsilon$-greedy policy.

2. Episode Loop: Repeat for each episode:

   • Initialize the starting state $S$.
   • Choose the first action $A$ from state $S$ using the policy derived from $Q$ (e.g., $\epsilon$-greedy).
   • Step Loop: Repeat for each step within the episode:
     • Take action $A$. Observe the reward $R$ and the next state $S'$.
     • Choose the next action $A'$ from state $S'$ using the policy derived from $Q$ (e.g., $\epsilon$-greedy).
     • Perform the SARSA update: $$Q(S, A) \leftarrow Q(S, A) + \alpha [R + \gamma Q(S', A') - Q(S, A)]$$
     • Update the state and action for the next iteration: $S \leftarrow S'$, $A \leftarrow A'$.
   • Continue until $S$ is a terminal state.

Why is SARSA On-Policy?

SARSA is classified as an on-policy algorithm. This means it learns the value function $Q_\pi$ for the policy $\pi$ that the agent is currently following. The policy being followed includes the exploration steps (e.g., the random actions taken by $\epsilon$-greedy).

The on-policy nature comes directly from the update rule: $Q(S_{t+1}, A_{t+1})$ uses the action $A_{t+1}$ that was actually selected by the current policy in state $S_{t+1}$. The algorithm estimates the value of taking actions based on the agent's actual behavior, including its exploration strategy.

This has practical implications. If the agent uses $\epsilon$-greedy, SARSA learns the values associated with this $\epsilon$-greedy policy. The resulting $Q$-values reflect the expected return considering that the agent might take a random, suboptimal action with probability $\epsilon$. This often leads to finding "safer" paths in environments where exploration mistakes can be costly (e.g., falling off a cliff). The agent learns to account for its own potential missteps during exploration.

Contrast this with Monte Carlo control methods, which also learn based on the policy being followed, but only update after the episode ends. SARSA provides the benefit of TD learning (updating at each step) while still learning about the policy in use.

In the next section, we will explore Q-learning, a closely related TD control algorithm that takes a different approach: it learns the optimal policy directly, regardless of the exploration policy being followed. This makes Q-learning an off-policy method.