Reinforcement Learning Q-learning and SARSA

In the field of artificial intelligence, reinforcement learning is a method that allows an agent to learn how to achieve goals by interacting with the environment.

Imagine teaching a puppy a new command: when it performs an action (such as sitting), you give it a reward (a treat), and it gradually learns to respond correctly when it hears the command. Q-learning and SARSA are two classic and crucial algorithms in reinforcement learning; they are the core tools for the agent to learnwhat action is best in what statecore tools.

Reinforcement Learning and Markov Decision Process Basics

Before diving into Q-learning and SARSA, we need to understand the common theoretical framework they share.

Core Concepts

Reinforcement learning problems are usually modeled asa Markov decision process. It contains the following key elements:

  • Agent: The entity that makes decisions and learns.
  • Environment: The external world with which the agent interacts.
  • State: A description of the environment at a particular moment.
  • Action: An operation the agent can perform in a given state.
  • Reward: The immediate payoff signal fed back by the environment after the agent performs an action.
  • Policy: The rule by which the agent selects actions in a given state; it is the learning target.

Goals and Value Functions

The agent's ultimate goal is to maximize long-term cumulative reward, not just immediate reward. To this end, we introducevalue functions.。

  • State-value function V(s): Represents, starting from states, the expected cumulative reward obtainable by following a specific policy.
  • Action-value function Q(s, a): Represents, in statestaking actiona, and then following a specific policy, the expected cumulative reward that can be obtained.The core of Q-learning and SARSA is to learn this Q function.

To balance immediate and future rewards, we usediscount factor γ(usually in the range [0, 1]). The reward at future step k is multiplied by γ^k, which means the agent places more importance on near-term rewards.

Q-learning: Off-Policy Temporal Difference Learning

Q-learning is anoff-policyalgorithm, proposed by Watkins in 1989. Its core idea is that the agent indirectly finds the optimal policy by learning an optimal Q-value table.

Algorithm Core: Q-Value Update Formula

The learning process of Q-learning is driven by the following formula:Q(s_t, a_t) ← Q(s_t, a_t) + α * [ r_{t+1} + γ * max_{a} Q(s_{t+1}, a) - Q(s_t, a_t) ]

Let's break down this formula:

  • Q(s_t, a_t)Q(s, a): at time tt, in state ss_ttaking action aa_t, the current estimate.
  • α： Learning rate α, controls the degree to which new information overrides old information (0 < α ≤ 1).
  • r_{t+1}r: after executing an actiona_t, the immediate reward obtained.
  • γ： Discount factor γ, measures the importance of future rewards.
  • max_{a} Q(s_{t+1}, a)max Q(s', a'): in thenext state s_{t+1}, the largest Q value among all possible actions. This represents the best possible future return estimated based on the current Q table.
  • [ r_{t+1} + γ * max_{a} Q(s_{t+1}, a) - Q(s_t, a_t) ]TD error: calledtemporal difference error. It is the difference between the "target value" (immediate reward plus the best future estimate) and the "current estimate". The algorithm updates Q by reducing this error.

The Meaning of Off-Policy

Q-learning is calledoff-policy, because when it updates Q values, the action used to evaluate future value (max_{a} Q(s_{t+1}, a)) and the action the agent actually performs for explorationare separate.。

  • Behavior policy: The policy used to select actions actually performed (e.g., ε-greedy, which explores randomly with a certain probability).
  • Target policy: The policy used to update Q-values; it is a fully greedy policy (always selecting the action with the largest current Q-value).

This separation allows Q-learning to boldly learn using its estimate of the optimal path, even while it is currently performing random exploration.

Algorithm Procedure

SARSA: On-Policy Temporal Difference Learning

The name SARSA comes from the state-action sequence involved in its update process:(S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1}). It is anon-policyalgorithm.

Algorithm Core: Q-Value Update Formula

SARSA's update formula is very similar to Q-learning's, but there is one key difference:Q(s_t, a_t) ← Q(s_t, a_t) + α * [ r_{t+1} + γ * Q(s_{t+1}, a_{t+1}) - Q(s_t, a_t) ]

Notice the second part:

  • Q-learning uses max_{a'} Q(s', a')： γ * max_{a} Q(s_{t+1}, a)
  • SARSA uses Q(s', a')： γ * Q(s_{t+1}, a_{t+1})

In SARSA, the agent inthe next states_{t+1}will actually take an actiona_{t+1}whose Q-value is used to estimate future value.

The Meaning of On-Policy

SARSA is calledon-policy, because the policy it uses to update Q-values (target policy) and the policy it uses to select actions (behavior policy)are the same, both usually being the ε-greedy policy.

  • It evaluates and optimizes the policy itis currently executing.
  • What it learns is a policy that accounts for the risk of future exploration, so it is usually more "conservative".

Comparison of Q-learning and SARSA

Understanding the difference between the two is key to mastering them. The table below clearly summarizes the core differences:

Feature Q-learning SARSA
Policy type Off-policy On-policy
Update target Based on the optimal action:r + γ * max Q(s', a') Based on the actual action:r + γ * Q(s', a_{t+1})
Learning objective Learnthe optimal policy'sQ-function. Learnthe behavior policy (e.g., ε-greedy)'s Q-function.
Risk tendency More "bold", assumes optimal actions will be taken in the future More "conservative", considers the risk that future exploration may bring
Update timing In(s, a, r, s')can be updated immediately after (S, A, R, S') requires(s, a, r, s', a')the five-tuple (S, A, R, S', A') to update.
Typical applications Discrete environments, seeking the global optimal solution Environments with high safety requirements, where dangerous states need to be avoided

Classic Cliff Walking Example

This example vividly illustrates the difference between the two. Suppose a grid world where the agent walks from start S to goal G; below is a cliff. Falling off gives a large negative reward and returns to the start.

  • Q-learningQ-learning: Since it assumes the future will always take the optimal (safest) path, it quickly learns the shortest path along the cliff edge (Path 1), because it "believes" it will not fall off.
  • SARSASARSA: Since it considers that there is still a probability ε of random exploration in the future, it may fall off the cliff. Therefore, it learns a safer path further up (Path 2). Although longer, its long-term expected return is higher.

Conclusion: In environments where exploration and exploitation need to be balanced and mistakes are costly, SARSA usually learns a safer and more robust policy.

Code Practice: Implementing Q-learning and SARSA in Python

We will use a simple4x4grid world to demonstrate both algorithms. The goal is for the agent to move from the top-left corner(0,0)to the bottom-right corner(3,3)。

Environment Setup

Example

import numpy as np
import random

class GridWorld:
    def __init__(self, size=4):
        self.size = size
        self.state = (0, 0) # Starting point
        self.goal = (size-1, size-1) # Ending point
        self.actions = ['up', 'down', 'left', 'right']
        self.action_map = {'up': (-1, 0), 'down': (1, 0), 'left': (0, -1), 'right': (0, 1)}

    def reset(self):
        """Reset environment to starting point"""
        self.state = (0, 0)
        return self.state

    def step(self, action):
        """Execute action, return (next state, reward, terminated)"""
        move = self.action_map[action]
        next_state = (self.state[0] + move[0], self.state[1] + move[1])

        # Boundary check: if out of bounds, stay in place
        if not (0 <= next_state[0] < self.size and 0 <= next_state[1] < self.size):
            next_state = self.state

        self.state = next_state

        # Reward setup: reward 10 for reaching goal, -1 for other moves (encourage reaching quickly)
        if next_state == self.goal:
            reward = 10
            done = True
        else:
            reward = -1
            done = False

        return next_state, reward, done

    def get_actions(self):
        return self.actions

Q-learning Algorithm Implementation

Example

def q_learning(env, episodes=500, alpha=0.1, gamma=0.9, epsilon=0.1):
    """
Implement Q-learning algorithm
env: environment object
episodes: number of training episodes
alpha: learning rate
gamma: discount factor
epsilon: exploration probability in ε-greedy policy
    """
    # Initialize Q table with shape [grid rows, grid cols, number of actions]
    q_table = np.zeros((env.size, env.size, len(env.actions)))

    for episode in range(episodes):
        state = env.reset()
        done = False

        while not done:
            # 1. Choose action using ε-greedy policy
            if random.uniform(0, 1) < epsilon:
                action_idx = random.randint(0, len(env.actions)-1) # Exploration: randomly choose
            else:
                action_idx = np.argmax(q_table[state[0], state[1], :]) # Exploitation: choose the one with maximum Q value
            action = env.actions[action_idx]

            # 2. Take action, get feedback
            next_state, reward, done = env.step(action)

            # 3. Q-learning core update
            # Q value of the current state-action pair
            current_q = q_table[state[0], state[1], action_idx]
            # Maximum Q value of the next state (key for off-policy)
            next_max_q = np.max(q_table[next_state[0], next_state[1], :])
            # Compute target Q value
            target_q = reward + gamma * next_max_q
            # Update Q table
            q_table[state[0], state[1], action_idx] = current_q + alpha * (target_q - current_q)

            # Transition to next state
            state = next_state

    return q_table

SARSA Algorithm Implementation

Example

def sarsa(env, episodes=500, alpha=0.1, gamma=0.9, epsilon=0.1):
    """
Implement SARSA algorithm
Parameter meanings same as Q-learning
    """
    q_table = np.zeros((env.size, env.size, len(env.actions)))

    for episode in range(episodes):
        state = env.reset()
        done = False

        # SARSA needs to first choose an action for the initial state
        if random.uniform(0, 1) < epsilon:
            action_idx = random.randint(0, len(env.actions)-1)
        else:
            action_idx = np.argmax(q_table[state[0], state[1], :])
        action = env.actions[action_idx]

        while not done:
            # 1. Execute the action chosen in the previous step
            next_state, reward, done = env.step(action)

            # 2. Choose an action for the next state (on-policy, still using ε-greedy)
            if random.uniform(0, 1) < epsilon:
                next_action_idx = random.randint(0, len(env.actions)-1)
            else:
                next_action_idx = np.argmax(q_table[next_state[0], next_state[1], :])
            next_action = env.actions[next_action_idx]

            # 3. SARSA core update
            current_q = q_table[state[0], state[1], action_idx]
            # Key difference: use the Q value of the **actual action to be executed** in the next state
            next_q = q_table[next_state[0], next_state[1], next_action_idx]
            target_q = reward + gamma * next_q
            q_table[state[0], state[1], action_idx] = current_q + alpha * (target_q - current_q)

            # 4. Update state and action for the next iteration
            state = next_state
            action_idx = next_action_idx
            action = next_action

    return q_table

Testing and Policy Visualization

Example

def test_policy(env, q_table, episodes=10):
    """Test the learned policy"""
    total_rewards = []
    for _ in range(episodes):
        state = env.reset()
        done = False
        total_reward = 0
        steps = []

        while not done:
            # Use greedy policy during testing (no exploration)
            action_idx = np.argmax(q_table[state[0], state[1], :])
            action = env.actions[action_idx]
            next_state, reward, done = env.step(action)
            steps.append(action[0].upper()) # Record the first letter of each action
            total_reward += reward
            state = next_state

        total_rewards.append(total_reward)
        print(f"Episode steps: {steps}, Total reward: {total_reward}")

    print(f"Average reward: {np.mean(total_rewards):.2f}")

# Create environment
env = GridWorld(size=4)

print("=== Training and testing Q-learning ===")
q_table_ql = q_learning(env, episodes=1000)
test_policy(env, q_table_ql)

print("\n"=== Training and testing SARSA ===")
env.reset() # Reset environment state
q_table_sarsa = sarsa(env, episodes=1000)
test_policy(env, q_table_sarsa)

# Simply compare the final policies
print("\n=== Policy comparison (actions from starting point (0,0)) ===)
start_q_values = q_table_ql[0, 0, :]
start_sarsa_values = q_table_sarsa[0, 0, :]
print(f"Q-learning Q-values: {dict(zip(env.actions, start_q_values))}")
print(f"Recommended action: {env.actions[np.argmax(start_q_values)]}")
print(f"SARSA Q-values: {dict(zip(env.actions, start_sarsa_values))}")
print(f"Recommended action: {env.actions[np.argmax(start_sarsa_values)]}")
Other Extensions