Problem 1: Consider a Markov chain {Xn:n=0,1,2} having three states {0,1,2} with the following transition probability matrix. At each state, you can make one of two actions {1,2}. For each action taken, transition probabilities are given as follows: Action 1: P(1)=1/21/41/201/201/21/41/2 Action 2: P(2)=01/21/21/21/41/21/21/40 Each state will be rewarded by the following values. 1) Formulate the linear programming problem that maximizes the expected average reward. 2) (Bonus) solve this linear programming problem and get the answer for optimal policy (all s)