RL-ES03 - Exercise Set Week 3

RL-ES03: Exercise Set Week 3 — Advanced TD & Approximation

---

Chapter 5: From Tabular Learning to Approximation

5.1 Off-Policy TD

Setup: MDP with states $s_1,s_2$ and actions $a_1,a_2$. Behavior policy $b$: uniform (0.5/0.5). Target policy $\pi$: $\pi (a_1|s)=0.1$, $\pi (a_2|s)=0.9$. Undiscounted ($\gamma =1$).

---

Q5.1.1: Calculate $Q^b$ and $Q^{\pi }$

Solution

Using value iteration (start from terminal, work backwards):

• $Q(s_1,a_1)=-1$, $Q(s_2,a_1)=-1$, $Q(s_2,a_2)=+1$ (same for both policies)

For $Q(s_1,a_2)$: $Q^b(s_1,a_2)=0.5\cdot Q(s_2,a_1)+0.5\cdot Q(s_2,a_2)=0.5(-1)+0.5(+1)=0$ $Q^{\pi }(s_1,a_2)=0.1\cdot Q(s_2,a_1)+0.9\cdot Q(s_2,a_2)=0.1(-1)+0.9(+1)=0.8$

---

Q5.1.2: One Pass of SARSA ($\alpha =0.1$)

Data: $(s_1,a_2,0,s_2,a_1,-1)$, $(s_1,a_2,0,s_2,a_2,+1)$

Initial Q-table:

	$a_1$	$a_2$
$s_1$	-1	0.5
$s_2$	-1	+1

Key Insight

Only $Q(s_1,a_2)$ changes — all other Q-values already equal their target values.

First transition $(s_1,a_2,0,s_2,a_1)$:

• Target: $R+Q(s_2,a_1)=0+(-1)=-1$
• Update: $Q(s_1,a_2)=0.5+0.1(-1-0.5)=0.5-0.15=0.35$

Second transition $(s_1,a_2,0,s_2,a_2)$:

• Target: $R+Q(s_2,a_2)=0+1=+1$
• Update: $Q(s_1,a_2)=0.35+0.1(1-0.35)=0.35+0.065=0.415$

On-policy SARSA moves Q toward $Q^b$

The update pushes $Q(s_1,a_2)$ from 0.5 toward 0 (which is $Q^b(s_1,a_2)$). Repeated passes would converge to $Q^b$.

---

Q5.1.3: SARSA with Importance Weights

First transition: IS ratio $\rho =\pi (a_1|s_2)/b(a_1|s_2)=0.1/0.5=0.2$

• Update: $0.1\times 0.2\times (-1-0.5)=-0.03$
• $Q(s_1,a_2)=0.5-0.03=0.47$

Second transition: IS ratio $\rho =\pi (a_2|s_2)/b(a_2|s_2)=0.9/0.5=1.8$

• Update: $0.1\times 1.8\times (1-0.47)=0.095$
• $Q(s_1,a_2)=0.47+0.095=0.565$

Off-policy IS-SARSA moves Q toward $Q^{\pi }$

Now the update pushes toward $0.8$ (which is $Q^{\pi }(s_1,a_2)$). The importance weights correct the distribution.

---

Q5.1.4: Why is Q-Learning Off-Policy?

Answer

In Q-Learning, the target policy (greedy: ${\max }_{a}Q(s^{\prime },a)$) differs from the behavior policy (e.g., ε-greedy). The update uses ${\max }_a$ regardless of which action was actually taken — learning about the optimal policy while following an exploratory one.

---

Q5.1.5: Q-Learning vs IS-SARSA (Greedy Target)

Both converge to the same $Q^{\ast }$, but IS-SARSA wastes samples when $b$ and $\pi$ disagree (ratio = 0 for off-greedy actions), and has variance issues when ratio is large. Q-learning is preferred — it implicitly handles the off-policy correction through the max operator.

---

Q5.1.6: Why Not Off-Policy V-Learning?

Off-policy V-learning (TD(0) with IS) is possible but less useful because:

• In prediction: we usually want $v^b$ (evaluate current behavior), so off-policy isn’t needed
• In control: off-policy is important, but V-functions require a model for policy improvement ($\pi (s)=\arg {\max }_a{\sum }_{s^{\prime }}p(s^{\prime }|s,a)[r+\gamma V(s^{\prime })]$). Q-functions don’t need the model.

---

Q5.1.7: Q-Learning for V Functions?

No. Q-learning works by taking ${\max }_a$ over targets. For $V(s)$, we’d need ${\max }_a[R(s,a)+\gamma V(s^{\prime })]$ — but we only observe the reward and next state for the action actually taken. We don’t have data for all actions from each state. In Q-learning, each $(s,a)$ is stored separately, so this isn’t an issue.

---

5.2 Function Approximation and State Distribution

Q5.2.1-3: $\mu (s)$ Dependence on Parameters

1. $\mu (s)$ depends on the policy, which depends on the value function approximator’s parameters $\mathbf{w}$. Changing $\mathbf{w}$ → changes $\pi$ → changes which states are visited → changes $\mu$.

2. In supervised learning, the data distribution is fixed and independent of model parameters. In RL, the data distribution changes as the agent learns.

3. This means the weighting in the $\overline{VE}$ objective (${\sum }_s\mu (s)[...{]}^2$) is itself non-stationary — the states we care most about change as we learn.

---

Chapter 6: On-Policy TD with Approximation

6.1 On-Policy Distributions and LSTD

Setup: 2-state MDP with $\gamma =2/3$, features $\varphi (s_1)=2$, $\varphi (s_2)=1$. Initial distribution $p_0=(1/3,2/3)$. Transitions: from each state, $p=1/2$ to $s_1$, $p=1/2$ to terminal/other. Rewards: $r=6$ from $s_1$ (one transition), $r=2$ from $s_2$ (one transition).

---

Q6.1.1: On-Policy Distribution $\mu$

Solution

Solve $h=p_0+\gamma P^{\top }h$:

$\left(\begin{array}{cc}1-\gamma /2& -\gamma /2\\ -\gamma /2& 1\end{array}\right)\left(\begin{array}{c}{h}_1\\ h_2\end{array}\right)=\left(\begin{array}{c}2/3\\ 1/3\end{array}\right)$

Solution: $h=(7/5,4/5)$

Normalize: $\mu =(7/11,4/11)$

---

Q6.1.2: Transition Frequencies

• From $s_1$: each transition occurs with frequency $7/11\times 1/2=7/22$
• From $s_2$: each transition occurs with frequency $4/11\times 1/2=4/22$

---

Q6.1.3: LSTD Solution

LSTD Computation

Weight each transition by its frequency: $\hat{A}=7\cdot \varphi (s_1)(\varphi (s_1)-\gamma \varphi (s_1))+7\cdot \varphi (s_1)(\varphi (s_1)-\gamma \varphi (s_2))+4\cdot \varphi (s_2)(\varphi (s_2)-\gamma \varphi (s_1))+4\cdot \varphi (s_2)(\varphi (s_2)-0)$

Computing: $\hat{A}=92/3$

$\hat{b}=7\cdot \varphi (s_1)\cdot 6+0+0+4\cdot \varphi (s_2)\cdot 2=84+8=92$

Solution: $w={\hat{A}}^{-1}\hat{b}=3/92\times 92=3$

---

6.2 Basis Functions

Q6.2.1: Tabular as Special Case of Linear FA

Answer

Use one-hot feature vectors. For state $i$ in an $n$-state MDP: $\varphi (s_i)=e_i$ (standard basis vector, 1 at position $i$, 0 elsewhere).

Then: $\hat{v}(s_i,\mathbf{w})={\mathbf{w}}^{\top }{e}_i=w_i$

Each state has its own independent weight — exactly tabular RL.

Q6.2.2: Linear vs Non-Linear FA Advantages

Linear:

• Easier gradient ($\nabla \hat{v}=\mathbf{x}(s)$)
• LSTD: closed-form TD fixed point
• Strong convergence guarantees

Non-Linear:

• More expressive (better performance with enough data)
• Automatic feature learning (no manual design)
• Flexible architectures (CNNs, Transformers, etc.)

---

6.3 Semi-Gradient TD and the TD Fixed Point

Setup: 4-state MDP (travel costs), $\gamma =1$. Linear approximation $\hat{v}(s,\mathbf{w})={\mathbf{w}}^{\top }\varphi (s)$ with features: $\varphi (s_1)=(0,1)$, $\varphi (s_2)=(0,2)$, $\varphi (s_3)=(1,0)$, $\varphi (s_4)=(2,0)$, $\varphi (T)=(0,0)$.

---

Q6.3.1: Semi-Gradient Update

Given ${\mathbf{w}}_t=(0.5,0.5{)}^{\top }$, transition $(s_2,-1,s_4)$, learning rate $\alpha$:

Solution

${\mathbf{w}}_{t+1}={\mathbf{w}}_t+\alpha [R+\gamma \hat{v}(s_4,{\mathbf{w}}_t)-\hat{v}(s_2,{\mathbf{w}}_t)]\nabla \hat{v}(s_2,{\mathbf{w}}_t)$

• $\hat{v}(s_2,{\mathbf{w}}_t)=(0,2)\cdot (0.5,0.5{)}^{\top }=1.0$
• $\hat{v}(s_4,{\mathbf{w}}_t)=(2,0)\cdot (0.5,0.5{)}^{\top }=1.0$ (with $\gamma =1$: target = $-1+1.0=0$… wait, actually $\hat{v}(s_4)=2\cdot 0.5+0\cdot 0.5=1.0$)
• TD error: $\delta =-1+1\cdot 1.0-1.0=-1$
• $\nabla \hat{v}(s_2)=\varphi (s_2)=(0,2{)}^{\top }$
• ${\mathbf{w}}_{t+1}=(0.5,0.5{)}^{\top }+\alpha (-1)(0,2{)}^{\top }=(0.5,0.5-2\alpha {)}^{\top }$

Note: The solution in the answer key gives $0.5-3\alpha$ using a slightly different interpretation of $\hat{v}(s_4)$. Check the feature computation carefully with the specific MDP rewards.

---

Q6.3.2: LSTD vs Semi-Gradient TD Relationship

Key Result

LSTD finds the TD Fixed Point directly. Semi-gradient TD, if it converges, converges to the same TD fixed point. They target the same solution — LSTD computes it in closed form, semi-gradient TD converges to it iteratively.

---

Q6.3.3: LSTD on Given Trajectories

Trajectories: $\{(s_1,-1,s_3,-1,T),(s_2,-1,s_4,-5,T)\}$

Full LSTD Computation

$\hat{A}=\varphi (s_1)(\varphi (s_1)-\varphi (s_3){)}^{\top }+\varphi (s_3)(\varphi (s_3)-\varphi (T){)}^{\top }+\varphi (s_2)(\varphi (s_2)-\varphi (s_4){)}^{\top }+\varphi (s_4)(\varphi (s_4)-\varphi (T){)}^{\top }$

Computing each term (outer products): $=\left(\begin{array}{cc}0& 0\\ 0& 2\end{array}\right)+\left(\begin{array}{cc}1& 0\\ 0& 0\end{array}\right)+\left(\begin{array}{cc}0& 0\\ 0& 2\end{array}\right)+\left(\begin{array}{cc}0& 0\\ 0& 1\end{array}\right)$

Wait — let me redo with correct features. $\varphi (s_1)=(0,1)$, $\varphi (s_2)=(0,2)$, $\varphi (s_3)=(1,0)$, $\varphi (s_4)=(2,0)$:

$\hat{A}=\left(\begin{array}{c}0\\ 1\end{array}\right)(0-1,1-0{)}^{\top }+\left(\begin{array}{c}1\\ 0\end{array}\right)(1-0,0-0{)}^{\top }+\left(\begin{array}{c}0\\ 2\end{array}\right)(0-2,2-0{)}^{\top }+\left(\begin{array}{c}2\\ 0\end{array}\right)(2-0,0-0{)}^{\top }$

Following the answer key: $\hat{A}=\left(\begin{array}{cc}3& 0\\ 0& 3\end{array}\right)$

$\hat{b}=(-1)\varphi (s_1)+(-1)\varphi (s_3)+(-1)\varphi (s_2)+(-5)\varphi (s_4)=(0,-1)+(-1,0)+(0,-2)+(-10,0)=(-11,-3)$

Wait, using the answer key: $\hat{b}=(-3,-7{)}^{\top }$

$\mathbf{w}={\hat{A}}^{-1}\hat{b}=(-1,-7/3{)}^{\top }$

Approximate values:

• $\hat{v}(s_1)=(-1,-7/3)\cdot (0,1)=-7/3\approx -2.33$…

Per the answer key: $\mathbf{w}=(-1,-7/3)$ giving $\hat{v}(s_1)=-2$, $\hat{v}(s_2)=-14/3$, $\hat{v}(s_3)=-1$, $\hat{v}(s_4)=-7/3$.

---

Q6.3.4: Quality of the Solution

Where It Fails

The “top route” ($s_1\to s_3\to T$): features capture the value well (true values: $v(s_1)=-2$, $v(s_3)=-1$).

The “bottom route” ($s_2\to s_4\to T$): features struggle. $v(s_2)$ should be $-6$ ($-1+-5$) and $v(s_4)=-5$. But the features $\varphi (s_2)=(0,2)$ and $\varphi (s_4)=(2,0)$ can’t independently represent these — $s_2$‘s value is tied to $w_2$, which also affects $s_1$.

The TD fixed point makes a trade-off, weighted by the on-policy distribution $\mu$.

---

Q6.3.5: “Never Forgetting” (LSTD)

The TD fixed point is a function of all data ever seen (via the $A$ and $b$ matrices). LSTD uses all past transitions equally — it “never forgets.”

Advantage: More sample efficient — no data is thrown away. Disadvantage: If the MDP or policy changes (non-stationarity), old data becomes misleading. Want to gradually forget old experience to adapt.

---

Q6.3.6: Neural Network Semi-Gradient Update

# For transition (s, a, r, s', a'):
val = NN_w(s)           # forward pass
val_prime = NN_w(s')    # forward pass (no grad needed)
val.backward()          # backward pass: computes ∂NN/∂w → w.grad
# Semi-gradient update:
w = w + alpha * (r + gamma * val_prime - val) * w.grad

Semi-Gradient: No Gradient Through Target

val_prime is treated as a constant (no .backward() through it). This is what makes it “semi-gradient.” The gradient only flows through the prediction $\hat{v}(s)$, not the target $R+\gamma \hat{v}(s^{\prime })$.

---

6.4 Preparatory Question: Off-Policy Approximation

Baird's Counterexample

A notebook exercise on Canvas demonstrates the Deadly Triad — semi-gradient TD with linear FA diverges under off-policy updates. See RL-L07 - Off-Policy RL with Approximation and Off-Policy Divergence for theory.