2026-07-22T21:23:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21176 2024-09-23T09:13:18Z ddc:004 open_access

The Last Success Problem with Samples Yoshinaga, Toru Kawase, Yasushi The Last Success Problem Secretary Problem Sample Information Model Optimal Stopping Online Algorithms The last success problem is an optimal stopping problem that aims to maximize the probability of stopping on the last success in a sequence of independent n Bernoulli trials. In the classical setting where complete information about the distributions is available, Bruss [Bruss, 2000] provided an optimal stopping policy that ensures a winning probability of 1/e. However, assuming complete knowledge of the distributions is unrealistic in many practical applications. This paper investigates a variant of the last success problem where samples from each distribution are available instead of complete knowledge of them. When a single sample from each distribution is allowed, we provide a deterministic policy that guarantees a winning probability of 1/4. This is best possible by the upper bound provided by Nuti and Vondrák [Nuti and Vondr{á}k, 2023]. Furthermore, for any positive constant ε, we show that a constant number of samples from each distribution is sufficient to guarantee a winning probability of 1/e-ε. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Toru Yoshinaga and Yasushi Kawase 2024 Is Part Of LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2024.105 urn:nbn:de:0030-drops-211762 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.105 eng https://creativecommons.org/licenses/by/4.0/legalcode