論文の概要: Contextual Bandits with Packing and Covering Constraints: A Modular
Lagrangian Approach via Regression
- arxiv url: http://arxiv.org/abs/2211.07484v2
- Date: Mon, 20 Mar 2023 22:13:29 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-24 02:05:03.219595
- Title: Contextual Bandits with Packing and Covering Constraints: A Modular
Lagrangian Approach via Regression
- Title(参考訳): パッキングとカバー制約を伴うコンテキストバンディット:回帰によるモジュールラグランジアンアプローチ
- Authors: Aleksandrs Slivkins and Karthik Abinav Sankararaman and Dylan Foster
- Abstract要約: 本稿では,アルゴリズムが全消費の線形制約を受ける複数の資源を消費する,文脈的帯域幅の変形について考察する。
我々は, 単純で計算効率が良く, 後悔の欠如を認める新しいアルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 77.89393441155376
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider a variant of contextual bandits in which the algorithm consumes
multiple resources subject to linear constraints on total consumption. This
problem generalizes contextual bandits with knapsacks (CBwK), allowing for
packing and covering constraints, as well as positive and negative resource
consumption. We present a new algorithm that is simple, computationally
efficient, and admits vanishing regret. It is statistically optimal for CBwK
when an algorithm must stop once some constraint is violated. Our algorithm
builds on LagrangeBwK (Immorlica et al., FOCS 2019) , a Lagrangian-based
technique for CBwK, and SquareCB (Foster and Rakhlin, ICML 2020), a
regression-based technique for contextual bandits. Our analysis leverages the
inherent modularity of both techniques.
- Abstract(参考訳): 本稿では,アルゴリズムが全消費の線形制約を受ける複数の資源を消費する,文脈的帯域幅の変形について考察する。
この問題はknapsacks (CBwK) を用いてコンテキスト的帯域幅を一般化し、制約のパッケージ化とカバー、および正および負のリソース消費を可能にする。
我々は, 単純で計算効率が良く, 後悔の欠如を認める新しいアルゴリズムを提案する。
CBwK はアルゴリズムが何らかの制約に違反したら停止しなければならない場合に統計的に最適である。
我々のアルゴリズムは、CBwKのためのラグランジアンベースのテクニックであるLagrangeBwK(Immorlica et al., FOCS 2019)と、文脈的盗賊のための回帰ベースのテクニックであるSquareCB(Foster and Rakhlin, ICML 2020)に基づいて構築されている。
我々の分析は、両方の技術の本質的なモジュラリティを活用する。
関連論文リスト
- Second Order Methods for Bandit Optimization and Control [37.70434692823672]
我々は,大規模な凸関数に対して,このアルゴリズムが最適($kappa$-2020と呼ぶ凸関数の観点で)となることを示す。
また,メモリを用いたオンライン凸最適化への2次帯域幅アルゴリズムの適用について検討した。
論文 参考訳(メタデータ) (2024-02-14T04:03:38Z) - Online Clustering of Bandits with Misspecified User Models [42.56440072468658]
コンテキスト線形バンディット(Contextual linear bandit)は、与えられた腕の特徴を学習エージェントが各ラウンドで選択し、長期の累積報酬を最大化するオンライン学習問題である。
バンディットのクラスタリング(CB)と呼ばれる一連の研究は、ユーザの好みに対する協調効果を利用しており、古典的な線形バンディットアルゴリズムよりも大幅に改善されている。
本稿では,不特定ユーザモデル (CBMUM) による盗賊のクラスタリングに関する重要な問題を初めて提示する。
モデル誤特定による不正確なユーザの選好推定と誤クラスタリングを両立できる頑健なCBアルゴリズムRCLUMBとRCLUMBを考案した。
論文 参考訳(メタデータ) (2023-10-04T10:40:50Z) - Optimal Contextual Bandits with Knapsacks under Realizibility via
Regression Oracles [14.634964681825197]
我々は,knapsacks (CBwK) 問題を用いてコンテキスト的帯域幅について検討し,各行動がランダムな報酬をもたらす一方で,ベクトル形式のランダムなリソース消費を犠牲にしている。
本稿では,CBwKをオンライン回帰に還元することで,CBwKの汎用的かつ最適なアルゴリズムフレームワークを提案する。
論文 参考訳(メタデータ) (2022-10-21T09:28:53Z) - 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) - On Kernelized Multi-Armed Bandits with Constraints [16.102401271318012]
一般に未知の報酬関数と一般未知の制約関数を併用した帯域幅問題について検討する。
本稿では,アルゴリズムの性能解析のための一般的なフレームワークを提案する。
本稿では,数値実験により提案アルゴリズムの優れた性能を示す。
論文 参考訳(メタデータ) (2022-03-29T14:02:03Z) - Upper Confidence Bounds for Combining Stochastic Bandits [52.10197476419621]
バンディットアルゴリズムを結合する簡単な手法を提案する。
私たちのアプローチは、個々のbanditアルゴリズムのそれぞれを、より高いレベルのn$-armed bandit問題のアームとして扱う"meta-ucb"手順に基づいています。
論文 参考訳(メタデータ) (2020-12-24T05:36:29Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-06-17T22:32:19Z) - Beyond UCB: Optimal and Efficient Contextual Bandits with Regression
Oracles [112.89548995091182]
我々は、文脈的帯域幅からオンライン回帰への、初めての普遍的で最適な削減を提供する。
我々のアルゴリズムは、実現可能性以上の分布仮定は必要とせず、コンテキストが逆選択された場合でも機能する。
論文 参考訳(メタデータ) (2020-02-12T11:33:46Z) - Improved Algorithms for Conservative Exploration in Bandits [113.55554483194832]
文脈線形帯域設定における保守的学習問題について検討し、新しいアルゴリズムである保守的制約付きLinUCB(CLUCB2)を導入する。
我々は、既存の結果と一致したCLUCB2に対する後悔の限界を導き、多くの合成および実世界の問題において、最先端の保守的バンディットアルゴリズムよりも優れていることを実証的に示す。
論文 参考訳(メタデータ) (2020-02-08T19:35:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。