論文の概要: 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アルゴリズムを構築し,その新たな解析を行った。
関連論文リスト
- Borda Regret Minimization for Generalized Linear Dueling Bandits [65.09919504862496]
本稿では,ボルダスコアが最も高い項目を識別することを目的とした,デュエルバンディットに対するボルダ後悔最小化問題について検討する。
本稿では,多くの既存モデルをカバーする一般化線形デュエルバンドモデルのリッチクラスを提案する。
我々のアルゴリズムは$tildeO(d2/3 T2/3)$ regretを達成し、これも最適である。
論文 参考訳(メタデータ) (2023-03-15T17:59:27Z) - Contextual Bandits with Packing and Covering Constraints: A Modular
Lagrangian Approach via Regression [99.27350939441146]
我々は,線形制約付きコンテキスト帯域(CBwLC)を,knapsacks(CBwK)を用いたコンテキスト帯域(CBwLC)の変種として検討する。
この問題はknapsackでコンテキストの帯域幅を一般化し、制約のパッケージ化とカバー、そして正と負のリソース消費を可能にする。
回帰オラクルに基づくCBwLC(CBwK)の最初のアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-11-14T16:08:44Z) - The price of unfairness in linear bandits with biased feedback [62.25313751895011]
線形帯域フィードバックによる逐次意思決定の問題点について検討する。
その結果,不偏フィードバック下で得られたdT 1/2 log(T) の後悔率よりも最悪の後悔率が高いことがわかった。
興味深いことに、ギャップ依存率によって、問題はバイアスのないものほど難しくない非自明なインスタンスの存在が明らかになる。
論文 参考訳(メタデータ) (2022-03-18T08:03:20Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。