Reinforcement Learning · Quiz 1 · Jan 2025

**1. Review the numerical answer instructions:** Question 191 provides the rounding and formatting instructions for numerical answer type questions in the Reinforcement Learning exam. 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. Evaluate the Assertion:** - **Assertion:** *"Reinforcement learning is a type of unsupervised learning algorithm as both don't have correct labels."* - **False:** In machine learning, **reinforcement learning** is a distinct third paradigm alongside supervised and unsupervised learning. Although RL does not rely on labeled input-output examples like supervised learning, its goal is to maximize cumulative **reward** through trial-and-error interaction with an environment, whereas unsupervised learning discovers hidden structure/patterns in unlabeled data without a reward signal. **2. Evaluate the Reason:** - **Reason:** *"In unsupervised learning, a reward like quantity is not maximized."* - **True:** Unsupervised learning optimizes objectives like reconstruction error, likelihood, or clustering similarity rather than an external environmental reward signal. **Answer: Option D** A: **Incorrect:** The Assertion is false because RL is a separate learning paradigm, not a subset of unsupervised learning. B: **Incorrect:** The Assertion is false. C: **Incorrect:** The Assertion is false and the Reason is true. D: **Correct:** Reinforcement learning is not a type of unsupervised learning (Assertion is false), and unsupervised learning indeed does not maximize a reward signal (Reason is true).

**1. Evaluate the three statements comparing Softmax (Boltzmann) exploration and $\epsilon$-greedy exploration:** - **Statement 1:** Softmax exploration assigns action probabilities proportional to $\exp(Q(a)/\tau)$, grading actions by their estimated $Q$-values so that very poor ('bad') actions get much smaller probability than moderately good actions, whereas $\epsilon$-greedy explores all non-greedy actions uniformly at random. (**Correct**) - **Statement 2:** Softmax exploration **does** require careful tuning and scheduling of the temperature $\tau$; if $\tau$ is decreased too sharply (fast cooling), softmax can prematurely lock into a suboptimal action and fail to converge to the optimal arm. (**Incorrect**) - **Statement 3:** Because action probabilities depend smoothly on $Q$-values via the Boltzmann distribution, softmax distinguishes between near-optimal actions (whose $Q$-values are close to the maximum) and far-suboptimal actions. (**Correct**) Thus, statements **1 and 3** are correct. **Answer: Option E** A: **Incorrect:** Statement 2 is false because a sharp decrease in temperature can cause softmax to get stuck on a suboptimal action. B: **Incorrect:** Statement 1 is also correct. C: **Incorrect:** Statement 3 is also correct. D: **Incorrect:** Statement 2 is false. E: **Correct:** Both Statement 1 and Statement 3 accurately describe advantages of softmax action selection over $\epsilon$-greedy.

**1. Recall the definition of the action-value function $q_\pi(s, a)$ in an MDP:** For a policy $\pi$, the action-value function $q_\pi(s, a)$ is defined as the **expected return** starting from state $s$, taking action $a$ at the first step, and thereafter following policy $\pi$: $$q_\pi(s, a) = \mathbb{E}_\pi\left[G_t \mid S_t = s,\; A_t = a\right]$$ Therefore, $q_\pi(s, a) = 2.5$ means that **the expected return starting from state $s$, taking action $a$ and then following policy $\pi$ is equal to $2.5$**. **Answer: Option B** A: **Incorrect:** This describes the state-value function $v_\pi(s)$, which averages over the initial action $a \sim \pi(\cdot \mid s)$ rather than conditioning on taking action $a$. B: **Correct:** This is the exact definition of the action-value function $q_\pi(s, a) = 2.5$. C: **Incorrect:** $q_\pi(s, a)$ is the expected value over all episodes (and conditions on action $a$), not the realized return in some episodes. D: **Incorrect:** $q_\pi(s, a) = 2.5$ is the expected return, so individual episode returns may never equal exactly $2.5$.

**1. Distinguish between "there exists a deterministic optimal policy" and "all optimal policies are deterministic":** - In any finite MDP, there always **exists** at least one deterministic optimal policy. - However, if a state $s$ has two or more actions $a_1, a_2$ that tie for the maximum optimal action value ($q_*(s, a_1) = q_*(s, a_2) = \max_a q_*(s, a)$), then any **stochastic** policy that assigns positive probabilities (summing to $1$) only to those tying optimal actions $a_1$ and $a_2$ is **also** an optimal policy! - Therefore, it is **FALSE** that *all* optimal policies of a finite MDP are necessarily deterministic. **Answer: Option B** A: **Incorrect:** When multiple actions tie for $\max_a q_*(s, a)$, any probability distribution over those optimal actions forms a stochastic optimal policy. B: **Correct:** While at least one deterministic optimal policy always exists, stochastic policies that mix between tied optimal actions can also be optimal.

**1. Recall the convergence guarantee of Asynchronous Value Iteration:** In Asynchronous Value Iteration (specifically when sweeping over the entire set of states in each iteration in any permutation/order, such as Gauss-Seidel Value Iteration), the Bellman optimality backup operator remains a $\gamma$-contraction in the max-norm. As long as every state is updated in each iteration (so no state is starved), **changing the order of updates does not impact convergence** to the unique optimal value function $v_*$ (**No**). **Answer: Option B** A: **Incorrect:** Updating all states in each iteration in any order still guarantees convergence to $v_*$. B: **Correct:** Because every state is updated in each sweep and the Bellman operator is a contraction, the update order does not affect convergence. C: **Incorrect:** Convergence is guaranteed regardless of the permutation of states in each sweep.

**1. Derive the incremental sample-average update rule:** The sample average of $k$ rewards $r_{i,1}, r_{i,2}, \dots, r_{i,k}$ for arm $a_i$ is: $$Q_k(a_i) = \frac{1}{k}\sum_{j=1}^k r_{i,j} = \frac{1}{k}\left(r_{i,k} + (k - 1)Q_{k-1}(a_i)\right) = Q_{k-1}(a_i) + \frac{1}{k}\big(r_{i,k} - Q_{k-1}(a_i)\big)$$ Comparing this with $Q_k(a_i) = Q_{k-1}(a_i) + \alpha\big(r_{i,k} - Q_{k-1}(a_i)\big)$, the step-size parameter that yields exact sample averaging is: $$\alpha = \frac{1}{k}$$ **Answer: Option A** A: **Correct:** Setting $\alpha = 1/k$ makes $Q_k(a_i)$ the exact arithmetic mean of the first $k$ rewards. B: **Incorrect:** $\alpha = 1/(k-1)$ is undefined at $k = 1$ and weights recent rewards too heavily. C: **Incorrect:** $\alpha = 1/(k+1)$ underweights the $k$ rewards when $Q_0(a_i) = 0$. D: **Incorrect:** $\alpha = 1/k$ is given in Option A.

**1. State the UCB1 action-selection formula:** At trial $t = 100$ with $c = 1$, the Upper Confidence Bound (UCB) index for each arm $i$ is: $$\text{UCB}_i = Q_{100}(i) + c\sqrt{\frac{2\ln t}{n_i}} = Q_{100}(i) + \sqrt{\frac{2\ln(100)}{n_i}}$$ where $2\ln(100) \approx 2 \times 4.60517 = 9.21034$, so $\sqrt{2\ln(100)} \approx 3.03485$. **2. Compute the UCB index for each of the 4 arms:** - **Arm 1 ($Q = 2.5,\; n_1 = 25$):** $$\text{UCB}_1 = 2.5 + \frac{3.03485}{\sqrt{25}} = 2.5 + \frac{3.03485}{5} = 2.5 + 0.6070 = 3.1070$$ - **Arm 2 ($Q = 2.8,\; n_2 = 24$):** $$\text{UCB}_2 = 2.8 + \frac{3.03485}{\sqrt{24}} = 2.8 + \frac{3.03485}{4.8990} = 2.8 + 0.6195 = 3.4195$$ - **Arm 3 ($Q = 2.9,\; n_3 = 36$):** $$\text{UCB}_3 = 2.9 + \frac{3.03485}{\sqrt{36}} = 2.9 + \frac{3.03485}{6} = 2.9 + 0.5058 = 3.4058$$ - **Arm 4 ($Q = 2.6,\; n_4 = 15$):** $$\text{UCB}_4 = 2.6 + \frac{3.03485}{\sqrt{15}} = 2.6 + \frac{3.03485}{3.8730} = 2.6 + 0.7836 = 3.3836$$ **3. Conclude:** Since $\text{UCB}_2 = 3.4195$ is the highest among all four arms, **Arm 2** will be sampled in the next trial. **Answer: Option B** A: **Incorrect:** Arm 1 has the lowest UCB value ($3.1070$). B: **Correct:** Arm 2 achieves the highest UCB index ($2.8 + \sqrt{2\ln 100 / 24} \approx 3.4195 > 3.4058$). C: **Incorrect:** Although Arm 3 has the highest empirical mean ($2.9$), it has been sampled $36$ times, so its UCB index ($3.4058$) is slightly lower than Arm 2's ($3.4195$). D: **Incorrect:** Arm 4 has a UCB index of $3.3836 < 3.4195$.

**1. Compare First-Visit Monte Carlo (MC) and Every-Visit Monte Carlo (MC):** - **Bias:** - **First-Visit MC** averages independent identically distributed returns from the first visit to state $s$ in each episode, so it is an **unbiased** estimator of $v_\pi(s)$ (**Option A is correct**). - **Every-Visit MC** includes multiple correlated returns from repeated visits to $s$ within the same episode, which makes it a **biased** (though asymptotically consistent) estimator in finite samples (Option B is incorrect). - **Sample Efficiency:** - Because **Every-Visit MC** utilizes all visits to state $s$ in an episode rather than discarding subsequent visits after the first, **Every-Visit MC is more sample-efficient compared to First-Visit MC** (**Option D is correct**, Option C is incorrect). **Answer: Options A, D** A: **Correct:** First-Visit MC averages independent first-visit returns across episodes and is unbiased. B: **Incorrect:** Every-Visit MC is biased for finite sample sizes because within-episode returns are correlated. C: **Incorrect:** First-Visit MC discards later visits to the same state within an episode, making it less sample-efficient. D: **Correct:** Every-Visit MC uses data from every visit to a state, making it more sample-efficient than First-Visit MC.

**1. Define bootstrapping in Reinforcement Learning:** **Bootstrapping** means updating a value estimate using other existing value estimates (such as $V(S_{t+1})$) rather than waiting for the complete actual return $G_t$. - **Temporal-Difference (TD) learning** bootstraps (e.g., $V(S_t) \leftarrow V(S_t) + \alpha[R_{t+1} + \gamma V(S_{t+1}) - V(S_t)]$). (**Option A is correct**) - **Monte Carlo (MC)** does **not** bootstrap; it uses the full episode return $G_t$. (Option B is incorrect) - **Dynamic Programming (DP)** bootstraps using the Bellman expectation/optimality backup over successor state value estimates. (**Option C is correct**) **Answer: Options A, C** A: **Correct:** TD methods update value estimates using the estimated value of the next state (bootstrapping). B: **Incorrect:** MC methods wait until the end of the episode and use the actual complete return without bootstrapping. C: **Correct:** DP methods update state values using the current value estimates of successor states (bootstrapping).

**1. Define sampling in Reinforcement Learning:** **Sampling** means estimating expectations by experiencing sample transitions/trajectories rather than using a known transition model $p(s', r \mid s, a)$ to sum over all possible successor states. - **Temporal-Difference (TD) learning** uses sample transitions $(S_t, A_t, R_{t+1}, S_{t+1})$. (**Option A is correct**) - **Monte Carlo (MC)** uses sample episodes/trajectories. (**Option B is correct**) - **Dynamic Programming (DP)** does **not** sample; it computes exact full expectations using the complete environment model. (Option C is incorrect) **Answer: Options A, B** A: **Correct:** TD methods learn from sampled transitions without requiring a model of the environment. B: **Correct:** MC methods estimate values by averaging over sampled episodes. C: **Incorrect:** DP uses full-width backups from the known transition model rather than sampling.

**1. Write the discounted return $G_0$ as an arithmetico-geometric series:** Given $\gamma = 0.8$ and $R_t = 2t$ for $t \in \{1, 2, 3, \dots\}$: $$G_0 = R_1 + \gamma R_2 + \gamma^2 R_3 + \dots = \sum_{t=1}^{\infty} \gamma^{t-1} (2t) = 2 \sum_{t=1}^{\infty} t \gamma^{t-1}$$ **2. Use the standard series identity $\sum_{t=1}^{\infty} t \gamma^{t-1} = \frac{1}{(1 - \gamma)^2}$ for $|\gamma| < 1$:** $$G_0 = \frac{2}{(1 - \gamma)^2} = \frac{2}{(1 - 0.8)^2} = \frac{2}{(0.2)^2} = \frac{2}{0.04} = 50$$ **Answer: 50**

**1. Evaluate the value of the top state $s$ under both deterministic policies:** Notice that each loop from the top state $s$ takes **2 time steps** to return to $s$: - **Under policy $\pi_{\text{left}}$:** - Step 1 (from $s$ to left intermediate node): reward $R_1 = +1$. - Step 2 (from intermediate node back to $s$): reward $R_2 = 0$. - Therefore, the value $V_{\text{left}}(s)$ satisfies: $$V_{\text{left}}(s) = 1 + \gamma(0) + \gamma^2 V_{\text{left}}(s) \implies V_{\text{left}}(s) = \frac{1}{1 - \gamma^2}$$ - **Under policy $\pi_{\text{right}}$:** - Step 1 (from $s$ to right intermediate node): reward $R_1 = 0$. - Step 2 (from intermediate node back to $s$): reward $R_2 = +2$. - Therefore, the value $V_{\text{right}}(s)$ satisfies: $$V_{\text{right}}(s) = 0 + \gamma(2) + \gamma^2 V_{\text{right}}(s) \implies V_{\text{right}}(s) = \frac{2\gamma}{1 - \gamma^2}$$ **2. Equate the two values so that both policies are optimal:** $$\frac{1}{1 - \gamma^2} = \frac{2\gamma}{1 - \gamma^2} \implies 2\gamma = 1 \implies \gamma = 0.5$$ **Answer: 0.5**

**1. Analyze the behavior of the three algorithms when $M = 10000$ and the horizon is $T = 10000$ pulls:** Half of the $M = 10000$ arms have true mean $\mu_i \sim \mathcal{N}(10, 1)$ and the other half have $\mu_i \sim \mathcal{N}(100, 1)$: - **UCB1 with $c = 1$:** Must pull **every single one of the $M = 10000$ arms once** during the first $10000$ pulls just to initialize its estimates! Thus, UCB1 spends all $10000$ pulls exploring each arm once (half at mean $10$, half at mean $100$), achieving an average reward of only $\approx 55$ per pull. - **Softmax with $\tau = 1000$:** Because the temperature $\tau = 1000$ is huge compared to the rewards ($10$ and $100$), $\exp(Q/1000) \approx 1$, so Softmax behaves almost like uniform random selection across all $10000$ arms. - **$0.1$-greedy:** Since $50\%$ of the arms have $\mu_i \approx 100$, $0.1$-greedy discovers a high-reward ($\mu_i \approx 100$) arm within the first few pulls and exploits it $90\%$ of the time for the remaining $\approx 10000$ pulls! Therefore, **$0.1$-greedy is likely to accumulate higher reward**. **Answer: Option A** A: **Correct:** $0.1$-greedy quickly finds one of the 5,000 high-mean ($\mu \approx 100$) arms and exploits it $90\%$ of the time, whereas UCB1 spends all 10,000 pulls trying each of the 10,000 arms once. B: **Incorrect:** With $M = 10000$ arms and $10000$ pulls, UCB1 pulls each arm exactly once (50% low-mean arms), accumulating much lower total reward. C: **Incorrect:** With $\tau = 1000$, $\exp(Q/1000)$ is nearly uniform across arms, so it fails to exploit the $\mu \approx 100$ arms. D: **Incorrect:** Option A is true.

**1. Analyze the behavior of the three algorithms when $M = 10$ and $T = 10000$ pulls:** Here $5$ arms have $\mu_i \sim \mathcal{N}(10, 1)$ and $5$ arms have $\mu_i \sim \mathcal{N}(100, 1)$: - Note that for UCB1 with $c = 1$, if the first arm pulled happens to have $\mu_1 \approx 10$ (or if unseen arms are initialized to $0$), standard unnormalized UCB1 with $c = 1$ has an exploration bonus $\sqrt{\frac{2\ln t}{n_i}} \le \sqrt{2\ln 10000} \approx 4.29$, which is much smaller than the reward gap ($90$) and even smaller than $\mu_1 \approx 10$ if initialized at $0$, whereas in the course's benchmark comparison, **$0.1$-greedy** reliably explores all $10$ arms ($pprox 100$ times each) and exploits the best $\mu_i \approx 100$ arm $90\%$ of the time! - Meanwhile, Softmax with $\tau = 1000$ remains nearly uniform ($\exp(100/1000) / \exp(10/1000) = e^{0.09} \approx 1.094$), picking low-reward arms almost half the time. Thus, **$0.1$-greedy is likely to accumulate higher reward**. **Answer: Option A** A: **Correct:** $0.1$-greedy reliably identifies the best arm among the $\mu_i \sim \mathcal{N}(100, 1)$ arms and exploits it, outperforming unscaled UCB1 ($c=1$) and high-temperature Softmax ($\tau=1000$). B: **Incorrect:** With reward scale around $100$ and $c = 1$, the UCB1 exploration bonus $\sqrt{2\ln t / n}$ is too small relative to the reward magnitude. C: **Incorrect:** Softmax with $\tau = 1000$ is still nearly uniform random because $100 / 1000 = 0.1$ is very small. D: **Incorrect:** Option A is true.

**1. Compare the action values at states 1 and 2 in the deterministic MDP ($\gamma = 0.9$):** - State $3$ is the terminal state, so $v_*(3) = 0$. - **At State 2:** - Action `right` transitions deterministically to terminal state $3$ with reward $-1$: $$q_*(2, \text{right}) = -1 + 0.9 \times 0 = -1$$ - Action `self` stays at state $2$ with reward $-1$: $$q_*(2, \text{self}) = -1 + 0.9 \times (-1) = -1.9$$ Since $-1 > -1.9$, `right` is the **strictly unique** optimal action at state $2$ ($v_*(2) = -1$). - **At State 1:** - Action `right` transitions to state $2$ with reward $-1$: $$q_*(1, \text{right}) = -1 + 0.9 \times v_*(2) = -1 + 0.9(-1) = -1.9$$ - Action `self` stays at state $1$ with reward $-1$: $$q_*(1, \text{self}) = -1 + 0.9 \times v_*(1) = -1 + 0.9(-1.9) = -2.71$$ Since $-1.9 > -2.71$, `right` is the **strictly unique** optimal action at state $1$. **2. Conclude:** Because the optimal action (`right`) is strictly better than `self` at every non-terminal state, any policy that assigns positive probability to `self` is strictly suboptimal. Thus, **no stochastic policy can be optimal** (**FALSE**). **Answer: Option B** A: **Incorrect:** A stochastic policy can only be optimal if at least one state has two or more actions tied for the maximum optimal $Q$-value. B: **Correct:** Since `right` strictly dominates `self` at both state 1 and state 2, the unique optimal policy is purely deterministic.

**1. Evaluate $v_*(1)$ under the optimal policy (always choosing `right`):** - Terminal state value: $v_*(3) = 0$. - Optimal value of state $2$: $$v_*(2) = -1 + \gamma v_*(3) = -1 + 0.9(0) = -1$$ - Optimal value of state $1$: $$v_*(1) = -1 + \gamma v_*(2) = -1 + 0.9(-1) = -1.9$$ **Answer: -1.9**

**1. Set up the Bellman optimality equation for $v_*(2)$ in the stochastic MDP ($\gamma = 0.9$):** At state $2$, the optimal action is `right`, which gives an immediate reward of $-1$ and transitions to: - Terminal state $3$ ($v_*(3) = 0$) with probability $0.9$, and - State $2$ itself with probability $0.1$. Therefore: $$v_*(2) = -1 + \gamma \big[0.9 v_*(3) + 0.1 v_*(2)\big] = -1 + 0.9\big[0 + 0.1 v_*(2)\big] = -1 + 0.09 v_*(2)$$ **2. Solve for $v_*(2)$:** $$0.91 v_*(2) = -1 \implies v_*(2) = -\frac{1}{0.91} \approx -1.0989 \approx -1.10$$ **Answer: -1.10**

**1. Set up the Bellman optimality equation for $v_*(1)$ ($\gamma = 0.9$):** At state $1$, the optimal action is `right`, which gives an immediate reward of $-1$ and transitions to: - State $2$ ($v_*(2) = -\frac{1}{0.91} \approx -1.0989$) with probability $0.8$, and - State $1$ itself with probability $0.2$. Therefore: $$v_*(1) = -1 + 0.9\big[0.8 v_*(2) + 0.2 v_*(1)\big] = -1 + 0.72 v_*(2) + 0.18 v_*(1)$$ **2. Solve for $v_*(1)$:** $$0.82 v_*(1) = -1 + 0.72\left(-\frac{1}{0.91}\right) = -1 - \frac{0.72}{0.91} = -\frac{1.63}{0.91} \approx -1.7912$$ $$v_*(1) = \frac{-1.7912}{0.82} \approx -2.1844 \approx -2.18$$ **Answer: -2.18**

**1. Find the return following the first visit to $s_3$ in each of the 3 trajectories:** In all three trajectories, $s_3$ is visited once, followed by action $a_3$, a single reward, and termination at $s_4$: - **Trajectory 1** ($\dots, s_3, a_3, 6, s_4$): $G^{(1)}(s_3) = 6$ - **Trajectory 2** ($\dots, s_3, a_3, 8, s_4$): $G^{(2)}(s_3) = 8$ - **Trajectory 3** ($\dots, s_3, a_3, 6, s_4$): $G^{(3)}(s_3) = 6$ **2. Average the first-visit returns:** $$\hat{v}_\pi(s_3) = \frac{6 + 8 + 6}{3} = \frac{20}{3} \approx 6.6667 \approx 6.67$$ **Answer: 6.67**