DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2024.105

The Last Success Problem with Samples

Authors: Toru Yoshinaga and Yasushi Kawase

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract

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-ε.

Cite as

Toru Yoshinaga and Yasushi Kawase. The Last Success Problem with Samples. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 105:1-105:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{yoshinaga_et_al:LIPIcs.ESA.2024.105,
  author =	{Yoshinaga, Toru and Kawase, Yasushi},
  title =	{{The Last Success Problem with Samples}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{105:1--105:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.105},
  URN =		{urn:nbn:de:0030-drops-211762},
  doi =		{10.4230/LIPIcs.ESA.2024.105},
  annote =	{Keywords: The Last Success Problem, Secretary Problem, Sample Information Model, Optimal Stopping, Online Algorithms}
}

Search Results

Documents authored by Yoshinaga, Toru

The Last Success Problem with Samples

Abstract

Cite as

Thanks for your feedback!

Could not send message