Value Iteration failing to converge to optimal value function in Sutton-Barto's Gambler problem
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 &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;.