Recently I simulated the Gambler's Problem in RL:
Now, the problem is, the curve does not at all appear the way as given in the book. The "best policy" curve appears a lot more undulating than it is shown based on the following factors:
- Sensitivity (i.e. the threshold for which you decide the state values have converged).
- Probability of heads (expected).
- Depending the value of sensitivity it also depends on whether I find the policy by finding the action (bet) which cause the maximum return by using $>$ or by using $>=$ in the following code i.e:
initialize maximum = -inf
best_action = None
loop over states:
loop over actions of the state:
if(action_reward>maximum):
best_action = action
Also note that if we make the final reward as 101 instead of 100 the curve becomes more uniform. This problem has also been noted in the following thread.
So what is the actual intuitive explanation behind such a behaviour of the solution. Also here is the thread where this problem is discussed.