論文の概要: Asymptotically Optimal Learning for Parametric Prophet Inequalities

• arxiv url: http://arxiv.org/abs/2606.26893v1
• Date: Thu, 25 Jun 2026 11:26:16 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-26 18:46:32.256536
• Title: Asymptotically Optimal Learning for Parametric Prophet Inequalities
• Title（参考訳）: パラメトリック預言不等式に対する漸近的最適学習
• Abstract要約: 我々は指数型パラメトリック・ファミリーから引き出された報酬を未知のパラメータ$$.d.で予言の不等式で学習する。 まず、この家族の最適な全情報競合比を特徴付ける。 次に、オンライン学習のための信頼性に基づく動的プログラミングポリシーを提案する。
• 参考スコア（独自算出の注目度）: 34.052091679352316
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study learning in prophet inequalities with i.i.d. rewards drawn from an exponential-type parametric family with an unknown parameter $θ$, a class that includes exponential, Pareto, and bounded-support power-family distributions. We first characterize the optimal full-information asymptotic competitive ratio for this family. In the unbounded-support case, the limit is $ {\left(θ/({θ-c_+})\right)^{c_+/θ}}/ {Γ(1-c_+/θ)},$ while in the bounded-support case, the limit is $1$. We then propose a confidence-based dynamic-programming policy for online learning. By exploiting the explicit parametric structure, the policy achieves the same optimal asymptotic competitive ratio using only online observations, without external offline samples. We further derive distribution-specific convergence rates for canonical examples. Finally, numerical experiments on synthetic instances illustrate the performance of our algorithm.
• Abstract（参考訳）: 本研究では,指数型パラメトリック・ファミリーから引き出された帰納的不等式を未知のパラメータ$θ$,指数関数,パレート,および有界支持パワーファミリー分布を含むクラスで学習する。 まず、この家系の最適な完全情報漸近競合比を特徴付ける。 有界支持の場合、極限は$ {\left(θ/({θ-c_+})\right)^{c_+/θ}}/ {\(1-c_+/θ)} である。 次に、オンライン学習のための信頼性に基づく動的プログラミングポリシーを提案する。 明示的なパラメトリック構造を利用することで、オンライン観測のみを用いて、外部のオフラインサンプルを使わずに、同じ最適な漸近競合比を達成する。 さらに、正規例に対する分布特異的収束率を導出する。 最後に, 合成事例に関する数値実験により, アルゴリズムの性能を実証した。

関連論文リスト

• Rate optimal learning of equilibria from data [63.14746189846806]
  マルチエージェント・イミテーション・ラーニング(MAIL)における理論的ギャップは,非対話的MAILの限界を特徴づけ,ほぼ最適なサンプル複雑性を持つ最初の対話的アルゴリズムを提示することによって解決する。 インタラクティブな設定では、報酬のない強化学習と対話型MAILを組み合わせたフレームワークを導入し、それをMAIL-WARMというアルゴリズムでインスタンス化する。 我々は,我々の理論を裏付ける数値的な結果を提供し,グリッドワールドのような環境において,行動クローンが学習に失敗する状況を示す。
  論文  参考訳（メタデータ） (2025-10-10T12:28:35Z)
• On Uniform Weighted Deep Polynomial approximation [0.0]
  本研究では,一方の非対称な振舞いと他方の減衰を有する関数に適した重み付き深部近似剤のクラスを導入,解析する。 このフレームワークがTaylor, Chebyshev, and standard Deep Approximantsより優れていることを示す。
  論文  参考訳（メタデータ） (2025-06-26T14:25:32Z)
• Finite Sample Analysis of Linear Temporal Difference Learning with Arbitrary Features [21.241323360100548]
  本稿では、任意の機能の下で線形TD($lambda$)演算に対する最初の$L2$収束率を確立する。 任意の特徴から生じる解の潜在的非特異性に対処するために、単一点ではなく解集合への収束率を特徴とする新しい近似結果を開発する。
  論文  参考訳（メタデータ） (2025-05-27T16:17:49Z)
• Towards a Sharp Analysis of Offline Policy Learning for $f$-Divergence-Regularized Contextual Bandits [49.96531901205305]
  我々は$f$-divergence-regularized offline policy learningを分析する。 逆Kullback-Leibler (KL) の発散に対して、単極集中性の下での最初の$tildeO(epsilon-1)$サンプル複雑性を与える。 これらの結果は,$f$-divergence-regularized policy learningの包括的理解に向けて大きな一歩を踏み出したものと考えられる。
  論文  参考訳（メタデータ） (2025-02-09T22:14:45Z)
• Beyond likelihood ratio bias: Nested multi-time-scale stochastic approximation for likelihood-free parameter estimation [49.78792404811239]
  確率分析形式が不明なシミュレーションベースモデルにおける推論について検討する。 我々は、スコアを同時に追跡し、パラメータ更新を駆動する比率のないネスト型マルチタイムスケール近似(SA)手法を用いる。 我々のアルゴリズムは、オリジナルのバイアス$Obig(sqrtfrac1Nbig)$を排除し、収束率を$Obig(beta_k+sqrtfracalpha_kNbig)$から加速できることを示す。
  論文  参考訳（メタデータ） (2024-11-20T02:46:15Z)
• Nonlinear Stochastic Gradient Descent and Heavy-tailed Noise: A Unified Framework and High-probability Guarantees [56.80920351680438]
  本研究では,重音の存在下でのオンライン学習における高確率収束について検討する。 ノイズモーメントを仮定することなく、幅広い種類の非線形性を保証する。
  論文  参考訳（メタデータ） (2024-10-17T18:25:28Z)
• High-probability Convergence Bounds for Nonlinear Stochastic Gradient Descent Under Heavy-tailed Noise [59.25598762373543]
  重み付き雑音の存在下でのストリーミングデータにおける学習の精度保証について検討した。 解析的に、与えられた問題に対する設定の選択に$ta$を使うことができることを実証する。
  論文  参考訳（メタデータ） (2023-10-28T18:53:41Z)
• On Computationally Efficient Learning of Exponential Family Distributions [33.229944519289795]
  我々は、サポートと自然なパラメータが適切にバウンドされている設定に焦点を当てる。 本手法は,ノードワイズ・スパースランダムフィールドに適した場合,$O(sf log(k)/alpha2)$のオーダー最適サンプル複雑性を実現する。
  論文  参考訳（メタデータ） (2023-09-12T17:25:32Z)
• Kernel-based off-policy estimation without overlap: Instance optimality beyond semiparametric efficiency [53.90687548731265]
  本研究では,観測データに基づいて線形関数を推定するための最適手順について検討する。 任意の凸および対称函数クラス $mathcalF$ に対して、平均二乗誤差で有界な非漸近局所ミニマックスを導出する。
  論文  参考訳（メタデータ） (2023-01-16T02:57:37Z)
• Optimal and instance-dependent guarantees for Markovian linear stochastic approximation [47.912511426974376]
  標準スキームの最後の繰り返しの2乗誤差に対して、$t_mathrmmix tfracdn$の非漸近境界を示す。 マルコフ雑音による政策評価について,これらの結果のまとめを導出する。
  論文  参考訳（メタデータ） (2021-12-23T18:47:50Z)
• A Computationally Efficient Method for Learning Exponential Family Distributions [29.289136623702056]
  我々は、計算的かつ統計的に効率的な方法でサンプルから$k$パラメータ指数族(英語版)の自然パラメータを学習する問題を考える。 本手法は指数関数族に属する再分類分布の最大推定値とみなすことができる。
  論文  参考訳（メタデータ） (2021-10-28T18:42:04Z)
• Tight Nonparametric Convergence Rates for Stochastic Gradient Descent under the Noiseless Linear Model [0.0]
  このモデルに基づく最小二乗リスクに対する1パス, 固定段差勾配勾配の収束度を解析した。 特殊な場合として、ランダムなサンプリング点における値のノイズのない観測から単位区間上の実関数を推定するオンラインアルゴリズムを解析する。
  論文  参考訳（メタデータ） (2020-06-15T08:25:50Z)
• Is Temporal Difference Learning Optimal? An Instance-Dependent Analysis [102.29671176698373]
  我々は、割引決定過程における政策評価の問題に対処し、生成モデルの下で、ll_infty$errorに対するマルコフに依存した保証を提供する。 我々は、ポリシー評価のために、局所ミニマックス下限の両漸近バージョンと非漸近バージョンを確立し、アルゴリズムを比較するためのインスタンス依存ベースラインを提供する。
  論文  参考訳（メタデータ） (2020-03-16T17:15:28Z)

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

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