論文の概要: Batch-Size Independent Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms or Independent Arms

• arxiv url: http://arxiv.org/abs/2208.14837v3
• Date: Mon, 18 Nov 2024 17:30:05 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-20 13:34:53.379931
• Title: Batch-Size Independent Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms or Independent Arms
• Title（参考訳）: 確率的トリガーアームと独立アームを併用したコンビニアルセミバンドのバッチサイズ独立レグレットバウンド
• Authors: Xutong Liu, Jinhang Zuo, Siwei Wang, Carlee Joe-Wong, John C. S. Lui, Wei Chen,
• Abstract要約: 半帯域 (CMAB) について検討し, 半帯域 (CMAB) におけるバッチサイズ (K$) の依存性の低減に着目した。 まず,確率的に引き起こされるアーム(CMAB-T)を用いたCMABの設定に対して,分散を考慮した信頼区間を持つBCUCB-Tアルゴリズムを提案する。 次に,独立アームを用いた非トリガ型CMABの設定に対して,TPVM条件の非トリガ型を利用したSESCBアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 59.8188496313214
• License:
• Abstract: In this paper, we study the combinatorial semi-bandits (CMAB) and focus on reducing the dependency of the batch-size $K$ in the regret bound, where $K$ is the total number of arms that can be pulled or triggered in each round. First, for the setting of CMAB with probabilistically triggered arms (CMAB-T), we discover a novel (directional) triggering probability and variance modulated (TPVM) condition that can replace the previously-used smoothness condition for various applications, such as cascading bandits, online network exploration and online influence maximization. Under this new condition, we propose a BCUCB-T algorithm with variance-aware confidence intervals and conduct regret analysis which reduces the $O(K)$ factor to $O(\log K)$ or $O(\log^2 K)$ in the regret bound, significantly improving the regret bounds for the above applications. Second, for the setting of non-triggering CMAB with independent arms, we propose a SESCB algorithm which leverages on the non-triggering version of the TPVM condition and completely removes the dependency on $K$ in the leading regret. As a valuable by-product, the regret analysis used in this paper can improve several existing results by a factor of $O(\log K)$. Finally, experimental evaluations show our superior performance compared with benchmark algorithms in different applications.
• Abstract（参考訳）: 本稿では,組み合わせセミバンド(CMAB)について検討し,各ラウンドで引き出すことができる腕の総数としてK$のバッチサイズのK$の依存性を低減することに焦点をあてる。 まず,確率的に引き起こされるアーム(CMAB-T)を用いたCMABの設定において,カスケードバンド,オンラインネットワーク探索,オンライン影響の最大化など,従来使用されていたスムーズな条件に取って代わる,新しい(方向性)トリガの確率と分散変調(TPVM)条件を発見する。 この新たな条件下では、分散対応の信頼区間を持つBCUCB-Tアルゴリズムを提案し、上記のアプリケーションに対する後悔境界を大幅に改善し、$O(K)$係数を$O(\log K)$または$O(\log^2K)$に還元する。 第2に,非トリガリングCMABを独立したアームで設定するために,TPVM条件の非トリガバージョンを利用したSESCBアルゴリズムを提案する。 貴重な副産物として、本論文で用いた後悔分析は、$O(\log K)$の因子によって、いくつかの既存の結果を改善することができる。 最後に, 評価実験により, 異なるアプリケーションにおけるベンチマークアルゴリズムと比較して, 優れた性能を示した。

関連論文リスト

• Fixed-Budget Differentially Private Best Arm Identification [62.36929749450298]
  差分プライバシー制約下における固定予算制度における線形包帯のベストアーム識別(BAI)について検討した。 誤差確率に基づいてミニマックス下限を導出し、下限と上限が指数関数的に$T$で崩壊することを示した。
  論文  参考訳（メタデータ） (2024-01-17T09:23:25Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
  本稿では, 一般化線形モデル(GLM)から, デュエルアームのバイナリ比較を生成するコンテキストデュエルバンド問題について検討する。 本稿では,SupLinUCB型アルゴリズムを提案する。このアルゴリズムは,計算効率と分散を意識したリセットバウンド$tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$を提案する。 我々の後悔は、比較が決定論的である場合の直感的な期待と自然に一致し、アルゴリズムは$tilde O(d)$ regretにのみ悩まされる。
  論文  参考訳（メタデータ） (2023-10-02T08:15:52Z)
• Multi-Fidelity Multi-Armed Bandits Revisited [46.19926456682379]
  我々は,MF-MAB(Multi-fidelity multi-armed bandit)問題の拡張であるMF-MAB(Multi-fidelity multi-armed bandit)について検討した。 MF-MABは、各アームを異なるコスト(忠実さ)と観察精度で引っ張ることができる。
  論文  参考訳（メタデータ） (2023-06-13T13:19:20Z)
• Combinatorial Bandits for Maximum Value Reward Function under Max Value-Index Feedback [9.771002043127728]
  本稿では,最大値報酬関数に対する最大値と指数フィードバックに基づくマルチアームバンディット問題を考察する。 有限なサポートを持つ任意の分布にしたがって、アーム結果を持つ問題インスタンスに対して、アルゴリズムを提案し、後悔の束縛を与える。 我々のアルゴリズムは、$O(((k/Delta)log(T))$ distribution-dependent と $tildeO(sqrtT)$ distribution-independent regret を達成する。
  論文  参考訳（メタデータ） (2023-05-25T14:02:12Z)
• Contextual Combinatorial Bandits with Probabilistically Triggered Arms [45.305256056479045]
  確率的に誘発される腕(C$2$MAB-T)を様々な滑らかさ条件下で検討した。 トリガー変調 (TPM) 条件の下では、C$2$-UC-Tアルゴリズムを考案し、後悔すべき$tildeO(dsqrtT)$を導出する。
  論文  参考訳（メタデータ） (2023-03-30T02:51:00Z)
• Adversarially Robust Multi-Armed Bandit Algorithm with Variance-Dependent Regret Bounds [34.37963000493442]
  本稿では,マルチアーム・バンディット(MAB)問題について考察し,両対向的条件下でほぼ最適に機能する,新たなベスト・オブ・ボス・ワールド(BOBW)アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-06-14T12:58:46Z)
• 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)

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

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