Answers.Body: <p>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 <span class="math-container">$v_{L,n}(S_0) = v_{R,n}(S_0)$</span>. </p>
  
  <p>I will show for case B when <span class="math-container">$\gamma = 0.9$</span> 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. </p>
  
  <p>Now, as you stated <span class="math-container">$v(s) = \mathbb{E}[R_{t+1} + \gamma v(S_{t+1}) | S_t = s]$</span>. Assuming that <span class="math-container">$\gamma = 0.9$</span> 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. </p>
  
  <h2>'Left Policy'</h2>
  
  <p><span class="math-container">\begin{align}v(s_0) &amp;= 1 + 0.9 \times v(s_L) \\ v(s_L) &amp;= 0 + 0.9 \times v(s_0) \\ v(s_R) &amp;= 2 + 0.9 \times v(s_0)
  \end{align}</span>
  We can solve this set of linear equations to get <span class="math-container">$v(s_0) = \frac{100}{19}, v(s_L) = \frac{90}{19}, v(s_R) = \frac{128}{19}\;.$</span></p>
  
  <h2>'Right Policy'</h2>
  
  <p><span class="math-container">\begin{align}v(s_0) &amp;= 0 + 0.9 \times v(s_R) \\ v(s_L) &amp;= 0 + 0.9 \times v(s_0) \\ v(s_R) &amp;= 2 + 0.9 \times v(s_0)
  \end{align}</span>
  We can again solve these to obtain <span class="math-container">$v(s_0) = \frac{180}{19}, v(s_L) = \frac{162}{19}, v(s_R) = \frac{200}{19}\;.$</span></p>
  
  <p>As we can see, for each of the states the value function is larger for <em>all</em> of the states under the policy 'go right', thus this is the optimal policy for the case of <span class="math-container">$\gamma = 0.9$</span>. </p>
  
  <p>It is important to note that if we take the 'left' action in state <span class="math-container">$s_0$</span> then our policy would never take us to state <span class="math-container">$s_R$</span>, and the same for the right action and state <span class="math-container">$s_L$</span>, however due to the definition of an optimal policy requiring <span class="math-container">$v_{\pi ^*}(s) \geq v_{\pi}(s)\; \forall s \in \mathcal{S}$</span> 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 <span class="math-container">$s_R$</span> will change whether we go right or left, because the value of this state depends on the value of <span class="math-container">$s_0$</span>, which clearly changes depending on whether we go right or left. </p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-15T12:40:09.560Z
Answers.Text: 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?
Answers.UserDisplayName: tmaric
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-15T12:50:49.003Z
Answers.Text: 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.
Answers.UserDisplayName: David
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-15T12:52:01.787Z
Answers.Text: 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.
Answers.UserDisplayName: David
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-15T12:53:12.367Z
Answers.Text: You're welcome, glad that I could help.
Answers.UserDisplayName: David
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-15T11:38:13.493Z
Answers.LastActivityDate: 2020-06-15T12:57:18.727Z
Answers.LastEditDate: 2020-06-15T12:57:18.727Z
Answers.UserDisplayName: David
Body: <p>The goal is to find an optimal deterministic policy for this MDP: </p>
  
  <p><a href="https://i.sstatic.net/TegpT.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/TegpT.png" alt="enter image description here"></a></p>
  
  <p>There are two possible policies: left (L) and right (R). What is the optimal policy, when different discounts are used: </p>
  
  <p>A <span class="math-container">$\gamma = 0$</span></p>
  
  <p>B <span class="math-container">$\gamma = 0.9$</span></p>
  
  <p>C <span class="math-container">$\gamma = 0.5$</span></p>
  
  <p>The optimal policy <span class="math-container">$\pi_* \ge \pi$</span> if <span class="math-container">$v_{\pi^*}(s) \ge v_{\pi}(s), \forall s \in S$</span>, 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). </p>
  
  <p>The Bellman equation for the state value function is </p>
  
  <p><span class="math-container">$v(s) = E_\pi[G_t | S_t= s] = E_\pi[R_{t+1} + \gamma v(S_{t+1}) | S_t = s]$</span></p>
  
  <p>The suffix <span class="math-container">$_n$</span> marks the current iteration, and <span class="math-container">$_{n+1}$</span> marks the next iteration. The following is valid if the value function is initialized to <span class="math-container">$0$</span> or some random <span class="math-container">$x \ge 0$</span>.</p>
  
  <p>A) <span class="math-container">$\gamma = 0$</span></p>
  
  <p><span class="math-container">$v_{L,n+1}(S_0) = 1 + 0 v_{L,n}(S_L) = 1$</span></p>
  
  <p><span class="math-container">$v_{R,n+1}(S_0) = 0 + 0 v_{R,n}(S_R) = 0$</span></p>
  
  <p><span class="math-container">$L$</span> is optimal in case A. </p>
  
  <p>B) <span class="math-container">$\gamma = 0.9$</span></p>
  
  <p><span class="math-container">$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)$</span></p>
  
  <p><span class="math-container">$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)$</span></p>
  
  <p><span class="math-container">$R$</span> is optimal in case B.</p>
  
  <p>C) <span class="math-container">$\gamma = 0.5$</span></p>
  
  <p><span class="math-container">$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)$</span></p>
  
  <p><span class="math-container">$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)$</span></p>
  
  <p>Both <span class="math-container">$R$</span> and <span class="math-container">$L$</span> are optimal in case C. </p>
  
  <p><strong>Question</strong>: Is this correct? </p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-15T11:20:19.693Z
Comments.Text: 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$.
Comments.UserDisplayName: David
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-15T11:31:44.357Z
Comments.Text: "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).
Comments.UserDisplayName: tmaric
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-15T11:38:39.743Z
Comments.Text: I just posted a solution to section B so you can see a way of doing it to obtain numerical solutions. :-)
Comments.UserDisplayName: David
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-15T12:29:01.913Z
Comments.Text: @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.
Comments.UserDisplayName: tmaric
Tags: <reinforcement-learning>
Title: Solution to exercise 3.22 in the RL book by Sutton and Barto
UserDisplayName: tmaric
ThreadText: # Solution to exercise 3.22 in the RL book by Sutton and Barto
  
  (Asked by: username_0 on 2020-06-15)
  
  The goal is to find an optimal deterministic policy for this MDP:
  
  [![enter image description here](https://i.sstatic.net/TegpT.png)](https://i.sstatic.net/TegpT.png)
  
  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?
  
  **Tags:** reinforcement-learning
  > **Comments:**
  > **username_1**: 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$.  
  > **username_0**: "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).  
  > **username_1**: I just posted a solution to section B so you can see a way of doing it to obtain numerical solutions. :-)  
  > **username_0**: @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.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-06-15. Score: 2 | Accepted answer
  
  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.
  
  > **Comments:**
  > **username_0**: 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?  
  > **username_1**: 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.  
  > **username_1**: 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.  
  > **username_1**: You're welcome, glad that I could help.  
  
  ---
  
  