Midterm Practice Paper

A1. Tabular convergence conditions [2 points]

Which combination is relevant to standard tabular SARSA convergence to optimal action values under suitable finite-MDP assumptions?

A2. Expectation over next states [2 points]

An action gives reward 1 and moves to X or Y with probabilities 0.25 and 0.75. V(X)=8, V(Y)=0 and γ=0.5. What is its one-step action value?

A3. Experience replay [2 points]

What is a main purpose of sampling minibatches from a replay buffer?

A4. An advantage signal [2 points]

At a fixed state, qπ(s,a)=6 and vπ(s)=4. What is Aπ(s,a)?

A5. An infinite discounted stream [2 points]

A continuing task gives reward 2 on every step. If γ=0.5, what is the return?

A6. A model versus a value function [2 points]

Which output is most clearly an environment-model prediction rather than a value prediction?

A7. Value iteration [2 points]

Which statement about intermediate value-iteration estimates is generally correct?

A8. TD error [2 points]

V(S)=3, r=-1, γ=0.5 and V(S′)=6 for a nonterminal transition. What is the TD error?

A9. Importance weights [2 points]

In PER with N=4, P(i)=0.5 and β=1, what is the UNNORMALIZED importance weight (N P(i))^(−β)?

A10. A wall in gridworld [2 points]

In the stated gridworld convention, attempting to move outside the grid keeps the state unchanged and costs -1. Which target is correct for this action?

B1. Three DP procedures [5 points]

Distinguish iterative policy evaluation, policy iteration and value iteration. Explain what is fixed during evaluation, what changes during improvement and what k counts. [5 points]

B2. Exploration and tie handling [5 points]

Give the ε-greedy probabilities for m actions with g tied greedy actions, using uniform exploration over all m actions. Explain why greedy actions also receive exploration probability and why GLIE needs more than a decaying ε. [5 points]

B3. Double DQN does not average networks [5 points]

Explain maximization bias using noisy Q estimates. Give the Double DQN target, identify the roles of the online and target networks, and state one limitation of the method. [5 points]

B4. Numerical PER probabilities [5 points]

Three transitions have absolute TD errors (0,1,3). Set εₚ=1, αₚ=1 and β=1. Find priorities, sampling probabilities and unnormalized importance weights. Explain why transition 1 can still be sampled. [5 points]

B5. Baseline and actor update direction [5 points]

For an undiscounted REINFORCE update, explain the role of ∇θ log πθ(Aₜ|Sₜ). If Gₜ=3 and b(Sₜ)=5, what is the weight on this gradient, and what is the usual local effect on the selected action probability? Explain why the baseline must not depend on the sampled action in the simple unbiased-baseline argument. [5 points]

C1. Rewards correlated with transitions [8 points]

There is one nonterminal state S and one terminal state T. From S, with probability 0.5 the process returns to S and receives reward 2; with probability 0.5 it enters T and receives reward 6. γ=0.5.

(a) Find the expected immediate reward at S and write the Bellman equation. [2]

(b) Solve for v(S). [2]

(c) For S --2→ S --6→ T, compute both visit returns. [2]

(d) From V₀(S)=0, compute V₁,V₂,V₃ synchronously. [2]

C2. Nonuniform policy probabilities [8 points]

γ=0.5. At A, fast gives reward 1 and terminates; support gives reward 0 and moves to B. At B, finish gives reward 3 and terminates; repeat gives reward 1 and returns to B. π(fast|A)=0.25, π(support|A)=0.75; π chooses each B action with probability 0.5.

(a) Write Bellman expectation equations. [2]

(b) Solve for vπ(A),vπ(B). [2]

(c) Find all four qπ values and a greedy policy π′. [2]

(d) Evaluate π′ and verify whether another improvement is possible. [2]

C3. A random walk with two terminals [9 points]

Five locations lie on a line: Tₗ — L — M — R — Tᵣ. Both end locations are terminal. At each nonterminal state, left and right are chosen with probability 0.5 and move to the adjacent location. Every move costs -1, including entry into a terminal. γ=1.

(a) From V₀=0, give V₁ for (L,M,R). [1]

(b) Compute V₂ synchronously. [2]

(c) Compute V₃ synchronously. [2]

(d) Solve for the exact random-policy values. [2]

(e) Using those exact values, list all greedy actions in each state. [2]

D1. Targets of different horizons [10 points]

Observed episodes are (1) A --0→ B --2→ T; (2) A --2→ T. γ=1. For constant-step updates initialize V(A)=1,V(B)=0 and α=0.5. Treat methods independently.

(a) List all visit returns. [2]

(b) Compute first-visit sample-mean MC estimates from these episodes with fresh counts. [2]

(c) Process both episodes with online TD(0), showing all three updates. [3]

(d) Starting from the original values, perform ONLY the two-step update for the first visit to A in episode 1. [2]

(e) Why does this two-step target equal the MC return for that visit? [1]

D2. Tie-breaking changes Double DQN [10 points]

Q(S,A)=0, r=2, γ=1, α=0.5 and the transition is nonterminal. Online next-state values are (3,3,1); the actual next action is a₃. Behaviour uses ε=0.3, splitting exploitation equally among tied maxima. Target-network values are (4,1,5). For Double DQN only, break online argmax ties by choosing the lowest action index.

(a) Compute the behaviour probabilities. [2]

(b) Compute SARSA's target and update. [2]

(c) Compute Q-learning's target and update. [2]

(d) Compute DQN and Double DQN targets, applying the stated tie rule. [3]

(e) Give the target and tabular update for a terminal version of this transition. [1]

E1. Discounting changes the optimal choice [10 points]

At S, exit gives reward 2 and terminates; work gives reward 1.5, then moves to S or T with probability 0.5 each. At U, stop gives reward 1.5 and terminates; join gives reward 0 and goes to S. For (a)–(c), γ=0.8 and π₀=(exit,stop).

(a) Evaluate π₀. [2]

(b) Compute all qπ₀ values and improve the policy. [3]

(c) Evaluate the improved policy and verify optimality. [3]

(d) Let γ vary in [0,1). At S, for which γ is work strictly better than exit when followed optimally? State the tie value. [2]