A1. The meaning of k [2 points]
In synchronous policy evaluation, k in Vₖ denotes which quantity?
Midterm Practice Paper
Foundations, policy evaluation and on-policy 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. A sufficient state [2 points]
A robot must collect a key before opening a door. Which state representation most directly fixes the missing information if position alone is not Markov?
A3. A DQN target [2 points]
A nonterminal transition has r=2 and γ=0.5. The target network outputs (6, 2) at the next state. What is the standard DQN target?
A4. Bellman expectation [2 points]
A policy selects a₁ with probability 0.25 and a₂ with probability 0.75. If qπ(s,a₁)=8 and qπ(s,a₂)=4, what is vπ(s)?
A5. Bootstrapping [2 points]
Which target bootstraps from an estimated state value?
A6. An action-independent baseline [2 points]
In REINFORCE, why can a state-dependent, action-independent baseline be subtracted from the return without changing the expected policy-gradient estimator?
A7. Discounted return [2 points]
The rewards are -2, 4, 8, followed by termination. With γ = 0.5, what is G₀?
A8. Function approximation [2 points]
Two states have similar feature vectors in a linear value approximator. Updating the weights using one state may affect the estimate of the other state. This illustrates:
A9. Ties in ε-greedy [2 points]
There are four actions. Exactly two tie for the largest Q value. If ε = 0.2, what is the probability of EACH greedy action?
A10. Dueling aggregation [2 points]
A dueling network has V(s)=3 and raw advantages (4, 0). Using mean-subtracted advantages, what are the Q values?
5 questions × 5 points
II. Short-answer questions
25 pointsB1. Prediction versus control [5 points]
Explain prediction and control. Describe the two stages of policy iteration, and explain why a greedy policy improvement uses argmax rather than max. [5 points]
B2. GLIE is a property [5 points]
State both GLIE conditions. Is GLIE itself a learning update or an action-selection formula? Discuss fixed ε = 0.1 and explain why merely requiring εₜ → 0 is insufficient. [5 points]
B3. DQN and Double DQN [5 points]
Give the standard DQN and Double DQN nonterminal targets. Explain which network selects and evaluates the next action in each case, and why Double DQN can reduce overestimation. [5 points]
B4. Prioritized replay [5 points]
Describe proportional prioritized experience replay. State a priority, a sampling probability and an importance-sampling weight. Explain the roles of the small positive priority offset and the correction exponent β. [5 points]
B5. REINFORCE and Actor–critic [5 points]
For an undiscounted episodic task, write a REINFORCE update with a state baseline. Then describe the actor and critic, and give a one-step TD-error signal commonly used by the actor. [5 points]
3 questions: 8 + 8 + 9 points
III. Calculation — MDP
25 pointsC1. A two-state Markov reward process [8 points]
There are nonterminal states A, B and terminal state T. γ=0.5. From A, the immediate reward is always 2; the next state is A or B with probability 0.5 each. From B, the reward is always -1; the next state is A or T with probability 0.5 each. T is absorbing with zero reward.
(a) Write the transition matrix in the order (A,B,T) and the expected reward vector. [2]
(b) For the observed episode A → B → T, compute G₀ and G₁. [2]
(c) Write and solve the Bellman equations for v(A),v(B). [2]
(d) From V₀=(0,0), calculate the synchronous vectors V₁ and V₂. [2]
C2. Policy evaluation and one improvement [8 points]
γ=0.5. In S, action stay gives reward 1 and returns to S; move gives reward 0 and goes to U. In U, cash gives reward 4 and terminates; reset gives reward 0 and goes to S. Policy π selects each available action with probability 0.5.
(a) Write the Bellman expectation equations under π. [2]
(b) Solve for vπ(S) and vπ(U). [2]
(c) Compute qπ for all four state-action pairs, and give a greedy improved policy π′. [2]
(d) Evaluate π′. Is its action at S uniquely greedy with respect to vπ′? Explain. [2]
C3. A 2 × 3 grid [9 points]
The grid has two rows and three columns. (1,1) and (2,3) are terminal. Four actions (up, down, left, right) are equiprobable. A move outside the grid leaves the state unchanged. Every move FROM a nonterminal state gives reward -1, including a move entering a terminal. γ=1; terminal values are fixed at zero.
(a) Write the synchronous random-policy update equation. [1]
(b) Starting from V₀=0, give the whole V₁ grid. [2]
(c) Give the whole V₂ grid. [2]
(d) Calculate V₃(1,2) and V₃(2,1). [2]
(e) Using V₂ for successor values, compute all four one-step action values at (1,2) and identify every greedy action. [2]
2 questions × 10 points
IV. Calculation — Learning algorithms
20 pointsD1. Repeated states: MC and online TD [10 points]
An episode is A --2→ B --(-1)→ A --4→ T. γ=0.5. For constant-step-size algorithms initialize V(A)=0, V(B)=2 and use α=0.5. Run each named algorithm independently from these initial values.
(a) Compute G₀,G₁,G₂. [2]
(b) Apply first-visit MC with the stated constant α once per visited state. [2]
(c) Using ONLY this episode and fresh zero counts, compute every-visit sample-mean MC estimates. [2]
(d) Apply online TD(0) in chronological order; show the value after each update. [3]
(e) Explain why the TD update at the second transition uses a value that has already changed. [1]
D2. Four targets from one transition [10 points]
A nonterminal transition has current Q(S,A)=1, reward r=-1, γ=0.8 and learning rate α=0.25. Online next-state values for (a₁,a₂,a₃) are (5,2,0). The actual next action is a₂. The behaviour is ε-greedy with ε=0.3. Target-network next-state values are (1,4,3). Compute each algorithm independently.
(a) Give the behaviour probabilities of a₁,a₂,a₃. [2]
(b) Give the SARSA target and updated Q(S,A). [2]
(c) Give the Q-learning target and updated Q(S,A). [2]
(d) Give the standard DQN and Double DQN targets. Show which next action each selects. [3]
(e) If the transition instead terminates, give its target and tabular update. [1]
1 question, 4 subquestions
V. Calculation — Optimal policy
10 pointsE1. An optimal policy with a tie [10 points]
γ=0.5. In X, safe gives reward 2 and goes to T; travel gives reward 0 and goes to Y. In Y, collect gives reward 4 and goes to T; cycle gives reward 1 and goes to X. Start policy iteration with π₀=(travel,cycle).
(a) Evaluate π₀ exactly. [2]
(b) Compute all four qπ₀ values and make a greedy improvement π₁. [3]
(c) Evaluate π₁, verify Bellman optimality, and list ALL deterministic optimal policies. [3]
(d) From V₀=0, give the synchronous value-iteration vectors V₁ and V₂. [2]