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)