論文の概要: Bandits with Knapsacks beyond the Worst-Case

• arxiv url: http://arxiv.org/abs/2002.00253v7
• Date: Tue, 28 Dec 2021 17:55:19 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-05 00:46:50.597913
• Title: Bandits with Knapsacks beyond the Worst-Case
• Title（参考訳）: ナップサックのバンディット、最悪のケースを超える
• Authors: Karthik Abinav Sankararaman and Aleksandrs Slivkins
• Abstract要約: 最悪の場合の視点を超えた3つの結果を提示します。 第一に、対数的、インスタンス依存的後悔率の完全な特徴を与える上限と下限を提供する。 第二に、与えられたラウンドにおけるアルゴリズムの性能を追跡するBwKの「簡単な後悔」を考察し、数ラウンドを除いては小さくないことを示す。
• 参考スコア（独自算出の注目度）: 87.54497614804409
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Bandits with Knapsacks (BwK) is a general model for multi-armed bandits under supply/budget constraints. While worst-case regret bounds for BwK are well-understood, we present three results that go beyond the worst-case perspective. First, we provide upper and lower bounds which amount to a full characterization for logarithmic, instance-dependent regret rates. Second, we consider "simple regret" in BwK, which tracks algorithm's performance in a given round, and prove that it is small in all but a few rounds. Third, we provide a general "reduction" from BwK to bandits which takes advantage of some known helpful structure, and apply this reduction to combinatorial semi-bandits, linear contextual bandits, and multinomial-logit bandits. Our results build on the BwK algorithm from \citet{AgrawalDevanur-ec14}, providing new analyses thereof.
• Abstract（参考訳）: Knapsacks (BwK) は、供給・予算制約下での多武装バンディットの一般的なモデルである。 BwKの最悪の後悔境界はよく理解されているが、最悪のケースの観点からは3つの結果が提示される。 第一に、対数的、インスタンス依存的後悔率の完全な特徴を与える上限と下限を提供する。 第二に、与えられたラウンドにおけるアルゴリズムの性能を追跡するBwKの「簡単な後悔」を考察し、数ラウンドを除いては小さくないことを示す。 第三に、BwKからバンドイットへの一般的な「還元」を提供し、いくつかの既知の有用な構造を利用し、この還元を組合せ半バンドイット、線形文脈バンドイット、多重項ロジットブレイディットに適用する。 本研究は,<citet{AgrawalDevanur-ec14}からBwKアルゴリズムを構築し,その新たな解析を行った。

関連論文リスト

• Feel-Good Thompson Sampling for Contextual Dueling Bandits [49.450050682705026]
  FGTS.CDBという名前のトンプソンサンプリングアルゴリズムを提案する。 われわれのアルゴリズムの核心は、デュエルバンディットに適した新しいFeel-Good探索用語である。 我々のアルゴリズムは最小限の誤差、すなわち $tildemathcalO(dsqrt T)$, $d$ はモデル次元、$T$ は時間水平線である。
  論文  参考訳（メタデータ） (2024-04-09T04:45:18Z)
• Adversarial Combinatorial Bandits with Switching Costs [55.2480439325792]
  本稿では,各ラウンドで選択したアームのスイッチに対して,切替コストが$lambda$の逆帯域問題について検討する。 ミニマックスの後悔とそれにアプローチするための設計アルゴリズムの限界を低くする。
  論文  参考訳（メタデータ） (2024-04-02T12:15:37Z)
• Zero-Inflated Bandits [11.60342504007264]
  ゼロ膨らんだ帯状地について検討し、報酬をゼロ膨らんだ分布と呼ばれる古典的な半パラメトリック分布としてモデル化する。 一般報奨仮定と準ガウス報奨を含む文脈一般化線形報奨を併用した多腕包帯の両面における後悔境界を導出する。 多くの設定において、我々のアルゴリズムの後悔率は、最小限の最適か最先端のどちらかである。
  論文  参考訳（メタデータ） (2023-12-25T03:13:21Z)
• 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)
• Bandits Corrupted by Nature: Lower Bounds on Regret and Robust Optimistic Algorithm [14.214707836697823]
  破損したバンドイット問題、すなわち、$k$未知の報酬分布を持つ多重武装バンドイット問題について検討する。 本稿では,ハマー推定器上に構築した,破損した盗賊に対する新しいUPB型アルゴリズムを提案する。 異なる報酬分布と異なるレベルの汚職に対する腐敗した包帯の解法におけるHubUCBとSeqHubUCBの有効性を実験的に説明した。
  論文  参考訳（メタデータ） (2022-03-07T07:44:05Z)
• Risk-Aware Algorithms for Combinatorial Semi-Bandits [7.716156977428555]
  半帯域フィードバック下でのマルチアームバンディット問題について検討する。 本稿では,最悪の場合の報酬のみを考慮したリスク尺度であるCVaR(Conditional Value-at-Risk)の最大化の問題を検討する。 本稿では,バンディットのスーパーアームから得られる報酬のCVaRを最大化するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-12-02T11:29:43Z)
• The Symmetry between Bandits and Knapsacks: A Primal-Dual LP-based Approach [15.626602292752624]
  そこで我々は,問題依存型対数的後悔境界を実現する原始双対アルゴリズムを開発した。 サブオプティマティリティ尺度は、後悔を決定する上でのナップサックの重要な役割を強調します。 これは一般のBwK問題を解くための最初の問題依存対数的後悔である。
  論文  参考訳（メタデータ） (2021-02-12T08:14:30Z)
• 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)

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

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