Optimal Stopping: Three-Roll Dice Game
You are offered the following game: roll a fair six-sided die up to 3 times. After each roll, you decide -- stop and collect the face value in dollars, or roll again and forfeit what you just saw. If you roll a third time, you must accept whatever comes up.
What is the optimal stopping strategy, and what is the expected payout under that strategy?
Hints
- Start at the end: if you are on your last roll, you have no choice. What is the expected value of a forced final roll? That number is your threshold for deciding on the previous roll.
- On each earlier roll, you should stop if and only if the current face value exceeds the expected payout of continuing. This gives you a cutoff rule at each stage -- derive the cutoffs from last to first.
- For roll 2: the threshold is $3.5$, so accept 4, 5, 6 and re-roll on 1, 2, 3. Compute $E_2 = \frac{1}{6}(3.5 \times 3 + 4 + 5 + 6)$. Then use $E_2$ as the threshold for roll 1.
Worked Solution
How to Think About It: This is a textbook optimal stopping problem, and the key move is to work backwards. At the last roll you have no choice -- you take what you get. That gives you a concrete number (the expected value of a die roll) to use as the threshold on the second roll: only stop early if you beat the value of continuing. Repeat one step back. The intuition is that each earlier roll has option value -- you can always reject a bad outcome and keep going -- so thresholds rise as you get closer to the last roll and fall as you move earlier (since you have more rolls left to improve).
Quick gut check before any algebra: with 3 rolls you should be able to do meaningfully better than $3.50 (the no-choice baseline). With one extra roll, you can reject anything below 4, pushing the mean up to about $4.25. With two extra rolls, you can be even pickier on the first one. Expect something around $4.50-$4.75.
Quick Estimate: Work back from the last roll. - Roll 3 (forced): $E_3 = (1+2+3+4+5+6)/6 = 3.5$. - Roll 2 threshold: $3.5$. Accept 4, 5, or 6; otherwise re-roll. Rough average of accepted values: $(4+5+6)/3 = 5.0$. Accepted with prob $1/2$, re-roll with prob $1/2$ giving $3.5$. Estimate: $(1/2)(5.0) + (1/2)(3.5) = 4.25$. This is exact. - Roll 1 threshold: $4.25$. Accept 5 or 6; otherwise re-roll for $4.25$. Average of accepted values: $(5+6)/2 = 5.5$. Accepted with prob $1/3$. Estimate: $(1/3)(5.5) + (2/3)(4.25) \approx 1.83 + 2.83 = 4.67$. Ballpark confirmed.
Approach: Backward induction (dynamic programming). Define $E_k$ as the expected payout under the optimal strategy with $k$ rolls remaining. At each step, the threshold is $E_{k-1}$: stop if the current roll exceeds the continuation value, else keep rolling.
Formal Solution:
Roll 3 (last roll) -- no choice:
$$E_3 = \frac{1}{6}(1+2+3+4+5+6) = 3.5$$
Roll 2 -- stop if face value $\geq E_3 = 3.5$, i.e., stop on 4, 5, or 6:
$$E_2 = \frac{1}{6}\bigl(E_3 + E_3 + E_3 + 4 + 5 + 6\bigr) = \frac{1}{6}(3.5 + 3.5 + 3.5 + 4 + 5 + 6) = \frac{25.5}{6} = 4.25$$
The three low rolls (1, 2, 3) are each replaced by the continuation value $E_3 = 3.5$, while the three high rolls (4, 5, 6) are accepted at face value.
Roll 1 -- stop if face value $\geq E_2 = 4.25$, i.e., stop on 5 or 6:
$$E_1 = \frac{1}{6}\bigl(E_2 + E_2 + E_2 + E_2 + 5 + 6\bigr) = \frac{1}{6}(4 \times 4.25 + 11) = \frac{28}{6} = \frac{14}{3} \approx 4.67$$
The four low rolls (1, 2, 3, 4) are replaced by $E_2 = 4.25$; only 5 and 6 are accepted.
Optimal Strategy: - Roll 1: keep only 5 or 6. Otherwise roll again. - Roll 2: keep 4, 5, or 6. Otherwise roll again. - Roll 3: must accept whatever comes up.
Answer: The expected payout is $\dfrac{14}{3} \approx \$4.67$. The stopping thresholds are 5 on the first roll and 4 on the second.
Intuition
The core principle here is that options have value. At every stage before the last, you hold the option to reject a bad outcome and try again -- and that option is worth something. Because you can always fall back on the continuation value, your effective floor rises: on roll 2 you are guaranteed at least $3.50 in expectation, and on roll 1 you are guaranteed at least $4.25. That rising floor means your optimal threshold also rises as you move earlier: you become pickier on roll 1 (need 5 or 6) than on roll 2 (need 4 or better), precisely because you have more runway to find a good outcome.
This pattern -- backward induction with a threshold that tightens toward the final stage -- is everywhere in quant finance. Secretary problems, optimal trade execution (when to submit a large order vs. wait for a better price), and American option early exercise all share this structure. The key insight is always the same: compute the value of continuing, and stop only when the immediate payoff beats it. If you can internalize that framing, you can set up any finite-horizon stopping problem in seconds.