論文の概要: Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles

• arxiv url: http://arxiv.org/abs/2002.04926v2
• Date: Tue, 23 Jun 2020 10:44:25 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-01 19:49:18.251457
• Title: Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles
• Title（参考訳）: beyond ucb: レグレッションオラクルによる最適かつ効率的なコンテキストバンディット
• Authors: Dylan J. Foster and Alexander Rakhlin
• Abstract要約: 我々は、文脈的帯域幅からオンライン回帰への、初めての普遍的で最適な削減を提供する。 我々のアルゴリズムは、実現可能性以上の分布仮定は必要とせず、コンテキストが逆選択された場合でも機能する。
• 参考スコア（独自算出の注目度）: 112.89548995091182
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A fundamental challenge in contextual bandits is to develop flexible, general-purpose algorithms with computational requirements no worse than classical supervised learning tasks such as classification and regression. Algorithms based on regression have shown promising empirical success, but theoretical guarantees have remained elusive except in special cases. We provide the first universal and optimal reduction from contextual bandits to online regression. We show how to transform any oracle for online regression with a given value function class into an algorithm for contextual bandits with the induced policy class, with no overhead in runtime or memory requirements. We characterize the minimax rates for contextual bandits with general, potentially nonparametric function classes, and show that our algorithm is minimax optimal whenever the oracle obtains the optimal rate for regression. Compared to previous results, our algorithm requires no distributional assumptions beyond realizability, and works even when contexts are chosen adversarially.
• Abstract（参考訳）: 文脈的バンディットにおける基本的な課題は、分類や回帰といった古典的な教師付き学習タスクよりも、計算要件による柔軟で汎用的なアルゴリズムを開発することである。 回帰に基づくアルゴリズムは有望な実証的成功を示しているが、特別な場合を除いて理論的な保証は得られていない。 コンテキストバンディットからオンライン回帰への最初の普遍的かつ最適な還元を提供する。 我々は、任意の値関数クラスでオンライン回帰に対してoracleを変換する方法を示し、実行時やメモリ要件のオーバーヘッドを伴わずに、引き起こされたポリシークラスでコンテキストバンディットのアルゴリズムに変換する。 文脈的バンディットのミニマックスレートを一般的な非パラメトリック関数クラスで特徴付けし、オラクルが回帰の最適レートを得るたびに、アルゴリズムがミニマックス最適であることを示す。 従来の結果と比較して,本アルゴリズムは実現可能性以上の分布仮定は必要とせず,文脈が逆選択された場合でも機能する。

関連論文リスト

• Optimal Contextual Bandits with Knapsacks under Realizibility via Regression Oracles [14.634964681825197]
  我々は,knapsacks (CBwK) 問題を用いてコンテキスト的帯域幅について検討し,各行動がランダムな報酬をもたらす一方で,ベクトル形式のランダムなリソース消費を犠牲にしている。 本稿では,CBwKをオンライン回帰に還元することで,CBwKの汎用的かつ最適なアルゴリズムフレームワークを提案する。
  論文  参考訳（メタデータ） (2022-10-21T09:28:53Z)
• Smoothed Online Learning is as Easy as Statistical Learning [77.00766067963195]
  この設定では、最初のオラクル効率、非回帰アルゴリズムを提供する。 古典的な設定で関数クラスが学習可能な場合、文脈的包帯に対するオラクル効率のよい非回帰アルゴリズムが存在することを示す。
  論文  参考訳（メタデータ） (2022-02-09T19:22:34Z)
• Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability [59.81339109121384]
  我々は,学習者が文脈情報を用いて2つの決定を下す連続的な決定設定であるK$コンテキストデュエルバンディット問題について検討するが,一方の判断が他方よりも優れていることを示唆する強調基準に基づくフィードバックのみを観察する。 提案手法は, 最善応答後悔という新たな概念に対して, 最善応答後悔に対する最適後悔率を実現するアルゴリズムである。
  論文  参考訳（メタデータ） (2021-11-24T07:14:57Z)
• Adapting to Misspecification in Contextual Bandits [82.55565343668246]
  我々は、$varepsilon$-misspecified contextual banditsに対して、新しいオラクル効率アルゴリズム群を導入する。 我々は、未知の不特定値に対して最適な$O(dsqrtT + varepsilonsqrtdT)$ regret boundを達成する最初のアルゴリズムを得る。
  論文  参考訳（メタデータ） (2021-07-12T21:30:41Z)
• Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discrimination [82.52105963476703]
  統計的学習、オンライン学習、その他における繰り返しのテーマは、低騒音の問題に対してより速い収束率が可能であることである。 1次保証は統計的およびオンライン学習において比較的よく理解されている。 三角識別と呼ばれる対数損失と情報理論量が一階保証を得る上で基本的な役割を担っていることを示す。
  論文  参考訳（メタデータ） (2021-07-05T19:20:34Z)
• Adapting to misspecification in contextual bandits with offline regression oracles [7.312170216336086]
  本稿では,適切な安全ポリシーに回帰することで,誤特定誤りに適応する文脈的帯域幅アルゴリズムのファミリーを提案する。 我々のアルゴリズムは、平均的な不特定化レベルの測定で優雅に劣化する後悔の保証を保証するために、オフラインの回帰オラクルのみを必要とします。
  論文  参考訳（メタデータ） (2021-02-26T00:15:04Z)
• Fast OSCAR and OWL Regression via Safe Screening Rules [97.28167655721766]
  順序付き$L_1$ (OWL)正規化回帰は、高次元スパース学習のための新しい回帰分析である。 近勾配法はOWL回帰を解くための標準手法として用いられる。 未知の順序構造を持つ原始解の順序を探索することにより、OWL回帰の最初の安全なスクリーニングルールを提案する。
  論文  参考訳（メタデータ） (2020-06-29T23:35:53Z)
• Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizability [18.45278329799526]
  オフライン回帰オラクルへの$O(log T)$呼び出しだけで統計的に最適な後悔を実現する高速で単純なアルゴリズムを設計する。 この結果は、文脈的帯域幅からオフライン回帰への最初の普遍的かつ最適の還元を提供する。
  論文  参考訳（メタデータ） (2020-03-28T04:16:52Z)

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

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