The ID algorithm, Monte Carlo method and $-$return algorithm looks forward to approx$-$

imate $v.$ Alternatively, we can look backward via the eligibility trace method. The $TD()$

algorithm is given by

$z_t(s)=z_{t-1}(s)+I_{\{s)}=s_t,$AAsinS

$v_{t+1}(s)=v_t(s)+{}_t{z}_t(s),$AAsinS,

where $z_{t}in{R}^{|S|}$ is called the eligibility vector and the initial $z_{-1}(s)=0$ for all $s.$

$($c$)$ In the $TD()$ algorithm, $z_t$ is computed recursively. Express $z_t$ only in terms of the states

visited in the past. This representation of the eligibility vector will show that eligibility

vectors combine the frequency heuristic and recency heuristic to address the credit assign$-$

ment problem. For the rewards received, the frequency heuristic assigns higher credit to

the frequently visited states while the recency heuristic assigns higher credit to the recently

visited states. The eligibility vector assigns higher credits to the frequently and recently

visited states.

Note that in the $TD()$ algorithm, value function estimate for every state gets updated different

from the $n-$step TD algorithms, where only the estimate for the current state gets updated. If

a state has not been visited recently and frequently then the eligibility of that state $($i$.$e$.,$ the

associated entry of the eligibility vector$)$ will be close to zero. Therefore, the update via the

TD$-$error will take very small steps for such states.

Though $-$return is forward$-$looking while $TD()$ is backward looking, they are equivalent

as you will show next for the finite horizon problem with horizon length

$($d$)$ Assume that the initial value function estimates are zero, i$.$e$.,v_0(s)=0$ for all $s.$ Then, the

recursive update in the $-$return algorithm yields that $v_T(s)$ can be written as

$v_T(s)={\displaystyle \underset{t=0}{\overset{T-1}{}}}(G_t^{}-v_t(s_t))*I_{\{s_t)}=s.$

Correspondingly, the recursive update in the $TD()$ algorithm yields that $v_T(s)$ can be writ$-$

ten as

$v_T(s)={\displaystyle \underset{t=0}{\overset{T-1}{}}}{}_t{z}_t(s).$

Show that

${\displaystyle \underset{t=0}{\overset{T-1}{}}}{}_t{z}_t(s)={\displaystyle \underset{t=0}{\overset{T-1}{}}}(G_t^{}-v_t(s_t))*I_{\{s_t)}=s,$AAs.