Suppose that a machine can be in four different states {0, 1, 2, 3}where the higher the state is the worse the condition of the machine is. Thus, state 0 can be considered a brand new machine and state 3 represents a broken machine. At each decision epoch you would like to determine to keep the machine as it is or replace it by a brand new machine. Note that if the machine is in state 3, it needs to be replaced. We assume that between decision epochs the state of the machine either stays the same or gets worse with equal probability. For example if the machine is in state 0, it will be in states 0,1,2,3 with probability 1/4 at the beginning of the next period whereas if the machine is in state 1, it will be in states 1,2,3 with probability 1/3 at the beginning of the next period. There is a fixed reward of $10,000 per period, an operating cost of h(s) = 1000s for s = 0, 1, 2, 3 and the replacement cost is $2000. Suppose your objective is to determine the long-run average optimal replacement policy. Is this problem recurrent or unichain? If it is, compute the long-run average optimal policy using policy iteration.

PLEASE DO THE WORK IN ENTIRETY AND DON'T SKIP STEPS. Thanks :)