論文の概要: Recurrent Submodular Welfare and Matroid Blocking Bandits
- arxiv url: http://arxiv.org/abs/2102.00321v1
- Date: Sat, 30 Jan 2021 21:51:47 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-04 10:13:26.903187
- Title: Recurrent Submodular Welfare and Matroid Blocking Bandits
- Title（参考訳）: 再発するサブモジュラ福祉とマトロイド遮断帯
- Authors: Orestis Papadigenopoulos and Constantine Caramanis
- Abstract要約: 最近の研究は、マルチアームバンディット問題(MAB)の研究に焦点をあてている。
我々は、任意のマトロイドに対して$ (1 - frac1e)$-approximation を得ることのできる新しいアルゴリズムのアイデアを開発した。
鍵となる要素は、相関的な(インターリーブされた)スケジューリング技術である。
- 参考スコア（独自算出の注目度）: 22.65352007353614
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: A recent line of research focuses on the study of the stochastic multi-armed
bandits problem (MAB), in the case where temporal correlations of specific
structure are imposed between the player's actions and the reward distributions
of the arms (Kleinberg and Immorlica [FOCS18], Basu et al. [NIPS19]). As
opposed to the standard MAB setting, where the optimal solution in hindsight
can be trivially characterized, these correlations lead to (sub-)optimal
solutions that exhibit interesting dynamical patterns -- a phenomenon that
yields new challenges both from an algorithmic as well as a learning
perspective. In this work, we extend the above direction to a combinatorial
bandit setting and study a variant of stochastic MAB, where arms are subject to
matroid constraints and each arm becomes unavailable (blocked) for a fixed
number of rounds after each play. A natural common generalization of the
state-of-the-art for blocking bandits, and that for matroid bandits, yields a
$(1-\frac{1}{e})$-approximation for partition matroids, yet it only guarantees
a $\frac{1}{2}$-approximation for general matroids. In this paper we develop
new algorithmic ideas that allow us to obtain a polynomial-time $(1 -
\frac{1}{e})$-approximation algorithm (asymptotically and in expectation) for
any matroid, and thus allow us to control the $(1-\frac{1}{e})$-approximate
regret. A key ingredient is the technique of correlated (interleaved)
scheduling. Along the way, we discover an interesting connection to a variant
of Submodular Welfare Maximization, for which we provide (asymptotically)
matching upper and lower approximability bounds.
- Abstract（参考訳）: 最近の研究は、プレイヤーの行動と腕の報酬分布(Kleinberg and Immorlica (FOCS18), Basu et al)の間に特定の構造の時間的相関が課される場合において、確率的マルチアームバンディット問題(MAB)の研究に焦点が当てられている。
[NIPS19])。
後視における最適解を自明に特徴づけることができる標準MAB設定とは対照的に、これらの相関は、興味深い動的パターンを示す(サブ)最適解へとつながります。
本研究では、上述の方向をコンビナトリアルなバンディット設定に拡張し、腕がマトロイド制約の対象となり、各腕が各プレイ後に一定数のラウンドに対して利用不能(ブロック)になる確率的MABの変種を研究する。
包帯をブロックするための最新式の自然な一般的な一般化であり、マトロイド包帯に対しては$(1-\frac{1}{e})$-approximation for partition matroidsとなるが、一般には$\frac{1}{2}$-approximation for general matroidsのみを保証する。
本稿では,任意のマトロイドに対して多項式時間$(1-\frac{1}{e})$近似アルゴリズム(漸近的および期待的)を得ることを可能にする新しいアルゴリズムアイデアを開発し,$(1-\frac{1}{e})$-approximate regretの制御を可能にした。
重要な成分は、相関(インターリーブ)スケジューリングの技術です。
その過程で、我々は(非対称的に)上下の近似性境界に一致するサブモジュラ福祉最大化の変種への興味深い接続を発見します。
関連論文リスト
- A General Framework for Clustering and Distribution Matching with Bandit Feedback [81.50716021326194]
我々は,帯域幅フィードバックを用いたクラスタリングと分散マッチング問題のための一般的なフレームワークを開発する。
誤り確率が$delta$を超えない任意のオンラインアルゴリズムに対して、平均アームプル数に基づいて漸近的でない下界を導出する。
論文 参考訳（メタデータ） (2024-09-08T12:19:12Z) - Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳（メタデータ） (2023-12-13T11:08:25Z) - Contextual Combinatorial Bandits with Probabilistically Triggered Arms [55.9237004478033]
確率的に誘発される腕(C$2$MAB-T)を様々な滑らかさ条件下で検討した。
トリガー変調 (TPM) 条件の下では、C$2$-UC-Tアルゴリズムを考案し、後悔すべき$tildeO(dsqrtT)$を導出する。
論文 参考訳（メタデータ） (2023-03-30T02:51:00Z) - Complexity Analysis of a Countable-armed Bandit Problem [9.163501953373068]
遊びの地平線上で期待される累積的後悔を最小限に抑えるという古典的問題を考察する。
我々は、$K=2$のとき、$mathcalOleft(log n right)$の率最適有限時間インスタンス依存後悔を実現するアルゴリズムを提案する。
問題に対する後悔の順序と複雑さは、古典的MAB問題と非常に類似していることを示しているが、アルゴリズム設計における性能境界の特性と健全な側面は、後者とはかなり異なる。
論文 参考訳（メタデータ） (2023-01-18T00:53:46Z) - Stochastic Rising Bandits [40.32303434592863]
本研究は、腕が単調に非減少している、安静時および安静時バンディットの特定の症例について検討する。
この特性により、ペイオフの規則性を利用して、厳密な後悔の限界を提供する、特別に構築されたアルゴリズムを設計することができる。
我々は,本アルゴリズムを実世界のデータセットに対するオンラインモデル選択問題や,複数の合成されたタスクに対する非定常MABの最先端手法と経験的に比較した。
論文 参考訳（メタデータ） (2022-12-07T17:30:45Z) - On Submodular Contextual Bandits [92.45432756301231]
作用が基底集合の部分集合であり、平均報酬が未知の単調部分モジュラ函数によってモデル化されるような文脈的包帯の問題を考える。
Inverse Gap Weighting 戦略により,提案アルゴリズムは推定関数の局所的最適度を効率よくランダム化することを示す。
論文 参考訳（メタデータ） (2021-12-03T21:42:33Z) - Combinatorial Blocking Bandits with Stochastic Delays [33.65025386998747]
最近の研究は、各腕の報酬が最後の引き抜きから経過した時間の特別な機能であるマルチアームバンディット問題の自然変化を考察している。
本研究では, 上記のモデルを2つの方向に拡張する。 (i) 各ラウンドで複数の腕を演奏できる汎用的な設定を, 実現可能性制約の下で検討する。
我々は、利用可能な(非ブロック化された)アームの中で、常に最大で期待される報酬を再生する自然な欲求部分集合の近似を厳密に分析する。
腕の期待報酬が不明な場合、上記のアルゴリズムを盗賊に適応させる。
論文 参考訳（メタデータ） (2021-05-22T02:46:04Z) - 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) - Stochastic Linear Bandits Robust to Adversarial Attacks [117.665995707568]
我々はロバスト位相除去アルゴリズムの2つの変種を提供し、その1つは$C$を知っており、もう1つはそうでない。
いずれの変種も、倒壊しない場合には、それぞれ$C = 0$ となり、それぞれ追加の加法項が生じる。
文脈的設定では、単純な欲求的アルゴリズムは、明示的な探索を行わず、C$を知らないにもかかわらず、ほぼ最適加法的後悔項で証明可能な堅牢性を示す。
論文 参考訳（メタデータ） (2020-07-07T09:00:57Z) - Contextual Blocking Bandits [35.235375147227124]
我々は,多腕バンディット問題の新たな変種について検討し,各ステップごとに,腕の平均報酬を決定する独立したサンプルコンテキストをプレイヤーが観察する。
アームを再生することで(すべてのコンテキストにわたって)将来の時間ステップの固定および既知の回数をブロックする。
我々は、$mathcalO(log T)$-regret w.r.t.$alpha$regret戦略を$Tタイムステップで保証し、$Omega(log(T)$low boundと一致する UCB ベースのフル情報アルゴリズムの変種を提案する。
論文 参考訳（メタデータ） (2020-03-06T20:34:42Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。