Topic 18: Reinforcement Learning Exercises¶

These exercises test your understanding of Markov Decision Processes, Temporal Difference learning, and the difference between on-policy and off-policy algorithms.

Reference: theory.md

In [1]:

import random

import matplotlib.pyplot as plt
import numpy as np

%load_ext autoreload
%autoreload 2

SEED = 42
random.seed(SEED)
rng = np.random.default_rng(SEED)

plt.rcParams["figure.dpi"] = 90

import random import matplotlib.pyplot as plt import numpy as np %load_ext autoreload %autoreload 2 SEED = 42 random.seed(SEED) rng = np.random.default_rng(SEED) plt.rcParams["figure.dpi"] = 90

Exercise 1: Hand Calculation - Value Iteration¶

Consider a tiny MDP with 3 states: $S = \{s_1, s_2, s_3\}$ and 2 actions: $A = \{a_1, a_2\}$.

• $s_3$ is a terminal goal state.
• Discount factor $\gamma = 0.9$.
• Initial values $V_0(s) = 0$ for all $s$.

Transitions and Rewards from $s_1$:

• Action $a_1$: transitions to $s_2$ with probability 1.0, reward = 0
• Action $a_2$: transitions to $s_3$ with probability 0.8, reward = 10; transitions to $s_1$ with probability 0.2, reward = -1

Task: Compute $V_1(s_1)$, which is the value of $s_1$ after exactly one step of Value Iteration.

Write your derivation here: ...

Solution 1¶

The Bellman Optimality update is: $$ V_{k+1}(s) = \max_a \sum_{s'} P(s'|s,a)[R(s,a,s') + \gamma V_k(s')] $$

Since $V_0(s) = 0$ for all states, the $\gamma V_0(s')$ term is 0.

For $s_1$:

• $Q(s_1, a_1) = 1.0 \times (0 + 0) = 0$
• $Q(s_1, a_2) = 0.8 \times (10 + 0) + 0.2 \times (-1 + 0) = 8.0 - 0.2 = 7.8$

$$ V_1(s_1) = \max(0, 7.8) = 7.8 $$

In [2]:

# Code Verification
v0 = {'s1': 0, 's2': 0, 's3': 0}
gamma = 0.9

q_s1_a1 = 1.0 * (0 + gamma * v0['s2'])
q_s1_a2 = 0.8 * (10 + gamma * v0['s3']) + 0.2 * (-1 + gamma * v0['s1'])

v1_s1 = max(q_s1_a1, q_s1_a2)
print(f"V_1(s_1) = {v1_s1}")
assert np.isclose(v1_s1, 7.8)

# Code Verification v0 = {'s1': 0, 's2': 0, 's3': 0} gamma = 0.9 q_s1_a1 = 1.0 * (0 + gamma * v0['s2']) q_s1_a2 = 0.8 * (10 + gamma * v0['s3']) + 0.2 * (-1 + gamma * v0['s1']) v1_s1 = max(q_s1_a1, q_s1_a2) print(f"V_1(s_1) = {v1_s1}") assert np.isclose(v1_s1, 7.8)

V_1(s_1) = 7.8

Exercise 2: Implementation - SARSA¶

You have seen Q-Learning, an off-policy TD control method. Now implement SARSA, an on-policy TD control method.

The update rule for SARSA is: $$ 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] $$

Task: Complete the SARSAAgent class below. Notice that update takes next_action as an argument, unlike Q-Learning.

In [3]:

class SARSAAgent:
    def __init__(self, n_states, n_actions, alpha=0.1, gamma=0.9):
        # For simplicity, states are just integers 0 to n_states-1
        self.Q = np.zeros((n_states, n_actions))
        self.alpha = alpha
        self.gamma = gamma
        
    def update(self, state, action, reward, next_state, next_action, done):
        # TODO: Implement the SARSA update rule
        pass

class SARSAAgent: def __init__(self, n_states, n_actions, alpha=0.1, gamma=0.9): # For simplicity, states are just integers 0 to n_states-1 self.Q = np.zeros((n_states, n_actions)) self.alpha = alpha self.gamma = gamma def update(self, state, action, reward, next_state, next_action, done): # TODO: Implement the SARSA update rule pass

Solution 2¶

In [4]:

class SARSAAgent:
    def __init__(self, n_states, n_actions, alpha=0.1, gamma=0.9):
        self.Q = np.zeros((n_states, n_actions))
        self.alpha = alpha
        self.gamma = gamma
        
    def update(self, state, action, reward, next_state, next_action, done):
        if done:
            td_target = reward
        else:
            td_target = reward + self.gamma * self.Q[next_state, next_action]
            
        td_error = td_target - self.Q[state, action]
        self.Q[state, action] += self.alpha * td_error

# Deterministic assertion check
agent = SARSAAgent(n_states=5, n_actions=2, alpha=0.5, gamma=0.9)
agent.Q[1, 0] = 1.0
agent.Q[2, 1] = 2.0

# Experience: S_t=1, A_t=0, R_{t+1}=5, S_{t+1}=2, A_{t+1}=1 (done=False)
agent.update(state=1, action=0, reward=5.0, next_state=2, next_action=1, done=False)

# Expected Target: 5.0 + 0.9 * 2.0 = 6.8
# Expected Error: 6.8 - 1.0 = 5.8
# New Q: 1.0 + 0.5 * 5.8 = 3.9
print("Updated Q:", agent.Q[1, 0])
assert np.isclose(agent.Q[1, 0], 3.9), "SARSA update incorrect"

class SARSAAgent: def __init__(self, n_states, n_actions, alpha=0.1, gamma=0.9): self.Q = np.zeros((n_states, n_actions)) self.alpha = alpha self.gamma = gamma def update(self, state, action, reward, next_state, next_action, done): if done: td_target = reward else: td_target = reward + self.gamma * self.Q[next_state, next_action] td_error = td_target - self.Q[state, action] self.Q[state, action] += self.alpha * td_error # Deterministic assertion check agent = SARSAAgent(n_states=5, n_actions=2, alpha=0.5, gamma=0.9) agent.Q[1, 0] = 1.0 agent.Q[2, 1] = 2.0 # Experience: S_t=1, A_t=0, R_{t+1}=5, S_{t+1}=2, A_{t+1}=1 (done=False) agent.update(state=1, action=0, reward=5.0, next_state=2, next_action=1, done=False) # Expected Target: 5.0 + 0.9 * 2.0 = 6.8 # Expected Error: 6.8 - 1.0 = 5.8 # New Q: 1.0 + 0.5 * 5.8 = 3.9 print("Updated Q:", agent.Q[1, 0]) assert np.isclose(agent.Q[1, 0], 3.9), "SARSA update incorrect"

Updated Q: 3.9

Exercise 3: Conceptual - Q-Learning vs SARSA¶

Question: Explain why Q-learning is called an off-policy algorithm while SARSA is called an on-policy algorithm. When might you prefer SARSA over Q-learning?

Answer: ...

Solution 3¶

Off-policy vs On-policy:

• Q-Learning is off-policy because it updates the Q-value of an action using the maximum Q-value of the next state ($\max_{a'} Q(S_{t+1}, a')$). It assumes the agent will take the greedy (optimal) action next, regardless of what exploratory action the agent actually ends up taking due to its $\epsilon$-greedy policy. It learns the value of the optimal policy while following a different exploratory policy.
• SARSA is on-policy because it updates the Q-value using the action the agent actually takes in the next state ($Q(S_{t+1}, A_{t+1})$). It learns the value of the exact policy that the agent is currently following (e.g., an $\epsilon$-greedy policy).

When to prefer SARSA: SARSA is preferred when the cost of exploration is very high during training. For example, in the classic Cliff Walking environment, a random exploratory action near the cliff causes the agent to fall and incur a massive negative reward.

• Q-learning will learn a policy that walks right along the edge of the cliff (because it assumes it will never take a random action when calculating targets).
• SARSA learns that it is currently acting $\epsilon$-greedily and might randomly jump off the cliff, so it learns a safer policy that takes a wider path around the cliff to avoid the catastrophic cost of exploration during training.

Exercise 4: Advantage Actor-Critic (A2C) Calculation¶

In Advantage Actor-Critic (A2C), the Advantage function $A(s, a) = Q(s, a) - V(s)$ measures how much better taking action $a$ is compared to the baseline expected return from state $s$.

Using a 1-step Temporal Difference target, the advantage estimate is: $$\hat{A}(s_t, a_t) = R_{t+1} + \gamma (1 - done) V(S_{t+1}) - V(S_t)$$

Task: Implement a function that computes:

1. The Advantage $\hat{A}(s, a)$.
2. The Policy (Actor) loss gradient signal: $-\log(\pi(a|s)) \cdot \hat{A}(s, a)$.
3. The Value (Critic) loss: $0.5 \cdot \hat{A}(s, a)^2$.

Solution 4¶

With the given numbers: $\hat{A} = 1.0 + 0.9 \times 2.0 - 1.5 = 1.3$. The actor signal scales $-\log \pi(a|s)$ by this advantage, and the critic loss regresses the TD error toward zero.

In [5]:

def compute_a2c_updates(state_val, next_state_val, reward, done, action_prob, gamma=0.99):
    """
    Computes A2C advantage, actor policy gradient signal, and critic loss.
    """
    target = reward + (0.0 if done else gamma * next_state_val)
    advantage = target - state_val
    actor_grad_signal = -np.log(action_prob + 1e-8) * advantage
    critic_loss = 0.5 * (advantage ** 2)
    return advantage, actor_grad_signal, critic_loss

# Deterministic Test Check
adv, actor_sig, critic_l = compute_a2c_updates(state_val=1.5, next_state_val=2.0, reward=1.0, done=False, action_prob=0.8, gamma=0.9)

print(f"Advantage: {adv:.4f}")
print(f"Actor Grad Signal: {actor_sig:.4f}")
print(f"Critic Loss: {critic_l:.4f}")

# Sanity Assertions
assert np.isclose(adv, 1.3), f"Expected advantage 1.3, got {adv}"
assert np.isclose(critic_l, 0.845), f"Expected critic loss 0.845, got {critic_l}"
print("All A2C assertions passed!")

def compute_a2c_updates(state_val, next_state_val, reward, done, action_prob, gamma=0.99): """ Computes A2C advantage, actor policy gradient signal, and critic loss. """ target = reward + (0.0 if done else gamma * next_state_val) advantage = target - state_val actor_grad_signal = -np.log(action_prob + 1e-8) * advantage critic_loss = 0.5 * (advantage ** 2) return advantage, actor_grad_signal, critic_loss # Deterministic Test Check adv, actor_sig, critic_l = compute_a2c_updates(state_val=1.5, next_state_val=2.0, reward=1.0, done=False, action_prob=0.8, gamma=0.9) print(f"Advantage: {adv:.4f}") print(f"Actor Grad Signal: {actor_sig:.4f}") print(f"Critic Loss: {critic_l:.4f}") # Sanity Assertions assert np.isclose(adv, 1.3), f"Expected advantage 1.3, got {adv}" assert np.isclose(critic_l, 0.845), f"Expected critic loss 0.845, got {critic_l}" print("All A2C assertions passed!")

Advantage: 1.3000
Actor Grad Signal: 0.2901
Critic Loss: 0.8450
All A2C assertions passed!

Exercise 5: UCB Regret Bound (Hand Derivation)¶

Given: 2-armed bandit, arm 1 mean=0.6, arm 2 mean=0.4. Agent uses UCB1 with $c=1$.

• Task: Compute UCB values for both arms at $t=10$ given $N_1(10)=7, N_2(10)=3, Q_1=0.57, Q_2=0.33$
• Derive which arm UCB selects and explain why

Solution 5¶

With $\text{UCB}_i = Q_i + c\sqrt{\ln t / N_i}$ and $\ln 10 \approx 2.3026$:

• Arm 1: $0.57 + \sqrt{2.3026 / 7} = 0.57 + 0.5735 = 1.1435$
• Arm 2: $0.33 + \sqrt{2.3026 / 3} = 0.33 + 0.8761 = 1.2061$

Result: UCB selects arm 2. Although its estimated mean is lower, it has been pulled fewer times, so its confidence bonus is larger — optimism in the face of uncertainty forces further exploration of the under-sampled arm.

In [6]:

# Exercise 5: Verification Code
t = 10
N = np.array([7, 3])
Q = np.array([0.57, 0.33])
c = 1.0

ucb_values = Q + c * np.sqrt(np.log(t) / N)
selected_arm = np.argmax(ucb_values)

print(f"UCB values: {ucb_values}")
print(f"Selected arm: {selected_arm + 1}")

assert np.allclose(ucb_values, [1.14353355, 1.20608696], atol=1e-6), "UCB values incorrect"
assert selected_arm == 1, "Selected arm should be arm 2"

# Exercise 5: Verification Code t = 10 N = np.array([7, 3]) Q = np.array([0.57, 0.33]) c = 1.0 ucb_values = Q + c * np.sqrt(np.log(t) / N) selected_arm = np.argmax(ucb_values) print(f"UCB values: {ucb_values}") print(f"Selected arm: {selected_arm + 1}") assert np.allclose(ucb_values, [1.14353355, 1.20608696], atol=1e-6), "UCB values incorrect" assert selected_arm == 1, "Selected arm should be arm 2"

UCB values: [1.14353355 1.20608696]
Selected arm: 2

Exercise 6: MC vs TD Bias-Variance (Conceptual)¶

• Question: Given a 3-state MDP with known transition matrix, explain why: (a) MC estimate of $V(s)$ is unbiased but has high variance (b) TD(0) estimate of $V(s)$ is biased but has lower variance (c) What does TD's bias depend on?

Solution 6¶

(a) MC uses the full actual return $G_t$. Since $E[G_t] = V(s)$, it's unbiased. But $G_t$ accumulates randomness from many state transitions and rewards, leading to high variance. (b) TD(0) uses a bootstrapped target $R_{t+1} + \gamma V(S_{t+1})$. It only depends on one step of randomness, so variance is lower. It's biased because it relies on the current (likely incorrect) estimate of $V(S_{t+1})$. (c) TD's bias depends entirely on the accuracy of the current value estimate $V$ for subsequent states.

Exercise 7: PPO Clipped Objective (Hand Calculation)¶

Given: $\pi_{old}(a|s) = 0.3$, $\pi_{new}(a|s) = 0.5$, Advantage $A = 2.0$, clip_eps = 0.2

• Task: Compute $r(\theta) = \pi_{new}/\pi_{old}$, clipped ratio, unclipped objective, clipped objective, and final $L^{CLIP}$
• Also compute for negative advantage case: $A = -1.5$

Solution 7¶

Ratio: $r(\theta) = 0.5 / 0.3 = 1.6\overline{6}$, clipped to $[0.8, 1.2]$ gives $1.2$.

• $A = 2.0$: unclipped $= 1.667 \times 2.0 = 3.333$; clipped $= 1.2 \times 2.0 = 2.4$; $L^{CLIP} = \min(3.333, 2.4) = 2.4$
• $A = -1.5$: unclipped $= 1.667 \times (-1.5) = -2.5$; clipped $= 1.2 \times (-1.5) = -1.8$; $L^{CLIP} = \min(-2.5, -1.8) = -2.5$

The $\min$ keeps the more pessimistic value: gains from pushing the ratio beyond $1+\epsilon$ are capped, while penalties are not.

In [7]:

# Exercise 7: Verification Code
def ppo_clip(pi_new, pi_old, A, clip_eps=0.2):
    r = pi_new / pi_old
    clipped_r = np.clip(r, 1 - clip_eps, 1 + clip_eps)
    unclipped_obj = r * A
    clipped_obj = clipped_r * A
    L_clip = min(unclipped_obj, clipped_obj)
    return r, clipped_r, unclipped_obj, clipped_obj, L_clip

# Positive advantage
r1, cr1, uo1, co1, L1 = ppo_clip(0.5, 0.3, 2.0)
print(f"Positive A: r={r1:.3f}, clipped_r={cr1:.3f}, obj={uo1:.3f}, clipped_obj={co1:.3f}, L={L1:.3f}")
assert np.isclose(L1, 2.4), "L_clip for positive A incorrect"

# Negative advantage
r2, cr2, uo2, co2, L2 = ppo_clip(0.5, 0.3, -1.5)
print(f"Negative A: r={r2:.3f}, clipped_r={cr2:.3f}, obj={uo2:.3f}, clipped_obj={co2:.3f}, L={L2:.3f}")
assert np.isclose(L2, -2.5), "L_clip for negative A incorrect"

# Exercise 7: Verification Code def ppo_clip(pi_new, pi_old, A, clip_eps=0.2): r = pi_new / pi_old clipped_r = np.clip(r, 1 - clip_eps, 1 + clip_eps) unclipped_obj = r * A clipped_obj = clipped_r * A L_clip = min(unclipped_obj, clipped_obj) return r, clipped_r, unclipped_obj, clipped_obj, L_clip # Positive advantage r1, cr1, uo1, co1, L1 = ppo_clip(0.5, 0.3, 2.0) print(f"Positive A: r={r1:.3f}, clipped_r={cr1:.3f}, obj={uo1:.3f}, clipped_obj={co1:.3f}, L={L1:.3f}") assert np.isclose(L1, 2.4), "L_clip for positive A incorrect" # Negative advantage r2, cr2, uo2, co2, L2 = ppo_clip(0.5, 0.3, -1.5) print(f"Negative A: r={r2:.3f}, clipped_r={cr2:.3f}, obj={uo2:.3f}, clipped_obj={co2:.3f}, L={L2:.3f}") assert np.isclose(L2, -2.5), "L_clip for negative A incorrect"

Positive A: r=1.667, clipped_r=1.200, obj=3.333, clipped_obj=2.400, L=2.400
Negative A: r=1.667, clipped_r=1.200, obj=-2.500, clipped_obj=-1.800, L=-2.500

Exercise 8: Double DQN Update (Implementation)¶

• Task: Given Q_online and Q_target as numpy arrays, implement the Double DQN target computation: $y = r + \gamma \cdot Q_{target}[s', \arg\max_a Q_{online}[s', a]]$
• Compare with standard DQN target: $y = r + \gamma \cdot \max_a Q_{target}[s', a]$
• Show numerically that standard DQN overestimates when Q has noise

Solution 8¶

The Double DQN target selects the action with the online network but evaluates it with the target network. Pointwise, $\max_a Q_{target}[s',a] \ge Q_{target}[s', \arg\max_a Q_{online}[s',a]]$, so the standard DQN target is never below the Double DQN target; with independent noise on the two networks, its expectation exceeds the true value while Double DQN's stays nearly unbiased. A single noise draw is uninformative, so we average the comparison over many seeded trials below.

In [8]:

# Exercise 8: Verification Code
q_true = np.array([1.0, 1.0, 1.0])
r = 0.5
gamma = 0.9
y_true = r + gamma * np.max(q_true)  # 1.4, the noise-free target

# A single noise draw can go either way; the overestimation is a *systematic* effect,
# so we average the two targets over many trials drawn from the seeded first-cell rng.
n_trials = 50
y_dqn_trials = np.zeros(n_trials)
y_ddqn_trials = np.zeros(n_trials)
for trial in range(n_trials):
    noise_online = rng.normal(0, 0.5, 3)
    noise_target = rng.normal(0, 0.5, 3)
    q_online_next = q_true + noise_online
    q_target_next = q_true + noise_target

    # Standard DQN: max over the noisy target network
    y_dqn_trials[trial] = r + gamma * np.max(q_target_next)

    # Double DQN: select with online network, evaluate with target network
    best_action = np.argmax(q_online_next)
    y_ddqn_trials[trial] = r + gamma * q_target_next[best_action]

mean_dqn = y_dqn_trials.mean()
mean_ddqn = y_ddqn_trials.mean()
print(f"True target:              {y_true:.3f}")
print(f"Mean standard DQN target: {mean_dqn:.3f}  (bias {mean_dqn - y_true:+.3f})")
print(f"Mean Double DQN target:   {mean_ddqn:.3f}  (bias {mean_ddqn - y_true:+.3f})")
print(f"Mean overestimation gap:  {np.mean(y_dqn_trials - y_ddqn_trials):.4f}")

# Averaged over 50 trials the effect is systematic (measured: gap ~0.33, DQN bias ~+0.33,
# Double DQN bias ~+0.005), so these margins hold with room to spare.
assert np.mean(y_dqn_trials - y_ddqn_trials) > 0.1, "Standard DQN should systematically exceed Double DQN"
assert mean_dqn > y_true + 0.1, "Standard DQN should systematically overestimate the true target"
assert abs(mean_ddqn - y_true) < abs(mean_dqn - y_true), "Double DQN should be less biased than standard DQN"
print("All Double DQN assertions passed!")

# Exercise 8: Verification Code q_true = np.array([1.0, 1.0, 1.0]) r = 0.5 gamma = 0.9 y_true = r + gamma * np.max(q_true) # 1.4, the noise-free target # A single noise draw can go either way; the overestimation is a *systematic* effect, # so we average the two targets over many trials drawn from the seeded first-cell rng. n_trials = 50 y_dqn_trials = np.zeros(n_trials) y_ddqn_trials = np.zeros(n_trials) for trial in range(n_trials): noise_online = rng.normal(0, 0.5, 3) noise_target = rng.normal(0, 0.5, 3) q_online_next = q_true + noise_online q_target_next = q_true + noise_target # Standard DQN: max over the noisy target network y_dqn_trials[trial] = r + gamma * np.max(q_target_next) # Double DQN: select with online network, evaluate with target network best_action = np.argmax(q_online_next) y_ddqn_trials[trial] = r + gamma * q_target_next[best_action] mean_dqn = y_dqn_trials.mean() mean_ddqn = y_ddqn_trials.mean() print(f"True target: {y_true:.3f}") print(f"Mean standard DQN target: {mean_dqn:.3f} (bias {mean_dqn - y_true:+.3f})") print(f"Mean Double DQN target: {mean_ddqn:.3f} (bias {mean_ddqn - y_true:+.3f})") print(f"Mean overestimation gap: {np.mean(y_dqn_trials - y_ddqn_trials):.4f}") # Averaged over 50 trials the effect is systematic (measured: gap ~0.33, DQN bias ~+0.33, # Double DQN bias ~+0.005), so these margins hold with room to spare. assert np.mean(y_dqn_trials - y_ddqn_trials) > 0.1, "Standard DQN should systematically exceed Double DQN" assert mean_dqn > y_true + 0.1, "Standard DQN should systematically overestimate the true target" assert abs(mean_ddqn - y_true) < abs(mean_dqn - y_true), "Double DQN should be less biased than standard DQN" print("All Double DQN assertions passed!")

True target:              1.400
Mean standard DQN target: 1.734  (bias +0.334)
Mean Double DQN target:   1.405  (bias +0.005)
Mean overestimation gap:  0.3287
All Double DQN assertions passed!