Problem $2.$ Consider a MDP with two states $S=\{0,1\},$ two actions $A=\{1,2\},$ and the

follow reward function

$R_s^{(a)}=\{\begin{array}{ccc}1,& (s,a)=(0,& 1)\\ 4,& (s,a)=(0,& 2)\\ 3,& (s,a)=(1,& 1)\\ 2,& (s,a)=(1,& 2)\end{array}$

and the transition probabilities $P_{s{s}^{\text{'}}}^{(a)}$ as follows:

$\left[\begin{array}{cc}{P}_{00}^{(1)}& P_{00}^{(2)}\\ P_{10}^{(1)}& P_{10}^{(2)}\end{array}\right]=\left[\begin{array}{cc}\frac{1}{3}& \frac{1}{2}\\ \frac{1}{4}& \frac{2}{3}\end{array}\right]$

The other probabilities can be deduced, for example:

$P_{01}^{(1)}=1-P_{00}^{(1)}=1-\frac{1}{3}=\frac{2}{3}.$

The discount factor is

$=\frac{3}{4.}$

Exercise on model$-$free prediction:

$($a$)$ For the policy $$ that chooses action $1$ in state $0,$ and action $2$ in state $1,$ starting from

state $0,$ generate one episode $E$ of $10000$ triplets of $(R_i,S_i,A_i),i=0,2,$dots,$9999,$ with

$R_0=0,S_0=0.$

$($b$)$ Based on the episode $E,$ use Monte Carlo policy evaluation to estimate the value

function $v_{}(s).$

$($c$)$ Based on the episode $E,$ use $n-$step temporal difference policy evaluation to estimate

the value function $v_{}(s).$

Exercise on model$-$free control:

$($a$)$ Use the SARSA algorithm to estimate the optimal action$-$value function $q_{**}(s,a),$ by

running the algorithm in Sutton and Barto's book $(2$nd edition, available online$).$

$($b$)$ Use the Q$-$learning algorithm to estimate the optimal action$-$value function $q_{**}(s,a),$ by

running the algorithm in Sutton and Barto's book $(2$nd edition, available online$).$

You only need to simulate one episode. In both cases, you will need to decide an appropriate

fixed step$-$size $,$ and exploration probability $lon,$ and number of time steps in the episode.