Optimal Stopping — Mathematics Knowledge System

Overview

Optimal stopping is the problem of choosing a stopping time T to maximize (or minimize) an expected reward E[G(X_T)], where G is a payoff function and X is a stochastic process. It underlies option pricing (when to exercise an American option), the secretary problem, sequential testing, and real options analysis. The solution is characterized by the Snell envelope (smallest supermartingale dominating the payoff process) and, in Markov settings, by a variational inequality.

Intuition

You observe a sequence of offers and must decide when to stop and accept. Stop too early and you miss better offers; stop too late and you lose opportunity. The key insight: the optimal strategy is a threshold rule -- stop when the current value exceeds the expected future value of waiting. The 'Snell envelope' is the value process of the optimal strategy, and the optimal stopping time is when the payoff process touches the Snell envelope.

Formal Definition

Definition

Given a filtered probability space and adapted payoff process {G_n}, the Snell envelope U_n is defined as U_n = ess sup_{T >= n, T stopping time} E[G_T | F_n]. The optimal stopping time is T* = inf{n : U_n = G_n}. The Snell envelope is the smallest supermartingale dominating G.

U_n = \operatorname*{ess\,sup}_{T \ge n} \mathbb{E}[G_T \mid \mathcal{F}_n]

Snell envelope

T^* = \inf\{n \ge 0 : U_n = G_n\}

Optimal stopping time

U_n = \max(G_n,\, \mathbb{E}[U_{n+1} \mid \mathcal{F}_n]) \quad \text{(backward induction)}

Dynamic programming recursion

V(x) = \sup_{\tau} \mathbb{E}^x[G(X_\tau)], \quad V(x) \ge G(x)

Value function (Markov case)

Notation

Notation	Meaning
$U_n$	Snell envelope: value of optimal stopping from time n onward
$T^*$	Optimal stopping time: first time the payoff equals the Snell envelope
$V(x)$	Value function in Markov setting: expected payoff under optimal stopping from state x

Theorems

Theorem 1: Theorem 1 (Snell Envelope Characterization)

\text{The Snell envelope } \{U_n\} \text{ is the smallest supermartingale that dominates } \{G_n\}. \text{ The optimal stopping time is } T^* = \inf\{n : U_n = G_n\}, \text{ and } \mathbb{E}[G_{T^*}] = U_0.

Theorem 2: Theorem 2 (Secretary Problem / 1/e Rule)

\text{For the secretary problem with } n \text{ candidates, the optimal strategy is to observe and reject the first } r^* \approx n/e \text{ candidates, then accept the next candidate better than all seen so far. This succeeds with probability} \to 1/e \approx 0.368.

Worked Examples

1
Work backwards. At time 2 (last chance), you must stop, so U_2 = X_2 with E[U_2] = 1/2.
$\mathbb{E}[U_2] = \mathbb{E}[X_2] = \frac{1}{2}$
2
At time 1: stop if X_1 > E[U_2] = 1/2, otherwise continue. U_1 = max(X_1, 1/2).
$U_1 = \max\!\left(X_1, \frac{1}{2}\right)$
3
Optimal rule: stop at time 1 if X_1 > 1/2, else stop at time 2. Expected payoff: E[U_1] = E[max(X_1, 1/2)] = int_0^{1/2} (1/2) dx + int_{1/2}^1 x dx = 1/4 + (1 - 1/4)/2 = 1/4 + 3/8 = 5/8.
$\mathbb{E}[U_1] = \int_0^{1/2} \frac{1}{2}\,dx + \int_{1/2}^1 x\,dx = \frac{1}{4} + \left[\frac{x^2}{2}\right]_{1/2}^1 = \frac{1}{4} + \frac{1}{2} - \frac{1}{8} = \frac{5}{8}$

✓ Answer

Stop at time 1 if X_1 > 1/2, else stop at time 2. Expected payoff = 5/8.

Practice Problems

Mediumfree response

You observe X_1, X_2, X_3 i.i.d. Uniform[0,1] and receive X_T as reward. What is the optimal stopping rule and expected payoff for N = 3?

Hardfree response

Describe the connection between the Snell envelope and supermartingales. Why is T* = inf{n : U_n = G_n} optimal?

Common Mistakes

Common Mistake

Thinking you should always wait to collect more information

Optimal stopping balances information gain against opportunity cost. Waiting has value only if the expected improvement exceeds the cost of delay.

Common Mistake

Confusing the Snell envelope with the payoff process

U_n >= G_n always. U_n = G_n only at the optimal stopping time -- the Snell envelope is the value of optimal stopping, not the current payoff.

Quiz

Summary

Optimal stopping: choose T to maximize E[G(X_T)] over all stopping times T.
Snell envelope U_n = max(G_n, E[U_{n+1} | F_n]) via backward induction.
Optimal stopping time: T* = inf{n : U_n = G_n} (first time payoff equals continuation value).
Secretary problem: observe and reject first n/e candidates, then accept the next record.
American options: early exercise optimal when stock price enters the stopping region.

References

BookPeskir, G. and Shiryaev, A. -- Optimal Stopping and Free-Boundary Problems
BookShiryaev, A. -- Optimal Stopping Rules
WebsiteWikipedia -- Optimal stopping