Reinforcement Learning · Quiz 2 · Jan 2025

**1. Review the numerical answer instructions:** Question 157 states the formatting instructions for numerical answer type questions. Selecting **"Instructions has been mentioned above."** acknowledges these instructions. **Answer: Option A** A: **Correct:** Acknowledges the exam instructions stated above. B: **Incorrect:** Standard exam procedure requires selecting the first option to confirm the instructions.

**1. Recall the on-policy SARSA update rule and algorithm flow:** The SARSA update for state-action value $Q(s, a)$ is: $$Q(s, a) \leftarrow Q(s, a) + \alpha\big[r + \gamma Q(s', a') - Q(s, a)\big]$$ Because $Q(s', a')$ is required inside the TD target to perform the update of $Q(s, a)$, the next action $a'$ in state $s'$ must be sampled from the current policy **before updating $Q(s, a)$** (and that exact sampled action $a'$ is then executed on the next time step). **Answer: Option A** A: **Correct:** In SARSA, $a'$ is sampled from the policy at state $s'$ before computing the TD error and updating $Q(s, a)$. B: **Incorrect:** $Q(s, a)$ cannot be updated without first knowing $a'$, because $Q(s', a')$ appears in the update target. C: **Incorrect:** Sampling $a'$ twice would violate the on-policy SARSA algorithm, which executes the same $a'$ used in the update. D: **Incorrect:** $a'$ is sampled once before the update and then directly taken at the next step. E: **Incorrect:** Option A is accurate.

**1. Evaluate each statement about $\text{TD}(\lambda)$ learning:** - **Option A:** $\text{TD}(\lambda)$ uses an **exponentially decaying** ($(1-\lambda)\lambda^{n-1}$) weighted average of $n$-step returns (the $\lambda$-return), and in its backward-view implementation updates at every step using eligibility traces rather than a generic arbitrary weighted average. - **Option B:** In the backward view (online $\text{TD}(\lambda)$), updates can be performed at every step using eligibility traces; moreover, $\lambda = 1$ corresponds to $\text{TD}(1)$ (Monte Carlo equivalence in offline/episodic updates). - **Option C:** When $\lambda = 0$, the $\lambda$-return $G_t^\lambda = (1 - \lambda)\sum_{n=1}^\infty \lambda^{n-1} G_{t:t+n}$ places $100\%$ of the weight on the 1-step return $G_{t:t+1} = R_{t+1} + \gamma V(S_{t+1})$, and the eligibility trace decays immediately to $0$ after one step. Thus, **$\text{TD}(\lambda)$ with $\lambda = 0$ reduces to one-step TD learning ($\text{TD}(0)$)**. (**Correct**) - **Option D:** $\lambda = 0.5$ is not guaranteed to always converge faster than $\text{TD}(0)$ across all environments and learning rates. **Answer: Option C** A: **Incorrect:** Only the specific $(1-\lambda)\lambda^{n-1}$ geometric weighting defines the forward view of $\text{TD}(\lambda)$, and Option C is the exact, unambiguous property. B: **Incorrect:** Online backward-view $\text{TD}(\lambda)$ updates on every step, not only at the end of an episode. C: **Correct:** Setting $\lambda = 0$ in $\text{TD}(\lambda)$ gives $\text{TD}(0)$, which is one-step TD learning. D: **Incorrect:** The optimal value of $\lambda$ for convergence speed depends on the task and step size.

**1. Understand the role of the eligibility trace $e_t(s)$ or $e_t(s, a)$ in $\text{TD}(\lambda)$:** In the backward view of $\text{TD}(\lambda)$, an **eligibility trace** is a short-term memory vector/table that tracks how recently and frequently each state (or state-action pair) has been visited, **determining which states or state-action pairs are eligible for credit assignment (updates)** when a TD error $\delta_t$ occurs, and by what proportion. **Answer: Option C** A: **Incorrect:** Eligibility traces store a single decaying recency/frequency scalar per state-action pair (or parameter), not a full replay buffer of past observations. B: **Incorrect:** The learning rate $\alpha$ is a separate hyperparameter; the trace scales the TD error based on recency/frequency of visits. C: **Correct:** The eligibility trace tracks recently visited state-action pairs to determine which pairs are eligible for updates when a TD error occurs. D: **Incorrect:** Eligibility traces record state/action visitation recency (decayed by $\gamma\lambda$), not a history of rewards.

**1. Compare $n$-step TD prediction with one-step $\text{TD}(0)$ prediction:** - One-step TD updates $V(S_t)$ using only the immediate next reward $R_{t+1}$ and the bootstrap estimate $\gamma V(S_{t+1})$, so reward information propagates backward by only one state per visit. - **$n$-step TD prediction** uses the $n$-step return $G_{t:t+n} = R_{t+1} + \gamma R_{t+2} + \dots + \gamma^{n-1}R_{t+n} + \gamma^n V(S_{t+n})$, allowing it to **handle delayed rewards and assign credit over multiple ($n$) time steps** at once. **Answer: Option B** A: **Incorrect:** $n$-step TD actually requires *more* memory than 1-step TD because it must store the last $n$ states and rewards. B: **Correct:** Looking $n$ steps ahead allows $n$-step TD to propagate delayed rewards and assign credit across $n$ time steps in a single update. C: **Incorrect:** TD prediction evaluates a fixed policy; it does not by itself find an optimal policy. D: **Incorrect:** Too large a learning rate $\alpha$ can cause $n$-step TD to diverge.

**1. Recall the motivation and mechanism of Double Q-learning:** Standard Q-learning suffers from **maximization bias** (overestimation of action values) because it uses the same noisy estimates both to *select* the maximizing action and to *evaluate* its value ($\max_{a'} Q(s', a')$). **Double Q-learning** maintains two independent estimates $Q_1$ and $Q_2$, using one to select the greedy action and the other to evaluate it, which eliminates maximization bias and **reduces the variance/instability in action-value estimates, leading to more stable learning**. **Answer: Option A** A: **Correct:** By decoupling action selection from action evaluation, Double Q-learning mitigates overestimation and reduces variance/instability in action-value estimates. B: **Incorrect:** No Q-learning variant is guaranteed to converge to the global optimum under general non-linear function approximation. C: **Incorrect:** Because Double Q-learning splits updates between two Q-tables/networks, it typically requires at least as many samples as standard Q-learning. D: **Incorrect:** Double Q-learning still requires standard hyperparameter tuning.

**1. Analyze the Copter Bird problem setting:** In this easy variant of Copter Bird, the obstacles (pipes) are placed **quite far away from each other**, and the bird has a low horizontal velocity. - Consequently, across most time steps (when the bird is flying in open space far from any obstacle), the **choice of action (UP, DOWN, or do nothing) has very little immediate effect on the expected return**; what matters most is the value of the **state** $V(s)$ itself, whereas action advantages $A(s, a)$ only matter near the pipe gaps. - **Dueling DQN** explicitly decomposes $Q(s, a) = V(s) + \big(A(s, a) - \frac{1}{|\mathcal{A}|}\sum_{a'} A(s, a')\big)$ into a state-value stream $V(s)$ and an advantage stream $A(s, a)$, allowing the network to learn the value of states $V(s)$ efficiently without having to wait to experience every action in every state! **Answer: Option D** A: **Incorrect:** Expected SARSA is a tabular/general update rule rather than the deep architecture specifically designed for states where actions rarely affect value. B: **Incorrect:** Standard DQN must learn $Q(s, a)$ separately for each action even when actions make little difference far from obstacles. C: **Incorrect:** Double DQN addresses overestimation bias, whereas Dueling DQN addresses state-value estimation when many states are action-agnostic. D: **Correct:** Dueling DQN separates state value $V(s)$ from action advantage $A(s, a)$, which excels in environments where actions do not significantly affect outcomes across many time steps.

**1. Understand the linear approximator view of a Deep Q-Network (DQN):** - The network has 3 layers of nodes with IDs **`0` (input layer, 3 nodes)**, **`1` (hidden layer, 4 nodes)**, and **`2` (output layer, 2 nodes for the action values $Q(s, a)$)**. - In the linear function approximator view of a DQN, the final output layer (layer `2`) computes a linear combination of the learned feature representation $\phi(s)$: $$Q(s, a) = w_a^T \phi(s)$$ - These state features $\phi(s)$ are the activations produced by the **penultimate layer (the last hidden layer before the output layer)**, which is **layer `1`**. **Answer: 1**

**1. Compute the return $G$ from the first (and only) visit to state $B$ in each of the 8 episodes:** In all 8 episodes, state $B$ is visited once right before termination, so the return from $B$ is simply the immediate terminal reward after $B$: - Episode 1 (`A, 2, B, 0`): return from $B$ is $0$ - Episode 2 (`A, 0, B, 1`): return from $B$ is $1$ - Episode 3 (`A, 2, B, 0`): return from $B$ is $0$ - Episode 4 (`A, 2, B, 0`): return from $B$ is $0$ - Episode 5 (`B, 1`): return from $B$ is $1$ - Episode 6 (`B, 0`): return from $B$ is $0$ - Episode 7 (`B, 1`): return from $B$ is $1$ - Episode 8 (`B, 3`): return from $B$ is $3$ **2. Average the 8 returns for $V(B)$:** $$V(B) = \frac{0 + 1 + 0 + 0 + 1 + 0 + 1 + 3}{8} = \frac{6}{8} = 0.75$$ **Answer: 0.75**

**1. Identify all episodes in which state $A$ is visited and compute the discounted return ($\gamma = 0.8$):** State $A$ is visited in the first 4 episodes: - **Episode 1 (`A, 2, B, 0`):** $$G_1 = 2 + 0.8(0) = 2.0$$ - **Episode 2 (`A, 0, B, 1`):** $$G_2 = 0 + 0.8(1) = 0.8$$ - **Episode 3 (`A, 2, B, 0`):** $$G_3 = 2 + 0.8(0) = 2.0$$ - **Episode 4 (`A, 2, B, 0`):** $$G_4 = 2 + 0.8(0) = 2.0$$ **2. Average the 4 returns for First-Visit MC estimate of $V(A)$:** $$V(A) = \frac{2.0 + 0.8 + 2.0 + 2.0}{4} = \frac{6.8}{4} = 1.70$$ **Answer: 1.70**

**1. Understand Batch $\text{TD}(0)$ (Certainty-Equivalence / Maximum Likelihood MDP):** Batch $\text{TD}(0)$ converges to the exact value function of the empirical Markov chain formed by the observed transitions. - From state $B$, all $8$ transitions go directly to the terminal state with rewards $0, 1, 0, 0, 1, 0, 1, 3$. - Therefore, the batch $\text{TD}(0)$ estimate of $V(B)$ is the average immediate reward from $B$: $$V(B) = \frac{0 + 1 + 0 + 0 + 1 + 0 + 1 + 3}{8} = \frac{6}{8} = 0.75$$ **Answer: 0.75**

**1. Compute the Batch $\text{TD}(0)$ estimate of $V(A)$ ($\gamma = 0.8$):** Batch $\text{TD}(0)$ satisfies the certainty-equivalence Bellman equation using the empirical transition probabilities and empirical mean reward from state $A$, bootstrapping on the batch $\text{TD}(0)$ estimate $V(B) = 0.75$: - In all $4$ episodes starting at $A$, state $A$ transitions $100\%$ of the time to state $B$, with rewards $2, 0, 2, 2$. - The average immediate reward from $A$ is: $$\bar{R}(A) = \frac{2 + 0 + 2 + 2}{4} = \frac{6}{4} = 1.5$$ - Bootstrapping on $V(B) = 0.75$ with discount factor $\gamma = 0.8$: $$V(A) = \bar{R}(A) + \gamma V(B) = 1.5 + 0.8(0.75) = 1.5 + 0.6 = 2.10$$ **Answer: 2.10**

**1. Check the definition of a linear function approximator:** A value function approximator $V(s; w)$ is **linear** if it is a linear function of the **weight vector $w = (w_0, w_1, w_2, w_3)^T$**, i.e., if it can be written as the inner product of $w$ and a feature vector $\phi(s)$: $$V(s; w) = w_0 + w_1 s + w_2 s^2 + w_3 s^3 = \sum_{i=0}^3 w_i \phi_i(s) = w^T \phi(s)$$ where $\phi(s) = (1, s, s^2, s^3)^T$. Even though the features $\phi_i(s) = s^i$ are polynomial (non-linear) in the scalar state $s$, $V(s; w)$ is strictly linear in the parameters $w$. Thus, the statement is **TRUE**. **Answer: Option A** A: **Correct:** Linearity of a function approximator means linearity in the learnable parameters $w$, and $V(s; w) = w^T (1, s, s^2, s^3)$ is linear in $w$. B: **Incorrect:** Non-linearity in the state variable $s$ (polynomial features $s^2, s^3$) does not make the approximator non-linear in $w$.

**1. Understand the semi-gradient $\text{TD}(0)$ update:** Given the $\text{TD}(0)$ error: $$\delta = \underbrace{r}_{\text{①}} + \underbrace{\gamma V(S'; w)}_{\text{②}} - \underbrace{V(S; w)}_{\text{③}}$$ In **semi-gradient** $\text{TD}(0)$, when computing the gradient of the squared TD error $\delta^2$ with respect to $w$, we treat the **TD target $U_t = r + \gamma V(S'; w)$** as a fixed constant target (ignoring the dependence of $V(S'; w)$ on $w$) and only differentiate $-V(S; w)$: $$\frac{1}{2}\nabla_w \delta^2 \approx -\delta \nabla_w V(S; w)$$ Therefore, both **① ($r$)** and **② ($\gamma V(S'; w)$)** are treated as constants, while **③ ($V(S; w)$)** is differentiated with respect to $w$. **Answer: Options A, B** A: **Correct:** The reward $r$ (①) does not depend on $w$ and is a constant during gradient computation. B: **Correct:** In semi-gradient TD(0), the bootstrap term $\gamma V(S'; w)$ (②) is held constant (stop-gradient) when differentiating $\delta^2$. C: **Incorrect:** $V(S; w)$ (③) is the current state's value estimate, which IS differentiated with respect to $w$.

**1. Write the semi-gradient $\text{TD}(0)$ update rule:** Using the semi-gradient approximation $\nabla_w \delta^2 = -2\delta \nabla_w V(S; w)$, the update rule $w_{t+1} = w_t - \frac{\alpha}{2}\nabla_w \delta^2$ becomes: $$w_{t+1} = w_t + \alpha \delta \nabla_w V(S; w)$$ where $\delta = r + \gamma V(s_2; w_t) - V(s_1; w_t)$ and $\nabla_w V(s; w) = (1, s, s^2, s^3)^T$. **2. Evaluate for the experience $(s_1, a_1, -3, s_2)$ with $s_1 = 1,\; r = -3,\; w_0 = \mathbf{0},\; \alpha = 0.1,\; \gamma = 0.9$:** - Since initially $w_0 = \mathbf{0}$, we have $V(s_1; w_0) = 0$ and $V(s_2; w_0) = 0$. - Therefore, the TD error is: $$\delta = -3 + 0.9(0) - 0 = -3$$ - At $s_1 = 1$, the feature gradient vector is: $$\nabla_w V(s_1; w) = (1, 1^1, 1^2, 1^3)^T = (1, 1, 1, 1)^T$$ - The updated weight vector is: $$w_1 = \mathbf{0} + (0.1)(-3)(1, 1, 1, 1)^T = (-0.3, -0.3, -0.3, -0.3)^T$$ **3. Sum the components of the updated weight vector $w_1$:** $$\sum_{i=0}^3 w_{1,i} = -0.3 - 0.3 - 0.3 - 0.3 = -1.2$$ **Answer: -1.2**

**1. Recall the updated weight vector $w$ from Question 171 and state $s_2 = -2$:** From Question 171: $$w = (w_0, w_1, w_2, w_3)^T = (-0.3, -0.3, -0.3, -0.3)^T$$ We are given $s_2 = -2$. **2. Evaluate $V(s_2; w) = w_0 + w_1 s_2 + w_2 s_2^2 + w_3 s_2^3$:** - $s_2 = -2$ - $s_2^2 = (-2)^2 = 4$ - $s_2^3 = (-2)^3 = -8$ Substitute into $V(s_2; w)$: $$V(-2; w) = -0.3(1) + (-0.3)(-2) + (-0.3)(4) + (-0.3)(-8)$$ $$V(-2; w) = -0.3(1 - 2 + 4 - 8) = -0.3(-5) = 1.5$$ **Answer: 1.5**

**1. Compute $\frac{\nabla \pi_\theta(a_t)}{\pi_\theta(a_t)}$ for both actions $a_t = 1$ and $a_t = 0$:** Given $\pi(\theta, a) = \begin{cases} \theta, & \text{if } a = 1 \\ 1 - \theta, & \text{if } a = 0 \end{cases}$: - **If $a = 1$:** $\pi(\theta, 1) = \theta$, so $\frac{d}{d\theta}\pi(\theta, 1) = 1$, giving: $$\frac{\nabla \pi_\theta(1)}{\pi_\theta(1)} = \frac{1}{\theta}$$ - **If $a = 0$:** $\pi(\theta, 0) = 1 - \theta$, so $\frac{d}{d\theta}\pi(\theta, 0) = -1$, giving: $$\frac{\nabla \pi_\theta(0)}{\pi_\theta(0)} = \frac{-1}{1 - \theta}$$ This piecewise expression matches **Option C** (and shows Option A is incorrect because of the missing minus sign for $a = 0$). **2. Combine into a single algebraic formula for $a \in \{0, 1\}$:** Check $\frac{a - \theta}{\theta(1 - \theta)}$: - For $a = 1$: $\frac{1 - \theta}{\theta(1 - \theta)} = \frac{1}{\theta}$. - For $a = 0$: $\frac{0 - \theta}{\theta(1 - \theta)} = \frac{-1}{1 - \theta}$. Thus, **Option B** ($\frac{a - \theta}{\theta(1 - \theta)}$) is also equivalent! **Answer: Options B, C** A: **Incorrect:** For $a = 0$, the derivative of $1 - \theta$ with respect to $\theta$ is $-1$, not $+1$. B: **Correct:** Substituting $a = 1$ gives $1/\theta$ and substituting $a = 0$ gives $-1/(1-\theta)$. C: **Correct:** Directly expresses $\frac{\nabla \pi_\theta(a)}{\pi_\theta(a)}$ for $a = 1$ and $a = 0$. D: **Incorrect:** For $a = 1$, $(1 + \theta)/(\theta(1 - \theta)) \ne 1/\theta$.

**1. Differentiate $\ln \pi(\Theta, a_i)$ with respect to $\theta_j$ for $j \ne i$:** Using the log-derivative identity $\frac{\nabla \pi(\Theta, a_i)}{\pi(\Theta, a_i)} = \nabla \ln \pi(\Theta, a_i)$: $$\ln \pi(\Theta, a_i) = \ln\left(\frac{e^{\theta_i}}{\sum_{k=1}^n e^{\theta_k}}\right) = \theta_i - \ln\left(\sum_{k=1}^n e^{\theta_k}\right)$$ Now take the partial derivative with respect to $\theta_j$ where $j \ne i$ (so $\frac{\partial \theta_i}{\partial \theta_j} = 0$): $$\left[\frac{\nabla \pi(\Theta, a_i)}{\pi(\Theta, a_i)}\right]_j = \frac{\partial}{\partial \theta_j}\left(\theta_i - \ln\sum_{k=1}^n e^{\theta_k}\right) = 0 - \frac{e^{\theta_j}}{\sum_{k=1}^n e^{\theta_k}} = -\pi(\Theta, a_j)$$ **Answer: Option B** A: **Incorrect:** $1 - \pi(\Theta, a_i)$ is the $i^{\text{th}}$ component (where $j = i$), not $j \ne i$. B: **Correct:** For any $j \ne i$, $\frac{\partial}{\partial \theta_j} \ln \pi(\Theta, a_i) = -\pi(\Theta, a_j)$. C: **Incorrect:** For $j \ne i$, the derivative is $-\pi(\Theta, a_j)$, not $1 - \pi(\Theta, a_j)$. D: **Incorrect:** Differentiating with respect to $\theta_j$ puts $e^{\theta_j}$ in the numerator, giving $-\pi(\Theta, a_j)$, not $-\pi(\Theta, a_i)$.

**1. Analyze the REINFORCE update when $b$ is a very large positive scalar ($b \gg r_t$):** From Question 174, for the sampled action $a_t = a_i$, the components of the score function $\frac{\nabla \pi(\Theta, a_i)}{\pi(\Theta, a_i)}$ are: - $1 - \pi(\Theta, a_i) > 0$ for the chosen action $a_i$, and - $-\pi(\Theta, a_j) < 0$ for all unchosen actions $a_j$ ($j \ne i$). When $b$ is a very large positive scalar such that $r_t - b < 0$ is always **negative** on every step: - The update for the chosen action $a_i$ is $\Delta \theta_i = \alpha(r_t - b)(1 - \pi(\Theta, a_i)) < 0$, which **decreases** the preference $\theta_i$ of whichever action was just taken! - The update for every other action $a_j$ ($j \ne i$) is $\Delta \theta_j = \alpha(r_t - b)(-\pi(\Theta, a_j)) > 0$, which **increases** the preferences of the actions not taken! **2. Conclude the limiting policy:** Because any action with a higher probability of being selected gets penalized more frequently and pushed down while less-probable actions get pushed up, the action probabilities are driven toward equality ($\pi(\Theta, a_1) = \dots = \pi(\Theta, a_n) = \frac{1}{n}$), converging to the **Uniform Random Policy**. **Answer: Option B** A: **Incorrect:** Because $r_t - b < 0$ is always negative, taken actions are penalized rather than reinforced toward the optimal arm. B: **Correct:** Since $r_t - b < 0$ penalizes whichever action is sampled and boosts unsampled actions, higher-probability actions are pushed down until the policy converges to a Uniform Random Policy. C: **Incorrect:** The limiting behavior is well-determined from the softmax gradient equations.

**1. Analyze the theoretical validity of making the step size $\alpha$ depend on the current reward $r_t$:** In stochastic gradient ascent (REINFORCE), the unbiasedness of the policy gradient relies on the step size $\alpha_t$ being conditionally independent of the stochastic sample return/reward $r_t$ given the current parameters $\theta_t$: $$\mathbb{E}[\alpha \cdot r_t \nabla \ln \pi_\theta(a_t)] = \alpha \, \mathbb{E}[r_t \nabla \ln \pi_\theta(a_t)] = \alpha \nabla J(\theta)$$ If $\alpha(r_t)$ is a function of the random reward $r_t$ (e.g., increasing $\alpha$ when $r_t$ is high), then $\alpha(r_t) r_t$ nonlinearly distorts the reward function (effectively optimizing a distorted objective $\mathbb{E}[\alpha(r_t)r_t]$ rather than $\mathbb{E}[r_t]$) and biases the gradient estimate, so it is **not a valid** way to guarantee convergence to the optimal policy of the original problem (**No**). **Answer: Option B** A: **Incorrect:** Making $\alpha$ depend on the stochastic reward $r_t$ introduces bias into the stochastic gradient update and changes the objective function. B: **Correct:** In stochastic approximation, the learning rate $\alpha$ must not depend on the noisy sample reward $r_t$; otherwise the gradient estimate becomes biased.

**1. Sum the total number of tiles across the 3 grid-tilings:** In tile coding, each tile in each grid-tiling corresponds to one binary feature (component) in the discretized state vector $\hat{s} \in \{0, 1\}^d$. We have 3 grid-tilings: - **Blue tiling:** $2 \times 2 = 4$ tiles - **Black tiling:** $3 \times 3 = 9$ tiles - **Brown tiling:** $4 \times 4 = 16$ tiles **2. Compute the total length $d$ of the binary feature vector:** $$d = 4 + 9 + 16 = 29$$ **Answer: 29**

**1. Determine how many tiles are active (ON) for any state $s \in \mathbb{R}^2$:** - Each of the 3 grid-tilings (Blue $2 \times 2$, Black $3 \times 3$, and Brown $4 \times 4$) partitions the bounded state space into non-overlapping tiles. - Therefore, any continuous state $s \in \mathbb{R}^2$ falls into **exactly 1 tile** in the Blue tiling, **exactly 1 tile** in the Black tiling, and **exactly 1 tile** in the Brown tiling. - Thus, for any state $s$, the number of ON bits (1s) in $\hat{s}$ is constant and equal to the number of tilings: $$1 + 1 + 1 = 3$$ **Answer: 3**