論文の概要: Optimal Contextual Bandits with Knapsacks under Realizibility via Regression Oracles

• arxiv url: http://arxiv.org/abs/2210.11834v1
• Date: Fri, 21 Oct 2022 09:28:53 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-24 14:00:22.363990
• Title: Optimal Contextual Bandits with Knapsacks under Realizibility via Regression Oracles
• Title（参考訳）: クナプサックを用いた回帰オラクルによる最適コンテキスト帯域
• Authors: Yuxuan Han, Jialin Zeng, Yang Wang, Yang Xiang, Jiheng Zhang
• Abstract要約: 我々は,knapsacks (CBwK) 問題を用いてコンテキスト的帯域幅について検討し,各行動がランダムな報酬をもたらす一方で,ベクトル形式のランダムなリソース消費を犠牲にしている。 本稿では,CBwKをオンライン回帰に還元することで,CBwKの汎用的かつ最適なアルゴリズムフレームワークを提案する。
• 参考スコア（独自算出の注目度）: 14.634964681825197
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the stochastic contextual bandit with knapsacks (CBwK) problem, where each action, taken upon a context, not only leads to a random reward but also costs a random resource consumption in a vector form. The challenge is to maximize the total reward without violating the budget for each resource. We study this problem under a general realizability setting where the expected reward and expected cost are functions of contexts and actions in some given general function classes $\mathcal{F}$ and $\mathcal{G}$, respectively. Existing works on CBwK are restricted to the linear function class since they use UCB-type algorithms, which heavily rely on the linear form and thus are difficult to extend to general function classes. Motivated by online regression oracles that have been successfully applied to contextual bandits, we propose the first universal and optimal algorithmic framework for CBwK by reducing it to online regression. We also establish the lower regret bound to show the optimality of our algorithm for a variety of function classes.
• Abstract（参考訳）: 確率的文脈的帯域幅をknapsacks (CBwK) 問題を用いて検討し、各アクションがコンテキストに基づいて、ランダムな報酬をもたらすだけでなく、ベクトル形式のランダムなリソース消費を発生させる。 課題は、各リソースの予算に違反することなく、全報酬を最大化することです。 この問題を、期待される報酬と期待されるコストが、与えられた一般関数クラス $\mathcal{F}$ と $\mathcal{G}$ のコンテキストとアクションの関数であるような一般化可能性設定の下で研究する。 既存のCBwKの作業は、線形形式に強く依存するUCB型アルゴリズムを使用するため、一般関数クラスに拡張することが難しいため、線形関数クラスに制限される。 オンラインレグレッションオラクルがコンテキストバンディットに適用に成功していることに動機づけられ、オンラインレグレッションに縮小することで、cbwkの普遍的かつ最適なアルゴリズムフレームワークを提案する。 また、様々な関数クラスに対するアルゴリズムの最適性を示すために、より低い後悔を確立する。

関連論文リスト

• Second Order Methods for Bandit Optimization and Control [34.51425758864638]
  我々は,大規模な凸関数に対して,このアルゴリズムが最適($kappa$-2020と呼ぶ凸関数の観点で)となることを示す。 また,メモリを用いたオンライン凸最適化への2次帯域幅アルゴリズムの適用について検討した。
  論文  参考訳（メタデータ） (2024-02-14T04:03:38Z)
• Contextual Bandits with Packing and Covering Constraints: A Modular Lagrangian Approach via Regression [65.8785736964253]
  本稿では,線形制約付きコンテキスト帯域(CBwLC)について考察する。これは,アルゴリズムが全消費の線形制約を受ける複数のリソースを消費するコンテキスト帯域の変種である。 この問題はknapsacks (CBwK) を用いてコンテキスト的帯域幅を一般化し、制約のパッケージ化とカバー、および正および負のリソース消費を可能にする。 本稿では,回帰オラクルに基づくCBwLC(CBwK)のアルゴリズムについて述べる。このアルゴリズムは単純で,計算効率が良く,統計的に最適である。
  論文  参考訳（メタデータ） (2022-11-14T16:08:44Z)
• Contextual bandits with concave rewards, and an application to fair ranking [108.48223948875685]
  CBCR (Contextual Bandits with Concave Rewards) に対する反省点のある最初のアルゴリズムを提案する。 我々は,スカラー・リワード問題に対するCBCRの後悔から,新たな縮小を導出した。 推薦の公正さによって動機づけられたCBCRの特別事例として,ランク付けと公正を意識した目的について述べる。
  論文  参考訳（メタデータ） (2022-10-18T16:11:55Z)
• Anti-Concentrated Confidence Bonuses for Scalable Exploration [57.91943847134011]
  固有の報酬は、探検と探検のトレードオフを扱う上で中心的な役割を果たす。 楕円ボーナスを効率的に近似するためのエンファンティ集中型信頼境界を導入する。 我々は,Atariベンチマーク上での現代固有の報酬と競合する,深層強化学習のための実用的な変種を開発する。
  論文  参考訳（メタデータ） (2021-10-21T15:25:15Z)
• Adapting to Misspecification in Contextual Bandits [82.55565343668246]
  我々は、$varepsilon$-misspecified contextual banditsに対して、新しいオラクル効率アルゴリズム群を導入する。 我々は、未知の不特定値に対して最適な$O(dsqrtT + varepsilonsqrtdT)$ regret boundを達成する最初のアルゴリズムを得る。
  論文  参考訳（メタデータ） (2021-07-12T21:30:41Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)
• Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizability [18.45278329799526]
  オフライン回帰オラクルへの$O(log T)$呼び出しだけで統計的に最適な後悔を実現する高速で単純なアルゴリズムを設計する。 この結果は、文脈的帯域幅からオフライン回帰への最初の普遍的かつ最適の還元を提供する。
  論文  参考訳（メタデータ） (2020-03-28T04:16:52Z)
• Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles [112.89548995091182]
  我々は、文脈的帯域幅からオンライン回帰への、初めての普遍的で最適な削減を提供する。 我々のアルゴリズムは、実現可能性以上の分布仮定は必要とせず、コンテキストが逆選択された場合でも機能する。
  論文  参考訳（メタデータ） (2020-02-12T11:33:46Z)

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

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