Problem $1.(50$pt$)$ Given a Markov stationary policy $\backslash$pi $,$ consider the policy evaluation problem to compute v$^\backslash$pi $.$ For example, we can apply the temporal difference $($TD$)$ learning algorithm given by v$\_$t$+1($s$)=$v$\_$t$($s$)+\backslash$alpha $\backslash$delta $\_$t$($s$)\_\{$s$\_$t$=$s$\},$ where $\backslash$delta $\_$t:$=$r$\_$t$+\backslash$gamma 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$)+\backslash$alpha $($G$\_$t$^($n$)-$v$\_$t$($s$))\_\{$s$\_$t$=$s$\},$ where G$\_$t$^($n$)$:$=$r$\_$t$+\backslash$gamma r$\_$t$+1+...+\backslash$gamma $^$n$-1$ r$\_$t$+$n$-1+\backslash$gamma $^$n v$\_$t$^\backslash$pi $($s$\_$t$+$n$)$ for n$=1,2,....$ Note that $\backslash$delta $\_$t$=$ G$\_$t$^(1)-$v$\_$t$($s$\_$t$).$ The n$-$step TD algorithms for n$<\backslash$infty use bootstrapping. Therefore, they use biased estimate of v$^\backslash$pi $.$ On the other hand, as n $->\backslash$infty $,$ the n$-$step TD algorithm becomes a Monte Carlo method, where we use an unbiased estimate of v$^\backslash$pi $.$ 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 $\backslash$lambda $-$return algorithm given by v$\_$t$+1($s$)=$v$\_$t$($s$)+\backslash$alpha $($G$\_$t$^\backslash$lambda $-$v$\_$t$($s$))\_\{$s$\_$t$=$s$\},$ where given $\backslash$lambda in $[0,1],$ we define G$\_$t$^\backslash$lambda :$=(1-\backslash$lambda $)\_$n$=1^\backslash$infty $\backslash$lambda $^$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$+\backslash$gamma G$\_$t$+1^($n$-1).$ Derive an analogous recursive relationship for G$\_$t$^\backslash$lambda and G$\_$t$+1^\backslash$lambda $.($b$)$ Show that the term G$\_$t$^\backslash$lambda $-$v$\_$t$($s$)$ in the $\backslash$lambda $-$return update can be written as the sum of TD errors. The TD algorithm, Monte Carlo method and $\backslash$lambda $-$return algorithm looks forward to approximate v$^\backslash$pi $.$ Alternatively, we can look backward via the eligibility trace method. TheTD$(\backslash$lambda $)$algorithm is given by $[$ z$\_$t$($s$)=\backslash$gamma $\backslash$lambda z$\_$t$-1($s$)+\_\{$s$=$s$\_$t$\}$ s in S; v$\_$t$+1($s$)=$v$\_$t$($s$)+\backslash$alpha $\backslash$delta $\_$t z$\_$t$($s$)$ s in S$,]$ where z$\_$t in $^|$S$|$ is called the eligibility vector and the initial z$\_-1($s$)=0$ for all s$.($c$)$ In the TD$(\backslash$lambda $)$ 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 assignment 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$(\backslash$lambda $)$ 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 $\backslash$lambda $-$return is forward$-$looking while TD$(\backslash$lambda $)$ is backward looking, they are equivalent as you will show next for the finite horizon problem with horizon length T$<\backslash$infty $.($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 $\backslash$lambda $-$return algorithm yields that v$\_$T$($s$)$ can be written as v$\_$T$($s$)=\_$t$=0^$T$-1\backslash$alpha $($G$\_$t$^\backslash$lambda $-$v$\_$t$($s$\_$t$))\_\{$s$\_$t$=$s$\}.$ Correspondingly, the recursive update in the TD$(\backslash$lambda $)$ algorithm yields that v$\_$T$($s$)$ can be written as v$\_$T$($s$)=\_$t$=0^$T$-1\backslash$alpha $\backslash$delta $\_$t z$\_$t$($s$).$ Show that $\_$t$=0^$T$-1\backslash$alpha $\backslash$delta $\_$t z$\_$t$($s$)=\_$t$=0^$T$-1\backslash$alpha $($G$\_$t$^\backslash$lambda $-$v$\_$t$($s$\_$t$))\_\{$s$\_$t$=$s$\}$ s $.$