Problem $1$: An MDP Episode $(25$ points$)$

In this part of the assignment, we are going to play an episode in an MDP by following a given policy. Consider the first test case of problem $1($available in the file test$\_$cases$/$p$1/1.$prob$).$

The first part of this file specifies an MDP$.S$ is the start state with four available actions $($N$,E,S,W$ is an ordinary state with the same four available actions and $1,-1$ are states where the only available action is exit and the reward are $1$ and $-1$ respectively. The reward for action in other states is $-0\mathrm{.}05.$# is a wall.

Actions are not deterministic in this environment. In this case with noise $=0\mathrm{.}1,$ we are successfully acting $80\%$ of the time and $20\%$ of the time we will act perpendicular to the intended direction with equal probability, i$.$e$.10\%,$ for each unintended direction. If the agent attempts to move into a wall, the agent will stay in the same position. Note that this MDP is identical to the example that we covered extensively in our class.

The second part of this file specifies the policy to be executed.

As usual, your first task is to implement the parsing of this grid MDP in the function read$\_$grid$\_$mdp$\_$problem$\_$p$1($file$\_$path$)$ of the file

parse.py$.$ You may use any appropriate data structure.

Next, you should implement running the episode in the function play$\_$episode$($problem$)$ in the file $p1.$ py$.$

Below is the expected output. Note that we always use exactly $5$ characters for the output of a single grid and that the last line does not contain a new line.

Taking action: W $($intended: $N)$

Reward received: $-0\mathrm{.}05$

New state:

$-\frac{,}{b}ar(P),-,1$

$,-,-1$

Cumulativ$$ rew$\backslash$bar $($a$)$ rd s$$m: $-0\mathrm{.}1$

Taking action: $N($intended: $N)$

Reward received: $-0\mathrm{.}05$

New state:

Cumulativ$$ rew$\backslash$bar $($a$)$ rd s$$m: $-0\mathrm{.}15$

Taking action: $N($intended: $N)$

Reward received: $-0\mathrm{.}05$

New state:

$P,-,1\frac{?}{b}$

$ar(S),-,-1$

Cumulativ$$ rew$\backslash$bar $($a$)$ rd s$$m: $-0\mathrm{.}2$

Taking action: $S($intended: E$)$

Reward received: $-0\mathrm{.}05$

New state:

$\frac{?}{\text{b}\text{a}\text{r}}(P),$#$,-,1$

$S,-,-1$

Cumulativ$$ rew$\backslash$bar $($a$)$ rd s$$m: $-0\mathrm{.}25$

Taking action: $N($intended: $N)$

Reward received: $-0\mathrm{.}05$

New state:

$P,-,1\frac{?}{b}$

$ar(S),-,-,-1$

Cumulativ$$ rew$\backslash$bar $($a$)$ rd s$$m: $-0\mathrm{.}3$

Taking action: E $($intended: E$)$

Reward received: $-0\mathrm{.}05$

'New state:

Cumulativ$$ rew$\backslash$bar $($a$)$ rd s$$m: $-0\mathrm{.}35$

Taking action: E $($intended: E$)$

Reward received: $-0\mathrm{.}05$

New state:

Cumulative rew$\backslash$bar $($a$)$ rd s$$m: $-0\mathrm{.}4$

Taking action: E $($intended: E$)$

Reward received: $-0\mathrm{.}05$

New state:

$-,-,P$

$-,-,-1$

$\frac{?}{\text{b}\text{a}\text{r}}(s)$

Cumulative rew$\backslash$bar $($a$)$ rd s$$m: $-0\mathrm{.}45$

Taking action: exit $($intended: exit$)$

Reward received: $1\mathrm{.}0$

New state:

$-\frac{,}{b}ar(2),-\frac{?}{b}$

$ar(s),-,-1$

Cumulative rew$\backslash$bar $($a$)$ rd s$$m: $0\mathrm{.}55$

As you can see, in this question we don't use any discount factor. We will introduce that in the next question. You can also try some of the other test cases such as test$\_$cases$/$p$1/8.$prob.With a correct implementation, you should be able to pass all test cases.

py $q,$

import sys$,$ grader, parse

def policy$\_$evaluation$($problem$)$:

return$\_$value $=\text{'}\text{'}$

return return$\_$value

if $\_=""$:

test$\_$case$\_$id $=$ int$($sys$.$argv$[1])$

problem$\_$id $=2$

grader.grade$($problem$\_$id$,$ test$\_$case$\_$id$,$ policy$\_$evaluation, parse.read$\_$grid$\_$mdp$\_$problem$\_$p$2)$