Consider an MDP with n states s1, s2, ..., sn and 2 actions a1, a2 at each state. At each state si w ...

---

Consider an MDP with n states s1, s2, ..., sn and 2 actions a1, a2 at each state. At each state si with i < n, action a1 takes the agent to s(i+1), and for state sn, action a1 is a self-loop that keeps the agent in sn. At any state other than sn, action a2 takes the agent back to s1; at sn, a2 is again a self-loop. The reward R(si, aj) is 0 except for (sn, a1), which has a value of 1. The agent takes one action at each step. Under the uniform random policy, the agent at each state chooses one of the available actions uniformly at random. Show your work. (a) Compute the expected number of steps for the uniform random policy to go from state s1 to state sn. (b) In a discounted-reward setting with discount factor gamma, let Q(si, aj) be the action-value function of the uniform random policy. Prove that for all i < n, Q(si, a1) > Q(si, a2).