Exercise 6.1.2
Semi-gradient TD(0): true SGD of MSVE and TD error, Gradient MC
The Foundation of Gradient-Based TD Methods
-
a) For a given policy \(\pi\), the most natural and standard objective for value prediction is the Mean Squared Value Error (\(MSVE\)), which measures the quality of a value function approximation \(\hat{v}(s, \mathbf{w})\). It is given by: \[MSVE(\mathbf{w}) \doteq \sum_{s \in \mathcal{S}} \mu(s) [v_\pi(s) - \hat{v}(s, \mathbf{w})]^2\] where \(\mu(s)\) is the on-policy state distribution.
First, derive the update rule for a true stochastic gradient descent (SGD) step designed to minimize the \(MSVE\). Then, contrast this with the true SGD update for minimizing the squared TD error at each step, \([(R_{t+1} + \gamma \hat{v}(S_{t+1}, \mathbf{w})) - \hat{v}(S_t, \mathbf{w})]^2\).
-
b) State the update rule used in the semi-gradient TD(0) algorithm for value prediction. By comparing this practical update rule to the true gradient-based updates you derived in part (a), explain the origin of the term “semi-gradient." Your explanation should highlight the key mathematical difference between them. Finally, discuss the theoretical and practical implications of this difference.
-
c) Now, consider a Gradient Monte Carlo (MC) prediction algorithm. Analyze the update target used in Gradient MC and explain how its stochastic gradient descent updates relate to the MSVE objective from part (a). Based on your analysis, does Gradient MC also qualify as a semi-gradient method? Justify your conclusion.