論文の概要: Randomized Greedy Learning for Non-monotone Stochastic Submodular Maximization Under Full-bandit Feedback

• arxiv url: http://arxiv.org/abs/2302.01324v1
• Date: Thu, 2 Feb 2023 18:52:14 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-03 12:39:05.085775
• Title: Randomized Greedy Learning for Non-monotone Stochastic Submodular Maximization Under Full-bandit Feedback
• Title（参考訳）: 非単調確率部分モジュラー最大化のための全帯域フィードバックによるランダム化グレディラーニング
• Authors: Fares Fourati, Vaneet Aggarwal, Christopher John Quinn, Mohamed-Slim Alouini
• Abstract要約: 本稿では,非拘束型マルチアームバンディットのフルバンドフィードバックとサブモジュール性に対する報奨問題について検討する。 RGLは、サブモジュールおよび非サブモジュール設定において、他のフルバンド変種よりも経験的に優れていることを示す。
• 参考スコア（独自算出の注目度）: 98.29086113546045
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We investigate the problem of unconstrained combinatorial multi-armed bandits with full-bandit feedback and stochastic rewards for submodular maximization. Previous works investigate the same problem assuming a submodular and monotone reward function. In this work, we study a more general problem, i.e., when the reward function is not necessarily monotone, and the submodularity is assumed only in expectation. We propose Randomized Greedy Learning (RGL) algorithm and theoretically prove that it achieves a $\frac{1}{2}$-regret upper bound of $\tilde{\mathcal{O}}(n T^{\frac{2}{3}})$ for horizon $T$ and number of arms $n$. We also show in experiments that RGL empirically outperforms other full-bandit variants in submodular and non-submodular settings.
• Abstract（参考訳）: 本研究は,全帯域フィードバックと確率的報酬を伴う非拘束コンビネート型多腕バンディットの問題点について検討する。 先行研究は、部分モジュラーおよびモノトン報酬関数を仮定するのと同じ問題を研究する。 本研究では, 報酬関数が必ずしも単調ではない場合や, 期待値においてのみ部分モジュラリティが仮定される場合など, より一般的な問題について検討する。 我々は,ランダム化グリーディ学習(rgl)アルゴリズムを提案し,理論的に,horizon $t$ と arms $n$ に対する$\tilde{\mathcal{o}}(n t^{\frac{2}{3}}) の上限値である$\frac{1}{2}$-regretの上限値を達成することを証明した。 また、RGLは、サブモジュールおよび非サブモジュール設定において、他のフルバンド変異よりも経験的に優れていることを示す。

関連論文リスト

• Fair Submodular Cover [18.37610521373708]
  フェア・サブモジュラー被覆 (FSC) の研究は、与えられた基底集合$U$, 単調部分モジュラー関数 $f:2UtomathbbR_ge 0$, しきい値$tau$ が与えられる。 まず、二項近似比を$(frac1epsilon, 1-O(epsilon))$とするFSCの離散アルゴリズムを導入する。 次に、$(frac1epsilon, 1-O(epsilon))$-を達成する連続アルゴリズムを示す。
  論文  参考訳（メタデータ） (2024-07-05T18:37:09Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• Dynamic Non-monotone Submodular Maximization [11.354502646593607]
  濃度制約$k$で非単調部分モジュラ函数を最大化することから、同じ制約の下で単調部分モジュラ函数を最大化することへの還元を示す。 我々のアルゴリズムは、ソリューションの$(epsilon)$-approximateを維持し、期待される$O(epsilon-3k3log3(n)log(k)$ query per updateを使用する。
  論文  参考訳（メタデータ） (2023-11-07T03:20:02Z)
• Bandit Multi-linear DR-Submodular Maximization and Its Applications on Adversarial Submodular Bandits [21.54858035450694]
  分割マトロイド制約を持つ部分モジュラー帯域に対するサブ線形後悔アルゴリズムを提案する。 バンドイットの逐次部分モジュラーに対して、既存の研究はO(T2/3)$ regret を証明し、近似比は1/2$である。
  論文  参考訳（メタデータ） (2023-05-21T08:51:55Z)
• Top $K$ Ranking for Multi-Armed Bandit with Noisy Evaluations [102.32996053572144]
  我々は,各ラウンドの開始時に,学習者が各アームの真の報酬について,ノイズのない独立した評価を受けるマルチアームバンディット・セッティングを考える。 評価の方法によって異なるアルゴリズムアプローチと理論的保証を導出する。
  論文  参考訳（メタデータ） (2021-12-13T09:48:54Z)
• On Submodular Contextual Bandits [92.45432756301231]
  作用が基底集合の部分集合であり、平均報酬が未知の単調部分モジュラ函数によってモデル化されるような文脈的包帯の問題を考える。 Inverse Gap Weighting 戦略により,提案アルゴリズムは推定関数の局所的最適度を効率よくランダム化することを示す。
  論文  参考訳（メタデータ） (2021-12-03T21:42:33Z)
• 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)
• Regularized Submodular Maximization at Scale [45.914693923126826]
  亜モジュラリティは本質的に多様性、カバレッジ、代表性の概念に関係している。 正規化部分モジュラ函数 $f = g ell$ を行列式部分モジュラ関数 $g$ とモジュラ関数 $ell$ の差分として最大化する手法を提案する。
  論文  参考訳（メタデータ） (2020-02-10T02:37:18Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。