Optimal Stopping for Maximum of Uniforms

Worked Solution

How to Think About It: This is a classic sequential decision problem. At each step you see a draw and must decide: take it or gamble that something better comes along. The key insight is that your decision should only depend on the current value $X_t$ and how many observations remain -- the past draws (which you already rejected) are irrelevant. This immediately suggests a threshold structure: for each time step, there is a cutoff below which you should keep looking and above which you should stop. The threshold should decrease as you run out of observations, because the option to continue becomes less valuable.

Quick Estimate: With $n$ observations, the expected payoff of the naive strategy (just take the last one) is $1/2$. The optimal strategy must do better. For $n = 2$: you stop at $X_1$ if $X_1 \geq c_1$, otherwise take $X_2$. By symmetry and a quick calculation (below), $c_1 = 1/2$ and the expected payoff is $3/4$. For large $n$, the optimal expected payoff grows roughly like $1 - 1/n$ (you are very likely to see something close to 1 among $n$ uniform draws, and the threshold policy captures most of that).

Approach: Define the value function by backward induction, then show the optimal policy is a threshold rule by examining the structure of the continuation value.

Formal Solution:

*Part 1: Threshold structure*

Let $V_t$ denote the expected payoff under the optimal policy when you are at step $t$ and have not yet stopped. Define $V_{n+1} = 0$ (if you somehow pass all observations, you get nothing -- but in practice you are forced to take $X_n$).

At step $n$ (the last observation), you must take $X_n$, so: $$V_n = E[X_n] = \frac{1}{2}$$

But more precisely, $V_n$ is the expected payoff *before* seeing $X_n$. The decision at step $t < n$ is: stop and receive $X_t$, or continue and receive expected payoff $V_{t+1}$. The optimal action is: $$\text{Stop at } t \iff X_t \geq V_{t+1}$$

This is a threshold rule with $c_t = V_{t+1}$ -- you stop whenever the current draw exceeds the value of continuing. The threshold structure follows because $V_{t+1}$ is a constant (it does not depend on $X_t$ or any past observations), so the comparison $X_t \geq V_{t+1}$ is simply checking whether the current observation exceeds a fixed cutoff.

*Part 2: Recursion for the thresholds*

At step $t$, under the optimal policy you stop if $X_t \geq c_t = V_{t+1}$ and continue otherwise. The expected payoff at step $t$ is: $$V_t = E[\max(X_t, V_{t+1})]$$

Since $X_t \sim \text{Unif}(0,1)$: $$V_t = \int_0^{V_{t+1}} V_{t+1} \, dx + \int_{V_{t+1}}^{1} x \, dx$$ $$= V_{t+1} \cdot V_{t+1} + \left[\frac{x^2}{2}\right]_{V_{t+1}}^{1}$$ $$= V_{t+1}^2 + \frac{1}{2} - \frac{V_{t+1}^2}{2}$$ $$= \frac{1}{2}(1 + V_{t+1}^2)$$

So the recursion is: $$\boxed{V_t = \frac{1 + V_{t+1}^2}{2}}$$

with the threshold at step $t$ being $c_t = V_{t+1}$.

*Computing $c_n$ and $c_{n-1}$:*

At step $n$, you are forced to take $X_n$, so $c_n = 0$ (you always stop -- equivalently, the continuation value after step $n$ is 0, and any non-negative draw beats it). More usefully: $$V_n = \frac{1}{2}$$

Thus $c_{n-1} = V_n = \frac{1}{2}$. At step $n-1$, you stop if $X_{n-1} \geq 1/2$.

For completeness: $$V_{n-1} = \frac{1 + (1/2)^2}{2} = \frac{1 + 1/4}{2} = \frac{5}{8}$$

So $c_{n-2} = 5/8$, confirming the thresholds are increasing as we move earlier in the sequence (you are pickier when you have more chances remaining).

Answer: The optimal policy is a threshold rule: stop at step $t$ if $X_t \geq c_t$, where $c_t = V_{t+1}$ and the value function satisfies $V_t = (1 + V_{t+1}^2)/2$ with $V_n = 1/2$. Explicitly, $c_n = 0$ (always take the last draw) and $c_{n-1} = 1/2$.