# Probabilistic dynamic programming question

A gambler has 2 dollars. He is allowed to play a game four times and his goal is to maximize his probability of ending with at least 6 dollars . If the gambler bets $b$ dollars then with probability $0.4$ he wins the game and increases his capital position by $b$ dollars; with probability $0.6$ he loses the game and decreases his capital by $b$ dollars. On any play of game gambler may not bet more than he has available. Determine the betting strategy that would maximize the gamblers probability of attaining at least $6$ dollars by the end of fourth game.Assume that bets of zero dollars(not betting) are permissible.

By using probabilistic dynamic programming solve this.

I defined as let $f_t(d)$ be the probability by the end of game 4, the gambler will have at least $6$ dollars. $d$ is the amount that he has at the beginning of game $t$ which he can use for betting and let $b_t(d)$ be the amount that he bets to attain $f_t(d)$.

But I don't understand how I can make a recursive relationship between $f_t(d)$ and $f_t+1$ and solve this problem . As a hint it is given

max{$0.4f_{t+1}(d+b)+0.6f_{t+1}(d−b)$} Can someone please show me a way to do this problem using the hint.

## 1 Answer

It seems more like backward induction than dynamic programming to me.

In the last game, the gambler will bet $0$ dollars if he has at least $6$, winning with probability $1$, will bet $6-d$ if he has $3\le d\lt 6$, winning with probability $0.4$, and will give up and win with probability $0$ if he has less than $3$. So we know the value of the game before the last bet:

$$f_4(d)=\begin{cases} 1&d\ge6\;,\\ 0.4&3\le d\lt 6\;,\\ 0&d\lt 3\;. \end{cases}$$

Now we can analyze the third bet. Again, for $d\ge6$ we have $f_3(d)=1$. For $4.5\le d\lt 6$ the gambler will bet $6-x$, winning with probability $0.4$ and getting another $0.4$ chance with probability $0.6$, for a total of $0.4+0.6\cdot 0.4=0.64$. For $3\le d\lt 4.5$ we can try to get to $6$ in one go by immediately betting $6-d$, which gives us a $0.4$ probability of winning, and we can't do any better by betting less since we'd then still have to win in the last round, so the value in this range is $0.4$. For $1.5\le d\lt3$ we try to double twice, for a chance of $0.4^2=0.16$, and for $d\lt1.5$ we give up. So to summarize,

$$f_3(d)=\begin{cases} 1&d\ge6\;,\\ 0.64&4.5\le d\lt 6\;,\\ 0.4&3\le d\lt 4.5\;,\\ 0.16&1.5\le d\lt 3\;,\\ 0&d\lt 1.5\;. \end{cases}$$

You can go on like this to deduce the rest of the strategy. There will be some slightly less trivial decisions, but you can always make them by comparing the expected values, using the known game values of the next stage.

Edit in response to the comment: Your definition of $f_t(d)$ isn't very clearly formulated ($t$ doesn't occur in the sentence introducing $f_t(d)$), but since in the next sentence you write "$d$ is the amount that he has at the beginning of game $t$", I figured that $f_t(d)$ is meant to be the probability that the gambler will win (i.e. will have at least $6$ dollars after the fourth game) given that he has $d$ dollars before game $t$. Now, the way I understand your hint is that you can calculate $f_t(d)$ from $f_{t+1}$ as

$$f_t(d)=\max_{0\le b\le d}\left(0.4f_{t+1}(d+b)+0.6f_{t+1}(d−b)\right)\;,$$

that is, knowing the probabilities for stage $t+1$ you can perform backward induction for stage $t$ by maximizing the winning probability over all possible bets. Now the way you've defined $f_t(d)$, it's literally only defined for $t=1,\ldots,4$, because there are $4$ games. But "before game $t$" was just some language you used to refer to a point in time, and you can extend that to let $t=5$ refer to the time after the fourth game. At that time, the probabilities are particularly simple, since at that time the outcome is decided: For $d\ge6$ you win (with probability $1$), and for $d\lt6$ you lose (i.e. you win with probability $0$). So the initial values for the recursion can be taken to be

$$f_5(d)=\begin{cases}1&d\ge6\;,\\0&d\lt6\;.\end{cases}$$

• In $f_4(d)$ why shouldn't he bet when $d<3$? Can this be done by max{$0.4f_{t+1}(d+b)+0.6f_{t+1}(d-b)$} – clarkson Jul 23 '15 at 10:56
• @clarkson: It doesn't matter whether he bets. It's the last bet, and he won't get to $6$ dollars by betting his $d\lt3$ dollars. The value of the game at this point is $0$. And yes, it can be done that way (where the maximum is taken over all admissible bets $b$, and you need to define $f_5(d)=1$ for $d\ge6$ and $f_5(d)=0$ for $d\lt6$). – joriki Jul 23 '15 at 10:58
• Can you please explain why $f_5(d)=1$? Can there be $f_5$ as there is only 4 games? Also in $0.4f_{t+1}(d+b)+0.6f_{t+1}(d-b)$ how can I compute $f_4(d)$. Can you please explain how it can be done $0.4f_{t+1}(d+b)+0.6f_{t+1}(d-b)$ in this way as it is a hint given in the question – clarkson Jul 23 '15 at 12:17
• @clarkson: I added a bit to the answer in response to your comment -- I hope that clears things up a bit? – joriki Jul 24 '15 at 16:13
• @clarkson: I'm not sure I understand what you mean by "what happens when he doesn't bet a game". It sounds a bit as if you're interpreting $f_t(d)$ to describe any possible move in the game. It doesn't; it's the win probability under optimal play. Since betting $0$ when you only have $2$ is clearly not optimal play, $f_t(d)$ contains no information about what happens if you do it anyway. There's no such thing as "$f_1(2)$ when $b=0$". $b$ is a variable that's being maximized over, and the value $b=0$ in this case is not the one that yields the maximum; hence it doesn't determine the result. – joriki Jul 24 '15 at 22:33