Stopping on the last success with unknown odds: asymptotic minimax optimality of the plug-in rule

Abstract

We study the last-success problem for sequential Bernoulli trials in the homogeneous setting where $X_1,\dots ,X_n$ are i.i.d. $\mathrm{Bernoulli}(p)$ but the success probability $p\in (0,1)$ is unknown to the decision maker. When $p$ is known, Bruss' sum-the-odds theorem yields an optimal threshold rule with win probability $V_n(p)$; when it is not, the odds driving this threshold must be learned from the very sequence on which one is trying to stop, which turns the problem into a genuinely statistical decision problem over the class of $p$-blind rules---those depending on the data but not on $p$. Writing $W_n^{\pi }(p)$ for the win probability of such a rule, we show that, for any $p_0\in (0,\frac{1}{2})$, $$\underset{n\to \infty }{\lim }\sqrt{n}\underset{\pi }{\inf }\underset{p\in [p_0,1)}{\sup }(V_n(p)-W_n^{\pi }(p))=C_{\star },$$ with $C_{\star }:=\frac{1}{2}{\sup }_{u>0}u\Phi (-u)\approx 0.085$ (here, $\Phi$ is the standard normal distribution function), and that this exact constant is attained by the natural plug-in odds rule, which is therefore asymptotically minimax optimal. The result is in fact local: at every transition point $1/k$ of the oracle threshold, the deficit admits an exact local minimax constant proportional to ${\gamma }_k=\frac{1}{\sqrt{k}}(1-\frac{1}{k}{)}^{k-3/2}$, and $C_{\star }$ is the largest of these, attained at $k=2$. We further quantify the cost of the natural sample-splitting alternative, show that the plug-in rule is asymptotically oracle-optimal in the sparse regime $p=p_n\to 0$ with $n{p}_n\to \infty$, and prove that no $p$-blind sequence of rules, even randomized, can converge to the oracle uniformly over $p\in (0,1)$, the obstruction being located in the critical window where $p$ is of order $1/n$.

67 pages, 4 figures