Answers.Body: <p>So, naturally, if you've observed something that contradicts the theoretical properties of Value Iteration, something's wrong, right?</p>
  <p>Well, the code you've linked, as it is, is fine. It works as intended when all the values are initialized to zero. HOWEVER, my guess is that you're the one introducing an (admittedly very subtle) error. I think you're changing this:</p>
  <pre><code>state_value = np.zeros(GOAL + 1)
  state_value[GOAL] = 1.0
  </code></pre>
  <p>for this:</p>
  <pre><code>state_value = np.ones(GOAL + 1)
  state_value[GOAL] = 1.0
  </code></pre>
  <p>So, you see, this is wrong. And the reason why it's wrong is that both GOAL (which is 100 in the example) and 0 must have an immutable and fixed values, because they're terminal states, and their values are not subject to estimation. The value for GOAL is 1.0, as you can see in the original code. If you want initial values other than 0, then you must do this:</p>
  <pre><code>state_value = np.ones(GOAL + 1)
  state_value[GOAL] = 1.0
  state_value[0] = 0
  </code></pre>
  <p>In the first case (changing the initial values to 1) what you were seeing was, essentially, an &quot;I don't care policy&quot;. Whatever you do, you'll end with a value of 1. In the second case, with the random values, you saw the classic effects of &quot;garbage in, garbage out&quot;.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-09-05T08:33:29.110Z
Answers.LastActivityDate: 2020-09-05T08:33:29.110Z
Answers.UserDisplayName: Asher
Body: <p>In <a href="http://incompleteideas.net/book/RLbook2020.pdf#page=106" rel="nofollow noreferrer">Example 4.3:Gambler's Problem of Sutton and Barto's book</a> whose code is given <a href="https://github.com/ShangtongZhang/reinforcement-learning-an-introduction/blob/master/chapter04/gamblers_problem.py" rel="nofollow noreferrer">here</a>.
  In this code the value function array is initialized as <code>np.zeros(states)</code> where <code>states</code> <span class="math-container">$\in[0,100]$</span> and the value function for optimal policy which is returned after solving it with value iteration is same as the one given in the book, but, if we only change the initialization of the value function in the code, suppose to <code>np.ones(states)</code> then the optimal value function returned changes too, which means that the value iteration algorithm converges in both the cases but to different optimal value functions,but two different optimal value function is impossible in a MDP. So why is the value iteration algorithm not converging to optimal value function?</p>
  <p>PS: If we change the initialization of value function array to <code>-1*np.random.rand(states)</code>, then the converged optimal value function also contains negative numbers which should be impossible as <code>rewards&gt;=0</code>, hence value iteration fails to converge to optimal value function.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-09-14T20:01:11.903Z
Comments.Text: @DuttaA Multiple solutions, yes. But the optimal value function must be unique.
Comments.UserDisplayName: Asher
Tags: <reinforcement-learning><value-functions><sutton-barto><value-iteration><numpy>
Title: Value Iteration failing to converge to optimal value function in Sutton-Barto's Gambler problem
UserDisplayName: ZERO NULLS
ThreadText: # Value Iteration failing to converge to optimal value function in Sutton-Barto's Gambler problem
  
  (Asked by: username_0 on 2020-09-05)
  
  In [Example 4.3:Gambler's Problem of Sutton and Barto's book](http://incompleteideas.net/book/RLbook2020.pdf#page=106) whose code is given [here](https://github.com/ShangtongZhang/reinforcement-learning-an-introduction/blob/master/chapter04/gamblers_problem.py).
  In this code the value function array is initialized as `np.zeros(states)` where `states` $\in[0,100]$ and the value function for optimal policy which is returned after solving it with value iteration is same as the one given in the book, but, if we only change the initialization of the value function in the code, suppose to `np.ones(states)` then the optimal value function returned changes too, which means that the value iteration algorithm converges in both the cases but to different optimal value functions,but two different optimal value function is impossible in a MDP. So why is the value iteration algorithm not converging to optimal value function?
  
  PS: If we change the initialization of value function array to `-1*np.random.rand(states)`, then the converged optimal value function also contains negative numbers which should be impossible as `rewards>=0`, hence value iteration fails to converge to optimal value function.
  
  **Tags:** reinforcement-learning, value-functions, sutton-barto, value-iteration, numpy
  > **Comments:**
  > **username_1**: @DuttaA Multiple solutions, yes. But the optimal value function must be unique.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-09-05. Score: 3 | Accepted answer
  
  So, naturally, if you've observed something that contradicts the theoretical properties of Value Iteration, something's wrong, right?
  Well, the code you've linked, as it is, is fine. It works as intended when all the values are initialized to zero. HOWEVER, my guess is that you're the one introducing an (admittedly very subtle) error. I think you're changing this:
  state_value = np.zeros(GOAL + 1)
  state_value[GOAL] = 1.0
  
  for this:
  state_value = np.ones(GOAL + 1)
  state_value[GOAL] = 1.0
  
  So, you see, this is wrong. And the reason why it's wrong is that both GOAL (which is 100 in the example) and 0 must have an immutable and fixed values, because they're terminal states, and their values are not subject to estimation. The value for GOAL is 1.0, as you can see in the original code. If you want initial values other than 0, then you must do this:
  state_value = np.ones(GOAL + 1)
  state_value[GOAL] = 1.0
  state_value[0] = 0
  
  In the first case (changing the initial values to 1) what you were seeing was, essentially, an "I don't care policy". Whatever you do, you'll end with a value of 1. In the second case, with the random values, you saw the classic effects of "garbage in, garbage out".
  
  
  ---
  
  