論文の概要: Contextual Blocking Bandits
- arxiv url: http://arxiv.org/abs/2003.03426v2
- Date: Wed, 17 Jun 2020 11:36:37 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-26 00:54:30.860710
- Title: Contextual Blocking Bandits
- Title（参考訳）: コンテキストブロックバンド
- Authors: Soumya Basu, Orestis Papadigenopoulos, Constantine Caramanis, Sanjay
Shakkottai
- Abstract要約: 我々は,多腕バンディット問題の新たな変種について検討し,各ステップごとに,腕の平均報酬を決定する独立したサンプルコンテキストをプレイヤーが観察する。
アームを再生することで(すべてのコンテキストにわたって)将来の時間ステップの固定および既知の回数をブロックする。
我々は、$mathcalO(log T)$-regret w.r.t.$alpha$regret戦略を$Tタイムステップで保証し、$Omega(log(T)$low boundと一致する UCB ベースのフル情報アルゴリズムの変種を提案する。
- 参考スコア（独自算出の注目度）: 35.235375147227124
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study a novel variant of the multi-armed bandit problem, where at each
time step, the player observes an independently sampled context that determines
the arms' mean rewards. However, playing an arm blocks it (across all contexts)
for a fixed and known number of future time steps. The above contextual
setting, which captures important scenarios such as recommendation systems or
ad placement with diverse users, invalidates greedy solution techniques that
are effective for its non-contextual counterpart (Basu et al., NeurIPS19).
Assuming knowledge of the context distribution and the mean reward of each
arm-context pair, we cast the problem as an online bipartite matching problem,
where the right-vertices (contexts) arrive stochastically and the left-vertices
(arms) are blocked for a finite number of rounds each time they are matched.
This problem has been recently studied in the full-information case, where
competitive ratio bounds have been derived. We focus on the bandit setting,
where the reward distributions are initially unknown; we propose a UCB-based
variant of the full-information algorithm that guarantees a $\mathcal{O}(\log
T)$-regret w.r.t. an $\alpha$-optimal strategy in $T$ time steps, matching the
$\Omega(\log(T))$ regret lower bound in this setting. Due to the time
correlations caused by blocking, existing techniques for upper bounding regret
fail. For proving our regret bounds, we introduce the novel concepts of delayed
exploitation and opportunistic subsampling and combine them with ideas from
combinatorial bandits and non-stationary Markov chains coupling.
- Abstract（参考訳）: 我々は,多腕バンディット問題の新たな変種について検討し,各ステップごとに,腕の平均報酬を決定する独立したサンプルコンテキストをプレイヤーが観察する。
しかし、アームの演奏は(すべてのコンテキストにわたって)将来の時間ステップの固定および既知の回数でブロックする。
上記のコンテキスト設定は、レコメンデーションシステムや多様なユーザによる広告配置といった重要なシナリオをキャプチャし、その非コンテキスト対応(basu et al., neurips19)に有効な欲張りなソリューション技術を無効にする。
文脈分布の知識と各アーム-コンテキストペアの平均報酬を仮定すると、問題はオンラインの2部マッチング問題として、右バーチス(コンテキスト)が確率的に到着し、左バーチス(アーム)がマッチするたびに有限個のラウンドのためにブロックされる。
この問題は、競争比率の限界が導かれるフルインフォメーションのケースで近年研究されている。
我々は、当初報酬分布が不明なバンディット設定に注目し、$\omega(\log(t))$ regretlowboundに一致する$\mathcal{o}(\log t)$-regret w.r.t.$\alpha$-optimal strategyを$t$時間ステップで保証する全情報アルゴリズムのucbベースの変種を提案する。
ブロックによって引き起こされる時間的相関が原因で、既存のオーバーバウンディング後悔のテクニックは失敗する。
後悔の限界を証明するために、我々は、遅れた搾取と機会主義的なサブサンプリングという新しい概念を導入し、これらを組合せの包帯と非定常マルコフ連鎖結合のアイデアと組み合わせる。
関連論文リスト
- Bridging Rested and Restless Bandits with Graph-Triggering: Rising and Rotting [67.1631453378926]
Graph-Triggered Banditsは、安静と安静のバンディットを一般化するフレームワークである。
本研究は,2種類の単調包帯に焦点をあてる: 立ち上がり, 腕の期待される報酬が増加する, 引き金の数が増える, 回転する, 反対の行動が起こる。
論文 参考訳（メタデータ） (2024-09-09T18:23:07Z) - A General Framework for Clustering and Distribution Matching with Bandit Feedback [81.50716021326194]
我々は,帯域幅フィードバックを用いたクラスタリングと分散マッチング問題のための一般的なフレームワークを開発する。
誤り確率が$delta$を超えない任意のオンラインアルゴリズムに対して、平均アームプル数に基づいて漸近的でない下界を導出する。
論文 参考訳（メタデータ） (2024-09-08T12:19:12Z) - Feel-Good Thompson Sampling for Contextual Dueling Bandits [49.450050682705026]
FGTS.CDBという名前のトンプソンサンプリングアルゴリズムを提案する。
われわれのアルゴリズムの核心は、デュエルバンディットに適した新しいFeel-Good探索用語である。
我々のアルゴリズムは最小限の誤差、すなわち $tildemathcalO(dsqrt T)$, $d$ はモデル次元、$T$ は時間水平線である。
論文 参考訳（メタデータ） (2024-04-09T04:45:18Z) - Optimal cross-learning for contextual bandits with unknown context
distributions [28.087360479901978]
本稿では,バルセイロ等のクロスラーニング環境において,文脈的包括的アルゴリズムを設計する際の問題点について考察する。
コンテクスト数によらずに$widetildeO(sqrtTK)$というほぼ厳密な(対数的要因まで)後悔境界を持つ効率的なアルゴリズムを提供する。
アルゴリズムのコアとなるのは,複数のエポックにまたがるアルゴリズムの実行をコーディネートする新しい手法である。
論文 参考訳（メタデータ） (2024-01-03T18:02:13Z) - Best-of-Both-Worlds Linear Contextual Bandits [45.378265414553226]
本研究は, 対向汚職下での多武装盗賊問題の事例である$K$腕線形文脈盗賊の問題を考察する。
我々は,理論的保証のもと,双方の敵環境に有効な戦略を開発する。
両体制の理論的保証から,我々の戦略をBest-of-Both-Worlds (BoBW) RealFTRLと呼んでいる。
論文 参考訳（メタデータ） (2023-12-27T09:32:18Z) - 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) - Combinatorial Blocking Bandits with Stochastic Delays [33.65025386998747]
最近の研究は、各腕の報酬が最後の引き抜きから経過した時間の特別な機能であるマルチアームバンディット問題の自然変化を考察している。
本研究では, 上記のモデルを2つの方向に拡張する。 (i) 各ラウンドで複数の腕を演奏できる汎用的な設定を, 実現可能性制約の下で検討する。
我々は、利用可能な(非ブロック化された)アームの中で、常に最大で期待される報酬を再生する自然な欲求部分集合の近似を厳密に分析する。
腕の期待報酬が不明な場合、上記のアルゴリズムを盗賊に適応させる。
論文 参考訳（メタデータ） (2021-05-22T02:46:04Z) - Recurrent Submodular Welfare and Matroid Blocking Bandits [22.65352007353614]
最近の研究は、マルチアームバンディット問題(MAB)の研究に焦点をあてている。
我々は、任意のマトロイドに対して$ (1 - frac1e)$-approximation を得ることのできる新しいアルゴリズムのアイデアを開発した。
鍵となる要素は、相関的な(インターリーブされた)スケジューリング技術である。
論文 参考訳（メタデータ） (2021-01-30T21:51:47Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z) - The Unreasonable Effectiveness of Greedy Algorithms in Multi-Armed Bandit with Many Arms [10.662105162882526]
本研究は,Emphmany-armed regimeにおける$k$-armed bandit問題について考察する。
以上の結果から,多腕の環境下での強欲なアルゴリズムには,新たなエフェフリー探索法が有用であることが示唆された。
論文 参考訳（メタデータ） (2020-02-24T08:59:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。