New bounds for Robbins' problem via exact policy improvement and martingale duality

Robbins' problem asks for the minimal expected rank V of an observation selected by a non-anticipating stopping rule from a sequence of i.i.d. uniform random variables, in the limit of a long sequence. The value is unknown; the best published bounds were 1.908 ≤ V ≤ 2.32614 (Bruss and Ferguson 1993; Meier and Sögner 2017). Working in Gnedin's planar Poisson model, we observe that the continuation cost of any memoryless threshold rule is an additive function of the past observations, with an explicit kernel. This makes one step of policy improvement over the optimal memoryless rule exactly computable. The improved rule uses the full history and has expected rank 2.30705 ± 0.00016 (Monte Carlo), and a non-asymptotic confidence bound gives V ≤ 2.3088 with confidence 1 − 10⁻³. A simple explicit rule, a memoryless threshold lowered linearly in the relative rank, already gives 2.3178 ± 0.0005. The same construction for finite n improves on recent MDP-based values for 10 ≤ n ≤ 500. The additive structure also yields an exactly computable martingale for the dual (information-relaxation) bound of optimal stopping. It pins down V_n to within 0.001 for n ≤ 100 and, with a betting confidence bound, gives V ≥ 2.2731 with confidence 1 − 10⁻³. This is a statistical certificate rather than a proof. Its probabilistic logic and hypotheses are formalized in Lean 4.