論文の概要: Stochastic $k$-Submodular Bandits with Full Bandit Feedback
- arxiv url: http://arxiv.org/abs/2412.10682v1
- Date: Sat, 14 Dec 2024 05:02:53 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-17 13:59:50.209875
- Title: Stochastic $k$-Submodular Bandits with Full Bandit Feedback
- Title（参考訳）: 完全帯域フィードバック付き確率$k$サブモジュラバンド
- Authors: Guanyu Nie, Vaneet Aggarwal, Christopher John Quinn,
- Abstract要約: オンラインの$k$-submodular最適化問題に対して,最初のサブ線形$alpha$-regretバウンダリをフルバンドフィードバックで提示する。
私たちの研究の重要な貢献は、アルゴリズムの堅牢性を分析することです。
- 参考スコア（独自算出の注目度）: 29.705337940879705
- License:
- Abstract: In this paper, we present the first sublinear $\alpha$-regret bounds for online $k$-submodular optimization problems with full-bandit feedback, where $\alpha$ is a corresponding offline approximation ratio. Specifically, we propose online algorithms for multiple $k$-submodular stochastic combinatorial multi-armed bandit problems, including (i) monotone functions and individual size constraints, (ii) monotone functions with matroid constraints, (iii) non-monotone functions with matroid constraints, (iv) non-monotone functions without constraints, and (v) monotone functions without constraints. We transform approximation algorithms for offline $k$-submodular maximization problems into online algorithms through the offline-to-online framework proposed by Nie et al. (2023a). A key contribution of our work is analyzing the robustness of the offline algorithms.
- Abstract（参考訳）: 本稿では、オンラインの$k$サブモジュラー最適化問題に対する最初のサブ線形$\alpha$-regretバウンダリをフルバンドフィードバックで示し、$\alpha$は対応するオフライン近似比である。
具体的には、複数の$k$-submodular stochastic combinatorial multi-armed bandit問題に対するオンラインアルゴリズムを提案する。
(i)単調関数と個々のサイズ制約
(ii)マトロイド制約付き単調関数
(三)マットロイド制約のある単調でない関数
(四)制約のない非単調関数、及び
(v)制約のない単調関数。
我々は,オフラインの$k$-submodular maximization問題に対する近似アルゴリズムを,Nie et al (2023a) によって提案されたオフラインからオンラインへのフレームワークを通じてオンラインアルゴリズムに変換する。
私たちの研究の重要な貢献は、オフラインアルゴリズムの堅牢性を分析することです。
関連論文リスト
- Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
離散部分モジュラー問題を連続的に最適化するために,$textbfMA-OSMA$アルゴリズムを提案する。
また、一様分布を混合することによりKLの発散を効果的に活用する、プロジェクションフリーな$textbfMA-OSEA$アルゴリズムも導入する。
我々のアルゴリズムは最先端OSGアルゴリズムによって提供される$(frac11+c)$-approximationを大幅に改善する。
論文 参考訳（メタデータ） (2025-02-07T15:57:56Z) - Federated Combinatorial Multi-Agent Multi-Armed Bandits [79.1700188160944]
本稿では,Banditを用いたオンライン最適化に適したフェデレーション学習フレームワークを提案する。
この設定では、エージェントのアームサブセットは、個々のアーム情報にアクセスせずにこれらのサブセットに対するノイズの多い報酬を観察し、特定の間隔で協力して情報を共有することができる。
論文 参考訳（メタデータ） (2024-05-09T17:40:09Z) - Bridging the Gap Between General and Down-Closed Convex Sets in
Submodular Maximization [8.225819874406238]
Mualem citemualem23re は、この手法がダウンクローズド制約と非ダウンクローズド制約の間を滑らかにできないことを示す。
本研究では,物体を2つの異なる凸体に自然分解した新しいオフラインおよびオンラインアルゴリズムを提案する。
また、3つのオフラインおよび2つのオンラインアプリケーションにまたがる提案アルゴリズムの優位性を実証的に示す。
論文 参考訳（メタデータ） (2024-01-17T14:56:42Z) - 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) - Randomized Greedy Learning for Non-monotone Stochastic Submodular
Maximization Under Full-bandit Feedback [98.29086113546045]
本稿では,非拘束型マルチアームバンディットのフルバンドフィードバックとサブモジュール性に対する報奨問題について検討する。
RGLは、サブモジュールおよび非サブモジュール設定において、他のフルバンド変種よりも経験的に優れていることを示す。
論文 参考訳（メタデータ） (2023-02-02T18:52:14Z) - A Framework for Adapting Offline Algorithms to Solve Combinatorial
Multi-Armed Bandit Problems with Bandit Feedback [27.192028744078282]
離散オフライン近似アルゴリズムをサブ線形$alpha$-regretに適応するためのフレームワークを提供する。
提案手法は準モジュラー地平線における多種多様な応用に適用できる。
論文 参考訳（メタデータ） (2023-01-30T23:18:06Z) - Online Nonsubmodular Minimization with Delayed Costs: From Full
Information to Bandit Feedback [98.7678704343537]
我々は,オンラインおよび近似的オンライン帯域勾配勾配アルゴリズムのいくつかの変種に対する後悔の保証を,特別な構造を持つ非部分モジュラ関数のクラスに焦点をあてる。
我々は,決定の選択と帰属費用の受け取りの遅れが無拘束である場合でも,エージェントの完全な情報と盗賊のフィードバック設定に対する後悔の限界を導出する。
論文 参考訳（メタデータ） (2022-05-15T08:27:12Z) - Submodular + Concave [53.208470310734825]
第一次最適化法が凹関数の最大目的値に収束できることはよく確立されている。
本研究では、滑らかな函数凸体(英語版)の行列式を$F(x) = G(x) +C(x)$で始める。
このクラスの函数は、保証がないような凹凸函数と連続DR-部分モジュラ函数の両方の拡張である。
論文 参考訳（メタデータ） (2021-06-09T01:59:55Z) - Fast and Private Submodular and $k$-Submodular Functions Maximization
with Matroid Constraints [27.070004659301162]
差分プライバシーの枠組みにおいて, マットロイド制約を受ける単調部分モジュラ函数を最大化する問題について検討する。
マットロイド制約を受けるべき$k$submodular関数を保存する最初の$frac12$-approximationアルゴリズムを与える。
論文 参考訳（メタデータ） (2020-06-28T23:18:58Z) - Submodular Bandit Problem Under Multiple Constraints [8.100450025624443]
我々は、$l$knapsacksと$k$-system制約の交わりの下で、部分モジュラーバンディット問題を導入する。
この問題を解決するために,標準あるいは修正された高信頼境界に適応的に焦点をあてる非グレーディアルゴリズムを提案する。
近似比が高速アルゴリズムのそれと一致するような近似後悔の確率の高い上限を提供する。
論文 参考訳（メタデータ） (2020-06-01T01:28:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。