WEKO3
アイテム
The Last Success Problem with a Single Sample
https://ipsj.ixsq.nii.ac.jp/records/228925
https://ipsj.ixsq.nii.ac.jp/records/228925e68d141f-6e75-4a72-8a75-baf966dd3820
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL23195005.pdf (891.2 kB)
2025年11月9日からダウンロード可能です。
|
Copyright (c) 2023 by the Information Processing Society of Japan
|
|
| 非会員：¥0, IPSJ:学会員：¥0, AL:会員：¥0, DLIB:会員：¥0 | ||
| Item type | SIG Technical Reports(1) | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2023-11-09 | |||||||||
| タイトル | ||||||||||
| タイトル | The Last Success Problem with a Single Sample | |||||||||
| タイトル | ||||||||||
| 言語 | en | |||||||||
| タイトル | The Last Success Problem with a Single Sample | |||||||||
| 言語 | ||||||||||
| 言語 | eng | |||||||||
| 資源タイプ | ||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||||
| 資源タイプ | technical report | |||||||||
| 著者所属 | ||||||||||
| The University of Tokyo | ||||||||||
| 著者所属 | ||||||||||
| The University of Tokyo | ||||||||||
| 著者所属(英) | ||||||||||
| en | ||||||||||
| The University of Tokyo | ||||||||||
| 著者所属(英) | ||||||||||
| en | ||||||||||
| The University of Tokyo | ||||||||||
| 著者名 |
Toru, Yoshinaga
× Toru, Yoshinaga
× Yasushi, Kawase
|
|||||||||
| 著者名(英) |
Toru, Yoshinaga
× Toru, Yoshinaga
× Yasushi, Kawase
|
|||||||||
| 論文抄録 | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | 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 n Bernoulli trials. In this paper, we investigate a variant of the last success problem where we have single-sample access from each distribution instead of having comprehensive knowledge of the distributions. Nuti and Vondrak demonstrated that a winning probability exceeding 1/4 is unachievable for this setting, but it remains unknown whether a stopping policy that meets this bound exists. We reveal that Bruss's policy, when applied with the estimated success probabilities, cannot ensure a winning probability greater than (1-e-4)/4, irrespective of the estimations from the given samples. Nevertheless, we demonstrate that by setting the threshold the second-to-last success in samples and stopping on the first success observed after this threshold, a winning probability of 1/4 can be guaranteed. | |||||||||
| 論文抄録(英) | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | 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 n Bernoulli trials. In this paper, we investigate a variant of the last success problem where we have single-sample access from each distribution instead of having comprehensive knowledge of the distributions. Nuti and Vondrak demonstrated that a winning probability exceeding 1/4 is unachievable for this setting, but it remains unknown whether a stopping policy that meets this bound exists. We reveal that Bruss's policy, when applied with the estimated success probabilities, cannot ensure a winning probability greater than (1-e-4)/4, irrespective of the estimations from the given samples. Nevertheless, we demonstrate that by setting the threshold the second-to-last success in samples and stopping on the first success observed after this threshold, a winning probability of 1/4 can be guaranteed. | |||||||||
| 書誌レコードID | ||||||||||
| 収録物識別子タイプ | NCID | |||||||||
| 収録物識別子 | AN1009593X | |||||||||
| 書誌情報 |
研究報告アルゴリズム（AL） 巻 2023-AL-195, 号 5, p. 1-1, 発行日 2023-11-09 |
|||||||||
| ISSN | ||||||||||
| 収録物識別子タイプ | ISSN | |||||||||
| 収録物識別子 | 2188-8566 | |||||||||
| Notice | ||||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||||
| 出版者 | ||||||||||
| 言語 | ja | |||||||||
| 出版者 | 情報処理学会 | |||||||||
