Problem $3.(50$pt$)$ Consider an infinite horizon MDP$,$ characterized by $M=($:$S,A,r,p,$:$)$

and $r$:$SA[0,1].$ We would like to evaluate the value of a Markov stationary policy

$$:$S(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})inSAS$ for $k=0,1,$dots. Let hat$(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),$:$)$ and obtain widehat$(v{)}^{}.$

Prove the simulation lemma bounding the difference between hat$(v{)}^{}$ and the true value of the

policy, denoted by $v^{},$ by showing that

$|v^{}(s_0)-$widehat$(v{)}^{}(s_0)|\frac{}{(1-{)}^2}{E}_{s{d}_{s_0}^{},a(s)}||widehat(p)(*|s,a)-p(*|s,a)|{|}_1,$

where $s_0$ is the initial state and $d_{s_0}^{}$ is the discounted state visitation distribution under policy

$.$ Note that the difference $|v^{}(s_0)-$widehat$(v{)}^{}(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 $$~~$1$ as the approximation error propagates more across stages.

You can search the simulation lemma online, but you need to understand and write the

proof in your own words.