Answers.Body: <p>I think you have constructed a bad case for the algorithm as given. You have created an infinite loop and set starting values such that there is no chance for the loop to break out. You have also deliberately set up a starting policy for an episodic problem where the episode cannot terminate.</p>
  <p>One simple rule to avoid this is to set <span class="math-container">$\pi$</span> to the stochastic equiprobable policy initially (i.e. the first policy will explore all edges of the MDP, making it very hard - maybe impossible - to construct bad cases), and all initial <span class="math-container">$V$</span> to <span class="math-container">$0$</span>. Although these can be set <em>arbitrarily</em>, it is not the user of the solver that normally gets to decide these initialisations, but the person implementing the solver.</p>
  <p>So, yes, the algorithm as shown does let you deliberately break it through apparently free choices that are not covered in the book. However, these look like edge cases that were maybe not worth covering in detail. The algorithm works if you pick <em>reasonable</em> arbitrary choices, but defining &quot;reasonable&quot; is fiddly and might distract from the introduction to the topic.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-19T11:06:59.167Z
Answers.Text: I agree with your second point, but not with the first. If $\gamma < 1$ it seems to always work.
  I made a toy repository if you want to fiddle with the numbers and/or check if I did something wrong: https://github.com/Gregwar/policy_iteration_initialization
Answers.UserDisplayName: Gregwar
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-19T12:13:17.527Z
Answers.Text: @Gregwar: You are right, it works. I was forgetting that the update step re-evaluates the bootstrap values to pick the optimal action. As soon as predicted values from evaluation drop below the actual reward received by transitioning to the terminal state, the polciy switches to that final transition.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-19T12:15:47.950Z
Answers.Text: @Gregwar I dropped my bullet points as they are not relevant to the take-away, which is "arbitrary" means "person writing solver controls it, and has plenty of free choice", and not literally "works for all values".
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-19T12:27:00.337Z
Answers.Text: Ok, I see. But I feel like they'd better give slightly more conservative preconditions that works all the time and let the "person writing solver" take advantages of less conservative reality rather than writing "arbitrary", where it is easy to find a counter-example and thus deceptive :-)
Answers.UserDisplayName: Gregwar
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-17T20:52:59.163Z
Answers.LastActivityDate: 2022-02-19T12:14:35.633Z
Answers.LastEditDate: 2022-02-19T12:14:35.633Z
Answers.UserDisplayName: Neil Slater
Body: <p>In Sutton and Barto's book (Reinforcement learning: An introduction. MIT press, 2018), the algorithm &quot;Policy Iteration&quot; is:
  <a href="https://i.sstatic.net/Bw1ou.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/Bw1ou.png" alt="Policy Iteration algorithm" /></a></p>
  <p>Here, <span class="math-container">$V(s)$</span> is initialized arbitrarily, meaning that I can choose anything I want. Moreover, I think nothing is stated about <span class="math-container">$\gamma$</span> here so we can consider undiscounted environments where <span class="math-container">$\gamma = 1$</span>.
  Now suppose we use the following environment:</p>
  <p><img src="https://i.sstatic.net/m6zEe.png" alt="MDP2" /></p>
  <p>If I initialize:</p>
  <ul>
  <li><span class="math-container">$V(s_1) = 10$</span></li>
  <li><span class="math-container">$V(s_2) = 10$</span></li>
  <li><span class="math-container">$V(s_3) = 0$</span></li>
  <li><span class="math-container">$\pi(s_1) = a_1$</span></li>
  <li><span class="math-container">$\pi(s_2) = a_3$</span></li>
  </ul>
  <p>With this, it appears that the &quot;Policy Evaluation&quot; part will not have any effect and the algorithm will immediately stops, outputing a policy where the optimal actions are <span class="math-container">$\pi(s_1) = a_1$</span> and <span class="math-container">$\pi(s_2) = a_3$</span>. What am I missing ?</p>
  <hr />
  <p>EDIT: I made a toy repository to reproduce, if you want to tweak the numbers of point out something I misunderstood: <a href="https://github.com/Gregwar/policy_iteration_initialization/blob/master/policy_iteration.py" rel="nofollow noreferrer">https://github.com/Gregwar/policy_iteration_initialization/blob/master/policy_iteration.py</a></p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-02-17T13:38:26.907Z
Comments.Text: (I think the thing is that $\gamma = 1$ can only be used if all episodes terminate, else it *has* to be $< 1$. Else the episode returns is not well-defined.)
Comments.UserDisplayName: Gregwar
Tags: <reinforcement-learning><value-functions><policies><policy-iteration>
Title: Is the initialisation of $V(s)$ and $\pi(s)$ really arbitrary in policy iteration?
UserDisplayName: Gregwar
ThreadText: # Is the initialisation of $V(s)$ and $\pi(s)$ really arbitrary in policy iteration?
  
  (Asked by: username_0 on 2022-02-17)
  
  In Sutton and Barto's book (Reinforcement learning: An introduction. MIT press, 2018), the algorithm "Policy Iteration" is:
  [![Policy Iteration algorithm](https://i.sstatic.net/Bw1ou.png)](https://i.sstatic.net/Bw1ou.png)
  
  Here, $V(s)$ is initialized arbitrarily, meaning that I can choose anything I want. Moreover, I think nothing is stated about $\gamma$ here so we can consider undiscounted environments where $\gamma = 1$.
  Now suppose we use the following environment:
  
  ![MDP2](https://i.sstatic.net/m6zEe.png)
  
  If I initialize:
  
  * $V(s\_1) = 10$
  * $V(s\_2) = 10$
  * $V(s\_3) = 0$
  * $\pi(s\_1) = a\_1$
  * $\pi(s\_2) = a\_3$
  
  With this, it appears that the "Policy Evaluation" part will not have any effect and the algorithm will immediately stops, outputing a policy where the optimal actions are $\pi(s\_1) = a\_1$ and $\pi(s\_2) = a\_3$. What am I missing ?
  
  ---
  
  EDIT: I made a toy repository to reproduce, if you want to tweak the numbers of point out something I misunderstood: <https://github.com/username_0/policy_iteration_initialization/blob/master/policy_iteration.py>
  
  **Tags:** reinforcement-learning, value-functions, policies, policy-iteration
  
  > **Comments:**
  > **username_0**: (I think the thing is that $\gamma = 1$ can only be used if all episodes terminate, else it *has* to be $< 1$. Else the episode returns is not well-defined.)  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2022-02-17. Score: 1
  
  I think you have constructed a bad case for the algorithm as given. You have created an infinite loop and set starting values such that there is no chance for the loop to break out. You have also deliberately set up a starting policy for an episodic problem where the episode cannot terminate.
  
  One simple rule to avoid this is to set $\pi$ to the stochastic equiprobable policy initially (i.e. the first policy will explore all edges of the MDP, making it very hard - maybe impossible - to construct bad cases), and all initial $V$ to $0$. Although these can be set *arbitrarily*, it is not the user of the solver that normally gets to decide these initialisations, but the person implementing the solver.
  
  So, yes, the algorithm as shown does let you deliberately break it through apparently free choices that are not covered in the book. However, these look like edge cases that were maybe not worth covering in detail. The algorithm works if you pick *reasonable* arbitrary choices, but defining "reasonable" is fiddly and might distract from the introduction to the topic.
  
  > **Comments:**
  > **username_0**: I agree with your second point, but not with the first. If $\gamma < 1$ it seems to always work. I made a toy repository if you want to fiddle with the numbers and/or check if I did something wrong: https://github.com/username_0/policy_iteration_initialization  
  > **username_1**: @username_0: You are right, it works. I was forgetting that the update step re-evaluates the bootstrap values to pick the optimal action. As soon as predicted values from evaluation drop below the actual reward received by transitioning to the terminal state, the polciy switches to that final transition.  
  > **username_1**: @username_0 I dropped my bullet points as they are not relevant to the take-away, which is "arbitrary" means "person writing solver controls it, and has plenty of free choice", and not literally "works for all values".  
  > **username_0**: Ok, I see. But I feel like they'd better give slightly more conservative preconditions that works all the time and let the "person writing solver" take advantages of less conservative reality rather than writing "arbitrary", where it is easy to find a counter-example and thus deceptive :-)  
  
  ---
  
  