The full Deep Reinforcement Learning mid-semester (regular) paper, every question worked end-to-end — bandits (incremental Q, UCB, ε-greedy), MDPs & Bellman equations, value iteration, Monte-Carlo prediction, and returns. Questions are boxed; solutions are collapsible. The makeup-exam study guide lists the same concepts to revise.
Q1 — Bandits: incremental Q, UCB, ε-greedy 2 + 2 + 2 marks
A food app recommends one of R1, R2, R3 per session (reward +1 if an order is placed, else 0). History (7 sessions): R1✓1, R2✗0, R3✓1, R1✓1, R2✓1, R3✗0, R2✓1. (a) Use incremental averaging to compute Q(R1), Q(R2), Q(R3). (b) Apply UCB with c=2 to pick the action at session 8. (c) With ε-greedy (ε=0.3), compute the probability of selecting each restaurant at session 8.
Show worked solution
(a) Incremental averaging \(Q_{n+1}=Q_n+\frac1n (R-Q_n)\).
- R1: rewards {1,1} → \(Q(R1)=\) 1.0 (n=2).
- R2: {0,1,1} → 0 → 0.5 → \(0.5+\tfrac13(1-0.5)=\) 0.667 (n=3).
- R3: {1,0} → \(Q(R3)=\) 0.5 (n=2).
(b) UCB, \(a=\arg\max\big[Q(a)+c\sqrt{\ln t / n_a}\big]\), total pulls = 7 so \(t=8\), \(\ln 8 = 2.079\).
| Arm | Q | n | bonus = 2·√(ln8/n) | UCB |
|---|---|---|---|---|
| R1 | 1.0 | 2 | 2·√(1.040)=2.039 | 3.039 |
| R2 | 0.667 | 3 | 2·√(0.693)=1.665 | 2.332 |
| R3 | 0.5 | 2 | 2.039 | 2.539 |
Highest UCB → select R1 at session 8.
(c) ε-greedy, ε=0.3, K=3 arms. Greedy arm = R1 (highest Q). \(P(\text{greedy}) = 1-\varepsilon+\varepsilon/K = 0.7+0.1 = 0.8\); others \(\varepsilon/K = 0.1\).
Q2 — Triage MDP & Bellman equations 2 + 2 + 2 marks
A triage agent chooses to (1) Admit or (2) Observe. Admit → recover (0.8, +10) or deteriorate (0.2, −5). Observe → discharge (0.6, +3) or still-needs-admission (0.4, +2 then the same admission transition). (a) Formally define the MDP (states, actions, transitions, rewards; draw the diagram). (b) Write the Bellman optimality equations with γ=0.9. (c) Effect of changing the deterioration reward from −5 to 0?
Show worked solution
(a) MDP. States: S = patient awaiting decision (non-terminal); terminal states {Recovered, Deteriorated, Discharged}; an intermediate “needs-admission” outcome of Observe that leads back into the admission transition. Actions: {Admit, Observe}. Transitions/rewards:
| State | Action | Outcome (prob, reward) |
|---|---|---|
| S | Admit | Recover (0.8, +10) · Deteriorate (0.2, −5) |
| S | Observe | Discharge (0.6, +3) · Needs-admission (0.4, +2) → then admission transition |
Diagram: S →(Admit)→ {Recover, Deteriorate}; S →(Observe)→ {Discharge, Needs-admission →(Admit)→ Recover/Deteriorate}.
(b) Bellman optimality, γ=0.9, terminal V=0. Let \(V_{adm}=0.8(10)+0.2(-5)=7\) (value of admitting).
\(Q(S,\text{Observe}) = 0.6(3) + 0.4\big(2 + 0.9\,V_{adm}\big) = 1.8 + 0.4(2+6.3) = 1.8 + 3.32 = 5.12\)
\(V^*(S) = \max(7,\ 5.12) = \) 7 ⟹ optimal action = Admit
(c) Deterioration reward −5 → 0. Now \(Q(S,\text{Admit}) = 0.8(10)+0.2(0) = 8\) (up from 7); \(V_{adm}=8\) so Observe rises to \(1.8+0.4(2+0.9·8)=5.48\). Admit (8) still dominates and is now even more attractive — removing the downside penalty makes immediate admission risk-free, so the agent admits more readily / more confidently.
Q3 — Value iteration (recycling robot) 4 + 2 marks
States H, M, L; actions Search/Wait; γ=0.9. Dynamics: H-Search→H(0.7,+3)/M(0.3,−2); H-Wait→H(1.0,+1); M-Search→H(0.4,+2)/L(0.6,−2); M-Wait→M(1.0,0); L-Search→H(0.3,+4)/L(0.7,−3); L-Wait→L(1.0,−1). (a) Do 1 iteration of synchronous value iteration from \(V_0=0\); show the table. (b) Derive the optimal policy after iteration 1; what happens if γ → 0.1?
Show worked solution
(a) With \(V_0=0\), the discounted-future term is 0, so \(Q_1 = \sum P\cdot r\).
| State | Q₁(·,Search) | Q₁(·,Wait) | V₁ = max | arg max |
|---|---|---|---|---|
| H | 0.7(3)+0.3(−2)=1.5 | 1.0(1)=1.0 | 1.5 | Search |
| M | 0.4(2)+0.6(−2)=−0.4 | 1.0(0)=0 | 0 | Wait |
| L | 0.3(4)+0.7(−3)=−0.9 | 1.0(−1)=−1.0 | −0.9 | Search |
(b) Policy after iteration 1: H → Search, M → Wait, L → Search.
If γ → 0.1: at iteration 1 the values are identical (the future term multiplies \(V_0=0\)), so the iteration-1 policy is unchanged. But over full convergence a small γ makes the agent myopic — it weights immediate reward heavily and discounts the future benefit of reaching High via Search, so it tends to prefer Wait in more states (the negative immediate rewards of Search are no longer offset by future gains).
Q4 — Monte-Carlo prediction (self-driving) 2 + 2 + 2 marks
Two states S1, S2; γ=0.8. Episodes:
E1: S1,A1,−10, S2,A2,−20, S1,A3,−30, T
E2: S1,A2,−15, S2,A1,−25, T
E3: S1,A3,−5, S2,A2,−10, S1,A1,−20, S2,A3,−30, T
Compute MC estimates of V(s) by (a) First-Visit and (b) Every-Visit. (c) Why is Dynamic Programming unsuitable here?
Show worked solution
Compute returns \(G_t = r_{t+1} + \gamma G_{t+1}\) backward (γ=0.8).
E1: G(S1@t0)=−45.2, G(S2@t1)=−44, G(S1@t2)=−30.
E2: G(S1@t0)=−35, G(S2@t1)=−25.
E3: G(S1@t0)=−41.16, G(S2@t1)=−45.2, G(S1@t2)=−44, G(S2@t3)=−30.
(a) First-Visit (first occurrence per episode):
V(S2) = (−44 − 25 − 45.2)/3 = −114.2/3 = −38.07
(b) Every-Visit (all occurrences):
V(S2) = (−44 −25 −45.2 −30)/4 = −144.2/4 = −36.05
(c) Why not DP? Dynamic programming needs a full model of the environment — the transition probabilities \(P(s'\mid s,a)\) and reward function. Here the car only has sampled sensor interactions; the dynamics are unknown, stochastic, and the state space is huge/continuous, so DP is infeasible. Monte-Carlo is model-free and learns V(s) directly from sample episodes.
Q5 — Returns, bandit-vs-MDP, PI vs VI 2 + 2 + 2 marks
(a) γ=0.8, rewards R1=3, R2=−1, R3=5, R4=2, R5=4, R6=1, terminal T=6. Compute G₀…G₆. (b) A drone must land on a moving ship with stochastic, unknown motion: (i) is this a Multi-Armed Bandit? (ii) if not, what RL framework fits? (c) Compare Policy Iteration and Value Iteration on convergence speed and cost per iteration.
Show worked solution
(a) Returns \(G_t = R_{t+1} + 0.8\,G_{t+1}\), \(G_6 = 0\):
| t | G_t |
|---|---|
| G₆ | 0 |
| G₅ | 1 |
| G₄ | 4 + 0.8(1) = 4.8 |
| G₃ | 2 + 0.8(4.8) = 5.84 |
| G₂ | 5 + 0.8(5.84) = 9.672 |
| G₁ | −1 + 0.8(9.672) = 6.738 |
| G₀ | 3 + 0.8(6.738) = 8.39 |
(b) (i) No — a Multi-Armed Bandit is stateless: each pull is independent and actions don’t change a state. Here the drone–ship relative position is a state that evolves and actions affect future states, with delayed reward. (ii) Model it as a (PO)MDP and use model-free RL (Q-learning / policy-gradient); since the ship’s motion is unobserved/unknown it’s really a POMDP, justifying a recurrent/belief-state policy.
(c) Policy Iteration vs Value Iteration.
| Dimension | Policy Iteration | Value Iteration |
|---|---|---|
| Convergence speed (iterations) | Fewer iterations — each step fully evaluates then improves the policy, so it converges in few outer loops. | More iterations — improves the value a little each sweep. |
| Cost per iteration | More expensive — full policy evaluation (solve/iterate a linear system) each round. | Cheaper — a single Bellman backup per state. |
Makeup exam — what to study study guide
The makeup paper tests the same concepts with new numbers. Drill the methods below.
| Concept (revise this) | Tested in | What to be able to do |
|---|---|---|
| Bandits: incremental Q, UCB, ε-greedy | Q1 | Update Q incrementally; compute UCB with the exploration bonus; get ε-greedy selection probabilities. |
| MDP formalism & Bellman optimality | Q2 | Define states/actions/transitions/rewards; write & evaluate Bellman optimality equations; reason about reward changes. |
| Value iteration & policy extraction | Q3 | Run synchronous VI tables; extract the greedy policy; explain the effect of the discount γ. |
| Monte-Carlo prediction | Q4 | Compute returns; do First-Visit vs Every-Visit V(s); explain model-free vs DP (model-based). |
| Returns & discounting | Q5a | Compute \(G_t\) recursively from a reward sequence. |
| Problem framing (bandit vs MDP/POMDP) | Q5b | Decide stateless bandit vs stateful MDP/POMDP and justify. |
| Policy vs Value Iteration | Q5c | Compare on convergence speed and per-iteration cost. |