SARSA, Q-Learning and Expected SARSA Targets

Problem Statement

Implement the three action-value control updates side by side. They differ only in how the next state is valued.

Background

Every one of these has the same skeleton — move Q(s,a) a fraction alpha toward a target — and the entire on-policy/off-policy distinction lives in one term.

SARSA uses the action the behaviour policy actually took next:

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

It is on-policy: it learns the value of the policy you are running, exploration mistakes included. That is why SARSA learns the "safe" path near a cliff — it knows an epsilon-greedy agent will occasionally fall off.

Q-learning ignores what happened next and uses the greedy value:

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

It is off-policy: it learns the optimal policy's values while behaving with exploration. The price is maximisation bias — a max over noisy estimates is systematically optimistic.

Expected SARSA replaces the sample or the max with the exact expectation under the target policy:

$Q(S_t,A_t) \leftarrow Q(S_t,A_t) + \alpha\Big[R_{t+1} + \gamma \sum_{a'} \pi(a' \mid S_{t+1}) Q(S_{t+1},a') - Q(S_t,A_t)\Big]$

Removing the sampling of $A_{t+1}$ removes its variance for the cost of one extra sum, which is usually free. With an epsilon-greedy $\pi$ and epsilon = 0 it is Q-learning; with larger epsilon it drifts toward the on-policy answer.

Your Task

Implement all three. Each returns the new scalar value of Q[s][a]; do not mutate Q.

def sarsa_update(Q, s, a, r, s2, a2, alpha, gamma):
    ...

def q_learning_update(Q, s, a, r, s2, alpha, gamma):
    ...

def expected_sarsa_update(Q, s, a, r, s2, alpha, gamma, epsilon):
    ...

expected_sarsa_update weights the successor action values by an **epsilon-greedy distribution over **Q[s2]****, splitting the greedy probability 1 - epsilon evenly across all tied maxima.

Input / Output Format

Q is a nested list of floats. Each function returns a single float, rounded to 4 decimals by the grader.

Sample

Q = [[0.0, 0.0], [2.0, 6.0]]
print(round(sarsa_update(Q, 0, 0, 1.0, 1, 0, 0.5, 0.9), 4))
print(round(q_learning_update(Q, 0, 0, 1.0, 1, 0.5, 0.9), 4))
print(round(expected_sarsa_update(Q, 0, 0, 1.0, 1, 0.5, 0.9, 0.2), 4))

Output:

1.4
3.2
3.02

All three start from Q[0][0] = 0.0 and move half way (alpha = 0.5) toward their target. SARSA bootstraps off the action actually taken, Q[1][0] = 2.0, for a target of 1.0 + 0.9*2.0 = 2.8. Q-learning bootstraps off max(Q[1]) = 6.0, for a target of 6.4. Expected SARSA bootstraps off the epsilon-greedy expectation 0.12.0 + 0.96.0 = 5.6, for a target of 1.0 + 0.9*5.6 = 6.04.