論文の概要: Contextual Combinatorial Volatile Bandits via Gaussian Processes
- arxiv url: http://arxiv.org/abs/2110.02248v1
- Date: Tue, 5 Oct 2021 18:02:10 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-07 14:34:25.774151
- Title: Contextual Combinatorial Volatile Bandits via Gaussian Processes
- Title（参考訳）: ガウス過程による文脈的組合せ揮発性帯域
- Authors: Andi Nika, Sepehr Elahi, Cem Tekin
- Abstract要約: 利用可能なベースアームのセットとそのコンテキストによるコンテキスト的バンディット問題を考える。
我々は,カーネル上信頼境界(O'CLOK-UCB)を用いた最適組合せ学習と最適化というアルゴリズムを提案する。
両アルゴリズムが従来のUTBベースのアルゴリズムを現実的な設定で大幅に上回っていることを実験的に示す。
- 参考スコア（独自算出の注目度）: 10.312968200748116
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider a contextual bandit problem with a combinatorial action set and
time-varying base arm availability. At the beginning of each round, the agent
observes the set of available base arms and their contexts and then selects an
action that is a feasible subset of the set of available base arms to maximize
its cumulative reward in the long run. We assume that the mean outcomes of base
arms are samples from a Gaussian Process indexed by the context set ${\cal X}$,
and the expected reward is Lipschitz continuous in expected base arm outcomes.
For this setup, we propose an algorithm called Optimistic Combinatorial
Learning and Optimization with Kernel Upper Confidence Bounds (O'CLOK-UCB) and
prove that it incurs $\tilde{O}(K\sqrt{T\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 cardinality of any feasible action over all
rounds. To dramatically speed up the algorithm, we also propose a variant of
O'CLOK-UCB that uses sparse GPs. Finally, we experimentally show that both
algorithms exploit inter-base arm outcome correlation and vastly outperform the
previous state-of-the-art UCB-based algorithms in realistic setups.
- Abstract（参考訳）: 組み合わせ動作セットと時変ベースアームの可利用性を考慮した文脈的帯域幅問題を考える。
各ラウンドの開始時に、エージェントは利用可能なベースアームとそのコンテキストのセットを観察し、その後に利用可能なベースアームのセットの実行可能なサブセットであるアクションを選択し、長期の累積報酬を最大化する。
ベースアームの平均結果は、文脈集合 ${\cal x}$ でインデックスづけされたガウス過程のサンプルであり、期待される報酬は期待ベースアーム結果においてリプシッツ連続であると仮定する。
この設定のために、カーネル・アッパー信頼境界(O'CLOK-UCB)を用いたOptimistic Combinatorial Learning and Optimization(O'CLOK-UCB)と呼ばれるアルゴリズムを提案し、それが$\tilde{O}(K\sqrt{T\overline{\gamma}_{T}} )$ regret with high probability, where $\overline{\gamma}_{T}$は、最初の$T$ラウンドに出現したベースアームコンテキストのセットに関連する最大情報ゲインであり、$K$はすべてのラウンドにおける実行可能なアクションの最大値であることを示す。
アルゴリズムを劇的に高速化するために,スパースGPを用いたO'CLOK-UCBの変種を提案する。
最後に,両アルゴリズムがベース間arm結果相関を生かして,従来のucbベースのアルゴリズムをリアルなセットアップで圧倒的に上回ることを示す。
関連論文リスト
- Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳（メタデータ） (2023-12-13T11:08:25Z) - 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) - 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) - Contextual Combinatorial Multi-output GP Bandits with Group Constraints [11.317136648551537]
連合型多武装バンディット問題では、クライアントを保護するための最小限のプライバシー要件を満たしながら、世界的報酬を最大化することが主な目標である。
我々は、グループやアクションセットの変更によるコンテキスト的バンディットの設定を検討し、そこでは、類似のベースアームがグループに到着し、スーパーアームと呼ばれるベースアームのセットが各ラウンドで選択され、スーパーアームの報酬を最大化し、ベースアームが選択されたグループの報酬の制約を満たす。
次に、累積スーパーアーム報酬の最大化と充足のバランスをとる、Thresholded Combinatored upper Confidence Bounds (TCGP-UCB)と呼ばれる新しい二重UCBGPバンドアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-11-29T18:39:09Z) - Sleeping Combinatorial Bandits [15.004764451770441]
睡眠帯域設定においてよく知られたCUCBアルゴリズムを適用し,それをCSUCBと呼ぶ。
穏やかな条件下では、CSUCBアルゴリズムが$O(sqrtT log (T)$ instance-dependent regret guaranteeを達成することを証明します。
我々の結果は極めて一般的なものであり、非付加的な報酬関数、揮発性アームの可用性、引くべきベースアームの変動数など、実用的な応用によって生じる一般的な環境下で維持されます。
論文 参考訳（メタデータ） (2021-06-03T06:49:44Z) - 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) - 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) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。