4
$\begingroup$

I am reading these slides. On page 38, the update for the parameters for the linear function approximation of TD(0) is given. I have a doubt regarding this. The cost function (RMSE) is given on page 37.

My doubt is: why is the gradient of $\hat v(S^{\prime}, \mathbf w)$ with respect to parameters $w$ not considered?

I think the parameter update should be: $$\mathbf w \leftarrow \mathbf w +\alpha [R + \gamma \hat v(S', \mathbf w) - \hat v(S, \mathbf w)] (\nabla \hat v(S, \mathbf w)- \gamma \nabla \hat v(S', \mathbf w))$$ Instead in the material it is given as:- $$\mathbf w \leftarrow \mathbf w +\alpha [R + \gamma \hat v(S', \mathbf w) - \hat v(S, \mathbf w)] \nabla \hat v(S, \mathbf w)$$

Could someone please explain?

$\endgroup$

1 Answer 1

1
$\begingroup$

This is formally known as a semi-gradient method.

What we would like to do is to minimize $\big(v(S) - \hat v(S, w)\big)^2$, where $v(S)$ is the true value function. This would give the gradient descent update \begin{align*} w \leftarrow w + \alpha[v(S) - \hat v(S, w)]\nabla \hat v(S, w) . \tag{1} \end{align*} Of course we don't have access to $v(S)$. So instead, we could use the monte carlo return (the observed, discounted, episodic return). The other option is to use a bootstraped estimate of $v(S)$, e.g. the estimate $r + \gamma \hat v(S', w)$, which would give the update

\begin{align*} w \leftarrow w + \alpha[r + \gamma \hat v(S', w) - \hat v(S, w)]\nabla \hat v(S, w) \tag{2} \end{align*}

As you correctly point out, Eq. 2 is no longer a true gradient descent method. To directly quote Sutton and Barto, section 9.3 page 165,

This step [Eq. 1] would not be valid if a bootstrapping estimate were used in place of v(S). Bootstrapping methods are not in fact instances of true gradient descent (Barnard, 1993). They take into account the effect of changing the weight vector w on the estimate, but ignore its effect on the target. They include only a part of the gradient and, accordingly, we call them semi-gradient methods.

The 'estimate' here is refering to $\hat v(S, w)$, whereas the 'target' is $v(S)$ (or its approximation). Indeed the parameter update you give would be the true gradient descent update for minimizing $\big(r + \gamma \hat v(S', w) - \hat v(S, w)\big)^2$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .