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_{t+1}(s)=v_t(s)+(G_t^{(n)}-v_t(s))*I_{\{s_t)}=s,$

where $G_t^{(n)}$:$=r_t+r_{t+1}+$dots$+{}^{n-1}{r}_{t+n-1}+{}^n{v}_t^{}(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\_138568"></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)}\text{'}$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$()$

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