Level 4 — ApplicationReinforcement Learning Foundations

Reinforcement Learning Foundations

⏱ 60 minutes60 marksprintable — key stays hidden on paper

Level: 4 — Application (novel problems, no hints) Time limit: 60 minutes Total marks: 60

Answer all questions. Show full working. Use $\gamma$ for the discount factor. State any assumptions.

Question 1 — Returns and the Discount Factor (10 marks)

A robot receives the infinite reward sequence starting at $t=0$ :

$r_0=2,\quad r_1=2,\quad r_2=2,\ \dots \quad \text{(constant reward } 2 \text{ forever)}$

except that at exactly one step $t=3$ it receives a one-time penalty making $r_3 = -6$ (all other rewards are $2$ ).

(a) Write the general formula for the discounted return $G_0$ and compute it symbolically as a function of $\gamma$ . (6)

(b) Evaluate $G_0$ for $\gamma = 0.9$ . (2)

(c) A colleague claims "with $\gamma=0$ the agent is myopic." State $G_0$ for $\gamma=0$ and explain in one sentence what behaviour this induces. (2)

Question 2 — Modelling as an MDP (12 marks)

A vending machine restocks a single product. Each morning the stock level is $s\in\{0,1,2\}$ units. The manager chooses action $a\in\{\text{order},\ \text{wait}\}$ . "Order" adds 1 unit (capped at 2) with reward $-1$ (cost). During the day, demand consumes 1 unit with probability $0.7$ and 0 units with probability $0.3$ ; each unit sold gives reward $+3$ . A stockout (demand arrives at stock 0) gives reward $-2$ .

(a) Identify the state set, action set, and the discount interpretation appropriate for an ongoing daily process. (3)

(b) For state $s=1$ , action $\text{wait}$ , write the full transition-and-reward distribution: list each next state $s'$ , its probability, and the immediate reward. (5)

(c) Explain why the Markov property holds for this formulation, and give one realistic feature of the real machine whose inclusion would break it. (4)

Question 3 — Bellman Evaluation by Hand (14 marks)

Consider a 2-state MDP with states $A, B$ and a fixed policy $\pi$ . Under $\pi$ :

From $A$ : reward $+1$ , then go to $B$ with prob $1$ .
From $B$ : reward $+4$ , then go to $A$ with prob $0.5$ and stay in $B$ with prob $0.5$ .

Use $\gamma = 0.5$ .

(a) Write the two Bellman expectation equations for $V^\pi(A)$ and $V^\pi(B)$ . (4)

(b) Solve the linear system exactly for $V^\pi(A)$ and $V^\pi(B)$ . (8)

(c) Using your results, compute the action-value-style one-step consistency check: verify that $V^\pi(A) = 1 + \gamma V^\pi(B)$ . (2)

Question 4 — TD, SARSA vs Q-learning Update (14 marks)

An agent uses learning rate $\alpha = 0.5$ , $\gamma = 0.9$ . Current estimates:

$Q(s,a_1)=2,\quad Q(s,a_2)=5,\quad Q(s',a_1)=10,\quad Q(s',a_2)=6.$

The agent is in $s$ , takes $a_1$ , receives reward $r=3$ , and lands in $s'$ . Its behaviour policy is $\epsilon$ -greedy; on the next step it happens to select $a_2$ in $s'$ .

(a) Compute the updated $Q(s,a_1)$ under the SARSA rule. Show the TD target and TD error. (5)

(b) Compute the updated $Q(s,a_1)$ under the Q-learning rule. Show the TD target and TD error. (5)

(c) Explain precisely why the two results differ here, and state which one is on-policy. (4)

Question 5 — Exploration and Policy Design (10 marks)

An agent uses $\epsilon$ -greedy action selection over $|\mathcal{A}|=4$ actions.

(a) With $\epsilon = 0.2$ , and a unique greedy action, give the probability of selecting the greedy action and the probability of selecting each specific non-greedy action. (4)

(b) The designer uses a decay schedule $\epsilon_k = \tfrac{1}{1+k}$ for episode $k=0,1,2,\dots$ . Compute $\epsilon_0, \epsilon_1, \epsilon_9$ , and explain in one sentence why decaying $\epsilon$ supports convergence to a near-optimal policy. (4)

(c) State one situation where pure greedy ( $\epsilon=0$ ) from the start would fail, referencing the exploration–exploitation tradeoff. (2)

Answer keyMark scheme & solutions

Question 1 (10 marks)

(a) Definition $G_0=\sum_{t=0}^\infty \gamma^t r_t$ . (1) All rewards are $2$ except $r_3=-6$ , i.e. the actual value differs from an all-2 stream by $(-6-2)=-8$ at $t=3$ .

$G_0 = \underbrace{\sum_{t=0}^\infty \gamma^t\cdot 2}_{\text{all-2 stream}} + \gamma^3(-8)$

The all-2 geometric series $=\dfrac{2}{1-\gamma}$ (converges for $|\gamma|<1$ ). (3)

$\boxed{G_0 = \frac{2}{1-\gamma} - 8\gamma^3}$ (2) (correct assembly)

(b) $\gamma=0.9$ : $\dfrac{2}{0.1} - 8(0.729) = 20 - 5.832 = 14.168$ . (2)

(c) $\gamma=0$ : only $r_0$ counts, $G_0 = 2$ . The agent maximises immediate reward only, ignoring all future consequences. (2)

Question 2 (12 marks)

(a) States $\mathcal S=\{0,1,2\}$ ; actions $\mathcal A=\{\text{order},\text{wait}\}$ . For an ongoing (continuing, non-terminating) process a discount factor $0<\gamma<1$ is appropriate to keep returns finite and weight nearer days more. (3)

(b) State $s=1$ , action wait (no ordering cost). Demand $=1$ w.p. $0.7$ → sells one unit (reward $+3$ ), stock $\to 0$ . Demand $=0$ w.p. $0.3$ → no sale (reward $0$ ), stock stays $1$ .

$s'$	prob	reward
$0$	$0.7$	$+3$
$1$	$0.3$	$0$

No stockout possible since stock $\ge$ demand. (5) (2 for probabilities, 2 for rewards, 1 for correct next states)

(c) Markov property holds because next state and reward depend only on current stock and action, not on the history of previous days' demand. (2) A realistic breaker: demand that depends on recent sales history / day-of-week seasonality (a hidden trend), making the true state incomplete. (2)

Question 3 (14 marks)

(a) Bellman expectation equations, $\gamma=0.5$ : (4)

$V(A) = 1 + \gamma\,V(B)$ $V(B) = 4 + \gamma\big(0.5\,V(A) + 0.5\,V(B)\big)$

(b) Substitute $\gamma=0.5$ :

$V(A) = 1 + 0.5\,V(B)$
$V(B) = 4 + 0.5(0.5 V(A) + 0.5 V(B)) = 4 + 0.25 V(A) + 0.25 V(B)$

From second: $0.75 V(B) = 4 + 0.25 V(A) \Rightarrow V(B) = \tfrac{16}{3} + \tfrac13 V(A)$ . (3)

Substitute into first: $V(A) = 1 + 0.5\left(\tfrac{16}{3} + \tfrac13 V(A)\right) = 1 + \tfrac{8}{3} + \tfrac16 V(A).$ $V(A) - \tfrac16 V(A) = \tfrac{11}{3} \Rightarrow \tfrac56 V(A) = \tfrac{11}{3}.$ $V(A) = \tfrac{11}{3}\cdot\tfrac65 = \tfrac{66}{15} = \tfrac{22}{5} = 4.4.$ (3)

Then $V(B) = \tfrac{16}{3} + \tfrac13(4.4) = 5.3333 + 1.4667 = 6.8$ . (2)

$\boxed{V(A)=4.4,\quad V(B)=6.8}$

(c) Check: $1 + 0.5(6.8) = 1 + 3.4 = 4.4 = V(A)$ . ✓ (2)

Question 4 (14 marks)

$\alpha=0.5$ , $\gamma=0.9$ , took $a_1$ in $s$ , $r=3$ , next action chosen $a_2$ in $s'$ .

(a) SARSA (uses the actually-chosen next action $a_2$ ):

TD target $= r + \gamma Q(s',a_2) = 3 + 0.9(6) = 3 + 5.4 = 8.4$ . (2)
TD error $\delta = 8.4 - Q(s,a_1) = 8.4 - 2 = 6.4$ . (1)
Update: $Q(s,a_1) \leftarrow 2 + 0.5(6.4) = 2 + 3.2 = 5.2$ . (2)

(b) Q-learning (uses $\max_{a'}Q(s',a')=\max(10,6)=10$ ):

TD target $= 3 + 0.9(10) = 3 + 9 = 12$ . (2)
TD error $\delta = 12 - 2 = 10$ . (1)
Update: $Q(s,a_1) \leftarrow 2 + 0.5(10) = 2 + 5 = 7$ . (2)

(c) They differ because SARSA bootstraps on the action actually taken ( $a_2$ , value 6), while Q-learning bootstraps on the greedy/max action ( $a_1$ , value 10). Since $a_2$ was not greedy in $s'$ , the targets differ ( $8.4$ vs $12$ ). SARSA is on-policy (it evaluates the behaviour policy); Q-learning is off-policy. (4)

Question 5 (10 marks)

(a) Greedy action prob $= 1-\epsilon + \epsilon/|\mathcal A| = 0.8 + 0.2/4 = 0.8 + 0.05 = 0.85$ . (2) Each specific non-greedy action prob $= \epsilon/|\mathcal A| = 0.2/4 = 0.05$ . (2) (Check: $0.85 + 3(0.05) = 1.$ )

(b) $\epsilon_0 = 1/(1+0)=1$ ; $\epsilon_1 = 1/2 = 0.5$ ; $\epsilon_9 = 1/10 = 0.1$ . (3) Early large $\epsilon$ ensures broad exploration of all state-actions (needed for value estimates to be accurate), while shrinking $\epsilon$ lets the agent increasingly exploit its improved estimates, approaching the greedy optimal policy. (1)

(c) With $\epsilon=0$ from the start, the agent commits to whatever action first looked best (possibly by chance/initialisation) and never tries alternatives, so it can get stuck in a suboptimal action having never explored the truly best one — pure exploitation with no exploration. (2)

[
  {"claim":"Q1b return equals 14.168 for gamma=0.9","code":"g=Rational(9,10); G=2/(1-g)-8*g**3; result=(G==Rational(14168,1000))"},
  {"claim":"Q3 solution V(A)=4.4 V(B)=6.8 satisfies Bellman eqs with gamma=0.5","code":"VA,VB=symbols('VA VB'); sol=solve([VA-(1+Rational(1,2)*VB), VB-(4+Rational(1,2)*(Rational(1,2)*VA+Rational(1,2)*VB))],[VA,VB]); result=(sol[VA]==Rational(22,5) and sol[VB]==Rational(34,5))"},
  {"claim":"Q4a SARSA update gives 5.2","code":"a=Rational(1,2); g=Rational(9,10); target=3+g*6; q=2+a*(target-2); result=(q==Rational(52,10))"},
  {"claim":"Q4b Q-learning update gives 7","code":"a=Rational(1,2); g=Rational(9,10); target=3+g*Max(10,6); q=2+a*(target-2); result=(q==7)"},
  {"claim":"Q5a epsilon-greedy probs sum to 1 with eps=0.2,4 actions","code":"eps=Rational(2,10); n=4; pg=1-eps+eps/n; po=eps/n; result=(pg==Rational(85,100) and po==Rational(5,100) and pg+3*po==1)"}
]