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

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?

• Yes, these are all correct. You can get numerical values for each state-value function by solving some linear equations, because the environment is deterministic and you are looking for a deterministic policy you don't need to take any horrible expectations and can be solved using dynamic programming, which you will get to in chapter 4. I'm not sure exactly on your method how you have arrived at these conclusions however, e.g. in the final case how do you know that $v_{R,n}(S_0) = v_{L,n}(S_0)$? You also calculated for each state, which is required when $\gamma \neq 0$. – David Ireland Jun 15 '20 at 11:20
• "horrible expectations" As someone just starting to learn about this, I find them horrible as well. :) Regarding your question: this diagram is returning immediately from the next, to the initial state, so I just applied the Bellman equation for the value state function until I reached the root (starting) node. For this diagram, it turns out that a single look ahead step is sufficient to do this. When you look at C, you'll find $\gamma = 0.5$ multiplied with the value at either $S_{L,n}$, or $S_{R,n}$ (depending on the policy), and this is the next reward + next value (root value). – tmaric Jun 15 '20 at 11:31
• I just posted a solution to section B so you can see a way of doing it to obtain numerical solutions. :-) – David Ireland Jun 15 '20 at 11:38
• @DavidIreland: yes, there might be a serious flaw in my thinking, because I was focused on initial values too much. Meaning: $v_{L,0}(S_0) = v_{R,0}(S_0)=v(S_0)$. Then I can conclude what I did for C only in the first iteration, not for every iteration. – tmaric Jun 15 '20 at 12:29

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.

• Hm. Still I don't understand why $v(s_R)$ is evaluated as if the right policy is taken, for the left policy? If I want to evaluate all states of this MDP for always following left (L), then $v(s_R)$ doesn't change, does it? – tmaric Jun 15 '20 at 12:40
• Because of the definition of the state-value function, if we are in state $s_R$ then the value function is the expected reward + the value function for the state we transition into, which is $s_0$. Under the policy of 'go left', if we start in $s_0$ we would never reach $s_R$ but it still needs to be updated because the definition of a value function is that we condition on the current state we are in, and to find an optimal policy involved calculating the value function for all states, even if it s a state the policy would never take us. – David Ireland Jun 15 '20 at 12:50
• Also, $v(s_R)$ and $v(s_L)$ depend on the value of state $s_0$ due to the bellman equation, and the value of $v(s_0)$ will change depending on whether you take left or right in that state, as you can see from the workings out. – David Ireland Jun 15 '20 at 12:52
• Thanksa lot! Understood! :) – tmaric Jun 15 '20 at 12:52
• You're welcome, glad that I could help. – David Ireland Jun 15 '20 at 12:53