論文の概要: Logarithmic Regret for Unconstrained Submodular Maximization Stochastic Bandit
- arxiv url: http://arxiv.org/abs/2410.08578v1
- Date: Fri, 11 Oct 2024 07:07:12 GMT
- ステータス: 処理完了
- システム内更新日: 2024-10-30 23:04:57.376559
- Title: Logarithmic Regret for Unconstrained Submodular Maximization Stochastic Bandit
- Title（参考訳）: 非拘束的部分モジュラー最大化確率帯域に対する対数回帰法
- Authors: Julien Zhou, Pierre Gaillard, Thibaud Rahier, Julyan Arbel,
- Abstract要約: 本稿では,オンラインの非依存サブモジュール問題(Online USM)を,帯域幅のフィードバックを伴う設定で解決する。
この枠組みでは、決定者は、既知の間隔で値を取る非単調な部分モジュラ函数からノイズの報奨を受ける。
本稿では、オフラインおよびオンラインのフル情報設定から、Double-Greedy-Explore-then-Commit(DG-ETC)を適用したDG-ETCを提案する。
- 参考スコア（独自算出の注目度）: 12.096516329746292
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We address the online unconstrained submodular maximization problem (Online USM), in a setting with stochastic bandit feedback. In this framework, a decision-maker receives noisy rewards from a nonmonotone submodular function, taking values in a known bounded interval. This paper proposes Double-Greedy - Explore-then-Commit (DG-ETC), adapting the Double-Greedy approach from the offline and online full-information settings. DG-ETC satisfies a O(d log(dT)) problemdependent upper bound for the 1/2-approximate pseudo-regret, as well as a O(dT^{2/3}log(dT)^{1/3}) problem-free one at the same time, outperforming existing approaches. To that end, we introduce a notion of hardness for submodular functions, characterizing how difficult it is to maximize them with this type of strategy.
- Abstract（参考訳）: オンラインの非制約部分モジュラー最大化問題(Online USM)について,確率的帯域幅フィードバックを用いて検討した。
この枠組みでは、決定者は、既知の有界区間で値を取る非単調な部分モジュラ函数からノイズの報奨を受ける。
本稿では、オフラインおよびオンラインのフル情報設定から、Double-Greedy-Explore-then-Commit(DG-ETC)を適用したDG-ETCを提案する。
DG-ETC は O(d log(dT)) 問題依存上界を 1/2-近似擬回帰に対して満たし、O(dT^{2/3}log(dT)^{1/3}) 問題依存上界を同時に満たし、既存のアプローチより優れている。
そのために, 部分モジュラ函数に対する硬さの概念を導入し, この戦略でそれらを最大化することがいかに困難であるかを特徴付ける。
関連論文リスト
- Continuous K-Max Bandits [54.21533414838677]
我々は、連続的な結果分布と弱い値-インデックスフィードバックを持つ、$K$-Maxのマルチアームバンディット問題について検討する。
この設定は、レコメンデーションシステム、分散コンピューティング、サーバスケジューリングなどにおいて重要なアプリケーションをキャプチャします。
我々の重要な貢献は、適応的な離散化とバイアス補正された信頼境界を組み合わせた計算効率の良いアルゴリズムDCK-UCBである。
論文 参考訳（メタデータ） (2025-02-19T06:37:37Z) - Stochastic $k$-Submodular Bandits with Full Bandit Feedback [29.705337940879705]
オンラインの$k$-submodular最適化問題に対して,最初のサブ線形$alpha$-regretバウンダリをフルバンドフィードバックで提示する。
私たちの研究の重要な貢献は、アルゴリズムの堅牢性を分析することです。
論文 参考訳（メタデータ） (2024-12-14T05:02:53Z) - Federated Combinatorial Multi-Agent Multi-Armed Bandits [79.1700188160944]
本稿では,Banditを用いたオンライン最適化に適したフェデレーション学習フレームワークを提案する。
この設定では、エージェントのアームサブセットは、個々のアーム情報にアクセスせずにこれらのサブセットに対するノイズの多い報酬を観察し、特定の間隔で協力して情報を共有することができる。
論文 参考訳（メタデータ） (2024-05-09T17:40:09Z) - Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems [61.85150061213987]
一般化線形モデル (GLM) フレームワークを用いて, citelu2021low で提案した一般化低ランク行列帯域問題について検討する。
既存のアルゴリズムの計算不可能性と理論的制約を克服するため,まずG-ESTTフレームワークを提案する。
G-ESTT は $tildeO(sqrt(d_1+d_2)3/2Mr3/2T)$ bound of regret を達成でき、G-ESTS は $tildeO を達成できることを示す。
論文 参考訳（メタデータ） (2024-01-14T14:14:19Z) - Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳（メタデータ） (2023-12-13T11:08:25Z) - 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) - Borda Regret Minimization for Generalized Linear Dueling Bandits [65.09919504862496]
本稿では,ボルダスコアが最も高い項目を識別することを目的とした,デュエルバンディットに対するボルダ後悔最小化問題について検討する。
本稿では,多くの既存モデルをカバーする一般化線形デュエルバンドモデルのリッチクラスを提案する。
我々のアルゴリズムは$tildeO(d2/3 T2/3)$ regretを達成し、これも最適である。
論文 参考訳（メタデータ） (2023-03-15T17:59:27Z) - 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) - Online Nonsubmodular Minimization with Delayed Costs: From Full
Information to Bandit Feedback [98.7678704343537]
我々は,オンラインおよび近似的オンライン帯域勾配勾配アルゴリズムのいくつかの変種に対する後悔の保証を,特別な構造を持つ非部分モジュラ関数のクラスに焦点をあてる。
我々は,決定の選択と帰属費用の受け取りの遅れが無拘束である場合でも,エージェントの完全な情報と盗賊のフィードバック設定に対する後悔の限界を導出する。
論文 参考訳（メタデータ） (2022-05-15T08:27:12Z) - Submodular Bandit Problem Under Multiple Constraints [8.100450025624443]
我々は、$l$knapsacksと$k$-system制約の交わりの下で、部分モジュラーバンディット問題を導入する。
この問題を解決するために,標準あるいは修正された高信頼境界に適応的に焦点をあてる非グレーディアルゴリズムを提案する。
近似比が高速アルゴリズムのそれと一致するような近似後悔の確率の高い上限を提供する。
論文 参考訳（メタデータ） (2020-06-01T01:28:44Z) - Online DR-Submodular Maximization with Stochastic Cumulative Constraints [17.660958043781154]
線形長期制約を伴うオンライン連続DR-サブモジュラーを考える。
オンラインラグランジアンFrank-Wolfe (OLFW) アルゴリズムは、この種のオンライン問題を解く。
論文 参考訳（メタデータ） (2020-05-29T17:55:42Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。