論文の概要: Batch-Size Independent Regret Bounds for Combinatorial Semi-Bandits with
Probabilistically Triggered Arms or Independent Arms
- arxiv url: http://arxiv.org/abs/2208.14837v1
- Date: Wed, 31 Aug 2022 13:09:39 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-01 12:56:48.179545
- 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アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 53.89752069984382
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- 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)条件を発見する。
この新たな条件下では,分散認識信頼区間を有するbcccb-tアルゴリズムを提案し,後悔度解析を行い,後悔度境界の$o(\log k)$ または $o(\log^2 k)$ を減少させ,上記のアプリケーションに対する後悔度を大幅に向上させる。
第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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。