論文の概要: Contextual Pandora's Box

• arxiv url: http://arxiv.org/abs/2205.13114v3
• Date: Tue, 16 Jan 2024 01:34:20 GMT
• ステータス: 処理完了
• システム内更新日: 2024-01-18 03:56:23.579666
• Title: Contextual Pandora's Box
• Title（参考訳）: コンテキストPandoraのボックス
• Authors: Alexia Atsidakou, Constantine Caramanis, Evangelia Gergatsouli, Orestis Papadigenopoulos, Christos Tzamos
• Abstract要約: PandoraのBoxは基本的な最適化の問題です。 我々はコンテキストを取り入れつつ、PandoraのBoxをオンライン環境で研究する。 我々の主な成果は、最適なアルゴリズムに相容れない性能の非回帰アルゴリズムである。
• 参考スコア（独自算出の注目度）: 36.625727016146485
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Pandora's Box is a fundamental stochastic optimization problem, where the decision-maker must find a good alternative while minimizing the search cost of exploring the value of each alternative. In the original formulation, it is assumed that accurate distributions are given for the values of all the alternatives, while recent work studies the online variant of Pandora's Box where the distributions are originally unknown. In this work, we study Pandora's Box in the online setting, while incorporating context. At every round, we are presented with a number of alternatives each having a context, an exploration cost and an unknown value drawn from an unknown distribution that may change at every round. Our main result is a no-regret algorithm that performs comparably well to the optimal algorithm which knows all prior distributions exactly. Our algorithm works even in the bandit setting where the algorithm never learns the values of the alternatives that were not explored. The key technique that enables our result is a novel modification of the realizability condition in contextual bandits that connects a context to a sufficient statistic of each alternative's distribution (its "reservation value") rather than its mean.
• Abstract（参考訳）: pandoraのボックスは基本的な確率的最適化問題であり、意思決定者は、各選択肢の価値を探求する検索コストを最小化しながら、優れた選択肢を見つけなければならない。 オリジナルの定式化では、全ての代替品の値に正確な分布が与えられていると推定され、最近の研究では、分布が不明なPandoraのBoxのオンライン版が研究されている。 本研究では,PandoraのBoxをオンライン環境で研究し,コンテキストを取り入れた。 各ラウンドで、各ラウンドで変化する可能性のある未知の分布から引き出されたコンテキスト、探索コスト、未知の値を持つ、いくつかの代替案が提示されます。 我々の主な成果は、全ての事前分布を正確に知る最適アルゴリズムと相反する非回帰アルゴリズムである。 我々のアルゴリズムはバンディット設定でも動作し、アルゴリズムは探索されなかった代替品の値を決して学習しない。 結果を可能にするキーテクニックは,コンテキストバンディットにおける実現可能性条件の新規な修正であり,その平均ではなく,各選択肢の分布の十分な統計値(保存値)とを接続するものである。

関連論文リスト

• Variance-Dependent Regret Bounds for Non-stationary Linear Bandits [52.872628573907434]
  報酬分布の分散と$B_K$の分散を利用するアルゴリズムを提案する。 Restarted Weighted$textOFUL+$とRestarted$textSAVE+$の2つの新しいアルゴリズムを紹介します。 特に、V_K$が$K$よりはるかに小さい場合、我々のアルゴリズムは、異なる設定下での非定常線形バンドレットの最先端結果よりも優れている。
  論文  参考訳（メタデータ） (2024-03-15T23:36:55Z)
• Semi-Bandit Learning for Monotone Stochastic Optimization [20.776114616154242]
  モノトーン」問題のクラスに対して汎用的なオンライン学習アルゴリズムを提供する。 我々のフレームワークは、預言者、Pandoraのボックスナップサック、不等式マッチング、部分モジュラー最適化など、いくつかの基本的な最適化問題に適用できる。
  論文  参考訳（メタデータ） (2023-12-24T07:46:37Z)
• Bandit Algorithms for Prophet Inequality and Pandora's Box [13.709418181148148]
  マルチアーメッド・バンディットモデルにおける預言不等式とPandoraのボックス問題について検討した。 我々の結果は、予言の不平等とPandoraのBoxの両面で、ほぼ最適の$tildeO(mathsfpoly(n)sqrtT)$トータル後悔アルゴリズムを提供する。
  論文  参考訳（メタデータ） (2022-11-16T00:10:35Z)
• Online Learning for Min Sum Set Cover and Pandora's Box [18.30302893560438]
  最適な探索順序のコストに対して一定の競合性を持つ計算効率の良いアルゴリズムを提案する。 本結果は,Pandora の Box および Min Sum Set Cover の他のよく研究されている変種に一般化する。
  論文  参考訳（メタデータ） (2022-02-10T07:12:44Z)
• Linear Contextual Bandits with Adversarial Corruptions [91.38793800392108]
  本稿では,敵対的腐敗の存在下での線形文脈的包帯問題について検討する。 逆汚染レベルに適応する分散認識アルゴリズムをC$で提案する。
  論文  参考訳（メタデータ） (2021-10-25T02:53:24Z)
• Corralling Stochastic Bandit Algorithms [54.10645564702416]
  相関アルゴリズムの後悔は、最も報酬の高い腕を含む最高のアルゴリズムの後悔よりも悪くはないことを示す。 最高報酬と他の報酬の差は、最高報酬と他の報酬の差に依存することを示す。
  論文  参考訳（メタデータ） (2020-06-16T15:33:12Z)
• Rate-adaptive model selection over a collection of black-box contextual bandit algorithms [0.966840768820136]
  文脈的帯域設定におけるモデル選択タスクについて検討する。 我々の提案は、一般的なブラックボックス・コンテクスト・バンディットアルゴリズムの収集に適応する最初のものである。
  論文  参考訳（メタデータ） (2020-06-05T18:55:16Z)
• Greedy Algorithm almost Dominates in Smoothed Contextual Bandits [100.09904315064372]
  オンライン学習アルゴリズムは探索と搾取のバランスをとる必要がある。 欲求的アプローチは、他のアルゴリズムのベイズ的後悔率とほぼ一致していることを示す。
  論文  参考訳（メタデータ） (2020-05-19T18:11:40Z)
• Model Selection in Contextual Stochastic Bandit Problems [51.94632035240787]
  基本アルゴリズムを選択できるメタアルゴリズムを開発した。 基本アルゴリズムの1つが$O(sqrtT)$後悔している場合でも、一般的には$Omega(sqrtT)$後悔よりも良いものを得ることはできません。
  論文  参考訳（メタデータ） (2020-03-03T18:46:34Z)

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

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