Optimal Stopping

Compare the value of stopping now against the expected value of continuing to decide the optimal threshold strategy.

1. The idea

Optimal stopping problems ask when to stop a sequential process to maximize expected value. The key idea is the continuation value: the expected payoff from continuing optimally, computed independently of the current observation.

The optimal rule is a threshold: stop if the current value exceeds the continuation value, otherwise continue. Because the continuation value doesn't depend on the current draw, it can be computed first and then compared against each possible outcome.

With multiple stages (e.g., two allowed rerolls), work backward from the last stage: compute the continuation value for the final decision, then use that as the 'stopping payoff' for the decision one stage earlier.

2. Why it matters

Optimal stopping captures a recurring trading intuition — when to accept a price versus wait for a better one — and it's tested directly via reroll and secretary-style interview questions.

3. Core mathematics

Continuation value

c = E [payoff if you continue optimally]

Optimal rule

Stop if current value \geq c, else continue

Value of the game

V = E [max (X, c)]

4. How to recognize it

Think of this when…

You are allowed one or more chances to reroll, redraw, or resample
The question asks for the optimal strategy's expected value, not just a fixed rule's
Multiple stages suggest working backward from the last decision point

5. Worked example

Worked example

Roll a fair die once. You may choose to keep the result or reroll it exactly once (and must accept the second roll). What is the optimal strategy and its expected value?

1
The continuation value (expected value of rerolling) equals the mean of a fresh die: $c = 3.5$ .
$c = E [fresh roll] = 3.5$
2
Optimal rule: keep the first roll if it exceeds 3.5, i.e., keep on ${4, 5, 6}$ ; reroll on ${1, 2, 3}$ .
$keep if X \geq 4$
3
Compute the value: with probability $1/2$ you keep a value in ${4, 5, 6}$ (average $5$ ); with probability $1/2$ you reroll for an expected $3.5$ .
$V = \frac{1}{6} (4 + 5 + 6) + \frac{1}{6} (3.5 + 3.5 + 3.5)$
4
Simplify.
$V = \frac{15}{6} + \frac{10.5}{6} = \frac{25.5}{6} = 4.25$
Answer: Keep on 4, 5, or 6; reroll on 1, 2, or 3. Expected value $= 4.25$

6. Common mistakes

Computing the continuation value after conditioning on the current draw, which double counts information
Using a suboptimal fixed threshold instead of solving for the one that maximizes expected value
In multi-stage problems, forgetting to solve backward from the final decision
Mixing up 'keep if above threshold' with 'keep if below threshold' — check the direction against the payoff structure

7. Quick check

In the one-reroll die problem, what is the correct threshold for keeping the first roll?

8. Practice

7 QuantSolve questions use this concept.

Practice this concept

9. Related methods

Dynamic Programming / Continuation Value Recursive Expectation / First-Step Analysis

Create a free account to save lesson progress.