Noesis
Level 5 — MasteryDeep & Advanced RL

Deep & Advanced RL

⏱ 2 minutes60 marksprintable — key stays hidden on paper

Time limit: 2 hours 30 minutes Total marks: 60 Instructions: Answer ALL three questions. Show derivations fully; state assumptions. Code answers may be written in NumPy/PyTorch-style pseudocode but must be logically complete.

Question 1 — Policy Gradients, Baselines & Variance (20 marks)

Consider a single-step (bandit-like) stochastic policy πθ(a∣s)\pi_\theta(a\mid s) over a finite action set A\mathcal{A}, with scalar reward r(s,a)r(s,a). Define the objective J(θ)=Ea∼πθ[r(s,a)]J(\theta)=\mathbb{E}_{a\sim\pi_\theta}[r(s,a)] for a fixed state ss.

(a) Derive the policy gradient ∇θJ(θ)\nabla_\theta J(\theta) from first principles using the log-derivative (score function) trick. State clearly why the identity Ea∼πθ[∇θlog⁡πθ(a∣s)]=0\mathbb{E}_{a\sim\pi_\theta}[\nabla_\theta\log\pi_\theta(a\mid s)]=0 holds. (5)

(b) Prove that subtracting any action-independent baseline b(s)b(s) from the reward leaves the gradient estimator unbiased. Then, treating the single-sample estimator g(a)=(r(a)−b) ∇θlog⁡πθ(a)g(a)=(r(a)-b)\,\nabla_\theta\log\pi_\theta(a) as a random vector, derive the value of the scalar baseline b⋆b^\star that minimises E[∥g(a)∥2]\mathbb{E}[\lVert g(a)\rVert^2]. (7)

(c) For a softmax policy πθ(a)=eθa∑a′eθa′\pi_\theta(a)=\dfrac{e^{\theta_a}}{\sum_{a'}e^{\theta_{a'}}} over A={1,2}\mathcal{A}=\{1,2\} with θ=(θ1,θ2)\theta=(\theta_1,\theta_2), compute ∇θlog⁡πθ(a=1)\nabla_\theta\log\pi_\theta(a=1) explicitly. Given θ=(0,ln⁡3)\theta=(0,\ln 3) and rewards r(1)=1, r(2)=0r(1)=1,\ r(2)=0, compute the exact gradient ∇θJ\nabla_\theta J and the optimal constant baseline b⋆b^\star from part (b). (8)

Question 2 — DQN Target Objects & Overestimation (20 marks)

(a) Write the tabular Q-learning update and the DQN loss using a target network with parameters θ−\theta^-. Explain, in terms of the bias–variance and stability of the regression target, why the target network and why experience replay each help. Give the precise failure mode each mitigates. (6)

(b) Overestimation bias. Let Q(s′,a)=Q∗(s′,a)+εaQ(s',a)=Q^\ast(s',a)+\varepsilon_a where the errors εa\varepsilon_a are i.i.d. zero-mean with variance σ2\sigma^2 across mm actions, and suppose all true values are equal, Q∗(s′,a)=VQ^\ast(s',a)=V. Show that E[max⁡aQ(s′,a)]≥V\mathbb{E}[\max_a Q(s',a)]\ge V, i.e. the max operator produces a non-negative bias. Then explain precisely how Double DQN decouples action selection from action evaluation to reduce this bias, writing its target explicitly. (8)

(c) Dueling architecture. The dueling network outputs Q(s,a)=V(s)+A(s,a)Q(s,a)=V(s)+A(s,a). Explain why this decomposition is unidentifiable, and derive/justify the standard identifiability fix used in practice (subtracting the mean advantage). Show that with the fix the mapping from (V,A)(V,A) to QQ is unique. (6)

Question 3 — PPO / TRPO and Entropy-Regularised RL (20 marks)

(a) TRPO maximises the surrogate E[πθ(a∣s)πθold(a∣s) A^]\mathbb{E}\big[\tfrac{\pi_\theta(a\mid s)}{\pi_{\theta_{\text{old}}}(a\mid s)}\,\hat A\big] subject to E[KL(πθold∥πθ)]≤δ\mathbb{E}[\mathrm{KL}(\pi_{\theta_{\text{old}}}\Vert\pi_\theta)]\le\delta. State the PPO clipped objective and explain, with a case analysis on the sign of A^\hat A, how clipping the probability ratio ρ=πθ/πθold\rho=\pi_\theta/\pi_{\theta_{\text{old}}} approximates the trust-region constraint without a hard KL constraint. (8)

(b) For two Gaussians p=N(μ1,σ2)p=\mathcal{N}(\mu_1,\sigma^2) and q=N(μ2,σ2)q=\mathcal{N}(\mu_2,\sigma^2) with equal variance, derive KL(p∥q)\mathrm{KL}(p\Vert q). Comment on how this relates to a quadratic penalty on the policy-mean shift in continuous-control TRPO/PPO. (6)

(c) Soft Actor-Critic. SAC augments the reward with an entropy term, optimising ∑tE[rt+αH(π(⋅∣st))]\sum_t\mathbb{E}[r_t+\alpha\mathcal H(\pi(\cdot\mid s_t))]. For a discrete state with two actions and Q-values Q(a1),Q(a2)Q(a_1),Q(a_2), derive the optimal soft policy (the one maximising Eπ[Q]+αH(π)\mathbb{E}_\pi[Q]+\alpha\mathcal H(\pi)) and show it is the Boltzmann/softmax distribution over Q/αQ/\alpha. Evaluate the optimal action probabilities for Q(a1)=2, Q(a2)=1, α=1Q(a_1)=2,\ Q(a_2)=1,\ \alpha=1. (6)

Answer keyMark scheme & solutions

Question 1

(a) (5) J(θ)=∑aπθ(a) r(a)J(\theta)=\sum_a \pi_\theta(a)\,r(a). ∇θJ=∑ar(a)∇θπθ(a)=∑ar(a)πθ(a)∇θπθ(a)πθ(a)=Ea∼πθ[r(a)∇θlog⁡πθ(a)].\nabla_\theta J=\sum_a r(a)\nabla_\theta\pi_\theta(a)=\sum_a r(a)\pi_\theta(a)\frac{\nabla_\theta\pi_\theta(a)}{\pi_\theta(a)}=\mathbb{E}_{a\sim\pi_\theta}[r(a)\nabla_\theta\log\pi_\theta(a)].

  • Log-derivative identity ∇π=π∇log⁡π\nabla\pi=\pi\nabla\log\pi: (2)
  • Final expectation form: (1)
  • Zero-score fact: E[∇θlog⁡πθ(a)]=∑aπθ∇log⁡πθ=∑a∇πθ=∇θ∑aπθ=∇θ1=0\mathbb{E}[\nabla_\theta\log\pi_\theta(a)]=\sum_a\pi_\theta\nabla\log\pi_\theta=\sum_a\nabla\pi_\theta=\nabla_\theta\sum_a\pi_\theta=\nabla_\theta 1=0. Holds because probabilities sum to 1 (normalisation constant). (2)

(b) (7) Unbiasedness: subtracting bb adds −b E[∇log⁡π]=−b⋅0=0-b\,\mathbb{E}[\nabla\log\pi]=-b\cdot 0=0, so E[(r−b)∇log⁡π]=E[r∇log⁡π]=∇J\mathbb{E}[(r-b)\nabla\log\pi]=\mathbb{E}[r\nabla\log\pi]=\nabla J. (3)

Minimise variance/second moment. Let ψ(a)=∇θlog⁡πθ(a)\psi(a)=\nabla_\theta\log\pi_\theta(a). E∥g∥2=E[(r−b)2∥ψ∥2]=E[r2∥ψ∥2]−2b E[r∥ψ∥2]+b2E[∥ψ∥2].\mathbb{E}\lVert g\rVert^2=\mathbb{E}[(r-b)^2\lVert\psi\rVert^2]=\mathbb{E}[r^2\lVert\psi\rVert^2]-2b\,\mathbb{E}[r\lVert\psi\rVert^2]+b^2\mathbb{E}[\lVert\psi\rVert^2]. Set derivative w.r.t. bb to zero: b⋆=E[r(a)∥ψ(a)∥2]E[∥ψ(a)∥2].b^\star=\frac{\mathbb{E}[r(a)\lVert\psi(a)\rVert^2]}{\mathbb{E}[\lVert\psi(a)\rVert^2]}.

  • Expand second moment: (2)
  • Differentiate and solve: (2) (This is the classic ψ\psi-weighted reward baseline.)

(c) (8) Softmax score: log⁡π(1)=θ1−ln⁡(eθ1+eθ2)\log\pi(1)=\theta_1-\ln(e^{\theta_1}+e^{\theta_2}). ∂θ1log⁡π(1)=1−π(1),∂θ2log⁡π(1)=−π(2).\partial_{\theta_1}\log\pi(1)=1-\pi(1),\qquad \partial_{\theta_2}\log\pi(1)=-\pi(2). So ∇θlog⁡π(1)=(1−π(1),−π(2))\nabla_\theta\log\pi(1)=(1-\pi(1),-\pi(2)); similarly ∇θlog⁡π(2)=(−π(1),1−π(2))\nabla_\theta\log\pi(2)=(-\pi(1),1-\pi(2)). (2)

With θ=(0,ln⁡3)\theta=(0,\ln3): π(1)=11+3=14, π(2)=34\pi(1)=\frac{1}{1+3}=\tfrac14,\ \pi(2)=\tfrac34. Gradient: ∇J=∑aπ(a)r(a)∇log⁡π(a)\nabla J=\sum_a\pi(a)r(a)\nabla\log\pi(a). Only r(1)=1r(1)=1 contributes: ∇J=π(1)⋅1⋅(1−π(1),−π(2))=14(34,−34)=(316,−316).\nabla J=\pi(1)\cdot1\cdot(1-\pi(1),-\pi(2))=\tfrac14(\tfrac34,-\tfrac34)=(\tfrac{3}{16},-\tfrac{3}{16}). (3)

Baseline: ψ(1)=(3/4,−3/4)\psi(1)=(3/4,-3/4), ∥ψ(1)∥2=9/8\lVert\psi(1)\rVert^2=9/8; ψ(2)=(−1/4,1/4)\psi(2)=(-1/4,1/4), ∥ψ(2)∥2=1/8\lVert\psi(2)\rVert^2=1/8. b⋆=π(1)r(1)∥ψ(1)∥2+π(2)r(2)∥ψ(2)∥2π(1)∥ψ(1)∥2+π(2)∥ψ(2)∥2=14⋅1⋅98+014⋅98+34⋅18=9/329/32+3/32=912=34.b^\star=\frac{\pi(1)r(1)\lVert\psi(1)\rVert^2+\pi(2)r(2)\lVert\psi(2)\rVert^2}{\pi(1)\lVert\psi(1)\rVert^2+\pi(2)\lVert\psi(2)\rVert^2}=\frac{\tfrac14\cdot1\cdot\tfrac98+0}{\tfrac14\cdot\tfrac98+\tfrac34\cdot\tfrac18}=\frac{9/32}{9/32+3/32}=\frac{9}{12}=\tfrac34. (3)

Question 2

(a) (6) Tabular: Q(s,a)←Q(s,a)+α[r+γmax⁡a′Q(s′,a′)−Q(s,a)]Q(s,a)\leftarrow Q(s,a)+\alpha\big[r+\gamma\max_{a'}Q(s',a')-Q(s,a)\big]. DQN loss: L(θ)=E(s,a,r,s′)∼D[(r+γmax⁡a′Qθ−(s′,a′)−Qθ(s,a))2]L(\theta)=\mathbb{E}_{(s,a,r,s')\sim D}\big[(r+\gamma\max_{a'}Q_{\theta^-}(s',a')-Q_\theta(s,a))^2\big]. (2)

  • Target network: keeps the regression target y=r+γmax⁡Qθ−y=r+\gamma\max Q_{\theta^-} fixed for many steps, breaking the feedback loop where updating θ\theta instantly moves the target ("chasing a moving target"), which otherwise causes oscillation/divergence. (2)
  • Experience replay: samples transitions uniformly from buffer, breaking temporal correlation of consecutive samples (which violates i.i.d. and biases SGD) and improving data efficiency by reusing transitions. Failure mode mitigated: catastrophic correlation-induced instability & forgetting. (2)

(b) (8) By Jensen (max is convex): E[max⁡aQ(s′,a)]≥max⁡aE[Q(s′,a)]=max⁡aQ∗(s′,a)=V\mathbb{E}[\max_a Q(s',a)]\ge\max_a\mathbb{E}[Q(s',a)]=\max_a Q^\ast(s',a)=V. Since errors are zero-mean, E[Q(s′,a)]=V\mathbb{E}[Q(s',a)]=V for all aa, so the RHS =V=V, giving bias ≥0\ge0; strictly positive whenever σ2>0\sigma^2>0 and m≥2m\ge2. (4) Double DQN target: yDDQN=r+γ Qθ− ⁣(s′, arg⁡max⁡a′Qθ(s′,a′)).y^{DDQN}=r+\gamma\,Q_{\theta^-}\!\big(s',\ \arg\max_{a'}Q_\theta(s',a')\big). Selection uses the online net θ\theta; evaluation uses the target net θ−\theta^-. Because the noise driving the argmax (online) is independent of the noise in the evaluation (target), the selected action is no longer systematically the one whose evaluation noise is largest, removing the upward coupling and reducing overestimation. (4)

(c) (6) Unidentifiability: Q=V+A=(V+c)+(A−c)Q=V+A=(V+c)+(A-c) for any constant cc; infinitely many (V,A)(V,A) give the same QQ, so the network cannot recover VV and AA separately. (2) Fix: Q(s,a)=V(s)+(A(s,a)−1∣A∣∑a′A(s,a′))Q(s,a)=V(s)+\big(A(s,a)-\frac1{|\mathcal A|}\sum_{a'}A(s,a')\big). (2) Uniqueness: averaging both sides over aa gives 1∣A∣∑aQ=V+(Aˉ−Aˉ)=V\frac1{|\mathcal A|}\sum_a Q=V+ \big(\bar A-\bar A\big)=V, so VV is pinned to the mean of QQ, and then A(s,a)=Q(s,a)−V(s)A(s,a)=Q(s,a)-V(s) up to the enforced zero-mean constraint. The constraint ∑aA=0\sum_a A=0 removes the free constant cc, making the map bijective. (2)

Question 3

(a) (8) PPO clipped objective: LCLIP=E[min⁡(ρA^, clip(ρ,1−ϵ,1+ϵ)A^)],ρ=πθπθold.L^{CLIP}=\mathbb{E}\big[\min\big(\rho\hat A,\ \mathrm{clip}(\rho,1-\epsilon,1+\epsilon)\hat A\big)\big],\quad \rho=\tfrac{\pi_\theta}{\pi_{\theta_{old}}}. (2) Case analysis:

  • A^>0\hat A>0 (good action): objective increases with ρ\rho but min⁡\min caps it at ρ=1+ϵ\rho=1+\epsilon; no incentive to push probability beyond 1+ϵ1+\epsilon. (2)
  • A^<0\hat A<0 (bad action): objective favours decreasing ρ\rho; the clip at 1−ϵ1-\epsilon (via the min⁡\min of two negative terms selecting the smaller/more-negative unclipped one only until the bound) prevents the ratio from being driven arbitrarily far below, limiting the pessimistic step. (2) Net effect: the ratio is confined near 1, keeping πθ\pi_\theta close to πθold\pi_{\theta_{old}} — a first-order, penalty-free surrogate for TRPO's KL trust region, cheaper (no Fisher/CG) and reusable over minibatches. (2)

(b) (6) KL(p∥q)=∫pln⁡pq=Ep[−(x−μ1)22σ2+(x−μ2)22σ2].\mathrm{KL}(p\Vert q)=\int p\ln\frac pq=\mathbb{E}_p\Big[-\frac{(x-\mu_1)^2}{2\sigma^2}+\frac{(x-\mu_2)^2}{2\sigma^2}\Big]. Expanding and using Ep[(x−μ1)2]=σ2\mathbb{E}_p[(x-\mu_1)^2]=\sigma^2, Ep[(x−μ2)2]=σ2+(μ1−μ2)2\mathbb{E}_p[(x-\mu_2)^2]=\sigma^2+(\mu_1-\mu_2)^2: KL(p∥q)=(μ1−μ2)22σ2.\mathrm{KL}(p\Vert q)=\frac{(\mu_1-\mu_2)^2}{2\sigma^2}. (4) It is a quadratic in the mean shift; hence bounding KL ≤δ\le\delta bounds ∣μ1−μ2∣≤2σ2δ|\mu_1-\mu_2|\le\sqrt{2\sigma^2\delta} — the trust region on a Gaussian policy is (locally) a quadratic penalty on how far the action-mean may move per update, matching the Fisher-metric quadratic used in TRPO. (2)

(c) (6) Maximise F(π)=∑aπ(a)Q(a)−α∑aπ(a)ln⁡π(a)F(\pi)=\sum_a\pi(a)Q(a)-\alpha\sum_a\pi(a)\ln\pi(a) s.t. ∑π=1\sum\pi=1. Lagrangian: ∂π(a)[F−λ(∑π−1)]=Q(a)−α(ln⁡π(a)+1)−λ=0\partial_{\pi(a)}[F-\lambda(\sum\pi-1)]=Q(a)-\alpha(\ln\pi(a)+1)-\lambda=0 ⇒ln⁡π(a)=Q(a)α−1−λα\Rightarrow \ln\pi(a)=\frac{Q(a)}{\alpha}-1-\frac{\lambda}{\alpha}, so π⋆(a)=exp⁡(Q(a)/α)∑a′exp⁡(Q(a′)/α).\pi^\star(a)=\frac{\exp(Q(a)/\alpha)}{\sum_{a'}\exp(Q(a')/\alpha)}. (4) Boltzmann/softmax over Q/αQ/\alpha — the SAC soft-optimal policy. Evaluate Q=(2,1),α=1Q=(2,1),\alpha=1: π(a1)=e2e2+e1=ee+1≈0.731,π(a2)≈0.269.\pi(a_1)=\frac{e^2}{e^2+e^1}=\frac{e}{e+1}\approx0.731,\quad \pi(a_2)\approx0.269. (2)

[
  {"claim":"Q1c policy pi(1)=1/4, pi(2)=3/4 for theta=(0,ln3)",
   "code":"import sympy as sp; t1,t2=0,sp.log(3); p1=sp.exp(t1)/(sp.exp(t1)+sp.