論文の概要: Contextual Combinatorial Multi-output GP Bandits with Group Constraints
- arxiv url: http://arxiv.org/abs/2111.14778v2
- Date: Mon, 10 Jul 2023 15:11:08 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-11 19:44:40.136135
- Title: Contextual Combinatorial Multi-output GP Bandits with Group Constraints
- Title（参考訳）: グループ制約付きコンテキスト組合せ多出力GP帯域
- Authors: Sepehr Elahi, Baran Atalar, Sevda \"O\u{g}\"ut, Cem Tekin
- Abstract要約: 連合型多武装バンディット問題では、クライアントを保護するための最小限のプライバシー要件を満たしながら、世界的報酬を最大化することが主な目標である。
我々は、グループやアクションセットの変更によるコンテキスト的バンディットの設定を検討し、そこでは、類似のベースアームがグループに到着し、スーパーアームと呼ばれるベースアームのセットが各ラウンドで選択され、スーパーアームの報酬を最大化し、ベースアームが選択されたグループの報酬の制約を満たす。
次に、累積スーパーアーム報酬の最大化と充足のバランスをとる、Thresholded Combinatored upper Confidence Bounds (TCGP-UCB)と呼ばれる新しい二重UCBGPバンドアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 11.317136648551537
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In federated multi-armed bandit problems, maximizing global reward while
satisfying minimum privacy requirements to protect clients is the main goal. To
formulate such problems, we consider a combinatorial contextual bandit setting
with groups and changing action sets, where similar base arms arrive in groups
and a set of base arms, called a super arm, must be chosen in each round to
maximize super arm reward while satisfying the constraints of the rewards of
groups from which base arms were chosen. To allow for greater flexibility, we
let each base arm have two outcomes, modeled as the output of a two-output
Gaussian process (GP), where one outcome is used to compute super arm reward
and the other for group reward. We then propose a novel double-UCB GP-bandit
algorithm, called Thresholded Combinatorial Gaussian Process Upper Confidence
Bounds (TCGP-UCB), which balances between maximizing cumulative super arm
reward and satisfying group reward constraints and can be tuned to prefer one
over the other. We also define a new notion of regret that combines super arm
regret with group reward constraint satisfaction and prove that TCGP-UCB incurs
$\tilde{O}(\sqrt{\lambda^*(K)KT\overline{\gamma}_{T}} )$ regret with high
probability, where $\overline{\gamma}_{T}$ is the maximum information gain
associated with the set of base arm contexts that appeared in the first $T$
rounds and $K$ is the maximum super arm cardinality over all rounds. We lastly
show in experiments using synthetic and real-world data and based on a
federated learning setup as well as a content-recommendation one that our
algorithm performs better then the current non-GP state-of-the-art
combinatorial bandit algorithm, while satisfying group constraints.
- Abstract（参考訳）: フェデレーテッド・マルチアームド・バンディット問題では、クライアントを保護するために最小限のプライバシー要件を満たしながら、グローバルな報酬を最大化することが主な目標である。
このような問題を定式化するために、グループとアクションセットの変更による組合せ的文脈的バンディットの設定を考える。そこでは、類似のベースアームがグループに到着し、スーパーアームと呼ばれるベースアームのセットが各ラウンドで選択され、ベースアームが選択されたグループの報酬の制約を満たすとともに、スーパーアーム報酬を最大化する。
柔軟性を高めるために、各ベースアームは2出力ガウス過程(GP)の出力としてモデル化され、1つの結果がスーパーアーム報酬の計算に使われ、もう1つの結果がグループ報酬の計算に使用される。
次に、累積スーパーアーム報酬の最大化とグループ報酬制約の充足のバランスを保ち、他方よりも優先するように調整できる、Thresholded Combinatorial Gaussian Process Upper Confidence Bounds (TCGP-UCB)と呼ばれる新しい二重UCBGPバンドアルゴリズムを提案する。
TCGP-UCB が $\tilde{O}(\sqrt{\lambda^*(K)KT\overline{\gamma}_{T}} )$ regret with high probability, ここで $\overline{\gamma}_{T}$ は、最初の$T$ラウンドで出現したベースアームコンテキストの集合に関連する最大情報ゲインであり、$K$ は全ラウンドにおける最大スーパーアーム定数であることを示す。
最後に,合成および実世界のデータを用いた実験を行い,グループ制約を満たしながら,現在の非gp型コンビネータ型バンディットアルゴリズムよりも優れた結果が得られるような,コンテント・レコンメンデーション設定に基づく。
関連論文リスト
- Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳（メタデータ） (2023-12-13T11:08:25Z) - Max-Quantile Grouped Infinite-Arm Bandits [39.7239093424124]
無限に多くの腕からなる群が多数存在するバンド問題。
本稿では,まず各グループから一定数のアームを要求し,次に有限腕グループ化された最大量子帯域幅アルゴリズムを実行する2段階アルゴリズムを提案する。
インスタンス依存と最悪のケースの後悔の両方を特徴付け、後者に一致する下位境界を提供します。
論文 参考訳（メタデータ） (2022-10-04T00:46:49Z) - Risk-Aware Algorithms for Combinatorial Semi-Bandits [7.716156977428555]
半帯域フィードバック下でのマルチアームバンディット問題について検討する。
本稿では,最悪の場合の報酬のみを考慮したリスク尺度であるCVaR(Conditional Value-at-Risk)の最大化の問題を検討する。
本稿では,バンディットのスーパーアームから得られる報酬のCVaRを最大化するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-12-02T11:29:43Z) - Max-Min Grouped Bandits [48.62520520818357]
マルチアームバンディット問題であるmax-min grouped banditsを導入する。
ゴールは、最悪の腕が最高の平均報酬を持つグループを見つけることです。
この問題はレコメンデーションシステムのようなアプリケーションには関心がある。
論文 参考訳（メタデータ） (2021-11-17T01:59:15Z) - Contextual Combinatorial Volatile Bandits via Gaussian Processes [10.312968200748116]
利用可能なベースアームのセットとそのコンテキストによるコンテキスト的バンディット問題を考える。
我々は,カーネル上信頼境界(O'CLOK-UCB)を用いた最適組合せ学習と最適化というアルゴリズムを提案する。
両アルゴリズムが従来のUTBベースのアルゴリズムを現実的な設定で大幅に上回っていることを実験的に示す。
論文 参考訳（メタデータ） (2021-10-05T18:02:10Z) - Top-$k$ eXtreme Contextual Bandits with Arm Hierarchy [71.17938026619068]
我々は、腕の総数が膨大であることができるトップ$ k$極端な文脈的包帯問題を研究します。
まず,Inverse Gap Weighting戦略を用いて,非極端に実現可能な設定のアルゴリズムを提案する。
我々のアルゴリズムは、$O(ksqrt(A-k+1)T log (|mathcalF|T))$である。
論文 参考訳（メタデータ） (2021-02-15T19:10:52Z) - Recurrent Submodular Welfare and Matroid Blocking Bandits [22.65352007353614]
最近の研究は、マルチアームバンディット問題(MAB)の研究に焦点をあてている。
我々は、任意のマトロイドに対して$ (1 - frac1e)$-approximation を得ることのできる新しいアルゴリズムのアイデアを開発した。
鍵となる要素は、相関的な(インターリーブされた)スケジューリング技術である。
論文 参考訳（メタデータ） (2021-01-30T21:51:47Z) - Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit
Feedback [51.21673420940346]
コンビナーシャルバンディットはマルチアームバンディットを一般化し、エージェントが腕のセットを選択し、選択したセットに含まれる各腕の騒々しい報酬を観察します。
我々は, 最善の腕を一定の信頼度で識別する純粋爆発問題と, 応答集合の構造が動作集合の1つと異なるような, より一般的な設定に注目する。
有限多面体に対するプロジェクションフリーオンライン学習アルゴリズムに基づいて、凸的に最適であり、競争力のある経験的性能を持つ最初の計算効率の良いアルゴリズムである。
論文 参考訳（メタデータ） (2021-01-21T10:35:09Z) - Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits
with Linear Payoff Functions [53.77572276969548]
我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。
一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-20T04:29:18Z) - Tight Lower Bounds for Combinatorial Multi-Armed Bandits [72.56064196252498]
Combinatorial Multi-Armed Bandit 問題は、エージェントが各ラウンドで一組の腕を選択する、シーケンシャルな意思決定問題である。
最近提案されたGini重み付き滑らか度パラメータが単調報酬関数の下限を決定することを示す。
論文 参考訳（メタデータ） (2020-02-13T08:53:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。