1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Gambler's problem has multiple solutions. It is stated by the one of the author himself. Check here: incompleteideas.net/book/first/gamblers.html $\endgroup$ – DuttaA Sep 5 at 12:14
  • $\begingroup$ @DuttaA Multiple solutions, yes. But the optimal value function must be unique. $\endgroup$ – Asher Sep 14 at 20:01
3
$\begingroup$

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

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.