You go to a Halloween party at a mysterious haunted house. Through exploration, you discover

that it has the following characteristics. You can either be scared or not scared, and you can either be

upstairs or downstairs. If you are scared, running up or down the stairs costs you a unit of energy

$($reward $=1)$ but changes your scared state. If you aren$$t scared, you can run up or down the stairs

with a unit energy cost but also a $+1$ reward for continuing to not be scared $($so overall reward $=0).$

There are more ghosts downstairs than upstairs, so sitting still in a scared state is worse downstairs

$($reward $=3)$ than upstairs $($reward $=2).$ If you sit still while you are not scared, a ghost will pop

out and scare you $25\%$ of the time $(2$ reward$).$ Otherwise you will remain happy $(+2$ reward$).$

$($a$)$ Formulate this problem as an MDP $($for the sake of uniformity, formulate it as a continuing

discounted problem with gamma $=0\mathrm{.}9.)$ The rewards are specified in the description. Explicitly

give the state set, action set, transition probabilities and reward expectations Ra

ss$($expected

rewards for state$$action$$next$-$state triples as a three$-$argument function R : S$\backslash$times A$\backslash$times S $->$ R$,$ hint:

See equation $3\mathrm{.}6$ in Reinforcement Learning Second Edition Sutton and Bartos $)$

$($b$)$ Starting with the policy of running from every state, perform ONE step of policy iteration $($by

hand$).$ This means evaluate the given policy and then do policy improvement ONCE. Show

all steps. What is the resulting policy? $($Hint: use iterative policy evaluation.$)$

$($c$)$ Explicitly write the Bellman optimality equations for this problem.