論文の概要: Learning in Prophet Inequalities with Noisy Observations

• arxiv url: http://arxiv.org/abs/2604.01789v1
• Date: Thu, 02 Apr 2026 08:55:56 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-03 14:21:10.626999
• Title: Learning in Prophet Inequalities with Noisy Observations
• Title（参考訳）: 雑音観測による預言不平等の学習
• Authors: Jung-hun Kim, Vianney Perchet,
• Abstract要約: オンライン意思決定と最適停止における基本的な問題である預言不平等について検討する。 我々は,低信頼度しきい値を用いた学習と意思決定を統合するアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 38.27113852163736
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the prophet inequality, a fundamental problem in online decision-making and optimal stopping, in a practical setting where rewards are observed only through noisy realizations and reward distributions are unknown. At each stage, the decision-maker receives a noisy reward whose true value follows a linear model with an unknown latent parameter, and observes a feature vector drawn from a distribution. To address this challenge, we propose algorithms that integrate learning and decision-making via lower-confidence-bound (LCB) thresholding. In the i.i.d.\ setting, we establish that both an Explore-then-Decide strategy and an $\varepsilon$-Greedy variant achieve the sharp competitive ratio of $1 - 1/e$, under a mild condition on the optimal value. For non-identical distributions, we show that a competitive ratio of $1/2$ can be guaranteed against a relaxed benchmark. Moreover, with limited window access to past rewards, the tight ratio of $1/2$ against the optimal benchmark is achieved.
• Abstract（参考訳）: 本稿では,オンライン意思決定と最適停止の基本的な問題である預言不等式について,雑音の認識と報酬分布が未知の現実的な環境で考察する。 各段階において、決定者は、真値が未知の潜在パラメータを持つ線形モデルに従うノイズの多い報酬を受け取り、分布から引き出された特徴ベクトルを観測する。 この課題に対処するために,低信頼度閾値(LCB)による学習と意思決定を統合するアルゴリズムを提案する。 i.d.\ 設定では、探索-then-Decide 戦略と$\varepsilon$-Greedy 変種の両方が、最適な値の穏やかな条件の下で、1-1/e$の急激な競合比を達成することを証明している。 非恒等分布の場合、緩和されたベンチマークに対して1/2$の競合比を保証できることが示される。 さらに、過去の報酬に対するウィンドウアクセスが制限された場合、最適なベンチマークに対して1/2ドルの厳密な比率が達成される。

関連論文リスト

• Robust and Consistent Ski Rental with Distributional Advice [13.811651343801579]
  スキーレンタル問題は不確実性の下でのオンライン意思決定の標準モデルである。 本稿では,未知品質の分布的アドバイスを決定論的アルゴリズムとランダム化アルゴリズムの両方に統合するフレームワークを提案する。 我々のフレームワークは、既存の点予測ベースラインよりも一貫性を著しく向上し、かつ、同等の堅牢性を維持していることを示す。
  論文  参考訳（メタデータ） (2026-03-31T04:04:21Z)
• Active Bipartite Ranking with Smooth Posterior Distributions [1.9838140219494644]
  双部格付けは、多くのアプリケーションにかかわる統計的学習問題であり、受動的文脈において広く研究されている。 本研究では,推定ランキングルールのROC曲線と$sup$ノルムの最適値との距離を最小化することを目的とした,スムーズランクと呼ばれる新しいアルゴリズムを提案する。 本研究では,スムーズランクのサンプリング時間に依存する問題と,任意のPAC$(,)$アルゴリズムのサンプリング時間に依存する問題を確立する。
  論文  参考訳（メタデータ） (2026-02-27T18:32:08Z)
• Optimistic Feasible Search for Closed-Loop Fair Threshold Decision-Making [0.0]
  バンディットフィードバックからの1次元しきい値ポリシーのオンライン学習について検討する。 我々は,報酬と制約残差に対する信頼境界を維持する単純なグリッドベース手法であるOptimistic Feasible Search (OFS)を提案する。
  論文  参考訳（メタデータ） (2025-12-26T10:44:40Z)
• Regret Minimization and Statistical Inference in Online Decision Making with High-dimensional Covariates [7.21848268647674]
  我々は、決定のための$varepsilon$-greedybanditアルゴリズムと、疎帯域パラメータを推定するためのハードしきい値アルゴリズムを統合する。 マージン条件下では、我々の手法は、$O(T1/2)$ regret あるいは古典的な$O(T1/2)$-consistent推論のいずれかを達成する。
  論文  参考訳（メタデータ） (2024-11-10T01:47:11Z)
• Beyond Expectations: Learning with Stochastic Dominance Made Practical [88.06211893690964]
  支配は、不確実な結果で意思決定を行うためのリスク-逆の選好をモデル化する。 理論上は魅力的だが、機械学習における優位性の応用は乏しい。 まず支配の概念を一般化し、任意の確率変数の任意のペア間の比較を可能にする。 次に、優位性の観点から最適解を見つけるための単純で効率的なアプローチを開発する。
  論文  参考訳（メタデータ） (2024-02-05T03:21:23Z)
• A Minimaximalist Approach to Reinforcement Learning from Human Feedback [49.45285664482369]
  人間のフィードバックから強化学習を行うアルゴリズムとして,SPO(Self-Play Preference Optimization)を提案する。 我々のアプローチは、報酬モデルや不安定な敵の訓練を必要としないという点で最小主義である。 我々は,一連の継続的制御タスクにおいて,報酬モデルに基づくアプローチよりもはるかに効率的に学習できることを実証した。
  論文  参考訳（メタデータ） (2024-01-08T17:55:02Z)
• Online Learning with Knapsacks: the Best of Both Worlds [54.28273783164608]
  オンライン学習の課題として,意思決定者が,リソース制約の有限セットに違反することなく,期待する報酬を最大化したい,という課題を提起する。 当社のフレームワークは,意思決定者がそのエビデンスを柔軟かつコスト論的に扱えるようにします。
  論文  参考訳（メタデータ） (2022-02-28T12:10:48Z)
• Top $K$ Ranking for Multi-Armed Bandit with Noisy Evaluations [102.32996053572144]
  我々は,各ラウンドの開始時に,学習者が各アームの真の報酬について,ノイズのない独立した評価を受けるマルチアームバンディット・セッティングを考える。 評価の方法によって異なるアルゴリズムアプローチと理論的保証を導出する。
  論文  参考訳（メタデータ） (2021-12-13T09:48:54Z)

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

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