Problem $3.(50$pt$)$ Consider an infinite horizon MDP$,$ characterized by M$=($:S$,$A$,$r$,$p$,\backslash$gamma :) and r:S$\backslash$times A$->[0,1].$ We would like to evaluate the value of a Markov stationary policy $\backslash$pi :S$->\backslash$Delta $($A$).$ However, we do not know the transition kernel p $.$ Rather than applying a model$-$free approach, we decided to use a model$-$based approach where we first estimate the underlying transition kernel by follow some fully stochastic policy in the MDP $($for good exploration$)$ and observe the triples $($s$\_($k$),$a$\_($k$),$s$\_($k$+1))$inS$\backslash$times A$\backslash$times S for k$=0,1,$dots $.$ Let widehat$($p$)$ be our estimate of p based on the data collected. Now, we can apply value iteration directly as if the underlying MDP is widehat$($M$)=($:S$,$A$,$r$,$widehat$($p$),\backslash$gamma :) and obtain widehat$($v$)^(\backslash$pi $).$ Prove the simulation lemma bounding the difference between hat$($v$)^(\backslash$pi $)$ and the true value of the policy, denoted by v$^(\backslash$pi $),$ by showing that $|$v$^(\backslash$pi $)($s$\_(0))-$widehat$($v$)^(\backslash$pi $)($s$\_(0))|<=(\backslash$gamma $)/((1-\backslash$gamma $)^(2))$E$\_($s$$d$\_($s$\_(0))^(\backslash$pi $),$a$\backslash$pi $($s$))||$widehat$($p$)(*|$s$,$a$)-$p$(*|$s$,$a$)||\_(1),$ where s$\_(0)$ is the initial state and d$\_($s$\_(0))^(\backslash$pi $)$ is the discounted state visitation distribution under policy $\backslash$pi $.$ Note that the difference $|$v$^(\backslash$pi $)($s$\_(0))-$widehat$($v$)^(\backslash$pi $)($s$\_(0))|$ gets smaller with the smaller model approximation error $||$widehat$($p$)(*|$s$,$a$)-$p$(*|$s$,$a$)||\_(1).$ However, the impact of model approximation error gets larger with $\backslash$gamma $1$ as the approximation error propagates more across stages.