Solution to exercise 3.22 in the RL book by Sutton and Barto

Question

The goal is to find an optimal deterministic policy for this MDP:

There are two possible policies: left (L) and right (R). What is the optimal policy, when different discounts are used:

A $\gamma = 0$

B $\gamma = 0.9$

C $\gamma = 0.5$

The optimal policy $\pi_* \ge \pi$ if $v_{\pi^*}(s) \ge v_{\pi}(s), \forall s \in S$, so to find the optimal policy, the goal is to check which one of those results in the largest state value function for all states in the system given discount factors (A,B,C).

The Bellman equation for the state value function is

$v(s) = E_\pi[G_t | S_t= s] = E_\pi[R_{t+1} + \gamma v(S_{t+1}) | S_t = s]$

The suffix $_n$ marks the current iteration, and $_{n+1}$ marks the next iteration. The following is valid if the value function is initialized to $0$ or some random $x \ge 0$.

A) $\gamma = 0$

$v_{L,n+1}(S_0) = 1 + 0 v_{L,n}(S_L) = 1$

$v_{R,n+1}(S_0) = 0 + 0 v_{R,n}(S_R) = 0$

$L$ is optimal in case A.

B) $\gamma = 0.9$

$v_{L,n+1}(S_0) = 1 + 0.9 v_{L,n}(S_L) = 1 + 0.9(0 + 0.9 v_{L,n}(S_0)) = 1 + 0.81v_{L,n}(S_0)$

$v_{R,n+1}(S_0) = 0 + 0.9 v_{R,n}(S_R) = 0 + 0.9(2 + 0.9 v_{R,n}(S_0)) = 1.8 + 0.81v_{R,n}(S_0)$

$R$ is optimal in case B.

C) $\gamma = 0.5$

$v_{L,n+1}(S_0) = 1 + 0.5 v_{L,n}(S_L) = 1 + 0.5(0 + 0.9 v_{L,n}(S_0)) = 1 + 0.45v_{L,n}(S_0)$

$v_{R,n+1}(S_0) = 0 + 0.5 v_{R,n}(S_R) = 0 + 0.5(2 + 0.9 v_{R,n}(S_0)) = 1 + 0.45v_{R,n}(S_0)$

Both $R$ and $L$ are optimal in case C.

Question: Is this correct?

Answer 1

Your answer is correct but I am not sure exactly on how you arrived at it, as e.g. in the last case you don't know that $v_{L,n}(S_0) = v_{R,n}(S_0)$.

I will show for case B when $\gamma = 0.9$ as case A is trivial and hopefully you can apply what I've done in case B to case C so that you get exact answers.

Now, as you stated $v(s) = \mathbb{E}[R_{t+1} + \gamma v(S_{t+1}) | S_t = s]$. Assuming that $\gamma = 0.9$ we can calculate the values for each state under the policy of taking the left action. Note that because we are looking for deterministic policies and the environment is deterministic then a lot of the expectations can be disregarded as nothing random is happening.

'Left Policy'

\begin{align}v(s_0) &= 1 + 0.9 \times v(s_L) \\ v(s_L) &= 0 + 0.9 \times v(s_0) \\ v(s_R) &= 2 + 0.9 \times v(s_0) \end{align} We can solve this set of linear equations to get $v(s_0) = \frac{100}{19}, v(s_L) = \frac{90}{19}, v(s_R) = \frac{128}{19}\;.$

'Right Policy'

\begin{align}v(s_0) &= 0 + 0.9 \times v(s_R) \\ v(s_L) &= 0 + 0.9 \times v(s_0) \\ v(s_R) &= 2 + 0.9 \times v(s_0) \end{align} We can again solve these to obtain $v(s_0) = \frac{180}{19}, v(s_L) = \frac{162}{19}, v(s_R) = \frac{200}{19}\;.$

As we can see, for each of the states the value function is larger for all of the states under the policy 'go right', thus this is the optimal policy for the case of $\gamma = 0.9$.

It is important to note that if we take the 'left' action in state $s_0$ then our policy would never take us to state $s_R$, and the same for the right action and state $s_L$, however due to the definition of an optimal policy requiring $v_{\pi ^*}(s) \geq v_{\pi}(s)\; \forall s \in \mathcal{S}$ then we must evaluate the value function for all states, even ones that would not be visited under a policy you are evaluating. This means that the state for $s_R$ will change whether we go right or left, because the value of this state depends on the value of $s_0$, which clearly changes depending on whether we go right or left.