論文の概要: Contextual Combinatorial Bandits with Probabilistically Triggered Arms
- arxiv url: http://arxiv.org/abs/2303.17110v2
- Date: Wed, 14 Jun 2023 09:00:10 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-17 01:39:07.032566
- Title: Contextual Combinatorial Bandits with Probabilistically Triggered Arms
- Title（参考訳）: 確率的トリガーアームを用いた文脈組合せ帯域
- Authors: Xutong Liu, Jinhang Zuo, Siwei Wang, John C.S. Lui, Mohammad
Hajiesmaili, Adam Wierman, Wei Chen
- Abstract要約: 確率的に誘発される腕(C$2$MAB-T)を様々な滑らかさ条件下で検討した。
トリガー変調 (TPM) 条件の下では、C$2$-UC-Tアルゴリズムを考案し、後悔すべき$tildeO(dsqrtT)$を導出する。
- 参考スコア（独自算出の注目度）: 45.305256056479045
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study contextual combinatorial bandits with probabilistically triggered
arms (C$^2$MAB-T) under a variety of smoothness conditions that capture a wide
range of applications, such as contextual cascading bandits and contextual
influence maximization bandits. Under the triggering probability modulated
(TPM) condition, we devise the C$^2$-UCB-T algorithm and propose a novel
analysis that achieves an $\tilde{O}(d\sqrt{KT})$ regret bound, removing a
potentially exponentially large factor $O(1/p_{\min})$, where $d$ is the
dimension of contexts, $p_{\min}$ is the minimum positive probability that any
arm can be triggered, and batch-size $K$ is the maximum number of arms that can
be triggered per round. Under the variance modulated (VM) or triggering
probability and variance modulated (TPVM) conditions, we propose a new
variance-adaptive algorithm VAC$^2$-UCB and derive a regret bound
$\tilde{O}(d\sqrt{T})$, which is independent of the batch-size $K$. As a
valuable by-product, our analysis technique and variance-adaptive algorithm can
be applied to the CMAB-T and C$^2$MAB setting, improving existing results there
as well. We also include experiments that demonstrate the improved performance
of our algorithms compared with benchmark algorithms on synthetic and
real-world datasets.
- Abstract（参考訳）: 本研究では,コンテキストカスケードバンドや文脈影響最大化バンドなど,幅広い応用を捉えた様々な平滑性条件下で,確率的トリガアーム(c$^2$mab-t)を用いたコンテクストコンビネートバンドの研究を行った。
トリガリング確率変調 (TPM) 条件の下では、C$^2$-UCB-T アルゴリズムを考案し、$\tilde{O}(d\sqrt{KT})$ regret bound を達成する新しい解析法を提案し、潜在的に指数関数的に大きな因子である $O(1/p_{\min})$ を除去し、$d$ は文脈の次元であり、$p_{\min}$ は任意のアームをトリガできる最小の正の確率であり、バッチサイズ $K$ はラウンド毎にトリガできる最大のアーム数である。
分散変調 (vm) またはトリガー確率および分散変調 (tpvm) 条件の下で, 分散適応アルゴリズム vac$^2$-ucb を提案し, バッチサイズの $k$ とは独立な, 後悔の束縛 $\tilde{o}(d\sqrt{t})$ を導出する。
価値ある副産物として,cmab-t および c$^2$mab 設定に解析手法と分散適応アルゴリズムを適用し,既存の結果も改善した。
合成および実世界のデータセットのベンチマークアルゴリズムと比較して,アルゴリズムの性能向上を示す実験も含んでいる。
関連論文リスト
- Combinatorial Logistic Bandits [30.829239785016934]
我々はロジスティック・バンディット(CLogB)と呼ばれる新しいフレームワークを紹介する。
各ラウンドでは、ベースアームのサブセット(スーパーアームと呼ばれる)が選択され、各ベースアームの結果はバイナリとなる。
実世界のデータセットの実験では、ベンチマークアルゴリズムと比較してアルゴリズムの性能が優れていた。
論文 参考訳（メタデータ） (2024-10-22T14:52:46Z) - Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳（メタデータ） (2023-12-13T11:08:25Z) - Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement
Learning: Adaptivity and Computational Efficiency [90.40062452292091]
本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。
我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。
また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-02-21T00:17:24Z) - Batch-Size Independent Regret Bounds for Combinatorial Semi-Bandits with
Probabilistically Triggered Arms or Independent Arms [53.89752069984382]
半帯域 (CMAB) について検討し, 半帯域 (CMAB) におけるバッチサイズ (K$) の依存性の低減に着目した。
まず,確率的に引き起こされるアーム(CMAB-T)を用いたCMABの設定に対して,分散を考慮した信頼区間を持つBCUCB-Tアルゴリズムを提案する。
次に,独立アームを用いた非トリガ型CMABの設定に対して,TPVM条件の非トリガ型を利用したSESCBアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-08-31T13:09:39Z) - Adversarially Robust Multi-Armed Bandit Algorithm with
Variance-Dependent Regret Bounds [34.37963000493442]
本稿では,マルチアーム・バンディット(MAB)問題について考察し,両対向的条件下でほぼ最適に機能する,新たなベスト・オブ・ボス・ワールド(BOBW)アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-06-14T12:58:46Z) - Contextual Combinatorial Volatile Bandits via Gaussian Processes [10.312968200748116]
利用可能なベースアームのセットとそのコンテキストによるコンテキスト的バンディット問題を考える。
我々は,カーネル上信頼境界(O'CLOK-UCB)を用いた最適組合せ学習と最適化というアルゴリズムを提案する。
両アルゴリズムが従来のUTBベースのアルゴリズムを現実的な設定で大幅に上回っていることを実験的に示す。
論文 参考訳（メタデータ） (2021-10-05T18:02:10Z) - Problem Dependent View on Structured Thresholding Bandit Problems [73.70176003598449]
我々は、Thresholding Bandit problem (TBP)における問題依存体制について検討する。
学習者の目的は、シーケンシャルゲームの終わりに、所定のしきい値を超える手段を持つアームセットを出力することである。
コンケーブ設定と単調設定の両方で誤差の確率を上下に設定する。
論文 参考訳（メタデータ） (2021-06-18T15:01:01Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。