The problem with the Gambler's Problem in RL 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 $&gt;$ or by using $&gt;=$ in the following code i.e:





 initialize maximum = -inf
 best_action = None
 loop over states:
    loop over actions of the state:
       if(action_reward&gt;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.
The intuitive explanation is that there are many equally good "optimal" policies. This is mentioned at the end of the example problem description you posted. My gut says that the family of optimal policies would be any policy from the double/nothing family. So, for example, if you bet 25 on the first bet instead of 50, I think your overall chances of winning should be the same as if you bet 50, it'll just take longer in expectation. The resulting family of policies will look more undulating than the one in the book.

As Neil notes, for low values of $p$, the probability that you win a gamble, it is the case that there is a unique optimal policy.