Reinforcement Learning Foundations

Level 3 — Production (from-scratch derivations, code-from-memory, explain-out-loud) Time limit: 45 minutes Total marks: 60

Answer all questions. Show all working. Where code is requested, pseudo-code with correct update rules and control flow is acceptable but must be self-consistent.

---

Question 1 — Bellman equations from scratch (12 marks)

(a) Starting from the definition of the return $G_t = \sum_{k=0}^{\infty}\gamma^k R_{t+k+1}$, derive the Bellman expectation equation for the state-value function $v_\pi(s)$ in terms of $v_\pi(s')$. State every assumption you use. (5)

(b) Write the Bellman expectation equation for the action-value function $q_\pi(s,a)$, and show how $v_\pi(s)$ and $q_\pi(s,a)$ are related to each other (both directions). (4)

(c) Write the Bellman optimality equation for $v_*(s)$ and explain in one sentence why it is nonlinear whereas the expectation equation is linear. (3)

---

Question 2 — Solving a 2-state MDP by hand (12 marks)

An MDP has two states $\{A, B\}$ and a single action available in each state (so the policy is fixed). Dynamics and rewards are deterministic:

• From $A$: reward $+2$, transition to $B$.
• From $B$: reward $+1$, transition to $A$.

Use discount factor $\gamma = 0.9$.

(a) Write the two linear Bellman equations for $v(A)$ and $v(B)$. (3)

(b) Solve them exactly for $v(A)$ and $v(B)$. (6)

(c) Verify your answer for $v(A)$ by directly summing the infinite discounted return of the reward sequence generated from $A$. (3)

---

Question 3 — Value iteration, coded from memory (10 marks)

(a) Write pseudo-code for the value iteration algorithm for a finite MDP with known $P$ and $R$, including the stopping criterion and how the greedy policy is extracted at the end. (7)

(b) State the computational cost per sweep in terms of $|S|$, $|A|$ and explain why value iteration converges (name the property). (3)

---

Question 4 — TD, SARSA, Q-learning contrast (12 marks)

(a) Write the TD(0) update for $V(s)$ and define the TD error $\delta_t$. (3)

(b) Write the SARSA and Q-learning update rules for $Q(s,a)$ side by side, and clearly mark which term differs between them. (4)

(c) Explain out loud (in words) why SARSA is called on-policy and Q-learning off-policy, and describe one behavioural consequence on the classic cliff-walking task. (5)

---

Question 5 — Exploration and $\epsilon$-greedy (8 marks)

(a) Define the $\epsilon$-greedy policy formally: give the probability of selecting the greedy action and of selecting any specific non-greedy action, for $|A|$ actions. (3)

(b) With $\epsilon = 0.1$ and $|A| = 4$, compute the probability of taking the greedy action and the probability of taking one particular non-greedy action. (3)

(c) Give one advantage of decaying $\epsilon$ over training, in terms of the exploration–exploitation tradeoff. (2)

---

Question 6 — Monte Carlo return and TD target (6 marks)

An agent observes this single episode ($\gamma = 0.5$), terminating after the last reward:

$S_0 \xrightarrow{R_1=1} S_1 \xrightarrow{R_2=0} S_2 \xrightarrow{R_3=4} \text{terminal}$

(a) Compute the Monte Carlo return $G_0$. (3)

(b) If the current estimate is $V(S_1) = 3$, compute the TD(0) target for updating $V(S_0)$ using $R_1$ and $V(S_1)$. (3)

---