Reinforcement Learning Foundations

Q1. (5 marks) — 1 mark each.

• (a) Agent: the decision-maker/learner that selects actions to maximise cumulative reward.
• (b) Environment: everything outside the agent; it responds to actions with new states and rewards.
• (c) State: a representation of the situation of the environment at a given time step, $s \in S$.
• (d) Action: a choice available to the agent, $a \in A$, that influences the environment.
• (e) Reward: a scalar feedback signal $R$ indicating the immediate value of the agent's action.

Why: these are the standard five primitives defining the agent–environment interaction loop.

Q2. (6 marks) — 1 mark per element (5) + 1 mark for Markov property.

• $S$: set of states (state space).
• $A$: set of actions (action space).
• $P$: transition probability, $P(s'\mid s,a)=\Pr[S_{t+1}=s'\mid S_t=s, A_t=a]$.
• $R$: reward function, expected reward $R(s,a)$ (or $R(s,a,s')$).
• $\gamma$: discount factor, $\gamma \in [0,1]$.
• Markov property: $\Pr[S_{t+1}\mid S_t, A_t] = \Pr[S_{t+1}\mid S_1,A_1,\dots,S_t,A_t]$ i.e. the next state depends only on the current state and action, not the full history.

Q3. (4 marks) Definition (1 mark): $G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \dots = \sum_{k=0}^{\infty}\gamma^k R_{t+k+1}$ Computation (3 marks): $G_t = 2 + 0.5(4) + 0.25(8) = 2 + 2 + 2 = 6$ Why: each future reward is weighted by an increasing power of $\gamma$, reflecting reduced value of delayed rewards. Answer: $G_t = 6$.

Q4. (5 marks) Bellman expectation equation (3 marks): $v_\pi(s) = \sum_{a}\pi(a\mid s)\sum_{s',r}P(s',r\mid s,a)\big[r + \gamma v_\pi(s')\big]$ Difference (2 marks):

• $v_\pi(s)$: expected return starting from state $s$ and following policy $\pi$.
• $q_\pi(s,a)$: expected return starting from state $s$, taking action $a$, then following $\pi$. Relation: $v_\pi(s)=\sum_a \pi(a\mid s)\,q_\pi(s,a)$.

Q5. (4 marks) Trade-off (2 marks): Exploitation uses current knowledge to pick the best-known action for immediate reward; exploration tries other actions to gain information that may yield higher long-term reward. The agent must balance the two.

Computation (2 marks): With $\epsilon=0.1$, $|A|=4$:

• (a) Greedy action: $P = (1-\epsilon) + \epsilon/|A| = 0.9 + 0.1/4 = 0.925$.
• (b) A specific non-greedy action: $P = \epsilon/|A| = 0.1/4 = 0.025$.

Check: $0.925 + 3(0.025) = 1.0$. ✓

Q6. (4 marks) — 2 marks per valid difference.

• MC updates only at the end of an episode using the full observed return $G_t$; TD updates every step using bootstrapping (an estimate of future value).
• MC requires complete episodes (episodic tasks); TD works online and in continuing tasks.
• (Alt.) MC has higher variance/no bias; TD has lower variance but introduces bias from bootstrapping.

Q7. (3 marks) $V(S_t) \leftarrow V(S_t) + \alpha\Big[\underbrace{R_{t+1}+\gamma V(S_{t+1})}_{\text{TD target}} - V(S_t)\Big]$

• TD error: $\delta_t = R_{t+1}+\gamma V(S_{t+1}) - V(S_t)$ (1 mark)
• Correct update form with $\alpha$ (1 mark), correct target labelled (1 mark).

Q8. (5 marks) SARSA (2 marks): $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]$ Q-learning (2 marks): $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]$ Classification (1 mark): SARSA is on-policy (uses the action $A_{t+1}$ actually taken); Q-learning is off-policy (uses the greedy $\max$ regardless of behaviour policy).

Q9. (4 marks) — 2 marks each.

• Policy iteration: alternates full policy evaluation (solve for $v_\pi$) and policy improvement (greedy update) until the policy is stable.
• Value iteration: applies the Bellman optimality update directly, effectively truncating evaluation to a single sweep per iteration; converges to $v_*$, then extracts the greedy policy.

[
  {"claim":"Q3 discounted return equals 6","code":"g=0.5; G=2+g*4+g**2*8; result=(G==6)"},
  {"claim":"Q5a epsilon-greedy greedy action prob equals 0.925","code":"eps=0.1; A=4; p=(1-eps)+eps/A; result=(abs(p-0.925)<1e-9)"},
  {"claim":"Q5b non-greedy action prob equals 0.025","code":"eps=0.1; A=4; p=eps/A; result=(abs(p-0.025)<1e-9)"},
  {"claim":"Q5 probabilities sum to 1","code":"eps=0.1; A=4; pg=(1-eps)+eps/A; pn=eps/A; total=pg+(A-1)*pn; result=(abs(total-1)<1e-9)"}
]