論文の概要: Adapting to Misspecification in Contextual Bandits

• arxiv url: http://arxiv.org/abs/2107.05745v1
• Date: Mon, 12 Jul 2021 21:30:41 GMT
• ステータス: 処理完了
• システム内更新日: 2021-07-14 14:54:10.526004
• Title: Adapting to Misspecification in Contextual Bandits
• Title（参考訳）: 文脈帯域における誤特定への適応
• Authors: Dylan J. Foster and Claudio Gentile and Mehryar Mohri and Julian Zimmert
• Abstract要約: 我々は、$varepsilon$-misspecified contextual banditsに対して、新しいオラクル効率アルゴリズム群を導入する。 我々は、未知の不特定値に対して最適な$O(dsqrtT + varepsilonsqrtdT)$ regret boundを達成する最初のアルゴリズムを得る。
• 参考スコア（独自算出の注目度）: 82.55565343668246
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A major research direction in contextual bandits is to develop algorithms that are computationally efficient, yet support flexible, general-purpose function approximation. Algorithms based on modeling rewards have shown strong empirical performance, but typically require a well-specified model, and can fail when this assumption does not hold. Can we design algorithms that are efficient and flexible, yet degrade gracefully in the face of model misspecification? We introduce a new family of oracle-efficient algorithms for $\varepsilon$-misspecified contextual bandits that adapt to unknown model misspecification -- both for finite and infinite action settings. Given access to an online oracle for square loss regression, our algorithm attains optimal regret and -- in particular -- optimal dependence on the misspecification level, with no prior knowledge. Specializing to linear contextual bandits with infinite actions in $d$ dimensions, we obtain the first algorithm that achieves the optimal $O(d\sqrt{T} + \varepsilon\sqrt{d}T)$ regret bound for unknown misspecification level $\varepsilon$. On a conceptual level, our results are enabled by a new optimization-based perspective on the regression oracle reduction framework of Foster and Rakhlin, which we anticipate will find broader use.
• Abstract（参考訳）: 文脈帯域における主要な研究方向は、計算効率が良く、柔軟な汎用関数近似をサポートするアルゴリズムを開発することである。 モデリング報酬に基づくアルゴリズムは、強い経験的性能を示してきたが、典型的には明確に定義されたモデルが必要であり、この仮定が守られなければ失敗する可能性がある。 効率的でフレキシブルなアルゴリズムを設計することはできますが、モデルの誤特定に直面して優雅に分解できますか? 我々は、未知のモデルの不特定性に適応する、$\varepsilon$-misspecified contextual bandits(有限および無限のアクション設定)のための、新しいオラクル効率アルゴリズム群を紹介します。 正方損失の回帰のためにオンラインのオラクルにアクセスすると、我々のアルゴリズムは最適に後悔し、特に、事前の知識なしに、誤特定レベルに最適に依存する。 d$次元の無限の作用を持つ線形文脈的包帯に特化して、未知の誤特定レベル$\varepsilon$に対する最適$O(d\sqrt{T} + \varepsilon\sqrt{d}T)$後悔境界を達成する最初のアルゴリズムを得る。 概念レベルでは,Foster と Rakhlin の回帰オラクル還元フレームワークに対する新たな最適化に基づく視点で,より広範な利用が期待できる。

関連論文リスト

• Second Order Methods for Bandit Optimization and Control [34.51425758864638]
  我々は,大規模な凸関数に対して,このアルゴリズムが最適($kappa$-2020と呼ぶ凸関数の観点で)となることを示す。 また,メモリを用いたオンライン凸最適化への2次帯域幅アルゴリズムの適用について検討した。
  論文  参考訳（メタデータ） (2024-02-14T04:03:38Z)
• Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability [59.81339109121384]
  我々は,学習者が文脈情報を用いて2つの決定を下す連続的な決定設定であるK$コンテキストデュエルバンディット問題について検討するが,一方の判断が他方よりも優れていることを示唆する強調基準に基づくフィードバックのみを観察する。 提案手法は, 最善応答後悔という新たな概念に対して, 最善応答後悔に対する最適後悔率を実現するアルゴリズムである。
  論文  参考訳（メタデータ） (2021-11-24T07:14:57Z)
• Misspecified Gaussian Process Bandit Optimization [59.30399661155574]
  カーネル化されたバンディットアルゴリズムは、この問題に対して強い経験的および理論的性能を示した。 本稿では、未知関数を$epsilon$-一様近似で近似できるエンフェミス特定カーネル化帯域設定を、ある再生カーネルヒルベルト空間(RKHS)において有界ノルムを持つ関数で導入する。 提案アルゴリズムは,不特定性に関する事前知識を伴わず,$epsilon$への最適依存を実現する。
  論文  参考訳（メタデータ） (2021-11-09T09:00:02Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• Adapting to misspecification in contextual bandits with offline regression oracles [7.312170216336086]
  本稿では,適切な安全ポリシーに回帰することで,誤特定誤りに適応する文脈的帯域幅アルゴリズムのファミリーを提案する。 我々のアルゴリズムは、平均的な不特定化レベルの測定で優雅に劣化する後悔の保証を保証するために、オフラインの回帰オラクルのみを必要とします。
  論文  参考訳（メタデータ） (2021-02-26T00:15:04Z)
• Conservative Stochastic Optimization with Expectation Constraints [11.393603788068777]
  本稿では,データ指標や環境変数に関して,目的関数と制約関数が期待する凸最適化問題を考察する。 このような問題を解決するためのオンラインおよび効率的なアプローチは、広く研究されていない。 本稿では、制約違反をゼロとし、$Oleft(T-frac12right)$Optimity gapを実現する新しい保守的最適化アルゴリズム(CSOA)を提案する。
  論文  参考訳（メタデータ） (2020-08-13T08:56:24Z)
• Model Selection in Contextual Stochastic Bandit Problems [51.94632035240787]
  基本アルゴリズムを選択できるメタアルゴリズムを開発した。 基本アルゴリズムの1つが$O(sqrtT)$後悔している場合でも、一般的には$Omega(sqrtT)$後悔よりも良いものを得ることはできません。
  論文  参考訳（メタデータ） (2020-03-03T18:46:34Z)
• Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles [112.89548995091182]
  我々は、文脈的帯域幅からオンライン回帰への、初めての普遍的で最適な削減を提供する。 我々のアルゴリズムは、実現可能性以上の分布仮定は必要とせず、コンテキストが逆選択された場合でも機能する。
  論文  参考訳（メタデータ） (2020-02-12T11:33:46Z)

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

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