Midterm Practice Paper

A1. Double DQN action selection [2 points]

Online next-state values are (1,5), while target-network values are (7,2). Which value is used for the bootstrap term in Double DQN?

A2. An optimality equation [2 points]

For an MDP with stochastic next states, which operation order is correct in a Bellman optimality backup?

A3. What GLIE does not imply [2 points]

Which statement is NOT part of the definition of GLIE?

A4. Discount factor zero [2 points]

If γ=0, which quantity does the return Gₜ equal?

A5. DQN output [2 points]

In a standard discrete-action DQN, what does the network output for one input state?

A6. ε-greedy probabilities [2 points]

With five actions, a unique greedy action and ε=0.1, what is the probability of choosing a nongreedy action in total?

A7. The critic [2 points]

In actor–critic, what is the critic’s main role?

A8. First-visit MC [2 points]

A state occurs twice in one episode, with returns 4 and 10 at its two visits. Which return is used by first-visit MC for that state in this episode?

A9. Which state needs a velocity? [2 points]

For a moving cart whose future position depends on its velocity, which claim is most reasonable?

A10. Linear value approximation [2 points]

A linear value approximator uses x(s)=(1,2) and w=(3,-1). What is v̂(s,w)?

B1. Reading the notation [5 points]

Briefly distinguish reward from return, state value from action value, and max from argmax. Finally distinguish the iteration counter k from environment time t and the learning rate α from the exploration parameter ε. [5 points]

B2. MC and TD with repeated visits [5 points]

Explain first-visit versus every-visit MC. Distinguish sample-mean and constant-step-size estimation. Explain why online TD must specify the order of transitions when a state repeats. [5 points]

B3. Choose the correct DQN improvement [5 points]

Match each mechanism to its main purpose and give one useful detail: (i) replay buffer, (ii) target network, (iii) Double DQN, (iv) prioritized replay, (v) dueling network. [5 points]

B4. A small REINFORCE calculation [5 points]

In a one-state two-action bandit, πθ(a₁)=σ(θ) and πθ(a₂)=1−σ(θ), where σ is the logistic function. An episode consists of one action. At θ=0 the sampled action is a₁ and its reward is 4. Use baseline b=2 and learning rate α=0.1. Compute ∂logπθ(a₁)/∂θ, the REINFORCE parameter update, and the direction of the probability change. Explain the role of the baseline. [5 points]

B5. Learning, planning and model errors [5 points]

Distinguish model-free learning from planning. Outline the real-experience and simulated-experience parts of Dyna. Why can additional planning be harmful when the learned model is inaccurate? [5 points]

C1. Undiscounted absorbing MRP [8 points]

γ=1. States A and B are nonterminal. Each transition from either state has reward -1. A moves to A or B with probability 0.5 each. B moves to A with probability 0.25 and to terminal T with probability 0.75. T is absorbing with zero reward.

(a) Write the transition matrix and the Bellman equations. [2]

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

(c) For the observed episode A → A → B → T, compute all three returns. [2]

(d) Interpret -v(A) and -v(B), and explain why finite values are possible even though γ=1. [2]

C2. A deterministic initial policy [8 points]

γ=0.5. At S, a gives reward 2 and goes to U; b gives reward 1 and terminates. At U, c gives reward 0 and goes to S; d gives reward 3 and terminates. The initial deterministic policy is π=(a,c).

(a) Write its Bellman equations. [2]

(b) Solve for vπ(S),vπ(U). [2]

(c) Compute all four qπ values and give a greedy improvement. [2]

(d) Evaluate the improved policy and test whether it is optimal. [2]

C3. Expectation backups versus optimality backups [9 points]

γ=0.5. At S, a gives reward 0 and returns to S; b gives reward 1 and goes to U. At U, c gives reward 2 and terminates; d gives reward -1 and goes to S. Let Vₖ be random-policy evaluation with probability 0.5 per action. Let Wₖ be value iteration. Start both at zero.

(a) Write the update formulas for V and W at S. [1]

(b) Compute V₁,V₂ for (S,U). [2]

(c) Compute W₁,W₂ for (S,U). [2]

(d) Using V₂ as successor values, calculate all four one-step action values and the greedy policy. [2]

(e) Explain why the two sequences differ even though they use the same environment. [2]

D1. Every-visit constant-step MC [10 points]

An episode is A --1→ A --2→ B --3→ T. γ=0.5. Initialize V(A)=2,V(B)=1 and use constant α=0.5. Reset to these initial values for each method. Every-visit MC updates are applied in chronological visit order after the episode has ended.

(a) Compute G₀,G₁,G₂. [2]

(b) Apply first-visit constant-step MC. [2]

(c) Apply every-visit constant-step MC, showing both A updates. [2]

(d) Apply online TD(0), showing all three updates. [3]

(e) Why is the every-visit result not simply the arithmetic mean of A’s two returns? [1]

D2. Separate behaviour, learning and target networks [10 points]

Q(S,A)=3, r=0, γ=0.9, α=0.1. The transition is nonterminal. Online next-state values for (a₁,a₂) are (2,6), target-network values are (7,4), and the actual next action is a₁. Behaviour is ε-greedy with ε=0.2. Run each algorithm independently.

(a) Compute behaviour action probabilities. [2]

(b) Compute the SARSA target and tabular update. [2]

(c) Compute the Q-learning target and tabular update. [2]

(d) Compute DQN and Double DQN targets; state which network selects and which evaluates the next action. [3]

(e) If this transition is terminal, compute its target and tabular update. [1]

E1. Three actions at one state [10 points]

γ=0.5. At S, short gives reward 4 and terminates; long gives reward 0 and moves to U; wait gives reward 1 and returns to S. At U, collect gives reward 6 and terminates; back gives reward 0 and moves to S. Start with π₀=(wait,back).

(a) Evaluate π₀. [2]

(b) Compute all five qπ₀ values and obtain π₁ by greedy improvement. [3]

(c) Evaluate π₁ and prove it is optimal by checking every action. [3]

(d) From V₀=(0,0), compute V₁,V₂ with synchronous value iteration. [2]