論文の概要: Bandit Multi-linear DR-Submodular Maximization and Its Applications on
Adversarial Submodular Bandits
- arxiv url: http://arxiv.org/abs/2305.12402v1
- Date: Sun, 21 May 2023 08:51:55 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-23 20:43:11.464580
- Title: Bandit Multi-linear DR-Submodular Maximization and Its Applications on
Adversarial Submodular Bandits
- Title（参考訳）: Bandit Multi-linear DR-submodular Maximization とその応用
- Authors: Zongqi Wan, Jialin Zhang, Wei Chen, Xiaoming Sun, Zhijie Zhang
- Abstract要約: 分割マトロイド制約を持つ部分モジュラー帯域に対するサブ線形後悔アルゴリズムを提案する。
バンドイットの逐次部分モジュラーに対して、既存の研究はO(T2/3)$ regret を証明し、近似比は1/2$である。
- 参考スコア（独自算出の注目度）: 21.54858035450694
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We investigate the online bandit learning of the monotone multi-linear
DR-submodular functions, designing the algorithm $\mathtt{BanditMLSM}$ that
attains $O(T^{2/3}\log T)$ of $(1-1/e)$-regret. Then we reduce submodular
bandit with partition matroid constraint and bandit sequential monotone
maximization to the online bandit learning of the monotone multi-linear
DR-submodular functions, attaining $O(T^{2/3}\log T)$ of $(1-1/e)$-regret in
both problems, which improve the existing results. To the best of our
knowledge, we are the first to give a sublinear regret algorithm for the
submodular bandit with partition matroid constraint. A special case of this
problem is studied by Streeter et al.(2009). They prove a $O(T^{4/5})$
$(1-1/e)$-regret upper bound. For the bandit sequential submodular
maximization, the existing work proves an $O(T^{2/3})$ regret with a suboptimal
$1/2$ approximation ratio (Niazadeh et al. 2021).
- Abstract（参考訳）: 単調多線形dr-サブモジュラー関数のオンラインバンディット学習について検討し,$o(t^{2/3}\log t)$ 1-1/e)$-regret を得るアルゴリズム $\mathtt{banditmlsm}$ を設計した。
次に,分割マトロイド制約とバンディット逐次モノトン最大化により,単調多線形DR-サブモジュラ関数のオンラインバンディット学習を減らし,両問題において$O(T^{2/3}\log T)$(1-1/e)$-regretを実現し,既存の結果を改善する。
私たちの知る限りでは、分割マトロイド制約付きサブモジュラーバンドイットに対して、サブ線形後悔アルゴリズムを最初に与えました。
この問題の特別なケースは、Streeterらによって研究されている。
(2009).
彼らは$O(T^{4/5})$(1-1/e)$-regret上界を証明する。
バンドイットの逐次部分モジュラー最大化について、既存の研究は1/2$近似比(Niazadeh et al. 2021)でO(T^{2/3})$後悔を証明している。
関連論文リスト
- Sum-max Submodular Bandits [7.337919355153117]
このクラスのすべての関数が擬凸と呼ばれる重要な性質を満たすことを示す。
この境界は、単純で効率的なアルゴリズムによって達成され、帯域幅のフィードバックを持つオンラインモノトン部分モジュラーに対して$widetildeObig(T2/3big)$ regret boundで大幅に改善される。
論文 参考訳（メタデータ） (2023-11-10T10:18:50Z) - Randomized Greedy Learning for Non-monotone Stochastic Submodular
Maximization Under Full-bandit Feedback [98.29086113546045]
本稿では,非拘束型マルチアームバンディットのフルバンドフィードバックとサブモジュール性に対する報奨問題について検討する。
RGLは、サブモジュールおよび非サブモジュール設定において、他のフルバンド変種よりも経験的に優れていることを示す。
論文 参考訳（メタデータ） (2023-02-02T18:52:14Z) - Online Learning for Non-monotone Submodular Maximization: From Full
Information to Bandit Feedback [12.914842850902456]
本稿では, 閉鎖凸集合上でのオンライン非単調連続DR-サブモジュラー問題を再検討する。
メタ-MFWアルゴリズムは$O(sqrtT)$の1/e$-regret境界を達成する。
次に、Mono-MFWを帯域設定に拡張し、$O(T8/9)の1/e$-regretバウンダリのBandit-MFWアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-08-16T09:32:37Z) - Corralling a Larger Band of Bandits: A Case Study on Switching Regret
for Linear Bandits [99.86860277006318]
本稿では,一組の逆アルゴリズムを組み合わせ,学習することの問題点について考察する。
Agarwal et al. の CORRAL はこの目標を、$widetildeO(sqrtd S T)$ の残酷なオーバーヘッドで達成している。
この問題に触発されて、後悔のオーバーヘッドが百万ドルにしか依存しない大規模バンディットアルゴリズムのバンドを囲む新しいレシピを提案する。
論文 参考訳（メタデータ） (2022-02-12T21:55:44Z) - On Submodular Contextual Bandits [92.45432756301231]
作用が基底集合の部分集合であり、平均報酬が未知の単調部分モジュラ函数によってモデル化されるような文脈的包帯の問題を考える。
Inverse Gap Weighting 戦略により,提案アルゴリズムは推定関数の局所的最適度を効率よくランダム化することを示す。
論文 参考訳（メタデータ） (2021-12-03T21:42:33Z) - Faster First-Order Algorithms for Monotone Strongly DR-Submodular
Maximization [11.919431962501479]
連続部分モジュラ函数はDimishing Returns (DR) の性質を満たすが、これは非負の方向に沿って凹凸であることを意味する。
そこで本稿では,lceilfracLmurce$のあとで,証明可能な1-fracce$近似比と一致する新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-11-15T18:53:14Z) - Improved Regret Bounds for Online Submodular Maximization [10.089520556398575]
我々は、各ステップ$tin[T]$において、固定凸からアクション$x_t$を選択し、コンパクトなドメインセット$mathcalK$を選択するオンライン最適化問題を考える。
ユーティリティ関数 $f_t(cdot)$ が明らかになり、アルゴリズムはペイオフ $f_t(x_t)$ を受け取る。
論文 参考訳（メタデータ） (2021-06-15T02:05:35Z) - The Power of Subsampling in Submodular Maximization [51.629656762796564]
このアプローチは,既存の手法よりもはるかに単純であるにもかかわらず,最適/最先端の結果をもたらすことを示す。
我々は,映像要約,位置情報要約,映画推薦タスクにおけるアルゴリズムの有効性を実証的に示す。
論文 参考訳（メタデータ） (2021-04-06T20:25:57Z) - Revisiting Modified Greedy Algorithm for Monotone Submodular
Maximization with a Knapsack Constraint [75.85952446237599]
修正されたグリードアルゴリズムは、近似係数が0.305$であることを示す。
最適なデータ依存上界を導出する。
また、分岐やバウンドといったアルゴリズムの効率を大幅に改善するためにも使うことができる。
論文 参考訳（メタデータ） (2020-08-12T15:40:21Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。