Problem: Let \(p(r_{t+1},s_{t+1}|s_t)\) be a Markov reward process. Compare constant-\(\alpha\) Monte Carlo (MC) evaluation and \(n\)-step constant-\(\alpha\) temporal difference (TD) evaluation.
Solution: Essentially, TD is a bootstrapped version of MC, and indeed it turns out \(\lim_{n\to\infty}\text{TD}_{(n,\alpha)}=\text{MC}_{\alpha}\). That is, both TD and MC are model-free methods for evaluating the value function \(V(s_t)\), but whereas MC patiently waits for each episode to reach a terminal state before the value functions of the visited states are simultaneously updated:
\[\Delta V(s_t)=\alpha(\sum_{\text{visits }i\text{ to } s_t}R_i-V(s_t))\]
\(n\)-step TD is more impatient and instead replaces the empirical return \(R_i\mapsto r_{t+1}+…+\gamma^{n-1}r_{t+n}+\gamma^nV(s_{t+n})\) with a bootstrapped estimate depending on the estimated value \(V(s_{t+n})\) (this is not to be confused with the RL definition of dynamic programming (DP) which like TD also relies on recursive bootstrapping, but unlike TD is model-based rather than model-free. Also, don’t confuse the concept of DP in RL with DP in CS which simply means recursion with memoization).
Problem: Explain why, in practice, TD outperforms MC at value function estimation.
Solution: A useful analogy is to imagine a carnival (MRP) with \(2\) games (states) \(A,B\). Game \(A\) always returns reward \(r_A=0\) but also asserts the player has to proceed to game \(B\) (i.e. \(p(r_{t+1}=0,s_{t+1}=B|s_t=A)=1\)), and game \(B\) can return reward \(r_B\in\{0,1\}\) with (say) \(50:50\) odds but after that the player must go home. Imagine a batch of \(8\) carnival players/”episodes”, \(2\) of which are initialized at game \(A\), and the other \(6\) are initialized at game \(B\). It turns out that both of the players who begin at game \(A\) then receive \(r_A=0\) as expected, and then proceed to game \(B\) and happen to receive \(r_B=0\) and go home. On the other hand, of the \(6\) players who begin at game \(B\), \(4\) of them get \(r_B=1\) while the remaining \(2\) get \(r_B=0\). Assuming undiscounted return \(\gamma=1\), the Monte Carlo approach would look at the \(2\) episodes that passed through game \(A\), and conclude that game \(A\) has no value \(V(A)=0\), whereas game \(B\) seems to have value \(V(B)=4/8=1/2\). By contrast, a TD approach would say that both games \(A\) and \(B\) have value \(1/2\) because anyone who plays game \(A\) has to play game \(B\). Thus, TD is about finding the maximum likelihood for the MRP, whereas MC is about minimizing mean-squared error.
(aside: to illustrate this more clearly, consider \(n=1\)-step TD where \(\Delta V(s_t)=\alpha(r_{t+1}+\gamma V(s_{t+1})-V(s_t))\) for each visit to state \(s_t\). Then the total bootstrap on the value over all times \(t\) when \(s_t\) was visited would be given by: \(\sum_t\Delta V(s_t)=0\) at equilibrium, so rearranging, one finds a Bellman-like equation \(V(s_t)=\hat r_{t+1}+\gamma\hat{V}(s_{t+1})\). This result is sometimes called Sutton’s theorem).
Problem: TD learning is solely for policy evaluation (i.e. bootstrapping \(V(s_t)\)). By contrast, SARSA, expected SARSA, and \(Q\)-learning are GPI algorithms. Explain how each of them works.
Solution: In all \(3\) cases, the proportionality constant \(\alpha>0\) is a hyperparameter.
For \(1\)-step SARSA, the idea is that a particular instantiation \(s_t\to a_t\to (r_{t+1}, s_{t+1})\to a_{t+2}\) of the MDP will lead to the \(Q\)-evaluation:
\[\Delta Q(s_t,a_t)\propto r_{t+1}+\gamma Q(s_{t+1},a_{t+1})-Q(s_t,a_t)\]
(which can be trivially extended to \(n\)-step SARSA). Expected (\(1\)-step, though again the generalization to \(n\geq 1\) is trivial) SARSA replaces \(Q(s_{t+1},a_{t+1})\) associated to whatever specific action \(a_{t+1}\) was drawn from the \((1-\varepsilon)\)-greedy policy \(\pi(a_{t+1}|s_{t+1})\) with, as its name suggests, the expectation value \(\langle Q(s_{t+1},a_{t+1})\rangle_{a_{t+1}}:=\sum_{a_{t+1}}\pi(a_{t+1}|s_{t+1})Q(s_{t+1},a_{t+1})\). Finally, (\(1\)-step) \(Q\)-learning is the special case of expected SARSA where the policy is maximally greedy (\(\varepsilon:=0\)) and hence \(\langle Q(s_{t+1},a_{t+1})\rangle_{a_{t+1}}=\max_{a_{t+1}}Q(s_{t+1},a_{t+1})\). In all cases, armed with \(Q\), one can then perform standard policy improvement by being greedy with respect to \(Q\), hence closing the GPI loop.
Problem: Explain how the “MODERN” acronym provides a bird’s eye-view over the field of RL.
Solution:
M: Model-free/based
O: On/off-policy
D: Distribution
E: Evaluation
R: Representation
N: \(n\)-step
Problem: Explain function approximation in the context of RL.
Solution: As the name suggests, function approximation is just RL’s glorified way of saying “use a neural network”. Exactly which function one is approximating with a neural network depends on the application, but could be e.g. the value function \(\hat{V}(s|\boldsymbol{\theta})\), the action function \(\hat{Q}(s,a|\boldsymbol{\theta})\), the policy itself \(\hat{\pi}(a|s,\boldsymbol{\theta})\), etc.
- Gradient Monte Carlo approximates the true value function \(V(s|\boldsymbol{\theta})\) by a neural network \(\hat{V}(s|\boldsymbol{\theta})\) via stochastic gradient descent on the loss:
\[L(\boldsymbol{\theta})=\frac{1}{2N(s)}\sum_t(\hat{V}(s_t|\boldsymbol{\theta})-R_t)^2\]
Thus, gradient descent is the usual \(\boldsymbol{\theta}\mapsto\boldsymbol{\theta}-\alpha\frac{\partial L}{\partial\boldsymbol{\theta}}\) with:
\[\frac{\partial L}{\partial\boldsymbol{\theta}}=\frac{1}{N(s)}\sum_t(\hat{V}(s_t|\boldsymbol{\theta})-R_t)\frac{\partial\hat{V}(s_t|\boldsymbol{\theta})}{\partial\boldsymbol{\theta}}\]
(or some stochastic or mini-batch version).
- Semi-gradient TD instead uses MSE loss against a (biased) estimator \(r_{t+1}+\gamma\hat{V}(s_{t+1}|\boldsymbol{\theta})\) of the return \(R_t\).
\[L(\boldsymbol{\theta})=\frac{1}{2N(s)}\sum_t(\hat{V}(s_t|\boldsymbol{\theta})-r_{t+1}-\gamma\hat{V}(s_{t+1}|\boldsymbol{\theta}))^2\]
Here, although the true gradient \(\partial L/\partial\boldsymbol{\theta}\) would take into account the \(\boldsymbol{\theta}\)-dependence present in both \(\hat{V}(s_t|\boldsymbol{\theta})\) and \(\hat{V}(s_{t+1}|\boldsymbol{\theta})\), it turns out to be better to only take into account the \(\boldsymbol{\theta}\)-dependence present in \(\hat{V}(s_t|\boldsymbol{\theta})\), hence the term “semi-gradient”:
\[\frac{\partial L}{\partial\boldsymbol{\theta}}\approx \frac{1}{N(s)}\sum_t(\hat{V}(s_t|\boldsymbol{\theta})-r_{t+1}-\gamma\hat{V}(s_{t+1}|\boldsymbol{\theta}))\frac{\partial\hat{V}(s_t|\boldsymbol{\theta})}{\partial\boldsymbol{\theta}}\]
Problem: on-policy & off-policy control with function approximation…
Solution:
Problem: Explain how the REINFORCE algorithm works, what its flaws are, and introducing a baseline can help remedy this.
Solution: (policy gradient method)
Problem: State and prove the policy gradient formula.
Solution: Out of context, one can remember it in the general form:
\[\frac{d}{d\theta}\langle f(x)\rangle_{x\sim p(x|\theta)}=\biggr\langle\frac{\partial\ln p(x|\theta)}{\partial\theta}f(x)\biggr\rangle_{x\sim p(x|\theta)}\]
which can heuristically be remembered as being able to “commute” the derivative operator \(d/d\theta\) with the expectation \(\langle\rangle\) provided one compensates with the log-policy \(\ln p\).
Problem: State the Bradley-Terry preference formula.
Solution: For an input (e.g. prompt to an LLM) \(x\) and two outputs (e.g. LLM responses) \(y,y’\), one postulates the existence of a scalar function \(r(y|x)\in\mathbf R\) such that the probability of humans preferring \(y\) over \(y’\) given \(x\) is expressible in the softmax form:
\[p(y\succ y’|x):=\frac{e^{r(y|x)}}{e^{r(y|x)}+e^{r(y’|x)}}=\sigma(r(y|x)-r(y’|x))\]
There are some heuristic theoretical justifications one can provide for why the Bradley-Terry formula is a useful model of human psychology but at the same time it is known to be imperfect.
Problem: In practice, the reward “logit/energy” \(r(y|x)=r(y|x,\boldsymbol{\phi})\) is some neural network containing learnable parameters \(\boldsymbol{\phi}\). Write down the cost function \(C(\boldsymbol{\phi})\) to be minimized (gradient descent and all) with respect to \(\boldsymbol{\phi}\).
Solution: Loss on a single training triplet \((x,y,y’)\) is the usual negative log-likelihood:
\[L(x,y,y’,\boldsymbol{\phi}):=-\ln p(y\succ y’|x,\boldsymbol{\phi})=-\ln\sigma(r(y|x,\boldsymbol{\phi})-r(y’|x,\boldsymbol{\phi}))\]
Given a training dataset \(\mathcal D_{\text{tr}}\), one minimizes the usual empirical Monte Carlo average \(C(\boldsymbol{\phi}|\mathcal D_{\text{tr}}):=\langle L(x,y,y’,\boldsymbol{\phi})\rangle_{(x,y,y’)\sim\mathcal D_{\text{tr}}}\approx\frac{1}{|\mathcal D_{\text{tr}}|}\sum_{i=1}^{|\mathcal D_{\text{tr}}|}L(x_i,y_i,y’_i,\boldsymbol{\phi})\).
Furthermore, in the case of an RLHF reward model for LLM post-training, the architecture of \(r(y|x,\boldsymbol{\phi})\) is typically just the post-SFT LLM with the output layer swapped for a linear projection layer onto \(\mathbf R\).
Problem: The above describes the first stage of RLHF (reinforcement learning with human feedback). After a suitable reward model \(r(y|x,\boldsymbol{\phi})\) has been obtained, the next step of RLHF is to freeze \(\boldsymbol{\phi}\) and do what?
Solution: