論文の概要: The Secretary Problem with a Stochastic Precursor

• arxiv url: http://arxiv.org/abs/2605.22653v1
• Date: Thu, 21 May 2026 15:56:09 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-22 16:35:42.335736
• Title: The Secretary Problem with a Stochastic Precursor
• Title（参考訳）: 確率的前処理器による秘書問題
• Authors: Franziska Eberle, Alexander Lindermayr,
• Abstract要約: 本稿では,到着時刻のみから,予測が有用であることを示す。 我々は,前駆体を付加した基本秘書問題,すなわち,最良項目よりも遅く到着することが保証されるコンテンツフリー信号について検討する。 ランダムオーダーモデルと逆オーダーモデルにおいて最適ポリシーを特徴付ける。
• 参考スコア（独自算出の注目度）: 49.51793477594992
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In learning-augmented online algorithms, predictions are usually valued for what they say: a value estimate, a solution, or an algorithmic recommendation. This paper shows that predictions can also be valuable solely due to their arrival time. We study the fundamental secretary problem augmented with a stochastic precursor: a content-free signal that is guaranteed to arrive no later than the best item, but is otherwise stochastically timed. The signal does not carry any additional information; nevertheless, its timing alone changes the structure of optimal stopping. We characterize optimal policies in the random-order and adversarial-order models. In random order, a single uniformly timed precursor already gives success probability at least $\frac12$, improving on the classic $\frac1e$ benchmark. With increasingly late precursors, the success probability approaches $1$. In adversarial order, for which traditional models do not admit strong guarantees, sufficiently concentrated precursors recover constant success guarantees. Our results show that such novel forms of asynchronous temporal information are a distinct and powerful form of advice in online decision making and may also be effective for other problems.
• Abstract（参考訳）: 学習強化されたオンラインアルゴリズムでは、予測は通常、価値見積、ソリューション、アルゴリズムレコメンデーションなど、彼らの言うことに対して評価される。 本稿では,到着時刻のみから,予測が有用であることを示す。 我々は,確率的前駆体を付加した基本的な秘書問題,すなわち,最高の項目よりも遅く到着することが保証されるコンテンツフリー信号について検討する。 信号には追加情報はないが、そのタイミングだけで最適な停止構造が変化する。 ランダムオーダーモデルと逆オーダーモデルにおいて最適ポリシーを特徴付ける。 ランダム順序では、1つの一様時間前駆体が少なくとも$\frac12$を成功確率を与え、古典的な$\frac1e$ベンチマークを改善している。 成功の確率は、ますます遅い前駆者たちと近づきつつある。 従来のモデルが強い保証を認めていない敵順では、十分に集中した前駆体が一定の成功保証を回復する。 以上の結果から,このような非同期時間情報の新たな形態は,オンライン意思決定において一意かつ強力なアドバイスであり,他の問題にも有効である可能性が示唆された。

関連論文リスト

• Robust and Consistent Ski Rental with Distributional Advice [13.811651343801579]
  スキーレンタル問題は不確実性の下でのオンライン意思決定の標準モデルである。 本稿では,未知品質の分布的アドバイスを決定論的アルゴリズムとランダム化アルゴリズムの両方に統合するフレームワークを提案する。 我々のフレームワークは、既存の点予測ベースラインよりも一貫性を著しく向上し、かつ、同等の堅牢性を維持していることを示す。
  論文  参考訳（メタデータ） (2026-03-31T04:04:21Z)
• The Secretary Problem with Predictions and a Chosen Order [19.836223305384696]
  藤井と吉田が最近導入した秘書問題(2023年)の学習強化版について検討した。 予測が正確であれば、アルゴリズムは最適に近い秘書を選ぶべきであるが、不正確な予測の下では、有界競争比を保証すべきである。 我々は,従来のランダム秩序秘書問題(ROSP)において,候補が一様にランダムな順序で到着する問題と,意思決定者が予測値に基づいて到着順序を選択することができるようなより自然な学習強化モデルを考える。
  論文  参考訳（メタデータ） (2026-01-12T12:34:49Z)
• Stopping Rules for Stochastic Gradient Descent via Anytime-Valid Confidence Sequences [51.56484100374058]
  凸最適化のための勾配降下(SGD)の停止規則について検討した。 我々は、投影されたSGDの重み付き平均準最適度に対して、任意の有意、データ依存の高信頼シーケンスを開発する。 これらは、厳格でタイムユニフォームなパフォーマンス保証と、有限時間$varepsilon$-optimality証明書である。
  論文  参考訳（メタデータ） (2025-12-15T09:26:45Z)
• Fair Secretaries with Unfair Predictions [12.756552522270198]
  予測値が少なくとも$maxOmega (1), 1 - O(epsilon)$倍の候補を受け入れることを約束しているにもかかわらず、アルゴリズムが最良の候補を受け入れる確率がゼロであることを示し、ここでは$epsilon$が予測誤差である。 私たちのアルゴリズムと分析は、既存の作業から分岐し、結果のいくつかを単純化/統一する、新たな"ペギング(pegging)"アイデアに基づいている。
  論文  参考訳（メタデータ） (2024-11-15T00:23:59Z)
• Autoregressive Bandits [58.46584210388307]
  本稿では,オンライン学習環境であるAutoregressive Banditsを提案する。 報酬プロセスの軽微な仮定の下では、最適ポリシーを便利に計算できることが示される。 次に、新しい楽観的後悔最小化アルゴリズム、すなわちAutoRegressive Upper Confidence Bound (AR-UCB)を考案し、$widetildemathcalO left( frac(k+1)3/2sqrtnT (1-G)のサブ線形後悔を被る。
  論文  参考訳（メタデータ） (2022-12-12T21:37:36Z)
• Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discrimination [82.52105963476703]
  統計的学習、オンライン学習、その他における繰り返しのテーマは、低騒音の問題に対してより速い収束率が可能であることである。 1次保証は統計的およびオンライン学習において比較的よく理解されている。 三角識別と呼ばれる対数損失と情報理論量が一階保証を得る上で基本的な役割を担っていることを示す。
  論文  参考訳（メタデータ） (2021-07-05T19:20:34Z)
• Debiased Off-Policy Evaluation for Recommendation Systems [8.63711086812655]
  A/Bテストは信頼できるが、時間と費用がかかり、失敗のリスクが伴う。 提案手法は,履歴データに対するアルゴリズムの性能を推定する手法である。 提案手法は,最先端手法よりも平均2乗誤差が小さい。
  論文  参考訳（メタデータ） (2020-02-20T02:30:02Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。