論文の概要: Contextual Bandits with Packing and Covering Constraints: A Modular Lagrangian Approach via Regression

• arxiv url: http://arxiv.org/abs/2211.07484v4
• Date: Mon, 12 Jun 2023 01:43:30 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-14 02:08:52.051543
• Title: Contextual Bandits with Packing and Covering Constraints: A Modular Lagrangian Approach via Regression
• Title（参考訳）: パッキングとカバー制約を伴うコンテキストバンディット:回帰によるモジュールラグランジアンアプローチ
• Authors: Aleksandrs Slivkins and Karthik Abinav Sankararaman and Dylan J. Foster
• Abstract要約: 我々は,線形制約付きコンテキスト帯域(CBwLC)を,knapsacks(CBwK)を用いたコンテキスト帯域(CBwLC)の変種として検討する。 この問題はknapsackでコンテキストの帯域幅を一般化し、制約のパッケージ化とカバー、そして正と負のリソース消費を可能にする。 回帰オラクルに基づくCBwLC(CBwK)の最初のアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 99.27350939441146
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider contextual bandits with linear constraints (CBwLC), 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 provide the first algorithm for CBwLC (or CBwK) that is based on regression oracles. The algorithm is simple, computationally efficient, and admits vanishing regret. It is statistically optimal for the variant of CBwK in which the algorithm must stop once some constraint is violated. Further, we provide the first vanishing-regret guarantees for CBwLC (or CBwK) that extend beyond the stochastic environment. We side-step strong impossibility results from prior work by identifying a weaker (and, arguably, fairer) benchmark to compare against. 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（参考訳）: 本稿では,線形制約付きコンテキスト帯域(CBwLC)について考察する。これは,アルゴリズムが全消費の線形制約を受ける複数のリソースを消費するコンテキスト帯域の変種である。 この問題はknapsacks (CBwK) を用いてコンテキスト的帯域幅を一般化し、制約のパッケージ化とカバー、および正および負のリソース消費を可能にする。 回帰オラクルに基づくCBwLC(CBwK)の最初のアルゴリズムを提案する。 このアルゴリズムは単純で計算効率が良く、後悔は消える。 CBwKの変種には統計的に最適であり、ある制約が破られたらアルゴリズムは停止しなければならない。 さらに,確率的環境を超えたCBwLC(CBwK)について,初めて消滅・回復保証を行う。 私たちは、比較するより弱い(そしておそらく公平な)ベンチマークを特定することで、以前の作業から強い不可能性(impossibility)を回避します。 我々のアルゴリズムは、CBwKのためのラグランジアンベースのテクニックであるLagrangeBwK(Immorlica et al., FOCS 2019)と、文脈的盗賊のための回帰ベースのテクニックであるSquareCB(Foster and Rakhlin, ICML 2020)に基づいて構築されている。 我々の分析は、両方の技術の本質的なモジュラリティを活用する。

関連論文リスト

• Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints [29.514323697659613]
  我々は,学習者が任意の長期制約を満たすことなく報酬を最大化することを目的とした,knapsacks問題によるバンディットの一般化に対処する。 私たちのゴールは、双方の制約の下で機能するベスト・オブ・ザ・ワールドのアルゴリズムを設計することです。
  論文  参考訳（メタデータ） (2024-05-25T08:09:36Z)
• No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization [26.415300249303748]
  本研究は, 一次アルゴリズムと双対アルゴリズムを弱適応化させることにより, 制約のサブ線形違反を回避可能であることを示す。 最初のケースでは、アルゴリズムがサブ線形後悔を保証することを示し、後者の場合、厳密な競合比を$rho/(1+rho)$とする。 この結果から,線形制約付き文脈帯域問題に対する新たな結果が得られる。
  論文  参考訳（メタデータ） (2024-05-10T16:22:33Z)
• 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)
• Improved Branch and Bound for Neural Network Verification via Lagrangian Decomposition [161.09660864941603]
  ニューラルネットワークの入出力特性を公式に証明するためのブランチとバウンド(BaB)アルゴリズムのスケーラビリティを改善します。 活性化に基づく新しい分岐戦略とBaBフレームワークであるブランチとデュアルネットワーク境界(BaDNB)を提案する。 BaDNBは、従来の完全検証システムを大きなマージンで上回り、対数特性で平均検証時間を最大50倍に削減した。
  論文  参考訳（メタデータ） (2021-04-14T09:22:42Z)
• 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)

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

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