Deep & Advanced RL

Question 1 (12 marks)

(a) Standard DQN: uses the target network for both action selection and evaluation. $y_{\text{DQN}} = r + \gamma \max_{a'} Q_{\theta^-}(s',a') = 2 + 0.9 \times \max(6.0,4.0,7.0) = 2 + 0.9\times 7.0 = 8.3$

• Correct max of target net (7.0): 1
• Correct discount+reward assembly: 1
• Answer $8.3$: 1

(b) Double DQN: online net selects the argmax action, target net evaluates it.

• Online argmax at $s'$: $a_1$ (value 8.0 is largest). (2)
• Evaluate with target: $Q_{\theta^-}(s',a_1) = 4.0$. (1) $y_{\text{DDQN}} = 2 + 0.9\times 4.0 = 5.6$ (1)

(c) (5 marks)

• Double DQN mitigates maximization bias / overestimation of Q-values (2). The single $\max$ operator in standard DQN couples selection and evaluation, so noise/errors are systematically over-selected: $\mathbb{E}[\max] \ge \max \mathbb{E}$ (2).
• Here the online net picks $a_1$ (its optimistic choice), but the target net values $a_1$ only at 4.0, whereas the standard target greedily grabs the target net's own max (7.0). Decoupling yields the smaller, less optimistic target $5.6 < 8.3$ (1).

Question 2 (14 marks)

(a) Softmax over logits $(0, \ln 3)$: $\pi(a_0) = \frac{e^0}{e^0+e^{\ln 3}} = \frac{1}{1+3} = 0.25,\qquad \pi(a_1) = \frac{3}{4} = 0.75$

• Setup: 1, each probability: 1+1

(b) Update rule (REINFORCE-with-baseline): $\theta \leftarrow \theta + \alpha (G-b)\nabla_\theta\log\pi(a_1)$.

• $G - b = 1 - 0.5 = 0.5$. (1)
• $\nabla_\theta\log\pi(a_1) = \mathbf{e}_{a_1} - \pi = (0,1) - (0.25, 0.75) = (-0.25, 0.25)$. (2)
• Update vector: $\alpha(G-b)\nabla = 0.1\times 0.5 \times(-0.25,0.25) = (-0.0125, 0.0125)$. (2)
• New parameters: $\theta_0 = 0 + (-0.0125) = -0.0125,\qquad \theta_1 = 1.0986 + 0.0125 = 1.1111$ (2)

(Interpretation: positive advantage on $a_1$ raises its logit, lowers $a_0$'s.)

(c) (4 marks)

• Purpose: baseline reduces variance of the gradient estimate without introducing bias, giving faster/stabler learning (2).
• Unbiasedness proof (2): the extra term is $\mathbb{E}_{a\sim\pi}\big[b(s)\nabla_\theta\log\pi(a|s)\big] = b(s)\sum_a \pi(a|s)\nabla_\theta\log\pi(a|s) = b(s)\sum_a \nabla_\theta\pi(a|s) = b(s)\nabla_\theta\!\sum_a\pi(a|s) = b(s)\nabla_\theta 1 = 0.$ Since it adds zero in expectation, the estimator's expectation is unchanged.

Question 3 (12 marks)

(a) $\hat A=+3>0$, $\rho=1.5$, clip range $[0.8,1.2]$.

• Unclipped: $1.5\times 3 = 4.5$; clipped: $\text{clip}(1.5,0.8,1.2)\times3 = 1.2\times3 = 3.6$.
• $L = \min(4.5, 3.6) = 3.6$. (3)

(b) $\hat A=-2<0$, $\rho=1.5$.

• Unclipped: $1.5\times(-2) = -3.0$; clipped: $1.2\times(-2) = -2.4$.
• $L = \min(-3.0, -2.4) = -3.0$. (3)

(c) (6 marks)

• For positive advantage with $\rho > 1+\epsilon$, the clipped branch $(1+\epsilon)\hat A$ is constant in $\rho$, and since it is the smaller of the two when $\rho>1+\epsilon$, $L = (1+\epsilon)\hat A$, so $\partial L/\partial\rho = 0$ (3).
• Implication: no gradient once the policy has moved "too far" in the improving direction → prevents excessively large policy updates / destructive steps (2).
• Contrast: a vanilla importance-weighted objective $\rho\hat A$ has constant gradient $\hat A$ and keeps pushing $\rho$ up without bound, causing large, unstable off-policy updates (1).

Question 4 (10 marks)

(a) $A(s_0,a_0) = 1 + 0.8\times 3.0 - 2.0 = 1 + 2.4 - 2.0 = 1.4$. (3)

(b) $A^{(2)} = 1 + 0.8\times 0 + 0.8^2\times 1.5 - 2.0 = 1 + 0 + 0.64\times1.5 - 2 = 1 + 0.96 - 2 = -0.04$. (3)

(c) TD errors:

• $\delta_0 = r_1 + \gamma V(s_1) - V(s_0) = 1.4$ (same as (a)). (1)
• $\delta_1 = r_2 + \gamma V(s_2) - V(s_1) = 0 + 0.8\times1.5 - 3.0 = 1.2 - 3.0 = -1.8$. (1)
• GAE: $\hat A^{\text{GAE}}_0 = \delta_0 + (\gamma\lambda)\delta_1 = 1.4 + (0.8\times0.5)(-1.8) = 1.4 + 0.4\times(-1.8) = 1.4 - 0.72 = 0.68$. (2)

Question 5 (12 marks)

(a) (4 marks)

• Form: $F(s,s') = \gamma\Phi(s') - \Phi(s)$ for a real-valued potential $\Phi$ over states (2).
• Guarantee: potential-based shaping preserves the optimal policy (policy invariance) — the set of optimal policies of the shaped MDP equals that of the original (Ng, Harada & Russell) (2).

(b) (4 marks) Adding $+0.1$ for every "closer" move (not potential-based) creates exploitable cycles: e.g. the robot can oscillate/loop to repeatedly gain the shaping bonus, or take a longer meandering path that maximizes distance-decreasing steps rather than reaching the goal fast. It can even avoid the goal to keep farming the bonus. Any concrete reward-hacking loop earns full marks (4).

(c) (4 marks)

• $F = \gamma\Phi(s') - \Phi(s) = 1\times(-4) - (-5) = -4 + 5 = +1$. (2)
• Reason: the shaping term telescopes over any trajectory — its cumulative contribution depends only on start/end potentials (with $\gamma$ weighting), adding a state-only offset to the value function that does not alter the relative ordering of actions, hence the argmax (optimal) policy is unchanged (2).

[
  {"claim":"DQN target = 8.3, Double DQN target = 5.6","code":"gamma=Rational(9,10); r=2; y_dqn=r+gamma*7; y_ddqn=r+gamma*4; result=(y_dqn==Rational(83,10)) and (y_ddqn==Rational(56,10))"},
  {"claim":"REINFORCE update gives theta0=-0.0125, theta1=ln3+0.0125","code":"alpha=Rational(1,10); Gb=Rational(1,2); grad0=Rational(-1,4); grad1=Rational(1,4); t0=0+alpha*Gb*grad0; t1=alpha*Gb*grad1; result=(t0==Rational(-1,80)) and (t1==Rational(1,80))"},
  {"claim":"PPO L values: 3.6 for A=3,rho=1.5 and -3.0 for A=-2,rho=1.5","code":"def clip(x,lo,hi): return Max(lo,Min(hi,x))\nrho=Rational(3,2); eps=Rational(1,5)\nL1=Min(rho*3, clip(rho,1-eps,1+eps)*3)\nL2=Min(rho*(-2), clip(rho,1-eps,1+eps)*(-2))\nresult=(L1==Rational(18,5)) and (L2==-3)"},
  {"claim":"A2C: A1step=1.4, A2step=-0.04, GAE=0.68","code":"g=Rational(8,10); d0=1+g*3-2; A2=1+g*0+g**2*Rational(3,2)-2; d1=0+g*Rational(3,2)-3; lam=Rational(1,2); gae=d0+(g*lam)*d1; result=(d0==Rational(7,5)) and (A2==Rational(-1,25)) and (gae==Rational(17,25))"}
]