論文の概要: Budgeted Combinatorial Multi-Armed Bandits

• arxiv url: http://arxiv.org/abs/2202.03704v1
• Date: Tue, 8 Feb 2022 07:58:25 GMT
• ステータス: 処理完了
• システム内更新日: 2022-02-10 01:01:04.909158
• Title: Budgeted Combinatorial Multi-Armed Bandits
• Title（参考訳）: 予算コンビネート型多腕バンディット
• Authors: Debojit Das, Shweta Jain, Sujit Gujar
• Abstract要約: 各ラウンドにおいて、アルゴリズムは1つ以上のアームからなるスーパーアームを選択する。 目標は、限られた予算内での全てのラウンドの後、予想される総後悔を最小限にすることである。 2つのアルゴリズムを実験的に比較し,CBwK-Greedy-UCBがCBwK-LP-UCBよりも漸進的に性能が向上することを示した。
• 参考スコア（独自算出の注目度）: 9.765091765083374
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider a budgeted combinatorial multi-armed bandit setting where, in every round, the algorithm selects a super-arm consisting of one or more arms. The goal is to minimize the total expected regret after all rounds within a limited budget. Existing techniques in this literature either fix the budget per round or fix the number of arms pulled in each round. Our setting is more general where based on the remaining budget and remaining number of rounds, the algorithm can decide how many arms to be pulled in each round. First, we propose CBwK-Greedy-UCB algorithm, which uses a greedy technique, CBwK-Greedy, to allocate the arms to the rounds. Next, we propose a reduction of this problem to Bandits with Knapsacks (BwK) with a single pull. With this reduction, we propose CBwK-LPUCB that uses PrimalDualBwK ingeniously. We rigorously prove regret bounds for CBwK-LP-UCB. We experimentally compare the two algorithms and observe that CBwK-Greedy-UCB performs incrementally better than CBwK-LP-UCB. We also show that for very high budgets, the regret goes to zero.
• Abstract（参考訳）: 各ラウンドにおいて、アルゴリズムは1つ以上のアームからなるスーパーアームを選択する。 目標は、限られた予算内ですべてのラウンドを終えて、期待される総後悔を最小限に抑えることだ。 この文献の既存の技術は、1ラウンドあたりの予算を固定するか、各ラウンドで引き出された武器の数を固定する。 我々の設定はより一般的であり、残りの予算と残りのラウンド数に基づいて、アルゴリズムは各ラウンドで何個のアームを引くかを決定することができる。 まず, CBwK-Greedy-UCBアルゴリズムを提案する。 次に,この問題を単一プルでKnapsacks (BwK) を用いた Bandits に還元する手法を提案する。 そこで本研究ではPrimalDualBwKを用いたCBwK-LPUCBを提案する。 我々はCBwK-LP-UCBに対する後悔の限界を厳格に証明する。 2つのアルゴリズムを実験的に比較し,CBwK-Greedy-UCBがCBwK-LP-UCBよりも漸進的に優れた性能を発揮することを示した。 また、非常に高い予算で、後悔はゼロになることも示しています。

関連論文リスト

• Adversarial Combinatorial Bandits with Switching Costs [55.2480439325792]
  本稿では,各ラウンドで選択したアームのスイッチに対して,切替コストが$lambda$の逆帯域問題について検討する。 ミニマックスの後悔とそれにアプローチするための設計アルゴリズムの限界を低くする。
  論文  参考訳（メタデータ） (2024-04-02T12:15:37Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• Batch-Size Independent Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms or Independent Arms [59.8188496313214]
  半帯域 (CMAB) について検討し, 半帯域 (CMAB) におけるバッチサイズ (K$) の依存性の低減に着目した。 まず,確率的に引き起こされるアーム(CMAB-T)を用いたCMABの設定に対して,分散を考慮した信頼区間を持つBCUCB-Tアルゴリズムを提案する。 次に,独立アームを用いた非トリガ型CMABの設定に対して,TPVM条件の非トリガ型を利用したSESCBアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-08-31T13:09:39Z)
• Achieving the Pareto Frontier of Regret Minimization and Best Arm Identification in Multi-Armed Bandits [91.8283876874947]
  本稿では,BoBW-lil'UCB$(gamma)$アルゴリズムの設計と解析を行う。 i) RMとBAIの両方の目的に対して最適なアルゴリズムを同時に実行できないことを示す。 また、BoBW-lil'UCB$(gamma)$は、時間複雑性と後悔の点で競合よりも優れていることを示す。
  論文  参考訳（メタデータ） (2021-10-16T17:52:32Z)
• Contextual Combinatorial Volatile Bandits via Gaussian Processes [10.312968200748116]
  利用可能なベースアームのセットとそのコンテキストによるコンテキスト的バンディット問題を考える。 我々は,カーネル上信頼境界(O'CLOK-UCB)を用いた最適組合せ学習と最適化というアルゴリズムを提案する。 両アルゴリズムが従来のUTBベースのアルゴリズムを現実的な設定で大幅に上回っていることを実験的に示す。
  論文  参考訳（メタデータ） (2021-10-05T18:02:10Z)
• Upper Confidence Bounds for Combining Stochastic Bandits [52.10197476419621]
  バンディットアルゴリズムを結合する簡単な手法を提案する。 私たちのアプローチは、個々のbanditアルゴリズムのそれぞれを、より高いレベルのn$-armed bandit問題のアームとして扱う"meta-ucb"手順に基づいています。
  論文  参考訳（メタデータ） (2020-12-24T05:36:29Z)
• The Unreasonable Effectiveness of Greedy Algorithms in Multi-Armed Bandit with Many Arms [10.662105162882526]
  本研究は,Emphmany-armed regimeにおける$k$-armed bandit問題について考察する。 以上の結果から,多腕の環境下での強欲なアルゴリズムには,新たなエフェフリー探索法が有用であることが示唆された。
  論文  参考訳（メタデータ） (2020-02-24T08:59:34Z)
• Bandits with Knapsacks beyond the Worst-Case [87.54497614804409]
  最悪の場合の視点を超えた3つの結果を提示します。 第一に、対数的、インスタンス依存的後悔率の完全な特徴を与える上限と下限を提供する。 第二に、与えられたラウンドにおけるアルゴリズムの性能を追跡するBwKの「簡単な後悔」を考察し、数ラウンドを除いては小さくないことを示す。
  論文  参考訳（メタデータ） (2020-02-01T18:50:44Z)

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

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