Introduction

TD(0) in the previous article learned the state value of a fixed policy $\pi$.

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

This is a prediction problem: evaluate how good each state is if the current policy continues to be followed.

Now we move to a control problem, in which the policy itself must improve. Action values are more convenient than state values when we need to decide which action to choose.

$$Q(s,a)$$

They directly store how good it is in the long run to take action $a$ in state $s$. Even without a transition model, we can compare the Q-values of the actions and choose the largest one.

The basic TD-control update has the following form.

$$Q(S_t,A_t) \leftarrow Q(S_t,A_t) + \alpha \left[ \text{TD target} - Q(S_t,A_t) \right]$$

Almost the entire difference between SARSA and Q-Learning lies inside this TD target.

• SARSA borrows the Q-value of the next action that was actually selected.
• Q-Learning borrows the largest Q-value in the next state.

Let us work through why these similar-looking equations lead to on-policy and off-policy learning.

SARSA Is Named After Five Consecutive Elements of Experience

SARSA joins the initials of the experience used in one update.

$$S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1}$$

The agent takes an action in a state, receives a reward and next state, and then its current policy actually selects the next action as well.

The SARSA target is

$$R_{t+1} + \gamma Q(S_{t+1},A_{t+1}).$$

The full update is

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

$A_{t+1}$ is not assumed to be the action with the largest Q-value. It is the action actually selected by the policy the agent is currently using—for example, an $\epsilon$-greedy policy.

If exploration chooses the action that currently appears second best, the SARSA target uses that action's Q-value.

Q-Learning Uses the Maximum Instead of the Actual Next Action

The Q-Learning target uses the largest Q-value among the actions available in the next state.

$$R_{t+1} + \gamma \max_{a'} Q(S_{t+1},a')$$

The full update is

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

The target does not depend on which action the agent actually chooses next. It looks at the greatest Q-value that would be available if the agent acted greedily from the next state.

Suppose the next state in the figure has three actions with Q-values $5$, $2$, and $1$. Exploration causes the agent to select the action with value $2$.

• Value borrowed by SARSA: $2$
• Value borrowed by Q-Learning: $5$

This single difference changes the policy each algorithm learns to evaluate.

Calculating Both Updates with the Same Numbers

Suppose the current experience and estimates are as follows.

• $Q(S_t,A_t)=4$
• $R_{t+1}=1$
• The Q-value of the actual $A_{t+1}$ is $2$.
• The maximum Q-value in the next state is $5$.
• $\gamma=0.9$
• $\alpha=0.1$

SARSA

The target is

$$1+0.9\times2=2.8.$$

It is smaller than the current Q-value of $4$, so the update gives

$$\begin{aligned} Q(S_t,A_t) &\leftarrow 4+0.1(2.8-4) \\ &= 3.88. \end{aligned}$$

Q-Learning

The target is

$$1+0.9\times5=5.5.$$

The update gives

$$\begin{aligned} Q(S_t,A_t) &\leftarrow 4+0.1(5.5-4) \\ &= 4.15. \end{aligned}$$

Both algorithms observed the same $(S_t,A_t,R_{t+1},S_{t+1})$, yet SARSA decreased the value while Q-Learning increased it. SARSA evaluated the future produced by the actual policy, including its exploratory action. Q-Learning evaluated the future under a target policy that acts greedily.

On-Policy and Off-Policy

Learning is on-policy when the policy that produces the data is also the policy being learned.

In SARSA, the current $\epsilon$-greedy policy chooses the next action, and the Q-value of that action evaluates the same policy.

$$\text{behaviour policy} = \text{target policy}$$

In off-policy learning, the policy that produces the data may differ from the policy being learned.

In Q-Learning, the behaviour policy that generates actions may be $\epsilon$-greedy, while the target assumes a greedy policy.

$$\text{behaviour: }\epsilon\text{-greedy}$$ $$\text{target: greedy}$$

Off-policy does not mean that the algorithm can learn successfully from arbitrary data. The behaviour policy must visit the necessary state-action pairs often enough, and combining off-policy learning with function approximation can make training unstable. For now, it is enough to understand that the roles of the two policies are separate in a tabular setting.

Intuition from Cliff Walking

Cliff Walking is a common example for explaining the difference between SARSA and Q-Learning.

Suppose the shortest path from a starting point to a goal runs immediately beside a cliff. Falling from the cliff produces a large negative reward and returns the agent to the start.

During training, the agent explores with $\epsilon$-greedy. Even while following the greedy path, it can occasionally choose the wrong direction.

SARSA's View

SARSA evaluates the actual policy, which will continue to behave $\epsilon$-greedily at the next step. Near the cliff, the value reflects the possibility that one exploratory action may cause a fall. A safer detour can therefore look better to the policy being used during training.

Q-Learning's View

The Q-Learning target assumes greedy behavior from the next state onward. It does not include the possibility of an exploratory mistake in its target policy. It may therefore assign a high value to the shortest path along the cliff under the greedy policy.

This example is not a universal law that SARSA is always safe and Q-Learning is always dangerous. It is an intuitive environment that shows how learning can differ depending on whether the behaviour and target policies are the same.

Why Do Both Methods Need Exploration?

Because Q-Learning uses a $\max$ in its target, it may seem that the agent can simply behave greedily. The behaviour policy that collects data still needs exploration.

Initial Q-values are inaccurate. If the agent repeatedly takes only the greedy action, it may become trapped in whichever action happened to be valued highly at the beginning. Without selecting another action, it also receives no experience with which to correct that action's Q-value.

The agent therefore usually behaves as follows.

• With high probability, select the action with the largest current Q-value.
• With a small probability $\epsilon$, try another action.

SARSA learns the Q-values of this $\epsilon$-greedy behavior itself. Q-Learning collects experience with $\epsilon$-greedy while learning a greedy target.

When and how quickly to reduce exploration is the subject of the next article.

The Target at a Terminal State

If the next state is terminal, its future value is zero.

$$Q(S_{t+1},a)=0 \qquad \text{if } S_{t+1}\text{ is terminal}$$

For the final transition, the target of both algorithms therefore contains only the immediate reward.

$$\text{Target}=R_{t+1}$$

There is no action after a terminal state, so SARSA does not select $A_{t+1}$ either.

The Flow of SARSA and Q-Learning

SARSA

1. Use the policy to choose $A_t$ in $S_t$.
2. Execute the action and observe $R_{t+1},S_{t+1}$.
3. Use the same policy to actually select $A_{t+1}$.
4. Update with $R_{t+1}+\gamma Q(S_{t+1},A_{t+1})$.
5. Move forward with $(S_t,A_t)\leftarrow(S_{t+1},A_{t+1})$.

Q-Learning

1. Use the behaviour policy to choose $A_t$ in $S_t$.
2. Execute the action and observe $R_{t+1},S_{t+1}$.
3. Update with $R_{t+1}+\gamma\max_{a'}Q(S_{t+1},a')$.
4. In the next state, choose the next action with the behaviour policy.

SARSA must select the next action before it can perform the current update. Q-Learning needs only the Q-values of the next state.

Common Points of Confusion

SARSA Can Select a Greedy Action Too

On-policy does not mean that the algorithm always uses random actions. If the current policy is $\epsilon$-greedy, it selects the greedy action most of the time. But when exploration selects a different action, SARSA also reflects that actual action in its target.

Q-Learning's Behaviour Need Not Be Greedy

Its target is greedy, but experience can be collected by another policy such as $\epsilon$-greedy.

The Maximum Does Not Execute an Action

The $\max$ in the Q-Learning update merely reads the largest number to calculate the target. It does not mean that the agent actually executed the corresponding action.

Both Methods Bootstrap from a Value Estimate

Neither algorithm waits for the actual return through the end of an episode. Both borrow a Q estimate from the next state. They differ in which next action supplies that Q-value.

What to Remember

The central idea of this article is

SARSA learns the future of the policy that actually behaves, while Q-Learning learns the future of a greedy policy independently of the policy that generated the experience.

More specifically:

1. The SARSA target is $R_{t+1}+\gamma Q(S_{t+1},A_{t+1})$.
2. The Q-Learning target is $R_{t+1}+\gamma\max_{a'}Q(S_{t+1},a')$.
3. SARSA is on-policy, and Q-Learning is off-policy.
4. The action selected by $\max$ in Q-Learning need not be the action actually executed.
5. Both methods need exploration to collect sufficient experience.

The next article considers exploration as a problem in its own right. Using the multi-armed bandit, we will see why a greedy policy can become trapped in a bad choice and how $\epsilon$-greedy and UCB decide which new action to try.

References

• David Silver, Lecture 5: Model-Free Control
• Seoul National University DSBA Lab, Introduction of Reinforcement Learning
• Sutton & Barto, Reinforcement Learning: An Introduction, 2nd Edition