Answers.Body: <p>The other answers are cool, here I give a straightforward proof, it might be more clearly for understanding the whole process.</p>
  <p>The core idea here is that since each state can rollback to the previous state (the state before State S is itself), and each time it rollbacks to the previous state, the expected value of steps should increase the expectation of the previous state. The number of steps, which is ultimately expressed in the form of an infinite series.</p>
  <p>Assuming that the action Left is selected in the first <span class="math-container">$t-1$</span> steps, and the action Right is selected in the <span class="math-container">$t$</span>-th step, a total of <span class="math-container">$t$</span> steps are required to reach the State 2, where <span class="math-container">$ t \in [1, \infty) $</span>:</p>
  <p><span class="math-container">$ E_{S\rightarrow 2}=1\cdot p^1+2\cdot p^1 (1-p)^1+3\cdot p^1 (1-p)^2+\cdots=p\sum_{t=1}^{\infty}t(1-p)^{t-1} $</span>
  <span class="math-container">$ =\frac{p}{1-p}\sum_{t=1}^{\infty}t(1-p)^t=\frac{p}{1-p}\cdot\frac{1-p}{p^2} = \frac{1}{p} $</span></p>
  <p>The transition from State 2 to State 3 is divided into two cases, namely 2→3, 2→S→2→3, and if rollbacking from 2 to S, it is necessary to recursively calculate the expected number of steps from 2→S→2: <span class="math-container">$ E_{s\rightarrow 2} $</span>, where <span class="math-container">$t$</span> is the total number of times to return to state S:</p>
  <p><span class="math-container">$ E_{2\rightarrow 3}=(1-p)+(2+E_{S\rightarrow2})p(1-p)+(3+2E_{S\rightarrow2})p^2(1-p)+\cdots $</span>
  <span class="math-container">$ =(1-p)+(1-p)\sum_{t=1}^{\infty}\left[1+t(1+E_{S\rightarrow2})\right]p^t$</span>
  <span class="math-container">$ =(1-p)+p+\frac{1-p^2}{p}\frac{p}{(1-p)^2} = 1+\frac{1+p}{1-p} = \frac{2}{1-p}$</span></p>
  <p><span class="math-container">$ E_{3\rightarrow G} $</span> can be obtained in the same way:</p>
  <p><span class="math-container">$ E_{3\rightarrow G}=p+(2+E_{2\rightarrow3})p(1-p)+(3+2E_{2\rightarrow3})p(1-p)^2+\cdots $</span>
  <span class="math-container">$ =p+p\sum_{t=1}^{\infty}\left[1+t(1+E_{2\rightarrow3})\right](1-p)^t $</span>
  <span class="math-container">$ = p+ p \left[ \frac{1-p}{p} + \frac{3-p}{1-p} \frac{1-p}{p^2} \right] = p+(1-p) + \frac{3-p}{p} = \frac{3}{p} $</span></p>
  <p>Above we have calculated the expected number of steps for the three state transitions <span class="math-container">$ E_{S\rightarrow 2}, E_{2\rightarrow 3}, E_{3\rightarrow G} $</span>, so the total expected value is:</p>
  <p><span class="math-container">$ E = E_{S\rightarrow 2} + E_{2\rightarrow 3} + E_{3\rightarrow G} = \frac{4}{p} + \frac{2}{1-p} $</span></p>
  <p>To maximize the expectation, then</p>
  <p><span class="math-container">$ \left[\frac{4}{p} + \frac{2}{1-p}\right]^{\prime} = -\frac{4}{p^2}+\frac{2}{(1-p)^2} = 0 $</span></p>
  <p>Get a solution that satisfies the condition: <span class="math-container">$ p=2-\sqrt{2}\approx 0.5858, E=6+4\sqrt{2} \approx 11.6568 $</span>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-10-23T08:40:25.433Z
Answers.LastActivityDate: 2022-10-23T09:27:05.173Z
Answers.LastEditDate: 2022-10-23T09:27:05.173Z
Answers.UserDisplayName: FERRYSELING
Answers.Body: <p>Here is a simple way to solve the problem.<br />
  With probability <code>p</code> of moving right in normal grids, we can write down the transition matrix.</p>
  <p><span class="math-container">$$
  Q=\begin{bmatrix} 1-p &amp; p &amp; 0 \\
  p &amp; 0 &amp; 1-p \\
  0 &amp; 1-p &amp; 0 \end{bmatrix}
  $$</span></p>
  <p>From this answer we have the method to calculate the expected steps between two states.
  <a href="https://math.stackexchange.com/questions/691494/expected-number-of-steps-between-states-in-a-markov-chain">https://math.stackexchange.com/questions/691494/expected-number-of-steps-between-states-in-a-markov-chain</a></p>
  <p>which is, the sum of the first row of the matrix <span class="math-container">$(I-Q)^{-1}$</span></p>
  <p><span class="math-container">$$
  M=(I-Q)^{-1}=\begin{bmatrix} \frac{2}{p}+\frac{1}{1-p} &amp; \frac{1}{p}+\frac{1}{1-p} &amp; \frac{1}{p} \\
  \frac{1}{p}+\frac{1}{1-p} &amp; \frac{1}{p}+\frac{1}{1-p} &amp; \frac{1}{p} \\
  \frac{1}{p} &amp; \frac{1}{p} &amp; \frac{1}{p} \end{bmatrix}
  $$</span>
  So the expectation of the number of steps is</p>
  <p><span class="math-container">$$
  E[t]=\frac{4}{p}+\frac{2}{1-p}
  $$</span></p>
  <p>And since the reward is -1 per step
  <span class="math-container">$$J(p)=-E[t]=-\frac{4}{p}-\frac{2}{1-p}$$</span></p>
  <p><span class="math-container">$$
  \frac{dJ}{dp}=\frac{4}{p^2}-\frac{2}{(1-p)^2}=0
  $$</span>
  <span class="math-container">$$ 2p^2=4(1-p)^2 $$</span>
  <span class="math-container">$$ p^2-4p+2=0 $$</span></p>
  <p>We then have solutions <span class="math-container">$p=2\pm\sqrt{2}$</span>, and since <span class="math-container">$p$</span> is a probability in <span class="math-container">$[0,1]$</span>
  <span class="math-container">$$ \hat{p} = 2-\sqrt{2} \approx 0.586 $$</span></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-04-05T13:18:54.470Z
Answers.LastActivityDate: 2022-04-05T13:18:54.470Z
Answers.UserDisplayName: Alex Fan
Answers.Body: <p>As Alex mentioned, this is a typical mean time to absorption type of problem in a Markov chain except each step incurs a negative reward. So, yet another way to solve this problem is to set up a system of equations. Let <span class="math-container">$v_1, v_2, v_3$</span> denote the mean reward starting from states 1, 2, and 3, respectively. Then we have:</p>
  <p><span class="math-container">$$
  \begin{cases}
  v_1 =&amp; (1-p)v_1 + pv_2 -1 \\
  v_2 =&amp; (1-p)v_3 + pv_1 -1 \\
  v_3 =&amp; (1-p)(v_2-1)
  \end{cases}
  $$</span></p>
  <p>Solving this gives <span class="math-container">$v_1 = \frac{p^2-3p+4}{p(p-1)}$</span>. Now, taking the derivative and setting it to 0 yields <span class="math-container">$p^* = 2-\sqrt{2}$</span></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-08-12T13:19:39.300Z
Answers.LastActivityDate: 2023-08-12T13:19:39.300Z
Answers.UserDisplayName: Xinsong Lin
Answers.Body: <p>There are problems with both the approach and the expressions that you have. I don't want to just give the correct solution, though, that's an exercise for you to go through and learn from your own experience trying to accomplish it. Instead, let me illustrate that your expressions for <span class="math-container">$v(s_i)$</span> are wrong. To do that we'll just do a Monte-Carlo estimate for a range of values of <span class="math-container">$p$</span> and compare to your expression.</p>
  <p>Here's the Python code that runs a single payout starting from state <code>state</code> and following the policy with probability <code>p</code> of choosing &quot;right&quot;. It returns the collected reward:</p>
  <pre><code>import numpy as np
  
  def playout(state, p):
     reward = 0
     while state != 0:
         action_right = np.random.rand() &lt; p
         move_right = action_right if state != 2 else (not action_right)
         state = state - 1 if move_right else state + 1
         state = 3 if state &gt; 3 else state
         reward -= 1
     return reward
  </code></pre>
  <p>Then we make a simulation code that runs the <code>playout</code> multiple times, collects the reward counts, and returns the average reward (so, essentially estimates <span class="math-container">$v^\pi(s_i)$</span>):</p>
  <pre><code>from collections import defaultdict
  
  def simulate(state, p, n):
      rewards = defaultdict(lambda : 0, {})
      for _ in range(n):
          rewards[playout(state,p)] += 1
      results = np.array([[a,b] for a,b in rewards.items()]).T
      reward , nplayouts = results[0] , results[1]
      value = (reward * nplayouts).sum() / nplayouts.sum()
      return value
  </code></pre>
  <p>Finally, I make a grid in <code>p</code> and run each playout 10000 times:</p>
  <pre><code>p = np.linspace(0,1,51)[1:-1]
  v3 = [simulate(3,p,10000) for p in p]
  v2 = [simulate(2,p,10000) for p in p]
  v1 = [simulate(1,p,10000) for p in p]
  </code></pre>
  <p>I've plotted the resulting value estimates for each state. Together with your expression for them (blue curves). And the correct expression (red curve) that I've obtained by actually writing down and solving the equations:</p>
  <p><a href="https://i.sstatic.net/eV1Rc.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/eV1Rc.png" alt="enter image description here" /></a></p>
  <p>As you can see, the expressions you've presented are all too far off from the results that the simulation returns. More than that - the asymptotic behavior of your solutions at <span class="math-container">$p\to0$</span> and <span class="math-container">$p\to1$</span> doesn't make much sense.</p>
  <p>I've obtained the expressions for the red curves above by solving the system for <span class="math-container">$v(s_i)$</span> on my own account - without relying on weird and wrong solutions that I googled on the internet. Which I'd recommend you do as well.</p>
  <p>Finally, the question of the exercise is to find an optimal <span class="math-container">$p$</span> for a policy that starts at <span class="math-container">$s_3$</span> - not &quot;<em>irrespective of starting state</em>&quot; as you've thought is should be. Unlike your expression the correct expression for  <span class="math-container">$v(s_3)$</span> has a maximum, which can be found analytically and it is
  <span class="math-container">$$\max_p v(s_3) = -6-4\sqrt2 \simeq -11.6$$</span>
  <span class="math-container">$$ \text{at}\quad p = ??? \simeq 0.59$$</span></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-05-25T19:39:00.077Z
Answers.Text: I reread the question, it is word for word what I wrote in the question, where does it say to find an optimal policy that starts at state $s_3$?
Answers.UserDisplayName: Snowball
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-05-25T20:14:48.977Z
Answers.Text: @Snowball "S" and "G" is a standard notation for start and end states across the book. See e.g. examples 6.5, 6.6, 8.1
Answers.UserDisplayName: Kostya
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-05-24T13:00:09.840Z
Answers.LastActivityDate: 2021-05-24T13:00:09.840Z
Answers.UserDisplayName: Kostya
Body: <p>I'm attempting exercise 13.1 in the Sutton and Barto textbook. It asks for an optimal probability for selecting action right in the short corridor scenario (see first 6 lines of the image below for the scenario).</p>
  <p><strong>Exercise 13.1:</strong> Use your knowledge of the gridworld and its dynamics to determine an
  exact symbolic expression for the optimal probability of selecting the right action in
  Example 13.1.</p>
  <p><strong>My attempt:</strong>
  Letting <span class="math-container">$p$</span> denote the probability of choosing right, I understand that using the Bellman equations, we can solve for the value of <span class="math-container">$s_1, s_2, s_3$</span> where the states are numbered from left to right in terms of <span class="math-container">$p$</span>. We have <span class="math-container">$v(s_1) = \frac{2-p}{p-1}$</span>, <span class="math-container">$v(s_2) = \frac{1}{(p-1)p}$</span>, <span class="math-container">$v(s_3) = -\frac{p+1}{p}$</span>.
  I can see how we can find the max of each of these functions to get the best optimal policy, given the state we're currently in.</p>
  <p>However, how do you find the optimal policy generally (irrespective of starting state)? I found solutions here, which magically arrives at
  <span class="math-container">$\frac{p^2-2p+2}{p(1-p)}$</span>. Can someone explain this part?</p>
  <p><a href="https://github.com/brynhayder/reinforcement_learning_an_introduction/blob/master/exercises/exercises.pdf" rel="nofollow noreferrer">https://github.com/brynhayder/reinforcement_learning_an_introduction/blob/master/exercises/exercises.pdf</a></p>
  <p><a href="https://i.sstatic.net/sluM6.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/sluM6.png" alt="enter image description here" /></a></p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-05-24T09:24:20.983Z
Comments.Text: The expression $(p^2-2p+2)/(p(1-p))$ is positive for all, so I wouldn't rely on it...
Comments.UserDisplayName: Kostya
Tags: <reinforcement-learning>
Title: Sutton and Barto 2nd Edition Exercise 13.1
UserDisplayName: Snowball
ThreadText: # Sutton and Barto 2nd Edition Exercise 13.1
  
  (Asked by: username_0 on 2021-05-24)
  
  I'm attempting exercise 13.1 in the Sutton and Barto textbook. It asks for an optimal probability for selecting action right in the short corridor scenario (see first 6 lines of the image below for the scenario).
  
  **Exercise 13.1:** Use your knowledge of the gridworld and its dynamics to determine an
  exact symbolic expression for the optimal probability of selecting the right action in
  Example 13.1.
  
  **My attempt:**
  Letting $p$ denote the probability of choosing right, I understand that using the Bellman equations, we can solve for the value of $s\_1, s\_2, s\_3$ where the states are numbered from left to right in terms of $p$. We have $v(s\_1) = \frac{2-p}{p-1}$, $v(s\_2) = \frac{1}{(p-1)p}$, $v(s\_3) = -\frac{p+1}{p}$.
  I can see how we can find the max of each of these functions to get the best optimal policy, given the state we're currently in.
  
  However, how do you find the optimal policy generally (irrespective of starting state)? I found solutions here, which magically arrives at
  $\frac{p^2-2p+2}{p(1-p)}$. Can someone explain this part?
  
  <https://github.com/brynhayder/reinforcement_learning_an_introduction/blob/master/exercises/exercises.pdf>
  
  [![enter image description here](https://i.sstatic.net/sluM6.png)](https://i.sstatic.net/sluM6.png)
  
  **Tags:** reinforcement-learning
  > **Comments:**
  > **username_1**: The expression $(p^2-2p+2)/(p(1-p))$ is positive for all, so I wouldn't rely on it...  
  
  ---
  
  ## 4 answers
  
  ### Answer by username_2 on 2022-10-23. Score: 2
  
  The other answers are cool, here I give a straightforward proof, it might be more clearly for understanding the whole process.
  
  The core idea here is that since each state can rollback to the previous state (the state before State S is itself), and each time it rollbacks to the previous state, the expected value of steps should increase the expectation of the previous state. The number of steps, which is ultimately expressed in the form of an infinite series.
  
  Assuming that the action Left is selected in the first $t-1$ steps, and the action Right is selected in the $t$-th step, a total of $t$ steps are required to reach the State 2, where $ t \in [1, \infty) $:
  
  $ E\_{S\rightarrow 2}=1\cdot p^1+2\cdot p^1 (1-p)^1+3\cdot p^1 (1-p)^2+\cdots=p\sum\_{t=1}^{\infty}t(1-p)^{t-1} $
  $ =\frac{p}{1-p}\sum\_{t=1}^{\infty}t(1-p)^t=\frac{p}{1-p}\cdot\frac{1-p}{p^2} = \frac{1}{p} $
  
  The transition from State 2 to State 3 is divided into two cases, namely 2→3, 2→S→2→3, and if rollbacking from 2 to S, it is necessary to recursively calculate the expected number of steps from 2→S→2: $ E\_{s\rightarrow 2} $, where $t$ is the total number of times to return to state S:
  
  $ E\_{2\rightarrow 3}=(1-p)+(2+E\_{S\rightarrow2})p(1-p)+(3+2E\_{S\rightarrow2})p^2(1-p)+\cdots $
  $ =(1-p)+(1-p)\sum\_{t=1}^{\infty}\left[1+t(1+E\_{S\rightarrow2})\right]p^t$
  $ =(1-p)+p+\frac{1-p^2}{p}\frac{p}{(1-p)^2} = 1+\frac{1+p}{1-p} = \frac{2}{1-p}$
  
  $ E\_{3\rightarrow G} $ can be obtained in the same way:
  
  $ E\_{3\rightarrow G}=p+(2+E\_{2\rightarrow3})p(1-p)+(3+2E\_{2\rightarrow3})p(1-p)^2+\cdots $
  $ =p+p\sum\_{t=1}^{\infty}\left[1+t(1+E\_{2\rightarrow3})\right](1-p)^t $
  $ = p+ p \left[ \frac{1-p}{p} + \frac{3-p}{1-p} \frac{1-p}{p^2} \right] = p+(1-p) + \frac{3-p}{p} = \frac{3}{p} $
  
  Above we have calculated the expected number of steps for the three state transitions $ E\_{S\rightarrow 2}, E\_{2\rightarrow 3}, E\_{3\rightarrow G} $, so the total expected value is:
  
  $ E = E\_{S\rightarrow 2} + E\_{2\rightarrow 3} + E\_{3\rightarrow G} = \frac{4}{p} + \frac{2}{1-p} $
  
  To maximize the expectation, then
  
  $ \left[\frac{4}{p} + \frac{2}{1-p}\right]^{\prime} = -\frac{4}{p^2}+\frac{2}{(1-p)^2} = 0 $
  
  Get a solution that satisfies the condition: $ p=2-\sqrt{2}\approx 0.5858, E=6+4\sqrt{2} \approx 11.6568 $.
  
  
  ---
  
  ### Answer by username_3 on 2022-04-05. Score: 1
  
  Here is a simple way to solve the problem.  
  With probability `p` of moving right in normal grids, we can write down the transition matrix.
  
  $$
  Q=\begin{bmatrix} 1-p & p & 0 \\
  p & 0 & 1-p \\
  0 & 1-p & 0 \end{bmatrix}
  $$
  
  From this answer we have the method to calculate the expected steps between two states.
  <https://math.stackexchange.com/questions/691494/expected-number-of-steps-between-states-in-a-markov-chain>
  
  which is, the sum of the first row of the matrix $(I-Q)^{-1}$
  
  $$
  M=(I-Q)^{-1}=\begin{bmatrix} \frac{2}{p}+\frac{1}{1-p} & \frac{1}{p}+\frac{1}{1-p} & \frac{1}{p} \\
  \frac{1}{p}+\frac{1}{1-p} & \frac{1}{p}+\frac{1}{1-p} & \frac{1}{p} \\
  \frac{1}{p} & \frac{1}{p} & \frac{1}{p} \end{bmatrix}
  $$
  So the expectation of the number of steps is
  
  $$
  E[t]=\frac{4}{p}+\frac{2}{1-p}
  $$
  
  And since the reward is -1 per step
  $$J(p)=-E[t]=-\frac{4}{p}-\frac{2}{1-p}$$
  
  $$
  \frac{dJ}{dp}=\frac{4}{p^2}-\frac{2}{(1-p)^2}=0
  $$
  $$ 2p^2=4(1-p)^2 $$
  $$ p^2-4p+2=0 $$
  
  We then have solutions $p=2\pm\sqrt{2}$, and since $p$ is a probability in $[0,1]$
  $$ \hat{p} = 2-\sqrt{2} \approx 0.586 $$
  
  
  ---
  
  ### Answer by username_4 on 2023-08-12. Score: 1
  
  As Alex mentioned, this is a typical mean time to absorption type of problem in a Markov chain except each step incurs a negative reward. So, yet another way to solve this problem is to set up a system of equations. Let $v\_1, v\_2, v\_3$ denote the mean reward starting from states 1, 2, and 3, respectively. Then we have:
  
  $$
  \begin{cases}
  v\_1 =& (1-p)v\_1 + pv\_2 -1 \\
  v\_2 =& (1-p)v\_3 + pv\_1 -1 \\
  v\_3 =& (1-p)(v\_2-1)
  \end{cases}
  $$
  
  Solving this gives $v\_1 = \frac{p^2-3p+4}{p(p-1)}$. Now, taking the derivative and setting it to 0 yields $p^\* = 2-\sqrt{2}$
  
  
  ---
  
  ### Answer by username_1 on 2021-05-24. Score: 1
  
  There are problems with both the approach and the expressions that you have. I don't want to just give the correct solution, though, that's an exercise for you to go through and learn from your own experience trying to accomplish it. Instead, let me illustrate that your expressions for $v(s_i)$ are wrong. To do that we'll just do a Monte-Carlo estimate for a range of values of $p$ and compare to your expression.
  Here's the Python code that runs a single payout starting from state state and following the policy with probability p of choosing "right". It returns the collected reward:
  import numpy as np
  
  def playout(state, p):
     reward = 0
     while state != 0:
         action_right = np.random.rand() < p
         move_right = action_right if state != 2 else (not action_right)
         state = state - 1 if move_right else state + 1
         state = 3 if state > 3 else state
         reward -= 1
     return reward
  
  Then we make a simulation code that runs the playout multiple times, collects the reward counts, and returns the average reward (so, essentially estimates $v^\pi(s_i)$):
  from collections import defaultdict
  
  def simulate(state, p, n):
      rewards = defaultdict(lambda : 0, {})
      for _ in range(n):
          rewards[playout(state,p)] += 1
      results = np.array([[a,b] for a,b in rewards.items()]).T
      reward , nplayouts = results[0] , results[1]
      value = (reward * nplayouts).sum() / nplayouts.sum()
      return value
  
  Finally, I make a grid in p and run each playout 10000 times:
  p = np.linspace(0,1,51)[1:-1]
  v3 = [simulate(3,p,10000) for p in p]
  v2 = [simulate(2,p,10000) for p in p]
  v1 = [simulate(1,p,10000) for p in p]
  
  I've plotted the resulting value estimates for each state. Together with your expression for them (blue curves). And the correct expression (red curve) that I've obtained by actually writing down and solving the equations:
  
  As you can see, the expressions you've presented are all too far off from the results that the simulation returns. More than that - the asymptotic behavior of your solutions at $p\to0$ and $p\to1$ doesn't make much sense.
  I've obtained the expressions for the red curves above by solving the system for $v(s_i)$ on my own account - without relying on weird and wrong solutions that I googled on the internet. Which I'd recommend you do as well.
  Finally, the question of the exercise is to find an optimal $p$ for a policy that starts at $s_3$ - not "irrespective of starting state" as you've thought is should be. Unlike your expression the correct expression for  $v(s_3)$ has a maximum, which can be found analytically and it is
  $$\max_p v(s_3) = -6-4\sqrt2 \simeq -11.6$$
  $$ \text{at}\quad p = ??? \simeq 0.59$$
  
  > **Comments:**
  > **username_0**: I reread the question, it is word for word what I wrote in the question, where does it say to find an optimal policy that starts at state $s_3$?  
  > **username_1**: @Snowball "S" and "G" is a standard notation for start and end states across the book. See e.g. examples 6.5, 6.6, 8.1  
  
  ---
  
  