Reinforcement Learning Foundations

Level: 5 (Mastery — cross-domain: math + coding + proof/build) Time limit: 90 minutes Total marks: 60

Notation: MDP $\langle S, A, P, R, \gamma\rangle$. Return $G_t=\sum_{k=0}^{\infty}\gamma^k R_{t+k+1}$. Value functions $v_\pi$, $q_\pi$; optimal $v_*$, $q_*$.

---

Question 1 — Contraction, convergence, and a numeric MDP (24 marks)

(a) Define the Bellman optimality operator $T$ on the space of value functions $\mathbb{R}^{|S|}$ by $(Tv)(s) = \max_{a\in A}\Big[ \textstyle\sum_{s'} P(s'\mid s,a)\big(R(s,a,s') + \gamma\, v(s')\big)\Big].$ Prove that $T$ is a $\gamma$-contraction in the sup-norm $\lVert\cdot\rVert_\infty$, i.e. $\lVert Tu - Tv\rVert_\infty \le \gamma\lVert u-v\rVert_\infty$. Hence state why value iteration converges to a unique fixed point. (8)

(b) Consider a 2-state MDP with states $\{A,B\}$, a single available action in each state (so the policy is fixed), $\gamma=0.9$, deterministic transitions and rewards:

• From $A$: go to $B$, reward $+5$.
• From $B$: go to $A$, reward $-1$.

Write the two linear Bellman evaluation equations for $v(A)$ and $v(B)$ and solve them exactly. (8)

(c) Starting from $v_0(A)=v_0(B)=0$, perform two synchronous value-iteration (here just policy-evaluation) sweeps and report $v_2(A), v_2(B)$. Using part (a), give an upper bound on $\lVert v_2 - v_*\rVert_\infty$ in terms of $\gamma$ and $\lVert v_1-v_0\rVert_\infty$, and check numerically that your bound holds. (8)

---

Question 2 — SARSA vs Q-learning: derive, code, and reason (22 marks)

(a) Write the update rules for tabular SARSA and Q-learning given a transition $(s,a,r,s',a')$. Explain precisely, with reference to the target term, why SARSA is on-policy and Q-learning is off-policy. (6)

(b) Implement a single agent step (in Python-like pseudocode) for an $\varepsilon$-greedy Q-learning agent, including action selection and the Q-update. Your code must be runnable logic (no hand-waving) using a dictionary/array Q. (8)

(c) A cliff-walking-style task has a shortcut path with high per-step reward but a risk of catastrophic penalty under exploration. Argue which of SARSA / Q-learning learns the safer path during training and which learns the optimal greedy path, and connect this to the exploration–exploitation tradeoff and the $\gamma$ discount. (8)

---

Question 3 — Monte Carlo vs Temporal Difference estimation (14 marks)

(a) Given the episode of rewards (single trajectory, $\gamma=0.5$): $R_1=2,\ R_2=0,\ R_3=-4,\ R_4=8,$ compute the return $G_0$ (from the first state). (6)

(b) Suppose current estimate $V(s_0)=1.0$, and after the first transition we observe $R_1=2$ and next state $s_1$ with $V(s_1)=3.0$. Compute the TD(0) target and the TD update to $V(s_0)$ with learning rate $\alpha=0.1$, $\gamma=0.5$. Contrast the bias/variance of the MC target (part a) vs this TD target in one or two sentences. (8)