Section 22.1

Stop or Roll Again?

Dynamic stopping in dice and card games: rerolls at a cost, accumulate-or-bust (Pig), drawing while the colour balance is favourable, betting on the next card.

Toolkit

Optimal stopping over a finite or random horizon reduces to backward induction: compute the value of stopping now versus the expected value of continuing optimally, and stop exactly when the former dominates. Key tools:

Backward induction with $n$ actions left: $V_n = \mathbb{E}[\max(X, V_{n-1})]$ , $V_0 = 0$ (or the terminal payoff).
Stationary threshold $k$ for i.i.d. rewards: solve
$v = \mathbb{P}(\text{reroll})\,(v - c) + \mathbb{E}[X \mid X \ge k]\,\mathbb{P}(X\ge k),$
then optimise $v$ over $k$ .
One-step lookahead (monotone case): stopping is optimal once the one-step gain no longer exceeds the one-step risk; in such monotone problems the myopic rule is globally optimal.
Exchangeability: if the relevant indicator (e.g. colour of the next card) is exchangeable with a fixed future card, every stopping rule gives the same win probability.
For accumulating processes, track the full state (sum so far, remaining composition) and compare its continuation value to stopping.

Problems