SARSA Update - Reinforcement Learning

SARSA Update

What you'll build

One step of SARSA, the on-policy cousin of Q-learning, which bootstraps from the action the agent actually takes next.

Background

SARSA is named after the tuple it learns from: (S, A, R, S', A'). Because it evaluates the policy it is following (exploration included), it learns safer behaviour when exploratory mistakes are costly. In the classic cliff-walking task, SARSA learns the path away from the cliff edge, while Q-learning learns the optimal edge path and falls off during ε-greedy exploration.

Formula

target = r + γ · Q(s', a')        (a' = the next action actually taken)
δ      = target - Q(s, a)
Q(s, a) ← Q(s, a) + α · δ

	SARSA	Q-learning
Bootstrap value	Q(s', a') for the action taken	max over a' of Q(s', a')
Policy type	On-policy	Off-policy
Learns	Value of the behaviour policy	Value of the greedy policy

Inputs

• Q: (n_states, n_actions) Q-table
• state, action, next_state, next_action: int indices
• reward, alpha, gamma: floats

Expected return format

The updated (n_states, n_actions) Q-table as a float array (a nested list also passes), rounded to 2 decimals. Work on a copy.

Edge cases and conventions

• Only Q[state, action] changes.
• No done flag: a terminal transition is modelled with gamma = 0.

Constraints

NumPy only.

Follow-up

• Expected SARSA replaces Q(s', a') with Σ_a' π(a'|s')·Q(s', a'). Why does that lower variance?
• With ε → 0 over time, what do SARSA and Q-learning converge to?

Input: Q = [[1, 2], [3, 4]], s = 0, a = 0, r = 5, s' = 1, a' = 0, α = 0.5, γ = 0.9
Output: [[4.35, 2.0], [3.0, 4.0]]

Input: Same, but a' = 1
Output: [[4.8, 2.0], [3.0, 4.0]]

import numpy as np

def sarsa_update(Q: np.ndarray, state: int, action: int, reward: float,
                 next_state: int, next_action: int,
                 alpha: float, gamma: float) -> np.ndarray:
    """
    Perform one SARSA update.

    Args:
        Q: (n_states, n_actions) Q-table
        state: current state s
        action: action taken a
        reward: reward received r
        next_state: next state s'
        next_action: next action a' (the one that will actually be taken)
        alpha: learning rate
        gamma: discount factor

    Returns:
        Updated (n_states, n_actions) Q-table (a copy), rounded to 2 decimals
    """
    Q = np.array(Q, dtype=float)
    # Your code here
    pass