論文の概要: Optimal No-Regret Learning for Repeated Prophet Inequality

• arxiv url: http://arxiv.org/abs/2609.23265v1
• Date: Sun, 20 Sep 2026 00:50:02 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-22 20:29:00.741779
• Title: Optimal No-Regret Learning for Repeated Prophet Inequality
• Title（参考訳）: 反復的預言不等式に対する最適非線形学習法
• Abstract要約: 提案手法は, 対数的因子に一致して, 期待される後悔の度合いを$widetilde O(sqrtT)$で達成するアルゴリズムである。
• 参考スコア（独自算出の注目度）: 3.2669518901121672
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study repeated prophet inequalities under prefix feedback. In each of $T$ rounds, a learner encounters fresh values drawn independently from $n$ boxes with unknown $[0,1]$-supported distributions in a fixed order and must irrevocably accept one, observing only the prefix up to its stopping box. Regret is measured against the optimal stopping policy that knows the distributions. We give an efficient algorithm achieving $\widetilde O(\sqrt{T})$ expected regret, matching the lower bound up to logarithmic factors. Our algorithm explores directly through near-optimal policies, combining empirical backward induction with box-specific reach bonuses. A relative-drop aggregation rule then exploits the nesting structure of observed prefixes to preserve exploration, thereby removing the polynomial dependence on the box number $n$. This resolves an open question posed by Liu et al. (2025).
• Abstract（参考訳）: プレフィックスフィードバックによる反復的預言不平等について検討した。 各$T$ラウンドでは、学習者は未知の$[0,1]$サポートされた分布を持つ$n$ボックスから独立して引き出された新鮮な値に遭遇する。 レグレトは、分布を知る最適な停止ポリシーに対して測定される。 我々は, 対数的因子に一致して, $\widetilde O(\sqrt{T})$ expected regret を達成するアルゴリズムを提案する。 本アルゴリズムは,経験的後進誘導とボックス固有のリーチボーナスを組み合わせることで,最適に近いポリシーを直接探索する。 相対ドロップアグリゲーションルールは、観測された接頭辞のネスト構造を利用して探索を保存し、ボックス番号$n$の多項式依存を除去する。 これは、Lou et al (2025) によって提起された開問題を解決する。

関連論文リスト

• A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
  我々は、要素が時間とともに到着する際のソリューションの品質と安定性のトレードオフについて研究する。 我々のアルゴリズムは,有理オラクル$を$O(varepsilon-1)$recourseで実装し,そのアルゴリズムから普遍価格証明書の存在を分離する。
  論文  参考訳（メタデータ） (2026-09-09T10:13:43Z)
• The Sample Complexity of Multiclass and Sparse Contextual Bandits [106.74652380822778]
  我々は,包括的フィードバックに基づいて,与えられたクラスからほぼ最適なポリシーを特定することを目的とする。 ゼロ・ワンの報酬を伴うバンド型マルチクラス分類に動機付けられ、emph$s$-sparse設定に焦点をあてる。 我々は、$s$-sparseの報酬で、誘導モデルクラスは、$s$でスケールするシャープなDEC境界を認め、直接最適なレートを得ることを示す。
  論文  参考訳（メタデータ） (2026-05-28T09:12:20Z)
• Online Set Learning from Precision and Recall Feedback [60.00180898830079]
  オンライン設定でドメインの未知のサブセットである$N_texttarget$を学習する問題を考察する。 この単純なオンラインセット学習問題は、精度とリコール型のフィードバックで様々な学習シナリオを抽象化する。 この設定で仮説クラスが学習可能であることを示し、それが有限のヴァプニク・チェルヴォネンキス次元を持つ場合に限る。
  論文  参考訳（メタデータ） (2026-05-10T14:28:05Z)
• A Fully Polynomial-Time Algorithm for Robustly Learning Halfspaces over the Hypercube [26.777025730534756]
  ハイパーキューブ上の一様分布に関して、ハーフスペースを学習するための最初のフルタイムアルゴリズムを与える。 誤り保証は$etaO(1)+epsilon$で、$eta$はノイズレートです。 より一般的に、我々のフレームワークは、個別分布に関する教師あり学習が以前考えられていたほど難しくないことを示している。
  論文  参考訳（メタデータ） (2025-11-10T15:58:41Z)
• Improved Regret and Contextual Linear Extension for Pandora's Box and Prophet Inequality [40.41746954717661]
  PandoraのBox問題を半帯域フィードバックによるオンライン学習環境で研究する。 各ラウンドでは、学習者は、未知の報酬分布を持つ最大$n$ボックスを開くために順次支払いを行う。 我々は,$T$ラウンド後に$widetildeO(sqrtT)$ regretを達成する新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-05-24T18:55:22Z)
• p-Mean Regret for Stochastic Bandits [52.828710025519996]
  単純で統一された UCB ベースのアルゴリズムを導入し、新しい$p$-mean の後悔境界を実現する。 我々の枠組みは、特別な場合として、平均的な累積的後悔とナッシュ後悔の両方を包含する。
  論文  参考訳（メタデータ） (2024-12-14T08:38:26Z)
• Learning to Cover: Online Learning and Optimization with Irreversible Decisions [50.5775508521174]
  我々は,個別かつ不可逆な意思決定を対象とするオンライン学習と最適化の問題を定義した。 各期間において、意思決定者は、オープンする施設を選択し、それぞれの成功に関する情報を受け取り、将来の決定を導くために分類モデルを更新する。 目的は,多数の施設を対象とする地平線を特徴とし,カバー対象を反映するチャンス制約の下で施設開口を最小化することである。
  論文  参考訳（メタデータ） (2024-06-20T23:00:25Z)
• Bandit Algorithms for Prophet Inequality and Pandora's Box [13.709418181148148]
  マルチアーメッド・バンディットモデルにおける預言不等式とPandoraのボックス問題について検討した。 我々の結果は、予言の不平等とPandoraのBoxの両面で、ほぼ最適の$tildeO(mathsfpoly(n)sqrtT)$トータル後悔アルゴリズムを提供する。
  論文  参考訳（メタデータ） (2022-11-16T00:10:35Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)

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

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