論文の概要: Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizability

• arxiv url: http://arxiv.org/abs/2003.12699v5
• Date: Sat, 10 Jul 2021 04:40:21 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-18 23:37:48.139431
• Title: Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizability
• Title（参考訳）: Monsterをバイパスする: 実現可能性下でのコンテキスト帯域の高速かつ簡易な最適アルゴリズム
• Authors: David Simchi-Levi, Yunzong Xu
• Abstract要約: オフライン回帰オラクルへの$O(log T)$呼び出しだけで統計的に最適な後悔を実現する高速で単純なアルゴリズムを設計する。 この結果は、文脈的帯域幅からオフライン回帰への最初の普遍的かつ最適の還元を提供する。
• 参考スコア（独自算出の注目度）: 18.45278329799526
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the general (stochastic) contextual bandit problem under the realizability assumption, i.e., the expected reward, as a function of contexts and actions, belongs to a general function class $\mathcal{F}$. We design a fast and simple algorithm that achieves the statistically optimal regret with only ${O}(\log T)$ calls to an offline regression oracle across all $T$ rounds. The number of oracle calls can be further reduced to $O(\log\log T)$ if $T$ is known in advance. Our results provide the first universal and optimal reduction from contextual bandits to offline regression, solving an important open problem in the contextual bandit literature. A direct consequence of our results is that any advances in offline regression immediately translate to contextual bandits, statistically and computationally. This leads to faster algorithms and improved regret guarantees for broader classes of contextual bandit problems.
• Abstract（参考訳）: 一般化可能性仮定の下での一般(確率的な)文脈的包帯問題、すなわち、期待される報酬は、文脈と行動の函数として、一般函数クラス $\mathcal{F}$ に属する。 我々は,すべての$T$ラウンドにわたるオフライン回帰オラクルへの${O}(\log T)$呼び出しだけで,統計的に最適な後悔を実現する,高速で単純なアルゴリズムを設計する。 oracleの呼び出し数はさらに$t$が事前に分かっている場合は$o(\log\log t)$に減らすことができる。 本研究は,コンテキストバンディットからオフライン回帰への最初の普遍的かつ最適な還元を行い,コンテキストバンディット文学における重要なオープン問題を解決した。 我々の結果の直接的な結果として、オフライン回帰の進展は直ちに統計的・計算的に文脈的帯域に変換される。 これにより、より高速なアルゴリズムと、より広い階層の文脈的バンディット問題の後悔の保証がもたらされる。

関連論文リスト

• Contexts can be Cheap: Solving Stochastic Contextual Bandits with Linear Bandit Algorithms [39.70492757288025]
  我々は,意思決定者がコンテキストを提供するコンテキスト線形帯域問題に対処する。 文脈問題を線形バンディット問題として解くことができることを示す。 この結果から,文脈的線形包帯に対して$O(dsqrtTlog T)$高確率残差が生じることが示唆された。
  論文  参考訳（メタデータ） (2022-11-08T22:18:53Z)
• Optimal Contextual Bandits with Knapsacks under Realizibility via Regression Oracles [14.634964681825197]
  我々は,knapsacks (CBwK) 問題を用いてコンテキスト的帯域幅について検討し,各行動がランダムな報酬をもたらす一方で,ベクトル形式のランダムなリソース消費を犠牲にしている。 本稿では,CBwKをオンライン回帰に還元することで,CBwKの汎用的かつ最適なアルゴリズムフレームワークを提案する。
  論文  参考訳（メタデータ） (2022-10-21T09:28:53Z)
• Improved High-Probability Regret for Adversarial Bandits with Time-Varying Feedback Graphs [62.52390282012508]
  我々は、T$ラウンド以上の時間変化フィードバックグラフを持つ、敵対的な$K$武器付きバンディットに対する高い確率的後悔境界について検討する。 提案アルゴリズムは,高い確率で最適に後悔する$widetildemathcalO((sum_t=1Talpha_t)1/2+max_tin[T]alpha_t]$を達成するアルゴリズムを開発した。 また,弱可観測グラフに対する最適高確率残差を求めるアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-10-04T04:36:15Z)
• Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Bandits [99.86860277006318]
  本稿では,一組の逆アルゴリズムを組み合わせ,学習することの問題点について考察する。 Agarwal et al. の CORRAL はこの目標を、$widetildeO(sqrtd S T)$ の残酷なオーバーヘッドで達成している。 この問題に触発されて、後悔のオーバーヘッドが百万ドルにしか依存しない大規模バンディットアルゴリズムのバンドを囲む新しいレシピを提案する。
  論文  参考訳（メタデータ） (2022-02-12T21:55:44Z)
• Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability [59.81339109121384]
  我々は,学習者が文脈情報を用いて2つの決定を下す連続的な決定設定であるK$コンテキストデュエルバンディット問題について検討するが,一方の判断が他方よりも優れていることを示唆する強調基準に基づくフィードバックのみを観察する。 提案手法は, 最善応答後悔という新たな概念に対して, 最善応答後悔に対する最適後悔率を実現するアルゴリズムである。
  論文  参考訳（メタデータ） (2021-11-24T07:14:57Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)
• An Efficient Algorithm For Generalized Linear Bandit: Online Stochastic Gradient Descent and Thompson Sampling [83.48992319018147]
  プレイヤーが過去の観測結果に基づいて逐次意思決定を行い、累積報酬を最大化する文脈的帯域幅問題を考える。 この問題を解決する自然な方法は、ステップごとの時間とメモリの複雑さを一定に抑えるために、オンライン勾配降下(SGD)を適用することである。 本研究では,オンラインSGDが一般化線形帯域問題に適用可能であることを示す。 過去の情報を活用するためにシングルステップのSGD更新を利用するSGD-TSアルゴリズムは、全時間複雑度で$tildeO(sqrtT)$ regretを達成する。
  論文  参考訳（メタデータ） (2020-06-07T01:12:39Z)
• Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles [112.89548995091182]
  我々は、文脈的帯域幅からオンライン回帰への、初めての普遍的で最適な削減を提供する。 我々のアルゴリズムは、実現可能性以上の分布仮定は必要とせず、コンテキストが逆選択された場合でも機能する。
  論文  参考訳（メタデータ） (2020-02-12T11:33:46Z)

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

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