$1.$ Consider the following Markov decision process, with the gridworld and transition function as illustrated

below. The states are grid squares, identified by their row and column number $($row first$).$ The agent

always starts in state $(1,1),$ marked with the letter $S.$ There are two terminal goal states, $(2,3)$ with reward

$+5$ and $(1,3)$ with reward $-5.$ Rewards are $0$ in non$-$terminal states. $($The reward for a state is received

as the agent moves into the state$)$ The transition function is such that the intended agent movement

$($North$,$ South, West, or East$)$ happens with probability $0\mathrm{.}8.$ With probability $0\mathrm{.}1$ each, the agent ends up

in one of the states perpendicular to the intended direction. If a collision with a wall happens, the agent

stays in the same state.$($a$)$ Gridworld MDP$.($b$)$ Transition function.

$($a$)$ Draw the optimal policy for this grid.

$($b$)$ Suppose the agent knows the transition probabilities. Give the first two rounds of value iteration

updates for each state, with a discount of $0\mathrm{.}9.($Assume $V_0$ is $0$ everywhere and compute $V_1$ for times

$i=1,2.$

$($c$)$ Suppose the agent does not know the transition probabilities. What does it need $($or must it have

available$)$ in order to learn the optimal policy?

$($d$)$ The agent starts with the policy that always chooses to go right, and executes the following three

trials:

$(1,1)-(1,2)-(1,3),$

$(1,1)-(1,2)-(2,2)-(2,3),$ and

$(1,1)-(2,1)-(2,2)-(2,3).$

What are the monte carlo $($direct utility$)$ estimates for states $(1,1)$ and $(2,2),$ given these traces? $(4)$

$($e$)$ Using a learning rate of $0\mathrm{.}1$ and assuming initial values of $0,$ what updates does the TD$-$learning agent

make after trials $1$ and $2,$ above? First give the TD$-$learning update equation, and then provide the

updates after the two trials.

Consider the MDP below, in which there are two states, $x$ and $Y,$ two sctions, right and left, and the

deterministic rewards on each transition are as indicated by the numbers. Note that if action right is

taken in state $x,$ then the transition may be either to $x$ with a reward of $+2$ or to $Y$ with a reward of $-2.$

These two possibilities occur with probabilities $\frac{2}{3}($for the transition to $x)$ and $\frac{1}{3}($for the transition

to state $Y.$

Consider two deterministic policies:

${}_1(x)=$ left, ${}_1(Y)=$ right

${}_2(x)=$ right, ${}_2(Y)=$ right

$($a$)$ Show a typical trajectory for policy ${}_1$ from state $x.$

$($b$)$ Show a typical trajectory for policy ${}_2$ from state $x.$

$($c$)$ Assuming $=0\mathrm{.}5,$ the value of state $Y$ under policy is ${}_1$ :

$($d$)$ Assuming $=0\mathrm{.}5,$ the action$-$value of $x,$ left under policy ${}_1$ is:

The plot below shows the target value per time step as a grey line. Apply the equation below

to determine the estimates for time step $2$ to $13.$ Draw your answers on the graph below, where the first

value is provided in blue. Show all your calculations.

$Q_{n+1}=Q_n+[R_n-Q_n]$