Reasoning for temporal difference update rule

Question

In TD(0) learning where the value function is given by $V(s) = w^T\phi(s)$ where $w$ is a weight vector and $\phi$ is a feature map, the weight update is given by $w_{t+1} = w_{t} + \eta\delta_{t+1}\phi(s_{t})$, where $\eta$ is the learning rate and $\delta$ is the temporal difference error. The temporal difference error is given by $\delta_{t+1} = r_{t}+\gamma V_{t+1} -V_{t}$, where $r$ is the reward and $\gamma$ is the discount factor. Note that the weight update is proportional to the old state features. This update rule can be thought of as trying to make $V_{t}$ closer to $r_t +\gamma V_{t+1}$ to make the value function more self consistent.

However, it is also possible to make the value of $\gamma V_{t+1}$ closer to $V_{t}-r_{t}$ by making the weight update rule $w_{t+1} = w_{t} - \frac{\eta}{\gamma}\delta_{t+1}\phi(s_{t+1})$. It is also possible to do something in the middle like $w_{t+1} = w_{t} + \frac{\eta}{2}\delta_{t+1}(\phi(s_{t})-\frac{1}{\gamma}\phi(s_{t+1}))$.

Are these viable weight update rules? If not, why? What properties do the learning algorithms corresponding to these update rules have?

Answer 1

First of all the weights update is derived using gradient descent. So the proper form of update is the first one you have. This is derived using math and satisfies that the updates are towards minimizing the Mean Square Error between true value and approximated one. For the true value we use a biased sample of the true value at the next time step plus the reward obtained at the current timestep: $r_t + \gamma \hat{v}_{t+1}$ which is your TD target (what you try to approximate). So the tricky part in RL with FA is that you try to approximate something which is also an approximation of a true quantity.

I am not very sure what do you mean by making the value of γVt+1 closer to Vt−rt. For linear approximation, as you stated at the beginning of your question, the update needs to have the following form in order to reduce the MSE of the true value function: $\Delta w=\eta(v_\pi-\hat{v}_w)\phi(s)$. As I mentioned above because in RL we don't have knowledge of the true value, but only reward signals, we substitute the target (true value) with the target form I described in the previous paragraph.

Your first proposed update, first of all, eliminates the discount factor which ensures that in an infinite horizon scenario the sum of rewards converges into a real value and not to infinity. Even if you consider episodic tasks the sign change makes your weights updating into a direction that doesn't follow the gradient of the MSE. In your second update again you use a an arbitrary rule for updating and not derived through gradient descent. By the way cutting in half the learning rate does not help in any sense as again you can define a new learning rate.

I refer you to these documents in which you can clarify how the update rule is defined and why it has that particular form and what are the optimality criteria and the role of the discount factor in RL:

RL with FA, 2.3 Optimality Criteria and Discounting

Hope this helps!