A1. max and argmax [2 points]
For actions left, right and wait, Q values are (-5,-2,-4). Which statement is correct?
Midterm Practice Paper
Stochastic transitions, negative values and batch versus online learning
120 minutes100 points21 questions
Original practice material based on the supplied lecture notes and photographed revision priorities. This is not an official examination or a prediction of the actual questions.
Instructions
Closed-book except for two double-sided sheets of notes. A standalone calculation-only calculator is permitted. Answer all questions. Each single-choice question has exactly one correct answer. Show your working for calculations. Equivalent formulas and exact fractions are acceptable; otherwise use at least four decimal places where needed.
The first reward in Gₜ is Rₜ₊₁ and is not discounted. Terminal values are zero; rewards on entry to a terminal still count. Uniform ε-greedy exploration includes ALL available actions. Split exploitation equally among tied greedy actions unless a different tie rule is stated.
DP updates are synchronous unless stated otherwise. Online TD immediately retains each update. Independent methods restart from their stated initial values. Do not transfer updates from one method to another.
| Section | Questions | Points | Suggested time |
|---|---|---|---|
| Single-choice | 10 | 20 | 15 min |
| Short-answer | 5 | 25 | 30 min |
| MDP calculations | 3 (4–5 parts each) | 25 | 30 min |
| Learning algorithms | 2 (5 parts each) | 20 | 25 min |
| Optimal policy | 1 (4 parts) | 10 | 15 min |
Reserve the remaining 5 minutes for checking.
Name: ________________________ Student ID: ________________________
10 questions × 2 points
I. Single-choice questions
20 pointsA2. The target network [2 points]
Why does DQN hold target-network parameters fixed for several updates?
A3. An MDP model [2 points]
Which pair of objects describes the one-step environment model needed for tabular dynamic programming?
A4. Planning in Dyna [2 points]
What supplies the additional transitions used by Dyna planning updates?
A5. Fixed exploration [2 points]
In a state with a unique greedy action and at least one nongreedy action, a fixed ε=0.05 ε-greedy policy fails which GLIE requirement?
A6. Immediate reward and value [2 points]
A terminal transition gives reward 7. There are no later rewards. If γ=0.1, what is the return immediately BEFORE taking this transition?
A7. A uniform replay special case [2 points]
For proportional PER with all pᵢ>0, which setting makes P(i) uniform over N stored transitions?
A8. Policy evaluation versus value iteration [2 points]
What replaces the policy-weighted action average when moving from a policy-evaluation backup to a value-iteration backup?
A9. Stochastic policies [2 points]
Why can a stochastic policy be useful in rock-paper-scissors against an adaptive opponent?
A10. On-policy control [2 points]
Which target is used by ordinary one-step SARSA after observing (S,A,R,S′,A′)?
5 questions × 5 points
II. Short-answer questions
25 pointsB1. DP, MC and TD comparison [5 points]
Compare DP, Monte Carlo and TD(0) in terms of model requirements, sampled versus expected backups, bootstrapping, and whether an entire episode is needed. Explain the usual MC–TD bias/variance trade-off. [5 points]
B2. Policy improvement theorem [5 points]
Explain why a policy greedy with respect to vπ is no worse than π in a finite discounted MDP. State the one-step comparison, explain the repeated-improvement intuition, and distinguish policy stability from unchanged values after one approximate sweep. [5 points]
B3. Why Q-learning is off-policy [5 points]
Explain behaviour and target policies in Q-learning. Contrast its target with SARSA, and explain how exploration can affect their learned behaviour near a costly cliff. [5 points]
B4. Dueling is not Double [5 points]
State the mean-subtracted dueling aggregation formula. Explain the roles of the value and advantage streams, why an aggregation constraint is useful, and how dueling differs from Double DQN. [5 points]
B5. Function approximation risks [5 points]
Why is function approximation useful when tabular methods are impractical? Explain generalization, a linear approximation and a semi-gradient value update. Mention a limitation of shared parameters. [5 points]
3 questions: 8 + 8 + 9 points
III. Calculation — MDP
25 pointsC1. A branching episodic MRP [8 points]
States are A,B,C,T, with T terminal and γ=0.5. A gives reward 1 and transitions to B or C with probability 0.5 each. B gives reward 0 and moves to C. C gives reward 4 and terminates.
(a) Write the transition matrix and reward vector in order (A,B,C,T). [2]
(b) Compute all returns in the sampled episode A → B → C → T. [2]
(c) Compute the exact values of C, B and A by backward substitution. [2]
(d) Starting at V₀=0, give synchronous V₁,V₂,V₃ for (A,B,C). [2]
C2. Risky action and policy averaging [8 points]
γ=0.5. At S, safe gives reward 2 and terminates; bold gives reward 5 and moves to T or L with probability 0.5 each. At L, quit gives reward 0 and terminates; recover gives reward -2 and returns to S. A policy chooses each available action with probability 0.5.
(a) Derive the two Bellman expectation equations. [2]
(b) Solve for vπ(S),vπ(L). [2]
(c) Calculate the four qπ values and a greedy improved policy. [2]
(d) Evaluate the improved policy and determine whether it is already optimal. Justify your answer by checking both actions at L. [2]
C3. Value iteration with stochastic outcomes [9 points]
γ=0.5. In S, action a gives reward 1 and moves to S or U with probability 0.5 each; action b gives reward 0 and terminates. In U, action c gives reward 2 and terminates; action d gives reward 0 and moves to S.
(a) Write both Bellman optimality backup formulas. [1]
(b) From V₀=(0,0), compute V₁. [2]
(c) Compute V₂. [2]
(d) Compute V₃ and the actions selected in this third backup. [2]
(e) Evaluate the stationary policy (a,c) exactly and check Bellman optimality. [2]
2 questions × 10 points
IV. Calculation — Learning algorithms
20 pointsD1. MC, online TD and one frozen batch sweep [10 points]
Two episodes are observed in this order: (1) A --1→ B --2→ T; (2) A --2→ T. γ=1. For TD use α=0.5 and initial V(A)=V(B)=0. Independent methods reset to their specified initial conditions.
(a) List the return for each visit to A and B. [2]
(b) Compute first-visit sample-mean MC estimates using only these episodes. [2]
(c) Apply online TD(0) in the order the transitions were observed. Show all three updates. [2]
(d) Starting again at zero, perform ONE frozen batch TD sweep: compute TD errors using the initial zero table, average the errors separately for each state, then update each state once using α=0.5. [3]
(e) Explain why the two TD results need not agree. [1]
D2. Negative action values [10 points]
A nonterminal transition has Q(S,A)=-3, r=-2, γ=0.5 and α=0.2. Online next-state Q values (a₁,a₂,a₃) are (-2,-4,-1); the actual next action is a₁. Behaviour is ε-greedy with ε=0.2. Target-network values are (-3,-1,-2). Treat algorithms independently.
(a) Give the ε-greedy action probabilities. [2]
(b) Compute the SARSA target and update. [2]
(c) Compute the Q-learning target and update. [2]
(d) Compute DQN and Double DQN targets, identifying the selected actions. [3]
(e) Recompute the target and tabular update if this transition is terminal. [1]
1 question, 4 subquestions
V. Calculation — Optimal policy
10 pointsE1. An optimal continuing action [10 points]
γ=0.8. At S, stop gives reward 3 and terminates; wait gives reward 1 and returns to S. At U, exit gives reward 2 and terminates; join gives reward 0 and moves to S. Start with π₀=(stop,exit).
(a) Evaluate π₀. [2]
(b) Calculate all qπ₀ values and find a greedy π₁. [3]
(c) Evaluate π₁ and verify its optimality. [3]
(d) From V₀=0 give V₁ and V₂ under synchronous value iteration. Explain why they do not equal the final values. [2]