Problem $1.(50$pt$)$ Given a Markov stationary policy $,$ consider the policy evaluation problem

to compute $v.$ For example, we can apply the temporal difference $($TD$)$ learning algorithm

given by

$v_{t+1}(s)=v_t(s)+{}_t(s)*I_{\{s_t)}=s,$

where ${}_t$:$=r_t+v_t(s_{t+1})-v_t(s_t)$ is known as TD error. Alternatively, we can apply the $n-$step

TD learning algorithm given by

$v_{n+t}(s)=v_{n+t-1}(s)+(G_t^{(n)}-v_{t+n-1}(s))*I_{\{s_t)}=s,$

where $G_t^{(n)}$:$=r_t+r_{t+1}+$dots$+{}^{n-1}{r}_{t+n-1}+{}^n{v}_{n+t-1}(s_{t+n})$ for $n=1,2,$dots. Note that

${}_t=G_t^{(1)}-v_t(s_t).$

The $n-$step TD algorithms for $n<mi\; id="EditorElement\_1152462"></mi>$ use bootstrapping. Therefore, they use biased estimate

of $v.$ On the other hand, as $n,$ the $n-$step TD algorithm becomes a Monte Carlo method,

where we use an unbiased estimate of $v.$ However, these approaches delay the update for $n$

stages and we update the value function estimate only for the current state.

As an intermediate step to address these challenges, we first introduce the $-$return algo$-$

rithm given by

$v_{t+1}(s)=v_t(s)+(G_t^{}-v_t(s))*I_{\{s_t)}=s,$

where given $in[0,1],$ we define $G_t^{}$:$=(1-){\displaystyle \underset{n=1}{\overset{}{}}}{}^{n-1}{G}_t^{(n)}$ taking a weighted average of

$G_t^{(n)}$ s$.$

$($a$)$ By the definition of $G_t^{(n)},$ we can show that $G_t^{(n)}=r_t+G_{t+1}^{(n-1)}.$ Derive an analogous

recursive relationship for $G_t^{}$ and $G_{t+1}^{}.$

$($b$)$ Show that the term $G_t^{}-v_t(s)$ in the $-$return update can be written as the sum of TD errors.

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

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