論文の概要: The Secretary Problem with Predictions and a Chosen Order

• arxiv url: http://arxiv.org/abs/2601.07482v1
• Date: Mon, 12 Jan 2026 12:34:49 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-13 19:08:01.38224
• Title: The Secretary Problem with Predictions and a Chosen Order
• Title（参考訳）: 予知問題と勅撰令
• Authors: Helia Karisani, Mohammadreza Daneshvaramoli, Hedyeh Beyhaghi, Mohammad Hajiesmaili, Cameron Musco,
• Abstract要約: 藤井と吉田が最近導入した秘書問題(2023年)の学習強化版について検討した。 予測が正確であれば、アルゴリズムは最適に近い秘書を選ぶべきであるが、不正確な予測の下では、有界競争比を保証すべきである。 我々は,従来のランダム秩序秘書問題(ROSP)において,候補が一様にランダムな順序で到着する問題と,意思決定者が予測値に基づいて到着順序を選択することができるようなより自然な学習強化モデルを考える。
• 参考スコア（独自算出の注目度）: 19.836223305384696
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study a learning-augmented variant of the secretary problem, recently introduced by Fujii and Yoshida (2023), in which the decision-maker has access to machine-learned predictions of candidate values. The central challenge is to balance consistency and robustness: when predictions are accurate, the algorithm should select a near-optimal secretary, while under inaccurate predictions it should still guarantee a bounded competitive ratio. We consider both the classical Random Order Secretary Problem (ROSP), where candidates arrive in a uniformly random order, and a more natural learning-augmented model in which the decision-maker may choose the arrival order based on predicted values. We call this model the Chosen Order Secretary Problem (COSP), capturing scenarios such as interview schedules set in advance. We propose a new randomized algorithm applicable to both ROSP and COSP. Our method switches from fully trusting predictions to a threshold-based rule once a large prediction deviation is detected. Let $ε\in [0,1]$ denote the maximum multiplicative prediction error. For ROSP, our algorithm achieves a competitive ratio of $\max\{0.221, (1-ε)/(1+ε)\}$, improving upon the prior bound of $\max\{0.215, (1-ε)/(1+ε)\}$. For COSP, we achieve $\max\{0.262, (1-ε)/(1+ε)\}$, surpassing the $0.25$ worst-case bound for prior approaches and moving closer to the classical secretary benchmark of $1/e \approx 0.368$. These results highlight the benefit of combining predictions with arrival-order control in online decision-making.
• Abstract（参考訳）: 藤井と吉田が最近導入した秘書問題(2023年)の学習強化版について検討した。 予測が正確であれば、アルゴリズムは最適に近い秘書を選ぶべきである。 我々は,従来のランダム秩序秘書問題(ROSP)において,候補が一様にランダムな順序で到着する問題と,意思決定者が予測値に基づいて到着順序を選択することができるようなより自然な学習強化モデルを考える。 我々はこのモデルをCOSP(Chosen Order Secretary Problem)と呼び、事前に設定されたインタビュースケジュールなどのシナリオをキャプチャする。 ROSPとCOSPの両方に適用可能な新しいランダム化アルゴリズムを提案する。 提案手法は,大規模な予測偏差を検出すると,完全に信頼された予測からしきい値に基づくルールに切り替わる。 ε\in [0,1]$ は最大乗算予測誤差を表す。 ROSP の場合、このアルゴリズムは、$\max\{0.221, (1-ε)/(1+ε)\}$ の競合比を達成し、以前の$\max\{0.215, (1-ε)/(1+ε)\}$ の制限値を改善する。 COSPでは、$\max\{0.262, (1-ε)/(1+ε)\}$を達成し、以前のアプローチの0.25$最悪のケースを越え、1/e \approx 0.368$の古典的秘書ベンチマークに近づいた。 これらの結果は、オンライン意思決定において、予測と到着順序制御を組み合わせる利点を浮き彫りにする。

関連論文リスト

• Learning-Augmented Online Bipartite Matching in the Random Arrival Order Model [0.688204255655161]
  ランダム到着順序モデルにおけるオンライン非重み付き二部マッチング問題について検討する。 我々の学習強化アルゴリズムは、1-o(1))$-consistencyと$(-o(1))$-robustnessを達成する。
  論文  参考訳（メタデータ） (2025-11-28T17:31:11Z)
• Fair Secretaries with Unfair Predictions [12.756552522270198]
  予測値が少なくとも$maxOmega (1), 1 - O(epsilon)$倍の候補を受け入れることを約束しているにもかかわらず、アルゴリズムが最良の候補を受け入れる確率がゼロであることを示し、ここでは$epsilon$が予測誤差である。 私たちのアルゴリズムと分析は、既存の作業から分岐し、結果のいくつかを単純化/統一する、新たな"ペギング(pegging)"アイデアに基づいている。
  論文  参考訳（メタデータ） (2024-11-15T00:23:59Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Streaming Algorithms for Learning with Experts: Deterministic Versus Robust [62.98860182111096]
  エキスパート問題を伴うオンライン学習では、アルゴリズムは、T$day(または時間)ごとに結果を予測する必要がある。 目標は最小限のコストで予測を行うことだ。 最良専門家が$M$の誤りを犯したとき、後悔する$R$を達成するような決定論的アルゴリズムに対して、$widetildeOmegaleft(fracnMRTright)$の空間下界を示す。
  論文  参考訳（メタデータ） (2023-03-03T04:39:53Z)
• 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)
• Learning-Augmented Algorithms for Online TSP on the Line [4.636538620253008]
  本研究では,オンライントラベリングセールスマン問題 (TSP) を,機械学習による予測を付加した線上で研究する。 古典的な問題では、実際の行に沿って時間をかけてリリースされるリクエストのストリームがあります。 オープンな変種とクローズドな変種を区別し、全ての要求を処理した後、アルゴリズムに元の値を返すように要求する。
  論文  参考訳（メタデータ） (2022-06-01T17:47:26Z)
• Online Optimization with Untrusted Predictions [7.895232155155041]
  本稿では, オンライン最適化の課題について検討し, 意思決定者は, ラウンドごと, 非競争的打撃コスト, ラウンド間切替コストの合計に対して, 一般的な計量空間内の点を選択する必要がある。 本稿では,新しいアルゴリズムであるAdaptive Online Switching (AOS)を提案し,予測が完全であれば$tildecalO(alphadelta)$が不正確であっても$tildecalO(alphadelta)$であることを示す。
  論文  参考訳（メタデータ） (2022-02-07T21:08:02Z)
• Double Coverage with Machine-Learned Advice [100.23487145400833]
  オンラインの基本的な$k$-serverの問題を学習強化環境で研究する。 我々のアルゴリズムは任意の k に対してほぼ最適の一貫性-破壊性トレードオフを達成することを示す。
  論文  参考訳（メタデータ） (2021-03-02T11:04:33Z)
• Learning with User-Level Privacy [61.62978104304273]
  ユーザレベルの差分プライバシー制約下での学習課題を,アルゴリズムを用いて解析する。 個々のサンプルのプライバシーのみを保証するのではなく、ユーザレベルのdpはユーザの貢献全体を保護します。 プライバシコストが$tau$に比例した$K$適応的に選択されたクエリのシーケンスにプライベートに答えるアルゴリズムを導き出し、私たちが検討する学習タスクを解決するためにそれを適用します。
  論文  参考訳（メタデータ） (2021-02-23T18:25:13Z)

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

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