1
$\begingroup$

Recently I simulated the Gambler's Problem in RL:

enter image description here

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ The writer Prof. Sutton himself has commented that he cannot give any explanation, so I thought to ask her. Check the link! $\endgroup$
    – user9947
    May 22, 2019 at 16:26
  • 1
    $\begingroup$ @DuttaA I think what he is saying in that link is that there are many possible solutions. The form of the solutions makes a lot of sense too. Perhaps I will do a formal analysis of this (or maybe someone else here will!), but I think this basically just boils down to the MDP's solution space being under-determined because there's no discounting factor. I suspect that if a discounting factor is added, a unique solution emerges. $\endgroup$
    – John Doucette
    May 22, 2019 at 16:38
  • 1
    $\begingroup$ Actually if p > 0.5 and p < 1 for heads, you should get a deterministic solution of bet minimum amount (1) always. It is only p <= 0.5 when the double-or-quits logic kicks in. $\endgroup$
    – Neil Slater
    May 22, 2019 at 18:55
  • $\begingroup$ @JohnDoucette I forgot about the 2nd part of my answer. Why do you think the policy becomes stable if the final is reward is 101 instead of 100? Someone in the thread noted it and I cross checked it, it's happening. $\endgroup$
    – user9947
    May 23, 2019 at 3:04
  • 1
    $\begingroup$ @DuttaA My guess is that when the target amount is odd, a lot of the potential ties should go away because there no longer exists any (sane) amount you can bet that simultaneously reaches the win condition and the lose condition. $\endgroup$
    – John Doucette
    May 23, 2019 at 3:37

You must log in to answer this question.