Value Iteration failing to converge to optimal value function in Sutton-Barto's Gambler problem

Question

In Example 4.3:Gambler's Problem of Sutton and Barto's book whose code is given here. 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.

Answer 1

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".