Interleaved — Phase 5

AI-ML interleaved practice

printable — key stays hidden on paper

Instructions: Work each problem independently. These deliberately mix RL fundamentals with deep RL algorithms in random order — part of your task is deciding which framework or update rule applies before computing. Show all reasoning. Total: 50 marks.

Problem 1. (5 marks) An agent in a 2-state MDP is in state $s$ . The immediate reward for the next step is $R_1 = 2$ , then $R_2 = 3$ , then $R_3 = 1$ , and every reward thereafter is $0$ . With discount factor $\gamma = 0.9$ , compute the return $G_0$ observed from the start of this trajectory.

Problem 2. (5 marks) You observe the following single transition: state $s$ , action $a$ , reward $r = 5$ , next state $s'$ . Current estimates are $Q(s,a) = 10$ , and for $s'$ the values are $Q(s', a_1) = 8$ , $Q(s', a_2) = 12$ . The agent's policy at $s'$ actually selected $a_1$ . Using $\alpha = 0.5$ , $\gamma = 1.0$ : (a) Compute the Q-learning update for $Q(s,a)$ . (b) Compute the SARSA update for $Q(s,a)$ . (c) State the one conceptual reason the two answers differ.

Problem 3. (5 marks) An $\epsilon$ -greedy policy over 4 actions uses $\epsilon = 0.2$ . The greedy action is $a^\*$ . Give the probability of selecting $a^\*$ and the probability of selecting any one specific non-greedy action.

Problem 4. (6 marks) A 3-state MDP has a fixed policy $\pi$ . Under $\pi$ the dynamics give deterministic transitions: $s_1 \to s_2$ (reward 0), $s_2 \to s_3$ (reward 0), $s_3 \to s_3$ (reward 1, absorbing self-loop). Discount $\gamma = 0.5$ . Using the Bellman expectation equation, compute $V^\pi(s_1)$ , $V^\pi(s_2)$ , $V^\pi(s_3)$ .

Problem 5. (5 marks) For a stochastic policy, an episode gives return $G = 4$ following action $a$ taken in state $s$ , where $\pi_\theta(a|s) = 0.25$ . In the REINFORCE update, the parameter step is $\theta \leftarrow \theta + \alpha\, G\, \nabla_\theta \ln \pi_\theta(a|s)$ . If $\nabla_\theta \ln \pi_\theta(a|s) = 3$ and $\alpha = 0.1$ , compute the size of the update $\Delta\theta$ . Why do we use $\ln \pi$ rather than $\pi$ ?

Problem 6. (5 marks) Explain concisely why Double DQN was introduced over vanilla DQN. Write the target used in vanilla DQN and the target used in Double DQN, clearly showing which network selects and which evaluates the action.

Problem 7. (6 marks) Monte Carlo prediction: three episodes visit state $s$ once each, producing returns $G = \{6, 2, 10\}$ . (a) Give the first-visit MC estimate of $V(s)$ . (b) A new episode gives return $G = 4$ . Update $V(s)$ using the incremental MC rule $V(s) \leftarrow V(s) + \alpha (G - V(s))$ with $\alpha = 0.1$ starting from your answer in (a). (c) State one reason to prefer TD(0) over MC here.

Problem 8. (4 marks) Match each algorithm to the property that distinguishes it: (i) SARSA, (ii) Q-learning, (iii) A2C, (iv) SAC — against — (A) off-policy, maximizes reward plus an entropy term; (B) on-policy TD control; (C) off-policy control using the max over next-state values; (D) on-policy actor-critic using an advantage estimate.

Problem 9. (5 marks) In experience replay with a target network, explain: (a) what problem experience replay solves, and (b) what problem the separate target network solves. State how often the target network parameters are typically updated relative to the online network.

Problem 10. (4 marks) PPO uses a clipped surrogate objective. Given the probability ratio $r_t(\theta) = \frac{\pi_\theta(a_t|s_t)}{\pi_{\theta_{old}}(a_t|s_t)} = 1.4$ , advantage $\hat{A}_t = +2$ , and clip parameter $\epsilon = 0.2$ , compute the value of the clipped term $\min\big(r_t \hat{A}_t,\ \text{clip}(r_t, 1-\epsilon, 1+\epsilon)\hat{A}_t\big)$ .

Answer keyMark scheme & solutions

Problem 1 — Subtopic 5.1.6 (Discount factor & returns). $G_0 = R_1 + \gamma R_2 + \gamma^2 R_3 = 2 + 0.9(3) + 0.81(1) = 2 + 2.7 + 0.81 = \boxed{5.51}$ . Why this method: a pure return computation — no bootstrapping, just geometric discounting of a finite reward sequence.

Problem 2 — Subtopics 5.1.13 (Q-learning) vs 5.1.12 (SARSA). (a) Q-learning target $= r + \gamma \max_{a'} Q(s',a') = 5 + 1.0(12) = 17$ . Update: $Q \leftarrow 10 + 0.5(17 - 10) = 10 + 3.5 = \boxed{13.5}$ . (b) SARSA uses the actual next action $a_1$ : target $= 5 + 1.0(8) = 13$ . Update: $Q \leftarrow 10 + 0.5(13 - 10) = 10 + 1.5 = \boxed{11.5}$ . (c) Q-learning is off-policy (uses $\max$ , the greedy target), SARSA is on-policy (uses the action the behavior policy actually took). The choice hinges on spotting "policy actually selected $a_1$ " → SARSA must use it.

Problem 3 — Subtopic 5.1.8 (ε-greedy). $P(a^\*) = 1 - \epsilon + \epsilon/4 = 0.8 + 0.05 = \boxed{0.85}$ . Each non-greedy action: $\epsilon/4 = 0.2/4 = \boxed{0.05}$ . Check: $0.85 + 3(0.05) = 1.0$ . ✓ Why: standard ε-greedy split — greedy gets the leftover mass plus its share of exploration.

Problem 4 — Subtopics 5.1.5 (Bellman) + 5.1.3/5.1.4 (value functions). Work backward from absorbing state. $V(s_3) = 1 + \gamma V(s_3) \Rightarrow V(s_3)(1-0.5) = 1 \Rightarrow V(s_3) = 2$ . $V(s_2) = 0 + 0.5 \cdot V(s_3) = 0.5(2) = 1$ . $V(s_1) = 0 + 0.5 \cdot V(s_2) = 0.5(1) = 0.5$ . $\boxed{V(s_1)=0.5,\ V(s_2)=1,\ V(s_3)=2}$ . Why: deterministic policy → Bellman expectation collapses to a chain; solve the self-loop first as a geometric fixed point.

Problem 5 — Subtopic 5.2.6 (REINFORCE). $\Delta\theta = \alpha\, G\, \nabla_\theta \ln \pi = 0.1 \times 4 \times 3 = \boxed{1.2}$ . Log used because $\nabla \ln \pi = \nabla\pi / \pi$ ; the log-derivative (score function) trick turns the policy-gradient expectation into a sample-averageable form $\mathbb{E}[G\nabla\ln\pi]$ , and dividing by $\pi$ correctly weights actions inversely to their sampling probability.

Problem 6 — Subtopic 5.2.4 (Double DQN). Vanilla DQN overestimates values because the same network both selects and evaluates the max action, and $\max$ over noisy estimates is biased upward. Vanilla target: $y = r + \gamma \max_{a'} Q_{\theta^-}(s',a')$ . Double DQN target: $y = r + \gamma\, Q_{\theta^-}\!\big(s',\ \arg\max_{a'} Q_{\theta}(s',a')\big)$ — the online net $\theta$ selects the action, the target net $\theta^-$ evaluates it, decoupling selection from evaluation to reduce overestimation bias.

Problem 7 — Subtopic 5.1.10 (Monte Carlo), contrasted with 5.1.11 (TD). (a) $V(s) = (6 + 2 + 10)/3 = 18/3 = \boxed{6}$ . (b) $V \leftarrow 6 + 0.1(4 - 6) = 6 - 0.2 = \boxed{5.8}$ . (c) TD(0) bootstraps, so it can update online per-step (no need to wait for episode end) and typically has lower variance than MC (which needs full returns).

Problem 8 — Subtopics 5.1.12, 5.1.13, 5.2.8, 5.2.11. (i) SARSA → (B) on-policy TD control. (ii) Q-learning → (C) off-policy, max over next values. (iii) A2C → (D) on-policy actor-critic with advantage. (iv) SAC → (A) off-policy with entropy-augmented objective.

Problem 9 — Subtopics 5.2.2 (replay) + 5.2.3 (target networks). (a) Experience replay breaks the temporal correlation between consecutive samples (and reuses data), giving more i.i.d.-like minibatches and better sample efficiency. (b) The target network provides a stationary/fixed target for a number of steps, preventing the moving-target instability where the network chases its own rapidly changing predictions. Update cadence: target net is updated to the online net's weights periodically (every $C$ steps, e.g. every few thousand) or via slow Polyak averaging.

Problem 10 — Subtopic 5.2.9 (PPO). Since $\hat{A}_t = +2 > 0$ , clip caps the ratio at $1+\epsilon = 1.2$ . Unclipped: $r_t \hat{A}_t = 1.4 \times 2 = 2.8$ . Clipped: $\text{clip}(1.4, 0.8, 1.2)\cdot 2 = 1.2 \times 2 = 2.4$ . $\min(2.8, 2.4) = \boxed{2.4}$ . Why: the clip removes incentive to push the ratio beyond $1.2$ for a positive advantage, limiting destructive policy updates.

[
  {"claim":"P1 return G0 = 5.51",
   "code":"G = 2 + 0.9*3 + 0.9**2*1\nresult = abs(G - 5.51) < 1e-9"},
  {"claim":"P2 Q-learning update gives 13.5 and SARSA gives 11.5",
   "code":"ql = 10 + 0.5*((5 + 1.0*12) - 10)\nsa = 10 + 0.5*((5 + 1.0*8) - 10)\nresult = (ql == 13.5) and (sa == 11.5)"},
  {"claim":"P10 PPO clipped term equals 2.4",
   "code":"r=1.4; A=2; eps=0.2\nclip = min(max(r,1-eps),1+eps)\nval = min(r*A, clip*A)\nresult = abs(val - 2.4) < 1e-9"}
]