Dice Game with 1 die and Payoff Function

Question

Imagine a dice game where you may repeatedly roll a die until you either decide to stop, or roll a 1, with the following payoff function (where k is the number on the die),

$f(k) = 0$ when $k=1$

$f(k) = k^2$ when $k>1$

So if on your nth roll you land $1$, you go home with nothing. If on your $n$th roll you land a $4$, you get $16$ USD, and can either decide to roll again or go home with the $16$ USD.

My question: how should I set up the optimal stopping problem, after I have written down the transition matrix (making this into a Markov Process with each state space corresponding to the number I land)? Any hints would be appreciated, thank you

Answer 1

Suppose you have rolled a $4$, which gives a payout of $16$, should you roll again? The probability of getting a $j \in \{4,5,6\}$ later in the game is rolling $n$ times a $2$ or $3$ and then a $j$ for any $n \in \mathbb{N}$, which gives $$\mathbb{P}(\textrm{getting a }j)=\sum_{n=0}^\infty \frac{1}{3^n} \frac{1}{6}= \frac{1}{6} \frac{3}{2} = \frac{1}{4}.$$ So you have a $\frac{1}{4}$ chance of getting a lower payoff, and a $\frac{3}{4}$ chance of getting a better or equal payoff, which gives a payoff of $$ \frac{1}{4} ( 16+25+36) = \frac{77}{4} > 16.$$ So it seems like you should continue rolling.
If you get a $5$, at the same way you get by continuing to roll an average payoff of $$ \frac{1}{3}(25+36) = \frac{61}{3} < 25.$$ So if you get a $5$, you should stop.

Thus the optimal strategy is to keep rolling till you have at least rolled a $5$, and then stop.

Answer 2

Obviously, if you roll a $6$ at any time, you should stop, with value $\$36$.

If you roll a $5$, you can either stop (with value $\$25$), or continue until you roll either a $1$ or a $6$ (both equally likely). If you terminate on a $1$ (with probability $1/2$), you win nothing; if you terminate on a $6$ (with probability $1/2$), you win $\$36$. The value of continuing is therefore $36/2 = \$18$. Since this is less than $\$25$, you should stop on a $5$.

If you roll a $4$, you can either stop (with value $\$16$), or continue until you roll a $1$, a $5$, or a $6$ (all equally likely). The value of continuing, reasoning analogously with the previous paragraph, is $25/3+36/3 = \$20.33+$. Since this is greater than $16$, you should continue on a $4$.

Similar reasoning shows that you should continue on a $2$ or a $3$, also. (It may be of interest to note that the value of rolling a $4$ should be counted as $61/3$, not $16$, though it does not affect the decision.)