Introduction to Q-Learning

Recommended resources

The freely available resources this lesson will direct you to.

Introduction

In our previous lesson, we established the theoretical foundation for solving Reinforcement Learning problems using the Bellman equations. We saw that if we have a perfect model of the environment's dynamics, $p (s^{'}, r ∣ s, a)$ , we can use methods like Value Iteration to find the optimal value function $V^{*}$ or $Q^{*}$ . However, in most real-world scenarios, from robotics to game playing, such a perfect model is unavailable. This raises a critical question: how can an agent learn to act optimally by learning directly from its experience?

This lesson introduces Q-learning, a cornerstone algorithm that answers this question. You will learn how Q-learning combines the recursive structure of the Bellman equation with the model-free approach of learning from sampled experiences. We will define the algorithm's update rule, and then delve into the crucial distinction between on-policy and off-policy learning, which is key to understanding why Q-learning is so powerful and widely used. By the end, you will understand how Q-learning works as a canonical value-based, off-policy method for finding optimal policies.

From Model-Based to Model-Free Learning

The methods derived from the Bellman equations in the last lesson, such as Value Iteration, are forms of Dynamic Programming (DP). They require a complete model of the MDP to perform the expectation calculations. This is why they are called model-based methods. When a model is not available, we must turn to model-free methods, which learn value functions and policies purely from sampled experience tuples: $(S_{t}, A_{t}, R_{t + 1}, S_{t + 1})$ .

The simplest model-free approach is Monte Carlo (MC) learning, where the agent estimates the value of a state by averaging the full returns ( $G_{t}$ ) from all episodes that have passed through that state. While unbiased, MC methods have two main drawbacks: they have high variance (since a return is a sum of many random variables) and can only learn from complete, finite episodes.

A more sophisticated and generally more efficient approach is Temporal-Difference (TD) Learning. TD learning strikes a balance between DP and MC methods.

Like MC, it learns directly from experience without a model.
Like DP, it updates value estimates based on other learned estimates, a process called bootstrapping. It does not wait for the end of an episode.

The core of TD learning for policy evaluation is the following update rule for the state-value function $V$ :

V (S_{t}) \leftarrow V (S_{t}) + α TD Error [R_{t + 1} + γ V (S_{t + 1}) - V (S_{t})]

Here, $R_{t + 1} + γ V (S_{t + 1})$ is the TD Target, an estimate of the return from state $S_{t}$ . The algorithm nudges the current value $V (S_{t})$ towards this target. This is effectively a stochastic approximation of the Bellman expectation equation we saw previously.

Reinforcement Learning 4: Model-Free Prediction and Control

This segment from a lecture by Hado van Hasselt provides an excellent conceptual overview of the shift towards model-free learning and the core idea of TD learning.

Watch the portion of the video from the introduction of TD learning. Focus on the comparison between Dynamic Programming, Monte Carlo, and TD learning, and understand the concepts of the TD target and the bias-variance tradeoff.

Q-Learning: TD Control without a Model

Now, how can we use this TD idea not just for evaluating a policy (prediction), but for finding the optimal policy (control)? The key is to apply the TD learning principle to the action-value function $Q (s, a)$ and to use the Bellman optimality equation as our guide.

Recall the Bellman optimality equation for $Q^{*}$ :

Q^{*} (s, a) = E [R_{t + 1} + γ a^{'} max Q^{*} (S_{t + 1}, a^{'}) ∣ S_{t} = s, A_{t} = a]

Q-learning directly implements a stochastic approximation of this equation. Given a transition $(s, a, r, s^{'})$ , the Q-learning update is:

Q (s, a) \leftarrow Q (s, a) + α Q-learning Target r + γ a^{'} max Q (s^{'}, a^{'}) - Q (s, a)

Let's break this down:

The agent is in state $s$ and takes action $a$ .
It observes a reward $r$ and the next state $s^{'}$ .
The term $r + γ max_{a^{'}} Q (s^{'}, a^{'})$ serves as a sampled estimate of the optimal long-term return from taking action $a$ in state $s$ . It combines the real, immediate reward $r$ with the current best estimate of the future value from the next state $s^{'}$ , assuming a greedy action is taken there.
The difference between this target and the old estimate $Q (s, a)$ is the TD error.
The old $Q (s, a)$ value is updated by a small step ( $α$ ) in the direction of this error.

By repeatedly applying this update, the $Q$ function progressively converges towards the optimal action-value function, $Q^{*}$ .

Q-Learning: Model Free Reinforcement Learning and Temporal Difference Learning

Steve Brunton's video offers a very clear and direct derivation of the Q-learning update rule as an application of temporal difference learning to the quality function.

Please watch the segment from "Q-learning is essentially". This will walk you through the components of the update rule, explaining how the TD target is constructed for Q-learning.

The entire process follows an iterative loop, as depicted in the flowchart below. The agent observes its state, uses its current Q-table to decide on an action (balancing exploration and exploitation), receives a reward, and then uses this experience to update the Q-table before starting the next step.

This flowchart illustrates the iterative cycle of a Q-learning agent. At each step, the agent observes the state, chooses an action, receives a reward, and updates its Q-table based on the observed outcome.

Off-Policy vs. On-Policy Learning

One of the most powerful aspects of Q-learning is that it is an off-policy algorithm. To understand this, we must distinguish between two policies:

The behavior policy ( $b$ ): The policy the agent uses to explore the environment and select actions (e.g., an $ϵ$ -greedy policy that mostly acts greedily but occasionally takes a random action to explore).
The target policy ( $π$ ): The policy that the agent is trying to learn and improve (in the case of Q-learning, the optimal greedy policy).

An off-policy method is one where the target policy is different from the behavior policy ( $π \neq = b$ ). An on-policy method learns the value of the policy it is currently executing ( $π = b$ ).

On-Policy vs Off-Policy Reinforcement Learning

This article from Georgia Tech's CORE Robotics lab provides a crystal-clear distinction between behavior and update policies, which is fundamental to understanding the on-policy/off-policy concept.

Please read the introductory part of the article, focusing on the definitions of the Behavior Policy and the Update Policy. The key insight is presented in the bolded and italicized paragraph that follows.

Q-learning is off-policy because its update depends on $max_{a^{'}} Q (s^{'}, a^{'})$ . This term concerns the best possible action from the next state, which defines the greedy target policy. However, the action $A_{t}$ that was actually taken to generate the experience might have been chosen by a more exploratory behavior policy. Q-learning learns about the optimal way to behave, even when it isn't currently behaving optimally.

To make this concrete, let's contrast Q-learning with a classic on-policy algorithm: SARSA (State-Action-Reward-State-Action).

The SARSA update rule is:

Q (s, a) \leftarrow Q (s, a) + α [r + γ Q (s^{'}, a^{'}) - Q (s, a)]

The crucial difference is that the SARSA target uses $Q (s^{'}, a^{'})$ , where $a^{'}$ is the actual action taken in the next state $s^{'}$ according to the behavior policy. SARSA learns the value of its own policy, including the exploratory "wiggles".

Lecture 7 - Temporal Difference Learning and Stochastic ...

These lecture notes provide a concise, formal definition of both SARSA and Q-learning, clearly highlighting the difference in their update rules.

Please read Section 7.4, TD Control. First, read the paragraph defining SARSA (On-Policy TD Control). Then, read the paragraph defining Q-learning (Off-Policy TD Control) and note the structural difference in their update equations.

Case Study: The Cliff Walking Problem

The practical difference between off-policy and on-policy learning is best illustrated with the "Cliff Walking" environment. An agent must travel from a start (S) to a goal (G). Every step has a reward of -1. Stepping into the "cliff" region results in a large negative reward of -100 and sends the agent back to the start.

Q-learning (off-policy) learns the optimal policy, which is to walk right along the edge of the cliff. Its update rule always assumes the optimal next step will be taken, so it is not "afraid" of the cliff. However, while executing its $ϵ$ -greedy behavior policy, it will frequently take a random step down, fall off the cliff, and incur a large penalty.
SARSA (on-policy) learns a safer, but suboptimal, policy. Because its updates incorporate the actual (potentially random) next action, it learns that being near the cliff is dangerous. The Q-values near the cliff edge become very low because there's a chance that the $ϵ$ -greedy policy will choose to step down. As a result, the final greedy policy learned by SARSA gives the cliff a wide berth.

On-Policy vs Off-Policy Reinforcement Learning

The same article provides a great visual and conceptual explanation of this case study.

Read Section 3, Implications. Pay attention to the figure showing the two paths and the explanation of why Q-learning learns the optimal path while SARSA learns a safer one. The plot of rewards during training is also insightful.

This case study highlights the fundamental tradeoff: Q-learning directly learns the optimal policy but can be unsafe during training. SARSA learns a more conservative policy that is safer during exploration but is not strictly optimal.

A Deeper Look: Maximization Bias

Your background in systems and algorithms makes you well-equipped to appreciate a subtle but important issue in Q-learning: maximization bias. The max operator in the Q-learning update is taken over estimated values, which are noisy. The maximum of a set of noisy random variables is often an overestimate of the maximum of their true means. This can lead to Q-learning systematically overestimating the Q-values.

A clever solution to this is Double Q-learning. Instead of one Q-table, we maintain two, $Q_{A}$ and $Q_{B}$ . For each experience, we randomly choose one to update.

To update $Q_{A}$ , we find the best next action using $Q_{A}$ but get its value from $Q_{B}$ : $a^{*} = a^{'} argmax Q_{A} (s^{'}, a^{'})$ $Q_{A} (s, a) \leftarrow Q_{A} (s, a) + α [r + γ Q_{B} (s^{'}, a^{*}) - Q_{A} (s, a)]$
To update $Q_{B}$ , we do the reverse.

This decouples the selection of the best action from the evaluation of its value, which mitigates the overestimation bias.

Reinforcement Learning 4: Model-Free Prediction and Control

Hado van Hasselt, who co-developed Double Q-learning, explains the issue of maximization bias and the solution.

Please watch the segment from "I want to talk about an issue". Focus on the intuition for why the max operator causes an upward bias and how using two separate Q-functions for selection and evaluation resolves this. The results on the Atari games demonstrate its practical impact.

Conclusion

This lesson has taken us from the world of model-based planning to model-free learning. Q-learning stands as a canonical example of how an agent can learn optimal behavior directly from environmental interaction, without needing a pre-existing model of the world.

Here are the essential takeaways:

Q-learning is a model-free, value-based reinforcement learning algorithm that uses Temporal-Difference (TD) learning to find the optimal action-value function, $Q^{*}$ .
Its update rule, $Q (s, a) \leftarrow Q (s, a) + α [r + γ max_{a^{'}} Q (s^{'}, a^{'}) - Q (s, a)]$ , is a stochastic approximation of the Bellman optimality equation.
Q-learning is an off-policy algorithm because it learns about the optimal (greedy) policy while following a different, more exploratory behavior policy. This allows for efficient learning but can lead to risky behavior during training.
This contrasts with on-policy methods like SARSA, which learn the value of the actual behavior policy being executed, often resulting in safer but suboptimal final policies.
Advanced techniques like Double Q-learning can address theoretical issues like maximization bias, improving performance and stability.

In all the methods we've seen so far, the core idea has been to learn a value function ( $V$ or $Q$ ) and then derive a policy from it. In our next lesson, we will explore a fundamentally different approach: policy gradient methods, which bypass value functions and learn the policy directly.