Model-Free Control: SARSA and Q-Learning

Hello! Welcome to the fifth lesson in our module on Reinforcement Learning Foundations.

In our last lesson, we explored how to evaluate a given policy without a model of the environment, using Monte Carlo (MC) and Temporal Difference (TD) prediction. We learned to estimate the state-value function, $V^{\pi }(s)$, purely from experience. But evaluation is only half the battle. Our ultimate goal is to find the best policy.

Today, we make the crucial leap from prediction to control. We'll learn how to not just evaluate, but to actively improve our policy and find the optimal way to act. This lesson directly addresses the learning outcome: Implement model-free control algorithms: SARSA and Q-Learning. These two algorithms are foundational to reinforcement learning and serve as the perfect entry point into the critical concepts of on-policy and off-policy learning.

1. From Prediction to Control: The Action-Value Function

In our previous model-based lessons (Value and Policy Iteration), we could improve a policy by looking one step ahead. With a state-value function $V(s)$, we'd check all actions, see where they lead using the model $p(s^{\prime },r|s,a)$, and pick the action leading to the best outcome.

In a model-free setting, this is impossible. We don't have the transition probabilities $p(s^{\prime },r|s,a)$. So, how do we choose the best action?

The answer is to shift from learning state values to learning action-values. We introduce the action-value function, $Q^{\pi }(s,a)$, which represents the expected return from starting in state $s$, taking action $a$, and then following policy $\pi$ thereafter.

If we have the optimal action-value function, $Q^{\ast }(s,a)$, finding the optimal policy becomes trivial—no model needed! We simply act greedily at each state:
${\pi }^{\ast }(s)=\arg {\max }_{a\in A(s)}{Q}^{\ast }(s,a)$
Our goal is now to estimate $Q^{\ast }(s,a)$ using the TD learning principles from our last lesson.

To set the stage, let's first get a clear understanding of this "quality" function and why model-free methods are necessary.

2. Q-Learning: Off-Policy TD Control

Q-learning is arguably the most famous RL algorithm. It's a model-free, TD control method that directly approximates the optimal action-value function, $Q^{\ast }(s,a)$, regardless of the policy being followed.

The update rule for Q-learning looks very similar to the TD(0) update we saw for V-functions, but applied to Q-values:

$$Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\alpha \left[\underset{\text{TD Target}}{\underbrace{R_{t+1}+\gamma \underset{a^{\prime }}{\max }Q(S_{t+1},a^{\prime })}}-Q(S_t,A_t)\right]$$

Let's dissect this:

• We take an action $A_t$ in state $S_t$ and observe the reward $R_{t+1}$ and next state $S_{t+1}$.
• The crucial part is the TD target: $R_{t+1}+\gamma {\max }_{a^{\prime }}Q(S_{t+1},a^{\prime })$. To estimate the value from the next state, Q-learning uses the maximum Q-value possible from $S_{t+1}$. It assumes we will take the best possible action from that point onwards.
• This makes Q-learning an off-policy algorithm. The policy it learns about (the optimal, greedy policy) is different from the policy it uses to generate actions (the behavior policy, which must explore, e.g., $ϵ$-greedy). It learns about being greedy, even while it's behaving non-greedily.

This diagram clearly shows the update mechanism.

For a detailed walkthrough of the Q-learning algorithm and its off-policy nature, watch the following segment.

Implementing Q-Learning

Given your background in Python, let's look at a practical implementation. We'll use the FrozenLake-v1 environment from the Gymnasium library—a classic grid world where an agent must navigate a frozen lake to a goal, avoiding holes.

As you watch, consider how you would structure this code. The core components are:

1. A loop over episodes.
2. An inner loop for steps within an episode.
3. An action selection mechanism ($ϵ$-greedy).
4. Executing the action and getting (next_state, reward, done).
5. Updating the Q-table using the Q-learning rule.

For a formal pseudocode representation and a well-structured Python implementation, you can refer to the resource "Temporal difference reinforcement learning". It presents the algorithm clearly in Algorithm 4.

3. SARSA: On-Policy TD Control

SARSA is the on-policy sibling of Q-learning. Its name is a mnemonic for the sequence of events involved in its update: State, Action, Reward, State, Action.

The SARSA update rule is subtly but profoundly different from Q-learning:

$$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]$$

Notice the TD target: $R_{t+1}+\gamma Q(S_{t+1},A_{t+1})$.

• Instead of taking the maximum Q-value at the next state, SARSA uses the Q-value of the actual next action, $A_{t+1}$, that the agent chose to take according to its behavior policy (e.g., $ϵ$-greedy).
• This makes SARSA an on-policy algorithm. It learns the value of the exact policy it is following, including its exploratory actions. It doesn't make optimistic assumptions about acting greedily in the future.

The flowcharts below provide a great side-by-side comparison of the procedural differences.

Let's get a clear explanation of SARSA and its on-policy nature.

Implementing SARSA is very similar to implementing Q-learning. The main difference is that you must choose the next action, $A_{t+1}$, before you can calculate the TD target and update the Q-value for the current state-action pair, $Q(S_t,A_t)$. The gibberblot.github.io resource provides excellent pseudocode in Algorithm 5 and a Python implementation that highlights this difference.

4. On-Policy vs. Off-Policy: The Cliff Walking Example

So, which is better? The answer depends on the problem. The classic "Cliff Walking" environment provides the perfect illustration of their different behaviors.

The Setup: An agent starts at one corner of a grid and must reach the goal at the opposite corner. There's a "cliff" along the bottom edge.

• Optimal Path: Move right along the edge of the cliff. This is the shortest path but is very risky. One wrong (exploratory) move, and the agent falls off, receiving a large negative reward.
• Safe Path: Move up and around the cliff. This path is longer (and thus accumulates more small negative rewards per step) but is safe from falling.

Here's the takeaway from the Cliff Walking example:

• Q-Learning (Off-Policy): Learns the optimal policy (the risky path along the cliff). Because its update rule uses ${\max }_{a}Q(s^{\prime },a)$, it ignores the consequences of the exploratory actions that lead to falling off the cliff. It's an optimistic learner.
• SARSA (On-Policy): Learns the safe policy (the longer path). Because its update rule uses the Q-value of the next actual action, $Q(s^{\prime },a^{\prime })$, the large negative rewards from exploratory "falls" are incorporated into the Q-values of states near the cliff. It learns that being near the cliff is dangerous and finds a safer, albeit suboptimal, path.

This reveals a fundamental trade-off: optimality vs. safety during training.

Test your understanding!

Imagine you are developing an RL agent for two different tasks:

1. A simulated agent learning the absolute best strategy for a stock trading game, where you can run millions of episodes at no real cost.
2. A physical robot learning to navigate a factory floor with expensive equipment. Mistakes during training could be very costly.

Which algorithm, Q-learning or SARSA, would you choose as a starting point for each task, and why?

Show answer

1. Stock Trading Game: Q-learning is the better choice. The goal is to find the absolute optimal policy, and the cost of "bad" exploratory actions during training is zero (it's just a simulation). Q-learning's off-policy nature allows it to learn the optimal path without being overly conservative due to exploration.

2. Physical Robot: SARSA is the safer and more appropriate starting point. The on-policy nature of SARSA means it will be sensitive to the real-world consequences of its exploratory actions. It will learn a "safer" policy that avoids costly mistakes, which is paramount when physical damage or safety is a concern. The final policy might be slightly suboptimal, but the training process will be much less hazardous.

This detailed comparison video will solidify the practical differences between the two algorithms.

Conclusion

In this lesson, we moved from model-free prediction to model-free control, learning how to find optimal policies directly from experience. We implemented and contrasted two of the most important algorithms in the RL canon.

Key Takeaways:

• Model-Free Control uses the action-value function $Q(s,a)$ to select the best actions without needing a model of the environment.
• Q-Learning is an off-policy algorithm. It learns the optimal (greedy) policy by using the $\max$ operator in its update, making it "optimistic" and often faster at finding the best possible path.
• SARSA is an on-policy algorithm. It learns the value of the policy it is actually following (including exploration), making it more "realistic" and sensitive to the costs of mistakes during training.
• The choice between them represents a fundamental optimality vs. safety trade-off. SARSA is often preferred when training mistakes are costly, while Q-learning is preferred when the goal is to find the best possible policy in a safe (e.g., simulated) environment.

Preview of the Next Lesson:

We've just had a very practical introduction to the concepts of on-policy and off-policy learning. In our next lesson, we will formalize this distinction. We will explore more deeply what it means for an algorithm to be on-policy or off-policy and discuss the broader implications and applications of each approach, setting the stage for more advanced algorithms.